機器學習算法與實踐 課件 第9、10章 聚類算法、數(shù)據(jù)降維

第九章聚類算法

無監(jiān)督學習（UnsupervisedLearning）是指在樣本標記信息未知的情況下，通過對樣本的學習來找到數(shù)據(jù)本身的內(nèi)在性質(zhì)和規(guī)律。無監(jiān)督學習可以用于數(shù)據(jù)分析或者監(jiān)督學習的前處理，主要包含聚類（Clustering）、降維（DimensionalityReduction）、概率估計（ProbabilityEstimation）等。

其中聚類應(yīng)用最為廣泛，其基本思想是將樣本中“相似”的樣本聚為相同的類或簇，“不相似”的樣本聚為不同的類。19.1聚類概述相似或者不相似的定義和標準不是固定的，而是根據(jù)數(shù)據(jù)本身的性質(zhì)決定。依據(jù)形狀聚類依據(jù)顏色聚類

依據(jù)不同的策略，可以設(shè)計不同的聚類算法，主要包括原型聚類、層次聚類以及密度聚類。29.1.1相似度1.樣本相似度

常用的有距離（Distance）（閔可夫斯基距離（MinkowskiDistance）、馬哈拉諾比斯距離（MahalanobisDistance））、相關(guān)系數(shù)（CorrelationCoefficient）、夾角余弦等。

聚類的核心概念是相似度，其度量方式有很多種，并直接影響聚類結(jié)果的好壞，具體哪一種更好取決于問題本身的特性。39.1.1相似度（1）閔可夫斯基距離（MinkowskiDistance）

49.1.1相似度

（2）馬哈拉諾比斯距離（MahalanobisDistance）59.1.1相似度

（3）相關(guān)系數(shù)(相關(guān)系數(shù)絕對值越接近1表示樣本越相似；越接近0表示樣本越不相似)

（4）夾角余弦(夾角余弦的數(shù)值越接近1表示樣本越相似；越接近0表示樣本越不相似)69.1.1相似度（5）VDM（ValueDifferenceMetric）距離

79.1.1相似度（6）加權(quán)距離（WeightedDistance）

89.1.1相似度2.類（或簇）的相似度或距離

99.1.2

性能度量

聚類算法的性能度量是一種“有效性指標（ValidityIndex）”，評估類內(nèi)樣本的相似度，不同類別之間的相似度，用以評價聚類結(jié)果以及聚類算法的好壞。

109.1.2

性能度量

顯然，DBI指數(shù)越小越好，DI指數(shù)越大越好119.2

原型聚類

129.2

原型聚類

算法流程：139.2

原型聚類

149.3

密度聚類

假設(shè)聚類結(jié)構(gòu)可以通過樣本分布的緊密程度確定，以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進行聚類。

此類算法無需預先設(shè)定類別數(shù)量，因此適合于未知內(nèi)容的數(shù)據(jù)集，代表算法有DBSCAN、OPTICS、DENCLUE等(本節(jié)只討論DBSCAN)主要思想：

逐步檢查數(shù)據(jù)集中的每個樣本，如果其鄰域內(nèi)的樣本點總數(shù)小于某個閾值，那么定義該點為低密度點；反之，如果大于該閾值，則稱其為高密度點。如果一個高密度點在另外一個高密度點的鄰域內(nèi)，就直接把這兩個高密度點劃分為一個類別；如果一個低密度點在一個高密度點的鄰域內(nèi)，則將該低密度點加入距離它最近的高密度點的類別中；不在任何高密度點鄰域內(nèi)的低密度點，被劃入異常點類別，直到最終處理整個數(shù)據(jù)集?；靖拍睿?59.3

密度聚類DBSCAN算法

其核心是找到樣本點的全部密集區(qū)域，并把這些密集區(qū)域當作不同的類別。如下圖所示：

利用“鄰域”（Neighborhood）的半徑和最少點數(shù)（Minpoints，簡記為Minpts）兩個參數(shù)刻畫樣本分布的緊密程度。169.3

密度聚類將樣本點分為以下三類：

179.3

