审校 | 重楼
聚类分析(或聚类)是一种数据分析技术,它能够探索和分组一组向量(或数据点),使同一聚类中的向量彼此之间比其他聚类中的向量更相似。聚类算法被广泛应用于例如数据分析、模式识别和图像处理等许多应用场景中。
本文将介绍一种新的基于凸集投影(POCS:Projection onto Convex Sets)方法的聚类算法,称为基于POCS的聚类算法。最初的论文在IWIS2022中介绍,源代码也已在Github上发布。
凸集定义与启示
凸集被定义为一组数据点,其中连接该集合中任意两个点x1和x2的线段完全包含在该集合中。根据凸集的定义,空集∅、单例集、线段、超平面和欧氏球都被认为是凸集。数据点也被认为是凸集,因为它是单例集(一个只有一个元素的集合)。由这一概念启示我们可发现一条新的研究路径,即凸集投影的概念可以应用于聚类数据点。
凸集投影
首先,让我们一起简单回顾一下凸集投影的概念(没有方程形式)。凸集投影的方法大致可以分为两种形式:交替和平行。
交替凸集投影
从数据空间中的任意点开始,从该点到两个(或多个)相交凸集的交替投影将收敛到集合的交点内的一个点。下图给出了相应的图形化说明。
当凸集不相交时,交替投影将收敛到贪婪极限环,贪婪极限环取决于投影的阶数。
平行凸集投影
与交替形式不同,并行形式的凸集投影同时执行从数据点到所有凸集的投影,并且每个投影具有重要的权重。对于两个非空相交凸集,类似于交替版本,平行投影收敛到集合的相交点。
在不相交凸集的情况下,投影将收敛到最小化解。基于凸集投影的聚类算法的主要思想正是从这一性质出发产生的。
有关凸集投影的更多详细信息,您可以访问原始论文和/或其他一些推荐论文(包括可用的pdf文件):
基于凸集投影方法的聚类算法
利用并行凸集投影方法的收敛性,作者提出了一种非常简单但(在一定程度上)有效的聚类算法。该算法以类似于经典K-Means算法的精神进行操作,但每个算法处理每个数据点的方式存在差异,即K-Means方法以相等的加权重要性处理每个数据点。然而,另一方面,基于凸集投影的聚类算法,以不同的重要性权重处理每个数据点,该重要性权重与从数据点到集群原型的距离成正比。
该算法的伪代码如下所示:
实验结果
作者们从网站聚类基本基准出发,在一些公共基准数据集上检验了基于凸集投影的聚类算法的性能。下表总结了这些数据集的描述。
在本文中,作者将基于凸集投影的聚类算法与其他传统聚类方法(包括K-Means和模糊C-Means算法)的性能进行了比较。下表总结了针对执行时间和集群错误方面的评估结果。
可视化聚类结果也如下图所示:
有关更多详细信息,您可以在此处查看原始论文。
示例代码
让我们在一个非常简单的数据集上使用这个算法。为了简单起见,可以使用以下命令安装已发布的算法包:
pip install pocs-based-clustering
首先,让我们导入几个必要的包,并创建一个简单的数据集,其中以10个集群为中心,周围环绕着5000个数据点:
#导入包
import time
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from pocs_based_clustering.tools import clustering
# 生成一个简单的数据集
num_clusters = 10
X, y = make_blobs(n_samples=5000, centers=num_clusters, \
cluster_std=0.5, random_state=0)
plt.figure(figsize=(8,8))
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.show()
现在,使用内置函数执行聚类并显示实验结果:
# 基于凸集投影方法的聚类算法
centroids, labels = clustering(X, num_clusters, 100)
# 显示结果
plt.figure(figsize=(8,8))
plt.scatter(X[:, 0], X[:, 1], c=labels, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], s=100, c='red')
plt.show()
结论
在这篇文章中,我简要回顾了一种基于凸集投影(POCS)方法的简单而有效的聚类技术,称为基于凸集投影的聚类算法。该算法利用凸集投影的收敛性将其应用于聚类任务,并在一定程度上实现了可行的改进。该算法的有效性已经在一些基准数据集上得到了验证。
原始论文可以在arXiv(预印本:https://arxiv.org/abs/2208.08888)或IEEE Xplore(已发表论文:https://ieeexplore.ieee.org/document/9920762)上找到。该代码也在Github代码仓库网站上发布。
我很高兴并欢迎您来到我的Facebook页面分享有关机器学习的内容:深入机器学习。我的其他值得您注意的帖子也可以在下面这些内容中找到:
- EDN-GTM
- MetaFormer
- Darkeras
- EFPN:扩展特征金字塔网络
- Data augmentation(数据增强)
- Data Distillation(数据蒸馏)
- 以及我的网页中的其他文章。
译者介绍
朱先忠,51CTO社区编辑,51CTO专家博客、讲师,潍坊一所高校计算机教师,自由编程界老兵一枚。
原文POCS-based Clustering Algorithm Explained,作者:LA Tran