Luận Án Tiến Sĩ: Phát Triển Thuật Toán Khai Thác Tập Mục Hiệu Quả Trên Cơ Sở Dữ Liệu Phân Cấp

Luận án tiến sĩ HUS nghiên cứu phát triển thuật toán khai thác tập mục hiệu quả trên cơ sở dữ liệu phân cấp, nâng cao khả năng xử lý dữ liệu.

• Tác giả: Nguyễn Duy Hàm
• Người hướng dẫn: TS. Nguyễn Thị Hồng Minh
• Trường học: Trường Đại Học Khoa Học Tự Nhiên - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Cơ Sở Toán Cho Tin Học
• Đề tài: Phát Triển Một Số Thuật Toán Hiệu Quả Khai Thác Tập Mục Trên Cơ Sở Dữ Liệu Số Lượng Có Sự Phân Cấp Các Mục
• Loại tài liệu: Luận Án Tiến Sĩ
• Năm xuất bản: 2016
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. MỞ ĐẦU
• 2. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC
• 2.1. Bài toán khai thác tập mục
• 2.2. Một số khái niệm cơ bản
• 2.3. Bài toán khai thác FI
• 2.4. Các phương pháp khai thác FI
• 2.4.1. Phương pháp khai thác FI trên CSDL ngang
• 2.4.2. Phương pháp khai thác FI trên CSDL dọc dựa trên IT-tree
• 2.5. Một số phương pháp khai thác FWI và FWUI trên CSDL số lượng
• 2.5.1. Khai thác FWI
• 2.5.2. Khai thác FWUI
• 2.5.3. Khai thác TRFIk
• 2.5.4. Khai thác FI trên CSDL có sự phân cấp các mục
• 2.5.5. Tiếp cận bit-vector trong khai thác FI
• 2.6. Kết luận chương
• 3. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU SỐ LƯỢNG
• 3.1. Thuật toán khai thác tập FWI
• 3.2. Thuật toán tính giao của hai IWS
• 3.3. Thuật toán khai thác FWI
• 3.4. Kết quả thực nghiệm
• 3.5. Thuật toán khai thác FWUI
• 3.6. Cấu trúc Multi bit segment
• 3.7. Thuật toán xác định giao MBiS
• 3.8. Thuật toán khai thác FWUI dựa trên MBiS-tree
• 3.9. Kết quả thực nghiệm
• 3.10. Thuật toán khai thác TRFWUIk
• 3.11. Một số khái niệm
• 3.12. Cấu trúc DTab
• 3.13. Cấu trúc TR-tree
• 3.14. Thuật toán khai thác TRFWUIk sử dụng cấu trúc dữ liệu DTab
• 3.15. Thuật toán khai thác nhanh TRFWUIk dựa trên cấu trúc DHeap
• 3.16. Kết quả thực nghiệm
• 3.17. Kết luận chương
• 4. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU SỐ LƯỢNG CÓ SỰ PHÂN CẤP CÁC MỤC
• 4.1. Giới thiệu bài toán
• 4.2. Thuật toán khai thác FWUI trên HQDB
• 4.3. Thuật toán xác định weight cho các mục cha
• 4.4. Thuật toán thêm mục cha vào CSDL
• 4.5. Thuật toán khai thác FWUI
• 4.6. Một số cải tiến nâng cao hiệu quả khai thác FWUI trên HQDB
• 4.7. Cấu trúc EDBV
• 4.8. Tính tidset nút cha từ tidset nút con
• 4.9. Kiểm tra mối quan hệ cha con đối với các mục trong tập mục
• 4.10. Thuật toán khai thác nhanh FWUI trên HQDB
• 4.11. Kết quả thực nghiệm
• 4.12. CSDL thực nghiệm
• 4.13. Kết quả thực nghiệm
• 4.14. Kết luận chương
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN

Tóm tắt

I. Tổng Quan Về Phát Triển Thuật Toán Khai Thác Tập Mục

Trong bối cảnh dữ liệu ngày càng gia tăng, việc phát triển các thuật toán khai thác tập mục trở nên cần thiết. Các thuật toán này giúp tìm ra các mẫu và quy luật trong dữ liệu, từ đó hỗ trợ ra quyết định trong nhiều lĩnh vực như thương mại điện tử, phân tích thị trường, và nhiều ứng dụng khác. Việc khai thác tập mục không chỉ giúp tiết kiệm thời gian mà còn nâng cao hiệu quả trong việc xử lý dữ liệu lớn.

1.1. Khái Niệm Về Khai Thác Tập Mục

Khai thác tập mục là quá trình tìm kiếm các tập hợp mục thường xuyên xuất hiện trong cơ sở dữ liệu. Điều này giúp xác định các mối quan hệ giữa các mục, từ đó phát hiện ra các quy luật tiềm ẩn trong dữ liệu.

1.2. Lịch Sử Phát Triển Thuật Toán Khai Thác Tập Mục

Thuật toán đầu tiên được biết đến trong lĩnh vực này là Apriori, được phát triển bởi Agrawal và các đồng sự vào năm 1994. Kể từ đó, nhiều thuật toán khác như FP-Growth và Eclat đã được phát triển nhằm cải thiện hiệu suất và giảm thiểu thời gian xử lý.

II. Vấn Đề Trong Khai Thác Tập Mục Trên Cơ Sở Dữ Liệu Phân Cấp

Khai thác tập mục trên cơ sở dữ liệu phân cấp gặp nhiều thách thức, đặc biệt là về hiệu suất và bộ nhớ. Các thuật toán hiện tại thường tốn thời gian và không tối ưu cho các cơ sở dữ liệu lớn có cấu trúc phân cấp. Việc thêm các mục cha vào cơ sở dữ liệu cũng là một vấn đề lớn cần giải quyết.

2.1. Thách Thức Về Thời Gian Xử Lý

Nhiều thuật toán hiện tại yêu cầu quét cơ sở dữ liệu nhiều lần, dẫn đến thời gian xử lý kéo dài. Điều này đặc biệt rõ ràng khi làm việc với các cơ sở dữ liệu lớn.

2.2. Vấn Đề Về Bộ Nhớ

