（计算机应用技术专业论文）基于近似密度构造的聚类分析与离群点检测算法研究.pdf

摘要 聚类分析是研究数据聚簇模式的技术。由丁它始终是数据挖掘研究的重要内容、手段和工具， 因此，聚类分析又是一个被不断探索并充满创新的研究主题。离群点检测是研究包含在数据中的少 数异常而新颖的数据分布模式的技术。随着数据挖掘研究的不断深入并拓展到风险检测等众多特殊 应用领域，面向这一新兴课题的研究方兴术艾。近年来，网络和数据库技术高速发展，由此引发的 数据爆炸使面向大规模海量数据集的数据挖掘研究成为关键。探索并构造具有高性能、高效率的新 算法是解决大规模数据挖掘问题的有效途径也是本文开展聚类分析和离群点检测问题研究的着眼 点和出发点。 本文将数据空间弼格划分技术与数据集密度函数构造技术紧密结合在一起，形成了基于网格上 近似密度函数模型的算法构造思想。数据空间网格划分技术不仅被有效地运用于数据组织，使其发 挥数据存储和索引上的高效率，而且被运h j 于分箱核密度估计，成为简化密度函数计算中的有效机 制。在密度函数构造上，通过采片j 简便高教的分箱核估计避免传统核密度估计方法的繁复计算。为 了提高分箱核估计的计算精度，本文提出了基于网格数据重心的分箱核近似方法，从理论上证明了 其在误著阶上的改进结果的正确性。进一步遗，本文就常用的高斯核估计提出并论证了用于迸一步 提高近似核估计精度的带修正的近似核函数计算方法。这种方法在不改变分箱近似核估计计算复杂 度的同时，可以十分精确地逼近传统的核密度函数。 将上述基于网格上近似密度函数计算的思想运用于聚类分析和离群点检测算法构造，提出了用 于改进d e n c l u e 算法的) e n c l i d e - m 聚类算法和离群点检测算法g r i d o f ，g r o f c 。其中，d e n c l u e m 算法和 g v i d o f 算法深入揭示了聚类分析与离群点检测之问的内在联系，g r o f c 算法则从离群数据与聚类数据 在个别属性上的差异性的角度，在c h e b y s h e v 距离意义下讨论丁离群点检测问题。 所构造的几类算法均源自于严格的数学理论，具有相对于原始数据集线性的时间复杂度和优良 的空间效率，能够在有限的内存空间中处理任意规模的数据集并支持增量聚类，且对数据维数具有 良好的适应性。此外，d e n c l l f e 一聚类算法还具有发现任意形状聚类且不受噪声数据干扰的优点。 在研究过程中，针对所提出的近似密度模型和所构造的各种算法进行了大量的实验验证，实验结 果证明了这一思想的合理性和有效性，所提出的算法在综合性能上均明显优于现有的相应算法。 基于所提出的近似密度函数构造的思想，开展了图象特征提取与噪声过滤的实验研究。其处理 图象象素数据的方法新颖，所取得的实验研究结果进一步证明了这一方法的优越性， 关键字：网格，分箱核估计，近似密度函数，聚类分析离群点检溯 a bs t r a c t c l u s t e r i n gi s ap a r t i t i o ns c h e m et h a td i v i d e sad a t a s e ti n t o g r o u p so fs i m i l a ro b j e c t s s i n c et h e p r o s p e r i t yo f d a t am i n i n gi nl a s t9 0 s ，c l u s t e r i n gh a sb e e naf l o u r i s h i n gr e s e a r c ha r e aa n dw i d e l yr e c o g n i z e d a sak e yt o o lf o rm i n i n gv a l u a b l ei n f o r m a t i o na n d k n o w l e d g e f r o mt h ed a t a b a s e s o nt h eo t h e rh a n d ，o u t l i e r d e t e c t i o n - - ad a t aa n a l y s i su t i l i t yt h a tf i n da b n o r m a lw h e r e a si n t e r e s t i n gk n o w l e d g er e v e a l e db yt h er a r e i n s t a n c e sw i t h i nt h ed a t a s e t ，i sab u r g e o n i n ga n d p o w e r f u lt o o lc o m e sa l o n g w i t ht h ed e v e l o p i n go f t h ed a t a m i n i n gr e s e a r c h a st h ef a s te v o l u t i o no ft h ew o r l d w i d ew e ba n dd a t a b a s et e c h n o l o g i e s ，r e s e a r c h e r sa n d s e r v i c ep r o v i d e r sa r ep r e s s i n g i ys e e k i n ge v e rm o r ep o w e r f u la l g o r i t h m st h a tc a nh a n d l em a s s i v ed a t a s e t s e f f e c t i v e l ya n de f f i c i e n t l y t h i ss i t u a t i o ns h a p e su pt h eb a c k g r o u n d o f r e s e a r c h e si nt h i st h e s i s an o v e l c l u s t e r i n ga n d o u t l i e rd e t e c t i o nm e c h a n i s m ，t h a tb o t he m p l o y sd a t as p a c e p a r t i t i o na n dd e n s i t y f u n c t i o nm o d e l i n g ，i sp r e s e n t e d i nt h ep u r p o s e dm e c h a n i s m ，g r i d ak e yc h a r a c t e rt h a tr e s u l t sf r o ms p a c e p a r t i t i o n i st a k e na d v a n t a g eo fb o t ha sa ne f f e c t i v ed a t am a n a g e m e n tu n i ta n da l li d e a lm e s hf o rd a t a s e t s d e n s i t yc o n s t r u c t i o n b i n n e dk e r n e ld e n s i t ye s t i m a t i o n ，a ni m p o r t a n tm e t h o do r i g i n a t e df r o mc l a s s i c a l s t a t i s t i c s c o n s t i t u t e sa n o t h e rk e ym e a n sf o rt h em e c h a n i s mt ob o o s td e n s i t yf u n c t i o ne s t i m a t i o n t h e d i s t i n c ta p p r o a c hf o r w a r d e di nt h i sp a p e re n a b l e sr o b u s ta n dd e d i c a t e dc l u s t e r i n ga n do u t l i e rd e t e c t i o n a l g o r i t h mc o n s t r u c t i o n d e t a i l e ds t u d yi sd o n et oi m p r o v et h ea c c u r a c yo ft h eb i n n e dk e r n e ld e n s i t ye s t i m a t i o nm e t h o d s ，t h e p r e s e n t e da p p r o a c h f i r s ta l t e r st h eb i n n i n gc e n t e rf r o mt h ec e n t e ro f t h eg r i dt ot h eg r a v i t yc e n t e ro f t h ed a t a o b j e c t s w i t h i nt h e g d d b yt h i s m e a n s ，t h e a c c u r a c y o ft h eb i n n e de s t i m a t i o n g a i n s r e m a r k a b l e i m p r o v e m e n tu n d e rs k e w e dd a t ad i s t r i b u t i o ns e c o n d l y ，u n d e rt h eb a l a n c e dd i s t r i b u t i o np r e s u m p t i o n ， w h i c hi sr e a s o n a b l ew h e n p a r t i t i o n i n gf ll a r g ed a t a s e tw i t hr e l a t i v e l ys m a l lg r i dw i d t h ，a ne r r o ra d j u s t i n g s t r a t e g yi sd e v e l o p e db a s e do ng a u s s i u nk e r n e lf u n c t i o n t h es t u d yr e s u l t si n as c h e m eo ff a s td e n s i t y e s t i m a t i o nw i t hm i n o r a c c u r a c y l o s so f t h ed e n s i t yf u n c t i o n c l u s t e r i n g a n do u t l i e rd e t e c t i o n a l g o r i t h m s a r e p u r p o s e d b a s e do n g r i d - b a s e dd e n s i t y f u n c t i o n c h a r a c t e r i z a t i o no fad a t a s e t d e n c l u e m ，an e wc l u s t e r i n ga l g o r i t h mi n h e r i t st h ei d e a lo fd e n c l u e ， r e d u c en o t a b l e s p a c e a n dt i m e c o m p l e x i t y i n c o m p a r i s o n t oi t sc o l l a t o r b y t a k e a d v a n t a g e s o ft h e a p p r o x i m a t i o nm e c h a n i s mb o t hi n d a t as c a n n i n ga n dc l u s t e r i n g p h a s e g r i d o fi s a ne f f i c i e n to u t l i e r d e t e c t i o na l g o r i t h mb e a r st h es a m ec h a r a c t e r i s t i co fd e n c l u e mo r i g i n a t e df r o mt h ea p p r o x i m a t i o n c o n s i d e r a t i o n a n o t h e ro u t l i e rd e t e c t i o na l g o f i t h r a ，g r o f c ，c o n c e n t r a t e si t s e l f o nt h ep r o b l e mo fl a r g ea n d h i g hd i m e n s i o n a ld a t a s e tu n d e rc h e b y s h e vd i s t a n c e a l lt h ea l g o r i t h m sc o n s t r u c t e dh a v es o m ec o m m o n s u p e r i o r i t i e si nt h ef o l l o w i n ga s p e c t s ： ( 1 ) s o l i dm a t h e m a t i c a lf o u n d a t i o no r i g i n a t e df r o mc l a s s i c a ls t a t l s t i c a lt h e o r i e s ； ( 2 ) l i n e a r i nc o m p l e x i t yt ot h es c a l eo f t h e g i v e nd a t a s e t ； ( 3 ) i n d e p e n d e n t t o t h ea v a i l a b l e m e m o r ys p a c e w i t h o u t n e e do f s w a p i n a n d s w a p o u t o f t h ed a t a ；a n d ( 4 ) s u p p o n i n c r e m e n t a ld a t am i n i n g p u r p o s e sw i t ht h ei n f o r m a t i o ng a t h e r e d b e s i d e s ，d e n c l u e ma l s oh a st h ea b i l i t i e sb o t hi nf i n d i n ga r b i t r a r ys h a p e dc l u s t e r sa n dh a n d l en o i s y d a t a s e ts u c c e s s f u l l y i m a g ef e a t u r ee x t r a c t i o na n dn o i s ef i l t e r i n ga r et w oe x p e r i m e n t a ls t u d i e sb a s e do nt h ea p p r o x i m a t e d d e n s i t yc o n s t r u c t i o nm e c h a n i s mp u r p o s e di nt h et h e s i s t h ep r o c e s s i n gs t r a t e g i e sa n de x p e r i m e n t a lr e s u l t s p r o v et h er a t i o n a l i t ya n da v a i l a b i l i t yo f t h en o v e lm e t h o d k e y w o r d s ：g r i d ，b i n n e dk e r n e le s t i m a t i o n ，a p p r o x i m a t e dd e n s i t yf u n c t i o n ，c l u s t e r i n ga l g o r i t h m ，o u t l i e r d e t e c t i o na l g o r i t h m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名： 第一章概述 1 1 选题依据及意义 第一章概述 在过去的半个世纪里。信息技术走过了一段辉煌的发展历程。信息技术向科学与社会各个领域 的强力渗透和转移极大地改变了人类工作、生活和认识自然的方式。信息技术的发展在为科学技术 的全面突破与创新提供了强大技术手段的同时，人啊j 探索未知领域的强烈欲望和来自应用领域的需 求又对现有的信息技术提出新的挑战。上个世纪八十年代以来，数据库技术得到了广泛的应用，数 据获取技术与存储能力的提高使人们所面临的数据量飞速增长。为此，人们迫切需要一种能够从大 量的数据中智能地、自动地抽取有价值的信息或知识的新技术。于是，数据库知识发现技术 ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e k d d ) 应运而生。 数据库知识发现( 又称数据挖掘，d a t a m i n i n g ，d m ) 是从数据集中识别出有效的、新颖的、潜在有 用的并最终可理解模式的非平凡过程“j 。其在功能上的强健性和应用领域的f “泛眭已被广为了解。 十多年来，围绕这一主题所开展的深入而广泛的研究与探索工作常新不竭，成果丰硕。尽管如此， 互联网络技术的兴起和人类基因组计划的实施等一系列信息技术应用领域的重大事件使人们真正看 到了什么是巨量数据一不论设备处理能力的增长如何显著，总是存在来自更为复杂问题的数据使计 算资源消耗殆尽l 面对如此大规模的数据，人们除了借助于高速计算机以外，就是从根本上研究并 构造高效的信息与知识抽取方法。 奉论文研究工作涉及数据库知识发现的重要工具聚类分析与离群点检测技术。其目标是通过 系统的理论探索与创新，研究井构造具有优良性能的高教聚类分析与离群点检测算法。由于离群点 检测与聚类分析问题在理论上遵循类似的机理，因此，本论文研究工作中，将聚类分析与离群点检 测问题综合起来。在研究过程中，以探讨和解决聚类分析问题为主线，提出有关的概念、思想和方 怯，然后将其运用于聚类算法的构造。在此基础上，将所取得的有关近似密度构造的理论研究成果 根据离群点检测问题的特点加以探讨和应用，提出基于本论文思想的离群点检测算法。 本论文在广泛调研的基础上，根据聚类分析和离群点检溯技术研究的潜在应用背景，结合国家 自然科学基金项目“面向企业风险管理的数据挖掘技术及其应用研究”( 基金立项编号：7 9 9 7 0 0 9 2 ) 、 国家自然科学基金项目“基于数据挖掘技术的中观审计风险研究”( 基金立项编号：7 0 3 7 1 0 1 5 ) 、江 苏省教育厅自然科学基金项目“知识发现技术在功能基因识别中的应用研究”( 基金立项编号： 0 2 k j b 5 2 0 0 1 2 ) 及国家中小型企业创新基金项目“企业商务智能决策导航器一e b i d n ”( 基金立项编 号：0 2 c 2 6 2 1 3 2 1 0 0 7 0 ) 的研究工怍，通过对基于网格的近似核密度估计技术的深入研究，提出面向 大规模数据聚类分析和离群点发现问题的高效算法，为所从事的应琦j 研究项目开辟新的技术途径。 1 2 聚类分析与离群点检测研究现状及相关领域 1 , 2 1 聚类分析 聚类分析( c l u s t e r i n g ) 是人们认识和探索事物内在联系的一种手段成语“物以类聚，人以群分” 是这一理念的最朴素和直观的反映。从数据分析的角度来看，聚类分析的目标是把一个数据集中的 元素按照适当的相似性准则归结为若干个互不相交的子集，称为聚类。其目标是使属于同一聚类的 数据之间的相似性尽可能大，而属于不同聚类的数据2 间的相似性尽可能小”4 1 聚娄分析技术具有广阔的应用背景。从对自然和宇宙观察数据的研究到对功能基因组的分类与 识别，聚类分析都是必不可少的工具。聚类分析技术还在统计数据分析，模式匹配、图象处理和商 东南大学博十论文 业领域的应j = j 中显示出独到的效能。目前，基于w e b 的电子商务和数字图持馆技术方兴末艾聚类 分析技术在这些领域中都发挥了重要的作用，成为决策支持与优化服务的主要信息提取工具。 众所周知，聚类分析与回归分析、判别分析一起，构成了经典数理统计学的三大支柱。其中， 聚类分析是一种不依赖于先验知识的、从数据本身出发发现其内部分布模式的数据分析方法，它在 分析和解决缺乏背景知识的复杂问题时体现出巨大的优越性。随着数据挖掘技术的兴起和智能信息 技术的深入运用，聚类分析理论与实现技术己远远超越传统统计学的范畴，成为多学科分支相互交 义、共同作用的基础理论和应用研究领域。 近十年来，国内外有关聚类分析理论与算法的研究成果不胜枚举，所构造的各种聚类算法i l ”1 9 8 。”不下几十种并继续以更快的速度不断出现或得到改进。它们分别基丁不同的理论与方法，能够 处理这种应用领域具有不同数据类型的数据。在理论研究快速发展的同时聚类分析已成为目前智 能信息技术应用的热门工具。g o o g l e 作为全球最强大的搜索上具，采用聚类分析软件实现面向全球 用户快速、精确、齐全的搜索服务。它通过动态地访问和搜索全球4 5 0 0 个主要的新闻站点，自动地 实现文档的快速比较和聚类。正是这种先进的网页聚类技术保证了g o o g l e 在互联网搜索服务上的领 先地位。就具体的聚类分析应用系统而言，除了e n t e r p r i s em i n e r ( s a s 软件公司) 、q u e s t ( i b m ) 、 d b m i n e r ( ) j 口拿大s i m o nf r a s e r 大学h a r tj i a w e i 研究组) 、k e t i r ( 美国g t e 实验室) 等知名数据挖掘系 统都将聚类分析作为其基本的工具和功能模块之外，还涌现了一系列专门开展聚类分析研究的应用 系统，例如： 1 c l u s t e r & t r e e v i e w ：由斯坦福大学m i c h a e le i s e n 主持开发的用于大规模基因表达谱聚类分析 的著名自由软件( h t t p ：r a n a 1 b 1 g o v e i s e n s o f c w a r e h t m ) ，其中c l u s t e r 采用谱系聚类方法对微阵列数据 集进行聚类分析再通过t r e e v i e w 实现基因聚类谱系图的可视化表达。该系统已经成为生命科学研 究者破解人类基因之谜的基本工具。此外，m i t w h i t e h e a d 实验室研制的基于自组织图( s o m ) 算法的 g e n e c i a s t e r 系统( h t t p ：w w w b r o a d m i t e d u c a n c e r s o f t w a r e s o f i w a r e h t m l ) 也是面向基因聚类分析的专 用软件。 2 c l u s t a r l g r a p h i c s ：由专门致力于开发聚类分析软件的c l u s t a n 软件公( h t t p ：w w w c l u s t a n c o r n ) 开发的通用商业软件。c l u s t a n 公司研究人员除专心于聚类算法的研究以外，还研究各种现有算法的 软件实现以及各种算法对不同应用领域的适应性。c l u s t a n g r a p h i c s 具有强大的数据清洗、数据转换、 聚类分析和聚类结果的可视化表达功能。该公司网站展示了软件在各种实际领域的数十个聚类分析 示例。 除此之外，j “为采用的聚类分析专门系统还包括c 4 5 ( 基于决策树的聚类分析) 、f c l u s t e r ( 模 糊聚类分折) 、c l u t o ( 基于优化的聚粪划分) 、s p s s 等。可喜的是，国内已有包括宝山钢铁公司在 内的很多大型企业成功地将聚类分析技术引入到面向企业经营数据的知识挖掘，并自主开发符合自 身需求的应用软件( 如宝钢p m ，p r a c t i c a lm i n e r ) ，为实现管理与决策智能化迈出了重要的一步。 可以预见，随着应用领域的快速扩展和研究的不断深入，聚类分析研究与应用一定会取得更为 丰硕的成果。 1 2 2 离群点检测 与聚类分析不同，离群点检澳l j ( o u t l i e r d e t e c t i o n ) l j 是从大量事物中发现少量的与多数事物具有明 显区别的异常个体的过程p 】。它主要关注一个事物有别于常规的异常表现或行为通过对离群点的 检测和分析，使人们发现并理解异常事物的起源和机理。从数据分析的角度来看，离群点检测就是 从大量的数据中分离出少量的个体样本，它”j 在属性上与其他样本之间存在足以引起怀疑的差异。 聚类分析、分类规则与关联规则发现等数据挖掘专题主要关注于挖掘隐含子数据主体，即具有 一定规模的数据子集所共同具有的行为模式。但是，在很多应用场台，获得关于例外情况的知识比发 现常规模式更有价值。例如，电子商务中的欺诈行为，金融领域中信用i 恶意透支，网络安全中的 恶意攻击，地震预报中的异常波形等，这类行为所产生的数据记录都是夹杂在大量常规记录中的少 量个体。然而，正是对这些小部分数据所遵循模式的研究，人们才能够有效地获驭它们所代表的异 2 第一覃概述 常行为的知识，并为采取相应的对策提供依据。由此可见，对这些通常被认为是噪声的数据的发现 和研究具有特殊的意义。在数据挖掘领域，面向异常点的知识发现称为离群数据挖掘【1 pj ，它包括离 群点检测和离群点分析( o u t l i e rd e t e c t i o na n da n a l y s i s ) 两项内容。其任务是从大量复杂的数据中发现 存在丁小部分异常数据中的新颖的、与常规数据模式显著不同的新的数据模式。例如，在面向网络 登录记录数据集的知识发现应用中，离群数据挖掘的任务是发现与正常网络登录模式不同的异常模 式，即恶意入侵者对网络结点的攻击行为模式。这些恶意攻击模式的发现为研究网络入侵防范和抵 御提供了重要的线索。目前，离群数据挖掘研究正得到越来越多的重视，相关研究成果已被成功应用 丁各种风险预警和控制领域。 离群点检测同样是经典数理统计学的基本研究内容。例如，假设检验中对于一个事件作出接受 或拒绝时所依据的小概率原理，其问题本身就是现代离群点检测思想的雏形。然而，随着数据挖掘 研究的深入年u 应用的普及，离群数据挖掘研究的重要意义已经得到国内外学者的普遍认同成为一 个学科领域交叉、应崩前景广阔的专门研究主题。除了基于统计学的研究方法外，来自数据库、机 器学习、遗传算法等众多领域的研究者也就该主题开展了广泛的研究，提出了一系列具有代表性的 离群点检铡算法iv 2 0 3 1 。由于离群点检测与聚类分析在数据处理和分析过程中遵循类似的机理，因此， 很多研究者将离群点检测问题与聚类分析问题结合起来，形成了很多基于聚类算法的离群点检测方 法。 在应用领域，离群数据挖掘同样己开始发挥出重要的作用。除了部分现有通用数据挖掘系统 ( 如：s a s 、e n t e r p r i s em i n e r 、c l u s t a n g r a p h i c s 等) 已嵌入专门的离群知识发现模块以外，其他如 d e l t a m i n e r ( 发现异常数据的商业智能o l a p 系统) 、k e p l e r ( 数据偏差检测) 、w m r u l e ( 检测离群点及异 常数据模式) 、o r e a ( 基于距离的离群点检测系统) 、j a m ( j a v a a g e n t sf o r m e t al e a r n i n g ，欺诈与入侵检 测系统) 等专门系统也都在各种不同的应用领域发挥了有效的作用。 毫无疑问，离群点检测所具有的独特功能必将在更多的应用领域发挥其他工具所无法取代的功 能，从事该主题的研究具有重要的理论与实际意义。 1 2 3 与其他分支领域盼关系 目前聚类分析与离群点检测研究已成为众多信息技术领域共同关注的问题。数据库技术和程 序设计技术对于数据挖掘技术的支撑和促进作用无需赘述，数理统计学，机器学习、人工智能、粗 糙集理论、神经网络与遗传算法 t 8 - 2 5 1 等众多学科领域的研究思想与方法同样在聚类分析与离群点检 测问题的研究过程中发挥了巨大的作用。 传统的基于统计学理论的聚类方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品 聚类、有重叠聚类和模糊聚类等。这些聚类方法基于对数据的全局比较，需要考察全部数据个体以 决定类的划分。基于统计学的离群点检测方法为不一致性检验，通过对假设的验证完成对一个样本 的离群性判别。基于统计学的方法要求所有的数据必须预先给定，不具有动态分析的功能。此外， 这种方法不具有线性的计算复杂度，难以运用于具有人规模数据集的情况。 在机器学习方法中，聚类被称作无监督归纳，它与分类学习不同，不需要为数据对象预先殴定 类别标记，聚类算法通过对训练数据集的自主学习而获得。通过改变学习策略，机器学习方法同样 也可以用于离群点的检测。由予对训练数据集和背景知识的依赖陛，基于机器学习的方法不具有广 泛的适应性。此外，在实际应用中，这种方法效率较低，同样难以处理大规模数据聚类问题。 在人丁智能方法中，聚类也称为概念聚类。这是因为，数据点之间的相似性测度不再依赖于传 统的几何距离，而是通过对概念的描述加以确定。随着聚类对象的增加，概念聚类方法在数据对象 间形成概念上的分类。这种处理概念数据集的聚类思想与方法为聚类技术开辟了新的应崩领域。成 为又一个热点研究内容。在神经网络方法中，聚类被称为自组织神经网络方法，如k o h o n e n 臼组织 特征映射网络、竞争学习网络等等。近年来，人工智能与神经网络方法在离群点检测中的应用同样 受到重视并获得了可喜的进展。此外，对于聚类模式和离群点知识挖掘结果可视化方法的研究也g 起研究者极大的兴趣，这些努力为人们更好地理解、解释和运用所挖掘的知识提供了便利。 东南大学博士论文 综上所述，聚类分析与离群点检测技术受到来自众多研究领域的关注，这些领域的共同努力使 研究不断深化和扩展，成为人们获取知识和信息的益发重要的工具之一。 必须指出，经典的数理统计学理论是聚类分析与离群点检测技术的基础和本源，不论基于怎样 的研究手段，所构造的聚类分析和离群点检测方法本身及其所产生的结果的合理性都有必要在数理 统计学的意义下加以解释、支撑和检验。 本论文着眼于从传统的数理统计学基础出发，研究聚类分析与离群点检测问题，综合现有的基 于密度和基丁网格的思想，运用网格层次上近似密度构造的思想研究并提出高性能的面向大规模数 据集的聚类分析与离群点检测算法。 1 3 系统模型与基本概念 1 3 1 问题的形式化描述 图1 1 示出了描述聚类分析和离群点检测问题的物理系统( a ) 及对应的模型系统( b ) 。物理系 统一真实反映了输入数据集d = 扛，x 2 ，j 。) 所隐含的聚类模式或离群点分布特征：，= f r ( d ) 而 模型系统f 。是由研究者建立的关于b 的模拟系统，两者之间的关系为i 】： 嘞( d ) = f r ( d ) + e ( m ) ( 1 1 ) 由于( x ) 一般是未知的，因此，“m ) 可以视为建模过程中伴随的噪声或误差。由此看来，研 究并建立聚类分析或离群点检测系统的目标就是在高效地完成数据分析的基础上，使其自身的误差 e ( m ) 最小化。苛 豺 ( a ) 物理系统r( b ) 模型系统m 图1 1 聚类分析的物理系统与模型系统 具体而言，聚类问题可以形式化地表述为：给定一个d 维属性空间中的集合d = x ，i x 。= ( x 。x 。j d ) ，i = 1 , 2 ，n ) ，构造算法模型m ，将d 中的元素划分为k 个互不相交的子集合，称为聚 类( c l u s t e r ) ： c ，c ，c 。i c ，量d ) ，uc ，= d ，使得同一聚类中的数据的相似睦尽可能大，而属于 不同聚类的元素的相似性尽可能小。当k = 1 或k = n 时，称为平凡聚类，否则称为非平凡聚类o j 。 离群点又称为孤立点、野点，目前，关于离群点尚没有公认的形式化定义。事实上基于不同 的观点或离群点检测的目的不同，离群点的定义也不尽相同。在专业研究领域。h a w k i n s 首先给出 了如下的描述性定义1 ： 如果一个数据样本与其他样本之间存在足以引起怀疑的差异，则称其为离群点。 显然，这一定义与常识保持一致。但是，由于它不是一个定量的定义方法，因此，在具体进行 离群点检测时缺乏可操作性。为此，研究者基丁不同的应用目的对离群点给出不同的量化定义。例 如，以下是k n o r r 给出的基于距离的定义 7 5 1 ： 给定数据集d 和阀值f 、d ，称样本y e d 为离群点，如果存在至多f 个样本点位于爿的o - 距 离之内，即i y d id i s t ( x ，y ) 口) l f 。 在本论文研究中，我们从上述基于距离的离群点定义出发，讨论离群点检测问题。 上述定义中，集合d 中的元素j ，通常称为数据点或样本点，n = j d l 为数据集d 包含的点数。 4 第一章概述 每个数据点通常表示人们对被研究对象的一次观测或抽样( s a m p l e ) 数据点的每一维用于描述和反映 被观察对象住一个属一眭( a t t r i b u t e ) 上的取值。对于不同的属性变量来说，其取值通常分为三类：即造 续犁、序列型和名字型。 连续型l 坟值的变量可以在一定的实数区域内取值，变量的值仅受制于观测的精度，如物体的温 度等。序列型变量的各个取值之问存在序关系，可以进行比较，例如人的健康状态可以分为：差、 一般和强壮等。名字型取值除了标识数据记录在该属性上的取值外，不具有其他含义值与值之间 不具有可比性，如城市的邮政编码、售货记录中的物品名称等。 由上述形式化定义可见，不论是聚类分析还是离群点检测，合理地定义数据点之间的关系是成 功地午句造算法模型的关键。这里所指的关系就是数据点之间的相似性或相异性。 i 3 2 相似性测度 上述关1 = 聚类分析与离群点检测问题的形式化描述的核心概念是数据点之间的相似性( 或相异 性，其实质仍然是相似性1 ，即数据点之间的亲疏远近关系。为了使数据分析过程能够在严格的定量 意义上进行必须恰当地对样本点之间的相似性加以定义。数据分析应用中，描述数据对象间的相 似性度量有两种：即相似系数和距离1 ”j 。 ( 1 ) 相似系数 相似系数是描述数据对象之间相似性的测度，两个样本点之间愈相似则其之间的相似系数愈 接近1 ：否则，两个样本点愈不相似，其之间的相似系数愈接近0 ，根据给定的相似系数，可以构造 个反映数据相似形态的相似性矩阵。数据点之间的相似系数是满足如下条件的二元函数 s ：d x d _ 【- 1 ，1 】： i s ( x ，y ) 库1 ；( 1 2 ) s ( x ，y ) = s ( y ，上) ；( 1 3 ) s ( x ，x ) = i ( 1 4 ) 条件规定，一个数据点与其自身的相似性最人。在处理包含重复数据的数据集时，两个相互 重合的数据点之间的相似性等于1 常用的相似系数定义方法包括数据点间的夹角余弦和相关系数： 夹角余弦： y ， q 噩n 2 丽霸丽 a 5 yi 夹角余弦函数忽略两数据点( 向量) 间的绝对长度而考虑其在空间方向上的关系。两数据点间的相 似性反映了其在状态空间方向上的一致性，当它们在方向上一致时，夹角余弦为l ：而当两者之间 毫无相似性( 正交) 时，其夹角余弦为0 。夹角余弦方法常用来描述概念型数据点之间的相似性关系。 相关系数： e ( x 。一习( y 。一刃 n ( x ，r ) = f = = 兰= = = = = = = = = = = = 一 ( 1 6 ) 。 ( ( 一i ) 2 ) ( ( y ，一i ) ：) 相关系数是关于向量标准差的夹角余弦，它表示两个向量线性相关的程度。 r 2 ) 距离 距离是刻划数据对象间差异性的测度，冈此，数据对象之间距离的定义是有效地组织数据井加 以聚类分析的前提条件。通常地，研究者并不孤立地对数据对象之间的距离加以定义，而是将所给 定的具有d 个相互独立的属性度的数据集映射剑一个特定的d 维线性空间一上，通过对空间f “赋 予某种距离的概念而在两个数据对象之间建立适当的距离关系。显然，数据对象之闻的g e 离建立后， 5 东南大学博士论文 两者之间的距离越小，其相似性越大，否则相似性越小。 设数据集d c f 。，f “上的二元关系d i s t ：f 4 f 8 + r 称为距离，如果如叱- ) 满足： 非负性：d i s t 0 ，y ) 0 ，d i s t ( x ，y ) = 0 当且仅当x = y ；( 1 7 ) 对称性：d s t o ，z ) = d i s t ( x ，力；( 1 8 ) 三角不等式：d i s t ( x ，y ) s d i s t ( x ，z ) 十d i s t ( y ，z ) ，或( 1 9 ) d i s t ( x ，y ) m a x d i s t ( x ，z ) ，d i s t ( y ，z ) )( i 10 ) 其中，满足条件，的距离是通常意义下的距离，而满足，的距离函数称为极端距离 它在某些聚类模型构造中具有重要的应用。以下是聚类分析中常见的有关距离的定义： 闵科夫斯基( m i k o w s 婶距离( f 。距离) ： d 。( x ，y ) = ( i x 一y j1 9 ) 1 “，x ，y ef 4 ，p = l 一2 上式中，当p = l 时，为绝对值距离( 又称m a n h a t t a n 度量或网格变量) ：当p = 2 时，称为欧氏距 离：而当p = 时，d 。( x ，y ) = m a x l 。- r , l ，称为切比雪夫( c h e b y s h e v ) 距离。 马氏( m a h a l a n o b i s ) 距离 d ( x ，y ) = 瓜万可丽，x ，y e f “ ( 1 1 2 ) 其中为数据集d 所构成的数据矩阵的协方差矩阵，它是样本总体分布的协差估计量。 马氏距离的优点在于其在线性变换下的不变性，这一性质使马氏距离克n t 闵氏距离定义受量 纲影响的缺陷。同时，马氏距离还可咀有效地处理具有多重相荚性的数据。但是，协羞矩阵的构造 与计算是十分复杂的，因此，这种方法在处理大规模数据时并不适用。 兰氏( c a n b e r r a ) g l i 离 础，耻莩黼，础 ( 1 1 3 ) 同样地，兰氏距离也可以克服数据集在量纲上不一致的缺陷，而且在计算复杂度上较之马氏距离简 便。 海明( h a m m i n g ) 距离： 和上述面向数值型数据的距离不同，海明距离在两个等长的字符串之间定义距离： d ( s i ，s 2 ) = c o u n t 。( s l j s 2 ，) ( 1 t 4 ) 其中，s 。，s ，为两个字符串，s 。s i = 1 , 2 ，为其在各位上的码字。海明距离为字符型数据聚类分 析提供了基础条件，它常用于文本聚类问题。 此外，聚类分析还常采用斜交空间距离和卡方距离来对数据点之间的距离加以定义。由丁选择 不同的距离定义方法所获得的聚类结果会有所差异，因此，在实用中，可以采用几种距离进行计算、 对比，选择一种较为合理的距离进行聚类。 在本文的讨论中，我们所涉及的距离定义是在通常意义下的满足式( 1 7 ) ，式( 1 ，8 ) 和式( 1 9 ) 的闵氏距离。此外，由于所讨论的数据对象主要是数值型数据，因此在不特别声明的情况下，总假 定上述线性空间f “即为通常f 2 距离意义下的的d 维欧氏空间r “。 6 第一章概述 1 4 聚类算法概述 1 4 1 聚类的定义方法 聚类分析是面向实际应用的技术，因此，聚类的定义与待处理的数据类型有关。基丁不同的模 型构造思想，在上述形式化定义的基础上，学术界提出了一系列更加具体化的定义 1 - 5 。 ( 1 ) 基于距离的定义( d i s t a n c e - b a s e d ) ：个聚类是这样一组数据的集合，其聚类成员之间距离的 最人值仍小于这些成员到任一非聚类成员距