ナード戦隊データマン

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

機械学習を使わずにニュースイベントを分類する

前回前々回、マルコフクラスタリングによってニュースイベントを分類しました。今回は、機械学習を使わず、nnlm-ja-dim128による分散表現と類似度に対するスレッショルドだけを用いてどの程度分類できるのか試します。

ニュースイベントの分類についての概要

ニュースの分類では、分類の抽象度を決める必要があります。

最も具体的なレベルの分類は「同一イベント」による分類です。例えば、「18日, 九州で地震」と「18日, 熊本で地震」はおそらく同一イベントとして考えることができますが、「22日, 関東で地震」は別のイベントです。

しかし、抽象度を上げて「日本の地震」という分類で考えると、前述の3つは同じ「タイプ」として分類されることになります。さらに「地震」という分類ならより抽象的になり、世界中の地震情報が同じタイプとして分類されます。さらに抽象度を上げれば「自然災害」ということになるでしょう。

一般的には、トピックモデリングやkmeansのような手法を用いる場合、トピック数やkの数が少ないほど抽象度が上がります。しかし、これらの手法で「同一イベント」という具体的なイベントを分類しようとすると、事前に「イベント数」をわかっている必要があるため、非現実的です。

そこで類似度の行列(を時間減衰関数と演算したもの)に対してマルコフクラスタリングを行うような手法を使えば同一イベントで分類できます。ただ、類似度の行列は記事数×記事数なので、計算量はO(n2)となり、さらに必要なメモリ領域もαn2だけ必要になります。

今回書く手法も、O(n2)の手法ですが、「機械学習を使わずに」どの程度分類できるかを試します。

パイプライン

  1. イベントチェーンを生成する。
  2. 各チェーンの中で同一のイベントがあればマージする。
  3. マージされなかった同一イベントを再グルーピングする。

モジュール

import tensorflow as tf
import tensorflow_hub as hub
import numpy as np
import pandas as pd


def cossim(v1, v2):
    return np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))


