k-means算法实例

#include "assert.h" #include "cmean.h" CCMean::CCMean(CData *pdata) { pData = pdata; for(int i = 0; i < DATANUM; i ++ ) { pcla[i] = new list< CData >; assert( pcla[i] != 0 ); } je = 0; } CCMean::~CCMean() { for(int i = 0; i < DATANUM; i ++ ) delete pcla[i]; } void CCMean::init() { for(int i = 0; i < DATANUM; i ++ ) { pcla[i]->clear(); mean[i].x1 = 0; mean[i].x2 = 0; } je = 0; } void CCMean::CalcuMean(int ii) { int sum1 = 0, sum2 = 0; int si = (int)pcla[ii]->size(); list< CData >::iterator iter = pcla[ii]->begin(); for(int i = 0; i < si; i ++ ) { sum1 += iter->x1; sum2 += iter->x2; iter++; } mean[ii].x1 = sum1 / si; mean[ii].x2 = sum2 / si; } void CCMean::CalcuJe() { for( int i = 0; i < iClassNum ; i ++ ) { CalcuJc( i ); je += jc[i]; } } void CCMean::CalcuJc( int index ) { list< CData >::iterator iter = pcla[index]->begin(); int si = (int)pcla[index]->size(); jc[index] = 0; for( int i = 0; i < si; i ++) { jc[index] += dist( mean[index], *iter ); iter ++; } } int CCMean::dist(const CData& mean, const CData& da) { return (mean.x1 - da.x1)*(mean.x1 - da.x1) + (mean.x2 - da.x2)*(mean.x2 - da.x2); } void CCMean::InitDeploy() { CData *ptem = pData; for( int i = 0; i < iClassNum; i++ ) { // choose the first iClassNum data as our initial class-center: mean[i] = *ptem; pcla[i]->push_back( *ptem ); ptem++; } // put other data to our initial classes: for( int ii = iClassNum; ii < DATANUM; ii ++ ) { int mindis = MAXDIST; int pos = 0; // get the least distance between pData[i] and m1, m2, m3 .... for( int j = 0; j < iClassNum; j ++ ) { int curdis = dist( pData[ii], mean[j] ); if( curdis < mindis ) { mindis = curdis; pos = j; } } // add pData to class (pos): pcla[pos]->push_back( pData[ii] ); } for( int k = 0; k < iClassNum ; k ++ ) CalcuMean(k); CalcuJe(); } bool CCMean::MoveItoK( const CData &da, int i , int& k ) { // now da is in class i,if da is moved to another class, return true, else return false int Pk = MAXDIST; int Pj = 0; int temk = 0; for( int j = 0; j < iClassNum; j ++ ) { int si = (int)pcla[j]->size(); if( j == i ) Pj = dist( mean[j], da ) * si/(si - 1); else Pj = dist( mean[j], da ) * si/(si + 1); if( Pj < Pk ) { Pk = Pj; temk = j; } else if ( Pj == Pk && j == i ) { // when Pj == Pk && j == i, we do not move (da) from class i to class j temk = i; } } if( i == temk ) return false; // we do NOT move da; k = temk; // add da to class k: pcla[k]->push_back( da ); // delete da from class i, first find the positon of da in class i: list< CData >::iterator iter = pcla[i]->begin(); while( iter != pcla[i]->end() ) { if( iter->x1 == da.x1 && iter->x2 == da.x2 ) break; iter++; } // now delete da from class i: pcla[i]->erase( iter ); // we have move da from class i to class k; return true; } void CCMean::OutPut() { for( int i = 0; i < iClassNum ; i ++ ) { printf("class %d:\n", i ); list< CData >::iterator iter = pcla[i]->begin(); int j = 1; while( iter != pcla[i]->end() ) { printf( "(%d, %d) ", iter->x1, iter->x2 ); iter ++; if( j++ % 5 == 0) printf("\n"); } printf("\n"); } } void CCMean::work(int InitClassNum) { iClassNum = InitClassNum; // step 1 of C-Mean algorithm InitDeploy(); int counter = 0; Again: //OutPut(); // step 2 of C-Mean algorithm: choose one sample y (here is da) from collection for( int i = 0; i < iClassNum ; i ++ ) { // step 3 of C-Mean algorithm: int si = (int)pcla[i]->size(); if( si == 1 ) continue; // step 4 of C-Mean algorithm: list< CData >::iterator iter = pcla[i]->begin(); for(int j = 0; j < (int)pcla[i]->size(); j++) { int k = 0; CData da = *iter; iter ++; // step 5 of C-Mean algorithm: if( MoveItoK( da , i, k ) == true ) { // step 6 of C-Mean algorithm: int OldJe = je; je -= jc[i]; je -= jc[k]; CalcuMean( i ); CalcuMean( k ); CalcuJc( i ); CalcuJc( k ); je += jc[i]; je += jc[k]; if( OldJe > je ) { counter = 0; goto Again; } } counter++; // step 7 of C-Mean algorithm: if( counter == DATANUM ) goto end; } } end: printf(" current Je is: %d\n", je ); OutPut(); }