論文の概要: Structured Inverted-File k-Means Clustering for High-Dimensional Sparse
Data
- arxiv url: http://arxiv.org/abs/2103.16141v1
- Date: Tue, 30 Mar 2021 07:54:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-31 15:06:24.380478
- Title: Structured Inverted-File k-Means Clustering for High-Dimensional Sparse
Data
- Title(参考訳): 高次元スパースデータのための逆ファイルk-meansクラスタリング
- Authors: Kazuo Aoyama and Kazumi Saito
- Abstract要約: 本稿では,大規模かつ高次元スパースデータセットのためのアーキテクチャフレンドリーなk-meansクラスタリングアルゴリズムsivfを提案する。
性能解析の結果,sivfはキャッシュミス数と分岐予測の精度低下係数を低減し,高い速度を実現していることがわかった。
- 参考スコア(独自算出の注目度): 2.487445341407889
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents an architecture-friendly k-means clustering algorithm
called SIVF for a large-scale and high-dimensional sparse data set. Algorithm
efficiency on time is often measured by the number of costly operations such as
similarity calculations. In practice, however, it depends greatly on how the
algorithm adapts to an architecture of the computer system which it is executed
on. Our proposed SIVF employs invariant centroid-pair based filter (ICP) to
decrease the number of similarity calculations between a data object and
centroids of all the clusters. To maximize the ICP performance, SIVF exploits
for a centroid set an inverted-file that is structured so as to reduce pipeline
hazards. We demonstrate in our experiments on real large-scale document data
sets that SIVF operates at higher speed and with lower memory consumption than
existing algorithms. Our performance analysis reveals that SIVF achieves the
higher speed by suppressing performance degradation factors of the number of
cache misses and branch mispredictions rather than less similarity
calculations.
- Abstract(参考訳): 本稿では,大規模かつ高次元スパースデータセットのためのアーキテクチャフレンドリーなk-meansクラスタリングアルゴリズムsivfを提案する。
時間のアルゴリズム効率はしばしば類似度計算のようなコストのかかる演算数によって測定される。
しかし実際には、アルゴリズムが実行されるコンピュータシステムのアーキテクチャにどのように適応するかに大きく依存している。
提案するsivfは,invariant centroid-pair based filter (icp)を用いて,全クラスタにおけるデータオブジェクトとcentroidの類似度計算回数を削減する。
ICP性能を最大化するために、SIVFはパイプラインのハザードを低減するために構成された逆ファイルセットをセントロイドに悪用する。
我々は、SIVFが既存のアルゴリズムよりも高速でメモリ消費の少ない実大規模文書データセットについて実験を行った。
性能解析の結果,SIVFは類似性の少ない計算よりも,キャッシュミス数や分岐予測ミス数の性能劣化係数を抑えることにより,より高速に実現できることがわかった。
関連論文リスト
- Randomized Dimension Reduction with Statistical Guarantees [0.27195102129095]
この論文は、高速な実行と効率的なデータ利用のためのアルゴリズムをいくつか探求している。
一般化と分散性を向上する様々なデータ拡張を組み込んだ学習アルゴリズムに着目する。
具体的には、第4章では、データ拡張整合正則化のための複雑性分析のサンプルを提示する。
論文 参考訳(メタデータ) (2023-10-03T02:01:39Z) - Performance Embeddings: A Similarity-based Approach to Automatic
Performance Optimization [71.69092462147292]
パフォーマンス埋め込みは、アプリケーション間でパフォーマンスチューニングの知識伝達を可能にする。
本研究では, 深層ニューラルネットワーク, 密度およびスパース線形代数合成, および数値風速予測ステンシルのケーススタディにおいて, この伝達チューニング手法を実証する。
論文 参考訳(メタデータ) (2023-03-14T15:51:35Z) - Fast conformational clustering of extensive molecular dynamics
simulation data [19.444636864515726]
本稿では,長い軌道の高速なコンフォーメーションクラスタリングを実現するために,教師なしのデータ処理ワークフローを提案する。
我々は密度に基づく空間クラスタリングアルゴリズム(HDBSCAN)と2つの次元削減アルゴリズム(cc_analysisとEncodermap)を組み合わせる。
4つのテストシステムの助けを借りて、このクラスタリングワークフローの機能とパフォーマンスを説明します。
論文 参考訳(メタデータ) (2023-01-11T14:36:43Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳(メタデータ) (2022-10-21T15:56:13Z) - Random projections and Kernelised Leave One Cluster Out
Cross-Validation: Universal baselines and evaluation tools for supervised
machine learning for materials properties [10.962094053749093]
1つのクラスタ・アウト・クロス・バリデーション(LOCO-CV)は、これまで目に見えない材料群を予測するアルゴリズムの性能を測定する方法として導入された。
コンポジションベース表現の徹底的な比較を行い,カーネル近似関数を用いてLOCO-CVアプリケーションの拡張を行う方法について検討する。
テストされたほとんどのタスクにおいて、ドメイン知識は機械学習のパフォーマンスを向上しないが、バンドギャップ予測は例外である。
論文 参考訳(メタデータ) (2022-06-17T15:39:39Z) - Large-scale Optimization of Partial AUC in a Range of False Positive
Rates [51.12047280149546]
ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。
近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。
提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
論文 参考訳(メタデータ) (2022-03-03T03:46:18Z) - AsySQN: Faster Vertical Federated Learning Algorithms with Better
Computation Resource Utilization [159.75564904944707]
垂直連合学習(VFL)のための非同期準ニュートン(AsySQN)フレームワークを提案する。
提案アルゴリズムは、逆ヘッセン行列を明示的に計算することなく、近似して降下ステップをスケールする。
本稿では,非同期計算を採用することにより,計算資源の有効利用が期待できることを示す。
論文 参考訳(メタデータ) (2021-09-26T07:56:10Z) - Fast and Robust Iterative Closest Point [32.42799285301607]
イテレーティブ・クローズト・ポイント(ICP)は、2つの点集合間の剛性登録のための基本技術である。
Sparse ICPのような最近の研究は、計算速度を犠牲にしてスパース性最適化によって堅牢性を達成する。
本稿では,古典的な点対点ICPを最大化最小化(MM)アルゴリズムとして扱えることを示す。
論文 参考訳(メタデータ) (2020-07-15T11:32:53Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳(メタデータ) (2020-05-22T23:07:42Z) - 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) - Inverted-File k-Means Clustering: Performance Analysis [1.3955252961896318]
inverted-file k-means clustering algorithm (IVF) は、潜在的に多数のクラスを持つ大規模なスパースデータセットに適したアルゴリズムである。
我々は,IVFが設計アルゴリズムよりも優れた性能を実現することを実験的に実証した。
論文 参考訳(メタデータ) (2020-02-21T02:20:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。