機(jī)器學(xué)習(xí)聚類-山東大學(xué)

1、數(shù)學(xué)文化之機(jī)器學(xué)習(xí),劉丙強(qiáng)山東大學(xué)數(shù)學(xué)學(xué)院知新樓B835; 88363455bingqiangsdu@gmail.com2013-11-20 (3),1,統(tǒng)計(jì)與機(jī)器學(xué)習(xí),統(tǒng)計(jì)學(xué)：從不完全的信息里取得準(zhǔn)確知識(shí)的技巧。統(tǒng)計(jì)應(yīng)用：用數(shù)理統(tǒng)計(jì)的原理和方法，分析和解釋自然界界的種種現(xiàn)象和數(shù)據(jù)資料，以求把握其本質(zhì)和規(guī)律性。機(jī)器學(xué)習(xí)：可以理解為計(jì)算機(jī)自動(dòng)從數(shù)據(jù)中發(fā)現(xiàn)規(guī)律，并應(yīng)用于解決新問題。內(nèi)容比較雜，至今還沒

2、有統(tǒng)一的定義，而且也很難給出一個(gè)公認(rèn)的和準(zhǔn)確的定義。機(jī)器學(xué)習(xí)在大多數(shù)情況下應(yīng)用概率論與統(tǒng)計(jì)學(xué)理論來設(shè)計(jì)算法；,2,機(jī)器學(xué)習(xí),給定數(shù)據(jù) (X1, Y1), (X2, Y2), … ,(Xn, Yn)，機(jī)器自動(dòng)學(xué)習(xí) X 和 Y 之間的關(guān)系，從而對(duì)新的 Xi，能夠預(yù)測(cè) Yi。垃圾郵件識(shí)別：(郵件 1, 垃圾), (郵件 2, 正常), (郵件 3, 垃圾), …(郵件 N, 正常)郵件 X => 垃圾 or 正常？,3,測(cè)試數(shù)據(jù)

3、,發(fā)現(xiàn)規(guī)律,預(yù)測(cè),預(yù)測(cè)結(jié)果,規(guī)則,,,,,,郵件Xi,Yi：垃圾or正常,發(fā)件人郵件地址異常；標(biāo)題含有“低價(jià)促銷”…,機(jī)器學(xué)習(xí),一般流程：,4,訓(xùn)練數(shù)據(jù),測(cè)試數(shù)據(jù),學(xué)習(xí),預(yù)測(cè),預(yù)測(cè)結(jié)果,模型,,,,,,,,訓(xùn)練過程,應(yīng)用過程,(X1, Y1)(X2, Y2)… (Xn, Yn),Xi,Yi,機(jī)器學(xué)習(xí),模型：?jiǎn)栴}的影響因素(特征)有哪些？它們之間的關(guān)系如何？策略：什么樣的模型是好的模型；算法：如何高效的找到最優(yōu)參數(shù)

4、；分類：有監(jiān)督的學(xué)習(xí)；無監(jiān)督的學(xué)習(xí)；半監(jiān)督的學(xué)習(xí)；增強(qiáng)學(xué)習(xí)；多任務(wù)學(xué)習(xí)；,5,統(tǒng)計(jì)與機(jī)器學(xué)習(xí),內(nèi)容：聚類與分類；統(tǒng)計(jì)推斷：參數(shù)檢驗(yàn)，假設(shè)檢驗(yàn)；回歸分析；馬爾科夫鏈與隱馬爾科夫模型。遺傳算法與神經(jīng)網(wǎng)絡(luò)；。。。,6,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)集劃分為多個(gè)類別，使類別內(nèi)的數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相似度較小;簇（或類Cluster）：子集合最

5、大化簇（或類）內(nèi)的相似性；最小化簇（或類）間的相似性；聚類是一種無監(jiān)督分類法：沒有預(yù)先指定的類別；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布； 作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；,7,機(jī)器學(xué)習(xí)：聚類 (Clustering),簡(jiǎn)單示例：聚類后預(yù)測(cè)：,8,訓(xùn)練數(shù)據(jù),待分類數(shù)據(jù),機(jī)器學(xué)習(xí)：聚類 (Clustering),基因表達(dá)芯片（微陣列）：預(yù)測(cè)新測(cè)序基因的功能是重要的生物學(xué)問題；基因表達(dá)微陣列提供了預(yù)

