基于隨機(jī)投影的高維數(shù)據(jù)流聚類

朱穎雯 陳松燦

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106)2(模式分析與機(jī)器智能工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室(南京航空航天大學(xué)) 南京 211106)3(三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210012)(yingwen.zhu@nuaa.edu.cn)

隨著云計(jì)算、物聯(lián)網(wǎng)的快速發(fā)展，許多新型的應(yīng)用領(lǐng)域，諸如網(wǎng)絡(luò)入侵檢測、視頻監(jiān)控、氣象衛(wèi)星遙感以及電力供應(yīng)網(wǎng)等，每時(shí)每刻都在產(chǎn)生大量的數(shù)據(jù).這些數(shù)據(jù)并不事先存放在存儲(chǔ)介質(zhì)中，而是像水流一樣不斷出現(xiàn)，它們具有快速(high speed)、時(shí)序(temporally ordered)、海量(massive)等特征，被稱作數(shù)據(jù)流(data stream).

越來越多數(shù)據(jù)流的產(chǎn)生和應(yīng)用需求使得對于數(shù)據(jù)流的挖掘變得炙手可熱.挖掘數(shù)據(jù)流[1-9]的目的是從這些連續(xù)不斷的流數(shù)據(jù)中提取隱藏的知識結(jié)構(gòu).數(shù)據(jù)流挖掘技術(shù)包括數(shù)據(jù)流分類、數(shù)據(jù)流聚類、數(shù)據(jù)流關(guān)聯(lián)規(guī)則挖掘等.其中，數(shù)據(jù)流聚類是數(shù)據(jù)流學(xué)習(xí)的一項(xiàng)重點(diǎn)任務(wù)，它是將數(shù)據(jù)對象集合中相似對象劃分為一個(gè)或多個(gè)組(稱為“簇”，cluster)的過程，劃分后同一簇中元素彼此相似，但與其他簇中元素相異.不同于傳統(tǒng)的靜態(tài)數(shù)據(jù)聚類，數(shù)據(jù)流聚類面臨許多問題，例如：1)有限內(nèi)存(bounded memory)，數(shù)據(jù)流中的數(shù)據(jù)常是海量，所以不可能在內(nèi)存及硬盤上存儲(chǔ)整個(gè)數(shù)據(jù)流集；2)一次掃描(single-pass)，同樣因?yàn)閿?shù)據(jù)量巨大，傳統(tǒng)的多遍掃描方法不再適用，對其挖掘應(yīng)該是一個(gè)單遍掃描過程，且對流中數(shù)據(jù)元素的訪問只能單次線性(linear scan)，即只能按照流入順序依次讀取一次，無法進(jìn)行隨機(jī)訪問；3)實(shí)時(shí)響應(yīng)(real-time response)，多數(shù)應(yīng)用要求快速響應(yīng)，因此挖掘應(yīng)該是一個(gè)連續(xù)在線的過程；4)概念漂移(concept-drift detection)，數(shù)據(jù)分布常隨著時(shí)間的推移而發(fā)生變化.

目前，對于數(shù)據(jù)流聚類算法的研究已在學(xué)術(shù)界和工業(yè)界得到了廣泛關(guān)注，許多相關(guān)算法已被提出[10-26].現(xiàn)有數(shù)據(jù)流聚類算法均由傳統(tǒng)聚類算法擴(kuò)展而來，根據(jù)其所擴(kuò)展的傳統(tǒng)算法不同，我們可以將其分為5類：基于劃分的方法(STREAM[10])；基于層次的方法(CluStream[11],HPStream[12],SWClustering[13],E-Stream[14],REPSTREAM[15])；基于密度的方法(DenStream[16],ACSC[17],OPTICS-Stream[18],incPre-Decon[19])；基于網(wǎng)格的方法(D-Stream[20],MR-Stream[21],CellTree[22])；基于模型的方法(SWEM[23],GCPSOM[24],G-Stream[25],RPGStream[26]).表1分別針對6個(gè)特性對現(xiàn)有方法進(jìn)行總結(jié)：1)基算法；2)所用計(jì)算策略(在線學(xué)習(xí)或兩步學(xué)習(xí))；3)類簇個(gè)數(shù)是否自適應(yīng)；4)是否可挖掘拓?fù)浣Y(jié)構(gòu)；5)是否可檢測概念漂移；6)是否適合高維數(shù)據(jù).

