張志強(qiáng) 王偉鈞 楊晉浩 周曉清 鄭加林

摘 要： 在知識挖掘應(yīng)用中，行業(yè)領(lǐng)域數(shù)據(jù)識別是知識挖掘的重要過程。對大量的行業(yè)領(lǐng)域數(shù)據(jù)進(jìn)行數(shù)據(jù)識別需要借助領(lǐng)域詞庫標(biāo)識樹來完成，而影響數(shù)據(jù)識別準(zhǔn)確率的重要因素是領(lǐng)域詞庫標(biāo)識樹構(gòu)建的正確性。領(lǐng)域詞庫數(shù)據(jù)量一般很大，以其構(gòu)建的領(lǐng)域詞庫標(biāo)識樹結(jié)構(gòu)復(fù)雜，在復(fù)雜結(jié)構(gòu)的標(biāo)識樹中通過已有的檢測方法判斷其正確性往往很困難。為了解決這個(gè)問題，提出一種詞庫標(biāo)識樹的正確性檢測算法。該算法通過構(gòu)建詞庫特征向量空間矩陣，計(jì)算樹節(jié)點(diǎn)的相關(guān)性系數(shù)來自動(dòng)檢測樹節(jié)點(diǎn)構(gòu)建的正確性，同時(shí)可以根據(jù)判定閾值來確定正確性判定范圍。實(shí)驗(yàn)結(jié)果表明，無論樹結(jié)構(gòu)如何復(fù)雜，該算法都能高效準(zhǔn)確地實(shí)現(xiàn)標(biāo)識樹的正確性檢測和發(fā)現(xiàn)錯(cuò)誤。

關(guān)鍵詞： 詞庫標(biāo)識樹； 正確性檢測； 特征向量空間矩陣； 相關(guān)性系數(shù)； 知識挖掘； 數(shù)據(jù)識別

中圖分類號： TN911.23?34； TP391.1 文獻(xiàn)標(biāo)識碼： 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 引 言

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

1 檢測算法的目標(biāo)

檢測算法的目標(biāo)是通過領(lǐng)域詞庫構(gòu)建詞庫標(biāo)識樹，并對標(biāo)識樹進(jìn)行高效準(zhǔn)確地正確性檢測，然后根據(jù)檢測結(jié)果發(fā)現(xiàn)，樹中有識別歧義的樹節(jié)點(diǎn)信息，根據(jù)錯(cuò)誤信息改進(jìn)前期的分詞算法。檢測算法在數(shù)據(jù)識別處理流程中的階段如圖1所示。

2 檢測算法的設(shè)計(jì)

本文算法進(jìn)行檢測的關(guān)鍵是構(gòu)建詞庫特征向量空間矩陣，通過該矩陣獲得標(biāo)識樹中任何樹節(jié)點(diǎn)的詞匯特征向量空間，然后利用詞匯特征向量空間計(jì)算標(biāo)識樹中各節(jié)點(diǎn)間的相關(guān)性系數(shù)。

2.1 詞庫特征向量空間矩陣的構(gòu)建

為了獲取詞庫中詞匯的相互關(guān)聯(lián)信息，需要構(gòu)建詞庫中每個(gè)詞匯的特征向量空間，將所有詞匯特征向量空間組合在一起構(gòu)建詞庫特征向量空間矩陣。詞匯特征向量空間需要由詞庫標(biāo)識樹來構(gòu)建。構(gòu)建詞庫標(biāo)識樹的策略是：首先自定義根節(jié)點(diǎn)；然后將詞庫中的所有詞匯類別作為樹的非葉子節(jié)點(diǎn)、所有詞匯作為葉子節(jié)點(diǎn)構(gòu)建標(biāo)識樹。以本文實(shí)驗(yàn)采用的政府采購信息樣本數(shù)據(jù)為依據(jù)，構(gòu)建的詞庫標(biāo)識樹結(jié)構(gòu)如圖2所示。

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

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

2.2 矩陣存儲的處理

當(dāng)[n]值很大時(shí)，矩陣[T]在存儲數(shù)據(jù)表時(shí)會出現(xiàn)“[n] >系統(tǒng)數(shù)據(jù)表列數(shù)最大值”錯(cuò)誤，采用多表關(guān)聯(lián)方式解決相關(guān)問題。本文構(gòu)建了詞匯表、詞匯類別表、詞匯向量空間表，3個(gè)表的ER圖設(shè)計(jì)如圖3所示。

通過3個(gè)表的關(guān)聯(lián)，矩陣[T]從3個(gè)表中還原。不管矩陣[T]的規(guī)模有多大，矩陣[T]都可以存入數(shù)據(jù)庫。

2.3 樹節(jié)點(diǎn)相關(guān)性系數(shù)計(jì)算

