基于分類詞典的文本相似性度量方法

李海林，鄒金串

(1.華僑大學(xué) 信息管理系，福建 泉州 362021； 2.華僑大學(xué) 現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心，福建 廈門 361021)

基于分類詞典的文本相似性度量方法

李海林1，鄒金串2

(1.華僑大學(xué) 信息管理系，福建 泉州 362021； 2.華僑大學(xué) 現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心，福建 廈門 361021)

針對現(xiàn)有基于語義知識規(guī)則分析的文本相似性度量方法存在時(shí)間復(fù)雜度高的局限性，提出基于分類詞典的文本相似性度量方法。利用漢語詞法分析系統(tǒng)ICTCLAS對文本分詞，運(yùn)用TF×IDF方法提取文本關(guān)鍵詞，遍歷分類詞典獲取關(guān)鍵詞編碼，通過計(jì)算文本關(guān)鍵詞編碼的近似性來衡量原始文本之間的相似度。選取基于語義知識規(guī)則和基于統(tǒng)計(jì)兩個(gè)類別的相似性度量方法作為對比方法，通過傳統(tǒng)聚類與KNN分類分別對相似性度量方法進(jìn)行效果驗(yàn)證。數(shù)值實(shí)驗(yàn)結(jié)果表明，新方法在聚類與分類實(shí)驗(yàn)中均能取得較好的實(shí)驗(yàn)結(jié)果，相較于其他基于語義分析的相似性度量方法還具有良好的時(shí)間效率。

文本挖掘；語義分析；分類詞典；關(guān)鍵詞提??；詞語編碼；相似性度量；聚類；分類

大數(shù)據(jù)時(shí)代，相似性度量方法通常作為數(shù)據(jù)挖掘任務(wù)的基礎(chǔ), 使得相應(yīng)的算法和技術(shù)能夠在復(fù)雜數(shù)據(jù)中發(fā)現(xiàn)具有潛在價(jià)值的信息與知識[1-2]，文本挖掘技術(shù)與方法通常用于處理與分析非結(jié)構(gòu)化文本數(shù)據(jù)，其中相似性度量質(zhì)量的好壞將很大程度上影響文本挖掘質(zhì)量和效率，與文本相關(guān)的數(shù)據(jù)挖掘任務(wù)結(jié)合，也廣泛存在于現(xiàn)實(shí)應(yīng)用中, 例如聚類與分類、信息檢索、機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)信息認(rèn)定[3]與人工智能等文本信息處理。

根據(jù)文獻(xiàn)[4]中提到的概念層次理論，文本相似性度量建立在句子相似性度量之上，句子相似性度量進(jìn)一步以詞語的相似性為前提。因此，詞語相似性度量結(jié)果的好壞直接影響文本相似性度量以及文本聚類、分類等后續(xù)文本挖掘任務(wù)與工作的質(zhì)量。

詞語相似度指在不同位置，詞語可以互相替換使用的程度，文本相似性度量通常分為基于語義知識規(guī)則的相似性度量和基于統(tǒng)計(jì)的相似性度量。基于語義知識規(guī)則的文本相似度計(jì)算主要建立在基于Wordnet[5-6]、MindNet[7]、FramNet[8]等語義知識庫的基礎(chǔ)上。20世紀(jì)90年代開始，涌現(xiàn)出大量基于Wordnet的語義相似度計(jì)算算法，主要針對外文長文本的語義相似度計(jì)算[9]?，F(xiàn)有基于語義分析的中文文本相似性度量方法主要依托于同義詞詞林[10]與知網(wǎng)[11]。劉群等[12]以知網(wǎng)為依托，將詞語相似性度量分為義原相似性度量、概念相似性度量和詞語相似性度量3個(gè)步驟，并提出了基于知網(wǎng)的詞語相似度計(jì)算方法(ZW_Sim)。由于該方法的適用性和有效性，部分學(xué)者在此基礎(chǔ)上對該相似度計(jì)算方法進(jìn)行改進(jìn)。林麗等[13]在基于知網(wǎng)的詞語相似度計(jì)算中引入弱義原的概念，即通過計(jì)算除區(qū)分能力弱的第一基本義原外的其他義原來計(jì)算詞語相似度，以減少計(jì)算時(shí)間和提高計(jì)算精度；王小林[14]在原始基于知網(wǎng)方法的基礎(chǔ)上，改進(jìn)不同類別義原在詞語相似度計(jì)算中所占權(quán)重的計(jì)算方法提高計(jì)算精度，通過義項(xiàng)詞性判斷降低相似性計(jì)算復(fù)雜度；張亮等[15]利用知網(wǎng)，從義項(xiàng)的主類義原、主類義原框架和義項(xiàng)特性描述三方面綜合分析詞語相似度，并從語義特征相似度和句法特征相似度兩方面來描述詞語相似度；田久樂等[16]提出基于同義詞詞林的詞語相似度計(jì)算方法(CL_Sim)，并通過人工測試、非人工測試以及與ZW_Sim方法進(jìn)行比較，證明了方法的可行性；徐慶等[17]在此基礎(chǔ)上對詞語相似度計(jì)算公式進(jìn)行改進(jìn)，并將該方法應(yīng)用于中文實(shí)體關(guān)系抽取，取得了較好的實(shí)驗(yàn)結(jié)果；鄭紅艷等[18]將詞林與TF×IDF方法相結(jié)合，過濾同義詞并對詞語權(quán)重賦值進(jìn)行文本特征提取，新的方法具有更好的特征提取結(jié)果。各位學(xué)者將基于知網(wǎng)與詞林的相似性度量方法在參數(shù)與時(shí)間復(fù)雜度方面不斷完善，使方法的準(zhǔn)確性與時(shí)間效率都一定程度上有所提高。基于語義知識庫的相似性度量方法均需要對語義知識庫多次遍歷，各位學(xué)者雖不同程度提高了方法的時(shí)間效率，但時(shí)間復(fù)雜度高的問題依然存在。

蘇新春教授編寫的《現(xiàn)代漢語分類詞典》[19]與《同義詞詞林》在結(jié)構(gòu)上具有相似性，但《現(xiàn)代漢語分類詞典》對詞語分類更細(xì)，詞語間相似度只需通過兩個(gè)詞語編碼進(jìn)行計(jì)算比較，相較于ZW_Sim方法，不需要對詞語相似度進(jìn)行分層計(jì)算，時(shí)間復(fù)雜度大大降低?；诰嚯x的語義相似度計(jì)算主要包括語義重合度(共同祖先節(jié)點(diǎn)數(shù))、語義深度、語義密度、語義距離等4個(gè)方面的度量。多級分類體系使得基于分類詞典的相似性度量結(jié)果可以直接反映兩個(gè)詞語在語義樹中的重合度、深度與距離。在此基礎(chǔ)上，本文提出一種基于現(xiàn)代漢語分類詞典的文本相似性度量方法(Similarity measure based on Cidian, CD_Sim)。CD_Sim方法通過中科院研制出的漢語詞法分析系統(tǒng)對待分析文檔進(jìn)行分詞等一系列基本處理，統(tǒng)計(jì)詞語與文檔間的詞頻矩陣，結(jié)合TF×IDF算法構(gòu)建詞語文檔的向量空間模型[20]，對向量空間模型進(jìn)行標(biāo)準(zhǔn)化處理、排序等操作實(shí)現(xiàn)對文檔的特征提取。通過AP聚類[21]、Kmeans聚類[22]、譜聚類[23]3種聚類算法以及KNN分類[24]方法對方法計(jì)算結(jié)果進(jìn)行檢驗(yàn)分析。方法理論簡單、易于應(yīng)用，對降低同義詞、同類詞導(dǎo)致的誤差有一定作用，在短文本相似度量應(yīng)用中相較于基于統(tǒng)計(jì)學(xué)的方法可以降低度量誤差，相較于基于知識庫的方法簡單易行。數(shù)值實(shí)驗(yàn)結(jié)果表明，CD_Sim方法在聚類與分類實(shí)驗(yàn)中均能取得較好的實(shí)驗(yàn)結(jié)果，證明了方法的可行性與度量效果。

1 相關(guān)理論基礎(chǔ)

1.1 現(xiàn)代漢語分類詞典

我國現(xiàn)代漢語首部分類詞典是《同義詞詞林》，按照詞語的概義來對詞語進(jìn)行分類編排。但現(xiàn)在《同義詞詞林》一定程度上不能很好地反映當(dāng)前語言現(xiàn)狀。《現(xiàn)代漢語分類詞典》在吸收前人成果的基礎(chǔ)上，收錄了8.3萬條通用性詞語，較《同義詞詞林》新增常用詞2.9萬條，按五級語義層編排，包含9個(gè)一級類，62個(gè)二級類，508個(gè)三級類，2 057個(gè)四級類，12 659個(gè)五級類。

《現(xiàn)代漢語分類詞典》用5層編碼代表分類詞典的5層結(jié)構(gòu)，例如“B03Cc04”是“灰漿”和“砂漿”的編碼，示例編碼中各層編碼意義如表1，表示“灰漿”和“砂漿”均是“具體物”類別下“材料”類別中“建筑材料”范疇內(nèi)“水泥石灰瀝青”小類中的“灰漿”類別。若兩個(gè)詞語各級編碼均相同，則二者是同義詞，相似度為1。

