陳向東

摘要：數(shù)據(jù)挖掘是從海量的數(shù)據(jù)中，發(fā)現(xiàn)隱藏的、潛在的數(shù)據(jù)規(guī)則和模式的過程；聚類算法是數(shù)據(jù)挖掘的一個重要研究方法，它按照一定的要求和規(guī)律將事物進(jìn)行分類的一種數(shù)學(xué)方法。本文針對幾種常用聚類算法，研究比較了幾種聚類算法的聚類劃分方法，探討了幾種常用聚類算法的優(yōu)缺點(diǎn)。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類劃分；聚類

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2017）04-0151-02

隨著網(wǎng)絡(luò)應(yīng)用于各個領(lǐng)域，隨之也產(chǎn)生了海量的網(wǎng)絡(luò)數(shù)據(jù)，并且這些數(shù)據(jù)是雜亂的，無規(guī)則的。對于信息數(shù)據(jù)的爆炸式的增長，而如何分析處理這些收集到的海量數(shù)據(jù)，是數(shù)據(jù)挖掘面臨的首要問題。數(shù)據(jù)挖掘（Data Mining），即是從大量的、不規(guī)則的、有噪聲的、模糊的數(shù)據(jù)中，提取隱藏在其中的、人們事先不知道的、但又潛在有用的信息和知識的過程[1]。聚類分析是數(shù)據(jù)挖掘領(lǐng)域中研究的一項(xiàng)重要課題，對于收集到的海量數(shù)據(jù)，通過聚類分析，發(fā)現(xiàn)相似數(shù)據(jù)間的知識特征，不相似數(shù)據(jù)間的數(shù)據(jù)屬性之前存在較大差異，并以此規(guī)則進(jìn)行數(shù)據(jù)分類，分類后的同類的數(shù)據(jù)對象之間的有一定的相似度，不同類的數(shù)據(jù)對象之間的相似度較小，每一組數(shù)據(jù)都是相似對象的集合，通過分析可以獲得同類數(shù)據(jù)對象的數(shù)學(xué)模型和數(shù)據(jù)特征。

1 聚類

聚類是一個將數(shù)據(jù)劃分為若干簇或類的過程，它將物理的或抽象的數(shù)據(jù)的集合分組成多個簇或類，每個簇或類中的數(shù)據(jù)特征有較高的相似性，不同的類或簇中的數(shù)據(jù)特征則不相似，這一分類過程就是聚類的過程。聚類分析就是從給定的數(shù)據(jù)集中找出同類數(shù)據(jù)對象之間的聯(lián)系，被分為同一類的數(shù)據(jù)對象，由于數(shù)據(jù)特征相同，常常被當(dāng)作一個對象來進(jìn)行分析處理，通過對不同數(shù)據(jù)集之間的分析，挖掘出潛在的，有用的數(shù)據(jù)知識模型，為用戶提供決策。對于聚類算法，很難有明確的分類標(biāo)準(zhǔn)，這些聚類方法一般具有某些類別特征。

2 聚類算法的分類

2.1 基于劃分的聚類算法

假定數(shù)據(jù)集包含n個數(shù)據(jù)對象或數(shù)據(jù)元組，要將數(shù)據(jù)集通過聚類劃分成K（K≤n）個簇或類，劃分的簇或類要滿足下列三個條件：（1）每個簇或類中包含r（r≥1）個數(shù)據(jù)對象或元組；（2）任意一個數(shù)據(jù)對象或元組只能屬于一個簇或類；（3）簇或類的劃分準(zhǔn)則是：在同一個簇或類中的數(shù)據(jù)元組特征是相似的，不同簇或類中的數(shù)據(jù)元組特征是不相似的。

基于劃分的聚類算法，依據(jù)初始數(shù)據(jù)集劃分?jǐn)?shù)目K，構(gòu)建一個初始聚類劃分，然后利用迭代重定位技術(shù)，將每個數(shù)據(jù)元組在各個聚類簇中進(jìn)行劃分，原則是：同一個劃分簇中的對象或元組數(shù)據(jù)特征相似，不同劃分簇中的對象或元組數(shù)據(jù)特征有較大的差異，通過迭代重定位，把數(shù)據(jù)集N最終劃分成了K個簇[2]。典型的基于劃分的算法有：K均值聚類和K中心點(diǎn)聚類。

