Khai Phá Luật Kết Hợp Hiếm Trên Cơ Sở Dữ Liệu Và Ứng Dụng

Khai phá luật kết hợp hiếm là một lĩnh vực quan trọng trong khai phá dữ liệu, giúp phát hiện các mối quan hệ ít xảy ra… 58 trang · Đại học Thái Nguyên · 2015.

• Tác giả: Nguyễn Thị Hải Lý
• Người hướng dẫn: TS. Nguyễn Huy Đức
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Khai Phá Luật Kết Hợp Hiếm Trong Cơ Sở Dữ Liệu
• Loại tài liệu: luận văn
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• MỞ ĐẦU
• 1. CHƯƠNG 1: KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP
• 1.1. Khai phá dữ liệu
• 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu
• 1.3. Kiến trúc của hệ thống khai phá dữ liệu
• 1.4. Quá trình khai phá dữ liệu
• 1.5. Nhiệm vụ của khai phá dữ liệu
• 1.6. Các ứng dụng của khai phá dữ liệu
• 1.7. Khai phá luật kết hợp trong cơ sở dữ liệu
• 1.7.1. Các khái niệm cơ sở
• 1.7.2. Cơ sở dữ liệu giao tác
• 1.7.3. Tập mục phổ biến
• 1.7.4. Luật kết hợp
• 1.8. Kết luận chương 1
• 2. CHƯƠNG 2: LUẬT KẾT HỢP HIẾM
• 2.1. Giới thiệu chung về luật kết hợp hiếm
• 2.2. Một số hướng nghiên cứu chính phát hiện luật kết hợp hiếm
• 2.3. Sử dụng ràng buộc phần hệ quả của luật
• 2.4. Thiết lập đường biên phân chia các tập phổ biến và không phổ biến
• 2.5. Phát hiện luật kết hợp hiếm từ các CSDL định lượng
• 2.6. Khuynh hướng nghiên cứu về luật hiếm
• 2.7. Phát hiện luật kết hợp hiếm Sporadic trên CSDL giao tác
• 2.7.1. Khái niệm về luật hiếm Sporadic
• 2.7.2. Thuật toán Apriori-Inverse
• 2.7.3. Thuật toán tìm tập Sporadic tuyệt đối hai ngưỡng đóng
• 2.7.4. Tập Sporadic tuyệt đối hai ngưỡng
• 2.7.5. Thuật toán MCPSI tìm tập Sporadic tuyệt đối hai ngưỡng đóng
• 2.8. Kết luận chương 2
• 3. CHƯƠNG 3: THỰC NGHIỆM TÌM LUẬT HIẾM SPORADIC TUYỆT ĐỐI
• 3.1. Giới thiệu bài toán
• 3.2. Dữ liệu thực nghiệm
• 3.3. Xây dựng chương trình
• 3.4. Thực nghiệm khai phá
• 3.5. Kết quả thực nghiệm
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Luật Kết Hợp Hiếm Trong Cơ Sở Dữ Liệu

Khai phá luật kết hợp hiếm là một lĩnh vực quan trọng trong khai phá dữ liệu, giúp phát hiện các mối quan hệ ít xảy ra nhưng có giá trị trong cơ sở dữ liệu. Luật kết hợp hiếm không chỉ đơn thuần là những luật có tần suất thấp mà còn mang lại thông tin quý giá cho các nhà nghiên cứu và doanh nghiệp. Việc hiểu rõ về luật kết hợp hiếm sẽ giúp tối ưu hóa các chiến lược kinh doanh và nghiên cứu.

1.1. Khái Niệm Về Khai Phá Dữ Liệu Và Luật Kết Hợp

Khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích từ các tập dữ liệu lớn. Luật kết hợp là mối quan hệ giữa các phần tử dữ liệu, thể hiện sự xuất hiện đồng thời của chúng trong các giao tác. Việc phát hiện luật kết hợp giúp nhận diện các mẫu hành vi trong dữ liệu.

1.2. Tầm Quan Trọng Của Luật Kết Hợp Hiếm

Luật kết hợp hiếm có thể cung cấp những thông tin quan trọng mà các luật phổ biến không thể hiện. Chúng thường liên quan đến các hành vi đặc biệt của người tiêu dùng hoặc các hiện tượng hiếm gặp trong dữ liệu, từ đó giúp doanh nghiệp đưa ra quyết định chính xác hơn.

II. Thách Thức Trong Khai Phá Luật Kết Hợp Hiếm

