数据挖掘技术基础知识.ppt

1、数据挖掘,厦门大学计划统计系,数据挖掘技术 基础知识简介,数据挖掘技术 基础知识简介,一、数据挖掘技术的由来 二、知识发现和数据挖掘的定义 三、数据挖掘能干些什么 四、数据挖掘与其它学科 五、数据挖掘的任务 六、数据挖掘的对象 七、数据挖掘的知识表示 八、数据挖掘的方法和技术,教学内容,数据挖掘技术基础知识, 引言 网络之后的下一个技术热点 数据爆炸但知识贫乏 支持数据挖掘技术的基础 从商业数据到商业信息的进化 逐渐演变的过程 ,一、数据挖掘技术的由来, 引言,一、数据挖掘技术的由来,顾名思义， “数据挖掘” (Data Mining) 就是从大量数据中寻找其规律的技术。它是根据人们的特定要求

2、，从浩如烟海的数据中找出所需的信息来，供人们的特定需求使用。 数据挖掘应用领域非常广阔。先期将在数据积累比较充分的领域银行、证券、电信等领域到应用，以后将在各领域中获得应用。 未来市场不可限量，中国将形成数百亿的市场规模。将在中国形成一个新型的产业。,随着信息化的深入发展，积累的数据会越来越多，所以对数据挖掘技术的需求也会越来越大。数据挖掘技术将被社会长期使用。 数据挖掘技术相对门槛较高。需要有数理统计学、数据库、人工智能等基础，目前国内数据挖掘人才奇缺。 我系已于 2004 年开设面向研究生数据挖掘有关课程，面向本科生的课程也已开设。为了让大家了解数据挖掘的基本内容。我们从数据挖掘有关文献和

3、材料上加工整理了一些有关该课程的基本知识，供参考。, 引言, 网络之后的下一个技术热点,一、数据挖掘技术的由来,1. 我们已生活在一个网络化的时代, 通信、计算机和网络技术正改变着整个人类和社会; 如果用芯片集成度来衡量微电子技术，用 CPU 处理速度来衡量计算机技术，用信道传输速率来衡量通信技术， 那么摩尔定律告诉我们，它们都是以每 18 个月翻一番的速度在增长。 在美国，广播达到 5000 万户用了 38 年；电视用了13 年；Internet 拨号上网达到 5000 万户仅用了 4 年。,全球 IP 网发展速度达到每 6 个月翻一番，国内情况亦然。 1999 年初，中国上网用户为 210

4、 万, 现在已经达到 10300万人 (2005年7月中国互联网络发展状况统计报告) 。 2007 年中国互联网调查报告显示：互联网用户规模达1.82亿人, 较06年增长33.8% , 预计 2008 年中国互联网用户规模将达 2.44 亿; 2007年中国综合门户企业市场营收规模为123.5亿元,较 2006 年增长22.3%。 2008 年中国互联网综合门户企业市场营收规模将达161.9 亿元，广告收入将大幅增长。, 网络之后的下一个技术热点, 网络之后的下一个技术热点,2. 人们不仅要问：就推动人类社会进步而言, 历史上能与网络技术相比拟的是什么技术呢? 有人甚至要把网络技术与火的发明相

5、比拟。 火的发明区别了动物和人; 种种科学技术的重大发现扩展了自然人的体能、技能和智能; 而网络技术则大大提高了人的生存质量和人的素质，使人成为社会人。, 网络之后的下一个技术热点,3. 现在的问题是：网络之后的下一个技术热点是什么？ 让我们来看一些身边俯拾即是的现象： 纽约时报由 60 年代的 1020 版扩张至现在的 100200 版，最高曾达 1572 版； 北京青年报也已是 1640 版；市场营销报已达 100 版。 然而在现实社会中，人均日阅读时间通常为 3045 分钟，只能浏览一份 24 版的报纸。, 网络之后的下一个技术热点,大量信息在给人们带来方便的同时也带来了一大堆问题： 第

6、一是信息过量,难以消化； 第二是信息真假难以辨识； 第三是信息安全难以保证； 第四是信息形式不一致,难以统一 处理。,可怕的数据, 网络之后的下一个技术热点,4. 人们开始提出新的口号:“要学会抛弃信息” 面对这一挑战, 数据开采和知识发现 (DMKD) 技术应运而生, 并显示出强大的生命力。, 数据爆炸但知识贫乏,一、数据挖掘技术的由来,另一方面, 随着数据库技术的迅速发展以及数据库管理系统的广泛应用, 人们积累的数据越来越多。 激增的数据背后隐藏着许多重要的信息, 人们希望能够对其进行更高层次的分析, 以便更好地利用这些数据。,目前的数据库系统可以高效地实现数据的录入、查询、统计等功能,

7、但无法发现数据中存在的关系和规则, 无法根据现有的数据预测未来的发展趋势。 缺乏挖掘数据背后隐藏的知识的手段, 导致了“数据爆炸但知识贫乏” 的现象。, 数据爆炸但知识贫乏, 支持数据挖掘技术的基础,一、数据挖掘技术的由来,数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。 起初各种商业数据是存储在计算机的数据库中的, 然后发展到可对数据库进行查询和访问, 进而发展到对数据库的即时遍历。 数据挖掘使数据库技术进入了一个更高级的阶段, 它不仅能对过去的数据进行查询和遍历, 并且能够找出过去数据之间的潜在联系，从而促进信息的传递。,现在数据挖掘技术已可以马上投入使用, 因为支持的它的基础技术

