2012年12月からCodeIQで機械学習分野の問題を3題出題しました。

第1問から第3問で一連のストーリー（「金とキノコ」3部作）になっています。3問とも、機械学習の基礎的な知識と手元のPCで解けるようなやさしめの設定にしてあります。

第1問と第2問はクラス分類を使って、本物の金貨と本物のキノコを見分ける問題です。第3問は、異常（外れ値）検出で、選んではいけない玉を見つけ出す問題です。

今日は、第1問と第2問について、解説をします。

以下の解説ではRによるコード例を示していますが、いずれも数行のコードで解くことができます。

問題

週末に海賊船で催されたPRML読書会に参加したN君は、船内に山のように積まれた金銀財宝に目を奪われました。 近くにあった宝箱の1つを開けてみると、きらきらと輝くコインが何枚も入っていました。
手に取ってみるとどれもずっしりと重みがあります。金貨に違いありません。
好きなだけ持って帰ってよいと言われ、勉強会帰りに何枚か鞄に詰め込んで帰ることにしました。

家に帰ってから少し冷静になったN君は「気前よく配っていたけれど、この金貨は本物なのだろうか」と疑い始めました。
鞄には20枚の金貨が入っていましたが、友人のアルキメデスに計測してもらったところ、20枚とも体積も重さも異なりました。
ネットで検索してみたところ、金貨の体積と重さと真贋のデータを得られました。
このデータを参考に、貰ってきた金貨の真贋を見分けてください。

■貰ってきた20枚のコインのデータ  （CodeIQ_mycoins.zip）

■金貨の体積と重さと真贋のデータ  （CodeIQ_auth.zip）

■解答方法

それぞれのコインの真贋を、1行にコイン1枚ずつ、本物なら「1」、偽物なら「0」、どちらとも言えなければ「？」と記入したファイルをアップロードしてください。

1
0
1
?
1
0
…

のような20行のテキストファイルになります。
「貰ってきた20枚のコインのデータ」のファイルと同じ順番でお願いします。
（改行コードの差異は採点側で吸収しますので心配しないで下さい）

■ヒント

難易度★なので、答えが '1' か '0' になるようなコインしか入っていません！

■豆知識

本物の金貨には一定割合以上の金が含まれています（純粋な金は、流通を前提とした硬貨として使用するには柔らかすぎるため、通常は、銀や銅などの他の金属との合金が用いられます）。
ちなみに、金とほぼ同じ比重を持つタングステンで鋳造し金メッキを施したコインは、重さと体積だけでは識別できませんのでご注意ください！
本設問ではコインには金と同等、もしくは金より比重の大きい金属は混ざっていないものとします。

解説

与えられたデータ（コイン100枚分）を教師とする、クラス分類（教師あり学習）問題です。
教師あり学習（Supervised Learning）とは、分類済みのデータを訓練データとして用いることができる状況で、新たに与えられたデータに対し分類や回帰を行う手法です。

解法

データをプロットしてみておわかりかと思いますが、直線できれいに分類できそうなデータです。引っ掛け問題的な要素も特にありません。

【註】しかも、原点を通る直線が引けます。これは、重さを体積で割って比重を求めれば、しきい値の上か下かで分類できてしまうことを意味します。

フィッシャーの線形判別法、パーセプトロン、SVM（サポートベクタマシン）など色々な手法が使えますが、この後のコード例ではSVMを使っています。

SVM（サポートベクタマシン）とは

2クラスの訓練データの識別面を、データ点からの距離（マージン）が最大になるように求める線形識別手法です。現在知られている中では最高レベルの精度が得られる手法のひとつです。

カーネル関数を導入することで、線形分離が不可能な問題にも適用することができます。

最近では、SVMと同等以上の精度での識別が可能なRandom Forest法などの手法が知られています。

評価のポイント

貰ったコインは20枚のうち10枚が本物で、10枚が偽物です。

難易度★ということで（問題をやさしくするために）、100枚分の真贋のデータ（＝教師データ）をもとに本物と偽物を分離する境界線をどのように引いたとしても境界線に一番近い教師データよりも貰ったコインのほうが近いという事がないようなデータセットにしてあります。

ヒントにも書いたとおり、答えが '1' か '0' になるようなコインしか入っていません！特に引っ掛け問題的な要素はありません。