Việc lưu trữ các cấu trúc dữ liệu như tidset trong bộ nhớ có thể gây ra tình trạng thiếu hụt bộ nhớ, ảnh hưởng đến hiệu suất của thuật toán. Cần có các phương pháp tối ưu hóa để giảm thiểu yêu cầu bộ nhớ.

III. Phương Pháp Khai Thác Tập Mục Hiệu Quả

Để cải thiện hiệu quả khai thác tập mục, nhiều phương pháp mới đã được đề xuất. Các phương pháp này tập trung vào việc tối ưu hóa thuật toán và cấu trúc dữ liệu, nhằm giảm thiểu thời gian và bộ nhớ sử dụng.

3.1. Cải Tiến Thuật Toán Apriori

Cải tiến thuật toán Apriori bằng cách sử dụng các cấu trúc dữ liệu mới giúp giảm thiểu số lần quét cơ sở dữ liệu, từ đó nâng cao hiệu suất khai thác.

3.2. Sử Dụng Cấu Trúc Dữ Liệu Mới

Việc áp dụng các cấu trúc dữ liệu như bit-vector và tree-based structures có thể giúp tối ưu hóa bộ nhớ và thời gian xử lý, từ đó nâng cao hiệu quả khai thác tập mục.

IV. Ứng Dụng Thực Tiễn Của Khai Thác Tập Mục

Khai thác tập mục có nhiều ứng dụng thực tiễn trong các lĩnh vực như thương mại điện tử, phân tích dữ liệu và marketing. Việc phát hiện các quy luật trong hành vi người tiêu dùng giúp các doanh nghiệp đưa ra các quyết định chiến lược hiệu quả.

4.1. Ứng Dụng Trong Thương Mại Điện Tử

Các thuật toán khai thác tập mục giúp các nhà bán lẻ trực tuyến xác định các sản phẩm thường xuyên được mua cùng nhau, từ đó tối ưu hóa chiến lược marketing và khuyến mãi.

4.2. Ứng Dụng Trong Phân Tích Dữ Liệu

Khai thác tập mục cũng được sử dụng trong phân tích dữ liệu để phát hiện các xu hướng và mẫu trong dữ liệu lớn, hỗ trợ ra quyết định trong các lĩnh vực như tài chính và y tế.

V. Kết Luận Và Hướng Phát Triển Tương Lai

Khai thác tập mục trên cơ sở dữ liệu phân cấp là một lĩnh vực nghiên cứu quan trọng với nhiều thách thức và cơ hội. Việc phát triển các thuật toán hiệu quả sẽ giúp cải thiện khả năng khai thác dữ liệu trong các ứng dụng thực tiễn.

5.1. Tương Lai Của Khai Thác Tập Mục

Trong tương lai, việc phát triển các thuật toán khai thác tập mục sẽ tiếp tục được nghiên cứu và cải tiến, nhằm đáp ứng nhu cầu ngày càng cao trong việc xử lý dữ liệu lớn.

5.2. Hướng Nghiên Cứu Mới

Các nghiên cứu mới có thể tập trung vào việc kết hợp các phương pháp học máy và khai thác dữ liệu để phát hiện các mẫu phức tạp hơn trong dữ liệu, từ đó nâng cao hiệu quả khai thác.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Phát triển một số thuật toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lượng có sự phân cấp các mục" được thực hiện bởi nghiên cứu sinh Nguyễn Duy Hàm, thuộc chuyên ngành Cơ sở toán cho tin học (mã số: 62460110) tại Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội vào năm 2016, dưới sự hướng dẫn khoa học của TS. Nguyễn Thị Hồng Minh và PGS. Võ Đình Bảy.

Về tính cấp thiết và khoảng trống nghiên cứu, trong lĩnh vực khai thác dữ liệu, bài toán khai thác tập mục phổ biến (Frequent Itemsets - FI) đóng vai trò nền tảng để sinh luật kết hợp, nhận diện quy luật dữ liệu và hỗ trợ ra quyết định. Tuy nhiên, các kỹ thuật khai thác FI truyền thống trên cơ sở dữ liệu (CSDL) nhị phân chỉ ghi nhận sự xuất hiện của mục mà không phản ánh số lượng hay giá trị kinh tế của từng mục trong giao dịch. Để phản ánh thực tế, các dạng CSDL số lượng (Quantitative Database) và CSDL có trọng số (Weighted Database) đã được quan tâm nghiên cứu với các bài toán khai thác tập mục phổ biến có trọng số (Frequent Weighted Itemsets - FWI) và tập mục phổ biến trọng số hữu ích (Frequent Weighted Utility Itemsets - FWUI). Dù vậy, các thuật toán hiện hành vẫn gặp rào cản lớn về thời gian xử lý và dung lượng bộ nhớ khi phải lưu trữ, tính toán giao các tập chỉ số giao dịch (tidset). Đồng thời, bài toán khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất (TRFWUIk) trên CSDL số lượng chưa được nghiên cứu giải quyết. Mặt khác, CSDL trong thực tế thường chứa mối quan hệ thứ bậc giữa các mục (cây phân cấp), nhưng các tiếp cận hiện nay chủ yếu dừng lại ở CSDL nhị phân và mắc hạn chế lớn khi phải chèn trực tiếp các mục cha vào từng giao dịch, dẫn đến việc bùng nổ dung lượng dữ liệu. Đến thời điểm tác giả thực hiện nghiên cứu, bài toán khai thác tập mục trên CSDL số lượng có sự phân cấp các mục (Hierarchical Quantitative Database - HQDB) vẫn chưa được quan tâm nghiên cứu.

Mục tiêu nghiên cứu của luận án được văn bản xác định cụ thể như sau:

1. Đối với các thuật toán hiện có trên CSDL số lượng: Nghiên cứu phương thức khai thác hiệu quả hơn bằng cách cải tiến theo hướng tiếp cận bit-vector nhằm tối ưu bộ nhớ và thời gian tính toán.
2. Phát triển khái niệm CSDL số lượng có sự phân cấp mục và đề xuất phương pháp khai thác mẫu trên CSDL số lượng có sự phân cấp mục.

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