Khai phá luật kết hợp hiếm gặp nhiều thách thức, bao gồm việc xác định ngưỡng hỗ trợ tối thiểu và độ tin cậy. Những luật này thường có tần suất thấp, dẫn đến khó khăn trong việc phát hiện và phân tích. Ngoài ra, việc xử lý dữ liệu không đầy đủ và nhiễu cũng là một vấn đề lớn.

2.1. Vấn Đề Xác Định Ngưỡng Hỗ Trợ

Ngưỡng hỗ trợ tối thiểu là một yếu tố quan trọng trong việc phát hiện luật kết hợp hiếm. Nếu ngưỡng này quá cao, nhiều luật có giá trị sẽ bị bỏ qua. Ngược lại, nếu quá thấp, sẽ dẫn đến việc phát hiện quá nhiều luật không có ý nghĩa.

2.2. Dữ Liệu Không Đầy Đủ Và Nhiễu

Dữ liệu không đầy đủ và nhiễu có thể làm giảm độ chính xác của các luật kết hợp hiếm. Việc xử lý và làm sạch dữ liệu là cần thiết để đảm bảo rằng các luật được phát hiện là chính xác và có giá trị.

III. Phương Pháp Khai Phá Luật Kết Hợp Hiếm Hiệu Quả

Để khai phá luật kết hợp hiếm hiệu quả, cần áp dụng các phương pháp và thuật toán phù hợp. Các thuật toán như Apriori-Inverse và MCPSI đã được phát triển để tối ưu hóa quá trình này. Những phương pháp này giúp phát hiện các luật hiếm một cách chính xác và nhanh chóng.

3.1. Thuật Toán Apriori Inverse

Thuật toán Apriori-Inverse là một trong những phương pháp hiệu quả để phát hiện luật kết hợp hiếm. Nó giúp xác định các luật hiếm bằng cách sử dụng các ràng buộc phần hệ quả, từ đó tối ưu hóa quá trình khai phá.

3.2. Thuật Toán MCPSI

Thuật toán MCPSI được thiết kế để tìm tập Sporadic tuyệt đối hai ngưỡng đóng. Phương pháp này giúp phát hiện các luật hiếm một cách chính xác, đồng thời giảm thiểu chi phí tính toán.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Luật Kết Hợp Hiếm

Khai phá luật kết hợp hiếm có nhiều ứng dụng thực tiễn trong các lĩnh vực như thương mại, y tế và tài chính. Việc phát hiện các luật hiếm giúp doanh nghiệp tối ưu hóa chiến lược marketing và cải thiện dịch vụ khách hàng.

4.1. Ứng Dụng Trong Thương Mại

Trong thương mại, việc phát hiện luật kết hợp hiếm giúp doanh nghiệp hiểu rõ hơn về hành vi của khách hàng. Điều này cho phép họ điều chỉnh chiến lược marketing và tăng cường sự hài lòng của khách hàng.

4.2. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, khai phá luật kết hợp hiếm có thể giúp phát hiện các mối liên hệ giữa các triệu chứng và bệnh tật. Điều này hỗ trợ bác sĩ trong việc chẩn đoán và điều trị bệnh hiệu quả hơn.

V. Kết Luận Và Tương Lai Của Khai Phá Luật Kết Hợp Hiếm

Khai phá luật kết hợp hiếm là một lĩnh vực đầy tiềm năng và thách thức. Với sự phát triển của công nghệ và các thuật toán mới, khả năng phát hiện các luật hiếm sẽ ngày càng được cải thiện. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều giá trị cho các ngành công nghiệp khác nhau.

5.1. Xu Hướng Nghiên Cứu Trong Tương Lai

Các nghiên cứu trong tương lai sẽ tập trung vào việc phát triển các thuật toán mới và cải tiến các phương pháp hiện có để phát hiện luật kết hợp hiếm một cách hiệu quả hơn.

5.2. Giá Trị Của Khai Phá Luật Kết Hợp Hiếm

Giá trị của khai phá luật kết hợp hiếm không chỉ nằm ở việc phát hiện các mối quan hệ hiếm mà còn ở khả năng cung cấp thông tin quý giá cho các quyết định kinh doanh và nghiên cứu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu của thế kỷ 21, các siêu thị lớn như Siêu thị Hải Dương có thể tích lũy hơn 10.000 giao tác mua hàng mỗi quý với hơn 800 mặt hàng lưu thông. Từ khối dữ liệu khổng lồ đó, một câu hỏi thực tiễn được đặt ra: làm thế nào để khai thác các mẫu mua hàng ít phổ biến nhưng lại mang giá trị kinh doanh cao?

