C ++ implementation of C-mean algorithm (K-mean algorithm) in dynamic clustering

One: Description

The dynamic clustering method is a generally adopted method in pattern recognition, which has the following three points:

1: Select a certain distance metric as the similarity measure between the sample

2: Determine a guidelines for the quality of an evaluation cluster

3: Give a given initial classification, then use iterative algorithm to find the best cluster results that makes the criterion function

This article gives a C implementation of the C-mean algorithm.

(Algorithm description, seeing the music, Zhang Xueu, etc. << Mode Recognition >> P237 Tsinghua University Press)

2: Source code

2.1 header file

#pragma overce

#include

#include

Using namespace std;

#define datanum 19

#define maxdist 333333

Struct CDATA

{

INT X1;

INT x2;

}

Class ccmean

{

PUBLIC:

CCMean (CData * PDATA);

~ Ccmean (void);

Void init ();

Void Work (int init initclassnum);

Private:

// Calculate the mean of class i:

Void Calcumean (INT I);

// Calculate The Error of Class I:

Void Calcujc (INT I);

Void Calcuje ();

// Step 1 of c-mean algorithm

voidinploy ();

// Step 4 and 5 of c-mean algorithm

// da Is now in class i,

// Return Ture When Moving Da from Class To Class K

// Return False When We do Not Move DA

Bool Moveitok (Const CDATA & DA, INT I, INT & K);

// Calculate the distance OF to data:

INT DIST (Const CData & Mean, Const CDATA & DA);

// Print Result:

Void output ();

// ivlassnum is the initial class number, in text book, iClassNum <==> C

Int iClassNum;

// Pointer to Data Array:

CDATA * PDATA;

// store the mean of all classes. JUST UESES 0 to ICLASSNUM - 1;

// in text Book IS: M1, M2, M3, M4, ..., MC.

CData mean [datanum];

// store the error of each class, Just uESES 0 to ICLASSNUM - 1;

// The sum of jc [0] to jc [icsnum - 1] Will Be Je Defined Following JC;

INT JC [Datanum];

// the sum of jc [0] to jc [iClassNum - 1]

INT JE;

// pcla [i] Pointer Class I Which store in list

List * pcla [datanum];

}

2.2 Implement file

#include "assert.h"

#include "cmean.h" ccmean :: ccmean (cdata * pdata)

{

PDATA = PDATA;

For (INT i = 0; i

{

PCL [I] = New List ;

Assert (PCLA [i]! = 0);

}

JE = 0;

}

CCMean :: ~ ccmean ()

{

For (INT i = 0; i

Delete PCL [I];

}

Void ccmean :: init ()

{

For (INT i = 0; 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 :: item t = pcla [ii] -> begin ();

For (int i = 0; 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

{

Calcujc (i);

JE = JC [I];

}

}

Void ccmean :: Calcujc (int index)

{

List :: item t = pcla [index] -> begin ();

INT Si = (int) PCLA [INDEX] -> Size ();

JC [INDEX] = 0;

For (int i = 0; i

{

JC [Index] = Dist (mean [index], * it);

iTer ;

}

}

Int Ccmean :: Dist (Const CData & Mean, Const CData & DA)

{

Return (Mean.x1 - da.x1) * (mean.x2 - da.x2) * (mean.x2 - da.x2);

}

Void ccmean :: initdeploy ()

{

CDATA * PTEM = PDATA;

For (int i = 0; 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 i = IClassNum; I

Int minDis = maxdist;

INT POS = 0;

// Get the Least Distance Between PDATA [I] and M1, M2, M3 ....

For (int J = 0; j

{

INT Curdis = dist (PDATA [I], Mean [J]);

Curdis

{

Mindis = Curdis;

POS = J;

}

}

// Add PData To Class (POS):

PCLA [POS] -> Push_Back (PDATA [i]);

}

For (int i = 0; i

Calcumean (i);

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 returnaf

INT pk = maxdist;

INT PJ = 0;

INT TEMK = 0;

For (int J = 0; 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 = Pj;

Temk = j;

}

Else IF (PJ == PK && J == i)

{

// when pj == pk && j == i, We do not move (da) from class i to clas j

Temk = i;

}

}

IF (i == Temk)

Return False; // We do not move.

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 :: item t = pcla [i] -> begin ();

While (ore! = pcla [i] -> end ())

{

IF (item-> 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

Printf ("Class% D: / N", I);

List :: item t = pcla [i] -> begin ();

INT j = 1;

While (ore! = pcla [i] -> end ())

{

Printf ("(% D,% d)", item-> 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

{

// Step 3 of c-mean algorithm:

INT Si = (int) PCLA [I] -> Size ();

IF (Si == 1)

CONTINUE;

// Step 4 of c-mean algorithm:

List :: item t = 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 ();

}

2.3 test file

#include "cmean.h"

#include "process.h"

CDATA YY [DATANUM] =

{

{0,0}, {0, 1}, {1,0}, {1, 1}, {1, 2}, {2, 1}, {2, 2}, {2,3}

, {6, 6}, {6, 7}, {6, 8}, {7, 6}, {7, 7}, {7, 8}, {7, 9}, {8,7}

, {8, 8}, {8, 9}, {9, 8}

}

INT Main (int Argc, char * argv []) {

Ccmean cmean (yy);

CMean.work (2);

System ("pause");

Return 0;

}