Khai thác dữ liệu báo cáo chương iii phân tích luật kết hợp

PHÂN TÍCH LUẬT KẾT HỢP3.1 Giới thiệu về Luật Kết Hợp3.1.1 Định nghĩa Luật Kết Hợp Khái niệm cơ bản: Luật kết hợp, hay còn gọi là luật kết hợp Association Rules, là một kỹ thuật trong kha

BỘ GIAO THÔNG VẬN TẢI HỌC VIỆN HÀNG KHÔNG VIỆT NAM

KHOA CÔNG NGHỆ THÔNG TIN

KHAI THÁC DỮ LIỆU BÁO CÁO CHƯƠNG III: PHÂN TÍCH LUẬT KẾT HỢP

Giảng viên hướng dẫn: ThS.NCS Trần Anh Tuấn

Sinh viên/ Nhóm sinh viên thực hiện: Nhóm 02

Lớp: 010100087302

TP.Hồ Chí Minh, tháng 01/2025

Danh sách Nhóm:

1 Nguyễn Hải Đăng 225481008 3 22ĐHTT02 Thành viên Tích cực

2 Lê Phương Lâm 225481012 1 22ĐHTT03 Thành viên Tích cực

3 Trần Phan Tuyết Lan 225481013 8 22ĐHTT03 Thành viên Tích cực

4 Nguyễn Lê Thùy Linh 225481015 2 22ĐHTT03 Nhóm Trưởng Tích cực

5 Nguyễn Khả Lực 225481031

7 22ĐHTT03 Thành viên Tích cực

MỤC LỤC

CHƯƠNG 3 PHÂN TÍCH LUẬT KẾT HỢP 1

3.1 Giới thiệu về Luật Kết Hợp 1

3.2 Các Chuẩn Đo Đánh Giá Sức Mạnh của Luật Kết Hợp 2

3.2.1 Support (Hỗ trợ) 2

3.2.2 Confidence (Độ Tin Cậy) 4

3.2.3 Lift (Tỷ Lệ Nâng Cao) 5

3.2.4 Các Chỉ Số Khác 7

3.3 Các Cách Lưu Trữ Cơ Sở Dữ Liệu Giao Dịch 8

3.3.1 Cơ Sở Dữ Liệu Quan Hệ (Relational Databases) 8

3.3.2 Cơ Sở Dữ Liệu Phi Quan Hệ (NoSQL Databases) 10

3.3.3 Các Kỹ Thuật Lưu Trữ Khác 11

3.4 Thuật Toán Apriori 13

3.4.1 Nguyên Tắc Hoạt Động của Apriori 13

3.4.2 Các Bước Thực Hiện Thuật Toán Apriori 14

3.4.3 Phân Tích Phức Tạp và Tối Ưu 15

3.4.4 Ví Dụ Minh Họa 16

3.5 Áp Dụng Phân Tích Luật Kết Hợp trên Weka 22

3.5.1 Chuẩn Bị Dữ Liệu cho Weka 22

3.5.2 Thực Hiện Phân Tích Luật Kết Hợp 23

3.5.3 Đánh Giá và Giải Thích Kết Quả 24

3.5.4 Ví Dụ Minh Họa 25

Kết Luận Chương 3 27

CHƯƠNG 3 PHÂN TÍCH LUẬT KẾT HỢP3.1 Giới thiệu về Luật Kết Hợp

3.1.1 Định nghĩa Luật Kết Hợp

Khái niệm cơ bản: Luật kết hợp, hay còn gọi là luật kết hợp (Association Rules), là một kỹ thuật

trong khai thác dữ liệu được sử dụng để tìm ra các mối quan hệ, mẫu hình ẩn giữa các biến trongmột tập dữ liệu lớn Luật kết hợp thường được áp dụng trong các lĩnh vực như bán lẻ, y tế, tàichính để phát hiện các xu hướng và hành vi tiêu dùng, từ đó hỗ trợ quá trình ra quyết định

Ý nghĩa trong khai thác dữ liệu: Trong khai thác dữ liệu, luật kết hợp giúp khám phá những mối

