K-MEANS 算法

  • A+
所属分类:Script

输入聚类个数 k ,以及包含 n 个数据对象的数据库,输出满足方差最小标准的 k 个聚类

k-means 算法接受输入量 k ;然后将 n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个 “ 中心对象 ” (引力中心)来进行计算的。

k-means 算法的工作过程说明如下:首先从 n 个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数 。 k 个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

处理流程
( 1 ) 从 n 个数据对象任意选择 k 个对象作为初始聚类中心;
( 2 ) 循环( 3 )到( 4 )直到每个聚类不再发生变化为止 ;
( 3 ) 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;
( 4 ) 重新计算每个(有变化)聚类的均值(中心对象)

计算复杂度:

O(nkt), 其中 t 是迭代次数。

下面是程序代码:

效果是分成了1,2,3,5,6,7,9,10,11 和 100,150,200 和 1000三组,和感觉上的聚类一样:)


public class BasicKMeans {

public static void main(String[] args) {

double [] p={1,2,3,5,6,7,9,10,11,100,150,200,1000};

int k=3;

double [][] g;

g=cluster (p,k);

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

for ( int j=0;j<g[i]. length ;j++){

System. out .print(g[i][j]+ "\t" );

}

System. out .println();

}

}

/**

* 聚类函数

* @param p 数据对象

* @param k 聚类数目

* @return

*/

public static double [][] cluster( double [] p, int k){

double [] c= new double [k]; // 旧的聚类中心

double [] nc= new double [k]; // 新的聚类中心

double [][] g; // 结果

/*

* 1. 初始化聚类中心(经典方式是随机选取 k 个,本例中取前 k 个)

*/

for ( int i=0;i<k;i++){

c[i]=p[i];

}

/*

* 2. 循环聚类,更新聚类中心直到不变为止

*/

while ( true ){

/*

* 2.1 根据数组中每个元素分配给当前聚类中心

*/

g=group (p,c);

/*

* 2.2 计算分配后的聚类中心

*/

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

nc[i]=center (g[i]);

}

/*

* 2.3 更新聚类中心

*/

if (!equal (nc,c)){

c=nc;

nc= new double [k];

} else {

break ;

}

} //while(true)

return g;

}

/**

* 根据聚类中心 c 将数组 p 中元素分配到不同类别 !!!

* @param p 待分配的数组

* @param c 聚类中心数组

* @return

*/

private static double [][] group( double [] p, double [] c) {

int [] gi= new int [p. length ]; // 记录每个元素被归到哪一类

/*

* 考察每个元素 pi 同每个聚类中心 cj 的距离,

* 距离最小就将 pi 归为 j 类

*/

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

double [] d= new double [c. length ];

for ( int j=0;j<c. length ;j++){

d[j]=distance (p[i],c[j]);

}

int minDistOffset=min (d);

gi[i]=minDistOffset;

}

double [][] g= new double [c. length ][]; // 存放分组结果

/*

* 根据上面找到的结果,设置好返回值

*/

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

int s=0; // 某类的大小

for ( int j=0;j<gi. length ;j++){

if (gi[j]==i) s++;

}

g[i]= new double [s];

s=0;

for ( int j=0;j<gi. length ;j++){

if (gi[j]==i){

g[i][s]=p[j];

s++;

}

}

}

return g;

}

/**

* 重新计算一个类的中心(简单的以为聚类返回其算术平均值)

* @param gi

* @return

*/

private static double center( double [] gi) {

return sum (gi)/gi. length ;

}

/**

* 返回两点的一维欧氏距离

*/

private static double distance( double x, double y){

return Math.abs (x-y);

}

/**

* 返回数组和

*/

private static double sum( double [] arr) {

double sum=0.0;

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

sum+=arr[i];

}

return sum;

}

/**

* 返回数组(第一个)最小元素下标

*/

private static int min( double [] arr){

int min=0;

double minEle=arr[0];

for ( int i=1;i<arr. length ;i++){

if (arr[i]<minEle){

min=i;

minEle=arr[i];

}

}

return min;

}

/**

* 判断两个数组是否相同

*/

private static boolean equal( double [] a, double [] b){

if (a. length !=b. length ){

return false ;

} else {

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

if (a[i]!=b[i]) return false ;

}

}

return true ;

}

}

avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: