王玉晗 羅鄧三郎

摘 要：在數(shù)據(jù)挖掘中，聚類有著非常重要的地位。本文分別介紹了基于劃分、基于層次、基于密度、基于網(wǎng)格和基于模型的聚類方法。對(duì)這五類聚類方法中的典型算法的聚類思想和特點(diǎn)做了相應(yīng)的介紹，并分析了算法的優(yōu)缺點(diǎn)，對(duì)聚類算法做了初步的總結(jié)。在具體問(wèn)題的應(yīng)用中，需多方面考慮算法的特性才能得到最佳聚類結(jié)果。

關(guān)鍵詞：數(shù)據(jù)挖掘 聚類 密度 模型

中圖分類號(hào)：G71 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2018）08（c）-0010-02

隨著科技的發(fā)展，目前已步入大數(shù)據(jù)的時(shí)代，數(shù)據(jù)中包含的信息具有很高的價(jià)值。通過(guò)聚類分析，數(shù)據(jù)對(duì)象被劃分為具有現(xiàn)實(shí)意義的組（集群），有助于人類分析和描述世界。聚類分析在心理學(xué)研究中、生物學(xué)研究中和模式識(shí)別以及數(shù)據(jù)挖掘等領(lǐng)域中都起著重要的作用。

聚類分析僅通過(guò)描述對(duì)象和其關(guān)系的數(shù)據(jù)信息，期望將對(duì)象劃分為多個(gè)組，使得組內(nèi)對(duì)象相似，組間對(duì)象不同。聚類的定義最早由Everitt在1974年提出，要求組內(nèi)對(duì)象在空間中相對(duì)緊湊，組內(nèi)任意兩對(duì)象間的距離小于不同組的任意兩對(duì)象間的距離。在實(shí)際應(yīng)用中，聚類的定義通常不精確，最優(yōu)的定義取決于聚類對(duì)象的性質(zhì)和期望得到的結(jié)果。

根據(jù)聚類算法中對(duì)象間相似度的計(jì)算方式以及聚類結(jié)果中對(duì)象的關(guān)系可以將聚類算法分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法[1]。

1 聚類方法

1.1 基于劃分的聚類方法

基于劃分的聚類方法只是將數(shù)據(jù)對(duì)象集合劃分為若干個(gè)無(wú)交集的子集（簇），使得每個(gè)對(duì)象僅屬于一個(gè)子集。主要包括K-Means算法、K-modes算法、PAM算法和CLARA算法等。

K-Means算法是一個(gè)基于原型的劃分聚類算法，通過(guò)對(duì)象間的距離評(píng)價(jià)對(duì)象間的相似度，距離越近，對(duì)象間相似度越大，反之則越小。用戶需要預(yù)先指定需要?jiǎng)澐值拇財(cái)?shù)k和每簇質(zhì)心的初值，其思想如下：先選取k個(gè)數(shù)據(jù)作為k個(gè)簇的質(zhì)心，計(jì)算數(shù)據(jù)集中每個(gè)對(duì)象到質(zhì)心的距離，按照距離將其歸類，完成后重新計(jì)算每個(gè)簇的質(zhì)心，直到聚類結(jié)果不再發(fā)生變化為止。K-Means聚類算法的優(yōu)點(diǎn)主要為算法運(yùn)算快速且簡(jiǎn)單，對(duì)于數(shù)據(jù)較多的數(shù)據(jù)集有較高的聚類效率，具有可伸縮性。確定質(zhì)心初值的主要方法有：（1）根據(jù)數(shù)據(jù)對(duì)象的性質(zhì)和分布憑主觀經(jīng)驗(yàn)選取。（2）將數(shù)據(jù)對(duì)象隨機(jī)分成k類，把每類的重心作為質(zhì)心初值。（3）按密度大小選取質(zhì)心初值。聚類結(jié)果對(duì)質(zhì)心初值的選擇敏感，選用不同質(zhì)心初值可能得到不同的結(jié)果。數(shù)據(jù)集中的噪點(diǎn)和孤立點(diǎn)也會(huì)影響K-Means算法的聚類結(jié)果。

