一種數(shù)據(jù)流自適應(yīng)兩階段聚類算法

李志杰 廖旭紅 劉基旺 江華

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

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

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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ò)、移動(dòng)通信、物聯(lián)網(wǎng)等眾多快速發(fā)展的產(chǎn)生數(shù)據(jù)流場(chǎng)景，迫切需要滿足數(shù)據(jù)流特征的實(shí)時(shí)聚類技術(shù)[1-3]。數(shù)據(jù)流本質(zhì)上可視為只能讀取一次的數(shù)據(jù)序列。設(shè)計(jì)數(shù)據(jù)流聚類算法，必須滿足如下數(shù)據(jù)流公理[4，5]：

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

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

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

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

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

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

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

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

1 ?相關(guān)工作

1.1 ?K-means算法

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

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

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

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

3 ? ? 重新計(jì)算聚類中心u1，…，uk;

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

5 ?return u1，…，uk.

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

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

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

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

一個(gè)sketch算法主要包含三個(gè)操作：

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

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

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

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

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

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

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

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

2.1 ?在線階段

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

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

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

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

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

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

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

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

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

SSj=;

T：微簇直徑;

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

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

2.2 ?離線階段

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

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

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

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

3 ?實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

移動(dòng)時(shí)間間隔;

聚類半徑;

維度;

噪聲率。

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

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

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

3.2 ?實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

4 ?結(jié) ?論

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

參考文獻(xiàn)：

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

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