データサイエンティスト上がりのDX参謀・起業家

データサイエンティスト上がりのDX参謀・起業家のブログ。データ分析や事業について。自身はアーティスト、経営者、事業家。

バッギング、ランダムフォレスト、ブースティング

今回は集団学習（アンサンブル学習）で良く出てくる、バッギング、ランダムフォレスト、ブースティングについてメモしておきます。参考にしている教科書はこちらです。貼りつけている数式もこの教科書から抜粋しています。


The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition (Springer Series in Statistics)

The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition (Springer Series in Statistics)

どの手法も、「弱い学習器」をたくさん集めて良い予測値を得ることを目指しています。弱学習器を集めているせいか、予測精度は高いのに過適合しにくいのが特徴です。教科書の事例では学習データでどんどん学習させても、テストデータに対して予測エラーが全然上がらない（つまり過学習していない）。


1. バッギング（Bagging）

データをブートストラップサンプリングし、予測器f(x)を作る。それをB回繰り返し、それぞれの予測器の平均値を予測値とする。

特に、f(x)が決定木（decision tree）の場合をバッギング木（bagged tree）という。



2. ランダムフォレスト（Random Forest）

バッギング木と似たアルゴリズムだが、説明変数もランダムにm個選択するところが大きく異なる。バッギングと同じように、データは毎回ブートストラップサンプリングする（P588）。




3. ブースティング（Boosting）

アルゴリズムGの予測値を実測値に近づけるように、予測値の加重和パラメータω、アルゴリズムの加重和パラメータαを計算する。最終的にM個作ったアルゴリズムをαで加重和したものを予測値とする（下記の結果変数は[-1, 1]なのでsignを予測値としている）。

パラメータの計算方法で最も有名な方法が、アダブーストM1（Ada Boost.M1）である（P339）。また、アルゴリズムGの損失関数の微分（勾配）を利用して、パラメータ更新を素早く行うことのできる手法が、勾配ブースティングモデル（Gradient Boosting Model, GBM）である（P361）。

Facebookの情報を取得する

あけましておめでとうございます。今年初の記事です。Rbloggersで気になった記事があったので、やってみようと思ったのですが、、、

http://applyr.blogspot.com/2012/01/mining-facebook-data-most-liked-status.html


いろいろ下記の設定をしたのですが、結局Rgraphvizが自分のマシンでは動かず、グラフを描くところまで行きませんでした。


コードはこちら↓

access_token <- "...................."

require(RCurl)
require(rjson)

# Facebook json function copied from original (Romain Francois) post
facebook <-  function( path = "me", access_token, options){
   if( !missing(options) ){
        options <- sprintf( "?%s", paste( names(options), "=", 
                           unlist(options), collapse = "&", sep = "" ) )
    } else {
        options <- ""
    }
    data <- getURL( sprintf( "https://graph.facebook.com/%s%s&access_token=%s",
                    path, options, access_token ), ssl.verifypeer = FALSE )
    fromJSON( data )
}


friends <- facebook( path=".../friends" , access_token=access_token)
# extract Facebook IDs
friends.id <- sapply(friends$data, function(x) x$id)


friends.name <- sapply(friends$data, function(x)  iconv(x$name,"UTF-8","ASCII//TRANSLIT"))
# short names to initials 
initials <- function(x) paste(substr(x,1,1), collapse="")
friends.initial <- sapply(strsplit(friends.name," "), initials) 

# friendship relation matrix
N <- length(friends.id)
friendship.matrix <- matrix(0,N,N)
for (i in 1:N) {
  tmp <- facebook( path=paste(".../mutualfriends", friends.id[i], sep="/") , access_token=access_token)
  mutualfriends <- sapply(tmp$data, function(x) x$id)
  friendship.matrix[i,friends.id %in% mutualfriends] <- 1
}

require(Rgraphviz)
# convert relation matrix to graph
g <- new("graphAM", adjMat=friendship.matrix)

