K均值聚类算法

从网上找到了很多定义，这里选取比较典型的几个；

K-Mean分群法是一种分割式分群方法，其主要目标是要在大量高纬的资料点中找出

具有代表性的资料点；这些资料点可以称为群中心，代表点；然后再根据这些

群中心，进行后续的处理，这些处理可以包含

1）资料压缩：以少数的资料点来代表大量的资料，达到资料压缩的功能； 2）资料分类：以少数代表点来代表特点类别的资料，可以降低资料量及计算量；

分割式分群法的目的是希望盡量減小每個群聚中，每一點與群中心的距離平方差（square error）。

假設我們現在有一組包含c個群聚的資料，其中第 k 個群聚可以用集合 Gk來表示，假設 Gk包含nk筆

資料{x1, x2, …, xnk），此群聚中心為yk，則該群聚的平方差 ek可以定義為： ek = i |xi-yk|2，其中 xi是屬於第 k 群的資料點。 而這c個群聚的總和平方差E便是每個群聚的平方差總和：

E = k=1~c ek

我們分群的方法，就變成是一個最佳化的問題，換句話說，我們要如何選取 c 個群聚以及相關的群中心， 使得 E 的值為最小。

2．处理流程

（1） 从c个数据对象任意选择 k 个对象作为初始聚类中心； （2） 循环（3）到（4）直到每个聚类不再发生变化为止；

（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（4） 重新计算每个（有变化）聚类的均值（中心对象）

3. java算法的实现说明

1)假设给点一组c点资料X = {x1, ..., xc}，每一点都有d维；给定一个群聚的数目k,求其

最好的聚类结果。 2）BasicKMeans.java主类

int coordCount = 250;//原始的资料个树

int dimensions = 100;//每个资料的纬度数目

double[][] coordinates = new double[coordCount][dimensions];

这里假设c点资料为coordinates对象，其中c为coordCount,d为dimensions相应值。

int mk = 30; //想要群聚的数目 根据群聚数目定义mk个群聚类对象

mProtoClusters = new ProtoCluster[mK];//见ProtoCluster类说明 //首先随机选取mk个原始资料点作为群聚类

mProtoClusters[i]= new ProtoCluster (coordinates[j] );//i依此为0到mk的值；j为0到coordCount的值

定义一个变量用于记录和跟踪每个资料点属于哪个群聚类 mClusterAssignments = new int[coordCount];

mClusterAssignments[j]=i;//表示第j个资料点对象属于第i个群聚类 //开始循环

//依次调用计算每个群聚类的均值

mProtoClusters[i].updateCenter(mCoordinates);//计算第i个聚类对象的均值



//依次计算每个资料点到中心点的距离，然后根据最小值划分到相应的群集类中；

采用距离平方差来表示资料点到中心点的距离；



//定义一个变量，来表示资料点到中心点的距离 mDistanceCache = new double[coordCount ][mk];

//其中mDistanceCache[i][j]表示第i个资料点到第j个群聚对象中心点的距离； //距离算法描述():

a)依次取出每个资料点对象double[] coord = coordinates[i];

b)再依次取出每个群聚类中的中心点对象double[] center = mProtoClusters[j].mCenter;

c)计算coord对象与center对象之间的距离

double distance(double[] coord, double[] center) { int len = coord.length; double sumSquared = 0.0; for (int i=0; idouble v = coord[i] - center[i]; sumSquared += v*v; //平方差 }

return Math.sqrt(sumSquared); }

d)循环执行上面的流程，把结果记录在mDistanceCache[i][j]中；

//比较出最小距离，然后根据最小距离重新对相应对象进行划分 依次比较每个资料点的 最短中心距离， int nearestCluster(int ndx) { int nearest = -1;

double min = Double.MAX_VALUE; for (int c = 0; c < mK; c++) {

double d = mDistanceCache[ndx][c]; if (d < min) { min = d;

nearest = c; } }

return nearest; }

该方法返回该资料点对应的最短中心距离的群聚类的索引值； 比较每个 nearestCluster[coordCount] 的值和mClusterAssignments[coordCount]

的值是否相等，如果全相等表示所有的点已经是最佳距离了，直接返回； 否则需要重新调整资料点和群聚类的关系，调整完毕后再重新开始循环；



调整时需要更新下列数据：

a)更新mProtoClusters[i]中的mCurrentMembership集合； b)更新mClusterAssignments[i]中对应的值； 然后重行开始循环

3）ProtoCluster.java是一个包含代表点的群聚类，该类有两个最主要的属性\"代表点\"和\"群中心\"；

int[] mCurrentMembership;//用于表示每个群聚包含的数据资料点集合 double[] mCenter;//用于表示每个聚类对象的均值，也就是中心对象 void updateCenter(double[][] coordinates) { //该方法计算聚类对象的均值;

//根据mCurrentMembership取得原始资料点对象coord，该对象是coordinates的一个子集；然后取出该子集的均值；

取均值的算法很简单，可以把coordinates想象成一个m*n的距阵,每个均值就是每个纵向列的取和平均值,该值保 存在mCenter中

for (int i=0; i< mCurrentMembership.length; i++) {

double[] coord = coordinates[mCurrentMembership[i]]; for (int j=0; jmCenter[j] += coord[j];//得到每个纵向列的和； }

for (int i=0; imCenter[i] /= mCurrentSize; //对每个纵向列取平均值 } }