基于遗传算法的高维离群点检测算法的改进.doc

基于遗传算法的高维离群点检测算法的改进摘要： 离群点检测问题在欺诈检测，网络鲁棒性分析，和入侵检测等领域上有着重要的应用，并且大多数应用在高维数据领域中，Aggarwal 和Yu提出的基于子空间投影和遗传算法（GA）的离群点检测方法是处理高维数据的一个有效方法。由于该算法的交叉重组过程采用贪心策略选择子串，并且随着变异概率的改变可能导致发现不了一些有意义的离群数据。本文提出一种改进的算法，通过对原算法的交叉过程和变异过程进行适当的改进，提高了检测的精度并不受变异概率改变的影响。关键词：离群点检测；高维数据；遗传算法；交叉；变异An improved high-dimensional Outlier detection algorithm Based on genetic algorithmJia ruiyu,Huang yitang,Shidondong（Educational Department Key Laboratory of Intelligent Computing & Signal Processing, Anui University, Hefei, china 230039School of Computer Science and Technology of Anhui University, Hefei 230039 ）Abstract.:The outlier detection problem has important applications in the field of fraud detecti，on, network robustness analysis, and intrusion detection. Most such applications are most important for high-dimensional domains in which the data can contain hundreds of dimensions. Aggarwal and Yus recent projection of space-based and genetic algorithm (GA) of the Outlier Detection of high-dimensional data processing is an effective method, because the algorithm is cross-restructuring process by greedy string of strategic options, and mutation in the course of this mutation probability that the change may not lead to some Outlier. This paper presents an improved method, through the crossover and the variability of due process of improvement, Improve the accuracy of the test and is not subject to mutation probability of impactKey words: outlier detection；high-dimensional data；genetic algorithm；crossover；mutation1. 引言离群数据挖掘通常可以看作三个子问题：什么样的数据是异常，即离群点的定义；有效挖掘离群数据的方法； 离群点的意义，即离群挖掘结果的合理解释。到目前为止，离群点还没有一个被普遍采纳的定义，Hawkins 对离群定义在一定意义上揭示了离群点的本质：“离群点与其他点如此不同，以至于让人怀疑它们是由另外一个不同的机制产生的。”现有的离群点的定义大多是在Hawkins定义的基础上给出的一个定量化描述。近年来，研究人员提出了大量的离群检测算法，大致可以把它们归纳为以下几类：基于统计的方法、基于密度的方法、基于深度的方法、基于距离的方法和基于偏离的方法。在一些实际的应用中常常要面临这高维的问题，高维空间离群检测与其他数据集的离群检测差别甚大的原因主要有两个：高维空间数据的稀疏性经常导致所有记录在传统距离的收稿日期:2008基金项目:安徽省高等学校省级自然科学研究项目（kj2008B092）作者简介：贾瑞玉（1965-），女，副教授,研究方向为计算机图形学、数据挖掘、人工智能;黄义堂（1983-），男，安徽滁州人，硕士研究生，研究方向为智能软件。意义上都有可能是离群点。因此，高维空间中很难找到一个通用的离群产生机制；高维空间中的离群检测算法的计算复杂度通常都比较高，算法的执行效率极低。高维空间中的异常检测通常采用AggarwalYu提出的高维数据异常检测方法。基本思想是把高维空间投影到子空间，采用演化计算来寻找最优子空间，降低空间的维数，然后利用传统的检测算法来发现异常。具体实现时，高维空间中异常模式的检测通常是非常困难的，一个最简单的办法是考虑数据维的所有可能组合，对所有子空间进行异常模式的搜索。这种方法虽然能找出全局最优的离群点，然而对于具有n个属性的数据集，可能的维数组合数为，对于高维数据，这个数字将是一个天文数字，因此算法的执行效率非常差。针对这一缺陷， AggarwalYu运用遗传算法提出了子空间离群点检测方法（简记为Gen）优化了这个问题的求解，并取得良好效果。但在交叉过程和变异过程仍存在缺陷，检测的精度不够高。在此基础上通过对原算法的交叉过程和变异过程进行适当的改进，提高了检测的精度并不受变异概率改变的影响。2. 原算法描述 Gen算法将数据的每一维分成个等深度（equi-depth）区间，即数据映像到一维空间上后，每一区间包含相等数量的数据点，占总数据点的f=1/。在一个数据集k 维子空间中的每一维上各取一个深度区间，组成一个k 维立方体D，引入稀疏系数S(D)来表示它的稀疏程度.(D 对应的k 个属性及取值相当于数据集的一个模式)。，S(D)越小表示D 所包含的数据点越少，稀疏系数很小的D对应的模式即为异常模式。稀疏系数S(D)的定义如下：其中，n(D)为立方体D 包含的数据点的数目，f = f=1/，N 为数据集大小. 为预期分数，为标准偏差点。Gen算法描述：GA 的操作对象是字符串，变量与个体之间的映像要通过编码实现，下面简单介绍GA的个体编码。考虑一个n 维数据集，第k（kn）个属性的取值可能为1或者“*”，“*”表示对该属性的取值不关心。例如对一个四维数据集的二维子空间它的一个可能的二维子空间模式为“*3*9”，这个模式中，第二维和第四维的取值是确定的，而第一维和第三维的取值是不关心的。Gen中使用前面讨论的稀疏系数计算相应模式的适应度由于本文将在通过对交叉操作和变异过程进行改进，使得改进后的算法能够比Gen 更为有效，因此着重介绍交叉过程和变异过程的实现。交叉过程（CrossOver）:常用的交叉方法为两点交叉，即任选一点作为交叉点并交换这点右边的部分。例如两个字符串3*2*1 和1*33*，若选择第3位置为交叉点，那么交叉结果为3*23*和1*3*1。在这个例子中，父串和子串都是五维数据的三维子空间模式。但是，如果交叉发生在第四点之后，两个结果子串为3*2*和1*331，分别对应着五维数据的二维子空间和四维子空间模式。由于异常检测过程中只考虑给定维数的子空间，所以这种两点交叉会产生不合理的结果。因此Gen中对交叉方法作了相应的修改，来保证父串和子串都对应相同给定维数的子空间模式。令k 为指定的子空间维数，对于一对模式阶为k 的字符串s1 和s2，指定串中的一个位置，有以下3 种类型：(1) 在此位置上，两个串都是*(2) 在此位置上，两个串都不是*(3) 在此位置上，两个串中只有一个是*设s 为s1 和s2 交叉生成的一个子串，很明显在第一类位置上，子串s 也是*。假设s1 和s2 含k 个第2 类位置，则s1 和s2 均含有k- k 个第3 类位置，两者总共包含2(k- k ) 个第3 类位置。Gen中字符串s1 和s2 重组过程（Recombine(s1, s2)）（即s1 和s2 交叉过程）描述如下： 设R 为第二类位置的集合（k 个），Q 为第三类位置的集合，s 为一子串。 枚举第二类位置的所有可能重组方式（2 k 种），选择稀疏系数最小的一种组合方式设置在s的对应位置上。 反复选取Q 中第三类位置对应的父串值并设置在s 的相应位置上，使得s 有最小的稀疏系数，直到s 的k 个位置都设置完毕。s 的其它位置设为*。 令s 为s 的补串，s 的每一位置的取值相对于s 来自不同的父串，将s 作为s1 和s2 交叉后的另一个子串。很显然，重组后的交叉过程能够保证子串s 和s 与父串有相同的维（阶）数。变异过程（Mutation）Gen算法的变异过程分两种情况：(1)设s为原字符串s的一个子串，其每一个位置的取值都为*，Gen将s之外的一个位置变为*，同时我们从1到之间选取一个值更改s的一个随机位置的属性值，从而确保子空间的维数不会发生变化。(2)如果变异发生在不是*的位置上，这个位置的属性值就由1到的一个其他值来替代。对于这两种情况，Gen设置两个变异概率p1和p2。P1对应（1）的情况，p2对应（2）的情况，计算它们的平均值p=（p1+ p2）/2来作为Gen的变异概率。3. Gen算法的改进在一对模式阶为k 的字符串（k 维模式）s1 和s2 交叉过程中，其子串形式有种，其中可能包含了一些稀疏系数很小的子串。Gen认为遍历这些子串耗时太多，因此，Gen中的重组过程（Recombine(s1,s2)）只是结合贪心策略，尽可能获取比s1 和s2 稀疏系数小的一个子串s 即可。显然，Gen 在交叉过程中降低了时间复杂度，但由于其在Recombine(s1,s2)过程中只是为了获取一个稀疏系数小的子串s，并没有对s 以外的一些稀疏系数很小的子串（k 维模式）进行判断处理，最终可能丢失相当部分的异常模式，因为s 以外的其它子串中很可能存在一些比s 更优的子串，同时这些子串中包含了一些稀疏系数很小的子串（异常模式）。针对Recombine(s1,s2)的这一不足，本文通过保存s 以外的一些较优的子串（异常模式）并进行判断处理来对Gen进行改进。预置参数MinSC 和异常模式候选集CandSet，在字符串s1和s2 交叉过程中，对交叉得到的子串进行判断处理：如果发现某子串模式的稀疏系数小于MinSC，将该子串模式保存在CandSet。显然，参数MinSC应该根据实际数据集合理设置，尽量比较小。改进后的重组过程为Recombine-1(s1,s2)： 设R 为第二类位置的集合（k 个），Q 为第三类位置的集合，s 为一子串。 枚举第二类位置的所有可能重组方式（2k种），选择稀疏系数最小的一种组合方式设置在s的对应位置上。 用第三类位置的每一种重组方式来扩展s，如果s 的稀疏系数MinSC，则s 为异常模式，将其添加至CandSet。最终选择其中一种重组方式设置在s 的相应位置上，使得s 有最小的稀疏系数。 令s 为s 的补串， s 的每一位置的取值相对于s 来自不同的父串，将s 作为s1 和s2 交叉后的另一个子串。由于对交叉过程中产生的子串进行判断处理，增加了异常模式候选集CandSet，扩大的模式多样性，因此，改进后的算法 与Gen相比更有可能收敛到期望的解。在变异过程（Mutation）中如果p1和p2发生变化，即变异概率p发生变化，很可能导致相当部分的异常模式发生变化，按照上述方法增加变异候选集MutationSet，在发生变异过后将产生的新的字符串保存在MutationSet中，通过将变异前后的字符串的稀疏系数与MinSC进行比较。假设s是s的变异字符串（1）若s的稀疏系数MinSC且s的稀疏系数MinSC且s的稀疏系数MinSC。者将s保留。（2）若s的稀疏系数MinSC或者s的稀疏系数MinSC,者将s替换s。通过上述处理，从而保证查找结果不会因p的变化而发生变化。4. 实验结果及分析实验采用UCI机器学习仓库的数据集。PC 机的配置：3.0G Intel(R)CPU，DDR512M 内存。数据集Breastcancer ,Zoo和Machine 的属性区间个数=2。Gen代表原算法，Gen代表只进行交叉过程改进的算法，Gen代表交叉过程和变异过程都改进的算法。试验结果见表1和表2：表1 Gen和Gen比较数据集Gen（time）Gen（time）Gen（quality）Gen（quality）Breastcancer (14)(m=200, k=4)42s40s-3.54(125),15-3.54(250),20Zoo (18)(m=100,k=4)18s14s-3.00(62),6-3.00(125),9Machine (8)（m=100，k=5）12s9s-3.31(23),12-3.31(96),25表1 中数据集Breastcancer， Zoo 和Machine的属性区间个数=2。结果分析：以Zoo数据集（测试在其18个属性上进行）为例。m：最优异常模式个数，k：子空间维数，交叉概率和变异概率分别取0.5 和0.05，即搜索最优的100个4维异常模式。Gen耗时18秒找到100个4维异常模式，其中包括62个不同的异常模式，稀疏系数均值为-3.00，包含这些异常模式的离群点有6个。Gen耗时14秒找到100个4维异常模式，其中包括125（增加CandSet的缘故）个不同的异常模式，稀疏系数均值为-3.00，包含这些异常模式的离群点有9个.显然Gen比Gen的效率更高，原因在与Gen 在交叉过程中的改进能够找到更多的异常模式，同时Recombine-1(s1,s2)较Recombine(s1,s2)可能得到更优的子串s，使得Gen 中的GA 收敛更快，耗时更少。表1表明Gen比Gen能发现更多的异常模式和离群点。表2 Gen和Gen比较数据集Gen（quality）Gen（quality）Zoo (18)(m=100,k=4,p=0.05)-3.06(125),9-3.00(127),10Zoo (18)(m=100,k=4,p=0.01)-3.00(121),9-3.00(127),10Zoo (18)(m=100,k=4,p=0.002)-2.99(116),7-3.00(127),10表2中数据集Zoo在m、k、交叉概率相等的情况下，对变异概率分别为0.05、0.01、0.002进行比较，发现在Gen中随着变异概率的不同，查找的异常模式和离群点的个数也不同,而在Gen中者不会发生变化，这是因为在变异过程中增加了一个变异候选集，通过再次比较，筛选出一部分发生变异的字符串，确保变异概率的改变不会对