ナード戦隊データマン

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

MCLによるクラスタに後から割り当てる

前回の記事では、マルコフクラスタリングによってニュースイベントを分類しました。今回は、こちらの論文 (Unsupervised Event Clustering and Aggregation from Newswire and Web Articles) を日本語で実行します。

パイプライン

[クラスタリングフェーズ] 1. 記事をスクレイピングしておく。 2. 記事をBoWでベクトル化。 3. ベクトル化した記事をAPSSで行列化。 4. 類似度行列をMCLに渡す。

[割り当てフェーズ] 1. 割り当てたい記事をmonolingual word alignment systemでスコアリング。 2. 各クラスタに対し、スコアの最も高い記事を、クラスタリングフェーズで求めたクラスタに割り当てる。

monolingual word alignment system (MWAS)

まず、このMWALをイチから実装する必要があります。実装のために、TDDを使いました。テストケースから先に書いて、小さなステップを繰り返す方法です。

MWASは、論文内の以下の図と論文の説明を見て、おおよそ推測しました:

Screenshot_2018-07-13_19-36-52.png

まあ、テストケースを見てもらえばわかると思います。

テストケースは何度か修正しましたが、リファクタリングを繰り返した結果として以下のようなモジュールが完成しました。

import tensorflow as tf
import tensorflow_hub as hub
import numpy as np
from functools import partial
from sklearn.metrics.pairwise import cosine_similarity


def texts_encoder(texts):
    with tf.Graph().as_default():
        embed = hub.Module("https://tfhub.dev/google/nnlm-ja-dim128/1")
        embeddings = embed(texts)
        with tf.Session() as sess:
            sess.run(tf.global_variables_initializer())
            sess.run(tf.tables_initializer())
            result = sess.run(embeddings)
    return result


def align(base, target, threshold=0.50):
    word_vectors = texts_encoder(base+target)
    base_vectors = word_vectors[:len(base)]
    target_vectors = word_vectors[len(base):]
    return solve(target, base_vectors, target_vectors, threshold)


def solve(target, base_vectors, target_vectors, threshold=0.50):
    similarities = cosine_similarity(base_vectors, target_vectors)
    results = []
    for similarity in similarities:
        if max(similarity) > threshold:
            results.append(target[np.argmax(similarity)])
        else:
            results.append(None)
    return results


def aligns(base, targets, threshold=0.50):
    ls = [len(base)] + [len(target) for target in targets]
    pt = 0

    data = base
    for target in targets:
        data += target
    
    word_vectors = texts_encoder(data)
    target_vectors = []
    for i, l in enumerate(ls):
        if i == 0:
            base_vector = word_vectors[:l]
        else:
            target_vectors.append(word_vectors[pt:pt+l])
        pt += l

    return [solve(target, base_vector, target_vector, threshold)
                 for target, target_vector in zip(targets, target_vectors)]


def sum_aligns(Bs):
    return np.sum(Bs, axis=0)


def W(A, Bs):
    A = np.array(A)
    tmp_W = []
    for B in Bs:
        tmp_W.append(A * B)
    return np.array(tmp_W)
    

def aligns2Bs(aligns):
    return [list(map(lambda x: x is not None, align)) for align in aligns]


def score(Ws):
    return np.sum(Ws, axis=1)


def execute(base_sentence, target_sentences, tokenize, stps, threshold=0.5):
    func = partial(fmt_sentence, tokenize=tokenize, stps=stps)
    base = func(base_sentence)
    targets = list(map(func, target_sentences))
    als = aligns(base, targets, threshold=threshold)
    Bs = aligns2Bs(als)
    A = sum_aligns(Bs)
    Ws = W(A, Bs).tolist()
    return score(Ws)


def fmt_sentence(sentence, tokenize, stps):
    return [term for term in tokenize(sentence).split() if term not in stps]

最終的に、テストケースが以下のようになりました:

import unittest
import numpy as np
import sys
sys.path.append("..")
import align
from nltk.corpus import stopwords
import MeCab


