国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2016-07-20 21:03朱俚治朱梧檟
關(guān)鍵詞:相似性

朱俚治 朱梧檟

摘 要:在當(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ù)的、無(wú)界的、不定速度的流式數(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ù)流的屬性角度上來(lái)看,連續(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è)聚類分組中通過(guò)距離公式計(jì)算聚類對(duì)象的相似性來(lái)完成聚類。k-均值聚類算法是一常見的基于劃分的聚類算法,通過(guò)有限次數(shù)的迭代來(lái)完成對(duì)象之間的聚類,該算法的特點(diǎn)是實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單,同時(shí)適合大規(guī)模數(shù)據(jù)的聚類,該算法的實(shí)用性較強(qiáng),因此k-均值在各個(gè)科學(xué)領(lǐng)域都有廣泛的應(yīng)用,大多數(shù)的聚類過(guò)程中都采用該算法為聚類的算法[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的屬性比較過(guò)程中,如果對(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的屬性比較過(guò)程中,如果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的屬性比較過(guò)程中,如果需對(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ù),也就是說(shuō)兩者的距離越小表示兩者的相似就越大,反之則相似性就越小[4-5]。的思想是:該算法的思想是:把所有需要聚類的數(shù)據(jù)分成若干個(gè)類,如果在每個(gè)類中數(shù)據(jù)屬性相似程度較高,那么將每個(gè)類中所有屬性值求平均值,每個(gè)類的平均值成為這個(gè)類的聚類中心。之后根據(jù)每個(gè)類的平均值的相似程度開始聚類。該算法的聚類過(guò)程是:根據(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é)束語(yǔ)

混合屬性數(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ò)管理人員來(lái)說(shuō)要保證網(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í)別流來(lái)說(shuō)是相當(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.

猜你喜歡
相似性
12個(gè)毫無(wú)違和感的奇妙動(dòng)物組合
基于隱喻相似性研究[血]的慣用句
中西山水田園詩(shī)歌比較
基于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性的鏈路預(yù)測(cè)算法
一種新的郵件過(guò)濾技術(shù)研究
從相似性看水資源保護(hù)公益廣告中多模態(tài)隱喻意義的構(gòu)建
視知覺組織原則在文字設(shè)計(jì)中的運(yùn)用
莊子學(xué)派與犬儒學(xué)派哲學(xué)思想異同點(diǎn)淺析
一種基于自適應(yīng)近鄰選擇的協(xié)同過(guò)濾推薦算法
淺談愛情中的兩性差異
沧州市| 蕲春县| 宜良县| 娄烦县| 安龙县| 鄂托克前旗| 西乌珠穆沁旗| 乌恰县| 瑞金市| 龙州县| 尼玛县| 兴海县| 喀喇沁旗| 石城县| 北流市| 玉溪市| 井研县| 江山市| 清流县| 宝坻区| 同仁县| 大足县| 新干县| 兰西县| 温泉县| 遵义县| 黄浦区| 从江县| 晋江市| 金阳县| 右玉县| 武宣县| 长白| 荆州市| 通道| 鸡西市| 射阳县| 武夷山市| 新宁县| 邹平县| 惠安县|