（计算机软件与理论专业论文）数据挖掘技术的研究与实现.pdf

南京航空航天大学硕士学位论文 摘要 l 数据挖掘技术近年来成为数据库、机器学习和决策支持领域的研究热点，其中分 类模型的挖掘是数据挖掘的重要研究内容之一。) 本文基于农业领域数据挖掘的需求， 首先将模糊技术融入连续属性论域的离散化过程中，在传统分类模型挖掘的基础之上 提出模糊分类模型的概念；接着给出一种基于遗传算法的连续属性离散化方法；然后 根据数据挖掘的需求改进标准遗传算法提出算法f c r m a 实现了模糊分类模型的挖 掘；最后应用f c r m a 基于c o m 标准开发出可集成到农业专家系统开发平台的知识 获取构件，以缓解专家系统中知识获取的“瓶颈”问题。实验证明：模糊分类模型比 普通分类模型具有更高的预测准确度，f c r m a 可以从数据库中挖掘出高效的模糊分 类模型并可应用于实际的农业生产中。 关键词：数据挖掘；分类模型；遗传算法；模糊逻辑 譬蠢焉 弋1 6 一 塑塑垄堡堡查塑堕窒量壅墨 a b s t r a c t t h e t e c h n 0 1 0 9 yo f d a t am i n i n gh a sb e c o m eat o d a y sh o t s p o ti nt h ef i e j do f d a t a b a s e 、 m a c h i n e 1 e a m i n g a n d d e c i s i o n m a k i n & a n d t h em i n i n go fc l a s s i 矗e ri so n eo f t h ei m p o r t a m t o p i c so f d a t am i n i n gb a s e do nt h er e q u i r e m e n to f a g r i c u l t u r ed a t am i n i n g ，t h i sp a p e la t n r s t ，a d d s 如z z yi o g i ci n t ot h ep r o c e s so fm a k i n gt h ed o m a i no fs e r i a t ea t t f i b u t i o n sd i s c f e t e a n dp u t sf o r w a r dt h ec o n c e p to f 如z z y c l a s s m e es e c o n d ，b a s e do ng e n e t i ca l g o r i t h m ，t h i s p a p e rp u t sf o 九a r daw a y t om a k et h ed o m a i no fs e “a t ea t t r i b u t i o n sd i s c r e t e ：t h i r d t h i s p a p e rr e a l l z e s t h em i n i n g o f 旬z z yc l a s s i n e rb a s e do na ni m p r o v e dg e n e t i ca l g o r i t h m a c c o r d i n g t od a t a m i n i n g ；a t1 a s t ，b a s e do nc o m t e c l f l o l o g y ，t h i sp a p e ra p p l i e st h e a l g o r i t h m t o d e v e l o p i n g a k n o w l e d g e a c q u i r i n g m o d e lw h i c hc a nb ei n t e g r a t e d i n t o a g n c u l t u r ee x p e ns y s t e m t o i m p r o v ep r e s e m k n o w l e d g e a c q u i r i n g m e t h o dt h e e x p e r i m e n t sp r o v e t h a t t h e 允z z y c l a s s m e rh a sb e t t e rf o r e c a s t a b i l i t vt h a no r d i n a r v c l a s s i e e lf c r m a c a nm i n eg o o d 允z z yc l a s s m e rf r o md a t a b a s ea n dc a nb ea p p l l e dt o a g r i c u l t u r e k e y w o r d s ：d a t a m i n i n g ，c l a s s i f i e lg e n e t i ca l g o r i t h m ，f u z z yl o g i c 南京航空航天大学硕士学位论文 1 1 本文目的和意义 第一章绪论 信息爆炸是当今数字化社会面临的一个巨大挑战。商业上条形码的普遍使用使得 很多行业每天都积累了大量数据，科学上先进的现代观测仪器的使用导致每天产生巨 量的数据，i n t e r n e t 的迅猛发展使得网络上的各种信息异常丰富。面对数据和数据库 的飞速增长，人们迫切地感到需要新的技术和工具以便从大量的数据中智能地、自动 地抽取出有价值的知识或信息。数据挖掘“1 ( d a t am i n i n g ) 于是应运而生。目前，d m 不仅被许多研究人员看作是数据库系统和机器学习方面一个重要的研究课题，而且被 许多工商界人士看作是一个能带来巨大回报的重要领域。从数据库中发现出来的知识 可以用在信息管理、查询响应、决策支持、过程控制等许多方面。 我国是农业大国，如何使科学技术更有效地服务于农业生产是关系到国计民生的 一件大事。在过去的几年中，我国曾耗费巨资进行各种农业数据的普查，积累了大量 数据资料。如何有效地从这些浩瀚的数据中深入寻找各种因素的相互联系，发现一些 指导农业生产的规律或知识，这对推动农业生产，产生巨大的经济效益与社会效益是 十分必要的，因此农业领域数据挖掘需求非常迫切。 本文的研究工作源于上述背景。我们课题研究的目的是根据农业数据挖掘的需 要，对数据挖掘技术进行深入的研究，探讨新的挖掘算法，以及研究如何应用到农业 生产中。 1 2 数据挖掘概述 由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作中的需要， 数据挖掘技术逐渐发展起来。d m 也有人称之为数据库中的知识发现眯n o w l e d g e d i s c o v e r yi nd a t a b a s e ) ，实际两者是有区别的，一种较为普遍的观点认为：数据挖掘 是k d d 中专门负责发现知识的核心环节；而k d d 是一个交互式、循环反复的整体 数据挖掘技术的研究与实现 过程，除了包括数据挖掘外还包括数据准备和发现结果解释评估等诸多环节，但一般 可以不加区别地使用两者。k d d 术语于1 9 8 9 年出现，其定义几经变动，最新的描述 性定义是f a y y a d 等给出的：k d d 是从数据集中识别出有效的、新颖的、潜在有用 的，以及最终可理解的模式的非平凡过程。在定义中，涉及几个需要进一步解释的概 念：“数据集”、“模式”、“过程”、“有效性”、“新颖性”、“潜在有用性” 和“最终可理解性”。鬏锘筹是一组事实f ( 如关系数据库中的记录) 。船f 是一 个用语言来表示的一个表达式e ，它可用来描述数据集f 的某个子集凡，e 作为一 个模式要求它比对数据子集r 的枚举要简单( 所用的描述信息量要少) 。也翟在k d d 中通常指多阶段的一个过程( 见图1 1 ) ，涉及数据准备、模式搜索、知识评价，以 及反复的修改求精；该过程要求是班j 醐的，意思是要有一定程度的智能性、自动性 ( 仅仅给出所有数据的总和不能算作是一个发现过程) 。方兹拦是指发现的模式对 于新的数据仍保持有一定的可信度。新颧性要求发现的模式应该是新的。潜在存劈 拦是指发现的知识将来有实际效用，如用于决策支持系统里可提高经济效益。最冬 可理解拦要求发现的模式能被用户理解，目前它主要是体现在简洁性上。有效性、 新颖性、潜在有用性和最终可理解性综合在一起可称之为兴，廖拦。k d d 过程可粗略 地理解为三步：数据旌务( d a t ap r e p a r 砒i o n ) 、教锘嬲以及结果的解释铲信 ( h l t e r d r e t a t i o na n de v a l u a t i o n )。 图1 1k d d 过程示意图 数据准备又可分为三个子步骤：数据迸取( d a t as e l e c t i o n ) 、我窍，厨处翌( d a t a 2 南京航空航天大学硕士学位论文 p r e p m c e s s i n g ) 和敛镭雯摸( d a t at r a n s f o r m a t i o n ) 。数据选取的目的是确定发现任务的 操作对象，即目标数据( t a 唱e td a t a ) ，它是根据用户的需要从原始数据库中抽取的一 组数据。数据预处理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、完 成数据类型转换( 如把连续值数据转换为离散型的数据，以便于符号归纳，或是把离 散型的转换为连续值型的，以便于神经网络归纳) 等。当数据挖掘的对象是数据仓库 时，一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是消 减数据维数或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减 少数据挖掘时要考虑的特征或变量个数。 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类4 “”、 聚类、关联规则发现陋”】或序列模式发现等。确定了挖掘任务后，就要决定使用什么 样的挖掘算法。同样的任务可以用不同的算法来实现，选择实现算法有两个考虑因素： 一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际 运行系统的要求，有的用户可能希望获取描述型的( d e s 酾p t i v e ) 、容易理解的知识( 采 用规则表示的挖掘方法显然要好于神经网络之类的方法) ，而有的用户或系统的目的 是获取预测准确度尽可能高的预测型( p r e d i c t i v e ) 知识。完成了上述准备工作后，就 可以实施数据挖掘操作了。需要指出的是，尽管数据挖掘算法是k d d 的核心，也是 目前研究人员主要努力的方向，但要获得好的挖掘效果，必须对各种挖掘算法的要求 或前提假设有充分的理解。 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或无关的 模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现过程 退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据挖掘 参数值，甚至换一种挖掘算法( 如当发现任务是分类时，有多种分类方法，不同的方 法对不同的数据有不同的效果) 。另外，k d d 由于最终是面向人类用户的，因此可能 要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决 策树转换为“i f - l h e n ”规则。 1 3 课题背景介绍 当今国际上发达国家广泛利用信息技术作为发展农业的重要手段，其中农业专家 3 数据挖掘技术的研究与实现 系统的研究与应用己达到较高的水平。通过把农学领域的专家知识、实践经验、科技 成果和数据资料等与计算机技术结合起来，建立起能够针对不同情况推荐优化方案的 综合性专家系统，通过大面积的应用，对推动科技进步具有重要的理论意义和实用价 值，针对我国幅员辽阔，农民科技文化素质差、高水平的领域专家和农技人员不足的 现实情况，具有更特殊的重要意义。 “智能化农业信息技术应用示范工程南京示范区”是国家8 6 3 计划3 0 6 主题的重 点课题，以“小麦周年生产综合管理专家系统”为核心内容，总体目标是通过智能化 信息技术高度集成、组装配套有重要价值和应用前景的农业技术成果，开发出可在微 机和网络上运行的专家系统，建立起集约化科学栽培技术体系和为生产服务的运行机 制。它是基于当前主流软硬件环境上开发的面向农业应用领域的集成化专家系统，由 里到外由农业专家系统开发平台、应用框架和本地化应用系统三个层次组成，如图 11 。 图1 2 农业专家系统总体结构 图中内层为外层提供服务，外层在内层提供服务的基础上开发，即开发平台的层 次性。每一层的软件均由统一规范的软构件组成，且可以方便地集成到由主流软硬件 环境所提供的“软总线”上，即即插即用，从而构成了可伸缩、可裁减的农业专家系 统通用开发平台、应用框架或本地化的应用系统，即开发平台的集成性。内层所有的 软件要有较宽的适应范围，能为外层软构件以方便的形式调用，平台内部各层的软构 4 南京航空航天大学硕士学位论文 件能开放地给设计应用框架的非计算机人员使用，框架层开放给示范区进行本地化应 用系统开发的基层高素质农技人员使用，应用系统则能够直接交给一般的基层农技人 员和新一代农民使用。各层次的专家系统开发者可以根据系统提供的软构件开发技术 手段和技术和规范，自行开发更适用的软构件，在授权之后可集成到系统中来。开发 平台提供适用于种植业、养殖业、农产品加工业等各类农业专家系统的通用开发环境， 应用框架提供专用于某一特定农业领域的专家系统开发环境，应用系统是专用于某一 特定农业领域，并在某一特定地区应用的农业专家系统。 知识获取是建造专家系统的核心问题，也是建造专家系统的“瓶颈”问题。知识 获取的过程就是从某些知识源中提炼出求解问题的知识或规则的过程，并转化为计算 机程序。目前出现了一些能应用于农业领域的数据挖掘算法m 1 。能否有效地获取知 识是专家系统成败的关键，它是决定一个专家系统性能的主要因素。 本课题的研究任务是通过对数据挖掘技术和遗传算法应用的研究，提出一种新的 有效的数据挖掘算法，并基于该算法开发出基于c o m 标准的能集成到农业专家系统 中的知识获取构件，该构件符合智能化农业信息技术应用工程规范的接口标准，能 够从农业数据库中发现一种或多种知识，实现知识的自动获取而解决知识获取的“瓶 颈”问题。 1 4 本文贡献 本论文的贡献主要为如下方面： 1 分析国内外数据挖掘研究的现状，在传统的分类模型挖掘的基础上，根据客观 世界的多样性和复杂性造成许多事物难于用精确和确定的概念描述的现实，将模糊技 术引入分类模型挖掘中，提出模糊分类模型的概念。 2 提出了一种基于遗传算法的连续属性离散化方法。实验结果表明，采用基于遗 传算法的离散化方法可以作为分类模型挖掘算法中的连续值属性预处理有效手段。 3 通过对遗传算法应用的研究，提出模糊分类模型挖掘算法f c 眦( f u z z y c l a s s i f i c a t i o nr u l e sm i n i n ga 1 9 0 r i t 1 1 1 1 ) ，实验证明该算法获得的分类模型具有较 高的预测准确度。 4 基于c o m 0 l e 实现一个知识自动获取构件，该构件可集成到农业专家系统开发 数据挖掘技术的研究与实现 平台中缓解知识获取的“瓶颈”问题。 1 5 本文组织安排 本论文主要由六章组成。 第一章是全文的绪论。 第二章提出模糊分类模型的概念。 第三章在讨论连续属性离散化方法的基础上给出了一种基于遗传算法的离散化方 法，并在该章最后给出了和其它常用方法的实验比较。 第四章实现了模糊分类模型的挖掘算法f c r m a ，并从多个方面对f c r m a 算法进行 了分析以及和其它常用算法进行比较。 第五章实现了知识获取构件，然后给出了一个在南京农业大学提供的降水数据库 上进行分类规则发现的运行实例。 第六章是全文的总结。 6 南京航空航天大学硕士学位论文 第二章模糊分类模型及其挖掘技术 2 1 模糊分类模型 2 1 1 信息系统( i n f o r m a t i o ns y s t e m ) 客观世界或对象世界抽象为一个信息系统，也称属性一值系统。一个信息系统 s 是一个四元组： s = 其中，u 是一组对象( 或事例) 的有限集合，称论域；设有n 个对象，则u 可表 示为：u = u 。，u ：，u 。) 。a 是有限个属性的有限集合，设有m 个属性，则其可表示 为：a = a 。，a 2 ，a 。) 。v 是属性的值域集，v = v 。，v 2 ，v 。) ，其中v 是属性a 的 值域，我们限制属性的值域为离散的( 定性的) ，如果该属性是连续值( 定量的) ，则 需要先经过离散化处理( 具体方法参见下章) ；a 又可进一步划分为两个不相交的集 合：条件属性集c 和决策属性集d ，c 和d 满足a = c u d 且c n d = g ，d 般只有 一个属性。f 是信息函数( i n f o r m a t i o n 血n c t i o n ) ，f ：u a _ v ，f ( u 。，a ) v 。 信息系统也称信息表，表列是属性，共有m 列；表行是对象，共有n 行。第i 行 第j 列上的表项内容是f ( u 。钆) 。表中的一行内容表示了信息系统中该对象的所有信 息。数据库中的表可以看成信息系统。 2 1 2 分类和分类模型1 1 】 分类是数据挖掘的一种非常重要的方法，它反映同类事物共同性质的特征型知识 和不同事物之间的差异型特征知识。分类的概念是在已有数据的基础上学会个分类 函数或构造出一个分类模型，即通常所说的分类器( c 1 a s s 砺e r ) 。该函数或模型能够把 数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测。分类模 型的获得需要一组训练例子集合，我们从信息系统s 的论域u 中采用分层抽样法抽取 一组对象或事例组成训练集和测试集，我们把这些事例的条件属性集c 称做对象的描 述属性，把决策属性d 作为分类的属性叫做标签，也就是训练例子的类别( c l a s s ) 。 设属性a 论域上的定性概念集合记为t ( a ) = 正，巧，磁) ( i - l ，2 ，m ；w i 为定性 7 数据挖掘技术的研究与实现 概念数目) ，当a 为离散属性时，t ( a ) 是论域映射的一组离散描述；当a 为连续属性 时，t ( a ) 为离散化所得离散区间的语义描述集合。当a 为决策属性即类别c l a s s 时， 我们将t ( a ) 映射为例子的类别集合t ( c l a s s ) = c ，c ：，c 【) 饵为例子的类别数) 。分类 模型的规则( 本文称之为分类规则) 形式如下： i f a 。t i s t 甚a n da 、i st 泛a n d a il i s t 泛t h e n c k s s sc ，其中l 为魏戳鼓长度，t i t a 。：j ，l t z m ，l j z w pz 2 1 2 一l ，c t i c l a s s j 。 目前对分类规则的研究大多是仅限于用确定的精确概念表示的确定分类规则 m 4 “”，但是从概念的外延来看，概念可以分为精确的概念和不精确的概念。在传统 的分类系统中，t 是普通的经典集合，但在日常生活中许多属性代表人类的意愿，它 们有时不是绝对的，如人类的感觉：冷、热等，再如年龄，对于“青年”这个语义， 不能用一个绝对的年龄界限来定义它。因此分类中的模糊问题是普遍存在的。而且在 对数值型属性进行离散化过程中，对属性论域进行僵硬的划分，并不能直接反映数据 的分布情况。例如年龄属性是数据库中常见的一个属性，常用具体的数字表示，进行 分类规则挖掘时需要离散化成一定的年龄区间，如( o ，1 1 ) 、( 2 5 ，3 5 ) 等，并为每个离 散区间加上定性语言值，如小孩、青年等，但是青年的年龄区间并不是绝对在2 5 和3 5 之间。这种僵硬的划分影响挖掘到的分类规则的正确性，我们可以利用模糊技术将区 间模糊化减少边缘效应，可以在集合元素和非集合元素之间提供平滑的变迁，从而克 服了划分边界过硬的缺点，提高划分的合理性，从而提高挖掘出的分类模型的分类正 确度。下面首先简单介绍模糊技术的理论基础。 2 1 3 模糊技术【4 ，5 1 人类在认识改造自然和社会的过程中，首先寻找最为简单的确定性判断的现象 一是或非现象的规律性，并建立相应的数学方法。这个方法在c a n t o r 建立的集合论上， 奠定了现代经典数学的基础，它用来处理确定性现象，取得了辉煌的成果，为人类进 入现代文明，作出了巨大的贡献。随着社会和科学技术更加进步、发展，人类进入了 “自然社会思维”的认知阶段。人们要求数学能处理更为复杂的不确定现象， 特别是人文科学、社会科学和思维科学中的不确定现象，也要求计算机像人脑一样， 能自行识别和处理客观世界中的不确定问题。1 9 6 5 年，l az a d e h 借助经典数学的成 r 南京航空航天大学硕士学位论文 就，并在此基础上建立了模糊集合论，取得了巨大的成功。 z a d e h 建立的模糊集合论是在经典集合论上的扩充，它采用了经典数学的映射和 方法，是经典意义处理模糊性现象的集合，它无条件地承认了经典数学的实数理论和 自然数系。从特征函数方面讲就是：元素x 对集合a 的隶属程度不再局限于取o 或1 ， 而是。到1 的任何一个数值，这一数值反映了元素x 属于a 的程度。 定义2 1 设u 是一个用精确数值量表示的论域空间，j 是论域u 上的一个定性概念 ( 定性语言值) ，对于任意x u ，指定了个数“。( x ) o ，1 ，叫做x 对于4 的隶属程 度。映射“。叫做4 的隶属度函数。 “ ：u o 0 ，i 】 上述定义表明，一个定性概念4 可完全由其隶属度函数”。来刻画。“。的值接近于l 表示x 隶属于4 的程度很高；”。的值接近于0 ，表示x 隶属于4 的程度很低：当“。 的值域变为( 0 ，1 ) 时，o ) 演化为普通的特征函数，4 演化为传统的定性概念a 。 目前常用的隶属度函数有三角形、梯形和s 形等。s 型隶属度函数由于形状容易 控制，所以是一种常用的模糊隶属度函数，描述它的方法有多种，本文采用图2l 所 示的s 型隶属度函数，表达式如下： “s ( x ；口，) = 一丁 口 卢 中其 廖 y 岱 一 一 y r x 口 芦 2 - 、， y 一口口一口二一 o二一zy l与肇 芒r 孔 2 一 数据挖掘技术的研究与实现 u l 05 0 ， j 。 d b ，、 jj y x a 咱a _ b 2 图2 ，l 隶属度函数图22 中间型隶属度函数 基于上述s 型隶属函数的戒上型、中间型( 如图22 ) 和戒下型隶属度函数可以 分别描述为： “( z ；口，6 ) = 1 一“s ( z ；，d ，( 22 ) 吲础，垆 。：嚣：；： s ， “r s ( x ；口，6 ) = “s ( z ；d 一6 ，口)( 24 ) 其中，a 为曲线的核，b 为带宽因子。 2 1 4 模糊分类模型 本节我们提出模糊分类模型的概念，它是普通分类模型在模糊集合上的扩展，其 组成规则在形式上和普通分类模型是相同的。首先我们定义一种基于模糊集合理论的 广义数据离散描述方法，当属性为离散属性时，与普通分类规则处理相同；当某属性 为连续属性时，我们将其论域划分为按照定的交叉因子相互交叉的区间描述( 定性 语言值) 。为了方便，我们作如下统一定义： 定义2 2 属性a 值域v 。映射的一组离散描述为f ( a ) = ( j 。1 ，2 ，w ，仁1 ，2 ，m ) ，石为离散描述或区间的定性语言值，q 和q 为隶属度函数 参数。当 为离散属性时，口；和巧取值o ，当a 为连续属性时，d ；、q 为区间f 隶 1 0 南京航空航天大学硕士学位论文 属度函数参数值。模糊分类模型的规则形式为 i f a 1 i st 盖a n da 、i st 苌a n d a 。l l s t 泛t h e n c l a s si sc ，其中l 为规购的长度t t f ( a 。：) ，j i 。m ，l j 。w r z 2 i 2 l 。c f ( c i a s s ) 。 我们定义下面的参数考察组成规则的性能。 定义2 3 规则支持度为s 。( ，) ，规则支持度是表示训练集中满足规则条件的记录的比 例。规则的条件是定义在论域u 上的模糊集合。支持度表示这个模糊集合在u 上的 相对大小，支持度越大，规则的普遍意义越好。 定义2 4 规则正确度4 。p ) ，规则正确度是训练集中可以被规则正确分类的记录的比 例。规则的结论是定义在u 上的一个模糊集合，而正确度是表示条件的模糊集合是结 论的模糊集合子集的程度或者条件推出结论的正确程度。当正确度为1 时，称规则恒 真，此时只要条件为真，结论匣为真。 定义2 5 规则覆盖度ep ) ，覆盖度是表示结论的模糊集合包含于条件的模糊集合的 程度或者结论暗示条件的正确程度。当覆盖度为l 时，称规则是完备的，此时条件为 真是结论为真的必需条件。 定义2 6 规则相对贡献c 。，用来衡量规则在分类模型中的贡献大小。 因为规则中条件属性的个数可以少于训练例子条件属性的个数，我们定义，对于规 则r 5 和r b ，当规则r 4 长度大于规则r b ，而且规则r b 中包含的条件属性规则r 8 全部包 含且两者结论类别相同，此时我们认为规则r b 包含规则r 4 。例如： p ：i fa li s f l a n da 2i s f 2a n da 3 i s f 3t b e nc l a s s i sc 一：i fa ii s f l a h da 2i s f 2 1 b e nc l a s si s c 最后我们定义两个参数来衡量分类模型的性能。我们用n 表示测试集合中所有的 例子数，p 表示可以被分类模型分类的例子数，q 表示测试集合可以被分类模型正确 分类的例子数。 定义2 7 覆盖度c v 5 = p n ，c v s 反映分类模型的完备性； 定义2 8 正确度c 0 8 = 。p ，c 0 8 反映了分类模型的正确性； 分类模型s 的性能不仅依赖其组成规则的性能，而且规则之间的相互合作效果也 影响它的性能。 1 1 数据挖掘技术的研究与实现 2 2 挖掘技术 2 2 1 常用的分类模型挖掘技术 决策树 1 5 5 2 1 构造一个决策树分类模型，它的输入是一组带有类别标记的例子，构造的结果是 一棵二叉或多叉树。二叉树的内部节点( 非叶子节点) 一般表示为一个逻辑判断，如 形式为( 氐= v i ) 的逻辑判断，其中a i 是属性，v i 是该属性的某个属性值；树的边是逻 辑判断的分支结果。多又树( 如3 ) 的内部节点是属性，边是该属性的所有取值， 有几个属性值，就有几条边。树的叶子节点都是类别标记。 构造决策树的方法是采用自上而下的递归构造。以多叉树为例，它的构造思路是， 如果训练例子集合中的所有例子是同类的，则将之作为叶子节点，节点内容即是该类 别标记。否则，根据某种策略选择一个属性，按照属性的各个取值，把例子集合划分 为若干子集合，使得每个子集上的所有例子在该属性上具有同样的属性值。然后再依 次递归处理各个子集。这种思路实际上就是“分而治之”( d i v i d e a n d c o n q u e r ) 的道 理。二叉树同理，差别仅在于要选择一个好的逻辑判断。构造好的决策树的关键在于 如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例 子。 粗集 粗集( r o u g hs e t ) 理论是一种研究不精确、不确定性知识的数学工具，由波兰科 学家p a w l a k 在1 9 8 2 年提出。随着d m 的兴起，粗集理论也受到d m 研究者的重视 进而受到研究界的广泛注意。粗集和d m 关系密切，它为d m 提供了一种新的方法和 工具。首先，d m 研究的实施对象多为关系型数据库。关系表可被看作为粗集理论中 的信息表或决策表，这给粗集方法的应用带来极大的方便；第二，粗集的约简理论可 用于高维数据的预处理上以去除冗余属性从而达到降低维数的目的；第三，现实世界 中的规则有确定性的，也有不确定性的。从数据库中发现不确定性的知识，为粗集方 法提供了用武之地。第四，运用粗集方法得到的知识发现算法有利于并行执行，这可 极大地提高对大规模数据库中的知识发现的效率。文 4 0 4 3 提出基于粗集的数据挖掘 算法。 南京航空航天大学硕士学位论文 面向属性的归纳技术m 采用多维数据分析方法进行数据总结，它针对的是数据仓库，数据仓库存储的是 脱机的历史数据。它的思路是，直接对用户感兴趣的数据视图进行泛化，而不是象多 维数据分析方法那样预先就存储好了泛化数据。方法的提出者h a n 对这种数据泛化技 术称之为面向属性的归纳方法。该方法涉及的泛化操作有：属性去除操作、概念树提 升、属性闽值控制、频数传播，以及其它的数据汇集操作。原始关系经过泛化操作后 得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化 关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系 基础上生成特性规则、判别规则、分类规则，以及关联规则等。面向属性的归纳方法 的一个核心部件是属性背景知识，它表示为各个属性的概念层次树。 面向属性的归纳方法是一种通用的技术，不仅可用于关系数据库，同样可用于面 向对象数据库、空间数据库，以及其它类型的数据库。这种方法是一种泛化技术的方 法，不适用于挖掘低层次上的具体模式。 2 2 2 遗传算法【2 3 】 在d a n v i n i a n 进化论、门德尔摩根遗传学说的影响下，在7 0 年代初期，美国 m i c h i g a n 大学j o h nh o l l a n d 教授从对生物例子的研究中提出了遗传算法。遗传算法 ( g e n e t i ca j g o r i t h m ) 可以形式化描述为g a i ( j i ，p m 。v m ，r ，t ) 。其中为种群 规模。p 。= ( p 。，p ：，p 。) 为初始种群，p 。( 1 i n ) 为种群中的个体，是特定长度的二 进制串，p 。由串中二进制位( 基因) 决定。r 。， 。和v 。分别为遗传算法中的3 个基 本算子：再生( r m ：r e p r o d u c t i o n ) 、交叉( o m ：c r o s s o v e r ) 和变异( v m ：m u t a t i o n ) ，通过 这3 个基本算子就可以从一个初始种群p 。出发，产生期望的改良种群。r 是评价个 体适应度的函数，e = 1 1 ( p 。) ，表示个体p 。的适应度。r 可表示从m 到r 的映射r ：m r ，其中m 是所有个体组成的集合，r 为实数集合。t 为算法终止条件。下面介绍 遗传算法主要遗传算子。 ( 1 ) 再生操作 再生操作根据种群中的每个个体的适应度，按与适应度成比例的概率选择参与下 一代的个体，再生操作的作用效果是提高了种群的平均适应度，并是以损失种群的多 样性为代价的，它不能产生新的个体。这是一种自然选择的人工模型。 记r “为n 维实空间，则种群适应度f = ( f l ，f ) r 4 ，其中( 1 i n ) 为个 13 数据挖掘技术的研究与实现 体p ，的适应度。 定义2 9 设吼是所有种群组成的集合，种群中吼，m 是所有个体组成的集合，种 群适应度f r “，再生算予r m ：锨r “一m 定义为： r m f ) _ p 。， 其中k 为论域m 上的再生操作符；个体p p ，且按概率z 。被选择。 ( 2 ) 交叉操作 与再生算子不同，交叉算子可以产生新的个体，从而检测搜索空间中新的点。再 生算子每次仅作用于一个个体上，而交叉算子每次作用在种群中随机选取的两个个体 上。交叉算子产生两个子代串，它们一般与父代串不同，每个子代串都包含两个父代 串的遗传物质。 定义2 1 0 设l 为个体p ，的长度，n = 1 ，2 ，1 ) 为个体p 上位置指标的集合，定义 所有可能的交叉位置的集合为： 2 ( i i ) | ( i ，j ) h 佴i j ) 定义2 1 1 设z ，m 是所有个体组成的集合，个体a b ，a ，b m ，交叉算子o m ：m m 一m m 定义为： ( 气b ，z ) = a 。，b ) 其中v i 币 1 4 。= e 当疗j m ，( 门，埘) z ； l b 。 = 爿， 1 4 。 = 4 ， 其它情况 i b ：= e 4 ，b ，4 ，e 分别表示个体人b ，a 和b 中的第i 位的值。 在最简单的情况下，取z = ( k ，1 ) ) ，我们称这种最简单的交叉算子为单点交叉算子， 称k 为交叉位置。根据交叉段集合不同，还可进行多点交叉。只有经过交叉，才能出 现新的个体。正是再生和随机交叉的信息交换给予了遗传算法巨大的生命力。 ( 3 ) 变异操作 变异算子以一个很小的概率p 。随机地改变个体串上的某些位，若参数本身为二进 1 4 南京航空航天大学硕士学位论文 制编码，则变异只是简单的将l 变成。或反之。 定义2 1 2 设q 冲昭) 是可的幂集，变异算子v 。：m q m 定义为 v 。) ( ) = a 其中v i h ： 4 一 ，当i x x q 4 = a 其它情况下 比之再生和交叉算子，变异算子是遗传算法中次要的算子。它在恢复种群多样性 方面具有潜在的作用。在人工遗传系统中，变异操作是防止重要特征过早丢失的一种 保险策略。通过对生物例子的研究，还可以总结出许多其他遗传操作符，然而再生、 简单交叉和变异己被证明，他们不仅计算简单而且处理许多重要的优化问题时也非常 有效。遗传算法的主要操作步骤如下： a ) 初始化第o 代种群p 。( 一般随机产生) ； b ) 对种群p 。迭代执行步骤( i ) ( i v ) ，直到满足终止条件t ； ( i ) 依概率选择遗传算子r 。o 。，v 。； ( i i ) 计算种群中每个个体的适应度= r ( p 。) ，1 i ； ( i i i ) 根据种群中每个个体的适应度选择参与产生下一代的个体； ( i v ) 将所选择的遗传算子作用于选择的个体，并根据所产生的新个体更新 种群； c ) 将任意一代中出现的最好结果指定为遗传算法的结果。 数据挖掘技术的研究与实现 第三章连续属性离散化 3 1 连续属性离散化定义 在机器学习和数据挖掘的研究中，大多数算法都是以离散值为处理对象的，一般 都需要一个离散的属性空间。然而现实世界的许多问题却涉及大量的连续属性，因此 连续属性离散化的研究相当重要。在本文提出的分类规则挖掘过程中也需要连续属性 离散化。离散化有两个原因：一方面，可以将那些原来仅适用离散空间的算法扩展到 连续属性空间，使其能处理现实世界问题；另一方面，好的离散化方法可以大大减少 学习时间。连续属性离散化定义为：通过选择适当的划分点将整个连续属性的值域划 分为一些离散化空间，同时提供确定值域中的任一个点所对应的离散化区间的计算方 法。我们将数值属性的论域离散化形成多个子区间，其中每个区间对应着一个离散的 符号( 定性语言值) 。例如，设当前考察的属性是年龄，则一种可能的离散化是 o 11 j 小孩， 1 21 7 】j 少年， 1 8 4 4 】j 青壮年， 4 5 6 9 卜 中年，【7 9 】老年。 目前人们提出了很多离散化力法：”o “”，如：长度区间法、等频区间法和基于信 息商的二元分割法等等。离散化方法可分为两种类型：不考虑带类别标记和考虑带类 别标记。离散化问题是一个典型的搜索问题，它使得分割的离散区间满足：区间内相 似性最大，而区间之间相似性最小。普通算法搜索空间仅在相邻节点之间，有时并不 能找到最佳的离散化集合，这些算法有的过于简单化，有的较为复杂，计算量大。而 遗传算法在解决搜索问题上有其它方法无法比拟的优势，它可以进行全局搜索并加快 搜索过程。因此本文通过对遗传算法应用研究，来提出一种新的离散化方法。 3 2 连续属性离散化方法 1 ) 不带类别标记离散化方法 目前常用的不带类别标记离散化方法有两种：一种是等距区间法( e q u a l 一w i d t h i n t e a l s ) ，它把连续属性取值区间等分为n 个小区间( n 是用户给定的离散值个数) ， 1 6 南京航空航天大学硕士学位论文 例如设原始区间为hb 】，则n 个等分区间为 a ，a + ( b a ) n ，【a + ( b a ) n 】，a + 2 ( b a ) 尉】， a + ( n _ i ) ( b a ) 彻，b 。第二种是等频区间法( e q u a i f r e q u e n c y i n t e a i s ) ， 它把原始区间划分为n 个小区间( n 是用户给定的离散值个数) ，使得每个小区间中 所含的数据个数近似相同。还有其它较为复杂的一类方法，如最大熵方法、各种聚类 分析方法等。 带类别标记离散化 带类别标记离散化方法是目前流行的离散化方法，这里介绍常用的归并和划分离 散化方法。归并算法的思想是：初始把属性的每个取值当作一个离散的属性值，然