跳到主要內容

臺灣博碩士論文加值系統

(44.222.64.76) 您好!臺灣時間:2024/06/15 06:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李諺泯
研究生(外文):Yan-Min Lee
論文名稱:修改K-means演算法應用在距離矩陣為基礎的分類
論文名稱(外文):A Modify K-means algorithm for distance matrix based clustering
指導教授:阮議聰
指導教授(外文):Yee-Tsong Juan
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:117
中文關鍵詞:K均值演算法距離矩陣叢集
外文關鍵詞:clusteringdistance matrixK-means
相關次數:
  • 被引用被引用:6
  • 點閱點閱:545
  • 評分評分:
  • 下載下載:70
  • 收藏至我的研究室書目清單書目收藏:1
中文摘要
在這篇論文中我們提出一個Modify K-means的方法應用在比對後的距離矩陣資料上。一般來說我們常見的叢集演算法大致上分為Partitioning與Non- partitioning(Hierarchical)兩種方式去做資料的分類。我們使用Partition的方式中最廣為人知的演算法K-means,修改並讓其適用於距離矩陣的資料,並比較兩者之間的差異。在處理資料方面,能對距離矩陣為基礎的資料作分類;在執行效率上,除了收斂的次數比K-means來的少外,利用儲存第一次計算的花費來修正每一次所需計算的資料量,以至於在執行的效率上能趨近K-means的速度甚至能比K-means優越。而能對多種資料作有效分析的演算法,如non-Partitioning方式中的凝聚法(agglomerative method),雖然能處理多樣化的資料型態,可是卻沒有顯示出叢集的代表點,且資料一但分配過亦不能再重新分配也流於時間的複雜而不具價值。因此我們將所提出的方法延伸,使分割出來的叢集也能呈現出階層式的表示,方便使用者觀察分割完成後物件的差異來加強資料的實用性。在此我們發現,Hierarchical這方法所呈現的階層圖是所有物件的結合差異,但是當資料量大時,我們並不需要將所有物件的差異都得知後再去做處理,只需得到所欲分割的叢集差異即可。基於此種理由,我們利用Partition的方式先對資料作分割,再將分割結果以Hierarchical方式求算叢集間的差異來達到上述的目的。最後將此兩種方法應用在C程式比對後的對稱矩陣實例上。
Abstract
In this paper we propose a Modify K-means method for distance matrix based clustering. Usually, clustering methods are classified into two categories of Partitioning and Hierarchical. A well-known method of Partitioning method is K-means algorithm. This method can’t deal with the distance matrix based data set, so we modify this method for distance matrix based data and compare the difference between these two methods. Convergence frequency in our method is much lower than K- means method and we improve the time complexity of our method in each iteration, so that the efficiency of our method is close to K-means, even can be better. Although the Hierarchical methods can deal with the distance matrix based data, it does not show the feature of clusters and the time complexity is too high. We extend our method to display the result with Hierarchical diagram, user can observe the difference of the clusters. And then we propose another method to combine Partitioning with Hierarchical method. First, we use the Partitioning method to clustering the data. Second, we deal the result of first phase with Hierarchical method. At last we apply these two methods to distance matrix data, which represent the difference of C program codes.
目錄:
中文摘要 I
Abstract II
謝誌 III
目錄: IV
圖形目錄: VI
表格目錄: IX
第一章 研究背景與動機: 1
1-1. 廣泛的介紹clustering data的背景 1
1-2. 動機 1
1-3. 論文章節概要 2
第二章. 相關研究 3
2-1. Partitioning Algorithms 3
2-2. Hierarchical Algorithms 7
2-3. Density-based Algorithms 9
第三章. Modify K-means algorithm 10
第四章. Modify K-means comparison with K-means and Hierarchical 14
4-1. Modify K-means與K-means的比較: 14
4-1-1. 中心點分佈的差異性 14
4-1-2. 代表點與虛擬點對分離物的敏感度 17
4-1-3. cost function的收斂 19
4-1-4. time complexity and space complexity 22
4-2. Modify K-means combined with K-means in High dimension 25
4-3. Modify K-means VS Hierarchical Agglomerative clustering 27
4-3-1. 叢集分割的差異 27
4-3-2. time complexity 35
4-3-3. 優缺點的比較 38
4-4. Dendrogram of Modify K-means 39
4-4-1. group形成時的最大、最小或平均的差異性值 39
4-4-2. group與group之間的差異 40
4-4-3. group與group結合的順序 44
4-5. 利用min base、max base、average base以分割的方式達到Hierarchical clustering的效果 48
第五章. 實驗結果 55
5-1. 應用在C程式比對後的分類 55
5-1-1. 資料來源的描述: 55
5-1-2. 實驗結果: 55
5-2應用在實例資料上[20] 90
5-2-1 實驗結果 91
第六章. 結論與未來展望 105
6-1. 總結 105
6-2. 未來展望 105
參考書目 106

