模式識別非監(jiān)督學習方法

模式識別非監(jiān)督學習方法第1頁，共60頁，2023年，2月20日，星期一2主要內容1.引言2.單峰子集（類）的分離方法3.類別分離的間接方法4.分級聚類方法第2頁，共60頁，2023年，2月20日，星期一31.引言第3頁，共60頁，2023年，2月20日，星期一4引言有監(jiān)督學習（supervisedlearning)：分類器設計方法是在樣本集中的類別標簽已知的條件下進行的，這些樣本稱為訓練樣本。在樣本標簽已知的情況下，可以統(tǒng)計出各類訓練樣本不同的描述量，如其概率分布，或在特征空間分布的區(qū)域等，利用這些參數(shù)進行分類器設計。用已知類別的樣本訓練分類器，以求對訓練集的數(shù)據達到某種最優(yōu)，并能推廣到對新數(shù)據的分類。第4頁，共60頁，2023年，2月20日，星期一5無監(jiān)督學習（unsupervisedlearning)：樣本數(shù)據類別未知，需要根據樣本間的相似性對樣本集進行分類(聚類，clustering)，試圖使類內差距最小化，類間差距最大化。利用聚類結果，可以提取數(shù)據集中隱藏的信息，對未來數(shù)據進行預測和分類。應用于數(shù)據挖掘、模式識別、圖像處理、經濟學……引言第5頁，共60頁，2023年，2月20日，星期一6廣泛的應用領域商務：幫助市場分析人員從客戶信息庫中發(fā)現(xiàn)不同的客戶群，用購買模式來刻畫不同的客戶群的特征土地使用：在地球觀測數(shù)據庫中識別土地使用情況相似的地區(qū)保險業(yè)：汽車保險單持有者的分組，標識那些有較高平均賠償成本的客戶。城市規(guī)劃：根據房子的類型，價值和地理分布對房子分組生物學：推導植物和動物的分類，對基因進行分類地震研究:

根據地質斷層的特點把已觀察到的地震中心分成不同的類。第6頁，共60頁，2023年，2月20日，星期一7有監(jiān)督學習與無監(jiān)督學習的區(qū)別有監(jiān)督學習方法必須要有訓練集與測試樣本。在訓練集中找規(guī)律，而對測試樣本使用這種規(guī)律；而非監(jiān)督學習沒有訓練集這一說，只有一組數(shù)據，在該組數(shù)據集內尋找規(guī)律。有監(jiān)督學習方法的目的就是識別事物，識別的結果表現(xiàn)在給待識別數(shù)據加上了標號。因此訓練樣本集必須由帶標號的樣本組成。而非監(jiān)督學習方法只有要分析的數(shù)據集本身，預先沒有什么標號。如果發(fā)現(xiàn)數(shù)據集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預先的分類標號對上號為目的。第7頁，共60頁，2023年，2月20日，星期一8無監(jiān)督學習方法在尋找數(shù)據集中的規(guī)律性，這種規(guī)律性并不一定要達到劃分數(shù)據集的目的，也就是說不一定要“分類”。這一點是比有監(jiān)督學習方法的用途要廣泛。譬如分析一堆數(shù)據的主分量，或分析數(shù)據集有什么特點都可以歸于無監(jiān)督學習方法的范疇。用無監(jiān)督學習方法分析數(shù)據集的主分量與用K-L變換計算數(shù)據集的主分量又有區(qū)別。應該說后者從方法上講不是一種學習方法。因此用K-L變換找主分量不屬于無監(jiān)督學習方法，即方法上不是。而通過學習逐漸找到規(guī)律性這體現(xiàn)了學習方法這一點。在人工神經元網絡中尋找主分量的方法屬于無監(jiān)督學習方法。有監(jiān)督學習與無監(jiān)督學習的區(qū)別第8頁，共60頁，2023年，2月20日，星期一9無監(jiān)督學習方法的分類基于概率密度函數(shù)估計的方法：指設法找到各類別在特征空間的分布參數(shù)再進行分類?；跇颖鹃g相似性度量的方法：直接按樣本間的相似性，或彼此間在特征空間中的距離長短進行分類。其原理是設法定出不同類別的核心，然后依據樣本與這些核心之間的相似性度量，將樣本聚集成不同類別。如何聚類則取決于聚類的準則函數(shù)，以使某種聚類準則達到極值為最佳。兩種聚類方法：

