工業物聯網數據流自適應聚類方法①

朱維富,曾智霞,肖如良,4

1(福建師范大學 計算機與網絡空間安全學院,福州 350117)2(福建省應用數學中心(福建師范大學),福州 350117)3(福建師范大學 數字福建環境監測物聯網實驗室,福州 350117)4(福建師范大學 福建省網絡安全與密碼技術重點實驗室,福州 350007)

5G 技術的發展促使工業物聯網得到全面提升,使全球加速進入第4 次工業革命時代[1].工業物聯網在提升生產效率的同時,會產生海量、超高維、復雜異構的實時流數據,業界稱之為工業數據流[2-4].這些流數據不能再做靜態數據假設,數據量大實時性強,又必須在有限內存內處理[5,6],從而工業物聯網所產生的海量實時數據給數據流聚類分析帶來了巨大的挑戰.

近年來,數據流聚類已經成為了工業物聯網數據挖掘分析的關鍵性研究領域,其目的是為了識別無界且無序觀測流中的模式[5,7,8].數據流聚類技術通常是采用在線和離線兩個階段.在線階段主要通過優化數量和更新簇的位置,以便更好地表示底層數據;在離線階段提取相關信息,而不對數據進行存儲并且重新評估所有的結果.數據流聚類技術發展至今,主要可以分為這3 類:基于距離的流聚類方法、基于網格的流聚類方法、基于預測的流聚類方法.

第1 類:基于距離的流聚類方法.該類方法是最流行的方法,它通過簡單的插入規則來構建簇,基于概要數據結構來總結與簇相關的觀測值,而不存儲每個單獨的數據點.最具有代表性的是:CluStream[9],DBSTREAM[10]以及BOCEDS[11]等.2003年,Aggarwal 等人提出了CluStream 算法[9].其算法核心思想主要是通過在線階段利用微族的概要存儲結構存儲數據流的匯總結果,并按金字塔式時間結構將中間結果進行保存;而其離線部分則根據用戶指定的觀察階段及聚類數量,快速生成聚類結果.在2016年,Baer 等人提出了DBSTREAM算法[10].該算法采用了微簇之間密度共享機制來確定所屬宏族,該機制利用保持微族的共享密度來作為它們之間的半徑,并且在離線階段具有高共享密度的微簇歸屬于同一個宏族.在2019年Islam 等人提出了BOCEDS 算法[11],它仍然采用了概要技術存儲微簇信息,該算法主要增加了一個緩存機制來處理數據流演化以及漂移問題.

第2 類:基于網格的流聚類方法.該類方法通過網格將數據空間沿各維度進行分隔,以創建多個網格結構.通過將數據點映射到單元格,可以保持密度估計[8].最具有影響力的代表性算法如:2007年Chen 等人提出的D-Stream 流聚類方法[12],它將新的數據點映射到所屬單元格中,并通過將所有密集單元格分配給單個簇進行初始化,并經相鄰網格擴展;還有2014年Amini等人所提出的HDCStream[13]以及其在2016年提出的Mudi-Stream[14]等.基于網格的流聚類方法可以識別任意形狀的簇,這也是該方法所具備的重要特征.

第3 類:基于預測的流聚類方法.該類方法是一種高維數據流的流聚類方法.該類方法可以在數據流維度十分大的空間中識別簇,從而為高維數據流提供了一個利基.該類方法最具有代表性的是:HPStream[15]、HDDStream[16]等.2004年Aggarwal 等人提出了HPStream 算法[15],它基于CluStream 算法[9]在高維上進行了擴展.通過定期采樣當前簇的標準差,調整現有的聚類,使每個維度標準化,通過更新簇分配每個簇的關聯維度.在每個簇中暫定添加一個新的觀測點,以更新維度.如果聚類數據點不超過閾值則不增加聚類半徑,且將其添加到最近的聚類中.

