大量の日本語文書から似ている文書を探してみる

<a href="http://www.adventar.org/calendars/1637">Valtech (バルテック) Advent Calendar 2016</a>
12月13日担当として今回は巷で話題の「機械学習」について実際に動かしながらどんな感じのことができるのか紹介できればなぁと思います。

#そもそも機械学習ってなんぞや
センサやデータベースなどから、ある程度の数のサンプルデータ集合を入力して解析を行い、そのデータから有用な規則、ルール、知識表現、判断基準などを抽出し、アルゴリズムを発展させる。なお、データ集合を解析するので、統計学との関連が深い。
・・・（中略）
機械学習は検索エンジン、医療診断、スパムメールの検出、金融市場の予測、DNA配列の分類、音声認識や文字認識などのパターン認識、ゲーム戦略、ロボット、など幅広い分野で用いられている。
<a href="https://ja.wikipedia.org/wiki/%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92">wikipedia引用</a>

# 要するに
過去のデータから傾向を分析して、未来予知ができるよ！
（そういえばPC系雑誌の<a href="https://www.amazon.co.jp/Interface-%E3%82%A4%E3%83%B3%E3%82%BF%E3%83%BC%E3%83%95%E3%82%A7%E3%83%BC%E3%82%B9-2017%E5%B9%B4-01-%E6%9C%88%E5%8F%B7/dp/B000JVT2ZE/ref=pd_sim_14_5?_encoding=UTF8&psc=1&refRID=HD194P3C7K6M1E7V88JM">Interface(インターフェース) 2017年 01 月号 </a>には過去のTwitterデータから株価予測的なことをやっていました）

# 今回実際にやってみること
大量の日本語で書かれた文書から似ている文書を探し出してみます。

# 材料の準備
まず大量の日本語で書かれた文書が必要です。
これにはクローラを使用してWebページを巡回してページ情報を回収しデータを集めます。
（Webページを巡回してページ情報を回収する際には著作権などの問題があると思われますが個人や家族間で使用する、情報解析用でしたら問題ないようです。<a href="http://qiita.com/nezuq/items/c5e827e1827e7cb29011">参考にしたページ</a>、確かにそもそもこれがNGだとGoogleなどもNGとなってしまいますね。）

```
crawler \
-u クロール対象のURL \
-s "どんなリンクを辿るか@リンクをたどった際に行う処理"  \
-i インターバル
```

こんな感じに書くと

```
crawler \
-u http://example.co.jp \
-s "decreg('.sample','.+.html')@file_save_full('/tmp','%protocol/%host/%path')"  \
-i 5
```

example.co.jpを訪れて、class=".sample"と定義されている要素配下要素から".html"が末尾に付与されているURLに移動し、そのページ情報を/tmp配下のプロトコル、ホスト名、パスのディレクトリに保存する。（ディレクトリは勝手に作成されます。）という感じで回収します。
サーバに負荷をかけないように5秒インターバルを与えてます。
これだと深さが１層しか巡回出来ませんが、アロー（->）でつなげると何層でも深く出来ます。

