改進的維吾爾語Web文本后綴樹聚類

鄒志華，田生偉，禹 龍，馮冠軍

（1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊830046；2.新疆大學(xué) 軟件學(xué)院，新疆 烏魯木齊830008；3.新疆大學(xué) 網(wǎng)絡(luò)中心，新疆 烏魯木齊830046；4.新疆大學(xué) 人文學(xué)院，新疆 烏魯木齊830046）

1 引言

聚類作為一種自動化程度較高的無監(jiān)督機器學(xué)習(xí)方法，近年來在信息檢索、多文檔自動文摘等領(lǐng)域得到了廣泛的應(yīng)用。文本聚類基于以下假設(shè)：同類的文本相似度較大，不同類的文本相似度較小。

Za mir提出了后綴樹聚類（Suffix Tree Cl ustering，STC）算法，通過識別不同文檔之間的共享短語對文本聚類，其時間復(fù)雜度為O（Nl og N）。STC算法基于文檔集的后綴樹模型（Suffix Tree Model，ST M），其考慮到了詞之間的鄰近順序關(guān)系，產(chǎn)生了比較好的聚類效果。相比向量空間模型，STC算法有很多優(yōu)點：（1）廣義后綴樹將文本表示成一定的詞組的集合，能保持原文本的語義結(jié)構(gòu)并提高比較的準確度和效率。（2）基于廣義后綴樹的文本聚類算法可以較容易的提取聚類結(jié)果的類別標識。（3）STC是一種軟聚類算法，允許一個文檔屬于幾個不同的類別。但STC算法存在一定不足：（1）不能有效處理文本數(shù)目差距很大但具有包含關(guān)系的節(jié)點。（2）文本相似但其主題不同的聚類節(jié)點可能被合并到同一個聚類中。（3）缺乏有效的類別標識選擇算法。

本文主要探討了改進的后綴聚類算法在維吾爾語Web文本聚類中的應(yīng)用。第1節(jié)為引言，分析了傳統(tǒng)的后綴樹聚類的優(yōu)勢與不足；第2節(jié)介紹了后綴樹聚類及其改進算法的相關(guān)研究；第3節(jié)著重介紹了改進的維吾爾語Web文本后綴樹聚類STCU算法；第4節(jié)給出了評價標準并對實驗結(jié)果進行了分析；最后，對研究工作做出總結(jié)和展望。

2 相關(guān)工作

Weiner［1]首次提出了線性時間的后綴樹建樹算法。Mc Creight［2]在此基礎(chǔ)上提出了更為節(jié)約空間的算法。Ukkonen［3－4]提出了改進的線性時間建樹算法，它易于理解且具有在線特性。Gusfield［5]對Ukkonen的后綴樹算法進行了詳細的闡述。在實際應(yīng)用中，Ukkonen提出的算法得到了廣泛應(yīng)用。

現(xiàn)階段，對于文本聚類和后綴樹聚類的相關(guān)工作已經(jīng)有了廣泛而深入的研究。文獻［6]對文本聚類進行了綜述。對于 Web文本，文獻［7]提出了通過二次特征提取和聚類的方法，將Web文本按照主題進行自動聚類。文獻［8]提出了一種新的基于主題的文本聚類方法：LFIC，能準確識別文本主題并根據(jù)文本的主題對其進行聚類。文獻［9]應(yīng)用LDA模型進行文檔的潛在語義分析，將語義分布劃分成低頻、中頻、高頻語義區(qū)，采用文檔類別與語義互作用機制對聚類結(jié)果進行修正。Zamir［10－12]首次提出了STC算法，利用短語來發(fā)現(xiàn)文檔，通過抽取片段中的短語作為標簽，提高了算法的性能，比AHC，K－means等傳統(tǒng)算法要好。文獻［13]在聚類過程利用語義相似度，改善了STC方法，采取了有效的啟發(fā)式方法進行結(jié)果聚類，通過語義相似度，減少了后綴節(jié)點和分支。文獻［14]比較了兩種文本后綴樹模型抽取短語的方式，討論了表示模型和相似度計算方法，并研究了計算算法。文獻［15]提出新的后綴樹聚類方法NSTC，采用了新的相似度計算方法對后綴樹相似度測量。文獻［16]提出了語義后綴樹聚類SSTC并構(gòu)建了語義后綴樹，利用Wor d Net數(shù)據(jù)庫進行語義相似度和字符串匹配，通過剪枝減少子樹規(guī)模來分離語義類。文獻［17]利用后綴數(shù)組發(fā)現(xiàn)核心短語，采用了矩陣奇異值分解提高聚類精度。文獻［18]改進了短語打分公式，將STC應(yīng)用到層次聚類。文獻［19]在聚類之前就產(chǎn)生好的標簽，在生成了標簽的基礎(chǔ)上，再進行檢索結(jié)果聚類。文獻［20]利用后綴樹文檔模型的后綴樹的快速匹配，實時獲得文本的向量表示，不需要對文本進行分詞、特征抽取等復(fù)雜計算。文獻［21]提出了使用后綴樹聚類算法優(yōu)化K－means文檔聚類初始值的快速混合聚類方法STK－means。文獻［22]針對 Web文檔的結(jié)構(gòu)及其特征，提出了一種新的加權(quán)后綴樹聚類方法WSTC。文獻［23]使用改進的后綴樹算法用于中文網(wǎng)頁聚類，結(jié)合了中文的語言特性，采取了新的單元選擇原則和新穎的后綴樹構(gòu)造策略。文獻［24]通過去除同義詞、近義詞、相同句子的方法對文本進行降維處理，并查詢關(guān)鍵字與文本的相似度，對文本打分來降低STC的時間復(fù)雜度以提高STC聚類準確率。文獻［25]提出了適合中文 Web信息搜索結(jié)果的后綴樹聚類算法，采用有效的策略解決了類別描述問題，利用短語類語義層面的相似性合并同義短語類，有效地改善了聚類結(jié)果的質(zhì)量。文獻［26]結(jié)合STC算法和變色龍算法提出了STCC算法，采用雅可比系數(shù)修改了STC算法中基本類相似度的計算方法，出色地完成了網(wǎng)頁聚類。

