一種實(shí)現(xiàn)混合屬性數(shù)據(jù)流聚類的算法

朱俚治　朱梧檟

摘 要：在當(dāng)今的網(wǎng)絡(luò)中存在三種形式的數(shù)據(jù)流，連續(xù)型數(shù)據(jù)流，標(biāo)稱型數(shù)據(jù)流和混合屬性數(shù)據(jù)流。由于目前在數(shù)據(jù)挖掘中大部分算法只能處理一種屬性的數(shù)據(jù)流，而處理混合屬性數(shù)據(jù)流的算法卻很少，但在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中常常需要將不同屬性的數(shù)據(jù)流進(jìn)行相互區(qū)分。事實(shí)上研究人員在區(qū)分不同屬性數(shù)據(jù)流時(shí)，首先是將不同屬性的流進(jìn)行聚類，其次是對(duì)不同屬性的流進(jìn)行識(shí)別。在查閱有了有關(guān)資料和參考文獻(xiàn)后，本文提出了一種對(duì)混合屬性數(shù)據(jù)流的聚類算法，該算法的聚類思想是：①提取混合屬性數(shù)據(jù)流的分類屬性，②使用k-近鄰算法計(jì)算數(shù)據(jù)流分類屬性的相似性，③根據(jù)k-近鄰算法對(duì)數(shù)據(jù)流相似度的計(jì)算結(jié)果，使用k-均值聚類算法對(duì)混合屬性數(shù)據(jù)流進(jìn)行聚類，④給出聚類的算法。

關(guān)鍵詞：混合屬性數(shù)據(jù)；相似性；k-近鄰算法；k-均值聚類；分類屬性

中圖分類號(hào)：TP372 文獻(xiàn)標(biāo)識(shí)碼：A

1 引 言

當(dāng)今的計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)發(fā)展的速度是快速的，在這些技術(shù)快速發(fā)展的同時(shí)，產(chǎn)生了大量的各種屬性的數(shù)據(jù)，這些數(shù)據(jù)是連續(xù)的、無界的、不定速度的流式數(shù)據(jù)，IT人員將這些數(shù)據(jù)稱為數(shù)據(jù)流[2]。在網(wǎng)絡(luò)中每天都有驚人的流量吞吐量，在這些海量的數(shù)據(jù)中可將這些數(shù)據(jù)流的屬性分為三種型式，連續(xù)屬性數(shù)據(jù)流、標(biāo)稱屬性數(shù)據(jù)流和混合屬性數(shù)據(jù)流。從數(shù)據(jù)流的屬性角度上來看，連續(xù)屬性數(shù)據(jù)流和標(biāo)稱屬性數(shù)據(jù)流是傳統(tǒng)意義上的數(shù)據(jù)流，而混合屬性數(shù)據(jù)流是IT技術(shù)發(fā)展之際產(chǎn)生的新屬性的數(shù)據(jù)流。網(wǎng)絡(luò)管理人員為了從這大量的數(shù)據(jù)流中獲取重要的信息，必須對(duì)這三種屬性的數(shù)據(jù)流進(jìn)行有效準(zhǔn)確的識(shí)別。為了對(duì)未知屬性數(shù)據(jù)流進(jìn)行識(shí)別，第一步是將這些數(shù)據(jù)流進(jìn)行聚類。盡管目前有多種數(shù)據(jù)流的聚類算法，但這些大部分算法都是用于傳統(tǒng)意義上的數(shù)據(jù)流，而對(duì)混合屬性數(shù)據(jù)流的聚類算法相對(duì)較少。為了檢測(cè)網(wǎng)絡(luò)流量中的混合屬性數(shù)據(jù)流，在聚類算法這方面研究主要有以下幾種算法：有Guha等人提出的STREAM聚類算法、Aggarwal提出的clustrem的改算法和Ong等人根據(jù)clustrem提出的利用標(biāo)稱屬性作為聚類條件的SCLOPE等算法[2]。本文的作者在查閱了一些有關(guān)文獻(xiàn)和一些聚類算法之后提出了一種實(shí)現(xiàn)混合屬性數(shù)據(jù)流的聚類算法，在本文中仍然以混合屬性數(shù)據(jù)流的分類屬性作為聚類的前提條件。以下是本文聚類算法中使用的算法的簡(jiǎn)介。

