凸集合への投影 (POCS) に基づくクラスタリング アルゴリズム

POCS: 凸集合への投影。数学では、凸集合とは、任意の 2 点間の任意の線分が集合内に含まれる集合です。投影は、点を別の空間の部分空間にマッピングする操作です。凸集合と点が与えられると、凸集合への点の投影を見つけることによって操作できます。投影は、凸集合内の点に最も近い点であり、この点と凸集合内の他の点との間の距離を最小化することによって計算できます。これは投影であるため、特徴を別の空間の凸セットにマッピングして、クラスタリングや次元削減などの操作を実行できます。

この記事では、凸集合射影法に基づくクラスタリング アルゴリズム、つまり POCS に基づくクラスタリング アルゴリズムをレビューします。原論文はIWIS2022で発表されました。

凸集合

凸集合はデータ点の集合として定義され、集合内の任意の 2 点 x1 と x2 を結ぶ線分が完全にこの集合に含まれます。凸集合の定義によれば、空集合∅、ユニタリー集合、線分、超平面、ユークリッド球はすべて凸集合とみなされます。データ ポイントはシングルトン セット (要素が 1 つだけあるセット) であるため、凸セットともみなされます。これにより、POCS の概念をクラスター化されたデータ ポイントに適用するための新しい道が開かれます。

凸集合の射影 (POCS)

POCS 手法は、交互と並列の 2 つのタイプに大別できます。

1. 交互の poc

データ空間内の任意の点から開始して、この点から 2 つ (またはそれ以上) の交差する凸セットへの交互投影は、セットの交点 1 つの点に収束します。次の図のように:

凸集合が交差しない場合、交互投影は投影順序に依存する貪欲なリミット サイクルに収束します。

2. 並列 POCS

交互形式とは異なり、並列 POCS プロジェクトはデータ ポイントからすべての凸セットに同時にプロジェクトされ、各投影にはすべて重要性があります。重さ。 2 つの空でない交差する凸セットの場合、交互バージョンと同様に、平行投影はセットの交点の点に収束します。

凸集合が交差しない場合、射影は最小解に収束します。 POC ベースのクラスタリング アルゴリズムの主なアイデアは、この機能から来ています。

POCS の詳細については、元の論文を参照してください。

pocs に基づくクラスタリング アルゴリズム

並列の収束を使用するPOCS 手法の特性を利用して、論文の著者は非常にシンプルだがある程度効果的なクラスタリング アルゴリズムを提案しました。このアルゴリズムは古典的な K-Means アルゴリズムと同様に機能しますが、各データ ポイントの処理方法に違いがあります。K-Means アルゴリズムは各データ ポイントの重要度の重み付けが同じですが、POC ベースのクラスタリング アルゴリズムは各データ ポイント重要度は異なる重み付けされ、クラスター プロトタイプからのデータ ポイントの距離に比例します。

アルゴリズムの疑似コードは次のとおりです。

実験結果

著者は、いくつかの公開環境で POC ベースのアルゴリズムをテストしました。ベンチマーク データ セット クラスタリング アルゴリズムのパフォーマンス。以下の表は、これらのデータセットの説明をまとめたものです。

著者らは、POC ベースのクラスタリング アルゴリズムのパフォーマンスを、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 中国語 Web サイトの他の関連記事を参照してください。