圖形目錄:
圖 1. 分配到最近的中心點 4
圖 2. 計算新中心點 5
圖 3. 停止更新的中心點 5
圖 4. K-MEANS中心點分佈 15
圖 5. MODIFY K-MEANS中心點分佈 16
圖 6. 分離物對K-MEANS與MODIFY K-MEANS的影響 18
圖 7. 資料量變動兩者收斂的比較 20
圖 8. 資料量變動兩者時間的比較 20
圖 9. 叢集變動兩者收斂的比較 21
圖 10. 叢集變動兩者時間的比較 21
圖 11. 1000~5000個RANDOM DATA POINTS平均執行次數 24
圖 12. 1000~5000個RANDOM DATA POINTS平均時間 24
圖 13. 維度對K-MEANS的影響 26
圖 14. SINGLE-LINKAGE METHOD分成兩個叢集 28
圖 15. SINGLE-LINKAGE CHAIN EFFECT 29
圖 16. COMPLETE-LINKAGE METHOD IN CHAIN EFFECT 30
圖 17. AVERAGE-LINKAGE METHOD IN CHAIN EFFECT 30
圖 18. 使用SINGLE-LINKAGE將DATA2.分類 31
圖 19. 使用COMPLETE-LINKAGE將DATA2.分類 32
圖 20. 使用AVERAGE-LINKAGE將DATA2.分類 32
圖 21. 利用MODIFY K-MEANS將圖14.平面上的點分割成兩個叢集 33
圖 22. 利用MODIFY K-MEANS將圖15的平面上資料分割成三個叢集 34
圖 23. HIERARCHICAL,MODIFY K-MEANS在相同條件下所得的平均時間 37
圖 24. 叢集結合的差異性階層圖I 43
圖 25. 叢集結合的差異性階層圖II 46
圖 26. MIN BASE處理同心圓 50
圖 27. 利用MIN BASE方式去對圖14.的資料分割成兩個叢集的結果。 51
圖 28. 利用MAX BASE方式去對圖14.的資料分割成兩個叢集的結果。 51
圖 29. 利用MAX BASE方式去對圖形中有NOISE CHAIN的資料作分割 52
圖 30. 利用AVERAGE BASE方式去對圖14.的資料分割成兩個叢集的結果。 52
圖 31. 利用AVERAGE BASE方式去對圖形中有NOISE CHAIN的資料作分割 53
圖 32 資料量變動下,結合法與階層法的時間比較 53
圖 33 變動叢集數目下,結合法時間隨著叢集增加而上升 54
圖 34. HOMEWORK 1. SINGLE-LINKAGE, MIN BASE分割10個叢集 56
圖 35. HOMEWORK 1. COMPLETE-LINKAGE, MAX BASE分割10個叢集 57
圖 36. HOMEWORK 1. AVERAGE-LINKAGE, AVERAGE BASE分割10個叢集 58
圖 37. HOMEWORK 1. 使用MODIFY K-MEANS分割10個叢集 59
圖 38. HOMEWORK 2. SINGLE-LINKAGE, MIN BASE分割30個叢集, 61
圖 39. HOMEWORK 2. COMPLETE-LINKAGE, MAX BASE分割30個叢集 63
圖 40. HOMEWORK 2. AVERAGE-LINKAGE, AVERAGE BASE分割30個叢集 66
圖 41. HOMEWORK 2. 使用MODIFY K-MEANS分割30個叢集 68
圖 42. HOMEWORK 3. SINGLE-LINKAGE, MIN BASE分割30個叢集 70
圖 43. HOMEWORK 3. COMPLETE-LINKAGE, MAX BASE分割30個叢集 73
圖 44. HOMEWORK 3. AVERAGE-LINKAGE, AVERAGE BASE分割30個叢集 75
圖 45. HOMEWORK 3.使用MODIFY K-MEANS分割30個叢集 77
圖 46. HOMEWORK 4. SINGLE-LINKAGE, MIN BASE分割10個叢集 78
圖 47. HOMEWORK 4. COMPLETE-LINKAGE,MAX BASE分割10個叢集 79
圖 48. HOMEWORK 4. AVERAGE-LINKAGE, AVERAGE BASE分割10個叢集 80
圖 49. HOMEWORK 4. 使用MODIFY K-MEANS分割10個叢集 81
圖 50. HOMEWORK 5. SINGLE-LINKAGE, MIN BASE分割30個叢集 83
圖 51. HOMEWORK 5. COMPLETE-LINKAGE, MAX BASE分割30個叢集 84
圖 52. HOMEWORK 5. AVERAGE-LINKAGE, AVERAGE BASE分割30個叢集 86
圖 53. HOMEWORK 5. 使用MODIFY K-MEANS分割30個叢集 88
圖 54. 使用MIN BASE將CYTOCHROMES C的資料分為10類 91
圖 55. 使用MAX BASE將CYTOCHROMES C的資料分為10類. 92
圖 56. 使用AVERAGE BASE將CYTOCHROMES C的資料分為10類 93
圖 57. 使用MODIFY K-MEANS將CYTOCHROMES C的資料分為10類 94
圖 58. 使用MIN BASE將植物的資料分為10類 95
圖 59. 使用MAX BASE將植物的資料分為10類. 96
圖 60. 使用AVERAGE BASE將植物的資料分為10類 97
圖 61. 使用MODIFY K-MEANS將植物的資料分為10類 98
圖 62. 使用MIN BASE將果蠅的資料分為15類 100
圖 63. 使用MAX BASE將果蠅的資料分為15類 100
圖 64. 使用AVERAGE BASE將果蠅的資料分為15類 101
圖 65. 使用MODIFY K-MEANS將果蠅的資料分為15類 102
圖 66. 使用MIN BASE將HUMAN MITOCHNDRIAL的資料分類 103
圖 67. 使用MAX BASE將HUMAN MITOCHNDRIAL的資料分類 103
圖 68. 使用AVERAGE BASE將HUMAN MITOCHNDRIAL的資料分類 104
圖 69. 使用MODIFY K-MEANS方法將HUMAN MITOCHNDRIAL的資料分類 104

