一種行業領域詞庫標識樹的正確性檢測算法研究

張志強 王偉鈞 楊晉浩 周曉清 鄭加林

摘 要： 在知識挖掘應用中，行業領域數據識別是知識挖掘的重要過程。對大量的行業領域數據進行數據識別需要借助領域詞庫標識樹來完成，而影響數據識別準確率的重要因素是領域詞庫標識樹構建的正確性。領域詞庫數據量一般很大，以其構建的領域詞庫標識樹結構復雜，在復雜結構的標識樹中通過已有的檢測方法判斷其正確性往往很困難。為了解決這個問題，提出一種詞庫標識樹的正確性檢測算法。該算法通過構建詞庫特征向量空間矩陣，計算樹節點的相關性系數來自動檢測樹節點構建的正確性，同時可以根據判定閾值來確定正確性判定范圍。實驗結果表明，無論樹結構如何復雜，該算法都能高效準確地實現標識樹的正確性檢測和發現錯誤。

關鍵詞： 詞庫標識樹； 正確性檢測； 特征向量空間矩陣； 相關性系數； 知識挖掘； 數據識別

中圖分類號： TN911.23?34； TP391.1 文獻標識碼： A 文章編號： 1004?373X（2018）18?0088?04

Research on correctness detection algorithm for thesaurus identification

tree in profession domain

ZHANG Zhiqiang， WANG Weijun， YANG Jinhao， ZHOU Xiaoqing， ZHENG Jialin

（School of Information Science and Engineering， Chengdu University， Chengdu 610106， China）

Abstract： In the knowledge mining application， the data recognition in profession domain is an important process of knowledge mining. The identification of massive profession domain data is accomplished by means of the identification tree of the domain thesaurus. An important factor of affecting the accuracy rate of data recognition is the construction correctness of the identification tree of the domain thesaurus. As the data quantity of the domain thesaurus is generally large， the constructed identification tree of the domain thesaurus has a complex structure， which makes it difficult to judge the correctness of the identification tree with a complex structure by using the existing detection methods. A correctness detection algorithm for the thesaurus identification tree is proposed to solve the above problem. In the algorithm， the correlation coefficient of tree nodes is calculated to automatically detect the construction correctness of tree nodes by building the space matrix of thesaurus feature vectors， and the judgment range of correctness is determined according to the decision threshold. The experimental results show that， no matter how complex the tree structure is， the algorithm can effectively and accurately implement the correctness detection of the identification tree and find errors.

Keywords： thesaurus identification tree； correctness detection； feature vector space matrix； correlation coefficient； knowledge mining； data identification

0 引 言

在知識挖掘中，利用知識樹進行知識挖掘和提取是目前研究的方向，其可應用于行為挖掘和圖像檢索[1?2]等。在樹的構建方面，目前有如下策略：基于文本聚類的構建方法[3]、基于文本詞匯功能描述的構建方法[4]、基于漢語自動句法分析和語言知識庫的構建方法[5]、基于文本敏感信息過濾算法的構建方法[6]等。針對行業領域數據的知識挖掘應用，利用行業領域標準對大量的行業領域數據進行數據識別也是知識挖掘的重要過程。數據識別過程中，首先需要利用分詞算法對行業領域標準文檔進行分詞并建立領域詞庫；然后根據領域詞庫中的所有詞匯按照類別構建領域詞庫標識樹；最后根據數據識別算法利用詞庫標識樹對行業領域數據進行自動識別。顯然，構建無識別歧義的正確標識樹是數據識別高準確率的保證，同時，標識樹的正確性又與分詞的準確性密切關聯。為了能夠檢測和發現樹的錯誤信息，目前已提出的檢測方法有：基于規則的方法檢測[7]、基于計算語句相似度的檢測方法[8]、基于文本相似度計算的檢測方法[9]、基于詞匯相似度計算的檢測方法[10]等。領域詞庫數據量一般比較大，通過詞庫構建的標識樹結構復雜，利用已有的方法來判斷標識樹的正確性一般比較困難。為了能夠高效準確地進行標識樹的正確性檢測，本文提出一種基于樹節點間相關性系數計算策略的判定方式來實現標識樹正確性檢測算法。在算法中利用詞庫特征向量空間矩陣計算樹節點間相關性系數，來判斷樹節點間的相似度，從而有效地進行樹的正確性檢測，發現存在識別歧義的錯誤信息。實驗結果表明，該算法能夠高效準確地檢測并發現樹的錯誤信息。

