发新帖

机器学习算法与Python实践之(六)二分k均值聚类

[复制链接]
1668 5
机器学习算法与Python实践之(六)二分k均值聚类




       机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习算法加深下了解,所以就想通过Python来实现几个比较常用的机器学习算法。恰好遇见这本同样定位的书籍,所以就参考这本书的过程来学习了。
       在上一个博文中,我们聊到了k-means算法。但k-means算法有个比较大的缺点就是对初始k个质心点的选取比较敏感。有人提出了一个二分k均值(bisecting k-means)算法,它的出现就是为了一定情况下解决这个问题的。也就是说它对初始的k个质心的选择不太敏感。那下面我们就来了解和实现下这个算法。

一、二分k均值(bisecting k-means)算法
       二分k均值(bisecting k-means)算法的主要思想是:首先将所有点作为一个簇,然后将该簇一分为二。之后选择能最大程度降低聚类代价函数(也就是误差平方和)的簇划分为两个簇。以此进行下去,直到簇的数目等于用户给定的数目k为止。
       以上隐含着一个原则是:因为聚类的误差平方和能够衡量聚类性能,该值越小表示数据点月接近于它们的质心,聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次的划分,因为误差平方和越大,表示该簇聚类越不好,越有可能是多个簇被当成一个簇了,所以我们首先需要对这个簇进行划分。
       二分k均值算法的伪代码如下:
***************************************************************
将所有数据点看成一个簇
当簇数目小于k时
       对每一个簇
              计算总误差
              在给定的簇上面进行k-均值聚类(k=2)
              计算将该簇一分为二后的总误差
       选择使得误差最小的那个簇进行划分操作
***************************************************************

二、Python实现
       我使用的Python是2.7.5版本的。附加的库有Numpy和Matplotlib。具体的安装和配置见前面的博文。在代码中已经有了比较详细的注释了。不知道有没有错误的地方,如果有,还望大家指正(每次的运行结果都有可能不同)。里面我写了个可视化结果的函数,但只能在二维的数据上面使用。直接贴代码:
biKmeans.py
  1. #################################################
  2. # kmeans: k-means cluster
  3. # Author : zouxy
  4. # Date   : 2013-12-25
  5. # HomePage : http://blog.csdn.net/zouxy09
  6. # Email  : zouxy09@qq.com
  7. #################################################

  8. from numpy import *
  9. import time
  10. import matplotlib.pyplot as plt


  11. # calculate Euclidean distance
  12. def euclDistance(vector1, vector2):
  13.         return sqrt(sum(power(vector2 - vector1, 2)))

  14. # init centroids with random samples
  15. def initCentroids(dataSet, k):
  16.         numSamples, dim = dataSet.shape
  17.         centroids = zeros((k, dim))
  18.         for i in range(k):
  19.                 index = int(random.uniform(0, numSamples))
  20.                 centroids[i, :] = dataSet[index, :]
  21.         return centroids

  22. # k-means cluster
  23. def kmeans(dataSet, k):
  24.         numSamples = dataSet.shape[0]
  25.         # first column stores which cluster this sample belongs to,
  26.         # second column stores the error between this sample and its centroid
  27.         clusterAssment = mat(zeros((numSamples, 2)))
  28.         clusterChanged = True

  29.         ## step 1: init centroids
  30.         centroids = initCentroids(dataSet, k)

  31.         while clusterChanged:
  32.                 clusterChanged = False
  33.                 ## for each sample
  34.                 for i in xrange(numSamples):
  35.                         minDist  = 100000.0
  36.                         minIndex = 0
  37.                         ## for each centroid
  38.                         ## step 2: find the centroid who is closest
  39.                         for j in range(k):
  40.                                 distance = euclDistance(centroids[j, :], dataSet[i, :])
  41.                                 if distance < minDist:
  42.                                         minDist  = distance
  43.                                         minIndex = j
  44.                        
  45.                         ## step 3: update its cluster
  46.                         if clusterAssment[i, 0] != minIndex:
  47.                                 clusterChanged = True
  48.                                 clusterAssment[i, :] = minIndex, minDist**2

  49.                 ## step 4: update centroids
  50.                 for j in range(k):
  51.                         pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]
  52.                         centroids[j, :] = mean(pointsInCluster, axis = 0)

  53.         print 'Congratulations, cluster using k-means complete!'
  54.         return centroids, clusterAssment

  55. # bisecting k-means cluster
  56. def biKmeans(dataSet, k):
  57.         numSamples = dataSet.shape[0]
  58.         # first column stores which cluster this sample belongs to,
  59.         # second column stores the error between this sample and its centroid
  60.         clusterAssment = mat(zeros((numSamples, 2)))

  61.         # step 1: the init cluster is the whole data set
  62.         centroid = mean(dataSet, axis = 0).tolist()[0]
  63.         centList = [centroid]
  64.         for i in xrange(numSamples):
  65.                 clusterAssment[i, 1] = euclDistance(mat(centroid), dataSet[i, :])**2

  66.         while len(centList) < k:
  67.                 # min sum of square error
  68.                 minSSE = 100000.0
  69.                 numCurrCluster = len(centList)
  70.                 # for each cluster
  71.                 for i in range(numCurrCluster):
  72.                         # step 2: get samples in cluster i
  73.                         pointsInCurrCluster = dataSet[nonzero(clusterAssment[:, 0].A == i)[0], :]

  74.                         # step 3: cluster it to 2 sub-clusters using k-means
  75.                         centroids, splitClusterAssment = kmeans(pointsInCurrCluster, 2)

  76.                         # step 4: calculate the sum of square error after split this cluster
  77.                         splitSSE = sum(splitClusterAssment[:, 1])
  78.                         notSplitSSE = sum(clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])
  79.                         currSplitSSE = splitSSE + notSplitSSE

  80.                         # step 5: find the best split cluster which has the min sum of square error
  81.                         if currSplitSSE < minSSE:
  82.                                 minSSE = currSplitSSE
  83.                                 bestCentroidToSplit = i
  84.                                 bestNewCentroids = centroids.copy()
  85.                                 bestClusterAssment = splitClusterAssment.copy()

  86.                 # step 6: modify the cluster index for adding new cluster
  87.                 bestClusterAssment[nonzero(bestClusterAssment[:, 0].A == 1)[0], 0] = numCurrCluster
  88.                 bestClusterAssment[nonzero(bestClusterAssment[:, 0].A == 0)[0], 0] = bestCentroidToSplit

  89.                 # step 7: update and append the centroids of the new 2 sub-cluster
  90.                 centList[bestCentroidToSplit] = bestNewCentroids[0, :]
  91.                 centList.append(bestNewCentroids[1, :])

  92.                 # step 8: update the index and error of the samples whose cluster have been changed
  93.                 clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentroidToSplit), :] = bestClusterAssment

  94.         print 'Congratulations, cluster using bi-kmeans complete!'
  95.         return mat(centList), clusterAssment

  96. # show your cluster only available with 2-D data
  97. def showCluster(dataSet, k, centroids, clusterAssment):
  98.         numSamples, dim = dataSet.shape
  99.         if dim != 2:
  100.                 print "Sorry! I can not draw because the dimension of your data is not 2!"
  101.                 return 1

  102.         mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
  103.         if k > len(mark):
  104.                 print "Sorry! Your k is too large! please contact Zouxy"
  105.                 return 1

  106.         # draw all samples
  107.         for i in xrange(numSamples):
  108.                 markIndex = int(clusterAssment[i, 0])
  109.                 plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

  110.         mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
  111.         # draw the centroids
  112.         for i in range(k):
  113.                 plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
  114.                
  115.         plt.show()
