k-means聚类JAVA实例

标签: means 聚类 java | 发表时间:2014-05-30 20:50 | 作者:fz2543122681
出处:http://blog.csdn.net

《mahout in action》第六章。

datafile/cluster/simple_k-means.txt数据集如下:

1 1
2 1
1 2
2 2
3 3
8 8
8 9
9 8
9 9

1. k-means聚类算法原理


1、从D中随机取k个元素,作为k个簇的各自的中心。


2、分别计算剩下的元素到k个簇中心的相异度,将这些元素分别划归到相异度最低的簇。


3、根据聚类结果,重新计算k个簇各自的中心,计算方法是取簇中所有元素各自维度的算术平均数。


4、将D中全部元素按照新的中心重新聚类。


5、重复第4步,直到聚类结果不再变化。


6、将结果输出。

2. 举例说明


2.1 从D中随机取k个元素,作为k个簇的各自的中心。

private final static Integer K=2; //选K=2,也就是估算有两个簇。
下面选1 1,2,1两个点。
C0:1 1
C1:2 1

2.2 分别计算剩下的元素到k个簇中心的相异度,将这些元素分别划归到相异度最低的簇。

结果为:
C0 : 1 1
C0:的点为:1.0,2.0
C1:  2 1
C1:的点为:2.0,2.0
C1:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0



2.3 根据2.2的聚类结果,重新计算k个簇各自的中心,计算方法是取簇中所有元素各自维度的算术平均数。

采取欧区距离公式。
C0 新的簇心为:1.0,1.5
C1 新的簇心为:5.857142857142857,5.714285714285714

2.4 将D中全部元素按照新的中心重新聚类。

第2次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0


2.5  重复第4步,直到聚类结果不再变化。

当距离小于某个值的时候,就认为聚类已经聚类了,不需要再迭代,这里的值选0.001
private final static Double converge=0.001;

------------------------------------------------
C0的簇心为:1.6666666666666667,1.75
C1的簇心为:7.971428571428572,7.942857142857143
各个簇心移动中最小的距离为,move=0.7120003121097943
第3次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.777777777777778,1.7916666666666667
C1的簇心为:8.394285714285715,8.388571428571428
各个簇心移动中最小的距离为,move=0.11866671868496578
第4次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.7962962962962965,1.7986111111111114
C1的簇心为:8.478857142857143,8.477714285714285
各个簇心移动中最小的距离为,move=0.019777786447494432
第5次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.799382716049383,1.7997685185185184
C1的簇心为:8.495771428571429,8.495542857142857
各个簇心移动中最小的距离为,move=0.003296297741248916
第6次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.7998971193415638,1.7999614197530864
C1的簇心为:8.499154285714287,8.499108571428572
各个簇心移动中最小的距离为,move=5.49382956874724E-4

3. JAVA实现

package mysequence.machineleaning.clustering.kmeans;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

import mysequence.machineleaning.clustering.canopy.Point;

public class MyKmeans {

	static Vector<Point>  li=new Vector<Point>();
	//static List<Point>  li=new ArrayList<Point>();
	static List<Vector<Point>> list=new ArrayList<Vector<Point>>(); //每次迭代保存结果,一个vector代表一个簇
	private final static Integer K=2; //选K=2,也就是估算有两个簇。
	private final static Double converge=0.001; //当距离小于某个值的时候,就认为聚类已经聚类了,不需要再迭代,这里的值选0.001	
	
