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

第9章聚類分析Ⅰ:概念與K-均值算法9.1引言9.2聚類流程與方法9.3K-均值算法9.4K-均值算法的拓展9.5圖像分割的應(yīng)用本章小結(jié)

9.1引言

聚類分析是將物理或抽象對(duì)象的集合進(jìn)行分組的過(guò)程,其中每一組中的對(duì)象具有高度的相似性。聚類分析也是一種重要的人類行為,可輔助人類的生產(chǎn)、生活。聚類源于很多領(lǐng)域,包括數(shù)學(xué)、計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)、生物學(xué)和經(jīng)濟(jì)學(xué)等。在不同的應(yīng)用領(lǐng)域,很多聚類技術(shù)都得到了發(fā)展,這些技術(shù)方法被用于描述數(shù)據(jù)、衡量不同數(shù)據(jù)源間的相似性,以及把數(shù)據(jù)源分類到不同的簇中,如圖9-1所示。圖9-1聚類分析

問題:聚類與分類的區(qū)別是什么?

提示:從目標(biāo)、數(shù)據(jù)、模式等方面考慮。

從統(tǒng)計(jì)學(xué)的觀點(diǎn)來(lái)看,聚類分析是通過(guò)數(shù)據(jù)建模從而簡(jiǎn)化數(shù)據(jù)的一種方法。傳統(tǒng)的統(tǒng)計(jì)聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動(dòng)態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。采用K-均值、K-中心點(diǎn)等算法的聚類分析工具已被加入到許多著名的統(tǒng)計(jì)分析軟件包中,如SPSS、SAS等。

聚類分析是一種探索性的分析,在分類的過(guò)程中,人們不必事先給出一個(gè)分類的標(biāo)準(zhǔn),聚類分析能夠從樣本數(shù)據(jù)出發(fā),自動(dòng)進(jìn)行分類。聚類分析由所使用方法的不同,常常會(huì)得到不同的結(jié)論。不同研究者對(duì)于同一組數(shù)據(jù)進(jìn)行聚類分析,所得到的聚類結(jié)果未必一致。

從實(shí)際應(yīng)用的角度來(lái)看,聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。

分類與聚類的區(qū)分歸納為如下幾點(diǎn),如表9-1所示。

基于上述分析,給定聚類分析定義如下:

聚類依據(jù)研究對(duì)象(樣品或指標(biāo))的特征對(duì)其進(jìn)行分類,從而減少研究對(duì)象的數(shù)目。由于很多事物缺乏可靠的歷史資料,無(wú)法確定共有多少類別,而聚類的目的是將性質(zhì)相近的事物/對(duì)象歸入一個(gè)組/簇。

定義9.1(聚類分析ClusteringAnalysis)將一組研究對(duì)象分為相對(duì)同質(zhì)的群組(Clusters)的統(tǒng)計(jì)分析技術(shù)。

聚類分析已經(jīng)廣泛運(yùn)用于各行各業(yè),包括:

(1)商業(yè):聚類分析被用來(lái)發(fā)現(xiàn)不同的客戶群,并且通過(guò)購(gòu)買模式刻畫不同客戶群的特征。

(2)生物醫(yī)學(xué):聚類分析被用來(lái)對(duì)動(dòng)植物和基因進(jìn)行分類,獲取對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí),利用聚類分析挖掘致癌基因等。

(3)地理:聚類能夠幫助判別在地球中被觀察對(duì)象的相似性。

(4)保險(xiǎn)行業(yè):聚類分析通過(guò)平均消費(fèi)的高低來(lái)鑒定汽車保險(xiǎn)單持有者的分組,同時(shí)根據(jù)住宅類型、價(jià)值、地理位置來(lái)鑒定一個(gè)城市的房產(chǎn)分組。

(5)因特網(wǎng):聚類分析被用來(lái)在網(wǎng)上進(jìn)行文檔歸類來(lái)修復(fù)信息。

(6)電子商務(wù):聚類分析也是電子商務(wù)網(wǎng)站建設(shè)數(shù)據(jù)挖掘中很重要的一個(gè)方面,通過(guò)分組聚類出具有相似瀏覽行為的客戶,并分析客戶的共同特征,可以更好地幫助電子商務(wù)的用戶了解自己的客戶,向客戶提供更合適的服務(wù)。

9.2聚類流程與方法

9.2.1聚類流程典型的聚類分析流程如圖9-2所示,主要包括四個(gè)過(guò)程:數(shù)據(jù)預(yù)處理、數(shù)據(jù)相似度度量、聚類策略的選擇、聚類結(jié)果評(píng)估。圖9-2聚類分析的基本流程

