《數(shù)據(jù)挖掘基礎(chǔ)及其應(yīng)用》課件第10章

第10章聚類分析Ⅱ:分層聚類與密度聚類10.1引言10.2分層聚類10.3分層聚類的實(shí)現(xiàn)10.4密度聚類10.5聚類結(jié)果評估10.6聚類算法對比本章小結(jié)

10.1引言

聚類分析是將物理或抽象對象的集合分組為由類似的對象組成的多個類的分析過程,它是一種重要的人類行為,已在數(shù)學(xué)、計算機(jī)科學(xué)、統(tǒng)計、生物和經(jīng)濟(jì)等不同領(lǐng)域進(jìn)行了廣泛的應(yīng)用。

聚類分析的優(yōu)點(diǎn):

(1)簡單、直觀;

(2)主要應(yīng)用于探索性的研究,其結(jié)果可以提供多個可能的解,選擇最終的解需要研究者的主觀判斷和后續(xù)分析;

(3)不管實(shí)際數(shù)據(jù)中是否真正存在不同的類別,利用聚類分析都能得到分成若干類別的解;

(4)聚類分析的解完全依賴于研究者所選擇的聚類變量,增加或刪除一些變量對最終的解都可能產(chǎn)生實(shí)質(zhì)性的影響。

聚類分析的缺點(diǎn):

(1)不能自動發(fā)現(xiàn)分成多少個類———屬于無監(jiān)督分析方法;

(2)期望能很清楚地找到大致相等的類或細(xì)分是不現(xiàn)實(shí)的;

(3)對樣本聚類時,變量之間的關(guān)系需要研究者決定;

(4)不會自動給出一個最佳的聚類結(jié)果。

問題1:K-均值算法有哪些典型的缺陷?是否存在有效的解決方法?

提示:噪聲敏感、非凸結(jié)構(gòu),如第9章表93所示。

本章闡述的分層聚類與基于密度的算法可以克服K-均值算法的缺陷,其中分層聚類主要解決初始值選擇與敏感性高的問題,而密度聚類主要解決非凸結(jié)構(gòu)的問題,如表

10-1所示。

10.2分層聚類

分層聚類(或?qū)哟尉垲?輸出層次結(jié)構(gòu),這種結(jié)構(gòu)比K-均值聚類返回的非結(jié)構(gòu)化聚類集更具信息性。此外,分層聚類不需要預(yù)先指定聚類的數(shù)量,同時分層算法是確定性的。這些優(yōu)勢都是K-均值算法所不具備的。與K-均值算法和EM算法(Expectation_x0002_Maximizationalgorithm,最大期望算法)的線性復(fù)雜度相比,最常見的層次聚類算法具有至少O(N2)的復(fù)雜度,也就是說,分層聚類的這些優(yōu)點(diǎn)以降低效率為代價。

10.2.1算法流程

分層聚類法首先將每個數(shù)據(jù)對象看成一個類,計算類之間的距離(如何計算類之間的距離將在10.2.2節(jié)中進(jìn)行詳細(xì)描述),每次將距離最近的數(shù)據(jù)對象合并成一個類。然后,計算類與類之間的距離,將距離最近的類歸并為一個大類。不停地合并,直到合成一個類,如圖10-1所示,每次歸并兩個點(diǎn),直到所有的數(shù)據(jù)點(diǎn)都隸屬于一個組。圖10-1分層聚類通過不斷歸并(劃分)數(shù)據(jù)進(jìn)行聚類

分層聚類法基本上有兩種:聚集法和分割法。聚集法首先將所有的研究對象都各自算作一類,將最“靠近”的類首先進(jìn)行聚類,再將這個類和其他類中最“靠近”類的結(jié)合,這樣繼續(xù)合并直至所有對象都綜合成一類或滿足某個給定閾值條件為止。分割法正好相反,它首先將所有對象看成一大類,然后分割成兩類,使一類中的對象盡可能地“遠(yuǎn)離”另一類的對象,再將每一類繼續(xù)這樣分割下去,直至每個對象都自成一類或滿足一個閾值條件為止。

