Press "Enter" to skip to content

数据分析之二分K均值聚类算法

一、介绍

 

在聚类问题中,我们会给定一组未加标签的数据集,同时希望有一个算法能够自动将这些数据分成有紧密关系的子集或者是簇。K均值算法现在是最火热也是最为广泛应用的聚类算法。

 

二、K均值聚类算法原理

 

假设有一个无标签数据集图(a),现在想将其分为两个簇,使用K均值算法来进行操作,操作步骤:

 

1.首先随机生成两个点,这两点叫做聚类中心(图b)。 K均值算法是一个迭代算法,它会做两件事,第一个是簇分配,第二个是移动聚类中心。

 

2.簇分配: K均值算法中每次内循环的第一步要进行簇分配,也就是说,遍历每个样本点,根据每个样本与红色聚类中心更近还是蓝色中心更近来将每个样本点分配个两个聚类中心之一。具体的说,就是讲靠近蓝色聚类中心的点染成蓝色,靠近红色聚类中心的点染成红色。

 

3.移动聚类中心: K均值算法中每次内循环的第二步要移动聚类中心,要做是找到所有蓝点并计算出它们的均值,然后把蓝色聚类中心移到那里,红色聚类中心也是一样的操作。

 

4.然后接着继续做簇分配和移动聚类中心,迭代多次之后,就会完成最终的两个点集的聚类,这就可以说K均值算法已经聚合了。

 

三、K均值聚类算法原理图解

 

 

(a)

 

 

(b)

 

 

(c)

 

 

(d)

 

 

(e)

 

四、K均值聚类算法伪代码

 

 

五、K均值算法问题

 

k均值算法有一个不足之处,就是聚类结果易受到聚类中心点的选择影响,在很多情况下只会收敛到局部最小值而不是全局最小值(如下图)

 

(1)随机化较好情况,得到三个不错的簇

 

 

(2)随机化不好的情况,得到不同的局部最优解

 

 

六、二分K均值算法

 

二分k均值算法可以改善k均值算法聚类结果易受到聚类中心点的选择影响,在很多情况下只会收敛到局部最小值而不是全局最小值的问题。

 

(1)原理

 

将所有点作为一个簇,然后将该簇一分为二,之后选择一个簇进行划分,选择哪一个簇进行划分取决于对其划分是够可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复,直到得到用户指定的簇数目为止。

 

SSE:误差平方和,该统计参数计算的是拟合数据和原始数据对应点的误差的平方和。SSE越接近于0,说明模型选择和拟合更好,数据预测也越成功。

 

(2)伪码

 

将所有点看成一个簇

 

当簇数目小于k时:

 

对每一个簇

 

计算总误差

 

在给定的簇上面进行K-均值划分(k=2)

 

计算将该簇一分为二之后的总误差

 

选择使得总误差最小的那个簇的进行划分

 

七、Iris数据集实验结果

 

(1) 数据集简介:

 

来自UCI欧文大学机器学习存储库,包含150个样本,分为3类,每类50个数据,每个数据包含4个属性。可通过花萼长度,花萼宽度,花瓣长度,花瓣宽度4个属性预测鸢尾花卉属于(Setosa,Versicolour,Virginica)三个种类中的哪一类

 

(2) 实验结果:

 

1) 鸢尾花数据集分布

 

 

2) 聚类效果较好的情况

 

 

 

准确率为86.7%

 

3) 聚类效果较差的情况

 

 

 

准确率为66.7%

 

八、观察分析

 

K均值算法是二分K均值建模的主要思想,它们的聚类原理是一致的,二分K均值算法能够克服K均值收敛于局部最小的局限,在聚类效果上展示出比较稳定的性能,二分K均值算法在Iris数据集上聚类效果比较好的情况,能展示出86.7%的预测准确率。同时,二分K均值算法在Iris数据集上聚类效果会出现不太好的情况。这是由于虽然二分K均值能克服K均值收敛于局部最小的局限,但并不能保证收敛到全局最优值。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注