傳統(tǒng)與流數據聚類算法

劉曉璐，王志棟，單廣榮

（1.西北民族大學，甘肅省民族語言智能處理重點實驗室，蘭州 730030；2.大連交通大學機車車輛工程學院，大連 116028）

0 引言

數據流挖掘是指從大量連續(xù)生成的數據中發(fā)現(xiàn)知識的過程[8]。數據流挖掘過程多數采用聚類算法。聚類，是將一個數據集對象進行分類的過程，在這個過程中，我們通過對比一些性能將相似的對象進行分類。如在市場分析中，從客戶大數據庫中劃分客戶群，需要根據不同客戶的不同需求等特征進行客戶群劃分[4-5]；其次在生物學動植物分類中，通過基因的分類來認識種群中的固有結構等都是聚類的典型應用，都需要聚類算法聚類進行特征提取[6-9]。因此本文針對一些傳統(tǒng)聚類算法以及流數據聚類算法進行分析和總結。

1 聚類概述

聚類在進行分類時不依賴預先定義的類以及一些標記，而是根據相似度進行分類。一些未被處理的數據作為輸入數據進行聚類任務處理，處理結果希望在類之間的相似度盡可能地低，類內相似度盡量地高。例如將聚類運用到股票系統(tǒng)中，投資者和股民可以利用聚類后的結果進行預判，選擇合適的股票，如將一些相似波動情況的股票劃為一類，并按照其不同的特征再進行分類，方便股民參考。聚類不僅可以用于樣本分類，還可以用于網絡欺詐風險預估等[9]。

聚類在進行數據挖掘時，必須具備以下的特點：

（1）可伸縮性：有處理不同大小數據集的能力。

（3）發(fā)現(xiàn)任意形狀的聚類：既要能處理凸型簇也要能處理非凸型簇。

（4）輸入參數：許多算法中需要人為輸入參數，參數輸入不當會給聚類造成很大影響。

（5）對有損數據的處理：原始數據中會出現(xiàn)有損數據，需要進行有效處理，保證聚類質量[10]。

（6）對數據輸入順序不敏感：對某些算法當輸入順序改變時，算法效果會產生相應的變化，不利于最終結果[11]。

（7）高維性：數據具有高維性。

（8）基于約束的聚類：找到事物的主要屬性進行聚類。

2 聚類算法

在本文中，主要介紹傳統(tǒng)聚類算法[12]以及流數據聚類算法[13-14]，在介紹時，將會選取該種類的幾個算法進行大致介紹以了解不同類型的聚類算法。下面將介紹基于劃分、基于層次、基于密度和基于網格的傳統(tǒng)與流數據聚類算法。

2.1 基于劃分的聚類算法

基于劃分的傳統(tǒng)聚類算法，就是將數據集進行分組的過程，其中一組只包含一個對象，一個對象只屬于一個組[15]。K-means 算法[16-17]的基本思想是：確定 k 個簇中心，按照距離分配其他樣本點，直至全部分配完成后重新確定簇心，再次分配，即不斷重復此過程，直到簇心不變化或者樣本點不變化為止[16]。K-means 算法適用于簇狀為凸的數據，處理效率高；但是，此算法對異常數據較為敏感并且需要人為指定簇數目，僅僅試用于簇狀為凸面數據，限制聚類屬性，使用范圍較小，常常終止于局部最優(yōu)。因此，基于K-means 算法提出了二分K-means，使算法終止于全局最優(yōu)[17]。并且為了改善K-means 算法對聚類屬性限制的缺點，提出了K-medoids[18-19]。該算法第一步與K-means 算法相同，先隨機確定k 個中心點，之后通過其他樣本點與該中心點距離進行樣本點分配，全部分配完成后不斷通過非中心點替代中心點，提高最終聚類結果。K-中心點算法相較于K-means 算法而言沒有對聚類屬性的限制，且對噪聲、異常數據不敏感，但是該算法較為耗時，也需要事先指定簇中心數目。

模型(3)仍為非線性規(guī)劃模型，與模型(1)和(2)最大的區(qū)別在于不再是基于設備的可利用生產時間來構成約束條件，而是基于設備的可用數量來構成約束條件，以此反映出從生產設備的數量方面進行最優(yōu)分配和調度．

流數據聚類STREAM 算法基于K-means 算法提出，用于處理數據流。該算法每次只處理m 個數據，對m 個數據進行聚類形成k 個簇，此時僅保留簇中心而丟棄其余數據，其中k 個簇中心會通過權值來記錄每個簇中的數據點的個數。隨著數據流的進入，STREAM算法仍保持每次處理m 個數據。STREAM 算法與傳統(tǒng)的聚類算法如BIRCH 相比，能產生質量更高的聚類結果。由于其沒有對數據流變化以及時間進行考慮，導致不能及時更新近期數據流對聚類結果的影響以及不能展現(xiàn)不同時間粒度產生的不同聚類結果[16]。

2.2 基于層次的聚類算法

層次法基本原理是將每一個樣本點視為一個類，按距離進行聚類，對形成的類再次按距離進行聚類，不斷重復此過程直到只有一個大類為止[20]。

BIRCH 算法中包含兩步，首先是構建聚類特征樹，聚類特征樹中包含了數據對象的所有屬性；得到特征樹后通過其他算法對其進行聚類[21]。BIRCH 有以下的優(yōu)缺點，首先該算法只需要存儲節(jié)點和地址，對于數據本身不需要存儲，因此節(jié)約存儲空間[22]；其次由于該算法在構建特征樹時只需要依次掃描，因此速度較快[23]。該算法還可以識別噪聲點，完成數據預處理。但是該算法也存在一些缺點，首先BIRCH 算法在特征樹上可以存儲的特征有限，會導致聚類結果不準確，因此該算法不適合于高維數據聚類；其次當數據的簇狀不是凸面時，聚類效果也不好。因此，基于上述缺點提出CURE 算法[24]改善其缺點，使其可以更好地處理大數據且識別噪聲能力強。