quan hệ đáng kể giữa các mục dữ liệu, chẳng hạn như sản phẩm thường được mua cùng nhautrong một giỏ hàng Việc phát hiện các luật kết hợp này không chỉ giúp doanh nghiệp hiểu rõ hơn

về hành vi khách hàng mà còn hỗ trợ trong việc tối ưu hóa quy trình kinh doanh, tăng cường chiếnlược marketing và nâng cao trải nghiệm khách hàng

3.1.2 Lịch sử và Phát triển

Các bước tiến trong nghiên cứu luật kết hợp:

 Những năm 1990: Thuật toán Apriori được giới thiệu bởi Agrawal và Srikant, đánh dấu

sự khởi đầu của nghiên cứu luật kết hợp

 Những năm 2000: Sự phát triển của các thuật toán hiệu quả hơn như FP-Growth và Eclat,

giúp xử lý các tập dữ liệu lớn hơn

 Những năm 2010 đến nay: Ứng dụng luật kết hợp được mở rộng ra nhiều lĩnh vực khác

nhau, cùng với sự phát triển của Big Data và Machine Learning

Ứng dụng thực tiễn qua các thời kỳ:

 Bán lẻ: Phân tích giỏ hàng để xác định các sản phẩm bán cùng nhau.

 Y tế: Khám phá các mối liên hệ giữa các triệu chứng và bệnh lý.

 Tài chính: Phân tích các giao dịch để phát hiện các mẫu hành vi bất thường.

3.1.3 Các Thành phần Chính của Luật Kết Hợp

Itemset (Tập hợp các mục): Một tập hợp các mục (items) mà chúng thường xuất hiện cùng nhau

trong dữ liệu Ví dụ, trong một giỏ hàng, một itemset có thể là {sữa, bánh mì, trứng}

Support (Hỗ trợ): Đo lường tần suất xuất hiện của một itemset trong toàn bộ tập dữ liệu Support

giúp xác định mức độ phổ biến của một itemset

Confidence (Độ tin cậy): Đo lường xác suất một item xuất hiện khi một item khác đã xuất hiện.

Confidence giúp đánh giá mức độ mạnh mẽ của một luật kết hợp

Lift (Tỷ lệ nâng cao): Đo lường mức độ tăng cường của xác suất xuất hiện của một item khi biết

rằng một item khác đã xuất hiện Lift giúp xác định liệu một luật kết hợp có ý nghĩa thống kê haykhông

3.2 Các Chuẩn Đo Đánh Giá Sức Mạnh của Luật Kết Hợp

Để đánh giá hiệu quả và tính mạnh mẽ của các luật kết hợp được phát hiện trong tập dữ liệu, chúng

ta sử dụng một số chuẩn đo phổ biến Các chuẩn đo này giúp xác định mức độ liên quan và ý nghĩacủa các luật, từ đó lựa chọn ra những luật có giá trị thực tiễn cao Dưới đây là các chuẩn đo chínhđược sử dụng trong phân tích luật kết hợp:

Ý Nghĩa và Tầm Quan Trọng

 Ý nghĩa: Support phản ánh mức độ phổ biến của một itemset trong cơ sở dữ liệu Nó giúp

xác định những itemset nào xuất hiện thường xuyên và có khả năng mang lại giá trị trongviệc đưa ra quyết định kinh doanh

 Tầm quan trọng: Đặt ngưỡng support tối thiểu giúp lọc bỏ những itemset hiếm gặp, giảm

độ phức tạp của thuật toán và tập trung vào các luật có ý nghĩa thực tiễn cao

Ví Dụ Minh Họa

Ví dụ 1: Phân Tích Giỏ Hàng

Giả sử chúng ta có 1000 giao dịch mua sắm tại một cửa hàng:

 Itemset A = {Sữa} xuất hiện trong 200 giao dịch.

 Itemset B = {Bánh mì, Sữa} xuất hiện trong 50 giao dịch.

Trong 5000 giao dịch trực tuyến:

 Itemset C = {Điện thoại, Tai nghe} xuất hiện trong 300 giao dịch.

