基于改进层次方法的无参K-means算法

2022-09-28史国斌张忠林

计算机仿真 2022年8期

史国斌，张忠林

(兰州交通大学电子与信息工程学院，甘肃兰州 730070)

1 引言

对数据进行聚类在现代数据价值提取过程中有非常重要的意义[1]。比如在现代营销系统中，利用大量客户资料，对客户进行聚类可以进行精准营销[2]；在文字识别领域，对手写字体进行归一化、标准化后进行聚类可以识别文字[3]；通过对滴滴、Uber等大量关于交通、运输时间、高峰乘车地点等数据聚类有助于对城市的交通模式进行深入的了解，可以帮助做城市未来规划等[4]。

K-means和层次方法(Hierarchical Clustering)是聚类算法中的经典算法。K-means的时间复杂度为O(ktmn)，但其对入参：聚类数k敏感。层次聚类可以无需入参，但时间复杂度至少是O(n2)[5]。

本文通过改进凝聚层次算法，使其自动为K均值算法提供初始化参数，进而利用K均值的高效性对大型数据集进行聚类。

本文算法在大型数据集(超过200万)上的测试表明，本方法具备生产实践应用可行性。

2 相关工作

K均值算法作为数据挖掘十大算法之一，在生产实践中尤其是现代数据科学面对体量巨大的数据集时，仍然具有很强的商业应用价值并得到广泛应用[6]。因此国内外学者持续对其进行研究与改进，这些改进大多都是针对如何找到合适的K值或避免初值敏感等问题的。

如K-means++算法[7]，利用聚类中心点的选取应尽可能相互离散的思想，来优化初值敏感问题。该算法一定程度上避免了初值选取随机性带来的问题，优化了迭代次数，但仍然存在初值、初始聚类中心的随机选择问题。实验部分本文对比了该算法。

ISODATA[8]算法在运行过程中能够根据各个类别的实际情况进行两种操作来调整聚类中心数K：①分裂操作，对应着增加聚类中心数；②合并操作，对应着减少聚类中心数。该算法改进了原算法硬划分的不合理性，但仍然需要设置初始参数启动算法。

Fuzzyc-means由Dunn(1973)[9]提出，后来由Bezdek(1981)[10]进行了改进，该算法的核心是每个数据点以隶属度值归为多个聚类(软分配)。Eschrich等[11]在2003对该聚类思想再优化，通过用质心代替类内所有数据点来减少数据量，以加快K-means和模糊C-means的使用效率。该算法启动时通常采用随机初始化。即权值随机地选取。簇数需要人为选定。

Pelleg和Moore[12]在1999年提出利用KD树(kd-tree)来高效地识别所有数据点最接近的聚类中心，可以省略一些明显不属于既定聚类中心的距离计算。一年后他们提出X均值(X-means)[13]，在之前工作的基础上，通过给定K值得范围，利用诸如赤池信息量准则(AIC)或贝叶斯信息准则(BIC)自动找到K。X-means需要提供初始的聚类数上下限和这需要一定的经验。

K-medoid[14]算法是由Kaufman和Rousseeuw，2005年提出的优化K均值算法，不同的是该算法初始随机点限定在样本点中且使用数据的中位数而不是平均值来表示类。该算法同样需要人工输入K值，且其时间复杂度为O(ktn2)，t为迭代次数，复杂度不适用于大型数据集。

谷歌公司的D.Sculley在2010年提出的Mini-BatchKMeans[15]聚类算法，该算法使用了一种叫做MiniBatch(分批处理)的方法对数据点之间的距离进行计算。MiniBatch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算，这种思路不仅应用于K-Means聚类，还广泛应用于梯度下降、深度网络等机器学习和深度学习算法。但由于计算样本量少，所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。实验部分本文对比了该算法。

所有这些扩展算法思路都是由一个或多个算法优化K均值算法，且都引入了一些必须由用户指定的初始算法参数。本文吸收了上述算法的部分思想，同时避免了参数的输入。

3 算法过程

