廖江陵，管有慶

(南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

一種改進(jìn)的模糊數(shù)據(jù)流聚類算法

廖江陵，管有慶

(南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003)

提出了一種基于TEDA(典型與偏心數(shù)據(jù)分析，Typicality and Eccentricity Data Analysis)模型的模糊數(shù)據(jù)流聚類算法。TEDA模型常用于離群數(shù)據(jù)樣本的檢測，以此來獲得更好的聚類效果。為能夠適應(yīng)在線模糊數(shù)據(jù)流聚類、滿足實時響應(yīng)要求，該算法沿用了TEDA算法中離心率與典型性的概念及相關(guān)公式，用以判斷指定數(shù)據(jù)樣本是否屬于特定數(shù)據(jù)簇或特定數(shù)據(jù)簇群，以此進(jìn)行整個簇群的更新。同時對TEDA算法在處理高維度數(shù)據(jù)流時的不足進(jìn)行補(bǔ)充。該算法具有完全的自主性，能夠自動地創(chuàng)建、更新及合并數(shù)據(jù)簇，并且無需提前定義參數(shù)。不同于傳統(tǒng)聚類算法，該算法無需存儲已掃描數(shù)據(jù)樣本，內(nèi)存利用率高，計算成本低，并且利用遞歸使其更適用于在線實時應(yīng)用。實驗結(jié)果表明，該算法可以很好地對實際數(shù)據(jù)進(jìn)行聚類分析，相對于傳統(tǒng)算法具有一定優(yōu)勢。

典型與偏心數(shù)據(jù)分析；離心率；典型性；聚類

1 概 述

數(shù)據(jù)流聚類技術(shù)[1]已廣泛地應(yīng)用于許多不同的領(lǐng)域，如模式識別[2]、圖像處理[3]、數(shù)據(jù)挖掘[4]等。針對不同領(lǐng)域，存在多種算法，但都受到各種因素的限制。根據(jù)其工作原理，可將這些算法分為三類：離線型、增量型和在線型。離線型聚類算法是將數(shù)據(jù)流上的聚類問題當(dāng)作是對數(shù)據(jù)集進(jìn)行單遍掃描的聚類問題[5-6]，認(rèn)為數(shù)據(jù)流的底層模型不變，即假設(shè)數(shù)據(jù)集是靜態(tài)的，不會受到外界因素的干擾，致使算法的應(yīng)用場景受到

了很大的限制。增量型算法假設(shè)數(shù)據(jù)流底層模型不斷變化，但通常需要存儲此前掃描過的全部或者部分的數(shù)據(jù)樣本。而在線型算法[7]，無需存儲此前掃描過的數(shù)據(jù)樣本。這種算法計算效率高，并且利用遞歸的方法使其更適用于在線的實時應(yīng)用。

作為傳統(tǒng)的聚類算法，k-means[8]和k-NN(k-Nearest Neighbor[9])兩種算法很容易理解，并且在解決某些問題上很實用，但不能應(yīng)用于數(shù)據(jù)流的實時在線處理。例如，k-means算法需要線下批量處理數(shù)據(jù)

的過程，對簇的形狀有限制，而且不適用于噪聲環(huán)境。而k-NN算法在聚類之前需要進(jìn)行額外訓(xùn)練。并且兩種算法都需要將簇的數(shù)量作為輸入?yún)?shù)。此后Guha提出了STREAM[10-11]算法。該算法是一種分離算法，使用了LSEARCH方法，是一種k-median算法的變形。該算法是以塊為單位對數(shù)據(jù)流進(jìn)行處理，通過維持唯一的簇中心權(quán)重k，對數(shù)據(jù)流進(jìn)行聚類，并將生成的簇再一次進(jìn)行聚類，從而產(chǎn)生最終的簇。相似的算法還有StreamKM++[12]等。雖然這些算法考慮了高效內(nèi)存需求、數(shù)據(jù)單次處理等情況，但是不能很好地處理數(shù)據(jù)流不斷演化的問題。為了讓用戶靈活地捕捉數(shù)據(jù)流不斷演化的行為，Aggarwal等[13]提出了CluStream模型。該模型的核心思想是結(jié)合在線和離線兩個階段對數(shù)據(jù)流進(jìn)行聚類。在線部分通過維持固定數(shù)量的微簇對數(shù)據(jù)流進(jìn)行聚類，離線部分則使用k-means聚類算法對微簇再一次進(jìn)行聚類。基于上述微簇及在線和離線的概念，DenStream[14]算法可以在噪聲環(huán)境下對數(shù)據(jù)流進(jìn)行聚類并且可以發(fā)現(xiàn)任意形狀的簇。然而此類算法不能很好地應(yīng)對簇的實時更新問題，并且缺乏在線監(jiān)測新簇產(chǎn)生和數(shù)據(jù)對象離群的機(jī)制。

