k-means.cpp

K—means算法简单应用

#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

int N;  //数据个数
int K;  //集合个数
int *CenterIndex; //质心索引集合
double *Center;   //质心集合
double *CenterCopy;
double *DataSet;
double **Cluster;
int *Top;

/*算法描述:
  C-Fuzzy均值聚类算法采用的是给定类的个数K,将N个元素(对象)分配到K个类中去
  使得类内对象之间的相似性最大,而类之间的相似性最小 */


//函数声明部分
void InitData();
void InitCenter();
void CreateRandomArray(int n,int k,int *centerIndex);
void CopyCenter();
void UpdateCluster();
void UpdateCenter();
int  GetIndex(double value,double *centerIndex);
void AddtoCluster(int index,double value);
void print();
bool IsEqual(double *center,double *centercopy);

int main()
{
 int Flag=1;
 InitData();
 while(Flag)
 { 
  UpdateCluster();
  UpdateCenter();
  if(IsEqual(Center,CenterCopy))
  {
   Flag=0;
  }
  else
  {
   CopyCenter();
  }
 }
 print();

 system("pause");
}

void InitData()
{
 int i=0;
 int a;
 cout<<"请输入数据元素的个数:  ";
 cin>>N;
 cout<<"请输入分类数:  ";
 cin>>K;
 if(K>N)
 {
  return;
 }

 CenterIndex =new int [sizeof(int)*K];
 Center  =new double [sizeof(double)*K];
 CenterCopy =new double [sizeof(double)*K];
 DataSet  =new double [sizeof(double)*N];
 Cluster  =new double* [sizeof(double*)*K];
 Top   =new int [sizeof(int)*K];

 //初始化K个类的集合
 for(i=0;i<K;i++)
 {
  Cluster[i]=new double [sizeof(double)*N];
  Top[i]=0;
 }

 cout<<"请输入数据"<<endl;
 for(i=0;i<N;i++)
 {
  cin>>a;
  DataSet[i]=a;
 }

 //初始化质心集合
 InitCenter();
 UpdateCluster();
}

void InitCenter()
{
 int i=0;
 //产生随即的K个<N的不同的序列
 CreateRandomArray(N,K,CenterIndex);
 for(i=0;i<K;i++)
 {
  Center[i]=DataSet[CenterIndex[i]];
 }
 CopyCenter();

}

void CreateRandomArray(int n,int k,int *centerIndex)
{
 int i=0,j=0;
 for(i=0;i<K;i++)
 {
  int a=rand()%n;
  for(j=0;j<i;j++)
  {
   if(centerIndex[j]==a)
    break;
  }

  if(j>=i)
  {
   centerIndex[i]=a;
  }
  else
  {
   i--;
  }
 }
} 


void CopyCenter()
{
 int i=0;
 for(i=0;i<K;i++)
 {
  CenterCopy[i]=Center[i];
 }
}

void UpdateCluster()
{
 int i=0;
 int tindex;

 for(;i<K;i++)
 {
  Top[i]=0;
 }

 for(i=0;i<N;i++)
 {
  tindex=GetIndex(DataSet[i],Center);
  AddtoCluster(tindex,DataSet[i]);
 }
}


int GetIndex(double value,double *center)
{
 int i=0;
 int index=i;
 double min=fabs(value-center[i]);
 for(i=0;i<K;i++)
 {
  if(fabs(value-center[i])<min)
  {
   index=i;
   min=fabs(value-center[i]);
  }
 }

 return index;
}

void AddtoCluster(int index,double value)
{
 Cluster[index][Top[index]]=value;
 Top[index]++;
}


void UpdateCenter()
{
 int i=0,j=0;
 double sum;
 for(i=0;i<K;i++)
 {
  sum=0.0;
  for(j=0;j<Top[i];j++)
  {
   sum+=Cluster[i][j];
  }

  if(Top[i]>0)
  {
   Center[i]=sum/Top[i];
  }
 }
}

bool IsEqual(double *center,double*centercopy)
{
 int i;
 for(i=0;i<K;i++)
 {
  if(fabs(center[i]!=centercopy[i]))
   return 0;
 }
 return 1;
}

void print()
{
 int i,j;
 cout<<"===================================="<<endl;
 for(i=0;i<K;i++)
 {
  cout<<"第"<<i<<"组：质心为："<<Center[i]<<endl;
  cout<<"数据元素为:\n";
  for(j=0;j<Top[i];j++)
  {
   cout<<Cluster[i][j]<<'\t';
  }
  cout<<endl;
 }
}