数据挖掘及其算法概览.ppt

1、哈尔滨工程大学计算机科学与技术学院 软件与理论研究所 数据库与知识工程研究室 王念滨 教授 博导 ,新一代数据库系统,数据库,新一代数据库系统课程安排,主动数据库 分布式数据库 知识库,数据仓库 数据集成 数据挖掘,张建沛,王念滨,基础,学习,课 程 体 系,第 1 章 数据挖掘及其算法概览,第1章 数据挖掘及其算法概览,主要内容,数据库知识发现基本概念,数据挖掘算法概览,典型数据挖掘算法,数据集成概览,第1章 数据挖掘及其算法概览,主要内容,数据库知识发现基本概念,数据挖掘算法概览,典型数据挖掘算法,数据集成概览,第1章 数据挖掘及其算法概览,数据挖掘概述,数据挖掘技术是人们长期对数据库技术

2、进行研究 和开发的成果。数据挖掘和知识发现源于人工智能的 学习，并在20世纪80年代有了长足的进展。 目前，数据挖掘技术已经在市场分析、政府管理、 医疗卫生、科学探索、金融及制造业得到应用并取得 了一定的实效。,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,数据挖掘的目标是支持利用数据进行合理的决策。 数据挖掘可以与数据仓库结合起来帮助实现某些类型的 决策。,数据库知识发现基本概念,数据挖掘目标,第1章 数据挖掘及其算法概览,四个方面的原因促进了数据挖掘技术产生、发展应用。数据挖掘技术是信息技术发展到一定程度的必然结果 A.大容量数据库的出现。 B.先进计算机技术应用。 C.现代化经营

3、管理的需要。 D.对数据挖掘精、深能力的要求。,数据挖掘产生的背景,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘产生的背景,沃尔玛 每天交易记录2千万条, 客户数据库记录11T. 1998年.,黑龙江省地方税务局 每月纳税高峰期(7/8/9), 纳税记录平均每天新增 1百万条.2009年 数据库记录容量1.5T.,数据量不断增长,先进计算机技术应用,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘产生的背景,对海量数据集成和处理技术的发展（并行、分布式 数据库系统）； 数据仓库技术的不断成熟； 网络及数据搜索技术的牵引。 人工智能技术的发

4、展,现代化经营管理的需要,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘产生的背景,1、 根据销售数据库，发现某类商品用户消费特征 （尿布与牛奶的故事）。 2、根据纳税人财务数据和纳税数据，通过建立模型，发现偷税漏税情况 3、根据信用卡消费情况，建立监测模型，发现信用卡欺诈情况； 4、根据病人病情分析，建立医疗模型；,纳税人基础信息,纳税人应税信息,纳税人其它信息,外部数据源,分组 规则,按 照 规 则 分 组,行为规律分析,组间交叉分析,纳税人应税地点、方式,纳税人应税品种,纳税人所属地区、行业,欠税发生频率,欠税高峰期,基础近似，分组不同原因,纳税人分组变化的条件及可能性,

5、不同分组的主要差别,统 计 分 析 归 纳 演 绎,确定稽查检查对象,制定鼓励政策,信用等级评定,纳税人辅导,税务机关,税收计划,基于数据仓库的纳税人信息辅助分析软件,财务报表对比,辅助分析系统,税务机关,历史数据仓库,聚类、决策树等,第1章 数据挖掘及其算法概览,大量的数据是当今信息社会的特征。是社会的宝贵财富。然而 面对海量的数据，我们往往无法适从，无法发现数据中存在的关系 和规则，无法根据现有的数据预测未来的发展趋势。导致了“我们 淹没在数据的海洋中，但却缺少知识”的现象。 80年代中后期，人们开始考虑运用知识发现技术从这些数据中 挖掘出对我们有用的知识。大量的数据背后隐藏了很多具有决策

6、意 义的信息，通过对海量数据的分析，发现数据之间的潜在联系，为 人们提供自动决策支持。,数据库知识发现基本概念,数据挖掘产生的背景,对数据挖掘精、深能力的要求,应用和需求是技术发展的动力 A.大容量数据库的出现。 B.先进计算机技术应用。 C.现代化经营管理的需要。 D.对数据挖掘精、深能力的要求。 我们拥有丰富的资源，但却缺乏有用的信息 解决方法 数据仓库与OLAP 数据挖掘、知识发现,数据挖掘产生的背景,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,数据挖掘的演变进程,数据库知识发现基本概念,演变阶段,商业问题,支持技术,产品厂家,产品特点,数据搜集（

