K-Means聚类旨在将n个 对象划分为k个聚类，其中每个对象属于具有最近均值的聚类。该方法产生恰好 具有最大可能区别的k个不同簇。导致最大间隔（距离）的最佳簇 数k 不是先验的，必须根据数据计算。K-Means聚类的目标是最小化总簇内方差，或平方误差函数：

算法

将数据聚集到k个 组中，其中k 是预定义的。

随机选择k 点作为聚类中心。

根据欧几里德距离函数将对象分配到其最近的聚类中心 。

计算每个群集中所有对象的质心或平均值。

重复步骤2,3和4，直到在连续轮次中为每个群集分配相同的点。

K-Means是一种相对有效的方法。但是，我们需要提前指定簇的数量，最终结果对初始化很敏感，并且通常在局部最优处终止。遗憾的是，没有全局理论方法可以找到最佳簇数。一种实用的方法是将多次运行的结果与不同的k进行比较，并根据预定义的标准选择最佳运行结果 。通常，大k 可能会降低误差但会增加过度拟合的风险。

示例：

假设我们想要使用他们的年龄（一维空间）将访问者分组到一个网站，如下所示：

n = 19

15,15,16,19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65

初始簇（随机质心或平均值）：

k = 2

c 1 = 16

c 2 = 22

迭代 1：

c 1 = 15.33

c 2 = 36.25

x i c 1 c 2 距离1 距离2 最近的集群 新的质心

15 16 22 1 7 1 15.33

15 16 22 1 7 1

16 16 22 0 6 1

19 16 22 9 3 2 36.25

19 16 22 9 3 2

20 16 22 16 2 2

20 16 22 16 2 2

21 16 22 25 1 2

22 16 22 36 0 2

28 16 22 12 6 2

35 16 22 19 13 2

40 16 22 24 18 2

41 16 22 25 19 2

42 16 22 26 20 2

43 16 22 27 21 2

44 16 22 28 22 2

60 16 22 44 38 2

61 16 22 45 39 2

65 16 22 49 43 2

迭代 2：

c 1 = 18.56

c 2 = 45.90

x i c 1 c 2 距离1 距离2

最近的集群

新的质心

15 15.33 36.25 0.33 21.25 1 18.56

15 15.33 36.25 0.33 21.25 1

16 15.33 36.25 0.67 20.25 1

19 15.33 36.25 3.67 17.25 1

19 15.33 36.25 3.67 17.25 1

20 15.33 36.25 4.67 16.25 1

20 15.33 36.25 4.67 16.25 1

21 15.33 36.25 5.67 15.25 1

22 15.33 36.25 6.67 14.25 1

28 15.33 36.25 12.67 8.25 2 45.9

35 15.33 36.25 19.67 1.25 2

40 15.33 36.25 24.67 3.75 2

41 15.33 36.25 25.67 4.75 2

42 15.33 36.25 26.67 5.75 2

43 15.33 36.25 27.67 6.75 2

44 15.33 36.25 28.67 7.75 2

60 15.33 36.25 44.67 23.75 2

61 15.33 36.25 45.67 24.75 2

65 15.33 36.25 49.67 28.75 2

迭代 3：

c 1 = 19.50

c 2 = 47.89

x i c 1 c 2 距离1 距离2 最近的集群 新的质心

15 18.56 45.9 3.56 30.9 1 19.50

15 18.56 45.9 3.56 30.9 1

16 18.56 45.9 2.56 29.9 1

19 18.56 45.9 0.44 26.9 1

19 18.56 45.9 0.44 26.9 1

20 18.56 45.9 1.44 25.9 1

20 18.56 45.9 1.44 25.9 1

21 18.56 45.9 2.44 24.9 1

22 18.56 45.9 3.44 23.9 1

28 18.56 45.9 9.44 17.9 1

35 18.56 45.9 16.44 10.9 2 47.89

40 18.56 45.9 21.44 5.9 2

41 18.56 45.9 22.44 4.9 2

42 18.56 45.9 23.44 3.9 2

43 18.56 45.9 24.44 2.9 2

44 18.56 45.9 25.44 1.9 2

60 18.56 45.9 41.44 14.1 2

61 18.56 45.9 42.44 15.1 2

65 18.56 45.9 46.44 19.1 2

迭代 4：

c 1 = 19.50

c 2 = 47.89

x i c 1 c 2 距离1 距离2 最近的集群 新的质心

15 19.5 47.89 4.50 32.89 1 19.50

15 19.5 47.89 4.50 32.89 1

16 19.5 47.89 3.50 31.89 1

19 19.5 47.89 0.50 28.89 1

19 19.5 47.89 0.50 28.89 1

20 19.5 47.89 0.50 27.89 1

20 19.5 47.89 0.50 27.89 1

21 19.5 47.89 1.50 26.89 1

22 19.5 47.89 2.50 25.89 1

28 19.5 47.89 8.50 19.89 1

35 19.5 47.89 15.50 12.89 2 47.89

40 19.5 47.89 20.50 7.89 2

41 19.5 47.89 21.50 6.89 2

42 19.5 47.89 22.50 5.89 2

43 19.5 47.89 23.50 4.89 2

44 19.5 47.89 24.50 3.89 2

60 19.5 47.89 40.50 12.11 2

61 19.5 47.89 41.50 13.11 2

65 19.5 47.89 45.50 17.11 2

没有注意到迭代3和4之间的变化。通过使用聚类，已经确定了2组15-28和35-65。质心的初始选择可以影响输出集群，因此算法通常在不同的起始条件下运行多次，以便获得集群应该是什么的公平视图。