Nghiên Cứu Phát Triển Mô Hình Thuật Toán Khai Phá Tập Phần Tử Có Trọng Số

Khai phá dữ liệu là một quá trình quan trọng trong việc tìm kiếm thông tin hữu ích từ khối lượng lớn dữ liệu. 161 trang · Học viện Kỹ thuật Quân sự · 2018.

• Người hướng dẫn: TS Nguyễn Mạnh Hùng
• Trường học: Học viện Kỹ thuật Quân sự
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề tài: Mô Hình Thuật Toán Khai Phá Tập Phần Tử Có Trọng Số
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2018
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. MỞ ĐẦU: TỔNG QUAN VỀ KHAI PHÁ TẬP PHỔ BIẾN
• 2. THUẬT TOÁN KHAI PHÁ TẬP LỢI ÍCH CAO DỰA TRÊN MÔ HÌNH CWU
• 3. THUẬT TOÁN KHAI PHÁ TẬP LỢI ÍCH CAO TRÊN CÂY DANH SÁCH LỢI ÍCH VÀ CẤU TRÚC RTWU
• KẾT LUẬN VÀ KIẾN NGHỊ
• DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về Khai Phá Dữ Liệu

Khai phá dữ liệu là một quá trình quan trọng trong việc tìm kiếm thông tin hữu ích từ khối lượng lớn dữ liệu. Khai phá dữ liệu không chỉ giúp phát hiện các mẫu và xu hướng mà còn hỗ trợ trong việc ra quyết định. Các phương pháp khai phá dữ liệu như phân lớp, phân cụm và khai phá luật kết hợp đã được áp dụng rộng rãi trong nhiều lĩnh vực như y tế, tài chính và giáo dục. Tuy nhiên, một trong những thách thức lớn nhất là khai phá tập phổ biến, nơi mà các phần tử được coi là có tầm quan trọng như nhau. Điều này dẫn đến việc không phản ánh đúng giá trị thực tế của từng phần tử trong cơ sở dữ liệu. Để khắc phục điều này, mô hình khai phá tập phổ biến có trọng số (WFI) và tập lợi ích cao (HUI) đã được đề xuất, cho phép đánh giá tầm quan trọng của từng phần tử thông qua các trọng số khác nhau.

II. Mô Hình Khai Phá Tập Phần Tử Có Trọng Số

Mô hình khai phá tập phần tử có trọng số cho phép người dùng đánh giá tầm quan trọng của từng phần tử trong cơ sở dữ liệu. Mỗi phần tử có thể có một trọng số khác nhau, phản ánh giá trị thực tế của nó. Mô hình này không chỉ giúp xác định các tập phần tử phổ biến mà còn cho phép người dùng đưa ra quyết định dựa trên lợi ích thực tế. Thuật toán khai thác tập phần tử có trọng số đã được phát triển để tối ưu hóa quá trình tìm kiếm và giảm thiểu số lượng ứng viên không cần thiết. Các nghiên cứu đã chỉ ra rằng việc áp dụng mô hình này có thể cải thiện đáng kể hiệu suất khai thác dữ liệu, đặc biệt trong các lĩnh vực như thương mại điện tử và phân tích hành vi người tiêu dùng.

III. Phân Tích và Đánh Giá Các Thuật Toán Khai Phá

Các thuật toán khai phá tập lợi ích cao dựa trên mô hình CWU đã được phát triển để tối ưu hóa quá trình khai thác. Những thuật toán này không chỉ giúp xác định các tập phần tử có trọng số mà còn cho phép phân tích sâu hơn về lợi ích của từng phần tử. Việc áp dụng các thuật toán như HP, PPB và CTU-PRO+ đã cho thấy hiệu quả cao trong việc giảm thiểu không gian tìm kiếm và tăng tốc độ xử lý. Kết quả thực nghiệm cho thấy rằng các thuật toán này có thể xử lý khối lượng dữ liệu lớn một cách hiệu quả, từ đó mở ra nhiều cơ hội ứng dụng trong thực tế.

IV. Ứng Dụng Thực Tế và Giá Trị Của Nghiên Cứu

Nghiên cứu về mô hình và thuật toán khai phá tập phần tử có trọng số không chỉ có giá trị lý thuyết mà còn mang lại nhiều ứng dụng thực tiễn. Các mô hình này có thể được áp dụng trong nhiều lĩnh vực như phân tích thị trường, quản lý chuỗi cung ứng và tối ưu hóa quy trình sản xuất. Việc khai thác thông tin từ dữ liệu lớn giúp các doanh nghiệp đưa ra quyết định chính xác hơn, từ đó nâng cao hiệu quả hoạt động. Hơn nữa, nghiên cứu này cũng mở ra hướng đi mới cho các nghiên cứu tiếp theo trong lĩnh vực khai phá dữ liệu, đặc biệt là trong việc phát triển các thuật toán mới và cải tiến các mô hình hiện có.

Nội dung chính

Tổng quan luận án

Khai phá dữ liệu là quá trình trích xuất thông tin hữu ích và tri thức tiềm ẩn từ các tập dữ liệu có quy mô lớn, đóng vai trò nền tảng trong việc hỗ trợ ra quyết định tại nhiều lĩnh vực như tài chính, y tế, thương mại, viễn thông và giáo dục. Trong các kỹ thuật khai phá dữ liệu, khai phá luật kết hợp và khai phá tập phổ biến (Frequent Itemsets – FI) là hướng tiếp cận nhận được sự quan tâm rộng rãi. Tuy nhiên, bài toán khai phá tập phổ biến truyền thống tồn tại hai hạn chế căn bản: coi mọi phần tử trong cơ sở dữ liệu đều có vai trò như nhau và chỉ ghi nhận trạng thái xuất hiện nhị phân (có hoặc không có) của phần tử trong từng giao dịch. Mô hình này không phản ánh được giá trị định lượng thực tế như số lượng mua, đơn giá hay mức độ đóng góp lợi nhuận của từng mặt hàng.