基于对聚类相关算法思想的研究，本文考虑从三方面对聚类算法性能进行优化。①算法是否可以不带随机或者经验性输入参数？②一般情况下如果1成立，则算法复杂度会大幅上升(参考无参的层次聚类)，如何能兼顾1的情况下保障算法复杂度较低。③聚类作为无监督学习对于初步探究数据固有模型有实用价值，如何让聚类算法在超大型数据集中快速有效的发挥作用。

针对上述问题，本文算法考虑利用无参数的层次聚类在抽样数据中找到合适的初始聚类中心；再利用其结果为K均值提供入参聚类完整数据。图1为算法核心步骤动态查找最佳聚类值过程图(图片数据来自本文HandPosture实验)。

图1 迭代后期动态监控各类别内聚耦合程度

监控算法本身是有时间复杂度的，图1的数据集“Hand Postures”有78095个样本点，如果按照一般的凝聚层次方法监控的话，会造成时间复杂度增加。本文算法ABK为了控制时间复杂度与K-means相当，设计了如下所示的方法，虚线框说明了监控算法启动触发条件。需要注意的是，必须监测离群点/异常点(outlier)，否则算法触发点会推迟，严重影响精确度。

图2 算法流程图

图2中评价函数CH是利用本文2.3节介绍的评价模型calinski＿harabaz＿score(CH分数)来计算分数的。

因为ABK算法主要针对的是大型数据集，下面分步介绍ABK算法在大型数据集上工作的步骤。

3.1 数据抽样

首先通过对数据集D={y1，y2，y3，…ym}按比例抽样得到一个子数据集D1={x1，x2，x3，…xn}(D1∈D)。抽样比例按照数据集大小确定，目标是找到一个平衡点，子集即保留了原始数据集统计学特征，也不至于过大导致初值确定过程耗费过大的算力和时间[16]。抽样数一般取样本总体的10%，且100

图3是利用python随机抽样数据示意图，展示了抽样后数据在一定程度上仍保持原有分布模式。

图3 数据正确抽样后仍保持部分原有特征

图3表明，在抽样数据上进行数据原型刻画(比如分类类数和类中心等)，可以一定程度上反映原始数据的特征，为K-means等需要此类参数的算法提供可靠入参。

3.2 算法优化目标及伪代码

本文算法的优化目标函数分析如下：

首先，全部样本点为xi(i∈1，2，…，n)；

确定类间距离L度量方法为“中心距离法”Centroid linkage：

L=‖cs-ct‖

其中S，T为两个类，cs和ct分别是两类中心，若初期单个实例为一类，则中心既实例坐标

初始置全部样本点自为一类，开始迭代(iter)，本来这种迭代只能通过本次迭代的目标函数

∀S，TLST=min{‖cs-ct‖}

找到最小的s、t进行合并操作，无法求全局最优解，本方法将CH(calinski＿harabaz＿score)[17]模型与原算法恰当结合，对每轮迭代后的结果进行类内聚合度和类间离散度的评估。CH算法推导如下，下面是CH主要函数

该函数中m为训练集样本数，k为类别数。Bk为类别之间的协方差矩阵

Wk为类别内部数据的协方差矩阵

其中cq是q类的中心点，cE是全部样本中心点，nq是q类总样本数，tr为矩阵的迹。

最终每轮迭代得到一个s(k)值，保存该值和其对应的标签信息(labels information)。可以明显的看到，类别内部数据的协方差越小、类别之间的协方差越大CH指标s(k)越高，聚类效果越好。

最后，从保存的s(k)值中取最大值对应的结果，就是最终需要自动传递给K均值的参数。算法伪代码如下：

START：

输入抽样D1={x1，x2，x3，…xn}D1={x1，x2，x3…xn}，选定距离度量函数dist(xi，xj)，置聚类C={∅}，选评估函数Estimator，聚类评价记录E={∅}；

Step1：计算类间的距离L(xi，xj)，第一轮时样本(类)集为D1，后续样本集为更新后D*；

Step2：找到最小的距离样本对下标：

λi，j=arg mini，j∈DL(xi，xj).将{xi|i∈λi，j}合并为一个类cλi，j；

Step3：形成新的集合D*=D1λi，j。此时：

C=C∪cλi，j。计算类中心，并入D*，此时：cent(ck)=∑xck/count(ck)，D*=D*∪cent(ck)；

Step4：return新集合D*，聚类结果C，聚类中心cent(ck)。

