k均值算法（c++）.txt

聚类分析最基本的K均值算法的C++语言实现程序

聚类分析（K均值算法）

2007-05-13 00:40 
/*K-MEANS源代码*/

#include "math.h"

#include "iostream.h"

#define N 10 //样本数目

#define K 4 //聚类中心数

struct Pattern //二维模式

{

double x1;

double x2;

int c; //类别标识

};

/*寻找数组中最小元素的位置*/

int FindMin(double *p,int n)

{

double d=p[0];

int i,j=0;

for(i=0;i<n;i++)

       if(d>p[i])

       {

        d=p[i];

        j=i;

       }

return j;

}

/*主函数*/

void main()

{

if(N<K)

{

       cout<<"聚类中心数应少于模式样本数"<<endl;

       return;

}

int i,j;

Pattern x[N]; //模式样本

Pattern c[K]; //聚类中心

Pattern sc[N];//记录上一次迭代的聚类中心

bool b;       //控制迭代

cout<<"输入"<<N<<"个二维模式样本："<<'\n';

/*输入样本*/

for(i=0;i<N;i++)

{
//x样本有两个特征值 
       cin>>x[i].x1;

       cin>>x[i].x2;

       x[i].c=0;//0 表示未被分类 

}

/*设置初始聚类中心*/

       for(i=0;i<K;i++)

       c[i]=x[i];

do

{

       /*记录聚类中心*/

       for(j=0;j<K;j++)

        sc[j]=c[j];

       /*按照最小距离原则进行分类*/

       for(i=0;i<N;i++)

       {

        double *d=new double[K];//开辟内存用于保存距离

        for(j=0;j<K;j++)

        {

         d[j]=sqrt((x[i].x1-c[j].x1)*(x[i].x1-c[j].x1)+(x[i].x2-c[j].x2)*(x[i].x2-c[j].x2));//最小欧式距离 

        }

        x[i].c=FindMin(d,K)+1;//最小距离原则

        delete d;

       }

       /*重新计算聚类中心*/

     for(j=0;j<K;j++)

       {

        c[j].x1=0;

        c[j].x2=0;

        int n=0;

        for(i=0;i<N;i++)

         if(x[i].c==j+1)

         {

          n++;

          c[j].x1+=x[i].x1;

          c[j].x2+=x[i].x2;

         }

        c[j].x1/=n;

        c[j].x2/=n;

       }

       /*比较聚类中心变化*/

       b=false;

       for(j=0;j<K;j++)

       {

        if(c[j].x1!=sc[j].x1||c[j].x2!=sc[j].x2)

        b=true;

       }       

}

while(b);

/*显示分类结果*/

for(j=0;j<K;j++)

{

       cout<<"第"<<j+1<<"类:";

       for(i=0;i<N;i++)

       {

        if(x[i].c==j+1)

         cout<<" ("<<x[i].x1<<" "<<x[i].x2<<")";

       }

       cout<<'\n';

}

}