読者です 読者をやめる 読者になる 読者になる

MyEnigma

とあるエンジニアのブログです。#Robotics #Programing #C++ #Python #MATLAB #Vim #Mathematics #Book #Movie #Traveling #Mac #iPhone

k-means法によるクラスタリングのためのMATLABサンプルプログラム

MATLAB Robot

f:id:meison_amsl:20150509170746p:plain

パターン認識と機械学習 上

パターン認識と機械学習 上

  • 作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/04/05
  • メディア: 単行本(ソフトカバー)
  • 購入: 6人 クリック: 33回
  • この商品を含むブログ (18件) を見る

 

目次

はじめに

ロボティクスにおいて、

データをいくつかのグループに分類する

クラスタリングは重要な技術です。

 

例えば、移動物体の位置と速度などを

レーザセンサやステレオカメラを使ってトラッキングしたい場合、

センサの観測値データをクラスタリングし、

移動物体から検出された観測点のみを抽出したくなります。

 

今回、クラスタリングのアルゴリズムの中でも最も基礎的な

k-meansアルゴリズムを使ってクラスタリングを実施する

MATLABサンプルプログラムを作ってみました。

k-meansアルゴリズムについて

k-meansアルゴリズムは、

各クラスタの平均値を使って、k個のクラスタに分けることから、

k-meansアルゴリズムと呼ばれているようです。

 

クラスタリングの方法としては

下記の順番で各データをラベリングします。

  1. すべてのデータをランダムにラベリングする

  2. それぞれのラベル(クラスタ)の平均値を計算する

  3. 各クラスタの平均値と各データの距離を使って一番近いクラスタにラベルを更新する

  4. 各データのラベルが変わらなくなるまで、2-3を繰り返す。

です。

 

非常にシンプルですが、

冒頭の図のように、ちゃんとクラスタリングしてくれます。

 

k-means法ではクラスタの数は

事前に決定し、パラメータとして与えておく必要があります。

下記の図のように、2つのソースから生成されたデータにおいても、

クラスタ数を3とすることで、無理やり3つのクラスタに分けることもできます。

f:id:meison_amsl:20150509174358p:plain  

MATLABサンプルプログラム

下記のGitHubのリポジトリにも置いてあります。

MATLABRobotics/kmeansSample.m at master · AtsushiSakai/MATLABRobotics

% -------------------------------------------------------------------------
%
% File : kmeansSample.m
%
% Discription : Sample code for k-means clustering
%
% Environment : Matlab
%
% Author : Atsushi Sakai
%
% Copyright (c): 2015 Atsushi Sakai
%
% License : GPL Software License Agreement
% -------------------------------------------------------------------------

function kmeansSample()
close all;
clear all;

disp('k-means clustering sample start!!');

data=GetRawData();%生データを取得する関数

%k-means法によるクラスタリング
nCluster=2;%クラスタの数
[result,means]=kmeansClustering(data,nCluster);
%クラスタリングの結果を表示
ShowClusteringResult(result,means,nCluster);

function [result,means]=kmeansClustering(data,nCluster)
%k-meansを使ってクラスタリングを実施する方法

%初期クラスタリング ランダムにクラスを振り分ける
result=[data randi(nCluster,[length(data(:,1)),1])];

while 1
    means=[];
    for i=1:nCluster
        %各クラスタの平均値を計算
        means=[means;mean(result(result(:,3)==i,1:2))];
    end
    
    %クラスタリングの結果を表示
    ShowClusteringResult(result,means,nCluster);
    
    %各データを平均値から近い順に再クラスタリング
    nUpdate=0;%クラスタが更新された数
    for j=1:length(result(:,1))
        
        %各データと各平均値までの距離を計算
        d=[];
        for k=1:nCluster
            d=[d norm(result(j,1:2)-means(k,:))];
        end
        [c,i]=min(d);%一番距離の小さいクラスタのIDを計算
        if result(j,3)~=i 
            result(j,3)=i;%クラスタを更新
            nUpdate=nUpdate+1;
        end
    end
    
    if nUpdate==0
        break;%クラスタが変化しなくなったら終了
    end
    
    pause;
end

function ShowClusteringResult(result,means,nCluster)
%クラスタリングの結果をグラフに描画する関数
hold off;

%グラフの色用のデータを作成
cc=hsv(nCluster);

%各クラスタ毎にデータを描画
for i=1:nCluster
    data=result(result(:,3)==i,1:2);
    plot(data(:,1),data(:,2),'.','Color',cc(i,:)); hold all;
    plot(means(i,1),means(i,2),'x','Color',cc(i,:));hold all;
end
axis equal;
grid on;
hold on;
    

function data=GetRawData()
%擬似データのクラスターの中心と誤差量
nSample=[0 0 2;
        10 10 5];
ndata=30;%一つのクラスタに関するデータ点
data=[];

for nc=1:length(nSample(:,1))
    for i=1:ndata
        xy=nSample(nc,1:2)+randn(1,2)*nSample(nc,3);
        data=[data;xy];
    end
end
data=sortrows(data,2);%データをソートして混ぜる

 

参考資料

k平均法 - Wikipedia

「パターン認識と機械学習」に挑戦 その1 ベイズ理論あたり(8章から11章まで) - old school magic

Pythonでx-means法を実装した - WEB SALAD

#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム | Antecanis

パターン認識と機械学習 上

パターン認識と機械学習 上

  • 作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/04/05
  • メディア: 単行本(ソフトカバー)
  • 購入: 6人 クリック: 33回
  • この商品を含むブログ (18件) を見る

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

  • 作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/02/29
  • メディア: 単行本
  • 購入: 6人 クリック: 14回
  • この商品を含むブログを見る

イラストで学ぶ 人工知能概論 (KS情報科学専門書)

イラストで学ぶ 人工知能概論 (KS情報科学専門書)