基于PCA的高維流式數(shù)據(jù)聚類算法

張?jiān)讫?/p>

摘要：本文的基于PCA的高維流式數(shù)據(jù)聚類算法是在D-Stream算法的基礎(chǔ)上提出來的。首先，從基本原理上分析了D-Stream算法在高維網(wǎng)格劃分時(shí)，存在著大量計(jì)算，影響算法效率;其次，對于高維數(shù)據(jù)本身而言，存在著數(shù)據(jù)高維稀疏的特性;最后，本文采.用PCA降維與滑動窗口技術(shù)相結(jié)合的思想來改進(jìn)D-Stream算法，并通過仿真實(shí)驗(yàn)證明了算法的可行性。

[關(guān)鍵詞]流式數(shù)據(jù)PCA滑動窗口聚類

1引言

近年來，我們處在一個(gè)數(shù)據(jù)爆炸式增長的時(shí)代，從以往的靜態(tài)數(shù)據(jù)過渡到流式數(shù)據(jù)，其隱藏在這些數(shù)據(jù)背后的商業(yè)價(jià)值是不可估量的。如今，在有限的計(jì)算能力下處理流式數(shù)據(jù)處處受限，導(dǎo)致流式數(shù)據(jù)聚類算法的運(yùn)行效率受到一定的影響，如何提高流式數(shù)據(jù)聚類的效率尤其是針對高維數(shù)據(jù)尤為重要。

2007年由chen提出的基于網(wǎng)格密度的D-Sream算法，處理的是一個(gè)個(gè)網(wǎng)格，而非一個(gè)個(gè)數(shù)據(jù)，所以算法具有一定的速度優(yōu)勢。但是在網(wǎng)格劃分時(shí)，D-Stream存在高維網(wǎng)格劃分需要計(jì)算消耗，所以影響算法的運(yùn)行效率。近年來，對于網(wǎng)格密度的算法也有著大量的研究，例如：孫玉芬針對高維數(shù)據(jù)問題提出的基于聚類子空間的GSCDS算法、于翔等人提出的數(shù)據(jù)子空間的SC-RP算法、劉波等人提出的屬性最大間隔的子空間聚類算法MMSC、肖紅光等人于2016年提出的基于結(jié)構(gòu)樹的高維流式數(shù)據(jù)子空間的自適應(yīng)聚類算法等。針對以上眾多算法研究發(fā)現(xiàn)，針對高維數(shù)據(jù)流的算法大都采用映射子空間的技術(shù)來解決，但是算法需要預(yù)先設(shè)定參數(shù)，且計(jì)算量有所增加，消耗一定的內(nèi)存。而且未針對高維數(shù)據(jù)稀疏問題作出分析。在有限的計(jì)算資源下，提高高維流式數(shù)據(jù)聚類算法的效率具有一定的研究意義。

2 一種新的基于網(wǎng)格密度的流式數(shù)據(jù)聚類算法

2.1PCA數(shù)據(jù)降維算法原理簡介

PCA降維算法基本原理：主成分分析的的主要思想是將n維特征映射到k維上（k

（1）標(biāo)準(zhǔn)化模塊;

（2）相關(guān)矩陣模塊的計(jì)算;

（3）特征值特征向量的求解;

（4）主成分的保留。

其中，主成分分析法可以最大程度的保留原始數(shù)據(jù)的信息，所以可以提供足夠的的信息來綜合反映原始數(shù)據(jù)。

2.2PCA與滑動窗口技術(shù)結(jié)合實(shí)現(xiàn)數(shù)據(jù)流降維

本文認(rèn)真分析了D-Stream在劃分網(wǎng)格是存在的高維問題，以及高維數(shù)據(jù)本身的稀疏性特點(diǎn)，最終選擇了比較成熟的PCA降維算法，主成分分析顧名思義可以保留數(shù)據(jù)盡可能多的完整性，并且在針對高維數(shù)據(jù)稀疏上有一定的處理能力。

