論文の概要: Efficient Constrained $k$-Center Clustering with Background Knowledge
- arxiv url: http://arxiv.org/abs/2401.12533v1
- Date: Tue, 23 Jan 2024 07:16:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 16:30:19.119140
- Title: Efficient Constrained $k$-Center Clustering with Background Knowledge
- Title（参考訳）: バックグラウンド知識を用いた効率的な制約付き$k$-Centerクラスタリング
- Authors: Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu and Minhui Xue
- Abstract要約: 我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。
制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
- 参考スコア（独自算出の注目度）: 13.741723261888616
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Center-based clustering has attracted significant research interest from both
theory and practice. In many practical applications, input data often contain
background knowledge that can be used to improve clustering results. In this
work, we build on widely adopted $k$-center clustering and model its input
background knowledge as must-link (ML) and cannot-link (CL) constraint sets.
However, most clustering problems including $k$-center are inherently
$\mathcal{NP}$-hard, while the more complex constrained variants are known to
suffer severer approximation and computation barriers that significantly limit
their applicability. By employing a suite of techniques including reverse
dominating sets, linear programming (LP) integral polyhedron, and LP duality,
we arrive at the first efficient approximation algorithm for constrained
$k$-center with the best possible ratio of 2. We also construct competitive
baseline algorithms and empirically evaluate our approximation algorithm
against them on a variety of real datasets. The results validate our
theoretical findings and demonstrate the great advantages of our algorithm in
terms of clustering cost, clustering quality, and running time.
- Abstract（参考訳）: センターベースのクラスタリングは理論と実践の両方から大きな研究関心を集めている。
多くの実用的なアプリケーションでは、入力データは、しばしばクラスタリング結果を改善するのに使用できる背景知識を含んでいる。
本研究は、広く採用されている$k$-centerクラスタリングに基づいて、入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。
しかし、$k$-centerを含むクラスタリング問題は本質的に$\mathcal{NP}$-hardであるのに対し、より複雑な制約のある変種は、それらの適用性を著しく制限する厳しい近似と計算障壁に悩まされることが知られている。
逆支配集合、線形計画法(lp)積分多面体、lp双対性を含む一連の手法を用いることにより、最大比率2の制約付きk$中心に対する最初の効率的な近似アルゴリズムに到達した。
また、競合ベースラインアルゴリズムを構築し、様々な実データセット上で近似アルゴリズムを実証的に評価する。
その結果, クラスタリングコスト, クラスタリング品質, 実行時間の観点から, 提案アルゴリズムの優れた利点を実証した。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - Query-Efficient Correlation Clustering with Noisy Oracle [17.11782578276788]
共同マルチアーマッドバンド(PE-CMAB)における純粋探索のパラダイムに根ざしたオンライン学習問題の2つの新しい定式化を導入する。
我々は,サンプリング戦略と古典近似アルゴリズムを組み合わせるアルゴリズムを設計し,それらの理論的保証について検討する。
本研究は, PE-CMABの場合のクラスタリング時アルゴリズムの最初の例であり, 基礎となるオフライン最適化問題はNP-hardである。
論文 参考訳（メタデータ） (2024-02-02T13:31:24Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - Neural Capacitated Clustering [6.155158115218501]
本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。
人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
論文 参考訳（メタデータ） (2023-02-10T09:33:44Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳（メタデータ） (2022-08-02T01:49:31Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳（メタデータ） (2022-02-01T19:31:15Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳（メタデータ） (2021-11-30T17:08:53Z) - Learning-Augmented $k$-means Clustering [44.06375788674942]
予測器を付加した$k$-means問題を考えると、任意の点で、そのクラスタラベルを、何らかの、おそらくは逆のエラーまで、ほぼ最適なクラスタリングで返します。
精度の高い予測器に従えば、高いクラスタリングコストがもたらされるが、予測器の精度とともに性能が向上するアルゴリズムを提案する。
我々は、実際のデータセット上でアルゴリズムを評価し、クラスタリングの品質を大幅に改善したことを示す。
論文 参考訳（メタデータ） (2021-10-27T00:11:49Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。
相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文 参考訳（メタデータ） (2020-02-06T14:28:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。