Để giải quyết hạn chế trên, hai mô hình mở rộng đã được phát triển gồm: khai phá tập phổ biến có trọng số (Weighted Frequent Itemsets – WFI) và khai phá tập lợi ích cao (High Utility Itemsets – HUI). Khác với tập phổ biến truyền thống vốn thỏa mãn tính chất đóng (tính chất phản đơn điệu Apriori), tập phổ biến có trọng số và tập lợi ích cao không duy trì tính chất này. Để kiểm soát không gian tìm kiếm, các phương pháp khai phá tập lợi ích cao phổ biến thường sử dụng chặn trên dựa trên lợi ích trọng số giao dịch (Transaction Weighted Utility – TWU). Dẫu vậy, ngưỡng TWU thường có độ lệch lớn so với lợi ích thực tế (Actual Utility – AU), khiến số lượng tập ứng viên sinh ra ở các giai đoạn trung gian vẫn rất lớn, gây quá tải về bộ nhớ và thời gian xử lý.

Luận án "Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao" của tác giả Đậu Hải Phong, chuyên ngành Cơ sở Toán học cho Tin học (mã số 62.10...), được thực hiện dưới sự hướng dẫn khoa học của TS. Nguyễn Mạnh Hùng và TS. Đoàn Văn Ban tại Học viện Kỹ thuật Quân sự (năm 2018), tập trung giải quyết các khoảng trống nghiên cứu trên.

Mục tiêu nghiên cứu của luận án được xác định gồm:

1. Nghiên cứu các thuật toán khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao.
2. Xây dựng mô hình, cấu trúc dữ liệu nhằm giảm không gian tìm kiếm và dựa trên cơ sở đó để xây dựng các thuật toán khai phá tập phổ biến có trọng số và tập lợi ích cao.

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

• Các mô hình, cấu trúc dữ liệu phục vụ cắt tỉa tập ứng viên trong khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao.
• Các thuật toán khai phá tập phổ biến có trọng số và tập lợi ích cao (dạng tuần tự và song song).

Phạm vi nghiên cứu:

• Không gian nghiên cứu: Không gian cơ sở dữ liệu giao dịch định lượng và có trọng số.
• Phạm vi nội dung: Đánh giá mô hình lý thuyết, thiết kế cấu trúc dữ liệu nén và thuật toán cắt tỉa không gian tìm kiếm; cài đặt thử nghiệm, so sánh hiệu năng thực thi trên các tập dữ liệu thực tế và tập dữ liệu mô phỏng chuẩn (Mushroom, Foodmart, các tập dữ liệu tổng hợp họ T...I...D...).

Tổng quan tài liệu và vị trí của luận án

Luận án đã tổng quan các hướng tiếp cận chính trong lịch sử phát triển của bài toán khai phá mẫu phổ biến và lợi ích cao:

Hướng nghiên cứu	Tác giả, công trình tiêu biểu	Đặc điểm và hạn chế ghi nhận trong văn bản
Khai phá tập phổ biến truyền thống	- R. Agrawal, R. Srikant (1993, 1994): Apriori, AIS - J. S. Park et al. (1995): DHP - M. J. Zaki (2000): Eclat - J. Han, J. Wang, Y. Yin (2000): FP-growth - P. Shenoy et al. (2002): VIPER - C. Chuan et al. (2003): CT-PRO (cây CFP)	Thuật toán dựa trên kết nối (Apriori) sinh lượng lớn ứng viên; cấu trúc cây FP-tree và CFP-tree nén dữ liệu tốt nhưng FP-growth phải xây dựng cây điều kiện đệ quy gây tốn kém tài nguyên.
Khai phá tập phổ biến có trọng số (WFI)	- Unil Yun, J. J. Leggett (2005): WFIM - Zi-guo Huai, Ming-he Huang (2011): Hash-based - Unil Yun, K. H. Ryu (2008): WAF - P. Kumar, Ananthnarayana (2009): WT song song - Bay Vo, F. Coenen, Bac Le (2013): WIT-tree	WFIM yêu cầu duyệt CSDL 2 lần; WAF chấp nhận sai số xấp xỉ $\varepsilon$; WIT tính toán độ hỗ trợ trọng số giao dịch $tw(T_k)$ qua danh sách tidset nhưng kích thước lưu trữ trung gian còn lớn.
Khai phá theo chiều dọc dựa trên Diffset	- M. J. Zaki (2003): Diffset - M. A. El-Megid et al. (2009): VMUDG	Lưu trữ sự khác biệt tidset giúp giảm dung lượng bộ nhớ, tuy nhiên VMUDG mới chỉ áp dụng cho tập phổ biến thông thường, chưa hỗ trợ trọng số.
Khai phá tập lợi ích cao (HUI)	- R. Chan et al. (2003): Mô hình HUI - Y. Liu et al. (2005): Mô hình TWU - Nguyễn Huy Đức (2010), Nguyễn Duy Hàm (2016) tại Việt Nam	Mô hình TWU là nền tảng cắt tỉa 2 pha nhưng chặn trên TWU quá lỏng, sinh ra nhiều ứng viên giả (false positive).

