論文の概要: Sensitivity Sampling with Predictions for k-Means Clustering

• arxiv url: http://arxiv.org/abs/2607.04949v1
• Date: Mon, 06 Jul 2026 11:24:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-07 22:26:30.126115
• Title: Sensitivity Sampling with Predictions for k-Means Clustering
• Title（参考訳）: k平均クラスタリングの予測による感度サンプリング
• Abstract要約: 大規模データセット上でのk平均クラスタリングの問題について検討する。 k-平均のコアセットを導出する最もポピュラーで先進的なアプローチの1つは感度サンプリングである。 我々は,同じ問題からデータセットのシーケンス上でクラスタリングを行う(時間とともに)一般的なシナリオに適用する自然予測器を提案する。
• 参考スコア（独自算出の注目度）: 4.766451696574634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of k-means clustering on large datasets. The state-of-the-art for the problem is given by coresets-based approaches, which build small weighted summaries of the input and derive approximate solutions with rigorous quality guarantees from them. One of the most popular and advanced approaches to derive coresets for k-means is sensitivity sampling. However, sensitivity sampling requires to compute the importance of each input point with respect to the whole dataset over all possible choices of centers. Since the exact computation of such quantities is unfeasible, current approaches work by approximating the sensitivity values. Nevertheless, the runtime of such approaches is still impractical for large datasets. In this work, we propose to reduce the runtime of sensitivity-based approaches for k-means by leveraging predictions to approximate the importance of input points. We first formally prove that current theoretical results on coresets construction via sensitivity sampling hold for coarser approximations of sensitivities compared to the one required by existing approaches. This implies that even fairly noisy predictors can be leveraged for sensitivity-sampling approaches. We then propose a natural predictor, which applies to the common scenario where clustering is performed (over time) on a sequence of datasets from the same problem. We prove that when the datasets in the sequence come from the same (unknown) distribution, centers resulting in a low error on one dataset can be used as predictions for sensitivity sampling in subsequent datasets, with guarantees on their quality. We perform an extensive experimental evaluation showing that our approach significantly improves, in terms of clustering cost vs runtime, over uniform sampling and state-of-the-art sensitivity sampling approaches when applied to sequences of datasets.
• Abstract（参考訳）: 大規模データセット上でのk平均クラスタリングの問題について検討する。 この問題の最先端はコアセットベースのアプローチによって与えられ、入力の小さな重み付き要約を構築し、厳密な品質保証を伴う近似解を導出する。 k-平均のコアセットを導出する最もポピュラーで先進的なアプローチの1つは感度サンプリングである。 しかし、感度サンプリングは、全ての可能な中心の選択に対してデータセット全体に対する各入力点の重要性を計算する必要がある。 そのような量の正確な計算は不可能であるため、現在の手法は感度値の近似によって機能する。 それでも、そのようなアプローチのランタイムは、大規模なデータセットでは実用的ではない。 本研究では,入力点の重要度を近似するために予測を活用することにより,k平均に対する感度に基づくアプローチの実行時間を削減することを提案する。 まず, 従来の手法と比較して, 感度サンプリングホールドによるコアセット構築に関する理論的な結果が, 感度の粗い近似に有効であることを正式に証明した。 これは、かなりノイズの多い予測器でも感度サンプリングアプローチに活用できることを意味している。 次に、同じ問題からデータセットのシーケンス上でクラスタリングを行う(時間とともに)一般的なシナリオに適用する自然予測器を提案する。 シーケンス内のデータセットが同じ(未知の)分布から来ると、あるデータセットのエラーの少ないセンターが、その後のデータセットにおける感度サンプリングの予測として、その品質を保証することができることを証明した。 我々は,クラスタリングコスト対ランタイムの観点から,データセットのシーケンスに適用した場合,一様サンプリングおよび最先端感度サンプリングアプローチよりも,我々のアプローチが大幅に改善されることを示す,広範囲な実験的評価を行った。

関連論文リスト

• Active Learning with Low-Rank Structure for Data Selection [85.43185363043362]
  低ランク近似と残差に基づくサンプリングに基づく新しいデータ選択フレームワークを提案する。 平均損失がデータセット全体の平均損失を近似した$tildeOleft(k + frac1varepsilon2right)$データポイントの重み付きサブセットを選択することができることを示す。
  論文  参考訳（メタデータ） (2026-06-14T22:29:59Z)
• CavMerge: Merging K-means Based on Local Log-Concavity [2.579311291240392]
  K平均クラスタリングは、非線形分離データに適用した場合、最適以下の性能を示すことが知られている。 本稿では,新しいK平均マージアルゴリズムであるemphCavMergeについて述べる。
  論文  参考訳（メタデータ） (2026-04-05T22:47:36Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Geometric Median Matching for Robust k-Subset Selection from Noisy Data [75.86423267723728]
  最適分解点1/2のロバストな推定器であるGeometric Medianを利用する新しいk-subset選択法を提案する。 提案手法は, k-subset を反復的に選択し,部分集合の平均が(潜在的に)ノイズデータセットの GM に近似し,任意の汚損の下でもロバスト性を確保する。
  論文  参考訳（メタデータ） (2025-04-01T09:22:05Z)
• Categorical Data Clustering via Value Order Estimated Distance Metric Learning [53.28598689867732]
  本稿では,分類属性を直感的に表現する新しい順序距離計量学習手法を提案する。 新しい共同学習パラダイムが開発され、クラスタリングとオーダー距離メートル法学習の代替となる。 提案手法は分類および混合データセットのクラスタリング精度に優れる。
  論文  参考訳（メタデータ） (2024-11-19T08:23:25Z)
• Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization [0.3069335774032178]
  K平均クラスタリングはデータマイニングの基盤であるが、その効率は大量のデータセットに直面すると悪化する。 可変近傍探索(VNS)メタヒューリスティックを利用して,K平均クラスタリングをビッグデータに最適化する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-18T15:43:34Z)
• Inference with K-means [0.0]
  k-meansは、kセントロイドをランダムに割り当て、データポイントを最も近いセントロイドに割り当て、割り当てられたポイントの平均に基づいてセントロイドを更新する反復的クラスタリングアルゴリズムである。 オンライン平衡k平均手法を用いて,クラスタデータ分布から得られるデータポイントの最後の成分の予測について検討した。
  論文  参考訳（メタデータ） (2024-10-04T06:51:58Z)
• Downstream-Pretext Domain Knowledge Traceback for Active Learning [138.02530777915362]
  本稿では、下流知識と事前学習指導のデータ相互作用をトレースするダウンストリーム・プレテキスト・ドメイン知識トレース(DOKT)手法を提案する。 DOKTは、トレースバックの多様性指標とドメインベースの不確実性推定器から構成される。 10のデータセットで行った実験は、我々のモデルが他の最先端の手法よりも優れていることを示している。
  論文  参考訳（メタデータ） (2024-07-20T01:34:13Z)
• 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)
• Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
  我々は,k-meansクラスタリングのPeng-Wei半定緩和を高速化するためのスケッチ・アンド・ソルジ手法を提案する。 データが適切に分離された場合、k平均の最適なクラスタリングを特定する。 そうでなければ、我々のアプローチは最適k-平均値に高信頼な下界を与える。
  論文  参考訳（メタデータ） (2022-11-28T19:51:30Z)
• Far Away in the Deep Space: Dense Nearest-Neighbor-Based Out-of-Distribution Detection [33.78080060234557]
  Nearest-Neighborsアプローチは、オブジェクト中心のデータドメインでうまく機能することが示されている。 近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近
  論文  参考訳（メタデータ） (2022-11-12T13:32:19Z)

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

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