Step5： while count (C)>=2 do：

将步骤4返回的D*、C作为入参执行步骤1至4，开始进行聚类结果评价，并记录结果：E=E∪Estimator(C)

Step6：若聚类数为1：E=E∪Estimator(C)

break；

Step7：返回聚类评价、聚类结果、聚类中心．

return E，C，cent(ck)．

Step8：取max(E)对应聚类数k=count(CmaxE)，聚类中心作为入参传入K-means，得到完整数据集的聚类结果。

目前，多数高校图书馆电脑设施配置不够高级，软件硬件更新不快，机器严重老化，在借阅过程中经常出错，甚至导致借阅系统混乱，越是借阅高峰期越容易出错，还有报警设备也时好时坏，该响的时候不响，不该响的时候乱叫，使借阅室处于一片混乱状态。再就是借阅室格局单调，进门就是书架，满眼都是书，缺乏人文气氛，使人产生一种拥堵疲惫的感觉，享受不到知识带来的愉悦感。

END

3.3 算法复杂度分析

主要对时间复杂度进行分析。本文算法时间复杂度由改进的层次聚类算法和K-means两部分组成。计抽样数为n，样本总数为N。

本算法层次聚类部分复杂度为O(n3)，迭代后期加入CH评估后，该部分增加的时间复杂度推导如下：

基于CH函数(式(1))的计算方法，得

s(k)=f(Wk，Bk，k，m)(k，m视为常数)

O(s)=O(f(Wk，Bk，k，m))=O(f(Wk，Bk))①

=O(Wk，Bk)②

O(Wk，Bk)=O(Wk)×O(Bk)==O(Wk×Bk)③

∴O(Wk，Bk)=O(C×Bk)=O(N)

推导中运用的一些算法复杂性分析基本运算规则如下：(以下假设f(N)，g(N)是定义在正数集上的正函数。)

①O(C×f)=O(f)

②f=O(f)

③O(f)×O(g)=O(f×g)

假设迭代数为C，根据规则①，推知CH算法的时间复杂度是O(n)，n为样本容量。

在层次聚类算法中添加CH算法，其对时间复杂度的影响符合如下规则：

④O(f)+O(g)=O(max(f，g))

通过以上分析，ABK算法在数据模型刻画阶段与传统层次聚类算法的时间复杂度一至，为O(n3)(计抽样数为n)。

在K-means聚类阶段的时间复杂度是O(ktmn)，总时间复杂度是

O(ABK)=O(n3)+O(ktmN)

面对大型数据集时，n<

4 对比实验

4.1 实验综述

实验的硬件环境为：CPU：Intel-I5处理器、8GB内存。实验的软件环境为：64位Windows10；Python3.6.3。

为了验证算法效率，实验从两方面进行对比：一是对比不同聚类算法在同一数据集上的聚类时间和结果评价，目的是在同一数据集上验证不同算法效率。二是对比不同数据集下各算法的聚类时间、迭代次数和结果评价，目的是查看在不同数据集类型，不同数据规模下同一算法的表现。数据集的选取情况及针对不同数据集的评估方法介绍如下。

1) 有参照(labels＿true)数据集

对于已有划分参照的数据集实验包括2个维度的对比：

①时间效率对比：算法执行时间对比；

②基于外部熵的聚类评估方法[18](external entropy based cluster evaluation measure)：该维度分为以下三个子评分，其中：

C={ci|i=1，2，…，n}为n个待聚类样本；

K={kj|j=1，2，…，m}代表m个聚类；

A={aij}代表第i个样本被分配到第j类。

a)同质性评估(homogeneity)

每个群集只包含单个类的成员，公式如下

其中

b)完整性评估(completeness)

其中

c)两者的调和平均(V-mesure)

其中：若β比1大，则完整性权重大。否则同质性权重大。

2) 无参照数据集

对于没有真实分类参照的数据集将从执行时长和CH分数两个维度，结合PCA降维后的图形化进行对比分析。

3) 实验数据来源

对比实验所用数据集来自于UCI[19]标准数据集和scikit-learn[20]。包括来自sklearn的digits手写字数据集，来自UCI的Mop Cap Hand Postures手势数据集、美国人口普查数据集US Census1990。具体数据集描述如表1所示。