如表1所示，基于劃分的數(shù)據(jù)流聚類方法相對簡單并易于實(shí)現(xiàn)，但其需要預(yù)先定義類簇個(gè)數(shù)，然而由于數(shù)據(jù)分布未知，類簇個(gè)數(shù)通常無法直接得到.此外，該方法無法檢測概念漂移.基于層次的數(shù)據(jù)流聚類方法雖然能夠發(fā)現(xiàn)有意義的類簇結(jié)構(gòu)，但其一般具有較高的計(jì)算代價(jià)，而且對流數(shù)據(jù)到達(dá)的順序敏感.基于密度的數(shù)據(jù)流聚類方法可以發(fā)現(xiàn)任意形狀的類簇，但是算法需要預(yù)設(shè)較多參數(shù).基于網(wǎng)格的數(shù)據(jù)流聚類方法運(yùn)行速度較快，也可以發(fā)現(xiàn)任意形狀的類簇，但是其聚類質(zhì)量取決于選取的網(wǎng)格粒度.基于模型的數(shù)據(jù)流聚類方法包含了很多領(lǐng)域知識并強(qiáng)依賴于假設(shè)模型，例如SWEM算法基于EM模型、GCPSOM算法基于SOM模型、G-Stream和RPG-Stream算法均基于GNG模型.從表1我們發(fā)現(xiàn)，在線(聯(lián)機(jī))學(xué)習(xí)算法是處理數(shù)據(jù)流聚類的一個(gè)很好策略，可以解決數(shù)據(jù)流約束中的一次掃描，實(shí)時(shí)響應(yīng)和有限內(nèi)存問題.STREAM[10]，REPSTREAM[15]，ACSC[17]，incPre-Decon[19]，SWEM[23]，GCPSOM[24]，G-Stream[25]和RPGStream[26]均為在線學(xué)習(xí)算法，但只有REPSTREAM，ACSC，SWEM，GCPSOM，G-Stream和RPGStream可以處理概念漂移，即此算法能夠隨著數(shù)據(jù)的流動(dòng)更新新來的概念并移除舊的概念.GCPSOM,G-Stream和RPGStream不僅可以解決數(shù)據(jù)流挖掘中的各類約束，同時(shí)可以發(fā)現(xiàn)數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，它們分別基于SOM(self-organizing maps)和GNG(growing neural gas)模型.但GCPSOM和G -Stream面對高維數(shù)據(jù)無能為力，據(jù)現(xiàn)有資料顯示只有HPStream[12],incPre -Decon[19]和RPGStream[26]可以處理高維數(shù)據(jù).RPGStream雖然可以處理高維數(shù)據(jù)，但因其基于GNG模型，超參數(shù)較多，調(diào)節(jié)參數(shù)對算法性能影響較大.故本文的直接動(dòng)機(jī)是設(shè)計(jì)一個(gè)可在單機(jī)執(zhí)行、適用于高維數(shù)據(jù)流的高效數(shù)據(jù)流聚類算法.

Table 1 Comparison of Various Data Stream Clustering Algorithms表1 數(shù)據(jù)流聚類算法比較

為解決高維數(shù)據(jù)流聚類問題(n和d均很大)，本文提出了一種基于隨機(jī)投影的高維數(shù)據(jù)流聚類算法RPFART.首先通過隨機(jī)投影將原始高維數(shù)據(jù)映射到低維數(shù)據(jù)空間，再使用ART模型[42]進(jìn)行數(shù)據(jù)流聚類.ART具有線性計(jì)算復(fù)雜度，且僅使用1個(gè)超參數(shù)，并對參數(shù)設(shè)置魯棒.雖然將隨機(jī)投影用于K-Means算法可以分析理論最差界，但由于ART本身的復(fù)雜性我們無法分析RPFART的最差界.所以，本文中我們使用大量實(shí)驗(yàn)分析RPFART算法的聚類性能.多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明:即使原始尺寸壓縮到10%，RPFART算法仍可以達(dá)到與RPGStream算法相當(dāng)甚至更好的性能.對于ACT1數(shù)據(jù)集，其維數(shù)從67 500減少到6 750.

1 相關(guān)工作

1.1 數(shù)據(jù)流聚類與ART

