1.3 十大数据挖掘算法简介

本节给出对数据挖掘的十大算法的简要介绍。有些比较常用的算法可能会在不同的应用案例中被多次使用到。

数据挖掘十大算法源自于2016年一篇发表在《IEEE International Conference on Data Mining （ICDM）》的论文，并收录在2007年12月的《Journal of Knowledge and Information Systems》杂志上。

ICDM 2006的会议邀请ACM SIGKDD发明奖得主和IEEE ICDM研究贡献奖得主作为数据挖掘十大算法提名委员会专家。十大数据挖掘算法首先经过委员会专家的提名，然后再查阅其引用次数（要求至少50 次以上），选出18个算法。最后再邀请ACM SIGKDD 2006、IEEE ICDM 2006、SIAM DM 2006 3个国际会议的程序委员会委员投票选出前十大数据挖掘算法。

这十大算法见表1-2。

这里，作者只简述这十大算法的思想。关于这十大算法的详细介绍，读者可以在数据挖掘和机器学习的教科书上查阅。另外，《Machine Learning in Action》这本书也针对这十大算法的实现做了详细的代码讲解。十大数据挖掘算法里，k近邻（k-Nearest Neighbors）、C4.5、支持向量机（Support Vector Machine）、AdaBoost、CART、朴素贝叶斯用于解决分类任务。k-均值（k-means）是最常见的聚类算法。Apriori 是关联规则挖掘算法。Expectation Maximization 是一种估计概率模型参数的算法。PageRank是一种链接分析的算法，主要用于图数据里，对节点重要性进行排名。

k近邻算法的思想是通过找事物属性上的相似性，去揣测类别上的相同，简单来说就是类比法。k 近邻算法从训练数据集里找出和待分类的数据对象最相近的 k个对象。这k个对象中出现次数最多的那个类别，就可以被当作这个待分类的数据对象的类别。例如，我们对一个植物样本进行分类的时候，通过对比这个样本和实验室的标本之间的各个特征，例如长度、直径、颜色等属性，然后找到最相似的几个标本。这几个标本的类别就应该是这个植物样本的类别。如果这几个标本的类别也不同，我们取里面出现次数最多的那个类别。

通过调节k值的大小，能够改变分类结果，进而改变分类准确率。在图1-3所示的例子中，当设置k值为3时，该点分类结果为三角形（邻居分布：2个三角形， 1个正方形）；当设置k值为5时，该点分类结果为正方形（邻居分布：3个正方形， 2个三角形）。

由于在计算某待分样本的过程中，需要计算该样本与所有样本点的距离，进而找到最近邻居，k近邻算法被称作基于条目（Instance-Based）的分类算法。因此，区别于很多训练好模型便可以丢弃训练数据的方法，k近邻算法需要保留训练数据。

C4.5和CART （Classification and Regression Tree） 都是基于决策树（Decision Tree）的分类算法。决策树本质上是一个对训练数据进行划分的数据结构。决策树中每个节点代表一个关于属性的问题。对这个问题的不同回答决定了一个数据对象被分到树的不同分支。最终所有的训练数据都会被塞入某个叶子节点。这和常见的二分搜索树、B+树等数据结构没有本质的区别。与其他树的数据结构用途不同的是，决策树最终的目的是要回答一个数据对象的类别。如果一个未知类别的数据对象被决策树划分到某个叶子节点，这个叶子节点内的数据类别就可以被当作这个数据的类别标记。如果叶子节点的数据有几个不同的类别，与k近邻算法一样，我们取出现次数最多的那个类别。

在图1-4所示的例子中，椭圆形表示属性节点，用于划分数据，矩形表示叶节点，用于指定分类结果。假设一条训练数据的属性取值为{天气=凉爽，刮风=是}，那么按照给定的决策树，该条数据的分类结果应为“不打球”。

