知能情報工学 第11回 クラスタリング 2016年6月28日 吉川雅博

クラスタリング 教師のない学習データを自動的に分類 （教師なし学習） クラスタ1 クラスタ2 クラスタ3 まとまりがありそうなデータ クラスは不明

k-means クラスタリング 学習データを 𝒙 𝑖 (𝑖=1, …, 𝑁)とする ①クラスタの数𝐾を決める ②ランダムにクラスタ中心 𝒄 𝑗 (𝑗=1,…,𝐾)を設定する ③各学習データとクラスタ中心との距離 𝒙 𝑖 − 𝒄 𝑗 を計算し， 　最も近くのクラスタに学習データを割り当てる ④各クラスタについて以下の式で中心の位置を更新する 𝒄 𝑗 = 1 𝑁 𝑗 𝑖=1 𝑁 𝑗 𝒙 𝑖 𝑁 𝑗 は𝑗番目のクラスタの 学習データ数 ⑤クラスタ中心が変化しなくなるまで，②-④を繰り返す

ランダムにクラスタ中心 𝒄 𝑗 (𝑗=1,…,𝐾)を設定する（この例では𝐾=5） ※「てっく煮ブログ」のオンラインデモより

各学習データとクラスタ中心との距離 𝒙 𝑖 − 𝒄 𝑗 を計算し， 最も近くのクラスタに学習データを割り当てる

各クラスタについて中心の位置を更新する 𝒄 𝑗 = 1 𝑁 𝑗 𝑖=1 𝑁 𝑗 𝒙 𝑖 更新前 更新後

各学習データとクラスタ中心との距離 𝒙 𝑖 − 𝒄 𝑗 を計算し， 最も近くのクラスタに学習データを割り当てる 再割当て前 再割当て後

クラスタ中心が変化しなくなるまで繰り返すとクラスタが完成！

演習14 学習データ，𝑆={2, 4, 6, 10, 12, 14}をk-meansクラスタリングを用いて ２つのクラスに識別せよ． ただし，初期クラスタは， 𝑆 1 = 2, 4, 10 , 𝑆 2 ={6, 12, 14}とする． 2 4 6 10 12 14

演習14-解答 𝑆 1 = 2, 4, 10 , 𝑆 2 ={6, 12, 14} 2 4 6 10 12 14 各クラスタの中心を計算する 𝑆 1 = 2, 4, 10 , 𝑆 2 ={6, 12, 14} 2 4 6 10 12 14 各クラスタの中心を計算する 𝑐 1 = 2+4+10 3 = 16 3 =5 1 3 𝑐 2 = 6+12+14 3 = 32 3 =10 2 3 𝑐 1 𝑐 2 2 4 6 10 12 14

演習14-解答 クラスタ中心との距離に基づいて学習データの再割当てを行う 𝑐 1 𝑐 2 2 4 6 10 12 14 𝑆 1 = 2, 4, 6 , 𝑆 2 ={10, 12, 14} 各クラスタの中心を計算する 𝑐 1 = 2+4+6 3 = 12 3 =4 𝑐 2 = 10+12+14 3 = 36 3 =12 𝑐 1 𝑐 2 2 4 6 10 12 14 この段階でクラスタ中心が動かなくなるので終了

k-meansのプログラム function clusteredData = Kmeans_(trainData,cluster) fprintf('Process is running.\n'); [N D] = size(trainData); % サンプル総数N,特徴ベクトルの次元D % セントロイドをランダムに設定 centroid = randn(cluster,D); centroid = centroid*sqrtm(cov(trainData,1))+ones(cluster,1)*mean(trainData); dist = zeros(cluster,1); centroidDist = zeros(cluster,1); clusteredData = trainData; while(1) for n = 1:N for m = 1:cluster % クラスタ中心とサンプル間の距離計算 dist(m) = sum((centroid(m,:)-clusteredData(n,1:D)).^2); end % サンプルにクラスタ割り当て [minimum clusterTmp] = min(dist); clusteredData(n,D+1) = clusterTmp; centroidOld = centroid; % クラスタ中心を保存 for n = 1:cluster % クラスタ中心を再計算 centroid(n,:) = mean(clusteredData(clusteredData(:,D+1)==n,1:D)); % 前のクラスタ中心と現在のクラスタ中心との距離を計算 centroidDist(m) = sum((centroidOld(m,:)-centroid(m,:)).^2); if max(centroidDist)==0 break; % クラスタ中心に変化がなければ終了

特徴ベクトルの扱い-正規化 𝒙= 𝑥 1 , 𝑥 2 , …, 𝑥 𝑑 𝑡 で表す特徴ベクトルは， 𝒙= 𝑥 1 , 𝑥 2 , …, 𝑥 𝑑 𝑡 で表す特徴ベクトルは， 各要素の単位はまちまち（cm，m，Hz，%など） 各軸の分散が1になるように正規化するのが一つの方法 各軸の標準偏差を 𝜎 𝑖 とすると，正規化後の特徴ベクトル 𝒙 ′ は， 𝜎 𝑖 の逆数を対角にもつ対角行列を用いて求められる 𝒙′= 1 𝜎 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ 1 𝜎 𝑑 𝒙 正規化行列

演習15 以下の学習データ{ 3, 2 , 3, 4 , 5, 4 , (5, 6)}を正規化せよ 𝑥 2 6 4 2 𝑥 1 3 5 以下の学習データ{ 3, 2 , 3, 4 , 5, 4 , (5, 6)}を正規化せよ 𝑥 2 6 4 2 𝑥 1 3 5 ※荒木雅弘「フリーソフトでつくる音声認識システム」より

演習15-解答 平均ベクトルを計算する 𝝁= 1 4 3+3+5+5 2+4+4+6 = 4 4 𝑥 1 の標準偏差は， 𝝁= 1 4 3+3+5+5 2+4+4+6 = 4 4 𝑥 1 の標準偏差は， 1 4 { 3−4 2 + 3−4 2 + 5−4 2 + 5−4 2 } =1 𝑥 2 の標準偏差は， 1 4 { 2−4 2 + 4−4 2 + 4−4 2 + 6−4 2 } = 2

演習15-解答 1 0 0 1 2 正規化行列は 学習データに正規化行列をかけると,正規化後の学習データは以下 𝑥 2 3 2 2 2 2 1 0 0 1 2 正規化行列は 学習データに正規化行列をかけると,正規化後の学習データは以下 𝑥 2 3 2 2 2 2 𝑥 1 3 5

特徴ベクトルの扱い-次元の圧縮 特徴ベクトルの次元数が多い ・処理に時間がかかる ・識別に不要な情報の混入 主成分分析による次元の削減 　・処理に時間がかかる 　・識別に不要な情報の混入 主成分分析による次元の削減 𝑥 2 𝑥 2 𝑦 1次元の特徴空間に 写像しても分離可能 2次元の特徴空間 𝑥 1 𝑥 1

特徴ベクトルの扱い-次元の圧縮 𝑑次元の特徴ベクトル𝒙から，𝑑′次元の特徴ベクトル𝒚への線形変換は 𝑑行𝑑′列の行列𝑨を用いて表現できる． 𝒚= 𝑨 𝑡 𝒙 変換行列𝑨は，学習データの共分散行列Σの上位𝑑′個の固有値に対する 固有ベクトルを列とする行列となる． 𝑨= 𝑎 11 ⋯ 𝑎 1𝑑′ ⋮ ⋱ ⋮ 𝑎 𝑑1 ⋯ 𝑎 𝑑𝑑′ 固有ベクトル