自動要約アルゴリズムLexRankを用いたECサイトの商品価値の要約

# はじめに
人工知能の研究・開発が近年ブームとなってきており，様々な分野で色々な成果が出ています．
文書の自動要約技術も大きな枠組みではAIの分野で，専門的には自然言語処理という分野になります．
文書要約は，新幹線の電光掲示板やWebニュースの見出しに用いられたりしますが，使い方はニュースのようなきっちりした文書に限らないと思います．

本記事では，文書要約アルゴリズムLexRankを用いて，ECサイト(楽天)の商品レビューを要約することで素早く購入者の典型的なレビューを可視化することをやってみたいと思います．

# LexRank
LexRankはErkanらがPageRankの概念を元に提案した文書要約のアルゴリズムになります．
> 元論文: [LexRank: Graph-based Lexical Centrality as Salience in Text Summarization](http://www.jair.org/media/1523/live-1523-2354-jair.pdf)

細かいところは省略しますが，LexRankにおいて大切にしている概念は次の2つだけです．

- 多くの文に類似する文は，重要文である
- 重要な文に類似する文は，重要文である

上記2つの概念を，グラフ化すると下図のようになります．
(dXsY: 文書XのY番目の文)

![Kobito.LIwsUr.png](https://qiita-image-store.s3.amazonaws.com/0/117645/a650e4a2-b980-030a-96b7-5abc0f3113bc.png "Kobito.LIwsUr.png")
Figure: 類似度グラフの例([Erkan 04]より抜粋)

太いエッジが張っている先のノードはそれだけ重要度が高く，重要度の高いノードからエッジが張られているノードもまた重要度が高いと考えます．

# ECサイトのレビュー要約
Amazonや楽天を使っていると，こんなことをよく感じます．

- レビュー数がものすごく多くて信憑性は高そうだけど，どのレビューを参考にすればいいのか分からない！
- 参考になったかどうか投票できるようになっているが，参考になるレビューが長文…

そこで今回は， **膨大な数のレビュー文から，みんながレビューしているような部分を含む要約文をn文で出力する**ことを目標とします．
このことにより，何100件レビューがあろうとも，長文レビューがあろうとも省エネでレビューの雰囲気をつかむことができるようになるはずです！

## 依存環境
今回のスクリプトは，下記のパッケージに依存します．
全てpip install / conda installで簡単に導入できます．
- numpy 1.11.1
- scipy 0.18.1
- fasttext 0.8.0 (文章のベクトル化でword2vecを用いる場合は必要です)

## 実装
作成したLexRankのmainコードは以下のようになります．
このアルゴリズムは，元論文のAlgorithm3を参考にしています．

```py:lexrank.py
def lexrank(sentences, N, threshold, vectorizer):

    CosineMatrix = np.zeros([N, N])
    degree = np.zeros(N)
    L = np.zeros(N)

    if vectorizer == "tf-idf":
        vector = tfidf.compute_tfidf(sentences)
    elif vectorizer == "word2vec":
        vector = tfidf.compute_word2vec(sentences)

    # Computing Adjacency Matrix                                                                                                                                         
    for i in range(N):
        for j in range(N):
            CosineMatrix[i,j] = tfidf.compute_cosine(vector[i], vector[j])
            if CosineMatrix[i,j] > threshold:
                CosineMatrix[i,j] = 1
                degree[i] += 1
            else:
                CosineMatrix[i,j] = 0

    # Computing LexRank Score                                                                                                                                            
    for i in range(N):
        for j in range(N):
            CosineMatrix[i,j] = CosineMatrix[i,j] / degree[i]

    L = PowerMethod(CosineMatrix, N, err_tol=10e-6)

    return L
```

- Input:
	- sentneces: 入力文のリスト
	- N: 入力文数
	- threshold: 隣接行列(類似度グラフ)を作成する際の類似度の閾値
	- vectorizer: 文のベクトル化の手法(tf-idf/word2vec)

- Output:
	- L: LexRankのスコア(各文章の重要度)

LexRankスコアLは，固有ベクトルを指します．
元論文では，PowerMethod(べき乗法)を用いて求めています．

```py:PowerMethod
def PowerMethod(CosineMatrix, N, err_tol):

    p_old = np.array([1.0/N]*N)
    err = 1

    while err > err_tol:
        err = 1
        p = np.dot(CosineMatrix.T, p_old)
        err = np.linalg.norm(p - p_old)
        p_old = p

    return p
```

- Input:
	- CosineMatrix: 隣接行列
	- N: 入力文数
	- err_tol: PowerMethodにより収束したと判定するための誤差許容値

- Output:
	- p: 固有ベクトル (LexRankスコア)

## 実行結果
今回は楽天に出品されている以下のゲーム機のレビューについて要約したいと思います．(一応，機種名だけでどの商品かについては，伏せておきます)

### tf-idf model
文章のベクトル化をtf-idfを用いて行い，隣接行列を作成したモデルの要約がこちらです．
ちなみに，元論文ではtf-idfモデルで隣接行列を作成しています．(当時word2vecはありませんでした)

- PlayStation4
> 1: だいぶ前に他のメーカーのテレビゲームを持っていましたが、こんなにも進化しているとは驚きです！画像の綺麗なのはもちろんの事、色んな機能が付いていて、これならこの値段は仕方ないのかなと思いました。こちらのショップは、ポイントも多めに付くし、クーポンもあったので、思った以上に安くなり買って良かったです。
2: こちらで購入しました。
3: 家族が購入したのですが、高性能でびっくりしています。


- Nintendo 3DS LL
> 1: 弟のクリスマスプレゼント用にNintendoNew3DSを注文させて頂きました。注文してから予想以上に早く届きました。ゲーム機ですのでもう少し包装をしっかりして欲しいかなと思いましたが、初期不良・箱に傷も無かったので良しです(笑)また、何かありましたら宜しくお願いします。
2: 3DSを持っていたのですが液晶が壊れ一度修理したのですが再度壊れてしまい、あらたに3DSを購入する羽目に。どうせ買うなら次は画面の大きいもののほうがいいと思いLLを購入しました。
3: 子供のクリスマスプレゼントに購入しました。

PS4は高性能であるという特徴が抽出され，3DSは子供用のプレゼントとして購入される方が多いということがつかめています．
一方で，どちらの商品についても一文目のレビューが冗長なので，もう少しセグメントを考える必要がありそうです．
また，PS4の2文目の情報は特に有益な情報を持たないので，今回のタスクでは抽出するべきでないと考えられます．

### word2vec model
文章のベクトル化をword2vecを用いて行い，隣接行列を作成したモデルの要約がこちらです．
事前学習させた単語ベクトルにより，文章に含まれる全単語の重心を文ベクトルとしています．

- PlayStation4
> 1: ポイントを使ったがなんか損した気分
2: 問題なく使えてます♪
3: テレビに映る画面がかなりきれいになっています。

- Nintendo 3DS LL
> 1: 子供が使うものとしては、3DSと同じ折りたたみタイプで、ちょっと前に出た2DSのようなシンプルな機能のもので、もう少しお安いものがあればいいんですけどね。
2: すぐに発送して頂けたのでよかったです。
3: 急遽LLに買い替えです。

tf-idfモデルの要約と比較すると，より簡潔な要約文であるような印象を受けます．
ただし，要約の内容が商品のレビューではないものも含まれています．
意味的に多くの文に類似する文のスコアが高くなるので，出力された要約はある意味もっともらしいものが多いと言える反面，今回の課題では工夫が必要そうです．

# まとめ
今回は自動要約アルゴリズムLexRankを用いてECサイトのレビュー要約を行いました．
大量のレビューを要約することで，効率的に商品の特徴が掴めるようになりそうです．
一方で，文のセグメントや冗長性の削減などもう少し工夫する必要があると感じました．
その点については，また今度作成したいと思います．


# おまけ
各文の類似度計算のためのベクトル計算法(tf-idf, word2vec)のコードを下記に載せます．
このスクリプト自体はlexrank.pyの中で呼び出しています．(vector = tfidf.compute_tfidf(sentences))
lexrank.pyの中でimport tfidf　のようにすれば，実行できます．
あと，word2vecモデルで呼び出している単語ベクトルモデル('../models/wiki_sg_d100.bin')というのは，日本語のWikipediaの全文から学習させた単語ベクトルです．

```py:tfidf.py
#!/usr/bin/env python                                                                                                                                                    
# -*- coding: utf-8 -*-                                                                                                                                                  

import sys
import numpy as np
import fasttext as ft
from scipy.spatial import distance


def word2id(bow, word_id):

    for w in bow:
        if word_id.has_key(w) == False:
            word_id[w] = len(word_id)

    return word_id

def compute_tf(sentences, word_id):

    tf = np.zeros([len(sentences), len(word_id)])

    for i in range(len(sentences)):
        for w in sentences[i]:
            tf[i][word_id[w]] += 1

    return tf

def compute_df(sentences, word_id):

    df = np.zeros(len(word_id))

    for i in range(len(sentences)):
        exist = {}
        for w in sentences[i]:
            if exist.has_key(w) == False:
                df[word_id[w]] += 1
                exist[w] = 1
            else:
                continue

    return df

def compute_idf(sentences, word_id):

    idf = np.zeros(len(word_id))
    df = compute_df(sentences, word_id)

    for i in range(len(df)):
        idf[i] = np.log(len(sentences)/df[i]) + 1

    return idf

def compute_tfidf(sentences):

    word_id = {}

    for sent in sentences:
        word_id = word2id(sent, word_id)

    tf = compute_tf(sentences, word_id)
    idf = compute_idf(sentences, word_id)

    tf_idf = np.zeros([len(sentences), len(word_id)])

    for i in range(len(sentences)):
        tf_idf[i] = tf[i] * idf

    return tf_idf

def compute_cosine(v1, v2):

    return 1 - distance.cosine(v1, v2)
    
def sent2vec(bow, model_w):

    vector = np.zeros(100)
    N = len(bow)

    for b in bow:
        try:
            vector += model_w[b]
        except:
            continue

    vector = vector / float(N)

    return vector

def compute_word2vec(sentences):

    model_w = ft.load_model('../models/wiki_sg_d100.bin')
    vector = np.zeros([len(sentences), 100])

    for i in range(len(sentences)):
        vector[i] = sent2vec(sentences[i], model_w)

    return vector
 
if __name__ == "__main__":

    pass       
```