1、模式識別與機器學習期末考查思考題1：簡述模式識別與機器學習研究的共同問題和各自的研究側重點。機器學習是研究讓機器（計算機）從經驗和數據獲得知識或提高自身能力的科學。機器學習和模式識別是分別從計算機科學和工程的角度發展起來的。然而近年來，由于它們關心的很多共同問題（分類、聚類、特征選擇、信息融合等），這兩個領域的界限越來越模糊。機器學習和模式識別的理論和方法可用來解決很多機器感知和信息處理的問題，其中包括圖像/視頻分析、（文本、語音、印刷、手寫）文檔分析、信息檢索和網絡搜索等。近年來，機器學習和模式識別的研究吸引了越來越多的研究者，理論和方法的進步促進了工程應用中識別性能的明顯提高。機器學習：要

2、使計算機具有知識一般有兩種方法；一種是由知識工程師將有關的知識歸納、整理，并且表示為計算機可以接受、處理的方式輸入計算機。另一種是使計算機本身有獲得知識的能力，它可以學習人類已有的知識，并且在實踐過程中不總結、完善，這種方式稱為機器學習。機器學習的研究，主要在以下三個方面進行：一是研究人類學習的機理、人腦思維的過程；和機器學習的方法；以及建立針對具體任務的學習系統。 機器學習的研究是在信息科學、腦科學、神經心理學、邏輯學、模糊數學等多種學科基礎上的。依賴于這些學科而共同發展。目前已經取得很大的進展，但還沒有能完全解決問題。 模式識別：模式識別是研究如何使機器具有感知能力，主要研究視覺模式和聽覺

3、模式的識別。如識別物體、地形、圖像、字體（如簽字）等。在日常生活各方面以及軍事上都有廣大的用途。近年來迅速發展起來應用模糊數學模式、人工神經網絡模式的方法逐漸取代傳統的用統計模式和結構模式的識別方法。 特別神經網絡方法在模式識別中取得較大進展。 理解自然語言 計算機如能“聽懂”人的語言（如漢語、英語等），便可以直接用口語操作計算機，這將給人們帶來極大的便利。計算機理解自然語言的研究有以下三個目標：一是計算機能正確理解人類的自然語言輸入的信息，并能正確答復（或響應）輸入的信息。二是計算機對輸入的信息能產生相應的摘要，而且復述輸入的內容。三是計算機能把輸入的自然語言翻譯成要求的另一種語言，如將漢語

4、譯成英語或將英語譯成漢語等。目前，研究計算機進行文字或語言的自動翻譯，人們作了大量的嘗試，還沒有找到最佳的方法，有待于更進一步深入探索。機器學習今后主要的研究方向如下：1)人類學習機制的研究；2)發展和完善現有學習方法，建立實用的學習系統，特別是開展多種學習方法協同工作的集成化系統的研究；通過多個現有的具體例子進行分析，歸納為更一般的概念.機器學習所關注的一個根本問題是如何提高學習系統的泛化能力，或者說是機器在數據中發現的模式怎樣才能具有良好的推廣能力.機器學習的研究主旨是使用計算機模擬人類的學習活動，它是研究計算機識別現有知識、獲取新知識、不斷改善性能和實現自身完善的方法。 模式識別(Pat

5、tern Recognition)是指對表征事物或現象的各種形式的(數值的、文字的和邏輯關系的)信息進行處理和分析,以對事物或現象進行描述、辨認、分類和解釋的過程,是信息科學和人工智能的重要組成部分。模式識別的研究的內容是指利用計算機對要分析的客觀事物與標準模板的通過某種模式算法，對其進行分類，在錯誤概率最小的條件，使識別到的結果最接近于待識別的客觀事實。先用一定數量的樣本，根據它們之間的相似性進行分類器設計，而后用所設計的分類器對待識別的樣本進行分類決策目前模式識別的主要研究的是提取目標的運動特征，或在此基礎上進行對目標的整體的運動軌跡進行研究，2：列出在模式識別與機器學習中的常用算法及其優

