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

(新疆大學 信息科學與工程學院，新疆 烏魯木齊 830046)

基于語義串特征提取及融合評價的維吾爾文文本聚類

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

(新疆大學 信息科學與工程學院，新疆 烏魯木齊 830046)

該文研究一種改進的n元遞增算法來抽取文本中表達關鍵信息的語義串，然后用多特征融合的評價方法為每一個文本選取最重要的語義串，并用這些語義串作為特征表示文本。通過K_means聚類分析的實驗結果表明，以語義串作為特征可以構造比單詞特征集更緊湊的文本模型，不僅可以大大降低特征空間的維度，對于提高聚類算法性能也是非常有效的。

維吾爾文；語義串抽??；特征評價及選?。幌蛄靠臻g模型；K_means

1 引言

在文本聚類中，先對文本集進行切分和特征提取，然后評價特征集中每一個特征的重要度并選取一個特征子集來表示文本集，最后用這個特征子集去計算并對文本集進行歸類。因此，提取什么樣的特征，如何評價和選取一個最佳特征子集是文本聚類的主要研究課題[1]。

關于特征提取，常用的方法是對文本進行分詞，并以詞為特征表示文本。但是，詞的語義表達能力有限，還有多義、歧義等現(xiàn)象的存在，用詞特征往往不能很好地表示文本[2]。除此之外，用詞特征表示文本時，特征空間的高維性和類間交叉特征的出現(xiàn)是制約聚類算法性能的主要因素[3]。因此，越來越多的研究者在探索從文本中抽取比單詞更具體而完整的語言單元作為表達信息特征的方法[4-6]。

維吾爾文屬于阿爾泰語系突厥語族，是一種拼音文字。從文字表面上看，維吾爾文是以空格隔開的詞的序列，在這一特點上跟英文有點類似。因此，常以空格作為自然分隔符，簡單獲取文本中的詞。由于這種簡單分詞方法具有很明顯的局限性和不足，因此以詞特征表示文本時的維吾爾文聚類算法效果總是不能被接受。其實，維吾爾文中能表達一個完整語義的最小語言單元常常不是一個單詞，而是突破詞語概念界限的語義串[7]，其特點是： 文本中上下文任意多個連續(xù)字符(字或詞)的穩(wěn)定組合，其結構是穩(wěn)定不可分割的，是語義完整的語言單元，如固定搭配、對偶詞、習語等具有詞匯意義及語法意義的模式串[8]、詞組或短語[9]、復合詞或領域術語[10]，還有命名實體等。文本認為，句子可以表達一個完整、連貫及易于理解的語義，而語義串能蘊含句子里的關鍵信息。因此，選語義串作為特征來表示文本，就能夠有效地刻畫文本的主題，這樣就有利于正確度量文本相似性[11]。

因此，我們研究了一種基于改進的n元遞增算法及語言規(guī)則相結合的方法，抽取文本中表達關鍵信息的語義串集，并從結構完整性、類別區(qū)分能力和所表達的信息量等方面綜合評價每一個語義串，從而選取一個語義串子集，并將它作為特征子集來構造文本模型。最終，我們設計了多個實驗并進行K_means聚類分析，實驗結果表明，本文提出的方法有效解決了以維吾爾文詞特征表示文本時的特征空間高維性、較高的計算量和聚類算法效率低等問題。

2 語義串識別及抽取

本文提出的語義串抽取方法是在單詞(詞干)的基礎上，按文本書寫方向進行向下擴展，從而識別并抽取文本中的語義串。這就需要統(tǒng)計每一個單詞或詞串的出現(xiàn)頻次、單詞長度、出現(xiàn)的位置、詞性及上下文等統(tǒng)計信息。因此，我們設計了一種多層動態(tài)索引結構來存儲以上信息[12]，并在此基礎上識別文本中的頻繁模式，然后對每一個頻繁模式進行完整性評價，從而獲取結構及語義完整的語義串。頻繁模式的發(fā)現(xiàn)是對n元遞增算做的改進[13]，語義串的抽取過程主要按以下幾個步驟進行。

