關(guān)于數(shù)據(jù)挖掘中聚類分析的研究進展

劉俊 劉希玉

山東師范大學管理與經(jīng)濟學院 山東 250014

0 引言

隨著信息技術(shù)的飛速發(fā)展以及信息獲取的便利，人們已被大量的信息淹沒。如何從信息的海洋中提取出人們感興趣的知識，以幫助人們完成特定的任務成為了一個迫切需要解決的問題，基于這樣一種需求，用來幫助用戶從這些海量數(shù)據(jù)中分析出其間所蘊涵的有價值的模式和知識的技術(shù)——數(shù)據(jù)挖掘就應運而生了。

所謂數(shù)據(jù)挖掘，就是從大量的、不完全的、有噪聲的、模糊的、隨機的、無序的數(shù)據(jù)中提取隱含在其中的有效的、有價值的、可理解的模式，進而發(fā)現(xiàn)有用的或是潛在有用的知識，并得出時間的趨向和關(guān)聯(lián)，為用戶提供問題求解層次的決策支持能力。

聚類分析是數(shù)據(jù)挖掘中一種很重要的技術(shù)。所謂聚類，就是把擁有大量數(shù)據(jù)的集合分成若干簇，在同一個簇中的數(shù)據(jù)對象之間最大程度的相似，而在不同簇中的數(shù)據(jù)對象之間具有最大程度的不同。在實際應用中，一個聚類結(jié)果會影響到數(shù)據(jù)挖掘的后續(xù)工作，通常一個好的聚類結(jié)果會使數(shù)據(jù)分析工作變得簡單清晰，比較容易得到用戶想要的知識，而一個糟糕的聚類結(jié)果卻正好相反，甚至得不到用戶想要的結(jié)果。因此聚類分析成了數(shù)據(jù)挖掘中的最為關(guān)鍵的部分，發(fā)展成為一個很活躍的研究方向。

1 對聚類分析研究成果的概述

對于數(shù)據(jù)挖掘中聚類分析的傳統(tǒng)方法，根據(jù)其基本的思想，可以分成以下幾類：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法。

（1）劃分方法

劃分方法的基本思想是：給定具有N個對象或元組的數(shù)據(jù)庫，指明想要得到的簇的數(shù)目k，一個劃分方法利用采取的算法將這N個對象劃分成k個分組，其中k

K-means方法：在具有n個對象的數(shù)據(jù)集中，隨機選擇k個對象，每個對象初始的代表一個簇的中心，根據(jù)所采用的距離度量（如歐幾里得距離度量）計算剩余的每個對象與這k個初始簇中心點的距離，將對象分配到與其具有最小距離的簇中，這樣具有n個對象的數(shù)據(jù)集被劃分成k個簇，然后重新計算每個簇的平均值。該過程不斷的循環(huán)迭代，直到新計算的平均值與上一次的平均值相比沒有變化。

從該方法的過程可以看出，當結(jié)果簇間具有明顯的區(qū)別時，k-means方法具有很好的效果，但是當存在孤立點時，孤立點對k-means方法會產(chǎn)生很大的影響，因為平均值對孤立點很敏感。另外，k-means方法需要事先指定聚類的數(shù)目。

K-medoids方法與k-means方法的過程類似，只是該方法用簇中一個實際的對象代替簇的平均值，所以相比較k-means方法而言，其不易受孤立點的影響。但是該方法要進行不斷的對比和比較，其計算代價很高，而且不太適合于大型數(shù)據(jù)集。K-medoids方法需要事先指定要得到的簇的數(shù)目。

k-means方法和k-medoids方法是目前最為流行的聚類方法，當前發(fā)展的許多聚類技術(shù)都是在這兩種方法的基礎上進行拓展（如模糊k-means聚類方法），以及在這兩種方法的基礎上進行的改進。

（2）層次方法

層次聚類方法通過將數(shù)據(jù)組織成若干組并形成一個相應的樹狀圖來進行聚類。根據(jù)其聚類的過程是自下而上還是自上而下，層次聚類方法又分成了聚合聚類和分解聚類兩種。其主要思想如下：

聚合聚類方法：將數(shù)據(jù)集中的每一個對象看作是一個單獨的簇，然后根據(jù)某個給定的原則將這些簇進行合并，直到數(shù)據(jù)集中的對象形成一個簇或者是滿足事先定義的某個終止條件。

分解聚類方法：與聚合聚類方法恰好相反，將所有的數(shù)據(jù)集看成是一個大的聚類，根據(jù)某個給定的規(guī)則對這個簇進行劃分，細化成越來越小的簇，直到每個數(shù)據(jù)對象自成一個簇或者達到某個終止條件。

幾種典型的層次方法有BIRCH，CURE等。

