論文の概要: Accelerating spherical K-means clustering for large-scale sparse document data
- arxiv url: http://arxiv.org/abs/2411.11300v1
- Date: Mon, 18 Nov 2024 05:50:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-19 14:35:35.288760
- Title: Accelerating spherical K-means clustering for large-scale sparse document data
- Title（参考訳）: 大規模スパース文書データのための球状K平均クラスタリングの高速化
- Authors: Kazuo Aoyama, Kazumi Saito,
- Abstract要約: 本稿では,大規模かつ高次元のスパース文書データセットを対象とした球面K平均クラスタリングアルゴリズムを提案する。
提案手法は, 大規模文書において, 最先端技術を用いたアルゴリズムと比較して, 高速性能を効果的に達成できることを実験的に実証した。
- 参考スコア（独自算出の注目度）: 0.7366405857677226
- License:
- Abstract: This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We design an algorithm working in an architecture-friendly manner (AFM), which is a procedure of suppressing performance-degradation factors such as the numbers of instructions, branch mispredictions, and cache misses in CPUs of a modern computer system. For the AFM operation, we leverage unique universal characteristics (UCs) of a data-object and a cluster's mean set, which are skewed distributions on data relationships such as Zipf's law and a feature-value concentration phenomenon. The UCs indicate that the most part of the number of multiplications for similarity calculations is executed regarding terms with high document frequencies (df) and the most part of a similarity between an object- and a mean-feature vector is obtained by the multiplications regarding a few high mean-feature values. Our proposed algorithm applies an inverted-index data structure to a mean set, extracts the specific region with high-df terms and high mean-feature values in the mean-inverted index by newly introduced two structural parameters, and exploits the index divided into three parts for efficient pruning. The algorithm determines the two structural parameters by minimizing the approximate number of multiplications related to that of instructions, reduces the branch mispredictions by sharing the index structure including the two parameters with all the objects, and suppressing the cache misses by keeping in the caches the frequently used data in the foregoing specific region, resulting in working in the AFM. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.
- Abstract（参考訳）: 本稿では,大規模かつ高次元のスパース文書データセットを対象とした球面K平均クラスタリングアルゴリズムを提案する。
本稿では,最新のコンピュータシステムにおいて,命令数や分岐予測,キャッシュミスなどの性能劣化を抑える手法として,アーキテクチャフレンドリな手法(AFM)を設計する。
AFM 操作では,Zipf の法則や特徴値集中現象といったデータ関係のスキュー分布であるデータオブジェクトとクラスタの平均集合の普遍的特徴 (UC) を利用する。
UCは、類似度計算の乗算数の大部分が高文書頻度(df)で実行され、オブジェクトと平均特徴ベクトルの類似度の大部分は、いくつかの高い平均特徴値に関する乗算によって得られることを示す。
提案アルゴリズムは, 逆インデックスデータ構造を平均集合に適用し, 新たに導入した2つの構造パラメータにより, 高df項と高平均値を持つ特定領域を抽出し, 効率的な刈り取りのために, インデックスを3つの部分に分割する。
アルゴリズムは、2つのパラメータを含むインデックス構造を全てのオブジェクトと共有することにより分岐予測を最小化し、2つの構造パラメータを最小化することにより2つの構造パラメータを決定する。
提案手法は, 大規模文書において, 最先端技術を用いたアルゴリズムと比較して, 高速性能を効果的に達成できることを実験的に実証した。
関連論文リスト
- FLASC: A Flare-Sensitive Clustering Algorithm [0.0]
本稿では,クラスタ内の分岐を検知してサブポピュレーションを同定するアルゴリズムFLASCを提案する。
アルゴリズムの2つの変種が提示され、ノイズの堅牢性に対する計算コストが取引される。
両変種は計算コストの観点からHDBSCAN*と類似してスケールし,安定した出力を提供することを示す。
論文 参考訳（メタデータ） (2023-11-27T14:55:16Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - CloudAttention: Efficient Multi-Scale Attention Scheme For 3D Point
Cloud Learning [81.85951026033787]
この作業にトランスフォーマーをセットし、それらを形状分類と部分およびシーンセグメンテーションのための階層的なフレームワークに組み込む。
また、各イテレーションにおけるサンプリングとグループ化を活用して、効率的でダイナミックなグローバルなクロスアテンションを計算します。
提案した階層モデルは,最先端の形状分類を平均精度で達成し,従来のセグメンテーション法と同等の結果を得る。
論文 参考訳（メタデータ） (2022-07-31T21:39:15Z) - DRBM-ClustNet: A Deep Restricted Boltzmann-Kohonen Architecture for Data
Clustering [0.0]
DRBM-ClustNetと呼ばれるデータクラスタリングのためのベイジアンDeep Restricted Boltzmann-Kohonenアーキテクチャを提案する。
ラベルなしデータの処理は、非線形分離可能なデータセットの効率的なクラスタリングのために、3段階に分けて行われる。
このフレームワークはクラスタリングの精度に基づいて評価され、他の最先端クラスタリング手法と比較してランク付けされる。
論文 参考訳（メタデータ） (2022-05-13T15:12:18Z) - Riemannian classification of EEG signals with missing values [67.90148548467762]
本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。
第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。
その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
論文 参考訳（メタデータ） (2021-10-19T14:24:50Z) - Structured Inverted-File k-Means Clustering for High-Dimensional Sparse
Data [2.487445341407889]
本稿では,大規模かつ高次元スパースデータセットのためのアーキテクチャフレンドリーなk-meansクラスタリングアルゴリズムsivfを提案する。
性能解析の結果,sivfはキャッシュミス数と分岐予測の精度低下係数を低減し,高い速度を実現していることがわかった。
論文 参考訳（メタデータ） (2021-03-30T07:54:02Z) - A Holistically-Guided Decoder for Deep Representation Learning with
Applications to Semantic Segmentation and Object Detection [74.88284082187462]
一般的な戦略の1つは、バックボーンネットワークに拡張畳み込みを採用し、高解像度のフィーチャーマップを抽出することです。
本稿では,高分解能なセマンティクスリッチな特徴マップを得るために紹介される,新たなホリスティック誘導デコーダを提案する。
論文 参考訳（メタデータ） (2020-12-18T10:51:49Z) - DyCo3D: Robust Instance Segmentation of 3D Point Clouds through Dynamic
Convolution [136.7261709896713]
本稿では,インスタンスの性質に応じて適切な畳み込みカーネルを生成するデータ駆動型アプローチを提案する。
提案手法はScanetNetV2とS3DISの両方で有望な結果が得られる。
また、現在の最先端よりも推論速度を25%以上向上させる。
論文 参考訳（メタデータ） (2020-11-26T14:56:57Z) - New advances in enumerative biclustering algorithms with online
partitioning [80.22629846165306]
さらに、数値データセットの列に定数値を持つ最大二クラスタの効率的で完全で正しい非冗長列挙を実現できる二クラスタリングアルゴリズムであるRIn-Close_CVCを拡張した。
改良されたアルゴリズムはRIn-Close_CVC3と呼ばれ、RIn-Close_CVCの魅力的な特性を保ちます。
論文 参考訳（メタデータ） (2020-03-07T14:54:26Z) - Data Structures & Algorithms for Exact Inference in Hierarchical
Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。
我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文 参考訳（メタデータ） (2020-02-26T17:43:53Z) - Inverted-File k-Means Clustering: Performance Analysis [1.3955252961896318]
inverted-file k-means clustering algorithm (IVF) は、潜在的に多数のクラスを持つ大規模なスパースデータセットに適したアルゴリズムである。
我々は,IVFが設計アルゴリズムよりも優れた性能を実現することを実験的に実証した。
論文 参考訳（メタデータ） (2020-02-21T02:20:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。