迭代的動態(tài)聚類方法和非迭代的分級聚類方法

第9頁，共60頁，2023年，2月20日，星期一102.單峰子集（類）的分離方法第10頁，共60頁，2023年，2月20日，星期一11思想：把特征空間分為若干個區(qū)域，在每個區(qū)域上混合概率密度函數(shù)是單峰的，每個單峰區(qū)域對應一個類別。【基本思想】第11頁，共60頁，2023年，2月20日，星期一12直接

方法一維空間中的單峰分離:對樣本集KN={xi}應用直方圖/Parzen窗方法估計概率密度函數(shù)，找到概率密度函數(shù)的峰以及峰之間的谷底，以谷底為閾值對數(shù)據進行分割?！疽痪S空間中的單峰子集分離】第12頁，共60頁，2023年，2月20日，星期一13【多維空間投影方法】基本思路：多維空間中直接劃分成單峰區(qū)域比較困難，而一維空間中則比較簡單。尋找一個坐標系統(tǒng)，在該系統(tǒng)下，數(shù)據的混合概率密度函數(shù)可以用邊緣概率密度表示。如果某邊緣概率密度函數(shù)呈現(xiàn)多峰形式，則在此坐標軸上（一維）作分割。做法：把樣本投影到某一一維坐標軸（按某種準則），在這一維上求樣本的概率密度（邊緣概率密度），根據這一概率密度函數(shù)的單峰劃分子集。（如果這一維上只有一個峰，則尋找下一個投影方向。）投影方向：使方差最大的方向，即協(xié)方差陣本征值最大的本征向量方向。第13頁，共60頁，2023年，2月20日，星期一14【投影方法】基本步驟第14頁，共60頁，2023年，2月20日，星期一15問題：這樣投影有時并不能產生多峰的邊緣密度函數(shù)

-方差最大的準則有時并不一定最有利于聚類?！敬嬖趩栴}】失敗的例子第15頁，共60頁，2023年，2月20日，星期一163.類別分離的間接方法第16頁，共60頁，2023年，2月20日，星期一17【引言】回顧：直接方法：1.估計概率密度函數(shù)——

困難2.尋找密度函數(shù)中的單峰間接方法：考查樣本這間的相似性，根據相似性把樣本集劃分為若干子集，使某種表示聚類質量的準則函數(shù)最優(yōu)。第17頁，共60頁，2023年，2月20日，星期一18【引言】相似性度量：以某種距離定義直觀理解：同一類的樣本的特征向量應是相互靠近的?！疤幔禾卣鬟x取合理，能反映所求的聚類關系。與基于密度函數(shù)的方法的關系：概念上相互關聯(lián)，因密度估計也是在樣本間距離的基礎上的。具體關系取決于具體數(shù)據情況。第18頁，共60頁，2023年，2月20日，星期一19動態(tài)聚類方法的任務：

將數(shù)據集劃分成一定數(shù)量的子集，例如將一個數(shù)據集劃分成三個子集，四個子集等。因此要劃分成多少個子集往往要預先確定，或大致確定，這個子集數(shù)目在理想情況下能夠體現(xiàn)數(shù)據集比較合理的劃分。需要解決的問題：怎樣才能知道該數(shù)據集應該劃分的子集數(shù)目

