論文の概要: An Algebraic Approach to Constrained K-means Clustering

• arxiv url: http://arxiv.org/abs/2610.14932v1
• Date: Sat, 10 Oct 2026 14:05:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-20 03:21:50.631421
• Title: An Algebraic Approach to Constrained K-means Clustering
• Title（参考訳）: 制約付きK平均クラスタリングへの代数的アプローチ
• Abstract要約: そこで本研究では,k-meansクラスタリングの手法を提案する。 このアルゴリズムは最適化前にGrbnerベースを使用して制約を単純化する。 また、最適化前に制約セットが実行可能な代入を持つかどうかを検出することもできる。
• 参考スコア（独自算出の注目度）: 0.22940141855172028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is typically performed using only object features, although additional information about relationships between objects may be available and can be incorporated through constraints. Among these, pairwise constraints require two objects to belong to the same cluster or to different clusters. Several extensions of the k-means algorithm accommodate such constraints, but they sometimes fail to find a feasible assignment or incur high computational cost. Motivated by these limitations, we propose an algebraic approach to k-means clustering with pairwise constraints. The algorithm simplifies the constraints using Gröbner bases before optimization, improving the efficiency of cluster assignment. It can also detect whether the constraint set has a feasible assignment before optimization. Comparative experiments with existing algorithms showed that the proposed algorithm achieved comparable or better clustering quality at a lower computational cost, particularly when the numbers of constraints and clusters were small.
• Abstract（参考訳）: クラスタリングは通常、オブジェクトの特徴のみを使用して実行されるが、オブジェクト間の関係に関する追加情報は利用可能であり、制約を通じて組み込むことができる。 これらの中で、ペアワイズ制約は、2つのオブジェクトを同じクラスタまたは異なるクラスタに属さなければならない。 k平均アルゴリズムのいくつかの拡張はそのような制約を満たすが、実現可能な代入を見つけられなかったり、高い計算コストを被ったりすることがある。 これらの制約を動機として,k-meansクラスタリングの代数的手法を提案する。 このアルゴリズムは、最適化前にGröbnerベースを使用して制約を単純化し、クラスタ割り当ての効率を向上させる。 また、最適化前に制約セットが実行可能な代入を持つかどうかを検出することもできる。 既存のアルゴリズムとの比較実験により,提案アルゴリズムは計算コストの低いクラスタリング品質,特に制約数やクラスタ数が少ない場合において,同等あるいは優れたクラスタリング品質を達成できた。

関連論文リスト

• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• A Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems [24.208152437317768]
  我々は、半教師付きクラスタリングタスクを、与えられたデータセットに関連付けられたグラフ上のパーティショニング問題とみなす。 このモデルを効率的に解くためにブロック座標降下アルゴリズムを提案する。 穏やかな仮定の下で、理論的には必須リンク制約を満たすクラスタを構築することができる。
  論文  参考訳（メタデータ） (2025-03-06T14:02:28Z)
• A column generation algorithm with dynamic constraint aggregation for minimum sum-of-squares clustering [0.30693357740321775]
  最小2乗クラスタリング問題(MSSC)は、$n$のデータポイントを$k$クラスタに分割する問題を指す。 カラム生成(CG)と動的制約集約(DCA)を組み合わせた大規模MSSCインスタンスの効率的な解法を提案する。
  論文  参考訳（メタデータ） (2024-10-08T16:51:28Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Clustering to the Fewest Clusters Under Intra-Cluster Dissimilarity Constraints [0.0]
  均等なクラスタリングは、密度も期待されるクラスの数にも依存せず、相似性の閾値にも依存します。 このクラスタリング問題に対する様々な実践的ソリューション間のトレードオフを特定するために,適切なクラスタリングアルゴリズムをレビューし,評価する。
  論文  参考訳（メタデータ） (2021-09-28T12:02:18Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)

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

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