文中算法是在TEDA的基礎(chǔ)上提出的。TEDA算法是建立在RDE(Recursive Density Estimation，遞歸密度估計)算法家族之上，同時對大量的公式進(jìn)行了改進(jìn)，已經(jīng)廣泛應(yīng)用于許多領(lǐng)域。TEDA算法旨在避免傳統(tǒng)的統(tǒng)計類以及概率理論類方法中具有限制性的假設(shè)，例如數(shù)據(jù)對象樣本彼此獨(dú)立，無法處理大量的數(shù)據(jù)集合以及提前對數(shù)據(jù)集合的分布進(jìn)行假設(shè)等。傳統(tǒng)的統(tǒng)計類方法通常適用于隨機(jī)過程，但可能違反或者忽略了數(shù)據(jù)之間實際的依賴性。因此，TEDA作為替代統(tǒng)計類方法的框架，可以有效地應(yīng)用于任何類型數(shù)據(jù)，而不僅僅是純隨機(jī)過程的數(shù)據(jù)。TEDA算法中運(yùn)用了幾種基于n維特征空間中進(jìn)行鄰近分析的新的度量方法，其中的術(shù)語“典型性”類似于在文獻(xiàn)[15]中的概念，即用來描述某個對象能在多大程度上代表某種概念。

高效的聚類算法需要持續(xù)不斷地適應(yīng)隨時間改變的數(shù)據(jù)流底層模型，而且新的數(shù)據(jù)樣本可能致使新簇產(chǎn)生，所以不應(yīng)該假定簇的數(shù)量是固定的。由此，文中提出了一種新的針對在線數(shù)據(jù)流的模糊數(shù)據(jù)流聚類算法，并通過實驗對該算法進(jìn)行驗證。

2 基本概念及公式

對TEDA算法中的基本概念與公式進(jìn)行闡述，并且對該算法在處理高維度數(shù)據(jù)流時的不足進(jìn)行補(bǔ)充。

假設(shè)一個數(shù)據(jù)樣本空間χ∈n,在此空間中定義空間元素與間的距離為并且假設(shè)數(shù)據(jù)樣本是一個有序的序列n,k∈。其中k的物理意義是數(shù)據(jù)樣本到達(dá)的序號，后續(xù)k的意義與此相同。

(1)

第k個數(shù)據(jù)樣本到達(dá)時的離心率可定義為：

(2)

典型性可定義為：

(3)

當(dāng)數(shù)據(jù)集合的維度不高時，使用歐氏距離計算的離心率ξ可被化簡為[16]：

(4)

(5)

(6)

歸一化離心率為：

(7)

當(dāng)涉及到高維度的數(shù)據(jù)集合時，使用歐氏距離的計算方法會導(dǎo)致較低的精確度。此時可使用馬哈拉諾比斯距離進(jìn)行計算：

(8)

協(xié)方差矩陣定義如下：

(9)

化簡得到：

(10)

其中

(11)

(12)

歸一化離心率為：

(13)

其中，N為數(shù)據(jù)集合的維度。

3 算法基本思想

圖1 簇樣本模型

3.1簇的更新

當(dāng)數(shù)據(jù)集合的維度較低時，可使用歐氏距離進(jìn)行計算，得到如下公式：