基于聚合的分層聚類算法更加通用,也是本書介紹的重點(diǎn),其關(guān)鍵技術(shù)是如何通過層次樹結(jié)構(gòu)將數(shù)據(jù)歸并/劃分過程記錄下來,形成系統(tǒng)樹(Dendrogram),如圖10-2所示?？梢?樹狀結(jié)構(gòu)更加直觀與清晰。圖10-2系統(tǒng)樹的兩種形式

10.2.2集合距離計算

問題2:K-均值算法用數(shù)據(jù)對象之間的距離刻畫相似性,分層聚類法用什么方法呢?

分層聚類的重點(diǎn)在于如何計算數(shù)據(jù)對象集合之間的相似性。給定兩個集合C1與C2,如何度量這兩個集合之間的相似性?其難點(diǎn)在于如何定義集合之間的相似性,集合由數(shù)據(jù)對象構(gòu)建,其相似性可基于數(shù)據(jù)相似性,如圖10-3所示。圖10-3集合之間相似性的計算

定義集合之間的相似性的原則是:集合相似性基于集合中數(shù)據(jù)對象之間的相似性。因此,典型的集合相似性包括最近距離、最遠(yuǎn)距離、平均距離。

1.最近距離

最近距離也稱為單鏈距離(SingleLinkage),其計算方法是將兩個組合數(shù)據(jù)點(diǎn)中距離最近的兩個數(shù)據(jù)點(diǎn)間的距離作為這兩個組合數(shù)據(jù)點(diǎn)的距離,這種方法容易受到極端值的影響,兩個非常相似的組合數(shù)據(jù)點(diǎn)可能由于其中的某個極端的數(shù)據(jù)點(diǎn)距離較近而組合在一起,如圖10-4所示。圖10-4基于最近距離的集合相似性

2.最遠(yuǎn)距離

最遠(yuǎn)距離也稱為全鏈距離(CompleteLinkage),其計算方法與最短距離的不同,它將兩個組合數(shù)據(jù)點(diǎn)中距離最遠(yuǎn)的兩個數(shù)據(jù)點(diǎn)間的距離作為這兩個組合數(shù)據(jù)點(diǎn)的距離。最遠(yuǎn)距離的問題與最近距離的相反,兩個不相似的組合數(shù)據(jù)點(diǎn)可能由于其中的極端值距離較遠(yuǎn)而無法組合在一起,如圖10-5所示。圖10-5基于最遠(yuǎn)距離的集合相似性

3.平均距離

平均距離(AverageLinkage)的計算方法是計算兩個組合數(shù)據(jù)點(diǎn)中的每個數(shù)據(jù)點(diǎn)與其他所有數(shù)據(jù)點(diǎn)的距離,將所有距離的均值作為兩個組合數(shù)據(jù)點(diǎn)間的距離,如圖10-6所示。這種方法的計算量比較大,但其結(jié)果比前兩種方法的更合理。圖10-6基于平均距離的集合相似性

問題3:三種集合相似性計算的優(yōu)缺點(diǎn)是什么?

提示:從定義、準(zhǔn)確性、穩(wěn)定性等方面進(jìn)行分析。

(1)單鏈、全鏈方式的優(yōu)勢在于計算過程簡單,缺點(diǎn)是不夠穩(wěn)定,僅利用了局部信息;

(2)平均距離方法的優(yōu)勢在于相對穩(wěn)定,利用了集合中的全局信息,缺點(diǎn)是計算相對復(fù)雜。

現(xiàn)舉例說明分層聚類法的操作過程。給定5個樣本的集合,樣本之間的歐氏距離由如下矩陣D表示,采用最小距離作為類間距離,并設(shè)定最終類別個數(shù)為1,即將所有樣本聚為一類作為終止條件。

問題4:相較于K-均值算法,分層聚類法的優(yōu)勢是什么?

提示:從噪聲、準(zhǔn)確性、穩(wěn)定性等方面進(jìn)行分析,如表10-2所示。

通過對比可知:

①分層聚類法可以有效解決噪聲、聚類數(shù)等問題。

②分層聚類法的時間復(fù)雜度高。具體來說,K-均值算法的時間復(fù)雜度接近線性,而分層聚類法的時間復(fù)雜度是二次方。