密度聚類非密度相連（Non-densityConnected）：如果兩個點不屬于密度相連關(guān)系，則兩個點非密度相連。進一步定義四種樣本點的關(guān)系：

189.3

密度聚類

任意選擇一個沒有類別的核心對象作為種子，然后找到所有這個核心對象能夠密度可達的樣本集合，即為一個類別。接著繼續(xù)選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇，這樣的得到都肯定是密度相連的，一直運行到所有核心對象都有類別為止。DBSCAN方法199.3

密度聚類

20

例：如下圖所示：

9.3

密度聚類

219.3

密度聚類

229.3

密度聚類

239.3

密度聚類

249.3

密度聚類

259.3

密度聚類（2）可以在聚類的同時發(fā)現(xiàn)異常點，對數(shù)據(jù)集中的異常點不敏感。主要優(yōu)點：主要缺點：（1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量較差，這時DBSCAN聚類一般不適合。

269.4

層次聚類(假設(shè)類別之間存在層次結(jié)構(gòu)，將樣本聚到層次化的類別中)聚合（Agglomerative）/自下而上（Bottom-up）聚類——本節(jié)重點分裂（Divisive）/自上而下（Top-down）聚類

每個樣本各分到一個類，之后將距離相近的兩類合并，建立一個新的類別，重復此操作直到滿足停止條件，得到層次化的類別。

將所有的樣本分到一個類，之后將已有類中相距最遠的樣本分到兩個新的類，重復此操作直到滿足停止條件，得到層次化的類別。279.4

層次聚類Agglomerative聚類算法基本流程：

距離尺度：最短距離、最長距離、平均距離、Ward方差等對應(yīng)算法：“單鏈接（Single-linkage）”、“全鏈接（Complete-linkage）”、“單鏈接（Average-linkage）”

、“Ward鏈接（Ward-linkage）”等289.4

層次聚類例：單鏈接Agglomerative聚類算法步驟：

299.4

層次聚類

309.4

層次聚類圖解示例：Agglomerative聚類算法可在不同層次上對數(shù)據(jù)集進行劃分，形成一個樹狀的聚類結(jié)構(gòu)，可以指定類別數(shù)也可不指定。但Agglomerative聚類算法的時間和空間復雜度較高，不適合解決大型數(shù)據(jù)集聚類問題。319.5

本章小結(jié)

DBSCAN算法，不需要指定類別的數(shù)量，聚類的形狀可以是任意的，能找出數(shù)據(jù)中的噪音，對噪音不敏感，算法應(yīng)用參數(shù)少。但對于密度不均勻的樣本集、聚類間距差相差很大的樣本集，聚類質(zhì)量較差，一般不適合。Agglomerative聚類算法可在不同層次上對數(shù)據(jù)集進行劃分，形成一個樹狀的聚類結(jié)構(gòu)，可以指定類別數(shù)也可不指定。但Agglomerative聚類算法的時間和空間復雜度較高，不適合解決大型數(shù)據(jù)集聚類問題。其次，對于三種算法，通過不同案例，分別介紹了手工實現(xiàn)和調(diào)包實現(xiàn)兩種代碼實現(xiàn)方式。32第十章數(shù)據(jù)降維

數(shù)據(jù)降維是緩解維數(shù)災(zāi)難常用方法之一，是將原始數(shù)據(jù)映射到低維子空間，以達到降低維度的目的，這個過程中數(shù)據(jù)的特征發(fā)生了本質(zhì)的變化，新的子空間的特征不再是原來的特征，因此不存在完全無損的降維方法，區(qū)別只是損失多少的問題.

針對研究對象，我們通常會收集一系列特征屬性，對研究對象進行分析，屬性越多，越有利于細致研究分析。但是隨著屬性增多，也會增加后續(xù)數(shù)據(jù)處理的運算量，帶來較大的處理負擔。3310.1

數(shù)據(jù)降維概述

數(shù)據(jù)降維方法從不同角度可以分為不同的類別，根據(jù)數(shù)據(jù)的特性劃分，有線性降維和非線性降維；根據(jù)是否利用數(shù)據(jù)的監(jiān)督信息劃分，有無監(jiān)督降維、有監(jiān)督降維和半監(jiān)督降維；根據(jù)是否保持數(shù)據(jù)的結(jié)構(gòu)劃分，有全局保持降維、局部保持降維和全局與局部保持一致降維等。需要根據(jù)特定的問題選擇合適的數(shù)據(jù)降維方法.

