数据挖掘基本概念.DOC

1、1.1 数据挖掘的定义 11234596781数据挖掘基本概念本章为全书的导论部分，首先阐述数据挖掘的本质，并讨论其在多个相关学科中的不同理解。接着介绍邦弗朗尼原理（Bonferronis principle） ，该原理实际上对数据挖掘的过度使用提出了警告。本章还概述了一些非常有用的思想，它们未必都属于数据挖掘的范畴，但是却有利于理解数据挖掘中的某些重要概念。这些思想包括度量词语重要性的TF.IDF权重、哈希函数及索引结构的性质、包含自然对数底e的恒等式等。最后，简要介绍了后续章节所要涉及的主题。1.1 数据挖掘的定义最广为接受的定义是，数据挖掘（data mining）是数据“模型 ”的发现

2、过程。而“模型” 却可以有多种含义。下面介绍在建模方面最重要的几个方向。1.1.1 统计建模最早使用“data mining”术语的人是统计学家。术语“data mining”或者“data dredging”最初是贬义词，意指试图抽取出数据本身不支持的信息的过程。1.2节给出了这种挖掘情况下可能犯的几类错误。当然，现在术语“data mining”的意义已经是正面的了。目前，统计学家认为数据挖掘就是统计模型（statistical model）的构建过程，而这个统计模型指的就是可见数据所遵从的总体分布。例 1.1 假定现有的数据是一系列数字。这种数据相对于常用的挖掘数据而言显得过于简单，但这

3、只是为了说明问题而采用的例子。统计学家可能会判定这些数字来自一个高斯分布（即正态分布） ，并利用公式来计算该分布最有可能的参数值。该高斯分布的均值和标准差能够完整地刻画整个分布，因而成为上述数据的一个模型。1.1.2 机器学习有些人将数据挖掘看成是机器学习的同义词。毫无疑问，一些数据挖掘方法中适当使用了第 1 章2 第 1 章 数据挖掘基本概念机器学习算法。机器学习的实践者将数据当成训练集来训练某类算法，比如贝叶斯网络、支持向量机、决策树、隐马尔可夫模型等。某些场景下上述的数据利用方式是合理的。机器学习擅长的典型场景是人们对数据中的寻找目标几乎一无所知。比如，我们并不清楚到底是影片的什么因素导

4、致某些观众喜欢或者厌恶该影片。因此，在Netflix竞赛要求设计一个算法来预测观众对影片的评分时，基于已有评分样本的机器学习算法获得了巨大成功。在9.4节中，我们将讨论此类算法的一个简单形式。另 一 方 面 ， 当 挖 掘 的 目 标 能 够 更 直 接 地 描 述 时 ， 机 器 学 习 方 法 并 不 成 功 。 一 个 有 趣 的 例子 是 ， WhizBang!实 验 室 1曾 试 图 使 用 机 器 学 习 方 法 在 Web上 定 位 人 们 的 简 历 。 但 是 不 管 使 用什 么 机 器 学 习 算 法 ， 最 后 的 效 果 都 比 不 过 人 工 设 计 的 直 接 通

5、 过 典 型 关 键 词 和 短 语 来 查 找 简 历的 算 法 。 由 于 看 过 或 者 写 过 简 历 的 人 都 对 简 历 包 含 哪 些 内 容 非 常 清 楚 ， Web页 面 是 否 包 含 简历 毫 无 秘 密 可 言 。 因此，使用机器学习方法相对于直接设计的简历发现算法而言并无任何优势。1.1.3 建模的计算方法近年来，计算机科学家已将数据挖掘看成一个算法问题。这种情况下，数据模型仅仅就是复杂查询的答案。例如，给定例1.1中的一系列数字，我们可以计算它们的均值和标准差。需要注意的是，这样计算出的参数可能并不是这组数据的最佳高斯分布拟合参数，尽管在数据集规模很大时两者非常

