`
AngelAndAngel
  • 浏览: 234296 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

聚类算法之kmeans算法java版本

阅读更多
   聚类的意思很明确,物以类聚,把类似的事物放在一起。
    聚类算法是web智能中很重要的一步,可运用在社交,新闻,电商等各种应用中,我打算专门开个分类讲解聚类各种算法的java版实现。
    首先介绍kmeans算法。
    kmeans算法的速度很快,性能良好,几乎是应用最广泛的,它需要先指定聚类的个数k,然后根据k值来自动分出k个类别集合。
    举个例子,某某教练在得到全队的数据后,想把这些球员自动分成不同的组别,你得问教练需要分成几个组,他回答你k个,ok可以开始了,在解决这个问题之前有必要详细了解自己需要达到的目的:根据教练给出的k值,呈现出k个组,每个组的队员是相似的。
   首先,我们创建球员类。
  
    package kmeans;

   /**
    * 球员
     * 
    * @author 阿飞哥
    * 
    */
  public class Player {

	private int id;
	private String name;

	private int age;

	/* 得分 */
	@KmeanField
	private double goal;

	/* 助攻 */
	//@KmeanField
	private double assists;

	/* 篮板 */
	//@KmeanField
	private double backboard;

	/* 抢断 */
	//@KmeanField
	private double steals;

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public double getGoal() {
		return goal;
	}

	public void setGoal(double goal) {
		this.goal = goal;
	}

	public double getAssists() {
		return assists;
	}

	public void setAssists(double assists) {
		this.assists = assists;
	}

	public double getBackboard() {
		return backboard;
	}

	public void setBackboard(double backboard) {
		this.backboard = backboard;
	}

	public double getSteals() {
		return steals;
	}

	public void setSteals(double steals) {
		this.steals = steals;
	}

	
}

   

@KmeanField这个注解是自定义的,用来标示这个属性是否是算法需要的维度。
代码如下
package kmeans;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * 在对象的属性上标注此注释,
 * 表示纳入kmeans算法,仅支持数值类属性
 * @author 阿飞哥
 */
@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.FIELD)
public @interface KmeanField {
}


接下来看看最核心的kmeans算法,具体实现过程如下:
1,初始化k个聚类中心
2,计算出每个对象跟这k个中心的距离(相似度计算,这个下面会提到),假如x这个对象跟y这个中心的距离最小(相似度最大),那么x属于y这个中心。这一步就可以得到初步的k个聚类
3,在第二步得到的每个聚类分别计算出新的聚类中心,和旧的中心比对,假如不相同,则继续第2步,直到新旧两个中心相同,说明聚类不可变,已经成功

实现代码如下:
package kmeans;

import java.lang.annotation.Annotation;
import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author 阿飞哥
 * 
 */
public class Kmeans<T> {

	/**
	 * 所有数据列表
	 */
	private List<T> players = new ArrayList<T>();

	/**
	 * 数据类别
	 */
	private Class<T> classT;

	/**
	 * 初始化列表
	 */
	private List<T> initPlayers;

	/**
	 * 需要纳入kmeans算法的属性名称
	 */
	private List<String> fieldNames = new ArrayList<String>();

	/**
	 * 分类数
	 */
	private int k = 1;

	public Kmeans() {

	}

	/**
	 * 初始化列表
	 * 
	 * @param list
	 * @param k
	 */
	public Kmeans(List<T> list, int k) {
		this.players = list;
		this.k = k;
		T t = list.get(0);
		this.classT = (Class<T>) t.getClass();
		Field[] fields = this.classT.getDeclaredFields();
		for (int i = 0; i < fields.length; i++) {
			Annotation kmeansAnnotation = fields[i]
					.getAnnotation(KmeanField.class);
			if (kmeansAnnotation != null) {
				fieldNames.add(fields[i].getName());
			}

		}

		initPlayers = new ArrayList<T>();
		for (int i = 0; i < k; i++) {
			initPlayers.add(players.get(i));
		}
	}

	public List<T>[] comput() {
		List<T>[] results = new ArrayList[k];

		boolean centerchange = true;
		while (centerchange) {
			centerchange = false;
			for (int i = 0; i < k; i++) {
				results[i] = new ArrayList<T>();
			}
			for (int i = 0; i < players.size(); i++) {
				T p = players.get(i);
				double[] dists = new double[k];
				for (int j = 0; j < initPlayers.size(); j++) {
					T initP = initPlayers.get(j);
					/* 计算距离 */
					double dist = distance(initP, p);
					dists[j] = dist;
				}

				int dist_index = computOrder(dists);
				results[dist_index].add(p);
			}

			for (int i = 0; i < k; i++) {
				T player_new = findNewCenter(results[i]);
				T player_old = initPlayers.get(i);
				if (!IsPlayerEqual(player_new, player_old)) {
					centerchange = true;
					initPlayers.set(i, player_new);
				}

			}

		}

		return results;
	}

	/**
	 * 比较是否两个对象是否属性一致
	 * 
	 * @param p1
	 * @param p2
	 * @return
	 */
	public boolean IsPlayerEqual(T p1, T p2) {
		if (p1 == p2) {
			return true;
		}
		if (p1 == null || p2 == null) {
			return false;
		}

		

		boolean flag = true;
		try {
			for (int i = 0; i < fieldNames.size(); i++) {
				String fieldName=fieldNames.get(i);
				String getName = "get"
						+ fieldName.substring(0, 1).toUpperCase()
						+ fieldName.substring(1);				
				Object value1 = invokeMethod(p1,getName,null);
				Object value2 = invokeMethod(p2,getName,null);
				if (!value1.equals(value2)) {
					flag = false;
					break;
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
			flag = false;
		}

		return flag;
	}

	/**
	 * 得到新聚类中心对象
	 * 
	 * @param ps
	 * @return
	 */
	public T findNewCenter(List<T> ps) {
		try {
			T t = classT.newInstance();
			if (ps == null || ps.size() == 0) {
				return t;
			}

			double[] ds = new double[fieldNames.size()];
			for (T vo : ps) {
				for (int i = 0; i < fieldNames.size(); i++) {
					String fieldName=fieldNames.get(i);
					String getName = "get"
							+ fieldName.substring(0, 1).toUpperCase()
							+ fieldName.substring(1);
					Object obj=invokeMethod(vo,getName,null);
					Double fv=(obj==null?0:Double.parseDouble(obj+""));
					ds[i] += fv;
				}

			}

			for (int i = 0; i < fieldNames.size(); i++) {
				ds[i] = ds[i] / ps.size();
				String fieldName = fieldNames.get(i);
				
				/* 给对象设值 */
				String setName = "set"
						+ fieldName.substring(0, 1).toUpperCase()
						+ fieldName.substring(1);

				invokeMethod(t,setName,new Class[]{double.class},ds[i]);

			}

			return t;
		} catch (Exception ex) {
			ex.printStackTrace();
		}
		return null;

	}

	/**
	 * 得到最短距离,并返回最短距离索引
	 * 
	 * @param dists
	 * @return
	 */
	public int computOrder(double[] dists) {
		double min = 0;
		int index = 0;
		for (int i = 0; i < dists.length - 1; i++) {
			double dist0 = dists[i];
			if (i == 0) {
				min = dist0;
				index = 0;
			}
			double dist1 = dists[i + 1];
			if (min > dist1) {
				min = dist1;
				index = i + 1;
			}
		}

		return index;
	}

	/**
	 * 计算距离(相似性) 采用欧几里得算法
	 * 
	 * @param p0
	 * @param p1
	 * @return
	 */
	public double distance(T p0, T p1) {
		double dis = 0;
		try {

			for (int i = 0; i < fieldNames.size(); i++) {
				String fieldName = fieldNames.get(i);
				String getName = "get"
						+ fieldName.substring(0, 1).toUpperCase()
						+ fieldName.substring(1);
				
				Double field0Value=Double.parseDouble(invokeMethod(p0,getName,null)+"");
				Double field1Value=Double.parseDouble(invokeMethod(p1,getName,null)+"");
				dis += Math.pow(field0Value - field1Value, 2); 
			}
		
		} catch (Exception ex) {
			ex.printStackTrace();
		}
		return Math.sqrt(dis);

	}
	
	/*------公共方法-----*/
	public Object invokeMethod(Object owner, String methodName,Class[] argsClass,
			Object... args) {
		Class ownerClass = owner.getClass();
		try {
			Method method=ownerClass.getDeclaredMethod(methodName,argsClass);
			return method.invoke(owner, args);
		} catch (SecurityException e) {
			e.printStackTrace();
		} catch (NoSuchMethodException e) {
			e.printStackTrace();
		} catch (Exception ex) {
			ex.printStackTrace();
		}

		return null;
	}

}


最后咱们测试一下:
package kmeans;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class TestMain {

	public static void main(String[] args) {
       List<Player> listPlayers=new ArrayList<Player>();
        
        for(int i=0;i<15;i++){
        	
        	Player p1=new Player();
        	p1.setName("afei-"+i);
        	p1.setAssists(i);
        	p1.setBackboard(i);
        	
        	//p1.setGoal(new Random(100*i).nextDouble());
        	p1.setGoal(i*10);
        	p1.setSteals(i);
        	//listPlayers.add(p1);	
        }
        
        Player p1=new Player();
        p1.setName("afei1");
        p1.setGoal(1);
        p1.setAssists(8);
        listPlayers.add(p1);
       
        Player p2=new Player();
        p2.setName("afei2");
        p2.setGoal(2);
        listPlayers.add(p2);
        
         Player p3=new Player();
        p3.setName("afei3");
        p3.setGoal(3);
        listPlayers.add(p3);
        
         Player p4=new Player();
        p4.setName("afei4");
        p4.setGoal(7);
        listPlayers.add(p4);
        
         Player p5=new Player();
        p5.setName("afei5");
        p5.setGoal(8);
        listPlayers.add(p5);
        
         Player p6=new Player();
        p6.setName("afei6");
        p6.setGoal(25);
        listPlayers.add(p6);
        
         Player p7=new Player();
        p7.setName("afei7");
        p7.setGoal(26);
        listPlayers.add(p7);
        
         Player p8=new Player();
        p8.setName("afei8");
        p8.setGoal(27);
        listPlayers.add(p8);
        
         Player p9=new Player();
        p9.setName("afei9");
        p9.setGoal(28);
        listPlayers.add(p9);
        
        
		Kmeans<Player> kmeans = new Kmeans<Player>(listPlayers,3);
		List<Player>[] results = kmeans.comput();
		for (int i = 0; i < results.length; i++) {
			System.out.println("===========类别" + (i + 1) + "================");
			List<Player> list = results[i];
			for (Player p : list) {
				System.out.println(p.getName() + "--->"
						+ p.getGoal() + "," + p.getAssists() + ","
						+ p.getSteals() + "," + p.getBackboard());
			}
		}
		
		
		
      
	}

}


结果如下


  这个里面涉及到相似度算法,事实证明欧几里得距离算法的实践效果是最优的。
  最后说说kmeans算法的不足:可以看到只能针对数字类型的属性(维),对于其他类型的除非选定合适的数值度量。


By 阿飞哥 转载请说明
腾讯微博:http://t.qq.com/duyunfeiRoom
新浪微博:http://weibo.com/u/1766094735

分享到:
评论
6 楼 ganminhui 2015-07-29  
我把代码复制上去,怎么测试结果都在一个分类里,根本没有起到聚类的效果
5 楼 hyywlz 2013-05-18  
小弟是新手 ,不知道怎么改,能具体告诉我怎么改吗?
4 楼 AngelAndAngel 2013-05-15  
KmeanField
hyywlz 写道
核心的Kmeans算法中
58   Annotation kmeansAnnotation = fields[i]  
59                    .getAnnotation(KmeanField.class); 
报这个错误:
Multiple markers at this line
- Type mismatch: cannot convert from KmeanField to Annotation
- Line breakpoint:Kmeans [line: 50] - Kmeans(List<T>, int)
- Bound mismatch: The generic method getAnnotation(Class<T>) of type AnnotatedElement is not applicable for the
arguments (Class<KmeanField>). The inferred type KmeanField is not a valid substitute for the bounded parameter <T extends  Annotation>
求解 不胜感激


KmeanField 这个是自定义注解
3 楼 hyywlz 2013-05-15  
核心的Kmeans算法中
58   Annotation kmeansAnnotation = fields[i]  
59                    .getAnnotation(KmeanField.class); 
报这个错误:
Multiple markers at this line
- Type mismatch: cannot convert from KmeanField to Annotation
- Line breakpoint:Kmeans [line: 50] - Kmeans(List<T>, int)
- Bound mismatch: The generic method getAnnotation(Class<T>) of type AnnotatedElement is not applicable for the
arguments (Class<KmeanField>). The inferred type KmeanField is not a valid substitute for the bounded parameter <T extends  Annotation>
求解 不胜感激
2 楼 hyywlz 2013-05-15  
核心的Kmeans算法中
58   Annotation kmeansAnnotation = fields[i]  
59                    .getAnnotation(KmeanField.class); 
报这个错误:
Multiple markers at this line
- Type mismatch: cannot convert from KmeanField to Annotation
- Line breakpoint:Kmeans [line: 50] - Kmeans(List<T>, int)
- Bound mismatch: The generic method getAnnotation(Class<T>) of type AnnotatedElement is not applicable for the
arguments (Class<KmeanField>). The inferred type KmeanField is not a valid substitute for the bounded parameter <T extends  Annotation>
求解 不胜感激
1 楼 hyywlz 2013-05-15  
核心的Kmeans算法中
58   Annotation kmeansAnnotation = fields[i]  
59                    .getAnnotation(KmeanField.class); 
报这个错误:
Multiple markers at this line
- Type mismatch: cannot convert from KmeanField to Annotation
- Line breakpoint:Kmeans [line: 50] - Kmeans(List<T>, int)
- Bound mismatch: The generic method getAnnotation(Class<T>) of type AnnotatedElement is not applicable for the
arguments (Class<KmeanField>). The inferred type KmeanField is not a valid substitute for the bounded parameter <T extends  Annotation>
求解 不胜感激

相关推荐

    java实现聚类算法,Kmeans

    K-means聚类算法是一种迭代求解的聚类分析算法,其步骤是随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象...

    kmeans聚类算法的java实现

    在Java中实现KMeans算法,我们可以利用编程语言的强大功能来处理大规模数据集,并将其应用于实际问题,如本例中的数据库字段分组。 1. **KMeans算法基本原理**: KMeans算法主要包含以下步骤: - 初始化:选择K个...

    kmeans聚类算法,kmeans聚类算法优缺点,matlab

    kMeans聚类算法是一种广泛应用的无监督机器学习方法,主要用于数据的分类和分组。它通过将数据点分配到最近的聚类中心来构建类别,然后更新这些中心以更好地反映其所属的数据点。这个过程会迭代进行,直到聚类中心...

    聚类经典程序kmeans的c++源码

    《KMeans算法的C++实现解析》 KMeans算法是一种广泛应用的数据聚类方法,它以其简单易懂和高效性在机器学习...通过理解和实现这个过程,我们可以更好地掌握聚类算法的核心思想,并将其应用到实际的数据分析任务中。

    C#实现简单的K-means聚类算法

    ### C# 实现简单的 K-means 聚类算法 #### 概述 K-means 是一种常用的无监督机器学习算法,主要用于数据聚类。它能够将数据集划分为K个簇(Cluster),使得每个数据点都属于离它最近的簇中心。在本文中,我们将...

    实验二 聚类算法_Kmeans_DBSCAN_matlab_聚类算法

    在本实验中,我们将深入探讨两种常用的聚类算法——K-Means和DBSCAN,并了解如何在MATLAB环境中实现它们。聚类是无监督学习的一种方法,主要用于发现数据集中的自然群体或类别,无需事先知道具体的分类信息。 **K-...

    机器学习领域,聚类算法,kmeans自动计算gap,自动确定k值

    机器学习领域涉及多种算法,其中聚类算法是一个重要分支,常见的聚类算法有kmeans,虽然原理简单,简单易用,但通常需要事先确定K值,k值选取与具体数据和业务场景紧密相关,一旦k值选取不合理会导致模型效果出现...

    详解Java实现的k-means聚类算法

    Java语言是实现k-means聚类算法的不二之选。 在学习k-means聚类算法之前,需要了解一些基本概念: 1. 聚类分析:聚类分析是指对数据进行分类,将相似的数据点聚类到一起,形成不同的簇。 2. 无监督学习:无监督...

    聚类算法 : Kmeans、Kmeans++、肘方法 - DBSCAN

    首先,K-means是最广泛应用的聚类算法之一,其基本思想是通过迭代将数据分配到K个预设的聚类中,以最小化各聚类内部的平方误差总和。K-means的工作流程包括选择初始质心、分配数据点到最近的质心对应的聚类、重新...

    大数据聚类算法与kmeans 算法综述

    KMeans算法作为最经典且广泛使用的无监督学习方法之一,是大数据聚类的首选工具。本文将深入探讨大数据聚类的概念、重要性以及KMeans算法的工作原理和应用。 大数据聚类是对大量、高维度数据进行分类的一种方法,...

    kmeans聚类算法,kmeans聚类算法优缺点,matlab源码.zip

    kMeans聚类算法是数据挖掘领域中广泛应用的一种无监督学习方法,主要用于将数据集中的样本点按照相似性划分到不同的类别或簇中。这个算法基于一个简单的核心思想:通过迭代优化,使得每个簇内的样本点尽可能接近,而...

    kmeans聚类算法,kmeans聚类算法优缺点,matlab源码.rar

    KMeans聚类算法是数据挖掘领域中广泛应用的一种无监督学习方法,主要用于将数据集划分成多个不重叠的类别或簇。它通过迭代的方式寻找数据的聚类中心,并将每个数据点分配到最近的聚类中心所在的簇。下面将详细介绍...

    聚类分析,kmeans聚类分析,输出聚类坐标点。matlab2021a测试仿真。

    这里提到的“k-means聚类分析”是聚类算法中的一种经典方法,它通过迭代寻找最佳的k个簇来对数据进行分类。 k-means算法的基本步骤如下: 1. 初始化:选择k个数据点作为初始的质心(cluster centers)。 2. 分配:...

    聚类算法与Kmeans代码_K-Means聚类_

    K-Means算法是其中最常用且理解简单的聚类算法之一。本篇将深入探讨K-Means算法及其代码实现,并对相关的Meanshift算法进行简单介绍。 ### K-Means算法原理 K-Means算法的目标是将数据集划分为K个不同的簇,使得每...

    聚类算法 实现Kmeans,DBSCAN以及谱聚类.zip

    聚类算法要把M个数据点按照分布分成K类(很多算法的K是人为提前设定的)。我们希望通过聚类算法得到 K个中心点,以及每个数据点属于哪个中心点的划分。 中心点可以通过迭代算法来找到,满足条件:所有的数据点到...

    mahout聚类算法

    Mahout 聚类算法可以分为多种类型,如 Canopy、KMeans、Fuzzy-KMeans、Spectral Clustering 等,每种算法都有其自己的特点和应用场景。 在 Mahout 聚类算法中,数据模型是数据的基本结构,它可以是 DenseVector、...

Global site tag (gtag.js) - Google Analytics