李志杰 廖旭紅 劉基旺 江華

摘 ?要：K-means是最常用的批量聚類方法，然而該算法需要多次迭代并不能直接用于數(shù)據(jù)流聚類。文章基于自適應(yīng)諧振理論（ART），提出一種針對數(shù)據(jù)流聚類的自適應(yīng)兩階段聚類算法（ATPC）。該算法分為在線自適應(yīng)微聚類和離線全局批量聚類兩個階段，自適應(yīng)生成微簇，具有線性計算復(fù)雜度。在MOA平臺上真實與模擬數(shù)據(jù)流的實驗結(jié)果驗證了ATPC方法的高效性。

關(guān)鍵詞：數(shù)據(jù)流;聚類;兩階段;自適應(yīng)諧振理論;微簇

中圖分類號：TP311.13 文獻標(biāo)識碼：A文章編號：2096-4706（2021）14-0124-03

Abstract： K-means is the most commonly used batch clustering method， however， this algorithm requires several iterations and cannot be directly used for data stream clustering. In this paper， we propose an adaptive algorithm with two phases for data stream clustering （ATPC） based on adaptive resonance theory （ART）. ATPC is divided into two phases， online adaptive microclustering and offline global batch clustering， and adaptively generates microclusters with linear computational complexity. Experimental results on the real dataset and simulated data streams validate the efficiency of ATPC method.

Keywords： data stream; clustering; two phases; adaptive resonance theory; micro cluster

0 ?引 ?言

社交網(wǎng)絡(luò)、移動通信、物聯(lián)網(wǎng)等眾多快速發(fā)展的產(chǎn)生數(shù)據(jù)流場景，迫切需要滿足數(shù)據(jù)流特征的實時聚類技術(shù)[1-3]。數(shù)據(jù)流本質(zhì)上可視為只能讀取一次的數(shù)據(jù)序列。設(shè)計數(shù)據(jù)流聚類算法，必須滿足如下數(shù)據(jù)流公理[4，5]：

（1）每個數(shù)據(jù)項只能被觀察和處理一次。

（2）處理每個數(shù)據(jù)項只能消耗較少的時間。

（3）只能存儲一小部分?jǐn)?shù)據(jù)項，其內(nèi)存占用與數(shù)據(jù)流長度成亞線性（sublinear）關(guān)系。

（4）必須做到隨時提供算法的解答。

（5）能夠有效檢測與處理數(shù)據(jù)流的概念漂移。

K-means算法是離線聚類的基礎(chǔ)方法之一[6]。該算法需要在數(shù)據(jù)集上迭代優(yōu)化，并且還要預(yù)先指定簇的個數(shù)。然而，由聚類創(chuàng)建的簇的數(shù)量在學(xué)習(xí)開始之前是未知的，例如細分營銷客戶群體、社交網(wǎng)絡(luò)中尋找社區(qū)等。因此，K-means無法直接用于數(shù)據(jù)流聚類。

與K-means方法不同，自適應(yīng)諧振理論（adaptive resonance theory， ART）可以實現(xiàn)樣本數(shù)據(jù)新建模式類的自適應(yīng)。聚類過程中，當(dāng)輸入樣本與當(dāng)前某一模式類高度相似時則將其歸為這一模式類，而當(dāng)所有模式類的相似度都不超過警戒門限時，則新建模式類來存儲當(dāng)前輸入模式，自動增加聚類簇的個數(shù)[7，8]。

基于ART理論，數(shù)據(jù)流聚類在線階段可以實現(xiàn)自適應(yīng)微聚類;然后，我們以保存在線階段統(tǒng)計數(shù)據(jù)的微簇（microcluster）為偽點，數(shù)據(jù)流聚類的離線階段進一步消除噪音并全局聚類。

1 ?相關(guān)工作

1.1 ?K-means算法

K-means算法計算數(shù)據(jù)點彼此之間的距離，依靠相似性進行分組。K-均值算法是一種無監(jiān)督的迭代優(yōu)化學(xué)習(xí)算法，將一個給定的數(shù)據(jù)集分類為K個聚類。算法不斷進行迭代計算和調(diào)整，直到達到一個理想的結(jié)果。K-means算法的偽代碼為：