6、接近。数据建模有很多不同的方法。前面我们已经提到，数据可以通过其生成所可能遵从的统计过程构建来建模。而其他的大部分数据建模方法可以描述为下列两种做法之一：(1) 对数据进行简洁的近似汇总描述；(2) 从数据中抽取出最突出的特征来代替数据并将剩余内容忽略。在接下来的内容中，我们将探究上述两种做法。1.1.4 数据汇总一种最有趣的数据汇总形式是PageRank，它也是使谷歌成功的关键算法之一，我们将在第5章对它进行详细介绍。在这种形式的Web挖掘当中，Web的整个复杂结构可由每个页面所对应的一个数字归纳而成。这种数字就是网页的PageRank值，即一个Web结构上的随机游走者在任1 该初创实验室试

7、图使用机器学习方法来进行大规模数据挖掘，并且雇用了大批机器学习高手来实现这一点。遗憾的是，该实验室并没有能够生存下来。1.1 数据挖掘的定义 3123459678意给定时刻处于该页的概率（这是极其简化的一种说法） 。PageRank的一个非常好的特性就是它能够很好地反映网页的重要性，即典型用户在搜索时期望返回某个页面的程度。另一种重要的数据汇总形式是聚类，第7章将予以介绍。在聚类中，数据被看成是多维空间下的点，空间中相互邻近的点将被赋予相同的类别。这些类别本身也会被概括表示，比如通过类别质心及类别中的点到质心的平均距离来描述。这些类别的概括信息综合在一起形成了全体数据集合的数据汇总结果。例 1

8、.2 一个利用聚类来解决问题的著名实例发生在很久以前的伦敦，在整个问题的解决中并没有使用计算机 1。内科医生 John Snow在处理霍乱爆发时在城市地图上标出了病例的发生地点。图1-1 给出了该图的一个小片段，展示了病例的传播情况。图1-1 在伦敦市地图上标出的霍乱病例的传播情况示意图图中显示，病例聚集在某些交叉路口。这些路口的水井已经被污染，离这些水井最近的居民染上了疾病，而清洁的水井附近的居民则没有染病。如果没对这些数据进行聚类，霍乱的病因就难以揭开。1.1.5 特征抽取典型的基于特征的模型会从数据中寻找某个现象的最极端样例，并使用这些样例来表示数据。熟悉机器学习的一个分支贝叶斯网络（并

9、不在本书的讨论范围内）的读者应该会知道，1 参考http:/en.wikipedia.org/wiki/1854_Broad_Street_cholera_outbreak。4 第 1 章 数据挖掘基本概念在贝叶斯网络中，可以利用寻找对象间的最强统计依赖来表示所有统计关联，从而表示出对象之间的复杂关系。我们将要介绍大规模数据集下的一些重要的特征抽取类型，它们包括以下两种。(1) 频繁项集（frequent itemset） 该 模 型 适 用 于 多 个 小 规 模 项 集 组 成 的 数 据 ， 就 像 我 们 将 在第6章讨论的购物篮问题（market-basket problem）一样。

10、我们寻找那些在很多购物篮中同时出现的小规模项集，这些频繁项集就是我们要找的刻画数据的特征。这种挖掘的原始应用的的确确发生在真实的购物篮场景下：在商店或者超市收银台结账的时候确实会发现某些物品会被顾客同时购买，例如汉堡包和番茄酱，这些物品就组成所谓的项集。(2) 相似项（similar item） 很 多 时 候 ， 数 据 往 往 看 上 去 相 当 于 一 系 列 集 合 ， 我 们 的 目 标 是 寻找那些共同元素比例较高的集合对。一个例子是将在线商店（如Amazon）的顾客看成是其已购买的商品的集合。为了使Amazon能够向某顾客推荐他可能感兴趣的其他商品，Amazon 可以寻找与该顾客

11、相似的顾客群，并把他们当中大部分人购买过的商品也推荐给他。该过程称为协同过滤（collaborative filtering） 。如果顾客的兴趣都很单一，即他们只购买某一类的商品，那么将顾客聚类的方法可能会起作用。然而，由于顾客大都对许多不同的商品感兴趣，因此对每个顾客而言，寻找兴趣相似的那部分顾客并根据这些关联对数据进行表示的做法会更有用。我们将在第3章讨论相似性。1.2 数据挖掘的统计限制一类常见的数据挖掘问题涉及在大量数据中发现隐藏的异常事件。本节主要讨论这个问题，并介绍对数据挖掘的过度使用进行警告的邦弗朗尼原理。1.2.1 整体情报预警2002年，美国布什政府提出了一项针对所有可获得的