以上方法各有優點:基于距離的流聚類算法通常計算負荷低、基于網格的流聚類算法可以識別任意形狀的簇;基于預測的流聚類算法能有效應對維度災難.但是也存在如下的缺陷:基于距離的流聚類算法往往依賴于參數的設定,基于網格的聚類算法卻由于網格是動態確定的而增加了計算負荷,而基于預測的流聚類算法增加了宏族選擇子空間的復雜性.

面對著內存受限、高維度災難、低聚類質量以及低處理速度數據流特性來說,目前數據流聚類研究主要存在著以下3 個方面的困難:

(1)對于持續、快速、以及高維數據流來說,數據源源不斷地流入,導致微簇數量的持續性增加,聚類方法中隱含高負荷剪枝操作.

(2)聚類簇數的確定一直是流聚類方法中的困難問題,同時聚類簇數也對聚類質量有非常大的影響.

(3)生產環境是開放的,所產生的數據流會不斷演化,許多數據流聚類方法未能將一些離核心微簇較遠、信息量較少的微簇進行異常檢測.

針對工業物聯網實時數據流的上述挑戰問題,在我們小組已有的基礎性工作[17]的基礎之上,本文提出了一種新的工業物聯網數據流自適應聚類算法(簡稱MCStream).本文的方法與現有的方法完全不同,第一,在處理海量高維數據的聚類上,目前基于密度的流聚類算法對于參數值的變化很敏感,往往由于參數的細微變化在很大程度上影響了聚類質量;第二,在動態數據聚類過程中,存在著大量數據的插入以及移除操作,進一步地引起大規模的交叉微簇連接操作,目前基于密度的流聚類算法未能有效的解決這樣復雜計算問題.本文算法引入一種新的引力能量函數的方法對參數進行遞歸的更新操作,很好地解決了參數敏感性問題,并且通過高斯核函數計算微簇密度峰值方式代替了大規模交叉微簇連接操作,進一步地加快了數據流聚類映射速度.因此本文的主要貢獻如下:

(1)提出了一種新的微簇構建方法.該方法采用引力能量更新函數,對微集群進行遞歸在線更新;同時取消交叉微簇連接操作,從而達到微簇構建與數據映射實時響應.

(2)提出了一種新的自適應計算聚類簇數的方法.該方法以微簇作為參與宏簇聚類的樣本數據,利用各微簇的局部密度以及距離值,計算微簇的密度峰值,并通過這兩個變量值來自適應求出聚類簇數,從而更好地處理大規模數據.

(3)構建了一種新的檢測異常微簇的判定方法.該方法采用一個局部密度上界來標識宏簇,以區分密集簇和離群簇,使異常族檢測更加精確.

1 運動目標檢測工業物聯網聚類框架及基本概念

1.1 工業物聯網聚類框架

工業物聯網數據流的自適應聚類方法是工業物聯網時代信息處理要解決的基本問題.本文構建了工業物聯網數據流挖掘總體框架.它主要分為:數據收集層,數據挖掘層以及數據應用層,如圖1所示.由于工業物聯網數據量巨大、協議標準眾多、安全性考慮不足等缺陷,數據收集層大多采用傳統傳感器技術來獲取數據,如GPS、Network Flow 以及海量信息化數據等[4,18,19].數據挖掘層接收來自數據收集層中的數據,以流的形式傳入處理器中;在數據挖掘層中采用的是先利用本文提出的工業物聯網自適應聚類技術進行聚類分析,再將聚類結果集通過數據傳輸存儲到總服務器中.在數據應用層中,數據存儲總服務器通過類別分別傳入到對應的應用上,從而達到分布式管理.對數據達到針對性應用.在對工業物聯網自適應聚類算法詳細介紹之前,我們先對工業物聯網數據流及其相關概念進行介紹.

圖1 工業物聯網聚類框架

1.2 基本概念

定義1 (工業數據流).設D是一個工業數據流:D={xi}∞1,其中,{xi}代表著在t時刻到達的一個數據樣本,{xi∈Rd}代表著這個數據樣本點是一個d維向量.

