分类器学习(kNN&决策树&SVM&Adaboost)

MachineLearning

---

kNN

kNN的工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算饭提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是kNN算法中k的出处，通常k是不大于20的整数（在本算法中k=5）。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

决策树

单层决策树为一个二分类器。针对多分类问题，算法的基本思想是首先利用使用“一对一”的方法将多分类问题分解为多个二分类问题，每个二分类器利用单层决策树实现。
如针对iris数据库的三分类问题可分解为3个二分类问题——1 vs 2, 2 vs 3, 3 vs 1。分别对每个二分类器进行训练。训练结束后进行测试时，每个二分类器都对其类别进行判断，并为相应的类别“投上一票”，最后得票最多的类即作为该测试样本的预测类别。
当所有类别的得票数目相同时，随机采用任意一个二分类器的分类结果，本算法中采用1vs2决策树的分类结果。

SVM

算法的基本思想是首先利用使用“一对一”的方法将多分类问题分解为多个二分类问题，利用SVM实现每个二分类器 。
如针对iris数据库的三分类问题可分解为3个二分类问题——1 vs 2, 2 vs 3, 3 vs 1。分别对每个SVM二分类器利用SMO算法进行训练。训练结束后进行测试时，每个二分类器都对其类别进行判断，并为相应的类别“投上一票”，最后得票最多的类即作为该测试样本的预测类别。
当所有类别的得票数目相同时，随机采用任意一个二分类器的分类结果，本算法中采用1vs2的SVM二分类器的分类结果。
三个二分类器的训练集分别保存在./data目录下1_2.txt, 2_3.txt和3_1.txt三个文件中。
关于SVM以及SMO算法的原理可参见博客园—JerryLead的博客。

Adaboost

同多分类决策树一样，首先将利用“一对一”方法将多分类问题转化为多个二分类问题，如iris中的三分类可转化为3个二分类问题——1 vs 2, 2 vs 3, 3 vs 1。
每个二分类基于单层决策树实现，在训练的时候采用Adaboost算法，训练过程如下：赋予训练数据中的每个样本一个权值，这些权值构成向量D。一开始这些权值都被初始化为相同的值，首先在训练数据上构建一个弱分类器，计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练中，将会调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本权重将会提高。为了从所有弱分类器中得到最终的分类结果，Adaboost为每个分类器都分配了一个权重值alpha，这些值是基于每个弱分类的错误率进行计算的。其中错误率的定义为：

$$\varepsilon = \frac{未正确分类的样本数目}{所有样本数目}$$
而alpha的计算公式如下：
$$\alpha = \frac{1}{2}ln(\frac{1-\varepsilon}{\varepsilon})$$
计算出alpha值之后，可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高。D的计算方法如下。
如果某个样本被正确分类，那么该样本的权重更改为：
$$D_u^{(i+1)} = \frac{D_i^{(t)} e^{-\alpha}}{Sum(D)}$$
而如果某个样本被错分，那么该样本的权重更改为：
$$D_u^{(i+1)} = \frac{D_i^{(t)} e^{\alpha}}{Sum(D)}$$
在计算出D之后，Adaboost又开始进入下一轮迭代。Adaboost算法会不断地重复训练和调整权重的过程，直到错误率为0或者弱分类器的数目达到用户的指定值为止。
在训练好每个二分类器之后，采用投票的进行多分类类，即每个二分类器都对其类别进行判断，并为相应的类别“投上一票”，最后得票最多的类即作为该测试样本的预测类别。
当所有类别的得票数目相同时，随机采用任意一个二分类器的分类结果，本算法中采用1vs2决策树的分类结果。

不同分类器的比较

参见博客常见机器学习算法思想梳理，正确应用机器学习以及Choosing a Machine Learning Classifier

附录

• knn与k-means的区别

knn	kmeans
分类算法	聚类算法
监督学习	非监督学习
数据集带label，是经过标定的数据	数据集无label,杂乱无章，经聚类后变得有序
没有明显的前期训练过程，memory-based learning	有明显的前期训练过程（找到聚类中心）
k的含义：新来一个样本x，要进行分类给它一个标签y，就从数据集中找到离它最近的k个数据点。在这个k个数据点中，类别c占的个数比较多，就把x的label设为c	k的含义：k是人工固定好的数据，假设数据集合可以分为k个簇（不一定准备，需经过交叉验证）。由于是依靠人工设定，所以需要一点先验知识

相似点：都包含这样的过程：给定一个店，在数据集中找到离它最近的n个点。即两者都用到了NN（Nears Neighbor）算法。

• 正则化

  1. 模型选择的典型方法是正则化。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项(regularizer)或惩罚项(penalty term)。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化项就越大；
  2. 正则化的作用是选择经验风险最小和模型复杂度同时较小的模型；从贝叶斯估计的角度来看，正则化项对应于模型的先验概率。

• 数据预处理
  参见博客ufldl-数据预处理以及关于数据预处理的技巧