【机器学习】Kmeans聚类（含代码）基本聚类⽅法 算法时间复杂度：
时间复杂度：O(T*n*k*m)
空间复杂度：O(n*m)
n：元素个数，k：第⼀步中选取的元素个数，m：每个元素的特征项个数，T：第5步中迭代的次数。
算法代码：
环保润滑油# 注意，这⾥采⽤的是完全随机初始化，这样的效果不是很好。因为可能会存在有病态的初始化结果。
# 正确⽅法应该是从样本中随机选择k个点作为初始点。
k-means的损失函数是平⽅误差：
中⼼点的选择
k-meams算法的能够保证收敛，但不能保证收敛于全局最优点，当初始中⼼点选取不好时，只能达到局部最优点，整个聚类的效果也会⽐较差。可以采⽤以下⽅法：k-means中⼼点
1、选择彼此距离尽可能远的那些点作为中⼼点；
2、先采⽤层次进⾏初步聚类输出k个簇，以簇的中⼼点的作为k-means的中⼼点的输⼊。
3、多次随机选择中⼼点训练k-means，选择效果最好的聚类结果
算法衡量指标：
SSE（误差平⽅和）⽤来度量聚类效果。SSE越⼩表⽰数据点越接近它们的质⼼，聚类效果也越好。因为对误差取了平⽅，因此更加重视那些远离中⼼的点。 算法优缺点：
链接：
优点：
1. 计算复杂度低，为O(Nmq)，N是数据总量，m是类别（即k），q是迭代次数。⼀般来讲m、q会⽐N⼩得多，那么此时复杂度相当于
O(N)，在各种算法中是算很⼩的。
2. 思想很简单，实际上是⼀个优化全局MSE (Mean Square Error)和局部MSE的过程。
张英森缺点：
1. 分类结果依赖于分类中⼼的初始化（可以通过进⾏多次k-means取最优来解决）。 2. 对类别规模差异太明显的数据效果不好。⽐如总共有A、B两类，ground truth显⽰A类有1000个点，B类有100个点。
3. 对噪声敏感。⽐如总共有A、B两类，每类500个点，⽽且相距不远。此时在离这两类很远的地⽅加⼀个点（可以看作噪声），对分类中⼼会有很⼤的影响（因为分类中⼼是取平均）。
4. 同理，k-means对于距离⾮常近的类别（blobs）的分类效果也不好。
5. 不适⽤于categorical的分类。这个不知道怎么翻译，举⼏个例⼦说明。⽐如我们的分类标准是性别，⾮男即⼥（为了简化讨论，不考虑其他情况），那么假设男=1，⼥=0，如果使⽤k-means的话，有可能出来两个中⼼的值在0-1之间，那么就不符合实际情况了。同理，国籍、使⽤的语⾔这些分类也不能⽤k-means；反之，⾝⾼、体重等连续变化的数值可以使⽤。
逆王水（注：我⽬前的理解就是离散分类不可⽤k-means，连续分类可⽤k-means，如果有误，欢迎指正）
6. 需要预先知道有⼏类。
总⽽⾔之，即便k-means有很多缺点（很多都是可以克服的），但它最⼤的优点是算法复杂度低，也就意味着它能够在短时间内处理海量的数据，这在如今这个数据爆炸的时代是⾮常重要的。因此，k-means⽬前仍然被各个企业⼴泛使⽤。科学家、⼯程师等也⼀直在研究不同的⽅法去克服k-means的
缺点。
1. ⼈⼯确定初始K值
2. 受初始值的位置和个数的影响较⼤
3. 容易受到离点和噪声点的影响
完整的^(*￣(oo)￣)^
Kmeans实现Tensorflow版本
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
import seaborn as sns
import tensorflow as tf
#随机⽣成数据，2000个点，随机分为两类
num_puntos=2000
conjunto_puntos=[]#数据存放在列表中
for i in range(num_puntos):
if np.random.random()<0.5:
conjunto_puntos.append([al(0.0,0.9),al(0.0,0.9)])
else:
打印机共享器conjunto_puntos.append([al(3.0,0.5),al(3.0,0.5)])
df=pd.DataFrame({'x':[v[0] for v in conjunto_puntos],
'y':[v[1] for v in conjunto_puntos]})
sns.lmplot('x','y',data=df,fit_reg=False,size=6)
plt.show()
#lmplot, ⾸先要明确的是：它的输⼊数据必须是⼀个Pandas的'DataFrame Like' 对象,
#然后从这个DataFrame中挑选⼀些参数进⼊绘图充当不同的⾝份.
#把数组装进tensor中
stant(conjunto_puntos)
k=4
#tf.random_shuffle（value,seed=None,name=None）：对value（是⼀个tensor）的第⼀维进⾏随机化。相当于把数据随机化centroides=tf.Variable(tf.slice(tf.random_shuffle(vectors),[0,0],[k,-1]))
#随机选取K个点作为质⼼
#增加维度
expanded_pand_dims(vectors,0)
管式反应器expanded_pand_dims(centroides,1)
diff=tf.sub(expanded_vectors,expanded_centroides)
sqr=tf.square(diff)
duce_sum(sqr,2)
#挑选每⼀个点⾥的最近的质⼼（返回的是最⼩值索引）
assignments=tf.argmin(distance,0)
#tf.where（）返回bool型tensor中为True的位置，
#tf.gather(params, indices, validate_indices=None, name=None)合并索引indices所指⽰params中的切⽚
at(0,[tf.reduce_mean(tf.gather(vectors,
reduction_indices=[1])for c in range(k)])
#tf.assign()⽤means更新centroides
update_centroides=tf.assign(centroides,means)
init=tf.global_variables_initializer()
init=tf.global_variables_initializer()
sess=tf.Session()
sess.run(init)
for step in range(100):
_,centroid_values,assignment_values=sess.run([update_centroides,centroides,assignments])
data={'x':[],'y':[],'cluster':[]}
for i in range(len(assignment_values)):
data['x'].append(conjunto_puntos[i][0])
data['y'].append(conjunto_puntos[i][1])
快递系统data['cluster'].append(assignment_values[i])
df=pd.DataFrame(data)
sns.lmplot('x','y',data=df,fit_reg=False,size=6,hue='cluster',legend=False)
#hue通过指定⼀个分组变量, 将原来的y~x关系划分成若⼲个分组;fit_reg：是否显⽰回归曲线
plt.show()
补充知识点：
k-means的每⼀次迭代都可以分为以下3个步骤。
第⼀步：Map：对于每⼀个点，将其对应的最近的聚类中⼼
第⼆步：Combine：刚完成map的机器在本机上都分别完成同⼀个聚类的点的求和，减少reduce操作的通信量和计算量。
第三步：reduce：将同⼀聚类中⼼的中间数据再进⾏求和，得到新的聚类中⼼
k-means 聚类算法进⾏ MapReduce 的基本思路：对串⾏算法中每 1 次迭代启 动对应的 1 次 MapReduce 计算过程，完成数据记录到聚类中⼼的距离计算以及新 的聚类中⼼的计算。
K-Means的收敛性
在EM框架下，求得的参数θ⼀定是收敛的，能够到似然函数的最⼤值。那么K-Means是如何来保证收敛的呢？
⽬标函数
假设使⽤平⽅误差作为⽬标函数：
E-Step
固定参数μkμk, 将每个数据点分配到距离它本⾝最近的⼀个簇类中：
M-Step
固定数据点的分配，更新参数（中⼼点）μkμk:
为啥K-means会收敛呢？⽬标是使损失函数最⼩，在E-step时，到⼀个最逼近⽬标的函数γ；在M-step时，固定函数γ，更新均值μ（到当前函数下的最好的值）。
参考：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议