定義2 (概念漂移).設x為特征向量,其中Pt(l|x)是x在t時刻的條件分布,隨著時間t的推移,x的條件分布滿足?x:Pt0(l|x)≠Pt1(l|x).即聚類統計特性正在以不可見的方式進行著變化,從而聚類精度不斷地降低.

定義3 (微簇結構).設mc表示一個微簇,該微族定義為一個六元組mc=(CNt,Nt,S Nt,C,θ,W),其中:

(1)CNt表示每個微簇核心區數據點數,微簇核心區是指在距離微簇中心r/2 范圍內的區域.

(2)Nt表示在t時刻數據點到來時相應微簇的數據點數,t+1 時刻使用式(1)更新.

(3)S Nt表示微簇殼區總樣本點數,微簇殼區表示距離微簇核心r處邊緣;殼區數據點數用式(2)計算.每個微簇分為核心區和殼區兩部分.

(4)C為微簇中心,表示微簇在空間中的位置.Ctk表示在t時刻聚類中心C的第K維所對應的值;xkt表示在t時刻到來的數據點X第K維的值;隨著時間推移,數據點不斷到來,微簇中心C會進行更新改變,如式(3)所示.

(5)微簇的衰減因子我們使用 θ表示,表示單位時間內到達的數據點數目,當微簇需要進行微簇更新時,每更新一次權重都會進行一次衰減因子的更新.

(6)Wt表示微簇的權重值,采用引力能量函數進行遞歸在線更新;dis(xt+1,Ct)表示在t+1 時刻到來的數據點距離所屬微簇C的簇中心距離值;r表示微簇半徑.每個微簇的生存或者死亡都是依賴于微簇的權重,權重值等于或者小于0的微簇都不會參與到聚類當中,其中微簇權重更新使用式(4)進行更新.

定義4 (核心簇).核心簇用CoreClusters 表示,在t時刻的核心簇中,簇總數據點數Nt＞minPts最小密度值),微簇權重Wt＞0,它存儲在主存儲器當中.

定義5 (潛在核心簇).潛在核心簇用pCoreCluster 表示,在t時刻的潛在核心簇中,簇總數據點數Nt＜minPts微簇權重值Wt＞0,它代表目前這個簇由于數據點不足而無法構成核心簇,但在未來時間內有可能隨著數據點的增加而成為核心簇.

定義6 (離線緩沖簇).離線緩沖簇用OBuffer-Cluster 表示,在t時刻的離線緩沖簇中,簇總數據點數Nt＞minPts,微簇權重Wt＜0,它存儲在緩沖存儲器當中,它表示核心簇由于隨著時間的增加權重逐漸降至為0 之后變成了離線緩沖簇,但它并不是就沒有關聯了,有可能在未來某一段時間它會隨著數據點的到來再次變為核心簇.

定義7 (微簇局部密度).微簇局部密度Pmi是簇群中與CoreCluster 之間的距離小于截斷距離dmin的微簇.其中dij表示微簇i和微簇j中心點間的歐式距離.局部密度Pmi的計算方式可使用一種高斯核函數來進行計算,見式(5).

定義8 (微簇距離).基于定義7,對微族局部密度進行排序,當微族qi的局部密度最大時,微簇距離δqi的距離是微簇群中與qi最大的距離 m ax{δqj},否則表示簇群中所有微簇局部密度大于qi的微簇中與qi最近距離的微簇 min{dqidqj}.從而微簇距離 δqi可用式(6)計算.

在上述定義當中,微簇中心是通過計算殼區域數據點的平均值,而不是通過計算整個簇數據點的平均值,這是因為他們通過限制微簇的移動來阻止微簇無休止地跟隨數據流的漂移[20],在聚類過程中,只有核心簇參與到簇聚類,對于離群簇則會進行移除操作,當微簇CoreCluster 具有最大局部密度時,δqi表示在核心簇CoreClusters 中與CoreCluster 距離最大的微簇點與CoreCluster 之間的距離;否則,δqi表示在所有局部密度大于CoreCluster的微簇點中,與CoreCluster 距離最小的那些微簇與CoreCluster 之間的距離.

