基于Levenshtein和TFRSF的文本相似度計(jì)算方法

藏潤(rùn)強(qiáng)，孫紅光,2，楊鳳芹,2，馮國(guó)忠,2，尹良亮

(1.東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130117; 2.智能信息處理吉林省高校重點(diǎn)實(shí)驗(yàn)室，吉林 長(zhǎng)春 130117)

0 引 言

字符串相似問(wèn)題在自然語(yǔ)言處理、數(shù)據(jù)挖掘、信息檢索等領(lǐng)域，具有非常廣泛的應(yīng)用背景[1]。另外在Google與百度等搜索引擎對(duì)模糊關(guān)鍵詞查詢(xún)處理、機(jī)器對(duì)主觀題判卷、論文重復(fù)率檢測(cè)等方面，其相似性問(wèn)題也一直是需要解決的核心問(wèn)題。相似的數(shù)據(jù)信息普遍存在，加上復(fù)雜的信息難以區(qū)分，嚴(yán)重影響后續(xù)數(shù)據(jù)處理過(guò)程，如何判斷相似的數(shù)據(jù)信息一直是自然語(yǔ)言處理、數(shù)據(jù)挖掘等領(lǐng)域的重要主題之一。例如，不同的社交網(wǎng)絡(luò)[2]其功能和用戶(hù)體驗(yàn)都有不同的特點(diǎn)，用戶(hù)常常在多個(gè)不同的社交網(wǎng)絡(luò)上擁有賬戶(hù)。用戶(hù)會(huì)根據(jù)不同的社交網(wǎng)絡(luò)性質(zhì)創(chuàng)建一個(gè)自身完整形象的局部縮影，由于用戶(hù)信息分散在各個(gè)不同的社交網(wǎng)絡(luò)，這些分散的局部信息不會(huì)相互連通，因此，需要將多個(gè)社交網(wǎng)絡(luò)的賬戶(hù)進(jìn)行數(shù)據(jù)拉通。在現(xiàn)實(shí)世界中，同一個(gè)實(shí)體的描述內(nèi)容總是充滿(mǎn)多義性的，人的名字也是其中之一，同一個(gè)人名可能被不同人使用，這樣導(dǎo)致社交網(wǎng)絡(luò)中普遍存在的問(wèn)題是：當(dāng)查詢(xún)一個(gè)人名時(shí)，現(xiàn)有的系統(tǒng)會(huì)將所有與該人名同名的結(jié)果列出來(lái)，這樣無(wú)疑會(huì)使查詢(xún)用戶(hù)產(chǎn)生混淆，同名者的個(gè)人社會(huì)網(wǎng)絡(luò)往往會(huì)出現(xiàn)錯(cuò)誤的重疊或合并,針對(duì)這些問(wèn)題，同名相似度匹配的研究工作就顯得非常重要。對(duì)于姓名重復(fù)的用戶(hù)，通過(guò)個(gè)人背景信息描述的差異，可以判斷是不是同一個(gè)人，但是，當(dāng)描述信息相似，譬如，原有信息的增加或者減少，個(gè)人信息簡(jiǎn)寫(xiě)，信息內(nèi)容顛倒，計(jì)算機(jī)會(huì)誤判為不是同一個(gè)人。為了解決這個(gè)問(wèn)題，目前，提出了很多種計(jì)算字符串相似度的算法，有字面相似算法、矩陣匹配相似度算法、編輯距離算法等，其中編輯距離[3]算法作為常用的字符串相似度求解算法，在數(shù)據(jù)清理方面具有一定的優(yōu)勢(shì)[4]，在拼寫(xiě)錯(cuò)誤檢測(cè)方面具有較高的精度，具有應(yīng)用廣泛、查找高效和時(shí)間復(fù)雜度較低等優(yōu)點(diǎn)。近些年，對(duì)編輯距離算法的改進(jìn)一直在繼續(xù)，文獻(xiàn)[5]中提供了一種歸一化的編輯距離。文獻(xiàn)[6]中提出了2種計(jì)算字符串相似度的公式。文獻(xiàn)[7]中提出了一種基于編輯距離和相似度改進(jìn)的漢字字符串近似匹配算法，通過(guò)改進(jìn)動(dòng)態(tài)規(guī)劃算法，能夠有效提高編輯距離的計(jì)算準(zhǔn)確度以及執(zhí)行效率。文獻(xiàn)[8]中提出了基于基本操作序列的編輯距離順序驗(yàn)證方法，不論在長(zhǎng)字符還是短字符中都具有更高的效率。文獻(xiàn)[9]中使用編輯距離計(jì)算2個(gè)網(wǎng)絡(luò)應(yīng)用程序的相似度，但規(guī)定的編輯操作仍不夠靈活。