6、測(cè)功能的途徑；基因芯片對(duì)研究調(diào)控網(wǎng)絡(luò)提供了最基本的數(shù)據(jù)；基因芯片可以衡量基因在不同條件下的表達(dá)量；基因如果被轉(zhuǎn)錄，就可以認(rèn)為是處于激活狀態(tài)；轉(zhuǎn)錄產(chǎn)物 mRNA 的數(shù)量代表基因的活性；,9,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA 芯片的應(yīng)用：研究基因樣本在在不同的時(shí)間段表達(dá)的差異；研究不同的基因樣本在相同的條件下的表達(dá)差異,10,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA芯片數(shù)據(jù)：綠色：僅僅在參考狀態(tài)表達(dá)

7、；紅色：僅僅在所研究的狀態(tài)表達(dá)；黃色：在兩種狀態(tài)都表達(dá)；黑色：在兩種狀態(tài)都不表達(dá)；表達(dá)強(qiáng)度數(shù)據(jù)會(huì)被標(biāo)準(zhǔn)化、組成表達(dá)強(qiáng)度矩陣。,11,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA 芯片數(shù)據(jù)的聚類：每組數(shù)據(jù)可以看做 n 維空間里的點(diǎn)；通過對(duì)每個(gè)點(diǎn)對(duì)計(jì)算距離構(gòu)造距離矩陣；距離較近的基因表達(dá)情況相似、或許更有可能具有功能上的相關(guān)性；聚類能夠構(gòu)造功能相關(guān)基因集合；,12,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA芯片數(shù)

8、據(jù)的聚類：同質(zhì)性：一個(gè)類中基因相似，即距離較小；差異性：不同類的基因非常不同，即距離較大；聚類并非易事；算法不同可能得到不同的結(jié)果；,13,,,,,,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA芯片數(shù)據(jù)的聚類：兩點(diǎn)之間的距離歐氏距離： 平方歐氏距離：夾角余弦：絕對(duì)距離： Chebychev距離:皮爾森相關(guān)系數(shù)：M

9、inkowski距離：,14,機(jī)器學(xué)習(xí)：聚類 (Clustering),DNA芯片數(shù)據(jù)的聚類：兩類之間的距離最短距離法:最長距離法：重心法：類平均法：離差平方和：,15,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法（k-means）給定 k, k-均值算法由以下四步來完成:把對(duì)象劃分為 k 個(gè)非空的子集；隨機(jī)的選擇一些種子點(diǎn)作為目前劃分的簇的質(zhì)心。質(zhì)心是簇的中心（平均點(diǎn)）；把每一個(gè)對(duì)象賦

10、給最近的種子點(diǎn)；重復(fù)第二步，直到?jīng)]有新的分配；,16,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法,17,,,,,,,,,,,,,,,,,,,,,,,,,,,,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法,18,,,,,,,,,,,,,,,,,,,,,,,,,,,,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法,19,,,,,,,,,,,,,,,,,,,,,,,,,,,,機(jī)器學(xué)習(xí)：聚

11、類 (Clustering),聚類方法：k-均值法,20,,,,,,,,,,,,,,,,,,,,,,,,,,,,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法優(yōu)點(diǎn)：復(fù)雜度: O(tkn), 其中 n 是對(duì)象的數(shù)目, k 是 cluster 的數(shù)目, t 是迭代的次數(shù)，通常 k, t << n；通常以局部最優(yōu)結(jié)束，使用遺傳算法技術(shù)可以達(dá)到全局最優(yōu)；缺點(diǎn)：只有在 cluster 的平均值被定義的情況下才

