機械学習の10、Aprioriアルゴリズム

はじめに

スーパーでは、おむつとワインと同時に売れそうだから数多くの商品からおむつとワインが何らかの関連性があるとは。お父さんが子供用品を買うときに自分のご褒美にワインを買ってしまうと考えられる。アメリカ大統領の当選の予想には選挙イベント用のグッズの販売数が多いほうが当選されてしまうのもグッズと当選が強く相関すると考えられる。以上のことから、ビッグデータからアイテムの頻出度(出現頻度)を数えて頻出アイテム集合を検出して、頻出アイテム集合から相関ルールを検出するのは画期的なスーパーでは、おむつとワインと同時に売れそうだから数多くの商品からおむつとワインが何らかの関連性があるとは。お父さんが子供用品を買うときに自分のご褒美にワインを買ってしまうと考えられる。アメリカ大統領の当選の予想には選挙イベント用のグッズの販売数が多いほうが当選されてしまうのもグッズと当選が強く相関すると考えられる。以上のことから、ビッグデータからアイテムの頻出度(出現頻度)を数えて頻出アイテム集合を検出して、頻出アイテム集合から相関ルールを検出するのは画期的なアプリオリ(Apriori)アルゴリズムである。例えばトランザクション数=4、\(\small [(1,3,4),(2,3,5),(1,2,3,5),(2,5)]\)のトランザクション集合(買上げリスト4本と思って良い)にアプリオリ・アルゴリズムを適用すると、次式の頻出ルールで頻出度、相関ルール\(x → y\)で確信度を計算する。
$$ \small 頻出度(x)= \frac{xを含むトランザクション数}{トランザクション数} \\
\small 頻出度(1)= \frac{2}{4} = 50\% \\
\small 頻出度(x,y)= \frac{xとyを含むトランザクション数}{トランザクション数} \\
\small 頻出度(1,3)= \frac{2}{4} = 50\% \\
\small 確信度(x,y)= \frac{xとyを含むトランザクション数}{xを含むトランザクション数} \\
\small 確信度(1,3)= \frac{2}{2} = 100\% \\ \small 確信度(2,3)= \frac{2}{3} = 67\% $$
これで頻出度の閾値(最小頻出度)と確信度の閾値(最小確信度)を決めると、以下Aprioriアルゴリズムの処理手順で閾値以上の相関ルールが見出すことになる。
※ トランザクションの由来は、スーパーで1回ずつの買い物(取引)から得たデータなので、例えば(1,3,4)は1回の買い物から、数字化したデータ、1-おむつ、3-ワイン、4-たまごを表す。

頻出アイテム集合を検出手順】最初に1個の要素からなる候補集合C1を生成して、頻出度が閾値以上であるという条件でふるい分けして、頻出アイテム集合L1を作り出す。次に、頻出アイテム集合L1の要素を組み合わせて2個要素からなる候補集合C2を生成して、頻出度が閾値以上であるという条件でふるい分けして、頻出アイテム集合L2を作り出す…繰り返す。

相関ルールを検出手順】頻出アイテム集合L2から、次に確信度が閾値以上であるとの条件で相関ルールを検出する。次に、頻出アイテム集合L3から…繰り返す。

実装

\(\small [(1,3,4),(2,3,5),(1,2,3,5),(2,5)]\)から決まった頻出度、確信度で相関ルールを検出する。アプリオリ・アルゴリズムでは検出することができると分かる。

ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/apriori

実行

最小頻出度(minSupport): 0.5, 最小確信度(minConfidence): 0.5

[main] minSupport: 0.5, Lk: [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
suppDataList: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
[calcConf] frozenset({3})--> frozenset({2}), conf: 0.67
[calcConf] frozenset({2})--> frozenset({3}), conf: 0.67
[calcConf] frozenset({5})--> frozenset({3}), conf: 0.67
[calcConf] frozenset({3})--> frozenset({5}), conf: 0.67
[calcConf] frozenset({5})--> frozenset({2}), conf: 1.00
[calcConf] frozenset({2})--> frozenset({5}), conf: 1.00
[calcConf] frozenset({3})--> frozenset({1}), conf: 0.67
[calcConf] frozenset({1})--> frozenset({3}), conf: 1.00
[calcConf] frozenset({5})--> frozenset({2, 3}), conf: 0.67
[calcConf] frozenset({3})--> frozenset({2, 5}), conf: 0.67
[calcConf] frozenset({2})--> frozenset({3, 5}), conf: 0.67
[main] minConfidence: 0.5
ruleList: [(frozenset({3}), frozenset({2}), 0.67), (frozenset({2}), frozenset({3}), 0.67), (frozenset({5}), frozenset({3}), 0.67), (frozenset({3}), frozenset({5}), 0.67), (frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({3}), frozenset({1}), 0.67), (frozenset({1}), frozenset({3}), 1.0), (frozenset({5}), frozenset({2, 3}), 0.67), (frozenset({3}), frozenset({2, 5}), 0.67), (frozenset({2}), frozenset({3, 5}), 0.67)]

最小頻出度(minSupport): 0.5, 最小確信度(minConfidence): 0.7

[main] minSupport: 0.5, Lk: [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
suppDataList: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
[calcConf] frozenset({5})--> frozenset({2}), conf: 1.00
[calcConf] frozenset({2})--> frozenset({5}), conf: 1.00
[calcConf] frozenset({1})--> frozenset({3}), conf: 1.00
[main] minConfidence: 0.7
ruleList: [(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]

参考文献

[1] PeterHarrington. Machine Learning in Action.

ロボット・ドローン部品お探しなら
ロボット翔・電子部品ストア