數(shù)據(jù)挖掘常用聚類算法研究

趙學武　劉向嬌　尹孟洋

摘要：信息社會的發(fā)展，使數(shù)據(jù)量以前所未有的速度在增長，因此從海量數(shù)據(jù)中獲取有用的知識和信息就變得越來越重要。數(shù)據(jù)挖掘是一種綜合多領(lǐng)域知識而形成的數(shù)據(jù)分析技術(shù)，能夠從大量數(shù)據(jù)中獲取有價值的知識并為決策提供支持。聚類分析算法是數(shù)據(jù)挖掘中的一個核心內(nèi)容，也是目前研究的一個熱點。該文首先講述了基于劃分的聚類算法、基于分層的聚類算法、基于密度的聚類算法和基于網(wǎng)格的聚類算法等常用的聚類分析算法，并分析了其特點；然后通過舉例詳細描述了最近鄰聚類算法的操作過程。聚類算法的總結(jié)，對聚類的研究和發(fā)展具有積極意義。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類；聚類算法；簇；核密度

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）16-3710-03

Abstract：The development of the information society make the amount of data growing at an unprecedented rate， and so to obtain useful knowledge from huge amounts of data and information becomes more and more important. Data mining is a data analysis technique formed by integrating multi-domain knowledge， which can acquire valuable knowledge from large amounts of data and provide support for decision. Clustering analysis algorithm in data mining is a core content， which is also a hotspot in the research of the current. This article first describes commonly used clustering algorithms that include the clustering algorithm based on classification， the clustering algorithm based on hierarchies and the clustering algorithm based on density and the clustering algorithm based grid， and then analyzes their characteristics. The operation process of nearest neighbor clustering algorithm is illustrated in detail by an example. The summary of the clustering algorithms has positive significance for the research and development of clustering.

Key words： data mining； clustering； clustering algorithm； cluster； kernel density

近年來，通信技術(shù)、計算機技術(shù)、信息技術(shù)的快速發(fā)展和不斷完善，使社會上每天產(chǎn)生了大量的諸如文本、音頻、視頻、圖像等數(shù)據(jù)。面對這些海量數(shù)據(jù)，如何從中找到有價值的知識和信息是目前研究者研究的一個重要課題，數(shù)據(jù)挖掘技術(shù)在這種背景下應運而生了。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或挖掘出潛在的、有價值的、可理解的知識和規(guī)則的過程，并為用戶決策提供支持。作為一個應用驅(qū)動的領(lǐng)域，數(shù)據(jù)挖掘吸納了諸如統(tǒng)計學習、機器學習、模式識別、數(shù)據(jù)庫和數(shù)據(jù)倉庫、信息檢索、可視化、算法、高性能計算和許多應用領(lǐng)域的大量技術(shù)[1]。數(shù)據(jù)挖掘是一種新式的具有一定深度的數(shù)據(jù)處理技術(shù)；聚類分析是一種重要的分析數(shù)據(jù)的方法，是將物理的或抽象的對象集合分成相似的對象類的過程[2]，是人們發(fā)現(xiàn)事物內(nèi)在聯(lián)系的有效手段之一[3]。劃分后的對象類被稱為簇，因此聚類的結(jié)果是一個簇集，也稱為一個聚類。聚類分析的主要目標是在沒有先驗信息的前提下將樣本空間中的數(shù)據(jù)集按照某種度量標準劃分成若干類，使得按照這一標準在同一類中的個體盡可能相似而在不同類中的個體有較大差異[4]。聚類分析并沒有對簇的數(shù)目和結(jié)構(gòu)做出事先的假定，因此它是一種無監(jiān)督學習的方法，其具體實現(xiàn)有不同的算法。

1 數(shù)據(jù)挖掘常用聚類算法簡要介紹

聚類分析是數(shù)據(jù)挖掘中占具著重要地位，它是在數(shù)據(jù)對象沒有類標號的情況下，把數(shù)據(jù)對象集劃分成若干個簇，使得同一個簇內(nèi)的數(shù)據(jù)對象高度相似，不同簇間的數(shù)據(jù)對象高度相異。聚類分析技術(shù)在生物學、商務(wù)智能和Web搜索等領(lǐng)域得到了廣泛應用。到目前為止出現(xiàn)了一些實現(xiàn)聚類分析的算法，其中比較常用的有基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法和基于網(wǎng)格的聚類算法等。