在編輯距離算法的多次改進(jìn)之后仍然存在若干問(wèn)題，編輯距離算法沒(méi)有考慮可能存在字符串位置顛倒問(wèn)題，這樣會(huì)導(dǎo)致錯(cuò)誤的相似度計(jì)算結(jié)果。完成2個(gè)字符串的編輯距離算法之后需要進(jìn)行相似度計(jì)算，傳統(tǒng)的相似度計(jì)算方法只考慮了編輯操作次數(shù)，沒(méi)有考慮2個(gè)字符串之間的公共子串[10]對(duì)相似度的影響。因此，傳統(tǒng)的字符串相似度計(jì)算方法不具備普遍適用性和準(zhǔn)確性。

針對(duì)以上文獻(xiàn)描述的不足之處，本文根據(jù)相關(guān)的字符串含有共同詞的頻率，提出了詞頻相關(guān)字符串頻率方法，并改進(jìn)為一種新的編輯距離方法levenshtein+tf.rsf (lv+tf.rsf)，所提方法的創(chuàng)新之處是融合新的tf.rsf方法處理字符串位置顛倒導(dǎo)致的相似性不準(zhǔn)確問(wèn)題。另外對(duì)傳統(tǒng)的字符串相似度計(jì)算方法進(jìn)行改進(jìn)，新的相似度計(jì)算方法利用公共子串更適用于編輯距離算法。為了驗(yàn)證所提方法的有效性，使用支持向量機(jī)、樸素貝葉斯、隨機(jī)森林和邏輯回歸分類(lèi)模型[11]進(jìn)行訓(xùn)練。通過(guò)評(píng)價(jià)指標(biāo)[12-13]對(duì)數(shù)據(jù)集上進(jìn)行的文本分類(lèi)實(shí)驗(yàn)結(jié)果表明，本文所提出的方法處理字符串相似度更加準(zhǔn)確。

1 相關(guān)技術(shù)與研究

1.1 Levenshtein編輯距離

Levenshtein編輯距離算法是一種計(jì)算2個(gè)字符串之間的差異程度度量，編輯距離是通過(guò)改變?cè)醋址侥繕?biāo)字符串的最小距離。這個(gè)距離包括插入、替換和刪除等操作，利用動(dòng)態(tài)規(guī)劃的操作，對(duì)每個(gè)字符串進(jìn)行順序比較，其算法的時(shí)間復(fù)雜度是O(mn)，空間復(fù)雜度為O(mn)，m和n分別表示源字符串S和目標(biāo)字符串T的長(zhǎng)度。

編輯距離D(S,T)的計(jì)算方法如下，首先假設(shè)Dij=D(S0…Si,T0…Tj),0≤i≤m,0≤j≤n,S0…Si是源字符串，T0…Tj是目標(biāo)字符串，那么(m+1)×(n+1)階矩陣Dij可以通過(guò)式(1)計(jì)算得到：

(1)

式(1)包含刪除(wa)、插入(wb)、替換(wc)這3種操作[6]，wa,wb和wc分別表示每一種操作的權(quán)重，實(shí)驗(yàn)中，刪除、插入權(quán)重加1，替換權(quán)重加2，本文設(shè)置wa=1,wb=1和wc=2。

Dij是指從源字符串S到目標(biāo)字符串T的最小編輯操作次數(shù)，目的是計(jì)算S與T的相似度，Dij隨著2個(gè)字符串之間的相似度減少而增加。該算法從字符串左邊第一個(gè)字符串位置開(kāi)始比較，對(duì)已經(jīng)比較過(guò)的編輯距離，繼續(xù)計(jì)算下一個(gè)字符位置的編輯距離。矩陣能夠通過(guò)從D00逐行逐列計(jì)算獲取，最終Dmn表示D(S,T)的值，即S和T的最小編輯距離。

