程序猿成长之路之数据挖掘篇——Kmeans聚类算法

2024-08-25 17:28
文章标签 算法 程序 之路 聚类 数据挖掘 成长 kmeans

本文主要是介绍程序猿成长之路之数据挖掘篇——Kmeans聚类算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Kmeans 是一种可以将一个数据集按照距离（相似度）划分成不同类别的算法，它无需借助外部标记，因此也是一种无监督学习算法。

什么是聚类

用官方的话说聚类就是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程。用自己的话说聚类是根据不同样本数据间的相似度进行种类划分的算法。这种划分可以基于我们的业务需求或建模需求来完成，也可以单纯地帮助我们探索数据的自然结构和分布。

什么是K-means聚类

用官方的话说：k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

K-means聚类实现流程在这里插入图片描述

K-means聚类聚类的优劣性

优点：

  1. K-means聚类可以支持无监督学习，无需人工标记即可进行分类
  2. K-means聚类有处理不同类型数据的能力，如二元、序数、标称、数值等类型数据都可以处理。
  3. K-means聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

缺点：

  1. 需要提前确定几何中心的数量
  2. 设置初始几何中心需要考虑尽可能选取差异较大的数据作为初始几何中心
  3. 适用于有明显中心的数据样本，对于相对分散的数据样本处理效果欠佳。

典型案例

学校A有若干不同年龄分布的学生，并且性别也不一样，想要依据这两个参数对学生进行分类。

学生类

import java.util.List;public class Student{@Overridepublic String toString() {return "Student [name=" + name + ", age=" + age + ", gender=" + gender + ", myHobby=" + myHobby+ ", myDream=" + myDream + "]";}public List<MyHobby> getMyHobby() {return myHobby;}public Student setMyHobby(List<MyHobby> myHobby) {this.myHobby = myHobby;return this;}public String getName() {return name;}public Student setName(String name) {this.name = name;return this;}public int getAge() {return age;}public Student setAge(int age) {this.age = age;return this;}public String getGender() {return gender;}public Student setGender(String gender) {this.gender = gender;return this;}String name;@Elem(type = ElemType.NUMBER)int age;@Elem(type = ElemType.XUSHU,list={"男","女"})String gender;@Elem()List<MyHobby> myHobby;@Elem()List<String> myDream;public Student(String name, int age, String gender) {super();this.name = name;this.age = age;this.gender = gender;}public Student(String name, int age, String gender,List<MyHobby> myHobby) {this(name,age,gender);this.myHobby = myHobby;}public Student(String name, int age, String gender,List<MyHobby> myHobby, List<String> myDreams) {this(name,age,gender);this.myHobby = myHobby;this.myDream = myDreams;}
}

配置类

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
public @interface Elem {ElemType type() default ElemType.BASIC; //属性类型String[] list() default {}; //选择项
}
package kmeans;
/*** 元素属性类型（标称属性、序数属性、数值属性、二元属性）* @author zygswo**/
public enum ElemType {BASIC("标称属性"),XUSHU("序数属性"),NUMBER("数值属性"),ERYUAN("二元属性");private String name;private ElemType(String name) {this.setName(name);}public String getName() {return name;}public void setName(String name) {this.name = name;}
}
package kmeans;public enum DistanceType {EUCLID("欧几里得距离"),MANHATTAN("曼哈顿距离"),QIEBIXUEFU("切比雪夫距离");private String name;private DistanceType(String name) {this.setName(name);}public String getName() {return name;}public void setName(String name) {this.name = name;}
}

主方法

