引 言

聚类是指按照一定的相似性度量准则将物理或抽象对象的集合划分成多组具有同类性质的子类(簇)，同一子类(簇)中的对象相似度较高，而不同子类(簇)中的对象差别较大^[1]。聚类在生态学领域，医学医疗领域，经济学领域，以及电子商务领域等很多领域都有着非常广泛的应用^[2]。不同的领域中，有适用于该领域的聚类算法。基本的聚类算法可分为层次聚类、划分聚类、密度聚类、模型聚类和网格聚类^[3]。K均值聚类算法是一种经典的划分聚类算法，它将对象按照欧氏距离来进行划分。在实际中样本对象之间没有固定的边界，往往会出现某个对象不是确定地属于某一类。

粗糙集理论^[4]是Pawlak提出的一种可以有效处理不确定性问题的方法。Lingras提出了粗糙K均值聚类算法，它能较好地处理无法精确分类的样本数据^[5]。粗糙K均值聚类算法根据样本对象到类(簇)心欧氏距离的不同，将其划分到上近似区域和下近似区域。上近似区域中的样本对象可能属于某类(簇)，下近似区域中的样本对象确定属于某类(簇)，因此粗糙K均值聚类算法能较好地处理无法精确分类的样本数据。粗糙K均值聚类算法存在以下不足：初始质心的选取是随机的，导致聚类结果可能不是全局最优而是局部最优；阈值的选择不合理导致聚类结果的波动性较大；经验权重的设置容易忽略了数据分布的差异性。

国内外文献针对粗糙K均值聚类算法的不足之处进行了研究与改进，文献[6]根据样本密度迭代地选取粗糙K均值算法的初始聚类中心，同时提出根据样本密度给每个样本赋以不同的权重计算类质心，但是没有考虑到，固定经验权重无法很好地适应聚类前期和后期的特点。文献[7]考虑了每个对象的密度和赋予不同的权重，但缺少对上近似和下近似整的体权重的考虑。文献[8]认为在聚类过程中同一类中的各个样本对类心的影响是不相同的，因此针对每一个样本都计算其所属类别的权重，但却没考虑阈值随聚类过程的变化对聚类结果的影响。文献[9]采用遗传算法与粗糙K均值结合虽得到全局最优解，却忽略了固定经验权重无法很好地适应聚类前期和后期的特点。文献[10]采用自适应获得参数的方法，避免了人为设置固定经验权重对算法影响的缺点，提高了算法的准确性，却没考虑到粗糙K均值聚类算法对初始点敏感的缺陷。文献[11]中通过构造Logistic增长曲线来计算下近似区域的权重，但当算法的迭代次数过大时下近似区域的权重几乎不再改变，对于不同的数据集忽略了其数据分布的差异性。

本文在前人对粗糙K均值聚类算法研究的理论基础上进行改进，结合蚁群算法中蚂蚁决策行为时的随机概率选择策略，以及蚁群算法的正负反馈机制，对粗糙K均值聚类算法的初始质心的选择进行优化，以改进基本粗糙K均值聚类算法初始质心随机选择导致聚类结果可能是局部最优而不是全局最优的缺点，同时采用动态调整阈值和相关权重的方法，避免人为设置对算法的影响。

1 粗糙K均值聚类算法

粗糙集的思想为确定属于某个类的样本点在该类的下近似区域中，可能属于某个类的样本点在该类的上近似区域中^[7]。在K均值聚类算法的基础上引入粗糙集的思想，即为粗糙K均值聚类算法。

用xi表示样本点，Ck表示k个类，每个类对应的的上近似表示为Ck¯和下近似表示为Ck̲，类Ck的边界区域表示为CkB，其中CkB=Ck¯-Ck̲，mk表示类心。mk计算公式为

式中：·表示样本点个数；ωl表示下近似区域权重，ωb表示边界区域的权重，且ωl+ωb=1；∅表示空集。