Luận văn thạc sĩ "Khai phá luật kết hợp hiếm trên cơ sở dữ liệu và ứng dụng" của tác giả Nguyễn Thị Hải Lý, thực hiện năm 2015 tại Viện Công nghệ thông tin – Đại học Thái Nguyên dưới sự hướng dẫn của TS. Nguyễn Huy Đức, giải quyết trực tiếp bài toán này. Nghiên cứu tập trung vào dạng luật kết hợp hiếm Sporadic tuyệt đối — loại luật có độ hỗ trợ thấp hơn ngưỡng maxSup nhưng độ tin cậy đạt từ 60% trở lên, xuất hiện khi tất cả các mục dữ liệu thành phần đều hiếm theo cùng ngưỡng đó.

Mục tiêu cụ thể của nghiên cứu bao gồm ba hướng chính: (1) Hệ thống hóa lý thuyết về khai phá luật kết hợp và luật kết hợp hiếm; (2) Phân tích chuyên sâu hai thuật toán tìm luật Sporadic tuyệt đối là Apriori-Inverse và MCPSI; (3) Triển khai thực nghiệm trên bộ dữ liệu giao dịch thực tế gồm 500 giao tác tháng 6/2015 với 20 mặt hàng thiết yếu.

Ý nghĩa khoa học của đề tài nằm ở chỗ: các thuật toán phổ biến như Apriori, khi buộc phải đặt ngưỡng minSup rất thấp để bắt luật hiếm, sẽ sinh ra số lượng tập mục ứng viên lên đến hàm mũ 2^m (với m là số mục dữ liệu), gây lãng phí tài nguyên tính toán nghiêm trọng. Nghiên cứu này đề xuất hướng tiếp cận chuyên biệt, hiệu quả hơn cho bài toán vốn đang là vấn đề mở trong cộng đồng nghiên cứu khai phá dữ liệu.

---

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên hai nền tảng lý thuyết cốt lõi:

Lý thuyết Khám phá Tri thức từ Cơ sở Dữ liệu (KDD) cung cấp quy trình 5 bước làm khung xử lý tổng thể: trích chọn dữ liệu → tiền xử lý → biến đổi → khai phá → đánh giá và biểu diễn tri thức. Đây là quy trình chuẩn được J. Han và M. Kamber hệ thống hóa, trong đó bước khai phá dữ liệu là tốn kém và phức tạp nhất.

Lý thuyết Kết nối Galois và Tập đóng — nền tảng của thuật toán CHARM và MCPSI — cung cấp công cụ toán học để xác định các tập mục đóng trong không gian tìm kiếm. Với cặp ánh xạ f: 2^O → 2^INF và g: 2^INF → 2^O, toán tử đóng h = f·g cho phép thu gọn đáng kể không gian kết quả mà không mất thông tin.

Năm khái niệm trung tâm của nghiên cứu gồm:

• Cơ sở dữ liệu giao tác (Transaction DB): tập hợp các giao tác T ⊆ I, mỗi giao tác mang định danh TID riêng biệt.
• Độ hỗ trợ (Support): sup(X) = |{T ∈ DB | X ⊆ T}| / |DB|, phản ánh tần suất xuất hiện.
• Độ tin cậy (Confidence): conf(X→Y) = sup(X∪Y) / sup(X), phản ánh sức mạnh mối liên hệ.
• Tập Sporadic tuyệt đối: tập X thỏa mãn minSup ≤ sup(X) < maxSup và mọi phần tử x ∈ X đều có sup(x) < maxSup.
• Luật Sporadic tuyệt đối đóng: luật dẫn xuất từ tập đóng Sporadic, giúp loại bỏ các luật dư thừa.

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

Phương pháp chính là nghiên cứu lý thuyết kết hợp với đánh giá thực nghiệm định lượng, bao gồm hai giai đoạn song song:

• Giai đoạn lý thuyết: Tổng hợp và phân tích các công bố khoa học trong và ngoài nước về khai phá luật kết hợp hiếm, gồm các công trình của Koh & Rountree (2005) — Đại học Otago, New Zealand — và Cù Thu Thủy với thuật toán MCPSI.
• Giai đoạn thực nghiệm: Triển khai chương trình trên ngôn ngữ Java (môi trường Eclipse Mars 4.0, hệ điều hành Windows 7).