2.1 建多層動態(tài)索引

文本集中所有文本經(jīng)過預處理之后，首先按每一個單詞在對應文本中出現(xiàn)的順序進入一個詞典，然后根據(jù)生成的單詞ID序列建詞索引。例如，對于一個只有六個單詞的文本“ABCF#EFCEABCFD#EFCADFECDABCFACD#”(#為不同標點符號)，建詞索引如圖1所示。

一級索引中，termID是一個單詞或串在索引中唯一的ID，F(xiàn)req是該term在語料中的頻次，is_stop為停用詞標志，is_adj是形容詞標志，Unit_count是該term的單詞長度，也就是串中包含的單詞個數(shù)， Pos_pointer，Rv_pointer和Lv_pointer分別是對應的二級索引入口地址的偏移量。二級索引是索引項列表，其入口地址是從一級索引獲取的。二級索引中的每一個項是該term在文本集中的概要描述。其中，Pos_pointer指向的是該索引項的位置倒排；Lv_pointer指向的是該term的左鄰接列表，是該term所有的左鄰接及其出現(xiàn)頻次；Rv_pointer指向的是該term的右鄰接列表，是該term所有的右鄰接及其出現(xiàn)頻次。

通過這樣的索引結構，可以描述文本集中任何一個單詞或串盡可能多的屬性，其動態(tài)性、效率及擴展性等也能滿足海量文本處理的需求。

2.2 詞串擴展及頻繁模式發(fā)現(xiàn)

開始時，將所有單詞(ID)調入一個隊列中，然后根據(jù)每個單詞在索引中的統(tǒng)計信息判斷其向它的下文擴展的可能性，這樣就得到其二詞或三詞串，然后讓已被擴展單詞出隊，并將新產(chǎn)生的擴展串入隊，繼續(xù)判斷并從n詞串擴展得到n+1或n+2詞串，反復迭代，直到隊列為空為止。串擴展前單詞索引及擴展候選隊列初始狀態(tài)如圖2所示。

在串擴展中，需要判斷一個單詞或串能否與其下文(單詞或串)結合成為一個關聯(lián)模式的可能性。在本文中，我們用語言規(guī)則、置信度及逆置信度的評價指標[14]。其中，置信度(Confidence)是指單詞關聯(lián)wi-1→wi的上文(前件)wi-1出現(xiàn)的情況下，其下文是wi的條件概率。逆置信度(R-Confidence)是指單詞關聯(lián)wi-1→wi的下文(后件)wi出現(xiàn)的情況下，其上文是wi-1的條件概率，計算公式如下：

可見，置信度評價的是單詞關聯(lián)的上文在本關聯(lián)中的比重，而逆置信度是用來度量單詞關聯(lián)的下文對此關聯(lián)強度的共現(xiàn)。因此，當Confidence(wi-1，wi)gt;minconf或R-Confidence(wi-1，wi)gt;minconf時,則可以判定詞串wi-1wi為可信頻繁模式(trusted frequent pattern，TFP)。

在本文研究中，我們還發(fā)現(xiàn)維吾爾文以下語言特性對文本中關聯(lián)模式的識別非常有用。

特性1維吾爾文中的連詞、助詞、副詞、代詞、量詞及感嘆詞等功能詞，在文本中始終不會跟其他單詞結合成為強關聯(lián)模式。在本文研究中，我們將這類詞統(tǒng)稱為“獨立詞”(independent word,IW)。

特性2維吾爾文單詞之間的結合主要是在名詞(N)、 形容詞(ADJ)和動詞(V)之間發(fā)生，并構成語義串。其中，當形容詞與名詞或形容詞與動詞結合時，形容詞總是作為前驅，而不會出現(xiàn)在后繼位置上。因此，N+ADJ或V+ADJ的相鄰單詞絕不會結合為一個語義串。

圖1 多層動態(tài)索引示例