本章主要介紹常見的兩種數(shù)據(jù)降維技術(shù)：主成分分析（PrincipalComponentAnalysis，簡稱PCA）、線性判別分析（LinearDiscriminantAnalysis，簡稱LDA）。3410.2

主成分分析35

主成分分析（PrincipalComponentAnalysis，PCA）主要用于發(fā)現(xiàn)數(shù)據(jù)中變量之間的關(guān)系，是數(shù)據(jù)分析的有力工具，是一種常用的無監(jiān)督學習方法，其原理是通過通過正交變換將一組可能存在相關(guān)性的變量轉(zhuǎn)換為一組線性不相關(guān)的變量，轉(zhuǎn)換后的這組變量叫主成分，它是原特征的線性組合，其個數(shù)通常小于原始變量的個數(shù)。10.2

主成分分析PCA算法原理：（1）由于樣本的屬性特征維數(shù)較高，相互之間存在關(guān)聯(lián)關(guān)系.為了消除相關(guān)性，對原始屬性進行線性線性組合，找到一組彼此不相關(guān)的屬性特征；（2）在新的屬性特征中，刪除一些不重要的特征，保留較少特征數(shù)，同時保證損失較小.利用線性代數(shù)的知識對此進行解釋：

3610.2.1

PCA算法原理

37

10.2.1

PCA算法原理38

對于二維降一維問題，只需要找到一個基向量就夠了，即方差最大化就夠了。但對于更高維的問題，還有其他基向量需要求解.10.2.1

PCA算法原理39

例如，三維降二維，第一個基向量通過方差找到，第二個如果也利用方差，那么它與第一個基向量幾乎重合.我們希望第二個基向量與第一個線性無關(guān)，而協(xié)方差可以表示樣本某兩個屬性的相關(guān)性.當協(xié)方差為0時，表示樣本的某兩個屬性獨立。

由上述討論知，我們希望單個屬性上方差最大，兩兩屬性間協(xié)方差為0。為將二者統(tǒng)一，我們考慮協(xié)方差矩陣。10.2.1

PCA算法原理

那么同樣地，可以推廣至更高維。40

10.2.1

PCA算法原理若要找到一組新的正交基，使得在這組基下的樣本集的協(xié)方差矩陣為對角陣，并且為了找到最大方差，對角線上元素應(yīng)從大到小排列。

4110.2.1

PCA算法原理

利用特征值分解利用奇異值（SVD）分解

4210.2.1

PCA算法原理那么此時

SVD降維與特征值降維雖然原理一致，但不需要計算協(xié)方差矩陣，節(jié)省了計算量。4310.2.1

PCA算法原理貢獻率

對于利用SVD實現(xiàn)的降維，我們可以利用奇異值衡量，將上面兩個公式中的特征值替換為對應(yīng)的奇異值即可。

4410.2.2

特征值分解降維利用特征值和特征向量實現(xiàn)PCA算法基本步驟：

4510.2.3

奇異值分解降維利用SVD實現(xiàn)PCA算法基本步驟：

4610.3線性判別分析(LinearDiscriminantAnalysis，簡稱LDA)LDA是一種經(jīng)典的線性學習方法、分類算法，也是一種有監(jiān)督降維方法?；舅枷雽?shù)據(jù)投影到低維空間上，并且希望投影后的數(shù)據(jù)點滿足：同一類別盡可能“接近”，不同類別盡可能“遠離”。4710.3線性判別分析(LinearDiscriminantAnalysis，簡稱LDA)算法原理(以二分類問題為例)：

4810.3線性判別分析

4910.3線性判別分析二分類問題（1）廣義Rayleigh商

5010.3線性判別分析（2）類內(nèi)散度

5110.3線性判別分析

那么投影后的兩類樣本的方差和為

定義類內(nèi)散度矩陣為5210.3線性判別分析（3）類間散度

（4）LDA模型（