模糊聚類技術在文獻自動分類系統中的應用

〔摘 要〕本文采用模糊聚類技術，結合《中國圖書館分類法》，嘗試建立一種新型的文獻自動分類機制。文章采用模塊化技術，提出整套系統的設計流程和關鍵點的設計，并分析了其優缺點。目的是為文獻的自動分類探索一種新的思路和方法。

〔關鍵詞〕自動分類;模糊C均值;圖書館專家系統

〔中圖分類號〕G254 〔文獻標識碼〕B 〔文章編號〕1008-0821(2009)09-0166-03

Application of Fuzzy Clustering Technology in

Literature Automatic Classification SystemChu Cunkun Li Tao

(Library，Taishan medical college，Taian 271000，China)

〔Abstract〕In this paper，based on fuzzy clustering technology，combined with“Chinese Library Classification”，the author tried to establish a new mechanism for automatic classification of literature.The article adopts modular technology，the entire system to the design process and the key points of the design and analysis of its advantages and disadvantages.This paper documents for the automatic classification explored a new way of thinking and methods.

〔Key words〕automatic classification;fuzzy c-means;library expert system

自1960年Maron在Journal of ASM發表了有關自動分類的第一篇論文，隨后許多著名的情報學家如K.Sparch，G.Salton及R.M.Needham等都在這一領域進行了卓有成效的研究[1]。到目前為止，自動分類在國外大體經歷了3個發展階段:第一階段(1958-1964)主要進行自動分類的可行性研究;第二階段(1965-1974)進行自動分類的實驗研究;第三階段1975-至今)進入實用化階段。但是由于分類方法的不同，這些軟件并不能在我國通用。我國的自動分類工作經歷了2個階段，1981年候漢清老師首次對自動分類進行了探討[2];1991年后以李欣老師為代表的一批人開始了試驗軟件的研發[3]，然而到現在為止，雖然有一些自動化分類軟件誕生，但是離社會化、商品化還有一定的距離，尚處于第二階。究其原因一是開發技術難度比較大，普通圖書館技術人員難以勝任，二是少量開發出的軟件推廣難度比較大，辛辛苦苦開發出的軟件由于各種原因不能被廣泛應用，沒有信心繼續研究。本文嘗試將一種廣泛使用于圖像處理領域的分類算法——模糊聚類技術移植到文獻自動分類中來，借以探索新的研發途徑。

1 模糊聚類技術簡介及移植思路

模糊聚類技術是一種智能分類技術，目前廣泛應用在數據挖掘、圖像分割、模式識別等領域并取的了良好的效果。它非常適合處理事物內在的不確定性，而且對噪聲不敏感;它利用多值邏輯來描述復雜系統，能以更接近人的思維方式準確地對事物進行分類[4]。

模糊聚類技術的典型算法——模糊C均值算法(fuzzy c-means，FCM)是一種較典型的逐點修改迭代的動態聚類算法，其要點是以誤差平方和為準則函數。逐點修改聚類中心:一個元素按某一原則，歸屬于某一組類后，就要重新計算這個組類的均值，并且以新的均值作為凝聚中心點進行下一次元素聚類;逐批修改聚類中心:在全部元素樣本按某一組的類中心分類之后，再計算修改各類的均值，作為下一次分類的聚類中心點。

其核心思想是[5]:算法把n個向量xj(1，2，…，n)分為c個組Ci(i=1，2，…，c)，并求每組的聚類中心，使得非相似性(或距離)指標的價值函數(或目標函數)達到最小。當選擇歐幾里德距離為組j中向量xk與相應聚類中心ci間的非相似性指標時，價值函數定義為:

J=∑Ni=1∑Cj=1(μij)mxi-υj2

其中:uik=1+∑Cj=1j≠ixk-υi2xk-υj21/m-1-1(1)

υi=∑Nk=1(μik)m#8226;xk∑Nk=1(μik)m(2)

圖書自動分類系統的核心部分是推理機。其任務是模擬分類專家的思維過程，控制并執行對問題的求解。它能根據當前已知的事實，利用知識庫中的知識，按一定的推理方法和控制策略進行推理，最后得到分類結果[6]。

結合FCM算法的特點，本文圖書自動分類系統推理機的推理流程如下:

第一步:給定分類數C，初始化加權指數m及容許誤差εmax，令迭代計數變量p=1;

第二步:初始化聚類中心υi，i=1，2，…，c;

