ECLATアルゴリズムによる高速アソシエーションルール生成 | アソシエーション分析 | Pythonによる機械学習を学ぶ

2024.09.29
スポンサーリンク
スポンサーリンク
amazon
スマイルSALE
--:--:--
～
ad. 価格範囲を指定して商品を探せます

ECLATアルゴリズムによる高速アソシエーションルール生成

ECLAT（Equivalence Class Clustering and bottom-up Lattice Traversal）は、アソシエーション分析で使われる頻出アイテムセット探索アルゴリズムです。Aprioriと同じく「一緒に出現しやすいアイテムの組み合わせ」を見つけるために使われますが、データの持ち方に大きな違いがあります。

Aprioriが取引ごとに商品を並べる水平形式のデータを使うのに対し、ECLATは各アイテムが登場するトランザクションIDを管理する垂直形式のデータを使います。これにより、共通するトランザクションIDの積集合を計算することで、頻出アイテムセットを効率よく見つけられます。

ECLATアルゴリズムの仕組みを図で理解する

ECLATアルゴリズムの仕組みを図で理解する

ECLATアルゴリズムとは

ECLATは、各アイテムがどのトランザクションに登場したかを記録し、その共通部分を使ってサポートを計算するアルゴリズムです。

例えば、「ミルク」と「パン」が同じトランザクションに何回登場したかを調べる場合、それぞれのトランザクションIDのリストを比較し、共通するIDを数えます。

水平形式と垂直形式の違い

形式 考え方 例
水平形式 取引ごとに購入された商品を並べる 取引1：ミルク、パン、卵
垂直形式 商品ごとに登場する取引IDを管理する ミルク：取引1、取引3、取引4

ECLATでは垂直形式を使うため、アイテム同士の共通トランザクションを高速に求めやすくなります。

ECLATアルゴリズムの基本的な流れ

  1. トランザクションデータを垂直形式に変換する
  2. 各アイテムが登場するトランザクションIDを記録する
  3. アイテム同士のトランザクションIDの共通部分を求める
  4. 共通部分の数からサポートを計算する
  5. 最小サポート以上のアイテムセットを頻出アイテムセットとして残す

サポートの考え方

サポートは、あるアイテムセットが全体のトランザクションの中でどの程度出現しているかを示す指標です。

サポート = アイテムセットが出現した取引数 / 全取引数

ECLATでは、トランザクションIDの共通部分の数を使ってサポートを計算します。

PythonによるECLATアルゴリズムの実装

以下では、簡単なトランザクションデータを使って、ECLATの基本的な考え方をPythonで確認します。

import pandas as pd
from collections import defaultdict

# トランザクションデータの作成
data = {
    'トランザクションID': [1, 2, 3, 4, 5],
    'ミルク': [1, 0, 1, 1, 0],
    'パン': [1, 1, 0, 1, 1],
    'バター': [0, 1, 1, 0, 1],
    '卵': [1, 1, 0, 0, 1]
}

df = pd.DataFrame(data)

# 各アイテムが登場するトランザクションIDを作成
vertical_format = defaultdict(list)

for item in df.columns[1:]:
    vertical_format[item] = list(
        df[df[item] == 1]['トランザクションID']
    )

# 2つのアイテムの共通トランザクションIDを計算
def calculate_common_transactions(itemset1, itemset2):
    return set(vertical_format[itemset1]) & set(vertical_format[itemset2])

# ミルクとパンの共通トランザクションID
support_milk_bread = calculate_common_transactions('ミルク', 'パン')

print("ミルクとパンの共通トランザクションID:", support_milk_bread)

コードのポイント

  • vertical_format: 各アイテムが登場するトランザクションIDを保存するデータ構造
  • calculate_common_transactions: 2つのアイテムが共通して登場するトランザクションIDを求める関数
  • 積集合: 共通するトランザクションIDを見つけるために使用する

この例では、「ミルク」と「パン」が同時に登場するトランザクションIDを求めています。

AprioriとECLATの違い

項目 Apriori ECLAT
データ形式 水平形式 垂直形式
探索方法 候補アイテムセットを生成して確認 トランザクションIDの共通部分を計算
得意な処理 考え方が分かりやすい 頻出アイテムセットを高速に探索しやすい
計算の特徴 候補生成が多くなる場合がある 積集合計算で効率化できる

ECLATの応用例

ECLATは、アイテム同士の関連性を見つけたい場面で利用されます。

  • マーケットバスケット分析: 一緒に購入されやすい商品を発見する
  • レコメンド: 購入履歴から関連商品を提案する
  • 異常検知: 通常とは異なる組み合わせパターンを検出する
  • バイオインフォマティクス: 遺伝子や特徴の共起関係を分析する

アソシエーションルールの評価指標

ECLATで頻出アイテムセットを見つけた後は、サポート、信頼度、リフトなどを使ってルールの有用性を評価します。

指標 意味
サポート アイテムセットが全体の中でどれだけ出現するか
信頼度 Aが出現したときにBも出現する割合
リフト AとBの関連が偶然より強いかを示す指標

ECLATを使う際のポイント

  • 垂直形式に変換することで共通トランザクションを探しやすくなる
  • サポートが低すぎるとルールが多くなりすぎる
  • サポートが高すぎると有用なルールを見逃す可能性がある
  • 頻出アイテムセットを見つけた後、信頼度やリフトで評価する
スポンサーリンク