無(wú)監(jiān)督學(xué)習(xí)與聚類(lèi)第一頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.0監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)的最大區(qū)別在于訓(xùn)練樣本是否有類(lèi)別標(biāo)號(hào)，無(wú)類(lèi)別標(biāo)號(hào)的稱(chēng)為無(wú)監(jiān)督學(xué)習(xí)；監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)也被稱(chēng)為有教師學(xué)習(xí)與無(wú)教師學(xué)習(xí)。第二頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.1混合密度及可辨識(shí)性從理論上講，無(wú)監(jiān)督學(xué)習(xí)可以看作是一個(gè)混合密度的估計(jì)問(wèn)題：所有樣本都來(lái)自于c種類(lèi)別，c已知；每種類(lèi)別的先驗(yàn)概率已知；類(lèi)條件概率的數(shù)學(xué)形式已知，但參數(shù)未知；樣本類(lèi)別未被標(biāo)記。第三頁(yè)，共三十八頁(yè)，編輯于2023年，星期六混合密度樣本可以看作是按如下方式產(chǎn)生的：先以概率決定其所屬類(lèi)別，然后根據(jù)概率密度生成一個(gè)具體的樣本x。因此x樣本的產(chǎn)生概率為：第四頁(yè)，共三十八頁(yè)，編輯于2023年，星期六可辨識(shí)性不可辨識(shí)：如果無(wú)論樣本的數(shù)目有多少，都不存在唯一的解，則稱(chēng)密度是不可辨識(shí)的；完全不可辨識(shí)：如果參數(shù)的任何部分都無(wú)法求出，則稱(chēng)為完全不可辨識(shí)；大多數(shù)的混合密度是可以辨識(shí)的，但也存在某些混合密度是無(wú)法辨識(shí)的。第五頁(yè)，共三十八頁(yè)，編輯于2023年，星期六完全不可辨識(shí)假設(shè)樣本x的概率是由兩個(gè)0-1分布混合而成，兩個(gè)分布的先驗(yàn)概率相等，參數(shù)分別為則混合概率為：即使可以統(tǒng)計(jì)出，也無(wú)法求解出參數(shù)。第六頁(yè)，共三十八頁(yè)，編輯于2023年，星期六部分不可辨識(shí)假設(shè)樣本x的概率密度是兩個(gè)均勻分布的混合：如果訓(xùn)練樣本是0-1之間的均勻分布：則對(duì)任意的0<t<1，只要：第七頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.2聚類(lèi)準(zhǔn)則函數(shù)類(lèi)別數(shù)c=2第八頁(yè)，共三十八頁(yè)，編輯于2023年，星期六誤差平方和準(zhǔn)則將樣本分成c個(gè)子集D1,…,Dc，ni為第i個(gè)子集的樣本數(shù)，mi為樣本均值：誤差平方和準(zhǔn)則：第九頁(yè)，共三十八頁(yè)，編輯于2023年，星期六散布矩陣類(lèi)內(nèi)散布矩陣：類(lèi)間散布矩陣：總體散布矩陣：第十頁(yè)，共三十八頁(yè)，編輯于2023年，星期六散布準(zhǔn)則基于行列式的散布準(zhǔn)則：基于不變量的散布準(zhǔn)則：第十一頁(yè)，共三十八頁(yè)，編輯于2023年，星期六準(zhǔn)則函數(shù)的優(yōu)化窮舉法優(yōu)化：聚類(lèi)準(zhǔn)則函數(shù)的優(yōu)化是組合最優(yōu)問(wèn)題，是一個(gè)NP難題，將n個(gè)樣本分到c個(gè)類(lèi)別有cn/c!種分法，窮舉計(jì)算是不現(xiàn)實(shí)的，只能尋找次優(yōu)方法解決；迭代最優(yōu)化：隨機(jī)設(shè)置初始聚類(lèi)，計(jì)算將樣本x從Di聚類(lèi)移到Dj聚類(lèi)是否能夠使準(zhǔn)則函數(shù)減小，減小則做此修改，否則不修改。第十二頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.3k-均值聚類(lèi)begininitialize樣本數(shù)n，聚類(lèi)數(shù)c，初始聚類(lèi)中心m1,…,mc；

do按照最近鄰mi分類(lèi)n個(gè)樣本；重新計(jì)算聚類(lèi)中心m1,…,mc；

