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

作者：佚名 2023-04-02 14:16:45

在數(shù)學(xué)中，凸集是指其中任意兩點間的線段均在該集合內(nèi)的集合。而投影則是將某個點映射到另一個空間中的某個子空間上的操作。給定一個凸集合和一個點，可以通過找到該點在該凸集合上的投影來進行操作。

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

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

凸集

凸集定義為一個數(shù)據(jù)點集合，其中連接集合中任意兩點x1和x2的線段完全包含在這個集合中。根據(jù)凸集的定義，認為空集?、單集、線段、超平面、歐氏球都被認為是凸集。數(shù)據(jù)點也被認為是凸集，因為它是單例集（只有一個元素的集合）。這為 POCS 的概念應(yīng)用于聚類數(shù)據(jù)點開辟了一條新路徑。

凸集投影(POCS)

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

1、交替式poc

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

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

2、并行式 POCS

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

在凸集不相交的情況下，投影將收斂到一個最小解。基于pocs的聚類算法的主要思想來源于這一特性。

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

基于pocs的聚類算法

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

算法的偽代碼如下所示:

實驗結(jié)果

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

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

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

示例代碼

我們在一個非常簡單的數(shù)據(jù)集上使用這個算法。作者已經(jīng)發(fā)布了直接使用的包，對于應(yīng)用我們可以直接使用：

pip install pocs-based-clustering

創(chuàng)建一個以10個簇為中心的5000個數(shù)據(jù)點的簡單數(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é)

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

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

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

責(zé)任編輯：華軒來源： DeepHub IMBA

凸集算法集合