Jaccardの類似係数

瞎扯一通#

最近、データ構造の課題設計をしています。私たちのグループのテーマはキャンパスガイドシステムです。私たちはあまりにも下手で良いアイデアが思いつかないので😭、情報を調べている（~~他の人のアイデアを盗む~~）際に、いくつかの推薦アルゴリズムの紹介を見つけましたので、それを私たちの設計に追加しました。

Jaccard 相関係数#

定義#

$Jaccard(A, B) = \frac{ | A \cap B | }{ | A \cup B | } = \frac{ | A \cap B | }{ | A | + | B | - | A \cap B | }$ , もし $A = \varnothing$ かつ $B = \varnothing$ ならば、 $Jaccard(A, B) = 1$

注: $Jaccard(A, B) \in [0, 1]$

Jaccard 距離#

2 つの集合の非類似度を表すために使用されます。

$Dist_{Jaccard} = 1 - Jaccard(A, B) = \frac{ A \Delta B }{ | A \cup B | }$

簡単な推薦アルゴリズムの実装#

変更前の建物 / 観光地ノードの定義:#

struct Location {
    double longitude;
    double latitude;

    [[nodiscard]] std::string toString() const {
        return std::to_string(longitude) + "," + std::to_string(latitude);
    }
};

template<typename IdType>
struct Spot {
    IdType id;
    std::string title;
    std::string description;
    Location location{};
};

実装のアイデア#

現在の建物に基づいて他の類似の建物を推薦するため、私はSpot構造体にtagsフィールド（セット）を設定することを考えました。各建物には、使用目的に基づいていくつかのタグを設定します。例えば: "教室"、"実験室"、"共通科目"、"専門科目"、"理論科目"、"実験科目" などです。これらのタグを使用してJaccard 相関係数を類似度として使用します。

各建物に対して、類似度が similarityThreshold(類似度の下限) を超える建物を推薦し、距離がより近い建物を優先的に推薦します。similarityThresholdの値は、グローバルなタグの数を総合的に考慮して決定する必要があります。

変更後の定義:#

struct Location {
    double longitude;
    double latitude;

    [[nodiscard]] std::string toString() const {
        return std::to_string(longitude) + "," + std::to_string(latitude);
    }
};

template<typename IdType>
struct Spot {
    IdType id;
    std::string title;
    std::unordered_set<std::string> tags;
    std::string description;
    Location location{};
};

コードの実装:#

template<typename IdType>
class Recommend {
private:
    // Jaccard相関係数を計算する
    static double jaccardSimilarity(
            const std::unordered_set<std::string>& set1,
            const std::unordered_set<std::string>& set2
    ) {
        std::unordered_set<std::string> intersection;
        std::unordered_set<std::string> union_set;

        std::copy_if(set1.begin(), set1.end(),
                     std::inserter(union_set, union_set.end()),
                     [&](const std::string& s) {
                         return set2.find(s) != set2.end();
                     }
        );

        std::set_intersection(set1.begin(), set1.end(),
                              set2.begin(), set2.end(),
                              std::inserter(
                                      intersection,
                                      intersection.end()
                              )
        );

        std::set_union(set1.begin(), set1.end(),
                       set2.begin(), set2.end(),
                       std::inserter(
                               union_set,
                               union_set.end()
                       )
        );

        return static_cast<double>(intersection.size()) /
               static_cast<double>(union_set.size());
    }

public:
    static std::vector<std::pair<IdType, double>> recommendSimilarSpots(
            Graph<IdType> graph,
            const Spot<IdType>& referenceSpot,
            double similarityThreshold = 0.3
    ) {
        std::vector<std::pair<IdType, double>> similarityScores;

        for (const auto& spotPair : graph.getSpots()) {
            const auto& spot = spotPair.second;
            if (spot.id != referenceSpot.id) {
                double similarity = jaccardSimilarity(
                        referenceSpot.tags,
                        spot.tags
                );
                if (similarity >= similarityThreshold) {
                    similarityScores.push_back(
                            std::make_pair(spot.id, similarity)
                    );
                }
            }
        }

        Sort(similarityScores.begin(), similarityScores.end(),
             [&graph, &referenceSpot](
                     const std::pair<IdType, double>& a,
                     const std::pair<IdType, double>& b
             ) {
                 if (a.second == b.second) {
                     return distanceHaversine(referenceSpot.location, graph.getSpot(a.first).location) <
                            distanceHaversine(referenceSpot.location, graph.getSpot(b.first).location);
                 }
                 return a.second > b.second;
             }
        );

        return similarityScores;
    }
};