論文の概要: A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
- arxiv url: http://arxiv.org/abs/2601.06351v1
- Date: Fri, 09 Jan 2026 23:14:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-13 19:08:00.765821
- Title: A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
- Title（参考訳）: ユークリッドアンチクラスタリングの高速かつ効果的な手法:アサインメントベースアンティルスター法
- Authors: Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum, Jason Yang,
- Abstract要約: 代入ベースのアンチクラスタリングアルゴリズムは、非常に大きなインスタンスにスケールする。
ABAは、ソリューションの品質と実行時間の両方において、よく知られたMETIS法よりも優れている。
ABAアルゴリズムのコードはGitHubで公開されている。
- 参考スコア（独自算出の注目度）: 0.43748379918040853
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The anticlustering problem is to partition a set of objects into K equal-sized anticlusters such that the sum of distances within anticlusters is maximized. The anticlustering problem is NP-hard. We focus on anticlustering in Euclidean spaces, where the input data is tabular and each object is represented as a D-dimensional feature vector. Distances are measured as squared Euclidean distances between the respective vectors. Applications of Euclidean anticlustering include social studies, particularly in psychology, K-fold cross-validation in which each fold should be a good representative of the entire dataset, the creation of mini-batches for gradient descent in neural network training, and balanced K-cut partitioning. In particular, machine-learning applications involve million-scale datasets and very large values of K, making scalable anticlustering algorithms essential. Existing algorithms are either exact methods that can solve only small instances or heuristic methods, among which the most scalable is the exchange-based heuristic fast_anticlustering. We propose a new algorithm, the Assignment-Based Anticlustering algorithm (ABA), which scales to very large instances. A computational study shows that ABA outperforms fast_anticlustering in both solution quality and running time. Moreover, ABA scales to instances with millions of objects and hundreds of thousands of anticlusters within short running times, beyond what fast_anticlustering can handle. As a balanced K-cut partitioning method for tabular data, ABA is superior to the well-known METIS method in both solution quality and running time. The code of the ABA algorithm is available on GitHub.
- Abstract（参考訳）: 反クラスタリング問題は、オブジェクトの集合を、反クラスタ内の距離の和を最大化するように、K 個の等しいサイズの反クラスタに分割することである。
反クラスタリング問題はNPハードである。
ユークリッド空間では,入力データは表形式で,各オブジェクトはD次元特徴ベクトルとして表現される。
距離は各ベクトル間の2乗ユークリッド距離として測定される。
ユークリッドのアンチクラスタリングの応用例としては、社会研究、特に心理学、各フォールドがデータセット全体の良い代表となるKフォールドクロスバリデーション、ニューラルネットワークトレーニングにおける勾配降下のためのミニバッチの作成、バランスの取れたKカット分割などがある。
特に、機械学習アプリケーションには数百万のデータセットとKの非常に大きな値が含まれており、スケーラブルなアンチクラスタリングアルゴリズムが不可欠である。
既存のアルゴリズムは、小さなインスタンスのみを解決できる正確なメソッドか、ヒューリスティックなメソッドで、中でも最もスケーラブルなのは、交換ベースのヒューリスティックなfast_anticlusteringである。
大規模インスタンスにスケールする新しいアルゴリズムであるAssignment-Based Anticlustering Algorithm (ABA)を提案する。
ABAは、ソリューションの品質と実行時間の両方において、高速な_anticlusteringよりも優れています。
さらにABAは、数百万のオブジェクトと数十万のアンチクラスタを短時間でインスタンスにスケールする。
グラフデータのKカット分割法として、ABAはソリューションの品質と実行時間の両方において、よく知られたMETIS法よりも優れている。
ABAアルゴリズムのコードはGitHubで公開されている。
関連論文リスト
- Linear time Evidence Accumulation Clustering with KMeans [0.0]
この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。
分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。
k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
論文 参考訳（メタデータ） (2023-11-15T14:12:59Z) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳（メタデータ） (2021-11-30T17:08:53Z) - Divide-and-conquer based Large-Scale Spectral Clustering [8.545202841051582]
そこで本研究では,分散・分散型大規模スペクトルクラスタリング手法を提案し,効率と効率のバランスを良くする。
提案手法は,既存の大規模スペクトルクラスタリングよりも計算量が少ない。
論文 参考訳（メタデータ） (2021-04-30T15:09:45Z) - ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
クラスタリングは機械学習の根本的な問題であり、遠隔ベースのアプローチが数十年にわたってこの分野を支配してきた。
Theta-based Algorithms (ThetA) と呼ばれる新しい距離しきい値法を提案する。
論文 参考訳（メタデータ） (2021-02-13T23:16:33Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文 参考訳（メタデータ） (2020-12-01T13:17:27Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering [2.5182813818441945]
最近導入された凸クラスタリング手法は、凸最適化問題としてクラスタリングを定式化している。
最先端の凸クラスタリングアルゴリズムは大規模な計算とメモリ空間を必要とする。
本稿では,凸クラスタリングのための非常に効率的なスムーズな勾配法 (Sproga) を提案する。
論文 参考訳（メタデータ） (2020-06-22T20:02:59Z) - Learnable Subspace Clustering [76.2352740039615]
本研究では,大規模サブスペースクラスタリング問題を効率的に解くために,学習可能なサブスペースクラスタリングパラダイムを開発する。
鍵となる考え方は、高次元部分空間を下層の低次元部分空間に分割するパラメトリック関数を学ぶことである。
我々の知る限り、本論文は、サブスペースクラスタリング手法の中で、数百万のデータポイントを効率的にクラスタ化する最初の試みである。
論文 参考訳（メタデータ） (2020-04-09T12:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。