package kmeans;import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;/*** kmeans聚类工具类* @author zygswo**/
public class KmeansUtils<T> {private int initKNodeNb; //kmeans初始几何中心数量private List<T> trainData; //kmeans训练数据private DistanceType distanceType;/*** kmeans构造方法(默认为欧式距离公式）* @param initKNodeNb kmeans初始几何中心数量* @param trainData	训练数据*/public KmeansUtils(List<T> trainData, int initKNodeNb) {this.initKNodeNb = initKNodeNb;this.trainData = trainData;this.distanceType = DistanceType.EUCLID;}/*** kmeans构造方法(默认为欧式距离公式）* @param initKNodeNb kmeans初始几何中心数量* @param trainData	训练数据* @param distanceType 距离公式*/public KmeansUtils(List<T> trainData, int initKNodeNb, DistanceType distanceType) {this.initKNodeNb = initKNodeNb;this.trainData = trainData;this.distanceType = distanceType;}/*** kmeans模型训练*/public void fit(){//计算距离List<Map<String,Double>> initKNodeDistanceVal = Collections.synchronizedList(new ArrayList<>());//初始化几何列表List<List<T>> resList = Collections.synchronizedList(new ArrayList<>());if (this.trainData == null || this.trainData.isEmpty()) {throw new IllegalArgumentException("训练集为空");}if (this.initKNodeNb <=0) {throw new IllegalArgumentException("几何中心数量小于0");}if (this.initKNodeNb > this.trainData.size()) {throw new IllegalArgumentException("几何中心数量超过数组数量");}if (this.distanceType == null) {throw new IllegalArgumentException("距离类型为空");}//1.获取前initKNodeNb个数据放入initKNodeList列表中//初始化的几何中心，需要选择差异较大的this.trainData.sort((T item1,T item2)-> {return (int)(calcDiff(item1,this.trainData.get(0)) - calcDiff(item2,this.trainData.get(0)));});int step = this.trainData.size() / initKNodeNb;//选择从小到大的initKNodeNb个元素作为初始几何for (int i = 0; i < this.trainData.size() && resList.size() < initKNodeNb; i+=step) {List<T> temp = Collections.synchronizedList(new ArrayList<>());temp.add(this.trainData.get(i));resList.add(temp); //多个几何列表设置初始结点}//2.计算所有变量到不同的几何中心距离,如果稳定了(几何中心固定了)，就退出循环while(true) {boolean balanced = true; //是否已经平衡for (T item: this.trainData) {double distance, minDistance = Double.MAX_VALUE; //求最小距离int preIndex = 0,afterIndex = 0; //preIndex-原位置initKNodeDistanceVal.clear();
//				for (List<T> list : resList) {
//					System.out.println(list.toString());
//				}//计算几何中心for (int i = 0; i < initKNodeNb; i++) {if (resList.get(i).size() > 0)initKNodeDistanceVal.add(calc(resList.get(i))); //计算初始结点距离}//计算原来的位置for (int i = 0; i < initKNodeNb; i++) {if(resList.get(i).contains(item)) {preIndex = i;break;}}
//				System.out.println("item = " + item.toString());//计算不同变量到不同的几何中心距离for (int i = 0; i < initKNodeNb; i++) {if (resList.get(i).size() > 0 && i < initKNodeDistanceVal.size()) {distance = calcDistance(item, initKNodeDistanceVal.get(i));
//						System.out.println("distance = " + distance);
//						System.out.println("minDistance = " + minDistance);if (distance < minDistance) {minDistance = distance;afterIndex = i;}}					}
//				System.out.println("preIndex = " + preIndex);
//				System.out.println("afterIndex = " + afterIndex);//位置替换,如果替换就还没结束if (preIndex != afterIndex) {resList.get(preIndex).remove(item);resList.get(afterIndex).add(item);balanced = false;} if (preIndex == afterIndex) {//如果新增就还没结束if (!resList.get(preIndex).contains(item)) {resList.get(preIndex).add(item);balanced = false;}}}if (balanced){break;}}
//		//打印结果for (List<T> list : resList) {System.out.println(list.toString());}}/*** 计算距离* @param item1 item1* @param item2 item2* @return*/private double calcDiff(T item1, T item2) {List<T> list = Collections.synchronizedList(new ArrayList<>());list.add(item2);Map<String, Double> map = calc(list);double dist = calcDistance(item1, map);return dist;}
/*** 计算距离* @param item 当前对象* @param map 几何中心* @return*/private double calcDistance(T item, Map<String, Double> map) {double distance = 0.0;//距离int level = 0;//根据距离公式判断距离计算等级Class<?> cls = item.getClass();Field[] fs = cls.getDeclaredFields();for (Field f : fs) {double dist1 = 0.0, dist2 = 0.0;f.setAccessible(true);//获取需要计算的参数Elem el = f.getAnnotation(Elem.class);if (el == null) {continue;}try {switch(el.type()) {case BASIC: break;case XUSHU://获取数组String[] arr = el.list();if (arr == null) {throw new IllegalArgumentException("序数属性需配置属性集合数组");}//数组排序Arrays.sort(arr);List<String> list = Arrays.asList(arr);//计算差距步长Double diffStep = 1 / (list.size() * 1.0);//获取当前对象序数属性的值Object value = f.get(item);dist1 = list.indexOf(value) * diffStep;break;case NUMBER: //获取当前对象数值属性的值Object value1 = f.get(item); //数据转换Double intVal = Double.parseDouble(String.valueOf(value1));dist1 = intVal;break;case ERYUAN://获取数组String[] arr1 = el.list();if (arr1 == null) {arr1 = new String[]{"0","1"};} else {//数组排序Arrays.sort(arr1);}//转列表List<String> list1 = Arrays.asList(arr1);//计算差距步长Double diffStep1 = 1 / (list1.size() * 1.0);Object value2 = f.get(item);int ind = list1.indexOf(value2);dist1 = ind * diffStep1;break;}//获取当前几何中心属性的值dist2 = map.get(f.getName());//计算距离switch(distanceType) {case EUCLID: level = 2; break;case MANHATTAN: level = 1;break;case QIEBIXUEFU: level = 100;break;}distance += Math.pow(Math.abs(dist1 - dist2),level);} catch(Exception ex) {throw new RuntimeException(ex.getMessage());}distance = Math.pow(distance, 1/(level * 1.0));}	return distance;}/*** 计算几何中心坐标* @param kNodeList* @return 几何中心坐标map*/private Map<String, Double> calc(List<T> kNodeList) {if (kNodeList == null || kNodeList.size() <= 0) {throw new IllegalArgumentException("几何中心列表数组为空");}//反射获取参数,形成数值数组Map<String, Double> result = new ConcurrentHashMap<>();T item = kNodeList.get(0);Class<?> cls = item.getClass();Field[] fs = cls.getDeclaredFields();for (Field f: fs) {//获取需要计算的参数Elem el = f.getAnnotation(Elem.class);if (el == null) {continue;}//将数据转换成数值Double dist = 0.0;switch(el.type()) {case BASIC: break;case XUSHU: //获取数组String[] arr = el.list();if (arr == null) {throw new IllegalArgumentException("序数属性需配置属性集合数组");}//数组排序Arrays.sort(arr);//转列表List<String> list = Arrays.asList(arr);//计算差距步长Double diffStep = 1 / (list.size() * 1.0);for (T kNode : kNodeList) {try {//获取当前对象序数属性的值Object value = f.get(kNode);int ind = list.indexOf(value);//求和dist += ind * diffStep;} catch (IllegalArgumentException e) {// TODO Auto-generated catch blocke.printStackTrace();} catch (IllegalAccessException e) {// TODO Auto-generated catch blocke.printStackTrace();}}break;case NUMBER: for (T kNode : kNodeList) {try {//获取当前对象数值属性的值Object value = f.get(kNode);//数据转换Double intVal = Double.parseDouble(String.valueOf(value));dist += intVal;} catch (IllegalArgumentException e) {// TODO Auto-generated catch blocke.printStackTrace();} catch (IllegalAccessException e) {// TODO Auto-generated catch blocke.printStackTrace();}}break;case ERYUAN://获取数组String[] arr1 = el.list();if (arr1 == null) {arr1 = new String[]{"0","1"};} else {//数组排序Arrays.sort(arr1);}//转列表List<String> list1 = Arrays.asList(arr1);//计算差距步长Double diffStep1 = 1 / (list1.size() * 1.0);for (T kNode : kNodeList) {try {//获取当前对象二元属性的值Object value = f.get(kNode);int ind = list1.indexOf(value);//求和dist += ind * diffStep1;} catch (IllegalArgumentException e) {// TODO Auto-generated catch blocke.printStackTrace();} catch (IllegalAccessException e) {// TODO Auto-generated catch blocke.printStackTrace();}}break;}dist /= (kNodeList.size() * 1.0); //求平均值result.put(f.getName(), dist);}return result;}public static void main(String[] args) {List<Student> trainData = new ArrayList<>();trainData.add(new Student("zyl",28,"男"));trainData.add(new Student("sjl",28,"女"));trainData.add(new Student("xxx",27,"男"));trainData.add(new Student("stc",30,"男"));trainData.add(new Student("wxq",30,"女"));trainData.add(new Student("zzz",27,"男"));trainData.add(new Student("sss",27,"女"));trainData.add(new Student("mmm",20,"男"));trainData.add(new Student("qqq",20,"女"));trainData.add(new Student("666",30,"男"));
//		trainData.add(new Student("mmm",19,"男"));KmeansUtils<Student> utils = new KmeansUtils<>(trainData, 4);utils.fit();}
}

运行结果
在这里插入图片描述

这篇关于程序猿成长之路之数据挖掘篇——Kmeans聚类算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1106183。

相关文章

springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何用java对接微信小程序下单后的发货接口

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》：本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
基于Python开发PDF转Doc格式小程序

基于Python开发PDF转Doc格式小程序

《基于Python开发PDF转Doc格式小程序》这篇文章主要为大家详细介绍了如何基于Python开发PDF转Doc格式小程序,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用python实现PDF转Doc格式小程序以下是一个使用Python实现PDF转DOC格式的GUI程序，采用T
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
将java程序打包成可执行文件的实现方式

将java程序打包成可执行文件的实现方式

《将java程序打包成可执行文件的实现方式》本文介绍了将Java程序打包成可执行文件的三种方法：手动打包（将编译后的代码及JRE运行环境一起打包）,使用第三方打包工具（如Launch4j）和JDK自带... 目录1.问题提出2.如何将Java程序打包成可执行文件2.1将编译后的代码及jre运行环境一起打包2
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
在不同系统间迁移Python程序的方法与教程

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术（如Docker）、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术（如 docker）1. 创
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2