机器学习的常用算法（生信必备）

作为一个合格的生物信息工程师，生物学的算法是必备的技能。本人从业不到一年，深感统计学知识匮乏，希望以简书作为自己的学习平台，和大家分享一些常用的算法，本人能力有限，只能介绍一些常用的，还有很多不断在更新的算法，希望各位道友多多发表，多多沟通。

决策树算法

算法思想

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。
其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。
使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
简单的说就是根据一些feature进行数据分类，从根上开始，每个分支节点提一个问题，然后依据是否满足条件分为两类，然后再进行提问，循环往复，直到达到数据每个分支的末端
总结来说：
决策树模型核心是下面几部分：
一、结点和有向边组成
二、结点有内部结点和叶结点俩种类型
三、内部结点表示一个特征，叶节点表示一个类

算法

ID3算法

“信息熵”是度量样本集合不确定度的最常用的指标。
在ID3算法中，我们采取信息增益这个量来作为不确定度的度量。我们选取使得信息增益最大的特征进行分裂！
信息熵是代表随机变量的复杂度（不确定度），条件熵代表在某一个条件下，随机变量的复杂度（不确定度）。而我们的信息增益恰好是：信息熵-条件熵。
当前样本集合 D 中第 k 类样本所占的比例为 pk ，则 D 的信息熵定义为：

1.png
离散属性 a 有 V 个可能的取值 {a1,a2,…,aV}；样本集合中，属性 a 上取值为 av 的样本集合，记为 Dv。
用属性 a 对样本集 D 进行划分所获得的“信息增益”
2.png
信息增益表示得知属性 a 的信息而使得样本集合不确定度减少的程度
在决策树算法中，我们的关键就是每次选择一个特征，特征有多个，那么到底按照什么标准来选择哪一个特征。
这个问题就可以用信息增益来度量。如果选择一个特征后，信息增益最大（信息不确定性减少的程度最大），那么我们就选取这个特征。

C4.5算法

首先我们来看信息增益率的公式：

1.png

由上图我们可以看出，信息增益率=信息增益/IV(a),说明信息增益率是信息增益除了一个属性a的固有值得来的。
我们来看IV(a)的公式：
属性a的固有值：

2.png

CART算法

这里我们重点看一下CART算法
当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据;
分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。
CART既能是分类树，又能是决策树。
CART如何选择分裂的属性？
如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。
GINI值的计算公式：

image
节点越不纯，GINI值越大。以二分类为例，如果节点的所有数据只有一个类别，则 image ，
如果两类数量相同，则 image 。
回归方差计算公式：
image
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。
因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者
回归方差最小的属性作为分裂的方案。即最小化（分裂树）
image
或者（回归树）：
image
CART如何分裂成一棵二叉树？
节点的分裂分为两种情况，连续型的数据和离散型的数据。
CART对连续型属性的处理与C4.5差不多，通过最小化分裂后的GINI值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看C4.5。
对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。
详细的例子决策树算法

随机森林算法

1 什么是随机森林？

作为新兴起的、高度灵活的一种机器学习算法，随机森林（Random Forest，简称RF）拥有广泛的应用前景，从市场营销到医疗保健保险，既可以用来做市场营销模拟的建模，统计客户来源，保留和流失，也可用来预测疾病的风险和病患者的易感性。最初，我是在参加校外竞赛时接触到随机森林算法的。最近几年的国内外大赛，包括2013年百度校园电影推荐系统大赛、2014年阿里巴巴天池大数据竞赛以及Kaggle数据科学竞赛，参赛者对随机森林的使用占有相当高的比例。此外，据我的个人了解来看，一大部分成功进入答辩的队伍也都选择了Random Forest 或者 GBDT 算法。所以可以看出，Random Forest在准确率方面还是相当有优势的。
那说了这么多，那随机森林到底是怎样的一种算法呢？
如果读者接触过决策树（Decision Tree）的话，那么会很容易理解什么是随机森林。随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支——集成学习（Ensemble Learning）方法。随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。“森林”我们很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，这样的比喻还是很贴切的，其实这也是随机森林的主要思想--集成思想的体现。“随机”的含义我们会在下边部分讲到。
其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging 思想。
简单地说，就是在源数据中随机选取几个子集，产生随机subsets进行分类

2 随机森林的特点

我们前边提到，随机森林是一种很灵活实用的方法，它有如下几个特点：

• 在当前所有算法中，具有极好的准确率/It is unexcelled in accuracy among current algorithms；
• 能够有效地运行在大数据集上/It runs efficiently on large data bases；
• 能够处理具有高维特征的输入样本，而且不需要降维/It can handle thousands of input variables without variable deletion；
• 能够评估各个特征在分类问题上的重要性/It gives estimates of what variables are important in the classification；
• 在生成过程中，能够获取到内部生成误差的一种无偏估计/It generates an internal unbiased estimate of the generalization error as the forest building progresses；
• 对于缺省值问题也能够获得很好得结果/It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing
• ... ...

实际上，随机森林的特点不只有这六点，它就相当于机器学习领域的Leatherman（多面手），你几乎可以把任何东西扔进去，它基本上都是可供使用的。在估计推断映射方面特别好用，以致都不需要像SVM那样做很多参数的调试。具体的随机森林介绍可以参见随机森林主页：Random Forest。

3 随机森林的相关基础知识

随机森林看起来是很好理解，但是要完全搞明白它的工作原理，需要很多机器学习方面相关的基础知识。在本文中，我们简单谈一下，而不逐一进行赘述，如果有道友不太了解相关的知识，可以参阅其他博友的一些相关博文或者文献。
1）信息、熵以及信息增益的概念
这三个基本概念是决策树的根本，是决策树利用特征来分类时，确定特征选取顺序的依据。理解了它们，决策树你也就了解了大概。
引用香农的话来说，信息是用来消除随机不确定性的东西。当然这句话虽然经典，但是还是很难去搞明白这种东西到底是个什么样，可能在不同的地方来说，指的东西又不一样。对于机器学习中的决策树而言，如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息可以定义如下:

image
I(x)用来表示随机变量的信息，p(xi)指是当xi发生时的概率。
熵是用来度量不确定性的，当熵越大，X=xi的不确定性越大，反之越小。对于机器学习中的分类问题而言，熵越大即这个类别的不确定性更大，反之越小。
信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好。
这方面的内容不再细述，感兴趣的同学可以看 信息&熵&信息增益 这篇博文。

2）决策树

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。

3）集成学习

集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。

随机森林是集成学习的一个子类，它依靠于决策树的投票选择来决定最后的分类结果。你可以在这找到用python实现集成学习的文档：Scikit 学习文档。

4 随机森林的生成

前面提到，随机森林中有许多的分类树。我们要将一个输入样本进行分类，我们需要将输入样本输入到每棵树中进行分类。打个形象的比喻：森林中召开会议，讨论某个动物到底是老鼠还是松鼠，每棵树都要独立地发表自己对这个问题的看法，也就是每棵树都要投票。该动物到底是老鼠还是松鼠，要依据投票情况来确定，获得票数最多的类别就是森林的分类结果。森林中的每棵树都是独立的，99.9%不相关的树做出的预测结果涵盖所有的情况，这些预测结果将会彼此抵消。少数优秀的树的预测结果将会超脱于芸芸“噪音”，做出一个好的预测。将若干个弱分类器的分类结果进行投票选择，从而组成一个强分类器，这就是随机森林bagging的思想（关于bagging的一个有必要提及的问题：bagging的代价是不用单棵决策树来做预测，具体哪个变量起到重要作用变得未知，所以bagging改进了预测准确率但损失了解释性。）。下图可以形象地描述这个情况：

image

有了树我们就可以分类了，但是森林中的每棵树是怎么生成的呢？

每棵树的按照如下规则生成：

1）如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；

从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。

为什么要随机抽样训练集？

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；

为什么要有放回地抽样？

我理解的是这样的：如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是绝对"片面的"（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是"盲人摸象"。

