制約付きクラスタリングの手法とは？ハード制約とソフト制約への対応方法を解説

制約付きクラスタリングの概要

クラスタリングにおいて特定の制約を扱うには、制約の種類に応じたさまざまな手法が必要とされます。ここでは、ハード制約とソフト制約を扱うための一般的な原則について解説します。

ハード制約への対応

ハード制約を扱う一般的な手法は、クラスタ割り当ての手順において制約を厳密に遵守することです。データセットと、サンプルに対する一連の制約（必ず同じクラスタに割り当てる「must-link制約」、絶対に同じクラスタに割り当ててはならない「cannot-link制約」）が与えられた場合、k-means法をどのように拡張すればこれらの制約を満たせるのでしょうか。COP-k-meansアルゴリズムは以下の手順で動作します。

must-link制約に対するスーパーインスタンスの生成

まず、must-link制約の推移閉包を計算します。これにより、すべてのmust-link制約を同値関係として扱うことができます。この閉包から、同一クラスタに割り当てるべきオブジェクトの部分集合が1つ以上得られます。

部分集合を定義したら、その中の複数のオブジェクトを平均値で置き換えます。スーパーインスタンスには、それが表すオブジェクトの数を示す重みも付与されます。この処理により、must-link制約は常に満たされることが保証されます。

修正版k-meansクラスタリングの実行

通常のk-means法では、オブジェクトは最も近い中心に割り当てられます。cannot-link制約を遵守するためには、k-meansの中心割り当てプロセスを「最も近い実行可能な中心への割り当て」に変更します。

オブジェクトを順番に中心へ割り当てていく際、各ステップで、それまでの割り当てがcannot-link制約に違反していないことを確認します。オブジェクトは、cannot-link制約を満たす中で最も近い中心に割り当てられます。

COP-k-meansは各ステップで制約違反が発生しないことを保証するため、バックトラッキング（巻き戻し処理）を必要としません。制約間に矛盾が存在しない限り、すべての制約を満たすクラスタリングを生成する貪欲法（greedy algorithm）として機能します。

ソフト制約への対応

ソフト制約を伴うクラスタリングは、最適化問題として定式化されます。クラスタリングがソフト制約に違反した場合、そのクラスタリングに対してペナルティが課されます。したがって、クラスタリングの最適化の目的関数は、「クラスタリング品質の最適化」と「制約違反ペナルティの最小化」という2つの要素で構成されます。つまり、目的関数はクラスタリング品質スコアとペナルティスコアの組み合わせとなります。

データセットとサンプルに対する一連のソフト制約が与えられた場合、CVQE（Constrained Vector Quantization Error）アルゴリズムは、制約違反ペナルティを適用しながらk-meansクラスタリングを実行します。CVQEで使用される目的関数は、k-meansで用いられる距離の総和に制約違反ペナルティを加味して修正したものであり、ペナルティは以下のように計算されます。

must-link違反のペナルティ

オブジェクトxとyの間にmust-link制約が存在するにもかかわらず、両者が異なる2つの中心c₁とc₂に割り当てられた場合、制約に違反したことになります。この場合、c₁とc₂の間の距離dist(c₁, c₂)がペナルティとして目的関数に加算されます。

cannot-link違反のペナルティ

オブジェクトxとyの間にcannot-link制約が存在するにもかかわらず、両者が同一の中心cに割り当てられた場合、制約に違反したことになります。この場合、cと別の中心c’の間の距離dist(c, c’)がペナルティとして目的関数に加算されます。