Dự đoán hành vi của khách hàng dựa vào tập phổ biến

Khám phá cách dự đoán hành vi khách hàng thông qua tập phổ biến, giúp tối ưu hóa chiến lược marketing và nâng cao trải nghiệm người dùng.

• Tác giả: Nguyễn Văn Vương
• Người hướng dẫn: TS. Phạm Thị Thiết
• Trường học: Trường Đại Học Công Nghiệp TP.HCM
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Dự Đoán Hành Vi Khách Hàng Qua Phân Tích Tập Phổ Biến
• Loại tài liệu: Khóa Luận Tốt Nghiệp
• Năm xuất bản: 2021
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• NHẬN XÉT VÀ ĐÁNH GIÁ CỦA GIÁO VIÊN HƯỚNG DẪN
• ĐÁNH GIÁ VÀ NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN 1
• ĐÁNH GIÁ VÀ NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN 2
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Giới thiệu về khai thác dữ liệu
• 1.2. Mục tiêu nghiên cứu
• 1.3. Nội dung nghiên cứu
• 1.4. Đối tượng nghiên cứu
• 1.5. Phương pháp nghiên cứu
• 1.6. Cấu trúc luận văn
• 2. CHƯƠNG 2: TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU
• 2.1. Giới thiệu sơ lược về khai thác dữ liệu
• 2.2. Khai thác luật kết hợp
• 2.3. Khai thác tập phổ biến
• 2.4. Các khái niệm cơ sở
• 3. CHƯƠNG 3: THUẬT TOÁN NEGFIN ĐỂ KHAI THÁC CÁC TẬP PHỔ BIẾN
• 3.1. Cấu trúc dữ liệu
• 3.2. Cấu trúc BMC-tree
• 3.3. Cấu trúc Node-set
• 3.4. Cấu trúc cây liệt kê
• 3.5. Thuật toán negFIN
• 4. CHƯƠNG 4: XÂY DỰNG ỨNG DỤNG VÀ KẾT QUẢ THỰC NGHIỆM
• 4.1. Môi trường xây dựng ứng dụng
• 4.2. Cơ sở dữ liệu thực nghiệm
• 4.2.1. Tiền xử lý dữ liệu
• 4.2.2. Định dạng dữ liệu
• 4.3. Giao diện chương trình
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 5.1. Kết luận
• 5.2. Hướng phát triển
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH
• DANH MỤC CÁC KÝ HIỆU VIẾT TẮT
• MỞ ĐẦU

Tóm tắt

I. Tổng quan về dự đoán hành vi khách hàng qua phân tích tập phổ biến

Dự đoán hành vi khách hàng là một lĩnh vực quan trọng trong marketing và kinh doanh. Việc hiểu rõ hành vi tiêu dùng của khách hàng giúp doanh nghiệp tối ưu hóa chiến lược tiếp thị và nâng cao trải nghiệm khách hàng. Phân tích tập phổ biến là một trong những phương pháp hiệu quả để thực hiện điều này. Bài viết này sẽ khám phá cách mà phân tích tập phổ biến có thể giúp dự đoán hành vi khách hàng.

1.1. Khái niệm về phân tích tập phổ biến trong dự đoán hành vi

Phân tích tập phổ biến là quá trình tìm kiếm các mẫu thường xuyên xuất hiện trong dữ liệu giao dịch. Điều này giúp xác định các mối quan hệ giữa các sản phẩm và hành vi tiêu dùng của khách hàng. Các thuật toán như Apriori và FP-Growth thường được sử dụng để khai thác các tập phổ biến này.

1.2. Tại sao dự đoán hành vi khách hàng lại quan trọng

Dự đoán hành vi khách hàng giúp doanh nghiệp hiểu rõ hơn về nhu cầu và mong muốn của khách hàng. Điều này không chỉ giúp tối ưu hóa chiến lược tiếp thị mà còn tăng cường sự hài lòng của khách hàng, từ đó nâng cao doanh thu và lợi nhuận.

II. Thách thức trong việc dự đoán hành vi khách hàng qua phân tích tập phổ biến

Mặc dù phân tích tập phổ biến mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Việc xử lý dữ liệu lớn và phức tạp là một trong những vấn đề chính. Ngoài ra, việc xác định các tham số như độ hỗ trợ và độ tin cậy cũng rất quan trọng để đảm bảo tính chính xác của các dự đoán.

2.1. Vấn đề về dữ liệu lớn trong phân tích

Dữ liệu lớn có thể gây khó khăn trong việc xử lý và phân tích. Các thuật toán cần phải được tối ưu hóa để có thể xử lý hiệu quả các tập dữ liệu lớn mà không làm giảm hiệu suất.

2.2. Độ chính xác của các dự đoán

Độ chính xác của các dự đoán phụ thuộc vào chất lượng dữ liệu và các tham số được sử dụng trong phân tích. Việc lựa chọn ngưỡng hỗ trợ và độ tin cậy phù hợp là rất quan trọng để đảm bảo rằng các mẫu được phát hiện là có ý nghĩa.

III. Phương pháp phân tích tập phổ biến hiệu quả trong dự đoán hành vi

Để dự đoán hành vi khách hàng một cách hiệu quả, cần áp dụng các phương pháp phân tích tập phổ biến tiên tiến. Các thuật toán như NegFin đã được chứng minh là có hiệu quả trong việc khai thác các tập phổ biến từ dữ liệu giao dịch.

