機械学習_k近傍法_理論編

データ分析

#機械学習

yoshim

2017.12.18

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

概要

　こんにちは、データインテグレーション部のyoshimです。
　この記事は機械学習アドベントカレンダー１８日目のものとなります。
　今回は「k近傍法(k-NN)」という手法を説明してみようと思います。

1.k-NNとは

　ざっくり言うと、「回帰や分類を行う際に、似たようなデータをk個集めてそれらの多数決から目的とする値を求める」という手法です。もし「回帰」に使うのなら、似たk個のデータのそれぞれの値の平均値や中央値、もしくは重み付けした集計値を予測結果に用います。また、もし「クラス分類」に使うのなら、似たk個のデータそれぞれの「クラス」でもっとも数が多いクラスにデータを分類します。（多数決の原理です）

こちらはk-NNのイメージです。緑色の円が新しくクラス分類をしたいデータとした時、最も似ているデータ３つ（k=3）のクラスから予測する、となると赤い三角と同じクラスに分類されることになります。また、もし最も似ているデータ5つ（k=5）のクラスから予測する、となると青い四角形のクラスに分類されることになります。

　かつては、アイテムのレコメンドシステムにも使われていたそうです。
（ユーザAがまだ評価していないアイテムに対して、ユーザAに似たユーザの評価からユーザAの評価値を予測する等）
せっかくなので、今回のエントリでは「アイテムのレコメンドシステム」を例にして「k-NN」についてご紹介しようと思います。

2.処理の流れ（概要）

　処理の流れをざっくり見ていきます。ここでは、「映画をレコメンドするサービス」において、「ユーザAがまだ見ていない映画Xに対するユーザAの評価」を予想するシステムを例に説明しようと思います。
（ユーザAに似たユーザをk人集めて、彼らの映画Xに対する評価値の平均からユーザAの評価値を予測する）

　また、あらかじめ全ユーザから「ジャンルごとの好み度合い」について「シリアス映画」、「アクション映画」、「SF映画」の３ジャンルについて1~5の値で聞いていたとします。
また、各ユーザの映画Xに対する評価値も1~5の範囲で保持しているとします。

1.ユーザの情報をベクトル化する。

　ユーザ間の類似度を計算するために、行列形式でデータを保持します。イメージとしては、下記のような形です。
(下記ではユーザDまでのデータしか表示しておりませんが、実際はもっとたくさんのデータがあると仮定してください)
(ユーザA以外は、「映画Xに対する評価」があるユーザのみを対象とします)

ユーザ	シリアス映画	アクション映画	SF映画	映画Xに対する評価
A	2	4	3
B	1	1	5	5
C	4	3	4	4
D	5	5	1	3

2.ユーザAに似ているユーザをk人抽出する

類似度（距離）に関する何らかの指標に基づいて、ユーザAと似ているユーザをk人抽出します。
(この指標については後ほどご説明します。)
今回はk=3として、ユーザAに似ているユーザを3人抽出した結果、ユーザB、C、Dが抽出されたとします。

3.抽出されたユーザの評価値から、ユーザAの評価値を予測

ユーザB、C、Dの映画Xに対する評価値の「平均」や「中央値」等を用いて、ユーザAの映画Xに対する評価値を予測します。例えば、ユーザB、C、Dの映画Xに対する評価値の平均を使ってみると、計算結果は4となりました。
[latex] \frac{(5 + 4 + 3)}{3} = 4 [/latex]

以上から、ユーザAの映画Xに対する評価値は4だと予測されます。

「ユーザAがまだ見ていない映画Xに対するユーザAの評価」を予想するk-NNにおける処理の流れは、大まかにこのような流れになります。大枠としてはこのような流れなのですが、実際にこのアルゴリズムを使おうとするともう少し考慮しなければいけない点があります。なので、続いて「考慮すべき点」について説明いたします。

3.考慮すべき点

ここでは、実際にk-NNを利用するにあたって考慮すべき点について、「2.処理の流れ（概要）」に沿ってご説明します。

1.ユーザの情報をベクトル化する。

ここで考慮しておきたい点は「欠損値への対応」と「ユーザのバイアス」の2つです。

「欠損値への対応」とは、利用したい値（今回の場合は、「ジャンルごとの好み度合い」）が欠損していた場合どうするか、というものです。対応方法としては、「そのユーザのデータは分析に利用しない」、「何らかの値から補完する（その他のジャンル好み度合いの平均値を利用する等）」といった手法が取れます。

「ユーザのバイアス」とは、具体的にいうと、ユーザによって「好み度合い」や「映画の評価値」を高くつけたり低くつけたりする傾向があるはずなので、それらを平準化しようということです。平準化の方法としては、各値を「ユーザごとに正規化」する手法が一般的でしょう。
例えば、どんな映画に対しても高評価なAさん、どんな映画に対しても低評価なBさんが映画δに対して高評価をつけていますが、この評価値は同等として扱ってはいけないはずです。

ユーザ	映画αへの評価	映画βへの評価	映画γへの評価	映画δへの評価
A	5	4	5	5
B	1	1	2	5

なので、「正規化」という処理を施すことで、Aさん、Bさんの各映画に対する評価値を平準化します。

ユーザ	映画αへの評価	映画βへの評価	映画γへの評価	映画δへの評価
A	-1.5	0.5	0.5	0.5
B	-0.66	-0.66	-0.13	1.45

