基于PCA的高維流式數據聚類算法

張云龍

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

[關鍵詞]流式數據PCA滑動窗口聚類

1引言

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

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

2 一種新的基于網格密度的流式數據聚類算法

2.1PCA數據降維算法原理簡介

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

（1）標準化模塊;

（2）相關矩陣模塊的計算;

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

（4）主成分的保留。

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

2.2PCA與滑動窗口技術結合實現數據流降維

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

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

2.3基于PCA的高維流式數據聚類算法的實現

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

輸入：數據流X、網格密度系數入、時間t、參數β、C、Cm網格劃分r輸出：聚類簇

（1）Algorithmbegin

（2）t=0

（3）Whiledatacollectionforeachslidingwindow#在滿足滑動窗口大小時

（4）Receive（X）

（5）PCAdimensionreductiongenerationmatrixX#使用PCA降維得到數據

（6）RangestandardizationX'

（7）FordatainX'#將數據輸入到后續的處理算法中

（8）t.+=1

（9）BasedonrDividingGrid

（10）ForeachdataX;#新數據點加入

（11）Joingridgandupdate#新數據加入以及網格更新

（12）Ift。%gap=0

（13）JudgeandremoveSporadic

（14）UpdateAllGridbasedonλ

（15）UseDBSCANclusteringgrid

（16）endAlgorithm

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

3算法的實驗結果及分析

本節對基于PCA的流式數據聚類算法進行性能測試，實驗平臺的配置如下：操作系統：Win7_64位;CPU為i5處理器;開發平臺：pycharm。實驗數據集采用的是網絡入侵檢測數據集KDDCPU99。實驗使用數據集模擬數據流進行輸入，其中算法參數λ=0.998，β=0.5，窗口的大小設置為5萬（一個窗口中的數據量達到五萬）。

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

來表示算法運行效率的對比度，如圖1所示。

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

針對高維數據的高維稀疏性的特點，實驗之前，分析了實驗數據集，發現該數據集不僅存在高維特性，而且出現數據稀疏的特點，所以又做了本論文提出的基于PCA的高維流式數據聚類算法與D-Stream算法的準確率對比，實驗結果圖如圖2。

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

4總結

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

參考文獻

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

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

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

[4]劉波，王紅軍，成聰等，基于屬性最大間隔的子空間聚類[J].南京大學學報（自然科學），2014，50（04）：482-493.

[5]肖紅光，陳穎慧，巫小蓉，基于結構樹的高維數據流子空間自適應聚類算法[J].小型微型計算機系統，2016，37（10）：2206-221.