3.1. Thuật toán NegFin và ứng dụng của nó

Thuật toán NegFin là một phương pháp mới trong khai thác tập phổ biến, cho phép tiết kiệm bộ nhớ và tăng tốc độ xử lý. Nó sử dụng cấu trúc dữ liệu NegNodeset để tối ưu hóa quá trình khai thác.

3.2. So sánh giữa các thuật toán khai thác tập phổ biến

Các thuật toán như Apriori và FP-Growth có những ưu điểm và nhược điểm riêng. Việc so sánh hiệu suất của chúng với NegFin sẽ giúp xác định phương pháp tối ưu cho từng loại dữ liệu.

IV. Ứng dụng thực tiễn của phân tích tập phổ biến trong dự đoán hành vi khách hàng

Phân tích tập phổ biến đã được áp dụng rộng rãi trong nhiều lĩnh vực, từ bán lẻ đến tài chính. Các doanh nghiệp sử dụng các kỹ thuật này để tối ưu hóa chiến lược tiếp thị và cải thiện trải nghiệm khách hàng.

4.1. Ví dụ về ứng dụng trong ngành bán lẻ

Nhiều chuỗi siêu thị đã áp dụng phân tích tập phổ biến để xác định các sản phẩm thường xuyên được mua cùng nhau. Điều này giúp họ tối ưu hóa việc sắp xếp hàng hóa và tăng doanh thu.

4.2. Ứng dụng trong lĩnh vực tài chính

Trong lĩnh vực tài chính, phân tích tập phổ biến giúp phát hiện các mẫu giao dịch bất thường, từ đó hỗ trợ trong việc ngăn chặn gian lận và quản lý rủi ro.

V. Kết luận và tương lai của dự đoán hành vi khách hàng qua phân tích tập phổ biến

Dự đoán hành vi khách hàng qua phân tích tập phổ biến là một lĩnh vực đang phát triển mạnh mẽ. Với sự tiến bộ của công nghệ và các thuật toán mới, khả năng dự đoán sẽ ngày càng chính xác hơn, mở ra nhiều cơ hội cho doanh nghiệp.

5.1. Xu hướng phát triển trong tương lai

Các công nghệ mới như machine learning và trí tuệ nhân tạo sẽ tiếp tục cải thiện khả năng phân tích và dự đoán hành vi khách hàng, giúp doanh nghiệp đưa ra quyết định chính xác hơn.

5.2. Tầm quan trọng của việc cập nhật công nghệ

Doanh nghiệp cần liên tục cập nhật và áp dụng các công nghệ mới để duy trì lợi thế cạnh tranh và đáp ứng nhu cầu ngày càng cao của khách hàng.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh khoa học và công nghệ phát triển mạnh mẽ, khả năng thu thập và lưu trữ thông tin của các hệ thống tăng trưởng với tốc độ nhanh chóng. Sự tích lũy khối lượng dữ liệu khổng lồ từ nhiều nguồn dẫn đến thách thức lớn trong việc phân loại, trích xuất và chuyển hóa dữ liệu thô thành tri thức hữu ích phục vụ quản trị và kinh doanh. Khai phá dữ liệu (Data Mining) ra đời nhằm giải quyết bài toán này thông qua các kỹ thuật tự động phân tích dữ liệu tiềm ẩn, hỗ trợ doanh nghiệp đưa ra các quyết định chiến lược như tối ưu hóa bố trí quầy hàng, nâng cao doanh số và tư vấn bán hàng.

Trong các hướng tiếp cận của khai phá dữ liệu, khai thác luật kết hợp (Association Rule Mining) là kỹ thuật trọng tâm, trong đó giai đoạn khai thác tập phổ biến (Frequent Itemset Mining) chiếm phần lớn thời gian và quyết định hiệu năng xử lý. Các thuật toán kinh điển như Apriori (Agrawal & Srikant, 1994) và FP-Growth (Han và cộng sự, 2000) bộc lộ hạn chế lớn khi làm việc với các cơ sở dữ liệu quy mô lớn: Apriori phải duyệt dữ liệu nhiều lần và làm bùng nổ số lượng tập ứng viên, trong khi FP-Growth gặp khó khăn khi duy trì cấu trúc cây FP-Tree trong bộ nhớ chính. Các cấu trúc dữ liệu cải tiến sau này như Node-list (Deng & Wang, 2010) và N-list (Deng, Wang, & Jiang, 2012) tuy nâng cao hiệu suất nhưng đòi hỏi phải mã hóa đồng thời cả pre-order và post-order cho mỗi nút trên cây PPC-Tree, gây lãng phí bộ nhớ. Cấu trúc NegNodeset (Nader, Behrouz & Mohammad, 2018) ra đời nhằm khắc phục nhược điểm này bằng cách sử dụng biểu diễn bitmap, chỉ cần một loại mã thứ tự duy nhất và giúp tiết kiệm một nửa dung lượng bộ nhớ.

Khóa luận tốt nghiệp của sinh viên Nguyễn Văn Vương và Nguyễn Hoàng Thiên Chí, dưới sự hướng dẫn của TS. Phạm Thị Thiết tại Trường Đại học Công nghiệp TP.HCM (6/2021), được thực hiện nhằm nghiên cứu cấu trúc NegNodeset và cài đặt thuật toán NegFIN để dự đoán hành vi mua hàng của người tiêu dùng.