如果劃分數(shù)目已定，則又如何找到最佳劃分。因為數(shù)據集可以有許多種不同的劃分方法，需要對不同的劃分作出評價，并找到優(yōu)化的劃分結果。由于優(yōu)化過程是從不甚合理的劃分到“最佳”劃分，是一個動態(tài)的迭代過程，故這種方法稱為動態(tài)聚類方法?！緞討B(tài)聚類方法】第19頁，共60頁，2023年，2月20日，星期一20對計算機來說，所確定的初始代表點很可能不甚合理，以至于影響到聚類的結果。這就需要有一個對聚類的結果進行修改或迭代的過程，使聚類結果逐步趨向合理。迭代的過程需要一個準則函數(shù)來指導，使迭代朝實現(xiàn)準則函數(shù)的極值化方向收斂。聚類過程：從確定各聚類的代表點開始（比如，確定三個質心點）按各樣本到三個質心最短距離將樣本分到該類【動態(tài)聚類方法】第20頁，共60頁，2023年，2月20日，星期一21三個要點選定某種距離度量作為樣本間的相似性度量；確定樣本合理的初始分類，包括代表點的選擇，初始分類的方法選擇等；確定某種評價聚類結果質量的準則函數(shù)，用以調整初始分類直至達到該準則函數(shù)的極值?！緞討B(tài)聚類方法】

C均值算法（k均值，C-meansork-means）ISODATA方法常用算法：第21頁，共60頁，2023年，2月20日，星期一221.

準則函數(shù)—誤差平方和準則

這個準則函數(shù)是以計算各類均值，與計算各類樣本到其所屬類別均值點誤差平方和為準則。

反映了用c個聚類中心代表c個樣本子集所帶來的總的誤差平方和。

目標:

最小化Je，即類內元素相似性高，類間元素相似性低，實現(xiàn)最小方差劃分。【C均值算法】第22頁，共60頁，2023年，2月20日，星期一232.樣本集初始劃分初始劃分的一般作法是先選擇一些代表點作為聚類的核心，然后把其余的樣本按某種方法分到各類中去。代表點的幾種選擇方法：憑經驗選擇代表點。根據問題的性質，用經驗的辦法確定類別數(shù)，從數(shù)據中找出從直觀上看來是比較合適的代表點。將全部數(shù)據隨機地分為C類，計算各類重心，將這些重心作為每類的代表點?！綜均值算法】第23頁，共60頁，2023年，2月20日，星期一24“密度”法選擇代表點。這里的“密度”是具有統(tǒng)計性質的樣本密度。一種求法是對每個樣本確定大小相等的鄰域(如同樣半徑的超球體)，統(tǒng)計落在其鄰域的樣本數(shù)，稱為該點“密度”。在得到樣本“密度”后，選“密度”為最大的樣本點作為第一個代表點，然后人為規(guī)定距該代表點一定距離外的區(qū)域內找次高“密度”的樣本點作為第二個代表點，依次選擇其它代表點，使用這種方法的目的是避免代表點過分集中在一起。用前c個樣本點作為代表點．【C均值算法】第24頁，共60頁，2023年，2月20日，星期一25從(c-1)聚類劃分問題的解中產生C聚類劃分問題的代表點。其具體做法：對樣本集首先看作一個聚類，計算其總均值，然后找與該均值相距最遠的點，由該點及原均值點構成兩聚類的代表點。依同樣方法，對已有(c-1)個聚類代表點(由(c-1)個類均值點組成)找一樣本點，使該樣本點距所有這些均值點的最小距離為最大，這樣就得到了第c個代表點?！綜均值算法】第25頁，共60頁，2023年，2月20日，星期一26【動態(tài)聚類】C均值算法初始分類方法：1.最近距離法。離哪個代表點近就歸入哪一類。2.最近距離法歸類，但每次都重新計算該類代表點。3.直接劃分初始分類：每一個樣本自成一類，第二個樣本若離它小于某距離閾值則歸入此類，否則建新類，……4.將特征歸一化，用樣本各特征之和作為初始分類依據。說明：初始劃分無一定之規(guī)，多為啟發(fā)式方法。C均值方法結果受初值影響，是局部最優(yōu)解。第26頁，共60頁，2023年，2月20日，星期一27【動態(tài)聚類】C均值算法第27頁，共60頁，2023年，2月20日，星期一28【動態(tài)聚類】C均值算法第28頁，共60頁，2023年，2月20日，星期一29【動態(tài)聚類】C均值算法第29頁，共60頁，2023年，2月20日，星期一30【動態(tài)聚類】C均值聚類方法用于非監(jiān)督模式識別的問題：1.要求類別數(shù)已知；2.是最小方差劃分，并不一定能反映內在分布；3.與初始劃分有關，不保證全局最優(yōu)。C均值算法第30頁，共60頁，2023年，2月20日，星期一31在類別數(shù)未知情況下使用C—均值算法時，可以假設類別數(shù)是逐步增加的，例如對c＝1，2，3，…分別使用該算法。準則函數(shù)是隨c的增加而單調地減少的。如果樣本集的合理聚類數(shù)為c類，當類別數(shù)繼續(xù)增大時，相當于將聚類很好的類別又分成子類，則值雖然繼續(xù)減少但會呈現(xiàn)平緩趨勢，如果作一條值隨c變化的曲線，則其拐點對應的類別數(shù)就比較接近于最優(yōu)聚類數(shù)?！綜均值算法-類別數(shù)未知】第31頁，共60頁，2023年，2月20日，星期一32但是并非所有的情況都能找到明顯的轉折點。在無明顯的轉折點時，這種選擇最佳分類數(shù)的方法將失效。一般需要利用先驗知識對不同的聚類結果進行分析比較。

