データ解析第十回「k-近傍法」鈴木　大慈理学部情報科学科西八号館W707号室s-taiji@is.titech.ac.jp
7/7は休講
。k-近傍法による密度推定。k-近傍法による判別● k-近傍法による確率密度推定● k-近傍法の推定手法● kの選択。理論● k-近傍法による判別●実データでの実験
ノンパラメトリック密度推定法の一種カーネル密度推定と類似
。（長所）計算が簡単、k-近傍への距離を計算すればよい. (長所) o漸近的な性質が理論的に導出可能o (長門) (短所) o分布に対する仮定が少ない．滑らかさくらい．推定した密度が積分して１になるとは限らない. (短所) o推定した密度関数は不連続になりえる. o （短所）ノイズに弱い. （短所）推定された分布は裾が重い. o ● k-近傍法による確率密度推定● k-近傍法の推定手法● kの選択。理論● k-近傍法による判別●実データでの実験
{X;}}=1:データ(d次元とする) k-近傍密度推定量(k-nearest neighbor) ● k ≥ 1を一つ固定. ●点xに一番近いk個のサンプル点{X(1), X(2), . . . , X(k)}を持ってくる. (距離が近い順に並んでいるとする．X(k)が一番遠い） ●密度を次のように推定:
ただし，V đはd次元超球({x ∈ R đ | ||×|| ≤ 1})の体積.  V đ = π(α /2+1) xのまわりに多くのサンプルがあればβ(x)は大きく，逆に少なければβ(x)は小さい.
8/39
o k = 10でのk-近傍o

10/39
一方，Ｒが十分小さければ，
特に，Ｒとして‖× − X(k)‖としたものがk-近傍法である．V』を単位球の体積とすると,
なので，密度推定量を得る.
11 / 30

n = 100
n = 1000 k = 10
n = 10000 k = 50 k = 500サンプルサイズが大きくなるにつれ，kも大きくしたほうがよい. ● k-近傍法による確率密度推定● k-近傍法の推定手法● kの選択。理論● k-近傍法による判別●実データでの実験
カーネル密度推定のカーネルと同様に，kは適切に選ぶ必要がある．クロスバリデーションを使えばよい. ● k-近傍法による確率密度推定● k-近傍法の推定手法● kの選択。理論● k-近傍法による判別●実データでの実験k ≥ 1に対する，k-近傍密度推定量を
とする. ●推定量βの点xにおける平均二乗誤差(Mean Squared Error) : MSE( ρ ( x ), k ) := E[( ρ ( x ) − ρ ( x ))²].ただし，期待値E[.]はサンプル{X;} f=1の出方についてとる. Q: kに対して平均二乗誤差はどのように振る舞うか？
n → ∞に伴い，k → ∞とする．その時，
証明は省略.例えばBiau et al. (2011)を参照.これより最適なｋは
18 / 39
カーネル密度推定と同様にMSE( ρ ( x ), k * ) = 0 ( n − σ = )は，dが大きくなると収束レートが遅くなる． 「次元の呪い」はノンパラメトリック推定において必ず現れる. ● k-近傍法による確率密度推定。k-近傍法の推定手法o kの選択。理論● k-近傍法による判別●実データでの実験
●密度推定はそこまで安定していない. ●カーネル密度推定を用いたほうが良さそう. ● k-近傍法は，むしろ判別でよく用いられている. 。機械学習などで用いられる最も初等的な判別器の一つ. 。へたに凝った方法を用いるより精度が出たりする.
サンプル: {(X;, Y;)};=1 ∈ R d × {1, . . . , Q}ただし，Y; ∈ {1,2,...,Q}. つまりQ個のカテゴリへの分類.やりたいこと：サンプルから新しい点xをQ個のカテゴリへ判別したい. （例：手書き文字認識） n1, n2, . . . , no:カテゴリqのサンプルの数とする(∑ g=1 nq = n). ●点xに最も近いk個のサンプルを取ってくる.それを{(X(1), Y(1), (X(2), Y(2), . . . , (X(k), Y(k))}とする. ●このｋ個の内，最も数が多かったカテゴリヘｘを判別: k。をｋ個のサンプルのうち，カテゴリqであるものの数として(∑ g=1 kg = k), q(x) = argmaxq=1,...,Qkq.直観：近くに沢山あるカテゴリがもっとも確からしいだろう.点xがカテゴリqである確率をP(q|x)とする．ベイズの定理より，
である。ただし, ● ρ(x|q)はカテゴリqに属するサンプルの確率密度関数. ● ρ(x)はxの周辺確率密度関数. ● P(q)はカテゴリqが出る確率. ● ρ(x)はk-近傍法で推定可能.
¤ ρ(x|q)もk-近傍法で推定可能：
(半径||X(k) − ×||の球にkg個入っている).以上をベイズの定理に代入すると,
を得る。これの最大値がq(x)である.
24 / 39

判別誤差を最小にするｋ選びたい. J-foldクロスバリデーション●サンプルをＪ個に等分割する. ● Ｊ分割のj番目のグループをI ;とおく: {(Xi, Yi)}iez; (i = 1, . . . , J). ●  Îù : R d → {1,2,..., Q}をj番目のグループIjを除いて推定された判別器とする. ●判別誤差の推定量E(k)を計算: ê(k) = ∑( µ ∑ ¹[ fç )(x;) ≠ Y;] | ● Ê(k)を最小にするkを採用.
d次元データを用いる場合，座標ごとのスケールが大きく違う場合，推定結果が悪くなる場合がある.講義で紹介したk-近傍法は等方的にユークリッドノルムによる球を用いているためである.解決法。座標ごとの分散を揃える(座標ごと正規化する): X; ; ← X; ;/std(X; ; ). 。座標ごとに幅が異なる楕円や長方形を使う．その際，Vg‖× − X(k)‖ 6の代わりに楕円や長方形の体積を用いる. ● k-近傍法による確率密度推定。k-近傍法の推定手法o kの選択。理論● k-近傍法による判別●実データでの実験
k-近傍密度推定方のパッケージは見つからなかった．スクリプトに関数を定義してある. o knn(train, test, cl, k = 1, l = 0, prob = FALSE, use.all = TRUE): FNNパッケージに入っている. 。 |やuse.allはタイを処理するための引数, 。同バッケージに入っているknn.distなどを用いればKD木（等）を用いたk-近傍の高速計算が可能.鶏kknn:  kknnパッケージに入っている．重み付きk-近傍法が使える．
k = 30を採用。不安定. price
k = 30を採用。不安定. price
k = 30を採用。不安定.
1K, 1DK, 1LDKとそれ以外（2LDKなど）とを判別．k = 10.赤が部屋数１で,青がそれ以上. MNIST手書き文字データ: ● 28 × 28のグレースケール画像. 。6000個の訓練サンプル, 10000個のテストサンプル. | S 4 3 7 5 5 3 5 5 9 0 6 3 5ユ0の※講義情報ベージからcsvファイルを入手可能.輝度値は0から255の整数値. k = 10で96.65%の正答率. > res = knn(data.train_origin[,1:dimx], data.test[,1:dimx], data.train_origin[,dimy], k = 10, prob=FALSE) > (clerr = mean(res!=data.test[,dimy])) #0.0335, 96.65%の確率で正解. [1] 0.0335 > table(res,data.test[,dimy])
k-近傍法によるデータ解析●密度推定●判別kの選択は重要であった.
1自分の興味のあるデータで講義第八回に紹介した検定手法を当てはめてみよ.もしデータが見つからなければ「autopoll.csv」で分散分析を行ってみよ. 2講義第七回に説明した主成分分析を実装せよ.具体的には，データｘを受け取って第k番目までの主成分スコア，対応する主成分負荷(入;)および主成分のリストを返す関数を作成せよ. ● Yk: k番目までの主成分スコア。 Lk: k番目までの主成分負荷(入1, . . . , λ k ) 。 Vk: k番目までの主成分ベクトルを並べた行列3 上で得た自作の関数とRの組み込み関数princompの返り値とを比較せよ. 4  「ken-c-kakou.csv」にあるデータを用いて主成分分析を行え（データは講義七回目のzipファイルに入っている）。なお，このデータは総務省統計局「統計でみる都道府県のすがた．経済基盤」から抜粋した： http://www.stat.go.jp/data/k-sugata/index.htm http://www.e-stat.go.jp/SG1/estat/List.do?bid=00001052235&cycode=0データの読み込みはx <- read.csv("ken-c-kakou.csv",header=TRUE)で可能. 5 (optional)自分が興味のあるデータで主成分分析を行え.
●私宛にメールにて提出. ●件名に必ず「データ解析第n回レポート」と明記し，Rのソースコードと結果をまとめたレポートを送付のこと. ●氏名と学籍番号も忘れず明記すること. 。レポートは本文に載せても良いが，pdfなどの電子ファイルにレポートを出力して添付ファイルとして送付することが望ましい(これを期にtexの使い方を覚えることを推奨します). ●出力結果をただ提示するだけでなく，必ず考察を入れること. ●提出期限は講義最終回まで. ※相談はしても良いですが，コピペは厳禁です.講義情報ページhttp://www.ocw.titech.ac.jp/index.php?module=General& action=T0300&GakubuCD=100&GakkaCD=15&KougiCD=5522& Nendo=2015&Gakki=1&lang=JA&vid=03 http://www.is.titech.ac.jp/~s-taiji/lecture/2015/dataanalysis/ dataanalysis.html G. Biau, F. Chazal, D. Cohen-Steiner, L. Devroye, and C. Rodríguez. A weighted k-nearest neighbor density estimate for geometric inference. Electron. J. Statist. , 5:204–237, 2011. doi: 10.1214/11-EJS606. URL http://dx.doi.org/10.1214/11-EJS606.