![Screenshot from 2016-12-11 04:43:26.png](https://qiita-image-store.s3.amazonaws.com/0/106422/ba335a1a-3a10-8e33-d802-d20c1389f4f3.png)

とりあえず、14000件ほどデータを集めました。

このデータからメイン部分の日本語が記述されている箇所を抜き出し、ファイルに保存します。
getcontent_htmldocは-fに指定されたHTMLファイルを読み込んで、そのなかからclass="title"の要素を取得、
その要素配下にある内容を標準出力に出力します。
以下の文はそれをリダイレクトでファイルに吐き出しています。

```
for i in `find ./ -name data`
do
getcontent_htmldoc -f $i -t ".title" > `dirname $i`/title
done
```

これで14000件の日本語データが準備できました。

# 分類器を準備する。
機械学習にもいろいろ種類がありますが、今回は単純明快且つ実装が簡単
（というかほかはまだ説明できるほどの域に達していないし・・・orz）
な「TF-IDF」と「k平均法」の組み合わせで行こうかと思います。

分類器のながれ
**１． 日本語を分かち書きにする。**
「私は東京に住んでいます。」
を
「私　は　東京　に　住んで　います　。」
みたいに形態素解析を行った上で単語をスペース区切りにします。

これにはMeCabを使用します。

```
import MeCab
def get_word(str, split_char):
    returnstr = ""
    mecab_result  = MeCab.Tagger('mecabrc').parse(str)
    splited_words = mecab_result.split('\n')
    for splited_word in splited_words:
        if splited_word == 'EOS' or splited_word == '':
            break
        splited_word_info = splited_word.split(',')
        word_and_tag = splited_word_info[0].split('\t')
        if len(word_and_tag) == 2:
            word = word_and_tag[0]
            returnstr += word + split_char
    return returnstr
```

**２． TF-IDFを使用して、日本語データをベクトル化します。**

tf-idfは、文書中の単語に関する重みの一種であり、主に情報検索や文章要約などの分野で利用される。
<a href="https://ja.wikipedia.org/wiki/Tf-idf">Wikipediaより</a>

・TF (Term Frequency)
ある文書 d の中に出現する索引語 t の頻度です。文書中にその単語が何回現れたかをあらわします。

・DF (Document Frequency)
文書全体でその単語が何回現れたかをあらわします。
IDFはDFの対数。

数式などは<a href="http://qiita.com/ynakayama/items/300460aa718363abc85c">このページ</a>がとてもわかりやすいです。

これを行うことで各文書の「特徴量」を算出することが出来ます。

これにはscikit-learnライブラリを使用します。

```
from sklearn.feature_extraction.text import TfidfVectorizer
vectorizer = TfidfVectorizer(use_idf=True, token_pattern=u'(?u)\\b\\w+\\b', min_df=1, max_df=50)
vecs = vectorizer.fit_transform(data)
```

**３． 「k平均法」を使用してクラスタリングする。**
k平均法（kへいきんほう、英: k-means clustering）は、非階層型クラスタリングのアルゴリズム。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法（k-means）、c-平均法（c-means）とも呼ばれる。
<a href="https://ja.wikipedia.org/wiki/K%E5%B9%B3%E5%9D%87%E6%B3%95">Wikipediaより</a>

簡単にいうとN次元空間上に配置されたデータで近くにある要素を探します。

今回の要件ではまずN次元空間上にTF-IDFが掛けられた文書をすべて配置します。
（要素と要素は近所であればあるほど似ている文書ということとなります。）

その中に任意のクラスタをランダムに打ち込んですべての文書がいずれかのクラスタに所属するようにクラスタと要素の距離を計算しながら少しずつクラスタの位置を動かしていきます。
すべてのクラスタが動かなくなった（収束したら）計算終了となります。

これにもscikit-learnライブラリを使用します。

```
clusters = KMeans(n_clusters=100, random_state=0).fit_predict(vecs)
```

# 実装

```
import os
import random
import MeCab
import numpy as np

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import KMeans

def fild_all_files(directory, filename):
    for root, dirs, files in os.walk(directory):
        for file in files:
            if filename == file :
                yield os.path.join(root, file)

def get_files_with_label(label, directory, filename):
    retuenarray = np.empty((0,4))
    for file in fild_all_files(directory, filename):
        filestr = ''
        for line in open(file, 'r'):
            filestr += line.rstrip()
        
        filedata = np.array([[label, filestr, file, -1]])
        retuenarray = np.append(retuenarray, filedata, axis=0)
    return retuenarray

def get_word(str, split_char):
    returnstr = ""
    mecab_result  = MeCab.Tagger('mecabrc').parse(str)
    splited_words = mecab_result.split('\n')
    for splited_word in splited_words:
        if splited_word == 'EOS' or splited_word == '':
            break
        splited_word_info = splited_word.split(',')
        word_and_tag = splited_word_info[0].split('\t')
        if len(word_and_tag) == 2:
            word = word_and_tag[0]
            returnstr += word + split_char
    return returnstr

# 指定のディレクトリに保存してあるデータを読み込み
alldata = np.empty((0,4))
alldata = np.append(alldata, get_files_with_label('it'           , '/tmp/crawler/savedata/it'           , 'title'), axis=0)
alldata = np.append(alldata, get_files_with_label('economy'      , '/tmp/crawler/savedata/economy'      , 'title'), axis=0)
alldata = np.append(alldata, get_files_with_label('entertainment', '/tmp/crawler/savedata/entertainment', 'title'), axis=0)
alldata = np.append(alldata, get_files_with_label('sports'       , '/tmp/crawler/savedata/sports'       , 'title'), axis=0)

# 文書をスペースにて分かち書きにする
all_title_data = np.array([])
for str in alldata[:,1]:
    all_title_data = np.append(all_title_data, get_word(str, ' '))

# TF-IDFを算出する。
vectorizer = TfidfVectorizer(use_idf=True, token_pattern=u'(?u)\\b\\w+\\b', min_df=1, max_df=50, ngram_range=(1,2))
vecs = vectorizer.fit_transform(all_title_data)

# K平均法でクラスタリング、100個くらいに分類
clusters = KMeans(n_clusters=100, random_state=0).fit_predict(vecs)

# 結果をデータに戻す。
for i in range(0, len(alldata)):
    alldata[i, 3] = clusters[i]

# 適当なクラスタに属した文書を取得
result=[]
for i in range(0, len(alldata)):
    if int(alldata[i,3]) == random.randint(0,99):
        result.append(alldata[i,1])

# 表示
result.sort()
for i in range(0, len(result)):
    print(result[i])
```


# 実行結果

実行時間は3分くらいかな？
実行結果を一部抜粋

```
Windows 7 RC、日本は5月7日一般公開　「XPと同等かそれ以上に快適」
Windows 7 RCは5月5日リリース？　Microsoftがリーク
Windows 7β版、一般公開終了
Windows 7の「XPモード」、RC版公開
Windows 7の「XPモード」が完成　10月22日にリリース
Windows 7のエディションは6種類、すべてネットブックに対応――マイクロソフトが公表
Windows 7の一般販売が解禁――真夜中のアキバに1000人を超える群衆
Windows 7の評価をユーザーが投稿　MSが専用サイト
Windows 7ベータ版、一般公開期限を2月12日まで延長
Windows 7／8.1→Windows 10が“推奨される更新”に
Windows XPがもうすぐアキバから消える？ 「とりあえず再入荷はこれで最後かも」
Windows XPの「メインストリーム・サポート」が終了、14日から「延長サポート」に移行
Windows7が70円？海賊版、早速猛威振るう−北京
XPモデル、新色・新柄を追加したポケットサイズPC――「VAIO type P」
flumpool山村隆太、一般女性と結婚へ　“14年愛”を実らせライブで生報告
「Doblog」5月に終了　障害で3カ月投稿不能、一部データ復旧できず
「Skype」と「Google Voice」に脆弱性、“PBXボットネット”に悪用されるおそれも
「Surface 3」当初の販売地域に日本は含まれず ～日本へは「最適な形での投入を検討」
「Windows 7」のアップグレード、“ここ”に注意
「Windows 7」ベータ版公開一般ユーザーへの提供は9日から
「Windows 7はXPより速い」　MS公式ベンチマークの結果は
「wwwの父」がどうしてもやり直したいこと、それはhttp:のあとの//の不要化―米紙
・・・
```

（データは<a href="http://news.yahoo.co.jp/">Yahooニュース</a>様のニュースを使用させていただきました。）

う〜む・・・確かに似ている文書が集まっているが、まだ粗い。だけどk平均法なのでまだ良く分類出来たほうなのかな？
ただ特徴量を出すときに名詞のみに絞り込んだり、TF-IDFの除外する最小、最大数等の各種パラメータを調整すればもっと精度は高くなると思います。

# こういった技術は何に使えるの？

例えば

・SNS上で自分の似ているユーザを探す
・ユーザがよく見ているニュースからそのユーザが好きそうなニュースを優先して表示させる
・買い物サイトでユーザの閲覧履歴からおすすめ商品を表示させる
・掲示板サイトを作った時には投稿された文書からタグ付けが出来る

適当に考えるだけでも結構思いつき、いろいろ応用が聞くのではないのでしょうか。

また前日の記事でArata Miyauchiさんが書いてらっしゃったようにIotが進めばそこから取れるデータと、機械学習、ディープラーニングを併用することで更に便利で、面白く、楽しい世界が待っているのではないでしょうか

# 今後
今後は、SVMや、ロジスティック回帰、TensorFlowを使用してニューラルネットワークにかけてもっと精度を上げていければと思います。

### 今回使用したツール
今回使用したクローラと、HTMLから指定の要素の内容を抽出するツールは自作したものです。
githubにコードは上がってますので適当に使って頂いて結構ですが、まだちゃんとしたものではないので使用する際は自己責任で・・・

### 以上
機械学習の汎用性の高さと、楽しさを感じていただければ幸いです。