（计算机应用技术专业论文）基于数据挖掘的贝叶斯网络和提升算法的研究.pdf

湖北工业大学硕士学位论丈 摘要 数据挖掘 d a t am i n i n g 是在应用需求的背景下产生并迅速发展起来的 开 发信息资源的一套科学方法 算法及软件工具和环境 是集统计学 人工智能 模式识别 并行计算 机器学习 数据库等技术的一个交叉性的研究领域 d m 是 识别有效的 新颖的 具有潜在用处的可理解的数据模式的过程 贝叶斯网络是研究不确定性问题的重要方法之一 它基于概率和统计理论 具有坚实的数学基础 由于具有自然的表达方式 强大的推理能力和方便的决策 机制等许多优点 贝叶斯网络在许多领域得到了广泛的应用 本文的主要工作如 下 1 首先对贝叶斯网络理论进行了系统深入的分析和论述 并用一个疾病网络 的实例模型对贝叶斯网络的构成及语义进行了详细介绍 总结和归纳出贝叶斯网 络与其他方法相比的优势和特点 论述了贝叶斯网络的功能和推理机制 分析和 讨论了贝叶斯网络学习的内容和目标 并对贝叶斯网络结构学习中的主要问题进 行了深入地剖析 2 在分析了条件独立性的有关性质和属性的基础上 推导出条件独立性与概 率参数之间的几个推论并给予证明 从条件独立性的角度 给出了贝叶斯网络 b n 的一般性定义 讨论了互信息与条件独立性之间的内在关系 并探讨了b n 与条件 独立性的关系 3 对贝叶斯改进算法进行了比较研究 在对提升算法研究的基础上 提出了 一种通过从弱分类器构造强分类器的方法 b b n 并对算法的正确性进行了证明 从理论上证明了该方法能较好的提高了朴素贝叶斯分类器的性能 关键词 数据挖掘 朴素贝叶斯分类器 贝叶斯网络 条件独立性 b o o s t i n g 湖北工业大学硕士学位论丈 a b s t r a c t d a t am i n i n g d m i sar a p i d l yg r o w i n gf i e l d w h o s ed e v e l o p m e n ti sd r i v e nb y s t r o n gr e s e a r c hi n t e r e s t sa sw e l la su r g e n tp r a c t i c a l s o c i a l a n de c o n o m i c a ln e e d s d m i sas u i to fs c i e n t i f i cm e t h o d a l g o r i t h m s o f t w a r et o o la n de n v i r o n m e n ta n dc a nb eu s e d t od e v e l o pi n f o r m a t i o nr e s o u r c e s d mi sam u l t i d i s c i p l i n a r yc r o s sr e s e a r c hf i e l 正 i n c l u d i n gs t a t i s t i c s a r t i f i c i a li n t e l l i g e n c e p a t t e r nr e c o g n i t i o n p a r a l l e lc o m p u t i n g m a c h i n el e a r n i n g d a t a b a s et e c h n o l o g ya n ds oo n d mi st h en o n t t i v i a lp r o c e s so f i d e n t i f y i n gv a l i d n o v e l p o t e n t i a l l yu s e f u l a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si n d a t a w ea l s oa d o p tt h ec o m m o n l yu s e dd e f t n i t i o no fd a t am i n i n ga st h ee x t r a c t i o no f p a r e n t so rm o d e l sf r o mo b s e r v e dd a t a 1 f i r s t l y t l l i sp a p e rd i s c u s s e st h eb a s i st h e o r yo fb a y e s i a nn e t w o r k s a n dt h e n d e s c r i b et h ec o m p o n e n t so fi t m o r e o v e r t h ep a p e ri n t r o d u c et h ec o n s t i t u t i o na n d s e m a n t i c so fb a y e s i a nn e t w o r kb yas a m p l eo fs i xc o d e s i ta l s os u r m m a r i z e st h e s u p e r i o r i t i e sa n dc h a r a c t e r i s t i c st h a tb a y e s i a nn e t w o r k sc o m p a r e sw i t ho t h e rm e t h o d s a f t e rd i s c u s s i n gi t sf u n c t i o na n dr e a s o n i n gm e c h a n i s m t h ep a p e rf o c u so nt h ea l m sa n d m a j o rp r o b l e m so fb a y e s i a nn e t w o r k s 2 b a s e do nt h ef e a t u r e sa n da t t r i b u t i o n i td e r i v e sa n dp r o v e sf o u rc o r o l l a r i e so f c o n d i t i o n a li n d e p e n d e n c ew i t hp r o b a b i l i t yp a r a m e t e r n e nu s e dt h ec o n d i t i o n a l i n d e p e n d e n c et o d e f i n et h en o t i o no fb a y e s i a nn e t w o r k s b d d i s c u s s e st h e r e l a t i o n s h i pb e t w e e nm u t u a li n f o r m a t i o nw i t hc o n d i t i o n a li n d e p e n d e n c e a n di n d i c a t e s t h a tw ec a l li d e n t i f yt h ed i r e c t1 i n k si nt h e u n d e r l i n i n gb a y s e s i a nn e t w o r k s f u r t h e r m o r e d e m o n s t r a t e st h er e l a t i o nb e t w e e nt h em o d e lo fb na n dh ec o n d i t i o n a l i n d e p e n d e n c e s 3 s t u d y t h e a l g o r i t h m s t o i m p r o v e t h e p e r f o r m a n c e o fn a t v e b a y e s c l a s s i f i c a t i o n p u t t i n gf o r w a r dan e wm e t h o dt oi m p r o v et h ep e r f o r m a n c eo fn b cb y c r e a t i n gn e ws t r o n g c l a s s i f i e rf r o mp o o rc l a s s i f i e r t h eb o o s tn b cc l a s s i f i e r t h e l l w ep r o v e di tb ec o r r e c ta n ds a t i s f i e dc l a s s i f i c a t i o np e r f o r m a n c e k e y w o r d s d a t am i n i n g n a i v eb a y e s i a nc l a s s i f i c a t i o n b a y e s i a nn e t w o r k s c o n d i t i o n a li n d e p e n d e n c e b o o s t i n g n 诹 l 亡工繁火溶 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师指导下 独立进行研究工作所取 得的研究成果 除文中已经标明引用的内容外 本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果 对本文的研究做出贡献的个人和集体 均已在文中以明确方 式标明 本声明的法律结果由本人承担 学位论文作者签名 佃习禾日期 加1 年多月占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 e p 学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索 可以采 用影印 缩印或扫描等复制手段保存和汇编本学位论文 学位论文作者签名 啊纫席牝 日期 加浒 月 日 湖北工业大学硕士学位论丈 第1 章引言 随着信息技术的快速发展和信息搜集能力的同益提高 产生了海量的数据 这些海量的数据或是存储在企业的物理存储器上的静态数据或是不被存储而瞬时 出现的动态数据 面对如此丰富的海量数据 传统的数据处理方法和能力己远远 不能满足实际的需求 面对r 趋激烈的市场竞争 人们需要从这些蕴含着丰富决 策信息的数据中抽取能帮助领导进行决策的知识 在需求的强烈驱动下 数据挖 掘技术应运而生 数据挖掘就是综合应用一系列先进的技术从大型数据库或数据仓库中提取人 们感兴趣的信息和知识 它们是隐含的 事先未知且潜在有用的概念 规则 规 律 模式等 在关系数据库和事务数据库之上 己经对数据挖掘方法在许多领域进行了较 为深入广泛的研究 这些领域有数据流信息处理 空间信息处理 多媒体信息 时空信息以及移动对象信息等 已有的关于数据挖掘 机器学习 数据库系统 统计方法等的研究为进一步 的数据挖掘方法研究奠定了很好的基础 新的数据挖掘方法一定是在继承己有的 理论方法研究基础上并结合新的数据特性而得到的理论方法 本文的研究同样遵 循这一规律 1 1 研究背景 1 1 1 数据挖掘 数据挖掘是一个多学科交叉研究领域 它融合了数据库技术 人工智能 机 器学习 统计学 知识工程 面向对象方法 信息检索 高性能计算以及数据可 视化等最新技术的研究成果 数据挖掘之所以被称为未来信息处理的骨干技术之 一 主要在于它以一种全新的概念改变着人们利用数据的方式 二十世纪 数据 库技术取得了决定性的成果并且已经得到广泛的应用 但是 数据库技术作为一 种基本的信息存储和管理方式仍然以联机事务处理o l t p o n l i n et r a n s a c t i o n p r o c e s s i n g 为核心应用 缺少对决策 分析 预测等高级功能的支持机制 众所 周知 随着数据库容量的膨胀特别是数据仓库 d a t aw a r e h o u s e 以及w e b 等新型 湖北工业大学硕士学位论丈 数掘源的 l 益普及 联机分析处理o l a p o n l i n ea n a l y t i cp r o c e s s i n g 决 策支持 d e c i s i o ns u p p o r t 以及分类 c l a s s i f i c a t i o n 聚类 c l u s t m i n g 等复杂应用 成为必然 面对这一挑战 数据挖掘和知识发现 k n o w l e d g ed i s c o v e r y 技术应运而 生并显示出强大的生命力 数据挖掘和知识发现使数据处理技术进入了一个更高 级的阶段 它不仅能对过去的数据进行查询 并且能够找出过去数据之间的潜在 联系 进行更高层次的分析 以便更好地作出理想的决策 预测未来的发展趋势 等 经过十几年的研究和实践 数据挖掘技术已经吸收了许多学科的最新研究成 果而形成独具特色的研究分支 勿容置疑 数据挖掘研究和应用具有很大的挑战 性 在理论上 一批具有挑战性和前瞻性的问题被提出 吸引越来越多的研究者 数据挖掘的概念从二十世纪八十年代被提出后 其经济价值己经显现出来 而且 被众多商业厂家所推崇 形成初步的市场 另一方面 目前的数据挖掘系统研制 也决不是象一些商家为了宣传自己商品所说的那样神奇 仍有许多问题需要研究 和探索 把目前数据挖掘的研究现状描述为鸿沟阶段是比较准确的 所谓鸿沟阶 段是说数据挖掘技术在广泛被应用之前仍有许多鸿沟需要攀越 在过去的数十年 中 我们产生和收集数据的能力已经迅速提高 起作用的因素包括条码在大部分 商业产品中的广泛使用 许多商务 科学和行政事务的计算机化 以及由文本和 图像扫描平台到卫星遥感系统的数据收集工具的进步 此外 作为全球信息系统 的万维网的流行 己经将我们淹没在数据和信息的汪洋大海中 尽管很早就出现 了简单的数据统计技术 但先进的智能数据分析工具尚未成熟 因此 在数据生 成和数据理解之间存在很大的差距 例如 就目前商家推出的数据挖掘系统而言 它们都是一些通用的辅助开发工具 这些工具只能给那些熟悉数据挖掘技术的专 家或高级技术人员使用 仅对专业人员开发对应的应用起到加速或横向解决方案 的作用 但是 数据挖掘来自于商业应用 而商业应用又会由于应用的领域不同 而存在很大差异 大多数学者赞成这样的观点 数据挖掘在商业上的成功不能期 望通用的辅助开发工具 而应该是数据挖掘概念与特定领域商业逻辑相结合的纵 向解决方案 j 存储数据的爆炸性增长业己激起对新技术和自动工具的需求 以帮助我们将 海量数据转换成信息和知识 于是 数据挖掘 由大量数据中 用非平凡的方 法发现有用的知识 就成了一种自然的需求 正是这种需求引起了人们的广泛关 注 导致了数据挖掘研究的蓬勃开展 2 湖北5 业大学硕士学位论文 i 1 2 贝叶斯分类 在众多的数据挖掘算法中 贝叶斯网络1 2 1 1 3 1 结合图论和统计学方面的知识 提 供了一种自然的表示因果信息的方法 用于表达随机变量之间复杂的概率不确定 性 发现数据 日j 的潜在关系 贝叶斯理论给出了信念函数在数学上的计算方法 具有稳固的数学基础 贝叶斯网络作为一种图形化的建模工具 具有一系列的优 点 1 贝叶斯网络将有向无环图与概率理论有机结合 不但具有了正式的概率理 论基础 同时也具有更加直观的知识表示形式 一方面 它可以将人类所拥有的 因果知识直接用有向图自然直观地表示出来 另一方面 也可以将统计数据以条 件概率的形式融入模型 这样贝叶斯网络就能将人类的先验知识和后验的数据无 缝地结合 克服框架 语义网络等模型仅能表达处理定量信息的弱点和神经网络 等方法不够直观的缺点 2 贝叶斯网络与一般知识表示方法不同的是对于问题域的建模 因此当条件 或行为等发生变化时 不用对模型进行修正 3 贝叶斯网络可以图形化表示随机变量问的联合概率 因此能够处理各种不 确定性信息 4 贝叶斯网络中没有确定的输入或输出结点 结点之间是相互影响的 任何 结点观测值的获得或者对于任何结点的干涉 都会对其它结点造成影响 并可以 利用贝叶斯网络推理来进行估计预测 5 贝叶斯网络的推理是以贝叶斯概率理论为基础的 不需要外界的任何推理 机制 不但具有理论依据 而且将知识表示与知识推理结合起来 形成统一的整 体 由于上述优点 贝叶斯网络很快就成为数据挖掘领域进行不确定性推理和建 模的一个有效工具 利用贝叶斯网络可以对于事件或者属性间的带有不确定性的 相互关系进行分析 论文研究内容和组织结构 在收集和整理大量的相关资料 弄清相关的理论 方法 算法 体系结构 原型系统等基础上 本文集中选取了下面两个问题开展研究工作 1 数据挖掘过程和系统构架研究 在分析现有的数据挖掘系统 原型系统的 体系结构基础上 系统研究了数据挖掘的基本过程和系统功能部件 这些研究包 括从数据挖掘的基本过程来探讨系统应具备的主要功能部件及其相互联系 数据 挖掘的技术方法 数据挖掘系的主要问题 2 贝叶斯网络学习的研究和提升算法的改进 数据挖掘已经建立了许多独具 湖北工业大学硕士学位论丈 特色的挖掘理论体系 但足从应川范咽 有效性以及适应性等方面仍 岳要探索新 的挖掘理论 在回顾了现有主流的数据挖掘技术 特别是数据分类问题 在对贝 叶斯理论 朴素贝叶斯分类和贝叶斯网络的深入的研究和剖析的基础上 分析了 贝叶斯独立和贝叶斯网络独立性的关系 对贝叶斯结构学习进行了深入的研究 在探讨了几种贝叶斯分类器的改进方法 最后给出了一种基于贝叶斯提升算法的 改进并进行了理论证明 论文的组织结构如下 第l 章简单介绍了研究背景和论文的研究内容和组织结构 第2 章对数据挖掘进行了详细的综述 介绍了数据挖掘的研究背景 研究意 义 分类方法 研究现状和主要问题 第3 章对贝叶斯理论的研究进行了详细的论述 介绍了贝叶基本原理 朴素 贝叶斯公式 贝叶斯网络结构学习 第4 章探讨了几种贝叶斯分类器的改进的方法 最后给出了一种基于贝叶斯 提升算法并进行了理论证明 第5 章结束语 4 湖北工业大学硕士学位论丈 2 1 数据挖掘概述 第2 章数据挖掘 简单地说 数据挖掘 d a t am i n i n g d m 是提取或 挖掘 知识 目前 数 据挖掘可以从统计学 数据库和机器学习等三个角度进行定义 挖掘 一词最早 出现于统计学中 从统计学的角度 数据挖掘是指分析所观察的数据集以发现可 信的数据问的未知关系并提供给数据拥有者可理解的 新颖的和有用的归纳数据 从数据库的观点来看 数据挖掘是指从存储在数据库 数据仓库或其它信息仓库 中的大量数据中发现有趣的知识的过程o l 从机器学习的角度 数据挖掘定义为从 数据中抽取隐含的 明显未知的和潜在有用的信息1 5 2 1 1 数据库中的知识发现和数据挖掘的关系 数据库中的知识发现 6 j k n o w l e d g ed i s c o v e ri nd a t a b a s e k d d 是识别有效的 新颖的 具有潜在用处的可理解的数据模式的过程 d b 与k d d 的关系从名称上 就体现了明显的区别 d b 提供了基本数据模型下的存储和数据操作 而k d d 的 过程说明了知识发现常常意味着经验 重复 用户的交互及许多设计 决策和习 惯 简单地讲 k d d 表示了从低层数据抽象高层知识的整个过程 通过数据库中 的知识发现 人们可以从数据库的数据及相关集合中抽象有用的知识 数据的规 律性或高层的信息 对于k d d 还有一些类似的术语 如从数据库中挖掘知识 知识提取 数据考古 数据捕捞 数据 模型分析等 本质上 数据挖掘 d m 与 k d d 也是不同的 但也有一些人把数据挖掘和k d d 等同看待 其实d m 仅仅 是k d d 的一个步骤如图2 1 典型的k d d 的过程下 1 数据清理 消除噪声或不一致的数据 2 数据集成 多种数据组合在一起 3 数据选择 从数据库中检索与分析任务相关的数据 4 数据变换 数据变换或统一成适合挖掘的形式 如通过汇总或聚集操作 5 数据挖掘 使用不同的智能方法提取数据模式或模型 6 模式 型 评估 根据某种兴趣度度量 识别表示知识的真j 下有趣的模式 7 知识表示 使用可视化和知识表示技术 向用户提供所挖掘的知识 湖北工业大学硕士学位论文 图2 1 典型的知识发现的流程图 数据挖掘是一个交叉的学科领域 包括了数据库技术 统计学 机器学习 可视化和信息科学 数据挖掘中主要采用的技术有神经网络 模糊理论 粗糙集 理论 知识表示 归纳逻辑和高性能计算等 依赖所挖掘的数据类型或给定的数 据挖掘应用 数据挖掘系统也可能集成空间数据分析 信息检索 模式识别 图 像分析 信号处理 计算机图形学 w 曲技术 数据可视化及经济 商业 生物 信息学或心理学等领域的核心技术 本文基于数据库的观点 着重研究大型数据 库中有效的 可伸缩的和可行的数据挖掘技术 通过数据挖掘 可以从数据库中 提取有趣的知识 规律和信息 并可以从不同的角度观察和浏览 所发现的知识 可用于决策 信息管理 查询处理 过程控制等等 因此 数据挖掘是当今信息 技术学科最前沿的领域之一 数据挖掘过程如图2 2 可以与用户或知识库交互 将有趣的模式提供给用户 或作为新的知识存放 在知识库中 比较广义的观点是 数据挖掘是从存放在数据库 数据仓库或其他 信息库中的大量的数据中挖掘有趣知识的过程 按照这样的观点 典型的数据挖 掘系统具有如下组成 数据库 数据仓库或其他信息库 这是一个或一组数据库 数据仓库 电子 6 湖北工业大学硕士学位论文 表格或其他类型的信息库 可以任此数掘集l 进f i 数捌清理和集成 数据库或数据仓库服务器 根据用户的数据挖掘请求 数据库或数据仓库服 务器负责提取相关数据 知识库 存放领域知识 用于指导搜索 或评估结果模式的兴趣度 这种知 识可能包括概念分层及用户确信度方面的知识 数据挖掘引擎 数据挖掘的基本组成部分 由一组功能模块组成 用于特征 化 关联 分类 聚类分析以及演变或偏差分析 模式评估模块 通常使用兴趣度来测试 并与数据挖掘模块交互 以便将搜 索聚焦在有趣的模式上 可以使用兴趣度阈值过滤所发现的模式 模式评估模块 也可以与挖掘模块集成在一起 其不同依赖于所用的数据挖掘方法的实现 但是 有效的数据挖掘应将模式评估集成到数据挖掘的一定过程之中 从而可使搜索限 制在感兴趣的模式上 数据清洗囊数据集成霪过滤 l 图2 2 典型的数据挖掘系统的结构 图形用户界面 本模块在用户和数据挖掘系统之间通信 允许用户与系统交 互 指定数据挖掘查询或任务 提供信息 帮助搜索聚焦 根据数据挖掘的中间 结果进行探索式数据挖掘 此外 该模块还允许用户浏览数据库和数据仓库模式 或数据结构 评估挖掘的模式 以不同的形式对模式进行可视化 痧噻 湖北5 业大学硕士学位论丈 2 1 2 数据仓库 数据仓库l7 是系统地组织 理解和使用数据的一种结构和工具 粗略地说 数 据仓库也是一个数据库 它与某部门所有的操作数据库分别维护 数据仓库系统 可将各种应用系统集成在一起 为统一的历史数据分析提供平台 数据仓库有多 种定义 较为公认的定义为 数据仓库是一个面向主题的 集成的 时变的非易 失的数据集合 以支持部门的决策 所谓面向主题的是指数据仓库围绕某个主题 剔除无用的数据 提供特定主题的简明视图 集成的是指数据仓库通常是多个异 种数据源中的各种数据的集成 时变的是指数据仓库中的数据为历史数据 其关 键结构隐式的或显式地包含着时间因素 非易失的是指数据仓库物理地分离式存 放数据 数据仓库中不需要事务处理 恢复和并发控制机制 数据仓库的应用有信息处理 分析处理和数据挖掘 其中 信息处理支持查 询和基本的统计分析 并使用交叉表 表 图 图表进行报告 分析处理支持基 本的o l a p 8 操作 包括切片与切块 下钻 上卷和转轴 支持多维数据分析 数据挖掘支持知识发现 可以找出隐藏的模式和关联 构造分析模型 进行分类 和预测 并用可视化工具提供挖掘结果 从数据仓库的观点 数据挖掘可以看成 联机分析处理 0 l a p 的高级阶段 然而 通过结合更高级的数据理解工具 数 据挖掘比数据仓库的汇总型的分析处理更先进 2 2 数据挖掘的技术方法 概念描述 9 1 c o n c e p td e s c r i p t i o n 产生数据的特征化和比较描述 特征化指 对选择的数据进行简洁明了的描述和表达 比较是对两个或两个以上的数据进行 对比得出的结果 概念是认识客观世界的基础 它是对物质 运动和能量等客观 现实的表达和描述 这些文字 图形或符号化的表达有利于更好的认识 理解和 判别客观世界中的物质与现象 概念描述通过对大量数据实例的分析 对比与综 合 总结和归纳出简洁 准确 易于理解的具体描述 为用户提供数据对象的有 趣的一般特性 这是对数据实例中特征或本质的一种提炼过程 数据挖掘是一个交叉性的学科领域 涉及数据库技术 统计学理论 机器学 习技术 模式识别技术 可视化理论和技术等 由于所用的数据挖掘方法的不同 所挖掘的数据类型的不同 数据挖掘应用的不同 从而产生了大量的 各种不同 类型的数据挖掘系统 掌握数据挖掘系统的不同分类 可以帮助用户确定最适合 的数据挖掘系统 数据挖掘的方法通常可以分为两大类 一类是统计型 常用的技术有概率分 湖北工业大学硕士学位论丈 析 相天性 聚类分析和削别分析等 另 类足人上智能中的机器学习型 通过 训练和学习大量的样品集得出需要的模式或参数 陈京民等将常用的数据挖掘技 术分为统计分析类 知识发现类和其他类型的数据挖掘技术三大类 其他数据挖 掘中包含文本数据挖掘 w 曲数据挖掘 分类系统 可视化系统和空间数据挖掘 等 i 州 朱明从数据分析角度出发 将数据挖掘分为两种类型 描述型数据挖掘和 预测型数据挖掘1 1 1 关联规则 关联规则是数据中一种简单但很实用的规则 也是一种常用的数据挖掘技术 指从大量的数据集中发现有用的依赖性或关联性的知识 其基本思路表示为 w b 其中w 代表属性集 b 代表属性个体 规则简单地解释为在数据库的列表 中 w 属性集具有真值 则个体b 具有真值的可能性和趋势 货篮分析是关联 分析中最常用的形式 1 2 1 用支持度 c o n f i d e n c e 和置信度 s u p o r t 两个属性 值来度量 组成 支持度一置信度 框架 例如在零售业中 分析客户购买计算 机后 购买打印机的概率是多少 这对于销售配货 产品布局和商务管理等具有 积极的意义 在制造业中 可以分析事件a 和事件b 发生后 事件c 发生的 概率是多少 这种技术常用于故障检测和机器维修 关联规则可以从大量的事务 数据或关系数据中 挖掘出感兴趣的知识和模式 在零售业 保险业 通讯和制 造业等行业都得到广泛的应用 2 决策树 决策树是数据挖掘中进行归纳学习和分类的重要方法 其基本思想是使用信 息论原理对大量实例的特征进行信息量分析 计算数据特征的互信息或信道容量 找出反映类别的重要特征 l 通过某种度量准则选取撮优的属性或属性组合 对 样本数据进行分类 基于样本数据中各个样本对应的属性值 形成若干分支 并 尽量保证同一分支中的样本属于同一类别 这样可以对数据样本或新的样本进行 分类 决策树主要是基于数据的属性值进行归纳分类 常用于分类的层次方法有 i f t h e n 规则 其最大优点就是可理解性 比较直观 它在学习过程中不需 要用户了解很多背景知识 它与神经网络最大的区别是 决策树可以解释如何得 出结果的决策过程 其缺点是处理复杂性的数据时 分支数非常多 管理起来难 度较大 同时 还存在数据的缺值处理问题 其算法有i d 3 c 4 5 等 目前出 现的两种新算法s u q 和s p r i t 可以由非常大的训练集进行决策树归纳 可以 处理分类属性和连续性属性 3 遗传算法 遗传算法是一种基于生物进化过程的组合优化方法 它是生物学和计算机科 9 湖北工业大学硕士学位论丈 学结合的产物1 1 4 1 山荚崮密i f l i 根大学d j h o l l a n d 教授和他的n d 事们在1 9 7 5 年首次提出 根据适者生存的原则 模拟自然界中的生命进化机制 形成由当前 群体中最适合的规则组成新的群体 以及这些规则的后代 基于这一思想的应用 根据遗传算法获得最适合的模型 并进一步对数据模型进行优化 由于遗传算法 对问题的信息要求较少 具有高效性和灵活性的特点 在数据挖掘中 也用于评 估其它算法的适合度 该算法擅长于数据聚类 通过时间上的类比和空间上的类 比 可以使大量繁杂的信息数据系统化 条理化 从而找出数据之间的内在联系 得出有用的概念和模式 在建立数据模型时 将遗传算法与神经网络相结合 可 以更好地提高模型的可理解性 遗传算法广泛应用于自动控制 机器学习 模式 识别 搜索调度和组合优化等领域 4 贝叶斯网络 贝叶斯网络基于后验概率的贝叶斯定理 是建立在对数据进行统计处理基础 上的方法 将不确定事件通过网络连接起来 可以对与其他事件相关的事件的结 果进行预测 其网络变量可以是可见的 也可以隐藏在训练样本中 贝叶斯网络 具有分类 聚类 预测和因果关系分析的功能 其优点是易于理解 预测效果较 好 缺点是对发生频率很低的事件预测效果不好 在医学和制造业等领域的应用 具有较好的效果 5 粗糙集理论 粗糙集 r o u g hs e t 1 1 5 理论是波兰别z i s k e wp a w t a k 教授在1 9 8 2 年首先 提出的 它是一种基于集合论的数学工具 这一方法在数据挖掘中具有重要的作 用 常用于处理含糊性和不确定性的问题 发现不准确数据或噪声数据内在的结 构联系 也可以用于特征归约和依赖性分析 知识约简是粗糙集的核心内容之一 它在保持知识库的分类或决策能力不变的条件下 删除其中不相关或不重要知识 去掉变量中的多余属性 粗糙集可以看成是含糊概念的一个数学模式 其主要优 点就是不需要任何关于数据的初始的或附加的信息 方法简单 易于操作 因此 广泛应用于不确定 不完整的信息分类和信息获取 粗糙集理论和技术的出现 大大地提高了数据挖掘和知识发现的效率 6 神经网络 神经网络是最常用的数据挖掘技术之一 最早由心理学家和神经生物学家提 出的 旨在寻求开发和测试神经的计算模拟 它类似于人类大脑重复学习的方法 先给出一系列的样本 进行学习和训练 从而产生区别各种样品之间的不同特征 和模式 1 9 9 5 1 0 样本集应该尽量体现代表性 为了精确地拟合各种样本数据 通过上百次 甚至上千次的训练和学习 系统最后得出潜在的模式 当它遇到新 l o 湖北工业大学硕士学位论丈 的样品数铡时 系统就会根掘训练结果f 动进行颅测和分炎 最人的特点足难于 理解 即无法解释如何得出结果和使用了什么规则 它需要很长的训练时问 需 要大量的参数 而且解释性较差 该算法的优点是对复杂问题能进行很好的预测 对噪声数据的适应能力比较高 以及它对未经训练的数据分类的能力 神经网络 可细分为前馈式 反馈式和自组织神经网络 具有优化计算 聚类和预侧等功能 在商业界 医疗诊断 工业生产监控 图像处理等各个方面都得到广泛的应用 军 事方面可用于目标跟踪 飞行控制等 会融市场采用神经网络建立信用卡和货币 交易模型 用于识别信贷客户 股票预测和证券市场分析等方面 7 统计分析 统计分析的理论基础主要是统计学和概率论的原理 是一种较为精确的数据 挖掘技术 它是一种基于模型的方法 包括回归分析 因子分析和判别分析等 该方法的优点是容易理解 对结果描述精确 可实现趋势分析 相似性搜索 相 关分析 时间序列模式和周期性模式的挖掘等功能 统计分析在实际应用中较为 广泛 著名的统计产品供应商s p s s 公司开发了s p s s 和s y s t a t 统计软件包 同时 s a s 公司也开发出相应的产品s a s 和j m p 这些产品都占有一定的应 用市场 8 异常分析 在特定的应用领域 数据库中的异常数据可能具有特殊的意义 例如 信用 卡显示的数据异常可能意味着客户欺诈行为的发生 异常 o u t l i n e r 分析就是针 对给定的数据集 通过相关技术描述和分析数据的异常或极端现象 包括不规则 数据 类别中的反常实例 模式的例外 观测值与期望值的偏离等 异常检测1 1 7 的数据模式有极值点 断点 拐点等不同的偏离现象 主要用于分析客户异常行 为 信用欺诈甄别和数据质量控制 网络安全管理和故障检测等领域 总之 数据挖掘在具体应用中 最终的目标都是发现有价值的知识和信息 各种技术方法有共同的思路和步骤 但也存在很大的差异和区别 由于它们都具 有自身的功能特点以及应用领域 见表2 1 数据挖掘技术的选择将影响最后结 果的质量和效果 通常可以将多种技术结合使用 形成优势互补 下面简要介绍 数据挖掘中常用的关联分析 决策树 贝叶斯网络和神经网络等几种技术方法 包括技术的基本思想 优势与缺点和主要应用领域 湖北工业大学硕士学位论丈 表2 1 常见的数掘技术方法的比较 2 3 国内外数据挖掘研究现状 数据挖掘和知识发现 k d d m 是近年来一个十分活跃的研究领域 从数据库中 发现知识 k d d 一词首先出现在1 9 8 9 年举行的第十一届国际联合人工智能学 术会议 1 c a d 上 从1 9 8 9 年到1 9 9 4 年举行了四次k d d 的国际研讨会 在此基础上 1 9 9 5 年召开了第一届知识发现与数据挖掘的国际学术会议 1 9 9 8 年建立了新的学术组 织a c m s i g m o d 即a c m 下的数据库中的知识发现专业组 s p e c i a li n t e r e s t e d g r o u p o nk 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 9 9 年a c m s l g m o d 组织了第五届知识发现与数据挖掘国际学术会议 k d d 9 9 专题杂志d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y 自1 9 9 7 年起由 l d u w e r s 出版社出版 此外 还有一些国际和地区性数据挖掘会议 如 知识发现 与数据挖掘太平洋亚洲会议 p a k d d 数据库中的知识发现原理与实践欧洲 会议 p k d d 数据仓库与知识发现国际会议 d a w a k a c m s i g m o d 数 2 湖北工业大学硕士学位论丈 据管理幽际会议 s i g m o d 超大型数掘库国际会议 v l d 8 a c m s i g m o d s i g a r t 数据库原理研讨会 p o d s 数据工程国际会议 i c d t 扩展数据库技术国际会议 e d b t 数据库理论国际会议 i c d t 信息与知识管理国际会议 c i k m 数据库与专家系统应用国际研讨会 d e x a 数据库系统高级应用国际会议 d a s f a a 人工智能国际联合会议 u c a i 美国人工智能学会会议 a a a i 等等 到目前为止 由美国人工智能协 会主办的k d d 国际研讨会已召开了多次 规模由原来的专题讨论会发展到国际 学术大会 以k d d 国际会议为例 1 9 9 5 年与会代表3 5 0 人 展示软件6 套 1 9 9 6 年与会代表4 5 7 人 展示软件1 8 套 1 9 9 7 年到会5 7 7 人 展示软件2 6 套 1 9 9 8 年就有7 7 3 人到会 展示软件3 9 套 平均会议代表年增长率为4 0 6 另 外 仅以1 9 9 9 年为例 就有近2 0 个国际会议列有k d d m 的专题 如c f 9 9 c i m c a 9 9 d a w a k 9 9 d i s c o v e r ys c i e n c e l 9 9 9 e u r o p a r 9 9 i d a 9 9 i s s m i s 9 9 j s m 9 9 l d 9 9 p l d 9 9 r s f d 讯 9 9 d s 9 9 v l d b 9 9 i j c a i 9 9 s i g m o d 9 9 p a d d 9 9 c i m c a 9 9 p a k d d 9 9 等 近几年 从事数据挖掘研发的人员遍布世 界8 0 多个国家 数据挖掘的研究重点也已从算法研究向具体应用过渡 从实验室 原型走向商品化阶段 1 9 9 9 年 国际上从事数据挖掘产品研发的软件公司己从 1 9 8 9 年的几个公司 猛增为上百家公司 每年都有若干软件产品推出 国内这两 年也有相当多的数据挖掘和知识发现方面的研究成果 许多学术会议上都设有专 题进行学术交流 目前 几种典型的数据挖掘研究是关联规则 分类 聚类 预 测 w e b 挖掘等 2 4 数据挖掘中存在的重点问题 分析目前研究和应用现状 数据挖掘存在以下几个需要重点研究的问题 1 技术与特定商业逻辑的平滑集成问题 它包括领域知识对行业或企业知识 挖掘的约束与指导 商业逻辑有机嵌入数据挖掘过程等关键课题 2 据挖掘技术与特定数据存储类型的适应问题 不同的数据存储方式会影响 数据挖掘的具体实现机制 目标定位 技术有效性等 依靠一种通用的应用模式 适合所有的数据存储方式下发现有效知识是不现实的 因此 针对不同数据存储 类型的特点 进行针对性研究是目前流行而且也是将来一段时间所必须面对的问 题 3 数据挖掘系统的构架与交互式挖掘技术 虽然经过多年的探索 数据挖掘 系统的基本构架和过程己经趋于明朗 但是受应用领域 挖掘数据类型以及知识 湖北工业大学硕士学位沦丈 表达模 等的影响 在具体的实现机制 技术路线以及备阶段或部件 如数据清 洗 知识形成 模式评估等的功能定位方面仍需要细化和深入研究 由于数据挖 掘是在大量的源数据集中发现潜在的 事先并不知道的知识 因此和用户交互式 进行探索性挖掘是必然的 这种交互可能发生在数据挖掘的各个不同阶段 从不 同角度或不同粒度进行交互 所以 良好的交互式挖掘 l8 i n t e r a c t i o nm i n i n g 也 是数据挖掘系统成功的前提 4 数据挖掘语言与系统的可视化问题 对o l t p 应用来说 结构化查询语 言s q l 己经得到充分发展 并成为支持数据库应用的重要基石 但是 对于数据 挖掘技术而言 由于诞生的较晚 加之它相比o l t p 应用的复杂性 开发相应的 数据挖掘操作语言仍然是一个极富挑战性的工作 可视化要求已经成为目前信息 处理系统的必不可少技术 对于一个数据挖掘系统来说它更是如此 可视化挖掘 除了要与良好的交互式技术结合外 还必须在挖掘结果或知识模式的可视化 挖 掘过程的可视化以及可视化指导用户挖掘等方面进行探索和实践 5 数据挖掘理论与算法研究 经过十几年的研究 数据挖掘己经在继承和发 展相关基础学科如机器学习 统计学等已有成果方面取得了可喜的进步 探索出 了许多独具特色的理论体系 但是 这决不意味着挖掘理论的探索已经结束 恰 恰相反 它给研究者留下了更加丰富的理论课题 一方面 在这些大的理论框架 下有许多面向实际应用目标的挖掘理论等待探索和创新 另一方面 随着数据挖 掘技术本身和相关技术的发展 新的挖掘理论的诞生是必然的 而且可能对特定 的应用产生推动作用 新理论的发展必然促进新的挖掘算法的产生 这些算法可 扩展挖掘的有效性 如针对数据挖掘的某些阶段 某些数据类型 大容量源数据 集等更有效 可提高挖掘的精度或效率 也可融合特定的应用目标如c r m 电子 商务等 因此 对数据挖掘理论和算法的探讨将是长期而艰巨的任务 从上面可以看 出 数据挖掘研究和探索的内容是及其丰富和具有挑战性的 湖北工业大学硕士学位论丈 第3 章贝叶斯网络学习 3 1 概率与贝叶斯公式 为了更好的说明贝叶斯网络 下面介绍几个相关的基本概念和公式 定义3 1概率独立设q 表示事件全集 有两个事件分别是a 和b 如果 p a b p a p b 3 1 称事件a 与b 独立 定义3 2 条件概率是概率论中的一个重要概念 设有两个事件分别是a 和b 在事件a 已经发生的条件是下 事件b 发生的可能性 用符号p b i a 表示 p b i a 丛生p a o 3 2 爿 为事件a 已发生的条件下b 发生的条件概率 设q 表示事件全集 对与条件概率有如下几个性质 1 p b i b l 2 若a 和b 为互斥的两个事件 则p b i a p a 旧 3 以b l q p 占 定义3 3 设b 1 b 2 b 为样本空间s 中的事件 p b i 可根据以前的数据分 析得到 或根据先验知识估计获得 则称p b i 为先验概率 p b i 的值以过去的实践 经验和认识为依 在实验之前得到或已经确定 定义3 4 设b l b 2 b n 为样本空间s 中的事件 则事件a 发生的情况下b i 发 生的概率p b i i a 可根据先验概率p b i 和观测信息重新修正和调整后得到 通常 将p b i i a 称为后验概率 e b i a 筹 等 3 3 随着样本信息的不断变化 后验概率也不断的更新 前一次的后验概率将作 为在次调整时的先验概率使用 从而得到新的后验概率 这是一个不断更新 反 复调整的过程 定义3 5 若有诸事件a l a 2 a 彼此独立 且b 为事件a i a 2 的子事件 p a i 0 i l 一2 一 n p b o 那么b a y e s 公式可表示为 湖北工业大学硕士学位论丈 j p 4 i 口 一型址 3 4 p a j p b 1 4 p a 2 尸 口1 4 j p 4 尸 b 1 4 式中 p a o p a 2 p 为先验概率 p a d p a 2 p a 1 1 为后验概率 b a y e s 公式就是从先验概率推导出后验概率的公式 3 2 朴素贝叶斯分类 朴素贝叶斯分类 n a i v eb a y e s i a nc l a s s i f i c a t i o n n b c 是一种基于b a y e s 理 论的简单分类方法 它在很多领域都表现出优秀的性能 丹1 1 2 0 1 朴素贝叶斯分类器 的 朴素 指的是它的条件独立性假设 即假设样本的非类别属性在给定类别的 条件下相互独立 虽然在许多不满足独立性假设的情况下其仍然可能获得较好的 结果 但是大量研究表明此时可以通过各种方法来提高朴素贝叶斯分类器的性能 2 1 1 1 2 2 1 田 n b c 模型将训练实例1 分解成特征向量a 和决策类别变量c 朴素贝叶斯 模型假定特征向量的各分量间相对于决策