k均值算法是模式识别的聚分类问题，这是用C实现其算法以下是程序源代码
/****************************************************************************
* *
* KMEANS *
* *
*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
// FUNCTION PROTOTYPES
// DEFINES
#define SUCCESS 1
#define FAILURE 0
#define TRUE 1
#define FALSE 0
#define MAXVECTDIM 20
#define MAXPATTERN 20
#define MAXCLUSTER 10
char *f2a(double x, int width){
char cbuf[255];
char *cp;
int i,k;
int d,s;
cp=fcvt(x,width,&d,&s);
if (s) {
strcpy(cbuf,"-");
}
else {
strcpy(cbuf," ");
} /* endif */
if (d>0) {
for (i=0; i<d; i++) {
cbuf[i+1]=cp;
} /* endfor */
cbuf[d+1]=0;
cp+=d;
strcat(cbuf,".");
strcat(cbuf,cp);
} else {
if (d==0) {
strcat(cbuf,".");
strcat(cbuf,cp);
}
else {
k=-d;
strcat(cbuf,".");
for (i=0; i<k; i++) {
strcat(cbuf,"0");
} /* endfor */
strcat(cbuf,cp);
} /* endif */
} /* endif */
cp=&cbuf[0];
return cp;
}
// ***** Defined structures & classes *****
struct aCluster {
double Center[MAXVECTDIM];
int Member[MAXPATTERN]; //Index of Vectors belonging to this cluster
int NumMembers;
};
struct aVector {
double Center[MAXVECTDIM];
int Size;
};
class System {
private:
double Pattern[MAXPATTERN][MAXVECTDIM+1];
aCluster Cluster[MAXCLUSTER];
int NumPatterns; // Number of patterns
int SizeVector; // Number of dimensions in vector
int NumClusters; // Number of clusters
void DistributeSamples(); // Step 2 of K-means algorithm
int CalcNewClustCenters();// Step 3 of K-means algorithm
double EucNorm(int, int); // Calc Euclidean norm vector
int FindClosestCluster(int); //ret indx of clust closest to pattern
//whose index is arg
public:
system();
int LoadPatterns(char *fname); // Get pattern data to be clustered
void InitClusters(); // Step 1 of K-means algorithm
void RunKMeans(); // Overall control K-means process
void ShowClusters(); // Show results on screen
void SaveClusters(char *fname); // Save results to file
void ShowCenters();
};
void System::ShowCenters(){
int i,j;
printf("Cluster centers:\n");
for (i=0; i<NumClusters; i++) {
Cluster.Member[0]=i;
printf("ClusterCenter[%d]=(%f,%f)\n",i,Cluster.Center[0],Cluster.Center[1]);
} /* endfor */
printf("\n");
}
int System::LoadPatterns(char *fname){
FILE *InFilePtr;
int i,j;
double x;
if((InFilePtr = fopen(fname, "r")) == NULL)
return FAILURE;
fscanf(InFilePtr, "%d", &NumPatterns); // Read # of patterns
fscanf(InFilePtr, "%d", &SizeVector); // Read dimension of vector
fscanf(InFilePtr, "%d", &NumClusters); // Read # of clusters for K-Means
for (i=0; i<NumPatterns; i++) { // For each vector
for (j=0; j<SizeVector; j++) { // create a pattern
fscanf(InFilePtr,"%lg",&x); // consisting of all elements
Pattern[j]=x;
} /* endfor */
} /* endfor */
printf("Input patterns:\n");
for (i=0; i<NumPatterns; i++) {
printf("Pattern[%d]=(%2.3f,%2.3f)\n",i,Pattern[0],Pattern[1]);
} /* endfor */
printf("\n--------------------\n");
return SUCCESS;
}
//***************************************************************************
// InitClusters *
// Arbitrarily assign a vector to each of the K clusters *
// We choose the first K vectors to do this *
//***************************************************************************
void System::InitClusters(){
int i,j;
printf("Initial cluster centers:\n");
for (i=0; i<NumClusters; i++) {
Cluster.Member[0]=i;
for (j=0; j<SizeVector; j++) {
Cluster.Center[j]=Pattern[j];
} /* endfor */
} /* endfor */
for (i=0; i<NumClusters; i++) {
printf("ClusterCenter[%d]=(%f,%f)\n",i,Cluster.Center[0],Cluster.Center[1]);
} /* endfor */
printf("\n");
}
void System::RunKMeans(){
int converged;
int pass;
pass=1;
converged=FALSE;
while (converged==FALSE) {
printf("PASS=%d\n",pass++);
DistributeSamples();
converged=CalcNewClustCenters();
ShowCenters();
} /* endwhile */
}
double System::EucNorm(int p, int c){ // Calc Euclidean norm of vector difference
double dist,x; // between pattern vector, p, and cluster
int i; // center, c.
char zout[128];
char znum[40];
char *pnum;
pnum=&znum[0];
strcpy(zout,"d=sqrt(");
printf("The distance from pattern %d to cluster %d is calculated as:\n",c,p);
dist=0;
for (i=0; i<SizeVector ;i++){
x=(Cluster[c].Center-Pattern[p])*(Cluster[c].Center-Pattern[p]);
strcat(zout,f2a(x,4));
if (i==0)
strcat(zout,"+");
dist += (Cluster[c].Center-Pattern[p])*(Cluster[c].Center-Pattern[p]);
} /* endfor */
printf("%s)\n",zout);
return dist;
}
int System::FindClosestCluster(int pat){
int i, ClustID;
double MinDist, d;
MinDist =9.9e+99;
ClustID=-1;
for (i=0; i<NumClusters; i++) {
d=EucNorm(pat,i);
printf("Distance from pattern %d to cluster %d is %f\n\n",pat,i,sqrt(d));
if (d<MinDist) {
MinDist=d;
ClustID=i;
} /* endif */
} /* endfor */
if (ClustID<0) {
printf("Aaargh");
exit(0);
} /* endif */
return ClustID;
}
void System::DistributeSamples(){
int i,pat,Clustid,MemberIndex;
//Clear membership list for all current clusters
for (i=0; i<NumClusters;i++){
Cluster.NumMembers=0;
}
for (pat=0; pat<NumPatterns; pat++) {
//Find cluster center to which the pattern is closest
Clustid= FindClosestCluster(pat);
printf("patern %d assigned to cluster %d\n\n",pat,Clustid);
//post this pattern to the cluster
MemberIndex=Cluster[Clustid].NumMembers;
Cluster[Clustid].Member[MemberIndex]=pat;
Cluster[Clustid].NumMembers++;
} /* endfor */
}
int System::CalcNewClustCenters(){
int ConvFlag,VectID,i,j,k;
double tmp[MAXVECTDIM];
char xs[255];
char ys[255];
char nc1[20];
char nc2[20];
char *pnc1;
char *pnc2;
char *fpv;
pnc1=&nc1[0];
pnc2=&nc2[0];
ConvFlag=TRUE;
printf("The new cluster centers are now calculated as:\n");
for (i=0; i<NumClusters; i++) { //for each cluster
pnc1=itoa(Cluster.NumMembers,nc1,10);
pnc2=itoa(i,nc2,10);
strcpy(xs,"Cluster Center");
strcat(xs,nc2);
strcat(xs,"(1/");
strcpy(ys,"(1/");
strcat(xs,nc1);
strcat(ys,nc1);
strcat(xs,")(");
strcat(ys,")(");
for (j=0; j<SizeVector; j++) { // clear workspace
tmp[j]=0.0;
} /* endfor */
for (j=0; j<Cluster.NumMembers; j++) { //traverse member vectors
VectID=Cluster.Member[j];
for (k=0; k<SizeVector; k++) { //traverse elements of vector
tmp[k] += Pattern[VectID][k]; // add (member) pattern elmnt into temp
if (k==0) {
strcat(xs,f2a(Pattern[VectID][k],3));
} else {
strcat(ys,f2a(Pattern[VectID][k],3));
} /* endif */
} /* endfor */
if(j<Cluster.NumMembers-1){
strcat(xs,"+");
strcat(ys,"+");
}
else {
strcat(xs,")");
strcat(ys,")");
}
} /* endfor */
for (k=0; k<SizeVector; k++) { //traverse elements of vector
tmp[k]=tmp[k]/Cluster.NumMembers;
if (tmp[k] != Cluster.Center[k])
ConvFlag=FALSE;
Cluster.Center[k]=tmp[k];
} /* endfor */
printf("%s,\n",xs);
printf("%s\n",ys);
} /* endfor */
return
