《ROCK演算法探讨概要课件.ppt》由会员分享，可在线阅读，更多相关《ROCK演算法探讨概要课件.ppt（26页珍藏版）》请在三一办公上搜索。
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.,報告大綱,動機目的傳統分群算法缺點ROCK預先知識ROCK演算法實驗結論心得,動機,傳統演算法在分類屬性距離的不適用,目的,提出資料點間以連結為相似度之概念提出依連結基礎及具
2、強健性之演算法,傳統分群演算法缺點,分割式分群演算法階層式分群演算法,分割式分群演算法,使用合適的函式將資料點分成k個群集 其中 為群集Ci的中心點，而 為 與 的幾何距離 最小化 E區域最佳化,分割式分群演算法(續),適用數字屬性資料不適用類別屬性資料行銷資料庫屬性多，每筆交易項目少，造成同群集中，交易相同項目少,階層式分群演算法,每個資料點當成一個群集，將相似者兩兩合併，至k個群集適用類別屬性資料,階層式分群演算法(續),U=1,2,3,4,5,6A=1,2,3,5= (1,1,1,0,1,0)B=2,3,4,5= (0,1,1,1,1,0)C=1,4 = (1,0,0,1,0,0)D=6
3、 = (0,0,0,0,0,1)AB幾何距離最小( ) -合併CD次小( ) -合併，但CD並無相同項目不適用幾何距離,階層式分群演算法(續),改用但Jaccard係數僅測兩點之相似度，無法反映鄰居之性質不同群集1,2,3、1,2,7之 JC=0.5；而同群集1,2,3、3,4,5之 JC=0.2,ROCK預先知識,鄰居(neighbors)連結(links)標準函式(criterion function)優度函式(goodness function),鄰居,相似度函式 其中sim(pi,pj)為pi、pj 之相似度， ，值愈大表愈相似，為使用者自定之鄰居門檻值sim(pi,pj)為公制(Lp
4、)或非公制(領域專家提供),連結,link(pi,pj)為二資料點pi、pj 之相同鄰居數，值愈大表pi、pj 同一群集之機率愈大Ex. =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),標準函式,最大化link(pq,pr)，最小化link(pq,ps)故標準函式如： (X)上述函式無法防止所有資料點指定成一個單一群集,標準函式(續),所以標準函式應如下： (O) 其中ni為群集Ci中總資料點數 為Ci中預期總鄰居數Guha et al.,1997 為Ci中預期總連結數Guha et al.,1997,優度函式,(X)其
5、中linkCi,Cj為群集Ci 與Cj交叉連結數 做為合併兩群集Ci、Cj之參考依據但如果包含離群值，則可能造成所有群集合併於同一群集,優度函式(續),其中 為二群集中預期交叉連結個數Guha et al.,1997,ROCK演算法概觀,由資料庫中隨機載入樣本將link的方法套用於資料點中分群完成之樣本用於指派資料庫中其餘資料點於適當已知群集,ROCK演算法,輸入參數：包含n個資料點之資料集S，及預期群集數k起始時，每一資料點為一群集計算各點之連結數為每一個群集i，建立一個區域累堆qi，包含每一個與群集i之連結數不為零之群集jqi中之各群集j依g(i,j)值由大至小排序,ROCK演算法(續),
6、建立一全域累堆(global heap)Q，包含每一qi之優度函式最大值之群集j每一回合，合併Q中最佳群集j與qj中之最佳群集每當合併即重新運算各區域累堆及全域累堆，包括新形成之群集當群集數不小於k時，持續合併，此外當所有qi=0時亦停止合併,ROCK演算法(續),ROCK時間及空間複雜度,時間 O(n2+nmmma+n2logn)mm為最大鄰居數ma為平均鄰居數n為資料點數空間 O(minn2, nmmma),實驗設計,ROCK傳統演算法類別資料 布林值(0/1) Ex. U=1,2,3,4,5,6, A=1,2,3,5 = (1,1,1,0,1,0)使用幾何距離資料集,實驗-磨菇毒性分類,ROCKk=20=0.8傳統演算法 k=20,結論,提出資料點間以連結為類別屬性資料相似度測量之概念依連結基礎而非幾何距離強健性之階層式分群演算法實驗結果相當不錯,心得,ROCK的提出link的概念，但未有較適合之相似度函式sim(p,q)使用Jaccard係數為boolean方式，但細看兩項目間仍為boolean，不足以精細表達出距離sim(可樂,衣服)=sim(可樂,百事)=0 實際上，sim(可樂,衣服) sim(可樂,百事),
