閉頻繁アイテムセットを効率的にマイニングする方法とは？枝刈り戦略とクロージャーチェックを解説

閉頻繁アイテムセットマイニングの基本アプローチ

最も単純な（ナイーブな）アプローチでは、まず頻出アイテムセットの完全な集合をマイニングし、その後、既存の頻出アイテムセットの真部分集合であり、かつ同じサポート度を持つ各頻出アイテムセットを削除します。

しかし、この方法では、長さ100の頻出アイテムセットを1つ得るためだけに、2¹⁰⁰−1個もの頻出アイテムセットを導出してからでなければ、冗長なアイテムセットの削除を開始できません。そこで推奨されるのは、マイニング段階で閉頻繁アイテムセット（closed frequent itemsets）を直接探索する手法です。これには、マイニング中に閉アイテムセットの性質を識別できる時点で、直ちに探索空間を枝刈りすることが求められます。主な枝刈り戦略には以下のようなものがあります。

主要な枝刈り戦略

アイテムマージ（Item Merging）
頻出アイテムセットXを含むすべてのトランザクションが、アイテムセットYを含み、かつYの真上位集合を含まない場合、X∪Yは閉頻出アイテムセットを形成します。この場合、Xを含むがYを含まないアイテムセットを探索する必要はありません。

部分アイテムセットの枝刈り（Sub-itemset Pruning）
頻出アイテムセットXが、すでに発見された閉頻出アイテムセットYの真部分集合であり、support_count(X) = support_count(Y) が成り立つ場合、Xおよび集合列挙木におけるXの子孫はすべて閉頻出アイテムセットになり得ないため、枝刈りできます。

アイテムスキップ（Item Skipping）
閉アイテムセットの深さ優先マイニングでは、各レベルにおいて、ヘッダーテーブルおよび投影データベースに関連付けられたプレフィックスアイテムセットXが存在し得ます。ある局所的な頻出アイテムpが複数のレベルの複数のヘッダーテーブルで同じサポート度を持つ場合、より高いレベルのヘッダーテーブルからpを安全に削除できます。

クロージャーチェックの2種類の検証

新しい頻出アイテムセットが生成された際には、次の2種類のクロージャーチェックを実行する必要があります。

• 上位集合チェック（Superset Checking）：新しい頻出アイテムセットが、同じサポート度を持つ以前に発見された閉アイテムセットの上位集合であるかどうかを検証します。

• 下位集合チェック（Subset Checking）：新しく発見されたアイテムセットが、同じサポート度を持つ以前に発見された閉アイテムセットの下位集合であるかどうかを検証します。

分割統治法による効率化

分割統治（divide-and-conquer）構造のもとでアイテムマージの枝刈り技法を採用すれば、上位集合テストは実質的に組み込まれるため、明示的に上位集合チェックを実装する必要はありません。これは、頻出アイテムセットX∪YがアイテムセットXよりも後に発見され、Xと同じサポート度を持つ場合、それは必ずXの投影データベース内に存在し、アイテムマージの過程で生成されているはずだからです。

パターンツリーによる下位集合チェックの支援

下位集合チェックを支援するために、圧縮されたパターンツリー（pattern-tree）を構築し、マイニングされた閉アイテムセットの集合を管理することができます。このパターンツリーはFP-treeとメカニズムが類似していますが、異なる点として、発見されたすべての閉アイテムセットが対応するツリーのブランチに明示的に格納されます。