論文の概要: Simple KNN-Based Outlier Detection Achieves Robust Clustering

• arxiv url: http://arxiv.org/abs/2605.07130v1
• Date: Fri, 08 May 2026 02:08:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.738515
• Title: Simple KNN-Based Outlier Detection Achieves Robust Clustering
• Title（参考訳）: 単純なKNNベースのアウトレイラ検出がロバストクラスタリングを実現する
• Authors: Tianle Jiang, Yufa Zhou,
• Abstract要約: 外れ値の存在に堅牢であることは、実際にクラスタリングアルゴリズムを適用する上で極めて重要です。 我々は,K$-Nearest-Neighbor 距離の大きい点を除去することで,近似保証の点から先行処理に匹敵する性能が得られることを示す。
• 参考スコア（独自算出の注目度）: 0.8250700096210891
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the $\textit{robust $k$-Means}$ problem (i.e., $k$-Means with outliers), the goal is to remove $z$ outliers and minimize the $k$-Means cost on the remaining points. Despite the close connection between robust $k$-Means and outlier detection, both theoretical and empirical understanding of the effectiveness of $\textit{classic outlier detection heuristics}$ for robust $k$-Means remains limited. In this paper, we prove that under a practical assumption on the optimal cluster sizes, simply removing points with large $K$-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees: it yields a constant-factor reduction from robust $k$-Means to standard $k$-Means, without introducing additional centers or discarding extra outliers, as is commonly required by existing approaches. Empirically, experiments on real-world datasets show that our method outperforms or matches several more sophisticated algorithms in terms of clustering cost and runtime. These results demonstrate that simple KNN-based heuristics can be surprisingly effective for robust clustering, highlighting new opportunities to bridge techniques from outlier detection and clustering.
• Abstract（参考訳）: 外れ値の存在に堅牢であることは、実際にクラスタリングアルゴリズムを適用する上で極めて重要です。 $\textit{robust $k$-Means}$ problem (例:$k$-Means with outliers)では、$z$outliersを削除し、残りのポイントの$k$-Meansコストを最小化する。 堅牢な$k$-Meansとoutlier detectionの密接な関係にもかかわらず、$\textit{classic outlier detection heuristics}$のロバストな$k$-Meansに対する有効性に関する理論的および実証的な理解は依然として限られている。 本稿では, クラスタサイズを最適に仮定した上で, K$-Nearest-Neighbor 距離の大きい点を単純に取り除けば, 従来のアプローチでは必要とされていたような, より堅牢な $k$-Means から標準 $k$-Means への定数要素の削減を達成できることを示す。 実世界のデータセットに関する実験では、クラスタリングコストと実行時間の観点から、我々の手法がより優れているか、より洗練されたアルゴリズムと一致していることが示された。 これらの結果は、単純なKNNベースのヒューリスティックスがロバストクラスタリングに驚くほど効果的であることを示し、異常検出やクラスタリングからテクニックをブリッジする新たな機会を強調している。

関連論文リスト

• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Bridged Clustering for Representation Learning: Semi-Supervised Sparse Bridging [7.631238459202664]
  我々はBridged Clusteringを紹介した。Bridged Clusteringは、未実装の入力$X$と出力$Y$データセットから予測子を学習する半教師付きフレームワークである。 我々のメソッドはまず最初に$X$と$Y$を独立にクラスタし、その後、わずかにペア化された例を使ってクラスタ間のスパースで解釈可能なブリッジを学習する。
  論文  参考訳（メタデータ） (2025-10-08T16:20:49Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Are Easy Data Easy (for K-Means) [0.0]
  本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。 シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
  論文  参考訳（メタデータ） (2023-08-02T09:40:19Z)
• Asymptotics for The $k$-means [0.6091702876917281]
  k$-meansは統計学と計算機科学において最も重要な教師なし学習手法の1つである。 提案したクラスタリング整合性は,クラスタリング手法の以前の基準整合性よりも適切である。 提案した$k$-means法はクラスタリングエラー率を低くし,小さなクラスタやアウトレイアに対してより堅牢であることがわかった。
  論文  参考訳（メタデータ） (2022-11-18T03:36:58Z)
• Robust Trimmed k-means [70.88503833248159]
  本稿では,外乱点とクラスタポイントを同時に識別するRobust Trimmed k-means (RTKM)を提案する。 RTKMは他の方法と競合することを示す。
  論文  参考訳（メタデータ） (2021-08-16T15:49:40Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Entropy Regularized Power k-Means Clustering [21.013169939337583]
  本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。 我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
  論文  参考訳（メタデータ） (2020-01-10T14:05:44Z)

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

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