	//读取数据
	public static final void readF1() throws IOException {      
		String filePath="datafile/cluster/simple_k-means.txt";
		BufferedReader br = new BufferedReader(new InputStreamReader(
        new FileInputStream(filePath)));
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            if(line.length()==0||"".equals(line))continue;
        	String[] str=line.split(" ");               
            Point p0=new Point();
    		p0.setX(Double.valueOf(str[0]));
    		p0.setY(Double.valueOf(str[1]));
    		li.add(p0);
            //System.out.println(line);               
        }
        br.close();
    }
	  //math.sqrt(double n)
    //扩展下,如果要给m开n次方就用java.lang.StrictMath.pow(m,1.0/n);
	//采用欧氏距离
	public static  Double DistanceMeasure(Point p1,Point p2){
		
		Double tmp=StrictMath.pow(p2.getX()-p1.getX(), 2)+StrictMath.pow(p2.getY()-p1.getY(), 2);
		return Math.sqrt(tmp);
	}
	
	//计算新的簇心
	public static Double CalCentroid(){
		System.out.println("------------------------------------------------");
		Double movedist=Double.MAX_VALUE;
		for(int i=0;i<list.size();i++){
			Vector<Point> subli=list.get(i);
			Point po=new Point();
			Double sumX=0.0;
			Double sumY=0.0;
			Double Clusterlen=Double.valueOf(subli.size());
			for(int j=0;j<Clusterlen;j++){
				Point nextp=subli.get(j);
				sumX=sumX+nextp.getX();
				sumY=sumY+nextp.getY();
			}
			po.setX(sumX/Clusterlen);
			po.setY(sumY/Clusterlen);
			//新的点与旧点之间的距离
			Double dist=DistanceMeasure(subli.get(0),po);
			//在多个簇心移动的过程中,返回移动距离最小的值
			if(dist<movedist)movedist=dist;
			list.get(i).clear();
			list.get(i).add(po);
			System.out.println("C"+i+"的簇心为:"+po.getX()+","+po.getY());
		}
		String test="ll";
		return movedist;
	}
	//本次的簇心
	//下一次移动的簇心
	
	private static Double move=Double.MAX_VALUE;//移动距离
	//不断地迭代,直到收敛
	public static void RecursionKluster(){
		for(int times=2;move>converge;times++){
			System.out.println("第"+times+"次迭代");
			//默认每一个list里的Vector第0个元素是质心
			for(int i=0;i<li.size();i++){
				Point p=new Point();
				 p=li.get(i);
				int index = -1;
				
	            double neardist = Double.MAX_VALUE;
				for(int k=0;k<K;k++){
					Point centre=list.get(k).get(0);
					double currentdist=DistanceMeasure(p,centre);
					if(currentdist<neardist){
						neardist=currentdist;
						index=k;
					}
				}
				
				System.out.println("C"+index+":的点为:"+p.getX()+","+p.getY());
				list.get(index).add(p);
				
			}
			//重新计算簇心,并返回移动的距离,最小的那个距离
			
			move=CalCentroid();
			System.out.println("各个簇心移动中最小的距离为,move="+move);
		}
	}
	
	public static void Kluster(){
		
		for(int k=0;k<K;k++){
			Vector<Point> vect=new Vector<Point>();
			Point p=new Point();
			p=li.get(k);
			vect.add(p);
			list.add(vect);
		}
		System.out.println("第1次迭代");
		//默认每一个list里的Vector第0个元素是质心
		for(int i=K;i<li.size();i++){
			Point p=new Point();
			 p=li.get(i);
			int index = -1;
			
            double neardist = Double.MAX_VALUE;
			for(int k=0;k<K;k++){
				Point centre=list.get(k).get(0);
				double currentdist=DistanceMeasure(p,centre);
				if(currentdist<neardist){
					neardist=currentdist;
					index=k;
				}
			}
			
			System.out.println("C"+index+":的点为:"+p.getX()+","+p.getY());
			list.get(index).add(p);
			
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//读取数据
		readF1();
		//第一次迭代
		Kluster();
		//第一次迭代后计算簇心
		CalCentroid();
		//不断迭代,直到收敛
		RecursionKluster();
	}

}

4.运行结果:

C0:1 1
C1:2 1
第1次迭代
C0:的点为:1.0,2.0
C1:的点为:2.0,2.0
C1:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.0,1.5
C1的簇心为:5.857142857142857,5.714285714285714
第2次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.6666666666666667,1.75
C1的簇心为:7.971428571428572,7.942857142857143
各个簇心移动中最小的距离为,move=0.7120003121097943
第3次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.777777777777778,1.7916666666666667
C1的簇心为:8.394285714285715,8.388571428571428
各个簇心移动中最小的距离为,move=0.11866671868496578
第4次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.7962962962962965,1.7986111111111114
C1的簇心为:8.478857142857143,8.477714285714285
各个簇心移动中最小的距离为,move=0.019777786447494432
第5次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.799382716049383,1.7997685185185184
C1的簇心为:8.495771428571429,8.495542857142857
各个簇心移动中最小的距离为,move=0.003296297741248916
第6次迭代
C0:的点为:1.0,1.0
C0:的点为:2.0,1.0
C0:的点为:1.0,2.0
C0:的点为:2.0,2.0
C0:的点为:3.0,3.0
C1:的点为:8.0,8.0
C1:的点为:8.0,9.0
C1:的点为:9.0,8.0
C1:的点为:9.0,9.0
------------------------------------------------
C0的簇心为:1.7998971193415638,1.7999614197530864
C1的簇心为:8.499154285714287,8.499108571428572
各个簇心移动中最小的距离为,move=5.49382956874724E-4
作者:fz2543122681 发表于2014-5-30 12:50:12 原文链接
阅读:132 评论:0 查看评论

