K-均值聚类算法
1. K-均值聚类算法的工作原理：
K 均值算法（K-Meansalgorithm）是最常用的聚类算法之一，属于划分聚类方法。对于数据样本集 X={x1,x2,…,xn}，n为样本数，设拟划分为 k 个聚类V={v1,v2,…,vk }，cj 为vj 的中心，j=1,2,…,k。k均值算法将问题转化为组合优化问题：目标函数为；约束为：（1.1）αij∈{0,1}；（1.2）；（1.3）。其中，为样本与聚类中心的欧氏距离。式（1.1）限制一数据样本属于或不属于某一聚类，二者必居其一；式（1.2）规定一数据样本只属于一个聚类；式（1.3）表明聚类非空。K-means 聚类算法步骤：1）从数据集中随机选择 k 个样本作为初始聚类中心；2）将每个样本分配到与之最近的初始聚类中心；3）将所有样本分配到相应的聚类后，重新计算聚类中心 Cj；4）循环执行第 2）步和第3）步，直至聚类中心不再变化，算法终止。
2.K-means聚类算法的一般步骤
（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；
（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（3） 重新计算每个（有变化）聚类的均值（中心对象）；
（4） 循环（2）到（3）直到每个聚类不再发生变化为止。
3.K-均值聚类算法的总结
K 均值算法原理简单、对大数据集计算速度很快，因此应用广泛。但算法对初始聚类中心选择非常敏感。此外，基于梯度下降和算法的贪心性，使得算法易于陷入局部极值而无法达到全局最优。针对 k 均值算法易陷入局部最优的缺陷，许多研究将启发式规则引入算法，使聚类中心的移动产生扰动，取得理想效果。本文提出将模拟退火算法与 k 均值算法相结合，以提高算法的全局寻优能力。
4.K-均值聚类算法c语言代码
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <time.h>
#include <math.h>
long int posnum;
const int M=1000;
const double NUM_MAX=100000000;
const doubleNUM_MIN=0.00000001;
int knum;
int row;
int *numperclu;//每个簇的个数
//均值聚类数据结构
struct cluster
{double *data;
int dataindex;
struct cluster *next; };
typedef struct cluster ccnode;
typedef ccnode *ccLink;
ccLink kcluster;
//读文件，位置矩阵
double** readdata(char* s)
{FILE* fp;
if((fp=fopen(s,"rb"))==NULL)
{printf("erro! cannot openfile!\n");
exit(0); }
int i,j;
double **tpos;
tpos=(double**)malloc(M*sizeof(double*));
for ( i=0;i<M;i++)
{ tpos[i] =(double*)malloc(M*sizeof(double)); }
char temp[100]={0};
char *p = NULL; double x;
for(i=0;!feof(fp);i++)
{if((fgets(temp,100,fp))==NULL)
{break; }
p = temp; j=0;
while(1)
{x=atof(p);
tpos[i][j] = x;
j++;
if((p=strchr(p,' '))==NULL)
{break; }
p++;}}
posnum = i ; row = j;
double **pos;
pos= (double**)malloc(posnum*sizeof(double*));
for ( i=0;i<posnum;i++)
{ pos[i] =(double*)malloc(row*sizeof(double));
for(j=0;j<row;j++)
{pos[i][j] = tpos[i][j]; }
free(tpos[i]); }
free(tpos);
fclose(fp);
return pos; }
void insertcluster(ccLinkHead,double *key,int dataindex)
{ccLink pointer;
pointer = Head;
// Head->data[0]++;
int i;
while (pointer->next!=NULL){
pointer=pointer->next; }
ccLink New;
New =(ccLink)malloc(sizeof(ccnode));
pointer->next=New;
New->data=(double*)malloc(row*sizeof(double));
for (i=0;i<row;i++)
{New->data[i]=key[i]; }
New->dataindex=dataindex;
New->next=NULL; }
doubledist(double* d1,double *d2)
{int i;double distant=0;
for (i=0;i<row;i++)
{distant=distant+(d1[i]-d2[i])*(d1[i]-d2[i]);}
distant=sqrt(distant);
return distant; }
int isexit(double** temp)
{int i,j;double distant=0.0;
for (i=0;i<knum;i++)
{/* for (j=0;j<row;j++)
{printf("%lf",temp[i][j]);
printf("%lf",kcluster[i].data[j]); }
*/
distant=distant+dist(temp[i],kcluster[i].data); }
printf("%lf\n",distant);
if (distant<NUM_MIN)
{return 0; }
else
{return 1; }}
//重新计算均值并赋值
void calmean(ccLink Head)
{int i;
int num=0;
double*sum=(double*)(malloc(row*sizeof(double)));
for (i=0;i<row;i++)
{sum[i]=0; }
ccLink pointer;
pointer=Head->next;
for ( ;pointer!=NULL;
pointer=pointer->next)
{for (i=0;i<row;i++){
sum[i]=sum[i]+pointer->data[i];}
num++;}
for (i=0;i<row;i++)
{if (num!=0)
{sum[i]=sum[i]/num; }
else
{sum[i]=0; }
Head->data[i]=sum[i]; }
free(sum); }
double** initdata()
{ int i,j;
srand((unsigned)time(NULL));
double** pos;
pos =readdata("pos.txt");
numperclu =(int*)malloc(knum*sizeof(int));
for (i=0;i<knum;i++)
{numperclu[i]=0; }
int num;
int bestnum;
doublemin=NUM_MAX;
doubledistant;
kcluster=(ccLink)malloc(knum*sizeof(ccnode));
for (i=0;i<knum;i++)
{kcluster[i].data=(double*)malloc(row*sizeof(double));}
for (i=0;i<knum;i++)
{num=rand()%posnum;
for (j=0;j<row;j++){
kcluster[i].data[j]=pos[num][j];}
kcluster[i].dataindex = 0;
kcluster[i].next=NULL; }
for (i=0;i<posnum;i++)
{min = NUM_MAX;
for (j=0;j<knum;j++)
{distant=dist(pos[i],kcluster[j].data);
if (distant<min)
{min=distant;
bestnum=j; }}
insertcluster(&kcluster[bestnum],pos[i],i);
numperclu[bestnum]++;//簇内数目加一}
for (i=0;i<knum;i++)
{calmean(&kcluster[i]); }
return pos; }
//删除不在同一个簇内的节点，并查入到最近的簇中
void delandinsercluster(double*data,int bestnum)
{int i;
for (i=0;i<knum;i++)
{ccLink pointer;
pointer = &kcluster[i];
ccLink back=pointer;
pointer=pointer->next;
for (;pointer!=NULL;pointer=pointer->next)
{if(dist(data,pointer->data)<NUM_MIN)
{if (i!=bestnum)
{//查入到bestnum簇中
insertcluster(&kcluster[bestnum],data,pointer->dataindex);
numperclu[bestnum]++;//簇内数目加一
//删除i簇中的节点，并查入到bestnum簇中
back->next=pointer->next;
free(pointer->data);
free(pointer);
numperclu[i]--;//簇内数目减一}
break; }
back = pointer; }}}
int kmeancluster(double** pos)
{ int i,j;
int bestnum=0;
double distance=0.0;
for (i=0;i<posnum;i++)
{double min=NUM_MAX;
for (j=0;j<knum;j++)
{distance=dist(pos[i],kcluster[j].data);
if (distance<min)
{min=distance;
bestnum=j; }}
delandinsercluster(pos[i],bestnum);}
double**temp=(double**)malloc(knum*sizeof(double*));
for (i=0;i<knum;i++)
{temp[i]=(double*)malloc(row*sizeof(double));}
for (i=0;i<knum;i++)
{for (j=0;j<row;j++)
{temp[i][j]=kcluster[i].data[j];//后面的值}}
for (i=0;i<knum;i++)
{calmean(&kcluster[i]); }
int isstop = isexit(temp);
for (i=0;i<knum;i++)
{free(temp[i]); }
free(temp);
return isstop; }
void printcluster()
{ccLink pointer;
FILE* fp;
if((fp=fopen("out.txt","w"))==NULL)
{printf("error! can't openout file!\n");
exit(0); }
int i,j;
for (i=0;i<knum;i++)
{printf("第%d组:数目:%d节点:",i,numperclu[i]);
fprintf(fp,"%d %d",i,numperclu[i]);
for(pointer=kcluster[i].next;pointer!=NULL;
pointer=pointer->next )
{printf("%d",pointer->dataindex);
fprintf(fp,"%d",pointer->dataindex); }
printf("\n");
fprintf(fp,"\n");}
fclose(fp); }
void freeall()
{free(numperclu);
int i;
ccLink pointer;
ccLink tpointer;
for(i=0;i<knum;i++)
{pointer=&kcluster[i];
pointer=pointer->next;
while (pointer!=NULL)
{tpointer=pointer;
pointer=pointer->next;
free(tpointer->data);
free(tpointer); }
free(kcluster[i].data); }
free(kcluster); }
int main()
{knum=3;
int i=0;
double **pos = initdata();
int isstop=1;
while (isstop)
{i++;
isstop = kmeancluster(pos);
printf("第%d次迭代\n",i); }
printcluster();
freeall();
return 0; }
文章出处：http://wenku.baidu.com/link?url=_8dBPOxiunOYd3TNwZrlpo1dDs-q1EJLYBRSi3Q79MMzvbrAEjTjt4zpM7wZVtYKNbJTWGVtqVjMw3LMwZ-dl9yLc2dV_pSqSu9vwmYIacC
一种改进的K-均值聚类算法
摘要：在K-均值聚类算法中，K值需事先确定且在整个聚类过程中不能改变其大小，而按照经验K值划分所得的最终聚类结果一般并非最佳结果。本文将最大最小距离算法与K-均值算法结合，通过最大最小距离算法估算出K值，再用K-均值算法改进聚类精度。
1. 概述
聚类(cluster)做为数据挖掘技术的主要研究领域之一，近年来被广泛应用于各行各业。聚类分析方法做为一种无监督的学习方法，采用“物以类聚”的思想，将数据对象按某些属性分组成为多个类或簇，并且使得同类或簇中数据对象相似度尽可能大，而不同类或簇之间的差异尽可能大。K- 均值聚类算法是聚类分析中一种基本的划分方法，因其思想可靠，算法简洁，而且能有效的应用于大数据集而被广泛使用。但是传统的K 均值聚类算法往往受初始中心点选取的影响并且常常终止于局部最优。因此初始中心点的选择在K-均值聚类算法中非常重要，通常希望找到散布较大的点作为初始中心点。但是在传统的K-均值聚类算法中初始中心点选择的随机性较强，导致聚类结果的随机性。而且在传统的K-均值聚类算法中K的值需要给定，如果K值给定的不合理也将影响聚类的效果。
针对以上缺点本文将最大最小距离聚类算法和传统的K-均值聚类算法结合。形成一种初始中心点的距离最大，中心点数自动调整的K-均值算法。以达到更高的聚类精度。
2．K-均值聚类算法基本思想
K 均值聚类算法是一种基于划分方法的经典聚类算法之一，该算法的核心思想如下：首先从所给n 个数据对象中随机选取k个对象作为初始聚类中心点，然后对于所剩下的其它对象，则根据它们与所选k 个中心点的相似度(距离)分别分配给与其最相似的聚类，然后在重新计算所获聚类的聚类中心(该聚类中所有对象的均值)，不断重复这一过程直到标准测度函数开始收敛为止，其基本算法流程如下：
1) 从n个数据对象中任意选择k个对象作为初始聚类中心。
2) 根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离并根据最小距离对相应对象进行划分。
3) 重新计算每个(有变化)聚类的均值(中心对象)。
循环上述流程2 到3，直到每个聚类不再发生变化或者标准测度函数开始收敛为止。
3. 改进的K-均值聚类算法
3.1 最大最小距离法的基本思想
最大最小距离法是模式识别领域中的一种基于试探的算法,思想是取尽可能离得远的对象做为聚类中心,避免了K-均值聚类算法初值选取时可能出现的聚类种子过于邻近的情况,智能地确定初始聚类种子的个数。最大最小距离聚类的基本算法流程如下：
1)从n个数据对象中任意选择一个对象作为第一个类的中心。
2) 计算剩余对象与选取的对象的距离，找出距离最大的那个对象作为第二个类的中心。
3) 设定阈值T，（D为第一个中心点与第二个中心点的距离，通常取）。
4) 对剩余对象，分别计算到第一类中心点和第二类中心点的距离。令其中较小的那个为Di。若Di<T则将对象归入距离较小的那类；若Di>T则将该对象作为新的类的中心。
5)重复同样的处理,直到再找不到符合条件的新的聚类中心。
3.2 改进的K-均值聚类算法的基本思想
改进的K-均值聚类算法是将K-均值算法与最大最小算法相结合。其基本思想是：首先选取距离最大的两个对象作为初始聚类中心，然后对于剩余对象计算到两个初始聚类中心的距离，再与阈值比较判断是否有新的聚类中心。然后在重新计算所获聚类的聚类中心(该聚类中所有对象的均值)，不断重复这一过程直到标准测度函数开始收敛为止，其基本算法流程如下：
1）计算对象两两间的距离，找出距离最大的两个点作为初始聚类中心。
2）根据对象到初始中心点的距离判断所属分类。若对象到两初始中心点的较小的那个大于阈值，则把改对象作为新的聚类中心。
3）根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离并根据最小距离对相应对象进行划分。
4）重新计算每个(有变化)聚类的均值(中心对象)。
4.实例比较
本实验操作系统采用的是Windows操作系统，实验环境主要应用MyEclipse6.6 开发平台，采用Mysql 做为后台数据库。将iris 数据集应用于传统的K-均值聚类算法与本文所改进的K-均值聚类算法。其中iris数据集包含150个数据，标准聚类数为3，每类包括50 个数据，每个数据包含4 个属性；在K-均值聚类算法中，iris 数据集初始聚类数K 为：3、4。
4.1 传统的K-均值聚类
采用传统的K-均值算法对iris数据集进行聚类。聚类的效果如下面两个图所示：
(a) k=3时iris 数据集分类情况
(b) k=4时iris 数据集分类情况
4.2 改进的K-均值聚类
采用本文提出的改进的K-均值聚类，对iris数据集进行聚类。聚类的效果如下图所示：
从实验的聚类效果可以看出：初始聚类中心点的选择对传统的K-均值算法有很大的影响，初始中心点数量和位置的选择对聚类效果都影响聚类效果。而改进的K-均值算法则可以不用设置初始中心点的数量，中心点的数量将在聚类的过程中自动调整。而且两个初始中心点得位置选取距离最大的两个可以使聚类达到类间相似度最小。
5结语
虽然改进的K 均值遗传算法克服了K 均值聚类算法聚类中心点选择的问题，有效改进了聚类中心点的选取，并且使K 值可以向最佳聚类数学习，但是也应该看到改进的K-均值聚类算法的计算量比传统的K-均值聚类算法大了很多，改进的K-均值聚类算法还有很多不足之处，需要在以后的学习研究中继续改进。
K 均值聚类算法matlab程序
http://wenku.baidu.com/link?url=F63FBpCQGHBY9XM3dPsZ2mVeMyhVH-F9NE1_DhVy-eo6OaNtdVBsaWFPPgjkuKMov5Rh-njhvic9gHZYec1LzIphYCAHXKOfQiFgal0zkK7