最大頻度アイテムセットとは？定義・具体例・メリットと課題を解説

最大頻度アイテムセットの定義

最大頻度アイテムセット（Maximal Frequent Itemset）とは、その直接の上位集合（スーパーセット）のどれひとつとしても頻度アイテムセットではない頻度アイテムセットのことを指します。

格子構造（ラティス）上のアイテムセットは、「頻度アイテムセット」と「非頻度アイテムセット」の2つのグループに分けられます。この2つのグループを隔てる境界は「頻度アイテムセット境界」と呼ばれ、通常は破線で表現されます。

格子図における境界の考え方

境界よりも上側に位置するアイテムセットはすべて頻度アイテムセットであり、境界より下側に位置するアイテムセット（網掛けされたノード）は非頻度アイテムセットです。

境界付近に存在するアイテムセットの中で、{a, d}、{a, c, e}、{b, c, d, e} の3つは、それぞれの直接の上位集合がすべて非頻度であるため、最大頻度アイテムセットとして扱われます。

具体例で見る判定基準

たとえば、{a, d} は最大頻度アイテムセットです。これは、その直接の上位集合である {a, b, d}、{a, c, d}、{a, d, e} のいずれもが非頻度であるためです。

これに対して {a, c} は最大頻度アイテムセットではありません。なぜなら、その直接の上位集合である {a, c, e} が頻度アイテムセットだからです。

最大頻度アイテムセットによるコンパクトな記述

最大頻度アイテムセットを利用すると、頻度アイテムセット全体を簡潔に記述できます。言い換えれば、すべての頻度アイテムセットを導き出すことができる「最小限のアイテムセットの集合」を形成します。

たとえば、頻度アイテムセットは次の2つのグループに分類できます。

• 項目 a を含む頻度アイテムセット：項目 c、d、e を組み合わせて含むことが可能です。このグループには {a}、{a, c}、{a, d}、{a, e}、{a, c, e} などが該当します。

• 項目 b、c、d、e から始まる頻度アイテムセット：このグループには {b}、{b, c}、{c, d}、{b, c, d, e} などが該当します。

第1のグループに属する頻度アイテムセットは {a, c, e} または {a, d} の部分集合であり、第2のグループに属する頻度アイテムセットは {b, c, d, e} の部分集合です。したがって、最大頻度アイテムセットである {a, c, e}、{a, d}、{b, c, d, e} の3つだけで、すべての頻度アイテムセットをコンパクトに記述することができます。

メリット：頻度アイテムセットの指数爆発への対策

高次元データや密度の高いデータセットでは、頻度アイテムセットの数が指数関数的に増大する傾向があります。こうしたデータに対しては、最大頻度アイテムセットによる記述が非常に有効です。

ただし、このアプローチが実用的に機能するのは、部分集合を個別に列挙することなく最大頻度アイテムセットを直接発見できる効率的なアルゴリズムが存在する場合に限られます。

注意点：支持度情報は保持されない

コンパクトな記述を実現できる一方で、最大頻度アイテムセットにはその部分集合の支持度（サポートカウント）に関する情報は含まれていません。

たとえば、最大頻度アイテムセット {a, c, e}、{a, d}、{b, c, d, e} の支持度を知ったとしても、それらの部分集合の支持度については何も推測できません。

非最大の頻度アイテムセットの支持度を求めるためには、データセットに対して追加の走査（追加パス）を実行する必要があります。こうした背景から、支持度の情報を保持したまま頻度アイテムセットを最小限に記述したい場合には、クローズドアイテムセット（閉アイテムセット）などの別の概念が利用されることがあります。