哈工大模式識(shí)別課程10.非監(jiān)督學(xué)習(xí)市公開課一等獎(jiǎng)省賽課微課金獎(jiǎng)

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

依據(jù)地質(zhì)斷層特點(diǎn)把已觀察到地震中心分成不一樣類。5第5頁(yè)有監(jiān)督學(xué)習(xí)與無監(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í)方法目標(biāo)就是識(shí)別事物，識(shí)別結(jié)果表現(xiàn)在給待識(shí)別數(shù)據(jù)加上了標(biāo)號(hào)。所以訓(xùn)練樣本集必須由帶標(biāo)號(hào)樣本組成。而非監(jiān)督學(xué)習(xí)方法只有要分析數(shù)據(jù)集本身，預(yù)先沒有什么標(biāo)號(hào)。假如發(fā)覺數(shù)據(jù)集展現(xiàn)某種聚集性，則可按自然聚集性分類，但不以與某種預(yù)先分類標(biāo)號(hào)對(duì)上號(hào)為目標(biāo)。6第6頁(yè)無監(jiān)督學(xué)習(xí)方法在尋找數(shù)據(jù)集中規(guī)律性，這種規(guī)律性并不一定要到達(dá)劃分?jǐn)?shù)據(jù)集目標(biāo)，也就是說不一定要“分類”。這一點(diǎn)是比有監(jiān)督學(xué)習(xí)方法用途要廣泛。譬如分析一堆數(shù)據(jù)主分量，或分析數(shù)據(jù)集有什么特點(diǎn)都能夠歸于無監(jiān)督學(xué)習(xí)方法范圍。用無監(jiān)督學(xué)習(xí)方法分析數(shù)據(jù)集主分量與用K-L變換計(jì)算數(shù)據(jù)集主分量又有區(qū)分。應(yīng)該說后者從方法上講不是一個(gè)學(xué)習(xí)方法。所以用K-L變換找主分量不屬于無監(jiān)督學(xué)習(xí)方法，即方法上不是。而經(jīng)過學(xué)習(xí)逐步找到規(guī)律性這表達(dá)了學(xué)習(xí)方法這一點(diǎn)。在人工神經(jīng)元網(wǎng)絡(luò)中尋找主分量方法屬于無監(jiān)督學(xué)習(xí)方法。有監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)區(qū)分7第7頁(yè)無監(jiān)督學(xué)習(xí)方法分類基于概率密度函數(shù)預(yù)計(jì)方法：指設(shè)法找到各類別在特征空間分布參數(shù)再進(jìn)行分類?；跇颖鹃g相同性度量方法：直接按樣本間相同性，或彼此間在特征空間中距離長(zhǎng)短進(jìn)行分類。其原理是設(shè)法定出不一樣類別關(guān)鍵，然后依據(jù)樣本與這些關(guān)鍵之間相同性度量，將樣本聚集成不一樣類別。怎樣聚類則取決于聚類準(zhǔn)則函數(shù)，以使某種聚類準(zhǔn)則到達(dá)極值為最正確。兩種聚類方法：

迭代動(dòng)態(tài)聚類方法和非迭代分級(jí)聚類方法

8第8頁(yè)2.單峰子集（類）分離方法9第9頁(yè)思想：把特征空間分為若干個(gè)區(qū)域，在每個(gè)區(qū)域上混合概率密度函數(shù)是單峰，每個(gè)單峰區(qū)域?qū)?yīng)一個(gè)類別?！净舅枷搿?0第10頁(yè)直接

方法一維空間中單峰分離:對(duì)樣本集KN={xi}應(yīng)用直方圖/Parzen窗方法預(yù)計(jì)概率密度函數(shù)，找到概率密度函數(shù)峰以及峰之間谷底，以谷底為閾值對(duì)數(shù)據(jù)進(jìn)行分割?！疽痪S空間中單峰子集分離】11第11頁(yè)【多維空間投影方法】基本思緒：多維空間中直接劃分成單峰區(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é)方差陣本征值最大本征向量方向。12第12頁(yè)【投影方法】基本步驟13第13頁(yè)【投影方法】直方圖法求概率密度函數(shù)：14第14頁(yè)問題：這么投影有時(shí)并不能產(chǎn)生多峰邊緣密度函數(shù)