③K-均值算法與分層聚類法都不能對非凸聚類進(jìn)行準(zhǔn)確的分析。

10.3分層聚類的實(shí)現(xiàn)

這里我們選用SPSS數(shù)據(jù)管理軟件實(shí)現(xiàn)分層聚類,選用的數(shù)據(jù)集為一組有關(guān)12盎司啤酒成分和價格的數(shù)據(jù),變量包括name(啤酒名稱)、calories(熱量卡路里)、sodium(鈉含量)、alcohol(酒精含量)以及cost(價格)。

其具體步驟如下:

(1)將數(shù)據(jù)導(dǎo)入軟件中,如圖10-7所示。

(2)依次單擊Analyze→Classify→HierarchicalCluster...選項,打開分層聚類對話框,如圖10-8所示。

(3)在“HierarchicalClusterAnalysis”對話框中,將用于聚類的變量calories、sodium、alcohol、cost放入“Variables”文本框中;將“name”放入LabelCasesby標(biāo)簽中,使得每一

條數(shù)據(jù)用name的值命名;在“Cluster”一欄中選擇“Cases”對樣本進(jìn)行聚類,即對啤酒進(jìn)行聚類;在“Display”一欄中選擇需要展示的輸出結(jié)果,如圖10-9所示。圖10-7將數(shù)據(jù)導(dǎo)入軟件中圖10-8打開分層聚類對話框

圖10-9設(shè)置各項參數(shù)

(4)單擊“Statistics...”按鈕,進(jìn)入Statistics對話框,選擇要求輸出的統(tǒng)計量,選中“Agglomerationschedule”復(fù)選框,顯示聚類過程中每一步合并的類或觀測量,如圖10-10所示。然后單擊“Continue”按鈕,返回“HierarchicalClusterAnalysis”對話框。圖10-10-Statics對話框

(5)單擊“Plots...”按鈕,進(jìn)入Plots對話框,選中“Dendrogram”復(fù)選框,選擇輸出樹狀圖,如圖10-11所示。然后單擊“Continue”按鈕,返回“HierarchicalClusterAnalysis”

對話框。圖10-11Plots對話框

(6)單擊“Method...”,按鈕進(jìn)入Method對話框確定聚類方法,單擊“ClusterMethod”下拉列表框中的下箭頭按鈕,展開方法選擇菜單,選擇“Between-groupslinkage”組間連接

選項,即類平均法;點(diǎn)擊“Measure”文本框內(nèi)“Interval”下拉列表框中的下箭頭按鈕,展開距離測度選擇菜單,選擇決定是否合并兩類的距離測度,這里選擇“SquaredEuclideandistance”選項,即歐氏距離平方,如圖10-12所示。然后單擊“Continue”按鈕返回“HierarchicalClusterAnalysis”對話框。圖10-12Method對話框

(7)單擊“OK”按鈕,得到層次聚類聚集狀態(tài)圖和表示層次聚類過程的樹狀圖,如圖10-13、圖10-14所示。

圖10-13層次聚類聚集狀態(tài)圖圖10-14層次聚類過程的樹狀圖

10.4密度聚類

分層聚類可克服K-均值算法的部分缺陷,但是K-均值算法與分層聚類算法都不能有效解決的問題是:在非凸簇結(jié)構(gòu)條件下,兩類算法的效果不佳。密度聚類又稱“基于密度的聚類”,此類算法假設(shè)聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定。

密度聚類算法的優(yōu)點(diǎn):

(1)聚類速度快,且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類;

(2)與K-均值算法相比,不需要輸入需要劃分的聚類個數(shù);

(3)聚類簇的形狀沒有偏倚;

(4)可以在需要時輸入過濾噪聲的參數(shù)。

密度聚類算法的缺點(diǎn):

(1)當(dāng)數(shù)據(jù)量增大時,要求較大的內(nèi)存支持,I/O消耗也很大;

(2)當(dāng)空間聚類的密度不均勻、聚類間距差相差很大時,聚類質(zhì)量較差,因?yàn)檫@種情況下參數(shù)“MinPts”和“Eps”選取困難。

(3)算法聚類效果依賴于距離公式的選取,實(shí)際應(yīng)用中常用歐氏距離;對于高維數(shù)據(jù),存在“維數(shù)災(zāi)難”。

