基於凸集上投影（POCS）的聚類演算法

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

#執行聚類並顯示結果:

# 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://arxiv.org/abs/2208.08888

作者发布的源代码在这里：https://github.com/tranleanh/pocs-based-clustering

以上是基於凸集上投影（POCS）的聚類演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！