Khoảng trống luận án lựa chọn giải quyết:

• Ứng dụng cấu trúc diffset vào bài toán khai phá tập phổ biến có trọng số để giảm chi phí bộ nhớ của tiếp cận theo chiều dọc, đồng thời phát triển phiên bản song song.
• Đề xuất mô hình chặn trên mới CWU (Candidate Weighted Utility) có cận chặt hơn TWU, kết hợp bảng chỉ số hình chiếu nhằm thu hẹp không gian ứng viên cho tập lợi ích cao.
• Thiết kế cấu trúc cây nén CUP (Compressed Utility Pattern) và cấu trúc tỉa RTWU (Remaining Transaction Weighted Utilization) cùng danh sách lợi ích mở rộng, loại bỏ nhu cầu sinh ứng viên trung gian và tránh duyệt đệ quy tốn kém.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và các khái niệm cốt lõi

Luận án xây dựng các thuật toán dựa trên hệ thống khái niệm hình thức trong cơ sở dữ liệu giao dịch:

• Cơ sở dữ liệu giao dịch và độ hỗ trợ: Cho $D = {T_1, T_2, \dots, T_m}$ là tập các giao dịch, $I = {i_1, i_2, \dots, i_n}$ là tập phần tử. Độ tin cậy của luật $X \to Y$ được xác định qua công thức: $$\text{Confidence}(X \to Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)}$$

• Độ hỗ trợ có trọng số (WSupp): Mỗi phần tử $i \in I$ gắn với trọng số $w_i$. Trọng số của tập phần tử $X$ là $\text{Weight}(X) = \sum_{i \in X} w_i$. Độ hỗ trợ có trọng số được tính: $$\text{WSupp}(X) = \text{Support}(X) \times \sum_{i \in X} w_i$$ Tập $X$ là phổ biến có trọng số nếu $\text{WSupp}(X) \ge \text{minwsupp}$.

• Cấu trúc Diffset: Với tập giao dịch toàn cục $U$, tidset của phần tử $a$ là $t(a)$, diffset của $a$ là $d(a) = U \setminus t(a)$. Diffset của tập $ab$ là $d(ab) = d(b) \setminus d(a)$. Độ hỗ trợ của $ab$ được tính theo biểu thức: $$\sigma(ab) = \sigma(a) - |d(ab)|$$

• Độ đo lợi ích:

  • Lợi ích trong (Internal Utility): $O(i_k, T_j)$ biểu thị số lượng của phần tử $i_k$ trong giao dịch $T_j$.
  • Lợi ích ngoài (External Utility): $S({i_k})$ biểu thị đơn giá hoặc giá trị lợi nhuận ngoài của phần tử $i_k$.
  • Lợi ích của phần tử trong giao dịch: $U(i_k, T_j) = O(i_k, T_j) \times S({i_k})$.
  • Lợi ích thực tế của tập $X$ trong CSDL ($AU(X)$) là tổng lợi ích của $X$ trên toàn bộ các giao dịch chứa $X$.

• Các mô hình chặn trên:

  • Mô hình TWU (Transaction Weighted Utility).
  • Mô hình CWU (Candidate Weighted Utility): Phân chia thành lợi ích ứng viên có trọng số cao (High CWU – HCWU) và thấp (Low CWU – LCWU).
  • Mô hình RTWU (Remaining Transaction Weighted Utilization): Khai thác lợi ích của các phần tử còn lại trong giao dịch sau phần tử đang xét để thiết lập cận trên chặt.

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

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

• Phương pháp toán học và lý thuyết thuật toán: Thiết lập mô hình, định nghĩa hình thức, chứng minh các mệnh đề toán học về tính đúng đắn và đánh giá độ phức tạp tính toán trong trường hợp xấu nhất ($O(2^n)$ cho thuật toán tuần tự và $O(\frac{1}{p} \cdot 2^n)$ cho thuật toán song song với $p$ luồng xử lý).
• Thiết kế cấu trúc dữ liệu: Xây dựng cấu trúc cây nén CUP-Tree, bảng chỉ số (Index Table – IT), bảng ứng viên (Table Candidate – TC), bảng lợi ích (Utility Table – UT) và danh sách lợi ích mở rộng (Extended Utility-List).
• Phương pháp thực nghiệm: Cài đặt các thuật toán tuần tự và song song trên môi trường Visual Studio.NET, sử dụng thư viện OpenMP trên phần cứng máy tính IBM T61 (Intel Core 2 Duo, RAM 2GB, 3 luồng thực thi). Đo đạc thời gian chạy, số lượng tập ứng viên sinh ra và mức tiêu thụ tài nguyên trên các tập dữ liệu tổng hợp ($T30I4D100KN100K$, $T10I4D100K$, $T10I4D200K$, $T40I4D100K$, $T5N5D100K$, $T10N5D100K$, tập 52 phần tử/3984 giao dịch) và tập dữ liệu thực tế ($Mushroom$, $Foodmart$).

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

Chương 1: Tổng quan về khai phá tập phổ biến

Chương 1 hệ thống hóa các khái niệm nền tảng về luật kết hợp, tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao; phân tích ưu nhược điểm của các cấu trúc dạng cây (FP-tree, CFP-tree, WIT-tree) và cấu trúc dạng dọc (tidset, diffset). Trọng tâm đóng góp của chương là việc đề xuất kỹ thuật khai phá tập phổ biến có trọng số theo chiều dọc:

