《华人性研究》编辑部发

《《华人性研究》编辑部发》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章群集分析：基本概念與演算法©2008台灣培生教育出版(PearsonEducationTaiwan)群集分析群集分析將資料分成許多有意義或有用的群體（群集）若以有意義的群體為目標，則群集應捕捉資料的基本結構。但在一些情況下，群集分析對其他應用而言只是一個起點而已，例如資料彙總不論是針對理解性（understanding）或使用性（utility）而言，群集分析在心理學與其他社會科學、生物學、統計學、樣式辨識（patternrecognition）、資訊檢索、機器學習與資料探勘等領域上，都扮演很重要的角色為理解而分群：生物學（

2、Biology）資訊檢索（informationretrieval）天氣心理學與醫學商業為使用而分群彙總（summarization）壓縮有效地發掘最近鄰居什麼是群集分析？群集分析是根據物件的資料，以及物件之間的關係資訊為基礎來進行物件的群集群集分析的目的是要使同群內的物件彼此相似（或相關）的，且與其他群中的物件不同（不相關）當群內的相似度（或同質性）很大，且群間的差異很大時，則有較好或更具區別性的群體以不同方式對相同集合之資料點做分群不同的分群類型階層式的與分割式的：最常見的分群類型，是根據群集的集合為巢狀（nested）的或非

3、巢狀的（unnested）來區分，而在傳統的術語中則稱為階層的或分割的互斥的與重疊的與模糊的：當指派每個物件至單一群集中，圖8.1中的分群為唯一的（exclusive）。有許多情況是一個點可被合理地指定到一個以上的群集中，這種情況最好是由非互斥分群（non-exclusiveclustering）來描述。在最一般的意義中，使用重疊的或非互斥分群可用來反應一個物件會同時屬於一個以上的群體（類別）完整的與部份的：完整分群（completeclustering）將每個物件指定至一個群集中，而部份分群（partialclustering）

4、卻不是。部份分群的動機為資料集中的一些物件可能不屬於已定義清楚（well-defined）的群集，許多在資料集中的物件可被表示為雜訊（noise）、離群值（outlier）或「不有趣的背景」（uninterestingbackground）不同的群集類型分散良好的（Well-Separated）：群集是物件的集合，相較於其他不在群集中的物件，每個物件與群集中的其他物件會較接近（或很相似）。有時是使用門檻值來說明一個群中的所有物件必須彼此是夠接近的（或相似的）。只要當資料包含自然的群集（naturalclusters）且彼此是相距很

5、遠的，這個群集的理想定義會被滿足不同的群集類型以雛型為基礎的（Prototype-Based）：群集是物件的集合，其中每個物件會接近（相當相似）所屬群集之雛型。針對連續屬性資料，群集的雛型通常為質量中心（centroid），即在群集中所有點的平均值（mean）。當質量中心沒有意義時，例如當資料有類別的屬性時，則雛型通常是medoid，亦即為群中最具代表性的點不同的群集類型以圖形為基礎（Graph-Based）：若資料表示成圖形，這裡的節點為物件，而鏈結表示物件之間的連結，則群集可被定義為連結的元件（connectedcompone

6、nt）；即一群彼此相連的物件，但沒有和此群體外的物件相連不同的群集類型以密度為基礎（Density-Based）：群集為一個物件密集的區域且由低密度的區域所圍繞共享屬性（Shared-Property，概念的群集）：一般來說，我們定義群集為物件的集合且共有一些屬性，這個定義包含之前所有群集的定義；例如，在以中心為基礎的群集中的物件共享一個特性，就是它們全部與相同的質量中心點（centroid）或medoid非常接近準則（RoadMap）K-means：這是一個以雛型為主的分割式分群技術，以試圖找出使用者指定之群集個數（K），並以群

7、中心為代表凝聚式層階分群法（AgglomerativeHierarchicalClustering）：這個分群方法是指一群為緊密相關之分群技術，藉由每一點為一個單一群集開始，接著多次合併兩個最接近的群集，直到剩下包含所有群集之單一群集為止，以產生階層式分群DBSCAN：這是以密度為基礎的分群演算法，可以產生分割式分群，其分群數可由演算法自動決定，在低密度區域的點會被歸類為雜訊而被省略；因此，DBSCAN不能產生完整的分群利用二維之資料點說明不同類型的群集K-means以雛形為基礎之群集技術可建立具有一個階層之資料分割，這樣的技術有

8、一些，但最常見的兩個技術是K-means與K-medoid。K-means使用雛型的中心，通常是一群資料點的平均，且典型地被應用於連續n維度空間的物件上。K-medoid使用雛型之中心點，以一個最具代表性的點來表示一群資料點，可應用的範圍很廣，因為