1）基于劃分的聚類算法

對于給定的n個對象集，將數(shù)據(jù)對象集劃分成不重疊的子集（簇），使得每個數(shù)據(jù)對象?。ㄖ唬┰谝粋€子集中，每個子集中至少有一個數(shù)據(jù)對象?；趧澐值木垲愃惴▽栴}歸結(jié)為一個優(yōu)化問題，具有深厚的泛函基礎(chǔ)，是聚類算法研究的重要分支之一[5]。

K-均值聚類算法是基于劃分的聚類算法中最著名、最常用的算法之一，它的基本思路如下：對于給定的數(shù)據(jù)對象集D，通過參數(shù)K指定簇的數(shù)目，為每個簇指定一個質(zhì)心 （中心點）；然后，每個點被指派到最近的質(zhì)心，而指派到同一個質(zhì)心的點集形成一個簇。之后，根據(jù)被指派到簇的點，更新每個簇的質(zhì)心，重復指派和更新過程，直到質(zhì)心不再發(fā)生變化。K-均值算法思想簡單、局部搜索能力強，收斂速度快[6]；其簇數(shù)K必須由用戶指定。K-均值有以下局限性：a）當真實簇的大小差異很大、密度變化很大或為非球形簇時，K-均值很難找到真實存在的簇；b）當數(shù)據(jù)對象集包含離群點時，K-均值存在問題；c）K-均值僅限于具有中心（質(zhì)心）概念的數(shù)據(jù)對象集。endprint

2）基于層次的聚類算法

層次聚類算法依據(jù)數(shù)據(jù)對象間的相似度做迭代性的層次分解。根據(jù)建立層次方向的不同，可以分為自底向上的凝聚算法和自頂向下的分裂算法。前者是首先把每個對象作為一個群組，然后逐次合并當前最相似的群組或?qū)ο?，直到僅剩一個組群為止或滿足終止條件；后者是首先將所有對象放在一個群組中，然后迭代執(zhí)行：把一個簇劃分為更小的簇，直到每個群組中只有一個對象或滿足終止條件為止。層次聚類算法的優(yōu)點是能夠得到不同粒度上的多層次聚類結(jié)構(gòu)[7]。

（1） 最近鄰聚類算法。首先把每個數(shù)據(jù)對象作為一個簇，然后迭代進行：計算當前所有簇中兩兩之間的相似性，把相似性最大的兩個簇之間加一條鏈使之合并成為一個更大的簇，重復進行，直到只剩下一個簇為止。最近鄰算法的優(yōu)勢是能夠處理非橢圓形狀的簇，其局限性是對噪聲和離群點比較敏感。

（2） 最遠鄰聚類算法。從所有數(shù)據(jù)對象中每個對象作為一個簇開始，然后進行迭代：計算所有簇中兩兩之間的最大距離，然后從中選取距離最小的兩個簇，在其間添加一條鏈形成一個更大的簇，重復操作直到只剩下一個簇為止。最遠鄰近聚類算法的優(yōu)勢是對噪聲和離群點比較不敏感，其局限性是可能使較大的簇破裂且偏好球形簇。

3）基于密度的聚類算法

基于密度的聚類算法中類簇被定義為連通的稠密子區(qū)域[8]，其主要思想是在數(shù)據(jù)點（數(shù)據(jù)對象）分布中，高密度的區(qū)域被低密度的區(qū)域所分隔，將密度足夠高的區(qū)域劃分成簇。這種算法的優(yōu)點是不受噪聲和離群點的影響，并且可以發(fā)現(xiàn)任意形狀的簇。

