論文の概要: Sparse Partitioning Around Medoids

• arxiv url: http://arxiv.org/abs/2309.02557v1
• Date: Tue, 5 Sep 2023 19:52:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 17:35:50.594085
• Title: Sparse Partitioning Around Medoids
• Title（参考訳）: メドイド周囲のスパース分割
• Authors: Lars Lenssen and Erich Schubert
• Abstract要約: パーティショニング・アラウンド・メドイド (PAM, k-メドイド) は任意の距離関数や類似性を持つ一般的なクラスタリング手法である。 FastPAMは最近、大きな問題に適用できるように、大きな k の高速化を導入したが、このメソッドは N で実行時二次性を持つ。 本稿では,例えば道路網などのグラフデータにおいて,この問題のスパースかつ非対称な変種について論じる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Partitioning Around Medoids (PAM, k-Medoids) is a popular clustering technique to use with arbitrary distance functions or similarities, where each cluster is represented by its most central object, called the medoid or the discrete median. In operations research, this family of problems is also known as facility location problem (FLP). FastPAM recently introduced a speedup for large k to make it applicable for larger problems, but the method still has a runtime quadratic in N. In this chapter, we discuss a sparse and asymmetric variant of this problem, to be used for example on graph data such as road networks. By exploiting sparsity, we can avoid the quadratic runtime and memory requirements, and make this method scalable to even larger problems, as long as we are able to build a small enough graph of sufficient connectivity to perform local optimization. Furthermore, we consider asymmetric cases, where the set of medoids is not identical to the set of points to be covered (or in the interpretation of facility location, where the possible facility locations are not identical to the consumer locations). Because of sparsity, it may be impossible to cover all points with just k medoids for too small k, which would render the problem unsolvable, and this breaks common heuristics for finding a good starting condition. We, hence, consider determining k as a part of the optimization problem and propose to first construct a greedy initial solution with a larger k, then to optimize the problem by alternating between PAM-style "swap" operations where the result is improved by replacing medoids with better alternatives and "remove" operations to reduce the number of k until neither allows further improving the result quality. We demonstrate the usefulness of this method on a problem from electrical engineering, with the input graph derived from cartographic data.
• Abstract（参考訳）: 分裂 メドイド (PAM, k-メドイド) は任意の距離関数や類似性を持つ一般的なクラスタリング技法であり、各クラスタはメドイド (medoid) と呼ばれる最も中心的な対象によって表現される。 運用研究においては、この問題のファシリティ・ロケーション・イシュー(FLP)とも呼ばれる。 fastpamは最近、大きなkの高速化を導入し、より大きな問題に適用できるようにしましたが、nではまだ実行時二乗法があります。本章では、道路網などのグラフデータで使用するために、この問題のばらばらで非対称な変種について論じます。 空間性を活用することで、局所最適化を行うのに十分な接続性のグラフを構築できる限り、二次的なランタイムとメモリ要件を回避し、このメソッドをさらに大きな問題にスケーラブルにすることができる。 さらに, メドロイド群が被被覆点の集合と同一でない非対称の場合(あるいは施設位置の解釈において, 可能な施設位置が消費者の位置と同一でない場合)を考える。 空間性のため、小さな k に対して k 個のメドイドで全ての点をカバーすることは不可能であり、この問題は解決不可能となり、良い開始条件を見つけるための一般的なヒューリスティックスを破ることになる。 そこで我々は,k を最適化問題の一部として決定することを検討するとともに,まずより大きい k で欲求初期解を構築することを提案する。次に,医薬をより良い代替品に置き換えることで結果が改善される PAM スタイルの "スワップ" 演算を交互に行い,k の数を減らし,結果の質をさらに向上させることは不可能である。 本手法の有効性を,地図データから入力グラフを抽出し,電気工学的な問題に対して示す。

関連論文リスト

• A cutting plane algorithm for globally solving low dimensional k-means clustering problems [4.5594982923247995]
  我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。 これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。 本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
  論文  参考訳（メタデータ） (2024-02-21T07:55:33Z)
• Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces [5.534626267734822]
  本稿では,低次元空間における2つの点間のGromov-Wasserstein問題を計算するための枠組みを提案する。 これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。
  論文  参考訳（メタデータ） (2023-07-18T08:20:56Z)
• Decentralized Riemannian natural gradient methods with Kronecker-product approximations [11.263837420265594]
  本稿では,分散化多様体最適化問題の解法として,効率的な分散化自然勾配降下法(DRNGD)を提案する。 クロネッカー因子を介して通信を行うことにより、RFIMの高品質な近似を低コストで得ることができる。
  論文  参考訳（メタデータ） (2023-03-16T19:36:31Z)
• Regularization and Optimization in Model-Based Clustering [4.096453902709292]
  k-平均アルゴリズムの変種は、本質的に同じ球面ガウスの混合と、そのような分布から大きく逸脱するデータに適合する。 一般のGMMに対してより効率的な最適化アルゴリズムを開発し、これらのアルゴリズムと正規化戦略を組み合わせ、過度な適合を避ける。 これらの結果から, GMM と k-means 法の間の現状に新たな光を当て, 一般 GMM をデータ探索に利用することが示唆された。
  論文  参考訳（メタデータ） (2023-02-05T18:22:29Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  幾何学的中央値 (textGm) は、未破損データのロバストな推定を達成するための統計学における古典的な方法である。 本稿では,テキストscGmを一度に選択した座標ブロックにのみ適用することにより,スムーズな非テキスト問題に対して0.5の分解点を保持することができることを示す。
  論文  参考訳（メタデータ） (2021-06-16T15:55:50Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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