但是主成分分析并不能直接處理流式數(shù)據(jù)，這是由流式數(shù)據(jù)特點(diǎn)決定的。數(shù)據(jù)流式具有快速的、大量的、持續(xù)不斷產(chǎn)生的特點(diǎn)，所以本文分析并使用滑動窗口技術(shù)與PCA算法相結(jié)合來適應(yīng)流式數(shù)據(jù)的處理。其中，采用定滑動窗口模式，為滑動窗口定一個(gè)值，并采用周期法，數(shù)據(jù)流流入時(shí)，且數(shù)據(jù)片段未達(dá)到窗口大小時(shí)，暫時(shí)將數(shù)據(jù)存儲在緩存區(qū)內(nèi)，當(dāng)滿足滑動窗口要求時(shí)將數(shù)據(jù)放入滑動窗口內(nèi)，對數(shù)據(jù)進(jìn)行降維處理。當(dāng)數(shù)據(jù)開始流入算法時(shí)，設(shè)滑動窗口大小為γ，然后判斷流入的數(shù)據(jù)是否達(dá)到滑動窗口的大小，若是沒有則繼續(xù)流入數(shù)據(jù)，當(dāng)達(dá)到滑動窗口大小時(shí)，使用PCA降維處理窗口內(nèi)的數(shù)據(jù)。當(dāng)選取了盡可能優(yōu)的低維空間，得到了降維后的數(shù)據(jù)集，對降維后的數(shù)據(jù)再進(jìn)行極差標(biāo)準(zhǔn)化處理，然后再進(jìn)行數(shù)據(jù)的摘要提取和網(wǎng)格劃分。

2.3基于PCA的高維流式數(shù)據(jù)聚類算法的實(shí)現(xiàn)

本文采用的是滑動窗口與PCA結(jié)合的思想對其進(jìn)行降維處理，然后再對滑動窗口中處理后的數(shù)據(jù)進(jìn)行摘要的提取，網(wǎng)格的劃分，在時(shí)間間隔gap后，離線過程根據(jù)網(wǎng)格的密度以及一些判斷條件對網(wǎng)格進(jìn)行處理，包括更新網(wǎng)格密度、刪除零星網(wǎng)格等，最后再根據(jù)DBSCAN算法對網(wǎng)格進(jìn)行密度聚類，形成一個(gè)個(gè)的簇，并且在離線過程對簇進(jìn)行調(diào)整，包括簇的合并、簇的分裂等。其中的主要的過程如下：

輸入：數(shù)據(jù)流X、網(wǎng)格密度系數(shù)入、時(shí)間t、參數(shù)β、C、Cm網(wǎng)格劃分r輸出：聚類簇

（1）Algorithmbegin

（2）t=0

（3）Whiledatacollectionforeachslidingwindow#在滿足滑動窗口大小時(shí)

（4）Receive（X）

（5）PCAdimensionreductiongenerationmatrixX#使用PCA降維得到數(shù)據(jù)

（6）RangestandardizationX'

（7）FordatainX'#將數(shù)據(jù)輸入到后續(xù)的處理算法中

（8）t.+=1

（9）BasedonrDividingGrid

（10）ForeachdataX;#新數(shù)據(jù)點(diǎn)加入

（11）Joingridgandupdate#新數(shù)據(jù)加入以及網(wǎng)格更新

（12）Ift。%gap=0

（13）JudgeandremoveSporadic

（14）UpdateAllGridbasedonλ

（15）UseDBSCANclusteringgrid

（16）endAlgorithm

上述步驟是基于PCA的高維流式數(shù)據(jù)聚類算法的簡要處理過程，算法采用的滑動窗口技術(shù)與PCA降維算法相結(jié)合的特點(diǎn)，符合流式數(shù)據(jù)處理的條件，并且在降低高維數(shù)據(jù)的難題下，PCA算法又可以很大程度上的保留原始數(shù)據(jù)的完整性，并且在降維的過程中又可以在一定程度，上消除數(shù)據(jù)的高維稀疏特性，不僅降低了數(shù)據(jù)處理的計(jì)算量，提高了聚類的效率，而且在算法的處理上有著一定的好處，可以保證聚類的質(zhì)量。

3算法的實(shí)驗(yàn)結(jié)果及分析

本節(jié)對基于PCA的流式數(shù)據(jù)聚類算法進(jìn)行性能測試，實(shí)驗(yàn)平臺的配置如下：操作系統(tǒng)：Win7_64位;CPU為i5處理器;開發(fā)平臺：pycharm。實(shí)驗(yàn)數(shù)據(jù)集采用的是網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集KDDCPU99。實(shí)驗(yàn)使用數(shù)據(jù)集模擬數(shù)據(jù)流進(jìn)行輸入，其中算法參數(shù)λ=0.998，β=0.5，窗口的大小設(shè)置為5萬（一個(gè)窗口中的數(shù)據(jù)量達(dá)到五萬）。