• Thuật toán tuần tự VMWFP (Vertical Mining of Weighted Frequent Patterns): Ứng dụng cấu trúc diffset để phân loại các tập 2-phần tử thành các nhóm cơ bản (Basic Groups – $G_i$) có cùng diffset. Tiếp đó, thuật toán kết hợp các nhóm cơ bản cùng tiền tố thành lớp các nhóm (Class Groups – $N_k$) nếu thỏa mãn điều kiện độ hỗ trợ có trọng số: $$\text{Supp}(X) = T - C - TI$$ $$\text{Weight}(X) = \sum_{i \in X} w_i$$ $$\text{WSupp}(X) = \text{Supp}(X) \times \text{Weight}(X) \ge \text{minwsupp}$$ Trong đó $T$ là tổng số giao dịch, $C$ là số tid trong diffset của tiền tố, $TI$ là số tid trong diffset của nhóm.

• Thuật toán song song PVMWFP (Parallel VMWFP): Được xây dựng theo mô hình bộ nhớ chia sẻ. Tiến trình Master phân chia CSDL theo chiều ngang cho các luồng; mỗi luồng tính toán diffset cục bộ, sau đó Master phân phối các tiền tố độc lập cho từng luồng để tính toán song song việc tạo nhóm và sinh tập phổ biến có trọng số.

• Độ phức tạp tính toán: Luận án chứng minh mệnh đề độ phức tạp trong trường hợp xấu nhất của VMWFP là $O(2^n)$ và của PVMWFP là $O(\frac{1}{p} \cdot 2^n)$ (với $n$ là số phần tử, $p$ là số luồng). Thực nghiệm trên tập dữ liệu gồm 52 phần tử và 3984 giao dịch ngẫu nhiên cho thấy PVMWFP với 3 luồng đạt tốc độ xử lý nhanh hơn rõ rệt so với thuật toán tuần tự VMWFP.

Chương 2: Thuật toán khai phá tập lợi ích cao dựa trên mô hình CWU

Chương 2 tập trung giải quyết bài toán khai phá tập lợi ích cao bằng cách khắc phục sự lỏng lẻo của chặn trên TWU thông qua mô hình đề xuất CWU:

• Mô hình CWU (Candidate Weighted Utility): Đưa ra công thức ước lượng cận trên lợi ích của ứng viên chặt hơn TWU, cho phép phân loại ứng viên thành nhóm có trọng số cao (HCWU) và nhóm có trọng số thấp (LCWU), giúp loại bỏ sớm các tập ứng viên không tiềm năng.
• Thuật toán HP: Khai phá tập lợi ích cao dựa trên sự kết hợp giữa bảng chỉ số hình chiếu (Projected Index Table – IT) và mô hình CWU, cắt tỉa không gian tìm kiếm trực tiếp trên các hình chiếu CSDL.
• Thuật toán song song PPB: Khai phá tập lợi ích cao song song dựa trên chỉ số hình chiếu và danh sách lợi ích (Utility List – UL). Thuật toán phân bổ các nhánh tìm kiếm dựa trên tiền tố cho các luồng xử lý độc lập, tối ưu hóa quá trình tính toán lợi ích cục bộ và hợp nhất kết quả toàn cục.
• Thuật toán CTU-PRO+: Cải tiến dựa trên ý tưởng cây CFP và CSDL chiếu của thuật toán CT-PRO, thực hiện khai phá không đệ quy trên cây lợi ích nén.
• Kết quả thực nghiệm: Đánh giá trên các bộ dữ liệu $T30I4D100KN100K$, $Mushroom$, $T5N5D100K$ và $T10N5D100K$ cho thấy mô hình CWU và các thuật toán HP, PPB, CTU-PRO+ giảm đáng kể số lượng tập ứng viên sinh ra so với các thuật toán dựa trên TWU truyền thống, từ đó giảm thời gian thực thi khi thay đổi ngưỡng lợi ích tối thiểu ($\text{minutil}$).

Chương 3: Thuật toán khai phá tập lợi ích cao trên cây danh sách lợi ích và cấu trúc RTWU

Chương 3 phát triển các cấu trúc dữ liệu và kỹ thuật cắt tỉa nâng cao nhằm tối ưu hóa hiệu năng khai phá tập lợi ích cao mà không phát sinh ứng viên trung gian:

