面向维吾尔语文本的改进后缀树聚类

摘要:针对后缀树聚类选取基类时，基类短语出现信息不规范、重复和冗余的问题，提出了一种改进后缀树聚类算法。该算法首先以短语互信息算法改进基类的选取，选出遵守维吾尔语语法规则的基类短语；然后，利用短语归并算法对选取的重复基类短语进行归并；最后，在前两步的工作基础上，利用短语去冗余算法处理冗余的基类短语。实验证明，与传统后缀树聚类(STC）相比，改进后缀树聚算法的全面率、准确率都得到了提高。这表明，改进算法有效地改善了聚类效果。

关键词:维吾尔语；后缀树；互信息；归并；冗余

中图分类号: TP391.1文献标志码:A

Improved suffix tree clustering for Uyghur text

ZHAI Xian.min1*, TIAN Sheng.wei2, YU Long3, FENG Guan.jun4

1. College of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China;

2. College of Software, Xinjiang University, Urumqi Xinjiang 830008， China;

3. Network Center, Xinjiang University, Urumqi Xinjiang 830046, China;

4. College of Humanities, Xinjiang University, Urumqi Xinjiang 830046, China

Abstract:

In order to solve the problems of irregular, repetition and redundancy of information in the process of selecting the base class phrases, an improved suffix tree clustering (STC) method is proposed. Firstly, phrase mutual information algorithm is put forward to choose the base class phrases abiding by Uyghur grammar. Secondly, in order to reduce the repeated base class phrase, the phrase reduction algorithm based on Uyghur grammar is proposed. Thirdly, on the basis of the first two steps, the phrase redundancy algorithm based on Uyghur grammar is constructed to remove redundant phrase. The experimental results show that this method improves the recall and the precision compared STC. This indicates that the improved algorithm can enhance clustering results effectively.In order to solve the problems of non.standard, repetition and redundancy of information in the process of selecting the base class phrases, an improved Suffix Tree Clustering (STC) method was proposed. Firstly, phrase mutual information algorithm was put forward to choose the base class phrases abiding by Uyghur grammar. Secondly, in order to reduce the repeated base class phrase, the phrase reduction algorithm based on Uyghur grammar was proposed. Thirdly, on the basis of the first two steps, the phrase redundancy algorithm based on Uyghur grammar was constructed to remove redundant phrase. The experimental results show that this method improves the recall and the precision compared with STC. This indicates that the improved algorithm can enhance clustering performance effectively.

Key words:

Uyghur; Suffix Tree (ST); Mutual Information (MI); reduction; redundancy

0 引言

后缀树聚类(Suffix Tree Clustering，STC)算法是Zamir［1］最先提出的一种快速聚类算法。与基于向量空间模型的K.Means［2］、Single.Pass［3］和SOM［4］不同，STC算法是基于文本间共享短语的算法。文献［5］中对此进行了对比实验，结果证明与基于向量空间模型的算法相比，基于短语的STC算法有效地考虑了词与词的关系，产生了比较好的聚类效果。但是，STC算法依然存在不足，这些不足主要表现在时间复杂度、空间复杂度以及信息的抽取和利用等方面。近年来针对STC算法的不足，学者们提出来许多STC的改进方法。文献［6］提出一种使用新数据结构的并行算法，这个算法降低了STC算法的时间复杂度。文献［7］利用x元数据结构进行后缀树的构造，优化了STC存储结构，降低了空间复杂度。然而，越来越多的学者对信息的抽取和利用进行了改进。文献［8］提出STC+和NM.STC两种算法:STC+通过突显主题词的打分公式，使STC+有所偏向地选取特征词，提高了选取特征词的准确率;NM.STC通过组织层次类簇的方法，提高了STC的处理速度，降低了时间复杂度。文献［9］通过给出一个基类选择测度以及修改的基类合并相似度公式，对STC算法进行了改进。为了发现文档中常用并且有意义的主题短语，文献［10］提出了在STC算法中使用潜在语义的索引方法。文献［11］采用倒排索引对文档的重复词进行处理，使STC降低了删除重复词的错误率。文献［8,11］中提出的算法，是为了提高STC算法中信息抽取的正确率或信息的利用率，但是这些算法并没有完全解决信息抽取和利用的问题，所以对文档信息的抽取和利用需要继续研究。

在STC算法中，后缀树得到的基类就是文档的信息，所以对基类选取和利用的研究就是对信息抽取和利用的研究。本文对STC算法中基类选取算法进行改进，提出了短语互信息（Phrase Mutual Information, PMI）算法、短语归并（Phrase Reduction, PR）算法和短语去冗余算法，结合维吾尔语语法规则，形成了改进后缀树聚类（Suffix Tree Clustering base on Phrase Mutual Information and Reduction, PMIR.STC）算法。实验证明了PMIR.STC算法增强了选取短语的有效性与正确性，最终提高了STC算法聚类的全面率和准确率。

1 改进后缀树聚类算法

与STC算法类似，PMIR.STC的聚类算法也有4个步骤:1)对文本信息集进行预处理；2)构造文本信息集的后缀树模型；3)利用添加PMI算法的公式，计算基类的分值，选择基类，然后对基类短语进行归并和去冗余；4)合并基类，形成最终聚类结果。

