論文の概要: Wide Gaps and Clustering Axioms
- arxiv url: http://arxiv.org/abs/2308.03464v1
- Date: Mon, 7 Aug 2023 10:43:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-08 14:15:56.083296
- Title: Wide Gaps and Clustering Axioms
- Title(参考訳): 広いギャップとクラスタリング公理
- Authors: Mieczys{\l}aw A. K{\l}opotek
- Abstract要約: k-平均は、距離に基づくクラスタリングアルゴリズムのためのクラインバーグの公理系と矛盾している。
我々は,2つの新しいクラスタビリティ特性,変分k-分離性と残留k-分離性を導入する。
我々は、k-meansを、ユークリッドおよび非ユークリッドセッティングにおけるクラインバーグの公理的フレームワークと照合する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The widely applied k-means algorithm produces clusterings that violate our
expectations with respect to high/low similarity/density and is in conflict
with Kleinberg's axiomatic system for distance based clustering algorithms that
formalizes those expectations in a natural way. k-means violates in particular
the consistency axiom. We hypothesise that this clash is due to the not
explicated expectation that the data themselves should have the property of
being clusterable in order to expect the algorithm clustering hem to fit a
clustering axiomatic system. To demonstrate this, we introduce two new
clusterability properties, variational k-separability and residual
k-separability and show that then the Kleinberg's consistency axiom holds for
k-means operating in the Euclidean or non-Euclidean space. Furthermore, we
propose extensions of k-means algorithm that fit approximately the Kleinberg's
richness axiom that does not hold for k-means. In this way, we reconcile
k-means with Kleinberg's axiomatic framework in Euclidean and non-Euclidean
settings. Besides contribution to the theory of axiomatic frameworks of
clustering and for clusterability theory, practical contribution is the
possibility to construct {datasets for testing purposes of algorithms
optimizing k-means cost function. This includes a method of construction of
{clusterable data with known in advance global optimum.
- Abstract(参考訳): 広く応用されたk平均アルゴリズムは、高い/低い類似性/密度に関して我々の期待に反するクラスタリングを生成し、これらの期待を自然な方法で形式化する距離ベースクラスタリングアルゴリズムに対するクラインバーグの公理的システムと矛盾している。
k-平均は特に一貫性公理に反する。
この衝突は、アルゴリズムのクラスタリングヘムがクラスタリングの公理系に適合することを期待するために、データ自体がクラスタリング可能な性質を持つべきだという明示的な期待によるものである。
これを示すために、変分 k-分離性と残留 k-分離性という2つの新しいクラスタビリティ特性を導入し、クラインバーグの一貫性公理がユークリッド空間や非ユークリッド空間で作用するk-平均に対して成り立つことを示す。
さらに,k-means に当てはまらない Kleinberg のリッチネス公理にほぼ一致する k-means アルゴリズムの拡張を提案する。
このようにして、k-平均をユークリッドおよび非ユークリッド設定におけるクラインバーグの公理的枠組みと調和させる。
クラスタリングとクラスタ性理論の公理的枠組みの理論への貢献の他に、k平均コスト関数を最適化するアルゴリズムをテストするためにデータセットを構築することができる。
これには、事前にグローバルな最適化が知られている {clusterable data の構築方法が含まれる。
関連論文リスト
- Explaining Kernel Clustering via Decision Trees [10.504801686625129]
解釈可能なカーネルクラスタリングについて検討し、カーネルk-meansによって誘導されるパーティションを近似するために決定木を構築するアルゴリズムを提案する。
本稿は,k-meansに関する従来の研究に基づいて,解釈可能なモデルの近似保証を犠牲にすることなく,適切な特徴の選択が解釈可能性の維持を可能にすることを実証する。
論文 参考訳(メタデータ) (2024-02-15T11:08:23Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。
本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
論文 参考訳(メタデータ) (2022-05-17T01:41:06Z) - A Greedy and Optimistic Approach to Clustering with a Specified
Uncertainty of Covariates [6.231304401179968]
我々は,経験的不確実性集合よりも優れた特徴候補を求める,欲求的で楽観的なクラスタリング(GOC)アルゴリズムを提案する。
重要な応用として、銀河系の形成過程を模した数値シミュレーションにより生成された恒星の軌道特性の合成データセットにGACアルゴリズムを適用した。
論文 参考訳(メタデータ) (2022-04-18T07:54:24Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳(メタデータ) (2021-12-07T18:50:17Z) - HAWKS: Evolving Challenging Benchmark Sets for Cluster Analysis [2.5329716878122404]
クラスタリングアルゴリズムの包括的なベンチマークは難しい。
厳格なベンチマークのベストプラクティスに関する合意はありません。
このようなベンチマークのフレキシブルな生成を支援するために,進化的アルゴリズムが果たす重要な役割を実証する。
論文 参考訳(メタデータ) (2021-02-13T15:01:34Z) - A Multi-disciplinary Ensemble Algorithm for Clustering Heterogeneous
Datasets [0.76146285961466]
本稿では,社会階級ランキングとメタヒューリスティックアルゴリズムに基づく進化的クラスタリングアルゴリズム(ECAStar)を提案する。
ECAStarは、再共生進化演算子、レヴィ飛行最適化、いくつかの統計技術と統合されている。
従来の5つのアプローチに対してECAStarを評価する実験を行った。
論文 参考訳(メタデータ) (2021-01-01T07:20:50Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳(メタデータ) (2020-10-31T21:35:42Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳(メタデータ) (2020-08-31T08:41:20Z) - Real Elliptically Skewed Distributions and Their Application to Robust
Cluster Analysis [5.137336092866906]
本稿では,Really Skewed(RESK)分布と関連するクラスタリングアルゴリズムの新しいクラスを提案する。
非対称分散および重み付きデータクラスタは、様々な現実世界のアプリケーションで報告されている。
論文 参考訳(メタデータ) (2020-06-30T10:44:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。