文本相似度余弦值相似度算法 VS L氏編輯距離（動態規劃）

fxp 發布于2019-06-28 11:05 / 1981人閱讀

摘要：本文對兩種文本相似度算法進行比較。余弦值相似度算法最小編輯距離法氏編輯距離基于詞條空間編輯距離，又稱距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。但是同時也可以看出余弦相似度得到的結果相對比較高一些。

本文由作者祝娜授權網易云社區發布。

本文對兩種文本相似度算法進行比較。余弦值相似度算法 VS 最小編輯距離法
1、L氏編輯距離（基于詞條空間）
編輯距離（Edit Distance），又稱Levenshtein距離，是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。

算法實現步驟:

1 設置n為字符串s的長度。("我是個小仙女")
設置m為字符串t的長度。("我不是個小仙女")
如果n等于0，返回m并退出。
如果m等于0，返回n并退出。
構造兩個向量v0[m+1] 和v1[m+1]，串聯0..m之間所有的元素。
2 初始化 v0 to 0..m。
3 檢查 s (i from 1 to n) 中的每個字符。
4 檢查 t (j from 1 to m) 中的每個字符
5 如果 s[i] 等于 t[j]，則編輯代價cost為 0；
如果 s[i] 不等于 t[j]，則編輯代價cost為1。
6 設置單元v1[j]為下面的最小值之一：
a、緊鄰該單元上方+1：v1[j-1] + 1
b、緊鄰該單元左側+1：v0[j] + 1
c、該單元對角線上方和左側+cost：v0[j-1] + cost
7 在完成迭代 (3, 4, 5, 6) 之后，v1[m]便是編輯距離的值。

我們得到最小編輯距離為1那么它們的相似度為 (1-ld/(double)Math.max(str1.length(), str2.length()));

1 - 1/8=7/8.

其算法實現（java）：

public static float levenshtein(String str1,String str2) {  
    //計算兩個字符串的長度。  
    int len1 = str1.length();  
    int len2 = str2.length();  
    //建立上面說的數組，比字符長度大一個空間  
    int[][] dif = new int[len1 + 1][len2 + 1];  
    //賦初值，步驟B。  
    for (int a = 0; a <= len1; a++) {  
        dif[a][0] = a;  
    }  
    for (int a = 0; a <= len2; a++) {  
        dif[0][a] = a;  
    }  
    //計算兩個字符是否一樣，計算左上的值  
    int temp;  
    for (int i = 1; i <= len1; i++) {  
        for (int j = 1; j <= len2; j++) {  
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {  
                temp = 0;  
            } else {  
                temp = 1;  
            }  
            //取三個值中最小的  
            dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,  
                    dif[i - 1][j] + 1);  
        }  
    }  

    float similarity =1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());  
    return similarity;
}

2、余弦值（基于權值空間）

關于余弦相似度可以參照百度詞條余弦相似度

通過測量兩個向量之間的角的余弦值來度量它們之間的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1;并且其最小值是-1。從而兩個向量之間的角度的余弦值確定兩個向量是否大致指向相同的方向。所以，它通常用于文件比較。

算法步驟
預處理→文本特征項選擇→加權→生成向量空間模型后計算余弦。

具體步驟見附件：余弦相似度算法步驟解釋.docx
其算法實現（java）:

public static double getSimilarity(String doc1, String doc2) { if (doc1 != null && doc1.trim().length() > 0 && doc2 != null && doc2.trim().length() > 0) {

        MapAlgorithmMap = new HashMap();            // 將兩個字符串中的中文字符以及出現的總數封裝到，AlgorithmMap中
        for (int i = 0; i < doc1.length(); i++) {                char d1 = doc1.charAt(i);                if (isHanZi(d1)) {                    int charIndex = getGB2312Id(d1);                    if (charIndex != -1) {                        int[] fq = AlgorithmMap.get(charIndex);                        if (fq != null && fq.length == 2) {
                        fq[0]++;
                    } else {
                        fq = new int[2];
                        fq[0] = 1;
                        fq[1] = 0;
                        AlgorithmMap.put(charIndex, fq);
                    }
                }
            }
        }            for (int i = 0; i < doc2.length(); i++) {                char d2 = doc2.charAt(i);                if (isHanZi(d2)) {                    int charIndex = getGB2312Id(d2);                    if (charIndex != -1) {                        int[] fq = AlgorithmMap.get(charIndex);                        if (fq != null && fq.length == 2) {
                        fq[1]++;
                    } else {
                        fq = new int[2];
                        fq[0] = 0;
                        fq[1] = 1;
                        AlgorithmMap.put(charIndex, fq);
                    }
                }
            }
        }

        Iteratoriterator = AlgorithmMap.keySet().iterator();            double sqdoc1 = 0;            double sqdoc2 = 0;            double denominator = 0;            while (iterator.hasNext()) {                int[] c = AlgorithmMap.get(iterator.next());
            denominator += c[0] * c[1];
            sqdoc1 += c[0] * c[0];
            sqdoc2 += c[1] * c[1];
        }            double origin = denominator / Math.sqrt(sqdoc1 * sqdoc2);            if (String.valueOf(origin).equals("NaN")) {                return Double.valueOf("0");
        }
        BigDecimal bg = new BigDecimal(origin);            double f1 = bg.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue();            return f1;
    } else {            throw new NullPointerException(" the Document is null or have not cahrs!!");
    }
}    public static boolean isHanZi(char ch) {        // 判斷是否漢字
    return (ch >= 0x4E00 && ch <= 0x9FA5);

}    /**
 * 根據輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，
 *
 * @param ch
 *            輸入的GB2312中文字符或者ASCII字符(128個)
 * @return ch在GB2312中的位置，-1表示該字符不認識
 */