1.1 相关概念

定义1 后缀树(Suffix Tree, ST)。包含n个词的句子s的后缀树T，是一个有且仅有n个叶子的树，对于每一个非根节点，至少有两个子节点，且每一条边都表示一个s的子串。从一个节点发出的两条边不能包含相同词开始的子串。后缀树的最重要的特征就是对于任何一个叶子k，从根到该叶子的整个路径上的边串联起来的内容就是s从位置k起的后缀子串，即s［k…n］。

定义2 短语。除根节点之外的任何一个节点所对应的短语为从根到本节点的边串联起来的内容。

定义3 基类。又称基本类簇，STC算法中，基本类簇是通过短语类簇表示，短语类簇是一些具有共同短语的文档的集合。

定义4 基类短语。基类文档集所共有的公共短语。

定义5 候选基类。对基类文档数目设置一个阈值（本文取值为1），超过阈值的作为候选基类。

定义6 临时基类。在基类合并之前，由基类选取算法选取的候选基类，称为临时基类。

定义7 短语冗余。如果一个短语包含在另一个短语中，称这一短语冗余。

算法1 短语归并算法。对任意临时基类A和C，首先把A和B的基类短语进行前缀提取，得到A′和C′，具体的过程：把临时基类短语按空格分词，形成词组，对每个词进行提前缀，然后按原来顺序把词拼成处理后的基类A′和C′，若存在关系

A′=g(C′)(1)

则把两临时基类短语进行归并，归并的方式是把临时基类C的信息完全添加至临时基类A的信息中。函数关系式y=g(x)代表短语x、y互相包含。

“亚欧博览会”已经包含了“博览会”的信息，出现冗余，由于冗余短语在STC算法的后续聚类中没有意义，所以需要对短语去冗余，即删除短语“博览会”及其所代表的信息。

通过算法2对临时基类进行去冗余，也将会导致临时基类数目减少，因此，需要添加新的候选基类，再对临时基类进行短语去冗余，如此递归选取候选基类进行补充和再去冗余，直至短语去冗余处理后的基类数目仍为m。

1.5 基类的合并

由于选取的基类可能存在文档集高度重合的问题，为避免相同类的出现，必须合并高度重合的基类。

基类合并的过程，任意两个基类Dm和Dn，如果存在如下关系，则进行合并:

|Dm∩Dn||Dm|>α and |Dm∩Dn||Dn|>α(7)

其中：|Dm∩Dn|是基类Dm和Dn文档集中相同文档的数目，|Dm|是基类Dm所代表文档集的文档数目，|Dn|是基类Dn所代表文档集的文档数目。

2 实验结果与分析

2.1 实验的数据集

由于维吾尔语中没有英语reuters21578和汉语TanCorp.V1.0等已建好的类别语料库，本文使用的是从维吾尔语网站收集的经人工分类的话题集。话题集包含第26届大运会、第1届亚欧博览会、“7.23”动车追尾事故等20个话题，每个话题包含20～60个相关话题文档，共594个话题文档，每个文档词数40～600，平均词数82。为满足实验需求，基于以上话题集设置如下3组数据。

数据1 选取这20个话题，每个话题中任选20个相关话题文档，总共400个话题文档。

数据2 从20个话题中任选10个，每个话题中任选20个相关话题文档，总共200个话题文档。

数据3 选取这20个话题，每个话题中的相关话题文档全部选取，总共594个话题文档。

2.2 评价指标

