K-MEANS算法:
k-means 算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。
k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
具体如下:
输入:k, data[n];
(1) 选择k个初始中心点,例如c[0]=data[0],…c[k-1]=data[k-1];
(2) 对于data[0]….data[n], 分别与c[0]…c[n-1]比较,假定与c[i]差值最少,就标记为i;
(3) 对于所有标记为i点,重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数;
(4) 重复(2)(3),直到所有c[i]值的变化小于给定阈值。
算法实现起来应该很容易,就不帮你编写代码了。
1. 什么是 k-means 聚类算法?
从网上找到了很多定义,这里选取比较典型的几个;
K-Mean 分群法是一种分割式分群方法,其主要目标是要在大量高纬的资料点中找出
具有代表性的资料点;这些资料点可以称为群中心,代表点;然后再根据这些
群中心,进行后续的处理,这些处理可以包含
1 )资料压缩:以少数的资料点来代表大量的资料,达到资料压缩的功能;
2 )资料分类:以少数代表点来代表特点类别的资料,可以降低资料量及计算量;
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; i<len; i++) {
double 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; j<coord.length; j++) {
mCenter[j] += coord[j];// 得到每个纵向列的和;
}
f or (int i=0; i<mCenter.length; i++) {
mCenter[i] /= mCurrentSize; // 对每个纵向列取平均值
}
}
分享到:
相关推荐
java语言实现对mysql数据库表中某个字段实现k-means算法,并将处理后的数据写入新表
数据挖掘kmeans算法
KMeans算法是机器学习的经典算法,该文档实现了KMeans算法,文档中的数据是为了实现算法随机构造的。
java实现的kmeans聚类算法, 对某张表的某个字段进行kmeans聚类算法,并写到新创建的表中
前端react 后端springboot 数据库mysql
kmeans算法java源码工程简单实例,解压即可运行
用MapReduce实现KMeans算法,数据的读写都是在HDFS上进行的,在伪分布下运行没有问题。文档中有具体说明。
kmeans聚类java实现附测试数据及结果
java实现的文本聚类使用了kmeans算法
本代码 旨在演示kmeans的算法思想,以及将其应用到15个国家的世界杯排名分析中。
K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-...
包含两种平台上运行的kmeans算法:一种是在Hadoop系统上的并行化kmeans算法,支持读文件,执行聚类算法,输出质心文件,将每个数据的聚类信息输出到控制台上;另一种是串行的聚类算法,支持读文件数据,执行kmeans...
用java语言实现的kmeans算法,将n个点分成k个聚类。
java写的聚类程序,包括kmeans算法的实现. 部分java程序可以重用.
K均值算法java实现,最简单的聚类算法,适合高斯聚类
使用纯java实现KMeans模拟算法代码,随即撒点,计算K个聚类,使用了javaFX绘图工具包,结果有散点图的显示
Spark中机器学期(Machine Learning)之KMeans算法完整代码讲解
java语言实现kmeans算法,内含详细注释
Java是一种高性能、跨平台的面向对象编程语言。它由Sun Microsystems(现在是Oracle Corporation)的James Gosling等人在1995年推出,被设计为一种简单、健壮、可移植、多线程、动态的语言。Java的主要特点和优势...