針對維吾爾語語言和Web文本特點，本文提出了一種改進的維吾爾語Web文本聚類的后綴樹聚類算法（STCU）。文中對詞語進行詞干提取，構(gòu)建了兩種維吾爾語停用詞表，并采用文檔頻率和詞性結(jié)合的方法對關(guān)鍵短語提取。合并基類時采用了改進的二進制方法，能根據(jù)語料類別數(shù)對聚類類別閾值自動調(diào)整。最后，利用最一般短語對聚類結(jié)果進行描述，提高了文本聚類的質(zhì)量。

3 改進的維吾爾語后綴樹聚類

3.1 維吾爾語的特點

維吾爾語屬于阿爾泰語系突厥語族［27]，是一種黏著語，它的語法形式都是通過在單詞原形的后面或前面附加一定的附加成分來完成的。在維吾爾語文本中，一個詞語具有多種語法形式。在文本預(yù)處理時，需要對維吾爾語詞語進行詞干提取。另外構(gòu)形附加成分表示一定詞匯意義或語法意義，它們不僅與詞干互相黏連，并且彼此之間也互相黏連。在維吾爾語詞切分中，除了詞干提取之外還要對構(gòu)形附加成分加以切分。

3.2 改進的維吾爾語文本聚類流程

改進的維吾爾語后綴樹聚類具體流程為：

（1）維吾爾語Web文本預(yù)處理，對詞語進行詞干提取，過濾絕對停用詞和相對停用詞；

（2）構(gòu)造Web文本廣義后綴樹，其中后綴樹以維吾爾語句子為單位進行構(gòu)造；

（3）遍歷維吾爾語文本廣義后綴樹，得到文本集的公共短語；

（4）對公共短語，利用文檔頻率和詞性結(jié)合的方法提取關(guān)鍵短語；

（5）利用關(guān)鍵短語作為基類，然后利用改進相似度公式對基類進行合并；

圖1 維吾爾語后綴樹聚類流程

（6）利用最一般短語作為聚類標簽并將聚類結(jié)果可視化顯示。

3.2.1 算法描述

改進的維吾爾語后綴樹聚類算法STCU（Improved Suffix Tree Cl ustering f or Uyghur）描述如下：

輸入：文本集合D＝｛d1，d2，…，dn｝；

輸出：帶有類別短語標簽的簇集合C＝｛c1，c2，…，cn｝；

Step1 對文本集合D中文本di進行清洗、過濾、解析，得到對應(yīng)文本集合的字符串集合S＝｛s1，s2，…，sn｝；

Step2 使用線性時間復(fù)雜度算法對s1構(gòu)造后綴樹N1，在N1基礎(chǔ)上，依次增量構(gòu)造后綴樹N2，N3，…，Nn，得到廣義后綴樹T；

Step3 遍歷廣義后綴樹T，找到內(nèi)部節(jié)點集合V＝｛v1，v2，…，vt｝中的每個節(jié)點vi所對應(yīng)的最大短語基類，得到基類集合B＝｛b1，b2，…bt｝，vip代表基類bi的短語標簽；

Step4 公共短語分別構(gòu)建多短語表P1和單短語表P2，公共短語中兩個及以上單詞的短語具有豐富的語義信息，不予處理；單個單詞需要進行詞性標注，去除連詞、語氣詞、動詞；

