K-近傍法
===========

.. highlight:: cpp


このアルゴリズムでは，まず学習用サンプルをすべてキャッシュします．そして，新たなサンプルに対する応答を，その最近傍にある（ 
**K**
）個のサンプルを（投票や重み付き和などを用いて）分析し，予測します．この手法では，与えられたベクトルの近傍に存在する，応答が既知の特徴ベクトル，を調べて予測を行うので，「サンプルによる学習（learning by example）」と呼ばれることがあります．



.. index:: CvKNearest

.. _CvKNearest:

CvKNearest
----------

`id=0.867526929279 Comments from the Wiki <http://opencv.willowgarage.com/wiki/documentation/cpp/ml/CvKNearest>`__

.. ctype:: CvKNearest



K-近傍法モデル．




.. code-block:: c


    
    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:
        ...
    };
    

..


.. index:: CvKNearest::train

.. _CvKNearest::train:

CvKNearest::train
-----------------

`id=0.92941238207 Comments from the Wiki <http://opencv.willowgarage.com/wiki/documentation/cpp/ml/CvKNearest%3A%3Atrain>`__




.. cfunction:: 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``
）です．変数（特徴）の部分集合，およびデータ欠損はサポートされません．

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

パラメータ 
``_update_base``
は，モデルを一から学習する（ 
``update_base=false``
）か，新しい学習データを利用して更新する（ 
``update_base=true``
）か，を指定します．後者の場合，パラメータ 
``_max_k``
を，元の値よりも大きくしてはいけません．



.. index:: CvKNearest::find_nearest

.. _CvKNearest::find_nearest:

CvKNearest::find_nearest
------------------------

`id=0.49285212548 Comments from the Wiki <http://opencv.willowgarage.com/wiki/documentation/cpp/ml/CvKNearest%3A%3Afind_nearest>`__




.. cfunction:: 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``
の行である）各入力ベクトルに対して，このメソッドは， 
:math:`\texttt{k} \le \texttt{get\_max\_k()}`
個の最近傍を求めます．回帰の場合，予測結果はそれぞれのベクトルの最近傍の平均値となります．分類の場合，投票によりクラスが決定されます．

ユーザ独自の分類/回帰予測を行うために，このメソッドはオプションとして，近傍ベクトル自身へのポインタ（ 
``neighbors``
，サイズ 
``k*_samples->rows``
の配列）と，それに対応する出力値（ 
``neighbor_responses``
， 
``k*_samples->rows``
個の要素をもつベクトル），そして入力ベクトルからの近傍までの距離（ 
``dist``
， 
``k*_samples->rows``
個の要素をもつベクトル），を返すことができるようになっています．

それぞれの近傍は，各入力ベクトルまでの距離でソートされます．

また，単一の入力ベクトルが渡された場合，すべての出力行列はオプション扱いになり，このメソッドの戻り値が予測値なります．







.. code-block:: c


    
    #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;
    }
    

..