1 檢測算法的目標

檢測算法的目標是通過領域詞庫構建詞庫標識樹，并對標識樹進行高效準確地正確性檢測，然后根據檢測結果發現，樹中有識別歧義的樹節點信息，根據錯誤信息改進前期的分詞算法。檢測算法在數據識別處理流程中的階段如圖1所示。

2 檢測算法的設計

本文算法進行檢測的關鍵是構建詞庫特征向量空間矩陣，通過該矩陣獲得標識樹中任何樹節點的詞匯特征向量空間，然后利用詞匯特征向量空間計算標識樹中各節點間的相關性系數。

2.1 詞庫特征向量空間矩陣的構建

為了獲取詞庫中詞匯的相互關聯信息，需要構建詞庫中每個詞匯的特征向量空間，將所有詞匯特征向量空間組合在一起構建詞庫特征向量空間矩陣。詞匯特征向量空間需要由詞庫標識樹來構建。構建詞庫標識樹的策略是：首先自定義根節點；然后將詞庫中的所有詞匯類別作為樹的非葉子節點、所有詞匯作為葉子節點構建標識樹。以本文實驗采用的政府采購信息樣本數據為依據，構建的詞庫標識樹結構如圖2所示。

在圖2中，“服務業”一詞的類別數據在詞庫中為“A01”，為其構建為一個非葉子節點、“交通運輸”一詞的類別數據在詞庫中為“A0101”，為其構建一個非葉子節點，詞匯構建為葉子節點；依次類推，將詞庫中所有的詞匯數據和詞匯類別數據構建標識樹。標識樹的節點層次體現了不同詞匯的類別歸屬關系，如“交通運輸”歸屬于“服務業”。這種歸屬關系也是后期數據識別的重要判定依據。根據詞庫標識樹構建詞庫特征向量空間矩陣[T（m×n）]。其中[m]=[{詞庫中的所有詞匯集合}]，[n={詞庫中所有詞匯類別數據集合}]。當某個詞匯是標識樹的葉子節點時，如圖2中的“交通運輸”，其在樹中祖先節點集合為{“[A]”，“[A01]”，“[A0101]”}，在矩陣[T]中，將該詞匯所在行的對應列“[A]”，列“[A01]”，列“[A0101]”的值分別置1，其余列的值全部置0。根據這種策略，構建的矩陣[T]定義為：

式中：word1，word2等是詞庫中的所有詞匯；A，A01，A0101等是詞庫中詞匯所屬類別數據。從矩陣[T]可見，詞匯“交通運輸”的特征向量空間[S′]（“交通運輸”）={1，1，1，0，0，…}，其為[T]中對應行向量值。同理，根據矩陣[T]，詞匯類別數據“[A01]”的特征向量空間[S]（“[A01]”）={1，0，1，1，…}，其為[T]中對應列向量值。根據矩陣[T]，可以獲取詞庫中任意詞匯和詞匯類別數據的特征向量空間。

2.2 矩陣存儲的處理

當[n]值很大時，矩陣[T]在存儲數據表時會出現“[n] >系統數據表列數最大值”錯誤，采用多表關聯方式解決相關問題。本文構建了詞匯表、詞匯類別表、詞匯向量空間表，3個表的ER圖設計如圖3所示。

通過3個表的關聯，矩陣[T]從3個表中還原。不管矩陣[T]的規模有多大，矩陣[T]都可以存入數據庫。

2.3 樹節點相關性系數計算

標識樹的同層非葉子節點間相關性系數是判定數據識別歧義的重要標準，樹節點[nodei]與[nodej]間相關性系數[ρi，j]定義為：