untilmi不再改變；returnm1,…,mc;end第十三頁(yè)，共三十八頁(yè)，編輯于2023年，星期六k-均值聚類(lèi)的特點(diǎn)k-均值算法可以看作是對(duì)平方誤差準(zhǔn)則函數(shù)的貪心搜索算法；聚類(lèi)結(jié)果受初始聚類(lèi)中心的選擇影響很大，不同的初始聚類(lèi)中心會(huì)導(dǎo)致不同的聚類(lèi)結(jié)果。第十四頁(yè)，共三十八頁(yè)，編輯于2023年，星期六模糊k-均值聚類(lèi)k-均值算法的每一步迭代中，每一個(gè)樣本都被認(rèn)為完全屬于某一個(gè)類(lèi)別。作為改進(jìn)版本，可以引入模糊的概念，假定每個(gè)樣本以某種隸屬度函數(shù)屬于某個(gè)類(lèi)別；樣本x對(duì)第i個(gè)聚類(lèi)的隸屬度可以定義為： 其中mi為第i個(gè)聚類(lèi)的均值，b>1為控制不同類(lèi)別混合程度的自由參數(shù)。第十五頁(yè)，共三十八頁(yè)，編輯于2023年，星期六模糊k-均值聚類(lèi)算法begininitializen,c,b,m1,…,mc;do計(jì)算n個(gè)樣本對(duì)c個(gè)類(lèi)別的隸屬度：重新計(jì)算各個(gè)聚類(lèi)的均值m1,…,mc;untilm1,…,mc變化很??；returnm1,…,mc。第十六頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.4層次聚類(lèi)begininitializec,c’n,Di{xi},i=1,…,n;doc’c’-1

求最接近的聚類(lèi)，如Di和Dj；合并Di和Dj；

untilc’=c;returnc個(gè)聚類(lèi);end第十七頁(yè)，共三十八頁(yè)，編輯于2023年，星期六層次聚類(lèi)的樹(shù)圖相似度標(biāo)尺第十八頁(yè)，共三十八頁(yè)，編輯于2023年，星期六層次聚類(lèi)的特點(diǎn)層次聚類(lèi)不用初始化聚類(lèi)中心，因此聚類(lèi)結(jié)果不受初始聚類(lèi)中心的影響；需要定義類(lèi)別之間的相似性度量；當(dāng)樣本數(shù)比較多時(shí)，算法的計(jì)算量比較大（算法第3步）。聚類(lèi)結(jié)果同樣是對(duì)平方誤差準(zhǔn)則函數(shù)的貪心優(yōu)化結(jié)果。第十九頁(yè)，共三十八頁(yè)，編輯于2023年，星期六聚類(lèi)算法存在的問(wèn)題（一）準(zhǔn)則函數(shù)的選擇平方誤差準(zhǔn)則Je比較大平方誤差準(zhǔn)則Je比較小第二十頁(yè)，共三十八頁(yè)，編輯于2023年，星期六聚類(lèi)算法存在的問(wèn)題（二）特征量綱的影響（縮放坐標(biāo)軸）第二十一頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.5競(jìng)爭(zhēng)學(xué)習(xí)Hebb假設(shè)：如果一條突觸兩側(cè)的神經(jīng)元同時(shí)被激活，則該突觸的強(qiáng)度將會(huì)增大；Hebb學(xué)習(xí)規(guī)則：第i個(gè)神經(jīng)元與第j個(gè)神經(jīng)元之間的連接wij，第i個(gè)神經(jīng)元向第j個(gè)神經(jīng)元的輸出為p，第j個(gè)神經(jīng)元的輸出為a，則： 其中η為學(xué)習(xí)率。第二十二頁(yè)，共三十八頁(yè)，編輯于2023年，星期六競(jìng)爭(zhēng)網(wǎng)絡(luò)樣本的特征維數(shù)為d，輸入層神經(jīng)元數(shù)d+1，輸入樣本須歸一化到單位長(zhǎng)度；輸出層對(duì)應(yīng)c個(gè)類(lèi)別；輸出層神經(jīng)元之間有側(cè)向抑制連接，對(duì)于每一個(gè)輸入樣本，只有一個(gè)競(jìng)爭(zhēng)層神經(jīng)元被激活(稱(chēng)為勝元，輸出1)，其它神經(jīng)元被抑制(輸出0)。輸入層競(jìng)爭(zhēng)層第二十三頁(yè)，共三十八頁(yè)，編輯于2023年，星期六競(jìng)爭(zhēng)學(xué)習(xí)begininitialize學(xué)習(xí)率η,訓(xùn)練樣本數(shù)n,類(lèi)別數(shù)c,迭代次數(shù)k，初始權(quán)值w1,…,wc;歸一化所有訓(xùn)練樣本和權(quán)值；do隨機(jī)選取一個(gè)x計(jì)算勝元：權(quán)值修正：權(quán)值歸一化：until在k次重復(fù)中w無(wú)顯著改變；returnw1,…,wc第二十四頁(yè)，共三十八頁(yè)，編輯于2023年，星期六競(jìng)爭(zhēng)學(xué)習(xí)過(guò)程第二十五頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.6自組織特征映射自組織特征映射也稱(chēng)為Kohonen網(wǎng)絡(luò)(SOFM,Self-OrganizingFeatureMap)；SOFM采用的仍然是競(jìng)爭(zhēng)學(xué)習(xí)規(guī)則，與競(jìng)爭(zhēng)網(wǎng)絡(luò)不同的是競(jìng)爭(zhēng)網(wǎng)絡(luò)每次只對(duì)一個(gè)勝元的權(quán)值進(jìn)行調(diào)整，而SOFM則對(duì)以勝元為中心的一個(gè)鄰域內(nèi)的神經(jīng)元均進(jìn)行調(diào)整；經(jīng)過(guò)學(xué)習(xí)后的網(wǎng)絡(luò)會(huì)具有空間拓?fù)溆行蛐?。第二十六?yè)，共三十八頁(yè)，編輯于2023年，星期六1維SOFM網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)窗函數(shù)輸入層競(jìng)爭(zhēng)層第二十七頁(yè)，共三十八頁(yè)，編輯于2023年，星期六2維SOFM網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)窗函數(shù)y*輸入層競(jìng)爭(zhēng)層第二十八頁(yè)，共三十八頁(yè)，編輯于2023年，星期六SOFM學(xué)習(xí)算法begininitialize網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，權(quán)值，鄰域Λ(0)，迭代次數(shù)T，學(xué)習(xí)率η(0)，t0；歸一化所有訓(xùn)練樣本和權(quán)值；