表1 实验所涉及数据集及其描述

4) 本文比对的算法及其参数

本文对比算法均来自Python-sklearn库，如表2所示。表2中算法1、2入参中设置了n＿init为10，该参数使K-means算法以随机中心执行10次并选取其中最好的结果输出。计算迭代次数(iteration)时，只输出最好的这次的迭代次数，故计算实际迭代次数时需要按输出的迭代次数乘以10估算(n＿iter＿*10)。

表2 实验涉及的算法说明

来自sklearn算法4、5、6、7没有输出没有迭代数(n＿iter＿)，不进行迭代次数对比。

下面是不同算法在不同数据集上与ABK效率对比实验结果介绍。

4.2 手写字(digits)数据集对比实验

数据集介绍：手写字数据集是由1797个手写字符组成的数据集，内容是手写的阿拉伯数字1至9，每个字符由8×8的矩阵表示，所以该字符集有64维属性。其聚类目标是10个阿拉伯数字(0至9)，实验结果如表3所示。

表3 各算法在手写字(digits)小型数据集上的聚类结果对比(抽样数：500 是否预处理：否)

表3 中，本文算法的时间效率是8种算法中最高的，比PCA降维后的K-means表现还高22%(0.02/0.09)；而在同质性评分上仅次于自顶向下的层次聚类(-9%)、但时间效率是其7.28倍；完整性评分上仅低于近邻传播(-22%)但时间效率是其100.8倍；两者调和平均V-measure评分上，时间效率是自底向上的层次聚类算法的7.42倍，但评分下降了18%。

评分整体表现上高于除了向下层次聚类算法的其它6种算法，但时间效率在小数据集无法完全体现K-means优势的情况下仍然比向下的层次聚类高7倍。

4.3 手势(hand postures)数据集对比实验

数据集介绍：手势数据集是使用带有位置矢量标记的手套，记录了来自12个用户的5种手势得到的数据集。其聚类目标是5种手势的区分。实验结果如表4所示。

表4 各算法在手势(hand postures)中型数据集上的聚类结果对比

实验表明，在样本数达到7万时，本文算法综合性能优于除了算法2、3的其它6种算法。在这个数据量级上，与算法2时间效率差距较大、但有精确度上的优势；从迭代数可以看出，算法2的迭代数是全部算法里最少的。近邻传播和层次聚类已不适用这种规模的数据集。

图4 手势数据集聚类可视化(1，2维)

本文算法在聚类结果评价上优于算法2、3，正如相关工作中提到的，MiniBatchKMeans会轻微造成精度下降。而PCA用其它属性投影在主属性上进行“预测”则会产生5%左右的误差[21]。图4是在手势数据集上的聚类效果图。

从图中可以看到，蓝色部分由于簇型结构较好聚类基本与原始聚类一致。其它簇的结果稍弱，但红色(red)簇实验效果不理想，该簇类被其它簇类瓜分了部分样本。

4.4 人口普查(USCensus)数据集对比实验

数据集介绍：美国人口普查数据集(USCensus1990raw)来自加州大学欧文分校机器学习库，是从1990年的总体普查样本中的公共用途微数据样本(PUMS)中抽取的百分之一的样本。其属性为68维，包含居民衣食住行等全面的信息。该数据集专门针对聚类，聚类目标为测试本算法效率和可伸缩性。实验结果如表5所示。

表5 各算法在(UScensus1990)人口普查大型数据集上的聚类结果对比

通过表5可以看到，在样本数达到245万时，本文算法时间效率和评分结果比所有参与实验的算法均有提升。尤其是时间效率比算法2提升了12%。PCA降维K均值算法在超大数据集聚类时时间优势丧失且在聚类结果CH分数评价上产生了严重下降(-67.7%)。

该数据集进行可视化时，由于数据集具有68个维度，通过PCA主成分分析后发现该数据集90%以上的方差比集中在三个维度，故进行PCA降维后可视化会较为明显。图5是将245万个点进行PCA，参数n＿components=9(选择进行9维的主成分投影)后得到的聚类效果图，可以清晰的看到，该数据集经过PCA处理后，其簇型结构非常明显。