程式狂想筆記
首頁 文章 標籤 分類 好站連結
程式狂想筆記

Contents

探索陣列與字串相似度比較方法

 included in 程式心法
   459 words   3 minutes 
https://gist.github.com/assets/6058558/57614585-8a83-46d9-9c64-7dfe71bd4f48

最近要產敏要做相似度功能，目前沒有大數據平台串接，所以用貼標方式去做相似度。但要怎麼做到這個功能，SA 提出用字串串接相似度來判斷，我覺得滿有趣，找出一些網路上案例，看看他們怎麼做。

相關文章

大概有用字串、陣列方式去算比較方法。

用 Jaccard 相似度去算

這篇簡單 C# 實作，後面的用 Jaccard 和 Cosine 的 ArrayComparer 類別可以取代物件做測試。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

using System;
using System.Linq;

public class ArrayComparer
{
    public int CalculateSimilarity(int[] array1, int[] array2)
    {
        // 計算兩個陣列中相同元素的數量
        var commonElementsCount = array1.Intersect(array2).Count();

        // 計算兩個陣列中元素的總數，去除重複元素
        var totalElementsCount = array1.Union(array2).Count();

        // 計算並返回相似度百分比
        var similarity = (int)((double)commonElementsCount / totalElementsCount * 100);
        return similarity;
    }
}

1
2
3

var comparer = new ArrayComparer();
int similarity = comparer.CalculateSimilarity(new int[] { 1, 2, 3, 4 }, new int[] { 4, 3, 2, 1 });
Console.WriteLine(similarity);  // 輸出：100

LinqPad 測試連結

最後我使用 SQL 算統計相似度，沒用到上面這些方法。不過這些判斷說不定以後會用到可以拿來用。

Jaccard index

雅卡爾指數（英語：Jaccard index），又稱為交並比（Intersection over Union）、雅卡爾相似係數（Jaccard similarity coefficient），是用於比較樣本集的相似性與多樣性的統計量。雅卡爾係數能夠量度有限樣本集合的相似度。
參考: 雅卡爾指數 - 維基百科，自由的百科全書

這邊為了方便說明，我一律說 Jaccard 相似度。

Jaccard 相似度是一種用於比較兩個集合的相似度的方法。它的計算公式為：兩個集合的交集大小除以兩個集合的聯集大小。在 C# 中，我們可以使用以下的程式碼來計算 Jaccard 相似度：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class ArrayComparer
{
    public double CalculateSimilarity(int[] array1, int[] array2)
    {
        var intersectionCount = array1.Intersect(array2).Count();
        var unionCount = array1.Union(array2).Count();

        return (double)intersectionCount / unionCount;
    }
}

Jaccard 相似度是一種用於比較兩個集合的相似度的方法。它的計算公式為：兩個集合的交集大小除以兩個集合的聯集大小。**Jaccard 相似度的值範圍在 0 到 1 之間，值越大表示相似度越高。**Jaccard 相似度適用於處理無序的集合數據，並且不考慮元素的頻率。

Cosine Similarity

Cosine 相似度是一種用於比較兩個向量方向的相似度的方法。它的計算公式為：兩個向量的點積除以兩個向量的模長的乘積。在 C# 中，我們可以使用以下的程式碼來計算 Cosine 相似度：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class ArrayComparer
{
    public double CalculateSimilarity(int[] array1, int[] array2)
    {
        var dotProduct = array1.Zip(array2, (a, b) => a * b).Sum();
        var magnitude1 = Math.Sqrt(array1.Sum(a => a * a));
        var magnitude2 = Math.Sqrt(array2.Sum(b => b * b));

        return dotProduct / (magnitude1 * magnitude2);
    }
}

Cosine 相似度是一種用於比較兩個向量方向的相似度的方法。它的計算公式為：兩個向量的點積除以兩個向量的模長的乘積。Cosine 相似度的值範圍在 -1 到 1 之間，值越大表示向量方向越相似。Cosine 相似度適用於處理有序的向量數據，並且考慮到元素的頻率和位置。

Jaccard VS Cosine

Jaccard 相似度和 Cosine 相似度都是用來衡量兩個集合或向量的相似度的方法，但它們的計算方式和適用場景有所不同。

總的來說，如果你的資料是無序的集合，並且不需要考慮元素的頻率，那麼 Jaccard 相似度可能是一個好選擇。如果你的數據是有序的向量，並且需要考慮元素的頻率和位置，那麼 Cosine 相似度可能更適合。

文字比較方法

在前面的部分，我們討論了如何使用 Jaccard 相似度和 Cosine 相似度來比較陣列。然而，在許多情況下，我們需要比較的是文字，而不是陣列。這時，Levenshtein distance 就派上用場了。

Levenshtein distance

Levenshtein distance 是一種衡量兩個字串差異的方法，它計算的是從一個字串變成另一個字串所需要的最少單字符編輯（插入、刪除或替換）的次數。在接下來的部分。

以下是如何在 C# 中使用 Levenshtein distance 來比較兩個字串的相似度的範例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

StringComparer.CalculateLevenshteinDistance("123","555").Dump();

public class StringComparer
{
	public static int CalculateLevenshteinDistance(string str1, string str2)
	{
		var matrix = new int[str1.Length + 1, str2.Length + 1];

		for (int i = 0; i <= str1.Length; i++)
			matrix[i, 0] = i;
		for (int j = 0; j <= str2.Length; j++)
			matrix[0, j] = j;

		for (int i = 1; i <= str1.Length; i++)
		{
			for (int j = 1; j <= str2.Length; j++)
			{
				int cost = (str1[i - 1] == str2[j - 1]) ? 0 : 1;

				matrix[i, j] = Math.Min(
					Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
					matrix[i - 1, j - 1] + cost);
			}
		}

		return matrix[str1.Length, str2.Length];
	}
}

範例

這個方法首先創建一個二維矩陣，然後使用動態規劃的方法來計算 Levenshtein 距離。最後，返回的數值越小，表示兩個字串的相似度越高。

請注意，這種方法的時間複雜度和空間複雜度都是 O (nm)，其中 n 和 m 分別是兩個字串的長度。在處理長字串時，可能需要考慮使用更高效的算法。

參考

Updated on 2024-04-28
 Array, String, Similarity, Comparison, Jaccard, Cosine, Levenshtein Distance
Back | Home