2013年2月20日水曜日

ナイーブベイズ


ナイーブベイズとは、入力文書の各単語に対して、
カテゴリー別に単語出現頻度を調べることによってカテゴリを推定する方法です。

うーん、この書き方ですと、分かりづらいですよね・・・^^;
多少具体的な例を挙げて説明してみますね。

例えば、入力文書を、野球カテゴリー/野球以外のカテゴリーの
どちらかに振り分けることを考えます。

まず、野球カテゴリー,野球以外のカテゴリーの単語出現頻度を予め求めます。
ここで、単語出現頻度は、1文書あたりに登場する平均単語数を指します。
例えば、野球カテゴリーの単語出現頻度は、各単語において、
文書に登場した回数を数え、これを文書数で割ることによって得られます。
この単語出現頻度を、野球カテゴリー,あるいは野球以外のカテゴリーの特徴
であるとします。

次に、入力文書を、どちらかのカテゴリーのいずれかに振り分けることを考えます。
文書に登場した各単語において、単語出現頻度を全て抽出し、これら全てを積算します。
これを各カテゴリーで行っておきます。

すると、入力文書が野球カテゴリーである確率と、
野球以外のカテゴリーである確率の両方が求まります。
この2つの確率を比較し、大きい方を入力文書の属するカテゴリとして出力します。


数式で書くと、評価関数f(w1,・・・,wn)が非負だったら野球カテゴリ。
負だったら野球以外のカテゴリ、と判断することになります。

f(w1,・・・,wn) = P(w1)P(w2)・・・P(wn) - Q(w1)Q(w2)・・・ Q(wn)   ・・・(式1)

ここで、

 P(wi)は、野球カテゴリーである場合の単語wiの出現頻度
 Q(wi)は、野球以外のカテゴリーである場合の単語wiの出現頻度、

をそれぞれ表します。



本来は、文書Dが野球カテゴリC1に属する確率P(C1|D),
野球以外のカテゴリC2に属する確率P(C2|D)を比較するのが妥当です。

しかし、文書Dが前提となる各カテゴリの条件付き確率を求めるためには、
実際に文書Dの特徴に極端に似ているパターンを探して、
それがカテゴリC1とカテゴリC2のどちらに属するのかを
さらに探していくことになるので、現実的には求められないものと思われます。

そこで、ベイズの定理を使って、カテゴリに属する条件の下での
確率値を求める問題にすり替えます。

ベイズの定理より、 P(C1|D)は

 P(C1|D) = P(D|C1)・P(C1)/P(D)

となります。P(C2|D)も同様です。

ここで、P(D|C1)は、クラスC1を条件とした下での文書Dが出現する確率となりますので、
予めクラスC1に属する文書を集めて確率値を求めておけば、
文書DがクラスC1に属する 確率として求めることができます。

P(D)は、C1やC2に依らない数値ですので、比較するだけだったら無視できます。

P(C1)は、C1とC2の出現する比率を表しますが、データサンプルの数が無限にあると
仮定すれば、C1とC2は等しくなるという強引な仮定を立てられるため、
P(C1) ≒ P(C2)と表現することができ、この影響も考えずに済むことになります。

このため、P(C1|D)を求める問題は、P(D|C1)を求める問題にすり替えられます。

ただ、文書Dは、そのものを数値化された特徴として表現できません。
そのため、文書Dに出現した各単語の出現頻度の積を、P(D|C1)として
扱うようにします。

この結果、式1による評価をすれば、文書DがカテゴリC1, C2のどちらに
属するのかが分かる、ということになります。



集合知プログラミングによると、
ナイーブベイズを導入することによって、
スパムメール判定の性能が格段に上がったという
実験結果があるという旨のことが書いてありました。

クラス分類問題へのアプローチとしては、とても単純ではありますが、
最終的には性能が出せれば良いのですから、
利用する側の方々にとっては御の字でしょうね。


そんなわけで、次回はナイーブベイズを使ったRのソースコードを
晒してみたいと思います。

2013年2月16日土曜日

k-近傍法のRコード

今回は、k-近傍法のRコードについて書きます。

どんな処理をしているのかとかいう話については、
前回の記事をご参照ください。

この記事を書くにあたり、 ここのブログ記事を参考にさせていただきました。



(1)例に使うソースコードの処理概要

k近傍法でクラス分類するにあたり、ラベル付きの2次元データをたくさん作成し、
そのうちの1部をテストデータ、残りのデータを学習用データとして扱います。

