資料探勘 第二單元 資料探勘的技術(shù)與工具

1、叢集分析之探勘資料探勘第二單元 資料探勘的技術(shù)與工具 1本周綱要叢集分析法的基本概念叢集分析法的技術(shù) 階層式叢集分析法 分割式叢集分析法 其他叢集分析法2叢集分析法的基本概念叢集分析法的主要目的是將一群擁有相異性質(zhì)的資料 (個(gè)體)，區(qū)隔為數(shù)個(gè)同質(zhì)性較高的資料群體 (叢集)3何謂叢集分析法叢集分析法的特性4叢集分析法與分類法分類法分群方式，為擁有事先定義好的群組分群時(shí)再依每個(gè)資料最適合哪個(gè)群組，將資料分配至已經(jīng)事先定義好的群組中叢集分析法無(wú)任何事先定義好的群組群組的特性，需視欲將資料分為幾群或視資料的屬性而定。一種動(dòng)態(tài)的分群資料分析法5叢集分析法的進(jìn)行步驟樣式的描述 (包括特徵的選擇或萃取) 樣

2、式間的相似度計(jì)算分群資料的摘要 (視實(shí)際情況決定是否需要進(jìn)行此步驟)輸出的評(píng)估 (視實(shí)際情況決定是否需要進(jìn)行此步驟) 6叢集分析法的應(yīng)用領(lǐng)域叢集分析法在商業(yè)上的應(yīng)用顧客分群銀行業(yè)方面，可以利用叢集分析法中的離群值分析，來(lái)判別信用卡持卡人的消費(fèi)是否與其平常的消費(fèi)型態(tài)有所不同，藉以降低銀行與持卡人的風(fēng)險(xiǎn)與損失叢集分析法在醫(yī)學(xué)上的應(yīng)用判斷病癥的輔助工具叢集分析法在網(wǎng)路上的應(yīng)用網(wǎng)頁(yè)的內(nèi)容分析叢集分析法在生物領(lǐng)域上的應(yīng)用動(dòng)物或植物進(jìn)行分群7相似度的衡量a. 連續(xù)或區(qū)間數(shù)值的相似度衡量a.1. 標(biāo)準(zhǔn)化先計(jì)算變數(shù)的平均絕對(duì)差異值計(jì)算每個(gè)數(shù)值的 分?jǐn)?shù)可將區(qū)間數(shù)值標(biāo)準(zhǔn)化，再利用標(biāo)準(zhǔn)化後的值進(jìn)行相似度衡量，較不易

3、產(chǎn)生偏差的值。8相似度的衡量a.2. 相似度衡量方法a.2.1. 歐幾里德距離 a.2.2. 曼哈頓距離a.2.3. Minkowski距離9相似度的衡量a.2.4. 加權(quán)式距離衡量方式a.2.5. MND距離衡量法NN(a,b)為對(duì)b而言, 比a到b距離近的鄰居數(shù)目(包含b)10相似度的衡量a.2.6. 概念性叢集之相似度衡量11作業(yè): 利用以下的相似度衡量法計(jì)算甲與乙的距離1. 歐幾里德距離 2. 曼哈頓距離3. 加權(quán)式距離衡量方式(權(quán)重: 年齡0.1, 身高0.4, 體重0.4,成績(jī)0.1)12相似度的衡量b. 其他類型值之相似度衡量b.1. 名目變數(shù)的相似度計(jì)算範(fàn)例相似度=0.2513

4、相似度的衡量b.2. 二元變數(shù)值之相似度衡量方法沿用名目變數(shù)相似度計(jì)算方式範(fàn)例相似度=3/5=0.614相似度的衡量b.3. 等級(jí)變數(shù)之相似度衡量方法標(biāo)準(zhǔn)化為01之間的數(shù)值範(fàn)例之後再採(cǎi)用歐幾里德、曼哈頓或Minkowski其中一種來(lái)進(jìn)行距離的計(jì)算斯皮爾曼等級(jí)相關(guān)係數(shù)15叢集分析法的技術(shù)16叢集分析法技術(shù)的分類階層式叢集分析法主要透過(guò)分類樹狀圖的建立可再依其進(jìn)行的方式分為聚合式與分裂式分割式叢集分析法分割式叢集分析法為目前進(jìn)行叢集分析的主流方式其他叢集分析法的技術(shù)以密度為基礎(chǔ)的叢集分析法DBSCAN演算法以方格為基礎(chǔ)的叢集分析法STING演算法類神經(jīng)網(wǎng)路叢集分析法以機(jī)率為基礎(chǔ)的叢集分析法EM演算

