制約付きのクラスタリングの方法は何ですか？

特定の制約を処理するには、さまざまな手法が必要です。次のようなハード制約とソフト制約の処理の一般原則-

厳しい制約の処理 −難しい制約を処理するための一般的な方法は、クラスター割り当て手順で制約を厳密に考慮することです。データセットと例の制約のグループ（つまり、リンクする必要がある制約またはリンクできない制約）が与えられた場合、そのような制約を満たすためにk-meansアプローチをどのように開発できますか？ COP-kmeansアルゴリズムは次のように機能します-

リンクが必要な制約のスーパーインスタンスを生成する −リンクが必要な制約の推移閉包を計算できます。したがって、すべてのリンクしなければならない制約は、同値関係と見なされます。クロージャーは、オブジェクトの1つまたは複数のサブセットを提供し、サブセット内の一部のオブジェクトを1つのクラスターに割り当てる必要があります。

それはそのようなサブセットを定義することができ、サブセット内のいくつかのオブジェクトを平均で置き換えることができます。スーパーインスタンスは、定義するオブジェクトの数である重みも生成します。このプロセスの後、リンクが必要な制約は継続的に満たされます。

修正されたk-meansクラスタリングを実行する − k-meansでは、オブジェクトは最も近い中心に作成されます。リンクできない制約を尊重でき、k-means法の中心割り当てプロセスを最も近い実行可能な中心割り当てに変更します。

オブジェクトが順番にセンターに割り当てられると、すべてのステップで、これまでの割り当てによってリンクできない制約が中断されないようにすることができます。オブジェクトは最も近い中心に割り当てられるため、割り当てはリンクできない制約を尊重します。

COP-k-meansは、各ステップで制約に違反しないことを提供するため、バックトラックは必要ありません。これは、すべての制約を満たすクラスタリングを作成するための欲張りアルゴリズムであり、制約間に競合が存在しないことをサポートしています。

ソフト制約の処理 −ソフト制約を使用したクラスタリングは、最適化の問題です。クラスタリングがソフト制約を混乱させる場合、クラスタリングにペナルティが必要です。したがって、クラスタリングの最適化の目的には、クラスタリングの側面の最適化と制約違反のペナルティの最小化などの2つの部分が含まれます。目的のサービスは、クラスタリング品質スコアとペナルティスコアのセットです。

データセットと例のソフト制約のセットが与えられた場合、CVQE（制約付きベクトル量子化エラー）アルゴリズム戦略k-は、制約違反のペナルティを適用しながらクラスタリングを意味します。 CVQEで使用される目的関数は、k-meansで使用される距離の合計であり、制約違反のペナルティによって変更され、次のように計算されます-

リンクが必要な違反のペナルティ −オブジェクトxとyにリンクが必要な制約があるが、それらが2つの複数の中心c ₁に作成されている場合 およびc₂ したがって、したがって、制約に違反します。その結果、dist（c ₁ 、c ₂ ）、c ₁間の距離 およびc₂ 、ペナルティとして目的関数に挿入されます。

リンクできない違反のペナルティ −オブジェクトxとyにリンクできない制約があるが、それらが共通の中心cに作成されている場合、制約に違反します。距離、距離（c、c ^’ ）、cとc ^’ の間 ペナルティとして目的関数に挿入されます。