基于语义串特征提取及融合评价的维吾尔文文本聚类

吐尔地·托合提， 维尼拉·木沙江，艾斯卡尔·艾木都拉

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

基于语义串特征提取及融合评价的维吾尔文文本聚类

吐尔地·托合提， 维尼拉·木沙江，艾斯卡尔·艾木都拉

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

该文研究一种改进的n元递增算法来抽取文本中表达关键信息的语义串，然后用多特征融合的评价方法为每一个文本选取最重要的语义串，并用这些语义串作为特征表示文本。通过K_means聚类分析的实验结果表明，以语义串作为特征可以构造比单词特征集更紧凑的文本模型，不仅可以大大降低特征空间的维度，对于提高聚类算法性能也是非常有效的。

维吾尔文；语义串抽取；特征评价及选取；向量空间模型；K_means

1 引言

在文本聚类中，先对文本集进行切分和特征提取，然后评价特征集中每一个特征的重要度并选取一个特征子集来表示文本集，最后用这个特征子集去计算并对文本集进行归类。因此，提取什么样的特征，如何评价和选取一个最佳特征子集是文本聚类的主要研究课题[1]。

关于特征提取，常用的方法是对文本进行分词，并以词为特征表示文本。但是，词的语义表达能力有限，还有多义、歧义等现象的存在，用词特征往往不能很好地表示文本[2]。除此之外，用词特征表示文本时，特征空间的高维性和类间交叉特征的出现是制约聚类算法性能的主要因素[3]。因此，越来越多的研究者在探索从文本中抽取比单词更具体而完整的语言单元作为表达信息特征的方法[4-6]。

维吾尔文属于阿尔泰语系突厥语族，是一种拼音文字。从文字表面上看，维吾尔文是以空格隔开的词的序列，在这一特点上跟英文有点类似。因此，常以空格作为自然分隔符，简单获取文本中的词。由于这种简单分词方法具有很明显的局限性和不足，因此以词特征表示文本时的维吾尔文聚类算法效果总是不能被接受。其实，维吾尔文中能表达一个完整语义的最小语言单元常常不是一个单词，而是突破词语概念界限的语义串[7]，其特点是： 文本中上下文任意多个连续字符(字或词)的稳定组合，其结构是稳定不可分割的，是语义完整的语言单元，如固定搭配、对偶词、习语等具有词汇意义及语法意义的模式串[8]、词组或短语[9]、复合词或领域术语[10]，还有命名实体等。文本认为，句子可以表达一个完整、连贯及易于理解的语义，而语义串能蕴含句子里的关键信息。因此，选语义串作为特征来表示文本，就能够有效地刻画文本的主题，这样就有利于正确度量文本相似性[11]。

因此，我们研究了一种基于改进的n元递增算法及语言规则相结合的方法，抽取文本中表达关键信息的语义串集，并从结构完整性、类别区分能力和所表达的信息量等方面综合评价每一个语义串，从而选取一个语义串子集，并将它作为特征子集来构造文本模型。最终，我们设计了多个实验并进行K_means聚类分析，实验结果表明，本文提出的方法有效解决了以维吾尔文词特征表示文本时的特征空间高维性、较高的计算量和聚类算法效率低等问题。

2 语义串识别及抽取

本文提出的语义串抽取方法是在单词(词干)的基础上，按文本书写方向进行向下扩展，从而识别并抽取文本中的语义串。这就需要统计每一个单词或词串的出现频次、单词长度、出现的位置、词性及上下文等统计信息。因此，我们设计了一种多层动态索引结构来存储以上信息[12]，并在此基础上识别文本中的频繁模式，然后对每一个频繁模式进行完整性评价，从而获取结构及语义完整的语义串。频繁模式的发现是对n元递增算做的改进[13]，语义串的抽取过程主要按以下几个步骤进行。

2.1 建多层动态索引

文本集中所有文本经过预处理之后，首先按每一个单词在对应文本中出现的顺序进入一个词典，然后根据生成的单词ID序列建词索引。例如，对于一个只有六个单词的文本“ABCF#EFCEABCFD#EFCADFECDABCFACD#”(#为不同标点符号)，建词索引如图1所示。

一级索引中，termID是一个单词或串在索引中唯一的ID，Freq是该term在语料中的频次，is_stop为停用词标志，is_adj是形容词标志，Unit_count是该term的单词长度，也就是串中包含的单词个数， Pos_pointer，Rv_pointer和Lv_pointer分别是对应的二级索引入口地址的偏移量。二级索引是索引项列表，其入口地址是从一级索引获取的。二级索引中的每一个项是该term在文本集中的概要描述。其中，Pos_pointer指向的是该索引项的位置倒排；Lv_pointer指向的是该term的左邻接列表，是该term所有的左邻接及其出现频次；Rv_pointer指向的是该term的右邻接列表，是该term所有的右邻接及其出现频次。