2 工業物聯網數據流自適應聚類方法

本文算法主要分為6 個階段,分別為:初始化微族,微族映射,更新微族,移除離群族,構建微族決策樹,更新族圖.

2.1 初始化微簇

在數據流D中第一個數據點到來時候,它不屬于任何簇結構,因此將創建一個微簇來存儲信息.這一步與之后的新的微簇創建同時發生.微簇的創建首先要初始化特征向量.新簇的簇中心C和半徑r定義了微簇在數據空間中位置以及覆蓋范圍;簇中心C初始設置為xi,衰減因子θ是根據相關應用程序的專家知識所設置的,殼數據點數據以及微簇數據點數都設置為1.這些值被記錄以用來對微簇中心的遞歸更新,權重W值是用來確定微簇群的時間長度;它是使用一個時間衰減函數來進行遞歸更新,這在后面詳述.當數據點到來之時,它會判斷是否存在簇結構;如果不存在,則會創建一個微簇結構.

2.2 微簇映射

在任意t時刻,數據流D={xi}∞1中數據點xi到達的時候,該算法首先將計算數據點xi與微簇的歐式距離;如果距離dis滿足式(7),則將數據點映射到所屬微簇當中.數據點有可能映射3 種微簇集合當中.

第1 種就是參與集群聚類的核心簇(CoreClusters),第2 種就是潛在核心簇(pCoreCluster),第3 種就是存儲在緩沖器當中的離線緩沖簇(OBufferCluster).為了找到目標微簇,該算法首先計算核心簇與數據點xi的歐式距離.如果滿足式(7),則將數據點映射到核心簇當中,并記錄該核心簇索引.如果在核心簇中沒有找到,則同尋找核心簇方法一樣在另外兩種微簇集群當中進行映射.如果數據點xi即滿足核心簇的映射條件也滿足其他一種或者兩種核心簇,則選擇將該數據點映射到核心簇當中.

2.3 微簇的更新

在圖像預對于集群當中任何微簇結構.任何一個微簇集群只要接收到了新數據,那么該微簇結構的概要信息都會進行更新.如果在t時刻數據點屬于核心簇CoreCluster,那么將會使用式(1)更新微簇數據點的數量;如果它是映射到核心簇殼區域,那么會使用式(3)更新映射微簇中心.這種簇中心更新機制是為了防止微簇集群由于數據點的增加而出現數據漂移,并且會使用式(2)更新殼區數據點的數量.使用式(4)更新微簇權重.

如果數據點xti是映射到核心區域,則不會進行簇中心的更新.如果數據點xti映射到潛在核心簇pCoreCluster,那么同核心簇一樣會對所映射的pCoreCluster 概要信息進行更新;并且會對pCoreCluster 微簇數據樣本點進行判斷,看是否滿足Nt＞minPts.如果滿足,則將該映射pCoreCluster 移入到核心簇當中,并從潛在核心簇去除該簇.如果數據點映射到離線緩沖簇當中,那么在同核心簇一樣更新微簇概要之后還會將該簇從離線緩沖簇中移除;并將它移入核心簇當中,這是由于數據流的演化特性.由于在數據演化過程中微簇權重可能會越來越低,當它權重低于0 則會與當前數據流無關;但是在未來某一段時間有可能會隨著新的數據的到來而重新相關;因此它會被重新移入核心簇當中參與集群聚類.

2.4 移除離群簇

