一种分类数据的新型人工蜂群聚类算法外文翻译资料

一种分类数据的新型人工蜂群聚类算法

摘要：具有分类性质的数据在现实生活中是无处不在的。但是现存在的一些分类数据的聚类算法倾向于最佳条件，为了处理这个问题，我们在本论文中提出一个新型的聚类算法，ABC-K-Modes 这是一种基于传统K-means聚类算法以及人工蜂群的算法的解决方案。在我们的解决方案中，我们首先介绍一下K-Modes的过程，然后将这个结合人工蜂群算法来处理要分类的数据。因为蜂群中在搜索阶段是由侦查蜂来完成，我们使用批处理的思想来完成这个多源数据的侦查进而加快ABC-K-Modes算法的收敛。ABC-K-Modes算法的表现在一系列与其他在分类数据方面的算法对比的实验下是被接受评估。

Introduction

作为在数据挖掘方面的一种新兴技术，聚类分析已经被应用到了多个领域。比如说信息检索，社交网络分析，隐私保护，图像文本分析以及生物信息学。聚类的目的是把那些具有相似特征的数据放到同一个组里面。把不同特征的放在其他组里面。现存在的聚类算法通常属于下面两种类型，一种是分层，一种是分割。分层聚类算法根据分类和合并的策略分配一组数据到一个嵌套分区，然而分割聚类算法通过优化目标函数将一系列的数据分割到一些列已经定义好的集群中。

中心点聚类算法是一种最有名的分类聚类算法，其中K-Means算法因为其简单以及高效的特点是一种应用的最广泛的中心点算法。考虑到数据的不确定性，模糊型K-Means聚类算法就被发明了出来，K-Means聚类算法和模糊型聚类算法能够处理数字化的对象，但是在现实生活中尤其是在生物信息学更多的是遇见分类数据。举个例子，通过分类属性描述的信息来聚类Twitter用户。为了聚类这些分类的数据，Huang扩展了两个偶痛的算法并把他们定义为·K-Means算法和模糊型K-Means算法，但是出现在这两种算法上的一个问题就是他们都会陷入本地最优条件，为了解决这个问题，许多在聚类过程中采用优化手段的探索性算法被使用。GAs算法，一种以GA算法为基础的聚类方式，包括最基础的遗传性K-Means算法，最快速的K-Means算法，以及遗传性K-Modes算法被发明了出来。在这些以GA算法为基础的算法中，遗传性K-Modes算法最适用于分类数据，除此之外，其他聚类算法通常被用来聚类数字化数据。Selim 和 Al-Sultan为聚类中的问题提出了模拟退火算法，Maulik 和 Mukhopadhyay通过整合模拟退火算法以及人工神经网络提出了一种新型的聚类方式。Sung 和 Jin通过结合包装和释放的过程提出了基于搜索的聚类算法

在过去的二十年里，很少方法被用来模拟动物在觅食行为上的能力，比如鸟和蚂蚁，为了最优化这个问题，这些方法被成功的运用到聚类上面，Shelokar, Jayaraman, 和 Kulkarni提出了蜂群聚类算法来模拟蚂蚁找寻家到食物源所在的位置的最优化路径。Kao, Zahara, 和 Kao 集成了粒子群优化的方法，它模拟了模仿鸟的方式在搜寻空间中找到最佳食物，用K均值程序和Nelder–Mead的单纯搜索方法用于改善集群的性能，和Kao的方法相比，Tunchan 针对集群提供了一种更纯净的粒子群算法，Chuang, Hsiao, 和· Yang 提出了通过整合粒子群算法以及加速收敛速度战略的方法为集群提出了混沌映射的策略，Wan提出了一种优化觅食行为的聚类算法。

在这些年中，调查蜜蜂的觅食行为，包括学习，记忆和信息共享机制，已成为在群体智能一个有趣的研究方向，由蜜蜂群在现实世界的觅食行为的启发，Lucic 和Teodorović推出了蜂群优化启发式，这也被用于解决各种工程和管理问题。Karaboga 和 Basturk 人工蜂群（ABC）算法来处理数值优化问题，通过使用ABC优化策略，Karaboga和Ozturk的提出了一个人工蜂群聚类方法，几乎在同一时间，Zhang, Ouyang和Ning也引入了一个人工蜂群聚类方法，其中Deb的规则被用来指导每个候选食物源的探索方向，然而，大多数的这些启发式方法被设计用于数字数据，因此，它们不适合于处理的分类数据。考虑到在实际应用中分类数据的普及性，这有必要为分类数据来制定基于ABC的聚类算法。

在本文中，我们提出了一种新型人工蜂群聚类分类数据。在我们的方法，我们首先介绍了一步K-模式过程，然后整合人工蜂群启发式来聚类分类数据，对所提出的方法的时空复杂性进行了分析，并与其它流行的方法比较证明了我们方法的有效性。

