算法介绍
- 对于同一个数据集，相同的聚簇中心，每次计算结果也可能会不一样
- 该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
function K-Means(输入数据，中心点个数K)
获取输入数据的维度Dim和个数N
随机生成K个Dim维的点
while(算法未收敛)
对N个点：计算每个点属于哪一类。
对于K个中心点：
1，找出所有属于自己这一类的所有数据点
2，把自己的坐标修改为这些数据点的中心点坐标
end
输出结果：
end
K-均值
- sklearn 示例
>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
... [4, 2], [4, 4], [4, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> kmeans.predict([[0, 0], [4, 4]])
array([0, 1], dtype=int32)
>>> kmeans.cluster_centers_
array([[1., 2.],
[4., 2.]])
- k-means算法初始聚簇中心落点影响很大
- 参数
n_cluster: 聚簇中心个数
n_init: 算法迭代次数
max_iter:
面试题
1 K-means中常用的到中心距离的度量有哪些？
- 欧式距离
- 曼哈顿距离
2 K-means中的k值如何选取?
手肘法
- 随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，
- 而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，
然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，
而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。
轮廓系数
-
使用轮廓系数(silhouette coefficient)来确定，选择使系数较大所对应的k值
计算样本i到同簇其他样本的平均距离ai。ai 越小，说明样本i越应该被聚类到该簇。将ai 称为样本i的簇内不相似度。 -
计算样本i到其他某簇Cj 的所有样本的平均距离bij，称为样本i与簇Cj 的不相似度。定义为样本i的簇间不相似度：bi =min{bi1, bi2, ..., bik}
bi越大，说明样本i越不属于其他簇。簇C中所有样本的a i 均值称为簇C的簇不相似度。 -
根据样本i的簇内不相似度a i 和簇间不相似度b i ，定义样本i的轮廓系数
lunkuo.png
-
判断：
轮廓系数范围在[-1,1]之间。该值越大，越合理。
si接近1，则说明样本i聚类合理；
si接近-1，则说明样本i更应该分类到另外的簇；
若si 近似为0，则说明样本i在两个簇的边界上。 -
所有样本的s i 的均值称为聚类结果的轮廓系数，是该聚类是否合理、有效的度量。
-
使用轮廓系数(silhouette coefficient)来确定，选择使系数较大所对应的k值
-
sklearn.metrics.silhouette_score sklearn中有对应的求轮廓系数的API
3 K-means算法中初始点的选择对最终结果有影响吗？
- 有，不同的初始值可能会结果不一样
4 K-means聚类中每个类别中心的初始点如何选择？
- 选择彼此距离尽可能远的K个点
- 先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
5 K-means中空聚类的处理
- 选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。
- 从具有最大SSE的簇中选择一个替补的质心，这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。
- 如果噪点或者孤立点过多，考虑更换算法，如密度聚类
6 K-means是否会一直陷入选择质心的循环停不下来？
- 迭代次数设置
- 设定收敛判断距离
7 如何快速收敛数据量超大的K-means？
8 K-means算法的优点和缺点是什么？
优点
1.算法快速、简单;
2.对大数据集有较高的效率并且是可伸缩性的;
3.时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目
缺点
1 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适
2 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。
3 特殊的聚类数据(相邻很近的长条形聚类、双月牙形、双环等)，K-means分类效果不佳，K-means寻找的是球形聚类
- 如何对K-means聚类效果进行评估？
答：
网友评论