一种适合于中文网页文档的后缀树聚类方法

摘要

本发明提出一种适合于中文网页文档的后缀树聚类方法。后缀树聚类算法的提出是建立在英文网页聚类的基础上的，研究的对象是网页中的英文单词，而中文最大的特点是词与词之间没有分隔符。为满足中文网页的聚类需求，本发明针对中文网页文档的特点，对后缀树聚类算法进行了改进，使之适于中文Web信息搜索结果的聚类。文档预处理按照句子边界将每一篇文档转化为词的序列，同时过滤掉非词标记及停用词。后缀树构建由预处理得到的词序列生成后缀树。短语类识别通过后缀树识别短语类并对其打分。短语类合并通过基于二进制的及语义层面短语类间的相似性计算方法，合并相似度值高的短语类，并选取分值较高的短语类作为最终聚类结果。

主权项

1.一种适合于中文网页文档的后缀树聚类方法，其特征在于：包括以下步骤：A、文档预处理搜索引擎返回的结果列表包含文档的URL、标题和摘要信息，其中URL是用来定位文档的，因此将文档的标题和摘要作为聚类算法的输入；数据预处理阶段主要分为两个部分，HTML标签及特殊符号的过滤和停用词的去除；A1、过滤HTML标签及特殊符号HTML标签以及特殊符号的过滤是预处理的第一个步骤，主要负责将文档中没有用的或者干扰文档信息的非汉语元素去除掉，包括HTML标签，如<br>、<p>、<td>等、特殊字符，如、#、%等、标点符号，去除包括“，”、“”、“！”、“；”等符号、数字等字符；A2、去除停用词消除停用词需要定义并维护一个中文停用词表，使在后缀树构建过程中出现在停用词表中的词语全部被剔除，用以改善聚类结果的质量；B、后缀树构建假设为长度为m的字符串S生成一棵后缀树，首先要为树添加一条表示后缀S[1,m]的边，然后连续递归地为树添加表示后缀S[i,m]的边，其中i从2到m；设Ni为中间后缀树，对S[i,m]进行后缀树表示；树N1包含有一条单一的边和一个叶子结点，叶子结点用1标识，边用S[1,m]标识；树Ni+1的构造基于树Ni：在Ni中，找到从根结点开始的、并且标识能够匹配S[i+1,m]的前缀的最长路经；这条路径的查找方法如下：不断的将S[i+1,m]与从根结点开始的路径上的标识比较和匹配，直到没有更多的匹配时就得到了最长的路径；如果没有找到与S[i+1,m]的前缀相匹配的路径，则创建一条从根节点到新叶节点i+1的边，用来标识后缀S[i+1,m]；否则，当找到最长的路径时，存在两种状态：有可能匹配的位置在一个结点上，设为x，也可能匹配的位置在一条边的中间，设这条边为(u,v)；如果是在一条边的中间，此时需要先将边(u,v)折为两段，在折断位置插入新的结点x，折断的位置就是和S[i+1,m]的前缀比较时，匹配的最后一个词的下一个位置；在两种状态下，都需要创建一条新边(x,i+1)，其中结点i+1是一个新的标识为i+1的叶子，并且用S[i+1,m]的不匹配部分来表示这条边；C、短语类识别为每个短语类分配一个分值，然后选择分值高的作进一步分析；包含短语Bp的短语类B的分值Score(B)可以由下面的公式得到：Score(B)=|B|f(|B_p|)∑TF-IDF(w_i)其中，|B|是短语类B中的文档数目，|Bp|是Bp的长度；当短语中的字数小于7时f函数是线性的，而大于7时则是个常数，w_i是Bp中的词，TF-IDF(w_i)是Bp中每个词的权值；TF-IDF是IR领域一个常用的为词赋权重的方法，其基本原理是：在一篇文档中出现频率越高的词越能代表这篇文档的主题，而出现频率越低的词越能区分不同的文档，其计算公式如下：$\mathrm{TF}-\mathrm{IDF}\left(w_i\right)=(1+\log \left(\mathrm{TF}\left(w_i\right)\right)).\log (1+\frac{N}{\mathrm{DF}\left(w_i\right)})$其中，TF(w_i)表示短语类代表的文档子集中词w_i的出现次数，N是文档子集中的文档数目，DF(w_i)是出现词w_i的文档数目；D、短语类合并文档集中有可能包含一个以上的相同短语，因此，不同短语类代表的文档集合可能大部分重叠甚至完全相同，需要从文档集重合度方面进行短语类合并；另外，还从短语类本身的语义层面考虑合并具有相同语义的短语类，目的是避免在最后的聚类结果中出现语义相同的类别，提高聚类结果的质量；D1、考虑文档集重叠度使用二进制的方法计算两个短语类之间的相似度，按分值由高到低的顺序，依次计算每个短语类和其它所有短语类之间的相似度；计算方法如下：给定两个短语类Am和An，如果|Am∩An|/|Am|>k并且|Am∩An|/|An|>k，则Am和An的相似度为1，否则为0，其中k是一个在0和1之间的常数，通常取0.5，|Am∩An|表示Am和An所代表的文档集中的相同文档数，|Am|表示Am所代表的文档集中的文档数；然后，将相似度值为1的短语类合并；合并后的类包含所有短语类对应的文档集合，合并类的分值等于其所包含的短语类的分值总和；计算出短语类的相似度后，对于值为1的短语类还应判断它们之间是否存在依附关系，然后再决定合并与否；D2、考虑短语类语义借助词典对同义短语进行判断，计算两个短语类Am和An语义相似度的公式如下：$\mathrm{Similarity}(A_m,A_n)=\frac{\mathrm{KN}(A_m,A_n)+\mathrm{SN}(A_m,A_n)}{\mathrm{Max}(\mathrm{kn}\left(A_m\right),\mathrm{kn}\left(A_n\right))}$其中，kn(.)表示对应的短语类的字数，KN(Am,An)表示短语类Am和An中相同词的长度，SN(Am,An)表示Am和An中同义词的长度；同样需要为相似度值定义一个阈值k，计算结果大于k的两个短语类被认为是具有相同语义的短语类，将被合并成一个类别。