public static short getGB2312Id(char ch) {        try {            byte[] buffer = Character.toString(ch).getBytes("GB2312");            if (buffer.length != 2) {                // 正常情況下buffer應該是兩個字節，否則說明ch不屬于GB2312編碼，故返回"?"，此時說明不認識該字符
            return -1;
        }            int b0 = (buffer[0] & 0x0FF) - 161; // 編碼從A1開始，因此減去0xA1=161
        int b1 = (buffer[1] & 0x0FF) - 161; // 第一個字符和最后一個字符沒有漢字，因此每個區只收16*6-2=94個漢字
        return (short) (b0 * 94 + b1);
    } catch (UnsupportedEncodingException e) {
        e.printStackTrace();
    }        return -1;
}

現在對兩種計算相似度的算法進行比較：

編輯距離相似度運行結果：

"第六章字符編碼" 與 "第一章設計模式" 的相似度為:0.07159507274627686

"第六章字符編碼" 與 "第二章 python學習" 的相似度為:0.06676656007766724

"第六章字符編碼" 與 "第三章 python簡介" 的相似度為:0.08275055885314941

"第六章字符編碼" 與 "第四章輸入輸出" 的相似度為:0.1878122091293335

"第六章字符編碼" 與 "第五章數據類型和變量" 的相似度為:0.20358151197433472

"第六章字符編碼" 與 "第六章字符編碼" 的相似度為:1.0

"第六章字符編碼" 與 "第七章 list" 的相似度為:0.20995670557022095

runtime:989毫秒

L編輯距離的時間算法采用矩陣的方式，計算兩個字符串之間的變化步驟，會遍歷兩個文本中的每一個字符兩兩比較，可以推斷出時間復雜度至少為 document1.length × document2.length

cos相似度運行結果:

"第六章字符編碼" 與 "第一章設計模式" 的相似度為:0.5

"第六章字符編碼" 與 "第二章 python學習" 的相似度為:0.59

"第六章字符編碼" 與 "第三章 python簡介" 的相似度為:0.68

"第六章字符編碼" 與 "第四章輸入輸出" 的相似度為:0.62

"第六章字符編碼" 與 "第五章數據類型和變量" 的相似度為:0.72

"第六章字符編碼" 與 "第六章字符編碼" 的相似度為:1.0

"第六章字符編碼" 與 "第七章 list" 的相似度為:0.59

runtime:400毫秒

使用余弦定理計算文本效率相對比較高：其算法復雜度大致為：document1.length + document2.length。

但是同時也可以看出余弦相似度得到的結果相對比較高一些。使用分詞或者過濾掉一些常用詞會對結果的準確性更有利。

使用分詞的方法在本文中沒有展開。但是如果去掉文章里的“的、了、吧，呢、啊”等可以提高結果的準確率。當然同時也可以提高判斷的閥值。

運行結果：

"第六章字符編碼" 與 "第一章設計模式" 的相似度為:0.37

"第六章字符編碼" 與 "第二章 python學習" 的相似度為:0.48

"第六章字符編碼" 與 "第三章 python簡介" 的相似度為:0.57

"第六章字符編碼" 與 "第四章輸入輸出" 的相似度為:0.56

"第六章字符編碼" 與 "第五章數據類型和變量" 的相似度為:0.67

"第六章字符編碼" 與 "第六章字符編碼" 的相似度為:1.0

"第六章字符編碼" 與 "第七章 list" 的相似度為:0.48

runtime:519毫秒

看以看出準確度有了一定的提高。

番外：

L編輯距離動態計算法，調用python腳本實現，腳本文件

author = "victor"

-- coding:utf-8 --

import sys

import Levenshtein

