知能情報工学
第3回
k最近傍法
2016年4月26日
吉川雅博
1
プロトタイプによるNN法の流れ
音声や画像
（アナログ信号）
AD変換
前処理部
特徴抽出部
・標本化
・量子化
・ノイズ除去
・正規化
識別が容易な
特徴を抽出
識別部
識別
結果
プロトタイプと比較
学習
識別辞書
（プロトタイプ）
2
AD変換
アナログ信号
一定区間で区切って
サンプルをとる
標本化（サンプリング）
サンプリング周波数
音楽CD 44.1kHz
音声認識 16kHz
データを何段階の
数値で表現するか
量子化
量子化ビット
音楽CD 16bit
(65536段階)
3
前処理部
音声・・スペクトルサブトラクションによるノイズ除去
画像・・平均値フィルタやメディアンフィルタによるノイズ除去
対象の特徴に合わせて適切に処理する必要がある
4
特徴抽出
特徴抽出は識別に役立つ情報を取り出す処理
音声認識：個人の声の性質や声の大きさ
文字認識：文字の大きさや色
識別には無意味
識別に必要な特徴のみを取り出す
5
特徴ベクトル
特徴抽出後は特徴を並べた𝑑次元のベクトルで表現
𝑥𝑑
𝒙 = (𝑥1 , 𝑥2 , … , 𝑥𝑑 )𝑡
𝑥𝑗
𝑥1
𝑥2
𝑥3
𝑑次元空間を特徴空間，𝒙を特徴ベクトルと呼ぶ
6
学習（プロトタイプの決定）
𝑐種類のクラスをそれぞれ𝜔1 , 𝜔2 , … , 𝜔𝑐 とし，
各クラスのプロトタイプを𝒑1 , 𝒑2 , … , 𝒑𝑐 とする
𝑥𝑑
𝒑1
𝒑𝑖
𝒑2
𝒑𝑐
𝑥1
𝑥𝑗
𝑥2
𝑥3
プロトタイプは学習データから決定する
7
プロトタイプによるNN法
各プロトタイプとの距離を計算し最も近いプロトタイプ𝒑𝑖 に決定する
→最近傍決定則，最近傍法（Nearest Neighbor法：NN法）
𝑥𝑑
𝒙
𝒑1
𝒑2
𝒑𝑖
𝒑𝑐
𝑥1
𝑥𝑗
𝑥2
𝑥3
8
NN法の定式化（1）
𝑐種類のクラスをそれぞれ𝜔1 , 𝜔2 , … , 𝜔𝑐 とする
クラスωi のプロトタイプ𝒑𝑖 を𝑑次元の特徴ベクトルで定義
𝒑𝑖 = 𝑝𝑖1 , 𝑝𝑖2 , … , 𝑝𝑖𝑑
𝑡
(𝑖 = 1, … , 𝑐)
未知データ𝒙を𝑑次元の特徴ベクトルで定義
𝒙 = 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑑
𝑡
𝒙と𝒑𝑖 との距離を以下のように計算（ユークリッド距離）
𝐷 𝒙, 𝒑𝑖 =
𝑥1 − 𝑝𝑖1
2
+ 𝑥2 − 𝑝𝑖2
2
+ ⋯ + 𝑥𝑑 − 𝑝𝑖𝑑
2
(𝑖 = 1, … , 𝑐)
9
NN法の定式化（2）
距離の最小値を以下のように定義
min 𝐷 𝒙, 𝒑𝑖
(i = 1, ⋯ , 𝑐)
距離が最小となるプロトタイプ（クラス）を求める数式は以下
arg min 𝐷 𝒙, 𝒑𝑖
(i = 1, ⋯ , 𝑐)
𝑖
距離𝐷を最小にする𝑖を返すという意味
10
NN法と識別境界
NN法は2点のプロトタイプを結ぶ直線の
垂直2等分線（識別境界）を求めるのと同じ
プロトタイプ
𝒑1
識別境界
𝒑2
プロトタイプ
11
演習3
クラス𝜔1 のプロトタイプが𝒑1 = (2, 8)，
クラス𝜔2 のプロトタイプが𝒑2 = (8, 4)の時，
NN法を用いて未知パターン𝒙 = (1, 6)を識別せよ．
また，識別境界の式を求めよ．
𝑥2
𝒑1 = (2, 8)
𝒙 = (1, 6)
※荒木雅弘「フリーソフトでつくる音声認識システム」より
𝒑2 = (8,4)
𝑥1
12
演習3-解答
𝐷 𝒙, 𝒑1 =
1−2
2
+ 6−8
2
= 5
𝐷 𝒙, 𝒑2 =
1−8
2
+ 6−4
2
= 53
したがって，𝒙はクラス𝜔1 に分類される
𝑥2
𝒑1 = (2, 8)
𝒙 = (1, 6)
𝒑2 = (8,4)
𝑥1
13
演習3-解答
識別境界は，直線𝒑1 𝒑2 の中点 5, 6 を通り，直交する直線
3𝑥1 − 2𝑥2 = 3
𝑥2
3𝑥1 − 2𝑥2 = 3
𝒑1 = (2, 8)
(5,6)
𝒙 = (1, 6)
𝒑2 = (8,4)
𝑥1
14
k最近傍法（k-NN法）（1）
プロトタイプによるNN法はプロトタイプを学習データから決める
→ パーセプトロンなどで学習が必要
各クラスのプロトタイプ
プロトタイプを決定する学習を行わないのもアリ
k最近傍法（k-NN法）
学習を行わずすべての学習データをプロトタイプとして扱う
15
k最近傍法（k-NN法）（2）
1-NN法
①すべての学習データとの距離を計算
②最も近い学習データのクラスに決定
k-NN法
①すべての学習データとの距離を計算
②最も近い学習データk個の中で多数決を行う
③投票数の多いクラスに決定
3-NNの場合
最も近い3個のうち
が2個， が1個 →
に決定
16
kの値による識別境界の変化
k=1
k = 30
17
演習4
以下の学習データを用いて，3-NN法により𝒙 = (3, 4)を識別せよ
𝑥2
5
𝒙
4
𝜔1
3
2
1
𝜔2
1
2
3
4
5
𝑥1
※荒木雅弘「フリーソフトでつくる音声認識システム」より
18
演習4-解答
最も近いのは(3, 3)，次に近いのは(2,3)と(4,3)
多数決を行うと𝜔1 が２つ，𝜔2 が１つのため𝜔1 が識別結果となる
𝑥2
5
𝒙
4
𝜔1
3
2
1
𝜔2
1
2
3
4
5
𝑥1
19
演習5
以下の学習データを用いて，3-NN法により𝒙 = (2.1, 3)を識別せよ
𝑥2
5
4
𝜔1
𝒙
3
2
1
𝜔2
1
2
3
4
5
𝑥1
※荒木雅弘「フリーソフトでつくる音声認識システム」より
20
演習5-解答
とても近い学習データ(2, 3)があるにも関わらず，𝜔2 に分類される
→ 距離を考慮した工夫が必要
𝑥2
5
4
𝜔1
𝒙
3
2
1
𝜔2
1
2
3
4
5
𝑥1
21
k-NNの長所・短所
長所
・学習が不要
・実装が簡単な割に高い識別率（ベンチマークとして利用）
短所
・すべての学習データとの距離計算が必要（処理時間長い）
・コンピュータに大きな記憶領域（メモリ）が必要
・kの値は実験的に求める必要性あり
22
K-NNのコード
function predictLabelVote = KNN_(testData,trainData,trainLabel,K)
fprintf('Process is running.\n');
trainData
= trainData';
trainLabel = trainLabel';
testData
= testData';
trainLabelNumber = length(trainLabel);
% 学習データラベルの総数
classType = unique(trainLabel);
% クラスの種類を抽出
testDataNumber = size(testData,2);
% テストデータのサンプル総数
predictLabel = zeros(testDataNumber,1);
% テストデータラベル作成
predictLabelVote = zeros(testDataNumber,1); % 同票決戦
distSum = ones(testDataNumber,length(classType)).*1000; % 同票決戦の集計用
for n = 1:testDataNumber
% 学習サンプルとテストサンプル間のユークリッド距離計算
distance = sum((trainData-testData(:,n)*ones(1,trainLabelNumber)).^2);
% ソートを行ない，ソート前のインデクスを保存
[sortDistance preIndex] = sort(distance);
% classTypeを横軸としたヒストグラムを作成する（K個のラベルで投票）
voteResult = hist(trainLabel(preIndex(1:K)),classType);
% 最も多く識別されたクラスに決定
[maxVote bestClass] = max(voteResult);
predictLabel(n) = classType(bestClass); % 同票決戦処理なしの結果
% 同票決戦の処理（距離の合計が小さい方に決定）
voteIndex = (voteResult==maxVote);
for m = 1:length(voteIndex)
if voteIndex(m)==1
q = trainLabel(preIndex(1:K))==m-1;
distSum(n,m) = sum(sortDistance(q));
end
end
[unused bestbestClass] = min(distSum(n,:));
predictLabelVote(n) = classType(bestbestClass); % 同票決戦後の結果
end
23
© Copyright 2024 ExpyDoc
