计算文本相似度
簡單講解
上一章有提到過[基于關鍵詞的空間向量模型]的算法，將用戶的喜好以文檔描述并轉換成向量模型，對商品也是這么處理，然后再通過計算商品文檔和用戶偏好文檔的余弦相似度。
文本相似度計算在信息檢索、數據挖掘、機器翻譯、文檔復制檢測等領域有著廣泛的應用。
比如輿論控制，我們假設你開發了一個微博網站，并且已經把世界上罵人的句子都已經收錄進了數據庫，那么當一個用戶發微博時會先跟罵人句子的數據庫進行比較，如果符合里面的句子就不讓用戶發出。
通常情況下，很多工程師就會想到用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(只余3位)，可以百度"2除以(根號3乘以根號3)"看到計算結果。
余弦值越接近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 + 曼哈頓距離)得到相似度。
其它
公式生成工具：http://private.codecogs.com/latex/eqneditor.php
總結
- 上一篇： LambdaMART的思想
- 下一篇： Solr相似度算法一：Lucene TF