资料群聚性之研究.doc

資料群聚性之研究 指導教授: 陳彥良博士 撰寫人: 許昌齡 問題的說明與定義 群聚(clustering)是把有形或抽象的物件歸類到類似物件的類別的過程；將類似物件集合成同群，不同群物件的集合不相似，群聚與分類最大不同是，群聚不預先知道類別標籤，而把資料歸類成新類別[Han 2000]。例如它可透過數學方法來尋找空間物件的相似性，而分析最終目的是將資料進行分類的工作。 群聚方法的典型需求如下[Han 2000]: 需要極少領域知識去決定輸入參數。 有處理不同型態屬性的能力。 高維度。 發現任何形狀群聚。 處理雜值的能力。 延展性:有效率地處理大型資料庫。 可解釋性:透過這模型所能了解和洞察的水準。 限制基礎(constraint-based)群聚。 它有那些的應用 群聚法廣泛地應用在許多領域，例如模式識別，資料分析，和圖像處理。例如市場分析領域，分群基於顧客購買模式 [Han 2000]。 目前的研究現況，有那些議題已經被討論了，結果如何 目前的研究依方法分類有下列五種，茲探討如下: 分割方法(Partitioning) 此種為亦稱非層次化方法，目標通常是將資料分割到類似小組裡，創造分群的集合。K-means[MacQueen67]企圖把一套資料分成子集， 因此在給定的子集之內指向在對其他子集的成員顯著地不同時對彼此有一定程度的相似之處。這樣的子集通常叫作一分群，它優點是很快速。 K-means的步驟由使用者設定要找多少個群組，設要找 K 個群組在資料庫中以亂數找出K個點來當作初始的質心，驗證這K個點是否為最後之質心，如果是則完成，如果否則繼續尋找，直到都符合為止。 k-medoids [Kaufman90]在處理noise 及 outlier較k-means健全。k-mode [Huang98]擴展k-means透過使用對於categorical object簡單相匹配不相似性測量。K-prototypes[Huang98]整合K-means 及k-modes 能針對numeric及cate-gorical值作群聚。 CLARANS(Clustering Large Applications Based upon Randomized Search) [Ng94]起源於兩演算法，PAM(Partitioning Around Medoids)及CLARA(Clust-ering Large Application)，CLARANS 的缺點是被群聚的物體都存在主記憶體中，因此計算二分群間總距離是昂貴的。Easter et al. [Ester95]整合R* tree[Bradly98]去改善CLARANS的效能。 階層方法(Hierarchical) 涉及將資料組織到大群組裡， 大群組裡含有更小的群組並且依此類推，此種群聚過程稱之。以歐式距離(Euclidean distance)計算相似度，方法分成凝聚法(agglomerative)為bottom up及分散法(divise)為top down。 BIRCH(Balanced Iterative Reducing and Clustering) [Zhang 96]提出Clustering Feature(CF) 及 CF 樹概念，CF代表子分群， 動態建一平衡壓縮的CF樹然後對葉節點群聚，焦點在以代表物體減少考慮的物體的數目，集中於有關分群和一分群擁有貢獻物體可減短查詢。CF樹與CLARANS合用有不錯的效能。 傳統群聚法最喜歡球狀和類似的分群尺寸，或對於outliers易破碎。CURE [Guha 98]能處理非球形的形狀和變化尺寸，對於outliers較健全，它不處理categorical屬性，忽視兩不同分群物件間的聚集(aggregate)互連的資訊。而ROCK[Guha 99] 處理categorical屬性，基於互連度而合併兩分群，當強調互連時，忽視兩不同分群的相似資訊。Chameleon[Karypis99]使用動態模式，主要改善CURE及ROCK的上述缺點。 密度基礎方法(density-based) DBSCAN[Ester96]它將含有雜訊之空間資料，選出高密度區域為任何形狀之分群。DBSCAN交給使用者從已發現可接受之分群中去決定參數，這些參數常以經驗(或觀察)為依據，因此很難去決定，為了解決此問題Optics[Ankerst99]計算一個密度基礎的分群順序，它擴充DBSCAN，根據此順序自動去處理參數。Optics結構與DBSCAN相等，時間複雜度一樣。DENCLUE[Hinneburg98]將資料存到cell中成樹狀存取結構較 DBSCAN快速。 格子基礎方法(Grid-based) STING[Wang97]探索存在格子cell的統計資訊，其缺