論文の概要: BETULA: Numerically Stable CF-Trees for BIRCH Clustering
- arxiv url: http://arxiv.org/abs/2006.12881v1
- Date: Tue, 23 Jun 2020 10:20:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 22:33:49.726785
- Title: BETULA: Numerically Stable CF-Trees for BIRCH Clustering
- Title(参考訳): BETULA:BIRCHクラスタリングのための数値安定CFトレー
- Authors: Andreas Lang and Erich Schubert
- Abstract要約: BIRCHクラスタリングはクラスタリングのアプローチとして広く知られており、その後の研究や商業製品に影響を与えている。
我々は,数値問題がなく,メンテナンスにそれほど費用がかからないクラスタ機能を導入し,多くの計算を簡素化し,効率を向上する。
- 参考スコア(独自算出の注目度): 0.76146285961466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: BIRCH clustering is a widely known approach for clustering, that has
influenced much subsequent research and commercial products. The key
contribution of BIRCH is the Clustering Feature tree (CF-Tree), which is a
compressed representation of the input data. As new data arrives, the tree is
eventually rebuilt to increase the compression. Afterward, the leaves of the
tree are used for clustering. Because of the data compression, this method is
very scalable. The idea has been adopted for example for k-means, data stream,
and density-based clustering.
Clustering features used by BIRCH are simple summary statistics that can
easily be updated with new data: the number of points, the linear sums, and the
sum of squared values. Unfortunately, how the sum of squares is then used in
BIRCH is prone to catastrophic cancellation.
We introduce a replacement cluster feature that does not have this numeric
problem, that is not much more expensive to maintain, and which makes many
computations simpler and hence more efficient. These cluster features can also
easily be used in other work derived from BIRCH, such as algorithms for
streaming data. In the experiments, we demonstrate the numerical problem and
compare the performance of the original algorithm compared to the improved
cluster features.
- Abstract(参考訳): BIRCHクラスタリングはクラスタリングのアプローチとして広く知られており、その後の研究や商業製品に影響を与えている。
BIRCHの重要なコントリビューションは、入力データの圧縮表現であるClustering Feature Tree (CF-Tree)である。
新しいデータが到着すると、最終的に木は圧縮を増やすために再構築される。
その後、木の葉をクラスタリングに使用する。
データ圧縮のため、この手法は非常にスケーラブルである。
k-means、データストリーム、密度ベースのクラスタリングといったアイデアが採用されている。
BIRCHで使用されるクラスタリング機能は単純な要約統計であり、点数、線形和、平方値の和といった新しいデータで簡単に更新できる。
残念なことに、BIRCHにおける正方形の合計は破滅的なキャンセルの傾向にある。
我々は、この数値問題を持たない代替クラスタ機能を導入し、メンテナンスにそれほど費用がかからず、多くの計算を単純化し、より効率的にする。
これらのクラスタ機能は、ストリーミングデータのアルゴリズムなど、BIRCHから派生した他の作業でも簡単に使用することができる。
実験では,数値問題を実演し,元のアルゴリズムの性能を改良されたクラスタ特性と比較した。
関連論文リスト
- Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。
木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-10-19T14:02:42Z) - Linear time Evidence Accumulation Clustering with KMeans [0.0]
この研究は、平均的なリンククラスタリングの振る舞いを模倣するトリックを記述する。
分割の密度を効率よく計算する方法を見つけ、二次的な複雑さから線形的な複雑さへのコストを削減した。
k平均結果は、計算コストを低く保ちながら、NMIの観点からは、最先端の技術に匹敵する。
論文 参考訳(メタデータ) (2023-11-15T14:12:59Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳(メタデータ) (2023-05-28T15:33:24Z) - GBMST: An Efficient Minimum Spanning Tree Clustering Based on
Granular-Ball Computing [78.92205914422925]
多粒度グラニュラバルと最小スパンニングツリー(MST)を組み合わせたクラスタリングアルゴリズムを提案する。
粒度が粗い粒状ボールを構築し,さらに粒状ボールとMSTを用いて「大規模優先度」に基づくクラスタリング手法を実装した。
いくつかのデータセットの実験結果は、アルゴリズムの威力を示している。
論文 参考訳(メタデータ) (2023-03-02T09:04:35Z) - Recovering Unbalanced Communities in the Stochastic Block Model With
Application to Clustering with a Faulty Oracle [9.578056676899203]
オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。
我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-02-17T08:51:19Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - Clustering of Big Data with Mixed Features [3.3504365823045044]
我々は混合型の大規模データのための新しいクラスタリングアルゴリズムを開発した。
このアルゴリズムは、比較的低い密度値の外れ値とクラスターを検出することができる。
本研究では,本アルゴリズムが実際に有効であることを示す実験結果を示す。
論文 参考訳(メタデータ) (2020-11-11T19:54:38Z) - Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
本稿では,データのスムーズさを初めて考慮した新しいクラスタリングアルゴリズムを提案する。
私たちのキーとなるアイデアは、スムーズなグラフを構成する小さなクラスタをクラスタ化することです。
本稿では,マルチスケールな状況に着目するが,データのスムーズさの考え方はどのクラスタリングアルゴリズムにも確実に拡張できる。
論文 参考訳(メタデータ) (2020-09-10T05:21:20Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。