共计 1854 个字符，预计需要花费 5 分钟才能阅读完成。
POCS：Projections onto Convex Sets。在数学中，凸集是指其中任意两点间的线段均在该汇合内的汇合。而投影则是将某个点映射到另一个空间中的某个子空间上的操作。给定一个凸汇合和一个点，能够通过找到该点在该凸汇合上的投影来进行操作。该投影是离该点最近的凸集内的点，能够通过最小化该点和凸集内任何其余点之间的间隔来计算。既然是投影，那么咱们就能够将特色映射到另一个空间中的凸汇合上，这样就能够进行聚类或降维等操作。
本文综述了一种基于凸集投影法的聚类算法，即基于 POCS 的聚类算法。原始论文公布在 IWIS2022 上。
凸集
凸集定义为一个数据点汇合，其中连贯汇合中任意两点 x1 和 x2 的线段齐全蕴含在这个汇合中。依据凸集的定义，认为空集∅、单集、线段、超平面、欧氏球都被认为是凸集。数据点也被认为是凸集，因为它是单例集（只有一个元素的汇合）。这为 POCS 的概念利用于聚类数据点开拓了一条新门路。
凸集投影(POCS)
POCS 办法大抵可分为交替式和并行式两种。
1、交替式 poc
从数据空间中的任意一点开始，从该点到两个 (或多个) 相交凸集的交替投影将收敛到汇合交点内的一点，例如下图：
当凸集不相交时，交替投影将收敛到依赖于投影阶数的 greedy limit cycles。
2、并行式 POCS
与交替模式不同，并行的 POCS 是从数据点到所有凸集同时进行投影，并且每个投影都有一个重要性权重。对于两个非空相交凸集，相似于交替式版本，平行投影会收敛到集相交处的一个点。
在凸集不相交的状况下，投影将收敛到一个最小解。基于 pocs 的聚类算法的次要思维来源于这一个性。
无关 POCS 的更多细节，能够查看原论文
基于 pocs 的聚类算法
利用并行 POCS 办法的收敛性，论文作者提出了一种非常简单但在肯定水平上无效的聚类算法。该算法的工作原理与经典的 K -Means 算法相似，但在解决每个数据点的形式上存在差别：K-Means 算法对每个数据点的重要性加权雷同，然而基于 pocs 的聚类算法对每个数据点的重要性加权不同，这与数据点到聚类原型的间隔成正比。
算法的伪代码如下所示:
试验后果
作者在一些公共基准数据集上测试了基于 pocs 的聚类算法的性能。下表总结了这些数据集的形容。
作者比拟了基于 pocs 的聚类算法与其余传统聚类办法的性能，包含 k 均值和含糊 c 均值算法。下表总结了执行工夫和聚类谬误方面的评估。
聚类后果如下图所示：
示例代码
咱们在一个非常简单的数据集上应用这个算法。作者曾经公布了间接应用的包，对于利用咱们能够间接应用：
pip install pocs-based-clustering创立一个以 10 个簇为核心的 5000 个数据点的简略数据集:
# Import packages
importtime
importmatplotlib.pyplotasplt
fromsklearn.datasetsimportmake_blobs
frompocs_based_clustering.toolsimportclustering
# Generate a simple dataset
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()执行聚类并显示后果:
# POSC-based Clustering Algorithm
centroids, labels=clustering(X, num_clusters, 100)
# Display results
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) 办法的聚类技术，称为基于 POCS 的聚类算法。该算法利用 POCS 的收敛个性利用于聚类工作，并在肯定水平上实现了可行的改良。在一些基准数据集上验证了该算法的有效性。
https://avoid.overfit.cn/post/bd811302f89c47fa8777c9f5bac8c59e
作者：LA Tran