自动分类技术

自动分类技术1背景介绍自上个世纪80年代以来，信息化的浪潮席卷全球，信息技术迅速地渗透到社会经济的各个领域。随着Internet的普及和网络技术的不断完善，Internet已经成为了全球最庞大最丰富的信息资源库。由于Internet的开放性，各类信息都能在第一时间发布在Internet上。然而，也导致了Internet上信息的杂乱性和冗余性。因此，自动分类技术随着时代的需求而蓬勃发展了起来。作为一种有效的信息处理方法，自动分类技术将各类信息按照一定的分类体系进行分类整理，从而大大提高了用户搜集情报的效率。自动分类技术是在手工分类技术的基础上发展起来的。传统的信息手工分类技术已经相当成熟，但却不适于对Internet上时刻更新的信息进行处理。因为它不具有实时性，另外查全率和分类的一致性也受到一定的制约。世界著名搜索引擎Yahoo长期以来集中了大量人力进行手工分类，并且曾经因此获得了巨大的成功，但这种成功的背后已潜伏着落后的危机。Yahoo宣布同Google合作，开发自动分类技术以取代手工分类——自动分类技术已经成为大势所趋。2自动分类历史自动分类技术的研究始于20世纪50年代末，IBM公司的H.P.Luhn在这一领域进行了开创性的研究。1960年，Maron在JournalofACM上发表了有关自动分类的第一篇论文OnRelevance,ProbabilisticIndexingandInformationRetrieval，随后许多著名的情报学家如K.Sparch、G.Salton及R.M.Needham等都在这一领域进行了卓有成效的研究。相对于国外的情况，我国开展自动分类的研究起步稍晚一些。80年代中期开始，我国的一些大学、图书馆和文献工作单位开展了档案、文献或图书的辅助或自动分类研究，并陆续研制出一批计算机辅助分类系统和自动分类系统，这些系统主要集中在中文处理领域。3自动分类的种类自动分类是计算机系统代替人工对文本，网页等对象进行分类。从实现途径进行划分，自动分类分为自动聚类和自动归类。自动聚类是从待分类对象中提出特征，然后将提出的全部特征进行比较，再根据一定的原则将具有相同或相近特征的对象定义为一类。自动归类是分析被分类对象的特征，并与事先定义好的各种类别具有的共同特征进行比较，然后将对象划归为特征最接近的一类并赋予相应的分类号。4自动分类的作用目前搜索引擎提供两种信息查询方式：分类浏览和关键词检索。分类浏览一般是基于网站分类目录。它浏览的对象是网站，目录分类的质量较高，检索效果好；但是成本高、信息更新慢、维护的工作量大。关键词检索的对象不是网站，而是符合条件的网页。关键词检索信息量大、更新及时、不需要人工干预；但是返回信息过多，质量太低。如果能够实施网页的自动分分类，就可以实现网页标引和检索的分类主题一体化，搜索引擎就能够兼有分类浏览、检索和关键词检索的优点，同时具备族性检索和特性检索的功能；能够深入到网页层次，帮助用户迅速的判断返回的结果是否符合自己的检索要求。5自动分类算法(1)KNN法(2)SVM法(3)VSM法(4)Bayes法（1）KNN法KNN法即K最近邻法该方法的思路：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。具体的算法步骤如下:STEP1:根据特征项集合重新描述训练文本向量;STEP2:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示;STEP3:在训练文本集中选出与新文本最相似的K个文本，计算公式为:i表示第i篇档的特征向量j表示第j篇文档的特征向量，M为特征向量的维数，sim(d)表示第i和j篇文档的相似度，讯为向量的第k维。STEP4:在新文本的K个邻居中，依次计算每类的权重，计算公式如下:其中，征向量，sim()为相似度计算其中，也为新文本的特公式，而到，c为类别属性函数，如果属于cj类，那么函数值为1，否则为0。STEP5:比较类的权重，将文本分到权重最大的那个类别中。优缺点优点：可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。缺点：计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。(2)SVM法SVM法即支持向量机法主要思想是针对2类分类问题，在高维空间中寻找一个超平面作为2类的分割，以保证最小的分类错误率。SVM法对小样本情况下的自动分类有着较好的分类结果。SVM是从线性可分情况下的最优分类面发展而来的，基本思想可见图，分割线1和分割线2都能正确地将2类样本分开，这样的分割线有无线多条，但分割线1使2类样本的间隙最大，称之为最优分类线(更高维即为最优分类面或最优超平面)。(3)VSM法VSM法即向量空间模型法基本思想：将文档表示为加权的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。在实际应用中，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为该待分样本所对应的类别。VSM法相对其他分类方法而言，更适合于专业文献的分类。(4)Bayes法即贝叶斯法Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。Bayes分类方法在理论上论证得比较充分，在应用上也是非常广泛的。Bayes分类判决准则•设训练样本集分为M类，记为C=｛c1，…，ci，…cM}，每类的先验概率为P(ci)，i=1，2，…，M。当样本集非常大时，可以认为P(ci)=ci类样本数/总样本数。对于一个待分样本X，其归于cj类的类条件概率是P(X/ci)，则根据Bayes定理，可得到cj类的后验概率P(ci/X)：•P(ci/x)=P(x/ci)·P(ci)/P(x)(式1-1)•若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，则有x∈ci(式1-2)•式(1-2)是最大后验概率判决准则，将式(1-1)代入式(1-2)，则有：•若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，则x∈ci缺点Bayes方法的薄弱环节在于实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。6自动聚类的实现方法网页的自动聚类一般包括四个步骤：（1）网页表示：包括特征抽取和特征选择。特征选择是选择那些最具有区分性的特征，也就是最能把不同类别区分开来的特征，而不是大多数对象都具有的特征。（2）相似度计算。主要根据网页表示的距离函数来定义。（3）聚类：根据网页表示和相似度计算的结果，按照一定的规则将聚类网页分成不同的类。（4）给出聚类的标识。在最后形成的每一类中抽取一定具有代表性的特征，作为该类的标识。聚类方法（1）单遍聚类法（2）逆中心距聚类法（3）密度测试法（4）图聚类法7自动分类技术的展望1立体性文本的内容可以从不同角度或不同侧面进行考察，从而挖掘出不同偏重的信息。自动分类技术中立体性的发展目标就是要建立一个全面的分类系统，其2动态性分类法可以动态地随信息内容概率分布的变化进行变化，力求分类法的树型结构是一个平衡结构，使分类法更利于快速检索。3面向用户性分类系统的实时调节能力。不同用户有着不同的分类要求，同一用户在不同场合也可能有着不同的分类要求。因此，未来的自动分类系统应该更多的考虑增强学习功能，能够在用户的指导下对分类体系及分类法做出个性化的调整，以满足用户的需求