数据挖掘十大算法之K-means算法

k-means算法介绍:

K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

相异度计算

在正式讨论聚类前,我们要先弄清楚一个问题:如何定量计算两个可比较元素间的相异度。用通俗的话说,相异度就是两个东西差别有多大,例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度,这是能我们直观感受到的。但是,计算机没有这种直观感受能力,我们必须对相异度在数学上进行定量定义。

设X={x_(1,) x_(2,),…,x_(n,) },Y={y_(1,) y_2,…,y_n} ,其中X,Y是两个元素项,各自具有n个可度量特征属性,那么X和Y的相异度定义为:d{x,y}=f(x,y)→ R,其中R为实数域。也就是说相异度是两个元素对实数域的一个映射,所映射的实数定量表示两个元素的相异度。

标量

标量也就是无方向意义的数字,也叫标度变量。在先考虑元素的所有特征属性都是标量的情况。例如,计算X={2,1,102}和Y={1,3,2}的相异度。

50949820.jpg

标量的规格化:上面这样计算相异度的方式有一点问题,就是取值范围大的属性对距离的影响高于取值范围小的属性。所谓规格化就是将各个属性值按比例映射到相同的取值区间,这样是为了平衡各个属性对距离的影响。通常将各个属性均映射到[0,1]区间,映射公式为:a_i^,=(a_i−min⁡(a_i ))/(max⁡(a_i )−min⁡(a_i ) ),其中max(a_i)和min(a_i)表示所有元素项中第i个属性的最大值和最小值。例如,将示例中的元素规格化到[0,1]区间后,就变成了X’={1,0,1},Y’={0,1,0},重新计算欧氏距离约为1.732。

算法思想:通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优,从而使生成的每个聚类内紧凑,类间独立。这一算法不适合处理离散型属性,但是对于连续型具有较好的聚类效果。

算法描述

1. 为中心向量c1, c2, …, ck初始化k个种子;
2. 分组:
    1) 将样本分配给距离其最近的中心向量
    2) 由这些样本构造不相交( non-overlapping )的聚类
3. 确定中心:用各个聚类的中心向量作为新的中心
4. 重复分组和确定中心的步骤,直至算法收敛。

k-means算法

输入:簇的数目k和包含n个对象的数据库。
输出:k个簇,使平方误差准则最小。

算法步骤:
    1. 为每个聚类确定一个初始聚类中心,这样就有K 个初始聚类中心;
    2. 将样本集中的样本按照最小距离原则分配到最邻近聚类;
    3. 使用每个聚类中的样本均值作为新的聚类中心;
    4. 重复步骤2.3直到聚类中心不再变化;
    5. 结束,得到K个聚类。

54899785.jpg
81946802.jpg
62721056.jpg
11547722.jpg