吐?tīng)柕亍ね泻咸幔?維尼拉·木沙江，艾斯卡爾·艾木都拉

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

基于語(yǔ)義串特征提取及融合評(píng)價(jià)的維吾爾文文本聚類

吐?tīng)柕亍ね泻咸幔?維尼拉·木沙江，艾斯卡爾·艾木都拉

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

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

維吾爾文；語(yǔ)義串抽??；特征評(píng)價(jià)及選?。幌蛄靠臻g模型；K_means

1 引言

在文本聚類中，先對(duì)文本集進(jìn)行切分和特征提取，然后評(píng)價(jià)特征集中每一個(gè)特征的重要度并選取一個(gè)特征子集來(lái)表示文本集，最后用這個(gè)特征子集去計(jì)算并對(duì)文本集進(jìn)行歸類。因此，提取什么樣的特征，如何評(píng)價(jià)和選取一個(gè)最佳特征子集是文本聚類的主要研究課題[1]。

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

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

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

2 語(yǔ)義串識(shí)別及抽取

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

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

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

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

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

2.2 詞串?dāng)U展及頻繁模式發(fā)現(xiàn)

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

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

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

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

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

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

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

圖2 串?dāng)U展初始狀態(tài)示例

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

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

根據(jù)以上規(guī)則和評(píng)價(jià)指標(biāo)，假定A、B是文本中相鄰的兩個(gè)單詞(或串)，A是B的上文(右鄰接詞)，B是A的下文(左鄰接詞)，如要進(jìn)行“A→AB”的擴(kuò)展，則“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；

以上例子中，當(dāng)隊(duì)頭單詞A出隊(duì)后，因?yàn)锳具備條件①和②，因此從二級(jí)索引中讀取A的左鄰接列表，然后根據(jù)條件③、④、⑤依次判斷A跟其每一個(gè)下文(左鄰接)詞構(gòu)成新串的可能性。本例中，A的第一個(gè)左鄰接B具備條件③和④，同時(shí)A與B構(gòu)成的擴(kuò)展串AB也具備條件⑤，因此將新產(chǎn)生的串AB入隊(duì)，同時(shí)將它的信息追加到索引中，然后判斷A跟其下一個(gè)左鄰接詞C的關(guān)聯(lián)強(qiáng)度，依次判斷并進(jìn)行從單詞到二詞擴(kuò)展，直到A的所有左鄰接詞都被訪問(wèn)完為止(A與C和D都不能結(jié)合)。此時(shí)，候選隊(duì)列及索引變化情況如圖3所示。

圖3 串?dāng)U展示例1

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

圖4 串?dāng)U展示例2

等所有單詞的二詞或三詞串?dāng)U展完畢之后，就接著進(jìn)入從串?dāng)U展更長(zhǎng)串的過(guò)程，直到串?dāng)U展候選隊(duì)列為空，此時(shí)，頻繁模式發(fā)現(xiàn)過(guò)程全部結(jié)束。

2.3 模式串完整性評(píng)價(jià)及語(yǔ)義串抽取

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

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

② 在維吾爾文語(yǔ)義串識(shí)別及抽取中，我們當(dāng)然可以采取與中文類似的方法，判斷模式串串首和串尾的“雙詞”耦合度，這樣對(duì)垃圾串過(guò)濾肯定會(huì)有一定的幫助，但這需要大量的學(xué)習(xí)語(yǔ)料和人工標(biāo)注工作來(lái)構(gòu)建雙詞耦合度詞典。然而，本文研究的目的是基于無(wú)監(jiān)督學(xué)習(xí)的語(yǔ)義串識(shí)別及抽取方法。

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

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

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

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

圖5 語(yǔ)義串抽取流程

3 語(yǔ)義串評(píng)價(jià)及語(yǔ)義串特征提取

3.1 語(yǔ)義串基本特征

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

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

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

3.2 多特征融合的語(yǔ)義串評(píng)價(jià)

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

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

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

4 實(shí)驗(yàn)與分析

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

因此，我們?nèi)匀徊捎肰SM構(gòu)建文本模型，即單詞特征VSM和語(yǔ)義串特征VSM，然后通過(guò)K_means聚類實(shí)驗(yàn)結(jié)果對(duì)比來(lái)分析并驗(yàn)證本文提出的語(yǔ)義串特征提取及融合評(píng)價(jià)方法的正確性和有效性。

4.1 實(shí)驗(yàn)語(yǔ)料

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

