トランザクションデータベースからのマルチレベル相関ルールマイニングとは？

マルチレベル相関ルールのマイニングとは

トランザクションデータベースからのマルチレベル相関ルール（マルチレベルアソシエーションルール）のマイニングは、サポート・信頼度（support-confidence）フレームワークに基づいて行われます。この手法ではトップダウン戦略が採用され、コンセプトレベル1から始めて、より具体的な下位の概念レベルへと向かいながら、各概念レベルで頻出アイテムセットを計算するためのカウントを蓄積していきます。Aprioriアルゴリズムを用いて、それ以上頻出アイテムセットが見つからなくなるまで処理が続けられます。

概念階層によるデータの一般化

データは、低レベルの概念を、概念階層におけるより高レベルの概念（祖先ノード）に置き換えることで一般化できます。概念階層は木構造として表現され、その根（ルート）はD、すなわちタスク関連データを表します。

マルチレベル相関ルールの代表的な応用分野はマーケットバスケット分析です。これは顧客の購買習慣を研究するもので、一緒に購入されることの多いアイテムの集合を探索します。この分析において、概念階層の考え方が重要な役割を果たします。

各ノードは調査済みのアイテムまたはアイテムセットを表します。任意の抽象化レベルで頻出アイテムセットを見つけるためにはさまざまなアプローチがあり、実際に使われている主な方法としては、「全レベルで統一された最小サポートを使用する」「下位レベルで最小サポートを引き下げる」「レベルごとの独立探索」などが挙げられます。

階層エンコードされたトランザクションテーブル

マルチレベルデータベースでは、元のトランザクションテーブルではなく、階層データをエンコードしたトランザクションテーブルが必要になります。これは、すべてのアイテムではなく「食品」のようにトランザクションデータベースの一部だけに関心がある場合に特に有用です。この方法なら、まず関連するデータの集合を収集し、その後タスク関連データの集合に対して繰り返し作業を行うことができます。トランザクションテーブルでは、各アイテムは数字のシーケンスとしてエンコードされます。

全レベルで統一された最小サポートを使用する方法

統一された最小サポート閾値を使用すると、探索手順が簡素化されます。「祖先は子孫のスーパーセットである」という知識に基づく最適化技術を採用することで、祖先が最小サポートを満たさないアイテムを含むアイテムセットの調査を回避できます。

ただし、この統一サポート方式の主な欠点は、抽象度の低いレベルのアイテムが、抽象度の高いレベルのアイテムと同じ頻度でしか出現しなくなる点です。本来、下位レベルの具体的なアイテムは出現頻度が低いため、統一閾値では貴重なパターンを見逃してしまう可能性があります。

下位レベルで最小サポートを引き下げる方法

この方式では、抽象化の各レベルがそれぞれ独自の最小サポート閾値を持ちます。抽象化レベルが低いほど、対応する閾値も小さくなります。削減サポートを用いたマルチレベル相関ルールのマイニングにおける探索カテゴリは、以下の3つに分類されます。

• レベルごとの独立探索（Level-by-level independent）：完全な幅優先探索であり、頻出アイテムセットに関する背景知識を枝刈りに利用します。親ノードが頻出であることが確認されていなくても、各ノードが調査されます。
• 単一アイテムによるレベル間フィルタリング（Level cross-filtering by a single item）：第iレベルのアイテムは、その親ノードにあたる第(i-1)レベルのアイテムが頻出である場合にのみ調査されます。
• k-アイテムセットによるレベル間フィルタリング（Level cross-filtering by k-itemset）：第iレベルのアイテムセットは、その対応する親にあたる第(i-1)レベルのk-アイテムセットが頻出である場合にのみ調査されます。