模式識(shí)別非監(jiān)督學(xué)習(xí)方法

1、模式識(shí)別非監(jiān)督學(xué)習(xí)方法第1頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四2主要內(nèi)容1.引言2. 單峰子集（類）的分離方法3. 類別分離的間接方法4. 分級(jí)聚類方法第2頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四31.引言第3頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四4引言有監(jiān)督學(xué)習(xí)（supervised learning)： 分類器設(shè)計(jì)方法是在樣本集中的類別標(biāo)簽已知的條件下進(jìn)行的，這些樣本稱為訓(xùn)練樣本。在樣本標(biāo)簽已知的情況下，可以統(tǒng)計(jì)出各類訓(xùn)練樣本不同的描述量，如其概率分布，或在特征空間分布的區(qū)域等，利用這些參數(shù)進(jìn)行分類器設(shè)計(jì)。用已知類別的樣本訓(xùn)練分類

2、器，以求對(duì)訓(xùn)練集的數(shù)據(jù)達(dá)到某種最優(yōu)，并能推廣到對(duì)新數(shù)據(jù)的分類。第4頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四5無(wú)監(jiān)督學(xué)習(xí)（unsupervised learning) ： 樣本數(shù)據(jù)類別未知，需要根據(jù)樣本間的相似性對(duì)樣本集進(jìn)行分類(聚類，clustering)，試圖使類內(nèi)差距最小化，類間差距最大化。利用聚類結(jié)果，可以提取數(shù)據(jù)集中隱藏的信息，對(duì)未來(lái)數(shù)據(jù)進(jìn)行預(yù)測(cè)和分類。應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別、圖像處理、經(jīng)濟(jì)學(xué)引言第5頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四6廣泛的應(yīng)用領(lǐng)域商務(wù)：幫助市場(chǎng)分析人員從客戶信息庫(kù)中發(fā)現(xiàn)不同的客戶群，用購(gòu)買模式來(lái)刻畫不同的客戶群的特征土地使

3、用：在地球觀測(cè)數(shù)據(jù)庫(kù)中識(shí)別土地使用情況相似的地區(qū)保險(xiǎn)業(yè)：汽車保險(xiǎn)單持有者的分組，標(biāo)識(shí)那些有較高平均賠償成本的客戶。城市規(guī)劃：根據(jù)房子的類型，價(jià)值和地理分布對(duì)房子分組生物學(xué)：推導(dǎo)植物和動(dòng)物的分類，對(duì)基因進(jìn)行分類地震研究: 根據(jù)地質(zhì)斷層的特點(diǎn)把已觀察到的地震中心分成不同的類。第6頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四7有監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的區(qū)別有監(jiān)督學(xué)習(xí)方法必須要有訓(xùn)練集與測(cè)試樣本。在訓(xùn)練集中找規(guī)律，而對(duì)測(cè)試樣本使用這種規(guī)律；而非監(jiān)督學(xué)習(xí)沒有訓(xùn)練集這一說，只有一組數(shù)據(jù)，在該組數(shù)據(jù)集內(nèi)尋找規(guī)律。有監(jiān)督學(xué)習(xí)方法的目的就是識(shí)別事物，識(shí)別的結(jié)果表現(xiàn)在給待識(shí)別數(shù)據(jù)加上了標(biāo)號(hào)。因此訓(xùn)練樣

