論文の概要: Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers

• arxiv url: http://arxiv.org/abs/2301.02814v1
• Date: Sat, 7 Jan 2023 09:26:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-10 18:20:51.834697
• Title: Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers
• Title（参考訳）: 異常値を持つk中心クラスタリングのためのランダム化グリーディアルゴリズムと合成可能コアセット
• Authors: Hu Ding, Ruomin Huang, Kai Liu, Haikuo Yu, Zixiu Wang
• Abstract要約: 外れ値の存在は計算の複雑さを著しく増大させる。 我々のアイデアは、通常の$k$-centerクラスタリング問題を解決するために開発されたgreedy法にインスパイアされている。
• 参考スコア（独自算出の注目度）: 11.546734084378683
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of {\em $k$-center clustering with outliers}. The problem has many important applications in real world, but the presence of outliers can significantly increase the computational complexity. Though a number of methods have been developed in the past decades, it is still quite challenging to design quality guaranteed algorithm with low complexity for this problem. Our idea is inspired by the greedy method, Gonzalez's algorithm, that was developed for solving the ordinary $k$-center clustering problem. Based on some novel observations, we show that a simple randomized version of this greedy strategy actually can handle outliers efficiently. We further show that this randomized greedy approach also yields small coreset for the problem in doubling metrics (even if the doubling dimension is not given), which can greatly reduce the computational complexity. Moreover, together with the partial clustering framework proposed in arXiv:1703.01539 , we prove that our coreset method can be applied to distributed data with a low communication complexity. The experimental results suggest that our algorithms can achieve near optimal solutions and yield lower complexities comparing with the existing methods.
• Abstract（参考訳）: 本稿では,異常値を持つk$-centerクラスタリングの問題について検討する。 この問題は現実世界で多くの重要な応用があるが、外れ値の存在は計算の複雑さを大幅に増加させる可能性がある。 過去数十年の間に多くの手法が開発されてきたが、この問題の複雑さが低い品質保証アルゴリズムを設計することは依然として困難である。 我々のアイデアは、通常の$k$-centerクラスタリング問題を解決するために開発されたgreedy法であるGonzalezのアルゴリズムにインスパイアされている。 いくつかの新しい観察結果から,この欲望戦略の単純なランダム化バージョンが,実際には異常値の処理を効率的に行うことができることを示した。 さらに、このランダム化された欲求的アプローチは、(倍の次元が与えられなくても)メトリクスを2倍にする問題に対して小さなコアセットをもたらすことも示し、計算複雑性を大幅に減少させる。 さらに、arXiv:1703.01539で提案されている部分クラスタリングフレームワークとともに、コアセット手法が通信複雑性の低い分散データに適用可能であることを示す。 実験結果から,提案アルゴリズムは近似最適解を導出し,既存手法と比較して低複雑性が得られることが示唆された。

関連論文リスト

• From Large to Small Datasets: Size Generalization for Clustering Algorithm Selection [12.993073967843292]
  我々は,未知の地下構造クラスタリングを用いて,半教師付き環境で問題を研究する。 本稿では,クラスタリングアルゴリズムの精度向上のためのサイズ一般化の概念を提案する。 データセット全体においてどのアルゴリズムが最適かを特定するために、データの5%をサブサンプルとして使用しています。
  論文  参考訳（メタデータ） (2024-02-22T06:53:35Z)
• A cutting plane algorithm for globally solving low dimensional k-means clustering problems [4.5594982923247995]
  我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。 これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
  論文  参考訳（メタデータ） (2024-02-21T07:55:33Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers [5.478764356647437]
  本稿では,損失最小化に基づくロバストなクラスタリングアルゴリズムを提案する。 これはアルゴリズムが高い確率で高い精度を得るという理論的保証を提供する。 実世界の大規模データセットの実験では、アルゴリズムの有効性が示されている。
  論文  参考訳（メタデータ） (2023-02-28T14:39:18Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Clustering of Big Data with Mixed Features [3.3504365823045044]
  我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。 このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。 本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
  論文  参考訳（メタデータ） (2020-11-11T19:54:38Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
  直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。 本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
  論文  参考訳（メタデータ） (2020-02-20T02:41:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。