劉曉璐，王志棟，單廣榮

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

0 引言

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

1 聚類概述

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

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

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

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

（4）輸入?yún)?shù)：許多算法中需要人為輸入?yún)?shù)，參數(shù)輸入不當會給聚類造成很大影響。

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

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

（7）高維性：數(shù)據(jù)具有高維性。

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

2 聚類算法

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

2.1 基于劃分的聚類算法

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

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

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

2.2 基于層次的聚類算法

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

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

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

2.3 基于密度的聚類算法

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

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

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

2.4 基于網(wǎng)格的聚類算法

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

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

3 結(jié)語

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