論文の概要: Exponentially Consistent Nonparametric Clustering of Data Streams

• arxiv url: http://arxiv.org/abs/2411.13922v1
• Date: Thu, 21 Nov 2024 08:18:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-22 15:19:51.733980
• Title: Exponentially Consistent Nonparametric Clustering of Data Streams
• Title（参考訳）: データストリームの指数整合非パラメトリッククラスタリング
• Authors: Bhupender Singh, Ananth Ram Rajagopalan, Srikrishna Bhashyam,
• Abstract要約: 我々は、未知の分布から生成されたM$独立で同一の分散データストリームの非パラメトリッククラスタリングを考える。 単一リンクベースクラスタリング(SLINK)や$k$-medoids分散クラスタリングのような既存の非パラメトリッククラスタリングアルゴリズムでは、最大クラスタ内距離(d_L$)が最小クラスタ間距離(d_H$)よりも小さいと仮定している。
• 参考スコア（独自算出の注目度）: 4.2603120588176635
• License:
• Abstract: In this paper, we consider nonparametric clustering of $M$ independent and identically distributed (i.i.d.) data streams generated from unknown distributions. The distributions of the $M$ data streams belong to $K$ underlying distribution clusters. Existing results on exponentially consistent nonparametric clustering algorithms, like single linkage-based (SLINK) clustering and $k$-medoids distribution clustering, assume that the maximum intra-cluster distance ($d_L$) is smaller than the minimum inter-cluster distance ($d_H$). First, in the fixed sample size (FSS) setting, we show that exponential consistency can be achieved for SLINK clustering under a less strict assumption, $d_I < d_H$, where $d_I$ is the maximum distance between any two sub-clusters of a cluster that partition the cluster. Note that $d_I < d_L$ in general. Our results show that SLINK is exponentially consistent for a larger class of problems than $k$-medoids distribution clustering. We also identify examples where $k$-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent. Then, we propose a sequential clustering algorithm, named SLINK-SEQ, based on SLINK and prove that it is also exponentially consistent. Simulation results show that the SLINK-SEQ algorithm requires fewer expected number of samples than the FSS SLINK algorithm for the same probability of error.
• Abstract（参考訳）: 本稿では,未知の分布から生成したデータストリームを独立に,同一に分散した$M$の非パラメトリッククラスタリングについて考察する。 M$のデータストリームの分布は、基礎となる分散クラスタの$K$に属する。 単一リンクベース(SLINK)クラスタリングや$k$-medoids分散クラスタリングのような指数関数的に一貫した非パラメトリッククラスタリングアルゴリズムでは、最大クラスタ内距離(d_L$)が最小クラスタ間距離(d_H$)よりも小さいと仮定する。 まず、固定サンプルサイズ(FSS)設定において、より厳密な仮定の下でSLINKクラスタリングにおいて指数的一貫性を達成できることを示し、$d_I < d_H$, ここで、$d_I$はクラスタを分割するクラスタの任意の2つのサブクラスタ間の最大距離である。 注意すべき点は、一般に$d_I < d_L$である。 以上の結果から,SLINKは$k$-medoidsの分散クラスタリングよりも大規模な問題に対して指数関数的に一貫性があることが示唆された。 また、$k$-medoidsクラスタリングが真のクラスタを見つけることができない例も見出すが、SLINKは指数関数的に一貫性がある。 そこで我々は,SLINKに基づく逐次クラスタリングアルゴリズムSLINK-SEQを提案し,指数関数的に一貫性があることを証明した。 シミュレーションの結果、SLINK-SEQアルゴリズムは、同じ誤差の確率で、FSS SLINKアルゴリズムよりも期待されるサンプル数が少ないことがわかった。

関連論文リスト

• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [44.25945344950543]
  境界共分散分布の混合に対するクラスタリング問題について検討する。 このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。 我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
  論文  参考訳（メタデータ） (2023-12-19T01:01:53Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。 我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
  論文  参考訳（メタデータ） (2021-04-28T13:35:17Z)
• K-expectiles clustering [0.0]
  本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。 固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
  論文  参考訳（メタデータ） (2021-03-16T21:14:56Z)
• Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries [22.672233769934845]
  オラクルクエリを用いたクラスタ依存の正確な問題について検討する。 任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
  論文  参考訳（メタデータ） (2021-01-31T18:00:29Z)
• Faster DBSCAN via subsampled similarity queries [42.93847281082316]
  DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。 本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
  論文  参考訳（メタデータ） (2020-06-11T18:57:54Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Statistical power for cluster analysis [0.0]
  クラスターアルゴリズムは、生物医学研究でますます人気がある。 シミュレーションにより,共通解析におけるパワーと精度を推定する。 我々は,大規模なサブグループ分離が期待される場合にのみ,クラスタ分析を適用することを推奨する。
  論文  参考訳（メタデータ） (2020-03-01T02:43:15Z)

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

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