Course5集群分析ClusterAnalysis课件

Course5

集群分析

ClusterAnalysisOutlines什麼是集群分析？集群分析的典型應用集群分析應用實例什麼是好的集群分析？資料挖掘對集群分析的要求集群分析中的資料類型相異度計算主要的集群方法離異值挖掘什麼是集群分析？集群(Cluster:聚類、簇、分群):資料對象的集合所謂集群是指一群人、事、物或資料的組合，這些人、事、物或資料統稱為Object或對象在同一個集群(簇)中的Object彼此相似不同集群中的Object則相異集群分析將一堆Objects分成幾個群，使性質相似的對象自成一個小集群的過程假設每個對象在許多屬性(或欄位)上均有一個觀測分數，有人在某些屬性上分數較高，在其它屬性上分數較低。每個對象在這些屬性上分數高低的情況，即為該Object在這些欄位上分數的Profiles(輪廓)，每個profile在幾何座標圖中以一點表示。集群是一種無指導的學習︰沒有預先定義的類別編號集群分析的資料挖掘功能作為一個獨立的工具來獲得資料分配的情況作為其他演算法(如︰特徵和分類)的預先處理步驟以不同方式對相同集合之資料點做分群集群分析的典型應用模式識別空間資料分析在GIS系統中，對相似區域進行集群，產生主題地圖檢測空間集群，並給出它們在空間資料挖掘中的解釋圖像處理市場研究WWW對WEB上的文件進行分類對WEB日誌的資料進行集群，以發現相同的用戶訪問模式資訊檢索什麼是好的集群分析？一個好的集群分析方法會產生高品質的集群高的群內相似度低的群間相似度作為統計學的一個分支，集群分析的研究主要是基於距離的集群；一個高品質的集群分析結果，將取決於所使用的集群方法集群方法所使用的相似性度量和方法的實施方法發現隱藏模式的能力資料挖掘對集群分析的要求可量度性(Scalability)許多分群的方法運用在少量資料的分群結果很好，但是對於龐大的資料其結果會造成偏差(Bias)，因此分群的可量度性是需要的。處理不同資料類型的能力數字型，二元類型，類別型/區間型，順序型,比例型等等。發現任意形狀群體的能力基於距離的集群演算法往往發現的是球形的集群，然而現實的集群可能是任意形狀的決定輸入參數的最少領域知識許多方法都需要輸入參數，然而參數很難決定，尤其是對於高維度資料，這使得集群的結果品質很難控制處理雜訊資料的能力對空缺值、離異值、資料雜訊不敏感對於輸入資料的順序不敏感某些方法不能將新資料加入現有的群組資料中，它必須對全部資料重新進行群。也有一些方法會受輸入資料順序的影響。同一個資料集合，以不同的次序提交給同一個演算法，應該產生相似的結果。高維度高維度(多屬性)的資料往往比較稀疏或高度扭曲。基於限制的集群實際應用需要在不同的限制下進行分群。分群要使每個群組滿足特定限制。可解釋性和可用性使用者會希望群組的結果具解釋性、了解性與使用性。相異度計算許多集群演算法都是以相異矩陣為基礎，如果資料是用資料矩陣形式表示，則往往要將其先轉化為相異矩陣。相異度d(i,j)的具體計算會因所使用的資料類型不同而不同，常用的資料類型包括︰區間變數二元變數類別型、順序型和比例型變數混合類型的變數區間變數(Interval-scaledVariables)區間變數是一個線性尺度下的連續值，比如重量、高度等選用的度量單位將直接影響集群分析的結果，因此需要實現度量值的標準化，將原來的值轉化為無單位的值，讓每個變數能有相同的權重。給定一個變數f的度量值，可使用以下兩步驟轉換︰計算平均絕對偏差其中計算標準化的度量值(z-score)使用平均絕對偏差往往比使用標準差更具有健壯性對象間的相似度和相異度對象間的相似度和相異度是基於兩個對象間的距離來計算的歐幾里得(Euclidean)距離i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是兩個p維資料對象曼哈頓(Manhattan)距離二元變數(BinaryVariable)一個二元變數只有兩種狀態︰0或1；e.g.smoker來表示是否吸煙一個對象可以包含多個二元變數。二元變數的列聯表(ContingencyTable)︰如何計算兩個二元變數之間的相似度?ObjectiObjectj對稱的v.s.不對稱的二元變數對稱的二元變數指變數的兩個狀態具有同等價值，相同權重；e.g.性別根據對稱的二元變數所產生的不相似度稱為對稱二元相異度(SymmetricBinaryDissimilarity)，可以使用簡單匹配系數評估它們的相異度︰不對稱的二元變數中，變數的兩個狀態的重要性是不同的；e.g.HIV陽性v.sHIV陰性根據不對稱的二元變數所產生的不相似度稱為非對稱二元相異度(AsymmetricBinaryDissimilarity)。兩個0的一致在這裡並不重要。二元變數的相異度──範例二元變數之間的相異度（病患記錄表）“姓名”是對象標識“性別”是對稱的二元變數其餘屬性都是非對稱的二元變數如過Y和P（positive陽性）為1，N為0，則︰有一個混合類型變數的資料表如下：假設目前僅使用到屬性1來建構一個4×4相異矩陣(如下左)，利用簡單匹配方法可計算出該矩陣之所有值(如下右)：個體編號屬性1(類別)屬性2(順序)屬性3(比例)1黃極佳4452綠一般223藍佳1644黃極佳1210方法二︰對M個類別狀態中的每個狀態創建一個新的二元變數，並用非對稱的二元變數來編碼類別變數個體編號紅綠藍黃粉紅取值10 00 10黃20 10 00綠