-方差最大準(zhǔn)則有時(shí)并不一定最有利于聚類?！敬嬖趩栴}】失敗例子15第15頁(yè)【基于對(duì)稱集性質(zhì)單峰子集分離法】對(duì)稱集定義：16第16頁(yè)【基于對(duì)稱集性質(zhì)單峰子集分離法】基本步驟：17第17頁(yè)【基于對(duì)稱集性質(zhì)單峰子集分離法】基本步驟：18第18頁(yè)【單峰子集分離迭代算法】概念：19第19頁(yè)【單峰子集分離迭代算法】20第20頁(yè)【單峰子集分離迭代算法】目標(biāo)：步驟：21第21頁(yè)3.類別分離間接方法22第22頁(yè)【引言】回顧：直接方法：1.預(yù)計(jì)概率密度函數(shù)——困難2.尋找密度函數(shù)中單峰間接方法：考查樣本這間相同性，依據(jù)相同性把樣本集劃分為若干子集，使某種表示聚類質(zhì)量準(zhǔn)則函數(shù)最優(yōu)。不一樣聚類方法實(shí)際上反應(yīng)了對(duì)聚類不一樣了解：混合模型：數(shù)據(jù)服從混合分布，聚類對(duì)應(yīng)于各分布單峰子集：聚類即概率分布中單峰，即樣本分布相對(duì)集中區(qū)域間接方法：相同樣本聚類，不一樣聚類樣本不相同23第23頁(yè)【引言】相同性度量：以某種距離定義直觀了解：同一類樣本特征向量應(yīng)是相互靠近?！疤幔禾卣鬟x取合理，能反應(yīng)所求聚類關(guān)系。與基于密度函數(shù)方法關(guān)系：概念上相互關(guān)聯(lián)，因密度預(yù)計(jì)也是在樣本間距離基礎(chǔ)上。詳細(xì)關(guān)系取決于詳細(xì)數(shù)據(jù)情況。24第24頁(yè)動(dòng)態(tài)聚類方法任務(wù)：

將數(shù)據(jù)集劃分成一定數(shù)量子集，比如將一個(gè)數(shù)據(jù)集劃分成三個(gè)子集，四個(gè)子集等。所以要?jiǎng)澐殖啥嗌賯€(gè)子集往往要預(yù)先確定，或大致確定，這個(gè)子集數(shù)目在理想情況下能夠表達(dá)數(shù)據(jù)集比較合理劃分。需要處理問題：怎樣才能知道該數(shù)據(jù)集應(yīng)該劃分子集數(shù)目

假如劃分?jǐn)?shù)目已定，則又怎樣找到最正確劃分。因?yàn)閿?shù)據(jù)集能夠有許各種不一樣劃分方法，需要對(duì)不一樣劃分作出評(píng)價(jià)，并找到優(yōu)化劃分結(jié)果。因?yàn)閮?yōu)化過程是從不甚合理劃分到“最正確”劃分，是一個(gè)動(dòng)態(tài)迭代過程，故這種方法稱為動(dòng)態(tài)聚類方法。

