數(shù)據(jù)挖掘?qū)哟尉垲愃惴ㄑ芯烤C述

1、數(shù)據(jù)挖掘?qū)哟尉垲愃惴ㄑ芯烤C述摘 要 聚類問題是數(shù)據(jù)挖掘中的重要問題之一，是一種非監(jiān)督的學(xué)習(xí)方法。分層聚類技術(shù)在圖像處理、入侵檢測和生物信息學(xué)等方面有著極為重要的應(yīng)用，是數(shù)據(jù)挖掘領(lǐng)域的研究熱點之一。本文總結(jié)了分層聚類算法技術(shù)的研究現(xiàn)狀，分析算法性能的主要差異，并指出其今后的發(fā)展趨勢。關(guān)鍵詞 層次聚類，數(shù)據(jù)挖掘，聚類算法 Review of hierarchical clustering algorithm in Data MiningAbstract Clustering problem of data mining is one of important issues, it is a kin

2、d of unsupervised learning methods. Stratified cluster technology in image processing, intrusion detection and bioinformatics has extremely important application and is data mining area of research one of the hotspots. This paper summarizes the layered clustering algorithm technology research, analy

3、zes the main difference arithmetic performance, and pointed out the future development trend.Keywords Hierarchical clustering，Data mining，Clustering algorithm1引言隨著計算機技術(shù)的發(fā)展，信息數(shù)據(jù)越來越多，如何從海量數(shù)據(jù)中提取對人們有價值的信息已經(jīng)成為一個非常迫切的問題。由此產(chǎn)生了數(shù)據(jù)挖掘技術(shù)，它是一門新興的交叉學(xué)科，匯集了來自機器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能等各領(lǐng)域的研究成果。聚類分析是數(shù)據(jù)挖掘中的一個重要研究領(lǐng)域。它在圖像處

4、理、入侵檢測和生物信息學(xué)等方面有著極為重要的應(yīng)用。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取出可信、 新穎、 有效并能被人理解的模式的高級處理過程。 其目標(biāo)是從數(shù)據(jù)庫中發(fā)現(xiàn)隱含的、 有意義的知識。聚類分析作為一個獨立的工具來獲得數(shù)據(jù)分布的情況，是數(shù)據(jù)挖掘的一個重要研究分支。 在數(shù)據(jù)挖掘領(lǐng)域，研究工作己經(jīng)集中在為大型數(shù)據(jù)庫的有效和實際的聚類分析尋找適當(dāng)?shù)姆椒??；钴S的主題集中在聚類方法的可伸縮性，方法對聚類復(fù)雜形狀和類型的數(shù)據(jù)的有效性，高維聚類分析技術(shù)，以及針對大型數(shù)據(jù)庫中混合數(shù)值和分類數(shù)據(jù)的聚類方法。迄今為止， 人們己經(jīng)提出了很多聚類算法， 它們可以分為如下幾類：劃分方法、 層次方法、 基于密度的方法、 基于網(wǎng)

5、格的方法和基于模型的方法，這些算法對于不同的研究對象各有優(yōu)缺點。在聚類算法當(dāng)中， 劃分方法和層次方法是最常見的兩類聚類技術(shù)，其中劃分方法具有較高的執(zhí)行效率，而層次方法在算法上比較符合數(shù)據(jù)的特性，所以相對于劃分方法聚類的效果比較好。1層次聚類算法和基于劃分的K-Means聚類算法是實際應(yīng)用中聚類分析的支柱，算法簡單、快速而且能有效地處理大數(shù)據(jù)集。層次聚類方法是通過將數(shù)據(jù)組織為若干組并形成一個相應(yīng)的樹來進行聚類的。根據(jù)層是自底而上還是自頂而下形成。一個完全層次聚類的質(zhì)量由于無法對己經(jīng)做的合并或分解進行調(diào)整而受到影響。但是層次聚類算法沒有使用準(zhǔn)則函數(shù)，它所潛含的對數(shù)據(jù)結(jié)構(gòu)的假設(shè)更少，所以它的通用性更