6、缺點。1.k-近鄰法近鄰法是一種最簡單的非參數模式識別方法中的模式匹配法,它主要依據樣本間的多維空間距離來實現分類.令Dn=x1,x2,xn,其中,每一個樣本所屬的類別均已知.對于測試樣本點x,分類是，在集合Dn中與每個模板進行一一比較，將距離最近的點標記為x'.那么,近鄰法就是把點x分為x'所屬類別.（1）優點：算法簡單，易于理解和分析，分類效果好。（2）缺點：大樣本的計算量大，存儲所有樣本需較大容量，樣本小時誤差難控制。2. 貝葉斯決策法貝葉斯決策法是基于概率統計的基本的判別函數分類法。（1）貝葉斯決策優點：算法簡單，易于理解和分析，其基本概念被眾多的先進決策算法運用，判斷

7、結果較精確。（2）貝葉斯決策的主要的缺陷：在采用貝葉斯算法之前，要事先收集一定數量的符合實際情況的樣本，這樣才能較精確得出先驗概率和條件概率。且在實際生活中，決策表是很難確定的，計算所需要的損失差數，往往是根據多位專家根據實際具體問題，共同其錯誤的決策造成的損失的嚴重程度來大概確立的。3. 逆向傳播神經網絡其算法在應用中的缺點主要如下：（1） 算法的穩定性與學效率成反比。（2） 還沒找到某一明確的規則確定學效率的大小，尤其相對于非線性網絡來說，學效率的選擇更是一個難題。（3） 訓練過程也可能陷入局部最小，可以通過變換初始值進行多次訓練來決絕這個問題，但又增加了計算的負擔。（4） 沒有有效的方法

8、可以確定網絡層數，太多或太少都會影響系統的性能。（5） 收斂于局部極小的較早收斂問題尚未解決主要的優點如下：（6） 每個神經元的運算功能十分簡單。（7） 各神經元之間是并行結構互使得其具有高速處理能力。（8） 在神經網絡中，知識與信息的存儲表現為神經元之間分布式的物理聯系，知識存儲容量很大。（9） 網狀結構似的整個系統的工作不會因為個別的神經元的損失而大大降低系統性能。（10） 它可以實現輸入和輸出數據之間的非線性映射.4. 遺傳算法遺傳算法的優點 遺傳算法解決了傳統優化算法容易誤入局部最優解的缺點，不用單值迭代，而是從解集合進行搜索，利于全局擇優。遺傳算法需要的參數少，容易形成通用算法程序。

9、 遺傳算法有極強的容錯能力，遺傳算法的初始串集本身就帶有大量與最優解甚遠的信息；該算法具有收斂性，通過選擇、交叉、變異操作能迅速排除與最優解相差極大的串。 遺傳算法是采用隨機方法進行最優解搜索，選擇體現了向最優解迫近，交叉體現了最優解的產生，變異體現了全局最優解的復蓋。 力稱為隱含并行性(Implicit Parallelism)。它說明遺傳算法其內在具有并行處理的特質。 遺傳算法的缺點遺傳算法雖然可以在多種領域都有實際應用，并且也展示了它潛力和寬廣前景；遺傳算法還有大量的問題需要研究，目前也還有各種不足。選取的值范圍大，變量多時，收斂速度也隨之下降，甚至有時還無法給定取值范圍時。可找到最優解

10、附近，但無法精確確定最優解位置。遺傳算法的參數(n,Pm,Pc)選擇還沒準確的定數，還需要進一步研究其數學基礎理論。5. 決策樹算法優點：由于決策樹具有易構造、結構簡單、易于理解、分類精度高，且易于轉化成SQI語句有效地存取數據庫，易于算法實現等優點，決策樹尤其適于數據挖掘。描述簡單，分類速度快，特別適合大規模的數據處理缺點：在學習過程中不能有很多背景知識。是非遞增學習算法；ID3決策樹是單變量決策樹，復雜概念的表達困難；同性間的相互關系強調不夠；抗噪性差。決策樹的這種明確性可能帶來誤導.神經網絡方法神經網絡由于本身良好的魯棒性、自組織自適應性、并行處理、分布存儲和高度容錯等特性非常適合解決數

