机器学习（二）--- 分类算法详解 常用分类算法 Ensemble learning

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E5%B8%B8%E7%94%A8%E5%88%86%E7%B1%BB%E7%AE%97%E6%B3%95">常用分类算法</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#bayes">Bayes</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">朴素贝叶斯的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E7%9A%84%E5%85%AC%E5%BC%8F">朴素贝叶斯的公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#decision-tree">Decision Tree</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E5%86%B3%E7%AD%96%E6%A0%91%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">决策树的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E5%86%B3%E7%AD%96%E6%A0%91%E5%85%AC%E5%BC%8F">决策树公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#svm">SVM</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">支持向量机的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA%E7%9A%84%E5%85%AC%E5%BC%8F">支持向量机的公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#knn">KNN</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#k%E8%BF%91%E9%82%BB%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">K近邻的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#k%E8%BF%91%E9%82%BB%E7%9A%84%E5%85%AC%E5%BC%8F">K近邻的公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#logistic-regression">Logistic Regression</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">逻辑回归的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E7%9A%84%E5%85%AC%E5%BC%8F">逻辑回归的公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E9%80%BB%E8%BE%91%E5%9B%9E%E5%BD%92%E7%9A%84%E9%97%AE%E9%A2%98">逻辑回归的问题</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C">神经网络</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9">神经网络的优缺点</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C%E5%85%AC%E5%BC%8F">神经网络公式</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0">深度学习</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#ensemble-learning">Ensemble learning</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#gbdt">GBDT</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#adaboost">Adaboost</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#random-forest">Random Forest</a>

<a href="http://blog.csdn.net/china1000/article/details/48597469#%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE">参考文献</a>

贝叶斯分类法是基于贝叶斯定定理的统计学分类方法。它通过预测一个给定的元组属于一个特定类的概率，来进行分类。朴素贝叶斯分类法假定一个属性值在给定类的影响独立于其他属性的 —— 类条件独立性。

优点 

所需估计的参数少，对于缺失数据不敏感。

缺点 

假设属性之间相互独立，这往往并不成立。（喜欢吃番茄、鸡蛋，却不喜欢吃番茄炒蛋）。

需要知道先验概率。

分类决策错误率。

朴素贝叶斯求解： 

P(C|F1,...,Fn)=p(C)p(F1,...,Fn|C)p(F1,...,Fn)=p(C)∏i=1np(Fi|C)

在决策树算法中，ID3基于信息增益作为属性选择的度量，C4.5基于信息增益比作为属性选择的度量，CART基于基尼指数作为属性选择的度量。

1

不需要任何领域知识或参数假设。

适合高维数据。

简单易于理解。

短时间内处理大量数据，得到可行且效果较好的结果。

对于各类别样本数量不一致数据，信息增益偏向于那些具有更多数值的特征。

易于过拟合。

忽略属性之间的相关性。

不支持在线学习

熵： 

Entropy(S)=−∑pilogpi

信息增益： 

Entropy(S,A)=Entropy(S)−∑v∈V(A)|Sv||S|Entropy(Sv)

分裂信息： 

SplitInfoR=−∑j=1k|Dj||D|log2|Dj||D|

增益比率： 

GainRatio(R)=Gain(R)SplitInfoR(D)

基尼指数： 

Gini(S)=1−∑imp2i

支持向量机把分类问题转化为寻找分类平面的问题，并通过最大化分类边界点距离分类平面的距离来实现分类。

可以解决小样本下机器学习的问题。

提高泛化性能。

可以解决高维、非线性问题。超高维文本分类仍受欢迎。

避免神经网络结构选择和局部极小的问题。

缺失数据敏感。

内存消耗大，难以解释。

运行和调差略烦人。

转自研究者July: SVM的求解，先导出12||w||2，继而引入拉格朗日函数，转化为单一因子对偶变量a的求解。如此求w.b与a的等价，而求a的解法即为SMO。把求分类函数f(x)=ω∗x+b的问题转化为求w,b的最优化问题，即凸二次规划问题，妙。 

从上图我们可以看出，这条红色的线（超平面）把红色的点和蓝色的点分开了。超平面一边的点对应的y全部是-1，而另外一边全部是1。 

接着我们可以令分类函数：f(x)=ωTx+b。显然x是超平面上的点时，f(x)=0。那么我们不妨要求所有满足f(x)&lt;0的点，其对应的y等于-1，而f(x)&gt;0则对应的y=1的数据点。（我盗用了很多图。。。） 

回忆之前的目标函数： 

max1||ω||s.t.,yi(ωT+b)≥1,i=1,...,n

这个问题等价于

max1||ω||2s.t.,yi(ωT+b)≥1,i=1,...,n

很显然这是一个凸优化的问题，更具体的，它是一个二次优化问题—目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的QP（Quadratic Programming）优化包解决。但是因为这个问题的特殊性，我们还可以通过Lagrange Duality变换到对偶变量的优化问题，找到一种更加行之有效的方法求解。首先我们给每一个约束条件加上一个Lagrange mutiplier,我们可以将它们融合到目标函数中去。 L(ω,b,a)=12||ω||2−∑ni=1α(yi(wTxi+b)−1)，然后我们令θ(ω)=maxai≥0L(ω,b,a)容易验证，当某个约束条件不满足时，例如yi(wTxi+b)&lt;1，那么我们显然有θ(w)=∞。而当所有约束条件都满足时，则有θ(ω)=12||ω||2，亦即我们最初要最小化的量。那么我们现在的目标函数就变成了：minw,bθ(ω)=minω,bmaxai≥0L(ω,b,α)=p∗，并且我们有d∗≤p∗，因为最大值中最小的一个一定要大于最小值中最大的一个。总之p∗提供了一个第一个问题的最优值p∗的一个下界。在满足KKT条件时，二者相等，我们可以通过求解第二个问题来求解第一个问题。 