7、20 世纪60年代）,数据访问（20 世纪80年代）,数据仓库决策 支持（20世纪 90年代,数据挖掘（正 在流行）,“过去五年中整个有关 联锁超市总收入是 多少？”,“联锁超市第一分部去 年三月的销售额是 多少？”,“联锁超市第一分部去 年三月的销售额是多 少？第二分部据此可 得出什么结论？”,“下个月第二分部的销售 会怎么样？为什么？”,计算机、磁带和磁盘,关系数据库 （RDBMS），结构化 查询语言（SQL）， ODBC,OLAP、多维数据库和 数据仓库,高级算法、多处理器 计算机和海量数据库,IBM和CDC,Oracle、Sybase 、Informix、 IBM和 Microsoft

8、,Pilot、Comshare 、Arbor、 Cognos和 Microstrategy,Pilot、Lockheed 、IBM、SGI 和其他初创公司,提供历史性的静态 的数据,在记录级提供历史性 动态数据,在各种层次上提供 回溯的动态数据,提供预测性信息,工具特点,分析重点,分析目的,数据集大小,启动方式,技术状况,传统数据分析工具（DSS/EIS）,回顾型的、验证型的,已经发生了什么,从最近的销售文件中列出最大客户,数据维、维中属性数、维中数据均是 少量的,企业管理人员、系统分析员、管理 顾问启动与控制,成熟,数据挖掘工具,预测型的、发现型的,预测未来的情况、解释发生的原因,锁定未来的

9、可能客户，以减少 未来的销售成本,数据维、维中属性数、维中数据 均是庞大的,数据与系统启动，少量的人员指导,统计分析工具已经成熟，其他工具正在 发展中,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘工具与传统数据分析工具的比较,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,参考文献 以上的统计数据来源于文献 Written By Walter Alberto Aldana MIT 2000 网上可以找到。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘技术定义,从技术角度看，数据挖掘就是应用一系列技术从(大型数据 库或数据仓库的)数据中提取人们感兴趣的信

10、息和知识，这些知识 或信息是隐含的、事先未知而潜在有用的，所提取的知识表示为 概念、规则、规律和模式等形式。 从商业角度看，数据挖掘是新型的商业分析处理技术。它是 从大型数据库或数据仓库中发现并提取隐藏在其中信息的一种新 技术，帮助决策者寻找数据间潜在的关联，发现被忽略的因素。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘的三股研究力量,1、从数据库（应用需求）的角度来研究数据挖掘问题 参考文献 Data Mining: An overview from Database Perspective IEEE Transactions on Knowledge and Data

11、Engineering 1996, 8(6): 866-883,2、从统计学（应用需求）的角度来研究数据挖掘问题 参考文献 Statistical Themes and Lessons for Data Mining Data Mining and Knowledge Discovery,1996,3、从机器学习的角度来研究数据挖掘问题,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘领域国外著名期刊和会议,1、IEEE Transactions on Knowledge and Data Engineering 2、Data Mining and Knowledge Disco

12、very 3、Knowledge and Information Systems 4、Intelligent Data Analysis 5、Information Systems 6、Journal of Intelligent Information System,期刊,会议,1、ACM SIGKDD 2、ICDM 3、PKDD, PAKDD 4、ACMSIGMON/PODS，VLDB, CIKM, ICDE, ICML（数据库领域） 5、AAAI,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,参考书籍,数据挖掘：概念和技术 范明 孟小峰 译,数据挖掘原理 张银奎译,数据挖掘导论

13、范明 范宏建 译,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据(挖掘)的发展历程,1960S及以前 文件系统,1970S 层次及网状数据库,1980S前期 关系数据库,1980S后期 关系数据库逐渐成熟，并成为商业市场主要产品,1990S 数据仓库、数据挖掘、网络数据库,2000S 数据集成、流数据库、XML数据库、数据空间、数据挖掘应用,第1章 数据挖掘及其算法概览,数据、信息与知识,数据（DATA）： 描述事物的符号记录称为“数据”。 包含两层含义：存储在某一介质上的可加以鉴定的符号资料； 数据内容是事物特征的反映或者描述。,信息（INFORMATION）： 是对数据的解释。

14、数据经过处理并经 过解释才有意义，才成为信息。,知识（Knowledge）:知识是通过实践、研究、联系或调查获得 的关于事物的事实和状态的知识,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,学生的分数-数据,成绩最好的学生的分数-信息,成绩最好的学生的特点-知识,数据、信息与知识,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据挖掘与数据库知识发现,数据挖掘是数据库知识发现的过程之一。,知识发现：从数据集中抽取和精化新的模式的过程。 知识发现的范围非常广泛，可以是经济、工业、农业、军事等 的数据，数据的形态包括数字、符号、图形、图像、声音等。 数据组织