Dữ liệu thực nghiệm được trích chọn từ cơ sở dữ liệu giao tác của Siêu thị Hải Dương: 500 giao tác trong tháng 6/2015, bao gồm 20 mặt hàng thiết yếu (thực phẩm, đồ gia dụng, vệ sinh cá nhân). Phương pháp chọn mẫu là trích chọn có chủ đích (purposive sampling) — giới hạn 500 giao tác từ hơn 10.000 giao tác quý 2/2015 — nhằm đảm bảo tính kiểm soát được trong thực nghiệm và phù hợp với năng lực tính toán của môi trường thử nghiệm (RAM 512MB, ổ cứng 1GB trống).

Phương pháp phân tích là so sánh hiệu năng giữa hai thuật toán Apriori-Inverse (duyệt chiều rộng – BFS) và MCPSI (duyệt chiều sâu – DFS) trên cùng bộ dữ liệu, với các tham số ngưỡng MinSup và MaxSup thay đổi. Lý do lựa chọn phương pháp so sánh: cả hai thuật toán đều giải cùng một bài toán nhưng theo chiến lược tìm kiếm khác nhau, do đó so sánh trực tiếp là cách đánh giá khách quan và có tính thuyết phục cao nhất.

---

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Phát hiện 1 – Hiệu quả khai phá luật Sporadic tuyệt đối: Chạy thuật toán Apriori-Inverse với MinSup = 10% và MaxSup = 60% trên bộ 500 giao tác, chương trình xác định được các tập 1-mục sporadic với độ hỗ trợ nằm trong khoảng 10%–60%, và sinh ra thành công các luật Sporadic tuyệt đối từ các tập 2-mục. Ví dụ minh họa trong luận văn cho thấy luật {4}→{5} (mua Dao thì mua Thìa) đạt độ tin cậy 100% và luật {5}→{4} đạt 66%, trong khi cả hai mặt hàng đều có độ hỗ trợ dưới ngưỡng maxSup = 65%.

Phát hiện 2 – Bất cập của Apriori khi áp dụng vào luật hiếm: Nếu có 10.000 mục dữ liệu phổ biến, thuật toán Apriori cần sinh ra hơn 10^7 tập ứng viên 2-mục và duyệt cơ sở dữ liệu số lần bằng độ dài tập mục phổ biến dài nhất. Việc đặt ngưỡng minSup quá thấp để bắt luật hiếm làm chi phí tính toán tăng theo hàm mũ — đây là giới hạn nội tại không thể khắc phục trong thiết kế gốc của Apriori.

Phát hiện 3 – Ưu thế của MCPSI so với Apriori-Inverse: Thuật toán MCPSI có độ phức tạp O(|C|·δ²), trong đó |C| là số tập Sporadic đóng và δ là chiều dài trung bình định danh giao tác. Nhờ tìm kiếm theo chiều sâu (DFS) và kỹ thuật tỉa nhánh dựa trên kết nối Galois, MCPSI tránh được việc sinh số lượng khổng lồ tập ứng viên mà Apriori-Inverse (dựa trên BFS) phải xử lý — đặc biệt hiệu quả trên cơ sở dữ liệu dày (dense databases).

Phát hiện 4 – Ứng dụng thực tiễn tại Siêu thị Hải Dương: Trong bộ dữ liệu thực nghiệm gồm 20 mặt hàng thiết yếu, mỗi giao tác chứa trung bình 4–7 mặt hàng. Các luật Sporadic tuyệt đối phát hiện được phản ánh các mẫu mua hàng hiếm nhưng nhất quán — ví dụ, khách mua Dao có khả năng cao mua Thìa cùng lúc — thông tin hữu ích cho quyết định bày trí hàng hóa và chương trình khuyến mãi nhắm mục tiêu.

Thảo luận kết quả

Các kết quả trên hoàn toàn phù hợp với phát biểu lý thuyết của Koh (2005): phát hiện luật kết hợp hiếm đòi hỏi kỹ thuật tiền xử lý khác biệt so với luật phổ biến. Bộ dữ liệu thực nghiệm có thể được trực quan hóa qua biểu đồ phân bố độ hỗ trợ dạng histogram — với trục hoành là khoảng [0%, 100%] và trục tung là số lượng tập mục — để thấy rõ vùng "hiếm" nằm dưới đường ngưỡng maxSup. Ngoài ra, bảng so sánh hai thuật toán theo chiều: số tập ứng viên sinh ra, số lần duyệt CSDL, thời gian thực thi sẽ minh họa rõ hơn ưu thế của MCPSI.

