基于人工蜂群智能技术的属性异常点检测*

朱焕雄，刘 波

暨南大学 信息科学技术学院，广州 510630

基于人工蜂群智能技术的属性异常点检测*

朱焕雄，刘 波+

暨南大学 信息科学技术学院，广州 510630

为了解决数据库属性异常点检测方法时间复杂度大并且查准率和查全率不高的问题，提出了新的基于人工蜂群优化技术（artificial bee colony，ABC）和O-measure度量（一种评估属性异常点的度量）相结合的属性异常点检测方法，模拟人工蜂群随机搜索较优的食物源能力发现属性异常点。针对群体智能算法检测属性异常点会陷入局部收敛的缺陷，提出使用模拟退火技术让人工蜂群跳出局部最优解而找到全局最优解的算法。该算法通过蜂群在二维数据平面上搜索食物源,计算所经过路径上的数据项O-measure适应度，从中寻找最优解（即属性异常点）。实验结果表明，所提算法较之前的算法耗时短，且提高了检测的准确率和查全率。

属性异常点；人工蜂群算法；模拟退火；O-measure

1 引言

随着大数据时代的到来，数据质量问题成为人们日益关注的重点。数据库中存在异常属性值就是数据质量问题之一。异常点[1]是数据集中出现与正常的数据集中不一致的数据，往往是错误的数据值，会降低数据的可用性[2]，对数据分析与挖掘产生较大的影响。为此有必要对数据异常点进行检测，其对保证数据的质量具有重要的意义。

异常点（outlier）分为类异常点和属性异常点[1,3]。类异常是指在具有类别属性的数据集中存在的稀有类对象（元组或记录等）[1,3]；属性异常点是指数据集记录中存在错误的属性值或者是偏离正常分布的属性值[1]，这些错误的属性值通常由人为拼写错误或传输过程出错等引起。

文献[4]介绍了一些常用的检测类异常点方法，如基于统计的方法、基于分类的方法、基于聚类的方法等[4]，但是检测类异常点的方法不能直接用于检测属性异常点。因此Koh等人[5]提出采用O-measure、P-measure、Q-measure标准度量来衡量属性异常点，对产生的数据子空间中的每个属性计算这3个标准度量值，使用OODS（outlier detection from data space）算法对属性异常点进行检测，由于算法需要产生数据子空间，检测的时间复杂度相当高。文献[3]将群体智能技术应用在属性异常点检测；文献[6]提出两个数据项集之间相关可信度度量的概念，并利用该度量检测离散型属性孤立点；文献[7]提出基于函数依赖的异常点检测方法；文献[8]采用FP-growth算法挖掘出非频繁数据项集，结合异常度量阈值对异常点检测，但是算法时间复杂度较高；蔡美等人[9]提出基于蚁群算法的属性异常点检测方法，但是容易陷入局部最优。

本文在已有的属性异常点检测算法基础上，拟研究新的属性异常点的检测方法，主要有以下贡献：

（1）提出了新的基于人工蜂群算法的属性异常点检测算法。具体地讲，首先将数据集记录去重，统计相应元组在原数据集中的频数；然后将去重后的数据集记录（不包括频数）映射到一个二维的搜索平面，数据集的每个数据项对应到二维平面上的点；随后充分利用蜂群在二维平面上的局部寻优能力和随机寻优能力寻找最优食物源，每次迭代后将较小的属性O-measure度量值存储到异常结果表中，根据属性的O-measure值越小而属性异常可能性越大的原则[5]，最终发现属性异常点。

（2）为了避免群体智能算法陷入局部最优的情形，本文将模拟退火的机制引入人工蜂群算法中。虽然文献[10]也提出使用模拟退火算法改进人工蜂群算法，但该算法省去了人工蜂群算法中的侦察蜂阶段，在算法执行后期全局搜索能力会受到很大的影响，而本文算法在侦察蜂执行阶段能搜索全局最优解。

（3）通过实验验证了本文提出的人工蜂群智能算法能缩短属性异常点的检测时间，提高算法的查准率和查全率。对提出的人工蜂群算法在检测属性异常点准确性上进行相应的效果分析。

2 人工蜂群算法及相关概念

2.1 人工蜂群算法