12、数据进行挖掘的计划，目的用于追踪恐怖活动，这些数据包括信用卡收据、酒店记录、旅行数据以及许多其他类型的情报。该计划被称为整体情报预警（Total Information Awareness，TIA ） 。 TIA计划无疑在隐私倡导者当中受到了极大关注，虽然最终它并没有被国会通过，但其实我们并不清楚这种计划是否已被冠以其他名称而得以真正实施。隐私和安全的折中困难姑且不在本书的讨论目的之列，然而，TIA或类似系统若想进一步发展，在其可行性和所依赖假设的现实性方面还需做更多的技术改进。很多人关心的是，如果浏览了这么多数据，并且想从这些数据当中发现疑似的恐怖行为，那么难道最终就不会找出很多无辜的行为？

13、乃至虽然非法但不是恐怖行为的行为？这些发现会1.2 数据挖掘的统计限制 5123459678导致警察的登门造访甚至更糟的情形。答案取决于所定义行为的严密程度。统计学家已经发现了该问题的各种伪装形式，并且提出了一个理论。该理论将在下一节介绍。1.2.2 邦弗朗尼原理假定人们有一定量的数据并期望从该数据中找到某个特定类型的事件。即使数据完全随机，也可以期望该类型事件会发生。随着数据规模的增长，这类事件出现的数目也随之上升。任何随机数据往往都会有一些不同寻常的特征，这些特征看上去虽然很重要，但是实际上并不重要，除此之外，别无他由，从这个意义上说，这些事件的出现纯属“ 臆造” 。统计学上有一个称为邦弗

14、朗尼校正（Bonferroni correction）的定理，该定理给出一个在统计上可行的方法来避免在搜索数据时出现的大部分“臆造”正响应。这里并不打算介绍定理的统计细节，只给出一个非正式的称为邦弗朗尼原理的版本，该原理可以帮助我们避免将随机出现看成真正出现。在数据随机性假设的基础上，可以计算所寻找事件出现次数的期望值。如果该结果显著高于你所希望找到的真正实例的数目，那么可以预期，寻找到的几乎任何事物都是臆造的，也就是说，它们是在统计上出现的假象，而不是你所寻找事件的凭证。上述观察现象是邦弗朗尼原理的非正式阐述。以寻找恐怖分子为例，可以预期在任何时候都几乎没有恐怖分子在活动。按照邦弗朗尼原理，

15、只需要寻找那些几乎不可能出现在随机数据中的罕见事件来发现恐怖分子即可。下一节将给出一个扩展的例子。1.2.3 邦弗朗尼原理的一个例子假设我们确信在某个地方有一群恶人，目标是把他们揪出来。再假定我们有理由相信，这些恶人会定期在某个宾馆聚会来商讨他们的作恶计划。为限定问题的规模，我们再给出如下假设：(1) 恶人数目可能有10亿；(2) 每个人每100天当中会有一天去宾馆；(3) 一个宾馆最多容纳100个人。因此，100 000个宾馆已足够容纳10亿人中的1% 在某个给定的日子入住宾馆；(4) 我们将对1000天的宾馆入住记录进行核查。为了在上述数据中发现恶人的踪迹，我们可以找出那些在两个不同日子入

16、住同一宾馆的人。但是假设并没有恶人，也就是说，给定某一天，对每个人来说，他们都是随机地确定是否去宾馆（概率为0.01） ，然后又是随机地从10 5个宾馆中选择一个。从上述数据中，我们能否推断出某两个人可能是恶人？6 第 1 章 数据挖掘基本概念接下来我们做个简单的近似计算。给定某天，任意两个人都决定去宾馆的概率为0.000 1，而他们入住同一宾馆的概率应该在0.000 1基础上除以10 5（宾馆的数量） 。因此，在给定某天的情况下，两个人同时入住同一宾馆的概率是10 9。而在任意给定的不同的两个日子，两人入住同一宾馆的概率就是10 9的平方，即10 18。需要指出的是，上述推理中只需要两人两次