首先将每个xi(i=1,2,⋯,N)分到任意一个Ck(k=1,2,⋯,K)的Ck̲中，之后依照公式(1)计算mk。接下来计算每个xi与各个mk的距离dki，并找出与xi距离最近的mk'，即xi与mk'之间的距离为min(dk'i)。若存在其他mk(k≠k')与xi之间的dki与min(dk'i)之差小于阈值，则把该xi划分到这些类的Ck¯，否则把xi加入到mk'所对应的类Ck'的Ck'̲。再次更新类心，不断循环上述过程，直到每个类的mk不变^[10]。

2 结合蚁群算法的改进粗糙K均值聚类算法

蚁群算法是对真实蚂蚁觅食行为的一种抽象，算法中人为定义的蚂蚁代替了真实的蚂蚁。蚂蚁从一个样本点移动到聚类中心时，根据当前路径信息素量的大小依概率进行选择，蚂蚁在所经过的路径上留下信息素，以此影响本次迭代或者下次迭代蚂蚁选择该路径的概率。而信息素随着时间的推移不断挥发，这使蚂蚁不局限于过去的寻优结果，能跳出局部最优解，发现新的解。

结合蚁群算法中蚂蚁决策行为时的随机概率选择策略以及蚁群算法的正负反馈机制，以此增加聚类结果的多样性，且不断搜索更优结果，在避免算法陷入局部最优解的同时达到改进粗糙K均值聚类算法对初始点敏感的缺陷。同时粗糙K均值聚类算法中下近似与边界区域权重的通过上、下近似元素数来衡量，阈值采取自动获得，都避免了人为设计对聚类结果的影响，以此达到改进粗糙K均值聚类算法的目的。

2.1　随机概率选择策略增加解的多样性

在蚁群算法中，蚂蚁搜索所有样本所属的聚类中心时，根据当前信息素量的大小依概率进行随机选择，某样本与某一聚类中心之间的信息素量越大，该样本点被选择归入该类的概率越大。随机概率选择策略使算法拥有收敛的特性，同时有利于搜索更优的结果，避免算法陷入局部最优。

样本到聚类中心mk的距离dij为欧式距离，启发式函数定义为距离的倒数，即

式中：k=1,2,⋯,K，其中K表示聚类数目；j=1,2,⋯,N，其中N表示数据集中样本总个数。蚂蚁在选择路径时，不仅利用启发式函数，而且用到了样本点与聚类中心之间的信息素。样本与聚类中心之间的信息素分布为τkj，信息素分布在样本和聚类中心之间。

在算法的搜索过程中，样本点被分配到各个聚类中心的概率计算公式为

式中：α为信息素的相对重要程度，β为启发式因子的相对重要程度，M为蚂蚁总数(m∈[0,M])，q∈[0,1]为给定参数，随机产生的rand∈[0,1]，t为迭代次数。allowm(i)为禁忌表之外的样本集合，s为禁忌表中第s个元素，即蚂蚁m所走过的第s个样本。在算法的搜索过程中，为了加快收敛速度和增加搜索的多样性，蚂蚁随机选择一个xi∈allowm(i)作为起始点，之后按照式(3)计算该样本选择各个聚类中心的概率pkj，最后根据轮盘赌的方法确定xi所属的类，并将xi归到相应的类中。之后，蚂蚁再随机选取一个不包含在禁忌表之内的样本，重复上述过程，直到将所有样本遍历，即形成一个解。

2.2　目标函数设计

在算法中所有蚂蚁完成构造解以后，通过目标函数进行评估，每次只保留目标函数值最优的蚂蚁所得到的聚类结果，因此粗糙K均值聚类可视为优化问题，优化的过程即为目标函数最小值的获得，即为最优的聚类结果。

式中：J表示类内距离，用来评价聚类的内聚程度；·2表示欧氏距离；ωlk，ωbk分别为第k簇下近似和边界区域的权重值。在聚类过程中动态地调整下近似与边界区域的权重，可以避免经验权重的设置导致忽略了数据分布的差异性。下近似与边界区域的元素个数可以衡量相对重要度比例

考虑到聚类结果的好坏是由类内距离和类间距离共同作用，即尽量减小类内距离，增加类间距离。故本文采用能有效地均衡类间距离与类内距离的目标函数，当目标函数达到最小值时，得到最优的聚类结果。目标函数的计算公式为

式中：D表示类间距离，用来评价类间分离程度，随着K增加内聚程度下降，而类间分离程度增加。为使类间距离和类内距离达到平衡，ω为类间分离程度权重 ^[11]。

2.3　正负反馈机制

蚁群算法中各条路径上信息素在不断更新，最优路径上不断增加的信息素吸引更多的蚂蚁沿此路径前进，同时新增的蚂蚁在该路径上释放更多的信息素，不断加强该路径的吸引力，形成正反馈机制。差的路径上信息素被加强的程度较弱或者得不到加强，随着信息素不断挥发慢慢失去吸引力，形成负反馈机制^[12]。

正反馈机制将更多的蚂蚁吸引到当前最优的路径上，促进了聚类算法的收敛。但当蚂蚁搜索得到的是局部最优解时，为防止更多的蚂蚁被吸引到该路径导致最终结果为局部最优解，负反馈机制则可以消除正反馈机制的作用。通过正负反馈机制对蚂蚁释放的信息素的作用，使蚂蚁在寻优过程当中，不局限于局部最优解，能不断发现新的解。

蚁群算法中的人工蚂蚁寻优利用的是蚁群的整体信息，即完成一次寻优后才进行残留信息素的全局更新。在蚁群算法中各路径上的信息素更新公式为

式中：JFmin为目标函数取得最小值时的类内距离；Δτkj为信息素的增量；Q为蚂蚁释放的信息素总量；ρ(0<ρ<1)为信息素挥发系数。

2.4　自动获取阈值

阈值T的作用是区分样本属于聚类上近似区域或下近似区域，阈值选择的适当才能确保上、下有充足的样本。阈值的取值使用文献[13]提出的方法，该方法可以自动获得阈值，避免人为设置对算法的影响。

(1) 分别计算所有样本元素与K个聚类中心的距离d(k,j)。

(2) 找出d(k,j)中每列的最小值dmin(j)。

(3) 计算各个样本元素和其他类心的距离与dmin(j)的差值dt(k,j)。

(4) 找出差值矩阵中每列的最小值ds(j)且ds(j)≠0，求这些最小值的平均值dsmean(j)。

(5) 阈值的取值为T=min(dsmean(j))。

其中k=1,2,⋯,K；j=1,2,⋯,N。

2.5　生成新聚类中心

式中：k=1,2,⋯,K；j=1,2,⋯,N；ωlk与ωbk分别表示第k类的下近似权重和边界区域权重。

2.6　算法描述

蚂蚁随机选取一个样本点作为起点，参考启发式函数与路径上信息素的量，按照随机概率选择策略计算该样本选择各个聚类中心的概率，然后根据概率确定应该所属的类。然后蚂蚁再随机选取另外一个样本，重复上述过程，直到蚂蚁遍历所有样本，即形成了一个解。所有的蚂蚁构造完成解之后，使用目标函数评价出最优值并且保留，然后计算下近似区域权重和边界区域权重，最后重新计算各个簇的质心。信息素的更新为全局更新，在算法迭代的过程中，只聚类结果最优的蚂蚁的路径进行信息素增加，其余的蚂蚁的路径进行信息素衰减。

算法具体步骤如下：

(1) 设定各参数的值，初始信息素浓度τkj(0)=1，求阈值。

(2) 初始聚类中心随机选取K个。

(3) 计算dkj及ηkj。

(4) M只蚂蚁按照式(3)搜索方法独立地构造各自的解。

(5) 根据式(5，6)计算下近似权重和边界区域权重，根据式(11)重新计算各个簇的质心。

(6) 如果M只蚂蚁都构造完成各自的解，转步骤(7)，否则转步骤(4)。

(7) 根据式(4，7，8)计算并比较M只蚂蚁求得的目标函数，保存其最优解和最优聚类结果。

(8) 根据式(9，10)进行全局信息素更新。

(9) 若满足结束条件(达到最大迭代次数)，则输出最优解，否则进行迭代，转步骤(3)。

3 实

验

3.1　评价指标

实验将聚类结果与实际通用UCI数据进行比较，以此评价聚类算法的性能的优良。常用的评价方法有准确率指标Rand^[8]和Kappa系数^[14]。

Rand计算公式为

式中nk表示正确划入第k簇的下近似中的样本的个数。聚类结果中的任意一个簇的下近似中，若其中含有k类别的样本数目最多，则认为该集合为第k类数据的分布。

Kappa系数公式如下

式中：nk+表示第k类真实的样本总数，n+k表示第k类被分类的样本总数。

3.2　UCI数据集实验

采用UCI机器学习数据库中的3个经典数据集：Iris，Balance-scale和Wine数据集验证算法的性能，数据集具体信息如表1所示。实验环境为：Windows 7系统，i3处理器，2 GB内存，C语言编程。

实验参数α=1，β=1，ρ=0.9，q=0.9，M=20，T=0.1最大迭代次数Nc=100，Q=100。

为了验证本文算法的性能，分别采用粗糙K均值聚类算法、基于粒计算的粗糙集聚类算法^[10]和本文提出的算法在所选UCI标准数据集上进行20次实验，然后取其平均值进行比较分析。在粗糙K均值聚类算法中ωl和ωb取值的不同会导致类心的变化，影响到聚类结果的准确率。当ωl和ωb取不同值时粗糙K均值聚类结果准确率如图1所示。下近似和边界区域的权重中的一个太大或者太小，都会造成类心的偏移，导致聚类结果准确率不高。因此在本次试验中粗糙K均值聚类算法中的下近似和边界区域权重的取值分别为ωl=0.8，ωb=0.2。

图1 ωl和ωb取不同值对应的聚类结果准确率

Fig.1 Accuracy rate of different ωl and ωb

3种算法在各数据集上聚类结果的准确率和Kappa系数如图2,3,4所示。3种算法在各个数据集上运行时间和迭代次数如图5,6所示。3种算法在各个数据集上运行后下近似中各类的类内距离如图7,8,9所示。

图2 Iris数据集准确率和Kappa系数

Fig.2 Accuracy rate and Kappa of Iris data sets

图3 Balance-scale数据集准确率和Kappa系数

Fig.3 Accuracy rate and Kappa of Balance-scale data sets

图4 Wine数据集准确率和Kappa系数

Fig.4 Accuracy rate and Kappa of Wine data sets

图5 3种算法运行时间

Fig.5 Running time of three algorithms

图6 3种算法运行次数

Fig.6 Running number of three algorithms

图7 Iris数据集收敛曲线

Fig.7 Convergence curves of Iris data sets

图8 Balance-scale数据集收敛曲线

Fig.8 Convergence curves of Balance-scale data sets

图9 Wine数据集收敛曲线

Fig.9 Convergence curves of Wine data sets

通过图2,3,4各项实验结果数据可知，本文算法在聚类准确率、Kappa系数方面有所改进。在Iris数据集上本文算法比粗糙K均值聚类算法与基于粒计算的粗糙集聚类算法的准确率分别提高了13.5%和3.17%，准确率效果显著，Kappa系数也得到了提高。在Balance-scale数据集和Wine数据集上，样本维数增加，本文算法的准确率与Kappa系数依然高于粗糙K均值聚类算法和基于粒计算的粗糙集聚类算法。通过图5和图6可知，本文算法与粗糙K均值聚类算法相比，运行时间和迭代次数都有所下降；本文算法与文献[10]中算法比较，虽然运行时间和迭代次数都略有增加，但是实验结果的准确率和Kappa系数都得到提升，因此为了提升实验结果增加迭代次数和运行时间也是值得的。下近似中各类的类间距离越大，即确定划分到该类的元素越多，算法的准确率越高。由图7,8,9可知，本文提出算法收敛的速度快于粗糙K均值聚类算法，与文献[10]算法相比收敛速度差别不大，但是准确率更高。由此可见，本文算法使用蚁群算法中随机概率选择策略增加解的多样性，使用信息素正负反馈机制促进算法收敛的同时跳出局部最优解，克服粗糙K均值聚类算法对初始点敏感的缺陷。同时根据数据集中数据的特点使用动态调整下近似权重，边界区域权重和阈值的方法，避免了人为设置参数对算法的影响，使得本文算法优于比较的其他算法。

4 结束语

本文提出了一种结合蚁群算法的改进粗糙K均值聚类算法，该算法结合蚁群算法中的随机概率选择策略和正负反馈机制，优化粗糙K均值聚类算法对初始点敏感，导致聚类结果时常是局部最优而不是全局最优的缺陷，以及采用了动态调整下近似与边界区域的权重和算法阈值的方法，克服了人为设置参数对算法的影响。实验证明这种方法，聚类结果的准确率和Kappa系数有很大提高。但该算法还存在着一些不足，如当有新的数据加入时需要在整个数据集上重新聚类。此项不足将是笔者下一步的研究工作重点。

参考文献