• Cấu trúc cây CUP (Compressed Utility Pattern tree): Cấu trúc cây nén lưu trữ đầy đủ thông tin về tần suất và giá trị lợi ích của các phần tử trong giao dịch. Cây CUP kết hợp với bảng mục toàn cục (GlobalItemTable) và cây toàn cục (GlobalCUP-Tree), cho phép trích xuất các mẫu điều kiện và xây dựng cây CUP điều kiện cho từng phần tử mà chỉ chiếm dung lượng bộ nhớ nhỏ.
• Thuật toán HUI-Growth: Thực hiện khai phá tập lợi ích cao trực tiếp trên cấu trúc cây CUP thông qua việc duyệt mẫu điều kiện, loại bỏ thao tác sinh ứng viên tốn kém. Thực nghiệm trên dữ liệu $Mushroom$ và $T40I4D100K$ chứng minh thuật toán có thời gian chạy ổn định.
• Cấu trúc cắt tỉa RTWU (Remaining Transaction Weighted Utilization) và danh sách lợi ích mở rộng: Cấu trúc RTWU tính toán tổng lợi ích của tập phần tử kết hợp với phần lợi ích còn lại của các phần tử xuất hiện phía sau trong cùng một giao dịch. Danh sách lợi ích mở rộng (Extended Utility-List) lưu trữ bộ thông tin gồm chỉ số giao dịch (tid), lợi ích thực tế của tập phần tử trong giao dịch ($iutil$) và lợi ích còn lại ($rutil$).
• Thuật toán tuần tự EAHUI-Miner: Sử dụng danh sách lợi ích mở rộng và cận trên RTWU để thực hiện cắt tỉa không gian tìm kiếm theo chiều sâu.
• Thuật toán song song PEAHUI-Miner: Song song hóa quá trình duyệt danh sách lợi ích mở rộng và phân chia nhánh tìm kiếm trên cây tiền tố cho các luồng.
• Kết quả thực nghiệm: Thử nghiệm trên các tập dữ liệu $Mushroom$, $Foodmart$, $T10I4D100K$ và $T10I4D200K$. So sánh số lượng tập ứng viên và thời gian thực hiện khẳng định EAHUI-Miner và PEAHUI-Miner cắt giảm vượt trội số lượng ứng viên cần kiểm tra, đồng thời phiên bản song song PEAHUI-Miner nâng cao tốc độ xử lý khi khối lượng giao dịch tăng lên 200.000 ($D200K$).

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả khoa học chính cả về mặt lý luận và thực tiễn:

Đóng góp về mặt lý luận và mô hình

1. Đề xuất mô hình CWU (Candidate Weighted Utility): Cung cấp cận trên chặt hơn mô hình TWU cổ điển, giảm thiểu sự bùng nổ số lượng tập ứng viên giả trong khai phá tập lợi ích cao.
2. Đề xuất cấu trúc cắt tỉa RTWU và danh sách lợi ích mở rộng: Thiết lập cơ chế đánh giá lợi ích còn lại của giao dịch, cho phép cắt tỉa sớm các nhánh tìm kiếm không thỏa mãn ngưỡng lợi ích.
3. Thiết kế cấu trúc cây CUP (Compressed Utility Pattern): Cung cấp giải pháp nén cơ sở dữ liệu giao dịch định lượng và cấu trúc cây điều kiện phục vụ khai phá không đệ quy.
4. Chứng minh toán học: Xác lập cơ sở lý thuyết và chứng minh độ phức tạp tính toán trường hợp xấu nhất cho thuật toán tuần tự $O(2^n)$ và thuật toán song song $O(\frac{1}{p} \cdot 2^n)$.

Đóng góp về mặt thuật toán và thực tiễn

Luận án đã thiết kế và cài đặt thực nghiệm 7 thuật toán:

STT	Tên thuật toán	Hướng tiếp cận	Cấu trúc dữ liệu / Mô hình áp dụng
1	VMWFP	Tuần tự (WFI)	Cấu trúc nhóm Diffset (Basic Groups, Class Groups)
2	PVMWFP	Song song (WFI)	Cấu trúc Diffset phân vùng, đa luồng OpenMP
3	HP	Tuần tự (HUI)	Bảng chỉ số hình chiếu (IT) và mô hình CWU
4	PPB	Song song (HUI)	Chỉ số hình chiếu và danh sách lợi ích (Utility List)
5	CTU-PRO+	Tuần tự (HUI)	Cấu trúc cây CFP và CSDL chiếu không đệ quy
6	HUI-Growth	Tuần tự (HUI)	Cấu trúc cây nén CUP-Tree và mẫu điều kiện
7	EAHUI-Miner / PEAHUI-Miner	Tuần tự / Song song (HUI)	Cấu trúc RTWU và danh sách lợi ích mở rộng

Kiến nghị và giải pháp đề xuất

• Ứng dụng các thuật toán khai phá tập lợi ích cao và tập phổ biến có trọng số vào các bài toán thương mại thực tế như phân tích giỏ hàng siêu thị, xác định nhóm sản phẩm đem lại lợi nhuận cao nhất, tối ưu hóa vị trí trưng bày hàng hóa và giảm thiểu tồn kho.
• Ứng dụng mô hình tính toán song song dựa trên phân chia tiền tố để xử lý dữ liệu giao dịch có quy mô lớn trong doanh nghiệp.

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

Hạn chế ghi nhận

• Các thuật toán đề xuất chủ yếu tập trung xử lý trên cơ sở dữ liệu giao dịch tĩnh; chưa xử lý trực tiếp trên các mô hình dữ liệu biến đổi liên tục hoặc cơ sở dữ liệu phân tán không chia sẻ bộ nhớ.
• Trong trường hợp xấu nhất, khi mọi tập con đều thỏa mãn ngưỡng hỗ trợ hoặc ngưỡng lợi ích, độ phức tạp tính toán lý thuyết vẫn phụ thuộc vào hàm mũ $O(2^n)$.
• Các thực nghiệm song song (PVMWFP, PEAHUI-Miner) chủ yếu được thử nghiệm trên mô hình bộ nhớ chia sẻ với số luồng giới hạn (thực nghiệm trên phần cứng máy tính cá nhân 3 luồng).

Hướng nghiên cứu tiếp

• Mở rộng mô hình và phát triển các thuật toán khai phá tập phần tử có trọng số và lợi ích cao trên môi trường dòng dữ liệu (data stream) và cơ sở dữ liệu động có sự cập nhật thêm/xóa giao dịch theo thời gian thực.
• Phát triển các thuật toán song song trên môi trường phân tán quy mô lớn (mô hình MapReduce/Hadoop hoặc Spark) để khai phá dữ liệu phân tán.
• Nghiên cứu kết hợp khai phá tập lợi ích cao với các dạng ràng buộc ngữ nghĩa và tri thức miền bổ sung.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các nhóm đối tượng:

• Nghiên cứu sinh và học viên cao học chuyên ngành Khoa học Máy tính, Cơ sở Toán học cho Tin học: Tham khảo phương pháp thiết kế cận trên toán học (CWU, RTWU), cách tiếp cận cấu trúc nén dữ liệu (Diffset groups, CUP-tree, Extended Utility-List) và phương pháp chứng minh độ phức tạp tính toán.
• Giảng viên giảng dạy môn Khai phá dữ liệu và Khám phá tri thức: Sử dụng các thuật toán từ Apriori, FP-growth đến VMWFP, EAHUI-Miner làm tài liệu giảng dạy chuyên đề nâng cao về luật kết hợp, trọng số và độ đo lợi ích.
• Chuyên gia phát triển phần mềm và phân tích dữ liệu kinh doanh: Tham khảo mã nguồn, cấu trúc thuật toán song song OpenMP và các cơ chế đánh giá lợi ích thực tế nhằm tích hợp vào hệ thống phân tích giỏ hàng (Market Basket Analysis) và hỗ trợ ra quyết định.

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

1. Điểm khác biệt căn bản giữa khai phá tập phổ biến truyền thống (FI), tập phổ biến có trọng số (WFI) và tập lợi ích cao (HUI) là gì?
Khai phá tập phổ biến truyền thống (FI) chỉ xem xét tần suất xuất hiện nhị phân của các phần tử và coi mọi phần tử có tầm quan trọng như nhau. Khai phá tập phổ biến có trọng số (WFI) bổ sung trọng số tĩnh ($w_i$) cho từng phần tử để phản ánh mức độ quan trọng. Khai phá tập lợi ích cao (HUI) kết hợp cả hai yếu tố: lợi ích trong ($O(i_k, T_j)$ - số lượng mua trong từng giao dịch) và lợi ích ngoài ($S({i_k})$ - đơn giá hoặc tỷ suất lợi nhuận), giúp đánh giá chính xác giá trị thực tế của tập mục.

2. Tại sao bài toán khai phá tập lợi ích cao không thể áp dụng trực tiếp thuật toán Apriori truyền thống?
Tập lợi ích cao không có tính chất đóng (tính chất phản đơn điệu Apriori): một tập phần tử có lợi ích cao thì các tập con của nó chưa chắc đã có lợi ích cao, và ngược lại một tập con có lợi ích thấp vẫn có thể tạo thành một tập cha có lợi ích cao do tổng lượng mua lớn. Do đó, không thể dùng điều kiện tập con không phổ biến để cắt tỉa tập cha như trong Apriori thông thường.

3. Cấu trúc Diffset trong thuật toán VMWFP hoạt động như thế nào và đem lại lợi ích gì so với Tidset?
Thay vì lưu trữ toàn bộ danh sách các giao dịch chứa phần tử (Tidset), cấu trúc Diffset chỉ lưu trữ danh sách các giao dịch không chứa phần tử đó ($d(a) = U \setminus t(a)$). Khi kết hợp các tập phần tử, $d(ab) = d(b) \setminus d(a)$, độ hỗ trợ được tính nhanh bằng phép trừ $\sigma(ab) = \sigma(a) - |d(ab)|$. Kỹ thuật này giúp giảm mạnh kích thước bộ nhớ cần thiết để lưu trữ kết quả trung gian và tăng tốc độ tính toán.

4. Mô hình CWU và cấu trúc RTWU khắc phục điểm yếu nào của mô hình TWU?
Mô hình TWU truyền thống cộng toàn bộ lợi ích của giao dịch cho mọi phần tử xuất hiện trong giao dịch đó, tạo ra ngưỡng chặn trên quá lớn so với lợi ích thực tế ($AU$), dẫn đến sinh ra một lượng khổng lồ các ứng viên giả. Mô hình CWU và cấu trúc RTWU ước lượng cận trên chặt hơn bằng cách chỉ tính lợi ích của tập phần tử cộng với lợi ích của các phần tử còn lại trong giao dịch, loại bỏ sớm các ứng viên dư thừa ngay từ các bước đầu.

5. Các thuật toán song song trong luận án (PVMWFP, PPB, PEAHUI-Miner) được thiết kế dựa trên nguyên lý nào?
Các thuật toán song song được thiết kế trên mô hình bộ nhớ chia sẻ sử dụng thư viện OpenMP. Nguyên lý chung là phân vùng dữ liệu giao dịch theo chiều ngang hoặc phân chia không gian tìm kiếm dựa trên các tiền tố độc lập cho các luồng xử lý riêng biệt, sau đó tổng hợp kết quả tại tiến trình chính, giúp tối ưu hóa thời gian thực thi khi kích thước dữ liệu tăng.

Kết luận

Luận án "Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao" của tác giả Đậu Hải Phong đã giải quyết trọn vẹn bài toán tối ưu hóa không gian tìm kiếm và nâng cao tốc độ xử lý trong khai phá dữ liệu có trọng số và định lượng lợi ích. Bằng việc đề xuất các mô hình chặn trên chặt chẽ (CWU, RTWU), cấu trúc dữ liệu nén (Diffset nhóm, CUP-tree, Extended Utility-List) cùng hệ thống 7 thuật toán tuần tự và song song, công trình đã khắc phục hiệu quả hiện tượng bùng nổ tập ứng viên của các phương pháp TWU truyền thống. Các kết quả nghiên cứu được chứng minh chặt chẽ về mặt toán học và kiểm chứng đầy đủ qua thực nghiệm trên các tập dữ liệu chuẩn, đóng góp giá trị học thuật vững chắc cho chuyên ngành Cơ sở Toán học cho Tin học.

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

