一種基于文本分類的知識樹自動構建方法

摘 要:針對當前知識管理系統中知識樹的創建和維護問題，設計了一種新的基于文本聚類的知識樹構建方法。由于從傳統的K-means和SOM等文本聚類的結果中難以提取知識樹中節點對應的概念和詞匯列表，選取PLSA方法進行聚類和知識層次樹構建。實驗表明，新方法除了在聚類精確度上優于傳統方法，聚類結果還包含文檔的主題與詞匯之間的概率關系，因此新方法在聚類的同時，可以方便地提取知識樹上每個節點對應的概念或概念集合。

關鍵詞:概率潛在語義分析; 潛在語義空間; 知識管理; 知識樹

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0475-04

doi:10.3969/j.issn.1001-3695.2010.02.019

Automatic construction of knowledge tree based on text clustering

ZHONG Jiang， LIU Jie

(College of Computer Science， Chongqing University， Chongqing 400044， China)

Abstract:The construction and maintenance of the knowledge tree is an important and time-consuming task in a knowledge management system (KMS). This paper presented a novel method to construct the knowledge tree based on text clustering. Because it’s difficult to extract concepts and vocabulary corresponding to nodes in knowledge tree while clustering by traditional K-means and SOM algorithms， selected PLSA (probabilistic latent semantic analysis) to construct knowledge tree. Experiment shows that the clustering accuracy of the new method is higher than the traditional K-means and SOM algorithms. In addition， because the probabilistic relationship between the vocabulary and the concept (subject) has been established， the concepts of node in knowledge tree could be easily extracted while clustering documents by the new method.

Key words:PLSA; latent semantic space; knowledge management; knowledge tree

0 引言

所謂知識管理是通過對知識資源采取一系列系統和規范的管理活動，以獲取知識的最大價值。知識管理系統為企業實現顯性知識和隱性知識的共享提供了新的途徑。它為組織內的成員提供方便收集、查詢、獲取和共享知識的環境，協助知識應用到組織提供的產品和服務中，從而提高企業創新能力和市場反應速度。

知識樹是知識管理系統中常見的知識組織形式，它有利于管理和利用系統中的各種知識資源。知識樹中的每一個節點代表一個主題(概念)，對應著現實世界中的某個概念或知識的某種分類。其中，根節點為知識庫所屬領域的頂層概念，它可能是一個在現實中沒有具體對應類別的虛擬概念;葉子節點表示一個具體的顯性知識，可能對應一類文檔、網頁或者視頻等對象;樹上的邊則表示子節點與父節點之間的從屬關系。例如，可以把一個體育網站中的所有網頁看做一個知識庫，其對應知識樹的頂層節點對應著頂層概念“體育”，頂層概念可以進一步細分為諸如球類、田徑等概念。球類又可分為籃球、足球、羽毛球等概念，田徑可以分為長跑、短跑、跳高和跳遠等概念。通過上述概念的逐層劃分而建立起來的概念樹結構就是知識樹。

知識樹的構建方法，目前主要是依賴專家，通過手工方式創建。而通過人工建立知識樹的結構取決于知識專家對于領域知識中概念關系的理解，因此具有很強的主觀性，不一定符合實際應用的需要。本文試圖利用文本聚類技術來實現知識樹的自動構建。其基本過程是:先將知識庫中的文檔聚成幾個大類，建立第一級概念并將文檔劃分到相應的概念下面;然后對每個概念所包含的文檔子集繼續進行聚類處理，建立子概念的同時實現知識庫的進一步劃分，最后得到一棵滿足特定組織需要的知識樹。

常用的聚類方法有K-means[1]、LSA[2](latent semantic analysis)、SOM[3]等。K-means是基于劃分的聚類方法，聚類速度快但聚類結果的可解釋性差;LSA則通過對詞—文檔矩陣進行截斷的奇異值分解后將文檔投影到低維的潛在語義空間中，其計算量大，且無從對空間中的數據作出語境上的說明;SOM是基于神經網絡的聚類算法，SOM網絡將多維數據映射到低維規則網格中，可以有效地進行大規模的數據挖掘。

PLSA[4]是Hofmann在LSA的基礎上提出來的，聚類結果的語義相關性和聚類精度較其他算法要高等優點使其在用戶興趣聚類、文本分割等領域上有著良好的表現[5，6]。