15、方式各不相同，可以使结构化的、半结构化的、非结 构化的。 知识发现的结果可以表示成多种形式，包括规则、法则、规律、 方程等。 由于关系数据库具有统一的组织结构、一体化的查询语言、关系 之间及属性之间具有平等性等优点，因此基于数据库（特别是关 系数据库）的知识发现（KDD：Knowledge Discovery in Database ）是知识发现研究的主体和热点。,第1章 数据挖掘及其算法概览,KDD的定义 从数据集中识别出有效的、新颖的、潜在有用的，以及 最终可以理解的模式的非平凡过程。 数据集是一组事实F（如关系数据库中的记录）； 模式是一个用语言L来表示的一个表达式E，它可以用来描述 数

16、据集F的某个子集FE，E作为一个模式要求它比对数据子集FE 的枚举要简单（所用的描述信息量要少）。 非平凡(nontrivial)是指KDD过程不是线性的，具有智能性和自动 性，并且往往是一个反复的过程。 有效性是指发现的模式对于新的数据仍保持一定的可信度。 新颖性是指发现的模式应该不同于以往的知识或模式。 潜在有用性是指发现的知识将来有实际效用。,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程,数据源,数据源,。 。,数据,目标 数据,预处理 后 的数据,信息,知识,数据准备,数据挖掘,结果表达及解释,数据集成,数据选择,预处理,数据挖掘,表达及

17、解释,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程-数据准备,数据准备：数据选取、数据预处理和数据转换。 数据选取的目标是确定发现任务的操作对象，即目标数据， 它是根据用户需求从原始数据库中抽取的一组数据； 数据预处理一般包括消除噪声、推导计算缺值数据、消除 重复记录、完成数据类型转换（如将连续值数据转换为离散值 数据）； 数据转换的主要目标是消减数据维数或降维。即从初始特 征中找出真正有用的特征并减少数据挖掘时要考虑的特征或者 变量的个数。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程-数据准备,数据选取,数据挖掘通常不需要所有的数据。有些数据

18、对象和数据属 性对建立模型获得模式是没有影响的，这些数据的加入会大大 影响挖掘效率，甚至可能导致数据挖掘结果的偏差。 对数据库表的选择，有两种方式，纵向选择-列属性选择； 横向选择-元组或记录选择。 数据选择是对发现任务和数据本身的内容的理解的基础上。 寻找依赖于发现目标的表达数据的有用特征，以减少数据规模， 从而在尽可能保持数据原貌的前提下最大限度地精简数据量。 通过数据选取使数据的规律性和潜在特征更加明显。 数据选取在实际应用中非常重要，但DM领域对其也就并不 深入，往往认为数据挖掘时，数据已经准备好了。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程-数据准备,数据

19、预处理,也称数据清理或者数据清洗。在数据中消除错误和不一致， 并解决对象识别问题的过程。主要包括空值处理、噪声数据处 理、及不一致数据处理等。也就是说通过数据预处理去除噪声 或无关数据，并处理数据中缺失的数据项或域。例如，关于“高 薪”、“低收入”等概念在不同的数据集合中有不同的定义，需要 进行统一。需要对数据值进行标准化，例如，人员出身地在不同 的集合中表示不同，例如一个集合中为哈市，一个集合中为哈尔 滨市。解决异名同义问题，以及同名异义等问题。 数据清理是一个困难、繁琐的问题。DM领域对此研究并不 多，在数据集成领域研究比较丰富。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识

20、发现的过程-数据准备,数据集成,数据挖掘需要对数据进行集成。将多个数据源中的数据合并 存放在统一的数据存储中。数据集成主要涉及三个方面的问题： 模式集成：从多个异构的数据库、文件、遗留系统中提取并 集成数据，解决语义二义性，统一不同的数据格式，消除冗余， 重复等问题。模式集成涉及实体识别。目前该领域研究比较热， 但问题多难以形成统一的解决方法。目前研究包括元数据、元知 识（Meta data, Meta knowledge）及本体（Ontology）等方法。 数据值冲突检测及处理：表示、比例、单位、编码等不同的 解决方法。例如，货币单位等 冗余：如同一属性多次出现等。在数据仓库和数据挖掘领域，

