（系统工程专业论文）基于神经网络的分类数据挖掘属性选择和规则抽取研究.pdf

中文摘要 数据挖掘是一门从大规模数据中提取有用信息和知识的新兴技术，分类是数 据挖掘的一项重要内容。面对大规模、高维的数据，如何建立有效的，可扩展 的分类数据挖掘算法是数据挖掘研究的重要方向之一。 在分类数据挖掘中，属性选择和规则抽取是两个最重要的工作。神经网络是 数据挖掘的一个重要工具，而现有的神经网络属性选择方法必须对全部属性进行 训练和裁剪，造成网络规模过大，训练量大，效率低下的缺陷，为了克服这些缺 陷，必须提出新的方法。 本文以神经网络为主要研究方法，并结合模糊逻辑技术，对分类数据挖掘中 的属性选择和规则抽取两个问题提出了一些有效的算法，具体的研究工作如下： 提出了一种基于输入输出关联法排序的r b f 神经网络属性选择方法。由于属 性选择是一个n p 一姒r d 问题，现有的属性选择方法计算过于复杂，效率低下。本 文提出一种新的属性选择方法。该方法先用输入输出关联法对所有属性进行重要 性排序，然后根据属性重要性次序用r b f 神经网络进行属性选择。该方法避免了 现有的神经网络降维方法必须对全部属性进行训练和裁剪的弊端，大大提高了属 性选择的效率。 提出了一种可分性判据排序的r b f 神经网络属性选择方法。该方法先用可分 性判据计算每个属性的重要度，并对其进行排序，然后根据属性重要性次序用 r b f 神经网络进行属性选择。 提出了一种基于降维的概率神经网络模糊规则抽取方法。该方法先用上面的 属性选择方法从原始属性集中选择部分最重要的属性，然后对这部分属性进行模 糊化处理，接着用概率神经网络进行模糊规则抽取。该方法通过属性选择减少了 神经网络训练规模，避免了对神经网络进行节点裁剪，从而大大提高了规则抽取 的效率。并且，用模糊规则来表现知识，规则易于理解，规则精度也有所提高。 关键词： 数据挖掘神经网络属性选择规则抽取 a b s t r a c t d a t am i n i n gi san e wt e c h n o l o d yt h a ti su s e dt oe x t r a c tu s e f u li n f o r m a t i o na n d k n o w l e d g ef r o ml a r g ed a t a b a s e s c l a s s i f i c a t i o ni s a ni m p o r t a n tt a s ko fd a t am i n i n g f a c i n gt h em a s s i v ev o l u m ea n dh i 曲d i m e n s i o n a ld a t ah o w t ob u i l de f f e c t i v ea n d s c a l a b l ea l g o r i t h mf o rd a t am i n i n gi so n eo f r e s e a r c hd i r e c t i o n so f d a t am i n m i n g a t t r i b u t i o n ss e l e c t o na n dr u l ee x t r a c t i o na r et h em o s ti m p o r t a n tt o p i c si nd a t a m i n i n g a n d n e u r a ln e t w o r ki so n eo f t h ei m p o r t a n tm i n i n gt o o l s h o w e v e r , t r a d i t i o n a ln e u r a ln e t w o r km e t h o d sr e q u i r et r a i n i n g a l la t t r i b u t i o n s ， w h i c hc a u s e st h ed e f i c i e n c i e so f e x c e s s i v el a r g es i z eo f n e t w o r ka n dl o w e f f i c i e n c y t h i s p a p e rp r e s e n t s s o m en e wm e t h o d so fa t t r i b u t i o n ss e l e c t i o na n dr u l e e x t r a c t i o ni nd a t am i n i n gu s i n gn e u r a ln e t w o r ka n df u z z yl o g i c w h i c ha r el i s t e da s f o l l o w s am e t h o do fr b fn e u r a ln e t w o r ka t t r i b u t i o n ss e l e c t i o nb a s e do nd a t a i n p u t o u t p u tc o r r e l a t i o nr a n k i n gi sp r e s e n t e di n t h i s p a p e r t h i sm e t h o dr a n k st h e a t t r i b u t i o n si nt h eo r d e ro fd a t ai n p n t - o u t p u tc o r r e l a t i o na n ds e l e c t st h ea t t r i b u t i o n s u s i n gr b fn e u r a ln e t w o r kb a s e do nt h ea t t r i b u t i o n sr a n k i n g i ta v o i d st h ed e f i c i e n c y o ft r a d i t i o n a ln e u r a ln e t w o r km e t h o d s n e e d i n g t ot r a i na l la t t r i b u t i o n s ，w h i c hg r e a t l y i m p r o v e s t h ee f f i c i e n c yo f a t t r i b u t i o n ss e l e c t i o n a n o t h e rm e t h o do fr b fn e u r a ln e t w o r k sa t t r i b u t i o n ss e l e c t i o nb a s e do na s e p a r a b i l i t yc r i t e r i o nr a n k i n gi sp r e s e n t e di nt h i sp a p e r i tr a n k st h ea t t r i b u t i o n su s i n g t h es e p a r a b i l i t yc r i t e r i o nf o rt h ea t t r i b u t i o n sa n ds e l e c t e st h ea t t r i b u t i o n su s i n gr b f n e u r a ln e t w o r kb a s e do nt h ea t t r i b u t i o n sr a n k i n g an e wr u l ee x t r a c t i o nm e t h e di sp r e s e n t e di nt h i sp a p e r i nt h i sm e t h o d ，a p a r to f i m p o r t a n ta t t r i b u t i o n s a r ef a s ts e l e c t e df r o mp r i m ea t t r i b u t i o n s u s i n gt h e a b o v e m e t h o d s a t i e rf u z z i n e s so ft h e s ei m p o r t a n ta t t r i b u t i o n s t h er u l ee x t r a c t i o ni sc a r r i e d o u t u s i n g a p r o b a b l e n e u r a ln e t w o r k t h i sm e t h o dg r e a t l yr e d u c e st h en e u r a l n e t w o r k ss i z et h r o u g ht h ea t t r i b u t i o n ss e l e c t i o n , a n ds ol a r g e l y i m p r o v e s t h ee f f i c i n c y o ft h er u l ee x t r a c t i o nc o m p a r e dw i t he x i s t i n gs i m i l a rm e t h o d s a tt h es a m e t i m e ，t h e k n o w l e d g ee x t r a c t e d c a l lb ee a s i l yu n d e r s t a n d e da n dt h er u l e a c u u r a c y i sa l s o i m p r o v e d k e yw o r d s ：d a t a m i n i n g ，n e u r a ln e t w o r k ，a t t r i b u t i o n ss e l e c t i o n ，r u l e e x t r a c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 京签字日期：三。玉年卢月易日 学位论文版权使用授权书 本学位论文作者完全了解墨洼盘堂有关保留、使用学位论文的规定。 特授权墨洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 妄之 导师签名 参段 签字日期：酗3 年己月b 日 签字日期：少哆年，上月夕口日 至望奎兰堡主堂垡笙苎 兰= 量些笙 第一章绪论 本章首先阐明了本文所选课题的研究背景及其所具有的研究价值，接着对分 类数据挖掘的基本概念进行了简要介绍，然后着重评述了分类数据挖掘所用的工 具，最后综述了本文的主要研究工作和创新点。 1 1 本文的选题背景和研究意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非 常方便地获取和存储大量的数据，在这大量的数据背后隐藏着许多重要的信息。 面对大规模的海量的数据，传统的数据分析工具( 如管理信息系统) 只能进行一 些表层的处理( 如查询、统计等) ，而不能获得数据之间的内在关系和隐含的信 息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地自 动地把数据转换成有用信息和知识的技术和工具，这种对强有力数据分析工具的 迫切需求使得数据挖掘技术应运而生。数据挖掘工具能够对将来的趋势和行为进 行预测，从而很好地支持人们的决策，比如，经过对公司整个数据库系统的分析， 数据挖掘工具可以回答诸如“哪个客户对我们公司的邮件推销活动最有可能作 出反应，为什么? ”等类似的问题。有些数据挖掘工具还能够解决一些很消耗人 工时间的传统问题，因为它们能够快速地浏览整个数据库，找出一些专家们不易 察觉的极有用的信息。 数据挖掘是多门学科和多门技术相结合的产物，也是一个非常年轻而又活跃 的研究领域。在促进数据挖掘诞生、发展、应用的众多原因中，主要有4 种，即 超大规模数据库的出现、先进的计算机技术、经营管理的实际需要和对这些数据 的精深计算能力。从经营管理角度出发，进入2 1 世纪以后，全球经济一体化的 进程日益加快，企业所面临的市场竞争压力日趋严重，企业经营管理者特别是决 策者希望e 够从企业积累的大量历史数据中找到应对日趋严重的竞争压力良方， 希望能够从这些数据中找到经营管理中问题的根本原因，能够快速从大量数据中 挖掘出对经营管理有用的信息，以应对瞬息万变的市场压力。更重要的是，当前 社会进入信息时代，特别是i n t e r n e t 的迅猛发展，使得数据以指数速率增长， 由于这些数据十分繁杂，要从中发现有价值的信息或知识达到为决策服务的目的 这是十分艰巨的任务，为达此目的的研究统称为数据挖掘。因此可以说数据挖掘 天津大学硕士学位论文 第一章绪论 技术是一个对管理决策者提供决策支持的有力工具。 在数据挖掘中，分类是一种重要的数据分析技术，它可以用于提取描述重要 数据类的模型和预测未来的数据趋势。数据挖掘算法的工作方法是通过分析已知 分类信息的历史数据总结出一个预测模型。分类问题在人工智能、机器学习以及 模式识别等领域已经得到了广泛的研究，并已产生了许多的分类方法。但是，面 对大规模的海量的数据，传统的分类算法在可扩展性和高效率性等方面面临大量 的问题。因此，近年来在“如何处理大规模数据”、“如何使获得的分类知识更易 于为人所理解及应用”等问题的激发下，分类问题已成为数据挖掘领域的一项重 要研究内容n ，获得了更加广泛的、深入的研究。 现实中的很多问题都可以转化为分类问题，因而分类数据挖掘技术的潜在应 用十分广泛，从政府管理决策、商业经营、科学研究和工业企业决策支持等各个 领域都可以找到分类技术的用武之地。例如，可以建立一个分类模型，对银行的 贷款客户进行分类，以降低贷款的风险；也可以通过建立分类模型，对工厂的机 器运转情况进行分类，用来预测机器故障的发生。因此，进行分类数据挖掘技术 的迸一步研究具有重要的理论意义和实际应用价值。 在分类数据挖掘中，属性选择和规则抽取是两个最重要的工作。随着数据挖 掘研究的深入和在实际中的应用，数据挖掘的规模也越来越大了，这主要表现在 两个方面：一个是数据样本个数越来越大了，另一个则是数据属性维数越来越高 了。在原始数据中，包含有大量冗余和不相关的属性，这些属性对挖掘结果影响 不大。如果用原始数据进行挖掘将会导致挖掘时间长，效率低下，得出来的规则 也难于理解，这就给数据挖掘提出了一个挑战。如何从大量的原始数据属性中选 择部分重要的对分类效果影响大的属性集就成为了数据挖掘中的一个重要研究 课题，即属性选择问题。 在分类数据挖掘中，最终挖掘出来的结果是用i f ，t h e n 表示出来的分类规 则。因此如何设计出高效的算法，从数据集中得出精度高，可理解性强，高鲁棒 性的规则就成为了分类数据挖掘中最重要也是最关键的步。 鉴于以上认识，在国家自然科学基金的资助下，本文对分类数据挖掘中的属 性选择和规则抽取问题进行了研究，为构建可扩展的、高鲁棒性的、可理解性强 的、高效的数据挖掘分类算法做出了自己的努力。 1 2 数据挖掘概论 数据挖掘是2 0 世纪9 0 年代兴起的一项新技术，它是知识发现的关键步骤 国内外学术界和企业界都非常重视对数据挖掘技术和软件工具的研究和开发。 天津人学硕士学位论文第一章绪论 面对信息社会中数据和数据库的爆炸式增长，人们分析数据和从中提取有用 信息的能力远远不能满足实际需要。所以迫切需要一种能够智能地自动地把数据 转换成有用信息和知识的技术和工具。数据库管理系统和人工智能中的机器学习 两种技术的发展和结合促成了知识发现( k d d ，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 ) 这一新技术的产生。1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合 会议的专题讨论会上首次提出了k d d 。它是一门交叉性学科，内涵极为广泛，理 论和技术难度很大，所以使当时针对大型数据库的k d d 技术一时还难于满足应用 需要。于是1 9 9 5 年，在美国计算机年会( a c m ) 上提出了数据挖掘( d a t am i n i n g ) 概念。也有一些文献把数据挖掘技术称为知识抽取( k n o w l e d g ee x t r a c ti o n ) 、数 据考古学( d a t aa r c h a e o l o g y ) 、数据捕捞( d a t ad r e d g i n g ) 等等。多数人认为数 据挖掘是k d d 过程的关键技术，从而不加区分的使用知识发现和数据挖掘两个术 语。 1 2 1 数据挖掘定义 数据挖掘( d a t am i n i n g ，d m ) 的定义与另一个常用的术语“数据库知识 发现”( 常简称为知识发现，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 s ，k d d ) 密切 相关。一种观点。1 1 认为知识发现是从大规模数据中发现知识的整个过程，而数 据挖掘只是这个过程的一个重要步骤；另一种观点“则认为两者是等价的概念， 均指发现知识的全过程。本文采用文献 7 的观点，认为数据挖掘从理论和技术 上继承了知识发现领域的成果，同时又有着独特的内涵。数据挖掘更着眼于设计 高效的算法以达到从巨量数据中发现知识的目的。 因此，数据挖掘的具体定义为“数据挖掘是一个从大型数据库中抽取隐含的、 事先未知的、具有潜在有用的信息或知识的非平凡过程”。其流程图如图1 一l 所 示。 天津大学硕士学位论文 第一章绪论 数 据 预 1 - 2 2 挖掘系统的分类 图卜i 数据挖掘过程 数据挖掘是一门交叉学科，受多个学科的影响，包括数据库系统、统计学、 机器学习、可视化和信息科学等。此外依赖于所用的数据挖掘方法，以及可以使 用的其他学科技术，如神经网络、模糊逻辑、粗集理论、知识表示、归纳逻辑程 序设计或高性能计算等。 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同 类型数据挖掘系统，这样就需要对数据挖掘系统给出一个清楚的分类。从不同的 角度出发，对数据挖掘系统有几种分类，主要是根据挖掘的数据库的种类、根据 得到的知识分类和所使用的技术分类“3 。 ( 1 ) 根据数据库分类数据挖掘所基于的数据库类型有：关系型、事务型、 面向对象型、推论型( d e d e c t i v e ) 、空间型、时序型、多媒体型、异质型 ( h e t e r p g e n e o u s ) 、主动型( a c t i v e ) 、遗留型( 1 e g a c y ) 、文本挖掘和基于网络信 息的挖掘等。 ( 2 ) 根据得到的知识分类包括关联规则、特征规则、分类规则、判别 ( d i s c r i m i n a n t ) 规则等的挖掘和聚类、演变( e v o l u t i o n ) 分析、偏差( d e v i a t i o n ) 分析、孤立点分析和相似性分析等，此外根据所挖掘的知识的抽象层次进行划分， 可以包括原始层知识( 在原始数据层) 、多层次知识和高层次知识的数据挖掘。 ( 3 ) 根据所采用的技术分类常用的数据挖掘技术有 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的非 线性预测模型。可以完成分类、聚类和特征挖掘等任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产 生规则，典型的决策树方法有分类回归树( c a r t ) 、c 4 5 等，其典型应用为分类 规则的挖掘。 遗传算法：是一种新的优化技术，基于生物进化概念设计了一系列的过程来 4 天津大学硕士学位论文 第一章绪论 达到优化的目的。这些过程有基因组合、交叉、变异和自然选择等。遗传算法易 于并行计算，并且已经应用于分类和其他优化问题。 粗集理论：它是一种研究不确定性问题的数学工具，作为集合论的扩展，主 要用于研究不完全和不完整信息描述的数据挖掘技术。可以用于分类，进行特征 归约和最小属性子集归约。 模糊逻辑：通过隶属度函数定义分类系统的“模糊”阈值或边界，从而可以 产生人们易于理解的分类规则。 最近邻技术：通过k 个与之相近的历史记录的组合来辨别新的记录，也称为 k 一最近邻技术。主要应用于分类、聚类和偏差分析等。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者， 决策者可以通过可视化技术交互式地分析数据关系。 ( 4 ) 根据应用领域分类数据挖掘的应用领域非常广泛，如金融、电信、股 票分析、客户信用评价、网络数据分析等等。不同的应用通常需要集成对于该应 用领域特别有效的方法。普通的、全能的数据挖掘系统往往并不适合特定领域的 挖掘任务。 1 2 3 分类数据挖掘的主要步骤 分类( c l a s s i f i c a t i o n ) 是一个从现有的带有类别的数据集中寻找同一类别 数据的共同特性，并以此将它们进行区分的过程。构造分类器的过程一般分为以 下几个主要步骤： ( 1 ) 将现有的己知类别的数据划分为训练数据和测试数据两部分； ( 2 ) 通过构造分类算法对训练数据进行学习，最终得到一个符合学习要求( 如 训练精度) 的分类模型，它可以以分类规则、决策树或数学公式等形式 给出： ( 3 ) 使用分类模型对测试数据进行检测，如果符合测试要求( 如测试精度) ， 则进行( 4 ) ；否则，返回( 2 ) ； ( 4 ) 应用得到的分类模型对未知类别的新数据进行分类。 其中，步骤( 1 ) 目前主要有两种划分方法：保持( h o l d o u t ) 方法和k 倍交叉验证 ( k - f o l dc r o s sv a l i d a t i o n ) 方法。保持方法将已知数据随机划分为训练数据和 测试数据两部分，一般做法是三分之二数据作为训练数据，其余三分之一作为测 试数据。使用训练数据导出分类模型，其在测试数据上的分类精度作为最终的分 类精度。k 倍交叉验证将己知数据随机划分为k 个互不相交的大致相等的数据子 集 5 ：，s ，s 。训练和测试迭代进行k 次。在第i 次迭代，s 作为测试数据， 其余的子集用于训练分类法。最终的分类器的分类精度取k 次测试数据上的分类 天津大学硕十学位论文 第一章绪论 精度的平均值。 1 2 4 分类数据挖掘面临的主要问题 尽管分类数据挖掘继承了大量在人工智能、机器学习以及模式识别等领域己 发展出的理论与技术，但是它仍然面l 临大量问题的挑战。主要有以下几个方面“ 4 e ，： ( 1 ) 挖掘算法的有效性和可扩展性 现在的数据库包含的数据量往往达到g b 级，甚至t b 级。从巨量的数据中有效 地抽取分类信息要求所用的挖掘算法必须是有效的，而且是可扩展的。也就是说， 算法用于大型数据库时的运行时间必须是可预测和可接受的。具有指数复杂度甚 至中等多项式复杂度的算法在实际中是不实用的。 ( 2 ) 噪声数据和丢失数据的处理 这个问题在商业领域中尤其突出。可以想象，如果某数据库在建立时不是面 向数据挖掘的，其某些重要数据或属性可能丢失，某些数据的纪录很可能产生模 糊甚至错误。这将干扰挖掘过程，降低挖掘知识的精确性。目前主要是使用统计 和不确定性理论来确定隐含变量及其依赖关系。 ( 3 ) 时序数据和知识更新问题 在各种应用领域中的数据库大多是随时间变化的，这使得早期挖掘到的知识 并不适用于后期的情况。这就要求数据挖掘系统能够具备随时更新所获知识的功 能，通常采用增量学习等手段来处理时序数据。 ( 4 ) 模式易懂性 数据挖掘的结果能否为人所懂是其为人所用的前提条件。简单明了的表达方 式能够提高挖掘结果的可理解性。目前的表达方式主要有：决策树、规则、图表、 自然语言表示、以及数据与知识的可视化等。 ( 5 ) 网络与分布式环境下的分类挖掘 随着i n t e r n e t 的不断发展，网络资源日渐丰富。面对分布式与网络化的环 境，数据挖掘系统需要增加相关的技术，当前人工智能中关于多a g e n t 系统的研 究提供了有益的借鉴和帮助。 ( 6 ) 数据挖掘的效率 随着i n t e r n e t 的迅猛发展，数据的维数和数据样本个数均以十分迅猛的速 度增长，这就迫切需要提高数据挖掘的效率。而现有的神经网络数据挖掘方法中， 一般采用神经网络逐步训练、裁剪、再训练、再裁剪如此反复的方法进行属 性选择和规则抽取，这势必会影响挖掘效率。对于属性维数较小的数据库，此方 法尚可进行有效的挖掘，但面对高维数据时，此方法的弊端就暴露无遗。因此， 天津大学硕士学位论文 第一章绪论 为了适应挖掘高维数据的需要，需要提出新的属性选择方法和规则抽取方法，以 克服现有挖掘算法的局限性。 1 3 分类技术的有关方法 数据挖掘是一门新兴的技术，用于数据挖掘的主要工具有统计学、神经网络、 决策树、粗集理论、k 一最近邻、模糊逻辑以及它们的集成，而在这些方法中，神 经网络、粗集理论、决策树学习、遗传算法、k 一最近邻方法是几种最主要的方法， 本节重点介绍这几种方法在分类数据挖掘中的应用。 1 3 1 神经网络 神经网络是分类技术中最重要的一个工具，近几年的大量研究证明神经网络 将有希望替代传统的基于统计的分类方法嘲。其优势在于：( 1 ) 神经网络是一个 自适应方法；( 2 ) 神经网络可以以任意精度逼近任意函数“o “1 ，因为分类过程就 是寻求类和属性之间比较精确的关系的过程；( 3 ) 神经网络是一个非线性模型， 这使得它能够灵活的模拟现实世界中数据之间的复杂关系。虽然神经网络有各种 模型可以应用于分类任务，但是使用较多还是前馈神经网络。 已经有很多文献表明神经网络已经成功的应用于现实世界的包括工业、经济 和科学“”的各种分类任务，其应用包括破产预测“”1 ，笔迹识别“6 ”，故障探测 ”，医疗诊断“捌和债券估价”等。同时有文献对神经网络和其他的传统分类技 术作了比较。2 “，其中m i c h i ee t a 1 2 3 对神经网络、统计分类和机器学习三 种分类技术总共采用了2 3 种方法对2 0 种不同的实际数据库进行了分类结果的比 较，它的结论是尽管前馈网络对于多数问题能够很好的解决，但是没有哪种方法 对于所有的数据库都是最优的。 学习性能和泛化性能是神经网络研究中最重要的两个问题”2 ，学习性能是 指拟合训练数据中内在的行为和规律的能力，而泛化性能是指预测和训练数据差 距比较大的数据的能力。当神经网络的拟合能力较强时对噪声数据会导致过拟合 问题的出现，过拟合的表征现象是神经网络模型能够很好的拟合训练数据，但是 当用来预测未知数据时将表现出很差的结果( 网络的泛化性能很低) ，即学习性能 和泛化性能往往是一对矛盾。目前解决这一矛盾的方法有选择合适的网络结构 ( 如隐单元的数目) 、选择合适的样本尺寸、选择合适的网络模型( 如正则神经网 络) 以及样本特征集的选择等。 文献 2 9 发现神经网络分类器是一种非稳定性预测方法，即训练样本的微小 变化将导致测试集上预测精度的很大改变。因此在训练网络的过程中有一些方法 天津大学硕士学位论文 第一章绪论 也可以减小网络的预测误差提高泛化性能，如交叉验证、带惩罚项训练、权重削 减和节点删除”等。 虽然神经网络经过上述的各种改进方法后具有很高的学习和泛化性能，但是 神经网络仍然有一个缺陷即其知识是用加权连接单元组成的网络来表示的，这样 的形式很难被人理解。这激发了人们提取隐藏在经过训练的神经网络中的知识并 解释这些知识的研究热情。研究方法主要是网络的分类规则提取，业已提出了多 种规则提取算法，其中文献 3 3 的规则提取方法主要步骤是首先对网络进行裁 剪，剪去网络中对网络精度影响较小的权值和节点，然后通过聚类的方法对每个 节点的输出值进行聚类，导出输出值和隐层单元的相关规则以及隐层和输入值之 间的相关规则，最后两个规则集结合在一起便形成了i f t h e n 规则。当然还有许 多其他的规则提取算法如利用布尔函数抽取规则”和搜寻重复样本抽取规则等 以及其他一些方法。5 “。文献 3 9 将r s e t i o n oe t a l 研究的两个规则提取算法 n e u r o l i n e a r 和n e u r o r u l e 成功的应用于医疗诊断。 当然还有其他一些算法将神经网络和其他的知识表达方法相结合，从而对神 经网络抽取的知识重新描述，如粗集理论、模糊逻辑“。4 “、决策树“3 、”和似然 推理1 等。 虽然神经网络目前在数据挖掘中取得了很大的成就，但仍然存在不少问题， 主要表现如下： ( 1 ) 网络不适合于处理大规模数据。当数据维数很大时，用神经网络处理 数据时将会使计算时间过长，内存占用量过大，使数据挖掘效率低下。 而在原始数据库中，包含大量冗余和不相关属性，这些属性对数据挖 掘用途不大。因此，迫切需要一种方法，从原始数据库中选择部分重 要的、对数据挖掘影响最大的数据属性集： ( 2 ) 经网络挖掘过程比较复杂。由于神经网络数据挖掘过程中，其知识隐 含在神经网络权值和隐含层激活值中。挖掘过程中，需要对输入层和 隐含层结点进行逐步的训练、裁减、再训练、再裁减，如此反复进行， 直到网络分类预测精度误差达到事先设定的阈值为此。规则抽取时， 需要对隐含层激活值进行离散化处理，再抽取隐含层到输出层的规则 和输入层到隐含层的规则，最后把这两部分规则结合起来，得到最后 的规则。这种挖掘方法比较繁琐，需要提出新的神经网络数据挖掘方 法，以简化神经网络挖掘过程，提高神经网络数据挖掘的效率。 一8 天津大学硕士学位论文 第一章绪论 1 3 2 粗集理论 粗集( r o u g hs e t ) 理论是八十年代初由波兰数学家z p a w l a k “”首先提出的 一个分析数据的数学理论。它是一种研究不确定性问题的数学工具”，作为集合 论的扩展，主要用于研究不完全和不完整信息描述的数据挖掘技术。目前无论是 在系统理论、计算模型的建立和应用系统的研制开发上，都已取得了很多成果， 也建立了一套较为完善的粗集理论体系”1 。 粗集理论能够在缺少关于数据先验知识的情况下，以考察数据的分类能力为 基础，解决模糊和不确定数据的分析和处理。由于粗集算法简单易于操作，以其 为基础构造的数据挖掘工具比较多”1 。( 它可以支持知识发现的多个步骤，如数 据预处理、数据约简、规则生成等。 粗集理论的要点是将分类与知识联系在一起，它使用等价关系来形式化地表 示分类。“。这样，知识就可以理解为：使用等价关系集r 对离散表示的空间u 进 行划分，知识就是r 对u 划分的结果。由此，在u 与r 的意义下，知识库可以定 义为属于r 中的所有可能的关系对u 的划分，记为 k = ( u ，r )( 卜1 ) 进而，为了描述知识的确定程度，粗集理论引入了上近似和下近似的概念， 并以这些概念来定义u 中的一个子集b 与被关系r 划分之后的u 的相合程度，称 为粗糙度。 粗集理论还包含了求取大量数据中最小不变集合( 核) 与求取最小规则集( 称 为约简) 的理论，这就是分类过程中的属性约简和规则生成，也是粗集理论在数 据挖掘中的主要应用。 基于粗集理论的知识发现主要是借助于决策表这样一种有效的数据表知识 表达形式，决策表的每一行为一个实例，每个实例包含若干个条件属性和一个决 策属性。其知识发现，主要是通过对原始决策表的约简，在保持决策表中决策属 性和条件属性依赖关系不变的前提下对决策表进行约简，包括属性约简和值约 简。 人们已在属性约简上作了许多工作，提出了一些比较有效的算法，如通过去 除某属性后判断不可区分关系是否改变来决定是否应删除该属性。“。在已知关于 粗集理论研究中，s k o w r o n ”1 提出的可辩识矩阵为求取最佳属性约简提供了很好 的思路，通过可辩识矩阵可以很快的得到决策表的属性核”1 。在可辩识矩阵的基 础上又提出了各种改进算法如潘丹，郑启伦等e 5 5 提出的相对差异比较表，在此 基础上借用了基因算法的基本思想提出了属性约简自寻优算法。除了可辩识矩阵 外还有其他的属性约简方法，如基于逻辑运算的约简算法、归纳属性约简算法和 天津大学硕士学位论文 第一章绪论 基于特征选择的属性约简算法等。 属性约简是将决策表中对决策分类不必要的属性进行约简，但是这只是在一 定程度上去掉了决策表中的冗余信息，对于每一条实例来说可能仍然有不必要的 属性存在，因此在不引起冲突的条件下，可以将每一条实例中的该属性删除，这 就是值约简，值约简的最终结果就是知识发现所需的规则。值约简算法主要包括 归纳值约简、启发式值约简和基于决策矩阵的值约简算法等以及增量式规则获取 算法。”和其他一些改进算法”“。 1 3 3 决策树学习 决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散目标函数的 方法，在这种方法中学到的知识被表示成一颗决策树。学到的决策树也能表示为 多个i f t h e n 的规则，以提高可读性。决策树已被成功的应用到医疗诊断、评估 贷款申请的信用分析等广泛领域。i d 3 4 ，c 4 5e s g 是其最主要的算法，最近，又推 出了s e e 5 ( w i n d o w s 平台) 、c 5 0 ( u n i x 平台) 。 决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为 实例的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的 每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节 点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的数值向 下移动。然后这个过程在以新节点为根的子树上重复。 尽管已经开发的种种决策树学习算法有这样或那样不太一致的能力和要求， 通常决策树学习最适合具有以下特征的问题1 。 ( 1 ) 实例是由“属性一值”对表示的：实例是一系列固定的属性和它们的值来 描述的。在最简单的决策树学习中，每个属性取少数的离散的值。然而，扩展的 算法也可以处理值域为实数的属性； ( 2 ) 目标函数具有离散的输出值：该方法适应于给每一个实例赋予一个布尔型 的分类。这种决策树方法也很容易扩展到学习有两个输出值的函数。一种更强有 力的扩展算法允许学习具有实数输出的函数； ( 3 ) 可能需要析取的描述：决策树很自然的代表了析取表达式： ( 4 ) 训练数据可以包含错误：决策树学习对错误有很好的鲁棒性，无论是训练 样例所属的分类错误还是描述这些样例的属性错误； ( 5 ) 训练数据可以包含缺少属性值的实例：决策树学习甚至可以在未知属性值 的分类时使用。 已经发现很多实际问题符合这些特征，所以决策树学习已被应用到很多问 题中。例如根据疾病分类患者；根据起因分类设备故障；根据拖欠支付的可能 天津大学硕士学位论文 第一章绪论 性分类贷款问题申请等等。 另外，决策树还和其它知识表示方法相结合，如神经网络，模糊逻辑，遗 传算法，粗集理论等。 1 3 4 遗传算法 遗传算法“”是在7 0 年代初期由美国密执根大学的h o l l a n d 教授发展起来的一 种软计算方法。它主要用于优化领域。它借鉴了很多生物进化的特征。遗传算法 是一种大致基于模拟进化的学习方法，其中个体常被描述为二进位串，称为染色 体。搜索合适的个体是从若干初始假设的群体或集合开始的。当前群体的成员通 过模仿生物进化的方式来产生下一代群体，比如说随机变异和交叉。每一步，根 据给定的适应度评价当前群体中的个体，然后使用概率方法选出适应度最高的个 体作为产生下一代的种子。 遗传算法包含以下主要处理步骤。“： ( i )首先对优化问题的解进行编码，一个解的编码为一个染色体，组成编码 的元素为基因。编码的目的主要是用于优化问题解的表现形式和利于之 后遗传算法中的计算： ( 2 ) 适应函数的的构造和应用。适应函数基本上依据优化问题的目标函数而 定。当适应函数确定后，自然选择规律是以适应值的大小决定的概率分布 来确定哪些染色体适应生存，那些被淘汰。生成下来的染色体组成种群， 形成一个可以繁衍下一代的群体； ( 3 ) 染色体的结合。双亲的遗传基因结合是通过编码之间的交叉产生下一代， 新一代的产生是一个生殖过程，它产生了下一个新解； ( 4 ) 变异。新解产生过程中可能发生基因变异，变异是某些解的编码发生变 化，使解有更大的遍历性。 遗传算法的主要优点为。“： ( 1 ) 遗传算法适合数值求解那些带有多参数、多变量、多目标和在多领域但连 通信较差的n p _ h a r d 优化问题； ( 2 ) 遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非 常深入的了解； ( 3 ) 遗传算法同求解问题的其他启发式算法有较好的兼容性。如可以用其它的 算法求初始解。在每一群体，可以用其它的方法求解下一代新群体。 在分类数据挖掘中，遗传算法主要是和其它方法集成，具体应用在属性选择 和规则选择方面。 天津大学硕士学位论文 第一章绪论 1 3 5k 一最近邻方法 由于k 一最近邻技术的鲁棒性、理论完美性和实现的灵活性使得k 一最近邻被 广泛应用于分类”。k 一最近邻分类技术是数据挖掘技术中最容易理解的技术之 一，因为它是用与人类思维方式相似的方法进行分析即检测最接近的匹配样 本。k 一最近邻分类是基于类比学习的”，训练样本也是用n 维数值的属性描述。 每个样本代表n 维空间的一个点，这样所有样本都存放在n 维模式空间中。当给 定一个未知样本时，k 一最近邻分类法将搜索模式空间，找出最接近未知样本的k 个训练样本，这k 个训练样本是未知样本的k 个“近邻”。其近邻性一般用欧几 里德距离定义，设两个样本分别是五= 0 ，x ：，a ，z 。) 和r = 。，y ：，人，乩) ，其欧 几里德距离是 d ( x ：压丽 ( 1 2 ) 未知样本被分配到k 个最近邻者中最公共的类。 由于k 一最近邻分类方法是首先存放所有的训练样本，当有新的样本需要被 分类时才从样本库中搜索所有的与其最邻近的训练样本，当训练样本的数据量很 大时将招致很大的计算开销，因此需要一个有效的索引技术。同时由于在最邻近 的测量对每个属性指定了相同的权，即认定每个属性对分类所做出的贡献是一样 的，当数据中存在许多不相关属性时，这可能会引起分类混乱。 基于上述两个缺点人们提出了各种各样的改进算法，简述如下。 当训练样本的数量比较大时，为了减小计算开销，必须对训练样本集进行编 辑处理，即从原始的训练样本集中选择最优的参考子集进行k 一最近邻计算以减 , j , i j i l 练样本的存储量和提高计算效率。在文献 6 4 中对许多编辑处理方法进行了 总结，其中主要有三种常用方法o 。第一种方法为近邻规则浓缩法( c o n d e n s e d n e a r e s tn e i g h b o rr u l e ：c n n ) 。，其编辑处理的结果是产生一个训练样本的子 集，在这个子集上进行k - 最近邻的计算，其中文献 6 2 就是进行这种方法的研 究。第二种方法为产生或修改原型( g e n e r a t eo rm o d i f i e dp r o t o t y p e ) ，这种方 法包括建立个新的原型o ”和在原始训练样本集中调整几个有限的数据。其中多 数情况下采用神经网络技术”“。第三种方法为多重分类器的结合( c o m b i n a t i o n o fm u l t i p l ec l a s s i f i e r s ) ，是指用几个神经网络组成一个分类器o ，其每个 神经网络担当一个卜最近邻分类器的作用，对一个子集进行卜最近邻计算，而 这个子集用h a r t s 旧1 提出的方法来产生。 当样本数据中含有很多不相关属性时，为了减小不相关属性对分类的影响， 天津大学硕士学位论文 第一章绪论 人们提出了许多方法加以改进，其中主要是针对不同的属性赋予了不同的权重， 对于权重的调整提出了各种算法。文献 7 1 提出的v s m 算法采用最佳的变化梯度 学习每个属性的权重，它通过一个最佳函数在每次迭代时对权重进行调整，但是 由于k 一最近邻方法是一个非线性问题，因此线性的变化梯度很难保证该方法收 敛，尤其是当最佳函数有多个局部最小值时。文献 7 2 提出了4 种神经网络技术 对属性的权重进行调整，并且对各种神经网络的调整结果进行了比较，这一方法 将神经网络和k 一最近邻技术有机的融合在一起。 1 4 本文的主要工作和创新点 1 4 1 本文的主要工作 本文以神经网络为主要研究方法，并结合模糊逻辑技术，对分类数据挖掘中 的属性选择和规则抽取两个问题提出了一些有效的算法，具体的研究工作如下： 第一章为本文的绪论部分。首先分析了本文的选题背景和研究意义，然后对 分类数据挖掘的基本概念作了全面的介绍，接着介绍了分类数据挖掘常用技术， 最后总结了本文的主要工作点和创新点。 第二章介绍了属性选择和规则抽取的基本概况，研究进展。着重阐述了神经 网络、粗集理论和决策树在分类数据挖掘属性选择和规则抽取中的应用。 第三章提出了一种基于输入输出关联法排序的r b f 神经网络属性选择方法 3 。原始数据集中含有大量冗余属性和不相关属性，如何从这些属性集中选出部 分对分类最有用的属性集是数据挖掘中的一个重要课题。随着数据的维数越来越 高，属性选择显得越来越重要。由于属性选择是一个n p h a r d 问题，现有的属性 选择方法计算过于复杂，效率低下。本章提出一种新的属性选择方法。该方法先 用输入输出关联法对所有属性进行重要性排序，然后根据属性重要性次序用r b f 神经网络进行属性选择。 第四章提出一种可分性判据排序的r b f 神经网络属性选择方法”“。该方法先 用可分性判据计算每个属性的重要度，并对其进行排序，然后根据属性重要性次 序用r b f 神经网络进行属性选择。 第五章提出一种基于降维