圖2 串擴展初始狀態(tài)示例

根據(jù)以上的語言特性，我們歸納出了用于詞間關聯(lián)性辨別的單詞結合規(guī)則(word association rule,WAR)，定義如下：

定義1(單詞結合規(guī)則： WAR)： 對于文本中的相鄰詞對“AB”，如成立條件： A ∈{IW} or B ∈{IW} or B∈{ADJ}，則A與B不能結合成為關聯(lián)模式。

根據(jù)以上規(guī)則和評價指標，假定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的左鄰接列表，然后根據(jù)條件③、④、⑤依次判斷A跟其每一個下文(左鄰接)詞構成新串的可能性。本例中，A的第一個左鄰接B具備條件③和④，同時A與B構成的擴展串AB也具備條件⑤，因此將新產(chǎn)生的串AB入隊，同時將它的信息追加到索引中，然后判斷A跟其下一個左鄰接詞C的關聯(lián)強度，依次判斷并進行從單詞到二詞擴展，直到A的所有左鄰接詞都被訪問完為止(A與C和D都不能結合)。此時，候選隊列及索引變化情況如圖3所示。

圖3 串擴展示例1

之后，讓當前隊頭單詞B出隊，因為B已跟A結合，就不再進行擴展，然后是C出隊。就這樣，依次對每一個單詞進行二詞或三詞擴展，同時將新產(chǎn)生的二詞或三詞串入隊，等待繼續(xù)被擴展。當所有單詞都被訪問完之后，候選隊列及索引變化情況如圖4所示。

圖4 串擴展示例2

等所有單詞的二詞或三詞串擴展完畢之后，就接著進入從串擴展更長串的過程，直到串擴展候選隊列為空，此時，頻繁模式發(fā)現(xiàn)過程全部結束。

2.3 模式串完整性評價及語義串抽取

一個串能成為語義串的前提是，它在結構、語義、語用及統(tǒng)計上應能滿足一定的特點。通過以上頻繁模式識別得到的結果只能滿足可統(tǒng)計性要求，被稱為語義串候選，但這還需要采用語言模型或上下文鄰接分析等方法進一步的甄別和過濾[15]。在本文研究中，我們所采取的方法與中文有所不同。主要原因是：

① 中文常用功能字會跟其他漢字構成實詞，如“的士、嘿店”等。因此，對于串首或串尾出現(xiàn)功能字的情況，還需判斷串首、串尾雙字耦合度，以及詞首和詞尾成詞概率。另外，因為所有的漢字都不能作為詞首或詞尾，因此可以通過計算單字位置成詞的概率來判斷串首和串尾， 可以有效地過濾垃圾串。但是維吾爾文與中文不同。首先，維吾爾文中的功能詞一般不會跟其他詞結合并構成新詞。另外，維吾爾文中的詞語本來就是一個獨立運用的語言單元，詞在串首或串尾位置用法上沒有特定規(guī)律(形容詞除外)。

② 在維吾爾文語義串識別及抽取中，我們當然可以采取與中文類似的方法，判斷模式串串首和串尾的“雙詞”耦合度，這樣對垃圾串過濾肯定會有一定的幫助，但這需要大量的學習語料和人工標注工作來構建雙詞耦合度詞典。然而，本文研究的目的是基于無監(jiān)督學習的語義串識別及抽取方法。

③ 關于語言模型的模式串分析方法，本算法已引入單詞結合規(guī)則，并把它嵌入到串擴展及頻繁模式發(fā)現(xiàn)過程中，因而有效避免了串尾出現(xiàn)形容詞從而產(chǎn)生垃圾串的情況，在一定程度上減輕了垃圾串過濾任務。

因此，本文主要是根據(jù)上下文鄰接特征來判斷每一個語義串候選的結構完整性。中文相關研究結果表明，采用鄰接熵的結果比其他三種鄰接特征量(鄰接種類，鄰接對種類，鄰接對熵)的結果好[16]。因此，我們用式(3)為每一個候選語義串賦權重：