• Đối tượng nghiên cứu: CSDL số lượng và CSDL số lượng có sự phân cấp mục.
• Phạm vi nghiên cứu: Phát triển các cấu trúc dữ liệu và thuật toán khai thác tập mục phổ biến ứng dụng trên CSDL số lượng và CSDL số lượng có sự phân cấp mục; kiểm thử thực nghiệm trên các bộ dữ liệu chuẩn trong khai thác dữ liệu.

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

Luận án điểm lại hệ thống các nghiên cứu nền tảng và chuyên sâu trong và ngoài nước liên quan đến bài toán khai thác tập mục:

1. Khai thác tập mục phổ biến trên CSDL nhị phân: Thuật toán đầu tiên được công bố bởi Agrawal và đồng sự (1993, 1994) với thuật toán Apriori dựa trên tính chất bao đóng giảm. Tiếp đó, Han và đồng sự (2000) đề xuất FP-Growth và Grahne cùng đồng sự phát triển FP-Growth* dựa trên việc nén CSDL vào cấu trúc cây FP-tree với 2 lần quét CSDL. Zaki (1997, 2000) đề xuất thuật toán Eclat dựa trên cấu trúc cây IT-tree (Itemset Tidset-tree) chuyển CSDL ngang thành CSDL dọc để khai thác với 1 lần đọc dữ liệu, cùng kỹ thuật diffset (dEclat). Tiếp cận lai ghép N-list kết hợp giữa FP-tree và dữ liệu dọc được nghiên cứu bởi Deng và các cộng sự (2012, 2014) nhằm giảm bộ nhớ nhưng chưa được mở rộng trên CSDL số lượng.
2. Khai thác tập mục trên CSDL số lượng và CSDL trọng số: Ramkumar và đồng sự (1998) giới thiệu bài toán FWI và thuật toán WIS. Tiếp cận FWI chia làm hai hướng: Hướng thứ nhất dựa trên hàm trung bình và chặn trên trọng số của Yun và đồng sự (2003), Yun & Leggett (2005) với thuật toán WSPAN, Lan và đồng sự (2014) với mô hình sequence-maximum-weight. Hướng thứ hai do Tao và đồng sự (2003) đề xuất dựa trên độ đo trọng số giao dịch (tw) và độ hỗ trợ trọng số (ws) theo tiếp cận Apriori. Sau đó, Vo và đồng sự (2012) đề xuất cấu trúc WIT-tree dựa trên tiếp cận Eclat. Đối với bài toán FWUI, Khan và đồng sự (2008) đưa ra khái niệm trọng số hữu ích của giao dịch (twu) và độ hỗ trợ trọng số hữu ích (wus); Vo và đồng sự (2013) phát triển cấu trúc MWIT-tree.
3. Khai thác k nhóm tập mục phổ biến có thứ hạng cao nhất (Top-rank-k): Deng (2007) giới thiệu bài toán TRFIk với thuật toán FAE; Fang và đồng sự (2009) đề xuất thuật toán VTK; Deng (2014) phát triển thuật toán NTK dựa trên PPC-tree và N-list; Le và đồng sự (2015) đề xuất thuật toán iNTK sử dụng kỹ thuật subsume. Các nghiên cứu này mới giới hạn trên CSDL nhị phân.
4. Khai thác trên CSDL có sự phân cấp: Han và đồng sự (1995) khởi xướng bài toán trên CSDL phân cấp. Liu và đồng sự (1999) và Tseng cùng đồng sự (2005) đề xuất mô hình khai thác với nhiều ngưỡng hỗ trợ. Vo và đồng sự (2012) phát triển cấu trúc GIT-tree dựa trên Eclat nhưng việc chèn nút cha vào CSDL làm tăng đáng kể dung lượng lưu trữ.
5. Tiếp cận bit-vector: Luoie & Liu (1998), Dong & Han (2007), Song và đồng sự (2007) đề xuất cấu trúc BitTable. Vo và đồng sự (2012) đề xuất cấu trúc DBV (Dynamic Bit-Vector) loại bỏ các byte 0 ở hai đầu nhưng vẫn còn các byte 0 ở giữa.

Khoảng trống học thuật mà luận án lựa chọn giải quyết bao gồm: Khắc phục nhược điểm lãng phí bộ nhớ của DBV trên CSDL thưa; phát triển thuật toán khai thác TRFWUIk đầu tiên trên CSDL số lượng; và xây dựng mô hình thuật toán khai thác trên CSDL số lượng có sự phân cấp mục (HQDB) mà không cần chèn các mục cha vào CSDL.

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

Luận án sử dụng các khung lý thuyết, định nghĩa hình thức và độ đo toán học:

1. Cơ sở dữ liệu nhị phân: Bộ đôi $DB = (T, I)$ với tập giao dịch $T = {t_1, t_2, \dots, t_m}$ và tập mục $I = {i_1, i_2, \dots, i_n}$. Độ hỗ trợ của tập mục $X$: $$support(X) = \frac{|{t \in T \mid X \subseteq t}|}{m}$$
2. Cơ sở dữ liệu trọng số: Bộ ba $DB = (T, I, W)$ với $W = {w_1, w_2, \dots, w_n}$ là trọng số của các mục tương ứng. Trọng số giao dịch của $t_k$: $$tw(t_k) = \frac{\sum_{i=1}^p w_i}{p}$$ với $p$ là số lượng mục có mặt trong $t_k$. Độ hỗ trợ trọng số của tập mục $X$: $$ws(X) = \frac{\sum_{t \in t(X)} tw(t)}{\sum_{t \in T} tw(t)}$$
3. Cơ sở dữ liệu số lượng: Bộ ba $DB = (T, I, W)$ trong đó mỗi giao dịch $t_k = {q_1, q_2, \dots, q_n}$ với $q_j$ là số lượng của mục thứ $j$. Trọng số hữu ích của giao dịch $t_k$: $$twu(t_k) = \frac{\sum_{i=1}^n q_i \times w_i}{\sum_{i=1}^n q_i}$$ Độ hỗ trợ trọng số hữu ích của tập mục $X$: $$wus(X) = \frac{\sum_{t \in T(X)} twu(t)}{\sum_{t \in T} twu(t)}$$
4. CSDL có sự phân cấp các mục: Bổ sung cây phân cấp $T_r$ thể hiện mối quan hệ bao hàm giữa các mục khái quát (mục cha, thuộc tập $J$) và các mục cơ sở (mục lá, thuộc tập $I$).