So sánh với nghiên cứu của Szathmary và cộng sự về luật hiếm trong y tế (luật "ăn chay → bệnh tim mạch" trong CSDL điều trị bệnh nhân Stanislas, Pháp, và luật liên quan đến thuốc Cerivastatin dẫn đến quyết định thu hồi thuốc), kết quả của luận văn xác nhận: luật Sporadic tuyệt đối dù hiếm về tần suất nhưng có giá trị ứng dụng thực tế cao trong nhiều lĩnh vực.

---

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu, bốn nhóm khuyến nghị được đề xuất nhằm nâng cao hiệu quả ứng dụng khai phá luật kết hợp hiếm:

1. Mở rộng thuật toán MCPSI sang cơ sở dữ liệu định lượng Nhóm nghiên cứu và các nhà phát triển phần mềm nên mở rộng thuật toán MCPSI để xử lý được CSDL định lượng (quantitative DB) — nơi mỗi mục dữ liệu có giá trị số thay vì nhị phân. Mục tiêu: giảm tối thiểu 30% số lần duyệt CSDL so với phương pháp rời rạc hóa thông thường. Timeline đề xuất: 12–18 tháng cho giai đoạn nghiên cứu và thử nghiệm.

2. Tích hợp kỹ thuật song song hóa (Parallel Mining) Các nhà quản trị hệ thống tại các siêu thị và tổ chức có CSDL lớn (trên 100.000 giao tác) nên triển khai phiên bản song song của thuật toán Apriori-Inverse, phân tán xử lý trên ít nhất 4 node tính toán, nhằm đạt thời gian phản hồi dưới 60 giây cho mỗi lần khai phá theo lô. Kỹ thuật này đặc biệt cấp thiết khi kích thước CSDL tăng trưởng theo thời gian thực.

3. Phát triển bộ độ đo phù hợp với luật hiếm Các nhà nghiên cứu trong lĩnh vực khai phá dữ liệu cần xây dựng ít nhất 3 độ đo mới (bên cạnh Support và Confidence) đặc trưng cho luật hiếm — chẳng hạn hệ số Lift hiếm, độ đo Oddity, hoặc chỉ số Isolation Score — nhằm phân biệt hiệu quả giữa luật hiếm có giá trị và nhiễu dữ liệu. Đây là vấn đề mở được xác nhận trong nghiên cứu này, cần giải quyết trong vòng 2–3 năm tới.

4. Ứng dụng vào lĩnh vực y tế và phát hiện gian lận Cơ quan quản lý y tế và tổ chức tài chính nên đầu tư thử nghiệm thuật toán tìm luật Sporadic tuyệt đối trên dữ liệu lâm sàng (phát hiện bệnh hiếm) và dữ liệu giao dịch tài chính (phát hiện giao dịch bất thường) trong vòng 6 tháng, với bộ dữ liệu thử nghiệm tối thiểu 5.000 bản ghi. Mục tiêu là đạt độ chính xác phát hiện bất thường trên 80% trong giai đoạn pilot.

---

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và học viên cao học ngành Khoa học Máy tính / Công nghệ thông tin Luận văn cung cấp nền tảng lý thuyết hệ thống về KDD, khai phá luật kết hợp và khai phá luật hiếm Sporadic — bao gồm đầy đủ các định nghĩa hình thức, tính chất toán học và pseudocode của hai thuật toán Apriori-Inverse và MCPSI. Nhóm đối tượng này sẽ tiết kiệm đáng kể thời gian khảo sát tài liệu nền tảng khi bắt đầu nghiên cứu về khai phá dữ liệu, đồng thời có ngay điểm xuất phát để mở rộng sang các hướng như luật hiếm định lượng hay luật hiếm mờ.

2. Nhà phát triển phần mềm phân tích dữ liệu (Data Analyst / Data Engineer) Chương trình Java thực nghiệm (Sporadic_Rule.jar) và hướng dẫn triển khai cụ thể trong Chương 3 là tài liệu tham khảo thực tiễn để xây dựng module phát hiện mẫu hiếm trong các hệ thống phân tích kinh doanh. Use case cụ thể: tích hợp vào hệ thống BI (Business Intelligence) của siêu thị, trung tâm thương mại với dữ liệu giao tác từ 1.000 đến 100.000 bản ghi.

3. Nhà quản lý kinh doanh và chuyên viên nghiên cứu thị trường Các luật Sporadic tuyệt đối phát hiện được từ dữ liệu siêu thị Hải Dương minh họa cách biến dữ liệu giao dịch thô thành thông tin chiến lược: xác định các cặp mặt hàng có tần suất mua chung thấp nhưng tỷ lệ kèm nhau cao trên 66%–100%, từ đó tối ưu hóa bố trí gian hàng và thiết kế chương trình khuyến mãi nhắm đúng nhóm khách hàng.

