数据挖掘原理与算法（第三版）

很多学科都面临着一个普遍问题：如何存储、访问异常庞大的数据集，并用模型来描述和理解它们？这些问题使得人们对数据挖掘技术的兴趣不断增强。长期以来，很多相互独立的不同学科分别致力于数据挖掘的各个方面

数据挖掘

• 第一章 绪论
  • 1.1 数据挖掘技术的产生与发展
    • 1.1.1 数据挖掘产生的技术背景
      • (1) 数据库系统的发展
      • (2) 统计学的深入应用
        • 概率论和数理统计为我们从数据归纳到知识发现提供理论基础
      • (3) 人工智能技术的发展
    • 1.1.2 大数据时代数据挖掘技术需求分析
      • 大数据研究的发展划分为三个阶段: （1）大数据萌芽阶段; （2）大数据概念探索阶段; （3）大数据概念进一步深化，成为学术研究的焦点，成为许多应用 的支撑概念。
      • 大数据概念归纳起来有四个视角: 数据论;方法论;环境论;属性论.
  • 1.2 数据挖掘研究的发展趋势
    • 随着数据挖掘概念在学术界和工业界的影响越来越大，数据挖掘的研究向着 更深入和更实用技术方向发展。
  • 1.3 数据挖掘概念
    • 1.3.1 数据挖掘的技术含义
      • KDD与Data Mining的关系，有不同的看法： （1）KDD看成数据挖掘的一个特例： 数据挖掘可以在多种数据组织形式中挖掘知识，那么数据库中知识发现只是数据挖掘的一个方面。 （2）数据挖掘是KDD的一个关键步骤： KDD是一个更广义的范畴，包括数据清洗、数据集成、数据选择、数据转换 、数据挖掘、模式生成及评估等一系列步骤，KDD是一些基本功能构件的系统化同工作系统，而数据挖掘是这个系统中的一个关键的部分。 （3）KDD与Data Mining含义相同： 现今的许多场合，仍然不加区分地使用着。也有其他的说法： • KDD在人工智能界更流行，而Data Mining在数据库界使用更多。 • 在研究领域被称作KDD，在工程领域则称之为数据挖掘。 • 数据挖掘有广义和狭义之分，广义的观点，数据挖掘是从大型数据集中， 挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的完整过程。
    • 1.3.2 数据挖掘研究的理论基础
      • 模式发现（Pattern Discovery）架构、规则发现（Rule Discovery）架构：基于概率和统计理论、微观经济学观点（Microeconomic View）、基于数据压缩（Data Compression）理论、基于归纳数据库（Inductive Database）理论、可视化数据挖掘（Visual Data Mining）。
  • 1.4 数据挖掘技术的分类问题
    • 1.4.1 根据挖掘任务
      • 分类或预测模型发现 数据总结与聚类发现 关联规则发现 序列模式发现 相似模式发现 混沌模式发现 依赖关系或依赖模型发现 异常和趋势发现等
    • 1.4.2 根据挖掘对象
      • 关系数据库挖掘 面向对象数据库挖掘 空间数据库挖掘 时态数据库挖掘 文本数据源挖掘 多媒体数据库挖掘 异质数据库挖掘 遗产数据库挖掘 web数据挖掘等
    • 1.4.3 根据挖掘方法
      • 机器学习方法、统计方法 聚类分析方法 神经网络（Neural Network）方法 遗传算法（Genetic Algorithm）方法 数据库方法 近似推理和不确定性推理方法 基于证据理论和元模式的方法 现代数学分析方法 粗糙集（Rough Set）或模糊集方法 集成方法等
    • 1.4.4 根据知识类型
      • 挖掘广义型知识 挖掘差异型知识 挖掘关联型知识 挖掘预测型知识 挖掘偏离型（异常）知识 挖掘不确定性知识等
  • 1.5 数据挖掘常用的知识表示模式与方法
    • 1.5.1 广义知识挖掘
      • 广义知识是指描述类别特征的概括性知识。 数据挖掘的目的之一是根据数据的微观特性发现有普遍性的、更高层次概念的中观和宏观的知识； 因此，这类数据挖掘系统是对数据所蕴含的概念特征信息、汇总信息和比较信息等的概括、精炼和抽象的过程。 被挖掘出的广义知识可以结合可视化技术以直观的图表形式展示给用户，也可以作为其他应用的基础知识
    • 1.5.2 关联知识挖掘
      • 关联规则挖掘（Association Rule Mining）是关联知识发现的最常 用方法，最著名的就是Apriori及其改进算法。
    • 1.5.3 类知识挖掘
      • 类知识（Class）刻画了一类事物，这类事物具有某种意义上的共 同特征，并明显和不同类事物相区别。 采用两个基本的方法来挖掘类知识： 分类：决策树、贝叶斯分类、神经网络、遗传算法、类比学习。 聚类：基于划分、层次、密度、网络、模型的聚类方法。
    • 1.5.4 预测型知识挖掘
      • 预测性挖掘主要是对未来数据的概念分类和趋势输出。 预测型知识的挖掘可以结合经典的统计方法、神经网络和机器学习等技术来研究。
    • 1.5.5 特异型知识挖掘
      • 特异型知识（Exception）是源数据中所蕴涵的极端特例或明显 区别于其他数据的知识描述，它揭示了事物偏离常规的异常规律。
