OpenCV学習ノート(11)-K平均

K平均クラスタリングアルゴリズムはcxcoerにおいて、MLライブラリが誕生する前から存在するためである.K平均値はデータの自然カテゴリを見つけようとする.ユーザはカテゴリの個数を設定、K平均値は速やかに「良い」カテゴリの中心を見つける.「良い」とは、クラスタリングの中心がデータの自然カテゴリの中心にあることを意味する.K平均値は最も一般的なクラスタリングカウントの一つであり、Gauss混合における所望の最大化アルゴリズム(MLライブラリではCvEMとして実現)とよく似ており、平均ドリフトアルゴリズム(CVライブラリではcvMeanShift()として実現)とも似ている.K平均値は反復アルゴリズムであり、OpenCVではLloydアルゴリズム、Voronoi反復とも呼ばれる.アルゴリズムは以下のように動作.
1.データセットとカテゴリ数Kの入力(ユーザ指定)
2.カテゴリの中心点をランダムに割り当てる位置
3.各点を最も近いカテゴリの中心点の集合に入れる.
4.カテゴリの中心点をその集合の中心に移動
5.収束まで3ステップ目に進む.
図13-5は、K平均値がどのように動作かを示す.この例では、2回の反復だけで収束.現実のデータでは、アルゴリズムは常に速く収束するが、反復する回数が多い場合がある.
問題と解決策
K平均は効率的なクラスタリングアルゴリズムであるが、以下の3つの問題もある.
1.クラスタリングの中心を特定するための最良の方法を見つけることは保証されないが、ある解決策(例えば反復が無限に継続しない)に収束することを保証することができる.
2.Kの平均値は、どのようなカテゴリを使用すべきかを示すことができない.同意データセットでは、例えば図13-5の例では、2つのカテゴリを選択すると4つのカテゴリを選択すると、得られる結果は異なる、さらには不合理である.
3.K平均は空間の共分散行列が結果に影響しないと仮定し、あるいは正規化した(Mahalanobis距離の議論を参照).
この3つの問題にはいずれも「解決策」がある.これらの解決方法の中で最も良い2つは「ハイジャックデータの分散」に基づいている.K平均では、各クラスタリング中の線は彼のデータ点を持っており、これらの点の分散を計算し、最良のクラスタリングはあまり複雑さを引き起こさずに分散を最小にする.したがって、リストされた問題は以下のように改善することができる.
1.K平均を複数回行うと、初期のクラスタリング中心点が毎回異なる(OpenCVが中心点をランダムに選択するので簡単にできる)、最後に選択分散が最小になる結果
2.まずカテゴリ数を1にする、次にカテゴリ数(ある上限に達する)を上げ、クラスタリングのたびに前述の方法1を用いる.一般的には、総分散はすぐに曲がり点に達するまで下がります.これは、新しいクラスタリング中心を追加すると、総分散が著しく減少しないことを意味する.変曲点で停止する、このときのカテゴリ数を保存する.
3.逆共分散行列を乗じる.例えば、入力ベクトルが行毎に配列するデータ点が1つも行ない場合には、新たなデータベクトルD*,D*=DΣ-1/2を算出することによりデータ空間を正規化する.
K平均コード
K平均関数の呼び出しは簡単です.
void cvKMeans2(const CvArr* samples, int cluster_count,CvArr* labels,CvTrtmCriteria termcrit);
配列sampleは多次元のデータサンプル行列であり、各行に1つのデータサンプルである.ここで少し微妙ですが、データサンプルは浮動小数点型CV_32 FC 1ベクトル、CV_32FC2,CV_32 FC 3とCV_32 FC(k)の多次元ベクトル.パラメータcluster_countはカテゴリ数を指定し、戻りベクトルは各点の最後のカテゴリインデックスを含む.前にterncritについて議論した.