Chương 1 giới thiệu các khái niệm cơ sở liên quan; phương pháp khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao. Chương 2 trình bày mô hình CWU, các thuật toán khai phá tập lợi ích cao dựa trên mô hình CWU như: HP, PPB, CTU-PRO+. Chương 3 trình bày cấu trúc cây mẫu lợi ích nén (CUP) kết hợp danh sách lợi ích và thuật toán HUI-Growth khai phá tập lợi ích cao dựa trên cấu trúc cây CUP; trình bày cấu trúc cắt tỉa RTWU và hai thuật toán tuần tự, song song khai phá tập lợi ích cao dựa trên cấu trúc cắt tỉa tập ứng viên RTWU là EAHUI- Miner, PEAHUI-Miner. TỔNG QUAN VỀ KHAI PHÁ TẬP PHỔ BIẾN Chương này trình bày các khái niệm liên quan đến khai phá tập phổ biến, luật kết hợp, tập phổ biến có trọng số, tập lợi ích cao; phân loại các phương pháp khai phá tập phổ biến, tập phổ biến có trọng số, tập lợi ích cao và phân tích những ưu điểm, hạn chế của chúng.

Đề xuất thuật toán khai phá tập phổ biến có trọng số theo chiều dọc [I]. Giới thiệu chung Khai phá tập phổ biến là tìm ra các tập phần tử có số lần xuất hiện lớn hơn một ngưỡng hỗ trợ tối thiểu (minsupp). Tuy nhiên, khai phá tập phổ biến có những hạn chế. Thứ nhất, nó xử lý tất cả các phần tử có tầm quan trọng như nhau.

Thứ hai, trong một giao dịch mỗi phần tử chỉ có trạng thái xuất hiện hoặc không xuất hiện. Rõ ràng những hạn chế này làm cho bài toán khai phá tập phổ biến truyền thống không phù hợp với các cơ sở dữ liệu thực tế, ví dụ như trong cơ sở dữ liệu của siêu thị, mỗi mặt hàng có tầm quan trọng hay giá cả khác nhau, số lượng mua các mặt hàng trong mỗi giao dịch cũng khác nhau,… Vì vậy, mô hình khai phá tập phổ biến chỉ phản ánh mối tương quan giữa các phần tử xuất hiện trong cơ sở dữ liệu, nhưng không phản ánh ý nghĩa của từng phần tử dữ liệu. Để khắc phục những nhược điểm trên có hai mô hình được đưa ra: Tập phổ biến có trọng số - WFI và Tập lợi ích cao - HUI. Trong đó, mỗi phần tử có một trọng số khác nhau như: lợi ích, giá cả, độ quan trọng hay số lượng,…Một tập các phần tử được xem là phổ biến có trọng số khi giá trị có trọng số của chúng lớn hơn một ngưỡng cho trước.

Từ mô hình này nhiều 17 thuật toán khai phá tập phổ biến có trọng số được đưa ra [11], [72], [64], [33], [58], [73],… Năm 2003 Chan [13] và cộng sự đã đưa ra mô hình khai phá tập lợi ích cao (High Utility Itemsets – HUI), khắc phục những hạn chế của mô hình khai phá tập phổ biến và tập phổ biến có trọng số. Mô hình này cho phép người sử dụng đánh giá được tầm quan trọng của từng phần tử qua hai trọng số khác nhau gọi là lợi ích trong và lợi ích ngoài. Lợi ích trong có thể là số lượng từng phần tử trong giao dịch; lợi ích ngoài có thể là lợi nhuận hoặc giá cả của các mặt hàng. Lợi ích của một phần tử là tích hai giá trị lợi ích trong và lợi ích ngoài.

Một tập phần tử được gọi là tập lợi ích cao khi giá trị lợi ích của nó lớn hơn một ngưỡng do người dùng định nghĩa trước. Nhờ khai phá tập lợi ích cao có thể đưa ra một số quyết định quan trọng như tối đa hóa doanh thu, giảm thiểu chi phí, hạn chế hàng tồn kho,… 1. 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 [5] đề 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 luật kết hợp và tập phổ biến. Khái niệm cơ sở Cho D = {T1, T2,…Tm} là cơ sở dữ liệu giao dịch và I = {i 1, i2,…,in} là tập các phần tử trong cơ sở dữ liệu D. Mỗi giao dịch T i  I.

Tập X  I có k phần tử được gọi là tập k-phần tử.1) | D| 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: Định nghĩa 1. [6] Độ 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.3) Support( X) Định nghĩa 1. [6] Tập phần tử X được gọi là tập phổ biến nếu có Support(X) ≥ minsupp, với minsupp là ngưỡng hỗ trợ tối thiểu cho trước.

