譯者 | 朱先忠

審校 | 重樓

聚類分析（或聚類）是一種數(shù)據(jù)分析技術(shù)，它能夠探索和分組一組向量（或數(shù)據(jù)點），使同一聚類中的向量彼此之間比其他聚類中的向量更相似。聚類算法被廣泛應用于例如數(shù)據(jù)分析、模式識別和圖像處理等許多應用場景中。

本文將介紹一種新的基于凸集投影（POCS：Projection onto Convex Sets）方法的聚類算法，稱為基于POCS的聚類算法。最初的論文在IWIS2022中介紹，源代碼也已在Github上發(fā)布。

凸集定義與啟示

凸集被定義為一組數(shù)據(jù)點，其中連接該集合中任意兩個點x1和x2的線段完全包含在該集合中。根據(jù)凸集的定義，空集?、單例集、線段、超平面和歐氏球都被認為是凸集。數(shù)據(jù)點也被認為是凸集，因為它是單例集（一個只有一個元素的集合）。由這一概念啟示我們可發(fā)現(xiàn)一條新的研究路徑，即凸集投影的概念可以應用于聚類數(shù)據(jù)點。

凸集投影

首先，讓我們一起簡單回顧一下凸集投影的概念（沒有方程形式）。凸集投影的方法大致可以分為兩種形式：交替和平行。

交替凸集投影

從數(shù)據(jù)空間中的任意點開始，從該點到兩個（或多個）相交凸集的交替投影將收斂到集合的交點內(nèi)的一個點。下圖給出了相應的圖形化說明。

當凸集不相交時，交替投影將收斂到貪婪極限環(huán)，貪婪極限環(huán)取決于投影的階數(shù)。

平行凸集投影

與交替形式不同，并行形式的凸集投影同時執(zhí)行從數(shù)據(jù)點到所有凸集的投影，并且每個投影具有重要的權(quán)重。對于兩個非空相交凸集，類似于交替版本，平行投影收斂到集合的相交點。

在不相交凸集的情況下，投影將收斂到最小化解?；谕辜队暗木垲愃惴ǖ闹饕枷?/span>正是從這一性質(zhì)出發(fā)產(chǎn)生的。

有關(guān)凸集投影的更多詳細信息，您可以訪問原始論文和/或其他一些推薦論文（包括可用的pdf文件）：

• 模糊凸集上的交替投影
• 膨脹凸集投影：極小極大凸優(yōu)化

基于凸集投影方法的聚類算法

利用并行凸集投影方法的收斂性，作者提出了一種非常簡單但（在一定程度上）有效的聚類算法。該算法以類似于經(jīng)典K-Means算法的精神進行操作，但每個算法處理每個數(shù)據(jù)點的方式存在差異，即K-Means方法以相等的加權(quán)重要性處理每個數(shù)據(jù)點。然而，另一方面，基于凸集投影的聚類算法，以不同的重要性權(quán)重處理每個數(shù)據(jù)點，該重要性權(quán)重與從數(shù)據(jù)點到集群原型的距離成正比。

該算法的偽代碼如下所示：

實驗結(jié)果

作者們從網(wǎng)站聚類基本基準出發(fā)，在一些公共基準數(shù)據(jù)集上檢驗了基于凸集投影的聚類算法的性能。下表總結(jié)了這些數(shù)據(jù)集的描述。

在本文中，作者將基于凸集投影的聚類算法與其他傳統(tǒng)聚類方法（包括K-Means和模糊C-Means算法）的性能進行了比較。下表總結(jié)了針對執(zhí)行時間和集群錯誤方面的評估結(jié)果。

可視化聚類結(jié)果也如下圖所示：

有關(guān)更多詳細信息，您可以在此處查看原始論文。

示例代碼

讓我們在一個非常簡單的數(shù)據(jù)集上使用這個算法。為了簡單起見，可以使用以下命令安裝已發(fā)布的算法包：

pip install pocs-based-clustering

首先，讓我們導入幾個必要的包，并創(chuàng)建一個簡單的數(shù)據(jù)集，其中以10個集群為中心，周圍環(huán)繞著5000個數(shù)據(jù)點：

#導入包
import time
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from pocs_based_clustering.tools import clustering
# 生成一個簡單的數(shù)據(jù)集
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()

現(xiàn)在，使用內(nèi)置函數(shù)執(zhí)行聚類并顯示實驗結(jié)果：

# 基于凸集投影方法的聚類算法
centroids, labels = clustering(X, num_clusters, 100)
# 顯示結(jié)果
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é)論

在這篇文章中，我簡要回顧了一種基于凸集投影（POCS）方法的簡單而有效的聚類技術(shù)，稱為基于凸集投影的聚類算法。該算法利用凸集投影的收斂性將其應用于聚類任務，并在一定程度上實現(xiàn)了可行的改進。該算法的有效性已經(jīng)在一些基準數(shù)據(jù)集上得到了驗證。

原始論文可以在arXiv（預印本：https://arxiv.org/abs/2208.08888）或IEEE Xplore（已發(fā)表論文：https://ieeexplore.ieee.org/document/9920762）上找到。該代碼也在Github代碼倉庫網(wǎng)站上發(fā)布。

我很高興并歡迎您來到我的Facebook頁面分享有關(guān)機器學習的內(nèi)容：深入機器學習。我的其他值得您注意的帖子也可以在下面這些內(nèi)容中找到：

• EDN-GTM
• MetaFormer
• Darkeras
• EFPN：擴展特征金字塔網(wǎng)絡
• Data augmentation（數(shù)據(jù)增強）
• Data Distillation（數(shù)據(jù)蒸餾）
• 以及我的網(wǎng)頁中的其他文章。

譯者介紹

朱先忠，51CTO社區(qū)編輯，51CTO專家博客、講師，濰坊一所高校計算機教師，自由編程界老兵一枚。

原文標題：POCS-based Clustering Algorithm Explained，作者：LA Tran