自組織神經(jīng)網(wǎng)絡(luò)是人工智能領(lǐng)域應(yīng)用最為廣泛的一種學(xué)習(xí)模型.為解決大部分神經(jīng)網(wǎng)絡(luò)模型遭遇的“穩(wěn)定性-彈性問題”，美國Boston大學(xué)的Grossberg和Carpenter于1976年提出了一種無監(jiān)督競爭型神經(jīng)網(wǎng)絡(luò)模型，即自適應(yīng)諧振理論網(wǎng)絡(luò)(adaptive resonance theory, ART)[43]，可在穩(wěn)定原有模式類的前提下學(xué)習(xí)新的模式.ART模擬了人類大腦如何捕捉、識別、記憶關(guān)于事物和事件的信息.隨著理論的不斷完善，學(xué)者們提出了大量基于ART改進(jìn)的無監(jiān)督學(xué)習(xí)模型，如ART1[44],ART2[45],ART2-A[46],ART3[47]和模糊ART(fuzzy ART)[42].模糊ART通過在類別空間實(shí)時(shí)搜索和匹配現(xiàn)有類簇，增長式地逐步處理每一個(gè)輸入模式，是本文研究的基本模型.警戒參數(shù)(vigilance parameter)用于約束在同一個(gè)類簇中模式的最小相似度.當(dāng)輸入模式與現(xiàn)有類簇都不相似時(shí)，則生成一個(gè)新的類簇來編碼這個(gè)新模式.模糊ART已用于解決圖像和文本挖掘問題，如Web文檔管理、基于標(biāo)記的Web圖像組織、圖像-文本關(guān)聯(lián)，但還未用于數(shù)據(jù)流聚類.

模糊ART模型由輸入層F1和識別層F2組成，如圖1所示.輸入層F1包含的輸入向量I被提交到網(wǎng)絡(luò)，與識別層F2中各個(gè)類簇的權(quán)值向量進(jìn)行相似度比較并歸類.

Fig.1 Fuzzy ART architecture圖1 模糊ART結(jié)構(gòu)

2) 權(quán)值向量(weight vector).設(shè)wj表示識別層F2中第j個(gè)類cj(j=1,2,…,J)的權(quán)值.

3) 參數(shù)(parameter).模糊ART隨著3個(gè)參數(shù)動(dòng)態(tài)改變，它們分別是選擇參數(shù)α>0、學(xué)習(xí)參數(shù)β∈[0,1]、以及警戒參數(shù)ρ∈[0,1].

模糊ART聚類過程包含3個(gè)關(guān)鍵步驟：

步驟1. 類別選擇(category choice).對每個(gè)輸入模式I，模糊ART根據(jù)選擇函數(shù)計(jì)算此輸入對識別層F2中的每個(gè)類簇的選擇值，并取具有最大值的類簇作為獲勝類簇cj*.第j個(gè)類簇cj的選擇函數(shù)定義為

(1)

步驟2. 模板匹配(template matching).輸入模式I與獲勝類簇cj*使用匹配函數(shù)Mj*進(jìn)行評估，Mj*定義為

(2)

如果獲勝類簇cj*的Mj*≥ρ，則發(fā)生共振(resonance)，引發(fā)步驟3——中心學(xué)習(xí).否則，返回步驟2，繼續(xù)在剩下的類簇中尋找一個(gè)獲勝類簇.如果所有選出的獲勝類簇均不滿足Mj*≥ρ，則生成一個(gè)新的類簇來編碼這個(gè)輸入模式I.

步驟3. 中心學(xué)習(xí)(prototype learning).如果獲勝類簇cj*的Mj*≥ρ，根據(jù)式(3)更新其權(quán)值向量wj*.

(3)

1.2 隨機(jī)投影

(4)

隨機(jī)投影的理論依據(jù)是JL引理[31]：高維歐氏空間里的點(diǎn)集映射到低維空間，其相對距離得到一定誤差范圍內(nèi)的保持.

(5)

這里參數(shù)ε控制距離保持的精度，β控制投影成功的概率.dc是一個(gè)正整數(shù)，且dc≥k0，隨機(jī)矩陣R是一個(gè)d×dc矩陣，R(i,j)=rij,rij是一個(gè)獨(dú)立的隨機(jī)變量，可以由3種概率分布生成：

rij～N(0,1);

(6)

(7)

(8)

對所有的u,v∈X，在至少1-n-β概率下:

(9)