4、本集必須由帶標(biāo)號(hào)的樣本組成。而非監(jiān)督學(xué)習(xí)方法只有要分析的數(shù)據(jù)集本身，預(yù)先沒有什么標(biāo)號(hào)。如果發(fā)現(xiàn)數(shù)據(jù)集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預(yù)先的分類標(biāo)號(hào)對(duì)上號(hào)為目的。第7頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四8無(wú)監(jiān)督學(xué)習(xí)方法在尋找數(shù)據(jù)集中的規(guī)律性，這種規(guī)律性并不一定要達(dá)到劃分?jǐn)?shù)據(jù)集的目的，也就是說不一定要“分類”。這一點(diǎn)是比有監(jiān)督學(xué)習(xí)方法的用途要廣泛。譬如分析一堆數(shù)據(jù)的主分量，或分析數(shù)據(jù)集有什么特點(diǎn)都可以歸于無(wú)監(jiān)督學(xué)習(xí)方法的范疇。 用無(wú)監(jiān)督學(xué)習(xí)方法分析數(shù)據(jù)集的主分量與用K-L變換計(jì)算數(shù)據(jù)集的主分量又有區(qū)別。應(yīng)該說后者從方法上講不是一種學(xué)習(xí)方法。因此用K-L變換

5、找主分量不屬于無(wú)監(jiān)督學(xué)習(xí)方法，即方法上不是。而通過學(xué)習(xí)逐漸找到規(guī)律性這體現(xiàn)了學(xué)習(xí)方法這一點(diǎn)。在人工神經(jīng)元網(wǎng)絡(luò)中尋找主分量的方法屬于無(wú)監(jiān)督學(xué)習(xí)方法。有監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的區(qū)別第8頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四9無(wú)監(jiān)督學(xué)習(xí)方法的分類基于概率密度函數(shù)估計(jì)的方法：指設(shè)法找到各類別在特征空間的分布參數(shù)再進(jìn)行分類。基于樣本間相似性度量的方法：直接按樣本間的相似性，或彼此間在特征空間中的距離長(zhǎng)短進(jìn)行分類。其原理是設(shè)法定出不同類別的核心，然后依據(jù)樣本與這些核心之間的相似性度量，將樣本聚集成不同類別。如何聚類則取決于聚類的準(zhǔn)則函數(shù)，以使某種聚類準(zhǔn)則達(dá)到極值為最佳。兩種聚類方法： 迭

6、代的動(dòng)態(tài)聚類方法和非迭代的分級(jí)聚類方法 第9頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四102. 單峰子集（類）的分離方法第10頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四11思想：把特征空間分為若干個(gè)區(qū)域，在每個(gè)區(qū)域上混合概率密度函數(shù)是單峰的，每個(gè)單峰區(qū)域?qū)?yīng)一個(gè)類別?！净舅枷搿康?1頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四12直接方法一維空間中的單峰分離: 對(duì)樣本集KN=xi應(yīng)用直方圖/Parzen窗方法估計(jì)概率密度函數(shù)，找到概率密度函數(shù)的峰以及峰之間的谷底，以谷底為閾值對(duì)數(shù)據(jù)進(jìn)行分割?！疽痪S空間中的單峰子集分離】第12頁(yè)，共60頁(yè)，2022

7、年，5月20日，23點(diǎn)34分，星期四13【多維空間投影方法】基本思路： 多維空間中直接劃分成單峰區(qū)域比較困難，而一維空間中則比較簡(jiǎn)單。 尋找一個(gè)坐標(biāo)系統(tǒng)，在該系統(tǒng)下，數(shù)據(jù)的混合概率密度函數(shù)可以用邊緣概率密度表示。 如果某邊緣概率密度函數(shù)呈現(xiàn)多峰形式，則在此坐標(biāo)軸上（一維）作分割。做法：把樣本投影到某一一維坐標(biāo)軸（按某種準(zhǔn)則），在這一維上求樣本的概率密度（邊緣概率密度），根據(jù)這一概率密度函數(shù)的單峰劃分子集。 （如果這一維上只有一個(gè)峰，則尋找下一個(gè)投影方向。）投影方向：使方差最大的方向，即協(xié)方差陣本征值最大的本征向量方向。 第13頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四14【投影