17、中每次住的宾馆相同即可，并不需要两次都是同一家宾馆 1。基于上述计算，我们必须要考虑到底事件出现多少次才意味着作恶事件的发生。上例中，“事件”的含义是指 “两个人在两天中的每一天入住相同宾馆 ”。为简化数字运算，对于较大的n，大概等于n 2/2。下面我们都采用这个近似值。因此在10 9中的人员组对个数为2=51017，而在 1000天内任意两天的组合个数为 =5105。疑似作恶事件的期望数目910 102应该是上述两者的乘积再乘上“两个人在两天中的每一天入住相同宾馆 ”的概率，结果为5 1017 5 105 1018 = 250 000也就是说，大概有25万对人员看上去像恶人，即使他们根本不是

18、。现在假定实际上只有10对人员是真正的恶人。警察局需要调查25万对人员来寻找他们。除了会侵犯近50万无辜人们的生活外，所需的工作量非常大，以至于上述做法几乎是不可行的。1.2.4 习题习题1.2.1 基于1.2.3节的信息，如果对数据做如下改变（其他数据保持不变） ，那么可能的嫌疑人员对的数目是多少？(1) 观察的天数从1000天增加到2000天。(2) 要观察的总人员数目上升到20亿（因此需要200 000个宾馆）。(3) 只有在不同的三天内的同一时刻两个人入住相同宾馆的情况下，才进行嫌疑报告。! 习 题 1.2.2 假 定 有 1亿 人 的 超 市 购 物 记 录 ， 每 个 人 每 年

19、都 会 去 超 市 100次 ， 每次都会买超市中1000种商品中的10种。我们相信，两个恐怖分子会在一年中的某个时段购买相同的10种商品（比如制造炸弹的材料） 。如果对购买相同商品集合的人员对进行搜索，那么能否期望我们发现的任何这类人员都是真正的恐怖分子？ 21如第一天大家都住A，第二天都住B 。 但A可以不等于B 。译者注2 也 就 是 说 ， 假 定 恐 怖 分 子 一 定 会 在 一 年 中 的 某 个 时 段 购 买 相 同 的 10件 商 品 。 这 里 不 考 虑 恐 怖 分 子 是 否 必 须 要 这 样 做 。1.3 相关知识 71234596781.3 相关知识本节中，我们

20、将简要介绍一些有用的主题，读者可能在其他课程的研究中接触过或者根本没有接触过这些主题，但是它们却对于数据挖掘的研究相当有益。这些主题包括：(1) 用于度量词语重要性的TF.IDF 指标；(2) 哈希函数及其使用；(3) 二级存储器（磁盘）及其对算法运行时间的影响；(4) 自然对数的底e 及包含它的一系列恒等式；(5) 幂定律（power law） 。1.3.1 词语在文档中的重要性数据挖掘的不少应用都会涉及根据主题对文档（词语的序列）进行分类的问题。一般来说，文档的主题主要通过找到一些特定的能够体现主题的词语来刻画。例如，有关棒球（baseball）的文章当中往往会出现类似“ball ”（球）

21、 、 “bat”（球棒） 、 “pitch”（投球）以及“run” （跑垒）之类的词语。一旦将文档分到确实是关于棒球的主题类中，不难发现上述词语在文档当中的出现往往十分频繁。但是，在没有分类之前，并不能确定这些词语就刻画了棒球的主题类别。因此，分类的第一步往往是考察文档并从中找出重要的词语。为达到这个目的，我们首先猜测文档中最频繁出现的词语应该最重要。但是，这个直觉和实际情况恰恰相反。出现最频繁的大部分词语肯定都是那些类似于“the”或者“and”的常见词，这些词通常都用于辅助表达但本身不携带任何含义。实际上，英语中几百个最常见的词（称为停用词）往往都在文档分类之前就被去掉。事实上，描述主题的

22、词语往往都相对罕见。但是，并非所有罕见词在做指示词时都同等重要。一方面，某些在整个文档集合中极少出现的词语（如“notwithstanding”或“ albeit”）并不能提供多少有用的信息。另一方面，某个如“chukker”（马球比赛中的一局）的词虽然和上述词语一样罕见，但是该词语却能提示我们文档明显和马球运动有关。上述两类罕见词的区别与它们是否在部分文档中反复出现有关。也就是说，类似“albeit” 的词语在文档中出现并不会增加它多次出现的可能性。但是，如果一篇文章有一次提到“chukker”，那么文档可能会提到“first chukker”（第一局）发生什么，接着提到“second ch

