虚点一种减少特征值鸿沟的方法

1、虚点：一种减少特征值鸿沟的方法林游龙1,2，余智华1，程学旗1，刘悦11中国科学院计算技术研究所，北京，100802中国科学院研究生院，北京，100190E-mail: linyoulong摘 要：基于向量空间模型的分类方法是目前各种分类方法广泛使用的文档结构表示方法，在对基于向量空间模型的分类方法的研究发现，基于向量空间模型的分类方法存在不合理之处，即特征值之间的“鸿沟”，这种鸿沟会导致向量空间模型中两点之间的距离的计算出现偏差，本文介绍了一种使用虚点的方法，这种方法消除了特征值之间的鸿沟，使得分类的效果得到了提高。该方法是通过重新定义特征权重，调整向量空间模型中点的特征值，即相当于重新定义

2、向量空间中的点，这样的点是相对于原来向量空间模型中的点的矫正映射，即就好像是虚拟点一样，最后问题归结为计算向量空间模型中的点与虚拟点的映射函数。理论分析表明虚点方法能提高基于向量空间模型的分类方法的效果，在SVM中运用虚点方法的实验结果表明，运用虚点方法的SVM的精确度得到了提高，这种结果验证了本文提出的虚点方法的有效性。关键词：虚点；分类算法；特征权重；向量空间模型VPM: A Method to Bridge the Gap between FeaturesYoulong Lin1,2 , Zhihua Yu1, Xueqi Cheng1, Yue Liu11Institute of Co

3、mputing Technology, Chinese Academy of Sciences, Beijing, 100802Graduate University of Chinese Academy of Sciences, Beijing, 100190E-mail: linyoulongAbstract: Vector space model (VSM) is the widely used model in the representation of the document structure in a variety of classification methods. The

4、 research on the vector space model based classification method shows that there is unreasonable point, that is, the gap between the features, this gap will lead to the deviation in the calculation of the distance between the two points in vector space model. This paper proposes a method of the virt

5、ual point to eliminate the gap between two features which improve the performance of the text categorization. The method is to adjust the feature value of point in the vector space model by redefining the weight of feature which is equivalent to the redefinition of the point in the vector space. Com

6、pared with the point in the original vector space model, the point is assumed to be the correctly mapping, that is, like a virtual point. Finally the problem boils down to the calculating of the mapping function between the vector space model and of virtual vector space model. Theoretical analysis s

7、howed that the virtual-point method can improve the performance of text categorization based on the vector space model. The experimental results of the support vector machine categorization method using virtual-point show that the performance has been improved, which verify that the virtual-point me

8、thod is effective.Keywords: Virtual point, text categorization, feature weight, vector space model1 引言随着信息时代的高速发展，如何对自然语言文本进行挖掘，特别是对其按照设定的语义进行正确的归类，已经成为组织大量文本信息的一个关键问题，这就是文本挖掘中很重要的一类任务一文本分类1。自动文本分类（Automatic Text Categorization）或者简称为文本分类，是指计算机将一篇文章归于预先给定的某一类或某几类的过程2。随着文本信息量的快速增长，文本分类已成为信息检索、知识挖掘和管理等

9、领域的关键技术34。文本分类的精确程度取决于特征提取5和分类算法6。人们提出了很多文本分类方法，例如k-最近邻分类法，贝叶斯分类，决策树和神经网络7。最广泛使用以及效果最好的文本分类方法是支持向量机与knn方法89。支持向量机是由Vapnik等人提出的一种学习技术，是借助于最优化方法解决机器学习问题的新工具。它集成了最大间隔超平面、Mercer核、凸二次规划、稀疏解和松弛变量等多项技术10。由于其具有全局最优、结构简单、推广能力强等优点，近几年得到了广泛地研究并应用于文本分类、模式识别等领域11。k-最近邻居分类（KNN）方法基于类比学习12，采用SVM（向量空间模型）13表示文档，是一种非参

10、数的分类技术，在基于统计的模式识别中非常有效，对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰等诸多优点14。本文在对基于向量空间模型的分类方法(如SVM 1516)的研究发现，基于向量空间模型的分类方法存在不合理之处，即特征值之间的“鸿沟”，这种鸿沟会导致向量空间模型中两点之间距离的计算出现偏差，由于目前基于向量空间模型的分类方法都没有考虑到这种鸿沟，因此分类效果受到了一定的限制，因此要想进一步提高分类效果，就必须解决这种偏差。本文介绍了一种使用虚点的方法，这种方法消除了特征值之间的鸿沟，使得分类的效果得到了提高。该方法是通过重新定义特征权重，调整向量空间模型中点的特征值，

