サポートカウントとは？Aprioriアルゴリズムにおける支持度計数の仕組みを徹底解説

サポートカウント（support counting、支持度の計数）とは、Aprioriアルゴリズムにおける重要な処理の一つです。具体的には、apriori-gen関数による候補枝刈り（candidate pruning）ステップを通過した各候補アイテムセットが、データセット全体でどれほどの頻度で出現するのかを判定する手順を指します。

サポートカウントの2つの基本手法

手法1：トランザクションとの総当たり比較

一つ目の方法は、すべてのトランザクションとすべての候補アイテムセットを照合し、トランザクションに含まれている候補のサポートカウントを順次更新していくというものです。

しかしこの方法は計算コストが非常に高く、特にトランザクションの件数や候補アイテムセットの数が多い場合には、処理時間が大幅に増大してしまうという欠点があります。

手法2：トランザクション内アイテムセットの列挙

二つ目のアプローチは、各トランザクションに含まれるアイテムセットをすべて列挙し、その情報をもとに該当する候補アイテムセットのサポートカウントを更新する方法です。

例えば、{1, 2, 3, 5, 6} という5個のアイテムを含むトランザクション t を考えてみましょう。このトランザクションには、サイズ3のアイテムセットが C(5,3) = 10 個含まれています。

列挙されたアイテムセットの中には、解析対象となっている候補3-アイテムセットと一致するものがあり、その場合は該当候補のサポートカウントが加算されます。一方、どの候補にも一致しない t の部分集合は無視できます。

プレフィックス構造による体系的な列挙

t に含まれる3-アイテムセットを漏れなく・重複なく列挙するには、体系的なアプローチが必要です。各アイテムセットはアイテムを辞書式順序（昇順）で保持していると仮定すると、最小のアイテムから順に、より大きいアイテムを続けて定義していくことで列挙が可能になります。

先ほどの t = {1, 2, 3, 5, 6} の例で言えば、t に含まれるすべての3-アイテムセットは、アイテム1、2、または3から始まることになります。アイテム5や6から始まる3-アイテムセットを作ることはできません。これは、t の中で5以上のラベルを持つアイテムが2個しか存在しないためです。

このような「プレフィックス構造」を利用すると、トランザクションに含まれるアイテムセットを、左端のアイテムから右端のアイテムへと一つずつ定義していく形で、一貫性をもって列挙できます。

さらに、列挙された各3-アイテムセットが既存の候補アイテムセットと一致するかどうかを判定できます。一致する候補が存在すれば、その候補のサポートカウントをインクリメント（加算）します。

ハッシュツリーによる効率化

Aprioriアルゴリズムでは、候補アイテムセットを複数のバケットに分割し、ハッシュツリー（hash tree）として格納します。サポートカウントの実行時には、各トランザクションに含まれるアイテムセットも同様にハッシュ関数によって適切なバケットへ振り分けられます。

これにより、トランザクション内のアイテムセットをすべての候補アイテムセットと比較する必要がなくなり、同一バケットに属する候補アイテムセットとのみ照合すればよくなります。比較回数が大幅に削減され、処理の高速化が実現します。

ツリーの各内部ノードでは、次にどの分岐をたどるべきかを決定するために、h(p) = p mod 3 というハッシュ関数が使用されます。例えば、アイテム1、4、7は3で割った余りがすべて等しいため、同じ分岐（最も左の分岐）にハッシュされます。そして、すべての候補アイテムセットは、このハッシュツリーの葉ノード（leaf node）に格納されます。