为了尽可能保持回答的一致性，我们希望每个叶子节点内的数据类别尽量保持一致。直观来说，这样决策树在回答一个数据类别的时候，就更加有把握。因此，我们希望决策树每个叶子节点的类别分布越纯越好（或越单调越好）。当一个节点内所有数据的类别都一致的时候，纯度最高。当一个节点所有数据的类别都两两不相同的时候，纯度最低。此时，类别分布最混乱，简单理解就是类别分布过于平均，不倾向任何一个类别。可以说，此时的类别分布最混乱、最不纯。

纯度可以用不同的指标来测量，常见的纯度指标包括熵（Entropy）和基尼指数（Gini Index）。一个节点的纯度越高，熵和基尼指数就越小。将数据集按照某属性取值划分后，得到的新的纯度估计叫作条件熵（Conditional Entropy），因此纯度的提升可以表示为划分后条件熵与划分前熵的差异，这个差异值叫作信息增益（Information Gain）。在决策树构建中，选取使当前信息增益最大的属性进行分支构建。当下一步划分引发的信息增益很小，或者已经没有属性再供划分之时，将节点转换为叶节点，并将该节点内数量最多的类别标记作为该节点的类别标记。通过这样递归地构建分支（即叶节点）生成的树叫作ID3决策树。但是，由于ID3算法无法处理连续（数值）属性，并没有入选十大挖掘算法。

但是，C4.5（或CART）算法，均与ID3算法有着相似的递归树构建理念。除能处理连续属性和样本缺省值外，C4.5算法利用信息增益比（Information Gain Ratio）评估分支属性，在信息增益的基础上，除以属性本身取值的分散性（用熵表示），用以修正在使用信息增益的过程中选择结果偏向取值较多的属性的偏差。另外，在C4.5中引入了剪枝（Pruning）操作，通过停止树生长，或去除某个子树的方式，减少决策过程划分过细引起的过拟合（Overfitting）问题。

对比而言，CART将基尼指数与条件基尼指数的差异，作为评估属性重要性依据。同时，CART能够处理回归任务，因此，在算法用途上更加广泛。

Naïve Bayes是通过贝叶斯定理（Bayesian Theorem）来进行分类的。朴素贝叶斯将数据的属性和类别看作两个随机变量（X和Y），然后问题转换成为给定属性X，找出哪个Y出现的概率最大，即贝叶斯定理中的后验概率P（Y|X）。

根据贝叶斯定理，后验概率可以由先验概率和条件概率计算出来。而先验概率和条件概率可以由训练数据统计而得。因此分类的过程被转换为一系列计算后验概率P（Y1|X）,…,P（Yc|X）的过程，后验概率最大对应的类别标记即分类结果。

朴素贝叶斯之所以叫朴素，是因为这个算法假设对于给定的数据对象的类别Y来说，不同属性的出现是互相独立的（Conditionally Independent），这种朴素假设大大简化了运算。假定X有f个属性，那么对于类别标记Y而言，在独立性假设下， P(Y|X)的取值可用式（1-2）进行评估。因为无须考虑各个属性X1,…,Xf之间的相关性，因此运算被大大简化。

支持向量机是近年来使用得最广的分类算法，因为它在高维数据，例如图像和文本上的表现都好过其他很多算法。与Naïve Bayes的不同之处在于，它不关心这个数据是如何产生的，它只关心如何区分这个数据的类别。所以也称这种分类算法是判别式（Discriminative）的。在 SVM 算法内，任何一个数据都被表示成一个向量，也就是高维空间中的一个点，每个属性代表一个维度。SVM和大多数分类算法一样，假设一堆数据的类别相同，那么它们的其他属性值也应该相近。因此，在高维空间上，不同的类别数据应该处于不同的空间区域。SVM的训练算法就是找出区分这几个区域的空间分界面。能找到的分界面可能有很多个，SVM算法中选择的是两个区域之间最靠近正中间的那个分界面，或者说离几个区域都最远的那个分界面（Maximum-Margin Hyperplane）。因此，相比逻辑斯特回归（Logistic Regression）而言，SVM中的分界面只有一个，即最大间隔分界面。

