K均值(K-MEANS)

路漫 2020-05-30

Kmeans是一种简单的聚类方法,一般在数据分析前期使用,选取适当的k,将数据分类后,然后分类研究不同聚类下数据的特点。

算法原理

kmeans的计算方法如下: 

  1 随机选取k个中心点;

  2 遍历所有数据,将每个数据划分到最近的中心点,作为一个簇;

  3 计算每个聚类的平均值,并作为新的中心点;

  4 重复2-3,直到这k个中心点不再变化(收敛),或执行了足够多的迭代。

轮廓系数

轮廓系数(Silhouette Coefficient)结合了聚类的凝聚度(Cohesion)和分离度(Separation),用于评估聚类的效果。该值处于-1~1之间,值越大,表示聚类效果越好。具体计算方法如下:

  1 对于第i个元素x_i,计算x_i与其同一个簇内的所有其他元素距离的平均值,记作a_i,用于量化簇内的凝聚度。 

  2 选取x_i外的一个簇b,计算x_i与b中所有点的平均距离,遍历所有其他簇,找到最近的这个平均距离,记作b_i,用于量化簇之间分离度。 

  3 对于元素x_i,轮廓系数s_i = (b_i – a_i)/max(a_i,b_i) 计算所有x的轮廓系数,求出平均值即为当前聚类的整体轮廓系数 

从上面的公式,不难发现若s_i小于0,说明x_i与其簇内元素的平均距离小于最近的其他簇,表示聚类效果不好。如果a_i趋于0,或者b_i足够大,那么s_i趋近与1,说明聚类效果比较好。

注意点

  1 随机初始化的中心点可能会影响聚类结果,可以多次聚类选择较优的聚类结果。

  2 K值的选取直接影响聚类簇数。

如何选取合适的K值

  1 最常用最简单的方法可视化数据,然后观察出聚类聚成几类比较合适,高维数据可视化困难。

  2 令k从2到一个固定值如10,在每个k值上重复运行数次kmeans(避免局部最优解),并计算当前k的平均轮廓系数,最后选取轮廓系数最大的值对应的k作为最终的集群数目。

Kmeans算法优缺点

  优点:1 对于类似球形簇的数据集,聚类效果明显;2 收敛速度较快,时间复杂度O(tkn) t为迭代次数 k中心点个数 n数据量;

  缺点:1 K值难以确定;2 初始点不合适,可能陷入局部最优的聚类结果;3 对噪点敏感(更新中心点使用均值,均值对噪声敏感);4 对于不规则的簇,kmeans聚类结果差。

参考:https://www.cnblogs.com/bourneli/p/3645049.html

2020-05-30 11:22

相关推荐

EffortsRun / 0评论 2014-04-22