8、方法】基本步驟 第14頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四15問題：這樣投影有時(shí)并不能產(chǎn)生多峰的邊緣密度函數(shù) -方差最大的準(zhǔn)則有時(shí)并不一定最有利于聚類?！敬嬖趩栴}】失敗的例子第15頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四163. 類別分離的間接方法第16頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四17【引言】回顧：直接方法：1. 估計(jì)概率密度函數(shù) 困難2. 尋找密度函數(shù)中的單峰間接方法：考查樣本這間的相似性，根據(jù)相似性把樣本集劃分為若干子集，使某種表示聚類質(zhì)量的準(zhǔn)則函數(shù)最優(yōu)。第17頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四1

9、8【引言】相似性度量：以某種距離定義直觀理解：同一類的樣本的特征向量應(yīng)是相互靠近的。前提：特征選取合理，能反映所求的聚類關(guān)系。與基于密度函數(shù)的方法的關(guān)系： 概念上相互關(guān)聯(lián)，因密度估計(jì)也是在樣本間距離的基礎(chǔ)上的。 具體關(guān)系取決于具體數(shù)據(jù)情況。第18頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四19動(dòng)態(tài)聚類方法的任務(wù)： 將數(shù)據(jù)集劃分成一定數(shù)量的子集，例如將一個(gè)數(shù)據(jù)集劃分成三個(gè)子集，四個(gè)子集等。因此要?jiǎng)澐殖啥嗌賯€(gè)子集往往要預(yù)先確定，或大致確定，這個(gè)子集數(shù)目在理想情況下能夠體現(xiàn)數(shù)據(jù)集比較合理的劃分。 需要解決的問題： 怎樣才能知道該數(shù)據(jù)集應(yīng)該劃分的子集數(shù)目 如果劃分?jǐn)?shù)目已定，則又如何找到最

10、佳劃分。因?yàn)閿?shù)據(jù)集可以有許多種不同的劃分方法，需要對(duì)不同的劃分作出評(píng)價(jià)，并找到優(yōu)化的劃分結(jié)果。由于優(yōu)化過程是從不甚合理的劃分到“最佳”劃分，是一個(gè)動(dòng)態(tài)的迭代過程，故這種方法稱為動(dòng)態(tài)聚類方法?！緞?dòng)態(tài)聚類方法】第19頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四20對(duì)計(jì)算機(jī)來(lái)說，所確定的初始代表點(diǎn)很可能不甚合理，以至于影響到聚類的結(jié)果。這就需要有一個(gè)對(duì)聚類的結(jié)果進(jìn)行修改或迭代的過程，使聚類結(jié)果逐步趨向合理。迭代的過程需要一個(gè)準(zhǔn)則函數(shù)來(lái)指導(dǎo)，使迭代朝實(shí)現(xiàn)準(zhǔn)則函數(shù)的極值化方向收斂。 聚類過程：從確定各聚類的代表點(diǎn)開始（比如，確定三個(gè)質(zhì)心點(diǎn) ） 按各樣本到三個(gè)質(zhì)心最短距離將樣本分到該類【動(dòng)態(tài)

11、聚類方法】第20頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四21三個(gè)要點(diǎn)選定某種距離度量作為樣本間的相似性度量； 確定樣本合理的初始分類，包括代表點(diǎn)的選擇，初始分類的方法選擇等；確定某種評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，用以調(diào)整初始分類直至達(dá)到該準(zhǔn)則函數(shù)的極值。【動(dòng)態(tài)聚類方法】 C 均值算法（ k 均值，C-means or k-means）ISODATA 方法常用算法：第21頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四221. 準(zhǔn)則函數(shù)誤差平方和準(zhǔn)則 這個(gè)準(zhǔn)則函數(shù)是以計(jì)算各類均值 ，與計(jì)算各類樣本到其所屬類別均值點(diǎn)誤差平方和為準(zhǔn)則。 反映了用c個(gè)聚類中心代表c個(gè)樣本子集

