CodeIQで出題した機械学習の問題は、「金貨の真贋を見分けよう」「食べられるキノコはどれだ？」と、今回ご紹介する「金塊か、キノコ料理か」で、全3部作の「金とキノコ」シリーズとなっています。

前篇の解説記事で扱った2つの問題はクラス分類をテーマにしていましたが、後篇は異常（外れ値）検出をテーマにした問題となっています。

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

問題

食糧になるものが金色のキノコしかない黄金の島で、われわれはN君が選んでくれた安全なキノコを齧りながら探索を続けていた。
見渡す限りの黄金だけでも十分な財宝だが、この島には他のお宝は何もないのだろうか。

金色のキノコが生い茂る道をしばらく行くと

　ザザザッ

風がざわめき、周囲で金色の影が動いた。
後ろから甘い香りが漂ってきた、と思ったら急激に意識が遠のいて行った。

　＊ ＊ ＊

気がつくとわれわれは手足を縛られ、島民と思われる者たちに包囲されていた。
島民たちはみな屈強という風でもないが、身に纏う金色の鎧が眩しい。

あの鎧はぜひともいただいて帰りたい。
とかそんな事を呑気に考えているうちにわれわれは島民たちに担がれ、全島民が集まる集会場のような場所に連れて行かれた。

　＊ ＊ ＊

島民は全部で百人ほどいるようだ。老若男女問わず金色の装束を身につけていて眩しい。

われわれの言葉がわかると思われる島民が1人、こちらにやってきて手足の縄を解きながら言った。

「われわれの島には、百年に一度、海を渡って大切な客人がやって来るという言い伝えがある。
　客人の機嫌を損ねると、島が沈んでしまうと伝えられている。」

それは手厚くもてなさないといけませんな・・・

「しかし、毎年一度は盗賊がやってくる。
　盗賊たちが言うには、珍しくもなんともない金色の物が目当てなのだそうだが。」

そうか、この島にいると金は存在が当たり前過ぎて空気並みの価値しかないのか・・・

「金色の物には特に価値があるわけではないから、
　盗賊だとわかった奴らにはこの金色の塊を持てるだけ持たせて追い払っている。」

それ金塊ですから！こんなのが流出したら金相場が暴落しますから！

「ただ、客人なのだとしたら、言い伝えに従って、機嫌を損ねないように手厚くもてなしたい。
　あそこに積んであるキノコをふんだんに使った料理で。
　どうだ？美味そうだろ。」

傘の大きさと柄の長さを見ただけで毒キノコかどうかだいたいわかるようになってきたわれわれの目には、それは毒キノコの山にしか見えなかった。

「そこで、きみたちが盗賊なのか客人なのかを調べ、適切な処遇をしたい。」
「調べ方はこの島の伝統に則った方法だ。」
「ここに100個の玉がある。
　この中に1つだけ貴重な石でできた玉がある。
　大切な客人ならば、それを選び出すことができるはずだ。
　大きさも重さも調べたいだけ調べてもらって構わない。」

単に毎年やってくる盗賊に100分の1の確率でキノコ料理を食わせているだけの話に聞こえなくもないが・・・

まあいい。状況を整理しよう。

• われわれは捕らわれの身である
• 島民たちはわれわれが盗賊なのか客人なのか知りたがっている
• 100個の玉の中に1つだけ入っている貴重な石でできた玉を選べば客人、他の玉を選べば盗賊とみなされる
• 客人とみなされれば毒キノコ料理を食わされ、3日3晩笑い転げ泣き転げる。命を落とさないとも限らない
• 盗賊とみなされれば金塊を持てるだけ持たされて島から追放される

ここは盗賊とみなしてもらって、金塊を持てるだけいただいてこの島を出るのが得策だろう。
あのキノコはもううんざりなので、確実に盗賊認定を受けたい。

「ちなみに、きみたちには全部同じ大きさの金色の玉にしか見えないだろうが、われわれは目で見て、触ってみるだけでその玉がどれなのかわかる。」
「きみたちには無理だろうから、手持ちの機材で計測するなり、知人に連絡するなり好きにしてもらって構わない。」

確かに全部同じ大きさの金色の玉にしか見えない。
外見上なにかの目印があるのかと思って調べてみたのだが、どれも傷ひとつないきれいな球形をしており区別がつかない。
・・・こうなるとN君が頼りだ。

　＊ ＊ ＊

というわけで、N君への今回の依頼はこれだ。

• 100個の玉のうち、貴重な石でできた玉がどれなのか教えてほしい。
• 判定が微妙なものがあれば、怪しい玉も含めて3つぐらい教えてほしい。

必ず盗賊認定されたいので、こちらは教えてくれた玉以外を選ぶことにする。

よろしく頼むよ。

■与えられるデータ

hundred.txt：100個の玉のデータ。1行につき玉1個分のデータが、重さ[g]、比熱[J/kg・K]、光の反射率[％] の順にスペース区切りで記してあります。（玉はすべて半径1.0cmの球体です）

データはこちらよりダウンロードしてください。zipファイルを解凍すると「hundred.txt」があります。

■解答方法

answer.txt：解答は、テキストファイル「answer.txt」をアップロードしていただきます。
他の玉とは性質が違いそうな玉をいくつか選んで（※3つ以内）、100個の玉のデータと同じ形式で記入したファイル「answer.txt」を作成してください。
（ソート順や改行コードの差異は採点側で吸収しますので心配しないでください）