伴隨著流數據的不斷流入,在數據點不斷地映射到微簇群之后;該算法會對所有簇群中的微簇進行權重更新.在核心簇、潛在核心簇、離線緩沖簇中,由于有些微簇持續性沒有新的數據映射進來;其微簇權重都會不斷地降低,這也體現著數據流演化特性.對于核心簇群來說,每個核心微簇如果權重小于0,那么該微簇將會從核心簇當中移入緩沖簇中;并且會對其能量設置為原有初始能量的一半.而在對潛在核心簇以及離線緩沖簇來說;如果長時間的沒有新的數據對其微簇進行更新,那么說明這些微簇跟數據流內容長期無關并且是正在消亡的微簇.對于流式算法來說低內存是其中一個不可或缺的評價標準;因此這些正在消亡的微簇就需要從內存中永久性的移除.

2.5 構建微簇決策樹

當核心簇以及其他兩個簇群發生改變時,該算法會進行維護聚類圖操作.而對于聚類我們都需要保證聚類中心的密度最大,以及各個微簇聚類中心的距離相對較遠.只有這樣才能讓各簇之間區分明顯,并且自適應的確定宏簇聚類簇數.

在微簇進行更新之后.為了獲取根據核心簇的數據特性而自適應的求出微簇所需要聚類簇數;我們首先需要計算核心微簇群當中所有微簇之間相互的歐式距離值.通過計算這個距離值可以構建一個核心微簇的距離矩陣.在獲取到距離矩陣后我們通過對這個距離進行排序以此來獲取一個截斷距離dmin;其中等于比dmin更接近核心簇i的數據點數.由于這個值的選擇跟核心簇中不同的微簇距離相關,因此dmin的選擇是魯棒性的.通過式(5)可知,與微簇i之間的距離小于dc的越多,那么與微簇i的局部密度就越大.當微簇i為核心簇局部密度最大的點時,我們通過計算與微簇i距離最大的點的距離;而對于其他局部密度的微簇,則通過計算比它局部密度更大的點中距離最小的微簇之間的距離;通過這兩個值,我們可以直觀的反應聚類中心的特性.局部密度大以及各聚類中心之間相差很遠.

2.6 更新簇圖

在簇圖更新中,我們在式(5)得到了微簇局部密度以及距離.我們將每一個參與聚類的微簇作為一個數據點.首先將每個微簇的局部密度以及距離進行歸一化處理;然后將他們的乘積λ作為以微簇為聚類點的聚類中心的評判標準.如果微簇C[i]是聚類中心,并且屬于第k簇,那么將其宏簇屬性設定為k;如果不是微簇,那么將其屬性賦值為-1.在所有聚類中心確定之后,我們需要對非聚類中心微簇進行歸類操作.這里是按照密度值從大到小的順序進行的遍歷;這樣做可以逐層的擴充每一個微簇.微簇通過這兩步操作,即完成了聚類中心及微簇的歸類操作.我們進一步將每個宏簇分為cluster core 以及cluster halo 兩類;這里是通過屬性來進行標識.對于cluster core,是指那些局部密度較大者;而對于cluster halo是指那些局部密度較小的,我們通過了為每一個宏簇設定一個局部密度平均上界來確定cluster core 以及cluster halo.這樣能將離聚類中心以及信息量較少的微簇進行標識.

3 相關理論分析

3.1 時間復雜度

算法時間的消耗主要來源于數據點的映射以及簇圖的聚類過程,假設在T時刻M維數據流產生了N個微簇,數據點映射時間與微簇數以及維度呈正相關關系,因此在數據點映射的時間復雜度為O(MN),在簇圖聚類過程中,假設產生了d個核心簇,產生了K個類,所需時間復雜度為O (d2),因此本文算法整體時間復雜度為O(MN)+O(d2).

3.2 空間復雜度

該算法內存消耗主要來源于微簇的存儲以及簇圖的存儲,維度為M的數據流產生了N個微簇且其中產生了C個核心簇,在簇圖聚類過程中,d個核心簇在簇圖聚類過程中聚成了K個類,因此本文算法整體空間復雜度為O (N+d),且d?N.

3.3 微簇數量上界值分析

