論文の概要: Average Sensitivity of Hierarchical $k$-Median Clustering

• arxiv url: http://arxiv.org/abs/2507.10296v1
• Date: Mon, 14 Jul 2025 14:02:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:25.066306
• Title: Average Sensitivity of Hierarchical $k$-Median Clustering
• Title（参考訳）: 階層型$k$-Medianクラスタリングの平均感度
• Authors: Shijie Li, Weiqiang He, Ruobing Bai, Pan Peng,
• Abstract要約: 階層的およびセントロイドベースのクラスタリングを橋渡しする階層的$k$-medianクラスタリング問題に焦点を当てる。 階層的な$k$-medianクラスタリングのための効率的なアルゴリズムを提案し,その平均感度とクラスタリング品質を理論的に証明する。
• 参考スコア（独自算出の注目度）: 9.107341310040155
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hierarchical clustering is a widely used method for unsupervised learning with numerous applications. However, in the application of modern algorithms, the datasets studied are usually large and dynamic. If the hierarchical clustering is sensitive to small perturbations of the dataset, the usability of the algorithm will be greatly reduced. In this paper, we focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering while offering theoretical appeal, practical utility, and improved interpretability. We analyze the average sensitivity of algorithms for this problem by measuring the expected change in the output when a random data point is deleted. We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality. Additionally, we show that single linkage clustering and a deterministic variant of the CLNSS algorithm exhibit high average sensitivity, making them less stable. Finally, we validate the robustness and effectiveness of our algorithm through experiments.
• Abstract（参考訳）: 階層クラスタリングは、多くのアプリケーションで教師なし学習に広く使われている手法である。 しかし、現代のアルゴリズムの適用においては、研究対象のデータセットは通常大きく、動的である。 階層的クラスタリングがデータセットの小さな摂動に敏感であれば、アルゴリズムのユーザビリティは大幅に低下する。 本稿では,階層型クラスタリングとセントロイド型クラスタリングを橋渡しし,理論的魅力,実用性,解釈可能性の向上を図った階層型$k$-medianクラスタリング問題に焦点をあてる。 ランダムなデータポイントが削除された場合の出力の変化を計測することにより,この問題に対するアルゴリズムの平均感度を解析する。 階層的な$k$-medianクラスタリングのための効率的なアルゴリズムを提案し,その平均感度とクラスタリング品質を理論的に証明する。 さらに,CLNSSアルゴリズムの単一リンククラスタリングと決定論的変異は,高い平均感度を示し,安定性を低下させることを示した。 最後に,実験によるアルゴリズムの堅牢性と有効性を検証する。

関連論文リスト

• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  本研究では,Fair SC問題を凸関数(DC)フレームワークの差内にキャストすることで,フェアスペクトルクラスタリング(Fair SC)のための新しい効率的な手法を提案する。 本研究では,各サブプロブレムを効率よく解き,計算効率が先行処理よりも高いことを示す。
  論文  参考訳（メタデータ） (2025-06-09T18:46:27Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。 本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-07T12:25:03Z)
• Hierarchical clustering by aggregating representatives in sub-minimum-spanning-trees [5.877624540482919]
  本稿では,クラスタリングデンドログラムを構築しながら,代表点を効果的に検出できる階層的クラスタリングアルゴリズムを提案する。 解析の結果,提案アルゴリズムはO(nlogn)時間複雑度とO(nlogn)空間複雑度を有し,大規模データ処理のスケーラビリティを示す。
  論文  参考訳（メタデータ） (2021-11-11T07:36:55Z)
• Envelope Imbalance Learning Algorithm based on Multilayer Fuzzy C-means Clustering and Minimum Interlayer discrepancy [14.339674126923903]
  本稿では,マルチ層ファジィc-means(MlFCM)と最小層間離散化機構(MIDMD)を用いたディープインスタンスエンベロープネットワークに基づく不均衡学習アルゴリズムを提案する。 このアルゴリズムは、事前の知識がなければ、ディープインスタンスエンベロープネットワークを使用して、高品質なバランスの取れたインスタンスを保証できる。
  論文  参考訳（メタデータ） (2021-11-02T04:59:57Z)
• Unsupervised Clustered Federated Learning in Complex Multi-source Acoustic Environments [75.8001929811943]
  現実的で挑戦的なマルチソース・マルチルーム音響環境を導入する。 本稿では,音響シーンの変動を考慮したクラスタリング制御手法を提案する。 提案手法はクラスタリングに基づく測度を用いて最適化され,ネットワークワイド分類タスクによって検証される。
  論文  参考訳（メタデータ） (2021-06-07T14:51:39Z)
• DAC: Deep Autoencoder-based Clustering, a General Deep Learning Framework of Representation Learning [0.0]
  dac,deep autoencoder-based clustering,深層ニューロンネットワークを用いてクラスタリング表現を学ぶためのデータ駆動フレームワークを提案する。 実験結果から,KMeansクラスタリングアルゴリズムの性能をさまざまなデータセット上で効果的に向上させることができた。
  論文  参考訳（メタデータ） (2021-02-15T11:31:00Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
  直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。 本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
  論文  参考訳（メタデータ） (2020-02-20T02:41:02Z)

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

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