11、即相当于重新定义向量空间中的点，这样的点是相对于原来向量空间模型中的点的矫正映射，即就好像是虚拟点一样，最后问题归结为计算向量空间模型中的点与虚拟点的映射函数。理论分析表明虚点方法能提高基于向量空间模型的分类方法的效果，在SVM中运用虚点方法的实验结果表明，运用虚点方法的SVM的精确度得到了提高，这种结果验证了本文提出的虚点方法的有效性。2 向量空间模型向量空间模型(Vector Space Model, VSM)8是康奈尔大学Salton等人上世纪70年代提出并倡导的，文档可以转化为标引项(term)及其权重组成的向量表示，都可以看成空间中的点。向量之间通过距离计算得到向量的相似度。VSM中

12、有三个关键问题：(1)标引项(term)的选择(2)权重的计算，即计算每篇文档中每个Term的权重(3)空间中文档之间距离的计算。Term可以是能代表文档内容的特征如：字、词、短语或者某种语义单元(比如：所有同义词作为1维)。对于权重计算，目前广泛使用的方法是TF*IDF方法，其中TF代表Term在文档中出现的次数。IDF代表Term的文档频率DF的倒数。两者相乘然后做线性编号就是此方法。计算完Term的特征权重后就可以在向量空间模型中用特征向量表示一个文档，即一个文档可以表示为一个向量空间模型中的一点。文档之间距离的通常有欧式距离、向量夹角余弦、向量夹角正弦和马氏距离等9。3 虚点原理3.1

13、虚点方法产生的背景-特征值鸿沟(GBF)如图1所示，假设一个类的构成只有2个Term，其中Term权重用TF*IDF表示，则每个类都可以表示为一个带权重的Term的特征向量，假设类别1的分类中心为(1,1)。类别2的分类中心为(3,2)，可知两者的对角点为(3,1),对角点相对于其它的点来说，特殊之处在于它对类别1的分类中心的距离只跟Feature1相关，而跟类别2的分类中心的距离只跟Feature2相关。那么问题就归结为对角点的分类问题，按照原来的向量空间模型，对角点有两个(1,2),(3,1)。其中(3,1)跟分类中心1(1,1)的Feature1的距离为特征Feature1的差值2.跟分

14、类中心2(3,2)的Feature2的距离为特征Feature2的差值1。可以知道应该将对角点分到类别2(3,2)那一组，但从理论上可知，属于同一特征的值，可以用量来表示，但是属于不同特征的值无法用量来表示，因为两者的判定的标准不一样。Feature2的差值为2的数不一定大于Feature1的差值为1的数。因此仅仅从此对角点的分类问题应该无法判断到底属于哪一类。也就是Feature2的差值为2的数应该与Feature1的差值为1的数相等。此时对角点到两类的距离相等，符合无法判断类型的情况。因此原向量空间模型没考虑到这个问题，这就是特征值的鸿沟问题(GBF)的产生。如图1所示鸿沟为q1。图1.虚

15、点原理示意图Fig. 1. Theory of Virtual Point Method为了消除特征值之间的鸿沟。可以认为存在原分类点的虚点，这些点是由调整特征权重的分配来得到的。它们必须满足两个条件：1、归一化条件。2、调整后的两个类别虚点到虚对角点的距离必须相等。 如图所示，vp1和vp2分别对应分类点1和分类点2的虚点。现在的问题归结为本文提出的特征鸿沟理论到底存不存在，用即特征鸿沟的的消除能不能带来分类效果的提高，从如图2所示，就是要证明在虚点空间中用vp1和vp2分类比原向量空间中分类的效果更好。3.2虚点方法介绍变量定义：假设向量空间模型中的分类点为类别1的分类中心a和类别2的分类

16、中心b，必然存在一个点a，它跟a的距离只跟Feature(1)相关，即特征距离，假设其为l(1),跟b的距离只跟Feature(2),设为l(2)相关，这个点称为a和b的对角点。易知a和b的对角点有两个，任选其中的一个Feature(1)与Feature(2)之间的距离鸿沟d(12)定义为：d(12)=|l(1)l(2)|。虚点方法：存在特征权重l(1),l(2)满足归一化条件，并且使得分配权重后的向量空间中的点，即原空间中的a和b在虚点空间中的分别对应的点的虚点a和b的2个特征距离相等，即a和b到它们虚点空间中的对角点的离相等：l(1) = l(2)。这样在虚拟空间中特征之间的距离鸿沟就为零