Step5 對短語進行文檔頻率提取，并調(diào)節(jié)閾值ST1，得到有效短語；

Step6 計算每個基類bi的得分，由高到低排序，過濾得分過低的噪聲簇，得到新的基類集合M＝｛m1，m2，…，mc｝；

Step7 聚類閾值ST2自動調(diào)整，使得合并的短語類簇數(shù)目不至過大，滿足實際聚類要求；

Step8 定義短語類簇mi和mj相似度si m（mi，mj），合并基類短語構(gòu)造短語簇圖，遍歷圖找出最大連通分量對應(yīng)的新的簇集合E＝｛E1，E2，…，El｝，并計算合并后短語簇的得分，從而得到類簇短語標簽；

Step9 依據(jù)短語簇的得分和包含文本數(shù)目兩個指標，由高到低排序，并根據(jù)指定的簇數(shù)目閾值k決定最終聚類集合C＝｛c1，c2，…，ck｝；

Step10 使用最一般短語GP＝（gp1，gp2，…，gpn）作為標簽對聚類結(jié)果進行描述，并可視化顯示。

3.3 文本分析及預(yù)處理

文本分析是STC算法的基礎(chǔ)，主要工作是對文本進行規(guī)范化處理。識別文本中的詞語，對維語文本進行詞干提取，去除停用詞，識別數(shù)字、標點符號（維吾爾語的標點符號主要有：“－”，“.”，“《”，“》”，“‘”，“：”，“！”，“”，“；”等符號）、網(wǎng)頁中的 HT ML標簽等。

在文本預(yù)處理階段，將文本句子轉(zhuǎn)化為詞的序列。對于一些非維吾爾語的元素，如標點符號和HT ML標簽等會干擾后綴樹的構(gòu)建，采取正則表達式把這些元素從文本中過濾掉。

3.3.1 構(gòu)建絕對停用詞表和相對停用詞表

維吾爾語文本中存在停用詞現(xiàn)象，即出現(xiàn)頻率很高和出現(xiàn)頻率很低但對主題描述意義不大的詞。如：助詞、代詞等，它們的存在會嚴重影響聚類結(jié)果的質(zhì)量。相同的兩個短語如果使用了不同的停用詞，它們會被識別為不同的短語類，最終導(dǎo)致聚類結(jié)果中出現(xiàn)主題相同但分屬不同類別的現(xiàn)象。停用詞在文本聚類過程中將增加后綴樹構(gòu)建的復(fù)雜度，去除后不僅能減少構(gòu)建后綴樹的代價，加快后綴樹遍歷效率，而且能提高聚類效果。

為了消除停用詞對聚類結(jié)果的影響，本文定義并維護了一個維吾爾語絕對停用詞表和相對停用詞表，使在后綴樹構(gòu)建過程中出現(xiàn)在停用詞表中的詞語全部被剔除，用以改善聚類結(jié)果的質(zhì)量。

絕對停用詞表：通用的停用詞表，包括連詞、虛詞、嘆詞等無實際意義的詞語，在文本預(yù)處理階段必須去掉。在維吾爾語中，語氣詞（?。?、（哎呀）、（唉喲）；連詞（只是）、（竟然）為停用詞。

相對停用詞表：對于Web文本語料庫，其中有很多未登錄詞，此時需要對語料庫進行統(tǒng)計分析，去掉一些特定的高頻詞。如：（我臺報道），（圖片新聞），（評論員）、（編輯）等詞；

3.4 后綴樹模型

定義1 字符串S是由一串詞語組成的文本。定義2 字符串S的長度是指其包含的詞語的個數(shù)。

定義3 字符串S的后綴是指從某一個詞開始到最后一個詞語所構(gòu)成的字符串。長度為m的字符串S［1…m]共有m個后綴S［i…m]，其中，i＝1，2，…，m。每個后綴都由一個或多個詞語組成。

定義4 字符串S的后綴樹就是一棵由S的全部后綴所構(gòu)成的壓縮檢索樹（Co mpact Trie）。具備以下特性：

（1）后綴樹是一棵有根的有向樹；

（2）對于每一個不是根節(jié)點的中間節(jié)點至少包含兩個子節(jié)點；

（3）每一條邊標記為S的一個非空子串；

（4）從一個節(jié)點發(fā)出的兩條邊不能包含相同詞開始的子串；

（5）每一個節(jié)點的標簽定義為由根到這個節(jié)點的路徑上的邊的標簽的串聯(lián)；

（6）對于任何一個葉子i，從根到該葉子的整個路徑上的邊標簽串聯(lián)起來的內(nèi)容就是S從位置i起的后綴子串，即S［i…m]。