通过这样的索引结构，可以描述文本集中任何一个单词或串尽可能多的属性，其动态性、效率及扩展性等也能满足海量文本处理的需求。

2.2 词串扩展及频繁模式发现

开始时，将所有单词(ID)调入一个队列中，然后根据每个单词在索引中的统计信息判断其向它的下文扩展的可能性，这样就得到其二词或三词串，然后让已被扩展单词出队，并将新产生的扩展串入队，继续判断并从n词串扩展得到n+1或n+2词串，反复迭代，直到队列为空为止。串扩展前单词索引及扩展候选队列初始状态如图2所示。

在串扩展中，需要判断一个单词或串能否与其下文(单词或串)结合成为一个关联模式的可能性。在本文中，我们用语言规则、置信度及逆置信度的评价指标[14]。其中，置信度(Confidence)是指单词关联wi-1→wi的上文(前件)wi-1出现的情况下，其下文是wi的条件概率。逆置信度(R-Confidence)是指单词关联wi-1→wi的下文(后件)wi出现的情况下，其上文是wi-1的条件概率，计算公式如下：

可见，置信度评价的是单词关联的上文在本关联中的比重，而逆置信度是用来度量单词关联的下文对此关联强度的共现。因此，当Confidence(wi-1，wi)gt;minconf或R-Confidence(wi-1，wi)gt;minconf时,则可以判定词串wi-1wi为可信频繁模式(trusted frequent pattern，TFP)。

在本文研究中，我们还发现维吾尔文以下语言特性对文本中关联模式的识别非常有用。

特性1维吾尔文中的连词、助词、副词、代词、量词及感叹词等功能词，在文本中始终不会跟其他单词结合成为强关联模式。在本文研究中，我们将这类词统称为“独立词”(independent word,IW)。

特性2维吾尔文单词之间的结合主要是在名词(N)、 形容词(ADJ)和动词(V)之间发生，并构成语义串。其中，当形容词与名词或形容词与动词结合时，形容词总是作为前驱，而不会出现在后继位置上。因此，N+ADJ或V+ADJ的相邻单词绝不会结合为一个语义串。

图1 多层动态索引示例

图2 串扩展初始状态示例

根据以上的语言特性，我们归纳出了用于词间关联性辨别的单词结合规则(word association rule,WAR)，定义如下：

定义1(单词结合规则： WAR)： 对于文本中的相邻词对“AB”，如成立条件： A ∈{IW} or B ∈{IW} or B∈{ADJ}，则A与B不能结合成为关联模式。

根据以上规则和评价指标，假定A、B是文本中相邻的两个单词(或串)，A是B的上文(右邻接词)，B是A的下文(左邻接词)，如要进行“A→AB”的扩展，则“AB”需满足以下条件 ：

① A不是停用词，即is_stop(A)=0；

② A是频繁模式，即Freq(A)gt;=2；

③ B不是停用词或形容词，即is_adj(B)=0且is_stop (B) =0；

④ B是频繁模式，即Freq(B)gt;=2；

⑤ AB是可信频繁模式，即Confidence(A→B)gt;minconf且R-Confidence(A→B) gt;minconf；

以上例子中，当队头单词A出队后，因为A具备条件①和②，因此从二级索引中读取A的左邻接列表，然后根据条件③、④、⑤依次判断A跟其每一个下文(左邻接)词构成新串的可能性。本例中，A的第一个左邻接B具备条件③和④，同时A与B构成的扩展串AB也具备条件⑤，因此将新产生的串AB入队，同时将它的信息追加到索引中，然后判断A跟其下一个左邻接词C的关联强度，依次判断并进行从单词到二词扩展，直到A的所有左邻接词都被访问完为止(A与C和D都不能结合)。此时，候选队列及索引变化情况如图3所示。

图3 串扩展示例1

之后，让当前队头单词B出队，因为B已跟A结合，就不再进行扩展，然后是C出队。就这样，依次对每一个单词进行二词或三词扩展，同时将新产生的二词或三词串入队，等待继续被扩展。当所有单词都被访问完之后，候选队列及索引变化情况如图4所示。

图4 串扩展示例2

等所有单词的二词或三词串扩展完毕之后，就接着进入从串扩展更长串的过程，直到串扩展候选队列为空，此时，频繁模式发现过程全部结束。

