工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)流自適應(yīng)聚類方法①

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

1(福建師范大學(xué) 計算機與網(wǎng)絡(luò)空間安全學(xué)院,福州 350117)2(福建省應(yīng)用數(shù)學(xué)中心(福建師范大學(xué)),福州 350117)3(福建師范大學(xué) 數(shù)字福建環(huán)境監(jiān)測物聯(lián)網(wǎng)實驗室,福州 350117)4(福建師范大學(xué) 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室,福州 350007)

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

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

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

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

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

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

面對著內(nèi)存受限、高維度災(zāi)難、低聚類質(zhì)量以及低處理速度數(shù)據(jù)流特性來說,目前數(shù)據(jù)流聚類研究主要存在著以下3 個方面的困難:

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

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

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

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

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

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

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

1 運動目標(biāo)檢測工業(yè)物聯(lián)網(wǎng)聚類框架及基本概念

1.1 工業(yè)物聯(lián)網(wǎng)聚類框架

工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)流的自適應(yīng)聚類方法是工業(yè)物聯(lián)網(wǎng)時代信息處理要解決的基本問題.本文構(gòu)建了工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)流挖掘總體框架.它主要分為:數(shù)據(jù)收集層,數(shù)據(jù)挖掘?qū)右约皵?shù)據(jù)應(yīng)用層,如圖1所示.由于工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)量巨大、協(xié)議標(biāo)準(zhǔn)眾多、安全性考慮不足等缺陷,數(shù)據(jù)收集層大多采用傳統(tǒng)傳感器技術(shù)來獲取數(shù)據(jù),如GPS、Network Flow 以及海量信息化數(shù)據(jù)等[4,18,19].數(shù)據(jù)挖掘?qū)咏邮諄碜詳?shù)據(jù)收集層中的數(shù)據(jù),以流的形式傳入處理器中;在數(shù)據(jù)挖掘?qū)又胁捎玫氖窍壤帽疚奶岢龅墓I(yè)物聯(lián)網(wǎng)自適應(yīng)聚類技術(shù)進行聚類分析,再將聚類結(jié)果集通過數(shù)據(jù)傳輸存儲到總服務(wù)器中.在數(shù)據(jù)應(yīng)用層中,數(shù)據(jù)存儲總服務(wù)器通過類別分別傳入到對應(yīng)的應(yīng)用上,從而達到分布式管理.對數(shù)據(jù)達到針對性應(yīng)用.在對工業(yè)物聯(lián)網(wǎng)自適應(yīng)聚類算法詳細(xì)介紹之前,我們先對工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)流及其相關(guān)概念進行介紹.

圖1 工業(yè)物聯(lián)網(wǎng)聚類框架

1.2 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 工業(yè)物聯(lián)網(wǎng)數(shù)據(jù)流自適應(yīng)聚類方法

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

2.1 初始化微簇

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

2.2 微簇映射

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

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

2.3 微簇的更新

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

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

2.4 移除離群簇

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

2.5 構(gòu)建微簇決策樹

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

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

2.6 更新簇圖

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

3 相關(guān)理論分析

3.1 時間復(fù)雜度

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

3.2 空間復(fù)雜度

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

3.3 微簇數(shù)量上界值分析

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

對于每一個時間周期內(nèi),微簇數(shù)量M的產(chǎn)生總是滿足:

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

因此,對于一個時間周期內(nèi),該算法所產(chǎn)生的微簇數(shù)量M為C_of_c,即:

3.4 微簇低延遲處理

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

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

4 仿真實驗與分析

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

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

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

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

實驗3.設(shè)置不同衰減因子,測試CMStream 算法從低維到高維數(shù)據(jù)流處理的響應(yīng)時間.

工業(yè)物聯(lián)網(wǎng)所產(chǎn)生的數(shù)據(jù)數(shù)量龐大,超高維度,因此為了更好驗證CMStream 算法在工業(yè)物聯(lián)網(wǎng)環(huán)境的性能,我們使用了3 個海量、高維的數(shù)據(jù)集,為了讓數(shù)據(jù)集仿真真實環(huán)境,本文通過時間窗口的形式將靜態(tài)數(shù)據(jù)集進行動態(tài)化模擬測試.

(1)KDDCUP’99:數(shù)據(jù)集包含4 898 431 個實例,每個實例包含著41 維向量,它產(chǎn)生于現(xiàn)代工業(yè)的網(wǎng)絡(luò)流量記錄.

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

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

4.1 對比算法

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

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

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

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

4.2 聚類處理速度對比

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

圖2 在EPM 數(shù)據(jù)集上測試對MCStream 算法進行測試

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

圖3 在KDDCUP’99 數(shù)據(jù)集上測試對MCStream 算法進行測試

4.3 聚類純度對比

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

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

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

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

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

4.4 參數(shù)影響以及聚類精度定義

在本文所規(guī)劃的實驗中,需要設(shè)定相關(guān)參數(shù)以研究權(quán)重衰減因子對聚類響應(yīng)速度,以及對于聚類精度的影響.

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

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

圖5 不同衰減因子在不同維度上對數(shù)據(jù)點處理速度

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

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

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

5 結(jié)束語

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

目前,工業(yè)物聯(lián)網(wǎng)正發(fā)展迅猛,其數(shù)據(jù)結(jié)構(gòu)越來越復(fù)雜,其規(guī)模也越來越大.在未來工作中,我們將進一步提高算法在大規(guī)模稀疏數(shù)據(jù)集上的處理效果,提高算法在現(xiàn)實工業(yè)領(lǐng)域的適應(yīng)性.