12、所帶來(lái)的總的誤差平方和。 目標(biāo): 最小化Je，即類內(nèi)元素相似性高，類間元素相似性低，實(shí)現(xiàn)最小方差劃分?！綜均值算法】第22頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四232.樣本集初始劃分初始劃分的一般作法是先選擇一些代表點(diǎn)作為聚類的核心，然后把其余的樣本按某種方法分到各類中去。 代表點(diǎn)的幾種選擇方法：憑經(jīng)驗(yàn)選擇代表點(diǎn)。根據(jù)問題的性質(zhì)，用經(jīng)驗(yàn)的辦法確定類別數(shù)，從數(shù)據(jù)中找出從直觀上看來(lái)是比較合適的代表點(diǎn)。將全部數(shù)據(jù)隨機(jī)地分為C類，計(jì)算各類重心，將這些重心作為每類的代表點(diǎn)?！綜均值算法】第23頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四24“密度”法選擇代表點(diǎn)。這里的“

13、密度”是具有統(tǒng)計(jì)性質(zhì)的樣本密度。一種求法是對(duì)每個(gè)樣本確定大小相等的鄰域(如同樣半徑的超球體)，統(tǒng)計(jì)落在其鄰域的樣本數(shù)，稱為該點(diǎn)“密度”。在得到樣本“密度”后，選“密度”為最大的樣本點(diǎn)作為第一個(gè)代表點(diǎn)，然后人為規(guī)定距該代表點(diǎn)一定距離外的區(qū)域內(nèi)找次高“密度”的樣本點(diǎn)作為第二個(gè)代表點(diǎn)，依次選擇其它代表點(diǎn)，使用這種方法的目的是避免代表點(diǎn)過分集中在一起。用前c個(gè)樣本點(diǎn)作為代表點(diǎn)【C均值算法】第24頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四25從(c-1)聚類劃分問題的解中產(chǎn)生C聚類劃分問題的代表點(diǎn)。其具體做法：對(duì)樣本集首先看作一個(gè)聚類，計(jì)算其總均值，然后找與該均值相距最遠(yuǎn)的點(diǎn)，由該點(diǎn)及原

14、均值點(diǎn)構(gòu)成兩聚類的代表點(diǎn)。依同樣方法，對(duì)已有(c-1)個(gè)聚類代表點(diǎn)(由(c-1)個(gè)類均值點(diǎn)組成)找一樣本點(diǎn)，使該樣本點(diǎn)距所有這些均值點(diǎn)的最小距離為最大，這樣就得到了第c個(gè)代表點(diǎn)?！綜均值算法】第25頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四26【動(dòng)態(tài)聚類】C 均值算法初始分類方法：1. 最近距離法。離哪個(gè)代表點(diǎn)近就歸入哪一類。2. 最近距離法歸類，但每次都重新計(jì)算該類代表點(diǎn)。3. 直接劃分初始分類：每一個(gè)樣本自成一類，第二個(gè)樣本若離它小于某距離閾值則歸入此類，否則建新類，4. 將特征歸一化，用樣本各特征之和作為初始分類依據(jù)。說明： 初始劃分無(wú)一定之規(guī)，多為啟發(fā)式方法。 C 均值

15、方法結(jié)果受初值影響，是局部最優(yōu)解。第26頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四27【動(dòng)態(tài)聚類】C 均值算法第27頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四28【動(dòng)態(tài)聚類】C 均值算法第28頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四29【動(dòng)態(tài)聚類】C 均值算法第29頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四30【動(dòng)態(tài)聚類】C 均值聚類方法用于非監(jiān)督模式識(shí)別的問題：1. 要求類別數(shù)已知；2. 是最小方差劃分，并不一定能反映內(nèi)在分布；3. 與初始劃分有關(guān)，不保證全局最優(yōu)。C 均值算法第30頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)

