您好, 访客   登录/注册

文本分类的关键技术

来源:用户上传      作者:

  摘 要 本文阐述了基于WEB的文本分类的关键技术,从网页的解析、文本的表示、降维技术到分类算法进行详细的论述,并对两个K-means算法和Baygers算法做了改进。
  关键词 文本分类 降维技术 文本表示 分类算法
  中图分类号:TP311 文献标识码:A
  文本分类是指在给定分类体系下,根据文本内容自动确定文本类别的过程,将大量的文本归到一个或多个类别中。从数学角度来看,文本分类是一个映射的过程,将未标明类别的文本映射到己有的类别中来,数学表示如下: f:A->B 其中A为待分类的文本集合,B为分类体系下的类别集合。
  1网页的解析
  按照W3C组织所制定的标准,每一个HTML页的结构都可以对应地描述成DOM树的形式。DOM定义了HTML文档的逻辑结构,提供了一种对网页中的数据及内容进行管理和操作的途径。DOM将整个文档的内容分别抽象为不同的对象,用结点的形式予以表示,如标签结点、文档类型结点、文本结点、注释结点、属性结点等。再用类似于父子的关系将各结点按照不同层次有顺序地组织起来,形成树型结构。
  2文本表示
  向量空间模型(Vector Space Model,简记为VSM)是一种较著名的用于文档表示的统计模型,该模型以特征项做为文档表示的基本单位,特征项可以由字词或短语组成。每一个文档可以看成是由特征项组成的n维特征向量空间的一个向量:D=(T1,W1;T2,W2;T3,W3……;Tn,wn),其中Wi为第i个向量Ti在文档中的权重,一般选词做特征项比选字做为特征项要好一些。一般使用TF-IDF公式计算特征项权重,其中TF(Term Frequency)表示词频,IDF(Inverse Document Frequency)表示逆文档频率,反映文档集合中出现该特征项的文档数目。
  3降维技术
  3.1信息增益
  信息增益在机器学习中经常被用做特征词评判的标准,它是一个基于熵的评估方法,定义为某特征项在文档中出现前后的信息熵之差。根据训练数据计算出各特征词的信息增益。删除信息增益很小的词,其余的按信息增益从大到小排列。如果以信息增益最大者为要根结点,建立一个决策树就可以进行决策树的分类挖掘。
  3.2互信息:(MI)
  应用在相关词统计建模中,在统计学中用于表示两个变量间的关系,其计算如下公式所示:
  其中各变量的含义同上。显然当特征项W独立于ci时它同该类的相关度为0 ,p(w)越小而同时p(w|ci)越大時特征项W提供类别ci的信息量越大,则这个特征项越能代表这一类,反之,p(w)越大的同时p(w|ci)越小,则可能得到负的互信息值,这种情况下,该特征项对分类的意义同样很大。
  4分类算法
  4.1 K-means算法
  K-means算法是应用最广泛的聚类算法之一,是一种已知聚类类别的聚类算法。指定类别数k,对样本集合进行聚类,聚类的结果由k个聚类中心来表达。相似度的计算根据一个簇中样本的平均值(被看作簇的中心)来进行。
  首先,随机选择k个对象,每个对象初始的代表了一个簇的平均值或中心。对剩余的每个对象,根据其与各个簇中心的距离,将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如公式(6):
  这里的E是数据库中所有对象的平方误差的总和,p是空间中的点,表示给定的数据对象,mi是簇Ci的平均值(p和mi都是多维的)。这个准则试图使生成的结果簇尽可能的紧凑和独立。
  这个算法尝试找出使平方误差函数至最小的k个划分。当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好。对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度是O(nkt),其中,n是所有样本的数目,k是聚类簇的数目,t是迭代的次数。通常的k<<n且t<<n。这个算法经常以局部最优结束。
  但是,K-means只有在簇的平均值被定义的情况下才能使用。这使得它不适用某些应用,例如涉及到分类属性的数据。要求用户必须事先给出k,可以算是该方法的另一个缺点。同时K-means不适合发现非凸面形状的簇,或者大小差别很大的簇。而且,它对于“噪声”和孤立点数据是敏感的,少量的该类数据能够对平均值产生极大的影响。
  4.2朴素贝叶斯算法
  利用对研究对象的已有认识-先验概率作为基础,进行判断。它具有最小的出错率,在误差率要求较高的应用上,它具有很大的优势。但贝叶斯算法需要已知条件的概率,而且其决策面往往是超曲面,形状复杂,难以计算和构造。朴素贝叶斯是贝叶斯算法的改进,假设一个属性对一个给定类的影响独立于其它属性的值。这一假定成为类条件独立。它简化了原来贝叶斯算法的计算,提高了算法效率,可以用于大型数据库,并且已表现出高准确率和高速度。
  朴素贝叶斯算法的本质是用词和类别的联合概率估计给定文档属于各个类别的概率。它假设,一个词在给定类别的条件概率独立于该类的其它词的条件概率。这样,就以降低分类精度的代价换来了较高的执行效率。
  参考文献
  [1] 姚天顺.自然语言理解[M].北京:清华大学出版社,1995.
  [2] 吴立德.大规模中文文本处理[M].上海:复旦大学出版社,1997.
  [3] 王永成,许慧敏.OA中文文献自动摘要系统[J].情报学报,1997,16(02):128-132.
转载注明来源:https://www.xzbu.com/1/view-14926066.htm