技術要約：高速かつ効果的なユークリッド反クラスタリング手法

問題の定義

本論文は、NP困難な組合せ最適化タスクであるユークリッド反クラスタリング（Euclidean Anticlustering）問題を取り扱う。目的は、$D$次元ユークリッド空間内の特徴ベクトルとして表される$N$個のオブジェクトを、$近似的に等しいサイズの$K$個のグループ（アンチクラスター）に分割することである。従来のクラスタリングがグループ内の距離を最小化しようとするのに対し、反クラスタリングは、同一のアンチクラスター内におけるオブジェクト間の二乗ユークリッド距離の総和を最大化することを目指す。

目標は、各アンチクラスターがデータセット全体を代表するように、メンバー間の非類似性を最大限に高めるグループを作成することである。この問題は、社会科学（比較可能な被験者グループの作成）、生物医学研究（シーケンシングにおけるバッチ効果の抑制）、および機械学習（確率的勾配降下法のためのミニバッチ生成や、交差検証のための代表的なフォールドの作成）など、さまざまな分野で発生する。

特定のバリアントとして、オブジェクトが特定のカテゴリに属し、各アンチクラスターが各カテゴリから等数（またはそれに近い数）のオブジェクトを含む必要があるカテゴリ付きユークリッド反クラスタリングも検討されている。さらに、この問題は、カットコスト（グループ間のエッジ重みの総和）を最小化することを目的とする**バランスKカット（Balanced K-cut）**問題とも関連している。これは、完全グラフにおけるユークリッド重みを用いた、グループ内の二乗距離の総和を最大化することと数学的に等価である。

既存の手法は、重大なスケーラビリティの課題に直面している。厳密解法（例：混合整数計画法）は、小規模なインスタンス（通常 $N \le 100$）に限定される。交換ベースの手法（例：fast-anticlustering）などのヒューリスティック手法は、全ペアの距離を計算するか、高コストな最近傍探索を行う必要があり、百万規模のデータセットや大きな $K$ の値に対しては計算量的に実行不可能となることが多い。

手法：割り当てベースの反クラスタリング（ABA）アルゴリズム

著者らは、**割り当てベースの反クラスタリング（Assignment-Based Anticlustering: ABA）**と呼ばれる新しい構成的ヒューリスティックを提案している。核心となる革新は、フルサイズの $N \times N$ 距離行列の計算を回避し、一連の割り当て問題を解くためにユークリッド二乗和の性質を活用することにある。

コアメカニズム

1. グローバル・セントロイドとランキング： アルゴリズムはまず、データセットのグローバル・セントロイド（全体の重心）を計算する。その後、すべてのオブジェクトは、このグローバル・セントロイドからの二乗ユークリッド距離の降順に基づいてランク付けされる。
2. バッチ処理： ランク付けされたリストは、$B = \lceil N/K \rceil$ 個のバッチに分割される。最初のバッチには最も遠い $K$ 個のオブジェクトが含まれ、第2のバッチには次の $K$ 個が含まれる、という具合に進む。
3. 反復的な割り当て：
   • 最初のバッチが $K$ 個のアンチクラスターを初期化する（各オブジェクトが単一要素のアンチクラスターとなる）。
   • 後続の各バッチについて、アルゴリズムは、バッチ内の $K$ 個のオブジェクトを既存の $K$ 個のアンチクラスターに割り当てるための最大重み割り当て問題（具体的には線形割り当て問題）を解く。
   • この割り当てのためのコスト行列は、現在のバッチ内のオブジェクトと、アンチクラスターの現在のセントロイドとの間の二乗ユークリッド距離によって定義される。
   • 決定的なのは、アンチクラスター内の二乗距離の総和を最大化することは、オブジェクトとそのアンチクラスター・セントロイドとの二乗距離の総和を最大化することと等価であるという**事実1（Fact 1）**に基づいていることである。これにより、アルゴリズムはすべてのペア間の距離（$O(K^2)$）ではなく、セントロイドへの距離（$O(K)$）を計算できる。
   • 割り当ての後、アンチクラスターのセントロイドが更新される。
4. 終了： すべてのバッチが割り当てられるまでプロセスが繰り返される。アルゴリズムは、割り当てステップに支配される $O(NK^2)$ の時間で動作する。

バリアント

• カテゴリ付きABA： カテゴリ制約を扱うために、初期ランキングが修正される。オブジェクトはグローバル・セントロイドへの距離に基づいてソートされるが、その後、同じカテゴリのオブジェクトがバッチ間で均等に分散されるように再配置される。割り当て中、あるオブジェクトの割り当てがカテゴリ・バランス制約に違反する場合、対応するコスト行列のエントリに大きな負の値が設定され、その割り当てを実質的に禁止する。
• 階層的分解： 極めて大きな $K$（例：$K=100,000$）の場合、$K \times K$ の割り当て問題を解くことがボトルネックとなる。著者らは、問題を複数のレベルに分解する階層的戦略（例：まず $K_1$ 個のグループを作成し、次に各グループを $K_2$ 個に細分化する）を提案している。これにより、解の質への影響を最小限に抑えつつ、複雑度を $O(NK^2)$ から $O(N \sum K_\ell^2)$ に低減させ、実行速度を大幅に向上させる。

