譯者 | 朱先忠
審校 | 重樓
聚類分析（或聚類）是一種數據分析技術，它能夠探索和分組一組向量（或數據點），使同一聚類中的向量彼此之間比其他聚類中的向量更相似。聚類算法被廣泛應用于例如數據分析、模式識別和圖像處理等許多應用場景中。
本文將介紹一種新的基于凸集投影（POCS：Projection onto Convex Sets）方法的聚類算法，稱為基于POCS的聚類算法。最初的論文在IWIS2022中介紹，源代碼也已在Github上發布。
凸集定義與啟示
凸集被定義為一組數據點，其中連接該集合中任意兩個點x1和x2的線段完全包含在該集合中。根據凸集的定義，空集?、單例集、線段、超平面和歐氏球都被認為是凸集。數據點也被認為是凸集，因為它是單例集（一個只有一個元素的集合）。由這一概念啟示我們可發現一條新的研究路徑，即凸集投影的概念可以應用于聚類數據點。
凸集投影
首先，讓我們一起簡單回顧一下凸集投影的概念（沒有方程形式）。凸集投影的方法大致可以分為兩種形式：交替和平行。
交替凸集投影
從數據空間中的任意點開始，從該點到兩個（或多個）相交凸集的交替投影將收斂到集合的交點內的一個點。下圖給出了相應的圖形化說明。
當凸集不相交時，交替投影將收斂到貪婪極限環，貪婪極限環取決于投影的階數。
平行凸集投影
與交替形式不同，并行形式的凸集投影同時執行從數據點到所有凸集的投影，并且每個投影具有重要的權重。對于兩個非空相交凸集，類似于交替版本，平行投影收斂到集合的相交點。
在不相交凸集的情況下，投影將收斂到最小化解?；谕辜队暗木垲愃惴ǖ闹饕枷?/span>正是從這一性質出發產生的。
有關凸集投影的更多詳細信息，您可以訪問原始論文和/或其他一些推薦論文（包括可用的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