一個由m個詞的字符串S的后綴樹T，有m個葉子，這些葉子編號從1到m。

圖2 字符串“mississippi＄”的后綴樹

一般后綴樹只能表達一個文本的后綴字符串，而文本集包含大量字符串，為了利用后綴樹進行聚類，需要將待處理的多個文本或者文本建立在同一棵后綴樹上，形成多個文本的廣義后綴樹（Generalized Suffix Tree，GST）。

定義5 一個廣義后綴樹就是由若干字符串組成的后綴樹，即：設(shè)字符串集合有n個字符串S1，S2，…，Si，…，Sn，字符串Si的長度為mi，由這些字符串構(gòu)成的廣義后綴樹T，是一個有根的有向樹，該樹有∑mi個葉子。

圖3是三個維吾爾語文本的廣義后綴樹，為方便構(gòu)造廣義后綴樹，在每個字符的末尾增加一個特殊的終止符“＄”。

圖3中，每一個中間節(jié)點附著一個方框。在廣義后綴樹中有一類特殊節(jié)點，其入邊的標簽只包含特殊終止符“＄”，用灰色圓圈表示，稱為終端節(jié)點。

文本集包含三個文本字符串，第一個字符串有3個后綴，第二個字符串有4個后綴，第三個字符串有4個后綴，圖中共畫出了8個葉子節(jié)點。

圖3 維吾爾語廣義后綴樹實例

廣義后綴樹的一個重要的特點是可以發(fā)現(xiàn)多個字符串的公共子串。這也是能夠使用后綴樹進行聚類的一個主要特性。

字符串S的后綴樹的構(gòu)造，一般是先將S［1，…，m]作為一個單邊加入樹中，然后依次將各個后綴S［i，…，m]，i＝2，3，…，m；加入樹中。采用一般后綴樹算法構(gòu)造一個長度為m的字符串S的后綴樹的時間復(fù)雜度為O（m2）。很多文獻對后綴樹的構(gòu)造算法進行了改進，其中最著名的是Ukkonen提出的線性的后綴樹構(gòu)造方法。本文使用與Za mir相同的方法構(gòu)造后綴樹。

3.5 文本聚類特征提取

在文本聚類中最為常用的幾種無監(jiān)督特征選擇方法有文檔頻率、單詞權(quán)、單詞熵和單詞貢獻度［28]。本文采用文檔頻率和詞性結(jié)合的方法對特征進行提取。

3.5.1 文檔頻率

文檔頻率是最易理解的一種無監(jiān)督特征選擇方法。詞的文檔頻率是在整個文本集中出現(xiàn)該詞的文本數(shù)。文檔頻率的理論前提是：詞在某個類中出現(xiàn)次數(shù)過多或過少對問題是無貢獻的，刪除這些單詞會提高聚類結(jié)果，尤其是稀少單詞恰好是噪聲單詞的情況。文檔頻率的優(yōu)點在于它的速度十分快，其時間復(fù)雜度O（n）與文本數(shù)成線性關(guān)系，適合于海量文本數(shù)據(jù)集的特征提取。

3.5.2 詞性標注

在現(xiàn)存的大部分語言中都有詞兼類問題，維吾爾語詞中也存在兼類詞的問題，并且兼類詞在具體的文本中運用更加復(fù)雜，在文本預(yù)處理的過程中需要考慮如何在具體的語境中確定兼類詞的詞性。

本文中所采用的詞性標注詞類是維吾爾語中最基本的12種詞類。所使的詞性標記集由13個標記符號組成，即T＝｛A，D，N，M，V，P，O，C，O，E，H，W ｝。其中，包括形容詞（A），副詞（D），名詞（N），數(shù)詞（M），動詞（V），代詞（P），量詞（O），連詞（C），擬聲詞（O），嘆詞（E），后置詞（H），語氣同（Y）以及標點符號（W）。該標注集是《新疆大學(xué)詞性標注集》的一個子集。

3.6 基本類簇識別

STC算法中，基本類簇的識別就是找出短語類簇。在構(gòu)造廣義后綴樹后，通過識別包含多個文本的中間節(jié)點得到。

定義6 短語是指由一個或多個詞組成的一個有序序列。短語的長度不確定，但是不能跨越短語的邊界。

定義7 短語邊界是文本解析器識別特殊語法符號時插入到短語間的標記，如標點符號，或者HT ML標簽等。文本的開頭和結(jié)尾也被認為是短語邊界。

定義8 短語類簇是一個至少被兩個文本共享的短語，以及包含該短語的一組文本。

定義9 最大短語類簇是在不改變文本樹的情況下，不能再增加短語的詞語。

