您的位置: 首页  >  文章  >  “集体智慧编程”之第三章：“发现群组”的 k均值聚类

“集体智慧编程”之第三章：“发现群组”的 k均值聚类

分类: 文章 • 2025-02-01 09:45:34

分级聚类的缺点

此前学习的分级聚类、与列聚类，有二个缺点：

  • 计算量大，数据越大运行越缓慢。
  • 没有确切的将数据分成不同的组，只是形成了树状图。虽然我倒觉得如果写过多的代码这一点还是可以搞定的。

k均值聚类可以应对上述两种缺点，我们会预先告诉算法生成的聚类数量，也就是我要产生几个类。

原理

如下图所示，对于5个数据项和两个聚类

过程是这样的，先随机产生两个聚类点，那么每一个数据项都会离一其中一个最近，那么将其分配给那个聚类。比如，A/B分配了给了上方的点，C/D/E分配给了下方的点。紧着，将聚类点的位置会发生改变，会改变到分配给它的所有数据项的中心位置。然后再进行一次分配，很明显C的距离离上面那一个点变得更近了。所以再将C分配给了上面的聚类点，接着，聚类点的位置再次发生改变。如此一来。当然分配的过程中，没有一个点的分配状况被改变，那么聚类点的位置也不会发生改变。此时，聚类结束。我们产生了两个聚类。
“集体智慧编程”之第三章：“发现群组”的 k均值聚类

所以与分级聚类相比，其还会接受一个额外的参数，就是希望参数多少个聚类的多少。

k均值聚类的代码

代码如下：
[python] view plain copy
  1. import random  
  2.   
  3.   
  4. def kcluster(rows,distance=pearson,k=4):  
  5.     #收集每一行的最大值和最小值  
  6.     ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) for i in range(len(rows[0]))]  
  7.       
  8.   
  9.   
  10.     #创建k个聚类点，第一次是随机的,数组列表里面再装了一个数组列表，外层数据列表有4个元素，内层数据列表有和单词数一样多个。  
  11.     #内层数组列表的每一个数值就是最大值到最小值之间的一个数，表示这个聚类点与其他数据点之间的...差距吧，因为如果两者数值一样，那么就离得很近  
  12.     #刚开始这个数值是每一行都加入了，后来将聚类点新的位置的时候，只有这个属于这个类的元素点才算进去，求平均了   
  13.     clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0] for i in range(len(rows[0]))] for j in range(k)]  
  14.       
  15.     lastmatches=None  
  16.     for t in range(100):#迭代次数，这里写的是100次  
  17.         print 'Iteration %d' % t  
  18.         bestmatches=[[]for i in range(k)]#一个列表数组里面再装一个列表数组  
  19.           
  20.         #在每一行中寻找距离最近的中心点  
  21.         for j in range(len(rows)):#那得博客的数量，也就是对每一个博客  
  22.             row=rows[j]#从0开始，没问题，这里拿到第一个博客的词频，因为博客名和单词都不在这个data数据集里面,这里是一行一行的拿数据  
  23.             bestmatch=0#没有加s，与上一个不同.假设与第0个聚类点最近  
  24.             for i in range(k):#循环4次  
  25.                 d=distance(clusters[i],row)#计算聚类点和数据之间的距离  
  26.                 if d<distance(clusters[bestmatch],row):bestmatch=i  
  27.             bestmatches[bestmatch].append(j)#bestmathes里面的元素就是4个数组，因为每个数组里面就是数，如果0就代表第一个博客，1就代表第二个博客              
  28.         #如果迭代的过程中，与上次相同，那么就停止。  
  29.         if bestmatches==lastmatches:break  
  30.         lastmatches=bestmatches  
  31.   
  32.   
  33.         #中心点移动到其所有成员的平均位置处  
  34.         for i in range(k):  
  35.             avgs=[0.0]*len(rows[0])#产生和单词数量一样多的的0.0  
  36.             if len(bestmatches[i])>0:#说明分类里面有元素  
  37.                 for rowid in bestmatches[i]:#这个代码很清晰，bestmatches里面每一个数组列表里面存的就是rowid  
  38.                     for m in range(len(rows[rowid])):  
  39.                         avgs[m]+=rows[rowid][m]#把存在于rowid的行和m列的数都取出来加起来，最后求平均值  
  40.                 for j in range(len(avgs)):#其实这里就是求一个平均的数值。  
  41.                     avgs[j]/=len(bestmatches[i])#bestmatches[i]是一个聚类，一个聚类里有多少rowid，就除以多少个rowid，就形成了平均。  
  42.                 clusters[i]=avgs  
  43.   
  44.   
  45.     return bestmatches  

执行代码：

[python] view plain copy
  1. blognames,words,data=readfile('blogdata.txt')  
  2. kclust=kcluster(data,k=10)  
  3. print [blognames[r] for r in kclust[0]]  

结果如下：

我只打印了聚类中的第一个类的结果。

[python] view plain copy
  1. >>>   
  2. Iteration 0  
  3. Iteration 1  
  4. Iteration 2  
  5. Iteration 3  
  6. Iteration 4  
  7. Iteration 5  
  8. Iteration 6  
  9. ['Hot Air', 'Talking Points Memo: by Joshua Micah Marshall', 'Andrew Sullivan | The Daily Dish', "Captain's Quarters", 'Power Line', 'The Blotter', 'Crooks and Liars', 'Think Progress', 'NewsBusters.org - Exposing Liberal Media Bias']  
  10. >>>   

