首页 > 代码库 > 机器学习算法Review之分类
机器学习算法Review之分类
机器学习有着丰富的理论，分为有监督学习和无监督学习，有监督学习包括分类和回归，无监督学习包括聚类等。各种机器学习算法的基本思想都不难理解（这里的基本思想我的理解是各个算法的模型建立），而难点在于对于模型的求解，这里边有着优美的理论还有一些技巧，如SVM，EM，CART，AdaBoost，RF等。这些算法都是一些专家学者历经数年乃至十数年的研究成果，要想将它们都研究透彻确实是一项大工程，多数算法深入下去都是一本书，因此这里旨在从理解及应用的角度对这些经典的机器学习算法进行review。
分类
1）KNN
KNN算法的原理是对于一个已标记的样本集，不用对改样本集进行分类器的训练，而直接使用该样本集作为分类器。对于一个测试数据，我们直接计算该数据和已标记的样本集中的数据相似度，选择和测试样本最相似的K个数据的标记中累计最多的类别作为对测试数据类别的预测。
该算法适用于样本容量比较大的类域的自动分类，而那些样本容量小的类域采用该方法比较容易产生误分。
对于K值的选择，K选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰，而如果K选择过大，并且测试数据属于已标记样本集中较少的类别，那么在选择K近邻时，实际上会将不太相似的数据亦被包含进来，造成噪声增加而导致分类准确率的降低。
对于K值的选择目前没有什么好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K值，一般初始值设置为几百到几千。
KNN算法的优点：较高的预测准确率，对噪声数据不敏感，对数据没有任何先验假设不需要训练分类器。
KNN算法的缺点：当样本不平衡时，一个类别的样本数据多，另一个类别的样本数据少时会降低预测准确率，这可以采用加权的方法，例如和测试数据相似度较高的样本数据获得较大的权重。另一个不足之处是计算量大，目前常用的解决方法是对已标记的样本集进行剪辑，去除分类作用不大的样本数据。
KNN算法的预测目标：连续或不连续。
2）决策树
决策树也叫做分类树，它被提出了两次。一次由统计学家Breiman等提出，花了十多年时间出书了他们的研究成果CART（1984），CART是分类回归树的简写，顾名思义，它既能用作分类（目标离散）也能用作回归（目标连续）。另一次由人工智能专家Quinlan等提出，ID3（1986），C4.5（1993）及C5.0等。CART和ID3等树形结构用做分类时，除了在分裂过程中选择属性的标准不同外（CART选用Gini指标，ID3选用熵增益，C4.5选用熵增益率），其它基本一致，这里对于决策树仅讨论ID3等算法。
构建决策树的原则是尽量使得每个节点的样本标签尽可能少，算法描述如下：
Check if every itemin the dataset is in the same class:
If so return the class label
Else
find the best feature to split the data
split the dataset
create a branch node
for each split
call create Branch and add the resultto the branch node
return branch node
对于ID3算法find the best feature tosplit the data的准则就是尽量使得分支之后节点的类别纯一些，也就是使得后续分类能够准确一些，它用熵增益来衡量，熵增益越大说明分裂后得到的样本集更纯一些。
C4.5算法是对ID3算法的改进，它选用熵增益率准则来选择best featureto split，目的在于分裂信息将阻碍选择值为均匀分布的属性。例如，考虑一个含有n个样例的集合被属性A彻底分割（分成n组，即一个样例一组）。这时分裂信息的值为log2n。相反，一个布尔属性B分割同样的n个实例，如果恰好平分两半，那么分裂信息值是1。如果属性A和B产生同样的信息增益，那么根据增益比率度量，明显B会得分更高。
使用熵增益比代替熵增益来选择属性产生的一个实际问题是，当某个Si接近S（|Si||S|）时分母可能为0或非常小。如果某个属性对于S的所有样例有几乎同样的值，这时要么会导致增益比率未定义，要么是增益比率非常大。为了避免选择这种属性，我们可以采用这样一些启发式规则，比如先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益比率测试。
C4.5对ID3改进的方面还包括：能处理连续属性数据，能够对不完整数据进行处理在树构造过程中进行剪枝，在构造决策树的时候，为了防止overfitting，那些挂着几个元素的节点直接构成叶子节点，这实际上是一种先剪枝的算法，后面在讲CART用于回归时会review一种后剪枝算法。
C5.0是将C4.5算法应用到Boosting算法中，Boosting是一种Ensemble的分类算法，功能很强大，和SVM在机器学习的分类算法中占据重要地位。Ensemble的分类算法将在后面review。
决策树算法的优点：计算复杂度低，学习结果易于理解，允许属性缺失，可处理不相关的属性。
决策树算法的缺点：易于过拟合，可以选择先剪枝或后剪枝算法防止过拟合。
决策树算法的预测目标：连续或不连续。
3）朴素贝叶斯
贝叶斯决策就是对于一个测试数据，计算它属于已知的标记的样本数据集中的每个类别的概率，即P（Ci|x），选择概率最大的一个作为该测试数据的决策类别，也就是通过先验概率求后验概率。贝叶斯决策的原理就是经典的贝叶斯定理，贝叶斯定理是由贝叶斯公式导出的。贝叶斯公式为：P（x|C）=P（xC）/P（C）=P（C|x）*P（x）/P（C），贝叶斯公式之所以有用是因为对于P（x|C）我们容易求出，而对于P（C|x）不容易求出，而我们又比较关心P（C|x）。贝叶斯定理为：P（C|x）= P（x|C）*P（C）/P（x）。
求P（Ci|x）时，由贝叶斯定理得到P（Ci|x）= P（x|Ci）*P（Ci）/P（x）。由于对于所有的Ci来说P（x）是一样的，因此可以不考虑后验概率P（Ci|x）的分母部分，仅比较分子大小而得出决策结果。分子由乘法构成，可以进行log处理，进而只需要进行加法计算。朴素贝叶斯假设样本数据的所有属性是独立的，所以P（x1……xn|Ci）* P（Ci）=P（x1|Ci）*……*P（xn|Ci）*P（Ci），这实际上是对Ci类中的样本数据属性的条件概率的一个加权。
由于朴素贝叶斯假设样本数据的属性是独立的，因此对于有些样本集其决策结果不太好，于是有的学者又提出了一些加权的贝叶斯决策算法，基于属性重要性的加权，基于属性相关性的加权以及基于粗糙集加权的贝叶斯决策算法等。
朴素贝叶斯的优点：对于容量小的数据集有较好的决策效果，能够处理多类别决策问题。
朴素贝叶斯的缺点：对于训练样本数据较为敏感。
朴素贝叶斯的预测目标：不连续。
4）Logistic回归
Logistic回归要解决的问题是对于测试数据的预测target是以概率的形式出现的，比如给出衡量某疾病的一组因素，要预测出该组因素下某疾病是会出现还是不会出现。对于这样的问题，用一般的多元线性回归来解决这样的问题就不太合适。
Logistic回归分析，本质上是对一组因素的线性组合所产生某种结果的可能性的一种估量，这种估量由Logistic函数给出，P（x）=e^（p0+px）/（1+e^（p0+px））。我们将其线性化，看看P（x）到底有什么意义，线性化得到：ln（P（x）/（1-p（x）））=p0+px，可以看出当P（x）很小时，p0+px的值会很小，当p（x）很大接近于1时，p0+px的值会很大，这是符合一般规律的，因为一组因素线性组合产生的作用越强，那么导致某种结果的概率就越大，相反一组因素线性组合产生的作用越弱，那么导致某种结果的概率就越小，这也是为什么选择Logistic函数来对一组因素的线性组合所产生某种结果的可能性进行估量。Logistic函数实际上是将一组因素的线性组合产生的作用强度映射到了（0,1）的概率空间，那么只要选择了合适的阈值很容易进行二分类。
有了Logistic函数这样的一个模型，现在剩下的工作就是对p0和p参数进行估计了。估计出了参数，我们就能够使用Logistic回归模型进行预测了。
设n个观测值为y1，y2……yn，设pi=p{yi=1|xi}为给定xi条件下得到yi=1的概率。同样条件下的到yi=0的概率为p{yi=0|xi}=1-pi。于是由上述两个方程得到的一个观测值的概率为p（yi）= （pi^yi）（（1-pi）^（1-yi）），因为各项观测值独立，所以它们的联合分布可以表示为各边际分布的乘积：l（p0，p）= {p（x1）^yi[1-p（x1）]^（1-y1）}*……*{p（xn）^yn[1-p（xn）]^（1-yn）}。对似然函数l（p0，p）取对数有L（p0，p）={[y1ln(p(x1))]+(1-y1)ln[1-p(x1)]}+……+{[ynln(p(xn))]+(1-yn)ln[1-p(xn)]}。可以对L求导然后用Newton-Raphson方法进行迭代求解参数p0，p。但幸运的是，L是一个凸函数，可以选择梯度下降或随机梯度下降法求解参数p，p0。
上面的方法是针对目标为离散的二分类情况，如果目标为连续的概率（值域为[0,1]）值时，我们又该怎么办呢？我们观察ln（P（x）/（1-p（x）））=p0+px公式，可以看出，先用ln（P（x）/（1-p（x）））对目标为连续值的概率进行变换，然后采用多元线性回归模型进行参数估计就行了。至于预测，进行相反的步骤就可以了。
Logistic回归的优点：算法复杂度不高，容易实现，对知识的表达容易说明。
Logistic回归的缺点：可能拟合度不够，预测准确率可能较低。
Logistic回归的预测目标：连续或不连续
5）SVM
SVM算法可以说一直占据着分类算法老大的位置，有着相当优美的理论。总的来说SVM算法的思想（求解分类问题的模型建立）是不难理解的，难点在于对模型的求解。算法的核心思想是一个优化问题，这个优化问题可以描述为：寻找到分割两类样本数据的超平面，该超平面要满足各类中距离分类平面最近的点到分类平面的距离最大，也就是对类间间隔最大情况下的超平面的参数进行估计。寻找最优分类面的问题最终转换成为一个二次寻优问题，理论是上这个二次寻优问题的解是一个全局最优解（凸二次函数），这也避免了像神经网络方法中不可避免的局部极值问题。从SVM的建模思想上来说，它能够避免像神经网络等模型那样在降低训练集上的分类错误时而导致的过拟合的情况，因此对于一些未见过的测试样本具有更好的推广能力。
SVM算法可分为三类：线性可分、非线性可分以及需要核函数映射三种。下面对这三种情况及相关类容进行一个brief review。
（1）线性可分情况
假设最优分类超平面的方程为：WTx+b=0。根据点到平面的距离公式，样本数据x到最优分类超平面的距离可表示为：| WTx+b|/||W||。现在我们想知道的是最优分类超平面方程的参数W和b，也就是建立如下模型：
argmax[W,b] { min[n] (| WTxn+b| / ||W||) }
上述模型中W,b为最优分类超平面参数，n为样本数据编号。
模型建立好了，下面就开始求解模型了。从min[n] (| WTxn+b | / ||W||)中的| WTx+b | / ||W||，可以看出，通过等比例的对W和b加权缩放，那么会存在很多的超平面满足min[n] (| WTxn+b | / ||W||)，于是我们对超平面进行规范化，选择使最近样本点xk到超平面的距离| WTxk+b| / ||W|| = 1时的W和b。现在从最近样本点到最优分类超平面的距离表示为：WTxk+b| / ||W|| = 1 / ||W||，此时最优分类超平面构成的分类间隔为：
m = 2 / ||W||
现在我们的目标就是求使得m最大化的W，让后将W带入| WTxk+b | = 1即可得到b。
最大化m = 2 / ||W||，等价于最小化：
J(W) = (1/2)*||W||2
其中带有约束条件：
yi((Wxi)+b) >= 1
(i=1, 2, 3,……,N)
yi是样本点类别，其值为+1或-1，(Wxi)=WTxi。
J(W)是一个带约束的极值问题，通过拉格朗日乘数法，可将J(W)转换成一个不受约束的极值问题，即关于W，b，和拉格朗日乘子α的最小化L：
L(W,b,α)=(1/2)*||W||2-∑i=1Nαi[yi((Wxi)+b)-1]
(αi > 0)
求L(W,b,α)对W和b的偏导，并令其等于零得到：
W=∑i=1Nαiyixi, ∑i=1Nαiyi=0
将上述两式带入L(W,b,α)得到：
L(α)=(-1/2)∑i=1N∑j=1Nαiαjyiyj(xixj)+∑i=1Nαi
(αi > 0, ∑i=1Nαiyi=0)
L(α)是一个关于α的拉格朗日对偶问题，是一个关于α的凸二次规划问题，详细解法可参看相关理论，后续有时间也会针对优化理论写一写博文。
根据最优化解的性质（Karush-Kuhn-Tucker-conditions），解α必须满足：αi[yi(WTxi+b)-1]= 0(i = 1,……,N)，因此对于每个样本点必须满足αi=0或yi(WTxi+b)-1=0。从而那些不满足yi(WTxi+b)-1=0的样本点对应的αi必为0；而只有那些满足yi(WTxi+b)-1=0的样本点才有对应的大于0的αi，这些样本点就被称作支持向量。
求出系数α，W，b的最优解α*，W*，b*后，得到如下的分类器：
h(x)=sgn((W*x)+b*)=sgn(∑i=1Nαi*yi(xix)+b*)
其中x是待分类的测试样本数据，xi是N个训练样本数据，xi和x之间是点积的关系。对于非支持向量而言，其αi等于0，所以分类器可如下表示：
h(x)=sgn(∑i∈SVαi*yi(xix)+b*)
（2）非线性可分情况（C-SVM）
为处理非线性情况，引入松弛变量ei>0，此时约束条件变为：
yi((Wxi)+b) >= 1-ei
(i=1, 2, 3,……,n)
当ei=0，上述约束条件变为线性可分时的约束条件；当0<ei<1时，说明约束条件允许样本点落在分割间隔内，但大于0则说明分类超平面仍能够正确分类；当ei>1时，说明约束条件已经允许分类超平面错误分类出现了。
附加一个错误代价系数C后，目标函数变为最小化下式：
J(W,e) = (1/2)*||W||2+C∑i=1Nei
目标函数包括两个部分，第一部分和线性可分情况一样，第二部分是分类造成的分类错误代价，只有ei>0的那些“错误”样本点（错误分类和落在分类间隔内的样本点）才会产生代价。事实上，最小化目标函数J(W,e)体现了对最大化间隔（目标函数第一部分）和最小错误分类代价（目标函数第二部分）之间的权衡。通过调整代价系数C的值，可以对两者之间进行权衡，找出最优的C来降低分类器的训练错误同时保证适当的推广能力。
类似线性可分情况的推导，可得到一个对偶问题，最大化下式：
L(α)=∑i=1Nαi - 1/2∑i=1N∑j=1Nαiαjyiyj(xixj)
(0<αi<C, ∑i=1Nαiyi=0)
再用二次规划技术求出系数α，W，b的最优解α*，W*，b*后，得到的分类器与线性可分情况一样。
（3）核函数映射情况
线性分类的能力毕竟有限，而且对于非线性可分情况也不能一味的放宽约束条件，这样会导致更多的训练错误。这时可以通过一个非线性映射f:Rn->RD将样本数据映射到高维的特征空间RD，映射后的样本数据在RD特征空间中线性可分。如果在高维特征空间中仍非线性可分，则可考虑非线性可分的情况。在分类时，我们直接将测试样本数据映射到高维特征空间后，使用RD特征空间中的分类器。
类似（2）中的推导过程，我们得到如下对偶问题，最大化下式：
L(α)=∑i=1Nαi - 1/2∑i=1N∑j=1Nαiαjyiyj(f(xi)f(xj))
(0<αi<C, ∑i=1Nαiyi=0)
这时有：
W=∑i=1Nαiyif(xi)
所以最终的分类器为：
h(x)=sgn((W*f(x))+b*)=sgn(∑i=1Nαi*yi(f(xi)f(x))+b*)
同样对于非支持向量而言，其αi等于0，于是上式可表示为：
h(x)=sgn(∑i∈SVαi*yi(f(xi)f(x))+b*)
（4）核函数
一般情况下我们都没必要关系映射函数f的具体形式。可以注意到在（3）中的优化函数L(α)以及分类函数h(x)中都只涉及的样本特征之间的点积运算(f(xi)f(xj))。因此在高维空间只需要进行点积运算，向量的点积也就是一个常数，那么我们能不能够抛开f的具体形式，而根据原特征空间中的xi，xj直接得到(f(xi)f(xj))的结果呢？答案是肯定的，这可以用原特征空间中的核函数实现的。
根据泛函的相关理论，只要一种核函数K(xi,xj)满足Mercer条件，它就对应某一变换空间（RD）中的内积。Mercer核函数计算高维空间中的点积公式：
K(xi,xj) = (f(xi)f(xj))
常用的核函数有线性和函数，多项式核函数，径向基核函数，Sigmoid核函数等，其中径向基核函数最为常用。
SVM的优点：分类错误率低，计算量低，结果容易解释。
SVM的缺点：对参数调整和核函数的选择较为敏感，基本算法只能用于而分类。
SVM的预测目标：连续或不连续。
有三种策略将二分类SVM推广到多分类，它们分别是一对多最大响应策略、一对一投票策略及一对一淘汰策略。
6）Ensemble
Ensemble类的分类算法的核心思想是由弱分类器构造强分类器，其大致可以分为两类，一类是基于Bagging（Bootstrap Aggregating）的，另一类基于Boosting的。基于Bagging的常用算法是RF（Random Forest），基于Boosting的常用算法是AdaBoost。
AdaBoost和RF算法虽然没有as elegant as SVM的theory，但是他们的思想是非常有意思的，可以说都是resultof thinking’s collision，他们的核心思想都是由弱分类器构造强分类器。
（1）AdaBoost
AdaBoost是1995年Freund和Schapire提出的，它解决了早期的Boosting算法存在的许多问题。其算法伪代码描述（Robert E. Schapire, A brief introduction to boosting,1999）如下：
AdaBoost和Random Forests算法最大的区别在于AdaBoost算法中的弱分类器的组合权重不一样，而bagging的每个弱分类器的组合权重是相等的。
AdaBoost算法的优点：较低的推广（测试）误差，编码容易，适用于多数的分类器，不用调整参数。
AdaBoost算法的缺点：对异常数据敏感。
AdaBoost算法预测目标：连续或不连续。
（2）Random Forest
Random Forest是Bagging (Breiman, 1996)和Random Feature Selection（Amit and Geman 1997）的结合。RandomForest算法对输入的数据要进行行（Bagging）、列（Random Feature Selection）的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m<M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。
Random Forest在衡量generalization error时，使用的是out-of-bagestimation方法，主要是Bagging采样使得这种方法成为可能。Random Forest还提供了属性重要性的计算方法，其描述为：1）对于随机森林中的每一颗决策树,使用相应OOB（袋外数据）数据来计记为OOBerr1；2）随机地对袋外数据OOB所有样本数据的特征xi加入噪声干扰（就可以随机的改变样本在特征xi处的值），再次计算它的袋外数据误差,记为errOOB2；3）假设随机森林中有N棵树,那么对于特征xi的重要性为∑(errOOB2-errOOB1)/N，之所以可以用这个表达式作为相应特征的重要性的度量值是因为，若给某个特征随机加入噪声之后，袋外的准确率大幅度降低，则说明这个特征对于样本的分类结果影响很大,也就是说它的重要程度比较高。
基于Random Forest提供的属性重要性计算方法，提出了随机森林的特征选择方法（Robin Genuer, Variable Selection using Random Forests，2012）。
首先特征选择的目标有两个：
1’：找到与因变量高度相关的特征变量。
2’：选择出数目较少的特征变量并且能够充分的预测应变量的结果。
其次一般特征选择的步骤为：
1’：初步估计和排序
a)对随机森林中的特征变量按照VI（Variable Importance）降序排序。
b)确定删除比例,从当前的特征变量中剔除相应比例不重要的指标，从而得到一个新的特征集。
c)用新的特征集建立新的随机森林,并计算特征集中每个特征的VI,并排序。
d)重复以上步骤,直到剩下m个特征。
2’：根据1中得到的每个特征集和它们建立起来的随机森林,计算对应的袋外误差率(OOB err),将袋外误差率最低的特征集作为最后选定的特征集。
Random Forest算法的优点：
1. 对于很多种资料，它可以产生高准确度的分类器。
2. 它可以处理大量的输入变量。
3. 它可以在决定类别时，评估变量的重要性。
4. 在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计。
5. 它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失，仍可以维持准确度。
6. 它提供一个实验方法，可以去侦测 variable interactions 。
7. 对于不平衡的分类资料集来说，它可以平衡误差。
8. 它计算各例中的亲近度，对于数据挖掘、侦测偏离者（outlier）和将资料视觉化非常有用。
9. 使用上述。它可被延伸应用在未标记的资料上，这类资料通常是使用非监督式聚类。也可侦测偏离者和观看资料。
10. 学习过程是很快速的。
Random Forest算法的缺点：
1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟。
2. 对于有不同级别的属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。
Random Forest算法预测目标：连续或不连续。
参考资料：
Machine Learning in Action
Induction of Decision Trees
数字图像处理与机器视觉
A brief introduction to boosting
Random Forests
Variable Selection using Random Forests
http://blog.csdn.net/cuoqu/article/details/9319459
http://www.cnblogs.com/wentingtu/archive/2011/12/22/2297405.html
http://www.360doc.com/content/13/1206/09/13528701_334877080.shtml
本文出自 “Remys” 博客，转载请与作者联系！
机器学习算法Review之分类