Ruby简单实现K-means聚类算法.doc

Ruby简单实现K-means聚类算法文章分类:综合技术 K-means是一个简单容易实现的聚类算法，我们以对一个图片的颜色的RGB值进行聚类为例， 实现这个算法。 K-means算法是一个EM的迭代过程： 1.随机选择k个作为聚类中心 2.E step: 对每一个点，计算它到每一个聚类中心的距离，把这个点分配到最近的聚类中心代表的 聚类中。 3.M step： 重新计算每个聚类的中心：每个聚类中心为该聚类所有点的均值。 重复23直到达到最大的迭代次数或者聚类不再发生变化。 Ruby代码 1. #!/usr/bin/ruby 2. #autor:fuliang/ 3. 4. classRGB 5. attr_accessor:r,:g,:b6. 7. definitialize(r=0,g=0,b=0) 8. r,g,b=r,g,b 9. end10. 11. def+(rgb) 12. r+=rgb.r 13. g+=rgb.g 14. b+=rgb.b 15. self16. end17. 18. def/(n) 19. r/=n 20. g/=n 21. b/=n 22. self23. end24. end25. 26. defrandom_k_centers(instances,k) 27. rand_indxes=(0.instances.size).sort_byrand0.k 28. instances.values_at(*rand_indxes) 29. end30. 31. defdistance(ins1,ins2)#采用余弦值，因为255,255,255和200,200,200颜色基本类似 32. dot_product=ins1.r*ins2.r+ins1.g*ins2.g+ins1.b*ins2.b 33. mod1=Math.sqrt(ins1.r*ins1.r+ins1.g*ins1.g+ins1.b*ins1.b) 34. mod2=Math.sqrt(ins2.r*ins2.r+ins2.g*ins2.g+ins2.b*ins2.b) 35. return1-dot_product/(mod1*mod2) 36. end37. 38. defk_means_cluster(instances,k,max_iter=100) 39. random_centers=random_k_centers(instances,k) 40. prandom_centers 41. instance_cluster_map= 42. change_count=0 43. clusters= 44. 0.upto(max_iter)do|iter_num| 45. clusters= 46. putsiterate#iter_num.47. change_count=0 48. #E-step 49. instances.eachdo|instance| 50. min_distance=1.0/0 51. min_indx=0 52. random_centers.each_with_indexdo|center,index| 53. current_distance=distance(center,instance) 54. ifmin_distancecurrent_distancethen55. min_indx=index 56. min_distance=current_distance 57. end58. end59. ifinstance_cluster_mapinstance!=min_indxthen#tracethechange 60. change_count+=1 61. instance_cluster_mapinstance=min_indx 62. end63. clustersmin_indx|= 64. clustersmin_indxinstance 65. end66. putschange_count=#change_count67. breakifchange_count.zero? 68. #M-step 69. clusters.each_with_indexdo|cluster,index| 70. center=RGB.new71. cluster.eachdo|instance| 72. center+=instance 73. end74. center/=cluster.size 75. random_centersindex=center#updatecenter 76. end77. end78. returnclusters 79. end80. 81. instances= 82. File.open(rgbs.txt).each_linedo|line| 83. line.split(/t/).eachdo|rgb| 84. r,g,b=rgb.split(/,/).collect|e|e.to_i 85. instancesRGB.new(r,g,b) 86. end87. end88. 89. clusters=k_means_cluster(instances,5,100) 90. k_candidates= 91. clusters.eachdo|cluster| 92. sum=cluster.inject(RGB.new)|sum,ins|sum+ins 93. candidate=sum/cluster.size 94. k_candidates current_distance then min_indx = index min_distance = current_distance end end if instance_cluster_mapinstance != min_indx then#trace the change change_count += 1 instance_cluster_mapinstance = min_indx end clustersmin_indx |= clustersmin_indx instance end puts change_count=#change_count break if change_count.zero? #M-step clusters.each_with_index do |cluster,index| center = RGB.new cluster.each do |instance| center += instance end center /= cluster.size random_centersindex = center # update center end end return clustersendinstances = File.open(rgbs.txt).each_line do |line| line.split(/t/).each do | rgb | r,g,b = rgb.split(/,/).collect|e| e.to_i instances RGB.new(r,g,b) endendclusters = k_means_cluster(instances,5,100)k_candidates = cl