表1 分類詞典編碼方式示例

1.2 向量空間模型

向量空間模型是當(dāng)前使用較多的文本表示方法，向量空間矩陣為待分析文本樣本詞語-文檔權(quán)重矩陣。假設(shè)待分析樣本D中有n個(gè)文檔dj(j=1,2,…,n)，用m個(gè)詞語ti(i=1,2,…,m)在文檔中出現(xiàn)的頻數(shù)組成的向量對一篇文檔進(jìn)行向量表示，根據(jù)詞語在該文檔中出現(xiàn)的概率及在整個(gè)樣本中出現(xiàn)的概率對該特征詞的重要性賦值權(quán)重wij，則樣本D表示為

式中：wij表示第i個(gè)詞語在第j篇文檔中重要程度的權(quán)值。

詞語權(quán)重的計(jì)算方法有多種，經(jīng)典權(quán)重計(jì)算方法如TF×IDF算法：

式中：TFij指特征詞ti在文檔dj中出現(xiàn)的次數(shù)pij占文檔dj中總詞數(shù)pj的比重：

IDFi為逆文檔頻率，計(jì)算公式為

式中：N為樣本中文檔總數(shù)，ni為樣本中出現(xiàn)過特征詞ti的文檔數(shù)。

2 文本相似度計(jì)算

針對目前基于語義知識規(guī)則的文本相似性度量方法存在計(jì)算過程中多次遍歷語義知識庫導(dǎo)致方法時(shí)間復(fù)雜度高的局限性，提出了基于現(xiàn)代漢語分類詞典的文本相似性度量方法(Similarity measure based on Cidian, CD_Sim)。方法側(cè)重于詞語相似度量方法的改進(jìn)，最終應(yīng)用于文本相似度量，且度量方法較基于統(tǒng)計(jì)學(xué)的方法可以一定程度降低同義詞、同類詞導(dǎo)致的誤差，故方法效果通過文本相似度量結(jié)果進(jìn)行對比衡量。方法以《現(xiàn)代漢語分類詞典》作為語義知識庫，以基于TF×IDF方法的向量空間模型作為文本關(guān)鍵詞提取依據(jù)，文本相似性度量過程包括詞語編碼獲取、詞語相似度計(jì)算和文本相似度計(jì)算3個(gè)步驟。

2.1 詞語相似度計(jì)算

基于語義知識庫的詞語相似度通常通過計(jì)算義原相似度(ZW_Sim方法)或者詞語編碼相似度(CL_Sim方法)來計(jì)算。CD_Sim方法通過遍歷分類詞典，在分類詞典中搜索關(guān)鍵詞，用該關(guān)鍵詞在分類詞典中對應(yīng)的編碼替換關(guān)鍵詞進(jìn)行關(guān)鍵詞相似度計(jì)算。樣本D中各文檔以關(guān)鍵詞編碼集的形式表示。

分類詞典中每一個(gè)大類均可以看做一棵語義樹，同一個(gè)節(jié)點(diǎn)下的葉子節(jié)點(diǎn)為同義詞，且同義詞編碼相同。通常詞語相似性通過其在語義樹中的位置進(jìn)行度量計(jì)算，包括語義密度、語義深度、語義重合度、語義距離四方面衡量。分類詞典對所有詞語均采用5級分類，即所有詞語語義深度相同，語義重合度與語義距離可通過公式計(jì)算互換(見式(8))，故可僅取其中一種衡量方式進(jìn)行計(jì)算(涉及時(shí)間復(fù)雜度，語義密度暫不考慮)。

定義關(guān)鍵詞A的編碼為“a1a2a3a4a5”，關(guān)鍵詞B的編碼為“b1b2b3b4b5”，兩關(guān)鍵詞語義重合度計(jì)算公式：

i=1時(shí)，

i>1時(shí)，

任意兩個(gè)編碼(假設(shè)兩編碼前三位相同，后兩位不同)的語義重合度與語義距離在編碼中可表示為式(8)形式：

則根據(jù)a1?b1,a2?b2,a3?b3前三對編碼位相同，語義重合度(即相同父節(jié)點(diǎn)數(shù))記為3，語義距離(即從末位編碼開始向上遍歷編碼位，經(jīng)過第一共同編碼位再到另一編碼末位編碼所經(jīng)過的不同編碼位的路徑數(shù))表示為a5→a4→b4→b5，記為3。根據(jù)語義重合度和語義距離的概念與計(jì)算規(guī)則，通過換算，得到任意兩編碼語義距離公式為

根據(jù)編碼語義重合度和語義距離的計(jì)算公式，列出3個(gè)編碼，分別求兩兩編碼的語義重合度和語義距離，驗(yàn)證計(jì)算公式的正確性與可行性。 二者換算示例如表2。