Phương pháp nghiên cứu thực tế:

• Phương pháp hình thức hóa toán học và thuật toán: Thiết kế các cấu trúc dữ liệu dựa trên tiếp cận bit-vector, chứng minh tính chất đoạn con và phép giao các phân đoạn bit; thiết kế giải thuật duyệt cây theo chiều sâu kết hợp kỹ thuật cắt tỉa dựa trên tính chất bao đóng giảm.
• Phương pháp thực nghiệm: Cài đặt các thuật toán đề xuất và thuật toán đối sánh bằng ngôn ngữ lập trình, đo đạc thời gian thực thi (giây) và bộ nhớ tiêu thụ (megabyte) trên các tập dữ liệu thực tế và tập dữ liệu chuẩn mô phỏng (benchmark).

Nguồn dữ liệu thực nghiệm gồm các tập dữ liệu phổ biến trong nghiên cứu khai thác dữ liệu:

• CSDL thưa và trung bình: RETAIL, BMS-POS, CONNECT, ACCIDENTS.
• CSDL bán hàng thực tế có phân cấp: SALE-FACT-1997, SALE-FACT-1997+1998, SALE-FACT-SYNC.

Tên CSDL thực nghiệm	Đặc điểm / Kiểu dữ liệu	Phạm vi áp dụng kiểm thử
RETAIL	Dữ liệu giao dịch bán lẻ, cấu trúc thưa	Khai thác FWI, FWUI, TRFWUIk
BMS-POS	Dữ liệu giao dịch điểm bán hàng, thưa	Khai thác FWI, FWUI, TRFWUIk
CONNECT	Dữ liệu bàn cờ trò chơi, cấu trúc dày	Khai thác FWI, FWUI, TRFWUIk
ACCIDENTS	Dữ liệu tai nạn giao thông, dày	Khai thác FWI, FWUI
SALE-FACT-1997	Dữ liệu bán hàng có cây phân cấp	Khai thác FWI, FWUI, HQDB
SALE-FACT-1997+1998	Dữ liệu bán hàng mở rộng hai năm	Khai thác FWI, FWUI, HQDB
SALE-FACT-SYNC	Dữ liệu bán hàng đồng bộ	Khai thác FWI, FWUI, HQDB

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

Chương 1: Tổng quan về khai thác tập mục

Chương này trình bày hệ thống lý thuyết về bài toán khai thác tập mục phổ biến trên các loại CSDL khác nhau và phân tích ưu, nhược điểm của các giải thuật nền tảng:

• Phân tích thuật toán Apriori trên CSDL ngang: Chỉ ra hạn chế phải quét toàn bộ CSDL nhiều lần để sinh tập ứng viên $L_k$ từ $L_{k-1}$, gây nghẽn hiệu năng khi dữ liệu có dung lượng lớn.
• Phân tích thuật toán FP-Growth: Sử dụng cấu trúc cây FP-tree để nén dữ liệu qua 2 lần quét CSDL. Hạn chế nằm ở chi phí thời gian duyệt các cây FP-tree điều kiện đối với các CSDL lớn hoặc phân bố thưa.
• Phân tích thuật toán Eclat dựa trên cấu trúc IT-tree: Chỉ cần một lần quét dữ liệu để chuyển sang định dạng dọc, kết nối các nút trong cùng lớp tương đương để sinh tập mục mới. Nhược điểm chính là việc lưu danh sách giao dịch (tidset) bằng các mảng số nguyên chiếm dụng dung lượng bộ nhớ lớn và làm chậm các phép toán tìm giao tidset.
• Tổng hợp các phương pháp trên CSDL trọng số (thuật toán của Tao, cấu trúc WIT-tree) và CSDL số lượng (thuật toán của Khan, cấu trúc MWIT-tree).
• Đánh giá tiếp cận bit-vector: Cấu trúc BitTable tốn $(\frac{|T|}{8} + 1)$ byte cho mỗi tập mục và chứa nhiều byte giá trị 0. Cấu trúc DBV của Vo chỉ cắt bỏ byte 0 ở hai đầu, vẫn để lại các byte 0 ở giữa dải biểu diễn, đồng thời xử lý ở cấp độ đơn vị byte (8 bit) nên chưa khai thác được ưu thế xử lý số nguyên lớn (word 16 bit, 32 bit, 64 bit) trên phần cứng hiện đại.

Chương 2: Khai thác tập mục phổ biến trên cơ sở dữ liệu số lượng

Chương 2 tập trung giải quyết bài toán tối ưu hóa bộ nhớ và thời gian tính toán trên CSDL số lượng và CSDL trọng số thông qua các cấu trúc dữ liệu mới:

1. Cấu trúc Interval Words Segment (IWS) cho khai thác FWI:

• Định nghĩa IWS: Biểu diễn tidset bằng danh sách các đoạn liên tiếp gồm các word (2 byte = 16 bit) khác 0, loại bỏ hoàn toàn các word bằng 0 ở cả hai đầu lẫn ở giữa. Mỗi đoạn gồm vị trí bắt đầu Start và mảng giá trị Word list.
• Phép toán giao hai đoạn IWS: Cho hai đoạn $S_x = s_x(u_0, u_1, \dots, u_k)$ và $S_y = s_y(v_0, v_1, \dots, v_l)$, đoạn giao $S_z = S_x \cap S_y$ được xác định với điểm bắt đầu $s_z = \max(s_x, s_y)$, độ dài $m = \min(k+s_x, l+s_y) - s_z$, và các phần tử $w_i = u_{i + s_z - s_x} \ & \ v_{i + s_z - s_y}$ (sử dụng phép toán AND bit).
• Tăng tốc tính toán bằng mảng MAP: Khai báo trước bảng MAP gồm 65.536 phần tử (tương ứng giá trị word 2 byte) để tra cứu trực tiếp vị trí các bit 1, giúp tính nhanh tổng giá trị $tw$ của các giao dịch mà không phải duyệt từng bit.
• Xây dựng cấu trúc IWS-tree kết hợp kỹ thuật cắt tỉa theo ngưỡng $minws$.

