按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,*,叢集分析之探勘,資料探勘第二單元,資料探勘的技術與工具,本周綱要,叢集分析法的基本概念,叢集分析法的技術,階層式叢集分析法,分割式叢集分析法,其他叢集分析法,叢集分析法的,基本,概念,叢集分析法的主要目的是將一群擁有相異性質的資料,(,個體,),，區隔為數個同質性較高的資料群體,(,叢集,),何謂叢集分析法,叢集分析法的特性,叢集分析法與分類法,分類法,分群方式，為擁有事先定義好的群組,分群時再依每個資料最適合哪個群組，將資料分配至已經事先定義好的群組中,叢集分析法,無任何事先定義好的群組群組的特性，需視欲將資料分為幾群或視資料的屬性而定。,一種動態的分群資料分析法,叢集分析法的進行步驟,樣式的描述,(,包括特徵的選擇或萃取,),樣式間的相似度計算,分群,資料的摘要,(,視實際情況決定是否需要進行此步驟,),輸出的評估,(,視實際情況決定是否需要進行此步驟,),叢集分析法的應用領域,叢集分析法在商業上的應用,顧客分群,銀行業方面，可以利用叢集分析法中的離群值分析，來判別信用卡持卡人的消費是否與其平常的消費型態有所不同，藉以降低銀行與持卡人的風險與損失,叢集分析法在醫學上的應用,判斷病症的輔助工具,叢集分析法在網路上的應用,網頁的內容分析,叢集分析法在生物領域上的應用,動物或植物進行分群,相似度的衡量,a.,連續或區間數值的相似度衡量,a.1.,標準化,先計算變數的平均絕對差異值,計算每個數值的 分數,可將區間數值標準化，再利用標準化後的值進行相似度衡量，較不易產生偏差的值。,相似度的衡量,a.2.,相似度衡量方法,a.2.1.,歐幾里德距離,a.2.2.,曼哈頓距離,a.2.3.,Minkowski,距離,相似度的衡量,a.2.4.,加權式距離衡量方式,a.2.5.MND,距離衡量法,NN(a,b,),為對,b,而言,比,a,到,b,距離近的鄰居數目,(,包含,b),相似度的衡量,a.2.6.,概念性,叢集之相似度衡量,作業,:,利用以下的相似度衡量法計算甲與乙的距離,1.,歐幾里德距離,2.,曼哈頓距離,3.,加權式距離衡量方式,(,權重,:,年齡,0.1,身高,0.4,體重,0.4,成績,0.1),年齡,身高,體重,成績,甲,18,178,50,90,乙,20,160,60,60,相似度的衡量,b.,其他類型值之相似度衡量,b.1.,名目變數的相似度計算,範例,相似度,=0.25,相似度的衡量,b.2.,二元變數值之相似度衡量方法,沿用名目變數相似度計算方式,範例,相似度,=3/5=0.6,相似度的衡量,b.3.,等級變數之相似度衡量方法,標準化為,0,1,之間的數值,範例,之後再採用歐幾里德、曼哈頓或,Minkowski,其中一種來進行距離的計算,斯皮爾曼等級相關係數,叢集分析法的技術,叢集分析法技術的分類,階層式叢集分析法,主要透過分類樹狀圖的建立,可再依其進行的方式分為,聚合式與分裂式,分割式叢集分析法,分割式叢集分析法為目前進行叢集分析的主流方式,其他叢集分析法的技術,以,密度,為基礎的叢集分析法,DBSCAN,演算法,以,方格,為基礎的叢集分析法,STING,演算法,類神經網路,叢集分析法,以,機率,為基礎的叢集分析法,EM,演算法,分析離群值,的離群分析法,影響叢集分析法技術的因素,聚合或分裂,單一特性或多特性,明確的叢集或模糊的叢集,事先決定或隨機決定,遞增或非遞增,階層式叢集分析法,階層式叢集分析法,聚合式叢集分析法,由樹狀分類圖中的分枝一直進行到根部的叢集分析法，亦可說是一種由下到上的叢集分析法,演算法,步驟一：將,n,個資料自己分為一叢集，因此一開始將會有,n,個叢集,步驟二：計算叢集之間的距離，並加以排序,步驟三：選擇兩個最近的叢集，聚為一個新的叢集,步驟四：將步驟三的新叢集與其他的叢集重新計算距離，更新叢集間的距離，新的叢集距離的代表值，依照不同的叢集方法,(,單一鏈結、完全鏈結,),步驟五：重複步驟三、四 次,步驟六：直到所有的叢集都聚在同一叢集中，即結束,階層式叢集分析法,單一鏈結法,兩個資料間新的距離定義為兩個叢集之間的最小距離,完全鏈結法,兩個資料間新的距離定義為兩個叢集之間的最大距離,分割式叢集分析法,k-means,演算法,將,n,個資料分至,k,個叢集中，最後達成一個最佳化，也就是每一群之間的資料是最相似的，而群與群之間的相似度則是最小的,衡量相似度的基準在於求出每一群資料的平均值,(,也就是所謂的重心,),演算法,步驟一：隨機選定欲進行叢集的資料中,k,個資料，最初以這,k,個資料為各叢集的起始重心,步驟二：將剩下的每一個資料分配至最近的重心，聚為同一個叢集,步驟三：以目前每一個叢集的資料為主，重新計算每一個叢集的平均值，找出新的重心,步驟四：如果未符合收斂的基準，則至步驟二再執行一次演算法，直至收斂為止,;,或跳至步驟二執行的次數已超過指定的閥值就停止。,收斂的準則有兩個,(,達到其中一個即可,),再沒有任何的,(,或極少,),值被分到新的叢集中,群聚的平方誤差,(,距離平方誤差（,square error,）,),總和，可稱為分群的誤差函數,E,（,error function,）或失真度。最佳化,使,E,的值為最小。,k-means,演算法,缺點,資料必須能夠計算平均值，也就是必須為數值資料，但實際的情況下，資料可能很難為這種情況。,使用者必須事先決定叢集的數目，但有時此數目並非最佳的叢集狀態。,容易受到雜質或離群值影響叢集的結果，因為會影響平均值的計算,(,重心的決定,),。,作業,:,以,K-means,方法找出下列資料的叢集分析結果,6 instances,2 attributes,2 cluster,第五節 其他叢集分析法,以密度為基礎的叢集方法,優點,可找出有不確定形狀的叢集,可掌握雜質,以密度為基礎的叢集分析法進行演算時，只需對資料進行一次的掃描,以密度為基礎的叢集方法,DBSCAN,必須明定兩個參數值來定義最小的密度。,在以 為半徑內的資料稱為 鄰居域,在 鄰居域中，最少需有的資料數目稱為,MinPts,範例,在圖中,則,DBSCAN,假設有一連串的點 ，而 為從 密度可直接觸及的點,如圖左邊的部分，因為點 可以直接觸及 ，則稱 為可依據密度而連結的點,DBSCAN,演算法,步驟一：任意選擇一點,步驟二：找出在 和,MinPts,下從 可以直接觸及的區域,步驟三：如果 為核心點，則叢集形成,步驟四：如果 為邊緣點，但沒有任何點從 可以直接觸及，則,DBSCAN,演算法會結束 的處理，繼續進行其他點的處理,步驟五：重複直到所有的點皆處理完畢,以方格為基礎的叢集方法,STING,利用階層式的方格結構，儲存資料的數值性統計參數特性,(,如：最大值、最小值、平均數,等,),在方格內,屬性獨立的參數：,n,：一格內資料的數目,屬性相依的參數,(,假設資料為數值資料,),m,：方格內所有資料值的平均值,s,：方格內所有資料屬性值的標準差,min,：方格內所有資料屬性值的最小值,max,：方格內所有資料屬性值的最大值,distribution,：方格內所有資料屬性值的分布狀況。分布狀況不是數值資料，如：正常、平均,等。如果分布情況未知的話，則會記錄為,NONE,。,類神經網路叢集方法,自我組織圖,(SOM),的技術,以機率為基礎的叢集分析法,解決混合的資料機率分布,以機率為基礎的叢集分析法,EM,演算法,EM,就是將期望最大化的意思,先猜測,5,個參數值,計算每個機率分布的機率,利用其機率值分配資料到各叢集後，再估計參數值,直到最好的結果出現,假設 為資料 在叢集,A,中的機率，則此時,A,的平均數及標準差可以下列公式計算之：,收斂的準則為,離群值分析,低維度的資料,利用視覺化的方法,高維度的資料,以,統計,為基礎的離群值偵測方法,以,距離,為基礎的離群值偵測方法,以索引式資料結構為基礎的演算法,利用多維度索引的資料結構，如,R-tree,或,k-d,tree,來進行離群值的偵測,以細胞,(Cell),概念為基礎的演算法,把整個資料的集合切成大小相同的細胞，再對於每個細胞進行偵測，決定在細胞內的值是否為離群值,以細胞,(Cell),概念為基礎的演算法之細胞構造示意圖,以細胞,(Cell),概念為基礎的演算法,步驟一,計算在細胞外之第一層細胞壁與細胞內的資料數目，假如資料數目小於或等於 時，則將整個細胞視為離群值,而假如資料的數目大於 的話，則進行第二個步驟的離群值偵測。,步驟二,計算在第二層細胞壁內，包括第一層細胞壁及細胞內的資料，判斷準則與第一步驟相同,假如計算後的資料數目大於 時，此時資料內仍可能存在離群值，則會對於每個資料進行單獨的偵測,偵測的方法採用鄰居域的方法,假如對每個資料而言，在,d-,鄰居域中的鄰居資料數目不足的話，則此資料將會被視為離群值，如果數量足夠的話，就非離群值。,離群值分析,以,偏差概念,為基礎的離群值偵測方法,衡量資料的主要特性與在同一群資料中的特性有無出現偏差過大的情形，藉以找出資料中的離群值,SET,演算法,為 個資料的集合，為具有順序性的資料子集合，為其中的一個資料子集合中的第 個，而,在資料子集合中的順序性為透過隨機的方式賦予。之後,SET,演算法會計算每兩個資料子集合間的距離，其計算公式如下：,演算法會對每一個子集合進行分析，藉由移除一個 ，然後再計算剩餘子集合之間的距離,找出在 移除後可以減少全部子集合的距離最大的 ，則此 中的資料就會被認定為離群值,