表2語義重合度與語義距離換算示例

Table2Exampleofconversionbetweencoincidenceanddistanceofsemantic

編碼深度重合度/距離B03Cc04B03Dc03C02Cb01B03Cc0455/02/50/9B03Dc0352/55/00/9C02Cb0150/90/95/0

考慮到語義重合度與語義距離可互相換算，CD_Sim方法中詞語相似度均采用語義重合度進(jìn)行計(jì)算，將語義重合度標(biāo)準(zhǔn)化公式：

將關(guān)鍵詞轉(zhuǎn)化為編碼可以更加直觀表示關(guān)鍵詞在詞典中所屬類別，在關(guān)鍵詞相似度計(jì)算過程中直接通過編碼計(jì)算，不需要多次訪問語義知識庫，提高了計(jì)算的時(shí)間效率。

2.2 相似度計(jì)算

文本相似度計(jì)算建立在詞語相似性度量之上，每個(gè)關(guān)鍵詞與對比文檔中關(guān)鍵詞的距離取該關(guān)鍵詞與對比文檔中所有關(guān)鍵詞相似度的最大值。設(shè)文檔d1(t1,t2,…,tp)(p=1,2,…,x)有x個(gè)關(guān)鍵詞，文檔d2(t1,t2,…,tq)(q=1,2,…,y)有y個(gè)關(guān)鍵詞，計(jì)算d1與d2中所有關(guān)鍵詞的相似度矩陣

式中：spq表示文檔d1中的第p個(gè)關(guān)鍵詞與文檔d2中的第q個(gè)關(guān)鍵詞的相似度。根據(jù)兩文本關(guān)鍵詞相似度矩陣可求文本相似度為

關(guān)鍵詞與比較文本關(guān)鍵詞相似度取該關(guān)鍵詞與比較文本所有關(guān)鍵詞相似度最大值，即對關(guān)鍵詞相似度矩陣每行每列均取最大值，平均值即為兩文本相似度。

基于現(xiàn)代漢語分類詞典的文本相似性度量算法Z=CD_Sim(D):

輸入待分析樣本D；

輸出樣本D中所有文本間相似度集合Z。

1)對樣本D中所有文檔進(jìn)行分詞、過濾停用詞處理；

2)對處理后的結(jié)果構(gòu)建詞語-文檔頻數(shù)矩陣，并結(jié)合TF×IDF方法構(gòu)建樣本的向量空間模型D′；

3)根據(jù)向量空間模型D′對每篇文檔按照一定的規(guī)則進(jìn)行關(guān)鍵詞提??；

4)fori=1:size(D,1)-1

①forj=i+1:size(D,1)

a)根據(jù)式(10)計(jì)算文檔i和文檔j中所有關(guān)鍵詞相似度，并按式(11)將計(jì)算結(jié)果存入相似度矩陣Sim；

b)將相似度矩陣Sim按式(12)進(jìn)行計(jì)算，得到文檔i和文檔j的相似度SIM(di,dj)；

②End

5)End

6)得出樣本D中所有文本間相似度集合Z。

根據(jù)方法介紹，CD_Sim方法與CL_Sim方法時(shí)間復(fù)雜度均為O(n2)，ZW_Sim方法時(shí)間復(fù)雜度為O3(n2)。

3 仿真實(shí)驗(yàn)

為檢驗(yàn)CD_Sim方法的結(jié)果在應(yīng)用中的準(zhǔn)確性與時(shí)間效率，從搜狗分類語料庫[25]中隨機(jī)選擇5類數(shù)據(jù)作為實(shí)驗(yàn)樣本，采用中科院分詞軟件對樣本進(jìn)行預(yù)處理，通過TF×IDF方法對處理結(jié)果進(jìn)行關(guān)鍵詞提取，選擇基于語義知識規(guī)則和基于統(tǒng)計(jì)兩類詞語相似性度量方法作為對比方法，用聚類與分類兩種方法對相似性度量結(jié)果進(jìn)行檢驗(yàn)。文中文本相似性度量方法仿真實(shí)驗(yàn)對每篇文檔取詞語權(quán)值排序前15位詞語作為文本關(guān)鍵詞進(jìn)行數(shù)值實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)語料數(shù)據(jù)選自搜狗實(shí)驗(yàn)室提供的搜狗分類語料庫，該語料庫包含了環(huán)境、計(jì)算機(jī)、交通、教育、經(jīng)濟(jì)、軍事、體育、醫(yī)藥、藝術(shù)和政治10個(gè)類別文本文檔。

