分類算法在范例推理中的研究與應用

劉連喜，邢 彤，徐 浩，王 偉，高 凱

（1.河北科技大學財務處，河北石家莊 050018；2.河北化工醫藥職業技術學院，河北石家莊 050026；3.河北科技大學信息科學與工程學院，河北石家莊 050018）

分類算法在范例推理中的研究與應用

劉連喜1，邢 彤1，徐 浩2，王 偉3，高 凱3

（1.河北科技大學財務處，河北石家莊 050018；2.河北化工醫藥職業技術學院，河北石家莊 050026；3.河北科技大學信息科學與工程學院，河北石家莊 050018）

將范例推理中的范例初步匹配看作文本分類的特殊情形，提出基于類別中心向量的分類算法。通過確定待處理案例的歸屬類別，縮小范例檢索范圍，減少在范例精確匹配階段的計算量，提高案例初步匹配的準確性。在此基礎上，將上述算法應用在對交通事故案例的處理與交通信息預警系統中。實驗與使用表明，該算法能較為準確地判斷事故類型并給出相應的預警信息。

人工智能；自然語言處理；分類；信息檢索；范例推理

范例推理（case－based reasoning，CBR）作為基于規則推理技術的一個重要補充，是當前人工智能及機器學習領域中的熱門課題與前沿研究方向之一。CBR的執行過程如圖1所示，主要包括檢索相似案例、重用相似案例并推斷新案例解決方案、修訂解決方案、保存新案例以備后用等。由于CBR具有信息的完全表達、增量式學習、形象思維的準確模擬、求解效率高等特點，因此能夠應用在那些沒有很強的理論模型和領域知識不完全的決策環境中［1］。目前，關于范例推理的研究主要集中在以下幾個方面：范例的索引及檢索技術，范例修正技術及其修正規則的獲取方法，范例庫的維護技術及其性能的研究，范例工程的自動化，范例推理的理論基礎，范例推理與其他方法（包括學習技術、多Agent技術、推理方法、數據挖掘、數據倉庫技術）的集成技術，范例推理的應用，研制CBR開發平臺，CBR融合及大規模并行處理，基于Web的分布式CBR系統，可視化CBR技術及對話式CBR模型等［2－5］。

圖1 CBR執行過程Fig.1 Process of CBR

由于交通事故發生的原因和案發現場的勘察結果之間往往有著一定的因果聯系，因此通過對事故勘查的特征提取，并通過相應的匹配算法，將所抽取出來的新案例特征與范例庫中典型事故案例——指那些已成功處理、具有某些典型的特征屬性進行比較，檢索那些較符合的事故案例，找出相應事故的解決方案，并由分析得出相應的預警信息是可行、可信的。基于CBR的交通事故處理及其預警機制研究，可為處理類似的交通事故案件提供決策參考。但一般的范例推理過程在檢索源范例時，往往存在著檢索結果不準確、檢索效率低下等問題。如果能在檢索范例之前，通過適當的分類算法，確定新案例最可能歸屬的類別，然后再在其所屬類別范圍里通過相似度查找最近似的部分范例，就可以有效縮小范例檢索的范圍，提高范例檢索的效率和準確率。在此將范例的初步匹配問題看作文本分類問題的特殊情形，提出基于類別中心向量的分類算法，并將其應用到范例推理的初步匹配階段。從空間幾何角度看，計算平均向量的過程就是計算多維空間中1個點集群中心的過程，只要1個點處于以這個中心和一定半徑所劃定的空間區域里，就可以認為該點所代表的案例歸屬于這個中心向量所代表的類別。在前期工作基礎上，通過分類算法首先確定待處理案例的歸屬類別，減少了在范例精確匹配階段的計算量，提高了范例推理系統整體性能。通過對公路車輛監控與交通事故處理（數據分析）的應用表明，該算法能較為準確地判斷事故類型并給出相應的預警信息。

1 范例的組織及其向量化表示

