Khóa luận tốt nghiệp Hệ thống thông tin: Phân tích hành vi của người tiêu dùng trong thị trường bằng thuật toán tìm luật kết hợp cơ bản và cải tiến

Mụcđích của những thuật toán trên chính là trích lọc những tập phô biến từ bộ đữ liệu đểtìm ra các luật kết hợp nhằm khai phá tri thức.. Luật kết hợp là một hướng nghiên cứu trong khai p

ĐẠI HỌC QUOC GIA TP HO CHÍ MINH

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

KHOA HỆ THÓNG THÔNG TIN

NGUYEN MINH TUẦN

NGUYEN DUC THANG

KHOA LUAN TOT NGHIEP

PHAN TÍCH HANH VI NGƯỜI TIÊU DUNG

TRONG THI TRUONG BANG THUAT TOAN

TIM LUAT KET HOP CO BAN VA CAI TIEN

KY SU NGANH HE THONG THONG TIN

TP HO CHÍ MINH, 2021

ĐẠI HỌC QUÓC GIA TP HÒ CHÍ MINH

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

KHOA HE THONG THONG TIN

Nguyễn Minh Tuấn — 16521381 Nguyễn Đức Thắng - 16521101

KHÓA LUẬN TÓT NGHIỆP

PHÂN TÍCH HÀNH VI NGƯỜI TIÊU DÙNG TRONG THỊ TRƯỜNG BẰNG THUẬT TOÁN

TÌM LUẬT KET HỢP CƠ BAN VÀ CẢI TIEN

KỸ SƯ NGANH HE THONG THONG TIN

GIANG VIEN HUONG DAN

TS Doan Huấn

Th.S Đỗ Thị Minh Phung

TP HO CHÍ MINH, 2021

DANH SÁCH HỘI ĐÒNG BẢO VỆ KHÓA LUẬN

Hội đồng chấm khóa luận tốt nghiệp, thành lập theo Quyết định số

.-T8ầy của Hiệu trưởng Trường Đại học Công nghệ Thông tin.

¬ ——— — Chủ tịch.

LỜI CẢM ƠN

Trước tiên, chúng em xin cảm ơn tất cả các giảng viên khoa Hệ thống Thông Tin — Đại

học Công Nghệ Thông Tin đã trực tiếp giảng dạy và cung cấp cho chúng em nhiều kiến

thức nền tảng quý giá trong suốt thời gian học tập tại môi trường đại học Đặc biệt, chúng

em xin chân thành cảm ơn sâu sắc đến TS Đoàn Huan và ThS Đỗ Thị Minh Phụng đã trực

tiếp hướng dẫn, hỗ trợ giúp đỡ chúng em trong suốt quá trình thực hiện khóa luận Tiếp

theo, chúng em xin chân thành cảm ơn tác giả K.Rajeswari, R Garg, Mohammed

AI-Maolegi và một số tác giả khác đã cung cấp tài liệu tham khảo với những giải đáp bồ ích

về thuật toán, tác giả Mukesh Kumar và cửa hàng Tạp hoá xanh đã cung cấp dữ liệu thực

nghiệm trong quá trình thực hiện đánh giá thực nghiệm Chúng em cũng không quên sự

giúp đỡ của cựu sinh viên đã cung cấp luận văn tốt nghiệp mà họ đã thực hiện trước đó dé chúng em tham khảo cách trình bày cũng như những vấn đề về nội dung liên quan Xin chân thành cảm ơn tất cả mọi người đã giúp đỡ chúng em trong quá trình thực hiện khoá luận, ho là những nhân tổ hết sức quan trọng dé chúng em có thé hoàn thành luận văn này.

Cuối cùng, chúng em xin bày tỏ lòng biết ơn sâu sắc đến gia đình, bạn bè, người thân đã

khích lệ, động viên chúng em suốt thời gian thực hiện đề tài này.

Thành phó Hồ Chí Minh, ngày 30 tháng 12 năm 2020

Sinh viên thực hiện

Nguyễn Minh Tuan — Nguyễn Đức Thắng

LỜI CAM ĐOAN

Chúng em, Nguyễn Minh Tuân — Nguyễn Đức Thắng xác nhận nội dung trình bay trong báo cáo này dựa trên những tổng hợp lý thuyết và kiến thức tích lũy của bản thân Các số

liệu, những kết luận nghiên cứu được trình bày trong luận văn này là trung thực và chưa từng được công bố dưới bat cứ hình thức nào Moi thông tin trích dẫn đều được chú thích

và liệt kê rõ ràng thành các tài liệu tham khảo Chúng em xác nhận báo cáo khóa luận tốt nghiệp này là công trình nghiên cứu của chúng em dưới sự hướng dẫn của TS Đoàn Huan,

ThS Đỗ Thị Minh Phụng và sự giúp đỡ của những cá nhân khác đã được ghi nhận.

Thành phó Hồ Chí Minh, ngày 30 tháng 12 năm 2020

Nguyễn Minh Tuấn - Nguyễn Đức Thắng

LỜI NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN

Giảng viên hướng dẫn

TS Doan Huan - ThS Đỗ Thị Minh Phụng

LỜI NHẬN XÉT CỦA GIẢNG VIÊN PHẢN BIỆN

Giảng viên phản biện

.4 Đối tượng, phương pháp và phạm vi nghiên cứu

5 Nội dung nghiên CỨU -¿ ¿+55 3E v21 re 7

6 Kết quả dự kiến

na na ca 8

Chuong2 | KHAI PHA DU LIEU - LUAT KET HỢP

2.1 Giới 060-1) nnn 10

2.1.1 Khái niệm khai phá luật kết hợp

2.1.2 Bài toán khai phá luật kết hợp -: -¿+5cs++2sz+cvsesrx 13

2.2 Thuật toán Apiori

2.2.1 Các khái niệm cơ bản - + + *k*x**E*EeEEkrkrersrekekrkrkreree 15

2.2.2 Phương pháp thực hin eee es es eseeeseseeesceeeeeeneneseeeeseeeeee 17 2.2.2.1 Mô ta eececcccccccceseceseeeseeseseessseessseessseessseessseessseessasessseenseeesseeenseees 17 2.2.2.2 Vi dỤ SH HH tre 17 2.3 Thuật toán FP Growth +: + 1 k2 SH H211 1H10 10v, 21 2.3.1 Cc khai ni€m CO baN 0117 21 2.3.2 Phương pháp thực hiện - ¿- + + + £+++**£sEserrersrekree 21 2.3.2.1 Mô tả SH re 22 2.3.2.2 Ví dỤ HH re 23

"Pu IÀ háo on 26

2.4.1 Các khái niệm cơ bản c5 3c 32213213 22ESEEerEssrrreererrrrererre 28 2.4.2 Phương pháp thực hiện

2.4.2.1 Mô tả

2.4.2.2 Ví dụ.

2.5 So sánh thuật toán trên cơ sở lý thuyết -¿-©22ccs22vxesrrrersrrrrrcee 31

Chương 3 CẢI TIỀN THUẬT TOÁN APRIORI

3.1 Thuật toán Apriori cải tiến — bảng Hash -2 ©22cc225ccccccsccee 33

3.1.1 Các khái niệm cơ bản

3.1.2 Phương pháp thực hiện - -¿- ¿+ 2 + ++*+++2£s£+zzeerseeeree 34

3.1.2.1 Mô ta 3.1.2.2 Ví dụ

3.1.2.3 Mã giã AP MI xŒ iiiiee 4

3.2 Thuật toán Apriori cải tiến — giảm giao dịch cần phải duyệt - 46

3.2.1 Các khai niệm cơ bản 2c 2c 323321 £<ESEEeeEseeeeeeserrrresesre 46 3.2.2 Phương pháp thực hiện - ¿+ 2 + +++++++£+£+zzxersezxzee 46 3.2.2.1 Mô tẢ LH." HH HH HH Hư, 46 3.2.2.2 Ví dụ c2 22H 47

3.2.2.3 Mã giả HH hướn 50

3.3 So sánh 2 thuật toán cải tiến với thuật toán Apriori cơ bản 50

Chương 4 CÀI ĐẶT, THỰC NGHIỆM, ĐÁNH GIÁ THUAT TOÁN 52

4.1 Ứng dụng cai đặt và trực quan hoá kết qua 2 thuật toán cơ bản 52

4.1.1 Dữ liệu đầu vào ccccesrrrriiiriiirrrrrrirrrrie 52 4.1.2 Tiền xử lý dữ liệu - -cc©2c+c2cSreErrrerrtrerrrerrkrerree 53 4.1.3 Tổng quan mô hình thực nghiệm -¿- + 5+z+++zs++ 54

4.1.3.1 Các bước thực hiỆn - - c2 S132 2E srisrrrerrrrrrrrerrre 54

4.1.3.2 Các tham số đầu vào

4.1.3.3 Công cụ thực hiỆn - ¿có SH re 54 4.1.4 Xây dung ứng dung.

4.1.5 Thue nghiệm 5S 5+2 steeieerererey 61

4.1.5.1 Kết qua thực nghiệm với bộ đữ liệu 22-24/12/2018

4.1.5.2 Kết quả thực nghiệm với bộ dit liệu 12/2018 - 64 4.1.5.3 Kết quả thực nghiệm với bộ dữ liệu quý 4 năm 2018

4.1.6 Kết luận và đánh giá thực nghiệm - ¿+5 + +c+<++s<++ 72 4.2 Ứng dụng cài đặt Apriori và thuật toán cải tiễn 2:- ¿©5522 72 4.2.1 Dữ liệu đầu vào -22¿-222+c2EEteEEkeErkrsrkkerrkrerree 73 4.2.2 Tiền xử lý dữ liệu cccccrerrerrrrrrrrrrrrrrrrree 73 4.2.3 Tổng quan mô hình thực hiện -. ¿+z22++2zs+zz+++ 74

4.2.3.1 Các bước thực hiỆn - -.- 2 S132 ESEEseEereteerersesrrrrersre 74

4.2.3.2, Các tham số đầu vào c-+cccrtttEkiirrrrriiirrrriiirrre 74

4.2.3.3 Công cụ thực hiỆn ¿6+5 S121 SE E221 1121 1y 75 4.2.4 Xây dựng ứng dụng «ch ng rên 75

4.2.5 'Thực nghiỆm - G6 111 1 1E 1 1n Hàn TH HH it 79

4.2.5.1 Kết quả thực nghiệm với bộ dữ liệu 31 giao dịch 80 4.2.5.2 Kết quả thực nghiệm với bộ dữ liệu 51 giao dịch 82 4.2.5.3 Kết quả thực nghiệm với bộ dữ liệu 71 giao dịch 85 4.2.6 Kết luận và đánh giá -:-22:22c2c2t2EEeEEkrerrtrrrkrrrrrrerrev 88 Chương 5 KÉT LUẬN VA HƯỚNG PHAT TRIÊN -: + §9

SL ch a+ỲỪỲ345 §9

5.2 Khó khăn và hạn ChẾ - - xxx SE EEEEE E23 EEEvEEEEEEkEkrkrkrkrerrex

5.4 Tổng kết

DANH MỤC HÌNH VE

Hình 2-1: Khai phá tri thức hỗ trợ việc ra quyết định trong kinh doanh 10

Hình 2-2: Các bước trong quá trình khai phá tri thỨc - ¿ -««++<s<++<ex+++ 11 Hình 2-3: FP Tree được xây dựng - - c1 11121111 1111811111811 1181 1g rrưy 25 Hình 3-1: Mô tả quá trình tạo tập ứng viên Ck của thuật toán cải tiến 3.2 47

Hình 4-1: Giao diện “Dữ liệu đầu vào” - ứng dụng Python tìm luật kết hợp 56

Hình 4-2: Thống kê doanh thu dựa vào bộ dit liệu theo ngày -. 57

Hình 4-3: Giao diện “Thuật toán Apriori” - ứng dụng Python tìm luật kết hợp 57

Hình 4-4: Trực quan hoá luật kết hop tìm được bằng Heatmap - 59

Hình 4-5: Trực quan hoá luật kết hợp tim được bang Graph - 60

Hình 4-6: Giao diện “Thuật toán FP Growth” - ứng dụng Python tìm luật kết hợp 60 Hình 4-7: Biểu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4.1.5 L 62

Hình 4-8: Biéu đồ so sánh thời gian thực thi thuật toán ở thực nghiệm 4 1.5 1 63

Hình 4-9: Biểu đồ so sánh bộ nhớ sử dung ở thực nghiệm 4 I.5 I - - 64

Hình 4-10: Biéu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4 I.5.2 66

Hình 4-11: Biéu đồ so sánh thời gian thực thi thuật toán ở thực nghiệm 4 1.5.2 67

Hình 4-12: Biéu đồ so sánh bộ nhớ sử dụng ở thực nghiệm 4 l.5.2 - 68

Hình 4-13: Biéu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4.1.5.3 70

Hình 4-14: Biéu đồ so sánh thời gian thực thi thuật toán ở thực nghiệm 4.1.5.3 71

Hình 4-15: Biéu đồ so sánh bộ nhớ sử dụng ở thực nghiệm 4 1.5.3 - 71

Hình 4-16: Giao diện chính của ứng dụng cài đặt thuật toán cải tiễn -.-: 76

Hình 4-17: Giao diện “Dữ liệu đầu vào” - ứng dụng cài đặt thuật toán cải tiến 7Ó Hình 4-18: Giao diện “Apriori” - ứng dung cai đặt thuật toán cải tiễn - 77

Hình 4-19: Hình 4-20: Hình 4-21: Hình 4-22: Hình 4-23: Giao diện “Apriori cải tiên Hash” - ứng dụng cài đặt thuật toán cải tiên Giao diện “Apriori cải tiến giảm GD” - cài đặt thuật toán cải tiến 79

Biểu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4.2.5 81

Biểu đồ so sánh thời gian thực thi ở thực nghiệm 4.2.5 l 82

Biểu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4.2.5.2 84

Hình 4-24: Biéu đồ so sánh thời gian thực thi ở thực nghiệm 4.2.5.2 - 84Hình 4-25: Biéu đồ so sánh số lượng luật kết hợp tạo ra ở thực nghiệm 4.2.5.3 86Hình 4-26: Biéu đồ so sánh thời gian thực thi ở thực nghiệm 4.2.5.3 86Hình 4-27: Combo mua hàng (bánh đậu xanh + bánh qué) -2- +: 87Hình 4-28: Cross-sell khi mua bánh đậu xanh - - - - - +52 << << <<<+cc<+c++>ss 87

DANH MỤC BANG

Bảng 2-1: Cơ sở dữ liệu mẫu - ApriOri ¿-:- ¿5252225 St+E+EeEvztzxexervzrexererxea 15

Bang 2-2: Cơ sở dữ liệu cho ví dụ thuật toán ADFIOFI - 55c << ++sxc+sex 17

Bang 2-3: Tập Ứng Vin C” -c 111131321111 11 11 1111 11g 1 ng ng ve 18

Bang 2-5: Tap Ung Vin Ca eee eeeescccsneceseessneeeseesseceseessaeeeeecsseseeessateeeeseaeees 19

Bang 2-6: Tap phô biến Lo (2-it€ITS€(S) - E3 1E EEEEEEEEEEEEEEEEEkrkekrkrrrrrrs 19

Bảng 2-7: Tap Ứng VIÊN Ca G9 Họ ng 19

Bang 2-9: Cơ sở dữ liệu cho ví dụ thuật toán FP Growth ‹ -<<<<s<+2 23

Bang 2-10: Tập phô biến 1-itemsets sắp xếp theo thứ tự giảm dần - 23Bang 2-11: Giữ lại 1-itemsets phổ biến và sắp xếp theo thứ tự giảm dan ở mỗi TID

— Ô.c ‹< Ố ố" 24

Bang 2-12: Tập phô biến dựa trên co sở mẫu điều kiện và cây FP điều kiện 26

Bảng 2-13: Dữ liệu dạng ngang - - (c1 27 Bang 2-14: Dữ liệu dang dỌC - - c1 011112 1111 119 111 1n 1 ng ve 27

Bang 2-15: Co sở dữ liệu cho vi dụ thuật toán EClat - << «<< <<++++sess2 29

Bảng 2-16: Chuyển đôi thành đữ liệu dạng dọc (1-itemsets) ‹‹ - 29

Bang 2-17: Tập ứng viên 2-If€TnS€fS - . G1119 1119 Sky 30

Bang 2-18: Tập ứng viên 3-It€TnS€(S - 2c Q1 ng re 30

Bang 2-19: So sánh 3 thuật toán dự trên cơ sở lý thuyết [10] - 5: 32

Bảng 3-2: Bang Hash sau khi duyệt qua giao dich 'TT - «5+ <+sxccess 35 Bang 3-3: Bang Hash sau khi duyệt qua giao dịch T2 << «<< ss+++sssesss 36 Bang 3-4: Bang Hash sau khi duyệt qua giao dịch T3 - << << ss+<<s<sess2 36 Bảng 3-5: Bang Hash sau khi duyệt qua giao dịch 'Ï4 - - «5s sssxcesss 37 Bảng 3-6: Bang Hash sau khi duyệt qua giao dich TS - «sec 38 Bang 3-7: Bang Hash sau khi duyệt qua giao dịch “T6 << 5< s++<sssess2 39 Bang 3-8: Bang Hash sau khi duyệt qua giao dịch T7 -. +5 s5 + s+++<ssx+sss 40

Bang 3-9: Bang Hash sau khi duyệt qua giao dịch T8 << << <s+<<sssess2 41

Bang 3-10: Bang Hash sau khi duyệt qua giao dich 'T9 - -.-csssssss++ssersses 42

Bang 3-11: Bang Hash sau khi đã sắp xếp theo số lượng giảm dan No_of_Itemset43 Bảng 3-12: Bảng Hash sau khi loại bỏ các dòng không thoả điều kiện minsupport44 Bảng 3-13: Dữ liệu ví dụ - thuật toán cải CHEN 3.2 tt n SE ng re 47

Bảng 4-1: Mô tả thuộc tính của bộ dữ liệu cửa hàng qua tặng ở Anh 53

Bảng 4-2: Kết quả thực nghiệm Python với bộ dữ liệu 22-24/12/2018 61

Bảng 4-3: Kết quả thực nghiệm Python với bộ dữ liệu tháng 12/2018 65

Bang 4-4: Kết quả thực nghiệm Python với bộ dit liệu quý 4 năm 2018 69

Bang 4-5: Thuộc tính bộ dir liệu Taphoaxanh - s5 + *++svesseeereses 73 Bảng 4-6: Kết quả thực nghiệm C# với bộ dữ liệu 31 giao dịch 80

Bảng 4-7: Kết quả thực nghiệm C# với bộ dữ liệu 51 giao dịch - 83

Bảng 4-8: Kết quả thực nghiệm C# với bộ dit liệu 71 giao dịch -. 85

DANH MỤC TU VIET TAT

CSDL Co sở dữ liệu

TPB Tập phô biến

LKH Luật kết hợp

KPLKH Khai phá luật kết hợpMINCONF Độ tin cậy tối thiểu

MIINSUP Độ hỗ trợ tối thiểu

TID Mã giao dịch/hoá đơn

Ck Tap ứng viên Ck

Lk Tập pho biến Lk

TÓM TÁT KHÓA LUẬN

Hiện nay, có rất nhiều thuật toán có thể dung dé khai phá luật kết hợp ví dụ như FPGrowth, EClat, nhưng phổ biến và lâu đời nhất chính là thuật toán Apriori Mụcđích của những thuật toán trên chính là trích lọc những tập phô biến từ bộ đữ liệu đểtìm ra các luật kết hợp nhằm khai phá tri thức Các luật kết hợp này là cơ sở giúpdoanh nghiệp lập ra những chiến lược marketing, chương trình khuyến mãi sản phẩm,

up-sell và cross-sell Phạm vi dé tai là tìm luật kết hợp đối với một cửa hàng cụ thê.

Khoá luận này sẽ đề cập đến cơ sở lý thuyết của ba thuật toán Apriori, FP Growth,EClat và đồng thời so sánh hiệu năng giữa Apriori và FP Growth băng ngôn ngữPython trên bộ dữ liệu cửa hàng quà tặng ở Anh Phần tiếp theo, khoá luận sẽ nêu rahai phương pháp cải tiến thuật toán Apriori Một là cải tiễn bằng bảng Hash — giảm

số lần duyệt cơ sở dữ liệu xuống còn 1 lần.Hai là cải tiến thông qua việc giảm số giao

dịch cần duyệt qua cơ sở đữ liệu mỗi khi tính support (độ hỗ trợ) của tập ứng viên

Cả hai phương pháp cải tién đều cho ra kết quả nhanh hơn thuật toán Apriori cơ bản

MỞ ĐẦU

Dữ liệu là một thành phần hết sức quan trọng không những trong các lĩnh vực nghiêncứu khoa học mà còn trong đời sống thực tế Quả thực, ngày nay con người tiếp cậnvới rất nhiều nguồn dữ liệu khác nhau, đa dạng về số lượng lẫn chất lượng thông tin,

tri thức ma con người có thé nhận thức được rất hạn chế Vì vậy, sự ra đời của khai

phá dữ liệu trong lĩnh vực khoa học máy tính đã góp phan to lớn trong việc giúp đỡcon người tiếp cận được những thông tin, tri thức quý giá tiềm tàng từ những nguồn

dữ liệu không 16 Cụ thé hơn trong lĩnh vực thương mại điện tử, bán lẻ những câuhỏi rất phô biến đối với một chủ doanh nghiệp, các cấp lập chiến lược kinh doanh và

Marketing: làm thé nào dé kích thích sức mua hay đưa ra chiến dịch khuyến mãi như

thé nào là hợp ly, Hàng ngàn câu hỏi đặt ra chi với một mục đích duy nhất là tăngdoanh thu dựa trên các chiến lược Marketing, khuyến mãi, up-sell và cross-sell phù

hợp nhất với người tiêu dùng Đề giải quyết vấn đề đó, luật kết hợp ra đời, tìm ra các

thuật toán và áp dụng vào những lĩnh vực cụ thể của đời sông dé đưa ra tập luật kếthợp phô biến, đó xem như là những lời gợi ý, lời khuyên dé cải thiện việc kinh doanhcủa cửa hàng Luật kết hợp là một hướng nghiên cứu trong khai phá dữ liệu đặc biệt

được quan tâm của các nhà khoa học từ những đầu năm thập niên 90 và không ngừngđược nghiên cứu và phát triển đến hiện nay Thông qua quá trình nghiên cứu của các

nhà khoa học, nhiều hướng tiếp cận ra đời nhằm giải quyết vấn đề trên Trong khoáluận tốt nghiệp lần này, chúng em lựa chọn đề tài này dé thực hiện dé nghiên cứu một

số van đề cơ bản của luật kết hợp, tìm hiểu thuật toán cải tiễn dựa trên thuật toán cơ

bản và xây dựng chương trình giúp tìm luật kết hợp và trực quan hoá kết quả đó Mụcđích chính của khóa luận là tìm hiểu cơ sở lý thuyết và thực nghiệm một số thuật toánluật kết hợp Qua đó, phân tích được ưu nhược điểm của từng phương pháp, giải thuật

dé giúp các nhà phát triển phần mềm có thé lựa chọn được hướng tiếp cận phù hợp

với từng ứng dụng khác nhau Do thời gian nghiên cứu giới hạn, nội dung đề tài còn

nhiều hạn chế và không tránh khỏi những thiếu sót, kính mong quý Thay Cô, bạn bèđóng góp ý kiến dé dé tài được hoàn thiện hơn

Chương 1 TONG QUAN DE TÀI

Đề mở đầu cho khóa luận tốt nghiệp “Phân tích hành vi của người tiêu dùng trong thitrường băng thuật toán tìm luật kết hợp co bản và cải tiến”, nội dung chương sẽ giới

thiệu tong quát về dé tài Nội dung trình bày của chương bao gồm: khái quát van dé

chính của đề tài, mục tiêu cùng với phương pháp nghiên cứu và nội dung thực hiện.Bên cạnh đó, phạm vi của đề tài và các kết quả dự kiến của đề tài cũng sẽ được trìnhbày chỉ tiết trong chương này

thức muốn thu được từ dữ liệu mà ta sử dụng các phương pháp khai phá phù hợp

Bên cạnh đó, khai phá dữ liệu còn giúp quá trình tìm thông kiếm thông tin tốt hơnvới người dùng hay việc chăm sóc khách hàng, bán hàng tốt hơn đối với các doanhnghiệp Chúng ta rất quen thuộc với việc tìm kiếm trên google, chúng ta đã thử đặtcâu hỏi tại sao google có thể tìm kiếm một cách nhanh và thông minh đến vậy và dữ

liệu vô cùng phong phú trên tât cả các mặt các lĩnh vực của đời sông xã hội?

Hay việc mua bán sách trực tuyến trên trang nồi tiếng amazon.com, ban để ý rang

mỗi khi bạn xem thông tin chỉ tiết về một quyền sách nào đó trên site thì bao giờ cũngkèm theo 1 danh sách các quyên sách gợi ý mua kèm theo quyền ban đang xem, mộtthống kê cho thấy có tới trên 70% đầu sách được người dùng mua thêm thông quahình thức gợi ý này Vậy điều gì làm cho việc bán sách hiệu quả đến như vậy?

Tất cả những điều đạt được như vậy là nhờ công nghệ khai phá dữ liệu (data mining).Công nghệ này bao gồm việc tìm tòi và phân tích các khối dit liệu lớn dé chat lọc rađược những mẫu hình và xu hướng có ý nghĩa Nó được sử dụng trong nhiều mụcđích khác nhau như tiếp thị theo cơ sở dữ liệu, quản trị rủi ro tín dụng, phòng chốnggian lận, loc mail rác, hoặc đơn giản là dé tìm hiểu tâm lí và ý kiến của người dùng.

Đó cũng chính là một trong những mục tiêu phô biến nhất hiện nay Hiện nay, có rất

nhiều những tác vụ khai phá dữ liệu, nhưng được sử dụng nhiều va phổ biến trong

thương mại điện tử không thé không ké đến Association rule — một phương pháp khai

phá dữ liệu nhăm đưa ra các tập luật phô biến cho các sản phẩm thường được muacùng nhau Những tập luật này góp phần hỗ trợ cho các chiến dịch marketing cũngnhư đóng góp không nhỏ trong quá trình đưa ra quyết định của các cấp lập chiến lược(tạo chương trình khuyến mãi, chạy quảng cáo) Các thuật toán nổi tiếng có thể kếđến đối với phương pháp khai phá này là thuật toán Apriori, thuật toán FP Growth,

thuật toán Eclat.

Tuy nhiên, do thuật toán Apriori đã phát triên từ rất lâu nên có nhiều khuyết điểmnhư tốc độ xử lý, duyệt cơ sở dữ liệu quá nhiều lần Do đó, trong phạm vi Khoá luậntốt nghiệp lần này, nhóm em sẽ tìm hiểu và thực hiện cài đặt 2 thuật toán cải tiễn cùng

với đó là so sánh 2 thuật toán co bản Apriori, FP Growth và trực quan hoá các tap

luật trích xuất được

1.2 Mục tiêu

Khóa luận được thực hiện với bảy mục tiêu chính:

Thứ nhất, tìm hiểu về luật kết hợp và các thuật toán tìm luật kết hợp tiêu biểu, gồm:

Thứ ba, thực hiện xây dựng cai đặt các thuật toán tiêu biểu và thực nghiệm trên một

số bộ dữ liệu khác nhau

Thứ tư, trực quan hoá tập luật thu được từ thực nghiêm hai thuật toán tiêu biểu Apriori

va FP Growth trên thành các dạng biéu dé:

- Heatmap

- Graph

Thứ năm, dựa trên thực nghiệm với một số bộ dữ liệu khác và các chỉ số được tông

hợp từ việc cài đặt thuật toán dé đưa ra so sánh giữa hai thuật toán tiêu biểu dựa trên

các tiêu chí như thời gian, số lượng tập luật được sinh ra, hiệu năng (dung lượng bộ

Thứ bảy, xây dựng chương trình minh hoạ dựa trên thư viện Python để trực quan hoá

kết quả cho thuật toán tìm luật kết hợp tiêu biểu và xây dựng chương trình cài đặt haithuật toán cải tiến

1.3 Ý nghĩa đề tài

Ý nghĩa thực tế:

-_ Việc áp dụng Khai phá dit liệu mà cụ thé là luật kết hợp giúp các doanh nghiệp

có cái nhìn khác về dữ liệu rằng chúng không chỉ để xuất ra báo cáo doanh thuhàng tháng, năm mà còn có thê đưa ra một số gợi ý nhằm cài thiện tình hìnhkinh doanh mà cụ thê trong phạm vi đề tài lần này là ở một cửa hàng cụ thể,không phải trường hợp nhiều chi nhánh

- Goi ý đó trong phạm vi dé tài này chính là các sản phẩm thường được mua

cùng với nhau Từ đó, bộ phận kinh doanh có thê xem xét và điêu chỉnh các

chiến lược ví dụ như: cách bố trí sản pham tai quay hàng, danh sách sản phẩm

đề xuất khi khách hàng mua hàng online, chương trình khuyến mãi [1] [2],

Ngoài những lợi ích về phía chủ doanh nghiệp, khách hàng cũng được hưởng

các lợi ích như: rút ngăn thời gian trong quá trình di chuyển mua hàng, cónhững chương trình khuyến mãi hấp dẫn và phù hợp với nhu cầu [2] [3]

Tạo tiền đề dé phát triển các ứng dụng khác

Ý nghĩa nghiên cứu khoa học:

Đề tài về Khai phá luật kết hợp có lẽ tuy đã khá phố biến nhưng những ứngdụng của nó vẫn rất hữu ích

Do đó, các nhà khoa học không ngừng tìm hiểu thêm những thuật toán mớicũng như cải tiễn thuật toán cũ và trong đề tài này nhóm em thực hiện dựa trênmột bài báo khoa học vào năm 2012 và một bài báo vào năm 2014.

1.4 Đối tượng, phương pháp và phạm vi nghiên cứu

Đối tượng nghiên cứu

Kỹ thuật khai phá dữ liệu.

Thuật toán cải tiến

Luật kết hợp, chức năng, vấn đề tồn tại và các kỹ thuật giải quyết

Phương pháp đánh giá thuật toán.

Phạm vi nghiên cứu

Tìm hiểu phương pháp phân tích dữ liệu, thực nghiệm và cài đặt lại thuật toán

Apriori va FP Growth dựa vào thư viện mlxtend trên Python.

Bộ dữ liệu được lấy từ nguồn Kaggle — Online Retail Data v3 (2017) bao gồm

Bill (Mã giao dịch), MerchandiseID (Mã sản phẩm), Product (Tên sản phẩm), Quota (Số lượng), BillDate (Ngày giao dịch), Amount (Giá/sản phẩm),

CustomerID (Mã khách hàng), Country (Quốc gia)

Xây dựng chương trình cài đặt hai thuật toán cải tiến và so sánh với thuật toán

Apriori.

Bộ dữ liệu của cửa hàng tạp hoá thực phẩm xanh tại Việt Nam.

Phương pháp nghiên cứu

1.5.

1.6.

Tìm hiểu phương pháp phân tích thuật toán:

Association Rule Mining (Apriori Algorithm) Association Rule Mining (FP-Growth)

Association Rule Mining (EClaT) Cai đặt thuật toán Apriori va FP Growth.

So sánh các thuật toán.

Cải tiến thuật toán

Tìm hiểu các kỹ thuật trực quan hóa dữ liệu

Xây dựng tool bằng ngôn ngữ Python nhăm trực quan hóa các số liệu phân

tích và các luật được sinh ra.

Phân tích, nhận xét kết quả thực nghiệmXây dựng chương trình cài đặt hai thuật toán cải tiễn và so sánh với thuật toán

Apriori cơ bản.

Nội dung nghiên cứu

Khảo sát nghiên cứu các vấn đề về luật kết hợp, các phương pháp, giải thuật

giải quyết và so sánh ưu nhược điểm của từng phương pháp

Phân tích dữ liệu thực tế từ một cửa hàng quà tặng online ở Châu Âu (2017),cửa hàng tạp hoá thực pham xanh tai Viét Nam

Đề xuất cải thiện thuật toán

Thực nghiệm, đánh giá các thuật toán, đưa ra so sánh và báo cáo kêt quả.

Kết quả dự kiến

Các kêt quả dự kiên của khóa luận như sau:

So sánh ưu nhược điểm của 2 thuật toán cơ bản: Apiori, FP Growth

Truc quan hoá các tập luật kết hợp.

Dé xuât thuật toán cải tiên.

- Phan tích, nhận xét kết quả thực nghiệm.

1.7 Bố cục báo cáo

Báo cáo được chia thành năm chương, phần còn lại được bố cục như sau:

Chương 2 — Luật kết hợp

Nội dung chương sẽ khái quát hóa những van dé về luật kết hợp bao gồm định nghĩa

luật kết hợp, các chức năng, van đề và kỹ thuật tiếp cận của luật kết hợp Apiori, FP

Growth và Eclat sẽ là các thuật toán co bản được dé cập trong chương này

Chương 3 — Thuật toán cải tiễn

Hiện nay, có rât nhiêu thuật toán mới ra đời nhăm giải quyêt những hạn chê của các

thuật toán cơ bản Tuy nhiên, vẫn còn một hướng nghiên cứu khác đó chính là cải

tiên những thuật toán cũ Chương này sẽ nói về một thuật toán cải tiên và cơ sở lýthuyết của phương pháp này

Chương 4— Đánh gia

Đề kiểm chứng tính hiệu quả của các thuật toán đã được trình bày trong chương 2 va

3, các thuật toán phải được thực nghiệm thực tế thông qua các bộ dữ liệu khác nhau

và dựa trên các chỉ số đánh giá khác nhau Nội dung của chương sẽ trình bày phương

pháp thực hiện thực nghiệm, sau đó so sánh các kết quả thực nghiệm thực tế dé có

thể phân tích những ưu, nhược điểm của từng thuật toán

Chương 5 — Kết luận và hướng phát triển

Nội dung trình bày tổng quan những nội dung được thực hiện trong khóa luận, nhữngthành quả cũng như những hạn chế khóa luận gặp phải Bên cạnh đó đưa ra những

hướng phát triển của đề tài trong tương lai

Chương 2 KHAI PHA DU LIEU - LUAT KET HỢP

Khai pha dữ liệu là một bước trong quá trình khám phá tri thức, bao gồm các thuậttoán chuyên dụng đáp ứng một số yêu cầu về hiệu quả tính toán dé tim ra các mẫu

hoặc các mô hình tồn tại bên trong cơ sở dữ liệu đang bị che khuất Dé tìm ra các

mau, mô hình tiềm 4n có tính tri thức các chuyên gia phải tìm và áp dụng các phương

pháp, kỹ thuật khai phá sao cho các kỹ thuật và phương pháp này phải phù hợp vớitính chất, đặc trưng của dữ liệu và mục đích sử dụng Tuy khai phá dữ liệu chỉ là mộtbước trong quá trình khám phá tri thức nhưng nó lại là bước tiên quyết, quan trọng

và anh hưởng đến toàn bộ quá trình!.

Mục đích của khai phá dữ liệu là phát hiện tri thức phục vụ cho các lợi ích trong thực

tế và các yêu cầu trong nghiên cứu học thuật Do đó chúng ta có thể coi mục đích

chính của khai phá dữ liệu là mô tả (description) và dự đoán (prediction) Dự đoán

liên quan đến việc sử dụng các biến hoặc các trường trong cơ sở dữ liệu dé chiết xuất

ra các mẫu nhằm dự đoán những giá trị chưa biết hoặc giá tri của các biến sẽ được

quan tâm trong tương lai Mô tả tập trung vào việc tìm kiếm các mẫu biểu diễn dữliệu mà con người có thể hiểu được [1] [4]

Khai phá dữ liệu còn là sự kết hợp của nhiều ngành như: Cơ sở dữ liệu, giải thuật(Algorithm), thông kê (Statistics), nhận dạng mẫu (Pattern recognition), trực quan

hoá dữ liệu (Visualization), máy học (Machine learning), trí tuệ nhân tạo (Artificial

Intelligent), lý thuyết thông tin, tính toán hiệu năng cao (High-performance

computing), và các phương pháp tính toán mềm

! https://vi.wikipedia.org/wiki/ truy cập lần cuối vào 20/10/2020

Increasing potential

to support

Decision Making

Business Analyst Data Presentation

Visualization Techniques

Data Analyst Data Mining

Information Discovery

Data Exploration

Statistical Summary, Querying, and Reporting

Data Preprocessing/Integration, Data Warehouses

Data Sources —_

Paper, Files, Web documents, Scientific experiments, Database Systems

Hình 2-1: Khai phá tri thức hỗ trợ việc ra quyết định trong kinh doanh?

Lợi ích đến từ khai phá dữ liệu có thê nói là rất lớn nhưng bên cạnh đó vẫn luôn tồntại song song nhiều thách thức và khó khăn trong quá trình khám phá tri thức và khaiphá dữ liệu Một số các thách thức và khó khăn cần được quan tâm là về kích thước

dữ liệu, thay đổi dữ liệu và tri thức, dữ liệu bị thiếu và bị nhiễu, mối quan hệ phức

tạp giữa các trưởng, vấn đề từ phía người dùng và việc tích hợp với các hệ thống

khác.

2.1 Giới thiệu

Thuật ngữ Khai phá dữ liệu ra đời vào cuối những năm 80 thé kỷ trước Có nhiềuđịnh nghĩa khác nhau về khai phá đữ liệu, nhưng diễn đạt một cách dễ hiểu thì khaiphá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) có ích, tiềm ân và mangtính dự đoán trong các khối cơ sở đữ liệu lớn [5]

Một số nhà khoa học xem khai phá dữ liệu như là một cách gọi khác của một thuậtngữ rất thông dụng là khám phá tri thức trong Cơ sở dữ liệu (Knowlwdge Discovery

? https://www.geeksforgeeks.org/data-mining-process/ truy cập lần cuối vào 20/10/2020

10

in Data bases), vì cho rằng mục đích của quá trình khám phá tri thức là thông tin làtri thức có ích, những đối tượng mà chúng ta phải xử lý rất nhiều trong suốt quá trình

khám phá tri thức lại chính là dữ liệu Một số nhà khoa học khác thì xem khai phá dữ

liệu như một bước chính trong quá trình khám phá tri thức.

Khai phá dữ liệu là một bước của quá trình khai phá tri thức (Knowledge Discovery

Process) [5], bao gồm nhiều bước:

Nghiên cứu và đặt bài toán

J

Tao va thu nhập dữ liệu dau vào

Tiên xử ly dữ liệu: làm sạch, mã hóa

Hình 2-2: Các bước trong quá trình khai phá tri thức”

- Bước 1: Nhằm tìm hiểu lĩnh vực ứng dụng từ đó hình thành nên bài toán cần

giải, xác định các nhiệm vụ cần phải hoàn thành Tạo tiền đề cho việc hìnhthành nên đữ liệu cần thu thập

3 https://viblo.asia/p/kho-du-lieu-va-khai-pha-du-lieu-tiep-djeZ.1DjSKWz truy cập lần cuối vào 20/10/2020

11

- _ Bước 2: Mục tiêu là tìm kiếm thu thập dữ liệu sẵn có hoặc tạo mới theo yêu

cầu của bài toán đã đặt ra nhằm có được nguồn dữ liệu thích hợp với mục đíchứng dụng và bản chất của dữ liệu

- _ Bước 3: Là thu thập và xử lý thô, (tiền xử lý dữ liệu) nhằm loại bỏ nhiễu, xử

lý việc dữ liệu bị thiếu, bị thừa hoặc không có thông tin Gọi chung là làm sạch

dữ liệu

- Bước 4: Là quá trình lựa chọn các thuộc tính cần thiết phù hợp cho việc phân

tích để sử dụng xây dựng mô hình, thuật toán Sau đó dữ liệu được chuyên đôihoặc hợp nhất thành một thé thích hợp phù hợp cho việc khai phá

- Bước 5: Đây là bước quan trọng nhất nhăm rút ra các tri thức Quá trình này

thực hiện bằng các thuật toán đề xây dựng mô hình đủ độ tin cậy theo yêu cầu,

mục đích đã đặt ra Kết quả cho ta một nguồn tri thức thô

- Bước 6: Bước này nhằm đánh giá lại kết quả tìm kiếm tri thức dựa trên một số

tiêu chí, chỉ tiêu đánh giá.

- Bước 7: Hiéu tri thức đã tìm được, làm sáng tỏ các mô tả và dự đoán

Quá trình khai phá tri thức không chỉ là một quá trình tuần tự từ bước đầu tiên đếnbước cuôi cùng mà là một quá trình lặp và có thê quay trở lại các bước đã qua.

Như vậy khai phá dit liệu là một trong những giai đoạn quan trọng nhất trong quitrình phát hiện tri thức Bước này gồm có các thuật toán khai phá dữ liệu có hiệu quả

tính toán chấp nhận được dé tìm ra các mẫu hoặc các mô hình trong dữ liệu Nói một

cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu

hoặc các mô hình dang tôn tại trong cơ sở dir liệu.

Trong các phương pháp khai phá dữ liệu, có ba phương pháp được các nhà nghiên

cứu sử dụng nhiều nhất đó là: luật kết hợp, phân lớp dit liệu và phân cum dé liệu

Trong phạm vi khoá luận lần này, nhóm em sẽ tập trung tìm hiểu về phương phápkhai phá dữ liệu — Luật kết hợp và đề xuất hai thuật toán cải tiến dựa trên thuật toánApriori — một trong những thuật toán phố biến và được ứng dụng rộng rãi trong kinh

doanh và Marketing.

12

2.1.1 Khai niệm khai phá luật kết hợp

Khai phá luật kết hợp là một kĩ thuật quan trọng của khai phá dữ liệu Mục tiêu nhằm

phát hiện môi quan hệ giữa các sản phâm được mua.

Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn gọi

là mô hình cơ bản) được R Agrawal, T Imielinski và A Swami dé xuất vào năm

1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các

mối quan hệ giữa các tập hàng hóa (Itemsets) đã bán được tại các siêu thị [8] [6].

Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng như không

dựa vào các đặc tính đữ liệu vốn có của các mục dữ liệu mà chỉ dựa vào sự xuất hiện

cùng lúc của chúng.

Luật kết hợp, do đó thích hợp với mục tiêu thăm dò dữ liệu, phát hiện mối liên hệ

giữa các yếu tô và biến kết quả, bao gồm quan hệ tương tac

Kết quả của luật kết hợp phụ thuộc rất lớn vào cỡ mẫu và bị chỉ phối bởi những điềukiện chủ quan của người dùng (về ngưỡng support và confidence) vì vậy dễ bị ảnh

hưởng bởi cảm tính chủ quan hơn so với giải thuật cây quyết định và log-linear các

thuật toán xây dựng hệ khuyến nghị

2.1.2 Bài toán khai phá luật kết hợp

Bài toán khai phá luật kết hợp có thê phát biêu như sau: Cho cơ sở dữ liệu giao tác,ngưỡng độ hỗ trợ tối thiêu (minsup) và ngưỡng độ tin cậy tối thiểu (minconf)

Yêu cầu: Tìm tất cả các luật kết hợp X>Y trên co sở dữ liệu sao cho

sup(X—>Y) = minsup va conf (X—>Y) = minconf [6] [2].

Khai phá luật kết hợp được gọi là bài toán cơ ban hay bài toán nhị phân, vi ở đây, giá

trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện hay không xuất hiện)

[5].

Bài toán khai phá luật kết hợp trong cơ sở dữ liệu chia thành hai bài toán con:

13

1 Tìm tat cả các tập mục phổ biến: Một tập mục là phổ biến được xác định qua

tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu

2 Sinh ra các luật kết hợp từ các tập mục phô biến đã tìm được thỏa mãn độ tin

cậy tôi thiêu cho trước.

Khi khai phá luật kết hợp trong cơ sở dữ liệu thì mọi khó khăn nằm ở bài toán thứnhất là tìm tập mục phô biến

Ở các mục sau trong chương 2, phần cơ sở lý thuyết của một số thuật toán ứng dụng

trong luật kết hợp sẽ được trình bày

2.2 Thuật toán Apiori

Thuật toán Apriori được công bố bởi R Agrawal và R Srikant vào năm 1994 vì détìm các tập phô biến trong một bộ dữ liệu lớn Tên của thuật toán là Apriori vì nó sử

dụng kiến thức đã có từ trước (prior) về các thuộc tinh, vật phâm thường xuyên xuất

hiện trong cơ sở dữ liệu Thuật toán Apriori sẽ tạo ra tập phố biến thông qua việc tạocác tập ứng viên và loại bỏ các tập ứng viên này theo điều kiện minsupport Luật kếthợp sẽ được sinh ra từ các tập pho bién va cũng được lọc theo một điều kiện đó là

ngưỡng minconfidence [7] [9].

14

2.2.1 Cac khái niệm cơ bản

Đề minh hoạ cho các khái niệm của thuật toán Apiori [6] [2], ta dùng cơ sở dữ liệu

như sau:

—

\S |œI¬|ICŒ|C:.|+|tC›|`

e Hạng mục (item): A = apple, B = bread, C = cereal, D = donuts, E = eggs.

e Tập các hạng mục (itemset): danh sách các hang mục trong giỏ hang như {A,

B,C, E}.

e Giao dich (transaction): tập các hạng mục được mua trong một giỏ hàng, lưu

kèm với mã giao dịch (TID).

e Mẫu pho biến (frequent item): là mẫu xuất hiện thường xuyên trong tập dữ

liệu như {A, C} xuất hiện khá nhiều trong các giao dịch

e Tap k-hạng mục (k-itemset): ví dụ danh sách sản phẩm (1-itemset) như {A, B,

C}, danh sách cặp sản phẩm đi kèm (2-itemset) như {{A, B}, {A, C}, {B, C}},

danh sách 3 sản phẩm đi kèm (3-itemset) như {{A, B, C}, {A, C, E}}

count(X )

———— X=B, C là tập các

ID

e Độ pho biến (support): được tinh bằng supp(X) =

hạng mục, D là cơ sở dtr liệu (CSDL) giao dịch.

15

Tập pho bién (frequent itemset): là tập các hạng mục X (itemset) thỏa mãn độ

phô biến tối thiêu (minsupp — do người dùng xác định như 40% hoặc xuất hiện

5 lan) Nếu suppCX) > minsupp thì X là tập phô biến

Tập pho biến tối đại (max pattern) thỏa

1 supp(X) = minsupp

2 không tồn tại |X'| > |X|, với X’ cũng phô biếnTập phô biến đóng (closed pattern) thỏa

1 supp(X) = minsupp

2 không tồn tai [X’| > |X| mà supp(X’) = supp(X)

Luat két hop (association rule): kí hiệu x +y, nghĩa là khi X có mặt thì Y

cũng có mặt (với xác suất nào đó) Ví dụ, A>B; ø->C; A,B—>D

Độ tin cay (confidence) [9]: được tính băng công thức

Conf(X > Y)= support(X UY) (1.1)

e_ Bước 1: Tìm tat cả các tập phô biến (theo ngưỡng minsupp)

° Bước 2: Xây dựng luật từ các tập phô biến

Đôi với môi tập phô biên S, tao ra tat cả các tập con khác rong của S.

16

- _ Đối với mỗi tập con khác rỗng A của S (IAI < ISI) Luật A—>(S—A) là luật

supp(S)

supp(A)kết hợp cần tìm nếu: conf (A> (S—A))= > minconƒ

2.2.2 Phuong pháp thực hiện

Thuật toán Apriori với mô tả chỉ tiết, ví dụ cụ thể cùng với mã giả sẽ được trình bày

trong mục này.

2.2.2.1 Mô tả

Nguyên tắc loại bỏ của Apriori: Nếu không phải là tập phô biến thì tập bao của nó

cũng không phô biến 4

Các bước dé tìm tập phố biến trong thuật toán Apriori [8]:

- Tim tat cả các tap phô biến 1- hạng mục (Li)

Tao các tập ứng viên kích thước k-hạng mục (k — candidate itemset) từ các tậpphổ biến có kích thước (k-1)-hang mục Vi dụ, tạo ứng viên Ca từ tập phdbiến Li

- _ Kiểm tra độ phô biến của các ứng viên trên CSDL và loại các ứng viên không

pho biến ta được Li (i=1, 2, , k).

- _ Dừng khi không tạo được tập phô biến hay tập ứng vién-L, =Ø hay C, =Ø

2.2.2.2 Ví dụ

Ta có bộ dữ liệu như sau với minsupp=50%

4 https://viblo.asia/ truy cập lần cuối vào 1/11/2020

17

Tu minsupp=50% suy ra minsupp=2 (2/4=50%)

Bước 1: Quét bộ dữ liệu dé tim C¡

Bước 3: Tạo tập phô biến Ca dựa trên L¡

Tap Co:

Bước 4: Loc tập C2 dựa theo supp dé tìm ra Lạ Ta loại {A, B}, {A, E} bởi vì sup(A,

B) < minsupp và sup(A, E) < minsupp

Tập La:

Bang 2-6: Tập phô biến Lạ (2-itemsets)

Bước 5: Tạo tập phổ biến C3 dựa trên La

Tap Ca:

Bảng 2-7: Tap ứng viên C3

19

Suy ra tập Ls:

Bảng 2-8: Tập pho biến La (3-itemsets)

Tại đây không thể tạo thêm tập C4 nên thuật toán kết thúc tại đây

Tập phổ biến thu được ở vi dụ trên là Lị ^ La 1 La bao gồm các tập {{A}, {B}, {C},

{E}, {A, C}, {B, C}, {B, E}, {C, E}, {B, €, E}}

20

2.3 Thuật toán FP Growth

Một phương pháp khác cho việc xác định các tập mục phổ biến là FP Growth

(Frequent Pattern Growth Algorithm).

Thuật toán FP Growth khám phá các tập phô biến frequent itemsets mà không cần

sinh ra các tập ứng cử viên (candidate itemsets).

Growth biểu diễn dữ liệu của các giao dịch bằng một cau trúc dữ liệu gọi là

FP-tree.

FP-Growth sử dụng cấu trúc FP-tree dé xác định trực tiếp các tập mục phô biến

Thuật toán được thực hiện với hai bước chính [10] [11]:

1 Xây dựng một cấu trúc dữ liệu nhỏ gọn được gọi là cây FP-tree

2 Trực tiếp trích xuất các tập phô biến frequent itemsets từ cây FP-tree

Ưu điểm của nó là xây dựng cơ sở dữ mẫu điều kiện từ cơ sở dữ liệu thỏa mãn độ hỗ

trợ tối thiểu (minsupport) Do cấu trúc cây nhỏ gọn và không tạo ra các tập ứng cửviên nên yêu cầu ít bộ nhớ hơn

2.3.1 Các khái niệm cơ bản

FP Tree: Frequent Pattern Tree là một cấu trúc giống cây được tao bằng các tập phôbiến ban đầu của cơ sở dit liệu Mục dich của cây FP là khai phá tập phổ biến nhất

Mỗi nút của cây FP đại diện cho một mục (item) của tập pho bién [10]

Nut gốc đại diện cho null trong khi các nút dưới đại diện cho các tập phổ biến Sựliên kết của các nút với các nút dưới là tập phô biến với các tập phô biến khác được

duy trì trong khi hình thành cây.

2.3.2 Phuong pháp thực hiện

Thuật toán FP Growth với mô tả chi tiết và ví dụ cụ thé sẽ được trình bày trong mục

này [12].

21

2.3.2.1 Mô tả

e Bước 1: Quét cơ sở dữ liệu dé tìm sự xuất hiện của các item trong cơ sở dữ

liệu Bước nay cũng giống như bước đầu tiên của Apriori Số lượng 1- itemsettrong cơ sở đữ liệu được gọi là support hoặc tần suất của 1- itemset Loại bỏcác item có supp(S) < minsupp Sắp xếp các mục trong giao dịch theo thứ

tự giảm dần của support (count) [11] [12]

e Bước 2: Xây dựng cây FP Gốc được dai diện bởi null [10]

e Bước 3: Duyệt qua từng giao dich và đưa các item vào cây theo thứ tự giảm

dan ở bước 1 Nếu itemset trong 1 giao dịch đã xuất hiện trên 1 nhánh của FPtree thì giao dịch đó sẽ dùng tiền tổ itemset của nhánh đó [12]

e Bước 4: Khi thêm itemset của một giao dịch vào cây thi count của item phải

được cập nhật trên nhánh [10].

e Bước 5: Khai phá cây FP và xây dựng mẫu điều kiện (Conditional pattern

base) Ở bước này, nút thấp nhất được kiểm tra đầu tiên cùng với các liên kết

của các nút thấp nhất Nút thấp nhất đại diện cho độ dài mẫu tần số 1 Từ đó,

đi qua đường dẫn trong Cay FP Đường dẫn hoặc các đường dẫn này được gọi

là cơ sở mẫu có điều kiện Cơ sở mẫu có điều kiện là một cơ sở dữ liệu con

bao gồm các đường dan tiền t6 trong cây FP với nút thấp nhất (hậu tố) [12]

[10].

e_ Bước 6: Thiết lập cây FP có điều kiện (Conditional FP Tree)

e Bước 7: Dua ra tập phổ biến dựa trên cây FP có điều kiện

Các bước 5, 6, 7 sẽ được trình bày chi tiết hon ở phan ví dụ thuật toán FP Growth

22

2.3.2.2 Ví dụ

Đề minh hoa cho thuật toán FP Growth Š, ta dùng bộ dữ liệu sau với minsupp = 50%:

Bảng 2-9: Cơ sở dữ liệu cho ví dụ thuật toán FP Growth

{a, b, c, f, 1, m, o}

{b, f, h, j, o}

{b, c, k, s, p}

{a, f, c, e, 1, p, m, n}

- _ Quét co sở dữ liệu một lần, tìm các tập phô biến 1-itemsets (chi có một hang

mục hay phan tử) và loại các mục có Frequency nhỏ hơn minsupp Sắp xếpcác tập phô biến tìm được theo thứ tự giảm dần của độ phô biến (tần số)

Bang 2-10: Tập phô biến 1-itemsets sắp xếp theo thứ tự giảm dan

5 https://viblo.asia/ truy cập lần cuối vào 1/11/2020

23

- Quét lại cơ sở dữ liệu lần 2, xây dựng một cây FP-tree bắt đầu với hạng mục

phô biến nhất trong mỗi giao dịch

- _ Với mỗi giao dich chỉ giữ lại các hạng mục phổ biến ở trong giao dịch đó và

sap xêp chúng theo thứ tự giảm dan của tân sô.

Bảng 2-11: Giữ lại 1-itemsets phố biến và sắp xếp theo thứ tự giảm dần ở mỗi TID

TID Ordered Frequent Itemset

e Néu một đường đi có tiền tố chung tồn tại: tăng tần số của các nút trên

đường đi này và nói thêm hậu to

e Ngược lại, tạo một nhánh mới.

24