論文の概要: Fast and explainable clustering in the Manhattan and Tanimoto distance

• arxiv url: http://arxiv.org/abs/2601.08781v1
• Date: Tue, 13 Jan 2026 18:14:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-14 18:27:19.323279
• Title: Fast and explainable clustering in the Manhattan and Tanimoto distance
• Title（参考訳）: マンハッタンと谷本距離における高速かつ説明可能なクラスタリング
• Authors: Stefan Güttel, Kaustubh Roy,
• Abstract要約: 我々はCLASSIXをマンハッタン距離や谷本距離など他の距離に拡張する。 実際の化学指紋のベンチマークでは、CLASSIX TanimotoはTaylor-Butinaアルゴリズムの約30倍、DBSCANの約80倍高速である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The CLASSIX algorithm is a fast and explainable approach to data clustering. In its original form, this algorithm exploits the sorting of the data points by their first principal component to truncate the search for nearby data points, with nearness being defined in terms of the Euclidean distance. Here we extend CLASSIX to other distance metrics, including the Manhattan distance and the Tanimoto distance. Instead of principal components, we use an appropriate norm of the data vectors as the sorting criterion, combined with the triangle inequality for search termination. In the case of Tanimoto distance, a provably sharper intersection inequality is used to further boost the performance of the new algorithm. On a real-world chemical fingerprint benchmark, CLASSIX Tanimoto is about 30 times faster than the Taylor--Butina algorithm, and about 80 times faster than DBSCAN, while computing higher-quality clusters in both cases.
• Abstract（参考訳）: CLASSIXアルゴリズムは、高速で説明可能なデータクラスタリング手法である。 このアルゴリズムは、最初の主成分によるデータポイントのソートを利用して、近くにあるデータポイントの探索を、ユークリッド距離の観点で定義する。 ここではCLASSIXをマンハッタン距離や谷本距離など他の距離に拡張する。 主成分の代わりに、データベクトルの適切なノルムをソート基準として使用し、探索終了のための三角形の不等式と組み合わせる。 谷本距離の場合、新しいアルゴリズムの性能を高めるために、証明可能なよりシャープな交叉不等式が用いられる。 実際の化学指紋のベンチマークでは、CLASSIX TanimotoはTaylor-Butinaアルゴリズムの約30倍、DBSCANの約80倍の速度で、両方のケースで高品質なクラスタを計算している。

関連論文リスト

• Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets [16.768212375976546]
  スパースANNSのための新しいデータ構造とアルゴリズム手法を提案する。 我々の貢献は、スパースベクトルに対する理論的に基底化されたスケッチアルゴリズムから、それらの有効次元を減少させるものまで様々である。 我々の最終アルゴリズムは耐震性と呼ばれ、大規模ベンチマークデータセット上で高精度でミリ秒以下のレイテンシに達する。
  論文  参考訳（メタデータ） (2025-09-29T14:02:45Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
  論文  参考訳（メタデータ） (2025-06-06T22:09:44Z)
• Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
  表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。 木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-10-19T14:02:42Z)
• Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
  時間的距離は、計画、制御、強化学習のための多くのアルゴリズムの中心にある。 このような時間的距離を設定内で定義しようとする以前の試みは、重要な制限によって妨げられている。 比較学習によって学習された後継特徴が,三角形の不等式を満たす時間的距離を形成することを示す。
  論文  参考訳（メタデータ） (2024-06-24T19:36:45Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
  この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。 分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
  論文  参考訳（メタデータ） (2022-03-02T09:29:40Z)
• K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
  本稿では,k-meansに基づく改良された階層型アルゴリズムであるk-splitsを紹介する。 提案手法の主な利点は,精度と速度である。
  論文  参考訳（メタデータ） (2021-10-09T23:02:57Z)
• Relational Algorithms for k-means Clustering [17.552485682328772]
  本稿では,関係アルゴリズムモデルにおいて効率的なk平均近似アルゴリズムを提案する。 実行時間は潜在的に$N$よりも小さくなり、リレーショナルデータベースが表すデータポイントの数はクラスタ化される。
  論文  参考訳（メタデータ） (2020-08-01T23:21:40Z)

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

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