BIRCH方法是一種綜合性的層次聚類算法，它利用聚類特征（CF）和聚類特征樹（CF tree）來描述聚類過程。CF是一個三元組，它對對象子類的信息給出了總結(jié)性描述；一個CF tree是高度平衡的樹，它有兩個參數(shù)：分支因子和閾值，它存儲了層次聚類的聚類特征。分支因子定義為每個非葉節(jié)點孩子的最大數(shù)目，而閾值是指存儲在樹的葉子節(jié)點中的子聚類的最大直徑。

BIRCH方法由于采用了CF tree匯總一個類的有關(guān)信息，從而使一個類可以用對應的CF表示，而不必用具體的一組數(shù)據(jù)點表示，因此大大提高了聚類算法對大型數(shù)據(jù)庫的高效性和可擴展性，具有良好的聚類質(zhì)量。但該方法又受到了CF tree節(jié)點大小的限制，CF tree節(jié)點并不總是與用戶所認為的自然聚類相對應。而且，如果簇不是球形，BIRCH算法則不能很好地工作。

CURE采用了一種新的層次聚類方法，對k-means方法和k-medoids方法進行了折中，選擇了位于基于質(zhì)心和基于代表對象方法之間的中間策略。由于CURE方法選擇數(shù)據(jù)空間中一定數(shù)目的具有代表性的點來代表一個簇，因此該方法可以識別復雜形狀和大小不同的簇，而且能很好地過濾孤立點。然而該方法對用戶輸入的參數(shù)（如樣本大小、收縮因子a）具有敏感性，同時也需要用戶事先指明想要得到的聚類的數(shù)目。

（3）基于密度的方法

對于非球形的簇，用對象之間的距離來度量相似性是不夠的，因此為了發(fā)現(xiàn)任意形狀的簇，利用密度（數(shù)據(jù)或?qū)ο簏c的數(shù)目）來代替距離，提出了基于密度的聚類方法。該方法從數(shù)據(jù)對象的分布密度出發(fā)，將簇看成是由低密度區(qū)域分割開的高密度對象區(qū)域。

DBSCAN是一種典型的基于密度的方法，它通過檢查數(shù)據(jù)庫中每個點的e鄰域來進行聚類。其基本思想：檢查一個對象p的e鄰域的密度是否足夠高，即一定距離e內(nèi)數(shù)據(jù)點的個數(shù)是否超過臨界值minpts（minpts由用戶事先指定），如果p的e鄰域內(nèi)的數(shù)據(jù)個數(shù)多于minpts個點，則創(chuàng)建一個以p為中心點的新簇。然后DBSCAN反復的尋找從這些中心點直接密度可達的對象并將其添加到簇中，當沒有新的對象可以添加到任何簇中時，該過程結(jié)束。

DBSCAN用對象或數(shù)據(jù)點的數(shù)目表示類的密度，利用密度可達性來進行聚類，因此能很好的處理噪聲，此外該方法能發(fā)現(xiàn)空間數(shù)據(jù)庫中任意形狀的密度連通集，對數(shù)據(jù)的輸入順序也不太敏感。但是該方法中使用的e鄰域和閾值需要事先指定，參數(shù)的設置依賴于具體的應用。

（4）基于網(wǎng)格的方法

該方法采用一個多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，它首先將數(shù)據(jù)空間劃分成有限數(shù)目的單元，形成一個網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個的單元為對象。處理速度通常與目標數(shù)據(jù)庫中記錄的個數(shù)無關(guān)，它只與單元的個數(shù)有關(guān)，故這種方法的一個突出優(yōu)點就是處理速度很快。代表性算法有STING。

STING算法將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)：高層的每個單元被劃分為多個低一層的單元。高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的計算得到。

STING的執(zhí)行效率比較高，而且利于并行處理和增量更新。但是如果數(shù)據(jù)粒度比較細，算法處理的代價會明顯的增加；而且該算法沒有考慮子單元和其他相鄰單元之間的關(guān)系，盡管該算法處理速度較快，但是可能會降低簇的質(zhì)量和精確性。

（5）基于模型的方法

基于模型的方法為每個簇都假定了一個模型，并尋找數(shù)據(jù)對給定模型的最佳擬合。該方法通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來實現(xiàn)聚類。這種聚類方法試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學模型之間的適應性。

人工神經(jīng)網(wǎng)絡就是一種基于模型的聚類方法，是模擬生物神經(jīng)網(wǎng)絡的結(jié)構(gòu)和功能而設計的一種信息處理系統(tǒng)。人工神經(jīng)網(wǎng)絡方法將每個簇描述為一個標本，標本作為簇的原型，不一定對應特定的數(shù)據(jù)實例和對象。根據(jù)某些距離度量，新的對象可以被分配給標本與其最相似的簇。被分配給一個簇的對象的屬性可以根據(jù)該簇的標本的屬性來預測。