21、 也许不需要规范化（去规范化）。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程-数据挖掘,数据挖掘：确定目标和任务。如数据总结、分类、聚类、关联规则 发现或者序列模式发现等。确定任务后，考虑采用何种算法。同样 的任务可以采用不同的算法来实现。选择算法的考虑因素包括：不 同的数据有不同的特点，因此需要采用与之相关的算法来处理；用 户或实际运行系统的要求，有的用户可能希望获得描述性、易于理 解的描述性知识，有的用户可能希望获得预测准确度高的预测型知 识。 数据挖掘仅仅是整个过程的一个部分，数据挖掘质量的好坏有两个 影响因素。采用的数据挖掘技术的有效性；用于挖掘数据的质量和

22、数量。数据挖掘过程是一个非平凡的过程，需要不断反馈。可视化 在数据挖掘中扮演重要的角色。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,知识发现的过程-结果表达于解释,结果解释和评价：数据挖掘阶段发现的模式，经过用户或机器的 评价，可能存在冗余或无关的模式，需要将其剔除。模式也可能 不满足用户的要求，需要重新进行KDD过程。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,KDD知识发现抽取知识的类型和表示,依赖关系； 分类知识； 描述性知识； 偏差性知识,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,1 依赖关系 若其中一项的数据可以预测另一项的数据，即A-B，则 称这

23、两项存在依赖关系。当确定依赖关系不存在时，可以附加 不确定度量： A-（0.95）B。这类知识可用于数据库知识的 归一化、查询优化，还可用于最小化决策树、搜索数据特例等 2 分类知识 数据子类的标识知识。子类可由某一现有属性确定，也可由 附加的知识领域知识来定义，KDD系统基于分类知识的发现任务 促进了交互式新型聚类算法的发展，即处理器计算机能力和用户 知识及可视化工具的有机集成。,KDD知识发现抽取知识的类型和表示,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,3 描述性知识 关于类别特征的概括性知识。主要包括两类知识：特征描述 知识和区分性知识。特征描述性知识是指本类数据所共有的；

24、区 分性知识是指本类区别于其他类的特征 4 偏差性知识 关于类别差异的描述。包括：标准类的特例，各类边缘外的 孤立点，时序关系上的单属性值和集合取值的不同，实际观测值 与系统预测值间的显著差别等。,KDD知识发现抽取知识的类型和表示,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,KDD的主要任务,KDD的核心部分是数据模式的抽取，即通过数据挖 掘完成各种模式的抽取。其主要的任务是： 分类知识发现、数据总结、数据聚类、 关联规则发现、序列模式发现、 依赖关系模型发现、异常发现和趋势预测等,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,1 分类知识发现 根据样本数据寻找相应的分类规

25、则。然后根据获得的规则来 确定某一非样本个体或对象是否属于某一特定的组或者类。在这 种分类知识发现中，样本数据中的个体或对象的类标识是已知的。 数据挖掘的任务就是从样本数据的属性中发现个体或对象分类的 一般规则，从而依据该规则对非样本数据对象进行分类有用。这 种分类规则一般表示为某种分类函数或者分类模型，简称分类器。,KDD的主要任务,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,2 聚类知识发现 数据聚类用于发现在数据库中未知的数据类。这种数据类划分的依据 是“物以类聚”，即按照个体或数据对象间的相似性，将研究对象划分为若 干类。由于数据挖掘之前，数据类划分的数量和类型均是未知的，因

26、此数 据挖掘后需要对数据挖掘结果进行合理分析与解释。 与分类知识发现不同的是，聚类任务没有已知的数据输入。即对于所 有元组（v1, v2, .,vn, C），给定属性vi，其类别C均是未知的。 在机器学习中，聚类被称为无监督或无指导学习，与之相反，分类被 称为有监督学习或有指导学习。因为在分类学习中，输入数据中有已知的 信息（各元组的类别属性C是已知的），算法从已知信息中抽取分类的规则，使有指导的。聚类算法中没有已知类别信息的输入，完全依靠算法对 元组相似度的衡量，自主学习自主确定类别，因此是无指导的 。,KDD的主要任务,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,KDD的主要任务

27、,3 关联规则知识发现 关联规则发现是在数据库中寻找数据对象间的关联模式。 例如“在购买个人电脑的顾客中，有90%的顾客购买了打印机” 就是一种关联模式。关联模式发现在研究和应用中的早期主要 用于零售业交易数据分析，以便进行物品更合理的摆放，最终 提高销售量。因此，关联规则发现有时也被称为“购物篮分析”。 关联规则发现是近年来研究比较多的数据挖掘方法，在数据 挖掘的各种方法中应用得也是最广的。目前研究发展趋势主要是： 从单一概念层次关联规则发现到多概念层次的关联规则发现，也 就是说在很多具体应用中，挖掘规则可以作用到数据库的不同层 面上。例如，在分析超市销售事务数据库过程中，若单单从数据 库中

