[关闭]
@hshustc 2015-09-21T13:51:10.000000Z 字数 2411 阅读 11624

分类器学习(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,这些值是基于每个弱分类的错误率进行计算的。其中错误率的定义为:

ε=

而alpha的计算公式如下:
α=12ln(1εε)

计算出alpha值之后,可以对权重向量D进行更新,以使得那些正确分类的样本的权重降低而错分样本的权重升高。D的计算方法如下。
如果某个样本被正确分类,那么该样本的权重更改为:
D(i+1)u=D(t)ieαSum(D)

而如果某个样本被错分,那么该样本的权重更改为:
D(i+1)u=D(t)ieαSum(D)

在计算出D之后,Adaboost又开始进入下一轮迭代。Adaboost算法会不断地重复训练和调整权重的过程,直到错误率为0或者弱分类器的数目达到用户的指定值为止。
在训练好每个二分类器之后,采用投票的进行多分类类,即每个二分类器都对其类别进行判断,并为相应的类别“投上一票”,最后得票最多的类即作为该测试样本的预测类别。
当所有类别的得票数目相同时,随机采用任意一个二分类器的分类结果,本算法中采用1vs2决策树的分类结果。

不同分类器的比较

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

附录

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

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注