人工蜂群算法[11-13]由土耳其学者Karaboga于2005年提出，它通过模拟蜜蜂采蜜觅食的行为而寻找优化问题的解，具有收敛速度快、并行的特征，而且能避免陷入局部最优。人工蜂群算法不仅在解决多维函数优化和组合优化问题上具有优势[11]，在聚类算法中也有相应的应用[13]。谢娟等人[14]提出基于近似梯度引导的人工蜂群搜索策略，曹春红等人[15]提出改进的人工蜂群算法，并用于几何约束问题上。人工蜂群算法中蜜蜂的基本组成主要有：引领蜂、跟随蜂和侦察蜂[11]。引领蜂的数量或者跟随蜂的数量等于蜂群数量的一半，也等于食物源的数量[11]，蜜源的位置表示优化问题的可行解。人工蜂群算法求解问题的步骤如下：

（1）初始化人工蜂群算法参数阶段。设置蜂群的数量、引领蜂的个数、最大迭代次数、limit参数等。

（2）引领蜂阶段。随机分配引领蜂到蜜源的各个位置进行食物源的搜索，每个引领蜂与一个食物源对应，计算引领蜂所在位置食物源的适应度，引领蜂根据式（1）在邻域内搜索新的食物源。当引领蜂搜索到更优的食物源时，更新引领蜂的位置，否则食物源未更新次数加1。

其中，j是随机选择的下标，j∈(1,2,…,D)，D是维数，i∈(1,2,…,SN)，k∈(1,2,…,SN)，SN是蜂群的数量，k表示不同于i的蜜源；α是一个随机参数，α∈[-1,1];NXij表示新的位置；Xij表示原来的位置。

（3）跟随蜂阶段。跟随蜂根据式（2）计算得到的选择概率，选择一个食物源：

其中，fiti表示蜜蜂的适应度值（如O-measure(Ai,t)，见式（4））；N表示食物源的数量。跟随蜂被选中后，也是按照式（1）在其附近寻找更优的蜜源，然后保存更优的食物源。

（4）侦察蜂阶段。当某个食物源未更新的次数达到一定的数量（limit）后，放弃该食物源，食物源所对应的引领蜂变为侦察蜂，然后侦察蜂按照式（3）全局搜索新的未被访问过的数据空间，寻找新的并且更优的食物源。

（5）记录本次迭代后的最优解。

（6）继续执行步骤（2），直到蜂群算法达到收敛状态或者是达到最大的迭代次数为止。

2.2 O-measure的相关概念

定义1（支持度）假设关系R中有m个属性A1,A2,…,Am，S是R上包含属性Au…Av的投影，记作S=πAu…Av(R)。在S中，某个元组s的支持度sup(s)就是该元组s在关系R上对应属性(Au,…,Av)上具有相同属性值的元组个数。

定义2（邻居）对于元组s=＜au…av＞，设属性Av是目标属性，目标属性的邻居记为N(Av,s)，且有N(Av,s)=＜au…av-1＞，即s中不包含属性Av的项。

定义3（属性异常度量O-measure）假设元组s=＜au…av＞，对目标属性Av的O-measure计算公式为：

一个经过处理后的数据集（选取国家、州、城市3个维度）示例如表1所示，对原来的数据集进行相应的预处理操作。首先对数据集进行去重，所谓去重是将相同的元组当作一条记录，然后统计该元组的频数，如果某个元组不存在相同的元组则频数为1。

Table 1 Dataset example表1 数据集示例

在表1中，令元组s=＜美国,纽约,纽约＞，元组t=＜澳大利亚,维多利亚,纽约＞,由式（4）定义可知：

因为O-measure（城市,t）＜O-measure（城市,s），所以“纽约”在元组t中是属性异常点的可能性更大，而在元组s中是属性异常点的可能性较小。

2.3 模拟退火算法

模拟退火算法[16]是一种全局优化算法，采用概率机制来控制解的接受与否，对于好的解，无条件地接受，反之，以一定的概率接受解。应用到人工蜂群算法中，蜜蜂将有更大的概率搜索到其他更优质的食物源，能很好地避免陷入局部最优解。模拟退火算法需要设置一个初温，算法执行后，温度不断发生变化，在变化过程中，新食物源的位置也是按式（1）产生，引领蜂和跟随蜂在搜索时对较差适应度（O-measure值较大）的食物源具有一定的选择概率，而不采用原始人工蜂群算法的贪心选择策略，扩大食物源的搜索范围。模拟退火算法满足式（5）的条件时会选择较差适应度的食物源。