例如將“改進(jìn)編輯距離”轉(zhuǎn)換成“編輯距離改進(jìn)”，至少需4次編輯操作：刪除字符“改”；刪除字符“進(jìn)”；在字符“離”后插入字符“改”；在字符“改”后插入字符“進(jìn)”。所以，由圖1可知，“改進(jìn)編輯距離”轉(zhuǎn)換成“編輯距離改進(jìn)”的編輯距離為4。

圖1 編輯距離過(guò)程

1.2 相似度計(jì)算方法

得到編輯距離結(jié)果后，需要進(jìn)行相似度計(jì)算，相似度是2個(gè)字符串之間相似程度的度量，基于編輯距離計(jì)算2個(gè)字符串相似度的公式[14]為：

(2)

式(2)中，ld表示2個(gè)字符串之間的Levenshtein距離；m和n分別為2個(gè)字符串的長(zhǎng)度；sim值越大，表示2個(gè)字符串相似度越高。

2 基于Levenshtein和TFRSF的文本相似度計(jì)算方法

由于Levenshtein編輯距離無(wú)法處理顛倒的字符串，根據(jù)相關(guān)的字符串含有共同詞的頻率，本文提出一種相關(guān)字符串頻率計(jì)算方法，并在其基礎(chǔ)上改進(jìn)為一種新的編輯距離方法levenshtein+tf.rsf。另外結(jié)合最長(zhǎng)公共子串長(zhǎng)度和字符串公共起始位置，對(duì)傳統(tǒng)的字符串相似度計(jì)算方法進(jìn)行改進(jìn)。

2.1 詞頻相關(guān)字符串頻率

tf.rsf是由詞頻(term frequency,tf)和相關(guān)字符串頻率(related string frequency,rsf)這2部分組成的，詞頻相關(guān)字符串頻率公式為：

(3)

2.1.1 特征的詞頻

詞頻(tf)是指在一篇文檔中，某一特征t出現(xiàn)的次數(shù)，詞頻代表當(dāng)前特征與包含此特征的文檔之間的關(guān)系。二進(jìn)制表示是tf的一個(gè)特殊形式，如公式(4)所示。

(4)

2.1.2 相關(guān)字符串頻率的提出

相關(guān)字符串頻率(rsf)這個(gè)命名主要是因?yàn)橹豢紤]相關(guān)的字符串含有共同詞的頻率，只有a和b在公式中發(fā)揮了作用。下面公式(5)的核心思想為：判斷2個(gè)字符串是否相似，具有最好區(qū)分能力的是那些在2個(gè)字符串中同時(shí)出現(xiàn)的詞。

(5)

在本文提出的“相關(guān)字符串頻率”中n代表2個(gè)字符串含有相同詞的數(shù)量，a為源字符串的詞的總數(shù)量，b為目標(biāo)字符串中詞的總數(shù)量，x為設(shè)定的常數(shù)。本文中令x=5，是為了相似度結(jié)果更加真實(shí)準(zhǔn)確。在公式(5)中，max(1,a)和max(1,b)是為了防止源字符串或目標(biāo)字符串不存在，導(dǎo)致分母等于0的情況。

2.2 兩個(gè)字符串之間的相似度改進(jìn)

相似度計(jì)算公式(2)并不具備普遍適用性。假設(shè)字符串：

S1=“ab”, T1=“bc”, T2=“de”

相似度：

sim(S1,T1)=0.5, sim(S1,T2)=0.5

使用式(2)算得S1，T1的相似度與S1，T2的相似度一樣為0.5，但S1，T1的相似度明顯大于S1，T2的相似度，因?yàn)镾1和T1之間存在最長(zhǎng)的公共子串b，最長(zhǎng)公共子串是字符串S和T的所有公共后綴中長(zhǎng)度最大的后綴。本文結(jié)合編輯距離和最長(zhǎng)公共子串給出改進(jìn)的字符串相似度計(jì)算公式，在改進(jìn)的相似度計(jì)算公式中本文重新定義了2個(gè)字符串之間的相似度。本文新的方法使用ld距離、2個(gè)字符串的最長(zhǎng)公共子串長(zhǎng)度LCS(S,T)(longest common substring)和2個(gè)字符串比較時(shí)第一次出現(xiàn)匹配的字符位置p(position)，引入匹配位置是因?yàn)樽址哂许樞蛐?，往往前面的字符相同才?huì)對(duì)比后面的字符是否相似，先出現(xiàn)的字符通常代表更重要的信息，所以有必要研究字符的先后順序?qū)ο嗨贫鹊挠绊憽?/p>