(14)

(15)

當(dāng)數(shù)據(jù)集合維度較高時，使用馬哈拉諾比斯距離進(jìn)行計算，得到如下公式：

(16)

(17)

(18)

(19)

(20)

圖2 簇的更新

3.2新簇的創(chuàng)建

3.3簇的合并

圖3 新簇的創(chuàng)建

圖4 簇的合并

(21)

(22)

(23)

4 實驗與分析

為了檢驗改進(jìn)算法的性能，使用真實的網(wǎng)絡(luò)數(shù)據(jù)集對算法進(jìn)行測試。該實驗是在安裝了Matlab7.1，CPU主頻為2.1 GHz，內(nèi)存為4G，操作系統(tǒng)為Windows的PC機(jī)上進(jìn)行的。

真實的數(shù)據(jù)集合是MIT林肯實驗室收集的網(wǎng)絡(luò)攻擊檢測數(shù)據(jù)流。該數(shù)據(jù)集合包含五個簇，并且每個連接包含42個特性。連續(xù)的34個特性都可被用作聚類分析。圖5是運(yùn)用文中算法進(jìn)行聚類分析后的結(jié)果。

從圖中可以清晰地發(fā)現(xiàn)存在有五個簇，每個簇中數(shù)據(jù)對象用不同的形狀表示，五角星代表簇的中心，運(yùn)行結(jié)果與數(shù)據(jù)集合的信息相符。由此可以得出結(jié)論，該算法能夠很好地對真實的數(shù)據(jù)流進(jìn)行聚類分析。

同時使用簇純度來衡量聚類的效果。根據(jù)主宰類的信息，可定義簇中主宰的類的比例為：

(25)

圖5 文中算法聚類結(jié)果

平均簇純度可定義為：

(26)

其中，N為已存在的簇的個數(shù)。

在不同時段，文中算法與DenStream算法、ClusStream算法的簇純度對比折線圖如圖6所示。

圖6 與DenStream和CluStream算法的比較

由圖6可知，文中提出的算法聚類后得到的簇的純度整體上要高于DenStream與CluStream算法。因此可以得到結(jié)論，文中算法在簇純度上相對于DenStream與ClusStream算法也具有一定的優(yōu)勢。

5 結(jié)束語

文中算法沿用了TEDA算法中離心率與典型性的概念及相關(guān)公式，通過離心率來判斷數(shù)據(jù)樣本是否屬于特定數(shù)據(jù)簇或特定數(shù)據(jù)簇群，運(yùn)用該算法進(jìn)行聚類得到的簇沒有特定形狀，并且對TEDA算法在處理高維數(shù)據(jù)流時的不足進(jìn)行了補(bǔ)充。算法使用了統(tǒng)計測量方法，如平均值、方差等，以此判斷何時及如何根據(jù)輸入的數(shù)據(jù)流來創(chuàng)建、更新及合并簇。相對于傳統(tǒng)的聚類算法，具有計算成本低、高度自動化等特點，并且無需預(yù)先定義參數(shù)。

該算法適用于需要實時數(shù)據(jù)分析的環(huán)境，由于無需存儲已掃描的數(shù)據(jù)樣本，對內(nèi)存的要求不高，同時也降低了計算的時間成本。該算法是一個自我演化的算法，會自動地創(chuàng)建、更新及合并簇類。實驗結(jié)果表明，算法可以準(zhǔn)確地對數(shù)據(jù)流進(jìn)行聚類分析，并且相對于DenStream和CluStream算法，性能更加優(yōu)越。

[1] 金建國.聚類方法綜述[J].計算機(jī)科學(xué),2014,41:288-293.

[2] 陳振華,余永權(quán),張 瑞.模糊模式識別的幾種基本模型研究[J].計算機(jī)技術(shù)與發(fā)展,2010,20(9):32-35.

[3] 蔣樹強(qiáng),閔巍慶,王樹徽.面向智能交互的圖像識別技術(shù)綜述與展望[J].計算機(jī)研究與發(fā)展,2016,53(1):113-122.