從式(9)可以看出，理論上JL界(k0)不依賴于原始空間的維度d，為了得到定理1的結(jié)果，我們只需要通過一個(gè)簡單的概率分布生成隨機(jī)矩陣R，同時(shí)進(jìn)行投影計(jì)算.

通過假設(shè)輸入數(shù)據(jù)的期望為0，在主成分分析的激勵(lì)下，文獻(xiàn)[41]給出結(jié)論：根據(jù)概率上的方差分析，壓縮后的數(shù)據(jù)獲得了原始數(shù)據(jù)的全部可變性.首先，壓縮后的數(shù)據(jù)可以從低維數(shù)據(jù)中獲得很多信息，因?yàn)檫@些低維都是線性無關(guān)的.其次，原始數(shù)據(jù)維度的方差之和等于投影后數(shù)據(jù)維度的方差之和.

1) 投影數(shù)據(jù)的維度是相互獨(dú)立的.

Cov(Yi,Yj)=0,?i≠j;

2) 隨機(jī)投影保持了可變性.

利用上述性質(zhì)，已有相關(guān)工作驗(yàn)證了將隨機(jī)投影應(yīng)用于聚類問題的可行性.Boutsidis等人[33]首次將隨機(jī)投影與k-Means結(jié)合進(jìn)行聚類;吳等人[34]和Schneider等人[37]針對SLC和ALC聚類以及最小生成樹(MST)問題，探索了基于隨機(jī)投影的快速層次聚類算法.同時(shí)Schneider和Vlachos[38]通過使用隨機(jī)投影來擴(kuò)展基于密度的聚類，并提出了顯著提高學(xué)習(xí)效率的算法.Ferns和Brodley[39]、Cardoso和Wichert[40]、葉等人[41]提出了使用隨機(jī)投影對高維數(shù)據(jù)聚類的集成模型和迭代模型.

2 基于隨機(jī)投影的數(shù)據(jù)流聚類算法

2.1 RPFART算法

算法1.RPFART算法.

① 生成滿足定理1的隨機(jī)矩陣Rd×dc(dc?d);

② for eachxi

③yi=xi×R；

④ 對yi使用模糊ART算法進(jìn)行聚類；

⑤ end for

2.2 算法復(fù)雜度分析

算法1中最耗時(shí)的運(yùn)算是步驟③和步驟④.可以看出隨機(jī)投影在計(jì)算上非常簡單，可以快速生成，故步驟③的投影時(shí)間復(fù)雜度為O(nddc).模糊ART算法包含了類別選擇、模板匹配、中心學(xué)習(xí)3個(gè)主要步驟，每個(gè)步驟的時(shí)間復(fù)雜度分別為O(d)，O(md)，O(d)，給定n個(gè)輸入樣本，總體時(shí)間復(fù)雜度為O(nmd)，其中m是聚類結(jié)果中節(jié)點(diǎn)個(gè)數(shù).故步驟④的時(shí)間復(fù)雜度為O(nmdc).RPFART算法的總體時(shí)間復(fù)雜度為O(nddc+nmdc).

3 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證本文提出算法的有效性，我們在5個(gè)數(shù)據(jù)集上與現(xiàn)有數(shù)據(jù)流聚類算法RPGStream進(jìn)行了比較.實(shí)驗(yàn)使用的計(jì)算機(jī)配置為Intel Core i5-6300U 2.4 GHz處理器和8 GB內(nèi)存，Windows 10操作系統(tǒng)，所有比較程序均在MATLAB R2015a上設(shè)計(jì)和運(yùn)行.

3.1 聚類評價(jià)指標(biāo)

為了對各種聚類算法性能進(jìn)行評價(jià)，我們引入了3項(xiàng)評價(jià)指標(biāo)[26]：1)accuracy(purity);2)NMI(normalized mutual information);3)RI(rand index).

1) Accuracy(Purity)

(10)

2)NMI(normalized mutual information)

歸一化互信息NMI是一個(gè)量化2個(gè)分布之間共享統(tǒng)計(jì)信息的對稱策略.當(dāng)類簇標(biāo)簽和真實(shí)樣本類別一對一映射時(shí)NMI值到達(dá)最大值1.0.給定真實(shí)類簇A={A1,A2,…,Ak}和某聚類算法得到的類簇B={B1,B2,…,Bh}，混淆矩陣C中的元素Cij表示即在Ai又在Bj中的樣本個(gè)數(shù).NMI計(jì)算為

NMI(A,B)=

(11)