決策樹，k近鄰算法和貝葉斯等算法是當(dāng)前研究的較多和主流的數(shù)據(jù)分類應(yīng)用算法。k近鄰算法對(duì)實(shí)例進(jìn)行分類時(shí)必須根據(jù)已知實(shí)例，該算法在識(shí)別數(shù)據(jù)的屬性時(shí)，必須提取待分類實(shí)例的各種屬性，再將該實(shí)例的各種屬性分別與已知實(shí)例的各種進(jìn)行逐一比較[6]。在最終的比較結(jié)果中如果有k個(gè)實(shí)例與待分類的實(shí)例屬性相同，那么就將這個(gè)待分類的實(shí)例與k個(gè)實(shí)例分為一類[6]。

目前，常用的聚類算法有基于劃分的聚類算法，基于層次的聚類算法和基于密度的算法。基于基于劃分的聚類的算法就是將聚類的對(duì)象劃分k個(gè)分組，每個(gè)分組代表一個(gè)聚類，在每個(gè)聚類分組中通過距離公式計(jì)算聚類對(duì)象的相似性來完成聚類。k-均值聚類算法是一常見的基于劃分的聚類算法，通過有限次數(shù)的迭代來完成對(duì)象之間的聚類，該算法的特點(diǎn)是實(shí)現(xiàn)起來較為簡(jiǎn)單，同時(shí)適合大規(guī)模數(shù)據(jù)的聚類，該算法的實(shí)用性較強(qiáng)，因此k-均值在各個(gè)科學(xué)領(lǐng)域都有廣泛的應(yīng)用，大多數(shù)的聚類過程中都采用該算法為聚類的算法[4-5]。

2 混合屬性數(shù)據(jù)流概念的簡(jiǎn)介和及其應(yīng)用

2.1 混合屬性數(shù)據(jù)流的基本概念

1.當(dāng)今網(wǎng)絡(luò)中的數(shù)據(jù)流可以分為三種屬性數(shù)據(jù)流：①連續(xù)型數(shù)據(jù)流，②標(biāo)稱型數(shù)據(jù)流，③混合型數(shù)據(jù)流。連續(xù)型數(shù)據(jù)流是指數(shù)據(jù)的取值是連續(xù)性的，標(biāo)出型數(shù)據(jù)流是指數(shù)據(jù)的取值為有限的狀態(tài)，混合屬性數(shù)據(jù)流是指數(shù)據(jù)同時(shí)具有連續(xù)屬性和標(biāo)稱屬性的數(shù)據(jù)流[1-3]。

2.混合屬性數(shù)據(jù)流集合表示為 ，集合x分類屬性， ，其中：數(shù)值屬性的 ，分類屬性為 [1-3]。

1）混合屬性數(shù)據(jù)流的數(shù)值屬性的含義是：該屬性的數(shù)據(jù)取值是連續(xù)型[1-3]。

2）混合屬性數(shù)據(jù)流的分類屬性的含義是：該屬性的數(shù)據(jù)取值是有限的狀態(tài)[1-3]。

計(jì)算技術(shù)與自動(dòng)化2016年6月

第35卷第2期朱俚治等：一種實(shí)現(xiàn)混合屬性數(shù)據(jù)流聚類的算法

由于目前一些面向混合屬性數(shù)據(jù)流的聚類算法將分類屬性作為混合屬性數(shù)據(jù)流聚類的條件，因此在本文中仍然以混合屬性數(shù)據(jù)流的分類屬性作為聚類的前提條件。

2.2 混合屬性數(shù)據(jù)流概念的應(yīng)用

3 k近鄰算法

基于實(shí)例的學(xué)習(xí)方法中的最基本的是k-鄰近算法。這個(gè)算法假定所有的實(shí)例對(duì)應(yīng)于n維空間中的點(diǎn)。一個(gè)實(shí)例的最近鄰是根據(jù)標(biāo)準(zhǔn)歐氏距離定義的。更精確地講把任意的實(shí)例x表示為下面的特征向量[6-8]。

4 k近鄰算法的應(yīng)用

4.1 數(shù)據(jù)流Ai與數(shù)據(jù)流Bi的屬性

某個(gè)已知的數(shù)據(jù)流Ai具有的數(shù)值屬性的{ai1，ai2，…，aid}，分類屬性為{ai（d+1），ai（d+2），…，aim}。

某個(gè)未知的數(shù)據(jù)流Bi具有的數(shù)值屬性的{bi1，bi2，…bid}，分類屬性為{bi（d+1），bi（d+2），…，bim}。

以下使用k-近鄰算法計(jì)算混合屬性數(shù)據(jù)流Ai與Bi中的分類屬性的相似度。

