基于动态离差平方和准则的无监督机器学习

肖枝洪，于 浩，王一超

(重庆理工大学 理学院， 重庆 400054)

经典K-means算法具体流程[8]如下：

1) 确定类别个数，再选取初始种子,计算各个样品与各个初始种子之间的距离。

2) 找出每个样品与各个种子之间最短距离,按照最短距离原则将全部样品划分到相应的类别中。

3) 再次计算每类重心,并将其作为新的种子,重复步骤1)。

4) 重复步骤2)、3),直到新的聚类结果与上一次相同,或者新的种子与上一次相同。

目前，对无监督机器学习算法主要对经典K-means 算法初始种子的选取进行研究。如马福民等[9]提出了一种基于局部密度自适应度量的粗糙K-means聚类算法；杨菊蜻等[10]提出一种基于改进 BA法的K-means算法，实现聚类结果的优化并提高聚类质量；薛卫等[11]采用可伸缩空间密度的相似性距离来度量数据点间的相似度的K-means 算法；于佐军等[12]提出一种改进的人工蜂群K-means算法，引入算术交叉操作并利用最优解指导搜索方向来提高K-means算法收敛的速度；田诗宵等[13]构造局部密度指标，并根据数据样本的局部密度分布情况，选取处在密度的峰值点作为初始种子以此来改进K-means算法；谢修娟等[14]提出一种基于样本密度选取初始种子的K-means改进算法；张阳等[15]通过设定K-means算法的终止条件的标准值以此减少算法迭代次数；杨玉梅[16]通过采用信息熵对样本数据赋权进而调整初始种子的选取以此达到优化K-means算法的效果；王茜等[17]基于“合并与分裂”思想，引入点密度概念和最小支撑树聚类算法提出了一种改进的K-means聚类算法；刘芝怡等[18]提出了一种利用最大距离等分策略来选取初始聚类中心的K-means 改进算法；王春龙等[19]提出一种基于隐含狄利克雷分概率模型的初始种子选取的K-means改进算法；此外还有袁方、赖玉霞等[20-22]分别采用不同的样本密度的计算方法来估计样本点的密度，从而选择相互距离最远并且处在高密度区域的K个样本作为K-means 算法的初始种子。综上，相关的研究多是将经典K-means与其他方法相结合得到的改进算法或者运用不同方法选取初始种子的改进方法，而针对划分标准进行改进的方法相对较少，所以本文在经典K-means算法步骤中第2步的划分标准基础上，提出了一种新的划分标准，也就是使得每次调整后的类内离差平方和递减，从而对经典K-means 算法进行改进，使得聚类结果更加准确。

1 基于动态离差平方和机器学习算法

1.1 动态离差平方和准则

假设已知以p个变量x1,x2,…,xp为指标的n个样品如表1所示，可以划分为C1,…,CK类如表2如示。

表1 p个指标n个样品

易知T(s)=T,T(s)=W(s)+A(s)。

那么，第s+1次调整后的类内离差平方和W(s+1)为：

W(s)+Δlm

(1)

K-means算法的划分原理要求

(2)

由DSSD算法可知，相对K-means算法而言，对数据的划分是基于整个类的离差平方和来判断的，是一种全局最优的聚类方法。在后面的例子中可以看到：它可以对K-means的聚类结果进行改进，使聚类结果更加精确。

1.2 动态离差平方和算法

动态离差平方和法算法流程：

1) 确定K个初始种子,并将全部观测聚类成为K个类,其中第j类的观测数记为nj,j=1,2,…,K。

4) 直至所有Δkl均大于0时，停止调整，得到最终的聚类结果。

1.3 DSSD算法与K-means算法比较

假设有16组观测数据如表3所示，并从表中选取x(3)、x(4)、x(15)为初始种子,采用K-means无监督机器学习算法进行聚类,得到结果如表4所示。

表3 16个样本2个指标的观测值

表4 K-means算法聚类结果及其类内离差平方和

对表4的聚类结果计算其各类的类重心为：xC1=(1.333,4.333)，xC2=(4.75,2.5),xC3=(-1.778,0.111)，并将xC1、xC2、xC3作为初始种子，采用DSSD法进行聚类，得到结果如表5所示。

表5 DSSD聚类结果及其类内离差平方和

从表5中可以看出经动态离差平方法聚类后，将表4中划分到C3类中的x(12)调整到了C1类中，并且类内离差平方和相比表4中类内离差平方和有所减小。这说明了基于动态离差平方和为划分依据的无监督机器学习算法可以对K-means算法的结果再次进行调整。

再直接采用K-means算法的初始种子x(3),x(4),x(15)，作为动态离差平方和法的初始种子进行聚类，得到结果与表5结果相同。其聚类结果不随着初始种子的改变而改变，聚类结果稳定。

由此看出，采用动态离差平方和法，对K-means算法的结果进行了进一步调整，而且调整后类内离差平方和有所下降，说明本文所提出的DSSD算法优于K-means算法。上述分析解释了DSSD算法相较于K-means算法的精确性，在下文中将进一步对本文算法的性能进行比较。

2 实例分析

本文采用UCI机器学习数据库[23]中的4个常用测试无监督机器学习算法的数据集如表6所示，并运用表中的数据来验证本文所提算法的性能，并与K-means算法的速度进行比较。

表6 UCI数据集描述

对表6中的4组数据集分别采用K-means无监督机器学习与DSSD法进行聚类，得到结果分别为表7～10所示。其中Cj为所对应数据集中包含的样品个数,j=1,2,…,8。

表7 Iris数据集聚类结果比较

表8 Wine数据集聚类结果比较

表9 Zoo数据集聚类结果比较

表10 Ecoli数据集聚类结果比较

从表7～10的结果可以看出：本文的DSSD算法的类内离差平方和均小于K-means无监督机器学习算法，说明了在大样本情形下，DSSD算法仍优于K-means算法。为了进一步验证DSSD算法相对K-means无监督机器学习算法的性能，遂采用外部聚类评价法中的调整兰德指数(adjusted rand index)进行评判。调整兰德指数是在数据集样本分类已知情况下，对待测聚类算法的聚类性能进行评价的有效指标[24-26]。结果如表11所示。

调整兰德指数的取值范围为[-1,1]，其值越接近于1意味着聚类结果与真实情况越吻合，从表11中的结果可以看出：DSSD算法的调整兰德指数均大于K-means无监督机器学习算法的调整兰德指数，说明DSSD算法相较于K-means算法性能更高。

表11 两种算法调整兰德指数

表12 两种算法运算时间比较

3 结束语

根据上述两种方法机器学习结果的对比可以看出:DSSD法的无监督机器学习算法在K-means算法结果之上又再次对其结果进行了“精修”，无论是从聚类后类内离差平方和还是调整兰德指数来判断，均可说明基于DSSD算法的聚类结果更具说服力。同时，DSSD算法的一个更具有吸引力的地方是聚类结果稳定，不依赖于初始种子。

但DSSD法也有不尽人之处，一方面，仍然需要事先确定类的个数，也就是K值依旧需要人工进行选取,不能动态改变类的个数；另一方面就是速度较慢。本文所提出的DSSD算法将在后续继续进行研究，对之进行优化,能有效改进类的动态选取方法，提高速度，减少运行时间。