其中，CA(CB)表示A(B)中樣本個(gè)數(shù),Ci.(C.j)表示C中i行元素和(C中j列元素和)，N表示樣本個(gè)數(shù).

3)RI(rand index)

RI比較n×(n-1)/2個(gè)數(shù)據(jù)對，其中n為數(shù)據(jù)集中樣本個(gè)數(shù)，P1，P2為2種聚類算法，n11為數(shù)據(jù)對(xi,xj)在P1，P2中劃分為同一類的數(shù)據(jù)對數(shù)，n00則為(xi,xj)隸屬不同類的數(shù)據(jù)對數(shù)，RI錯(cuò)誤率計(jì)算為

(12)

由式(12)可得RI∈[0,1]，當(dāng)P1與P2劃分完全一致時(shí)RI=1.

3.2 數(shù)據(jù)集和參數(shù)設(shè)置

為了對RPFART算法的聚類有效性進(jìn)行評價(jià)，實(shí)驗(yàn)中我們使用了人工和真實(shí)數(shù)據(jù)集，表2給出數(shù)據(jù)集的相關(guān)信息：

Table 2 Statistics of Five Datasets表2 數(shù)據(jù)集

HyperPlan數(shù)據(jù)集是人工模擬數(shù)據(jù)集.HyperPlan是一個(gè)含有概念漂移的數(shù)據(jù)流，包含5個(gè)類共10萬個(gè)樣本，每個(gè)樣本5維.KddCup99，CoverType和ACT均來自UCI.KddCup99數(shù)據(jù)集最早來源于MIT林肯實(shí)驗(yàn)室的一項(xiàng)入侵檢測評估項(xiàng)目,記錄了9周內(nèi)TCP網(wǎng)絡(luò)連接和系統(tǒng)審計(jì)數(shù)據(jù),仿真各種不同的用戶類型、網(wǎng)絡(luò)流量和攻擊手段.這些原始數(shù)據(jù)包含約50萬條連接記錄的訓(xùn)練集.每個(gè)連接記錄包含41個(gè)屬性，這些連接記錄含1種正常的標(biāo)識類型和22種訓(xùn)練攻擊類型共23個(gè)類別.CoverType數(shù)據(jù)集來源于US Geological Survey (USGS)和US Forest Service (USFS)對位于Roosevelt國家森林的四片荒野區(qū)域的觀測.數(shù)據(jù)集中包含581 012條記錄,這些記錄最終被分為7種類型.每條觀測記錄包含54個(gè)地質(zhì)學(xué)和地理學(xué)屬性.ACT(The Daily and Sports Activities Data Set)數(shù)據(jù)集包含45個(gè)傳感器在5 min內(nèi)以25 Hz的采樣頻率收集的19項(xiàng)活動(dòng)的數(shù)據(jù).為了獲得高維數(shù)據(jù)集，我們分別將1 min和5 s的活動(dòng)數(shù)據(jù)處理為一個(gè)樣本，結(jié)果得到了760×67 500(ACT1)和9 120×5 625(ACT2)數(shù)據(jù)矩陣.

由算法1所示，RPFART算法需要設(shè)置警戒參數(shù)ρ和壓縮率r.RPGStream算法設(shè)置εb=0.01、εn=0.001、β=300(ACT1取30)、λ1=0.2、λ2=0.2、|windows|=600(ACT1取60)、|reservoir|=400(ACT1取50)、agemax=250(代表邊年齡的最大值)、weightmin=2(代表神經(jīng)元節(jié)點(diǎn)權(quán)值的最小值)，并且每次插入新節(jié)點(diǎn)的個(gè)數(shù)NbNodesInserted=3.

3.3 聚類性能比較

首先評估RPFART的聚類質(zhì)量，并將其與RPGStream算法在5個(gè)數(shù)據(jù)集上進(jìn)行比較.每個(gè)算法重復(fù)實(shí)驗(yàn)10次.聚類結(jié)果如表3～5所示.參數(shù)r表示壓縮率，例如對于KddCup99數(shù)據(jù)集，r=90%表示通過隨機(jī)投影將特征數(shù)減少到54×0.9=48.