進行對于任何聚類算法來說,空間復雜度以及時間復雜度兩個值都決定著聚類的優劣.而對于流聚類算法來說,微簇數量的邊界決定著算法運行速度以及空間存儲需求,因此我們針對本文算法分析了在每一個周期內微簇數量M的邊界值.

對于每一個時間周期內,微簇數量M的產生總是滿足:

證明:在任意的一個時間周期上,衰減因子 θ是從數據流中在一個單位時間內到達的數據點數,由于數據點最新映射到潛在核心簇中,但參與聚類的簇為核心簇,潛在核心簇到核心簇滿足條件至少需要minPts個數據點,因此在一個時間內核心簇的最大數量為從而核心簇在一個周期內滿足的微簇數,由于離線緩沖簇是來自核心簇,且權重比為核心簇的1/2,因此離線緩沖簇的數量跟核心簇的數量成正比,從而離線緩沖簇在一個周期內產生的微簇數滿足:

因此,對于一個時間周期內,該算法所產生的微簇數量M為C_of_c,即:

3.4 微簇低延遲處理

假設Wt為某一時間窗口,Ct為當前時間,Ts為Ct-Wt時間之前任意序列中最后一次存儲微簇概要信息的時間,那么Ct-Ts≤2·Wt.

證明:設δ是最小整數,β是一個整數且 β≥1,βδ表示第δ 次存儲微簇概要信息時間間隔使得 βδ≥Wt.那么βδ-1≥Wt.因為可以知道存在序列為(δ-1)的β微簇概要信息,則在Ct-Wt之前必須始終存在至少一個序列為(δ-1)的微簇概要信息,讓Ts是發生在Ct-Wt之前的(δ-1)微 簇概要信息,那么Ct-Wt-Ts≤βδ-1.從而滿足:

4 仿真實驗與分析

為驗證本文所提出流聚類方法的先進性,下面將與當前已發表的同類前沿方法進行對比試驗,針對各項性能進行評測.所設定的實驗PC 硬件環境為:RAM 12 GB,主頻2.4 GHz;操作系統Windows 10 專業版,語言平臺:Python 3.6.我們使用了多個數據集來仿真工業物聯網中海量傳感器數據.在快速處理、有限內存的約束下,流聚類技術的高聚類質量是我們的追求目標,而聚類純度、聚類精度是評價聚類質量的重要指標,因此我們擬采用與目前基于密度的聚類算法分別從數據點處理速度,聚類純度以及算法內存消耗3 個方面進行對比,并設計了3 組實驗.

根據以上3 個方面,所進行的3 組實驗如下.

實驗1.測試不同數據流長度對各類密度聚類算法處理能力進行對比.

實驗2.比較不同聚類算法的平均聚類純度.

實驗3.設置不同衰減因子,測試CMStream 算法從低維到高維數據流處理的響應時間.

工業物聯網所產生的數據數量龐大,超高維度,因此為了更好驗證CMStream 算法在工業物聯網環境的性能,我們使用了3 個海量、高維的數據集,為了讓數據集仿真真實環境,本文通過時間窗口的形式將靜態數據集進行動態化模擬測試.

(1)KDDCUP’99:數據集包含4 898 431 個實例,每個實例包含著41 維向量,它產生于現代工業的網絡流量記錄.

(2)Bag of Words:數據集包含著8 000 000 條實例,每個實例包含著100 000 維向量,它從收集于文本數據集.

(3)EPM:數據流包含著230 318 條數據集,每個數據集13 維向量,它是一個學習分析數據集.

4.1 對比算法

(1)CEDAS[20]:2016年Hyde 等人提出了CEDAS算法.該算法是一種基于完全在線的算法將演化數據流聚成任意形狀的簇,它主要分為兩個階段,一個是微簇維護階段,一個是宏簇聚類階段.