[4] 劉大有,陳慧靈,齊 紅,等.時空數(shù)據(jù)挖掘研究進(jìn)展[J].計算機(jī)研究與發(fā)展,2013,50(2):225-239.

[5] Charikar M,O'Callaghan L,Panigrahy R.Better streaming algorithms for clustering problems[C]//ACM symposium on theory of computing.San Diego,CA,USA:DBLP,2003:30-39.

[6] Domingos P,Hulten G.A general method for scaling up machine learning algorithms and its application to clustering[C]//Proceedings of the eighteenth international conference on machine learning.[s.l.]:[s.n.],2002:106-113.

[7] 張曉龍,曾 偉.實時數(shù)據(jù)流聚類的研究新進(jìn)展[J].計算機(jī)工程與設(shè)計,2009,30(9):2177-2181.

[8] Macqueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of Berkeley symposium on mathematical statistics and probability.[s.l.]:[s.n.],1967:281-297.

[9] Fix E,Hodges J L.Discriminatory analysis nonparametric discrimination:consistency properties[J].International Statistical Review,1951,57(3):238-247.

[10] Guha S,Meyerson A,Mishra N,et al.Clustering data streams:theory and practice[J].IEEE Transactions on Knowledge & Data Engineering,2003,15(3):515-528.

[11] O' Callaghan L,Meyerson A,Motwani R,et al.Streaming-data algorithms for high-quality clustering[C]//International conference on data engineering.[s.l.]:IEEE,2002.

[12] Ackermann M R,Rtens M,Raupach C,et al.StreamKM++:a clustering algorithm for data streams[J].Journal of Experimental Algorithmics,2012,17:173-187.

[13] Aggarwal C C,Yu P S,Han J,et al.A framework for clustering evolving data streams[C]//International conference on very large data bases.[s.l.]:[s.n.],2003:81-92.

[14] Cao F,Ester M,Qian W,et al.Density-based clustering over an evolving data stream with noise[C]//SIAM international conference on data mining.[s.l.]:[s.n.],2006:328-339.

[15] Osherson D,Smith E E.On typicality and vagueness[J].Cognition,1997,64(2):189-206.

[16] Kangin D, Angelov P, Iglesias J A.Autonomously evolving classifier TEDAClass[J].Information Sciences,2016,366:1-11.

AnImprovedFuzzyDataStreamClusteringAlgorithm

LIAO Jiang-ling,GUAN You-qing

(College of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

A new method of fuzzy data steam clustering,which is based on TEDA,is proposed.TEDA is often used in the detection of outlier data samples for obtainment of better clustering results.In order to adapt to online fuzzy data clustering and meet the requirements of real-time response,the proposed algorithm follows the concept of eccentricity and typicality as well as the related formulas in TEDA,and judges whether a certain data sample belongs to a certain data cluster or several data clusters for updating of the entire cluster.At the same time,it also adds the part when TEDA dealt with the high-dimensional data flow.The proposed algorithm can automatically create,update and merge data clusters with complete autonomy,and not need to define parameters in advance.Different from the traditional clustering algorithm,it does not need to store the scanned data samples,with high memory utilization and low computational cost,and uses recursive methods,which make it more suitable for online real-time applications.Experimental results show that the proposed algorithm can carry out clustering analysis of the real data better and has certain advantages over traditional algorithms.

TEDA;eccentricity;typicality;cluster

2016-11-22

2017-03-24 < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2017-08-01

江蘇省高校自然科學(xué)研究計劃項目(05KJD520146)

廖江陵(1992-)，男，碩士研究生，研究方向為軟件技術(shù)在通信網(wǎng)絡(luò)中的應(yīng)用;管有慶，副研究員，碩士生導(dǎo)師，研究方向為數(shù)據(jù)庫、通信軟件和下一代網(wǎng)絡(luò)等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1552.042.html

TP301

A

1673-629X(2017)11-0096-05

10.3969/j.issn.1673-629X.2017.11.021