文本相識度算法（餘弦相似性、簡單共有詞、編輯距離、SimHash、漢明距離、Jaccard相似性系數、歐幾裡得距離、曼哈頓距離 ）

文本相似度計算在資訊檢索、資料挖掘、機器翻譯、文檔複制檢測等領域有着廣泛的應用。

比如輿論控制，我們假設你開發了一個微網誌網站，并且已經把世界上罵人的句子都已經收錄進了資料庫，那麼當一個使用者發微網誌時會先跟罵人句子的資料庫進行比較，如果符合裡面的句子就不讓使用者發出。

通常情況下，很多工程師就會想到用like或者where的sql文法去查找。可是當情況更為複雜呢？

資料庫存放了“你是個壞人”，使用者要發“小明是個壞人”，這時應該怎麼辦呢？

最簡單的辦法就是通過判斷文本的相似程度來決定使用者發的内容是否是罵人的。

本章節就幾種簡單的判斷文本相似性的算法來講解，幫助大家更好的了解。

相關算法

1、餘弦相似性

餘弦（餘弦函數），三角函數的一種。在Rt△ABC（直角三角形）中，∠C=90°，角A的餘弦是它的鄰邊比三角形的斜邊，即cosA=b/c，也可寫為cosA=AC/AB。餘弦函數：f（x）=cosx（x∈R）

這是一個非常常見的算法，相信大家都應該學過餘弦定理了，簡單來說這個算法就是通過計算兩個向量的夾角餘弦值來評估他們的相似度。

對于二維空間，根據向量點積公式，顯然可以得知（ps，這個公式不是這個算法的重點，可以不用強記）：

假設向量a、b的坐标分别為(x1,y1)、(x2,y2) 。則：

設向量 A = (A1,A2,...,An)，B = (B1,B2,...,Bn) 。推廣到多元，數學家已經幫我們證明了，是以你隻要記住下面的公式：

簡單來說可以寫成下面的式子：

（式子中的x和y是指詞頻）

比如我們要判斷兩句話

A=你是個壞人 

B=小明是個壞人

① 先進行分詞

A=你 / 是 / 個 / 壞人 

B=小明 / 是 / 個 / 壞人

② 列出所有的詞

{ 你 小明 是 個 壞人 }

③計算詞頻（出現次數）

A={1 0 1 1} (每個數字對應上面的字) 

B={0 1 1 1}

然後把詞頻帶入公式

最終=0.667。

餘弦值越接近1，就表明夾角越接近0度，也就是兩個向量越相似，這就叫"餘弦相似性"。

簡單來說上面計算出的值代表兩個句子大概六成相似，越接近1就越相似。

--------------------------------------------------

2、簡單共有詞

通過計算兩篇文檔共有的詞的總字元數除以最長文檔字元數來評估他們的相似度。

假設有A、B兩句話，先取出這兩句話的共同都有的詞的字數然後看哪句話更長就除以哪句話的字數。

同樣是A、B兩句話，共有詞的字元長度為4，最長句子長度為6，那麼4/6，≈0.667。

-------------------------------------------------

3、編輯距離

編輯距離（Edit Distance），又稱Levenshtein距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。一般來說，編輯距離越小，兩個串的相似度越大。由俄羅斯科學家Vladimir Levenshtein（找不到他照片233333）在1965年提出這個概念。

例如将“BABAY是個好人”轉成“BABY是個帥哥”，編輯舉例就是2（好人變帥哥隻要2就好...）： BABY是個帥人（好→帥） 

BABY是個帥哥（人→哥）

然後拿編輯距離去除以兩者之間的最大長度，2/6≈0.333，意味着隻要變動這麼多就可以從A變成B，是以不用變動的字元便代表了相似度，1-0.333＝0.667。

----------------------------------------------------------------

4、SimHash + 漢明距離

simhash是谷歌發明的算法，據說很nb，可以将一個文檔轉換成64位的位元組，然後我們可以通過判斷兩個位元組的漢明距離就知道是否相似了。

漢明距離是以理查德·衛斯裡·漢明的名字命名的。在資訊論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說，它就是将一個字元串變換成另外一個字元串所需要替換的字元個數。例如：

1011101 與 1001001 之間的漢明距離是 2。

"toned" 與 "roses" 之間的漢明距離是 3。

