不確定數(shù)據(jù)聚類算法研究

摘要：UK均值算法需要計算每個對象之間的期望距離（EDS）和聚類中心， EDS計算的成本就成了UK均值計算的性能瓶頸。為了提高UK均值的計算效率，本文提出一種優(yōu)化的UK均值算法，通過一個高效的公式來估計期望距離，大大降低了UK均值的額外時間，并在實驗中得以證明。我們還說明這個優(yōu)化公式有效地將UK均值算法降低到了傳統(tǒng)的基于K均值的聚類算法。

關(guān)鍵詞：不確定數(shù)據(jù)； 聚類； 期望距離；UK均值算法

中圖分類號：TP301.6 文獻標(biāo)識碼：A

1引言不確定性數(shù)據(jù)是近年來在傳感器網(wǎng)絡(luò)、無線射頻識別、數(shù)據(jù)集成、Internet應(yīng)用等領(lǐng)域中涌現(xiàn)出來的一類新數(shù)據(jù)，其特點是每個數(shù)據(jù)對象不是單個數(shù)據(jù)點，而是按照概率在多個數(shù)據(jù)點上出現(xiàn)[1]。不確定數(shù)據(jù)的研究一般可以分為兩類：一類是存在不確定性研究，關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)元組存在與否具有一定的概率，這種概率性同時又會影響其他數(shù)據(jù)元組的存在，這種“概率數(shù)據(jù)庫模式”已經(jīng)被應(yīng)用于半結(jié)構(gòu)化數(shù)據(jù)和XML中。另一類是值不確定性研究，針對元組數(shù)目和模型己經(jīng)被確定的前提下，屬性值中存在的誤差所造成的不確定信息常通過概率密度函數(shù)PDF或其他統(tǒng)計量（如方差、協(xié)方差等）表示。在不確定數(shù)據(jù)挖掘研究領(lǐng)域多考慮基

于PDF建模的不確定性數(shù)據(jù)[2]。本文研究的是基于值的不確定性。

關(guān)于不確定數(shù)據(jù)聚類，Michael Chau等人[3]首先提出了一種基于kmeans算法的不確定聚類算法，即ukmeans算法。該算法主要的計算時間是EDS的估計，它包括大量樣本點的集成，當(dāng)數(shù)據(jù)集較大時，其計算代價是相當(dāng)高的。為了提高UK均值算法的效率，提出了一些避免很多期望距離ED計算的修剪技術(shù)。這項修剪技術(shù)利用包圍盒以及三角不等式建立ED的上界和下界[4-6]。使用這些范圍，一些候選對象的集群作業(yè)被淘汰，因此相應(yīng)的ED計算也可以避免。但這些技術(shù)并沒有減少每次ED的計算時間。此外，修剪效果不能保證，因為它取決于數(shù)據(jù)的分布情況[7-9]。在本文中，我們的目標(biāo)不是使用修剪技術(shù)來提高UK算法的性能，而是推導(dǎo)出一個簡單的公式用于ED的計算，目的是減少計算成本會，進一步提高不確定聚類算法的效率。思想來源于剛體運動的轉(zhuǎn)動慣量的簡化計算方法。

2相關(guān)知識

2.1平行軸定理

4.2實驗設(shè)計

我們分別用真實數(shù)據(jù)和模擬數(shù)據(jù)進行實驗。真實數(shù)據(jù)來自網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集。該數(shù)據(jù)集中每個連接記錄包含了42個固定的屬性和1個類標(biāo)識。屬性包括一個TCP連接的日志記錄，含持續(xù)時間、傳輸字節(jié)數(shù)等。標(biāo)識類型表明每條記錄對應(yīng)于一個正常的連接或者是 4 種類型的網(wǎng)絡(luò)攻擊之一，例如信息收集型攻擊、利用型攻擊等。試驗中選擇42個屬性中的28個數(shù)值型屬性。

許多數(shù)據(jù)集都是根據(jù)n和k的不同產(chǎn)生的。用這種方法產(chǎn)生的每個數(shù)據(jù)集當(dāng)做UK均值和CK均值的數(shù)據(jù)集。測量每種方法所消耗的CPU時間。兩種算法的/o時間相差無幾，并且在數(shù)值上都很小，可不予考慮。

4.3實驗結(jié)果和分析

4.3.1對象數(shù)量的影響

第一組的實驗數(shù)據(jù)具有不同數(shù)目的不確定對象n和相同數(shù)目的聚類k=20。 圖中曲線顯示了兩種算法所消耗的CPU時間。實驗結(jié)果如圖1。