2）如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；

3）每棵树都尽最大程度的生长，并且没有剪枝过程。

一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

随机森林分类效果（错误率）与两个因素有关：

• 森林中任意两棵树的相关性：相关性越大，错误率越大；
• 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

5 袋外错误率（oob error）

上面我们提到，构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率oob error（out-of-bag error）。

随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。

我们知道，在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob样本。

而这样的采样特点就允许我们进行oob估计，它的计算方式如下：

（note：以样本为单位）

1）对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）；

2）然后以简单多数投票作为该样本的分类结果；

3）最后用误分个数占样本总数的比率作为随机森林的oob误分率。

（文献原文：Put each case left out in the construction of the kth tree down the kth tree to get a classification. In this way, a test set classification is obtained for each case in about one-third of the trees. At the end of the run, take j to be the class that got most of the votes every time case n was oob. The proportion of times that j is not equal to the true class of n averaged over all cases is the oob error estimate. This has proven to be unbiased in many tests.）
oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。
详细例子[随即森林例子]（https://blog.csdn.net/yangyin007/article/details/82385967）

SVM算法

support vector machine
这个想法对于生物信息来说应该是最为熟悉，无论是Seurat包还是Cellranger都采用这个算法
算法很复杂，这里我们简单来学一下其中的基础算法

1.1支持向量机(SVM)的由来

首先我们先来看一个3维的平面方程：Ax+By+Cz+D=0
这就是我们中学所学的，从这个方程我们可以推导出二维空间的一条直线：Ax+By+D=0
那么，依次类推，更高维的空间叫做一个超平面：

image
x代表的是一个向量，接下来我们看下二维空间的几何表示：
image
SVM的目标是找到一个超平面，这个超平面能够很好的解决二分类问题，所以先找到各个分类的样本点离这个超平面最近的点，使得这个点到超平面的距离最大化，最近的点就是虚线所画的。由以上超平面公式计算得出大于1的就属于打叉分类，如果小于0的属于圆圈分类。
这些点能够很好地确定一个超平面，而且在几何空间中表示的也是一个向量，那么就把这些能够用来确定超平面的向量称为支持向量（直接支持超平面的生成），于是该算法就叫做支持向量机(SVM)了。

1.2如何找到超平面

函数间隔

在超平面wx+b=0确定的情况下，|wx+b|能够表示点x到距离超平面的远近，而通过观察wx+b的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用(y(w*x+b))的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。定义函数间隔（用

image
表示)为：
image
但是这个函数间隔有个问题，就是我成倍的增加w和b的值，则函数值也会跟着成倍增加，但这个超平面没有改变。所以有函数间隔还不够，需要一个几何间隔。

几何间隔

我们把w做一个约束条件，假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到超平面的距离，如下图所示：

image

根据平面几何知识，有

image
image.png

1.3最大间隔分类器

对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的Gap的一半。

image
image.png

1.4后续问题

至此，SVM的第一层已经了解了，就是求最大的几何间隔，对于那些只关心怎么用SVM的朋友便已足够，不必再更进一层深究其更深的原理。
SVM要深入的话有很多内容需要讲到，比如：线性不可分问题、核函数、SMO算法等。
在此推荐一篇博文，这篇博文把深入的SVM内容也讲了，包括推导过程等。如果想进一步了解SVM，推荐看一下：
支持向量机通俗导论：https://blog.csdn.net/v_JULY_v/article/details/7624837#commentBox

KNN算法

一、KNN算法概述

邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。与急切学习（eager learning）相对应。

KNN是通过测量不同特征值之间的距离进行分类。

思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

提到KNN，网上最常见的就是下面这个图，可以帮助大家理解。

我们要确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。

image

算法的描述：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类

二、关于K的取值

K：临近数，即在预测目标点时取几个临近的点来预测。

K值得选取非常重要，因为：

如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；

如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；

K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。

K的取法：

常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。

一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。

三、关于距离的选取

距离就是平面上两个点的直线距离

关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。

Euclidean Distance 定义：