28、的原始字段进行规则挖掘，则可能难以发现令人感兴趣的规 则，这时如果将一些抽象层次的概念也考虑进去，则有可能发现 新的更抽象的概念。二是提高算法的效率。,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,4 数据总结 数据总结是将数据库中的大量相关数据从较低层次抽象到较 高概念层次的过程。计数、求和、求平均值、求最大值等计算都 是数据总结的具体化。由于数据库中的数据所包含的信息往往是 最原始的，最基本的信息，而有时人们需要从较高的层次上浏览 数据，这就要求从不同的层次上对数据进行总结以满足分析需要。,KDD的主要任务,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,5 时序与序列模式知

29、识发现 在数据挖掘过程中，有时需要对时序数据库或序列数据库进 行数据挖掘，时序数据库中的数据是一些反映随时间变化的序列 值或事件组成的数据，这些值一般是等时间间隔采集的数据，例 如证券市场每天的波动和产品加工过程的质量变化等。序列数据 库也是包含序列数据的数据库，但它可能有时间标记，也可能没 有。序列模式挖掘主要有趋势分析，相似性搜索，与时间有关的 数据的序列模式挖掘和周期性模式的挖掘。,KDD的主要任务,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,6 离群点检测 数据集中的离群点的定义是，根据某些标准，与其他数据点 有显著差别的那些数据点。这些离群点主要有两种，一种是噪声 数据，一

30、种是由一定实际意义的反常数据。对于噪声数据，需要 采取一定的方法加以清除。对于反常数据，则需要进行专门的探 测和分析，以便从中发现更多的信息。 离群点检测在许多领域中有重要作用。如信用卡欺骗检测、 网络入侵检测、贷款审核、医药研究、天气预报、金融数据分析 市场数据分析和客户细分等。离群点检测目前的主要问题是如何 解决高维问题。,KDD的主要任务,产 品,Clementine,Darwin,Data mining Workstation,Data Engine,IBM Intelligent Miner,F-DBMS,IDIS,Information Harvester,Knowledge Se

31、eker,Neural Ware,Prison,Re Mind,技 术,供应商,规则归纳,神经网络、遗传算法等,神经网络,神经网络、模糊逻辑、信号处理,多种技术,分数维,规则发现,模糊专家系统,规则发现、决策树,神经网络,神经网络,基于实例的推理、归纳逻辑,Ingegral Solutions,Thinking Machines Corp.,HNC Software Inc.,MIT Gmbh,IBM Corp.,Cross/Z International Inc.,Informational Discovery Inc.,Informational Harvesting,Angoss Sof

32、tware Int1 Ltd.,Neural Ware Inc.,Nestor Inc.,Cognitive Systems,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,一般性工具,第1章 数据挖掘及其算法概览,数据库知识发现基本概念,数据源,数据源,。,数据,目标 数据,预处理 后 的数据,信息,知识,数据准备,数据挖掘,结果表达及解释,数据集成,数据选择,预处理,数据挖掘,表达及解释,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,Web数据挖掘,WEB数据挖掘,内容挖掘,结构挖掘,使用挖掘,分 类,聚 类,检 索,隐 链 接 分 析,层 次 链 接 分 析,个 性 化,协

33、 同 过 滤,从网页内容中抽取 有用的信息和知识,从表征WEB结构的超 链接中寻找有用的知识,从记录每位用户点击情 况的使用日志中挖掘用 户的访问模式,数据库知识发现基本概念,第1章 数据挖掘及其算法概览,Web数据挖掘,WEB挖掘过程和数据挖掘过程十分相似，区别通常只是数据 收集。在传统的数据挖掘中，数据经常是收集并存储在数据仓库 中，对Web挖掘来说，数据收集是一项艰巨的任务。尤其是在进 行WEB内容挖掘和结构挖掘方面，需要爬取大量的网页。,主要内容,数据库知识发现基本概念,数据挖掘算法概览,典型数据挖掘算法,数据集成概览,大型机构具有复杂的内部组织, 并且将不同模式的数据存储在不同地点和

34、不同操作型(事务处理)系统 数据源通常只存储当前数据, 而非历史数据 公司决策要求所有的机构数据具有统一视图, 包括历史数据 数据仓库是从多个数据源搜集来的, 以一个统一模式存储的, 位于单一场地的信息存储体(档案) 大大简化查询, 允许研究历史趋势 将决策支持查询负载从事务处理系统移出,第1章 数据挖掘及其算法概览,数据集成概览,数据仓库,第1章 数据挖掘及其算法概览,数据集成概览,数据集成应用案例-黑龙江地税数据集成系统,应用体系架构,第1章 数据挖掘及其算法概览,数据集成概览,数据集成 应用案例 黑龙江地税 数据集成系统,第1章 数据挖掘及其算法概览,数据集成概览,数据仓库体系结构,第1