2. Cấu trúc Multi Bits Segment (MBiS) cho khai thác FWUI:

• Định nghĩa MBiS: Chỉ lưu trữ các đoạn bit 1 liên tiếp trên bit-vector. Mỗi đoạn được xác định bằng một cặp chỉ số: vị trí bit bắt đầu và vị trí bit kết thúc.
• Phép giao hai MBiS: Việc tìm giao hai phân đoạn bit 1 được thực hiện bằng cách lấy $\max$ của hai vị trí đầu đoạn và $\min$ của hai vị trí cuối đoạn, giảm thiểu tối đa các phép toán logic so với việc duyệt toàn bộ mảng bit.
• Xây dựng thuật toán khai thác FWUI dựa trên cây MBiS-tree với ngưỡng $minwus$.

3. Bài toán và thuật toán khai thác TRFWUIk:

• Đặt ra bài toán tìm $k$ nhóm tập mục phổ biến trọng số hữu ích có thứ hạng $wus$ cao nhất trên CSDL số lượng.
• Đề xuất hai cấu trúc lưu trữ động: Cấu trúc bảng động DTab (Dynamic Table) và cấu trúc heap động DHeap (Dynamic Heap) kết hợp cây TR-tree.
• DHeap duy trì ngưỡng cắt tỉa động: Ban đầu đặt ngưỡng bằng 0, khi DHeap đã chứa đủ $k$ mức hạng thì cập nhật ngưỡng bằng giá trị $wus$ nhỏ nhất trong heap; các ứng viên mới sinh ra chỉ được đưa vào heap nếu có độ hỗ trợ lớn hơn ngưỡng này.

Cấu trúc dữ liệu	Đơn vị lưu trữ cơ bản	Cách xử lý phần tử 0	Cơ chế tính giao / cập nhật
DBV (nghiên cứu trước)	Byte (8 bit)	Bỏ byte 0 ở đầu và cuối	Phép AND từng byte trong phạm vi
IWS (luận án)	Word (16 bit / 2 byte)	Bỏ toàn bộ word 0 (cả ở giữa)	AND các word trùng vị trí + mảng MAP
MBiS (luận án)	Đoạn bit 1 liên tiếp	Loại bỏ toàn bộ bit 0	Xác định $\max$ đầu đoạn và $\min$ cuối đoạn
DTab / DHeap (luận án)	Bảng / Heap động	Cập nhật ngưỡng $wus$ thứ hạng $k$	Quản lý cây TR-tree lọc top-k

Chương 3: Khai thác tập mục phổ biến trên cơ sở dữ liệu số lượng có sự phân cấp các mục

Chương 3 xây dựng mô hình khai thác trên CSDL số lượng có phân cấp các mục (HQDB) và các giải pháp nâng cao hiệu quả tính toán:

• Xác định trọng số cho các mục cha: Trọng số của mục cha trên cây phân cấp được tính bằng trung bình cộng trọng số của các mục con trực tiếp thuộc về nó.
• Thuật toán tiếp cận cơ bản: Bổ sung các mục cha vào từng giao dịch có chứa mục con tương ứng, sau đó áp dụng cấu trúc HIT-tree (Hierarchical Itemset Tidset-tree) để khai thác FWUI. Luận án chỉ ra cách làm này làm tăng kích thước CSDL và tiêu tốn bộ nhớ.
• Đề xuất cải tiến kỹ thuật:
  1. Cấu trúc EDBV (Extended Dynamic Bit-Vector): Biểu diễn tidset bằng các số nguyên lớn 8 byte (Large Integer - LI), tận dụng các lệnh thao tác bit 64-bit của CPU.
  2. Tính tidset nút cha từ tidset nút con: Thay vì chèn mục cha vào CSDL ban đầu, tidset của nút cha được suy dẫn trực tiếp bằng phép hợp logic (phép OR bit) trên tidset của các nút con của nó: $$tidset(P) = \bigcup_{C \in Children(P)} tidset(C)$$
  3. Kiểm tra mối quan hệ cha con: Loại bỏ ngay trong quá trình sinh ứng viên các tập mục chứa đồng thời cả mục cha và mục con (ví dụ: tập mục chứa đồng thời Printer và Laser Printer) nhằm đảm bảo tính độc lập ngữ nghĩa và giảm không gian tìm kiếm.
  4. Thuật toán khai thác nhanh FWUI trên HQDB: Tách các số nguyên lớn thành các đoạn 2 byte bằng các phép toán AND và dịch bit, sau đó kết hợp bảng tra cứu MAP để tính toán giá trị $wus$ với tốc độ cao.

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

Luận án tự tổng kết các kết quả và đóng góp mới về mặt lý luận cũng như thực tiễn như sau:

1. Đóng góp về cấu trúc dữ liệu và giải thuật trên CSDL số lượng:

• Đề xuất cấu trúc IWS và thuật toán khai thác FWI tương ứng, giải quyết triệt để tình trạng lãng phí bộ nhớ do các khối giá trị 0 nằm xen kẽ trong cấu trúc DBV; kết hợp mảng MAP để tối ưu hóa thời gian tính toán độ hỗ trợ trọng số $ws$.
• Đề xuất cấu trúc MBiS và giải thuật khai thác FWUI trên MBiS-tree, giảm thiểu khối lượng bộ nhớ lưu trữ tidset trên các CSDL thưa và tăng tốc độ tính giao tập mục.
• Khởi xướng bài toán và xây dựng thuật toán khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất (TRFWUIk) trên CSDL số lượng, triển khai qua hai cấu trúc quản lý ngưỡng động DTab và DHeap.

2. Đóng góp về mô hình và giải thuật trên CSDL số lượng có sự phân cấp mục:

• Định nghĩa hoàn chỉnh mô hình CSDL số lượng có sự phân cấp mục (HQDB).
• Đề xuất giải pháp xác định tidset của mục cha trực tiếp từ tidset của các mục con thông qua các phép toán bit, loại bỏ hoàn toàn thao tác thêm mục cha vào CSDL thô, ngăn chặn sự gia tăng dung lượng CSDL.
• Đề xuất cấu trúc EDBV dựa trên số nguyên lớn 8 byte và giải thuật kiểm tra quan hệ phân cấp, cho phép khai thác nhanh các tập FWUI trên CSDL phân cấp mà không phát sinh tập mục dư thừa về mặt ngữ nghĩa.