標(biāo)識樹的同層非葉子節(jié)點(diǎn)間相關(guān)性系數(shù)是判定數(shù)據(jù)識別歧義的重要標(biāo)準(zhǔn)，樹節(jié)點(diǎn)[nodei]與[nodej]間相關(guān)性系數(shù)[ρ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）

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

2.4 算法的實(shí)現(xiàn)

算法實(shí)現(xiàn)的步驟如下：

1） 設(shè)定檢測標(biāo)識樹的層次數(shù)[t]，其作為參數(shù)傳遞到算法中處理。

2） 根據(jù)數(shù)據(jù)庫中已有的領(lǐng)域詞庫構(gòu)建詞庫標(biāo)識樹。

3） 根據(jù)詞庫標(biāo)識樹構(gòu)建詞庫特征向量空間矩陣[T]，并存入數(shù)據(jù)庫中。

4） 構(gòu)建樹的第[i]層（根層忽略）的同層所有非葉子節(jié)點(diǎn)集合。

5） 從節(jié)點(diǎn)集合中任意選擇兩個(gè)不同節(jié)點(diǎn)，從矩陣[T]獲取節(jié)點(diǎn)的特征向量空間，計(jì)算該節(jié)點(diǎn)對的相關(guān)性系數(shù)[ρi，j]，并存入數(shù)據(jù)庫中，用于數(shù)據(jù)分析。

6） 將[i]的范圍設(shè)定為1～[t]，循環(huán)從步驟4）開始執(zhí)行，直到[i]范圍執(zhí)行結(jié)束。

3 算法實(shí)驗(yàn)

算法采用Java編程實(shí)現(xiàn)，算法測試的樣本數(shù)據(jù)基于政府采購標(biāo)準(zhǔn)信息數(shù)據(jù)，并利用前期的分詞算法對這些行業(yè)領(lǐng)域標(biāo)準(zhǔn)進(jìn)行分詞，構(gòu)建了領(lǐng)域詞庫并存儲在數(shù)據(jù)庫中。測試的樣本數(shù)據(jù)量如表1所示。

3.1 實(shí)驗(yàn)結(jié)果及分析

利用檢測算法對樣本數(shù)據(jù)詞庫構(gòu)建的詞庫標(biāo)識樹進(jìn)行檢測，檢測層次參數(shù)設(shè)為4（表示檢測從第1層到第4層的樹節(jié)點(diǎn)信息），根所在的層忽略不計(jì)，運(yùn)行的測試結(jié)果如表2所示。

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

3.2 判定閾值的下界設(shè)定

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

4 結(jié) 語

標(biāo)識樹的檢測是數(shù)據(jù)識別過程中非常重要的處理流程。本文提出的標(biāo)識樹正確性檢測算法，其通過詞庫特征向量空間矩陣計(jì)算樹中同層非葉子節(jié)點(diǎn)的相關(guān)性系數(shù)來判斷和發(fā)現(xiàn)標(biāo)識樹中存在識別歧義的錯(cuò)誤信息。實(shí)驗(yàn)結(jié)果表明，不管樹結(jié)構(gòu)如何復(fù)雜，算法都能高效準(zhǔn)確地檢測和發(fā)現(xiàn)錯(cuò)誤。

參考文獻(xiàn)

[1] 王東波，朱丹浩.面向漢語句法功能分布知識庫的詞匯類別知識挖掘研究[J].現(xiàn)代圖書情報(bào)技術(shù)，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] 陳曉寧.一種基于詞匯樹結(jié)構(gòu)的圖像檢索方法研究[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] 鐘將，劉杰.一種基于文本分類的知識樹自動(dòng)構(gòu)建方法[J].計(jì)算機(jī)應(yīng)用研究，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] 張明杰，張躍，姚天順.一種基于詞匯功能描述的樹庫構(gòu)建方法[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 王東波，朱丹浩，謝靖.面向漢語自動(dòng)句法分析的語法知識庫構(gòu)建[J].現(xiàn)代圖書情報(bào)技術(shù)，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] 鄧一貴，伍玉英.基于文本內(nèi)容的敏感詞決策樹信息過濾算法[J].計(jì)算機(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] 史林林，邱立坤，亢世勇.基于規(guī)則的依存樹庫錯(cuò)誤自動(dòng)檢測與分析[J].北京大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 楊喜權(quán)，國頔娜，胡加·托和塔森，等.基于領(lǐng)域本體的詞語相似度計(jì)算[J].計(jì)算機(jī)應(yīng)用，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] 王晉，孫涌，王璁瑋.基于領(lǐng)域本體的文本相似度算法[J].蘇州大學(xué)學(xué)報(bào)（工科版），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] 崔誠煜，冉曉旻，馮琳.基于領(lǐng)域本體的專業(yè)領(lǐng)域詞匯相似度算法[J].信息工程大學(xué)學(xué)報(bào)，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.