2.2 層次方法

層次聚類算法是將數(shù)據(jù)對象組成一棵聚類樹，根據(jù)層次分解的方法，對數(shù)據(jù)集進(jìn)行層次分解，直到滿足某種條件為止[3]。層次聚類方法有兩種，一種是自底向上的合并方法，一種是自頂向下的分裂方法。層次聚類的方法的劣勢在于：一旦決定采用具體的分裂法或合并方法后，如果中途發(fā)現(xiàn)此種方法并不合適，則無法返回更正。常見的層次聚類方法有：BIRCH（利用層次方法的平衡迭代歸約聚類算法）、CHAMELEON（動態(tài)建模的層次聚類算法）。

2.3 基于密度的方法

基于密度的聚類劃分：給定密度閾值，如果某個區(qū)域中數(shù)據(jù)點(diǎn)的密度大于密度閾值，則數(shù)據(jù)點(diǎn)屬于相近的劃分聚類，這種劃分方法將數(shù)據(jù)集看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的大密度區(qū)域?；诿芏葎澐值姆椒ù硇缘乃惴ㄓ校篋BSCAN（基于高密度連通區(qū)域的聚類算法）、DENCLUE（基于密度分布函數(shù)的聚類算法）。

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

基于網(wǎng)格的聚類劃分方法是將數(shù)據(jù)對象空間分為若干個網(wǎng)格單元，聚類的過程就是對這些網(wǎng)格處理的過程，基于網(wǎng)格的聚類劃分的優(yōu)點(diǎn)是處理速度快，處理速度受限于量化空間中每一維的單元數(shù)目，而于網(wǎng)格單元數(shù)目無關(guān)?；诰W(wǎng)格劃分方法的典型算法有STING（統(tǒng)計(jì)信息網(wǎng)格聚類算法）和WaveCluster（小波變換聚類算法）。

2.5 基于模型的方法

基于模型的聚類方法有個假定前提：每個聚類劃分都可以構(gòu)建一個數(shù)學(xué)模型，聚類就是找到每個聚類簇相對應(yīng)的數(shù)據(jù)模型的過程。數(shù)據(jù)集潛在的假定符合一系列的概率分布，數(shù)學(xué)模型算法可能數(shù)據(jù)點(diǎn)在空間中的分布密度函數(shù)或其它。常用的有EM（期望最大化聚類算法）。

3 幾種常用的聚類算法

3.1 K-means劃分聚類算法

通常給定包含N個數(shù)據(jù)對象的數(shù)據(jù)集D，將數(shù)據(jù)集按目標(biāo)度量函數(shù)劃分成K個簇。K-means聚類算法，是采用距離作為聚類的標(biāo)準(zhǔn)，距離越近，認(rèn)為其相似度越高，聚類過程如下：

（1）隨機(jī)從數(shù)據(jù)集D中選取K個數(shù)據(jù)對象作為初始點(diǎn)，初始化K個聚類；

（2）對于余下的每個數(shù)據(jù)元組，計(jì)算它與K個劃分類中心的距離，將其歸入距離最近的劃分類中；

（3）更新類并重新計(jì)算K個類的中心點(diǎn)；

（4）repeat②，until所有聚類中心點(diǎn)不發(fā)生變化，此時(shí)對于每一個數(shù)據(jù)對象，都被分為唯一的一個聚類中。

K-means聚類算法需要用戶給定K個聚類數(shù)，并選取K個數(shù)據(jù)點(diǎn)作為初始聚類中心，如若初始聚類中心選擇不當(dāng)，就會造成聚類結(jié)果有較大偏差；K-means聚類算法迭代的目標(biāo)函數(shù)，隨機(jī)選擇的初始中心點(diǎn)，可能會導(dǎo)致聚類結(jié)果穩(wěn)定性不夠，與最優(yōu)聚類有偏差。

3.2 最近鄰層次聚類算法

層次聚類算法有凝聚層次聚類算法和分裂層次聚類算法；凝聚層次聚類算法，是把數(shù)據(jù)集合S（包含n個數(shù)據(jù)對象）劃分成K個子集C1，C2，，…，Ck，每個子集中包含中的數(shù)據(jù)具有一定的相似性，兩個子集間通常用歐幾里德最小距離度量，如子集ci與子集cj距離為d（ci，cj），其中