2.3 模式串完整性评价及语义串抽取

一个串能成为语义串的前提是，它在结构、语义、语用及统计上应能满足一定的特点。通过以上频繁模式识别得到的结果只能满足可统计性要求，被称为语义串候选，但这还需要采用语言模型或上下文邻接分析等方法进一步的甄别和过滤[15]。在本文研究中，我们所采取的方法与中文有所不同。主要原因是：

① 中文常用功能字会跟其他汉字构成实词，如“的士、嘿店”等。因此，对于串首或串尾出现功能字的情况，还需判断串首、串尾双字耦合度，以及词首和词尾成词概率。另外，因为所有的汉字都不能作为词首或词尾，因此可以通过计算单字位置成词的概率来判断串首和串尾， 可以有效地过滤垃圾串。但是维吾尔文与中文不同。首先，维吾尔文中的功能词一般不会跟其他词结合并构成新词。另外，维吾尔文中的词语本来就是一个独立运用的语言单元，词在串首或串尾位置用法上没有特定规律(形容词除外)。

② 在维吾尔文语义串识别及抽取中，我们当然可以采取与中文类似的方法，判断模式串串首和串尾的“双词”耦合度，这样对垃圾串过滤肯定会有一定的帮助，但这需要大量的学习语料和人工标注工作来构建双词耦合度词典。然而，本文研究的目的是基于无监督学习的语义串识别及抽取方法。

③ 关于语言模型的模式串分析方法，本算法已引入单词结合规则，并把它嵌入到串扩展及频繁模式发现过程中，因而有效避免了串尾出现形容词从而产生垃圾串的情况，在一定程度上减轻了垃圾串过滤任务。

因此，本文主要是根据上下文邻接特征来判断每一个语义串候选的结构完整性。中文相关研究结果表明，采用邻接熵的结果比其他三种邻接特征量(邻接种类，邻接对种类，邻接对熵)的结果好[16]。因此，我们用式(3)为每一个候选语义串赋权重：

式(3)中，AEweight(S)是模式串S的邻接熵(adjacency entropy： AE)权重，RAE(S)是S的右邻接熵，LAE(S)是S左邻接熵。右 (左)邻接熵计算公式为：

式(4)中，m是模式串S的左邻接种类个数，ni是模式串S的第i个左邻接频次，N为全部左邻接频次总和。以上计算邻接特征量所需的所有信息，在这些模式串被发现时早已被记录好并存入索引中。最后，依次选取邻接特征量达到给定阈值的频繁模式，就获得最终要得到的语义串集。语义串的抽取流程如图5所示。

图5 语义串抽取流程

3 语义串评价及语义串特征提取

3.1 语义串基本特征

① 邻接熵特征。邻接特征表示语义串在语用环境中的结构完整性，而结构完整的词串总是能表达与文本主题相关的关键信息。因此，我们可以用邻接特征量去评价语义串的重要度，邻接特征量越大，表明语义串结构越完整，其表达的信息也越具体，而这样的特征可以为学习算法提供判断文本相似度的重要信息。邻接特征有多种，我们选邻接熵作为权重评价语义串的重要度。

② TFIDF特征。对于一个语义串项来说，如果它的频次特别低或者该语义串在大部分文本中都出现，则这样的语义串就没有类别区分能力，不应选择为文本特征。根据TFIDF评价函数的定义，在文本集中具有较高的频次及在少一部分文本中出现的语义串，其类别区分能力会比较大，因此为它赋予较大的权重。

③ 长度特征。语义串的长度与其表达的信息量成正比关系，因此长度越长，语义串表达的信息量也越大，语义更具体而完整。例如，语义串“高速公路收费系统”的信息量比“高速”、“高速公路”和“高速公路收费”都大，如这样的语义串在同一类文本中重复出现，则其区分类别能力也非常大，因此也为这样的特征赋予更大的权重。

3.2 多特征融合的语义串评价

在以上几种特征中，邻接熵值的大小既能体现语义串频次又能反映其语义完整性，TFIDF特征则反映语义串的类别区分能力，而长度特征是语义串表达信息量的度量。因此，根据不同特征在语义串评价中的重要度，给出了如下综合评价公式，即

其中，Wi是语义串集中第i个语义串权重，AEweight是用式(3)计算得到的邻接熵，Unit_count是该语义串包含的单词个数。TFIDFweight计算公式中，TF是第i个语义串在语义串集中的频次，IDF是该语义串逆文档频率。

最终，我们用式(5)依次计算每一个文本中的语义串权重，然后按权重大小排序，并选取权重最高的TopN个语义串作为特征，从而得到文本集的特征子集。