【C均值算法-類別數(shù)未知】第32頁，共60頁，2023年，2月20日，星期一33C均值算法比較簡單，但它的自我調整能力也比較差。這主要表現(xiàn)在類別數(shù)必須事先確定，不能改變，這種主觀確定數(shù)據子集數(shù)目并不一定符合數(shù)據集自身的特點，受代表點初始選擇的影響也比較大。類似于C

均值算法，ISODATA算法的聚類中心也是通過樣本均值的迭代運算來決定。與C均值算法不同的是，ISODATA算法將硬性確定聚類數(shù)目改成給出這個數(shù)目的期望值，作為算法的一個控制量。在算法中又加上分裂與合并機制，增加了一些試探性步驟和人機交互的“自組織”處理方式，因而能使聚類結果比較適應數(shù)據集的內在特性。ISODATA算法與C

均值算法相比，在下列幾方面有改進。1.考慮了類別的合并與分裂，因而有了自我調整類別數(shù)的能力。

合并主要發(fā)生在某一類內樣本個數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。

【迭代自組織的數(shù)據分析算法-ISODATA】第33頁，共60頁，2023年，2月20日，星期一34

分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內方差過大的現(xiàn)象，因而宜分裂成兩個類別，以維持合理的類內方差。給出一個對類內分量方差的限制參數(shù)，用以決定是否需要將某一類分裂成兩類。2.由于算法有自我調整的能力，因而需要設置若干個控制用參數(shù)。

迭代自組織算法流程圖如圖5-7所示?！镜越M織的數(shù)據分析算法-ISODATA】第34頁，共60頁，2023年，2月20日，星期一35ISODATA算法的具體步驟如下：【迭代自組織的數(shù)據分析算法-ISODATA】第35頁，共60頁，2023年，2月20日，星期一36【迭代自組織的數(shù)據分析算法-ISODATA】第36頁，共60頁，2023年，2月20日，星期一37【迭代自組織的數(shù)據分析算法-ISODATA】第37頁，共60頁，2023年，2月20日，星期一38【迭代自組織的數(shù)據分析算法-ISODATA】第38頁，共60頁，2023年，2月20日，星期一39【迭代自組織的數(shù)據分析算法-ISODATA】第39頁，共60頁，2023年，2月20日，星期一40步驟9(求每類具有最大標準偏差的分量)步驟10(分裂計算步驟)【迭代自組織的數(shù)據分析算法-ISODATA】第40頁，共60頁，2023年，2月20日，星期一41合并處理：

步驟11(計算全部聚類中心之間的距離)

【迭代自組織的數(shù)據分析算法-ISODATA】第41頁，共60頁，2023年，2月20日，星期一42步驟12(列出類間距離過近者)

步驟13(執(zhí)行合并)

【迭代自組織的數(shù)據分析算法-ISODATA】第42頁，共60頁，2023年，2月20日，星期一43步驟14(結束步驟)

如果迭代運算次數(shù)已達最大的迭代次數(shù)I，即是最后一次迭代，則算法結束；否則，如果需要由操作者改變輸入參數(shù)，轉入步驟1，設計相應的參數(shù)；否則，轉入步驟2。到了本步運算，迭代運算的次數(shù)加1。以上是整個ISODATA算法的計算步驟?？梢钥闯鯥SODATA算法與C