數(shù)值實(shí)驗(yàn)選取了環(huán)境、交通、政治、教育、體育5個(gè)類別，每個(gè)類別隨機(jī)選取20個(gè)文本文檔共100個(gè)文本文檔進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中通過TF_IDF特征選擇方法在100個(gè)文本中分別選擇15個(gè)關(guān)鍵詞進(jìn)行相似性度量，其中，由于基于統(tǒng)計(jì)方法的特殊性，該類方法采用整個(gè)詞語-文檔權(quán)重矩陣進(jìn)行相似度計(jì)算。

實(shí)驗(yàn)選擇基于LSA的文本相似性度量方法、基于詞林的文本相似性度量方法和基于知網(wǎng)的語義相似性度量方法作為對比方法，分別采用AP聚類、Kmeans聚類、譜聚類以及KNN分類對相似性度量結(jié)果進(jìn)行檢驗(yàn)。

3.2 聚類分析

相似性度量結(jié)果的好壞直接影響文本聚類算法的精度，在已知文檔類別的樣本中，聚類精度可以反過來檢驗(yàn)文本相似性度量結(jié)果的好壞。比較經(jīng)典的基于距離矩陣的聚類算法有Kmeans，AP聚類及后來發(fā)展起來的譜聚類算法等。Kmeans與譜聚類算法均是給定聚類數(shù)目的聚類算法，時(shí)間復(fù)雜度低，聚類準(zhǔn)確度高；在聚類數(shù)目未知的情況下，上述兩種方法聚類結(jié)果會產(chǎn)生較大的偏差。AP聚類沒有事先給定聚類數(shù)目，根據(jù)數(shù)據(jù)自身的特性進(jìn)行聚類，聚類結(jié)果與聚類對象特征更加吻合。將相似性度量方法實(shí)驗(yàn)結(jié)果做聚類分析，數(shù)值實(shí)驗(yàn)結(jié)果如表3。

表3 基于聚類檢驗(yàn)方法的數(shù)據(jù)實(shí)驗(yàn)結(jié)果

數(shù)值實(shí)驗(yàn)中，聚類結(jié)果通過熵值和純凈度來度量。聚類結(jié)果熵值越低、純凈度越高，則聚類結(jié)果越好。NUM記錄了將各相似性度量方法結(jié)果進(jìn)行AP聚類所得聚類類別數(shù)。基于LSA的相似性度量算法，K值取[10,20,…,100]這10組數(shù)據(jù)值進(jìn)行實(shí)驗(yàn)，每種聚類檢驗(yàn)方法中均取熵值最小且純凈度最高的實(shí)驗(yàn)結(jié)果作為基于LSA的相似性度量算法的實(shí)驗(yàn)結(jié)果。

根據(jù)聚類實(shí)驗(yàn)結(jié)果分析，對4種相似性度量方法進(jìn)行比較。AP聚類中，CD_Sim方法聚類結(jié)果最好，但數(shù)值實(shí)驗(yàn)樣本僅包含5類文檔，CD_Sim方法聚類數(shù)目達(dá)18種，存在一定的不合理性。在譜聚類算法中，CD_Sim方法聚類檢驗(yàn)結(jié)果明顯優(yōu)于其他相似性度量方法，在4種相似性度量方法中，熵值最小，純凈度最高。Kmeans聚類算法中，CD_Sim方法實(shí)驗(yàn)結(jié)果純凈度較低、熵值較大，但結(jié)果仍優(yōu)于其他相似性度量方法。

根據(jù)實(shí)驗(yàn)結(jié)果，對3種基于語義知識規(guī)則的相似性度量方法聚類實(shí)驗(yàn)結(jié)果進(jìn)行比較分析，CD_Sim方法實(shí)驗(yàn)結(jié)果優(yōu)于CL_Sim方法和ZW_Sim方法，聚類熵值最小、純凈度最高。

3.3 分類實(shí)驗(yàn)

分類檢驗(yàn)采用KNN算法進(jìn)行分析，算法從每個(gè)類別樣本中均選取一半作為已知類別樣本，剩下一半作為實(shí)驗(yàn)集，檢驗(yàn)結(jié)果以分類準(zhǔn)確率進(jìn)行度量，分類算法K值分別取[1,2,…,10]，得出10組不同K值下的KNN分類結(jié)果并取平均值mean。采用不的相似性度量方法作為文本之間近似性度量方法, 結(jié)合KNN方法進(jìn)行數(shù)值實(shí)驗(yàn), 其實(shí)驗(yàn)結(jié)果如表4所示。

表4基于分類檢驗(yàn)方法的數(shù)據(jù)實(shí)驗(yàn)結(jié)果

Table4Experimentresultsbasedonclassifiedmethod