10.4.1類密度

DBSCAN算法基于一組“鄰域”參數(shù)(ε,MinPts)來刻畫樣本分布的緊密程度,對數(shù)據(jù)點(diǎn)進(jìn)行分類,包括核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)。給定數(shù)據(jù)集D={x1,x2,…,xn},定義如下:

(1)Eps鄰域:給定對象半徑Eps內(nèi)的鄰域,稱為該對象的Eps鄰域,即對xj∈D,其Eps鄰域包含樣本集D中與xj的距離不大于ε的樣本,即Nε(xj)={xjεD|dist(xi,xj)≤ε};

(2)核心點(diǎn)(CorePoint):如果某個數(shù)據(jù)對象的Eps鄰域至少包含最小數(shù)目MinPts的對象,則稱該對象為核心對象,即若Nε(xj)≥MinPts,則xj是一個核心對象;

(3)邊界點(diǎn)(EdgePoint):不是核心點(diǎn),它落在某個核心點(diǎn)的Eps鄰域內(nèi),其Eps鄰域內(nèi)包含對象的數(shù)量小于MinPts,即若xi位于xj

的Eps鄰域中,xj

是核心點(diǎn),|Nε(xi)|<MinPts,則xi為邊界點(diǎn);

(4)噪聲點(diǎn)(OutlierPoint):既不是核心點(diǎn),也不是邊界點(diǎn)的任何點(diǎn)。

數(shù)據(jù)點(diǎn)分類如圖10-15所示,數(shù)據(jù)點(diǎn)的分類取決于參數(shù)MinPts和Eps。圖10-15DBSCAN算法數(shù)據(jù)點(diǎn)分類情況示意圖圖10-16DBSCAN算法數(shù)據(jù)對象之間的關(guān)系示意圖

10.4.2算法過程

1.時間復(fù)雜度

DBSCAN的基本時間復(fù)雜度是O(N*找出Eps鄰域中的點(diǎn)所需要的時間),N是點(diǎn)的個數(shù)。在低維空間數(shù)據(jù)中最壞情況下,時間復(fù)雜度是O(N2)。在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹(K-DimensionalTree),使得可以有效檢索特定點(diǎn)給定距離內(nèi)的所有點(diǎn),時間復(fù)雜度可以降低到O(NlgN)。

2.空間復(fù)雜度

在低維和高維數(shù)據(jù)中,其空間復(fù)雜度都是O(N),對于每個點(diǎn),DBSCAN只需要維持少量數(shù)據(jù),即簇標(biāo)號和每個點(diǎn)的標(biāo)識(核心點(diǎn)或邊界點(diǎn),或噪聲點(diǎn))。

3.參數(shù)設(shè)置

DBSCAN共包括3個輸入數(shù)據(jù):

①數(shù)據(jù)集D;

②鄰域半徑Eps;

③給定點(diǎn)在鄰域內(nèi)成為核心對象的最小鄰域點(diǎn)數(shù)MinPts。其中,Eps和MinPts要根據(jù)具體應(yīng)用人為設(shè)定。

例如,選擇與圖95中相同的數(shù)據(jù)集,采用DBSCAN算法對數(shù)據(jù)點(diǎn)進(jìn)行聚類。取k=4,可得到如圖10-17所示的結(jié)果。

圖10-17為樣本數(shù)據(jù)的K-距離圖。由圖可以看出,第一個谷值點(diǎn)位置對應(yīng)的K-距離值為0.8,則設(shè)定參數(shù)Eps為0.8,相應(yīng)地,設(shè)置參數(shù)MinPts為4。由圖10-18可以看出,使用參數(shù)(Eps=0.8,MinPts=4),DBSCAN算法可以得到很好的聚類結(jié)果,而采用參數(shù)(Eps=0.5,MinPts=4)和(Eps=3,MinPts=4)不能得到有效的聚類劃分?？梢?過小的Eps參數(shù)使得應(yīng)屬于同一聚類的數(shù)據(jù)被劃分為多個聚類,過大的Eps參數(shù)使得所有數(shù)據(jù)被聚為一類。圖10-17樣本數(shù)據(jù)的K-距離圖圖10-18樣本數(shù)據(jù)