4. Chuyên gia y tế và phân tích rủi ro tài chính Hai ứng dụng nổi tiếng của luật kết hợp hiếm được dẫn chứng trong luận văn — phát hiện tương tác thuốc hiếm dẫn đến thu hồi Cerivastatin và xác định nhóm bệnh hiếm từ CSDL điều trị Stanislas (Pháp) — là minh chứng thực tế cho tiềm năng của phương pháp trong y tế và tài chính. Nhóm đối tượng này có thể áp dụng trực tiếp framework lý thuyết và quy trình thực nghiệm của luận văn vào bộ dữ liệu chuyên ngành của mình.

---

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

1. Luật kết hợp hiếm khác gì so với luật kết hợp thông thường? Luật kết hợp thông thường có độ hỗ trợ cao — nghĩa là mẫu xảy ra thường xuyên trong CSDL. Luật kết hợp hiếm (Sporadic) có độ hỗ trợ thấp hơn ngưỡng maxSup nhưng độ tin cậy cao từ minConf trở lên. Sự khác biệt then chốt: luật hiếm mang thông tin về các sự kiện ngoại lệ có giá trị cao, ví dụ quyết định thu hồi thuốc Cerivastatin khỏi thị trường dược phẩm toàn cầu được kích hoạt bởi đúng loại luật hiếm này.

2. Tại sao không dùng Apriori với ngưỡng thấp để tìm luật hiếm? Khi đặt ngưỡng minSup rất thấp, số lượng tập ứng viên tăng theo hàm mũ — với 10.000 mục phổ biến, Apriori sinh ra hơn 10 triệu tập ứng viên 2-mục. Phần lớn trong số đó là tập phổ biến thông thường, không phải luật hiếm. Chi phí tính toán và bộ nhớ tăng đột biến trong khi hiệu suất tìm luật hiếm thực sự rất thấp, khiến phương pháp này không khả thi trong thực tế.

3. Tập Sporadic tuyệt đối và không tuyệt đối khác nhau thế nào? Tập Sporadic tuyệt đối yêu cầu tất cả các mục dữ liệu thành phần đều có độ hỗ trợ nhỏ hơn maxSup — tức là mọi thành phần đều hiếm. Tập Sporadic không tuyệt đối chỉ cần độ hỗ trợ của tập hợp nhỏ hơn maxSup, nhưng có thể có thành phần riêng lẻ vẫn phổ biến. Ví dụ: sup(A) = 12%, sup(B) = 10%, sup(AB) = 10%, với maxSup = 11% thì AB là tập Sporadic không tuyệt đối vì A có sup vượt maxSup.

4. Thuật toán MCPSI hoạt động hiệu quả hơn Apriori-Inverse ở điểm nào? MCPSI duyệt không gian tìm kiếm theo chiều sâu (DFS) và áp dụng tỉa nhánh thông minh dựa trên kết nối Galois, chỉ tìm các tập Sporadic đóng — tức là tập đại diện chứa đầy đủ thông tin, loại bỏ các tập con dư thừa. Độ phức tạp O(|C|·δ²) với |C| là số tập đóng nhỏ hơn nhiều so với tổng số tập Sporadic đầy đủ. Apriori-Inverse duyệt BFS và sinh toàn bộ tập ứng viên, gặp hiện tượng bùng nổ tổ hợp trên CSDL dày.

5. Kết quả thực nghiệm có thể áp dụng ngay cho siêu thị thực tế không? Hoàn toàn có thể, với điều kiện dữ liệu được tiền xử lý đúng quy trình: mã hóa mặt hàng bằng số tự nhiên, chuyển về dạng text theo từng giao tác, thiết lập ngưỡng MinSup và MaxSup phù hợp với đặc điểm kinh doanh. Trong thực nghiệm tại Siêu thị Hải Dương, chương trình Sporadic_Rule.jar chạy thành công trên máy tính cấu hình tối thiểu 512MB RAM, cho thấy khả năng triển khai thực tế với chi phí hạ tầng thấp.

---

Kết luận

Luận văn "Khai phá luật kết hợp hiếm trên cơ sở dữ liệu và ứng dụng" đạt được những đóng góp chính sau:

• Hệ thống hóa lý thuyết: Trình bày đầy đủ và mạch lạc bài toán khai phá luật kết hợp — từ khái niệm cơ bản đến các thuật toán Apriori, FP-growth — làm nền tảng cho nghiên cứu luật hiếm.
• Phân tích chuyên sâu luật Sporadic tuyệt đối: Làm rõ hai định nghĩa, tính chất Apriori của tập Sporadic và cách sinh luật từ tập Sporadic đóng — đây là hướng nghiên cứu còn mới tại Việt Nam năm 2015.
• So sánh hai thuật toán: Phân tích ưu nhược điểm của Apriori-Inverse (BFS) và MCPSI (DFS), chứng minh MCPSI vượt trội về độ phức tạp tính toán.
• Thực nghiệm trên dữ liệu thực: Triển khai thành công trên 500 giao tác thực tế, chứng minh tính khả thi của ứng dụng trong môi trường siêu thị.
• Định hướng tương lai: Xác định ba hướng mở gồm luật hiếm định lượng, khai phá song song và phát triển độ đo mới — tạo nền tảng cho các nghiên cứu tiếp theo.

Các nhà nghiên cứu muốn tiếp nối hướng này có thể bắt đầu bằng việc mở rộng thuật toán MCPSI sang CSDL định lượng trong vòng 12 tháng tới, hoặc thử nghiệm trên các bộ dữ liệu lâm sàng công khai như UCI Machine Learning Repository. Để tìm hiểu sâu hơn, hãy liên hệ Viện Công nghệ thông tin – Đại học Thái Nguyên hoặc tham khảo trực tiếp luận văn tại thư viện nhà trường.

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

CHƯƠNG 1 KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP 1. Khai phá dữ liệu 1. Quá trình phát hiện tri thức từ cơ sở dữ liệu Trong thời đại hiện đại của thế kỷ 21, với sự phát triển vượt bậc của công nghệ thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Lượng dữ liệu được lưu trữ dẫn đến một đòi hỏi cấp bách phải có những kỹ thuật mới, những công cụ tự động mới trợ giúp con người một cách thông minh trong việc chuyển đổi một lượng lớn dữ liệu thành thông tin hữu ích.

Một số nhà khoa học xem khai phá dữ liệu như là một cách gọi khác của một thuật ngữ cũng rất thông dụng là khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD)[5], vì cho rằng mục đích của quá trình khám phá tri thức là thông tin và tri thức có ích, nhưng đối tượng mà chúng ta phải xử lý rất nhiều trong suốt quá trình khám phá tri thức lại chính là dữ liệu. Một số nhà khoa học khác thì xem khai phá dữ liệu như là một bước chính trong quá trình khám phá tri thức. Hiểu quá trình khám phá, phát hiện tri thức ở đây là gì? Thông thường chúng ta coi dữ liệu như là một dãy các bit, các số và các ký hiệu, hoặc các “đối tượng” được gửi cho một chương trình dưới một định dạng nhất định nào đó. Chúng ta sử dụng các bit để đo lường thông tin, khi sử dụng xem nó như là dữ liệu đã được lọc bỏ dư thừa, được rút gọn tới mức tối thiểu.

Bít được dùng làm đơn vị đặc trưng cho dữ liệu. Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được học, được hiểu, được phát hiện ra. Nói cách khác, tri thức có thể coi là dữ liệu có độ trừu tượng và tổ chức cao.

Thuật ngữ KPDL ra đời vào những năm cuối của thập kỷ 1980. Khai phá dữ liệu bao gồm nhiều hướng tiếp cận, là sự kết hợp của nhiều ngành như: Cơ sở dữ liệu; Học máy; Trí tuệ nhân tạo; Lý thuyết thông tin; Xác suất thống kê; Tính toán hiệu năng cao và các phương pháp tính toán mềm v. Có rất nhiều định nghĩa khác nhau về "KPDL" đã được đưa ra, ta có thể hiểu khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) có ích, tiềm ẩn và mang tính dự đoán trong các khối cơ sở dữ liệu lớn. 4 KPDL là cốt lõi của quá trình khám phá tri thức.

Nó gồm có các giải thuật KPDL chuyên dùng, dưới một số quy định về hiệu quả tính toán chấp nhận được. KPDL là nhằm tìm ra những mẫu mới, mẫu có tính chất không tầm thường, những thông tin tiềm ẩn mang tính dự đoán chưa được biết đến và có khả năng mang lại lợi ích cho người sử dụng. Nói tóm lại, mục đích chung của việc phát hiện tri thức từ dữ liệu và KPDL là tìm ra các mẫu được quan tâm nhất tồn tại trong cơ sở dữ liệu, nhưng chúng lại bị che dấu bởi một số lượng lớn dữ liệu. Quá trình khám phá tri thức được tiến hành qua các bước sau [5]: Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu Kho data mining dữ 3.Biến đổi dữ liệu liệu data transformation 2.

Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1. Quá trình khám phá tri thức Bước 1: Trích chọn dữ liệu (data selection): là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses). Bước 2: Tiền xử lý dữ liệu (data preprocessing): là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, v.