复制代码


三、测试结果
      测试数据是二维的,共80个样本。有4个类。具体见上一个博文
测试代码:
test_biKmeans.py
  1. #################################################
  2. # kmeans: k-means cluster
  3. # Author : zouxy
  4. # Date   : 2013-12-25
  5. # HomePage : http://blog.csdn.net/zouxy09
  6. # Email  : zouxy09@qq.com
  7. #################################################

  8. from numpy import *
  9. import time
  10. import matplotlib.pyplot as plt

  11. ## step 1: load data
  12. print "step 1: load data..."
  13. dataSet = []
  14. fileIn = open('E:/Python/Machine Learning in Action/testSet.txt')
  15. for line in fileIn.readlines():
  16.         lineArr = line.strip().split('\t')
  17.         dataSet.append([float(lineArr[0]), float(lineArr[1])])

  18. ## step 2: clustering...
  19. print "step 2: clustering..."
  20. dataSet = mat(dataSet)
  21. k = 4
  22. centroids, clusterAssment = biKmeans(dataSet, k)

  23. ## step 3: show the result
  24. print "step 3: show the result..."
  25. showCluster(dataSet, k, centroids, clusterAssment)
复制代码

      这里贴出两次的运行结果:

机器学习算法与Python实践之(六)二分k均值聚类

机器学习算法与Python实践之(六)二分k均值聚类
                              

       不同的类用不同的颜色来表示,其中的大菱形是对应类的均值质心点。
       事实上,这个算法在初始质心选择不同时运行效果也会不同。我没有看初始的论文,不确定它究竟是不是一定会收敛到全局最小值。《机器学习实战》这本书说是可以的,但因为每次运行的结果不同,所以我有点怀疑,自己去找资料也没找到相关的说明。对这个算法有了解的还望您不吝指点下,谢谢。

举报 使用道具

回复

精彩评论5

咏随琪迹  注册会员  发表于 2015-8-17 20:50:34 | 显示全部楼层
真心顶

举报 使用道具

回复 支持 反对
喀喀喀2  注册会员  发表于 2015-8-17 21:20:02 | 显示全部楼层
很好哦

举报 使用道具

回复 支持 反对
喀喀喀2  注册会员  发表于 2015-8-17 20:50:15 | 显示全部楼层
资源太好了,是我想要的

举报 使用道具

回复 支持 反对
喀喀喀2  注册会员  发表于 2015-8-17 21:34:09 | 显示全部楼层
点赞

举报 使用道具

回复 支持 反对
a58523  注册会员  发表于 2015-8-17 21:05:13 | 显示全部楼层
真心不错

举报 使用道具

回复 支持 反对
*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

更多

关注我们

QQ:448109455 周一至周日8:30-20:30
快速回复 返回顶部 返回列表