12、能使用，那當(dāng)涉及有分類屬性的數(shù)據(jù)時(shí)該怎么辦?需要事先給出 k， cluster 的數(shù)目；不能處理噪聲數(shù)據(jù)和孤立點(diǎn)；不適合發(fā)現(xiàn)非凸面形狀的 cluster ；對(duì)初值比較敏感；,21,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：k-均值法的初值敏感性,22,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clustering）,23,,,,,,,機(jī)器學(xué)習(xí)：聚類 (Clusterin

13、g),聚類方法：層次聚類（ Hierarchical Clustering）自底向下的聚類每一項(xiàng)自成一類迭代，將最近的兩類合為一類自頂向下的聚類將所有項(xiàng)看作一類找出最不相似的項(xiàng)分裂出去成為兩類,24,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clustering）,25,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：層次聚類（ Hierarchical Clusteri

14、ng）常用于系統(tǒng)發(fā)生樹的構(gòu)造（基于序列）：,26,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類與系統(tǒng)發(fā)生樹,27,棕熊 北極熊 黑熊 眼鏡熊 大熊貓 浣熊 小熊貓,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類與系統(tǒng)發(fā)生樹,28,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：有瑕團(tuán)聚類（ Corrupted Cliques Clustering）團(tuán)是圖論中的概念：通過刪邊和加邊，一個(gè)圖可以破解

15、為團(tuán)的集合：,29,,,機(jī)器學(xué)習(xí)：聚類 (Clustering),聚類方法：有瑕團(tuán)聚類待聚類數(shù)據(jù)的距離矩陣為完全圖的鄰接矩陣：通過取一個(gè)閾值，可以將距離大的邊刪除；將剩余的圖破解為團(tuán)的集合，每個(gè)團(tuán)對(duì)應(yīng)一個(gè)聚類；,30,機(jī)器學(xué)習(xí)：雙聚類 (Bi-Clustering),雙聚類：大規(guī)模表達(dá)數(shù)據(jù)的聚類基因并不在所有條件下表達(dá)；基因受多個(gè)轉(zhuǎn)錄因子調(diào)控；兩步聚類不能解決問題；,31,,,,,,,,,,,,傳統(tǒng)聚類,雙聚類,機(jī)器學(xué)習(xí)：

16、雙聚類 (Bi-Clustering),雙聚類的目標(biāo)：相關(guān)性,32,機(jī)器學(xué)習(xí)：分類,聚類與分類的區(qū)別：訓(xùn)練集合有無（監(jiān)督與非監(jiān)督）類別已知和未知,33,機(jī)器學(xué)習(xí)：分類,分類問題及其算法對(duì)研究對(duì)象進(jìn)行貼標(biāo)簽式分類；用途：自然科學(xué)中有很多分類問題；生物種群分類；基于訓(xùn)練集合進(jìn)行特征選??；基于各種特征進(jìn)行疾病診斷；方式：基于各種特征，或在機(jī)器學(xué)習(xí)過程中提取特征；一般基于訓(xùn)練集合給出關(guān)于特征的標(biāo)準(zhǔn)；,34,機(jī)器學(xué)習(xí)：分

17、類,二分類問題：目的：將研究目標(biāo)分為不同屬性的兩類；標(biāo)準(zhǔn)：基于訓(xùn)練集合的特征選取和特征函數(shù)構(gòu)造；方法：利用學(xué)習(xí)出來的標(biāo)準(zhǔn)對(duì)新目標(biāo)進(jìn)行分類；方法：貝葉斯分類；決策樹；支持向量機(jī)；人工神經(jīng)網(wǎng)絡(luò)；k 近鄰法；。。。,35,機(jī)器學(xué)習(xí)：決策樹,決策樹(Decision Tree) 決策樹由一個(gè)決策圖和可能的結(jié)果組成， 用來創(chuàng)建到達(dá)目標(biāo)的規(guī)劃。常用于分類；動(dòng)物分類的例子：基于不同的屬性進(jìn)行分步驟的判斷；,36,機(jī)器學(xué)習(xí)

