文本相似度算法
轉(zhuǎn)自：http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html
Term frequency即關(guān)鍵詞詞頻，是指一篇文章中關(guān)鍵詞出現(xiàn)的頻率，比如在一篇M個(gè)詞的文章中有N個(gè)該關(guān)鍵詞，則
（公式1.1-1）
為該關(guān)鍵詞在這篇文章中的詞頻。
Inverse document frequency指逆向文本頻率，是用于衡量關(guān)鍵詞權(quán)重的指數(shù)，由公式
（公式1.2-1）
計(jì)算而得，其中D為文章總數(shù)，Dw為關(guān)鍵詞出現(xiàn)過(guò)的文章數(shù)。
預(yù)處理→文本特征項(xiàng)選擇→加權(quán)→生成向量空間模型后計(jì)算余弦。
預(yù)處理主要是進(jìn)行中文分詞和去停用詞，分詞的開(kāi)源代碼有：ICTCLAS。
然后按照停用詞表中的詞語(yǔ)將語(yǔ)料中對(duì)文本內(nèi)容識(shí)別意義不大但出現(xiàn)頻率很高的詞、符號(hào)、標(biāo)點(diǎn)及亂碼等去掉。如“這，的，和，會(huì)，為”等詞幾乎出現(xiàn)在任何一篇中文文本中，但是它們對(duì)這個(gè)文本所表達(dá)的意思幾乎沒(méi)有任何貢獻(xiàn)。使用停用詞列表來(lái)剔除停用詞的過(guò)程很簡(jiǎn)單，就是一個(gè)查詢(xún)過(guò)程：對(duì)每一個(gè)詞條，看其是否位于停用詞列表中，如果是則將其從詞條串中刪除。
圖2.2.1-1中文文本相似度算法預(yù)處理流程
過(guò)濾掉常用副詞、助詞等頻度高的詞之后，根據(jù)剩下詞的頻度確定若干關(guān)鍵詞。頻度計(jì)算參照TF公式。
加權(quán)是針對(duì)每個(gè)關(guān)鍵詞對(duì)文本特征的體現(xiàn)效果大小不同而設(shè)置的機(jī)制，權(quán)值計(jì)算參照IDF公式。
向量空間模型的基本思想是把文檔簡(jiǎn)化為以特征項(xiàng)（關(guān)鍵詞）的權(quán)重為分量的N維向量表示。
這個(gè)模型假設(shè)詞與詞間不相關(guān)（這個(gè)前提造成這個(gè)模型無(wú)法進(jìn)行語(yǔ)義相關(guān)的判斷，向量空間模型的缺點(diǎn)在于關(guān)鍵詞之間的線性無(wú)關(guān)的假說(shuō)前提），用向量來(lái)表示文本，從而簡(jiǎn)化了文本中的關(guān)鍵詞之間的復(fù)雜關(guān)系，文檔用十分簡(jiǎn)單的向量表示，使得模型具備了可計(jì)算性。
在向量空間模型中，文本泛指各種機(jī)器可讀的記錄。
用D（Document）表示文本，特征項(xiàng)（Term，用t表示）指出現(xiàn)在文檔D中且能夠代表該文檔內(nèi)容的基本語(yǔ)言單位，主要是由詞或者短語(yǔ)構(gòu)成，文本可以用特征項(xiàng)集表示為D（T1，T2，…，Tn），其中Tk是特征項(xiàng)，要求滿(mǎn)足1<=k<=N。
下面是向量空間模型（特指權(quán)值向量空間）的解釋。
假設(shè)一篇文檔中有a、b、c、d四個(gè)特征項(xiàng)，那么這篇文檔就可以表示為
D（a，b，c，d）
對(duì)于其它要與之比較的文本，也將遵從這個(gè)特征項(xiàng)順序。對(duì)含有n個(gè)特征項(xiàng)的文本而言，通常會(huì)給每個(gè)特征項(xiàng)賦予一定的權(quán)重表示其重要程度，即
D＝D（T1，W1；T2，W2；…，Tn，Wn）
簡(jiǎn)記為
D＝D（W1，W2，…，Wn）
我們把它叫做文本D的權(quán)值向量表示，其中Wk是Tk的權(quán)重，1<=k<=N。
在上面那個(gè)例子中，假設(shè)a、b、c、d的權(quán)重分別為30，20，20，10，那么該文本的向量表示為
D（30，20，20，10）
在向量空間模型中，兩個(gè)文本D1和D2之間的內(nèi)容相關(guān)度Sim（D1，D2）常用向量之間夾角的余弦值表示，公式為：
其中，W1k、W2k分別表示文本D1和D2第K個(gè)特征項(xiàng)的權(quán)值，1<=k<=N。
下面是利用模型進(jìn)行余弦計(jì)算的示例。
在自動(dòng)歸類(lèi)中，我們可以利用類(lèi)似的方法來(lái)計(jì)算待歸類(lèi)文檔和某類(lèi)目的相關(guān)度。
假設(shè)文本D1的特征項(xiàng)為a，b，c，d，權(quán)值分別為30，20，20，10，類(lèi)目C1的特征項(xiàng)為a，c，d，e，權(quán)值分別為40，30，20，10，則D1的向量表示為
D1（30，20，20，10，0）
C1的向量表示為
C1（40，0，30，20，10）
則根據(jù)上式計(jì)算出來(lái)的文本D1與類(lèi)目C1相關(guān)度是0.86。
那么0.86具體是怎么推導(dǎo)出來(lái)的呢？
在數(shù)學(xué)當(dāng)中，n維向量是
V{v1，v2，v3，...，vn}
模為
|v|=sqrt（v1*v1+v2*v2+…+vn*vn）
兩個(gè)向量的點(diǎn)積
m*n=n1*m1+n2*m2+......+nn*mn
相似度
sim＝（m*n）/（|m|*|n|）
它的物理意義就是兩個(gè)向量的空間夾角的余弦數(shù)值。
下面是代入公式的過(guò)程：
d1*c1=30*40+20*0+20*30+10*20+0*10=2000
|d1|=sqrt（30*30+20*20+20*20+10*10+0*0）=sqrt（1800）
|c1|=sqrt（40*40+0*0+30*30+20*20+10*10）=sqrt（3000）
sim=d1*c1/（|d1|*|c1|）=2000/sqrt（1800*3000）=0.86066
完畢。
開(kāi)源代碼：Text-Similarity-0.08
簡(jiǎn)介：PERL腳本、自定義去停用詞表、無(wú)語(yǔ)義識(shí)別功能、不適于中文。
局限：僅適用于英文、無(wú)語(yǔ)義相似判別功能
編譯安裝：
（1）進(jìn)入代碼主目錄里的/bin
修改text_similarity.pl
將第一行改為#!/usr/bin/perl
（2）退回代碼主目錄，分別執(zhí)行
perl Makefile.PL
make
make test
make install
（3）重新進(jìn)入主目錄/bin進(jìn)行測(cè)試
圖2.3-1代碼效果
可以看見(jiàn)語(yǔ)句“.......this is one”與“????this is two”的匹配度是0.66；
“.......this is one”與“.......this is two”的匹配度仍然是0.66；
“.......this is one”與“…….this is one”的匹配度是1；
“.......this is one”與“..（）（）this is one”的匹配度是1。
說(shuō)明匹配的算法去停用字功能存在。
這類(lèi)算法沒(méi)有很好地解決文本數(shù)據(jù)中存在的自然語(yǔ)言問(wèn)題，即同義詞和多義詞。這樣對(duì)于搜索的精度產(chǎn)生很大的影響。
圖2.5-1算法變體（紅）
隱性語(yǔ)義標(biāo)引（LSI）利用矩陣?yán)碚撝械摹捌娈愔捣纸猓⊿VD）”技術(shù)，將詞頻矩陣轉(zhuǎn)化為奇異矩陣：首先從全部的文檔集中生成一個(gè)文檔矩陣，該矩陣的每個(gè)分量為整數(shù)值，代表某個(gè)特定的文檔矩陣出現(xiàn)在某個(gè)特定文檔中次數(shù)。然后將該矩陣進(jìn)行奇異值分解，較小的奇異值被剔除。結(jié)果奇異向量以及奇異值矩陣用于將文檔向量和查詢(xún)向量映射到一個(gè)子空間中，在該空間中，來(lái)自文檔矩陣的語(yǔ)義關(guān)系被保留。最后，可以通過(guò)標(biāo)準(zhǔn)化的內(nèi)積計(jì)算來(lái)計(jì)算向量之間的夾角余弦相似度，進(jìn)而根據(jù)計(jì)算結(jié)果比較文本間的相似度。LSI引入的唯一變化就是剔除小的奇異值，因?yàn)榕c小的奇異值相關(guān)聯(lián)的特征實(shí)際上在計(jì)算相似度時(shí)并不相關(guān)，將它們包括進(jìn)來(lái)將降低相關(guān)性判斷的精確度。保留下來(lái)的特征是那些對(duì)文檔向量在m維空間中的位置大有影響的特征。剔除小的奇異值將文檔特征空間變?yōu)槲臋n概念空間。概念向量之問(wèn)使用內(nèi)積的夾角余弦相似度計(jì)算比原來(lái)基于原文本向量的相似度計(jì)算更可靠，這也是使用LSI方法的主要原因所在。LSI的缺點(diǎn)在于它的效果依賴(lài)于上下文信息，過(guò)于稀疏的語(yǔ)料不能很好的體現(xiàn)其潛在的語(yǔ)義。
用向量空間模型（VSM）來(lái)表示文本在該領(lǐng)域內(nèi)普遍受到認(rèn)可，是因?yàn)槠湓谥R(shí)表示方法上的巨大優(yōu)勢(shì)。在該模型中，文本內(nèi)容被形式化為多維空間中的一個(gè)點(diǎn)，通過(guò)向量的形式給出，把對(duì)文本內(nèi)容的處理簡(jiǎn)化為向量空間中向量的運(yùn)算，使問(wèn)題的復(fù)雜性大為降低。但是它很大的不足之處在于只考慮了詞在上下文中的統(tǒng)計(jì)特性，假定關(guān)鍵詞之間線性無(wú)關(guān)，而沒(méi)有考慮詞本身的語(yǔ)義信息，因此具有一定的局限性。
結(jié)合語(yǔ)義相似度計(jì)算后的算法流程如下所示：
圖3.2-1基于向量空間的語(yǔ)義相似度算法流程圖
其中，語(yǔ)義相關(guān)度計(jì)算獲得相似度矩陣的方向有兩個(gè)：基于知網(wǎng)HowNet或者基于WordNet。
不同于傳統(tǒng)的以關(guān)鍵詞匹配為核心的匹配技術(shù)，這里提出基于拼音相似度的編輯距離來(lái)衡量漢字字符串之間的相似度。
論文提出三種編輯距離：基于漢字的編輯距離、基于拼音的編輯距離，以及基于拼音改良的編輯距離。
（1）將兩個(gè)字符串分別以行和列組成矩陣。
（2）計(jì)算每個(gè)節(jié)點(diǎn)行列字符是否相同，如相同則為1。
（3）通過(guò)找出值為1的最長(zhǎng)對(duì)角線即可得到最長(zhǎng)公共子串。
為進(jìn)一步提升該算法，我們可以將字符相同節(jié)點(diǎn)的值加上左上角（d[i-1，j-1]）的值，這樣即可獲得最大公共子串的長(zhǎng)度。如此一來(lái)只需以行號(hào)和最大值為條件即可截取最大子串。
（1）狹義編輯距離
設(shè)A、B為兩個(gè)字符串，狹義的編輯距離定義為把A轉(zhuǎn)換成B需要的最少刪除（刪除A中一個(gè)字符）、插入（在A中插入一個(gè)字符）和替換（把A中的某個(gè)字符替換成另一個(gè)字符）的次數(shù)，用ED（A，B）來(lái)表示。直觀來(lái)說(shuō)，兩個(gè)串互相轉(zhuǎn)換需要經(jīng)過(guò)的步驟越多，差異越大。
（2）步驟
1.對(duì)兩部分文本進(jìn)行處理，將所有的非文本字符替換為分段標(biāo)記“#”
2.較長(zhǎng)文本作為基準(zhǔn)文本，遍歷分段之后的短文本，發(fā)現(xiàn)長(zhǎng)文本包含短文本子句后在長(zhǎng)本文中移除，未發(fā)現(xiàn)匹配的字句累加長(zhǎng)度。
3.比較剩余文本長(zhǎng)度與兩段文本長(zhǎng)度和，其比值為不匹配比率。
衡量文本相似度的幾種手段：
（1）最長(zhǎng)公共子串（基于詞條空間）
（2）最長(zhǎng)公共子序列（基于權(quán)值空間、詞條空間）
（3）最少編輯距離法（基于詞條空間）
（4）漢明距離（基于權(quán)值空間）
（5）余弦值（基于權(quán)值空間）
聯(lián)系客服