(6)

sim(S1,T1)=0.31, sim(S1,T2)=0

得出S1，T1的相似度大于S1，T2的相似度，比使用式(2)算得的結(jié)果更符合實(shí)際情況。為了進(jìn)一步說(shuō)明，假設(shè)源字符串為“take”，表1給出了對(duì)不同目標(biāo)字符串集合，分別使用式(2)和式(6)計(jì)算相似度的結(jié)果對(duì)比。

表1 式(2)和式(6)計(jì)算相似度值對(duì)比

目標(biāo)字符串公式(2)公式(6)tab0.570.38toke0.750.57type0.50.32taka0.70.57awake0.670.47taken0.890.77pake0.750.56

由以上例子說(shuō)明改進(jìn)的相似度計(jì)算公式結(jié)果更加真實(shí)，公式(6)的結(jié)果標(biāo)準(zhǔn)差為0.138，大于公式(2)的標(biāo)準(zhǔn)差0.118，說(shuō)明公式(6)有著更好的區(qū)分度。

2.3 改進(jìn)的編輯距離算法

同名異義是電子數(shù)據(jù)庫(kù)和語(yǔ)義社會(huì)網(wǎng)絡(luò)中普遍存在的問(wèn)題。比如：在查詢(xún)一個(gè)研究者所發(fā)表的文章時(shí)，現(xiàn)有的系統(tǒng)會(huì)將所有與該研究者同名的作者的文章返回給用戶(hù)，這樣無(wú)疑會(huì)使用戶(hù)產(chǎn)生混淆。而語(yǔ)義社會(huì)網(wǎng)絡(luò)中，同名者的個(gè)人社會(huì)網(wǎng)絡(luò)往往會(huì)出現(xiàn)錯(cuò)誤的重疊或合并。針對(duì)這些問(wèn)題，同名排歧的研究工作就顯得非常重要。

公式(1)在大多數(shù)情況下，從字符串的左邊第一位字符開(kāi)始，依次進(jìn)行比較，然后記錄已經(jīng)比較過(guò)的編輯距離的數(shù)值，最后得到下一個(gè)字符位置的編輯距離。但是中英文的某些表達(dá)方式可以不同，使用公式(1)計(jì)算時(shí)，卻得出錯(cuò)誤的結(jié)果，尤其是中文的表達(dá)方式。

例如S=“大家晚上好”和T=“晚上好大家”，編輯距離為5，相似度為0。實(shí)際上S和T表達(dá)的意思相同。因此在這種情況下，式(1)不再適用，需要進(jìn)一步改進(jìn)。

本文采用的方法是編輯距離和相對(duì)頻率的融合使用，當(dāng)2個(gè)字符串的相似度小于一定閾值，則使用相對(duì)頻率進(jìn)行相似度計(jì)算。這樣能有效解決因?yàn)槲恢貌煌瑢?dǎo)致相似度不正確的問(wèn)題，改進(jìn)方法的流程如圖2所示，其步驟如下：

1)首先計(jì)算字符串的相似度。

2)如果相似度大于或等于設(shè)定的閾值，則不進(jìn)行相對(duì)頻率的計(jì)算。

3)如果相似度小于設(shè)定的閾值，進(jìn)行相對(duì)頻率的計(jì)算。

①如果相對(duì)頻率計(jì)算的值大于或等于閾值，則替換不好的相似度值。

②如果相對(duì)頻率計(jì)算的值小于閾值，仍使用編輯距離計(jì)算出來(lái)的值。

圖2 改進(jìn)方法流程圖

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

3.1 數(shù)據(jù)集

為了驗(yàn)證本文所提出算法的有效性，計(jì)算不同社交網(wǎng)絡(luò)中的2個(gè)用戶(hù)信息相似度，判斷其是否是同一個(gè)人。

圖3 一個(gè)用戶(hù)信息抽取例子

首先按姓名搜索出同名列表，使用支持向量機(jī)二分類(lèi)判斷是否為用戶(hù)的個(gè)人主頁(yè)，圖3給出了用戶(hù)的個(gè)人主頁(yè)示例，其中包含了用戶(hù)的各種信息。例如：圖左框的上部包含其姓名、職位、聯(lián)系電話(huà)等，中間部分用自然語(yǔ)言描述了個(gè)人經(jīng)歷，下部提供了論文發(fā)表情況。其中AMiner利用信息抽取方法[15]自動(dòng)獲取來(lái)自學(xué)術(shù)合作者網(wǎng)絡(luò)的研究者相關(guān)信息，使用爬蟲(chóng)從社交網(wǎng)絡(luò)LinkedIn爬取用戶(hù)數(shù)據(jù)，圖3右邊顯示了理想的結(jié)構(gòu)化抽取結(jié)果。在實(shí)驗(yàn)前對(duì)所有數(shù)據(jù)進(jìn)行預(yù)處理，包括屬性選擇、去除停止詞、刪除標(biāo)點(diǎn)符號(hào)，過(guò)濾缺失數(shù)據(jù)和異常數(shù)據(jù)后各剩下33957名用戶(hù)信息。用戶(hù)的屬性包括姓名、單位、教育背景、發(fā)表論文、技能、獲獎(jiǎng)等。

3.2 評(píng)價(jià)指標(biāo)及其方法

使用公式(1)和公式(6)計(jì)算用戶(hù)信息相似度,生成特征文件。對(duì)于分類(lèi)問(wèn)題，目前并沒(méi)有一種通用的、在任何數(shù)據(jù)上都能取得最佳分類(lèi)正確率的算法，因此本文使用Python語(yǔ)言Scikit-Learn庫(kù)中的支持向量機(jī)、樸素貝葉斯、隨機(jī)森林和邏輯回歸分類(lèi)模型進(jìn)行訓(xùn)練，用多種分類(lèi)算法驗(yàn)證算法的有效性。將特征數(shù)據(jù)切分為5份，每次取其中的1份做測(cè)試以及評(píng)估，其它4份做訓(xùn)練，循環(huán)5次。用準(zhǔn)確率、召回率、F1值作為評(píng)價(jià)指標(biāo)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

為了更好地說(shuō)明評(píng)估指標(biāo)，引入類(lèi)別列聯(lián)表。類(lèi)別列聯(lián)表針對(duì)某一個(gè)類(lèi)別而言，統(tǒng)計(jì)了所有測(cè)試文本與這個(gè)待定類(lèi)別之間的分類(lèi)情況。TP(true positive)代表被正確分類(lèi)到類(lèi)別C的數(shù)量；FP(false positive)代表被錯(cuò)誤分類(lèi)到類(lèi)別C的數(shù)量；FN(false negative)代表實(shí)際屬于類(lèi)別C，但是被錯(cuò)誤分類(lèi)到其他類(lèi)別的數(shù)量。

3.2.1 準(zhǔn)確率和召回率

準(zhǔn)確率(Precision)指的是被正確分類(lèi)到類(lèi)別C的數(shù)量與被分類(lèi)到此類(lèi)別的所有數(shù)量的比值。召回率(Recall)是指被正確分類(lèi)到類(lèi)別C的數(shù)量與實(shí)際屬于此類(lèi)別的數(shù)量的比值。準(zhǔn)確率P與召回率R是分類(lèi)器性能的2個(gè)常用度量值，分別用公式(7)和公式(8)計(jì)算。

(7)

(8)

3.2.2 微平均、宏平均

準(zhǔn)確率和召回率僅僅可以度量分類(lèi)器對(duì)單個(gè)類(lèi)別的局部分類(lèi)性能。當(dāng)對(duì)分類(lèi)器的全局分類(lèi)性能評(píng)估時(shí)，通常采用微平均值(Micro-Average)和宏平均值(Macro-Average)。在計(jì)算微平均和宏平均的時(shí)候，首先需要依據(jù)每個(gè)類(lèi)別的列聯(lián)表得到全局列聯(lián)表，如表2所示。

表2 全局列聯(lián)表