#include <QCoreApplication>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/core/core.hpp>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    
   #define MAX_CLUSTER 5
    CvScalar color_table[MAX_CLUSTER];
    IplImage* img = cvCreateImage(cvSize(500,500),8,3);
    CvRNG rng = cvRNG(0xffffffff);

    color_table[0] = CV_RGB(255,0,0);
    color_table[1] = CV_RGB(0,255,0);
    color_table[2] = CV_RGB(100,100,255);
    color_table[3] = CV_RGB(255,0,255);
    color_table[4] = CV_RGB(255,255,0);

    cvNamedWindow("clusters",1);
    for(;;)
    {
        int k,cluster_count = cvRandInt(&rng)%MAX_CLUSTER +1; //     1~5
        int i,sample_count = cvRandInt(&rng)%1000+1;  //     1~1000
        CvMat* points = cvCreateMat(sample_count,1,CV_32FC2); //  sample_count 1                
        CvMat* clusters = cvCreateMat(sample_count,1,CV_32SC1);//  sample_count 1             
        //            
        //     sample_count      cluster_count
        //     points,      cluster_count           sample_count/cluster_count
        //               ,        0~sample_count/cluster_count 
        //          sample_count/cluster_count~sample_count/cluster_count*2 ,             ,            
        for(k=0;k < cluster_count;k++)
        {
            CvPoint center;  //        
            CvMat point_chunk;
            center.x = cvRandInt(&rng)%img->width;
            center.y = cvRandInt(&rng)%img->height;
            //           
            //points     ,point_chunk    
            //    k*sample_count/cluster_count
            //      k== cluster-1     samplecount     (k+1)*sample_count/cluster_count
            cvGetRows(points,&point_chunk,k*sample_count/cluster_count,
                      k == cluster_count -1? sample_count:
                      (k+1)*sample_count/cluster_count);
            //point_chunk    ,CV_RAND_NORMAL               
            //cvScalar(center.x,center.y,0,0)       
            // cvScalar(img->width/6,img->height/6,0,0)                
            cvRandArr(&rng,&point_chunk,CV_RAND_NORMAL,
                      cvScalar(center.x,center.y,0,0),
                      cvScalar(img->width/6,img->height/6,0,0));
        }
        //      
        for(i=0;i<sample_count/2;i++)
        {
            // points                
            CvPoint2D32f* pt1=(CvPoint2D32f*)points->data.fl+cvRandInt(&rng)%sample_count;
            CvPoint2D32f* pt2=(CvPoint2D32f*)points->data.fl+cvRandInt(&rng)%sample_count;
            CvPoint2D32f temp;
            CV_SWAP(*pt1,*pt2,temp);
        }
        //points    ,cliuster_count   ,    clusters,          
        cvKMeans2(points,cluster_count,clusters,cvTermCriteria(CV_TERMCRIT_EPS + CV_TERMCRIT_ITER,10,1.0));
        cvZero(img);
        for(i=0;i<sample_count;i++)
        {
            CvPoint2D32f pt = ((CvPoint2D32f*)points->data.fl)[i];
            int cluster_idx = clusters->data.i[i];
            cvCircle(img,cvPointFrom32f(pt),2, color_table[cluster_idx],CV_FILLED);
        }
        cvReleaseMat(&points);
        cvReleaseMat(&clusters);
        cvShowImage("clusters",img);
        int key = cvWaitKey(0);
        if(key==27)
            break;
    }

    return a.exec();
}

このコードには、highguiを含むウィンドウ出力が使用され、cxcoreを含むのはKmean 2()が含まれているためである.main関数では、戻したカテゴリ表示の色を設定します.カテゴリ個数上界MAX_を設定するCLUSTERS(これは5)カテゴリの個数がランダムに生成されcluster_に格納されるcount;データサンプルの個数の上限(1000)を設定し、データサンプルの個数もランダムに生成されsample_に格納されるcount中最外層サイクルfor{]では、sample_count個のデータサンプルを格納する浮動小数点数二重チャネルマトリクスpoingを割り当て、0~cluster_count-1からデータサンプルを格納するための整数マトリクスclusters個のクラスタリングラベルを割り当てる.
次に、他のアルゴリズムで使用できるデータ生成for{}サイクルに入る.各カテゴリにsample_を記入します.count/cluster_count個のデータサンプル、これらの2次元データサンプルは正規分布に従い、正規分布の中心はランダムに選択される.
次のfor{}ループはデータサンプルの順序を乱すだけである.次にcvKMean 2()を使用して、クラスタリング中心の最大移動が1未満になるまで使用します.
最後のfor{}ループの結果を図に示す.次に配列を解放する、ユーザの入力が次の計算またはEscキーの終了に入るのを待つ.