使用PLSA方法對文檔進行聚類有著較快的聚類速度且聚類精度比LSA和K-means高，并且可以按照其條件概率值將文檔劃分到多個主題下面，因此這種方法與現實中的知識組織方式一致。例如，一篇關于財經的文章可能講述的是汽車行業的狀況，因而這篇文章可以同時歸入財經和汽車這兩個類別中。模糊K-means方法盡管也能夠實現一個文檔從屬多個主題，但其隸屬關系是基于向量空間的距離關系，因此其結果的語義信息不明確。同時在使用傳統方法構建知識層次時，知識樹上節點的具體概念無法通過對文檔的聚類直接獲得，還需要通過輔助的手段(如特征詞的提取技術等)來完成。而PLSA算法在實現聚類的同時還可以提取與對應主題類別語義信息密切相關的詞匯，通過抽取其中相關度最高的詞匯來標示知識樹上相應節點的概念就可以很直觀地反映出該節點代表的概念?；谏鲜鲈?，本文提出了一種基于PLSA的知識樹生成方法。

1 基于概率潛在語義分析(PLSA)的聚類算法

對于文檔集D={d1，d2，…，dn}和詞匯集W={w1，w2，…，wm}，PLSA假定文檔集合中隱含著K類主題(即K個潛在變量){Z1，Z2，…，Zk}，文檔與詞之間相互獨立，文檔與詞共同出現的概率由它們與主題之間的概率關系來決定[3]。圖1所示的是文檔、主題與詞之間常見的兩類關系。其中圖1(a)中的關系模式為詞要經過主題關聯到相應的文檔對象，也即如果文檔di屬于主題zk，那么詞wj出現的概率為P(wj|zk);圖1(b)對應的模式是文檔和詞只與主題相關，即對于主題zk包含文檔di的概率為P(di|zk)，主題zk出現wj的概率為P(wj|zk)。因此基于PLSA的聚類過程可以看成是計算文檔與主題之間條件概率P(di|zk)或P(zk|di)的過程。

根據圖1所示的對象之間的概率關系，可以通過應用Bayes公式獲得以下的等式:

P(zk，di，wj)=P(di)P(zk|di)P(wj|zk)(1)

P(di，wj)=∑Kk=1P(zk)P(di|zk)P(wj|zk)(2)

P(zk|di，wj)=P(di，wj|zk)P(zk)P(di，wj)(3)

P(di|zk)=P(zk|di)P(di)P(zk)(4)

對于一個文檔集合，可見的數據就是描述詞與文檔共同出現情況的文檔—詞矩陣C(n(i，j))。其中n(i，j)表示文檔di中出現詞wj的次數。由于潛在變量(主題)是不可見的變量，通常利用EM算法來估計P(di|zk)以及P(wj|zk)最有可能的值，即P(di|zk)和P(wj|zk)的取值使得在完備數據集上的聯合分布概率值Lc最大。其中Lc為

Lc=∑Ni=1∑Mj=1∑Kk=1n(zk，di，wj)log P(zk，di，wj)(5)

其中:n(zk，di，wj)是主題zk、文檔di和詞wj一起出現的次數。由于zk是觀察不到的對象，該值只能通過P(zk|di，wj)來估計?？紤]到概率值P(zk|di，wj)的后驗概率形式為P(zk|di，wj)=n(zk，di，wj)/n(di，wj)，因此Lc可利用式(6)來計算。

Lc=∑Ni=1∑Mj=1n(di，wj)∑Kk=1p(zk|di，wj)×

log (P(di)P(zk|di)P(wj|zk))=

∑Ni=1∑Mj=1n(di，wj)∑Kk=1P(zk|di，wj)×

log (P(zk)P(di|zk)P(wj|zk))(6)

對于計算過程中的E(expectation)步驟，先通過式(7)來估計條件概率:

P(zk|di，wj)=P(di|zk)P(wj|zk)P(zk)∑Kk′=1P(zk′)P(di|zk′)P(wj|zk′)(7)

在M(maximization)步驟中，需要計算Lc的最大值，由于式(6)中的概率值存在著等式約束，增加相應的拉格朗日系數αi、βj、λ，那么Lc的最大值問題轉換為計算式(8)的極值。