class TestAlign(unittest.TestCase):
    def test_align_1(self):
        base_sentence = "京都市 洪水 被害".split(" ")
        target_sentence = "洪水 3人 死亡 京都市".split(" ")
        aligned = align.align(base_sentence, target_sentence)
        true_align = ["京都市", "洪水", None]
        self.assertEqual(aligned, true_align)

    def test_align_2(self):
        base_sentence = "アメリカ 保護貿易 蔓延 関税 引き上げ".split(" ")
        target_sentence = "関税 問題 米国 保護貿易 推進".split(" ")
        aligned = align.align(base_sentence, target_sentence)
        true_align = ["米国", "保護貿易", None, "関税", None]
        self.assertEqual(aligned, true_align)

    def test_aligns(self):
        base_sentence = "アメリカ 保護貿易 蔓延 関税 引き上げ".split(" ")
        targets =[
            "関税 問題 米国 保護貿易 推進".split(),
            "アメリカ 主導 世界 経済".split(),
            "保護貿易 自由貿易 比較".split()
        ]
        aligns = align.aligns(base_sentence, targets, threshold=0.50)
        true_aligns = [
            ["米国", "保護貿易", None, "関税", None],
            ["アメリカ", None, None, None, None],
            [None, "保護貿易", None, None, None]
        ]

        for aligned, true_aligns in zip(aligns, true_aligns):
            self.assertListEqual(aligned, true_aligns)
        
    def test_aligns2Bs(self):
        base_sentence = "アメリカ 保護貿易 蔓延 関税 引き上げ".split(" ")
        targets =[
            "関税 問題 米国 保護貿易 推進".split(),
            "アメリカ 主導 世界 経済".split(),
            "保護貿易 自由貿易 比較".split()
        ]
        aligns = align.aligns(base_sentence, targets, threshold=0.50)
        Bs = align.aligns2Bs(aligns)
        true_Bs = [
            [True, True, False, True, False],
            [True, False, False, False, False],
            [False, True, False, False, False]
        ]

        for B, true_B in zip(Bs, true_Bs):
            self.assertListEqual(B, true_B)

    def test_sum_aligns(self):
        base_sentence = "アメリカ 保護貿易 蔓延 関税 引き上げ".split(" ")
        targets =[
            "関税 問題 米国 保護貿易 推進".split(),
            "アメリカ 主導 世界 経済".split(),
            "保護貿易 自由貿易 比較".split()
        ]
        aligns = align.aligns(base_sentence, targets, threshold=0.50)
        Bs = align.aligns2Bs(aligns)
        A = align.sum_aligns(Bs).tolist()
        true_A = [2,2,0,1,0]

        self.assertListEqual(A, true_A)

    def test_W(self):
        base_sentence = "アメリカ 保護貿易 蔓延 関税 引き上げ".split(" ")
        targets =[
            "関税 問題 米国 保護貿易 推進".split(),
            "アメリカ 主導 世界 経済".split(),
            "保護貿易 自由貿易 比較".split()
        ]
        aligns = align.aligns(base_sentence, targets, threshold=0.50)
        Bs = align.aligns2Bs(aligns)
        A = align.sum_aligns(Bs)
        Ws = align.W(A, Bs).tolist()
        true_Ws = [
            [2,2,0,1,0],
            [2,0,0,0,0],
            [0,2,0,0,0]
        ]
        for W, true_W in zip(Ws, true_Ws):
            self.assertListEqual(W, true_W)

    def test_fmt_sentence(self):
        tagger = MeCab.Tagger("-Owakati")
        tokenize = tagger.parse
        stps = stopwords.words("japanese")        
        test_sentence = "アメリカが主導する世界の経済の行方は!?"
        sent_fmt = align.fmt_sentence(test_sentence, tokenize, stps)
        true_fmt = ["アメリカ", "主導", "世界", "経済", "行方"]
        self.assertListEqual(sent_fmt, true_fmt)

    def test_score(self):
        Ws = [
            [2,2,0,1,0],
            [2,0,0,0,0],
            [0,2,0,0,0]
        ]
        score = align.score(Ws).tolist()
        true_score = [5, 2, 2]
        self.assertListEqual(score, true_score)

    def test_execute(self):
        tagger = MeCab.Tagger("-Owakati")
        tokenize = tagger.parse
        stps = stopwords.words("japanese")        
        base_sentence = "アメリカ、保護貿易蔓延、関税引き上げか"
        targets =[
            "関税問題で米国、保護貿易を推進",
            "アメリカ主導の世界経済",
            "保護貿易と自由貿易を比較"
        ]
        ss = align.execute(base_sentence, targets, tokenize, stps, threshold=0.5).tolist()
        self.assertListEqual([9, 5, 7], ss)


if __name__ == "__main__":
    unittest.main()

jupyter notebook

クラスタリングフェーズでは、前回の記事とほぼ同じことを実行しますが、時間減衰関数をかけ合わせます。記事数が多い場合にも対応できるよう、スパース化します。

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.metrics.pairwise import cosine_similarity
from nltk.corpus import stopwords
import itertools
import markov_clustering as mc
import pandas as pd
import numpy as np

