2015-11-23

目的

テキストデータから特徴ベクトルを作って何かやろうと思ったときに，私の場合は何も考えずに単語文書行列を作ってナイーブベイズのようなベースライン的な手法を試すところからはじめます。単語文書行列というのは以下のページに載っているような行列です。英語ではDocument-Term Matrixといいます。

ベクトル空間モデル - Wikipedia

Wikipediaに載っているように，行方向に単語，列方向に文書を並べるのが普通です。ただし，scikit-learnの慣習では行方向に事例，列方向に素性を並べるため，逆になります。

語のリストから単語文書行列を作るときには，(a) collections.Counterとsklearn.feature_extraction.DictVectorizerを使う方法 がシンプルでおすすめです。一方で，scikit-learnにはsklearn.feature_extraction.textという，テキストデータから特徴ベクトルを作るためのモジュールがあるのですが，このモジュールの中では先ほど述べた手法とは少し違った方法で単語文書行列を作っています。この方法のことを(b) sklearn.feature_extraction.text.CountVectorizerで使われている方法と呼ぶことにします。scikit-learnにはDictVectorizerという便利なクラスがありながら，どうして別の方法を使っているんでしょうか？もしかして，(a)の方法は(b)の方法と比べて100倍くらい遅かったりするんでしょうか？実際に計測してみました。

(a) collections.Counterとsklearn.feature_extraction.DictVectorizerを使う方法

collections.Counterは標準ライブラリに含まれているクラスで，iterableを投げつけるとカウントしてくれます。

import collections
collections.Counter(['a', 'b', 'a', 'd', 'a']) # => Counter({'a': 3, 'b': 1, 'd': 1})

sklearn.feature_extraction.DictVectorizerは素性名，素性値のペアが入ったdictを投げつけると疎行列 (scipy.sparse.csr_matrix) に変換してくれるクラスです。

from sklearn.feature_extraction import DictVectorizer
v = DictVectorizer()
v.fit_transform([{'a': 3, 'b': 1, 'd': 1}, {'a': 1, 'c': 3, 'd': 2}]).toarray()
# => array([[ 3.,  1.,  0.,  1.],
#           [ 1.,  0.,  3.,  2.]])

この2つを組み合わせると単語文書行列が作れます。

def by_counter_dictvectorizer(documents):
    tf_list = []
    for document in documents:
        tf = Counter(document)
        tf_list.append(tf)

    v = DictVectorizer(sort=False)
    return v.fit_transform(tf_list)

sortというオプションは素性名の順番にソートするかどうかを決めるものでデフォルトはTrueですが，特に必要無いのでFalseに設定しました。

(b) sklearn.feature_extraction.text.CountVectorizerで使われている方法

以下のコードを参考にしました。

sklearn.feature_extraction.textはscikit-learnのモジュールで，ファイルの読み込み → 分かち書き，見出し語化 → ストップワード削除 → 単語文書行列の構築 → 頻度フィルタリング → TF-IDFの算出 → L1 or L2 正規化といった一連の処理をやってくれるクラス (CountVectorizer, HashingVectorizer, TfidfTransformer, TfidfVectorizer) が含まれています。

日本語の処理に使いたい場合には，文書を引数に取って語のリストを返す関数を定義して，コンストラクタの引数のanalyzerに渡せばよいです。

最初にcollections.defaultdictを使った怪しいコードがありますが，これはアイテムにIDを振るときの一般的なテクとして一部で知られています。defaultdictは基本的にはPythonの普通のdictとして振る舞いますが，存在しない要素をgetしようとしたときにはdefault_factory関数を呼び，その結果を返します。

vocabulary = defaultdict()
vocabulary.default_factory = vocabulary.__len__
vocabulary['a'] # => 0
vocabulary['b'] # => 1
vocabulary['a'] # => 0
vocabulary['c'] # => 2
vocabulary['a'] # => 0

次にj_indicesやindptrといった怪しげな変数が使われていますが，これは疎行列 (scipy.sparse.csr_matrix) の実装と関係があります。実装の詳細は以下のページが分かりやすいです。

scipy.sparseの内部データ構造 – はむかず！

scipy.sparse.csr_matrixのコンストラクタには，data, indices, indptrの組を引数にとるものもあり，CountVectorizer内の実装ではこれを利用しています。

scipy.sparse.csr_matrix — SciPy v0.16.1 Reference Guide

測定方法

Macbook Air (13-inch, Mid 2011, Core i5 1.7 GHz, Yosemite) 上にHomebrewでインストールしたPython 3.5.0で動かします。

私のブログ (くじらにっき++) のそれぞれの記事をMeCab + IPADIC-NEologdに入力して得られた語のリストを，(a), (b) の方法で単語文書行列を作る関数の入力として，単語文書行列であるscipy.sparse.csr_matrixを構築する時間を計測します。50回測定しました。

ソースコードを以下に示します。

import json
import time
from array import array
from collections import Counter, defaultdict

import numpy
from scipy.sparse import csr_matrix
from sklearn.feature_extraction import DictVectorizer


def by_counter_dictvectorizer(documents):
    tf_list = []
    for document in documents:
        tf = Counter(document)
        tf_list.append(tf)

    v = DictVectorizer(sort=False)
    return v.fit_transform(tf_list)


def by_countvectorizer(documents):
    vocabulary = defaultdict()
    vocabulary.default_factory = vocabulary.__len__
    j_indices = array('i')
    indptr = array('i')
    indptr.append(0)
    for document in documents:
        for word in document:
            j_indices.append(vocabulary[word])
        indptr.append(len(j_indices))

    j_indices = numpy.frombuffer(j_indices, dtype=numpy.intc)
    indptr = numpy.frombuffer(indptr, dtype=numpy.intc)
    values = numpy.ones(len(j_indices))

    X = csr_matrix((values, j_indices, indptr),
                   shape=(len(indptr) - 1, len(vocabulary)))
    X.sum_duplicates()
    return X


