（计算机软件与理论专业论文）基于密度的离群数据挖掘算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 数据挖掘技术是一个从大量数据中发现潜在知识的过程，其主要目的就是从 大量的、不完全的、有噪声的应用中，提取隐含在其中的、人们事先不知道的、 但又潜在有用的信息和知识。离群数据是明显偏离其它数据、不满足数据的一般 模式或行为，与存在的其它数据不一致的数据。当前离群数据挖掘已应用于电信、 金融、气象预报、股票市场、入侵检测等许多领域。离群数据挖掘包括了离群数 据发现和离群数据分析两部分，离群数据分析与背景知识有关，本文着重讨论了 离群数据挖掘中的最关键问题离群数据的发现问题。 本文通过研究不同的离群数据挖掘算法的特点，提出了改进的基于密度的 离群数据挖掘算法，并将改进后的算法应用于网络入侵检测。具体来讲，本文 的研究工作主要包括以下几个方面： 研究了离群数据挖掘的现状及过程、研究离群数据挖掘的意义、离群数 据挖掘与数据仓库的关系。通过对知识发现一般过程的分析，给出了一个典型 的离群数据挖掘系统的整体框架，分析了各模块的功能，并对其中采用的数据 挖掘技术进行了详细的阐述。 全面研究了现有的离群数据挖掘算法，分析了常用的离群数据挖掘算法 的优点和缺点、适用范围。 在现有基于密度的离群数据挖掘算法、d b s c a n 算法和c u r e 算法的 基础上，提出了改进的基于密度的离群数据挖掘算法，实验表明改进后的算法 优越于原算法。 将改进后的算法应用于网络入侵检测，通过检测率和误报率两个方面对 改进的算法进行了评估。 对离群数据挖掘未来的发展方向做了一下展望。 本文通过实验来评估改进算法的性能，其实验数据来源于j 6 唱s a n d e r 的 o p t i c s 算法的实验数据集和k d dc u p l 9 9 9 数据集。实验表明该算法具有很好的 检测效果，总的来说，本文提出的算法在实验中取得了令人满意的效果。 关键词：数据挖掘，离群数据，密度，划分 重庆大学硕士学位论文英文摘要 a b s t r a c t d a t am i n i n gt e c h n i q u ei sap r o c e d u r ei nw h i c hp o t e n t i a lk n o w l e d g ei sd i s c o v e r e d a m o n gal a r g eq u a n t i t yo fd a t a i t sm a i np u r p o s ei s t oe x t r a c tt h ep o t e n t i a lu s e f u l i n f o r m a t i o na n dk n o w l e d g ew h i c hi sh i d d e na n dp r i o ri g n o r a n tf t o mal a r g en m b e r so f u n c o m p l e t e da n dn o i s ya p p l i c a t i o n s o u t l i e rd a t ai st h ed a t aw h i c hi s a l lo b v i o u s l y d e p a r t u r ef i - o mo t h e rd a t a , i td o e sn o ts a t i s f yt h ec o m m o np a t t e r n s o ra c t i o n sa n d d i s a g r e e sw i t ho t h e re x i t i n gd a t a a tp r e s e n t ，o u t l i e rd a t am i n i n gi su s e df o rm a n ya r e a s ， s u c ha st e l e c o m m u n i c a t i o n , f i r l a n c c ，w e a t h e rf o r e c a s t , s t o c km a r k e t ，i n t r u s i o nd e t e c t i o n a n ds oo n o u t l i e rd a t am i n i n gi n c l u d e st w op a r t sw h i c ha r eo u t l i e rd a t ad e t e c t i o na n d o u t l i e rd a t aa n a l y s i s o u t l i e rd a t aa n a l y s i si sr e l a t e d 谢lb a c k g r o u n dk n o w l e d g e t h e m o s tp i v o t a lq u e s t i o n , w h i c hi so u t l i e rd i s c o v e r y , i sd i s c u s s e di nt h i sd i s s e r t a t i o n i nt h i sd i s s e r t a t i o n , t h ea d v a n t a g e so fd i f f e r e n to u t l i e rd a t am i n i n ga l g o r i t h m sa r e s t u d i e d , a ni m p r o v e do u t l i e rd a t am i n i n ga l g o r i t h mb a s e do nd e n s i t yi sr a i s e d , a n di ti s u s e df o rn e t w o r ki n t r u s i o nd e t e c t i o n s p e c i f i c a l l ys p e a k i n g , t h er e s e a r c hh e r em a i n l y i n c l u d e st h ef o l l o w i n ga s p e c t s ： t h ep r o c e s sa n ds t a t u sq u oo fo u t l i e rd a t am i n i n g , t h em e a n i n go fo u t l i e rd a t a m i n i n g , a n dt h er e l a t i o n s h i pb e t w e e no u t l i e rd a t am i n i n ga n dd a t aw a r e h o u s ei s r e s e a r c h e d t h r o u g ht h ea r l a l y z i n go f g e n e r a lp r o c e s so f k n o w l e d g ed i s c o v e r y , at y p i c a l o v e r a l lf r a m e w o r ko fo u t l i e rd a t am i n i n gs y s t e mi sp r o v i d e d , t h ef u n c t i o n so fe a c h m o d u l ea r ea n a l y z e da n dd e t a i ld e s c r i p t i o no fd a t am i n i n gt e c h n i q u e sw h i c hi sa p p l i e d h e r ea r eg i v e n t h ee x i s t i n go u t l i e rd a t am i n i n ga l g o r i t h m sa r es t u d i e dc o m p r e h e n s i v e l y , t h e a d v a n t a g e sa n dd i s a d v a n t a g e sa n dt h es c o p eo fa p p l i c a t i o n so fo u t l i e rd a t am i n i n g a l g o r i t h m sw h i d la r ei ne n m t n o n u s ea r ca n a l y z e d o nt h eb a s eo fe x i s t i n go u t l i e rd a t am i n i n ga l g o r i t h m sb a s e do nd e n s i t y , d b s c a na l g o r i t h m sa n dc u r ea l g o r i t h m s ，an o wi m p r o v e do u t l i e rd a t am i n i n g a l g o r i t h mb a s e d0 1 1d e n s i t yi sr a i s e d , a n dt h ed i f f e r e n to f r e p r o v e da l g o r i t h m sa n d o d 西n a la l g o r i t h m sa l ev a l i d a t e de x p e r i m e n t a l l y t h ei m p r o v e da l g o r i t h mi su s e df o rn e t w o r ki n t r u s i o nd e t e c t i o n , a n dt h e d e t e c t i o nr a t e sa n df a l s ea l a r mr a t e so f t h ei m p r o v e da l g o r i t h m sa r ea s s e s s e d t h ed e v e l o p m e n td i r e c t i o n so fo u t l i e rd a t am i n i n gt e c h n i q u e si nf u t u r ea r e d i s c u s s e d 重庆大学硕士学位论文 英文摘要 t h ea l g o r i t h mi ss i m p l ea n de f f e c t i v ei nt h e o r ya n de x p e r i m e n t t h ep e r f o r m a n c e i se v a l u a t e dt h r o u g he x p e r i m e n t t h ef i r s td a t a s e tw a su s e di nt h ea l g o r i t h mo f o r d e r i n g p o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r ew h i c hw a sp u tf o r w a r db yj 6 r gs a n d e ra n d t h es e c o n dd a t a s e tw a su s e di nk d dc u p l 9 9 9 t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a t t h ea l g o r i t h mi sv e r ys u c c e s s f u la n de f f e c t i v e k e y w o r d s ：d a t am i n i n g , o u t l i e r s ，d e n s i t y , p a r t i t i o n h i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：乓晓称签字日期：b ，7 年 月砷日 学位论文版权使用授权书 本学位论文作者完全了解重庞盍堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 签字日期：坤年s 月牛 导师签名： c 其中c 为某个阈值t h e n s t e p7 ：x 为离群数据，即m 。和4 + 。保持不变，并成为当前的正常和 离群数据集 s t e p8 ： e n d i f s t e p 9 - e n d f o r 因为正常数据对象的数量比离群数据对象的数量大很多，因此，当一个对象 移动到离群数据集后，正常数据对象的分布变化不大。在这种情况下，每个正常 重庆大学硕士学位论文3 离群数据挖掘方法概述 数据对象对正常数据对象的总似然的贡献保持相对不变。此外，如果假定离群数 据对象服从均匀分布，则移动到离群数据集的每个离群数据对象对离群数据的似 然贡献一个固定的量。这样当一个数据对象移动到离群数据集时，数据的总似然 的改变粗略地等于该对象在均匀分布下的概率( 用2 加权) 减去该对象在正常数据 点的分布下的概率( 用1 - 2 加权) 。从而，离群数据集由这样一些对象组成：这些 对象在均匀分布下比在正常对象的分布下具有显著高的概率。 基于统计学手段检测离群数据的主要优点是易于理解，对数据分布满足某种概 率的数值型单变量数据有效，但也有如下的缺点：大多数检验是针对单个属性的， 而许多离群数据挖掘问题要求在多维空间中发现离群数据，而且，统计学方法要 求知道关于数据集参数的知识，如数据分布、分布参数等。但在实际中，数据分 布往往是未知的。统计学方法也不能确保所有的离群点被发现，或者观察到的分 布不能被任何标准的分布来模拟和表示，并且用统计学方法进行离群数据挖掘需 要预先知道离群数据的个数，而这在实际中往往是难以实现的。 3 2 基于距离的离群数据挖掘方法 k n o t t 和n 酽卅提出了一种基于距离的离群数据检测方法，给定的数据集t ， t = t l ，t 2 ，t d ，0 为数据对象，s = s i ，s 2 ，瞄且s t ( 其中p 行) ，若s 中的对 象都远离于0 的距离为d 的邻域( 即i o 一岛| d ) ，则称。为基于距离的离群数据， 表示为d b ( p ，d ) 。采用不同的参数p 和d ，d b ( p ，d ) 离群数据可以表示所有 的基于距离的离群数据。基于距离的离群数据挖掘方法的缺点是输入参数p 和d 很难确定，并且对于不同的参数，结果有很大的不稳定性。这就需要用户反复输 入p 和d 进行测试，以确定一个满意的解；不能给出离群的程度；算法的复杂度 高。这种方法需要用户拥有相当多的领域知识来确定d ，因此，人为干预因素较大。 基于距离的离群数据检测避免了过多的计算。下面介绍几个基于距离的离群数 据挖掘方法j ： 基于索引的算法：给定一个数据集合，基于索引的算法采用多维索引结构 ( 如r - 树、l 一树等) 来查找每个对象。在半径d 内的邻居。设m 为离群数据。 的d 邻域的最大取值个数，那么，一旦对象。的m + 1 个邻居被发现，则。就不是 离群数据。在不考虑建立索引所需要的时间的情况下，此算法在最坏的情况下的 计算复杂度为0 ( p 1 1 2 ) ，其中，k 为数据对象的维数，n 为数据集中数据对象的个 数。 嵌套循环算法：此算法和基于索引的算法有相同的时间复杂度，但它不需 要建立索引结构，以此来最小化输入输出的次数，提高算法的效率。它把内存的 缓冲区域分为两半，把数据集分为若干块。然后以数据块为单位选择装入每个内 1 6 重庆大学硕士学位论文3 离群数据挖掘方法概述 存缓冲区，该算法与基于索引的算法中对对象逐个进行计算相比，输入输出效率 得到一定的改善。 基于单元的算法：此算法是为了避免0 ( n 2 ) 的计算复杂度，它的复杂度 是o ( c + 一) ，其中c 为常数，取决于单元的数目，k 是数据对象的维数。在该方法 中，数据空间被划分为边长等于d 2 j | 的单元。每个单元有两个层面围绕着它， 第一层面的厚度为一个单位，而第二层的厚度为 2 后一l 】个单元。该算法逐个单元 的计算离群数据，而不是逐个对象的计算离群数据。对于给定的一个单元，它累 计三个计数：单元中的对象数目、单元和第一层中对象的数目、单元和两个层次 中的对象的数目。用c 。，来标注行为x 、列为y 的单元，单元的第一层邻域记为 l i ： 厶( q ，) = 乞，i “= 工1 ，v = y 1 ，巴。，e ，) ( 3 5 ) 单元的第二层邻域记为k ： 工2 ( q ，) = g ，i “= 算3 ，= y 3 ，q ，芒厶( e a g ，q ，) ( 3 6 ) 若单元格中数据对象的数量大于某个指定的阈值，则该单元格及其第一邻域中 没有离群数据；若单元格及其第一邻域中数据对象的数量大于指定的阈值，则该 单元格中也不存在离群数据；若单元格及其第一、第二邻域中数据对象的数目小 于指定的阈值，则单元格中的数据对象均为离群数据。 3 3 基于偏离的离群数据挖掘方法 基于偏离的离群数据挖掘【2 5 】没有利用统计方法或基于距离的方法来识别离群 数据对象，而是通过对一组对象的特征进行检查来识别离群数据。基于偏离的离 群数据挖掘是模仿人类的思维方式，在观察一个连续的序列后，即使不清楚的数 据规则，也能快速发现其中一项数据与其它数据的明显不同。 序列异常技术 序列异常技术( s e q u e n t i a le x c e p t i o nt e c h n i q u e ) 模拟了人类从一系列数据对象 推测类似的对象中识别离群数据的方式，已知n 条记录的数据集，可以建立数据 子集：墨，s ：，s 。，由此求出子集间的偏离程度，当偏离程度大于某个阈值时， 即判断当前样本点为离群数据，为了判断偏离程度，引入了以下几个关键概念： 异常数据对象集( e x c e p t i o ns e t ) ：它是离群数据或偏离点的集合，所以也称为 偏离或者离群数据集，去除这些数据对象可以导致其它数据的相异度最大程度的 减少。 相异函数( d i s s i m i l a r i t yf u n c t i o n ) ：对于给定的一个数据集，如果该数据集中两 个对象相似，则相异函数返回值较小，反之，则相异函数返回值较大；一个数据 子集的计算依赖于前一个子集的计算。给定一个n 个对象的数据集协，而，工。) ， 1 7 重庆大学硕士学位论文3 离群数据挖掘方法概述 可能的一个相异度函数是集合中对象的方差： 1 三 一 二芝： 一曲2 ( 3 7 ) 厅百 这里，工是集合中n 个数的平均值。对于字符串，相异度函数可能是模式字符 串的形式( 例如包含通配符) ，它可以用来覆盖目前所见的所有模式。当覆盖目前 所见字符串的模式不能覆盖在s ，却不在s ，的任意字符串时，相异度增加。 基数函数( c a r d i n a l i t yf u n c t i o n ) ：一般是给定数据集合中数据对象的个数。 平滑因子( s m o o t h i n gf a c t o r ) ：也称为平滑系数，它是从原始数据集中去除子 集，相异度减小的量度，该值由集合的势依比例决定。平滑系数最大的子集是异 常数据集。 为了减轻输入顺序对结果的影响程度，在实际应用中以上处理过程可以被重复 若干次，每一次采用子集的一个不同的随机顺序。运用该方法的前提是事先知道 数据的特性，以便确定相异函数。显然，若相异度函数未知或选取不当，就无法 得到满意的结果，因此，其实用性较差。 o l a p 数据立方体技术 利用o l a p 数据立方体进行离群数据挖掘的方法就是利用数据立方体来识别 大面积多维数据集中的异常区域，为了提高效率，偏离的检测和数据立方体的建 立交替进行。如果一个立方体的单元值显著不同于根据统计模型得到的期望值， 该单元被认为是一个异常。 3 4 基于规则的离群数据挖掘方法 基于规则的离群数据挖掘方法【2 6 】是用来在分类数据中进行离群数据挖掘的。定 义条件项c 为数据对象的属性、属性值组成的合取形式。如果对象集合中有s 的 值支持c ，则条件项c 的支持度为s 。如果条件项c 的支持度小于某一阈值( 最大 离群支持度) ，则称c 为离群条件项，所有这些离群条件项的集合c 。称为离群条 件项集，数据对象中与之相对应的数据就是离群数据。 用此种方法发现离群数据可以看作树的搜索问题，根节点为空条件集，第一层 节点由长度为l 的条件项集组成，计算某一条件项的支持度，产生包含此节点且 长度为2 的所有条件项为第二层子节点。其它层叶子节点的产生方法依次类推。 这种算法的计算复杂度与每一层节点的个数、节点的层数有关，设k 为所有最感 兴趣节点的个数，n 为层数，其计算复杂度为o ( k n ) 。k 与数据集的属性的个数、 每个属性的值域有关。另外，k 还与数据集本身的特性( 如数据的分布及相应的分 布参数) 、最大支持度的选取有关。 运用此方法时，应根据数据的特性选取多层最大离群支持度，随层数的增加， 1 8 重庆大学硕士学位论文 3 离群数据挖掘方法概述 最大离群支持度减小；属性的值域范围大，易发现离群数据，属性问有逻辑关系 的数据，更易发现数据间的逻辑错误。 当然，当数据集中错误过多时，错误数据从规则上并不明显偏离其它数据，不 符合基于规则的离群数据的定义，基于规则的分类数据离群数据挖掘算法无法发 现这一类错误数据。 3 5 基于聚类的离群数据挖掘方法 基于聚类的离群数据挖掘方法的基本思想是首先对样本数据集进行聚类操作， 然后检测无法归类的孤立点，这些孤立点就是离群数据，该方法的优点是不需要 样本数据集的知识。 基于聚类的离群数据挖掘可以分为三个子问题： 用聚类算法进行聚类操作，确定类别特征。 常用的聚类算法有以下几种【2 7 】：基于密度的聚类算法( d a l s i t y - b a s e d m e t h o d s ) ，其典型的代表算法有d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法； 基于分裂的聚类算法( p a r t i t i o n i n g - b a s e dm e t h o d s ) ，其典型的代表算法有 k - m e a n s 算法、k - m e d o i s 算法、c l a r a n s 算法；基于层次的聚类算法 ( h i e f 诎i c a lm e t h o d s ) ，其典型的代表性算法有：b r i c h 算法、c u r e 算法、 c h a m e l e o n 算法；基于网格的聚类算法( g r i d - b a s e dm e t h o d s ) ，其典型的代表 性算法有：s t i n g 算法、c l i q u e 算法、w a v e c l u s t e r 算法；基于模型聚类算 法( m o d e l b a s e dm e t h o d s ) 等。 离群数据的定义：根据具体的数据对象的特征及离群数据的涵义，确定离 群数据的度量标准。 挖掘离群数据。 3 6 基于相似系数的离群数据挖掘方法 该方法将数据对象及其属性以矩阵形式表示，计算此矩阵中所有元素两两之间 的相似系数，并将计算得到的相似系数构成相似系数矩阵，然后将相似系数矩阵 的各元素按行求和，所得结果越d , l t j 该数据是离群数据的可能性越大。设定一个 阈值，大于该阈值的数据认为是离群数据【2 剐。此方法思想易懂，对于多目标决策 和综合评价分析中离群数据的发现比较有效，但缺点也很明显，就是建立相似系 数矩阵和求和需要进行大量计算，处理大量数据时效率下降明显。 3 7 离群数据的分析 离群数据挖掘主要包括离群数据检测和离群数据分析两部分。离群数据分析是 1 9 重庆大学硕士学位论文3 离群数据挖掘方法概述 通过对检测到的离群数据进行进一步分析，得出有用的结论或规则，所以说离群 数据检测出来还不是最终的目的，最重要的是分析这些离群数据产生的原因及其 中隐含的知识。 因此，在检测出离群数据后，还要进行以下工作【2 州： 确认该数据是否真实是离群数据； 分析离群数据产生的原因； 对离群数据进行分析，判断其中是否存在潜在有用的知识。 通过离群数据挖掘算法发现的离群数据与普通数据相比有以下几个比较显著 的特点【3 0 】： 稀疏。因为无论基于距离的离群数据发现方法还是基于偏离的离群数据发 现方法，离群数据所在的单位容积内数据数量远远小于普通数据所在的单位容积 内数据的数量。 数量少。离群数据与普通数据在数量上相比，比较少。 一般会有属性异常现象。对于大多离群数据来说，产生离群的主要原因是 某些属性值的异常。 在离群数据分析方法中有一种基于频繁属性的子空间法 3 h ：设 d = d 1 ，0 ：，d 。) ，是离群属性集，d ，是具有l 个属性如，a ：，口，) 的数据对象。首 先在属性集中寻找频繁属性，然后根据对属性频率的统计排序，确定属性子空间 为频繁属性子空间，最后确定的频繁属性子空间中用关联规则分析方法或特征化 分析方法等方法进行常规的知识发现。 3 8 本章小结 离群数据挖掘是一个新兴的研究课题，它是数据挖掘的重要组成部分，它已被 广泛应用于科学研究，如金融欺诈、电信计费、医疗保险、网络安全等领域，本 章介绍了几种常用的离群数据挖掘方法，并分析了它们的优缺点。 2 0 重庆大学硕士学位论文4 基于密度的离群数据挖掘算法及其改进 4 基于密度的离群数据挖掘算法及其改进 4 1 基于密度的局部离群数据挖掘算法 基于密度的局部离群数据挖掘方法是一种在多维数据集中挖掘离群数据的方 法。前面的离群数据挖掘方法用全局的观点看待数据集，因而只能挖掘到某些类 别的离群数据，这些离群数据称为“全局”离群数据。但是很多真实的数据集有更加 复杂的结构，会有另一种离群数据，这些离群数据可能相对于其近邻的局部密度 是离群的，所以称为“局部”离群数据。l o f 方法的特点是为每个对象赋予一个离群 数据因子，用来说明数据对象的离群程度，而前面介绍的方法对离群数据的定义 是二元的，即一个数据对象要么是离群的，要么不是离群的，不存在中间状态。 下面先介绍一下相关的概念f 3 2 3 3 , 弘3 5 1 。 定义4 1 对于任意正整数k ，对象p 的k 距离( 表示为kd i s t a n c e ( p ) ) 定义为p 和对 象o d 的距离d ( p ，o ) ，满足以下两个条件： 至少有k 个对象o r e d 一仞) ，使得d ( p ，0 ) d ( p ，0 ) ； 至多有k 1 个对象0 d p ) ，使得d ( p ，0 ) d ( 仍d ) 。 定义4 2 给定p 的k 距离，p 的k 距离内包含的每个对象，即： lm 。( p ) = 口d 一 p ) i d ( p ，g ) | i 一d i s t a n c e ( p ) ( 4 1 ) 这些数据对象q 称为p 的k 距离近邻。 定义4 3 设k 是一个给定的自然数，对象p 关于对象。的可达距离定义为： 一 r e a c h d i s t t ( p ，0 ) = i n a x 辑一d i s t a n c e ( o ) ，d ( p ，口) ) ( 4 2 ) 定义4 4 对象p 的局部可达密度定义为： 翮m ( p ) = 脚一。( p ) r e a c h 一如f 脚口( p ，d ) ( 4 3 ) 定义4 5 对象p 的局部离群因子定义为； fm 脚。( d ) 三c p ，= 警兰铲 l o f 算法描述如下： f o r e a c hp dd o 计算对象p 的m i n p t s 距离近邻及其与p 的距离； f o r e a c hp e dd o 计算对象p 的局部可达密度，然后计算其l o f 值； 根据l o f 的值判定数据对象是否是离群数据。 2 1 重庆大学硕士学位论文 4 基于密度的离群数据挖掘算法及其改进 4 2 基于密度的离群数据挖掘算法 目前常用的定义密度的方法有两种：一种密度的定义是数据对象的密度为其 到k 个最近邻的平均距离的倒数。如果该平均距离小则密度高，反之，密度低：另 一种是d b s c a n 聚类算法中的密度的定义，数据对象的密度就是该数据对象邻域 半径内的数据对象的数量，下面采用的是后一种密度的定义。 定义4 6 以数据对象o 为圆( 球) 心，半径内的区域称为o 的8 邻域 ( - n e i g h b o r h o o d ) 【3 6 1 。 定义4 7 若数据对象c 的邻域内含有数据对象数目不少于m i n p t s 个，则称c 为 核心对象( c o r e o b j e c t ) ，能产生核心对象的是有意义的。其中，m i n p t s 是一个可 以人为设定的自然数。 定义4 8d 是数据对象集合，p e d ，c o d 。对于给定的一个自然数m i n p t s ，若c 是核心对象，p 在c 的邻域内，则称p 是从c r i 发关于e 和m i n p t s 直接密度可达 ( d i r e e t l vd e n s i t yr e a c h a b l e ) 阶3 引。 定义4 9d 是数据对象集合，p e d ，p 的邻域内数据对象的集合称为p 的- 邻域 集，记为p 。 定义4 1 0d 是数据对象集合，o c d ，对于任意一个核心数据对象c o d ，从c 出发， 都不能关于瘌m i n p t s 直接密度可达并且i o i m i n p t s ，则称o 为关于瘌m i n p t s 的基 于密度的离群数据对象。 定义4 1 1d 是数据对象集合，p e d ，若p 的8 邻域内含有对象数目为零个，则称 p 是数据集d 中关于g 邻域的孤立点。 基于密度的离群数据挖掘算法( d b o m a ，d e n s i t y - b a s e do u t l i e rm i n i n g a l g o r i t h m ) 【3 9 柏、4 1 4 2 】可以发现任意形状的数据布局中的离群数据，它的基本思想 是：对于数据集中的每一个离群数据对象，不能包含在任何一个给定半径和该半 径邻域内包含指定数据对象数目的核心对象的邻域内。基于密度的离群数据挖掘 为了发现所有的离群数据，需要对每个数据进行处理。d b o m a 首先从数据集d 中 任意找一数据对象p ，并查找： s d 6 p p 的关于半径e 邻域内包含的所有的邻域对象， 若p 的邻域内某一个数据对象的e 邻域内包含m i n p t s 或多 ：m i n p t s 个数据对象，即p 的邻域内存在一核心数据对象，则p 不是离群数据，反之，若p 的邻域内所有数据 对象的邻域内包含的数据对象个数都少于m i n p t s 个或者p 的邻域内没有数据对象 即p 是数据集d 中关于邻域的孤立点，则p 是离群数据；接着处理数据集中的下一 个数据，直至数据集中的所有数据都被处理完。相应的算法描述如下： d b o m a ( d ，m i n p t s ) i o l - - n 酬i _ l ；i 匈；i + + ) f l a g = 0 ； 重庆大学硕士学位论文4 基于密度的离群数据挖掘算法及其改进 p = d g e t ( i ) ； p es f 铂u u ； c o u n t - - o ； f o r o = 1 j n ；j + + ) q = d g e t ( j ) ； i f ( d ( p ，q ) ) d ( p ，q ) 为数据对象p 、q 之间的距离 d p u t ( q ，p 嘣) c o u n t + + ； ) f o r ( k = 1 ；k = e o u n t ；k + + 1 n u m = 0 ； m = p h d g e t ( k ) ； 自呱l = 1 ；l ， 几- 一 则数据点p 的模定义为m ( p ) = 、最2 。 定义4 1 3 ( 向量的内积) 设p ，q 为2 个d 维向量，p = ( p l ，p 2 ，p d ，q - ( q l ， q 2 ，q d ) ，p 和q 的内积定义为 = p lx q ， 将数据集d 中每个数据点看作一个d 维向量，向量内积定义可以应用于数据 点间。 定理1 ( 向量内积不等式) 设p ，q e d 为数据集中任意2 个数据点，则有( p ，q ) m 0 ) m ( q ) 。 d 证明由定义4 1 2 及定义4 1 3 有 p ，g 碲p ，x q 。 = 辱虿= a x q l 。 即有 f ，故而无需计算d i s t ( p ，q ) 就可以判断出q 不可能在p 的r 邻域内， 仅当预判断无效时，才计算d i s t ( p ，q ) 的值。由此达到降低计算量，提高算法效率的 目的。下一步需解决的问题是如何高效地进行内外存间的数据置换。 从离群数据的特征来看，离群数据往往是比较稀疏的、在数据集中所占比例 比较小的数据，而大部分不是离群数据，因此，上述算法对每个数据及其邻域内 的数据进行相关判断，显然效率就比较低下。 定理3 如果一个数据对象是核心对象，那么该数据的邻域内的数据都不是离 群数据【5 n 。 证明假设存在一个数据集d ，c 为d 中关于e 和m i n p t s 的核心数据对象，c 聃d 为c 的邻域集，那么对c 。中的任意一个数据对象p ，都有d ( c ，p ) 鱼，也即从 核心数据对象c 出发，可以直接密度到达数据对象p ，由定义5 可知，数据对象p 不 是离群数据对象。 定理4 某个数据对象是离群数据是其邻域内数据对象的个数少于m i