# ellipse graph with initials
pdf(file="facebook1.pdf", width=25, height=25)
  attrs <- list(node=list(shape="ellipse", fixedsize=FALSE))
  nAttrs <- list(label=friends.initial)
  names(nAttrs$label) <- nodes(g)
  plot(g, "neato", attrs=attrs, nodeAttrs=nAttrs)
dev.off()


自分の環境では、最後のplot()でRがクラッシュてしまいます（32 bit版のRを使っても）。友人情報は取得できたので、Graphviz以外の方法でグラフを描けばいいかも。しかしRは他ソフトと連携しようとすると、エラーが多くなって安心して使えないですね。Rに限った話では無いかもしれませんが。


今回うまくいかなかったのも、原因は確定できませんが、64bitマシンを使ったからかなぁと。OSが変わるといろいろ大変ですね。。うまく行った方がいらっしゃれば、ぜひ教えて頂ければ幸いです。

今年紹介してきた統計学・機械学習・R・データマイニングの本やサイトまとめ

もう今年も終わりですね。今日はクリスマスというのに何をしてるのやら、、、とか思いつつ記事を書いてます。1年の大掃除の意味も込めて、今年いろんな人に紹介してきた本やサイトをまとめておこうかなと思います。



まずは定番の2冊。「機械学習」「統計的学習」と名前は分かれていますが、同じ手法を視点を変えて説明しているような感じです。


機械学習をいきなり英語で本格的に学ぶのがキツい場合は、これらの本やサイトが網羅的なのでオススメです。

多変量解析入門――線形から非線形へ

多変量解析入門――線形から非線形へ


英語の初級本は「おしゃスタ」勉強会でも使っている、この本。


初級〜中級以上は日本語のこの本です（この本はシリーズになっていて、他の2冊もオススメです）。

統計学入門 (基礎統計学?)

統計学入門 (基礎統計学?)

一般化線形モデルのこの本も追記。

一般化線形モデル入門 原著第2版

一般化線形モデル入門 原著第2版



学術的な本が辛い場合は、これらの読み物が良いと思います（読み物系は他にもいろいろありますのでお好みで）。

統計学とは何か ―偶然を生かす (ちくま学芸文庫)

統計学とは何か ―偶然を生かす (ちくま学芸文庫)

分析力を駆使する企業 発展の五段階

分析力を駆使する企業 発展の五段階



次にRの本やサイトです。

統計学:Rを用いた入門書

統計学:Rを用いた入門書

Rによるデータサイエンス データ解析の基礎から最新手法まで

Rによるデータサイエンス データ解析の基礎から最新手法まで

Rによる統計解析ハンドブック

Rによる統計解析ハンドブック

  • 作者: Brian S.Everitt,Torsten Hothorn,大門貴志,吉川俊博,手良向聡
  • 出版社/メーカー: メディカル・パブリケーションズ
  • 発売日: 2010/04
  • メディア: 単行本
  • 購入: 20人 クリック: 744回
  • この商品を含むブログ (6件) を見る


Data Mining with R: Learning with Case Studies (Chapman & Hall/CRC Data Mining and Knowledge Discovery Series)

Data Mining with R: Learning with Case Studies (Chapman & Hall/CRC Data Mining and Knowledge Discovery Series)

The Art of R Programming: A Tour of Statistical Software Design

The Art of R Programming: A Tour of Statistical Software Design

An R and S-Plus Companion to Multivariate Analysis

An R and S-Plus Companion to Multivariate Analysis

この本はMDSやコレスポンデンス分析についても書いてあります。


最後にデータマイニング系のサイトです。

資料はこれくらいでしょうか。

もうすぐ今年も終わりですね。この1年はいろいろありました。iana設立、おしゃスタ開催、TokyoRやTokyoWebminingに参加し始めたのも今年の4月からでした。ビジネス目的で海外に行ったのも初めてでした。いろんなところで新しい友人や仲間ができ、とても良い年でした。年の瀬にまた今年を振り返って、来年をより成長できる年にできるよう、頑張っていきたいですね！！