表格目錄:
表格 1 .K-MEANS,OLD AND NEW MODIFY K-MEANS的平均執行時間比較 23
表格 2 .K-MEANS,OLD AND NEW MODIFY K-MEANS的平均執行次數比較 23
表格 3 HIERARCHICAL與其他方法的平均執行時間比較 36
表格 4. K-MEANS,OLD AND NEW MODIFY K-MEANS的平均執行次數比較 36
表格 5. MIN BASE IN HOMEWORK 2.叢集與成員的對照表 61
表格 6. MAX BASE IN HOMEWORK 2.叢集與成員的對照表 64
表格 7. AVERAGE BASE IN HOMEWORK 2.叢集與成員的對照表 66
表格 8. MIN BASE IN HOMEWORK 3.叢集與成員的對照表 70
表格 9. MAX BASE IN HOMEWORK 3.叢集與成員的對照表 73
表格10. AVERAGE BASE IN HOMEWORK 3.叢集與成員的對照表 75
參考書目
[1] J.R. JANG,C.T. SUN and E. MIZUTANI, Neuro-Fuzzy and Soft Computing. Prentice Hall, 1997.
[2] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.:Prentice Hall, 1988.
[3] F. Hoppner , F. Klawomn ,R. Kruse and T. Runkler , Fuzzy Cluster Analysis. John Wiley & Sons Ltd, Baffins Lane, Chichester, West Sussex, England, 1999
[4] Jain, A.K., Murty M.N., and Flynn P.J. (1999):“Data Clustering: A Review”, ACM Computing Surveys, Vol 31, No. 3, pp.264-323 , September 1999
[5] Richard J. Hathaway, Member, IEEE, James C. Bezdek, Fellow, IEEE, and Yingkang Hu ,“Generalized Fuzzy c-means clustering strategies Using Lp Norm Distance,” IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 8, NO. 5,pp.576-582, OCTOBER 2000
[6] Hong Yan, Senior Member, IEEE ,“Fuzzy curve-Tracing Algorithm, ” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 31, NO. 5,pp.768-780, OCTOBER 2001
[7] Bezdek, J.C. and R.J. Hathaway ,”Numerical convergence and Interpretation of the Fuzzy c-shells clustering algorithm,” IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL.3, NO. 5,pp.787-793, SEPTEMEMBER,1992,
[8] A.B. Geva ,”Hierarchical Unsupervised Fuzzy clustering,“ IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 7, NO. 6,pp.723-733 ,DECEMBER 1999
[9] L.O. Hall, I. Burak ¨ Ozyurt, and J.C. Bezdek, Fellow, IEEE ,
”Clustering with a Genetically Optimized Approach,” IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 3, NO. 2,pp.103-112, JULY 1999
[10] K. Krishna and M. Narasimha Murty ,“Genetic K-Means Algorithm,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 29, NO. 3,pp.433-439, JUNE 1999

