データマイニングにおける制約の分類とは？3種類の制約と特徴を解説

制約ベースアルゴリズムにおける制約の役割

制約ベースのアルゴリズムでは、頻出項目集合の生成段階において探索空間を絞り込むために制約が必要となります（連想ルールの生成ステップは、網羅的アルゴリズムの場合と同様です）。

制約の重要性は明確に定義されており、ユーザーにとって興味深い連想ルールだけを抽出することを可能にします。この手法は非常にシンプルで、制約を適用することでルールの探索範囲が縮小され、残りのルールはすべて制約に従うことになります。

クラスタリング制約の3つの分類

クラスタ分析における制約は、主に以下の3種類に分類されます。

1. インスタンスに対する制約

インスタンスに対する制約は、クラスタ分析において、特定のペアまたはインスタンスの集合がどのようにグループ化されるべきかを定義します。このカテゴリには、次の2種類の制約があります。

• Must-link制約（必ず同一クラスタに属する制約）：2つのオブジェクトxとyにMust-link制約が定義されている場合、クラスタ分析の出力において、xとyは必ず同一のクラスタにグループ化されなければなりません。Must-link制約は推移性を持ちます。すなわち、must-link(x, y)かつmust-link(y, z)が成り立つならば、must-link(x, z)も成立します。
• Cannot-link制約（必ず別々のクラスタに属する制約）：Cannot-link制約は、Must-link制約の逆にあたります。2つのオブジェクトxとyにCannot-link制約が定義されている場合、クラスタ分析の出力において、xとyは必ず異なるクラスタに属さなければなりません。また、Cannot-link制約は導出が可能です。cannot-link(x, y)、must-link(x, x')、must-link(y, y')が成り立つ場合、cannot-link(x', y')が導かれます。

2. クラスタに対する制約

クラスタに対する制約は、クラスタの属性を利用して、クラスタそのものへの要件を定義します。たとえば、クラスタ内のオブジェクトの最小数、クラスタの最大直径、クラスタの形状（例：凸形状）などを指定できます。また、分割型クラスタリング手法においてあらかじめ定義されるクラスタ数も、クラスタに対する制約として扱うことができます。

3. 類似度測定に対する制約

ユークリッド距離などの類似度尺度は、クラスタ分析においてオブジェクト間の類似度を計算するために用いられます。しかし、応用分野によっては例外が生じることもあります。類似度測定に対する制約は、類似度の計算が従わなければならない要件を定義するものです。

たとえば、広場を移動する人々をオブジェクトとしてクラスタリングする場面を考えてみましょう。ユークリッド距離は2点間の直線距離を算出しますが、類似度測定に対する制約として「最短距離となる経路は壁を横切ってはならない」といった条件を課すことができます。

ハード制約とソフト制約という分類の観点

クラスタリング制約を分類するもう一つのアプローチとして、「制約がどれほど厳密に遵守されなければならないか」という基準があります。制約に違反するクラスタリング結果が許容できない場合、その制約はハード制約（hard constraint）と呼ばれます。一方、制約に違反するクラスタリングは望ましくないものの、より良い解が見つからない場合には許容できるという場合、その制約はソフト制約（soft constraint）と呼ばれます。ソフト制約は「選好（preference）」とも呼ばれます。