在CBR及其推理過程中，首先要明確范例庫及其組織方式。在本應用中，范例庫中所有交通事故范例按事故原因被分成8個類存儲，相同類別的范例保存在以類別名稱命名的文件夾中，各種信息用不同字段標志符表示出來。當有新的案例到來時，首先依據類別中心向量分類算法確定新范例的歸屬類別，然后計算新范例與其歸屬類別中每個范例的語義相似度，如果相似度大于閾值，就認為新范例與已有范例相似，不再儲存，否則將新案例的信息數據以文本文件的形式保存到所屬類別的文件夾里。

當完成了范例的向量化表示后，就構建起了范例庫的向量空間模型，之后才能在這個向量空間里實現分類算法。為了便于將范例內容映射入向量空間，使用中科分詞模塊ICTCLAS對范例的正文文本進行分詞處理。即首先將范例正文中的所有非中文字符替換為空格符，使用分詞模塊對預處理的范例正文進行分詞，根據停用詞詞典去除分詞結果中的停用詞。要想實現范例的向量化表示，須首先建立向量模板，之后可以依據向量模板實現范例的向量化。向量模板的構建過程大致分如下4個步驟。

1）逐篇掃描范例庫每個范例正文的分詞結果，分別統計各詞項在所屬范例正文中出現的詞頻（TF）和各詞項在所屬范例類別中出現的文檔數（DF）。

2）選擇特征詞。采用TFIDF算法作為特征詞權值的計算方法，計算公式如式（1）所示，其中IDF是詞條t的逆文檔頻率，m是某一類別文檔中包含詞條t的文檔數，n是包含詞條t的文檔總數。

3）將所有詞項按照IDF值從大到小排列，再根據預先設定的最大向量維數k選取IDF最大的前k個詞項作為特征詞項。為了統一所有特征詞項的分布概率，需要對特征詞的IDF值進行歸一化處理，具體方法如式（2）所示，式中IDFi表示第i項特征詞的IDF值，max（·）函數表示所有特征詞項中最大的IDF值。

在構建了向量模板以后，就可以依據向量模板實現范例的向量化表示了，主要步驟如下。

1）將范例正文中的非中文字符替換為空格，用分詞模塊對其進行分詞。

2）統計每個范例中各詞項的文檔頻率TF。考慮到范例正文長度的差異，須依據范例正文長度對每個詞項的文檔頻率進行歸一化處理，計算公式如式（3）所示，其中TFi是范例中詞項i的文檔頻率，li是范例正文長度。

為了統一范例中詞項的分布概率，還需要對詞項的TF值進行歸一化處理，見式（4），式中max（·）是范例正文所有詞項中最大的TF值：

在完成向量歸一化后，掃描范例分詞結果中的每個詞項。當把一個范例正文分詞結果中所有詞項掃描完畢后，就得到了該范例的空間向量。

2 類別中心向量的分類算法及其應用

類別中心向量是用各個類別的中心向量來代表相應類別，并且根據新來的案例向量與各類別中心向量的相似程度來判別新案例所歸屬的范例類別。算法處理流程見圖2。

圖2 類別中心向量分類算法流程圖Fig.2 Flow chart of the class－center vector based category algorithm

在建立了范例的向量空間模型以后，各范例都表示為向量的形式。筆者采用算數平均的方法來計算各類別的中心向量，計算公式如式（5）所示，式中Vcenter為某文檔類別的中心向量，W1為范例向量中第1維向量的權重，Wj為范例向量中第j維向量的權重，ni為文檔類別i中包含的文檔數：

