資源描述:
《資料群聚性之研究》由會員上傳分享,免費在線閱讀,更多相關內容在工程資料-天天文庫。
1、資料群聚性之硏究抬導教授:陳彥良博士撰寫人:許昌齡問題的說明與定義群聚(clustering)是把有形或抽象的物件歸類到類似物件的類別的過程;將類似物件集合成同群,不同群物件的集合不相似,群聚與分類最大不同是'群聚不預先知道類別標籤,而把資料歸類成新類別[Han2000]。例如它可透過數學方法來尋找空間物件的相似性,而分析最終戸的是將資料進行分類的工作。群聚方法的典型需求如下[Han2000]:?需要極少領域知識去決定輸入參數。有處理不同型態(tài)屬性的能力。?高維度。?發(fā)現任何形狀群聚。?處理雜値的能力。?延展性:有效率地處理大型
2、資料庫。?可解釋性:透過這模型所能了解和洞察的水準。?限制基礎(constraint-based)群聚。它有那些的應用群聚法廣泛地應用在許多領域,例如模式識別,資料分析,和圖像處理。例如市場分析領域'分群基於顧客購買模式[Han2000]。目前的硏究現況'有那些議丿已經被討論了>結果如何目前的硏究依方法分類有下列五種,茲探討如下:分割方法(Partitioning)此種爲亦稱非層次化方法‘目標通常是將資料分割到類似小組裡,創(chuàng)造分群的集合°K-means[MacQueen67]企圖把一套資料分成子集,因此在給定的子集之內指向在對
3、其他子集的成員顯著地不同時對彼此有一定程度的相似之處。這樣的子集通常叫作一分群,它優(yōu)點是很快速。K-means的步驟由使用者設定要找多少個群組,設要找K個群組在資料庫中以亂數找出K個點來當作初始的質心,驗證這K個點是否爲最後之質心,如果是則完成,如果否則繼續(xù)尋找,直到都符合爲止。k-medoids[Kaufman90]在處理noise及outlier較k?means健全。k-mode[Huang98]擴展k-means透過使用對於categoricalobject簡單相匹配不相似性測量。K-prototypes[Huang98
4、]整合K-means及k-modes能針對numeric及cate-gorical値作群聚°CLARANS(ClusteringLargeApplicationsBaseduponRandomizedSearch)[Ng94]起源於兩演算法,PAM(PartitioningAroundMedoids)及CLARA(Clust-eringLargeApplication),CLARANS的缺點是被群聚的物體都存在主記憶體中,因此計算二分群間總距離是昂貴的。Easteretal.[Ester95]整合R*tree[Bradly98
5、]去改善CLARANS的效能。階層方法(Hierarchical)涉及將資料組織到大群組裡,大群組裡含有更小的群組並.冃依此類推,此種群聚過程稱之。以歐式距離(Euclideandistance)計算相似度,方法分成凝聚法(agglomerative)爲bottomup及分散法(divise)爲topdown°BIRCH(BalancedIterativeReducingandClustering)[Zhang96]提出ClusteringFeature(CF)及CF樹槪念,CF代表子分群,動態(tài)建一平衡壓縮的CF樹然後對葉節(jié)點
6、群聚,焦點在以代表物體減少考慮的物體的數目,集中於有關分群和一分群擁有貢獻物體可減短查詢。CF樹與CLARANS合用有不錯的效能。傳統(tǒng)群聚法最喜歡球狀和類似的分群尺寸,或對於out1iers易破碎。CURE[Guha98]能處理非球形的形狀和變化尺寸'對於outliers較健全,它不處理categorical屬性,忽視兩不同分群物件間的聚集(aggregate)互連的資訊。jfijR0CK[Guha99]處理categorical屬性,基於互連度而合倂兩分群,當強調互連時,忽視兩不同分群的相似資訊。Chameleon[Kary
7、pis99]使用動態(tài)模式,主要改善CURE及ROCK的上述缺點。密度基礎方法(density-based)DBSCAN[Ester96]它將含有雜訊之空間資料,選出高密度區(qū)域爲任何形狀之分群。DBSCAN交給使用者從已發(fā)現可接受之分群中去決定參數,這些參數常以經驗(或觀察)爲依據,因此很難去決定,爲了解決此問題Optics[Ankerst99]計算一個密度基礎的分群順序,它擴充DBSCAN,根據此順序自動去處理參數。Optics結構與DBSCAN相等,時間複雜度一樣。DENCLUE[Hinneburg98]將資料存到cel1中
8、成樹狀存取結構較DBSCAN快速。格子基礎方法(Grid-based)STING[Wang97]探索存在格子cell的統(tǒng)計資訊,其缺點是分群形狀其邊不是水平就是垂直,此點儘管有快速時問'但會有損及其品質及正確率。WaveCluster[Sheikholeslami98]採密度