Twitterのフォロワーマップ

Twitterのフォロワーがどこに居るのかをマップで描いてくれる関数がR-bloggersに公開されました。


図がとても綺麗なので、せっかくなのでやってみました。RCurlが必要なのですが、windowsの場合、RCurlがinstall.packages()ではインストールできないので、下記からzipで落としてローカルからインストールしておきます。


その後、下記を実行します（isseing333の部分は適宜、興味あるユーザーに変更して下さい）。

source("http://biostat.jhsph.edu/~jleek/code/twitterMap.R")
options(encoding="shift-jis")
twitterMap("isseing333")


日本語がエンコーディングの問題で扱えないようなので、options(encoding="shift-jis")を指定しています。それでもwarningがいくつも出るので、userLocationオプション等を設定する必要があるのかもしれません。


実行すると、時間はフォロワー数にもよると思いますが、数分後にpdfファイルが作業ディレクトリに保存されます。結果はこんな感じです。


全フォロワーが描画されているわけではなさそうなので、詳細を知る場合は関数内部をハッキングする必要がありそうです。

おしゃれStatistics@銀座が開催されました！

先日、おしゃスタが銀座で開催されました。リクルート社さんのメディアテクノロジーラボ（MTL）という会場です。とてもおしゃれな会場で、ちょっとビックリ＆緊張しましたw 発表の内容はUSTになっているので、統計学にご興味のある方はぜひ。


おしゃスタat銀座


また、MTLさんのブログでも紹介されております。


いつもと違う会場でしたが、とても雰囲気が良くアットホームな感じで発表ができました。今回は私の他に@millionsmileさんと@teramonagiさんがスピーカーをしていらしたのですが、2人とも統計を違った分野で活用している事例だったのでとても興味深かったです。色んな分野での応用事例を勉強できるのは面白いですね。


統計学と複雑ネットワークのちょっと深いい話 - おしゃれStatistics @銀座
View more presentations from Hiroko Mills

金融業界でよく使う統計学
View more presentations from teramonagi



思い起こせば、おしゃスタは第1回が歌舞伎町のルノアールで行われ、今回は6回目でした。初回は7人でしたが、今回は約40人の方に来て頂けました。勉強会を始めた頃は、年末にこのような規模で行なうことができるとは思っておらず、参加者の皆様やスタッフのみんなには、ただただ感謝ですm(__)m

過去の開催はこのような感じでした。

せっかくなので、これまでのおしゃスタの「参加人数」「キャンセル人数」「キャンセル割合」をグラフにしてみました。


こうしてみると、普段はキャンセル率が結構高いですが、今回は参加人数が多い割にキャンセル率が少ないですね。銀座MTLで開催されたり、ゲストスピーカーさんが発表して下さったお陰でしょうか！

このグラフのRコードはこちらです（2軸プロットになっています）。

x  <- c(7, 15, 23, 22, 17, 40) # 参加人数
x1 <- c(0, 4, 12, 8, 9, 7)     # キャンセル人数
x2 <- c(7, 19, 35, 30, 26, 52) # 申し込み人数

y <- c("20110505", "20110707", "20110811", "20110920", 
       "20111027", "20111220")
yDate <- as.Date(y, "%Y%m%d")


par(mar=c(5, 4, 5, 4))
ymax <- 50
plot(yDate, x, type="b", xlab="Month", ylab="Number", bty="l", 
     ylim=c(0, ymax), xaxs="i", yaxs="i", 
     xlim=c(min(yDate) - 20, max(yDate) + 20), las=1, 
     main="oshasta")
lines(yDate, x1, lty=2)
rect(yDate-5, 0, yDate+5, x1/x2*ymax, col="#00000022", border="grey")
axis(4, seq(0, 100, by=25), at=seq(0, 60, by=ymax*0.25))
mtext("Proportion", side=4, padj=3)
abline(h=0)
legend("topleft", c("Number of participants", "Number of cancels", 
                    "Proportion of cancels"), 
       lty=c(1, 2, 1), pch=c(1, 0, 15), col=c(1, 1, "#00000022"))


これからもおしゃスタを続けていきたいと思っておりますので、今後共宜しくお願い致します！！


↓Togetterです

メモ：大量データをプロットするときの濃淡プロット

データが多くなってくると散布図が真っ黒になってしまうので、濃淡を付けることでどこに集中しているかが分かります。マイクロアレイ系でよく使われる Bioconductorというプロジェクトのパッケージを使うので、通常のパッケージをインストール方法が違います。

  • インストール
source("http://www.bioconductor.org/biocLite.R")
biocLite("prada")
  • プログラム例
library(prada)

n <- 10000
x1  <- matrix(rnorm(n), ncol=2)
x2  <- matrix(rnorm(n, mean=3, sd=1.5), ncol=2)
x   <- rbind(x1,x2)

smoothScatter(x)

pairs(iris, panel = function(...) smoothScatter(..., add=T))


【追記】

@bob3bob3がコメントをして下さったので、そちらも試してみました。

n <- 10000
x1  <- matrix(rnorm(n), ncol=2)
x2  <- matrix(rnorm(n, mean=3, sd=1.5), ncol=2)
x   <- rbind(x1,x2)

plot(x, col="#0000FF22", pch=19)

library(IDPmisc)
iplot(x)

library(hexbin)
plot(hexbin(x))

3つの中ではplot(x, col="#0000FF22", pch=19)が手軽で良い感じ。

こちらのサイトには、Rを使った様々な可視化がまとまっているようです。

http://addictedtor.free.fr/graphiques/

データマイニングで使われるトップ10アルゴリズム

2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。

　必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。

データマイニングの基礎


1. C4.5

C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。

  • CARTは2分岐しかできないがC4.5は3分岐以上もできる
  • CARTはジニ係数を分割の指標にするがC4.5は情報ベースの基準を使っている
  • CARTは木の剪定をクロスバリデーションによって行うため時間がかかるがC4.5は二項信頼限界を使うため一方行でできる

C4.5は1997年に商用のSee5/C5.0に改善され、以下のような変更点がありました（詳細はこちら）。

  • ブースティングを組み込むことで精度が格段に上がった
  • スケーラビリティが向上しているのでマルチコアCPUで有用

2. k-meansアルゴリズム

k-meansアルゴリズムは言わずと知れたクラスタリングの方法ですね。こちらのブログがとても視覚的に分かりやすかったので紹介させて頂きます（画像を使わせて頂いております）。


この画像の例では、2次元に分布しているデータを5つのクラスターに分けています。手法としては、次の2ステップを反復して計算します。

　Step 1. データの割り振り（一番近い中心に割りつける）
　Step 2. 平均値の計算（クラスター毎の平均値を計算する）

実用的には、「いくつのクラスターに分類するか」というkを事前に決定する必要があります。データから最適なkを推定する方法もいくつか提案されています（GAP推定量など）。



3. サポートベクターマシン

サポートベクターマシン（SVM）は機械学習の分野で最も代表的な手法です。SVMを学んだ際のに感じる主な疑問は「SVMの結果を解釈できるか？」と「SVMを連続値の予測に応用できるか？」の2ではないでしょうか。個人的にはSVMの結果の解釈は難しいと感じています。ただ、数%の予測精度の改善で売上が数千万も変わるようなビジネスの現場では、「結果の可読性」よりも「予測精度」を求められることも多いと思います。この2つはトレードオフの関係にありますので。また、SVMは連続値に容易に応用できます。パッケージによっては、特に指定しなくても連続変数を認識してそのようにモデルを作るものもあるでしょう。

　SVMに関してもう1つ気になるのは、学習（パラメータの予測）にかかる時間です。特にデータが数万を超えると、顕著に計算時間が増大します。これに関しては、core-vector machineという手法が提案されており、とても早く計算できるようです。



4. アプリオリアルゴリズム

アソシエイションルールの分析によって、高頻度のトランザクションを見つける際に最も良く使われる手法です。「土曜はビールとおむつがペアで買われる」というアレですね。以前みかけた記事によると、これはどうやら都市伝説みたいです。どこかの店舗でたまたま発見されたルールがインパクトがあったので広まってしまったが、全体のデータで試したらそんなルールは出なかったとか（web上の記事で読みました）。「部分集団で発見されたルールが全体には適応できない」という現象は分析をしていると良くある話です。

　アプリオリアルゴリズムは強力な結果を得ることができる割に、実装は他の手法に比べて難しくありません。ですのでデータマイナーにとっては最初に実装することのできる手法でしょう。近年のアプリオリアルゴリズムの顕著な発展は、FP-growth（frequent pattern growth、頻出パターン成長）という手法です。以下のようにデータベースをスキャンすることでルールを作成できます。データベースを2回しかスキャンしないので、アプリオリアルゴリズムよりも格段に早い手法です。

　Step 1. データベースを、全ての重要な情報を持つFP-treeという構造に圧縮する
　Step 2. 圧縮されたデータベースを、高頻度セットに関連する条件付きデータベースに分割し、それぞれをマイニングする

　他にも様々なトピックがあり、(1)分類学の組み込み、(2)インクレメンタルマイニング、(3)アイテムの連続変数の利用、(4)頻度ではない指標の利用、(5)アイテムセットよりリッチな表現（ツリーやグラフによる表現）、(5)閉じたアイテムセットなどがあります。



5. EMアルゴリズム

様々なモデルでパラメータ推定する際に使われるアルゴリズムです。モデル式が複雑になると数式展開では解を求めることができないので、EMアルゴリズムのような数値計算による最適化によってパラメータを求めます。論文では混合分布のモデルが紹介されています（なのでEMアルゴリズムというより混合モデルが良く使われるということでしょう）。

　混合分布がいくつのクラスター（正規分布）から出来ているかを決める必要がありますが、この最適な数を推定する方法がいくつかあります。BICを利用したり、尤度比検定を行ったりします。BICを使った最適化を組み込んだものに、MFclust関数という手法があります（以前、この記事で紹介しました）。EMアルゴリズムの説明のときは、k-means法と混合分布の話が良く出てきます。未確認ですが、正規分布を仮定すると、k-means法は混合モデルに帰着するのかもしれません。



6. ページランク

ページランクは1998年にSergeyによって提案されたサーチランキングを付ける方法です。そのアルゴリズムを元にサーチエンジンを開発したGoogleは大成功を収めました。本質的には、ハイパーリンクを投票のように解釈しています。しかし単純に投票数だけを見ているのではなくて、投票元のページも分析し、重みを付けています。

　様々な改善方法が論文で提案されており、より進んだトピックはこの2冊の本に紹介されています。

Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data (Data-Centric Systems and Applications)

Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data (Data-Centric Systems and Applications)

Google’s PageRank and beyond: the science of search engine rankings.



7. アダブースト

1997年に提案された、アンサンブル学習と呼ばれる手法の1つです。いくつかの学習器を組み合わせることで、強力な予測性能を得ることができます。また実装も難しくありません（たった10行程度のコード）。

　多くの研究によればアダブーストは過学習しにくいことがわかっています。つまり、訓練データでエラーが0であっても、テストデータのエラーも減少できるという結果が出ています。どうしてこのような現象が起こるのか、ということについての研究もされています。Schapireらはこの論文でマージンを基にした説明を試みており、この説明が成功するとアダブーストとSVMの関連性が見つかることになります。