【動(dòng)態(tài)聚類方法】25第25頁(yè)對(duì)計(jì)算機(jī)來說，所確定初始代表點(diǎn)很可能不甚合理，以至于影響到聚類結(jié)果。這就需要有一個(gè)對(duì)聚類結(jié)果進(jìn)行修改或迭代過程，使聚類結(jié)果逐步趨向合理。迭代過程需要一個(gè)準(zhǔn)則函數(shù)來指導(dǎo)，使迭代朝實(shí)現(xiàn)準(zhǔn)則函數(shù)極值化方向收斂。聚類過程：從確定各聚類代表點(diǎn)開始（比如，確定三個(gè)質(zhì)心點(diǎn)）按各樣本到三個(gè)質(zhì)心最短距離將樣本分到該類【動(dòng)態(tài)聚類方法】26第26頁(yè)三個(gè)關(guān)鍵點(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-meansork-means）ISODATA方法慣用算法：27第27頁(yè)1.

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

這個(gè)準(zhǔn)則函數(shù)是以計(jì)算各類均值，與計(jì)算各類樣本到其所屬類別均值點(diǎn)誤差平方和為準(zhǔn)則。

反應(yīng)了用c個(gè)聚類中心代表c個(gè)樣本子集所帶來總誤差平方和。

目標(biāo):

最小化Je，即類內(nèi)元素相同性高，類間元素相同性低，實(shí)現(xiàn)最小方差劃分?！綜均值算法】28第28頁(yè)2.樣本集初始劃分

初始劃分普通作法是先選擇一些代表點(diǎn)作為聚類關(guān)鍵，然后把其余樣本按某種方法分到各類中去。代表點(diǎn)幾個(gè)選擇方法：憑經(jīng)驗(yàn)選擇代表點(diǎn)。依據(jù)問題性質(zhì)，用經(jīng)驗(yàn)方法確定類別數(shù)，從數(shù)據(jù)中找出從直觀上看來是比較適當(dāng)代表點(diǎn)。將全部數(shù)據(jù)隨機(jī)地分為C類，計(jì)算各類重心，將這些重心作為每類代表點(diǎn)。【C均值算法】29第29頁(yè)“密度”法選擇代表點(diǎn)。這里“密度”是含有統(tǒng)計(jì)性質(zhì)樣本密度。一個(gè)求法是對(duì)每個(gè)樣本確定大小相等鄰域(如一樣半徑超球體)，統(tǒng)計(jì)落在其鄰域樣本數(shù)，稱為該點(diǎn)“密度”。在得到樣本“密度”后，選“密度”為最大樣本點(diǎn)作為第一個(gè)代表點(diǎn)，然后人為要求距該代表點(diǎn)一定距離外區(qū)域內(nèi)找次高“密度”樣本點(diǎn)作為第二個(gè)代表點(diǎn)，依次選擇其它代表點(diǎn)，使用這種方法目標(biāo)是防止代表點(diǎn)過分集中在一起。用前c個(gè)樣本點(diǎn)作為代表點(diǎn)．【C均值算法】30第30頁(yè)從(c-1)聚類劃分問題解中產(chǎn)生C聚類劃分問題代表點(diǎn)。其詳細(xì)做法：對(duì)樣本集首先看作一個(gè)聚類，計(jì)算其總均值，然后找與該均值相距最遠(yuǎn)點(diǎn)，由該點(diǎn)及原均值點(diǎn)組成兩聚類代表點(diǎn)。依一樣方法，對(duì)已經(jīng)有(c-1)個(gè)聚類代表點(diǎn)(由(c-1)個(gè)類均值點(diǎn)組成)找一樣本點(diǎn)，使該樣本點(diǎn)距全部這些均值點(diǎn)最小距離為最大，這么就得到了第c個(gè)代表點(diǎn)?！綜均值算法】31第31頁(yè)【動(dòng)態(tài)聚類】C均值算法初始分類方法：1.最近距離法。離哪個(gè)代表點(diǎn)近就歸入哪一類。2.最近距離法歸類，但每次都重新計(jì)算該類代表點(diǎn)。3.直接劃分初始分類：每一個(gè)樣本自成一類，第二個(gè)樣本若離它小于某距離閾值則歸入這類，不然建新類，……4.將特征歸一化，用樣本各特征之和作為初始分類依據(jù)。說明：初始劃分無一定之規(guī)，多為啟發(fā)式方法。

C均值方法結(jié)果受初值影響，是局部最優(yōu)解。32第32頁(yè)【動(dòng)態(tài)聚類】C均值算法33第33頁(yè)【動(dòng)態(tài)聚類】C均值算法34第34頁(yè)【動(dòng)態(tài)聚類】C均值算法35第35頁(yè)【動(dòng)態(tài)聚類】C均值聚類方法用于非監(jiān)督模式識(shí)別問題：1.要求類別數(shù)已知；2.是最小方差劃分，并不一定能反應(yīng)內(nèi)在分布；3.與初始劃分相關(guān)，不確保全局最優(yōu)。C均值算法36第36頁(yè)在類別數(shù)未知情況下使用C—均值算法時(shí)，能夠假設(shè)類別數(shù)是逐步增加，比如對(duì)c＝1，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ù)未知】37第37頁(yè)不過并非全部情況都能找到顯著轉(zhuǎn)折點(diǎn)。在無顯著轉(zhuǎn)折點(diǎn)時(shí)，這種選擇最正確分類數(shù)方法將失效。普通需要利用先驗(yàn)知識(shí)對(duì)不一樣聚類結(jié)果進(jìn)行分析比較。

【C均值算法-類別數(shù)未知】38第38頁(yè)C均值算法比較簡(jiǎn)單，但它自我調(diào)整能力也比較差。這主要表現(xiàn)在類別數(shù)必須事先確定，不能改變，這種主觀確定數(shù)據(jù)子集數(shù)目并不一定符合數(shù)據(jù)集本身特點(diǎn)，受代表點(diǎn)初始選擇影響也比較大。類似于C

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

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

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

【迭代自組織數(shù)據(jù)分析算法-ISODATA】39第39頁(yè)

