邢培　胥家瑞

[摘要]：近幾年來發(fā)展相當(dāng)迅猛的數(shù)據(jù)挖掘技術(shù)，這種數(shù)據(jù)挖掘的一種主要技術(shù)聚類是本文主要研究的內(nèi)容，目的是通過深入探索挖掘的方法，了解數(shù)據(jù)挖掘的應(yīng)用前景，可以為用戶更好地使用數(shù)據(jù)挖掘來解決實際問題提供了可行的操作方法和理論依據(jù)。

[關(guān)鍵詞]：數(shù)據(jù)挖掘 聚類神經(jīng)網(wǎng)絡(luò)

數(shù)據(jù)挖掘，顧名思義就是從大量數(shù)據(jù)中挖掘出有用的信息，即從大量的、不完全的、由噪聲的、模糊的、隨機實際應(yīng)用數(shù)據(jù)中發(fā)現(xiàn)隱含的、規(guī)律性的、人們事先未知的，但又是潛在有用的并且最終可理解的信息和知識的非平凡過程。用于數(shù)據(jù)挖掘的很多方法都來源于兩個研究分支，一個是機器學(xué)，另一個是統(tǒng)計學(xué)，特別是多元的計算統(tǒng)計學(xué)。 聚類是數(shù)據(jù)挖掘中的一種主要技術(shù)，是把一組個體按照相似性歸成若干類別，即“物以類聚”。它的目的是使得屬于同一類別的個體之間的距離盡可能的小，而不同類別上的個體間的距離盡可能的大。聚類和分類根本不同的是：分類問題中，我們知道訓(xùn)練例的分類屬性，而在聚類中，就需要我們在訓(xùn)練例中找到這個分類屬性值。聚類方法包括統(tǒng)計方法、機器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法和面向數(shù)據(jù)庫的方法。

在統(tǒng)計方法中聚類稱聚類分析，它是多元數(shù)據(jù)分析的三大方法之一（其它兩種是回歸分析和判別分析）。它主要研究基于幾何距離的聚類，如歐式距離、明考斯基距離等。傳統(tǒng)的統(tǒng)計聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。

在機器學(xué)習(xí)中聚類稱作無監(jiān)督或無教師歸納。因為和分類學(xué)習(xí)相比，分類學(xué)習(xí)的例子或數(shù)據(jù)對象有類別標(biāo)記，而聚類的例子則沒有標(biāo)記，需要由聚類學(xué)習(xí)算法來自動確定。機器學(xué)習(xí)領(lǐng)域中的概念聚類算法通過符號屬性來進(jìn)行聚類，并得出聚類的概念描述。當(dāng)聚類對象可以動態(tài)增加時，概念聚類則稱是概念形成。概念聚類由兩部分組成：

（1）發(fā)現(xiàn)合適的類

（2）形成對每個類的描述。

聚類分析問題可描述為：給定m維空間Rm中的n個向量，把每個向量歸屬到S聚類中的某一個，使得每個向量與其聚類中心的“距離”最小。聚類分析問題的實質(zhì)是一個全局最優(yōu)問題。在這里，m可認(rèn)為是樣本參與聚類的屬性個數(shù)，n是樣本的個數(shù)，S是由用戶預(yù)先設(shè)定的分類數(shù)目。

數(shù)據(jù)聚類正在蓬勃發(fā)展，有貢獻(xiàn)的研究領(lǐng)域包括數(shù)據(jù)挖掘、統(tǒng)計學(xué)機器學(xué)習(xí)、空間數(shù)據(jù)庫技術(shù)、生物學(xué)，以及市場營銷。由于數(shù)據(jù)庫中收集了大量的數(shù)據(jù)，聚類分析已經(jīng)成為數(shù)據(jù)挖掘研究領(lǐng)域中一個非常活躍的研究課題。

隨著數(shù)據(jù)挖掘研究的深入，出現(xiàn)了很多的聚類算法。常見的聚類算法有五大類。即劃分法、分層法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。

1、劃分方法（partitioning method）