DBSCAN是一種基于高密度連通區(qū)域的基于密度的聚類[1]，在數(shù)據(jù)挖掘中是一個非常著名的聚類算法。該算法的過程可以簡單描述如下：首先將所有數(shù)據(jù)點標記為核心點、邊界點和噪聲點；然后刪除噪聲點；接著在所有核心點中，為其距離在給定鄰域之內(nèi)的核心點之間加入一條邊；然后每組連通的核心點形成一個簇；最后將每個邊界點指派到一個與之關(guān)聯(lián)的核心點的簇中。在DBSCAN算法中，需要確定鄰域半徑（Eps）和數(shù)據(jù)點個數(shù)的閾值（MinPts）；該算法具有抗噪聲和能夠發(fā)現(xiàn)任意形狀的簇的優(yōu)勢，但同時也具有易受密度變化的影響和不適應處理高維數(shù)據(jù)的缺點。

DENCLUE是一種基于密度分布函數(shù)的聚類算法，具有堅實的數(shù)學基礎(chǔ)。DENCLUE的基本思想是核密度函數(shù)通過使用個體數(shù)據(jù)對象影響之和對點集總密度建模。DENCLUE算法的主要步驟：（1）推導出衡量數(shù)據(jù)點占據(jù)空間的密度函數(shù)；（2）識別局部最大點（密度吸引點）；（3）沿著密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點；（4）得到與特定的密度吸引點相關(guān)聯(lián)的點構(gòu)成的簇；（5）刪去密度吸引點的密度小于事先指定閾值的簇；（6）合并通過密度大于或等于噪聲閾值[ξ]的點路徑連接的簇。DENCLUE除了具有和DBSCAN算法的特點外，提供了較DBSCAN更加靈活、更加精確的計算密度的方法，可以適用于任何復雜數(shù)據(jù)對象，是一種比較有效的基于核密度的聚類算法。

4）基于網(wǎng)格的聚類算法

基于網(wǎng)格的聚類算法是一種比較新穎的采用空間驅(qū)動的聚類算法，把數(shù)據(jù)對象集劃分為數(shù)目有限的單元，創(chuàng)建網(wǎng)格單元的集合并形成一個網(wǎng)絡(luò)結(jié)構(gòu)；然后由足夠稠密的網(wǎng)格單元形成簇。該算法具有處理速度快的優(yōu)點，這是因為它的處理時間通常獨立于數(shù)據(jù)對象集，而只依賴于量化空間中每一維的單元數(shù)。

STING是一種面向網(wǎng)格的多分辨率聚類算法，它將數(shù)據(jù)點空間劃分成矩形單元。這些矩形單元形成一個層次結(jié)構(gòu)，并與不同級別的分辨率相對應。每個網(wǎng)格單元的屬性的統(tǒng)計信息被預先保存下來，被用于查詢處理或其它數(shù)據(jù)分析任務(wù)。網(wǎng)格結(jié)構(gòu)的最底層的粒度決定了STING聚類的質(zhì)量。STING算法除了具有處理速度快以外，還具有網(wǎng)格結(jié)構(gòu)獨立于查詢、有利于并行處理和增量更新等特點。

2 基于層次的聚類算法實例

基于層次的聚類算法是數(shù)據(jù)挖掘中最重要的聚類算法之一，將需要處理的數(shù)據(jù)點組織成樹狀圖的形式來表示聚類的結(jié)果。自底向上的層次聚類算法和自頂向下的層次聚類算法是基于層次的聚類算法的兩種形式，其中前者又是比較常見的層次聚類算法。在自底向上的層次聚類中，計算當前簇集中兩個簇之間的距離，然后將符合條件的兩個簇合并為一個簇；重復上述操作，直到僅剩一個簇為止。

給出平面上的6個點，如表1所示。用最近鄰聚類算法對其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計算表1中6個點中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個點是一個簇，如圖2中（a1）所示；

3） 計算最近的兩個簇，將其合并為一個簇；

4） 若有兩個分開的簇，則重復3），否則結(jié)束。

3 總結(jié)

本文首先介紹了數(shù)據(jù)挖掘聚類技術(shù)中目前比較常用的流行算法，并分析了這些算法的特點。然后描述了以最近鄰聚類算法為代表的層次聚類算法的操作過程，并得到了聚類的結(jié)果——樹狀圖結(jié)構(gòu)。聚類分析算法經(jīng)常應用在金融、教育等行業(yè)，具有較好的應用發(fā)展前景。因此，可以對其做深入研究。

參考文獻：

[1] Jiawei Han，Micheline Kamber，Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2012：288-314.