方法分類12345678910meanCL＿Sim0．600．580．640．640．720．680．700．620．700．780．67ZW＿Sim0．220．240．240．260．240．260．260．240．260．280．25CD＿Sim0．800．840．840．900．900．840．880．900．860．840．86LSA＿Sim0．820．840．840．840．840．840．860．760．780．800．82

數(shù)值實(shí)驗(yàn)結(jié)果表明，4種相似性度量方法中，CD_Sim方法分類實(shí)驗(yàn)結(jié)果最好，分類準(zhǔn)確率最高，LSA_Sim方法實(shí)驗(yàn)結(jié)果次之，優(yōu)于其他方法分類實(shí)驗(yàn)結(jié)果。3種基于語義知識規(guī)則的相似性度量方法分類檢驗(yàn)結(jié)果進(jìn)行比較，CD_Sim方法分類實(shí)驗(yàn)結(jié)果優(yōu)于CL_Sim方法和ZW_Sim方法，分類準(zhǔn)確度最高。

3.4 時(shí)間復(fù)雜度分析

實(shí)驗(yàn)中方法的時(shí)間復(fù)雜度是除準(zhǔn)確性外方法可行性的重要指標(biāo)，實(shí)驗(yàn)過程中對各方法100個(gè)文檔的相似度矩陣計(jì)算時(shí)間計(jì)時(shí)，結(jié)果如表5。

表5 相似性度量方法時(shí)間復(fù)雜度

根據(jù)表5實(shí)驗(yàn)數(shù)據(jù)，4種文本相似性度量方法中，基于統(tǒng)計(jì)的文本相似性度量方法時(shí)間效率較高，基于語義知識規(guī)則的文本相似性度量方法較基于統(tǒng)計(jì)的方法時(shí)間效率較低。在3種基于語義知識規(guī)則的文本相似性度量方法中，CD_Sim方法時(shí)間效率最高，CL_Sim方法時(shí)間效率次之，ZW_Sim方法時(shí)間效率最低。CD_Sim方法遍歷知識庫的次數(shù)為樣本中所有文檔關(guān)鍵詞的個(gè)數(shù)m，CL_Sim方法遍歷知識庫次數(shù)為(m+O(n2))，ZW_Sim方法遍歷知識庫次數(shù)為m。綜合文本相似性度量方法時(shí)間復(fù)雜度與遍歷知識庫的次數(shù)，CD_Sim方法在3種基于語義知識規(guī)則的文本相似性度量方法中時(shí)間效率最高。

3.5 方差分析

方法的穩(wěn)定性也是方法可行性的重要指標(biāo)。通常方差用來檢驗(yàn)數(shù)據(jù)的穩(wěn)定性，方差值越小，數(shù)據(jù)越穩(wěn)定。分別對4種方法的4個(gè)實(shí)驗(yàn)結(jié)果準(zhǔn)確率求方差，來驗(yàn)證4種相似性度量方法實(shí)驗(yàn)穩(wěn)定性：

根據(jù)表6，ZW_Sim方法實(shí)驗(yàn)結(jié)果最穩(wěn)定，CD_Sim方法次之，LSA_Sim方法方差最大，實(shí)驗(yàn)結(jié)果穩(wěn)定性相對較差。

表6 相似性度量方法方差

綜合聚類實(shí)驗(yàn)、分類實(shí)驗(yàn)、時(shí)間復(fù)雜度和穩(wěn)定性，CD_Sim方法準(zhǔn)確性優(yōu)于對比方法，穩(wěn)定性優(yōu)于大部分對比方法，時(shí)間效率優(yōu)于其他基于語義知識規(guī)則的對比方法，對比基于統(tǒng)計(jì)的方法時(shí)間效率仍有差距。

4 結(jié)束語

文本相似性計(jì)算的關(guān)鍵在于關(guān)鍵詞相似度計(jì)算，文本可以看作詞語的集合，關(guān)鍵詞根據(jù)其提取方法認(rèn)為是不同篩選程度下文本中能夠區(qū)別于其他文本的詞語，各位學(xué)者的語義方法均是在不同程度關(guān)鍵詞篩選結(jié)果的基礎(chǔ)上進(jìn)行。文章提出了基于分類詞典的文本相似性度量方法，對樣本進(jìn)行分詞、計(jì)算詞語權(quán)重、提取文本關(guān)鍵詞等一系列基本處理，定義基于關(guān)鍵詞編碼的詞語相似度計(jì)算公式，構(gòu)建文檔關(guān)鍵詞相似度矩陣，根據(jù)關(guān)鍵詞相似度矩陣計(jì)算文檔相似度。通過聚類與分類實(shí)驗(yàn)對相似性度量結(jié)果進(jìn)行驗(yàn)證，驗(yàn)證了該方法的合理性。方法采用分類詞典作為知識庫，分類詞典相較于詞林和知網(wǎng)收錄了更多的詞語，詞語編碼匹配成功概率更高，對文本相似性度量影響較?。挥?jì)算過程中僅在詞語編碼匹配一個(gè)階段訪問知識庫，提高了基于語義知識庫方法的時(shí)間效率；提出了新的詞語相似度計(jì)算方法，計(jì)算結(jié)果優(yōu)于其他基于語義知識庫的方法。由于各領(lǐng)域的發(fā)展都會不斷產(chǎn)生新的詞語，文本實(shí)驗(yàn)過程中出現(xiàn)部分分類詞典中未收錄的詞語，這部分詞語不參加文本相似度計(jì)算，一定程度上會導(dǎo)致實(shí)驗(yàn)結(jié)果的誤差；相較于基于統(tǒng)計(jì)的相似度計(jì)算方法，方法的時(shí)間效率有待提高。在保證方法準(zhǔn)確度的前提下提高時(shí)間效率是CD_Sim方法未來的研究方向。

