ROCK演算法探讨

1、ROCK演算法探討指導教授：許中川 博士研究生：林勇助 Reference: Guha, S., R. Rastogi and K. Shim, 1999, “Rock: a robust clustering algorithm for categorical attributes”, In Proc. of the 15th International Conference on Data Engineering.報告大綱n動機n目的n傳統分群算法缺點nROCK預先知識nROCK演算法n實驗n結論n心得動機n傳統演算法在分類屬性距離的不適用目的n提出資料點間以連結為相似度之概念n提出依連結

2、基礎及具強健性之演算法傳統分群演算法缺點n分割式分群演算法n階層式分群演算法分割式分群演算法n使用合適的函式將資料點分成k個群集 其中 為群集Ci的中心點，而 為 與 的幾何距離 n最小化 En區域最佳化kiCxiimxdE1),(im),(imxdxim分割式分群演算法(續)n適用數字屬性資料n不適用類別屬性資料n行銷資料庫屬性多，每筆交易項目少，造成同群集中，交易相同項目少階層式分群演算法n每個資料點當成一個群集，將相似者兩兩合併，至k個群集n適用類別屬性資料階層式分群演算法(續)nU=1,2,3,4,5,6nA=1,2,3,5 = (1,1,1,0,1,0)nB=2,3,4,5 = (0

3、,1,1,1,1,0)nC=1,4 = (1,0,0,1,0,0)nD=6 = (0,0,0,0,0,1)nAB幾何距離最小( ) -合併nCD次小( ) -合併，但CD並無相同項目n不適用幾何距離23階層式分群演算法(續)n改用n但Jaccard係數僅測兩點之相似度，無法反映鄰居之性質n不同群集1,2,3、1,2,7之 JC=0.5；而同群集1,2,3、3,4,5之 JC=0.2212121),(_TTTTTTtCoefficienJaccardROCK預先知識n鄰居(neighbors)n連結(links)n標準函式(criterion function)n優度函式(goodness fu

4、nction)鄰居n相似度函式 其中sim(pi,pj)為pi、pj 之相似度， ，值愈大表愈相似，為使用者自定之鄰居門檻值nsim(pi,pj)為公制(Lp)或非公制(領域專家提供),(jippsim1),(0jippsim連結nlink(pi,pj)為二資料點pi、pj 之相同鄰居數，值愈大表pi、pj 同一群集之機率愈大nEx. =0.5與 則link(1,2,6,1,2,7)=5 (因為1,2,3,1,2,4,1,2,5,1,6,7,2,6,7)212121),(TTTTTTsim標準函式n最大化link(pq,pr)，最小化link(pq,ps)n故標準函式如： (X)n上述函式無法

5、防止所有資料點指定成一個單一群集 kiCpprqlirqpplinkE1,),(標準函式(續)n所以標準函式應如下： (O) 其中ni為群集Ci中總資料點數 為Ci中預期總鄰居數Guha et al.,1997 為Ci中預期總連結數Guha et al.,1997kiCppfirqilirqnpplinknE1,)(21),(*)(21fin)(fin優度函式n (X)其中linkCi,Cj為群集Ci 與Cj交叉連結數 n做為合併兩群集Ci、Cj之參考依據n但如果包含離群值，則可能造成所有群集合併於同一群集jriqCpCprqpplink,),(優度函式(續) 其中 為二群集中預期交叉連結個數

6、Guha et al.,1997)(21)(21)(21)(,),(fjfifjijijinnnnCClinkCCg)(21)(21)(21)(fjfifjinnnnROCK演算法概觀n由資料庫中隨機載入樣本n將link的方法套用於資料點中n分群完成之樣本用於指派資料庫中其餘資料點於適當已知群集ROCK演算法n輸入參數：包含n個資料點之資料集S，及預期群集數kn起始時，每一資料點為一群集n計算各點之連結數n為每一個群集i，建立一個區域累堆qi，包含每一個與群集i之連結數不為零之群集jnqi中之各群集j依g(i,j)值由大至小排序ROCK演算法(續)n建立一全域累堆(global heap)Q，

7、包含每一qi之優度函式最大值之群集jn每一回合，合併Q中最佳群集j與qj中之最佳群集n每當合併即重新運算各區域累堆及全域累堆，包括新形成之群集n當群集數不小於k時，持續合併，此外當所有qi=0時亦停止合併ROCK演算法(續) ROCK時間及空間複雜度n時間 O(n2+nmmma+n2logn)nmm為最大鄰居數nma為平均鄰居數nn為資料點數n空間 O(minn2, nmmma)實驗設計nROCKn傳統演算法n類別資料 布林值(0/1) nEx. U=1,2,3,4,5,6, A=1,2,3,5 = (1,1,1,0,1,0)n使用幾何距離n資料集11)(f實驗-磨菇毒性分類nROCKnk=20n=0.8n傳統演算法 nk=20結論n提出資料點間以連結為類別屬性資料相似度測量之概念n依連結基礎而非幾何距離n強健性之階層式分群演算法n實驗結果相當不錯心得nROCK的提出link的概念，但未有較適合