详细解释数据挖掘中的 10 大算法（下）

问题导读


1.PageRank本文认为了什么而产生的算法？
2.AdaBoost 算法是做什么的？
3.朴素贝叶斯（Naive Bayes）并不只是一个算法是否正确？

上一篇中作者解释了 C4.5算法、K 均值聚类算法、支持向量机、Apriori 关联算法、EM 算法，下篇继续解释 PageRank 算法、AdaBoost 迭代算法、kNN 算法、朴素贝叶斯算法、CART 分类算法。

6.PageRank算法

算法是做什么的？PageRank是为了决定一些对象和同网络中的其他对象之间的相对重要程度而设计的连接分析算法(link analysis algorithm)。

那么什么是连接分析算法呢？它是一类针对网络的分析算法，探寻对象间的关系（也可成为连接）。

举个例子：最流行的 PageRank 算法是 Google 的搜索引擎。尽管他们的搜索引擎不止是依靠它，但  PageRank依然是 Google 用来测算网页重要度的手段之一。

解释一下：

万维网上的网页都是互相链接的。如果 Rayli.net 链接到了 CNN 上的一个网页，CNN 网页就增加一个投票，表示 rayli.net 和 CNN 网页是关联的。

这还没有结束：

反过来，来自rayli.net 网页的投票重要性也要根据 rayli.net 网的重要性和关联性来权衡。换句话说，任何给 rayli.net 投票的网页也能提升 rayli.net 网页的关联性。

基本概括一下：

投票和关联性就是 PageRank 的概念。rayli.net 给CNN 投票增加了 CNN 的 Pagerank，rayli.net 的 PageRank级别同时也影响着它为 CNN 投票多大程度影响了CNN 的 PageRank。

那么 PageRank 的0，1，2，3级别是什么意思？ 尽管 Google 并没有揭露PageRank 的精确含义，我们还是能了解它的大概意思。

我们能通过下面这些网站的PageRank得到些答案：

看到了么？

这排名有点像一个网页流行度的竞争。我们的头脑中都有了一些这些网站的流行度和关联度的信息。

PageRank只是一个特别讲究的方式来定义了这些而已。

PageRank还有什么其他应用呢？ PageRank是专门为了万维网设计的。

可以考虑一下，以核心功能的角度看，PageRank算法真的只是一个处理链接分析极度有效率的方法。处理的被链接的对象不止只是针对网页。

下面是 PageRank3个创新的应用：

•   芝加哥大学的Dr Stefano Allesina，将 PageRank应用到了生态学中，测定哪个物种对可持续的生态系统至关重要。
•   Twitter 研究出了一种叫 WTF（Who-to-Follow）算法，这是一种个性化的 PageRank推荐关注人的引擎。
•   香港理工大学的 Bin Jiang 使用一种变形的PageRank来预测基于伦敦地形指标的行人移动速率。
  

这算法是监督的还是非监督的？PageRank常用来发现一个网页的重要度关联度，通常被认为是一种非监督学习算法。

为什么使用PageRank？可以说，PageRank的主要卖点是：由于得到新相关链接具有难度，算法依然具有良好的鲁棒性。

更简单一点说，如果你又一个图或者网络，并想理解其中元素的相对重要性，优先性，排名或者相关性，可以用PageRank试一试。

哪里使用过它呢？Google 拥有PageRank 的商标。但是斯坦福大学取得了PageRank 算法的专利权。如果使用 PageRank，你可能会有疑问： 我不是律师，所以最好和一个真正的律师确认一下。但是只要和 Google 或斯坦福没有涉及到商业竞争，应该都是可以使用这个算法的。

给出PageRank 的三个实现：

1 C++ OpenSource PageRank Implementation

2 Python PageRank Implementation

3 igraph – The network analysis package (R)

7.AdaBoost 迭代算法

AdaBoost 算法是做什么的？AdaBoost 是个构建分类器的提升算法。

也许你还记得，分类器拿走大量数据，并试图预测或者分类新数据元素的属于的类别。

但是，提升(boost) 指的什么？提升是个处理多个学习算法（比如决策树）并将他们合并联合起来的综合的学习算法。目的是将弱学习算法综合或形成一个组，把他们联合起来创造一个新的强学习器。

