（管理科学与工程专业论文）孤立点分析在医学领域的应用研究.pdf

山东师范大学硕士学位论文 孤立点分析在医学领域的应用研究 摘要 随着现代信息技术的迅速发展，许多领域都积累了大量的数据，我们渴望发 现潜在于这些数据中的知识与规律，正是这一需求造就了数据挖掘学科的兴起及 数据挖掘技术的发展。数据挖掘技术主要的目的就是从大量的、不完全的、有噪 声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识，作为一个多学科交叉的综合性领域，数据挖掘涉 及了数据库、统计学、机器学习、高性能计算、模式识别、神经网络和数据可视 化等学科。 聚类分析是数据挖掘中的一个重要研究领域。所谓聚类，就是把没有类别标 记的样本集按某种准则划分成若干类，使类内样本的相似性尽可能大，而类间样 本的相似性尽量小，是一种无监督的学习方法。聚类分析通常是在没有先验知识 支持的前提下进行的，它所要解决的就是在这种前提下，实现满足要求的类的聚 合。聚类分析的研究主要集中在聚类算法上，产生性能好而且实用的聚类算法是 其终极目的。迄今为止，人们提出了很多种不同的适用于数据挖掘的聚类算法， 但这些算法仅适用于特定的问题及用户，而且它们在理论和方法上仍不完善，甚 至还有严重的不足之处。对聚类算法的进一步优化研究将不仅有助于算法理论的 完善，更有助于算法的推广和应用。 医学图像的数据挖掘不仅是数据挖掘研究领域的一个热点，也是难点。目前 图像挖掘的工具较少，挖掘过程需要人工干预，很难实现完全的自动化。 在实际的医疗工作中，医生对病人的医学图片的检查往往是通过多年的临床 经验来进行的，而个人的临床经验又不可能面而俱到，何况检查的过程中还会存 在很多的偶然性的干扰因素，所以很有必要利用数据挖掘技术为医疗行业提供帮 助。 孤立点分析又称孤立点挖掘、异常检测、例外挖掘、小事件检测、挖掘极小 类、偏差检测。孤立点可能是“脏数据”，也可能是与实际对应的有意义的事件。 从知识发现的角度看，在某些应用里，那些很少发生的事件往往比经常发生的事 山东师范大学硕士学位论文 件更有趣、也更有研究价值。因此，异常数据的检测和分析是一项重要且有意义 的研究工作。 本文针对传统的数据挖掘技术在图像挖掘方面的不足，分析了当前图像挖掘 的特点及现状，并在全面、深入掌握数据挖掘技术的基础上，结合图像处理和医 疗领域知识，提出了一种新颖的基于医学图像像素聚类的孤立点分析技术，详细 介绍了孤立点分析技术在c t 图像上具体的应用，描述了医学c t 图像的孤立点分析 方法及过程。该过程首先收集大量的医学c t 图像，对原始图像进行预处理，然后 进行像素聚类并提取参数，最后使用孤立点分析技术来挖掘出可能存在病变信息 的图片，以此帮助医生高效率地进行疾病检查和诊断。 关键词：孤立点分析，聚类，图像挖掘，医学图像 分类号：t p 3 9 1 4 山东师范大学硕士学位论文 r e s e a r c ho no u t l i e r a n a l y s i sw i t hm e d i c a la p p l i c a t i o n a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm o d e mi n f o r m a t i o nt e c h n o l o g y ，ag r e a td e a lo f d a t ah a sb e e na c c u m u l a t e di nm a n yf i e l d s p e o p l ee x p e c tt od i s c o v e rt h ek n o w l e d g e a n dr u l e se x i s t i n gi nt h e s ed a t a ，w h i c hj u s tb r i n g st h es t u d yo fd a t am i n i n ga n dt h e d e v e l o p m e n to fi t st e c h n o l o g y d a t am i n i n ga i m st oe x t r a c tt h ei m p l i c i t ，p r e v i o u s l y u n k n o w na n dp o t e n t i a l l yu s e f u lk n o w l e d g ef r o mv o l u m i n o u s ，n o n - c o m p l e t e ，f u z z y ， s t o c h a s t i cd a t a a sac o m p r e h e n s i v ef i e l do fc r o s s i n gm u l t i - s u b j e c t ，d a t am i n i n g i n v o l v e sm a n ys u b j e c t ss u c ha sd a t a b a s e ，s t a t i s t i c ，m a c h i n e l e a r n i n g ，h i g h p e r f o r m a n c ec o m p u t i n g ，p a t t e mr e c o g n i t i o n ，n e u r a ln e t w o r ka n dd a t av i s u a l i z a t i o n c l u s t e ra n a l y s i si sa ni m p o r t a n tt e c h n o l o g yi nd a t am i n i n g c l u s t e r i n gp r o c e s s e s a l ea l w a y sc a r r i e do u ti nt h ec o n d i t i o nw i t hn op r e - k n o w nk n o w l e d g e ，s ot h e m o s t r e s e a r c ht a s ki st os o l v et h a th o wt og e tt h ec l u s t e r i n gr e s u l ti nt h i sp r e m i s e s t h e m o s tr e s e a r c ha b o u tc l u s t e r i n gi sf o c u s e do nc l u s t e r i n ga l g o r i t h m s ，t h em a i np u r p o s ei s t op r o d u c ep r a c t i c a la l g o r i t h m sw i t hb e t t e rp e r f o r m a n c e u pt on o w m a n yc l u s t e r i n g a l g o r i t h m sh a v eb e e np r e s e n t e d ，b u tt h e s ea l g o r i t h m sa l eo n l ys u i t e ds p e c i a lp r o b l e m s a n du s e r s f u r t h e r m o r e ，t h e ya l ei m p e r f e c tb o t ht h e o r e t i c a l l ya n dm e t h o d o l o g i c a l l y ， e v e ns e v e r ef a u l t o p t i m i z i n gd e e p l yc l u s t e r i n ga l g o r i t h m sw i l ln o to n l yh e l pt op e r f e c t i t st h e o r y ，b u ta l s oi t sp o p u l a r i z a t i o na n da p p l i c a t i o n i m a g em i l l i l 唱i sa ni m p o r t a n ta n dd i f f i c u l tt o p i c t h e r ei sal a c ko fe f f e c t i v et o o l s f o ri m a g em i n i n g ，m i n i n gp r o c e s sn e e d sh u m a ni n t e r f e r ea n dc a n n o tb ec o m p l e t e l y a u t o m a t e d i n h o s p i t a l ，d o c t o r s d e t e c tt h em e d i c a l i m a g e su s u a l l yb yt h e i rp e r s o n a l e x p e r i e n c e ，b u tt h e i rp e r s o n a le x p e r i e n c e s c a i ln o tr e a c he v e r ya s p e c to fam a t e r ，a n d t h e r ea l ea l w a y sm a n yo t h e rs t o c h a s t i ct h i n g sd i s t u r b i n gh i m ，a l lo ft h e s em a y b r i n go n t h em i s t a k e so fh i se x a m i n e s s o ，i t sv e r yi m p o r t a n tt om a k et h ew a yo fd e t e c t i n g 5 山东师范大学硕士学位论文 i l l n e s st ob es t a n d a r d i z a t i o nb yt h eh e l po fc o m p u t e rt e c h n i q u e s t h ep r o b l e mo fo u t l i e ra n a l y s i sh a sb e e nv a r i o u s l yc a l l e do u t l i e rm i n i n g ，a n o m a l y d e t e c t i o n e x c e p t i o nm i n i n g ，d e t e c t i n g r a r e e v e n t s ，m i n i n g r a r ec l a s s e s ，d e v i a t i o n d e t e c t i o n ，e t c o u t l i e rm a yb e “d i r t yd a t a , b u t i ta l s oc a nm e a n sm e a n i n g f u le v e n t c o r r e s p o n d i n gt ot h er e a l i t y f r o mt h ep o i n to fk n o w l e d g ed i s c o v e r y ，r a r ee v e n t sa r e o f t e nm o r ei n t e r e s t i n ga n dv a l u a b l et h a no t h e r si nm a n yd o m a i n s ，w h e r et h er a r e e v e n t s i m p o r t a n c ei sq u i t eh i g hc o m p a r e dt oo t h e re v e n t s ，m a k i n gt h e i rd e t e c t i o na n d a n a l y s i se x t r e m e l yi m p o r t a n t i nt h i sp a p e r ，w ea n a l y s et r a d i t i o n a ld a t am i n i n gt e c h n o l o g yg a p si ni m a g e m i n i n g ，d e s c r i b et h e c h a r a c t e ra n dt h es t a t u so fi m a g em i n i n g ，a n di na c o m p r e h e n s i v e ，i n d e p t hg r a s po fd a t am i n i n gt e c h n o l o g yb a s e do nt h ec o m b i n a t i o n o fi m a g ep r o c e s s i n ga n dm e d i c a lk n o w l e d g e ，w eg i v ean e wp i x e l - b a s e dm e d i c a l i m a g ec l u s t e r i n go u t l i e ra n a l y s i st e c h n i q u e ，d e s c r i b i n gt h es p e c i f i ca p p l i c a t i o no f o u t l i e ra n a l y s i si nc ti m a g e s w ew i l ld e s c r i b et h ew h o l ep r o c e s so ft h eo u t l i e r m i n i n g f i r s t l y ，t h eo u t l i e rm i n i n gp r o c e s se x t r a c t sc ti m a g e sf e a t u r e sa n dp r e p r o c e s s t h ed a t a ，a n dt h e nd i v i d e st h ei m a g e sb yt h ew a yo fc l u s t e r i n gm e t h o do ni m a g e p i x e l s ，c o n s t r u c t st h ev e c t o r so fp a r a m e t e r ，a n dm i n e st h eo u t l i e r s w i t ht h er e s u l t s ，w e c a nh e l pd o c t o r st od e t e c ti l l n e s sb yam o r ee f f i c i e n tw a y k e y w o r d s ：o u t l i e ra n a l y s i s ，c l u s t e r i n g ，i m a g em i n i n g ，m e d i c a li m a g e 6 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本栏 可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 糊獬礼 翩辩： i 学位论文版权使用授权书 本学位论文作者完全了解遨有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权邋可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 靴敝储摊：坤 新辩： 签字日期：2 0 0 9 年，耖月矿日 签字日期：2 0 0 9 年 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论弟一早珀下匕 目前数据挖掘的大多数工作都集中在发现数据集合中的“大的模式 即 数据所显示出来的显著的多数的特征，如关联规则、分类和聚类等挖掘方法n 2 3 。 然而，在一些应用领域中，识别异常数据是许多工作的基础和前提，它们表示一 种偏差或新模式的开始，可能对用户产生危害或造成巨大的损失。孤立点 ( o u t l i e r ) 正是数据集合中与一般数据模型不相符合的那些数据n 1 。 孤立点检测在有些文献里又称为异常挖掘、离群数据挖掘等，是数据挖掘中 的一项重要技术，用来发现“小的模式 ( 相当于聚类) ，即数据集中显著不同 于其它数据的对象。在以往的数据挖掘应用中，孤立点经常被忽略或被当作“噪 音 而被剔除。“一个人的噪音可能是另一个人的信号”。研究孤立点有时比研 究聚类更有用、更重要，且具有特殊的意义和很高的实用价值。研究孤立点的异 常行为能发现隐藏在数据集中更有价值的知识。例如，错误数据的查找，金融、 通信领域的欺诈分析与检测；网络安全管理中，网络入侵的检测；市场分析中， 消费极高或极低的客户的行为分析；股票市场波动的异常反映；在医疗分析中， 用于发现对多种治疗方式的不寻常的反映；在数据仓库领域，孤立点检测被用来 发现不一致的数据，提高数据的质量等等。随着互联网应用的迅速普及，电子商 务的兴起，对网络安全的迫切要求，孤立点检测正引起研究者们的极大兴趣。因 此，孤立点分析方法的研究就具有十分重要的意义了口j ，。 在科学高度发达的今天，人们已经可以通过各种技术手段获得肉眼不可能直 接观察得到的许多极有价值的图像资料，例如医学图像( c t 图像，e c t 图像，核磁 共振图像) ，人造卫星图像和各类数字照片等等，而存储技术的发展也已经使得 大规模图像数据库成为现实。这些图像包含了大量的对人们有用的信息，但是对 于用户来说，仅凭人工手段和个人经验去分析、处理这些图像，是难以充分发现 和利用其中潜在的知识的。因此，将计算机技术引入图像处理领域，特别是对大 规模图像所蕴涵的信息的挖掘、整理工作中，就成为十分迫切的需求。 在我国，各医院近年来不断引进各种先进的数字医疗设备，产生了大量具有 山东师范大学硕士学位论文 很高的解析度并能显示出复杂结构的医学图像。但在进行临床诊断的时候，医生 往往仍是凭肉眼对医学图像进行观察和分析，而判读医学影像是一个比较枯燥的 工作，由于肉眼的分辨率较低，医学影像( 特别是造影图像) 中许多微小的纹理变 化细节和形态特征不容易被发现，会影响对病情的早期判断。因此，医生的个人 经验以及他当时的疲劳程度等主观因素对临床诊断的最终结果影响较大。为了尽 量减少这种主观误差，我们不得不求助于其它的辅助诊断手段。 数据挖掘是从人工智能的分支机器学习发展而来的，由数据库、统计学、模 式识别、知识库、数据可视化等技术相互交叉融合而成，至今已有十多年历史， 它能从数据库中获取正确、新颖、有潜在应用价值的和最终可理解的知识和模式。 n 1 随着近年来数据挖掘技术的不断发展和成熟，利用计算机的大规模运算能力， 将数据挖掘技术和医学图像技术相结合，已逐渐成为解决计算机辅助医学诊断这 一问题的新手段。 数据挖掘应用于大规模图像处理，称为计算机图像挖掘技术，它可以以人力 所不能及的大规模运算能力、速度和有效的算法从大量图像中发现隐含的知识或 者模式，这在需要从大量医学图像中寻找病征及其规律的医学图像分析领域中大 有可为。 数据挖掘任务可以分为四类：关联规则挖掘、分类、类描述和孤立点( 例外) 检测。前三类用于发现数据集中大比例的模式，大多数数据挖掘的研究，如关联 规则、分类、聚类、概念生成都属于这种类型。而孤立点检测用来发现数据集中 小部分对象，这些对象通常被忽略或视为噪音。尽管有不少机器学习和数据挖掘 的算法考虑了孤立点，但它们的目的只是使算法尽可能免受孤立点的影响，或者 排除它们。 所谓孤立点，是指数据集合中与多数数据的特征或行为完全不一致的数据。 在最初的挖掘算法中，人们总是将孤立点从数据集合中删除，以保证数据的纯洁 性。然而，删除孤立点可能会导致忽略某些非常有用的特殊规则，因而对孤立点 需作特殊处理。在一些应用中，罕见的事件可能比正常出现的那些更有趣、更有 意义。 医学工作的目的，就是发现、研究、治疗疾病。具体到医学影像的处理领 域，其主要的应用需求就是从大量的各类医学影像中总结或探索其中的普遍规 山东师范大学硕士学位论文 律，再利用这些规律去寻找与普遍模式不相符合的异常情况。因为人体医学图像 的异常往往意味着身体组织结构的异常，而身体组织结构的异常在医学上往往是 身体病变的反映。因此，孤立点分析的方法非常适用于这个领域，这也正是我们 开展本项研究的主要原因。 本项目的任务，就是从众多c t 图片中寻找含有异常图像区域信息的部分，换 而言之，也就是寻找那些在正常的图片中不应出现的部分，而它们的异常表现方 式可以是多种多样的，例如在身体中所处的位置、区域的密度( 灰度) 、组织的大 小、形状等等。在这里，对我们和用户而言，异于正常模式的图像结构、局部区 域才是我们所关心和寻找的目标。如果把这些异常的图片区域视为大量c t 图片数 据集中的孤立点，那么我们所进行的工作就是对这些孤立点的分析和挖掘。 我们经过与医学影像领域的专家、临床医务工作者的探讨，将本研究的目标 定位于为医生的诊断提供一种比较可靠的辅助手段，通过采用对器官组织正常差 异和形变不敏感的新的算法，尽量避开过去工作中遇到的诸多困难，将上述几个 方面以及领域知识综合运用，对大量待处理图像进行筛选、过滤，不保证每一个 筛选结果都一定存在病变信息，但尽量保证不漏过每一个可能存在病变信息的图 像。并对可能的病变区域进行提示，从而有效缩小需要人工处理的数据量，以达 到提高诊断效率的目的。 计算机对灰度图像的识别可以达至u 2 5 6 级，远高于人类肉眼的8 级，所以在一 定的算法支持下，计算机可能具有很高的“识别”能力，能够从医学图像中发现 一些肉眼所不能发现的微小的纹理和形态特征细节，而这些经常被人的肉眼所忽 略的细节往往就是早期病变的征兆信息，是能够用于对病人的病情做出正确诊断 的关键信息。另外，病人的各种病情及症状虽然千差万别，但是反应到医学图像 上，又都是具有一定的规律性的，如果能找到这些规律并将其用于临床诊断，将 能大大提高治疗的准确性和及时性。特别是对于脑瘤这类严重威胁人类健康的疾 病，一旦出现误诊、漏诊，后果将极其严重，因此，将数据挖掘技术和医学图像 的邻域知识结合起来应用于基于医学图像的计算机辅助诊断是非常有必要的。 在本文中，我们将可能含有病变信息的图像区域作为大量c t 图像中的孤立点 来分析。对图像中不同灰度的像素区域进行聚类，获得图像所显示的不同组织的 像素聚类信息，构造聚类参数矢量组，然后通过比较聚类参数矢量数据来筛选孤 9 山东师范大学硕士学位论文 立点，试图发现肉眼难以区别的异常图像区域，用以辅助医生进行诊断。我们十 分注重领域知识对医学c t 图像挖掘的指导作用，在计算机辅助诊断技术尚不成熟 的阶段，医学影像领域多年来所积累的丰富的知识和经验可以为我们提供许多行 之有效的方法和思路。我们在图像预处理和孤立点分析过程中都应用到了领域知 识。 1 2 国内外研究现状 医学图像挖掘的主要工作是利用图像的低层特征对图像进行相似度搜索然后 根据所获得的信息进行挖掘，最终通过对原始图像集的挖掘找到挖掘者感兴趣的 规则或对原始图像进行分类或生成图像的聚类。因此，目前所发展的主要的医学 图像挖掘技术均侧重于上述的几个方面。 在医学影像处理和医疗设备及软件的研究、开发领域，许多机构都在进行通 过计算机处理医学影像的尝试，其中，利用计算机将医学平面图片还原为三维数 字模型的应用是目前进步明显、成就显著的一个方面，这一类研究为医生提供了 比以往更为直观、清晰的观察方式，并不能代替人工进行临床检查。在计算机辅 助诊断方面，人们也进行了大量的探索和实践，并由此发展出许多相关的计算机 图像处理技术，例如图形对中、图片比较、图像特征提取等等，但是，至今还没 有一种可以完全代替人工进行临床医学影像检查的成熟技术出现。其制约因素， 主要有两个方面：其一，人体的组织结构极其复杂，而人体的病变机理更是千差 万别，加之不同对象之间的个体差异以及人体正常生命活动造成的正常形变，即 使是同一个体同一身体部位的c t 图像之间的差异也会非常大，这就使得计算机区 别健康个体图片与带有病变信息的图片的过程异常困难；其二，就研究内容和手 段而言，目前主要工作的特点是研究问题基本集中在关联规则和分类上，研究的 内容主要是医学图像数据库中每个对象的单一图像，而且研究方法主要是先从图 像上提取特征，产生特征属性，然后在特征属性上进行疾病检查。对图像特征的 分析有利于区别身体不同结构的器官组织，对关联规则的挖掘也能够揭示许多身 体构造的内在规律，但是对于检查对象的个体差异和生命活动造成的身体正常形 变，这些方法还难以处理。因此，这些做法目前还局限在形变和个体差异很小的 脑部及骨骼检查领域中，对形变幅度较大的身体其它部位的处理效果还不理想。 1 0 山东师范大学硕上学位论文 1 3 本研究的意义 图像挖掘是一个多学科交叉的研究方向，包括计算机视觉、图像处理、图像 检索、数据挖掘、机器学习、神经网络、统计学、模式识别、知识获取、信息检 索、人工智能、数据库和数据挖掘等。尽管以上各领域都有很多成熟的技术，但 是图像挖掘仍然处于起步阶段。 孤立点分析是图像挖掘的一个重要应用领域。医生每天都要看大量的影像， 往往会因为疲劳或者其它个人原因而导致诊断的准确率降低。如果几个不同医院 的医生，尤其是有经验的教授或者专家，联合进行诊断，会大大提高诊断的准确 率，但是这种做法的代价是非常大的，大多数情况下不太可能，往往只是由一个 医生来对病人的影像作出诊断。判断病人是否患有疾病主要是看影像上是否有占 位。如果有，病人应当尽早的进行治疗，以防止病情恶化而加大治疗的难度。但 是有些时候占位并不明显，通常医生很难看出来，只是结合病人的病史，反复分 析影像，凭借丰富的经验才能做出正确的诊断。这就是说，一旦诊断失误，那就 会延误病人的早期治疗，导致病情恶化，甚至会危及到病人的生命或者将来的生 活，例如，造成视觉障碍、偏瘫等等。正因为如此，在医学图像和相关文字上研 究医学图像中的异常数据，对辅助医生的诊断和提高医学经验的共享都有极其重 要的意义，而且由于它具有很强的领域性，使得这方面的研究具有非常大的挑战 性。 1 4 本文的主要工作 本研究针对目前各种数据库系统应用过程中积累的海量数据、但却难以提取 出有价值信息这一难题，运用孤立点数据挖掘技术，分析提取大数据集中隐藏的， 不为人所注意的，易被抛弃的但非常有用的信息，找出其中的医学诊断规则和模 式，从而辅助医生进行疾病诊断。从大量医学图像中寻找并发现可能存在病变信 息的图片一直是计算机图像处理算法领域的热点和难点问题。因为人体正常的个 体差异及身体形变在医学图像上所表现出来的差异与病变造成的身体组织结构 变化对于一些传统的图像处理方法来说是很难区别的，这也是影响计算机处理医 学图像领域顺利发展的一个重要障碍。我们针对收集的大量医学c t 图像，查找和 山东师范大学硕士学位论文 研究了国内外有关文献，与泰山医学院放射学院的医学影像专业老师进行了深入 探讨，最终提出了一种比较有效的基于医学图像像素聚类的孤立点分析算法，并 进行了改进。 本研究为数据挖掘技术在医学图像处理领域的应用，为数字医学图像中病变 的计算机诊断提供了一种新的思路和方法，对帮助医生及早发现和诊断恶性病 变、提高诊断效率和准确性具有重大的意义。 山东师范大学硕士学位论文 第二章孤立点分析基础 2 1 孤立点分析的基本概念 随着计算机技术，特别是数据库技术的快速发展和广泛应用，各行各业积累 的数据量越来越大，传统的数据处理方式已很难充分利用蕴藏在这些数据中的有 用知识。如何对这些海量数据进行有效处理就成了许多领域学者研究的热点，于 是数据挖掘技术应运而生。 在数据挖掘过程中，存在着不符合数据模型的数据对象，这些数据通常被看 作是数据集中的噪声，它们的存在会影响数据挖掘的精确度，有时甚至会产生非 常差的挖掘效果。与其他数据有显著区别的数据对象集合称为孤立点( o u t li e r ) 。 孤立点也被称为例外或异常。大部分数据挖掘方法将孤立点视为噪声或异常而丢 弃。然而，在一些应用中( 如金融欺诈) ，罕见的事件可能比正常出现的那些更有 价值。孤立点的产生可能是由执行错误造成，也可能是由固有的数据变异造成。 例如：一个人的身高为2 m ，这个孤立点是由于执行错误造成的；在中国移动的 所有用户中，大客户的业务数据量远大于其他用户，这是由于固有的数据变异造 成的孤立点。 孤立点的研究非常重要，这主要是由于：它对数据分析的结果有很大影响； 它有可能蕴涵应用领域中有意义的、新颖的、有用的知识；孤立点的确定经 常导致发现新的知识。 孤立点的定义：许多研究者对于孤立点给出了各自不同的定义：k n o r r 等畸3 把孤立点描述为在数据集中存在与数据0 的距离大于d ( 具体的距离) 的那些小部 分数据。r a m a s w a m y 等哺1 则认为，孤立点是和所有别的数据相比具有最大距离的那 部分数据。b r e u n i g 等口1 的观点是，孤立点是在一个给定的邻域内具有最大局部孤 立因子( 局部孤立因子是在一个具体的点周围对象的距离或密度的度量值，局部 孤立因子高说明距离很远，相反，局部孤立因子低则说明距离很近) 的那部分数 据。h a w k i n s 田3 对于孤立点给出了实质性的定义：孤立点是在数据集中与众不同 的数据，使人们怀疑这些数据产生于不同的机制，而并非随机偏差。 孤立点分析的过程3 ：孤立点分析的过程可以粗略包括：孤立点问题定义、 山东师范大学硕士学位论文 数据准备、孤立点分析、分析结果的解释及评估；如图2 - 1 所示：孤立点问题 描述。在问题描述阶段，数据挖掘人员必须和领域专家及最终用户紧密协作来确 定挖掘任务，一方面是确定实际工作对数据挖掘的要求；另一方面是确定可用的 挖掘算法。数据准备。该阶段包括2 个步骤：数据选取和数据预处理。数据选 取的目的是确定挖掘任务的目标数据，目标数据是根据用户的需求从原始数据库 中抽取的一组数据。数据预处理包括消除噪声、推导计算缺值数据、转换数据类 型、通过降低数据维数来减少挖掘过程中要考虑的对象数目。孤立点分析。明 确了挖掘任务后，本阶段的任务是通过确定挖掘算法来发现模式。挖掘结果的 解释及评估。对发现的模式进行评估。对冗余或无用的模式，需要剔除；对不满 足用户要求的模式，要返回到前一阶段，重新确定可用的挖掘算法、重新选取数 据、设定新的参数值等。由孤立点分析过程描述可以看出：整个挖掘过程是一个 不断反馈的过程。n 伽 孤立点问题描述 j 数据准备 上 孤立点分析 土 1 分析结果的解释及评估 土 知识应用 2 2 孤立点分析方法 图2 - 1 孤立点分析过程示意图 2 2 1 经典孤立点检测算法 基于统计的孤立点检测算法 早期的孤立点检测算法大多数是基于统计学原理实现的n 1 呓j 3 1 ，通常可以分为基 1 4 山东师范大学硕士学位论文 于分布的检测算法和基于深度的检测算法两类。前者一般先构造一个标准分布来 拟合数据集，然后根据概率分布来确定孤立点，例女h r o s n e r 提出的单样本多个离 群检测算法e s d 方法n 订和y a m a n i s h i n 2 3 等使用混合高斯模型的孤立点检测算法，此 类算法方法的明显不足在于估计多维数据分布的难度较大且准确性低n 引：基于深 度方法主要以计算几何为基础，通过计算不同层的k - d 凸包n q 将外层的对象判定 为孤立点，但当数据集的数目增长时，此类方法在维数上的伸缩性不好。所以， 该方法不能确保发现所有的孤立点。 基于偏离( d e v i a t i o n b a s e d ) 的算法 基于偏离的方法根据一个数据集中的主要特征来判定孤立点，与这个主要特 征背离很大的记录就被认为是一个孤立点。偏差型知识是对差异和极端特例的描 述，揭示事物偏离常规的异常现象，如标准类外的特例、数据聚类外的离群值等。 序列异常技术是基于偏离的孤立点分析的主要方法。 序列异常技术模仿了人类一系列推测类似的对象中识别异常对象的方式，它 利用隐含的数据冗余。给定n 个对象的集合s ，它建立一个子集合的序列 s 。， s 2 ，s 。) ，这里2 m n ，满足s j - l c s j ，s j - l c s 。 估算序列中子集合间的相异度。在序列异常技术中需要引入如下术语： 异常集：它是偏离或孤立点的集合，被定义为某类对象的最小子集，这些对 象的去除会产生剩余集合的相异度的最大减少。 相异度函数：该函数不要求对象之间的度量距离，它可以是满足如下条件的 任意函数：当给定一组对象时，如果对象间相似，返回值就较小。对象间的相异 度越大，函数返回值就越大。一个子集的相异度是根据序列中先于它的子集增量 计算的。给定一个n 个对象的子集合 x 。，x 。 ，可能的一个相异度函数是集 合中对象的方差： 喜c 杠) 2 这里x 是集合中n 个数的平均值。对于字符串，相异度函数可能是模式字符 串的形式，它可以用来覆盖目前所见的所有模式。当覆盖目前所见字符串的模式 不能覆盖在s ，中却不在s 的任一字符串时，相异度增加。 基数函数：一般是给定的集合中对象的数目。 山东师范大学硕士学位论文 平滑因子：它是一个为序列中的每个子集计算的函数。它估算从原始的对象 集合中移走子集合可以带来的相异度的降低程度。平滑因子值最大的子集是异常 集。 该方法的基本思想是不考虑其补集来估算当前子集的相异度，从集合中选择 一个子集合的序列来分析。对每个子集合，它确定其与序列中前一个子集合的相 异度差异。 为了减轻输入顺序对结果的任何可能的影响，可以重复以上的处理过程若干 次，每一次采用子集合的一个不同的随机顺序。在所有的送代中具有最大平滑因 子值的子集合成为异常集。 基于距离的孤立点检测算法 基于距离的孤立点检测算法的基本思路是把数据点看作空间中的点，孤立点 被定义为在数据集中与大多数数据对象之间的距离大于某个给定的阈值的对象 点，通常被描述为d b ( p c t ，d m i n ) ，当且仅当数据集s 中至少有p e t 个数据点与p 点的距离大于d m i n 时，数据对象p 点称为孤立点。这类方法与基于密度的检测算 法有很大的相似之处，不需要事先知道数据集的分布模型，对于任意的分布模型 均有效。 经典的k 近邻最先是由k n o r ra n dn g n 5 3 提出来的，该算法定义了孤立点的范 围，但要求事先给出合适的参数d 和k 。k n o r ra n dn g 给出了两种算法：循环嵌套 算法和基于单元的算法。前者时间复杂度为o ( 砌2 ) ，在挖掘海量数据集时表现 不能令人满意；后者运行效率和数据集的大小成线性关系，但和数据集的维数成 指数关系，仅当维数为4 时运行速度较快。 r a s t o g i 在上述基于距离的孤立点定义的基础上，提出了改进的基于距离的 最近邻( k n n ) 孤立点检测算法n 8 7 1 。用d k ( p ) 表示点p 的第k 个最近邻点的距离，首 先计算出数据集t 中所有数据点的k 最近邻距离，然后按值的大小降序排列，算法 把排在最前面的n 。个点标记为孤立点。 k o r n 等n 胡提出反向近邻( r n n ) 的概念，后来又将反向近邻的概念延伸到反向k 近邻( r k n n ) ，一个数据点p 的反向k 近邻是其k 个最近邻中包含有数据对象p 的点 集。此方法中，反向k 近邻能反映潜在的分布特征，数据分布的改变会影响到数 据对象p 的k 近邻。 1 6 山东师范大学硕士学位论文 r a m a s w a m y 等改进了k n o r r 对孤立点的定义，认为孤立点是数据集中到第k 个最近邻居的距离最大的n 个对象。首先对输入部分的数据聚类，然后对这些不 可能包含孤立点的部分剪枝n9 j 。实验显示该算法在数据集的大小和维数上伸缩性 良好，但不能准确区分稀疏与密集近邻。 基于密度的孤立点检测算法 所谓密度是指任意一点和p 点距离小于给定半径r 的邻域空间内的数据点的 个数，一般的对密度的定义是点到其k 近邻的平均距离，平均距离小则密度小。基 于密度的孤立点检测，就是探测局部密度，通过不同的密度估计策略来检测孤立 点，代表性算法主要有以下几种： ( 1 ) b r i t o 等心们提出相互k 近邻图( m u t u a lk - n e a r e s tn e i g h b o r ，简称m k n n ) 算法，其主要思想是对每个连通子图进行检测，如果包含多个结点就组成一个簇， 如果仅有一个结点，那么该结点就是孤立点。该算法针对数据点的分布对各种特 殊形状都有效，但算法执行效率不高。 。 ( 2 ) v i il eh a u t a m a k i 等心提出两种基于密度的孤立点检测算法，第一种算法 思路为在k n n 图中，若顶点v 成为其它点的k 近邻的次数少于给定闽值t 时就被认为 是孤立点，另一种算法则是先对所有顶点v 的平均k 近邻距离进行排序，然后将平 均最近邻距离大于t 的顶点视为孤立点。 ( 3 ) p a p a d i m i t r i o u n 6 1 定义了多粒度偏离系数( m u l t i g r a n u l a r i t y d e v i a t i o nf a c t o r ，简称m d e f ) ，该算法将多粒度偏离系数是所在邻域的标准多 粒度偏离系数的3 倍的点判定为孤立点，然而标准多粒度偏离系数的计算量大， 对算法的可行性有一定的限制。 ( 4 ) d o n g m e ir e n 口2 3 等采用相对密度系数( r e l a t i v ed e n s i t yf a c t o r ，简称 r d f ) ，i i l 3 p 点的密度相对该点的邻域密度的比值作为孤立程度的度量方法，其基 本思路是首先基于r d f 对位于簇中心的数据点进行剪枝，然后仅仅在剩下的较小 的数据集中进行孤立点检测。该方法降低了数据集的大小，提高了算法效率，但 是在剪枝过程中对于特殊分布的数据集就有可能将孤立点剪掉，算法的准确性受 到限制。 ( 5 ) b r e u n i gmm e 2 3 3 用局部孤立系数( l o c a lo u t l i e rf a c t o r ，简称l o f ) 表示 点的孤立程度，根据给定的最少邻居数k 和最近邻距离来确定邻域，通过计算数 1 7 山东师范大学硕士学位论文 据点的k 近邻距离、可达距离和可达密度，用数据点邻域的平均可达密度和数据 点自身的可达密度之比表示l o f ，若点p 的密度与其邻域内其它点的密度相差很大 ( l o f 值较大) ，则点p 被判定为局部孤立点。此方法可避免数据集的疏密不一致对 挖掘带来的影响。 基于聚类的孤立点检测算法 孤立点检测仅仅是聚类的副产品，聚类算法发展方向是优化聚类过程，而不 是提高对孤立点检测的能力 1 5 o 孤立点检测和聚类是两个相对立的过程，聚类是 把属于同一类的数据点聚集在一起，归为一类，而孤立点检测是把和大多数数据 点相异的点挖掘出来。 s u 乜4 1 等人首先提出了基于聚类的孤立点检测算法，聚集的较小簇被认为是孤 立点，但这种方法忽略了小聚集簇和大聚集簇之间的距离，当一个小聚集簇和一 个大聚集簇非常接近的时候，小聚集簇中的这些点更可能是大聚集簇的边界点而 不是孤立点。 模糊k 均值聚类算法( f c m ) 常用于孤立点检测，该算法动态地分配权重给每一 个数据点，权重表示该数据点和数据集中心之间的距离，通过各点的权重来判断 孤立点，例如文献血印提出的基于f c m 的模糊核聚类算法等。此类算法没有先验知 识指导如何确定聚类中心，只能是随机选取，优化搜索空间较大，算法的复杂度 较大。 h o n g y iz h a n g 等乜6 1 为了提高模糊核聚类算法的运行效率，提出了新的模糊核 聚类算法，该算法用先验知识对参数初始化，取代了用聚类中心初始化矩阵，改 进了聚类的目标函数，降低了算法的时间复杂度，但该算法没有提到如何选取核 函数，对于算法中模糊性的控制不好掌握。 汪阳等堙7 1 则把聚类算法和主成分分析方法结合起来，首先对正常数据训练集 进行聚类分析，然后对各子集进行主成分分析( p c a ) ，提取出每组数据的p c a 变换 矩阵，最后用训练得到的p c a 矩阵将待检测记录投影到各个主成分空间，计算出 其在不同空间上的主成分得分，并提出利用不同主成分上的得分来判断该数据是 否为孤立点，效果较好。 基于人工神经网络模型的孤立点检测算法 应用人工神经网络进行孤立点检测是新兴的孤立点检测算法。w i l li a m s 等乜8 3 1 8 山东师范大学硕士学位论文 提出的r n n ( r e p l i t o rn e u r a ln e t w o r k s ) 神经网络孤立点检测算法使用通用的统 计数据集( 一般较小) 和专用数据挖掘数据集( 较大，并且是现实的数据集) 作为数 据源，对r n n 孤立点检测算法和上述3 类方法进行比较，发现r n n 在大的数据集和 小数据集都令人满意，但当使用包含放射状的孤立点( r a d i a lo u t l i e r s ) 时，性 能下降。 由此可见神经网络能够运用于孤立点检测，此类算法由于要求事先对网络进 行训练，然后用训练好的神经网络来进行孤立点检测，要求训练样本均为非孤立 点，对挖掘出的孤立点的意义也难于解释。由于神经网络泛化能力的限制，针对 一种运用实践而训练的网络只能用于该类实践数据，并且迭代次数是人为控制， 这对训练效果有很大的影响，在运行效率上和准确率上要有所折衷。 2 2 2 特殊的孤立点检测算法 ( 一) 数据流中的孤立点检测算法 此类算法主要针对动态数据集进行孤立点