式(3)中，AEweight(S)是模式串S的鄰接熵(adjacency entropy： AE)權重，RAE(S)是S的右鄰接熵，LAE(S)是S左鄰接熵。右 (左)鄰接熵計算公式為：

式(4)中，m是模式串S的左鄰接種類個數(shù)，ni是模式串S的第i個左鄰接頻次，N為全部左鄰接頻次總和。以上計算鄰接特征量所需的所有信息，在這些模式串被發(fā)現(xiàn)時早已被記錄好并存入索引中。最后，依次選取鄰接特征量達到給定閾值的頻繁模式，就獲得最終要得到的語義串集。語義串的抽取流程如圖5所示。

圖5 語義串抽取流程

3 語義串評價及語義串特征提取

3.1 語義串基本特征

① 鄰接熵特征。鄰接特征表示語義串在語用環(huán)境中的結構完整性，而結構完整的詞串總是能表達與文本主題相關的關鍵信息。因此，我們可以用鄰接特征量去評價語義串的重要度，鄰接特征量越大，表明語義串結構越完整，其表達的信息也越具體，而這樣的特征可以為學習算法提供判斷文本相似度的重要信息。鄰接特征有多種，我們選鄰接熵作為權重評價語義串的重要度。

② TFIDF特征。對于一個語義串項來說，如果它的頻次特別低或者該語義串在大部分文本中都出現(xiàn)，則這樣的語義串就沒有類別區(qū)分能力，不應選擇為文本特征。根據(jù)TFIDF評價函數(shù)的定義，在文本集中具有較高的頻次及在少一部分文本中出現(xiàn)的語義串，其類別區(qū)分能力會比較大，因此為它賦予較大的權重。

③ 長度特征。語義串的長度與其表達的信息量成正比關系，因此長度越長，語義串表達的信息量也越大，語義更具體而完整。例如，語義串“高速公路收費系統(tǒng)”的信息量比“高速”、“高速公路”和“高速公路收費”都大，如這樣的語義串在同一類文本中重復出現(xiàn)，則其區(qū)分類別能力也非常大，因此也為這樣的特征賦予更大的權重。

3.2 多特征融合的語義串評價

在以上幾種特征中，鄰接熵值的大小既能體現(xiàn)語義串頻次又能反映其語義完整性，TFIDF特征則反映語義串的類別區(qū)分能力，而長度特征是語義串表達信息量的度量。因此，根據(jù)不同特征在語義串評價中的重要度，給出了如下綜合評價公式，即

其中，Wi是語義串集中第i個語義串權重，AEweight是用式(3)計算得到的鄰接熵，Unit_count是該語義串包含的單詞個數(shù)。TFIDFweight計算公式中，TF是第i個語義串在語義串集中的頻次，IDF是該語義串逆文檔頻率。

最終，我們用式(5)依次計算每一個文本中的語義串權重，然后按權重大小排序，并選取權重最高的TopN個語義串作為特征，從而得到文本集的特征子集。

4 實驗與分析

在現(xiàn)有多種文本表示方法中，向量空間模型(vector space model，VSM)具有模型構造簡單、系統(tǒng)易于實現(xiàn)、還能通過調節(jié)對應權重的大小來反映特征項與所在文檔的相關程度、易于對向量進行修改等特點，因此被廣泛接受。除此之外，我們在前期研究工作中，曾在以詞為特征的VSM上進行維吾爾文聚類研究，主要工作是如何找到正確的類中心，從而提高K_means聚類效率[17]。而本文研究目的是，要驗證以語義串作為特征表示文本的方法能否提高聚類算法的性能。

因此，我們仍然采用VSM構建文本模型，即單詞特征VSM和語義串特征VSM，然后通過K_means聚類實驗結果對比來分析并驗證本文提出的語義串特征提取及融合評價方法的正確性和有效性。

4.1 實驗語料