均值算法一樣，都是以與代表點的最小距離作為樣本聚類的依據，因此比較適合各類物體在特征空間以超球體分布的方式分布，對于分布形狀較復雜的情況需要采用別的度量。ISODATA算法與C均值算法的主要不同在于自我控制與調整的能力不同?！镜越M織的數(shù)據分析算法-ISODATA】第43頁，共60頁，2023年，2月20日，星期一44ISODATA算法流程圖【迭代自組織的數(shù)據分析算法-ISODATA】第44頁，共60頁，2023年，2月20日，星期一45【基于樣本和核的相似性度量的動態(tài)聚類算法】第45頁，共60頁，2023年，2月20日，星期一46【基于樣本和核的相似性度量的動態(tài)聚類算法】第46頁，共60頁，2023年，2月20日，星期一47【基于樣本和核的相似性度量的動態(tài)聚類算法】第47頁，共60頁，2023年，2月20日，星期一48【近鄰函數(shù)準則算法】定義第48頁，共60頁，2023年，2月20日，星期一第七章非監(jiān)督學習方法49【近鄰函數(shù)準則算法】

第i類和第j類間最小近鄰函數(shù)值定義為：相似性分析第i類內最大連接損失記為：aimax第i類與第j類之間的連接損失定義為bij，它的設計目標是：如果兩類間的最小近鄰值大于任何一方的類內的最大連接損失時，損失代價就是正的，從而應該考慮把這兩類合并第49頁，共60頁，2023年，2月20日，星期一第七章非監(jiān)督學習方法50【近鄰函數(shù)準則算法】

總類間損失：相似性分析準則函數(shù)：算法步驟：計算距離矩陣用距離矩陣計算近鄰矩陣計算近鄰函數(shù)矩陣在L中，每個點與其最近鄰連接，形成初始的劃分對每兩個類計算rij

和aimax，ajmax

，只要rij

小于aimax、ajmax中的任何一個，就合并兩類（建立連接）。重復至沒有新的連接發(fā)生為止第50頁，共60頁，2023年，2月20日，星期一514.分級聚類方法（HierachicalClustering）第51頁，共60頁，2023年，2月20日，星期一52分級聚類方法的目的并不把N個樣本分成某一個預定的類別數(shù)C，而是把樣本集按不同的相似程度要求分成不同類別的聚類。最極端的情況是每個樣本各自為一類，N個樣本共有N類，沒有任何聚類，另一極端則是將所有樣本歸一類。在這兩個極端之間的是類別數(shù)從N逐漸減少，每類的數(shù)量相應增加，而類內樣本的相似程度要求也隨之下降。這種聚類就是分級聚類，它可以用一樹形結構表示?！痉旨壘垲惙椒?-類別數(shù)未知

】第52頁，共60頁，2023年，2月20日，星期一53這是一棵具有6個樣本的分類樹。圖中左邊表示分級層次，第一層次各樣本自成一類，其類內相似度自然是百分之百，在第二層次y3與y5合成一類，第三層次y1與y4也合并成一類，依次下去。一經合并成一類的樣本不再分裂，類別數(shù)也隨之逐漸減少，類內相似程度逐漸降低。這種聚類方法在科學技術領域中得到了廣泛的應用，如生物分類就是分級聚類應用的一個例子?！痉旨壘垲悩浔硎痉椒?/p>

】第53頁，共60頁，2023年，2月20日，星期一54【分級聚類方法

】思想：從各類只有一個樣本點開始，逐級合并，每級只合并兩類，直到最后所有樣本都歸到一類。Hierarchicaltree--dendrogram聚類過程中逐級考查類間相似度，依此決定類別數(shù)第54頁，共60頁，2023年，2月20日，星期一55算法（從底向上）：（1）初始化，每個樣本形成一類（2）把相似性最大（距離最?。┑膬深惡喜ⅲ?）重復（2），直到所有樣本合并為兩類?！痉旨壘垲惙椒?/p>

】第55頁，共60頁，2023年，2月20日，星期一56【分級聚類方法

】劃分序列：N個樣本自底向上逐