4.2 k近鄰算法距離公式的應(yīng)用

1.實(shí)例A與實(shí)例B的屬性距離

1）aim表示實(shí)例A進(jìn)行分類時(shí)的能夠起到分類作用的屬性，B表示儲(chǔ)存器中一個(gè)的實(shí)例。實(shí)例B具有的分類作用的屬性bim。

2）d1表示ai（d+1）與bi（d+1）之間的距離，d2表示ai（d+2）與bi（d+2）之間的距離，……dn表示aim與bim之間的距離。

3）如果當(dāng)ai（d+1）-bi（d+1）≈0，ai（d+2）-bi（d+2）≈0…aim-bim≈0時(shí)，則有ai（d+1）bi（d+1）≈1，ai（d+2）bi（d+2）≈1…aimbim≈1

2.實(shí)例A與實(shí)例B屬性距離計(jì)算公式

1）實(shí)例A與實(shí)例B屬性的偏離估量函數(shù)

函數(shù)：f（x）=1-實(shí)例A的分類屬性值實(shí)例B的分類屬性值

2）實(shí)例A與實(shí)例B屬性相似程度的估計(jì)函數(shù)

函數(shù)： g（x）=1-f（x）

3.在實(shí)例A的屬性與實(shí)例B的屬性相似性的計(jì)算

1）在實(shí)例A的屬性與實(shí)例B的屬性比較過程中，如果對(duì)象aim的屬性十分接近于已知對(duì)象bim的屬性時(shí)，那么aimbim的比值將十分逼近1值。當(dāng)aimbim的比值十分逼近1時(shí)，這時(shí)f（x）=1-aimbim，并且k-近鄰算法中的距離dn就十分接近于0的值。當(dāng)實(shí)例aim的屬性偏離已知實(shí)例的bim屬性大小將趨向于0之時(shí)，則有dn的值越小，并且該值趨向于0時(shí)，這是則A的屬性偏離的B屬性概率就越小。

2）當(dāng)y=f（x）的值越小，則對(duì)象A的屬性偏離B的概率就越小。當(dāng)y=f（x）的值越小時(shí)，那么g（x）=1-f（x）的值就越大，這是表示對(duì)象A的屬性偏離B的概率就越小。如果對(duì)象A的屬性偏離B的概率越小，則對(duì)象A與B之間的相似度就越強(qiáng)。

4.在實(shí)例A的屬性與實(shí)例B的屬性偏離性的計(jì)算

1）在實(shí)例A的屬性與實(shí)例B的屬性比較過程中，如果A對(duì)象的屬性大于已知對(duì)象B的屬性時(shí)，那么aimbim的比值將大于1時(shí)。當(dāng)aimbim的比值越大時(shí)，函數(shù)f（x）=1-aimbim的值大于0的程度將越明顯，并且k-近鄰算法中的距離dn偏離0的程度就越大，則A的屬性與B的屬性偏離程度就越大。

當(dāng)y=f（x）的值越大時(shí)，那么g（x）=1-f（x）的值就小，這是表示對(duì)象A的屬性偏離B的概率就越大，則對(duì)象A與B之間的相似度就越差。

2）在實(shí)例A的屬性與實(shí)例B的屬性比較過程中，如果需對(duì)象的A屬性小于已知對(duì)象B的屬性時(shí)，那么aimbim的比值將小于1時(shí)。當(dāng)aimbim的比值越小時(shí)，函數(shù)f（x）=1-aimbim的值小于1的程度將越明顯，并且k-近鄰算法中的距離dn偏離0的程度就越大，則A的屬性與B的屬性偏離程度就越大。

當(dāng)y=f（x）的值越小時(shí)，那么g（x）=1-f（x）的值就大，這是表示對(duì)象A的屬性偏離B的概率就越大，則對(duì)象A與B之間的相似度就越差。

5.實(shí)例A與實(shí)例B屬性的比較結(jié)論

1）實(shí)例A屬性為{ai（d+1），ai（d+2），…，aim}，實(shí)例B分類屬性為{bi（d+1），bi（d+2），…，bim}。

2）d1表示ai（d+1）與bi（d+1）之間的距離，d2表示ai（d+2）與bi（d+2）之間的距離，……dn表示aim與bim之間的距離。

3）如果d1≈0，d2≈0，…dn≈0，則實(shí)例A與實(shí)例B的屬性是較為相似。

4）如果實(shí)例A與實(shí)例B的屬性是較為相似，則使用k均值聚類算法對(duì)實(shí)例A與實(shí)例B進(jìn)行聚類了。

