👠

SwiftでのMinHash法の類似度計算方法

2024/10/30に公開

 MinHashによる効率的な類似度計算
 概要MinHashは、大規模なテキストデータセット間の類似度を効率的に計算するためのアルゴリズムです。
従来の類似度計算手法と比べて、MinHashは計算効率が大幅に向上し、メモリ使用量も削減できます。

 基本概念：Jaccard類似度MinHashを理解する前に、その基礎となるJaccard類似度について説明します。

 Jaccard類似度とは2つの集合 A と B のJaccard類似度は、以下の式で定義されます：

J(A, B) = \frac{|A \cap B|}{|A \cup B|}
ここで：

|A \cap B| は、集合 A と B の共通要素の数

|A \cup B| は、集合 A と B の和集合の要素数
結果は0から1の値を取り、1に近いほど類似度が高いことを示します

 具体例例えば、以下の2つの文章があるとします：
文章1: "私は今日公園に行きました"
文章2: "私は昨日公園へ行きました"
これらの文章を単語の集合として表すと：
A = \{\text{私}, \text{は}, \text{今日}, \text{公園}, \text{に}, \text{行きました}\}
B = \{\text{私}, \text{は}, \text{昨日}, \text{公園}, \text{へ}, \text{行きました}\}
共通要素は4つ（私, は, 公園, 行きました）、和集合の要素数は8つなので：

\text{Jaccard類似度} = \frac{4}{8} = 0.5

 MinHashの仕組みMinHashは、Jaccard類似度を効率的に近似計算する手法です。以下の手順で処理を行います。

 1. ハッシュ関数群の準備複数のハッシュ関数 h_1, h_2, \dots, h_k を用意します：
各ハッシュ関数は独立していることが望ましい
仮に k は100程度の値を使用します
ハッシュ関数は、異なるシード値を持つ同一アルゴリズムでも構いません

 2. 署名ベクトルの生成各集合 S に対して、以下の手順で署名ベクトルを生成します：
集合の各要素に対して、各ハッシュ関数を適用します
各ハッシュ関数について、得られたハッシュ値の最小値を取得します
最小値を並べて署名ベクトルを作成します
数式で表すと：

\mathbf{M}(S) = \left( \min_{x \in S} h_1(x), \min_{x \in S} h_2(x), \dots, \min_{x \in S} h_k(x) \right)

 3. 類似度の近似計算2つの集合の署名ベクトル間で、対応する位置の値が一致する割合を計算します：

\text{近似Jaccard類似度} \approx \frac{\text{一致する要素の数}}{k}
この近似は、ハッシュ関数の数 k が大きいほど精度が高まります。

 効率的な実装：SwiftによるMinHash以下に、SwiftによるMinHashの効率的な実装例を示します。
class MinHash {
    private let numHashFunctions: Int
    private let hashFunctions: [(String) -> Int]
    
    init(numHashFunctions: Int = 100) {
        self.numHashFunctions = numHashFunctions
        
        // 効率的なハッシュ関数の生成
        self.hashFunctions = (0..<numHashFunctions).map { seed in
            { (input: String) -> Int in
                var hash = seed
                for char in input.unicodeScalars {
                    hash = (hash &* 31) &+ Int(char.value)
                }
                return hash
            }
        }
    }
    
    /// テキストの前処理を行い、単語の集合を生成
    private func preprocessText(_ text: String) -> Set<String> {
        let words = text.lowercased()
            .components(separatedBy: CharacterSet.punctuationCharacters.union(.whitespacesAndNewlines))
            .filter { !$0.isEmpty }
        return Set(words)
    }
    
    /// MinHash署名の計算
    func computeSignature(for text: String) -> [Int] {
        let words = preprocessText(text)
        return hashFunctions.map { hashFunc in
            words.map { hashFunc($0) }.min() ?? Int.max
        }
    }
    
    /// 類似度の計算
    func calculateSimilarity(between text1: String, and text2: String) -> Double {
        let sig1 = computeSignature(for: text1)
        let sig2 = computeSignature(for: text2)
        
        let matchCount = zip(sig1, sig2).filter { $0 == $1 }.count
        return Double(matchCount) / Double(numHashFunctions)
    }
}

 使用例let minHash = MinHash(numHashFunctions: 100)

let text1 = """
    SwiftのMinHash実装は、効率的な類似度計算を可能にします。
    この実装では、複数のハッシュ関数を使用して署名を生成します。
    """

let text2 = """
    SwiftでMinHashを実装すると、高速な類似度計算が可能です。
    署名の生成には、複数のハッシュ関数を利用します。
    """

let similarity = minHash.calculateSimilarity(between: text1, and: text2)
print(String(format: "類似度: %.2f", similarity))

 パフォーマンス最適化のポイント効率的なハッシュ関数の設計
計算速度を重視し、シンプルな演算で構成します（乗算、加算、ビット操作など）
ハッシュ関数の独立性を保つため、異なるシード値や係数を使用します
メモリ効率の向上
署名ベクトルのサイズ（ハッシュ関数の数）を適切に設定します
不要なメモリの割り当てを避け、インプレース処理を心がけます
前処理の最適化
テキストの正規化やトークン化を効率的に行います
不要な文字の除去や分割を一度の走査で完了させます

 まとめMinHashは、大規模なデータセット間の類似度計算を効率的に行うための強力なツールです。

高速性：近似計算でありながら、大規模データでも高速に処理可能

メモリ効率：署名ベクトルによる表現で、メモリ使用量を削減

精度：適切なハッシュ関数の数を選ぶことで、精度と計算コストのバランスを調整可能

汎用性：テキスト以外にも、集合データを扱う様々な分野で応用可能
実装時には、ハッシュ関数の選択や数、前処理方法など、目的に応じた最適化が重要です。

 参考文献Jure Leskovec, Anand Rajaraman, Jeff Ullman, "Mining of Massive Datasets", オンライン版
Preferred Networks, "MinHashを用いた高速な類似文書検索", 技術ブログ

MinHashによる効率的な類似度計算

概要

基本概念：Jaccard類似度

Jaccard類似度とは

具体例

MinHashの仕組み

1. ハッシュ関数群の準備

2. 署名ベクトルの生成

3. 類似度の近似計算

効率的な実装：SwiftによるMinHash

使用例

パフォーマンス最適化のポイント

まとめ

参考文献

Discussion