《Course5集群分析ClusterAnaly.ppt》由会员分享，可在线阅读，更多相关《Course5集群分析ClusterAnaly.ppt（72页珍藏版）》请在三一办公上搜索。
1、Course 5集群分析Cluster Analysis,Outlines,什麼是集群分析？集群分析的典型應用集群分析應用實例什麼是好的集群分析？資料挖掘對集群分析的要求集群分析中的資料類型相異度計算主要的集群方法離異值挖掘,什麼是集群分析？,集群(Cluster:聚類、簇、分群):資料對象的集合所謂集群是指一群人、事、物或資料的組合，這些人、事、物或資料統稱為Object或對象在同一個集群(簇)中的Object彼此相似不同集群中的Object則相異集群分析將一堆Objects分成幾個群，使性質相似的對象自成一個小集群的過程假設每個對象在許多屬性(或欄位)上均有一個觀測分數，有人在某些屬性上分
2、數較高，在其它屬性上分數較低。每個對象在這些屬性上分數高低的情況，即為該Object在這些欄位上分數的Profiles(輪廓)，每個profile在幾何座標圖中以一點表示。,設A和B二個Objects在x和y兩個變數上均有一個分數。Profiles A是由x=2和y=3所組成;Profiles B是由x=3和y=2所組成。依據畢氏定理(The Pythagorean Theorem)，直角三角形ABC的斜邊之平方等於其它兩邊平方之和。由於d之大小是兩個Profile距離的函數，故一般通稱之為距離函數係數(Distance-Function Coefficient)。,A,B,C,d=2,d1=
3、1,d2=-1,集群是一種無指導的學習沒有預先定義的類別編號集群分析的資料挖掘功能作為一個獨立的工具來獲得資料分配的情況作為其他演算法(如特徵和分類)的預先處理步驟,以不同方式對相同集合之資料點做分群,集群分析的典型應用,模式識別空間資料分析在GIS系統中，對相似區域進行集群，產生主題地圖檢測空間集群，並給出它們在空間資料挖掘中的解釋圖像處理市場研究WWW對WEB上的文件進行分類對WEB日誌的資料進行集群，以發現相同的用戶訪問模式資訊檢索,集群分析的方法雖多，但下列三個問題乃各方法所共同關心的:如何以數量來表示事物(包括人)和事物之間的相似性(Similarity)?如何根據這些相似性指標將類
4、似的個體分成一類(或一個集群)?所有事物分類完畢後，對於每一集群的性質應如何描述?,什麼是好的集群分析？,一個好的集群分析方法會產生高品質的集群高的群內相似度低的群間相似度作為統計學的一個分支，集群分析的研究主要是基於距離的集群；一個高品質的集群分析結果，將取決於所使用的集群方法集群方法所使用的相似性度量和方法的實施方法發現隱藏模式的能力,資料挖掘對集群分析的要求,可量度性(Scalability)許多分群的方法運用在少量資料的分群結果很好，但是對於龐大的資料其結果會造成偏差(Bias)，因此分群的可量度性是需要的。處理不同資料類型的能力數字型，二元類型，類別型/區間型，順序型,比例型等等。發
5、現任意形狀群體的能力基於距離的集群演算法往往發現的是球形的集群，然而現實的集群可能是任意形狀的決定輸入參數的最少領域知識許多方法都需要輸入參數，然而參數很難決定，尤其是對於高維度資料，這使得集群的結果品質很難控制處理雜訊資料的能力對空缺值、離異值、資料雜訊不敏感,對於輸入資料的順序不敏感某些方法不能將新資料加入現有的群組資料中，它必須對全部資料重新進行群。也有一些方法會受輸入資料順序的影響。同一個資料集合，以不同的次序提交給同一個演算法，應該產生相似的結果。高維度高維度(多屬性)的資料往往比較稀疏或高度扭曲。基於限制的集群實際應用需要在不同的限制下進行分群。分群要使每個群組滿足特定限制。可解釋
6、性和可用性使用者會希望群組的結果具解釋性、了解性與使用性。,集群分析中的資料類型,許多基於主記憶體式的集群演算法採用以下兩種資料架構:資料矩陣(Data Matrix)用p個變數來表示n個對象也叫雙模式矩陣(Two-mode Matrix)，行與列代表不同實體相異矩陣(Dissimilarity Matrix)存放n個對象兩兩之間的近似性也叫單模式矩陣(One-mode Matrix)，行和列代表相同的實體,相異度計算,許多集群演算法都是以相異矩陣為基礎，如果資料是用資料矩陣形式表示，則往往要將其先轉化為相異矩陣。相異度d(i,j)的具體計算會因所使用的資料類型不同而不同，常用的資料類型包括區
7、間變數二元變數類別型、順序型和比例型變數混合類型的變數,區間變數(Interval-scaled Variables),區間變數是一個線性尺度下的連續值，比如重量、高度等選用的度量單位將直接影響集群分析的結果，因此需要實現度量值的標準化，將原來的值轉化為無單位的值，讓每個變數能有相同的權重。給定一個變數f的度量值，可使用以下兩步驟轉換計算平均絕對偏差 其中計算標準化的度量值(z-score)使用平均絕對偏差往往比使用標準差更具有健壯性,對象間的相似度和相異度,對象間的相似度和相異度是基於兩個對象間的距離來計算的歐幾里得(Euclidean)距離i=(xi1,xi2,xip)和j=(xj1,xj
8、2,xjp)是兩個p維資料對象曼哈頓(Manhattan)距離,Manhattan距離和Euclidean距離的性質d(i,j)0。距離為非負數d(i,i)=0。同一object間的距離為0d(i,j)=d(j,i)。距離為對稱函數d(i,j)d(i,k)+d(k,j)。由object i直接到object j的距離一定不大於經過第三個個體h的距離明可夫斯基(Minkowski)距離上式中，q為正整數，如果q=1則表示Manhattan距離，如果q=2則表示Euclidean距離,二元變數(Binary Variable),一個二元變數只有兩種狀態0或1；e.g.smoker來表示是否吸煙一個
9、對象可以包含多個二元變數。二元變數的列聯表(Contingency Table)如何計算兩個二元變數之間的相似度?,對稱的 v.s.不對稱的二元變數對稱的二元變數指變數的兩個狀態具有同等價值，相同權重；e.g.性別根據對稱的二元變數所產生的不相似度稱為對稱二元相異度(Symmetric Binary Dissimilarity)，可以使用簡單匹配系數評估它們的相異度不對稱的二元變數中，變數的兩個狀態的重要性是不同的；e.g.HIV陽性 v.s HIV陰性根據不對稱的二元變數所產生的不相似度稱為非對稱二元相異度(Asymmetric Binary Dissimilarity)。兩個0的一致在這裡
10、並不重要。,二元變數的相異度範例,二元變數之間的相異度（病患記錄表）,“姓名”是對象標識“性別”是對稱的二元變數其餘屬性都是非對稱的二元變數如過Y和P（positive陽性）為1，N為0，則,類別變數(Categorical Variable),類別變數是二元變數的推展，它可以具有多於兩個的狀態值。比如“商品顏色”這個屬性有紅、綠、藍、黃和粉紅5個狀態。類別變數的狀態之間的排列順序是不重要的。計算類別變數所描述的對象 i和j之間的相異度方法一簡單匹配方法m:匹配的數目，即對象i和j取值相同的變數的數目(也可加上權重),有一個混合類型變數的資料表如下：假設目前僅使用到屬性1來建構一個44相異矩陣
11、(如下左)，利用簡單匹配方法可計算出該矩陣之所有值(如下右)：,方法二對M個類別狀態中的每個狀態創建一個新的二元變數，並用非對稱的二元變數來編碼類別變數,個體編號 紅 綠 藍 黃 粉紅 取值 1 0 0 0 1 0 黃 2 01 0 0 0 綠 3 00 1 0 0 藍 4 00 0 1 0 黃,順序變數(Discrete ordinal Variable),一個順序型變數可以是離散的或者是連續的順序型變數的值之間是有順序關係的，比如講師、助理教授、副教授、正教授。假設有n個objects，f 是一個順序變數，f 的相異度計算如下1.xif為object i於變數f中的值，並假設變數f有Mf個
12、順序狀態1,2,Mf。用xif相對應之狀態的順序狀態 取代xif。2.將每個變數的值域映射到0,1的空間3.採用區間變數的相異度計算方法，利用zif計算相異度,利用前述混合類型變數資料表中的屬性2。此屬性爲連續順序變數，它包含三個狀態：一般、佳與極佳。所以Mf=3。先用順序值1,2,3取代上述三個狀態。將順序值正規化到0,1之間利用歐幾里得距離計算相異矩陣。,比例變數(Ratio-scaled Variable),一個比例變數xif是使用非線性的尺標中所取的正度量值，例如指數標度。AeBt or Ae-Bt 其中，A與B為正常數，t通常是表示時間有三種計算比例變數對象之間的相異度方法：採用與區
13、間變數同樣的方法 但尺度可能被扭曲。將比例變數進行對數變化，轉換後的yif可視為區間變數。yif=log(xif)將xif看作連續順序資料，將其視作有順序的區間值來處理,利用前述混合類型變數資料表中的屬性3。此屬性爲比例變數，對屬性3進行對數轉換，我們將object 1到4的值轉換為2.65,1.34,2.21與3.08。再利用歐幾里得距離計算相異矩陣。,混合類型的變數,在真實的資料庫中，資料對象不是被一種類型的度量所描述，而是被多種類型（即混合類型）的度量所描述，包括區間值、對稱二元變數，不對稱二元變數，類別變數，順序變數和比例變數計算混合型變數描述的對象之間的相異度將變數按類型分組，對每種
14、類型的變數進行單獨的集群分析在每種集群分析導出相似結果的情況下可行。但是在真實應用上，這種做法一般不會產生適當結果。所有變數一起處理，進行一次集群分析，把所有有意義的變數轉換到共同的值域區間0,1之內，可以將不同類型的變數組合在單個相異矩陣中。,可以使用類似權重公式的做法來結合不同變數所得到的相異矩陣之效果。假設資料包含p個混合類型的變數其中，一般皆為1；若=0當：xif 或 xjf 為遺失值F為不對稱二元變數，且 xif=xjf=0,利用前述混合類型變數資料表。屬性1和屬性2處理方式和先前相同，結果皆介於0到1之間。對屬性3進行對數轉換後的值分別為2.65,1.34,2.21與3.08，所以
15、max=3.08、min=1.34。將原先比例變數所得到的相異矩陣之所有值除以(3.08-1.34)=1.74，會得到新的相異矩陣,接下來，將三個不同類型變數所求得之相異矩陣，其每個相對位置之值代入下列公式即可。例如：d(2,1)=1(1)+1(1)+1(0.75)/3=0.92。所以，會得到新的混合變數之相異矩陣：,主要的集群方法,集群分析演算法種類繁多，主要有以下幾類：分割方法(Partitioning Methods)階層式的方法(Hierarchical Methods)基於密度的方法(Density-based Methods)基於網格的方法(Grid-based Methods)基
16、於模型的方法(Model-based Methods)實際應用中的集群演算法，往往是上述集群方法中多種方法的整合,分割式集群分析,主要概念：事先挑選集群核心和訂定臨界值，所有Objects與該集群核心之距離只要沒有超過臨界值，一律歸併入該集群內，否則屬於其它集群。,給定一個具有n個對象的資料庫，一個分割方法會構建資料的k個分割區域，每個區域表示一個集群，並且k n。每個組至少包含一個對象每個對象屬於且僅屬於一個組分割準則同一個集群中的對象儘可能的接近或相關，不同集群中的對象儘可能的遠離或不同集群的表示k-平均演算法(k-Means)由集群的平均值來代表整個集群k中心點演算法(k-Medoids
17、)由處於集群中心區域的某個值代表整個集群以上兩種方法的變形,基於質心的技術：K平均方法,集群的相似度是關於集群中對象的平均值之度量，可以看成集群的質心(Centroid)K平均方法的計算流程：隨機選擇K個對象，每個對象代表一個集群的初始平均值或中心對剩餘的每個對象，根據它與集群均值的距離，將它指派到最相似的集群計算每個集群的新均值回到步驟2循環執行，直到準則函數收斂常用的準則函數：平方差準則(p是空間中的點，mi是集群Ci的均值),K-Means 分群法,範例,K=2任意選擇 K 個體當作起始群組中心,將每個個體分配至最接近中心,更新群組均值,更新群組均值,重新分配,重新分配,K-Means
18、法建議,優勢:相當有效率:O(tkn),n 為Object數目,k 為群組數目,t 為重複次數。一般來說 k與t皆遠小於 n.相較於其他方法:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k)經常找到區域最佳解。滿足收歛狀態的集群可能會有很多種(初始點、距離公式不同)全域最佳解可用下列方法找到:絕對降溫法或基因運算法則弱勢是用於均值可定義,那類別資料呢?需要事先設定群組數目 k無法處理雜訊與離異值不適合發掘非凸面形狀群組,K-Means 法變異,一些不同 k-means 主要差異在選擇起始 k 個均值不相似計算計算群組均值的方法處理類別資料:k-modes(Huang98)用模
19、式取代群組均值對類別個體使用新的不相似指標使用頻率式方法來更新群組模式類別與數值資料混合:k-prototype 方法,K-means與不同類型的群集,K-means和它的變形法在找尋不同類型的群集時有一些限制，尤其是當群集是非球型（non-spherical shapes），或有各種不同之大小或密度時。K-means在發現自然的（natural）群集會有困難,有不同大小之K-means群集,有不同密度之K-means群集,非球状之K-means群集,K-Means 方法的問題?,k-means 對離異值非常敏感!因為具有極大值Object會扭曲資料分佈平方差函數將進一步惡化這個這種影響K-M
20、edoids:不使用均值作為群組的參考點,我們使用medoids,它是群組最中心的個體降低對離異值的敏感度,K中心點方法,執行步驟：K中心點方法仍然基於最小化所有對象與其對應的參照點之間的相異度之和的原則，使用的是絕對誤差標準(p是空間中的點，代表集群Cj中的個給定對象；oj是集群Cj中的代表對象)本法通常會重複執行，直到每個代表對象都成為它的集群之實際中心點首先隨意選擇初始代表對象只要能夠提高聚類結果的品質，迭代過程就使用非代表對象替換代表對象聚類結果的品質是用代價函數來評估，該函數測量對象與其集群的代表對象之間的平均差異程度。,代表對象替換,為了確定非代表對象Orandom是否能夠替代當前
21、代表對象Oj，對於每一個非代表對象p，考慮四種情況：,重新分配將對代價函數產生影響，如果當前的代表對象被非代表對象所取代，代價函數就是計算絕對誤差值的差。變換的總代價是所有非代表對象所產生的代價之和總代價為負，實際的絕對誤差E將減少，Oj可以被Orandom所取代總代價為正，則本次迭代沒有變化,K均値法 vs.K中心點法,當存在雜訊和離群點時，K中心點法比K均值法更加強健中心點受離群點的影響較少K中心點方法的執行代價比K均值法要高K均值法:O(nkt)K中心點法:O(k(n-k)2)n與k較大時，K中心點法的執行代價很高兩種方法都要使用者指定集群的數目K,6,5,2,4,階層集群分析,N個Ob
22、jects未分類前，每個Object自成一類，共有N類。經過N-1次歸類程序後，所有Objects成一個大集群。每次歸類時各集群合併的情形及合併後組內誤差增加的數量，會以階層樹狀圖(Dendrogram)表示。,1,3,使用距離矩陣作為分群條件.這個方法不需群組數目 k 作為輸入,但是它需要一個結束條件,産生階層分群的方法,凝聚式的（Agglomerative）：開始將每個對象作為單獨的一個組，然後相繼的合併相近的對象或組，直到所有的組合併為一個，或者達到一個終止條件。這需要定義群集鄰近值（cluster proximity）的概念分裂式的（Divisive）：開始將所有的對象置於一個集群中，
23、在迭代的每一步，一個集群被分裂為多個更小的集群，直到最終每個對象在一個單獨的集群中，或達到一個終止條件在這個情況下，需要決定在每一步驟中哪一個群集要被切割，以及如何做切割缺點合併或分裂的步驟不能被撤銷,凝聚式階層分群,階層分群技術（hierarchical clustering techniques）是第二重要的分群方法類別如同K-means，這些方法和許多分群演算法比起來相對較久遠，但它們仍然被廣泛使用,四個資料點的階層分群以樹状圖和巣状群集表示,基本的凝聚式階層分群演算法,華德氏階層羣集分析,這個方法在集群分析之始，將每個Object各視為一個集群，然後將各集群依次合併。何者先合併，何者後
24、合併，完全視合併後集群之組內總變異程度而定。範例:,距離函數平方和 d2AB=,利用前面所求得的距離函數平方和矩陣，來計算每對Objects的組內誤差矩陣(Error Matrix for Each Pair of Objects).組內誤差矩陣:同一集群內各Profiles間距離函數之平方和，除以該集群之Objects數,EAB=d2AB/N,這些數據中以E和F所組成的集群之組內誤差最小，因此將E和F合併成一集群，並將之定名為E,EAE=EAE(NA+NE)+EAF(NA+NF)+EEF(NE+NF)-EAA(NA)-EEE(NE)EFF(NF)/(NA+NE+NF)=38.5(1+1)+3
25、3(1+1)+0.5(1+1)-0(1)-0(1)-0(1)/(1+1+1)=48,基於密度的方法,基於距離的集群方法的缺點只能發現球狀的集群，難以發現任意形狀的集群。基於密度的據類只要臨近區域的密度（對象或資料點的數目）超過某個臨界值，就繼續集群。優點可以過濾掉“雜訊”和“離異值”，發現任意形狀的集群。,基於網格的方法,把對象空間量化為有限數目的單元，形成一個網格架構。所有的集群都在這個網格架構上進行。優點處理數度快（因為處理時間獨立於資料對象數目，只與量化空間中每一維的單元數目有關）,基於模型的方法,為每個集群假定一個模型，嘗試將資料與給定模型進行最適化。一個基於模型的演算法可能透過構建反
26、映資料點空間分配的密度函數來定位集群這種方法同時也用於自動的決定資料集中集群的數目透過統計學的方法，考慮雜訊和離異值，從而產生健壯的集群方法,如何有效的使用集群分析,變項的選擇在集群分析之前，研究者首先應決定每個Object應具有哪些變項之分數變項的選擇對集群分析的結果有重大的影響由於變項的選擇沒有任何統計法則可供指引，研究者只有依據理論架構小心翼翼的決定變項的標準化如果各變項單位大略一致，可以不必予以標準化；如果單位不一致，則有的研究者常根據全體資料之標準差將之標準化，使其平均數各為零，標準差各為1。不過這種標準化方式會使各羣體在最具區別力之變項上的差距縮減尚有下列處理辦法:利用其它外界資料
27、(External Data)作為尋找同質性羣體的參考如果沒有辦法找到外界資料，則可先用全體資料的標準差進行集群分析，再根據分類後各組的組內標準差將各組資料標準化,相關變項的處理在集群分析時，如果變項愈多，所需的電腦時間就隨之急劇增加。因此，如果變項很多，且各變項的相關性很大，則常使用因素分析(如:主成份分析)將各變項濃縮成數目較少的因素。然後以幾個較重要的因素分數作為變項，進行集群分析。集群分析方法的挑選集群分析的方法非常繁多，但到現在還沒有任何方法被確定為最優異的方法，而每個方法所得的結果有時又略有出入。此外，目前集群分析的結果應保留多少集群，雖然學者已發展出各種集群顯著性考驗，但迄今尚乏
28、一個大家公認的理想方法。因此，目前一般研究者採用的應對措施是在做研究時兼採幾種不同的集群分析，再根據各種結果的意義性和可解釋性，從中挑選一個。,樣本的拆半考驗為考驗集群分析結果的推廣性，研究者可將樣本隨機分成二半，對各半樣本分別進行集群分析，然後再檢查這兩半樣本所得的結果是否一致。各變項重要性的辨認在集群分析中所用的各變項並非具有同等的區別力。如果能了解在一羣變項中何者是關鍵的變項，將是研究上的重要發現。可先以所有的變項進行集群分析，然後再將所認為的可能重要變項，從整個資料矩陣中刪除，再對剩餘的資料矩陣進行集群分析。如果所刪除的變項確為重要變項，則兩次分析的結果將有顯著的不同。,離異値挖掘,什
29、麼是離異值(Outlier)?與其他一般資料行為或模型有著顯著區別的資料集合例如Michael Jordon,比爾蓋茲離異值產生原因設定或執行上之錯誤（年齡-999）與生俱來的資料變異之結果離異值挖掘給定一個n個資料的集合，以及預期可能找出的離異值個數k，發現與剩餘的資料有著顯著差異的頭k個資料對象離異值挖掘可用於異常偵測，主要是要在很多物件中找到不同的物件，通常異常的物件為離異值。異常偵測(anomaly detection)也稱為偏差偵測（deviation detection），因為異常物件的屬性值會與預期的或基本的屬性值有顯著的偏差。,異常的應用範例,詐欺偵測（fraud detect
30、ion）：竊取信用卡者的購買行為可能會與信用卡持有人不同，信用卡公司觀察購買行為模式或注意基本行為的變化，可偵測到竊賊。類似的方法也可用於其他類型的詐欺入侵偵測（intrusion detection）：電腦系統和電腦網路是常見的攻擊行為。部分攻擊是顯而易見的，但如癱瘓電腦和網路的運作並秘密地收集資訊之類的攻擊則是很難偵測的。多數這類的攻擊只要監看系統與網路的異常狀況，即可偵測到生態系統的混亂（ecosystem disturbances）：在真實的世界中，有很多異常事件會對人類造成很大的影響，例如颶風、洪水、乾旱、熱浪與火災。這個目的是要去預測這些事件的可能性以及發生的原因,國民健康（pub
31、lic health）：在許多國家，醫院和醫療診所會對國家級組織報告各種統計資料，以便做進一步的分析。例如，若一個城市中的所有小孩已接種某種疫苗（例如麻疹疫苗），則散佈於不同醫院的少數個案就會是一個異常事件，這也代表這個城市有接種疫苗上的問題醫學（medicine）：針對特定的病患，異常的症狀或測試結果代表潛在的健康問題。然而，一個特定測試結果是否為異常，仍要依照病患的其他特徵，如年齡和性別來進行判斷。此外，結果的分類可能為異常的 若病患是健康的，則不需要額外的測試；而若這個條件是未被診斷或是未處理的，則會對病患有害,基於統計的離異値檢測,統計的方法對於給定的資料集合假定了一個分配或機率模型（
32、例如常態分配）使用倚賴於以下參數的不一致性檢驗（discordancy tests）資料分配分配參數（e.g.均值或方差）預期的離異值數缺點絕大多數檢驗是針對單個屬性的，而資料挖掘要求在多維空間中發現離異值大部分情況下，資料分配可能是未知的,基於距離的離異値檢測,為了解決統計學方法帶來的一些限制，引入了基於距離的離異值檢測在不知道資料分配的情況下對資料進行多維分析基於距離的離異值即DB(p,d)，如果資料集合S中的對象至少有p部分與對象o的距離大於d，則對象o就是DB(p,d)。挖掘基於距離的離異值的高效演算法基於索引的演算法巢狀循環演算法基於單元的演算法,基於偏差的離異値檢測,透過檢查一組對象的主要特徵來確立離異值跟主要特徵的描述相“偏離”的對象被認為是離異值兩種基於偏離的離異值探測技術序列異常技術模仿人類從一系列推測類似的對象中識別異常對象的模式OLAP資料立方體技術在大規模的多維資料中採用資料立方體來確定異常區域。如果一個立方體的單元值顯著的不同於根據統計模型得到的期望值，則改單元值被認為是一個異常，並用可視化技術表示。,
