 |
|
| Chemometrix > ケモメトリックス > KNN法（k nearest neighbors） | |
 |
8. KNN法（k nearest neighbors） |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| KNNでは，既にカテゴリーに割り当てられているサンプルに対しての親近性に基づいて未知試料を分類します)。未知試料のクラス予測はk個の最も近いサンプルの属するクラスに依存します。投票と同じような感じで，それぞれのk個の一番近いトレーニングセットのサンプルが，そのクラスに投票します。そして，未知試料は，一番投票数が多いクラスに割り当てられます。この過程の重要な箇所は，kの適切な数を決める点です。 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1. 数学的背景 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
KNNで使用される多変量距離は，平面における２点間の距離と似ていますが，計算上では２次元ではなくN次元になります。このユークリッド距離( )の一般的な式は以下のようになります ［式 -３５］ ただし，aとbは，２つのサンプルのベクトルです。ベクトルには，それぞれのサンプルから得られたＮ個の説明変数の測定値が含まれます。 KNNのモデルを構築する際には，トレーニングセットの各サンプル間のユークリッド距離が，式−３５から計算され，距離のテーブルとして記憶されます。あるサンプルの場合，最も近い複数のクラスに，割り当てられてしまう場合があります。この場合，サンプルは多数が属するクラスに割り当てられます。もし，一番投票の多かったクラスが２つ（またはそれ以上）で同数の場合には，距離の合計に基づいて割り当てが決まります。つまり，投票の代わりに距離が合計されます。そして，未知サンプルは，一番距離の近いクラスに属します。 ここでは，事前のカテゴリーの割り当てとKNNアルゴリズムで推測された割り当てを区別するために，(測定された)m-クラスと(予測された)p-クラスの用語を使用します。モデルを構築する際には，m-クラスとp-クラスの一致点を探します。一致が多いことは，事前の割り当てが正当で，説明変数がサンプルの類似性を良く表現していることを意味します。一致しない場合，アウトライヤーが原因になっている可能性があります。サンプルのm-クラスへの割り当てが間違っているか，サンプルが無意味な説明変数の測定に影響されている等の原因が考えられます。不一致は，不適切なk値から生じる場合もあります。kの値の範囲は，１からトレーニングセットのサンプル総数より１少ない数です。しかし，kがトレーニングセットの大きさに近づくと，k番目に近いサンプルは，一番遠いサンプルになります。以下の単純な例は，KNNにおける重要な考えを説明しています。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
２. KNNの例 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
表−３は，図−３４で表示されているデータセットを示しています。このデータセットには５つのトレーニングセットサンプル（AらEまで)と１つの未知試料(?)が含まれています。また，それぞれのサンプルには３つの測定値（変数）があります。 表 -３ ５つのトレーニングセットと１つの未知試料のデータ
 図 -３４ 表−３のデータの三次元プロット 表−３のデータから，AとB，Dは，CやEよりもお互いに似ていることが明らかです。図−３４の三次元プロットでは，この関係をより明確に示しています。表−４には，サンプル間の距離のテーブルが示されています。テーブルは対角線で対称なため，半分の数値だけが示されています。 表 -４ 表−３のデータのサンプル間の距離