H=Lc+∑Ki=1αi(1-∑Nj=1P(di|zk))+∑Ki=1βi(1-∑Mj=1P(wj|zi))+λ(1-∑Kk=1P(zk))(8)

式(8)的極值點為變量P(wj|zk)，P(di|zk)，P(zk)的偏導數為零的點，據此條件獲得式(9)~(11):

∑Ni=1n(di，wj)P(zk|di，wj)-αkP(wj|zk)=0

1≤k≤K，1≤j≤M(9)

∑Ni=1n(di，wj)P(zk|di，wj)-βkP(di|zk)=0

1≤k≤K，1≤i≤N(10)

∑Ni=1∑Mj=1n(di，wj)P(zk|di，wj)-λP(zk)=01≤k≤K(11)

消除拉格朗日系數后得到M步驟中的條件概率式:

P(wj|zk)=∑Ni=1n(di，wj)P(zk|di，wj)∑Ni=1∑Mj′=1n(di，wj′)P(zk|di，wj′)(12)

P(di|zk)=∑Mj=1n(di，wj)P(zk|di，wj)∑Ni′=1∑Mj=1n(di′，wj)P(zk|di′，wj)(13)

P(zk)=∑Mi=1∑Nj=1n(dj，wi)P(zk|dj，wi)∑Mi=1∑Nj=1∑Kk′=1n(dj，wi)P(zk′|dj，wi)(14)

經過反復執行E、M運算，如果Lc的增加量小于給定的閾值或達到指定的迭代次數時停止計算，那么此時的P(wj|zk)、P(di|zk)就是每個文檔和詞與主題之間最有可能的概率值。

2 知識樹的生成算法

知識樹的生成過程可以采用自頂向下的方式進行。用戶先指定知識樹根節點下包含的子概念的數量，然后利用PLSA聚類生成相應子概念(主題)，并將文檔劃分到相應的子概念下面。用戶可根據需要反復執行子概念生成算法，直到知識樹滿足用戶的需要為止。下面是根據概念所包含的文檔集合生成子概念的算法流程。

輸入:文檔集合、子概念的個數。

輸出:子概念集合以及每個子概念包含的文檔集合。

a)詞—文檔矩陣的建立和預處理。

b)計算每個詞和文檔從屬于主題的概率。

c)詞和文檔的劃分。

d)輸出結果，算法退出。

算法說明:

步驟a)在建立詞—文檔矩陣時，將不可聚類的文檔(該文檔不包含任何名詞集合中的名詞)打上標記，并將其對應的列從詞—文檔矩陣中刪除，以避免在后面的計算中出現除零錯誤而導致算法無法正常運行。

步驟b)中通過使用PLSA方法在詞—文檔矩陣上進行計算詞和文檔屬于各個主題的概率值P(wj|zk)、P(di|zk)以及各個主題出現的概率值P(zk)。

步驟c)中根據b)計算得出的詞和文檔從屬于各個主題的概率值大小將詞和文檔劃分到相應的主題下，從而得到關聯到各個主題下的詞與文檔集合。

算法執行完后可以通過人為參與判斷聚類的結果，如不理想則調整算法的收斂條件重新進行計算。

由于詞—文檔矩陣是一個稀疏矩陣，通過用二維鏈表來表示矩陣，并對算法中矩陣運算進行優化后使得算法在時間復雜度和空間復雜度上都有了很大的提高。時間復雜度為O(Ti×N×L×K)，空間復雜度為O((N+M)×K+N×L)。其中:Ti為EM迭代的次數;N為文檔庫中的文檔個數;L為平均每個文檔中包含的名詞數量;M為所有詞數量;K為潛在主題的數量。

3 實驗結果及分析

3.1 實驗數據集

