收稿日期:2008-09-28;修回日期:2008-11-28。 基金项目:国家自然科学基金资助项目(10871022)。
作者简介:陈丽(1982-),女,河南安阳人,硕士研究生,主要研究方向:数据挖掘、模式识别、支持向量机; 陈静(1964-),女,河南南阳人
,教授,主要研究方向:数据挖掘、数值模拟、最优化方法、支持向量机。
文章编号:1001-9081(2009)03-0833-03
基于支持向量机和k 近邻分类器的多特征融合方法
陈 丽,陈 静
(中国农业大学理学院,北京100083)
(ji ng_quch en @163.co m )
摘 要:针对传统分类方法只采用一种分类器而存在的片面性,分类精度不高,以及支持向量机分类超平面附近
点易错分的问题,提出了基于支持向量机(S VM )和k 近邻(KNN )的多特征融合方法。在该算法中,设样本集特征可分为L 组,先用S VM 算法根据训练集中每组特征数据构造分类超平面,共构造L 个;其次用S VM KNN 方法对测试集进行测试,得到由L 组后验概率构成的决策轮廓矩阵;最后将其进行多特征融合,输出最终的分类结果。用鸢尾属植物数据进行了数值实验,实验结果表明:采用基于S VM KNN 的多特征融合方法比单独使用一种SVM 或S VM KNN 方法的平均预测精度分别提高了28.7%和1.9%。
关键词:支持向量机;k 近邻;多特征融合;后验概率中图分类号:T P311.13;TP181 文献标志码:A
M ulti feature fusion m ethod based on support vector machi ne
and k nearest neighbor cl assifier
C H E N L,i C H E N Jing
(Colle g e o f S cie n ce ,C hina Ag ric u lt ural University ,B eiji ng 100083,C hina )
Abstract :T he trad iti onal c l assifi cation m e t hods on l y use one si ng l e c lassifi e r ,w hich may lead to one si dedness ,low
accuracy ,and that t he sa m ples nearby the SupportV ectorM achi ne (S VM )hyperplanes are mo re easily m i sclass ified .T o so l ve these proble m s ,t he mu lti feat u re f usion m ethod based on S VM and K N earest N eighbo r (KNN )c lassifi e rs w as presen ted in th i s paper .F irstl y ,t he features were divided into L g roups and the SVM hyperplanes w ere constructed f o r each feat u re of tra i n i ng set .Second l y ,the testi ng set w as tested by S VM KNN m e t hod ,and the decision pro file m atri x es we re obta i ned .F i nall y ,t hese dec isi on pro file m atr i xes we re i m p l em ented by mu lti feat u re fusi on m ethod .The experi m enta l results on Iris data show that t he f o recast accuracy of the m ulti f ea t ure fusi on m ethod based on SVM KNN classifiers i ncreases by 28.7%and 1.9%t han those o f S VM and S VM KNN m et hods respecti ve l y .
K ey words :SupportV ectorM achi ne (S VM );K NearestN e i ghbor (KNN )algo rit h m;mu lti feature f usi on ;i nverse probabilit y
0 引言
传统的分类方法大都采用单一的分类器对数据进行分
类,或者通过增加单个分类器结构的复杂度来提高分类精度,结果往往令人不满意。而通过将多个结构较为简单的分类器进行融合的方法来提高整体的分类精度,不失为明智的选择。然而,常见的融合方法如线性组合法、投票法[1]、计数法[2]、模糊积分[3-4]等都没能利用样本被子分类器分类后的后验概率,忽略了子分类器的性能差异,分类结果都不理想。另外,还有一种融合方法:概率乘积准则[5],此方法虽利用了样本被每个子分类器分类后的后验概率,但由于概率乘积准则在融合过程中要将所有后验概率相乘,增加了融合后样本被错分的概率。这是因为假设存在某个子分类器将样本分为某类的概率为零,则融合过程中将所有后验概率相乘时,该样本被分为该类的概率将大大降低。而采用概率和准则[5]可有效避免此类情况的发生。
研究发现支持向量机[6](Support V ector M ach i ne ,S VM )与k 近邻(K N ea rest N e i ghbor ,KNN )相结合能提高支持向量机的分类精度[7]。因此,本文提出了基于支持向量机(S VM )和k 近邻(KNN )的多特征融合分类方法,以期在不增加支持向量机算法时间复杂度的基础上,减少支持向量分类超平面
附近样本的错分率,提高对数据的分类准确率。
1 SVM KNN 分类器简介
支持向量机是由V apnik 等人于1995年提出的一种建立
在统计学习理论基础上的分类方法,在解决小样本、非线性、高维模式识别中具有分类精度高、泛化能力强等优势。但是在使用S VM 分类时,分界面附近的样本点比较容易被错分,而SVM 分类器等价于每类只选一个代表点的1 NN 分类器[7]。因而在对样本进行分类时,可以考虑根据空间的不同分布采用不同的分类方法:当样本距SVM 最优超平面的距离大于一给定阈值 时,即样本离分界面较远时,用S VM 方法进行分类;反之,当样本和SVM 最优超平面的距离小于 时,用KNN 方法对测试样本分类。
图1 SV M KNN 分类算法示意图
具体地,对于待识别样本x ,计算x 与两类支持向量代表
第29卷第3期
2009年3月
计算机应用
Journa l o f Co m puter App lications
V o.l 29No .3M ar .2009
点x +和x -的距离差,如果距离差大于 ,如图1中区域 ,用S VM 一般都可以正确分类;当距离差小于 ,即落入区域 ,如果分类时仍用SVM,相当于只计算x 与每类所取的一个代表点的距离,比较容易错分。所以这时采用KNN 算法进行分类,将所有支持向量作为代表点,计算待识别样本和每个支持向量的距离,对待识别样本做出判断。
2 多特征融合分类方法
多特征融合[8]是指首先根据样本的每组特征分别对样本进行分类,然后将所有的分类结果进行融合,得到最终分类结果,其构架如图2所示。它能整合来自多信息源的信息,降低单信息源中存在的不确定性,
从而提高系统的整体性能。
图2 多特征融合构架
图2中 样本 为测试集中一个样本, 特征i 表示第i 组参与融合的特征数据,i =1,2, ,L 。设所有样本可分为c 类。首先,根据训练样本集每组特征数据构造出L 组基本分类器。然后,用这L 组基本分类器分别对测试样本x 进行分类。设经第i 组分类器分类后得到的分类结果记为:{d i ,1(x ), ,d i,j (x ), ,d i ,c (x )},d i ,j (x )表示第i 个分类器将测试样本分为第j 类的概率(后验概率),其中i =1,2, ,L,j =1,2, ,c 。于是对每个测试样本x ,经L 个分类器分类后可以得到一个决策轮廓矩阵:
d 1,1(x )d 1,2(x ) d 1,j (x ) d 1,c (x )
d 2,1(x )d 2,2(x ) d 2,j (x ) d 2,c (x ) d i ,1(x )d i,2(x ) d i,j (x ) d i ,c (x ) d L,1(x )
d L,2(x )
d L,j (x )
d L,c (x )
(1)
最后,将这些结果经多特征融合后输出最终分类结果。
3 基于S VM KNN 的多特征融合分类方法
多特征融合方法能避免只采用单一分类器分类方法存在的片面性和分类精度不高的问题。其中,多特征融合方法中的概率和准则充分利用了样本被分类后的后验概率,是一种比投票法、计数法等融合方法更有效的特征融合方法。同时,由于SVM KNN 可以减轻对核函数参数选择的敏感程度,一定程度上比使用SVM 具有更好的分类性能[7]。因此,本文提出了基于SVM 和KNN 的多特征融合分类方法。新算法在不增加传统支持向量机方法时间复杂度的基础上,降低了其分类超平面附近样本点的错分率,考虑到了各个子分类器之间的差异,是一种比只采用单一的S VM 或SVM KNN 分类器分类精度更高的一种方法,且通过不同的融合方案能够分析出在分类过程中占主要因素的特征。3.1 概率和准则
概率和准则[5]的思想是:首先假设对于测试样本x ,经L 个基本分类器分类后,得到了一个决策轮廓矩阵,如式(1)。
然后,计算测试样本x 属于第j 类的置信度 j (x ):
j (x )=(1-L )p (j )+
L
i=1
d
i,j
(x );j =1,2, ,c (2)
其中,p (j )=N j /N,j =1,2, ,c ,N j 为训练样本集中属于第j 类的样本数量,N 为训练样本的总数量。
则融合后样本x 的判别结果为:
j *
(x )=arg m ax c
j =1[ j (x )]
(3)
3.2 S VM KNN 多特征融合分类算法
设样本集中共有L 组特征。首先,根据训练样本集中的L 组特征数据用SVM 方法分别得到L 组支持向量集T k s v 和决策超平面g k (x ):
g k (x )=
m
i=1
*i y i K (x i ,k ,x )+b *;k =1,2, ,L
(4)
其中,x i,k 表示第i 个训练样本的第k 组特征,K ( , )为支持
向量机核函数。
对于一个两分类问题,基于SVM KNN 的多特征融合分类算法步骤如下。
输入:测试样本集T 和训练样本集。输出:测试集中每个样本的类别j *(x )。方法:
1)取x T ,计算样本x 的决策轮廓矩阵(d i ,j (x ))L 2。1.1)设初始k =1。根据式(4)计算g k (x k ),其中x k 表示x 的第k 组特征数据。
1.1.1)若g k (x k )> ,计算x k 分别被分为正类和负类的概率{d k,1(x ),d k,2(x )}[9]:
d k ,1(x )=1
1+exp (-g k (x k )),d k,2
(x )=1-d k,1(x )
(5)
否则,转1.1.2)。1.1.2)若g k (x k )< ,用KNN 分类算法重新分类,训练集为第k 个支持向量机分类器的支持向量集T k s v ,则:
d k ,1(x )=q /p, d k,2(x )=1-d k ,1(x )(6)其中,p 为KNN 算法中所取近邻的个数,q 为所取近邻中属于正类的代表点的个数[10]。在KNN 算法中计算x k 与每个支持向量的距离时采用下式:
d (x k ,x i )=K (x k ,x k )-2K (x k ,x i )+K (x i ,x i );
x i T k s v (7)
1.2)k k +1,若k =L ,转2);否则,转1.1)。
2)得到样本的决策轮廓矩阵
d 1,1(x )d 1,2(x )
d i ,1(x )d i ,2(x ) d L,1(x )
d L,2(x )
,代入到式(2~3)中,此时c =2,得到测试点x 经多特征融合后的最终分类结果j *(x )并输出。
3)T T -{x },若T = ,停止;否则,转1)。3.3 算法时间复杂度分析
设n 为训练样本的个数,L 为将样本特征分成的组数,d 为每组特征包含的特征数目。对于一个测试样本,由于KNN 法的时间复杂度是O (dn 2)[11],计算后验概率时只需要将分类后的结果代入式(5~6)中,因此其时间复杂度是O (1),而判断g k (x k )与 的大小的时间复杂度是一常数,步骤1.1.1)和1.1.2)共循环了L 次,所以步骤1.1.1)的时间复杂度是O (L ),步骤1.1.2)的时间复杂度是O (Ldn 2+L )。所以,步骤1)计算样本决策轮廓矩阵的总时间复杂度是O (Ldn 2+L )。步骤2)中多特征融合的计算相当于对决策轮廓矩阵的每一列元素求和,再分别加上一个常数后求每列的最大值,然后取其下标,所以步2)的时间复杂度是O (2L )。又由于标准支持向量机的时间复杂度是O (n 3)[12],所以基于SVM KNN 的多特征融合分类算法总的时间复杂度是:
O (Ln 3)+O (Ldn 2+L )+O (2L )=
834 计算机应用
第29卷
O (L n 3+Ldn 2+L +2L )=O (n 3)(8)
其中,L 是不依赖于n 的指定正常数,d 由上面可以看出,本文提出的基于SVM KNN 的多特征融合分类算法并没有增加支持向量机的时间复杂度。 4 实验与讨论 为了验证算法的有效性,采用鸢尾属植物数据集的Iris ve rsico l or 和Iris v irg i nca 两类数据进行实验,这两类数据共包含100个样本,每个样本包含四个特征,分别为萼片长度、萼片宽度、花瓣长度和花瓣宽度。实验采用五折交叉验证的方法,将SVM 、SVM KNN 、基于SVM 的多特征融合算法与基于SVM KNN 的多特征融合算法四种算法的分类准确率作对比。实验中支持向量机核函数采用高斯径向基核函数K (x,y )=exp {-x -y 2/2 2},惩罚参数C 取1000。实验结果如图3和4 所示。 图3 三种方法在不同特征选取方案下的分类准确率 图3中横轴表示各种不同的特征选取方案,共有11种选取方案,C1、C2、C3、C4分别表示萼片长度、萼片宽度、花瓣长度、花瓣宽度四种特征。如方案C1,C2表示选取萼片长度,萼片宽度两个特征,分别用S VM 、S VM KNN 、基于SVM KNN 的多特征融合分类方法三种方法进行分类,纵轴表示平均分类准确率。通过图3可以看出:11种特征选取方案中,基于S VM KNN 的多特征融合方法的分类正确率高于SV M 的有11种,等于或高于S VM KNN 的有8种。并且SVM KNN 和S VM 的所有融合方案的平均分类准确率分别只有81.3%和52.6%,而基于S VM KNN 的多特征融合分类方法的平均准确率为83.4%,分别比S VM 和SV M KNN 方法提高了28.7%和1.9%。同时,从最后一个融合方案C1,C2,C3,C4(选取样本的所有特征),可以看出只采用SVM 或S VM KNN 方法对测试样本进行分类的平均准确率为54%和79%,而基于S VM KNN 的多特征融合分类方法的分类准确率为87%,比S VM 和S VM KNN 准确率分别提高了32%和8%。从以上分析可以看出,基于SVM KNN 的多特征融合分类方法与S VM 或SVM KNN 分类方法相比有较高的准确率。 图4比较了基于S VM 和SV M KNN 两种分类器的多特征融合方法的分类准确率,横轴表示参与融合的特征选取方案,纵轴表示分类准确率。从图中可以看出,基于SV M KNN 的多特征融合方法的11种融合方案的分类准确率均高于基于SV M 的多特征融合方法,且基于S VM 的多特征融合方法的平均准确率只有70.8%,比基于SVM KNN 的多特征融合方法的平均准确率低12.6%。这表明基于S VM KNN 的多特征融合方法是一种比基于S VM 更有效的多特征融合方法。 与此同时,对比基于SVM KNN 的多特征融合分类方法中的11种融合方案,从C1,C3与C1,C2,C3,C1,C4与C1, C2,C4,C1,C3,C4与C1,C2,C3,C4的分类准确率可以看出 各种特征包含的信息之间并非完全互补,而是存在着一定的冲突。同时,通过统计分类准确度在85%以上的融合方案中各种特征出现的次数,以及由C3,C4与C1,C3,C4的分类准确率相等,可以说明花瓣长度和花瓣宽度是鸢尾属的主要特征,其他特征是辅助特征。 图4 基于SV M 和SV M KNN 的多特征融合分类方法准确率 5 结语 本文研究的基于S VM KNN 的多特征融合的方法,整合了多种特征信息,避免了单一分类器可能存在的片面性和在S VM 分类中核参数选择问题,在不增加支持向量机算法时间复杂度的基础上,降低了SVM 分类面附近样本点的错分率,提高了分类系统的总体性能,是一种有效的分类预测方法。同时也发现,参与融合的特征数据之间并非是完全互补的,而是存在着一定的冲突,如何选择合适的特征使它们间的信息互补达到最大化,是一个值得研究的问题。另外,如何将本文的算法从两分类推广到多分类,并将其运用到基因表达数据分类中是进一步要解决的问题。参考文献: [1] BATT I TI R ,COLLA M.D e mocracy i n neu ral n ets :V oti ng sche m es for cl assification [J].N eura lNet w orks ,1994,7(4):691-707.[2] HO T K,HULL J J ,SRI HARI S N.Decision co mb i n ati on i n mu lti p l e cl assifi er syste m s [J].IEEE Tran sacti ons on Pattern Ana l ysis and M ac h i n e In t elli gence ,1994,16(1):66-75.[3] CHO S B ,JI N H K.Co m b i n i ng mu ltiple n eural net w orks by f uzzy i n t egral for robu st clas s ification[J].IEEE T ran s acti ons on Syste m s ,M an and Cybernetics ,1995,25(2):380-384.[4] CHO S B,JI N H K.M u lti ple net w ork f u si on us i ng f u zz y l og i c[J ].I EEE T ran s acti on s on N eural Net w orks ,1995,6(2):497-501.[5] KI TTLER J ,HATEFM,DU I N R PW,et al .On co m b i n i ng cl assi fi ers[J].I EEE T ransacti on s on Patt ern Anal ys i s and M ach i ne Intel li gen ce ,1998,20(3):226-239. [6] 邓乃扬,田英杰.数据挖掘中的新方法 支持向量机[M ].北京:科学出版社,2004:45-76. [7] LI R,YE S W,SH I Z Z .SV M kNN cl assifier -A ne w m ethod of i m p roving the accuracy ofSV M cl assifier[J].A cta E l ectron i ca S i n i ca ,2002,30(5):745-748. [8] 施建宇,潘泉,张绍武,等.基于多特征融合的蛋白质折叠子预 测[J].北京生物医学工程,2006,25(5):482-485.[9] PLATT J C.Probab ili sti c outpu t s for s upport vector mac h i nes and co m pari son t o regu l ari zed li keli hood met hods [C ]//Advances i n Large M argi n C l assifi ers .C a m bri dge ,MA :M I T Press ,2000:61-74.[10]娄震,金忠,杨静宇.基于类条件置信变换的后验概率估计方法[J].计算机学报,2005,28(1):19-24.[11]RIC HAR D O D ,PETER E H,D AV I D G S .Pattern cl as s i fi cati on[M ].李宏东,姚天翔,等译.北京:机械工业出版社,2003:151-158. [12]业宁,王迪,窦立君.信息熵与支持向量的关系[J].广西师范大 学学报:自然科学版,2006,24(4):127-130. 835第3期陈丽等:基于支持向量机和k 近邻分类器的多特征融合方法 支持向量机（SVM ）原理及应用 一、SVM 的产生与发展 自1995年Vapnik (瓦普尼克)在统计学习理论的基础上提出SVM 作为模式识别的新方法之后，SVM 一直倍受关注。同年，Vapnik 和Cortes 提出软间隔(soft margin)SVM ，通过引进松弛变量i ξ度量数据i x 的误分类(分类出现错误时i ξ大于0)，同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数)，SVM 的寻优过程即是大的分隔间距和小的误差补偿之间的平衡过程；1996年，Vapnik 等人又提出支持向量回归 (Support Vector Regression ，SVR)的方法用于解决拟合问题。SVR 同SVM 的出发点都是寻找最优超平面(注：一维空间为点；二维空间为线；三维空间为面；高维空间为超平面。)，但SVR 的目的不是找到两种数据的分割平面，而是找到能准确预测数据分布的平面，两者最终都转换为最优化问题的求解；1998年，Weston 等人根据SVM 原理提出了用于解决多类分类的SVM 方法(Multi-Class Support Vector Machines ，Multi-SVM)，通过将多类分类转化成二类分类，将SVM 应用于多分类问题的判断：此外，在SVM 算法的基本框架下，研究者针对不同的方面提出了很多相关的改进算法。例如，Suykens 提出的最小二乘支持向量机 (Least Square Support Vector Machine ，LS —SVM)算法，Joachims 等人提出的SVM-1ight ，张学工提出的中心支持向量机 (Central Support Vector Machine ，CSVM)，Scholkoph 和Smola 基于二次规划提出的v-SVM 等。此后，台湾大学林智仁(Lin Chih-Jen)教授等对SVM 的典型应用进行总结，并设计开发出较为完善的SVM 工具包，也就是LIBSVM(A Library for Support Vector Machines)。LIBSVM 是一个通用的SVM 软件包，可以解决分类、回归以及分布估计等问题。 二、支持向量机原理 SVM 方法是20世纪90年代初Vapnik 等人根据统计学习理论提出的一种新的机器学习方法，它以结构风险最小化原则为理论基础，通过适当地选择函数子集及该子集中的判别函数，使学习机器的实际风险达到最小，保证了通过有限训练样本得到的小误差分类器，对独立测试集的测试误差仍然较小。 支持向量机的基本思想：首先，在线性可分情况下，在原空间寻找两类样本的最优分类超平面。在线性不可分的情况下，加入了松弛变量进行分析，通过使用非线性映射将低维输 第2章k-近邻算法(kNN) 引言 本章介绍kNN算法的基本理论以及如何使用距离测量的方法分类物品。其次，将使用python从文本文件中导入并解析数据，然后，当存在许多数据来源时，如何避免计算距离时可能碰到的一些常见的错识。 2.1 k-近邻算法概述 k-近邻(k Nearest Neighbors)算法采用测量不同特征之间的距离方法进行分类。它的工作原理是：存在一个样本数据集合，并且样本集中每个数据都存在标签，即我们知道样本每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签。一般来说，我们只选择样本数据集中前k 个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。 k-近邻算法的优点是精度高，对异常值不敏感，无数据输入假定；缺点是计算复杂度高、空间复杂度高。适用于数值和离散型数据。 2.1.1 准备知识：使用python导入数据 首先，创建名为kNN.py的python模块，然后添加下面代码： from numpy import * #引入科学计算包 import operator #经典python函数库。运算符模块。 #创建数据集 def createDataSet(): group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels=['A','A','B','B'] return group,labels 测试：>>> import kNN >>> group,labels=kNN.createDataSet() 注意：要将kNN.py文件放到Python27文件夹下，否则提示找不到文件。 2.2.2 实施kNN算法 使用k-近邻算法将每组数据划分到某个类中，其伪代码如下： 对未知类别属性的数据集中的每个点依次执行以下操作： 1.计算已知类别数据集中的点与当前点之间的距离； 2.按照距离递增交序排序； 3.选取与当前点距离最小的k个点； 4.确定前k个点所在类别的出现频率； 5.返回前k个点出现频率最高的类别作为当前点的预测分类。 用欧氏距离公式，计算两个向量点xA和xB之间的距离： 例如，点(0, 0)与(1, 2)之间的距离计算为: python函数classify()程序如下所示： 基于机器学习算法的文本分类方法综述 摘要：文本分类是机器学习领域新的研究热点。基于机器学习算法的文本分类方法比传统的文本分类方法优势明显。本文综述了现有的基于机器学习的文本分类方法，讨论了各种方法的优缺点，并指出了文本分类方法未来可能的发展趋势。 1.引言 随着计算机技术、数据库技术，网络技术的飞速发展，Internet的广泛应用，信息交换越来越方便，各个领域都不断产生海量数据，使得互联网数据及资源呈现海量特征，尤其是海量的文本数据。如何利用海量数据挖掘出有用的信息和知识，方便人们的查阅和应用，已经成为一个日趋重要的问题。因此，基于文本内容的信息检索和数据挖掘逐渐成为备受关注的领域。文本分类(text categorization，TC)技术是信息检索和文本挖掘的重要基础技术，其作用是根据文本的某些特征，在预先给定的类别标记(label)集合下，根据文本内容判定它的类别。传统的文本分类模式是基于知识工程和专家系统的，在灵活性和分类效果上都有很大的缺陷。例如卡内基集团为路透社开发的Construe专家系统就是采用知识工程方法构造的一个著名的文本分类系统，但该系统的开发工作量达到了10个人年，当需要进行信息更新时，维护非常困难。因此，知识工程方法已不适用于日益复杂的海量数据文本分类系统需求[1]。20世纪90年代以来，机器学习的分类算法有了日新月异的发展，很多分类器模型逐步被应用到文本分类之中，比如支持向量机(SVM，Support Vector Machine)[2-4]、最近邻法(Nearest Neighbor)[5]、决策树(Decision tree)[6]、朴素贝叶斯(Naive Bayes)[7]等。逐渐成熟的基于机器学习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有所突破，取得了很好的分类效果。 本文主要综述基于机器学习算法的文本分类方法。首先对文本分类问题进行概述，阐述文本分类的一般流程以及文本表述、特征选择方面的方法，然后具体研究基于及其学习的文本分类的典型方法，最后指出该领域的研究发展趋势。 2．文本自动分类概述 文本自动分类可简单定义为：给定分类体系后，根据文本内容自动确定文本关联的类别。从数学角度来看，文本分类是一个映射过程，该映射可以是一一映射，也可以是一对多映射过程。文本分类的映射规则是，系统根据已知类别中若干样本的数据信息总结出分类的规律性，建立类别判别公式或判别规则。当遇到新文本时，根据总结出的类别判别规则确定文本所属的类别。也就是说自动文本分类通过监督学习自动构建出分类器，从而实现对新的给定文本的自动归类。文本自动分类一般包括文本表达、特征选取、分类器的选择与训练、分类等几个步骤，其中文本表达和特征选取是文本分类的基础技术，而分类器的选择与训练则是文本自动分类技术的重点，基于机器学习的文本分来就是通过将机器学习领域的分类算法用于文本分类中来[8]。图1是文本自动分类的一般流程。 支持向量机分类器 1 支持向量机的提出与发展 支持向量机( SVM, support vector machine )是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由V.Vapnik 等人在1995年首先提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。 根据Vapnik & Chervonenkis的统计学习理论 ,如果数据服从某个(固定但未知的)分布,要使机器的实际输出与理想输出之间的偏差尽可能小,则机器应当遵循结构风险最小化 ( SRM,structural risk minimization)原则,而不是经验风险最小化原则,通俗地说就是应当使错误概率的上界最小化。SVM正是这一理论的具体实现。与传统的人工神经网络相比, 它不仅结构简单,而且泛化( generalization)能力明显提高。 2 问题描述 2.1问题引入 假设有分布在Rd空间中的数据，我们希望能够在该空间上找出一个超平面(Hyper-pan),将这一数据分成两类。属于这一类的数据均在超平面的同侧，而属于另一类的数据均在超平面的另一侧。如下图。 比较上图，我们可以发现左图所找出的超平面（虚线），其两平行且与两类数据相切的超平面（实线）之间的距离较近，而右图则具有较大的间隔。而由于我们希望可以找出将两类数据分得较开的超平面，因此右图所找出的是比较好的超平面。 可以将问题简述如下： 设训练的样本输入为xi，i=1，…，l，对应的期望输出为yi∈{+1，-1}，其中+1和-1分别代表两类的类别标识，假定分类面方程为ω﹒x+b=0。为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足以下约束条件： 它追求的不仅仅是得到一个能将两类样本分开的分类面，而是要得到一个最优的分类面。 2.2 问题的数学抽象 将上述问题抽象为： 根据给定的训练集 K近邻算法 算法介绍： K最近邻(k-Nearest neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 模式识别课程大作业报告——支持向量机（SVM）的实现 姓名： 学号： 专业： 任课教师： 研究生导师： 内容摘要 支持向量机是一种十分经典的分类方法，它不仅是模式识别学科中的重要内容，而且在图像处理领域中得到了广泛应用。现在，很多图像检索、图像分类算法的实现都以支持向量机为基础。本次大作业的内容以开源计算机视觉库OpenCV为基础，编程实现支持向量机分类器，并对标准数据集进行测试，分别计算出训练样本的识别率和测试样本的识别率。 本报告的组织结构主要分为3大部分。第一部分简述了支持向量机的原理；第二部分介绍了如何利用OpenCV来实现支持向量机分类器；第三部分给出在标准数据集上的测试结果。 一、支持向量机原理概述 在高维空间中的分类问题实际上是寻找一个超平面，将两类样本分开，这个超平面就叫做分类面。两类样本中离分类面最近的样本到分类面的距离称为分类间隔。最优超平面指的是分类间隔最大的超平面。支持向量机实质上提供了一种利用最优超平面进行分类的方法。由最优分类面可以确定两个与其平行的边界超平面。通过拉格朗日法求解最优分类面，最终可以得出结论：实际决定最优分类面位置的只是那些离分类面最近的样本。这些样本就被称为支持向量，它们可能只是训练样本中很少的一部分。支持向量如图1所示。 图1 图1中，H是最优分类面，H1和H2别是两个边界超平面。实心样本就是支持向量。由于最优超平面完全是由这些支持向量决定的，所以这种方法被称作支持向量机（SVM）。 以上是线性可分的情况，对于线性不可分问题，可以在错分样本上增加一个惩罚因子来干预最优分类面的确定。这样一来，最优分类面不仅由离分类面最近的样本决定，还要由错分的样本决定。这种情况下的支持向量就由两部分组成：一部分是边界支持向量；另一部分是错分支持向量。 对于非线性的分类问题，可以通过特征变换将非线性问题转化为新空间中的线性问题。但是这样做的代价是会造成样本维数增加，进而导致计算量急剧增加，这就是所谓的“维度灾难”。为了避免高维空间中的计算，可以引入核函数的概念。这样一来，无论变换后空间的维数有多高，这个新空间中的线性支持向量机求解都可以在原空间通过核函数来进行。常用的核函数有多项式核、高斯核（径向基核）、Sigmoid函数。 二、支持向量机的实现 OpenCV是开源计算机视觉库，它在图像处理领域得到了广泛应用。OpenCV 中包含许多计算机视觉领域的经典算法，其中的机器学习代码部分就包含支持向量机的相关内容。OpenCV中比较经典的机器学习示例是“手写字母分类”。OpenCV 中给出了用支持向量机实现该示例的代码。本次大作业的任务是研究OpenCV中的支持向量机代码，然后将其改写为适用于所有数据库的通用程序，并用标准数据集对算法进行测试。本实验中使用的OpenCV版本是，实验平台为Visual 文本分类中的特征提取和分类算法综述 摘要：文本分类是信息检索和过滤过程中的一项关键技术，其任务是对未知类别的文档进行自动处理，判别它们所属于的预定义类别集合中的类别。本文主要对文本分类中所涉及的特征选择和分类算法进行了论述，并通过实验的方法进行了深入的研究。 采用kNN和Naive Bayes分类算法对已有的经典征选择方法的性能作了测试，并将分类结果进行对比，使用查全率、查准率、F1值等多项评估指标对实验结果进行综合性评价分析.最终，揭示特征选择方法的选择对分类速度及分类精度的影响。 关键字：文本分类特征选择分类算法 A Review For Feature Selection And Classification Algorithm In Text Categorization Abstract:Text categorization is a key technology in the process of information retrieval and filtering,whose task is to process automatically the unknown categories of documents and distinguish the labels they belong to in the set of predefined categories. This paper mainly discuss the feature selection and classification algorithm in text categorization, and make deep research via experiment. kNN and Native Bayes classification algorithm have been applied to test the performance of classical feature detection methods, and the classification results based on classical feature detection methods have been made a comparison. The results have been made a comprehensive evaluation analysis by assessment indicators, such as precision, recall, F1. In the end, the influence feature selection methods have made on classification speed and accuracy have been revealed. Keywords:Text categorization Feature selection Classification algorithm 毕业设计（论文）任务书 毕业设计（论文） 题目中文文本分类算法的设计及其实现 电信学院计算机系84班设计所在单位西安交通大学计算机系 西安交通大学本科毕业设计（论文） 毕业设计(论文)任务书 电信学院计算机系84 班学生丰成平 毕业设计(论文)工作自2013 年 2 月21 日起至2013 年 6 月20 日止毕业设计(论文)进行地点：西安交通大学 课题的背景、意义及培养目标 随着文本文件的增多，对其自动进行分门别类尤为重要。文本分类是指采用计算机程序对文本集按照一定的分类体系进行自动分类标记。文本分类器的设计通常包括文本的特征向量表示、文本特征向量的降维、以及文本分类器的设计与测试三个方面。本毕设论文研究文本分类器的设计与实现。通过该毕业设计，可使学生掌握文本分类器设计的基本原理及相关方法，并通过具体文本分类算法的设计与编程实现，提高学生的实际编程能力。 设计(论文)的原始数据与资料 1、文本语料库（分为训练集与测试集语料库）。 2、关于文本分类的各种文献（包括特征表示、特征降维、以及分类器设计）以及资料。 3、中科院文本分词工具(nlpir)。 4、文本分类中需要用到的各种分类方法的资料描述。 课题的主要任务 1．学习文本特征向量的构建方法及常用的降维方法。 2．学习各种分类器的基本原理及其训练与测试方法。 3．设计并编程实现文本分类器。 毕业设计（论文）任务书 4、对试验结果进行分析，得出各种结论。 5、撰写毕业论文。 6、翻译一篇关于文本分类的英文文献。 课题的基本要求(工程设计类题应有技术经济分析要求) 1、程序可演示。 2、对源代码进行注释。 3、给出完整的设计文档及测试文档。 完成任务后提交的书面材料要求(图纸规格、数量，论文字数，外文翻译字数等) 1、提交毕业论文 2、提交设计和实现的系统软件源程序及有关数据 3、提交外文资料翻译的中文和原文资料 主要参考文献： 自然语言处理与信息检索共享平台：https://www.doczj.com/doc/cf8277773.html,/?action-viewnews-itemid-103 Svm(支持向量机)算法：https://www.doczj.com/doc/cf8277773.html,/zhenandaci/archive/2009/03/06/258288.html 基于神经网络的中文文本分析（赵中原）：https://www.doczj.com/doc/cf8277773.html,/p-030716713857.html TF-IDF的线性图解：https://www.doczj.com/doc/cf8277773.html,/blog-170225-6014.html 东南大学向量降维文献：https://www.doczj.com/doc/cf8277773.html,/p-690306037446.html 指导教师相明 接受设计(论文)任务日期2013-02-21~2013-06-20 学生签名： 题目k-最近邻算法实现学生姓名 学生学号 专业班级 指导教师 2015-1-2 实验二 k-最近邻算法实现 一、实验目的 1.加强对k-最近邻算法的理解； 2.锻炼分析问题、解决问题并动手实践的能力。 二、实验要求 使用一种你熟悉的程序设计语言，如C++或Java，给定最近邻数k和描述每个元组的属性数n，实现k-最近邻分类算法，至少在两种不同的数据集上比较算法的性能。 三、实验环境 Win7 旗舰版 + Visual Studio 2010 语言：C++ 四、算法描述 KNN(k Nearest Neighbors)算法又叫k最临近方法。假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， KNN就是计算每个样本数据到待分类数据的距离。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待 分样本集来说，KNN 方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K 个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 1、 算法思路 K-最临近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。K-最临近分类基于类比学习，其训练样本由N 维数值属性描述，每个样本代表N 维空间的一个点。这样，所有训练样本都存放在N 维模式空间中。给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的K 个训练样本。这K 个训练样本是未知样本的K 个“近邻”。“临近性”又称为相异度（Dissimilarity ），由欧几里德距离定义，其中两个点 X （x1,x2,…,xn ）和Y （y1,y2,…,yn ）的欧几里德距离是： 2 222211)()()(),(n n y x y x y x y x D -+?+-+-= 未知样本被分配到K 个最临近者中最公共的类。在最简单的情况下，也就是当K=1时，未知样本被指定到模式空间中与之最临近的训练样本的类。 2、 算法步骤 初始化距离为最大值； 计算未知样本和每个训练样本的距离dist ； 得到目前K 个最临近样本中的最大距离maxdist ； 如果dist 小于maxdist ，则将该训练样本作为K-最近邻样本； 重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完； 统计K-最近邻样本中每个类标号出现的次数； 选择出现频率最大的类标号作为未知样本的类标号。 package com.vista; import java.io.IOException; import jeasy.analysis.MMAnalyzer; /** * 中文分词器 */ public class ChineseSpliter { /** * 对给定的文本进行中文分词 * @param text 给定的文本 * @param splitToken 用于分割的标记,如"|" * @return 分词完毕的文本 */ public static String split(String text,String splitToken) { String result = null; MMAnalyzer analyzer = new MMAnalyzer(); try { result = analyzer.segment(text, splitToken); } catch (IOException e) { e.printStackTrace(); } return result; } } 停用词处理 去掉文档中无意思的词语也是必须的一项工作,这里简单的定义了一些常见的停用词，并根据这些常用停用词在分词时进行判断。 package com.vista; /** * 停用词处理器 * @author phinecos * */ public class StopWordsHandler { private static String stopWordsList[] ={"的", "我们","要","自己","之","将","“","”","，","（","）","后","应","到","某","后","个","是","位","新","一","两","在","中","或","有","更","好",""};//常用停用词public static boolean IsStopWord(String word) { for(int i=0;i 支持向量机数据分类预测 一、题目——意大利葡萄酒种类识别 Wine数据来源为UCI数据库，记录同一区域三种品种葡萄酒的化学成分，数据有178个样本，每个样本含有13个特征分量。50%做为训练集，50%做为测试集。 二、模型建立 模型的建立首先需要从原始数据里把训练集和测试集提取出来，然后进行一定的预处理，必要时进行特征提取，之后用训练集对SVM进行训练，再用得到的模型来预测试集的分类。 三、Matlab实现 3.1 选定训练集和测试集 在178个样本集中，将每个类分成两组，重新组合数据，一部分作为训练集，一部分作为测试集。 % 载入测试数据wine,其中包含的数据为classnumber = 3,wine:178*13的矩阵,wine_labes:178*1的列向量 load chapter12_wine.mat; % 选定训练集和测试集 % 将第一类的1-30,第二类的60-95,第三类的131-153做为训练集 train_wine = [wine(1:30,:);wine(60:95,:);wine(131:153,:)]; % 相应的训练集的标签也要分离出来 train_wine_labels = [wine_labels(1:30);wine_labels(60:95);wine_labels(131:153)]; % 将第一类的31-59,第二类的96-130,第三类的154-178做为测试集 test_wine = [wine(31:59,:);wine(96:130,:);wine(154:178,:)]; % 相应的测试集的标签也要分离出来 test_wine_labels = [wine_labels(31:59);wine_labels(96:130);wine_labels(154:178)]; 3.2数据预处理 对数据进行归一化： %% 数据预处理 % 数据预处理,将训练集和测试集归一化到[0,1]区间 [mtrain,ntrain] = size(train_wine); [mtest,ntest] = size(test_wine); dataset = [train_wine;test_wine]; % mapminmax为MATLAB自带的归一化函数 [dataset_scale,ps] = mapminmax(dataset',0,1); dataset_scale = dataset_scale'; 文章编号:100228743(2004)0320075204 用于分类的支持向量机 黄发良,钟 智Ξ (1.广西师范大学计算机系,广西桂林541000; 2.广西师范学院数学与计算机科学系,广西南宁530001) 摘 要:支持向量机是20世纪90年代中期发展起来的机器学习技术,建立在结构风险最小化原理之上的支持向量机以其独有的优点吸引着广大研究者,该文着重于用于分类的支持向量机,对其基本原理与主要的训练算法进行介绍,并对其用途作了一定的探索. 关键词:支持向量机;机器学习;分类 中图分类号:TP181 文献标识码:A 支持向量机S VM (Support Vector Machine )是AT&T Bell 实验室的V.Vapnik 提出的针对分类和回归问题的统计学习理论.由于S VM 方法具有许多引人注目的优点和有前途的实验性能,越来越受重视,该技术已成为机器学习研究领域中的热点,并取得很理想的效果,如人脸识别、手写体数字识别和网页分类等. S VM 的主要思想可以概括为两点:(1)它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;(2)它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界. 1 基本原理 支持向量机理论最初来源于数据分类问题的处理,S VM 就是要寻找一个满足要求的分割平面,使训练集中的点距离该平面尽可能地远,即寻求一个分割平面使其两侧的margin 尽可能最大. 设输入模式集合{x i }∈R n 由两类点组成,如果x i 属于第1类,则y i =1,如果x i 属于第2类,则y i =-1,那么有训练样本集合{x i ,y i },i =1,2,3,…,n ,支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开来,通常分为两类情况来讨论,(1)线性可分,(2)线性不可分. 1.1 线性可分情况 在线性可分的情况下,就会存在一个超平面使得训练样本完全分开,该超平面可描述为: w ?x +b =0(1) 其中,“?”是点积,w 是n 维向量,b 为偏移量. 最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面.最优超平面可以通过解下面的二次优化问题来获得: min <(w )= 12‖w ‖2(2) Ξ收稿日期:2004202206作者简介:黄发良(1975-),男,湖南永州人,硕士研究生;研究方向:数据挖掘、web 信息检索. 2004年9月 广西师范学院学报(自然科学版)Sep.2004 第21卷第3期 Journal of G u angxi T eachers Education U niversity(N atural Science Edition) V ol.21N o.3 基于支持向量机的分类方法 摘要：本文首先概述了支持向量机的相关理论，引出了支持向量机的基本模型。当训练集的两类样本点集重合区域很大时，线性支持向量分类机就不适用了，由此介绍了核函数相关概念。然后进行了核函数的实验仿真，并将支持向量机应用于实例肿瘤诊断，建立了相应的支持向量机模型，从而对测试集进行分类。最后提出了一种支持向量机的改进算法，即根据类向心度对复杂的训练样本进行预删减。 1、支持向量机 给定训练样本集1122{[,],[,], ,[,]}()l l l T a y a y a y Y =∈Ω?L ，其中n i a R ∈Ω=，Ω是输入空间，每一个点i a 由n 个属性特征组成，{1,1},1,,i y Y i l ∈=-=L 。分类 就是在基于训练集在样本空间中找到一个划分超平面，将不同的类别分开，划分超平面可通过线性方程来描述： 0T a b ω+= 其中12(;;;)d ωωωω=K 是法向量，决定了超平面的方向，b 是位移项，决定 了超平面与原点之间的距离。样本空间中任意点到超平面的距离为|| |||| T a b r ωω+=。 支持向量、间隔： 假设超平面能将训练样本正确分类，即对于[,]i i a y T ∈，若1i y =+，则有 0T i a b ω+>，若1i y =-，则有0T i a b ω+<。则有距离超平面最近的几个训练样本点使得 11 11 T i i T i i a b y a b y ωω?+≥+=+?+≤-=-? 中的等号成立，这几个训练样本点被称为支持向量；两个异类支持向量到超平面 的距离之和2 |||| r ω=被称为间隔。 支持向量机基本模型： 找到具有最大间隔的划分超平面，即 ,2max ||||..()1,1,2,...,b T i i s t y a b i m ωωω+≥= 这等价于 2 ,||||min 2..()1,1,2,...,b T i i s t y a b i m ωωω+≥= 这就是支持向量机（SVM ）的基本模型。 支持向量机问题的特点是目标函数2 ||||2 ω是ω的凸函数，并且约束条件都是 线性的。 支持向量机(SVM)原理及应用 一、SVM得产生与发展 自1995年Vapnik(瓦普尼克)在统计学习理论得基础上提出SVM作为模式识别得新方法之后,SVM一直倍受关注。同年,Vapnik与Cortes提出软间隔(soft margin)SVM,通过引进松弛变量度量数据得误分类(分类出现错误时大于0),同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数),SVM得寻优过程即就是大得分隔间距与小得误差补偿之间得平衡过程;1996年,Vapnik等人又提出支持向量回归 (Support Vector Regression,SVR)得方法用于解决拟合问题。SVR同SVM得出发点都就是寻找最优超平面(注:一维空间为点;二维空间为线;三维空间为面;高维空间为超平面。),但SVR得目得不就是找到两种数据得分割平面,而就是找到能准确预测数据分布得平面,两者最终都转换为最优化问题得求解;1998年,Weston等人根据SVM原理提出了用于解决多类分类得SVM方法(MultiClass Support Vector Machines,MultiSVM),通过将多类分类转化成二类分类,将SVM应用于多分类问题得判断:此外,在SVM算法得基本框架下,研究者针对不同得方面提出了很多相关得改进算法。例如,Suykens 提出得最小二乘支持向量机(Least Square Support Vector Machine,LS—SVM)算法,Joachims等人提出得SVM1ight,张学工提出得中心支持向量机 (Central Support Vector Machine,CSVM),Scholkoph与Smola基于二次规划提出得vSVM等。此后,台湾大学林智仁(Lin ChihJen)教授等对SVM得典型应用进行总结,并设计开发出较为完善得SVM工具包,也就就是LIBSVM(A Library for Support Vector Machines)。LIBSVM就是一个通用得SVM软件包,可以解决分类、回归以及分布估计等问题。 二、支持向量机原理 SVM方法就是20世纪90年代初Vapnik等人根据统计学习理论提出得一种新得机器学习方法,它以结构风险最小化原则为理论基础,通过适当地选择函数子集及该子集中得判别函数, 使学习机器得实际风险达到最小,保证了通过有限训练样本得到得小误差分类器,对独立测试集得测试误差仍然较小。 支持向量机得基本思想:首先,在线性可分情况下,在原空间寻找两类样本得最优分类超平面。在线性不可分得情况下,加入了松弛变量进行分析,通过使用非线性映射将低维输入空 K近邻分类算法（K –nearest neighbors，简称KNN） 1算法的提出与发展 最初的近邻法是由Cover和Hart与1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。 2算法原理 2.1 基本原理 最近邻方法(k-nearest neighbor,简称kNN)是一种简洁而有效的非参数分类方法，是最简单的机器学习算法之一，该算法最初由Cover和Hart提出的，用于解决文本的分类问题。 K 近邻算法是最近邻算法的一个推广。该规则将是一个测试数据点x分类为与它最接近的K 个近邻中出现最多的那个类别。K 近邻算法从测试样本点x开始生长，不断的扩大区域，直到包含进K 个训练样本点为止，并且把测试样本点x归为这最近的K 个训练样本点中出现频率最大的类别。其中测试样本与训练样本的相似度一般使用欧式距离测量。 如果K 值固定，并且允许训练样本个数趋向于无穷大，那么，所有的这K 个近邻都将收敛于x。如同最近邻规则一样，K 个近邻的标记都是随机变量，概率P（w i|x），i=1,2,…,K 都是相互独立的。假设P（w m|x）是较大的那个后验概率，那么根据贝叶斯分类规则，则选取类别w m。而最近邻规则以概率P（w m|x）选取类别。而根据K近邻规则，只有当K个最近邻中的大多数的标记记为w m，才判定为类别w m。做出这样断定的概率为 通常K值越大，选择类别w m概率也越大。 2.2K值的选择 K近邻规则可以被看作是另一种从样本中估计后验概率P（w i|x）的方法。为了得到可高的估计必须是的K值越大越好。另一方面，又希望又希望x的K 个近邻x 距离x1越近越好，因为这样才能保证P（w i|x1）尽可能逼近P（w i|x）。在选取K 值的时候，就不得不做出某种折衷。只有当n趋近于无穷大时，才能保证K 近邻规则几乎是最优的分类规则。 K值的选择：需要消除K值过低，预测目标容易产生变动性，同时高k值时，预测目标有过平滑现象。推定k值的有益途径是通过有效参数的数目这个概念。有效参数的数目是和k值相关的，大致等于n/k，其中，n是这个训练数据集中实例的数目。 确定K的值：通过实验确定。进行若干次实验，取分类误差率最小的k值。 2.3算法步骤 1)依公式计算Item 与D1、D2 ……、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)……、Sim(Item, Dj)。 2)将Sim(Item, D1)、Sim(Item, D2)……、Sim(Item, Dj)排序，若是超过相似度门槛t则放入 邻居案例集合NN。 3)自邻居案例集合NN中取出前k名，依多数决，得到Item可能类别。 3KNN优缺点 优点：1）原理简单，实现起来比较方便； 2）支持增量学习； K近邻分类的算法实现 K近邻（KNN）法的输入为实例的特征向量，对应于特征空间的点；输入为实例的类别，可以取多类。K近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此K近邻不具有显式的学习过程。K近邻法实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 1.1 选题背景 现如今，数据的爆炸式增长、广泛可用和巨大数量使得我们的时代成为真正的数据时代。急需功能强大和通用的工具，以便从这些海量数据中发现有价值的信息，把这些数据转化成有组织的知识。这种需求导致了数据挖掘的诞生。这个领域是年轻的、动态变化的、生机勃勃的。数据挖掘已经并且将继续在我们从数据时代大步跨入信息时代的历程中作出贡献。 K近邻方法是20世纪50年代早期首次引进的。当给定大量数据集时，该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后它广泛用于模式识别领域。 K近邻分类法是基于类比学习，即通过将给定的检验元组与它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，k近邻分类法搜索模式空间，找出最接近元组的k个训练元组。这k个训练元组即为该元组的k个“最近邻”。 1.2 研究现状 国内外学者为此算法在实际生活中更好地应用做出了许多努力。例如对k近邻方法的不足做出的一些改进如文献[2]，[7]，[8]，[9]，[10]等等。在其他领域的应用如文献[5]将K近邻算法改进为非线性分类算法，以达到分类动态心电图波形的目的。文献[6]在KNN算法的基础上提出了图像自动分类模型。在生物学上，K近邻方法也得到了广泛地应用，有文献利用蛋白质相互作用网络,提出 支持向量机SVM分类算法 SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中[10]。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力[14]（或称泛化能力）。 以上是经常被有关SVM 的学术文献引用的介绍，我来逐一分解并解释一下。 Vapnik是统计机器学习的大牛，这想必都不用说，他出版的《Statistical Learning Theory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统完全成了一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。 结构风险最小听上去文绉绉，其实说的也无非是下面这回事。 机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的（如果知道了，我们干吗还要机器学习？直接用真实模型解决问题不就可以了？对吧，哈哈）既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模型到底是什么。 这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛(完整word版)支持向量机(SVM)原理及应用概述分析
k近邻分类算法
基于机器学习的文本分类方法
支持向量机分类器
基于K近邻的分类算法研究-WORD
支持向量机的实现
文本分类中的特征提取和分类算法综述
中文文本分类算法设计及其实现_毕业设计
k最近邻算法实验报告
贝叶斯算法(文本分类算法)java源码
支持向量机数据分类预测
用于分类的支持向量机
基于支持向量机的分类方法
支持向量机(SVM)原理及应用概述
K近邻分类算法
K近邻分类的算法实现
支持向量机SVM分类算法
相关主题
文本预览