類(lèi)別集合C={C1,C2,…,Ci,…,C|C|}實(shí)際樣本數(shù)據(jù)情況屬于類(lèi)別C不屬于類(lèi)別C分類(lèi)結(jié)果屬于類(lèi)別CTP=∑|C|i=1TPiFP=∑|C|i=1FPi不屬于類(lèi)別CFN=∑|C|i=1FNiTN=∑|C|i=1TNi

宏平均是每一個(gè)類(lèi)別性能指標(biāo)的算術(shù)平均，宏平均在度量的時(shí)候，均等對(duì)待每一個(gè)類(lèi)別，相比微平均值，宏平均值的結(jié)果極易受到小樣本類(lèi)別的影響，微平均是各個(gè)性能指標(biāo)的算術(shù)平均，它的值主要受到數(shù)據(jù)集中較多的類(lèi)別影響。微平均F1值與宏平均F1值可以綜合度量文本分類(lèi)性能指標(biāo)。

涉及“生態(tài)旅游”這一術(shù)語(yǔ)，最早可追溯到1983年，由世界自然保護(hù)聯(lián)盟（IUCN）首次提出，國(guó)際生態(tài)旅游協(xié)會(huì)1993年將其定義為：具有保護(hù)自然環(huán)境和維護(hù)當(dāng)?shù)厝嗣裆铍p重責(zé)任的旅游活動(dòng)[1]。

3.3 性能比較

將本文提出的方法與其它2組方法組合進(jìn)行對(duì)比分析：

1)使用傳統(tǒng)的Levenshtein方法作為本實(shí)驗(yàn)的基準(zhǔn)相似度方法。

2)邵清在提出的基于編輯距離和相似度改進(jìn)的漢字字符串匹配算法[7]中，同樣考慮到文本位置顛倒位置問(wèn)題，以語(yǔ)義編輯距離與長(zhǎng)句的長(zhǎng)度比值作為歸一化結(jié)果取得了很好的效果，本文使用歸一化的相似度計(jì)算公式(簡(jiǎn)稱(chēng)：lv+ssim)作為實(shí)驗(yàn)對(duì)比。

實(shí)驗(yàn)產(chǎn)生的特征文件在多種分類(lèi)算法下進(jìn)行微平均和宏平均的準(zhǔn)確率、召回率和F1值比較，如表3和表4所示。

表3 微平均性能對(duì)比表

分類(lèi)算法方法PrecisionRecallF1支持向量機(jī)Levenshtein0.938820.934930.93577lv+ssim0.948530.947250.94809lv+tf.rsf0.962160.961130.96189樸素貝葉斯Levenshtein0.915460.880560.89137lv+ssim0.919710.901120.90938lv+tf.rsf0.924920.926450.92021隨機(jī)森林Levenshtein0.943180.944160.94329lv+ssim0.960350.958290.95124lv+tf.rsf0.970400.969080.96702邏輯回歸Levenshtein0.943070.947110.93291lv+ssim0.956320.949740.94729lv+tf.rsf0.961570.961860.95774

表4 宏平均性能對(duì)比表

分類(lèi)算法方法PrecisionRecallF1支持向量機(jī)Levenshtein0.918670.865940.89496lv+ssim0.923920.870120.90589lv+tf.rsf0.931990.878770.90875樸素貝葉斯Levenshtein0.915460.870770.89137lv+ssim0.920100.882590.90128lv+tf.rsf0.928340.891260.90932隨機(jī)森林Levenshtein0.936400.884670.90835lv+ssim0.947620.904180.91587lv+tf.rsf0.951270.924750.92748邏輯回歸Levenshtein0.940130.866160.89149lv+ssim0.944190.869240.90631lv+tf.rsf0.950760.885420.91055

圖4與圖5展示了3種方法在不同分類(lèi)算法下Precision，Recall，F(xiàn)1這3個(gè)指標(biāo)平均值的對(duì)比，實(shí)驗(yàn)結(jié)果表明本文方法在各項(xiàng)性能指標(biāo)均優(yōu)于傳統(tǒng)編輯距離和采用歸一化的相似度計(jì)算方法，并且分類(lèi)結(jié)果具有很好的健壯性。

