（计算机应用技术专业论文）基于概念格的序列模式发现研究与实现.pdf

基于概念格的序列模式发现研究与实现 摘要 概念格是一种完备的数学模型，描述了概念内涵与外延之间以及泛化与例 化之间的关系，因而适用于数据和知识的表示以及包括分类、关联、序列和聚 类等多种知识发现问题的描述。随着数据规模的迅速增长，概念格的分布式构 造成为重要的研究内容。本文研究了概念格的分布式并行构造方法和概念格模 型应用于序列模式挖掘时的约简算法，以提高算法的效率，使得算法适用于更 大规模的数据库。 本文的主要工作如下： ( 1 ) 研究了一种基于索引的概念格分布式构造方法一一l c b i 。构造时主站 点先将形式背景划分并发送至从站点，从站点建好子格后发送回主站点进行合 并。合并时主站点找出当前插入概念的极大相关概念后自项向下并行地搜索， 直至找出它们两两间的交叉子概念。插入时只需比较极大相关概念和它们的交 叉子概念，以减少比较的范围，提高建格效率。 ( 2 ) 研究了一种基于概念近似度约简的序列模式挖掘算法。该算法基于概 念近似度的定义，先对交易数据库进行建格，再约简满足近似条件的概念，以 减少相似的频繁卜序列的数量，从而减少总的相似频繁序列的数量。实验证明， 挖掘海量数据时，在允许一定误差的前提下，该算法显著地提高了算法的效率 和挖掘结果的可理解性。 ( 3 ) 设计并实现了基于概念格的序列模式挖掘原型系统g c l k d d 。该系统包 括数据预处理模块、概念格构造模块、概念格约简模块、序列模式挖掘模块， 可以完成基于概念格和约简概念格的序列模式挖掘任务，也可以作为平台进行 相应扩展。 关键词：知识发现；数据挖掘；概念格；分布式构造；序列模式挖掘 r e s e a r c ha n di m p l e m e n to i ls e q u e n t i a lp a t t e r nm i n i n g b a s e do nc o n c e p tl a t t i c e a b s t r a c t c o n c e p tl a t t i c ei sap e r f e c tm a t h e m a t i c a lm o d e lw h i c hd e s c r i b e sk n o w l e d g e w i t ht h er e l a t i o nb e t w e e nt h ei n t e n s i o n sa n de x t e n s i o n so fc o n c e p t s ，a n dt h e r e l a t i o nb e t w e e nt h eg e n e r a l i z a t i o na n ds p e c i a l i z a t i o no fc o n c e p t s i t sg o o dt o s h o wt h ed a t aa n dk n o w l e d g ea n dd e s c r i b em a n y q u e s t i o n so fk n o w l e d g ed i s c o v e r y , s u c ha sc l a s s i f i c a t i o n ，a s s o c i a t i o nr u l e s ，s e q u e n t i a lp a t t e r n sa n dc l u s t e r i n g a st h e s i z eo fd a t ag r o w i n gf a s t ，t h ed i s t r i b u t e dc o n s t r u c t i n go fc o n c e p tl a t t i c eb e c o m e sa n i m p o r t a n tr e s e a r c hs u b j e c t i nt h i sd i s s e r t a t i o n ，t h ed i s t r i b u t e d p a r a l l e lc o n s t r u c t i o n o fc o n c e p tl a t t i c ea n dt h et h es u b je c ya b o u tr e d u c t i o ni nt h es e q u e n t i a lp a t t e r n s m i n i n gb a s e do nt h ec o n c e p tl a t t i c ea r et h em o s ti m p o r t a n ts t u d yd o m a i n s t h e o r y a n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h e yo u t p e r f o t nm u c hb e t t e rt h a nt h eo t h e r s w h e nd e a l i n gw i t hd e n s e n e s sc o n t e x t t h ec o n t r i b u t i o n so ft h ed i s s e r t a t i o na r ea sf o l l o w s ： ( 1 ) ad i s t r i b u t e da l g o r i t h mf o rc o n s t r u c t i n gc o n c e p tl a t t i c eb a s e do ni n d e xw a s p r o p o s e d t h ec o n s t r u c tp r o c e s sw a sf o l l o w ：f i r s t ，t h ec o n t e x tw a sc u tt o m u l t i - c h i l dc o n t e x t sb yp r i m a r ys t a n di n l i n e ，t h e r e f o r et h e yc a nb es e n tt o s e c o n d a r ys t a n d si nl i n e ，a n dt h ec o n s t r u c t e dc h i l dl a t t i c e sc a nb es e n tt op r i m a r y s t a n di nl i n et oc o m b i n e i tc a nf i n do u tt h eg r e a t e s tc o r r e l a t i v ec o n c e p t sr e f e rt ot h e i n d e xt a b l e a n dt h ep r i m a r ys t a n di nl i n ec a ns e a r c ht h ec h i l dn o d e so ft h eg r e a t e s t c o r r e l a t i v ec o n c e p t st o pd o w nt o g e tt h ec o m m o nc h i l dn o d e s i to n l yn e e dt o c o m p a r et h en e w n o d ew i t ht h ec o m m o nc h i l dn o d e s ，s ot h ea l g o r i t h mi se f f e c t i v e ( 2 ) s e q u e n t i a lp a t t e r n sm i n i n gb a s e do nc o n c e p t ss i m i l i t u d ed e g r e er e d u c t i o n w a sp r o p o s e d t h ed e f i n i t i o no fs i m i l a rc o n c e p ti sp r o p o s e di n t h i s d i s s e r t a t i o n b a s e do nt h i sd e f i n i t i o n ，t h ec o n c e p tl a t t i c ew a sc o n s t r u c t e du s i n gb u s i n e s s d a t a b a s ef i r s t ，a n dt h e nw er e d u c e dt h es i m i l a rc o n c e p t s s ot h en u m b e ro fs i m i l a r f r e q u e n t 1s e q u e n c e sw i l lb es m a l l e r a n dt h en u m b e ro fa l lt h es i m i l a rf r e q u e n t s e q u e n c e sw i l lb es m a l l e rt o o e x p e r i m e n t a lr e s u l t ss h o wt h a t i to u t p e r f o r m sm u c h b e t t e rw h e nd e a l i n gw i t hl a r g ea m o u n t so fd a t ai fi g n o r es o m ed e g r e eo fe r r o r ( 3 ) ak n o w l e d g ed i s c o v e r ya r c h e t y p a ls y s t e mb a s e do nc o n c e p tl a t t i c en a m e d g c l k d dw a sd e s i g n e da n dc o m p l e t e d i ti n c l u d e dt h em o d u l eo fd a t ap r e p a r a t i o n ， c o n c e p tl a t t i c ec o n s t r u c t i o n ，s e q u e n t i a lp a t t e r n sm i n i n ga n ds oo n t h i ss y s t e mc a n d e a lw i t hm a n yt a s k so fs e q u e n t i a lp a t t e r n sm i n i n ga n de x t e n da sam o d e lo f c o n c e p tl a t t i c e k e y w o r d s ：k n o w l e d g ed i s c o v e r y ；d a t am i n i n g ；c o n c e p tl a t t i c e ；d i s t r i b u t e d c o n s t r u c t i n g ；s e q u e n t i a lp a t t e r n sm i n i n g 图2 1 图3 1 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图6 1 图6 。2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 插图清单 知识发现过程6 表3 1 所对应的概念格1 6 一个概念格l ( k ) 示例2 6 概念格l ( k i ) 2 9 概念格l ( k 2 ) 2 9 概念格l ( k ) 3 0 特征数为1 0 时算法的时间性能比较3 1 特征数为2 0 法的时间性能比较3 1 特征数为4 0 算法的时间性能比较3 2 顾客交易数据库对应的概念格3 5 概念间相似的一个示例1 3 7 概念间相似的一个示例2 3 8 概念间相似的一个示例3 3 9 概念间相似的一个示例4 3 9 大数据集的对比效果4 0 g c l k d d 系统功能模块4 2 数据预处理模块界面4 5 概念格构造模块界面4 5 概念格约简模块界面4 5 序列模式挖掘模块界面4 6 基于约简的序列模式挖掘模块界面4 6 概念格可视化展示模块界面4 6 概念格构造结果展示4 7 表3 1 表4 1 表4 2 表4 3 表4 4 表5 1 表5 2 表5 3 表5 4 表格清单 太阳系中的主要行星的信息表1 6 示例形式背景2 9 特征数为1 0 时算法的时间性能比较一3 0 特征数为2 0 时算法的时间性能比较3 1 特征数为4 0 时算法的时间性能比较3 1 顾客交易数据库一3 5 顾客交易数据库对应的形式背景3 5 概念间相似的几种情况3 7 使用小数据集的详细对比效果4 0 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金壁王些太堂 或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：谭毵签字日期：矽叮年多月沙日。 ， 学位论文版权使用授权书 本学位论文作者完全了解金起王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金月曼王些态堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：饵貉 签字日期：阳口降岁月历日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名 签字日期： 电话： 邮编： 日 致谢 研究生生活的结束意味着学生生涯的完结，虽不圆满但却没有遗憾，从此 我就要踏上“修身齐家治国平天下 的人生征程。回首往昔，一幕幕仍然是那 样清晰。 三年以来，在数据挖掘与人工智能实验室里，在合肥工业大学的校园里， 我始终都能感觉到一种朝气蓬勃、奋发有为的进取精神。能够身处民族复兴的 伟大时代，我是幸运的；能够融入一个自强不息、生机盎然的研究团队，我是 幸福的! 首先我要感谢我的导师胡学钢教授。在我攻读硕士学位期间，他严谨的治 学态度，广博的专业知识，对事业孜孜不倦的追求精神和平易近人的处世作风 给我留下了深刻的印象，也必将会让我受益终生。他不仅是学术出色的导师， 同时也是指引我前进的长者，为我将来的发展提供了极大的帮助和指导。在此 谨向我的导师致以最真挚的谢意! 同时，我要深深地感谢实验室的王德兴老师、田卫东老师、张晶老师、张 玉红老师、阙夏老师、吴共庆老师，感谢他们三年来对我的关心和帮助；感谢 谢飞、胡春玲等各位博士在学习过程中的指引和帮助；特别要感谢我的师兄卫 祥学长和其他0 5 级的师兄师姐，他们乐观向上的人生态度永远激励着我! 感谢0 6 级的全体同学! 虽然我们来自五湖四海，但是三年以来，他们与我 最近、与我最亲，在即将毕业之际，我衷心地祝愿他们前程似锦! 感谢所有师 弟师妹，祝愿他们学有所成、永远快乐! 此外，在课题研究、论文工作，以及研究生学习期间，我还得到了其它许 多老师和同学的关心和帮助，在此一并表示谢意。 最后，要衷心的感谢我的父母! 他们一直给我精神上的鼓励和物质上的支 持。他们的不断鼓励和坚定支持是我最宝贵的财富，是我不断前进的最大动力! 作者：谭拮 2 0 0 9 年3 月 第一章绪论 本章介绍了本文的研究背景和主要研究内容等，并说明课题来源，简要给 出文章的组织结构。 1 1 引言 数据挖掘和知识发现是当前涉及人工智能、数据库理论与技术、统计学以 及电子商务等学科的一个非常活跃的研究与应用领域，在金融、保险、电信、 税务和市场销售等行业具有很好的应用前景【l 】，将成为未来几年内对工业产生 深远影响的关键技术，并且其研究和应用还会形成更大的高潮。随着信息化的 不断深入，商业数据库正在以一个空前的速度增长，积累的数据呈现出高维、 海量、异构和分布等新特征 2 3 】。因此，实际应用要求数据挖掘系统具有更好的 可扩展性：如在研究某种疾病在某地的发病情况与气候的关系时需要疾病控制 数据库以及环境数据库的配合；大型跨国公司营销策略的制定需要考虑到销售 点分散等因素。传统的数据挖掘模型和算法难以满足新的应用需求，数据挖掘 面临着新的挑战。另一方面，分布式计算环境不断发展、成熟【4 】，然而其强大 的计算能力却远没有被充分利用。因此，如何在分布式计算体系中处理数据挖 掘问题引起了国内外研究者的普遍关注。目前，分布式数据挖掘已成为研究的 热点，是一个新的有现实意义的研究领域。另外，在挖掘海量数据时，由于概 念格表示信息的完备性使得挖掘结果规模十分庞大而难以理解，如何对格进行 约简以提高可理解性和算法效率也成为近年来概念格应用领域的热点问题。本 章主要介绍本文的研究背景、主要研究内容等。 1 2 研究背景 数据挖掘是在大型数据存储库中自动地发现有用信息的过程。数据挖掘技 术用来探查大型数据库，发现先前未知的有用模式已经受到人工智能与数据库 领域的广泛重视。有效地描述数据和知识及其关系的数学模型是实现数据挖掘 和知识发现的基础。由r w i l l e 于1 9 8 2 年提出的概念格( c o n c e p tl a t t i c e ) p j 是一种完备的结构，描述了概念内涵与外延之间以及泛化与例化之间的关系， 因而适用于数据和知识的表示以及包括分类、关联、特征、聚类、序列模式挖 掘等多种知识发现问题的描述。经过二十多年的发展，概念格形成了较为丰富 的理论体系，并已应用于软件工程、知识工程、信息检索和知识的经济学等领 域【6 。12 1 ，格结构的完备性使得其规模随数据库规模的增长而迅速增长，建格的 效率也因此迅速下降。同时，挖掘海量数据产生的海量结果也影响了可理解性。 而在大量的结果中，用户可能并不在意有限的误差而更加注重算法效率和结果 的可理解性。因此，如何在海量数据情况下提高建格效率和约简过于庞大的格 规模成为近年来概念格领域的重要研究内容。本文将概念格的分布式并行构造 算法和约简算法作为研究方向，以提高挖掘海量数据时概念格构造算法的效率 和挖掘结果的可理解性，从而解决基于概念格的知识发现过程中时空性能上的 局限性。 1 3 研究内容 概念格模型是一种完备的概念层次结构，具有较好的知识表示及描述知识 发现问题的能力。本文研究了概念格的分布式并行构造方法和概念格模型应用 于序列模式挖掘时的约简算法，以提高算法的效率，使得算法适用于更大规模 的数据库。 概念格的分布式并行构造方法和概念格模型应用于序列模式挖掘时的约 简算法所研究的主要内容是： ( 1 ) 研究了一种基于索引的概念格分布式构造方法一一l c b i 。该算法基于 主从式多处理器的计算机体系，其中主站点为多处理器结构。构造过程是主站 点先将形式背景横向地划分为若干个子形式背景并发送到从站点建格，从站点 将建好的子格发往主站点进行合并。合并每个概念时先对照索引表找出其极大 相关概念，然后从每个极大相关概念自顶向下并行地搜索以找出它们两两间的 交叉子概念，插入时只需比较极大相关概念和它们的交叉子概念，从而减少了 比较的范围，以提高建格效率。 ( 2 ) 研究了一种基于概念近似度约简的序列模式挖掘算法。该算法基于概 念近似度的定义，先对交易数据库进行建格，然后约简满足近似条件的概念， 减少相似的频繁1 序列的数量，进而减少总的相似的频繁序列的数量，以期降 低概念格中信息的冗余度，提高基于概念格的序列模式挖掘算法的效率和挖掘 结果的可理解性。实验证明，挖掘海量数据时，在允许一定误差的前提下，该 算法显著地提高了算法的效率和结果的可理解性。 ( 3 ) 设计并实现了基于概念格的序列模式挖掘原型系统g c l k d d 。该系统 包括数据预处理模块、概念格构造模块、概念格约简模块、序列模式挖掘模块 等，可以完成基于概念格和约简概念格的序列模式挖掘任务，也可以作为平台 进行相应扩展。 1 4 课题来源和内容组织 1 4 1 课题来源 课题来源于安徽省自然科学基金项目“基于概念格的分布式知识发现的关 键问题研究，编号0 5 0 4 2 0 2 0 7 。 2 1 4 2 内容组织 本文由七章组成： 第一章主要简述本文的研究背景和主要研究内容等，最后说明课题来源， 简要给出文章的组织结构。 第二章主要简介数据挖掘和知识发现的相关知识。 第三章主要简述概念格模型的基础理论知识，主要包括概念格的基本概念、 构造算法等。 第四章重点介绍了一种基于索引的概念格分布式构造方法一一l c b i 。理论 分析和实验充分说明l c b i 是一种正确、有效的概念格分布式构造方法。 第五章重点介绍了一种基于概念近似度约简的序列模式挖掘算法，利用构 造好的序列概念格模型进行约简，在允许一定误差的情况下提高了算法的效率 和挖掘结果的可理解性，降低了概念格模型的信息冗余度。 第六章设计并实现了基于概念格的序列模式挖掘原型系统g c l k d d ，该系 统包括数据预处理模块、概念格构造模块、概念格约简模块、序列模式挖掘模 块等，可以完成基于概念格和约简概念格的序列模式挖掘任务，也可以作为平 台进行相应扩展。 第七章是全文总结，对本文的主要研究工作进行简要地阐述，并对需要进 一步解决的问题进行了探讨和展望。 1 5 本章小结 概念格是实现知识发现的重要的模型，概念格的构造方法直接影响到模型 的应用，而模型的约简又直接影响到挖掘结果的可理解性和知识发现的效率。 本文的工作重点是研究与实现概念格模型的分布式构造和模型的约简，并在此 基础上设计并实现了原型系统。 3 第二章数据挖掘和知识发现 本章主要介绍了数据挖掘和知识发现的定义以及两者之间的关系，同时也 简述了数据挖掘和知识发现的应用和所面临的挑战。 2 1 引言 近十几年来，数据的爆炸性增长激起了对新技术和自动发现工具的需求， 为了充分利用现有的数据资源，从数据的海洋中发现有价值的知识，数据库中 知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) 及其核心技术数据挖掘( d a t a m i n i n g ，d m ) 应运而生，目的在于对数据进行更高层次、更深入的分析，从大 量的、微观的原始数据中提取出精炼的、宏观的知识，发现有价值的信息，为 商业决策提供技术支持，从而利于商业运作，提高企业的竞争力。 2 2 数据库中的知识发现 2 2 1 知识发现产生的背景 在过去的数十年中，人类产生和收集数据的能力已经迅速提高，起作用的 因素包括如商业事务、政府事务、农业生产和科学研究过程的信息化；条形码 在大部分商业产品中的广泛使用；快速、高性能和廉价的存储设备；更好的数 据库管理系统和数据仓库技术等信息技术和数据存贮技术的发展。被有效存储 起来的数据爆炸性的增长已激起对新的数据分析技术和自动分析工具的需求， 正是在这种客观需要的推动下，数据库中知识发现( k d d ) 技术应运而生，并得 到迅速发展，越来越显示出其强大的生命力，成为数据库研究、开发和应用最 活跃的分支之一；2 0 世纪9 0 年代开始更是有了突飞猛进的发展，成为目前涉 及人工智能、数据库理论与技术、电子商务等学科的一个非常活跃的研究领域； 在商务管理、生产控制、市场分析、工程设计和科学探索等方面表现出很好的 应用前景，例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e 大学的k d d 研 究组，对其拥有的十多年的客户数据进行分析。该研究组在科学分析的基础上， 提出了新的电话收费和管理办法，制定了既有利于公司又有利于客户的新政策。 经过几十年的发展，知识发现研究的重点逐渐从发现方法转向系统应用，并且 注重多种发现策略和技术的集成，多种学科之间的相互交叉渗透；随着其后的 不断发展，形成为一个建立在数据库技术的基础上，结合人工智能、机器学习、 统计学、神经网络等多种学科技术的具有很强生命力的新研究领域。特别需要 指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库 的简单查询，而且要对这些数据库进行微观和宏观的分析和推理，企图发现事 件发生的背后所隐藏的规律、模式等有用信息，以指导实际问题的求解、对未 来活动进行预测等。k d d 是一个交叉学科，它从其它诸如：人工智能、机器学 4 习、数据库、统计学、神经网络等学科吸取营养。因此，统计学方法、神经网 络方法、模糊论方法等都对k d d 过程产生了影响；这种影响依赖于给定的数 据挖掘任务、所挖掘的数据类型等因素。 2 2 2 知识发现的概念 在k d d 9 6 国际会议上，f a y y a d ，p i a t e t s k y s h a p i r o 和s m y t h 对k d d 作了 如下描述：指从数据集中识别出有效的、新颖的、潜在有用的和最终可理解的 模式的非平凡过程【13 1 。 数据是实例或者事务、样本的集合。例如数据库中一条记录等。 一般地说，数据挖掘的数据类型可以是任何类型的信息。其数据的存在形 式有多种，如可以是保存在本地的关系数据库、层次数据库、网状数据库，也 可以是通过网络连接的异地的异构数据库，甚至是早期的展开文件( f l a tf i l e s ) ， 还可能是多媒体数据库、空间数据库等。 模式是以某种语言描述的数据子集，或者是可用于该子集合的模型。因此， 提取一个模式也称为对数据拟合一个模型或从数据中发现结构，或更一般地说 是发现数据集合的任意高级描述。模式的表现形式多种多样，根据挖掘的任务 的不同，模式的类型有：特征化和区分；关联模式；分类和预测模式；聚类分 析；演变分析等。其中较常见的表达形式是规则的形式：特征规则的发现：关 联规则的发现；分类规则的发现；序列模式的发现等，每一种规则都有其相应 的发现的方法。 由于k d d 的目标是发现隐含在数据中的模式( 知识) ，服务于用户，提高 效率，因而模式的有效性、新颖性、有价值和可理解性显得尤其重要。通常使 用兴趣度的这一个重要的概念来刻画，其中已经结合了有效性、新颖性、有用 性和简化等指标。兴趣程度函数可由k d d 系统显式地定义或以发现的模式或 模型的有序排列来隐含地给出。其相关的客观度量如支持度和置信度，每个客 观度量都于一个用户所确定的阈值相关联，体现用户对相关模式的认可程度， 以此来判断是否接受所挖掘的模式。其主观度量主要反映用户的需要和兴趣， 因人而异，因挖掘任务而异。 非凡过程意指某些搜索是复杂的，即不是一个像计算数据的平均值那样的 简单计算问题。同时也指明搜索的过程中不发现显而易见的模式，而特指发现 隐含的模式。 2 2 - 3 知识发现的过程 知识发现过程是交互的、重复的、包含大量由用户决策的阶段。根据 b r a c h m a n 和a n a n d 的观点，k d d 过程一般可粗略地分为以下三步：数据准备、 数据挖掘以及结果的表达和解释14 1 。 5 ( 1 ) 数据准备 数据准备又包含三个子步骤：数据集成、数据选择、数据预处理。数据集 成是将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊性、 处理数据中的遗漏和清洗脏数据等。数据选择的目的是确定发现任务的操作对 象，即目标数据，它是根据用户的需要从原始数据库中抽取的一组数据。数据 预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型 转换等工作。数据预处理的目的是为了克服目前数据挖掘工具的局限性。 图2 1知识发现过程 ( 2 ) 数据挖掘阶段 数据挖掘阶段首先确定的是挖掘的任务或目的，如分类、聚类、关联规则 发现或序列模式发现等。等确定了挖掘任务后，就要决定使用什么样的挖掘算 法。同样的任务可以用不同的算法来实现，选择实现算法有两个考虑因素：一 是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或 实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识，而 有的用户或系统的目的是获取预测准确度尽可能高的预测型知识。完成了上述 准备工作之后，就可以实施数据挖掘操作了。 ( 3 ) 结果表达和解释 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或 无关的模式，因而需要将其剔除；某些模式也可能不满足用户要求，因而发现 过程需要回到前面的某个发现阶段，例如，重新选取数据、采用新的数据变换 方法、设定新的数据挖掘参数值，甚至换一种挖掘算法。另外，k d d 由于最终 是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结果转换为 用户易懂的另一种表示，如把分类决策树转换为“i f ”t h e n ”规则。 6 2 2 4 知识发现与相关技术的比较 k d d 是一个多领域交叉的研究和应用领域，涉及许多学科，是多种技术的 集成，包括机器学习、模式识别、人工智能、统计学、专家系统、神经网络等， 其中k d d 主要的技术支柱为数据库、人工智能和数理统计。k d d 与这些领域 的技术密切相关，但又有一定区别。下面简要讨论k d d 与这些技术的比较。 ( 1 ) k d d 与机器学习 知识发现是从数据中提取知识的过程，而机器学习中的归纳学习也是从数 据中提取知识，但二者是有区别的。1 ) k d d 是从现实世界中已有的具体数据中 提取知识；而机器学习所使用的是专门为机器学习特别准备的数据，大多经过 专家挑选。2 ) k d d 使用来自现实世界数据库中的实际数据，数据量大，因此学 习算法的效率和可扩充性就尤为重要。而且由于数据来自实际数据库，因此数 据的一致性、完整性、正确性很难保证，存在一定的缺失和噪音；而机器学习 的数据一般由专家精心挑选，一般没有或较少出现噪音和缺失数据。3 ) 由于 k d d 处理的数据来自实际数据库，与这些数据库以及实际应用领域还有一些相 关的领域知识或背景知识，这些知识的合理运用将会显著提高算法效率、改善 发现知识的质量 1 5 , 1 6 j 。 ( 2 ) k d d 与数据库技术 k d d 与数据库技术都是对数据库进行操作，但是两者也是不同的。1 ) 数 据库技术侧重对数据库存储处理的高效率和并发控制的研究；而k d d 则是利 用数据库已经成熟的技术对数据进行分析。2 ) k d d 与目前数据库管理系统 d b m s 的作用不同，后者的侧重点是把大量的数据组织起来，以方便用户进行 存取、维护、查询，并对数据的一致性和完整性进行约束；而k d d 则侧重于 对数据库中的数据进行分析，以得到有用的结果。3 ) k d d 与数据库中的数据库 报表工具也是不同的，后者只是根据用户的选择对相应的数据进行简单的数学 运算和处理，并以特定的方式提交给用户；而前者是要对这些数据进行由微观 到宏观的统计、分析，企图发现隐藏在数据背后的总体特征和发展趋势，利用 已有的数据对未来进行预测。 ( 3 ) k d d 与传统的统计方法 尽管统计方法为数据分析提供了一个坚实的理论基础，但对k d d 来说， 仅有统计方法是不够的： 传统的统计方法一般只能处理数值型数据；而对k d d 而言，由于数据 库中存储的不仅仅是数值型数据，因此k d d 不仅要能够从数值型数据中发现 其内在的规律性，还要能够从名词型、结构化的数据中发现有价值的信息。 统计方法完全是由数据驱动的，依赖于特定分布和独立性假设，排除了 领域知识的参与；而对k d d 而言，领域知识的合理运用是非常有必要的，能 够为用户提供更有价值的信剧1 6 】。 7 ( 4 ) k d d 与专家系统 k d d 和专家系统都需要领域专家或用户的参与，然而从知识获取以及领域 专家在整个过程中的作用等方面，二者也存在差别： 专家系统必须要从领域专家那里获得知识，或从专家已经解决的问题中 进行归纳，得到规则，因此专家知识的获取以及正确性检验是建立专家系统之 前首先要做的工作；而k d d 主要处理现实世界数据库中的数据，它要处理的 数据无需额外的获取工作，而数据的正确性、有效性检验也是交由k d d 的数 据预处理来完成的。 专家系统是用已有的知识去解决问题，且它用于解决问题的知识一定是 专家系统里面已存在的、或经过演绎推理能够得到的知识，问题解决之后不会 产生新的知识；而k d d 是用于发现知识的，它运用已有的数据挖掘方法是从 大量数据中发现隐含的、未知的知识。 专家系统完全依靠领域专家的知识，注重经验第一；而k d d 以现实世 界中的数据为依据，虽然强调要使用领域知识，使得整个k d d 过程有用户的 参与、受专家的指导，但是它更注重的还是事实第一。 2 3 数据挖掘简介 数据挖掘是k d d 过程中的一个步骤，同时也是最关键的一个步骤，它是 指运用特定的挖掘算法是从数据中提取隐含的、有价值的模式。目前数据挖掘 主要的研究内容包括基础理论的研究、理论模型的构建、发现算法的设计与优 化、以及针对各种复杂数据类型的挖掘，如结构化和半结构化数据挖掘、w e b 挖掘、多媒体和文本挖掘、空间数据挖掘等等。 2 3 1 数据挖掘的研究内容和基本任务 数据挖掘的任务就是从数据集中发现隐含的、事先未知但潜在有用的模式。 数据挖掘的任务一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库 中数据的一般特性，而预测性挖掘任务则是在当前数据上进行推断，以进行预 测。具体来说，数据挖掘的基本任务主要有以下几种： ( 1 ) 分类( c l a s s i f i c a t i o n ) ：即区分数据的类别，寻找一个能够描述数据集 合典型特征的模型或函数( 也称作分类器) ，使之能够识别未知数据的类别 ( c l a s s ) 。由分类得到的分类规则反映了同类事物所具有的共性特征以及不同事 物之间的差异型特征。目前典型的分类方法主要有决策树、神经网络、粗糙集、 贝叶斯等等。 ( 2 ) 预测( p r e d i c t i o n ) ：根据已知数据的类别去推断其他类别未知的数据的 类别或根据历史的和当前的数据去推测未来的数据。它可以分为两种：1 ) 可以 根据分类所构造出的分类模型对其它类别未知的数据进行分类，从而预测这些 数据的类别；2 ) 基于时间序列的预测，通过建立统计上的随机模型或建立神经 8 网络预测模型进行时间序列预测。 ( 3 ) 关联规则( a s s o c i a t i o nr u l e s ) ：它是反映一个对象与其他对象之间依 赖或关联的知识。关联规则发现的任务就是从数据库中发现满足用户指定阈值 的强规则。关联规则挖掘分为两步：第一步是找出目标数据库的所有频繁项集； 第二步是由频繁项集产生关联规则。其中第一步是关联规则发现算法的核心， 对挖掘效率起关键作用，而第二步只是由频繁项集产生关联规则的枚举过程。 最为著名的关联规则发现方法是r a g r a w a l 提出的a p r i o r i 算法】及j i a w e ih a n 提出的f p g r o w t h 算法引。 ( 4 ) 序列模式( s e q u e n t i a lp a t t e r n s ) ：序列模式的概念最早由a g r a w a l 和 s r i k a n t 提出 1 9 1 ，指在多个数据序列中发现共同的行为模式。与关联规则挖掘频 繁模式类似，序列模式挖掘的是频繁出现的序列。例如，对于某顾客，在序列 数据库d 中，序列模式发现问题就是在该数据库中寻找所有的频繁序列或所有 的最长频繁序列。r a g r a w a l 称最长频繁序列为序列模式。 ( 5 ) 聚类( c l u s t e r i n g ) ：根据“各聚集内部数据对象间的相似度最大化和各 聚集对象间的相似度最小化 的基本原则，以及度量数据对象之间相似度的计 算公式，将数据对象划分为若干组，从而对未分类的数据进行类别的识别。一 旦聚类得以确定，各个对象就作相应的聚类标记，并概括同一聚类中的各个对 象的共同特性，从而形成类别描述。聚类分析与分类的最大区别在于前者数据 的类别是未知的，属于无监督学习，而后者用于训练的数据类别是已知的，因 而属于有监督学习。 ( 6 ) 偏离( d e v i a t i o n ) ：发现数据中与常规值相比最有意义的变化。在数据 集中不可能所有的数据都符合知识发现所获得的模型，对于那些不符合大多数 数据所构成的规律的数据就称作偏离或异常。在很多情况下，这些数据都被当 作噪音而不予考虑，但在有些场合，如商业欺诈行为的自动发现、网络攻击检 测等方面，偏离知识发现往往更有应用价值。发现偏离数据主要是利用数理统 计的相关知识，根据从已知数据所获得的概率统计分布模型确认偏离数据。 2 3 2 数据挖掘的常用模型和方法 ( 1 ) 粗糙集 粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家 z p a w l a k 在1 9 8 2 年首先提出，这一方法在数据挖掘中具有重要的作用，通常 处理含糊性和不确定的问题，发现不准确数据或噪音数据内在的结构关系，还 可用于特征的约简和相关分析中。知识工程研究中，一直存在着信息的含糊性 ( v a g u e n e s s ) 等问题。含糊性有三种：1 ) 术语的模糊性，如高矮；2 ) 数据的不 确定性，如噪音引起的；3 ) 知识自身的不确定性，如规则的前提与结果之间的 依赖关系并不是完全可靠的。 9 人工智能的基础理论之一一经典逻辑不足以解决这些不确定性问题。为此， 人们提出了一些解决方法，包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论，但这些方法都有一些内在缺陷或限定范围。例如，基于统计的方法 在理论上还难以令人信服；而模糊集方法则存在一个本质问题即如何确定成员 隶属度，相比之下，粗糙集方法则有几个优点：不需要预先知道的额外信息，如 统计中要求的先验概率和模糊集中要求的隶属度，算法简单，易于操作。 粗糙集对不精确概念的描述是通过上近似( u p p e ra p p r o x i m a t i o n ) 和下近似 ( 1 0 w e ra p p r o x i m a t i o n ) 这两个精确概念来实现的。一个概念( 或集合) 的下近似是 指其中的元组肯定属于该概念；一个概念( 或集合) 的上近似是指其中的元组可 能属于该概念。 ( 2 ) 统计分析 统计分析的理论基础主要是统计学和概率论的原理，是一种较为精确的数 据挖掘技术，它是一种基于模型的方法，包括回归分析、因子分析和判别分析 等，该方法比较容易理解，对结果描述精确。但是当利用大规模数据集来学习 时，统计分析的评估代价变的很敏感。收集关于数据的各种统计量的代价随着 实例数目的增长而增大。尽管最近的收集技术可能减少这个收集活动的代价， 但对每个新的我们所要的统计量集合仍然要花费大量的时间。 ( 3 ) 概念格 r w i l l e 等提出了根据一个二元关系来建立相应概念格或g a l o i s 格的基本 思想，它在本质上描述了对象与属性之间的联系，表明了概念之间泛化与例化 之间的关系。概念格的非形式化定义为： 给定上下文( c o n t e x t ) 为三元组t = ( o ，d ，r ) ，其中。是对象集合，d 是性质 集合，r 是。和d 之间的二元关系，则存在唯一的偏序集合与之对应，并且这 个偏序集合产生一种格结构，这种由上下文所诱导出的格称为概念格。x r x 表 示0 中的一个元素x 与d 中一个元素x 之间有关系r 。格中每个结点是一个序 偶( 即概念) ，记为( a ，b ) ，其中a p ( o ) ，b p ( d ) ，p ( o ) 是0 的幂集，p ( d ) 是d 的幂集，称a 为概念的外延( e x t e n s i o n ) ，称b 为概念的内涵( i n t e n s i o n ) 。概念格 是一种完备的概念层次结构，在信息检索、数字图书馆、软件工程、知识分类、 类的设计、网络管理和k d d 等领域，概念格已经显示出一定的应用价值。 ( 4 ) 决策树 决策树是通过一系列规则对数据进行分类的过程。它以信息论中的互信息 ( 信息增益) 原理为基础寻找数据库中具有最大信息量的字段，建立决策树的 一个结点，再根据字段的不同取值建立树的分枝；在每个分枝中集中重复建树 的下层结点和分枝的过程，即可建立决策树。采用决策树，可以将数据规则可 视化，其输出结果也容易理解。该类方法的实用效果好，影响较大。 1 0 ( 5 ) 贝叶斯网络 贝叶斯网络基于后验概念的贝叶斯定理，是建立在数据进行统计处理基础 上的方法。它将不确定事件通过网络连接起来，可以对于其他相关事件的结果 进行预测；此外其网络变量可以是可见的，也可隐藏在训练样本中。贝叶斯网 络具有分类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效 果较好，缺点是对发生频率很低的事件预测