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

摘要 摘要 本论文研究课题源于国家9 7 3 基础研究项目( n o 2 0 0 2 c b 3 1 2 0 0 6 ) i n t e m e t 环境 下基于a g e n t 的软件中间件理论和方法研究”和国家自然基金项目 ( n o 6 0 4 7 3 0 7 7 ) “水印关系数据库关键技术研究”。 近年来，随着我国信息化建设的快速发展，知识的自动获取已成为一种重要的 技术手段。数据挖掘研究如何从大量的数据中智能地自动地抽取出有价值的知识 和信息，因而成为当前人工智能研究中非常活跃的研究领域。粗糙集理论是一种 有效地处理模糊性和不确定性问题的数学工具，为数据挖掘提供了新的思路和基 础。本文的研究工作主要围绕基于粗糙集理论的数据挖掘，重点从基于粗糙集理 论的特征选择和连续属性离散化两个方面展开。本文的主要创新性研究工作包括： 1 ) 提出了基于属性出现频率的属性约简算法，这种算法以条件属性在分辨矩 阵中出现的频率作为启发信息，以条件属性所在最小分辨矩阵项的基数作为辅助 启发信息，来寻找决策信息系统的最小约简。实验证明，大多数情况下该算法能 够找到系统的最优( 最小) 约简。在没有找到最优约简的情况下，算法能够找到 次优约简。 2 ) 分析属性约简中条件属性之问的关系以及约简集合中条件属性和决策属性 之间的关系。在粗糙集理论的基础上给出了属性相关度的定义，并且根据这一定 义，提出了基于属性相关度的属性约简算法。实验结果证明，这种算法能够有效 地去除属性子集中的无关属性和冗余属性。 3 ) 提出了基于粗糙集理论的确定候选断点集合的新算法，该方法能够在保证 系统分辨关系的前提下，大幅度的降低候选断点的数量，从而大幅度的减少了后 继离散化算法的计算量。实验表明，这种确定候选断点集合的办法是切实可行的。 4 ) 提出了一种基于断点权重的启发式连续属性离散化方法。这种方法将连续 属性的候选断点作为一个单个的条件属性，建立新的决策信息系统以考察每个候 选断点对信息系统分辨能力的贡献。将断点在分辨矩阵中的出现频率作为断点的 权值，寻找系统的最优断点集合。实验结果表明，此算法能在较好地保留原信息 系统的分辨能力的同时，有效地解决离散化问题。 5 ) 提出了一种基于d b s c a n 聚类的连续属性离散化算法。这种离散化算法， 结合基于密度分布的聚类算法和粗糙集理论中属性依赖度的概念，通过对决策信 息系统中的所有实例进行聚类来实现连续属性的离散化。实验表明，这种离散化 西北t 业大学博士学位论文基于耗i 糙集理论的数据挖掘算法研究 算法是可行的，其离散化结果对数据的分类错误率较低。 由于上述约简算法和离散化算法中的某些算法需要构造决策信息系统的分辨 矩阵，其存储空间开销较大，因此如何减少算法的空间需求是下一步要解决的问 题。另外，如何将粗糙集理论和其他数据挖掘方法、软计算方法结合起来，也是 一项很有意义的研究课题。 关键词：数据挖掘粗糙集特征选择约简属性相关性属性依赖连续属性离散 化 a b s 仃a e t a b s t r a c t t h et h e o r e t i cs t i l d yo ft h i sp a p e rc o m e sf r o mt h e2 0 0 2 c b 31 2 0 0 0p r o g r a mo f n a t i o n a l9 7 3f u n d a m e n t a lr e s e a r c hp r o g r a ma n dt h e6 0 4 7 3 0 7 7p r o g r a mo fn a t i o n a l n a t u r es c i e n c ef o u n d a t i o n i nr e c e n ty e a r s ，i nc o n t r a s tt ot h er a p i dd e v e l o p m e n to fo u rn a t i o n a li n f o r m a t i o n c o n s t r u c t i o n , t h et e c h n o l o g yo fa u t o m a t i ca c q u i s i t i o no fk n o w l e d g eh a sb e c o m ei t s b o t t l e n e c k a sat e c h n o l o g ya i m st of i n do u tt h ew a yo fa b s t r a c t i n ga u t o m a t i c a l l ya n d i n t e l l i g e n t l yv a l u a b l ei n f o r m a t i o no rk n o w l e d g ef r o mah u g ea m o u n to fd a t a ，d a t a m i n i n gi sa na c t i v er e s e a r c hf i e l do fa ir e s e a r c h i n g a sa ne f f i c i e n tm a t h e m a t i ct o o lt o d e a lw i t ht h ev a g u e n e s sa n du n c e r t a i n t y ，r o u g hs e tt h e o r yp r o v i d e san e wa p p r o a c ho f d a t am i n i n g i nt h i st h e s i s ，w er e s e a r c hs o m ep r o b l e m so fd a t am i n i n gb a s e do nr o l l g h s e tt h e o r y t h er e s e a r c ht o p i cm a i n l yi n c l u d e sf e a t u r es e l e c t i o nb a s e do nr o u g hs e t t h e o r ya n dc o n t i n u o u sf e a t u r ed i s c r e t i z a t i o nb a s e do nr o u g hs e tt h e o r y m a i nt o p i c i n c h i d e si s ： 1 ) w ep r o p o s eah e u r i s t i cf e a t u r er e d u c ta l g o r i t h mb a s e do nf e a t u r ea p p e a r i n g f r e q u e n c y t of i n d i n g o u tm i n i m a lr e d u c t ，t h i s a l g o r i t h me m p l o y s a p p e a r i n gf r e q u e n c yo fc o n d i t i o nf e a t u r ei nd i s c e r n i b i l i t ym a t r i x a s h e u r i s t i ci n f o r m a t i o n ，a n de m p l o y sl e n g t ho fs h o r t e s td i s c e r n i b i l i t ym a t r i x e n t r yw h i c hc o n t a i n sc o r r e s p o n d i n gc o n d i t i o nf e a t u r e a ss e c o n d a r y h e u r i s t i ci n f o r m a t i o n e x p e r i m e n ts h o w st h a ti nm o s ts i t u a t i o n st h e p r o p o s e da l g o r i t h m c a l lf i n do p t i m a lr e d u t 2 )w ea n a l y s e st h er e l a t i o n s h i po fc o n d i t i o nf e a t u r ei nr e d u c tw i t hd e c i s i o n f e a t u r ea n dr e l a t i o n s h i po fc o n d i t i o nf e a t u r ew i t ho t h e rf e a t u r e si nr e d u c t ， a c c o r d i n gc o n c e p to ff e a t u r ed e p e n d e n c yb a s e do nr o u g hs e tt h e o r y ，w e d e f i n ef e a t u r ec o r r e l a t i o n b a s e do nt h i sd e f i n i t i o n ，w ep r o p o s eaf e a t u r e r e d u c ta l g o r i t h mb a s e do nf e a t u r ec o r r e l a t i o n t h ee m p i r i c a ls t u d ys h o w s t h a tt h ep r o p o s e d a p p r o a c hi se f f i c i e n ta n de f f e c t i v ei nr e m o v i n gr e d u n d a n t a n di r r e l c v a n tf e a t u r e s 3 )w ep r o p o s ean e wa p p r o a c ht od e c i d ec a n d i d a t ec u tp o i n ts e to fd e c i s i o n i 西北1 = 业大学博十学位论文 对基于机糙集数据挖掘的若干改进 i n f o r m a t i o ns y s t e m t h i sa p p r o a c hc a nd e c r e a s el o t so fc u tp o i n tf r o m c a n d i d a t ec u tp o i n ts e tw h i l et h ed i s c e r n i b i l i t yo fi n f o r m a t i o ns y s t e mc o u l d s t i l lb em a i n t a i n e d t h ee m p i r i c a ls t u d ys h o w st h i sa l g o r i t h mi sv i a b l e 4 )b yr e g a r d i n gc a n d i d a t ec u tp o i n ta san e wc o n d i t i o nf e a t u r e ，w ec o m p u t e n e wd e c i s i o ni n f o r m a t i o ns y s t e mt oi n v e s t i g a t et h ed i s c e m i b i l i t yo fe a c h c a n d i d a t ec u tp o i n tt od e c i s i o ni n f o r m a t i o ns y s t e m w ep r o p o s eah e u r i s t i c d i s c r e t i z a t i o na l g o r i t h mb a s e do nc u tp o i n tw e i g h t t h i sa l g o r i t h mt a k et h e c u tp o i n t sa p p e a r i n gf r e q u e n c yi nd i s c e r n i b i l i t ym a t r i xo fn e wd e c i s i o n i n f o r m a t i o ns y s t e ma sh e u r i s t i ci n f o r m a t i o nt of i n d i n go u to p t i m a lc u t p o i n ts e to fs y s t e m e x p r i m e n ts h o w st h a tt h ep r o p o s e da p p r o a c hc a n e f f e c t i v e l ys o l v et h ep r o b l e mo fd a t ad i s c r e t i z a t i o nw h i l et h ed i s c e m i b i l i t y o fi n f o r m a t i o ns y s t e mi sm a i n t a i n e d 5 ) w ep r o p o s ead i s c r e t i z a t i o na l g o r i t h mb a s e do nd b s c a nc l u s t e r i n g i n t e g r a t i n gd e n s i t y - b a s e dc l u s t e r i n gw i t hc o n c e p to ff e a t u r ed e p e n d e n c yi n r o u g hs e tt h e o r y ，t h i sa l g o r i t h mc l u s t e ri n s t a n c e so fi n f o r m a t i o ns y s t e mt o d i s c r e t ec o n t i n u o u sf e a t u r e s e x p e r i m e n ts h o w st h i sa l g o r i t h mi sf e a s i b l e ， a n dt h ec l a s s i f i c a t i o ne r r o rr a t eb yd i s c r e t i z a t i o nr e s u l ti sl o w e r i ti s s p a c ec o n s u m i n gt o c o n s t r u c tt h ed i s c e r n i b i l i t ym a t r i xo ft h ed e c i s i o n i n f o r m a t i o ns y s t e m ，s oh o wt or e d u c et h es p a c ed e m a n do fa l g o r i t h mi sai m p o r t a n t p r o b l e mt or e s o l v e f u r t h e rm o r e ，h o wt oi n t e r g r a t er o u g hs e t st h e o r yw i t ho t h e rd a t a m i n i n gt e c h n i q u e sa n do t h e rs o f tc o m p u t i n gt h e o r yi sav a l u a b l er e s e a r c hd i r e c t i o n k e y w o r d s ：d a t am i n i n g ，r o u g hs e tt h e o r y ，f e a t u r es e l e c t i o n ，r e d u o t ，f e a t u r e c o r r e l a t i o ni n d e x ，f e a t u r ed e p e n d e n c y ，c o n t i n u o u sf e a t u r ed i s c r e t i z a t i o n 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属于西j e 工业大学。学校有权保留并 向国繇有关部门或机构送交论文的复印件和电子版。本人允许论文被查 阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北工业大学。 住密论文待解密后适用本声明。 学位论文作者签名：。5 k 鹤一指导教师签名：饵算叁睦 山帅年d 月0 7 曰 护莎年月功日 。，7 二一- - 西北工业大学 学位论文原刨性声明 秉承学校严谨的学风和优怠的科学遭德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本论文不包含任何其 他个人或集体已经公开笈袭或撰写过的研究成果，不包古本人或他人已 申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均己在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任 学位论文作者签名： 击。6 年d 月j 7 日 第一章引言 第一章引言 数据挖掘是信息技术自然演化的结果。自2 0 世纪6 0 年代以来，数据管理和 信息技术已经从原始的文件系统处理演化到复杂的、功能强大的数据库系统。在 过去的3 0 年里，计算机硬件技术稳定的、令人吃惊的进步导致了功能强大的计算 机、数据收集设备和存储介质的大量需求。这些技术极大的推动了数据库和信息 产业的发展，使得大量数据库和信息存储用于事务管理、信息检索和数据分析。 随着数据库的大量应用，在各个行业都积累了十分丰富的数据，互联网的广泛应 用更加快了数据量增长的步伐。但是，这些海量数据绝大部分都没有提炼成为知 识，“数据丰富，知识贫乏”的现象广泛存在。j o h n n a i s b e t t 在大趋势一书中曾 经这样感叹：“w ea r ed r o w n i n gi ni n f o r m a t i o n , b u ts t a r v i n gf o rk n o w l e d g e ”。面对快 速增长的海量数据。需要有一个强有力的工具来理解，并从中提取有用的知识， 用以帮助企业决策、科学研究等，数据挖掘因此应运而生。 1 1 数据挖掘概述 数据挖掘就是从大量数据中发现潜在的规律，提取有用知识的方法和技术， 又被称为数据库知识发现( 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 o ) 。数据挖掘是一 个交叉学科领域，受数据库技术、统计学、机器学习、可视化和信息科学等多个 学科影响。 一般而言，数据挖掘的过程通常由以下几个步骤构成( 如图1 所示) ： i ) 数据清理( 消除具有噪音和不一致的数据) ； 2 ) 数据集成( 多种数据源整合) ； 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) ； 4 ) 数据变换( 对数据进行变换或整合成适于挖掘的形式，如通过汇总或聚集 操作) ： 5 ) 知识抽取( 基本步骤，使用智能方法提取数据模式) ： 6 ) 模式评估( 根据某种相似性度量，识别表示知识的真正有意义的模式) ； 1 两北工业大学博士学位论文基于粗糙集理论的数据挖掘算店研究 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 。 图1 数据挖掘流程图 数据挖掘过程是一个和领域相关的交互过程，需要领域专家的参与。一般而 言，一种数据挖掘算法不可能完全适合各种挖掘问题的需要，一种算法可能只适 合特定的问题。在数据挖掘的各个阶段，常用的技术有数据清理、特征选择、连 续属性离散化、分类算法、聚类算法、关联规则等。 1 1 1 数据清理 现实世界的数据往往是“脏”的、不完整的、不一致的。通过数据清理，可 以填充空缺的数据，识别孤立点、消除噪音。 对于缺失的数据，一般的做法有：忽略含有缺失数据的实例所对应的所有数 据；人工填写缺失数据( 一般由领域专家完成) ：使用全局常量填充空缺值：使 用属性平均值代替缺失数据；使用回归推导等方法计算最可能的值以代替缺失数 据等。 对于噪声数据，一般采用数据平滑技术进行处理。数据平滑通常使用的方法 有：分箱( b i n n i n g ) 、聚类、回归等。 第一章引言 1 1 2 特征选择 用于数据分析的数据可能包含数以百计的属性，其中大部分属性与挖掘任务 不相关。无关或者冗余属性的存在会致使所用的数据挖掘算法无所适从，从而导 致数据挖掘的结果质量下降。此外，无关或者冗余属性的存在增加了数据量，会 减缓数据挖掘的进程。特征选择是解决无关、冗余属性问题的有效方法。 特征选择是数据挖掘中的一项重要技术，在数据准备和预处理阶段发挥着重 要作用。特征选择的目的是找到满足特定标准的最小的属性子集。标准通常是错 误率，不一致率，信息熵，依赖程度等【l i ua n dm o t o d a ，1 9 9 8 。特征选择算法和 后续的学习算法之间的关系可以归为两类：w r a p p e r 方法和f i l t e r 方法 k o h a v ia n d j o h n ，1 9 9 7 。在w r a p p e r 方法中，特征选择算法利用学习算法评估特征选择的效 果，选出具有最好学习效果的一组属性，f i l t e r 方法则不考虑学习算法，利用自己 的标准进行特征选择，选择完毕再使用学习算法。一般来说，w r a p p e r 方法的效果 要好于f i l t e r 方法，但是时间复杂度也高于f i l t e r 方法。 在特征选择算法中，搜索算法起着重要的作用。搜索算法可以用搜索方向( 前 向，后向。双向，随机) ，搜索方式( 穷尽式，启发式，非确定式) 及评价方式( 精确 度，一致性，依赖度等) 等三个方面来分类。 使用最为广泛的是各种各样的贪心算法。在进行搜索时，总是选择评估标准 最大化的属性，直到达到标准为止，而不进行回溯。其策略是作局部最优选择， 期望由此导致全局最优解。在实践中，贪心算法是有效的，并且在大多数情况下 可以逼近最优解。 粗糙集理论 p a w l a k ，1 9 9 1 的核心概念之一约简，也是特征选择的一种重 要方法。除此之外，还有很多特征选择算法，例如神经网络方法、遗传算法、分 形、小波方法等 l i ua n dm o t o d a ，1 9 9 8 。这些方法各有特色，但到目前为止，还 没有一个公认的绝对好的方法。 1 1 3 连续属性离散化 数据挖掘中很多方法要求属性是离散的，特别是粗糙集方法只能处理离散的 西北工业大学博士学位论文基于粗糙集i 甲论的数据挖掘算法研究 属性，而实际数据中有很多属性是连续的，因此有必要对连续属性进行离散化。 离散化的任务是把连续属性的取值范围或取值区间划分为若干个数目不太多的小 区间，用区间标号代替实际的数值。目前的离散化方法主要有归并和划分两种策 略：归并策略的思想是把初始属性的每个取值当作一个离散的属性值，然后逐个 反复合并相邻的属性值，直到满足终止条件：划分策略的思想是把连续属性的整 个取值区间当作一个离散属性值，然后对该区间进行反复的划分，直至满足终止 条件。基于这两种思想产生了许多不同的离散化方法。 根据是否利用类信息，离散化方法一般可以分为有监督和无监督的两种类型 d o u g h e r t y ，k o h a v ia n ds a h a m i ，1 9 9 5 】。如果考虑概念类信息的离散化，又可分 为动态离散化和静态离散化两种方法，主要的根据是划分在分类的过程前还是在 分类的同时进行。根据是对所有连续属性同时离散化还是对单个属性单独离散化， 又可分为全局方法和局部方法。有监督的连续属性离散化方法又分为动态离散化 和静态离散化两种。动态算法在学习过程中将连续属性离散化，例如c 4 5 算法； 静态算法就是在学习算法开始之前先将连续属性离散化，不依赖于具体的算法。 常用的离散化方法有等距离离散化、等频度离散化、自适应方法、信息熵方 法、贝叶斯方法等。 布尔推理算法 s k o w r o na n dn g u y e n ，1 9 9 5 是s k o w r o n 和n g u y e n 根据粗糙集 理论和布尔推理提出的一种离散化算法，把离散化问题转化成布尔推理问题，从 而可以利用各种布尔函数化简技术寻找最优划分。这是一种全局有监督算法。 上述方法应用于同样的数据集，其离散化效果各不相同：而同样的方法用于 不同的数据集，结果差异也很大。没有哪一种方法是绝对最好的。评价个离散 化方法的好坏，通常以一致性、知识依赖度和冲突率作为评价的标准。 l - 1 4 分类算法 数据分类是指按照分析对象的属性、特征建立不同的组类来描述事物。数据 分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别 的精确描述。这种类别通常由分类规则组成，在使用上，既可以用此模型分析已 有的数据，也可以用来对未来的数据进行分类和预测。分类技术解决问题的关键 4 第一苹日l 言 是构造分类器。 分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有决策树方法、 贝叶斯方法、神经网络方法、统计学习理论、遗传算法等，不同的方法适用于不 同特点的数据。 分类方法的评估标准： 准确率：模型正确预测新数据类标号的能力。 速度：产生和使用模型花费的时间。 健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。 伸缩性：对于给定的大量数据，有效地构造模型的能力。 可解释性：学习模型提供的理解和观察的层次。 l 决策树分类 决策树( d e c i s i o nt r e e ) 又称为判定树，是应用最广的归纳推理算法之一，它搜 索一个完整表示的假设空间，是一种逼近离散值函数的方法。其主要代表算法有 i d 3 ，a s s i s t a n t ，c 4 5 等。 决策树的每个内部结点代表对某个属性的一次测试，每条边代表一个测试结 果，叶结点代表某个类或者类的分布( c l a s sd i s t r i b u t i o n ) ，最上面的结点是根结点。 决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变 量做决策树。 构造一个决策树分类器通常分为两步：树的生成和剪枝。树的生成采用自上 而下的递归分治法。如果当前训练例子集合中的所有实例是同类的，构造一个叶 节点，节点内容即是该类别。否则，根据某种策略选择一个属性。按照该属性的 不同取值，把当前实例集合划分为若干子集合。对每个子集合重复此过程，直到 当前集中的实例是同类的为止。剪枝就是剪去那些不会增大树的错误预测率的分 枝。经过剪枝，不仅能有效地克服噪声，还能使树变得简单，容易理解。生成最 优的决策树是n p 问题。目前的决策树算法通过启发式特征选择策略来解决问题。 决策树的代表算法是i d 3 及其后续版本c 4 5 q u i n l a n ，1 9 9 3 ，该方法采用信 息熵增益作为选择属性的依据。其他算法还有c a r t b r e i m a n ，f r i e m a n ，o l s h e na n d s 两北工业大学博士学位论文基于租糙集理论的数据挖掘算法研究 s t o n e ，1 9 8 4 】，s l i q m e h t a ，a g r a w a la n dr i s s a n e n ，1 9 9 6 等。 与其它分类算法相比，决策树有以下优点： ( 1 ) 速度快：计算量相对较小，且容易转化成分类规则。只要沿着树根向下 一直走到叶，根据沿途的分裂条件就能够唯一确定一条分类的谓词。 ( 2 ) 准确性高：挖掘出的分类规则准确性高，便于理解，决策树可以清晰地 显示哪些字段比较重要。 决策树的缺点是随着数据复杂性的提高，分支数增多，管理起来很困难。 2 贝叶斯分类 贝叶斯分类是基于贝叶斯定理的一种统计学分类方法，即利用贝叶斯公式将 先验信息和样本信息综合，得到后验信息以预测类成员关系的可能性，例如给定 样本属于一个特定类的概率。 对分类算法的比较研究不难发现，朴素贝叶斯分类算法可以与决策树和神经 网络分类算法媲美。朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它 属性的值( 类条件独立) ，把从训练样本中计算出的各个属性值和类别频率比作 为先验概率，直接利用贝叶斯公式进行预测，计算出要预测的实例对各个类别的 条件概率值，选取概率值最大的类别作为预测值。理论上讲，与其他所有分类算 法相比，贝叶斯分类具有最小的出错率。然而实践中并非总是如此。这是由于对 其应用的假定( 如类条件独立性假设) 的不准确以及缺乏可用的概率数据造成的。 朴素贝叶斯分类算法的类条件独立假设虽然简化了计算，但忽略了实际情况 下各种变量之间依赖存在的可能性。贝叶斯信念网络( b a y e s i a nb e l i e f n e t w o r k ) 说明 联合条件概率分布，允许在变量的子集间定义类条件独立性，提供了一种因果关 系的图形，可以在其上进行学习。 贝叶斯信念网络由两部分构成：第一部分是有向无环图 h e c k e r m a n ，1 9 9 7 ， 其每个节点代表一个随机变量，而每条弧代表变量间的概率依赖；第二部分是每 个属性的条件概率表。图模型能有效地表示大的变量集合的联合概率分布，从而 适合用来分析大量变量之间的相互关系，利用贝叶斯公式的学习和推理功能，实 现预测、分类等数据挖掘任务。因为关于变量组x 的贝叶斯网络表示了x 的联合 6 苎二兰! ! 重 概率分布，所以，一旦网络及其参数确定，原则上可以用它来推断任何感兴趣的 概率。贝叶斯信念网络也是一种适合处理不确定性知识问题的知识表示方法，因 为它可以从部分概率中进行推导。 构造贝叶斯信念网络需要进行网络结构和网络参数两部分的学习。为了建立 贝叶斯网络，首先确定问题的变量组，接着通过对变量之间条件独立性的分析， 建立一个表示这些变量之间的关系的有向无环图，最后需要对变量指派局部概率 分布。在离散的情形，需要为每一个变量的各个父节点的状态指派一个分布。但 是获得最优的结构和参数都是n p 问题。因此存在许多启发式方法 1 - i e c k e r m a n ， m a m d a n i ，a n dw e l l m a n ，1 9 9 5 ；s p i r t e sa n dm e e k ，1 9 9 5 。 关于离散变量的任意贝叶斯网络的精确推断也是n i 难题 c o o p e r ，1 9 9 0 1 。即 使是近似推断，比如使用m o n t e c a r l o 方法也是n p 难的 d a g u ma n dl u b y ，1 9 9 3 1 。 其主要原因是任意贝叶斯网络中存在环路( 不计较弧的方向) ，这使得推断难以 实施。不过在许多实际应用中，只要网络结构足够简单，或者可以在不牺牲太多 准确性的前提下将结构简化，则推理仍可有效地进行 s a u l ，j a a k k o l aa n dj o r d a n ， 1 9 9 6 ；j a a k k o l aa n dj o r d a n ，1 9 9 6 ：d a r w i c h ea n dp r o v a n ，1 9 9 6 】。 3 神经网络分类 神经网络最早由心理学家和神经生物学家提出，瞽在寻求开发和；贝| | 试神经的 计算模拟。粗略地说，神经网络是一组连接的输入输出单元，其中每个连接都与 一个权相关联。在学习阶段，通过调整神经网络的权，使其能够预测输入样本的 正确类标号来学习。 神经网络对于逼近实数值、离散值或向量值的目标函数提供了一种普遍适用 的方法。神经网络对于训练数据中的错误健壮性很好，特别是对于某些类型的问 题，如学习解释复杂的现实世界中的传感器数据，神经网络是目前已知的最有效 的学习方法之一。神经网络算法的代表算法有多层神经网络的后向传播算法( b p ) r u m e l h a r t ，h i n t o na n dw i l l i a m s ，1 9 9 6 1 、h o p f i e l d 神经网络模型等。 神经网络的主要缺点是其知识的表示。用加权链连接单元的嘲络表示知识很 难被人理解。这激发了提取隐藏在训练的神经网络中的知识，并象征地解释这些 知识的研究。近年来许多学者提出了从神经网络中提取规则的方法，典型的如 7 西北工业大学博士学位论文基于粗糙集理论的数据挖掘算法研究 k b a n n t o w e l la n ds h a v l i k ，1 9 9 4 等。主要可以分为三类方法：分解法、学习法 以及这两种的折衷方法。 分解提取方法的最大特点是对神经元网络内部的单个节点( 隐含和输出) 所表 示的概念进行解释，从每个节点中提取的规则是由与此节点相连的诸输入节点来 表示的，典型的分解算法有s u b s e t 及其改进m o f n t o w e l la n ds h a v l i k ，1 9 9 4 ， k t f u ，1 9 9 3 和r u l e x a n d r e w s ，d i e d e r i c ha n dt i c k l e ，1 9 9 6 。 学习提取法的基本思想是将训练后的神经元网络看成一个黑箱，而把规则抽 取过程看成是一个学习过程，其中所学的目标概念由神经元网络函数计算得到， 而其输入变量则为神经元网络的输入特征组成。学习提取方法主要利用符号学习 算法作为学习工具，而利用神经元网络作为学习例子生成器，主要代表方法有 t r e p a n c r a v e na n ds h a v l i k ，1 9 9 5 $ 1 1r l c r a v e na n ds h a v l i k ，1 9 9 4 算法。 4 统计学习理论 统计学习理论( s t a t i s t i c a ll e a r n i n g ) 的研究主要集中在两点上：表示问题和泛化 问题。表示问题的关键是非线性空间的线性表示。泛化问题则是对给定的样本集 合通过算法建立模型，判定该模型对问题实际为真的程度。将线性不可分问题转 化为线性可分问题的关键是寻找一个映射，将样本集映射到特征空间，使其在特 征空间线性可分。 波兰数学家v a p n i k 首先提出的支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 理 论 v a p n i k ，1 9 9 8 ：v a p n i k ，2 0 0 0 较好地解决了以上两个问题，因而成为统计学习 的代表方法。它基于结构风险最小化归纳法( s t r u c t u r a lr i s km i n i m i z a t i o ni n d u c t i v e p r i n c i p l e ) ，通过在特征空间构建具有最大间隔的最佳超平面，得到两类问题的划 分准则，使得期望风险的上界达到最小。由于支持向量机算法是一个凸优化问题， 因此局部最优解一定是全局最优解。而且s v m 的复杂度和实例集的维数无关。支 持向量机在解决小样本、非线性极高维模式识别问题中表现出许多特有的优势， 并能够推广应用到函数拟合等其它数据挖掘问题中。 s v m 的基本思想是通过某种事先选择的非线性映射将输入向量映射到一个高 维特征空间，在这个空间中构造最优分类超平面。在高维特征空间中构造最优超 兰二皇! ! 妻 平面，只需要计算特征向量与特征空间中向量的内积，然后使用某种核函数在原 空间计算就可以了，从而克服了维数困难。通过选用不同的核函数，可以构造输 入空间中不同类型的非线性决策面的学习机。 对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由 此确定该区域中未知样本的类别。 5 遗传算法分类 遗传算法 j o n e ，1 9 9 9 这个术语于1 9 6 7 年首次出现，1 9 7 5 年j h h o l l a n d 比 较全面地介绍了遗传算法，随后遗传算法成为人工智能研究领域的一个热点。遗 传算法开始会创建一个由随机产生的规则组成的初始群体，然后根据适者生存的 原则，形成由当前群体中最适合的规则组成的新群体，以及这些规则通过交叉变 异等遗传操作而产生的后代。典型情况下，规则的适合度( f i t n e s s ) 用它对训练样本 集的分类准确率评估。由原始规则群体产生新的规则群体的过程反复执行，直至 规则群体进化至其中每个规则都满足预先指定的适合度阈值。遗传算法一般具有 以下几个特点： 1 ) 智能式搜索：在适应度函数的约束下有指导地搜索，“优胜劣汰”，逐步 逼近目标。 2 ) 渐进式优化：模仿生物进化的遗传、杂交和变异等，通过多次迭代，逐渐 得出最优解。 3 ) 全局最优解：由于遗传算法一般采用杂交变异等操作，扩大了搜索范围， 因此从理论上讲，有跳出局部最优、得到全局最优的可能。 4 ) 黑箱结构：一般只要完成编码和适应度选择，其余的遗传、杂交变异等操 作可以自动完成，可看作只考虑输入输出的黑箱系统。 1 1 5 聚类分析 与分类相对，聚类是一种无监督的数据挖掘方法( u n s u p e r v i s e dl e a r n i n g ) ：设 想要求对一个数据对象的集合进行分析，与分类不同的是，要划分的类是未知的。 聚类( c l u s t e r i n g ) 就是将数据对象分组成为多个类或者簇( c l u s t e r ) ，同一簇中的对象 9 西北工业大学博士学位论文基于粗糙集理论的数据挖掘算法研究 之间具有较大的相似度，而不同簇中的对象差别较大。相异度是根据描述对象的 属性值来计算的。距离是经常采用的度量方式。直观的说，最终形成的每个聚类， 在空间上都是一个稠密的区域。在应用中，通常将一个簇中的数据对象当作一个 整体来对待。 大体上，聚类算法可以分为划分聚类、层次聚类等。 划分聚类是按照某种划分准则，将数据集划分成指定数目的k 个簇。其中全 局优化方法是穷尽所有的k - 划分空间寻求某种准则的最优划分。启发式方法是从 随机k 划分出发，通过迭代操作不断地调整对象归属，直到收敛( 前后两次划分 不变) 。代表性的启发式方法有k - m e a n s 和k - m e d o i d s 算法。 层次聚类又分为自底向上的聚合法和自顶向下的分治法两种。聚合法把每个 样本看做一个单独的簇，然后合并这些簇为越来越大的簇，直到所有的对象都在 一个簇中，或者满足某个预先设定的条件为止。绝大多数聚类算法属于这一类， 它们只是簇间相似度的定义有所不同。分治的层次聚类策略和聚合法相反，它首 先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成 一簇，或者某个预先设定的终止条件被满足。 评价聚类算法一般有以下几个标准： 1 ) 良好的可伸缩性，可适用于不同规模的数据集。 2 ) 能应付不同的数据类型。 3 ) 能够发现不同类型的聚类。 4 ) 使对专业知识的要求降到最低。 5 ) 能应付脏数据。 6 ) 对于数据不同的顺序不敏感。 7 ) 模型可解释，可使用。 1 1 6 集成学习 集成学n ( e n s e m b l el e a r n i n g ) 起源于对神经细胞工作方式的假设：信息加工是 由神经集合体共同完成的。1 9 9 5 年，s c h a p i r e 证明一个关键定理，由此奠定了集 1 0 第一苹引言 成学习的理论基础，即：一个学习方法可以提升为强学习方法的充要条件是其为 弱可学习。这个定理证明，多个弱分类器可以集成为一个强分类器。 b a g g i n g b r e i m a n ，1 9 9 6 1 和b o o s t i n g ； f r e u n da n ds e h a p i r e ，1 9 9 7 是近来研究提高分 类器学习系统预测能力的方法，也是集成学习中最具代表性和应用前景的方法。 b a g g i n g 和b o o s t i n g 都是通过组合多个弱分类器来得到一个强分类器，二者的主 要区别是取样的方式不同。b a g g i n g 采用的是均匀取样，而b o o s t i n g 根据错误率 取样，因此b o o s t i n g 的分类精度要优于b a g g i n g 。 近年来，集成学习方法已得到较为广泛的实验和应用，尤其是在数据挖掘方 面的前景日趋看好。 1 1 7 关联规则 在数据挖掘的知识模式中，关联规则是比较重要的一种。关联规则的概念由 a g r a w a l 等于1 9 9 3 年提出 a g r a w a l ，i m i e l i n s k ia n ds w a m i ，1 9 9 3 ，关联规则模式 属于描述型模式，发现关联规则的算法属于无监督学习。关联规则是形如；y 的 蕴涵式，其中x 、y 是项集且x n y = a 。关联规则的兴趣度通常用规则的支持度 和置信度两个指标来度量。关联规则的支持度是指规则为真的相关实例占所有实 例的百分比：在数据库中如果s 的实例同时包含x 和y ( 或s 的实例包含x u y ) 则关联规则x j y 的支持率为s 。关联规则的置信度是指规则为真的相关实例 占包含项集x 的实例的百分比：若包