1 初始化：樣本數(shù)n， 聚類數(shù)K，

原始聚類中心u1，…，uk;

2 ?do 按照最近鄰ui （i=1，…，k）分類n個樣本;

3 ? ? 重新計算聚類中心u1，…，uk;

4 ?until u1，…，uk不再改變;

5 ?return u1，…，uk.

K-means算法中“K”的選取是人為選定的，需要事先指定劃分的簇的個數(shù)。絕大部分的實際運用中，我們是無法提前預(yù)知數(shù)據(jù)樣本簇的個數(shù)，導(dǎo)致K-means算法的結(jié)果可能不符合真實情況。

K-Means本質(zhì)上是一種傳統(tǒng)的離線聚類算法，它需要反復(fù)對數(shù)據(jù)集進行迭代，不斷調(diào)整質(zhì)心位置直到質(zhì)心趨于穩(wěn)定[6]。而由于數(shù)據(jù)流的連續(xù)性和無窮性，導(dǎo)致幾乎不可能將數(shù)據(jù)樣本存儲下來并反復(fù)迭代，故無法對數(shù)據(jù)流使用K-Means算法來完成聚類。

1.2 ?數(shù)據(jù)流sketch數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)流聚類問題的解決方案都使用了數(shù)據(jù)流sketch的概念。一個sketch是一個數(shù)據(jù)結(jié)構(gòu)，自帶算法讀取數(shù)據(jù)流并存儲足夠的信息，以便能夠回答一個或多個關(guān)于數(shù)據(jù)流的查詢要求[9]。我們將sketch視為更高級別數(shù)據(jù)流學(xué)習(xí)和挖掘算法的基本組成部分。由于這些算法會創(chuàng)建許多sketch用于同時跟蹤不同的統(tǒng)計數(shù)據(jù)，因此要求sketch只能使用少量的內(nèi)存。

一個sketch算法主要包含三個操作：

（1）Init（...）操作：初始化數(shù)據(jù)結(jié)構(gòu)，可能有一些參數(shù)，如要使用的內(nèi)存量。

（2）Update（項）操作，將應(yīng)用于流上的每個數(shù)據(jù)項。

（3）Query（...）操作：返回到目前為止讀取的數(shù)據(jù)流上感興趣的函數(shù)的當(dāng)前值（也可能沒有參數(shù)）。

1.3 ?自適應(yīng)諧振理論ART

神經(jīng)網(wǎng)絡(luò)中自適應(yīng)諧振理論ART可以實現(xiàn)對樣本數(shù)據(jù)自適應(yīng)的新建模式類[10]。一般來說，ART模型由輸入層（F1）和識別層（F2）組成，如圖1所示。自適應(yīng)諧振的運行過程主要分為四個階段：識別階段、比較階段、搜索階段和學(xué)習(xí)階段。

訓(xùn)練過程中，當(dāng)輸入樣本與當(dāng)前神經(jīng)網(wǎng)絡(luò)中某一模式類高度相似時自動將其歸為這一模式類;當(dāng)所有模式類的相似度都不超過警戒門限即無法匹配當(dāng)前網(wǎng)絡(luò)中任意一模式類時，則新建模式類來存儲當(dāng)前輸入模式，從而實現(xiàn)對數(shù)據(jù)流的聚類且自動增加聚類簇的個數(shù)，在提高數(shù)據(jù)流聚類性能的同時，也彌補了K-means算法預(yù)定簇類的缺陷。

2 ?自適應(yīng)兩階段數(shù)據(jù)流聚類方法

基于sketch概念和ART機制，本文設(shè)計的數(shù)據(jù)流的聚類算法分為在線與離線兩個階段。

2.1 ?在線階段

考慮一個數(shù)據(jù)流x（1），x（2），...，x（n），...，每個實例包含d個特征，x（n）=∈Rd。在任何時候到達的實例，都進入到微簇中，過程如下：

（1）首先讀入第一條實例，構(gòu)造包含一個實例的微簇。

（2）陸續(xù)接收第2條實例、第3條實例…。每個實例到達時，計算該實例與目前所有微簇特征向量的距離，實例加入距離最近的微簇。

