機器學(xué)習(xí)算法與實踐 課件 第9章 聚類算法

第九章聚類算法

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

其中聚類應(yīng)用最為廣泛，其基本思想是將樣本中“相似”的樣本聚為相同的類或簇，“不相似”的樣本聚為不同的類。19.1聚類概述相似或者不相似的定義和標(biāo)準(zhǔn)不是固定的，而是根據(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

性能度量

聚類算法的性能度量是一種“有效性指標(biāo)（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ù)進(jìn)行聚類。

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

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

密度聚類DBSCAN算法

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

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

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

179.3

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

189.3

密度聚類

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

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

將所有的樣本分到一個類，之后將已有類中相距最遠(yuǎn)的樣本分到兩個新的類，重復(fù)此操作直到滿足停止條件，得到層次化的類別。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ù)集進(jìn)行劃分，形成一個樹狀的聚類結(jié)構(gòu)，可以指定類別數(shù)也可不指定。但Agglomerative聚類算法的時間和空間復(fù)雜度較高，不適合解決大型數(shù)據(jù)集聚類問題。319.5

本章小結(jié)

DBSCAN算法，不需要指定類別的數(shù)量，聚類的形狀可以是任意的，能找出數(shù)據(jù)中的噪音，對噪音不敏感，算法應(yīng)用參數(shù)少。但對于密度不均勻的樣本集、聚類間距差相差很大的樣本集，聚類質(zhì)量較差，一般不適合