KMean算法精讲

  KMeas算法是一种聚类算法，同时也是一种无监督的算法，即在训练模型时并不需要标签，其主要目的是通过循环迭代，将样本数据分成

K

K

K类。

基本训练步骤

• Step1：初始化$K$
• Step2：分别计算所有样本点到这$K$
• Step3：针对于每个group，计算其组内的平均点作为新的聚类中心（例如用户有年龄、性别两个特征，针对于年龄特征直接求平均值即可，对于性别特征使用onehot编码，每个纬度都求其平均值即可）
• Step4：重复步骤2和3直到满足终止条件

其基本过程如下图所示：

关于KMeans的几个问题

KMeans算法的目标函数是什么？

  已知观测集

(

x

1

,

x

2

,

.

.

.

,

x

n

)

(x_1,x_2,...,x_n)

(x1​,x2​,...,xn​)，其中每个观测都是一个d维实向量，k平均聚类要把这

n

n

n个观测划分到

K

K

K个集合中

(

K

≤

n

)

(K≤n)

(K≤n),使得组内平方和最小。换句话说，它的目标是找到使得下式满足的聚类

S

i

S_i

Si​：

arg min

⁡

S

∑

i

=

1

K

∑

x

∈

S

i

∣

∣

x

i

−

μ

i

∣

∣

2

argmin_Ssumlimits_{i=1}^Ksumlimits_{xin S_i}||x_i-mu_i||^2

Sargmin​i=1∑K​x∈Si​∑​∣∣xi​−μi​∣∣2
其中

u

i

u_i

ui​是

S

i

S_i

Si​中所有点的均值

KMeans算法是否一定会收敛？

  将

n

n

n个数据分为

K

K

K个聚类，最多有

n

K

n^K

nK种分类可能，这是一个很大但有限的数字。对于算法每次迭代，我们仅基于旧的聚类产生一个新的聚类。算法的性质如下：

• (1)如果旧的聚类与新的聚类相同，则下一次迭代的结果将再次相同。
• (2)如果新的聚类与旧的聚类不同，则更新的群集的目标函数值较低

  因此，KMeans算法的迭代过程总是在朝着目标函数减小的方向进行，进行优先次迭代之后，其目标值一定可以收敛。

不同的初始化是否带来不⼀样的结果？

不同的初始化显然会带来不同的结果，下面图片就可以表示：

K值如何进行选择？

  显然不同的K值也会导致最终的结果不同，那么我们该如何对K值进行选择？

  在这里我们定义一个概念Inertia：样本集中所有点离其所属cluster中心的距离的总和。

  因此我们可以使用交叉验证的方法，对不同的K值计算其Inertia，当

K

K

K趋近于

n

n

n时，Inertia的值一定是越来越小并且趋近于0，但其总会存在一个拐点，即Inertia下降的速度由快变为慢，我们一般取这个拐点的K值：

KMeans++

  所谓Kmeans++，即在Kmeans的基础上做了一些改进，主要是针对于初始点选择进行了优化，其初始点的选择过程如下：

• 1.从数据点中随机选择一个中心。
• 2.对于每个数据点$x$
• 3.使用加权概率分布随机选择一个新的数据点作为新的中心，其中选择点 $x$
• 4.重复步骤2和3，直到选择了$K$

其余训练过程与KMeans一致。

KMeans的优缺点

优点：

• 容易理解，容易实现
• 容易解释结果
• 计算复杂度比较低

缺点:

• 当数据的分布密度不均匀情况下，效果不理想
• 即使真实的聚类情况下不同聚类的个体数量非常不同，K-Means-也倾向让不同聚类包含的个体数据比较平均
• K-Means前提假设数据特征之间的联合分布是椭圆形的。这个条件在真实世界很难满足。
• K-Means无法处理环套环，缠绕S形的聚类
• 对异常值比较敏感
• 对初始化比较敏感

个人有关KMeans的奇思妙想

  上面有提到过，KMeans无法处理环套环，缠绕S形的聚类，也可以理解为对于分类问题，无法处理线性不可分的情况，但是我们在计算距离时如果有使用内积，比如余弦距离，那么我们就可以使用kernel trick，但缺点是对于核函数的选择我们往往需要采用交叉验证，这就需要我们使用带标签的数据来进行训练，而且现实中的意义可能不大。