ここでは、2次元データを次のように作成しています。

 クラス1のデータ → 平均(1,0), 分散(0.5,0.5)の正規乱数、
 クラス2のデータ → 平均(0,1), 分散(0.5,0.5)の正規乱数

クラス1、クラス2はそれぞれ200個データを生成しています。
そして、それぞれのクラスにおいて、100個分を学習用データ、
そして残りの100個をテストデータとして使います。

そして、学習用データ,テストデータをKNN関数に食わせて
どちらに分類されるのかを見ることによって、ざっと性能を見ます。

そんな内容になっています。


(2) パッケージのインストール

ここでは、classパッケージとMASSパッケージの2つをインストールします。

 ■classパッケージ

  クラス分類器のいくつかが入っているものです。

  マニュアル を読むと、自己組織化マップやLVQも扱えるようですね。

 ■MASSパッケージ

  こちらを見ると、

    Modern Applied Statistics with S』に出てくるデータセット
   と関数パッケージ


  と書いてありますが、これが何者なのかは分かりません。

この2つのパッケージのインストールは、Rのコマンドプロンプト上で
以下のように行いました。

 $ options(CRAN="http://cran.md.tsukuba.ac.jp/")
 $ install.package("MASS");
 $ install.package("class");


(3) KNN関数の使い方


マニュアルによると、使い方はこんな感じです。

 $ res <- knn(train,test,cl,k = 1,l = 0,prob=TRUE,use.all=TRUE)

変数名 内容
train 学習用データが格納された配列
test テストデータが格納された配列
cl 学習用データに対応するラベルデータが格納された配列
k 上位何位まで取るか。k=3で上位3位。
l クラス判定する際、最低限必要とする抽出データ数。
データ数に満たない場合は、doubtを返す。
prob TRUEにすると、推定されたクラスに学習用データが
何割属していたのかを返す。
use.all TRUEの場合は、全部のデータを使用してk近傍法を行う。
FALSEの場合は、ランダムに取ってきた一部のデータで行う。
最後のuse.allですが、FALSEの場合はk近傍法そのものの意味が
破綻してしまう気がするんですが、気にしすぎでしょうかね。。。


(4) ソースコードの例

nato6933さんのブログに書いてあったソースがとてもシンプルで分かりやすいので、
大部分を参考にさせて頂きました。

参考: http://room6933.com/blog/2011/11/08/r_knn_2/



### ここから、学習用データとテストデータを生成する。

# 平均値に該当するベクトルデータを生成しています。
# この場合は、2つの列データ(1,0)をmu1に代入しています。

mu1 <- c(1,0) 

# 共分散行列を生成します。
Sigma1 <- matrix(c(0.5,0,0,0.5),2,2)

# 正規乱数を200個生成します。
dat1 <- mvrnorm(200,mu1,Sigma1)
 
mu2 <- c(0,1) #平均
Sigma2 <- matrix(c(0.5,0,0,0.5),2,2) #分散
dat2 <- mvrnorm(200,mu2,Sigma2)


# 学習用データを生成します。 
train <- rbind(dat1[1:100,],dat2[1:100,])

# テストデータを生成します。
test <- rbind(dat1[101:200,],dat2[101:200,])

# 学習用データの正解ラベルを生成します。 
cl <- factor(c(rep("green",100),rep("red",100)))

# 最上位のデータだけを使って分類する場合 
k <- 1
res1 <- knn(train,train,cl,k,prob=TRUE)
table(cl,res1)
res2 <- knn(train,test,cl,k,prob=TRUE)
table(cl,res2)

# 上位3位のデータを使って分類する場合 
k <- 3 #3近傍
res3 <- knn(train,train,cl,k,prob=TRUE)
table(cl,res3)
 
res4 <- knn(train,test,cl,k,prob=TRUE)
table(cl,res4)


テーブルには、分類結果が表示されるだけなので、
各データどんな風に分類されたのかが知りたい場合は、
Rのコマンドプロンプト上で、res1, res2, res3を
それぞれ参照してみてください。

2013年2月14日木曜日

K-近傍法

k-近傍法は、テストデータとの距離が短い順にk個の判定用データを取り出し、
多数決によってテストデータが所属するカテゴリーを推定する方法です。


例えば、以下の図を見てください。
(図は、Wikipediaの「k近傍法」の解説にあったsvgをpngに変換したものです)

 


青四角や赤三角は判定用データで、
緑丸はテストデータです。

この例では、緑丸の属するカテゴリが、
青四角が属するカテゴリなのか、

赤三角が属するカテゴリなのか、を調べます。



