一种基于后缀树的中文网页层次聚类方法 指导教师：赵政 学生：史庆伟

1 引言 目前的搜索引擎产生的搜索结果过于庞大和杂乱，用户难以从大量的结果集中快速找到自己感兴趣的信息。 为了便于用户浏览，利用文档聚类算法将搜索结果自动聚类，形成一个类似文件夹的层次结构是一种好的方法。 传统的文档聚类算法，所产生的聚类结果簇没有可读性，不适于直接应用于网页的聚类。

有代表性的网页聚类方法包括：Sanderson和Croft提出的根据概念之间包含关系的聚类方法； Lawrie 提出的利用基于条件概率的语言模型聚类的方法； Hua-Jun Zeng提出的利用回归模型将聚类问题转换为分类问题的方法； 这些方法都是建立在对英文网页聚类的基础上的，研究的对象是网页中的英文单词，而中文最大的特点是词与词之间没有分隔符，因此上述方法很难直接应用到中文网页的聚类上； O.Zamir和O.Etzioni采用后缀树（Suffix Tree）数据结构给出了一种网页快速聚类的方法，称为STC(Suffix Tree Clustering)。

2 STC算法 STC算法的主要思想是将每一个文档看成一个字符串，构建后缀树，后缀树中出现的相同的字符被认为是基本类，然后对基本类进行合并。 后缀树的特点是： •只有一个根节点 •中间节点至少有两个子节点 •每条边用子串标识，表示节点到根的路径 •同一节点的边不能有相同的标识 •每个字符串的子串都有相对应的后缀节点

图1是三个字符串 “cat ate cheese”, “mouse ate cheese too” 和 “cat ate mouse too”形成的后缀树的例子。 图中圆形表示节点，每个中间节点表示文档中出现的相同的词，其内容在边上标识，矩形中第一个数字表示子串属于那个文档，第二个数字表示字符串中的第几个子串。

图1 “cat ate cheese”, “mouse ate cheese too” 和 “cat ate mouse too”三个字符串的后缀树

a至f是基本类，在合并基本类时，首先计算两个基本类的相似度，计算方法如下： 给定两个基本类Bm和Bn，如果 且 则Bm和Bn的相似度为1，否则为0 其中 表示同时含有基本类Bm和Bn的文档数， |Bm |表示含有基本类Bm的文档数， |Bn |表示含有基本类Bn的文档数。然后，将相似度为1的基本类连接在一起，完成基本类的合并。

3 STC算法的改进 STC算法中使用二进制的方法计算两个基本类之间的相似度，合并基本类的过程实际上是单链接(Single-Link)方法。STC算法中避免链式效应的代价是降低了精度。 改进方法：使用雅克比系数(Jaccard coefficient)作为计算基本类相似度的方法，结合传统的数据聚类算法变色龙算法(chameleon)实现提高STC算法精度的目的。

2.1 基本类相似度计算 STC算法中基本类相似度的取值，只有0和1两个值，忽略了一些类的相关性，降低了精度。 例如，假设有两个基本类Bm和Bn ，如果Bm包含Bn ，且 ， Bm和Bn明显有一定的相关性，而在STC算法中Bm和Bn的相似度为0。STCC算法采用雅克比系数计算基本类相似度，使其取值介于0和1之间，其计算方法如方程1所示。

（1） 其中， 为同时含有Bm和Bn的文档数， 为含有Bm或Bn其中之一的文档数。

2.2 基本类的合并 基本类的合并是将STC算法中产生的基本类作为基本点，采用雅克比系数获得基本类的相似度作为基本点之间边的权重，使用变色龙算法实现基本类的层次聚类。 变色龙算法是一种采用动态模型的聚类算法，只要定义了相似度函数，就可以应用于所有数据类型。 变色龙算法的主要思想是首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用凝聚的层次聚类算法反复合并子类来找到真正的结果簇

3 实验 实验数据选自百度搜索中最流行的五个关键词的搜索结果，即跑跑卡丁车、李宇春、qq、迅雷和mp3。 网页预处理 利用HTML DOM API将每个查询结果前500个网页片断的文本取出，然后去掉英文，数字等非汉语元素，一些网页中经常出现的词，如“下一页”，“点击”等，以及一些介词、连词和代词同时也被去掉。 根据标点符号将每一个句子看成一个字符串，构建后缀树，也就是说，处理的最小单位是句子，而不是整篇文档，这样大大节省了构建后缀树的时间和空间。

研究了STC算法和STCC算法的精度。 实验的结果如图2所示。 从图2中可以看出，STCC算法的精度比STC算法提高了将近10%左右，只有第三个查询(qq)的精度相差不大，这是因为其搜索结果中含有大量的特殊符号。

4 结 论 在STC算法基础上，使用雅克比系数计算基本类的相似度，使基本类相似度为介于0和1之间的值，产生基本类相似度矩阵，进而采用变色龙算法完成网页的层次聚类。 实验结果表明该方法提高了聚类精度，同时避免了单链接算法的链式效应。

6 参考文献 [1] O. Zamir, O. Etzioni. Web document clustering: A feasibility demonstration[C]. In: Proceedings of SIGIR, 1998:46–54. [2] G Karypis, EH Han, V Kumar. Chameleon: hierarchical clustering using dynamic modeling [J]. Computer, 1999, 32: 68-75. [3]R. Krishnapuram, K. Kummamuru. Automatic taxonomy generation: Issues and possibilities [J].LNCS: In: Proceedings of Fuzzy Sets and Systems (IFSA), Springer-Verlag Heidelberg, 2003, 2715: 52–63.