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

劉曉璐，王志棟，單廣榮

（1.西北民族大學(xué)，甘肅省民族語言智能處理重點(diǎn)實(shí)驗(yàn)室，蘭州 730030；2.大連交通大學(xué)機(jī)車車輛工程學(xué)院，大連 116028）

0 引言

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

1 聚類概述

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

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

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

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

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

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

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

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

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

2 聚類算法

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

2.1 基于劃分的聚類算法

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

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

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

2.2 基于層次的聚類算法

層次法基本原理是將每一個(gè)樣本點(diǎn)視為一個(gè)類，按距離進(jìn)行聚類，對(duì)形成的類再次按距離進(jìn)行聚類，不斷重復(fù)此過程直到只有一個(gè)大類為止[20]。

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

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

2.3 基于密度的聚類算法

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

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

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

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

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

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

3 結(jié)語

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