Jaccard係数とは

Jaccard係数は次の式で表せます。

J(A, B) = |A ∩ B| / |A ∪ B|

A ∩ B: 共通している要素数
A ∪ B: どちらかに含まれる要素数

たとえば、

A = {kotlin, backend, api}
B = {kotlin, android, api}

の場合、

|A ∩ B| = 2（kotlin, api）
|A ∪ B| = 4（kotlin, backend, android, api）

なので、J(A, B) = 2 / 4 = 0.5 になります。

値の範囲は 0.0 から 1.0 です。

完全一致: 1.0
共通要素なし: 0.0

Kotlinで最小実装

object Jaccard {
    fun similarity(a: Set<String>, b: Set<String>): Double {
        if (a.isEmpty() && b.isEmpty()) return 1.0

        val intersectionSize = a.intersect(b).size
        val unionSize = a.union(b).size

        return if (unionSize == 0) 0.0 else intersectionSize.toDouble() / unionSize.toDouble()
    }
}

集合演算（intersect, union）だけで書けるので、ロジックはかなりシンプルです。

動作確認

fun main() {
    val tagsA = setOf("kotlin", "backend", "api")
    val tagsB = setOf("kotlin", "android", "api")
    val tagsC = setOf("design", "management")

    println("A vs B = %.3f".format(Jaccard.similarity(tagsA, tagsB))) // 0.500
    println("A vs C = %.3f".format(Jaccard.similarity(tagsA, tagsC))) // 0.000
    println("A vs A = %.3f".format(Jaccard.similarity(tagsA, tagsA))) // 1.000
}

おすすめ記事を出す例

前提: 取得できるデータ形式

@JvmInline
value class UserId(
    val value: String
)

@JvmInline
value class ArticleId(
    val value: String
)

data class ViewedArticle(
    val articleId: ArticleId,
    val tags: Set<String>,
    val viewedAt: Instant
)

data class ArticleCandidate(
    val id: ArticleId,
    val title: String,
    val tags: Set<String>
)

ViewedArticle（閲覧ログ）と ArticleCandidate（おすすめ候補）を取得できる想定です。

1. アクセス時に閲覧ログを保存する

記事詳細を開いたタイミングで1件保存します。

fun onArticleOpened(userId: UserId, articleId: ArticleId) {
    userEventRepository.saveView(userId, articleId)
}

2. ログと候補を取得する

private const val RECENT_VIEW_LIMIT = 20
private const val CANDIDATE_LIMIT = 50
private const val RECOMMEND_LIMIT = 3

val userId = UserId(currentUserId)
val articleId = ArticleId(currentArticleId)

val recentViews: List<ViewedArticle> = recommendationRepository.fetchRecentViews(
    userId = userId,
    limit = RECENT_VIEW_LIMIT
)

val candidates: List<ArticleCandidate> = recommendationRepository.fetchCandidates(
    excludeArticleId = articleId,
    limit = CANDIDATE_LIMIT
)

3. Jaccard係数で候補を並べる

data class RecommendedArticle(
    val article: ArticleCandidate,
    val score: Double
)

private const val FALLBACK_SCORE = 0.0

fun recommendArticles(
    recentViews: List<ViewedArticle>,
    candidates: List<ArticleCandidate>,
    limit: Int = RECOMMEND_LIMIT
): List<RecommendedArticle> {
    val recentTags = recentViews.flatMap { it.tags }.toSet()

    if (recentTags.isEmpty()) {
        return candidates.take(limit).map { RecommendedArticle(it, FALLBACK_SCORE) } // fallback
    }

    return candidates
        .asSequence()
        .map { candidate ->
            RecommendedArticle(
                article = candidate,
                score = Jaccard.similarity(recentTags, candidate.tags)
            )
        }
        .sortedByDescending { it.score }
        .take(limit)
        .toList()
}

使う側のイメージはこうです。

val recommended = recommendArticles(
    recentViews = recentViews,
    candidates = candidates,
    limit = RECOMMEND_LIMIT
)

使いやすい場面

タグベースで関連記事の候補を出す
重複気味のデータをざっくり検知する
本格的な推薦導入前の一次候補絞り込み

まとめ

Jaccard係数は実装が短く挙動も説明しやすいので、軽い類似度判定にはちょうど良いです。

まずはこの形で動かして、必要になったら重み付けや別アルゴリズムに広げるのが進めやすいと感じました。