16、34分，星期四31在類別數(shù)未知情況下使用C均值算法時(shí)，可以假設(shè)類別數(shù)是逐步增加的，例如對(duì)c1，2，3，分別使用該算法。準(zhǔn)則函數(shù) 是隨c的增加而單調(diào)地減少的。如果樣本集的合理聚類數(shù)為c類，當(dāng)類別數(shù)繼續(xù)增大時(shí)，相當(dāng)于將聚類很好的類別又分成子類，則 值雖然繼續(xù)減少但會(huì)呈現(xiàn)平緩趨勢(shì)，如果作一條 值隨c變化的曲線，則其拐點(diǎn)對(duì)應(yīng)的類別數(shù)就比較接近于最優(yōu)聚類數(shù)?！綜均值算法-類別數(shù)未知】第31頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四32但是并非所有的情況都能找到明顯的轉(zhuǎn)折點(diǎn)。在無(wú)明顯的轉(zhuǎn)折點(diǎn)時(shí)，這種選擇最佳分類數(shù)的方法將失效。一般需要利用先驗(yàn)知識(shí)對(duì)不同的聚類結(jié)果進(jìn)行分析比較。 【C均值算法

17、-類別數(shù)未知】第32頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四33C 均值算法比較簡(jiǎn)單，但它的自我調(diào)整能力也比較差。這主要表現(xiàn)在類別數(shù)必須事先確定，不能改變，這種主觀確定數(shù)據(jù)子集數(shù)目并不一定符合數(shù)據(jù)集自身的特點(diǎn)，受代表點(diǎn)初始選擇的影響也比較大。類似于C 均值算法，ISODATA算法的聚類中心也是通過樣本均值的迭代運(yùn)算來(lái)決定。與C均值算法不同的是， ISODATA算法 將硬性確定聚類數(shù)目改成給出這個(gè)數(shù)目的期望值，作為算法的一個(gè)控制量。在算法中又加上分裂與合并機(jī)制，增加了一些試探性步驟和人機(jī)交互的“自組織”處理方式，因而能使聚類結(jié)果比較適應(yīng)數(shù)據(jù)集的內(nèi)在特性。ISODATA算法與C

18、均值算法相比，在下列幾方面有改進(jìn)。1.考慮了類別的合并與分裂，因而有了自我調(diào)整類別數(shù)的能力。 合并主要發(fā)生在某一類內(nèi)樣本個(gè)數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。 【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第33頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四34 分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內(nèi)方差過大的現(xiàn)象，因而宜分裂成兩個(gè)類別，以維持合理的類內(nèi)方差。給出一個(gè)對(duì)類內(nèi)分量方差的限制參數(shù) ，用以決定是否需要將某一類分裂成兩類。2.由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個(gè)控 制用參數(shù)。 迭代自組織算法流程圖如圖5-7所示?！镜越M織的數(shù)據(jù)分析算法-ISODATA

19、】第34頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四35ISODATA算法的具體步驟如下：【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第35頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四36【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第36頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四37【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第37頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四38【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第38頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四39【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第3

20、9頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四40步驟9(求每類具有最大標(biāo)準(zhǔn)偏差的分量)步驟10(分裂計(jì)算步驟)【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第40頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四41合并處理：步驟11(計(jì)算全部聚類中心之間的距離)【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第41頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四42步驟12(列出類間距離過近者)步驟13(執(zhí)行合并)【迭代自組織的數(shù)據(jù)分析算法-ISODATA】第42頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四43步驟14(結(jié)束步驟) 如果迭代運(yùn)算次數(shù)已

21、達(dá)最大的迭代次數(shù)I，即是最后一次迭代，則算法結(jié)束；否則，如果需要由操作者改變輸入?yún)?shù)，轉(zhuǎn)入步驟1，設(shè)計(jì)相應(yīng)的參數(shù)；否則，轉(zhuǎn)入步驟2。到了本步運(yùn)算，迭代運(yùn)算的次數(shù)加1。以上是整個(gè)ISODATA算法的計(jì)算步驟?？梢钥闯鯥SODATA算法與C 均值算法一樣，都是以與代表點(diǎn)的最小距離作為樣本聚類的依據(jù)，因此比較適合各類物體在特征空間以超球體分布的方式分布，對(duì)于分布形狀較復(fù)雜的情況需要采用別的度量。ISODATA算法與C均值算法的主要不同在于自我控制與調(diào)整的能力不同?！镜越M織的數(shù)據(jù)分析算法-ISODATA】第43頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四44ISODATA算法流程圖【