すべての真偽を正しく分類できれば評価5、10枚以下の正答は評価1としました。（プログラムコードの提出は不要です）

Rでのコード例

kernlabパッケージを用いますので、事前に

install.packages("kernlab")

しておいて下さい。

library(kernlab)

# ファイルからデータ読み込み
auth <- read.table("CodeIQ_auth.txt")
mycoins <- read.table("CodeIQ_mycoins.txt")

# auth を教師とする分類器をSVMで
svm <- ksvm(V3 ~., data=auth)

# 手持ちのコインのデータに分類器を適用
result <- predict(svm, mycoins)

# ファイルに出力
write.table(ifelse(result > 0.5, 1, 0), "answer.txt", quote=F, col.names=F, row.names=F)

解答

1
0
0
1
1
0
1
1
1
0
0
1
1
0
0
1
0
0
0
1

問題

海賊船で催されたPRML読書会は楽しかった。
機械学習の事も少しはわかった気がするし、金貨も沢山貰えた。偽金貨もずいぶん混ざっていたが。

本物とわかった金貨を何枚か貴金属店で売って小金ができた。
貴金属店の店主は海賊船での読書会の話もそこで金貨を貰った事も信じていないようだったが、
そのうち何枚かは百年前に北大西洋で沈没した豪華客船に積まれていた幻の金貨だそうで、店主もほくほくしていた。
これでカーネル多変量解析の本でも買おうかと思っていたN君に、海賊船の船長からメールが届いた。

「太平洋のある島にたどり着いた。島は家から道路から何もかも金でできている。」

もしかしてあの「ジパング」ですか？

「しかし、この島には誰も住んでおらず、あるものといえば金ばかりで食料が全くない。
　食用になりそうなのは道端に生えているキノコぐらいだ」

「この島のキノコは見たところ3種類あるようだ。そのうち2種類は毒キノコらしい。
　誤って食べた隊員が3日3晩笑い転げたり泣き叫んだりしている。
　3種類とも金色なので色では区別がつかない。」

とりあえず死人は出ていないらしい。

「採ってきたキノコと、隊員が食べたキノコのデータを送るから、
　食べても大丈夫なキノコを教えてほしい」

キノコの傘の大きさと柄の長さが記されたデータが送られてきた。
このデータをもとに採ってきたキノコをクラスタリングして、隊員が食べた毒キノコの含まれないグループのキノコを船長に教えてあげよう。

■採ってきたキノコと、隊員が食べたキノコのデータ

• CodeIQ_data.txt：採ってきたキノコ（96本）
  柄の長さ（cm）と傘の直径（cm）が半角スペース区切りで記入されている
• CodeIQ_eaten.txt：隊員が食べたキノコ（6本）
  柄の長さ（cm）と傘の直径（cm）と食べた隊員の安否（o/x）が半角スペース区切りで記入されている

■解答方法

• answer.txt：採ってきたキノコ（96本）
  解答は、テキストファイル「answer.txt」をアップロードしていただきます。
  「answer.txt」には食べていいキノコ（本数不明）のみについて、柄の長さ（cm）と傘の直径（cm）をCodeIQ_data.txtと同じ要領で、半角スペース区切りで記入してください。
  （ソート順や改行コードの差異は採点側で吸収しますので心配しないでください）

■注意

食用キノコと毒キノコの見分け方はその多くが迷信で、見た目の特徴で判断するのはほぼ不可能である。自然界には毒性の不明なキノコ、猛毒のキノコが多数存在する。キノコの拾い食いはやめよう。

解説

与えられたデータ点をクラスタに分類する、クラスタリング問題（教師なし学習）です。

教師なし学習（Unsupervised Learning）とは、分類済みのデータ（訓練データ）は前もって用意されておらず、与えられたデータだけからそのデータの構造や特徴を見出す手法です。クラスタ分類、主成分分析（PCA）などは教師なし学習の代表的な例です。

クラスタリング手法には、データを階層的に分類する階層型手法（Ward法など）と、特定のクラスタ数に分類する非階層的手法（K-means法など）があります。

解法

まずは、データをプロットして目で確認してみましょう。

［1］CodeIQ_data.txt：採ってきたキノコ（96本）