先让L关于ω和b最小化，我们分别把L对w和b求偏导： 

∂L∂ω=0⟹ω=∑i=1nαiyixi

∂L∂b=0⟹∑i=1nαiyi=0

再带回L得到： 

L(ω,b,a)=12∑i,j=1nαiαjyiyjxTixj−∑i,j=1nαiαjyiyjxTixj−b∑i=1nαiyi+∑i=1nαi=∑i=1nαi−12∑i,j=1nαiαjyiyjxTixj

此时我们得到关于dual variable α的优化问题： 

maxα∑ni=1αi−12∑ni,j=1αiαjyiyjxTixjs.t.,αi≥0,i=1,...,n∑ni=1αiyi=0 

这个问题存在高效的算法，不过求解过程就不在这里介绍了。对于一个数据点进行分类时，我们是把x带入到f(x)=wTx+b中，然后根据其正负号来进行类别划分的。把ω=∑ni=1αiyixi代入到f(x)=wTx+b，我们就可以得到f(x)=∑ni=1αiyi&lt;xi,x&gt;+b，这里的形式的有趣之处在于，对于新点x的检测，只需要计算它与训练数据点的内积即可。 

为什么非支持向量的α等于零呢？因为对于非支持向量来说，L(ω,b,a)=12||ω||2−∑ni=1α(yi(wTxi+b)−1)中的，(yi(wTxi+b)−1)是大于0的，而且αi又是非负的，为了满足最大化，αi必须等于0。悲剧的非支持向量就被无声的秒杀了。。。

暂无

计算量太大

对于样本分类不均衡的问题，会产生误判。

速度快。

简单易于理解，直接看到各个特征的权重。

能容易地更新模型吸收新的数据。

如果想要一个概率框架，动态调整分类阀值。

特征处理复杂。需要归一化和较多的特征工程。

hθ(x)=g(θTx)=11+e−θTx 

其中hθ(x)的值表示结果取1的概率。 

那么对于输入x的分类结果对于类别1和类别0的概率分别为： 

P(y=1|x;θ)=hθ(x) 

P(y=0|x;θ)=1−hθ(x) 

那么对于构造损失函数J，它们基于最大似然估计推到得到的： 

∑ni=1Cost(hθ(xi),yi)=−1m[∑ni=1yiloghθ(xi)+(1−yi)log(1−hθ(xi))] 

最小化上式，与最大化下式子类似： 

P(y|x;θ)=(hθ(x))y(1−hθ(x))1−y 

取似然函数： 

l(θ)=logL(θ)=∑ni=1yi(loghθ(xi)+(1−yi)log(1−hθ(xi))) 

使用梯度上升的方法，求解θ，同样如果把J(θ)取为 

−1ml(θ)，这样通过梯度下降求解梯度最小值。 

梯度下降法求最小值： 

θj:=θj−ασσθiJ(θ) 

代入后得到： 

θj:=θj−α1m∑mi=1(hθ(xi)−yi)xji 

然后θ的更新过程如下： 

θj:=θj−α1mxTE

其中E=g(A)-y。 

正则化Regularization： 

正则化是在经验风线上增加一个正则化项或者惩罚项。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化就越大。 

J(θ)=12m∑i=1n(hθ(xi)−yi)2+λ∑j=1nθ2j

λ是正则项系数。多分类时可以去样本被判定为分类概率最大的那个类。

过拟合问题 

减少feature个数

规格化

分类准确率高。

并行处理能力强。

分布式存储和学习能力强。

鲁棒性较强，不易受噪声影响。

需要大量参数（网络拓扑、阀值、阈值）。

结果难以解释。

训练时间过长。

集成学习的思路是在对新的实例进行分类的时候，把多个单分类器的结果进行某种组合，来对最终的结果进行分类。 

更好的数据往往打败更好的算法，设计好的特征大有脾益。并且如果你有一个庞大的数据集，使用某种特定的算法的性能可能并不要紧。大可以挨个分类器尝试，并且选取最好的一个。（可以多从易用性和性能考虑） 

而且从Netfliex Prize的经验教训来看，尝试各类分类器、交叉验证、集成方法往往能取得更好的结果，一般的boosting&gt;bagging&gt;single classifier。集成学习的方法主要有一下三种： 

1. 在样本上做文章，基分类器为同一个分类算法，主要有bagging和boosting。 

2. 在分类算法上做文章，即用于训练基分类器的样本相同。基分类器的算法不同。 

3. 在样本属性集上做文章，即在不同的属性上构建分类器，比较出名的是randomforest Tree的算法，这个有weka也有实现。 

1998年Jerome Friedman &amp; Trevor Hastie &amp; Robert Tibshirani发表文章Additive Logistic Regression: a Statistical View of Boosting，中提到Bagging是一个纯粹的降低相关度的方法。如果树的节点具有很高的相关性，bagging就会有很好的效果。

αm=12log1−emem，在em&lt;=1/2时，am&gt;=0，且am随着em的减小而增大。 

更新训练数据集的权值分布（目的：得到样本的新权值分布），用于下一轮迭代： 

Dm+1=(wm+1,1,wm+1,2,...wm+1,i...,wm+1,N), 

wm+1,i=wmiZmexp(−αmyiGm(xi)),i=1,2,...,N 

使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过Zm=∑Ni=1wmiexp(−αmyiGm(xi))，使得Dm+1成为一个概率分布。然后组合各个弱分类器f(x)=∑Mm=1αmGm(x)，而得到的最终分类器G(x)=sign(f(x))=sign[∑Mm=1αmGm(x)]。

随机森林指通过多颗决策树联合组成的预测模型，可以对样本或者特征取bagging。