.算法分析·
数字技术与应用
一种与k一prototypes混合的蚁群聚类算法的浅探
于斯
(1.华北电力大学河北保定
071000，2.保定职业技术学院河北保定
071000）
摘要；本文介于k-prototypes和效弹聚类算法的优，缺点，持两种算法进行改进后，交普使用，相至弥补，额长进短，形成一种全新的算法，既端短了聚类时间电能形成高效的聚类始采，
关键词；双群聚美算法中图分类号：TP18
1引
k—prelotypes算法
文献标识码，A
文编号：1007-9416(2010)11-0077-02
发现任意形状的，无需计算案类的平均
蚁群算法是20世纪90年代由意大利科学家M.Dorigo等人首先提出的，具有很好的通用性和普棒性，随着蚁群算法的深人研究，后来的科学家们提出了较群聚类算法，目前基于奴群算法的聚类方法从原理上分为四种川；一是源于蚂数觅食的原理，二是源于数堆形成的原理，三是源于蚂蚁自我行为的原理，四是源于蚁巢分类的原理，但无论哪种蚁群聚类算法都存在这样或那样的缺点，为了克服这些缺点，可以尝试着把蚁群聚类算法和其它算法结合，以获得“高质量"的聚类结果。本文就提出在数群案类算法的基础上，交替使用k-prototypes算法，在缩短时间的基础上得到较好的案类结果。
2基于蚊堆形成原理实现聚类的主要思想
将待聚类的数据随机放置在一个二维网格环境中，每个数据占据一个网格，虚拟蚂数随机移动，每只蚂数根据数据与局都环境的相似程度，决定捡起还是放下该数据，相似程度越高检起的概率越小，放下的概率越大，邻城相似函数几(o,)是蚂数捡起或放下数据o,与其观察半径内邻城对象间的平均相似度，公式如下：
0)=max0
ar
dfo.o,)
p V

其中dlo,0,)为对象间的距离，常用欧氏距离或余弦距，α为相似度调整因子，位置r的领城Neigh的面积为sXs，蚂数速度v均匀分布于[1.v],是一个妈数在一个时间单元内沿给定的网格轴线行走的网格单元数。“拉起”、“放下"概率公式为
P, =1Sigmoid(r(o,) P, =Sigmoid(r(o,))
<> <3>
其中 Sigmoid(s)=1-0"
i+ea.c为参数.c
越大，曲线饱和越快，算法收敛越快，这种蚁群聚类算法无需预先设定聚类的族数，可以
万方数据
值，为处理混合数据集提供了可能。但该算法收敛速度很慢，网格精细度会响聚类结果的精细度，
3与k-prototypes混合的蚊群聚类算法
K-prototypes算法是处理混合属性数据的主要聚类算法，但是存在对初始值敏感，参数依赖和易受“噪声"干扰等间题，当然收效速度比蚊群聚类算法要快。因此，要想得到较快且好的聚类结果，需对它们进行改进，并将二者结合。
3.1基本思路
首先利用数效群算法来形成初始，但由于划分时间长，所以在算法收敏之前就终止了算法，致使创建的划分存在错误划分，之后使用k-prototypes算法除去小的分类错误，并分配“自由"对象，即算法停止时仍有单独存在单元格上的对象或蚂蚁仍在搬运的对象，再次继续使用数群算法，这次的数群算法使用在对象堆上，堆同样可以像单个对象一样章起放下，形成新族；最后对于仍未分配的堆再次使用k-prototypes算法，最终得到最佳划分。
3.2关于蚊群聚类算法的改进
改进一3]：传统算法经常花大量时间来寻找合适的数据捡起，导致蚂蚁在多次选代中无负载的空转，降低算法的效率，改进中的蚂数在放下对象后在本次选代中立刻分配一个合适的空闲数据并尝试捡起，如果捡起失败则重新分配，直至捡起合适的数据。
改进二3；传统算法是将蚂数随机的移动到其它位置，这种策略有一定的盲目性，降低算法的效率。改进的算法为：首先查署与：距离为1的位置是否空闲，如果有空闲则在空闲位置放下对象，否则查看与s距离为2的位置是否空闲，反复，直至可视半径产，如果最终没找到空闲位置则将蚂数随机移动到其他位置。
改进三3，传统算法中参数α的确定很围难，也非常重要：α过大，蚂蚁捡起对象围
难而放下对象客易，会使不同的族合成一个；反之，蚂数捡起对象容易而放下对象困难，会阻止同一羡对象的合成，在改进的算法中使用自适应的策略决定α的值，即设参数α的初始值为0.1，在算法运行过程中每 N次选代次考察妈数放下对象失败的次数 N,与N的比值r,,如果r,>0.99，α增加0.0 1,否则减少0.01
改进四：传统的蚁群算法只能“捡起”、“效下"单个数据，对于一个簇进行"捡起”、"放下"有一定难度，故对<1>式中的d(e,o,) 进行改进，由计算欧民距离变为组平均，即：在计算平均相似度时，两个族的距离就是属
于不同赖的所有对象的距离的平均值； dfo.o
Z.o,(其中n,和 n,nz aecoer
，是两个族所包含的样本数)
<4>
3.3与k-prototypes混合的蚊群聚类算法的描述
(1)初始化蚁群中蚂数个数n_anr，最大送代次数M，局部区城边长s，参数α等参数设置和数据预处理，将数据随机置于二维平面上，每只蚂数随机捡起一个自由数据，并移动到平面上一个随机空闲位置：参数V 取三种类型值之一；常数，随机数或递减随机数。
(2)For /=1,2,, M,For J =1,2,-*,n_anf ; ①根据<1>式计算对象的平灼相似性，①如果蚂蚁未负载，根据<2>式计算概率，若P，大于某随机概率，而同时该对象未被其他妈
果妈蚁负载，根据<3>式计算“放下"概率，若P大于某随机概率，根据改进二放在合适位置，④根据改进三更新参数，
(3)For1=1,2,",再，如果某个对象是摄立点或其邻城对象个数小于某一个常数(阀值)，则标记该对象为孤立点，否则给该对象分配一个聚类序号，并递归的将其邻城对象标记为同样的序列号，
(4)当选代次数 (5)拥有间一聚类号的子集中，数值型属性计算数值型属性的平均值，作为初始点的
(下转79页）
Digital technology and application
数字技术与应用
77