SVM分类器

2024-06-24

SVM分类器（精选八篇）

SVM分类器篇1

关键词：浮动车数据,地图匹配,历史匹配数据,支持向量机多分类器

0 引言

浮动车数据(Floating Car Data,FCD)采集技术是近几年发展起来的交通信息采集技术,能够得到城市范围的实时交通状况[1]。其中,地图匹配是FCD处理的重要步骤,直接影响对交通信息估计的准确性。由于电子地图与定位设备存在误差,车辆轨迹在电子地图上与实际道路位置产生了较大偏差。恰当的地图匹配算法能够降低车辆定位误差,使车辆标记到正确道路。

根据匹配方式的不同,地图匹配分为全局匹配和增量匹配。文献[2]中描述了一种简单搜索的点对点增量匹配方法,文献[3]中引入了基于距离和方向的匹配策略,除了位置点外没有使用其他先验知识。文献[4]中的方法建立在前点已匹配基础上,此方法会累积匹配误差。GPS误差对增量匹配算法影响大,匹配结果对于突出点敏感,从而匹配准确度较低。全局匹配算法是寻找与车辆轨迹最接近的路径,文献[4][5]使用Fréchet距离进行相似度计算,匹配准确度比增量方法高。全局匹配算法不仅算法复杂度高、计算代价大,且不能用于FCD实时匹配。

本文提出一种对全局匹配得到的匹配结果进行统计学习的方法,以实现高准确度的FCD实时增量地图匹配。论文组织如下:首先给出了SVM多类分类理论;其次结合历史匹配样本误差特征给出了特征向量的获取方法;然后基于网格划分的SVM分类策略给出了本文的地图匹配算法;最后使用合肥FCD进行了地图匹配实验,给出训练过程及结果分析。

1 SVM多分类器

支持向量机(SVM)理论适合小样本学习及结构风险最小的特性,在机器学习领域产生了很好的应用效果。SVM用于分类的思路是:通过某种非线性映射将输入向量映射到高维特征空间,然后在此空间构造最优超平面,使分类间隔最大,同时保证训练样本的误差尽可能小。

本文采用one-against-one策略解决多分类问题[9]。该方法构造k(k-1)/2个分类器,每个分类器训练多类中的两类数据。对于第i类和第j类组成的训练数据,我们要解决下述二分类问题:

构造完毕后,使用如下投票策略来对未知样本x进行类别预测:每个分类器都给出对x的预测类别,如果分类器将此样本x分到第i类,那么第i类投票加1;否则,第j类票数加1。所有分类器都统计完成后,投票数最多的类别作为样本x的预测类别。

2 FCD误差分析

FCD由大量GPS数据构成,它的误差来源于GPS定位过程。导航卫星、信号传播过程及接收设备都对定位产生误差。Diggelen、Leick等人分别对GPS定位的准确度进行了理论分析和实验验证[6,7,8]。本文在上述研究基础上,作出GPS定位误差分布假设如下:a.GPS误差(在经度、纬度、海拔的每一维度上及时间上的误差)服从高斯分布。b.在水平误差分布上,比如XY平面上的分布,等概率密度线呈圆形。

基于实际FCD匹配结果进行分析(图1),可以观察到,上下两条平行的路段上分别分布了样本。这些样本是分布在路段中心线的周围,离中心线越近,密度越高,且不同路段之间存在一定间隔。通过分析发现,匹配样本可以基于路段来进行分类,即每条FCD记录的正确匹配路段编号作为该记录的类别。

3 FCD样本的特征提取

每个样本提取出来的特征组成了一个特征向量,用于SVM的训练和分类。对于一个好的匹配结果,GPS点离待匹配路段较近。并且匹配到同一路段的不同匹配点通常都聚集在一起,在电子地图准确的情况下,路段中心线处点分布密度较大。另外,对于平行反向的两条路段,通常这两条路段在同一条主干道上,离得非常近,每条路段都有方向性,而GPS点方向角是区别匹配点属于哪条路段的有效信息。因此,对于每个FCD样本(如图2所示),特征向量为:{X,Y,D}。其中,X为经度,Y为纬度,D为方向角。方向角取值范围为[0,359],以正东方向为0度,逆时针增加。

4 基于SVM的地图匹配算法

FCD地图匹配算法流程(如图3所示)分为离线训练和实时匹配。离线部分采用全局匹配[4]得到匹配结果,每个路段会有一组匹配点样本组成。使用每个路段上的匹配结果样本离线训练SVM多分类器。实时匹配部分,将实时匹配到路段的问题看作是匹配点的分类问题,训练好的分类器对匹配点进行分类预测,类别即是匹配后的路段编号。

4.1 基于路网划分的SVM多分类器训练

随着类别数增多,SVM多分类器的训练会耗费越多时间。若以整个城市的路段作为类别,计算代价会非常大。因此,本文对路网划分成nxn网格。设地图长为L,高为H,划分为nxn份,每个网格长l=L/n,高h=H/n,设路网左上角顶点坐标P0:(x0,y0),任意GPS点坐标为p(x,y),那么p所属的网格索引号ID的计算公式:

其中floor()为取整函数,使用该公式可以将GPS点快速定位到所属网格。

网格划分后,就能以网格为单位进行SVM多分类器的训练。对于某些处于网格边缘的样本点,它的匹配路段可能在周围网格内,因此在训练时有必要进行领域网格扩充。训练算法为:从左上角网格开始,依次训练SVM多分类器。对于网格,将邻域网格所包含的路段均加入到训练过程中,使用one-against-one策略学习SVM多分类器i。图4中展示了合肥部分路网的划分情况,为了便于描述,将该部分第一块网格标为1,其他依次类推。依次从网格1开始训练分类器1,在训练多分类器6时,使用第1、2、3、5、6、7、9、10、11网格区域内的路段作为模式样本进行训练。

对于整个路网,使用网格进行划分后,每个网格区域包含路段数远小于总路段数。这样,就避免了同时训练整个路网的所有类别。与不划分网格相比,减少了分类器训练时间和计算资源。

4.2 实时地图匹配

step1得到待匹配FCD记录,其中GPS点的经度为X,纬度为Y,方向角D;

step2获取特征向量F={X,Y,D};

step3根据式(5)在常数时间内得到所属网格gk;

step4使用训练好的SVM多分类器ck,输入特征向量F,得出类别T;

step5将该点匹配为路段编号为T的路段;

5 实验与讨论

实验从合肥市FCD采集系统中选择历史数据,对本文地图匹配算法进行验证。

5.1 实验背景及参数

用于匹配的电子地图采用合肥1:2500比例的GIS地图,网格划分默认为50x50。根据FCD误差分析,分类器采用C-SVC,并使用Gauss核函数:,取核参数。

使用合肥FCD系统采集的2010.01.02 11:00:00~11:05:00数据,采样间隔10秒1次,共18848组FCD记录。使用文献[3]的基于Fréchet距离全局匹配方法得到的匹配结果训练SVM,然后用2010.01.02 11:05:00~11:10:00的人工标记过的FCD进行测试得到匹配准确率。

5.2 训练及匹配结果

高斯核SVM的两个重要参数是惩罚因子C与核函数参数γ,C的作用是调节学习器的推广能力,一般取值范围在[1,10000],γ也会影响学习性能,一般取值范围在[0.01,100]。实验首先固定γ值,对C取不同值进行实验,得出匹配准确率。匹配准确率为:匹配到正确路段上的样本数/样本总数。图5显示了准确率随C的增大而提高,在C>5000后逐渐趋向稳定。图6给出了固定C=6000时,随着核函数参数γ的增大匹配准确率的变化,发现在γ>40后准确率提升趋向水平。

表1给出了四种算法的准确率比较。其中,点到点的方法为文献[2]中的算法1,计算离GPS点最近的路段节点;点到线方法[3]考虑GPS点到各路段的距离,取最近路段作为匹配路段;考虑方向角的点到线算法[2],选择在一定距离内(本文取GPS允许误差15m)方向角与路段方向差最小的路段。本文提出的基于SVM分类匹配算法的匹配准确率较高(表1)。随后我们给出路网网格划分与运行时间、准确率的关系(图7),C和γ同表1取值。我们可以看到在测试范围内,不同网格数对准确率影响不大,但网格数越少,SVM的训练时间越长,这说明一对一的多类SVM在类别多的情况下训练复杂度明显上升。根据实验结果,选择网格划分大于50x50较合适。

6 结论

本文提出了一种新的FCD地图匹配方法,将地图匹配视为分类问题,使用SVM进行多分类学习。为了提高算法性能,减少SVM训练的计算时间,给出了一种有效可行的基于网格划分的多分类器学习策略。实验使用合肥的FCD数据,对SVM的惩罚因子和核函数参数进行调优,最后将本文匹配方法与基于几何信息和拓扑结构(点到点、点到线)的算法进行了比较,确认了较高的匹配准确率。

参考文献

[1]殷伟,郭璘,方廷健,等.一种基于FCD的城市道路车流速度估计算法[J].中国科学技术大学学报.2008,38(9):1113-1117.

[2]White C E,Bernstein D,Kornhauser A L.Some map matching algorothms for personal navigation assistants[J].Transportation Research Part C:Emerging Technologies.2000,8(1):91-108.

[3]Greenfeld J.Matching GPS observations to locations on a digital map[C].Proc.81th Annual Meeting of the Transportation Research Board,Washington,DC,2002.

[4]Brakatsoulas S,Pfoser D,Salas R,et al.On map-matching vehicle tracking data[C]//Proc.21st VLDB Conference,2005:853-864.

[5]Wenk C,Salas R,Pfoser D.Addressing the need for map-matching speed:localizing Globalb curve-matching algorithms[C]//Proceedings of the18th International Conference on SSDBM,2006:379-388.

[6]Diggelen F van.GPS accuracy:Lies,damn lies,and statistics[J].GPS World,1998,9(1):41-45.

[7]Diggelen F van.GNSS accuracy:Lies,damn lies,and statistics[J].GPS World,2007,18(1):Cover Article.

[8]Leick A.GPS Satellite Surveying[M].John Wiley&Sons,Inc.1995.

SVM分类器篇2

[关键词]决策树支持向量机科技文献分类

1、引言

随着在线电子信息以几何级数的形式增长，截止2008年7月26日，Google搜索引擎建立索引的网页数量已经达到了一万亿幅。这些海量的信息来自不同行业，比如新闻资讯、娱乐消息、研究论文、数字图书馆等。为了适应因特网快速发展的需要，许多过去以印刷形式发行的报纸期刊也纷纷将自己的刊物搬到了因特网上，尤其是科技期刊的电子化和数字化图书馆的出现极大地丰富了网络空间的知识资源。研究如何实现电子科技文献的面向主题的自动获取、自动分类是Web资源开发与利用、实现个性化服务的一个很有意义的课题，其中一个很重要的环节就是文本的自动分类。现有的文本分类算法主要有：朴素贝叶斯算法（Naive Bayes），K最近邻居分类算法（KNN），类中心向量最近距离判别算法（Rocchio），聚类粒度原理的分类算法，决策树分类算法，以及SVM分类算法等。文本分类算法是分类系统的核心，所以在实现文本自动分类系统时，文本分类算法的性能是值得注意的问题。本文试图根据科技文献的特点，建立一种基于决策树和SVM算法的文本分类器，在此基础上进行实验研究，得出实验数据并进行对比分析。

2、决策树和SVM分类算法

2.1决策树分类算法

决策树也称为判定树，决策树学习是以示例学习为基础的归纳推理算法，着眼于从一组无次序、无规则的事例中推出决策树表示形式的规则。决策树归纳方法是目前许多基于规则进行归纳数据挖掘商用系统的基础，它在分类、预测和规则提取等领域运用最为广泛。到目前为止决策树有很多实现算法，1986年由J.R.Quinlan提出的ID3算法和1993年提出的C4.5算法，以及CART，C5.0（C4.5的商业版本），Fuzzy C4.5，SLIQ和SPRINT等算法[2-4]。