[2] 潘曉英，劉芳，焦李成.密度敏感的多智能體進化聚類算法[J].軟件學報，2010，21（10）： 2420-2431.

[3] 梁群玲，肖人岳，王向東.一種改進的自適應蟻群聚類算法[J].計算機應用研究，2011，28（4）： 1263-1265.

[4] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進展[J].計算機工程與應用，2012，48（12）：100-111.

[5] 雷小鋒，何濤，李奎儒，等.面向結(jié)構(gòu)穩(wěn)定性的分裂-合并聚類算法[J].計算機科學，2010，37（11）：217-222.

[6] 曹永春，邵亞斌，田雙亮，蔡正琦.一種基于免疫遺傳算法的聚類方法[J].廣西師范大學學報：自然科學版，2013，31（3）：59-64.

[7] 王永貴，林琳，劉憲國.結(jié)合雙粒子和K-means的混合文本聚類算法[J].計算機應用研究， 2014，31（2）：364-368.

[8] 劉雷，王洪國，邵增珍，等.一種基于峰群原理的劃分聚類算法[J].計算機應用研究， 2011，28（5）：1699-1702.endprint

2）基于層次的聚類算法

層次聚類算法依據(jù)數(shù)據(jù)對象間的相似度做迭代性的層次分解。根據(jù)建立層次方向的不同，可以分為自底向上的凝聚算法和自頂向下的分裂算法。前者是首先把每個對象作為一個群組，然后逐次合并當前最相似的群組或?qū)ο?，直到僅剩一個組群為止或滿足終止條件；后者是首先將所有對象放在一個群組中，然后迭代執(zhí)行：把一個簇劃分為更小的簇，直到每個群組中只有一個對象或滿足終止條件為止。層次聚類算法的優(yōu)點是能夠得到不同粒度上的多層次聚類結(jié)構(gòu)[7]。

（1） 最近鄰聚類算法。首先把每個數(shù)據(jù)對象作為一個簇，然后迭代進行：計算當前所有簇中兩兩之間的相似性，把相似性最大的兩個簇之間加一條鏈使之合并成為一個更大的簇，重復進行，直到只剩下一個簇為止。最近鄰算法的優(yōu)勢是能夠處理非橢圓形狀的簇，其局限性是對噪聲和離群點比較敏感。

（2） 最遠鄰聚類算法。從所有數(shù)據(jù)對象中每個對象作為一個簇開始，然后進行迭代：計算所有簇中兩兩之間的最大距離，然后從中選取距離最小的兩個簇，在其間添加一條鏈形成一個更大的簇，重復操作直到只剩下一個簇為止。最遠鄰近聚類算法的優(yōu)勢是對噪聲和離群點比較不敏感，其局限性是可能使較大的簇破裂且偏好球形簇。

3）基于密度的聚類算法

基于密度的聚類算法中類簇被定義為連通的稠密子區(qū)域[8]，其主要思想是在數(shù)據(jù)點（數(shù)據(jù)對象）分布中，高密度的區(qū)域被低密度的區(qū)域所分隔，將密度足夠高的區(qū)域劃分成簇。這種算法的優(yōu)點是不受噪聲和離群點的影響，并且可以發(fā)現(xiàn)任意形狀的簇。

DBSCAN是一種基于高密度連通區(qū)域的基于密度的聚類[1]，在數(shù)據(jù)挖掘中是一個非常著名的聚類算法。該算法的過程可以簡單描述如下：首先將所有數(shù)據(jù)點標記為核心點、邊界點和噪聲點；然后刪除噪聲點；接著在所有核心點中，為其距離在給定鄰域之內(nèi)的核心點之間加入一條邊；然后每組連通的核心點形成一個簇；最后將每個邊界點指派到一個與之關(guān)聯(lián)的核心點的簇中。在DBSCAN算法中，需要確定鄰域半徑（Eps）和數(shù)據(jù)點個數(shù)的閾值（MinPts）；該算法具有抗噪聲和能夠發(fā)現(xiàn)任意形狀的簇的優(yōu)勢，但同時也具有易受密度變化的影響和不適應處理高維數(shù)據(jù)的缺點。

