ナード戦隊データマン

データサイエンスを用いて悪と戦うぞ

タグレコメンデーション: グラフを使って次のタグを予測

StackLite 1 とは、stackoverflowの質問につけられたタグの一覧のデータセットです。このデータセットを使って、エレガントな方法でタグ候補を予測します。

仮定

  1. 使えるデータは、質問IDとそのIDに対応したタグのみ。
  2. 入力済みのタグから次のタグを予測するのが目的。

データ整形

import pandas as pd
from collections import defaultdict
import itertools as it
import pickle

if __name__ == "__main__":
    tags = defaultdict(list)
    df = pd.read_csv("./Tags.csv")
    for idx,tag in zip(df.Id,df.Tag):
        tags[idx].append(str(tag))

    with open("tags_fix.pkl","wb") as f:
        pickle.dump(tags, f)

グラフへぶち込む

import networkx as nx
import pickle
import tqdm
from collections import defaultdict

if __name__ == "__main__":
    with open("./tags_fix.pkl", "rb") as f:
        data = pickle.load(f)

    G = nx.DiGraph()
    edges = []
    weight = defaultdict(int)
    for k,tags in tqdm.tqdm(data.items()):
        for t1,t2 in zip(tags[0:-1],tags[1:]):
            weight[(t1,t2)] += 1
            edges.append((t1,t2))
    wedges = [(e[0],e[1],1.0/weight[e]) for e in tqdm.tqdm(edges)]
        
        
    G.add_weighted_edges_from(wedges)

    with open("graph.pkl", "wb") as f:
        pickle.dump(G, f)

予測スクリプトの作成 (sample.py)

import pickle
import networkx as nx
import itertools as it
import sys

if __name__ == "__main__":
    with open("./graph.pkl", "rb") as f:
        G = pickle.load(f)
    
    tags = sys.argv[1].split(",")

    cands = []
    for x in it.combinations(tags, 2):
        cands += nx.dijkstra_path(G,x[0],x[1])
        cands += nx.dijkstra_path(G,x[1],x[0])

    cands = list(set(cands))
    for t in tags:
        cands.remove(t)

    print(cands)

予測の実行

python sample.py tensorflow,machine-learning,deep-learning

出力

['classification', 'neural-network', 'artificial-intelligence', 'scikit-learn', 'backpropagation']

説明

データから有向グラフを作成していますが、頻度が高いエッジほど重みは低くなります。入力タグリストから重みが最小になるパスを見つけ、そのパスの中に含まれるタグを候補にします。

なにがエレガントか

機械学習を使っていないこと。この問題に機械学習を使う場合、Tag.csvだけ使うことを仮定すると特徴量が少なすぎます。しかし、このようなグラフ操作の問題にすれば、特徴量は共起頻度の逆数だけでいいわけです。