18、：決策樹,要素：特征參數(shù)：xi；分類標(biāo)簽： y= 0 or 1；訓(xùn)練集合： (xi, yi)構(gòu)造樹：決策結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。步驟：利用訓(xùn)練集建立并精化決策樹，建立決策樹模型。利用決策樹對(duì)新數(shù)據(jù)進(jìn)行分類。從根結(jié)點(diǎn)依次測(cè)試記錄的屬性值，直到到達(dá)某葉結(jié)點(diǎn)，找到該記錄所在的類。關(guān)鍵點(diǎn)：建樹（Tree Building）：決策樹建樹算法見下，這是一個(gè)遞歸的過程，最終將得到一棵樹。剪枝（Tree Pruning）：剪枝的目的是降低

19、由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。,37,機(jī)器學(xué)習(xí)：決策樹,決策樹算法的點(diǎn)如下：決策樹是一種構(gòu)建分類模型的非參數(shù)方法；不需要昂貴的的計(jì)算代價(jià)；決策樹相對(duì)容易解釋；決策樹是學(xué)習(xí)離散值函數(shù)的典型代表；決策數(shù)對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性；冗余屬性不會(huì)對(duì)決策樹的準(zhǔn)確率造成不利影響；找到最佳的決策樹理論上是 NP 難問題；,38,機(jī)器學(xué)習(xí)：決策樹,例子：天氣與高爾夫球場(chǎng)客流量；對(duì)決策樹的期望：規(guī)模較??；葉節(jié)點(diǎn)盡量少，熵值低

20、；決策節(jié)點(diǎn)特征的選取；,39,機(jī)器學(xué)習(xí)：決策樹,決策樹的一些缺點(diǎn)：數(shù)據(jù)碎片問題。隨著樹的生長，可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少，對(duì)于葉結(jié)點(diǎn)代表的類，不能做出具有統(tǒng)計(jì)意義的判決；子樹可能在決策樹中重復(fù)多次，使決策樹過于復(fù)雜；判定條件太過明確，導(dǎo)致爭(zhēng)議；,40,機(jī)器學(xué)習(xí)：支持向量機(jī),支持向量機(jī) （SVM, Supporting Vector Machine）Vapnik；起源于線性分類器，線性可分；擴(kuò)展到線性不可分的情況；甚至擴(kuò)展

21、到使用非線性函數(shù)中去。近年來的熱點(diǎn)方法；監(jiān)督式學(xué)習(xí)（supervised learning）,41,機(jī)器學(xué)習(xí)：支持向量機(jī),思想：如果兩類別訓(xùn)練樣本線性可分，則在兩個(gè)類別的樣本集之間存在一個(gè)間隔。我們來尋找最優(yōu)分界面；對(duì)一個(gè)二維空間的問題用下圖表示。,42,機(jī)器學(xué)習(xí)：支持向量機(jī),思想（續(xù)1）H 是將兩類分開的分界面，而 H1 與 H2 與 H 平行，H 是其平分面，H1 上的樣本是第一類樣本到 H 最近距離的點(diǎn)，H2 的點(diǎn)則是第二

22、類樣本距 H 的最近點(diǎn)。,43,機(jī)器學(xué)習(xí)：支持向量機(jī),思想（續(xù)2）由于這兩種樣本點(diǎn)很特殊，處在間隔的邊緣上，因此再附加一個(gè)圈表示。這些點(diǎn)稱為支持向量，它們決定了這個(gè)間隔。,44,機(jī)器學(xué)習(xí)：支持向量機(jī),思想（續(xù)3）顯然使 H1 與 H2 之間間隔最大的分界面 H 是最合理的選擇，因此最大間隔準(zhǔn)則就是支持向量機(jī)的最佳準(zhǔn)則。,45,,,,,,機(jī)器學(xué)習(xí)：支持向量機(jī),如何找到最大間隔？在凸集合上找最近點(diǎn)：,46,,,,,,,,,,,,,,,