DENCLUE是一種基于密度分布函數(shù)的聚類算法，具有堅實的數(shù)學基礎(chǔ)。DENCLUE的基本思想是核密度函數(shù)通過使用個體數(shù)據(jù)對象影響之和對點集總密度建模。DENCLUE算法的主要步驟：（1）推導出衡量數(shù)據(jù)點占據(jù)空間的密度函數(shù)；（2）識別局部最大點（密度吸引點）；（3）沿著密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點；（4）得到與特定的密度吸引點相關(guān)聯(lián)的點構(gòu)成的簇；（5）刪去密度吸引點的密度小于事先指定閾值的簇；（6）合并通過密度大于或等于噪聲閾值[ξ]的點路徑連接的簇。DENCLUE除了具有和DBSCAN算法的特點外，提供了較DBSCAN更加靈活、更加精確的計算密度的方法，可以適用于任何復雜數(shù)據(jù)對象，是一種比較有效的基于核密度的聚類算法。

4）基于網(wǎng)格的聚類算法

基于網(wǎng)格的聚類算法是一種比較新穎的采用空間驅(qū)動的聚類算法，把數(shù)據(jù)對象集劃分為數(shù)目有限的單元，創(chuàng)建網(wǎng)格單元的集合并形成一個網(wǎng)絡(luò)結(jié)構(gòu)；然后由足夠稠密的網(wǎng)格單元形成簇。該算法具有處理速度快的優(yōu)點，這是因為它的處理時間通常獨立于數(shù)據(jù)對象集，而只依賴于量化空間中每一維的單元數(shù)。

STING是一種面向網(wǎng)格的多分辨率聚類算法，它將數(shù)據(jù)點空間劃分成矩形單元。這些矩形單元形成一個層次結(jié)構(gòu)，并與不同級別的分辨率相對應。每個網(wǎng)格單元的屬性的統(tǒng)計信息被預先保存下來，被用于查詢處理或其它數(shù)據(jù)分析任務(wù)。網(wǎng)格結(jié)構(gòu)的最底層的粒度決定了STING聚類的質(zhì)量。STING算法除了具有處理速度快以外，還具有網(wǎng)格結(jié)構(gòu)獨立于查詢、有利于并行處理和增量更新等特點。

2 基于層次的聚類算法實例

基于層次的聚類算法是數(shù)據(jù)挖掘中最重要的聚類算法之一，將需要處理的數(shù)據(jù)點組織成樹狀圖的形式來表示聚類的結(jié)果。自底向上的層次聚類算法和自頂向下的層次聚類算法是基于層次的聚類算法的兩種形式，其中前者又是比較常見的層次聚類算法。在自底向上的層次聚類中，計算當前簇集中兩個簇之間的距離，然后將符合條件的兩個簇合并為一個簇；重復上述操作，直到僅剩一個簇為止。

給出平面上的6個點，如表1所示。用最近鄰聚類算法對其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計算表1中6個點中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個點是一個簇，如圖2中（a1）所示；

3） 計算最近的兩個簇，將其合并為一個簇；

4） 若有兩個分開的簇，則重復3），否則結(jié)束。

3 總結(jié)

本文首先介紹了數(shù)據(jù)挖掘聚類技術(shù)中目前比較常用的流行算法，并分析了這些算法的特點。然后描述了以最近鄰聚類算法為代表的層次聚類算法的操作過程，并得到了聚類的結(jié)果——樹狀圖結(jié)構(gòu)。聚類分析算法經(jīng)常應用在金融、教育等行業(yè)，具有較好的應用發(fā)展前景。因此，可以對其做深入研究。

參考文獻：

[1] Jiawei Han，Micheline Kamber，Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2012：288-314.

[2] 潘曉英，劉芳，焦李成.密度敏感的多智能體進化聚類算法[J].軟件學報，2010，21（10）： 2420-2431.

[3] 梁群玲，肖人岳，王向東.一種改進的自適應蟻群聚類算法[J].計算機應用研究，2011，28（4）： 1263-1265.

[4] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進展[J].計算機工程與應用，2012，48（12）：100-111.

[5] 雷小鋒，何濤，李奎儒，等.面向結(jié)構(gòu)穩(wěn)定性的分裂-合并聚類算法[J].計算機科學，2010，37（11）：217-222.