因为现实数据可能是有噪声的。如果有了噪声，一个数据可能会在观测空间位置的周围区域都出现。离几个区域最远的那个分界面能够尽量保证有噪声的数据点不至于从一个区域跳到另外一个区域去。这个最佳的分界面寻找问题在 SVM 中被表示成一个有约束的优化问题（Constrained Optimization）。通过优化算法里的拉格朗日法可以求得最优的分界面。

如图1-5所示，SVM通过求解带约束优化问题，寻找深、浅两组数据分布之间的最大间隔，这个最大间隔由间隔边界（图1-5中虚线表示）上的数据点来支持，这些点是原数据样本中的特殊点。由于这些点支持了间隔边界，又用向量表示，因此这些点被称为支持向量（Support Vector）。通常，支持向量在样本中所占的比例很小。

在硬间隔（Hard Margin）支持向量机中，不容忍数据点分布在分界面（图1-5中实线表示）和间隔边界之间。而在一些特殊情况下，例如深、浅数据分布有重叠，样本数据近似线性可分（Approximately Linear Separable）时，为保证模型的泛化性（Generalization），需要容忍分界面和间隔边界中的某些点，如图1-6所示，这些点要么是错分点，要么就是划分置信度（Confidence）不够。这种情况下的SVM叫作软间隔（Soft Margin）支持向量机。

另外一种情况是，数据根本就线性不可分（Non-Linear Separable），SVM对这种情况引入核技巧（Kernel Trick）。核技巧的基本思想是通过升维的方式将原本线性不可分的数据转化为线性可分数据，再类似地求解最大分界面。在图1-7所示的例子中，原本线性不可分的数据，在映射到核空间后，能够很好地进行划分。

AdaBoost（Adaptive Boosting）是一种集成学习算法。其核心思想是在同一个训练集上，通过考察上一次实验中每个样本的分类是否正确以及总体分类的准确率，自适应地调整每个样本的权值，迭代地生成若干个不同的分类器（弱分类器），最终将这些分类器组合起来，提升为一个强分类器。

AdaBoost的基本过程如下：

步骤1 对训练数据每个样本初始化一个权重（初始权重均相等），构成权重向量；

步骤2 利用弱分类器进行训练，并计算加权错误率；

步骤3 依据求得的错误率调整样本权重，同时，依据求得的错误率调整分类器系数；

步骤4 不断迭代步骤2和步骤3，直到指定迭代次数或错误率为0时，停止迭代。

AdaBoost并不是指集成不同的分类算法，而是对不同训练数据集创造分类器。AdaBoost为了减少分错的情况，有意识专门针对分错的数据进行训练。这种思想就如中学时期的试卷练习一样。同一份试卷的考题可以让学生做多次，但每次只需要重复上次学生做错的题；而上次做对了的题目，就不需要反复练习了。这样的练习可以突出重点，同时又节约时间。

在 AdaBoost 算法中，每一步迭代中均涉及两个权重的更新，一是样本权重，二是分类器权重。在样本权重更新中，倾向于赋更大权重给上一步错分样本，以提高其在本次迭代中的“发言权”；在分类器权重更新中，倾向于将更大权重给错误率小的分类器，以突出“优秀”分类的作用。最终的分类器表示为弱分类器的线性组合，用以给出集成后的分类结果。

k-means是最常见的聚类算法。k-means先随机在数据集里找k个簇中心点，把每个数据分到离它最近的中心所在的那个簇；然后再计算新的簇中心点。由此不断循环，直到所有簇中心不再变化。k-means 背后的思想其实属于 Expectation Maximization的一种。Expectation Maximization算法专门针对含有隐藏变量的模型进行估计。在k-means里，这个模型的参数就是k个簇的中心。隐藏的变量就是每个数据点的类标。如果我们知道每个数据点的类标，那么只需要针对每个簇的数据点求算数平均，就可以估计出这个簇的中心。但问题是，每个数据点的类标是隐藏的（未知的），所以我们无法直接估计出每个簇的簇中心。因此，需要随机选定几个簇质心，再通过迭代更新簇质心，从而最小化簇内相似性，最大化簇间相似性。

