（计算机软件与理论专业论文）基于粗糙集的聚类算法研究.pdf

摘要 随着数据库技术的飞速发展以及数据库管理系统的广泛应用，人们所拥有的 数据急剧增加，可是目前用于对这些数据进行分析处理的工具却很少。人们希望 根据现有的数据预测未来的发展趋势。数据挖掘技术应运而生，它是目前数据库 和信息决策领域最前沿的研究方向之一。粗糙集理论是波兰数学家z p a w l a k 在 1 9 8 2 年提出的一种处理模糊和不确定信息的数学工具，其主要思想是在保持分 类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。粗糙集理论 常与规则归纳、分类和聚类方法结合使用。 本文首先介绍了数据挖掘和粗糙集理论的基本概念、发展及应用，分析了粗 糙集理论与数据挖掘方法的特点，并对粗糙集理论在数据挖掘中的应用进行了综 合的分析。通过对粗糙集理论与聚类算法的分析，提出将粗糙集理论中的上、下 近似概念引入到利用分层的平衡迭代归约及聚类算法中，分析在多阈值方法下数 据对象同时属于多个簇的情况下数据对象的归属问题。对已有类似算法做出相应 改进，比较实验结果证明改进算法具有较高的精度。 离群点挖掘是数据挖掘中的一个重要研究内容。在分析比较了目前常用的多 种离群点查找方法之后，针对近年来在许多应用领域出现的称为数据流的新型数 据形式，提出了一种基于k 均值聚类和凝聚聚类的离群点查找方法，并进行了 实验分析。实验结果说明算法是有效可行的。 关键词：数据挖掘；粗糙集；聚类：离群点 a b s t r a c t w i mm c d e v e l o p m e n to f 蛐嬲et e d m o l o g y 锄d l ew i d e l yu s eo fd a 组b 弱e m a n 卿e n ts y s t e l t bp e o p l en e e dt om a n a g ew i mm o 他锄dm o r ed a t 乱h o w e v c u 【r r 饥t l yv e r yf e wt o o l sc 锄b cl l s e df o rt l l e 加a l y s i so f t l l e s ed a 衄s om 锄yp p l e w 趾tt 0p 问i c tt l i e 缸t u r e 慨do f 懿i s t i n gd a t ab ya d v 锄c e d 锄a l y s i s t h 嘴，批 m i l l i n gw 雒p r o p o s e d d a t am i i l i n gi sn 0 v d 趾da c t i v e 锄di so 舱o ft l l ei n o s tf 0 刑a r d l m 懿o fd a t a b 弱e 锄di n f o m a t i o nd e c i s i o n 础渤f c h t h er o u g l ls c tt l l c 0 恤c hw 嬲 i n 仰d u c e db yp a w l a l 【z i i i1 9 8 2 ，i sa 墩觚t i d 0 lt 0d e a lw i lv a g u 饥e 鼹a n d m c e 慨n t y w i lm u g l ls e tt l l e 0 d c c i s i o no rc l 雒s m c 撕0 nm l 鹪c 觚b ed c d u c 。d d u r i n gt 1 1 ep r o c e 豁o fk n o w l e d g er e d u c t i o i l w i md 舔s i 矽a _ b i l i t y1 1 0 td e c r e 舔e d r o u g h tt l l 。0 r y 盯eo r 锄u s e d 、) i r i n lm l ei n d u 嘶。玛d 嬲s i f i c a t i o n 锄dc l u s 衄i n g t t l i s p a p l e rf i r s t l yi l l 蛐c 贸 l eb 嬲i cc o n c 印t sa n di l l l p r 0 懈n e n t sa n d 印p l i c a t i o i l so fd a t am i i l i n g 锄dr o u g hs e tm r 弘a n d t l l er o u g hs e tb 弱e dd a t ai i l i i l i n g m e 廿1 0 d s a r e rd r a wc o m p 撕s o 舾o fr o u 曲s e t s 锄dc l u s t 嘶n ga l g o r i l m s ，i tp r e s t sa v e lm 甜l ( ) dt 0 b m c h ，b yi n n 砸u d n g l ec o n c e p to fu p p 盯 锄dl o w 盯 a p p r o x i m a t i o ni n t 0 圮b i r c h 1 1 l i sm e 廿l o d 锄a 1 ) r s 懿觚a n 矗b u t i o np r o b l 锄o f d a t a o b j e c t s ，、7 l ，h 饥 d a t ao b j e c t s s i m u l t a j l c 0 邯l yb e l o n g t 0 m u l t i p l e c l u s t e r s t h e e x p 甜m e i l t a lr e s u l t ss h o wt l l a tm ei n l p r o v c db i r c hh 鹤a a c u r a c yi m 】p 】r 0 v e d o u t l i e rm i i l i n gi s 觚i m p o r t 觚tr e s e 鲫c ho fd a t am i n i n g a r e r 肌a l y s i s 狃d c o m p 撕s o no fc 0 删 1 1 0 i l l yu s e dm 龇o fo u t l i e 体，i tm a l ( e s 觚o u t l i 盯d e t e c t i o n m e m o db a s e do nk m e a n sa n da g 酉o m c r a t i v ec l u s t 甜n gf o rd a t as 仃e 锄t h er e s u l to f t l l ee x p e r i m e n ts h o w sm a tt h i sa l g o r i t l l mi sf e 硒i b l e 锄de f l & t i v e k e yw o r d s ：d a t ai i l i n i n g ；r o u g hs e tt h e o r y ；c l u s t e 血g ；o u t u e r s 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名：叼段 日期2 0 0 9 年多月细 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：叼段 导师签名：逻可 日期：2 0 0 9 年月乡日 日期：2 0 0 9 年b 夥日 第一章绪论 在信息技术高速发展的今天，数据库技术也飞速发展，人类获取数据手段的 多样化使得人类所拥有的数据量急剧增加。但是已有的数据库系统仅仅是对数据 进行存取和简单的操作。人们通过这些简单操作只能对这些数据进行浅显地分 析，通过其只能获得整个数据库所包含信息量的很少很少一部分。然而，关于这 些数据的整体特征的描述及对其发展趋势的预测才是更重要的信息，才是人们迫 切想知道的有用的信息。但是它往往隐藏在数据的背后，不容易被人察觉。数据 挖掘【1 5 】( d a t am i m n gd m ) 是一门新兴的数据库技术，它是近几年来随着数据库 和人工智能的发展而发展起来的，它的目的是为了从大量的日常业务数据中抽取 出有价值的信息或知识。数据挖掘是目前数据库和信息决策领域最前沿的研究方 向之一。数据挖掘指的就是从海量数据中发现隐藏的有用的知识，为了这个目的 它可以利用各种自动化工具以及成熟算法。数据挖掘提取的知识可以表示为概 念、规律、规则、模式、可视化等。数据挖掘是学科交叉发展产生的一门新兴学 科。 2 0 世纪8 0 年代初，波兰华沙理工大学z p 删l a l 【教授提出了粗糙集【6 j 理论， 它是一种研究不完整、不确定知识和数据的表达、学习、归纳的方法。粗糙集理 论自问世以来，无论是在理论领域或是应用领域都有着迅猛的发展势头，已经成 为含糊性问题研究的重要研究方法。特别是在机器学习、决策分析、知识获取、 数据挖掘与模式识别等方面的应用，粗糙集理论都为其提供了一种有效的数学方 法。本文通过对粗糙集理论与聚类算法的分析，提出将粗糙集理论中的上、下近 似概念引入到利用分层的平衡迭代归约及聚类算法中。分析在多阈值方法下数据 对象同时属于多个簇的情况下数据对象的归属问题，提高聚类算法的精度。 1 1 研究背景和意义 当今世界数据库技术迅猛发展，人们所积累的数据不断增加。人们希望能够 对这些激增的数据进行更高层次的分析和研究，发现隐藏在它们背后令人感兴趣 的信息。虽然目前的数据库系统可以高效地实现数据的录入、查询、统计等功能， 但是它无法发现各种数据中存在的不易察觉的关系和规则，无法依据现有的数据 来预测事件的未来发展趋势，从而导致了“数据丰富但知识贫乏 的这一现象的 出现。由此，数据挖掘技术应运而生，并显示其强大的生命力。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别 有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程。近年，数据挖 掘和人工智能被国际权威机构g a 咖e rg m u p 列为“未来三到五年内将对工业产 生深远影响的五大关键技术的首位，与此同时，未来五年内投资焦点的十大新 兴技术的前两位分别为并行处理体系和数据挖掘列【6 】。数据挖掘对于信息的挖掘 和知识的发现是不需要明确假设的，这正是新兴的数据挖掘技术与传统的数据分 析之间的本质区别。数据挖掘所得到的信息是指那些预先不曾预料到的信息，也 就是说数据挖掘是要发现那些不能简单靠直觉发现的信息或知识。某些出乎意料 的信息可能具有更高的价值。因此，能自动分析数据、提取隐藏知识并将其表示 为人们所能理解的模式的数据挖掘算法是很有用的。数据挖掘的出现为自动和智 能地从海量数据中提取有用的知识提供了强而有力的手段。 粗糙集理论在数据挖掘领域中发挥着举足轻重的作用。粗糙集理论是一种处 理模糊和不确定信息的数学工具。粗糙集是由集合的上近似、下近似来定义的。 下近似中的每一个成员都是该集合的确定成员，若成员不属于上近似中则其肯定 不是该集合的成员。粗糙集的上近似包括下近似和边界区域。边界区域的成员有 可能是该集合的成员，但不是该集合的确定成员。 在知识工程研究中，存在信息的含糊性问题。术语的模糊性( 如高矮胖瘦) 、 数据的不确定性( 如噪声引起的) 以及知识自身的不确定性( 如提取的规则的前 后间的依赖关系是不完全可靠的) ，这是含糊性的三种表现形式。然而，人工智 能中的经典逻辑不足以解决这些不确定性问题。为此，人们提出了包括模糊集理 论、统计方法等在内的一些解决方法，但是这些方法都有一定的限定范围或缺陷， 都只能在一定的程度上解决含糊性问题。例如，统计的方法在理论上仍然难以令 人信服，模糊集方法存在怎样准确合理的确定成员隶属度这个本质问题。与之相 比，粗糙集方法则有不少的优点：不需要预先知道额外的信息( 如统计方法中的 先验概率以及模糊集要求的隶属度等) 、算法简单并且易于操作。粗糙集分析方 法仅仅利用数据自身提供的信息，不需要任何先验知识。粗糙集方法能表达和处 理不完备信息；粗糙集方法能在保留关键信息的前提下对数据进行化简并求得知 识的最小表达：粗糙集方法能识别、评估数据之间的依赖关系并揭示出他们之间 概念简单的模式；粗糙集方法能从经验数据中获取易证实的规则知识。目前，多 理论技术的结合是数据挖掘的一个研究热点，本论文研究基于粗糙集理论的数据 挖掘算法。 1 2 国内外研究现状 k d d 这个术语首次出现在第1 1 届国际人工智能联合会议上，它是1 9 8 9 年 2 8 月在美国底特律召开的。随着l d 专题讨论会的频繁举办以及与会人员的不 断增多，l d 国际会议逐步发展成年会。为集中讨论数据统计、海量数据分析 算法、知识表示和知识运用等问题提供了有利的平台。每年的关于数据挖掘的学 术会议不仅有许多学者踊跃参与，不少软件公司也相继展出了他们的数据挖掘软 件产品。 数据挖掘技术涉及的方法有很多。可以根据不同的性质对其进行划分。如： 根据挖掘任务，可以分为分类或预测模型发现、数据聚类、关联规则发现、数据 总结、序列模式发现等；根据挖掘对象，有关系数据库、空间数据库、面向对象 数据库、文本数据源、时态数据库、多媒体数据库、遗产数据库、异质数据库， 以及环球网w 曲等的数据挖掘；根据挖掘方法，可大致分为统计方法、机器学 习方法、数据库方法和神经网络方法等。 许多学者在上述数据挖掘的各个领域都取得了较好的研究成果，各大公司也 相继将数据挖掘技术应用到各自的产品中【悼 】。近年来，我国研究者们对数据挖 掘的研究也在升温。在国家的资金支持下，许多研究机构也相继投入到数据挖掘 的研究中来，并取得了一定的研究成果。但是，相对于国际上的发展，还是存在 比较大的差距，特别是我国的数据挖掘软件产品大部分还处于实验室阶段。随着 我国市场经济的不断发展，数据挖掘技术的市场潜力将是巨大。贸易的市场化与 全球一体化使得简单的价格竞争和规模竞争不再是市场竞争的主体，管理和决策 层面的竞争将在市场竞争中发挥决定性的作用，而数据挖掘技术正是一种提高管 理和决策水平的手段。 粗糙集理论的旺盛生命力在于它具有强大的实用性。粗糙集理论从诞生到现 在虽然仅有2 0 多年的时间，但它已经在许多领域中取得了令人鼓舞的好成绩。 近年来，粗糙集理论地地位不断上升，受到了国际上越来越多的学者的关注，使 得粗糙集理论的国际学术会议已经发展成为年会【1 8 - 2 2 】，并且成立了粗糙集理论的 国际学术团体。特别是2 0 0 3 年在重庆召开的第9 届国际粗糙集会议和第3 届中 国粗糙集会议，对我国粗糙集理论的研究与应用起了巨大的推动作用。 聚类是数据挖掘中一个活跃的研究领域。聚类的目的是使属于同一类别的个 体之间的相似程度尽可能的大，不同类别的个体之间的相似程度尽可能的小。从 机器学习的角度看，聚类和分类是不同的。聚类不依赖事先定义好的类和带类标 号的训练实例，属于无指导学习。聚类是知识发现的重要方法，在图像识别、信 息检索、客户关系管理、基因分析等领域有着广泛的应用。 近年来，聚类的研究主要集中在寻找适合大型数据库的有效和实际的聚类分 析方法，对下面这些问题仍有待进一步研究： ( 1 ) 算法的可伸缩性。 ( 2 ) 处理不同类型数据的能力。 ( 3 ) 发现任意形状的聚类。 ( 4 ) 用于决定输入参数的领域知识最小化。 ( 5 ) 处理噪声数据的能力。 ( 6 ) 结果对输入顺序的无关性。 ( 7 ) 处理高维数据的能力。 ( 8 ) 基于约束的聚类。 ( 9 ) 结果的可解释性和可用性。 近年来，不少学者对于利用粗糙集理论来改善聚类效果方面做了许多的研 究。文献 2 6 根据变精度粗糙集理论提出了一种新的聚类算法；文献 2 7 基于粗 糙集的相容关系，利用概念聚类和粗糙集理论相结合实现了金融数据分析方法， 并结合可变精度粗糙集提出了动态聚类算法；文献 2 8 利用基于粗糙集聚类方法 实现了数据的约简；文献 2 9 有效结合了粗糙集和c o b w e b ，提出了新的聚类 算法c r s c ，在不降低准确性的前提下，较之传统聚类算法提高了效率；文献 3 0 利用粗糙集相似关系，通过计算每个数据点的熵来选取聚类中心，并把所有数据 点聚集成数字颗粒结构；文献 3 1 提出了一种新的基于粗糙集相似模型的加权聚 类方法以及基于信息论的类提纯方法，利用信息熵值对各个属性进行加权重复聚 类，最终得到满足聚类要求的模式类，但这种方法时间和空间复杂度都比较高， 且不能同时处理符号属性和数值属性；刘少辉【3 2 】等在聚类结果的综合近似精度 等定义基础上提出了一种基于粗糙集的层次聚类算法，该算法能够自动调整参 数，以寻求更优的聚类结果。总的来说，基于粗糙集理论的数据挖掘算法研究是 一个较新的，很有研究价值的课题，正越来越被研究者们重视。 1 3 主要研究内容 聚类是一种重要的数据挖掘技术，也是数据挖掘研究的重点和热点之一。聚 类技术的研究有着广泛的应用基础。本文主要在两个方面对数据挖掘算法进行了 研究： ( 1 ) 通过对粗糙集理论与聚类算法的分析，本文提出将粗糙集理论中的上、 下近似概念概念引入到利用分层的平衡迭代归约及聚类算法中，分析在多阈值方 法下数据对象同时属于多个簇的情况下数据对象的归属问题，在一定程度上提高 算法的精度。 ( 2 ) 针对近年来在许多应用领域出现的称为数据流的新型数据形式，提出 了基于k 均值聚类和凝聚聚类的离群点查找方法。 4 1 4 论文的组成结构 第一章是绪论，介绍了本文的研究意义和背景，并对国内外在基于粗糙集理 论的聚类算法方面的研究发展现状进行了分析，最后对本文的主要研究内容进行 了介绍。 第二章介绍数据挖掘的 些基本概念、方法和应用。首先回顾了数据挖掘的 发展历程，介绍了数据挖掘可以发现的各种知识和数据挖掘的过程，并就数据挖 掘在今后一段时间内的研究方向和面临的挑战进行了探讨。然后对聚类以及聚类 的方法和用途进行了简单的介绍。最后对粗糙集理论进行了简单的介绍，包括粗 糙集理论的发展与特点，粗糙集理论的基本概念，以及粗糙集在数据挖掘中已有 的应用。 第三章对基于粗糙集理论的b i r c h 算法进行了研究。首先介绍了基于距离 的分层聚类法，分析了b i r c h 算法以及多阈值b i r c h 算法。然后基于粗糙集 理论的上、下近似概念，给出了新的聚类质点的计算公式，提出了基于粗糙集理 论的多阈值b i r c h 新算法。 第四章是对离群点的研究。首先对现有的典型的离群点查找算法进行了介绍 和分析，然后就近年来在许多应用领域出现的称为数据流的新型数据形式，提出 了基于k - 均值聚类和凝聚聚类的离群点查找方法。 第五章结论与展望。总结了本文的研究工作，提出进一步研究方向。 5 第二章预备知识 2 1 数据挖掘的发展 2 1 1 数据挖掘发展概述 原始数据被人们看作是形成知识的源泉。就像从矿石中采矿一样，数据挖掘 就是一个利用各种分析工具在原始数据中发现数据之间相互关系的过程。数据挖 掘技术不仅是对数据的简单的检索、查询、调用，而且还包括对这些数据在微观 或宏观方面的统计、分析、综合和推理，得出有价值的结论来指导实际问题的求 解。更甚者，希望利用已有的数据对未来可能的活动进行大胆预测。 数据库技术的掘起是从2 0 世纪6 0 年代开始的，这时基本的文件处理系统已 不能满足用户的需要，因此基本的文件处理系统逐步发展成为功能更加强大的数 据库系统；2 0 世纪7 0 年代，关系数据库系统的出现，数据建模工具的增多，索 引与数据组织技术迅速发展，使数据库系统的研究与发展出现了极具代表性的里 程碑。关系数据库技术在联机事务处理( o l ) 出现后有了极大地推广及应用， 特别是在大数据量存储、检索和管理领域取得了良好的实际应用效果。 2 0 世纪8 0 年代中期，许多先进的数据模型和应用数据库系统被相继提出， 关系数据库技术已经被用户普遍采用，尤其是异构数据库系统和基于互联网的全 球信息系统的飞速发展，导致了数据的快速增长，使得数据量的存储到了惊人的 地步。这些庞大的数据远远超过了人类自身的理解、分析、处理能力。海量数据 与知识之间的巨大差异使得数据挖掘技术应运而生。 2 1 2 数据挖掘的挑战与未来研究方向 近年，数据挖掘的研究取得了令人瞩目的进展，同时，数据挖掘所面临的挑 战也摆在了研究者面前，具体有以下几个方面： 1 、处理不同种类的数据。应用领域的增多使得不同种类的数据频繁出现， 因而，期望能够对不同种类的数据进行有效地挖掘。 2 、数据挖掘算法的效率和扩展性。海量数据的出现使数据挖掘的工作量猛 增，为了有效地抽取信息，数据挖掘算法必须是高效的并且是可扩展的。 6 3 、数据挖掘结果的可用性和确定性。由数据挖掘所发现的知识必须要精确 地描绘数据库的内容并且挖掘出的知识对已经确定的应用是有用的。 4 、数据挖掘方法应适应多种数据类型、能够克服数据丢失和数据噪声。计 算机网络的不断发展，使分布的、异构的多类型数据库也成为数据挖掘的对象。 数据被干扰情况也越来越严重，如何克服这些丢失的数据和噪声数据的干扰也是 数据挖掘所面临的难点。 5 、从各种不同的数据源中挖掘信息。海量的不均匀的数据库的出现，使得 从不同的格式化或非格式化并有不同语义的数据中挖掘出有用的知识成为数据 挖掘新的挑战。 6 、数据安全及隐私保护。由于数据能从不同角度和不同抽象层查看，因此 严重地威胁了保护数据安全以及禁止侵犯个人隐私的目标。知识发现何时会导致 侵犯隐私、需要开发何种安全措施柬保护敏感信息，都是非常重要的研究课题。 另外，多抽象层交互挖掘知识和数据挖掘结果的可理解性也是数据挖掘面临 的重要问题。 当前，数据挖掘和知识发现研究方兴未艾，研究焦点有可能会集中到以下几 个方面： l 、智能的、有效的、可扩充的数据挖掘方法的研究； 2 、知识发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言 也许会像s q l 语言一样走向标准化； 3 、寻求数据挖掘过程中的可视化方法，使数据挖掘的过程能够被用户理解， 便于在知识发现的过程中进行人机交互： 4 、网络环境下的数据挖掘技术； 5 、各种非结构化数据的挖掘，如对文本数据、视频图像数据、声音数据乃 至综合多媒体数据的挖掘。 2 2 数据挖掘的任务和过程 2 2 1 数据挖掘的任务 对数据库中的数据进行抽取、转换、分析和模型化处理，并从中提取出能进 行辅助决策的关键数据和隐藏在其中的预测性信息是数据挖掘的主要任务。数据 挖掘能找出可能被人们忽略的信息，发现数据之间存在的潜在关系与模式。通过 数据挖掘，人们可以了解到基于知识的决策分析意见和结论。数据挖掘有如下的 四种基本任务： 汇总( s u m m 撕z a t i o n ) ：对数据进行浓缩，给出它的紧凑描述。数据挖掘主要 7 是从数据泛化的角度来讨论数据总结。 分类( c l 船s i f i c a t i o n ) ：分类主要是为了学会一个分类函数或分类模型( 也称作 分类器) 。分类模型是指按照事先定义的标准，把数据库中的的各数据项映射到 已知类别中的某一个。 聚类( c l l l s t 嘶n g ) ：聚类是按照相似性程度的不同把一组个体归纳成若干类 别。分类属于有教师监督的学习方法，分类学习并获取预测模型所使用的数据是 已知类别归属的数据，而聚类分析则属于无教师监督的学习方法。这就是聚类和 分类的较为明显的不同之处。 关联规则( a s c i a t i o nr m e ) ：用来发现一组项目之间的关联关系和相关关系 的规则叫关联规则。形如彳j 】，的关联规则可以解释为：满足x 的数据也可能 会满足y 。关联可分三类：简单关联、因果关联和时序关联。 2 2 2 数据挖掘的过程 一个数据挖掘系统是一个完整的整体而不是多项技术的简单组合，数据挖掘 系统还需要各种辅助技术的支持，才能完成数据采集、预处理、数据分析、结果 表达这一系列的任务，最终将分析所得的结果呈现在用户面前。数据挖掘从大型 数据库中挖掘先前未知的，有效的，可实用的信息的过程，这些挖掘出的信息可 以为做出决策提供条件或丰富知识。 数据挖掘的过程可分为五部分：问题定义、数据收集和预处理、数据挖掘、 算法执行以及结果的解释和评估。数据挖掘的基本过程如图2 1 所示。 豳豳- 崮囱 图2 1 数据挖掘基本过程图 l 、问题定义 数据挖掘是为了在大量数据中发现令人感兴趣的有用信息，因此发现哪一种 知识成为整个数据挖掘过程中第一个最重要的阶段。在此期间，工作人员必须和 领域专家、最终用户充分协作，明确实际应用工作对数据挖掘的要求，进而分析 比较各种数据挖掘算法，找出适合此次实际工作的可用的挖掘算法。 2 、数据收集和数据预处理 数据准备分为数据选取、数据预处理、和数据变换三个子步骤。数据选取是 为了确定任务的最终操作对象。数据预处理包括消除噪声、缺失值与重复记录处 理、数据类型转换等。数据变换是为了给数据降维，也就是从最初的特征中找出 真正有用的特征，从而减少需要考虑的特征变量的个数。 3 、数据挖掘 数据挖掘执行阶段首先是明确挖掘的任务或目的，确定了任务后，接下来便 是决定使用什么样的算法来进行挖掘。挖掘算法的选择有两个需要考虑的因素： 不同的数据具有不同的特点，所以挖掘时需要用符合其数据特点的算法；考 虑用户的要求和实际运行时系统的要求，每个用户所希望获取的知识类型是不同 的，有的希望获取的知识是容易理解的，有的可能只是希望获取的知识预测准确 度尽可能高的。 4 、结果解释和评估 数据挖掘阶段发现出来的模式并不全部都是可用的，经过评估，需要剔除那 些冗余和无关的模式。还有一种结果是发现的模式不是用户所要求的，这时则需 要整个发现过程退回到前一阶段。此外，知识发现最终是面向人类用户的，这就 要求对发现的模式进行可视化处理，把数据挖掘的结结果转换为用户能够看得懂 的表示形式。 数据挖掘过程是一个不断反馈重复的过程。比如，在挖掘过程中发现选择的 数据不理想，挖掘的结果不是所期望的，此时，用户需要重复先前已经做过的步 骤，必要时甚至从头重新开始。 2 3 聚类概述 聚类就是将物理或抽象对象的集合构成为由类似的对象组成的多个类或簇 的过程。 聚类的思想并不复杂，聚类是以距离原则为准绳，当数据对象具有m 个属 性是，就把这个数据对象看作是m 维空间的一个点，根据事先定义好的m 维空 间的的距离计算方法，将数据对象根据距离的不同划分成不同的类别。 聚类无论是在商业上、生物学中，还是在其它领域用途都是非常广泛的。聚 类可以帮助市场分析人员区分不同的消费群体，并且概括出每一类消费者的消费 模式；聚类可以用来分类具有相似功能的基因，可以用来辅助研究动、植物的分 类，还可以用来发现人群中的一些潜在结构等；此外，聚类可以用来从地理数据 库中识别出具有相似土地用途的区域：聚类可以从保险公司的数据库中发现汽车 保险中具有较高索赔概率的群体；聚类还可以用来从1 1 1 t e n l e t 上分类不同类型的 文档。与此同时，聚类分析作为数据挖掘的一个模块，它可以作为一个单独的数 据挖掘工具用来发现数据之间的些深层次的信息：聚类分析也可以作为数据挖 9 掘算法中其他分析方法的一个预处理步骤。 基于机器学习的聚类技术主要包括划分方法、层次方法、基于密度的方法、 基于网格的方法和基于模型的方法。 基于划分的方法，给定一个有个元组或者记录的数据集合，构造k 个分 组，每一个分组代表一个聚类，mk 个分组满足以下两个条件：每一个分组 至少包含一个记录；每一个记录属于且仅属于一个分组。代表算法有：c i a ra 算法【3 3 1 、k m e a n s 算法、k - m e d o i d s 算法、c i ，a r a n s 算法【3 4 1 。 基于层次的方法，层次的分解给定的数据集，直到满足某种条件为止。代表 算法：a g n e s 算法、b i r c h 算法【3 5 1 、d l 州a 算法、c u r e 算法【3 6 1 、c h a m e l e o n 算法等。 基于密度的方法，当某个区域中的点的密度大于某个阈值，就把他加到与之 相近的聚类中去。基于密度的方法能克服基于距离的算法只能发现“类圆形聚 类的缺点。其代表算法有：d b s c a n 算法【3 7 1 、d e n c l u e 算法、o p t i c s 算法【3 8 】。 基于网格的方法，将数据空间划分成为有限个单元的网格结构，所有的处理 都是以单个单元为对象。基于网格方法的一个突出优点就是速度很快，它只与单 元格的个数有关，与目标数据库中的记录个数无关。s t i n g 算法【3 9 】是基于网格 方法的一个典型例子，c l i q u e 算法【4 0 】和w a v e c l u s t e r 算法既是基于网格 的，又是基于密度的。 基于模型的方法，给每一个聚类假定一个模型，然后去寻找能够很好的满足 这个模型的数据集。它的一个潜在的假定就是，目标数据集是由一系列的概率分 布所决定的。代表算法有：c o b w e b 算法( 统计学方法) 、s o m 算法( 神经网 络方法) 。 2 4 粗糙集理论概述 2 4 1 粗糙集理论的发展 数据是各种信息的载体，是对客观事物的数量、属性、位置以及它们之间的 相互关系的形式表示。经典逻辑中，只有真假二值之分，但是自然界中大多数事 物所呈现的信息都是不完整或含糊的，因此经典逻辑无法对含糊问题进行准确的 描述。美国控制论专家z a d e h 在1 9 6 5 年提出了f u z z y 集，不少逻辑学家和计算 机科学家试图通过这一新理论来解决含糊问题，但由于f u z z y 集中对于含糊概念 的描述并没有用数学公式来表示，无法计算出含糊元素数目。 波兰数学家z p a w l k a 根据g f r g 的边界线区域思想，在1 9 8 2 年提出了粗 糙集理论。与此同时，论文r o u g hs e t s 的发表，宣告了粗糙集理论的诞生【i 引。 l o 2 0 世纪9 0 年代前后，由于粗糙集理论在不同研究领域的成功应用，慢慢吸引了 世界各国学者的目光。1 9 9 1 年，粗糙集一关于数据推理的理论这一著作的 问世，标志着关于粗糙集的研究进入了活跃期。从9 0 年代开始，我国开始了对 粗糙集理论的的研究。为了促进粗糙集理论在中国的快速发展，中国计算机协会 人工智能与模式识别专业委员会于2 0 0 1 年5 月在重庆召开了第l 届中国粗糙集 理论与软计算学术研讨会。目前，粗糙集理论及其应用已成为信息科学最活跃的 研究领域之一。 2 4 2 粗糙集理论的特点 粗糙集理论是关于不精确知识的一种数学理论。粗糙集在处理不精确信息方 面的优势在于它不仅能够表达客观事实，同时也具有这种由客观事实推导出模糊 事实的能力。 作为研究知识发现的行之有效的工具的粗糙集理论具有以下几个优点： l 、粗糙集不需要先验知识。粗糙集分析方法仅用数据本身提供的信息，也 就是说，利用粗糙集来分析问题只和已知的数据有关，无须已知数据外的任何先 验知识，从而避免了主观因素对分析结果的影响。 2 、粗糙集是一个强大的数据分析工具。粗糙集能处理不完备信息，粗糙集 能在保留关键信息的前提下对数据进行化简，粗糙集能揭示出概念简单的模式； 粗糙集能从经验数据中获取易于证实的规则知识。 3 、粗糙集以不可分辨关系为基础，侧重分类。粗糙集和证据理论、模糊集 有一些相互交叠之处，在实际应用中可以互相补充。 2 5 粗糙集理论的基础知识 粗糙集理论认为知识是人类对对象进行分类的能力。粗糙集理论在不可分辨 关系基础上，引入上近似和下近似等概念来刻画知识的模糊性和不确定性，引入 约简和求核来进行知识的化简等计算【1 3 】。 2 5 1 知识表达系统 对某些客观对象的认知称为知识。用符号来对知识进行表示是为了能有效地 处理智能数据。知识表达系统所研究的对象是由指定对象的基本特征和特征值来 表述的。 数据挖掘中，知识表达是重要的，不可缺少的。知识表达系统在形式上是以 四元组s = ，彳，y ，厂) 的形式来表达的，其中： u ：称之为论域，表示关于对象的非空有限集合； a ：代表属性的非空有限集合； y = u 圪，圪是属性口的值域； 口e 一 厂：u 彳专y 表示一个信息函数，这个信息函数为论域中存在的每个对象的 每一个不同属性赋予信息值，即v 口彳，工c 【，厂( x ，口) 圪。 信息系统是知识表达系统的另一种称呼。因此s = ( u ，彳，y ，厂) 可以简化为 s = ( 【，彳) 。关系表在知识表达系统中是非常重要的。在知识表达系统中，关系 表是数据对象的形式表示方法。研究对象与该研究对象对应的属性分别由关系表 中的行和列来表示，关系表中行列交叉中的各属性值则用来表示研究对象所代表 的信息。 信息系统也称为属性值系统，其表达方式与关系数据库模型类似，粗糙 集理论中的有关约简和核的一些概念都是在这种表达方式的基础上来定义的。使 用这表达方式，数据对象就可以用来代替知识，为了寻找发现各种有实用价值的 知识，对数据对象的各种不同的操作都可以看作是用来实现知识处理的手段。 信息系统中有一个特殊的系统决策表。在决策表中，条件属性用来描述 数据对象的特征，具体该数据对象应该分为哪一类则由决策属性来表示。决策属 性可能表示各种不同的分类、需要采取的行动或决策，决策属性是由专家提出的， 但决策属性的提出必须是以条件属性所描述的情形为基础。决策属性不能脱离条 件属性而单独存在。所以说决策表在规则发现中有举足轻重的地位。 定义2 1 【1 3 】：决策系统( 有时称决策表) 是一个有序二元组，= ( 【，c u d ) ， 这里u 是一个对象的非空有限集合，称为论域；c 和d 分别为条件属性集和决 策属性集。 表2 1 表示一个决策表的例子，在表中，行代表所需研究的数据对象，即 “= x ，屯，毛，屯) ，列带表这些数据对象的对应属性值，即彳= h ，4 ，4 ，d ) ， 其中4 ，4 ，4 i 表示条件属性，d 表示决策属性。 表2 1 一个决策表的例子 u 44 4 d 工ol2o 而 l2o2 毛 l0lo 2lol 毛 1lo2 1 2 通常，在机器学习中，决策表被用来作为学习分类的映射。这个分类是根据 条件属性的不同描述而产生的，分类结果，即对象具体分到哪一类是由决策属性 确定的，映射则表示为所得决策规则的集合。 2 5 2 不可分辩关系 定义2 2 【1 3 】：在信息系统s = ( u ，彳) 中，对于bs 彳，则b 在u 上的不可分辨 关系定义为： 肋( b ) = ( 五，毛) u u 1 6 ( 西) = 6 ( 屯) ，v 6 曰) = n 肋( 6 ) 挺口 这里，不可分辨关系也是一种属性关系， 彳s = 这个二元组构成一 个近似空间。对于任意属性集b 彳，【，上的不可分辨关系上d ) 也是一种等 价关系。 定义2 3 【1 3 】：对于对象戈u ，b 彳，x 关于b 的等价类定义为 【z 】占= y u i ( 五y ) 肋( 曰) ) 上一公式表示所有与x 具有不可分辨关系的对象组成的集合，这一等价类是由对 象工决定的。 定义2 4 【1 3 l ：等价关系z d ( b ) 把u 划分为七个互不相关的等价类，称其为关 于召的基本集，记作u j 凇( 口) = 五，t ) ，这个公式表示关系z ( b ) 在【，上 的所有等价类的集合，即等价族，简记为u 曰。 2 5 3 集合的上、下近似 定义2 5 【1 3 】：给定知识表达系统k = ( 【，尺) 和u 的分类u r ，对于每个子集 x u ，下面这两个集合分别被称为x 的尺下近似和r 上近似。 下近似：鲋= u 缸u ：【j 】眉x ) ，即，当且仅当【j 】霄x ，x 心。 上近似：肘= u 扛u ：【x 】rn x 妒) ，即，当且仅当【x 】露n x ，z 见y 。 肘是关于知识尺，u 中所有由知识尺确定的一定属于x 的元素的集合： 肘是关于知识尺，u 中所有由知识尺确定的可能属于x 的元素的集合。 了解了上面的尺下近似和r 上近似的定义，我们来介绍下有关于正域、负域 和边界域的定义。 定义2 6 【1 3 】： 我们把集合尸0 ( x ) = 鲋称为x 的r 正域；把 舵g 。( x ) = u 一心称为x 的尺负域；把肼。( x ) = 肘一鲋称为的边界域。 2 6 基于粗糙集理论的数据挖掘方法研究现状 最近几年，通过研究者们的努力奋斗，对于粗糙集理论的应用与研究取得了 长足发展。这里从几个方面简单介绍一下与之相关的应用。 2 6 1 粗糙集模型拓展方面的研究 为了解决粗糙集进行数据分析时所遇到的数据噪声、数据不完备和连续数据 的离散化等问题，研究者们对粗糙集模型进行了拓展提出了可变精度模型、相似 模型和连续属性离散化模型。下面简要介绍下这三种模型。 l 、变精度模型。经典粗糙集中一直存在数据的过拟合问题。当数据集存在 各种干扰情况时，正是这种过度拟合会降低对新对象的预测能力。可变精度粗糙 集模型的抗干扰能力强于经典粗糙集模型。这正是由于可变精度粗糙集模型通过 定义一个精度，允许该模型存在一定的误分类率，从而使得可变精度粗糙集模型 具有不错的容错性。 2 、相似模型。相似模型与经典粗糙集模型最主要的区别在于相似类不再形 成对原集合的划分。这是由于在相似模型中相似关系替代了粗糙集中的不可分辨 关系。正是这种替代使得相似模型在实践应用中的性能比经典粗糙集模型的效果 更好。 3 、连续属性离散化模型。在实际的应用中，经常会遇到连续属性值的问题， 然而经典租糙集模型只能处理非连续的、离散型的属性。这时，就需要一种新的 模型能够对连续属性进行离散化。连续属性的离散化模型的提出，使得粗糙集对 离散的和连续的两种属性都能进行有效的处理，扩大了粗糙集模型的应用范围。 2 6 2 基于粗糙集理论的高效算法的研究 基于粗糙集理论的高效算法的研究，除一些基本的算法外，目前主要集中在 以下的四个方面。 1 、导出规则的增量式算法。粗糙集的基本算法的数据对象是固定不变的数 据集。这使得算法对于那些数据对象不断增加的数据集具有更高的复杂度。当新 数据增加到相应数据集时，算法必须从头重新计算全部数据集( 原有+ 新增) 才 能导出规则。然而增量式算法不需要对全部数据集重新进行计算，只需对新增数 据进行处理，进而对原有的规则进行修正，以此得到的规则就是关于新数据集的 规则。 2 、简约的启发式算法。寻找数据的所有的简约是一个n p 完全问题。这使 得我们只能用一种合适的方法来找出最优或次优的简约，启发式的方法很快的浮 1 4 现在脑海中。将属性重要性作为启发式信息，这是启发式算法用于约简的显著特 点，只是不同的启发式简约算法有着不同的属性重要性的量度。 3 、粗糙集基本运算的并行算法。粗糙集的很多基本运算都可以并行执行， 这是由粗糙集的基本性质决定的。并行计算在处理海量数据时是非常重要的。最 初研究粗糙集的目的就是将粗糙集做为一种数学工具用来处理海量数据，因此， 粗糙集的并行计算性质就显得尤为重要。 一 4 、大数据集中的粗糙集计算实现。在算法复杂度方面，粗糙集原本就有较 高的计算复杂度，有些研究者受到关联规则挖掘算法的启发提出将关联规则的挖 掘技巧适当的应用于粗糙集的确定的和可能的规则生成中，以降低粗糙集在数据 挖掘中的计算复杂度。 2 6 3 粗糙集与其它智能分析方法的融合 与各种智能理论取长补短、互相结合相类似，粗糙集理论同样也可以与概念 格、遗传算法、神经网络、模糊集理论和证据理论等其它智能理论相结合，使结 合算法具有更强更优的功能，以适应不同的应用目的。 1 、粗糙集与概念格。海量数据是在实际应用中所面临的和需要处理的，正 是由于数据量的过大使得直接利用概念格提取规则有过大的冗余度。根据粗糙集 中的上、下近似概念，概念格可以模仿粗糙集的上、下近似概念生成“上近似格 和“下近似格。这样就可以通过处理原来概念格到这些近似格的映射来降低冗 余度。 2 、粗糙集与遗传算法。遗传算法可以用来对粗糙集中的连续属性进行离散 化处理：遗传算法与粗糙集的简约计算相结合，可以为快速搜索决策系统的简约 提供一份力量。此外，用粗糙集来改进遗传算法，在提高交互式遗传算法的收敛 性和降低进化代数等方面有较好的表现。 3 、粗糙集与神经网络。粗糙集和神经网络的较好互补性体现在不确定性计 算方面。利用粗糙集来优化神经网络有两个方面，一是利用粗糙集构造网络规模 更小的神经网络，以便提高训练速度；二是利用粗糙集来简化神经网络的学习样 本。粗糙集和神经网络的结合还能应用于分类，可以取得较好的分类结果。 4 、粗糙集与模糊集理论。粗糙集与模糊集理论分别刻画了不完备信息的两 个方面：粗糙集侧重分类，主要研究不同类中的对象组成的集合之间的关系；模 糊集则强调集合自身的模糊性，主要研究同一类中的对象对集合的隶属关系。粗 糙集和模糊集组合可以得到“粗糙一模糊集合”和“模糊一粗糙集合”。 5 、粗糙集与证据理论。粗糙集和证据理论的相似性主要表现在相容性观点 下，在d s 理论的概率分配观点下，它们是完全不同的。粗糙集不需要除数据 本身之外的任何先验信息，而d s 理论则需要对基本概率分布进行假设分析。 所以，就互补性而言，粗糙集与d s 理论的互补性程度很高。 6 、粗糙集与其它理论。目前b a y 镪理论、概率统计理论、专家系统和p e t r i 网等都与粗糙集相关。另外，粗糙集与多种智能方法的融合，取彼之长，补己之 短。 2 7 本章小结 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中， 提取隐含的、先前未知的并有潜在价值的信息的非平凡的过程。 粗糙集理论从集合论的观点出发，以观察和测