カテゴリの調べ方としては、

  1. 緑丸と青四角or赤三角との距離を全て求める。
     
  2. 距離の短い順に青四角or赤三角をk個抽出する。
     
  3. 抽出した青四角と赤三角の個数をそれぞれ求め、
    多い方を緑丸の属するカテゴリとする。

という手順で求めます。


k=1ならば、最も距離が短い記事に該当するカテゴリがそのまま推定結果になります。
この図だと、緑丸に最も近いのは赤三角です。
よって、

  緑丸が属するカテゴリは、赤三角が属するカテゴリ

という推定結果を得ます。


k=3の場合は、上位3つの記事が、青四角が1つ、赤三角が2つとなります。
このため、

  緑丸が属するカテゴリは、赤三角が属するカテゴリ

という推定結果を得ます。


しかし、k=5になると、上位5つは、青四角が3つ、赤三角が2つとなります。
このため、

  緑丸が属するカテゴリは、青四角が属するカテゴリ

と推定されます。



このk近傍法で気になる点は2つあります。

1つ目は、判定用データの数が膨大になったり、
判定用データに使われる独立変数が増大すると、
距離計算にかかる演算量が増えてしまう点です。

2つ目は、1部の例外的な塊が誤った推定結果を促してしまう
という懸念がある点です。



1つ目の対策としては、距離計算に使われる判定用データの数を
極力減らすことが考えれます。

例えば、各判定用データは、他のどの判定用データに近いのか、
というデータ(周辺データと呼ぶことにします)も持つようにします。
そして、次の手順を繰り返しながら距離計算に使う判定用データを
決めていきます。

  1. 最初に距離計算に使う判定用データを適当に1つ決め、ポインタを当てる。
     
  2. 決めた判定用データと周辺データとの距離を求め、その中で最小になった判定用データに
    ポインタを移す。
     
  3. 2. の作業を、判定用データそのものが最小になるまでひたすら繰り返す。

こんな感じで距離計算していけば、距離が異常に長くなるような判定用データとの
距離計算を回避することが可能になるので、演算量削減が期待できます。


2つ目の対策については、データクレンジングをきっちり行うことが挙げられます。
データクレンジングとは、一般的なカテゴリの特徴とかけ離れたデータを
取り去る作業のことを言います。
ただ、この作業をひたすら行うことは、学習をしなくても良いというメリットを損なう気もします。
だから、クレンジングしまくらなくてはならないカテゴリについては、
k近傍法ではなく、カテゴリの代表的な特徴を求める手法を使う方が良いようにも思います。

他には、アンサンブル学習を適用するのもアリかと思います。
アンサンブル学習については、後にまた改めて書くつもりなので、
今回は説明をサボります。。。(笑)


そもそも、「カテゴリに分類できる問題じゃねぇじゃん!」という話もありますが・・・。


次回の記事では、Rを使ってk近傍法を試してみたいと思います。


2013年2月13日水曜日

Rのインストール

Rのインストールのメモです。

Macbook Air MD224J/A で試しています。
詳細のスペックは、以下をご覧ください。
(というか、自分できちんと語れませんw)
http://kakaku.com/item/K0000389912/spec/#tab


(1)Rサイトに行って、ダウンロード&インストール

http://cran.r-project.org/bin/macosx/

左側に.pkgファイルのリンクがあるので、これをクリック。
すると、ダウンロードが始まる。

ダウンロードが終了したら、finderを起動し、左側の「ダウンロード」を選択。
すると、ダウンロードしたRの.pkgがあるはずなので、これをダブルクリック。
あとは、パス設定とかはデフォルト状態でひたすらOKしまくったら
無事インストールが終了した。


(2)ドッグにRのショートカットを乗せる

finderを開き、左側の「アプリケーション」を選択。
R(R64でなくて)を選択し、パッドを押さえたままドッグまで持っていく。


(3)Rprofileの編集

多分、Rprofileはないと思うので、.Rprofileをホームディレクトリに作る。

 $ cd
 $ touch .Rprofile

そして、.RProfileには、以下のように記述する。
 options(repos=”http://cran.md.tsukuba.ac.jp/”)


とりあえず、これで起動してみる。

参考:
 http://d.hatena.ne.jp/foo22222/20100913/1284138268

てすと

てすと。
できるかな?? 
参考:http://osamu-tadanomemo.blogspot.jp/2012/03/blogger.html
  public class Test {
    public static void main(String args[]) {
      System.out.println("Hello, world!");
    }
  }
できたみたい。 参考サイトに感謝。