論文の概要: Fuzzy Clustering with Similarity Queries

• arxiv url: http://arxiv.org/abs/2106.02212v1
• Date: Fri, 4 Jun 2021 02:32:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 15:14:56.110308
• Title: Fuzzy Clustering with Similarity Queries
• Title（参考訳）: 類似クエリによるファジィクラスタリング
• Authors: Wasim Huleihel, Arya Mazumdar, Soumyabrata Pal
• Abstract要約: ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
• 参考スコア（独自算出の注目度）: 56.96625809888241
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The fuzzy or soft $k$-means objective is a popular generalization of the well-known $k$-means problem, extending the clustering capability of the $k$-means to datasets that are uncertain, vague, and otherwise hard to cluster. In this paper, we propose a semi-supervised active clustering framework, where the learner is allowed to interact with an oracle (domain expert), asking for the similarity between a certain set of chosen items. We study the query and computational complexities of clustering in this framework. We prove that having a few of such similarity queries enables one to get a polynomial-time approximation algorithm to an otherwise conjecturally NP-hard problem. In particular, we provide probabilistic algorithms for fuzzy clustering in this setting that asks $O(\mathsf{poly}(k)\log n)$ similarity queries and run with polynomial-time-complexity, where $n$ is the number of items. The fuzzy $k$-means objective is nonconvex, with $k$-means as a special case, and is equivalent to some other generic nonconvex problem such as non-negative matrix factorization. The ubiquitous Lloyd-type algorithms (or, expectation-maximization algorithm) can get stuck at a local minima. Our results show that by making few similarity queries, the problem becomes easier to solve. Finally, we test our algorithms over real-world datasets, showing their effectiveness in real-world applications.
• Abstract（参考訳）: ファジィあるいはソフトな$k$-meansの目標は、よく知られた$k$-means問題の一般的な一般化であり、$k$-meansのクラスタリング機能を不確実で曖昧で、クラスタ化が難しいデータセットに拡張する。 本稿では,学習者がオラクル(ドメインエキスパート)と対話し,選択した項目間の類似性を求める,半教師付きアクティブクラスタリングフレームワークを提案する。 本稿では,クラスタリングの問合せと計算複雑性について考察する。 このような類似性クエリがいくつかあることで、多項式時間近似アルゴリズムを、そうでない意味ではNPハードな問題に適用できることを示す。 特に、この設定において、ファジィクラスタリングの確率的アルゴリズムを提供し、$o(\mathsf{poly}(k)\log n)$ similarity クエリをリクエストし、多項式時間複雑度で実行し、ここで $n$ はアイテム数である。 ファジィ $k$-means の目的は非凸であり、特別な場合として $k$-means を持ち、非負行列因子分解のような他の一般的な非凸問題と同値である。 ユビキタスなロイド型アルゴリズム(あるいは期待最大化アルゴリズム)は、ローカルなミニマで立ち往生することができる。 その結果,類似性のあるクエリが少ないと,解決が容易になることがわかった。 最後に、我々のアルゴリズムを実世界のデータセット上でテストし、実世界のアプリケーションでの有効性を示す。

関連論文リスト

• Simple, Scalable and Effective Clustering via One-Dimensional Projections [10.807367640692021]
  クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。 任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。 我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
  論文  参考訳（メタデータ） (2023-10-25T16:37:45Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Are Easy Data Easy (for K-Means) [0.0]
  本稿では、$k$-meansアルゴリズムの様々なブランドによって、適切に分離されたクラスタを復元する能力について検討する。 シード選択時に繰り返しサブサンプリングによって$k$-means++のバリエーションが提案される。
  論文  参考訳（メタデータ） (2023-08-02T09:40:19Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
  我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。 一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。 我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-02-28T04:21:53Z)
• Query-Efficient Correlation Clustering [13.085439249887713]
  相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。 相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。 我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-02-26T15:18:20Z)
• Efficient Algorithms for Generating Provably Near-Optimal Cluster Descriptors for Explainability [36.11663695534294]
  本稿では,クラスタに対する簡潔な表現を構築するための最近のアプローチを拡張して,クラスタをより解釈しやすくする問題について検討する。 我々は,その問題に対する性能保証を証明可能な近似アルゴリズムを開発した。 また、異なる脅威レベルを表すゲノム配列のクラスタを含むデータセットからのクラスタを説明するアプリケーションを示す。
  論文  参考訳（メタデータ） (2020-02-06T19:49:54Z)

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

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