趙學(xué)武　劉向嬌　尹孟洋

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

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

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

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

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

1）基于劃分的聚類算法

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

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

2）基于層次的聚類算法

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

（1） 最近鄰聚類算法。首先把每個(gè)數(shù)據(jù)對(duì)象作為一個(gè)簇，然后迭代進(jìn)行：計(jì)算當(dāng)前所有簇中兩兩之間的相似性，把相似性最大的兩個(gè)簇之間加一條鏈?zhǔn)怪喜⒊蔀橐粋€(gè)更大的簇，重復(fù)進(jìn)行，直到只剩下一個(gè)簇為止。最近鄰算法的優(yōu)勢(shì)是能夠處理非橢圓形狀的簇，其局限性是對(duì)噪聲和離群點(diǎn)比較敏感。

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

3）基于密度的聚類算法

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

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

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

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

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

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

2 基于層次的聚類算法實(shí)例

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

給出平面上的6個(gè)點(diǎn)，如表1所示。用最近鄰聚類算法對(duì)其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計(jì)算表1中6個(gè)點(diǎn)中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個(gè)點(diǎn)是一個(gè)簇，如圖2中（a1）所示；

3） 計(jì)算最近的兩個(gè)簇，將其合并為一個(gè)簇；

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

3 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

2）基于層次的聚類算法

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

（1） 最近鄰聚類算法。首先把每個(gè)數(shù)據(jù)對(duì)象作為一個(gè)簇，然后迭代進(jìn)行：計(jì)算當(dāng)前所有簇中兩兩之間的相似性，把相似性最大的兩個(gè)簇之間加一條鏈?zhǔn)怪喜⒊蔀橐粋€(gè)更大的簇，重復(fù)進(jìn)行，直到只剩下一個(gè)簇為止。最近鄰算法的優(yōu)勢(shì)是能夠處理非橢圓形狀的簇，其局限性是對(duì)噪聲和離群點(diǎn)比較敏感。

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

3）基于密度的聚類算法

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

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

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

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

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

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

2 基于層次的聚類算法實(shí)例

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

給出平面上的6個(gè)點(diǎn)，如表1所示。用最近鄰聚類算法對(duì)其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計(jì)算表1中6個(gè)點(diǎn)中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個(gè)點(diǎn)是一個(gè)簇，如圖2中（a1）所示；

3） 計(jì)算最近的兩個(gè)簇，將其合并為一個(gè)簇；

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

3 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

2）基于層次的聚類算法

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

（1） 最近鄰聚類算法。首先把每個(gè)數(shù)據(jù)對(duì)象作為一個(gè)簇，然后迭代進(jìn)行：計(jì)算當(dāng)前所有簇中兩兩之間的相似性，把相似性最大的兩個(gè)簇之間加一條鏈?zhǔn)怪喜⒊蔀橐粋€(gè)更大的簇，重復(fù)進(jìn)行，直到只剩下一個(gè)簇為止。最近鄰算法的優(yōu)勢(shì)是能夠處理非橢圓形狀的簇，其局限性是對(duì)噪聲和離群點(diǎn)比較敏感。

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

3）基于密度的聚類算法

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

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

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

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

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

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

2 基于層次的聚類算法實(shí)例

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

給出平面上的6個(gè)點(diǎn)，如表1所示。用最近鄰聚類算法對(duì)其聚類，說明該算法的操作過程。最近鄰聚類算法的操作過程如下：

1） 計(jì)算表1中6個(gè)點(diǎn)中兩兩之間的歐幾里德距離，如表2所示。

2） 每一個(gè)點(diǎn)是一個(gè)簇，如圖2中（a1）所示；

3） 計(jì)算最近的兩個(gè)簇，將其合并為一個(gè)簇；

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

3 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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