OpenCV(2)MLライブラリ->K-Nearest Neighbour分類器
7773 ワード
KNNは最近接ノードアルゴリズム(k-Nearest Neighbor algorithm)の略であり、近接アルゴリズムとも呼ばれる.電子情報分類器アルゴリズムの一種である.KNN法は包容型データの特徴変数フィルタリングに特に有効である.
最近接ノードアルゴリズムはベクトル空間モデルを用いて分類され,概念は同じカテゴリのケースであり,互いの類似度が高いが,既知のカテゴリのケースとの類似度を計算することによって,未知のカテゴリのケースの可能な分類を評価することができる.
ターゲット:不明なカテゴリのケースを分類します.
入力:不明なカテゴリ・ケース・アイテムを分類します.既知カテゴリケースセットDは、j個の既知カテゴリのケースを含む.
出力:プロジェクトの可能なカテゴリ.
ItemとD 1,D 2......,Djの類似度を式に従って計算する.Sim(Item,D 1)、Sim(Item,D 2)……、Sim(Item,Dj)を得る.
Sim(Item,D 1),Sim(Item,D 2)…,Sim(Item,Dj)を並べ替え,類似度敷居tを超えると隣接事例集合NNに入れる.近隣事例集合NNから上位k名を取り出し,多数決によりItem可能カテゴリを得る.
1つのサンプルが、特徴空間におけるk個の最も類似した(すなわち、特徴空間において最も隣接している)サンプルの大部分があるカテゴリに属する場合、サンプルもこのカテゴリに属する.この方法は、分類決定において、最も隣接する1つまたは複数のサンプルのカテゴリにのみ基づいて、分類されるサンプルが属するカテゴリを決定する.
KNN法は原理的にも極限定理に依存するが,クラス決定においてはごく少量の隣接試料のみに関係する.従って、この方法を用いることで、サンプルのアンバランス問題をより好適に回避することができる.また,KNN法は主にクラスドメインを判別する方法で属するカテゴリを決定するのではなく,周囲に限られた隣接するサンプルに依存するため,クラスドメインの交差や重複が多い被分割サンプルセットに対しては他の方法よりもKNN法が適している.
この方法の欠点は,分類されるテキストごとに既知のサンプル全体までの距離を計算しなければ,K個の最近接点を求めることができないため,計算量が大きいことである.現在よく用いられている解決策は,既知のサンプルポイントを事前にクリップし,分類にあまり役に立たないサンプルを事前に除去することである.もう1つのReverse KNN法は,KNNアルゴリズムの計算の複雑さを低減し,分類の効率を向上させることができる.
このアルゴリズムは比較的サンプル容量の大きいクラスドメインの自動分類に適しているが,それらのサンプル容量の小さいクラスドメインはこのアルゴリズムを採用すると誤分が発生しやすい.
アルゴリズムの手順:
step.1---初期化距離が最大
step.2---未知のサンプルと各トレーニングサンプルの距離distを計算します.
step.3−−現在K個の最近接試料における最大距離maxdistを得る
step.4−−−distがmaxdistより小さい場合、このトレーニングサンプルをK−近隣サンプルとする
step.5--未知のサンプルとすべてのトレーニングサンプルの距離が計算されるまで、手順2、3、4を繰り返します.
step.6---K-近隣サンプルの各クラス番号の出現回数を統計する
step.7---不明なサンプルのクラス番号として、出現頻度が最も大きいクラス番号を選択します.
参照先:http://www.cnblogs.com/wengzilin/archive/2013/04/05/3001778.html
http://www.cnblogs.com/seacode/archive/2011/03/09/1979246.html
http://blog.csdn.net/yangtrees/article/details/7482890
http://www.cnblogs.com/xiangshancuizhu/archive/2011/08/06/2129355.html
http://blog.csdn.net/godenlove007/article/details/8084863
http://www.doc88.com/p-710937416243.html
http://blog.csdn.net/xlm289348/article/details/8876353
最近接ノードアルゴリズムはベクトル空間モデルを用いて分類され,概念は同じカテゴリのケースであり,互いの類似度が高いが,既知のカテゴリのケースとの類似度を計算することによって,未知のカテゴリのケースの可能な分類を評価することができる.
ターゲット:不明なカテゴリのケースを分類します.
入力:不明なカテゴリ・ケース・アイテムを分類します.既知カテゴリケースセットDは、j個の既知カテゴリのケースを含む.
出力:プロジェクトの可能なカテゴリ.
ItemとD 1,D 2......,Djの類似度を式に従って計算する.Sim(Item,D 1)、Sim(Item,D 2)……、Sim(Item,Dj)を得る.
Sim(Item,D 1),Sim(Item,D 2)…,Sim(Item,Dj)を並べ替え,類似度敷居tを超えると隣接事例集合NNに入れる.近隣事例集合NNから上位k名を取り出し,多数決によりItem可能カテゴリを得る.
1つのサンプルが、特徴空間におけるk個の最も類似した(すなわち、特徴空間において最も隣接している)サンプルの大部分があるカテゴリに属する場合、サンプルもこのカテゴリに属する.この方法は、分類決定において、最も隣接する1つまたは複数のサンプルのカテゴリにのみ基づいて、分類されるサンプルが属するカテゴリを決定する.
KNN法は原理的にも極限定理に依存するが,クラス決定においてはごく少量の隣接試料のみに関係する.従って、この方法を用いることで、サンプルのアンバランス問題をより好適に回避することができる.また,KNN法は主にクラスドメインを判別する方法で属するカテゴリを決定するのではなく,周囲に限られた隣接するサンプルに依存するため,クラスドメインの交差や重複が多い被分割サンプルセットに対しては他の方法よりもKNN法が適している.
この方法の欠点は,分類されるテキストごとに既知のサンプル全体までの距離を計算しなければ,K個の最近接点を求めることができないため,計算量が大きいことである.現在よく用いられている解決策は,既知のサンプルポイントを事前にクリップし,分類にあまり役に立たないサンプルを事前に除去することである.もう1つのReverse KNN法は,KNNアルゴリズムの計算の複雑さを低減し,分類の効率を向上させることができる.
このアルゴリズムは比較的サンプル容量の大きいクラスドメインの自動分類に適しているが,それらのサンプル容量の小さいクラスドメインはこのアルゴリズムを採用すると誤分が発生しやすい.
アルゴリズムの手順:
step.1---初期化距離が最大
step.2---未知のサンプルと各トレーニングサンプルの距離distを計算します.
step.3−−現在K個の最近接試料における最大距離maxdistを得る
step.4−−−distがmaxdistより小さい場合、このトレーニングサンプルをK−近隣サンプルとする
step.5--未知のサンプルとすべてのトレーニングサンプルの距離が計算されるまで、手順2、3、4を繰り返します.
step.6---K-近隣サンプルの各クラス番号の出現回数を統計する
step.7---不明なサンプルのクラス番号として、出現頻度が最も大きいクラス番号を選択します.
/****************************************************************************************\ * K-Nearest Neighbour Classifier * \****************************************************************************************/ // k Nearest Neighbors class CV_EXPORTS 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=0, const float** neighbors=0, CvMat* neighbor_responses=0, CvMat* dist=0 ) const; #ifndef SWIG CvKNearest( const cv::Mat& _train_data, const cv::Mat& _responses, const cv::Mat& _sample_idx=cv::Mat(), bool _is_regression=false, int max_k=32 ); virtual bool train( const cv::Mat& _train_data, const cv::Mat& _responses, const cv::Mat& _sample_idx=cv::Mat(), bool is_regression=false, int _max_k=32, bool _update_base=false ); virtual float find_nearest( const cv::Mat& _samples, int k, cv::Mat* results=0, const float** neighbors=0, cv::Mat* neighbor_responses=0, cv::Mat* dist=0 ) const; #endif virtual void clear(); int get_max_k() const; int get_var_count() const; int get_sample_count() const; bool is_regression() const; protected: virtual float write_results( int k, int k1, int start, int end, const float* neighbor_responses, const float* dist, CvMat* _results, CvMat* _neighbor_responses, CvMat* _dist, Cv32suf* sort_buf ) const; virtual void find_neighbors_direct( const CvMat* _samples, int k, int start, int end, float* neighbor_responses, const float** neighbors, float* dist ) const; int max_k, var_count; int total; bool regression; CvVectors* samples; }; // ：http://www.mysjtu.com/page/M0/S914/914320.html #include "stdafx.h" #include <ml.h> #include <iostream> #include <highgui.h> #include <cv.h> #include <cxcore.h> using namespace cv; using namespace std; int main( int argc, char** argv ) { const int K = 20; 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; // form the training samples cvGetRows( trainData, &trainData1, 0, train_sample_count/2 ); // cvRandArr( &rng_state, &trainData1, CV_RAND_NORMAL, cvScalar(200,200), cvScalar(50,50) ); // RNG 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) ); // learn classifier 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; // estimates the response and get the neighbors' labels response = knn.find_nearest(&sample,K,0,0,nearests,0); // compute the number of neighbors representing the majority for( k = 0, accuracy = 0; k < K; k++ ) { if( nearests->data.fl[k] == response) accuracy++; } // highlight the pixel depending on the accuracy (or confidence) 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)) ); } } // // display the original training samples 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; } 参照先:http://www.cnblogs.com/wengzilin/archive/2013/04/05/3001778.html
http://www.cnblogs.com/seacode/archive/2011/03/09/1979246.html
http://blog.csdn.net/yangtrees/article/details/7482890
http://www.cnblogs.com/xiangshancuizhu/archive/2011/08/06/2129355.html
http://blog.csdn.net/godenlove007/article/details/8084863
http://www.doc88.com/p-710937416243.html
http://blog.csdn.net/xlm289348/article/details/8876353