两个点或元组P1=（x1，y1）和P2=（x2，y2）的欧几里得距离是

image

距离公式为：（多个维度的时候是多个维度各自求差）

image

四、总结

KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时

KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。

KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。

KNN很耗时，时间复杂度为O(n)，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。

（弱小无助。。。根据许多大佬的总结整理的）

神经网络算法

神经网络是所谓深度学习的一个基础，也是必备的知识点，他是以人脑中的神经网络作为启发，最著名的算法就是backpropagation算法，这里就简单的整理一下神经网络相关参数，和计算方法。
一、多层向前神经网络（Multilayer Feed-Forward Neural Network）

多层向前神经网络由一下几个部分组成：
输入层（input layer），隐藏层（Hidden layer），输出层（output layer）

图片.png

特点如下：
1、每层由单元（units）组成
2、输入层是有训练集的实例特征向量传入
3、经过连接接点的权重（weight）传入下一层，一层的输出是下一层的输入
4、隐藏层的个数可以是任意的，输入层有一层，输出层有一层
5、每个单元也可以称之为神经结点，根据生物学来源定义
6、以上成为两层的神经网络，输入层是不算在里面的
7、一层中加权求和，然后根据非线性方程转化输出
8、作为多层向前神经网络，理论上，如果有足够的隐藏层，和足够的训练集，可以模拟出任何方程
二、设计神经网络结构

1、使用神经网络训练数据之前，必须确定神经网络的层数，以及每层单元的个数
2、特征向量在被传入输入层时通常要先标准化到0-1之间（为了加速学习过程）
3、离散型变量可以被编码成每一个输入单元对应一个特征值可能赋的值
比如：特征值A可能取三个值（a0, a1, a2), 可以使用3个输入单元来代表A。
如果A=a0, 那么代表a0的单元值就取1, 其他取0；
如果A=a1, 那么代表a1de单元值就取1，其他取0，以此类推
4、神经网络即可以用来做分类（classification）问题，也可以解决回归（regression）问题
（1）对于分类问题，如果是2类，可以用一个输出单元表示（0和1分别代表2类），如果多余2类，则每一个类别用一个输出单元表示
（2）没有明确的规则来设计最好有多少个隐藏层，可以根据实验测试和误差以及精准度来实验并改进
三、交叉验证方法（cross-Validation）

这里有一堆数据，我们把他切成3个部分（当然还可以分的更多）
第一部分做测试集，二三部分做训练集，算出准确度；
第二部分做测试集，一三部分做训练集，算出准确度；
第三部分做测试集，一二部分做训练集，算出准确度；
之后算出三个准确度的平局值，作为最后的准确度，如下图：

图片.png

这里写图片描述
四、backpropagation算法

他是通过迭代性来处理训练集中的实例，对比经过神经网络后，输人层预测值与真实值之间的误差，再通过反向法（从输出层=>隐藏层=>输入层）以最小化误差来更新每个连接的权重。

• 算法的详细介绍
  输入：D（数据集），学习率（learning rate），一个多层向前神经网络
  输出：一个训练好的神经网络（a trained neural network）

1.初始化权重和偏向：随机初始化在-1到1之间，或者-0.5到0.5之间，每个单元有一个偏向
2.开始对数据进行训练，步骤如下：

图片.png

由输入层向前传送

图片.png
Ij：要对其进行非线性转化，为下一单元的值
Oi：是输入的值
wij：为每个单元到下一个单元连线之间的权重

θj:偏向

对Ij进行非线性转化，得到下一个单元的值

图片.png

根据误差(error)反向传送

图片.png 对于输出层： 图片.png

对于隐藏层：这里写图片描述
Errj：用于更新偏向
Oj：为输出的值
Tj：为标签的值

图片.png
权重更新：
括号里为小l ，是学习率（learning rate）
图片.png

终止条件
方法一：权重的更新低于某个阈值
方法二：预测的错误率低于某个阈值
方法三：达到预设一定的循环次数
这个算法看起来很复杂，不容易理解，需要认真揣摩，一步一步认真推导结果。