5、法分析離群值的離群分析法17影響叢集分析法技術(shù)的因素聚合或分裂單一特性或多特性明確的叢集或模糊的叢集事先決定或隨機(jī)決定遞增或非遞增 18階層式叢集分析法19階層式叢集分析法聚合式叢集分析法由樹狀分類圖中的分枝一直進(jìn)行到根部的叢集分析法，亦可說(shuō)是一種由下到上的叢集分析法演算法步驟一：將n個(gè)資料自己分為一叢集，因此一開始將會(huì)有n個(gè)叢集步驟二：計(jì)算叢集之間的距離，並加以排序步驟三：選擇兩個(gè)最近的叢集，聚為一個(gè)新的叢集步驟四：將步驟三的新叢集與其他的叢集重新計(jì)算距離，更新叢集間的距離，新的叢集距離的代表值，依照不同的叢集方法 (單一鏈結(jié)、完全鏈結(jié))步驟五：重複步驟三、四 次步驟六：直到所有的叢集都聚在

6、同一叢集中，即結(jié)束20階層式叢集分析法單一鏈結(jié)法兩個(gè)資料間新的距離定義為兩個(gè)叢集之間的最小距離完全鏈結(jié)法兩個(gè)資料間新的距離定義為兩個(gè)叢集之間的最大距離21分割式叢集分析法k-means演算法將n個(gè)資料分至k個(gè)叢集中，最後達(dá)成一個(gè)最佳化，也就是每一群之間的資料是最相似的，而群與群之間的相似度則是最小的衡量相似度的基準(zhǔn)在於求出每一群資料的平均值 (也就是所謂的重心)演算法步驟一：隨機(jī)選定欲進(jìn)行叢集的資料中k個(gè)資料，最初以這k個(gè)資料為各叢集的起始重心步驟二：將剩下的每一個(gè)資料分配至最近的重心，聚為同一個(gè)叢集步驟三：以目前每一個(gè)叢集的資料為主，重新計(jì)算每一個(gè)叢集的平均值，找出新的重心步驟四：如果未符合

7、收斂的基準(zhǔn)，則至步驟二再執(zhí)行一次演算法，直至收斂為止; 或跳至步驟二執(zhí)行的次數(shù)已超過(guò)指定的閥值就停止。收斂的準(zhǔn)則有兩個(gè)(達(dá)到其中一個(gè)即可)再?zèng)]有任何的 (或極少) 值被分到新的叢集中群聚的平方誤差(距離平方誤差（square error）)總和，可稱為分群的誤差函數(shù)E（error function）或失真度。最佳化使 E 的值為最小。 22k-means演算法缺點(diǎn)資料必須能夠計(jì)算平均值，也就是必須為數(shù)值資料，但實(shí)際的情況下，資料可能很難為這種情況。使用者必須事先決定叢集的數(shù)目，但有時(shí)此數(shù)目並非最佳的叢集狀態(tài)。容易受到雜質(zhì)或離群值影響叢集的結(jié)果，因?yàn)闀?huì)影響平均值的計(jì)算 (重心的決定)。23作業(yè):

8、 以K-means方法找出下列資料的叢集分析結(jié)果6 instances, 2 attributes, 2 cluster24第五節(jié) 其他叢集分析法以密度為基礎(chǔ)的叢集方法優(yōu)點(diǎn)可找出有不確定形狀的叢集可掌握雜質(zhì)以密度為基礎(chǔ)的叢集分析法進(jìn)行演算時(shí)，只需對(duì)資料進(jìn)行一次的掃描25以密度為基礎(chǔ)的叢集方法DBSCAN必須明定兩個(gè)參數(shù)值來(lái)定義最小的密度。在以 為半徑內(nèi)的資料稱為 鄰居域在 鄰居域中，最少需有的資料數(shù)目稱為MinPts範(fàn)例在圖中 則26DBSCAN假設(shè)有一連串的點(diǎn) ，而 為從 密度可直接觸及的點(diǎn)如圖左邊的部分，因?yàn)辄c(diǎn) 可以直接觸及 ，則稱 為可依據(jù)密度而連結(jié)的點(diǎn)27DBSCAN演算法步驟一：任意