　現実に得られるデータは変数の次元がとても大きいことが多いです。このようなときは、次元縮約と変数選択（特徴選択）2つのアプローチがあります。次元縮約は数理的な意味づけはできますが、縮約後の変数は解釈をしにくいものになります（主成分分析など）。それに対して変数選択は解釈はしやすいものの、経験的に行われることが多いため数理的な基盤はありません。しかし、アダブーストは数理的な意味合いを持たせたまま、変数選択に利用できるのではないかという研究があります（論文）。画像の分野で主に研究されていますが、アダブーストを変数選択に応用することはとても重要なトピックでしょう（xboxのkinectによる認識技術も、アダブーストと類似のランダムフォレストで行われていると記憶しています）。



8. k-近傍分類

全ての訓練データを記憶してクラスタリングを行う、「まる暗記」型の分類器です。あるデータを、最も近いk個のデータの最多数のクラスに分類します。実装も理解するのも簡単ですが、訓練データを全て記録しておかなくてはならないのでコストが大きく、計算にも時間がかかります。

　分野によってはSVMのような高度な手法よりも性能が良いことがあります（遺伝子分野の論文）。進んだトピックとしては、精度を落とさないまま訓練データを減らす方法（condensing）、訓練データは減らすが精度が高くなる方法（editing）、近接グラフへの応用、ファジーアプローチなどがあります。



9. ナイーブベイズ

ナイーブベイズもクラスを予測するための手法です。構築するのが簡単で、パラメータ推定するために複雑な繰り返し計算が必要ありません。そのため大きなデータに対しても適用することができます。解釈もしやすく、性能もとても高いです。

　ナイーブベイズは簡潔であり、エレガントであり、ロバストであることから様々な分野で応用されています。最も古い手法であり、形も単純であるに関わらず、性能はとても高いです。テキスト分類やスパムフィルタリングで広く利用されています。また統計、データマイニング、機械学習、パターン認識の分野で様々な応用や改良がされています。ベイジアンネットワーク、boostedナイーブベイズのように進んだトピックもあります。



10. CART

1984年に出たこの本で提案されたCARTが、人工知能、機械学習、ノンパラメトリック統計学、データマイニングの分野でのマイルストーンになった。

Classification and Regression Trees (Wadsworth Statistics/Probability)

Classification and Regression Trees (Wadsworth Statistics/Probability)

　CART（Classification and Regression Trees、分類と回帰木）は2分岐の決定木によってクラス、連続値、生存時間を予測する手法です。決定木に関しては以前この記事で概要を書きました。欠測値もカテゴリとして扱うことで、欠測のあるデータをそのままアルゴリズムに突っ込むことができることも利点の一つです。



読み終わっての感想など

以上です。正直言ってC4.5が1番に紹介されているのが意外でした。ブースティングを組み込んだC5.0がそれだけ強力なのでしょうか。しかしそれだとランダムフォレストも同じくらい強力な気もしますが、どうなのでしょうか。何年か前のKDDのコンテストで優勝した人もアンサンブル学習を使っていたみたいですし、過去10年から今後10年くらいはアンサンブル学習が最も強力なのかもしれません。

　こうして改めて勉強してみると、自分がどこまで理解しているのか分かって良いですね。「k-means法と混合分布モデルの違いは？」「アダブーストとランダムフォレストの違いは？」「ナイーブベイズとベイジアンネットワークの違いは？」など、もうちょっと勉強しなきゃいけないかなと。

　今やRでどの手法も手軽に利用できますが、歴史を考えると感慨深いものがあります。むしろこんなに簡単にできちゃって良いのかと思うくらいです。これからは先人達の偉業を噛み締めながら利用することにしましょう。そして次の革新的な手法も提案していきたいところですね。

　あとは、回帰モデルや判別分析などのような、古典的な統計手法は入っていませんでしたね。これらの手法はモデルの可読性に重点を置いているので、機械学習のように性能を追求する分野ではあまり使わないのかもしれません。データを解釈するときには良いのですが、実際にシステムに組み込むときには性能不足なのでしょう。また決定木は、回帰モデルよりもさらに可読性が高いので、人気があるのかなと思います。


おまけ

gihyo.jpというサイトの機械学習に関する連載がとても良いです。私もこれから時間を見つけて読んでみようと思います。