（计算机应用技术专业论文）关联分类算法研究及其在医学图像数据挖掘中的应用.pdf

硕【学位论文 摘要 数据分类是数据挖掘中的一个重要课题。近年来研究提出的关联分类 ( a s s o c i a t i v ec l a s s i f i c a t i o n 简称a c ) 一一将关联规则挖掘和分类结合起来，作为 一种新的数据分类方法在数据挖掘领域引起了广泛的关注。自1 9 9 8 年出现第一个 基于关联的分类算法( c b a ) 以来，有不少学者对关联分类算法的设计及应用进 行了深入的研究。 随着医院使用计算机进行信息化，其各种医学信息数据库不断地建立。此外 又由于医学技术本身具有很强的实验性、实践性和统计性等特点，使数据挖掘在 医学诊断领域的应用具有重要的实用价值和广阔的发展前景。因此，面向医学图 像的数据挖掘技术研究成为医学和计算机科学交叉学科研究的一个十分重要的 领域。目前，面向医学图像的数据挖掘研究刚刚起步，现有的数据挖掘方法直接 应用还存在许多问题。研究和探索适于医学图像的数据挖掘方法具有重要、现实 的意义，对辅助医生进行临床诊断具有重要实用价值。 本文在分析c b a 算法的基础上，针对其存在的问题提出了一种基于属性重要 性的关联分类算法( i r a r c ) 。该算法的特点在于引入属性重要性，从而大大减 少了生成候选项目集的数目，解决了频繁项目增加时运算时问显著增加的问题， 提高了算法的效率；引入规则优先度的概念解决了规则选择的随机性。实验结果 表明，i r a r c 算法比c b a 算法有明显的优势，可以应用于大规模数据库的知识发 现中。 此外，对关联分类算法在医学图像数据挖掘中的应用进行了系统、深入地分 析研究，针对医学图像本身的特点使用f p g r o w t h 算法，解决了传统关联分类算 法在医学图像数据挖掘中有大量强模式、长模式或阈值较低时的不足；采用改进 的规则优先度的定义构造分类器。实验数据表明，该算法具有较高的精度和时效 性。 关键词：医学图像，数据挖掘，关联分类 关联分类算法研究及其在医学图像数据挖掘中的应用 a bs t r a c t c l a s s i f i c a t i o ni st h ek e yt a s k so fd a t am i n i n g a n dt h ec l a s s i n c a t i o nb a s e do n c l a s sa s s o c i a t i o nr u l e sa san e wm e t h o do fc l a s s i f i c a t i o nh a sa t t r a c t e da t t e n t i o nf r o m a c a d e m i cr e s e a r c h c o m m u n i t ya n di n d u s t r y n e l ds i n c et h en r s t a l g o r i t h mo f c 1 a s s i f i c a t i o nb a s e do na s s o c i a t i o nr u l e sw a si n t r o d u c e di n19 9 8 w i t ht h ed e v e l o p m e n to fc o n l p u t e r ，t h e r ei sag r e a td e a lo fd a t a b a s eo fm e d i c a l i n f o m a t i o n o w i n gt om e d i c a lt e c h n o l o g yh a sf e a t u r eo fe x p e r i m e n t a la n ds t a t i s t i c ， t h ed a t am i n i n gh a sw i d e l ya n dp r a c t i c a l p r o s p e c t s t h e r e f o r e ，d a t am i n i n gf o r m e d i c a li m a g eh a sb e e nan o u r i s h i n gr e s e a r c ha r e ab e t w e e nm e d i c a la n dc o m p u t e r s c i e n c en o w t h er e s e a r c ho nm e d i c a l i m a g em i n i n gh a sj u s ts t a r t e d i ti ss i g n i f i c a n t t or e s e a r c ha n df i n dp o w e r f i u ld a t am i n i n ga l g o r i t h m st h a tc a nh a n d l em e d i c a li m a g e d a t a s e t se f f e c t i v e l ya n de m c i e n t l y f u r t h e r ，i ti si m p o r t a n tt od i a g n o s i sd i s e a s ef o r 。 d o c t o r t h i sp a p e ra i m sa ta c h i e v i n gm o r ee f f e c t i v ea s s o c i a t i v ec l a s s i f i e r sb a s e do n i m p o r t a n c eo fa t t r i b u t e ( i r a r c ) c o m p a r e dw i t ho t h e ra l g o r i t h m s ，t h i sa l g o r i t h m w a sp r o p o s e dt oa p p l yt h ei m p o r t a n c eo fa t t r i b u t em e a s u r et ot h eg e n e r a t i o no f c a n d i d a t ei t e m s e t s m o r e o v e r ，i nt h ep r o c e s so fb u i l d i n gc l a s s i f i e r ，an e ws t r a t e g yt o r a n kc l a s sa s s o c i a t i o nr u l e si no r d e rt od i s c r i m i n a t eb e t w e e nr u l e sw h i c hh a v e i d e n t i c a lc o n f i d e n c e so rs u p p o r t sa n dt op r u n er u l er e d u n d a n c ya n dc o n f l i c t sw a s p r o p o s e d t h et h e o r e t i c a la n a l y s i sa n de x p e r i m e n tr e s u l t si n d i c a t et h a tt h i sa l g o r i t h m i so fh i g h e ra p p l i c a t i o ne f 矗c i e n c yt h a nc b a a l g o r i t h m t h i st h e s i ss t u d i e sa n da n a l y s e st h et e c h n i q u ea n da p p l i c a t i o no fa s s o c i a t i v e c l a s s i n c a t i o nr u l e sm i n i n gi nm e d i c a li m a g em i n i n gs y s t e m a t i c a l l ya n dd e e p l y t h i s a l g o r i t h mw a sp r o p o s e dt oa p p l yf p g r o w t ha l g o r i m m st os o l v em es h o r to fd a t a m i n i n gw h i c hi n v o l v ea 鲈e a tm a n yo f1 0 n gp a t t e r n ，s t r o n gp a t t e r na n dl o wt h r e s h o l d a n ds e c o n d l y ，a p p l y i n gan e ws t r a t e g yt or a n kc l a s sa s s o c i a t i o nr u l e si np r o c e s so f b u i l tac l a s s i f i e r e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o di se f f i c i e n ta n da c c u r a t e k e yw o r d s ：m e d i c a ii m a g e ；d a t am i n i n g ；a s s o c i a t i v ec l a s s i f i c a t i o n i i 硕十学位论文 插图索引 图1 1 频繁项集与非频繁项集的边界4 图3 。1 关联分类模型1 9 图3 2 存储频繁模式信息的f p t r e e 2 2 图3 3 表3 2 产生的c r t r e e 2 4 图4 1c b a 和i r a r c 内存使用对比3 3 图4 2c b a 和i r a r c 运行时间对比3 4 图5 1 医学图像分类处理的过程3 7 图5 2 图像预处理3 8 图5 3m i a s 被均分为1o 份的正预测值和负预测值4 2 i i i 关联分类算法研究及其在医学图像数据挖掘中的应用 表格索引 表3 1 所示的训练数据集t 2 2 表3 2 从训练集中发现的规则。2 4 表4 1 气象信息数据库3 2 表4 2 精度对照表3 3 表5 1 各种医学数据库的知识发现计算机辅助诊断系统特性一览表3 6 表5 2a p r i o r i 算法与改进算法的比较4 1 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 ，卞 作者签名：吻月5 维日期：汐哆年多月乡日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：谰；覆 刷醛砂一f 1 1 日期：砌彦年 日期：砌彦年 6 只日 乡月，日 硕1 学位论文 第一章绪论 1 1 研究背景与意义 早在1 9 8 2 年，趋势大师约翰奈斯比在他的首部著作大趋势中就提到： “人类正被信息淹没，却饥渴于知识。”在这个信息爆炸的时代，面对着浩瀚无 垠的信息海洋，人们呼喊着一个能将浩如烟海的数据转换成知识的技术。数据挖 掘( d a t am i n i n g ，d m ) 就是在这个背景下产生。数据挖掘【2 】是从大量的、不完 全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道 的、但又是潜在有用的信息和知识的过程。其中分类是数据挖掘应用研究的重要 内容之一。最近几年的研究提出了一种称作关联分类的新的分类方法，将关联规 则挖掘和分类集成起来。关联分类首先用关联规则算法，生成所有分类关联规则 ( c l a s sa s s o c i a t i o nr u l e ，c a r ) 集合，然后从中选取一部分具有较高质量的规则集 合。最后进行分类。与传统的决策树算法比较，关联分类具有分类预测准确度高 的特点，因此在数据挖掘领域引起了广泛关注。 随着科学技术的发展，我们获取各种数据的能力很快，需要挖掘的数据库通 常极为庞大，如果采用一些基本算法，运算复杂度会很高，需要占用大量时间和 空间，这些将导致用户满意度下降，从而限制数据挖掘的应用和发展。所以，数 据挖掘的核心步骤是算法的设计阶段，算法是影响数据挖掘效率的最重要的因 素。因此，研究设计出快速高效的挖掘算法能有效提高数据挖掘的效率，扩展数 据挖掘的应用范围，对于数据挖掘具有十分重要的意义。 近年来，生物医学工程研究有了迅猛发展，测量仪器技术的提高使得大量医 学信息的存储成为可能，然而同时也带来了一个新的课题：如何充分利用这些医 学数据和医生诊断经验，在计算机的帮助下，发现隐藏在这些海量数据背后的新 的有价值的医学信息。为了解决这个问题，医学图像数据挖掘应允而生。医学图 像数据挖掘既有一般数据挖掘的共性，又要求具有较高的分类准确率和较低的算 法复杂度。虽然国内外对医学图像的数据挖掘的研究己经取得了很多成功的经 验，但由于目前常用于医学图像挖掘的算法仍停留在对决策树、神经网络和关联 规则等传统的数据挖掘算法的直接使用上，目前的方法都存在着某些不足之处， 而不断发展的新学科新技术为医学图像的数据挖掘又带来了新的研究途径和方 法。 因此，本文对关联分类挖掘算法及其在医学图像数据挖掘中的应用进行探索 性研究，提出了基于属性重要性的关联分类算法；针对医学图像本身的特点使用 关联分类第法研究及j e 神：医学图像数据挖掘中的鹰用 f p g r o w t h 算法，解决了传统关联分类算法在医学图像数据挖掘中有大量强模式、 长模式或阈值较低时的不足。本文对于提高数据挖掘效率和解决分类的时效性和 准确性问题，均具有重要的理论意义和应用价值。 1 2 数据挖掘技术的理论与发展 数据挖掘是一项从数据库中智能地、自动地提取出有价值的知识和信息的研 究技术，是知识发现( k n o w l e d g ed i s c o v e r yi l id a t a b a s e ，简称k d d ) 过程中的 一个特定的关键步骤【3 1 ，是当前涉及人工智能和数据库等学科的一个相当活跃的 研究领域。19 8 9 年，第一届数据库知识发现国际学术会议在美国底特律市召开， 首先提出了k d d 这个术语。1 9 9 3 年a g r a w a lr 等人在a c ms i g m o d 国际数据 管理会议上提出第一个数据挖掘算法a i s ，这是一个挖掘频繁项集和关联规则的 算法。从此，数据挖掘研究成为计算机领域的一个热门课题，国内外众多研究机 构和学者发表了许多研究成果和论文，数据挖掘的商业软件也相继问世。 1 2 1 数据挖掘的目标和主要研究内容 数据挖掘的目标是发现有用的知识( 即概念、规则和模式) 。数据挖掘主要 研究内容包括以下六个方面【2 j ： 1 关联分析( a s s o c i a t i o na n a l v s i s ) ：是分析数据集中某些实例共同满足的、 存在于属性之间的关联性。关联分析可以揭示同类实例间未知的依赖关系。依据 这种关联性可以从一个实例来推断另一个实例的信息。近几年对关联规则的研究 内容较多。现在，关联规则的挖掘已经从单一概念层次关联规则的发现发展到多 概念层次关联规则的发现并把研究的重点放在提高算法的效率和规模可收缩性 上。目前，人们对于定量关联规则以及其他种类的关联规则的发现研究较为深入， 提出了关联规则的兴趣性的概念。与此同时，在提高挖掘过程的效率方面也作了 不少的研究，例如：减少对于数据库的搜索次数，适当放松对精确度的限制，通 过数据采样极大地提高了数据挖掘的效率：当数据库经常变动时，采用增量更新 技术来防止对于整个数据库的重新采掘；对数据挖掘进行并行化等等。 2 数据分类( c 1 a s s m c a t i o n ) ：数据分类按照一组数据对象的特征给出数据 对象数学划分的过程，是数据挖掘的重要研究内容之一，同时，也是其它诸如人 工智能、模式识别、人工神经元网络等学科的重要研究内容，并且有丰富的结果 和广泛的应用。利用分类模型能够依据未知实例的特征来推断其类别，可见，分 类模型具有预测和决策功能。数据分类的方法很多，包括决策树方法、统计学方 法、神经网络方法、最近邻方法等等。 3 聚类分析( c 1 u s t e “n ga n a l y s i s ) ：聚类是识别一组数据对象的内在规则， 从而将对象分组，构成相似对象类，以导出数据的分布规律，进一步说是试图去 2 硕 j 学位论文 发现隐含在一组混杂的数据对象的分类规则，这种隐含分类规则的分类规则可能 是非常难于理解的。近年，聚类开始在大型数据库中得到研究。 4 预测( p r e d i c t i o n ) ：依据历史数据和现有数据推测未来发展趋势的技术。 预测方法分为两类：定性预测和定量预测。定性预测又称直观预测，受人为因素 的影响很大。定量预测又称因果分析法( 如回归分析法) 、时间序列分析法( 如 移动平均法、平滑指数法) 。除了时序预测外，广泛使用的另一种预测技术就是 分类预测。预测作为智能决策的一种手段将在未来的商业智能中发挥重要的作 用。 5 偏差检验( d e v i v a t i o nd e t e c t i o n ) ：偏差检验技术用于提取数据中的偏差 和异常。令人感兴趣的偏差主要有三种：不符合标准的异常；与父类或兄弟 类有很大的异常；某个域( 如时间、空间) 内相邻两个区间的信息演变，例如， 某个地区两个季度销售收入的变动。 6 数据可视化( d a t av i s u a l i z a t i o n ) ：数据可视化以更形象、更直观的二维 三维图形来展示数据挖掘所得出的知识或模式，使对图表功能的拓展。 1 2 2 数据挖掘的理论与技术 数据挖掘涉及统计学习【4 1 、机器学习【5 1 、数据压缩【6 1 以及人工神经网络【7 1 等 方面的理论。在数据挖掘中，应用较广泛的技术来自机器学习和统计学习领域。 常用的统计方法有模糊集8 1 、支持向量机、贝叶斯网络9 1 、粗糙集理论【1 0 1 1 1 等。 常用的机器学习方法包括规则归纳、决策树、范例推理和遗传算法。在数据挖掘 技术方面，主要探讨与分类关联规则相关的技术。 1 关联规则挖掘： 关联规则是描述在一个交易中物品之间同时出现的规律的知识模式，更确 切的说，关联规则是通过量化的数字描述物品x 的出现对物品y 的出现有多大 的影响。以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发 现这些数据中常常隐含形式如下的规律“购买篮球的顾客中有7 0 的人同时 购买篮球运动服，所有交易中有4 0 的人同时购买篮球和篮球运动服”等。这些 规律即关联规则。 a g r a w a l 等人【1 2 】于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联 规则，并设计了一个基本算法。其核心是基于频集理论的递推方法，将关联规则 的设计分解为两个子问题：发现频集。这个子问题是最重要的，开销最大。因 此，各种算法主要致力于提高发现频集的效率。根据所获得的频繁项集，产生 强关联规则。根据定义这些规则必须满足信任度阈值。由于步骤中的操作极为 简单，因此挖掘关联规则的整个性能就由步骤所决定。该算法利用了如下两个 基本性质： 3 关联分类算法研究及其才：医学图像数据挖掘中的廊用 性质1 ：任何频集的子集必定是频集。 性质2 ：任何非频繁项集的超集必定是非频繁项集。 此后，j h a n 等人提出了不产生候选频繁项集的方法：f p 树频集算法【1 3 】。 该算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进 一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随后再将f p t r e e 分 化成一些条件库，每个库和一个长度为1 的频集相关，然后再对这些条件库分别 进行挖掘。f p g r o w t h 只需对数据库进行两次扫描，而且避免了产生大量候选集 的问题。实验表明：f p g r o w t h 对不同长度的规则具有很好的适应性，同时在效 率上较a p r i o r i 算法有很大的提高。 对于包含m 个布尔属性的数据集，候选频繁项集的搜索空间为2 m 。例如，对 于数据集包含五个布尔属性a ，c ，d ，t ，w 的数据集，采用自底向上的方法生 成频繁项集。先扫描数据集，产生频繁卜项集；由频繁卜项集生成候选2 一项集； 在数据集上对候选项集计数，得到频繁2 一项集，以此类推，由频繁k 一1 项集， 产生候选k 项集。理论上，五个布尔属性最多生成2 5 = 3 2 个组合方式。图1 1 列出 了除空集外的其中31 种组合方式。使用下划线描述的项集为非频繁项集。对于给 定支持度阈值，再频繁项集和非频繁项集之间存在一个明显的边界。这是因为频 繁项集存在反单调性，即如果一个项集不是频繁项集，那么他的所有的超集都不 可能成为频繁项集。 盘旦工燮 图1 1 频繁项集与非频繁项集的边界 关联规则挖掘属于求解集和子集问题，是典型的n p 难问题。当数据集中实 例个数较多时，测试一个候选项集是否为频繁项集的时问开销非常大。特别是当 数据集中属性较多时，项集之间的组合产生大量候选频繁项集，在数据集上测试 候选项集消耗大量系统资源，这种现象称为关联规则生成过程中发生的候选项集 “组合爆炸效应 。 2 数据分类： 4 硕l j 学位论文 目前构建分类系统的研究热点主要有：决策树( d e c i s i o nt r e e s ) 、粗糙集 ( r o u g hs e t ) 、贝叶斯方法( n a i v eb a y e s ) 、k 近邻( k n e a r e s t n e i g h b o r ) ，神经网络 n n e t ( n e u r a ln e t w o r k ) ，遗传算法( g e n e t i ca l g o r i t h m ) 等。 1 ) 决策树：该方法利用信息论的原理建立决策树。实用效果好，可高度自 动化地建立起易于为用户所理解的模型，系统具有较好地处理缺省数据及带有噪 声数据等能力。他最大的优点是在学习过程中不需要使用者了解很多背景知识。 这样只要训练事例能够用“属性一值”的方式表达出来，就能使用该算法进行学习。 最早的决策树算法是由q u i n l a n 提出的基于信息熵的i d 3 【1 4 】算法。后来q u i n l a n 对上述算法作了改进，提出了c 4 5 【1 5 】。为了适应大规模数据集的处理，又对它进 行了改进，其中 s l i q ( s u p e r v i s e dl e a r n i n gi nq u e s t ) 1 6 】和 s p r i n t ( s c a l e a b l e p a r a l l e l i z a b l ei n d u c t i o no fd e c i s i o nt r e e s ) 1 。7 】是比较有代表性的两个算法。 2 ) 粗糙集：是一种刻画不完整性和不确定性的数学工具，能有效地分析和 处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示 潜在的规律。由z p a w l a k 【lo j 于1 9 8 2 年提出，认为知识是一种分类的能力，在机 器学习、知识获取、决策分析、数据库的知识发现、专家系统、决策支持系统、 模式识别、模糊控制及其他各个方面得到了很好的应用。其基本思想是，将数据 库中的属性分为条件属性和决策属性，对数据库中的元组根据各个属性不同的属 性值分成相应的子集，然后根据条件属性划分的子集与决策属性划分的子集之间 的上下近似关系生成分类规则。 3 ) b a y e s 分类算法：是一类利用概率统计知识进行分类的算法，如n b ( n a i v e b a y e s ) 算法。主要利用b a y e s 定理来预测未知实例属于各个类的可能性，选择可 能性最大的一个类作为该实例的最终类。由于贝叶斯定理的成立本身需要一个很 强的独立性假设前提，然而这种假设在实际应用中难以成立，因此贝叶斯算法的 分类准确性难以得到保证。为此出现了不少改进b a y e s 分类的算法。如r o n k o h a v i 【1 8 】采用一个结合决策树与b a y e s 分类的混合方法，提高了简单b a y e s 分类器 的准确度。 4 ) k 最近邻分类：k n n 分类基于类比学习原理。对于具有n 个特征的实例， 每个实例的特征构成一个n 维向量。通过计算两个n 维向量的欧几里德( e u c l i d ) 距 离度量未知实例与训练实例之间的相似性。对于给定的未知实例，搜索最接近它 的k 个训练样本。未知实例的类标签由k 个最近邻中最公共的类决定。可见，k n n 方法没有明确的训练阶段，每个训练数据都是模型的一部分。当训练数据集较大 时，计算速度慢，因此，k n n 方法不适合大规模数据挖掘。 5 ) 基于软计算的分类：主要指基于遗传算法和入工神经网络的分类学习。 人工神经网络不适合离散型数据分类，而且目前尚未出现对神经网络学习模式做 出清楚解释的方法。然而对于决策支持系统而言，知识的可理解性是至关重要的。 5 关联分类算法研究及j e 神：医学图像数据挖掘中的应用 因此，从智能决策的角度考虑，基于神经网络的数据挖掘技术存在难以克服的缺 点。 6 ) 关联分类：是一种利用关联规则进行分类的新技术。关联分类包括两个 步骤：首先发现规则结论为类标签的所有分类关联规则( c 1 a s sa s s o c i a t i o nr u l e s ， 简称c a r s ) 。然后从已发现的c a r s 中选择分类能力强的规则来覆盖训练集。与 传统的决策树算法比较，基于关联的分类具有较高的分类预测准确度，但一般的 关联分类算法存在系统资源消耗大、执行效率低的问题。 1 2 3 数据挖掘的应用领域与发展前景 当前数据挖掘应用主要集中在电信、零售、银行、保险、基因工程、网络日 志分析等方面，并逐步扩展到制造业、农业、电子政务、教育、软件工程、智能 交通和军事研究等领域，以下通过一些具体的例子加以说明。 1 零售业中的客户购买行为分析：这种应用最早出现在美国，超市利用数 据挖掘从售货数据记录中发现购买商品的关联特性。利用数据挖掘得到的知识来 调整关联商品的摆放位置，既方便了顾客，又促进了销量。在线购物活动中，通 过提醒顾客是否购买关联商品，同样也促进了销量。 2 银行信用卡业务智能数据分析：例如美国花旗银行( c i t i b a n k ) 利用数 据挖掘获得的知识区分顾客信用等级，有效地减少了恶性透支，每年避免了十几 亿美元损失。 3 电信业务中的通话记录分析：电信公司或呼叫中心通过挖掘大量通话记 录，能找出电话呼叫方是谁、被叫方是谁、通话时间有多长、电话线是否同时支 持传真和语音等细节信息。客户服务呼叫中心能利用这些信息以及客户资料挖掘 有价值的增值服务模型。这对于面向特定客户进行服务或设备销售而言是非常有 用的。 4 基于时序数据挖掘的预测：政府高层、企业决策者需要对不同级别的宏 观经济数据分析，通过时序数据库和基于时序的数据挖掘预测未来的经济走势， 进行计算机辅助智能决策。 5 电子信息的防伪检测：电子商务和电子政务系统通过训练的模式知识自 动地辨别信息真伪，防止电子帐单和印鉴等电子信息的伪造。 6 计算机网络入侵监测系统：网络安全管理部门利用数据挖掘发现的知识 检测黑客程序的入侵。在信息系统的安全管理中，采用基于规则集的访问控制技 术结合系统日志文件，借助数据挖掘技术能检测出未授权用户对受保护数据的非 法访问。 7 面向提高服务质量的w e b 结构重组：通过挖掘w e b 日志发现用户访问行 为知识，重新组织w e b 结构，提高服务质量。 6 硕l ：学位论文 总之，数据挖掘能应用于众多领域。概括起来，可以将数据挖掘应用归纳为 客户关系管理、智能数据分析、智能决策、防伪检测、入侵检测等类型。人类已 经步入信息时代，面对数据爆炸，如何快速有效地获得最有价值的信息资源，成 为企业在激烈竞争中取胜的关键。因此，与数据挖掘相关的技术和工具将面临很 好的发展前景。数据挖掘将成为继互联网之后的下一个研究热点，特别是高维、 大型、分布式数据挖掘将具有广阔的应用前景和巨大的潜在经济价值。其中，分 类预测技术作为智能决策的重要手段将在未来的商务智能中发挥重要作用。 1 3 与本课题有关的国内外研究进展 1 3 1 关联分类技术的发展 19 9 7 年，a l i 等人提出了使用分类关联规则进行分类的思想，但他们当时认 为关联规则在分类预测问题上很难有很大的进展。1 9 9 8 年，在纽约举行的数据 库知识发现( k d d ) 国际会议上，新加坡国立大学的l i u 等人提出了基于分类关 联规则( c l a s sa s s o c i a t i o nr u l e ) 的关联分类算法c b a ( c l a s s m c a t i o nb a s e do n a s s o c i a t i o n ) 【”】，从此揭开了关联分类的序幕。与传统的决策树算法相比，关联 分类具有分类准确度高的特点，因此关联分类在数据挖掘领域内引起了广泛的关 注。目前，中国、美国、加拿大等国家都设立了国家自然科学基金进行这方面的 研究，许多学者目前正在从事这方面的研究并且在分类算法方面先后相继取得了 一些成果，如c b a 【19 1 ，c a e p 【2 0 1 ，a d t 2 1 1 ，c m a r 【2 2 1 ，c p a r 23 1 ，c a a r 2 4 1 等。 下面予以简要介绍。 1 9 9 8 年，l i u 等人率先提出了基于分类关联规则的关联分类算法c b a 【”】， 该算法使用类似a p r i o r i 【l j 7 】的算法( 称为类a p r i o r i 算法) 产生分类关联规则，使 用的支持度阈值为1 ，置信度阈值为5 0 ，试验结果给出了分类误差值，并与 决策树算法c 4 5 【1 5 】进行了比较，但是该研究存在的主要问题是采用类a p r i o r i 算 法产生了大量的分类关联规则，消耗的系统资源多，为了防止过度的消耗系统资 源，算法硬性的规定挖掘的规则数量不能超过8 0 0 0 0 个，当遇到高维数据库时， 挖掘的频繁项集迅速减少，很大程度的降低了分类的精度。 1 9 9 9 年，d o n g 等人【2 0 】创立了显露模式分类算法c a e p ( c l a s s m c a t i o nb y a g g r e g a t i n ge m e r g ep a t t e r n s ) ，显露模式是指从一个数据子集转变到另一个数据 子集时，支持度发生显著变化的项集【25 | 。最初的显露模式用于分析不同类型数 据之间多个属性的对比或随时间改变的不同趋势之间多个属性的对比。显露模式 分类利用支持度差异进行分类，没有充分的理论依据来确保分类准确度，他们将 该算法与c 4 5 与c b a 等算法进行了对比，给出了在15 个数据集上不完整的分类 结果，未给出算法的平均分类精度，试验结果也未能充分说明c a e p 有何突出的 7 关联分类算法研究及其存医学图像数据挖掘中的戍用 特点，只能说明提供了一种新的关联分类方法。 2 0 0 0 年，w a n g 等人【2 1 】结合关联规则分类和决策树分类算法各自的长处，提 出了关联决策树( a s s o c i a t i o nd e c i s i o nt r e e ，a d t ) 方法。a d t 方法完全放弃支持 度阈值，仅依据置信度阈值从分类关联规则中选择分类规则，以此构建准确度驱 动的决策树，采用自底向上的闭包运算生成可信的关联规则。该算法的缺点是对 噪声特别敏感，在实际应用中，由于存在噪声，难以达到试验取得的准确度。同 年，l i 等人【2 6 】提出利用跳跃的显露模式进行分类，对显露模式分类进行了改进。 2 0 0 1 年，j l i 等人【2 。7 】给出了挖掘最小的分类关联规则集用于预测的形式化 描述。他们提出在不损失预测能力的前提下挖掘最小的分类关联规则集。然而， 他们并没有给出试验数据比较最小规则集与完全分类关联规则集的预测能力。而 且，他们未能与其他典型的关联分类算法比较，在这种情况下提出算法在不损失 准确度的前提下产生最小分类关联规则集的论点缺乏足够的证据。同年，w l i 等人【2 2 】提出了基于多个分类关联规则的分类算法c m a r ( c l a s s m c a t i o nb a s e do n m u l t i p l ec l a s s a s s o c i a t i o nr u l e s ) ，该算法使用改进的频繁模式增长法f p g r o w t h 来挖掘关联规则，使用基于权重的多个强关联规则来确定新实例的类标签，实验 结果表明分类准确度优于c b a 算法。然而，该算法存在两个问题：第一，基于 f p g r o w t h 【1 3j 的关联规则挖掘尽管比a p r i o r i 快，但f p g r o w t h 不适合高维、大型 的数据库，而且该算法的内存消耗比较大，在大规模的数据库上不易实施。第二， 强关联规则在分类预测中的权重选择标准很难确定。 2 0 0 2 年，b a r a l i s 等人【2 8 】提出了一个懒的( l a z y ) 分类关联规则剪枝方法， 该方法迭代的去除产生错误分类的所有规则，分类经过两遍进行，并在2 6 个 u c i 【29 】数据集上进行了实验，结果表明该方法提高了分类精度。然而，该方法应 用于大规模数据集时会面临执行性能问题，因为在大规模数据集上挖掘全部分类 关联规则实际是不可行的。l i 等人【30 】对关联分类的鲁棒性进行研究，提出使用 k 个最优的规则集增强分类预测的可靠性，当测试数据集遗失某个属性时，其它 k 1 个规则能担任分类任务。这个特性是关联分类相对于决策树来讲最显著的优 点之一。但该算法的缺点是分类规则集庞大、模型的可理解性低。l i 等人【3 l 】提 出了挖掘最优的分类关联规则，最优的分类关联规则是指具有与完全分类关联规 则集同样预测能力的最小规则集。通过使用最小规则集，而不是完全规则集可以 减少挖掘分类关联规则集的时间，他们使用了自底向上的闭包特性，对弱规则剪 枝，避免挖掘弱规则。实验结果表明该算法挖掘的规则数是完全分类关联规则个 数的l 17 。实质上，与c b a 相比，上述算法没有显示出多少优越性。同年，李 勃【3 2 】等人研究了基于关联规则图像的分类；r u s h i n g 等人f 3 3 】研究了基于关联规则 的图像特征分割。 2 0 0 3 年，y i n 【2 3 】提出了一个称为预测型关联规则的分类算法c p a r ，避开了 8 硕 学位论文 使用资源消耗大的关联规则发现算法。采用贪婪算法直接从训练数据集中挖掘关 联规则，规则的支持度阈值设置为5 。c p a r 算法继承了一阶归纳学习算法f o i l 的思想，采用基于信息熵的方法选择最优的5 个规则用来分类一个实例。在预测 时使用5 个规则测试新实例的类标签，因此c p a r 分类器的规则数很大。c p a r 方法产生的规则数小于c m a r ，其分类准确度与c m a r 相当。l i u 等人【3 4 】针对 数据有噪声和类分布高度不均匀的情况提出了完全分类关联规则集给未知实例 评分( s c o r e ) 的方法来提高分类准确度。在他们的方法中，首先挖掘所有分类 关联规则，所以能给出所讨论问题的完整视图，利用完整的规则集能准确地估计 新实例的类标签。然而这种方法实用性差，其缺点主要表现在两个方面：第一， 分类过程需要利用所有分类关联规则，分类器的体积非常庞大。第二，这种方法 只适用于小规模数据瓦据，在大规模数据集上，利用低支持度阈值挖掘所有分类 关联规则的计算开销大得惊人，特别是当数据集的属性个数多，属性值域规模较 大时，需要对数据集进行多次扫描。实际上，当数据集属性个数较大时，挖掘完 全的分类关联规则集属于n p 一难问题。m e n n i s 等人【”】研究了c b a 算法在空间 时态数据挖掘中的应用，邹晓峰等人【36 j 研究了模糊分类关联规则的挖掘，y a n g 等人【3 7 j 提出了基于证据权重( w e i g h to fe v i d e n c e ) 的关联分类。 d a v y 等人p 8j 在2 0 0 3 。2 0 0 4 年期间，研究了对c b a 算法的改进，提出了一个 新的关联分类规则后件选择框架，并提出了一个称为暗示强度的指标来评价分类 关联规则质量，以提高分类预测的准确度。然而，他们在比较该算法和c b a 算 法时只是选择了l6 个u c i 数据集。 2 0 0 4 年，出现了基于正、负关联规则的关联分类算法【3 9 】。然而同时挖掘正、 负规则会降低算法的执行性能。文献【40 】对关联分类支持度进行了专门的研究， 发现采用类a p r i o r i 算法挖掘关联规则时，支持度对于分类的影响较大。 许孝元等人【4 1 】在2 0 0 4 年国际计算机与信息科学学会( a c i s ) 上提出了由置 信度主导的，基于置信度和支持度加权和的分类关联规则质量评价函数。将该函 数应用于基于遗传算法的关联分类取得了很好的效果，该函数显著优于基于灵敏 度和选择性乘积的传统分类规则的质量评价函数。同年在由i e e e 主办的“机器 学习与控制论国际会议上许孝元提出利用原子型分类关联规则构建分类器的 思想，该算法分类准确度高，执行速度快，比较适合大规模的数据库。 2 0 0 5 年w a n g 提出h a r m o n y 【42 | ，它直接挖掘覆盖样例置信度最高的规则。 2 0 0 6 年a d r i a n ov e l o s o 【4 3 】等提出的1 a z y 关联分类。 2 0 0 7 年a r u n a s a l a m 【4 4 】提出了适用与类不平衡数据上的关联分类。 可见，自1 9 9 8 年至今，关联分类的研究及应用从未间断，而且关联分类技 术的研究朝着追求高的分类准确度、有效的剪枝、减少冗余规则、提高计算机性 能的方向发展，这类的研究一直非常活跃。 9 关联分类算法研究及其神；医学图像数据挖掘中的感开j 1 3 2 关联分类存在的问题 通过上一节的分析，与传统的分类算法相比，基于关联规则的分类技术在总 体上具有分类准确度高，鲁棒性好的优点。作为一种新的分类算法，关联分类还 存在很多需要改进的地方。目前，一般关联分类算法存在以下一些问题：资源 消耗大：在挖掘大规模数据集时，c p u 时间和内存消耗问题更突出。规则剪 枝难：如何评价分类规则的质量，如何从大量关联规则中提取有效的分类规则。 分类模型较复杂：如何减少分类规则的数量，提高单个规则的推广能力，增强 规则的预测功能和可理解性。一般关联分类产生庞大的分类器，不利于分类知识 的理解，降低了数据挖掘的能力。 1 4 本文的主要研究工作 本文围绕关联分类挖掘技术的改进以及关联分类技术在图像数据挖掘中的 应用开展了研究，主要包括以下三点： 1 对关联分类算法进行了全面地分类、归纳和总结，对关联分类的典型 挖掘算法及其基本思想进行详细地归纳、分析和研究，对各个算法的差别进行客 观地比较，为本文提出的关联分类的改进算法建立理论前提。 2 对经典关联分类算法c b a 进行了详细的分析，针对存在的问题提出了一 种基于属性重要性的关联分类算法，一是将粗糙集中属性重要性的概念引入到类 别关联规则挖掘过程中，简化了组合项目集的数目，有效的节省了算法执行的时 间和空间。二是在构造分类器时，改进了规则优先度的定义。根据对u c i 中7 种数据集的测试表明，改进算法对于大多数数据集的测试得到的分类准确率令人 满意。 3 针对关联分类方法用于图像数据挖掘的特点，本文在对相关工作进行深 入分析的基础上，提出了一种基于f p g r o w t h 的改进算法。该方法通过挖掘训练 数据中的频繁项集建立规则集，利用c r t r e e 存储规则，然后通过规则优先度来 建立分类器。实验结果表明，本方法具有较高的分类精度和时效性。 1 5 本文的组织 本文的具体组织结构如下： 第一章、绪论。本章主要介绍了本文的研究背景，数据挖掘的发展和现状， 关联分类挖掘的国内外研究现状。阐述了本文主要研究工作和组织结构安排。 第二章、基本理论与概念。本章详细介绍了关联分类技术的有关概念和形式 化描述、并对于分类问题进行了详细阐述。 第三章、关联分类挖掘算法。本章主要介绍了两种方法：基于