4.2 評(píng)價(jià)指標(biāo)

常用的評(píng)價(jià)指標(biāo)包括準(zhǔn)確率(precision)、召回率(recall)和F-measure等。

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

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

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

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

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

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

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

續(xù)表

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

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

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

4.5 多特征融合的語(yǔ)義串評(píng)價(jià)方法的有效性

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

表2 單特征和多特征融合評(píng)價(jià)情況下的聚類效率

表2列出了不同策略單獨(dú)使用和使用組合策略情況下的實(shí)驗(yàn)結(jié)果?？梢钥闯觯褂媒M合特征策略總比使用單特征策略好。

圖7展示了三種策略單獨(dú)使用和兩兩組合時(shí)的聚類結(jié)果對(duì)比。從F-measure值來(lái)看，單獨(dú)使用AE評(píng)價(jià)語(yǔ)義串時(shí)的聚類效率最好，這表明選取AE值越高的語(yǔ)義串作為文本特征，能夠選取結(jié)構(gòu)及語(yǔ)義更完整的語(yǔ)義串特征，同時(shí)能夠有效防御垃圾串的選入。對(duì)于組合策略來(lái)說(shuō)，AE和TFIDF融合評(píng)價(jià)時(shí)的聚類效率較好，AE和Unit_count的組合也能選取重要的文本特征。

我們還采用逐步增加策略的方式做實(shí)驗(yàn)，觀察了聚類效率評(píng)價(jià)指標(biāo)變化情況，實(shí)驗(yàn)結(jié)果如圖8所示。

圖7 不同評(píng)價(jià)策略及聚類結(jié)果

圖8 逐步增加策略時(shí)的實(shí)驗(yàn)結(jié)果

可以看出，每增加一個(gè)語(yǔ)義串重要度評(píng)價(jià)策略，各個(gè)聚類評(píng)價(jià)指標(biāo)也相應(yīng)地逐步上升，說(shuō)明每一種策略都在起作用。在三種策略融合的評(píng)價(jià)方法中，因?yàn)橥瑫r(shí)從語(yǔ)義串的結(jié)構(gòu)完整性、蘊(yùn)含的信息量以及類別區(qū)分能力等方面進(jìn)行綜合評(píng)價(jià)，因此為每一個(gè)文本選取的語(yǔ)義串特征就能更好地表示文本主題，這是聚類算法得到較高聚類效率的前提。

5 結(jié)語(yǔ)

用傳統(tǒng)分詞方法獲取的維吾爾文文本特征集，因?yàn)榇嬖诖罅康恼Z(yǔ)義抽象和多義的單詞特征，不能很好地表征文本，因此無(wú)法得到較好的聚類效果。本文用統(tǒng)計(jì)和淺層語(yǔ)言分析的方法，從文本中抽取結(jié)構(gòu)完整的、表達(dá)關(guān)鍵信息的語(yǔ)義串進(jìn)行綜合評(píng)價(jià),并用語(yǔ)義串來(lái)表示文本，最后以K_means算法分別做了多個(gè)聚類實(shí)驗(yàn)，觀察了以單詞特征和語(yǔ)義串特征表示文本時(shí)的特征空間維度和算法性能的變化情況。實(shí)驗(yàn)結(jié)果表明，用語(yǔ)義串特征表示文本是特征空間降維的有效方法，用多特征融合的評(píng)價(jià)方法可以有效地獲取最重要的語(yǔ)義串特征，因此聚類效率也得到了明顯的提高。

[1] 劉遠(yuǎn)超,王曉龍,徐志明,等. 文檔聚類綜述[J].中文信息學(xué)報(bào),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]. 軟件學(xué)報(bào), 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].北京:科學(xué)出版社,2014.

[17] 吐?tīng)柕亍ね泻咸?艾海麥提江·阿布來(lái)提,米也塞·艾尼玩,等.一種結(jié)合GAAC和K-means的維吾爾文文本聚類算法[J].計(jì)算機(jī)工程與科學(xué),2013,35(7):149-155.

吐?tīng)柕亍ね泻咸?1975—)，副教授，博士，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理及文本挖掘。

E-mail：turdy@xju.edu.cn

維尼拉·木沙江(1960—)，教授，碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理及信息檢索。

E-mail：winira@xju.edu.cn

艾斯卡爾·艾木都拉(1972—)，教授，博士，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄苄畔⑻幚怼?/p>

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

國(guó)家自然科學(xué)基金(61562083,61262062,61262063)