Support (C )= 300

5000=0.06(6 %)

Ví dụ 3: Ứng Dụng Trong Y Tế

 Itemset D = {Huyết áp cao, Đái tháo đường} xuất hiện trong 800 hồ sơ.

 Ý nghĩa: Confidence đánh giá mức độ tin cậy của luật kết hợp Nó cho biết tỷ lệ các giao

dịch chứa B khi đã biết chứa A

 Tầm quan trọng: Confidence giúp xác định xem luật kết hợp có mạnh mẽ và đáng tin cậy

hay không Luật với confidence cao thường có giá trị dự đoán tốt hơn

Ví Dụ Minh Họa

Ví dụ 1: Phân Tích Giỏ Hàng

Sử dụng lại ví dụ ở phần Support:

 Itemset A = {Sữa} xuất hiện trong 200 giao dịch.

 Itemset B = {Bánh mì, Sữa} xuất hiện trong 50 giao dịch.

Trong 5000 giao dịch trực tuyến:

 Itemset C = {Điện thoại} xuất hiện trong 1000 giao dịch.

 Itemset C {Tai nghe} ∪ xuất hiện trong 300 giao dịch

Confidence (C=¿Tai nghe)= 300

1000=0.3(30 %)

Ví dụ 3: Ứng Dụng Trong Y Tế

Trong 10,000 hồ sơ bệnh nhân:

 Itemset D = {Huyết áp cao} xuất hiện trong 2000 hồ sơ.

 Itemset D {Đái tháo đường} ∪ xuất hiện trong 800 hồ sơ

Confidence ( D=¿Đái tháo đường)= 800

 Ý nghĩa: Lift đánh giá xem sự xuất hiện của B có thực sự phụ thuộc vào A hay không Nếu

lift > 1, có nghĩa là B xuất hiện nhiều hơn dự kiến khi A đã xuất hiện, ngược lại nếu lift < 1thì B xuất hiện ít hơn dự kiến

 Tầm quan trọng: Lift giúp xác định mối quan hệ giữa các itemset có ý nghĩa thống kê hay

không Nó cung cấp cái nhìn sâu hơn về sự liên kết giữa các itemset so với chỉ dựa trênsupport và confidence

Conviction đo lường mức độ ngược lại khi một luật kết hợp bị vi phạm Nó được tính bằng tỷ lệgiữa xác suất không có B khi có A và xác suất không có B.

Conviction ( A=¿B)= 1− Support ( B )

1−Confidence ( A=¿B)

Ý Nghĩa và Tầm Quan Trọng

 Ý nghĩa: Conviction cho biết mức độ chắc chắn mà B sẽ xảy ra khi A xảy ra Giá trị cao

của conviction cho thấy luật kết hợp ít khả năng bị vi phạm

 Tầm quan trọng: Conviction giúp bổ sung thông tin cho Support và Confidence, cung

cấp một góc nhìn khác về mối quan hệ giữa các itemset

 Ý nghĩa: Leverage đánh giá mức độ khác biệt giữa xác suất thực tế của sự kết hợp và xác

suất kỳ vọng nếu các item xảy ra độc lập

 Tầm quan trọng: Leverage giúp xác định mức độ mạnh mẽ của luật kết hợp bằng cách so

sánh với tình huống ngẫu nhiên

Ví Dụ Minh Họa

Ví dụ : Phân Tích Giỏ Hàng

Leverage ( A=¿B )=0.05−(0.2 x 0.05)=(0.05−0.01)=0.04

3.3 Các Cách Lưu Trữ Cơ Sở Dữ Liệu Giao Dịch

Cơ sở dữ liệu giao dịch là nền tảng cho việc phân tích luật kết hợp Việc lưu trữ dữ liệu một cáchhiệu quả không chỉ giúp tối ưu hóa quá trình khai thác dữ liệu mà còn cải thiện hiệu suất của cácthuật toán Dưới đây là các cách lưu trữ cơ sở dữ liệu giao dịch phổ biến:

3.3.1 Cơ Sở Dữ Liệu Quan Hệ (Relational Databases)

