相関規則アプリオリアルゴリズムを理解する方法

相関ルール アプリオリ アルゴリズムを理解する: アプリオリ アルゴリズムは、最初の相関ルール マイニング アルゴリズムであり、最も古典的なアルゴリズムです。レイヤーごとの検索の反復方法を使用して、データベース内のアイテム セット間の関係を見つけて、フォーム ルール プロセスは、接続 [行列のような操作] とプルーニング [不要な中間結果の削除] で構成されます。

相関ルール先験アルゴリズムを理解します:

1. 概念

表 1 スーパーマーケットの取引データベース

##T9#T5

取引番号 TID

顧客が購入した商品

トランザクション番号 TID

顧客が購入した商品

T1

パン、クリーム、ミルク、紅茶

T6

パン、紅茶

T2

パン、クリーム、牛乳

T7

ビール、牛乳、お茶

T3

ケーキ、牛乳

T8

パン、お茶

##T4

牛乳、紅茶

#パン、クリーム、牛乳、紅茶

パン、ケーキ、牛乳

T10

パン、牛乳、 お茶＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

定義 1: I={i1,i2,…,im} とします。これは、m 個の異なる項目のセットであり、各 ik は呼び出されます。 プロジェクトの場合。アイテムのコレクション I は itemset と呼ばれます。その要素の数はアイテムセットの長さと呼ばれ、長さ k のアイテムセットは k アイテムセットと呼ばれます。この例では、各製品は項目であり、項目セットは I={パン、ビール、ケーキ、クリーム、牛乳、紅茶}、I の長さは 6 です。

定義 2: 各 トランザクションT は、設定したアイテムセットの子です。 。各トランザクションに対応して、一意の識別トランザクション番号があり、TID として記録されます。すべてのトランザクションは トランザクション データベースD を構成し、|D| は D 内のトランザクションの数に等しくなります。この例には 10 個のトランザクションが含まれているため、|D|=10 となります。

定義 3: 項目セット #XX の場合、count(X⊆T) をトランザクション セット D 数量に X を含むトランザクションの数に設定します。の場合、項目セット X の サポート は次のようになります:

support(X)=count(X⊆T)/|D|

#この例では、#XX={パン, ミルク} が T1、T2、T5、T9、および T10 に出現するため、サポートは 0.5 になります。

定義 4

: 最小サポート はアイテムセットの最小値です。サポートしきい値は SUPmin として記録され、ユーザーが関心を持つ関連付けルールの最小重要性を表します。 サポートが SUPmin 以上である項目セットは頻出セット と呼ばれ、長さ k の頻出セットは k 頻度セットと呼ばれます。 SUPmin が 0.3 に設定されている場合、この例の {bread, Milk} のサポートは 0.5 であるため、2 度数セットになります。

定義 5

: 関連付けルール は暗黙的です:#R:X⇒Y

ここで、

X⊂I、Y⊂I、X∩Y=⌀。あるトランザクションでアイテムセット X が出現すると、一定の確率で Y も出現することを示します。ユーザーが気にする関連付けルールは、サポートと信頼性という 2 つの基準で測定できます。

定義 6

: 相関ルール R の サポートはトランザクションです。 X と Y の両方を含むセットを |D| にします。つまり: support(X⇒Y)=count(X⋃Y)/|D|サポートは、XX と Y が同時に出現する確率を反映します。時間。相関ルールのサポートは、頻出セットのサポートと同等です。

定義 7

: 相関ルール R の場合、

credibility を参照します#XX と Y を含むトランザクションの数と、X を含むトランザクションの数の比率。つまり: confidence(X⇒Y)=support(X⇒Y)/support(X)Confidence は、トランザクションに XX が含まれている場合、 then トランザクションに Y が含まれる確率。一般に、ユーザーにとって関心があるのは、高いサポートと信頼性を備えた相関ルールのみです。 定義 8

: 関連付けルールの最小サポートと最小信頼性を SUPmin および CONFmin として設定します。ルール R の支持と信頼性が SUPmin と CONFmin 以上である場合、それは

強相関ルール

と呼ばれます。相関ルール マイニングの目的は、販売者の意思決定を導くための強力な相関ルールを見つけることです。

これらの 8 つの定義には、相関ルールに関連するいくつかの重要な基本概念が含まれています。相関ルール マイニングには 2 つの主な問題があります:

1. ユーザーが指定した最小サポート以上の、頻繁に使用されるアイテムセットをトランザクション データベース内ですべて検索します。
2. 頻繁に使用するアイテム セットを使用して必要な関連付けルールを生成し、ユーザーが設定した最小限の信頼性に基づいて強い関連付けルールを除外します。

現在、研究者は主に最初の問題に焦点を当てており、頻出集合を見つけることは困難ですが、頻出集合との強い相関ルールを生成することは比較的簡単です。

2. 理論的根拠

まず、頻度集合の性質を見てみましょう。

#定理: 項目セット #XX が頻出セットの場合、その空でないサブセットはすべて頻出セットになります 。

定理によれば、

k 頻度集合の項目集合 X が与えられた場合、k-1 次のすべての部分集合は、2 つの k-1 頻度集合の項目集合は次の点のみ異なります。 1 つの項目であり、接続後は X に等しくなります。これは、ｋ−１個の頻度集合を連結することによって生成されたｋ候補集合が、ｋ頻度集合をカバーすることを証明する。同時に、k-候補集合内の項目集合 Y に、k-1 頻出集合に属さない k-1 次のサブセットが含まれている場合、Y は頻出集合であるはずがないため、候補集合から取り除く必要があります。 Apriori アルゴリズムは、この頻繁なセットの特性を利用します。

3. アルゴリズムのステップ:

最初はテスト データです:

製品T100T200##T300#I1、I2、I4#I2,I3T700#I1,I3T800I1、I2、I3、I5##T900

アルゴリズムのステップ図:

ご覧のとおり、候補セットの 3 ラウンド目は大幅に減少しましたが、これはなぜですか?

候補セットを選択するための 2 つの条件に注意してください:

1. 2 つの K 項目セットを接続するための 2 つの条件は、それらが K-1 を持っていることです。項目は同じです。したがって、(I2、I4)と(I3、I5)は接続できません。候補セットが絞り込まれます。

2. 項目セットが頻出セットの場合、サブセットではない頻出セットはありません。たとえば、(I1, I2) と (I1, I4) は (I1, I2, I4) を取得しますが、(I1, I2, I4) の部分集合 (I1, I4) は頻出集合ではありません。候補セットが絞り込まれます。

第 3 ラウンドで得られた 2 候補セットのサポートは、最小サポートとまったく同じです。したがって、それらはすべて頻繁なセットに含まれています。

次に、第 4 ラウンドの候補セットと頻出セットの結果を見てください。 は空です。

候補セットがそして、頻繁なセットは実際には空です！ 3 ラウンド目で取得した頻出集合は自己結合して {I1, I2, I3, I5} を取得しますが、これには部分集合 {I2, I3, I5} が含まれており、{I2, I3, I5} は存在しません。頻出集合の部分集合も頻出集合であるという条件を満たすため、枝刈りによって切り取られます。したがって、アルゴリズム全体が終了し、最後の計算で得られた頻出集合が最終的な頻出集合の結果として取得されます:

つまり: ['I1,I2,I3', 'I1,I2,I5 ']

4. コード:

Apriori アルゴリズムを実装する Python コードを作成します。コードでは、次の 2 つの点に注意する必要があります。

• Apriori アルゴリズムでは、項目セット内の項目が辞書編集順に並べ替えられており、セット自体は順序付けされていないと想定しているため、set を実行する必要があります。変換;
• 項目セットのサポートを記録するために辞書 (support_data) が使用されるため、項目セットをキーとして使用する必要があり、変数セットをキーとして使用することはできません。ディクショナリのキーなので、項目セットは適切な時点で固定に変換される必要があります。

def local_data(file_path):    import pandas as pd

    dt = pd.read_excel(file_path)
    data = dt['con']
    locdata = []    for i in data:
        locdata.append(str(i).split(","))   # print(locdata)  # change to [[1,2,3],[1,2,3]]
    length = []    for i in locdata:
        length.append(len(i))  # 计算长度并存储
   # print(length)
    ki = length[length.index(max(length))]   # print(length[length.index(max(length))])  # length.index(max(length)读取最大值的位置，然后再定位取出最大值

    return locdata,kidef create_C1(data_set):    """
    Create frequent candidate 1-itemset C1 by scaning data set.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
    Returns:
        C1: A set which contains all frequent candidate 1-itemsets    """
    C1 = set()    for t in data_set:        for item in t:
            item_set = frozenset([item])
            C1.add(item_set)    return C1def is_apriori(Ck_item, Lksub1):    """
    Judge whether a frequent candidate k-itemset satisfy Apriori property.
    Args:
        Ck_item: a frequent candidate k-itemset in Ck which contains all frequent
                 candidate k-itemsets.
        Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
    Returns:
        True: satisfying Apriori property.
        False: Not satisfying Apriori property.    """
    for item in Ck_item:
        sub_Ck = Ck_item - frozenset([item])        if sub_Ck not in Lksub1:            return False    return Truedef create_Ck(Lksub1, k):    """
    Create Ck, a set which contains all all frequent candidate k-itemsets
    by Lk-1's own connection operation.
    Args:
        Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
        k: the item number of a frequent itemset.
    Return:
        Ck: a set which contains all all frequent candidate k-itemsets.    """
    Ck = set()
    len_Lksub1 = len(Lksub1)
    list_Lksub1 = list(Lksub1)    for i in range(len_Lksub1):        for j in range(1, len_Lksub1):
            l1 = list(list_Lksub1[i])
            l2 = list(list_Lksub1[j])
            l1.sort()
            l2.sort()            if l1[0:k-2] == l2[0:k-2]:
                Ck_item = list_Lksub1[i] | list_Lksub1[j]                # pruning
                if is_apriori(Ck_item, Lksub1):
                    Ck.add(Ck_item)    return Ckdef generate_Lk_by_Ck(data_set, Ck, min_support, support_data):    """
    Generate Lk by executing a delete policy from Ck.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
        Ck: A set which contains all all frequent candidate k-itemsets.
        min_support: The minimum support.
        support_data: A dictionary. The key is frequent itemset and the value is support.
    Returns:
        Lk: A set which contains all all frequent k-itemsets.    """
    Lk = set()
    item_count = {}    for t in data_set:        for item in Ck:            if item.issubset(t):                if item not in item_count:
                    item_count[item] = 1                else:
                    item_count[item] += 1
    t_num = float(len(data_set))    for item in item_count:        if (item_count[item] / t_num) >= min_support:
            Lk.add(item)
            support_data[item] = item_count[item] / t_num    return Lkdef generate_L(data_set, k, min_support):    """
    Generate all frequent itemsets.
    Args:
        data_set: A list of transactions. Each transaction contains several items.
        k: Maximum number of items for all frequent itemsets.
        min_support: The minimum support.
    Returns:
        L: The list of Lk.
        support_data: A dictionary. The key is frequent itemset and the value is support.    """
    support_data = {}
    C1 = create_C1(data_set)
    L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)
    Lksub1 = L1.copy()
    L = []
    L.append(Lksub1)    for i in range(2, k+1):
        Ci = create_Ck(Lksub1, i)
        Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)
        Lksub1 = Li.copy()
        L.append(Lksub1)    return L, support_datadef generate_big_rules(L, support_data, min_conf):    """
    Generate big rules from frequent itemsets.
    Args:
        L: The list of Lk.
        support_data: A dictionary. The key is frequent itemset and the value is support.
        min_conf: Minimal confidence.
    Returns:
        big_rule_list: A list which contains all big rules. Each big rule is represented
                       as a 3-tuple.    """
    big_rule_list = []
    sub_set_list = []    for i in range(0, len(L)):        for freq_set in L[i]:            for sub_set in sub_set_list:                if sub_set.issubset(freq_set):
                    conf = support_data[freq_set] / support_data[freq_set - sub_set]
                    big_rule = (freq_set - sub_set, sub_set, conf)                    if conf >= min_conf and big_rule not in big_rule_list:                        # print freq_set-sub_set, " => ", sub_set, "conf: ", conf                        big_rule_list.append(big_rule)
            sub_set_list.append(freq_set)    return big_rule_listif __name__ == "__main__":    """
    Test    """
    file_path = "test_aa.xlsx"
  
    data_set,k = local_data(file_path)
    L, support_data = generate_L(data_set, k, min_support=0.2)
    big_rules_list = generate_big_rules(L, support_data, min_conf=0.4)    print(L)    for Lk in L:        if len(list(Lk)) == 0:            break
        print("="*50)        print("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport")        print("="*50)        for freq_set in Lk:            print(freq_set, support_data[freq_set])    print()    print("Big Rules")    for item in big_rules_list:        print(item[0], "=>", item[1], "conf: ", item[2])

ファイル形式:

test_aa.xlsx

name    con
T1     2,3,5T2     1,2,4T3     3,5T5     2,3,4T6     2,3,5T7     1,2,4T8     3,5T9     2,3,4T10    1,2,3,4,5

関連する無料学習の推奨事項: pythonビデオチュートリアル

トランザクション ID	IDリスト
I1、I2、I5
I2,I4
I2、I3	##T400
T500	#I1、I3
#T600
I1、I2、I3

以上が相関規則アプリオリアルゴリズムを理解する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。