11、據挖掘的問題，因此近年來越來越受到人們的關注。典型的神經網絡模型主要分3大類：以感知機、BP反向傳播模型、函數型網絡為代表的，用于分類、預測和模式識別的前饋式神經網絡模型；以Hopfield的離散模型和連續模型為代表的，分別用于聯想記憶和優化計算的反饋式神經網絡模型；以ART模型、Koholon模型為代表的，用于聚類的自組織映射方法。神經網絡方法的缺點是"黑箱"性，人們難以理解網絡的學習和決策過程。遺傳算法遺傳算法是一種基于生物自然選擇與遺傳機理的隨機搜索算法，是一種仿生全局優化方法。遺傳算法具有的隱含并行性、易于和其它模型結合等性質使得它在數據挖掘中被加以應用。Sunil

12、已成功地開發了一個基于遺傳算法的數據挖掘工具，利用該工具對兩個飛機失事的真實數據庫進行了數據挖掘實驗，結果表明遺傳算法是進行數據挖掘的有效方法之一。遺傳算法的應用還體現在與神經網絡、粗集等技術的結合上。如利用遺傳算法優化神經網絡結構，在不增加錯誤率的前提下，刪除多余的連接和隱層單元；用遺傳算法和BP算法結合訓練神經網絡，然后從網絡提取規則等。但遺傳算法的算法較復雜，收斂于局部極小的較早收斂問題尚未解決。決策樹方法決策樹是一種常用于預測模型的算法，它通過將大量數據有目的分類，從中找到一些有價值的，潛在的信息。它的主要優點是描述簡單，分類速度快，特別適合大規模的數據處理。最有影響和最早的決策樹方法

13、是由Quinlan提出的著名的基于信息熵的ID3算法。它的主要問題是：ID3是非遞增學習算法；ID3決策樹是單變量決策樹，復雜概念的表達困難；同性間的相互關系強調不夠；抗噪性差。針對上述問題，出現了許多較好的改進算法，如 Schlimmer和Fisher設計了ID4遞增式學習算法;鐘鳴，陳文偉等提出了IBLE算法等。 粗集方法粗集理論是一種研究不精確、不確定知識的數學工具。粗集方法有幾個優點：不需要給出額外信息；簡化輸入信息的表達空間；算法簡單，易于操作。粗集處理的對象是類似二維關系表的信息表。目前成熟的關系數據庫管理系統和新發展起來的數據倉庫管理系統，為粗集的數據挖掘奠定了堅實的基礎。但粗集

14、的數學基礎是集合論，難以直接處理連續的屬性。而現實信息表中連續屬性是普遍存在的。因此連續屬性的離散化是制約粗集理論實用化的難點。現在國際上已經研制出來了一些基于粗集的工具應用軟件，如加拿大Regina大學開發的KDD-R;美國Kansas大學開發的LERS等。覆蓋正例排斥反例方法它是利用覆蓋所有正例、排斥所有反例的思想來尋找規則。首先在正例集合中任選一個種子，到反例集合中逐個比較。與字段取值構成的選擇子相容則舍去，相反則保留。按此思想循環所有正例種子，將得到正例的規則(選擇子的合取式)。比較典型的算法有Michalski的AQ11方法、洪家榮改進的AQ15方法以及他的AE5方法。統計分析方法在