v), rút gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy 5 mẫu, .v ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng, v. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hoá. Bước 3: Biến đổi dữ liệu (data transformation): là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau. Bước 4: Khai phá dữ liệu (data mining): đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá(phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.

Bước 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai phá ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,. Đồng thời bước này cũng đánh giá những tri thức khai phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được lưu và sử dụng lại.

Quá trình khai phá dữ liệu Với những dữ liệu đã thu thập, ta tiến hành tích hợp và chỉnh sửa dữ liệu, lọc dữ liệu, đây là quá trình tiền xử lý. Dữ liệu được thu thập từ nhiều nguồn khác nhau, qua những dữ liệu trực tiếp ta thống kê tóm tắt, trong khi đó có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Quá trình khai phá dữ liệu được thể hiện bởi hình 1.3 sau: Thống kê tóm tắt Xác định Xác định dữ Thu thập và Giải thuật Mẫu nhiệm vụ liệu liên quan tiền xử lý DL khai phá DL Dữ liệu trực tiếp 6 Hình 1.3: Quá trình khai phá dữ liệu Công việc tiếp theo sử dụng các thuật toán khác nhau để khai phá các tri thức tiềm ẩn trong kho dữ liệu sau khi đã xử lý và được thống kê tóm tắt,….

Kết quả của quá trình khai phá dữ liệu là đạt được nhiệm vụ đặt ra. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. Các ứng dụng của khai phá dữ liệu Vào những năm của thế kỷ XX, khi công nghệ thông tin bùng nổ cả về bề rộng và chiều sâu, ảnh hưởng đến hầu hết các lĩnh vực khoa học, kinh tế và đời sống xã hội.

Dữ liệu ngày càng tăng theo thời gian, người ta coi khai phá dữ liệu là quá trình phân tích cơ sở dữ liệu nhằm phát hiện ra các thông tin mới và giá trị, thường thể hiện dưới dạng các mối quan hệ chưa biết đến giữa các mục dữ liệu. Nhờ phân tích các dữ liệu mà các doanh nghiệp có khả năng dự báo trước một số hành vi ứng xử của khách hàng. Công nghệ thông tin phát triển đồng nghĩa với việc phát triển các phần mềm ứng dụng. Phần mềm khai phá dữ liệu là một công cụ phân tích dùng để phân tích dữ liệu.

Nó cho phép người sử dụng phân tích dữ liệu theo nhiều góc nhìn khác nhau, phân loại dữ liệu theo những quan điểm riêng biệt và tổng kết các mối quan hệ đã được bóc tách. Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như: Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận, … Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm, … Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, …khoa học địa lý: dự báo động đất, … Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet… Những gì thu được từ khai phá dữ liệu thật đáng giá. Điều đó được chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trường hợp xét nghiệm 7 không hợp lý, tiết kiệm được nhiều kinh phí mỗi năm; Trong dịch vụ viễn thông đã phát hiện ra những nhóm người phổ biến gọi cho nhau bằng mobile và thu lợi hàng triệu USD; IBM Suft-Aid đã áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website; trang Web mua bán qua mạng cũng tăng doanh thu nhờ áp dụng khai phá dữ liệu trong việc phân tích sở thích mua bán của khách hàng. Khai phá luật kết hợp trong cơ sở dữ liệu 1.

Các khái niệm cơ sở Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay còn gọi là mô hình cơ bản) được R. Swami đề xuất vào năm 1993 [4], xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán được tại các siêu thị. Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng như không dựa vào các đặc tính dữ liệu vốn có của các mục dữ liệu mà chỉ dựa vào sự xuất hiện cùng lúc của chúng. Phần tiếp sau đây nêu một số khái niệm cơ bản dẫn đến bài toán khai phá tập mục phổ biến và luật kết hợp.

Cơ sở dữ liệu giao tác Định nghĩa 2.1: Cho tập các mục (item) I  i1 , i2 ,. Một giao tác (transaction) T là một tập con của I, TI. Cơ sở dữ liệu giao tác là một tập các giao tác DB  T1 ,T2 ,. Mỗi giao tác được gán một định danh TID.

Một tập mục con X  I , gồm k mục phân biệt được gọi là một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X  T .