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

朱俚治　朱梧檟

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

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

中圖分類號：TP372 文獻標識碼：A

1 引 言

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

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

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

2 混合屬性數(shù)據(jù)流概念的簡介和及其應用

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

1.當今網(wǎng)絡中的數(shù)據(jù)流可以分為三種屬性數(shù)據(jù)流：①連續(xù)型數(shù)據(jù)流，②標稱型數(shù)據(jù)流，③混合型數(shù)據(jù)流。連續(xù)型數(shù)據(jù)流是指數(shù)據(jù)的取值是連續(xù)性的，標出型數(shù)據(jù)流是指數(shù)據(jù)的取值為有限的狀態(tài)，混合屬性數(shù)據(jù)流是指數(shù)據(jù)同時具有連續(xù)屬性和標稱屬性的數(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]。

計算技術與自動化2016年6月

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

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

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

3 k近鄰算法

基于實例的學習方法中的最基本的是k-鄰近算法。這個算法假定所有的實例對應于n維空間中的點。一個實例的最近鄰是根據(jù)標準歐氏距離定義的。更精確地講把任意的實例x表示為下面的特征向量[6-8]。

4 k近鄰算法的應用

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

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

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

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

4.2 k近鄰算法距離公式的應用

1.實例A與實例B的屬性距離

1）aim表示實例A進行分類時的能夠起到分類作用的屬性，B表示儲存器中一個的實例。實例B具有的分類作用的屬性bim。

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

3）如果當ai（d+1）-bi（d+1）≈0，ai（d+2）-bi（d+2）≈0…aim-bim≈0時，則有ai（d+1）bi（d+1）≈1，ai（d+2）bi（d+2）≈1…aimbim≈1

2.實例A與實例B屬性距離計算公式

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

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

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

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

3.在實例A的屬性與實例B的屬性相似性的計算

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

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

4.在實例A的屬性與實例B的屬性偏離性的計算

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

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

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

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

5.實例A與實例B屬性的比較結論

1）實例A屬性為{ai（d+1），ai（d+2），…，aim}，實例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，則實例A與實例B的屬性是較為相似。

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

5 k均值聚類算法的應用

5.1 k均值算法基本概念簡介

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

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

6 聚類算法

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

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

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

7 結束語

混合屬性數(shù)據(jù)流技術是由網(wǎng)絡技術的發(fā)展而產生的新屬性數(shù)據(jù)，該屬性的數(shù)據(jù)流與連續(xù)屬性的數(shù)據(jù)流和標稱屬性的數(shù)據(jù)流形成當今網(wǎng)絡中主要的三種數(shù)據(jù)流。對于網(wǎng)絡管理人員來說要保證網(wǎng)絡的安全性和維護網(wǎng)絡的正常運行，對流量的監(jiān)測是必須的。如果要對網(wǎng)絡流量進行監(jiān)控，必須對數(shù)據(jù)流進行識別。對網(wǎng)絡中的流進行的識別之時，必須進行相同屬性流的聚類，因此流的聚類對識別流來說是相當重要的?；谏鲜鲈虮疚奶岢隽艘环N對混合屬性數(shù)據(jù)流進行聚類的算法，該算法具有一定的合理性和和科學性，因此該算方法具有一定的應用價值和一定的應用領域。

參考文獻

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

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

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

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

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

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

[7] 林關成.基于改進K近鄰算法支持向量分類研究[J].渭南師范學院學報，2012，（2）：83-86.

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

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