関連ルール学習

サポートとは、データセット内でアイテムセットがどのくらいの頻度で出現するかを示す指標です。

${\displaystyle {\text{support}}(A)=P(A)={\frac {({\text{number of transactions containing }}A)}{\text{ (total number of transactions)}}}}$

ルールの支持は次のように定義される。

${\displaystyle {\text{support}}(A\Rightarrow B)=P(A\cup B)={\frac {({\text{number of transactions containing }}A{\text{ and }}B)}{\text{ (total number of transactions)}}}}$

ここで、AとBはトランザクション内で同時に発生する別々のアイテムセットである。^{[ 12 ]}

表2を例にとると、アイテムセットは${\displaystyle X=\{\mathrm {beer,diapers} \}}$Xは全トランザクションの 20% (5 回に 1 回) で発生するため、サポートは1/5 = 0.2です。Xのサポートの引数は前提条件のセットであり、そのため、大きくなるにつれて (より包括的になるのではなく) より制限的になります。^{[ 13 ]}

さらに、アイテムセット${\displaystyle Y=\{\mathrm {milk,bread,butter} \}}$また、全取引の20%にも出現するため、1/5=0.2の支持率があります。

先行関係と後続関係を用いることで、データマイナーはデータセット全体と比較して、複数の商品が一緒に購入される可能性の強さを判断できます。例えば、表2では、牛乳が購入された場合、パンも購入される可能性の強さが0.4、つまり40%であることが示されています。これは、5回の取引のうち2回で牛乳とパンの両方が購入されているためです。この例のようにサンプル数が少ない小規模なデータセットでは、強い相関関係を見つけるのは困難ですが、データセットが大きくなると、スーパーマーケットの例のように、2つ以上の商品間の相関関係を見つけるためにサポートを利用できるようになります。

最小支持度閾値は、どのアイテムセットが好ましいか、あるいは興味深いかを判断するのに役立ちます。

表3でサポート閾値を≥0.4に設定すると、${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}$0.4という最小閾値を満たしていないため、削除されます。最小閾値は、データセット内でサンプルが重要または興味深いと判断するのに十分な支持または確信がないサンプルを削除するために使用されます。

興味深いサンプルを見つけるもう1つの方法は、（サポート） × （信頼度）の値を求めることです。これにより、データマイナーは、サポートと信頼度が十分に高く、データセット内で強調表示されるサンプルを確認し、サンプルを詳しく調べて、項目間の関連性に関するより多くの情報を得ることができます。

サポートは、データセット全体と比較して製品間の関連性を見つけるのに役立ちますが、信頼度は、1つまたは複数のアイテムと他のアイテムとの関連性を調べます。以下は、表4の情報を使用して信頼度値を導き出し、サポートとサポート×信頼度の比較と対比を示した表です。

Tに対するXのサポートは、データセット内のトランザクションのうちアイテムセットXを含むトランザクションの割合として定義されます。トランザクションを で表します。${\displaystyle (i,t)}$ここで、iはトランザクションの一意の識別子であり、tはそのアイテムセットである。サポートは次のように記述できる。

${\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T|}}}$

この表記法は、アイテムやアイテムセットが上記のスーパーマーケットの例ほど単純ではない、より複雑なデータセットを定義する際に使用できます。サポートが使用できるその他の例としては、病気を引き起こすために共同で作用する遺伝子変異のグループを見つけること、アップグレードオファーに反応する加入者の数を調査すること、ドラッグストアで一緒に購入されない製品を発見することなどがあります。^{[ 12 ]}

信頼度とは、 Xを満たすすべての取引のうち、 Yも満たす取引の割合である。^{[ 14 ]}

Tに関して、アソシエーションルールの信頼度値は、しばしば次のように表されます。${\displaystyle X\Rightarrow Y}$は、 XとYの両方を含むトランザクションの数と、存在するX値の総数との比率であり、 Xは前件、Yは後件である。

信頼度は条件付き確率の推定値としても解釈できる。${\displaystyle P(E_{Y}|E_{X})}$、トランザクションにルールの右辺が含まれているという条件の下で、トランザクションにルールの右辺が見つかる確率。^{[ 13 ] [ 15 ]}

一般的には次のように描かれています。

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{\text{number of transactions containing }}X{\text{ and }}Y}{{\text{number of transactions containing }}X}}}$

この式は、データセット内でトランザクションXとYが同時に発生する頻度を、トランザクションXのみを含むトランザクション数に対する比率として計算することで、信頼度を算出できることを示しています。つまり、 XとYの両方に含まれるトランザクション数を、 X のみに含まれるトランザクション数で割るということです。

例えば、表2にはルールが示されています。${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$信頼度は${\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0}$データセットでは、顧客がバターとパンを購入するたびに牛乳も購入することを示しています。この特定の例は、バターとパンの両方を含む取引に対してルールが100%正しいことを示しています。ルール${\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \}}$しかし、${\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67}$これは、果物が購入された場合の67%で卵が購入されていることを示唆しています。このデータセットでは、果物は合計3回購入されており、そのうち2回は卵の購入でした。