在图 1-8（a）中，初始质心（表示为+号）随机指定，在经过k-means 算法训练后，质心为各个簇的中心点，参见图1-8（b）。

k-means算法是最简单，也是最常用的聚类算法，然而由于初始质心随机指定，算法最终结果可能收敛为局部最小。

期望最大化（Expectation Maximization，EM）算法解决的问题是，在隐变量（Latent Variable）存在的情况下，对隐变量进行估计。在EM算法中，通过求解最大似然（Maximum Likelihood）找出模型参数，以使这个模型最能描述当前观察数据。换句话说，这个估计方法希望让观察的数据在这个估计的模型里出现的概率最高。

最大似然是统计学中一个参数估计原则。至于为什么要用最大似然这个原则，这源于概率论与数理统计的一个直观假设：观察到的事件总比没有观察到的事件发生的概率高；多次观察到的事件出现的概率总比很少观察到的事件出现的概率高。

EM算法是两个不同步骤的不断循环。一个步骤叫作Expectation，也就是固定当前模型的参数，估计最有可能隐藏变量的值。另外一个步骤叫作 Maximization，即通过当前估计隐藏变量的值，估计模型的参数。EM 算法不断迭代隐变量和模型参数的求解，直到模型的参数不再变化，算法即停止。在图 1-9 中给出了一个 EM算法的实例[3]。抛掷两枚硬币A、B：每次实验抛掷硬币10次，重复5次实验，当前抛掷的硬币为A或B是未知的（隐变量）。依据5次实验结果，估计硬币A与B正面朝上（用H表示，同理背面朝上用T表示）的概率θA与θB。

首先估计初始状态硬币A、B朝上的概率分别为0.6和0.5，按照二项分布估计硬币为A或B的概率分别为0.45和0.55。利用求得的概率乘以观察到的5次实验的结果，得到估计出的硬币A和B分别正面朝上的分布情况，例如对硬币A而言， 2.2枚正面朝上，2.2枚背面朝上；对硬币 B 而言，2.8枚正面朝上，2.8枚背面朝上。依据这样的结果更新θA与θB（更新的方向为在估计的隐变量下，得到的结果最接近观察到的实验结果，即求解实验结果在隐变量取值概率下的期望最大化，亦即Maximization步骤），那么更新后的θA与θB分别为0.71和0.58。将得到的估计再次传递给 Expectation 步骤，重复以上步骤，直到θA与θB不再明显变化为止。

Expectation和Maximization都是基于最大似然方法找隐藏变量的值和模型的参数值。在k-means里，把每个数据点塞进k个簇中，寻找离簇中心最近的那个步骤就是 Expectation。通过计算簇内所有数据点的算术平均得到簇中心的步骤就是Maximization。k-means 的目的是让每个簇内的数据点尽量靠近簇中心。从最大似然的角度来看，一个数据点越靠近其簇中心，它出现的概率就越高。因此在步骤Expectation中，k-means把每个数据点塞给距离最近的那个簇中心的簇。Maximization步骤的簇中心是通过算术平均求得的。算术平均就是最大似然的估计。

Apriori 算法的最早提出是为了寻找关联规则。关联规则最著名的例子莫过于“啤酒与尿布”，在超市货篮数据分析中，人们发现年轻爸爸在超市买尿布时，常常也会顺带为自己买啤酒。因此，从营销的角度来看，超市可以将尿布和啤酒绑定销售，或者给一点小小的折扣，以此刺激消费。这种促销方案类似于现在很多电信运营商的套餐服务。

