論文の概要: Ranking Vectors Clustering: Theory and Applications

• arxiv url: http://arxiv.org/abs/2507.12583v1
• Date: Wed, 16 Jul 2025 19:00:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-18 20:10:24.251368
• Title: Ranking Vectors Clustering: Theory and Applications
• Title（参考訳）: ランク付けベクトルクラスタリング:理論と応用
• Authors: Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee,
• Abstract要約: k-セントロイドランキングベクタークラスタリング問題(KRC)について検討する。 古典的なk平均クラスタリング(KMC)とは異なり、KRCは観測とセントロイドの両方をランクベクトルに制限する。 我々は,KMC の初期解を反復的に洗練する効率的な近似アルゴリズム KRCA を開発した。
• 参考スコア（独自算出の注目度）: 2.456159043970008
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of clustering ranking vectors, where each vector represents preferences as an ordered list of distinct integers. Specifically, we focus on the k-centroids ranking vectors clustering problem (KRC), which aims to partition a set of ranking vectors into k clusters and identify the centroid of each cluster. Unlike classical k-means clustering (KMC), KRC constrains both the observations and centroids to be ranking vectors. We establish the NP-hardness of KRC and characterize its feasible set. For the single-cluster case, we derive a closed-form analytical solution for the optimal centroid, which can be computed in linear time. To address the computational challenges of KRC, we develop an efficient approximation algorithm, KRCA, which iteratively refines initial solutions from KMC, referred to as the baseline solution. Additionally, we introduce a branch-and-bound (BnB) algorithm for efficient cluster reconstruction within KRCA, leveraging a decision tree framework to reduce computational time while incorporating a controlling parameter to balance solution quality and efficiency. We establish theoretical error bounds for KRCA and BnB. Through extensive numerical experiments on synthetic and real-world datasets, we demonstrate that KRCA consistently outperforms baseline solutions, delivering significant improvements in solution quality with fast computational times. This work highlights the practical significance of KRC for personalization and large-scale decision making, offering methodological advancements and insights that can be built upon in future studies.
• Abstract（参考訳）: ランク付けベクターのクラスタリングの問題について検討し、各ベクターが選好を異なる整数の順序リストとして表す。 具体的には、ランキングベクトルの集合をkクラスタに分割し、各クラスタのセントロイドを特定することを目的とした、k-セントロイドランキングベクトルクラスタリング問題(KRC)に焦点を当てる。 古典的なk平均クラスタリング(KMC)とは異なり、KRCは観測とセントロイドの両方をランクベクトルに制限する。 我々は、KRCのNP硬度を確立し、その実現可能な集合を特徴づける。 単一クラスタの場合、線形時間で計算できる最適セントロイドに対する閉形式解析解を導出する。 KRCの計算問題に対処するため,基本解と呼ばれるKMCの初期解を反復的に洗練する効率的な近似アルゴリズムであるKRCAを開発した。 さらに、KRCA内の効率的なクラスタ再構築のための分岐結合(BnB)アルゴリズムを導入し、決定木フレームワークを利用して計算時間を短縮し、制御パラメータを組み込んで解の質と効率のバランスをとる。 KRCA と BnB の理論的誤差境界を確立する。 合成および実世界のデータセットに関する広範な数値実験を通じて、KRCAはベースラインの解より一貫して優れ、高速な計算時間で解の質を大幅に向上させることを示した。 この研究は、個人化と大規模意思決定におけるKRCの実践的重要性を強調し、今後の研究で構築可能な方法論的進歩と洞察を提供する。

関連論文リスト

• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  本研究では,Fair SC問題を凸関数(DC)フレームワークの差内にキャストすることで,フェアスペクトルクラスタリング(Fair SC)のための新しい効率的な手法を提案する。 本研究では,各サブプロブレムを効率よく解き,計算効率が先行処理よりも高いことを示す。
  論文  参考訳（メタデータ） (2025-06-09T18:46:27Z)
• K*-Means: A Parameter-free Clustering Algorithm [55.20132267309382]
  k*-meansは、kや他のパラメータをセットする必要がない新しいクラスタリングアルゴリズムである。 最小記述長の原理を用いて、クラスタの分割とマージによって最適なクラスタ数k*を自動的に決定する。 k*-平均が収束することが保証されることを証明し、kが未知のシナリオにおいて既存のメソッドよりも著しく優れていることを実験的に証明する。
  論文  参考訳（メタデータ） (2025-05-17T08:41:07Z)
• Nearest Neighbour Equilibrium Clustering [6.635604919499181]
  新しく直感的に近づいた近傍のクラスタリングアルゴリズムでは、クラスタはそのサイズと凝集性のバランスをとる平衡条件によって定義される。 平衡条件の定式化は、各点のクラスタへのアライメントの強さの定量化を可能にし、これらのクラスタアライメントの強度は、提案されたアプローチを完全に自動化可能なモデル選択基準に自然に導かれる。
  論文  参考訳（メタデータ） (2025-03-27T12:16:54Z)
• How to optimize K-means? [8.206124331448931]
  センターベースのクラスタリングアルゴリズム(例えばK平均)はクラスタリングタスクに人気があるが、通常は複雑なデータセットで高い精度を達成するのに苦労する。 主な理由は、従来のセンターベースのクラスタリングアルゴリズムが、クラスタ内のクラスタリングセンターを1つだけ特定しているからです。 そこで本研究では,ECACと呼ばれる汎用最適化手法を提案し,異なる中心型クラスタリングアルゴリズムを最適化する。
  論文  参考訳（メタデータ） (2025-03-25T03:37:52Z)
• Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient [0.5939858158928473]
  本稿では,分類データクラスタリングにおける最適kを推定するアルゴリズムk-SCCを提案する。 k-SCCの性能を比較するために, 合成データセットと実データセットの比較実験を行った。
  論文  参考訳（メタデータ） (2025-01-26T14:29:11Z)
• 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)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。 本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。 実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
  論文  参考訳（メタデータ） (2022-07-05T05:00:38Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)

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

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