1.1 数据挖掘的定义

本质概念:用最强大的硬件、最强大的编程系统和最高效的算法’来解决科学、商业、医疗健康、政府、人文以及众多人类努力探索的其他领域中的问题。

1.1.1 建模

对很多人而言’数据挖掘是从数据构建模型的过程’而该过程通常利用机器学习来实现。但是更一般地来说数据挖掘的目标是算法。当然，在很多重要的应用中，建模是难点所在。—旦模型建好,那么使用该模型的算法就直截了当了。

1.1.2 统计建模

目前,统计学家认为数据挖掘就是统计模型（statisticalmodel）的构建过程’而此处统计模型指的就是可见数据所遵从的总体分布。

1.1.3 机器学习

有些人将数据挖掘看作机器学习的同义词。毫无疑问’一些数据挖掘方法中适当使用了机器学习算法。机器学习的实践者将数据当成训练集来训练某类算法，比如贝叶斯网络、支持向量机、决策树和隐马尔可夫模型等。
在某些场景下，上述数据利用方式是合理的。机器学习适用的典型场景是人们对要在数据中寻找的目标几乎—无所知。比如“我们并不清楚到底是什么因素导致某些观众喜欢或者厌恶一部影片”。因此’在Netflix竞赛要求预测观众对影片的评分时,基于已有评分样本的机器学习算法获得了巨大成功。
不过，当能够更直接地描述挖掘的目标时，机器学习方法并不成功。
有些机器学习方法还存在另外一个问题,就是它们产生的模型虽然效果很好，但是可解释性差。

1.1.4 建模的计算方法

与统计方法不同，计算机科学家倾向于将数据挖掘看成—个算法问题。这种情况下，数据模型仅仅是复杂查询的答案。
数据建模有很多不同的方法。前面已经提到可以构造一个随机过程，并通过这个过程生成数据。其他的大部分数据建模方法可以被描述为下列两种做法之一:
（1）对数据进行简明扼要的概括;
（2）从数据中抽取出最突出的特征来代替数据并忽略剩余内容。

1.1.5 数据概括

PageRank是最有趣的数据概括形式之一。
另一种重要的数据概括形式是聚类。在聚类中，数据被看作多维空间
下的点’而且空间中相互邻近的点将被赋予相同的类别。这些类别本身也会被概括表示，比如通过类别质心以及类别中各个点到质心的平均距离来描述。这些类别的概括信息综合在—起形成了整个数据集合的数据概括结果。

1.1.6 特征抽取

下面介绍大规模数据集下的两种重要的特征抽取类型。

1. 频繁项集： 该模型适用于多个小规模项集组成的数据
2. 相似项： 很多时候，数据看上去相当于—系列集合，而我们的目标是寻找那些共同元素占比较高的集合对。

1.2 数据挖掘的统计限制

一类常见的数据挖掘问题涉及在大量数据中发现隐藏的异常事件。

1.2.1 整体情报预警

现在，数据集成（information integration）往往是解决重要问题的关键步骤，它能将来自不同数据源的相关数据组合起来，以便获得无法从任何单一数据源中得到的信息。
本节期望集中关注一个特殊的技术问题:如果在数据中同时寻找过多的东西，那么可能会有看似有趣的发现，但是这实际上只是简单的统计生成物，并没有任何重要意义。

1.2.2 邦弗朗尼原理

假定人们有—定量的数据并从中寻找某个特定类型的事件.即使数据完全随机，也可以期望该类型的事件会发生。随着数据规模的增长，这类事件的出现次数也随之上升。任何随机数据都会有—些不同寻常的特征’这些特征虽然看上去很重要，但是实际上并不重要。从这个意义上说，上述事件的多次出现纯属“假象”。邦弗朗尼原理可以用于避免搜索数据时出现的大部分虚假结果。
邦弗朗尼原理： 在数据随机性假设的基础上，可以计算所寻找事件出现次数的期望值。如果该结果显著高于你所希望找到的真正实例的数目，那么可以预期，寻找到的任何事物几乎都是虚假的。也就是说’它们是在统计上出现的假象’而不是你所寻找事件的证据。上述观察结果是邦弗朗尼原理的非正式阐述°

1.2.3 邦弗朗尼原理的一个例子

1.3 相关知识

本节将简要介绍—些有用的主题，你可能在其他课程或研究中接触过它们’也可能根本没有听说过。这些对于数据挖掘的研究相当有益，包括:
（1）用于度量词语重要性的TPIDF指标;
（2）哈希函数及其使用;
（3）二级存储器（磁盘）及其对算法运行时间的影响;
（4）自然对数的底e及包含它的一系列恒等式;
（5）幂定律.

1.3.1 TF.IDF指标

TF.IDF指标用于度量给定词语在少数文档中反复出现程度（TF指吃词项频率，IDF指逆文档频率）。
假定文档集中有N篇文档，f_ij为词项i在文档j中出现频率（即次数），于是，TF_ij 定义为：

即词项i在文档j中出现频率的归一化结果。
假定词项i在文档集的n_i篇文档中出现，那么词项i的IDF定义如下：

于是，词项i在文档j中的得分被定义为TF_ij×IDF_i，具有最高TFIDF得分的那些词项通常是刻画文档主题的最佳词项。

1.3.2 哈希函数

首先’哈希函数h的输人是—个哈希键（hash-key），输出是—个桶编号（bucket number）。假定桶的个数为整数B，则桶编号通常是0和B-1之间的整数。哈希键可以是任何类型的数据。哈希函数的—个直观性质是将哈希键**“随机化”**（randomize）。

1.3.3 索引

给定某种对象的一个或多个元素值，索引是一种支持高效查找对象的数据结构。最常见的—种情况是对象都是记录，而索引是基于记录中的某个字段来建立的。给定该字段的值γ，根据索引能够快速返回该字段值等于γ的所有记录。

1.3.4 二级存储器

当处理大规模数据时，数据—开始在磁盘还是内存上会导致计算的时间开销相差很大。
磁盘呈块（block）结构，每个块是操作系统用于在内存和磁盘之间传输数据的最小单元。访问（将磁头移到块所在的磁道并等待磁盘块在该磁头下旋转经过）和读取一个磁盘块需要大概10毫秒的时间。相对于从内存中读取—个字的时间，磁盘的读取延迟至少要慢5个数量级（即存在因子10⁵）。因此，如果只需要访问若干字节’那么将数据放在内存中将具压倒性优势。实际上，假如我们要简单地处理—个磁盘块中的每个字节，比如将块看成哈希表中的桶，并在桶的所有记录当中寻找某个特定的哈希键，那么将块从磁盘移到内存的时间会大大多于计算的时间。