短語類簇的識別可以看成是建立文本集的短語倒排表（Phrase Inverted Table）。廣義后綴樹的每一個至少包含兩個短語的節(jié)點都可以看作一個短語類簇，對于一個短語類簇，根據(jù)它包含的文本的數(shù)量及組成短語的詞語數(shù)量賦予一定的權(quán)值，根據(jù)權(quán)值大小選擇短語類簇作為基本類簇。

任一短語類簇B的權(quán)值函數(shù)s（B）定義為：

其中，｜B｜為短語類簇的文本數(shù)，｜P｜為短語P的詞數(shù)，即短語的有效長度。函數(shù)f是一個短語長度調(diào)節(jié)函數(shù)，對于單個詞語取得最小定值，對于長度介于2～5之間的短語是線性的，對于更長的短語設(shè)為一個常數(shù)。

一般設(shè)置一個閾值ST，權(quán)值大于ST的短語類簇作為基本類簇，或者對短語類簇按照權(quán)值進行逆排序，選擇前面的短語類簇作為基本類簇。

3.7 聚類閾值選擇

聚類閾值r是關(guān)于聚類范圍的描述，r越大，得到類簇個數(shù)越多。閾值選擇策略如下：

（1）統(tǒng)計出文本的類別數(shù)目N；

（2）計算基類的數(shù)目N0；

（3）聚類閾值ε取值為ε×N，其中ε≥1。

當(dāng)ε達到一定的數(shù)值，基類聚類數(shù)目變得穩(wěn)定，從而聚類性能也變得穩(wěn)定，聚類閾值選擇問題得到了解決。同時，聚類閾值的大小受文本集影響。不同文本類別數(shù)目會隨著差異產(chǎn)生不同的聚類個數(shù)，這就解決了聚類中的聚類個數(shù)固定不變的問題。實驗結(jié)果表明，ε在［1，5]范圍內(nèi)取值效果比較理想。在本文方法測試中，取ε1＝3，ε2＝2。ε1表示STC的閾值，ε2表示STCU的閾值。

3.8 合并基本類簇

獲得基本類簇后，兩個文本之間共有的短語可能存在多個，不同短語類簇的文本集存在重疊，需要合并短語類簇形成最終的聚類簇。根據(jù)基本類簇之間文本集的重疊程度定義一個二值相似性度量。給定任意兩個基類簇Bm和Bn，各自包含的文本個數(shù)為｜Bm｜和｜Bn｜，｜Bm∩Bn｜表示兩個基類簇的共有文本，Si mT為基本類簇合并閾值。當(dāng)滿足下面公式時，兩個基類的相似度為1，否則為0。

3.9 改進的相似度公式

如果一個基類是另一個基類的子集，“與”布爾操作符在下面情況不適用。

本文采用文獻［19]提出的方法，把公式的“與”操作符改為“或”操作符：

本文采用變化的閾值參數(shù)為0.5，0.6，0.7。

然后，構(gòu)造基本類簇圖（Base Cl uster Graph）。為每個基類簇在圖中畫一個頂點，如果兩個基類簇的相似度為1，則把這兩個頂點用邊連接起來表示基類簇之間的關(guān)聯(lián)。依據(jù)基類簇關(guān)聯(lián)圖的連通性，確定哪幾個基類簇合并為一個類簇。基類簇中的文本劃分為一個類簇，從而形成最終聚類得出對文本的聚類結(jié)果。

實驗發(fā)現(xiàn)，調(diào)整基本類簇合并閾值Si mT可以改變最終的類簇數(shù)量。Si mT增大，類簇數(shù)量增加；Si mT減少，類簇數(shù)量減少。

3.10 聚類標簽的識別

STC算法得到的短語具有相當(dāng)高的相似性，從而顯得冗余。冗余短語會降低聚類描述的簡潔性和清晰性，也不利于利用其他富含信息量的短語，應(yīng)該淘汰掉或盡量少選這些冗余短語來描述聚類。如果一個聚類只有一個短語，則可以用這個短語來描述聚類。如果一個聚類對應(yīng)了多個短語，則使用Oren Za mir在文獻［12]提出的以下三個啟發(fā)式規(guī)則來識別冗余短語。

（1）子字符串和超級字符串

定義10 若短語1是短語2的子字符串，則短語1為短語2的子短語，短語2為短語1的超級短語。

從覆蓋率角度來看，子短語的覆蓋率一般不小于其相應(yīng)的超級短語覆蓋率。超級短語比其相應(yīng)的子短語更具有描述信息的細節(jié)性，從而超級短語更具有信息量。最后描述聚類時只需從最一般短語和最具體短語中選擇即可。對于每個短語，都要驗證它是否是這個聚類中的其他短語的子短語和超級短語。

