不確定數據聚類算法研究

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

關鍵詞：不確定數據； 聚類； 期望距離；UK均值算法

中圖分類號：TP301.6 文獻標識碼：A

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

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

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

2相關知識

2.1平行軸定理

4.2實驗設計

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

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

4.3實驗結果和分析

4.3.1對象數量的影響

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

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

4.3.2聚類數目的影響

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

4.3.3樣本數量的影響

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

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

5結論

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

參考文獻

[1]汪金苗， 張龍波， 鄧齊志， 等. 不確定數據頻繁項集挖掘方法綜述[J].計算機工程與應用，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].軟件學報，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.