if name == "__main__":

if(len(sys.argv) < 3):

    print("Usage: python myratiodetect.py str1 str2")

    exit(-1)

str1 = sys.argv[1]

str2 = sys.argv[2]

r = Levenshtein.ratio(str1, str2)

print(r)

exit(0)

本地運行的前提為：已經適應pip安裝了：python_Levenshtein，所以其對服務器的依賴比較大，如果工程環境遷移了的話，會比較受影響。

程序的運行結果：

"第六章字符編碼" 與 "第一章設計模式" 的相似度為:0.157063851181

"第六章字符編碼" 與 "第二章 python學習" 的相似度為:0.165801038753

"第六章字符編碼" 與 "第三章 python簡介" 的相似度為:0.194563908481

"第六章字符編碼" 與 "第四章輸入輸出" 的相似度為:0.268671351528

"第六章字符編碼" 與 "第五章數據類型和變量" 的相似度為:0.300997688969

"第六章字符編碼" 與 "第六章字符編碼" 的相似度為:1.0

"第六章字符編碼" 與 "第七章 list" 的相似度為:0.296406739228

runtime:2247毫秒

運行速度.....比較慢..2333

參考：

https://www.2cto.com/kf/20140...

http://wdhdmx.iteye.com/blog/...

http://blog.sina.com.cn/s/blo...

更多網易技術、產品、運營經驗分享請訪問網易云社區。
文章來源：網易云社區

GPU云服務器云服務器最好的文本相似度算法余弦相似度c語言人臉相似度比對算法字符串相似度算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/25320.html

推薦系統01--余弦相似度

摘要：在近鄰推薦中，最常用的相似度是余弦相似度。這就是由于余弦相似度被向量長度歸一化后的結果。用余弦相似度計算出來，兩個用戶的相似度達到。余弦相似度適用于評分數據，杰卡德相似度適合用于隱式反饋數據。今天，我們來聊聊協同過濾中的相似度計算方法有哪些。相似度的本質推薦系統中，推薦算法分為兩個門派，一個是機器學習派，另一個就是相似度門派。機器學習派是后起之秀，而相似度派則是泰山北斗，以致撐起來推...

cncoder 2019-07-31 11:07 評論0 收藏0
Move Mirror：使用 TensorFlow.js 在瀏覽器中預測姿勢之 AI 實驗

摘要：文和，創意實驗室創意技術專家在機器學習和計算機視覺領域，姿勢預測或根據圖像數據探測人體及其姿勢的能力，堪稱最令人興奮而又最棘手的一個話題。使用，用戶可以直接在瀏覽器中運行機器學習模型，無需服務器。文 / ?Jane Friedhoff 和 Irene Alvarado，Google 創意實驗室創意技術專家在機器學習和計算機視覺領域，姿勢預測或根據圖像數據探測人體及其姿勢的能力，堪稱最令人興...

MiracleWong 2019-04-25 18:28 評論0 收藏0
基于TensorFlow理解三大降維技術：PCA、t-SNE 和自編碼器

摘要：代碼地址在這篇文章中，我將盡我所能揭秘三種降維技術和自編碼器。動機當處理真實問題和真實數據時，我們往往遇到維度高達數百萬的高維數據。盡管在其原來的高維結構中，數據能夠得到較好的表達，但有時候我們可能需要給數據降維。代碼地址：https://github.com/eliorc/Medium/blob/master/PCA-tSNE-AE.ipynb在這篇文章中，我將盡我所能揭秘三種降維技術：...

Wildcard 2019-04-25 18:17 評論0 收藏0
自然語言處理真實項目實戰

摘要：在自然語言處理中，一個很重要的技術手段就是將文檔轉換為一個矢量，這個過程一般是使用這個庫進行處理的。自然語言處理中，一般來說，代表詞。自然語言預處理中，一個很重要的步驟就是將你收集的句子進行分詞，將一個句子分解成詞的列表。前言本文根據實際項目撰寫，由于項目保密要求，源代碼將進行一定程度的刪減。本文撰寫的目的是進行公司培訓，請勿以任何形式進行轉載。由于是日語項目，用到的分詞軟件等，在...

王巖威 2019-07-30 17:03 評論0 收藏0
[論文簡讀] Web Content Extraction Using Clustering

摘要：實驗結果實驗數據集數據集都是新聞類網頁，從五個中文新聞網站中收集一百個頁面這最多也就五類吧，而且也就五百個，好像有點少了吧結果與驗證性能指標這這這比較文本長度就了那不是只要包含新聞正文不就好了。《Web Content Extraction Using Clustering with Web Structure》引用 Huang X, Gao Y, Huang L, et al. ...

levinit 2019-08-23 10:49 評論0 收藏0