（计算机应用技术专业论文）基于谓词逻辑和包含集的分类规则约简算法.pdf

中文摘要 分类挖掘是数据挖掘的重要研究内容之一，现有的分类规则挖掘算法所得到的 规则集中存在大量的冗余，严重影响了分类规则的分类效率与可理解性，因此对挖 掘出的冗余分类规则集进行约简，具有重要的理论意义和应用价值。本文采用谓词 逻辑和包含集对分类规则集的后处理进行了研究，其主要研究成果如下： 第一、基于谓词逻辑的分类规则约简r m c r p l 算法。首先，用谓词公式描述分 类规则，把规则集转换成谓词公式的集合；其次，利用谓词逻辑中的逻辑推理，对 规则集进行约简，消除冗余规则；最后，采用恒星光谱数据，实验验证了该方法是 有效的，可行的； 第二、基于包含集的分类规则约简m m i s 与r r p a b i r s 算法。首先利用规则与 数据间的分类关系，提取以单条分类规则为元素的包含集；其次，通过对单个包含 集的处理来实现对分类规则集的精简，给出了m m i s 与r r p a b i r s 算法；最后采用 恒星光谱数据，实验验证了该方法是有效的，可行的。 关键词：数据挖掘；分类规则；谓词逻辑；包含集；冗余规则；恒星光谱数据 a b s t r a c t t h ec l a s s i f i c a t i o nl sa ni m p o r t a n tt a s ki nd a t am i n i n g t h e r ea r eal o to f r e d u n d a n tr u l e si nc l a s s i f i c a t i o nr u l es e tw h i c ha r ee x t r a c t e db yc l a s s i f i c a t i o n r u l e m i n i n gm e t h o d s ， s ot h a t t h e c l a s s i f i c a t i o n e f f i c i e n c y a n d u n d e r s t a n d a b i l i t yo ft h ec l a s s i f i c a t i o nr u l es e ta r ee f f e c t e ds e r i o u s l y s o ，t h e c l a s s i f i c a t i o n r u l es e tr e d u c i n gh a s v e r yi m p o r t a n tt h e o r ym e a n i n ga n d a p p l i c a t i o nv a l u e i nt h i sp a p e r ，t h ep o s t p r o c e s s i n gm e t h o d so fc l a s s i f i c a t i o n r u l es e ta r es t u d i e db yu s i n gt h ep r e d i c a t el o g i ca n dt h ei n c l u d i n gs e t t h e m a i nr e s e a r c hw o r k sa r ea sf o l l o w s ： f i r s t ，ar e d u c i n ga l g o r i t h m ( r m c r p l ) o fc l a s s i f i c a t i o nr u l es e ti s p r e s e n t e db a s e do np r e d i c a t el o g i c f i r s t l y ，t h ec l a s s i f i c a t i o nr u l e s e ti s d e s c r i b e db yu s i n gp r e d i c a t el o g i c ，s ot h a tt h er u l es e ti s c h a n g e di n t o a p r e d i c a t ef o r m u l as e t s e c o n d l y ，t h ec l a s s i f i c a t i o nr u l es e ti sr e d u c e db yu s i n g l o g i cr e a s o n i n gi np r e d i c a t ef o r m u l a ，s ot h a t t h er e d u n d a n tr u l e sa r e e l i m i n a t e d i nt h ee n d ，t h ee x p e r i m e n tr e s u l t sv a l i d a t et h a tt h ea l g o r i t h mi s e f f e c t i v ea n df e a s i b l eb yt a k i n gt h ec e l e s t i a ls p e c t r u md a t a s e c o n d ，r e d u c i n ga l g o r i t h m s ( m m l s a n d r r p a b i r s ) o ft h e c l a s s i f i c a t i o nr u l es e ta r ep r e s e n t e db a s e do nt h ei n c l u d i n gs e t f i r s t l y ，m a k i n g u s eo fc l a s s i f i c a t i o nr e l a t i o nb e t w e e nr u l ea n dd a t a ，t h ei n c l u d i n gs e to fa n y c l a s s i f i c a t i o nr u l ei se x t r a c t e d s e c o n d l y ，m m i sa n dr r p a b i r sr e d u c i n g a l g o r i t h m sa r ep r e s e n t e db yd e a l i n gw i t ht h ei n c l u d i n gs e to n gb yo n e i nt h e e n d ，t h ee x p e r i m e n tr e s u l t sv a l i d a t et h a tt h ea l g o r i t h m si se f f e c t i v ea n d f e a s i b l eb yt a k i n gt h ec e l e s t i a ls p e c t r u md a t a k e yw o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o nr u l e s ；p r e d i c a t el o g i c ；i n c l u d i n g s e t ；r e d u n d a n tr u l e s ；s t a rs p e c t r u md a t a i i i 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：日期： 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 日期： 导师签名：二哆姿壹l 日期：j 堕年- l 第一章绪论 第一章绪论 1 1 数据挖掘产生的背景及定义 科技的进步，尤其是信息产业的发展，把我们带入了一个崭新的信息化的时代。 随着数据库技术的高速发展和计算机应用的慢慢普及，每天都要产生海量的数据， 所以，在数据库中存储的数据量急剧增大。例如，n a s a 轨道卫星上的地球观测系 统e o s 每小时都会向地面发送5 0 g b 的图像数据；世界上最大的数据仓库之一，美 国零售商系统w a lm a r t 每天也会产生2 亿左右的交易数据；人类基因组数据库项 目也已经搜集了数以g b 的人类基因编码数据掣1 1 。大量的信息在虽然给人们带来 了非常大的便利，但同时也给人们带来了一系列的问题。比如，信息量过大，人们 很难对如此大量的消息进行有效地掌握并消化；网络上的信息安全难以得到可靠的 保障；信息组织形式的不一致性，对信息进行有效统一的处理就变得十分困难等； 一些信息难辨真伪，给正确的运用信息带来了一定困难；另一方面，人们也意识到 隐藏在这些数据之后的更深层次，更重要的信息能够描述数据集的整体特征，有效 利用信息，人们这些就可以预测事物的发展趋势，并且这些信息在决策生成的过程 中也具有非常重要的参考价值，但是由于缺乏有效的数据分析工具，人们往往不能 从整体上对这些数据进行把握。就是在这样的大背景下，在1 9 9 5 年美国计算机年 会( a c m ) 上，数据挖掘( d m ，d a t am i n i n g ) 的概念应运而生1 2 。可以说数据挖掘 的产生是计算机领域发展的必然结果，它的出现使得数据分析进入了一个全新的时 代。人们开始理性地去分析自己所保存的数据，而不是像先前那样依靠自己的感觉 来做出判断。它的出现能够帮助企业的决策者能够有效地分析自己所掌握的信息， 然后在此基础上做出更加科学的决策。 数据挖掘就是从大量的、模糊的、不完全的、有噪声的、随机的数据中，提取 出隐含在其中的、人们事先不知道的、潜在的有用信息和知识，为决策支持服务的 过程【3 j 。而更广义的说法是：数据挖掘就是意味着在一些事实或观察数据的集合中 寻找模式的决策支持过程【4 j 。 数据挖掘涉及到多学科技术的集成，机器学习，高性能计算，神经网络，数据 库技术，信息检索，数据可视化，统计学，模式设别，图像与信号处理和空间数据 分析。典型的数据挖掘系统主要是由以下几部分组成的【5 】： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表 格或者其他类型的信息库，可以在数据上进行数据清理和集成。 基丁谓词逻辑和包含集的分类规则约简算法 数据库或数据仓库服务器：用于存储由各种渠道而获得的有价值的数据，数据 挖掘行为都是在这些数据上进行的。 图形用户界面：用户和数据挖掘系统之间的通信，帮助搜索聚焦，指定数据挖 掘查询或任务，允许用户和系统交互，提供信息，根据数据挖掘的中间结果进行探 索式的数据挖掘。 知识库：这是领域知识，用于评估结果模式的兴趣度，或者指导搜索。这种知 识可能包含概念分层，用于将属性或属性值组织成不同的抽象层，并且用户确信方 面的知识也可以包含在内。可以使用这种知识，根据非期望性来评估模式的兴趣度。 模式评估模块：通常，此成分使用兴趣度来度量，并与数据挖掘模块交互，以 便能够将搜索聚焦在有趣的模式上。 数据挖掘引擎：是数据挖掘系统基本的组成部分，它一般包括一组功能模块， 用于聚类分析、分类、关联、特征化以及演变与偏差分析。 1 2 数据挖掘与知识发现 数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 非常 重要的组成成分，而k d d 是将未经过加工的数据转换成有用信息的过程，如图卜1 所示，该过程包括一系列转换步骤，从数据的预处理到对数据挖掘结果的后处理【3 】。 输入数据一数据预处理h 数据挖掘 h 后处理l 斗信息 特征选择、维规约、规范 化、选择数据子集 模式过滤、可视 化、模式表示 图卜1 数据库中知识发现过程 f i g u r e 1 - 1k n o w l e d g ed i s c o v e r yi nd a t a b a s e 从外部输入的数据可以存储成各种形式( 关系表、平展文件或者是电子数据 表) ，而且还可以分布在多个站点上，或者驻留在集中的数据存储库中。数据预处 理( p r e p r o c e s s i n g ) 的目的是将原始的数据转换成适合分析的形式。数据挖掘是在 大量数据中，挖掘有用信息的过程。由数据挖掘而得到的知识，有时会存在一些冗 余或虚假信息。正是由于这些信息的存在极大地降低了知识的应用价值。所以对挖 掘知识进行后处理就成了一项十分重要的工作。对这些知识进行后处理，剔除那些 冗余的信息，确保只把那些有用的结果和有效的信息集成进决策支持系统之中。在 后处理阶段，可以使用逻辑推理、虚假检验或统计度量等方法剔除那些虚假的或冗 2 第一章绪论 余的信息。后处理的一个十分典型的例子是可视化，它使得数据分析者能够从不同 的角度来探查目标数据与挖掘结果。 1 3 数据挖掘的主要方法 数据挖掘中常用的方法有：聚类，关联规则，粗糙集，决策树，模糊集和概念 格等。 聚类( c l u s t e r i n g ) 【5 】：是将物理或者抽象的对象集合分成多个组的过程。聚类 生成的组被称为簇( c l u s t e r ) ，即簇是数据对象的集合。对数据进行聚类的结果是 所生成的簇内部的任意两个对象之间具有较高的相似度，而不同族的对象之间具有 较高的相异度。聚类算法在数据挖掘中有如下特征：能够处理多种类型属性的能力， 处理孤立点或“噪声”数据的能力，发现任意形状簇的能力，对大型数据集的可扩展 性，处理高维数据的能力，对数据顺序的不敏感性，对先验知识和用户定义参数的 依赖性，聚类结果的可解释性和实用性等。 关联规则【l ，5 】：挖掘关联规则能够帮助我们发现在数据库存在中的项目( i t e m s ) 或属。i 生( a t t r i b u t e s ) 间的有趣关系，发现的这种关系事前对于人们来说是未知的但却 隐藏于数据之中，通过对数据库进行逻辑操作( 如：表的联接) 或统计等简单的方法 并不能得出这种关系。 粗糙集( r o u g hs e t ) t 6 - 8 1 ：是以波兰的数学家p a w l a k 为代表的研究者在1 9 8 2 年首次提出的，这种新的数学工具能够处理不确定性和含糊性的问题。在粗糙集对 数据进行处理的过程中，使用者完全的能够独立进行，既在挖掘的过程中完全不需 要关于数据的任何预备的或者是额外的信息。粗糙集可以约简信息系统中的属性， 通过对属性的约简，在原有属性集合中求出一个与其有相同的分类能极小子集。要 想找到属性集的所有约简是一个n p 完全问题。可以用不可分辨函数与不可分辨矩 阵来对原来的属性集进行约简。 决策树o 】：决策树是一个类似树形结构的流程图，每个内部节点表明在一个 属性上的测试，树枝描述测试的结果，叶子节点表明分类或分类的分布情况。最顶 端的节点是树根。选择合适的分类属性是构造一个好的决策树的关键。通常选用的 方法是，在各节点选择测试属性时用信息增益度量的方法，当前节点的测试属性为 具有最高信息增益的属性。 模糊集【l l 】：美国加利福尼亚大学的扎德教授于1 9 5 6 年提出了模糊集。模糊集 合理论是一种用精确的数学语言对模糊性进行描述的方法，在描述差异的中介过度 3 基丁谓词逻辑和包含集的分类规则约简算法 时它使用的是隶属程度。精确性与复杂性的“不相容原理”为扎德所提出。数学的应 用范围能够从精确现象扩大到了模糊现象领域正是由于模糊数学的产生。客观事物 的类属性往往并不是十分明确的，而很多聚类方法实现的却是是对数据对象的“硬 划分”。对象的这种不分明的类属性质能够用模糊聚类方法进行了很好地表达与处 理。模糊聚类分析方法有编网法，模糊c 均值方法，基于摄动的模糊聚类方法，最 大树法，传递闭包法等。模糊聚类分析已广泛的应用于气象学，经济学，生物学， 信息科学，工程技术科学等许多领域。 概念格【1 2 彤】：概念格是一种有效的数据挖掘及知识发现的方法，是形式概念分 析中的核心数据结构，最初于1 9 8 2 年由德国的w i l l e r 教授提出。概念格的每个概 念由两部分组成：内涵和外延，内涵是外延具有的共同属性，外延是概念覆盖的对 象的集合。由于概念格所具有的完备性，可以在概念格上进行多种不同知识的挖掘， 如对分类规则、关联规则、蕴含规则、等知识的提取都取得了非常好的效果。另外， 在数字图书馆、软件工程和信息检索等领域也得到了广泛的应用。近几年来，概念 格一直是人们研究的一个热点领域，这也使得概念格得到了非常快速的发展。 1 4 数据挖掘的功能 1 4 1 关联分析 关联分析发现关联规则，这些规则展示属性一值频繁地在给定的数据集中一起 出现的条件。关联分析广泛应用于购物篮或事物数据分析中。 关联规则的形式一般为x j y ，即“a l a 低 j “b l a a b m 形式的规则， 其中，a 0 1 ，n ) ) ，b i ( i 1 ，m ) ) 是属性- 值对。关联规则x j y 解释为“满足 x 中条件的数据库元组多半也满足y 中的条件”。 1 4 2 分类和预测 分类是一个这样的过程，它找出描述并区分数据类或概念的模型( 或函数) ， 以便能够使用模型来预测类标记未知的对象。 分类模型是基于对训练数据集( 即其类标记已知的数据对象) 的分析而得出的。 并且挖掘分类模型的方法有多种，且不同的方法挖掘出的分类模型的表示形式是不 同的，比较典型的表示形式有神经网络，判定树，分类( i f t h e n ) 规则。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望某 些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称 之为预测，预测一般限于值的预测，并因此不同于分类。预测也包含基于可用数据 4 第一章绪论 的分布趋势的识别。 1 4 3 聚类分析 聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过 程。聚类的结果是在一个簇中的对象具有非常高的相似性，而不同簇中的对象很不 相似。所形成的每个簇可以看做一个对象类，规则可以由它导出。 聚类一般分析那些类别标识未知的数据。 1 4 4 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或者模型不一致。这 些数据对象被称为孤立点。在一些应用中( 如欺骗检测) ，人们往往更加关心那些 罕见的事情。孤立点数据分析也称作孤立点挖掘。 使用统计试验检测可以挖掘孤立点。一个数据分布或概率模型先被假定，然后 用距离度量的方法，孤立点一般为到其它聚类的距离很大的对象。 1 5 数据挖掘的应用 数据挖掘是数据量快速增长的结果，所以它一开始就是面向应用的。目前数据 挖掘，已经在许多领域得到了应用，并且都取得了非常不错的效果【5 1 。 针对d n a 数据分析和生物医学的数据挖掘：d n a 数据的分析是目前生物医学 研究的一个热点问题，许多疾病和残疾的基因成果的发现都是在对此的基础上完成 的，对疾病的诊断，预防和治疗的新药，新方法的发现也是依靠d n a 分析的研究 成果。d n a 序列的研究是基因研究中的个非常重要的关注点，因为所有活的生 物体的基因代码都是在这种序列的基础构成的。但是，这是一项任务量非常巨大的 工作，单纯的去靠人工是几乎不能够完成的。因为在数据挖掘中已经有许多有意义 的序列模式分析和相似检索技术，所以数据挖掘就成了分析d n a 强有力的工具。 电信业中的数据挖掘：目前电信业已经是一个应用各种现代化的通信手段的、 能够提供综合性服务的行业。并且，竞争在电信业中也变得非常激烈。因此，利用 数据挖掘技术来帮助人们理解商业行为，更好地利用资源，捕捉盗用行为，确定电 信模式和提高电信业中的服务质量是非常有必要的。利用数据挖掘可以在很大程度 上帮助改变电信的服务质量。可以应用的范围有：( 1 ) 盗用模式分析和异常模式识 别：盗用行为每天使电信行业的损失多达千万。确定潜在的盗用者和他们的非典型 的使用模式，以及发现需要引起注意的异常模式，检测想侵入用户帐户的企图，这 些都是非常重要的。( 2 ) 多维关联和序列模式分析：多维分析中关联和序列模式的 5 基于谓词逻辑和包含集的分类规则约简算法 发现可以用来推动电信业服务的发展。( 3 ) 电信数据分析中可视化工具的使用： o l a p 可视化，连接可视化，关联可视化，聚类和孤立点可视化等工具，已经证明 对电信数据分析是非常有用的。( 4 ) 电信数据的分析：电信数据具有多维的特性， 对此类数据的多维分析有助于识别和比较数据通信情况，系统负载，利润，用户行 为，资源使用，等等。 零售业中的数据挖掘：取得更好的顾客保持力与满意程度，改进服务的质量， 零售数据挖掘可有助于识别顾客的购买行为，设计更好的货品运输与分销策略，发 现顾客的购买模式与趋势，提高货品的销量比率，减少商业成本。以下是几种典型 的应用情况。( 1 ) 顾客保持力一顾客忠诚分析。( 2 ) 购买推荐和商品参考。( 3 ) 销 售，产品，顾客，地区和时间的多维分析。( 4 ) 促销活动的有效性分析。( 5 ) 基于 数据挖掘的数据仓库的设计与构造。 数据挖掘的研究方兴未艾，具有非常广阔的应用前景。数据挖掘一定会在未来 的生产与生活中发挥越来越大的作用。 1 6 数据挖掘的主要问题 数据挖掘中应该考虑挖掘方法，用户交互，性能和各种数据类型。所以它的主 要问题有【5 j ： 挖掘方法和用户交互问题：这反映所挖掘的知识类型，特定的挖掘和知识的显 示，在多粒度上挖掘知识的能力，对领域知识的有效使用。( 1 ) 在数据库中挖掘不 同类型的知识：因为不同的用户可能对类型不同的知识感兴趣，所以数据挖掘系统 就应当能够覆盖范围很广的数据分析与知识发现任务。( 2 ) 处理噪声和不完全数据： 某些有异常情况的数据可能也被存放在数据库中，这些数据对象是不完全的或者噪 声数据对象。分析的过程可能被这些对象搞乱，这种情况的结果是可能导致数据与 所构造的知识模型存在过度适应的情况。而这种情况会导致，所发现的模式的精确 性也许会很差。需要处理数据噪声的数据清理的方法和数据分析的方法，以及发现 与分析异常情况的孤立点挖掘方法。( 3 ) 多个抽象层的交互知识挖掘：因为在数据 库中发现什么样的知识是难以预料的，所以应当进行交互式的数据挖掘。应当使用 适当的数据抽样技术，对那些包含大量数据的数据库，进行交互式的数据探查。( 4 ) 结合背景知识：知识的发现的过程可以使用所研究领域的信息或者背景来指导，并 以简洁的形式把所发现的模式在不同的抽象层上表示。( 5 ) 模式评估兴趣度问题： 数以千计的模式可能被数据挖掘系统所发现。不同的用户对不同的模式感兴趣，既 6 第一章绪论 并不是挖掘出来的所有的模式对于用户来说都是有趣的，它们缺乏新颖性或者是表 示公共的知识。关于开发模式兴趣度的评估技术，特别是关于特定的用户类，基于 用户的信赖或者是期望，评估模式价值的主观度量，依然存在一些挑战。在指导发 现过程与压缩搜索空间时使用兴趣度度量，是又一个人们非常感兴趣的研究领域。 性能问题：这包括数据挖掘算法的可伸缩性，有效性，和并行处理。( 1 ) 数据 挖掘算法的有效行和可伸缩性：要想有效地从数据库的大量数据中提取有用的信 息，必须保证数据挖掘算法具有有效与可伸缩性。或者说，对于大型数据库，数据 挖掘算法的运行时间必须有一个限制，必须是能够预先作出估算的并且必须是可以 被用户所接受的。从数据库的角度，数据挖掘系统实现的关键问题是有效性和可伸 缩性。( 2 ) 并行，分布式和增量挖掘算法：许多数据库的大容量性，数据的广泛分 布性与一些数据挖掘算法的计算复杂性是促使开发并行和分布式数据挖掘算法的 原因。这种算法把数据划分成几个部分，对这些部分可以并行处理，然后再合并每 部分的结果。此外，有些数据挖掘过程的高花费也导致了对增量数据挖掘算法的需 要。增量算法与数据库的更新结合在一起，而不必再重新挖掘全部的数据。这种算 法渐增地进行知识更新，修正与加强先前已经发现的知识。 关于数据库类型的多样性问题：( 1 ) 由异种数据库和全球信息系统挖掘信息： 多个异种数据库中的数据规律可以通过数据挖掘来帮助发现，简单的数据查询系统 多半难以发现这些规律，异种数据库的信息交换与互操作性也能够被改进。( 2 ) 关 系的和复杂的数据类型的处理：数据库可能包含复杂的数据对象，超文本与多媒体 的数据，空间数据，事物数据或者时间数据。正是由于数据类型的多样性与数据挖 掘目标的不同，一个数据挖掘系统不可能挖掘所以类型的数据。对特定类型的数据 进行挖掘，应当构造特定的数据挖掘系统。 在近年来的数据挖掘研究和开发中，一些挑战已受到一定程度的关注，并且考 虑到了各种需求，而另一些还处于研究阶段中。然而这些问题将继续刺激进一步的 研究与改进。 1 7 本文的主要研究内容及论文的组织与安排 1 7 1 研究内容 冗余规则的存在大大降低了分类规则集的分类效率和可理解性，所以如何对规 则集进行约简，消除规则集内存在的冗余，就成了分类中一个十分重要的问题。谓 词是一种有效的知识表示方法，利用谓词公式来表示分类规则，然后利用谓词公式 7 基于谓词逻辑和包含集的分类规则约简算法 中的逻辑推理，对分类规则集中存在的冗余情况进行刻划，并研究了消除冗余的算 法。根据规则和数据间的关系，研究了包含集的概念，并通过对包含集的处理来消 除规则集中存在的冗余。 1 7 2 论文组织 论文总共分为五章，具体安排如下： 第一章主要介绍了数据挖掘的产生背景，基本概念，主要应用和面对的问题。 第二章介绍了分类规则的基本概念及主要提取方法，谓词公式的基本概念以 及集合的基本概念。 第三章研究了一种基于谓词逻辑的分类规则约简算法。 第四章研究了基于包含集的分类规则约简算法。 第五章总结本文取得的研究成果，并分析有待继续深入研究的问题和进一步 拓展的方向。 8 第二章分类、谓词逻辑及集合 第二章分类、谓词逻辑及集合 2 1 分类知识介绍 2 1 1 分类基本概念 分类即区分数据类别，是数据挖掘中应用最多的任务。数据分类一般分为两步： 第一步，从数据中选出已经分好类的训练集，在此训练集上运用分类技术，产生关 于类别的精确描述，它代表了这类数据的整体信息。这种类别描述通常由分类规则组 成，可以用来对未来的未知类别的数据进行分类预测。第二步，使用模型进行分类。 在使用模型进行分类之前，必须要评估模型( 分类法) 的预测准确率。模型在给定 测试集上的分类准确率是正确被模型分类的预测样本的百分比。如果认为模型的分 类准确率是可以被接受的，就可以用它来对类标号未知的数据元组或对象进行分类。 2 1 2 分类知识的表示方法 分类知识可以用多种形式进行表示，如分类( i f - t h e n ) 规则，判定树，或神经 网络。 判定树是一种类似于流程图的树形结构，每个节点表示在一个属性值上的测试， 每个分支表示在测试上的一个输出，树叶用来代表类或者是类分布。神经网络是一 组类似于神经元的在处理单元之间的加权连接。 分类模型是由很多条的分类规则组成。一条分类规则可以分成两部分，规则前 件与规则后件。其一般按照i f t h e n 的形式来定义。规则前件包含一组条件的集合， 一般由逻辑连接符“a n d ”来进行连接，前件中的单个条件一般为一组属性值对。 规则的后件定义了符合规则前件数据的预测类别。而对于一条分类规则而言，它的 含义就是只要某条数据能同时满足规则前件中的所有条件，那么本规则就能确定此 条数据的类别，且类别为规则的后件所代表的类别。一条分类规则只能对满足它前 件的数据进行分类，并且能够得出一个确切的数据类别。 由于分类规则的形式易于理解，且方便在计算机内进行存储，所以在分类知识 的表示中得到了十分广泛的应用。 2 1 3 分类知识的提取方法 由于分类在现实生活与学习中有十分广阔的应用前景，所以近年来人们在分类 规则的提取上做了大量有价值的研究，产生了许多的有价值的分类规则提取算法。 利用概念格提取分类规则【1 4 1 9 】：概念格的每个节点就是一个形式概念，它由两 部分组成：外延，即概念所覆盖的实例；内涵，即对概念的描述，亦即该概念覆盖 9 基于谓词逻辑和包含集的分类规9 1 0 约简算法 实例的所有共同的特征。概念间的泛化与特化关系可以通过h a s s e 图生动而简洁地进 行体现。因此，概念格被认为是进行数据分析的强有力的工具。大量的研究证明， 利用概念格来提取分类规则也能取得非常好的效果。 利用粗糙集提取分类规则，2 0 。2 7 1 ：运用粗糙集理论把关系数据库按属性值划分 成若干个等价类、约简冗余属性以及依赖属性，然后对数据约简后的目标关系表求 取分类支持度大于阈值的强类与特征置信度大于阈值的强特征，从而可以获取强类 中的强特征的分类知识规则。这一分类技术的实现方法是以数据库中的关系表为基 础的，而且在原始数据增加的情况下，可以通过约简来压缩数据的规模，使之只与 属性值有关，而与原始的数据量无关。 利用决策树提取分类规则【9 。1 0 ，2 8 斟】：决策树是一种非常好的分类方法，近年来国 内外学者做了大量的研究。利用决策数提取分类规则比较经典的是i d 3 算法，该算法 是一种自顶向下、分而治之的递归构造决策树的贪心算法。它采用的是不可返回策 略，每次搜索全部样本空间中的一个子集来生成决策树，以确保决策树的建立最简 单，并且每次分析的训练数据量最少。其优点是在测试属性的选择上，利用了信息 增益的概念，构造的决策树平均深度较小，学习能力强，描述简单，分类速度快。 利用蚁群算法提取分类规则【3 5 。6 】：利用蚁群算法来提取分类规则一般分为两步： 1 ) 规则构造：模仿蚂蚁的觅食行为来构造分类规则。蚂蚁在觅食的过程中重复的选 择节点直到构造出一条完整的路径。每一条完整的路径就为一条分类规则。理论上 每个节点的选择可以是完全随机的，但是如果真的这样做就需要花费漫长的计算时 间来作为代价。所以一般情况下要设计一个与问题相关的启发式函数，用来引导蚁 群的搜索。2 ) 规则修剪：重复选择路径节点的的后果是可能存在分类规则对训练数 据集的过度拟合，所以要对得到的分类规则进行剪枝。而只有对一个规则进行剪枝 之后，它才可以算作一条合格的分类规则。对规则进行剪枝时一种比较简单的方法 是，依次移去能使规则有效性得到最大提高的属性节点，直至任一属性节点的移去 都将会导致降低规则的有效性。当从规则中移去属性节点而使规则改变时，可能需 要重新给它赋予一个类标号节点，以便使规则的有效性仍然是最大的。 利用遗传算法提取分类规则【3 7 】：遗传算法是一种基于生物进化论与分子遗传学 的全局随机搜索的算法，它具有使用简单、应用广泛等特点。遗传算法在分类中应 用的基本思想是将分类规则按某种形式进行编码，形成染色体。再随机选取n 个染色 体用来构成初始的种群，然后根据预定的评价函数对每个染色体计算适应值。通过 遗传操作( 交叉、选择、变异) 来产生一群新的更适应环境的染色体，从而形成新的 1 0 第二章分类、谓词逻辑及集合 种群。这样一代代不断繁殖进化，最后收敛到一批最适应环境的个体之上，这样就 能求得最优的分类规则集。 利用神经网络提取分类规则3 8 1 ：神经网络是解决分类问题的行之有效的一种方 法。神经网络以大量简单的单元( 节点) 通过复杂的相互连接后，并行运行以实现其 功能，系统的知识存储于网络的结构与各单元之间的连接权中。当神经网络建立起 来后，利用某种策略能够从中抽取出若干条的符号规则，形成分类规则集。 2 1 4 分类模型的判断标准 判断一个分类模型，首先要看这个模型的分类质量，因为分类质量的好坏直接 关系着分类模型的分类效果；除了考虑一个分类模型的分类质量，还要考虑一个分 类模型内规则的数量，因为规则数的多少直接关系着模型的分类效率与模型的可理 解性。可以从以下几个方面来判断一个分类模型：分类正确率，分类错误率，覆盖 率，平均使用规则数。 分类正确率：确保最大的分类正确率是衡量分类算法的一个重要标准，在此采 用的分类正确率的计算公式为： ” z e - m ( 公式2 1 ) 式中z 表示正确分类的实例的数目，m 表示所有实例的数目。只有分类正确率达 到一定的标准，我们说分类模型才有意义，才可以用它来划分陌生数据的类别。 分类错误率：表示错误分类的实例的数目和所有实例的比值，具体公式为： f c = 二( 公式2 2 ) 朋 式中的f 表示错误分类实例的数目，m 表示所有实例的数目。一个分类模型的分 类错误率必须控制在一定的范围之内。 覆盖率：表示分类模型能进行分类的实例的数目与所有实例数目的比值。具体 公式为： d ：旦( 公式2 3 ) 朋 式中的h 表示分类模型能进行分类的实例的数目，m 表示所有实例的数目。覆盖 率是一个分类模型的重要衡量标准，所以对于所有的挖掘算法而言，都要尽量提高 模型的覆盖率。 平均使用规则数：表示模型对数据集进行分类时，分类一条数据的平均扫描规 则数。为分类时所有的扫描次数与数据集内数据数的比值。具体的计算公式为： 基丁谓词逻辑和包含集的分类规蚍0 约简算法 p v = 兰( 公式2 4 ) c 式中的g c 表示对数据集进行分类时所有的扫描次数，c 为数据集的数目。对于 一个分类模型来说，这个值越少说明规则集的分类效率越高。 因为对于分类正确率，分类错误率，覆盖率，这三个参数只要知道两个参数就 可以推出另外一个，所以通常情况下只要用两个参数即可，本文中我们用的是正确 率，分类错误率这两个参数。 2 2 谓词公式的基本概念 2 2 1 命题公式 定义2 1 命题就是具有真假意义的语句。 命题代表人们进行思维时的一种判断，或者是否定，或者是肯定，只有这两种 情况。若命题的意义为假，称它的真值为假，记做f 。若命题的意义为真，称它的 真值为真，记做t ；一个命题不能同时即为真又为假，但可以在一定条件下为真， 在另一种条件下为假。没有真假意义的语句不是命题。 定义2 2 命题为简单的陈述句，不能分解成更简单的句子命题为简单命题( 原子命 题) 。简单命题一般用英文字母p ，q ，r ，表示。 定义2 3 由简单命题用联结词联结而成的命题叫称为复合命题。 命题逻辑主要研究的是复合命题。 定义2 4 用符号来表示命题称为命题符号化。 在命题逻辑中，可用下列联结词把一些简单命题连接起来进而构成一个复合命 题，以表示一个比较复杂的含义。 _ 1 ：称为“否定”或者“非”。其作用是用来否定位于它后面的命题。当- 1 p 为假 时，p 为真；当命题p 为真时，一p 为假。 v ：称为“析取”。它表示被它连接起来的两个命题具有“或”的关系。 八：称为“合取”。它表示被它连接起来的两个命题具有“与”的关系。 专：称为“蕴含”或者“条件”。p 寸q 表示“p 蕴含q ”，即“如果p 则q ”，其中p 称为条件的前件，q 称为条件的后件。 定义2 5 可由以下原则得到命题演算中的合式公式： ( 1 ) 单个命题常项或变项p ，q ，0 ，1 是合式公式； ( 2 ) 若彳是合式公式，则叫也是合式公式； ( 3 ) 若a ，b 是合式公式，则( a 八b ) ，( a v b ) ，( a b ) ，( a h b ) 是合式公式； 1 2 第二章分类、谓词逻辑及集合 ( 4 ) 只有有限次地应用( 1 ) ( 3 ) 组成的符号串才是合式公式。 在命题逻辑中合式公式即称为命题公式。 一个含有命题变项的命题公式的真值是不确定的，只有用指定的命题常项代替 后真值才唯一确定。 定义2 6 命题公式a 在各种赋值下取值恒为真，则a 为重言式。 定义2 7 命题公式a 在各种赋值下取值恒为假，则a 为矛盾式。 定义2 8 命题公式a 至少存在一组赋值是成真赋值，则a 为可满足式。 重言式一定是可满足式，反之不真。 、 定义2 9 设a ，b 为两命题公式，若等价式a h b 是重言式，称a 与b 是等值公式。 记作：a b 。 等值关系是传递的、对称的和自反的，因而为等价关系。 命题逻辑中的常用的等值公式： 1 交换律：p v q c z , q v p ，p a q c ： q a p 。 2 等幂律：a c = a v a ，a c ： a 八a 。 3 结合律：( p v q ) v r e ，p v ( q v r ) ，( p a q ) a r c ： p a ( q a r ) 。 4 德摩根律：一( p v q ) 一p 八一q ，一( p a q ) 一p v q 。 5 吸收律：p ( p v q ) p ，p v ( p 八q ) p 。 6 连接词转化归律：p q 一p v q 。 定义2 1 0 按一定方法寻找某个复合命题公式的等值式的过程称为等值演算。 2 2 2 谓词公式 谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可看做是谓词逻辑的一种 特殊形式【3 9 1 。为了表示知识的需要，谓词逻辑在命题逻辑的基础上又增加了一些新 的概念与性质。 定义2 1 1 用来刻划个体词之间关系或者个体词的性质的词称为谓词。 谓词的一般形式是：p ( x l ，x 2 ，x n ) ，其中：p 是谓词名，x i ，x 2 ，x n 是个体。谓词 名通常用大写的英文字母来表示，个体通常用小写的英文字母表示。在谓词中，个 体可以是变元，也可以是常量，还可以是一个函数。在用谓词表示客观事物时，谓 词的语义是由使用者根据需要人为地来定义的。当谓词中的所有变元都用特定的个 体取代时，谓词就具有一个确定的值：t 或f 。 定义2 1 2 谓词中所包含的个体词数称为谓词的元数。 定义2 1 3 含n ( 腔1 ) 个个体词( 个体变项) 的谓词称为n 元谓词，可用p ( x l ，x 2 ，x n ) 13 基于谓词逻辑和包含集的分类规则约简算法 来表示。 一元谓词一般表示性质，而二元或者多元谓词一般用来表示关系。 定义2 1 4 在谓词p ( x l ，x 2 ，x n ) d p ，若x i ( i = l ，n ) 都是变元，个体变量，或者函数， 则称它为一阶谓词。 在谓词中如果某个x i 本身又是一个一阶谓词，则称它为二阶谓词，余者类推。 在知识表示中，我们一般用到的是一阶谓词。 为刻画谓词与个体问的关系，在谓词逻辑中引入了两个量词，一个是存在量词 j ，表示“至少有一个”、“存在”，“有某些”等含义，例如：j x 表示存在个体 域中的个体，3 x f ( x ) 表示存在个体域中的个体具有性质f 。另一个是全称量词v ，为 “任意”，“一切”，“所有 等含义。例如：v x 表示对个体域中的所有的个体， v x f ( x ) 表示个体域中的所有个体都具有性质f 。 定义2 1 5 不出现命题联结词和量词的命题函数p ( x 1 ，x 2 ，x n ) ，且x i 是个体常项或变 项，为原子公式。 定义2 1 6 可按下述规则得到谓词演算的合式公式： ( 1 ) 原子公式是合式公式； ( 2 ) 若a ，b 是合式公式，则( a 专b ) ，n a ) ，( a v b ) ，( a a b ) ，( a h b ) 也是合式公式； ( 3 ) 若a 是合式公式，贝, i j v x a ，3 x a 也是合式公式； ( 4 ) 只有有限次地应用( 1 ) ( 3 ) 构成的符号串才是合式公式。 在谓词逻辑中合式公式也称谓词公式，简称为公式。在公式中，量词运算的优 先级高于所有的其它联结词。 2 2 3 谓词公式表示知识的特点 通常来说，把有关信息关联在一起所形成的信息的结构就称为知识。知识反映 了客观世界中事物之间的关系，不同事物或相同事物间的不同关系就形成了不同的 知识。 知识表示，实际上就是对知识的一种描述，一种计算机可以接受的用于描述知 识的数据结构。对知识进行表示的过程就是把知识编码成某种数据结构的过程。目 前用得比较广泛的知识表示方法有：p e t r i 网表示法，一阶谓词逻辑表示法，产生式 表示法，语义网络表示法，框架表示法，脚本表示法，面向对象表示法。 谓词逻辑是一种形式化语言，也是目前为止能够表达人类思维活动规律的一种 最精确的语言，它与人们的自然语言比较接近，同时又可非常方便地存储到计算机 中，并被计算机做精确处理。 1 4 第二章分类、谓词逻辑及集合 谓词逻辑适合用作表示事物的属性，状态，概念等事实性的知识，也可以用来 表示事物之间确定的因果关系，即规则。事实通常用谓词公式的“与或”形来表示， 所谓的“与或”形就是用合取符号( 八) 以及析取符号( v ) 连接起来所组成的公式。 规则一般用蕴含式来进行表示。当用谓词公式来表示知识时，首先必须定义谓词， 指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词 公式，来表示一个完整的含义。 一阶谓词逻辑是一种形式化的语言系统，它用逻辑的方法研究推理的规律，即 条件与结论之间的蕴含关系。用一阶谓词逻辑表示知识的特点有：精确性，谓词逻 辑是二值逻辑，可用作表示精确知识；严密性，谓词逻辑具有非常严格的形式定义 和推理规则；自然性，谓词逻辑是一种接近于自然语言的形式化语言，用它来表示 的知识理解起来比较容易；容易实现，用谓词逻辑表示的知识可以比较容易地转换 成计算机的内部形式，易于模块化，便于对知识进行增加，删除及修改。正是由于 这些优点，使其在新形势背景下的知识表示中得到了非常广泛的应用【3 9 4 0 】。 2 3 集合的基本概念 集合是一个不能精确定义的基本概念。一般来说，把某些具有共同性质的东西， 汇集成一个整体，就组成了一个集合。通常用大写的英文字母来表示集合的名称； 用小写的英文字母来表示组成集合的事物，即元素。若元素a 属于集合c ，记做a e c ， 亦称a 包含于c ；若元素a 不属于集合c ，记做a 仨c ，亦称a 不包含于c 。 两个集合相等是按照下述原理定义的： 外延性原理：两个集合是相等的，当且仅当它们有相同的成员。 两个集合c 和d 相等，记作c