データセットが大きい場合、信頼度の最小閾値またはパーセンテージカットオフは、項目間の関係を判断するのに役立ちます。 表 2 のデータの一部にこの方法を適用すると、要件を満たさない情報は削除されます。 表 4 は、信頼度の最小閾値が 0.5 (50%) である関連付けルールの例を示しています。信頼度が 0.5 未満のデータはすべて省略されます。 閾値を生成すると、最も頻繁に共起するものを強調することで、データがさらに調査されるにつれて項目間の関連性が強くなります。 表では、表 3 の信頼度情報を使用してサポート×信頼度列を実装し、1 つの概念だけでなく、信頼度とサポートの両方による項目間の関係を強調します。 サポート×信頼度でルールをランク付けすると、特定のルールの信頼度がサポートに乗算され、項目間の関係をより深く理解するためによく実装されます。

全体として、アソシエーションルールマイニングで信頼度を使用することは、データ間の関係性を認識する上で非常に有効な方法です。信頼度の最大の利点は、特定のルールにおける先行要素の出現頻度と、セット内の特定の要素間の関係性を明確にすることです。ただし、信頼度はアソシエーションルールマイニングにおけるすべての概念に対して最適な方法ではありません。信頼度を使用する際の欠点は、関連性について複数の異なる視点を提供しないことです。たとえば、サポートとは異なり、信頼度はデータセット全体と比較した特定の要素間の関係性に関する視点を提供しません。そのため、たとえば牛乳とパンは信頼度では100%出現するかもしれませんが、サポートは0.4（40%）にしかなりません。これが、関係性を定義する際に、1つの概念だけに頼るのではなく、サポート×信頼度などの他の視点も考慮する必要がある理由です。

ルールのリフトは次のように定義されます。

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}}$

または、XとYが独立である場合に期待される支持率に対する、観測された支持率の比率。