第三步:按式(1)計算隸屬度uik，k=1，2，…，C;i=1，2，…，N;

第四步:按式(2)修正所有的聚類中心υk(p+1)，k=1，2，…C;

第五步:計算誤差:ε=J(p+1)-Jp;

第六步:如果ε<εmax或者p>N則算法結束;否則p=p+1，轉向第三步。

算法結束后，可以按下述兩種方法對所有的樣本分類:

方法一:若ujk>ujk，k=1，2，…，c;i≠k，則將xj歸入第i類;

方法二:若xj-vi2

具體推理流程圖如圖1所示。其中參數C指的是分類數，Ci指第i級共有多少類;j參數控制分類精度，指共分到多少級;m是模糊指數，控制模糊聚類算法的指數，一般取2.0。N是模糊聚類算法的最大循環次數，防止進入死循環。ε參數為一個極小值，控制聚類精度，同時控制分類的精確程度。內循環為FCM算法，外循環控制分類的精度。

2009年9月第29卷第9期現?代?情?報Journal of Modern InformationSep.，2009Vol.29 No.92009年9月第29卷第9期模糊聚類技術在文獻自動分類系統中的應用Sep.，2009Vol.29 No.9

2 基于模糊聚類技術的自動分類技術的實現

2.1 總體思路

鑒于本自動分類系統主要面向圖書館工作人員和圖書分類的專家，因此該軟件的總體設計思想是人機界面友好、系統功能強、分類要快速準確、具有自動學習功能。軟件要以菜單驅動，利用詞的類分、詞語間的關系、詞和范疇之間的關系的分類規則通過模糊聚類技術的典型算法——模糊C均值(fuzzy c-means，FCM)算法處理對圖書進行自圖1 推理流程圖

動分類，得到正確的類名和類號，同時給出恰當的解釋。

2.2 系統的構成

圖書自動分類系統由以下幾個部分組成:人機接口及與其他數據庫的接口、圖書分類知識庫、推理機、數據庫、解釋機、圖書分類知識獲取機制。其系統框架見圖2。圖書自動分類系統通過人工輸入及從圖書館現有數據庫中導入圖書文獻信息，然后推理機將圖書文獻信息與知識庫中的規則進行匹配、推理、求解，得出此圖書文獻的分類號，最后由解釋機將整個分類的過程輸出給用戶。

圖2 圖書自動分類系統的組成

用戶接口是系統與一般用戶間的界面，由一組程序及相應的硬件組成，用于完成輸入輸出工作。圖書分類專家通過它輸入知識，更新、完善知識庫;一般用戶通過它輸入已知事實以及向系統提出的詢問;系統通過它輸出運行結果、回答用戶的詢問或者向用戶索取進一步的事實。如今，用戶界面通常采用友好的WINDOW界面。與數據庫的接口是為了充分利用圖書館已經建好的數據庫中的有效信息，以盡可能的減少用戶的輸入量。為了能與多種數據庫兼容，與其他數據庫的接口通常采用ODBC作為數據庫訪問的應用程序編程接口，并使用結構化查詢語言SQL作為其數據庫的訪問語言。

知識庫存放著作為圖書分類標準的知識本體以及相關的規則，如各種推理、判斷規則等，用于某種結論的推理、問題的求解，以及對于推理、求解知識的各種控制知識。除此之外，圖書分類知識庫還包括一些必要的管理功能，主要用于對知識條目的查詢、檢索、增刪、修改、擴充等操作。知識表示是知識庫建立的前提。專家系統問題的求解是以知識為基礎的。如何將已獲得的有關知識以計算機內部代碼形式加以合理地描述、存儲，以使有效地利用這些知識便是知識表示。知識表示方法有許多種，包括規則、語義網、框架、腳本等[7]。采用何種方法表示分類專家知識的依據其特點而定?！吨袌D法》分類規則作為整個知識庫的主要部分，是較為典型的樹型結構體系，對知識的組織采用的是從一般到具體、從寬到窄層層劃分的方式。因此采用產生式表示法較為有效。

推理機的構成參加本文第二部分模糊聚類技術簡介及移植思路。

