（计算机软件与理论专业论文）高维布尔型异常数据检测和利用神经网络生成模糊规则.pdf

摘要 摘要 本文主要研究了高维布尔型异常数据检测和基于模糊神经网络的模糊 规则生成的问题： 首先，研究的是高维布尔型异常数据检测问题。近年来许多的异常检 测算法都是使用相似度的概念。但是，在高维数据空间中，数据是稀疏的， 相似度的概念就失去了意义。因此，对于高维数据，找出有意义的异常数 据变得非常困难，特别对布尔型高维数据的异常检测，尚未找到理想的方 法。对此本文通过定义反映数据稀疏程度的覆盖系数，采用搜索其低维子 空间的异常模式来检测高维布尔型异常数据，并利用遗传算法来优化搜索 过程，通过实验验证也得到了较好的效果。 其次，研究的是利用模糊神经网络生成模糊推理规则，并通过模糊子 集合并和规则合并的方法，优化了模糊规则基。在这部分中，先对传统的 模糊神经网络进行了改进，通过该改进的模糊神经网络的学习生成了新模 糊推理规则结论的均值和方差的计算公式，并利用该公式生成新的模糊推 理规则。但是这样得到的模糊规则基，存在着规则冗余问题。于是本文又 通过定义模糊子集的相似度，给出了模糊子集合并算法，通过定义核和 y - s a m e ，给出了规则合并的充分条件，同时也给出了规则合并算法，利用 模糊子集合并算法和规则合并算法进行模糊子集合并和规则合并，从而达 到优化的目的。然后对该方法迸行了计算机仿真，结果也比较理想。 关键词异常检测；遗传算法：模糊规则基；模糊子集合并；规则合并 燕山大学工学硕士学位论文 a b s t r a c t i nt h i st h e s i so u t l i e rd e t e c t i o no fh i g hd i m e n s i o n a lb o o l - t y p ed a t aa n d f u z z yr u l eg e n e r a t i o nb a s e d o n n e u r o f u z z yn e t w o r k a r er e s e a r c h e d f i r s t l y ，o u t l i e rd e t e c t i o no fh i g hd i m e n s i o n a lb o o l - t y p ed a t ai s d i s c u s s e d t h e c o n c e p to f s i m i l a rd e g r e ei su s e di nm a n yo u t l i e rd e t e c t i o na l g o r i t h m s ，b u t t h ec o n c e p to fs i m i l a rd e g r e ei si n s i g n i f i c a n ti nt h eh i g hd i m e n s i o n a ld a t as p a c e b e c a u s eo f s p a r s ed a t a t h u s ，i ti sv e r yd i f f i c u l tt h a ts i g n i f i c a n to u t l i e rd a t aa r e f o u n da b o u th i g hd i m e n s i o n a ld a t a e s p e c i a l l y , o u t l i e rd e t e c t i o no f b o o l t y p e d a t ai s n ts t i l lr e s o l v e d s o ，i ti sp r o p o s e dt h a ta n a l g o r i t h m o fo u t l i e rd e t e c t i o n f o rh i g hd i m e n s i o n a ld a t aw h o s ea t t r i b u t e sa r ea l lb o o l e a n i ts e a r c h so u t l i e r m o d ei nl o wd i m e n s i o n a ls u b s p a c eb y d e f i n i n ga c o v e r e dc o e f f i c i e mw h i c hc a n r e f l e c tt h e s p a r s ed e g r e e o fd a t a i nt h i s a l g o r i t h m ，s e a r c h i n gp r o c e s s i s o p t i m i z e db yu s i n gg e n e t i ca l g o r i t h ma n d ag o o de f f e c ti sg o t t e n s e c o n d l y , f u z z yr e a s o n i n gr u l e sa r ec r e a t e db yn e u r o - f u z z yn e t w o r ka n d f u z z y r u l eb a s e sa r eo p t i m i z e db y f u z z y s e tc o m b i n a t i o na n dr u l ec o a l e s c e n t i n t h i sp a r t ，t r a d i t i o n a ln e u r o f u z z yl e a r n i n ga l g o r i t h mi s i m p r o v e d f o r m u l ao f e q u a lv a l u ea n ds q u a r ed i s p e r s i o no f c o n c l u s i o na r eo b t a i n e du n d e rn e w f u z z y r e a s o n i n gr u l e s t h e nn e wf u z z yr e a s o n i n gr u l e sa r ec r e a t e db yn e wa l g o r i t h m b u tt h e r ei sr e d u n d a n tq u e s t i o ni nt h ef u z z yr u l eb a s e sb yu s i n gt h em e t h o d t h u s ，f u z z ys e tc o m b i n a t i o na l g o r i t h mi sp r o p o s e db yd e f i n i n gs i m i l a rd e g r e e o ff u z z ys e t s ，a n df u l lc o n d i t i o n so fr u l ec o m b i n a t i o na n dr u l ec o a l e s c e n t a l g o r i t h m a r eg i v e nb y d e f i n i n gk e r n e la n dy - s a m e ，t h e n r u l e sa r eu n k e d b y t h e t w oa l g o r i t h m si no r d e rt oo p t i m i z er u l eb a s e s ，t h e n , t h ea l g o r i t h mi st r a i l e db y c o m p u t e rp r o g r a m a n dr e s u l ti si d e a lt o o k e y w o r d so u t l i e rd e t e c t i o n ；g e n e t i ca l g o r a h m ；f u z z yr u l e b a s e ；f u z z ys e t c o m b i n a t i o n ；r u l ec o a l e s c e n t i i 第1 章绪论 第1 章绪论 1 1引言 计算机与信息技术经历了半个世纪的发展，给人类社会带来了巨大的 变化与影响。随着人类活动范围的扩展，生活节奏的加快，以及技术的进 步，人们能以更快速、更容易、更廉价的方式获取和存储数据，这就使得 数据及其信息以指数方式增长。人们面对着快速扩张的数据海洋，如何有 效利用这一丰富数据海洋的宝藏为人类服务，业已成为广大信息技术工作 者所关注的焦点之一。但是现在人们所依赖的数据分析工具，却无法有效 的为决策者提供其决策支持所需要的相关知识，从而形成了一种“丰富的 数据，贫乏的知识”之独特现象。 为了解决这一问题，自2 0 世纪8 0 年代开始，数据挖掘技术逐步发展 起来。异常检测是数据挖掘中的一个崭新的领域，异常检测是用于发现“小 的模式”( 相对于聚类) ，即数据集中显著不同于其它数据的对象。 许多数据挖掘算法都试图降低异常数据的影响，或全部消除它们。然 而这就会导致丢失重要信息，因为“一个人的噪音声可能就是一个人的信 号”。换句话说，就是异常数据有时也可能是具有特殊意义的数据。如：在 欺诈检测中，异常数据可能就意味着欺骗行为的发生。因此异常数据检测 和分析是一个有意义的数据挖掘任务，这一挖掘工作就称为异常挖掘。 神经网络系统和模糊系统都是处理不精确的、模糊的信息，都是利用 数值化了的信息来建立特定的非线性映射，但是二者在知识的存储与表达、 计算精度、自适应能力等方面存在很大的差异。神经网络虽然对环境的变 化具有较强的自适应学习能力，但是从系统建模的角度而言，它采用的是 典型的黑箱型的学习模式，因此当学习完成后，神经网络所获得输入输出 关系无法用容易被人接受的方式表示出来。相反，模糊系统是建立在被人 容易接受的“如果- 贝u ”( i f - t h e n ) 表达方法之上。由于模糊系统和神经网络 系统都有其各自的优缺点，所以将神经网络系统和模糊系统有机结合，取 燕山大学工学硕士学位论文 长补短，已成为当前的一个重要的研究“热点”。 在前人研究的基础上，人们发现，怎样从训练数据中设计出最佳的模 糊规则来建立一个合理而且合适的模糊系统模型来适应相应的实际系统是 一个很重要的问题。通常情况下，模糊规则都是由专家或者操作员根据他 们的知识和经验确定的。然而，由于系统的不确定性和复杂性因素的影响， 在设计一个模糊系统模型的时候，人们设计模糊推理规则通常是很困难的， 而且是多变的。所以研究模糊规则生成，建立一个符合实际且有效的模糊 推理系统是很多研究者关注的焦点，也使得越来越多的专家学者投入到这 个领域中来，并做出了卓有成效的研究成果。 1 2 课题的研究背景和意义 异常检测作为一个正在蓬勃发展的崭新领域，具有广泛的应用。它可 用于欺诈检测，即监测信用卡使用或电信服务中的异常活动行为，还有通 过分析花费较小或较高顾客的消费行为，提出有针对性的营销策略，或在 医疗分析中发现多种医疗方案所产生的不同寻常的反应等。 目前已经开发了许多异常检测算法及方法，例如：基于统计方法、基 于距离方法和基于方差方法等。大部分的异常检测应用是在高维领域中的， 其中的数据可能是上百维的，但是现有的算法应用到这类高维数据中的时 候，往往就表现出了许多的局限性，如计算开销大、效率低、质量不高等。 因此，高维空间中的异常检测方法的研究仍然是重要研究内容。 模糊神经网纠l 】是神经网络和模糊理论发展到一定阶段的必然产物。模 糊神经网络在理论上和应用上都丰富和发展了神经网络和模糊理论，因此， 研究模糊神经网络无论是对神经网络还是模糊理论的进一步完善都有十分 重要的意义。 另外，人们的生产生活中大部分领域都是模糊性的、不精确的，这使 得模糊神经网络在实际的生产生活中有广阔的发展前景，如在军事、航天、 工业控制及财政等领域。研究模糊规则，不仅有理论上的意义，也有实际 应用的价值。特别是模糊规则推理在信息处理、股票分析和解决社会问题 第1 章绪论 等方有着很重要的应用价值，人们可以利用模糊规则提取的方法从大量数 据中找出需要的规则，因此，研究模糊规则的生成问题有着很重要的实际 意义。 1 3 异常检测研究和进展 异常( o u t l i e r ) 检测是数据挖掘中一个崭新的领域，用来发现“小的模 式”，即数据集中的显著不同与其它数据的对象，异常检测在电信和信用卡 欺骗、贷款审批、气象预报、金融领域和客户分类等各种领域都有着广泛 的应用。 尽管异常检测问题已经在统计学领域里得到了广泛研究，通常用户用 某个统计分布对数据点进行建模，在以假定的模型，根据点的分布来确定 是否异常。但是这些方法的最大缺陷是：在许多情况下，用户并不知道这 个数据分布。为了解决这个问题，k n o t t 和n g 2 】提出了基于距离的异常定 义：如果数据集中与点p 的距离小于d 的点的个数不超过k ，那么就称p 为相对于k 和d 的异常，这里的距离可以是任意的度量距离函数。 文献 3 】中引入了d ：异常的概念，并提出了循环嵌套、基于索引和基于 划分的算法。文献【4 中引入了局部异常因子的概念，是对以前的“全局” 异常的改进，认为异常不应该是对象的二进制表示，而是某个度量，并简 单分析了局部异常因子所具有的性质。 文献 5 讨论了一个适合商维数据集的异常检测的方法，该方法通过找 到局部稀疏模式来实现，但不能通过穷举法发现的低维映射来实现。一般 基于距离的异常检测不能克服高维数的影响，该方法可以解决这个问题。 1 4 神经网络综述 人的思维有逻辑性和直观性两种不同的基本方式。逻辑性的思维是指 根据逻辑规则进行推理的过程：它先将信息转化成概念，并用符号来表示， 然后根据符号运算按串行模式进行逻辑推理。这过程可以写成串行的指 燕山大学丁学硕士学位论文 令，让计算机来执行。然而，直观性的思维是将分布式存储的信息并行协 同处理的过程。譬如说，人们常常无意识的将分布在大脑各部位的信息综 合起来，结果是突然间产生想法或解决问题的办法。这种思维方式的根本 之点在于以下两点1 6 j ： ( 1 ) 信息是通过神经元上的兴奋模式分布存储在网络上。 ( 2 ) 信息处理是通过神经元之间同时相互作用的动态过程来完成的。 人工神经网络就是模拟人思维的第二种方式。它是一个非线性动力学 系统，其特色在于信息的分布式存储和并行协同处理。虽然单个神经元的 结构及其简单，功能有限，但大量神经元构成的网络系统所能实现的行为 却是及其丰富多彩的。和数字计算机相比，神经网络系统具有集体运算的 能力和自适应的学习能力。另外，它还有很强的容错性和鲁棒性，善于联 想、综合和推广。 网络的学习能力体现在网络参数的调整上。参数调整方法分为有教师 学习和无教师学习两种基本方式。有教师学习的方式就是网络根据教师给 出的正确输出模式，校正网络的参数，使其输出接近正确模式。这类方式 常采用梯度下降学习方法，如前向神经网络学习算法( 又称为b p 算法) 。而 无教师学习是网络在没有教师直接指点下通过竞争等方式自动调整网络参 数的学习方式，如自适应共振理论【7 】等。 1 5 模糊系统综述 1 5 1 模糊集概述 计算机不能像人脑一样思维、推理和判断，只有当给定准确的信息之 后，计算机才能够做出对错的判断。但人脑即使在只有部分、甚至不完全 对的情况下，也能够进行判断。计算机要模拟人的思维和判断过程，就必 须将人的语言中所具有的多义、不确定的信息定量的表示出来。模糊集的 概念就由此而来。 模糊集打破了传统的精确集只有0 和1 的界限。在精确集中，任一元 4 第1 章绪论 素属于某一集合的程度要么是0 要么是l 。但在模糊集的概念中，任一元素 可同时部分的属于多个模糊子集，隶属关系用隶属程度来表示。例如，3 5 岁的人属于“年轻”的程度为o _ 3 ，属于“中年”的程度为0 6 ，而属于“年 老”的程度为o 1 。显然这种表现方法要比分明集自然，更接近人的表述方 式。模糊集将分明集中0 和l 的边界平坦化，使其更自然。 1 5 2 模糊规则 模糊规则1 8 1 是定义在模糊集上的规则，是对自然或人工语言中的单词和 句子定量建模的有效工具。通过将模糊规则理解为恰当的模糊关系，就可 以研究不同的模糊推理方案，常采用“i f - t h e n ”( 如果，则) 的形式，可 以用来表示专家的经验、知识等。由于模糊规则的表现方式自然，用这种 表达方式比较容易获取专家的经验，同样，计算机的运算结果能表示成模 糊规则的形式，因此它也容易被人理解。 1 5 3 模糊逻辑推理 从已知条件求其结果的思维过程就是推理。模糊逻辑推理 9 】是一种近似 推理，它是从一组模糊规则和已知事实中得出结论的推理过程。例如，假 定有相同的蕴含规则“如果西红柿是红的，那么它是熟的”，而且已知“西 红柿是或多或少有些红”，那么可以推得“西红柿是或多或少有些熟”。这 就是一个模糊推理的过程。 1 5 4 模糊系统 模糊规则和模糊逻辑推理是模糊系统的基础。要表示输入输出的函数 关系，模糊系统除了模糊规则和模糊逻辑推理外，还必须有非模糊化的部 分。非模糊化过程则是将输出模糊子集转化为非模糊的数字量。从理论上 说，模糊系统可以近似任意的连续函数。 模糊的概念和统计学中的概率是不相同的。概率是用来表示随机事件 燕山大学工学硕士学位论文 发生可能性的大小，而模糊的概念则是和语言中的不确定性相关。前者是 客观的，后者是主观的。“明天要下雨”这一事件的不确定性由概率来表示， 但时间到了明天，这一事件则是确定的，如“年轻”这样的不确定性和时 间的经过无关，这是由语言造成的模糊概念。 1 6 模糊神经网络概念和分类 ( 1 ) 模糊神经网络的概念 1o 】在模糊神经元概念的基础上，把由2 个和 2 个以上的模糊神经元相互联结而成的复杂信息处理系统称为模糊神经网 络，简写为f n n 。在一个模糊神经网络中，如果两个神经元之间没有弧线 或箭头把它们连接起来，可以认为它们之间有连接，不过权值为0 。 ( 2 ) 模糊神经网络的分类】模糊神经网络分类是一个比较复杂的问 题。如根据结构可分为前向网络，回路网络等等；根据层次又可分为单层 网络，多层网络等。但是，由于模糊神经元的形式多种多样，如果一个模 糊神经网络是由同一种神经元互连而成，则称为单纯模糊神经网络，否则 称为混合模糊神经网络：根据功能的不同，可以分为逻辑推理类，模式识 别类，模糊联想类等。 近年来推出了各种模糊神经网络模型，其中比较著名的有模糊极大极 小神经网络分类器( f m m ) 、模糊自适应共振理论( f - a r t ) 、模糊学习矢量量 化分类器( f l v q ) 、模糊神经网络( f n n ) 、模糊多层感知机( f m l p ) 等等。 模糊极大极小神经网络( f m m ) 分类器是由美国学者s i m p s o n 于1 9 9 6 年 提出来的，它将模式样本用具有各种极大极小值的“超盒子”模糊集来表 示，模式样本与“超盒子”的关系可以用隶属函数值来表示，且每个“超 盒子”的极大极小值可以用学习的方法来决定。这种信息表达方式可以用 前馈网络的形式来实现，在有标记样本模式分类情况下，可以实现有导师 模式分类。 模糊神经网络( 卧) 是运用模糊数学方法与模糊技术以及神经网络建 立起来的人工系统，它可以进行模糊推理、模糊决策等。f n n 由三部分组 成：输入信息的模糊化处理，神经网络，模糊决策。它采用神经计算的方 6 第1 章绪论 法来获取模糊推理规则。f n n 系统具有推理精度高、适应范围广、泛化能 力强以及容易实现等特点。 模糊多层感知器( f m l p ) 是目前研究和应用最多的一类模糊神经网络之 一，它是用神经网络来构造模糊系统，利用神经网络的学习方法，根据输 入输出的样本来自动设计和调整模糊系统的设计参数，实现模糊系统的自 学习和自适应功能。与m l p 不同的是，f m l p 在结构上是神经网络，但它 在功能上是模糊系统。 1 7 本文的主要内容及组织结构 本课题为自选课题，首先研究的是高维布尔型数据空间异常数据检测 问题。其次研究的是利用模糊神经网络生成模糊推理规则，并通过模糊子集 合并和规则合并的方法，优化了模糊规则基。 本文的结构安排如下： 第1 章简要介绍了本课题的研究背景和意义。对异常检测给予了简单 性的综述，接着介绍了神经网络系统和模糊系统，及模糊神经网络的概念 和分类。最后给出了本文的研究内容和组织结构。 第2 章介绍了异常检测的基础知识。异常检测的定义和分类方法。 第3 章首先介绍了异常检测的相关概念，然后分析了高维数据的异常 检测研究现状，最后给出了一种布尔属性高维数据的异常检测方法。 第4 章介绍传统的模糊神经学习算法及其属性。详细介绍了这种算法 下的模糊规则的基本形式，重点分析了传统的模糊神经学习算法的一些重 要的属性，为后面的研究做准备。 第5 章给出了改进模糊神经学习算法及其属性。一种是基于简单模糊 推理方法基础上的新模糊神经学习算法，给出了它的模糊规则的形式，学 习算法和建立在高斯型隶属函数基础上的新模糊神经学习算法，及其公式 的推导过程；另一种是基于单值型模糊推理方法上的模糊神经的学习算法， 同时也给出了相应的模糊规则的形式和相关算法。本章也分析了这两种算 法在模糊规则基的组织上有什么优缺点，和传统的模糊神经学习算法相比 7 燕山大学工学硕士学位沦文 较，这两种算法避免了弱激活现象的发生。 第6 章提出利用模糊子集和规则合并方法来优化新模糊神经网络学习 算法中的规则基。在这一章中，先分析了常用的模糊神经学习算法中的规 则基的缺点，然后给出了模糊子集合并算法和规则合并的基本理论和规则 合并算法，对冗余的规则基进行了优化。最后针对一个连续的函数利用上 面的方法作出仿真结果，以验证方法的可行性。 第2 章异常检测的基本知识 第2 章异常检测的基本知识 2 1 异常检测简介 异常检测，也叫孤立点检测。h a w k i n s 给出了异常的本质性定义：异常 是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产 生于完全不同的机制。后来研究者们根据对异常存在的不同假设，发展了 许多异常检测算法，大体可以分为基于统计的算法、基于深度的算法、基 于距离的算法、基于密度的算法等。 从2 0 世纪8 0 年代，异常检测问题就在统计学领域里得到了广泛研究， 通常用户用某个统计分布对数据点进行建模，再以假定的模型，根据点的 分布来确定是否为异常。许许多多针对不同分布的异常检测方法发展起来， 他们分别适用于不同的情形：数据分布情况；数据分布参数是否已知；异 常数据数量；异常数据类型。这些方法的最大缺陷是：在许多情况下，用 户并不知道这个数据分布。而且现实数据也往往不符合任何一种理想状态 的数学分布。 r u t s 和r o u s s c c u w 提出了基于深度的算法。根据算法，每一个数据被 映射到一个k 维数据空间上的点，并且每个点被赋予一个特定定义的“深 度”，并根据不同深度将数据划分成不同层次。基于统计学的结论，异常往 往存在于较“浅”的层次中。由于基于深度的算法要求计算k 维数据空间 的凸闭包，复杂度较高，实际上，仅仅当k = 2 或k = 3 时，算法性能才可以 忍受。 a r g r a w a l 和r a g a r a n 在1 9 9 6 年提出过“序列异常”的概念。他们采用 这样一个机制：扫描数据集并观测到一系列相似数据，当发现一个数据点 明显不同于前面的序列，这样的点就被认为异常数据。这个算法复杂度与 数据集大小成线性关系，有优异的计算性能。但是序列异常在对异常存在 的假设太理想化，对现实复杂数据效果不太好。 k n o r r 和n g 在1 9 9 8 年提出了基于距离的异常检测算法。r a s t o g i 和 9 燕山大学工学硕士学位论文 r a m a s w a m y 改进了他们的异常定义，这在后面的小节里将详细讨论。 b r e u n i g 和k r i e g e l 作了将基于密度的聚类算法o p t i c s 与异常检测合 并到一起研究。这个算法的主要计算消耗在聚类的查找上，只需要很小的 额外代价就可以检测到异常。这些研究也奠定了基于密度的异常概念的产 生，在此基础上b r e u n i g 和k r i e g e l 提出了局部异常因子的概念【1 。 到目前为止，提出的异常检测算法对高维数据异常检测效果都不理想。 a g g a r w a l 和y u t ” 提出了一个针对高维数据集进行降维的异常检测新思路， 它把高维数据集映射到低维子空间，根据子空间的映射数据稀疏度来确定 异常数据是否存在。该方法取得了良好的效果，但也存在一些弊端，这将 在后面的章节里详细分析与讨论。 2 2 异常检测方法分类 本节我们介绍几种利用计算机监测出异常数据的一些重要方法，包括 基于统计的异常检测、基于距离的异常检测、基于密度的异常检测和基于 偏差的异常检测。 2 2 1 基于统计的异常检测 基于统计的异常检测方法假设所给定的数据集存在一个分布或概率模 型( 如一个正态分布) ，然后根据相应模型并通过不一致性测试来发现异常数 据。应用这种测试需要了解数据集参数的有关知识( 如数据分布情况) 、分布 参数知识( 如均值和方差) ，以及所预期的异常数据个数。 有两种检测异常数据的基本过程： ( 1 ) 块过程在这种情况下，要么所有被怀疑的对象均作为异常数据， 要么所有对象均作为一致的。 ( 2 ) y u 过程这种过程的一个例子就是内翻过程。其主要思想就是首先 检测最不可能的对象，如果发现其为异常数据，那么其他所有更可能的对 象均可认为是异常数据。否则再对次不可能对象进行检测，如此下去。这 1 0 第2 章异常检测的基本知识 一过程比块过程更有效。 利用统计方法检测异常数据的一个主要不足就是：大多数测试都是针 对单一属性的，而许多数据挖掘问题需要发现多维空间中的异常数据。此 外，统计方法还需要数据集参数的有关知识，如数据分布情况，但在多数 情况下，数据分布是未知的。统计方法也不能保证能够发现所有的异常数 据，尤其在不采用特别的测试方法的时候，或数据不能被任何标准分布所 描述的时候。 2 2 2 基于距离的异常检测 针对统计方法所存在的问题，k n o r r 和n g i l 4 i 提出了基于距离的异常检 测方法。如果数据集d 中的一个对象。是一个基于距离的异常数据，记为 d b ( p d ) ，它表示：若d 中至少有p 部分对象落在对象。大于d 的位置。换 句话说，这里不依赖统计测试，而是将没有足够邻居的对象看作基于距离 的异常数据。基于距离的异常检测避免了过多的计算。 目前已经提出了一些基于此距离定义的异常检测的有效算法，主要有 基于索引的算法、嵌套循环算法、基于单元算法。 k n o r r 和n g 异常定义有着明显的缺陷，输入参数p 和d 很难确定，而 且对于不同的参数d 值，异常个数有很大的不稳定性。这需要用户反复测 试以确定满意的结果。对此，r a s t o g i 和r a m a s w a m y i ”l 提出了一个新的异常 定义。 d ( p ) 表示点p 和它的第k 个最近邻的距离，对某个点p 根据它的d 。( p ) 进行排序，就得到了d 。异常的定义：给定d 维空间中包含n 个点的数据 集、参数1 1 和k ，如果满足d 。0 ) d 。( p ) 的p 点不超过n 1 个，那么就称p 为异常。即如果对数据点根据他们的d o ( p ) 距离进行排序，那么前n 个点就 被看作异常。基于这种改进的异常定义，又产生了改进的基于距离的算法。 循环嵌套算法对每个点p 计算它的第k 个最近邻的距离d o ( p ) ，把具有 极大d “值前n 个点作为异常。上面的算法每次处理一个点p ，那么需要扫 描数据库n 次州为数据点数) 。可以同时对i t l 个点作上面的检测，这样只 燕山火学工学硕士学位论文 需要扫描n m 次。 基于索引的算法用如r + 树的空间索引结构存储，那么可以根据k n n 查询来做修剪简化，减少计算点之间的距离。 基于划分算法的基本思想是：如果某个点的d o ( p ) 较小的话，那么不可 能是异常，可以先对数据集进行划分，然后估计每个划分的d 。( p ) 的上下限， 如果能判定某个划分不可能包含异常的话，那么就可以直接把它删除掉。 基于划分的算法无论是在数据量还是维数增加的时候，性能都是较好 的。但是，数据量可以是十万甚至百万以上，但是这里的维数仅仅可以增 加到1 0 维左右，当真正面对高维数据时，这些算法都是力不从心的。 2 2 3 基于偏差的异常检测 基于偏差的异常检测没有利用统计测试，或基于距离的方法来识别意 外的对象，相反它是通过对一组对象特征进行检查来识别异常数据的。偏 离特征描述的对象就认为是异常数据。因此这种方法中的“偏差”就是异 常。下面我们介绍基于偏差异常检测的两种方法，一种是对一组对象进行 依次比较，另一种是利用o l a p 数据立方的方法。 顺序意外方法与人从一系列相似的对象中识别出不寻常的对象方式类 似。该方法利用了潜在的数据冗余。给定包含n 个对象的数据集s ，构造一 系列子集 sj ，s 2 ，s 。) ，其中2 m n ，并有s s ，s 。 依次对对象间的差异迸行评估，对每个子集，确定该子集与前序子集 差异度的差，光滑因子( s m o o t h i n gf a c t o r ) 最大的子集就是异常集。光滑因子 用来评价从原始数据集中去除一个子集，差异度降低多少。为减少输入数 据的顺序对结果的影响，可以用不同的次序多次重复上述过程，找出其中 光滑因子最大的子集。此方法依赖所使用的差异性计算函数。然而定义差 异性计算函数将由于事先无法知道意外的规律而变得较为困难。根据实际 数据库应用已经排除了寻找统一差异性计算函数的可能。在循环次数不多 的情况下，这个算法复杂度与数据集大小呈线性关系，有优异的计算性能。 但序列异常在对异常存在的假设太过理想化，对现实复杂数据效果不太好。 第2 章异常检测的基本知识 2 3 本章小结 异常检测是数据挖掘中的一个崭新的领域。在这一章罩，首先介绍了 异常及异常检测的概念。异常是在数据集中与众不同的数据，使人怀疑这 些数据并非随机偏差，而是产生于完全不同的机制。异常检测就是挖掘出 这样的数据，它在电信和信用卡欺骗、贷款审批、气象预报、金融领域和 客户分类等方面有着广泛应用。其次，讨论了异常检测的方法分类，异常 检测的主要方法有基于统计的方法、基于距离的方法、基于密度的方法和 基于偏差的方法。 燕山大学工学硕士学位论文 第3 章一种布尔型高维数据空间异常检测方法 3 1 高维数据的异常检测研究现状 在这一节里我们首先说明高维数据异常检测算法的要求。要想有效的 工作，高维数据异常检测算法应满足以下性质： ( 1 ) 我们应该有能够有效的处理高维数据的稀疏度问题的技术： f 2 ) 确定异常的依据而言，它们应该提供解释，如果可能的话，还要决 定出这种依据有意义的概率水平； ( 3 ) 为了说明异常定义的物理意义，它们必须定义出正确的标准： ( 4 ) 异常检测算法应该在维数非常高的问题上依然有效，如果可能的话， 算法应该避免和搜索空间结合考察： ( 5 ) 在确定一点是否为异常时，算法应该提供局部数据的行为的重要信 息。 在以上要求中，有些已经被不同方法实现【l ”捕】，但是仍然没有一个对 高维数据完全有效的。 到目前为止，提出的算法都对高维数据异常检测效果不理想。a g g a r w a l 和y u 讨论了一个高维数据异常检测的方法。它将数据空间的每一维分成 个等深度区间。所谓等深度区间是指数据映射到此一维空间上后，每一区 间包含相等的f = 1 m 的数据点。在数据集的k 维子空间中的每一维上各取 一个等深度区间，组成一个k 维立方体，然后根据立方体的映射数据稀疏 程度来确定异常数据是否存在。 这个方法在许多应用中都取得了良好效果，但是它无法处理布尔型属 性的数据。对于布尔属性数据，它只有两种取值，我们无法把它分成中个 等深度的区间，k 维立方体也就无从建立。该方法在处理数据之前也是先把 布尔型属性预先去掉。我们针对该算法的这点不足，提出了一个专门处理 布尔型属性的高维数据异常检测方法。下一节我们将详细地讨论这个方法。 1 4 第3 章一种布尔型高维数据空间异常检测方法 3 2 布尔属性的高维数据异常检测方法研究 异常检测的大部分应用是在高维领域中的，其中的数据可能是上百维 的。近来许多的异常检测算法都是使用相似度的概念，基于其与其它数据 的关系来发现异常数据的。但是，在高维数据空间中，数据是稀疏的，相 似度的概念就失去了意义。因此，对于高维数据，找出有意义的异常数据 变得非常困难。在这一节里，将给出一种针对所有属性都是布尔型的高维 数据的异常检测方法。其中我们用到了遗传算法来优化求解过程。首先给 出此方法的相关概念的定义。 3 2 1 稀疏模式与异常数据定义 一些诸如聚类和相似度搜索的问题显示了在子空间中检测数据的行 为，可以设计更有效的算法，这是因为数据的不同局部相对于不同的属性 子集可能是密集的。这个观点也适用于异常检测，因为在诸如信用卡欺骗 检测之类的典型应用中，只有属性的子集在检测行为中是有用的，实际上 也只有这样的子集会被异常行为影响。 为了更好的说明这个的观点，我们来看图3 1 中的例子。在例子中给出 了一个高维数据集的四个典型的二维投影。对于各个高维数据，它很可能 在一些典型二维投影中是有结构的，而在其他投影中是噪音。例如图3 1 中的点a 和b ，它们分别在视图( a ) 和视图( d ) 中表现出异常的行为，而在其 他视图中显示了平均行为。在信用卡欺骗的应用环境中，点a 和点b 可能 分别对应着不同种类的欺骗行为，然而如果在所有维中测量距离可能就显 示了平均的行为，因此使用全维的距离标准很难有效的检测高维数据的异 常。 对于所有属性都是布尔型的高维数据集，数据点的分布是十分稀疏的， 很难从全维角度有效的检测异常数据。而且，正如前面讨论的，在高维数 据的实际应用中，异常数据往往只是就属性的子集而言的。例如，在现实 人群中2 0 岁以下的人很多，而糖尿病患者也不少，但是2 0 岁以下就得糖 燕山大学工学硕士学位论文 尿病的却极为罕见，从异常检测角度看，这样的纪录是非常值得关注的。 f a ) 第一种投影 ( a ) t h ef i r s tk i n do f p r o j e e t i o n ( b ) 第二种投影 ( b ) t h es e c o n d k i n do f p r o j e c t i o n ( c ) 第三种投影( d ) 第四种投影 ( c ) t h et h i r dk i n do f p r o j e c t i o n( d ) t h ef o r t hk i n do f p r o j e c t i o n 图3 - 1一组高维数据的几个二维投影 f i g 3 - 1s o m e t w o - d i m e n s i o n s p r o j e c t i o n so f ag r o u po f h i g h - d i m e n s i o nd a t a 这种方法的主要思路就是在子空间中寻找这样的稀疏模式，符合这种 模式的点就是异常数据。因此我们第一步就是要确定并且挖掘出那些异常 模式，一旦异常模式被确定，那么异常就定义为那些符合异常模式的记录。 我们分析一下我们研究的数据集，假设给定一个高维数据集d ，它的 每个属性都是布尔型。我们任取其中的k 维，由于每个属性只有两种取值， 那么在这个k 维子空间中，数据点只会落在2 。个位置上。假设数据集中有 n 个数据点，如果数据均匀分布，那么落在每个位置上的数据点个数的期 望值为n t 2 ，标准差为f ( s ) 的分母。考虑其中个位置s ，设落在s 上的 点的个数为s ( n ) ，我们定义位置s 的覆盖系数如下： 厂( s ) ：1 些! 三丝! ! ：( 3 - 1 ) + 1 2 ( 1 1 2 ) 1 6 第3 章一种布尔型高维数据空间异常检测方法 当f ( s ) 为负数时，说明落在位置s 上的点的个数低于平均值；f ( s ) 越 小，说明落在s 上的点越少。位置s 对应的k 个属性及其取值就相当于数 据集的一个模式，而落在s 上的点就是数据集中符合这个模式的数据。那 么，寻找覆盖系数最小的s 实质就是寻找只有极少数数据点能符合的异常 模式，而这些数据点b 口是高维数据中的异常数据。 高维数据中寻找异常模式是非常困难的，一种简单的办法是对所有数 据的维进行组合，来搜索覆盖系数最小的几个位置，即异常模式，那么落 在这些位置上的数据点的就是异常数据。 这种方法的算法描述为： a l g o r i t h mo u t l i e r d e t e c t i o n ( n u m b e r ：m ，d i m e n s i o n a l i t y ：k ) b e g i n r l = q l = s e to f a l l1 - d i m e n s i o n a l i t y - m o d e ； f o r i = lt o kd o b e g i n r i = r i 一1oq 1 ； e n d ； c o m p u t e r c o v e r e dc o e f f i c i e n t f ( s ) f o r a l le l e m e n t si nr k ； f 2 s e to f me l e m e n t si ni kw i t hm o s t n e g a t i v ec o v e r e dc o e f f i c i e n t s ； 0 2 s e t o f p o i n t sc o v e r e db y f ： r e t u r ni f , o ) ； e n d 它是通过检查所有可能的k 维投影集，来找出具有最负覆盖系数的投 影。它使用了一个自底向上的迭代算法来实际确定候选投影，第i + l 维投影 集通过连接第i 维投影集和所有可能的l 维投影集( 用q 1 表示) 得到的。r ， 表示i 维投影集，最终r k 中具有最小覆盖系数的m 个模式构成集合f ，符 合f 中模式的点就是异常数据集o 。 这种方法虽然思路简单，但是对于它在计算上是站不住脚的。因为它 是对完全空间的彻底搜索，再发现异常模式时是非常慢的，因为随着维数 的增加，异常检测问题的搜索空间将是成指数增长的，它的计算复杂度将 燕山大学1 学硕士学位论文 是无法让人忍受的。为了解决这个问题，把遗传算法引入到我们的异常检 测方法上来优化求解过程。下面先来讨论一下遗传算法。 3 2 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种基于自然选择原理和自 然遗传机制的搜索( 寻优) 算法，它是模拟自然界中的生命进化机制，在人工 系统中实现特定目标的优化i l 。遗传算法的仿效生物的进化与遗传，根据 “生存竞争”和“优胜劣汰”原则，借助选择、交叉、变异等操作，使所 要解决的问题一步步的逼近最优解。与其他优化方法相比，遗传算法以单 一字符串的形式描述所研究的问题，只需利用适应度函数值来进行优化计 算，而不需要函数导数等其他辅助信息，特别适合解决其他科学技术无法 解决或难以解决的复杂问题，是继专家系统、人工神经网络之后又一受青 睐的人工智能新学科分支。 遗传算法主要有以下几个主要特点： ( 1 ) 遗传算法是使用参数的编集，而不是参数本身进行工作； ( 2 ) 遗传算法是在点群中而不是一个单点上寻优： ( 3 ) 遗传算法仅使用问题本身所具有的目标函数进行工作，而不需要其 他任何先决条件和辅助信息； f 4 1 遗传算法使用随机转换规则而不是确定性规则进行工作。 遗传算法主要用于求解组合优化问题及存在不可微的目标函数或约束 条件复杂的非线性优化问题1 2 0 , 2 1 1 ，常规的数学优化技术不能有效地解决， 而遗传算法可以较好的求解这类问题，因而其应用前景和范围很广阔。 为了有效的利用遗传算法来解决我们的高维数据异常检测问题，我们 需要了解遗传算法的各个基本要点【2 2 州】。 ( 1 ) 编码遗传算法的操作对象是字符串，变量与个体间的映射要通过 编码来实现。编码方法的要求个是字符串要反映所研究问题的性质，另 一个是应遵循字符串长度最短、模式阶次最高、模式数目最大等原则。从 理论上可以证明，用二进制编码来描述个体比用k 进制编码能反映更多数 目的基因模式，因此遗传算法中常用二进制编码。 第3 章一种布尔型高维数据空间异常检测方法 f 2 1 适应度函数在遗传算法中，适应度是描述个体的性能的主要指标。 根据适应度的大小，对个体进行优胜劣汰。适应度是驱动遗传算法的动力。 从生物学角度讲，适应度相当于“生存竞争，适者生存”的生物生存能力， 在遗传算法过程中具有重要意义。将优化问题的目标函数与个体的适应度 建立的映射关系，即可以在群体进化过程中实现对优化问题目标函数的寻 优。将目标函数转换成适应度函数一般应遵循两个原则：一是适应度必须 非负，二是优化过程中目标函数的变化方向应与群体进化过程适应度函数 变化方向一致。 ( 3 1 群体初始化群体初始化是指产生第一代一定数量的个体。一般可 先将优化问题的初始解转化为个体，第一代群体中的其余个体是随机产生 的。研究表明，群体的初始化影响遗传过程的收敛速度。如果初始群体选 择恰当，收敛速度较快，否则，收敛速度较慢，甚至很难求得最优解。 ( 4 1 遗传算子一般的遗传算法都包含三个基本算子：选择、交叉和变 异。选择是从一个旧种群中选择生命力强的个体( 适者) 产生新的种群的过 程，对应“自然选择、适者生存”的原则，选择的根据是单个的位串对应 的函数值转换成适值的大小，适值大的被选中的机会就多。通过选择，使 得群体中的优秀个体数目不断增加，接个进化过程朝着更优解的方向进行。 选择概率通常取0 1 0 2 。 遗传算法的有效性主要来自选择和交叉操作，尤其是交叉，在g a 中 起着核心作用。选择虽然可以使可行解群体朝着最优解