基于層次的流數據聚類CluStream 算法[25]，該算法能夠完全適應數據流快速到達的特點并且能夠挖掘出數據流的潛在演化特征，產生球形的聚類結果；由于其對于噪聲數據敏感，每當出現(xiàn)異常數據時算法將會出現(xiàn)不穩(wěn)定性；隨著噪聲數據增加，微簇數量也會增加，該算法限制微簇數量，由此必須進行合并刪減，降低了算法聚類結果的準確度。

2.3 基于密度的聚類算法

基于密度的聚類算法整體思想是基于密集數據點進行處理，數據空間中的每一簇都是由很多密集數據點組成，并被稀疏區(qū)域劃分，通過從稀疏區(qū)域中找到密集數據點，并將稀疏區(qū)域視為噪聲點，從而進行數據集的處理。

DBSCAN 算法[26-27]尋找密集數據點過程是：首先需要隨機確定一個點，找出與此點距離小于等于掃描半徑的所有附近點，若所有附近點的數量大于等于最小包含點數，則將此點與其找出的所有點形成一個簇，并將此點標記為已訪問的點。按照上述過程遞歸訪問所有的未被標記的點，從而不斷擴展簇。DBSCAN 算法可以發(fā)現(xiàn)任意形狀的簇，并且在使用聚類算法時不需要指定最終形成的簇值k[25]，其次該算法不會受到噪聲點的干擾，可以擺脫噪聲點的干擾。該算法面對高維數據時效果不是很好，在樣本數據分布不均勻的情況下，聚類質量都會相應降低。

基于密度的流數據聚類DenStream 算法[13]，主要思想是基于CluStream 算法的聯(lián)機、脫機結構加入潛在微簇（p-micro-cluster）和孤立點微簇（o-micro-cluster）兩種結構，通過簇密度與閾值的比較區(qū)分兩種微簇結構，若其密度小于給定閾值，則說明是孤立點微簇。算法開始時，進行數據合并，首先嘗試合并至潛在微簇中，若不成功，則合并在微簇結構中。若成功，則進行微簇類型的轉換，只有簇密度大于閾值，才能將孤立點微簇轉化為潛在微簇。若合并失敗，則建立孤立點微簇以存儲此數據。在脫機部分，則直接使用DBSCAN 算法對兩類微簇進處理，得到聚類結果。DenStream 算法通過兩種微簇結構可以進行邊緣數據和真實數據的區(qū)分，成為了現(xiàn)在基于流數據聚類算法的主流方法。但是由于合并失敗時創(chuàng)建的微簇數量不斷增加將會導致所占內存較大，并且在判斷并移除邊緣值時計算量較大。

2.4 基于網格的聚類算法

CLIQUE 算法在給定分布情況不均衡的大數據集中，進行稀疏、密集區(qū)域的區(qū)分，將區(qū)分后相連的密集區(qū)域作為簇，由此完成聚類過程。其中稀疏區(qū)域和密集區(qū)域區(qū)分通過其內數據點是否超過給定模型參數來決定，若數據點個數超過此參數，則這個區(qū)域就是密集區(qū)域。因此，CLIQUE 算法對處理大數據集具有高效性并且對異常數據不敏感，另外，當數據輸入順序改變時，聚類結果不會受到影響。

基于網格流數據聚類D-Stream 算法，此算法整個聚類過程與密度息息相關，該算法在聚類過程中也分為兩個部分，即聯(lián)機部分和脫機部分，聯(lián)機部分是將流數據映射到網格中，脫機部分根據密度進行聚類，在第一個時間隙后，脫機部分根據網格密度形成第一個初始簇，之后在每個時間隙后對當前簇進行調整。DStream 算法在聚類過程中不依賴于查詢，每一個單元中都有對應的信息匯總，因此其效率較高，速度快并且不限制數據形狀，運用范圍廣。其缺點是網格質量決定聚類質量，當網格粒度小，較為精細，這樣產生的聚類效果也好，同樣的聚類花費代價大；相同而言，當網格粒度大時，對應的聚類效果也會降低。并且此算法只考慮了網格水平垂直方面的關系，沒有考慮到與其他相鄰單元的關系，也會造成聚類質量的降低。

3 結語

聚類研究工作一直以來在圖像處理、人工智能、數據挖掘領域都受到高度重視，現(xiàn)有的聚類算法都存在一些缺陷，不能滿足現(xiàn)實應用，因此聚類算法研究從未停止，很多研究工作都希望能夠提出新算法進行使用。如本文前面所述，無論是基于劃分的K-means 算法還是基于層次的CURE 算法都需要事先指定簇數目進行聚類，但是我們發(fā)現(xiàn)，在實際應用以及實驗中，簇數目是未知的，需要根據實驗過程而確定，因此針對此方面的缺陷依舊需要不斷研究。再者來說，我們已有的任何聚類算法都是針對某種情況而言，沒有一種算法適用于任何情況，因此，此方面也是聚類研究的熱點問題。大數據時代，需要處理的數據量及其龐大，而目前的一些算法僅僅適用于小規(guī)模數據和低維數據，因此，既能夠處理大規(guī)模數據而且處理速度快，效率高的聚類算法對現(xiàn)有應用是及其迫切的。目前很多聚類算法仍處于理論階段，我們在進行實驗時需要假設某些條件，在實際應用方面仍然需要進一步提高。