本文的其余部分安排如下：我们首先回顾了一些相关的工作。 其次是演示我们提出的方法，然后，我们呈现实验结果，表明该方法的优点。最后，我们得出结论并探索未来工作。

相关工作

在本节中，我们首先回顾了K-Means的算法，然后描述人工的蜂群优化的思想。

K-Modes算法是由Huang为聚类分类数据而提出来的，首先，设X={X1，X2hellip;hellip;Xn}表示一个由n个数据对象组成的数据集，一个数据Xi（0lt;ilt;n）其特征在于用m分类对象属性A1，A2hellip;..Am. 每个分类属性Aj具有的值域。其中t是A分类该属性的值，X是以矢量的模式被表示出来。K-Modes算法的目的就是最小化下面那个函数来划分数据集

在这里Ql是指在集群l中最频繁的属性值，他被称为集群l的模式，uil(0lt;uillt;1)是分割矩阵U的元素，K代表集群的个数，dis(xi, Ql)是距离它通过下面的公式得来，

在第二个公示中，alpha;(xij, qlj)被这么定义

Qlj 代表在集群l中第J个分类数据最频繁的属性值，k-modes算法的过程被如下描述。

步骤1.随机从数据集中点macr;x拿起k个数据对象作为集群的最初模式。

步骤2. 将数据对象X分配给集群距离相比于其它在公式（2）模式此数据对象最近的一个的模式，在所有数据被应用到集群以后，更新所有集群的模式

步骤3.在数据对象被分配以后，重新评估的数据对象和当前模式之间的相异度。如果发现该数据对象的最近的模式属于另一个群集，而不是当前的，该数据对象分配给另外一个集群并更新两个集群的模式。

步骤4.一个完整的循环测试X后，如果没有数据对象已经改变集群，终止算法;否则进入第3步。

人工蜂群算法

由Karaboga 和 Bastur k提出的人工蜂群算法因为算法的简单性和数字问题的鲁棒优化而闻明，在ABC算法中，人工蜂群由三种类型的蜜蜂：雇佣蜂，观察蜂和侦察蜂。雇佣蜂获得食物源的信息并将食物源信息分享给在巢穴的观察蜂。侦察蜂查找寻找新的食物源，观察蜂在巢穴等待，并通过雇佣蜂来共享食物来源的信息。人工蜂群有两部分：第一部分是雇佣蜂和第二部分是观察蜂，在牧草选择的模式，三个基本成分（食物来源，雇佣对象，观察对象）和两个行为（招募食物来源和遗弃食物来源）的被给定. 食物来源的值与许多因素有关，例如距离窝的位置，花蜜量和收集此类花蜜的难易程度。雇佣对象包含两个类型的蜜蜂：球探和围观,观察对象也包括两个类型，侦查对象和观察对象。一个食物源只有一只雇佣蜂，从而，雇佣蜂的数目等于的食物源的数量。观察蜂移动到根据一个基于概率的选择策略的食物来源。当食物的花蜜源耗尽，相应雇佣蜂变成了观察蜂。在ABC算法中，开采和勘探过程在一起进行。具体地，雇佣蜂和观察蜂实施开发过程，以及执行侦察兵探索的过程。该蜂群探险和利用了食物来源的方式，最大限度地最终被存储在巢的花蜜量，为一个优化问题，食物源装置意味着可能解决方案，

食物来源的最终花蜜的量衡量了相应对策的数目，并且目的是获得目标函数的最优值。 ABC算法的程序

如下：

步骤1.初始化的食物来源的数目。

步骤2.将雇佣蜂送往食物来源和评估相应花蜜的数额。

步骤3.评估的所有通过未雇佣蜂来选择食物源的可能性，并且每种食物源的概率值是由它的花蜜量来决定（即，相应的解决方案的质量）：越大花蜜量，较高的概率值;

步骤4.将被雇佣蜂带到食物来源：每个蜜蜂会根据步骤3计算的概率选择它的食物来源，利用其食物来源，评估花蜜所获得的食物来源的数量，并应用贪婪的选择过程

步骤5如果它的食物来源变接近没有了，终止雇佣蜂的开发过程，而这个雇佣蜂变成一个侦察蜂;

步骤6：发送侦察员到搜索空间随机寻找新的食物来源;

步骤7 记录下迄今为止发现的最好的食物来源;

步骤8。如果要求得到满足，输出最好的食物来源;否则转到步骤2

我们提出的ABC聚类算法

在本节中，我们首先描述我们提出的ABC聚类方法，然后再讨论复杂性和趋同性。

提出的方法：

