論文の概要: Accelerating the k-means++ Algorithm by Using Geometric Information

• arxiv url: http://arxiv.org/abs/2408.13189v1
• Date: Fri, 23 Aug 2024 16:15:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-26 14:30:30.841209
• Title: Accelerating the k-means++ Algorithm by Using Geometric Information
• Title（参考訳）: 幾何学情報を用いたk-means++アルゴリズムの高速化
• Authors: Guillem Rodríguez Corominas, Maria J. Blesa, Christian Blum,
• Abstract要約: 実験により、アクセラレーションされたバージョンは、訪問点数や距離計算の点で標準k-means++バージョンより優れていることが示された。 追加実験では、複数のジョブで並列に実行されるアルゴリズムの挙動を示し、メモリ性能が実用的なスピードアップにどのように影響するかを調べる。
• 参考スコア（独自算出の注目度）: 1.6795461001108096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose an acceleration of the exact k-means++ algorithm using geometric information, specifically the Triangle Inequality and additional norm filters, along with a two-step sampling procedure. Our experiments demonstrate that the accelerated version outperforms the standard k-means++ version in terms of the number of visited points and distance calculations, achieving greater speedup as the number of clusters increases. The version utilizing the Triangle Inequality is particularly effective for low-dimensional data, while the additional norm-based filter enhances performance in high-dimensional instances with greater norm variance among points. Additional experiments show the behavior of our algorithms when executed concurrently across multiple jobs and examine how memory performance impacts practical speedup.
• Abstract（参考訳）: 本稿では,幾何情報,特に三角不等式と追加のノルムフィルタを用いた正確なk-means++アルゴリズムの高速化と2段階のサンプリング手順を提案する。 我々の実験では、アクセラレーションされたバージョンは訪問点数や距離計算の点で標準k-means++バージョンよりも優れており、クラスタ数が増加するにつれて高速化が達成されている。 三角不等式を利用するバージョンは、低次元データに特に有効であるが、追加のノルムベースフィルタは、点間のノルムのばらつきが大きい高次元インスタンスの性能を高める。 追加実験では、複数のジョブで並列に実行されるアルゴリズムの挙動を示し、メモリ性能が実用的なスピードアップにどのように影響するかを調べる。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。 推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。 提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。 我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。 また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
  論文  参考訳（メタデータ） (2022-06-27T10:54:24Z)
• Fast Single-Core K-Nearest Neighbor Graph Computation [0.0]
  本論文では,Wei Dongらによるランタイム"NN-Descent"アルゴリズムを最適化したC実装を提案する。 低次元および高次元データセットの性能を改善するための様々な実装最適化について説明する。 l2距離メートル法の制限により、高次元データセットの性能を大幅に向上させるブロックされた距離評価が利用可能となる。
  論文  参考訳（メタデータ） (2021-12-13T13:16:30Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。 エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。 これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
  論文  参考訳（メタデータ） (2020-09-15T17:28:42Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。 古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-03T20:37:05Z)
• Efficient Nonnegative Tensor Factorization via Saturating Coordinate Descent [16.466065626950424]
  本稿では,要素選択手法を用いた高速かつ効率的なNTFアルゴリズムを提案する。 経験的解析により,提案アルゴリズムはテンソルサイズ,密度,ランクの点でスケーラブルであることがわかった。
  論文  参考訳（メタデータ） (2020-03-07T12:51:52Z)

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

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