相关 [means 聚类 java] 推荐:

k-means聚类JAVA实例

- - CSDN博客互联网推荐文章
《mahout in action》第六章. datafile/cluster/simple_k-means.txt数据集如下:. 1、从D中随机取k个元素,作为k个簇的各自的中心. 2、分别计算剩下的元素到k个簇中心的相异度,将这些元素分别划归到相异度最低的簇. 3、根据聚类结果,重新计算k个簇各自的中心,计算方法是取簇中所有元素各自维度的算术平均数.

TensorFlow实战之K-Means聚类算法实践

- - SegmentFault 最新的文章
Google 最近开源了它的第二代人工智能与数值计算库TensorFlow. TensorFlow由Google大脑团队开发,并且能够灵活地运行在多个平台上——包括GPU平台与移动设备中. TensorFlow的核心就是使用所谓的数据流,可以参考Wikipedia上的有关于 Genetic Programming 的相关知识,譬如:.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

Spark范例:K-means算法

- - yiihsia[互联网后端技术]_yiihsia[互联网后端技术]
k-means 算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小. 聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的. 算法首先会随机确定K个中心位置(位于空间中代表聚类中心的点),然后将各个数据项分配给最临近的中心点.

利用Mahout实现在Hadoop上运行K-Means算法

- - CSDN博客云计算推荐文章
    K-Means算法是基于分划分的最基本的聚类算法,是学习机器学习、数据挖掘等技术的最基本的 知识,所以掌握其运行原理是很重要的.     转载请注明出处:  http://hanlaiming.freetzi.com/?p=144.      一、介绍Mahout.     Mahout是Apache下的开源机器学习软件包,目前实现的机器学习算法主要包含有 协同过滤/推荐引擎, 聚类和 分类三个部分.

K-Means算法的10个有趣用例

- - 神刀安全网
摘要: 让我们走进K-Means算法的“前世今生”以及和它有关的十个有趣的应用案例. K-means算法具有悠久的历史,并且也是最常用的聚类算法之一. K-means算法实施起来非常简单,因此,它非常适用于机器学习新手爱好者. 首先我们来回顾K-Means算法的起源,然后介绍其较为典型的应用场景. 1967年,James MacQueen在他的论文《用于多变量观测分类和分析的一些方法》中首次提出 “K-means”这一术语.

Java中的锁(Locks in Java)

- - 并发编程网 - ifeve.com
原文链接 作者:Jakob Jenkov 译者:申章 校对:丁一. 锁像synchronized同步块一样,是一种线程同步机制,但比Java中的synchronized同步块更复杂. 因为锁(以及其它更高级的线程同步机制)是由synchronized同步块的方式实现的,所以我们还不能完全摆脱synchronized关键字( 译者注:这说的是Java 5之前的情况).

kmeans 实现文本聚类

- - IT瘾-dev
拿到的需求是输入n个文本,对文本进行聚类,由于这些输入不能通过历史数据进行训练,所以这个主要就是用无监督学习来解决. 谈到聚类就会想到kmeans,它的核心思想是给定的K值和K个初始质心将样本中每个点都分到距离最近的类簇中,当所有点分配完后根据每个类簇的所有点重新计算质心,一般是通过平均值计算,然后再将每个点分到距离最近的新类簇中,不断循环此操作,直到质心不再变化或达到一定的迭代次数.

聚类算法之DBSCAN

- - 标点符
K-Means算法和 Mean Shift算法都是基于距离的聚类算法,基于距离的聚类算法的聚类结果是球状的簇,当数据集中的聚类结果是非球状结构时,基于距离的聚类算法的聚类效果并不好. 与基于距离的聚类算法不同的是,基于密度的聚类算法可以发现任意形状的聚类. 在基于密度的聚类算法中,通过在数据集中寻找被低密度区域分离的高密度区域,将分离出的高密度区域作为一个独立的类别.

Java PaaS 对决

- 呆瓜 - IBM developerWorks 中国 : 文档库
本文为 Java 开发人员比较了三种主要的 Platform as a Service (PaaS) 产品:Google App Engine for Java、Amazon Elastic Beanstalk 和 CloudBees RUN@Cloud. 它分析了每种服务独特的技术方法、优点以及缺点,而且还讨论了常见的解决方法.