本文的實驗采用由Sougou實驗室(網址http://www.sogou.com/labs/)提供的語料庫，實驗中選取語料庫中8個領域共15 920個文檔作為實驗數據，以1998年版《人民日報》手工標注的語料庫建立基于2-Grams統計分詞器，并對文本庫進行分詞處理。由于自然語言中通常利用名詞來描述概念，實驗過程中基于出現頻率較高的名詞(包括人名、地名、機構名稱和其他專有名詞)構建詞—文檔矩陣。本文實驗采用文檔庫中出現頻率高的5 000個名詞。

由于Sougou語料庫只對文檔進行第一層的劃分，即將文檔分成文化、體育、健康等類別，但是對于每一類別下面的子類則沒有進一步劃分。為了驗證算法的有效性，實驗過程中分別對體育和健康兩個類別下的1 000個文檔通過人工分類方法進行了進一步劃分。其中體育劃分為世界杯、籃球-NBA、歐洲足球聯賽、羽毛球、中超五個子類;對于健康類別的文檔，則劃分成保健、醫藥、心理健康三個子類。

3.2 評價標準

顯然知識樹的構建過程中對文檔庫劃分的結果與人工劃分結果越吻合，那么生成的知識樹結構就越能滿足人們對文檔的組織和管理需求。因此聚類的質量直接決定了其構建知識樹的質量。文中通過引入信息熵和聚類純度[7]來對聚類質量進行評價。信息熵通過計算聚類結果的混亂度來度量聚類的結果，而聚類純度通過計算聚類結果的純凈度來評價聚類結果。

對文檔庫中已經標志的K個類別Tj(j=1，2，…，K)和聚類簇(潛在語義空間)Ci(i=1，2，…，K)，計算聚類簇Ci的信息熵Ei和聚類純度πi:

ni為劃分到聚類簇Ci中的文檔總個數。

nij為被劃分到聚類簇Ci中且屬于類別Tj的文檔個數。

Ei=-1log H ∑Hj=1nijni log nijni(15)

πi=1nimaxj(nij)(16)

信息熵Ei(0≤Ei<1) 反映聚類結果中主題的分布情況，熵值越高聚類質量越差。值為0，表明分類結果與聚類結果完全一致。

聚類純度πi(0<πi≤1) 計算聚類Ci下文檔數最多的類別所占該聚類結果中所有文檔的比重。πi的值越大，表明聚類質量越好。

3.3 結果及分析

為了進行對比分析，實驗中基于TF-IDF方法來表示文檔，其中詞向量空間同樣采用5 000個高頻的名詞，使用K-means和SOM方法分別進行聚類，并對文檔進行劃分。對于PLSA的分析結果，將根據文檔所屬主題的概率值大小進行文檔劃分操作。如果文檔di滿足式(17)，那么將文檔di劃分到分類(主題)k中。

P(di|zk)=maxj=1，…，K{P(di|zj)}(17)

表1中的結果是在所有文檔上分別按照K-means、SOM和PLSA方法進行聚類后對聚類質量的評價。表2是對體育和健康下的子概念聚類質量的評價。根據表1和2中的結果，采用PLSA方法聚類比基于劃分的K-means方法和基于神經網絡的SOM方法的熵平均降低了約0.06，聚類的純度提高了約4%。同時在軍事、體育和財經等類別的文檔中，將聚類純度提高約3%~6%。由以上結果可以得知:相對于傳統的聚類方法，基于PLSA生成的知識樹與實際的知識結構更吻合。

表1 所有文檔聚類質量的評價

文檔

K-means聚類結果

EntropyPurity

SOM聚類結果

EntropyPurity

PLSA聚類結果

EntropyPurity

財經0.251 60.872 40.235 40.881 20.201 20.920 4

文化0.486 60.728 40.493 20.706 80.417 30.756 1

健康0.386 30.806 40.368 70.814 90.342 50.834 6

體育0.354 20.816 20.346 80.822 80.266 30.871 6

旅游0.398 80.782 90.402 20.766 90.401 80.808 2

教育0.404 20.758 20.423 70.727 80.357 20.806 2

招聘0.524 40.701 20.512 50.706 50.477 80.731 7

軍事0.361 40.848 70.352 30.856 40.191 40.909 7

平均0.396 00.789 30.391 90.785 40.331 90.829 8

表2 體育和健康下子概念聚類質量的評價

文檔

K-means聚類結果

EntropyPurity

SOM聚類結果

EntropyPurity

PLSA聚類結果

EntropyPurity

體育0.304 40.362 30.300 60.366 20.350 10.834 60.752 40.838 60.757 60.764 5

0.286 60.368 70.298 90.368 10.356 7

0.852 10.748 60.845 40.754 20.757 6

0.255 10.322 40.288 60.354 70.310 5

0.894 10.802 10.885 60.788 60.820 5

0.334 40.806 20.335 70.827 00.322 50.854 3

健康0.348 30.752 60.351 20.752 60.343 20.822 3

0.341 60.816 20.339 70.820 40.336 80.838 7

平均0.337 20.790 30.338 20.794 70.316 70.838 3

PLSA方法不僅能夠分析文檔與潛在主題之間的概率關系，同時該方法獲得了詞匯與潛在主題之間的概率關系。圖2列出了每個主題下出現概率最大的前10個詞(圖中數字是對應詞的P(wj|zk)乘10的值)。從圖2中可以看出，各類主題下的詞匯基本上反映了該主題密切相關的概念，人們甚至無須分析該主題下的文檔，可以直接通過這些詞匯較容易地獲得反映該主題的概念描述。

為了說明基于PLSA方法的聚類結果具有更為清晰的語義，利用周茜等人在文獻[8]中提出的基于類別區分詞的特征選取方法，選取了每個主題的特征詞。圖3中列舉了CDW (t)值最大的10個詞。

通過將圖2和3中的結果對比分析發現:基于PLSA獲得的詞匯包含了更豐富、更完整的語義信息，而CDW(t)方法獲得的詞匯則更傾向于反映其在文檔中出現的頻率。例如對于財經主題，基于CDW(t)獲得的詞，主要集中了文檔中最常出現的詞匯，而基于PLSA方法獲得的詞涵蓋了更廣泛的財經方面的信息。又如教育主題下的詞匯，CDW(t)獲得的詞匯甚至包含與該概念沒有直接關系的詞，如“動詞”，而基于PLSA方法獲得的詞則不僅涵蓋這方面的概念，同時包含學校、教師、專業等與教育相關的概念。其他的類別中也可以看出用類別特征提取出的詞與主題的相關性很高，但是該類別下總體的語義信息不相符，而用PLSA方法提取的概率最高的詞可以反映出類別的整個語義信息。

綜上所述，PLSA能提取反映出類別語義信息的詞匯集合，而且這種方法比單純根據分類特征提取的詞能更好地反映類別的語義信息。因此基于這些具備良好語義定義的知識樹來組織知識庫中的文檔，將更有利于今后對這些文檔的檢索和利用。同時通過提取出的反映類別語義信息的詞匯來標注知識樹上的節點，不但簡化了知識樹的構建過程，而且這種標注方法能更真實地反映節點下文檔所包含的概念。

4 結束語

本文基于PLSA聚類算法設計了一種新的知識樹構建方法。實驗表明，與傳統方法比較，新方法具有更高的聚類精度，生成的知識樹能更自然地反映顯性知識間的語義關系，且能對知識樹上節點的概念進行自動標注。新方法解決了知識管理系統中在創建和維護知識樹時存在的耗時和結果難以符合用戶特定要求等問題，此方法在知識管理領域中知識樹的自動化構建問題上有很好的應用前景和較高的研究價值。

參考文獻:

[1]KANUNGO T， MOUNT D， NETANYAHU N， et al. An efficient K-means clustering algorithm: analysis and implementation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2000， 24(7):881-892.

[2]DEERWESTER S， DUMAIS S T， FURNAS G W， et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science， 1990，41(6):391-407.

[3]KOHONEN T. The self-organizing map[J]. Proc IEEE，1990，78(9):1464-1480.

[4]HOFMANN T. Unsupervised learning by probabilistic latent semantic analysis[J]. Machine Learning， 2001， 42(1-2):177-196.

[5]陳冬玲， 王大玲， 于戈，等. 基于PLSA方法的用戶興趣聚類[J].東北大學學報:自然科學版，2008，29(1):53-56.

[6]石晶， 戴國忠. 基于PLSA模型的文本分割[J]. 計算機研究與發展，2007，44(2):242-248.

[7]BOUCHACHIA A. PEDRYCZ W. Enhancement of fuzzy clustering by mechanisms of partial supervision[J]. Fuzzy Sets and Systems， 2006， 157(13):1733-1759.

[8]周茜，趙明生，扈旻. 中文文本分類中的特征選擇研究[J]. 中文信息學報， 2004， 18(3):17-23.