一、k-means聚类算法原理与一些性质
聚类问题从本质上来说是将包含若干元素的集合按某一准则划分成若干个互不相交的集合的并集，
该准则常常用一个函数来定义，称为目标函数。我们优化（聚类）的目标往往是极大化或者极小化
该目标函数。我们将它进行数学表述：
给定一个集合：
我们在 的非空子集定义一个集函数 ，并通过该函数构造一个目标函数，通过优化该
目标函数实现聚类。首先需要确定一个集合的划分方式：即将集合 分解为 个互不相交的
非空集合 的并集，使得
使得目标函数最大（或最小），即
其中 是一个超参数，需要人工设定。
考虑向量聚类问题：
在该问题中， 中的每个元素都是一个 维向量，将第 个元素记为 ：
。对于集合 的一个非空子集 ，定义：
该求和的意义是对 中的所有元素进行求和， 是 中的所有元素的中心，即
其中 表示集合 中的元素个数。
对于集合 的一个给定划分，可以得到
我们将它定义为向量聚类的目标函数，对它进行极小化。不难得到该目标函数的等价形式：
其中 是 所在类的中心。
极小化该目标函数的意义是使得同一类向量到它的中心位置的距离最近。该问题由于复杂度较高，
无法直接求出目标函数的最小值，所以只能从某一种分类出发，逐步进行迭代，使得目标函数朝着
改善（即目标函数值减小）的方向前进，这就是著名的 聚类算法。采用以下步骤进
行：
1、任选 个数据点 作为初始聚类中心（ 是一个超参数，是最终聚成的类别
数，需要人为设定）。
2、计算每个数据到 个中心的距离，并将数据划分到最近距离所在的类。这样就得到了集合 的
一种划分方式，重新计算每一类的中心位置 ，这样就得到了目标函数的一个取值，
即
是元素 所在的类的中心，即 中的某一个。
3、计算每个数据到 这 个中心的距离，并将数据划分到最近距离所在的类。这样
就得到了集合 的又一种划分方式，这样可以计算
的值，其中 是集合 中的元素， 仍然是 中的某一个，与 运算的
是根据步骤3中的新划分方式确定的，是 距离 最近的一个。由于 是
个中心的某一个，而 是 个中心中距 最近的一个，所以
即
但此时 不是该新划分下的目标函数，因为 不是新划
分下的中心位置。
4、计算3中的新划分得到的每一类的中心位置 ，从而得到目标函数的一个新取
值。我们下面说明，经过这样的一步操作之后，目标函数值不增（一般会较少，除非
与 完全重合）。由于
现只需证明
是新划分的每一类的中心位置。由于左右两边对集合 的划分方式是一样的，只是左边
的 是每类的中心，而右边不是。证明该不等式，就转化为了证明如下定理：
定理一、 设 是欧式空间的 个向量，则 取到最小值
当且仅当 是这 个向量的中心位置，即
评论0