target_afp = pd.read_csv("target_afp.csv")

def mul_sim(similarities, days):
    for i, d1 in enumerate(tqdm_notebook(days)):
        d = np.array([1/np.exp(diff_date(d1, d2)/24.0) for d2 in days])
        similarities[i, :] = similarities[i, :].multiply(d)
    return similarities

days =targets_afp['day_fixed'].tolist()
stps = stopwords.words("japanese")
stps = stps + [''.join(list(stp)) for stp in list(itertools.product(stps, stps))]
count_vectors = CountVectorizer(stop_words=stps).fit_transform(targets_afp['data'])
similarities = cosine_similarity(count_vectors, dense_output=False)
similarities = mul_sim(similarities, days)
result = mc.run_mcl(similarities)
clusters = mc.get_clusters(result)

クラスタ番号10は以下のようになりました:

[[cluster 10]]]
0) :金 正男 氏 殺害 で 女 1 人 を 逮捕 遺体 安置 の 病院 に は 北朝鮮 大使館 員 の 姿 も 北朝鮮 の 金 正 恩 ( キム ・ ジョン ウン 、 Kim Jong - Un ) 朝鮮 労働党 委員 長 の 異母 兄 、 金 正男 ( キム ・ ジョンナム 、 Kim Jong - Nam ) 氏 が マレーシア ・ クアラルンプール ( Kuala Lumpur ) の 空港 で 殺害 さ れ た 事件 で 、 マレーシア の 警察 当局 は 15 日 、 容疑 者 の 女 1 人 を 逮捕 し た 

1) :韓国 政府 、 金 正男 氏 の 暗殺 を 確認 大統領 代行 「 北 の 残忍 性 示す 」 ( 更新 ・ 写真 追加 ) 韓国 政府 は 15 日 、 北朝鮮 の 金 正 恩 ( キム ・ ジョン ウン 、 Kim Jong - Un ) 朝鮮 労働党 委員 長 の 異母 兄 、 金 正男 ( キム ・ ジョンナム 、 Kim Jong - Nam ) 氏 が マレーシア ・ クアラルンプール ( Kuala Lumpur ) の 空港 で 暗殺 さ れ た と の 報道 は 事実 だ と 確認 し た 

2) :北朝鮮 の 金 正男 氏 、 マレーシア で 暗殺 か 韓国 メディア 報道 ( 更新 、 写真 追加 ) 北朝鮮 の 金 正 恩 ( キム ・ ジョン ウン 、 Kim Jong - Un ) 朝鮮 労働党 委員 長 の 異母 兄 、 金 正男 ( キム ・ ジョンナム 、 Kim Jong - Nam ) 氏 が 、 マレーシア で 北朝鮮 の 工作 員 の 女 により 毒 針 を 使っ て 暗殺 さ れ た と 、 韓国 メディア が 14 日 、 報じ た 

このクラスタ10に、新たな記事を割り当てます。MWASを使います。

import sys
sys.path.append("../module/")
import align

targets = pd.read_csv("targets.csv")

scores = align.execute(base_sentence=targets_afp['title'].iloc[clusters[10][0]], target_sentences=targets['title'].tolist(), tokenize=tagger.parse, stps=stps, threshold=0.5).tolist()
scores = np.array(scores)

threshold = 1500

targets['title'][scores > threshold]

クラスタ10に新しく割り当てた記事↓

10989    金正男氏殺害で女1人を逮捕 遺体安置の病院には北朝鮮大使館員の姿も
36523           金正男氏は北朝鮮の女性工作員2人が殺害=韓国情報当局
36545            金正男氏の死亡、米は北朝鮮が殺害との見方=米政府筋

どうやら、イベントは概ね正しく分類できたようです。

おわりに

実は、スクレイピングしたデータのサイズが大きすぎてgithubにアップロードできなかったので、再現してもらうには自前でスクレイピングしてもらう必要があります。ここでは、マルコフクラスタリングによるクラスタリング結果に対し、新たなデータを割り当てる方法を試していき、それなりの結果を出すことがわかりました。

参考

[0] http://www.aclweb.org/anthology/W17-4211

追記

2018/07/13 20:03

何気に、nltkのストップワードでjapaneseを指定していますが、これはnltk_dataに以下を入れて実行しています。 https://github.com/sugiyamath/credibility_analysis/blob/master/japanese