通過上述步驟計算得到了各范例類別的中心向量、中心向量常數以及各類別的分類閾值后，就可以著手生成類別中心向量分類算法中的分類器模型。為了便于各種類型數據的統一存儲，采用XML文件格式保存分類器模型。當某個類別的中心向量需要動態修正時，XML文件可以方便地讀取和保存相應類別的中心向量。圖3是分類流程。范例推理系統的輸入數據就是待處理的交通案例，輸出就是交通事故的處理方案和某一時段的交通預警信息。在得到（或者用戶輸入）新案例后，首先將新案例的數據進行向量化處理，然后應用提出的分類算法來確定新案例所屬的類別，從而實現案例的初步匹配。之后，就可以在新案例所屬的類別內利用向量的相似度算法為新案例找到最為相似的范例，從而實現案例的匹配，最終實現交通事故案例的范例推理過程，并借助它輔助交通處理事故。

3 實驗分析與測試

圖3 分類流程Fig.3 Flow of the category

分別在不同的訓練和測試樣本集中，在不同的兼取類別情況下，對類別中心向量分類算法在交通范例推理系統中的應用性能進行了測試。表1是在封閉性測試情況下，測試兼取類別數對分類器性能的影響。

表1 封閉性不同兼取類別測試Tab.1 Colse test on different compatibility numbers of the category

從表1數據可以看出，兼取類別數增加后，分類器的性能得到了顯著提高。可見在對交通案例進行初次匹配時，必須考慮兼類的情況，這也是符合客觀事實的。

在交通案例的選取上，基礎案例的缺乏是一個不可避免的問題。由于行業數據的保密性，這里采用的是從網上收集的一些案例來充當范例庫的素材。盡管本文提出的算法有效實現了案例的初步匹配，但是該分類算法的性能還有提升空間，所以下一步還要在改進分類算法性能上再做一些工作。

4 結 語

將范例的初步匹配問題看作文本的分類問題，提出基于類別中心向量的分類算法，并將其應用到范例推理系統的初步匹配階段。通過分類算法首先確定待處理案例的歸屬類別，有效縮小了范例檢索的范圍，減少了在范例精確匹配階段的計算量，提高了范例推理系統整體性能。實驗與使用表明，該算法能較為準確地判斷事故類型并給出相應的預警信息。

［1］ 劉 芳.基于CBR的智能決策支持系統研究與應用［D］.蘭州：蘭州大學，2008.

［2］ 陸汝鈐.世紀之交的知識工程與知識科學［M］.北京：清華大學出版社，2001.

［3］ 陳文偉.決策支持系統及其開發［M］.北京：清華大學出版社，2000.

［4］ 周 勇，賈瑞玉.范例推理在智能決策系統中的應用研究［J］.電腦知識與技術（學術交流）（Computer Knowledge and Technology（Academic Exchange）），2007（3）：824－829.

［5］ 王 偉，許云峰，高 凱.基于哈希表的動態向量降維方法的研究及應用［J］.河北科技大學學報（Journal of Hebei University of Science and Technology），2011，32（4）：360－365.

Study on catagory algorithm and its application in cased－based reasoning

LIU Lian－xi1，XING Tong1，XU Hao2，WANG Wei3，GAO Kai3
（1.Finance Department，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.Hebei Chemical and Pharmaceutical College，Shijiazhuang Hebei 050026，China；3.College of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

This paper presents the class－centre vector based category algorithm，which is regarded as the basis of the text classification in case－based reasoning application.On the basis of the proposed algorithm，this method can be used to determine those cases＇affiliation，and as a result this can reduce the retrieval scope so as to reduce the calculation and improve the precision.We use the proposed algorithm in the traffic accident analysis and the corresponding early warning system.The experimental results and the analysis prove the feasibility of the approach，and the existing problems and further works are also discussed in the end.

artificial intelligence；natural language understanding；category；information retrieval；case－based reasoning

TP274

A

1008－1542（2012）02－0150－04

2011－11－17；責任編輯：李 穆

河北省科技支撐計劃資助項目（074572172）

劉連喜（1965－），女，河北高邑人，高級會計師，主要從事信息管理、會計理論與電算化技術等方面的研究。

高 凱副教授。E－mail：gaokao68＠163.com