强弱学习器之间有什么区别呢？弱学习分类器的准确性仅仅比猜测高一点。一个比较流行的弱分类器的例子就是只有一层的决策树。

另一个，强学习分类器有更高的准确率，一个通用的强学习器的例子就是 SVM。

举个 AdaBoost 算法的例子：我们开始有3个弱学习器，我们将在一个包含病人数据的数据训练集上对他们做10轮训练。数据集里包含了病人的医疗记录各个细节。

问题来了，那我们怎么预测某个病人是否会得癌症呢？AdaBoost 是这样给出答案的：

第一轮，AdaBoost 拿走一些训练数据，然后测试每个学习器的准确率。最后的结果就是我们找到最好的那个学习器。另外，误分类的样本学习器给予一个比较高的权重，这样他们在下轮就有很高的概率被选中了。

再补充一下，最好的那个学习器也要给根据它的准确率赋予一个权重，并将它加入到联合学习器中（这样现在就只有一个分类器了）

第二轮， AdaBoost 再次试图寻找最好的学习器。

关键部分来了，病人数据样本的训练数据现在被有很高误分配率的权重影响着。换句话说，之前误分类的病人在这个样本里有很高的出现概率。

为什么？

这就像是在电子游戏中已经打到了第二级，但当你的角色死亡后却不必从头开始。而是你从第二级开始然后集中注意，尽力升到第三级。

同样地，第一个学习者有可能对一些病人的分类是正确的，与其再度试图对他们分类，不如集中注意尽力处理被误分类的病人。

最好的学习器也被再次赋予权重并加入到联合分类器中，误分类的病人也被赋予权重，这样他们就有比较大的可能性再次被选中，我们会进行过滤和重复。

在10轮结束的时候，我们剩下了一个带着不同权重的已经训练过的联合学习分类器，之后重复训练之前回合中被误分类的数据。

这是个监督还是非监督算法？因为每一轮训练带有已经标记好数据集的弱训练器，因此这是个监督学习。

为什么使用 AdaBoost？AdaBoost算法简单， 编程相对来说简洁直白。

另外，它速度快！弱学习器 一般都比强学习器简单，简单意味着它们的运行速度可能更快。

还有件事：

因为每轮连续的Adaboost回合都重新定义了每个最好学习器的权重，因此这是个自动调整学习分类器的非常简洁的算法，你所要做的所有事就是指定运行的回合数。

最后，算法灵活通用，AdaBoost 可以加入任何学习算法，并且它能处理多种数据。

AdaBoost 有很多程序实现和变体。给出一些：

▪ scikit-learn

▪ ICSIBoost

▪ gbm: Generalized Boosted Regression Models

如果你喜欢Mr.Rogers,你会喜欢下面的算法的…

8.kNN：k最近邻算法

它是做什么的？kNN，或 K 最近邻(k-Nearest Neighbors), 诗歌分类算法。然而，它和我们之前描述的分类器不同，因为它是个懒散学习法。

什么是懒散学习法呢？和存储训练数据的算法不同，懒散学习法在训练过程中不需要做许多处理。只有当新的未被分类的数据输入时，这类算法才会去做分类。

但在另一方面，积极学习法则会在训练中建立一个分类模型，当新的未分类数据输入时，这类学习器会把新数据也提供给这个分类模型。

那么 C4.5，SVM 和 AdaBoost 属于哪类呢？不像 kNN算法，他们都是积极学习算法。

给出原因：

1 C4.5 在训练中建立了一个决策分类树模型。

2 SVM在训练中建立了一个超平面的分类模型。

3 AdaBoost在训练中建立了一个联合的分类模型。

那么 kNN 做了什么？ kNN 没有建立这样的分类模型，相反，它只是储存了一些分类好的训练数据。那么新的训练数据进入时，kNN 执行两个基本步骤：

1 首先，它观察最近的已经分类的训练数据点—也就是，k最临近点（k-nearest neighbors）

2 第二部，kNN使用新数据最近的邻近点的分类， 就对新数据分类得到了更好的结果了。

你可能会怀疑…kNN 是怎么计算出最近的是什么？ 对于连续数据来说，kNN 使用一个像欧氏距离的距离测度，距离测度的选择大多取决于数据类型。有的甚至会根据训练数据学习出一种距离测度。关于 kNN 距离测度有更多的细节讨论和论文描述。