决策树学习算法是一种归纳算法，它采用“自顶向下、分而治之”的方法将搜索空间分为若干个互不相交的子集，通常用来形成分类器和预测模型，可以对未知数据进行分类、预测和数据预处理等。应用这种方法需要首先构建一棵决策树对分类过程进行建模，一旦建好了树的模型之后，就可以将其应用于数据集中的元组中去，并得到分类结果。图1就是一棵决策树的示意结构描述。在图上，每个非叶子结点代表训练集数据的输入属性，Attribute Value代表属性对应的值，叶子结点代表目标类别属性的值。其中，树的中间结点通常用矩形表示，而叶子结点常用椭圆表示。图中的“是”，”否”分别代表实例集中的正例和反例[5]。

2.2 SVM分类算法

SVM（Support Vector Machine，支持向量机）方法是由V.Vapnik与其领导的贝尔实验室的小组一起开发出来的一种机器学习技术。支持向量机（SVM）是一种在统计学习理论（SLT）的基础上发展起来的一种机器学习方法。支持向量机在模式识别已经有了一些应用，如手写体数字识别[12]，人脸识别与人脸检测[13]，以及文本分类[14，15]等各种领域。此外，支持向量机还很好地应用于时间序列分析和回归分析等领域的研究。例如，MIT、Bell Lab和微软研究所等已成功地将支持向量机应用于动态图像的人脸跟踪，信号处理，语音识别，图像分类和控制系统等诸多领域。如果一个训练集中的矢量能被一个平面无错误地线性分割，且距该平面最近的矢量之间的距离最大，则称该平面为最佳分类面。

3、基于决策树和SVM的科技文献分类系统设计

3.1科技文献行文规范特点

由于科技文献特有的行文规范，它的格式和行文都有一定的特点。科技文献一般由标题、作者、作者单位、刊物名称、关键词、摘要、正文以及参考文献等几部分组成。标题、关键词和摘要部分很精简的反映了文章的核心内容，同时与文档主题内容不相关的描述很少，以这些内容作为文献的分类标准能体现出文本特征的区分性，降低噪声信息。另一方面，科技文献的关键词是经过作者认真筛选、提炼出来的能够反映文档主题内容的核心词汇。如果收集待分类的类别在一定时间内、不同期刊科技文献的关键词作为文本分类词条集合，在此基础上建立同义词、蕴含词、近义词表，并以此作为文本分类的特征，将会在很大程度上降低非专业词汇科技文本分类的噪声干扰，直接利用关键词集扫描统计专业文本的词频，无需进行词条的切分处理。

3.2科技文献分类系统设计

本文采用的是基于机器学习的文本分类技术，首先是构建一个计算机领域的语料库。语料库共分成人工智能、数据库、神经网络、模糊控制和计算机网络五类。科技文献自动分类系统研究了传统文本分类技术的各个流程，对其中各个关键步骤的算法技术进行相应的分析以及对比，并针对具体应用进行了一定的改进。整个系统设计如图4所示：

预处理阶段：该系统的预处理部分包括采用中科院计算所汉语词语分析系统ICTCLAS对训练集和测试集中文本进行扫描分词，再使用lawstoplist去除停留词。特征选择阶段：从每一类文档的所有特征词中抽取那些能够反映和区分此类文档与其它类文档的特征项。决策树的经典算法C4.5R是采用基于信息增益的特征提取方法。文本的VSM表示阶段：系统采用语义空间来表示文本信息，因此必须对文本进行模型化处理。因为向量空间模型概念简单、相似计算直观易懂，因此选择VSM作为文本的表示模式。科技文献分类阶段：通过决策树（C4.5R）和支持向量机分类算法对科技文献进行分类，并将分类结果进行输出。

5、总结与展望

本文的突出特点是从实际应用入手，选择决策树的经典算法C4.5R和SVM作为分类算法，对比了两种算法在特定应用领域（即科技文献分类领域）中文本的分类性能，得出了实验结果，并给出了针对科技文献分类领域文本信息分类系统的设计方案和实现过程。

参考文献

[1]王强，沈永平，陈英武.支持向量机规则提取[J].国防科技大学学报，2006，28（2）：801-805.

[2]王晓东.算法设计与分析[M].北京：清华大学出版社：2003.5-10

作者简介

黄华（1982-），男，硕士生，主要研究领域为数据挖掘，机器学习，文本分类。

SVM分类器篇3

分类方法已经被广泛应用在预测领域,但大多数的分类方法都要求各种类型的数据具有较为均匀的分布。若一种类型的数据与另一种类型的数据严重不均衡,少数类数据就有可能被当作噪声处理掉。现实世界中的数据集却往往呈现不均衡分布的特点,即其中一种类型的数据占绝大多数,另一种类型的数据只有为数不多的几个样本。然而,在一些特殊的情况下这些少数类样本却是人们更加关注的。例如,医生需要关注罕见疾病的诊断,银行信用卡中心需要辨别少数欺诈用户,电信运营商需要辨别少数缺乏信用恶意欠费的用户等等。

由于数量上的严重偏斜,运用常见的分类算法对非平衡数据集进行分类的性能不尽如人意,因为当对非平衡数据集进行训练时,其训练算法通常对多数类样本会产生很高的预测准确率,但是对少数类样本的预测准确性却很差。解决非均衡数据集分类难题的途径,可以粗略地分为两个方向: 一个方向是对数据进行采样处理; 另一个方向是算法设计。数据采样处理又进一步分为两种方法:一种是减少多数法(under-sampling),即减少多数类样本的数量[1,2]; 另一种是增加少数法(over-sampling),即通过复制或插值等方法增加少数类样本的数量[3]。算法设计则主要以线性Logistic回归(LLReg)、决策树(DT)、多层感知器神经网络(NN)、贝叶斯网络(Bnet)、多项Logistic回归、支持向量机(SVM)以和AdaBoost推进算法等为基础,适当予以修正,以尽量适应数据不均衡的特征[4]。

近年来,机器学习领域的一个重要进展是集成的办法,即通过集成多个精度不是很高的分类器来提高整体分类预测的精度。目前,主要运用Boosting和Bagging两种技术构建集成分类器。AdaBoost是一种最常见的Boosting方法, 在每次迭代中, 增加没有正确分类样本的权值, 减少正确分类样本的权值,更加关注于分类错误的样本。因少数类样本更容易被错误分类, 所以有理由相信该方法能够改进对少数类的预测性能。SMOTE技术(synthetic minority over-sampling technique)是非均衡数据集学习的一种新办法, 通过对少数类样本的人工合成提高少数类样本的比例, 降低数据的过度偏斜。SMOTE技术与AdaBoost结合,可有效避免由于赋予少数类样本更大权值而可能产生的过度拟合。SVM具有较强的泛化能力,以RBF为核参数的SVM,只需选择C和σ两个参数,并且选择一个大体合适的C后,通过调节σ,即可改善向量机的性能。

本文将以SVM作为弱分类器,并将SMOTE技术嵌入AdaBoost算法中, 建立非均衡数据集分类模型。研究结果表明:SMOTEBoostSVM集成分类器比单纯运用SMOTE技术、AdaBoost算法、SVM等的分类器,在非均衡数据集的分类预测中具有更好的效果。

2 算法模型

2.1 AdaBoost分类器

AdaBoost算法[5]的基本思想是通过训练一组分量分类器,将多个弱分类器集成为一个强分类器。在训练过程中,每个训练样本被赋予一个初始权值,当一个弱分类器训练完成后,根据其在训练集上的分类结果对所有的样本权值进行调整,使得下一次训练的弱分类器更关注那些被识别错误的样本。最后的强分类器的判决结果是所有弱分类器判决结果的加权和。AdaBoost算法的基本流程为:

(1)输入:标定的训练样本集,(x1,y1),(x2,y2),…,(xm,ym),其中:xi∈X,yi∈Y={-1,+1};

(2)对样本权值进行初始化,w1(i)=1/m;

(3)循环t=1,2,…,T;

①在加权训练样本集上用弱学习算法训练弱分类器Ct得到ht,或训练使用按照wt(i)采样的弱分类器Ct得到ht;

②计算Ct的训练误差εt: $ε_{t} = \sum_{h_{t} (x_{i}) \neq y_{i}} w_{t} (i)$ ;

③求弱分类器Ct的权值: $α_{t} = \frac{1}{2} \ln \frac{1 - ε_{t}}{ε_{t}}$ ;

④更新训练样本的权值:

$w_{t + 1} = \frac{w_{t} (i) \exp (α_{t} y_{i} h_{i} (x_{i}))}{Ζ_{t}} = \frac{w_{t} (i)}{Ζ_{t}} \cdot {\begin{cases} e^{- α_{t}}, \\ e^{α_{t}}, \end{cases} \begin{array}{l} h_{t} (x_{i}) = y_{i} \\ h_{t} (x_{i}) \neq y \end{array}$

其中:Zt为归一化因子,即 $Ζ_{t} = \sum_{i} w_{t} (i) e^{- α_{t} y_{i} h_{t} (x_{i})}$ 。

(4)输出:最后的强分器 $Η (x) = s i g n (\sum_{t = 1}^{Τ} α_{t} h_{t} (x))$ 。

2.2 SMOTE增加少数样本法

增加少数样本法是通过增加数据集中少数类样本的办法,降低类别之间分布的不平衡程度。早期的增加少数法是直接复制少数类样本,以增加其数量。DeRouin等通过神经网络技术, 用仿制取代复制, 以期减少少数类信息的缺失。Chawla则沿用仿制的思路, 提出了少数类信息的仿制技术SMOTE(synthetic minority over-sampling technique)[6]。

设少数类的样本数为T,增加样本后样本增长n倍,最近邻点数为k,SMOTE方法主要处理步骤如下:

(1)计算数据集中每个少数类别的k个最近多数类邻点;

(2)随机抽出少数类样本i的k个最近多数类邻点中的一个多数类样本j;

(3)计算少数类样本i与最近多数类邻点样本j的全部属性差值dif:

$d i f = n n s a m p l e [j] [a t t r] - s a m p l e [i] [a t t r]$

其中:nnsample[][]指最近的多数类邻居样本,sample[][]指少数类样本。

(4)产生一个介于0与1之间的随机数;

(5)生成少数类的合成样本Synthetic[l][attr]:

$S y n t h e t i c [l] [a t t r] = s a m p l e [i] [a t t r] + g a p \cdot d i f$

(6) 重复步骤(2)～(5),直至产生少数类样本i合成n倍个样本为止;

重复步骤(2)～(6),直至所有少数类样本均处理完毕为止。

2.3 支持向量机

支持向量机(support vector machine,SVM)是在统计学习理论基础上发展起来的新型通用分类和回归工具,较好地解决了小样本、非线性、高维数、局部极小点等实际问题,已在模式识别、信号处理、函数逼近等领域得到了较好应用,但是当应用于一种类型数据远多于另一种类型数据的非平衡数据集时,对于少数类的分析性能会急剧下降,分析其原因,主要包括:一是少数类点远离理想分界面,造成训练出的分界面向少数类偏斜;二是非平衡的支持向量比率,使得接近于边界的点更可能被归为多数类[7]。因此,要提高支持向量机对非平衡数据集的分类性能,可从平衡数据和向多数类方向推动分界面着手。

对于一个给定的训练数据集(xi,yi), i=1,2,…,n, xi∈Rd, yi∈R, 其中n为样本总数, d为R空间维数。给定一核函数K,支持向量机通过训练为每一个xi搜索最优的αi,使得分界面与最接近分界面的点之间的距离γ最大。对测试点通过式予以判别分类:

$s i g n (f (x) = \sum_{i = 1}^{n} y_{i} α_{i} Κ (x, x_{i}) + b) (1)$

其中: b为常数阈值。1-范数软边际支持向量机以最小化下列Lagrangian函数予以修正:

$\begin{array}{l} L_{p} = \frac{∥ w ∥^{2}}{2} + C \sum_{i = 1}^{n} ξ_{i} - \sum_{i = 1}^{n} α_{i} [y_{i} (w_{i} x + b - 1 + ξ_{i})] \\ - \sum_{i = 1}^{n} r_{i} ξ_{i} (2) \end{array}$

其中:αi≥0,并且ri≥0,惩罚系数C代表着误差与边际之间的一个折衷[8]。为满足KKT条件,还须满足:

$\sum_{i = 1}^{n} α_{i} y_{i} = 0 且 0 \leq α_{i} \leq C (3)$

2.4 SMOTEBoostSVM集成算法

本文提出的SMOTEBoostSVM集成算法的基本思想是:先运用SMOTE技术合成少数类样本,改善数据的偏斜状况,然后用AdaBoost算法集成多个SVM分类器,从而达到非均衡数据集上更好的分类效果与模型泛化能力。SVM常以RBF为核函数,只需确定C和σ两个参数,并且根据文献[9]可知,尽管当C值过小时,难以训练出好的RBFSVM,但当给出一个大致合适的C值后,训练效果将决定于σ.因此,本文选择RBFSVM作为弱分类器,一方面可简化模型参数的选择; 另一方面,仅调节σ,可实现AdaBoost算法在分类器分类精度与差异性之间的合理平衡。算法的具体流程如下:

(1)输入:标定的训练样本集,(x1,y1),(x2,y2),…,(xm,ym),其中:xi∈X,yi∈Y={-1,+1};RBFSVM的参数σ初始值σini,σ的最小值σmin,以及步长σstep;最大循环次数T;

(2)对样本权值进行初始化,w1(i)=1/m;

(3)当σ>σmin且t<T时循环:

① 用SMOTE算法生成N个少数类样本;

② 在加权训练样本集上用RBFSVM算法训练弱分类器Ct得到ht;

③ 计算Ct的训练误差εt: $ε_{t} = \sum_{h_{t} (x_{i}) \neq y_{i}} w_{t} (i)$ ;

④ 如果εt>0.5,令σ=σ-σstep,t=1,返回至②;

⑤ 求弱分类器Ct的权值: $α_{t} = \frac{1}{2} \ln \frac{1 - ε_{t}}{ε_{t}}$ ;

⑥ 更新训练样本的权值:

⑦ 令t=t+1。

(4)输出:最后的强分器 $Η (x) = s i g n (\sum_{t} α_{t} h_{t} (x))$ 。

3 实例分析

3.1 实验数据

本文使用2组数据对算法进行检验, 并与SVM、AdaBoost、SMOTE方法进行比较。这2组数据皆来源于UCI机器学习数据库,数据的特征信息见表1,数据集名称后的数字表示选择作为少数类的类型代码。

3.2 评估指标

评价分类器性能最直接的办法是基于混淆矩阵的分析。表2列示了二类分类问题的混淆矩阵。通过该矩阵,可能定义常用的错分率、正确率等指标,即:错分率 $E r r = \frac{B + C}{A + B + C + D}$ ,正确率 $A c c = \frac{A + D}{A + B + C + D} = 1 - E r r$ 。但是,由于非均衡数据集的特性,使用上述两个指标(实质上是一个指标)评价分类器的性能并不合适。例如,如果少数类与多数类的比率达到1∶99,那么,即使将所有未知类型的数据归为多数类,那么分类准确率即可达到99%以上,而这样的评价指标对于少数类的分类而言没有任何意义。因此,对非均衡数据集的分类通常引入以下几个指标:

少数类正确率:TP=Pr{predicted P|actually $Ρ} = \frac{A}{A + B}$

多数类正确率:TN=Pr{predicted N|actually $Ν} = \frac{D}{C + D}$

几何平均正确率: $g = \sqrt{Τ Ρ \cdot Τ Ν}$

精确率(Precision,p): $p = \frac{A}{A + C}$

召回率(Recall,r): $r = Τ Ρ = \frac{A}{A + B}$

F-measure: $f = \frac{2 p r}{p + r}$

3.3 结果评价

对Abalone数据集,以第19类作为少数类,其余类型统归为多数类,分别运用SVM、AdaBoost、SMOTE-Boost以及本文提出的SMOTEBoostSVM方法,以前3177点数据进行训练,对后1000点数据进行预测,实验结果如表3所示。

对Letter-recognition数据集,以第26类作为少数类,其余类型统归为多数类,分别运用SVM、AdaBoost、SMOTE-Boost以及本文提出的SMOTEBoostSVM方法,以前18000点数据进行训练,对后2000点数据进行预测,实验结果如表4所示。

实验结果表明:运用本文提出的SMOTEBoostSVM算法,能够在运用SMOTE技术人工合成少数类样本,以及AdaBoost算法增加分类错分样本权重,提高少数类样本预测精确性的同时,借助支持向量机的强泛化能力,能够减少、甚至可不损害对多数类的预测精度,可明显地改善非均衡数据集的分类性能。

4 结语

为解决非均衡数据集训练中易出现的偏斜问题, 提高模型的分类预测精度, 支持向量机、 SMOTE技术、 AdaBoost算法等都具有一定的效果,但目前研究方法的趋势是各种方法的集成。本文将上述几种方法加以集成,提出了SMOTEBoostSVM集成算法, 该算法集成了SMOTE技术、AdaBoost算法,并以SVM为弱分类器。实验结果表明该方法能够有效改进对非均衡数据集分类问题的预测效果。

摘要：在对实际问题进行数据挖掘时面临的多数是非均衡数据集,即各种类型的数据分布并不均匀,且关注的类型常是少数类。运用含有少量少数类型事例的数据集训练后的模型进行预测时,通常对多数类的预测精度很高,而少数类的预测精确性却很差。提出了一种集成方法SMOTEBoostSVM,通过SMOTE技术人工生成增加少数类样本量,以具有较强分类性能和泛化性能的SVM作为弱分类器,并以AdaBoost算法构建集成分类器。实验结果表明,SMOTEBoostSVM集成分类器比单纯运用SMOTE技术、AdaBoost算法以及SVM等的分类器,在非均衡数据集的分类预测中具有更好的效果。

关键词：SMOTE,AdaBoost,支持向量机,非平衡数据集

参考文献

[1]Kubat M,Holte R C,Stan M.Machine learningfor the detection of oil spills in satellite radar im-ages[J].Machine Learning,1998,30(2):195~215.

[2]Randall W D,Martinez T R.Reduction techniquesfor instance-based learning algorithms[J].MachineLearning,2000,38(3):257~286.

[3]Guo H Y,Viktor H L.Learning from imbalanceddata sets with boosting and data generation:the da-ta boost-IM approach[J].SIGKDD Explorations,2004,6(1):30~39.

[4]Daskalaki Sophia,et al.Evaluation of classifiers foran uneven class distribution problem[J].AppliedArtificial Intelligence,2006,20(5):381~417.

[5]Yoav F,et al.A short introduction to boosting[J].Journal of Japanese Society for Artificial intelli-gence,1999,14(5):771~780.

[6]Chawla N,et al.SMOTE:synthetic minority over-sampling Technique[J].Journal of Artificial Intel-ligence Research,2002,16:321~357.

[7]Wu G,Chang E Y.Class-boundary alignment forimbalanced dataset learning[A].ICML 2003 Work-shop on Learning from Imbalanced Data Sets II[C].Washington,D.C.,2003.

[8] Cristianini N, Shawe-Taylor J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge,UK:Cambridge University Press,2000.

基于SVM的网络文本分类篇4

随着互联网的飞速发展,Web的全球普及,社会生活的各个方面已经涵盖于网络信息资源中,这就引发了网络信息过载问题。人们在日常生活中不免需要这些信息,但信息的数据量过于庞大,这样往往效率极低。经研究分析,处理如此海量数据的一个重要方法就是先将它们自动分类。这样不但能够将网络文本根据类别信息分别建立相应的数据库,提高中文搜索引擎的查全率和查准率;而且可以建立自动的分类信息资源,为用户提供分类信息目录。

1 文本分类

1.1 文本分类概述

文本分类是将一个未知样本分到几个预先已知类的过程。用数学公式表示为:f:A→B。其中,A表示未标明类别的待分类的文本集合,B表示分类体系中已确定的类别集合。

1.2 文本分类预处理

1.2.1 文本分词

传统的文本分词缺点:中文分词涉及到词性标注、未定义词识别、语言特例以及分词等多个因素,大多数系统经常采用的模块组合方式是耦合法,这样缺乏统一的处理方法,不能准确有效地表达千差万别的语言现象。

本文基于中科院计算所汉语分析系统ICTCLAS,应用层叠马尔可夫模型,创新了分词算法,将中文词法分析的所有环节统一到了一个完整的理论框架中,获得最好的总体效果。优秀的ICTCLAS系统的特点是中文分词、词性标注、命名实体识别、文字识别,并支持用户词典N--最短路径算法。本文运用此系统进行文本分词,取得很好的效果,同时对切分词还进行了词性的标注、人名地名等专有名词的识别。

1.2.2 去停用词

停用词大致为如下两类:1)并不能够表征文本的语气助词、副词、介词、连接词等一些虚词;2)应用十分广泛的词,这些词没有区分类别的能力,不仅无法保证能给出真正相关的分类信息,还会降低分类的效率。

本文在网上下载一份中文的停用词表来作为去停用词的参考,若分词得到的文本词集中的词与停用词表的词匹配,表明该词为停用词,则从文本词集中删除;若不匹配,则保留。

1.2.3 传统的特征选择方法及不足之处

文本训练集经分词处理后,形成了一个原始特征词集T={t1,t2,t3,…,ti},用来表征文本类。其中i为特征词集总量。这一特征词集的维数一般都比较大,最坏情况下可能相当于抽词词典的规模。若直接采用T于后续的分类系统,无论是时间的复杂度或者空间复杂度都将无法承受,另外无法界定该特征集中各个表征词的重要性,因此需要对其进行降维处理,主要有两种途径,一是特征选择,二是特征抽取,本文对特征选择做一个简单的介绍。

特征选择指从特征集T={t1,t2,t3,…,ti} i个总量中选择一个真子集T={t1,t2,t3,…,ti}',而s'≤s(其中s为原始特征集的大小,s'为选择后的特征集大小)。通常是基于特征项对分类作用的大小而选择的,用一个统计量来度量。本文对其中的TF-IDF、IG、MI/以及CHI等四种方法及不足之处进行简单阐述。

(1)频度/逆文档频度法

该方法非常适合海量文本的特征表示,典型的是TF-IDF权值计算方法[1,2],如式1所示。

W(t,d)为词t在文本d中的权重,而tf(t,d)为词t在文本d中的词频,N为训练文本总数,nt为训练文本集中出现词t的文本数,分母为归一化因子。

该方法的缺点是:上述公式并无考虑文本的结构特点,会对特征项权重产生影响。

(2)信息增益

信息增益采用统计某个特征项在一篇文档中出现或不出现的次数来预测文档的类别。IG计算公式如式(2)。

表示一篇文档属于类别ci的概率;pr(t)表示特征项t在一篇文档内出现的概率; 表示特征项t不在一篇文档内出现的概率; 表征t在属于类别ci的文档内出现的概率; 表示特征项t不在属于类别ci的文档内出现的概率;m是文档那个类别数。

(3)互信息及其改进算法

随机变量的依赖程度是由互信息来衡量的,两个随机变量的依赖程度的大小取决于其值的高低。当特征存在负值时,互信息对分类的影响是传统的互信息算法所没有考虑的,因此削弱了这些特征在分类中的作用。本文应用改进后的互信息算法[3],通过对特征t和类c的互信息量I(t,c)取绝对值来克服以上缺陷。改进后的算法如式(3)所示。

其中,p(t)表示特征t的概率;p(t│ci)表示特征在类ci下的条件概率;p(ci)表示第i类的概率;I(t,ci)为特征t与类ci的互信息量。

(4)CHI(x2)

很多时候,特征项在类别判别的作用也会是反面作用的。若特征项t与类c反相关,则表明含有特征项t的文档不属于c的概率反而要大一些。CHI基于此原理,来计算特征项t和类c的相关性,如公式(4)。

A为t和c同时出现的次数;B为t出现而c没有出现的次数;C为c出现而t没有出现的次数;D为t和c同时没有出现的次数;N为训练集中的文档数。

1.2.4 改进的特征选择算法--权值算法

综上所述,四种方法皆存在其不足之处。在本文中的实验中,基于各种方法的优点在保证时间空间复杂度的前提下,采用“综合权值”法进行特征选择和权值计算。算法步骤:

输入:抽词结果库;

输出:投票法权值计算的特征向量库;

Step1:抽词结果库的类内词频统计;

Step2:抽词结果库的类间词频统计;

Step3:基于四种权值计算方法的各权值计算;

A)TF-IDF,生成w-value/w-value2列集合(分别存储特征权值及排序后的序号,下同),