Các kiến nghị và giải pháp ứng dụng:

• Áp dụng các cấu trúc bit-vector cải tiến vào các hệ thống khai phá dữ liệu giao dịch thương mại, siêu thị và phân tích đơn thuốc, nơi dữ liệu mang đặc thù số lượng và có hệ thống phân cấp chủng loại mặt hàng.

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

Dựa trên nội dung được trình bày trong luận án, các hạn chế và hướng mở rộng nghiên cứu bao gồm:

• Phạm vi thuật toán: Các giải thuật đề xuất được thiết kế và thực thi tuần tự trên một máy đơn lẻ; văn bản chưa mở rộng sang môi trường xử lý tính toán song song, phân tán hoặc mô hình tính toán trên dữ liệu lớn (Big Data).
• Dạng dữ liệu nghiên cứu: Các thuật toán tập trung vào dữ liệu giao dịch tĩnh có sẵn cấu trúc bảng và cây phân cấp tường minh; chưa khảo sát trên các dòng dữ liệu biến đổi liên tục (data streams) hoặc dữ liệu có cấu trúc đồ thị phức tạp.
• Hướng nghiên cứu tiếp theo: Tiếp tục mở rộng các cấu trúc IWS, MBiS, EDBV để khai thác luật kết hợp có trọng số hữu ích; nghiên cứu thuật toán khai thác các tập mục đóng (closed itemsets) hoặc tập mục cực đại (maximal itemsets) trên CSDL số lượng có phân cấp nhằm thu gọn tập kết quả đầu ra.

Giá trị tham khảo

Luận án cung cấp giá trị tài liệu học thuật cho các nhóm đối tượng:

• Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Cơ sở toán cho tin học và Hệ thống thông tin: Tham khảo mô hình toán học hóa các độ đo trọng số ($tw, ws, twu, wus$), phương pháp chứng minh tính chất bao đóng giảm và kỹ thuật xây dựng thuật toán duyệt cây dựa trên dữ liệu dọc.
• Giảng viên và nhà nghiên cứu khai phá dữ liệu: Sử dụng nội dung Chương 1 và Chương 2 làm tài liệu tham khảo chuyên khảo về tiến trình phát triển của các cấu trúc dữ liệu biểu diễn tidset (từ mảng danh sách, diffset, BitTable, DBV đến IWS và MBiS).
• Kỹ sư phát triển hệ thống và chuyên viên phân tích dữ liệu: Vận dụng giải pháp kỹ thuật tính tidset mục cha từ mục con của Chương 3 để giải quyết bài toán khai thác giỏ hàng (Market Basket Analysis) có phân tầng danh mục hàng hóa trong các hệ thống bán lẻ thực tế.

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

1. Luận án giải quyết hạn chế cụ thể nào của cấu trúc Dynamic Bit-Vector (DBV)?

Cấu trúc DBV trước đó chỉ loại bỏ các byte 0 ở hai đầu của bit-vector, do đó trên các CSDL thưa, bên trong DBV vẫn còn chứa rất nhiều byte 0 xen kẽ, gây lãng phí bộ nhớ và tốn thời gian tính toán. Cấu trúc IWS do luận án đề xuất đã chia bit-vector thành các đoạn 2 byte (word) và loại bỏ hoàn toàn tất cả các đoạn word có giá trị 0 ở cả hai đầu lẫn ở giữa, chỉ giữ lại các đoạn có giá trị khác 0 kèm theo vị trí bắt đầu của đoạn.

2. Sự khác biệt giữa hai độ đo FWI và FWUI trên CSDL số lượng là gì?

FWI (Frequent Weighted Itemsets) áp dụng cho CSDL trọng số, trong đó mỗi mục có một trọng số cố định và mỗi giao dịch chỉ quan tâm mục đó có mặt hay không; độ hỗ trợ trọng số ($ws$) phụ thuộc vào trọng số giao dịch ($tw$) tính bằng trung bình cộng trọng số các mục xuất hiện. FWUI (Frequent Weighted Utility Itemsets) áp dụng cho CSDL số lượng đầy đủ, kết hợp đồng thời cả số lượng của mục trong giao dịch ($q$) và trọng số/lợi ích của mục ($w$); độ đo $wus$ được tính dựa trên trọng số hữu ích của giao dịch ($twu$).

3. Tại sao việc thêm các mục cha vào CSDL phân cấp lại là một nhược điểm lớn trong các nghiên cứu trước?

Trong CSDL có sự phân cấp, nếu thêm trực tiếp các mục cha vào từng giao dịch chứa mục con, dung lượng CSDL sẽ tăng lên gấp nhiều lần tùy thuộc vào độ sâu và số lượng cây phân cấp (như ví dụ trong văn bản, số lượng mục trong các giao dịch tăng từ 11 mục lên 21 mục sau khi thêm mục cha). Điều này dẫn đến sự bùng nổ không gian lưu trữ và làm tăng chi phí thời gian quét dữ liệu cũng như tính toán giao tập mục.

4. Thuật toán của luận án xử lý việc tính tidset cho mục cha như thế nào để không phải sửa đổi CSDL gốc?

Thay vì chèn mục cha vào CSDL, thuật toán giữ nguyên CSDL ban đầu và xác định tidset của mục cha trực tiếp thông qua phép hợp logic (phép toán OR bit) trên tidset của toàn bộ các nút con của nó trên cây phân cấp. Cách tiếp cận này tận dụng cấu trúc bit-vector để tính toán nhanh trên bộ nhớ tạm mà không làm biến đổi cấu trúc dữ liệu thô.

5. Thuật toán khai thác TRFWUIk sử dụng cấu trúc nào để duy trì danh sách top-k tập mục?