23、ukker”（第二局）发生什么，以此类推。也就是说，如果这类词在文档中出现那么它们很可能会反复出现。这种度量给定词语在少数文档中反复出现程度的形式化指标称为TF.IDF（TF指词项频率，是Term Frequency的缩写，IDF指逆文档频率，是Inverse Document Frequency的缩写，TF.IDF表8 第 1 章 数据挖掘基本概念示词项频率乘以逆文档频率） 。它通常采用如下方式计算。假定文档集中有N篇文档，f ij为词项i在文档j中出现的频率（即次数） ，于是，词项i在文档j中的词项频率 TFij定义为maxijijkfTF也就是词项i在文档j中的词项频率f ij归一化结果

24、，其中归一化通过 fij除以同一文档中出现最多的词项（可能不考虑停用词的频率）的频率来计算。因此，文档j中出现频率最大的词项的TF值为1，而其他词项的TF值都是分数 1。假定词项i在文档集的n i篇文档中出现，那么词项i的IDF定义如下： 2logiiNIDFn于是，词项i在文档j中的得分被定义为TF ijIDFi，具有最高TF.IDF得分的那些词项通常都是刻画文档主题的最佳词项。例1.3 假 定 文 档 集 中 有 220 = 1 048 576 篇 文 档 ， 假 定 词 语 w在 其 中 的 210 = 1024篇 文 档 中 出 现 ，那么IDF w = log2(220/210) =

25、 log2(210) = 10。考虑一篇文档j，w在该文档中出现20次，这也是文档当中出现最多的词(停用词可能已经去掉)。那么TF wj =1，于是w 在文档j 中的TF.IDF 得分为10。假定在文档k中，词语w出现一次，而该文档中任一词语最多出现20次。于是有TF wk = 1/20，w 在文档 k中的TF.IDF 得分为1/2。1.3.2 哈希函数读者或许听说过哈希表，也可能在Java类或类似软件包当中使用过哈希表。实现哈希表的哈希函数在多个数据挖掘算法中都是核心要素，不过在这些数据挖掘算法中，哈希表却和一般常见的形式有所不同。下面我们将介绍哈希函数的基本知识。首先，哈希函数h的输入是一

26、个哈希键值（hash-key） ，输出是一个桶编号（bucket number） 。假定桶的个数为整数B，则桶编号通常是0到B-1之间的整数。哈希键值可以是任何类型的数据。哈希函数的一个直观性质是它们将哈希键值“随机化”（randomize） 。更精确地说，如果哈希键值随机地从某个合理的可能的哈希键分布中抽样而成，那么函数h将会把数目近似相等的哈希键值分配到每个桶中。这一点有可能做不到，比如当所有可能的哈希键值数目少于桶数目B时就是如此。当然我们可以认为该总体不具有“合理”分布。然而，可能存在更细微的原因导致哈希函数的结果不能近似均匀地分布。1 因为都是两个正整数词频相除。译者注1.3 相关知

27、识 9123459678例 1.4 假设所有的哈希键都是正整数。一个普遍且简单的哈希函数是h(x) = x mod B，即x除以B之后的余数。如果哈希键的总体是所有的正整数，那么上述哈希函数产生的结果会非常均匀，即1/B 的整数将被分到每个桶中。但是，如果哈希键只能是偶数值，并且如果B=10，那么h(x)的结果只能是0、2、4、6和 8，也就是说，此时哈希函数的行为明显不够随机。另一方面，如果选择B =11，那么会有1/11的偶数会分到每个桶中，这时候哈希函数的效果又会很好。 对 上 例 进 行 一 般 化 ， 当 哈 希 键 都 是 整 数 时 ， 如 果 选 用 一 个 与 所 有 可 能