1.數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理包括數(shù)據(jù)類型選擇、特征標(biāo)度刻畫等,主要依靠特征選擇和特征抽取。其中,特征選擇是選擇重要的特征,特征抽取是把輸入的特征轉(zhuǎn)化為一個(gè)新的顯著特征,它們經(jīng)常被用來(lái)獲取一個(gè)合適的特征集,從而避免“維數(shù)災(zāi)難”。數(shù)據(jù)預(yù)處理還包括將孤立點(diǎn)移出數(shù)據(jù)。由于孤立點(diǎn)是不依附于一般數(shù)據(jù)行為或模型的數(shù)據(jù),它經(jīng)常會(huì)導(dǎo)致有偏差的聚類結(jié)果,因此為了得到正確的聚類,必須將它們剔除。

2.數(shù)據(jù)相似度度量

既然相似性是定義一個(gè)簇的基礎(chǔ),那么同一個(gè)特征空間中不同數(shù)據(jù)之間相似度的衡量對(duì)于聚類極為重要。由于特征類型和特征標(biāo)度的多樣性,距離度量的選擇必須謹(jǐn)慎,它經(jīng)常依賴于應(yīng)用。

若函數(shù)dist(·,·)是一個(gè)“距離度量”,則需要滿足一些基本性質(zhì):

(1)非負(fù)性:dist(xi,xj)≥0;

(2)統(tǒng)一性:dist(xi,xj)=0,當(dāng)且僅當(dāng)xi=xj;

(3)對(duì)稱性:dist(xi,xj)=dist(xj,xi);

(4)直遞性(三角不等式):dist(xi,xj)≤dist(xi

,xk)+dist(xk,xj

)。

假定每個(gè)樣本有p個(gè)變量,則每個(gè)樣本都可以看成p維空間中的一個(gè)點(diǎn),n個(gè)樣本就是p維空間中的n個(gè)點(diǎn),將第i個(gè)樣本與第j個(gè)樣本之間的距離記為dij。典型的距離函數(shù)包括:

(3)馬氏(Mahalanobis)距離函數(shù),其表達(dá)式為

3.聚類策略的選擇

將數(shù)據(jù)對(duì)象分到不同的類/簇是聚類分析的最終目標(biāo),而劃分方法和層次方法是聚類分析的主要方法。其中,劃分方法一般從初始劃分和最優(yōu)化一個(gè)聚類標(biāo)準(zhǔn)開始,而層次方法則利用相似性構(gòu)建樹結(jié)構(gòu)進(jìn)行聚類。硬聚類(CrispClustering或HardClustering)中每一個(gè)數(shù)據(jù)對(duì)象屬于且僅屬于某一個(gè)類,軟聚類(FuzzyClustering或SoftClustering)中每個(gè)數(shù)據(jù)對(duì)象可以隸屬一個(gè)或多個(gè)類;硬聚類與軟聚類分別對(duì)應(yīng)集合的劃分與覆蓋問題。

4.聚類結(jié)果評(píng)估

聚類結(jié)果的質(zhì)量評(píng)估是聚類分析中極為重要的內(nèi)容之一。聚類是一個(gè)無(wú)管理的程序,也沒有客觀的標(biāo)準(zhǔn)來(lái)評(píng)價(jià)聚類結(jié)果。一般來(lái)說(shuō),利用類/簇的幾何性質(zhì)來(lái)評(píng)估聚類結(jié)果,包括類間的分離和類內(nèi)部的耦合。也可通過(guò)預(yù)先定義的函數(shù)對(duì)聚類結(jié)果進(jìn)行評(píng)估,如方差等。如果在有先驗(yàn)的專家知識(shí)的情況下,可利用專家知識(shí)引導(dǎo)評(píng)估等。

9.2.2聚類方法

聚類分析是數(shù)據(jù)挖掘中一個(gè)很活躍的研究領(lǐng)域,目前已經(jīng)提出了許多聚類算法。傳統(tǒng)的聚類算法可以分為五類:劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基

于模型的方法。

1.劃分方法(PartitioningMethod,PAM)

劃分方法的步驟為:首先創(chuàng)建k個(gè)劃分,k為要?jiǎng)?chuàng)建的劃分個(gè)數(shù);然后利用循環(huán)定位技術(shù)通過(guò)將對(duì)象從一個(gè)劃分移到另一個(gè)劃分來(lái)幫助改善劃分質(zhì)量。

2.層次方法

層次方法是(HierarchicalMethod)創(chuàng)建一個(gè)層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下(分解)和自下而上(合并)兩種操作方式。為彌補(bǔ)分解與合并的不足,層次方法經(jīng)常要與其他聚類方法相結(jié)合,如循環(huán)定位法。典型的層次分類方法包括:(1)BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)方法。

(2)CURE(ClusteringUsingREpresentatives)方法。

