加权KNN算法（精选4篇）
加权KNN算法 篇1
摘要：KNN文本分类算法是一种简单、有效、非参数的分类方法。针对传统的KNN文本分类算法的不足,出现了很多改进的KNN算法。但改进的KNN分类算法大多数是建立在样本选择的基础上。即以损失分类精度换取分类速度。针对传统的KNN文本分类算法的不足,提出一种基于特征加权的KNN文本分类算法(KNNFW),该算法考虑各维特征对模式分类贡献的不同,给不同的特征赋予不同的权值,提高重要特征的作用,从而提高了算法的分类精度。最后给出实验结果并对实验数据进行分析得出结论。
关键词：特征加权,K最近邻,文本分类,特征选取
1 引言
KNN文本分类算法的基本思想是根据传统的向量空间模型,文本内容被形式化为特征空间中的加权特征向量,即D=D(T1,W1;T2,W2;…;Tn,Wn)[1]。对于一个测试文本,计算其与训练样本集中每个文本的相似度,找出K个最相似的文本,根据加权距离和判断测试文本所属的类别。KNN算法是一种优秀的分类算法,但KNN算法同样存在着不足:一是对于高维文本向量样本规模较大时,算法的时间和空间复杂度较高,其时间复杂度为O(n*m),n为VSM空间特征维数,m为样本集大小;二是当新待分类样本到来时,每次都要计算其与所有训练样本的距离(或相似度),这就大大降低了算法的效率[2]。
针对传统的KNN文本分类算法的不足,出现了很多改进的KNN算法,目前主要通过两种途径来减小KNN算法的计算量。一种是通过对高维文本向量进行降维处理,采用的方法主要有:基于潜在语义分析的方法(LSA)[3]、基于特征向量聚合的方法[4]、基于特征选择的方法等[5]。另一种加快KNN算法分类速度的改进办法就是通过使用小样本库代替原来的大样本库进行分类。这类方法一般是在原来的训练样本库中选取一些代表样本作为新的训练样本,或删除除原来的训练样本库中的某些样本,将剩下的样本作为新的训练样本库,从而达到减小训练样本库的目的。这种途径最主要的方法有Hart的Condensing算法、WilSon的Editing算法和H.V.Jagadish的iDistance算法。
KNN分类算法以及改进的KNN分类算法大多数是建立在样本选择的基础上,即以损失分类精度换取分类速度。本文提出一种基于特征加权的KNN改进算法(KNN-FW),该算法考虑各维特征对模式分类贡献的不同,给不同的特征赋予不同的权值,提高重要特征的作用,从而提高了算法的分类精度。
2 基于特征加权的KNN文本分类算法
2.1 基本思想
KNN算法认为各维特征对分类的贡献是相同的,而事实上,构成样本特征矢量的各维特征来自不同的样本,存在量纲差异,精度及可靠性也可能不同,而且所选择的特征集也未必适合于模式的分类。鉴于此,将探讨一种改进的K最近邻算法,该算法考虑各维特征对模式分类的不同贡献,以便获得更有效的分类效果。
设一个给定的测试样本为t,特征为f,定义在特征f上的最近邻算法为KBag(f,t,k),该函数计算测试样本t在特征f权值上最近的K个邻居。然后对每一个类别进行K次投票,因此每一特征维度上就有K次的投票机会。测试样本的类别由这些特征上的K次投票结果综合决定。
2.2 特征选取
构成文本的词汇,数量是相当大的,因此表示文本的向量空间的维数也相当大,可以达到几万维,因此需要进行维数压缩的工作。目前对文档特征所采用的特征子集选取算法一般是构造一个评价函数,对特征集中的每一个特征进行独立的评估,这样每个特征都获得一个评估分,然后对所有的特征按照评估分的大小排序,选取预定数目的最佳特征作为结果的特征子集。一般采用的评估函数有信息增益[6]、互信息[7]、期望交叉熵[8]、χ2统计[9]、文本证据权、文档频次[10]和几率比等。针对论文抄袭检测问题,实验表明采用信息增益评估函数效果较好[11]。
权重的计算采用TFIDF公式,其中TF是特征项在文本中的绝对频率,而IDF表示特征项在文本中的文本内频数。不过纯粹选取权重值最大的前N个特征词汇作为训练样本特征库的方法,往往存在训练样本“不可描述”的问题,即部分训练文本不包含任何选取出的特征项。改进方法是在每个训练类别中抽取权重值最大的一定数量的词汇共同构成训练样本特征库,这样调整后训练文本特征库对于每个训练类别文档都能实现充分描述。每个训练类别抽取特征词的数量可以根据需要的总体特征维数决定。特征数也不是越多越好,有时特征数太多反而会影响分类的精度。在实验时发现特征数在1000~1500时,效果较好,这时对于每个训练类别抽取权重值最大的前200个词汇,稍加筛选共同构成训练样本特征库。
2.3 特征权值的确定
采用ReliefF算法来确定特征的权值。基本的Relief算法[12]是Kira和Rendell在1992年提出的,仅适用于训练样本是两类的情况。1994年Kononemko[13]扩展了Relief算法,得到ReliefF算法,RelliefF可以解决多类样本分类问题。
设X=邀x1,x2,…,xn妖是待分类的对象全体,其中xi=邀xi1,xi2,…,xiN妖表示第i个样本的N个特征值。对于任意的一个样本xi,首先找出R个与xi同类的最近邻样本hj,j=1,2,…,R,然后在每一个与xi不同类的子集中找出R个最近邻的样本mij,j=1,2,…R,l≠class(xj)设diff_hit是N×1的矩阵,表示hj与xi在特征上的差异,对于特征权重,表示为:
设diff_miss是N×1的矩阵,表示mij与xi在特征上的差异。对于特征权重,表示为:
P(l)为第l类出现的概率,可以用第l类的样本数比上数据集中的总数。若用λ表示各维特征的权值,λ是N×1的矩阵,则ReliefF算法中λ由下式更新:
如此重复若干次,就可以得到特征集中每一个特征的权值。
2.4 KNNFW文本分类算法流程
KNNFW文本分类算法流程和传统KNN文本分类方法流程差不多,主要的区别在于特征词的权重不同以及分类算法不同。KNNFW文本分类算法流程如图1所示。
文本的预处理包括分词和去除停用词等,预处理后在初步选取特征词的基础上进一步进行特征加权计算,根据加权的结果进行训练和分类,其中具体分类算法的实现如下:
输入:t测试样本,k最近邻个数。
输出:测试样本的类别。
(1)初始化阶段,对于每一个类别c设置投票结果为零,vote[c]=0。
(2)对于每一个特征f,计算每一个特征的k个邻居,Bag=kBag(f,t,k)。
(3)对于每一个类别c,分别计算它们的投票结果:
(4)最后判断各类投票结果vote[c]中的最大值,将最大值所对应类别作为测试样本t的类别ct。
其中count(c,Bag)函数计算特征f的k个邻居中类别为c的个数,W[f]为特征f的权值。
3 实验结果与分析
3.1 实验结果
为了验证算法的有效性和正确性,选取了2287个文本文件,共14个类别,包括:计算机、医药、经济、环境、军事、艺术、体育、教育、交通、政治、建筑、金融、宗教和电子商务等,作为训练集,并从中选取一部分作为测试集。训练样本、测试样本的分布情况如表1。
由于样本数和类别都不多,特征词取1500,特征初步选取策略采用信息增益评估函数,采用ReliefF算法来进一步确定特征的权值,K值取35。KNN和基于KNNFW两种文本分类法对比实验结果如表2。
3.2 基本结论
由以上实验结果可以看出,传统KNN文本分类法查准率和查全率都较低;而采用基于特征加权的KNN文本分类算法大大提高了查准率和查全率。同时,在每个训练类别中抽取权重值最大的一定数量的词汇共同构成训练样本特征库,可以避免由于训练样本分布不均匀而影响分类效果。另外,特征词的数量和K值的大小对实验结果有一定影响,但由于没有固定计算公式,因此只有通过实验确定较为合适的特征词数与K值。
4 结束语
针对传统KNN文本分类算法中假设各维特征对分类的贡献相同导致分类性能下降这一不足,提出一种基于特征加权的KNN文本分类算法。基于特征加权的KNN文本分类算法利用ReleifF计算特征权重,考虑了各种特征对分类贡献的大小,使得改进算法对文本的分类性能大大提高。同时改进算法还有助于分析各维特征对分类的贡献程度,可以有效地进行特征提取与优选,这在实际应用中是非常方便的。通过具体实验验证,基于特征加权的KNN分类算法和传统KNN分类算法相比,明显提高了查准率和查全率。基于特征加权的KNN分类算法具有很强的推广能力,不仅适合于文本分类,同样也适用于其它应用领域的分类。
一种加权的ML-kNN算法 篇2
问题转化法的主要思想是根据一定的规则将多标签问题转化为一个或多个单标签问题,再利用传统的单标签学习算法[9]进行处理。利用标签的一对一二元关系[10]或一对多二元关系[11]将多标签问题转换为单标签问题,思想虽然简单,易于实现,但标签之间还可能存在其他关系。标签超集转化法是将标签集的非空子集作为新标签的另一种转换方法[12][13],但对标签数较多的数据集,由于新标签数的指数增长,不但增加了问题的复杂度,还使某些新标签的样本覆盖率极低,从而严重影响学习效率及效果。
算法适应法主要是通过扩展传统的单标签学习算法来适用于多标签学习问题。包括修改信息熵的计算公式[6]的C4.5决策树算法,扩展AdaBoost算法的AdaBoost.MH[1]和AdaBoost.MR[1],结合SVM分类器和标签二元关系问题转化法的算法[2],基于关联分类的范式的MMAC算法[14]以及ML-kNN算法[5]等。
1 ML-kNN算法
张敏灵等人提出的ML-kNN算法引入贝叶斯概率将kNN的分类函数修改为:
其中Hbj为样本xi属于(b=1)及不属于(b=0)标签j的假设,EjCi(j)为样本xi的邻居中恰好有Ci(j)个邻居属于标签j的事实。其中Ci(j)为样本xi的邻居中属于标签j的邻居数。对各标签,概率P(Hbj)和P(EjCi(j)|Hbj)通过统计频数得到。
ML-kNN算法是一种简单但非常有效地解决多标签问题的方法。然而,由于它仅统计各标签在邻居中出现的频数,而不能很好处理标签分布不均匀的数据集。因此,本文利用距离加权对ML-kNN算法进行改进。
2 加权ML-kNN算法
对多标签数据的每个标签,含该签的数据构成一个聚类。通常属于同一聚类的数据分布相对集中,而属于不同聚类的数据分布相对分散。首先将同一聚类中的任意两个数据之间的平均距离作为该聚类的密度。在未知样本和k个邻居构成的局部,针对各标签,为那些到未知数据的距离与聚类密度相近的邻居赋予较大的权值;相反,为那些到未知数据的距离与聚类密度不相近的邻居赋予较小的权值。其次,同时考虑不含有某标签的邻居对未知数据标签分布的影响,则加权ML-kNN的分类函数为:
其中E͂kj-Ci(j)为样本xi的邻居中恰好有k-Ci(j)个邻居不属于标签j的事实,与EjCi(j)互补,因此P(E͂kj-Ci(j))=P(EjCi(j)),Pw表示加权的概率值。
3 实验与分析
3.1 实验设置
三个基准数据集的详细信息如表2所示。其中标签的势为样本的平均标签个数,标签密度为标签的势与标签总数的比值。
3.2 评测指标
表3给出常用的七种评测指标,前四种为基于标签排序的指标,后三种为基于分类的指标。给定多标签训练集S={(xi,Yi)}(i=1,2,...,m),其中xi∈χ,Yi⊆ψ。
3.3 实验结果
表4给出加权ML-kNN算法(记作W-ML-kNN)和ML-kNN算法在三个基准数据集上的对比实验结果。值为所有k=5,...,14时的平均值,Win(s)表示七个评测指标中各算法取最优值的次数,例如1(7),表示7项比较中有1项指标最优。
从表4中可以看出,加权ML-kNN算法取得最优值的次数较多。在基于标签排序的指标上加权ML-kNN算法明显优于ML-kNN算法,而在基于分类的指标上加权算法的改进效果不明显。这是因为距离权值更使各标签的概率更精确,即改善了标签排序效果;同时由于赋予那些覆盖率较低但与聚类密度相近的标签较高的权值,降低了这些标签的错分率,但为样本分配了更多的标签,而降低了Precision和Recall。整体上,加权ML-kNN算法在仅增加计算权值的线性时间复杂度的基础上很大程度地改进了ML-kNN算法的学习效果。
注:↑表示值越大效果越好,↓表示值越小效果越好
4 结束语
一种快速KNN文本分类算法 篇3
但是KNN算法是一种典型的消极学习方法(lazy learning)[3],在训练阶段仅仅存储所有的训练实例,所有的计算都延迟到分类阶段进行,对于高维文本向量或样本集规模较大的情况,庞大的计算量将严重影响分类速度。其实,效率问题一直是阻碍KNN及其变体推广应用的一个重要的实践问题,针对这个问题,目前的改进办法主要分为三类:1)对文本样本特征空间降维。但是这种方法所能减少的计算量有限,并且有可能会影响分类的准确率。2)用提取代表样本等方法缩小样本库[4]。这类方法对于小样本库来说,效果明显,但对于大样本库,其工作量相当巨大。3)提高高维向量空间的KNN检索效率[5]。这类方法都有一定的局限性,要么往往不可避免地遭遇“维数灾难”困扰[6],不能很好地应用于高维(超过几十维)数据空间检索[7];要么只是适用于近似检索要求,不能保证较高的KNN检索精度。
然而,以前的算法都忽略了文本向量在空间里具体的分布情况。文本向量的分布表现出某种聚集性,即同类的文本向量大部分都分布在同一区域里,而不同类的文本向量大部分会分布在不同的区域里。据此,本文提出了一种基于分布域的快速KNN分类方法。改进算法能找到并计算出每个类的分布域,参照待分类文本向量的空间位置,相对于传统KNN,只需要少量的计算就能判断其归属。实验表明,改进算法能在基本不影响原有算法准确率的情况下,大大提高文本的分类速度,并可应用于高维文本向量或样本集规模较大的情况。
1 基本概念
1.1 向量空间模型
向量空间模型(VSM)是近年来应用最多且效果较好的文档表示法之一。在该模型中,文档空间被看作是由一组正交词条向量所组成的向量空间,每个文档d表示为其中的一个范化特征向量V(d)=(t1,W1(d)),…ti,Wi(d),…tn,Wn(d)),其中ti为词条项,Wi(d)为ti在d中的权值。Wi(d)一般被定义为ti在d中出现频率tfi(d)的函数,即Wi(d)=δ(tfi(d))。常用的δ有平方根函数,对数函数,布尔函数和TFIDF(词频-逆向文本频率)函数等。TFIDF是目前最常用的一种权重函数,δ=tfi(d)log(N/ni),其中N为所有文档数目,ni为含有词条ti的文档数目,它不仅考虑了词在单个文档中的局部权值,还考虑到词在整个文档库的全局权值,因而更合理、更准确。
2.2基于KNN的文本分类方法
KNN最初由Cover和Hart于1968年提出,是一种理论上比较成熟的方法。该算法的基本思想是:根据传统的向量空间模型,文本内容被形式化为特征空间中的加权特征向量。对于一各待分类文本,计算出它与样本集中每个文本的相似度,找出K个最相似的文本,根据加权距离之和来判断待分类文本的所属类别。算法的具体步骤如下:
1)根据特征向量,把一个待分类文本表示成向量d。
2)计算d与样本集S中每个文本向量的相似度(通常为欧式距离或者是余弦距离),选择与d相似度最大的k个样本向量作为d的k个最近邻。
3)计算出d属于每个类的权重W,d属于类Cj的权重计算公式为:
其中sim(di,d)是d的k个最近邻中样本di之间的相似度,而φ(di,Cj)的取值为1或者0,如果di∈Cj,则函数值为1,反之则为0。
4)比较权重,将待分类样本d归属于权重最大的那个类别。
2 基于分布域的KNN文本分类方法
2.1 基本概念
为了刻画文本向量在空间中的分布,我们引入分布域的概念:
定义1(分布域):在文本向量空间中,若存在子空间,使得类C中的文本向量全部分布于其中,那么称满足条件的最小子空间为C的分布域。
2.2 改进的KNN算法
改进算法的步骤:1)计算出每个类的分布域;2)计算出待分类文本向量u在样本空间中的位置;3)看u位于哪些类的分布域之外,在计算u的K个最近邻向量时,排除与这些类中所有向量之间的距离计算,计算完毕后,根据公式(1)判定u的归属,算法结束。
改进算法分析:u的K近邻搜索范围会由于它落在一些类的分布域之外而被缩小,从而使分类的效率与传统KNN相比得到提高。同时根据定义1,在计算u的K最近邻向量时排除的都是其不可能属于的类,所以不会影响准确率。
2.3 分布域的计算方法
我们可以跟据训练样本来计算各类的分布域,但是训练样本总是有限的,再有其中难免会存在的噪音数据,这样使得在实践中只能找到各类分布域的近似值,从而影响到改进算法的分类准确率,但总体来说这并不妨碍改进算法的实用性,下面介绍本文使用的计算方法。
设T为样本集中全体文本向量集合,分布在m维的样本空间V中,其中共有n个类,分别用C1,C2,…Ci…Cn表示;类Ci的中心向量表示为O(Ci)。用S(O(Ci),r)表示样本空间中以O(Ci)为中心、r为半径的超球空间,分布于其中的文本向量集用E(S(O(Ci),r))表示。
我们根据大量的实验数据得知T中文本向量的空间分布有如下的规律:Ci中的大部分向量聚集在O(Ci)的周围,总体来说比其他类中的向量与O(Ci)的距离近。随着r的减小,E(S(O(Ci),r))中的属于类Ci的文本向量比率会变高,反之则会变低。
根据这种规律,我们用如下方式计算各类的分布域的近似值:设定阈值t(0
计算r的算法:
其中,D里存放的是按照与O(C)之间距离升序排列的训练样本集T内各向量,N是C中的向量个数,Num(i)代表D中前i个向量里属于C的个数,dist(νi,O(C)代表νi与O(C)之间的距离。
3 实验结果
我们实现了本文的算法并设计了实验,分别考察了t的取值对算法效率和准确率的影响,并在总体上分析了算法的有效性。实验采用了搜狐新闻语料库,包含IT,财经,体育等共9个类,16049篇文档。生成文本向量时,特征加权算法为TFIDF,维数为1000。改进算法的效率、准确率均和传统KNN做比较,K值取50,权重判定公式(1)中相似度函数sim(di,d)取两个向量之间的余弦。
由图1和图2可以看出,随着t的增大,效率会逐渐提高,但是随着计算出的各类分布域的缩小,使得准确率直线下降,这是因为很多文本向量被排除在了本类分布域之外,计算K最近邻的结果偏离原始取值的程度不断加大所致。t的不同取值会使得改进算法有不同的效率和准确率,只有合理的选取t值,才能使改进算法具有实用性,通过实验发现t=0.04时,改进算法的效果最好,准确率不至于下降太多,同时效率能有相当大的提高。可以看到,相对于传统KNN,改进的算法可以做到在准确率损失不到2%的情况下,提高70%以上的效率。
总之,在阈值选取合理的情况下,改进的算法可以在基本不影响的准确率的同时提高KNN的效率,但如果超过这个范围,虽然可以提高效率,但是准确率会急剧下降,使算法变得不实用。
4 结束语
本文提出了一种基于粗糙集的KNN快速分类算法。根据文本向量在空间的分布特点,计算出各类的分布域,在寻找待分类文本向量的K最近邻时,可以少做对样本集的搜索,从而大大提高了KNN的效率。
参考文献
[1]Yang Y.Expert network:Effective and efficient learning from human decisions in text categorizations in text categorization and retrieval[C]//The17th International ACM SIGIR Conference on Research and development in Information Retrieval,1994:13-22.
[2]Aha D W,Kibler D,Albert M K.Instance-based learning algorithms[J].Machine Learning,1991(6):37-66.
[3]Aha D W.Lazy learning[M].Dordrecht:Kluwer Academic,1997.
[4]王晓烨,王正欧.K-最近邻分类技术的改进算法[J].电子信息学报,2005,27(3):487-491.
[5]Hjaltason G R,Hanan S.Index-driven similarity search in metric spaces[J].ACM Trans.on Database Systems,2003,28(4):517-580.
[6]Hinneburg A,Aggarwal C C,Keim D A.What is the nearest neighbor in high dimensional spaces[C]//The26th International Conference on Very Large Data Bases,Cairo,Egypt,2000:506-515.
一种改进的KNN网页分类算法 篇4
网页分类中的经典算法包括类中心法、Naive-Bayes法、支持向量机(Support Vector Machine,简称SVM)、K-近邻算法(K-Nearest Neighbor,简称KNN)算法等。CMU的Yim Yang等人通过实验证明KNN算法是应用于网页分类最有效的方法[2]。KNN算法具有训练时间短,分类精度高的优点,但是也存在着一定程度的缺陷。它是典型的懒惰分类算法,对于分类所需的时间都推迟到分类时才进行,由于缺少了训练过程,所有的学习过程都集中在与整个数据集计算比较上,当训练数据集比较大时,计算开销很大,不适用于在线的实时分类。并且该算法对样本的分布情况比较敏感,样本分布不均匀会造成分类准确率的下降。本文将研究KNN的数据集优化策略,提出一种生成代表样本的方法。
1 KNN算法
1.1 KNN算法简介
经实验论证,在VSM模型下,KNN被认为是分类性能最好的分类算法[2]。有别以于其他分类算法,KNN算法不需要在训练过程中对分类器进行学习和训练,它能够对测试文档向量直接进行分类计算。算法步骤如下[2,3]:
(1)根据特征项集合重新描述训练文本向量;
(2)在新文本到达后,对新文本分词,并进行向量表示;
(3)计算训练集中所有样本与新文本的相似度,选出与新文本最相似的K个文本,相似度计算公式如下:undefined
(4)在新文本的K个邻居中,根据公式(2)[3]依次计算新文本相对于每类的权重:
undefined
其中,undefined为新文本的特征向量; Sim(undefined,undefinedi)为相似度计算公式,而y(undefinedi,Cj)为类别属性函数,即:如果di属于类Cj,那么函数值为1,否则为0,bj为预先计算得到的Cj的最优截尾阈值;
(5) 比较类的权重,将文本分到权重最大的那个类别中。
分析KNN的分类过程可知:(1)这些步骤大部分都集中在分类时进行,要遍历整个训练样本空间,分类法的效率取决于已知样本数据集的规模,对于庞大的数据集,显然计算量是巨大的,算法的执行效率比较低,不适用于海量数据的Web文档在线分类;(2) KNN的精度也依赖于K值的大小,目前的做法通常是人工指定一个经验值,从一定程度上带来了偏差;(3)在实际应用中,样本分布存在多峰分布[4]情况,因此同类样本之间的距离可能会大于不同类样本之间的距离;样本的分布往往不够紧密,很多样本处于类别的边界,容易造成错分情况;标准KNN算法的分类决策只统计临近样本的个数,这在很多情况下不够精确[4],因此样本的分布情况也影响了KNN的分类性能。
1.2 相关工作
针对这些不足之处,许多研究者都提出了改进措施:为了解决样本分布对KNN造成的影响,中科院的S Tan提出了一种适应性的KNN改进算法[5],对样本数差异较大的类别,设定不同的K值,减少了算法对样本分布的依赖性;为了提高分类精度,北京大学的L Baoli提出的方法是在比较两个样本的相似度时,对重要度较高的属性进行加权,加权的值为该维特征的权值,从而提高了类别的可标识度[6];为了提高KNN的分类效率,同济大学的张高胤等提出了动态生成代表样本法[7],选取样本集中的代表样本作为训练样本,从而减少训练样本集数量,但是该算法需要设定一个阈值,同类别的样本在这个阈值之间动态调整,生成代表样本。
2 代表样本集生成策略
2.1 代表样本
通过分析可知,庞大的数据集是造成KNN分类速度慢的主要原因,为此引入了代表样本[4,8]的概念。代表样本是从样本集合中选出一些最能代表类别特性的样本作为代表样本,用这些样本来代替样本集中的所有样本,在分类时只比较待分类样本与这些代表样本的相似程度,减少了分类时的计算规模。因此生成代表样本是解决KNN效率问题的有效途径。
常见的代表样本生成策略是假设同类的样本相似度最大,把同类的样本划分为一组,[4]。在每一类的中心选一个代表样本,代表样本的个数等于类别数。然而实际并非如此,样本常常存在多峰分布的情况假设训练样本集D在二维向量空间中的分布如图1所示,相同符号表示的文档属于同一类别,多峰分布导致了同一类别中的样本可能集中分布于几个不同的区域,如图2所示,若采用上述方法,黑点所代表的类的代表中心点则为方框图形所表示的样本A,而对黑点所表示的样本而言,最具有类别代表性的样本为B和C。可见,在选择代表样本时,不能只根据相似度大小或是所属类别对样本集合进行简单的划分,而是要根据他们的分布情况,综合相似度和类别属性这两个方面来决定如何生成代表样本。
本文将介绍一种代表样本生成策略。在选择代表样本时,所遵循的原则是让代表样本被尽可能多的同类样本所包围,在代表样本所代表的区域内尽可能多的包含同类样本。本文假设每个样本只属于一个类别。下面给出策略描述。
2.2 代表样本法
为了便于下文描述,首先给出样本的属性设定:
Sxy:表示文档dx与文档dy的相似度;
Ri:表示文档di可以代表的样本的个数,i是文档di的序号;
sample(i):表示di的代表样本;
r(i):表示样本di的代表相似度,即di所代表区域的最大半径;
Bji:表示样本dj与代表样本di所代表区域的区域边界相似度,Bji=Sji-r(i)。
训练过程如下:
首先,对训练样本集D,利用公式(1)计算其中所有样本之间的相似度,建立相似度矩阵M,并给每个样本d设定代表度初值Ri=1,表示每个样本都可以代表自己;初始化样本的sample属性为空,设集合D’是D经过分组划分为若干子集后组成的集合,如D’={{d1,d2},{d3,d4,d5},……}等。集合DR表示生成的代表样本集合,初始化D’={},DR={}。
其次,对标记sample(i)为null的所有属于类别C的样本di,利用公式(3)(4)求得每个样本di与其他样本(包括代表区域)的代表相似度r(i)。利用公式(5)计算所有样本di的代表度,从di中选取代表度最大的样本dc作为代表样本,增加到代表样本集合DR中,并把满足条件dj∈C,sample(dj)=null,Sij>r(i)的所有样本dj的代表属性设置为sample(dj)=i,然后把这些样本dj添加到集合D’中同时从集合D中删除。重复这个过程,直到D为空。
r(i)=max(Six,Biy’),∀dx∉C,dx∈D,dy’∈DR (3)
Biy’=Siy’-r(y’) (4)
undefined(其中i≠j) (5)
分类过程:
当一个新的待分类的样本d到来时,只需计算该样本与DR中代表样本的相似度,若相似度大于某个代表样本的代表相似度r(i),则把该样本归入该类,否则按照公式(4)计算与所有代表样本的区域边界相似度Bid。选择Bid最大值对应的代表样本di,把测试样本归入到di的类别中,样本d的类别即可确定。
2.3 算法描述
训练算法:
(1)对初始训练集D,计算样本间的相似度,生成相似度矩阵M[Sxy], 设定集合D’表示由若干个代表子集组成的集合,集合DR表示代表样本集合,初始化D’={},DR={};
(2)对所有样本di,初始化Ri=1,sample(di)=null,r(i)=0;
(3) 对任意di ∈D,且di∈C,if(sample(di)==null),则
对∀dk∉D ,dk∉C, m1=max(Sik);
对∀dk∈DR,dk∉C,计算Bik=Sik-r(k), m2=max(Bik);
(4)求得 r(i)=max(m1,m2);
(5)∀ dj∈D, dj∈C,若Sij>Li,则Ri++;
(6)Rc=max(Ri),dc=undefined,D=D-{dc},初始化一个集合A,A={dc},DR =DR+{dc}。对满足条件的(4)中的dj,sample(dj)=c,D=D-{dj}, A=A+{dj} ,D’=D’+{A};
(7)循环(2)-(5),直到D={}。
分类算法:
对待分类的新文档d:
(1)代表集合DR={d1,d2……dn},计算d与B中的代表样本的相似度{S1,S2,……Sn},n是代表样本的个数, 初始化F={};
(2)对每一个Si,
如果Si
否则,计算d到每一个样本区域边界的距离Si-r(i),F=F+{Si-r(i)};
(3)如果d未被标记,则对F中的每一个元素x,undefined,把d归入到dc所在的类别。
3 实验验证与分析
分类性能的指标采用查准率(precision)和查全率(recall)来表示,查准率是所有判断的文本类别与人工分类结果吻合的文本所占的比率,用p表示,查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率,用r表示。其数学公式表示如下其数学公式表示如下:
undefined
其中a是属于该类并被正确分类样本数,b是属于该类但被错分的样本数,c是不属于该类但被错分到该类的样本数。考虑查准率和查全率,计算综合分类率undefined[4]。
实验运行环境为P4 2.3G处理器,程序使用Java语言编写,Eclipse作为编译运行平台。实验选取了YQ-CCT-2006-03中文网页集的600个网页作为训练集,400个网页作为测试集,选取了教育、计算机、军事、法治、财经和体育几个主题作为实验的类别主题,结合向量空间模型和特征选取算法,在本文提出的代表样本法基础实现了KNN分类器,进行了实验,并与传统的KNN算法进行比较,记录分类结果,并分别计算准确率、查准率和F1对网页数量的加权平均值。实验结果见下表。
从实验结果来看,本文所提出的代表样本法在查准率和查全率上与传统的KNN算法的分类性能相当,查准率和查全率略有降低,F1值降低了约3%,但从分类时间上看,该算法比传统的KNN的分类时间缩短了40%左右。这是由于代表表样本法由于在训练过程中生成了数量比较少的代表样本集,分类时的计算都集中在代表样本空间上进行,大大缩短了分类时间。从训练规模上看,测试样本数越多,分类的性能越好,而分类时间越长。由于代表样本的数量也是算法自动生成的,整个实验过程都不需要人为估计K值的大小,从一定程度上降低了经验值带来的误差。
4 结束语
本文提出了一种对KNN训练集的优化方法-代表样本法,并给出了详细的算法描述。实验证明,该算法与传统的KNN算法相比,虽然查准率和查全率略微下降,但是分类时间大大缩短了,提高了网页的分类效率,适合对分类效率和即时性要求比较高的情况,能够满足Web在线文档分类的需要,而在分类的查准率和查全率上比传统KNN稍显不足。下一步的工作将集中到训练样本集的增量优化上。
摘要：针对KNN算法懒惰分类和效率不高的特点,将训练数据集进行优化,提取有代表性的训练样本作为代表样本,用其代替整个训练集进行相似度比较。实验结果表明,使用代表样本集的分类性能与传统KNN算法的性能相当,缩短了分类时间,提高了分类效率,并且不需要估计K值,减少了人工估计值的偏差。
关键词：网页分类,KNN,代表样本,数据集优化,相似度
参考文献
[1]Craig Silverstein,Monika Henzinger.Analysis of a Very Large Web Search Engine Query Log.SIGIR Forum,1999.
[2]Yang Y,Li X.Are-examination of text categorization method.In:Proceedings of ACMSIGIR Conference on Research and Devel-opment in Information Retrieval,1999.
[3]冯是聪,张志刚,李晓明.一种中文网页自动分类方法的实现及应用.计算机工程,2004,30(5)
[4]刘斌,黄铁军,程军等.一种新的基于统计的自动文本分类方法.中文信息学报,2002,16(6)
[5]S Tan.An effective refinement strategy for KNN text classifier.Expert Systems with Applications,2006Elsevier.
[6]L Baoli,L Qin,Y Shiwen.An Adaptive k-Nearest Neighbor Text Categorization Strategy ACMTransactions on Asian Language In-formation Processing(TALIP),2004,3(4).
[7]张高胤,谭成翔,汪海航.基于K-近邻算法的网页自动分类系统的研究及实现.计算机技术与发展,2007,17(1).