12.94 3.62
4.41 8.56
13.54 16.63
……

柄の長さを横軸に、傘の直径を縦軸にプロットしてみるとこんな感じです。

3つのクラスタがあるのがなんとなくわかりますね。

［2］CodeIQ_eaten.txt: 隊員が食べたキノコ（6本）

6.32 10.94 x
11.74 3.33 x
15.55 12.07 o
3.51 11.18 x
11.30 2.63 x
15.51 17.25 o

これもプロットしてみるとなんとなく3つのクラスタにわかれています。

先ほどのプロットに重ねてみましょう。

それぞれのクラスタに色をつけてみました。

2つのoが入っているクラスタが安全なクラスタです。

問題文からクラスタ数（＝キノコの種類）が3とわかっていますので、ここではK-means法で解いてみましょう。

K-means法（K平均法）とは

クラスタ数があらかじめわかっている場合に、

1. 各データ点にランダムにクラスタを割り振る
2. クラスタ毎に重心を求める
3. 各データ点を、重心が一番近くにあるクラスタに再分配
4. クラスタ移動がなくなるまで2〜3を繰り返し

のような処理をすることでクラスタを求める手法です。1.での割り振り方によって異なる結果に収束することがあります。

評価のポイント

特に引っ掛け問題的な要素はありません。

• 採ってきたキノコ（96本）を適切にクラスタリングする
• どのクラスタが食べても大丈夫なキノコのクラスタなのか、ヒント情報（隊員が食べた6本のキノコの情報）と照合して判別する

の2点ができていれば評価5としました。ちなみに食べても大丈夫なキノコは30本あります。

キノコの安全性は生死にかかわる問題であるためか、クラスタ境界をかなり小さめに（安全側に）取っている人もちらほらいらっしゃいました。毒キノコは選んでいないものの、安全なキノコの本数が少なめな場合は評価4。

生死にかかわる問題で基準を安全側に倒す判断は正当だと思います。今回は、隊員の食糧をできるだけ多く確保したいという思いから完全正答を30本としました。

クラスタ分類は概ね正しいものの、毒キノコが1本でも混ざっていれば評価3。

データが正しくない場合（問題データに存在しない柄の長さと傘の直径が含まれている、他の出題者の問題の解答が送られてきた、etc）は評価1とさせていただきました。

Rでのコード例

Rにはkmeans()というそのまんまの関数がビルトインであるのでこれを使いましょう。ライブラリパッケージのインストールは必要ありません。

# ファイルからデータ読み込み
eaten <- read.table("CodeIQ_eaten.txt")
data <- read.table("CodeIQ_data.txt")

# eatenからカラム3（o/x）を除外したものとdataを縦に結合
m <- rbind(eaten[1:6, -3], data)

k <- 3
km <- kmeans(m, k)

# 3番目と6番目のキノコは隊員が食べて大丈夫だったので、
# そのキノコが属するクラスタIDを安全クラスタとします。
# ここでは6番目を使っていますが3番目でも構いません。
safe_cluster_id <- km$cluster[6]

# 安全クラスタに属するものだけを抽出します
safe_cluster <- subset(m, km$cluster == safe_cluster_id)

# 大丈夫なキノコのうち、最初の2つは隊員が食べた物なので除外
answer <- safe_cluster[-c(1,2),]

# ファイルに出力
write.table(answer, "answer.txt", quote=F, col.names=F, row.names=F, sep=" ")

解答例

13.54 16.63
15.15 16.65
16.87 13.99
11.11 13.27
16.62 16.67
18.84 16.5
15.21 14.97
14.39 13.58
13.88 12.54
13.16 11.24
14.45 14.39
12.15 13.39
13.3 12.8
15.55 12.07
12.1 9.86
14.9 17.23
16.5 14.32
13.88 11.71
15.73 15.06
12.17 13.49
10.45 11.46
11.51 14.53
15.51 17.25
15.85 16.9
14.64 14.53
13.12 12.88
11.66 10.9
15.57 12.67
16.35 15.72
12.14 10.71

さいごに

機械学習を使って本物の金貨、本物のキノコは見分けられましたか？

後篇は100個の玉の中から貴重な石を一つだけ選び出す方法について解説する予定です。お楽しみに。