<p>（接上《聚类算法（1）》）</p>
<p> </p>
<p>除了在聚类算法（1）中的分级聚类，关于聚类还可以使用<a href="http://hi.baidu.com/sunshine_0316/blog/item/ddc1a5b69ef69dfd31add1c6.html">K-均值聚类</a>（也是为了克服分级聚类的两个不足之处）。</p>
<p> </p>
<p>算法描述：</p>
<p><a href="http://hi.baidu.com/languoning/blog/item/346c8b18ca6c98bc4aedbcf1.html">这里</a>有比较详尽的算法描述。（嗯，《<a href="http://book.douban.com/subject/2209702/">Programming Collective Intelligence </a>》上有幅超级好的插图。。。）</p>
<p> </p>
<p><textarea class="python" name="code">#----------------------------------------------------------------------
# K-均值聚类
#----------------------------------------------------------------------
def kcluster(rows, distancefunc=pearson, k=4):
"""K-Means Clustering"""
# 确定每个点的最大值和最小值
ranges = [ (min([row[i] for row in rows]), max([row[i] for row in rows]))
for i in range(len(rows[0]))]
# 随机创建K个中心点
clusters = [ [random.random()*(ranges[i][1]-ranges[i][0]) + ranges[i][0]
for i in range(len(rows[0]))] for j in range(k) ]
lastmatches = None
for t in range(100):
bestmatches = [[] for i in range(k)]
# 在每一行寻找距离最近的中心点
for j in range(len(rows)):
row = rows[j]
bestmatch = 0
for i in range(k):
d = distancefunc(clusters[i], row)
if d < distancefunc(clusters[bestmatch], row): bestmatch = i
bestmatches[bestmatch].append(j)
# 如果结果与上一次相同，则过程结束
if bestmatches == lastmatches: break
lastmatches = bestmatches
# 移动中心点
for i in range(k):
avgs = [0.0]*len(rows[0])
if len(bestmatches[i]) > 0:
for rowid in bestmatches[i]:
for m in range(len(rows[rowid])):
avgs[m] += rows[rowid][m]
for j in range(len(avgs)):
avgs[j] /= len(bestmatches[i])
clusters[i] = avgs
return bestmatches</textarea> </p>
<p> </p>
<p>说明：</p>
<p>1.rows是什么？</p>
<p> rows是从数据文件中读入的关于单词的频度数据。比如这里的rows，共有32项（有32个博客，即初始时有32个聚类），每项有629个数据（即，有629个单词，当然这些数据只是数字，是某单词（共629个）（该单词保存在其他地方）所对应的频度）。而我们进行的是，根据这些单词，分类那32个博客。故，我们的pearson算法计算的是一个长度629的列表与另一个629长的列表之间的距离。</p>
<p><strong>这个629长的列表即是我们所谓的点</strong>（我们要聚类的对象）。</p>
<p>2.clusters是什么？</p>
<p> 说clusters是K个中心点。那么K个中心点到底是什么？注意这里的“点”和平常所谓的点是不同的，上面的粗体部分已具体解释。说，clusters是k个中心点，即是说，clusters是个长度为k的列表，表中的每个元素是长度为620的数组（其中为我们随机产生的单词频度）。</p>
<p>那么，</p>
<p>“ 在每一行寻找距离最近的中心点”的意义也就明确了：将这32个条目（每个条目629项数据）中的某些同这k个所谓的中心点相关联。</p>
<p>另，</p>
<p>注意“移动中心点”中的if len(bestmatches[i]) > 0:一句是不可缺少的。因为可能这K个点中存在某些点，没有数据与他们相近，于是他们的长度就为0。</p>
<p>同时注意bestmatches中存的是什么？看代码：bestmatches[bestmatch].append(j)，我们知，bestmatches中存放的实际是某条数据在入内数据集中的序号。而在计算平均数时，也是计算的这些所有数据的平均数。</p>
<p>总之，记住这里的点实际上是个表。</p>
<p> </p>
<p>最后再append一个<strong>Tanimoto算法</strong>，用于距离度量。更精确的说，是用于这样的数据的距离度量：该数据中只可能有0,1两种取值，其中0代表不存在，1代表存在。（即yes和no的问题）</p>
<p><textarea class="python" name="code">#----------------------------------------------------------------------
# 距离度量： Tanimoto算法
def tanimoto(v1, v2):
c1,c2,shr = 0,0,0
for i in range(len(v1)):
if v1[i]: c1 += 1
if v2[i]: c2 += 1
if v1[i] and v2[i]: shr += 1
return (1.0 - (float(shr))/(c1+c2-shr)) </textarea> </p>
<p>注意这里是距离度量，因此，返回0，表示二者之间无距离，即两者喜欢的东西一模一样；返 |
|
转播