5 k均值聚類算法的應(yīng)用

5.1 k均值算法基本概念簡(jiǎn)介

1.k均值算法的聚類思想

k均值聚類算法在尋找對(duì)象之間相似性的度量通常是歐幾里德距離的倒數(shù)，也就是說兩者的距離越小表示兩者的相似就越大，反之則相似性就越小[4-5]。的思想是：該算法的思想是：把所有需要聚類的數(shù)據(jù)分成若干個(gè)類，如果在每個(gè)類中數(shù)據(jù)屬性相似程度較高，那么將每個(gè)類中所有屬性值求平均值，每個(gè)類的平均值成為這個(gè)類的聚類中心。之后根據(jù)每個(gè)類的平均值的相似程度開始聚類。該算法的聚類過程是：根據(jù)相似程度不同的若干個(gè)類，將其中相似程度最高的兩個(gè)類聚為一個(gè)類，當(dāng)每次聚類完成后再次計(jì)算該類的平均值，即新的類的中心值，然后再根據(jù)新的中心值，再次進(jìn)行聚類。如此重復(fù)，直到類的平均值不再變化為止。

6 聚類算法

1.需要聚類的混合屬性數(shù)據(jù)的流。

2.k近鄰算法計(jì)算混合屬性數(shù)據(jù)流的相似程度。

3.根據(jù)混合屬性數(shù)據(jù)流的相似程度使用k均值算法對(duì)相似的流進(jìn)行聚類。

7 結(jié)束語

混合屬性數(shù)據(jù)流技術(shù)是由網(wǎng)絡(luò)技術(shù)的發(fā)展而產(chǎn)生的新屬性數(shù)據(jù)，該屬性的數(shù)據(jù)流與連續(xù)屬性的數(shù)據(jù)流和標(biāo)稱屬性的數(shù)據(jù)流形成當(dāng)今網(wǎng)絡(luò)中主要的三種數(shù)據(jù)流。對(duì)于網(wǎng)絡(luò)管理人員來說要保證網(wǎng)絡(luò)的安全性和維護(hù)網(wǎng)絡(luò)的正常運(yùn)行，對(duì)流量的監(jiān)測(cè)是必須的。如果要對(duì)網(wǎng)絡(luò)流量進(jìn)行監(jiān)控，必須對(duì)數(shù)據(jù)流進(jìn)行識(shí)別。對(duì)網(wǎng)絡(luò)中的流進(jìn)行的識(shí)別之時(shí)，必須進(jìn)行相同屬性流的聚類，因此流的聚類對(duì)識(shí)別流來說是相當(dāng)重要的。基于上述原因本文提出了一種對(duì)混合屬性數(shù)據(jù)流進(jìn)行聚類的算法，該算法具有一定的合理性和和科學(xué)性，因此該算方法具有一定的應(yīng)用價(jià)值和一定的應(yīng)用領(lǐng)域。

參考文獻(xiàn)

[1] 黃德才，沈仙橋，陸億紅.混合屬性數(shù)據(jù)流的二重k近鄰聚類算法[J].計(jì)算機(jī)科學(xué)，2013， 40（10）：226-230.

[2] 楊春宇，周杰.一種混合屬性數(shù)據(jù)流聚類算法[J].計(jì)算機(jī)學(xué)報(bào)，200730（8）：13564-1371.

[3] 廖志芳，羅浩，樊曉平，等.一種面向混合屬性數(shù)據(jù)聚類的新算法[J].控制與決策，2009， 24（5）：697-700.

[4] 謝娟英，蔣帥，王春霞，等.一種改進(jìn)的全局k均值聚類算法[J].陜西師范大學(xué)學(xué)報(bào)：自然科學(xué)版.2010， 38（2）：18-22.

[5] 胡偉.改進(jìn)的層次k均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013， 49（2）：157-159.

[6] TomM.Mitchell著.機(jī)器學(xué)習(xí)[M].北京：機(jī)械工業(yè)出版社，2013.

[7] 林關(guān)成.基于改進(jìn)K近鄰算法支持向量分類研究[J].渭南師范學(xué)院學(xué)報(bào)，2012，（2）：83-86.

[8] 陸微微，劉晶.一種提高K-近鄰算法效率的新算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，（4）：163-178.

[9] 羅森林，馬駿，潘麗敏.數(shù)據(jù)挖掘理論與技術(shù)[M].北京：電子工業(yè)出版社，2013.