对于离散数据，解决方法是可以把离散数据转化为连续数据。给出两个例子：

1 使用汉明距离（Hamming distance ）作为两个字符串紧密程度的测度。

2 把离散数据转化为二进制表征。

这两个来自Stack Overflow的思路也有一些关于处理离散数据的建议：

▪ KNN classification with categorical data

▪ Using k-NN in R with categorical values

当临近的点是不同的类，kNN 怎么给新数据分类呢？当临近点都是同一类的时候，kNN 也就不费力气了。我们用直觉考虑，如果附近点都一致，那么新数据点就很可能落入这同一个类中了。

我打赌你能猜到事情是从哪里开始变的麻烦的了…

当临近点不是同一类时，kNN 怎么决定分类情况的呢？

处理这种情况通常有两种办法：

1 通过这些临近点做个简单的多数投票法。哪个类有更多的票，新数据就属于那个类。

2 还是做个类似的投票，但是不同的是，要给那些离的更近的临近点更多的投票权重。这样做的一个简单方法是使用反距离(reciprocal distance). 比如，如果某个临近点距离5个单位，那么它的投票权重就是1/5.当临近点越来越远是，倒数距离就越来越小…这正是我们想要的。

这是个监督算法还是非监督的呢？因为 kNN 算法提供了已经被分类好的数据集，所以它是个监督学习算法。

为什么我们会用 kNN？便于理解和实现是我们使用它的两个关键原因。根据距离测度的方法，kNN 可能会非常精确。

但是这还只是故事的一部分，下面是我们需要注意的5点：

1 当试图在一个大数据集上计算最临近点时，kNN 算法可能会耗费高昂的计算成本。

2 噪声数据(Noisy data)可能会影响到 kNN 的分类。

3 选择大范围的属性筛选(feature)会比小范围的筛选占有很多优势，所以属性筛选(feature)的规模非常重要。

4 由于数据处理会出现延迟，kNN 相比积极分类器，一般需要更强大的存储需求。

5 选择一个合适的距离测度对 kNN 的准确性来说至关重要。

哪里用过这个方法？有很多现存的 kNN 实现手段：

▪ MATLAB k-nearest neighbor classification

▪ scikit-learn KNeighborsClassifier

▪ k-Nearest Neighbour Classification in R

是不是垃圾，先别管了。先读读下面的算法吧….

9. Naive Bayes 朴素贝叶斯算法

算法是做什么的？朴素贝叶斯（Naive Bayes）并不只是一个算法，而是一系列分类算法，这些算法以一个共同的假设为前提：

被分类的数据的每个属性与在这个类中它其他的属性是独立的。

独立是什么意思呢？当一个属性值对另一个属性值不产生任何影响时，就称这两个属性是独立的。

举个例子：

比如说你有一个病人的数据集，包含了病人的脉搏，胆固醇水平，体重，身高和邮编这样的属性。如果这些属性值互相不产生影响，那么所有属性都是独立的。对于这个数据集来说，假定病人的身高和邮编相互独立，这是合理的。因为病人的身高和他们的邮编没有任何关系。但是我们不能停在这，其他的属性间是独立的么？

很遗憾，答案是否定的。给出三个并不独立的属性关系：

▪ 如果身高增加，体重可能会增加。

▪ 如果胆固醇水平增加，体重可能增加。

▪ 如果胆固醇水平增加，脉搏也可能会增加。

以我的经验来看，数据集的属性一般都不是独立的。

这样就和下面的问题联系起来了…

为什么要把算法称为朴素的(naive)呢？数据集中所有属性都是独立的这个假设正是我们称为朴素（naive）的原因—— 通常下例子中的所有属性并不是独立的。

什么是贝叶斯（Bayes）？Thomas Bayes 是一个英国统计学家，贝叶斯定理就是以他名字命名的。点击这个链接可以知道更多贝叶斯定理的内容（Bayes’ Theorem）

总而言之，根据给定的一系列属性信息，借用概率的知识，我们可以使用这个定理来预测分类情况。

分类的简化等式看起来就像下面的这个式子：

我们在深入研究一下..

这个等式是什么意思？在属性1和属性2的条件下，等式计算出了A 类的概率。换句话说，如果算出属性1 和2，等式算出的数据属于 A 类的概率大小。