17、了。关于对角点的说明：虚点空间与原空间的对角点不是独立存在的，他是针对分类点，以及虚点空间中分类点的虚点而提出的一个抽象的概念，它在现实中可能不存在。 到目前为止就只有一个问题了，即特征值鸿沟的观点是否存在？3.3 虚点方法的例子为了形象的说明整个流程，举个例子：比如判断一列火车属于快车与慢车的标准为：快车为，平均车厢的数量为10节，速度平均为180公里/小时。而慢车的为：平均车厢30节，速度平均为80公里/小时。如果此时，有一列特殊的列车，车厢为10节，速度为80公里/小时。那么根据向量空间模型的公式，可以算出这种列车对快车的差异为速度相差100公里/小时，车厢没差异。对慢车的差异为车厢相差

18、20节，速度没差异，进行标准化以后(假设速度的标准化为原值除以180，车厢的标准化为原值除以30)，差异分别为100/180,20/30。从而知道此列车属于快车。但是理论上可知此列出应该不能判断归属，因为20节车厢跟100公里/小时这两个数无法比较。此时鸿沟为差异值的差值即|100/180-20/30|=0.11。而这列车可能现实中不存在，它只是针对快车和慢车而提出的一个概念。因此本文设特征权重l(1),l(2)来分别调整火车车厢跟火车速度的权重，设归一化条件l(1)×l(2)1。此时l(1)×(20/30) = l(2)×(100/180)。可以得出l(1)&#

19、187;0.9129，l(2)»1.0954。此时虚拟分类点为快车平均节数为:9.129节，速度为197.172公里/小时：慢车平均节数为。27.387节，速度为：87.632公里/小时。此时就能用虚拟点分类了。可以计算特殊列车在虚点空间中的映射点为9.129节与 87.632公里/小时，从而计算得到鸿沟为0,此值小于<0.11。说明使用快车，与慢车的虚点用来分类比使用原点分类来得更接近实际。3.4 虚点方法的另一种解读假设原空间中存在分类点a(0,0)点和b(a,b)点。根据虚点方法可知，它们在虚点空间中分别对应虚点a(0,0)和b(al1,bl2)，其中，l1l2=1设a和

20、b的距离为c，则根据直角三角形公式，已及直角三角形不等式可知： （1）其中当al1=bl2，时c有最小值。而al1=bl2是虚点空间中的虚点满足的条件。因此虚点方法就转化为求虚点空间中虚点之间最小距离。即3.1节提出的虚点满足的两个条件变为：1、归一化条件。2、调整后的两个类别之间的距离最小。35虚点方法的求解输入变量定义：假设向量空间模型由n维特征向量构成，类别1的分类中心为a(a1,a2,.an)，类别2的分类中心为b(b1,b2,.bn)。输出变量：特征权重l1，l2，ln。求解原理： （2）限制条件为: （2）根据以上可知，这是最优化问题，因此本文使用拉格朗日乘数来解决此问题。得到如下

21、函数： （3）其中l为拉格朗日乘数。为了求l1, l2, ln。将函数(3)分别对l1, l2, ln求偏微分得： （4）即式子 （5）解得： （6）因此第i个特征权重为： （7）从以上式子可以看出，跟a和b的第i个特征的差值成反比。此结果证实了给人的感觉，即为了缩小特征鸿沟，特征值差异越大的，应该将它们分配的权重越低。4 SVM与使用虚点原理的SVM支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的17，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Ge

22、neralizatin Ability)。支持向量机方法的几个主要优点是1、可以解决小样本情况下的机器学习问题2、可以提高泛化性能3、可以解决高维问题4、可以解决非线性问题5、可以避免神经网络结构选择和局部极小点问题18。根据虚点方法可知，在SVM中使用虚点方法的步骤如下：1、在训练集中，根据虚点算法调整特征权重，映射到虚点空间。其中权重应满足归一化条件以及虚点空间中虚点之间的距离最小。2、在虚点空间运用SVM方法，即找出最优分类超平面，此时的最优超平面是虚点空间的最优分类超平面。3、用虚点空间的最优分类超平面来分类,即使用虚点空间建立的模型。图2.原SVM分类方法与使用了虚点方法的SVM分类

23、方法Fig. 2. SVM and Virtual Point Method based SVM如图所示2对于步骤1，首先分别求训练集中类别1和类别2的分类中心，可以用分别求类别1和类别2中向量的平均值的方法。然后使用3.6节中介绍的求解虚点的方法，求出特征权重。根据特征权重重新计算特征向量，相当于将原点映射到虚点空间，此时产生的新的训练集即虚点空间中的训练集。对于步骤2，跟运用SVM方法的差别仅仅是训练集的不同，即虚点空间运用的是步骤1产生的训练集。对于步骤3，跟运用SVM方法的差别仅仅是模型的不同，即，虚点空间用于的是步骤2产生的模型来分类。5 实验LIBSVM 是台湾大学林智仁(Chih

24、-Jen Lin)博士等开发设计的一个操作简单、易于使用、快速有效的通用SVM 软件包，可以解决分类问题、回归问题以及分布估计等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。本文使用libsvm附带的包含47,236个特征值的数据集rcv1.binary，其中数据量为20，242，本文将此数据集分为10份做交叉测试即，每份2,024个数据，最后一份是2,206个数据。然后依次选取10份中的一份做测试集，其它9份合并为一个训练集。核函数选取径向基函数19。因为其对应的特征空间是无穷维Hilber