從表3～5中我們可以發(fā)現(xiàn)：1)RPFART在使用了隨機(jī)投影后，總體上與RPGStream的結(jié)果相當(dāng)，特別是NMI和Rand指數(shù)在所有數(shù)據(jù)集上均超過了RPGStream.2)RPFART在HyperPlan和ACT2數(shù)據(jù)集上的聚類純度略低于RPGStream.3)即使設(shè)置一個(gè)小的r，例如r=10%，RPFART在ACT1上的聚類純度、NMI和Rand指數(shù)仍然是最好的.4)我們的算法不限于海量數(shù)據(jù)，即使對高維小樣本也可以得到很好的結(jié)果，如在ACT1數(shù)據(jù)集上取得了較好的效果.

Table 3 The Comparison Results of RPFART and RPGStream in Terms of Accuracy表3 RPFART(RPF)和RPGStream(RPG)在不同數(shù)據(jù)集上的聚類性能Accuracy比較

Table 4 The Comparison Results of RPFART and RPGStream in Terms of NMI表4 RPFART(RPF)和RPGStream(RPG)在不同數(shù)據(jù)集上的聚類性能NMI比較

Table 5 The Comparison Results of RPFART and RPGStream in Terms of Rand Index表5 RPFART(RPF)和RPGStream(RPG)在不同數(shù)據(jù)集上的聚類性能RI比較

為了進(jìn)一步證明RPFART的性能，我們分別在5個(gè)數(shù)據(jù)集上與離線聚類算法RPK-Means和PCAFART進(jìn)行了比較.PCAFART算法是將模糊ART與PCA結(jié)合對數(shù)據(jù)流進(jìn)行聚類.其結(jié)果如表6～8所示.

從表6～8中我們可以發(fā)現(xiàn)：1)RPFART在精度、NMI、Rand指數(shù)都優(yōu)于KddCup99，CoverType，ACT2，ACT1數(shù)據(jù)集上的RPK-Means.2)RPFART與PCAFART具有相當(dāng)?shù)木垲惤Y(jié)果，但后者在處理高維ACT1數(shù)據(jù)集時(shí)，出現(xiàn)內(nèi)存耗盡溢出問題.因此，我們可以得出RPFART更適合于高維數(shù)據(jù)，同時(shí)結(jié)合隨機(jī)投影和模糊ART是可行和有前途的.此外，RPFART的方差比其他方法略小，這表明它相對穩(wěn)定.除了隨機(jī)投影，PCA也可以用來降維，但當(dāng)我們想將PCA與模糊ART結(jié)合用于ACT1數(shù)據(jù)集時(shí)，算法因?yàn)閮?nèi)存不足而停止.

Table 6 The Comparison Results of RPFART, RPK-Means and PCAFART in Terms of Accuracy表6 RPFART(RPF)和RPK-Means(RPK), PCAFART(PCAF)在不同數(shù)據(jù)集上的聚類性能Accuracy比較

Table 7 The Comparison Results of RPFART, RPK-Means and PCAFART in Terms of NMI表7 RPFART(RPF)和RPK-Means(RPK), PCAFART(PCAF)在不同數(shù)據(jù)集上的聚類性能NMI比較

Table 8 The Comparison Results of RPFART, RPK-Means and PCAFART in Terms of RI表8 RPFART(RPF)和RPK-Means(RPK), PCAFART(PCAF)在不同數(shù)據(jù)集上的聚類性能RI比較

3.4 運(yùn)行時(shí)間比較

圖2顯示了r=50%時(shí)的5個(gè)數(shù)據(jù)集上RPFART和RPGStream的運(yùn)行時(shí)間.

Fig. 2 Execution time(in seconds)圖2 運(yùn)行時(shí)間比較

從圖2可以看出：1)RPFART和RPGStream的執(zhí)行時(shí)間都隨著數(shù)據(jù)量的增加而增加.2)隨著樣本數(shù)的增加RPFART比RPGStream更快.研究表明，RPFART算法對大規(guī)模、高維數(shù)據(jù)的處理效率更高.

3.5 隨機(jī)矩陣的選擇