其中，Fc表示当前食物源的适应度；Fne表示新的食物源的适应度；Temp(t)表示当前时刻的温度值。每次迭代时温度的更新公式如下：

其中,∂表示改变的因子，一般取∂∈(0.9,1.0)；Temp(t)表示当前时刻的温度；Temp(t+1)表示下一时刻的温度。

本文采取的方法是在引领蜂和跟随蜂阶段能使用模拟退火算法寻找全局较优解，而不只是贪婪选择较优的解，并且侦查蜂阶段也能够搜索到全局较优解。

3 利用人工蜂群智能属性异常点的检测

3.1 基本思路及IABC_Detection算法

为了模拟蜂群在二维平面上搜索最优解，将预处理后关系型数据集中的每个数据项对应到二维平面图中的一个结点，每个结点由记录所在维度的编号和属性所在维度的编号确定。图1表示表1的数据集（国家、州、城市属性的投影）对应的二维平面，平面上的结点“□”表示数据集中的一个属性值，蜂群可以在该平面图中搜索和寻找较优的食物源时发现属性异常点。图1中的一条路径展示了蜜蜂寻找较优食物源（即属性异常数据）的过程。

Fig.1 Bee's foraging source path图1 人工蜂群搜索食物源过程

将人工蜂群算法和O-measure度量相结合的思路如下：首先，将数据集对应到蜂群可以搜索的二维平面，充分利用蜂群的邻近搜索和随机搜索的觅食能力，在搜索平面中寻找较优的食物源，存储每次迭代后较优属性的O-measure度量值，并将相应的计算结果存入异常结果表中。接着，根据属性的O-measure值的大小找出属性异常点。为了防止群体智能算法在查找属性异常点时陷入局部收敛状态，再将模拟退火技术引入到上述思路中，所提出的算法记为IABC_Detection。

IABC_Detection算法步骤如下：

（1）初始化人工蜂群算法的相关参数，如蜂群的数量为SN，引领蜂的数量为SN/2，算法迭代的次数为t，模拟退火的初始温度等。

（2）引领蜂被随机分配到二维数据平面，然后对每个位置的引领蜂计算它们的适应度（O-measure值），按照模拟退火机制选择适应度较好的食物源，更新异常结果表S或者保存适应度较好的属性值到异常结果表S。

（3）跟随蜂在跟随蜂附近搜索也是按照模拟退火机制选择适应值较好的食物源。

（4）当某个食物源未更新的次数超过limit，则该食物源对应的引领蜂变为侦察蜂，放弃该食物源，侦察蜂进行随机搜索，全局搜索较优的食物源并且评估它们的适应度。

（5）记录本次迭代的最优解，模拟退火算法的温度发生变化。

（6）回到步骤（2），重复执行直到算法收敛或者是算法达到终止条件。

（7）输出属性异常点。

IABC_Detection算法实现的具体说明如下：

在步骤（1）中，初始化参数，如人工蜂群的数量SN，引领蜂的数量、跟随蜂的数量SN/2，算法迭代的次数t，模拟退火的初始温度（一般取1 000）；还有limit参数，算法执行时若食物源的适应度经过limit次都没更新，则该食物源被放弃，且该引领蜂转化为侦察蜂，侦察蜂重新在二维平面进行搜索。此外，引领蜂的数目或跟随蜂的数目与最优食物源的数目相等。

在步骤（2），算法随机分配引领蜂到二维数据平面上，每个引领蜂的位置可以表示为Lij，Lij也表示元组ti中属性Aj的属性值。对每个引领蜂所在的食物源计算适应度（即O-measure），然后在该引领蜂附近按照式（1）搜索更优的食物源，并且计算该食物源的适应度。引领蜂按照模拟退火机制选择适应度较好的食物源存入异常结果表，异常结果表S的结构定义为四元组(T,A,V,M)。其中T是元组的ID，A是目标属性的名称，V是该目标属性A所对应的值，M是目标属性A所对应的O-measure值。在异常结果表S中搜索是否存在元组s，使得元组s满足N(Ak,s[T])=N(Ak,t),s[A]=Ak,s[V]≠t[Ak]。假如存在这样的元组s并且有O-measure(Ak,t)＜s[M]，则更新元组s，其中s[V]=t[Ak],s[M]=O-measure(Ak,t),s[T]=t；否则将四元组(t,Ak,t[Ak],O-measure(Ak,t))插入到表S中。