（3）實例加入距離最近的微簇后，如果此時的簇直徑已經(jīng)大于T，則新建一個包含該實例的微簇。

微簇是旨在壓縮進入到其中的數(shù)據(jù)流實例的一種sketch結(jié)構(gòu)，本文定義微簇為：

定義1：微簇（micro cluster， MC）。微簇是微聚類的一種壓縮結(jié)構(gòu)，用于表示聚類特征樹葉子節(jié)點中實例的統(tǒng)計信息，MC=（n，LS，SS，T，L）。其中，

標(biāo)量n：到目前為止的實例數(shù)量;

向量LS=，到目前為止的實例之和;

向量SS，到目前為止的實例的平方和，其中

SSj=;

T：微簇直徑;

L：孩子節(jié)點數(shù)量閾值。

根據(jù)微簇定義，可以很容易計算微簇中心向量=LS/n。同時，向現(xiàn)有MC添加實例和合并兩個現(xiàn)有MC的操作也是非常直接和簡單的。

2.2 ?離線階段

離線階段使用在線階段形成的sketch，以有規(guī)律的時間間隔或者按需高效地計算全局最終的聚類。

本文的離線階段主要由兩個過程組成。首先，積極檢測不屬于真實聚類的隨機數(shù)據(jù)，消除噪音。把目前所有的MC根據(jù)其大小按降序排序，得到一個正的分布。然后，噪聲將出現(xiàn)在右下尾部，我們首先通過切割后45%的點來消除這個尾巴。

當(dāng)微簇實例數(shù)量分布的尾巴消失后，離線階段再以剩余的微簇為偽點，采用傳統(tǒng)的K-means方法按需高效計算最終聚類。

自適應(yīng)兩階段數(shù)據(jù)流聚類方法符合數(shù)據(jù)流聚類的全部要求。

3 ?實驗結(jié)果與分析

Massive Online Analysis（MOA）是數(shù)據(jù)流分析主流平臺，本文實驗使用MOA生成的人工數(shù)據(jù)流、以及真實數(shù)據(jù)集對算法的性能進行評價和比較。實驗在2.60 GHz、Intel（R） Core（TM） i7-6700HQ CPU、內(nèi)存16 GB、操作系統(tǒng)Windows 10的計算機上進行。

3.1 ?數(shù)據(jù)集

3.1.1 ?人工數(shù)據(jù)集

本文的人工數(shù)據(jù)集使用MOA數(shù)據(jù)流生成器RandomRBFGeneratorEvents，該生成器生成的數(shù)據(jù)點依據(jù)所選范圍具有類標(biāo)簽，以及反映數(shù)據(jù)點年齡的權(quán)重。所有聚類類別都具有同樣期望的數(shù)據(jù)點數(shù)量。

RandomRBFGeneratorEvents數(shù)據(jù)流生成器包含的參數(shù)有：

在數(shù)據(jù)空間中移動的聚類數(shù)量;

生成數(shù)據(jù)點的數(shù)量;

移動時間間隔;

聚類半徑;

維度;

噪聲率。

3.1.2 ?真實數(shù)據(jù)集

kddcup.data_10_percent是KDD Cup 1999競賽項目10%的訓(xùn)練數(shù)據(jù)集，共有494 021個樣本，用于預(yù)測網(wǎng)絡(luò)連接是“異?！边B接類型或“正?！边B接類型。本文預(yù)處理該數(shù)據(jù)集后，形成kddcup.data_10_percent_corrected.arff文件，用于真實數(shù)據(jù)集聚類分析。

kddcup.data數(shù)據(jù)集的每個樣本包含41個條件屬性，一個類別屬性。42個屬性中，33個是連續(xù)的數(shù)字類型，其余9個屬性是離散類型，即標(biāo)稱型屬性。

3.2 ?實驗結(jié)果與分析

實驗采用聚類映射度量（Cluster Mapping Measure， CMM）、純度（Purity， P）、剪影系數(shù)（Silhouette Coefficient， SC）三種性能指標(biāo)評估聚類性能。比較方法有ATPC

（adaptive two phases algorithm for data stream clustering）、clustream、denstream和ClusTree等。

