ROCK演算法探讨概要课件.ppt

上传人(卖家):三亚风情 文档编号:2494371 上传时间:2022-04-25 格式:PPT 页数:26 大小:690KB
下载 相关 举报
ROCK演算法探讨概要课件.ppt_第1页
第1页 / 共26页
ROCK演算法探讨概要课件.ppt_第2页
第2页 / 共26页
ROCK演算法探讨概要课件.ppt_第3页
第3页 / 共26页
ROCK演算法探讨概要课件.ppt_第4页
第4页 / 共26页
ROCK演算法探讨概要课件.ppt_第5页
第5页 / 共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.報告大綱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的概念,但未有較適合之相似度函式nsim(p,q)使用Jaccard係數為boolean方式,但細看兩項目間仍為boolean,不足以精細表達出距離nsim(可樂,衣服)=sim(可樂,百事)=0 n實際上,sim(可樂,衣服) sim(可樂,百事)

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(ROCK演算法探讨概要课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|