給定要構(gòu)建的劃分的數(shù)目k，創(chuàng)建一個初始劃分。每個劃分表示一個簇， 每個簇至少包含一個數(shù)據(jù)對象，同時，每個數(shù)據(jù)對象只能屬于一個簇（模糊聚類中可放寬約束）。然后采用一種迭代的重定位技術(shù)，嘗試通過對象在劃分間移動來改進(jìn)劃分，直到以局部最優(yōu)結(jié)束。一個好的劃分的準(zhǔn)則是：在同一類中的對象之間盡可能“接近”或相關(guān)，而不同類中的對象之間盡可能的遠(yuǎn)離或不同。

最著名與常用的劃分方法是K-means、K-medoids以及它們的變種。

2、層次方法（hierarchical method）

層次式聚類算法對給定數(shù)據(jù)對象集合進(jìn)行層次的分解，根據(jù)層次分解形成的方向又可以分成凝聚式和分列式兩種。前者采用自底向上的方法，先將每個對象歸為單獨底組，然后逐漸合并相近的對象或組，直到所有的組合并為一個，或者達(dá)到一個中止條件。后者則采用自頂向下的方法， 初始將所有的對象置于一個組中，然后在迭代的過程中，每個組被分裂為更小的組，直到最終每個對象在單獨的一個組中，或者達(dá)到一個中止條件。

層次式聚類算法的缺陷在于，一旦完成一個合并或分裂的步驟后，即使是錯誤的，也無法被撤銷，且影響其后的聚類過程。

CURE算法就是采用了層次聚類算法，解決了絕大多數(shù)聚類算法偏好球形和相似大小的問題，在處理孤立點上也更加健壯。但CURE不能處理分類屬性。

3、基于密度的方法（density-based method）

基于距離的聚類方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難，為此提出了基于密度的聚類。其中心思想是：只要臨近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個閥值就繼續(xù)聚類。也就是說，對類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目的點。這種方法可以用來過濾噪聲數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。

Ester Martin等人提出的DBSCAN算法是一種基于密度的空間數(shù)據(jù)聚類算法。該算法利用基于密度的聚類（或者類cluster）概念。這一算法的顯著優(yōu)點是聚類速度快，且能夠有效處理噪聲點（outliers）和發(fā)現(xiàn)任意形狀的空間聚類。但是它又兩個比較明顯的弱點：（1）當(dāng)數(shù)據(jù)量增大時，要求較大的內(nèi)存支持，I/O消耗也很大；（2）當(dāng)空間聚類的密度不均勻， 聚類間距離相差很大時，聚類質(zhì)量較差。

4、基于網(wǎng)格的方法（grid-based method）

基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成一個網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)（即量化空間）上進(jìn)行。

CLIQU算法綜合了基于密度和基于網(wǎng)格的聚類方法，利用自頂向上方法求出各個子空間的聚類單元，主要用于找出高維數(shù)據(jù)空間中存在的低維聚類。但為了求出K維空間聚類，則必須組合給出所有K-1維子空間的聚類，導(dǎo)致其算法的空間和時間效率都很低，而且要求用戶輸入兩個參數(shù)，數(shù)據(jù)聚值空間等間隔距離ξ和密度閥值τ。這些數(shù)據(jù)與樣本數(shù)據(jù)緊密相關(guān)，用戶一般難以確定。但它對數(shù)據(jù)的輸入順序不敏感。

5、基于模型的方法（model_based method）

基于模型的方法為每個聚類假定了一個模型，然后去尋找能夠很好滿足這個模型的數(shù)據(jù)集。一個基于模型的算法可以通過構(gòu)造反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類，也可以基于標(biāo)準(zhǔn)的統(tǒng)計數(shù)字自動決定聚類的數(shù)目。

現(xiàn)在人們又把數(shù)學(xué)中的模糊理論應(yīng)用到聚類領(lǐng)域中。從而產(chǎn)生了模糊聚類算法。傳統(tǒng)意義上的聚類分析是把每個樣本嚴(yán)格地劃分到某一類，屬于硬劃分的范疇，即硬聚類。隨著模糊集理論的提出，硬聚類被推廣為模糊聚類，即軟聚類。在模糊聚類中，每個樣本不再僅屬于某一類，而是以一定的隸屬度分別屬于每一類。換句話說，通過模糊聚類分析得到了樣本屬于各個類別的不確定性程度，即建立起了樣本對于類別的不確定性的描述。這樣就能更準(zhǔn)確地反映現(xiàn)實世界。