1.2 基于層次的聚類方法

層次聚類把數(shù)據(jù)對(duì)象構(gòu)建成一組具有樹狀結(jié)構(gòu)的嵌套簇，除了葉子節(jié)點(diǎn)的每個(gè)簇都是由其子節(jié)點(diǎn)（子簇）的并集構(gòu)成，根節(jié)點(diǎn)包含所有的數(shù)據(jù)對(duì)象。根據(jù)層次分解的過(guò)程一般分為兩類：（1）凝聚。從僅包含單個(gè)數(shù)據(jù)對(duì)象的簇開始，每次合并最接近的一對(duì)簇，直至簇中包含所有數(shù)據(jù)對(duì)象為止。（2）分裂。從一個(gè)包含所有數(shù)據(jù)對(duì)象的簇開始，每次對(duì)簇進(jìn)行分割，直至簇中僅包含一個(gè)數(shù)據(jù)對(duì)象為止。樹狀圖是層次聚類結(jié)果常用的表示方式。層次聚類方法主要包括單鏈接聚類、CURE算法、BIRCH算法和ROCK算法等。

單鏈接聚類基于自底向上方式對(duì)數(shù)據(jù)對(duì)象進(jìn)行分類，在聚類過(guò)程的開始，每個(gè)元素都在自己的簇中。然后通過(guò)最短距離將這些簇依次組合成較大的簇，直到簇中包含所有的數(shù)據(jù)對(duì)象。CURE是針對(duì)大小相似的數(shù)據(jù)集和球形數(shù)據(jù)集的一種改進(jìn)算法，其思想為一個(gè)簇由其中多個(gè)數(shù)據(jù)對(duì)象表示，每個(gè)簇對(duì)應(yīng)多于一個(gè)的對(duì)象。這種策略使得CURE算法可以適應(yīng)非球形的幾何形狀，并且能利用簇的收縮或凝聚控制孤立點(diǎn)的影響[2]。BIRCH是一種針對(duì)大規(guī)模數(shù)據(jù)集的聚類算法，通過(guò)聚類特征和聚類特征樹，利用各個(gè)簇之間的距離，通過(guò)迭代的方法對(duì)數(shù)據(jù)集進(jìn)行聚類[3]。ROCK算法是一種魯棒的聚類算法，在確認(rèn)兩個(gè)數(shù)據(jù)的分類時(shí)考慮了它們鄰居的數(shù)量，適用于類別型數(shù)據(jù)，如關(guān)鍵字、布爾值和枚舉值等。

1.3 基于密度的聚類方法

基于密度的聚類方法是根基數(shù)據(jù)集密度的大小將數(shù)據(jù)集分類成簇，密度高的區(qū)域聚類成簇，密度低的區(qū)域作為噪聲和孤立點(diǎn)處理，適用于空間中任意形狀的簇，具有很強(qiáng)的抗噪能力。DBSCAN算法是經(jīng)典的基于密度的聚類算法。其核心思想為：預(yù)先設(shè)置距離閾值和密度閾值，將數(shù)據(jù)對(duì)象都標(biāo)記為核心點(diǎn)，任意數(shù)據(jù)對(duì)象由距離閾值確定的范圍內(nèi)不存在核心點(diǎn)，則將其視為噪聲點(diǎn)消除。確定出每個(gè)距離閾值內(nèi)的所有滿足密度閾值的核心點(diǎn)的邊界點(diǎn)，并把每一組連接的核心點(diǎn)分為一個(gè)簇，最后將邊界點(diǎn)分配給相關(guān)核心點(diǎn)的簇。其優(yōu)點(diǎn)有：可以自動(dòng)確定聚類數(shù)量；對(duì)任意形狀的簇都適用；對(duì)數(shù)據(jù)異常點(diǎn)不敏感。缺點(diǎn)為需要設(shè)置距離和密度閾值，處理空間分布稀疏的數(shù)據(jù)對(duì)象時(shí)難以得到滿意的聚類結(jié)果，時(shí)間復(fù)雜度比K-Means算法高。

