数据挖掘算法中，聚类是最基本的常用算法之一。而如今内容平台不断增多，基于文本的数据挖掘的需求也越来越多。本文即抓取微信中热门文章，进行简单的聚类分析。 １.获取热门文章链接：
首先利用第三方开放的API（链接：/docs/api/id/147需要先申请一个Key才能使用）获取微信热门文章，这个API调用非常方便，根据实例调用即可，注意返回数据格式为json，里面包含热门文章的标题，链接，公众号名称。将抓取的数据进行保存，后面会利用这些数据进一步获取我们需要分析的文本。 ２.抓取热门文章：
像之前的爬虫程序一样，抓取各热门文章的正文文本，病保存在本地。这里要注意使用代理IP,以避免被微信封杀，本文作者就遇到了这个问题，在尝试随机更换代理IP后还是无法访问，导致测试程序时就只能用已抓取的几百个本地文件进行聚类了。 ３.文本分词：
我们抓取到的文章都是一大段的文本信息，我们需要将这些文本根据语义进行分词，然后根据一定算法（本文使用TF-IDF算法）提取每篇文章中最具代表性的
关键词，以这些关键字为基础来对各篇文章之间进行聚类。当前中文分词工具有中科院的ICTCLAS和jieba等，本文使用jieba，调用前需安装。当然事先还需要一份停用词表，停用词表中的词语都是一些常见但无法作为文本特征的词。
４.TF-IDF算法提取特征词：
TF-IDF是一种常用的文本特征提取算法，关于它的介绍可参考链接：/blog/2013/03/tf-idf.html　简单地说，能够代表一篇或一类文章的特征词需要有两个特征：一是这个词在某篇／类文章中出现次数要高，二是这个词在其他类的文章中出现频次要尽可能低 。这样的词才是最能代表一篇文章的特征的，TF-IDF思想正是这样的。其算法为：TF-IDF=词频×逆文档频率,其中词频＝某个词出现在文章中的次数或者某个词出现在文章中的次数/文章的总词数或者某个词出现在文中词数/该文中出现词数最多的词语所出现的词数来表示。词频这个指标实际上量化的就是上面所说的第一个特征；逆文档频率＝log(总文档数量/包含某个词的文档数量+１)
根据以上算法，提取出每个文档前１０个特征词（有可能不满１０个）。形成特征词集合之后，就可以用一组高维向量表示一个文档了。　５.Kmeans聚类
所有文档均量化为一个个向量后，文档的聚类问题就转化为向量的聚类问题了。而向量的聚类通常就用高维空间距离来度量其相似性了。高维空间距离度量多种度量方法，本文采用欧式距离度量。Kmeans算法是非常经典的聚类算法，其算法思想为：如果要将一堆对象分为Ｋ类，则先在待分类对象中随机选取Ｋ个作为聚类初始中心，计算其他所有对象与这些聚类中心的距离，然后将与某个聚类中心最近的文档归类到这个聚类中心，这样遍历一遍之后，所有文档就初步被分成了K类，我们在这K类中，计算每个类的中心文档（离平均向量最近的文档对象），就又得到了K个中心文档，按刚刚同样的方法进行归类，如此迭代下去，直到相邻两次的聚类结果是一直的时候，程序退出，返回聚类结果。程序比较长，就不帖代码了，代码已上传至：/dmhunter/cntextkmeans　程序运行结果：程序结果说明：i.上面数字表示文档id分类结果，共有１０类，下方１０行文字表示１０类中最具代表性的词语，可以看到健康，工作，人际关系这几个方面的文章用户比较喜欢阅读。ii.Kmeans聚类结果并不唯一，与每次初始随机选取的聚类中心有关，另外由于文档向量矩阵比较稀疏，每次运行结果可以看到很多id连续的文档都被归为一类，似乎程序忽略了它们一样，可以多运行几次，找到一些与其他类别差异度很大的文档id作为初始聚类中心，替换掉原程序中的最开始的随机聚类中心。总结：１.在写程序之前需要将任务详细分解，一个小功能用一个小函数实现，写完之后立即测试，如此滚动进行，就可以将调试程序时间降到最低；２.从降低程序计算复杂度与实现复杂度考虑,每个函数的输入与输出数据结构需要反复权衡选择，比如Python中的字典与列表，列表可变，排序页很容易，而字
典键值更改很容易发生错误，排序也比列表稍显复杂，但查找数据很容易。尤其是在使用字典的列表即[{
}...]或是列表的字典｛a:
]...｝时需要考虑到后面的函数功能的实现；３.养成良好的注释习惯，很多时候在调试bug过程中学到的是之前理解错了的知识，需要及时标注；变量较多的时候命名尽量与变量表示的含义相近；文本聚类的应用价值：i.以本文为例，文本聚类结果对于公众号的运营者来说具有一定意义，因为选取的都是热门文章，点击阅读量都很高，根据聚类结果我们可以找到与自己有相似的目标读者的其他公众号，这对于互相推荐关注或者关注竞争者这样的需求来是很有价值的。ii.对于有微信广告需求的市场主体来说，也是很有价值的，首先判定与某款产品类似的文本大类，进而找到这个领域内有影响力的大号，进行各种形式的广告合作。可视化数据分析(gh_c865d8af6e7a)　
　文章为作者独立观点，不代表微头条立场
的最新文章
更正从豆瓣网出现至今，基于用户兴趣的推荐系统的到了广泛的发展，现在已经成为几乎所有网站的标配，甚至连在线广告也越数据挖掘算法中，聚类是最基本的常用算法之一。而如今内容平台不断增多，基于文本的数据挖掘的需求也越来python爬虫项目中涉及到网页内容的提取时会经常用到xpath，本文简单介绍一下常用技
常见优化算法有随机搜索算法，爬山法，模拟退火算法，遗传算法。本文主要介绍随即搜索算法的应用。随机决策树算法主要用于分类与回归，对于离散变量可用于分类，对于连续性变量，可用于回归。以集体智慧编程一
到今天刚好整整半年，这期间自学了一些书，这里将书单整理分享排序算法是最基础的算法，本文利用python语言实现常见排序算法，并列举出同一标准下算法运行时间。#-*- 当前主流网购平台中似乎只有京东的商品评分可参考性较高了，本文详细介绍抓取京东全品类的所有商品近段时间琅琊榜电视剧红透整个网络，好多年都没怎么看电视剧了，好评这么多，弄得我也好奇地去看了看，没想gh_c865d8af6e7a本公众号致力于数据分析的可视化，欢迎关注！热门文章最新文章gh_c865d8af6e7a本公众号致力于数据分析的可视化，欢迎关注！Posts - 110,
Articles - 2,
Comments - 185
14:39 by Haippy, ... 阅读,
1 #! /usr/bin/env python
2 # -*- coding: utf-8 -*-
3 import os
4 import sys
5 import cmath
6 import os.path
8 class KMeans:
@descriptions: K-means Algorithm implementation.
@filename:
Filename of input data. 12
Clusters number. 13 ''' 14
def __init__(self, filename, knums): 15
self._filename = 16
self._knums = knums 17
self._dimension = 0 18
"""self._samples := [(seqx, x1, x2, ..., xn),
(seqy, y1, y2, ..., yn),
(seqz, z1, z2, ..., zn)]""" 22
self._samples= [] 23
"""self._clusters :=[[(0, c1, c2, ..., cn), (seqx, x1, x2, ..., xn), (seqy, y1, y2, ..., yn)],
self._clusters = [] 28
self._open(self._filename) 30
self._normalize() 31
#print self._samples 32
self._select(self._knums) 33
def _normalize(self): 36
@description: Normalize the attributes of input data. 38 """ 39
new_samples = [] 40
for t in xrange(len(self._samples)): 41
st = list(self._samples[t]) 42
new_samples.append(st) 43
for t in xrange(len(self._samples)): 45
self._samples.pop() 46
for d in xrange(1, (self._dimension + 1)): 48
container_att = [] 49
for idx in xrange(len(new_samples)): 50
att = new_samples[idx][d] 51
container_att.append(att) 52
max_att = max(container_att) 54
min_att = min(container_att) 55
for idx in xrange(len(new_samples)): 57
new_att = (new_samples[idx][d] - min_att) / (max_att - min_att) 58
new_samples[idx][d] = new_att 59
for t in xrange(len(new_samples)): 61
st = tuple(new_samples[t]) 62
self._samples.append(st) 63
def _open(self, filename): 67
@descriptions: Open the data file and fill each item into memory. 69
: Filename of input data. 70 """ 71
data_file= open(self._filename, "r") 72
data_lines= data_file.readlines(); 73
for line in data_lines: 74
string_samples = line.split("") 75
integer_samples= [] 76
integer_samples.append(int(string_samples[0])) 78
for e in string_samples[1:]: 80
integer_samples.append(float(e)) 81
samples = tuple(integer_samples) 82
self._samples.append(samples) 83
#print self._samples 84
self._dimension = len(self._samples[0]) - 1 85
#print self._dimension 86
def _select(self, knums): 89
@descriptions: Choose the first knums cluster center. 91
: Clusters number. 92 """ 93
for i in xrange(knums): 94
selected = self._samples[i] 95
temp = list(selected) 96
temp[0] = 0 97
self._clusters.append([]) 98
self._clusters[i].append(temp) 99
#print self._clusters100 101 102
def _distance(self, va, vb):103
@description: Return the (distance ** 2) of tuple va and tuple vb.105
: tuple va (x1, x2, ..., xn)106
: tuple vb (y1, y2, ..., yn)107 '''108
distance = 0109
for i in xrange(self._dimension):110
distance += (va[i] - vb[i]) * (va[i] - vb[i]) 111
#print distance112
return distance114 115 116
def _means(self, va):117
@description: Return the means of va.119
: A tuple of list va, with the form [(flagx, x1, x2, ..., xn), 120
(flagy, y1, y2, ..., yn), 121
(flagz, z1, z2, ..., zn), ...]122 """123
if (len(va) == 0):124
return va125
means_cluster = []127
means_cluster.append(1)#Indicate that the means has changed.128
#print va130
for d in xrange(self._dimension):131
tmp = 0132
for i in xrange(len(va)):133
tmp += va[i][d+1]134
means_cluster.append(tmp/len(va))135
means = tuple(means_cluster)136
return means138
def _equal(self, ta, tb):140
@description: Check if tuple ta equals to tuple tb.142
: Tuple ta.(flagx, x1, x2, ..., xn)143
: Tuple tb.(flagy, y1, y1, ..., ym)144 """145
if (len(ta) != len(tb)):146
return False147
for i in xrange(1, len(ta)):149
if (ta[i] != tb[i]):150
return False151
return True153
def flush(self, filename):155
@description: Flush data the disk.157
: Filename of output data.158 """159
foutput = open(filename, "w")160
for c in xrange(self._knums):162
foutput.write("Group %d" % c)163
for e in self._clusters[c][1:]:164
foutput.write("%s" %
repr(e))165
foutput.write("\n\n\n")166
print("Done.")167
foutput.close()168 169
def _reconstruct(self, idx):170
@description: Reconstruct the cluster points.172
: Index of clusters, where clusters has the form as follows:174
self._clusters :=[[(0, c1, c2, ..., cn), (seqx, x1, x2, ..., xn), (seqy, y1, y2, ..., yn)], 175
[]]178 """179
new_cluster = []180
new_cluster.append(0)181
for old_value in self._clusters[idx][0][1:]:182
new_cluster.append(old_value)183
for i in xrange(len(self._clusters[idx])):184
self._clusters[idx].pop()185
self._clusters[idx].insert(0, new_cluster)186 187 188
def process(self):189
@description: Process data, calculating k-means and clustering.191 """192
while True:193
for e in self._samples:195
shortest = -1197
for k in xrange(self._knums):198
#for k in _clusters[]199
#print e200
#print self._clusters[k][0]201
distance = self._distance(e[1:], self._clusters[k][0][1:])202
#print distance203
if (distance & 0.000001):204
# add e to the k-th cluster.205
self._clusters[k].append(e)206
if (shortest == -1):209
shortest = distance210
if (shortest & distance):212
shortest = distance213
if (k != self._knums - 1):215
continue216
# add e to the k-th cluster218
self._clusters[K].append(e)219
#print self._clusters220 221
for k in xrange(self._knums):222
new_ktuple = self._means(self._clusters[k][1:])223
if (len(new_ktuple) == 0):224
continue225
if (self._equal(self._clusters[k][0], new_ktuple) == False):226
self._clusters[k].pop(0)227
self._clusters[k].insert(0, new_ktuple)228
continue231
flag = 0233
for idx in xrange(self._knums):234
if (self._clusters[idx][0][0] == 1):235
flag = 1236
continue239 240
if (flag == 1):241
for idx in xrange(self._knums):242
self._reconstruct(idx) 243
break245 246 247 if __name__ =="__main__":248
ikmeans = KMeans("./iris-1.dat", 3)249
ikmeans.process()250
ikmeans.flush("./k-means-out.dat")
K-means算法的python代码，写完 + 调试花了差不多一天的时间，希望对大家有用。关于K-means聚类算法和ISODATA算法解释见下一篇博文。深入浅出K-Means算法
发表于 09:04|
来源CoolShell|
摘要：在数据挖掘中，K-Means算法是一种 cluster analysis 的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。
在数据挖掘中，K-Means算法是一种的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。
K-Means算法主要解决的问题如下图所示。我们可以看到，在图的左边有一些点，我们用肉眼可以看出来有四个点群，但是我们怎么通过计算机程序找出这几个点群来呢？于是就出现了我们的K-Means算法（）
K-Means要解决的问题
这个算法其实很简单，如下图所示：&
从上图中，我们可以看到，A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。
然后，K-Means的算法如下：
随机在图中取K（这里K=2）个种子点。
然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）
接下来，我们要移动种子点到属于他的&点群&的中心。（见图上的第三步）
然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。
这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下&求点群中心的算法&。
求点群中心的算法
一般来说，求点群中心点的算法你可以很简的使用各个点的X/Y坐标的平均值。不过，我这里想告诉大家另三个求中心点的的公式：
1）Minkowski Distance公式&&&可以随意取值，可以是负数，也可以是正数，或是无穷大。
2）Euclidean Distance公式&&也就是第一个公式&=2的情况
3）CityBlock Distance公式&&也就是第一个公式&=1的情况
这三个公式的求中心点有一些不一样的地方，我们看下图（对于第一个&在0-1之间）。
（1）Minkowski Distance & & （2）Euclidean Distance & &（3）&CityBlock Distance
上面这几个图的大意是他们是怎么个逼近中心的，第一个图以星形的方式，第二个图以同心圆的方式，第三个图以菱形的方式。
K-Means的演示
如果你以&K Means Demo&为关键字到Google里查你可以查到很多演示。这里推荐一个演示：
操作是，鼠标左键是初始化点，右键初始化&种子点&，然后勾选&Show History&可以看到一步一步的迭代。
注：这个演示的链接也有一个不错的。
K-Means++算法
K-Means主要有两个最重大的缺陷&&都和初始值有关：
K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（通过类的自动合并和分裂，得到较为合理的类型数目K）
K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（可以用来解决这个问题，其可以有效地选择初始点）
我在这里重点说一下K-Means++算法步骤：
先从我们的数据库随机挑个随机点当&种子点&。
对于每个点，我们都计算其和最近的一个&种子点&的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
然后，再取一个随机值，用权重的方式来取计算下一个&种子点&。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random&-=&D(x)，直到其&=0，此时的点就是下一个&种子点&。
重复第（2）和第（3）步直到所有的K个种子点都被选出来。
进行K-Means算法。
相关的代码你可以在这里找到&&（墙）另，
K-Means算法应用
看到这里，你会说，K-Means算法看来很简单，而且好像就是在玩坐标点，没什么真实用处。而且，这个算法缺陷很多，还不如人工呢。是的，前面的例子只是玩二维坐标点，的确没什么意思。但是你想一下下面的几个问题：
1）如果不是二维的，是多维的，如5维的，那么，就只能用计算机来计算了。
2）二维坐标点的X，Y 坐标，其实是一种向量，是一种数学抽象。现实世界中很多属性是可以抽象成向量的，比如，我们的年龄，我们的喜好，我们的商品，等等，能抽象成向量的目的就是可以让计算机知道某两个属性间的距离。如：我们认为，18岁的人离24岁的人的距离要比离12岁的距离要近，鞋子这个商品离衣服这个商品的距离要比电脑要近，等等。
只要能把现实世界的物体的属性抽象成向量，就可以用K-Means算法来归类了。
在《》&这篇文章中举了一个很不错的应用例子，作者用亚洲15支足球队的2005年到1010年的战绩做了一个向量表，然后用K-Means把球队归类，得出了下面的结果，呵呵。
亚洲一流：日本，韩国，伊朗，沙特
亚洲二流：乌兹别克斯坦，巴林，朝鲜
亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼
其实，这样的业务例子还有很多，比如，分析一个公司的客户分类，这样可以对不同的客户使用不同的商业策略，或是电子商务中分析商品相似度，归类商品，从而可以使用一些不同的销售策略，等等。
最后给一个挺好的算法的幻灯片：
推荐阅读相关主题：
网友评论有（0）
CSDN官方微信
扫描二维码,向CSDN吐槽
微信号：CSDNnews
相关热门文章Python实现的Kmeans++算法实例_python_ThinkSAAS
Python实现的Kmeans++算法实例
Python实现的Kmeans++算法实例
1、从Kmeans说起Kmeans是一个非常基础的聚类算法，使用了迭代的思想，关于其原理这里不说了。下面说一下如何在matlab中使用kmeans算法。创建7个二维的数据点： 代码如下:x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];使用kmeans函数： 代码如下:class = kmeans(x, 2);x是数据点，x的每一行代表一个数据；2指定要有2个中心点，也就是聚类结果要有2个簇。 class将是一个具有70个元素的列向量，这些元素依次对应70个数据点，元素值代表着其对应的数据点所处的分类号。某次运行后，class的值是： 代码如下: 2
2 2 1 1 1 1这说明x的前三个数据点属于簇2，而后四个数据点属于簇1。 kmeans函数也可以像下面这样使用： 代码如下:&& [class, C, sumd, D] = kmeans(x, 2)class =
0.1201sumd =
36.2149class依旧代表着每个数据点的分类;C包含最终的中心点，一行代表一个中心点；sumd代表着每个中心点与所属簇内各个数据点的距离之和；D的每一行也对应一个数据点，行中的数值依次是该数据点与各个中心点之间的距离，Kmeans默认使用的距离是欧几里得距离（参考资料[3]）的平方值。kmeans函数使用的距离，也可以是曼哈顿距离（L1-距离），以及其他类型的距离，可以通过添加参数指定。kmeans有几个缺点（这在很多资料上都有说明）：1、最终簇的类别数目（即中心点或者说种子点的数目）k并不一定能事先知道，所以如何选一个合适的k的值是一个问题。2、最开始的种子点的选择的好坏会影响到聚类结果。3、对噪声和离群点敏感。4、等等。2、kmeans++算法的基本思路kmeans++算法的主要工作体现在种子点的选择上，基本原则是使得各个种子点之间的距离尽可能的大，但是又得排除噪声的影响。 以下为基本思路：1、从输入的数据点集合（要求有k个聚类）中随机选择一个点作为第一个聚类中心2、对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)3、选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大4、重复2和3直到k个聚类中心被选出来5、利用这k个初始的聚类中心来运行标准的k-means算法假定数据点集合X有n个数据点，依次用X(1)、X(2)、……、X(n)表示，那么，在第2步中依次计算每个数据点与最近的种子点（聚类中心）的距离，依次得到D(1)、D(2)、……、D(n)构成的集合D。在D中，为了避免噪声，不能直接选取值最大的元素，应该选择值较大的元素，然后将其对应的数据点作为种子点。如何选择值较大的元素呢，下面是一种思路（暂未找到最初的来源，在资料[2]等地方均有提及，笔者换了一种让自己更好理解的说法）： 把集合D中的每个元素D(x)想象为一根线L(x)，线的长度就是元素的值。将这些线依次按照L(1)、L(2)、……、L(n)的顺序连接起来，组成长线L。L(1)、L(2)、……、L(n)称为L的子线。根据概率的相关知识，如果我们在L上随机选择一个点，那么这个点所在的子线很有可能是比较长的子线，而这个子线对应的数据点就可以作为种子点。下文中kmeans++的两种实现均是这个原理。3、python版本的kmeans++在http://rosettacode.org/wiki/K-means%2B%2B_clustering 中能找到多种编程语言版本的Kmeans++实现。下面的内容是基于python的实现（中文注释是笔者添加的）： 代码如下:from math import pi, sin, cosfrom collections import namedtuplefrom random import random, choicefrom copy import copytry:
import psyco
psyco.full()except ImportError:
passFLOAT_MAX = 1e100class Point:
__slots__ = ["x", "y", "group"]
def __init__(self, x=0.0, y=0.0, group=0):
self.x, self.y, self.group = x, y, groupdef generate_points(npoints, radius):
points = [Point() for _ in xrange(npoints)]
# note: this is not a uniform 2-d distribution
for p in points:
r = random() * radius
ang = random() * 2 * pi
p.x = r * cos(ang)
p.y = r * sin(ang)
return pointsdef nearest_cluster_center(point, cluster_centers):
"""Distance and index of the closest cluster center"""
def sqr_distance_2D(a, b):
return (a.x - b.x) ** 2
(a.y - b.y) ** 2
min_index = point.group
min_dist = FLOAT_MAX
for i, cc in enumerate(cluster_centers):
d = sqr_distance_2D(cc, point)
if min_dist & d:
min_dist = d
min_index = i
return (min_index, min_dist)'''points是数据点，nclusters是给定的簇类数目cluster_centers包含初始化的nclusters个中心点，开始都是对象-&(0,0,0)'''def kpp(points, cluster_centers):
cluster_centers[0] = copy(choice(points)) #随机选取第一个中心点
d = [0.0 for _ in xrange(len(points))]
#列表，长度为len(points)，保存每个点离最近的中心点的距离
for i in xrange(1, len(cluster_centers)):
# i=1...len(c_c)-1
for j, p in enumerate(points):
d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j个数据点p与各个中心点距离的最小值
sum += d[j]
sum *= random()
for j, di in enumerate(d):
if sum & 0:
cluster_centers[i] = copy(points[j])
for p in points:
p.group = nearest_cluster_center(p, cluster_centers)[0]'''points是数据点，nclusters是给定的簇类数目'''def lloyd(points, nclusters):
cluster_centers = [Point() for _ in xrange(nclusters)]
#根据指定的中心点个数，初始化中心点，均为(0,0,0)
# call k++ init
kpp(points, cluster_centers)
#选择初始种子点
# 下面是kmeans
lenpts10 = len(points) && 10
changed = 0
while True:
# group element for centroids are used as counters
for cc in cluster_centers:
cc.group = 0
for p in points:
cluster_centers[p.group].group += 1
#与该种子点在同一簇的数据点的个数
cluster_centers[p.group].x += p.x
cluster_centers[p.group].y += p.y
for cc in cluster_centers:
#生成新的中心点
cc.x /= cc.group
cc.y /= cc.group
# find closest centroid of each PointPtr
changed = 0
#记录所属簇发生变化的数据点的个数
for p in points:
min_i = nearest_cluster_center(p, cluster_centers)[0]
if min_i != p.group:
changed += 1
p.group = min_i
# stop when 99.9% of points are good
if changed &= lenpts10:
for i, cc in enumerate(cluster_centers):
cc.group = i
return cluster_centersdef print_eps(points, cluster_centers, W=400, H=400):
Color = namedtuple("Color", "r g b");
colors = []
for i in xrange(len(cluster_centers)):
colors.append(Color((3 * (i + 1) % 11) / 11.0,
(7 * i % 11) / 11.0,
(9 * i % 11) / 11.0))
max_x = max_y = -FLOAT_MAX
min_x = min_y = FLOAT_MAX
for p in points:
if max_x & p.x: max_x = p.x
if min_x & p.x: min_x = p.x
if max_y & p.y: max_y = p.y
if min_y & p.y: min_y = p.y
scale = min(W / (max_x - min_x),
H / (max_y - min_y))
cx = (max_x + min_x) / 2
cy = (max_y + min_y) / 2
print "%%!PS-Adobe-3.0n%%%%BoundingBox: -5 -5 %d %d" % (W + 10, H + 10)
print ("/l {rlineto} def /m {rmoveto} defn" +
"/c { .25 sub exch .25 sub exch .5 0 360 arc fill } defn" +
"/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath " +
gsave 1 setgray fill grestore gsave 3 setlinewidth" +
" 1 setgray stroke grestore 0 setgray stroke }def")
for i, cc in enumerate(cluster_centers):
print ("%g %g %g setrgbcolor" %
(colors[i].r, colors[i].g, colors[i].b))
for p in points:
if p.group != i:
print ("%.3f %.3f c" % ((p.x - cx) * scale + W / 2,
(p.y - cy) * scale + H / 2))
print ("n0 setgray %g %g s" % ((cc.x - cx) * scale + W / 2,
(cc.y - cy) * scale + H / 2))
print "n%%%%EOF"def main():
npoints = 30000
k = 7 # # clusters
points = generate_points(npoints, 10)
cluster_centers = lloyd(points, k)
print_eps(points, cluster_centers)main()上述代码实现的算法是针对二维数据的，所以Point对象有三个属性，分别是在x轴上的值、在y轴上的值、以及所属的簇的标识。函数lloyd是kmeans++算法的整体实现，其先是通过kpp函数选取合适的种子点，然后对数据集实行kmeans算法进行聚类。kpp函数的实现完全符合上述kmeans++的基本思路的2、3、4步。4、matlab版本的kmeans++ 代码如下:function [L,C] = kmeanspp(X,k)%KMEANS Cluster multivariate data using the k-means++ algorithm.%
[L,C] = kmeans_pp(X,k) produces a 1-by-size(X,2) vector L with one class%
label per column in X and a size(X,1)-by-k matrix C containing the%
centers corresponding to each class.%
Version: %
Authors: Laurent Sorber ()L = [];L1 = 0;while length(unique(L)) ~= k
% The k-means++ initialization.
C = X(:,1+round(rand*(size(X,2)-1))); %size(X,2)是数据集合X的数据点的数目，C是中心点的集合
L = ones(1,size(X,2));
for i = 2:k
D = X-C(:,L); %-1
D = cumsum(sqrt(dot(D,D,1))); %将每个数据点与中心点的距离，依次累加
if D(end) == 0, C(:,i:k) = X(:,ones(1,k-i+1)); end
C(:,i) = X(:,find(rand & D/D(end),1)); %find的第二个参数表示返回的索引的数目
[~,L] = max(bsxfun(@minus,2*real(C'*X),dot(C,C,1).')); %碉堡了，这句，将每个数据点进行分类。
% The k-means algorithm.
while any(L ~= L1)
for i = 1:k, l = L==i; C(:,i) = sum(X(:,l),2)/sum(l); end
[~,L] = max(bsxfun(@minus,2*real(C'*X),dot(C,C,1).'),[],1);
endend这个函数的实现有些特殊，参数X是数据集，但是是将每一列看做一个数据点，参数k是指定的聚类数。返回值L标记了每个数据点的所属分类，返回值C保存了最终形成的中心点（一列代表一个中心点）。测试一下： 代码如下:&& x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]]x =
3.6064&& [L, C] = kmeanspp(x',2)L =
0.1175好了，现在开始一点点理解这个实现，顺便巩固一下matlab知识。unique函数用来获取一个矩阵中的不同的值，示例： 代码如下:&& unique([1 3 3 4 4 5])ans =
5&& unique([1 3 3 ; 4 4 5])ans =
5所以循环 while length(unique(L)) ~= k 以得到了k个聚类为结束条件，不过一般情况下，这个循环一次就结束了，因为重点在这个循环中。rand是返回在(0,1)这个区间的一个随机数。在注释%-1所在行，C被扩充了，被扩充的方法类似于下面： 代码如下:&& C =[];&& C(1,1) = 1C =
1&& C(2,1) = 2C =
2&& C(:,[1 1 1 1])ans =
2&& C(:,[1 1 1 1 2])Index exceeds matrix dimensions.C中第二个参数的元素1，其实是代表C的第一列数据，之所以在值2时候出现Index exceeds matrix dimensions.的错误，是因为C本身没有第二列。如果C有第二列了： 代码如下:&& C(2,2) = 3;&& C(2,2) = 4;&& C(:,[1 1 1 1 2])ans =
4dot函数是将两个矩阵点乘，然后把结果在某一维度相加： 代码如下:&& TT = [1 2 3 ; 4 5 6];&& dot(TT,TT)ans =
45&& dot(TT,TT,1 )ans =
45&code&cumsum&/code&是累加函数： 代码如下:&& cumsum([1 2 3])ans =
6&& cumsum([1 2 3; 4 5 6])ans =
9max函数可以返回两个值，第二个代表的是max数的索引位置： 代码如下:&& [~, L] = max([1 2 3])L =
3&& [~,L] = max([1 2 3;2 3 4])L =
2其中~是占位符。关于bsxfun函数，官方文档指出： 代码如下:C = bsxfun(fun,A,B) applies the element-by-element binary operation specified by the function handle fun to arrays A and B, with singleton expansion enabled其中参数fun是函数句柄，关于函数句柄见资料[9]。下面是bsxfun的一个示例： 代码如下:&& A= [1 2 3;2 3 4]A =
4&& B=[6;7]B =
7&& bsxfun(@minus,A,B)ans =
-3对于： 代码如下:[~,L] = max(bsxfun(@minus,2*real(C'*X),dot(C,C,1).'));max的参数是这样一个矩阵，矩阵有n列，n也是数据点的个数，每一列代表着对应的数据点与各个中心点之间的距离的相反数。不过这个距离有些与众不同，算是欧几里得距离的变形。假定数据点是2维的，某个数据点为(x1,y1)，某个中心点为(c1,d1)，那么通过bsxfun(@minus,2real(C'X),dot(C,C,1).')的计算，数据点与中心点的距离为2c1x1 + 2d1y1 -c1.^2 - c2.^2，可以变换为x1.^2 + y1.^2 - (c1-x1).^2 - (d1-y1).^2。对于每一列而言，由于是数据点与各个中心点之间的计算，所以可以忽略x1.^2 + y1.^2，最终计算结果是欧几里得距离的平方的相反数。这也说明了使用max的合理性，因为一个数据点的所属簇取决于与其距离最近的中心点，若将距离取相反数，则应该是值最大的那个点。
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信