Luận án đề xuất sử dụng cấu trúc bảng động DTab và heap động DHeap kết hợp với cây TR-tree. Cấu trúc DHeap quản lý $k$ mức hạng giá trị $wus$ lớn nhất; khi heap đã đủ $k$ mức, giá trị $wus$ nhỏ nhất trong heap sẽ đóng vai trò ngưỡng cắt tỉa động để loại bỏ ngay lập tức các ứng viên mới sinh ra có độ hỗ trợ thấp hơn mà không cần lưu trữ hay duyệt tiếp.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Duy Hàm đã hoàn thiện việc nghiên cứu bài toán khai thác tập mục phổ biến trên các dạng cơ sở dữ liệu số lượng và cơ sở dữ liệu số lượng có sự phân cấp mục. Bằng việc đề xuất các cấu trúc dữ liệu bit-vector mới gồm IWS, MBiS, EDBV kết hợp cùng các kỹ thuật tra cứu bảng MAP và tính toán nút cha không qua chèn dữ liệu thô, công trình đã giải quyết được các hạn chế về bộ nhớ và thời gian xử lý của các giải thuật truyền thống. Hệ thống thuật toán đề xuất cùng bài toán mở rộng TRFWUIk đã được kiểm chứng thực nghiệm trên nhiều bộ dữ liệu benchmark, thể hiện tính đúng đắn và hiệu quả tính toán theo đúng mục tiêu nghiên cứu đã đặt ra.

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

Chương 1: “Tổng quan về khai thác tập mục” trình bày các khái niệm về khai thác FI các phƣơng pháp khai thác FI, FWI, FWUI và TRFIk. Phân tích ƣu điểm và hạn chế của các phƣơng pháp này đồng thời đề xuất hƣớng nghiên cứu của luận án. 5 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng” trình bày một số cấu trúc dữ liệu mới để biểu diễn tidset của các tập mục, trên cơ sở đó đề xuất các phƣơng pháp hiệu quả để khai thác nhanh FWI, FWUI trên CSDL số lƣợng. Đồng thời, trong chƣơng này cũng đề xuất bài toán khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất (TRFWUIk) trên CSDL số lƣợng và thuật toán hiệu quả để giải quyết bài toán này với hai cấu trúc DTab và DHeap.

Chương 3: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng có sự phân cấp các mục” đề xuất thuật toán khai thác FWUI trên CSDL số lƣợng có sự phân cấp các mục. Chƣơng này trình bày một mở rộng của cấu trúc dữ liệu trong chƣơng 2 và một số đề xuất nhằm cải tiến thuật toán khai thác hiệu quả FWUI trên CSDL số lƣợng có sự phân cấp các mục. 6 LUAN VAN CHAT LUONG download : add [e-mail] CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC Chƣơng này trình bày các nghiên cứu liên quan đến khai thác tập mục phổ biến trên các loại CSDL nhƣ CSDL nhị phân, CSDL số lƣợng, CSDL có sự phân cấp các mục và khai thác k nhóm tập phổ biến có thứ hạng cao nhất (Top-rank-k) từ các nhóm nghiên cứu trong nƣớc và quốc tế.

Phần này cũng trình bày các phân tích về ƣu điểm và hạn chế của các phƣơng pháp khai thác tập mục phổ biến hiện có. Từ cơ sở đó luận án đề ra các thuật toán mới dựa trên các cấu trúc dữ liệu phù hợp hơn cho các bài toán này trong chƣơng 2 và 3 của luận án. Bài toán khai thác tập mục Mục đích của việc khai thác tập mục là để xác định nhóm các mục (item) có tần suất xuất hiện thỏa mãn một ngƣỡng nào đó của ngƣời sử dụng đƣa vào. Trong đó, bài toán khai thác tập mục phổ biến là một bài toán con của bài toán khai thác tập mục với việc khai thác các tập mục có tần suất xuất hiện nhiều trong CSDL.

Tần suất xuất hiện này thỏa mãn ngƣỡng do ngƣời sử dụng đƣa vào (đƣợc gọi là ngƣỡng phổ biến). Từ các FI khai thác đƣợc có thể sinh ra tập luật kết hợp nhằm khám phá mối quan hệ tiềm ẩn, hữu ích giữa các mục trong CSDL, phục vụ các yêu cầu xuất phát từ đòi hỏi của thực tế của ngƣời sử dụng. Có thể nói, từ khi đƣợc giới thiệu đến nay, đã có khá nhiều công trình nghiên cứu liên quan nhằm mục đích giải quyết tốt bài toán này. Hiện nay, bài toán khai thác tập mục đang đƣợc tiếp tục nghiên cứu để tìm ra các giải pháp hiệu quả hơn.

Nội dung chƣơng 1 sẽ trình bày một số định nghĩa và khái niệm liên quan đến bài toán khai thác tập mục trên một CSDL nhƣ CSDL nhị phân, CSDL có sự phân cấp các mục, CSDL số lƣợng và một biến thể của CSDL số lƣợng là CSDL trọng số. Đồng thời chƣơng 1 giới thiệu tổng quát một số tiếp cận chính cho bài toán khai thác tập mục trên các loại CSDL đó. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Một số khái niệm cơ bản Định nghĩa 1.

CSDL nhị phân (binary database) là một bộ gồm hai thành phần: T, I trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL Với giao dịch thứ k (k = 1.m): ={ } trong đó 0 hoặc 1, với j = Ví dụ 1.1: Cho CSDL DB với tập các mục I = {A, B, C, D, E} và tập các giao dịch T đƣợc biểu diễn bởi Bảng 1.1 nhƣ sau: Bảng 1. Các giao dịch của CSDL nhị phân DB Mục A B C D E Giao dịch t1 1 1 0 1 1 t2 0 1 1 1 0 t3 1 1 0 1 1 t4 1 1 1 0 1 t5 1 1 1 1 1 t6 0 1 1 0 1 Các mục xuất hiện trong một giao dịch của CSDL tƣơng ứng có giá trị 1, ngƣợc lại có giá trị 0. Ví dụ giao dịch t1 = {1, 1, 0, 1, 1} có nghĩa các mục A, B, D, E có trong giao dịch, mục C không có trong giao dịch. CSDL nhị phân là CSDL biểu diễn sự xuất hiện hay không của các mục trong các giao dịch.