B)MI,生成m-value/m-value2列集合,

C)CHI(x2),生成c-value/c-value2列集合,

D)IG,生成i-value/i-value2列集合,

Step4:计算序号均值,生成value/value2列集合;

Step5:根据设定阈值,生成最终向量分分类矩阵知识库。

选取训练集中的国家安全类作为样本,在SVM分类器上对频度/逆频度、信息增益、互信息的改进方法、CHI及综合权值五种特征选择算法进行对比实验,我们取维数1000,采用相同的加权函数和分词算法。实验结果如表1所示。

2 简介几种文本分类方法

在几年的发展中,研究者们提出了多种文本分类方法,下面简介一下朴素贝叶斯方法和K-近邻方法。

2.1 朴素贝叶斯方法

朴素贝叶斯分类器利用类别的先验概率和样本的数据信息来计算未知文本属于某一类别的后验概率[4]。文档Di表示为(w1,w2,…wn),(w1,w2,…wn)为特征项集,则文档Di属于Cj的概率为:

缺点:该方法是基于统计思想的一种分类,在分类过程中存在诸如分类模型对样本具有敏感性、分类精度难以提高的不足之处。

2.2 K-最邻近分类方法

KNN方法是一种基于实例的文本分类方法,它把样本表示成n维空间Rn中的点。任意样本X表示为特征向量:X=(x1,x2,…,xn),xi表示样本X的第i个属性值。给定一个未知的样本,发现训练样本集中距之最近的K个训练样本,根据训练样本,来确定未知样品的类别。对于两个样本点X=(x1,x2,…,xn),和Y=(y1,y2,…,yn),我们用欧氏距离来计算其距离:

缺点:分类速度与训练文档的个数有关,因此K需慎重选取。再者,K小则待分类文档的所有内容特征无法用选择出的相关文档来表现;K大,该算法会为待分类文档选择出一些不是很相关的文档,从而超出待分类文档的内容特征。

3 基于SVM的网络文本分类

3.1 SVM及其算法

支持向量机(SVM)是Vapnik等人根据统计学习理论中结构风险最小化原则提出的。发展至此,它不再单纯使用内积运算,而是考虑用核函数替换。在SVM算法中,少数的支持向量即可决定决策超平面,实质是求解一个带约束条件的凸二次规划问题,能够保证找到的极值解就是全局最优解[5]。

SVM方法适合文本分类这种大样本集的分类,将降维与分类结合在一起。我们假设线性分类面的形式为[6]:

其中,w为其权系数向量,b为分类阈值。令│g(D)=1│,即 …,N。yi是样本的类别标记,yi=1时,样本属于c类,yi=-1时,样本属于其他,Di是相应的样本。我们的目标是使样本的分类间隔2/‖w‖最小,由此定义Lagrange函数:

其中, 乘数,将上式对w和b分别求偏微分并令其为0,原问题转换成如下对偶问题:在约束下对 ,n下对ai求解下列函数最大值:

如果,a*i为最优解,再由公式

得出最优分类面的权系数向量。为判断某个样本是否属于C,计算如下最优分类函数:

若f(D)=1,D就属于该类;否则就不是属于该类。

基于上述分析,目前已经提出许多针对大规模样本级的SVM训练算法,有Chunking算法、分解算法、SMO算法等。大部分基于分解迭代的思想,即在每一步的迭代计算中,都要把训练数据样本集分解为两个子集合B和N,只对工作集B中的数据样本进行优化,不处理另一集合N中数据样本。

4 实验及结果分析

4.1 语料库的设计

在本文实验中,从天涯论坛摘取1200个帖子组成本文语料库来进行分类测试实验,共分为七大类:国家安全、金融经济、精神文明、日常生活、社会稳定、政府执政、资源环境。在本实验中,训练集随机选取2000个文档,测试语料选择了700个文档,且没有重叠。各个类别中进行训练和测试的文档分布如表2所示。

4.2 实验及结果

在本研究中,把Matlab7.0作为仿真软件。在训练阶段,对训练集按照上述步骤进行预处理:分词、去停用词、得到特征空间,然后选择合适的参数构造分类器,直到分类器具有较好的分类能力。在测试阶段,测试集中每个文本按相同的预处理和特征转换步骤形成新的样本矢量,输入分类器进行测试,用构造好的分类器去评估测试训练集,正确率达到88.9%,但是按上所述,这种决策策略也不一定是最好的,因为文本分类从根本上说是一个映射过程,评估分类系统性能的标志是映射的准确程度和映射的速度。在这里我们就采用准确率和召回率两个性能指标来评估该分类系统,实验结果如表3所示。

二者反映了分类性能的不同方面,必须同时综合考虑,因此选取两者综合测试指标F,其中,

4.3 KNN与SVM不同分类器训练的比较

本文主要对比两种分类器的分类效果和分类时间,分类效果统一为7个类别分类的平均F1值。其中KNN分类器中的参数K取10。其中,两者统一用改进的投票交集法进行特征选取,对上述7个类别进行训练,实验结果如表4所示。

5 结束语

SVM分类器篇5

近年来,不平衡数据集(Imbalance Data Set,IDS)的分类问题因其在实际应用中的广泛出现,越来越受到数据挖掘和模式识别方向的关注和重视,已经成为机器学习领域的研究热点[1]。

不平衡数据集是指某类样本数量明显少于其它类样本的数据集,标准的机器学习分类方法在处理不平衡数据分类问题时,会出现不平衡现象,即分类判决总会倾向于多样本类,而导致少样本类分类精度很低。为描述方便,用负类特指多样本类,用正类特指少样本类。

国内外学者对不平衡数据集问题做了大量的研究工作,提出了许多不同的处理方法。主要包括从两个角度来处理问题: ①重构数据集方法, 分为两种方式, 一种是缩小多类样本, 另一种是扩大少类样本, Chawla等提出SMOTE方法, 在相距较近的正类样本之间插入人造的正类样本[2]; 李正欣等利用SMOTE方法增加正类样本,提出SMOTEBoostSVM集成方法[3]; 吴洪兴等利用遗传交叉运算, 生成新的正类训练样本, 重构数据集方法的核心是将不平衡数据集转换为平衡数据集[4]; ②分类器算法修正,Zhou等将不平衡问题视为代价敏感问题, 对每个类赋予不同的错误代价[5]; Alejo等在文献[5]的基础上, 引入代价函数用于错误代价的评估[6]; Veropulos等对SVM分类的两个类别施加不同的惩罚权值,降低两类样本数量不平衡对分类器的影响[7]。分类器算法修正的本质是:通过对分类器权重参数进行调整,使分类器对正类敏感。

以上不平衡数据集处理方法,都需要预知数据集为不平衡数据集,而事实上,样本分类在何种情况下会发生不平衡现象,且分类判决向负类倾斜的程度如何,都是未知的。因此,原有处理方法需要利用人工经验对数据集类型进行确定。同时,第一种方法中数据的采样率的确定以及第二种方法中权重参数的调整,也包含了人为因素的成分。当训练样本集从平衡态变为不平衡态时,所训练得到的分类器的分类判决受到训练样本分布的影响,标准支持向量机仅仅利用由少量的支持向量所构造的最优超平面作为分类标准,忽略了样本分布对分类决策的影响,从而导致分类精度的不均衡[8]。

本文提出一种平衡不平衡数据集统一分类器——自调节分类面支持向量机(self-adjusting classification-plane SVM,SCSVM),根据训练错分率对分类面进行自适应的调整,引入样本分布对于分类的影响,均衡正负类的错分率,实现平衡不平衡数据集的统一形式分类。

2 自调节分类面支持向量机(SCSVM)

2.1 支持向量机

基于结构风险最小化原理的SVM通过寻找有限训练样本情况下最优分类面,使得分类间隔达到最大。设{xi,yi},i=1,…,n为n个训练样本,xi∈Rd, yi∈{-1,1}为样本i的类别属性,为了使得算法对于测试样本具有良好的推广能力,所选择的最优分类面H应尽可能远离训练样本。设分类面方程H为:xTw+b=0, 则对于所有样本,满足约束方程:yi(xTiw+b)≥1,超平面H距离样本的距离和为2/‖w‖, 最大化间隔距离2/‖w‖对应于最小化目标函数‖w‖2/2;若训练样本为近似可分,则引入松弛变量ξi(≥0), 条件约束方程变为:yi(xTiw+b)≥1-ξi ,目标函数加上错分样本的惩罚变为 $∥ w ∥^{2} / 2 + C \sum_{i} ξ_{i}$ .利用Lagrange辅助函数得到对应的对偶问题:

$\begin{array}{l} \max L_{D} = \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i, j = 1}^{n} α_{i} α_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) \\ \sum_{i = 1}^{n} α_{i} y_{i} = 0; 0 \leq α_{i} \leq C; i = 1, \dots, n (1) \end{array}$

其中, xi·xj表示向量xi和xj的内积,只涉及到内积运算,可以将线性投影方程通过满足Mercer条件的核函数K(xi,xj)推广到非线性情况。判决输出函数为:

$f (x) = s i g n (\sum_{i} y_{i} α_{i} Κ (x_{i}, x) + b) (2)$

2.2 样本分布对分类的影响

对于标准SVM分类,根据KKT条件,可以得到:

$\begin{array}{l} α_{i} (y_{i} (w \cdot x_{i} + b) - 1 + ξ_{i}) = 0 \\ β_{i} ξ_{i} = (C - α_{i}) ξ_{i} = 0 (3) \end{array}$

求解标准SVM对偶二次规划问题得到的Lagrange乘子αi包含三种情况:

①αi=0, 则ξi=0,对应的样本xi被正确分类;

②0<αi<C, 则yi(w·xi+b)-1+ξi=0, 且ξi=0, 此时,样本xi称为标准支持向量,落于分类间隔面上,分类间隔面是平行于最优超平面且离最优超平面距离为1/‖w‖的两个超平面;

③αi=C, 则yi(w·xi+b)-1+ξi=0, 且ξi≥0, 若0≤ξi≤1, 则样本xi处于超平面与间隔面之间,并被正确分类;若ξi>1, 则xi被分到最优超平面的另一侧;如果ξi>0, 称其对应的样本xi为边界支持向量,边界支持向量的比例反映了SVM的错分率。

设NBSV+和NBSV-分别表示正类和负类中边界支持向量的个数,NSV+和NSV-分别表示正类和负类中所有支持向量(边界+标准)的个数,N+和N-分别表示正类和负类中的样本数,由式(1)得:

$\sum_{y_{i} = + 1} α_{i} = \sum_{y_{i} = - 1} α_{i} (4)$

因为0≤αi≤C, 从而有:

$\begin{array}{l} Ν_{B S V +} \cdot C \leq \sum_{y_{i} = + 1} α_{i} \leq Ν_{S V +} \cdot C \\ Ν_{B S V -} \cdot C \leq \sum_{y_{i} = - 1} α_{i} \leq Ν_{S V -} \cdot C (5) \end{array}$

