K-Means 聚类算法

K-Means聚类算法

概要

聚类算法是一种非监督的算法,简单说“人以类聚,物以群分”,就是将类似的事物归为一类,这里的类似特指距离,也就是距离越近,相似度越大。

相似性或距离的度量

对于样本空间 S,其中任意两个样本X, Y

X = {x_1, x_2, \cdots, x_p} \\
Y = {y_1, y_2, \cdots, y_p}
  1. 欧几里得距离
    样本之间的距离一本采用欧几里得空间距离,也就是我们常用的距离
d(X, Y) = \sqrt{(x_1 – y_1)^2 + (x_2 – y_2)^2 + \cdots + (x_p – y_p)}
  1. 曼哈顿距离
    主要用于城市两点的距离度量
d(X, Y) = |x_1 – y_1| + |x_2 – y_2| + \cdots + |x_p – y_p|
  1. 闵可夫斯基距离
d(X, Y) = \sqrt[q]{|x_1 – y_1|^q + |x_2 – y_2|^q + \cdots + |x_p – y_p|^q}
  1. 余弦距离
    用于度量两个文档之间的距离,将文档抽象为两个向量,向量的夹角余弦值作为两个文档的相似度
d(X, Y) = \cos <X, Y> = \frac{X \cdot Y}{||X|| \cdot ||Y|| }

计算流程

  1. N个样本数据中随机选取K个对象作为初始的聚类中心;
  2. 分别计算每个样本到各个中心的距离,将对象归为距离最近的中心;
  3. 所有对象计算完毕之后,得到总的距离平方和;
  4. 重新计算K个聚类中心,得到的总的距离平方和与上一次比较,如果大于上一次的,则转为步骤5,否则转为步骤2
  5. 当聚类中心不发生改变时,输出聚类结果

误差的计算

选择距离的平方和作为误差函数SSE,选择当SSE最小情况下的聚类

SSE = \sum _{i=1} ^ {K} \sum_{x \in E_i} d(e_i, x) ^ 2

其中簇E_i的聚类中心e_i为:

e_i = \frac{1}{n} \sum _{x \in E_i} x
符号 含义
K 聚类簇的个数
e_i E_i的中心
E_i i个簇
x 样本
n_i i个簇样本的个数
关注机器学习和算法的码农,喜欢编程和读书
文章已创建 72

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部