首先我們來計算SimHash：

① 提取文檔關鍵詞得到[word,weight]這樣一個數組。（舉例 [美國，4]）

② 用hash算法将word轉為固定長度的二進制值的字元串[hash(word),weight]。（舉例 [100101，4]）

③ word的hash從左到右與權重相乘，如果為1則乘以1 ，如果是0則曾以-1。（舉例4,-4,-4,4,-4,4）

④ 接着計算下個數，直到将所有分詞得出的詞計算完，然後将每個詞第三步得出的數組中的每一個值相加。（舉例美國和51區，[4,-4,-4,4,-4,4]和[5 -5 5 -5 5 5]得到[9 -9 1 -1 1 9]）

⑤ 對第四步得到的數組中每一個值進行判斷，如果＞0記為1，如果＜0記為0。（舉例[101011]）

第四步得出的就是這個文檔的SimHash。

這樣我們就能将兩個不同長度的文檔轉換為同樣長度的SimHash值，so，我們現在可以計算第一個文檔的值和第二個文檔的漢明距離（一般<3就是相似度高的）。

SimHash本質上是局部敏感性的hash（如果是兩個相似的句子，那麼隻會有部分不同），和md5之類的不一樣。 正因為它的局部敏感性，是以我們可以使用海明距離來衡量SimHash值的相似度。

如果想要小數形式的可以這麼做：1 - 漢明距離 / 最長關鍵詞數組長度。

---------------------------------------------------------

5、Jaccard相似性系數

Jaccard 系數，又叫Jaccard相似性系數，用來比較樣本集中的相似性和分散性的一個機率。Jaccard系數等于樣本集交集與樣本集合集的比值，即J = |A∩B| ÷ |A∪B|。

說白了就是交集除以并集，兩個文檔的共同都有的詞除以兩個文檔所有的詞。

---------------------------------------------

6、歐幾裡得距離

歐幾裡得距離是用得非常廣的公式，設A(x1, y1)，B(x2, y2)是平面上任意兩點那麼兩點間的距離距離(A,B)=平方根((x1-x2...)^2+(y1-y2....)^2)

我們可以拿兩個文檔所有的詞（不重複）在A文檔的詞頻作為x，在B文檔的作為y進行計算。

同樣拿A=你是個壞人、B=小明是個壞人 這兩句話作為例子，詞頻分别為A={1 0 1 1} 、B={0 1 1 1}。

那麼距離為根号2，≈ 1.414（餘3位）

然後可以通過1 ÷ (1 + 歐幾裡德距離)得到相似度。

---------------------------------------------------------------------

7、曼哈頓距離

曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼·闵可夫斯基所創詞彙，是種使用在幾何度量空間的幾何學用語，用以标明兩個點上在标準坐标系上的絕對軸距總和。

跟歐幾裡德距離有點像，簡單來說就是d(i,j)=|x1-x2...|+|y1-y2...|，同理xn和yn分别代表兩個文檔所有的詞（不重複）在A和B的詞頻。

然後可以通過1 ÷ (1 + 曼哈頓距離)得到相似度。

距離轉換相似度

score = 1 / (euclideanDistance+1)

文本相似度分值的取值範圍為[0, 1]，0表示完全不相似，說明比較的兩個文本之間沒有任何關系，1表示完全相似，說明比較的兩個文本其實是同一個文本的兩個副本。這個公式的目的是處理距離和文本相似度分值的關系，距離和文本相似度分值是反比的關系，距離越遠越不相似，距離趨于無窮大的時候，文本相似度分值趨于0，距離趨于或等于0的時候，文本相似度分值趨于或等于1。當然，當我們計算文本和自身的相似度的時候，我們期望的結果是完全相似，也就是完全等同，是以，距離等于0的時候，文本相似度分值等于1。

根據上述公式，當距離變量euclideanDistance==0的時候，score = 1 / (0+1)=1，相似度分值為1，表示比較的兩個文本其實是同一個文本，當距離變量euclideanDistance趨于無窮大的時候，score趨于0，表示兩個文本的相似度非常小。最後要說明的是，根據這個公式我們無法計算出相似度分值0，也就是說能計算出來的文本相似度分值的取值範圍為(0, 1]，任何兩個文本都存存或多或少的相似度。