主な貢献

1. スケーラビリティ： 百万規模のオブジェクトや数十万規模のアンチクラスターを持つインスタンスにも対応し、数秒から数分で解決できるABAアルゴリズムの導入。これは既存の交換ベースのヒューリスティックや厳密解法の能力を超えている。
2. 解の質： 本アルゴリズムは、目的関数の値（多様性）において、最先端の手法（具体的にはRパッケージ anticlust の fast-anticlustering およびグラフ分割ツールであるMETIS）を一貫して上回る。
3. アンチクラスターの類似性： 多様性を最大化するだけでなく、ABAは高い**アンチクラスター類似性（anticluster similarity）**を本質的に生成する。アルゴリズムはあらゆる距離範囲（バッチ）からのオブジェクトをすべてのアンチクラスターに割り当てるため、結果として得られるグループは、統計的特性（内部距離の平均および分散）が類似している。これは交換ベースの手法では見落とされがちな望ましい特性である。
4. カテゴリと大きな $K$ の処理： カテゴリ制約付きの反クラスタリングおよび巨大な $K$ 値のための階層的分解戦略に関する具体的なバリアントを提供し、これらの特定の文脈において既存のアプローチに対する優れた性能を実証した。
5. 包括的な評価： 著者らは、16の多様なデータセット（表形式データからImageNetのような高次元画像データまで）にわたる広範な計算研究を実施し、ランダム分割、厳密解法（小規模インスタンス用）、および主要なヒューリスティックを含む複数のベンチマークと比較を行った。

実験結果

実験研究は、以下の3つの主要な側面においてアルゴリズムの性能を検証している。

• 主要なヒューリスティックとの比較： 16のデータセットから派生した111の全問題インスタンスにおいて、ABAは fast-anticlustering アルゴリズム（P-N5, P-R5, P-R50, P-R500）よりも一貫して高い目的関数値を達成した。大きな $K$（例：$K=5,000$）において、ABAの解は平均してP-N5よりも16%以上良く、ランダム分割よりも30%以上優れていた。
• 実行時間： ABAは数桁高速であった。ABAが大規模なインスタンスを数秒で解決した一方で、競合するヒューリスティックは2時間の制限時間内に解を見つけることができず、失敗することが多かった。例えば、ImageNet32データセット（$N \approx 1.28$ 百万）において、ABAは $K=640,000$ のインスタンスを500秒未満で解決したが、ランダム分割は実行時間内に完了した唯一の他の手法であったものの、品質は著しく低かった。
• アンチクラスターの類似性： アンチクラスター内の多様性の標準偏差および範囲といった指標は、ABAが交換ベースの手法よりもはるかにバランスの取れたグループを生成することを示した。交換ベースの手法は、多様性のレベルが大きく異なるアンチクラスターを作成する傾向があったが、ABAによる多様性の分布はタイトで一貫していた。
• バランスKカット： バランスKカット問題に適用した場合、ABAは解の質と実行時間の両面で、最先端のMETISアルゴリズムを、特に大きな $K$ 値において上回った。
• 階層的分解： ImageNet32データセットを用いた実験では、階層的分解を用いることで、$K=5,000$ の場合の実行時間を3,900秒以上から約44秒に短縮でき、かつ解の質への損失は無視できる程度（<0.02%）であることが示された。

意義と主張

本論文は、これまでの手法の適用を制限してきたスケーラビリティのボトルネックを解消することで、ABAがユークリッド反クラスタリングの分野における重要な進歩であると主張している。著者らは、小さな $K$ ではランダム分割で十分な場合が多いが、$K$ が増加するにつれてその品質が急速に低下するため、ABAのようなアルゴリズムが必要になると強調している。

ABAの意義は二重である：

1. 実用的な有用性： 以前の手法では遅すぎた、あるいは低品質な解しか得られなかった機械学習（例：ミニバッチ生成）やその他の分野における、百万規模のデータセットへの反クラスタリングの適用を可能にする。
2. 統計的堅牢性： 二次的目標であるアンチクラスター類似性に独自に対処し、生成されるグループが多様であるだけでなく、統計的に比較可能であることを保証する。これは、交差検証や実験計画において極めて重要である。

著者らは、事前ランキングとバッチ割り当てに基づくABAの設計が、最大多様性問題（Maximum Diversity Problem）や複雑な制約を持つ反クラスタリングなど、他の多様性問題にも適応可能な堅牢なフレームワークを提供すると結論付けている。