二元數(shù)據(jù)子空間聚類算法的初始化研究
2009-01-01 00:00:00夏英魯寧豐江帆
計算機應用研究 2009年1期
（重慶郵電大學 中韓合作空間信息系統(tǒng)研究所， 重慶 400065）
摘 要：針對二元數(shù)據(jù)空間高維稀疏性的特點而提出的有限混合伯努利模型，能夠快速尋找映射簇的模型框架；EM算法是數(shù)學模型進行參數(shù)迭代的重要方法，其算法的優(yōu)劣很大程度上取決于其初始參數(shù)。對于運用EM算法來實現(xiàn)有限混合伯努利模型聚類算法已有許多研究， EM算法中參數(shù)的選取直接影響聚類算法的性能。引入 Binning法和改變數(shù)據(jù)之間相似度測量方式、中心點的選取方式來進行初始化，從而大大減少聚類結果對初始參數(shù)的依賴，實驗證明該算法是高效的、正確的。
關鍵詞：子空間聚類； 二元數(shù)據(jù)； 有限混合伯努利模型； EM算法
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)01004703
Research of initialization of subspace clustering algorithm in binary data
XIA Ying， LU Ning， FENG Jiangfan
(SIKOGIS Research Center， Chongqing University of Posts Telecommunications， Chongqing 400065，China)
Abstract:Aiming at the characteristic of highdimensionality and sparseness in binary data set， proposes the finite mixtures of Bernoulli distributions model for finding projected clusters fast. EM algorithm is the important method of iterative parameters， and the degree of good or bad with EM algorithm lies on initial parameters. As far as the finite mixtures of Bernoulli distributions model， there have been lots of researches about it. However， in EM algorithm， the initial parameters affect the clustering performance directly. Therefore， this paper introduced Binning method and computed parameters through changing the comparability measurement between dates and selection style about corepoint，in order to reduce the dependence of the clustering for initial parameters. Experiment demonstrates the algorithm is efficient and accurate.
Key words：subspace clustering; binary data; the finite mixtures of Bernoulli distributions model; EM algorithm
子空間聚類是指在原始數(shù)據(jù)空間的子空間中尋找數(shù)據(jù)簇，使每個簇與相應的屬性子集關聯(lián)，而簇內數(shù)據(jù)點在這樣的屬性集合下高度相似。該概念在1998年由Agrawal等人[1，2]提出后，引起許多學者關注，并不斷研究出新的成果。經(jīng)典的算法有CLIQUE[1]算法、改進了的PROCLUS[3]/ORCLUS[4]等算法，這些算法雖然能有效地發(fā)現(xiàn)映射簇，但也存在許多不足。例如CLIQUE算法發(fā)現(xiàn)簇的形狀總是超矩形的結合，而PROCLUS/ORCLUS算法的簇卻總是外凸的；從CLIQUE到PROCLUS/ORCLUS都采用硬劃分的方法把數(shù)據(jù)強制屬于某一類；CLIQUE和PROCLUS/ORCLUS都需要輸入?yún)?shù)，且算法都對初始值非常敏感；CLUQYE和PROCLUS/ORCLUS隨著維數(shù)的增大，算法的運行時間均呈指數(shù)增長?；谀Ｐ偷木垲惙椒╗5]利用已知數(shù)學模型，通過逐漸逼近的方法使得給定數(shù)據(jù)集與數(shù)據(jù)模型之間達成最佳擬合。這種聚類算法屬于軟劃分的方法，對簇的形狀要求低，也可解決多密度的問題，雖然依賴初始參數(shù)，但通過改進可以降低這種依賴程度。
二元數(shù)據(jù)只有兩種狀態(tài)且大多是高維的，例如在進行購物籃分析時，數(shù)據(jù)屬性代表超市商品，數(shù)據(jù)點代表購物事務。如果某商品在某事務中被購買，則在該商品對應的屬性上取值為1，否則取值為0。超市商品數(shù)一般都有數(shù)千種，意味著每個數(shù)據(jù)點都有數(shù)千維的數(shù)據(jù)屬性，但是每項事務所涉及的商品卻很少，也許在數(shù)千維的屬性中只有幾個或幾十個取值為1，其他全部為0；而且隨著超市商品數(shù)增多，每項事務所涉及的商品卻不會增多。由此可見，二元數(shù)據(jù)的特點是數(shù)據(jù)維度越大，數(shù)據(jù)的稀疏性越高。針對二元數(shù)據(jù)這種特點，A.Patrikainen[6]于2002年首次提出有限混合伯努利模型并且應用EM算法進行參數(shù)迭代的子空間聚類算法；此后不斷有學者完善該模型，仍有對EM算法初始參數(shù)估計不足，致使迭代次數(shù)增多和聚類效果不理想的問題。本文針對EM算法的收斂程度取決于初始參數(shù)這一問題，在保持EM算法本身迭代的前提下，通過引入Binning法[7~9]、改變數(shù)據(jù)之間相似度測量方式和中心點的選取方式來細化EM初始值，從而改善EM的收斂，獲得更好的聚類效果。
1 有限混合伯努利模型聚類算法
有限混合伯努利模型聚類算法的思想是：屬性之間是相互獨立的，每個屬性均可看做一個獨立事件Ai，每個對象是獨立事件實驗樣本。數(shù)據(jù)對象在某屬性上是否取值為1，取決于事件Ai發(fā)生的概率pi，數(shù)據(jù)對象在所有屬性上取值的分布律可以用相應公式來表示。如果各對象在具體屬性上取值的概率不同，則可以把概率相同的看做一類，形成數(shù)據(jù)集合中的聚類簇，同一簇的數(shù)據(jù)看做是由同一分布產生的數(shù)據(jù)點[10]。
1.1 有限混合伯努利模型
考慮K重D元混合伯努利分布，該分布的參數(shù)表示為P=(p1，p2，…，pk)。其中：
由式(4)可以看出，第k個混合分量的參數(shù)pk(t+1)是全部數(shù)據(jù)點的加權平均數(shù)，而第n個數(shù)據(jù)點的權重則是第k個混合分量產生它的概率，然后通過迭代把π和p計算出來。
2 改進的初始化算法
該算法是以子空間聚類模型為基礎，采用迭代的EM算法，從初始劃分、參數(shù)估計開始，對劃分方案進行迭代優(yōu)化，最終形成聚類結果。
2.1 普通的初始化算法
在有限混合伯努利分布模型的EM算法中，需要對模型參數(shù)進行預估以及對屬性進行初始化。常用的方法有AGENES、Kmeans、隨機中心等。AGENES聚類，即首先將n個樣本分成n類，使得每一類正好含有一個樣本；然后將樣本凝集成n-1類、n-2類，直到所有的樣本都凝集成所需要的k類為止。Kmeans聚類屬于聚類分析方法中應用最廣泛的劃分算法，目標就是要找到k個均值向量，k就是聚類數(shù)目。基于給定的聚類目標函數(shù)，算法采用迭代更新的方法。每一次迭代過程都是向目標函數(shù)值減小的方向進行，最終的聚類結果使目標函數(shù)值取得極小值，以達到較優(yōu)的聚類效果。因為二元數(shù)據(jù)取值只能是0或1，所以平均數(shù)的取值也只是在[0，1]中，導致平均數(shù)在迭代過程中變化不大，這影響了聚類的效果。隨機初始化方法即在數(shù)據(jù)集中隨機抽取n個點作為聚類中心，n為聚類數(shù)。然后，對數(shù)據(jù)集中的每個數(shù)據(jù)點(除了這n個點以外)計算其與這n個點的每個點的歐氏距離；根據(jù)距離最短原則，把每個點放入n類中的某一類。于是，對于每一類的數(shù)據(jù)，可以計算出其權重、期望、方差。但是由于二元數(shù)據(jù)取值有限，在用歐式距離進行測量從而判斷兩個數(shù)據(jù)點是否屬于同一個簇可能會失效，因為大量的計算值會重復。基于以上原因，引入Binning法并改進其度量方式作為ＥＭ算法的初始化方法。
2.2 改進的Binning初始化算法
Binning法可以想像成把數(shù)據(jù)空間在各維上劃分為一個個的箱子，再把數(shù)據(jù)點投射到對應的箱子里去。這里，初始化EM的任務就是找到最優(yōu)聚類中心，從而對參數(shù)以及屬性集進行估值，想法是最好的聚類中心可能就是概率密度數(shù)最稠密的部分。于是，通過Binning法來尋找概率密度函數(shù)最稠密的部分。Bin寬是指在Binning法中把整個數(shù)據(jù)空間分成若干個Bin并指定每一個Bin的寬度；然后把每個數(shù)據(jù)的每一維都投影到Bin中。因為Bin寬直接影響到數(shù)據(jù)的投影數(shù)量，所以選擇一個最優(yōu)的Bin寬就成為關鍵的問題。不過二元數(shù)據(jù)取值全部為{0，1}，因此最優(yōu)Bin寬無須考慮，這也是Binning法可以引入該算法的一個重要原因。另外，由于高維二元數(shù)據(jù)的特殊性，引入相異度和相似度兩個概念對數(shù)據(jù)點進行度量以及在選取中心點時引入的相異度均值和相異度標準差的概念，對原有的Binning法進行改進。
a)相似值(simi)標準定義如下：
的整個數(shù)據(jù)空間分成若干個Bin，然后把每個數(shù)據(jù)的每一維放到對應的Bin中，再計算每一個Bin中所含的數(shù)據(jù)點個數(shù)。含的點數(shù)多的則為概率密度相對大的區(qū)域，也就是聚類中心最可能存在的區(qū)域。在得到了每一個Bin中的數(shù)據(jù)點個數(shù)后，可以作進一步的優(yōu)化：
a)給每一個數(shù)據(jù)點一個向量標記，表示其各維所在的Bin位置。
b)計算出Bin中數(shù)據(jù)點的均值，把小于均值的Bin去除考慮范圍。
c)除去不滿足條件的Bin后，再對所有的數(shù)據(jù)點進行篩選。
d)在篩選后的數(shù)據(jù)集中篩選中心點。
e)按照相似度重新排列數(shù)據(jù)點，相似度高的為一類。
2.4 算法偽代碼
有限混合伯努利模型聚類算法
輸入：num_clust//輸入欲尋找簇的個數(shù)
輸出： clusters //簇中心
dim: 數(shù)據(jù)維數(shù)；num_data: 數(shù)據(jù);sele_core: 由步驟d)篩選出的點的個數(shù)；
for i=1tonum_data do
for j=1 to dim do
把每一個數(shù)據(jù)點的每一維都投影到相應的Bin向量的屬性中，并分別計算出映射到Bin向量中的數(shù)據(jù)個數(shù)之和
end for
end for
計算bin中數(shù)據(jù)點的均值。
for j=1to dim do
在bin向量中把小于均值的屬性去除
end for
for i=1tonum_data do
for j= 1to dim do
根據(jù)Bin向量中屬性的個數(shù)，從所有數(shù)據(jù)點中選出大于Bin向量中屬性個數(shù)的點，數(shù)目為sele_core
end for
end for
ifnum_clust > sele_core
算法結束，重新輸入簇的個數(shù)
end if
ifnum_clust ==sele_core
把步驟d)選出的點作為中心點
end if
if num_clust < sele_core
從已選出的聚類中心中進行第二次篩選，篩選的原則是彼此相異度最大的為簇中心
end if
fori = 1tonum_data do
for k = 1to num_clust do
根據(jù)相似度標準和已知的簇中心重新計算，給相同類的點以相同的類標
end for
end for
3 算法分析與測試
實驗使用的環(huán)境為Genuine Intel(R) 2140@1.60 GHz 的CPU，內存為512 MB，操作系統(tǒng)為Windows XP Professional，算法的編寫使用Visual C++ 6.0。
為了驗證本文改進的Binning算法初始化有限混合伯努利模型聚類算法的精確性和可操作性，本文采用三個數(shù)據(jù)集進行了實驗。在同一數(shù)據(jù)集上運行Kmeans算法和AGENES算法與本文算法進行比較。
a)第一個數(shù)據(jù)集是由數(shù)據(jù)生成器生成的3 000個模擬數(shù)據(jù)，但每1 000個數(shù)據(jù)點的維數(shù)各不相同，有2%的噪點分布。表1與圖1就是對用改進的Binning初始化算法、Kmeans與AGENES算法運行數(shù)據(jù)集時所耗費的時間以及數(shù)據(jù)點出錯數(shù)的比較說明。實驗結果表明，在數(shù)據(jù)個數(shù)不變、維數(shù)增大的情況下，改進的Binning法進行初始化的精確度要高于Kmeans，與AGENES基本持平，且改進的Binning初始化算法處理速度是最快的。
b)第二個數(shù)據(jù)集也是模擬數(shù)據(jù)，維數(shù)全部是120維且有2%的噪點分布。表2與圖2同樣是對這三個算法運行第二個數(shù)據(jù)集時所耗費的時間以及數(shù)據(jù)點出錯數(shù)的比較說明。該實驗表明，在維數(shù)不變、數(shù)據(jù)量增大的情況下，改進的Binning法進行初始化的精確度要高于Kmeans，與AGENES基本持平，且改進的Binning初始化算法處理速度是最快的。
c)第三個數(shù)據(jù)集來源于http://wwwusers.cs.umn.edu/~han/data/上的 la1的文本數(shù)據(jù)庫，其文本數(shù)量為3 204，屬性為31 472。原文檔集合被劃分為financial、foreign、national、metro、sports和entertainment六類。運用本文算法在同一PC機上對該數(shù)據(jù)進行聚類操作，運行時間為62 ms，運行Kmeans與AGENES算法的時間分別是165 ms和31 285 ms，精確度依次為0.981 9、0.911 4、0.981 0。
4 結束語
本文針對EM算法在收斂上的缺陷，在保持算法迭代的簡單性前提下，通過改變EM的初始化方法來優(yōu)化EM算法，從而使有限混合伯努利模型聚類算法得到更好的聚類效果。一方面引入Binning法來初始化EM；另一方面針對二元數(shù)據(jù)的數(shù)據(jù)特點，改變了數(shù)據(jù)之間相似度測量方式和中心點的選取方式，并比較了傳統(tǒng)的初始化方法。實驗表明，該方法有著較好的實際聚類效果和較快的處理速度。下一步的工作是促進有限混合伯努利模型聚類算法，如何減少迭代次數(shù)并使參數(shù)自適應。
參考文獻：
［1］CHENG C， FU A W， ZHANG Yi. Entropybased subspace clustering for mining numerical data[C]//Proc of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press， 1999:8493.
[2]AGRAWAL R， GEHRKE J， GUNOPULOS D，et al. Automatic subspace clustering of high dimensional data for data mining applications[J]. ACM SIGMOD Record， 1998，27(2):94105.
[3]AGGARWAL C C， WOLF J L， YLIP S，et al. Fast algorithms for projected clustering[J]. ACM SIGMOD. 1999，28(2):6172.
[4]AGGARWAL C C， YU P S. Finding generalized projected clusters in high dimensional space[J]. ACM SIGMOD. 2000，29(2):7081.
[5]FRALEY C. Algorithms for modelbased Gaussian hierarchical clustering[J]. SIAM Journal on Scientific Computing， 1999，20(1):270281.
[6]PATRIKAINEN A. Projected clustering of highdimensional binary data[D]. Helsinki: Helsinki University of Technology， 2002.
[7]岳佳，王士同.高斯混合模型聚類中EM算法及初始化的研究[J]. 微計算機信息，2006， 11(3):244246.
[8]BIERNACKI C. Initializing EM using the properties of its trajectories in Gaussian mixtures[J]. Statistics and Computing， 2004，14(3):267279.
[9]SCOTT D W. On optimal and databased histograms[J]. Biometrika，1979，66(3):605610.
[10]和亞麗. 基于高維空間的聚類技術研究[D]. 太原：中北大學， 2005.