在步骤（3）中，跟随蜂按照式（1）搜索新食物源，并且计算新食物源的适应度，采用模拟退火机制选择较优的食物源，并且将较优的食物源及其相应的适应度存储到异常结果表S中。

在步骤（4）中，侦察蜂按照式（3）选择蜜源的位置，然后在整个搜索空间进行新的食物源搜索，继续计算这些蜂所对应食物源的适应度，记录本次迭代后得到最优的食物源以及相应的适应度。

在步骤（5）中，记录每次迭代的最优解，模拟退火算法的温度根据式（6）进行相应的变化。

3.2 算法执行的时间复杂度分析

假定数据集元组的个数为n，选择的属性个数是k，总的蜂群个数为a，侦察蜂的个数为g，较优食物源的个数为m，迭代次数为t，算法执行的时间复杂度分析过程如表2所示。

Table 2 Time complexity analysis of algorithm表2 算法时间复杂度计算

由表2的时间复杂度计算可以知道，算法总的时间复杂度为O(mat)，全搜索算法需要双重循环遍历数据集，因此算法的时间复杂度为O(kn2)，对于大规模数据集，kn2≫mat，从而本文算法时间复杂度比全搜索算法的时间复杂度低。

3.3 IABC_Detection算法检测属性异常点的效果分析

人工蜂群算法具有全局寻优能力，并且收敛速度相对较快[17]。设IABC_Detection算法全局搜索寻找优质食物源后找到的解有N个，其中属性异常点的个数为n，非属性异常点的个数为N-n。在原始的人工蜂群算法中，蜂群按照贪婪择优的方法选择食物源[17]，如果新食物源的适应度优于旧食物源的适应度，新的食物源代替旧的食物源；否则保留旧的食物源，当食物源的适应度经过limit次都没改进时，该食物源将被丢弃。人工蜂群算法每一次迭代后将产生局部最优解，当算法执行结束时，在找到的N个食物源中，属性异常点的个数n会大于非属性异常点的个数，因此找到属性异常点的概率(n/N)大于找到非属性异常点的概率(N-n)/N，IABC_Detection算法查准率较高。

引入模拟退火的IABC_Detection算法能找到属性异常点的概率同样较高，即使算法开始时，蜂群会有较大的几率选择差的食物源，但算法总的目标是贪心选择适应度好的食物源作为目标解。

随着数据集的元组数或属性个数增大，当给定蜂群数量一定时，虽然侦查蜂能进行全局搜索，但蜂群在寻找最优食物源的时候仍然可能会出现搜索不到目标解的情形，算法的查全率会受到一定的影响。IABC_Detection算法采用模拟退火机制，能有效地跳出局部最优解，扩大解的搜索范围，从中寻找更多全局较优解。

设蜂群总数为SN，X(0)表示算法运行时的初始解集（每个解集X含有SN/2个解，这也是造成蜂群的数目会影响查全率的因素），X(n)表示迭代第n次蜂群求得的解集，f表示适应度，T表示蜂群从当前解状态移动到下一个解状态。

蜂群在寻找最优食物源时，都是从一个位置移动到新的位置，因此人工蜂群算法的状态转移可以表示为：

又新的解集X(n+1)仅与X(n)有关，{X(n),n∈N+}是有限齐次Markov链，由此得出蜂群移动时概率计算如下所示：

否则P(X,Y)=0。

因为人工蜂群算法结合模拟退火算法之后，都将会选择较优的食物源作为解，所以当给定初始的引领蜂的解，并且蜂群内部进行无数次的迭代后，人工蜂群算法的Markov链种群系列能以概率1收敛于全局属性异常点集合M，如式（9）所示：

4 模拟实验

4.1 实验环境

算法模拟平台为计算机Intel®CoreTMi5-3210 CPU@2.50 GHz，内存2 GB，Windows7 OS，编程语言Java，集成开发环境为eclipse-jee-neon-R-win32。实验以文献[9]所采用的worldclock数据集（http://www.timeanddate.com/worldclock/）的模式为基准，随机产生10、30、50、70万条数据记录，每1万条记录有一个属性错误值。worldclock数据集的属性包括国家、州、城市、所在时区、夏至时北京时差、与北京时差。