[6] 曹永春，邵亞斌，田雙亮，蔡正琦.一種基于免疫遺傳算法的聚類方法[J].廣西師范大學學報：自然科學版，2013，31（3）：59-64.

[7] 王永貴，林琳，劉憲國.結(jié)合雙粒子和K-means的混合文本聚類算法[J].計算機應用研究， 2014，31（2）：364-368.

[8] 劉雷，王洪國，邵增珍，等.一種基于峰群原理的劃分聚類算法[J].計算機應用研究， 2011，28（5）：1699-1702.endprint

2）基于層次的聚類算法

層次聚類算法依據(jù)數(shù)據(jù)對象間的相似度做迭代性的層次分解。根據(jù)建立層次方向的不同，可以分為自底向上的凝聚算法和自頂向下的分裂算法。前者是首先把每個對象作為一個群組，然后逐次合并當前最相似的群組或?qū)ο?，直到僅剩一個組群為止或滿足終止條件；后者是首先將所有對象放在一個群組中，然后迭代執(zhí)行：把一個簇劃分為更小的簇，直到每個群組中只有一個對象或滿足終止條件為止。層次聚類算法的優(yōu)點是能夠得到不同粒度上的多層次聚類結(jié)構(gòu)[7]。

（1） 最近鄰聚類算法。首先把每個數(shù)據(jù)對象作為一個簇，然后迭代進行：計算當前所有簇中兩兩之間的相似性，把相似性最大的兩個簇之間加一條鏈使之合并成為一個更大的簇，重復進行，直到只剩下一個簇為止。最近鄰算法的優(yōu)勢是能夠處理非橢圓形狀的簇，其局限性是對噪聲和離群點比較敏感。

（2） 最遠鄰聚類算法。從所有數(shù)據(jù)對象中每個對象作為一個簇開始，然后進行迭代：計算所有簇中兩兩之間的最大距離，然后從中選取距離最小的兩個簇，在其間添加一條鏈形成一個更大的簇，重復操作直到只剩下一個簇為止。最遠鄰近聚類算法的優(yōu)勢是對噪聲和離群點比較不敏感，其局限性是可能使較大的簇破裂且偏好球形簇。

3）基于密度的聚類算法

基于密度的聚類算法中類簇被定義為連通的稠密子區(qū)域[8]，其主要思想是在數(shù)據(jù)點（數(shù)據(jù)對象）分布中，高密度的區(qū)域被低密度的區(qū)域所分隔，將密度足夠高的區(qū)域劃分成簇。這種算法的優(yōu)點是不受噪聲和離群點的影響，并且可以發(fā)現(xiàn)任意形狀的簇。

DBSCAN是一種基于高密度連通區(qū)域的基于密度的聚類[1]，在數(shù)據(jù)挖掘中是一個非常著名的聚類算法。該算法的過程可以簡單描述如下：首先將所有數(shù)據(jù)點標記為核心點、邊界點和噪聲點；然后刪除噪聲點；接著在所有核心點中，為其距離在給定鄰域之內(nèi)的核心點之間加入一條邊；然后每組連通的核心點形成一個簇；最后將每個邊界點指派到一個與之關(guān)聯(lián)的核心點的簇中。在DBSCAN算法中，需要確定鄰域半徑（Eps）和數(shù)據(jù)點個數(shù)的閾值（MinPts）；該算法具有抗噪聲和能夠發(fā)現(xiàn)任意形狀的簇的優(yōu)勢，但同時也具有易受密度變化的影響和不適應處理高維數(shù)據(jù)的缺點。

DENCLUE是一種基于密度分布函數(shù)的聚類算法，具有堅實的數(shù)學基礎(chǔ)。DENCLUE的基本思想是核密度函數(shù)通過使用個體數(shù)據(jù)對象影響之和對點集總密度建模。DENCLUE算法的主要步驟：（1）推導出衡量數(shù)據(jù)點占據(jù)空間的密度函數(shù)；（2）識別局部最大點（密度吸引點）；（3）沿著密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點；（4）得到與特定的密度吸引點相關(guān)聯(lián)的點構(gòu)成的簇；（5）刪去密度吸引點的密度小于事先指定閾值的簇；（6）合并通過密度大于或等于噪聲閾值[ξ]的點路徑連接的簇。DENCLUE除了具有和DBSCAN算法的特點外，提供了較DBSCAN更加靈活、更加精確的計算密度的方法，可以適用于任何復雜數(shù)據(jù)對象，是一種比較有效的基于核密度的聚類算法。