4 实验与分析

在现有多种文本表示方法中，向量空间模型(vector space model，VSM)具有模型构造简单、系统易于实现、还能通过调节对应权重的大小来反映特征项与所在文档的相关程度、易于对向量进行修改等特点，因此被广泛接受。除此之外，我们在前期研究工作中，曾在以词为特征的VSM上进行维吾尔文聚类研究，主要工作是如何找到正确的类中心，从而提高K_means聚类效率[17]。而本文研究目的是，要验证以语义串作为特征表示文本的方法能否提高聚类算法的性能。

因此，我们仍然采用VSM构建文本模型，即单词特征VSM和语义串特征VSM，然后通过K_means聚类实验结果对比来分析并验证本文提出的语义串特征提取及融合评价方法的正确性和有效性。

4.1 实验语料

本实验使用新疆大学智能信息处理重点实验室提供的人工分类语料，包括健康类、交通类、教育类、经济类、体育类和宗教类，每类均为300篇，共1 800篇文本。

4.2 评价指标

常用的评价指标包括准确率(precision)、召回率(recall)和F-measure等。

P(准确率)=聚类正确的文本数/实际聚类的文本数

R(召回率)=聚类正确的文本数/应有的文本数

F-measure=2PR/(P+R)

我们对实验数据分别进行传统分词和语义串抽取并得到两份特征集，对通过分词得到的单词特征采用TFIDF评价函数进行权重计算，而对语义串特征采用本文提出的融合评价方法进行权重计算。实验中，我们主要观察分别用两种特征表示文本时的特征空间维度和算法性能的变化情况。

4.3 两种特征集的特征空间维度

本试验中，我们按一定比例为每一个文本选取权重最高的若干个特征来获取文本集的特征子集，不同规模特征子集包含的特征个数如表1所示。

表1 不同规模特征子集及特征个数

续表

4.4 两种文本特征集的聚类效率

从表1可以看出，语义串特征的提取明显降低了特征空间维度，这也应该体现在聚类算法效率的提高上。因此，我们以表1中不同规模特征子集表示文本，对比以单词特征和语义串特征表示文本时的K_means聚类效率，结果如图6所示。

图6 两种特征集的K_means聚类效果

4.5 多特征融合的语义串评价方法的有效性

本文中，我们从结构完整性(AE)，蕴含的信息量(Unit_count)，以及类别区分能力(TFIDF)等方面对语义串进行评价，并从按评价得分从高到低的排序序列中选取TopN个语义串来获得文本特征子集。因此，为了观察不同特征对于语义串评价及聚类效率的影响，我们采用不同特征的组合在实验数据集上分别做实验，得到如表2所示结果。

表2 单特征和多特征融合评价情况下的聚类效率

表2列出了不同策略单独使用和使用组合策略情况下的实验结果。可以看出，使用组合特征策略总比使用单特征策略好。

图7展示了三种策略单独使用和两两组合时的聚类结果对比。从F-measure值来看，单独使用AE评价语义串时的聚类效率最好，这表明选取AE值越高的语义串作为文本特征，能够选取结构及语义更完整的语义串特征，同时能够有效防御垃圾串的选入。对于组合策略来说，AE和TFIDF融合评价时的聚类效率较好，AE和Unit_count的组合也能选取重要的文本特征。

我们还采用逐步增加策略的方式做实验，观察了聚类效率评价指标变化情况，实验结果如图8所示。

图7 不同评价策略及聚类结果

图8 逐步增加策略时的实验结果

可以看出，每增加一个语义串重要度评价策略，各个聚类评价指标也相应地逐步上升，说明每一种策略都在起作用。在三种策略融合的评价方法中，因为同时从语义串的结构完整性、蕴含的信息量以及类别区分能力等方面进行综合评价，因此为每一个文本选取的语义串特征就能更好地表示文本主题，这是聚类算法得到较高聚类效率的前提。

5 结语

用传统分词方法获取的维吾尔文文本特征集，因为存在大量的语义抽象和多义的单词特征，不能很好地表征文本，因此无法得到较好的聚类效果。本文用统计和浅层语言分析的方法，从文本中抽取结构完整的、表达关键信息的语义串进行综合评价,并用语义串来表示文本，最后以K_means算法分别做了多个聚类实验，观察了以单词特征和语义串特征表示文本时的特征空间维度和算法性能的变化情况。实验结果表明，用语义串特征表示文本是特征空间降维的有效方法，用多特征融合的评价方法可以有效地获取最重要的语义串特征，因此聚类效率也得到了明显的提高。