15、數據庫字段項之間存在兩種關系：函數關系(能用函數公式表示的確定性關系)和相關關系(不能用函數公式表示，但仍是相關確定性關系)，對它們的分析可采用統計學方法，即利用統計學原理對數據庫中的信息進行分析。可進行常用統計(求大量數據中的最大值、最小值、總和、平均值等)、回歸分析(用回歸方程來表示變量間的數量關系)、相關分析(用相關系數來度量變量間的相關程度)、差異分析(從樣本統計量的值得出差異來確定總體參數之間是否存在差異)等。模糊集方法即利用模糊集合理論對實際問題進行模糊評判、模糊決策、模糊模式識別和模糊聚類分析。系統的復雜性越高，模糊性越強，一般模糊集合理論是用隸屬度來刻畫模糊事物的亦此亦彼性的。

16、李德毅等人在傳統模糊理論和概率統計的基礎上，提出了定性定量不確定性轉換模型-云模型，并形成了云理論。3：請應用一種具體的模式識別與機器學習算法，簡述解決問題的主要步驟。反向傳播網絡訓練設計步驟及算法設置初始值（初始化訓練的樣本集、學習速率lr，賦給每個連接權值wij和節點數的閾值）。輸入一個隨機樣本X和期望輸出T。計算實際輸出Y,計算公式見公式（5）（6）。 （5） （6）從輸出層向第一隱層，逐層反向調整權值，調整公式見公式（7）（8）（9）。 （7） （8） （9）轉 ，重復執行，直到誤差滿足要求為止。遺傳算法步驟：（1） 初始化群體；（2） 計算群體上每個個體的適應度值；（3） 按由個體適

17、應度值 所決定的某個規則選擇將 進入下一代的個體；（4） 按概率Pc進行交叉操作；（5） 按概率Pc進行突變操作；（6） 沒有滿足某種停止條件，則轉第(2)步，否則進入(7)。（7） 輸出種群中適應度值最優的 染色體作為問題 的滿意解或最優解。說明：算法停止條件最簡單的有如下兩種：完成了預先給定的進化代數則停止；種群中的最優個體在連續若干代沒有改進或平均適應度若干代基本沒有改進時停止。4：在模式識別與機器學習中，常常需要用已知的數據集來訓練所建立的模型。如果所建立的模型被說成是overfit，請解釋這是什么意思？請陳述一些避免overfit的方法。是"過擬合"現象，過擬合主

18、要指訓練后的網絡對訓練樣本（Train sample）具有極高的擬合精度，但是對工作樣本（Work sample）的預測誤差卻非常大。過擬合著重于網絡的推廣能力（Generalization Ability）問題，即網絡學習能力與推廣能力之間滿足一般測不準關系.1. 測不準關系式中的過擬合參數 P的確定將有助于避免出現"過擬合"現象. 2. 過擬合的解決方法是設置滿足問題求解精度要求的上限，不要將目標誤差設置太小。個人認為過擬合還與樣本過于冗余有關，采用刪除冗余樣本信息的特征樣本，不僅可以加快訓練速度，還可以改善過擬合問題。3. 1.使用初期終止的方法來提高泛化能力。用訓練

19、集來訓練網絡，同時考察網絡在校驗集上的誤差，一旦校驗集上的誤差的誤差不再下降（或者累計n次不再下降），那么就停止訓練，這樣可以減輕網絡過擬合的程度。4. 防止過擬合（overfitting）的方法：（1）按照一定比例在TRAIN函數導入校驗和測試的VV和VT參數；（2）采用TRAINGDX和LEARNGDM組合訓練；（3）采用TRAINBR函數訓練等等，發現沒有一個的泛化（GENERALIZATION)效果能很理想的。5. 通過加入擬合函數的先驗知識,加上正則項?；蚴羌討土P項。決策樹對此歷史數據可能非常準確,一旦應用到新的數據時準確性卻急劇下降,我們稱這種情況為訓練過度.為了使得到的決策樹所蘊

