論文の概要: A Constant Approximation Algorithm for Sequential No-Substitution
k-Median Clustering under a Random Arrival Order
- arxiv url: http://arxiv.org/abs/2102.04050v1
- Date: Mon, 8 Feb 2021 08:25:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-09 16:01:15.993174
- Title: A Constant Approximation Algorithm for Sequential No-Substitution
k-Median Clustering under a Random Arrival Order
- Title（参考訳）: ランダム到着順序に基づく連続非置換k-メディアンクラスタリングの定数近似アルゴリズム
- Authors: Tom Hess, Michal Moshkovitz and Sivan Sabato
- Abstract要約: シーケンシャルな非置換条件下でのk中間クラスタリングについて検討する。
この設定では、データストリームを順次観測し、アルゴリズムによっていくつかのポイントをクラスタセンターとして選択する。
ランダム到着順序下での最適リスクに対する定数近似係数を求めるアルゴリズムを新たに提案する。
- 参考スコア（独自算出の注目度）: 24.304228393096395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study k-median clustering under the sequential no-substitution setting. In
this setting, a data stream is sequentially observed, and some of the points
are selected by the algorithm as cluster centers. However, a point can be
selected as a center only immediately after it is observed, before observing
the next point. In addition, a selected center cannot be substituted later. We
give a new algorithm for this setting that obtains a constant approximation
factor on the optimal risk under a random arrival order. This is the first such
algorithm that holds without any assumptions on the input data and selects a
non-trivial number of centers. The number of selected centers is quasi-linear
in k. Our algorithm and analysis are based on a careful risk estimation that
avoids outliers, a new concept of a linear bin division, and repeated
calculations using an offline clustering algorithm.
- Abstract（参考訳）: 逐次no-substitution設定下でk-medianクラスタリングについて検討した。
この設定では、データストリームを順次観測し、アルゴリズムによっていくつかのポイントをクラスタセンターとして選択する。
しかし、次の点を観測する前に、その点が観測された直後にのみ中心として選択できる。
また、選択されたセンターを後で置き換えることはできない。
我々は、ランダムな到着順序の下で最適なリスクに対する一定の近似係数を得るこの設定のための新しいアルゴリズムを与える。
これは入力データに仮定せずに保持し、非自明な数のセンターを選択する最初のアルゴリズムである。
私たちのアルゴリズムと分析は、外れ値を回避する慎重なリスク推定、線形ビン分割の新しい概念、オフラインクラスタリングアルゴリズムを使用して繰り返し計算に基づいています。
関連論文リスト
- Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。
本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-07T12:25:03Z) - Rethinking k-means from manifold learning perspective [122.38667613245151]
平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。
具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。
異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
論文 参考訳（メタデータ） (2023-05-12T03:01:41Z) - An enhanced method of initial cluster center selection for K-means
algorithm [0.0]
K-meansアルゴリズムの初期クラスタ選択を改善するための新しい手法を提案する。
Convex Hullアルゴリズムは、最初の2つのセントロイドの計算を容易にし、残りの2つは、以前選択された中心からの距離に応じて選択される。
We obtained only 7.33%, 7.90%, and 0% clustering error in Iris, Letter, and Ruspini data。
論文 参考訳（メタデータ） (2022-10-18T00:58:50Z) - An Improved Greedy Algorithm for Subset Selection in Linear Estimation [5.994412766684842]
有限個の予測位置において、観測値の最もよい推定値を与えるような k 個の位置の集合を求める空間場における部分選択問題を考える。
観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。
本稿では,予測位置と予測位置によって形成される傾斜角の遠心点のみからなる探索空間を考慮し,計算複雑性を低減する手法を提案する。
論文 参考訳（メタデータ） (2022-03-30T05:52:16Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳（メタデータ） (2022-02-01T19:31:15Z) - Determinantal consensus clustering [77.34726150561087]
本稿では,クラスタリングアルゴリズムのランダム再起動における決定点プロセス (DPP) の利用を提案する。
DPPは部分集合内の中心点の多様性を好んでいる。
DPPとは対照的に、この手法は多様性の確保と、すべてのデータフェースについて良好なカバレッジを得るために失敗することを示す。
論文 参考訳（メタデータ） (2021-02-07T23:48:24Z) - Relational Algorithms for k-means Clustering [17.552485682328772]
本稿では,関係アルゴリズムモデルにおいて効率的なk平均近似アルゴリズムを提案する。
実行時間は潜在的に$N$よりも小さくなり、リレーショナルデータベースが表すデータポイントの数はクラスタ化される。
論文 参考訳（メタデータ） (2020-08-01T23:21:40Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Ball k-means [53.89505717006118]
Ball k-meansアルゴリズムは、ポイントセントロイド距離計算の削減に集中して、クラスタを記述するためにボールを使用する。
高速、余分なパラメータなし、単純設計のボールk平均アルゴリズムは、素早いk平均アルゴリズムを全面的に置き換える。
論文 参考訳（メタデータ） (2020-05-02T10:39:26Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z) - A novel initialisation based on hospital-resident assignment for the
k-modes algorithm [0.0]
本稿では,k-modesアルゴリズムの初期解を選択する新しい方法を提案する。
これは、数学的公正性の概念と、文献から共通の初期化ができないデータの活用を可能にする。
論文 参考訳（メタデータ） (2020-02-07T10:20:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。