[1] 刘远超,王晓龙,徐志明,等. 文档聚类综述[J].中文信息学报,2006,20(3):55-62.

[2] Mostafa M S， Haggag M H, Gomaa W H. Document clustering using word sense disambiguation[C]//Proceedings of the 17th International Conference on Software Engineering and Data Engineering, 2008:19-24.

[3] 徐燕,李锦涛,王斌,等.基于区分类别能力的高性能特征选择方法[J]. 软件学报, 2008,19(1):82-89.

[4] Bakr A M, Yousri N A, Ismail M A. Efficient incremental phrase-based document clustering[C]//Proceedings of the 21st International Conference on Pattern Recognition,2012: 517-520.

[5] Wu C B, Zhang Q. Text clustering based on combined features of concepts and words[J]. Journal of Information and Computational Science,2012,9(15): 4253-4260.

[6] Marcacini R M, Correa G N, Rezende S O. An active learning approach to frequent itemset-based text clustering[C]//Proceedings of the 21st International Conference on Pattern Recognition,2012: 3529-3532.

[7] Turdi Tohti,Winira Musajan, Askar Hamdulla.Unsupervised learning and linguistic rule based algorithm for Uyghur word segmentation[J]. Journal of Multimedia, 2014, 9(5):627-634.

[8] Candito M, Constant M. Strategies for contiguous multiword expression analysis and dependency parsing[C]//Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014-Proceedings of the Conference,2014: 743-753.

[9] Rais N H, Abdullah M T, Kadir R A. Multiword phrases indexing for Malay-English cross-language information retrieval [J]. Information Technology Journal, 2011,10(8): 1554-1562.

[10] Murata Masaki, Masao U. Compound word segmentation using dictionary definitions-extracting and examining of word constituent information [J]. ICIC Express Letters: Part B Applications, 2012, 3(3): 667-672.

[11] Eldesoky A E, Saleh M, Sakr N A. Novel similarity measure for document clustering based on topic phrases[C]//Proceedings of International Conference on Networking and Media Convergence, 2009: 92-96.

[12] Ma Y, Wang L. Dynamic indexing for large-scale collections[J]. Journal of Beijing Normal University(Natural Science),2009,45(2):134-137.

[13] Kiran R U, Reddy P K. An improved frequent pattern-growth approach to discover rare association rules[C]//Proceedings of the 1st International Conference on Knowledge Discovery and Information Retrieval,2009: 43-52.

[14] Jain J K, Tiwari N, Ramaiya M. Mining positive and negative association rules from frequent and infrequent pattern using improved genetic algorithm[C]//Proceedings of the 5th International Conference on Computational Intelligence and Communication Networks,2013: 516-521.

[15] Tiwari A, Gupta R K, Agrawal D P. A survey on frequent pattern mining: Current status and challenging issues [J]. Information Technology Journal, 2010, 9(7): 1278-1293.

[16] 张华平,高凯 ,黄河燕,等.大数据搜索与挖掘[M].北京:科学出版社,2014.

[17] 吐尔地·托合提,艾海麦提江·阿布来提,米也塞·艾尼玩,等.一种结合GAAC和K-means的维吾尔文文本聚类算法[J].计算机工程与科学,2013,35(7):149-155.

吐尔地·托合提(1975—)，副教授，博士，硕士生导师，主要研究领域为自然语言处理及文本挖掘。

E-mail：turdy@xju.edu.cn

维尼拉·木沙江(1960—)，教授，硕士生导师，主要研究领域为自然语言处理及信息检索。

E-mail：winira@xju.edu.cn

艾斯卡尔·艾木都拉(1972—)，教授，博士，博士生导师，主要研究领域为智能信息处理。

E-mail：askar@xju.edu.cn

AWeightedSemanticString-BasedApproachtoUyghurTextClustering

Turdi Tohti， Winira Musajan， Askar Hamdulla

(School of Information Science and Engineering, Xinjiang University, Urumqi, Xinjiang 830046, China)

This paper proposes an improved frequent pattern-growth approach to discover and extract the semantic strings which express key information in the text, It then assigns weights to them via a multi-feature fusion method and select the most important semantic strings as features to represent the text. The experimental results by K_means cluster shows that the text model constructed by semantic string feature is more compact than the text model constructed by word feature, not only greatly reducing the dimensions of feature space but also improving the performance of clustering algorithm.

Uyghur language; semantic string extraction; feature evaluation and selection; vector space model; K_means

1003-0077(2017)05-0099-09

TP391

A

2015-10-15定稿日期2016-05-12

国家自然科学基金(61562083,61262062,61262063)