■評価基準

• 貴重な石でできた玉が3つの中にあれば評価5とします。
• 自信がない場合、解答の玉の個数を増やしても構いません。（5個までなら評価4、10個までなら評価3とします）

■ヒント

貴重な石でできた玉以外の99個も、すべてが同じ素材でできているわけではなさそうです。
微妙な差なので「目で見て、触ってみるだけで」わかるにはおそらく修練が必要でしょう。
異常（外れ値）の検出については
http://research.preferred.jp/2013/01/outlier/
の記事が参考になると思いますので、ぜひご覧ください。

■補足

光の反射率は光の波長によって異なり、その特性から物体がどんな色に見えるかが推測できます。
この問題では単に「反射率」としていますが、500nm前後での計測とお考えいただければと思います。
http://en.wikipedia.org/wiki/Reflectivity

解説

与えられたデータ集合の中から、異常（外れ値）を検出する問題です。
外れ値検出は、ノイズや異常動作、故障の予兆などの検知に用いられるほか、未知の事象を発見したりするのにも有用です。
外れ値検出の主な手法としては、One-class Support Vector Machine（OC-SVM）やLocal Outlier Factor（LOF）があります。
設問中のヒントでも紹介しましたPFIの記事http://research.preferred.jp/2013/01/outlier/が良いまとめになっていますので、ぜひご覧ください。

解法

データを3次元プロットしてみるとこんな感じです。

大雑把に2つのクラスタが存在します。これは、金の純度などが微妙に異なった2つの素材を想定しています。「貴重な石」の素性は不明ですが、2つのクラスタのどちらにも属さないと思われます。どちらのクラスタにも属していなさそうな度合いの一番高いものを選んでいただければ正解に至ることができます。

上述のPFIの記事にも出てくるLOF（Local Outlier Factor）というアルゴリズムを用いると、この問題のように密度の異なる多峰性があるデータ分布における外れ値検知を簡単に行うことができます。

LOF（Local Outlier Factor）とは

• それぞれのデータ点について、その点からk番目に近い点までの距離を求め、その点のスコアとする
• 異常値は近傍にデータ点が少ないため、スコアが大きくなる

こうして得られたスコアが基準値を超えるものを検出する手法です。

本設問では特に基準値を設けることはできないので、スコア上位の物をいくつか選ぶことにしましょう。上の図でいうと#87がスコア最大になります。

【註】3要素の分布がそれぞれ異なるのであらかじめ正規化するのが望ましいですがそのまま突っ込んでも結果が変わらないようなデータにしてあります。

評価のポイント

この問題では、データの単峰性を前提とした手法では見逃しやすそうな場所に配置してあります。正解にたどり着くには、玉の分布の特徴を踏まえた手法を用いる必要があります。

引っ掛け問題的な要素ではありますが、最初にデータをプロットして目視してみることで回避できる程度の罠ですね。

• 1〜3個の玉のデータを提出し、その中に貴重な石でできた玉があれば評価5
• 4〜5個の玉のデータを提出し、その中に貴重な石でできた玉があれば評価4
• 6〜10個の玉のデータを提出し、その中に貴重な石でできた玉があれば評価3
• 提出されたデータの中に貴重な石でできた玉がなければ評価2
• 解答形式に誤りがある場合（11個以上の玉が解答に含まれる場合など）は評価1

としています。

Rでのコード例

RではLOFがパッケージDMwRで実装されているので、これを利用すると数行で求めることができます。事前に

install.packages("DMwR")

しておいて下さい。

library(DMwR)

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

# LOFスコアを計算。
# ここでは k=3 としていますが、
# 本設問ではk=2〜10ぐらいの範囲なら同じ玉がトップに来るようなデータになっています。
# （k=1だと警告メッセージが出ます）
outlier.scores <- lofactor(hundred, k=3)

# スコア上位3件を抽出
outliers <- order(outlier.scores, decreasing=T)[1:3]
write.table(hundred[outliers,], "answer.txt", quote=F, col.names=F, row.names=F, sep=" ")

解答例

（ソート順や改行コードは問いません）

84.406 129.347 50.527
76.911 127.382 51.565
89.907 131.723 52.932

84.406 129.347 50.527の行が含まれていれば正解とします。

おわりに

「金とキノコ」3部作、いかがでしたでしょうか。やさしすぎると思われた方もいらしたかもしれません。

機械学習について興味をもたれた方は、@echizen_tmさんの「これから始める人のための機械学習の教科書まとめ」が非常によくまとまっていますので手始めに一読されることをお勧めします。http://d.hatena.ne.jp/echizen_tm/20110209/1297272686

さらに理解を深めたい方には、機械学習のバイブルとも称されるC.M.ビショップ著「パターン認識と機械学習（PRML）」がお勧めです。Random Forest法やDeep Learningのような最近話題の手法には触れられていませんが、機械学習分野について網羅的に深く学習するのに適しています。独学するには数式や論理の展開が難解な部分もありますので、各地で催されている輪読会に参加してみることをお勧めします。

参考：C.M.ビショップ「パターン認識と機械学習(PRML)」読書会

今後もCodeIQで問題を出していくので、ぜひチャレンジしてみてください！

https://codeIQ.jp/ace/naoyat/