Trong nhiều trƣờng hợp, các mục trong CSDL có mối quan hệ với nhau đƣợc thể hiện qua các cây phân cấp, ví dụ "computer" là mức khái quát của "Desktop" và "Notebook", hay "Printer" là mức khái quát 8 LUAN VAN CHAT LUONG download : add [e-mail] của "Laser priter", "Ink-Jet printer", v.v… Những CSDL có thể hiện mối quan hệ của các mục thông qua cây phân cấp nhƣ trên đƣợc gọi là CSDL nhị phân có sự phân cấp các mục. CSDL nhị phân có sự phân cấp các mục (hierarchical database) là một bộ gồm ba thành phần: T, I, Tr, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL Với giao dịch thứ k (k = 1.m): ={ } trong đó 0 hoặc 1, với j = 1. Tr là cây phân cấp thể hiện mối quan hệ của các mục trong CSDL. Cho CSDL nhị phân có sự phân cấp mục DB với tập các mục I = {Desktop, Dot-matrix printer, Ink-jet printer, Laser printer, Notebook, Scanner}, các giao dịch T đƣợc biểu diễn nhƣ Bảng 1.2 và cây phân cấp thể hiện quan hệ các mục nhƣ Hình 1.

Các giao dịch của CSDL nhị phân có sự phân cấp mục DB Giao dịch Mục t1 Notebook, Laser printer t2 Scanner, Dot-matrix printer t3 Dot-matrix printer, Ink-jet printer t4 Notebook, Dot-matrix printer, Laser printer t5 Scanner t6 Desktop 9 LUAN VAN CHAT LUONG download : add [e-mail] Printer Computer Scanner Non – impact Dot – matrix Desktop Notebook Laser Ink – jet Hình 1. Cây phân cấp Tr Để đơn giản, ta gán các mục trên cây phân cấp Tr bằng các ID nhƣ Bảng 1. ID các mục của DB ID mục Tên mục A Desktop B Ink-jet Printer C Laser Printer D Notebook E Scanner F Dot-matrix Printer G Non-impact H Computer K Printer Từ ID đƣợc định nghĩa trong Bảng 1.3, các giao dịch trong Bảng 1.2 và cây phân cấp Tr đƣợc biểu diễn lại nhƣ trong Bảng 1. Các giao dịch của DB bằng ID Giao dịch mục t1 D, C t2 E, F t3 F, B t4 D, F, C t5 E t6 A 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Cây phân cấp Tr biểu diễn theo ID Tập J = {G, K, H} là tập các mục cha của cây phân cấp không xuất hiện trong các giao dịch của DB. Tuy nhiên chúng có vai trò nhất định, thể hiện mối quan hệ của các mục trong DB. Do đó, khi khai thác FI trên CSDL phân cấp đòi hỏi phải khai thác cả tập các mục trên cây phân cấp bao gồm (I J). CSDL nhị phân là CSDL thể hiện sự có mặt hay không của mục trong các giao dịch của CSDL mà không quan tâm đến giá trị (trọng số, lợi ích, số lƣợng, v.v…) của các mục trong các giao dịch.

Trong nhiều ứng dụng thực tế nhƣ CSDL bán hàng trong siêu thị, CSDL đơn thuốc, v.v… mỗi mục trên mỗi đơn hàng thƣờng kèm theo số lƣợng và giá trị của chúng. Các CSDL dạng này đƣợc gọi là CSDL số lƣợng. CSDL số lượng (quantitative database) là một bộ ba thành phần: T, I, W, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong tập I Với giao dịch thứ k (k = 1.m): tk = { , , …, }, là số tự nhiên chỉ số lƣợng của mục thứ j trong giao dịch, j = 1.2: Cho CSDL số lƣợng DB với tập các mục I = {A, B, C, D, E}, các giao dịch T đƣợc biểu diễn trong Bảng 1.5, trọng số các mục nhƣ trong bảng 1. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Giao dịch của CSDL số lƣợng BD Giao dịch A B C D E 1 1 0 4 1 0 1 3 0 1 2 1 0 3 2 3 1 1 0 1 1 2 2 1 3 0 1 1 1 0 Bảng 1. Trọng số các mục trong DB Mục Trọng số A 0,6 B 0,1 C 0,3 D 0,9 E 0,2 Theo Bảng 1.5, DB có sáu giao dịch {t1, t2, t3, t4, t5, t6}, ví dụ giao dịch = {1, 1, 0, 4, 1} có nghĩa là trong giao dịch có một mục A, một mục B, bốn mục D, một mục E, không có mục C. Trong nhiều ứng dựng thực tế, CSDL số lƣợng có thể không quan tâm đến số lƣợng của các mục trong mỗi giao dịch, mà chỉ quan tâm đến trọng số của chúng. Ví dụ CSDL vi phạm giao thông, ngƣời ta chỉ quan tâm là ngƣời vi phạm lỗi gì và mức tiền phạt tƣơng ứng cho từng lỗi ấy, hay CSDL khám bệnh, ngƣời ta quan tâm đến bệnh nhân có những triệu chứng gì mức độ nặng nhẹ (trọng số) của từng triệu chứng ấy, v.v… Các CSDL đó đƣợc gọi là CSDL có trọng số hay CSDL trọng số - một biến thể của CSDL số lƣợng với số lƣợng của các mục xuất hiện trong CSDL là 1.

12 LUAN VAN CHAT LUONG download : add [e-mail] Định nghĩa 1. CSDL trọng số (weighted database) là một bộ gồm ba thành phần: T, I, W, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2,., in} là tập gồm n mục trong CSDL W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong tập I Ví dụ 1.3: Cho CSDL trọng số DB với tập mục I = {A, B, C, D, E}, các giao dịch đƣợc biểu diễn trong Bảng 1.7, trọng số các mục đƣợc thể hiện trong Bảng 1. Các giao dịch của CSDL trọng số DB Giao dịch Mục A, B, D, E B, C, E A, B, D, E A, B, C, E A, B, C, D, E B, C, D Bảng 1. Trọng số của các mục của DB mục Trọng số A 0,6 B 0,1 C 0,3 D 0,9 E 0,2 Định nghĩa 1.

Tidset của tập mục X là tập hợp các giao dịch chứa X.