最一般的短語：如果某個短語沒有子短語，則表明該短語是一個最一般的短語。

最具體的短語：如果某個短語沒有超級短語存在，則表明該短語是一個最具體的短語。

顯然，最一般短語的長度應(yīng)該小于等于其相應(yīng)的最具體短語。對于只有一個短語的聚類，則該短語既是最一般短語也是最具體短語，描述聚類時，選擇這個短語即可。對于那些既不屬于最一般短語也不屬于最具體短語，在描述聚類時就不顯示這些短語。

（2）較低覆蓋率的最一般短語

選擇短而一般的短語作為聚類描述的目的是為了達到較高的覆蓋率。最一般短語一般比其相應(yīng)的具體短語覆蓋率高。如果一個最一般短語與其相應(yīng)的最具體短語相比幾乎沒有增加多少覆蓋率的話，可認為該最一般短語具有較低覆蓋率而不顯示這個最一般短語。定義一個最小覆蓋率增加值，只有不低于這個增加值的最一般短語才顯示。

（3）詞重疊度

對于最一般短語或者最具體短語的兩個短語，如果一個短語中屬于有效短語的詞在另一個具有較高覆蓋率的短語重復(fù)出現(xiàn)的頻率超過60%，這個短語將不顯示。

依據(jù)上面三個啟發(fā)式規(guī)則，每個聚類都確保選擇了至少一個短語作為描述。在一個聚類中如果選擇了多個短語，則在最后描述時，再將這些短語按照覆蓋率降序排序即可作為聚類了。

STCU算法中利用啟發(fā)式規(guī)則，得到的聚類標簽如表1所示：

表1 改進后綴樹聚類類別標簽

表1列舉了用改進的后綴樹聚類算法得出的10個類別與標簽，標簽短語有長有短，能夠代表相應(yīng)的類別。

4 實驗結(jié)果與分析

4.1 評價標準

維吾爾語沒有英語reuters21578和漢語《人民日報》語料庫等已建好的標準類別語料庫，本文使用的測試語料是從維吾爾語網(wǎng)站收集的經(jīng)人工分類并標注的新聞文本集合。其中新聞話題任意兩篇文本稱為一個人工關(guān)聯(lián)文本對，并定義如下一些數(shù)據(jù)［29]：Pt：文本集中所有可能的關(guān)聯(lián)對數(shù)目，Pt＝人工分類中所有可能的文本對的數(shù)目。Ta：聚類結(jié)果中所有可能的文本對的數(shù)目。Ei：錯誤關(guān)聯(lián)，指在聚類結(jié)果中出現(xiàn)，而在人工分類中沒有出現(xiàn)的文本對的數(shù)目。Em：遺漏關(guān)聯(lián)，指在人工分類中出現(xiàn)，而在聚類結(jié)果中沒有出現(xiàn)的文本對的數(shù)目。Ce：聚類錯誤率，Ce＝（Ei＋Em）／Pt。Cr：聚類全面率，Cr＝（Ta—Ei）／Tm。Cp：聚類準確率，Cp＝（Ta—Ei）／Ta。

4.2 實驗結(jié)果及分析

新聞文本集包含第26屆世界大運會、首屆亞歐博覽會、“7.23”動車追尾事故等20個新聞話題，每個話題包含20～60個相關(guān)話題文本，共689個話題文本，每個文本詞數(shù)40～600，平均詞數(shù)82。在搜集話題集的基礎(chǔ)上，設(shè)計了三組實驗語料：第一組實驗語料，從20個話題中任選10個，每個話題中任選10個相關(guān)話題文本，總共100個話題文本，作為DB1；第二組實驗語料，選取這20個話題，每個話題中任選20個相關(guān)話題文本，總共400個話題文本，作為DB2；第三組實驗語料，選取這20個話題，每個話題中的相關(guān)話題文本全部選取，總共689個話題文本，作為DB3。

（1）不同的數(shù)據(jù)集算法性能比較

為測試算法對語料的穩(wěn)定性和適用性，本文對三個數(shù)據(jù)集分別進行了聚類算法性能測試，結(jié)果如表2所示。

表2 不同的數(shù)據(jù)集算法性能比較

圖4 DB3的STC算法和STCU算法的對比