1.4 基于網(wǎng)格的聚類方法

基于網(wǎng)格的聚類方法把原數(shù)據(jù)對(duì)象空間劃分成獨(dú)立于輸入對(duì)象分布的單元。通過(guò)構(gòu)建父級(jí)子級(jí)網(wǎng)格單元關(guān)系形成一種多分辨率的網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，將連續(xù)空間離散化成有限數(shù)目的單元，利用所形成的網(wǎng)格結(jié)構(gòu)進(jìn)行聚類。該方法僅依賴于離散化后空間中的每一維的單元數(shù)，處理速度不受原數(shù)據(jù)大小的影響。STING是典型基于網(wǎng)格的聚類算法。在構(gòu)建的層次結(jié)構(gòu)實(shí)中，每個(gè)上層的結(jié)構(gòu)單元都在下一層被劃分為多個(gè)下層的結(jié)構(gòu)單元。在聚類時(shí)，每個(gè)網(wǎng)格單元的統(tǒng)計(jì)信息會(huì)被預(yù)先計(jì)算和儲(chǔ)存，相連高密度的網(wǎng)格單元判斷為簇。STING算法基于網(wǎng)格結(jié)構(gòu)，其算法效率高有利于增量更新和并行處理[4]，但在構(gòu)建父級(jí)單元時(shí)沒有考慮子級(jí)單元和相鄰單元之間的聯(lián)系，無(wú)法得到精確簇間邊界，同時(shí)聚類精度會(huì)受到網(wǎng)格粒度的影響，聚類精度隨粒度減小而提高，處理時(shí)間隨之增加。

1.5 基于模型的聚類方法

基于模型的聚類算法需要為數(shù)據(jù)對(duì)象中的可能存在的每一簇構(gòu)建一個(gè)分布模型，并假設(shè)數(shù)據(jù)對(duì)象均獨(dú)立分布，通過(guò)數(shù)據(jù)對(duì)象的真實(shí)分布計(jì)算模型參數(shù)，最后利用所得模型完成聚類。基于模型的方法主要包括統(tǒng)計(jì)學(xué)和網(wǎng)絡(luò)神經(jīng)方法，其中統(tǒng)計(jì)學(xué)方法有COBWEB算法；網(wǎng)絡(luò)神經(jīng)方法有SOM算法[5]?；谀Ｐ偷木垲惙椒ㄍǔＲ愿怕实男问綄?duì)簇進(jìn)行劃分，易于理解，但是算法的執(zhí)行效率并不高，同時(shí)假設(shè)條件不一定成立，對(duì)聚類結(jié)果也造成一定影響。

2 結(jié)語(yǔ)

本文介紹了基于5種聚類方法，主要介紹了其中具有代表性的算法K-Means、CURE、DBScan、STING算法和基于模型的聚類方法。分析了各類算法的特點(diǎn)和特性，對(duì)于不同的問(wèn)題應(yīng)采用不同的聚類算法。在實(shí)際應(yīng)用中，需要結(jié)合算法的優(yōu)缺點(diǎn)選擇合適的算法才能獲得理想的聚類效果。

參考文獻(xiàn)

[1] 陳建嬌.高維數(shù)據(jù)的K-harmonic Means聚類方法及其應(yīng)用研究[D].上海大學(xué)，2012.

[2] 周迎春，駱嘉偉.基于分層的平衡迭代規(guī)約聚類分析算法研究[J].科學(xué)技術(shù)與工程，2008，8（10）：2579-2584.

[3] 陳紹彬，葉飛躍，劉佰強(qiáng)，等.食品HACCP分類的BIRCH算法[J].計(jì)算機(jī)工程，2008，34（23）：59-61.

[4] 楊靜.分層模糊最小-最大聚類算法及其在圖像聚類中的應(yīng)用研究[D].合肥工業(yè)大學(xué)，2007.

[5] 冉延平，余昭平，賈利新，等.基于混合模型的聚類算法研究[J].河南科學(xué)，2005，23（3）：324-327.