很有意思的是：我发现每次结果都不一样。那这必然是因为初始随机点产生的不同的原因吧。


对项目的启示


这是一个纯粹对算法的学习，从聚类对项目的帮助来说，我已经在前两篇博客里谈的太多了，这里就不重复了。

需要记住，这个聚类产生的计算速度更快，而且可以确定产生多少个种类。这非常重要。到时在优化速度的时候必然有很大的帮助


全部源代码


[python] view plain copy
  1. # -*- coding: cp936 -*-  
  2. def readfile(filename):  
  3.     lines=[line for line in file(filename)]  
  4.   
  5.     #第一行是列标题，也就是被统计的单词是哪些  
  6.     colnames=lines[0].strip().split('\t')[1:]#之所以从1开始，是因为第0列是用来放置博客名了  
  7.     rownames=[]  
  8.     data=[]  
  9.     for line in lines[1:]:#第一列是单词，但二列开始才是对不同的单词的计数  
  10.         p=line.strip().split('\t')  
  11.         #每行都是的第一列都是行名  
  12.         rownames.append(p[0])  
  13.         #剩余部分就是该行对应的数据  
  14.         data.append([float(x) for x in p[1:]])#data是一个列表，这个列表里每一个元素都是一个列表，每一列表的元素就是对应了colnames[]里面的单词  
  15.     return rownames,colnames,data  
  16.   
  17.   
  18. from math import sqrt  
  19. def pearson(v1,v2):  
  20.     #先求和  
  21.     sum1=sum(v1)  
  22.     sum2=sum(v2)  
  23.   
  24.     #求平方和  
  25.     sum1Sq=sum([pow(v,2) for v in v1])  
  26.     sum2Sq=sum([pow(v,2) for v in v2])  
  27.   
  28.     #求乘积之和  
  29.     pSum=sum([v1[i]*v2[i] for i in range(len(v1))])  
  30.   
  31.     #计算pearson相关系数  
  32.     num=pSum-(sum1*sum2/len(v1))  
  33.     den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))  
  34.     if den==0:return 0  
  35.   
  36.     return 1.0-num/den#因为在本题中，我们想要相似度也大的两个元素的距离越近，所以才用1去减它们  
  37.   
  38.   
  39.   
  40. import random  
  41.   
  42. def kcluster(rows,distance=pearson,k=4):  
  43.     #收集每一行的最大值和最小值  
  44.     ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) for i in range(len(rows[0]))]  
  45.       
  46.   
  47.     #创建k个聚类点，第一次是随机的,数组列表里面再装了一个数组列表，外层数据列表有4个元素，内层数据列表有和单词数一样多个。  
  48.     #内层数组列表的每一个数值就是最大值到最小值之间的一个数，表示这个聚类点与其他数据点之间的...差距吧，因为如果两者数值一样，那么就离得很近  
  49.     #刚开始这个数值是每一行都加入了，后来将聚类点新的位置的时候，只有这个属于这个类的元素点才算进去，求平均了   
  50.     clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0] for i in range(len(rows[0]))] for j in range(k)]  
  51.       
  52.     lastmatches=None  
  53.     for t in range(100):#迭代次数，这里写的是100次  
  54.         print 'Iteration %d' % t  
  55.         bestmatches=[[]for i in range(k)]#一个列表数组里面再装一个列表数组  
  56.           
  57.         #在每一行中寻找距离最近的中心点  
  58.         for j in range(len(rows)):#那得博客的数量，也就是对每一个博客  
  59.             row=rows[j]#从0开始，没问题，这里拿到第一个博客的词频，因为博客名和单词都不在这个data数据集里面,这里是一行一行的拿数据  
  60.             bestmatch=0#没有加s，与上一个不同.假设与第0个聚类点最近  
  61.             for i in range(k):#循环4次  
  62.                 d=distance(clusters[i],row)#计算聚类点和数据之间的距离  
  63.                 if d<distance(clusters[bestmatch],row):bestmatch=i  
  64.             bestmatches[bestmatch].append(j)#bestmathes里面的元素就是4个数组，因为每个数组里面就是数，如果0就代表第一个博客，1就代表第二个博客              
  65.         #如果迭代的过程中，与上次相同，那么就停止。  
  66.         if bestmatches==lastmatches:break  
  67.         lastmatches=bestmatches  
  68.   
  69.         #中心点移动到其所有成员的平均位置处  
  70.         for i in range(k):  
  71.             avgs=[0.0]*len(rows[0])#产生和单词数量一样多的的0.0  
  72.             if len(bestmatches[i])>0:#说明分类里面有元素  
  73.                 for rowid in bestmatches[i]:#这个代码很清晰，bestmatches里面每一个数组列表里面存的就是rowid  
  74.                     for m in range(len(rows[rowid])):  
  75.                         avgs[m]+=rows[rowid][m]#把存在于rowid的行和m列的数都取出来加起来，最后求平均值  
  76.                 for j in range(len(avgs)):#其实这里就是求一个平均的数值。  
  77.                     avgs[j]/=len(bestmatches[i])#bestmatches[i]是一个聚类，一个聚类里有多少rowid，就除以多少个rowid，就形成了平均。  
  78.                 clusters[i]=avgs  
  79.   
  80.     return bestmatches  
  81.   
  82. blognames,words,data=readfile('blogdata.txt')  
  83. kclust=kcluster(data,k=10)  
  84. print [blognames[r] for r in kclust[0]]  
  85.                       
  86.                   
  87.               
  88.           
代码、数据已传至网盘：

相关推荐