k-medoids聚类算法实现
k-medoids聚类算法,即k-中心聚类算法,它是基于k-means聚类算法的改进。我们知道,k-means算法执行过程,首先需要随机选择初始质心,只有第一次随机选择的初始质心才是实际待聚类点集中的点,而后续将非质心点指派到对应的质心点后,重新计算得到的质心并非是待聚类点集中的点,而且如果某些非质心点是离群点的话,导致重新计算得到的质心可能偏离整个簇,为了解决这个问题,提出了改进的k-medoids聚类算法。
k-medoids聚类算法也是通过划分的方式来计算得到聚类结果,它使用绝对差值和(Sum of Absolute Differences,SAD)的度量来衡量聚类结果的优劣,在n维欧几里德空间中,计算SAD的公式如下所示:
围绕中心点划分(Partitioning Around Medoids,PAM)的方法是比较常用的,使用PAM方法进行处理,可以指定一个最大迭代次数的参数,在迭代过程中基于贪心策略来选择使得聚类的质量最高的划分。使用PAM的方法处理,每次交换一个中心点和非中心点,然后执行将非中心点指派到最近的中心点,计算得到的SAD值越小,则聚类质量越好,如此不断地迭代,直到找到一个最好的划分。
维基百科上给出的基于PAM方法计算聚类的过程,描述如下: 从待聚类的数据点集中随机选择k个点,作为初始中心点; 将待聚类的数据点集中的点,指派到最近的中心点; 进入迭代,直到聚类的质量满足指定的阈值(可以通过计算SAD),使总代价减少: 对每一个中心点o,对每一个非中心点p,执行如下计算步骤: 交换点o和p,重新计算交换后的该划分所生成的代价值; 如果本次交换造成代价增加,则取消交换。
上面算法描述,应该是按顺序的取遍中心点集合中的点,也从非中心点集合中取遍所有非中心点,分别计算生成的新划分的代价。由于待聚类的点集可大可小,我们可以考虑,每次取点的时候,采用随机取点的策略,随机性越强越好,只要满足最终迭代终止的条件即可。通常,如果能够迭代所有情况,那么最终得到的划分一定是最优的划分,即聚类结果最好,这通常适用于聚类比较小的点的集合。但是如果待聚类的点的集合比较大,则需要通过限制迭代次数来终止迭代计算,从而得到一个能够满足实际精度需要的聚类结果。
我们在下面实现k-medoids聚类算法,分别随机选择中心点和非中心点,对他们进行交换,通过设置允许最大迭代次数(maxIterations)这个参数值,来使聚类计算最后停止。
聚类算法实现
首先,为了便于理解后面的代码实现,我们描述一下代码实现聚类过程的基本步骤,如下所示:
输入待聚类点集,以及参数k、maxIterations、parallism; 同k-means算法一样,随机选择初始中心点集合; 启动parallism个线程,用来将非中心点指派给最近的中心点; 开始执行迭代,使得聚类结果对应的划分的SAD值最小: 将非中心点,基于Round-Robin策略,分配给多个线程,并行指派:将非中心点指派给距离其最近的中心点; 将多个线程指派的局部结果进行合并,得到一个全局的指派结果; 根据指派结果计算SAD值:如果是第一次进行指派,直接计算其SAD值,保存在previousSAD变量中,该变量保存的是最小的SAD值,第一次初始化第一次指派结果计算得到的SAD值;如果不是第一次进行指派,也计算SAD值,将SAD值保存在变量currentSAD中,继续执行步骤8; 随机选择一个非中心点; 创建一个ClusterHolder对象,该对象保存了该轮迭代指派结果,根据随机选择的非中心点修改ClusterHolder对象中的结果,将随机选择非中心点和对应的中心点进行交换,为下一轮指派过程准备数据; 最后,判断是否达到指定的最大迭代次数,如果达到则终止计算,处理最终聚类结果,否则执行下一轮迭代计算,转步骤5。我们实现的k-medoids聚类算法,需要指定2个聚类相关参数,另外一个参数是程序计算并行度,可以通过构造方法看到,代码如下所示:
public KMedoidsClustering(int k, int maxIterations, int parallism) {mergeMedoidAssignedResult(currentHolder); // 每个线程处理一部分,最后要合并多个线程分别处理的结果
RandomPoint randomPoint = selectNonCenterPointRandomly(currentHolder); // 随机选择一个非中心点
currentSAD = computeSAD(currentHolder); // // 计算用随机选择非中心点替换一个中心点得到的SAD值
if(currentSAD - previousSAD 0.0) { // 如果此次迭代得到的SAD值,比上次迭代计算得到SAD小,替换previousHolder和previousSAD,以保证最终算法终止后,该最小值对应的划分能够保留下来
currentHolder = constructNewHolder(currentHolder, randomPoint); // 根据随机选择的中心点,创建一个新的 ClusterHolde对象,用于下次迭代
LOG.info("Iteration #" + (++numIterations) + ": previousSAD=" + previousSAD + ", currentSAD=" + currentSAD);
Iterator Entry CenterPoint, List Point2D iter = previousHolder.medoidWithNearestPointSet.entrySet().iterator();
通过上面代码及其注释,我们可以了解到聚类实现的基本处理流程。首先,看一下工具类ClusterHolder和RandomPoint:
private class ClusterHolder {/** snapshot of clustering result: medoids of clustering result, as well as non-medoid points */
上面2个类,能够在迭代处理过程中,方便地保存当前迭代处理的数据状态。下面我们看一下,上面代码调用的比较重要的方法的实现逻辑。
并行将非中心点指派到最近的中心点将非中心点指派到最近的中心点的计算,是调用assignNearestMedoids方法,该方法的代码实现,如下所示:
private void assignNearestMedoids(final ClusterHolder holder, booleanfirstTimeToAssign) {if(firstTimeToAssign) { // 第一次进行指派,因为还没有进行指派过,所以只有随机选择的一组中心点,和全部待聚类的点的集合
holder.centerPoints.add(medoid.toPoint()); // 构造ClusterHolder对象,将中心点加入到集合中
for(Point2D p : allPoints) { // 对全部待聚类的点作为任务,加入到每个线程的队列中,但是要排除已经被选择为中心点的点
for(List Point2D points : holder.medoidWithNearestPointSet.values()) { // 如果笔试第一次进行指派,已经在构造ClusterHolder对象的时候,将随机选择的中心点和非中心点进行了交换,这里直接进行指派即可
上面代码调用selectSeeker()方法,获取到一个NearestMedoidSeeker线程,将待指派的点加入到其队列中,然后由该线程去异步循环处理。selectSeeker()方法实现代码,如下所示:
private NearestMedoidSeeker selectSeeker() {下面,我们看一下NearestMedoidSeeker线程的实现,它也比较简单,实现了从队列q中将非中心点取出,计算到该点最近的中心点,然后指派给该中心点,线程实现代码如下所示:
private class NearestMedoidSeeker implements Runnable {Double distance = distanceCache.computeDistance(p1, p2); // 计算非中心点p1到中心点p2的欧几里德距离
每一轮指派,多个线程都计算得到一个非中心点指派到最近中心点的子集,最后还要将这些子集合并为一个全局的指派结果,即得到距离每个中心点最近的非中心点的集合,合并的实现在mergeMedoidAssignedResult()方法中,代码如下所示:
private void mergeMedoidAssignedResult(ClusterHolder currentHolder) {Iterator Entry CenterPoint, List Point2D iter = seeker.clusteringNearestPoints.entrySet().iterator();
合并后的指派结果,都存放在ClusterHolder对象中,为下一轮迭代准备了数据。
随机选择中心点和非中心点随机选择一个中心点和非中心点,实现代码如下所示:
private RandomPoint selectNonCenterPointRandomly(ClusterHolder holder) {List CenterPoint medoids = new ArrayList CenterPoint (holder.medoidWithNearestPointSet.keySet());
CenterPoint selectedMedoid = medoids.get(random.nextInt(medoids.size())); // 随机选择一个中心点
Point2D point = belongingPoints.get(random.nextInt(belongingPoints.size())); // 随机选择一个非中心点
因为每一次迭代,我们都得到一个非中心点指派到最近的中心点的聚类结果集合,所以在设计随机选择中心点和非中心点进行交换时,我们首先从中心点集合中选择一个中心点,然后再从该中心点对应的非中心点的簇的集合中选择一个非中心点,当然也可以考虑用其他的方法,比如,在一次迭代过程中,待交换的中心点和非中心点不在同一个簇中。
创建ClusterHolder对象,交换非中心点和中心点我们处理的策略是,事后处理,也就是每次先实现非中心点和中心点的交换,再进行指派,计算SAD值,如果此轮迭代得到的SAD值比上一轮的大,则直接丢弃结果,将上一轮的指派结果作为最终候选结果,直到最后,保留着具有最小SAD值的指派结果。
交换中心点和非中心点,我们创建了一个ClusterHolder对象,然后在该对象所持有的集合上进行修改贾环。交换非中心点和中心点的实现代码,如下所示:
// create a new center point with type CenterPoint based on the randomly selected non-medoid point
newHolder.medoids.remove(oldMedoid); // remove old medoid from center point set of new holder object
oldPoints.remove(newPoint); // remove new randomly selected non-medoid point from previous result set of clustering
为了保留上一次迭代指派的结果,这里不要修改holder对应的结果的集合(holder是本次迭代得到的聚类结果),而是拷贝出一份,在拷贝的结果上交换中心点和非中心点。
聚类效果对比
我们分别使用k-medoids算法与k-means算法对同一个点集进行聚类,分别对结果进行比较。其中,k-means算法由于随机选择初始质心,每次执行聚类结果不同;而k-medoids算法的聚类结果质量依赖于迭代次数,所以我们选择不同的迭代次数:取值maxIterations分别为300、1000、3000时,对比效果,如下图所示:
上图中,第一排3个图是k-means聚类得到的3个结果,第二排是k-medoids聚类得到的结果。通过上图可以看出,使用k-medoids聚类算法,当maxIterations越大的时候,可能更加靠近最优解,聚类结果的质量越高,此时对应的质量的度量SAD的值就越小。
聚类 聚类就是把数据对象集合按照相似性划分成多个子集的过程(如下图)。其中,每个子集称为一个簇。聚类不仅要使簇中的对象彼此相似,而且要与其他簇中的对象相似**。聚类是无监督学习,数据不需要类标号(标注)信息。
相关文章
- Java实现 蓝桥杯 算法训练 数据交换
- Java实现 蓝桥杯 算法训练 景点游览
- java实现 蓝桥杯 算法训练 Password Suspects
- Java实现 蓝桥杯VIP 算法提高 多项式输出
- Java实现 蓝桥杯VIP 算法提高 企业奖金发放
- Java实现 蓝桥杯VIP 算法提高 不同单词个数统计
- Java实现 蓝桥杯VIP 算法提高 扫雷
- Java实现 蓝桥杯VIP 算法训练 整除问题
- Java实现 蓝桥杯VIP 算法训练 整数平均值
- Java实现 蓝桥杯VIP 算法训练 暗恋
- Java实现 蓝桥杯 算法提高 拿糖果
- Java实现 蓝桥杯 算法训练 矩阵乘法
- Java实现 蓝桥杯 算法训练 区间k大数
- 朴素贝叶斯算法的python实现方法
- (算法)稳定婚姻匹配
- PCL 改进的RANSAC算法实现点云粗配准
- 【快速乘、快速幂】快速乘算法和快速幂算法的思想及其代码实现
- ML之KG:基于MovieLens电影评分数据集利用基于知识图谱的推荐算法(networkx+基于路径相似度的方法)实现对用户进行Top电影推荐案例
- 【风场景生成与削减】【m-ISODATA、kmean、HAC】无监督聚类算法,用于捕获电力系统中风场景生成与削减研究(Matlab代码实现)
- 【风光场景生成】基于改进ISODATA的负荷曲线聚类算法(Matlab代码实现)
- 【乳腺癌诊断】基于聚类和遗传模糊算法乳腺癌(诊断)分析(Matlab代码实现)
- (Matlab实现)K-means算法及最佳聚类数目的确定
- 【DL】2023年你应该知道的 10 大深度学习算法
- Python实现随机分布式延迟PSO优化算法(RODDPSO)优化KMeans聚类模型项目实战
- 【架构实践】一致性Hash算法原理图文详解 & 使用 golang 实现
- 聚类算法之BIRCH(Java实现)转载
- java 实现DBScan聚类算法
- 聚类算法之DBScan(Java实现)
- Crawler/ML:爬虫技术(基于urllib.request库从网页获取图片)+HierarchicalClustering层次聚类算法,实现自动从网页获取图片然后根据图片色调自动分类
- 基于智能优化算法PSO/GWO/AFO+柔性车间生产调度(Matlab代码实现)
- 机器学习算法一之基于K均值聚类算法实现数据聚类及二维图像像素分割
- 机器学习算法二之DBSCAN聚类原理与实现(二维及三维)