30 01 00藍40 00 10黃順序變數(DiscreteordinalVariable)一個順序型變數可以是離散的或者是連續的順序型變數的值之間是有順序關係的，比如︰講師、助理教授、副教授、正教授。假設有n個objects，f是一個順序變數，f的相異度計算如下︰1.xif為objecti於變數f中的值，並假設變數f有Mf個順序狀態1,2,…,Mf。用xif相對應之狀態的順序狀態取代xif。2.將每個變數的值域映射到[0,1]的空間3.採用區間變數的相異度計算方法，利用zif計算相異度比例變數(Ratio-scaledVariable)一個比例變數xif是使用非線性的尺標中所取的正度量值，例如指數標度。AeBtorAe-Bt

其中，A與B為正常數，t通常是表示時間有三種計算比例變數對象之間的相異度方法：採用與區間變數同樣的方法─但尺度可能被扭曲。將比例變數進行對數變化，轉換後的yif可視為區間變數。yif=log(xif)將xif看作連續順序資料，將其視作有順序的區間值來處理利用前述混合類型變數資料表中的屬性3。此屬性爲比例變數，對屬性3進行對數轉換，我們將object1到4的值轉換為2.65,1.34,2.21與3.08。再利用歐幾里得距離計算相異矩陣。利用前述混合類型變數資料表。屬性1和屬性2處理方式和先前相同，結果皆介於0到1之間。對屬性3進行對數轉換後的值分別為2.65,1.34,2.21與3.08，所以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。所以，會得到新的混合變數之相異矩陣：主要的集群方法集群分析演算法種類繁多，主要有以下幾類：分割方法(PartitioningMethods)階層式的方法(HierarchicalMethods)基於密度的方法(Density-basedMethods)基於網格的方法(Grid-basedMethods)基於模型的方法(Model-basedMethods)…實際應用中的集群演算法，往往是上述集群方法中多種方法的整合分割式集群分析主要概念：事先挑選集群核心和訂定臨界值，所有Objects與該集群核心之距離只要沒有超過臨界值，一律歸併入該集群內，否則屬於其它集群。ABCDEFG給定一個具有n個對象的資料庫，一個分割方法會構建資料的k個分割區域，每個區域表示一個集群，並且k≤n。每個組至少包含一個對象每個對象屬於且僅屬於一個組分割準則︰同一個集群中的對象儘可能的接近或相關，不同集群中的對象儘可能的遠離或不同集群的表示k-平均演算法(k-Means)由集群的平均值來代表整個集群k中心點演算法(k-Medoids)由處於集群中心區域的某個值代表整個集群以上兩種方法的變形基於質心的技術：K平均方法集群的相似度是關於集群中對象的平均值之度量，可以看成集群的質心(Centroid)K平均方法的計算流程：隨機選擇K個對象，每個對象代表一個集群的初始平均值或中心對剩餘的每個對象，根據它與集群均值的距離，將它指派到最相似的集群計算每個集群的新均值回到步驟2循環執行，直到準則函數收斂常用的準則函數：平方差準則(p是空間中的點，mi是集群Ci的均值)K-Means分群法