6、強。2 基于層次的聚類算法2.1 凝聚的和分裂的層次聚類層次聚類是聚類問題研究中一個重要的組成部分。分層聚類的基本原則可以表述為：如果輸入n個數(shù)據(jù)點(或數(shù)集)，我們定義n個數(shù)簇，其中每個簇含一個數(shù)據(jù)。確定距離（簇與簇之間的距離可以通過很多的方法來定義，最常用的是單連接度量。其定義兩個簇之間的距離為一個簇中所有成員與另一簇中所有成員之間的最短距離。）層次化聚類算法可以進一步地分為兩類：凝聚和分裂。凝聚算法：在每層選擇兩個最相似的簇被合并，合并后的簇在更高層參與類似的合并。分裂算法：它首先把整個數(shù)據(jù)集看成一個簇，然后依據(jù)數(shù)據(jù)集的特性在每一層分成越來越小的簇。非層次化方法的聚類算法也有很多，其中，K

7、-Means算法是最經(jīng)典的，還有K-Means的變種。層次化聚類算法就是將數(shù)據(jù)對象組成一棵聚類的樹。根據(jù)層次分解是自底向上生成還是頂向下生成，層次的聚類方法可以細分為凝聚的和分裂的層次聚類。凝聚的層次聚類：凝聚的層次聚類是自底向上的策略。首先將每個對象作為一個類，然后合并這些原子類為越來越大的類，直到所有的對象都在一個類中，或者某個終結(jié)條件被滿足。分裂的層次聚類是種自頂向下的策略與凝聚的層次聚類相反，它首先將所有對象置于一個類中，然后逐漸細分為越來越小的類，直到每個對象自成一類，或者達到了某個終結(jié)條件，例如達到了某個希望的類數(shù)目，或者兩個最近的類之間的距離超過了某個閩值。絕大多數(shù)聚類方法屬于這

8、一類，它們只是在簇間相似度的定義有所不同。分裂的層次聚類：這種自頂向下的策略與凝聚的層次聚類相反，它首先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終止條件，例如達到了某個希望的簇數(shù)目，或者兩個最近的簇之間的距離超過了某個閥值。層次化聚類方法盡管簡單，但如何恰當(dāng)?shù)剡x擇合并或分裂點，是個很困難的工作，這樣的選擇是非常關(guān)鍵的，因為一旦一組對象被合并或者分裂，下一步的處理將在新生成的簇上進行。已做的處理不能被撤消，聚類之間也不能交換對象。如果在某一步?jīng)]有很好的選擇合并或者分裂的決定，可能會導(dǎo)致低質(zhì)量的聚類結(jié)果。而且，這種聚類方法不具有很好的可伸縮性，因為合

9、并或者分裂的決定需要檢查和估算大量的對象或簇。22.2 改進的層次聚類算法基本思想按照原層次聚類算法，當(dāng)依照最小距離d（i，j）合并了第i和第j簇后，必須重新計算新合并的簇d（i，j）和原有簇的距離，按照最小距離的計算方法，d(k)，(r，s)=min d(k)，(r)，d(k)，(s)，其中d(k)，(r)與d(k)，(s)來源于初始化的距離矩陣，也就是說d(k)，(r，s)的值必然也就是初始化距離矩陣中的某個值，同理，當(dāng)合并了一個簇后，新的距離矩陣?yán)锏乃兄狄簿投际莵碓从诔跏蓟木嚯x矩陣，當(dāng)然新的距離矩陣內(nèi)的最小值也來源于初始化的距離矩陣。層次聚類算法是按照最短距離法來進行層次聚類的，當(dāng)?shù)?/p>

10、一次合并了其中最小的一個d(i，j)后，產(chǎn)生了新的距離矩陣，由于新的距離矩陣中的所有值均來源于初始化的距離矩陣，再從新的距離矩陣中取最小值，那么這個最小值必定是除了第一次合并后的最小值外，初始化距離矩陣中的次小值。也就是說，假定我們合并掉了初始化距離矩陣中的最小值后，下一個要合并的必定就是初始化距離矩陣中的次小值，依次遞推下去，直到所有的簇都被合并完為止。2.3 改進的層次聚類算法改進層次算法的聚類質(zhì)量的一個主要方向是將層次聚類和其他的聚類技術(shù)進行集成，形成多階段聚類，許多學(xué)者在基于多階段聚類方法的思想之上提出了幾種經(jīng)典的層次聚類方法的改進算法。這里主要講BIRCH算法，它首先用樹結(jié)構(gòu)對對象進

