学ぶ Aprioriアルゴリズムによるトランザクションデータストリームの処理 | アソシエーションルールとトランザクション分析の基礎

メニューを表示するにはスワイプしてください

Aprioriアルゴリズムは、トランザクションデータにおける頻出アイテムセットを発見するための基礎的なツールであり、マーケットバスケット分析に不可欠な存在です。Aprioriの中心には、Apriori原理（ダウンクロージャー性とも呼ばれる）が存在します。

定義

Apriori原理 - あるアイテムセットが頻出である場合、そのすべての部分集合も頻出でなければならない。

この洞察により、評価すべきアイテムセットの数が大幅に削減されます。なぜなら、頻出でない部分集合を含むアイテムセットは即座に検討対象から除外できるためです。

候補生成は、アルゴリズムにおけるマッチングフェーズです。各ラウンドで、アルゴリズムは前のラウンドで頻出と判定されたアイテムセットを組み合わせ、新たな大きなグループ（候補）を作成します。効率的にこれを行うため、アルゴリズムは最後の1つ以外すべてのアイテムが一致する、ほぼ同一のアイテムセット同士のみを結合します。

仕組み: アルゴリズムが{Bread, Milk}と{Bread, Diapers}の両方が個別に非常に人気が高いことを発見した場合、これらを組み合わせて次のラウンド用の新しい3アイテム候補{Bread, Milk, Diapers}を作成します。

新しい候補を生成した直後、アルゴリズムは**剪定（プルーニング）**フェーズを開始し、重いデータベース計算を行う前に不要な候補を排除します。このステップは完全にApriori原理に基づいており、大きなアイテムセットが頻出となるのは、そのすべての小さな部分集合も頻出である場合のみという考え方です。剪定の際、アルゴリズムは各新候補を細かく分解し、その部分集合を調べます。もし1つでも前のラウンドで基準を満たさなかった部分集合があれば、その候補全体が即座に削除されます。

仕組み: 例えば候補{Bread, Milk, Eggs}が生成されたとします。アルゴリズムはその部分集合である{Bread, Milk}、{Bread, Eggs}、{Milk, Eggs}を確認します。もし過去のトランザクションログで{Milk, Eggs}が前のラウンドで基準を満たさなかった稀な組み合わせであれば、アルゴリズムは{Bread, Milk, Eggs}を完全に剪定します。これにより、失敗が保証されている組み合わせに計算リソースを無駄に費やすことを防ぎます。

候補リストが最も有望なものに絞り込まれた後、アルゴリズムは頻出アイテムセットの特定に進みます。システムは生のトランザクションデータベースをスキャンし、これらの候補グループが実際の購入履歴でどれだけ一緒に現れるかを正確にカウントします。各候補の合計回数はパーセンテージに変換されます。このスコアが事前に設定した最小サポート閾値以上であれば、その候補は正式に頻出アイテムセットとして認定されます。

定義

最小サポート閾値は、Aprioriアルゴリズムにおいてアイテムセットが有意と見なされるために必要な最低出現頻度を決定する、ユーザー定義のカットオフ値。この閾値を設定することで、データセット内で出現頻度が低すぎるアイテムセットを除外できる。高い閾値を設定すると、より一般的なアイテムセットのみが抽出され、興味深いが稀な組み合わせを見逃す可能性がある。一方、閾値を低くしすぎると、実用性の低いアイテムセットまで大量に抽出されてしまう。選択した閾値は分析の深さや焦点に直接影響するため、データ探索の目的や規模に合わせて設定する必要がある。

この3ステップのループ全体が連続して繰り返される。単一アイテムからペア、さらに3つ組と拡張し、新たな頻出アイテムセットが見つからなくなるまで続行し、消費者購買行動の全体像を網羅的に把握する。

これらの概念を具体的に理解するために、小規模なデータセットを用いた例を考える。以下のような取引があるとする：

Transaction 1: {Milk, Bread};
Transaction 2: {Milk, Diaper, Beer, Bread};
Transaction 3: {Milk, Diaper, Beer, Cola};
Transaction 4: {Diaper, Beer};
Transaction 5: {Milk, Diaper, Bread, Beer}.

アルゴリズムはまず頻繁に出現する単一アイテムを特定し、そこから候補となるペアを生成し、出現頻度の低いアイテムを含むものを除外し、このプロセスを繰り返して{Milk, Diaper, Beer}のようなより大きな頻出グループを発見する。


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

このPythonコードは、トランザクションデータにおける頻出アイテムセットを特定するためのAprioriアルゴリズムのシンプルな実装例です。各ステップの処理内容は以下の通りです。

データ準備

トランザクションはリストのリストとして表現され、各サブリストは一緒に購入されたアイテムを含みます。
すべてのユニークなアイテムを特定し、ソートします。
ワンホットエンコードされたDataFrameを作成します。各行はトランザクションを、各列はアイテムを表し、TrueまたはFalseで存在・不在を示します。

Aprioriアルゴリズムのステップ

1. 頻出1アイテムセットの特定

各アイテムごとにサポート値（そのアイテムを含むトランザクションの割合）を計算します。
アイテムのサポート値がmin_support（ここでは0.6）以上の場合、頻出アイテムとみなされ、最初の頻出アイテムセットリストに含まれます。

2. 候補生成

長さk（2から開始）のアイテムセットについて、前回の頻出アイテムセット同士で1つだけ異なるものを組み合わせて新たな候補アイテムセットを生成します。
重複のないユニークな組み合わせのみを考慮します。

3. 剪定（プルーニング）

新しい各候補の長さk-1の部分集合を確認します。
いずれかの部分集合が前回の頻出アイテムセットリストに含まれていない場合、Apriori原理に基づきその候補は除外されます。

4. サポート値のカウント

残った各候補について、すべてのアイテムを含むトランザクション数をカウントします。
サポート値を計算し、閾値と比較します。閾値を満たす候補のみが次回の頻出アイテムセットとなります。

5. 反復処理

ステップ2〜4を繰り返し、毎回アイテムセットのサイズを増やしていきます。新たな頻出アイテムセットが見つからなくなるまで続けます。

出力

最終リストにはすべての頻出アイテムセットとそのサポート値が含まれます。
コードは各頻出アイテムセットとそのサポート値を出力し、どのアイテムの組み合わせがトランザクション内でよく現れるかを示します。

1. Aprioriアルゴリズムにおける候補生成ステップを最もよく表しているのはどれですか？

2. Aprioriアルゴリズムで候補アイテムセットを剪定（プルーニング）する主な理由は何ですか？

すべて明確でしたか？

フィードバックありがとうございます！

セクション 1. 章 4

AIに質問する

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 1. 章 4