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