为了测试IABC_Detection的有效性，将其与全搜索方法（Full_search）、基于非频繁数据项集的异常点检测方法[8]（Associating detection）、基于ACO算法的属性异常点检测方法[9]（Ant_Omeasure）在相同的数据集条件下进行对比实验。Full_search方法对数据集中每条记录的每个属性计算O-measure值，采用IABC_Detection算法的步骤（2）中更新异常表的规则更新异常结果表S，然后排序筛选出O-measure值小的属性值作为属性异常点。在IABC_Detection算法实验中，一些参数经过测试调整后获得最优结果，如蜂群的数量设置为20～200，迭代次数t为2 000～2 500次，参数limit设置为20～30，O-measure阈值为0.010。

4.2 实验结果及分析

每种算法对数据集执行50次后取平均值作为有效数据，结果如图2、图3、图4所示。算法所使用的查准率和查全率计算公式如式（10）和式（11）所示：

Fig.2 Execution time of different algorithms图2 算法的执行时间对比图

Fig.3 Comparison of recall ratio图3 算法的查全率对比图

Fig.4 Comparison of precision ratio图4 算法的查准率对比图

图2是不同算法的执行时间对比图，结果表明Full_search算法要耗费的时间最多，IABC_Detection算法消耗的时间最少。采用Full_search方法计算属性O-measure值时，时间主要耗费在计算大量正常属性的O-measure值，而且随着数据集增多，全搜索算法寻找属性异常点所需要的时间也将显著增加。而IABC_Detection算法能充分利用蜂群的智能行为，在寻找最优食物源的过程中计算属性的O-measure值，算法在每一次迭代执行后记录找到的最优解，然后将较好的适应度值存入结果集表中，进而找到属性异常点，可以减少对正常属性计算O-measure值的时间。Associating detection算法进行检测需要遍历所有的数据值，因此耗费的时间多。Ant_Omeasure在数据量大时检测时间多于IABC_Detection算法，主要是人工蜂群算法能避免陷入局部最优，收敛速度会比蚁群算法快，同时也能保证查全率。

图3、图4分别给出了几个算法分别在同样的数据集下运行得到的查全率和查准率。实验结果表明，采用全搜索算法，在数据集大时虽能找出属性异常点，但在数据量小时会将许多正确的属性值误判成异常属性；而且全搜索算法对每条记录的每个属性计算O-measure值，会出现很多属性的O-measure值等于2，导致将很多正常的属性值误判成异常属性，造成全搜索算法查准率和查全率不高。IABC_Detection算法的查全率和查准率虽没达到100%，但IABC_Detection算法能充分利用蜂群的智能行为寻找最优食物源的过程寻找属性异常点，提高了属性异常点检测的查全率和查准率；由于蜂群算法采用的是群体智能的思想，算法执行搜索时具有一定的启发性，但也有可能会陷入局部收敛状态，因此也会出现搜索不到属性异常点的情形。而Associating detection算法采用基于非频繁项集异常度量的方法没有O-measure度量值准确，IABC_Detection算法的查全率高于Ant_Omeasure的查全率，是由于IABC_Detection算法能够防止陷入局部收敛，寻找更多的全局较优解。

下面给出IABC_Detection算法中参数值对结果的影响：

（1）O-measure阈值的设定。设定阈值α对异常结果集表S进行裁剪，即当属性的O-measure值大于阈值α时，对结果集表S中相应的数据进行删除。经过反复实验发现，当α=0.010时，算法具有较好的查准率，不会影响找到的异常属性点。

（2）迭代次数t对算法收敛性的影响。初始时，蜂群随机选择食物源，算法的查全率不高，但是随着算法迭代次数增加，当迭代次数增加到2 000次左右时，算法能找到的属性异常点数量将不再有大的变化，算法趋于收敛状态，查全率也趋于稳定。迭代次数对算法收敛性的影响实验结果如图5所示。

（3）引领蜂的数量对属性异常点查全率的影响。因为引领蜂的数量等于蜂群数量的一半，所以算法初始时蜂群数量设置得少，引领蜂的数量就少，最终能检测到的属性异常点就较少。但是当引领蜂的数量接近实际属性异常点个数时，算法趋于收敛状态。即使引领蜂的数量继续增加，算法检测到属性异常点的个数也不会增多，可以使用此特点判断属性异常点的个数。引领蜂的数量对属性异常点查全率的影响实验结果如图6所示。

