使用jaccard距離計算文本相似度

1. 使用simhash計算文本相似度

2. 使用餘弦相似度計算文本相似度

3. 使用編輯距離計算文本相似度

4. jaccard系數計算文本相似度

4.1 jaccard系數

jaccard系數反映了兩個向量（元素取值為0或1）間的關系。即對于A⃗\vec AA和B⃗\vec BB，定義：

NA0B0N_{A_0B_0}NA0​B0​​ = A⃗\vec AA中元素值為0且B⃗\vec BB中元素值為0的個數

NA1B0N_{A_1B_0}NA1​B0​​ = A⃗\vec AA中元素值為1且B⃗\vec BB中元素值為0的個數

NA0B1N_{A_0B_1}NA0​B1​​ = A⃗\vec AA中元素值為0且B⃗\vec BB中元素值為1的個數

NA1B1N_{A_1B_1}NA1​B1​​ = A⃗\vec AA中元素值為1且B⃗\vec BB中元素值為1的個數

則 jaccard系數可以表示為：

J(A,B)=NA0B0+NA1B1NA0B0+NA1B0+NA0B1+NA1B1(1)J(A,B)=\frac{N_{A_0B_0}+N_{A_1B_1}}{N_{A_0B_0}+N_{A_1B_0}+N_{A_0B_1}+N_{A_1B_1}} (1)J(A,B)=NA0​B0​​+NA1​B0​​+NA0​B1​​+NA1​B1​​NA0​B0​​+NA1​B1​​​(1)

當向量中為0的元素遠大于為1的元素的個數時，NA0B0N_{A_0B_0}NA0​B0​​ 需要從計算中移除，而隻關注均為1的元素的個數。因為當NA0B0N_{A_0B_0}NA0​B0​​較大時，整個計算結果将區域穩定，無明顯特征了。是以以上公式變為：

J(A,B)=NA1B1NA1B0+NA0B1+NA1B1(2)J(A,B)=\frac{N_{A_1B_1}}{N_{A_1B_0}+N_{A_0B_1}+N_{A_1B_1}} (2)J(A,B)=NA1​B0​​+NA0​B1​​+NA1​B1​​NA1​B1​​​(2)

另一種用集合表示的方法：

J(A,B)=∣A⋂B∣∣A⋃B∣=∣A⋂B∣∣A∣+∣B∣−∣A⋂B∣(3)J(A,B)=\frac{|A\bigcap{B}|}{|A\bigcup{B}|}=\frac{|A\bigcap{B}|}{|A|+|B|-|A\bigcap{B}|}(3)J(A,B)=∣A⋃B∣∣A⋂B∣​=∣A∣+∣B∣−∣A⋂B∣∣A⋂B∣​(3)

4.2 jaccard系數相似度

jaccard系數值越大，相似度越高，另一種說法是用jaccard距離表示相似度即：1−J(A,B)1-J(A,B)1−J(A,B)，本質一樣，但jaccard距離越大相似度越小。

一般的 jaccard系數隻适用于計算元素取值為0或1的集合，但是要注意的是這裡取值為0或1并不是值集合中的值為0或1，而僅僅是集合中元素的取值為0或1，而計算出的jaccard系數是和元素本身相關的。

4.2.1 jaccard系數衡量次元相似性

jaccard系數很适合用來分析多個次元間的相似性，也多被用于推薦系統中用來給使用者推薦相似的産品或業務。

舉個例子，要計算某網站的兩個使用者的相似性，可以從性别、地區、年齡、浏覽時間等等次元進行分析，我們把這些次元再進行細化：

男性、女性、小于18歲、18歲-40歲、40歲以上、浏覽時間為早上、浏覽時間為中午、浏覽時間為下午

将以上次元作為一個集合，對兩個使用者AAA和BBB，将符合以上次元的名額值置為1，其他置為0。

假設使用者AAA=[男性=1, 女性=0, 小于18歲=0, 18歲-40歲=1, 40歲以上=0, 浏覽時間為早上=0, 浏覽時間為中午=0, 浏覽時間為下午=1]

假設使用者BBB=[男性=1, 女性=0, 小于18歲=1, 18歲-40歲=0, 40歲以上=0, 浏覽時間為早上=0, 浏覽時間為中午=0, 浏覽時間為下午=1]

即他們隻有年齡不同，則根據計算公式，得到的jaccard系數值為：

J(A,B)=NA1B1NA1B0+NA0B1+NA1B1=24=0.5J(A,B)=\frac{N_{A_1B_1}}{N_{A_1B_0}+N_{A_0B_1}+N_{A_1B_1}}=\frac{2}{4}=0.5J(A,B)=NA1​B0​​+NA0​B1​​+NA1​B1​​NA1​B1​​​=42​=0.5

即他們的相似度為0.5

用matlab驗證下：

4.2.1 jaccard系數衡量文本相似性

雖然jaccard主要是在次元分析這樣的稀疏向量中作用比較大，但是在文本相似度計算時也可用jaccard。

仍然用之前的文本作為輸入樣本：

樣本1：今天天氣真好

樣本2：今天天氣不錯

首先要做的還是分詞：

A = [今天,天氣,真好]

B = [今天,天氣,不錯]

J(A,B)=∣A⋂B∣∣A⋃B∣=24=0.5J(A,B)=\frac{|A\bigcap{B}|}{|A\bigcup{B}|}=\frac{2}{4}=0.5J(A,B)=∣A⋃B∣∣A⋂B∣​=42​=0.5

4.3 jaccard系數計算實作(java)

public static double jaccard(String s1, String s2) {
        List<String> words1 = splitWords(s1);
        List<String> words2 = splitWords(s2);

        List<String> temp = new ArrayList<>();
        temp.addAll(words1);
        temp.addAll(words2);
        List<String> union = temp.stream().distinct().collect(Collectors.toList());
        List<String> intersect = new ArrayList<>();

        List<String> a = words1.stream().
                map(x -> words2.contains(x) ? x : null).
                collect(Collectors.toList());

        List<String> b = words2.stream().
                map(x -> words1.contains(x) ? x : null).
                collect(Collectors.toList());

        intersect.addAll(a);
        intersect.addAll(b);
        intersect = intersect.stream().distinct().collect(Collectors.toList());
        intersect.removeAll(Collections.singleton(null));

        return 1.0 * intersect.size() / union.size();
    }
           

4.4 總結

網絡上志同道合，我們一起學習網絡安全，一起進步，QQ群：694839022