35、章 数据挖掘及其算法概览,数据集成概览,数据仓库平台作用,登记,申报,征收,发票,票证,稽查,登记,数 据 仓 库 平 台,登记查询,发票查询,票证查询,统计报表,综合查询,主题分析,第1章 数据挖掘及其算法概览,数据集成概览,增量抽取,完全抽取,计 算,映 射,清 洗,业务要求,数据要求,抽 取,转 换,加 载,数据仓库,数据加载,异常情况处理及回退机制,作业控制管理,数据抽取、转换、加载,第1章 数据挖掘及其算法概览,数据集成概览,抽取转换加载（ETL）,两级ETL 数据源数据仓库 数据仓库数据集市,两级数据中转 转换中转区 加载中转区,映射 清洗,计算,第1章 数据挖掘及其算法概览,数据

36、集成概览,数据 仓库 结构,第1章 数据挖掘及其算法概览,数据集成概览,数据集成过程中需要考虑的问题？,数据的去规范化问题：第3范式是所有数据库系统遵循 的基本原则，在数据仓库和数据集成系统中存在什么 问题？ 不同数据源的数据如何进行转换，其采用的映射方法有 哪些？ 海量数据的存储和并行处理问题？ 后续章节学习。,主要内容,数据库知识发现基本概念,数据挖掘算法概览,典型数据挖掘算法,数据集成概览,第1章 数据挖掘及其算法概览,数据挖掘算法概览,数据挖掘经常被置于更广泛的数据库知识发现的大背景 下。数据库知识发现（KDD）术语来源于人工智能领域。KDD 的过程一般包括数据准备、数据挖掘、结果表达

37、与解释。更具 体说主要包括：目标数据选择、预处理数据、转换数据、通过 数据挖掘提取模式和关系、解释并评价发现的结构。 寻找数据集中的关系也就是说寻找精确、方便并且有价值 地总结了数据的某一特征的表示，这个过程包括步骤一般为： 决定要使用的表示的特征和结构； 决定如何量化和比较不同表示拟合数据的好坏（就是选择一 个评分函数）； 选择一个算法过程使评分函数最优； 决定使用何种数据管理原则高效地实现算法。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,数据集属性,数据集是从某个环境或过程中取得的一系列测量结果。一 般有一系列对象n，每个对象有p个测量结果。可以将其看作是 一个np的数据矩阵。 矩阵

38、中的n 行表示被测量的n个对象，根据不同的上下文可 以将这样的行称为个体(individual)、实体(entity)、实例(case)、 对象(object)、记录(record)。 矩阵中的另一维包含对每个对象所作的p种测量。一般假定 对每个个体使用同样的p个测量指标。可以将矩阵中的p个列称 为变量(variable)、特征(feature)、属性(attribute)、字段(field),第1章 数据挖掘及其算法概览,数据挖掘算法概览,观察上面的数据集，注意数据包含共同的类型，有连续型的， 有范畴型（categorical），也存在空值。在实际的数据集中存在空 值是普遍存在的。但是空值会

39、对结果产生不利的影响。更容易导致 错误的是测量结果中的噪声。,数据集属性,第1章 数据挖掘及其算法概览,数据挖掘算法概览,对于该类数据集，一个典型的任务是发现不同变量间的关系， 例如我们想看看从其它变量预测一个人的收入有多准确。,数据集属性,第1章 数据挖掘及其算法概览,数据挖掘算法概览,结构类型：模型和模式,一般可以从很多角度来对数据挖掘所探寻的不同表示进行 分类。一种方法是分析全局模型（ Model）和局部模式（Pattern、 Schema）的差异。 模型结构定义为对数据集的全局性总结。它是对整个测量空间 的每一个点作出描述。从几何角度考虑，数据矩阵中的行可以看作 是p维向量中的点。模型

40、是对该空间中的每一个点作出描述。如可 以把一个点分配到一个聚类或者预测出某个其它变量的值。 简单的模型如Y=aX + b，其中X、Y是变量，a、b是模型的参 数，也就是要在数据挖掘过程中确定的值。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,结构类型：模型和模式,与模型的全局性不同，模式结构仅对变量变化空间的一个 有限区域作出描述。一个例子是简单概率性结论： 若 Xx1, 则Yy1的概率为p1 。该结构由对变量X和Y的值 的约束组成。并以概率规则的形式将这两个变量联系到一起。当 然上述描述可以用条件概率描述p（Yy1|Xx1）=p1 。 模式描述的结构仅是与数据或一部份数据空间有关，或许仅