设 $\sum_{y_{i} = + 1} α_{i} = \sum_{y_{i} = - 1} α_{i} = Κ$ , 对式(5)分别除以N+·C和N-·C, 得:

$\begin{array}{l} \frac{Ν_{B S V +}}{Ν_{+}} \leq \frac{Κ}{Ν_{+} \cdot C} \\ \frac{Ν_{B S V -}}{Ν_{-}} \leq \frac{Κ}{Ν_{-} \cdot C} (6) \end{array}$

由式(6)可知, 正负类中边界支持向量与正负类样本数的比值(即SVM对于正负类样本的错分率)的上界, 受到正负类样本数的分布情况的约束, 当N+与N-相差悬殊时, 两类样本的错分率上界相差很大, 当数据集为不平衡数据集时, 标准的SVM的分类判决会倾向负类。

2.3 加权SVM分类器存在的问题

现有的处理不平衡数据的SVM改进算法[9,10],都借鉴了文献[7]的思想,即对不平衡的两类数据施加不同的惩罚权值,设C+,C-分别为正负类的惩罚权值,则式(6)转换为:

$\begin{array}{l} \frac{Ν_{B S V +}}{Ν_{+}} \leq \frac{Κ}{Ν_{+} \cdot C_{+}} \\ \frac{Ν_{B S V -}}{Ν_{-}} \leq \frac{Κ}{Ν_{-} \cdot C_{-}} (7) \end{array}$

通过令N+·C+=N-·C-来确定C+,C-, 达到正负类边界支持向量比的上界一致。

这种方法存在三个问题:第一,虽然通过调整权重可以使得正负类边界支持向量比的上界一致,但并不能够因此而保证正负类边界支持向量比近似相等,无法确定正负类边界支持向量比的取值与其上界存在一一对应关系;第二,若在N+与N-相差悬殊时引入不同的类惩罚权值,而判断相差悬殊的量值,并没有自动明确的方法获得,目前只能依靠人工经验确定;第三,由于处理不平衡数据集时人工经验的存在,无法得到平衡和不平衡数据集统一的分类方法,则需将平衡和不平衡数据集分割开来处理,平衡或不平衡数据集的判断存在人工经验引入。

2.4 自调节分类面支持向量机(SCSVM)

分类器构造的目的在于根据标准SVM分类器正负类错分率对分类面进行调整,使得两类样本的错分率达到均衡,即正负两类样本的训练精度保持平衡,控制两类样本获得均等的推广边际,保持两类均等的推广能力。

对于边界支持向量xi, 对应松弛因子ξi≥0, 当0≤ξi≤1时,xi被正确分类,称其为可容忍边界支持向量,当1<ξi时,xi被错误分类,称其为错分边界支持向量,错分边界支持向量比(与样本数之比)决定了分类器的精确度。

设两类训练样本{xi,yi},i=1,…,n为n个训练样本,xi∈Rd, yi∈{-1,1}, 设正类样本集记为{xi,+}, 负类样本集记为{xi,-}, 分类器构造中所涉及的正负类并非文中所指的少样本类和多样本类,而仅指其类标签为±1, 表明所构造的算法不需人工经验判断数据集类型。记正负类样本中的错分边界支持向量集分别为{xi,+,ebsv},{xi,-,ebsv}。由式(2)可知,支持向量机以最优超平面H法线方向为投影轴,计算样本x基于投影轴的投影z, 实现分类,投影公式为:

$z = \sum_{i} y_{i} α_{i} Κ (x_{i}, x) + b (8)$

其中, z∈R.

由式(2)可知,最优超平面对应为分类点z0=0, 分类间隔面对应为z=±1, 正负类样本集投影为{zi,+},{zi,-}, 正负类错分边界支持向量集投影为{zi,+,ebsv},{zi,-,ebsv}, 显然有,zi,+,ebsv∈{zi,+}, zi,+,ebsv<0, ξi,+=1-zi,+,ebsv>1, 且zi,-,ebsv∈{zi,-}, zi,-,ebsv>0, ξi,-=zi,-,ebsv+1>1, 记N+,ebsv,N-,ebsv分别为正负类错分样本数,则正负类错分率分别为 $\frac{Ν_{+, e b s v}}{Ν_{+}} ‚ \frac{Ν_{-, e b s v}}{Ν_{-}}$ 。

存在以下两种情况:

① $\frac{Ν_{+, e b s v}}{Ν_{+}} = \frac{Ν_{-, e b s v}}{Ν_{-}} \geq 0$ 。

说明对于原分类点z0=0而言,能够保证两类的错分率均衡,但为了使得两类获得相同的推广边际(generalization margin),做如下修正,取z+=min{{zi,+zi,+,ebsv}∪{zi,-,ebsv}}, 其中{zi,+zi,+,ebsv}表示去除错分投影样本的正类样本投影集,z-=min{{zi,-zi,-,ebsv}∪{zi,+,ebsv}}, 取 $z_{0} = \frac{z_{+} + z_{-}}{2}$ , 显然,这样的z0能够保证 $\frac{Ν_{+, e b s v}}{Ν_{+}} = \frac{Ν_{-, e b s v}}{Ν_{-}}$ , 且使得少类样本取得足够的推广能力,分类判决函数为

$f (x) = s i g n (\sum_{i} y_{i} α_{i} Κ (x_{i}, x) + b - z_{0}) (9)$

② $0 \leq \frac{Ν_{+, e b s v}}{Ν_{+}} < \frac{Ν_{-, e b s v}}{Ν_{-}}$ 或 $0 \leq \frac{Ν_{-, e b s v}}{Ν_{-}} < \frac{Ν_{+, e b s v}}{Ν_{+}}$ , 这两个不等式属于同一种情况。

不失一般性,设 $0 \leq \frac{Ν_{-, e b s v}}{Ν_{-}} < \frac{Ν_{+, e b s v}}{Ν_{+}}$ , 即{zi,+,ebsv}≠∅, 将集合{zi,+,ebsv}中的元素按从大到小的顺序排列,即有z0=0>z1,+,ebsv≥…≥zN+,ebsv,+,ebsv.通过以下算法寻找能使正负类错分率均衡的分类点。

错分率均衡分类点寻找算法:

初始化: 令m1=0=zi,+,ebsv, m2=zi+1,+,ebsv, i=0, 以z0′=m1为分类点时有 $0 \leq \frac{Ν_{-, e b s v} ´}{Ν_{-}} < \frac{Ν_{+, e b s v} ´}{Ν_{+}}$ 。

迭代:

Step1 取z0″=m2作为分类点,则正类的错分样本减少一个,而负类的错分样本有可能增加。

Step2 计算调整分类点后的正负类错分率,存在两种可能:

Step2.1 分类点调整后正负类错分率依然有 $\frac{Ν_{-, e b s v} ˝}{Ν_{-}} < \frac{Ν_{+, e b s v} ˝}{Ν_{+}}$ ,则令i=i+1, 若i<N+,ebsv, 仿初始化定义更新m1,m2, 转到Step1; 若i=N+,ebsv, 则取分类点z0″=m2=zN+,ebsv,+,ebsv时,有 $\frac{Ν_{-, e b s v} ˝}{Ν_{-}} \geq \frac{Ν_{+, e b s v} ˝}{Ν_{+}} = 0$ ,且有取分类点z0′=m1=zN+,ebsv-1,+,ebsv时, $\frac{Ν_{-, e b s v} ´}{Ν_{-}} < \frac{Ν_{+, e b s v} ´}{Ν_{+}}$ ,退出迭代。

Step2.2 分类点调整后正负类错分率变为 $\frac{Ν_{-, e b s v} ˝}{Ν_{-}} \geq \frac{Ν_{+, e b s v} ˝}{Ν_{+}}$ ,退出迭代。

对于找到两点m1,m2, 取分类点z0′=m1时, $\frac{Ν_{-, e b s v} ´}{Ν_{-}} < \frac{Ν_{+, e b s v} ´}{Ν_{+}}$ ,而取分类点z0=″m2时, $\frac{Ν_{-, e b s v} ˝}{Ν_{-}} \geq \frac{Ν_{+, e b s v} ˝}{Ν_{+}}$ 。

将区间(m2,m1)与点集{zi,-}取交集,记为A=(m2,m1)∩{zi,-}。

存在两种可能:

① A=∅, 即在两点m1,m2之间,不存在集合{zi,-}的点,显然也不存在集合{zi,+}的点,则令 $z_{0} = \frac{m_{1} + m_{2}}{2}$ , 则对于分类点z0, 可以实现两类的错分率岿衡,且赋予两类均等的推广边际。

② A≠∅, 即在两点m1,m2之间,存在集合{zi,-}的点,不存在{zi,+}的点,记点集A={zi,-′}, 由m1,m2的特性,类似上述寻找m1,m2的迭代过程,反向递推,最终可以找到两点m1′,m2′,在区间(m1′,m2′)内不存在集合{zi}的点,且取m2′为分类点时,有 $\frac{Ν_{+, e b s v}^{2}}{Ν_{+}} \geq \frac{Ν_{-, e b s v}^{2}}{Ν_{-}}$ ,而在取m1′为分类点时,有 $\frac{Ν_{+, e b s v}^{1}}{Ν_{+}} \leq \frac{Ν_{-, e b s v}^{1}}{Ν_{-}}$ ,则取 $z_{0} = \frac{m_{1} ´ + m_{2} ´}{2}$ 。

对于找到的分类点z0, 分类判决函数如式(9)所示。

3 仿真实验

3.1 实验数据

试验选用卡内基·梅隆大学(CUM)Cohn-Kanade人脸表情图像数据库进行算法测试。对原始图像进行人脸图像子区域分割,截取出纯人脸图像,并通过双线性插值算法和灰度直方图修正对人脸图像进行尺寸归一化和灰度归一化处理,经过处理后的人脸表情图像大小为50×50像素大小。利用Gabor小波变换进行特征提取, 其中Gabor小波变换中的网格大小为5×5。原数据集为多类问题,为了计算的方便,将其转换为两类问题,即选取某一人脸作为正类,其他类合并为负类,正负类训练样本比例如表1所示,因为平衡或不平衡数据问题源于训练样本,与测试样本无关,所以取正负类测试样本各10例进行测试。

3.2 评价标准

对于二类分类问题,设N+和N-分别表示正类和负类中的样本数, TP为真实正例数, FP为虚假正例数, TN为真实负例数, FN为虚假负例数。原有的精确率不再适合于对不平衡数据集的评价, 因为当负类所占样本总数比例较高时, 分类器将所有样本判决为负例即可获得较高的精确率,而这样的精确率是没有意义的。选用正负例精确度的几何平均作为评价准则,计算公式为: $g = \sqrt{a c c_{+} \cdot a c c_{-}}$ , 其中 $a c c_{+} = \frac{Τ Ρ}{Ν_{+}}$ 为正类精确度, $a c c_{-} = \frac{Τ Ν}{Ν_{-}}$ 为负类精确度。g值由正负类精确度共同决定,能够全面反映各类的错分情况,避免了原有整体精确度的缺陷。

3.3 试验结果

现有的各分类器需要借助人工经验判定数据为何种数据集,而且只能较好地处理特定类型的数据集;文中所设计的分类器力图避免这样的缺陷,将平衡和不平衡数据集视作一种数据问题,对各种数量比例的正负类采用无区别统一的分类方法处理。为了说明方法的有效性,采用交叉验证的方法,通过将正负类中某两类人交换,进行5次不同的测试,计算得到平均g值。同时,利用标准SVM与加权SVM进行对比实验,采用相同的实验数据和交叉验证方法,加权SVM中加权惩罚因子C+, C-确定方法为:取值C-=1, 根据 $\frac{C_{-}}{C_{+}} = \frac{Ν_{+}}{Ν_{-}}$ 确定C+, 从表1可知,所提出的方法能够对各种数量比例的正负类数据集进行准确有效的分类,不需要对数据集进行人工判定。其中SVM所选核函数为高斯径向基核函数,即

