Khai thác tập phổ biến & luật kết hợp – Association Rules

ngoton 25/02/2020 Data Mining Leave a comment 2,254 Views

1. Luật kết hợp trong khai phá dữ liệu (Association Rule in Data Mining)

Trong lĩnh vực Data Mining, mục đích của luật kết hợp (Association Rule – AR) là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu. Nội dung cơ bản của luật kết hợp được tóm tắt như dưới đây.

Cho cơ sở dữ liệu gồm các giao dịch T là tập các giao dịch t1, t2, …, tn.

T = {t1, t2, …, tn}. T gọi là cơ sở dữ liệu giao dịch (Transaction Database)

Mỗi giao dịch ti bao gồm tập các đối tượng I (gọi là itemset)

I = {i1, i2, …, im}. Một itemset gồm k items gọi là k-itemset

Mục đích của luật kết hợp là tìm ra sự kết hợp (association) hay tương quan (correlation) giữa các items. Những luật kết hợp này có dạng X =>Y

Trong Basket Analysis, luật kết hợp X =>Y có thể hiểu rằng những người mua các mặt hàng trong tập X cũng thường mua các mặt hàng trong tập Y. (X và Y gọi là itemset).

Ví dụ, nếu X = {Apple, Banana} và Y = {Cherry, Durian} và ta có luật kết hợp X =>Y thì chúng ta có thể nói rằng những người mua Apple và Banana thì cũng thường mua Cherry và Durian.

Theo quan điểm thống kê, X được xem là biến độc lập (Independent variable) còn Y được xem là biến phụ thuộc (Dependent variable)

Độ hỗ trợ (Support) và độ tin cây (Confidence) là 2 tham số dùng để đo lường luật kết hợp.

Độ hỗ trợ (Support) của luật kết hợp X =>Y là tần suất của giao dịch chứa tất cả các items trong cả hai tập X và Y. Ví dụ, support của luật X =>Y là 5% có nghĩa là 5% các giao dịch X và Y được mua cùng nhau.

Công thức để tính support của luật X =>Y như sau:

Trong đó: N là tổng số giao dịch.

Độ tin cậy (Confidence) của luật kết hợp X =>Y là xác suất xảy ra Y khi đã biết X. Ví dụ độ tin cậy của luật kết hợp {Apple} =>Banana} là 80% có nghĩa là 80% khách hàng mua Apple cũng mua Banana.

Công thức để tính độ tin cậy của luật kết hợp X =>là xác suất có điều kiện Y khi đã biết X như sau :

Trong đó: n(X) là số giao dịch chứa X

Để thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí: minimum support (min_sup) và minimum confidence (min_conf)

Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng) cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Rle)

Minimum support và Minimum confidence gọi là các giá trị ngưỡng (threshold) và phải xác định trước khi sinh các luật kết hợp.

Một itemsets mà tần suất xuất hiện của nó >= min_sup goi là frequent itemsets

Một số loại luật kết hợp

Binary association rules (luật kết hợp nhị phân): Apple => Banana

Quantitative association rules (luật kết hợp định lượng):

weight in [70kg – 90kg] => height in [170cm – 190cm]

Fuzzy association rules (Luật kết hợp mờ): weight in HEAVY => height in TALL

Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary association rules.

2.Thuật toán sinh các luật kết hợp Apriori (by Agrawal and Srikant 1994)

Tư tưởng chính của thuật toán Apriori là:

– Tìm tất cả frequent itemsets:

k-itemset (itemsets gồm k items) được dùng để tìm (k+1)- itemset.

Đầu tiên tìm 1-itemset (ký hiệu L₁). L₁ được dùng để tìm L₂ (2-itemsets). L₂ được dùng để tìm L₃ (3-itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy.

– Từ frequent itemsets sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn 2 tham số min_sup và min_conf)

Apriori Algorithm

1. Duyệt (Scan) toàn bộ transaction database để có được support S của 1-itemset, so sánh S với min_sup, để có được 1-itemset (L₁)

2. Sử dụng L_k-1 nối (join) L_k-1 để sinh ra candidate k-itemset. Loại bỏ các itemsets không phải là frequent itemsets thu được k-itemset

3. Scan transaction database để có được support của mỗi candidate k-itemset, so sánh S với min_sup để thu được frequent k –itemset (L_k)

4. Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không tìm thấy frequent itemsets)

5. Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng của I

6. Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu độ tin cậy (Confidence) của nó > =min_conf

Chẳn hạn với I= {A1,A2,A5},các tập con của I:

{A1}, {A2}, {A5}, {A1,A2},{A1,A5},{A2,A5}

sẽ có các luật sau

{A1} => {A2,A5},{A2} =>{A1,A5},{A5} =>{A1,A2}

{A1,A2} =>{A5},{A1,A5} =>{A2},{A2,A5} => {A1}

from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules
import pandas as pd
import argparse


def status(message):
    print(message)


def read_file(path):
    status("Reading file ...")
    try:
        reader = pd.read_csv(path, header=None)
        return reader
    except:
        print("File not found!")


def write_file(path, file, data):
    status("Writing " + file + " file ...")
    try:
        data.to_csv(path, index=False, header=None)
    except:
        print("Cannot write a file!")


def convert_dataset(dataset):
    status('Converting dataset to transaction...')
    data = dataset.values.tolist()
    te = TransactionEncoder()
    te_ary = te.fit(data).transform(data)
    df = pd.DataFrame(te_ary, columns=te.columns_)
    return df


def frequent_itemsets(dataset, minSupport):
    status("Creating  frequent itemsets...")
    frequent_itemsets = apriori(dataset, min_support=minSupport, use_colnames=True)
    frequent_itemsets['length'] = frequent_itemsets['itemsets'].apply(lambda x: len(x))
    return frequent_itemsets


def write_fi_file(itemsets, path):
    summary = itemsets.groupby(by='length').count()
    data = []
    for index, row in summary.iterrows():
        data.append(row['support'])
        items = itemsets[(itemsets['length'] == index)]
        for i, r in items.iterrows():
            strs = str(round(r['support'], 2)) + ' '
            for item in r['itemsets']:
                strs = strs + item + ' '

            data.append(strs)
    df = pd.DataFrame(data, columns=['A'])
    write_file(path, "FI", df)


def get_rules(frequent_itemsets, minConf):
    status("Creating  association rules...")
    rules = association_rules(frequent_itemsets, metric='confidence', min_threshold=minConf)
    rules["antecedent_len"] = rules["antecedents"].apply(lambda x: len(x))
    return rules


def write_ar_file(rules, path):
    summary = rules.groupby(by='antecedent_len').count()
    data = []
    for index, row in summary.iterrows():
        data.append(row['confidence'])
        items = rules[(rules['antecedent_len'] == index)]
        for i, r in items.iterrows():
            strs = str(round(r['confidence'], 2)) + ' '
            for item in r['antecedents']:
                strs = strs + item + ' '
            strs = strs + '==> '
            for item in r['consequents']:
                strs = strs + item + ' '
            data.append(strs)
    df = pd.DataFrame(data, columns=['A'])
    write_file(path, "AR", df)


def main(args):
    data = read_file(args.input)
    if data is not None:
        minSupport = float(args.minsup)
        minConf = float(args.minconf)
        data = convert_dataset(data)
        data = frequent_itemsets(data, minSupport)
        write_fi_file(data, args.outFI)
        data = get_rules(data, minConf)
        write_ar_file(data, args.outAR)
        status("Finish!")


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='Association rules')
    parser.add_argument('input', help='input file path')
    parser.add_argument('outFI', help='output FI file path')
    parser.add_argument('outAR', help='output AR file path')
    parser.add_argument('minsup', help='min support')
    parser.add_argument('minconf', help='min confidence')
    args = parser.parse_args()
    main(args)

100

101

102

103

104

105

106

107

from mlxtend.preprocessing import TransactionEncoder

from mlxtend.frequent_patterns import apriori

from mlxtend.frequent_patterns import association_rules

import pandas as pd

import argparse

def status(message):

print(message)

def read_file(path):

status("Reading file ...")

try:

reader = pd.read_csv(path, header=None)

return reader

except:

print("File not found!")

def write_file(path, file, data):

status("Writing " + file + " file ...")

try:

data.to_csv(path, index=False, header=None)

except:

print("Cannot write a file!")

def convert_dataset(dataset):

status('Converting dataset to transaction...')

data = dataset.values.tolist()

te = TransactionEncoder()

te_ary = te.fit(data).transform(data)

df = pd.DataFrame(te_ary, columns=te.columns_)

return df

def frequent_itemsets(dataset, minSupport):

status("Creating frequent itemsets...")

frequent_itemsets = apriori(dataset, min_support=minSupport, use_colnames=True)

frequent_itemsets['length'] = frequent_itemsets['itemsets'].apply(lambda x: len(x))

return frequent_itemsets

def write_fi_file(itemsets, path):

summary = itemsets.groupby(by='length').count()

data = []

for index, row in summary.iterrows():

data.append(row['support'])

items = itemsets[(itemsets['length'] == index)]

for i, r in items.iterrows():

strs = str(round(r['support'], 2)) + ' '

for item in r['itemsets']:

strs = strs + item + ' '

data.append(strs)

df = pd.DataFrame(data, columns=['A'])

write_file(path, "FI", df)

def get_rules(frequent_itemsets, minConf):

status("Creating association rules...")

rules = association_rules(frequent_itemsets, metric='confidence', min_threshold=minConf)

rules["antecedent_len"] = rules["antecedents"].apply(lambda x: len(x))

return rules

def write_ar_file(rules, path):

summary = rules.groupby(by='antecedent_len').count()

data = []

for index, row in summary.iterrows():

data.append(row['confidence'])

items = rules[(rules['antecedent_len'] == index)]

for i, r in items.iterrows():

strs = str(round(r['confidence'], 2)) + ' '

for item in r['antecedents']:

strs = strs + item + ' '

strs = strs + '==> '

for item in r['consequents']:

strs = strs + item + ' '

data.append(strs)

df = pd.DataFrame(data, columns=['A'])

write_file(path, "AR", df)

def main(args):

data = read_file(args.input)

if data is not None:

minSupport = float(args.minsup)

minConf = float(args.minconf)

data = convert_dataset(data)

data = frequent_itemsets(data, minSupport)

write_fi_file(data, args.outFI)

data = get_rules(data, minConf)

write_ar_file(data, args.outAR)

status("Finish!")

if __name__ == "__main__":

parser = argparse.ArgumentParser(description='Association rules')

parser.add_argument('input', help='input file path')

parser.add_argument('outFI', help='output FI file path')

parser.add_argument('outAR', help='output AR file path')

parser.add_argument('minsup', help='min support')

parser.add_argument('minconf', help='min confidence')

args = parser.parse_args()

main(args)

Programming, Network, Office, Hardware, Software, Design, Photography.. I am just a GEEK

Hi, I am

Ngô Tôn

I am a programmer.

Khai thác tập phổ biến & luật kết hợp – Association Rules

Related Articles

About ngoton

Leave a Reply

Lập trình hướng đối tượng trong Golang – OOP in Go

Java Interview Questions And Answers

Xây dựng website tự động tạo văn bản sử dụng OpenAI GPT-2

Đếm số lượng chỗ trống trong bãi đỗ xe sử dụng OpenCV Python

Ứng dụng AI cảnh báo người lạ đột nhập

Tổng hợp 1000 bài tập lập trình C/C++ từ cơ bản tới nâng cao

Hàm làm tròn số ROUND, FLOOR, CEIL – Nhật ký lập trình [Chapter 7]

Xác định góc phần tư thứ mấy trên đường tròn lượng giác

Hàm swap

Hoán vị 2 số không dùng biến tạm

Lập trình hướng đối tượng trong Golang – OOP in Go

Java Interview Questions And Answers

Xây dựng website tự động tạo văn bản sử dụng OpenAI GPT-2

Đếm số lượng chỗ trống trong bãi đỗ xe sử dụng OpenCV Python

Ứng dụng AI cảnh báo người lạ đột nhập

Tính diện tích, chu vi tam giác, đường tròn, hcn

Tạo một Custom Interceptor cho RestTemplate trong Spring Boot

Tìm cây khung nhỏ nhất với Prim & Kruskal

Kiểm tra tính đối xứng của chuỗi

Chuyển đổi từ số sang chữ trong PHP