11、行層次劃分，然后采用其他的聚類算法對聚類結(jié)果進行求精。4BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法是一個集成的層次聚類方法。它包含兩個重要概念：聚類特征(CF)和聚類特征樹(CF tree)，它們用于概括聚類描述。這些結(jié)構(gòu)輔助聚類方法在大型數(shù)據(jù)庫中取得更快的速度和可伸縮性。BIRCH算法對增量或動態(tài)聚類也非常有效。一個聚類特征CF是一個三元組，給出了對象子聚類的信息的匯總描述。假設(shè)某個子聚類中有N個d維數(shù)據(jù)或?qū)ο?。則該子聚類的CF=(N，LS，SS)其中，N為該子聚類所含對象個數(shù)；LS為這N個點的和

12、，SS為數(shù)據(jù)點的平方和。聚類特征基本上就是對給定子聚類統(tǒng)計信息的總結(jié)。它包含了聚類計算和空間存儲利用所需要的關(guān)鍵信息。如圖2.1所示，一個CF樹是高度平衡的樹，它存儲了層次聚類的聚類特征。樹中的非葉子節(jié)點有后代或“孩子”，它們存儲了其孩子的CF的總和，即匯總了關(guān)于其孩子的聚類信息。一個CF樹有兩個參數(shù)：分支因子B和閾值T。分支因子定義了每個非葉子節(jié)點孩子的最大數(shù)目，而閾值參數(shù)給出了存儲在樹的葉子節(jié)點中的子聚類的最大直徑。這兩個參數(shù)直接影響了結(jié)果樹的大小。CF1 CF2 CFK根CF1 CF2 CFK第一層圖2.1 CF樹示意圖BIRCH方法工作主要包括兩個階段：階段一：BIRCH掃描數(shù)據(jù)庫，建

13、立一個初始存放于內(nèi)存的CF樹，它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。階段二：BIRCH采用某個聚類算法對CF樹的葉子節(jié)點進行聚類。在階段一，隨著對象被插入，CF樹被動態(tài)地構(gòu)造。所以這個方法支持增量聚類。一個對象被插入到最近的葉子條目(子聚類)。如果在插入后存儲在葉子節(jié)點中的子聚類的直徑大于閾值。那么該葉子節(jié)點(及可能有其他節(jié)點)被分裂。新對象插入后，關(guān)于該對象的信息向著樹根傳遞。通過修改閾值，CF樹的大小可以改變。如果存儲CF樹需要的內(nèi)存大于主存的大小，可以定義一個較小的閾值，并重建CF樹。重建過程從舊樹的葉子節(jié)點建造一個新樹。這樣，重建樹的過程不需要重讀所有的對象。因此，為

14、了建樹，只需讀一次數(shù)據(jù)。BIRCH采用一些啟發(fā)式的規(guī)則和方法，通過額外的數(shù)據(jù)掃描來處理孤立點和改進CF樹的質(zhì)量。CF樹建好后，可以在階段二被用于任何聚類算法。BIRCH試圖利用可用的資源來生成最好的聚類結(jié)果。給定有限的主存，一個重要的考慮是最小的I/0時間。BIRCH采用了一種多階段聚類技術(shù)：數(shù)據(jù)集合的單遍掃描產(chǎn)生了一個基本的聚類，一遍或多遍的額外掃描可以進一步地改進聚類質(zhì)量。這個算法的計算復(fù)雜性是O(n)，這里的n是對象的數(shù)目。53 總結(jié)現(xiàn)有聚類算法的分類研究還需要繼續(xù)深入，在數(shù)據(jù)挖掘的理論及應(yīng)用實踐中，人們已經(jīng)提出了許多聚類算法，但到目前為止仍沒有普遍適用的聚類算法，每種方法在具有某種優(yōu)點的同時也存在著某些不足，可能適合于處理某些問題卻無法處理另一類情況。這就給人們的選擇使用帶來了不便，往往會出現(xiàn)面對浩瀚的聚類算法，卻不知道哪個可用的困境。因此，需要對現(xiàn)有聚類算法本身進行分類處理為用戶的