Course5集群分析ClusterAnaly.ppt
《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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Course5 集群 分析 ClusterAnaly
链接地址:https://www.31ppt.com/p-5574487.html