def main():
    with open('blog.json') as f:
        documents = json.load(f).values()

    # documents = [
    #     ['a', 'b', 'a', 'd', 'a'],
    #     ['c', 'c', 'd', 'a', 'd', 'c'],
    # ]

    method1 = []
    method2 = []

    for i in range(50):
        start = time.time()
        X = by_counter_dictvectorizer(documents)
        elapsed = time.time() - start
        method1.append(elapsed)

        start = time.time()
        X = by_countvectorizer(documents)
        elapsed = time.time() - start
        method2.append(elapsed)

    print('Counter + DictVectorizer', numpy.mean(method1), numpy.std(method1))
    print('CountVectorizer', numpy.mean(method2), numpy.std(method2))

if __name__ == '__main__':
    main()

結果

手法	平均 (sec)	標準偏差 (sec)
(a)	0.0405	0.00450
(b)	0.0252	0.00265

(a) が (b) と比べて約1.6倍時間がかかっています。

まとめ

(a) collections.Counterとsklearn.feature_extraction.DictVectorizerを使う方法は(b) sklearn.feature_extraction.text.CountVectorizerで使われている方法と比較して遅いです。ただし，処理時間は2倍以内には収まります。タスクによるかとは思いますが，機械学習するときに最も計算コストがかかるのはこの後の処理なので，全体としてみれば小さな差と言えるのではないかと思います。

DictVectorizerはカテゴリ素性を含むデータをOneHot表現の疎ベクトルに変換する際にも汎用的に使うことができるので，この程度の差しか無いのであればDictVectorizerを使う方法だけ覚えておいても良いのではないでしょうか。

おまけ

scikit-learnを使ってできることを一通り試してみたいという方には，以下の書籍がおすすめです。実践寄りの内容ですが，理論的な背景についても少なくない分量を割いています。「数学をバリバリ使っている本がほしい！」「厳密さが足りない！」という人には物足りないかもしれませんが，scikit-learnを初めて触る人には有益な情報を与えてくれると思います。

Python機械学習プログラミング達人データサイエンティストによる理論と実践 (impress top gear)

作者: Sebastian Raschka,株式会社クイープ,福島真太朗
出版社/メーカー: インプレス
発売日: 2016/06/30
メディア: 単行本（ソフトカバー）
この商品を含むブログ (3件) を見る

scikit-learn関連記事

kujira16.hateblo.jp

2015/Practice/模擬地区予選/案内 - ACM-ICPC Japanese Alumni Group

メンバー

私
OUDON氏
23氏

解けた問題

A. M and A

問題文

KADOKAWAとdwangoが云々という説明をする。「LCSするだけやん！」と謎の早とちりをしてWAを量産してしまう。つらい。

OUDON氏にGreedyにやるだけだと諭される。バグを仕込む。つらい。

自分で見つけられなくてOUDON氏に指摘される。AC。やったぜ。

B. Change a Password

問題文

「同じ文字が含まれないような数字って多くないよね」「それ高々10!やん」「あっ（察し）」やったぜ。

stringstreamが遅くてchar配列で書き直す。つらい。

C. Delete Files

問題文

「高い山を見つけて分割していってDPで〜♪」といった誤解釈でWAを量産してしまう。つらい。

OUDON氏 & 23氏チームが謎Greedyを提案してくれる。僕には理解できないが，今までに作ったテストケースが全部解けるようなので淡々と実装する。AC。たまげたなぁ。

D. Line Gimmick

問題文

「夏合宿の問題みたいに1回のシミュレーションはdancing linksでO(N)で出来るよね」「N <= 10⁵だから100回くらいはシミュレーションできるよ。log N回で決められないかな？」「log N… あっ（察し）」

（「あるマスxから始めると左から出て行ったならば，xよりも左側にある任意のマスから始めても左から出ていく」と仮定します。この予想が正しければ，左から出て行くマスと右から出て行くマスの境界が二分探索によりlog N回で決められます。あとは，境界の右と左からシミュレーションすることにより，乗ることが出来るマスの数を計算すればよいです。時間計算量はO(N log N)です）

E. Shifting a Matrix

問題文

OUDON氏にやるだけと言われる。殺人的に実装量が多い予感がしたが，それほどでもなかった。

H. Donut Decoration

問題文

範囲update (加算ではなく変更)，範囲minを実現する平方分割が，いわゆる遅延セグメント木のテクニックを応用することにより実現できた記憶があったので，すんなり実装できた。TLEは5秒だし間に合うでしょ → 2200msでAC。やったぜ。

（平方分割によるセグメント木の代用は，3〜5倍程度遅くなる程度で済むことが多いです。この差が致命的になることもあるのかもしれませんが，セグメント木は実装によって速度に幅が出るので，多くの問題ではTLEに余裕を持たせています。）

解けてない問題

F. Modern Announce Network

問題文

これグラフ理論の何ていう問題だっけ？というところから忘れていた（最小シュタイナー木）。もちろん計算量も忘れていた。

グループが3つしか無いことを利用して何かやるんだろうということから変な解法を実装してみたけど，コンパイルエラーを直している間にモーダルが現れて死。

その他

私は読んでいない。

まとめ

貪欲は私以外のメンバーに任せるとポジティブな結果が得られる。

くじらにっき++

scikit-learnで単語文書行列を作る方法の比較

目的