8、已成熟，他们是： 1. 海量数据搜集 商业数据库正以一个空前的速度增长,且数据仓库正在广泛地应用于各行业。 2. 强大的多处理器计算机 已成熟的并行多 cpu 的技术可以满足对计算机硬件性能越来越高的要求 。 3. 数据挖掘算法 经过了10多年的发展也已经成为一种成熟，稳定，且易于理解和操作的技术。, 支持数据挖掘技术的基础, 从商业数据到商业信息的进化,一、数据挖掘技术的由来,从商业数据到商业信息的进化过程中, 每一步前进都是建立在上一步的基础上的。 表中我们可以看到, 第四步进化是革命性的, 因为从用户的角度来看，这一阶段的数据库技术已经可以快速地回答商业上的很多问题了。 数据挖掘的核心模

9、块技术历经了数十年的发展,(包括数理统计、人工智能、机器学习); 这些成熟的技术, 加上高性能的关系数据库引擎及广泛的数据集成, 让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段;, 从商业数据到商业信息的进化, 数据挖掘逐渐演变的过程,一、数据挖掘技术的由来,电子数据处理的初期, 人们就试图通过某些方法来实现自动决策支持, 当时机器学习成为人们关心的焦点。 随后, 随着神经网络技术的形成和发展, 人们的注意力转向知识工程。 80 年代人们又在新的神经网络理论的指导下, 重新回到机器学习的方法上, 并将其成果应用于处理大型商业数据库。 80 年代末一个新的术语 KDD出现, 人们接受了这个

10、术语,知识工程不同于机器学习那样给计算机输入范例, 让它生成出规则, 而是直接给计算机输入已被代码化的规则, 而计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的成果, 但它有投资大、效果不甚理想等不足。,KDD (Knowledge discovery in database) 就是数据库中的知识发现, 泛指所有从源数据中发掘模式或联系的方法, 人们用 KDD 来描述整个数据发掘的过程, 包括最开始的制定业务目标到最终的结果分析, 而用数据挖掘 (data mining) 来描述使用挖掘算法进行数据挖掘的子过程。,机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输

11、入计算机, 机器通过学习这些范例总结并生成相应的规则, 这些规则具有通用性, 使用它们可以解决某一类的问题;,以后人们却在逐渐使用数据挖掘中, 发现有许多工作可以由统计方法来完成, 并认为最好的策略是将统计方法与数据挖掘有机的结合起来。 数据仓库的发展促使数据挖掘越来越热。 数据仓库技术的发展与数据挖掘有着密切的关系。其的发展是促进数据挖掘越来越热的原因之一。 但是, 数据仓库并不是数据挖掘的先决条件, 因为有很多数据挖掘可直接从操作数据源中挖掘信息。, 数据挖掘逐渐演变的过程, 技术上的定义及含义 商业角度的定义 KDD 过程 数据挖掘需要的人员 ,二、知识发现和挖掘的定义, 技术上的定义及

12、含义,二、知识发现和数据挖掘的定义,1. 定义 知识发现 (KDD) 被认为是从数据中发现有用知识的整个过程。 数据挖掘被认为是KDD 过程中的一个特定步骤, 它是用专门算法从数据中抽取模式。 KDD 过程定义如下： KDD 是从数据集中识别出有效的、新颖的、潜在有用的, 以及最终可理解的模式的高级处理过程。,模式 (Pattern) ： 用语言 L 表示的 F 中部分记录的表达式 E, 它所描述的数据集是集合 F 的一个子集 FE, 我们称表达式 E 为模式；,有效、新颖、潜在有用、可理解： 表示发现的模式应该是新的, 将来有实用价值, 能被用户所理解。,数据集：数据库记录的集合 F；,2.

13、 有关知识发现 (KDD)的几点说明 何为知识? 从广义上理解，数据、信息是知识的表现形式，但是人们更把概念、规则、模式、规律和约束等看作知识。 原始数据 可以是结构化的，如数据库中的数据; 也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。 人们把数据看作是形成知识的源泉，好像从矿石中采矿或淘金一样。, 技术上的定义及含义,所有发现的知识都是相对的。 不是要求发现放之四海而皆准的真理；也不是要去发现崭新的自然科学定理和纯数学公式；更不是什么机器定理证明； 实际上, 所有发现的知识是有特定前提和约束条件, 面向特定领域的;同时还要能够易于被用户理解。最好能用自然语言表

14、达所发现的结果。 发现知识的方法 可以是数学的, 也可以是非数学的; 可以是演绎的, 也可以是归纳的。, 技术上的定义及含义,发现的知识可以被用于 信息管理，查询优化，决策支持和过程控制等，数据自身的维护。 数据挖掘是一门交叉学科 把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。 汇聚了不同领域的研究者, 投身到这一新兴的领域，形成新的技术热点。, 技术上的定义及含义, 商业角度的定义,二、知识发现和数据挖掘的定义,数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理, 从中提取辅助商业决策的关键性数据;