[ρi，j=Ai·Ajqi×qj，Ai=S（nodei），Aj=S（nodej）， 1≤i≤n，1≤j≤nAi·Aj=k=1mAi[k]×Aj[k]，qi=k=1mAi[k]×Aj[k]， qj=k=1mAj[k]×Aj[k]] （2）

式中，樹節點[nodei]和[nodej]的相關性系數[ρi，j]的值與節點的特征向量空間[S]密切聯系。樹中同層非葉子節點[nodei]和[nodej]的相關性系數[ρi，j]表示從根節點到節點[nodei]之間構成的分支樹所屬詞匯集合與根節點到節點[nodej]之間構成的分支樹所屬詞匯集合的相似度。如果標識樹中不同分子樹所屬詞匯集合的相似度較高，會出現識別歧義問題。當[ρi，j]=0，表示兩個分支樹所屬詞匯集合完全不相同，其相似度為0，從理論上說這一種最理想的情況；當[ρi，j]=1，表示兩個分支樹所屬詞匯集合完全相同，其相似度為1，從理論上說這是一種最壞的情況；當[ρi，j>a]，表示兩個分支樹所屬詞匯集合的相似度大于[a]，這里[a]為判定閾值，說明節點所屬詞匯集合存在識別歧義問題。

2.4 算法的實現

算法實現的步驟如下：

1） 設定檢測標識樹的層次數[t]，其作為參數傳遞到算法中處理。

2） 根據數據庫中已有的領域詞庫構建詞庫標識樹。

3） 根據詞庫標識樹構建詞庫特征向量空間矩陣[T]，并存入數據庫中。

4） 構建樹的第[i]層（根層忽略）的同層所有非葉子節點集合。

5） 從節點集合中任意選擇兩個不同節點，從矩陣[T]獲取節點的特征向量空間，計算該節點對的相關性系數[ρi，j]，并存入數據庫中，用于數據分析。

6） 將[i]的范圍設定為1～[t]，循環從步驟4）開始執行，直到[i]范圍執行結束。

3 算法實驗

算法采用Java編程實現，算法測試的樣本數據基于政府采購標準信息數據，并利用前期的分詞算法對這些行業領域標準進行分詞，構建了領域詞庫并存儲在數據庫中。測試的樣本數據量如表1所示。

3.1 實驗結果及分析

利用檢測算法對樣本數據詞庫構建的詞庫標識樹進行檢測，檢測層次參數設為4（表示檢測從第1層到第4層的樹節點信息），根所在的層忽略不計，運行的測試結果如表2所示。

在表2中，相關性系數為1的節點對的數據記錄條數為16，說明標識樹中有16個節點對的分支樹所屬詞匯集合的相似度為1。例如，算法檢測出“A031103”和“A170203”兩個同層樹節點對的相關性系數為1，通過對標識樹的分析發現，兩個節點的分支樹所屬詞匯集合均為{“纖維”}，其在標識樹中如圖4所示。在圖4中，這兩個樹節點的特征向量空間相同，即：[S]（“A031103”） =[S]（“A170203”），從而使得相關性系數[ρi，j=1]，顯然在后期識別“纖維”詞匯時會出現識別歧義的問題，其他15個節點對也有類似的問題。對于其他相關性系數值范圍的節點對，如圖5中“A031016”和“C220203”兩個同層樹節點對的相關性系數為0.707 11；圖6中“C0205”和“C1005”兩個同層樹節點對的相關性系數為0.408 25。從圖5和圖6可知，當同層樹節點對的相關性系數[ρi，j>a]時，表示相應的兩個節點在標識樹中的所屬詞匯集合中有相同詞匯數據，其可能影響后期數據識別的準確度。從實驗結果分析可以看出，不管標識樹的結構如何復雜，算法都能準確高效地檢測標識樹的正確性、發現錯誤。

3.2 判定閾值的下界設定

確定判定閾值[a]的下界對數據分析非常重要。本文以相關性系數值為x軸，以數據記錄條數為y軸，將相關性系數值為0～0.1范圍的數據量作為在x軸0.1刻度的數據采集，相關性系數值為0.1～0.2范圍的數據量作為在x軸0.2刻度的數據采集、依次類推，數據變化曲線如圖7所示。從圖7可見，當[0.3≤ρi，j≤1]時，數據量的變化幅度不大，將判定閾值[a]的下界設定為0.3時較為合適。有時確定判定閾值還需要行業領域數據特點、識別要求、詞性、詞頻等因素綜合考慮。