[1]李海林,郭韌,萬校基.基于特征矩陣的多元時(shí)間序列最小距離度量方法[J].智能系統(tǒng)學(xué)報(bào), 2015, 10(3): 442-447, 2015.

LI Hailin, GUO Ren, WAN Xiaoji. A minimum distance measurement method for a multivariate time series based on the feature matrix[J]. CAAI transactions on intelligent systems, 2015, 10(3): 442-447.

[2]XU R, WUNSCH D. Survey of clustering algorithms[J]. IEEE transactions on neural networks, 2005, 16(3): 645-678.

[3]CHEN Wei, HUO Junge. Judicial determination of malicious forwarding cyber false information[J]. Journal of Chongqing university: social science edition，2017( 5) : 103-113．

[4]苗傳江.HNC(概念層次網(wǎng)絡(luò)理論)引導(dǎo)[M]. 北京:清華大學(xué)出版社，2005.

[5]PARK E K, RA D Y, JANG M G. Techniques for improving web retrieval effectiveness[J]. Information processing and management, 2005, 41(5): 1207-1223.

[6]WordNet Documentation [EB/OL]. [2010-10-27].http://wordnet.princeton.edu/wordnet/documentation/.

[7]RICHARDSON S D, DOLAN W B.VANDERWENDE L. MindNet: Acquiring and structuring semantic information from text[C]//Proceeding of the 17th International Conference on Computer Linguistics Volume 2.Stroudsburg: Association for Computational Linguistics, 1998: 1098-1102.

[8]BAKER C F, FILLMORE C J, LOWE J B. The Berkeley framenet project[C]//Proceeding of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computer Linguistics Volume 1. Stroudsburg: Association for Computational Linguistics, 1998: 86-90.

[9]翟延?xùn)|,王康平. 一種基于WordNet的短文本語義相似性算法[J]. 電子學(xué)報(bào)， 2012, 40(3): 617-620.

ZHAI Yandong, WANG Kangping. An algorithm for semantic similarity of short text based on WordNet[J]. Acta electronica sinica, 2012, 40(3): 617-620.

[10]梅家駒,竺一鳴,高蘊(yùn)琦，等.同義詞詞林[M].上海：上海辭書出版社，1996.

[11]董振東,董強(qiáng). 知網(wǎng)簡[EB/OL].http://www.keenage.com.

[12]劉群,李素建. 基于“知網(wǎng)”的詞匯語義相似度計(jì)算[C]//第三屆漢語詞匯語義學(xué)研究會論文集.臺北，中國， 2002: 59-76.

[13]林麗,薛方,任仲晟. 一種改進(jìn)的基于知網(wǎng)的詞語相似度計(jì)算方法[J].計(jì)算機(jī)應(yīng)用，2009, 29(1): 217-220.LIN Li, XUE Fang, REN Zhongsheng. Modified word similarity computation approach based on Hownet[J]. Journal of computer applications, 2009, 29(1): 217-220.

[14]王小林,楊林,王東. 基于知網(wǎng)的新詞語相似度算法研究[J]. 情報(bào)科學(xué)， 2015, 33(2): 67-71.

WANG Xiaolin, YANG Lin, WANG Dong. New word similarity algorithm research based on HowNet[J]. Information science, 2015, 33(2): 67-71.

[15]張亮,尹存燕.基于語義樹的中文詞語相似度計(jì)算與分析[J]. 中文信息學(xué)報(bào), 2007, 21(3): 99-105.

ZHANG Liang, YIN Cunyan. Chinese word similarity computing based on semantic tree[J]. Journal of Chinese information processing, 2007, 21(3): 99-105.

[16]田久樂,趙蔚. 基于同義詞詞林的詞語相似度計(jì)算方法[J]. 吉林大學(xué)學(xué)報(bào): 信息科學(xué)版，2010, 26(6): 602-608.

