群集分析 (Cluster Analysis)79017.ppt
《群集分析 (Cluster Analysis)79017.ppt》由会员分享,可在线阅读,更多相关《群集分析 (Cluster Analysis)79017.ppt(75页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、群集分析群集分析(Cluster Analysis)1內容概要內容概要簡介簡介資料的表示資料的表示相似度的計算與測量相似度的計算與測量分群法的採用分群法的採用分割式分群法分割式分群法非分割式分群法非分割式分群法分群法在大型資料集合之設計分群法在大型資料集合之設計評估分群的結果評估分群的結果2簡介簡介(1)群集分析的概念與目的群集分析的概念與目的將資料集合中的資料記錄,又稱為資料點,加以分群成數個群集(cluster),使得每個群集中的資料點間相似程度高於與其它群集中資料點的相似程度 主要的目地是分析資料彼此間的相似程度,藉由分析所找到的群集結果,推論出有用、隱含、令人感興趣的特性和現象在群集分
2、析的過程中,並沒有預先指定好的類別資訊,也沒有任何資訊可以表示資料記錄彼此之間是相關的,所以群集分析被視為一個非監督式學習的過程 3簡介簡介(2)群集分析在資料探勘過程中所扮演的角色群集分析在資料探勘過程中所扮演的角色資料精簡資料精簡將原本大量的資料加以分群成數個群集,並從每一個群集中挑挑選具有代表性的資料記錄來進行後續的處理選具有代表性的資料記錄來進行後續的處理 推斷假設的產生推斷假設的產生推斷出所關注資料中可能存在的某些特性或現象推斷出所關注資料中可能存在的某些特性或現象“年輕人通常年收入較低”、“中年人通常年收入較高”推斷假設的驗證推斷假設的驗證對推斷假設作有效性的驗證對推斷假設作有效性
3、的驗證試圖驗證“年輕人通常年收入較低,是否也代表其消費能力較低?”此假設性推斷時,可以對於“年齡”、“年收入”和“消費金額”所描述的資料記錄進行群集分析 歸屬預測歸屬預測分群結果應用於未知分類之資料記錄,預測資料所歸屬的群集分群結果應用於未知分類之資料記錄,預測資料所歸屬的群集 4簡介簡介(3)線上購物網站的使用者族群與消費能力線上購物網站的使用者族群與消費能力會員年齡平均月收入(千)120202212632225441305433265240755385簡介簡介(4)群集分析應用領域群集分析應用領域交易行為分析交易行為分析解各類型使用者的行為模式空間資料分析空間資料分析幫助使用者自動化分析圖
4、像資料庫所產生的影像資料,了解感興趣的特性和現象文件管理文件管理將文件加以分門別類,幫助文件資料的管理和使用6簡介簡介(5)群集分析五個主要的循序工作項目群集分析五個主要的循序工作項目資料的表示:資料的表示:找出代表性資料維度來表示資料點相似度的計算與測量:相似度的計算與測量:計算資料點間相似的程度分群法的採用:分群法的採用:挑選適當的分群演算法評估分群的結果:評估分群的結果:對群集分析的結果進行評估群集的解釋:群集的解釋:領域專家對分群結果做進一步解釋7資料的表示資料的表示將每一資料點利用有限、一致的資料維度表示將每一資料點利用有限、一致的資料維度表示濾掉與所分析問題無關、偏差、重複的資料維
5、度濾掉與所分析問題無關、偏差、重複的資料維度不適切的資料維度將造成分群結果凌亂、難以從中不適切的資料維度將造成分群結果凌亂、難以從中獲取各群聚的關係與差異獲取各群聚的關係與差異 相對於“性別”和“地址”這兩個資料維度,“平均月收入”與“年齡”這兩個資料維度將更能幫助了解各類型之會員族群會員2將可以表示為,其中21為會員2在“年齡”此資料維度的資料數值,而26為會員2在“平均月收入”此資料維度的資料數值 8相似度的計算與測量相似度的計算與測量衡量資料點間的相似度將決定資料記錄所歸衡量資料點間的相似度將決定資料記錄所歸屬的群聚,並影響整個分群的結果屬的群聚,並影響整個分群的結果相似度測量法是群集分
6、析中最根本的課題相似度測量法是群集分析中最根本的課題相似度的計算與測量的考量相似度的計算與測量的考量資料型態的考量資料型態的考量應用範圍的考量應用範圍的考量資料離散程度與複雜性的考量資料離散程度與複雜性的考量 9資料型態的考量資料型態的考量(1)連續性資料維度連續性資料維度通常利用簡單的空間距離計算公式,透過衡量資料點間距離的遠近來判斷彼此間的相似程度尤拉距離尤拉距離(Euclidean distance)資料點 xi=和資料點 xj=之間的尤拉距離:d2(xi,xj)=()曼哈頓距離曼哈頓距離(Manhattan distance)dM(xi,xj)=10資料型態的考量資料型態的考量(2)尤
7、拉距離與曼哈頓距離在二維空間上的物理尤拉距離與曼哈頓距離在二維空間上的物理意義意義會員1=與會員2=之間的尤拉距離與曼哈頓距離分別如下所示d2(x1,x2)=6dM(x1,x2)=7 11資料型態的考量資料型態的考量(3)類別型態資料維度類別型態資料維度利用字串比對的方式,對於資料數值完全相同時則相似度以1表示,否則以0表示透過專家事先訂定資料數值間的相似度與輔助之計算公式先轉換或對應成連續性的資料數值,再套用距離計算公式來計算其相似度 12應用範圍的考量應用範圍的考量(1)資料點之間的相似程度資料點之間的相似程度群集間的相似程度群集間的相似程度 13應用範圍的考量應用範圍的考量(2)14資料
8、離散程度與複雜性的考量資料離散程度與複雜性的考量一般相似度計算公式通常對資料點中各資料一般相似度計算公式通常對資料點中各資料維度給予相同的重要性,然而這將造成值域維度給予相同的重要性,然而這將造成值域(domain)較大的資料維度將左右分群的結果較大的資料維度將左右分群的結果會員A=、會員B=與會員C=透過尤拉距離的相似度公式計算後,將會認定會員A與會員C相似度較高;用人來判斷,會員A與會員B應該較可能屬於同一個族群 15分群法的採用分群法的採用分群法的種類分群法的種類應用領域應用領域:應用的目的通常決定分群法的使用分割式分群法適合找出類圓形和群集大小相似的群集階層式分群法或以密集度導向分群法
9、適合找出自然形狀 的群集任意大小的群集資料內容資料內容有些分群法相當容易受雜訊或偏移值的影響 資料維度與資料記錄數量的大小會影響分群法的成效 品質與速度的取捨品質與速度的取捨 品質與速度的需求常常是矛盾而難以取捨的 16分割式分群法分割式分群法(1)概念概念將資料點歸屬到數個互不交集的群集中,讓每一群集中的資料點與該群集之群集中心(clustering center)相似程度高於與其它群集中心,企圖使得每個資料點距離它所屬的群集中心的距離偏移值為最小 將n個資料點分配k個互不交集的群中,其距離總偏移值(total deviation)E:x表示一資料點,ui表示Si群集的群集中心17分割式分群
10、法分割式分群法(2)最小距離總偏移值最小距離總偏移值除非資料點所有可能的組合都嘗試當作一開始之起始群集中心點,否則將無法保證在所設定之k個群集中,得到最小距離總偏移值反覆重新配置技術反覆重新配置技術分割式分群法一開始會隨機先選擇k個資料點當作起始之群集中心接著每一回合都企圖尋找更好的群集中心來降低距離總偏移值,一旦距離總偏移值不再變動或已執行一定的回合數,則終止處理並輸出分群結果一開始所挑選之起始資料點的好壞,將對於分群結果優劣具有決定性的影響 18分割式分群法分割式分群法(3)k-平均法平均法(k-means method)k-物件法物件法(k-medoids method)反覆自我組織分析
11、技術反覆自我組織分析技術(Iterative Self-Organ-izing Data Analysis Technique,ISODATA)19 k-平均法平均法(k-means method)k-物件法物件法(k-medoids method)反覆自我組織分析技術反覆自我組織分析技術(Iterative Self-Organ-izing Data Analysis Technique,ISODATA)20k-平均法平均法(1)k-平均法的概念平均法的概念k-平均法使用群集中的質量中心群集中的質量中心(mean)作為群集中心作為群集中心,因此上述之距離總偏移值可以為:其中x表示一資料點,m
12、i表示群集Si的質量中心,|Si|表示群集Si中所涵蓋之資料點數量k-平均法除了一開始需指定k個資料點當作群集之群中心外,其它回合都將產生新的群集中心點除了尤拉距離計算公式外,也可以利用其他相似度計算公式將資料點歸屬到最接近的群集當中 21k-平均法平均法(2)k-平均法的運作過程平均法的運作過程輸入:一資料集合以及使用者定義之群集數量k輸出:k個互不交集的群集步驟 1:隨機從資料集合中選擇任k個資料點當作起始k群的群集中心步驟 2:利用相似度計算公式,將資料點分別歸屬到距其最近之群集中心所屬的群集,形成k個群集。步驟 3:利用各群集中所包含的資料點,重新計算各群集之群集中心點步驟 4:假如由
13、步驟3所得到各群之群集中心與之前所計算之群集中心相同,則表示分群結果已穩定並結束此處理程序並輸出各群結果,否則回到步驟2繼續執行 22k-平均法平均法(3)k=323k-平均法平均法(4)24k-平均法平均法(5)k-平均法在平均法在概念與實作上相當的簡單概念與實作上相當的簡單,且在,且在處理大量資料時相當有擴充性處理大量資料時相當有擴充性(scalable)且且有效率有效率,但是卻也存在一些缺點,但是卻也存在一些缺點無法處理類別性資料維度無法處理類別性資料維度容易受雜訊與偏移值影響其群集中心容易受雜訊與偏移值影響其群集中心 起始群集中心選擇上的影響起始群集中心選擇上的影響群集數量決定上的困難
14、群集數量決定上的困難 25k-平均法平均法(6)無法處理類別性資料維度無法處理類別性資料維度由於k-平均值法以群集中的質量中心當作群集中心,對於類別性資料維度所描述之資料集合而言,並無法求得群集的質量中心26k-平均法平均法(7)容易受雜訊與偏移值影響其群集中心容易受雜訊與偏移值影響其群集中心 27k-平均法平均法(8)起始群集中心選擇上的影響起始群集中心選擇上的影響 28k-平均法平均法(9)群集數量決定上的困難群集數量決定上的困難29 k-平均法平均法(k-means method)k-物件法物件法(k-medoids method)反覆自我組織分析技術反覆自我組織分析技術(Iterati
15、ve Self-Organ-izing Data Analysis Technique,ISODATA)30k-物件法物件法(1)k-物件法的概念物件法的概念改善k-平均法因質量中心所造成無法處理類別性資料和容易受偏移值影響的問題k-物件法則使用位於每一群中最中心的資料點當每一群中最中心的資料點當作該群集中心作該群集中心k-物件法在運作上與k-平均法相似,最大的不同最大的不同是每回合最多只改變一個群集中心,且此變動必是每回合最多只改變一個群集中心,且此變動必須是能使準則函數值須是能使準則函數值E下降下降分割環繞物件法分割環繞物件法(Partitioning Around Medoids,PAM
16、)31k-物件法物件法(2)分割環繞物件法分割環繞物件法(PAM)的運作過程的運作過程輸入:一資料集合以及使用者定義之群集數量k輸出:k個互不交集的群集步驟 1:隨機從資料集合選擇任k個資料點當作起始k群的中心點步驟 2:利用相似度計算公式,將資料點分別歸屬到距其最近之群集中心,形成k個群集步驟 3:由資料集合中任選一非群集中心之資料點,並取代任一選取之群集中心,並計算距離總偏移值E步驟 4:假如取代後所求得之距離總偏移值E下降,取代就成立,同時回到步驟2展開下一個群集中心取代的動作步驟 5:如果所有非群集中心之資料點都無法取代已存在之群集中心,則結束此處理程序並輸出各群結果 32k-物件法物
17、件法(3)k=333 k-平均法平均法(k-means method)k-物件法物件法(k-medoids method)反覆自我組織分析技術反覆自我組織分析技術(Iterative Self-Organ-izing Data Analysis Technique,ISODATA)34ISODATA(1)ISODATA的概念的概念改善k-平均法對於起始群集中心起始群集中心和群集數量群集數量這兩個問題針對初步分群後的結果,透過使用者所設定的門檻值,再進行合併群集或分裂群集的補救動作假如某一群集中的資料點分佈過於分散,使得群集變異值(variance)大於使用者所設定的門檻值,則將對此群集進行分裂
18、成兩個群集的動作假如兩個群集彼此相當接近,使得兩群集之群集中心之距離小於使用者所給定之另一門檻值,則將其合併成一個群集 35ISODATA(2)ISODATA的運作過程的運作過程輸入:一資料集合、使用者定義之起始群集數量k、群集分裂門檻值ts、群集合併門檻值tm、群集資料點數量門檻值tn輸出:c個互不交集的群集(c可能不等於k)步驟 1:隨機從資料集合中選擇任k個資料點當作起始中心點。步驟 2:利用相似度計算公式,將資料點分別歸屬到距其最近之群集中心所屬的群集,形成k個群集步驟 3:摒除資料點數量小於tn的群集,資料點數量小於tn的群集可以視為偏移值;並重新計算其他保留下來之群集的群集中心步驟
19、 4:假如某一群集中的資料點分佈過於分散,使得群集變異值大於ts且群集內資料點數量大於(2*tn),則將此群集分裂成兩個群集步驟 5:假如兩個群集彼此相當接近,使得兩群集之群集中心之距離小於tm,則將其合併成一個群集步驟 6:重新計算分裂或合併所形成之群集的群集中心,並回到步驟2繼續處理;如果群集中心不再變動,表示分群結果已穩定,則結束此處理程序並輸出各群結果36ISODATA(3)起始起始k=3 37非分割式分群法非分割式分群法(1)分割式分群法對於自然形狀的群集與任意大分割式分群法對於自然形狀的群集與任意大小的群集的困難小的群集的困難38非分割式分群法非分割式分群法(2)階層式分群法階層式
20、分群法(hierarchical method)密集度為導向的分群法密集度為導向的分群法(density-based algorithm)39 階層式分群法階層式分群法(hierarchical method)密集度為導向的分群法密集度為導向的分群法(density-based algorithm)40階層式分群法階層式分群法(1)概念概念將所要處理之資料集合的資料點,利用聚合或分裂的方式,將彼此相似度高的較小群集合併成較大的群集,或者將較大的群集進行分離最後利用樹狀結構圖(dendrogram)來表示群集間彼此關係利用所產生之樹狀結構,可以彈性地依據使用者不同的需求,對資料集合產生不同的群集
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 群集分析 Cluster Analysis79017 群集 分析 Cluster Analysis 79017
限制150内