分类算法汇总(一)

k-近邻,决策树,贝叶斯分类,Logistic,SVM

>> k-近邻(kNN)

kNN算法采用测量不同特征值之间距离的方法进行分类。

算法原理

存在一个样本数据集，每个数据都有标签。当输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，通常k不大于20。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

基本步骤

1.计算已知类别数据集中的点与输入点之间的距离(对于特征之间数值量级差异较大的点，需要进行归一化操作)
这里将特征值转化到0到1区间
newValue = (oldValue-min)/(max-min)
2.按照距离递增次序排序
3.选取与当前点距离最小的k个点
4.确定前k个点所在类别的出现频率
5.返回前k个点出现频率最高的类别作为输入点的预测分类

优缺点

优点:精度高、对异常值不敏感、无数据输入假定
缺点:无法给出数据的内在含义、计算复杂度高、空间复杂度高

>> 决策树

决策树是一种树型结构，内部节点表示一个特征，分支代表一个判断结果的输出，叶节点表示一种类别
决策树的生成算法有ID3,C4.5和CART等

ID3算法

ID3 (Iterative Dichotomiser 3)迭代二分器算法

基本思想

采用自顶向下的递归方法，以信息熵为度量，用于决策树结点的属性选择,每次优先选取信息增益最大的属性,即能使熵值最小的属性,构造一棵熵值下降最快的决策树。到叶子结点的熵值为0,此时对应实例集中的实例属于同一类别。

熵与信息增益

熵定义为信息期望值，为了计算所有类别所有可能值包含的信息期望值，通过下面公式得到

信息增益(Information gain)来选取Feature作为决策树分裂的节点.特征A对训练数据集D的信息增益定义为集合D的经验熵(所谓经验熵,指的是熵是有某个数据集合估计得到的)H(D)与特征A给定条件下D的经验条件熵H(D∣A)之差,记为 g(D,A).信息增益是熵的减少值或者是数据无序度的减少.

"da"

信息增益计算如下

"da"

生成决策树具体步骤

ID3从根节点开始,计算所有可能特征的信息增益,取信息增益最大的特征作为节点的特征,
然后由特征的不同取值,建立子节点,
再对子节点递归调用以上方法,直到所有特征的信息增益都很小或者没有特征选择为止.

C4.5算法

ID3采用会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).

避免这个不足的一个度量就是不用信息增益来选择Feature,而是用信息增益比率(gain ratio),增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature,分裂信息用来衡量Feature分裂数据的广度和均匀性:

但是当某个Di的大小跟D的大小接近的时候
"da"
为了避免这样的属性,可以采用启发式的思路,只对那些信息增益比较高的属性才应用信息增益比率.

相比ID3,C4.5还能处理连续属性值,具体步骤为:
1.把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序.
2.假设该属性对应的不同的属性值一共有N个,那么总共有N−1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成bool属性.实际上可以不用检查所有N−1个分割点,具体请看下面的例子.
3.用信息增益比率选择最佳划分.

假设上面关于贷款的例子还有个属性是收入情况,对应的数据如下(已经排好序):

可以证明这时候的切分点,只能出现在目标分类不同的相邻实例之间,即出现在(48,60)和(80,90)之间,这时候选取切分点 s1=(48+60)/2=54 和 s2=(80+90)/2=85.利用s1=54就可以将收入分成小于54和大于54两类.连续属性值比较多的时候,由于需要排序和扫描,会使C4.5的性能有所下降.

C4.5还能对缺失值进行处理,处理的方式通常有三种:
1.赋上该属性最常见的值
2.丢弃有缺失值的样本
3.根据节点的样例上该属性值出现的情况赋一个概率,比如该节点上有10个样本,其中属性A的取值有6个为是,4个为否.那么对改节点上缺失的属性A,以0.6的概率设为是,0.4的概率设为否.

CART算法

CART（Classification and Regression tree）分类回归树由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。下图显示信息熵增益的一半，Gini指数，分类误差率三种评价指标非常接近。回归时使用均方差作为loss function。基尼系数的计算与信息熵增益的方式非常类似

剪枝算法

决策树算法很容易在训练数据中生成复杂的树结构，造成过拟合。剪枝可以缓解过拟合的负作用，常用方法是预剪枝与后剪枝。

预剪枝策略(Pre-pruning)

决策树生成过程中,对每个结点在划分前进行估计,若划分不能带来决策树泛化性能提升,则停止划分并将该节点设为叶结点.
这里测试泛化性能可通过计算测试样本分类的正确率判断.

后剪枝策略(Post-pruning)

先利用训练集生成决策树,自底向上对非叶结点进行考察,若将该结点对应子树替换为叶结点能带来泛化性能提升,则将该子树替换为叶结点

>> 贝叶斯分类

贝叶斯公式

p(B)为先验概率，表示每种类别分布的概率；
P(A|B)为类条件概率，表示在某种类别前提下，某事发生的概率；
P(B|A)为后验概率，表示某事发生了，并且它属于某一类别的概率，有了这个后验概率，我们就可以对样本进行分类。后验概率越大，说明某事物属于这个类别的可能性越大，我们越有理由把它归到这个类别下

基于最小错误率的贝叶斯分类:计算出后验概率后，再计算分类的错误率，选择错误率最小的那一类。
基于最小风险的贝叶斯分类:计算出后验概率后，将不同决策乘以对应决策的风险值，选择能使风险值最小的那一类。

但是在实际问题中并不都是这样幸运的，我们能获得的数据可能只有有限数目的样本数据，而先验概率和类条件概率(各类的总体分布)都是未知的。根据仅有的样本数据进行分类时，一种可行的办法是我们需要先对先验概率和类条件概率进行估计，然后再套用贝叶斯分类器。

先验概率的估计较简单，1、每个样本所属的自然状态都是已知的（有监督学习）；2、依靠经验；3、用训练样本中各类出现的频率估计。

类条件概率的估计（非常难），原因包括：概率密度函数包含了一个随机变量的全部信息；样本数据可能不多；特征向量x的维度可能很大等等。总之要直接估计类条件概率的密度函数很难。解决的办法就是，把估计完全未知的概率密度转化为估计参数。这里就将概率密度估计问题转化为参数估计问题，极大似然估计就是一种参数估计方法。