本文側(cè)重講述邏輯和使用場(chǎng)景，嘗試將算法通俗化，盡量多舉例，降低理解門檻。希望讀完本文，大家可以對(duì)文本相似度有一個(gè)完整而深刻的理解，最好能在非代碼維度上超過(guò)開(kāi)發(fā)人員（達(dá)到了這種水平，輸出的需求自然會(huì)得到開(kāi)發(fā)同學(xué)最大的尊重和認(rèn)同）。
1. 背景介紹
因?yàn)橹白鲞^(guò)個(gè)性化推薦相關(guān)的項(xiàng)目，最近產(chǎn)品的其中一個(gè)模塊也需要用到文本相似度，趁此機(jī)會(huì)做一個(gè)全面的整理。
CSDN及各類技術(shù)博客上有很多文本相似度方面的文章，但它們的側(cè)重點(diǎn)是代碼，目標(biāo)受眾是開(kāi)發(fā)人員，代碼基礎(chǔ)薄弱的話看起來(lái)會(huì)比較吃力。
本文側(cè)重講述邏輯和使用場(chǎng)景，嘗試將算法通俗化，盡量多舉例，降低理解門檻。希望讀完本文，大家可以對(duì)文本相似度有一個(gè)完整而深刻的理解，最好能在非代碼維度上超過(guò)開(kāi)發(fā)人員（達(dá)到了這種水平，輸出的需求自然會(huì)得到開(kāi)發(fā)同學(xué)最大的尊重和認(rèn)同）。
文本相似度，顧名思義是指兩個(gè)文本（文章）之間的相似度，在搜索引擎、推薦系統(tǒng)、論文鑒定、機(jī)器翻譯、自動(dòng)應(yīng)答、命名實(shí)體識(shí)別、拼寫(xiě)糾錯(cuò)等領(lǐng)域有廣泛的應(yīng)用。
總的來(lái)說(shuō)，文本相似度是自然語(yǔ)言處理（NLP）中必不可少的重要環(huán)節(jié)，幾乎所有NLP的領(lǐng)域都會(huì)涉及到！
與之相對(duì)應(yīng)的，還有一個(gè)概念——文本距離——指的是兩個(gè)文本之間的距離。文本距離和文本相似度是負(fù)相關(guān)的——距離小，“離得近”，相似度高；距離大，“離得遠(yuǎn)”，相似度低。業(yè)務(wù)上不會(huì)對(duì)這兩個(gè)概念進(jìn)行嚴(yán)格區(qū)分，有時(shí)用文本距離，有時(shí)則會(huì)用文本相似度。
2. 各類算法
2.1 歐氏距離
數(shù)學(xué)中的一個(gè)非常經(jīng)典的距離，公式如下：
例1：計(jì)算“產(chǎn)品經(jīng)理”和“產(chǎn)業(yè)經(jīng)理是什么”之間的歐氏距離
過(guò)程如下：
- 文本向量A=（產(chǎn)，品，經(jīng)，理），即x1=產(chǎn)，x2=品，x3=經(jīng)，x4=理，x5、x6、x7均為空；
- 文本向量B=（產(chǎn)，業(yè)，經(jīng)，理，是，什，么），即y1=產(chǎn)，y2=業(yè)，y3=經(jīng)，y4=理，y5=是，y6=什，y7=么。
這里規(guī)定，若xi=yi，則xi-yi=0；
若xi≠yi，|xi-yi|=1。
所以，歐氏距離是2
（1）適用場(chǎng)景
編碼檢測(cè)等類似領(lǐng)域。兩串編碼必須完全一致，才能通過(guò)檢測(cè)，這時(shí)一個(gè)移位或者一個(gè)錯(cuò)字，可能會(huì)造成非常嚴(yán)重的后果。比如下圖第一個(gè)二維碼是“這是一篇文本相似度的文章”，第二個(gè)是“這是一篇文本相似度文章”。從人的理解來(lái)看，這兩句話相似度非常高，但是生成的二維碼卻千差萬(wàn)別。
掃描后，顯示“這是一個(gè)文本相似度文章”
掃描后，顯示“這是一個(gè)文本相似度的文章”
（2）不適用場(chǎng)景
文本相似度，意味著要能區(qū)分相似/差異的程度，而歐氏距離更多的只能區(qū)分出是否完全一樣。而且，歐氏距離對(duì)位置、順序非常敏感，比如“我的名字是孫行者”和“孫行者是我的名字”，在人看來(lái)，相似度非常高，但是用歐氏距離計(jì)算，兩個(gè)文本向量每個(gè)位置的值都不同，即完全不匹配。
2.2 曼哈頓距離
和歐氏距離非常相似（把平方換成了絕對(duì)值，拿掉了根號(hào)），公式如下：
適用場(chǎng)景同歐氏距離。
2.3?編輯距離（Levenshtein距離、萊文斯坦距離）
顧名思義，編輯距離指的是將文本A編輯成文本B需要的最少變動(dòng)次數(shù)（每次只能增加、刪除或修改一個(gè)字）。
例2：計(jì)算“椰子”和“椰子樹(shù)”之間的編輯距離。
因?yàn)閷ⅰ耙印鞭D(zhuǎn)化成“椰子樹(shù)”，至少需要且只需要1次改動(dòng)（反過(guò)來(lái)，將“椰子樹(shù)”轉(zhuǎn)化成“椰子”，也至少需要1次改動(dòng)，如下圖），所以它們的編輯距離是1。
因此，編輯距離是對(duì)稱的，即將A轉(zhuǎn)化成B的最小變動(dòng)次數(shù)和將B轉(zhuǎn)化成A的最小變動(dòng)次數(shù)是相等的。
同時(shí)，編輯距離與文本的順序有關(guān)。
比如，“椰子”和“子椰”，雖然都是由“椰”“子”組成，但因?yàn)轫樞蜃兞?，編輯距離是2（如下圖），而不是0。
（1）適用場(chǎng)景
編輯距離算出來(lái)很小，文本相似度肯定很高。如果用算法語(yǔ)言來(lái)說(shuō)的話，就是精確率很高（即雖然會(huì)漏掉一些好的case，但可以確保選出來(lái)的case一定非常好）。
（2）不適用場(chǎng)景
反過(guò)來(lái)說(shuō)，雖然精確率很高，但召回率不高（準(zhǔn)確率、精確率、召回率的定義見(jiàn)文章底部外鏈）。在某些業(yè)務(wù)場(chǎng)景中，漏掉的case會(huì)引起嚴(yán)重后果，比如“批發(fā)零售”和“零售批發(fā)”，人的理解應(yīng)該非常相似，可編輯距離卻是4，相當(dāng)于完全不匹配，這顯然不符合預(yù)期。
2.4 Jaccard相似度（杰卡德相似度）
杰卡德相似度，指的是文本A與文本B中交集的字?jǐn)?shù)除以并集的字?jǐn)?shù)，公式非常簡(jiǎn)單：
例3：計(jì)算“荒野求生”和“絕地求生”的杰卡德相似度。
因?yàn)樗鼈兘患莧求，生}，并集是{荒，野，求，生，絕，地}，所以它們的杰卡德相似度=2/6=1/3。
杰卡德相似度與文本的位置、順序均無(wú)關(guān)，比如“王者榮耀”和“榮耀王者”的相似度是100%。無(wú)論“王者榮耀”這4個(gè)字怎么排列，最終相似度都是100%。
在某些情況下，會(huì)先將文本分詞，再以詞為單位計(jì)算相似度。比如將“王者榮耀”切分成“王者/榮耀”，將“榮耀王者”切分成“榮耀/王者”，那么交集就是{王者，榮耀}，并集也是{王者，榮耀}，相似度恰好仍是100%。
（1）適用場(chǎng)景
- 對(duì)字/詞的順序不敏感的文本，比如前述的“零售批發(fā)”和“批發(fā)零售”，可以很好地兼容。
- 長(zhǎng)文本，比如一篇論文，甚至一本書(shū)。如果兩篇論文相似度較高，說(shuō)明交集比較大，很多用詞是重復(fù)的，存在抄襲嫌疑。
（2）不適用場(chǎng)景
- 重復(fù)字符較多的文本，比如“這是是是是是是一個(gè)文本”和“這是一個(gè)文文文文文文本”，這兩個(gè)文本有很多字不一樣，直觀感受相似度不會(huì)太高，但計(jì)算出來(lái)的相似度卻是100%（交集=并集）。
- 對(duì)文字順序很敏感的場(chǎng)景，比如“一九三八年”和“一八三九年”，杰卡德相似度是100%，意思卻完全不同。
如果要計(jì)算Jaccard距離，公式稍作變更即可：
2.5 余弦相似度
余弦相似度的靈感來(lái)自于數(shù)學(xué)中的余弦定理，這里對(duì)數(shù)學(xué)內(nèi)容不做過(guò)多解釋，直接上公式：
其中，A、B分別是文本一、文本二對(duì)應(yīng)的n維向量，取值方式用語(yǔ)言比較難描述，直接看例子吧：
例4：文本一是“一個(gè)雨傘”，文本二是“下雨了開(kāi)雨傘”，計(jì)算它們的余弦相似度。
它們的并集是{一，個(gè)，雨，傘，下，了，開(kāi)}，共7個(gè)字。
- 若并集中的第1個(gè)字符在文本一中出現(xiàn)了n次，則A1=n（n=0，1，2……）。
- 若并集中的第2個(gè)字符在文本一中出現(xiàn)了n次，則A2=n（n=0，1，2……）。
依此類推，算出A3、A4、……、A7，B1、B2、……、B7，最終得到：
- A=（1，1，1，1，0，0，0）。
- B=（0，0，2，1，1，1，1）。
將A、B代入計(jì)算公式，得到
（1）適用場(chǎng)景
余弦相似度和杰卡德相似度雖然計(jì)算方式差異較大，但性質(zhì)上很類似（與文本的交集高度相關(guān)），所以適用場(chǎng)景也非常類似。
余弦相似度相比杰卡德相似度最大的不同在于它考慮到了文本的頻次，比如上面例子出現(xiàn)了2次“雨”，和只出現(xiàn)1次“雨”，相似度是不同的；再比如“這是是是是是是一個(gè)文本”和“這是一個(gè)文文文文文文本”，余弦相似度是39%，整體上符合“相同的內(nèi)容少于一半，但超過(guò)1/3”的觀感（僅從文本來(lái)看，不考慮語(yǔ)義）。
（2）不適用場(chǎng)景
向量之間方向相同，但大小不同的情況（這種情況下余弦相似度是100%）。
比如“太棒了”和“太棒了太棒了太棒了”，向量分別是（1，1，1）和（3，3，3），計(jì)算出的相似度是100%。這時(shí)候要根據(jù)業(yè)務(wù)場(chǎng)景進(jìn)行取舍，有些場(chǎng)景下我們認(rèn)為它們意思差不多，只是語(yǔ)氣程度不一樣，這時(shí)候余弦相似度是很給力的；有些場(chǎng)景下我們認(rèn)為它們差異很大，哪怕意思差不多，但從文本的角度來(lái)看相似度并不高（最直白的，一個(gè)3個(gè)字，一個(gè)9個(gè)字），這時(shí)候余弦相似度就愛(ài)莫能助了。
2.6 Jaro相似度
Jaro相似度據(jù)說(shuō)是用來(lái)判定健康記錄上兩個(gè)名字是否相同，公式如下：
其中，m是兩個(gè)字符串中相互匹配的字符數(shù)量；|s1|和|s2|表示兩個(gè)字符串的長(zhǎng)度（字符數(shù)量）；t是換位數(shù)量。
這里著重說(shuō)一下“匹配”和“換位”的概念，先列一個(gè)公式，我稱之為“匹配閾值”：
當(dāng)s1中某字符與s2中某字符相同，且它們的位置相距小于等于k時(shí)，就說(shuō)它們是匹配的。
比如“我明白了”和“快一點(diǎn)告訴我”，按公式算出k=2。雖然兩個(gè)字符串中都有“我”字，但一個(gè)在第1位，另一個(gè)在第6位，相距為5，大于k值，所以這兩個(gè)字符串沒(méi)有任何一個(gè)字符是匹配的。
再比如“我明白了”和“明白了我”，k=1，所以這兩個(gè)字符串的“明”“白”“了”是匹配的，但是“我”是不匹配的，所以它們有3個(gè)字符是匹配的。
換位的意思，是將s1和s2匹配的字符依次抽出來(lái)，看它們順序不一樣的字符有多少個(gè)，這個(gè)數(shù)就是換位數(shù)量。
例5：計(jì)算“我表白了一個(gè)女孩”和“近幾天我白表了一次情”的Jaro相似度。
|s1|=8，|s2|=10，k=4，匹配的字符有5個(gè)，即m=5，分別是“我”“表”“白”“了”“一”。
將s1中的匹配字符依次抽出來(lái)，得到一個(gè)向量r1=（我，表，白，了，一）。
將s2中的匹配字符依次抽出來(lái)，得到一個(gè)向量r2=（我，白，表，了，一）。
比對(duì)r1和r2，發(fā)現(xiàn)有2個(gè)位置的值不一樣（第2位和第3位），所以換位數(shù)t=2。
于是，d=1/3[5/8+5/10+(5-2)/5]=57.5%。
（1）適用場(chǎng)景
對(duì)位置、順序敏感的文本。
文本位置的偏移，很容易使匹配字符數(shù)m變少；文本順序的變換，會(huì)使換位數(shù)量t增大。它們都會(huì)使Jaro相似度減小。換句話說(shuō)，如果某業(yè)務(wù)場(chǎng)景下需要考慮文本位置偏移、順序變換的影響，既不希望位置或順序變了相似度卻保持不變，又不希望直接一刀切將相似度變?yōu)?，那Jaro距離是十分合適的。
（2）不適用場(chǎng)景
未知（什么！作者這么任性的嗎？）。
其實(shí)，我自己確實(shí)沒(méi)想清楚，也沒(méi)有在實(shí)踐中使用過(guò)這個(gè)算法。
整體來(lái)說(shuō)，Jaro距離是比較綜合的文本相似度算法，從換位字符數(shù)來(lái)看，有點(diǎn)像編輯距離；從匹配字符的抽取來(lái)看，又有點(diǎn)像“交集”。
最后，對(duì)例5做個(gè)橫向?qū)Ρ龋?/p>
- 編輯距離算出來(lái)是8，s1長(zhǎng)度是8，s2長(zhǎng)度是10，編輯距離等于8，從數(shù)據(jù)上看非常不相似，與人的感官差異很大。
- 杰卡德相似度算出來(lái)是38.5%，數(shù)值比較低，和人的感官差異較大。
- 余弦相似度算出來(lái)是55.9%，和Jaro距離算出來(lái)差不多，都是50%+，比較符合人的感官——超過(guò)一半的內(nèi)容是相同的，同時(shí)有將近一半內(nèi)容是不同的。
- 如果在此例中，調(diào)整字符順序，讓換位數(shù)量t變大，匹配數(shù)量m變小，余弦相似度不變，Jaro相似度會(huì)降低。
3. 拓展閱讀
3.1 名詞解釋
算法中的重要概念（指標(biāo)）——準(zhǔn)確率、精確率、召回率。其中準(zhǔn)確率和精確率很容易混淆，詳細(xì)差別可以點(diǎn)開(kāi)以下鏈接：http://t.cn/R6y8ay9
3.2 貝葉斯公式
NLP領(lǐng)域，我個(gè)人認(rèn)為有兩個(gè)非常重要的、頻繁出現(xiàn)的基本公式，一個(gè)是前述的文本相似度，另一個(gè)就是貝葉斯公式了。對(duì)這塊有興趣的同學(xué)，可以閱讀下文：http://t.cn/haY0x
作者寫(xiě)的非常易于理解——我在《深度學(xué)習(xí)》這本書(shū)里看NLP相關(guān)內(nèi)容時(shí)，有幾個(gè)公式怎么都理解不了，看這篇文章簡(jiǎn)直是秒懂。
3.3 代碼
編輯距離的代碼見(jiàn)百度百科最底部，有興趣的同學(xué)可以擴(kuò)展閱讀：http://t.cn/R850kBe
余弦相似度的代碼見(jiàn)這篇CSDN博客 ，寫(xiě)的比較詳細(xì)：http://t.cn/R850ru8
切記，一定要在電腦上打開(kāi)鏈接查看代碼（別問(wèn)我怎么知道的）。
PS. 代碼這一塊我就意思一下，不是重點(diǎn)，不再每個(gè)算法都一一列舉了。
作者：Insight，“AI產(chǎn)品經(jīng)理大本營(yíng)”成員之一
本文由人人都是產(chǎn)品經(jīng)理專欄作家?@黃釗?授權(quán)發(fā)布于人人都是產(chǎn)品經(jīng)理，未經(jīng)作者許可，禁止轉(zhuǎn)載。
題圖由作者提供
愛(ài)盈利-運(yùn)營(yíng)小咖秀(www.jza6.com) 始終堅(jiān)持研究分享移動(dòng)互聯(lián)網(wǎng)App運(yùn)營(yíng)推廣經(jīng)驗(yàn)、策略、全案、渠道等純干貨知識(shí)內(nèi)容；是廣大App運(yùn)營(yíng)從業(yè)者的知識(shí)啟蒙、成長(zhǎng)指導(dǎo)、進(jìn)階學(xué)習(xí)的集聚平臺(tái)；
想了解更多移動(dòng)互聯(lián)網(wǎng)干貨知識(shí)，請(qǐng)關(guān)注微信公眾號(hào)運(yùn)營(yíng)小咖秀（ID: yunyingshow）