41、 有一部分记录具有某种特性。模式就是用来刻画这一部份数据的。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,结构类型：模型和模式,理解数据挖掘中模型和模式的概念 数据挖掘中模型是对一个数据集的高层次、全局性的描述。 它通过一个很大的样本透视总体。模型可以使描述性的-以方便 简洁的方式归纳数据，也可以是推理性的，允许对数据所在的数 据总体或者未来数据作出某些论断。典型的如线形回归模型、马 尔科夫模型等。 数据挖掘中模式是数据的局部特征。一个P维变量空间的局部 “结构”特性。如密度分布函数的最频值。或者回归曲线上的拐点 都是模式的例子。很多情况下，对模式的研究都是由意义的，它 描述了与数据一般行

42、为的背离现象。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,结构类型：模型和模式,理解数据挖掘中模型和模式的概念 以数据压缩来理解模型和模式。假定一个数据发送器T要传 送一幅图像I到接收器R。一般有两种策略：传送图像I的所有像素 的数据；传送图像的压缩版本。数据挖掘在很大程度上对应于后 一种情况。实现压缩的方法可能是把原始数据表示为一个模型， 或者也可以通过模式比标示出数据的异常特征。 当概括数据时很可能会导致某种数据失真。只要在允许的范围 内。例如对一个图像上的每个3232像素方块中用其均值来代替该 方块，结果会形成分辨率更低的图像。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,数据

43、挖掘与统计分析的比较,数据挖掘是揭示存在于数据里的模式及数据间的关系的学科。 它强调对大量的数据的处理以及数据与知识之间的关系。统计学是 一门关于数据资料的收集、整理、分析和推理的学科。共同的目标 -发现数据间隐藏的关系。,差别，只讨论一点，就是处理的数据规模和方法不同。传统的 统计一般是先有一个假设，然后收集数据，去验证假设的正确或错 误。数据挖掘则以处理海量数据、复杂数据为主。 提此问题的主要目的：统计是以一个的数学位基础的，为目前 数据挖掘研究尚缺乏严密的数学基础。要想在数据挖掘领域出成绩， 必须具备数学功底(特别针对搞数据库出生的)。有很多数据挖掘专 家来源于统计领域。（数据库领域、人

44、工智能领域、统计领域等）,第1章 数据挖掘及其算法概览,数据挖掘算法概览,多数情况下，数据挖掘算法可以从五个方面进行考虑。也 就是任务、模型、评分函数、搜索方法和数据管理技术。或者 称它们是算法组件。,关于算法组件,例如 关联规则的典型数据挖掘算法组件： 1 任务：描述变量之间的关联关系； 2 结构：用概率表示的“关联规则”模式； 3 评分函数：可信度与支持度的阈值； 4 搜索方式：系统搜索，带剪枝的广度优先； 5 数据管理技术：多重线性扫描。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-数据挖掘任务,该算法所针对的数据挖掘任务（如可视化、分类、聚类、 回归等）。通常不同的任

45、务需要不同的算法。 具体的任务类型见上节，包括： 分类知识发现； 聚类知识发现； 关联规则知识发现； 数据总结； 时序和序列模式知识发现； 离群点检测。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-模型和模式 用于拟合数据的模型或者模式的结构（函数形式） 例如线性回归模型，层次聚类模型等。这个结构定义了我们可以 近似或学习的边界。在该边界范围内，数据引导我们得到特定的 模型或者模式。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-模型和模式 模型是对现实世界中过程的抽象描述。模型是一种顶层的描述 概括并描述了一个庞大数据集的主要特征。 例如Y=aX+b是一个非

46、常简单的模型。在此事例中=a,b是 该模型的参数集。给定模型的现实或者结构，后续的工作就是通 过估计为其选择适当的参数，也就是说选择一个合适的评分函数 来衡量模型与数据的拟合程度。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-模型和模式,用于预测的模型结构 在预测模型中，一个变量被表达成其它变量的函数，这样可 以从给定的其它变量（称为解释或者预报变量）的值预测响应变 量的值。通常用Y表示预测模型的响应变量，用x1,xp表示p个 预报变量。以此建立一个预测模型，例如可以通过该方式预测前 例中纳税人职业和学历与申报收入的模型。一般可以将预测模型 表示为： = f(x1,xp, )

