ルール制約を活用して検索空間を効率的に削減する方法

相関ルールマイニングにおいて、ルール制約は膨大な検索空間を効率的に絞り込むための強力な手段となります。これらの制約は、その性質に応じていくつかのカテゴリに分類することができます。本記事では、代表的な分類について順に解説します。

1. 反単調制約（Antimonotonic Constraints）

最初のカテゴリは反単調制約です。例として、「sum(I.price) ≤ 100」というルール制約を考えてみましょう。Aprioriフレームワークでは、各反復kにおいてサイズkの項目集合を解析します。ある項目集合に含まれる商品の価格の合計がすでに100を超えている場合、この項目集合は検索空間から除外できます。なぜなら、さらに多くの商品を追加すれば合計金額は増える一方であり、制約を満たすことは二度とないからです。

反単調制約によるプルーニングは、Apriori型アルゴリズムのすべての反復段階で適用でき、データマイニング結果の完全性を保証しながら、マイニング処理全体の効率を大幅に向上させます。

実は、「頻出項目集合のすべての空でない部分集合もまた頻出である」と定義されるApriori特性自体が、反単調性を備えています。ある項目集合が最小サポートを満たさない場合、その上位集合（スーパーセット）も満たすことはありません。この特性をAprioriアルゴリズムの各反復で活用することで、検証すべき候補項目集合の数を削減し、相関ルール探索のための検索空間を縮小できます。

2. 単調制約（Monotonic Constraints）

次のカテゴリは単調制約です。ルール制約が「sum(I.price) ≥ 100」である場合、制約ベースの処理アプローチは先ほどとは逆になります。

項目集合Iがこの制約を満たしている、すなわち集合内の価格の合計が100以上である場合、そこへさらに商品を追加しても合計金額は増加し続けるため、制約は引き続き満たされます。

したがって、項目集合Iに対してこの制約を何度も検証することは冗長です。言い換えれば、ある項目集合がこの制約を満たすならば、そのすべての上位集合も必ず制約を満たします。このような性質を持つルール制約は「単調」であるといいます。

3. 簡潔制約（Succinct Constraints）

3番目のカテゴリは簡潔制約です。この種の制約では、制約を満たすことが保証された集合を直接列挙することができます。ルール制約が簡潔である場合、サポートカウントを開始する前の段階で、制約を満たす集合を正確に生成することが可能です。これにより、「生成と検査（generate-and-test）」パラダイムに伴う多大なオーバーヘッドを回避できます。

4. 変換可能制約（Convertible Constraints）

4番目のカテゴリは変換可能制約です。項目集合内のアイテムを特定の順序で並べ替えることで、頻出項目集合マイニングの過程において、制約が単調または反単調として扱えるようになる場合があります。

例えば、「avg(I.price) ≤ 100」という制約は、そのままでは反単調でも単調でもありません。しかし、トランザクション内のアイテムを価格の昇順で項目集合に追加していくと、この制約は反単調として振る舞います。なぜなら、項目集合Iがすでに制約に違反している場合（平均価格が100ドルを超えている場合）、それより高価なアイテムを追加しても制約を満たすことは決してないからです。

5. 変換不可能制約（Inconvertible Constraints）

最後に、上記のいずれの性質にも当てはまらない変換不可能制約が存在します。この種の制約は、アイテムの順序を工夫しても単調化・反単調化できないため、プルーニングには利用できません。この場合、制約チェックをマイニングプロセスの後段で行うか、別の最適化手法を組み合わせる必要があります。

このように、制約の性質を見極めて適切なプルーニング戦略を選択することで、相関ルールマイニングの計算コストを大幅に削減できます。