從原理上來分析，基于PCA的高維流式數(shù)據(jù)聚類算法降低了數(shù)據(jù)的特征維度，并且一定程度上解決了數(shù)據(jù)高維稀疏的特點(diǎn)，所以大大的減少了網(wǎng)格劃分時(shí)所產(chǎn)生的計(jì)算量，從而改善了算法的運(yùn)行效率，圖1即為本文提出的算法與D-Stream算法在網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集上的運(yùn)行效率對比圖，其中^t代表PCA降維的時(shí)間，t表示降維后數(shù)據(jù)聚類的時(shí)間，t表示原始D-Stream算法運(yùn)行的時(shí)間，設(shè)

來表示算法運(yùn)行效率的對比度，如圖1所示。

從圖1的運(yùn)行結(jié)果可以看出，本文提出的基于PCA的高維流式數(shù)據(jù)聚類算法明顯的比D-Stream算法在聚類效率上有所提高。本文提出的算法具有明顯的優(yōu)勢，首先，該算法采用了滑動窗口技術(shù)，使得處理的數(shù)據(jù)可以分批次批量處理;其次，從直接處理高維數(shù)據(jù)，變成處理極大保留了原始數(shù)據(jù)完整性的低維數(shù)據(jù)，使得網(wǎng)格劃分產(chǎn)生的計(jì)算量大大的降低，從而使得算法的運(yùn)行效率得到大大的提高。

針對高維數(shù)據(jù)的高維稀疏性的特點(diǎn)，實(shí)驗(yàn)之前，分析了實(shí)驗(yàn)數(shù)據(jù)集，發(fā)現(xiàn)該數(shù)據(jù)集不僅存在高維特性，而且出現(xiàn)數(shù)據(jù)稀疏的特點(diǎn)，所以又做了本論文提出的基于PCA的高維流式數(shù)據(jù)聚類算法與D-Stream算法的準(zhǔn)確率對比，實(shí)驗(yàn)結(jié)果圖如圖2。

由上述實(shí)驗(yàn)的數(shù)據(jù)結(jié)果得出，本論文提出的基于PCA的高維流式數(shù)據(jù)聚類算法，在一定程度上可以處理高維流式數(shù)據(jù)，在對高維數(shù)據(jù)存在的數(shù)據(jù)稀疏的問題上具有一定的去噪能力，由實(shí)驗(yàn)結(jié)果表明本文提出的基于PCA的高維流式數(shù)據(jù)聚類算法較D-Stream算法在聚類精度上有一定的提高。

4總結(jié)

本文提出的基于PCA的高維流式數(shù)據(jù)聚類算法是基于D-Stream算法的基礎(chǔ)上進(jìn)行改進(jìn)，該算法能有效的處理高維數(shù)據(jù)，并且基于密度的聚類可以發(fā)現(xiàn)任意形狀分布的簇，實(shí)驗(yàn)結(jié)果表明該算法的可行性，不僅提高了效率，而且在一定程度上解決高維稀疏的特性，提高聚類準(zhǔn)確率。對于未來的研究，將放在進(jìn)一步提高算法的效率與準(zhǔn)確率上，自適應(yīng)算法的加入是下一步研究重點(diǎn)。

參考文獻(xiàn)

[1] Chen Y， Tu L. Dens i ty-BasedClustering for Real-Time StreamData. KDD07， August12-15， 2007， SanJose， California， USA.133-142.

[2]孫玉芬，基于網(wǎng)格方法的聚類算法研究[D].華中科技大學(xué)，2006.

[3]于翔，印桂生，許憲東等.一種基于區(qū)域劃分的數(shù)據(jù)流子空間聚類方法[J].計(jì)算機(jī)研究與發(fā)展，2014，51（01）：88-95.

[4]劉波，王紅軍，成聰?shù)?，基于屬性最大間隔的子空間聚類[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)），2014，50（04）：482-493.

[5]肖紅光，陳穎慧，巫小蓉，基于結(jié)構(gòu)樹的高維數(shù)據(jù)流子空間自適應(yīng)聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37（10）：2206-221.