基于 Matlab 的分类算法测试研究
2018 年 12 月 1 日
目录
一、 分类算法介绍..................................................................................................... 3
1.1
SVM 支持向量机算法.................................................................................3
1.2 朴素贝叶斯分类算法................................................................................. 3
1.3
KNN 法......................................................................................................... 4
1.4 决策树......................................................................................................... 4
1.5 向量空间模型(Vector Space Model)法...................................................... 5
二、 UCI 数据集的准备...............................................................................................6
三、 分类算法原理与代码......................................................................................... 6
3.1 SVM 算法原理与代码...................................................................................6
3.2 朴素贝叶斯................................................................................................... 7
3.3 K 最近邻法.................................................................................................... 8
四、 实验结果分析与对比......................................................................................... 9
一、分类算法介绍
1.1
SVM 支持向量机算法
支持向量机(Support Vector Machine,SVM)是 Corinna Cortes 和 Vapnik 等于 1995 年首先
提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应
用到函数拟合等其他机器学习问题中。在机器学习中,支持向量机(SVM,还支持矢量网络)
是与相关的学习算法有关的监督学习模型,可以分析数据,识别模式,用于分类和回归分析。
支持向量机的目的是寻找一个超平面来对样本进行分割,分割的原则是间隔最大化,最
终转化为一个凸二次规划问题来求解。由简至繁的模型包括:
1 当训练样本线性可分时,通过硬间隔最大化,学习一个线性可分支持向量机;
2 当训练样本近似线性可分时,通过软间隔最大化,学习一个线性支持向量机;
3 当训练样本线性不可分时,通过核技巧和软间隔最大化,学习一个非线性支持向量
机;
SVM 在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目
前最常用,效果最好的分类器之一,在于其优秀的泛化能力,这是是因为其本身的优化目标
是结构化风险最小,而不是经验风险最小,通过 margin 的概念,得到对数据分布的结构化
描述,因此减低了对数据规模和数据分布的要求。
1.2 朴素贝叶斯分类算法
贝叶斯分类算法是统计学的一种分类方法,它是一类利用概率统计知识进行分类的算
法。在许多场合,朴素贝叶斯(Naïve Bayes,NB)分类算法可以与决策树和神经网络分类算法
相媲美,该算法能运用到大型数据库中,而且方法简单、分类准确率高、速度快。
Bayes 法是一种在已知先验概率与类条件概率的情况下的模式分类方法,待分样本的
分类结果取决于各类域中样本的全体。
设训练样本集分为 M 类,记为 C={c1,…,ci,…cM},每类的先验概率为 P(ci),i=1,
2,…,M。当样本集非常大时,可以认为 P(ci)=ci 类样本数/总样本数。对于一个待分样本 X,
其归于 cj 类的类条件概率是 P(X/ci),则根据 Bayes 定理,可得到 cj 类的后验概率 P(ci/X):
P(ci/x)=P(x/ci)·P(ci)/P(x)(1), 若 P(ci/X)=MaxjP(cj/X),i=1,2,…,M,j=1,2,…,M,则
有 x∈ci(2),式(2)是最大后验概率判决准则,将式(1)代入式(2),则有: 若 P(x/ci)P(ci)=Maxj
[P(x/cj)P(cj)],i=1,2,…,M,j=1,2,…,M,则 x∈ci。这就是常用到的 Bayes 分类判
决准则。经过长期的研究,Bayes 分类方法在理论上论证得比较充分,在应用上也是非常广
泛的。
Bayes 方法的薄弱环节在于实际情况下,类别总体的概率分布和各类样本的概率分布函
数(或密度函数)常常是不知道的。为了获得它们,就要求样本足够大。另外,Bayes 法要求
表达文本的主题词相互独立,这样的条件在实际文本中一般很难满足,因此该方法往往在效
果上难以达到理论上的最大值。
1.3
KNN 法
KNN 法即 K 最近邻法,最初由 Cover 和 Hart 于 1968 年提出的,是一个理论上比较成熟
的方法。该方法的思路非常简单直观:如果一个样本在特征空间中的 k 个最相似(即特征空
间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。该方法在定类
决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN 方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本
有关。因此,采用这种方法可以较好地避免样本的不平衡问题。另外,由于 KNN 方法主要
靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交
叉或重叠较多的待分样本集来说,KNN 方法较其他方法更为适合。
该方法的不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样
本的距离,才能求得它的 K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,
事先去除对分类作用不大的样本。另外还有一种 Reverse KNN 法,能降低 KNN 算法的计算复
杂度,提高分类的效率。
该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用
这种算法比较容易产生误分。
1.4 决策树
决策树算法借助于树的分支结构实现分类。下图是一个决策树的示例,树的内部结点表
示对某个属性的判断,该结点的分支是对应的判断结果;叶子结点代表一个类标。
决策树算法的好处在于,它可以产生人能直接理解的规则,这是贝叶斯、神经网络等算
法没有的特性;决策树的准确率也比较高,而且不需要了解背景知识就可以进行分类,是一
个非常有效的算法。
算法:GenerateDecisionTree(D,attributeList)根据训练数据记录 D 生成一棵决策树.
输入:
数据记录 D,包含类标的训练数据集;
属性列表 attributeList,候选属性集,用于在内部结点中作判断的属性.
属性选择方法 AttributeSelectionMethod(),选择最佳分类属性的方法.
输出:一棵决策树.
过程:
1. 构造一个节点 N;
2. 如果数据记录 D 中的所有记录的类标都相同(记为 C 类):则将节点 N 作为叶子节点
标记为 C,并返回结点 N;
3. 如果属性列表为空:则将节点 N 作为叶子结点标记为 D 中类标最多的类,并返回结点 N;
4. 调用 AttributeSelectionMethod(D,attributeList)选择最佳的分裂准则 splitCriterion;
5. 将节点 N 标记为最佳分裂准则 splitCriterion;
6. 如果分裂属性取值是离散的,并且允许决策树进行多叉分裂:从属性列表中减去分裂属
性,attributeLsit -= splitAttribute;
7. 对分裂属性的每一个取值 j:记 D 中满足 j 的记录集合为 Dj;如果 Dj 为空:则新建一个叶
子结点 F,标记为 D 中类标最多的类,并且把结点 F 挂在 N 下;
8. 否则:递归调用 GenerateDecisionTree(Dj,attributeList)得到子树结点 Nj,将 Nj 挂在 N 下;
返回结点 N;
1.5 向量空间模型(Vector Space Model)法
VSM 法即向量空间模型(Vector Space Model)法,由 Salton 等人于 60 年代末提出。这是
最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量:
D=D(T1,W1;T2,W2;…;Tn,Wn),然后通过计算文本相似度的方法来确定待分样本的
类别。当文本被表示为空间向量模型的时候,文本的相似度就可以借助特征向量之间的内积
来表示。
在实际应用中,VSM 法一般事先依据语料库中的训练样本和分类体系建立类别向量空
间。当需要对一篇待分样本进行分类的时候,只需要计算待分样本和每一个类别向量的相似
度即内积,然后选取相似度最大的类别作为该待分样本所对应的类别。
由于 VSM 法中需要事先计算类别的空间向量,而该空间向量的建立又很大程度的依赖
于该类别向量中所包含的特征项。根据研究发现,类别中所包含的非零特征项越多,其包含
的每个特征项对于类别的表达能力越弱。因此,VSM 法相对其他分类方法而言,更适合于
专业文献的分类。
二、UCI 数据集的准备
本次实验选择的 UCI 数据集包括以下 5 个,数据集中英文单词都换成用数字代替:
1
2
3
4
5
Blood Transfusion Service Center
Banknote authentication
Haberman’s Survival
BLOGGER
Phishing website
三、分类算法原理与代码
本次实验基于 matlab,使用十折交叉验证,使用混淆矩阵算出 F1 指标,并求平均值,
代码如下:
3.1 SVM 算法原理与代码
data=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_data.xls','A1:D800');
labels=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_label.xlsx','A1:A800');
[m,n]=size(data);%获取数据矩阵大小
F1_AVERAGE=0;
indices=crossvalind('Kfold',data(1:m,n),10); %K 折交叉验证
for i=1:10
test_indic = (indices == i);
train_indic = ~test_indic;
train_datas = data(train_indic,:);%找出训练数据与标签
train_labels = labels(train_indic,:);
test_datas = data(test_indic,:);%找出测试数据与标签
test_labels = labels(test_indic,:);
classifer = fitcsvm(train_datas,train_labels);%训练模型
predict_label
= predict(classifer, test_datas);%模型预测结果
c=confusionmat(test_labels,predict_label) %通过测试标签和预测标签来计算混淆矩阵以求 F1
指标
Accuracy=(c(1,1)+c(2,2))/(c(1,1)+c(1,2)+c(2,1)+c(2,2))%正确率
Recall=c(1,1)/(c(1,1)+c(1,2))%召回率
Precision=c(1,1)/(c(1,1)+c(2,1))%查准率
F1=2*Precision*Recall/(Precision+Recall)%计算 F1 指标
F1_AVERAGE=
F1_AVERAGE + F1;
end
F1_average =F1_AVERAGE / 10;%F1 指标求平均
disp('平均 F1 指标:');
disp( F1_average);
3.2 朴素贝叶斯
data=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_data.xls');
labels=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_label.xlsx',);
[m,n]=size(data);%获取数据矩阵大小
F1_AVERAGE=0;
indices=crossvalind('Kfold',data(1:m,n),10); %K 折交叉验证
for i=1:10
test_indic = (indices == i);
train_indic = ~test_indic;
train_datas = data(train_indic,:);%找出训练数据与标签
train_labels = labels(train_indic,:);
test_datas = data(test_indic,:);%找出测试数据与标签
test_labels = labels(test_indic,:);
classifer =NaiveBayes.fit (train_datas,train_labels);%朴素贝叶斯训练模型
predict_label
= predict(classifer, test_datas);%模型预测结果
c=confusionmat(test_labels,predict_label) %通过测试标签和预测标签来计算混淆矩阵以求 F1
指标
Accuracy=(c(1,1)+c(2,2))/(c(1,1)+c(1,2)+c(2,1)+c(2,2))%正确率
Recall=c(1,1)/(c(1,1)+c(1,2))%召回率
Precision=c(1,1)/(c(1,1)+c(2,1))%查准率
F1=2*Precision*Recall/(Precision+Recall)%计算 F1 指标
F1_AVERAGE=
F1_AVERAGE + F1;
end
F1_average =F1_AVERAGE / 10;%F1 指标求平均
disp('平均 F1 指标:');
disp( F1_average);
3.3 K 最近邻法
data=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_data.xls');
labels=xlsread('C:\Users\j\Desktop\学习\数据挖掘\UCI_DATA\blood_label.xlsx');
[m,n]=size(data);%获取数据矩阵大小
F1_AVERAGE=0;
indices=crossvalind('Kfold',data(1:m,n),10); %K 折交叉验证
for i=1:10
test_indic = (indices == i);
train_indic = ~test_indic;
train_datas = data(train_indic,:);%找出训练数据与标签
train_labels = labels(train_indic,:);
test_datas = data(test_indic,:);%找出测试数据与标签