在這幾種分類(lèi)器中，本文方法的準(zhǔn)確率、召回率、F1度量平均值都較穩(wěn)定，微平均下準(zhǔn)確率、召回率、F1度量的平均值均達(dá)到0.92以上，說(shuō)明受到數(shù)據(jù)集中類(lèi)別的影響較小。宏平均下準(zhǔn)確率平均值均達(dá)到0.92以上，召回率平均值均達(dá)到0.87以上，F(xiàn)1度量平均值均達(dá)到0.90以上，說(shuō)明模型對(duì)負(fù)樣本的區(qū)分能力強(qiáng)，對(duì)正樣本的識(shí)別能力強(qiáng)，分類(lèi)模型穩(wěn)定。

圖4 微平均下的Precision、Recall、F1平均值對(duì)比

圖5 宏平均下的Precision、Recall、F1平均值對(duì)比

4 結(jié)束語(yǔ)

本文針對(duì)相關(guān)的字符串含有共同詞的頻率提出相關(guān)字符串頻率方法，在Levenshtein編輯距離基礎(chǔ)上進(jìn)行改進(jìn)，將Levenshtein編輯距離和tf.rsf方法融合，有效地解決了因?yàn)樽址恢妙嵉箤?dǎo)致誤導(dǎo)決策問(wèn)題。由于傳統(tǒng)的基于編輯距離計(jì)算相似度方法普遍適用性低，本文提出的相似度計(jì)算方法，提高了計(jì)算相似度的準(zhǔn)確性。未來(lái)將繼續(xù)優(yōu)化相似度計(jì)算方法，研究更有效的并行算法，并將其用于海量數(shù)據(jù)處理中。

參考文獻(xiàn)：

[1] Gomaa W H, Fahmy A A. A survey of text similarity approaches[J]. International Journal of Computer Applications, 2013,68(13):13-18.

[2] Kwon O, Wen Yixing. An empirical study of the factors affecting social network service use[J]. Computers in Human Behavior, 2010,26(2):254-263.

[3] Levenshtein V I. Binary codes capable of correcting spurious insertions and deletions of ones[J]. Problems of Information Transmission, 1965,1(1):8-17.

[4] 劉輝平,金澈清,周傲英. 一種基于模式的實(shí)體解析算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2015,38(9):1796-1808.

[5] Li Yujian, Liu Bo. A normalized Levenshtein distance metric[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007,29(6):1091-1095.

[6] Putra M E W, Suwardi I S. Structural off-line handwriting character recognition using approximate subgraph matching and Levenshtein distance[J]. Procedia Computer Science, 2015,59:340-349.

[7] 邵清,葉琨. 基于編輯距離和相似度改進(jìn)的漢字字符串匹配[J]. 電子科技, 2016,29(9):7-11.

[8] 張潤(rùn)梁,牛之賢. 基于基本操作序列的編輯距離順序驗(yàn)證[J]. 計(jì)算機(jī)科學(xué), 2016,43(S1):51-54.

[9] Popescu D A, Nicolae D. Determining the similarity of two Web applications using the edit distance[C]// Proceedings of the 6th International Workshop on Soft Computing Applications. 2014,1:681-690.

[10] Crochemore M, Iliopoulos C S, Langiu A, et al. The longest common substring problem[J]. Mathematical Structures in Computer Science, 2017,27(2):277-295.

[11] Joachims T. Text categorization with support vector machines: Learning with many relevant features[C]// Proceedings of the 10th European Conference on Machine Learning. 1998:137-142.

[12] Herrera F, Herrera-Viedma E, Martinez L. A fuzzy linguistic methodology to deal with unbalanced linguistic term sets[J]. IEEE Transactions on Fuzzy Systems, 2008,16(2):354-370.

[13] 劉冬瑞,劉東升,張麗萍,等. 基于貝葉斯網(wǎng)絡(luò)預(yù)測(cè)克隆代碼質(zhì)量[J]. 計(jì)算機(jī)科學(xué), 2017,44(4):165-168.

[14] Schumann S, Bühligen U, Neumuth T. Distance measures for surgical process models[J]. Methods of Information in Medicine, 2013,52(5):422-431.

[15] Tang Jie, Yao Limin, Zhang Duo, et al. A combination approach to Web user profiling[J]. ACM Transactions on Knowledge Discovery from Data, 2010,5(1): Article No. 2.