Cấu Trúc và Đặc Điểm

Cơ sở dữ liệu quan hệ (RDBMS) lưu trữ dữ liệu dưới dạng bảng (tables) với các hàng (rows) vàcột (columns) Mỗi bảng đại diện cho một thực thể (entity) và các mối quan hệ giữa các bảng đượcxác định thông qua các khóa (keys)

 Bảng Giao Dịch (Transaction Table): Mỗi hàng đại diện cho một giao dịch, bao gồm các

trường như TransactionID, Date, CustomerID, v.v

 Bảng Mục (Item Table): Mỗi hàng đại diện cho một mục (item) với các trường như

ItemID, ItemName, Category, v.v

 Bảng Giao Dịch-Mục (Transaction-Item Table): Một bảng phụ để thể hiện mối quan hệ

nhiều-nhiều giữa các giao dịch và mục, với các trường như TransactionID và ItemID

Ưu Điểm và Hạn Chế

Ưu điểm:

 Cấu trúc rõ ràng: Dữ liệu được tổ chức theo cách có cấu trúc, dễ dàng truy vấn và quản

lý

 Hỗ trợ truy vấn mạnh mẽ: Sử dụng ngôn ngữ SQL cho các truy vấn phức tạp.

 Tính toàn vẹn dữ liệu: Hỗ trợ các ràng buộc để đảm bảo tính nhất quán của dữ liệu Hạn chế:

 Khả năng mở rộng hạn chế: RDBMS có thể gặp khó khăn khi xử lý các tập dữ liệu rất

lớn

 Hiệu suất thấp với các truy vấn liên kết nhiều bảng: Các truy vấn phức tạp có thể làm

giảm hiệu suất

 Không tối ưu cho khai thác dữ liệu: Thiết kế tối ưu cho các thao tác CRUD (Create,

Read, Update, Delete) hơn là khai thác dữ liệu

Ví dụ 3: Hệ Thống Tài Chính

Một ngân hàng sử dụng RDBMS để lưu trữ thông tin về các giao dịch tài chính, tài khoản kháchhàng và các sản phẩm dịch vụ Các bảng như Accounts, Transactions, Customers và Products hỗtrợ việc quản lý và phân tích dữ liệu tài chính

3.3.2 Cơ Sở Dữ Liệu Phi Quan Hệ (NoSQL Databases)

Các Loại NoSQL Phổ Biến

Cơ sở dữ liệu NoSQL được thiết kế để xử lý dữ liệu phi cấu trúc hoặc bán cấu trúc, cung cấp khảnăng mở rộng linh hoạt và hiệu suất cao Có bốn loại NoSQL chính:

1 Document Stores: Lưu trữ dữ liệu dưới dạng tài liệu (document) như JSON hoặc XML.

 Thiếu tính nhất quán mạnh: Một số NoSQL databases có thể không hỗ trợ ACID

(Atomicity, Consistency, Isolation, Durability) mạnh mẽ như RDBMS

 Hạn chế trong việc thực hiện các truy vấn phức tạp: Một số NoSQL databases không

hỗ trợ ngôn ngữ truy vấn mạnh mẽ như SQL

 Đòi hỏi kiến thức chuyên sâu: Cần hiểu rõ về cấu trúc và cách hoạt động của từng loại

NoSQL để sử dụng hiệu quả

Ví Dụ Ứng Dụng

Ví dụ 1: Phân Tích Dữ Liệu Lớn (Big Data)

Sử dụng MongoDB để lưu trữ và phân tích dữ liệu giao dịch từ các ứng dụng thương mại điện tửlớn Khả năng lưu trữ tài liệu JSON linh hoạt giúp dễ dàng quản lý các loại dữ liệu đa dạng và thayđổi liên tục

Ví dụ 2: Hệ Thống Đề Xuất (Recommendation Systems)

Sử dụng Redis để lưu trữ các cặp khóa-giá trị nhanh chóng trong hệ thống đề xuất sản phẩm, giúpcải thiện hiệu suất và khả năng phản hồi của hệ thống