15、简而言之, 数据挖掘其实是一类深层次的数据分析方法。 数据分析本身已有多年的历史, 只不过在过去数据收集和分析的目的是用于科学研究; 由于当时计算能力的限制, 对大数据量进行分析的复杂数据分析方法受到很大限制。,现在, 由于各行业业务自动化的实现, 商业领域产生了大量的业务数据, 这些数据不再是为了分析的目的而收集的, 而是由于纯机会的 (Opportunistic) 商业运作而产生。 分析这些数据也不再是单纯为了研究的需要, 更主要是为商业决策提供真正有价值的信息, 进而获得利润。 但所有企业面临的一个共同问题是： 企业数据量非常大, 而其中真正有价值的信息却很少；, 商业角度的定义,因此从

16、大量的数据中经过深层分析, 获得有利于商业运作、提高竞争力的信息, 就像从矿石中淘金一样, 数据挖掘也因此而得名。 因此, 数据挖掘可以描述为： 按企业既定业务目标, 对大量的企业数据进行探索和分析, 揭示隐藏的、未知的或验证已知的规律性, 并进一步将其模型化的先进有效的方法。, 商业角度的定义, KDD 过程,二、知识发现和数据挖掘的定义,图 数据挖掘视为知识发现过程的一个步骤, KDD 过程,KDD 过程可以概括为三部分： 数据准备 (Data Preparation) 数据挖掘 (Data Mining) 结果的解释和评估(Interpretation 选择实现算法有两个考虑因素： 一是

17、不同的数据有不同的特点； 二是用户或实际运行系统的要求。 有的用户可能希望获取描述型的、容易理解的知识；而有的只是希望获取预测准确度尽可能高的预测型知识。 选择了挖掘算法后，就可以实施数据挖掘操作, 获取有用的模式。, KDD 过程,3. 第三阶段 结果的解释和评估 数据挖掘阶段发现出来的模式, 经评估： 可能存在冗余或无关的模式,需将其剔除; 也可能有不满足用户要求模式，则需要退回到发现过程前面的阶段, 如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一种挖掘算法等等。 另外, KDD 由于最终是面向人类用户的,因此 可能要对发现的模式进行可视化, 或者把结果转换为用户易懂方式，

18、如把分类决策树转换为 “ if then” 规则。, KDD 过程,数据挖掘仅仅是整个过程中的一个步骤。 数据挖掘质量的好坏有两个影响要素： 一是所采用的数据挖掘技术的有效性; 二是用于挖掘的数据的质量和数量 (数据量的大小)。 如果选择了错误的数据或不适当的属性, 或对数据进行了不适当的转换则挖掘的结果不会成功。 整个挖掘过程是一个不断反馈的过程。 比如, 用户在挖掘途中发现选择的数据不太满意, 或使用的技术产生不了期望的结果。这时, 用户需要重复先前的过程, 甚至从头重新开始。, KDD 过程, 数据挖掘需要的人员,二、知识发现和数据挖掘的定义,数据挖掘过程的分步实现,不同的步会需要是有不

19、同专长的人员, 大体可以分为三类： 业务分析人员：要求精通业务, 能够解释业务对象, 并根据各业务对象确定出用于数据定义和挖掘算法的业务需求。 数据分析人员：精通数据分析技术, 并对统计学有较熟练的掌握, 有能力把业务需求转化为数据挖掘的各步操作, 并为每步操作选择合适的技术。,数据管理人员：精通数据管理技术,并从数据库或数据仓库中收集数据。 从上可见, 数据挖掘是一个多种专家合作的过程, 也是一个在资金上和技术上高投入的过程。 这一过程要反复进行，在反复过程中，不断地趋近事物的本质，不断地优化问题的解决方案。, 数据挖掘需要的人员, 数据挖掘都干了些什么？ 通过数据挖掘您可以得到什么？ 数据

20、挖掘应用领域 数据挖掘直邮效益分析 ,三、数据挖掘能干些什么, 数据挖掘都干了些什么？,三、数据挖掘能干些什么,新的产品，需要通过直邮的方式向客户推荐这种产品 使直邮的回应率提高了100,GUS日用品零售商店需要准确的预测未来的商品销售量，降低库存成本 通过数据挖掘的方法使库存成本比原来减少了3.8%, 数据挖掘都干了些什么？,汇丰银行需要对不断增长的客户群进行分类，对每种产品找出最有价值的客户 营销费用减少了30, 数据挖掘都干了些什么？,美国国防财务部需要从每年上百万笔的军火交易中发现可能存在的欺诈现象 发现可能存在欺诈的交易，进行深入调查，节约了大量的调查成本, 数据挖掘都干了些什么？,

21、美国国内税务局需要提高对纳税人的服务水平 合理安排税务官的工作，为纳税人提供更迅捷、更准确的服务, 数据挖掘都干了些什么？, 通过数据挖掘您可以得到什么？,三、数据挖掘能干些什么,发现最有价值的客户,留住那些最有价值的客户, 通过数据挖掘您可以得到什么？,用更小的成本发现欺诈现象, 通过数据挖掘您可以得到什么？, 数据挖掘应用领域,三、数据挖掘能干些什么,电信 ：流失 银行：聚类（细分），交叉销售 百货公司/超市：购物篮分析 （关联规则） 保险：细分，交叉销售，流失（原因分析） 信用卡： 欺诈探测，细分 电子商务： 网站日志分析，攻击检测 税务部门：偷漏税行为探测 警察机关：犯罪行为分析,医学

22、： 医疗保健 竞技运动 ：NBA的布阵安排 生物医学：DNA 数据分析 古代史料：存贮与检索 天文学：虚拟天文台 农产品交易： 化学： 气象： 教育： , 数据挖掘应用领域, 数据挖掘直邮效益分析,三、数据挖掘能干些什么,(Big Bank OLAP 则更进一步告诉你下一步会怎么样 (What next)、和如果我采取这样的措施又会怎么样 (What if)。,2. 数据挖掘和 OLAP 到底有何不同 ? 下面将会解释，他们是完全不同的工具，基于的技术也大相径庭。 OLAP在本质上是一个演绎推理的过程; OLAP 分析是建立一系列的假设，然后通过 OLAP 来证实或推翻这些假设来最终得到自己的

23、结论。如果分析的变量较多,手动验证比较困难。, 数据挖掘和在线分析处理 (OLAP),比如，一个分析师想找到导致贷款拖欠原因。 他可能先做初始的假定: 认为低收入者信用度也低 ; 然后用 OLAP 来验证他这个假设: 如果这个假设没有被证实，他可能去察看那些高负债的账户; 如果还不行，他也许要把收入和负债一起考虑, 一直进行到找到他想要的结果或放弃。,数据挖掘本质上是一个归纳的过程; DM 不是用于验证假定的模式的正确性，而是在数据库中自己寻找模型。 比如，用数据挖掘想找到引起贷款拖欠的风险因素。数据挖掘工具可能帮他找到高负债和低收入是引起这个问题的因素，甚至还可能发现一些分析师从来没有想过或

24、试过的其他因素，比如年龄。 数据挖掘与 OLAP 不同的地方 数据挖掘不是用于验证某个假定的模式（模型）的正确性，而是在数据库中自己寻找模型。他在本质上是一个归纳的过程。, 数据挖掘和在线分析处理 (OLAP),数据挖掘和 OLAP 具有一定的互补性。 在利用数据挖掘出来的结论采取行动之前，你也许要验证一下如果采取这样的行动会给公司带来什么样的影响，那么 OLAP 工具能回答你的这些问题。 而且在知识发现的早期阶段，OLAP 工具还有其他一些用途。 可以帮你探索数据，找到哪些是对一个问题比较重要的变量，发现异常数据和互相影响的变量。这都能帮你更好的理解你的数据，加快知识发现的过程。, 数据挖掘

25、和在线分析处理 (OLAP), 数据挖掘，机器学习和统计,四、数据挖掘与其它学科,数据挖掘利用了人工智能（AI）和统计分析的进步所带来的好处。这两门学科都致力于模式发现和预测。 数据挖掘不是为了替代传统的统计分析技术。相反，他是统计分析方法学的延伸和扩展。 大多数的统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求很高。,随着计算机计算能力的不断增强，我们有可能利用计算机强大的计算能力只通过相对简单和固定的方法完成同样的功能。 一些新兴的技术同样在知识发现领域取得了很好的效果，如神经元网络和决策树，在足够多的数据和计算能力下，他们几乎能自动就能完成许多有

26、价值的功能。 数据挖掘就是利用了统计和人工智能技术的应用程序，把高深复杂的技术封装起来，使人们不用掌握这些技术也能完成同样的功能，而更专注于所要解决的问题。, 数据挖掘，机器学习和统计, 数据挖掘与可视化技术,四、数据挖掘与其它学科,可视化技术在数据挖掘的各个阶段都起着重要的作用。 特别是在数据准备阶段, 用户可能要使用散点图、直方图等统计可视化技术来显示有关数据,以期对数据有一个初步的了解,从而为更好地选取数据打下基础。 在挖掘阶段, 用户则要使用与领域问题有关的可视化工具。 在表示结果阶段, 则可能要用到可视化技术以使得发现的知识更易于理解。, 软硬件发展的影响,四、数据挖掘与其它学科,使

27、数据挖掘这件事情成为可能的关键一点是计算机性能价格比的巨大进步。 磁盘价格的大幅度降低，在很大程度上改变了企业界对数据收集和存储的态度。 如果每兆的价格是10元，那存放 1TB的价格是一千万元，但当每兆的价格降为1 毛钱时，存储同样的数据只有十万元 2010 年3月7日硬盘报价: 希捷 1TB 价格：￥585 (0.058分/m),内存 RAM 也同样降价迅速 几年之内每兆内存的价格由几百块钱降到几块钱。通常PC都有64M内存，工作站达到256M，拥有上 G 内存的服务器已不是什么新鲜事了（2003年） 现在普通计算机的内存都达到 2G4G 据 09 年3月2 日内存报价： DDRII800,

28、 容量：2G，价格： ￥120 据 10 年3月7 日内存报价： DDRII800, 容量：2G，价格：￥285, 软硬件发展的影响,计算机计算能力价格的降低也非常显著。 每一代芯片的诞生都会把 CPU 的计算能力提高一大步。 目前几乎所有的服务器都支持多个CPU,甚至能让成百上千个 CPU 同时工作。 在单个 CPU 计算能力大幅提升的同时，基于多个CPU的并行系统也取得了很大的进步。 2010年3月7日报价: 一般的：Intel Core2 E7500 ￥740 (2.93GH) Intel Core2 Extreme QX9650 ￥ 1430 (09年4000) 最贵的 ： Intel

29、 酷睿i7 975 ￥6200 (主频 3.33GH), 软硬件发展的影响, 软硬件发展的影响,基于并行系统的数据库管理系统也给数据挖掘技术的应用带来了便利。如果你有一个庞大而复杂的数据挖掘问题要求通过访问数据库取得数据，那么效率最高的办法就是利用一个本地的并行数据库。 所有这些都为数据挖掘的实施扫清了道路，随着时间的延续，我们相信这条道路会越来越平坦。, 关联分析 时序模式 聚类 分类 偏差检测 预测 ,五、数据挖掘的任务, 关联分析,五、数据挖掘的任务,关联分析是从数据库中发现知识的一类重要方法。 若两个或多个数据项的取值之间重复出现且概率很高时, 它就存在某种关联, 可以建立起这些数据项

30、的关联规则。 例如, 买面包的顾客有 90% 的人还买牛奶，这是一条关联规则。 若商店中将面包和牛奶放在一起销售, 将会提高它们的销量。, 时序模式,五、数据挖掘的任务,通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。例如： 在所有购买激光打印机的人中, 半年后 80%的人再购买新硒鼓, 20%的人用旧硒鼓装碳粉; 在所有购买了彩色电视机的人中, 有 60% 的人再购买 VCD 产品。 例如在零售市场上, 找到另一个有相似销售的部门, 在股市中找到有相似波动的股票。,这些规则 有什么用？, 聚类,五、数据挖掘的任务,类是把一组个体按照相似性归成若干类别, 即 “物以类聚”。

31、如数据库中的数据可以划分为一系列有意义的子集, 即类。 聚类是识别出分析对象内在的规则, 按照这些规则把对象分成若干类。 例如：将申请人分为高度风险申请者，中度风险申请者，低度风险申请者。 目的是使得同一类的个体间的距离尽可能小,而不同类的个体间的距离尽可能大。, 分类,五、数据挖掘的任务,按照分析对象的属性、特征，建立不同的组类来描述事物。分类在数据挖掘中是非常重要的任务，目前在商业上应用最多。 例如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷款的客户，以采取相应的贷款方案。 分类的目的是学会一个分类函数或分类模型(也常常称作分类器), 该模型能把数据库中

32、的数据项映射到给定类别中的某一个。, 偏差检测,五、数据挖掘的任务,数据库中的数据存在着很多异常情况, 从数据分析中发现这些异常情况，揭示内在的原因，以引起人们对它更多的注意。 例如：在银行的 100 万笔交易中有 500 例的欺诈行为, 银行为了稳健经营, 就要发现这 500 例的内在因素, 减小以后经营的风险。 偏差包括很多有用的知识, 如以下 4 类： 分类中的反常实例、模式的例外、观察结果对模型预测的偏差、量值随时间的变化。, 预测,五、数据挖掘的任务,预测是利用历史数据找出变化规律, 建立模型, 并用此来预测未来数据的种类, 特征等; 典型的方法是回归分析, 即利用大量的历史数据,

33、以时间为变量建立线性或非线性回归方程。 近年来, 新发展起来的神经网络方法, 能进行非线性函数的判别。 分类也能进行预测, 但分类一般用于离散值; 回归预测则用于连续值。神经网络方法预测既可用于连续数值, 也可用于离散数值。, 关系数据库 文本数据 图像和视频数据 Web 数据 ,六、数据挖掘的对象, 关系数据库,六、数据挖掘的对象,目前建立的数据库都是关系数据库。数据挖掘方法也主要是研究数据库中属性之间的关系, 挖掘出多个属性取值之间的规则。 由于关系数据库的特点, 促使了数据挖掘方法的改善。 数据库的特点如下： 数据动态性 数据不完整性 数据噪声 数据冗余性 数据稀疏性 海量数据,1. 数

34、据动态性 数据的动态变化是数据库的一个主要特点。由于数据的存取和修改，使数据的内容经常发生变化，这就要求数据挖掘方法能适应这种变化。渐增式数据挖掘方法就是针对数据变化，使挖掘的规则知识能满足变化后的数据库内容。 2. 数据不完整性 数据不完整性主要反映在数据库中记录的域值丢失或不存在 (空值)。这种不完整数据给数据挖掘带来了困难。为此，必须对数据进行预处理，填补该数据域的可能值。, 关系数据库,3. 数据噪声 由于数据录入等原因，造成错误的数据，即数据噪声。含噪声的数据挖掘会影响抽取模式的准确性，并增加了数据挖掘的困难度。 在数据挖掘中要考虑噪声的影响，利用概率方法排除这些噪声。 4. 数据稀

35、疏性 数据稀疏性表现在实例空间中数据稀疏，数据稀疏会使数据挖掘丢失有用的模式。, 关系数据库,5. 数据冗余性 这表现在同一信息在多处重复出现。函数依赖是一个通常的冗余形式。冗余信息可能造成错误的数据挖掘, 至少有些挖掘的知识是用户不感兴趣的。为避免这种情况的发生, 数据挖掘时, 需要知道数据库中有哪些固有的依赖关系。 6. 海量数据 数据库中的数据在不断增长，已出现很多海量数据库。数据挖掘方法需要逐步适应这种海量数据挖掘，如建立有效的索引机制和快速查询方法等。, 关系数据库, 文本数据,六、数据挖掘的对象,文本是以文字串形式表示的数据文件。 文本分析包括： 关键词或特征提取； 相似检索； 文

36、本聚类； 文本分类。,1. 关键词或特征提取 一篇文本中，标题是该文本的高度概括。标题中的关键词是标题的核心内容。它的提取对于掌握该文本的内容至关重要。 文本中的特征如人名、地名、组织名等是某些文本中的重要信息，特征提取对掌握该文本的内容很重要。 2. 相似检索 对文本中关键词的相似检索是了解文本内容的一种重要方法。例如，“专家系统” 与 “人工智能” 两个关键词是有一定联系的，研究专家系统的文本，一定属于人工智能的研究领域。, 文本数据,3. 文本聚类 对于文本标题中关键词 (主题字) 的相似匹配是对文本聚类的一种简单方法。定义关键词的相似度, 将便于文本的简单聚类,类中文本满足关键词的相似

37、度，类间文本的关键词超过相似度。 4. 文本分类 将文本分类到各文本类中，一般需要采用一个算法，这些算法包括分类器算法、近邻算法等，这需要按文本中的关键词或特征的相似度来区分。, 文本数据, 图像和视频数据,六、数据挖掘的对象,图像和视频数据是典型的多媒体数据。 数据以点阵及帧形式存储, 数据量很大。 图像与视频的数据挖掘包括： 图像与视频特征提取； 基于内容的相似检索； 视频镜头的编辑与组织等。,1. 图像与视频特征提取 图像与视频特征有颜色、纹理和形状等。这些特征提取是用于基于内容的相似检索。海水是蓝色、房屋的形状及颜色等,都需要从大量图像和视频数据中提取。 2. 基于内容的相似检索 根据

38、图像、视频特征的分布、比例等进行基于内容的相似检索, 可以将图像和视频数据进行聚类以及分类，也能完成对新图像或视频的识别。如对遥感图像或视频的识别，这种应用非常广泛，例如，森林火灾的发现与报警，河流水灾的预报等。, 图像和视频数据,3. 视频镜头的编辑与组织 镜头代表一段连续动作 (视频数据流)。 典型的镜头编辑如足球赛的射门、某段新闻节目等, 都需要在冗长的视频数据流中进行自动裁取。 经过编辑的镜头，按某种需要重新组织，将形成特定需求的新视频节目。如足球射门集锦，某个新闻事件的连续报道等。, 图像和视频数据, Web 数据,六、数据挖掘的对象,随着 Internet 的发展和普及，网站数目的

39、迅速增长以及上网人数的剧烈增多，使网络数据量呈指数增长，Web 数据挖掘已成为新课题。 Web 数据挖掘具有如下特点： 异构数据集成和挖掘 半结构化数据模型抽取 总之 Web 数据挖掘正在逐步形成热点 ，这方面的文章特别多。,1. 异构数据集成和挖掘 Web 上每一个站点是一个数据源，各数据源都是异构的，形成了一个巨大的异构数据库环境。 将这些站点的异构数据进行集成, 给用户提供一个统一的视图, 才能在 Web 上进行数据挖掘, Web 数据,2. 半结构化数据模型抽取 Web 上的数据非常复杂, 没有特定的模型描述。虽然每个站点上的数据是结构化的, 但各自的设计对整个网络而言是一个非完全结构

40、化的数据，称为半结构化数据。 对半结构化模型的查询和集成, 需寻找一种半结构化模型抽取技术来自动抽取各站点的数据。 Net Perceotian 公司采用了 “实时建议” 技术, 能够根据用户以往的浏览行为来预测该用户以后的行为, 从而为用户提供个性化的浏览建议。, Web 数据, 规则 决策树 知识基 网络权值 公式 案例 ,七、数据挖掘的知识表示, 规则,七、数据挖掘的知识表示,规则知识由前提条件和结论两部分组成。 前提条件由字段项 (属性取值的合取 (与) 和析取 (或) 组合而成， 结论为决策字段项的取值或者类别组成。 我们用一个简单例子进行说明， 如两类人群的 9 个元组 (记录)

41、如表 2 所示。 利用数据挖掘方法, 将得到如下规则知识： IF (发色=金色红色)(眼睛=蓝色灰色) THEN 第一类人 IF (发色=黑色)(眼睛=黑色) THEN 第二类人,即： 凡是具有金色或红色的头发，并且同时具有蓝色或灰色眼睛的人属于第一类人; 凡是具有黑色头发或黑色眼睛的人属于第二类人。, 决策树,七、数据挖掘的知识表示,数据挖掘的信息论方法所获得的知识一般表示为决策树。 如 ID3 方法的决策树是由信息量最大的字段 (属性) 作为根结点，它的各个取值为分枝，对各个分枝所划分的数据元组 (记录) 子集，重复建树过程，扩展决策树，最后得到相同类别的子集，以该类别作为叶结点。 例如，

42、上例的人群数据库，按 ID3 方法得到的决策树如图 所示。, 知识基,七、数据挖掘的知识表示,数据挖掘方法能计算出数据库中字段项 (属性) 的重要程度, 对于不重要的字段可以删除, 对数据库中的元组 (记录) 能按一定的原则合并, 这样, 通过数据挖掘的方法能大大压缩数据库的元组和字段项, 最后得到浓缩数据, 称为知识基。它是原数据库的精华, 很容易转换成规则知识。 例如, 上例的数据库, 通过计算可以得出身高是不重要的字段, 删除该项后, 再合并相同数据元组, 得到的浓缩数据如表所示。, 知识基, 网络权值,七、数据挖掘的知识表示,神经网络方法经过对训练样本的学习后, 所得到的知识是网络连接

43、权值和结点的阈值, 一般表示为矩阵和向量。 例如, 异或问题的网络权值和阈值分别为：, 公式,七、数据挖掘的知识表示,对于科学和工程数据库，一般存放的是大量实验数据(数值)。它们中蕴涵着一定的规律性，通过公式发现算法，可以找出各种变量间的相互关系，用公式表示。 例如，太阳系行星运动数据中包含行星运动周期 (旋转一周所需天数)，以及它与太阳的距离 (围绕太阳旋转的椭圆轨道的长半轴，百万公里) 具体数据如表4所示。通过某物理定律发现系统 可以得到开普勒第三定律：d3/p2=25 。, 案例,七、数据挖掘的知识表示,案例是指人们经历过的一次完整的事件。 当人们要解决一个新问题时, 总是先回顾自己以前

44、处理过的类似事件(案例), 利用以前案例中解决问题的方法或者的结果, 作为参考并进行适当的修改,以解决当前新问题。 利用这种思想建立起基于案例推理 (Case Based Reasoning, CBR) 。 CBR 的基础是案例库, 在案例库中存放着大量成功或失败的案例。,可见, 案例是解决新问题的一种知识。 案例知识一般表示为三元组： 问题描述：对求解的问题及周围世界或环境的所有特征的描述； 解 描 述：对问题求解方案的描述； 效果描述：描述解决方案后的结果情况，是失败还是成功。, 案例, 归纳学习方法 仿生物技术 公式发现 统计分析方法 模糊数学方法 可视化技术 ,八、数据挖掘的方法和技术

45、, 归纳学习方法,八、数据挖掘的方法和技术,归纳学习方法是目前重点研究的方向，成果较多, 从技术上看, 分为信息论方法和集合论方法两大类。每类方法又含多个具体方法。 1. 信息论方法 (决策树方法) 该方法是利用信息论的原理建立决策树。 信息论方法最后获得的知识表示形式是决策树, 故一般文献中称它为决策树方法。 该类方法的实用效果好, 影响较大。 信息论方法中较有特色的方法 ID3 等方法,ID3 等方法 Quiulan 研制的 ID3 方法是利用信息论中互信息(信息增益)寻找数据库中具有最大信息量的字段,建立决策树的一个结点, 再根据字段的不同取值建立树的分枝, 再由每个分枝的数据子集重复建

46、树的下层结点和分枝的过程, 这样就建立了决策树。 这种方法对愈大的数据库效果愈好。 ID3 方法在国际上影响很大 ID3 方法以后又陆续开发了 ID4、 ID5、C4.5 等。, 归纳学习方法, 归纳学习方法,2. 集合论方法 集合论方法是开展较早的方法。 近年来，由于粗糙集理论的发展使集合论方法得到了迅速的发展。 这类方法中包括： 覆盖正例排斥反例的方法 (典型的方法是 AQ 系列方法) 概念树方法 粗糙集(Rough Set)方法 关联规则挖掘, 归纳学习方法,粗糙集（Rough Set）方法 在数据库中将行元素看成对象, 列元素是属性 (分为条件属性和决策属性) 。 等价关系 R 定义为

47、不同对象在某个 (或几个) 属性上取值相同, 这些满足等价关系的对象组成的集合称为该等价关系 R 的等价类。条件属性上的等价类 E 与决策属性上的等价类 Y 之间有 3 种情况： 下近似：Y 包含 E； 上近似：Y 和 E 的交为非空 无关：Y 和 E 的交为空。, 归纳学习方法,条件属性“头发(A)”的等价类: E =1,3,4,5,9,2,6,7, 8 于决策属性 “类别”上的等价类: Y= 1,2,3,4, 5,6,7,8,9 下近似: AY1=E2= 2; AY2= E3 = 6,7,8 上近似: Y1=E1E2=1,2,3,4,5,9; Y2=E1E3=1,3,4,9,无关情况不存在

48、规则。,对下近似建立确定性规则；,对上近似建立不确定性规则 (含可信度);, 归纳学习方法,关联规则挖掘 关联规则挖掘是在交易事务数据库 D中，挖掘出不同项 (商品) 集的关联关系, 即发现哪些商品频繁地被顾客同时购买。 对于 D 中不同项集 (如 A 和 B 两个商品), 若: 同时出现的概率(P(AB)大于min_sup, 且在包含一个项集 (如A) 的所在事务中, 同时也包含另一个项集 (如B) 的条件概率 (P(B|A) 大于 min_conf 时, 则存在关联规则有 (即 AB)。,支持度 P(AB)： 表示该规则所代表的事例 (元组) 占全部事例 (元组) 的百分比(说明普遍意义)

49、。 如买面包和买牛奶的顾客占全部顾客的百分比.,置信度 P(B|A) 表示该规则所代表事例占满足前提条件事例的百分比。 如买面包又买牛奶的顾客占买面包顾客中的 90%, 可信度为 90%。,最小置信度 min_conf 它反应了关联规则的最低可靠度。,最小支持度 min_sup： 它表示了一组物品集在统计意义上的需满足的最低程度。, 归纳学习方法,关联规则发现的主要对象是事务型数据库, 其中针对的应用则是售货数据(货篮数据)。 由于条形码技术的发展, 零售部门可以利用前端收款机收集存储大量的售货数据。因此, 如果对这些历史事务数据进行分析, 则可对顾客的购买行为提供极有价值的信息。例如,可以帮

50、助如何摆放货架上的商品 (如把顾客经常同时买的商品放在一起), 帮助如何规划市场(怎样相互搭配进货)。 由此可见,从事务数据中发现关联规则, 对于改进零售业等商业活动的决策非常重要。, 归纳学习方法,覆盖正例排斥反例方法 覆盖正例排斥反例方法是利用覆盖所有正例, 排斥所有反例的思想来寻找规则。 比较典型的有 AQ11 方法, 洪家荣改进的 AQ15 方法以及洪家荣的 AE5 方法。 AQ 系列的核心算法是在正例集中任选一个种子, 到反例集中逐个比较, 对字段取值构成的选择在相容时则舍去, 相斥则保留。按此思想循环所有正例种子, 将得到正例集的规则 。 AE 方法是在扩张矩阵中寻找覆盖正例排斥反

51、例的相同字段取值的公共路(规则) 。, 归纳学习方法,概念树方法 数据库中记录的属性字段按归类方式进行合并, 建立起来的层次结构称为概念树。 如 “城市” 概念树的最下层是具体市名或县名 (如长沙、南京等), 它的直接上层是省名 (湖南、江苏等), 省名的直接上层是国家行政区 (华南、华东等), 再上层是国名 (中国、日本等) 。 概念树提升的方法可以大大浓缩数据库中的记录。对多个字段的概念树提升, 将得到高度概括的知识基表, 再转换成规则。, 归纳学习方法,例如我们的任务是想知道厦大计统系中教师的特征，相关的属性有姓名、性别、年龄、籍贯、学历、工资。“籍贯” 的概念树如下图, 归纳学习方法,

52、可先从一个大的数据库中获得如表所示的相关数据即目标类(原始知识基表)。,与问题无关,提升为老中青,提升为高中低,通过第1条元组可以得到规则知识： “在计统系中的教师中有 24% 的人是青年男性，籍贯是湖南，且具有硕士学历，工资收人为中等。”, 仿生物技术,八、数据挖掘的方法和技术,仿生物技术典型的方法是神经网络方法和遗传算法, 这两类方法已经形成了独立的研究体系。它们在数据挖掘中也发挥了巨大的作用, 我们将它们归并为仿生物技术类。 . 神经网络方法 神经网络方法模拟了人脑神经元结构, 以 MP 模型和 Hebb 学习规则为基础, 建立了三大类多种神经网络模型。,前馈式网络 以感知机、BP反向传

53、播模型和函数型网络为代表, 此类网络可用于预测、模式识别等方面。 反馈式网络 以 Hopfield 的离散模型和连续模型为代表, 分别用于联想记忆和优化计算。 自组织网络 以 ART 模型、Kohonen 模型为代表，用于聚类。, 仿生物技术,神经网络的知识体现在网络连结的权值上，是一个分布式矩阵结构。 神经网络的学习体现在神经网络权值的逐步计算上 (包括反复迭代或者是累加计算) 下面以BP反向传播模型说明其工作原理。, 仿生物技术,f (x) = 1 / (1 + e-x) yi = f (jWij xji),2. 遗传算法 遗传算法是模拟生物进化过程的算法。 它由以下 3 个基本算子组成。 繁殖( 选择) 指从一个旧种群 (父代) 选择出生命力强的个体产生新种群 (后代) 的过程。 交叉(重组) 交叉是指选择两个不同个体(染色体) 的部分 (基因) 进行交换，形成新个体。 变异(突变) 变异是