TIAN Jiule, ZHAO Wei. Word similarity algorithm based on Yongyici Cilin in Semantic Web adaptive learning system[J]. Journal of Jilin university: information science edition, 2010, 26(6): 602-608.

[17]徐慶,段利國.基于實(shí)體語義相似度的中文實(shí)體關(guān)系抽取[J]. 山東大學(xué)學(xué)報(bào)：工學(xué)版, 2015, 45(6): 7-14.

XU Qing, DUAN Liguo. Chinese entity relation extraction based on entity semantic similarity[J]. Journal of Shandong university： engineering science, 2015, 45(6): 7-14.

[18]鄭紅艷,張東站.基于同義詞詞林的文本特征選擇方法[J]. 廈門大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012, 5(2): 200-203.

ZHENG Hongyan， ZHANG Dongzhan. A text feature selection method based on TongYiCi CiLin[J].Journal of Xiamen University： Natural Science， 2012, 5(2): 200-203.

[19]蘇新春.現(xiàn)代漢語分類詞典[M]. 上海：商務(wù)印書館, 2013.

[20]SALTON G. The transformation analysis and retrival of information by computer[M]. Wesley Reading Massach-uetts, 1989.

[21]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[22]FORGY E W. Cluster analysis of multivariate data: efficiency versus interpretability of classifications[J]. Biometric, 1965, 21: 768-769.

[23]丁世飛,賈洪杰.基于自適應(yīng)Nystrom采樣的大數(shù)據(jù)譜聚類算法[J]. 軟件學(xué)報(bào), 2014, 25(9): 2037-2049.

DING Shifei, JIA Hongjie. Spectral clustering algorit-hm based on adaptive nystrom sampling for big data analysis[J]. Journal of software, 2014, 25(9): 2037-2049.

[24]WU Xindong, KUMAR V, QUINLAN J R, et al. Top 10 algorit-hms in data mining[J]. Knowledge and information systems, 2008, 14(1): 1-37.

[25]搜狗實(shí)驗(yàn)室語料[EB/OL]. http://www.sogou.com/labs/resource/list_yuliao.php.

Textsimilaritymeasuremethodbasedonclassifieddictionary

LI Hailin1, ZOU Jinchuan2

(1. Department of Information Systems, Huaqiao University, Quanzhou 362021,China; 2.Research Center of Applied Statistics and Big Data, Huaqiao University, Xiamen 361021, China)

Existing text-similarity measurement methods based on the semantic knowledge rules analysis have the limitation of high time complexity. In this paper, we propose a text-similarity measurement method based on the Classified Dictionary. First, we segmented texts using the Chinese Lexical Analysis System. Then, we extracted text keywords using the term frequency-inverse document frequency (tf*idf) method and performed keywords coding by traversing the dictionary. By calculating the coding similarity of the text keywords, we can determine the similarity of the original texts. As our two comparison methods, we selected similarity measurement methods based on semantic knowledge rules and statistics. We verified our similarity measurement results using traditional clustering algorithms and the k-nearest neighbors classification method. Our numerical results show that our proposed method can obtain relatively good results in clustering and classification experiments. In addition, compared with other semantic analysis measurement methods, this method has better time efficiency.

data mining; semantic analysis; classified dictionary; keywords extraction; encoder; similarity measure; clustering; classification

2016-08-30.

國家自然科學(xué)基金項(xiàng)目(61300139)；福建省自然科學(xué)基金項(xiàng)目(2015J01581)；華僑大學(xué)中青年教師科研提升計(jì)劃項(xiàng)目(ZQN-PY220)；華僑大學(xué)研究生科研創(chuàng)新能力培育計(jì)劃項(xiàng)目(1511307006).

鄒金串.E-mail：Zou_jinchuan@163.com.

10.11992/tis.201608010

TP301

A

1673-4785(2017)04-0556-07

中文引用格式：李海林，鄒金串.基于分類詞典的文本相似性度量方法J.智能系統(tǒng)學(xué)報(bào)， 2017, 12(4): 556-562.

英文引用格式：LIHailin,ZOUJinchuan.TextsimilaritymeasuremethodbasedonclassifieddictionaryJ.CAAItransactionsonintelligentsystems, 2017, 12(4): 556-562.

李海林,男,1982年生,副教授,博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與決策支持,主持國家自然科學(xué)基金1項(xiàng)和省部級基金2項(xiàng),發(fā)表學(xué)術(shù)論文40余篇，其中被SCI檢索11篇，EI檢索20余篇。

鄒金串,女,1993年生,碩士研究生,主要研究方向?yàn)槲谋就诰颉?/p>