（计算机应用技术专业论文）基于粗糙集理论的聚类研究.pdf

摘要 数据挖掘技术是机器学习、数据库和统计理论相结合的产物，是从大量的、 不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含的、先前未知的并 有潜在价值的信息的非平凡过程。在数据挖掘领域中，聚类分析是一项重要的研 究课题。与分类不同，聚类的目标是在没有任何先验知识的前提下，根据数据的 相似性将数据聚合成不同的簇，使得相同簇中的元素尽可能相似，不同簇中的元 素差别尽可能大，因此又被称为非监督分类。聚类分析作为数据挖掘系统中的一 个模块，既可以作为一个单独的工具以发现数据库中数据分布的深层信息，也可 以作为其他数据挖掘分析算法的一个预处理步骤，因此研究如何提高聚类算法的 性能具有重要的意义。 粗糙集理论是一种刻画不确定性和不完整性知识的数学工具，由波兰数学家 p a w l a k 在上世纪八十年代初首先提出的。粗糙集理论善于分析隐藏在数据中的事 实而不需要关于数据的任何附加知识。该理论以其独特的优势正赢得越来越多的 研究者的关注，并在各个领域获得了广泛的应用。在数据挖掘领域，粗糙集最初 主要用于分类，丽今有关粗糙集的研究已深入到该领域的各个方面。 本文首先介绍了数据挖掘的定义和主要方法，重点对聚类分析技术的各种算 法作了详细的介绍和比较，并提出了一种改进的层次聚类算法；本文仔细学习了 粗糙集理论，提出了一种基于代数运算的属性约简方法，针对粗糙集理论善于处 理不精确和不确定性知识的特点，将粗糙集理论引入聚类分析中，对传统聚类方 法作了相应的改进，然后通过实验验证了这种改进有效性；本文最后分析了粒度 和聚类的关系，在粒度框架下研究了粗糙集理论在聚类中的应用，并提出了一种 基于粒度原理的聚类算法，然后对u c i 数据库中两个数据集进行了实验，结果表 明与没有引入粒度概念的传统聚类算法相比，该基于粒度原理的聚类算法明显提 高了对数据点的分类正确率，验证了在粒度框架下将粗糙集理论用于聚类可以有 效的提高聚类质量。 关键词：数据挖掘，聚类，粗糙集，属性约简，粒度。 a b s t r a c t t h ed a t am i n i n gt e c l m i q u ei sac o m b i n a t i o no fm a c h i n el e a r n i n g ，d a t a b a s ea n d s t a t i s t i c a lt h e o r y d a t am i n i n gc a l ls e e ki n t e r e s t i n go rv a l u a b l ei n f o r m a t i o n 谢t h i nl a r g e , i n c o m p l e t e ，n o i s y , r o u g h ，a n dr a n d o md a t a b a s e s c l u s t e ra n a l y s i s i sa ni m p o r t a n t r e s e a r c hp r o b l e mi nt h ed o m a i no fd a t am i n i n g t h eg o a lo fc l u s t e r i n gi st oc l a s s i f y d a t as e ti n t os n c hc l u s t e r st h a ti n t r a - e l u s t e rd a t aa r es i m i l a ra n di m e t - c l u s t e rd a t aa r e d i s s i m i l a rw i t h o ma n yp r i o rk n o w l e d g e ，w h i c hi sv e r yd i f f e r e n tf r o md a t ac l a s s i f i c a t i o n s oc l u s t e r i n gi sa l s ok n o w na s ”u n s u p e r v i s e dc l a s s i f i c a t i o n ”c l u e s t e ra n a l y s i sa sa m o d u l ei nt h es y s t e mo fd a t am i n i n gc a nb eu s e dn o to n l ya sas e p a r a t et e c h n i q u et o d i s c o v e rt h ei n f o r m a t i o na b o u td a t ad i s t r i b u t i o n ，b u ta l s oa st h ep r e p r o c e s s i n go fo t h e r d a t am i n i n go p e r a t i o n s ，t h e r e f o r ei ti sv e r ym e a n i n g f u lt or e s e a r c hh o wt oi m p r o v et h e p e r f o r m a n c eo f c l u s t e r i n ga l g o r i t h m s r o u g hs e tt h e o r y ( r s t 、i sam a t h e m a t i c a lt o o lu s e df o rd e a l i n gw i t hv a g u e n e s s a n du n c e r t a i n t yw h i c hi si n t r o d u c e db yp a w l a k i nt h ee a r l y1 9 8 0 s r o u g hs e tt h e o r yi s g o o da ta n a l y z i n gt h ef a c t sh i d d e ni nt h ed a t aw i t h o u ta n ya d d i t i o n a lk n o w l e d g ea b o u t t h ed a t a d u et oi t sp a r t i c u l a ra d v a n t a g e s ，r o u g hs e tt h e o r yh a sb e e nr e c e i v e dm o r ea n d m o r ca t t e n t i o n sf r o mr e s e a r c h e r sa n da p p l i e di nav a r i e t yo fa r e a si nr c c e n ty e a r s i n t h ed o m a i no f d a t am i n i n g ，r o u g hs e tw a so n l yu s e df o rc l a s s i f i c a t i o na tt h eb e g i n n i n g , b u tt h er e s e a r c ha b o u tr o u g hs e th a sa l r e a d ye x p a n d e dt oa n ya s p e c t so fd a t am i n i n g t o d a y t h i st h e s i si n t r o d u c e st h ec o n c e p t i o na n dm a i nm e t h o d so fd a t am i n i n ga tf i r s t ， e s p e c i a l l ya n a l y s e sa n dc o m p a r e se v e r yk i n do f c l u s t e r i n ga l g o r i t h m sd e t a i l e d l y , t h e na i m p r o v e dc l u s t e r i n ga l g o r i t h mb a s e do nh i e r a r c h i c a lm e t h o di sg i v e n t h i st h e s i s s t u d i e sr o u g hs e tt h e o r yc a r e f i l l l ya n dd e v e l o p sa l la t t r i b u t er e d u c t i o nm e t h o db a s e do n a l g e b r a i co p e r a t i o n b e c a u s er o u g h s e ti s g o o da td e a l i n gw i t hi n c o m p l e t ea n d u n c e r t a i ni n f o r m a t i o n w ei n t r o d u c ei ti n t oc l u s t e r i n gi no r d e rt oi m p r o v et r a d i t i o n a l c l u s t e r i n gm e t h o d s ，t h e nt h ep o s i t i v ee f f e c to ft h i si m p r o v e da l g o r i t h mi sp r o v e db y i i e x p e r i m e n t t h i st h e s i sa n a l y s e st h er e l a t i o n s h i pb e t w e e ng r a n u l a r i t ya n dc l u s t e r i n ga t l a s t , w h i l et h ea p p l i c a t i o no fr o u g hs e ti nc l u s t e r i n gi sr e s e a r c h e di nt h ef r a m eo f g r a n u l a r i t y ac l u s t e r i n ga l g o r i t h mb a s e d o n g r a n u l a r i t yi sp r e s e n t e d , t h e nt h e e x p e r i m e n ti si m p l e m e n t e do nt w od a t as e t sf r o mu c id a t a b a s e t h er e s u l ts h o w st h a t c o m p a r e dw h i tt h ec l u s t e r i n ga l g o r i t h mw i t h o u tg r a n u l a r i t yc o n c e p t i o n ，t h ec l u s t e r i n g a l g o r i t h mb a s e do ng r a n u l a r i t yh a sm o r ep r e c i s ec l a s s i f y i tp r o v e st h a tw eu s er o u g h s e tt h e o r yi nc l u s t e r i n gi nt h ef r a m eo fg r a n u l a r i t yc a ni m p r o v et h ec l u s t e rq u a l i t y o b v i o u s l y k e yw o r d s ：d a t am i n i n g ，c l u s t e r i n g ，r o u g hs e t ，a t t r i b u t er e d u c t i o n ，g r a n u l a r i t y i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得争i 鞭走孽或其他教育机构 的学位或证书而使用过的材料。与我一同z - 作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 髓，罨磷 签字日期：三，e 7年节月万日 学位论文版权使用授权书 本学位论文作者完全了解孝徽天孝有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权事徽夭幻以将学位论文的全部或部分内容编入有关数据譬进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：访，磊碑 签字日期：z 0 0 7 年带月三厂日 学位论文作者毕业去向： 工作单位： 通讯地址： 导师签名 签字日期 电话 邮编 麴滴、 弘切年月2 7 曰 第一章绪言 1 1 数据挖掘简介 1 1 1 数据挖掘的概念 第一章绪言 数据挖掘，就是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的， 事先未知的潜在的有用的信息，提取的知识表示为概念( c o n c e p t s ) ，规则( r m e s ) ， 规律( r e g u l a r i t i e s ) ，模式( p a t t e r n s ) 等形式【i 】。 数据挖掘的过程就是知识发现的过程，数据挖掘从理论和技术上继承了知识 发现领域的成果，同时又有着独特的内涵，数据挖掘更着眼于设计高效的算法以 达到从巨量数据中发现知识的目的。数据挖掘所能发现的知识有如下几种：广义 型知识，反映同类事物共同性质的知识；特征型知识，反映事物各方面的特征知 识；差异型知识，反映不同事物之间属性差别的知识；关联型知识，反映事物之 间依赖或关联的知识；预测型知识，根据历史的和当前的数据推测未来数据；偏 离型知识，揭示事物偏离常规的异常现象。所有这些知识都可以在不同的概念层 次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不 同层次决策的需要。 数据挖掘是涉及数据库、人工智能、数理统计、机械学、人工神经网络、可 视化、并行计算等的交叉学科，是目前国际上数据库和决策支持领域的最前沿的 研究方向之一【2 j 。 数据挖掘方法的提出，让人们有能力最终认识数据的真正价值，即蕴藏在数 据中的信息和知识。数据挖掘( d a t am i n i n g ) ，指的是从大型数据库或数据仓库中提 取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息，数据挖掘 是目前国际上数据库和信息决策领域的最前沿研究方向之一，引起了学术界和工 业界的广泛关注，一些国际上高级别的工业研究实验室，例如i b ma l m a d e n 和 g t e ，众多的学术单位，例如u cb e r k e l e y ，都在这个领域开展了各种各样的研究 计划【3 1 。研究的主要目标是发展有关的方法论、理论和工具，以支持从大量数据 中提取有用的和让人感兴趣的知识和模式。 与数据挖掘关系密切的研究领域包括机器学习( m a c h i n el e a r n i n g ) 和统计 基于粗糙集理论的聚类研究 ( s t a t i s t i c s ) 。特别是机器学习被认为和数据挖掘的关系最密切。二者的主要区 别在于：数据挖掘的任务是发现可以理解的知识，而机器学习关心的是提高系统 的性能，因此训练神经网络来控制系统是一种机器学习过程，但不是数据挖掘； 数据挖掘的对象是大型数据库，一般来说机器学习处理的数据集要小，因此效率 问题对数据挖掘问题来说是至关重要的。 1 1 2 数据挖掘的一般过程 数据挖掘是指根据对数据的分析，建立对数据的特性以及数据之间关系描述 的模式的过程。在这个描述中，数据是一系列事实的集合( 例如数据库中的实例) ， 而模式是使用某种语言对数据集合一个子集的描述。过程是指挖掘中的步骤。数 据挖掘一般由三个主要阶段组成：数据准备、数据挖掘，以及结果的解释和评估。 知识发现可以描述为这三个阶段的反复过程。图1 1 给出了数据挖掘的整个过程， 这个过程是交互和迭代的，其中许多时候需要用户的参与【4 】。 医主 囱重 在垂了司 l 。1 3 数据挖掘的主要方法 图1 1 数据挖掘的过程 数据挖掘方法有多种，其中比较典型的有汇总分析、分类分析、聚类分析、 关联规则分析等： 汇总( s u m m a r i z a t i o n ) ：其目的是对数据进行浓缩，给出它的紧凑描述。数据 挖掘主要关心从数据泛化的角度来讨论数据总结，数据泛化是种把数据库中的 有关数据从低层次抽象到高层次的过程。 分类( c l a s s i f i c a t i o n ) ：分类是数据挖掘中一项非常重要的任务，其目的是学会 一个分类函数或分类模型( 也称作分类器) 。该模型按照事先定义的标准，把数据 库的数据项映射到给定类别中的某一个，即对数据进行归类。分类的方法有统计 2 第一章绪言 方法、机器学习方法、仿生学方法等。 聚类( c l u s t e r i n g ) ：是把一组个体按照相似性归纳成若干类别，即“物以类聚”。 它的目的是使属于同一类别的个体之间的距离尽可能地小，而不同类 别的个体间的距离尽可能地大。与分类方法的明显不同之处在于，分类所学习获 取分类预测模型所使用的数据是已知类别归属，属于有导师监督的学习方法；而 聚类分析属于无导师监督的学习方法。 关联规则( a s s o c i a t i o nr u l e ) ：关联规则用来发现一组项目之间的关联关系和 相关关系。一条形如x y 的关联规则可以解释为：满足x 的数据项也很可能会 满足y 。关联可分为简单关联( 例如，购买面包的顾客中有9 0 的人同时购买牛奶) 、 时序关联( 例如，若a t & t 股票连续上涨两天且d e c 股票不下跌，则第三天i b m 股票上涨的可能性为7 5 ) 和因果关联，关联性问题是数据挖掘中研究比较成熟的 问题1 5 】。 1 1 4 小结 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检 索查询调用，而是要对这些数据进行微观、中观乃至宏观的统计、分析、综合和 推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数 据对未来的活动进行预测吼这样一来，就把人们对数据的应用，从低层次的末 端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比数据 库查询更为强大。 数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将 会不停地促进它的发展每年都有新的数据挖掘方法和模型问世，人们对它的研 究正日益广泛和深入。 1 2 粗糙集在数据挖掘中的应用 粗糙集理论作为一种全新的数学概念，为处理具有不完整、不一致及不确定性 特征的信息提供了新的有效工具【刀。它由波兰学者p a w l a l ( 在1 9 8 2 年首次提出，1 9 9 1 年，p a w l a k 教授出版了专著，全面系统地阐述了rs 理论引。目前有关粗糙集的研 究日益受到国内外学术界的重视。 基于框糙集理论的聚类研究 目前粗糙集理论己经成为研究不确定性问题的热门研究课题。粗糙集理论主 要是通过合并知识库中相近的知识元素来达到知识约简的目的。粗糙集为分析和 处理不精确、不一致和不完整信息提供了一种有效手段，具有广阔的应用前景【9 1 。 目前，粗糙集理论应用的主要领域有专家系统、机器学习、图像处理、模式识别、 知识的获取以及数据挖掘等。在数据挖掘中引入粗糙集理论可以解决信息不完整、 不精确情况下的挖掘问题，并且能够减小数据挖掘系统的复杂程度，降低系统运 行时问。在数据挖掘领域，粗糙集最初主要用于分类，而今有关粗糙集的研究已深 入到该领域的各个方面【1 0 1 。 1 3 论文的组织结构 本文在对传统聚类算法认真学习的基础上，对聚类的各种主要研究方法进行 了详实的介绍和比较，然后从聚类的效果和质量出发，将租糙集理论引入聚类分析 中，最后通过实验验证了所提出方法的有效性。 第一章是绪言，首先简要介绍了数据挖掘的定义，然后分析了粗糙集在聚类 中的应用情况。最后是论文的组织结构。 第二章对传统聚类分析技术的概念、算法进行了介绍，并比较了各类算法的 优缺点，最后针对传统层次算法的不足之处提出了一种改进算法。 第三章介绍了粗糙集的相关知识，不可分辨关系、上下近似、决策表、属性 约简、相对属性约简等等。 第四章开始介绍了基于可辨识矩阵的基本约简算法，再提出了一种改进的属 性约简算法，用代数运算代替复杂的逻辑运算，提高了计算速度和约简的效率。 然后分析传统聚类算法的两个缺陷：1 、没有考虑各个属性对聚类过程的作用各不 相同，而忽略属性间的差异，认为各个属性权重相等；2 、数据对象被严格的划分 到确定的簇，没有考虑到边界区域的模糊性，与现实世界不符合。本章提出了两 个相应的改进措施，最后通过实验验证了改进算法是有效的。 第五章从粒度的角度研究了粗糙集在聚类中的应用，分析了聚类中的粒度原 理，说明了聚类和粒度是相通的；本章在粒度的框架下将粗糙集理论引入聚类分 析中，举例分析了没有引入粒度概念的传统聚类算法的缺点，提出了一个基于粒 度原理的聚类算法，对数据集中不同部分的数据在不同粒度条件下聚类，以提高 4 第一章绪言 聚类质量。本章最后针对该基于粒度原理的聚类算法进行了实验，实验采用的数 据集为u c i 数据库中的两个数据集，实验结果验证了将粒度概念和粗糙集知识引 入聚类分析方法是非常有效的。 第六章是结论与展望，总结了本文中的研究工作，并展望了今后的任务。r 基于粗糙集理论的聚类研究 第二章聚类分析 2 1 聚类分析的介绍 在日常生活、生产、科研工作中，经常要对被研究对象进行分类。研究和处 理给定对象的分类常用的数学方法是聚类分析( c l u s t e r i n ga n a l y s i s ) 。聚类就是将 数据对象分组成为多个簇，使得同一个簇中的对象之间具有较高的相似性，而不 同簇中的对象具有较大的相异性【l ”。聚类分析是一种重要的人类行为，它的目的 是把相似的东西归为一类，使得类内具有较大的相似性，而类间具有较小的相似 性。聚类分析是多元统计分析的方法之一，它试图根据数据集的内部结构将数据 集分成若干个不同的子类，使得同一予类中的样本尽可能的相似，不同子类的样 本尽可能的不相似。 聚类分析已经广泛地用在许多应用中，包括模式识别、数据分析、图象处理、 以及市场研究。通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分 布模式，以及数据属性之间的有趣的相互关系。与分类不同的是，它要划分的类 是未知的。在分类模式中，对于目标数据库中存在哪些类这一信息、我们是知道 的，在那里我们要做的就是将每一条一记录分别属于哪一类标记出来【。 聚类分析源于许多研究领域包括数据挖掘。统计学、生物学、以及机器学习 等。是在预先不知道目标数据库到底有多少类的情况下，希望将所有的纪录组成 不同的类或者说“聚类”( d u s t e r ) ，使得在同一聚类之间具有较大的相似度，而在不 同聚类之间具有较小的相似度。聚类就是根据描述对象的属性值计算得出的相异 度，将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似 度，而不同簇中的对象差别较大。距离是经常采用的度量相似度的重要方式【l 射。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从他们的消 费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或 者说习惯；在生物学中，它可以被用来辅助研究动、植物的分类，可以用来分类 具有相似功能的基因，还可以又来发现人群中的一些潜在的结构等等：聚类还可 以用来从地理数据库中识别出具有相似土地用途的区域；可以从保险公司的数据 库中发现汽车保险中具有较高索赔概率的群体；还可以从一个城市的房地产信息 6 第二章聚类分析 数据库中，根据房型、房价及地理位置分成不同的类；还可以用来从万维网上分 类不同类型的文档等。同时，聚类分析作为数据挖掘中的一个模块，它既可以作 为一个单独的工具以发现数据库中数据分布的一些深入的信息，并且概括出每一 类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；聚类分析也 可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 2 2 聚类算法面临的挑战 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对分析算法提 出了特别的要求，下面列出一些典型的要求【1 4 】： 1 ) 可伸缩性：这里的可伸缩性是指算法要能够处理大数据量的数据库对象， 比如处理上百万条纪录的数据库。这就要求算法的时间复杂度不能太高，最好当 然是多项式时间的算法。值得注意的是，当算法不能处理大数据量时，用抽样的 方法来弥补也不是一个好主意，因为这通常导致歪曲的结果。 2 ) 处理不同字段类型的能力：即算法不仅要能处理数值性的字段，还要有处 理其它类型字段的能力，例如：布尔型、枚举型、序数型、以及混合型等。 3 ) 发现具有任意形状的聚类的能力：很多聚类分析算法采用基于欧几里德距 离的相似性度量方法，这一类算法发现的聚类通常是一些球状的、大小和密度相 近的类；但可以看见，现实数据库中的聚类可以是任意的形状，甚至是具有分形 维度的形状，故要求算法有发现任意形状的聚类的能力。 4 ) 输入参数对领域知识的弱依赖性：很多聚类算法都要求用户输入一些参数， 例如需要发现的聚类数，结果的支持度、置信度等，聚类分析的结果通常都对这 些参数很敏感，但另一方面，对于高维数据，这些参数又是相当难以确定的。这 样就加重了用户使用这个工具的负担，使得分析的结果很难控制。一个好的聚类 算法应该针对这个问题，给出一个好的解决方法。 ”能够处理异常数据：现实数据库中常常包含有异常数据，或者数据不完整， 缺乏某些字段的值，甚至是包含错误数据的现象，有一些聚类算法可能会对这些 数据很敏感，从而导致错误的分析结果。 6 ) 结果对输入记录顺序的无关性：有些分析算法对纪录的输入顺序是敏感的， 也即，对同一个数据集，将它以不同的顺序输入到分析算法，得到的结果会不同， 7 基于粗糙集理论的聚类研究 这是我们不希望的。 7 ) 处理高维数据的能力：一个数据库或者数据仓库都有很多的字段或者说维， 一些分析算法在处理维数比较少的数据集时表现不错，例如两、三维的数据；人 的理解能力也可以对两、三维数据的聚类分析结果的质量作出较好的判别，但对 于高维数据就没有那么直观了。所以对于高维数据的聚类分析是很具有挑战性的， 特别是考虑到在高维空间中，数据的分布是极其稀疏的，而且形状也可能是极其 不规则的。 8 ) 增加限制条件后的聚类分析能力：现实的应用中总会出现各种其它限制， 我们希望聚类算法可以在考虑这些限制的情况下，仍旧有较好的表现。 9 ) 结果的可解释性和可用性：聚类的结果最终都是要面向用户的，所以结果 应该是容易解释和理解的，并且是可应用的。这就要求聚类算法必须与一定的语 义环境，语义解释相关联。领域知识是如何影响聚类分析算法的设计是很重要的 一个研究方面。 2 3 聚类分析中的数据类型 2 3 1 数据矩阵 数据矩阵是一个对象一属性结构。它是由n 个对象组成，设聚类问题中有n 个对象组成：x i ( i = l ，2 ， n ) ，每个对象有p 个属性，第i 个对象第j 个属性的观测 值为x i j 。数据矩阵采用关系表形式或n x p 矩阵来表示【1 5 1 ( 如图2 1 ) 。 五i而2 。 而口 x 2 1 恐2 而p l 毛2 一 图2 1 数据矩阵 上面的矩阵常称为数据矩阵，其中第i 个对象p 个变量的观测值记为： x i = ( x i l ，x i 2 ，x i p ) 第二章浆类分析 2 3 2 相异度矩阵 相异度矩阵是一个对象一对象结构。它存放所有n 个对象彼此之间所形成的 相似性。它一般采用i i x n 矩阵来表示( 如图2 2 ) 。 o d ( 2 ，1 ) 0 ： ：。 d ( n ，1 ) d ( h ，2 ) 0 图2 2 相异度矩阵 其中d o , j ) - - d o ，i ) 且d ( i ，i ) = o ，a ( i j ) 表示对象i 和对象j 之间的相似性的量化表示， 通常d o , j ) 为一个非负数。当对象i 和对象j 非常相似或彼此“接近”时，该数值接 近0 ；该数值越大，就表示对象i 和对象j 越不相似。数据矩阵经常被称为二模 ( t w o - m o d e ) 矩阵，而相异度矩阵被称为单模( o n e - m o d e ) 矩阵。许多聚类算法以相异 度矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将 其转化为相异度矩阵。 2 3 3 区间标度变量 区间标度变量是一个粗略线性标度的连续度量，典型的例子包括质量和高度， 经度和纬度座标( 如聚类房屋) ，以及大气温度等。采用的测量单位会对聚类分析 产生不同程度的影响，导致不同的聚类结构。一般而言，选用的度量单位越小， 变量可能的值域就越大，这样对聚类结果的影响也越大。为了避免对度量单位选 择的依赖，数据应当标准化。所谓标准化就是给所有属性相同的权值。这一做法 在没有任何先验知识的情况下是非常有用的，但在一些应用中，用户会有意识地 赋予某些属性更大权值以突出其重要性。 为了实现标准化测量，一种方法就是将初始测量值转换为无单位变量。给定 一个属性( 变量) f 可以利用以下计算公式对其进行标准化： 计算绝对偏差均值s f 1 s t = 二( | x l f m f i + x 2 f m 什叫x n f r o d ) 玎 其中x l f ，x 2 f ，x n f 是变量f 的1 1 个测量值。m f 是变量f 的平均值，即 m f = ( x l f + x 2 r 卜+ x i l f ) n 。 9 基于粗糙集理论的聚类研究 计算标准化的测量值，或者z s c o r e ： 一x f m r z i f 。了。 其中绝对偏差均值要比标准偏差更为鲁棒( 对含有噪声数据而言) 。在计算绝 对偏差均值时，对均值的偏差i x l f m d 没有进行平方运算，因此异常数据的作用被 降低；还有一些关于针对分散数据更鲁棒的处理方法，如：中间值绝对偏差方法。 但是利用绝对偏差均值的好处就是：异常数据( o u t l i e r ) 的z 一分值不会变得太小， 从而使得异常数据仍是可识别的。 2 3 4 相似性度量 在标准化处理后，或在无需标准化的特定应用中，对象闻的相似性( 或相似度) 是基于对象间的距离来计算的。最常用的距离度量方法是明氏( m i n k o w s k i ) 距离、 马氏( m a h a l a i l o b i s ) 距离、c o s i n e 距离等。 1 ) 明氏( m i n k o w s k i ) 距离 d o ( q ) = 蓬i x i k 一靠陟9 其中q o ，d , j ( 0 3 为对象i 和对象j 之间的距离，常用于欧氏空间中。 当q 为1 时，明氏距离即为绝对值距离： d e ( q ) = ( 艺k b i ) 当q 为2 时，明氏距离即为欧式( e u c l i d ) 距离： d o ( q ) = ( 妻k 一靠| 2 ) i ，： 2 ) 马氏( m a h a l a n o b i s ) 距离 考虑到对象的各变量的观测值往往为随机值，因此第i 个对象的p 个分量的 观测值x i = ( x i l ，x i 2 ，x i p ) 7 为p 维随机向量。由于随机向量有一定的分布规 律，各分量之间又具有一定的相关性，因此两个对象作为两个随机向量的个体， 则第i 个与第j 个对象间的马氏距离的平方表示为： 第二章聚类分析 d ；( 拟7 ) = ( 薯一x j ) 7 1 ( 鼍- x j ) 其中是随机变量的协方差矩阵。 3 ) c o s i n e 距离 在聚类分析中，每个对象可以看作n 维空间中的向量，第i 个对象可表示为： x i = ( x i l ，x i 2 ，x i ，) t 。它们的相似系数可用两个向量间的夹角余弦来表示，于 是第i 个与第j 个对象的相似系数表示为： 乃= c o s ( 岛) = 2 4 聚类分析中的主要算法及其比较 2 4 1 聚类算法介绍 聚类和分类不同，聚类的输入数据集是一组未标记的对象，即输入的对象还 没有被进行过任何分类。聚类的目的是根据一定的规则，合理地进行分组或聚类， 并用显式或隐式的方法描述不同的类。目前可用的聚类算法很多，算法的选择取 决于数据的类型、聚类的目的和应用。如果聚类的分析被用作描述或探查工具， 可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。基本上，主要的 聚类算法可以划分为如下几类： 1 ) 划分方法( , p a r t i t i o n i n gm e t h o d ) 1 6 】 给定一个含n 个对象或元组的数据库，一个划分方法构建数据的k 个划分， 每个划分表示一个聚簇，并且k 2 5 ) ( 曲计算每个簇的整体相似度s i ( 1 a s i m b ，说明经过动态分裂和合并后 聚类的总体质量得到提高，故保留这次分裂和合并。 捧367c4 1 31 7 7 9叫5 650 c 2 i o l 卜7 3o l 1 i 表2 2 整体相似度 簇c 1 c 2c 3c 4 l 整体相似度 1 5 6o 6 71 02 5 实验采用的数据是在二维坐标中边长为5 0 0 的正方形区域内( 图2 8 ) ，随机 产生1 0 0 0 0 个数据点，对这些数据点分别用传统的层次聚类算法和改进算法进行 聚类。 05 0 0 图2 8 数据取样区域 本实验分两次，每次随机产生1 0 0 0 0 个数据点对改进算法进行验证，结果分 别如表2 3 、表2 4 所示：两次结果均显示，采用改进算法后，平均整体相似度 都比原始算法小，在总体上改进了聚类质量。 基于粗糙集理论的聚类研究 表2 3 第一次实验结果( a s i m 为平均整体相似度) 簇数量 1 2481 6 改进算法的 1 9 1 1 4 1 5 5 2 61 0 3 3 47 3 5 25 2 0 2 a s i m 原始算法的 1 9 1 1 4 1 5 5 2 61 1 8 5 18 5 7 25 8 4 8 a s i m 簇数量12481 6 改进算法的 1 8 5 0 6 1 4 9 8 61 0 2 3 37 0 2 44 9 0 6 a s i m 原始算法的1 8 5 0 61 4 9 8 61 1 9 7 l9 0 1 05 5 4 3 a s i m 2 5 5 结论 本节分析了传统的基于层次聚类算法的不足之处，一旦一个合并或分裂被执 行，就不能修正。提出了一种改进算法，可以和传统聚类算法相结合，在每层分 裂过后，动态地对分裂所产生的新的一层的所有簇进行检查，对聚类效果较差的 簇进行动态分裂和合并，同时并不改变原始算法的执行流程。通过实验验证了与 改进前相比较，改进算法在总体上提高了聚类的质量，可以得到更好的聚类结果。 第三章粗糙集理论 第三章粗糙集理论 本章主要介绍租糙集的基本理论。首先介绍了粗糙集合、知识化简、知识的 依赖性等基本概念，然后介绍了粗糙集在理论与应用方面的研究现状等，接着就 粗糙集相关的有效算法进行探讨。 粗糙集( r o u g h 集) 理论是一种新型的处理不确定性和含糊性知识的数学工 具。它是由波兰科学家z p a w l a k 在上个世纪8 0 年代初对信息系统逻辑特性进行 长期基础性研究并提出的。他们针对从实验中得到的以数据形式表述的不精确、 不相容和不完备问题，进行分类分析伽。 粗糙集理论的一个主要目标是通过背景知识获得目标概念的一个近似，在数 据挖掘和k d d 领域有着广泛的应用。对于数据挖掘，因为操作处理的对象大多 是带有噪音的，并且是不完备的，这使得采用传统的机器学习方法进行发现和描 述存在较大的困难，所以需要使用一些不确定性的方法来处理。其中有很多方法， 比如模糊集，统计学的概率分布，还有就是本章要讨论的粗糙集理论。粗糙集理 论提供了一套严格处理k d d 中最基本的分类问题的数学方法，通过对数据的分 析，生成确定与可能形式的规则。另外，粗糙集合理论包括了知识的一种形式模 型，这种模型可将知识定义为不可区分关系的一个族，使知识具有了一种清晰的 数学意义，并且可使用数学方法来分析处理。这些因素使得粗糙集合理论有助于 k d d 的研究。粗糙集不同于其他不确定性方法的一个重要方面是，它不需要提供 数据表以外的其他任何先验信息 2 s l 。 作为一种新型的处理不确定性知识的工具，粗糙集能有效地处理下列问题： 不确定或不精确知识的表达； 从实例中获取知识； 不一致信息的分析； 根据不确定和不完整的知识进行推理； 在保留信息的前提下进行数据约筒； 近似模式分类； 识别并评估数据之间的依赖关系。 粗糙集理论在数据挖掘中所研究的问题，主要包括属性约简和规则获取， 1 9 基于粗糙集理论的聚类研究 前者可用于对高维数据的降维，而后者可用于获得数据分类的规则。 3 1 粗糙集介绍 粗糙集理论是面向人类认识知识的数学学科，认为知识是人类对对象进行分 类的能力。不可分辨关系是粗糙集理论中的最基本概念。在此基础上，粗糙集理 论引入上近似和下近似等概念来刻画知识的不确定性和模糊性；引入约简和核进 行知识的化简等计算。 分类是推理、学习与决策中的关键问题。粗糙集假定知识是一种对对象进行 分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、 抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各 种分类模式联系在一起，这种特定部分称为所讨论的全域或论域。对于全域及知 识的特性并没有任何特别假设。知识构成某一感兴趣领域中各种分类模式的一个 簇集，这个簇集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事 实的推理能力。通常可用等价关系代替分类。 租糙集认为知识的粒度性造成用己有知识不能精确表示某些概念和造成对象 之间的不可分辨，这就产生了所谓的关于不精确的“边界”思想口6 】。粗糙集合理 论与传统集合理论有着相似之处，但是它们的出发点完全不同。在粗糙集合中， 成员关系不再是一个原始概念，认为不确定性与成员关系有关，模糊性则表现在 集合本身。 下面先给出粗糙集合的基本定义，定义3 1 至定义3 1 3 。 粗糙集中的模糊性，即一个不精确的概念具有模糊的不可被明确划分的边界， 是一种基于边界的概念。为描述这种模糊性，粗糙集采用两个精确集：上近似和 下近似近似地来表示，这使得我们可以精确的描述不精确的概念。 第三章粗糙集理论 3 2 粗糙集理论的基本知识 3 2 1 不可分辨关系 定义3 1 ：在系统s c ( u ，a ) 中，对于b o a ，则b 在u 上的不可分辨关系定 义为： i n d ( b ) = ( x l ，x 2 ) e u u | b ( x 0 = b ( x 2 ) ，v b e b ) = nr n d ( b ) 6 f 在这里，它也是一种属性关系，二元组a s = 构成一个近似空间。对 于任意属性集b o a ，u 上的不可分辨关系i n d ( b ) 也是一种等价关系 2 7 1 。 定义3 2 1 对于对象x e u ，b c _ a ，x 关于b 的等价类定义为： 【x 】b = y e u t ( x ，y ) e i n d ( b ) ) 它表示所有与x 不可分辨的对象所组成的集合，换句话说，是由x 决定的等价类。 定义3 3 - 等价关系i n d ( b ) 把u 划分为k 个不相关的等价类，也称为关于b 的基本集，记u i n d ( b ) - x l 抛，x k ) ，表示关系i n d ( b ) 在u 上的等价类族，简 记为u b 。 3 2 2 集合的上，下近似 定义3 4 ：给定知识库k = ( u ，r ) 和u 的分类u r ，对每个子集x c u ， 把一下两个集合分别称为x 的r 下近似和r 上近似： r x = x e u ：【x l r x ) ，即当且仅当【x 】rc _ x ，x r x ； r x = x u ： x rn x a ) ，即当且仅当 x 】rn x o ，x er x 。 墨x 是利用知识r u 中所有确定地