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

廖江陵，管有慶

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

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

1 概 述

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

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

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

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

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

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

2 基本概念及公式

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

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

(1)

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

(2)

典型性可定義為：

(3)

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

(4)

(5)

(6)

歸一化離心率為：

(7)

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

(8)

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

(9)

化簡(jiǎn)得到：

(10)

其中

(11)

(12)

歸一化離心率為：

(13)

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

3 算法基本思想

圖1 簇樣本模型

3.1簇的更新

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

(14)

(15)

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

(16)

(17)

(18)

(19)

(20)

圖2 簇的更新

3.2新簇的創(chuàng)建

3.3簇的合并

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

圖4 簇的合并

(21)

(22)

(23)

4 實(shí)驗(yàn)與分析

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

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

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

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

(25)

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

平均簇純度可定義為：

(26)

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

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

圖6 與DenStream和CluStream算法的比較

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

5 結(jié)束語(yǔ)

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

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

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

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

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

[4] 劉大有,陳慧靈,齊 紅,等.時(shí)空數(shù)據(jù)挖掘研究進(jìn)展[J].計(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í)時(shí)數(shù)據(jù)流聚類的研究新進(jìn)展[J].計(jì)算機(jī)工程與設(shè)計(jì),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ò)出版時(shí)間

時(shí)間：2017-08-01

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

廖江陵(1992-)，男，碩士研究生，研究方向?yàn)檐浖夹g(shù)在通信網(wǎng)絡(luò)中的應(yīng)用;管有慶，副研究員，碩士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)庫(kù)、通信軟件和下一代網(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