其中是把n個數(shù)據(jù)記錄看成m維空間中的n個對象向量，一般要求：

（1），對一切i，j；當(dāng)=0時(shí)；

（2），對一切i，j；

（3），對一切i，j，k三角不等式成立。

最近鄰層次聚類算法過程：

Step 1：將n個數(shù)據(jù)對象各自為一個類，即c1，c2，…，cn，其中ci，cj，（i，j≤n）的距離為d（ci，cj）；

Step 2：找出dmin（ci，cj），合并ci，cj為同一個類，n=n-1；

Step 3：重新計(jì)算各類間的距離d（ci，cj）；

Step 4：repeat step2，step3，Until n=1聚類結(jié)束。

層次聚類的方法簡單，但是對處理離散點(diǎn)和噪聲數(shù)據(jù)敏感，如果處理過程選擇不當(dāng)可能導(dǎo)致低質(zhì)量的聚類結(jié)果，而且層次聚類算法的可伸縮性比較差。

3.3 DBSCAN一種基于高密度連通區(qū)域的聚類算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

也是一種基于密度的聚類算法，該算法將高于一定密度的區(qū)域數(shù)據(jù)劃分為一類，且在有噪聲的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的劃分，一個聚類定義為密度相連的數(shù)據(jù)的最大集合。DBSCAN算法有以下定義：

（1）對象R的鄰域?yàn)榻o定對象半徑R內(nèi)的鄰域；

（2）S對象的R鄰域至少有最小數(shù)目MinPts個對象，則稱S對象為核心對象；

（3）對于數(shù)據(jù)對象集合D，如果Q是一個核心對象，且P在Q的R鄰域內(nèi)，則對象P從對象Q密度可達(dá)；

（4）密度可達(dá)：對于樣本集合D，給定一串樣本點(diǎn)p1，p2，…，pn，p=p1，q= pn，假如對象pi從pi-1直接密度可達(dá)，那么對象q從對象p密度可達(dá)。

（5）數(shù)據(jù)集D中存在對象S，且關(guān)于r和MinPts，對象p從對象S密度可達(dá)，對象Q從對象S也密度可達(dá)，那么對象p到對象q是關(guān)于r和MinPts密度相連。

與K-means算法相比，DBSCAN可以發(fā)現(xiàn)任意形狀的簇類，也無需事先知道數(shù)據(jù)形成簇類的數(shù)量，并且可以識別出數(shù)據(jù)噪聲點(diǎn)；但是對于邊界樣本數(shù)據(jù)的歸類會有所不同，不能很好地反映數(shù)據(jù)集變化的密度；由于DBSCAN算法不對聚類數(shù)據(jù)進(jìn)行預(yù)處理，所以當(dāng)要處理的數(shù)據(jù)量比較大時(shí)，所耗費(fèi)資源也非常大。

4 結(jié)語

本文介紹了數(shù)據(jù)挖掘中聚類算法的幾種分類，然后詳細(xì)分析了目前常用的3個聚類算法，并比較了各自的優(yōu)缺點(diǎn)。聚類分析是數(shù)據(jù)挖掘中一種重要的分析數(shù)據(jù)的方法，通過分析可以看出不同分類的聚類算法各有各的優(yōu)劣勢，實(shí)際使用過程中可以根據(jù)實(shí)際數(shù)據(jù)情況來選擇合適的聚類分析算法。由于聚類分析在電子商務(wù)、市場分析、生物學(xué)等越來越多的領(lǐng)域中得到了廣泛應(yīng)用，并且數(shù)據(jù)挖掘在實(shí)際應(yīng)用中取得了巨大的商業(yè)價(jià)值，可對其進(jìn)行深入研究。

參考文獻(xiàn)

[1]丁金鳳.基于網(wǎng)格與密度的數(shù)據(jù)流聚類算法研究[D].哈爾濱：哈爾濱工程大學(xué)，2010.

[2]王鑫.數(shù)據(jù)挖掘中聚類分析算法的研究[D].濟(jì)南：山東師范大學(xué)大學(xué)，2006.

[3]范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2011：251-278.