$Κ (x_{i}, x_{j}) = \exp (- γ ∥ x_{i} - x_{j} ∥^{2})$

其中, γ为Libsvm10折交叉验证确定,γ=0.01。

4 总结

现有的平衡或不平衡数据集分类方法需要利用人工经验预知数据集为何种类型的数据集,并且只能处理特定的数据集分类,限制了分类的自动化。

本文提出了一种基于分类面自调节的支持向量机分类器,能够根据标准SVM错分率对分类面进行自适应调整,所调整得到的分类器能够均衡不平衡数据集正负类样本的错分率,反映样本分布对于分类的影响,实现对平衡不平衡数据集的统一形式的分类,并通过试验,验证了所提出算法的有效性。

参考文献

[1]Nitesh V C,et al.Editorial:special issue onlearning from imbalanced data sets[J].ACMSIGKDD Exploration Newsletter,2004,6(1):1~6.

[2]Chawlan N V,et al.SMOTE:synthetic minorityover-sampling technique[J].Journal of ArtificialIntelligence Research,2002,16:321~357.

[3]李正欣,赵林度.基于SMOTEBoost的非均衡数据集SVM分类器[J].系统工程,2008,26(5):116~119.

[4]吴洪兴,彭宇,彭喜元.适用于不平衡样本数据处理的支持向量机方法[J].电子学报,2006,34(12A):2395~2398.

[5]Zhou Z H,Liu X Y.Training cost-sensitive neuralnetworks with methods addressing the classimbalance problem[J].IEEE Transaction onKnowledge and Data Engineering,2006,18(1):63~77.

[6]Alejo R,et al.An empirical study for the multi-class imbalance problem with neural networks[J].Lecture Notes in Computer Science,Progress inPattern Recognition,Image Analysis andApplications,2008,5197:479~486.

[7]Veropulos K,et al.Controlling the sensitivity ofsupport vector machine[A].Proceedings of theInternational Joint Conference on AI[C].1999:55~60

[8]Cortes C,Vapnik V.Support vector networks[J].Machine Learning,1995,20(3):273~297.

[9]程丽丽,张健沛,马骏.一种改进的加权边界调节支持向量机算法[J].哈尔滨工业大学学报,2007,28(10):1135~1138.

SVM分类器篇6

遥感图像分类是遥感图像处理技术中一个具有挑战性的研究领域, 由于目前尚无通用的分类理论, 而现有的大多数算法只针对具体问题[1], 所以人们至今仍在不断探索新的分类理论与分类算法。遥感图像分类方法可分为非监督分类和监督分类, 常见的非监督分类方法有K-Means分类法、FCM分类法;监督分类方法有最大似然分类、Fisher判别分类、神经元网络分类[2]。

支持向量机 (Support Vector Machine, SVM) 是近年提出的一种新监督分类方法, 它能很好地解决学习精度和推广能力之间的矛盾, 罗会兰[3]利用上述优势, 将改进的SVM算法应用于图像分类中, 明显提高了分类精度。与此同时, 在遥感图像分类方法的研究领域, 越来越多的学者开始研究和改进SVM算法[4,5,6,7]。文献[4]分析了统计模式识别方法的优缺点, 提出使用SVM方法进行遥感图像分类的设想。文献[5]首先针对SVM进行遥感图像分类的问题, 提出了理论探讨和实验分析;然后验证了与传统特征降维方法相比, SVM将原特征映射到超子空间的优势;最后深入讨论了SVM的多分类问题和参数的优化, 结论是SVM能有效替代传统模式识别方法对高光谱遥感数据进行分类。文献[6]提出了一种新的复合半监督SVM遥感图像光谱空间分类方法。而文献[7]则提出一种主动学习SVM遥感图像分类方法, 该方法不仅在训练过程中减少了支持向量的个数, 提高了算法效率, 而且提高了分类精确度。

传统非监督分类算法的分类精度通常很难令人满意, 所以遥感图像分类一般会采用分类精度比较高的监督分类方法。但一直以来, 训练样本的选取都是遥感图像监督分类算法的难题, 通常情况下, 遥感图像的样本提取需要人工参与, 十分繁琐, 这也是阻碍SVM在遥感图像处理方面发展的重要原因。针对这个缺陷, 居红云在文献[8]中提出一种利用K-Means聚类提取训练样本的方法, 算法对K-Means聚类后的每类样本再用K-Means算法进行聚类, 提取训练样本。该方法效率低, 算法的分类精度不高。原因在于K-Means算法存在弊端:一是聚类方法提取的训练样本在每一簇中的位置比较分散, 容易包含错分的样本;二是它是一种硬划分, 每个待辨识的对象严格地划分到某个类中, 具有非此即彼的划分性质, 实际上由于混合像元的存在, 使得部分像元很难进行非此即彼的划分。而FCM算法利用模糊集理论能在一定程度上克服硬划分的缺点, 因此FCM在遥感图像分类中的应用也越来越广泛, 如文献[9]针对FCM算法可能会陷入局部最优的缺点, 提出了基于GK和GG两种改进FCM的遥感图像聚类算法, 改进算法对不同形状、尺寸和密度的群集都有很好的适应性, 并且提高了分类的精确度。文献[10]深入研究了模糊集理论在遥感图像分类中的应用, 在对监督分类和非监督分类方法充分研究的基础上, 提出了模糊最大似然分类法, 此方法比单纯的聚类分析的分类效果有很大的改善。

文章充分考虑到训练样本的重要性, 根据FCM聚类后的隶属度矩阵, 提出了利用每类样本中密集程度较高的样本作训练样本的方法, 利用FCM软划分的特点提取性能较好的训练样本, 再结合SVM学习能力和泛化能力强的优点, 完成整个分类过程。

2 支持向量机[4]

1992—1995年, Vapnik等人在统计学习理论的基础上发展出一种新的模式识别方法———支持向量机 (Support Vector Machine, SVM) , 它在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势, 现已广泛用于解决高位数据的监督分类问题, 尤其是处理高维特征空间和大数据量的问题, 如高光谱数据。

SVM的核心思想是把样本通过非线性映射投影到高维特征空间, 以结构风险最小化思想为归纳原则, 在高维空间中构造VC维尽可能低的最优分类面, 使分类风险上界最小化, 从而使分类器对未知样本具有最优的推广能力。基本方法是构造一个超平面作为决策平面, 使得两类之间的空白最大, 构造最优超平面的过程可以转化成为一个典型的二次规划问题 (QP) , 在非线性分类时, 通常采用非线性映射的方法将原始空间中的样本映射到一个高维特征空间中, 使样本在这个空间中线性可分。

假设线性分类器的形式为

即在约束条件:下, C为误差惩罚系数, αi为每个样本对应的Lagrange乘子, αi求解下列函数的最大值

式中:K (xi, xj) =φ (xi) T, φ (xi) 是核函数。

根据二次规划算法求解出αi, 找出αi非零项, 即支持向量的系数, SVM判别函数为

3 模糊K均值聚类 (FCM) 算法

FCM是由Bezdek提出的一种目标函数法, 是模糊聚类算法中最著名、运用最广的算法。FCM聚类算法目标函数为[11]

如果p表示每一个样本xj的维数 (灰度图像时为1) , X=[x1, x2, x3, …, xN]是一个p×N的矩阵;N代表样本数目, 通常表示图像像素;C表示聚类数目;uij⊆U (C×N) 是矢量xj隶属于第i类的隶属度函数, 满足uij∈[0, 1]且;zi为第i类聚类中心, 聚类中心Z=[z1, z2, z3, …, zC]是p×C矩阵。则uij和zi分别更新为

式中:d (xj, zi) =‖xj-zi‖为相似性测度, 一般选用欧氏距离;m∈ (1, ∞) 控制模糊度的权重指数, 它的选取与数据集本身的特点有关, 具体设置方法可参考文献[12]。

FCM算法步骤为:

1) 设置目标函数精度ε, 模糊指数m (m通常取2) , 最大迭代次数Tm;

2) 初始化模糊聚类中心;

3) 由式 (5) 和式 (6) 更新模糊划分矩阵U={uij}和聚类中心Z={zi};

4) 若|J (t) -J (t-1) |<ε或t>Tm则结束聚类, 否则, t=t+1并转到步骤3) ;

5) 由U={uij}得到各像素点分类结果。

4 无人工样本的SVM遥感图像分类

针对人工提取训练样本的繁琐, 提出利用FCM算法提取训练样本的方法, 利用FCM初步分类得到的隶属度矩阵提取训练样本, 只提取每类数据中距离它们均值比较近的样本作为下一步SVM的训练样本。

整个算法流程可总结如下:

1) FCM聚类。设样本X={x1, x2, x3, …, xN} (N为样本的个数) , 用FCM算法 (参数m可调) 对样本进行聚类, 得到C类数据和样本隶属度矩阵U。

2) 提取训练样本, 过程如图1所示。

步骤1:设定每类样本的提取比例参数BL, 并获取所有样本的类别号 (如第i (i∈N) 个样本对应第j (j∈C) 类的隶属度最大, 就默认第i个样本属于第j类, 并记这个最大的隶属度为Fij) ;

步骤2:根据样本类别号, 求每类样本中所有样本属于该类的隶属度 (即最大隶属度Fij) 的均值 (i∈Kj, j=1, 2, …, C, Kj为第j类样本的样本总数) ;

步骤3:求每类样本中样本最大隶属度Fij与Ej (j=1, 2, …, C) 的差值, 按照差值的大小作升序排列, 提取前BL×Kj (j=1, 2, …, C) 个样本作为该类别的训练样本;

步骤4:最后一共得到C类训练样本数据BL×p个及相应的类别号。

3) SVM再次分类。文章中所用SVM函数来自于Libsvm工具箱。利用第2) 步得到的样本数据和类别号进行训练, 建立分类模型model;然后利用model对原数据重新分类, 得到新的类别标签。

5 实验结果及分析

5.1 Iris数据集分类

Iris数据集共有Setosa, Versicolor和Virginica三个类别, Setosa与其他两类是线性可分的, Versicolor和Virginica是线性不可分的。表1是5种算法对Iris数据集的分类结果对比, 其中K-Means算法中迭代次数为30次;FCM算法中权重参数m=9;SVM算法中训练样本比例为10%;文献[8]算法中K-Means算法的迭代次数也为30次;本文算法中FCM算法权重参数m=2、每类样本的提取比例BL=10%。

由表1可以看出K-Means算法的聚类效果最差;相对K-Means算法来说, FCM算法在平均分类精度方面提高了3.3%;由于SVM是监督分类算法, 而且原数据经过高斯核函数映射之后, 原来线性不可分的Versicolor类和Virginica类变得线性可分了, 所以平均分类精度能够达到98.7%;本文算法在分类效果上明显优于文献[8]算法, 平均分类精度提高了4%。另外, 虽然文献[8]算法和本文算法在非监督分类算法的基础上, 都能够有效地提升分类效果, 但是受训练样本的影响, 两种方法的总体分类精度不如监督分类算法。

5.2 遥感图像分类

本文所用的实验数据是由美国喷气推进实验室提供的N/A在Moffett Field附近机载飞行采集的224波段标准高光谱图像数据, 图2中第一幅为原图像 (第10, 20, 30波段合成的伪彩色图像) , 其光谱范围为0.4~2.5μm, 每个通道的波段宽约为10 nm。为了验证文章提出方法在遥感图像分类中的有效性, 在原图像上人工选取了一组遥感数据进行分类实验。提取的遥感数据样本有植被、水体、裸地、居民区和其他5类, 每类50个样本数据, 共250个遥感数据进行试验测试。整个实验在Inter Core双核2.20 GHz, 1.8 Gbyte内存, Windows XP和MATLAB环境下实现。表2对4种方法各自运行10次的平均时间进行对比, 表3是5种算法对遥感数据样本的分类结果对比, 其中K-Means算法中迭代次数为50次;FCM算法中权重参数m=2;SVM算法中训练样本比例为50%;文献[8]算法中K-Means算法的迭代次数也为50次;本文算法中FCM算法权重参数m=2、每类样本的提取比例BL=40%。

