（计算机应用技术专业论文）高维数据聚类技术中的若干算法研究.pdf

刘佳佳：高维数据聚类技术中的若干算法研究 7 9 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名：列i 圭佳 i 签字日期：加口占年厂月。巧日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名：c 汕 弘 签字日期：弘晰r 月玎日 导师签名：蛮确v 签字日期；洳湃，月纩日 刘佳佳：高维数据聚类技术中的若干算法研究 摘要 数据挖掘是一种可以在数据库上挖掘有用信息的技术，这些信息被称为知识， 所以数据挖掘又称知识发现。从大量数据中挖掘出的知识可用于决策支持、数据 分析等领域，随着数据库的发展，数据挖掘已显得越来越重要。 随着数据规模的不断增大，传统聚类分析方法难以发挥作用。聚类操作实际 上是数据对象之间相似性的度量，相似度高的对象被归为一类。在低维空间中经 常使用欧氏距离等函数来度量相似性，但在高维情况下由于相似性没有传递性， 距离函数不再发挥作用，而高维数据的距离函数难于定义，因此必须重新考虑新 的度量数据对象相似性的标准或准则。另外，由于维数很高，传统聚类算法的计 算复杂度会很高，其应用也受到了很大的局限性。 针对高维数据引起的“维度灾难”问题，本文研究了高维数据的特点，充分 利用单维与多维的关系，提出了用单维来分割高维数据，并将数据进行整合，按 维序逐次聚类的h d c as d p 算法。在单个维上进行聚类时，采用索引转换技术来 预处理数据，从而简化高维数据处理问题。该算法每次处理只针对一个维层次， 经过层层处理，最终就能得到完整数据空间上的聚类。 在h d c as d p 算法的基础上，分析并整合了传统数据聚类算法k - m e a l l s 算法的 几种改进算法，提出了适用于更高维空间的聚类算法d f b c 。d f b c 算法首先在高 维数据空间上，将维划分为比较低的维组合，在这些维组合的数据空间上运用改 进的k _ m e a n s 算法进行聚类，以维组合为层次，聚类过程是逐层进行的，这实际上 跟单维分割聚类技术是相似的，所有层处理完之后就得到了最终的聚类结果。相 比于单维分割聚类技术，使用维分组的聚类技术更适用于大型更高维的数据空间。 该算法按照维组层次的增长，计算时间也是呈线性变化的，但是就算法的思想来 说，它是低维聚类与高维聚类技术的一种折衷。 本文还对网格的聚类技术进行了研究，分析了固定网格划分聚类与自适应网 格划分聚类存在的缺陷，针对g c o d 算法存在的缺陷，提出了一种改进的方法。 g c o d 算法主要采用了相交网格划分的措施，对固定网格划分与自适应网格划分 2 扬州大学硕士学位论文 技术采取了一种折衷的处理策略。但是g c o d 算法未对相交网格的大小进行限制， 使得这其中会存在许多不合理化聚类。我们针对这个问题提出了对网格大小进行 限制的方法，并且提出了更加合理的密度计算方法。 研究了子空间聚类的一些算法，针对经典算法c l i o u e 存在的缺陷，提出了 基于半相交网格划分的h i g s c 算法。它首先利用半相交网格划分方法在单个维上 进行聚类，然后利用类a p r i o r i 规则来形成子空间，在子空间形成的过程中运用类 h d c as d p 方法产生子空间上的聚类。算法的性能较c l i q u e 算法有了提升，在 聚类结果的精度方面提升明显。 关键词：数据挖掘；聚类；高维聚类；子空间 刘佳佳：高维数据聚类技术中的若干算法研究3 a b s t r a c t d a 忸m i l l i n gi s at e c h n o l o g yo fm i i l i n g1 1 s e f l l li n f i o n n a t i o n 疗o md a 油a s e 1 1 1 i s i n f o r m a t i o nw 1 1 i c hi sm i n e df 如md a 脑b a s ei sa l s oc a i 】e dk n o w l e d g e ，s od a 诅m i n i n gi s a l s oc a l l e dk d d ( k n o w l e d g ed i s c o v e r yi d a t a b 髂e s ) 1 1 l em i n e dl ( 1 1 0 w l e d g ec 觚b e u s e di nd e c i s i o n 锄p p o m 删y s i s 觚d 趾yo t l l c rf i e l d b yt l l ed e v e l o p m e n to f d a t a b a s e ，d a t am i i l i i 培h 船b e e nm o r em l dm o r ei m p o r t a n t b yt 1 1 ei n c r e a s eo f m e s i z eo f d a 诅i nd a t a b a s e s ，仃a d i t i o m lc l l l s t e r i l l gm 曲o d sc 趴t t a k ee f r e c t l y a c t u a l l y ，t h eo p e 洲o no fc l u s t e r i n gi sj u s tt h em e a s u r e m e mo fs i m i l 硎t y k 呐e c nd i 蜘d a 七ao b j e c 乜t 1 1 e s ed a 诅o b j e c 忸w l l i c hh a v et h eh i 曲s i n l i l 撕t ) rs h o u l d b c 鹊s i 四e dt 0 o n ec i u s t e le u c l i dd i s t 锄c e 铀c t i o na 1 1 d 柚yo t h e rd i s 乜n c eb a s e d 硒1 c t i o n sa r eu s u a l l yl i s e di nc l u s t e r i n go nl o w - d i l n e l l s i o 删d a t a b u tt l l e yc 姐t 、v o r k w e l lo nl l i 曲一d i l n e 珊i o n a ld a _ t a ，b e c 硼膪et l l e yc 距t 咖s 断k t 、v e 衄d i f f 商m to b j e c t s a d “，sd i 伍c l d tt 0d e f i n et l ：l e 知l c t i o n so nh i 曲一d i m e l l s i o n a ld a t a ，s on c w m e 邪u r e m e l l to f s i i i l i l 碰修 m u s tb e c o n s i d e r e d 0 t 1 1 e r w i ， b e c a l l s eo ft h e h i 曲- d i m e 璐i o n ，们d i t i o n a la l g o r i t h m sa l 啪y sh a v e l eh i g l lc o n l p l e x i t y 趾dl i m i t a t i o n mm e i ra p p l i c a t i o i na l l u s i o nt ot l l ep r o b l e mo f d i m e n s i 伽脚i t yc u r c a u s e db yl l i g h - d i m e n s i o n a ld a ：t a ， w ep r o p o s e dac l i l s t e r i n ga l 舒b a s e do ns i n g l e _ d i m e n s i o np a r t i t i o nw l l i c hi sc a l l e d h d c a _ s d pi nt l l i sp a 肛nt a k 韶璐eo fm er e l a t i o n s h i p0 fs i 叫e - d i m e n s i o n 孤d m l | 1 t i m i n l c l l s i o n t r a n s p o s co f m d e xo ns i i l 西e d m 城【l s i o ni st a ：k e nt 0p r e d i g e s tm e m e l l l o do fh i 曲- d i m e n s i o n a ld a _ c ap r o c e s s t h i sa l g 耐d mw o r k so no n ed i m e l l s i o r l a l 1 a y e re 踮ht i r n e ，p r o c e s s e sw i 也e a c hl a y e ra n df i n a l l ya l l 也ec l u s t e r sw i l lb eg a i n e d w eh a v ea n a l y z e d 锄di m p r o v e daf e wi m p r o v e da l g o l i t l i m so n 删t i o n a ik m e a r 坶 a 1 9 0 砌m o n 也cb 黜o fh d c a - s d pa l g o 劬m ，w cp r o p o s c dd f b ca l g o m mw h i c h i ss u i tf o ri l i 曲e r - d i m e l l s i o n a ld a _ c a d f b ca l g o 训mf i r s tp a r t i t i o n 让圮w h o l ed i m e 璐i 0 珊 t os 啪ec o m b i n a t i o i l so f l o wd i m c n s i o n s ，t h e nc l u s t 盯o ne a c hc o m b i 删o n + t h ep r o c e s s 4 扬州大学硕士学位论文 i ss i m i l 盯t oh d c a s d pa l g o 开【1 1 1 1 1 c o m p a r e dt 0h d c a _ s d p ，d f b ca l g o r i t ni s m o r es l m a b l eo nl a 增ea n di l i g h e r - d i n l e n s i o n a ld a t a 1 1 地n l n n i n g 血n eo fd f b c a l g “t i n c r e a s e sl i n e 蒯哆晰t h 恤i n c r e 船e so fc o m b i n a t i o n s n s 跏a 1 1 ya c o m p r o m i s eo f l o 、- d i m e n s i o m la n dl l i g h d i m e n s i o n a lc l u s t e r i n gm 础o do ni t si d e a w br e s e a r c h e ds o m et c c l m o l o g i e so fg 耐b a s e da i g o 棚l i n sa 工l d 姐a l y z e df i x e ( 1 鲥d b a s e d 趾da d 印t _ g r i d ss h o r t a g e s i na l l u s i o nt og c o d ss h o n a g ew ep r o p o s e d 趾 i i i l p r o v e da l g 耐恤n am e a s u r eo fi n t e r s e c t i n g 鲥di sa d o p t e di ng c o da l g o r i t h m w h i c hi sac o m p r o r n i s em 州岫do f 丘x e d - g r i d 蛆da d l p t 一鲥db a s e da l g o r i t h t i l s b u ti t h 勰n tl i m i t c d 廿l es i z eo f 抽t e r s e c t i n gg r i d s ，舡l dt h e nt l l e r ew i l lb es o m em _ a t i o n a l 畸 c l u s t e r sf i n a l l y h la 1 1 l l s i o nt 0 廿l i sp r o b l e mw ep r o p o s e dam e 出o dt or e s t r i c tt i l es i z eo f i m e r s e c t i n g 鲥d s 趾dm o r cr a t i o n a ld e n s i t yc o m p u t i n gm e 廿l o d s o m ec l u s t e r i n ga l g o r i t h f n so ns u b s p a c ea r er e s 朗m h e di i ln l i sp i p e r i na l l u s i o nt o t 1 1 e 出o n a g eo f 蛔m t i o n a lc l i q u ea l g o r i t l l m ，m g s ca j g 吲t h m d l i c hi sb a s c do nh a l f i n t e r s e c t i l l g 鲥d si sp r o p o s e d nf i f s d yc l u s t e r so na l lo f 也es i l l g kd i r n e n s i o n sb 鹪e do n h l fi n t 钉c t i n g 鲥d s t h e ng e n e e a 士c ss u b s p a c eb yt l l es i m i l a rm l eo fa 埘o r i hn l e c a u r 跎o fg e n e m t i n gs u b s p a c ec l u s t e r i n ga r e g e n e r a t e db ys i n l i l a rh d c a s d p a l g o r i t h n l c o l p a r e dt 0c l i q u e ，t l 培p e r f o l m a n c eo fh i g s ca l g o r i t h mi si m p m v e d ， e s p e c i a l l yo nm ea s p e c to f p r e c i s i o no f c l u s t e r i n 吕 k e y w o r d s ：d a 诅m i i l i n g ；c l u s t c r i n g ；l l i 曲d i m l m s i o n a lc l u s t e r h l g ；s u b s p a c e 刘佳佳：高维数据聚类技术中的若干算法研究 5 第一章引言 本论文主要讨论了什么是数据挖掘，什么是高维数据聚类，有哪些传统的聚 类技术，针对传统或现有的聚类技术的局限性，讨论如何提升聚类的性能，并将 其运用到高维数据空间聚类中。本章将介绍数据挖掘的发展，数据聚类技术的特 点及高维数据聚类技术的发展。基于这些背景知识的介绍，我们提出本文的主要 工作，即运用单维与多维的关系来实现对高维数据的有效聚类，运用相交网格的 思想来聚类子空间等，以更好的完成数据挖掘的任务。本章的最后列出了文章的 组织结构。 1 1 研究背景 1 1 1 数据挖掘的产生与发展 6 0 年代末期以来，随着计算机应用的普及和数据处理在计算机应用中所占比 重的上升，数据库技术得到了迅速发展。数据库技术与计算机网络通信已经成为 当前计算机应用中两个最重要的基础领域【。计算机的一些重要应用，如管理信息 系统、办公自动化技术、计算机辅助设计、专家系统等，大都离不开这两个基本 技术。在当前流行的数据库管理系统中，采用的数据模型主要有层次模型、网状 模型和关系模型三种。7 0 年代中期，关系数据模型渐渐成为占主导地位的数据模 型。由于关系数据库的模型结构简单，逻辑物理界面清晰，具有较强的集合处理 功能，使得数据库应用系统开发的效率大大提高。 数据库的应用己经触及到人类生活的各个方面。据统计1 9 8 9 年时全世界数据 库总量为5 0 0 万个，而且数量以每2 0 个月翻一番的速度增长着，但是对数据库中 数据的开发应用还主要是检索查询，效率很低，往往很多数据还没来得及分析就 已经过时了。9 0 年代地球探测卫星每天产生的数据，超过以前所有航测数据的总 和，即使一个人以最快的速度一刻不停地工作，也要花费几年时间才能浏览卫星 6 扬州大学硕士学位论文 一天内产生的图片，生物学领域研究的数以百万计的遗传基因，世界各国定期进 行的人口普查，国土资源地理信息，铁路动态调度控制，公安司法部门的案件处 理，都涉及巨量的数据，相当数量的数据具有很强的时效性，数据的价值随着时 间的推移而迅速降低。 数据收集与维护的目的是供人们使用。简单的数据查询或统计虽然可以满足 某些低层次的需求，但人们更为需要的是从大量数据资源中挖掘出对各类决策有 指导意义的一般知识。它们是对大量数据的高度浓缩和抽象，是对数据整体的认 识，这些经过智能分析和表示的数据才是有价值和竞争力的社会资源。 数据挖掘技术就是在这样一个时代背景下产生的。它的宗旨就是在数据库中 分析处理大量的数据，发现有用的知识，为用户提供所需问题的答案，又称为数 据库知识发现。目前对数据挖掘比较公认的定义是：从数据集中识别出可信的、 有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。“数据库知识 发现”一词第一次出现是1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能 联合会议的专题研讨会上。1 9 9 1 年、1 9 9 3 年和1 9 9 4 年又分别举行过数据库知识 发现专题研讨会。由于参加会议的人数逐年增多，所以从1 9 9 5 年开始，每年都要 举办一次数据库知识发现国际会议。 1 1 2 聚类分析 聚类分析是数据挖掘的主要任务之一【2 捌，用于发现在数据库中未知的对象类。 通过聚类过程形成的每个组称为一个聚类簇。在数据挖掘之前，对象类划分的数 据量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行合理的 分析与解释。聚类是现实世界中普遍存在的现象，其应用也非常广泛。据文献所 载，在破产预测、手写体字符的计算机识别、交通管理与塞车状况预测等方面都 有过成功应用。 在2 0 世纪7 0 年代，对聚类分析已经有了比较深入的研究。聚类的方法主要 有统计学方法和机器学习的方法。在统计学中，聚类一般称为聚类分析，主要研 究基于几何距离的聚类。在使用上，首先定义多维空间，在多维空间中计算对象 问的距离，然后以距离作为对象间的相似性判别标准。在机器学习中，聚类称为 刘佳佳：高维数据聚类技术中的若干算法研究7 无监督学习，主要体现在聚类学习的数据对象没有类别标记，需要由聚类学习算 法自动计算。 近十年左右，随着数据挖掘技术的兴起，对聚类的研究掀起了新的热潮。除 了统计学和人工智能领域的研究人员以外，数据库领域的人员也加入了研究行列， 并取得了可喜的成果。从数据库知识发现的角度看，对聚类问题的研究是从大量 的数据集中智能地、自动地抽取出有价值的聚类知识。 s 近年来，随着聚类分析应用的领域扩展和深入，高维聚类问题成为当前聚类 分析研究的重点。典型的高维聚类应用如w e b 挖掘、文本聚类、搜索引擎、客户 分析等。在数据维数较高时，传统聚类分析的性能会急骤下降，甚至无法完成聚 类任务【4 ，5 1 。这样就产生了“维度困扰”的问题，维度困扰又称维度灾难，它是指 随着维度的增长，聚类分析的计算复杂度会呈指数级增长的情况。同时，高维数 据聚类中距离函数难于定义。聚类操作是数据对象之间相似性的度量，相似度高 的对象被归为一类。低维空间中经常使用欧氏距离等距离函数来度量相似性，但 是在高维情况下由于相似性没有传递性，距离函数无法发挥作用。这样就必须重 新考虑新的度量数据对象相似性的标准或准则。另外，基于距离的聚类方法，经 常需要计算簇的均值或近邻，但在高维情况下，按距离计算的簇的均值会很接近， 聚类操作由于无法明确区分簇的中心而无法进行。并且，由于维数很高，传统聚 类算法的计算复杂度会很高，其应用受到很大局限性。 1 2 课题的引出 聚类分析由来已久，但是国际上对高维聚类算法的研究相对较晚，大致起始 于2 0 世纪9 0 年代中期，较早的研究成果是一种基于超图划分的聚类方法【6 j ，此外 是一些基于网格的方法【。7 】和基于小波变换的方法【8 】等。 文献 6 仲提出了一种基于超图划分的方法，这种方法将高维数据聚类问题转 化为图划分问题，由于图划分问题己经研究得较为成熟，这使得转化后的问题相 对易于解决，从而实现了高维数据聚类问题的一种比较有效的解决方法。 对高维聚类研究得较多的另一种方法是基于网格的方法。基于网格的方法相 对比较简单：它首先通过有限地划分每一维，将数据空间量化为超矩形单元，形 8 扬州大学硕士学位论文 成一个网格结构。然后忽略掉低密度的单元，高密度的区域则代表簇。最后将相 连的相连的高密度单元合并形成一个簇。这种技术效率较高，但是随着数据维度 的增长，单元的数量以指数形式增加。并且，对分散在不同网格中的，但是原该 属于一类的数据作了划分，使得它们不一定被聚为一类，固定网格划分聚类遇到 的主要问题被称为聚类边界不明确。为了解决上述网格在高维空间中的问题，出 现了几个改进的网格划分聚类方法，分别是：w j v e c l u g t e r 【踟，c l i q u e 9 l ，m a f i a 【1 0 1 ， e n c l u s 【1 1 1 和o p t i g r i d 【1 2 1 算法等。 在美国休斯顿举行的第五届关于数据挖掘的s l a m ( i n t e m a t i o n a lc o 疵r c n c e o nd a t am i l l i n g ) 会议指出，当前许多应用领域都需要进行高维数据分析，数据的 维度通常是成百上千，而且非常稀疏，对这样数据进行聚类分析是目前相关研究 界面临的一个新兴挑战。 国内对面向数据挖掘的聚类算法研究相对起步较晚，但有着较大的发展空间， 目前在空间数据聚类上的研究已取得一些成果。 。 综上所述，目前高维聚类算法研究正处于发展初期，而随着信息时代的发展， 高维数据聚类在许多应用领域逐渐体现出其重要性，因此，对高维数据的聚类算 法进行研究并提出高效可行的算法是非常有意义的。 1 3 论文的主要工作 在论文中我们首先介绍了数据挖掘的基本原理以及相关数据聚类的方法和应 用，展望了当前数据聚类的研究热点和研究现状。然后对高维数据聚类技术作了 具体的介绍，结合相关问题对高维数据聚类算法进行了研究，在借鉴国内外在数 据挖掘与高维数据聚类处理方面已有成果的基础上，提出了利用单维与多维的关 系来聚类高维数据的方法，并利用相交网格聚类技术与子空间聚类技术来解决维 度困绕的难题。首先在高维数据的完全空间聚类方面，我们介绍了当前存在的传 统聚类技术，设计了一种基于单维分割的高维数据聚类技术，从而缓解了维度困 绕的问题。在子空间聚类方面，结合基于相交网格划分的方法与子空间聚类的传 统算法，提出了自己的见解和解决方案，为解决高维数据聚类问题提供了实际可 用的方法。 刘佳佳：高维数据聚类技术中的若干算法研究 9 1 ) 在高维数据集上使用单维分割的技术 研究高维数据的特点，比如稀疏性等问题，充分利用单维与多维的关系，提 出以单维分割高维数据，并将数据进行整合，按维序逐次聚类的技术。其中，设 计了将高维数据进行索引转换，从而达到降低维度的技术，它能快速生成各个维 的对象表示，从而简化高维数据处理问题。该技术由于每次处理只针对一个维， 因而可以将维作为层次，经过层层处理，最终就能得到完整数据空间上的聚类。 该算法按照维的增长，计算时间是呈线性变化的，可见维度困绕的问题得到了很 好的解决。 2 ) 在更高维数据集上使用维分组技术 研究了在低维数据空间上传统数据聚类算法k m e a n s 算法的几种改进算法， 并提出了对这几种改进算法的整合，从而形成了比较完善的k - m e 锄s 算法。在大 型高维数据空间上，将维划分为比较低的维组合，在这些维组合的数据空间上运 用改进的k m e a i l s 算法进行聚类，以维组合为层次，聚类过程是逐层进行的，这 跟单维分割聚类技术是相似的，所有层处理完之后就得到了最终的聚类结果。相 比于单维分割聚类技术，使用维分组的聚类技术更适用于大型更高维的数据空间。 该算法按照维组层次的增长，计算时间也是呈线性变化的，从算法的思想来看， 它是低维聚类与高维聚类技术的一种折衷。 3 ) 利用相交网格进行聚类 对基于网格的聚类技术进行了研究，分析了固定网格划分聚类与自适应网格 划分聚类存在的缺陷，并研究了克服这种缺陷的g c 0 d 算法，同时分析了g c 0 d 算法存在的缺陷，提出了一种改进的策略。g c o d 算法主要采用了相交网格划分 的措旌，对固定网格划分与自适应网格划分技术采取了一种折衷的处理策略。但 是g c o d 算法未对相交网格的大小进行限制，使得这其中会存在许多不合理的聚 类。我们针对这个问题提出了对网格大小进行限制的方法，并且提出了更加合理 的密度计算方法，从而大大改善了g c o d 算法的执行效果与执行性能。 4 ) 利用半相交网格划分技术聚类子空间 研究了高维数据子空间聚类的经典算法。分析了其存在的缺陷，提出了利用 相交网格划分的方法h i g s c 来改善这些问题。h i g s c 首先利用半相交网格划分方 1 0 扬州人学硕士学位论文 法在单个维上进行聚类，然后利用类a p r i o r i 规则来形成子空间，在子空间形成的 过程中运用类h d c as d p 算法产生子空间上的聚类。h i g s c 算法性能比c l i q u e 算法有了很大提升，在聚类结果的精度方面提升比较明显。 5 ) 索引转换技术的研究 在单个维上进行聚类往往需要索引转换的预处理，这样能加快算法的处理， 这种转换实际上是将关系数据库中的数据记录进行了转置存储。转置后的数据库 与原数据库占用相同的空间。因而，实际应用中，我们可以直接将数据存储为转 置数据库的形式以便于利用本文的相关方法进行聚类。 本文重点讨论了以上几个方面的内容，并分别在以下的章节中具体说明。在 论文的最后一章，我们设想了将来需要研究的方向： 1 ) 降维技术的研究； 2 ) 高维完整空间的并行聚类技术研究； 3 ) 子空间上的并行聚类技术研究。 1 4 本文创新点 本文的主要创新点如下： 1 ) 提出了基于单维分割的h d c as d p 算法。h d c as d p 算法利用单维与多 维在聚类处理上的关系，以维为层次，首先在第1 层进行聚类，然后将聚类得到 的结果作为第2 层的输入，在第2 层上进行聚类，再将得到的聚类结果作为第3 层的输入进行聚类，依次类推，直到所有的层被处理完就得到了最终的聚类结果。 聚类时维所起的作用是划分数据，将不属于一类的数据划分开，这样可自然形成 聚类，经过层层划分，最终得到的即是用户要求的聚类。单个维上的聚类操作采 用了基于网格与密度的算法思想。首先将当前的维按其属性值范围划分为多个网 格，然后计算每个网格的密度，视高密度的网格为聚类，相连的高密度网格在聚 类过程中被合并。 2 ) 在h d c as d p 算法的基础上，提出了适用于更高维空间的聚类算法d f b c 。 d f b c 算法是h d c as d p 算法的扩展，它将h d c as d p 算法中的层次扩展成了 维组合，在d f b c 算法中需要用到维分组的技术。一般情况下，将相关的维划分 刘佳佳：高维数据聚类技术中的若干算法研究 1 1 到一个维组合中，每个维组合都应是低维的。以维组合为层次代替h d c 气_ s d p 中 的维层次进行聚类。单层上的聚类操作采用了在艮m e a n s 算法基础上进行改进 的1 k m e a n s 算法。 3 ) 提出了基于相交网格划分聚类算法g c o d 的改进算法i g c 0 d 。由于g c 0 d 算法未对相交网格的大小进行限制，这就使得在算法执行过程中出现的过小的相 交块会被认为是高密度块，并以它为聚类中心合并相交的网格，形成不合理的聚 类。同时，简化的网格密度计算方法也加剧了这一问题，从而得到更多不合理的 聚类。针对g c o d 算法存在的这些缺陷，提出了限制相交网格大小与更加合理的 密度度量的方法，并在此基础上提出了i g c o d 算法。 4 ) 提出了基于半相交网格划分的子空间聚类算法h i g s c 。h i g s c 算法首先 利用半相交网格划分方法在单个维上进行聚类，然后利用类a p r i o r i 规则形成子空 间，在子空间形成的过程中运用类h d c as d p 算法产生子空间上的聚类。h i g s c 算法的子空间产生过程是自底向上的，以低维度的子空间为基础产生高维度的子 空间，以低维度子空间的聚类结果作为输入，在高维度子空间上进行聚类，当不 再产生聚类时，算法结束。 经实验验证，以上这几种算法是适用于高维数据聚类的，文中给出了相关的 实验分析。 1 5 论文组织 论文以下章节的组织结构如下： 第一章，引言。主要介绍了数据挖掘的发展，数据聚类技术的特点及高维数 据聚类技术的发展情况，并说明了本文的相关研究工作及本文的组织结构。 第二章，基本理论。简要地介绍数据挖掘的基本概念，聚类技术的概念与描 述，聚类技术的分类，高维数据聚类技术的相关问题与分类。 第三章，基于单维分割的高维数据聚类算法。讨论了运用网格与密度相结合 的方法聚类单维数据，并利用单维与多维的关系来实现的聚类算法h d c a - s d p 。 第四章，高维数据的维分组聚类技术。在h d c a s d p 算法的基础上提出在更 高维数据空间上，对维进行分组，将分组视为层次，利用单层数据空间与多层数 1 2 扬州大学硕士学位论文 据空间的关系来实现更高维数据的聚类，提出了d f b c 算法。 第五章，基于相交网格划分聚类的i g c o d 算法。分析了g c o d 算法存在的 缺陷，针对这些缺陷进行了改进，并提出了i g c o d 算法。 第六章，基于半相交网格划分聚类的子空间聚类h i g s c 算法。结合经典子空 间聚类算法c l l 0 u e 提出了聚类性能更好的的h i g s c 算法。 第七章，总结与展望。总结并给出了本论文的主要贡献及未来的工作展望。 刘佳佳：高维数据聚类技术中的若干算法研究1 3 第二章基本理论 本章讨论了高维数据聚类相关的基本理论，为后面章节更好地理解高维数据 聚类问题提供了理论基础。本章内容包括数据挖掘的定义及其分类，聚类问题的 描述、聚类中常用的概念及聚类技术分类，高维数据聚类的概念及其分类等。 2 1 数据挖掘简介 2 1 1 数据挖掘定义 随着数据库信息系统和计算机网络的发展与应用，各种数据源中都积攒了大 量的数据，造成了“数据丰富，但信息贫乏”的尴尬局面。数据挖掘作为一个面 向这个问题的技术就应运而生了。数据挖掘又称作数据库中的知识发现 ( k d d i 江o w l e d g ed i s c o v e r yi 1 1d a 诅b a s e ) ，在k d d9 6 国际会议上，k d d 被定义 为：对数据库中蕴涵的、未知的、有潜在应用价值的、非平凡的模式的提取i l 引。 它包括数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估和知识 表示等多个步骤，数据挖掘是对经过预处理的数据进行处理抽取知识的过程。 数据挖掘的对象往往是大规模的高维数据，这些数据可能来自于数据库、数 据仓库或其它数据源。同时，数据挖掘的结果是准确的、有用的、未知的、可解 释的，知识可能以各种形式存在：概念、规则、模式、约束等。另外，数据挖掘 的目的是支持决策分析，由于决策分析往往是有时间要求的，所以数据挖掘过程 必须高效。 2 1 2 数据挖掘分类 数据挖掘是一门交叉学科，受多个学科的影响，包括数据库系统、统计学、 机器学习、可视化和信息科学等。此外数据挖掘方法使用了大量其它学科的技术， 如神经网络、模糊逻辑、粗集理论、知识表示、归纳逻辑程序设计或高性能计算 1 4 扬州大学硕士学位论文 等。正由于数据挖掘源于多个学科，数据挖掘研究就产生了大量的、各种不同类 型的挖掘系统。因此，要对这些挖掘系统给出一个清楚的分类，这种分类可以帮 助用户区分并确定最适合需要的数据挖掘系统。根据不同的标准，数据挖掘系统 有很多种分类f 1 3 - 1 6 1 _ 1 ) 根据数据库类型分类 数据挖掘所基于的数据库类型有：关系型、事务型、面向对象型、推论型、 空间型、时序型、多媒体型、异质型、主动型、遗留型、文本挖掘和基于网络信 息的挖掘等。 2 ) 根据得到的知识分类 包括关联规则、特征规则、分类规则、判别规则等的挖掘和聚类、演变分析、 偏差分析、孤立点分析和相似性分析等，此外根据所挖掘的知识的抽象层次进行 划分，包括原始数据层知识、多层次知识和高层次知识的数据挖掘。 3 ) 根据所采用的技术分类 包括人工神经网络【1 7 - 1 踟、决策树1 9 1 、遗传算法【2 0 】、粗集理论【2 j 】、最近邻技术、 可视化技术等。 2 1 - 3 数据挖掘系统功能 数据挖掘系统要能够挖掘多种类型和各种粒度的模式，以适应不同的用户需 求或不同的应用。数据挖掘系统应当允许用户指导或聚焦有趣模式的搜索。数据 挖掘的系统功能包括如下一些： 1 ) 关联规则分析 关联分析发现关联规则，这些关联规则展示在给定的数据集中属性值频繁的 一起出现的条件。一个关联规则是形如x y ，即“a 1 a 。一b 1 b 。”的规则， 其中a i ( i 1 ，m ) ，b j ( j 1 ，_ ，n ) ) 是属性- 值对。关联规则x y 解释为“满 足x 中条件的数据库元组在一定程度上也满足y 中的条件”。一个以上的属性或 谓词之间的关联称为多维关联规则，单个谓词的关联规则称为单维关联规则。有 了这样的规则，就可以对其中一项的属性根据其它相关联的属性进行预测。 关联分析中的常用算法有候选集算法和非候选集算法两大类。候选集算法有 刘佳佳：高维数据聚类技术中的若干算法研究1 5 a p r i o r i 【矧算法以及许多基于a p 面r i 的改进算法，比如a p r i o r ir n d 【2 3 1 算法和使用哈 希技术改进的a 嘶o r i 【2 4 1 算法。非候选集算法不产生候选集，包括采用模式增长技 术的f p g r o w 【h 2 5 】和h m i n e 算法等。为了有效评价关联分析的结果，引入了置 信度和支持度的统计学概念，有的科学家还引入了相关支持度来评价关联分析的 结果。 2 ) 分类和预测 分类找出并区分数据类或概念的模型，以便能够用模型预测类标记未知的数 据对象，分类模型是基于对训练数据集的分析，分类模型可以有多种形式的表示 方法，如分类规则、决策树和神经网络等。分类可用来预测数据对象的类标记。 在某些情况下，需要预测某些空缺的值或未知的数据值，当预测的值是连续值时， 通常称之为预测。分类借鉴了很多机器学习、统计学和信息科学中成熟的技术和 思想，比如决簧树、神经网络、遗传算法等等。 3 ) 聚类分析 与分类和预测不同，聚类在不考虑己知类标记的情况下分析数据。通常训练 数据对象不提供类标记，聚类可以产生这种类标记，数据对象根据最大化类内的 相似性、最小化类间的相似性的原则进行聚类或分组，所形成的每个聚类可以看 作一个对象类，由它可以导出规则。 2 2 聚类技术 2 2 1 聚类问题的描述 所谓聚类，是指将数据对象分组成为多个类或簇，同一个类中的对象之间具 有较高的相似度，不同类中的对象差别较大。聚类问题的一般描述陆2 7 1 是： j = ( 墨，置h 以) 是n 个数据对象的集合，c = 瞩，g i i - ，q ) 是k 个数据对象 集合或组；c l uc 2 u u q = x ，c j n c ，= o ( f ，) ，g o ( ，= l ，足) ，即通过聚类算 法，n 个数据对象分别组成k 个数据组，每个组至少包含一个对象，每个对象必 须属于且只属于一个组。 1 6 扬州大学硕士学位论文 聚类的结果可以表示为u = c ，。，其中，= 骺，当值为时，；对象属 世 于组k ，当值为。时，i 不属于组k 。= 1 ，f = 1 ，2 ，；七= l ，2 ，k ， = 1 o ，1 k f = l ，2 ，；= 1 ，2 ，x 。 2 2 2 相似度度量 聚类时要根据对象之间的相似度把属性值相近的对象放入同一个聚类中，而 不相近的对象归入不同的聚类。所以，相似度的度量方法，直接决定着聚类的结 果。由于描述对象的变量类型的不同，度量的方法也不相同。 1 ) 数值变量 一般地，我们用特征空间中的距离作为度量标准来计算两个样本间的相似度， 常用距离度量标准有三种： 欧几里得距离( e i l c l i d e a n ) ：d 。( x ，_ ) = ( ( 一b ) 2 ) “2 ( 2 1 ) i = l 曼哈坦距离( m 柚h a t t a l l ) ：d 2 ( ，x ) = i h 一i ( 2 2 ) 明考斯基距离( m i l l l 【。w s k y ) ：以( t ，0 ) ：( 兰k 一1 9 ) 1 ， ( 2 3 ) 2 ) 标称变量 标称变量指其中每个属性只能取若干个状态值的变量，它们之间的相似度可 以用相同属性值的数目和所有属性的总量的比值来计算。用公式来表达就是 d ( f ，) = 竺，这里p 是属性的总数，m 是属性值相同的数目。 p 3 ) 向量变量 在一些应用，如信息检索，文档聚类或生物分类中，需要面对较复杂的对象。 为了衡量这些复杂对象的距离，引入一种非距离的相似度函数： 设两个向量石= 瓴，x ：，算。) ，r = ( m ，y ：，) ，则它们的相似度为： 刘佳佳：高维数据聚类技术中的若干算法研究1 7 姒喵护 2 2 3 聚类技术分类 ：，主n ：r i d j ( 2 4 ) 目前低维空间数据的聚类主要可以分为以下的几类阱堋： 1 ) 划分方法：最典型的基于划分的方法是k 平均 3 0 j l 】和k 中心法【3 2 】，包括 c i ，a r a 和c ia ra n s 【3 3 1 等。划分方法的基本思想是：给定划分簇的数目k ，划分 方法往往采用随机取点的方式，首先创建初始的k 个簇。然后采用一种迭代的重 定位技术，通过对象在不同的簇问移动改进划分质量。一般情况下，在同一个簇 中的对象之间尽可能“接近”或相关，丽不同簇的对象之间尽可能“远离”或不 同。在k 平均算法中，每个簇用簇中对象的平均值来表示。而在k - 中心算法中， 每个簇用接近聚类中心的一个对象来表示。这些聚类方法对在中小规模的数据库 中发现球状簇很适用，对大规模的数据集进行聚类，以及处理复杂形状的聚类， 基于划分的方法就不一定能很好地发挥作用了。 2 ) 层次的方法：层次的方法通过对给定的数据对象集按层次进行分解，形成 一棵以数据子集为节点的树。层次方法可分为凝聚和分裂两类方法。凝聚的聚类 方法，也称为自底向上的方法，首先将每个数据对象视为一个簇，然后根据某些 准则，由底向上，直到所有子簇被合并成为一个簇，或满足某个终止条件为止。 分裂聚类则相反，首先将所有数据对象放在一个簇中，然后按照两个子簇中心距 离最小准则，将一个簇分裂为若干个子簇，直至每个对象自成一簇，或达到某个 终止条件。层次方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能 被取消，虽然计算代价会很较小，但是，它不能更正错误的决定。有两种方法可 以改进层次聚类的结果：第一，在每层划分中，仔细分析对象间的“联接”，例如 c u r e 【3 4 j 和c h a m e l e o n 【3 5 1 中的做法。第二，综合层次凝聚和迭代的重定位方法。首 先用自底向上的层次算法，然后用迭代的重定位来改进结果，例如在b i r c h 断】中 的方法。 3 ) 基于密度的算法：绝大多数划分的方法是基于对象之间的距离进行聚类的。 1 8 扬州大学硕士学位论文 这样的方法只能发现球状的簇，而基于密度的方法可以发现任意形状的簇。在基 于密度聚类方法中，只要临近区域的密度超过某个闽值，就继续聚类。即对给定 类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样 的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。d b s c a n 【3 是一 个有代表性的基于密度的方法。它根据一个密度闽值来控制簇的增长。o p l r i c s 【3 8 l 是另一