Mô Tả: Data Warehousing là quá trình thu thập, lưu trữ và quản lý dữ liệu từ nhiều nguồn khác

nhau vào một kho dữ liệu (data warehouse) duy nhất Data warehouse được thiết kế để hỗ trợ cáchoạt động phân tích và báo cáo, tối ưu hóa cho các truy vấn đọc và phân tích lớn

Ưu Điểm:

 Khả năng tích hợp dữ liệu từ nhiều nguồn: Cho phép kết hợp dữ liệu từ các hệ thống

khác nhau

 Hỗ trợ lịch sử dữ liệu: Lưu trữ dữ liệu theo thời gian, giúp phân tích xu hướng và thay đổi Hạn Chế:

 Chi phí cao: Xây dựng và duy trì data warehouse đòi hỏi nguồn lực lớn.

 Thời gian cập nhật dữ liệu: Có thể không phù hợp với các ứng dụng yêu cầu dữ liệu thời

gian thực

 Phức tạp trong quản lý: Yêu cầu kiến thức chuyên sâu để quản lý và duy trì.

Ví Dụ Ứng Dụng: Doanh nghiệp bán lẻ sử dụng data warehouse để tổng hợp dữ liệu từ các cửa

hàng khác nhau, hệ thống quản lý khách hàng và hệ thống quản lý sản phẩm, từ đó phân tích xuhướng bán hàng và hành vi khách hàng

Data Mining Storage Structures

Mô Tả: Các cấu trúc lưu trữ tối ưu hóa cho quá trình khai thác dữ liệu (data mining), giúp tăng

hiệu suất và giảm thời gian xử lý Một số cấu trúc phổ biến bao gồm:

 Tree (Frequent Pattern Tree): Cấu trúc cây được sử dụng trong thuật toán

FP-Growth để lưu trữ các mẫu phổ biến

 Bitmaps: Sử dụng bitmaps để mã hóa sự xuất hiện của các item trong các giao dịch, giúp

tăng tốc độ truy vấn

 Tries và Hash Tables: Sử dụng để lưu trữ và truy xuất nhanh các itemset và các luật kết

hợp

Ưu Điểm:

 Tăng hiệu suất khai thác dữ liệu: Giảm thời gian xử lý và tăng tốc độ truy vấn.

 Tiết kiệm không gian lưu trữ: Tối ưu hóa sử dụng không gian lưu trữ thông qua các kỹ

thuật nén và mã hóa

 Hỗ trợ các thuật toán khai thác dữ liệu hiệu quả: Các cấu trúc này thường được thiết kế

để làm việc tốt với các thuật toán khai thác dữ liệu cụ thể

Hạn Chế:

 Phức tạp trong thiết kế: Cần thiết kế và triển khai các cấu trúc phức tạp.

 Khó mở rộng: Một số cấu trúc có thể không mở rộng tốt với các tập dữ liệu cực lớn.

 Yêu cầu kiến thức chuyên sâu: Cần hiểu rõ về cấu trúc dữ liệu và thuật toán để sử dụng

hiệu quả

Ví Dụ Ứng Dụng: Sử dụng FP-Tree trong thuật toán FP-Growth để phát hiện các mẫu phổ biến

trong tập dữ liệu bán lẻ lớn, giúp tối ưu hóa quá trình tìm kiếm luật kết hợp

3.4 Thuật Toán Apriori

Thuật toán Apriori là một trong những thuật toán phổ biến nhất trong khai thác luật kết hợp Nóđược thiết kế để tìm các itemset phổ biến và từ đó phát hiện các luật kết hợp mạnh mẽ Dưới đây làchi tiết về nguyên lý hoạt động, các bước thực hiện, phân tích phức tạp và các cải tiến của thuậttoán Apriori, kèm theo các ví dụ minh họa

3.4.1 Nguyên Tắc Hoạt Động của Apriori

Ý Tưởng Cơ Bản

Apriori dựa trên nguyên tắc "áp-priori", nghĩa là bất kỳ tập con nào của một itemset phổ biến cũngphải là phổ biến Nguyên tắc này giúp giảm số lượng các tập hợp cần kiểm tra bằng cách loại bỏcác itemset không thể phổ biến từ trước