(2)DBCLPG[21]:2019年Halim 等人提出了DBCLPG 算法.該算法是基于密度的大概率圖聚類,與其他算法不同的是,它在聚類過程是利用節點度以及鄰域信息為引導,通過圖的密度對大概率圖進行聚類.

(3)BOCEDS[11]:2018年Islam 等人提出了BOCEDS 算法.該算法是一種基于緩沖區的演化數據流在線聚類方法,在CEDAS[20]的基礎上提出了一個緩存機制來存儲無關微簇以及從這個緩沖區提取暫時無關微簇的在線剪枝聚類算法.

(4)microTEDAclus[22]:2019年Maia 等人提出了microTEDAclus 算法.該算法是基于典型性混合的進化聚類算法,基于TEDA 框架所提出來的,將聚類問題劃分為兩個子問題,一個是微簇構建,一個是微簇進化成宏簇.

4.2 聚類處理速度對比

為了探究在隨著數據集中數據點不斷流入的情況下MCStream 算法聚類處理速度,以及對于在同樣數據集長度下不同維度數據集的聚類處理速度,在實驗過程中,我們分別與當前最前沿的多個方法如:CEDAS[20]方法DBCLPG[21]方法microTEDAclus[22]方法以及BOCEDS[11]方法在不同維度的數據集上進行了對比.我們在數據集EPM 以及KDDCUP’99 分別設置不同長度來測試這些聚類算法的處理速度 (如圖2、圖3所示),其中每1 000 個數據點設置為一個時間窗口長度,圖3顯示了MCStream以及其他算法在不同維度數據集上響應時間.

圖2 在EPM 數據集上測試對MCStream 算法進行測試

從圖2、圖3中可以看出,MCStream 聚類算法隨著數據點的不斷增大在聚類處理時間上明顯低于其他聚類算法.而且在圖2的結果數據中可以看出,面對著數據量更大以及維度更高的EPM 數據流來說,各類聚類算法處理時間長度都顯著增加.這是由于維度大小與時間復雜度存在著線性關系.對于CEDAS[20]以及BOCEDS[11]來說,隨著數據量不斷增加,微簇數量也呈線性增加;而創建新的微簇來維護簇群以及更新微簇的邊緣,這是一個十分巨大的耗時任務.MCStream算法都是明顯優于其他聚類算法,這說明MCStream算法聚類算法可以在較低的處理時間和延遲代價來擴展到更高維的數據空間中.

圖3 在KDDCUP’99 數據集上測試對MCStream 算法進行測試

4.3 聚類純度對比

本組實驗的目的是為了研究MCStream 算法在數據流中聚類的純度從而反映其聚類性能.在評價聚類的指標中聚類純度是其中比較流行的一種評價方法,在式(9)給出了純度的詳細定義.

其中,K是所有宏簇數,m是所有參與聚類的數據點數,mi是聚類i中所有數據點數,mij是聚類i中數據類j的數據點數,這里取平均值是為了降低誤差性.

目前在據流聚類時比較受歡迎一類流聚類數據集是KDDCUP’99 數據集,它可以測試不斷演化的數據流聚類算法.我們通過以500 個數據點為一個長度分別設置不同長度來測試CEDAS[20]、DCLPG[21]、micro TEDAclus[22]、BOCEDS[11]以及本文提出的MCSTream在該數據集中聚類純度,實驗結果在圖4柱狀圖中顯示.

圖4 測試不同算法的聚類純度

從圖4數據中可以看出,在不同的時期聚類純度都有所不同,在后期所有聚類純度都有所降低.這是因為隨著數據流長度的不斷增長,微簇數量也在不斷增加,數據點錯分的概率也隨著線性增加,從而降低聚類純度.盡管這樣,MCStream 聚類算法仍然保持了一個平穩的較高聚類純度.這是由于在宏簇聚類中MCStream移除了信息量較少且離簇中心較遠卻又參與到宏簇聚類的異常簇,從而保證了高質量聚類,這表明MCStream算法在大規模數據集上有著良好的穩定性.