2 目前聚類分析研究的主要內(nèi)容

對聚類進行研究是數(shù)據(jù)挖掘中的一個熱門方向，由于以上所介紹的聚類方法都存在著某些缺點，因此近些年對于聚類分析的研究很多都專注于改進現(xiàn)有的聚類方法或者是提出一種新的聚類方法。以下將對傳統(tǒng)聚類方法中存在的問題以及人們在這些問題上所做的努力做一個簡單的總結(jié)：

（1）從以上對傳統(tǒng)的聚類分析方法所做的總結(jié)來看，不管是k-means方法，還是CURE方法，在進行聚類之前都需要用戶事先確定要得到的聚類的數(shù)目。然而在現(xiàn)實數(shù)據(jù)中，聚類的數(shù)目是未知的，通常要經(jīng)過不斷的實驗來獲得合適的聚類數(shù)目，得到較好的聚類結(jié)果。

（2）傳統(tǒng)的聚類方法一般都是適合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類，比如BIRCH方法對于球狀簇有很好的聚類性能，但是對于不規(guī)則的聚類，則不能很好的工作；K-medoids方法不太受孤立點的影響，但是其計算代價又很大。因此如何解決這個問題成為當前的一個研究熱點，有學者提出將不同的聚類思想進行融合以形成新的聚類算法，從而綜合利用不同聚類算法的優(yōu)點，在一次聚類過程中綜合利用多種聚類方法，能夠有效的緩解這個問題。

（3）隨著信息時代的到來，對大量的數(shù)據(jù)進行分析處理是一個很龐大的工作，這就關(guān)系到一個計算效率的問題。文獻提出一種基于最小生成樹的聚類算法，該算法通過逐漸丟棄最長的邊來實現(xiàn)聚類結(jié)果，當某條邊的長度超過了某個閾值，那么更長邊就不需要計算而直接丟棄，這樣就極大地提高了計算效率，降低了計算成本。

（4）處理大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)的能力有待于提高。目前許多聚類方法處理小規(guī)模數(shù)據(jù)和低維數(shù)據(jù)時性能比較好，但是當數(shù)據(jù)規(guī)模增大，維度升高時，性能就會急劇下降，比如k-medoids方法處理小規(guī)模數(shù)據(jù)時性能很好，但是隨著數(shù)據(jù)量增多，效率就逐漸下降，而現(xiàn)實生活中的數(shù)據(jù)大部分又都屬于規(guī)模比較大、維度比較高的數(shù)據(jù)集。文獻提出了一種在高維空間挖掘映射聚類的方法PCKA（Projected Clustering based on the K-Means Algorithm），它從多個維度中選擇屬性相關(guān)的維度，去除不相關(guān)的維度，沿著相關(guān)維度進行聚類，以此對高維數(shù)據(jù)進行聚類。

（5）目前的許多算法都只是理論上的，經(jīng)常處于某種假設之下，比如聚類能很好的被分離，沒有突出的孤立點等，但是現(xiàn)實數(shù)據(jù)通常是很復雜的，噪聲很大，因此如何有效的消除噪聲的影響，提高處理現(xiàn)實數(shù)據(jù)的能力還有待進一步的提高。

3 總結(jié)與展望

通過以上的分析可以看出，目前對于聚類的研究雖然成果很多，但是還不夠成熟，基本的理論方法還不夠完善，對實際的應用也還不夠廣泛，還需要對其作進一步的研究：

（1）繼續(xù)進行理論上的研究，尋求在理論上的改進和完善，提高各種方法的性能以及對現(xiàn)實數(shù)據(jù)的應用能力。

（2）尋求與其他學科的結(jié)合，尋找各學科之間的接口，完善現(xiàn)有的方法；并從其他學科獲得一些啟發(fā)，提出一些新方法，比如可以從代數(shù)拓撲中有關(guān)拓撲空間同倫等價的概念來研究聚類分析。

（3）增強聚類分析的應用能力，將其更廣泛的應用于實踐，為我們的生產(chǎn)生活提供便利，真正發(fā)揮其效能。

[1]賀玲，吳玲達，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計算機應用研究.2007.

[2]胡慶林，葉念渝，朱明富.數(shù)據(jù)挖掘中聚類算法的綜述[J].計算機與數(shù)字工程.2007.

[3]Jiawei Han，Micheline Kamber.Data Mining:Concepts and Techniques[M].機械工業(yè)出版社.2007.

[4]鄒志文，朱金偉.數(shù)據(jù)挖掘算法研究與綜述[J].計算機工程與設計.2005.