• 第二章 知识发现过程与应用结构
  • 2.1 知识发现的基本过程
    • 2.1.1 数据抽取与集成技术要点
      • （1）先弄清源数据的信息和结构。 （2）然后准确地界定所选取的数据源和抽取原则。 （3）最后设计存储新数据的结构和准确定义它与源数据的转换和 装载机制。这些结构和转换信息应该作为元数据 （Metadata）被存储起来。
    • 2.1.2 数据清洗与预处理技术要点
    • 2.1.3 数据的选择与整理技术要点
    • 2.1.4 数据挖掘技术要点
    • 2.1.5 模式评估技术要点
  • 2.2 数据库中的知识发现处理过程模型
    • 2.2.1 阶梯处理过程模型
      • 在对挖掘的知识进行评价后，根据结果可以决定是否重新开始某些处理，在处理的任意阶段都可以都可以返回重新处理。
    • 2.2.2 螺旋处理过程模型
      • 定义问题：数据挖掘人员与领域专家合作 抽取数据：根据问题的定义收集有关的数据 清洗数据：了解数据库中字段的含义及其与其他字段的 关系。 数据工程：对数据再加工 算法工程：选择合适的算法 运行挖掘算法：选择合适的知识发现方法 分析结果：优化包括对问题的再定义，数据进一步处理
    • 2.2.3 以用户为中心的处理模型
      • 从用户的角度对KDD处理过程进行了分析。应该更着重 于用户对知识发现的整个过程的支持，而不是仅仅限于在 数据挖掘的一个阶段上。KDD系统的真正困难在和用户 的交流上。因此，有了以用户为中心的处理模型
    • 2.2.4 联机KDD模型
      • OLAM结构示意图，使用户可以在数据立方体上进行多层次 的数据挖掘。
• 第三章 关联规则挖掘理论和算法
  • 3.1 基本概念与解决方法
    • 事务数据库： 一个事务数据库中的关联规则挖掘描述如下： 设I={ i1，i2，…，im }是一个项目集合，事务数据库D={ t1，t2，…，tn }是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。
    • 关联规则挖掘问题可以划分成两个子问题： 1. 发现频繁项目集:通过用户给定Minsupport ，寻找所有频繁 项目集。这些频繁项目集可能具有包含关系，一般我们只关心那 些不被其他频繁项目集所包含的最大频繁项目集的集合。 2．生成关联规则:通过用户给定Minconfidence ，在每个最大频 繁项目集中，寻找可信度不小于Minconfidence关联规则。
  • 3.2 经典的频繁项目集生成算法
    • 3.2.1项目集空间理论
      • 定理3-1. 如果项目集X是频繁项目集，那么它的所有非空子集都是频繁 项目集
      • 定理3-2. 如果项目集X是非频繁项目集，那么它的所有超集都是非频繁 项目集
    • 3.2.2关联规则的生成算法
      • 定理3-3 设项目集X，X1是X的一个子集，如果规则X->(l-X)不是强规 则，那么X1->(l-X1)一定不是强规则。
      • 定理3-4 设项目集X，X1是X的一个子集，如果规则Y->X是强规则，那 么Y->X1一定是强规则。
  • 3.3 Apriori算法的性能瓶颈问题
    • 1．多次扫描事务数据库，需要很大的I/O负载 对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验 证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至 少需要扫描事务数据库10遍。
    • 2．可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能 产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是 一种挑战。