图2是几种算法对遥感图像的分类结果图 (伪彩图) , 从图中可以看出本文算法比其他算法的效果要好, 图像纹理更清晰、更接近真实图像。

由表2可以看出本文算法和文献[8]算法都是先提取训练样本, 然后分类, 所以运行时间比非监督分类算法和监督分类算法都要多, 但本文算法却比文献[8]算法节约了91.6%的运行时间, 算法效率得到极大提高。

由表3可以看出K-Means算法对植被、裸地、居民区3个类别都存在错分的现象, 尤其是对裸地分类能力最差, 45个错分到居民区, 5个错分到其他类, 该方法共错分60个样本, 平均分类精度只有76%;而FCM算法克服了混合像元不可分的问题, 极大地提高了分类精度, 总体平均分类精度达到了96.4%;SVM算法的分类效果最好, 只有一个样本被错分, 总体分类精度能够达到99.6%。文献[8]算法与K-Means算法相比, 分类效果略有提高, 比FCM算法分类精度低20%;本文提出的方法对植被和居民区类的错分情况有明显改善, 只有2个裸地样本被错分到居民区类中, 总体平均分类精度达到了99.2%, 分类精度略低于SVM算法, 但比FCM算法提高了3.2%, 比文献[8]的方法提高了23.2%。

6 小结

对于遥感图像监督分类算法而言, 训练样本的获取是极其重要的一个步骤, 一般训练样本的提取都是人工实地考察和遥感图像的结合方法, 十分不易。针对这种缺陷, 文章提出一种FCM提取训练样本的方法。该方法在训练样本提取过程中, 只提取比较靠近聚类中心的样本, 这些样本代表性强、错分概率低、性能较好, 再结合SVM推广能力强的优势, 很好地提高了分类精度。实验结果证明本文提出算法的分类效果比非监督分类算法好, 而且与文献[8]方法相比, 训练样本的提取过程更加简单、合理, 虽然文中提出的分类方法比非监督分类和监督分类算法需要的时间要长, 效果也略逊于监督分类算法, 但这个代价是值得的, 因为它提高了非监督分类算法的分类精度, 免去了监督分类算法中人工提取训练样本的复杂工序, 非常适合应用于遥感图像处理。

摘要：针对遥感图像监督分类方法需要人工提取训练样本的缺陷, 提出一种模糊K均值聚类 (FCM) 提取训练样本、支持向量机 (SVM) 进行分类的方法。首先用FCM进行初步分类得到隶属度矩阵并判断每个样本的类别号;然后根据隶属度矩阵提取每类样本中密集程度较高的样本作为训练样本;最后用SVM对样本进行训练、再次分类。该方法克服了SVM算法需要人工样本的缺点, 改善了传统非监督分类算法的性能, UCI标准数据库Iris数据和遥感数据样本的实验结果证明了该方法的可行性。

关键词：遥感图像分类,模糊C均值聚类,支持向量机,隶属度

参考文献

[1]章毓晋.图象分割[M].北京:科学出版社, 2001.

[2]杨鑫.浅谈遥感图像监督分类与非监督分类[J].四川地质学报, 2008, 28 (3) :251-254.

[3]罗会兰, 杜连平.一种SVM集成的图像分类方法研究[J].电视技术, 2012, 36 (23) :39-42.

[4]张耀波, 张迁.基于SVM的遥感影像的分类[J].地理空间信息, 2005, 3 (4) :24-26.

[5]MELGANI F, BRUZZONE L.Classification of hyperspectral remote sensing images with support vector machines[J].IEEE Trans.Geoscience and Remote Sensing, 2004, 42 (8) :1778-1790.

[6]MARCONCINI M, CAMPS-VALLS G, BRUZZONE L.A composite semisupervised SVM for classification of hyperspectral images[J].IEEE Geoscience and Remote Sensing Letters, 2009, 6 (2) :234-238.

[7]SUN Z, LIU Z, LIU S, et al.Active learning with support vector machines in remotely sensed image classification[C]//Proc.CISP’09.Tianjin, China:IEEE Press, 2009:1-6.

[8]居红云, 张俊本, 李朝峰, 等.基于K-means与SVM结合的遥感图像全自动分类方法[J].计算机应用研究, 2007, 24 (11) :318-320.

[9]YU J, GUO P, CHEN P, et al.Remote sensing image classification based on improved fuzzy C-means[J].Geo-spatial Information Science, 2008, 11 (2) :90-94.

[10]别怀江.基于模糊集的遥感图像分类研究[D].哈尔滨:哈尔滨工程大学, 2005.

[11]俞群爱, 王艳清.基于MATLAB的FCM聚类算法研究[J].科学与财富, 2010 (4) :12-14.

SVM分类器篇7

关键词：MapReduce,SVM,KNN分类算法

0 引言

对垃圾邮件的过滤常采用黑白名单的形式,其具有速度快和简单的特点,但需要用户不断更新垃圾邮件的过滤规则并维护黑名单邮件列表。针对庞杂的垃圾邮件分类问题,支持向量机在学习过程中需要占用大量内存,寻优速度非常缓慢,进而导致分类速度急剧下降,因此SVM(支持向量机)对大规模数据集训练速度慢的瓶颈凸显出来。针对海量数据,Google实验室提出MapReduce并行分布式计算模型,它能够组织集群来处理大规模数据集。本文通过分析SVM的分类原理,找到其算法中可并行的点,将其巧妙地应用于MapReduce环境下。本文提出了基于MapReduce并行SVM的垃圾邮件分类算法,通过循环迭代机制、SVM参数寻优、KNN近邻算法来提高该算法的精度。

1 相关概念

1.1 MapReduce编程框架

MapReduce是一种编程模型,它具有简单、易于实现且扩展性强的优点,目前已得到广泛应用。MapReduce用于大规模数据集(大于1TB)的并行运算,它通常在多台主机集群中同时处理程序,使得程序运行速度较快。采用MapReduce编程模式具有如下优点:(1)能在由廉价主机所组成的大规模集群中自动并行执行;(2)每一个从节点任务都是独立并行运行的,互不干扰,从而简化了并行计算和容错功能实现;(3)网络传输数据速度将受带宽影响,而MapReduce可以将中间数据缓存到本地磁盘,这样就不受带宽限制。

1.2 支持向量机(SVM)

支持向量机(Support Vector Machine,SVM)由Corinna Cortes和Vapnik等学者于1995年首先提出,它在解决小样本、非线性以及高维模式识别中具有特有优势。其核心思想源于结构风险最小化原则,对特定样本进行训练得到有效模型,再根据已得到的模型识别任意样本,使得模型识别任意样本的能力尽可能高。作为统计学习理论中最具实用性的部分,支持向量机已成为大家追捧的关于机器学习与数据挖掘的重要技术,支持向量机有效解决了传统统计理论处理大规模数据存在的“维数灾难”缺陷,可以很好地应用于高维数据。而在支持向量机理论中,首先需要了解的知识点是最大超平面。

SVM使用训练样本中的一个子集作为决策边界,并将其称为训练结果的支持向量。本文研究的是二分类,基于两个类别的训练集进行考虑,如图1所示的2维空间R2上的分类问题。分别用星星和圆圈来表示这两个不同类别的样本,假设存在一条直线能够让星星位于该直线的一侧,而圆圈位于该直线的另一侧,则称这条直线为超平面,显然,符合上述条件的超平面有无穷多个。为了使得到的分类器的分类性能尽可能优,需探讨可能的超平面哪一个更优。

首先假定分划直线wTx+b=0的法向量w已经给定,可以找到多条这样的直线,不妨将这条直线进行左右平移,直到碰到某个样本点的输入,也即y=1和y=-1的两条极端线,则这两条直线就被称为支持直线,直线上的样本点就是支持向量。在y=1和y=-1这两条直线之间的所有平行直线都能将训练集正确划分;当超平面离直线两边样本点的间隔越大,分类准确率将越高,所以就是要寻找到具有最大间隔的超平面,于是引入最大间隔法,将目标函数转化为:

即求解1/‖w‖的值,则其最大值相当于1/2‖w‖^2的最小值,目标函数又可转化为:

鉴于该目标函数的特殊性,还可以通过拉格朗日变换到对偶函数的优化问题。

求解最大超平面的过程就转化为求解w、a、b这3个变量的值。

2 基于MapReduce的并行SVM分类算法

SVM适合解决小样本,其解决海量数据集的性能较差。为了提升处理性能,本文将MapReduce编程模式应用于非线性支持向量机算法中,分别实现了基于MapReduce的并行SVM算法(简称MR-SVM)、并行循环迭代SVM算法(简称MR-C-SVM)。为了减少误分样本数量,在原有算法基础上添加了KNN算法,简称MR-KSVM。

2.1 MapReduce编程模式下的并行SVM算法

MapReduce由Map和Reduce两个函数组合而成,因此可以将MapReduce分成两个阶段进行分析。

Map阶段:将输入的大数据集切割成多个均等的数据子集,然后将数据子集分配给空闲Map工作单元,最后工作单元以分布式方式并行求解各数据子集上的拉格朗日乘子。其中,非零拉格朗日乘子对应的样本点为支持向量。根据SMO算法求出了拉格朗日乘子后,根据式(1)、式(2))即可求出w和b。求出w和b后,便可得出分离超平面和分类决策函数。Reduce阶段:在各Map运行结束后,联合各Map得出的局部支持向量,一起作为Reduce的输入;将所有支持向量进行重训练,再将最终得到的训练结果作为分类器,将重训练的结果作为全局最优解。并将对应为支持向量机的样本,以及重训练得到的模型都保存到本地文件中,以便于测试数据时使用。

2.2 MapReduce环境下的SVM循环迭代算法

在MR-C-SVM循环迭代机制中,引入了KKT条件进行判断(KKT条件:αi表示拉格朗日乘子,yi表示标签值,ui表示函数值)。(1),表明是正常分类,在两条边界之外(已知道正确分类的点);(2)表明是支持向量,在边界上;(3)表明是在两条边界之间。

算法描述:(1)判断是否为首次训练,若是,按照MR-SVM算法单程顺序执行,执行完一次后将得到的分类器保存到本地文件,否则执行步骤(2);(2)反馈循环机制,将当前全局最优支持向量集以及决策参数w和b反馈给各Map。各Map利用当前最优分类器所确定的KKT条件来对原始数据进行判断,如果所有数据都符合KKT条件,则说明数据集收敛于全局最优解。否则,将违反KKT条件的向量和当前全局最优解支持向量联合进入下一步优化过程,再次执行步骤(2)。

2.3 参数寻优

SVM模型有两个非常重要的参数C与gamma。其中C是惩罚系数,即对误差的宽容度。C越高,说明越不能容忍出现误差。C过大或过小,泛化能力都变差。gamma是选择RBF函数作为kernel后,该函数自带的一个参数。该项目采用折叠K-foldcross-validation,也称K折交叉验证。

算法描述:让c和g在一定范围内取值,将原始数据集利用k-cv方法得到每组c和g下训练集验证分类准确率,最终取准确率最高的一组c和g作为最佳参数,并用于后续测试。但是有可能会出现多组c和g对应于最高分类准确率的情况,此种情况下,采用最高分类准确率中参数c最小的一组,如果最小的c有多组g,就选取搜索到的第一组参数作为最佳的参数组合,然后将最佳的c和g保存下来,为后面训练所用。

2.4 原有循环迭代基础上的KNN算法引入

