資料群聚性之研究

《資料群聚性之研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、資料群聚性之研究指導(dǎo)教授：陳彥良博士撰寫人：許昌齡問題的說(shuō)明與定義群聚(clustering)是把有形或抽象的物件歸類到類似物件的類別的過程；將類似物件集合成同群，不同群物件的集合不相似，群聚與分類最大不同是，群聚不預(yù)先知道類別標(biāo)籤，而把資料歸類成新類別［Han2000］。例如它可透過數(shù)學(xué)方法來(lái)尋找空間物件的相似性，而分析最終目的是將資料進(jìn)行分類的工作。群聚方法的典型需求如下［Hen2000］:?需要極少領(lǐng)域知識(shí)去決定輸入?yún)?shù)。有處理不同型態(tài)?高維度。?發(fā)現(xiàn)任何形狀群聚。?處理雜值的能力。?延展性:有效率地處理大型資料庫(kù)。?可解釋性:透過這模型所能了

2、解和洞察的水準(zhǔn)。?限制W(constraint-based)群聚。它有那些的應(yīng)用群聚法廣泛地應(yīng)用在許多領(lǐng)域，例如模式識(shí)別，資料分析，和圖像處理。例如市場(chǎng)分析領(lǐng)域'分群基於顧客購(gòu)買模式［Han2000］。目前的研究現(xiàn)況，有那些議題已經(jīng)被討論了，結(jié)果如何目前的研究依方法分類有下列五種，茲探討如下：分割方法(Partitioning)此種為亦稱非層次化方法‘目標(biāo)通常是將資料分割到類似小組裡，創(chuàng)造分群的集合°K-means[MacQueen67]企圖把一套資料分成子集，因此在給定的子集之內(nèi)指向在對(duì)其他子集的成員顯著地不同時(shí)對(duì)彼此有一定程度的相似之處。這樣的子

3、集通常叫作一分群，它優(yōu)點(diǎn)是很快速。K-means的步驟由使用者設(shè)定要找多少個(gè)群組，設(shè)要找K個(gè)群組在資料庫(kù)中以亂數(shù)找出K個(gè)點(diǎn)來(lái)當(dāng)作初始的質(zhì)心，驗(yàn)證這K個(gè)點(diǎn)是否為最後之質(zhì)心，如果是則完成，如果否則繼續(xù)尋找，直到都符合為止。k-medoids[Kaufman90]在處理noise及outlier較k?means健全°k-mode[Huang98]擴(kuò)展k-means透過使用對(duì)於categoricalobject簡(jiǎn)單相匹配不相似性測(cè)量。K-prototypes[Huang98]整合K?means及k-modes能針對(duì)numeric及cate-gorical值作

4、群聚°CLARANS(ClusteringLargeApplicationsBaseduponRandomizedSearch)[Ng94]起源於兩演算法，PAM(PartitioningAroundMedoids)及CLARA(Clust-eringLargeApplication)，CLARANS的缺點(diǎn)是被群聚的物體都存在主記憶體中，因此計(jì)算二分群間總距離是昂貴的。Easteretal.[Ester95]整合R*tree[Bradly98]去改善CLARANS的效能。階層方法(Hierarchical)涉及將資料組織到大群組裡，大群組裡含有更小的

5、群組並且依此類推，此種群聚過程稱之。以歐式距離(Euclideandistance)計(jì)算相似度，方法分成凝聚法(agglomerative)為bottomup及分散法(divise)為topdown°BIRCH(BalancedIterativeReducingandClustering)[Zhang96]提出ClusteringFeature(CF)及CF樹概念，CF代表子分群，動(dòng)態(tài)建一平衡壓縮的CF樹然後對(duì)葉節(jié)點(diǎn)群聚，焦點(diǎn)在以代表物體減少考慮的物體的數(shù)目，集中於有關(guān)分群和一分群擁有貢獻(xiàn)物體可減短查詢。CF樹與CLARANS合用有不錯(cuò)的效能。傳統(tǒng)群

6、聚法最喜歡球狀和類似的分群尺寸，或?qū)秓utliers易破碎。CURE[Guha98]能處理非球形的形狀和變化尺寸，對(duì)於outliers較健全，它不處理categorical屬性，忽視兩不同分群物件間的聚集(aggregate)互連的資訊。而R0CK[Guha99]處理categorical屬性，基於互連度而合併兩分群，當(dāng)強(qiáng)調(diào)互連時(shí)，忽視兩不同分群的相似資訊°Chameleon[Karypis99]使用動(dòng)態(tài)模式，主要改善CURE及ROCK的上述缺點(diǎn)。密度基礎(chǔ)方法(density-based)DBSCAN[Ester96]它將含有雜訊之空間資料，選出高

7、密度區(qū)域?yàn)槿魏涡螤钪秩?。DBSCAN交給使用者從已發(fā)現(xiàn)可接受之分群中去決定參數(shù)，這些參數(shù)常以經(jīng)驗(yàn)(或觀察)為依據(jù)，因此很難去決定，為了解決此問題Op仃cs[Ankerst99]計(jì)算一個(gè)密度基礎(chǔ)的分群順序，它擴(kuò)充DBSCAN，根據(jù)此順序自動(dòng)去處理參數(shù)。Optics結(jié)構(gòu)與DBSCAN相等，時(shí)間複雜度一樣。DENCLUE[Hinneburg98]將資料存到cell中成樹狀存取結(jié)構(gòu)較DBSCAN快速。格子基礎(chǔ)方法(Grid-based)STING[Wang97]探索存在格子cel1的統(tǒng)計(jì)資訊，其缺點(diǎn)是分群形狀其邊不是水平就是垂直，此點(diǎn)儘管有快速時(shí)間，但會(huì)有

8、損及其品質(zhì)及正確率。WaveC1uster[Sheikho1es1ami98]採(cǎi)密度及格子基礎(chǔ)方式群聚，透過