Jaccard相似系数

瞎扯一通#

最近在写数据结构的课程设计，我们组的题目是校园导游系统, 因为太菜了想不到好的 idea😭, 在查资料 (~~偷窥别人 idea~~) 的时候看到了一些推荐算法的介绍，遂加在了我们的课设里

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 距离#

用于描述两集合的不相似度

$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;
    }
};