Fig.5 Recall ratio to different number of iterations图5 迭代次数对查全率的影响

Fig.6 Recall ratio to different number of employed bees图6 引领蜂的个数对查全率的影响

（4）参数limit的设置。当寻找到食物源的适应度经过limit次未发生改变时，该食物源将被丢弃，并且该食物源对应的引领蜂变为侦察蜂，侦察蜂重新在全局搜索空间搜索新的食物源。参数limit如果设置得太大，容易陷入局部最优，但limit设置得太小，算法很难收敛。经实验发现，limit设置在20～30时算法的效果较佳。

4.3 F-score值的比较

为了将本文算法与其他文献对属性异常点的性能评估方法一致，使用F-score度量（见式（12））对数据异常点的检测效率进行评估。分别将本文算法与Full_search、Ant_Omeasure、Associating detection采取同样的数据集进行实验并计算相应的F-score值。表3显示了这些算法对worldclock数据集检测属性异常点得到的平均F-score值，由此表的结果可得出，本文采用改进的人工蜂群属性异常点检测算法效果最好，在数据集大的时候IABC_Detection的检测能避免陷入局部最优解，找到的属性异常点将会更多。

Table 3 F-score values of related algorithms表3 相关算法的F-score值比较表 %

总之，实验结果表明本文提出的人工蜂群算法结合O-measure度量的方法对于属性异常点的检测耗时少，并且提高了查准率和查全率。

5 结束语

本文使用蜂群算法对属性异常点进行检测，利用O-measure度量评估异常属性值，将数据集对应到二维平面，让引领蜂、观察蜂和侦察蜂通过群体智能在二维平面中搜索寻找最优解。针对群体智能算法会陷入局部较优解的情况，将模拟退火机制引入其中，使算法跳出局部最优解状态，找出全局最优解。下一步将研究如何采用并行计算技术让蜂群对海量高维的数据集寻找属性异常点。

[1]Wu Xindong.Class noise vs attribute noise:their impacts,detection and cleansing[C]//LNCS 4426:Proceedings of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining,Nanjing,China,May 22-25,2007.Berlin,Heidelberg:Springer,2007:7-8.

[2]Li Jianzhong,Liu Xuanmin,An important aspect of big data:data usability[J].Journal of Computer Research and Development,2013,50(6):1147-1162.

[3]Liu Bo,Cai Mei,Yu Jiazong.Swarm intelligence and its application in abnormal data detection[J].Informatica,2015,39(1):63-69.

[4]Han Jiawei,Micheline K.Data mining concepts and techniques[M].3rd ed.Fan Ming,Meng Xiaofeng,trans.Beijing:Machinery Industry Press,2012.

[5]Koh J L Y,Lee M L,Hsu W,et al.Correlation-based detection of attribute outliers[C]//LNCS 4443:Proceedings of the 12th International Conference on Database Systems for Advanced Applications,Bangkok,Thailand,Apr 9-12,2007.Berlin,Heidelberg:Springer,2007:164-175.

[6]Liu Bo,Pan Jiuhui.Study of abnormal data detecting method using attribute correlation analysis[J].Systems Engineering and Electronics,2011,33(1):202-207.

[7]Chiang F,Miller R J.Discovering data quality rules[J].Proceedings of the VLDB Endowment,2008,1(1):1166-1177.

[8]Kao L J,Huang Y P,Sandnes F E.Associating absent frequent itemsets with infrequent items to identify abnormal transactions[J].Applied Intelligence,2015,42(4):694-706.

[9]Cai Mei,Liu Bo.Abnormal data detection method based on ant colony algorithm[J].Computer Engineering,2016,42(8):166-169.

[10]Yang Qun,Cao Xiangyu,Gao Jun.Array synthesis on the basis of an improved artificial bee colony algorithm[J].Journal of Microwaves,2014,30(S1):37-40.

[11]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Erciyes University,2005.

[12]Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2008,8(1):687-697.

[13]Karaboga D,Ozturk C.A novel clustering approach:artificial bee colony(ABC)algorithm[J].Applied Soft Computing,2011,11(1):652-657.