为了检测文本聚类的质量，本文使用了文献［12］的质量评价指标：错误率、全面率、准确率。

由图2和图3可知，在平衡数据1和平衡数据2中，STC算法比其他算法性能优越，PMIR.STC算法比STC算法性能优越。由图4中可知，在非平衡数据3中，STC算法的聚类效果比其他算法的好， PMIR.STC算法的聚类效果比STC算法的好。这说明，与基于向量空间模型的其他算法相比，基于短语的STC算法对信息进行了更有效的抽取和利用，得到较好的聚类效果；而无论是平衡数据，还是非平衡数据，PMIR.STC算法都表现出比STC算法更好的性能。这证明本文提出的改进算法有效地提高了STC算法的性能。

3 结语

本文通过提出PMI算法、短语归并算法和短语去冗余算法，改进了基类短语的选取，使基类短语更具有可读性与代表性，实验表明改进算法有效地提高了STC算法的性能。当前网络快速发展，信息爆炸式增长，今后研究可以放在深入挖掘Web文档的信息上，响应网络信息的快速增长，虽然文献［13-14］都提出了针对Web文档的结构及其特征的聚类算法，但是还需要挖掘更多的Web文档信息，例如：时间、关注度等，以满足网络信息聚类更高的要求。

参考文献:

［1］

ZAMIR O, ETZIONI O, MADANI O, et al.Fast and intuitive clustering of Web documents ［C］// Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. New York: AAAI Press, 1997: 287-290.

［2］

HONG YI, SAM K. Learning assignment order of instances for the constrained K.means clustering algorithm ［J］. IEEE Transactions on Systems Man and Cybernetics Part B.Cybernetics, 2009, 39(2): 568-574.

［3］

HALL L O, GOLDGOF D B. On convergence properties of the singlepass and online fuzzy c.means algorithm ［C］// 2010 IEEE International Conference on Fuzzy Systems, Washington, DC: IEEE, 2010: 1-3.

［4］

AIOLLI F, SAN.MARTINO G, HAGENBUCHNER M， et al. Learning nonsparse kernels by self organizing maps for structured data ［J］. IEEE Transactions on Neural Networks, 2009, 20(12): 1938-1949.

［5］

ZAMIR O, ETZIONI O. Web document clustering: A feasibility demonstration ［C］// SIGIR ’98: Proceedings of the 21st International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press, 1998: 46-54.

［6］

CHEN CHUNXI, BERTIL S. Parallel construction of large suffix trees on a PC cluster ［C］// Euro.Par 2005 Parallel Processing: 11th International Euro.Par Conference. Berlin: Springer, 2005: 1227-1236.

［7］

WANG JUNZE, MO YIJUN, HUANG BENXIONG, et al. Web search results clustering based on a novel suffix tree structure ［C］// Autonomic and Trusted Computing: 5th International Conference. Berlin: Springer,2008: 540-554.

［8］

KOPIDAKI S, PAPADAKOS P, TZITZIKAS Y. STC+ and NM.STC: two novel online results clustering methods for Web searching ［C］// WISE 2009: 10th International Conference. Berlin: Springer, 2009: 523-537.

［9］

杜红斌，夏克文，刘南平,等.一种改进的基于广义后缀树的文本聚类算法［J］.信息与控制，2009, 38(3)：3331-336.

［10］

HAN WEN, GUO.SHUN HUANG, ZHAO LI. Clustering Web search results using semantic information ［C］// Proceedings of the Eighth International Conference on Machine Learning and Cybernetics. Liverpool: World Academic Press, 2009: 1504-1509.

［11］

WANG HUIJIAO, YIN BO, HOU JIE. An improved algorithm of STC for the deletion of duplicated Web pages based on repeated strings［C］// Proceedings of 2009 Third International Conference on Genetic and Evolutionary Computing. Washington, DC: IEEE CS, 2009: 414-417.

［12］

闵可锐，赵迎宾，刘昕,等.互联网话题识别与跟踪系统设计及实现［J］.计算机工程，2008，34(19）：212-214.

［13］

杨瑞龙，朱庆生，谢洪涛,等.一种新的加权后缀树Web文档聚类方法［J］.系统仿真学报，2011，23(3)：474-479.

［14］

李睿，曾俊，周四望.基于局部标签树匹配的改进网页聚类算法［J］.计算机应用，2010，30(3)：818-810.