通过上述循环迭代机制得到的分类器,对测试集进行测试时,位于两条边界线之间的样本点很有可能会出现误分情况,从而影响分类准确率。为了尽可能地降低误分的可能性,于是引入了KNN最邻分类算法。本文算法利用前面的MR-C-SVM,求出相应的支持向量和对应的拉格朗日乘子以及常数b,设T为测试集,P为支持向量集,K为KNN中的取值(根据数据集的大小自己设定),ε为判断的阈值。其步骤如下:(1)判断T是否为空,是就停止,否就在测试集中取一个样本x;(2)将索取样本点的数据带入

,其中Xi表示支持向量集的数据;(3)如果|g(x)|>ε时,则直接计算F(x)=sgn(g(x))的值进行输出,否则就将该样本点带入KNN算法进行分类,传递x、P、K这3个参数,将返回结果作为输出;(4)循环执行(1)。

3 实验结果分析

本实验所采用的数据集来自于标准UCI机器学习知识库中的SpamBase数据集,SpamBase数据集共包含4 601封邮件,该样本的维数是57维,其中一个是类别属性,样本含有两个标签,分别表示合法邮件和垃圾邮件,标签分别用1和-1表示。

根据数据集的数据量大小,经过参数寻优寻找到最佳的gamma取值为0.5。表1显示了参数C取不同值时所对应的分类准确率,迭代次数为5,KNN算法的K取值为10。分类准确率折线如图2所示。

根据实验结果可得出如下结论:

(1)MR-C-SVM与MR-SVM相比准确率更高,说明基于MapReduce的并行SVM算法存在的精度损失问题得到了一定改进,其关键在于MR-C-SVM在Reduce阶段将各Map联合后进行了重训练,并且引入了KKT条件判断进行循环迭代。

(2)MR-C-KSVM的准确率在原有循环迭代的基础上有明显提升。引入KNN的目的是降低在两条分界线之间的样本点误分的可能性,从结果可以看出,MR-C-KSVM算法不仅提高了算法的收敛性,还提升了分类精度。

参考文献

[1]杜玲玲.基于MapReduce的数据挖掘算法研究与应用[D].桂林:桂林电子科技大学,2012.

[2]邰建华.Hadoop平台下的海量数据存储技术研究[D].大庆:东北石油大学,2012.

[3]曹聪.云计算支持下的数据挖掘算法及其应用[D].广州:广州大学,2012.

[4]牛科.基于Hadoop云平台的分布式支持向量机研究[D].临汾:山西师范大学,2014.

[5]汪海燕,黎建辉,杨风雷.支持向量机理论及算法研究综述[J].计算机应用研究,2014(5):1281-1286.

[6]张国云.支持向量机算法及其应用研究[D].长沙:湖南大学,2006.

SVM分类器篇8

近些年,大量负荷接入电力系统,使电网产生各种电能质量问题[1],造成了巨大的经济损失和社会影响,电能质量的检测和分析已成为电力系统研究的重点之一。电能质量扰动分类是电能检测的前提,因此其对电能质量检测和提高具有重要作用。

目前对电能质量扰动的研究更多集中在单一扰动检测方面[2],但是实际中电能质量扰动的存在不是只有一种扰动,而是由多种单一扰动组合而成,这种扰动被称为复合扰动[3,4]。目前对电能质量复合扰动进行分类的方法主要有:神经网络[5]、决策树[6]和支持向量机(Support Vector Machine,SVM)[7,8]等。神经网络分类器具有简单的结构和很强的求解能力,但是训练时间长,且容易出现过学习等问题;决策树分类器是模拟人类的思维构建分类规则,虽然分类速度很快,但在分类过程中建立规则比较复杂,会出现错误累积的误差,并且对于多种类分类模型很难处理。

SVM基于统计学习理论,是一种解决样本数量少、非线性及高维样本的模式识别问题的机器学习方法,其克服了人工神经网络易陷入局部最优解和训练时间长的缺点[9]。本文中,采用SVM作为分类器,实现电能质量复合扰动的分类。首先,本文将采用小波变换的方法对各种电能质量复合扰动进行特征提取;然后,采用改进后的支持向量机对各种电能质量复合扰动进行分类。

2 支持向量机分类器

支持向量机是以统计学习理论和构建风险最小化为基础的一种机器学习方法,用于解决小样本数据的分类问题,它能把输入空间中线性不可分的问题经过核函数映射到高维空间,变成线性可分问题。通过建立一个最优超平面,得到最大的分类间隔,使两类样本达到最优化分类。

假设给定特征空间上的训练样本集为(xi,yi),其中,xi为第i个特征向量,yi∈{+1,-1}为分类号,i=1,2,…,N,N为样本数。所谓的线性分类器就是可以找到一个最优分类超平面ωTx+b=0将不同类别的特征量x分开。令分类函数f(x)=ωTx+b,其中,ω为法向量,b为截距,如果f(x)=0,那么x是分类超平面上的点;如果f(x)<0,那么x则属于类别-1;如果f(x)>0,那么x则属于类别1。要确定分类函数,则要确定分类函数中的两个参数ω和b,于是需要寻找最大分类间隔。经求解得到最大分类间隔为1/‖ω‖,即目标函数可以表示为max(1/‖ω‖),约束条件为yi(ωTx+b)≥1,其中,i=1,2,…,N。目标函数max(1/‖ω‖)经过取倒数可转化为求min(‖ω‖2/2),则目标函数为:

式中,ω为法向量。约束条件为:

为了更好地求解这个函数,可应用拉格朗日对偶性,通过求解对偶问题得到最优解,则有

分别对ω、b求偏导且结果为0。

对ω求导得:

对b求导得:

将式(4)和式(5)代入式(3),对αi求解最大值,即

约束条件为:

若αi*为最优解,则

式中,如果αi*不为零,那么其对应的训练样本就是支持向量。

综上所述,假设(xi,yi)是其中的一个支持向量,s为所有的支持向量数目,那么分类决策函数的表达式如下:

式中,K(xi,xj)为引入的核函数,其作用是将低维空间中非线性不可分样本映射到高维空间中,变成线性可分问题。

分类阈值为:

当样本线性不可分时,通过引入松弛变量ξi和惩罚因子C解决问题,则目标函数变为:

约束条件为:

SVM只是进行二类分类,当需要进行多分类时不能直接使用。对于解决电能质量复合扰动分类等多分类问题时,需要把多分类问题变换成二分类问题,因此,需要构造多个二分类SVM,把多分类问题变换成多级二分类问题来处理。本文采用一对一(One-against-One)SVM这种多分类方法对电能质量复合扰动进行分类。

3 改进的支持向量机

核函数是实现特征量数据从低维空间的非线性不可分到高维空间线性可分的关键。核函数的形式不一样,则支持向量机对样本的作用形式也不一样。对于所有的样本x,xi∈X,其中X是样本集,若函数K满足:

则称函数K为核函数。式中,ф(·)为从原始输入空间到高维特征空间的映射;<,>为内积。常用的核函数主要有高斯核函数、线性核函数、多项式核函数等。

3.1 高斯核函数

在解决实际问题中,高斯核函数因具有可分性,即存在一个超平面能将训练集分开,而被广泛应用。其一般形式为:

高斯核函数的曲线如图1所示。

3.2 核函数的改进

高斯核函数由欧式距离方程K(x,xi)=‖x-xi‖构成,其对样本的作用是局部的。在原空间分布比较密集的特征量经过高斯核函数的作用,映射到高维空间后会变得非常稀疏,这就降低了核函数的局部作用能力,使分类模型建立过程中支持向量的数目增加,计算复杂度变大,计算时间变长。从式(14)中能够得出,带宽σ是高斯核函数中仅有的一个参数,通过调整σ的值可以改变支持向量机的分类性能和样本在高维空间中的聚类能力。但是,只调节σ这一个参数对支持向量机的分类性能影响并不大,并没有解决高斯核函数存在的问题。

要解决该问题,核函数需具有在支持向量附近衰减速度很快的特性[10],所以本文将对高斯核函数进行改进,引入一个幅值调节参数,其表达式如下:

式(15)能使样本数据在支持向量附近有较快的衰减速度。

为了使特征量在高维空间中的支持向量附近更加聚集,引入径向宽度调节参数c,使得函数有较快衰减速度的同时样本数据在支持向量附近更加聚集,其表达式如下:

图2为函数幅值固定不变的情况下,通过调节参数c得到的函数曲线图。可以看出,c值越大,所对应的曲线衰减速度越快,数据在支持向量附近更加聚集。所以,通过控制参数c可以改变核函数的衰减速度和数据的聚集程度。

3.3 改进的高斯核函数和高斯核函数的性能比较

通过Matlab仿真,对两种核函数进行实验对比,结果如图3所示。σ都取值为0.595,改进的高斯核函数c取值5.5。

可以看出,改进的高斯核函数在支持向量附近更加聚集,而且在其附近的衰减速度比高斯核函数的衰减速度快,所以可以通过改变参数c改变核函数衰减速度的快慢,c越大,则衰减的速度越快。

4 电能质量复合扰动分析

本文主要针对电压骤降、电压骤升、电压中断、谐波、暂态脉冲、暂态振荡和电压闪变7种单一扰动和骤升+谐波、骤降+谐波、骤升+闪变、骤降+闪变和闪变+脉冲5种复合扰动进行分类,表1为12种电能质量扰动的数学模型[11,12,13]。

对电能质量复合扰动进行分类主要分成两步:特征提取和分类。小波变换被广泛应用于电能质量信号处理中[14],为了方便,本文采用小波变化对表1的12种电能质量扰动信号进行处理,采用db10小波进行8尺度小波分解,提取分解后的各层小波系数,根据Parseval定理求取各尺度的能量,然后求其与正常信号的能量之差,对这8个能量差进行归一化处理作为特征量,即共有8个特征量。最后用改进的支持向量机对电能质量复合扰动信号进行分类。分类的步骤如下:

(1)选取归一化处理的数据一部分作为训练样本,给定核函数带宽参数σ。

(2)用改进的支持向量机对训练样本进行训练建模,求得分类模型。

(3)将其余的样本作为测试样本,输入到训练好的分类模型中进行预测分类,求取分类准确率。

5 实验仿真与分析

本文对表1给出的12种电能质量扰动信号进行分类,验证所提分类方法的有效性,并与传统高斯核函数的支持向量机分类方法进行比较。其中,c值经过多次取值测试后确定。表2给出了不同c值时,模型的整体分类准确率以及支持向量总数。

从表2可以看出,当c值大于5.5或者小于5.5时,运行程序得出的分类结果虽然也较原来有所提高,但是都低于c值等于5.5时运行得出的结果。这是因为c值越大,改进的高斯核函数在支持向量附近越聚集,衰减的速度越快,但当c值大于5.5时,改进的高斯核函数在支持向量附近过于聚集,模型的整体分类准确率降低,所以本文中c取值为5.5。带宽参数σ和惩罚参数C的值通过交叉验证和网格搜索获取,σ取值0.595,C取值4,加入20d B的噪声。

表3给出了改进前后支持向量总数、运行时间和整体分类准确率的对比结果。表3中每种扰动的训练样本为80个,测试样本为120个,即训练样本总数为960个,测试样本总数为1440个。在这种情况下,由表3可以看出,改进的支持向量机分类过程中支持向量总数有所减少,使得计算变得简单,缩短了分类时间,而且最终整体的分类准确率有所提高。这三个对比结果都表明改进后的支持向量机提高了对电能质量复合扰动的分类准确率。

表4为12种电能质量扰动分别在改进后的支持向量机和未改进的支持向量机分类方法中的分类准确率,其中,每种扰动的训练样本为80个,测试样本120个。由表4可以看出,这12种扰动类型在改进后的支持向量机下的分类相比传统的支持向量机分类的分类准确率几乎都有所提高,平均分类准确率也有所提高。因此,该结果能够说明本文提出的分类方法对常见的几种电能质量复合扰动具有较高的分类准确率。

6 结论

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【SVM分类器】相关文章：

多分类SVM06-23

多分类器05-03

基于相反分类器的数据流挖掘方法分析09-11

诗歌分类按题材分类08-24