正規化処理を施すことで、映画δに対するAさん、Bさんの評価値に３倍ほどの差が生じていることが確認できます。

2.ユーザAに似ているユーザをk人抽出する

ここで考慮しておきたい点は「類似度の評価指標」、「リジェクト」、「kをどのような値に指定するべきか」の3つです。

「類似度の評価指標」とは、具体的にいうと、各ユーザがどれだけ似ているか、ってどうやって計算するのかということです。色々な類似度の計算方法があり、分析するデータの内容によってどの計算方法を用いるかを検討することが望ましいです。
（「ユークリッド距離」を用いるのが一般的のようですね...。）
各類似度の計算方法についてはこちらがとても綺麗に整理してくださっているので、気になる方はご参照ください。

「リジェクト」とは、どういった場合は予測をしないかという考え方です。例えば、クラス分類をするにあたって、kを6に設定したとします。この時、類似度をもとに抽出した6個のデータの投票結果がタイになってしまったとした場合（クラスα=3,クラスβ=3）は予測結果を出力しない、といった設定もできます。他にも、類似度に対して閾値を指定し、「類似度がα以上でないと、集計対象としない」といったような対応を取ることもできます。

「kをどのような値に指定するべきか」については、こんなもの分析してみないとわからないので、何パターンかkを指定して精度を確認してみるといった手法を取るのが一番です。「経験的にはデータサイズの平方根を指定すると良い」といった説明がなされる文献もありますが、これはあくまでも指標の1つとして捉えた方が良さそうです。

4.k-NNの特徴と補足説明

k-NNの処理の流れについてのご説明は以上です。ここまでご紹介した内容を復習するとともに上記までで説明できていない点について簡単にまとめます。

1.k-NNはアルゴリズムがとても単純

k-NNの一番の強みはここでしょう。アルゴリズムが単純だと、分析結果と内容を周囲の人間に理解してもらいやすいという素晴らしいメリットがあります。

2.類似度が大きいデータに対する重み付け

k-NNでは、「最も近いk個のデータ」から投入したデータの予測を行いますが、このk個のデータはそれぞれ同等に扱っていいのでしょうか。より類似度が大きいデータによる影響をより強くした方が、より良い分析結果がもたらされるのではないかと考える人も多いはずです。この、より似ているデータからの影響をより強くするという考え方は「変形k近傍法(modified k-NN)」というアルゴリズムに発展します。
（順位や類似度によって重み付けを行うことで、重み付けを考慮しないk-NNよりも「ノイズに強く」なり、性能も向上します）

また、k-NNでクラス分類をする際は選んだk個のデータのうち最も多数派のクラスに分類されることになるのですが、「特定のクラスのデータがとっても多い時には、そのクラスに分類されやすくなってしまいます。このような事象に対応するためにも、類似度による重み付けは有効です。

3.次元が大きいデータに対しては向かない

k-NNではデータ間の類似度を測る必要があるのですが、この時「次元」が大きくなりすぎるとデータ間の距離を測定する際に「どのデータとの距離も大きく、同じようなものになってしまう」という問題があります。これは「次元の呪い」という事象が原因です。

なので、もしk-NNを利用するのなら、「次元削減しても情報量があまり欠損しない」もしくは「次元数が少ないデータ」に対して行うこととなります。現実的には、「次元数が少ないデータ」に対して利用するケースが多いのではないでしょうか。

4.k-NNで人間が設定すべき指標は？

「k」,「類似度の基準」の2つです。

5.予測する際に処理が重い

その他のアルゴリズムでは、モデル作成には時間がかかるがモデルさえできてしまえば予測は比較的早く処理できるものが多い一方、k-NNは予測フェーズにおいても時間がかかることが欠点です。これは、新しいデータを入れて予測する際に毎回全データとの距離計算が行われるためです。

せっかくなので、計算量を軽減するための対策について4点ほど簡単に記述いたします。
k-NNはその計算量を軽減するための「探索手法」についての研究が盛んな点も特徴です。

・誤り削除型k-NN
モデル作成後、誤分類されているデータを削除したデータセットを使うk-NN。一度誤分類したデータを削除した後に更にそのデータを利用してモデル作成をする、といった繰り返しの手順も可能。

・圧縮型k-NN
識別に寄与しないデータを削除しておく手法。例えば、クラス分類をする際は、「識別超平面」付近にあるデータがあれば分類はできるので、各クラスの中心付近に存在するデータは不要とみなして削除しておく。

・分岐限定法
データを階層構造（決定木分析をイメージしてください）にして、上層のノードには下層ノードの位置情報（中心、中心から最も離れた点、等）を保持しておく。そして、新しいデータを投入する際は上層ノードに対して計算を仕掛けることで、下層ノード全てに対して計算する必要がなくなる。

・近似最近傍探索
距離について「近似解」をあらかじめ設定し、最低限その「近似解」よりは距離が近い点で計算する、と割り切ることで計算量を減らす手法。クラス分類をする場合、あらかじめ各クラスごとの「領域」を設定しておき、新しいデータが入ったら、「いずれかのクラスに所属させ」、「近いクラスのデータとの距離を計算」、「異なるクラスとの距離が最初に定めた値より大きくなったら計算を終了する」といったもの。