邢培　胥家瑞

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

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

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

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

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

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

（2）形成對(duì)每個(gè)類的描述。

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

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

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

1、劃分方法（partitioning method）

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

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

2、層次方法（hierarchical method）

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

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

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

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

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

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

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

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

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

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

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

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