範例K=2任意選擇K個體當作起始群組中心將每個個體分配至最接近中心更新群組均值012345678910012345678910更新群組均值重新分配重新分配012345678910012345678910K-Means法建議優勢:

相當有效率: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(Huang’98)用模式取代群組均值對類別個體使用新的不相似指標使用頻率式方法來更新群組模式類別與數值資料混合:k-prototype方法K-means與不同類型的群集K-means和它的變形法在找尋不同類型的群集時有一些限制，尤其是當群集是非球型（non-sphericalshapes），或有各種不同之大小或密度時。K-means在發現「自然的」（natural）群集會有困難有不同大小之K-means群集有不同密度之K-means群集非球状之K-means群集K-Means方法的問題?k-means對離異值非常敏感!因為具有極大值Object會扭曲資料分佈平方差函數將進一步惡化這個這種影響K-Medoids:不使用均值作為群組的參考點,我們使用medoids,它是群組最中心的個體降低對離異值的敏感度K中心點方法執行步驟：K中心點方法仍然基於最小化所有對象與其對應的參照點之間的相異度之和的原則，使用的是絕對誤差標準(p是空間中的點，代表集群Cj中的個給定對象；oj是集群Cj中的代表對象)本法通常會重複執行，直到每個代表對象都成為它的集群之實際中心點首先隨意選擇初始代表對象只要能夠提高聚類結果的品質，迭代過程就使用非代表對象替換代表對象聚類結果的品質是用代價函數來評估，該函數測量對象與其集群的代表對象之間的平均差異程度。代表對象替換為了確定非代表對象Orandom是否能夠替代當前代表對象Oj，對於每一個非代表對象p，考慮四種情況：重新分配將對代價函數產生影響，如果當前的代表對象被非代表對象所取代，代價函數就是計算絕對誤差值的差。變換的總代價是所有非代表對象所產生的代價之和總代價為負，實際的絕對誤差E將減少，Oj可以被Orandom所取代總代價為正，則本次迭代沒有變化K均値法vs.K中心點法當存在雜訊和離群點時，K中心點法比K均值法更加強健中心點受離群點的影響較少K中心點方法的執行代價比K均值法要高K均值法:O(nkt)K中心點法:O(k(n-k)2)n與k較大時，K中心點法的執行代價很高兩種方法都要使用者指定集群的數目K6524階層集群分析N個Objects未分類前，每個Object自成一類，共有N類。經過N-1次歸類程序後，所有Objects成一個大集群。每次歸類時各集群合併的情形及合併後組內誤差增加的數量，會以階層樹狀圖(Dendrogram)表示。FEGDCBAABCDEFG13使用距離矩陣作為分群條件.這個方法不需群組數目k