25、t空间。而Hilbert空间推广了高斯空间的概念，这点跟虚点方法(VPM)很相似。数据集都是经过了归一化的了。虚点方法参数l=2, 测试的是分类精度。实验结果如表1所示：表1 交叉测试结果Tab.1 Result of Cross TestNo.12345SVM56.92%54.35%58.25%47.04%43.43%SVM using VPM61.81%58.35%62.30%52.37%46.74%No.678910SVM50.64%55.19%50.15%59.14%43.19%SVM using VPM55.48%60.47%56.08%64.33%48.27%由实验结果可知，使用了

26、虚点方法调整的权重后分类的精度得到了一定的提高，这种结果验证了本文提出的虚点方法的有效性。6 总结本文提出了特征值之间存在鸿沟的问题，并介绍了一种使用虚点的方法，这种方法降低了特征值之间的鸿沟，使得分类的效果得到了进一步的提高。该方法是通过重新定义特征权重，调整向量空间模型中点的特征值，即相当于重新定义向量空间中的点，这样的点是相对于原来向量空间模型中的点的矫正映射，即就好像是虚拟点一样，最后问题归结为计算向量空间模型中的点与虚拟点的映射函数。理论分析和实验结果表明运用了虚点方法的基于向量空间模型的SVM的分类方法的精确度都得到了提高，这种结果验证了虚点方法的合理性。本文的主要贡献是：1、本文

27、提出了特征值之间存在鸿沟的问题，2、介绍了一种使用虚点的方法来降低特征值之间的鸿沟。本文介绍的使用虚点的方法，证明了分类中存在特征鸿沟的问题，提高分类的效果，本文使用的是用平均值求特征值鸿沟的方法，这种方法具有一定的局限性，因此研究求特征值鸿沟的方法以及使用训练集的启发式知识来定义特征值鸿沟与权重分配将是下一步要做的工作。参 考 文 献1 Ruch P. Query translation by text categorizationA. Proceedings of the 20th international conference on Computational Linguistics.

28、 2004.2 Bose I, Mahapatra RK. Business data mining-a machine learning perspectiveJ. J. Information & Management. 2001, 39(3):211-225.3 Núñez H, Angulo C, Català A. Rule-Based Learning Systems for Support Vector MachinesJ. J. Neural Process. Lett. 2006, 24(1):1-18.4 Liu Y, Loh HT,

29、Kama YT, et.al. A hierarchical text classification system for manufacturing knowledge management and retrievalJ. J. Int. Knowledge Management Studies. 2008, 2(4):406-425.5 Pechenizkiy M, Puuronen S, Tsymbal A. Feature Extraction for Classification in Knowledge Discovery SystemsJ. J. Knowledge-B

30、ased Intelligent Information and Engineering Systems . 2003, 2773: 526-5326 Antonie ML, Zaiane OR, Holte RC. Learning to Use a Learned Model: A Two-Stage Approach to ClassificationA. Proc. Int. Conf. Data Mining. 2006, 33-427 Yang Y, Pedersen JO. A Comparative Study on Feature Selection in Text Cate

31、gorizationA. Proc. Int. Conf. Machine Learning. 1997, 412-420.8 Salton G, Wong A, Yang CS. A vector space model for automatic indexingJ. J. Commun. ACM, 1975, 18(11):613-6209 Qu S, Wang S, Zou Y. Improvement of Text Feature Selection Method Based on TFIDFA. Proc. Int. Seminar on Future Information T

32、echnology and Management Engineering. 2008, 79-8110 Yang Y, Liu X, A re-examination of text categorization methodsA. Proc. Int. ACM SIGIR Conf. Research and Development in information Retrieval. 1999, 42-4911 Vapnik VN, The Nature of Statistical Learning TheoryM. Berlin: Springer-Verlag, 1995.12 Has

33、tie T, Tibshirani R. Discriminant Adaptive Nearest Neighbor ClassificationJ. IEEE Trans. Pattern Analysis and Machine Intelligence. 1996, 8(6):607-61613 Shakhnarovich G, Darrell T, Indyk P. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing)M. The MIT Press, 2006.14 Dasarathy BV. Nearest neighbor (NN) norms: NN pattern classification techniqueM. Los Alamitos:IEEE Computer Society Press, 199015 Cristianini N, Taylor JS. An Introduction to Support Vector Machin