表2為不同的數(shù)據(jù)集下相應(yīng)閾值調(diào)整后STC算法與STCU聚類性能比較。從表中可以看出，兩種方法在DB1下錯誤率較DB2、DB3都要小，總體性能也要優(yōu)于其他兩個數(shù)據(jù)集。這主要是因為DB1數(shù)據(jù)集小，包含的類別數(shù)目少，冗余信息較少，利用兩種算法聚類得到的精度則相對較高。在STC算法中，DB2的聚類效果比DB3好是由于STC算法未對公共短語進行相應(yīng)的特征提取，所取的公共短語打分后多為語料庫頻率分布在中間的短語，聚類的結(jié)果與實際效果不同；在STCU算法中，DB3的效果要比DB2效果好的原因在于，公共短語經(jīng)過特征提取后，關(guān)鍵短語的分布更為合理，利用其抽取出的聚類結(jié)果更為理想。兩種聚類算法在DB2和DB3上的全面率和準確率等聚類指標上相差不大，說明了提出的STCU算法能應(yīng)對不同大小的數(shù)據(jù)集，對非平衡語料庫具有適用性和穩(wěn)定性。

圖4為DB3下閾值調(diào)整后STC算法和STCU算法對比，從圖4中可以看出，本文的方法較傳統(tǒng)的STC方法，全面率、準確率有了較大的提高，全面率提高了44.51%，準確率提高了11.74%；錯誤率降低了0.94%。從實驗結(jié)果中可以看出，本文提出的STCU算法很好地改善了實驗效果，從而驗證了本文方法在文本聚類的有效性。

為測試聚類閾值與特征提取對算法的影響，對DB3做實驗如下介紹。

（2）聚類閾值的影響

由于基類的數(shù)目比較多，在合并基類后，單獨成類的基類仍較多。如果在合并后進行篩選再排序，很難得到需要的聚類結(jié)果。在基類合并前，設(shè)置一個大致的范圍對基類進行合并，不僅可以減少時間復(fù)雜度，而且能提高聚類的精度。按照文中所給公式，聚類的數(shù)目越多，文本對數(shù)目將急劇增多，全面率會大幅度提高，相應(yīng)的準確率則達不到要求。在實驗中，設(shè)置了1倍人工語料的類的數(shù)目，1.5倍人工語料的數(shù)目，2倍人工語料類的數(shù)目。由圖5可知，當(dāng)調(diào)整聚類數(shù)目和人工語料的類的數(shù)目大致相等時，聚類的全面率和準確率取得了很好的效果。

（3）特征提取的影響

圖5 基類的選擇數(shù)目對聚類的影響

為測試文檔頻率的特征提取方法對聚類算法的影響，從后綴樹中提取公共短語后，去掉其中的低頻詞和高頻詞。在公共短語中，低頻詞一般對結(jié)果影響不大，在實驗中取一個較大的定值（公共短語的50%）予以去除，去掉這些低頻詞能加快后續(xù)處理。而高頻詞對結(jié)果影響較大，因為該短語可能在大部分文本中出現(xiàn)，一些關(guān)鍵性詞語往往出現(xiàn)在其中。抽取過多，則把一些關(guān)鍵詞排除在外，聚類精度不高，取公共短語的1%～2%的比例對算法進行測試。從圖6可以看出，在比例為1.5%時取得較好效果。實驗結(jié)果充分說明了文檔頻率的特征提取方法可以很好地提高算法性能。

圖6 特征短語對STCU算法的影響

5 結(jié)論與展望

針對維吾爾語語言和Web文本特點，本文提出了改進的維吾爾語 Web文本后綴樹聚類算法STCU，采用了多種有效的方法和策略，不僅降低了聚類錯誤率，而且提高了聚類正確率和召回率，大大改善了文本聚類的質(zhì)量。將來的工作是引入語義知識對后綴樹構(gòu)建過程的進一步改進、關(guān)鍵短語的抽取方法研究以及結(jié)合其他的聚類算法得到層次形式的聚類效果，為用戶提供個性化的聚類結(jié)果顯示。

［1]Weiner P.Linear patter n matching algorith ms［C]／／IEEE Conference Record of 14th Annual Sy mposium on Switching and Auto mata Theory，1973.SWAT＇08，1973：1－11.

［2]E.Mc Creight.A space－econo mical suffix tree construction algorith m［J].Journal of the ACM 23，1976：262－272.

［3]E.Ukkonen.Constr ucting suffix trees on－line in linear ti me，in Algorith ms，Soft ware，Architect ure［J].Inf or mation Pr ocessing 92，vol.I （J.van Leeu wen，ed.），Elsevier，1992：484－492.

［4]Ukkonen Esko.On－Line Construction of Suffix Trees［J].Algorith mica，1995，14（3）：249－260.

［5]Gusfield D.Algorith ms on strings，trees，and sequences：co mputer science and co mputational biology［M].Cambridge Univ Pr，1997.

［6]劉遠超，王曉龍，徐志明，等.文檔聚類綜述［J].中文信息學(xué)報，2006，20（3）：55－62.

［7]孫學(xué)剛，陳群秀，馬亮.基于主題的 Web文檔聚類研究［J].中文信息學(xué)報，2003，17（3）：21－26.