关联规则通常表示成，意思是如果A、B出现了，那么C也有很大可能出现。关联规则依据历史数据求得。显然，不能因为历史数据中出现了一条数据同时包含A、B、C就认为成立。只有足够的数据记录都包含A、B、C 时，才认为这个规则是有一定置信度（Confidence）的。所以，关联规则第一步就是找出频繁的项集（Frequent Item Set）。项（Item）就是指这里的A、B、C等。项集（Item Set）就是包含这些项的集合。在这个例子里，{A,B,C}就是一个频繁的项集，A、B、C 属于项。如果数据库里有n个不同的项，那么总共可能有2n个项集。显然我们不能一个一个去试，看其是否频繁。Apriori算法要解决的问题就是如何快速找出频繁项集。Apriori 的核心思想就是认为如果项集{A,B,C}是频繁的，那么它的子集也必须是频繁的。这就是 Apriori 算法里所描述的递减性质（Anti-Monotonic Property）。

频繁的定义就是指出现的次数大于某个预先定义的阈值。因此，可以从只含一个项的集合开始搜索，剔除非频繁项。然后通过自拼接的方式，寻找只含2个项的集合，再剔除非频繁项。依次类推，即可找到所有的频繁项集。

如果把算法的搜索看作一个搜索树，那么每次的剔除都是剔除一棵树的分支，所以就可以大大减小搜索空间。因为Apriori算法有很清晰和简单的算法逻辑结构，所以Apriori逐步成为一种搜索算法思想，有点类似动态规划、贪心算法的概念。在很多相关论文里，算法以Apriori-like来修饰，但是算法的目的跟关联规则挖掘并没有关系。

Apriori算法的其他应用还包括告警的关联挖掘、用户行为关联分析以及崩溃和错误的关联分析等。处理任务描述参见表1-3。

PageRank因为谷歌搜索引擎而出名。该算法以Google创始人之一Larry Page的姓命名，他将学术论文的评分方法（按照引用量对论文质量进行评估）引入网页评分中。合作者Sergey Brin将算法转换为矩阵迭代运算的形式并证明其收敛性。该算法的思想可以用图1-10形象地表示。

满足一个关键词的网页通常有很多，如何安排这些网页显示的前后顺序呢？PageRank的想法就是，如果这个网页被很多其他网页引用，那么网页重要程度就很高，理应放得靠前一些。如果一个网页只被很少网页引用甚至没有被引用，那么这个网页就不重要，可以放得靠后一些。这里的引用和论文之间的引用类似。评价一篇论文的好坏也是看其引用数量。在网页里，引用可以是一个超链接。当然， PageRank 还可以用在其他图数据上，只要它们存在某种链接，就可以认为是这里的引用。除此之外，PageRank还认为，如果一个网页被重要的网页引用，那么这个网页肯定比被不重要网页引用的网页更重要。如果把每个网页的重要分数看成一个未知变量，这 2个直观的假设可以整理成一个线性方程，那么 PageRank 根据此方程解出每个网页的重要分数。最后网页的排名就是按照这个重要分数由大到小排列。同时，针对有向图中的死胡同问题（Dead End Problem）和陷阱问题（Trap Problem）， PageRank算法引入阻尼因子（Damping Factor），使得算法能以一定概率随机跳出到外部任意页面。

换句话说，PageRank算法综合考虑链接的数量和网页的质量两个因素,将二者结合起来对网页进行排序。需要特别指出的是，PageRank计算出的网页重要性排名是完全基于链接结构的，与用户输入的查询关键字无关。所以，很多时候，PageRank是可以离线计算的。

PageRank算法原理简单，具有简洁之美。然而，PageRank也有诸多缺点：PageRank无法抵御链接攻击（例如在权威页面下评论，并添加自身页面引用，提高自身PageRank值）；对新网页不公平，新网页到来时没有引用量，但并不代表质量不好。