表1是四種聚類方法在人工數(shù)據(jù)流上的聚類實驗結(jié)果。RandomRBFGeneratorEvents數(shù)據(jù)流樣本數(shù)量為50 000，樣本維度（dimensionality）分別取2、5、10、20，各場景的性能最佳值用加粗標(biāo)示，NA表示MOA內(nèi)存溢出。

表2是四種聚類方法在真實數(shù)據(jù)集kddcup1999上的聚類性能結(jié)果，性能度量和表1一樣，也采用聚類映射度量CMM、純度P、剪影系數(shù)SC三種性能評估指標(biāo)，最佳值加粗。

從表1和表2的實驗結(jié)果，我們不難看出：無論是人工數(shù)據(jù)流，還是真實數(shù)據(jù)集，本文提出的ATPC聚類方法，在大部分的場景下，其綜合聚類性能優(yōu)于其他流行的方法。

4 ?結(jié) ?論

數(shù)據(jù)流聚類通常采用兩階段聚類。本文基于自適應(yīng)諧振理論ART，在線階段自適應(yīng)微聚類，微簇個數(shù)自動生成。離線階段先消除噪聲再全局聚類，具有線性計算復(fù)雜度。在MOA平臺上對真實與模擬數(shù)據(jù)流進行了實驗，結(jié)果表明本文提出的方法是有效的。

參考文獻：

[1] BEYAZIT E，ALAGURAJAH J，WU X D. Online Learning from Data Streams with Varying Feature Spaces [J].Proceedings of the 33rd AAAI Conference on Artificial Intelligence，2019，33（1）：3232-3239.

[2] SCHNEIDER J，VLACHOS M. On Randomly Projected Hierarchical Clustering with Guarantees [C]//Proceedings of the 2014 SIAM International Conference on Data Mining（SDM）.Philadelphia：SIAM，2014：407-415.

[3] BIFET A，GAVALDA R，HOLMES G，et al. Machine learning for data streams：with practical examples in MOA [M].USA：Massachusetts Institute of Technology press，2017.

[4] SCHNEIDER J，VLACHOS M. Fast parameterless density-based clustering via random projections [C]//CIKM’13：Proceedings of the 22nd ACM international conference on Information & Knowledge Management.New York：ACM，2013：861-866.

[5] ANDRéS-MERINO J，BELANCHE L. StreamLeader：A New Stream Clustering Algorithm not Based in Conventional Clustering [C]//Artificial Neural Networks and Machine Learning–ICANN 2016.Barcelona：September，2016：208–215.

[6] YE M，LIU W F，WEI J H，et al. Fuzzy c-Means and Cluster Ensemble with Random Projection for Big Data Clustering [J/OL].Mathematical Problems in Engineering，2016（1）：1-13.

[7] HE Y，WU B，WU D，et al. Online learning from capricious data streams [C]//Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence，Macao：IJCAI，2019：2491-2497.

[8] LOSING V，HAMMER B，WERSING H，et al. Randomizing the Self-Adjusting Memory for Enhanced Handling of Concept Drift [C]//2020 International Joint Conference on Neural Networks（IJCNN）.Glasgow：IEEE，2020：1-8.

[9] KRANEN P，ASSENT I，BALDAUF C，et al. The ClusTree：indexing micro-clusters for anytime stream mining [J].Knowledge and Information Systems，2011，29（2）：249–272.

[10] 朱穎雯，陳松燦.基于隨機投影的高維數(shù)據(jù)流聚類 [J].計算機研究與發(fā)展，2020，57（8）：1683-1696.

作者簡介：李志杰（1964—），男，漢族，湖南永興人，博士，副教授，研究方向：大數(shù)據(jù)在線學(xué)習(xí);廖旭紅（1997—），女，漢族，湖南醴陵人，碩士研究生在讀，研究方向：數(shù)據(jù)流聚類;劉基旺（1997—），男，土家族，湖南永順人，碩士研究生在讀，研究方向：數(shù)據(jù)流分類;江華（1997—），男，漢族，安徽合肥人，碩士研究生在讀，研究方向：數(shù)據(jù)流分類。