もし，一番近いサンプル（つまり，ｋ＝１）だけに投票するとすれば，トレーニングセットサンプルのすべてのp-クラスとm-クラスが一致します。k=2の投票結果は，常にk=1の投票結果と同じになります。つまり，一番近いサンプルのクラスが二番目に近いサンプルのクラスと異なった場合，テストサンプルのp-クラスは，投票されたサンプルへの実際の距離に基づい決定します。投票数が１対１の場合には，一番近いサンプルのクラスを選ぶことになります。 各サンプルに対して，近いサンプルに３票が投票された場合，ミスが２つ生じます。カテゴリー２に属すると思われるCとEは，３つの近いサンプルのうちの２つがカテゴリー１に属しているため、カテゴリー１がp-クラスになります。もし，近いサンプルに４票が投票された場合、同じように２つのミスが生じます。もし，トレーニングセットの誤分類を許容できないと決定した場合，kは２になります。 もし，未知試料のカテゴリーがk=2で予測されたら，?はカテゴリー２に割り当てられます。なぜなら，２つの近いトレーニングセットはCとEで， 両方ともカテゴリー２に属しているからです。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3. KNNのモデルを構築する |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 投票結果（Votes） 先のトレーニングセットにおいて，KNNを実行した結果を以下に示します。各値は，それぞれのk値における既知サンプルのp-クラスです。この投票結果はn行とkmax列を含む行列で，nはトレーニングセットサンプルの数になります。この行列の最初の列は，１票だけが投票された時の，各トレーニングセットサンプルのp-クラスになります。最後の列は，kmax (n-1)票が投票された時の，各サンプルのp-クラスです。図−３５は，図−３４で示されているトレーニングセットでの投票結果の例を示しています。k=2の時，サンプルCはカテゴリー２になりますが，k=3の時にはカテゴリー１になります。  図 -３５ 投票結果 トータルミス（Total Misses） 予め入力したクラス変数（m-クラス）とp-クラスを比較して，これらの情報を含むトータルミスを作成できます。トータルミスとは，各サンプルにおいてm-クラスとp-クラスが一致した場合は０，違う場合は１つとして，全サンプルの結果を合計した値です。トータルミスは，指定したｋの設定での分類ミスの総数を示します。これは，適切な投票数を決める際に重要です。例えば，表−３のトレーニングセットのトータルミスを，図−３６に示します。  図 -３６ 投票結果のトータルミス kの数が，トレーニングセットの一番小さいクラスに属するサンプル数よりも多くなるに従って，トータルミスは増加する傾向があります。その理由を理解するために，一番小さいm-クラスに属し，そのクラスの中で他のサンプルの近くに位置するテストサンプルを考えてみましょう。kがクラスのサンプル数より少ない時，テストサンプルは仲間であるm-クラスのメンバーから大部分の投票を受けます。しかし，投票数が多くなると，他のm-クラスに属する遠くのサンプルの投票が結果的に多くなり，テストサンプルの分類ミスが増加します。 分類ミス（Misclassification） 最初に作ったモデルを，そのまま未知試料の分類に使用するケースは，ほとんどありません。つまり，最適化を行わなければいけません。これには，ｋの値，つまり投票数を適切な数に決定する必要があります。また，カテゴリー毎のサンプル数が少ない場合は，トレーニングセットからアウトライアヤーを見つけて取り除く必要があります。更に，もしクラスが十分に分離していない場合，カテゴリーを区別しない変数を除去する場合もあります。 適切なｋの値を決めることと，アウトライヤーを識別する作業は，関係しています。もし，クラスが重なり合ったり，アウトライヤーが近くに存在する場合，ｋが小さすぎるとサンプルのp-クラスは大きく影響されます。もし，ｋが大きすぎると，サンプルのp-クラスは近くのサンプル数の多いクラスの方に向かって歪んでしまいます。 ｋの値を決定する前に，トレーニングセットのカテゴリー数と，それぞれのカテゴリーに含まれているサンプル数について知る必要があります。また，解決する問題の性質と関連して，全部でいくつの分類ミスまで許容できるかどうかを考えます。 ｋを決める一般的な方法には，さまざまなｋにおける分類ミスを調べることが含まれます。ミスが２つのクラスに集中しているかどうかを調べます。例えば，ミスのほとんどがクラス３と７にあるとします。もし，分類がクラス３のクラス７に予測し，クラス７がクラス３に予測したとすれば，これはクラスが重なり合っている証拠になります。モデル構築の段階で，クラスの重なりを発見すれば，後の予測でも，それらのクラスに疑いを持てます。 ミスが多数のクラスにまたがって分布していたり，同じサンプルが異なったｋによって異なって分類されている場合，これはアウトライヤーの挙動と一致しています。除去する前に，アウトライヤーの可能性のあるサンプルのm-クラスとp-クラスのサンプルを比較してください。多分，アウトライヤーはまちがったm-クラスをもち，トレーニングセットの別のクラスに属します。もし，アウトライヤーの数がクラスの大きさや最適なkの数と比べて小さい場合，その影響は無視できます。 備考：トレーニングセットのサンプルが非常に少ない時には，最適な投票数として１を選ばなければいけない場合があります。しかし，クラスがうまく分離していない場合や，アウトライヤーを含む場合には，間違った予測が導かれる可能性が大きいので，そのような低い値を極力さけるのが普通です。 モデルの構築は繰り返しの作業です。 KNNモデルの最適化が完了したら，そのモデル使用して予測を実行します。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4. KNNの表示手法としてのHCA |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| KNNとHCAは，密接に関連しています。どちらも２つのサンプル間の多変量距離を計算することから始められます。最短距離法で示されるHCAのデンドログラムは，ｋ＝１におけるKNNモデルのグラフ表示です。つまり，デンドログラムによって，ある特定のデータセットでKNNモデルを構築できるかどうかが分かります。 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5. KNNの予測結果 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| KNNのモデルの最適化が終了したら，それを使用して予測を行います。 未知試料の投票結果 未知試料のデータセットの各サンプルに対して予測されたクラスは，投票結果としてテーブルで表示できます。各サンプルは，それぞれ１つだけのp-クラスが割り当てられます。?マークのサンプルに対して予測されたカテゴリーを，図−３７に示します。  図 -３７ KNNでの未知試料の予測結果
|
 |
| Software |
 |
 |