potix2/Chapter3.md

## Chapter3.md

      
    Raw
  

              Chapter3.md
            
          
    3章 クラスタリング: 関連のある文書を見つける


ラベル付きデータが入手できない状況を考える
Q&Aサイトを運営する場面。今見ているページ内容と関連する情報を提示したい。
文書間の類似度を素早く算出することで実現する。クラスタリングを使う。

3.1 文書の関連性を計測する

3.1.1 やってはいけないこと

レーベンシュタイン距離(levenshtein distance)


1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される

https://ja.m.wikipedia.org/wiki/レーベンシュタイン距離

machine と mchiene の距離は2
長さmとnの文書間の距離を計算するアルゴリズムのオーダーは*O(mn)*になる

なぜダメなのか？


計算コストが高い
単語の順序についてロバストでない(影響を受けやすい)

Bag of words

文書内に単語が含まれるかどうかだけに着目したモデル。単語の並び順は考慮しない。文書の各単語に対して出現回数をカウントしてベクトルとして表現する。これは、*ベクトル化(vectorization)と呼ばれ、このベクトルを特徴ベクトル(feature vectors)*と呼ぶ。
単語の種類が、
(disk, format, now, hard, my, problems, to)
のとき、“Hard disk format problems” の特徴ベクトルは、
(1,1,0,1,0,1,0)
となる。
ベクトル化すればユークリッド距離で比較できるようになる。
また最近傍点を見つけられる。ただし、時間がかかってしまう(これは、何故か？)
クラスタリングの手順


各文書から特徴量を抽出し、特徴ベクトルの形で保存する。
特徴ベクトルに対して、クラスタリングを行う。
投稿された質問文書に対して、クラスタを決定する。
このクラスタに属する文書を他にいくつか集める。

3.2 前処理: 共通する単語の出現回数を類似度として計測する

bag-of-wordsは高速でロバストだが問題がないわけではない。
3.2.1 テキストデータをbag-of-wordに変換する

sklearnのCountVectorizerを使う。
3.2.2 単語を数える

import scipy as sp
def dist_raw(v1, v2):
	delta = v1 - v2
	return sp.linalg.norm(delta.toarray())

ユークリッド距離を計算する関数。これを使って文書間の距離を計算し、最も近いものが類似度が高いと言える。
3.2.3 単語の出現回数ベクトルを正規化する

単語の出現回数からなるベクトルではなく、正規化したベクトルを返すようにする。
def dist_norm(v1, v2):
	v1_normalized = v1 / sp.linalg.norm(v1.toarray())
	v2_normalized = v2 / sp.linalg.norm(v2.toarray())
	delta = v1_normalized / v2_normalized
	return sp.linalg.norm(delta.toarray())

3.2.4 重要度の低い単語を取り除く

stop wordを取り除く。mostとか分野に関係なく現れる単語のこと。
3.2.5 ステミング(stemming)

imageとimagesが別な単語として扱われている。語幹に変換する処理のことをステミングという。
3.2.6 TF-IDFを用いる

TF-IDF(term frequency - inverse document frequency)
d: 文書
t:  単語
n(i,j): 単語t(i)の文書d(j)における出現回数
TF(i, j) = n(i,j) / Σ n(k,j)
IDF(i) = log( |D| / |{d: d∋t(i)}|)
https://ja.wikipedia.org/wiki/Tf-idf
特定の文書だけで現れやすい単語に特徴量として大きい値を設定できるようになる。
3.2.7 ここまでやってきたこと

テキストデータの前処理
bag-of-wordsの欠点


単語の関連性を考慮していない
否定的な意味を正しく考慮していない。bi-gramやtri-gramをカウントすることで対応できる。
タイプミスに対応できない

3.3 クラスタリング


フラットクラスタリング (flat clustering)
階層的クラスタリング (hierarchical clustering)

フラットクラスタリングでは予めクラスタ数を決める必要がある。階層的クラスタリングではクラスタ数を指定する必要はない。
3.3.1 KMeans

フラットクラスタリング。よく用いられる。

クラスタの数だけ任意に選び出し、クラスタの中心点とする
選ばれなかったデータも最も近い中心点をもつクラスタとする。
各クラスタで中心点を更新する。クラスタに属するデータの平均を中心とする。
中心点が動かなくなる（閾値以下の移動量になる）まで中心点の更新を繰り返す。


中心点が動く様子。
3.3.2 テストデータを用いて評価を行う


20newsgroupというデータセットを使ってテスト
正解となるラベルがすでにわかっている

3.3.3 文書のクラスタリング


現実のデータにはノイズが含まれる
UnicodeDecodeError: 不適切な文字が含まれているなど

3.4 最初の問題に対する答え


新しい文書が来たときにラベル予測をする
まず、文書をベクトル化してから予測する

予測ができたら、同じクラスタに所属する文書との類似度を評価する
3.4.1 ノイズに対する別の見方

comp.graphicsに所属する決め手を見つけることができるか？
やったこと


ストップワードの削除
TF/IDFの計算

結論

識別性の高い単語を見つけるのは難しい
3.5 パラメータの調整

調整するパラメータや手法はいろいろあるが、「より良い」とはどういうことかを定義しておく必要がある。 scikitでは sklearn.metricsというパッケージがありクラスタリングの性能を計測するための評価関数が含まれている。