23、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,c,d,,,,,,機(jī)器學(xué)習(xí)：支持向量機(jī),分界線：一個(gè)線性判別函數(shù)(discriminant function)是指由 x 的各個(gè)分量的線性組合而成的函數(shù)；兩類情況:對(duì)于兩類問題的決策規(guī)則為如果 g(x) > 0，則判定 x 屬于 H1，如果 g(x) < 0，則判定 x 屬于 C2，如果 g(x) = 0，則可以將 x 任意分到某一類或者拒絕判

24、定。,47,機(jī)器學(xué)習(xí)：支持向量機(jī),方程 g(x) = 0 定義了一個(gè)判定面，它把歸類于 C1 的點(diǎn)與歸類于 C2 的點(diǎn)分開來。當(dāng) g(x) 是線性函數(shù)時(shí)，此平面被稱為超平面 (hyperplane)。方程 g(x) = 0 實(shí)際上是 n - 1維的線性子空間；,48,機(jī)器學(xué)習(xí)：支持向量機(jī),如何找到最大間隔？為了將這個(gè)準(zhǔn)則具體化，需要用數(shù)學(xué)式子表達(dá)。為了方便，將訓(xùn)練樣本集表示成 {xi, yi}，i = 1, …, N，其中 xi

25、為 d 維向量也就是特征向量，而 yi ∈{-1, +1}，即用 yi 是 +1 或 -1 表示其類別。對(duì)于分界面 H 表示成：并且滿足：故 H1到 H2 的間隔為：目標(biāo)：在滿足約束條件的前提下達(dá)到間隔最大；前提：線性可分；,49,機(jī)器學(xué)習(xí)：支持向量機(jī),轉(zhuǎn)化為帶約束的極值問題，或規(guī)劃問題；對(duì)于這樣一個(gè)帶約束條件為不等式的條件極值問題，需要引用擴(kuò)展的拉格朗日乘子理論，按這個(gè)理論構(gòu)造拉格朗日函數(shù)的原則為：,50,(3)

26、,機(jī)器學(xué)習(xí)：支持向量機(jī),上述方法線性可分條件為基本前提；可否將不可分問題轉(zhuǎn)化為可分？,51,機(jī)器學(xué)習(xí)：支持向量機(jī),異或問題是最簡(jiǎn)單的一個(gè)無法直接對(duì)特征采用線性判別函數(shù)解決的問題。如圖所示的四個(gè)樣本點(diǎn)。利用 SVM 將他們映射到一個(gè)更高維的空間，使之線性可分。,52,機(jī)器學(xué)習(xí)：支持向量機(jī),采用最簡(jiǎn)單且展開不超過二次的展開將上述問題的點(diǎn)映射到六維空間：最佳超平面是：其二維空間投影如圖所示,53,,機(jī)器學(xué)習(xí)：支持向量

27、機(jī),特點(diǎn)：對(duì)特征空間劃分的最優(yōu)超平面是SVM的目標(biāo),最大化分類邊際的思想是SVM方法的核心；支持向量是SVM的訓(xùn)練結(jié)果,在SVM分類決策中起決定作用的是支持向量；模型為凸二次規(guī)劃模型，沒有陷入局部最優(yōu)解的問題，任何局部最優(yōu)解都是全局最優(yōu)解；SVM 的最終決策函數(shù)只由少數(shù)的支持向量所確定,計(jì)算的復(fù)雜性取決于支持向量的數(shù)目,而不是樣本空間的維數(shù),這在某種意義上避免了“維數(shù)災(zāi)難”。少數(shù)支持向量決定了最終結(jié)果,這不但可以幫助我們抓住關(guān)

28、鍵樣本、“剔除”大量冗余樣本,而且注定了該方法不但算法簡(jiǎn)單,而且具有較好的“魯棒”性。,54,機(jī)器學(xué)習(xí)：分類結(jié)果的衡量,靈敏度（Sensitivity）與特異度（Specificity）假陽性（FP）、真陽性（TP）；假陰性（FN）、真陰性（FN）；,55,機(jī)器學(xué)習(xí)：分類結(jié)果的衡量,Test!,56,機(jī)器學(xué)習(xí)：分類結(jié)果的衡量,ROC曲線接收者操作特征（receiver operating characteristic）真陽性率（