[14]Xie Juan,Su Shoubao,Wang Jiwen.Search strategy of artificial bee colony algorithm guided by approximate gradient[J].Journal of Frontiers of Computer Science and Technology,2016,10(12):1773-1782.

[15]Cao Chunhong,Xu Guangxing.Geometric constraint solving based on improved artificial bee colony algorithm[J].Journal of Frontiers of Computer Science and Technology,2015,9(9):1122-1131.

[16]Zhang Defu,Peng Yu,Zhu Wenxing,et al.A hybrid simulated annealing algorithm for solving three dimensional packing problem[J].Journal of Computer Science,2009,32(11):2147-2156.

[17]Ning Aiping,Zhang Xueying.Convergence analysis of artificial bee colony algorithm[J].Control and Decision,2013,28(10):1554-1558.

附中文参考文献：

[2]李建中,刘显敏.大数据的一个重要方面:数据可用性[J].计算机研究与发展,2013,50(6):1147-1162.

[4]Han Jiawei,Micheline K.数据挖掘概念与技术[M].3版.范明,孟小峰,译.北京:机械工业出版社,2012.

[6]刘波,潘久辉.采用属性相关分析的异常数据检测方法[J].系统工程与电子技术,2011,33(1):202-207.

[9]蔡美,刘波.基于蚁群算法的异常数据检测方法[J].计算机工程,2016,42(8):166-169.

[10]杨群,曹祥玉,高军,等.基于改进的人工蜂群算法的阵列综合研究[J].微波学报,2014,30(S1):37-40.

[14]谢娟,苏守宝,汪继文.近似梯度引导的人工蜂群搜索策略[J].计算机科学与探索,2016,10(12):1773-1782.

[15]曹春红,许光星.基于改进人工蜂群算法的几何约束求解[J].计算机科学与探索,2015,9(9):1122-1131.

[16]张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法[J].计算机学报,2009,32(11):2147-2156.

[17]宁爱平,张雪英.人工蜂群算法的收敛性分析[J].控制与决策,2013,28(10):1554-1558.

Outlier Detection Based onArtificial Bee Colony Intelligent Technology*

ZHU Huanxiong,LIU Bo+

College of Information Science and Technology,Jinan University,Guangzhou 510630,China

2017-03,Accepted 2017-06.

In order to solve the problems of high time complexity,low accuracy and low recall in detecting anomaly database attributes,this paper proposes a new method based on ABC(artificial bee colony)and the O-measure metric(i.e.,a kind of attribute outlier evaluation metric)to find out the attribute outliers,which simulates the bee colony behavior of searching for high quality food sources.In view of the local convergence of swarm intelligence algorithm to detect the attribute outliers,this paper presents the approach of finding the global optimal solution by using the simulated annealing technique,making the bee swarm jump out of the local optimal solution.The proposed algorithm calculates the O-measure of each attribute that the bees have walked,and then from the O-measure value result sets,chooses the best food sources(i.e.,the attribute outliers).In comparison with other algorithms,the experimental results show that the proposed algorithm needs less time,and improves the detection precision and recall.

attribute outlier;artificial bee colony algorithm;simulated annealing;O-measure

+Corresponding author:E-mail:ddxllb@163.com

10.3778/j.issn.1673-9418.1703042

*The National Natural Science Foundation of China under Grant No.U1431227(国家自然科学基金);the Foundation of Guangzhou Science and Technology Planning Project under Grant No.201604010037(广州市科技计划基金).

CNKI网络优先出版:2017-06-22,http://kns.cnki.net/kcms/detail/11.5602.TP.20170622.1702.002.html

ZHU Huanxiong,LIU Bo.Outlier detection based on artificial bee colony intelligent technology.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1984-1992.

A

TP18

ZHU Huanxiong was born in 1991.He is an M.S.candidate at Jinan University.His research interests include artificial intelligence and data mining,etc.

朱焕雄（1991—），男，广东梅州人，暨南大学硕士研究生，主要研究领域为人工智能，数据挖掘等。

LIU Bo was born in 1965.She received the M.S.degree in computer application from Central South University in 1991.Now she is a professor at Jinan University.Her research interests include data mining,swarm intelligence and information integration,etc.

刘波（1965—），女，广东阳江人，1991年于中南大学计算机应用专业获得硕士学位，现为暨南大学教授，主要研究领域为数据挖掘，群体智能，信息集成等。