47、,其中是该模型的预测。 代表该模型 结构的参数。 如果Y是数量值变量，则从p维空间向量X到Y的映射被称为 回归（Regression）。 如果Y是范畴型变量，则称其为分类（Classification ） ，也 称为有指导分类学习（Supervised Classification ）,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-模型和模式,模型主要可以分为描述模型和预测模型。 描述模型以方便的形式呈现数据的主要特征。它实际上是对数 据的概括。使我们可以看到数据的最主要的特征，不会因为数 集合的绝对容量使这些特征模糊不清。 预测模型的目标与描述模型不同，其目的是使我们可以根据

48、观 察到的对象特征值来预测它的其它特征。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-评分函数,用于根据观察到的数据判断拟合后的模型或者模式的质量的 评分函数,评分函数就是当我们把参数和模型及模式拟合起来时要最大化 或最小化的函数。因此，评分函数在反映模型或者模式的不同 参数化过程中的实际效果方面非常重要。此外，评分函数对于 学习和泛化也是至关重要的。它可以仅仅基于拟合完满度（也 就是模型多好的描述了观察数据），也可以尽可能的捕捉泛化 性能（也就是模型多好地描述了我们没有见过的数据）。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-评分函数,评分函数对一个模型

49、或参数结构拟合给定数据集的效果进行 量化。理想情况下，最佳的评分函数应该能够精确地反映出特定 的预测模型的效果（也就是期望模型所带来的真正效益）。在实 际应用中，难以精确地确定预测模型的真正效果。所以，经常使 用简单的、通用的评分函数，例如最小平方法等。 如果没有评分函数，就无法说明一个模型是否比另一个更好。 或者到底如何为模型的参数选择一套好的参数值。通常使用的一 种方法是误差平方：,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-评分函数,其中，y(i)为被预测的n个目标值之一，1=i=n。(i)为作出的 预测值,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-

50、评分函数 评分函数的主要意义 使用评分函数的目的是用函数的形式来评价和度量模型在实 际应用方面的“有用程度”。 可以从三个角度来区分评分函数： 1）用于模型的评分函数与用于模式的评分函数的差别； 2）用于预测性结构的评分函数与用于描述性结构的评分 函数的差别； 3）用于具有固定复杂度的模型的评分函数同用于具有不 同复杂度的模型的评分函数的差别。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-搜索策略,对于参数或结构的搜索方法或优化方法,也就是使评分函数相对特定的模型或者模式最大化（最小化） 的计算过程或算法。这里的问题包括优化评分函数以及与搜索 相关的参数。如果模型结构是简单且

51、固定的，则搜索将在参数 空间中进行，目的是相对该固定结构形式优化评分函数。如果 模型结构包含一组不同的结构，则搜索既要针对这些结构又要 针对和这些结构相联系的参数空间。优化和搜索通常是所有数 据挖掘算法的核心部分。,第1章 数据挖掘及其算法概览,数据挖掘算法概览,关于算法组件-数据管理技术,用于存储、索引、检索数据的数据管理技术,许多统计和机器学习算法并不指定任何数据管理技术，实际上 是假定数据集足够小可以驻留在主存储器中。以至于相对于总 的实际开销，随机访问任何数据点的时间都是可以忽略的。但 当数据规模达到一定数量后，数据的物理位置和访问方式对于 算法的效率至关重要。,第1章 数据挖掘及其算

52、法概览,数据挖掘算法概览,很多情况下，数据挖掘的目的是要得到针对现有数据之外的 某些推理。 例如，在一个天体数据库中，可能需要得到这样一个结论： “类似该天体的所有对象的行为是这样的”。或许带一个概率限 制。 数据库提供了用于建立模型或者搜索模式的对象集合。但最 终的目的一般不是要描述这些数据，多数情况下，目标是描述数 据产生的一般过程以及描述可能由同样的过程产生的其它数据集,第1章 数据挖掘及其算法概览,数据挖掘算法概览,所以这些都意味着有必要避免模型或模式与现有的数据匹配 的太紧密。应该明白现有数据往往是可能数据的一部分。所以不 希望模型与现有数据的特异性太接近。就是说要避免过度拟合 （O

53、verfitting）给定的数据。而是要发现可以很好地泛化到潜在将 来的数据的模型和模式。在选用评分函数时要考虑该问题的存在,主要内容,数据库知识发现基本概念,数据挖掘算法概览,典型数据挖掘算法,数据集成概览,第1章 数据挖掘及其算法概览,典型数据挖掘算法,数据挖掘领域典型算法,*ID3, C4.5 （决策树） *The k-means algorithm（聚类） Support vector machines（支持向量机） *The Apriori algorithm（关联规则） The EM algorithm（迭代优化算法） PageRank（网页等级/重要性算法） AdaBoost（迭代分类算法） *kNN: