Apriori アルゴリズムの紹介 (Python 実装)

[[188839]]

ビッグデータの概念が普及するにつれ、ビールとおむつの話は広く知られるようになりました。ビールを買う人はおむつを買う傾向があることをどうやって発見するのでしょうか? データマイニングで頻出アイテムセットと関連ルールをマイニングするために使用される Apriori アルゴリズムが教えてくれます。この記事では、まず Apriori アルゴリズムを紹介し、次に関連する基本概念をさらに紹介し、次に Apriori アルゴリズムの具体的な戦略と手順を詳細に紹介し、最後に Python 実装コードを示します。

1. Aprioriアルゴリズムの紹介

Apriori アルゴリズムは、頻繁なアイテムセットと関連ルールをマイニングするための古典的なデータマイニングアルゴリズムです。 a priori はラテン語で「前から」を意味します。問題を定義するとき、私たちは多くの場合、事前知識や仮定を使用します。これを「先験的」と呼びます。 Apriori アルゴリズムの名前は、アルゴリズムが頻繁なアイテムセットの事前特性を使用するという事実に基づいています。つまり、頻繁なアイテムセットの空でないサブセットもすべて頻繁である必要があります。 Apriori アルゴリズムは、レベルごとの検索と呼ばれる反復的な方法を使用します。この方法では、k 個のアイテムセットを使用して (k+1) 個のアイテムセットを探索します。まず、データベースをスキャンし、各アイテムの数を累積し、最小サポートを満たすアイテムを収集することによって、頻出する 1 アイテムセットのセットが見つかります。この集合は L1 と表記されます。次に、L1 を使用して頻繁な 2 項目セットのセット L2 を見つけ、L2 を使用して L3 を見つけます。これを、頻繁な k 項目セットが見つからなくなるまで繰り返します。各 Lk を見つけるには、データベースを完全にスキャンする必要があります。 Apriori アルゴリズムは、頻繁なアイテムセットの事前特性を使用して検索空間を圧縮します。

2. 基本概念

アイテムとアイテムセット: itemset={item1, item_2, …, item_m} をすべてのアイテムのセットとし、その中に item_k (k=1,2,…,m) がアイテムとして含まれます。アイテムのコレクションはアイテムセットと呼ばれ、k 個のアイテムを含むアイテムセットは k アイテムセットと呼ばれます。

トランザクションとトランザクションセット: トランザクション T はアイテムセットであり、アイテムセットのサブセットです。各トランザクションには一意の識別子 Tid が関連付けられています。異なるトランザクションが一緒になってトランザクションセット D を形成し、これが関連ルール検出のためのトランザクションデータベースを構成します。

関連ルール: 関連ルールは、A=>B という形式の含意です。ここで、A と B は両方ともアイテムセットのサブセットであり、どちらも空のセットではなく、A と B の交差は空です。

サポート: 関連ルールのサポートは次のように定義されます。

ここで、P(A∪B) は、トランザクションにセット A とセット B の和集合 (つまり、A と B のすべての項目) が含まれる確率を表します。トランザクションに A または B が含まれる確率を示す P(A または B) との違いに注意してください。

信頼性: 関連ルールの信頼性は次のように定義されます。

アイテムセットの頻度 (サポート数): アイテムセットを含むトランザクションの数。頻度、サポート数、またはアイテムセットの数と呼ばれます。

頻繁なアイテムセット: アイテムセット I の相対的なサポートが事前に定義された最小サポートしきい値を満たす場合 (つまり、I の出現頻度が対応する最小頻度 (サポートカウント) しきい値より大きい場合)、I は頻繁なアイテムセットです。

強力な関連ルール: 最小サポートと最小信頼度を満たす関連ルール、つまりマイニングされる関連ルール。

3. 実装手順

一般的に、関連ルールのマイニングは 2 段階のプロセスです。

頻繁に使用されるアイテムセットをすべて検索

頻繁なアイテムセットから強力な相関ルールを生成する

3.1 頻出アイテムセットのマイニング

3.1.1 関連する定義

接続ステップ: 頻出(k-1)アイテムセットLk-1を自己接続して候補kアイテムセットCkを生成する。

Apriori アルゴリズムでは、アイテムセット内のアイテムが辞書順に並べられていることを前提としています。 Lk-1 内の 2 つの要素 (アイテムセット) itemset1 と itemset2 の最初の (k-2) アイテムが同じである場合、itemset1 と itemset2 は接続可能であると言われます。したがって、itemset1とitemset2を連結して生成される結果のアイテムセットは、{itemset1[1]、itemset1[2]、…、itemset1[k-1]、itemset2[k-1]}になります。接続手順は、以下のコードの create_Ck 関数に含まれています。

剪定戦略

事前特性の存在により、非頻繁 (k-1) アイテムセットは、頻繁 k アイテムセットのサブセットではありません。したがって、候補 k 項目セット Ck の (k-1) 項目サブセットが Lk-1 にない場合、候補は頻繁に出現することはなく、Ck から削除して圧縮された Ck を取得できます。次のコードの is_apriori 関数は、事前プロパティが満たされているかどうかを判断するために使用されます。create_Ck 関数にはプルーニングステップが含まれており、事前プロパティが満たされていない場合はプルーニングが実行されます。

ポリシーの削除

圧縮された Ck に基づいて、すべてのトランザクションがスキャンされ、Ck 内の各項目がカウントされ、最小サポートを満たさない項目が削除されて、頻繁な k 項目セットが取得されます。削除戦略は、以下のコードの generate_Lk_by_Ck 関数に含まれています。

3.1.2 手順

各項目は、候補 1 項目セットの集合 C1 のメンバーです。アルゴリズムはすべてのトランザクションをスキャンし、各項目を取得して、C1 を生成します (以下のコードの create_C1 関数を参照)。次に各項目を数えます。次に、最小サポートに従ってC1から満たされていない項目を削除し、頻出する1項目セットL1を取得します。
L1 自身の接続によって生成されたセットが整理され、候補となる 2 項目セットのセット C2 が生成されます。次に、すべてのトランザクションがスキャンされ、C2 内の各項目がカウントされます。同様に、最小サポートに従ってC2から満たされていない項目を削除し、頻出2項目セットL2を取得します。
L2 自身の接続によって生成されたセットが整理され、候補となる 3 項目セットのセット C3 が生成されます。次に、すべてのトランザクションがスキャンされ、C3 内の各項目がカウントされます。同様に、最小サポートに従ってC3から満たされていない項目が削除され、頻出する3項目セットL3が得られます。
同様に、Lk-1 の自己接続によって生成されたセットに対してプルーニング戦略を実行して候補 k 項目セット Ck を生成し、次にすべてのトランザクションをスキャンして Ck 内の各項目をカウントします。次に、最小サポートに従ってCkから満たされていない項目を削除し、頻出k項目セットを取得します。

3.2 頻出アイテムセットからの相関ルールの生成

頻繁に使用されるアイテムセットが見つかると、そこから強力な関連ルールを直接生成できます。生成手順は次のとおりです。

各頻出アイテムセット itemset について、itemset のすべての空でないサブセットを生成します (これらの空でないサブセットは頻出アイテムセットである必要があります)。
アイテムセットの空でない部分集合sに対して、

出力は s=>(ls) となり、min_conf は最小信頼しきい値です。

4. 例とPython実装コード

下の図は、『データマイニング: 概念とテクニック (第 3 版)』の頻繁なアイテムセットのマイニングのサンプル図です。

この記事では、このサンプルのデータに基づいて Python コードを記述し、Apriori アルゴリズムを実装します。コードには注意すべき点が 2 つあります。

Apriori アルゴリズムでは、アイテムセット内のアイテムが辞書順にソートされ、セット自体は順序付けられていないことを前提としているため、必要に応じてセットとリストを変換する必要があります。

アイテムセットのサポートを記録するには辞書 (support_data) を使用する必要があるため、アイテムセットをキーとして使用する必要がありますが、可変セットは辞書のキーとして使用できません。したがって、適切な場合はアイテムセットを固定セットの freezeset に変換する必要があります。

 「」 「 」
 # Python 2.7
 # ファイル名: apriori.py
 # 著者: llhthinker
 # メール:hangliu56[ AT ]gmail[DOT]com
 # ブログ: http://www.cnblogs.com/llhthinker/p/6719779.html
 #日付: 2017-04-16
 「」 「 」 
 
 
 def load_data_set():
 「」 「 」
サンプルデータセットをロードします（ 『データマイニング：概念とテクニック、第3版』より）
戻り値:
 データセット: トランザクションのリスト。各トランザクション いくつかの項目が含まれています。
 「」 「 」
 データセット = [[ 'l1' , 'l2' , 'l5' ], [ 'l2' , 'l4' ], [ 'l2' , 'l3' ],
 [ 'l1' 、 'l2' 、 'l4' ]、[ 'l1' 、 'l3' ]、[ 'l2' 、 'l3' ]、
 [ 'l1' 、 'l3' ]、[ 'l1' 、 'l2' 、 'l3' 、 'l5' ]、[ 'l1' 、 'l2' 、 'l3' ]]
データセットを返す
 
 
 def create_C1(データセット):
 「」 「 」
データセットをスキャンして、頻出候補1アイテムセットC1を作成します。
 引数:
 data_set: トランザクションのリスト。各トランザクション いくつかの項目が含まれています。
戻り値:
 C1: 次のものを含む集合 頻出候補1アイテムセットすべて
「」 「 」
 C1 =セット()
 data_set内のtの場合:
 t内の項目の場合:
 item_set = 凍結セット([item])
 C1.追加(item_set)
 C1を返す
 
 
事前定義 is_apriori(Ck_item, Lksub1):
 「」 「 」
 頻出候補 k アイテムセットが Apriori プロパティを満たしているかどうかを判断します。
 引数:
 Ck_item: Ck内の頻出候補kアイテムセット。  すべて頻繁に
 候補となる k アイテムセット。
 Lksub1: Lk-1、以下を含む集合 すべての頻出候補(k-1)アイテムセット。
戻り値:
真: Apriori プロパティを満たします。
 False : Apriori プロパティを満たしていません。
 「」 「 」
 Ck_item内のアイテムの場合:
 sub_Ck = Ck_item - 凍結セット([item])
 sub_Ckが  Lksub1の場合:
戻る 間違い 
戻る 真実  
 
 
 def create_Ck(Lksub1, k):
 「」 「 」
 Ckを作成します。これは、  全て 頻出候補kアイテムセットすべて
Lk-1 独自の接続操作によって。
 引数:
 Lksub1: Lk-1、以下を含む集合 すべての頻出候補(k-1)アイテムセット。
 k:頻出アイテムセットのアイテム番号。
戻る：
 Ck:含まれる集合 全て 頻繁に出現する候補 k アイテムセットすべて。
 「」 「 」
 Ck =セット()
 len_Lksub1 = len(Lksub1)
 list_Lksub1 = リスト(Lksub1)
 iが範囲(len_Lksub1)内にある場合:
 jが範囲(1, len_Lksub1)内にある場合:
 l1 = リスト(list_Lksub1[i])
 l2 = リスト(list_Lksub1[j])
 l1.ソート()
 l2.ソート()
 l1[0:k-2] == l2[0:k-2]の場合:
 Ck_item = list_Lksub1[i] | list_Lksub1[j]
 # 剪定
 is_apriori(Ck_item, Lksub1)の場合:
 Ck.追加(Ck_item)
 Ckを返す
 
 
 def generate_Lk_by_Ck(データセット、Ck、min_support、support_data):
 「」 「 」
 Ckから削除ポリシーを実行してLk を生成します。
 引数:
 data_set: トランザクションのリスト。各トランザクション いくつかの項目が含まれています。
 Ck: 次のものを含む集合 全て 頻繁に出現する候補 k アイテムセットすべて。
 min_support: 最小サポート。
 support_data: 辞書。キー 頻繁なアイテムセットであり、値がサポートされています。
戻り値:
 Lk:含まれるセット 全て すべての頻繁な k アイテムセット。
 「」 「 」
 Lk =セット()
 アイテム数 = {}
 data_set内のtの場合:
 Ck内の項目の場合:
 項目がサブセットの場合(t):
 アイテムがない場合  item_count内:
 item_count[アイテム] = 1
それ以外：
 item_count[アイテム] += 1
 t_num = float (len(データセット))
 item_count内のアイテムについて:
 if (item_count[item] / t_num) >= min_support:
 追加(アイテム)
 サポートデータ[アイテム] = アイテム数[アイテム] / t_num
 Lkを返す
 
 
 def generate_L(データセット, k, min_support):
 「」 「 」
 すべての頻繁なアイテムセットを生成します。
 引数:
 data_set: トランザクションのリスト。各トランザクション いくつかの項目が含まれています。
 k :最大アイテム数 すべての頻繁なアイテムセット。
 min_support: 最小サポート。
戻り値:
 L: ルカによる福音書のリスト。
 support_data: 辞書。キー 頻繁なアイテムセットであり、値がサポートされています。
 「」 「 」
 サポートデータ = {}
 C1 = create_C1(データセット)
 L1 = generate_Lk_by_Ck(データセット、C1、最小サポート、サポートデータ)
 Lksub1 = L1.コピー()
 L = []
 L.append(Lksub1)
 iが範囲(2, k+1)内にある場合:
 Ci = create_Ck(Lksub1, i)
 Li = generate_Lk_by_Ck(データセット、Ci、最小サポート、サポートデータ)
 Lksub1 = Li.copy()
 L.append(Lksub1)
 L、support_dataを返す
 
 
 def generate_big_rules(L, support_data, min_conf):
 「」 「 」
 頻繁に使用されるアイテムセットから大きなルールを生成します。
 引数:
 L: ルカによる福音書のリスト。
 support_data: 辞書。キー 頻繁なアイテムセットであり、値がサポートされています。
 min_conf: 最小の信頼度。
戻り値:
 big_rule_list: リストに含まれるもの すべては大きなルール。それぞれの大きなルール 表現される
3 組として。
 「」 「 」
 ビッグルールリスト = []
 サブセットリスト = []
 iが範囲(0, len(L))内にある場合:
 L[i]内のfreq_setの場合:
 sub_set_list内のsub_setの場合:
 sub_set.issubset(freq_set): の場合
 conf = サポートデータ[周波数セット] / サポートデータ[周波数セット - サブセット]
 big_rule = (freq_set - sub_set、sub_set、conf)
 conf >= min_confかつbig_ruleが  big_rule_list内:
 # print freq_set-sub_set, " => " , sub_set, "conf: " , conf
 big_rule_list.append(big_rule)
 サブセットリストに追加(freq_set)
 big_rule_listを返す
 
 
 __name__ == "__main__"の場合:
 「」 「 」
 テスト
「」 「 」
 データセット = load_data_set()
 L、サポートデータ = generate_L(データセット、k=3、min_support=0.2)
 big_rules_list = generate_big_rules(L、サポートデータ、min_conf=0.7)
 Lkが Lの場合:
 印刷"=" *50
 「頻繁な」 + str(len(list(Lk)[0])) + 「-itemsets\t\tsupport」を印刷します。  
 印刷"=" *50
 Lkのfreq_setの場合:
 freq_set、support_data[freq_set]を印刷します。
 印刷
 「ビッグルール」を印刷する 
 big_rules_list内の項目の場合:
 項目[0]、 「=>」 、項目[1]、 「conf:」 、項目[2]を印刷する