KMeans算法实现.docx

资源描述

KMeans算法实现.docx

《KMeans算法实现.docx》由会员分享，可在线阅读，更多相关《KMeans算法实现.docx（9页珍藏版）》请在冰点文库上搜索。

KMeans算法实现.docx

KMeans算法实现

K-Means算法实现

一.K-Means算法简介

k-meansalgorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k

它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。

它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。

k-means算法的工作过程说明如下:

首先从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类;然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）;不断重复这一过程直到标准测度函数开始收敛为止。

一般都采用均方差作为标准测度函数.k个聚类具有以下特点:

各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

具体如下:

输入:

k,data[n];

（1）选择k个初始中心点，例如c[0]=data[0],…c[k-1]=data[k-1];

（2）对于data[0]….data[n],分别与c[0]…c[n-1]比较，假定与c[i]差值最少，就标记为i;

（3）对于所有标记为i点，重新计算c[i]={所有标记为i的data[j]之和}/标记为i的个数;

（4）重复

（2）（3）,直到所有c[i]值的变化小于给定阈值。

二.K-Means算法的实现（C++环境下实现）

#include

usingnamespacestd;

//数据对象，size为维度

structVector

{double*coords;//所有维度的数值

intsize;

Vector（）:

coords（0）,size（0）{}

Vector（intd）{create（d）;}

//创建维度为d的数据，并将各维度初始化为0

voidcreate（intd）

{size=d;

coords=newdouble[size];

for（inti=0;i

coords[i]=0.0;}

//复制一个数据

voidcopy（constVector&other）

{if（size==0）//如果原来没有数据，创建之

create（other.size）;

for（inti=0;i

coords[i]=other.coords[i];}

//将另一个数据的各个维度加在自身的维度上

voidadd（constVector&other）

{for（inti=0;i

coords[i]+=other.coords[i];}

//释放数值的空间

~Vector（）

{

if（coords）

delete[]coords;

size=0;}};

//聚类结构

structCluster

{Vectorcenter;//中心/引力数据对象

int*member;//该聚类中各个数据的索引

intmemberNum;//数据的数量};

//KMeans算法类

classKMeans

{private:

intnum;//输入数据的数量

intdimen;//数据的维数

intclusterNum;//数据的聚类数

Vector*observations;//所有数据存放在这个数组

中

Cluster*clusters;//聚类数组

intpassNum;//迭代的趟数

public:

//初始化参数和动态分配内存

KMeans（intn,intd,intk,Vector*ob）

num（n）

dimen（d）

clusterNum（k）

observations（ob）

clusters（newCluster[k]）

{for（intk=0;k

clusters[k].member=newint[n];}

//释放内存

~KMeans（）

{for（intk=0;k

delete[]clusters[k].member;

delete[]clusters;}

voidinitClusters（）

{//由于初始数据中心是任意的，

//所以直接把前个数据作为NumClusters个聚类的

数据中心

for（inti=0;i

{clusters[i].member[0]=i;//

记录这个数据的索引到第i个聚类中

clusters[i].center.copy（observations[i]）;//

把这个数据作为数据中心}}

voidrun（）

{boolconverged=false;//是否收敛

passNum=0;

while（!

converged&&passNum<999）

//如果没有收敛，则再次迭代

//正常情况下总是会收敛，passNum<999是防万一

{distribute（）;//将数据分配到聚中心最近的聚类

converged=recalculateCenters（）;//计算新

的聚类中心，如果计算结果和上次相同，认为已经收敛

passNum++;}}

voiddistribute（）

{//将上次的记录的该聚类中的数据数量清0，重新开始分配数据

for（intk=0;k

getCluster（k）.memberNum=0;

//找出每个数据的最近聚类数据中心，并将该数据

分配到该聚类

for（inti=0;i

{Cluster&cluster=getCluster（closestCluster（i））;//

找出最接近的其中心的聚类

intmemID=cluster.memberNum;//memberNum是当前

记录的数据数量，也是新加入数据在member数组中的位置

cluster.member[memID]=i;//将数据索引加入Member数组

cluster.memberNum++;//聚类中的数据数量加1

}}

intclosestCluster（intid）{intclusterID=0;//

暂时假定索引为id的数据最接近第一个聚类

doubleminDist=eucNorm（id,0）;//计算到第一个

聚类中心的误差（本程序中用距离的平方和作为误差）

//计算其它聚类中心到数据的误差，找出其中最小

的一个

for（intk=1;k

{doubled=eucNorm（id,k）;

if（d

作为当前最小值

{minDist=d;

clusterID=k;}}

returnclusterID;}

//索引为id的数据到第k个聚类中心的误差（距离的平方）

doubleeucNorm（intid,intk）

{Vector&observ=observations[id];

Vector¢er=clusters[k].center;

doublesumOfSquare=0;

//将每个维度的差的平方相加，得到距离的平方

for（intd=0;d

{doubledist=observ.coords[d]-

center.coords[d];//在一个维度上中心到数据的距离

sumOfSquare+=dist*dist;}

returnsumOfSquare;}

//重新计算聚类中心

boolrecalculateCenters（）

{boolconverged=true;

for（intk=0;k

{Cluster&cluster=getCluster（k）;

Vectoraverage（dimen）;//初始的数据平均值

//统计这个聚类中数据的总和（因为在构造函数

中会将各维数值清0，所以可以直接加）

for（intm=0;m

average.add（observations[cluster.member[m]]）;

//计算各个维度的评价值

for（intd=0;d

{average.coords[d]/=cluster.memberNum;

if（average.coords[d]!

=cluster.center.coords[d]）//如

果和原来的聚类中心不同

//表示没有收敛

{converged=false;

cluster.center.coords[d]=average.coords[d];//用这次的平均值作为新的聚类中心

}}}

returnconverged;}

//获得第id个聚类

Cluster&getCluster（intid）

{returnclusters[id];}};

//打印一个数据

voidprintVector（ostream&output,constVector&v）

{for（inti=0;i

{if（i!

=0）

output<<",";

output<

{//从input输入中获取数据

intn,dimen,k;

//文本文件中头三个数据分别是数据数量（n）、数据维

度（dimen）和聚类数量（k）

input>>n>>dimen>>k;

//创建存储数据的数值

Vector*obs=newVector[n];

//将数据读入数组

for（inti=0;i

{obs[i].create（dimen）;//创建数据

//依次读入各个维度的数值

for（intd=0;d

{input>>obs[i].coords[d];}}

//建立KMeans算法类实例

KMeanskmeans（n,dimen,k,obs）;

kmeans.initClusters（）;//初始化

kmeans.run（）;//执行算法

//输出聚类数据，如果希望输出到文件中，

//将后面的output的定义改为下面的形式即可

//ofstreamoutput（"result.txt"）;

ostream&output=cout;

for（intc=0;c

{Cluster&cluster=kmeans.getCluster（c）;

output<<"----第"<<（c+1）<<"个聚类----\n";

//显示第c个聚类

output<<"聚类中心:

printVector（output,cluster.center）;

for（intm=0;m

{intid=cluster.member[m];

printVector（output,obs[id]）;

output<<"\n";}

output<

delete[]obs;}

intmain（）

{constchar*fileName="observations.txt";

ifstreamobIn（fileName）;

if（obIn.is_open（））

partitionObservations（obIn）;

else

cout<<"open"<

return0;}

展开阅读全文