[6] 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 1. [4] (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.

[4] 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. Một số phương pháp khai phá tập phổ biến CHƯƠNG 2. Phương pháp dựa trên quan hệ kết nối Phương pháp thường được sử dụng là dựa vào việc kết nối để sinh tập ứng viên (k+1)-phần tử từ tập phổ biến k-phần tử, sau đó duyệt lại cơ sở dữ liệu giao dịch để xác nhận. Trong các phương pháp này, thuật toán Apriori là phổ biến và đơn giản nhất.

Srikant [6] đưa ra thuật toán Apriori dựa trên phương pháp kết nối. Thuật toán này xử lý từng mức một (level-wise), nghĩa là xác định các tập phổ biến có k-phần tử, rồi mới xác định tập phổ biến (k+1)-phần tử. Điều này đưa tới tính chất cơ bản của thuật toán Apriori là mọi tập con của tập phổ biến cũng là tập phổ biến. Vì vậy, các ứng viên phổ biến có chiều dài (k+1)-phần tử có thể được sinh ra bằng cách kết hợp các tập phổ biến có k- phần tử.

Một phép nối để tạo ra tập có k-phần tử được thực hiện khi (k-1)- phần tử chung. Để giảm số lượng ứng viên được sinh ra, tính chất đóng của tập phổ biến được sử dụng. Tính chất này đảm bảo rằng nếu trong tập k-phần 20 tử có tập con không phổ biến thì chắc chắn tập k-phần tử này cũng không phổ biến. Do vậy, có thể cắt tỉa tập này đi mà không cần xét tiếp.

Thuật toán DHP [45] được đề xuất dựa trên phương pháp Apriori, sử dụng phương pháp cắt tỉa và băm. Hai cách tối ưu cải thiện tốc độ thuật toán: cách thứ nhất là dựa vào việc cắt tỉa các ứng viên trong mỗi lần lặp và cách thứ hai là cắt tỉa các giao dịch để tính nhanh độ hỗ trợ. Phương pháp sử dụng cấu trúc cây Phương pháp sử dụng cấu trúc cây dựa trên kỹ thuật liệt kê tập hợp. Các ứng viên được xác định nhờ sử dụng đồ thị con của đồ thị các tập phần tử (Hình 1.1), còn được gọi là cây từ điển hoặc cây liệt kê [3].

Khi đó, việc sinh các tập phổ biến tương ứng với việc xây dựng cây từ điển. Cây có thể khai phá theo chiều rộng hoặc chiều sâu. Cấu trúc cây từ điển được xem là cơ sở cho phát triển thuật toán. Cây từ điển (hoặc cây liệt kê) 21 Thuật toán AIS [5] sử dụng cây từ điển, được xây dựng theo kiểu từng bước một.

Các tập phần tử được đưa ra ở mỗi mức gần với sử dụng cơ sở dữ liệu giao dịch. Thuật toán kết hợp các phần tử theo thứ tự từ điển để sinh tập ứng viên, sau đó đếm độ hỗ trợ của các tập ứng viên trên cơ sở dữ liệu giao dịch. Đây là phương pháp đơn giản khai phá toàn bộ không gian tìm kiếm. Thuật toán Eclat [74] sử dụng cách tiếp cận theo chiều rộng trước (breadth- first) dựa trên phép giao tập tid của tập phần tử giống như thuật toán của Savasere [51], sau đó phân chia các ứng viên vào các nhóm rời nhau, sử dụng cách tiếp cận phân vùng ứng viên tương tự như thuật toán Apriori song song.

Thuật toán Eclat [74] được trình bày hợp lý nhất trên cây từ điển với phép duyệt cây theo chiều rộng. Thuật toán Monet và Partition [31], [51] đề xuất xác định sự giao nhau đệ quy của danh sách tid (tid-lists) và một số biến thể hiệu quả của mô hình này. Thuật toán VIPER [53] sử dụng phương pháp tiếp cận dọc (vertical) theo tid để khai phá tập phổ biến. Ý tưởng cơ bản của thuật toán này là biểu diễn cơ sở dữ liệu giao dịch theo chiều dọc bằng véc tơ nhị phân.

Véc tơ này được sử dụng để đếm sự xuất hiện của tập ứng viên phổ biến khá hiệu quả. Đây là cách biểu diễn nén khác của tập tid cho phép đạt được một số điểm tối ưu trong thuật toán. Về bản chất, VIPER không khác nhau nhiều so với Eclat về phương pháp đếm. Sự khác biệt chủ yếu là về biểu diễn véc tơ bit nén và xử lý hiệu quả biểu diễn này.

Phương pháp tăng trưởng đệ quy dựa trên hậu tố Phương pháp FP-growth [30] tìm kiếm mẫu dựa trên hậu tố, sử dụng cấu trúc cây mẫu phổ biến (FP-tree) để biểu diễn CSDL giao dịch làm cho việc tính độ hỗ trợ của tập phần tử nhanh hơn. Cây mẫu phổ biến [30] biểu diễn 22 dạng nén của CSDL giao dịch, được xây dựng theo thứ tự giảm dần độ hỗ trợ của các phần tử từ gốc đến lá. Mỗi cây FP có thể xem như một cấu trúc dữ liệu cây dựa trên tiền tố (prefix-based) của CSDL giao dịch chứa các phần tử phổ biến. Do vậy, mỗi nút được gán nhãn là một phần tử nào đó và lưu trữ độ hỗ trợ của tập phần tử gồm những phần tử trên đường đi từ một nút bất kỳ đến nút gốc.

Thuật toán CT-PRO [57], sử dụng cấu trúc cây mẫu phổ biến mới gọi là cây nén mẫu phổ biến (CFP-Compact Frequent Pattern) chứa đủ các thông tin như trong cây FP, nhưng chỉ chiếm 50% lượng lưu trữ [57].