（计算机应用技术专业论文）不确定数据聚类研究.pdf

大连理工大学硕士学位论文 摘要 不确定数据是近年来在传感器网络( w s n ) 、无线射频识别( r f i d ) 等领域中涌 现出来的一类新数据，对不确定数据聚类分析已经成为数据挖掘领域研究的新热点。本 文阐述了数据不确定性形成的原因和表现形式，列举已有的不确定数据聚类算法的基本 思想和优缺点，通过这些分析了解到，现有不确定数据聚类算法主要是对传统的聚类算 法进行扩展而形成的，算法的流程也都是基于经典的确定对象聚类算法流程。 由于数值型数据的聚类问题已经被证实了是n p 难解的组合优化问题，而骨架作为 全局最优解的共同部分是获得n p 难解问题启发式算法的有利工具。但是在很多问题中 骨架很难获得，近似骨架可以很好的模拟全局最优解，所以对于很多n p 难解问题都采 用近似骨架进行算法优化。本文提出了一种基于近似骨架的不确定数据聚类算法框架 a b a u d c ，主要分为初始聚类产生局部最优解、构造近似骨架和二次聚类三个模块。它 采用已有的c k m e a n s 算法作为生成局部最优解的初始聚类算法，简化了对不确定数据 对象期望距离的计算。在获得近似骨架后，将约束条件加入到不确定数据集中，并调用 s s i m e a l l s 作为二次聚类算法进行半监督学习。 a b a u d c 算法特点：一是具有很好的灵活性，它提供的是一个算法框架，任何现有 不确定聚类算法都可以作为它的模块；二是实现简单，利用近似骨架作为约束条件，只 需进行简单的相交操作就能缩小二次聚类过程中解的搜索空间，实现算法的快速收敛。 为了验证新算法的聚类效果，首先构造了以u c i 机器学习库中四个经典数据集为原始点 的不确定数据集，然后在各个数据集上进行算法比较。通过平均质量标准对a b a u d c 算法和无监督的u k m e r t l s 算法的聚类效果进行评估。实验证明，新算法的聚类准确度 得到了显著的改善。 新算法的提出，将两个不同领域知识进行了有效的结合，为不确定数据聚类研究工 作拓展了思路，同时也为骨架研究找到了新的应用领域。 关键词：不确定数据挖掘；聚类；近似骨架；半监督学习 不确定数据聚类研究 r e s e a r c ho nc l u s t e r i n go fu n c e r t a i nd a t a a b s t r a c t u n c e r t a i nd a t ai saf o r t h c o m i n ga r e ai nd a t am i m n g ，w i t hn u m e r o u sa p p l i c a t i o n si n w i r e l e s ss e n s o rn e t w o r k s ( w s n ) ，r a d i of r e q u e n c yi d e n t i f i c a t i o n ( r f i d ) ，e t c t 1 1 i sp a p e r i n t r o d u c e st h er e a s o n sc a u s i n gu n c e r t a i na n dd a t at y p e s ，t h e ns u m m a r i z e se x i s t i n ga l g o r i t h m s f o rc l u s t e r i n go nu n c e r t a i nd a t a a f t e ra l lo ft h e s e ，t h i sp a p e ri l l u s t r a t e st h a ta l lt h ew o r k so n c l u s t e r i n go nu n c e r t a i nd a t aw h i c ha r ee x t e n d e do nt r a d i t i o n a lc l u s t e r i n gm e t h o d s i n c et h ec l u s t e r i n gp r o b l e mo nn u m e r i cd a t as e t sc a nb ef o r m u l a t e da sat y p i c a l c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m a n di th a sb e e np r o v e dt ob en p h a r d t h eb a c k b o n e ( t h e s h a r e dc o m m o np a r t so fa l lo p t i m a ls o l u t i o n s ) a sau s e f u lm e t h o dc a l ls o l v et h en p h a r d p r o b l e m s h o w e v e r , i ti sh a r dt og a i nt h eb a c k b o n e ，a n dr e p l a c e s 晰t l lt h ea p p r o x i m a t e b a c k b o n eb yu s i n gt h ei n t e r s e c t i o no fl o c a lo p t i m a ls o l u t i o n s t l l i sp a p e rp r o v i d e san e w a l g o r i t h ma b a u d c a saf r a m e w o r kw h i c hi sb a s e do na p p r o x i m a t eb a c k b o n e mn e wa l g o r i t h mi n c l u d e st h r e em o d e l s ，a n df i r s t l y ，i tu s e sc k m e a n s a l g o r i t h mf o rt h e i n i t i a lc l u s t e r i n g ，a n di tr e d u c e st h ec o m p l e x i t yo f c o m p u t i n ge x p e c t e dd i s t a n c e s s e c o n d l y ， a p p r o x i m a t eb a c k b o n ei sg e n e r a t e db yi n t e r s e c t i o no fl o c a lo p t i m a ls o l u t i o n s ，a n dt h es e a r c h s p a c ec a nb ed r a m a t i c a l l yr e d u c e db yf i x i n gt h ea p p r o x i m a t eb a c k b o n e ，t h e ni tr e d u c e ss e a r c h s p a c ec a nb ee f f i c i e n t l ys e a r c h e dt of i n dh i g l lq u a l i t ys o l u t i o n s t h i r d l y ，t h es e m i - s u p e r v i s e d i m e a n sa l g o r i t h mi sg i v e ni na b a u d ct oc l u s t e rw i t hc o n s t r a i n t s t h ee x p e r i m e n t so nu c id a t a s e t ss u c ha sh a b e r m a n s u r v i v a l w i n e s o y b e a na n dg l a s s p r o v et h a ta b a u d ca l g o r i t h mc a ni m p r o v ec l u s t e r i n gp r e c i s i o nt h a nu k m e a r l s a n di t p r o p o s e st h a ta b a u d ca l g o r i t h mi s an e wm e t h o dw i t hf l e x i b i l i t ya n ds i m p l i c i t yo n c l u s t e r i n gf o ru n c e r t a i nd a t a k e yw o r d s ：u n c e r t a i n d a t a m i n i n g ；c l u s t e r i n g ；a p p r o x i m a t eb a c k b o n e ； s e m i - s u p e r v i s e dl e a r n i n g 1 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：至至塑鋈塑垒鏊耋塑堡 作者签名：生鍪 日期：毕年旦月卫日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名：芝7 煎 日期：主竺j 年三月卫日 日期：幽年月坐日 大连理工大学硕十学位论文 1 绪论 随着计算机与因特网的出现，我们的生活正逐渐被数据信息所淹没。数据挖掘技术 帮助我们解决如何在海量的数据中寻找有用的信息，如何对数据进行有效的管理以及如 何通过分析历史数据预测未来行为。 人类在数据库管理和数据挖掘领域中所进行的研究都是基于确定性数据的。随着数 据采集和处理技术的发展，我们开始将注意力转移到不确定数据上。由于各种应用的驱 动，针对不确定性数据的研究已经成为国际学术界和工业界的热门课题。 近年来，很多重要国际会议( s i g i d ，i c d m ，s d m 等) 纷纷将不确定性数据的研 究列为重点征稿范围，还出现了多个专门针对不确定性数据挖掘的w o r k s h o p ( d u n e 0 7 ， m u d 0 8 s u m 0 9 ，m o u n d 0 9 ) 。而i e e et r a n s o nk n o w l e d g ea n dd a t ae n g i n e e r i n g ( t l e ) 杂志也专门安排了针对不确定性数据挖掘的专刊，计划在2 0 1 0 年5 月出版。 1 1不确定数据概述 不确定数据是在传感器网络w s n ( w i r e l e s ss e n s o rn e t w o r k s ) 、无线射频识别r f i d ( r a d i of r e q u e n c yi d e n t i f i c a t i o n ) 、g p s 定位、隐私保护等应用中涌现出来的一类数据， 其特点是每个数据对象不是单个数据点，而是按照概率在多个数据点上出现。 1 1 1产生原因 在不同应用领域里，数据的采集工作常常伴随着误差或人为干扰等因素进行着，这 样产生的数据就具备了不确定性。下面举例说明产生不确定数据的原因： ( 1 ) 由于数据采集方式的技术限制等【l - 2 】带来的数据不确定性。比如在无线传感器 网络中，传感器节点由于受到环境干扰、机械故障、仪器精度、数据融合等影响，所监 测到的数据往往带有一定的噪声。而在r f i d 应用中，现有的接收设备的准确率不能达 到1 0 0 ( 远距离的r f i d 设备的精度在8 0 9 0 左右) ，因此所接受的数据存在一定的 不确定性。 ( 2 ) 数据的所有者出于隐私保护等【3 】目的考虑，对数据进行扰动，获得不确定性数 据。比如，在电信、金融、保险等企业中存有大量的客户数据，在新推出相关产品前会 对既有的客户数据进行数据挖掘，以寻找的潜在目标客户。当这些数据挖掘任务委托给 第三方服务商时，有必要对于原始数据进行一定扰动，以保证客户敏感资料的安全。另 外，在公共安全领域，对于某些特殊人群的行为习惯进行数据挖掘时，也有必要对数据 进行扰动，避免这些敏感信息外泄。 不确定数据聚类研究 ( 3 ) 利用预测、归纳等统计学方法构造数据属性时常造成数据本质信息的丢失。 例如，当数据来源于移动物体的应用中，数据对象的运动轨迹不可预知，只有用预测等 方法估量，这样得到的数据从本质上就是不确定的。 综上可知，不确定数据的产生是由现实应用所驱动的，在本篇论文里，我们把( 1 ) 和( 3 ) 称作被动式需求驱动原因，( 2 ) 称作主动式需求驱动原因。 1 1 2 表现形式 不确定数据在数据挖掘研究范畴内的表现形式可分为存在不确定性和属性不确定 性【4 】。 ( 1 ) 存在不确定性( 也称元组不确定性) ：一个数据库中的数据元组存在与否具 有一定的概率，这种概率性同时又会影响其他数据元组的存在。在通常情况下，假设各 个元组之间是相互独立的，以便在不同的应用进行数据处理。 ( 2 ) 属性不确定性( 也称值不确定性) ：针对元组数目和模型已经被确定的前提 下，属性值中存在的误差所造成的不确定信息常通过概率密度函数p d f ( p r o b a b i l i t y d e n s i t yf u n c t i o n ) 或其他统计量( 如方差、协方差等) 表示。在不确定数据挖掘研究领 域多考虑基于p d f 建模的不确定性数据。 1 2 不确定数据挖掘相关工作 针对不确定数据的研究主要包括数据管理和数据挖掘两大方面。在数据管理方面， 由于传统技术已经无法应对不确定数据，大批学者和工业界对研发新型的不确定数据管 理技术产生了浓厚兴趣，主要的研究方向包括：数据不确定性的表示与模型定义【5 吲、 预处理和集成3 1 、存储与索引”1 7 1 以及查询分析处理【1 8 。2 刁等。目前，不确定数据管理 研究已经相对成熟，论文【4 】 2 3 】【2 4 】分别从不同的角度分析和阐述了不确定数据管理技 术，文献r 2 5 y l j 举了一些知名的科研机构正在进行的相关项目研究的基本情况。 与数据管理相比，不确定数据挖掘还不十分成熟。传统意义上，数据挖掘是指从大 量的原始数据中挖掘出隐含的、有用的、尚未发现的知识和信息。而更广义的说法是： 数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。它作为一门 交叉性学科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视 化、高性能计算、专家系统等多个领域。在许多应用方面，由于数据不确定性对挖掘结 果产生了不可忽视的影响，传统的针对确定数据的挖掘算法已经不能满足现实应用的迫 切要求，这使得专门针对不确定数据挖掘技术的研究十分必要。 目前，主要研究内容为分类、聚类、频繁项集挖掘以及孤立点检测。 大连理工火学硕十学位论文 1 2 1 聚类 近年来，对不确定性数据的聚类研究得到了广泛的关注。目前普遍的思路是将传统 的( 面向确定数据) 聚类方法推广到不确定数据，目前针对不确定数据的聚类研究一是 扩展基于划分的传统聚类算法，二是扩展基于密度的传统聚类算法。详细内容参见第三 毫。 1 2 2 分类 对于传统数据，常用的分类法包括：决策树分类法、基于规则的分类法、最近邻法、 神经网络、支持向量机和贝叶斯分类法。随着对不确定数据逐步深入的研究，传统的分 类方法扩展到不确定数据领域是一种必然的趋势。目前，主要的不确定数据分类算法包 括如下两种。 ( 1 ) 支持向量机的不确定分类法 支持向量机s v m ( s u p p o r tv e c t o rm a c h i n e ) 是一种基于统计机器学习理论的分类技 术，在文本分类、手写数字的识别等领域具有众多应用【2 6 1 。 针对不确定数据的支持向量机算法，把文本或图像属性等输入数据中存在的噪声点 作为不确定性。而且它基于这样一个假设，即观测到的噪声点不论是出现在训练集还是 检验集，对训练和检验过程的影响作用可看作相近的。所以很多分类方法只需在训练集 或者检验集中的一个考虑其噪声点的影响。 b i 和z h a n g 受总最d , - 乘回归方法( t o t a ll e a s ts q u a r e sr e g r e s s i o nm e t h o d ) 的启发， 在论文 2 7 】中提出了基于不确定数据的总支持向量分类法t s v c ( t o t a ls u p p o r tv e c t o r c l a s s i f i c a t i o n ) 。其训练集是带有噪声输入的，噪声点的选取采用的是具有统一先验的简 单有界的不确定模型，而不是一般意义上的高斯噪声。同时，方法还给出了一个直观的 几何表达，即它可以优化存在于所有边界上的两个类之间的“概率分离 。通过实验证 明，在解决不确定数据的分类问题时，t s v c 方法无论在人造数据集还是真实数据集上 分类的精度都优于标准的s v m 方法。 此外，b h a t t a c h a r y y a 等人1 2 8 1 提出了一种利用二阶锥规划s o c p ( s e c o n do r d e rc o n e p r o g r a m ) 和切比雪夫不等式( c h e b y s h e vi n e q u a l i t i e s ) 构造二元分类器的方法。此分类 器既可应用于分类问题又可应用于回归问题。在分类问题中，通过设置最坏情况下噪声 点的影响参数，分离训练集数据。在回归问题中，给出两种使用切比雪夫不等式改进 s o c p 的方法，并用它们分别构造相应的线形回归函数。 上述两种方法适用于简单的线性模型，对于更复杂的非线性模型，y a n g 和g u n n 在 文章 2 9 】和 3 0 1 中提出了三种迭代提升算法：一是基于线性模型的u s v c 方法( u n c e r t a i n t y 不确定数据聚类研究 s u p p o r tv e c t o rc l a s s i f i c a t i o n ) ，它也是一种二阶锥规划问题，可看作是s v c 方法的泛化； 另外两种方法都是基于非线性模型的、并把噪声特有协方差信息( n o i s e s p e c i f i c c o v a r i a n c ei n f o r m a t i o n ) 作为输入限制的迭代算法。这两种方法分别为：整合t s v c 和 u s v c 的a u s v c 方法( a d a p t i v eu n c e r t a i n t ys u p p o r t v e c t o rc l a s s i f i c a t i o n ) ；整合m p m ( m i n i m a xp r o b a b i l i t ys u p p o r tv e c t o rc l a s s i f i c a t i o n )和s v c 的m p s v c 方法。后两种方 法经过大量实验证明，是一种更有效、更健壮的不确定数据分类方法。 ( 2 ) 扩展的贝叶斯分类法 贝叶斯定理是一种把类的先验知识和从数据中收集的新证据相结合的统计原理，它 主要解决分类中属性集和类标号之间的关系不确定的问题。贝叶斯定理之所以能在分类 问题中发挥重要的作用，是因为它的类条件概率可以同先验概率以及证据共同表示后验 概率。对传统的确定数据分类的贝叶斯方法有两种：朴素贝叶斯分类法和贝叶斯信念网 络。 贝叶斯分类法广泛应用于生物信息领域。2 0 0 6 年d e m i c h e l i s 等人在研究肿瘤组织 基因及蛋白质的变异性分类研究时，针对重复或不均匀取样经常造成数据集的不确定， 改进了传统的贝叶斯分类器，提出了一种分层的贝叶斯分类器1 3 1 1 。新算法建立在贝叶斯 分层模型b h m ( b a y e s i a nh i e r a r c h i c a lm o d e l ) 基础上，该模型通过具体化合适的条件独 立结构和条件概率分布的集合，对样本概率分布提供一种简单的表示。实验证明，当各 个类的样本不均匀性不同时，分层贝叶斯分类法要比标准贝叶斯方法更有效。 1 2 3 频繁项集挖掘 不确定数据的频繁项集挖掘的一种思路是在传统a p r i o r i 算法上进行改进。c h u i 等 人【3 2 】提出了期望支持度计数来取代传统项集的支持度计数，并对传统的a 研嘶算法进 行改进的u a p r i o r i 算法。后者基本上效仿前者，所以在大数据集处理上效果不好。 此外，他们通过实验证明：在不确定数据集上，以低概率值出现的项的数量越多， u a p r i o r i 算法则越显无效。为了解决这一问题，文章提出了一种数据修整技术( d a t a t r i m m i n g ) ，基本思想是对原始数据集采用l g s t r i m m i n g ( 1 0 c a lt r i m m i n g ，g l o b a lp r u n i n g a n d s i n g l e p a s sp a t c hu p ) 技术修剪掉那些低概率出现的项，在此基础上应用u a p f i o f i 算法。由于修整后的数据集将比原始数据小很多，这意味着包含的事务集也少了很多， 故测试候选集的子集和计算支持度计数的速度会更快。大量的实验结果表明：应用 l g s - t r i m m i n g 技术的u a p r i o r i 算法无论在节省c p u 开销还是i o 开销上都取得了很大 的进步。 但是，l g s - i x i t a m i n g 技术在以下几方面存在不足。首先，修剪后的数据集虽然规模 缩小，但是包含的信息也是不完整的，在此上提取的频繁项集势必也不完整。虽然后期 大连理工大学硕士学位论文 的修补流程会覆盖上丢失的信息，但如果原始数据集中低概率项集数量很少，则修剪后 得到的数据集规模和原始数据集差别不大，那么l g s t r i m m i n g 技术效果不明显。也就 是说l g s t r i m m i n g 技术对低概率出现的项集的数量很敏感。其次，论文 3 2 】中算法依赖 人为给定的修整阈值( t r i m m i n gt h r e s h o l d ) 。当数据集中项集的存在概率满足二项式分 布，即多数项集以非常高的概率出现或非常低的概率出现，是两种极端的情况，而概率 适中的项集很少出现，此时选择修整阈值很容易。但是当存在概率更加趋向平稳适中时， 就很难选择一个合适的修整阈值了。 针对上述缺点，c h u i 等人【3 3 j 在2 0 0 8 年又提出了对不确定数据频繁项集挖掘的交替 递减剪枝技术d p ( d e c r e m e n t a lp r u n i n g ) ，它是对文章 3 2 】中方法的改进。对非频繁的候 选集x ，文章 3 2 】的方法要在遍历整个数据集后才能剪枝掉x ，而d p 技术对每个非空 x cx 给出一个递减计数的上界，用此维持每次事务被处理后x 的期望支持度计数的 递减变化，直至上界减到小于给定的支持度阈值，便可进行相应的剪枝。为了提高有效 性，还对d p 算法进一步改进，。提出了单例整合方法a s ( a g g r e g a t eb ys i n g l e t o n s ) 和公 共前缀方法c p ( c o m m o n p r e f i x ) 降低递减计数的数目。 不确定数据的频繁项集挖掘的另一种思路是拓展基于频繁模式树f p t r e e ( f r e q u e n t p a a e mt r e e ) 的方法。该方法无需生成候选集，只需测试支持度计数。l e u n g 等人【3 4 】提 出了针对不确定数据的u f g r o w t h 算法，它包括两个步骤：u f t r e e 的构建和在构建好 的u f t r e e 上进行频繁项集挖掘。构建u f t r e e 过程与f p - t r e e 步骤基本相同，每个树结 点除了存储项名称之外还要存储项的期望支持度以及同一项在不同事务中以相同期望 支持度出现的次数。在构建的u f t r e e 上采用自底向上方式的u f g r o w t h 算法。它采用 分支限晃策略将一个问题分解为多个小问题，对于每个结点，计算它的期望支持度计 数，通过与频繁阈值比较，从而发现以某个特定后缀结尾的所有频繁项集。在传统的确 定数据集上，f p g r o w t h 算法比标准的a p r i o r 算法要快几个数量级，对于不确定数据， u f g r o w t h 算法效率也要比u a p r i o d 算法效率高。特别的，当数据集中项集以低概率出 现的比例增大时，u a p r i o d 算法的时间开销增长非常快。 由于存储了数据的出现概率，u f t r e e 比f p t r e e 需要更大的存取内存。为了降低内 存消耗，l e u n g 等人1 3 5 j 在u f g r o w t h 算法又提出了两种改进策略：期望支持度值取整法 和只对单例模式的映射数据集建立u f - t r e e 的方法。 除此之外，在证据数据库领域，不确定数据的频繁项集挖掘研究也受到了关注。证 据数据库要求对存储的数据，使用证据理论对数据进行建模，即在每个属性上用基本信 念分配( b a s i cb e l i e f a s s i g n m e n t ) 来描述其不确定性。h e w a w a s a m 等人【3 6 】在2 0 0 5 年提 出了b i t 方法( b e l i e f i t e m s e tt r e e ) 。b a c ht o b j i 等人p7 j 在2 0 0 8 年又提出了一种新的数 不确定数据聚类研究 据结构r i d l i s t s ( r e c o r di d e n t i f i e rl i s t s ) ，它加速了项集的支持度计数，是一种证据数据 库的垂直描述。随后他们又对b i t 方法进行了改进，提出了f i m 方法【3 引，这种方法在 b i t 方法扫描的结果集上计算最大频繁项集m f 和它的子集( 根据 2 6 】中的支持度的反 单调性，若项集频繁，则其子集也是频繁的) ，在此基础上得出最终结果集f ，并可以 快速计算f 集中的可行子集，这大大提高了原算法的效率。 1 2 4 孤立点检测 目前，对孤立点检测的研究已经广泛存在于机器学习、统计学、信息论和数据挖掘 等诸多领域，具体可参看2 0 0 9 年的一篇综述【39 1 。孤立点检测方法主要分类为： ( 1 ) 基于模型的技术：首先要对数据建立模型，如果一个对象不能很好的同该模 型拟合，则它是一个孤立点。举例来说，若模型是通过估计概率分布建立的，则孤立点 是不服从此分布的对象；若模型是簇的集合，则孤立点是不明显属于任何簇集的对象。 ( 2 ) 基于相似性的技术：用数据对象间的相似性度量( 多是基于距离的) 来检测 那些远离大部分其他数据的对象。 ( 3 ) 基于密度的技术：对数据对象进行密度估计，低密度区域中的对象相对远离 近邻，可能被看作孤立点。 相对传统的确定数据来说，不确定数据的孤立点检测难度更大。由于数据对象会因 其不确定性而被当作孤立点来处理，如此不仅掩盖了真正的孤立点，还可能扭曲整体的 数据分布。 a g g a r w a l 等人在2 0 0 8 年提出了一种基于密度的孤立点检测方法，他在文章 4 0 】中 指出，当数据对象具有多维属性时，即使数据对象本身并不是孤立点，但是它的属性的 不确定级别却直接影响到它是否会被视作孤立点。也就是说，属性的不确定性越高，则 数据对象越容易被视为孤立点。另外他还指出，在高维空间识别孤立点具有很大的难度。 这是因为高维数据集一般是潜在稀疏的，每对数据点彼此是近似等距的【5 5 1 ，这样的数据 点很难被聚类，那么每一个数据看起来都像孤立点。多数情况下，只能对高维数据的子 空间进行检查，找到密度异常低的数据区域，从中检测出孤立点，所以算法的思想也是 基于遍历子空间和密度估计的。 算法定义了r 1 概率来量化一个不确定数据对象在一个密集区域出现的概率，n 值 表示对象出现在这一区域的概率最小值，它通过取样点进行计算，r l 值越小表明数据对 象越有可能出现在疏松的区域。在多个子空间内进行搜索，当r 1 概率小于给定的密度 阈值6 时，则称这个对象是( 6 ，n ) 孤立点。同时，文章还提出了基m i c r o c l u s t e r i n g 的 加速技术，进一步提高了算法的效率。 大连理工大学硕+ 学位论文 1 3 本文内容及组织结构 本论文通过对现有不确定数据聚类算法进行分析，提出了一种新的基于近似骨架的 不确定数据聚类算法a b a u d c 。同时，通过在u c i 知识学习库中的四个经典数据集上 进行算法对比实验，证明了新算法结合近似骨架后，在不同数据集上的聚类精度都优于 经典的不确定数据聚类u k m e a n s 算法。 第一章绪论。介绍本文的研究范围和相关背景知识，对数据不确定性产生的原因 和表现形式进行概述，同时，指出了目前对不确定数据挖掘工作的进展及成果。 第二章聚类分析。此章是本论文新算法提出的理论基础，介绍了聚类定义、目标 函数，传统的面向确定数据的聚类算法分类以及聚类在现实生活中的研究价值等。除此 之外，单独用一节列举了目前存在的的面向不确定数据的聚类算法，不仅介绍每个算法 的思想和流程，而且指出了算法的优缺点，为下一章新算法的提出提供了依据。 第三章不确定数据聚类的新算法。首先指出新算法提出的动机和原因，分析了近 似骨架与聚类问题结合的理论依据；其次对算法的核心模块、基本思想以及算法的聚类 质量评估方法等进行了详尽的介绍。： 第四章实验。为u c i 知识学习库中的四个经典数据集进行扰动，构造了相应的不 确定数据集，并使用新算法对每个数据集进行聚类，对新算法进行验证。同时，为了对 比新算法聚类效果优劣，采用了u k m e a n s 算法作为对比。实验验证了基于近似骨架的 聚类算法提高了聚类精度。 第五章结论。对论文进行了总结和回顾，同时对不确定数据挖掘未来工作进行了 展望，指出了针对不确定数据研究的新方向。 不确定数据聚类研究 2 聚类分析 2 1聚类概述 2 1 1数学描述 聚类分析是一种无监督学习，它把有限的无标签的数据集划分为多个“相似的”簇 集，而“相似性”体现了数据本质的类别属性。参照文献 4 1 】，我们给出如下聚类的数 学形式描述。 定义：给对数据集x = x l ，x n ) ，其中x j = x j l ，x j d 1 e r d 且x j i 代表数据的特征( 属 性、维度、变量等) 。 ( 1 ) 刚性聚类描述：对于给定数据集，寻找他的k 个划分，使得c = c i ，c k ( k 耋n ) ，并满足c ；a ，i = l9 * - 9 k ；c ；nc j 一，j = l ，k 且i j ； ( 2 ) 层次聚类描述：对于给定数据集，构造树型结构h = h i ，h k ( k 耋n ) ，使得 c ie h m ，c j h h ( m h ) ，对于所有i ，j i ，m , h = l ，q 满足c je c i 或者c jf - ) c i 2 。 在上述定义中，可知每个数据对象只能属于一个类，但对与模糊聚类分析，数据通 过判定隶属度可以划分到多个类中。 2 1 2 聚类过程 对聚类问题的研究已经有几十年的历史，人们不断对聚类过程、模式以及方法进行 研究，目前对于聚类过程的认识已经达到了共识。无论采用何种算饭，对于何种数据集 的聚类过程可归结为以下五个阶段，具体参见图2 1 所示。 图2 1 聚类过程 f i g 2 1c l u s t e r i n gp r o c e s s 大连理工大学硕十学位论文 ( 1 ) 数据预处理：一般包括数据清洗、特征标准化和降维。 ( 2 ) 特征选择：从最初的特征中选择最有效的特征，可以有效避免噪声点的影响。 ( 3 ) 特征提取：通过对所选择的特征进行转换形成新的突出特征。 ( 4 ) 聚类：选择合适特征类型的距离函数或相似性度量方式，通过算法把每个对 象划分到所属类中。 ( 5 ) 聚类结果评估：常通过外部有效性评估、内部有效性评估和相关性测试评估 等测试聚类结果的优劣。 2 2 聚类分析的研究意义 聚类分析在诸如数据统计、模式识别、图像处理、信息检索、医学诊断等与人类生 活息息相关的领域具有广泛的应用背景，发挥了显著作用【4 。例如： ( 1 ) 在市场分析领域，聚类分析可以帮助决策者更好的划分客户群以及分析同一 客户群的特征，从而提供更有针对性的服务和更加准确高效的策略定位。 ( 2 ) 在信息检索领域，聚类分析可以对w e b 文本进行划分，从而提高信息检索效 率。目前，人们较熟悉的g o o g l e 、百度等搜索引擎的核心技术都是源于聚类分析技术的。 ( 3 ) 在生物医学研究领域，聚类分析能够对不同疾病的特征表现进行分析、归类， 便于医生快速地诊断病情。同样的，也可以利用聚类来分析基因中的属性特征进而对动 植物进行分类。 ( 4 ) 在空间数据库领域，聚类分析可以识别具有相同地理特征的区域以及区域中 人和环境的特征。这在军事观察和能源探测方面发挥了显著的作用。 2 3 传统聚类分析算法 传统聚类分析指的是处理的数据对象为确定数据，即每一个数据对象都是单一的数 据点。对他们的研究工作已经进展了几十年，所以根据不同的应用背景产生出的聚类分 析算法也是数不胜数的。 了解聚类算法的分类不但有助于理解本论文的研究范围，同时利于理解不确定数据 挖掘算法产生的基础。文献 4 2 】 4 3 】是从不同角度提出的聚类算法的综述，值得说明的， 聚类算法并不是相互独立的，为了更好的提高算法效率和精度，一些算法常常继承其他 算法的思想。 本文对聚类算法的分类如表2 1 所示： 不确定数据聚类研究 表2 1 常用聚类算法分类 t a b 2 1t h ec a t e g o r yo fc l u s t e r i n ga l g o r i t h m s 聚类算法种类 典型算法 基于划分的聚类算法 基于层次的聚类算法 基于密度的聚类算法 基于网格的聚类算法 其他聚类法 k m e a n s ，k m e d o i d s ，k - c e n t e r , c l a r a n s ，e t c b r l c h ，c u r e ，r o c k ，d l a n a ，m o n a ，e t c d b s c a n ，o p t i c s ，g m d d ，d e n c l u e ，e t c d 1 g ，c l i c kh c s ，c a s t ，e t c w a v e c l u s t e r , l v q ，s o f m ，a r t ，s a r t ，e t c 2 3 1 划分方法 划分法的基本思想是把数据集中的数据对象平滑分割成k 个簇( k 为初始给定值) ， 使得每个数据对象唯一存在于一个簇中，同一簇中的数据具有相同的属性，不同簇中的 对象属性差异较大。 算法必须满足以下两个条件，即：每个簇至少包含一个对象；每个对象必须属于且 只属于某一个簇。分割的过程就是一次聚类，每个簇就是一个类，算法迭代往返，直到 类中对象不再发生变化而收敛。 在不确定数据聚类算法中，很多算法都是通过改进标准k m e f l d _ s 算法得到的，了解 它的基本定义和算法过程是我们探究不确定数据聚类的前提和基础。 k m e a i r l s 算法和k m e d o i d s 算法是典型的基于划分思想的聚类算法，同时也是最常 用的聚类方法。它们都是已知类的个数k ，并将数据集中的对象划分到k 个类中，聚类 结果由k 个类中心表示。不同的是，前者的中心点是每个簇中对象的平均值，而后者的 中心点是每次迭代后，距离旧的类中心最近的点。 k m e f l $ 1 s 算法的提出意义重大，但是他却存在很多缺点，如只适合数值属性的数据 聚类、易产生局部最优、对初始k 具有依赖性等等。 2 3 2 层次方法 该方法使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂或聚合， 以形成一个层次序列的聚类问题解。凝聚的方法也称自底向上的方法，一开始将每个对 象作为单独的一个组，然后相继地合并相近的对象和组，直到所有的组合并为一个或者 达到一个终止条件。分裂的方法，也称是自项向下的方法，一开始将所有的对象置于一 个组中。每迭代一步，一个簇被分裂为更小的簇，直到最终每个对象在单独的一组簇中 大连理工大学硕士学位论文 或者达到一个终止条件。图2 2 形象的表示了对图中左侧的数据集经过层次聚类后生成 的系统树图。 l 一2 3 4 一s + t6 7 j8 + ；9 v 图2 2 样本集和其相应系统树状图 f i g 2 2 ad e n d r o g r a mf o ras a m p l ed a t a s e t 图右侧的系统树状图中，每个叶子节点代表一个数据点，根结点代表整个数据集， 每个中间点和包含在下的叶子节点表示一个簇集，而树状图中的每个层次表示一次聚类 过程。自顶向下层次聚类方法和自底向上的层次聚类方法分别可以看做对树状图由上到 下的分裂和由下向上的凝聚。 层次方法的最大缺陷在于，某一步分裂或合并一旦完成，就不能更改。这就会导致 错误的分裂或合并无法更正， 有可能严重影响聚类的结果。 2 。3 。3 基于密度的方法 基于密度的方法采用的也是划分法的基本思想，但是由于它可以跳出基本划分方法 在发现非球状聚类上的缺陷，具有更广泛的研究意义，所以学者们常常将它作为单独的 聚类方法分类。基于密度聚类算法多用于时空信息处理、消除奇异值、发现各种形状的 类簇，对噪声不敏感，适合大型、高维数据集等方面具有好的特性。 常用的基于密度聚类思想包括两方面： ( 1 ) 基于密度连接方法 首先，我们对这种方法的概念定义给出介绍： 不确定数据聚类研究 邻域：对于数据点x ，在以为半径形成的邻域内，满足所有的点y 到x 的距 离都小于( 为算法输入参数) 。 核对象：某数据对象x 的邻域内包含的数据点超过m i n p t s 时，x 称作核对像 ( m i n p t s 为算法输入参数) 。 密度可达：每次迭代过程中，若数据对象y 和x 之间存在一系列的和对象集，则 说y 到x 是密度可达的。 密度连接：存在一个核对像，对于数据对象x 和y 都是密度密度可达的，则称x 和y 是密度连接的。 其次，算法核心思想是如果临近区域的给定密度函数值超过了某个阐值，就继续合 并周围的点，即是用密度低的点分割高密度区域。 常用的算法包括基于高密度连接区域的d b s c a n 算法；对数据对象排序进行聚类 的o p t i c s 算法以及能够综合使用非空间值、空间值和时态值实现聚类的d b c l a s d 算 法。 ( 2 ) 基于空问密度分布函数方法。 引入空间密度函数算法主要是h i r m e b u r g ，k e i m 等提出的利用空间密度分布函数的 d e n c l u e 算法。该方法的优点是能够发现任意形状的聚类，并且有效处理孤立点数据。 2 3 4 其他方法 ( 1 ) 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚 类操作都在这个网格结构( 即量化的空间) 上进行。s t i n g 是基于网格方法的一个典 型例子。 目前存在很多算法都是将网格与密度相结合的，常见算法如下：网格密度等值线聚 类算法g d i l c 用密度等值线图描述样本分布，具有消除奇异值和发现各种形状类簇的 能力：基于密度和网格的聚类算法s g c 是一种非参数类型的算法，计算时间与数据集 规模无关，适于任意形状类簇；网格聚类算法g c h l 能够发现任意形状类簇和奇异， 对噪声数据不敏感，4 聚类快速，聚类时间独立于数据规模和数据次序，伸缩性极好，适合 大型、高维数据集；基于密度自适应聚类方法t f c t m o 结合时态信息和空间信息，时 间聚焦能够提高移动对象轨迹聚类质量 4 4 1 。 ( 2 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法，其基本思想视：为每个聚类假设一个模型，再去发现符合模型的 数据对象，寻找给定数据与某个数学模型的最佳拟合。一个基于模型的方法可能通过构 大连理工大学硕士学位论文 建反映数据点空间分布的密度函数来定位聚类，也可能基于标准的统计数字自动决定聚 类的数目，进一步对考虑噪声点和孤立点的影响。 m o o r e 提出的m r k d - t r e e 算法就是一种基于模型的聚类方法，它通过构造一个树型 结构来