［8]趙世奇，劉挺，李生.一種基于主題的文本聚類方法［J].中文信息學(xué)報，2007，21（2）：58－62.

［9]劉振鹿，王大玲，馮時，等.一種基于LDA的潛在語義區(qū)劃分及 Web文檔聚類算法［J].中文信息學(xué)報，2011，25（1）：60－70.

［10]Zamir O，Etzioni O，Madani O，et al.Fast and Intuitive Clustering of Web Documents［C]／／Proceedings of t he 3r d Inter national Conference on Knowledge Discovery and Data Mining.New Yor k，USA：ACM，1997：287－290.

［11]Zamir O，Etzioni O.Web Document Clustering：A Feasibility Demonstration ［C]／／Proceedings of the 21st Inter national ACM SIGIR Conference on Research and Develop ment in Inf or mation Retrieval.USA：ACM，1998：46－54.

［12]Oren Zamir，Oren Etzioni.Grouper：A dynamic clustering interface to Web Search Results［J]，WWW8／Co mputer Net wor ks，1999，31（11－16）：1361－1374.

［13]Janr uang，Jongkol，Guha，Su manta，Ieee.Applying Semantic Suffix Net to Suffix Tree Clustering［C]／／3rd Conference on Data Mining and Opti mization（DMO）／1st Multi Conference on Artificial Intelligence Technology （MCAIT），Putrajaya，MALAYSIA，2011：146－152.

［14]Rafi M，Maujood M，F(xiàn)azal M M，et al.A co mparison of t wo suffix tree－based docu ment clustering algorithms［C]／／Inf or mation and Emerging Technologies（ICIET），2010 Inter national Conference，Karachi，2010：1－5.

［15]H.Chi m and X.Deng.A New Suffix Tree Si milarity Measure f or Docu ment Clustering［C]／／Proc.of WWW＇2007，Banff，Alberta，Canada，2007：121－129.

［16]Jongkol Janruang，Sumanta Guha.Semantic Suffix Tree Clustering［C]／／2011 First IRAST International Conference on Data Engineering and Inter net Technology（DEIT），Bali，Indonesia.2011.

［17]Zhang Dell，Dong Yisheng.Semantic，Hierarchical，Online Clustering of Web Search Results［M].Advanced Web Technologies and Applications：Springer，Berlin，Heidelberg，2004：69－78.

［18]KOPIDAKI S，PAPADAKOS P，TZITZIKAS Y.STC＋and NM－STC：t wo novel online results clustering methods for web searching［C]／／ WISE 2009：10th International Conference.Berlin，Ger many：Springer，2009：523－537.

［19]駱雄武，萬小軍，楊建武，等.基于后綴樹的 Web檢索結(jié)果聚類標簽生成方法［J].中文信息學(xué)報，2009，23（2）：83－88.

［20]郭莉，張吉，譚建龍.基于后綴樹模型的文本實時分類系統(tǒng)的研究和實現(xiàn)［J].中文信息學(xué)報，2005，19（5）：16－23.

［21]楊瑞龍，朱慶生，謝洪濤.快速混合Web文檔聚類［J].計算機工程與應(yīng)用，2010，46（23）：12－15.

［22]楊瑞龍.基于短語特征的 Web文檔聚類方法研究［D].重慶大學(xué)博士學(xué)位論文.2010.

［23]胡海龍，孫晨，赫楓齡，等.基于改進后綴樹算法中英文聚類引擎的實現(xiàn)［J].吉林大學(xué)學(xué)報（理學(xué)版），2009，47（2）：299－304.

［24]林慶，袁曉峰，吳旻.中文 Web文檔聚類算法研究［J].計算機工程與設(shè)計，2009，30（20）：4759－4761.

［25]J W Yang.A Chinese Web Page Clustering Algorith m Based on t he Suffix Tree.Wuhan University Journal of National Sciences［M].2004，9 （5）：817－822.

［26]史慶偉，趙政，朝柯.一種基于后綴樹的中文網(wǎng)頁層次聚類方法［J].遼寧工程技術(shù)大學(xué)學(xué)報（自然科學(xué)版），2006，25（6）：890－892.

［27]哈米提·鐵木爾.現(xiàn)代維吾爾語語法［M].北京：民族出版社版，1987.

［28]劉濤，吳功宜，陳正.一種高效的用于文本聚類的無監(jiān)督特征選擇算法［J].計算機研究與發(fā)展，2005，21（3）：381－386.

［29]閔可銳，趙迎賓，劉昕，等.互聯(lián)網(wǎng)話題識別與跟蹤系統(tǒng)設(shè)計及實現(xiàn)［J].計算機工程，2008，34（19）：212－214.