POCS：Projections  onto Convex Sets。在數(shù)學(xué)中，凸集是指其中任意兩點(diǎn)間的線段均在該集合內(nèi)的集合。而投影則是將某個(gè)點(diǎn)映射到另一個(gè)空間中的某個(gè)子空間上的操作。給定一個(gè)凸集合和一個(gè)點(diǎn)，可以通過(guò)找到該點(diǎn)在該凸集合上的投影來(lái)進(jìn)行操作。該投影是離該點(diǎn)最近的凸集內(nèi)的點(diǎn)，可以通過(guò)最小化該點(diǎn)和凸集內(nèi)任何其他點(diǎn)之間的距離來(lái)計(jì)算。既然是投影，那么我們就可以將特征映射到另一個(gè)空間中的凸集合上，這樣就可以進(jìn)行聚類或降維等操作。

本文綜述了一種基于凸集投影法的聚類算法，即基于POCS的聚類算法。原始論文發(fā)布在IWIS2022上。

凸集

凸集定義為一個(gè)數(shù)據(jù)點(diǎn)集合，其中連接集合中任意兩點(diǎn)x1和x2的線段完全包含在這個(gè)集合中。根據(jù)凸集的定義，認(rèn)為空集?、單集、線段、超平面、歐氏球都被認(rèn)為是凸集。數(shù)據(jù)點(diǎn)也被認(rèn)為是凸集，因?yàn)樗菃卫ㄖ挥幸粋€(gè)元素的集合）。這為 POCS 的概念應(yīng)用于聚類數(shù)據(jù)點(diǎn)開(kāi)辟了一條新路徑。

凸集投影(POCS)

POCS方法大致可分為交替式和并行式兩種。

1、交替式poc

從數(shù)據(jù)空間中的任意一點(diǎn)開(kāi)始，從該點(diǎn)到兩個(gè)(或多個(gè))相交凸集的交替投影將收斂到集合交點(diǎn)內(nèi)的一點(diǎn)，例如下圖：

當(dāng)凸集不相交時(shí)，交替投影將收斂到依賴于投影階數(shù)的greedy limit cycles。

2、并行式 POCS

與交替形式不同，并行的POCS 是從數(shù)據(jù)點(diǎn)到所有凸集同時(shí)進(jìn)行投影，并且每個(gè)投影都有一個(gè)重要性權(quán)重。對(duì)于兩個(gè)非空相交凸集，類似于交替式版本，平行投影會(huì)收斂到集相交處的一個(gè)點(diǎn)。

在凸集不相交的情況下，投影將收斂到一個(gè)最小解?；趐ocs的聚類算法的主要思想來(lái)源于這一特性。

有關(guān)POCS的更多細(xì)節(jié)，可以查看原論文

基于pocs的聚類算法

利用并行POCS方法的收斂性，論文作者提出了一種非常簡(jiǎn)單但在一定程度上有效的聚類算法。該算法的工作原理與經(jīng)典的K-Means算法類似，但在處理每個(gè)數(shù)據(jù)點(diǎn)的方式上存在差異：K-Means算法對(duì)每個(gè)數(shù)據(jù)點(diǎn)的重要性加權(quán)相同，但是基于pocs的聚類算法對(duì)每個(gè)數(shù)據(jù)點(diǎn)的重要性加權(quán)不同，這與數(shù)據(jù)點(diǎn)到聚類原型的距離成正比。

算法的偽代碼如下所示:

實(shí)驗(yàn)結(jié)果

作者在一些公共基準(zhǔn)數(shù)據(jù)集上測(cè)試了基于pocs的聚類算法的性能。下表總結(jié)了這些數(shù)據(jù)集的描述。

作者比較了基于pocs的聚類算法與其他傳統(tǒng)聚類方法的性能，包括k均值和模糊c均值算法。下表總結(jié)了執(zhí)行時(shí)間和聚類錯(cuò)誤方面的評(píng)估。

聚類結(jié)果如下圖所示：

示例代碼

我們?cè)谝粋€(gè)非常簡(jiǎn)單的數(shù)據(jù)集上使用這個(gè)算法。作者已經(jīng)發(fā)布了直接使用的包，對(duì)于應(yīng)用我們可以直接使用：

pip install pocs-based-clustering

創(chuàng)建一個(gè)以10個(gè)簇為中心的5000個(gè)數(shù)據(jù)點(diǎn)的簡(jiǎn)單數(shù)據(jù)集:

# Import packages
 import time
 import matplotlib.pyplot as plt
 
 from sklearn.datasets import make_blobs
 from pocs_based_clustering.tools import clustering
 
 
 # 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()

執(zhí)行聚類并顯示結(jié)果:

# 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()

總結(jié)

我們簡(jiǎn)要回顧了一種簡(jiǎn)單而有效的基于投影到凸集(POCS)方法的聚類技術(shù)，稱為基于POCS的聚類算法。該算法利用POCS的收斂特性應(yīng)用于聚類任務(wù)，并在一定程度上實(shí)現(xiàn)了可行的改進(jìn)。在一些基準(zhǔn)數(shù)據(jù)集上驗(yàn)證了該算法的有效性。

論文的地址如下：https://arxiv.org/abs/2208.08888

作者發(fā)布的源代碼在這里：https://github.com/tranleanh/pocs-based-clustering