Mục tiêu nghiên cứu của đề tài là tìm hiểu và ứng dụng thuật toán khai thác tập phổ biến NegFIN trên cơ sở dữ liệu "AdventureWork" để dự đoán các hành vi mua hàng có tính quy luật trong một khoảng thời gian nhất định.

Nhiệm vụ nghiên cứu được văn bản xác định gồm 4 nội dung cụ thể:

1. Nghiên cứu, tìm hiểu các thuật toán khai thác các tập phổ biến từ cơ sở dữ liệu.
2. Nghiên cứu, tìm hiểu chi tiết thuật toán NegFin trong khai thác các tập phổ biến.
3. Thu thập và xử lý cơ sở dữ liệu liên quan đến thói quen mua hàng của người dùng, cụ thể là cơ sở dữ liệu AdventureWork.
4. Xây dựng chương trình để dự đoán hành vi mua hàng của người dùng dựa trên thuật giải NegFin với cơ sở dữ liệu AdventureWork.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Cơ sở dữ liệu giao dịch "AdventureWork" và các đặc tính phục vụ khai phá; các tập phổ biến và luật kết hợp; thuật toán NegFIN và các cấu trúc dữ liệu liên quan (BMC-tree, Node-set, NegNodeset, cây liệt kê); chương trình ứng dụng dự đoán hành vi.
• Phạm vi nghiên cứu: Giới hạn trên bộ dữ liệu giao dịch bán hàng "AdventureWork" (tập trung vào các bảng Sales và Production) trong một không gian và khoảng thời gian xác định theo dữ liệu thực nghiệm.

---

Cơ sở lý thuyết và phương pháp

Khóa luận dựa trên nền tảng lý thuyết khai phá dữ liệu và khai thác luật kết hợp từ cơ sở dữ liệu giao dịch $D = {T_1, T_2, \dots, T_m}$ với tập các hạng mục $I = {i_1, i_2, \dots, i_n}$. Một tập con $X \subseteq I$ gồm $k$ phần tử được gọi là $k$-itemset.

Các khái niệm và công thức toán học cốt lõi được tác giả sử dụng bao gồm:

• Độ hỗ trợ (Support): Độ hỗ trợ của tập mục $X$, ký hiệu là $support(X)$, là số lượng giao dịch trong $D$ có chứa $X$.
• Tập phổ biến: Tập mục $X$ được coi là phổ biến nếu $support(X) \ge minsup$, trong đó $minsup$ là ngưỡng hỗ trợ tối thiểu.
• Luật kết hợp: Biểu thức dạng $X \to Y$ (với $X, Y \subset I$ và $X \cap Y = \emptyset$), có độ hỗ trợ được tính bằng: $$Support(X \cup Y) = \frac{|{T_i \in D \mid (X \cup Y) \subseteq T_i}|}{|D|}$$
• Độ tin cậy (Confidence): Tỉ số giữa số giao dịch chứa cả $X \cup Y$ và số giao dịch chứa $X$: $$Confidence(X \to Y) = \frac{Support(X \cup Y)}{Support(X)}$$ Luật $X \to Y$ là luật mạnh nếu $Confidence(X \to Y) \ge minconf$ (ngưỡng tin cậy tối thiểu).
• Tính chất đóng và cắt tỉa: Mọi tập con của một tập phổ biến đều là tập phổ biến; ngược lại, mọi tập cha của một tập không phổ biến đều là tập không phổ biến.

Phương pháp nghiên cứu kết hợp giữa lý thuyết và thực nghiệm:

• Phương pháp lý thuyết: Phân tích, tổng hợp tài liệu chuyên ngành về các thuật toán Apriori, FP-Growth, POC-Tree, Node-list, N-list; khảo sát mô hình biểu diễn bitmap (Song & Yang, 2008) và giải thuật NegFIN (Nader, Behrouz & Mohammad, 2018).
• Phương pháp thực nghiệm: Thực hiện tiền xử lý, trích xuất và chuẩn hóa dữ liệu từ CSDL AdventureWorks; cài đặt thuật toán NegFIN; thiết kế giao diện chương trình để kiểm thử việc sinh luật kết hợp và đưa ra dự đoán mua hàng.

Nguồn dữ liệu sử dụng là cơ sở dữ liệu quan hệ mẫu AdventureWorks của Microsoft, tập trung vào trích xuất dữ liệu từ hai bảng chính: Bảng dữ liệu Sales và Bảng dữ liệu Production.

---

Nội dung chính theo từng chương

CHƯƠNG 1: TỔNG QUAN

Chương mở đầu trình bày tổng quan về sự phát triển của công nghệ thông tin, sự gia tăng nhanh chóng của dữ liệu lưu trữ và nhu cầu ứng dụng khai phá dữ liệu trong các doanh nghiệp bán lẻ. Tác giả xác định rõ lý do chọn đề tài "Dự đoán hành vi của khách hàng dựa vào tập phổ biến", nêu mục tiêu nghiên cứu, liệt kê 4 nội dung nghiên cứu chính, đối tượng, phương pháp tiếp cận và cấu trúc tổng thể gồm 5 chương của khóa luận.

CHƯƠNG 2: TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU

Chương 2 hệ thống hóa cơ sở lý thuyết về bài toán khai thác luật kết hợp và tập phổ biến, phân tách quá trình này thành 2 giai đoạn: (1) Tìm các tập mục phổ biến thỏa mãn $minsup$, và (2) Sinh luật kết hợp mạnh thỏa mãn $minconf$. Tác giả phân tích chi tiết hai thuật toán kinh điển:

Tiêu chí	Thuật toán Apriori (Agrawal, 1993)	Thuật toán FP-Growth (Han et al., 2000)
Cơ chế hoạt động	Sinh tập ứng viên $C_k$ từ $L_{k-1}$ bằng hàm apriori-gen, quét CSDL đếm độ hỗ trợ	Nén dữ liệu vào cây FP-Tree, khai thác đệ quy trên các cây FP-Tree điều kiện
Số lần quét CSDL	Quét lại toàn bộ cơ sở dữ liệu tại mỗi bước lặp $k$	Quét CSDL đúng 2 lần để dựng bảng header và cây
Ưu điểm	Đơn giản, sử dụng tính chất cắt tỉa tập con	Không phát sinh tập ứng viên, tốc độ xử lý nhanh hơn
Hạn chế	Chi phí duyệt dữ liệu lớn, bùng nổ tập ứng viên khi dữ liệu lớn	Khó duy trì và cập nhật FP-Tree trong bộ nhớ khi CSDL quá lớn

Để minh họa các khái niệm, tác giả đưa ra một cơ sở dữ liệu giao dịch mẫu gồm 5 giao dịch ($D$) với tập hạng mục $I = {a, b, c, d, e, f, g, h, i}$ và ngưỡng $minsup = 2$:

TID	Items
1	e, b, g, d
2	c, e, b, a
3	c, b, a, i
4	a, d, h
5	a, d, c, b, f

Bảng tính độ hỗ trợ của các 1-itemset tương ứng:

• Item a: support = 4
• Item b: support = 4
• Item c: support = 3
• Item d: support = 3
• Item e: support = 2
• Các item f, g, h, i: support = 1 (bị loại do $< minsup$).

CHƯƠNG 3: THUẬT TOÁN NEGFIN ĐỂ KHAI THÁC CÁC TẬP PHỔ BIẾN

Chương này đi sâu vào chi tiết kỹ thuật của thuật toán NegFIN và các cấu trúc dữ liệu nền tảng:

• Ma trận bit (Bitmap matrix): Chuyển đổi dữ liệu giao dịch thành ma trận nhị phân với hàng là giao dịch và cột là item. Với CSDL mẫu 5 giao dịch, ma trận bit biểu diễn sự xuất hiện (1) hoặc không xuất hiện (0) của các phần tử.
• Cấu trúc BMC-tree (BitMap Coding tree): Cây tiền tố có nút gốc là null, mỗi nút con chứa 4 trường: item-name, count, bitmap-code, và children-list. Khác với POC-tree dùng mã pre-order và post-order, BMC-tree mã hóa đường dẫn nút bằng chuỗi bit thông qua phép toán logic OR: $N.bitmap_code = current_root.bitmap_code \vee 2^{index(i)}$.
• Cấu trúc Node-set và NegNodeset:
  • $L_1$ là danh sách các 1-itemset phổ biến được sắp xếp theo thứ tự độ hỗ trợ tăng dần (hoặc không giảm).
  • $N\text{-info}$ của mỗi nút được định nghĩa là cặp (bitmap-code, count).
  • Nodeset của một itemset $P_k$ là tập hợp tất cả các $N\text{-info}$ trên cây BMC có bit tại vị trí $index(i_1)$ bằng 1.
  • NegNodeset của $P_k = i_k P_{k-1}$ tương đương với $Nodeset(P'k = \neg i_k P{k-1})$, lưu trữ các nút mà $i_k$ không phải là tổ tiên.
  • Nhờ sử dụng các phép toán bitwise (AND, OR), NegNodeset giúp giảm 50% dung lượng bộ nhớ so với Node-list và N-list.
• Cấu trúc Cây liệt kê (Set-enumeration tree): Cây quản lý không gian tìm kiếm các tập phổ biến, được duyệt để kết hợp các phần tử theo thứ tự $\succ$ và áp dụng cơ chế cắt tỉa dựa trên tính chất tập tương đương ($equivalent_items$).
• Thuật toán NegFIN và thủ tục Constructing_Frequent_Itemset_tree: Trình bày mã giả chi tiết xây dựng cây BMC, khởi tạo $L_1$, gom nhóm $N\text{-info}$, tạo các nút con của cây liệt kê và đệ quy trích xuất các tập phổ biến $k$-itemset thông qua tính toán độ hỗ trợ trên NegNodeset.

CHƯƠNG 4: XÂY DỰNG ỨNG DỤNG VÀ KẾT QUẢ THỰC NGHIỆM

Chương 4 mô tả quá trình triển khai ứng dụng thực nghiệm:

• Môi trường thực nghiệm: Xây dựng trên nền tảng ngôn ngữ lập trình phục vụ xử lý thuật toán và giao diện người dùng.
• Xử lý dữ liệu: Thu thập dữ liệu từ CSDL AdventureWorks. Tác giả thực hiện tiền xử lý dữ liệu thông qua truy vấn kết hợp Bảng dữ liệu Sales và Bảng dữ liệu Production, gom nhóm các sản phẩm được mua trong cùng một mã hóa đơn/giao dịch thành chuỗi sản phẩm (Bảng dữ liệu chuỗi sản phẩm), sau đó chuẩn hóa thành dạng dữ liệu đầu vào phù hợp cho thuật toán (Bảng dữ liệu đã được định dạng).
• Giao diện chương trình:
  • Giao diện chính hiển thị thông tin nạp dữ liệu và các chức năng phân tích.
  • Giao diện kết quả cho phép người dùng nhập các tham số $Minsup$, $Minconfidence$ và chọn một sản phẩm mục tiêu cần dự đoán. Hệ thống thực thi thuật toán NegFIN để tìm tập phổ biến, tạo luật kết hợp và xuất ra danh sách các sản phẩm có khả năng cao được khách hàng mua kèm.

CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Tổng kết các nội dung đã hoàn thành của khóa luận, khẳng định việc cài đặt thành công thuật toán NegFIN và ứng dụng vào bài toán dự đoán hành vi mua hàng. Đồng thời, chương này chỉ ra các hướng nghiên cứu mở rộng trong tương lai.

---

Thiết kế và triển khai ứng dụng

Hệ thống ứng dụng được thiết kế nhằm tự động hóa quy trình khai phá dữ liệu từ CSDL quan hệ đến giao diện dự đoán trực quan cho người dùng:

[CSDL AdventureWorks (Sales, Production)]
      [Truy vấn & Tiền xử lý]
  [Chuẩn hóa chuỗi sản phẩm theo TID]
    [Xây dựng BMC-tree & L1]
  [Khai phá NegNodeset (Thuật toán NegFIN)]
       [Sinh Luật kết hợp]
   (Lọc theo Minsup & Minconfidence)
[Giao diện dự đoán sản phẩm mua kèm]

• Quy trình xử lý dữ liệu:
  1. Trích xuất dữ liệu: Thực hiện câu lệnh truy vấn liên kết bảng Sales và Production trong CSDL AdventureWorks để lấy thông tin mã giao dịch và tên/mã sản phẩm.
  2. Biến đổi dữ liệu: Nhóm các sản phẩm theo từng mã giao dịch (TID) để tạo thành chuỗi danh mục hàng hóa, sau đó ánh xạ thành định dạng ma trận bit.
  3. Thực thi giải thuật: Dữ liệu định dạng được đưa vào cây BMC-tree; thuật toán NegFIN tính toán danh sách tập phổ biến dựa trên phép toán bitwise trên NegNodeset.
• Tham số và tương tác trên giao diện:
  • Người dùng thiết lập hai tham số ngưỡng: Độ phổ biến tối thiểu ($Minsup$) và Độ tin cậy tối thiểu ($Minconfidence$).
  • Người dùng lựa chọn một sản phẩm cụ thể từ danh mục. Chương trình sẽ đối sánh với các luật kết hợp đã khai thác được để hiển thị danh sách các sản phẩm dự đoán mà khách hàng có xu hướng mua cùng.

---

Kết quả và đóng góp

Kết quả chính

• Tổng hợp và hệ thống hóa chi tiết cơ sở lý thuyết về bài toán khai thác luật kết hợp, các giải thuật kinh điển (Apriori, FP-Growth) cùng các cấu trúc dữ liệu hiện đại (Node-list, N-list, BMC-tree, NegNodeset).
• Trình bày đầy đủ thuật toán NegFIN và hàm tạo cây tập phổ biến Constructing_Frequent_Itemset_tree, làm rõ các tính chất toán học của phép toán bitwise trên NegNodeset.
• Thực hiện tiền xử lý thành công dữ liệu thực tế từ CSDL AdventureWorks (kết hợp bảng Sales và Production) thành tập giao dịch chuẩn hóa.
• Xây dựng hoàn chỉnh chương trình ứng dụng có giao diện cho phép tùy chỉnh ngưỡng $Minsup$, $Minconfidence$ và hiển thị kết quả dự đoán sản phẩm mua kèm theo từng mặt hàng được chọn.

Đóng góp so với các nghiên cứu trước

• So với thuật toán Apriori: Khắc phục triệt để chi phí quét lại CSDL nhiều lần và không làm bùng nổ số lượng tập ứng viên.
• So với thuật toán FP-Growth: Giảm thiểu độ phức tạp trong việc xây dựng và duy trì các cây điều kiện đệ quy trên bộ nhớ chính.
• So với cấu trúc Node-list (2010) và N-list (2012): Cấu trúc NegNodeset chỉ cần biểu diễn một mã thứ tự (pre-order hoặc post-order) thông qua bitmap-code, giúp tiết kiệm chính xác 50% dung lượng bộ nhớ dành cho việc mã hóa nút trên cây tiền tố.

---

Hạn chế và hướng nghiên cứu tiếp

• Hạn chế: Thử nghiệm của khóa luận chủ yếu tập trung trên bộ dữ liệu mẫu AdventureWorks; quá trình khai thác phụ thuộc vào việc người dùng phải tự thiết lập các ngưỡng tĩnh ($Minsup$, $Minconfidence$); văn bản chưa mở rộng đo lường hiệu năng so sánh thời gian chạy thực tế với nhiều bộ dữ liệu chuẩn quy mô lớn khác nhau.
• Hướng phát triển:
  • Mở rộng thử nghiệm thuật toán NegFIN trên các bộ dữ liệu giao dịch thương mại điện tử thực tế có quy mô lớn và đa dạng hơn.
  • Nghiên cứu tối ưu hóa thuật toán khi áp dụng trên các dòng dữ liệu thay đổi liên tục (data streams).
  • Tích hợp thêm các yếu tố thời gian, không gian hoặc phân khúc khách hàng vào mô hình để nâng cao độ chính xác của dự đoán hành vi.

---

Giá trị tham khảo

Khóa luận là tài liệu tham khảo hữu ích cho sinh viên, học viên chuyên ngành Công nghệ thông tin, Khoa học máy tính, Hệ thống thông tin và Khoa học dữ liệu đang nghiên cứu về khai phá dữ liệu và trí tuệ nhân tạo.

Các phần có giá trị tham khảo cao gồm:

• Toàn bộ cơ chế biểu diễn và tính toán đại số bitwise của cấu trúc BMC-tree, Nodeset và NegNodeset trong Chương 3.
• Mã giả chi tiết của 4 thuật toán: BMC-tree, constructing_set_enumeration_tree, negFIN và constructing_frequent_itemset_tree.
• Quy trình truy vấn, tiền xử lý và chuyển đổi bảng dữ liệu quan hệ (Sales, Production của AdventureWorks) thành dữ liệu giao dịch phục vụ khai phá tập phổ biến.

---

Câu hỏi thường gặp

1. Mục tiêu trọng tâm của đề tài khóa luận là gì?
Mục tiêu của đề tài là tìm hiểu cấu trúc dữ liệu NegNodeset và thuật toán NegFIN, từ đó cài đặt chương trình khai thác tập phổ biến và sinh luật kết hợp trên cơ sở dữ liệu "AdventureWork" để dự đoán hành vi mua hàng của khách hàng.

2. Cấu trúc NegNodeset mang lại ưu điểm gì vượt trội so với Node-list và N-list?
Cả Node-list và N-list đều bắt buộc phải mã hóa mỗi nút trên cây PPC-Tree bằng cả hai mã pre-order và post-order, gây tốn bộ nhớ. NegNodeset sử dụng mô hình mã hóa bitmap-code và chỉ yêu cầu mã pre-order hoặc post-order, giúp tiết kiệm một nửa (50%) dung lượng bộ nhớ.

3. BMC-tree khác với cây POC-tree ở điểm nào?
Về mặt cấu trúc, BMC-tree tương tự POC-tree, nhưng điểm khác biệt then chốt là mỗi nút của POC-tree được mã hóa bằng cặp mã pre-order và post-order, trong khi mỗi nút của BMC-tree được mã hóa trực tiếp bằng BMC(node-path) thông qua phép toán logic OR trên ma trận bit.

4. Dữ liệu thực nghiệm được tác giả thu thập và xử lý từ nguồn nào?
Tác giả sử dụng cơ sở dữ liệu mẫu "AdventureWork", thực hiện truy vấn kết hợp thông tin từ Bảng dữ liệu Sales và Bảng dữ liệu Production, sau đó xử lý gom nhóm theo mã giao dịch để tạo thành chuỗi sản phẩm đã định dạng.

5. Người dùng tương tác với chương trình thực nghiệm như thế nào để nhận kết quả dự đoán?
Trên giao diện chương trình, người dùng nhập vào hai thông số ngưỡng là $Minsup$ (độ hỗ trợ tối thiểu) và $Minconfidence$ (độ tin cậy tối thiểu), đồng thời chọn một sản phẩm mục tiêu. Hệ thống sẽ áp dụng thuật toán NegFIN để trích xuất các luật kết hợp thỏa mãn và đưa ra danh sách các sản phẩm dự đoán được mua cùng.

---

Kết luận

Khóa luận tốt nghiệp "Dự đoán hành vi của khách hàng dựa vào tập phổ biến" của tác giả Nguyễn Văn Vương và Nguyễn Hoàng Thiên Chí đã trình bày toàn diện cơ sở lý thuyết về khai phá luật kết hợp và cấu trúc dữ liệu NegNodeset kết hợp thuật toán NegFIN. Công trình đã chứng minh ưu thế tiết kiệm bộ nhớ của việc mã hóa bitmap-code so với các phương pháp duyệt cây truyền thống. Thông qua việc tiền xử lý dữ liệu AdventureWorks và xây dựng ứng dụng thực nghiệm, đề tài đã hiện thực hóa thành công mô hình dự đoán sản phẩm mua kèm hỗ trợ hoạt động bán lẻ.

Trích đoạn nội dung tài liệu

Chương 1 giới thiệu chung về bối cảnh, nhu cầu thực tế và khai phá dữ liệu. Đồng thời định hướng tiếp cận của luận văn. Chương 2 trình bày cơ sở lý thuyết về khai thác dữ liệu. Trong đó, luận văn giới thiệu chung về khái niệm, sơ lược các thuật toán khai thác tập phổ biến như Apiori, FP-Growth là các thuật toán cơ sở để phát triển các thuật toán sau này.

Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 3 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Chương 3 trình bày chi tiết cấu trúc dữ liệu Node-set,NegNode-set và thuật toán NegFin và áp dụng chúng trong khai thác tập phổ biến. Chương 4 trình bày về môi trường xây dựng chương trình dự đoán cũng như kết quả và đánh giá thực nghiệm của chương trình. Chương 5 trình bày kết luận chung cũng như định hướng phát triển của đề tài. Cuối cùng là chi tiết về các tài liệu tham khảo để hoàn thành luận văn này.

Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 4 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp CHƯƠNG 2: TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU 2.1 Giới thiệu sơ lược về khai thác dữ liệu 2.1 Khai thác luật kết hợp Bài toán khai thác luật kết hợp trong CSDL là một trong những chức năng chính của khai thác dữ liệu, là khai phá các luật kết hợp có độ phổ biến (support) cũng như độ tin cậy (confidence) lớn hơn hoặc bằng một ngưỡng phổ biến tối thiểu (minsup) và ngưỡng tin cậy tối thiểu (minconf). Bài toán khai thác luật kết hợp thường được chia thành 2 giai đoạn: Giai đoạn 1: Tìm tất cả các tập mục phổ biến từ dữ liệu giao dịch thoả minsup; Giai đoạn 2: Sinh các luật kết hợp mạnh từ tập mục phổ biến tìm thấy ở giai đoạn thứ nhất. Thông thường giai đoạn thứ nhất chiếm hầu hết thời gian cho quá trình khai thác luật kết hợp và là giai đoạn quan trọng vì nó là giai đoạn nâng cao hiệu suất trong khai thác luật kết hợp.2 Khai thác tập phổ biến Khai phá tập phổ biến là quá trình tìm kiếm tập các phần tử có số lần xuất hiện lớn hơn một ngưỡng cho trước và vấn đề này được R. Swami đề xuất năm 1993, xuất phát từ nhu cầu bài toán phân tích dữ liệu trong cơ sở dữ liệu giao dịch, nhằm phát hiện các mối quan hệ giữa các tập hàng hóa đã bán tại siêu thị.

Việc xác định này không phân biệt sự khác nhau giữa các hàng hóa, chỉ dựa vào sự xuất hiện của chúng. Phần tiếp theo đây nêu một số khái niệm cơ sở liên quan đến bài toán khai thác luật kết hợp và tập phổ biến.2 Các khái niệm cơ sở Cho D = {T1, T2,…Tm} là cơ sở dữ liệu giao dịch và I = {i1, i2,…,in} là tập các phần tử trong cơ sở dữ liệu D. Mỗi giao dịch Ti  I. Tập X  I có k phần tử được gọi là tập k-phần tử (k-itemset).

Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 5 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Bảng 2.1- CSDL giao dịch TID Items 1 e, b, g, d 2 c, e, b, a 3 c, b, a, i 4 a, d, h 5 a, d, c, b, f Trong bảng 2.1 là một cơ sở dữ liệu giao dịch gồm có 5 giao dịch trong đó I={a, b, c, d, e, f, g, h, i} là các phần tử hay còn gọi là item. Tập 1-itemset gồm {a, b, c, d, e, f, g, h, i}; Tập 2-itemset gồm {ab, ac, ae, af, ag, bc, bd, be, bf, bg, cd, ce, cf, cg, de, df, ef}; Tập 3-itemset gồm {abc, abe,,, ace, agc, bce, bcd, bcf, bde, bdf, bef, cde, cdf, cde, cdf, cef} tương tự ta có tập 4-itemset, 5-itemset,… k-itemset. (Độ hỗ trợ - Support): Độ hỗ trợ (support) của itemset 𝑋  𝐼, ký hiệu support(X), là số các giao dịch trong Ɗ có chứa X. Ví dụ 1: Xét CSDL giao dịch như Bảng 2.

{a} có độ phổ biến là 4, kí hiệu support(a)=4 vì {a} xuất hiện 4 lần trong 5 giao dịch D.Vậy độ hỗ trợ của {a} là 4. Tương tự, ta có độ hỗ trợ của các tập 1-itemset sau: Bảng 2.2-Bảng thể hiện độ hỗ trợ của các phần tử 1-itemset 1-itemset Độ hỗ trợ a 4 b 4 c 3 d 3 e 2 f 1 g 1 h 1 i 1 Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 6 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Khái niệm 2. (Tập phổ biến): Tập phần tử X được gọi là tập phổ biến nếu có support(X) ≥ minsup, với minsup là ngưỡng hỗ trợ tối thiểu cho trước. Ví dụ 2: Xét CSDL như bảng 2.1 có ngưỡng minsup là 2 nếu x có độ hỗ trợ support(x) nhỏ hơn 2, sẽ bị loại.

Ta gọi I là tập 1-itemset, ta được: I = {a, b, c, d, e} là tập phổ biến và các item g, h, i không là tập phổ biến do support(g) = support(h) = support(i) = 1 < minsup Khái niệm 2. (Luật kết hợp) Tập phổ biến thường dùng để sinh luật kết hợp. Luật kết hợp với dạng X → Y, với X, Y là hai tập phần tử, được xác định thông qua hai khái niệm độ hỗ trợ và độ tin cậy của luật được định nghĩa như sau: Khái niệm 2. |{𝑋  𝑌  𝑇𝑖 | 𝑇𝑖 ∈ 𝐷}| 𝑆𝑢𝑝𝑝𝑜𝑟𝑡 (𝑋 ∪ 𝑌) = |𝐷| Ví dụ 3: Độ hỗ trợ của luật X → Y = 40%, có nghĩa là 40% trong tất cả các giao dịch X và Y được mua cùng nhau.(Độ tin cậy của một luật (confidence)) Độ tin cậy của luật X → Y là tỉ số của số giao dịch trong D, kí hiệu là: Confidence(X →Y), chứa X  Y và số giao dịch trong D có chứa tập X.

𝑆𝑢𝑝𝑝𝑜𝑟𝑡(𝑋∪𝑌) 𝐶𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒 (𝑋 →𝑌) = 𝑆𝑢𝑝𝑝𝑜𝑟𝑡(𝑋) Ví dụ 4: Độ tin cậy của luật X → Y = 70%, có nghĩa là 70% khách hàng mua X cũng mua Y. Luật X →Y được gọi là tin cậy nếu có Confidence(X →Y) ≥ minconf, với minconf là ngưỡng tin cậy tối thiểu cho trước. Tập phổ biến có một số tính chất sau: Tính chất 2. (Tính chất đóng của tập phần tử) Giả sử X, Y là hai tập phần tử, X, Y  I.

Nếu Y là tập phổ biến và X  Y thì X cũng là tập phổ biến. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 7 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp Tính chất 2. Cho X, Y là hai tập phần tử, X  Y và X là tập không phổ biến thì Y cũng là tập không phổ biến. Ví dụ 5: Xét CSDL như bảng 2.1 có ngưỡng minsup là 2.

Xép tập mục X = {a,b,c} , support(X) = 3 ≥ minsup. Ta được X={a,b,c} là tập phổ biến theo ngưỡng minsup = 2. Theo tính chất 2.1 thì tất cả tập con của X = {a,b,c} cũng là tập phổ biến: support (a) = 4, support (b) = 4, support (c) = 3, support (ab) = 3, support (ac) = 3, support (bc) = 3 ≥ minsup. Tương tự, với X= {g}, support(X) = 1 < minsup.

Ta được X={g} là tập không phổ biến theo ngưỡng minsup = 2. Theo tính chất 2.2 thì tất cả tập con của X = {g} cũng không là tập phổ biến với support(gh) = 1 < minsup.3 Các thuật toán khai thác tập phổ biến 2. Thuật toán Apriori: Phương pháp sinh ứng viên để tìm tập phổ biến được Agrawal đề xuất từ năm 1993 với thuật toán Apriori. Ý tưởng của thuật toán Apriori dựa trên kết luận: nếu một tập phần tử là tập phổ biến thì tất cả tập con của nó cũng phải phổ biến (tính chất 2.1 – tập phổ biến).

Do vậy không thể có trường hợp một tập phổ biến có tập con là không phổ biến hay nói cách khác tập phổ biến nhiều danh mục hơn chỉ có thể được tạo ra từ các tập phổ biến ít danh mục hơn. Nguyên lý hoạt động cơ bản của thuật toán Apriori như sau: − Bắt đầu từ các tập phổ biến chỉ có một danh mục. - Dùng tập phổ biến kích thước k-itemset để tạo các tập ứng cử k-itemset - Duyệt cơ sở dữ liệu và đối sánh mẫu để đếm số lần xuất hiện của các tập ứngviên trong các giao dịch, nếu số lần xuất hiện của tập ứng viên lớn hơn hoặc bằng minsup thì là tập phổ biến, ngược lại không phải tập phổ biến. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 8 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp − Quá trình lặp lại cho đến khi không còn tập phổ biến nào được tạo ra.

Thuật toán Apriori Input: cơ sở dữ liệu D, minsup Output: L L1 ={tập hợp 1 danh mục}; For (k = 2; Lk-1 ≠ ; k++) do begin 3) Ck = apriori-gen (Lk-1); // Tạo ứng viên mới. 4) For all giao dịch t  D do begin //duyệt CSDL 5) Ct = subset(Ck, t); //các tập danh mục ứng viên có trong giao dịch t 6) For all ứng viên c  Ct do 7) c. count ++; 8) End 9) Lk = {c  Ck | c.count ≥ minsup} End Answer = k Lk; // Trả về tập hợp của các tập phổ biến Hình 2.1-Thuật toán Apriori Diễn giải thuật toán: - Bước đầu tiên của thuật toán đơn giản chỉ tính các danh mục xuất hiện để xác định tập hợp của các tập phổ biến 1-itemset. - Lặp bước k : + Tập hợp Lk-1 được sử dụng để tạo nên tập ứng viên Ck : sử dụng hàm apriori- gen được miêu tả là hàm lấy Lk-1 (tập hợp của các tập phổ biến k-itemset )là đầu vào và trả về Ck là tập hợp của tất cả các tập chứa k-itemset phát sinh từ tập hợp Lk-1 bằng cách hợp các tập 1-itemsettrong tập hợp Lk-1.

Chú ý một ứng viên thuộc Ck thì tất cả các tập con của ứng viên đó phải có mặt trong Lk-1 (theo tính chất 2.2 của tập phổ biến) + Bước kế tiếp, duyệt CSDL để tính độ phổ biến của các ứng viên trong tập hợp Ck. Từ đó, tính được tập hợp Lk. Nguyễn Văn Vương, Nguyễn Hoàng Thiên Chí 9 Dự đoán hành vi của khách hàng dựa vào tập phổ biến Khóa luận tốt nghiệp + Nếu Lk = ∅ thì dừng lại. - Hợp của các Lk chính là các tập phổ biến cần tìm.

Hạn chế của thuật toán Apriori: Để xác định độ phổ biến của các tập ứng viên, thuật toán Apriori phải quét lại toàn bộ giao dịch trong CSDL, do đó sẽ tiêu tốn rất nhiều thời gian khi phải quét CSDL nhiều lần để kiểm tra một lượng lớn các ứng viên, đặc biệt khi số danh mục lớn.