28、 的 哈 希 键 （ 或 者 大 部分 ） 都 具 有 公 因 子 的 B时 ， 将 会 导 致 分 配 到 桶 中 的 结 果 不 随 机 。 因 此 ， 通 常 都 首 选 将 B取 为 素 数 。尽 管 这 种 情 况 下 我 们 还 必 须 要 考 虑 所 有 的 哈 希 键 以 B为 因 子 的 可 能 性 ， 但 是 上 述 选 择 方 法 减 少了 非 随 机 行 为 的 可 能 性 。 当 然 ， 还 有 很 多 其 他 类 型 的 哈 希 函 数 并 不 基 于 取 模 运 算 。 这 里 也 并 不打 算 概 括 所 有 可 能 的 哈 希 函 数 类 型 ， 但 是 在

29、最 后 一 节 的 参 考 文 献 讨 论 当 中 也 提 到 了 一 些 相 关 的信 息 来 源 。如果哈希键不是整数，要如何处理呢？在某种意义上说，所有数据类型的值都由比特位组成，而比特位序列常常可以解释成整数。但是，有一些简单的规则可以将通用的类型转化成整数。例如，如果哈希键是字符串，那么可以将每个字符转换成其对应的ASCII码或Unicode码，每个码可以解释为一个小整数。在除以B之前可以将这些整数求和，只要B小于字符串总体中各字节字符码的典型求和结果，那么最后对B取模的结果相对还是比较均匀的。如果B更大，那么可以将字符串拆分成多个组，每个组包含多个字符，一组字符可以连在一起看成一个

30、整数。然后，将每组字符对应的整数求和之后对B取模。比如，如果B在10亿上下或者说2 30，那么每四个字符合成一组对应一个32位的整数，多个32位整数的求和结果将会相当均匀地分配到10亿个桶中去。 对于更复杂的数据类型，可以对上述字符串转化为整数的思路进行扩展来递归式处理。 对于记录型数据，记录中每个字段都有自己的类型，那么可以采用适合该类型的算法将每个字段递归地转换成整数，然后将所有字段转换出的整数求和，最后对B取模来将整数分配到不同桶中去。 对于数组型、集合型或包（bag）型 1数据，数据中的每一个元素都是相同类型。可以先将每个元素的值转换成整数，然后求和并对B取模。1.3.3 索引给定某种

31、对象的一个或多个元素值，索引是一种能够支持对象高效查找的数据结构。最常1 一种允许集合中元素重复的数据类型。译者注10 第 1 章 数据挖掘基本概念见的一种情况是对象都是记录，而索引按照记录中的某个字段来建立。给定该字段的值v，基于索引能够快速返回该字段值等于v的所有记录。例如，假定有一个由一系列三元组组成的档案记录表以及基于电话号码字段建立的索引。当给定一个电话号码时，基于索引就能快速找到包含该号码的一条或者多条记录。实现索引的方法有很多，这里并不打算给出全面的介绍。参考文献部分给出了扩展阅读的建议。但是，哈希表是一种简单的索引构建方法。哈希函数的输入键是用于建立索引的一个或者多个字段。对于

32、某条记录来说，哈希函数会基于其中哈希键的值进行计算，然后将整条记录分配到某个桶中，而桶的号码取决于哈希函数的结果。举例来说，这里的桶可以是内存或磁盘块中的一个记录表 1。于是，给定一个哈希键值，我们可以先求哈希函数的值，然后根据该值寻找相应的桶，最后只须在该桶中寻找包含给定哈希键值的记录即可。如果我们选取的桶数目B和档案中所有记录的数目大体相当，那么分配到每个桶的记录数目都会较小，这样在桶内部的搜索速度就会很快。例 1.5 图1-2给出了包含姓名（name） 、地址（address）和电话号码（phone ）字段的记录的内存索引结构的大概样子。这里，索引基于电话号码字段构建，而桶采用链表结构。图中展示电话号码800-555-1212所对应的哈希到桶号码为17。对于桶头(bucket header)构成的数组，其第i个元素实际上是第i个桶对应链表的头指针。图中展开了链表中的一个元素，它包含姓名、地址和电话号码字段的一条记录。事实上，该元素对应记录包含的电话号码正好是800-555-1212，但是该桶中的其他记录可能包含也可能不包含这个电话号码，我们只知道这些记录中的电话号码经过哈希变换之后结果都是17。1 由于多条记录可能会哈希哈希到同一个桶中，因此每个桶通常由多条记录所组成的表构成。译者注