[11] “An Efficient k-Means Clustering Algorithm : Analysis and Implementation,” IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 24, NO. 7,pp.881-892, JULY 2002
[12] K.C. GOWDA AND G. KRISHNA , “Disaggregative Clustering Using the Concept of Mutual Nearest Neighborhood,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS, VOL. SMC-8,NO. 12,DECEMBER 1978
[13] S.P. Smith, “Threshold Validity for Mutual Neighborhood Clustering,” IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 15, NO.1 ,pp.89-92, JANUARY 1993
[14] C.J. Veenman , Marcel J.T. Reinders, and Eric Backer ,“A Maximum Variance Cluster Algorithm,” IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 24, NO. 9,pp.1273-1280, SEPTEMBER 2002
[15] Mu-Chun Su and Chien-Hsing Chou , “A Modified Version of the K-Means Algorithm with a Distance Based on Cluster Symmetry,” IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 23, NO. 6,pp.674-680, JULY 2001
[16] Raghu Krishnapuram and Jongwoo Kim, “Clustering Algorithms Based on Volume Criteria,” IEEE TRANSACTIONS ON FUZZY SYSTEMS, VOL. 8, NO. 2,pp.228-236, APRIL 2000
[17] Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest “Introduction to algorithms ” , 1998
[18] KURITA, T. 1991. ,“An efficient agglomerative clustering algorithm using a heap. “Pattern Recogn, Vol. 24, 3 (1991), 205–209.
[19] SungYoung Jung, and Taek-Soo Kim ,“An Agglomerative Hierarchical Clustering using Partial Maximum Array and Incremental Similarity Computation Method, “ IEEE International Conference on Data Mining, 2001
[20]實例來源 http://www.csie.ncnu.edu.tw/~rctlee/course/biology/new_page_1.html

[21] L. Kaufman and P. J. Rousseeuw, Finding Groups in Data, An Itroduction to Cluster Analysis, JohnWiley & Sons, Brussels, Belgium, 1990.
[21] L. Kaufman and P. J. Rousseeuw, Finding Groups in Data, An Itroduction to Cluster Analysis, JohnWiley & Sons, Brussels, Belgium, 1990.
[22] Huang, Zhexue; "Extensions to the K-Means Algorithm For Clustering large Data sets with Categorical values", Data mining and knowledge discovery,2:283-304, 1998.
[23] BALL, G. H. AND HALL, D. J. ISODATA, a novel method of data analysis and classification. Tech. Rep.. Stanford University, Stanford, CA. 1965.
[24] Kirkpatrick, S , Gelatt, C.D., Vecchi, M.P. “Optimization by Simulated Annealing. Science,” vol 220, No. 4598, pp671-680,1983.
[25] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu , “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” Published in Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96)
[26] M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. “Optics: Ordering points to identify the clustering structure,” Proc. ACM SIGMOD’99 Int. Conf. on Management of Data, Philadelphia PA, 1999.
[27] A. Hinneburg and D. A. Keim, “An efficient approach to Clustering in Large multimedia Databases with Noise.” KDD pages 58-65, 1998.
[28] Guha, R. Rastogi, and K. Shim. “Cure: An efficient clustering algorithm for large databases.” SIGMOD'98.
[29] KARYPIS, GEORGE; HAN, EUI-HONG; KUMAR, VIPIN, "CHAMELEON: HIERARCHICAL CLUSTERING USING DYNAMIC MODELING," COMPUTER , VOLUME: 32, PP. 68-75, AUG 1999.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top