A Cluster Validity Indexing Method Based on Entropy for Solving Cluster Overlapping Problem

Data clustering technique can be used in many fields, such as data mining, statistical data analysis, image analysis, pattern recognition and so on. A good clustering can get the benefits of data compression and computational reduction; however, it is unknown about how many clusters that a data set should be partitioned. Having a good guess for an initial number of clusters is highly desired for clustering. The way to find the optimal number of clusters is called cluster validity. In this paper, we propose a new cluster validity indexing method which tries to solve the cluster overlap problem. First, The Fuzzy C-Means algorithm is used to get the necessary information for calculating the validity index. Second, the weight of separation vague on the overlapping part of clusters is increased according to our entropy-based algorithm. Our approach can help increasing the accurate rate of validity index. To demonstrate the effectiveness of our proposed validity index method, we conducted several experiments and compared our method with other cluster validity indices. Experimental results showed that our method is superior to all other methods.資料分群技術可以應用於多種領域之中，例如資料挖掘、統計資料分析、影像分析、圖形辨識等。良好的分群可以達到降低相關應用程式之計算量的好處，但是當拿到一筆未知的資料時往往不會知道它應該被分成幾群，而擁有好的初始分群數則是做好分群的必要條件。分群指標法可以幫助我們找出正確的分群數。本論文提出一個新的分群指標法 並嘗試解決舊有的方法常遇到的群組重疊問題。我們的方法使用 Fuzzy C-means 演算法從資料組之中得到計算分群指標的初步必要資訊，再使用我們所提出的基於熵度的分群指標演算法，增加發生重疊部分的分離度的權重，藉以提高分群指標的正確度。為了驗證方法的正確度，我們的分群指標法與數個傳統上常用的分群指標法進行比較，實驗樣本包含了自製的數據資料組。結果證明，在處理群組重疊的問題上，我們的方法擁有較高的正確性。摘要 ....................................................... i Abstract ...................................................... ii 目錄 ......................................................iii 圖目錄 ...................................................... v 表目錄...................................................... vi 第一章 緒論......................................................1 1.1 動機、背景與研究目標...................................................... 1 1.2 論文架構 ...................................................... 2 第二章 相關文獻...................................................... 3 2.1 資料分群的相關研究...................................................... 3 2.2 現有的分群指標方法...................................................... 4 2.2.1 Bezdek's Methods ...................................................... 4 2.2.2 Xie and Beni's Method ...................................................... 5 2.2.3 Fukuyama and Sugeno's Method ......................................................5 2.2.4 Kim's Method ...................................................... 6 2.2.5 Babak's Method ...................................................... 7 第三章 新的數據資料的分群方法...................................................... 9 3.1 利用 Fuzzy c means 來進行資料分群................................................ 9 3.2 基於熵度的分群指標法...................................................... 10 3.2.1 緊湊度(Compactness) ...................................................... 10 3.2.2 分離度 Separation ...................................................... 11 3.2.3 改良後的分群指標法...................................................... 14 第四章 實驗結果與分析...................................................... 16 4.1 效能評估方法...................................................... 16 4.2 實驗結果和其他方法的比較...................................................... 17 第五章 結論與未來展望...................................................... 27 參考文獻...................................................... 2