9、選擇一點(diǎn)步驟二：找出在 和MinPts下從 可以直接觸及的區(qū)域步驟三：如果 為核心點(diǎn)，則叢集形成步驟四：如果 為邊緣點(diǎn)，但沒有任何點(diǎn)從 可以直接觸及，則DBSCAN演算法會(huì)結(jié)束 的處理，繼續(xù)進(jìn)行其他點(diǎn)的處理步驟五：重複直到所有的點(diǎn)皆處理完畢28以方格為基礎(chǔ)的叢集方法STING利用階層式的方格結(jié)構(gòu)，儲(chǔ)存資料的數(shù)值性統(tǒng)計(jì)參數(shù)特性 (如：最大值、最小值、平均數(shù)等) 在方格內(nèi)屬性獨(dú)立的參數(shù)：n：一格內(nèi)資料的數(shù)目屬性相依的參數(shù) (假設(shè)資料為數(shù)值資料)m：方格內(nèi)所有資料值的平均值s：方格內(nèi)所有資料屬性值的標(biāo)準(zhǔn)差min：方格內(nèi)所有資料屬性值的最小值max：方格內(nèi)所有資料屬性值的最大值distribution

10、：方格內(nèi)所有資料屬性值的分布狀況。分布狀況不是數(shù)值資料，如：正常、平均等。如果分布情況未知的話，則會(huì)記錄為NONE。29類神經(jīng)網(wǎng)路叢集方法自我組織圖(SOM)的技術(shù)30以機(jī)率為基礎(chǔ)的叢集分析法解決混合的資料機(jī)率分布31以機(jī)率為基礎(chǔ)的叢集分析法EM演算法EM就是將期望最大化的意思先猜測(cè)5個(gè)參數(shù)值計(jì)算每個(gè)機(jī)率分布的機(jī)率利用其機(jī)率值分配資料到各叢集後，再估計(jì)參數(shù)值,直到最好的結(jié)果出現(xiàn)假設(shè) 為資料 在叢集A中的機(jī)率，則此時(shí)A的平均數(shù)及標(biāo)準(zhǔn)差可以下列公式計(jì)算之：收斂的準(zhǔn)則為32離群值分析低維度的資料利用視覺化的方法高維度的資料以統(tǒng)計(jì)為基礎(chǔ)的離群值偵測(cè)方法以距離為基礎(chǔ)的離群值偵測(cè)方法以索引式資料結(jié)構(gòu)為基礎(chǔ)

11、的演算法利用多維度索引的資料結(jié)構(gòu)，如R-tree或k-d tree來(lái)進(jìn)行離群值的偵測(cè)以細(xì)胞 (Cell) 概念為基礎(chǔ)的演算法把整個(gè)資料的集合切成大小相同的細(xì)胞，再對(duì)於每個(gè)細(xì)胞進(jìn)行偵測(cè)，決定在細(xì)胞內(nèi)的值是否為離群值33以細(xì)胞 (Cell) 概念為基礎(chǔ)的演算法之細(xì)胞構(gòu)造示意圖34以細(xì)胞 (Cell) 概念為基礎(chǔ)的演算法步驟一計(jì)算在細(xì)胞外之第一層細(xì)胞壁與細(xì)胞內(nèi)的資料數(shù)目，假如資料數(shù)目小於或等於 時(shí)，則將整個(gè)細(xì)胞視為離群值而假如資料的數(shù)目大於 的話，則進(jìn)行第二個(gè)步驟的離群值偵測(cè)。步驟二計(jì)算在第二層細(xì)胞壁內(nèi)，包括第一層細(xì)胞壁及細(xì)胞內(nèi)的資料，判斷準(zhǔn)則與第一步驟相同假如計(jì)算後的資料數(shù)目大於 時(shí)，此時(shí)資料內(nèi)仍可能存在離群值，則會(huì)對(duì)於每個(gè)資料進(jìn)行單獨(dú)的偵測(cè)偵測(cè)的方法採(cǎi)用鄰居域的方法假如對(duì)每個(gè)資料而言，在d-鄰居域中的鄰居資料數(shù)目不足的話，則此資料將會(huì)被視為離群值，如果數(shù)量足夠的話，就非離群值。35離群值分析以偏差概念為基礎(chǔ)的離群值偵測(cè)方法衡量資料的主要特性與在同一群資料中的特性有無(wú)出現(xiàn)偏差過(guò)大的情形，藉以找出資料中的離群值SET演