Quy Tắc Apriori

1 Khởi Tạo: Bắt đầu với việc xác định các item đơn (1-itemsets) phổ biến, tức là các item có

support >= support tối thiểu

2 Tạo Các Tập Hợp Mục Kế Tiếp: Sử dụng các itemset phổ biến ở cấp độ trước để tạo ra

các itemset ở cấp độ tiếp theo

3 Lọc Các Tập Hợp Dựa Trên Support: Đếm support của các itemset mới và lọc bỏ những

itemset không đạt yêu cầu support tối thiểu

4 Lặp Lại: Lặp lại quá trình tạo và lọc các itemset cho đến khi không còn itemset nào có thể

được tạo ra

5 Phát Hiện Các Luật Kết Hợp: Sử dụng các itemset phổ biến để tạo ra các luật kết hợp và

tính toán các chỉ số như confidence và lift

Đặc Điểm Nổi Bật

 Khả năng giảm số lượng các tập hợp cần kiểm tra: Bằng cách sử dụng nguyên tắc

Apriori, thuật toán giảm thiểu số lượng các tập hợp cần được kiểm tra

 Hiệu quả với các tập dữ liệu vừa và nhỏ: Apriori hiệu quả khi xử lý các tập dữ liệu không

quá lớn, nơi mà số lượng các itemset phổ biến không quá nhiều

 Đơn giản và dễ hiểu: Thuật toán có cấu trúc rõ ràng và dễ dàng triển khai.

3.4.2 Các Bước Thực Hiện Thuật Toán Apriori

Thuật toán Apriori thực hiện qua các bước chính sau:

Bước 1: Tạo Các Tập Hợp Mục (Itemsets)

 Khởi tạo: Xác định các item đơn (1-itemsets) và tính support của chúng.

 Lọc: Giữ lại những itemset có support >= support tối thiểu.

Bước 2: Tạo Các Tập Hợp Tại Cấp Độ Tiếp Theo

 Génération: Tạo các itemset ở cấp độ k+1k+1k+1 từ các itemset ở cấp độ kkk bằng cách

kết hợp các itemset có cùng k−1k-1k−1 item đầu

 Kiểm tra: Đảm bảo rằng tất cả các tập con của itemset mới đều là phổ biến (tồn tại trong

cấp độ kkk)

Bước 3: Đếm Support và Lọc Các Tập Hợp

 Đếm Support: Đếm số giao dịch chứa itemset mới.

 Lọc: Giữ lại những itemset có support >= support tối thiểu.

Bước 4: Lặp Lại Quá Trình

 Tiếp tục tạo và lọc các itemset cho đến khi không còn itemset nào có thể được tạo ra tại cấp

độ tiếp theo

Bước 5: Phát Hiện Các Luật Kết Hợp

 Từ các itemset phổ biến, tạo ra các luật kết hợp và tính toán các chỉ số như confidence vàlift để đánh giá luật

3.4.3 Phân Tích Phức Tạp và Tối Ưu

Vấn Đề Về Tính Toán

 Độ phức tạp thời gian: Thuật toán Apriori có độ phức tạp thời gian cao, đặc biệt là với các

tập dữ liệu lớn và số lượng itemset phổ biến cao

 Số lượng ứng viên lớn: Với mỗi cấp độ, số lượng các itemset ứng viên có thể tăng theo

cấp số nhân, gây tăng đáng kể thời gian tính toán

 Số lần quét cơ sở dữ liệu: Apriori yêu cầu nhiều lần quét cơ sở dữ liệu, điều này làm tăng

thời gian xử lý

Các Cải Tiến và Biến Thể của Apriori

FP-Growth (Frequent Pattern Growth):

o Mô tả: FP-Growth sử dụng cấu trúc FP-Tree để lưu trữ thông tin về các itemset phổ

biến mà không cần phải tạo các itemset ứng viên

o Ưu điểm: Giảm số lần quét cơ sở dữ liệu và tăng hiệu suất so với Apriori.