作為輸入,但是它需要一個結束條件步驟0步驟1步驟2步驟3步驟4bdceaabdecdeabcde步驟4步驟3步驟2步驟1步驟0凝聚式(AGNES)分裂式(DIANA)産生階層分群的方法凝聚式的（Agglomerative）：開始將每個對象作為單獨的一個組，然後相繼的合併相近的對象或組，直到所有的組合併為一個，或者達到一個終止條件。這需要定義群集鄰近值（clusterproximity）的概念分裂式的（Divisive）：開始將所有的對象置於一個集群中，在迭代的每一步，一個集群被分裂為多個更小的集群，直到最終每個對象在一個單獨的集群中，或達到一個終止條件在這個情況下，需要決定在每一步驟中哪一個群集要被切割，以及如何做切割缺點︰合併或分裂的步驟不能被撤銷凝聚式階層分群階層分群技術（hierarchicalclusteringtechniques）是第二重要的分群方法類別如同K-means，這些方法和許多分群演算法比起來相對較久遠，但它們仍然被廣泛使用四個資料點的階層分群以樹状圖和巣状群集表示基本的凝聚式階層分群演算法華德氏階層羣集分析這個方法在集群分析之始，將每個Object各視為一個集群，然後將各集群依次合併。何者先合併，何者後合併，完全視合併後集群之組內總變異程度而定。範例:距離函數平方和d2AB=利用前面所求得的距離函數平方和矩陣，來計算每對Objects的組內誤差矩陣(ErrorMatrixforEachPairofObjects).組內誤差矩陣:同一集群內各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)+33(1+1)+0.5(1+1)-0(1)-0(1)-0(1)]/(1+1+1)=48基於密度的方法基於距離的集群方法的缺點︰只能發現球狀的集群，難以發現任意形狀的集群。基於密度的據類︰只要臨近區域的密度（對象或資料點的數目）超過某個臨界值，就繼續集群。優點︰可以過濾掉“雜訊”和“離異值”，發現任意形狀的集群。基於網格的方法把對象空間量化為有限數目的單元，形成一個網格架構。所有的集群都在這個網格架構上進行。優點︰處理數度快（因為處理時間獨立於資料對象數目，只與量化空間中每一維的單元數目有關）基於模型的方法為每個集群假定一個模型，嘗試將資料與給定模型進行最適化。一個基於模型的演算法可能透過構建反映資料點空間分配的密度函數來定位集群這種方法同時也用於自動的決定資料集中集群的數目透過統計學的方法，考慮雜訊和離異值，從而產生健壯的集群方法如何有效的使用集群分析變項的選擇在集群分析之前，研究者首先應決定每個Object應具有哪些變項之分數變項的選擇對集群分析的結果有重大的影響由於變項的選擇沒有任何統計法則可供指引，研究者只有依據理論架構小心翼翼的決定變項的標準化如果各變項單位大略一致，可以不必予以標準化；如果單位不一致，則有的研究者常根據全體資料之標準差將之標準化，使其平均數各為零，標準差各為1。不過這種標準化方式會使各羣體在最具區別力之變項上的差距縮減尚有下列處理辦法:利用其它外界資料(ExternalData)作為尋找同質性羣體的參考如果沒有辦法找到外界資料，則可先用全體資料的標準差進行集群分析，再根據分類後各組的組內標準差將各組資料標準化相關變項的處理在集群分析時，如果變項愈多，所需的電腦時間就隨之急劇增加。因此，如果變項很多，且各變項的相關性很大，則常使用因素分析(如:主成份分析)將各變項濃縮成數目較少的因素。然後以幾個較重要的因素分數作為變項，進行集群分析。集群分析方法的挑選集群分析的方法非常繁多，但到現在還沒有任何方法被確定為最優異的方法，而每個方法所得的結果有時又略有出入。此外，目前集群分析的結果應保留多少集群，雖然學者已發展出各種集群顯著性考驗，但迄今尚乏一個大家公認的理想方法。因此，目前一般研究者採用的應對措施是在做研究時兼採幾種不同的集群分析，再根據各種結果的意義性和可解釋性，從中挑選一個。樣本的拆半考驗為考驗集群分析結果的推廣性，研究者可將樣本隨機分成二半，對各半樣本分別進行集群分析，然後再檢查這兩半樣本所得的結果是否一致。各變項重要性的辨認在集群分析中所用的各變項並非具有同等的區別力。如果能了解在一羣變項中何者是關鍵的變項，將是研究上的重要發現。可先以所有的變項進行集群分析，然後再將所認為的可能重要變項，從整個資料矩陣中刪除，再對剩餘的資料矩陣進行集群分析。如果所刪除的變項確為重要變項，則兩次分析的結果將有顯著的不同。離異値挖掘什麼是離異值(Outlier)?與其他一般資料行為或模型有著顯著區別的資料集合例如︰MichaelJordon,比爾蓋茲…離異值產生原因設定或執行上之錯誤（年齡︰-999）與生俱來的資料變異之結果離異值挖掘給定一個n個資料的集合，以及預期可能找出的離異值個數k，發現與剩餘的資料有著顯著差異的頭k個資料對象離異值挖掘可用於異常偵測，主要是要在很多物件中找到不同的物件，通常異常的物件為離異值。異常偵測(anomalydetection)也稱為偏差偵測（deviationdetection），因為異常物件的屬性值會與預期的或基本的屬性值有顯著的偏差。異常的應用範例詐欺偵測（frauddetection）：竊取信用卡者的購買行為可能會與信用卡持有人不同，信用卡公司觀察購買行為模式或注意基本行為的變化，可偵測到竊賊。類似的方法也可用於其他類型的詐欺入侵偵測（intrusiondetection）：電腦系統和電腦網路是常見的攻擊行為。部分攻擊是