4 結 語

標識樹的檢測是數據識別過程中非常重要的處理流程。本文提出的標識樹正確性檢測算法，其通過詞庫特征向量空間矩陣計算樹中同層非葉子節點的相關性系數來判斷和發現標識樹中存在識別歧義的錯誤信息。實驗結果表明，不管樹結構如何復雜，算法都能高效準確地檢測和發現錯誤。

參考文獻

[1] 王東波，朱丹浩.面向漢語句法功能分布知識庫的詞匯類別知識挖掘研究[J].現代圖書情報技術，2013，29（3）：33?37.

WANG Dongbo， ZHU Danhao. Research of mining the word category knowledge for Chinese syntactic function distribution knowledge base [J]. New technology of library and information service， 2013， 29（3）： 33?37.

[2] 陳曉寧.一種基于詞匯樹結構的圖像檢索方法研究[J].電子世界，2013（9）：172?173.

CHEN Xiaoning. A method of image retrieval based on lexical tree structure [J]. Electronics world， 2013（9）： 172?173.

[3] 鐘將，劉杰.一種基于文本分類的知識樹自動構建方法[J].計算機應用研究，2010，27（2）：475?478.

ZHONG Jiang， LIU Jie. Automatic construction of knowledge tree based on text clustering [J]. Application research of computers， 2010， 27（2）： 475?478.

[4] 張明杰，張躍，姚天順.一種基于詞匯功能描述的樹庫構建方法[J].東北大學學報（自然科學版），2000，21（3）：263?265.

ZHANG Mingjie， ZHANG Yue， YAO Tianshun. Constructing tree?bank based on lexical functional description [J]. Journal of Northeastern University （Natural science）， 2000， 21（3）： 263?265.

[5] 王東波，朱丹浩，謝靖.面向漢語自動句法分析的語法知識庫構建[J].現代圖書情報技術，2011，27（4）：42?47.

WANG Dongbo， ZHU Danhao， XIE Jing. Constructing the grammar knowledge database orienting Chinese automatic sentence analysis [J]. New technology of library and information service， 2011， 27（4）： 42?47.

[6] 鄧一貴，伍玉英.基于文本內容的敏感詞決策樹信息過濾算法[J].計算機工程，2014，40（9）：300?304.

DENG Yigui， WU Yuying. Information filtering algorithm of text content?based sensitive words decision tree [J]. Computer engineering， 2014， 40（9）： 300?304.

[7] 史林林，邱立坤，亢世勇.基于規則的依存樹庫錯誤自動檢測與分析[J].北京大學學報（自然科學版），2016，52（1）：58?64.

SHI Linlin， QIU Likun， KANG Shiyong. Rule?based detection and analysis of annotation errors in dependency Treebank [J]. Acta Scientiarum Naturalium Universitatis Pekinensis， 2016， 52（1）： 58?64.

[8] 楊喜權，國頔娜，胡加·托和塔森，等.基于領域本體的詞語相似度計算[J].計算機應用，2009，29（z1）：164?166.

YANG Xiquan， GUO Dina， TOHTASEN Hoja， et al. Word similarity computation based on domain ontology [J]. Journal of computer applications， 2009， 29（S1）： 164?166.

[9] 王晉，孫涌，王璁瑋.基于領域本體的文本相似度算法[J].蘇州大學學報（工科版），2011，31（3）：13?17.

WANG Jin， SUN Yong， WANG Congwei. Text similarity computing based on domain ontology [J]. Journal of Soochow University （Engineering science edition）， 2011， 31（3）： 13?17.

[10] 崔誠煜，冉曉旻，馮琳.基于領域本體的專業領域詞匯相似度算法[J].信息工程大學學報，2014，15（1）：68?73.

CUI Chengyu， RAN Xiaomin， FENG Lin. Calculation of field term similarity based on domain ontology [J]. Journal of Information Engineering University， 2014， 15（1）： 68?73.