4）基于網(wǎng)格的聚類算法

基于網(wǎng)格的聚類算法是一種比較新穎的采用空間驅(qū)動的聚類算法，把數(shù)據(jù)對象集劃分為數(shù)目有限的單元，創(chuàng)建網(wǎng)格單元的集合并形成一個網(wǎng)絡(luò)結(jié)構(gòu)；然后由足夠稠密的網(wǎng)格單元形成簇。該算法具有處理速度快的優(yōu)點，這是因為它的處理時間通常獨立于數(shù)據(jù)對象集，而只依賴于量化空間中每一維的單元數(shù)。

STING是一種面向網(wǎng)格的多分辨率聚類算法，它將數(shù)據(jù)點空間劃分成矩形單元。這些矩形單元形成一個層次結(jié)構(gòu)，并與不同級別的分辨率相對應。每個網(wǎng)格單元的屬性的統(tǒng)計信息被預先保存下來，被用于查詢處理或其它數(shù)據(jù)分析任務(wù)。網(wǎng)格結(jié)構(gòu)的最底層的粒度決定了STING聚類的質(zhì)量。STING算法除了具有處理速度快以外，還具有網(wǎng)格結(jié)構(gòu)獨立于查詢、有利于并行處理和增量更新等特點。

2 基于層次的聚類算法實例

基于層次的聚類算法是數(shù)據(jù)挖掘中最重要的聚類算法之一，將需要處理的數(shù)據(jù)點組織成樹狀圖的形式來表示聚類的結(jié)果。自底向上的層次聚類算法和自頂向下的層次聚類算法是基于層次的聚類算法的兩種形式，其中前者又是比較常見的層次聚類算法。在自底向上的層次聚類中，計算當前簇集中兩個簇之間的距離，然后將符合條件的兩個簇合并為一個簇；重復上述操作，直到僅剩一個簇為止。

給出平面上的6個點，如表1所示。用最近鄰聚類算法對其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計算表1中6個點中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個點是一個簇，如圖2中（a1）所示；

3） 計算最近的兩個簇，將其合并為一個簇；

4） 若有兩個分開的簇，則重復3），否則結(jié)束。

3 總結(jié)

本文首先介紹了數(shù)據(jù)挖掘聚類技術(shù)中目前比較常用的流行算法，并分析了這些算法的特點。然后描述了以最近鄰聚類算法為代表的層次聚類算法的操作過程，并得到了聚類的結(jié)果——樹狀圖結(jié)構(gòu)。聚類分析算法經(jīng)常應用在金融、教育等行業(yè)，具有較好的應用發(fā)展前景。因此，可以對其做深入研究。

參考文獻：

[1] Jiawei Han，Micheline Kamber，Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2012：288-314.

[2] 潘曉英，劉芳，焦李成.密度敏感的多智能體進化聚類算法[J].軟件學報，2010，21（10）： 2420-2431.

[3] 梁群玲，肖人岳，王向東.一種改進的自適應蟻群聚類算法[J].計算機應用研究，2011，28（4）： 1263-1265.

[4] 周濤，陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進展[J].計算機工程與應用，2012，48（12）：100-111.

[5] 雷小鋒，何濤，李奎儒，等.面向結(jié)構(gòu)穩(wěn)定性的分裂-合并聚類算法[J].計算機科學，2010，37（11）：217-222.

[6] 曹永春，邵亞斌，田雙亮，蔡正琦.一種基于免疫遺傳算法的聚類方法[J].廣西師范大學學報：自然科學版，2013，31（3）：59-64.

[7] 王永貴，林琳，劉憲國.結(jié)合雙粒子和K-means的混合文本聚類算法[J].計算機應用研究， 2014，31（2）：364-368.

[8] 劉雷，王洪國，邵增珍，等.一種基于峰群原理的劃分聚類算法[J].計算機應用研究， 2011，28（5）：1699-1702.endprint