本實驗使用新疆大學智能信息處理重點實驗室提供的人工分類語料，包括健康類、交通類、教育類、經(jīng)濟類、體育類和宗教類，每類均為300篇，共1 800篇文本。

4.2 評價指標

常用的評價指標包括準確率(precision)、召回率(recall)和F-measure等。

P(準確率)=聚類正確的文本數(shù)/實際聚類的文本數(shù)

R(召回率)=聚類正確的文本數(shù)/應有的文本數(shù)

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

我們對實驗數(shù)據(jù)分別進行傳統(tǒng)分詞和語義串抽取并得到兩份特征集，對通過分詞得到的單詞特征采用TFIDF評價函數(shù)進行權重計算，而對語義串特征采用本文提出的融合評價方法進行權重計算。實驗中，我們主要觀察分別用兩種特征表示文本時的特征空間維度和算法性能的變化情況。

4.3 兩種特征集的特征空間維度

本試驗中，我們按一定比例為每一個文本選取權重最高的若干個特征來獲取文本集的特征子集，不同規(guī)模特征子集包含的特征個數(shù)如表1所示。

表1 不同規(guī)模特征子集及特征個數(shù)

續(xù)表

4.4 兩種文本特征集的聚類效率

從表1可以看出，語義串特征的提取明顯降低了特征空間維度，這也應該體現(xiàn)在聚類算法效率的提高上。因此，我們以表1中不同規(guī)模特征子集表示文本，對比以單詞特征和語義串特征表示文本時的K_means聚類效率，結果如圖6所示。

圖6 兩種特征集的K_means聚類效果

4.5 多特征融合的語義串評價方法的有效性

本文中，我們從結構完整性(AE)，蘊含的信息量(Unit_count)，以及類別區(qū)分能力(TFIDF)等方面對語義串進行評價，并從按評價得分從高到低的排序序列中選取TopN個語義串來獲得文本特征子集。因此，為了觀察不同特征對于語義串評價及聚類效率的影響，我們采用不同特征的組合在實驗數(shù)據(jù)集上分別做實驗，得到如表2所示結果。

表2 單特征和多特征融合評價情況下的聚類效率

表2列出了不同策略單獨使用和使用組合策略情況下的實驗結果?？梢钥闯?，使用組合特征策略總比使用單特征策略好。

圖7展示了三種策略單獨使用和兩兩組合時的聚類結果對比。從F-measure值來看，單獨使用AE評價語義串時的聚類效率最好，這表明選取AE值越高的語義串作為文本特征，能夠選取結構及語義更完整的語義串特征，同時能夠有效防御垃圾串的選入。對于組合策略來說，AE和TFIDF融合評價時的聚類效率較好，AE和Unit_count的組合也能選取重要的文本特征。

我們還采用逐步增加策略的方式做實驗，觀察了聚類效率評價指標變化情況，實驗結果如圖8所示。

圖7 不同評價策略及聚類結果

圖8 逐步增加策略時的實驗結果

可以看出，每增加一個語義串重要度評價策略，各個聚類評價指標也相應地逐步上升，說明每一種策略都在起作用。在三種策略融合的評價方法中，因為同時從語義串的結構完整性、蘊含的信息量以及類別區(qū)分能力等方面進行綜合評價，因此為每一個文本選取的語義串特征就能更好地表示文本主題，這是聚類算法得到較高聚類效率的前提。

5 結語

用傳統(tǒng)分詞方法獲取的維吾爾文文本特征集，因為存在大量的語義抽象和多義的單詞特征，不能很好地表征文本，因此無法得到較好的聚類效果。本文用統(tǒng)計和淺層語言分析的方法，從文本中抽取結構完整的、表達關鍵信息的語義串進行綜合評價,并用語義串來表示文本，最后以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] 徐燕,李錦濤,王斌,等.基于區(qū)分類別能力的高性能特征選擇方法[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] 張華平,高凱 ,黃河燕,等.大數(shù)據(jù)搜索與挖掘[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)