結(jié)果表明，CK算法比UK算法快57-375倍。n值越大，速度越快。由于省略了ED的計算時間，所以CK均值很顯然會降低計算成本。實際上，CK均值的大部分計算時間花在預(yù)先計算質(zhì)心上，它包括用每個對象的樣本點來估計公式（6）中的積分。一旦質(zhì)心計算出來了，CK均值將需要很少的額外時間來聚類。同時發(fā)現(xiàn)，跟UK均值所消耗的時間相比，質(zhì)心的計算時間相對較少。當(dāng)n=50的時候，需花費 1.7%的時間。當(dāng)n增大的時候這個百分比下降，因為質(zhì)心的計算只有一次，然后在所有的迭代中重復(fù)使用。當(dāng)n=1000時，百分比下降到了0.24%。迭代次數(shù)增加n，每個對象的質(zhì)心計算成本就下降n。

4.3.2聚類數(shù)目的影響

我們固定對象數(shù)量n=1000，讓聚類數(shù)量k變化。實驗結(jié)果如圖2。CK均值比UK均值快19.9-796倍。每次質(zhì)心的計算大概都是0.45s。這是因為對象的數(shù)目是固定的，因此，其質(zhì)心計算的次數(shù)不變。總的趨勢是當(dāng)k增大的時候，所需的迭代的次數(shù)也增加，CK節(jié)省的時間也增加，因為質(zhì)心計算的每次迭代時間都降低。

4.3.3樣本數(shù)量的影響

研究的樣本數(shù)量的影響，其中保持n=1000，k=20，s從1000到5000不等，我們在這組實驗中采用的是二維數(shù)據(jù)。結(jié)果如圖3。

從圖中我們可以看到當(dāng)s增加的時候，UK和CK的花費時間都會增加，這是因為s越大，估計等式（3）中的積分就需要更多的時間。由于UK需要大量的ED計算，所以s越大時間就會越長。對于CK均值算法， s影響到的唯一的步驟就是等式（6）中質(zhì)心的計算。每個對象的樣本點越多，質(zhì)心計算的代價就越大。圖中質(zhì)心計算的曲線可以證明這一點。CK均值算法仍然是比UK均值算法性能好。速度是UK算法的306-527倍。

5結(jié)論

本文研究了m維歐幾里得空間中的不確定數(shù)據(jù)聚類問題。得出一個簡單的有效地預(yù)計期望距離的公式。這個公式被應(yīng)用到UK均值算法并且得到證實可以減少95%的計算時間，這相當(dāng)于至少提高速度20倍。在只知道m(xù)維空間中n個對象的概率信息的情況下做聚類的問題已經(jīng)成功的簡化為聚類n個點的問題。這n個點是n個對象的質(zhì)心或者是期望位置。今后，我們可以同樣使用期望距離作為ED的情況下將這些結(jié)果推廣到非歐式范式。

參考文獻

[1]汪金苗， 張龍波， 鄧齊志， 等. 不確定數(shù)據(jù)頻繁項集挖掘方法綜述[J].計算機工程與應(yīng)用，2011，47（20）：121-125.

[2]C.C.Aggarwal，P.S.Yu.Asurvey of uneertain data algorithms and applieations[R]，IBM Researeh Report RC24394，2007.

[3]MICHAEL C，REYNOLD C，BEN K，et al.Uncertain data mining：an example in clustering location data[C]//Pro-ceeding of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining （PAKDD 2006）.Berlin：Springer Verlag，2006：199-204.

[4]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報，2008，19（1）：48-61.

[5]X.J.Zhu.Semi-supervised learning literature survey [R].Teehnieal Report， Madison： DePartment of ComPuter Seienees， University of Wiseonsin， 2005：4-6.

[6]CHAU M，CHENG R，KAO B.Uncertain data mining：a new research direction[C]//Proceeding Workshop on the Sciences of the Artificial.Washington DC：IEEE Computer Society，2005：199-204.

[7]LEE S D，KAO B，CHENG R.Reducing uk-means toKmeans[C]//The 1st Workshop on Data Mining of Uncertain Data （DUNE），in conjunction with ICDM.Trenton，NJ：IEEE Press，2007：483-488

[8]P.Zou，Z.Zhou，G.L.Chen，etal.Approximate一baekbone guided fast ant algorithlns to QAP [J]. Journal of Software，2005，16（10）：1691-1698.

[9]C.C. Aggarwal. On unifying privacy and uncertain data models[C]. Proc. of the 24thIEEE Internationa lConfereneeon Data Engineering，2008.