4.4 參數影響以及聚類精度定義

在本文所規劃的實驗中,需要設定相關參數以研究權重衰減因子對聚類響應速度,以及對于聚類精度的影響.

聚類精度的定義在式(10)中給出,該公式中變量與式(9)中的變量定義是一樣的.在本實驗中,我們在高維數據流Bag of Words 以及KDDCUP’99 中分別測試了不同衰減因子在不同維度對于MCStream 聚類反應時間,以及不同衰減因子對于聚類精度的影響.為了模擬數據流的大規模性,本文采取了以1 000 個數據點為一個數據窗口長度,設置不同數據流長度的方式對MCStream 算法進行測試.圖3的實驗結果顯示了不同衰減因子在不同維度下算法MCStream 對于每個數據點的平均處理速度.在圖4的柱狀圖中顯示了對于不同的衰減因子對于聚類精度的影響.

從圖5可以看出,各類算法在不同維度下無論設置什么衰減因子其處理速度都在顯著的增加.這是因為數據維度是和時間復雜度呈線性相關,維度的升高,數據映射時間也會顯著性增加.而對于衰減因子來說,衰減因子是和微簇數量呈正相關.衰減因子增加會導致權重衰減得越慢,從而微簇數量勢必會增加,這對于新數據點所歸屬簇群的映射計算量也會顯著性增強.從簇群方面來說,微簇的量增加,那么對于維護簇群壓力也會增大.因此,衰減因子越大,數據點平均處理延遲也會越大.

圖5 不同衰減因子在不同維度上對數據點處理速度

從圖6可以看出,隨著衰減因子不斷增加,各類聚類算法的聚類精度也會隨之下降,這是因為上述所說的衰減因子與微簇數量呈正相關.微簇數量的增加,將會導致異常微簇數量增加,從而導致整體聚類精確度降低.對CEDAS[20]以及BOCEDS[11]來說,微簇數量的增加,會把更多的異常簇加入到聚類宏簇當中;而對于MCStream 來說,由于在宏簇聚類過程中有一個平均局部密度上界來區分一些邊緣微簇,從而大大提升了聚類的精度.

圖6 不同衰減因子參數下對聚類精度的影響

在本部分我們通過使用了3 個數據集在處理時間、聚類純度、精確度以及衰減參數上分別驗證了基于微簇結構的流聚類算法的有效性.實驗結果表明MCStream 具有較高的聚類能力,然而對于高維數據仍然對聚類處理時間有著較大的影響.在與流數據聚類算法進行對比的過程中,我們不僅得出了高速聚類的重要性,也驗證了MCStream的有效性和高效性.

5 結束語

工業物聯網產生的工業數據流具有無限、高維、無序的特點,因此構建高質量自適應流式聚類算法處理工業數據流具有十分重要的意義.本文提出了一種工業物聯網數據流自適應聚類算法,根據微簇的高密度性,將每一個微簇作為一個參與聚類的數據樣本點,計算每個微簇的局部密度以及微簇之間的距離,通過微簇的局部密度以及微簇距離來構建宏簇聚類決策樹從而確定聚類中心以及自適應確定宏簇聚類數.并且通過引入了引力能量函數來不斷地更新微簇權重,從而來移除老化的微簇以防止概念演化以及數據漂移問題.此外,本文方法去除了微簇構建過程中相交微簇之間的計算,維護了宏觀簇所需的最小計算量.通過在3 個仿真的大規模數據流中對算法從多個方面進行了評測,并且與當前前沿的聚類算法進行了充分的比較,證明了該算法具有顯著性優勢.由于該算法面向的是稠密數據集,面對著稀疏數據集時由于會產生大量單個稀疏微簇,聚類質量會顯著性降低.

目前,工業物聯網正發展迅猛,其數據結構越來越復雜,其規模也越來越大.在未來工作中,我們將進一步提高算法在大規模稀疏數據集上的處理效果,提高算法在現實工業領域的適應性.