論文の概要: A Global Optimization Algorithm for K-Center Clustering of One Billion
Samples
- arxiv url: http://arxiv.org/abs/2301.00061v1
- Date: Fri, 30 Dec 2022 21:53:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 16:06:15.107644
- Title: A Global Optimization Algorithm for K-Center Clustering of One Billion
Samples
- Title(参考訳): 10億サンプルのK中心クラスタリングのための大域的最適化アルゴリズム
- Authors: Jiayang Ren, Ningning You, Kaixun Hua, Chaojie Ji, Yankai Cao
- Abstract要約: 本稿では,K中心クラスタリング問題に対する実用的なグローバル最適化アルゴリズムを提案する。
クラスタ内の最大距離を最小化するために、クラスタの中心としてKサンプルを選択することを目的としている。
我々のアルゴリズムは、合成および実世界の全てのデータセットにおいて、目的関数を平均25.8%削減することができる。
- 参考スコア(独自算出の注目度): 3.4998703934432682
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a practical global optimization algorithm for the
K-center clustering problem, which aims to select K samples as the cluster
centers to minimize the maximum within-cluster distance. This algorithm is
based on a reduced-space branch and bound scheme and guarantees convergence to
the global optimum in a finite number of steps by only branching on the regions
of centers. To improve efficiency, we have designed a two-stage decomposable
lower bound, the solution of which can be derived in a closed form. In
addition, we also propose several acceleration techniques to narrow down the
region of centers, including bounds tightening, sample reduction, and
parallelization. Extensive studies on synthetic and real-world datasets have
demonstrated that our algorithm can solve the K-center problems to global
optimal within 4 hours for ten million samples in the serial mode and one
billion samples in the parallel mode. Moreover, compared with the
state-of-the-art heuristic methods, the global optimum obtained by our
algorithm can averagely reduce the objective function by 25.8% on all the
synthetic and real-world datasets.
- Abstract(参考訳): 本稿では,クラスタ内距離の最大化を目的とした,K中心クラスタリング問題に対する実用的なグローバル最適化アルゴリズムを提案する。
このアルゴリズムは、縮小空間分岐と境界スキームに基づいており、中心の領域に分岐するだけで、有限個のステップでグローバル最適への収束を保証する。
効率を向上させるため,我々は2段階の分解可能な下限を設計,その解は閉じた形で導出できることを示した。
さらに,本研究では,境界の締め付け,サンプルの削減,並列化など,中心領域を狭めるいくつかの加速手法を提案する。
合成および実世界のデータセットに関する大規模な研究により、我々のアルゴリズムは、シリアルモードで1000万サンプル、並列モードで10億サンプルに対して、K中心の問題を4時間以内にグローバルに最適に解けることを示した。
さらに,最先端のヒューリスティック法と比較して,本アルゴリズムにより得られた大域的最適度は,合成および実世界のデータセットすべてにおいて,平均25.8%の目標関数を減少させることができる。
関連論文リスト
- Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization [0.3069335774032178]
K平均クラスタリングはデータマイニングの基盤であるが、その効率は大量のデータセットに直面すると悪化する。
可変近傍探索(VNS)メタヒューリスティックを利用して,K平均クラスタリングをビッグデータに最適化する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-10-18T15:43:34Z) - Self-Supervised Graph Embedding Clustering [70.36328717683297]
K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。
本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
論文 参考訳(メタデータ) (2024-09-24T08:59:51Z) - Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
ファジィK平均クラスタリングは教師なしデータ分析において重要な手法である。
本稿では,クラスタセントロイドへの依存を完全に排除する,ファジィテクストK-Meansクラスタリングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-07T12:25:03Z) - A cutting plane algorithm for globally solving low dimensional k-means
clustering problems [4.5594982923247995]
我々は、低次元データを持つインスタンスのk-means問題を考え、これを構造的凹面割り当て問題として定式化する。
これにより、低次元構造を利用して、妥当な時間で大域的最適性に問題を解くことができる。
本論文は,グローバル最適化理論の手法を組み合わせて手順を高速化し,数値的な結果を提供する。
論文 参考訳(メタデータ) (2024-02-21T07:55:33Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳(メタデータ) (2023-06-21T17:03:22Z) - Neural Capacitated Clustering [6.155158115218501]
本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。
人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
論文 参考訳(メタデータ) (2023-02-10T09:33:44Z) - On the Global Solution of Soft k-Means [159.23423824953412]
本稿では,ソフトk-平均問題の解法を全世界で提案する。
ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
論文 参考訳(メタデータ) (2022-12-07T12:06:55Z) - An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文 参考訳(メタデータ) (2021-11-30T17:08:53Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time
Warping [57.316437798033974]
本研究では,トラジェクトリの集中型クラスタリングの問題について考察する。
我々はDTWの連続バージョンを距離測定として使用することを提案し、これをCDTW(Continuous dynamic time warping)と呼ぶ。
一連の軌道から中心を計算し、その後反復的に改善する実践的な方法を示す。
論文 参考訳(メタデータ) (2020-12-01T13:17:27Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳(メタデータ) (2020-10-22T15:58:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。