一、目的和要求
1.编程实现SVM训练函数和预测函数;
2.绘制线性和非线性边界;
3.编写线性核函数
二、算法
1.线性svm:
分离超平面:w·x+b=0,对于线性可分的数据集来说,这样的超平面有无穷多个(即感知机),但是几何间隔最大的分离超平面却是唯一的
输入:训练数据集 其中, , ;
输出:分离超平面和分类决策函数
(1)选择惩罚参数C>0,构造并求解凸二次规划问题
(2)计算
(3)求分离超平面
分类决策函数:
2.非线性svm:
输入:训练数据集 其中, , ;
输出:分离超平面和分类决策函数
(1)选取适当的核函数 [公式] 和惩罚参数 [公式] ,构造并求解凸二次规划问题
(2)计算
(3)分类决策函数:
三、过程记录
1.数据集1可视化
导入数据集1的数据,包括特征和类标,在绘图函数中完成如下代码可以实现:
分别将两种类标数据提取出来进行绘制,结果如下:
图1 数据集1样本点分布
2.svm训练
通过svmtrain函数对数据进行训练,初始设定C的值为1,训练完成后绘制通过visualizeBoundaryLinear函数绘制决策边界,结果如下:
图2 C=1时决策边界
从图中可以看出其中有一个正样本数据被分为了负样本,此时继续改变C的值来进行探究
图3 C=10时决策边界
图4 C=50 决策边界
图5 C=100 时决策边界
可以发现此时所有样本均分类正确
3.高斯核
通过公式编写高斯核函数来计算相应的高斯内核,函数内代码如下,x1,x2是两个数据,sigma为参数
接下来设定两个示例来调用该函数进行验证,设定sigma值为2
打印出的结果为0.324652
4.可视化数据集2
图6 数据集2样本点分布
5.对数据集2进行svmtrain训练,设定C=1,加入高斯核函数,设定sigma=0.1,训练完成后绘制的边界如下:
图7 C=1 sigma=0.1决策边界
可以发现此时边界基本能区分两类样本了。改变C和sigma的值进行相应实验:
图8 C=1 sigma=0.2决策边界
图9 C=50 sigma=0.1 决策边界
6.可视化数据集3
图10 数据集3样本点分布
7.寻找最佳C和sigma值,绘制决策边界
在dataset3Params函数中尝试不同的C的sigma值对并求出对应的交叉验证集的错误率,然后找到最小错误率所对应的C和sigma值,代码如下:
C和sigma的值都有八种选择,因此一共可以产生64中错误率结果,然后通过内置函数ind2sub找到最小值下表,最终结果如下:
图11 错误率及最终寻找结果
再将得到的最佳参数值代入训练中,得到的判别边界如下:
图12 决策边界
可以看出此时已经能够正确分类大部分的样本点了。
接下来进行垃圾邮件分类
8.电子邮件预处理和规范化
首先需要读取邮件,通过内置fopen函数打开数据集文件,然后使用fscanf将其中内容读取
处理包括以下几种:将邮件转换为小写、删除HTML标签、URL替换为文本“httpaddr”、电子邮件地址替换为文本“emailaddr”、将所有数字转换为文本“number”、将所有美元符号$替换为文本“dollar”、单词简化为词根形式、删除非单词和标点符号、所有的制表符、换行符、空格都被裁剪为一个空格字符。处理后结果如下:
图13 邮件处理后结果
9.建立电子邮件中的词所对应的单词表中的词汇的映射
通过字符串比较函数strcmp将处理后的邮件中的单词与词汇表中的单词一一比较,如果有相同的则将词汇表当前的索引记录下来:
最终得到的部分索引值如下:
10.从电子邮件中提取特征
在大小为1899的特征向量中,若词汇表中的单词存在于邮件中则将数组中为该单词对应的索引部分的值置为1,否则为0,然后统计非0值的个数。结果如下:
图14 特征提取结果
通过之前的实验可知在第一个邮件数据集中在处理过后一共有53个单词可以与词汇表所对应,但是此处只能提取45个,经过分析得知这是由于53个单词中有重复的单词,而45指的是词汇表中不同单词所能够映射到邮件中的个数。
11.svm垃圾邮件训练
加载已有的训练集文件,文件包括X(垃圾和非垃圾邮件实例),y(所属类别,1代表垃圾邮件,0代表非垃圾邮件)
初始设定C的值为0.1,训练后再进行预测计算出训练集和测试集的准确率
图15 训练集准确率
再继续对测试集数据进行预测,结果如下
图16 测试集准确率
12.寻找垃圾邮件主要预测的因素
将分类器模型中不同索引值的权重值进行排序,然后在词汇表中找到对应的单词,查看影响预测因素最大的前15个单词
图17 主要预测因素及其对应的权值
13.对不同邮件数据集进行处理并分类
读入一封已知的垃圾邮件进行同样的处理并且使用上述实验中已经得到的分类器进行分类预测
结果如下:
图18 原文
图19 处理后邮件
图20 分类结果
可知分类器对该邮件的预测为垃圾邮件,由已知条件可知分类正确
读入非垃圾邮件emailSample2.txt进行同样的操作,结果如下:
图21 处理后的邮件
图22分类结果
分类正确
结果验证该分类器可以正确分类示例中的垃圾和非垃圾邮件
四、结果分析
本次实验我们首先通过svm对各种示例2D数据集进行分类实验,第一个数据集可以通过线性边界分割开,但是在开始设定的惩罚因子C的值时依然会有错误分类,通过多次探究如图2到图5所示,将C的值调大后SVM越不会放弃那些离群点,并且趋于尝试正确分类所有的例子,但是过大也有可能会造成过拟合。对于线性不可分的数据集,需要加入高斯核来找到非线性决策边界,高斯核中的sigma参数对于结果也有影响,若过高则可能会欠拟合,若过低,可能训练准确率会很高但会过拟合,所以如果发现准确率低我们可以尝试调大C的值调小sigma的值。而在第三个数据集中,我们通过程序自动取寻找合适的C和sigma值,通过交叉集进行验证,以最小错误率为标准最终得出了最佳的结果如图12所示。
在垃圾邮件分类的实验中,我们通过对邮件进行处理从而方便特征的提取,通过与词汇表建立映射从而将字母等信息转换为更加适合处理的数字信息,通过训练后得到的分类器对于训练集及测试集的准确率都很高如图15与图16所示。分类器中也可以查看相应的参数,从而得知垃圾邮件的主要预测因素如图17所示,最后我对于其它的一些邮件示例进行预测发现结果均正确,由此可见该分类器模型预测效果不错。