分裂則主要發(fā)生在某一類別某分量出現(xiàn)類內(nèi)方差過大現(xiàn)象，因而宜分裂成兩個(gè)類別，以維持合理類內(nèi)方差。給出一個(gè)對(duì)類內(nèi)分量方差限制參數(shù)，用以決定是否需要將某一類分裂成兩類。2.因?yàn)樗惴ㄓ凶晕艺{(diào)整能力，因而需要設(shè)置若干個(gè)控制用參數(shù)。

迭代自組織算法流程圖如圖5-7所表示。【迭代自組織數(shù)據(jù)分析算法-ISODATA】40第40頁(yè)ISODATA算法詳細(xì)步驟以下：【迭代自組織數(shù)據(jù)分析算法-ISODATA】41第41頁(yè)【迭代自組織數(shù)據(jù)分析算法-ISODATA】42第42頁(yè)【迭代自組織數(shù)據(jù)分析算法-ISODATA】43第43頁(yè)【迭代自組織數(shù)據(jù)分析算法-ISODATA】44第44頁(yè)【迭代自組織數(shù)據(jù)分析算法-ISODATA】45第45頁(yè)步驟9(求每類含有最大標(biāo)準(zhǔn)偏差分量)步驟10(分裂計(jì)算步驟)【迭代自組織數(shù)據(jù)分析算法-ISODATA】46第46頁(yè)合并處理：

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

【迭代自組織數(shù)據(jù)分析算法-ISODATA】47第47頁(yè)步驟12(列出類間距離過近者)

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

【迭代自組織數(shù)據(jù)分析算法-ISODATA】48第48頁(yè)步驟14(結(jié)束步驟)

假如迭代運(yùn)算次數(shù)已達(dá)最大迭代次數(shù)I，即是最終一次迭代，則算法結(jié)束；不然，假如需要由操作者改變輸入?yún)?shù)，轉(zhuǎn)入步驟1，設(shè)計(jì)對(duì)應(yīng)參數(shù)；不然，轉(zhuǎn)入步驟2。到了本步運(yùn)算，迭代運(yùn)算次數(shù)加1。以上是整個(gè)ISODATA算法計(jì)算步驟。能夠看出ISODATA算法與C

均值算法一樣，都是以與代表點(diǎn)最小距離作為樣本聚類依據(jù)，所以比較適合各類物體在特征空間以超球體分布方式分布，對(duì)于分布形狀較復(fù)雜情況需要采取別度量。ISODATA算法與C均值算法主要不一樣在于自我控制與調(diào)整能力不一樣。【迭代自組織數(shù)據(jù)分析算法-ISODATA】49第49頁(yè)ISODATA算法流程圖【迭代自組織數(shù)據(jù)分析算法-ISODATA】50第50頁(yè)【基于樣本和核相同性度量動(dòng)態(tài)聚類算法】51第51頁(yè)【基于樣本和核相同性度量動(dòng)態(tài)聚類算法】52第52頁(yè)【基于樣本和核相同性度量動(dòng)態(tài)聚類算法】53第53頁(yè)【近鄰函數(shù)準(zhǔn)則算法】定義54第54頁(yè)【近鄰函數(shù)準(zhǔn)則算法】55第55頁(yè)【近鄰函數(shù)準(zhǔn)則算法】56第56頁(yè)4.分級(jí)聚類方法（HierachicalClustering）57第57頁(yè)分級(jí)聚類方法目標(biāo)并不把N個(gè)樣本分成某一個(gè)預(yù)定類別數(shù)C，而是把樣本集按不一樣相同程度要求分成不一樣類別聚類。最極端情況是每個(gè)樣本各自為一類，N個(gè)樣本共有N類，沒有任何聚類，另一極端則是將全部樣本歸一類。在這兩個(gè)極端之間是類別數(shù)從N逐步降低，每類數(shù)量對(duì)應(yīng)增加，而類內(nèi)樣本相同程度要求也隨之下降。這種聚類就是分級(jí)聚類，它能夠用一樹形結(jié)構(gòu)表示?！痉旨?jí)聚類方法--類別數(shù)未知

】58第58頁(yè)這是一棵含有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í)聚類樹表示方法

】59第59頁(yè)【分級(jí)聚類方法

】思想：從各類只有一個(gè)樣本點(diǎn)開始，逐層合并，每級(jí)只合并兩類，直到最終全部樣本都?xì)w到一類。Hierarchicaltree--dendrogram聚類過程中逐層考查類間相同度，依此決定類別數(shù)60第60頁(yè)樹枝長(zhǎng)度：反應(yīng)結(jié)點(diǎn)/樹枝之間相