機械学習 リファレンス マニュアル

• イントロダクション，共通のクラスと関数（Introduction. Common classes and functions）
• ナイーブベイズ（単純ベイズ）分類器（Normal Bayes Classifier）
• K近傍法（K Nearest Neighbors）
• サポートベクターマシン（SVM）
• 決定木（Decision Trees）
• ブースティング（Boosting）
• ランダムツリー（Random Trees）
• EMアルゴリズム（Expectation-Maximization）
• ニューラルネットワーク（Neural Networks）

K近傍法（K Nearest Neighbors）

このアルゴリズムでは，まず学習用サンプルを全て取り込み，次に新たに追加されるサンプルの応答を適当な数（K）の近傍を分析（投票や加重和などを使用することが多い）し，予測する． この手法では，予測のために与えられたベクトルの近傍にある既知の応答を用いて特徴ベクトルを調べるため，「サンプルによる学習（learning by example）」として紹介されることがある．

CvKNearest

K近傍法モデルクラス

class CvKNearest : public CvStatModel
{
public:

    CvKNearest();
    virtual ~CvKNearest();

    CvKNearest( const CvMat* _train_data, const CvMat* _responses,
                const CvMat* _sample_idx=0, bool _is_regression=false, int max_k=32 );

    virtual bool train( const CvMat* _train_data, const CvMat* _responses,
                        const CvMat* _sample_idx=0, bool is_regression=false,
                        int _max_k=32, bool _update_base=false );

    virtual float find_nearest( const CvMat* _samples, int k, CvMat* results,
        const float** neighbors=0, CvMat* neighbor_responses=0, CvMat* dist=0 ) const;

    virtual void clear();
    int get_max_k() const;
    int get_var_count() const;
    int get_sample_count() const;
    bool is_regression() const;

protected:
    ...
};

CvKNearest::train

モデルの学習

bool CvKNearest::train(const CvMat* _train_data, const CvMat* _responses,
                        const CvMat* _sample_idx=0, bool is_regression=false,
                        int _max_k=32, bool _update_base=false );

このメソッドは，K近傍法に必要なモデルを学習させる． これは以下の制限を持つようなtrain「メソッド」の一般的な仕様に従う． CV_ROW_SAMPLEデータレイアウトのみサポート，入力される変数は全て連続変数， 出力される変数はカテゴリ変数（is_regression=false）か，連続変数（is_regression=true）， あるいは変数の部分集合（var_idx）のいずれか．データ欠損はサポートされない．

パラメータ_max_kは，メソッドfind_nearestに渡される近傍の最大数を指定する．

パラメータ_update_baseは，モデルを始めから作り直す（_update_base=false）か， 新しい教師データを使って更新する（_update_base=true）かを指定する． 後者の場合，パラメータ_max_kを元の値より大きくしてはならない．

CvKNearest::find_nearest

入力ベクトルの近傍を探す

float CvKNearest::find_nearest(const CvMat* _samples, int k, CvMat* results=0,
        const float** neighbors=0, CvMat* neighbor_responses=0, CvMat* dist=0 ) const;

このメソッドは，各入力ベクトル（行列 _samplesの行に相当）に対し，k≤get_max_k()の最近傍を探す． 回帰の場合，予測された結果は個々の近傍ベクトルの平均値となる．分類の場合，クラスは投票により決定される．

ユーザ定義の分類/回帰による予測のために，このメソッドはオプションとして近傍ベクトル自体へのポインタ （neighbors, k*_samples->rows個のポインタの配列）と， それぞれの出力値（neighbor_responses， k*_samples->rows個の要素を持つベクトル）と， 入力ベクトルと近傍ベクトル間の距離（dist，k*_samples->rows個の要素を持つベクトル）を返すことができる．

各入力ベクトルに対し，近傍は各ベクトルへの距離でソートされる．

入力ベクトルが一つの場合， 全ての出力行列はオプションとなり， このメソッドにより予測された値が返される．

（例）k近傍法の分類器を用いた，混合ガウス分布からの2次元サンプルの分類

#include "ml.h"
#include "highgui.h"

int main( int argc, char** argv )
{
    const int K = 10;
    int i, j, k, accuracy;
    float response;
    int train_sample_count = 100;
    CvRNG rng_state = cvRNG(-1);
    CvMat* trainData = cvCreateMat( train_sample_count, 2, CV_32FC1 );
    CvMat* trainClasses = cvCreateMat( train_sample_count, 1, CV_32FC1 );
    IplImage* img = cvCreateImage( cvSize( 500, 500 ), 8, 3 );
    float _sample[2];
    CvMat sample = cvMat( 1, 2, CV_32FC1, _sample );
    cvZero( img );

    CvMat trainData1, trainData2, trainClasses1, trainClasses2;

    // 学習サンプルの生成
    cvGetRows( trainData, &trainData1, 0, train_sample_count/2 );
    cvRandArr( &rng_state, &trainData1, CV_RAND_NORMAL, cvScalar(200,200), cvScalar(50,50) );

    cvGetRows( trainData, &trainData2, train_sample_count/2, train_sample_count );
    cvRandArr( &rng_state, &trainData2, CV_RAND_NORMAL, cvScalar(300,300), cvScalar(50,50) );

    cvGetRows( trainClasses, &trainClasses1, 0, train_sample_count/2 );
    cvSet( &trainClasses1, cvScalar(1) );

    cvGetRows( trainClasses, &trainClasses2, train_sample_count/2, train_sample_count );
    cvSet( &trainClasses2, cvScalar(2) );

    // 分類器の学習
    CvKNearest knn( trainData, trainClasses, 0, false, K );
    CvMat* nearests = cvCreateMat( 1, K, CV_32FC1);

    for( i = 0; i < img->height; i++ )
    {
        for( j = 0; j < img->width; j++ )
        {
            sample.data.fl[0] = (float)j;
            sample.data.fl[1] = (float)i;

            // 応答の推定と，近傍のラベルの取得
            response = knn.find_nearest(&sample,K,0,0,nearests,0);

            // 多数を占める近傍数の計算
            for( k = 0, accuracy = 0; k < K; k++ )
            {
                if( nearests->data.fl[k] == response)
                    accuracy++;
            }
            // 精度（もしくは確信度）に応じてピクセルをハイライト
            cvSet2D( img, i, j, response == 1 ?
                (accuracy > 5 ? CV_RGB(180,0,0) : CV_RGB(180,120,0)) :
                (accuracy > 5 ? CV_RGB(0,180,0) : CV_RGB(120,120,0)) );
        }
    }

    // 元の学習サンプルの表示
    for( i = 0; i < train_sample_count/2; i++ )
    {
        CvPoint pt;
        pt.x = cvRound(trainData1.data.fl[i*2]);
        pt.y = cvRound(trainData1.data.fl[i*2+1]);
        cvCircle( img, pt, 2, CV_RGB(255,0,0), CV_FILLED );
        pt.x = cvRound(trainData2.data.fl[i*2]);
        pt.y = cvRound(trainData2.data.fl[i*2+1]);
        cvCircle( img, pt, 2, CV_RGB(0,255,0), CV_FILLED );
    }

    cvNamedWindow( "classifier result", 1 );
    cvShowImage( "classifier result", img );
    cvWaitKey(0);

    cvReleaseMat( &trainClasses );
    cvReleaseMat( &trainData );
    return 0;
}