ナード戦隊データマン

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

Webスパムを判定するためのリンクベース手法

Webスパムを判断する方法として、1)リンクベース特徴量を用いる方法, 2)コンテンツベース特徴量を用いる方法, がありますが、そのうちリンクベース特徴量では、TrustRankやAnti-TrustRankなどが有名です。しかし、QoC, QoLというもっと精度が高いらしい方法があったのでアルゴリズムを書いておきます。 https://github.com/sugiyamath/link_based_anti_spamming

アルゴリズムの数式

Screenshot_2018-06-02_07-46-07.png

QoCとQoLは同時に更新されます。ELは初期値として設定する値ですが、以下の4種類の方法で初期化が可能です:

  1. すべて"1/ページ数"で初期化。(uniform)
  2. 良いページの値を1、そうでない値を0で初期化。
  3. 悪いページの値を-1、そうでない値を0で初期化。
  4. 2と3を組み合わせて初期化。

QoCとQoLPageRank、TrustRank、AntiTrustRankを組み合わせたような機能性を持っているようです。

アルゴリズムのコード

以下は、数式をコード化したものです。

import numpy as np

def init_edges(size):
    edges = {}
    for i in range(size):
        edges[i] = []
    return edges

def load_edges(edge_file):
    tmp = []
    with open(edge_file, 'r') as f:
        for line in f:
            target = line.strip().split()
            tmp += [int(target[0]), int(target[1])]
    max_value = max(tmp) + 1
    from2to = init_edges(max_value)
    to2from = init_edges(max_value)
    with open(edge_file, 'r') as f:
        for line in f:
            target = line.strip().split()
            from2to[int(target[0])].append(int(target[1]))
            to2from[int(target[1])].append(int(target[0]))    
    return from2to, to2from

def init_Q(size, sparse_seed=None):
    """
    initial values using four ways:
      1. uniform: [1.0/size for i in range(size)]
      2. good seed set: {1:1, 5:1, 6:1, ...}
      3. bad seed set: {2:-1, 3:-1, 8:-1, ...}
      4. mixture: {1:1, 2:-1, 3:-1, ...}
    """
    if sparse_seed is None:
        return np.array([1.0/size for i in range(size)])
    else:
        out = []
        for i in range(size):
            if i in sparse_seed:
                out.append(sparse_seed[i])
            else:
                out.append(0.0)
        return np.array(out)
    
def update_QoC(QoC, QoL, from2to, to2from, size, alpha=0.6):
    out_QoC = np.copy(QoC)
    for i in range(size):
        total = 0
        for q_i in to2from[i]:
            ON_q_i = len(from2to[q_i])
            if ON_q_i == 0:
                continue
            left = alpha * (QoC[q_i]/ON_q_i)
            right = (1.0-alpha) * (QoL[q_i]/ON_q_i)
            total += left + right
        out_QoC[i] = total
    return out_QoC

def update_QoL(QoL, QoC, from2to, to2from, size, alpha=0.6):
    out_QoL = np.copy(QoL)
    for i in range(size):
        total = 0
        for r_i in from2to[i]:
            IN_r_i = len(to2from[r_i])
            if IN_r_i == 0:
                continue
            left = alpha * (QoC[r_i]/IN_r_i)
            right = (1.0-alpha) * (QoL[r_i]/IN_r_i)
            total += left + right
        out_QoL[i] = total
    return out_QoL

def train(QoC, QoL, from2to, to2from, size, itersize=5, alpha=0.6, beta=0.6, gamma=0.6):
    """
    INPUT QoC, QoL: np.array
    """
    out_QoL = np.copy(QoL)
    out_QoC = np.copy(QoC)
    for i in range(itersize):
        print("Iter:",str(i))
        out_QoC = update_QoC(out_QoC, out_QoL, from2to, to2from, size, alpha=alpha)
        out_QoL = update_QoL(out_QoL, out_QoC, from2to, to2from, size, alpha=beta)
        out_QoC = gamma * out_QoC + (1.0-gamma) * QoC
        out_QoL = gamma * out_QoL + (1.0-gamma) * QoL
    return out_QoC, out_QoL


if __name__ == "__main__":
    from2to, to2from = load_edges("/home/shun/work/data/edges.csv")

    size = len(from2to.items())
    assert(size == len(to2from.items()))

    QoC = init_Q(size)
    QoL = np.copy(QoC)
    
    out_QoC, out_QoL = train(QoC, QoL, from2to, to2from, size, itersize=10)
    
    with open("/home/shun/work/data/nodes_and_QoC.csv", 'w') as f:
        for i in range(out_QoC.shape[0]):
            f.write("{},{}\n".format(i,out_QoC[i]))
            
    with open("/home/shun/work/data/nodes_and_QoL.csv", 'w') as f:
        for i in range(out_QoL.shape[0]):
            f.write("{},{}\n".format(i,out_QoL[i]))
    

edges.csvには、以下の形式で辺を定義します。

from_id[tab]to_id\n . . .

from_idとは、リンク元のページのIDで、to_idはリンク先のページIDです。言い換えると、クローリングしてURL、外部リンクURLsを取得し、グラフ構造をURLに対応したIDを用いて定義したものです。

精度

Screenshot_2018-06-02_07-56-10.png

Screenshot_2018-06-02_07-58-33.png

QoCとQoLは、どちらも「良いページ」や「悪いページ」を検出するのに高い精度を出していることがわかります。また、正当なページやフェイクページを分類する精度も高いようです。

考察

QoCやQoLを条件として利用し、検索システムの検索結果から悪いページを除外する使い方もありますが、LTR(ランキング学習)の特徴量の一つとして使うこともできます。

また、検索結果を改善するために、手作業のパラメータチューニングと機械学習を用いたLTRのチューニングの両方を考慮することもできます。LTRでは、通常の検索結果に対してリスコアする、という2段階の構成になりますが、通常の検索結果を改善するために手作業のチューニングを行い、リスコアの段階で機械学習を用います。

LTRの特徴量としてQoC,QoLを使う以外にも、通常の検索結果を取得する段階でPageRankの代わりにQoCやQoLを使っても良いと思います。

参考

[1] https://arxiv.org/abs/1309.7266