10.5聚類結(jié)果評估

聚類效果的好壞會直接影響聚類的效果。大體上,有兩類指標(biāo)用以衡量聚類效果的好壞,一類是外部聚類效果,另一類是內(nèi)部聚類效果。聚類分析的目標(biāo)是:簇內(nèi)數(shù)據(jù)對象高度相似、簇間數(shù)據(jù)對象高度分離,即得到內(nèi)緊外松的結(jié)構(gòu),如圖10-19所示。圖10-19聚類分析的目標(biāo)是得到內(nèi)緊外松的結(jié)構(gòu)

聚類性能度量大致分為兩類,一類是將簇結(jié)果與某個參考模型進(jìn)行比較,稱為“外部指標(biāo)”;另一類是直接考察聚類結(jié)果,而不利用任何參考模型,稱為“內(nèi)部指標(biāo)”。

此外,根據(jù)簇的內(nèi)部緊湊性、外部分離性,常見的聚類性能度量的內(nèi)部指標(biāo)還有WSS(WithinSumofSquares)和BSS(BetweenSumofSquares),分別定義為

式中:mi

表示第i個聚類Ci的中心點(diǎn);m表示所有數(shù)據(jù)的中心點(diǎn)。WSS越小,說明簇內(nèi)內(nèi)容相似性越高;BSS越大,說明簇間內(nèi)容相似性越低。因此,最小化WSS、最大化BSS,也是常用的聚類性能度量的內(nèi)部指標(biāo)。

10.6聚類算法對比

10.6.1K-均值算法K-均值算法的原理可簡單理解為:假設(shè)有一堆散點(diǎn)需要聚類,想要的聚類效果就是“類內(nèi)的點(diǎn)都足夠近,類間的點(diǎn)都足夠遠(yuǎn)”。首先要確定這堆散點(diǎn)最后聚成幾類,然后挑選幾個點(diǎn)作為初始中心點(diǎn),再依據(jù)啟發(fā)式算法(HeuristicAlgorithms)給數(shù)據(jù)點(diǎn)做迭代重置(IterativeRelocation),直到最后達(dá)到“類內(nèi)的點(diǎn)都足夠近,類間的點(diǎn)都足夠遠(yuǎn)”的目標(biāo)。

優(yōu)點(diǎn):

(1)簡單,易于理解和實(shí)現(xiàn);

(2)時間復(fù)雜度低。

缺點(diǎn):

(1)需要手工輸入類數(shù)目,對初始值的設(shè)置很敏感,所以有了K-means++、intelligentK-means、geneticK-means算法;

(2)對噪聲和離群值非常敏感,所以有了K-medoids和K-medians算法;

(3)只適用于數(shù)值類型數(shù)據(jù),不適用于分類類型數(shù)據(jù),所以有了K-modes算法;

(4)不能解決非凸(Non-convex)數(shù)據(jù),所以有了核K-means算法;

(5)主要發(fā)現(xiàn)圓形或者球形簇,不能識別非球形的簇。

10.6.2分層聚類

分層聚類算法先計算樣本之間的距離,每次將距離最近的點(diǎn)合并到同一個類;然后計算類與類之間的距離,將距離最近的類合并為一個大類;不停地合并,直到合成了一個類。

其優(yōu)、缺點(diǎn)如下:

優(yōu)點(diǎn):

(1)距離和規(guī)則的相似度容易定義,限制少;

(2)不需要預(yù)先制訂聚類數(shù);

(3)可以發(fā)現(xiàn)類的層次關(guān)系;

(4)可以聚類成其他形狀。

缺點(diǎn):

(1)計算復(fù)雜度太高;

(2)奇異值對聚類也能產(chǎn)生很大的影響;

(3)算法很可能聚類成鏈狀。

10.6.3DBSCAN算法

DBSCAN算法基于密度,對于集中區(qū)域效果較好。為了發(fā)現(xiàn)任意形狀的簇,該算法將簇看作數(shù)據(jù)空間中被低密度區(qū)域分割開的稠密對象區(qū)域,是一種基于高密度連通區(qū)域密度的聚類方法