例えば、ルール${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$リフトは${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$。

ルールのリフト値が1であれば、それは前件の発生確率と後件の発生確率が互いに独立していることを意味する。2つの事象が互いに独立している場合、それらの事象を含むルールは作成できない。

リフト値が1より大きい場合、それは2つの事象が互いにどの程度依存しているかを示しており、将来のデータセットにおける結果を予測する上で、これらのルールが潜在的に有用であることを示しています。

リフト値が1未満の場合、それらのアイテムは互いに代替可能であることがわかります。つまり、一方のアイテムの存在は他方のアイテムの存在に悪影響を及ぼし、その逆もまた然りです。

リフトの価値は、ルールのサポートとデータセット全体の両方を考慮する点にある。^{[ 13 ]}

規則の確信は次のように定義される。${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}$[ ^{16 ]​}

例えば、ルール${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$有罪判決を受けている${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$これは、XとYが独立している場合にXがYなしで発生する期待頻度（つまり、ルールが誤った予測をする頻度）を、誤った予測の観測頻度で割った比率として解釈できます。この例では、確信度1.2は、ルールが${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$XとYの関連性が純粋に偶然によるものであれば、20%多く（1.2倍多く）間違ってしまうだろう。

信頼度以外にも、ルールの面白さを測る指標がいくつか提案されている。代表的な指標としては以下のようなものがある。

• 全面的に自信あり^{[ 17 ]}
• 集団の力^{[ 18 ]}
• レバレッジ^{[ 19 ]}

Tan ら^{[ 20 ]}および Hahsler ^{[ 21 ]}は、さらにいくつかの尺度を提示し比較している。ユーザーが知っていることをモデル化できる技術を探し、これらのモデルを面白さの尺度として使用することは、現在「主観的面白さ」という名前で活発な研究動向となっている。

Aprioriアルゴリズムは、1994年にR. AgrawalとR. Srikantによって、頻出アイテムセットのマイニングとアソシエーションルールの学習のために提案されました。このアルゴリズムは、データベース内の頻繁に出現する個々のアイテムを特定し、それらのアイテムセットが十分に頻繁に出現する限り、より大きなアイテムセットへと拡張していくことで処理を進めます。頻出アイテムセットの特性に関する事前知識を利用することから、このアルゴリズムはAprioriと名付けられました。

概要: Apriori は「ボトムアップ」アプローチを採用しており、頻出サブセットを一度に 1 つのアイテムで拡張し (候補生成と呼ばれるステップ)、候補のグループをデータに対してテストします。アルゴリズムは、それ以上の拡張が成功しなくなった時点で終了します。Apriori は幅優先探索とハッシュツリー構造を使用して、候補アイテムセットを効率的にカウントします。長さのアイテムセットから長さの候補アイテムセットを生成します。次に、頻度の低いサブパターンを持つ候補を剪定します。下方閉包補題によれば、候補セットにはすべての頻出長さアイテムセットが含まれます。その後、トランザクションデータベースをスキャンして、候補の中から頻出アイテムセットを決定します。

例：各行は、アルファベットの文字でラベル付けされた特定の変異の組み合わせを持つ癌サンプルであると仮定します。たとえば、行に{a, c}がある場合、それは変異「a」と変異「c」の両方の影響を受けていることを意味します。

次に、各文字の出現回数を数えることで、頻出アイテムセットを生成します。これはサポート値を求めることとも呼ばれます。その後、最小サポート閾値を選択してアイテムセットを剪定します。このアルゴリズムのステップでは、3を選択します。

サポート値がすべて3以上であるため、枝刈りは行いません。頻繁に出現するアイテムのセットは{a}、{b}、{c}、{d}です。この後、入力セット内の変異のペアを数えることで、このプロセスを繰り返します。

次に、最小サポート値を4に設定し、剪定後に{a, d}のみが残るようにします。次に、頻繁に出現するアイテムセットを使用して、3つの要素の組み合わせを作成します。その後、入力セット内の変異の3つの要素の出現回数を数えることで、このプロセスを繰り返します。

アイテムが1つしかないため、次の4つ組の組み合わせは空になり、アルゴリズムは停止します。

利点と限界：

Aprioriにはいくつかの制限があります。候補生成によって大きな候補セットが生成される可能性があります。たとえば、10^4 の頻出 1-アイテムセットは、10^7 の候補 2-アイテムセットを生成します。また、このアルゴリズムはデータベースを頻繁にスキャンする必要があり、具体的には n+1 回のスキャンが必要です。ここで n は最長のパターンの長さです。Apriori は Eclat アルゴリズムよりも低速です。ただし、データセットが大きい場合、Apriori は Eclat と比較して優れたパフォーマンスを発揮します。これは、Eclat アルゴリズムではデータセットが大きすぎると tid-list がメモリに対して大きくなりすぎるためです。FP-growth は Apriori と Eclat を上回ります。これは、FP-growth アルゴリズムには候補生成やテストがなく、コンパクトなデータ構造を使用し、データベースのスキャンが 1 回のみであるためです。^{[ 27 ]}

Eclat ^{[ 11 ]} (別名 ECLAT、Equivalence Class Transformation の略) は、頻出アイテムセット格子グラフを深さ優先探索(DFS) 方式で走査するバックトラッキングアルゴリズムです。Apriori アルゴリズムで使用される幅優先探索(BFS) 走査では、アイテムセットをチェックする前にすべてのサブセットをチェックすることになりますが、DFS 走査ではより大きなアイテムセットをチェックし、下方近接性により一部のサブセットのサポートのチェックを省略できます。さらに、DFS は BFS よりも空間計算量が少ないため、メモリ使用量もほぼ確実に少なくなります。

これを説明するために、頻出アイテムセット {a, b, c} があるとします。DFS は、頻出アイテムセットのラティスのノードを次の順序でチェックします: {a} → {a, b} → {a, b, c}。この時点で、{b}、{c}、{a, c}、{b, c} はすべて下方閉包性によりサポート制約を満たすことがわかっています。BFS は、{a, b, c} の各部分集合を探索してから、最終的にチェックします。アイテムセットのサイズが大きくなるにつれて、その部分集合の数は組み合わせ爆発を起こします。

局所性を高める特性を持ち、逐次実行と並列実行の両方に適しています。^{[ 28 ] [ 29 ]}

FPは頻出パターンの略です。^{[ 30 ]}

最初のパスでは、アルゴリズムはトランザクションのデータセット内のアイテム（属性と値のペア）の出現回数をカウントし、これらのカウントを「ヘッダーテーブル」に格納します。2 番目のパスでは、トランザクションをトライ木に挿入して FP ツリー構造を構築します。

各トランザクション内の項目は、データセット内での出現頻度の降順でソートしてから挿入する必要があります。これにより、ツリーの処理速度が向上します。最小サポート要件を満たさない各トランザクション内の項目は破棄されます。多くのトランザクションが最も頻繁に出現する項目を共有している場合、FPツリーはツリーのルート付近で高い圧縮率を実現します。

この圧縮されたメインデータセットの再帰処理では、候補アイテムを生成してデータベース全体に対してテストするのではなく（アスピリチュアルアルゴリズムのように）、頻出アイテムセットを直接生成します。

成長はヘッダーテーブルの一番下、つまりサポートが最も小さい項目から始まります。その項目で終わるすべてのソート済みトランザクションを見つけることで成長します。この項目を${\displaystyle I}$。

元の FP-ツリーを投影した新しい条件付きツリーが作成されます。${\displaystyle I}$投影されたツリー内のすべてのノードのサポートが再カウントされ、各ノードは子ノードのカウントの合計を取得します。最小サポートを満たさないノード（したがってサブツリー）は剪定されます。再帰的成長は、条件付きで個々の項目がなくなったときに終了します。${\displaystyle I}$最小サポートしきい値を満たします。ルートからの結果パス${\displaystyle I}$これらは頻繁に出現するアイテムセットです。このステップの後、処理は元のFPツリーの中で次に最も出現頻度の低いヘッダーアイテムへと続きます。

再帰処理が完了すると、すべての頻出アイテムセットが見つかり、関連付けルールの作成が開始されます。^{[ 31 ]}

• M. Hahslerによる、 アソシエーションルールに関する注釈付き参考文献（ 2017年2月19日、 Wayback Machineにアーカイブ済み）