等式这样写解释为：在属性1和属性2条件下，分类 A 的概率是一个分数。

▪ 分数的分子是在分类 A条件下属性1的概率，乘以在分类 A 条件下属性2的概率，再乘以分类 A 的概率

▪ 分数的分母是属性1的概率乘以属性2的概率。

举个 Naive Bayes 的例子，下面是一个从 Stack Overflow thread (Ram’s answer)中找到的一个好例子。

事情是这样的：

▪ 我们有个1000个水果的训练数据集。

▪ 水果可能是香蕉，橘子或者其他（这些水果种类就是类）

▪ 水果可能是长形的、甜的、或者黄颜色的(这些是属性).

在这个训练集中你发现了什么？

▪ 500个香蕉中，长的有400个、甜的有350个、黄色的450个

▪ 300个橘子中、没有长的、甜的150个、黄色的300个

▪ 还剩下的200个水果中、长的100个、甜的150个、黄色的50个

如果我们根据长度、甜度和水果颜色，在不知道它们类别的情况下，我们现在可以计算水果是香蕉、橘子或者其他水果的概率了。

假设我们被告知这个未分类的水果是长的、甜的、黄色的。

下面我们以4个步骤来计算所有的概率：

第一步：想要计算水果是香蕉的概率，我们首先发现这个式子看起来很熟悉。这就是在属性为长形、甜和黄色的条件下，水果是香蕉类的概率，这个表达更简洁一些：

这确实就像我们之前讨论的那个等式。

第二步：以分子开始，让我们把公式的所有东西都加进去。

像公式一样，把所有的都乘起来，我们就得到了：

第三步：不用管分母了，因为计算别的分类时分子是一样的。

第四步：计算其他类时也做类似的计算：

因为0.252大于0.01875，Naive Bayes 会把长形，甜的还是黄色水果分到香蕉的一类中。

这是个监督算法还是非监督算法呢？ 为了得到频数表，Naive Bayes 提供了已经分好类的训练数据集，所以这是个监督学习算法。

为什么使用 Naive Bayes？就像你在上面看到的例子一样，Naive Bayes 只涉及到了简单的数学知识。加起来只有计数、乘法和除法而已。

一旦计算好了频数表(frequency tables),要分类一个未知的水果只涉及到计算下针对所有类的概率，然后选择概率最大的即可。

尽管算法很简单，但是 Naive Bayes 却出人意料的十分精确。比如，人们发现它是垃圾邮件过滤的高效算法。

Naive Bayes 的实现可以从Orange, scikit-learn, Weka和 R 里面找到。

最后，看一下第十种算法吧。

10.CART 分类算法

算法是做什么的？ CART 代表分类和回归树(classification and regression trees)。它是个决策树学习方法，同时输出分类和回归树。 像 C4.5一样，CART 是个分类器。

分类树像决策树一样么？分类树是决策树的一种。分类树的输出是一个类。

举个例子，根据一个病人的数据集、你可能会试图预测下病人是否会得癌症。这个分类或者是“会的癌症”或者是“不会得癌症”。

那回归树是什么呢？和分类树预测分类不同，回归树预测一个数字或者连续数值，比如一个病人的住院时间或者一部智能手机的价格。

这么记比较简单：

分类树输出类、回归树输出数字。

由于我们已经讲过决策树是如何分类数据的了，我们就直接跳过进入正题了…

CART和 C4.5对比如下：

这是个监督算法还是非监督的呢？为了构造分类和回归树模型，需要给它提供被分类好的训练数据集，因此 CART 是个监督学习算法。

为什么要使用 CART 呢？使用 C4.5的原因大部分也适用于 CART，因为它们都是决策树学习的方法。便于说明和解释这类的原因也适用于 CART。

和 C4.5一样，它们的计算速度都很快，算法也都比较通用流行，并且输出结果也具有可读性。

scikit-learn 在他们的决策树分类器部分实现了 CART 算法；R 语言的 tree package 也有 CART 的实现；Weka 和 MATLAB 也有CART的实现过程。

最后，基于斯坦福和加州大学伯克利分校的世界闻名的统计学家们的理论，只有 Salford系统有最原始的 CART 专利源码的实现部分。

写的棒极啦~