論文の概要: An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering
- arxiv url: http://arxiv.org/abs/2111.15571v1
- Date: Tue, 30 Nov 2021 17:08:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-01 16:53:33.910292
- Title: An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering
- Title（参考訳）: 半教師付き最小二乗クラスタリングのためのエクササイズアルゴリズム
- Authors: Veronica Piccialli, Anna Russo Russo, Antonio M. Sudoso
- Abstract要約: 半教師付きMSSCのための分岐結合アルゴリズムを提案する。
背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。
提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
- 参考スコア（独自算出の注目度）: 0.5801044612920815
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum sum-of-squares clustering (MSSC), or k-means type clustering, is
traditionally considered an unsupervised learning task. In recent years, the
use of background knowledge to improve the cluster quality and promote
interpretability of the clustering process has become a hot research topic at
the intersection of mathematical optimization and machine learning research.
The problem of taking advantage of background information in data clustering is
called semi-supervised or constrained clustering. In this paper, we present a
new branch-and-bound algorithm for semi-supervised MSSC, where background
knowledge is incorporated as pairwise must-link and cannot-link constraints.
For the lower bound procedure, we solve the semidefinite programming relaxation
of the MSSC discrete optimization model, and we use a cutting-plane procedure
for strengthening the bound. For the upper bound, instead, by using integer
programming tools, we propose an adaptation of the k-means algorithm to the
constrained case. For the first time, the proposed global optimization
algorithm efficiently manages to solve real-world instances up to 800 data
points with different combinations of must-link and cannot-link constraints and
with a generic number of features. This problem size is about four times larger
than the one of the instances solved by state-of-the-art exact algorithms.
- Abstract（参考訳）: msc(minimum sum-of-squares clustering)またはk-means型クラスタリング(k-means型クラスタリング)は、伝統的に教師なし学習タスクであると考えられている。
近年,クラスタの品質向上とクラスタリングプロセスの解釈可能性向上のための背景知識の利用が,数学的最適化と機械学習研究の交わりにおいてホットな研究課題となっている。
データクラスタリングにおける背景情報を利用する問題は、半教師付きまたは制約付きクラスタリングと呼ばれる。
本稿では,半教師付きmsscに対する新しい分岐・境界アルゴリズムを提案する。
下位境界法では,MSSC離散最適化モデルの半定プログラム緩和を解くとともに,切断平面法を用いて境界の強化を行う。
上界に対して、代わりに整数プログラミングツールを用いて、k-meansアルゴリズムを制約されたケースに適応させることを提案する。
提案したグローバル最適化アルゴリズムは,M must-link と cannot-link の制約を交互に組み合わせることで,実世界のインスタンスを最大800個のデータポイントで効率的に解決する。
この問題のサイズは、最先端の正確なアルゴリズムによって解決されたインスタンスの約4倍である。
関連論文リスト
- Memetic Differential Evolution Methods for Semi-Supervised Clustering [1.0256438517258686]
我々は、背景知識がインスタンスレベルの制約の形で与えられる半教師付き最小値クラスタリング(MSSC)問題に対処する。
本稿では,非教師付きクラスタリング文献で最近提案された最先端のフレームワークを直接拡張する,微分進化パラダイムに基づく新しいメメティクス戦略を提案する。
論文 参考訳（メタデータ） (2024-03-07T08:37:36Z) - Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。
制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
論文 参考訳（メタデータ） (2024-01-23T07:16:32Z) - Large-scale Fully-Unsupervised Re-Identification [78.47108158030213]
大規模未ラベルデータから学ぶための2つの戦略を提案する。
第1の戦略は、近傍関係に違反することなく、それぞれのデータセットサイズを減らすために、局所的な近傍サンプリングを行う。
第2の戦略は、低時間上限の複雑さを持ち、メモリの複雑さを O(n2) から O(kn) に k n で還元する新しい再帰的手法を利用する。
論文 参考訳（メタデータ） (2023-07-26T16:19:19Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Neural Capacitated Clustering [6.155158115218501]
本稿では,クラスタセンターへのポイントの割り当て確率を予測するニューラルネットワークを学習する,容量クラスタリング問題(CCP)の新しい手法を提案する。
人工データと2つの実世界のデータセットに関する実験では、我々のアプローチは文学の最先端の数学的および解法よりも優れています。
論文 参考訳（メタデータ） (2023-02-10T09:33:44Z) - Global Optimization for Cardinality-constrained Minimum Sum-of-Squares
Clustering via Semidefinite Programming [1.3053649021965603]
最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。
本稿では,分枝切断法に基づく大域的最適化手法を提案する。
上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
論文 参考訳（メタデータ） (2022-09-19T10:19:06Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Meta Clustering Learning for Large-scale Unsupervised Person
Re-identification [124.54749810371986]
メタクラスタリング学習(MCL)と呼ばれる「大規模タスクのための小さなデータ」パラダイムを提案する。
MCLは、第1フェーズのトレーニングのためにコンピューティングを節約するためにクラスタリングを介して、未ラベルデータのサブセットを擬似ラベル付けするのみである。
提案手法は計算コストを大幅に削減すると同時に,従来よりも優れた性能を実現している。
論文 参考訳（メタデータ） (2021-11-19T04:10:18Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。
我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
論文 参考訳（メタデータ） (2020-10-22T15:58:35Z) - A semi-supervised sparse K-Means algorithm [3.04585143845864]
クラスタリングに必要な機能のサブグループを検出するために、教師なしスパースクラスタリング手法を用いることができる。
半教師付き手法では、ラベル付きデータを使用して制約を作成し、クラスタリングソリューションを強化することができる。
提案アルゴリズムは,他の半教師付きアルゴリズムの高性能性を保ち,また,情報的特徴から情報的特徴を識別する能力も保持していることを示す。
論文 参考訳（メタデータ） (2020-03-16T02:05:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。