(3)ROCK方法。該方法利用聚類間的連接進(jìn)行聚類合并。

(4)CHEMALOEN(變色龍,是一個(gè)利用動(dòng)態(tài)模型的層次聚類算法)方法。

3.基于密度的方法

該方法根據(jù)密度完成對(duì)象的聚類,并根據(jù)對(duì)象周圍的密度不斷增長(zhǎng)聚類。典型的基于密度的方法包括:

(1)DBSCAN,該方法通過(guò)不斷生長(zhǎng)足夠高的密度區(qū)域來(lái)進(jìn)行聚類,它能從含有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類,并將一個(gè)聚類定義為一組“密度連接”的點(diǎn)集。

(2)OPTICS算法不顯式地生成數(shù)據(jù)聚類,它只是對(duì)數(shù)據(jù)對(duì)象集合中的對(duì)象進(jìn)行排序,得到一個(gè)有序的對(duì)象列表,其中包含了足夠的信息用來(lái)提取聚類。

4.基于網(wǎng)格的方法

基于網(wǎng)格的方法(Grid-BasedMethods)首先將對(duì)象空間劃分為有限個(gè)單元以構(gòu)成網(wǎng)格結(jié)構(gòu),然后利用網(wǎng)格結(jié)構(gòu)完成聚類。STING是一個(gè)利用網(wǎng)格單元保存的統(tǒng)計(jì)信息進(jìn)行基于網(wǎng)格聚類的方法。此外,CLIQUE(ClusteringinQuest)和

Wave-Cluster是將基于網(wǎng)格與基于密度相結(jié)合的方法。

5.基于模型的方法

基于模型的方法為每個(gè)簇假定了一個(gè)模型,尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。一個(gè)基于模型的算法可能通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)定位聚類?；谀Ｐ偷乃惴?/p>

也基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)據(jù)自動(dòng)決定聚類的數(shù)目,考慮“噪聲”數(shù)據(jù)或孤立點(diǎn),從而產(chǎn)生穩(wěn)健的聚類方法。典型的基于模型的方法(Model-BasedMethods)包括:

(1)統(tǒng)計(jì)方法COBWEB,它是一個(gè)常用的且簡(jiǎn)單的增量式概念聚類方法。

(2)CLASSIT方法,它是COBWEB的另一個(gè)版本,可以對(duì)連續(xù)取值屬性進(jìn)行增量式聚類。

9.3K-均值算法

K-均值(K-means)算法是一種使用最廣泛的聚類算法,它將各個(gè)聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點(diǎn)。該算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類別,使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu),從而使生成的每個(gè)聚類類內(nèi)緊湊。

9.3.1算法的三大要素

聚類的目標(biāo)是將數(shù)據(jù)對(duì)象分配到不同的聚類中,以使得類間相對(duì)松散、類內(nèi)相對(duì)緊湊。如圖9-3所示,每個(gè)數(shù)據(jù)對(duì)象用一個(gè)點(diǎn)表示,同類數(shù)據(jù)對(duì)象用相同形狀標(biāo)記。圖9-3K-均值算法挖掘不同的簇/分組

1.相似性函數(shù)

K-均值聚類算法不適于處理離散型屬性,適合處理連續(xù)型屬性。因此在計(jì)算數(shù)據(jù)樣本之間的距離時(shí),可以根據(jù)實(shí)際需要選擇歐氏距離、曼哈頓距離或者明考斯距離中的一種作為算法的相似性度量,其中最常用的是歐氏距離。

由9.2節(jié)數(shù)據(jù)相似性內(nèi)容可知,典型的相似性函數(shù)有:

2.選擇評(píng)價(jià)聚類性能準(zhǔn)則函數(shù)

K-均值聚類算法使用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類性能。給定數(shù)據(jù)集X,其中只包含描述屬性,不包含類別屬性。假設(shè)X包含k個(gè)聚類子集X1,X2,…,Xk,各個(gè)聚類子集的均值代表點(diǎn)(也稱聚類中心)分別為m1,m2,…,mk,則誤差平方和準(zhǔn)則函數(shù)公式為

3.數(shù)據(jù)對(duì)象如何分組

計(jì)算每個(gè)簇的平均值,并用該平均值代表相應(yīng)的簇。根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離,分配給最近的簇。

綜上可知,K-均值算法三大要素包括目標(biāo)函數(shù)、相似性與分組原則。

9.3.2算法的流程

算法過(guò)程示意圖如圖9-4所示,首先隨機(jī)選定k個(gè)數(shù)據(jù)點(diǎn)作為初始的聚類中心,計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到聚類中心的距離;然后把數(shù)據(jù)對(duì)象賦給最近的中心所對(duì)應(yīng)的類/簇,重新計(jì)算簇中心,重新分組,一直迭代,直到算法終止。圖9-4K-均值算法過(guò)程示意圖圖9-4K-均值算法過(guò)程示意圖