數據庫用于存放人機接口及與數據庫接口提供的初始圖書文獻信息事實以及系統運行過程中得到的中間結果、最終結果、運行信息(如推出結果的知識鏈)等等。數據庫的內容是動態的，在系統開始運行時，它存放的是人機接口及與數據庫接口提供的初始事實;在推理過程中它存放每一步推理所得到的結果。推理機根據數據庫的內容從知識庫選擇合適的知識進行推理，然后又把推出的結果存入數據庫中。因此，數據庫是推理機不可缺少的一個工作場地，同時由于它可記錄推理過程中的各有關信息，又為解釋機構提供了回答用戶咨詢的依據。

解釋機負責對推理的結果作出必要的解釋，以便向用戶說明推理過程，使用戶接受推理的結果。它由一組程序組成，能跟蹤并記錄推理過程，當分類結束需要給出解釋時它將推理過程通過人機接口輸出給用戶。

知識獲取分人工獲取和自動獲取。它為知識庫的建立、修改知識庫中已有的知識和擴充新的知識提供手段。在專家與系統交互過程中，發現需要修改、刪除或增加的知識及由此引起的一切必要的改動，都要利用這部分。它是保證系統靈活性的必要部分，直接影響系統的生命力。

2.3 核心程序VC++編程實現

for(i=0;i

{

for(j=0;j

{

ftemp=0;

for(k=0;k

{

ftemp+=pow(adomatrixu[i*nnumpattern+k]，fweightm)*adipattern[k*ndimension+j];

}

adocenter[i*ndimension+j]=ftemp;

ftemp=0;

? for(k=0;k

{

ftemp+=pow(adomatrixu[i*nnumpattern+k]，fweightm);

}

? adocenter[i*ndimension+j]/=ftemp;∥寫入聚類中心

}

}

ncycle++;

nProcess=ncycle;

dDelta=delta;

}while(ncycledthreshold);

? sndPlaySound(″d:\\\\bird.wav″，SNDASYNC);

return 0;

3 實驗結果

分類系統系統完成后，將泰山醫學院圖書館R類中隨機抽取3 000種圖書文獻做樣本進行分類測試，其中單主題文獻1 945種，多主題文獻1 055種。通過測試來驗證本系統對于主題類型模式相對簡單的文獻和比較復雜的文獻分類準確性，根據在每個推理環節都得出的結果，最終來驗證分類效果。

結果對于單主題類型圖書的分類精確度達91.3%，對于多主題分類精度62.5%?？梢妼τ趩沃黝}類型的圖書該系統有較優異的表現，但是對于多主題的文獻的分類，表現一般，有待于算法的改進。

4 討 論

自動分類對于信息處理具有極其重要的意義。隨著Web2.0技術發展，網上信息泛濫嚴重，如果不加以有效整理，人們將難以有效利用，而這是人工無法完成的，我們必須借助自動搜索和自動分類技術對信息進行提取、加工、組織利用。從自動分類研究的發展來看，基于學習的自動分類法有較強的生命力，模糊聚類技術有較強的智能性，故該方案有較大的發展前途。但是難點在于知識庫的建立，建立的模式是什么?是基于本體的還是基于樹形結構的，以及索引表的建立方法和層次。本系統的優勢在于首次嘗試將FCM算法移植到圖書自動分類系統，可以在一定程度上推動自動分類研究的發展，進一步可以為未來網絡文獻的自動挖掘、分類探索出一條有益路徑。

作者認為基于知識本體的知識庫會使分類的準確度會有很大的提高，在未來的發展中具有很 大的潛力，是未來發展的一個方向。

參考文獻

[1]Golub K，Hamon T，Ardo A.Automated Classification of Textual Documents Based on a Controlled Vocabulary in Engineering[J].Knowledge Organization，2007，34(4):247-263.

[2]侯漢清.分類法的發展趨勢簡論[J].情報科學，1981，(1):58-68，30.

[3]李欣，陳星，閻慧，等.圖書分類專家系統設計[J].現代圖書情報技術，1991，(4):46-47.

[4]Shen S，Sandham W，Granat M，et al.MRI fuzzy segmentation of brain tissue using neighborhood attraction with neural-network optimization[J].IEEE Trans Inf Technol Biomed，2005，9(3):459-67.

[5]羅述謙，周果宏.醫學圖像處理與分析[M].北京:科學出版社，2003:93.

[6]Yi K.Automated Text Classification Using Library Classification Schemes:Trends，Issues，and Challenges[J].International Cataloging Bibliographic Control，2007，36(4):78-82.

[7]張惠.圖書自動分類專家系統的研究[J].佛山科學技術學院學報:自然科學版，2001，19(2):37-40.