在本节中，我们在人工蜂群和K-Modes的方法的基础上提出了一种新的聚类算法。如上述提到的，有人工蜜蜂3钟：雇佣蜂，观察蜂和侦察蜂。对一种食源对应的一个可能的解决方案问题进行优化，并且食物来源的花蜜量量表达相应的解决方案的质量。在聚类，聚类结果取决于聚类中心。当聚类中心是固定的，聚类结果确定。因此，该聚类问题可以看作是聚类中心的优化，和一组聚类中心的对应一个可能的解决方案。对于分类数据聚类，令f={Q1，Q2hellip;hellip;Qk}表示一个食物来源，Q是集群的模式，E（Fi）= E（U，Fi）是客观的成本函数，

，如式（1）式中符号具有相同的含义。 然后，食物来源网络连接的花蜜量由下式给出：

和ABC方法类似，在我们的算法中的人工蜂群有两部分：一般是雇佣蜂，另一半是观察蜂，一个食物源只存在有一个雇佣蜂，雇佣蜂的数目等于解决方式的数目。让Pfs={F1，F2，，，，，fH}表示的食物来源，其中H是的食物源的数目，和fi表示的的第i个食物来源。然后，第i个食物来源被一个旁观者发现的的可能性由下式给出：

对于从当前内存中衍生候选食物来源，我们引入一步到位的K-模式的过程，称为OKM，在我们的算法。该OKM过程基本上在k模式算法的搜索过程中的一个迭代步，它是由雇佣蜂和旁观者来进行的，目的是查找在当前食物附近的临近食物。令fi是当前食物来源，那么OKM由以下两个步骤：

1.最简便的方式分配每个数据对象到集群，进而形成一个分区矩阵U;特别的，如果第i个数据对象属于第l簇Uil= 1;否则UIL= 0，其中，Uil为U的元素之一;

2. 在计算区分矩阵U的基础上计算出一种新的模式，并且这种形式的候选

食物来源。对于蜂群来说，雇佣蜂变成一个侦察蜂时，其食物来源被耗尽。在我们的算法中，我们采用的参数L，它是一个预定的实验中，以控制食物资源是否放弃。如果食物源通过改进试验不能进一步优化，这种食物源就被假设抛弃，相应雇佣蜂变成了球探。让废弃的食物来源为Fi，那么搜索操作寻找新的食物源是由下式给出

其中i2 {1，2,hellip;hellip; H}，和Rand（DOM（X））是在我们的算法中从数据集X随机地选择k个数据对象的动作.，多源的搜索，这是受到批处理启发，加速了算法的收敛。该多源搜索被描述的理念如下：侦察蜂搜索T候选食物源的时间，然后拾取最好的一个作为新的食物来源。

在介绍了相关变量的详细计算公式以后，分类数据的ABC-K-模式聚类算法给出如下：

输入：蜂群大小N，最大循环次数MCN，集群的数量k和L。输出：最好的食物源

1.初始化的随机的食物来源Pfs={F1，F2,. . ，fH};具体地，对于每个食物来源，从数据集X选择k个数据作为集群的模式，设定组的食物来源的开采号码En1= 0，En2=0，Enh= 0。

2.按照公式（4）;评估食物来源NA（f1），NA（f2）的花蜜量NA（f1）, NA（f1） NA（fh），

3.设置CN（周期数）为1;

4.对于每个雇佣蜂 。

a 通过使用一步的kmodes过程OKM生成从当前的食物源和新的食物源“，并设置Eni = Eni 1;

b.根据式（4）评估花蜜量NA（Fi）为食物源 “;

c.如果NA（Fi）gt; NA（Fi），目前的食物源会被新的食物源所取代;否则，目前的食物源将保留。

5.通过公式5来评估每个食物来源的可能性;

6.对于每个旁观者

a 根据所计算可能性将食物源fi作为当前食物源

b通过使用OKM产生从目前的食物源到新的食物源“，然后设置Eni=Eni 1;

c.评估花蜜量fi，也就是NA（Fi）;

d.如果NA（Fi）gt; NA（Fi），目前的食物源会被新的食物源取代;否则，目前的食物来源网络连接保留;

e通过公式（5）更新每个食物源的概率。

7.对于每种食物来源网络，如果Eni数量小于L，这种食物来源被遗弃，以及相应的雇佣蜂变成了球探

8.如果存在一个废弃的食物来源fi，

a.派出侦查蜂根据公式（6）寻找T候选食物来源;

b.评估食物源F1~Ft的花蜜量

c.选择具有最高的花蜜量作为新的食物源，并设置Eni= 0;

d.如果NA（FI）gt; NA（Fi）目前的食物源会被新的食物源取代;否则，目前的食物源将保留。

9. CN = CN 1;

1

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[29040]，资料为PDF文档或Word文档，PDF文档可免费转换为Word