由于RPFART是基于隨機(jī)投影的，所以直觀地說，隨機(jī)矩陣R的類型選擇將在一定程度上對聚類性能產(chǎn)生影響.因此，為分析其影響，我們使用不同類型的隨機(jī)矩陣進(jìn)行實(shí)驗(yàn)，典型的有高斯分布(式(6))、均勻分布(式(7))和稀疏分布(式(8))隨機(jī)矩陣.我們還利用Gram Schmidt方法對上述隨機(jī)矩陣進(jìn)行正交實(shí)驗(yàn).所有實(shí)驗(yàn)均在HyperPlan,Kddcup99,CoverType,ACT2上進(jìn)行，重復(fù)10次，r=50%.結(jié)果如表9所示.結(jié)果表明，正交后RPFART算法在聚類純度、NMI和Rand指數(shù)上比非正交算法較優(yōu).然而，正交化并不免費(fèi)，計(jì)算上十分昂貴.有趣的是，Hecht-Nielsen[48]證明高維空間中存在大量幾乎正交(而不是嚴(yán)格正交)的方向，即具有隨機(jī)方向的一系列向量同樣可以是有效正交，從而其可作為一組基的近似.

Table 9 Performance of Clustering Algorithms with Different Random Matrix表9 不同隨機(jī)矩陣對RPFART的影響

3.6 處理非平穩(wěn)數(shù)據(jù)能力

本節(jié)研究RPFART在非平穩(wěn)數(shù)據(jù)流聚類中的有效性.許多實(shí)際應(yīng)用程序中，數(shù)據(jù)通常隨著時(shí)間演變，即具有非平穩(wěn)性.例如，第1個(gè)類的數(shù)據(jù)點(diǎn)全部到達(dá)后，第2個(gè)、第3個(gè)類的數(shù)據(jù)點(diǎn)才依次按類別到達(dá).這種情況下，舊的概念消失，同時(shí)新的概念隨著新的數(shù)據(jù)點(diǎn)的到來而出現(xiàn)，從而導(dǎo)致概念漂移.因此我們分別將RPFART在類排序(按類標(biāo)簽)和類未排序的數(shù)據(jù)流上進(jìn)行聚類，重復(fù)實(shí)驗(yàn)10次.圖3～5顯示了RPFART的聚類純度、NMI和Rand指數(shù).

Fig. 3 Accuracy of RPFART with and without ordering of classes圖3 RPFART在類排序與類未排序數(shù)據(jù)集上的聚類純度

Fig. 4 NMI of RPFART with and without ordering of classes圖4 RPFART在類排序與類未排序數(shù)據(jù)集上的NMI

Fig. 5 Rand index of RPFART with and without ordering of classes圖5 RPFART在類排序與類未排序數(shù)據(jù)集上的Rand指數(shù)

從圖中可以看出：1)RPFART在類排序數(shù)據(jù)集上可以找到與類未排序數(shù)據(jù)集上相當(dāng)?shù)木垲惣兌取MI和Rand指數(shù).特別是ACT2和ACT1數(shù)據(jù)集上甚至更優(yōu).2)僅KddCup99數(shù)據(jù)集上RPFART的聚類純度值略有下降.基于以上結(jié)果，我們可以得出結(jié)論，不管數(shù)據(jù)是否按類標(biāo)簽排序到達(dá)，RPFART均可以有效地處理概念漂移問題.

3.7 警戒參數(shù)ρ的變化

圖6顯示了r=50%時(shí)RPFART在5個(gè)數(shù)據(jù)集上隨警戒參數(shù)ρ的變化聚類性能的變化.

從圖6可以看出：1)5個(gè)數(shù)據(jù)集上聚類純度均隨參數(shù)ρ的增大到達(dá)一定值后有所下降；2)在HyperPlan,CoverType,ACT2這3個(gè)數(shù)據(jù)集上NMI和Rand指數(shù)都隨參數(shù)ρ的增大穩(wěn)步增長，但KddCup99和ACT1數(shù)據(jù)集有下降趨勢.

Fig. 6 Sensitivity of RPFART to vigilance value圖6 警戒參數(shù)對RPFART算法影響

4 結(jié) 論

本文基于隨機(jī)投影提出了高維數(shù)據(jù)流聚類算法RPFART.首先通過隨機(jī)投影將原始高維數(shù)據(jù)映射到低維數(shù)據(jù)空間，再使用ART模型進(jìn)行數(shù)據(jù)流聚類.ART具有線性計(jì)算復(fù)雜度，僅使用1個(gè)超參數(shù)，并對參數(shù)設(shè)置魯棒.文中使用大量實(shí)驗(yàn)分析RPFART算法的聚類性能.多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，即使原始尺寸壓縮到10%，RPFART算法仍可以達(dá)到與RPGStream算法相當(dāng)甚至更好的性能.對于ACT1數(shù)據(jù)集，其維數(shù)從67 500減少到6 750.