do隨機(jī)選擇樣本x；計(jì)算勝元y*：調(diào)整權(quán)值：權(quán)值歸一化：

tt+1；until

t=T 其中Λ(t)逐漸縮小范圍，η(t)逐漸減小。第二十九頁(yè)，共三十八頁(yè)，編輯于2023年，星期六10.6譜聚類(lèi)譜聚類(lèi)是一種新的聚類(lèi)分析方法譜聚類(lèi)通過(guò)求取核矩陣的特征值和特征矢量實(shí)現(xiàn)聚類(lèi)。令：{x1,…,xn}為樣本集合，?為輸入空間到特征空間的映射，并且||?(x)||=1，k為相應(yīng)的核函數(shù)。核矩陣K=[k(xi,xj)]n×n第三十頁(yè)，共三十八頁(yè)，編輯于2023年，星期六兩類(lèi)譜聚類(lèi)計(jì)算核矩陣K；計(jì)算對(duì)應(yīng)最大特征值的特征矢量y（n維）；通過(guò)一個(gè)閾值ε量化y，y中的元素大于ε的置為1，小于ε的置為0；對(duì)應(yīng)0的樣本為一個(gè)類(lèi)別，對(duì)應(yīng)1的樣本為另一個(gè)類(lèi)別。第三十一頁(yè)，共三十八頁(yè)，編輯于2023年，星期六例10.1將19個(gè)樣本分成2個(gè)聚類(lèi)。

x1=(0,0)t,x2=(1,0)t,x3=(0,1)t,x4=(1,1)t, x5=(2,1)t,x6=(1,2)t,x7=(2,2)t,x8=(3,2)t, x9=(6,6)t,x10=(7,6)t,x11=(8,6)t,x12=(7,7)t, x13=(8,7)t,x14=(9,7)t,x15=(7,8)t,x16=(8,8)t, x17=(9,8)t,x18=(8,9)t,x19=(9,9)t第三十二頁(yè)，共三十八頁(yè)，編輯于2023年，星期六核矩陣：第三十三頁(yè)，共三十八頁(yè)，編輯于2023年，星期六特征值 最大特征值對(duì)應(yīng)特征矢量第三十四頁(yè)，共三十八頁(yè)，編輯于2023年，星期六聚類(lèi)結(jié)果第三十五頁(yè)，共三十八頁(yè)，編輯于2023年，星期六多類(lèi)別譜聚類(lèi)計(jì)算核矩陣K；計(jì)算K的特征值和特征矢量；觀(guān)察特征值分布，確定聚類(lèi)數(shù)m；利用對(duì)應(yīng)前m個(gè)特征值的特征矢量確定樣本的類(lèi)別歸屬。第三十六頁(yè)，共三十八頁(yè)，編輯于2023年，星期六例10.2