IT技术之家

首页 > 人工智能

人工智能

KMean算法精讲_菜鸟炼丹师_kmean

发布时间:2022-10-24 17:12:42 人工智能 0次 标签:算法 聚类 机器学习
??KMeas算法是一种聚类算法,同时也是一种无监督的算法,即在训练模型时并不需要标签,其主要目的是通过循环迭代,将样本数据分成K类。...

本文目录

基本训练步骤关于KMeans的几个问题KMeans算法的目标函数是什么?KMeans算法是否一定会收敛?不同的初始化是否带来不?样的结果?K值如何进行选择? KMeans++KMeans的优缺点个人有关KMeans的奇思妙想

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

基本训练步骤

Step1:初始化 K K K个聚类中心(不必是真是的样本)Step2:分别计算所有样本点到这 K K K个聚类中心的距离,并把样本点划分至距离最近的groupStep3:针对于每个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) (Kn),使得组内平方和最小。换句话说,它的目标是找到使得下式满足的聚类 S i S_i Si?
arg?min ? S ∑ i = 1 K ∑ x ∈ S i ∣ ∣ x i ? μ i ∣ ∣ 2 \argmin_S\sum\limits_{i=1}^K\sum\limits_{x\in S_i}||x_i-\mu_i||^2 Sargmin?i=1K?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 x x,计算 D ( x ) D(x) D(x),即 x x x与已经选择的最接近中心之间的距离。3.使用加权概率分布随机选择一个新的数据点作为新的中心,其中选择点 x x x 的概率与 D ( x ) 2 D(x)^2 D(x)2成正比。4.重复步骤2和3,直到选择了 K K K个中心。

其余训练过程与KMeans一致。

KMeans的优缺点

优点:

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

缺点:

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

个人有关KMeans的奇思妙想

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