K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
算法原理：
首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
算法优缺点：
优点：
1.对处理大数据集，该算法保持可伸缩性和高效性
2.算法快速、简单，易于理解;
缺点：
1.在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的；
2.若簇中含有异常点，将导致均值偏离严重（即:对噪声和孤立点数据敏感）；
3.该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的；
4.在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果；
5.局部最优解而不是全局优 （这个和初始点选谁有关）。
算法流程：
step-1:首先从n个数据对象任意选择 k 个对象作为初始聚类中心；
-
#随机选择K个点
-
k = rd.sample(range(count), k_count)
-
k_point = [[x[i], [y[i]]]
for i
in k]
#保证有序
-
k_point.sort()
step-2:根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
-
km = [[]
for i
in range(k_count)]
#存储每个簇的索引
-
#遍历所有点
-
for i
in range(count):
-
cp = [x[i], y[i]]
#当前点
-
#计算cp点到所有质心的距离
-
_sse = [distance(k_point[j], cp)
for j
in range(k_count)]
-
#cp点到那个质心最近
-
min_index = _sse.index(min(_sse))
-
#把cp点并入第i簇
-
km[min_index].append(i)
step-3:重新计算每个（有变化）聚类的均值（中心对象）；
-
#更换质心
-
step+=
1
-
k_new = []
-
for i
in range(k_count):
-
_x = sum([x[j]
for j
in km[i]]) / len(km[i])
-
_y = sum([y[j]
for j
in km[i]]) / len(km[i])
-
k_new.append([_x, _y])
-
k_new.sort()
#排序
step-4: 循环（2）到（3）直到每个聚类不再发生变化为止
-
frames.append(imageio.imread(
'1.jpg'))
-
if (k_new != k_point):
#一直循环直到聚类中心没有变化
-
k_point = k_new
-
else:
-
return km
python完整代码实现：
-
# coding:utf-8
-
import numpy
as np
-
import pylab
as pl
-
import random
as rd
-
import imageio
-
#计算平面两点的欧氏距离
-
step=
0
-
color=[
'.r',
'.g',
'.b',
'.y']
#颜色种类
-
dcolor=[
'*r',
'*g',
'*b',
'*y']
#颜色种类
-
frames = []
-
def distance(a, b):
-
return (a[
0]- b[
0]) **
2 + (a[
1] - b[
1]) **
2
-
#K均值算法
-
def k_means(x, y, k_count):
-
count = len(x)
#点的个数
-
#随机选择K个点
-
k = rd.sample(range(count), k_count)
-
k_point = [[x[i], [y[i]]]
for i
in k]
#保证有序
-
k_point.sort()
-
global frames
-
global step
-
while
True:
-
km = [[]
for i
in range(k_count)]
#存储每个簇的索引
-
#遍历所有点
-
for i
in range(count):
-
cp = [x[i], y[i]]
#当前点
-
#计算cp点到所有质心的距离
-
_sse = [distance(k_point[j], cp)
for j
in range(k_count)]
-
#cp点到那个质心最近
-
min_index = _sse.index(min(_sse))
-
#把cp点并入第i簇
-
km[min_index].append(i)
-
#更换质心
-
step+=
1
-
k_new = []
-
for i
in range(k_count):
-
_x = sum([x[j]
for j
in km[i]]) / len(km[i])
-
_y = sum([y[j]
for j
in km[i]]) / len(km[i])
-
k_new.append([_x, _y])
-
k_new.sort()
#排序
-
-
#使用Matplotlab画图
-
pl.figure()
-
pl.title(
"N=%d,k=%d iteration:%d"%(count,k_count,step))
-
for j
in range(k_count):
-
pl.plot([x[i]
for i
in km[j]], [y[i]
for i
in km[j]], color[j%
4])
-
pl.plot(k_point[j][
0], k_point[j][
1], dcolor[j%
4])
-
pl.savefig(
"1.jpg")
-
frames.append(imageio.imread(
'1.jpg'))
-
if (k_new != k_point):
#一直循环直到聚类中心没有变化
-
k_point = k_new
-
else:
-
return km
-
-
-
x, y = np.loadtxt(
'2.csv', delimiter=
',', unpack=
True)
-
k_count =
4
-
-
km = k_means(x, y, k_count)
-
print step
-
imageio.mimsave(
'k-means.gif', frames,
'GIF', duration =
0.5)
实验结果：
初始值选取的不同造成结果也不一样，如：
代码：
链接：https://pan.baidu.com/s/1dEEEeWh
密码：需要的请回复或者支持下，赚点积分！
http://download.csdn.net/download/wind_blast/10155662
百度分享密码：thmt
参考资料：
转载：https://blog.csdn.net/wind_blast/article/details/78779987