20、含的規則具有普遍意義,必須防止訓練過度,同時也減少了訓練的時間.因此我們需要有一種方法能讓我們在適當的時候停止樹的生長.常用的方法是設定決策樹的最大高度(層數)來限制樹的生長.還有一種方法是設定每個節點必須包含的最少記錄數,當節點中記錄的個數小于這個數值時就停止分割.5：在模式識別與機器學習的研究中，還不斷有人提出新的算法。請問有那些方法可以用來判定他們的優劣？1. 正確性    說一個算法是正確的，是指對于一切合法的輸入數據，該算法經過有限時間（算法意義上的有限）的執行都能產生正確（或者說滿足規格說明要求）的結果。2. 時間復雜性應該怎樣計算一個算法的執行時間呢

21、？首先想到的是，我們應選擇一種度量，對解決同一個問題的諸多算法用該度量可有效地進行比較。：（1）它能告訴我們算法所用方法（包括數據結構）的時間效率；（2）它與算法描述語言（或程序設計語言）及設計風格無關；（3）它與算法實現過程中的許多細節：諸如增加循環下標、計算數組下標、設置數據結構指針等簿記運算無關；（4）它應該是足夠精確和具有一般性的。一個算法的時間復雜性是指該算法的基本運算次數。   3. 占用空間算法執行需要存儲空間來存放算法本身包含的語句、常數、變量、輸入數據和實現其運算所需的數據（如中間結果等），此外還需要一些工作空間用來對（以某種方式存儲的）數據進行

22、操作。4. 可讀性    可讀性好的算法有助于設計者和他人閱讀、理解、修改和重用。與此相反，晦澀難懂的算法不但容易隱藏較多的錯誤，而且增加了人們在閱讀、理解、調試、修改和重用算法等方面的困難。5. 堅固性     當輸入數據非法時，算法能適當地作出合適的反應。時間復雜度算法分析同一問題可用不同算法解決，而一個算法的質量優劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮。1、時間復雜度（1）時間頻度一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才

23、能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。（2）時間復雜度在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什么規律。為此，我們引入時間復雜度概念。一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T（n)/f(n)的極限值為

24、不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n),稱O(f(n) 為算法的漸進時間復雜度，簡稱時間復雜度。在各種不同算法中，若算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。按數量級遞增排列，常見的時間復雜度有：常數階O(1),對數階O(log2n),線性階O(n),線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),.，k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間

25、復雜度不斷增大，算法的執行效率越低。2、空間復雜度與時間復雜度類似，空間復雜度是指算法在計算機內執行時所需存儲空間的度量。記作:S(n)=O(f(n)我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規模。6：如果你所遇到的數據集是純數值型數據，你會采用那些模式識別與機器學習算法？若是包含大量非數值數據你會采用那些模式識別與機器學習算法？為什么？純數值型數據：貝葉斯決策法，神經網絡非純數值型數據：決策樹/1. k-近鄰法，是一種最簡單的模式識別方法中的模式匹配法,它主要依據樣本間的多維空間距離來實現分類.2. 貝葉斯決策法是基于概率統計的基本的判別函數分類法。只要知道先驗概率和條件概率就可以

26、對樣本進行判斷，算法簡單，易于理解和分析，其基本概念被眾多的先進決策算法運用，判斷結果較精確。由于數據是純數值型數據，數據簡單，樣本間的空間距離易計算，且先驗概率和條件概率易求得。2. BP神經網絡算法,神經網絡只能處理數值型數據建立神經網絡需要做的數據準備工作量很大. 要想得到準確度高的模型必須認真的進行數據清洗,整理,轉換,選擇等工作,對任何數據挖掘技術都是這樣,神經網絡尤其注重這一點.比如神經網絡要求所有的輸入變量都必須是0-1(或-1 - +1)之間的實數,因此像"地區"之類文本數據必須先做必要的處理變成數值之后才能用作神經網絡的輸入.但每個神經元的運算功能十分簡單。各神經元之間是并行結構互使得其具有高速處理能力。在神經網絡中，知識與信息的存儲表現為神經元之間分布式的物理聯系，知識存儲容量很大。貝葉斯算法是一種具有最小錯誤率或最小