22、迭代自組織的數(shù)據(jù)分析算法-ISODATA】第44頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四45【基于樣本和核的相似性度量的動(dòng)態(tài)聚類算法】第45頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四46【基于樣本和核的相似性度量的動(dòng)態(tài)聚類算法】第46頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四47【基于樣本和核的相似性度量的動(dòng)態(tài)聚類算法】第47頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四48【近鄰函數(shù)準(zhǔn)則算法】定義第48頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四第七章 非監(jiān)督學(xué)習(xí)方法49【近鄰函數(shù)準(zhǔn)則算法】第i類和第j類間最小近鄰函

23、數(shù)值定義為：相似性分析第i類內(nèi)最大連接損失記為： aimax第i類與第j類之間的連接損失定義為bij，它的設(shè)計(jì)目標(biāo)是：如果兩類間的最小近鄰值大于任何一方的類內(nèi)的最大連接損失時(shí)，損失代價(jià)就是正的，從而應(yīng)該考慮把這兩類合并第49頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四第七章 非監(jiān)督學(xué)習(xí)方法50【近鄰函數(shù)準(zhǔn)則算法】總類間損失：相似性分析準(zhǔn)則函數(shù)：算法步驟：計(jì)算距離矩陣用距離矩陣計(jì)算近鄰矩陣計(jì)算近鄰函數(shù)矩陣在L 中，每個(gè)點(diǎn)與其最近鄰連接，形成初始的劃分對(duì)每?jī)蓚€(gè)類計(jì)算rij 和aimax，ajmax ，只要rij 小于aimax、ajmax中的任何一個(gè)，就合并兩類（建立連接）。重復(fù)至沒

24、有新的連接發(fā)生為止第50頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四514. 分級(jí)聚類方法（Hierachical Clustering）第51頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四52分級(jí)聚類方法的目的并不把N個(gè)樣本分成某一個(gè)預(yù)定的類別數(shù)C，而是把樣本集按不同的相似程度要求分成不同類別的聚類。最極端的情況是每個(gè)樣本各自為一類，N個(gè)樣本共有N類，沒有任何聚類，另一極端則是將所有樣本歸一類。在這兩個(gè)極端之間的是類別數(shù)從N逐漸減少，每類的數(shù)量相應(yīng)增加，而類內(nèi)樣本的相似程度要求也隨之下降。 這種聚類就是分級(jí)聚類，它可以用一樹形結(jié)構(gòu)表示。 【分級(jí)聚類方法-類別數(shù)未知

25、】第52頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四53這是一棵具有6個(gè)樣本的分類樹。圖中左邊表示分級(jí)層次，第一層次各樣本自成一類，其類內(nèi)相似度自然是百分之百，在第二層次y3與y5合成一類，第三層次y1與y4也合并成一類，依次下去。一經(jīng)合并成一類的樣本不再分裂，類別數(shù)也隨之逐漸減少，類內(nèi)相似程度逐漸降低。這種聚類方法在科學(xué)技術(shù)領(lǐng)域中得到了廣泛的應(yīng)用，如生物分類就是分級(jí)聚類應(yīng)用的一個(gè)例子。 【分級(jí)聚類樹表示方法 】第53頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四54【分級(jí)聚類方法 】 思想：從各類只有一個(gè)樣本點(diǎn)開始，逐級(jí)合并，每級(jí)只合并兩類，直到最后所有樣本都?xì)w到一類。Hierarchical tree - dendrogram聚類過程中逐級(jí)考查類間相似度，依此決定類別數(shù)第54頁(yè)，共60頁(yè)，2022年，5月20日，23點(diǎn)34分，星期四55算法（從底向上）：（1）初始化，每個(gè)樣本形成一類（2）把相似性最大（距離最小）的兩類合并（3）重復(fù)（2），直到所有樣本合并為兩類?！痉旨?jí)聚