例如,數(shù)據(jù)對(duì)象集合S如表9-2所示,作為一個(gè)聚類分析的二維樣本,要求的簇的數(shù)量k=2。

9.3.3算法的性能分析

K-均值算法的優(yōu)缺點(diǎn)總結(jié)如表9-3所示。圖9-5K-均值算法不能對(duì)非凸數(shù)據(jù)進(jìn)行聚類圖9-6聚類密度對(duì)K-均值算法性能的影響較大

9.4K-均值算法的拓展

由于K-均值算法存在相應(yīng)的缺陷,因此如何有效解決這些問題就成為了關(guān)鍵。針對(duì)K-均值算法對(duì)于不同的初始值,可能會(huì)導(dǎo)致不同的結(jié)果,解決方法有:(1)多設(shè)置一些不同的初值,對(duì)比最后的運(yùn)算結(jié)果,一直到結(jié)果趨于穩(wěn)定結(jié)束。這種方法比較耗時(shí),也浪費(fèi)資源。(2)很多時(shí)候,事先并不知道數(shù)據(jù)集的聚類數(shù),這也是K-均值算法的一個(gè)不足。

ISODATA算法的流程如下:

K-均值算法其他的改進(jìn)方式:

(1)K-modes算法:實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類,保留了K-均值算法的效率,同時(shí)將K-均值算法的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。它是按照K-均值算法的核心內(nèi)容進(jìn)行修改,針對(duì)分類屬性的度量和更新質(zhì)心的問題而改進(jìn)的。K-modes算法具體如下:①度量記錄之間的相關(guān)性D的計(jì)算公式是,比較兩記錄之間的關(guān)系,屬性相同為0,不同為1,并將所有關(guān)系相加。因此D越大,數(shù)據(jù)的不相關(guān)程度越強(qiáng)(與歐氏距離代表的意義是一樣的)。②更新modes,使用一個(gè)簇的每個(gè)屬性出現(xiàn)頻率最高的那個(gè)屬性值作為代表簇的屬性值。

(2)K-prototype算法:可以對(duì)離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類。在K-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。K-prototype算法

結(jié)合了K-均值算法與K-modes算法,針對(duì)混合屬性解決了兩個(gè)核心問題:①度量具有混合屬性的方法是,數(shù)值屬性采用K-均值算法得到P1,分類屬性采用K-modes方法得到P2,則D=P1+aP2,其中a是權(quán)重。如果認(rèn)為分類屬性重要,則增加a,否則減少a。當(dāng)a=0時(shí),只有數(shù)值屬性。②更新一個(gè)簇中心的方法是結(jié)合K-均值算法與K-modes算法。

(3)K-中心點(diǎn)算法:K-均值算法對(duì)于孤立點(diǎn)是敏感的,為了解決這個(gè)問題,不采用簇中的平均值作為參照點(diǎn),可以選用簇中位置最中心的對(duì)象(中心點(diǎn))作為參照點(diǎn)。這種劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和來(lái)執(zhí)行的。

9.5圖像分割的應(yīng)用

圖9-7所示為一條狗、一輛自行車以及街道、樹木和汽車。使用K-均值算法對(duì)圖像進(jìn)行分割,將圖像分割為合適的背景區(qū)域(自行車、街道、樹木及汽車)和前景區(qū)域(狗)。圖9-8所示為一匹斑馬、草地。使用K-均值算法對(duì)圖像進(jìn)行分割,將圖像分割為合適的背景區(qū)域(草地)和前景區(qū)域(斑馬)。圖9-7K-均值算法應(yīng)用于圖像分割前后圖9-8K-均值算法應(yīng)用于圖像分割前后(聚類中心個(gè)數(shù)為3,最大迭代次數(shù)為10)

本章小結(jié)

聚類分析是無(wú)監(jiān)督學(xué)習(xí)中一項(xiàng)重要的研究課題,本章主要講述了聚類分析的背景、定義及其基本分類方法,重點(diǎn)闡述了聚類分析的過(guò)程、K-均值算法的原理與過(guò)程、K-均值算法的優(yōu)缺點(diǎn)及其在圖像中的應(yīng)用。本章回答了如下幾個(gè)問題:

(1)為什么要進(jìn)行聚類分析?

數(shù)據(jù)無(wú)標(biāo)簽。

(2)聚類分析的基本過(guò)程是什么?

四大過(guò)程:數(shù)據(jù)預(yù)處理、相似度度量、聚類策略的選擇、聚類結(jié)果評(píng)估。

(3)K-