def texts_encoder(texts):
    with tf.Graph().as_default():
        embed = hub.Module("https://tfhub.dev/google/nnlm-ja-dim128-with-normalization/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 similar_event(word_vectors, source_idx, range_idx, threshold=0.85):
    similar_events = []
    source_vector = word_vectors[source_idx]
    for i in range(range_idx[0], range_idx[0]+range_idx[1]):
        if cossim(source_vector, word_vectors[i]) > threshold:
            similar_events.append(i)
    return similar_events


def grouping_events(events, word_vectors, threshold=0.8):
    results = []
    current_group = []
    
    for i, e in enumerate(events):
        current_group.append(events[i])
        if i == len(events)-1:
            results.append(current_group)
            current_group = []
        else:        
            if cossim(word_vectors[events[i]], word_vectors[events[i+1]]) > threshold:
                current_group.append(events[i+1])
            else:
                results.append(current_group)
                current_group = []

    if current_group:
        results.append(current_group)
        
    return results


def compute_instances_and_chains(df, word_vectors, size=None, day_column="day_fixed", time_decay=30, 
                                 chain_threshold=0.8, grouping_threshold=0.87):
    all_events = []
    event_instances = []
    event_chains = []
    
    if size is None:
        size = df.shape[0]
    
    for i in range(size):
        if i%1000 == 0:
            print("{}".format(i*100/df.shape[0]))
        if i in all_events:
            continue
        after_week = df.iloc[i][day_column] + pd.DateOffset(time_decay)
        today = df.iloc[i][day_column]
        len_data = df[today <= df[day_column]][df[day_column] <= after_week].shape[0]
        events = similar_event(word_vectors, i, (i, len_data), threshold=chain_threshold)
        if events == []:
            continue
        grouped_events = grouping_events(events, word_vectors, threshold=grouping_threshold)
        event_instances += grouped_events
        event_chains.append(events)
        all_events += events
        all_events = list(set(all_events))
    return event_chains, event_instances


def regrouping(grouped_events, word_vectors, threshold=0.87):
    results = []
    all_events = []
    current_group = []
    for i, ge1 in enumerate(grouped_events):
        if i in all_events:
            continue
        current_group = []
        current_group += ge1
        for j, ge2 in enumerate(grouped_events[i+1:]):
            if i+j+1 in all_events:
                continue
            if cossim(word_vectors[ge1[0]], word_vectors[ge2[0]]) > threshold:
                current_group += ge2
                all_events += [i, i+j+1]
        results.append(list(set(current_group)))
    return results


def execute(df, word_vectors, size=None, day_column="day_fixed", time_decay=14, 
            chain_threshold=0.8, grouping_threshold=0.87, 
            regrouping_threshold=0.87, regrouping_level=1):

    event_chains, grouped_events = compute_instances_and_chains(
        df, word_vectors, size, day_column, time_decay, chain_threshold, grouping_threshold)

    regrouped_events = grouped_events
    for i in range(regrouping_level):
        regrouped_events = regrouping(regrouped_events, word_vectors, regrouping_threshold)
    
    return event_chains, regrouped_events

jupyterで実行

データは以下をダウンロードして展開してから使います。 https://github.com/sugiyamath/credibility_analysis/blob/master/notebook/data2.7z

In[1]:

import evolution
import pandas as pd
import MeCab
import numpy as np

df = pd.read_csv("../data/fixed_data.csv")
df['day_fixed'] = pd.to_datetime(df['day_fixed'])

tagger = MeCab.Tagger("-Owakati")

def data_define(d, tokenize=tagger.parse, c1="title", c2="body", sep="。", size=1):
    return tokenize('。'.join([d[1][c1]] + d[1][c2].split(sep)[:size]))

df['data'] = list(map(data_define, df.iterrows()))
df = df[['title', 'data', 'day_fixed']].sort_values(by="day_fixed")
word_vectors = evolution.texts_encoder(df['data'].tolist())
chains, instances = evolution.execute(df, word_vectors, size=5000, chain_threshold=0.85, regrouping_level=1)

In[2]:

for i, e in enumerate(regrouped_instances):
    if df.iloc[e].shape[0] > 1:
        print("[event {}]".format(i))
        print(df.iloc[e].sort_values(by="day_fixed").drop_duplicates()['title'])
        print()

Out[2]:

...[略]...

[event 1553]
38502       日本経済にグローバルな追い風、YCCが効果を増幅=日銀総裁
37729      日銀総裁、トランプ政策で世界経済加速 物価目標に追い風=報道
37727      米製造業改善で雇用引き締まり、経済の健全さ示唆=地区連銀報告
37552    判断維持「一部に改善遅れも、緩やかな回復基調」=1月月例経済報告
Name: title, dtype: object

[event 1560]
38577      米政権移行で米中関係は新たな不確実性に直面へ=中国外相
37458    米新政権と対話の用意、「一つの中国」尊重など前提=王毅外相
15440      米大統領報道官、中国への対抗措置を示唆 南シナ海問題で
36698      公平な対中貿易競争環境、トランプ氏「かなり早く実現へ」
Name: title, dtype: object

[event 1562]
12111    沖縄でオスプレイ「事故」 米海兵隊5人負傷
12089      オスプレイ、「事故」受け飛行を一時停止
Name: title, dtype: object

[event 1569]
12109        訪日前のプーチン氏、秋田犬「ゆめ」をお披露目
15676    プーチン大統領、日本から贈られた秋田犬を連れて会見に
Name: title, dtype: object

[event 1575]
38654    ベルリンのトラック突入、イスラム国が犯行声明=AMAQ通信
11982          IS、独トラック突入で犯行声明 「兵士が実行」
15639      独トラック突入、実行犯は依然逃走か ISISが犯行声明
15559        トルコ銃乱射、ISISが犯行声明 容疑者の捜索続く
Name: title, dtype: object

[event 1585]
12100    IS、シリア・パルミラで政府軍が放棄した戦闘装備を入手 米国防総省
12093              IS、パルミラで防空兵器入手か 米軍幹部が指摘
Name: title, dtype: object

[event 1591]
38888    米鉱工業生産予想以上の落ち込み、公益・製造業重しに
38563         米個人消費支出伸び鈍化、景気減速の可能性
Name: title, dtype: object

[event 1592]
38887             11月米小売売上高は微増、消費依然底堅く
38563             米個人消費支出伸び鈍化、景気減速の可能性
38091       米11月の卸売在庫は前月比1%増、2年ぶりの高い伸び
37755    米12月CPIは前年比2.1%上昇 2年半ぶりの大きな伸び
Name: title, dtype: object

[event 1594]
38892    南シナ海の人工島すべてに防衛施設、中国設置か=米シンクタンク
15678             中国、南シナ海の人工島に兵器システムを配備
38765      アングル:南シナ海の防衛施設、中国は反撃準備する権利主張
Name: title, dtype: object

[event 1596]
12119    チュニジア裁判所、妊娠した13歳少女の結婚認める NGOは怒り
15670          妊娠の13歳少女の結婚承認、親類男性と チュニジア
Name: title, dtype: object

[event 1600]
38893    米FOMCが0.25%利上げ、来年は3回の利上げ予想
38863     米FOMC、1年ぶりの利上げを決定:識者はこうみる
38890               イエレン米FRB議長の会見要旨
37114       米FOMC、金利据え置き 景気判断は依然前向き
37112           FOMC、金利据え置き:識者はこうみる
Name: title, dtype: object

[event 1602]
38891            米国株式市場は反落、来年の利上げペース加速を懸念
38836            米国株式市場は反発、利上げ加速観測で金融株に買い
38709              米国株は反発、独のトラック突入受け上げ幅縮小
38394                  米国株式市場は反落、幅広い銘柄に売り
38375                  米国株式市場は小幅続落、金融株に売り
38348    米国株が続落、アップルなどハイテク株に売り 年間ではプラスで終了
38319              米国株式市場は反発、ハイテク株や通信株に買い
38277              米国株式市場は続伸、消費関連株主導で買われる
37945          米国株は反落、決算発表前の買い手控えや政策不透明感で
37803             米国株は下落、米大統領選後の勝ち組銘柄売られる
37485           米国株式市場は反発、S&Pとナスダックが最高値更新
Name: title, dtype: object

...[略]...

考察

コードが行っているのは

1)起点記事との類似度が一定を超える記事をチェーンに追加 2)チェーン内の隣接ノードの類似度が一定を超えれば同一イベントとしてマージ 3)その他にマージしたほうがよさそうなものを類似度で評価してregroupingする

という三段階をとっています。

つまり、2つの文のベクトル表現の類似度と、スレッショルドの値だけで分類してこれだけ分類できてしまうわけです。

スレッショルドの値を変えてみればわかりますが、precisionとrecallのトレードオフ問題が生じます。thresholdが低すぎると、分類の抽象性が上がり、同一イベントではないものも含まれてしまいます。しかしthresholdが高すぎると、同一イベントが検出されなくなってしまいます。

試してみた感覚では、チェーン生成の段階ではthresholdを少し低めに設定して、同一イベント検出の段階で高いthresholdを設定すると良い結果が出ます。

ただ、計算量がO(n2)なので、この点では改善が必要です。特にregroupingの処理で結構時間がかかってしまうみたいです。

ちなみに、コサイン類似度にscikit-learnのものを使ってみましたが、速度が遅かったので私の先輩が実装した高速版の関数に変更しました。

参考

[1] http://kbcom.org/papers/KBCOM_2018_paper_1.pdf