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

收稿日期:2008基金项目:安徽省高等学校省级自然科学研究项目（kj2008B092）作者简介：贾瑞玉（1965-），女，副教授,研究方向为计算机图形学、数据挖掘、人工智能;黄义堂（1983-），男，安徽滁州人，硕士研究生，研究方向为智能软件。基于遗传算法的高维离群点检测算法的改进摘要：离群点检测问题在欺诈检测，网络鲁棒性分析，和入侵检测等领域上有着重要的应用，并且大多数应用在高维数据领域中，Aggarwal和Yu提出的基于子空间投影和遗传算法（GA）的离群点检测方法是处理高维数据的一个有效方法。由于该算法的交叉重组过程采用贪心策略选择子串，并且随着变异概率的改变可能导致发现不了一些有意义的离群数据。本文提出一种改进的算法，通过对原算法的交叉过程和变异过程进行适当的改进，提高了检测的精度并不受变异概率改变的影响。关键词：离群点检测；高维数据；遗传算法；交叉；变异Animprovedhigh-dimensionalOutlierdetectionalgorithmBasedongeneticalgorithmJiaruiyu,Huangyitang,Shidondong（EducationalDepartmentKeyLaboratoryofIntelligentComputing&SignalProcessing,AnuiUniversity,Hefei,china230039SchoolofComputerScienceandTechnologyofAnhuiUniversity,Hefei230039）Abstract.:Theoutlierdetectionproblemhasimportantapplicationsinthefieldoffrauddetecti，on,networkrobustnessanalysis,andintrusiondetection.Mostsuchapplicationsaremostimportantforhigh-dimensionaldomainsinwhichthedatacancontainhundredsofdimensions.AggarwalandYu'srecentprojectionofspace-basedandgeneticalgorithm(GA)oftheOutlierDetectionofhigh-dimensionaldataprocessingisaneffectivemethod,becausethealgorithmiscross-restructuringprocessbygreedystringofstrategicoptions,andmutationinthecourseofthismutationprobabilitythatthechangemaynotleadtosomeOutlier.Thispaperpresentsanimprovedmethod,throughthecrossoverandthevariabilityofdueprocessofimprovement,ImprovetheaccuracyofthetestandisnotsubjecttomutationprobabilityofimpactKeywords:outlierdetection；high-dimensionaldata；geneticalgorithm；crossover；mutation1.引言离群数据挖掘通常可以看作三个子问题：①什么样的数据是异常，即离群点的定义；②有效挖掘离群数据的方法；③离群点的意义，即离群挖掘结果的合理解释。[4]到目前为止，离群点还没有一个被普遍采纳的定义，Hawkins对离群定义在一定意义上揭示了离群点的本质：“离群点与其他点如此不同，以至于让人怀疑它们是由另外一个不同的机制产生的。”[1]现有的离群点的定义大多是在Hawkins定义的基础上给出的一个定量化描述。近年来，研究人员提出了大量的离群检测算法，大致可以把它们归纳为以下几类：基于统计的方法、基于密度的方法、基于深度的方法、基于距离的方法和基于偏离的方法。[5]在一些实际的应用中常常要面临这高维的问题，高维空间离群检测与其他数据集的离群检测差别甚大的原因主要有两个：①高维空间数据的稀疏性经常导致所有记录在传统距离的意义上都有可能是离群点。因此，高维空间中很难找到一个通用的离群产生机制；②高维空间中的离群检测算法的计算复杂度通常都比较高，算法的执行效率极低。高维空间中的异常检测通常采用Aggarwal＆Yu提出的高维数据异常检测方法。基本思想是把高维空间投影到子空间，采用演化计算来寻找最优子空间，降低空间的维数，然后利用传统的检测算法来发现异常。具体实现时，高维空间中异常模式的检测通常是非常困难的，一个最简单的办法是考虑数据维的所有可能组合，对所有子空间进行异常模式的搜索。这种方法虽然能找出全局最优的离群点，然而对于具有n个属性的数据集，可能的维数组合数为2n，对于高维数据，这个数字将是一个天文数字，因此算法的执行效率非常差。针对这一缺陷，Aggarwal＆Yu[2,3]运用遗传算法提出了子空间离群点检测方法[2]（简记为Gen°）优化了这个问题的求解，并取得良好效果。但在交叉过程和变异过程仍存在缺陷，检测的精度不够高。在此基础上通过对原算法的交叉过程和变异过程进行适当的改进，提高了检测的精度并不受变异概率改变的影响。2.原算法描述Gen°算法将数据的每一维分成φ个等深度（equi-depth）区间，即数据映像到一维空间上后，每一区间包含相等数量的数据点，占总数据点的f=1/φ。在一个数据集k维子空间中的每一维上各取一个深度区间，组成一个k维立方体D，引入稀疏系数S(D)来表示它的稀疏程度.(D对应的k个属性及取值相当于数据集的一个模式)。，S(D)越小表示D所包含的数据点越少，稀疏系数很小的D对应的模式即为异常模式。稀疏系数S(D)的定义如下：()()(1)kkknDNfSDNff其中，n(D)为立方体D包含的数据点的数目，f=f=1/φ，N为数据集大小.kNf为预期分数，(1)kkNff为标准偏差点。Gen°算法描述：GA的操作对象是字符串，变量与个体之间的映像要通过编码实现，下面简单介绍GA的个体编码。考虑一个n维数据集，第k（k≤n）个属性的取值可能为1～φ或者“*”，“*”表示对该属性的取值不关心。例如对一个四维数据集的二维子空间它的一个可能的二维子空间模式为“*3*9”，这个模式中，第二维和第四维的取值是确定的，而第一维和第三维的取值是不关心的。Gen°中使用前面讨论的稀疏系数计算相应模式的适应度[2]由于本文将在通过对交叉操作和变异过程进行改进，使得改进后的算法能够比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为一子串。②枚举第二类位置的所有可能重组方式（2k′种），选择稀疏系数最小的一种组合方式设置在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交叉过程中，其子串形式有'''(22)2()kkkkk种[3]，其中可能包含了一些稀疏系数很小的子串。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的稀疏系数MinSC。者将s′保留。（2）若s′的稀疏系数MinSC且s的稀疏系数MinSC或者s′的稀疏系数MinSC且s的稀疏系数Min