Khai Phá Dữ Liệu với Luật Kết Hợp và Ứng Dụng trong Trợ Giúp Ra Quyết Định

Khai phá dữ liệu (Data Mining) (DM) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong… 57 trang · Trường Đại Học Quảng Nam · 2017.

• Tác giả: Anoulak Sidaralak
• Người hướng dẫn: ThS. Lê Thị Nguyên An
• Trường học: Trường Đại Học Quảng Nam
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Khai Phá Dữ Liệu Với Luật Kết Hợp Và Ứng Dụng Trong Trợ Giúp Ra Quyết Định
• Loại tài liệu: khóa luận tốt nghiệp
• Năm xuất bản: 2017
• Địa điểm: Quảng Nam

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. PHẦN 1: MỞ ĐẦU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Đối tượng nghiên cưú và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Lịch sử nghiên cứu
• 1.6. Đóng góp của đề tài
• 1.7. Cấu trúc của đề tài
• 2. PHẦN 2: NỘI DUNG
• 2. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
• 1.1. Khai phá dữ liệu và phát hiện tri thức
• 1.2. Quá trình khám phá tri thức trong CSDL
• 1.3. Các phương pháp khai phá dữ liệu
• 1.4. Các thành phần của giải thuật khai phá dữ liệu
• 1.5. Phương pháp suy diễn / quy nạp
• 1.6. Phương pháp K-láng giềng gần
• 1.7. Phương pháp sử dụng cây quyết định và luật
• 1.8. Phương pháp phát hiện luật kết hợp
• 1.9. Nhiệm vụ chính trong khai thác dữ liệu
• 1.10. Mô hình hoá sự phụ thuộc (dependency modeling)
• 1.11. Phát hiện sự biến đổi và độ lệch (change and deviation detection)
• 1.12. Các kỹ thuật khai phá dữ liệu
• 1.13. Các kỹ thuật tiếp cận trong Data mining
• 1.14. Dạng dữ liệu có thể khai phá
• 1.15. Các ứng dụng của khai phá dữ liệu
• 1.16. Khai phá luật kết hợp và ứng dụng
• 1.17. Phân loại các hệ thống khai phá dữ liệu
• 1.18. Xu hướng trong khai phá dữ liệu
• 3. CHƯƠNG 2: LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU
• 2.1. Khai phá luật kết hợp
• 2.2. Lý thuyết về luật kết hợp
• 2.3. Định nghĩa luật kết hợp
• 2.4. Một số tính chất liên quan đến các hạng mục phổ biến
• 2.5. Tập mục phổ biến
• 2.6. Luật kết hợp
• 2.7. Một số hướng tiếp cận trong khai phá luật kết hợp
• 2.8. Phát biểu bài toán phát hiện luật kết hợp
• 2.9. Một số thuật toán phát hiện luật kết hợp
• 2.9.1. Thuật toán Apriori
• 2.9.2. Ý tưởng thuật toán Apriori
• 2.9.3. Thuật toán Apriori (chi tiết)
• 2.9.4. Sinh các luật kết hợp từ tập mục phổ biến
• 2.9.5. Thuật toán FP-growth
• 2.9.6. Ý tưởng thuật toán FP-growth
• 2.9.7. Thuật toán FP-growth (chi tiết)
• 2.9.8. Đánh giá thuật toán FP-growth
• 4. CHƯƠNG 3: THỬ NGHIỆM KHAI PHÁ LUẬT KẾT HỢP
• 3.1. Phát biểu bài toán
• 3.2. Phân tích chương trình
• 3.3. Sử dụng phần mềm weka để hỗ trợ ra luật kết hợp
• 5. PHẦN 3: KẾT LUẬN
• PHẦN 4: TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Dữ Liệu Định Nghĩa Vai Trò

Khai phá dữ liệu (Data Mining) (DM)** là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm khám phá tri thức trong cơ sở dữ liệu, để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn; trong đó khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất.

1.1. Phân Biệt Khai Phá Dữ Liệu và Phát Hiện Tri Thức KDD

Mặc dù thường được sử dụng thay thế cho nhau, khai phá dữ liệu và phát hiện tri thức (KDD) không hoàn toàn đồng nhất. Nếu quan niệm tri thức là một quan hệ của các mẫu giữa các phần tử dữ liệu thì quá trình phát hiện tri thức chỉ toàn bộ quá trình trích xuất tri thức từ cơ sở dữ liệu, trong đó trải qua nhiều giai đoạn khác nhau như: Tìm hiểu và phát hiện vấn đề thu thập và tiền xử lý dữ liệu, phát hiện tri thức, minh họa và đánh giá tri thức đã phát hiện và đưa kết quả vào thực tế. Khai phá dữ liệu có những điểm khác nhau về mặt ngữ nghĩa so với phát hiện tri thức từ cơ sở dữ liệu nhưng thực tế ta thấy khai phá dữ liệu là chỉ một giai đoạn phát hiện tri thức trong một chuỗi các giai đoạn quá trình phát hiện tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trò chủ chốt và là giai đoạn chính tạo nên tính đa ngành của phát hiện tri thức trong cơ sở dữ liệu.

1.2. Các Bước Cơ Bản Trong Quá Trình Khám Phá Tri Thức

Quá trình khám phá tri thức trong CSDL (KDD) bao gồm nhiều giai đoạn lặp lại. Bước đầu tiên là xác định bài toán. Tiếp theo là thu thập và tiền xử lý dữ liệu, loại bỏ nhiễu và làm giàu dữ liệu. Sau đó là giai đoạn khai phá dữ liệu, trích xuất các mẫu. Kế đến là diễn giải và đánh giá tri thức. Cuối cùng là sử dụng tri thức đã phát hiện. Theo tài liệu gốc, sự lặp lại có thể xuất hiện ở bất cứ bước nào, đảm bảo kết quả chính xác và hữu ích nhất.

II. Tìm Hiểu Luật Kết Hợp Cơ Sở Lý Thuyết Ứng Dụng

Luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu. Kỹ thuật khám phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Mục tiêu của đề tài là hiểu rõ đươc những khái niệm cơ bản của luật kết hợp, nắm vững một số thuật toán phát hiện luật kết hợp, xây dựng ứng dụng thuật toán Apriori và FP-growth để trợ giúp ra quyết địn trong thực tế.

2.1. Định Nghĩa và Các Khái Niệm Cơ Bản Của Luật Kết Hợp

Đề tài tập trung nghiên cứu lý thuyết về khai phá dữ liệu, một số thuật toán phát hiện luật kết hợp . Nghiêm cứu thuật toán Apriori, FP-growth và xây dựng ứng dụng thực tế. Luật kết hợp khám phá các mối quan hệ giữa các mục dữ liệu trong một tập dữ liệu lớn. Nó xác định các mục thường xuyên xuất hiện cùng nhau. Các khái niệm quan trọng bao gồm độ hỗ trợ (support), độ tin cậy (confidence), và độ nâng (lift) của luật. Các tham số này đánh giá mức độ quan trọng và tin cậy của các luật được khai phá.

2.2. Phát Biểu Bài Toán Phát Hiện Luật Kết Hợp Chi Tiết

Bài toán phát hiện luật kết hợp là tìm ra các luật dạng X -> Y, trong đó X và Y là các tập mục (itemset) không giao nhau. Mục tiêu là tìm tất cả các luật thỏa mãn ngưỡng độ hỗ trợ tối thiểu (minsup) và ngưỡng độ tin cậy tối thiểu (minconf). Điều này đòi hỏi việc khai thác các tập mục phổ biến (frequent itemset) và sau đó sinh ra các luật từ các tập mục này. Theo tài liệu gốc, thuật toán Apriori và FP-growth là hai phương pháp phổ biến để giải quyết bài toán này.

2.3. Các Hướng Tiếp Cận Chính Trong Khai Phá Luật Kết Hợp

Có nhiều hướng tiếp cận khác nhau trong khai phá luật kết hợp, bao gồm các phương pháp dựa trên thuật toán Apriori, FP-growth, và các biến thể của chúng. Thuật toán Apriori sử dụng phương pháp duyệt mức để tìm các tập mục phổ biến, trong khi FP-growth sử dụng cấu trúc cây FP-tree để nén dữ liệu và khai thác luật hiệu quả hơn. Mỗi phương pháp có ưu và nhược điểm riêng, phù hợp với các loại dữ liệu và yêu cầu ứng dụng khác nhau.

III. Thuật Toán Apriori Hướng Dẫn Chi Tiết Ví Dụ Minh Họa

Thuật toán Apriori là một trong những thuật toán kinh điển trong khai phá luật kết hợp. Mục tiêu của thuật toán này là tìm ra các tập mục phổ biến trong một tập dữ liệu giao dịch. Apriori sử dụng phương pháp duyệt mức, bắt đầu từ các mục đơn lẻ và mở rộng dần thành các tập mục lớn hơn. Nguyên tắc cơ bản là nếu một tập mục không phổ biến thì bất kỳ tập cha nào của nó cũng không thể phổ biến.

3.1. Ý Tưởng và Nguyên Lý Hoạt Động Của Thuật Toán Apriori

Ý tưởng chính của thuật toán Apriori là sử dụng tính chất "tập con của một tập phổ biến phải là phổ biến". Thuật toán bắt đầu bằng việc tìm tất cả các mục đơn lẻ (1-itemset) có độ hỗ trợ lớn hơn ngưỡng tối thiểu. Sau đó, nó tạo ra các ứng viên 2-itemset từ các 1-itemset phổ biến và tiếp tục quá trình này cho đến khi không còn ứng viên nào được tạo ra. Theo tài liệu, thuật toán sử dụng hai bước chính: sinh ứng viên và cắt tỉa (pruning).

3.2. Các Bước Cụ Thể Để Thực Hiện Thuật Toán Apriori

Thuật toán Apriori bao gồm các bước sau: 1) Tìm tất cả các mục đơn lẻ có độ hỗ trợ lớn hơn ngưỡng tối thiểu. 2) Tạo các ứng viên k-itemset từ các (k-1)-itemset phổ biến. 3) Tính độ hỗ trợ cho mỗi ứng viên. 4) Chọn các ứng viên có độ hỗ trợ lớn hơn ngưỡng tối thiểu để trở thành k-itemset phổ biến. 5) Lặp lại bước 2-4 cho đến khi không còn ứng viên nào được tạo ra.

3.3. Ưu Điểm Nhược Điểm Của Thuật Toán Apriori

Thuật toán Apriori có ưu điểm là đơn giản và dễ hiểu. Tuy nhiên, nó có nhược điểm là tốn kém về mặt tính toán, đặc biệt là khi tập dữ liệu lớn và ngưỡng độ hỗ trợ thấp. Thuật toán phải duyệt qua toàn bộ tập dữ liệu nhiều lần để tính độ hỗ trợ cho các ứng viên, dẫn đến hiệu suất kém.

IV. Thuật Toán FP Growth Giải Pháp Thay Thế Hiệu Quả

Thuật toán FP-growth là một giải pháp thay thế hiệu quả cho Apriori trong khai phá luật kết hợp. Thay vì tạo ra các ứng viên một cách tường minh, FP-growth sử dụng cấu trúc cây FP-tree để nén dữ liệu và khai thác luật trực tiếp từ cây. Điều này giúp giảm đáng kể chi phí tính toán và cải thiện hiệu suất.

4.1. Ý Tưởng Chính Đằng Sau Thuật Toán FP Growth

Ý tưởng chính của FP-growth là xây dựng một cây FP-tree đại diện cho tập dữ liệu giao dịch. Cây FP-tree lưu trữ thông tin về tần suất xuất hiện của các mục, cho phép khai thác luật mà không cần tạo ra các ứng viên. Thuật toán sau đó sử dụng phương pháp "chia để trị" để khai thác luật từ cây một cách hiệu quả.

4.2. Các Bước Xây Dựng và Sử Dụng Cây FP Tree

Các bước xây dựng cây FP-tree bao gồm: 1) Quét tập dữ liệu và tìm các mục phổ biến. 2) Sắp xếp các mục theo thứ tự giảm dần của tần suất xuất hiện. 3) Xây dựng cây FP-tree bằng cách duyệt qua từng giao dịch và thêm các mục vào cây theo thứ tự đã sắp xếp. Để khai thác luật, thuật toán duyệt cây từ dưới lên, tìm các mẫu phổ biến dựa trên các đường dẫn trên cây.

4.3. So Sánh FP Growth Với Apriori Ưu và Nhược Điểm

FP-growth có ưu điểm là hiệu suất cao hơn Apriori, đặc biệt là với các tập dữ liệu lớn và ngưỡng độ hỗ trợ thấp. Tuy nhiên, nó có nhược điểm là phức tạp hơn trong việc triển khai và yêu cầu nhiều bộ nhớ hơn để lưu trữ cây FP-tree. Ngoài ra, tài liệu gốc không đề cập chi tiết về các nhược điểm của FP-growth.

V. Ứng Dụng Luật Kết Hợp Trong Trợ Giúp Ra Quyết Định

Luật kết hợp có nhiều ứng dụng thực tế trong việc hỗ trợ ra quyết định trong nhiều lĩnh vực khác nhau. Một trong những ứng dụng phổ biến nhất là trong phân tích giỏ hàng (Market Basket Analysis) trong ngành bán lẻ. Ngoài ra, luật kết hợp cũng được sử dụng trong y học, tài chính, và nhiều lĩnh vực khác.

5.1. Ứng Dụng Trong Phân Tích Giỏ Hàng Market Basket Analysis

Phân tích giỏ hàng sử dụng luật kết hợp để tìm ra các sản phẩm thường được mua cùng nhau. Thông tin này có thể được sử dụng để tối ưu hóa vị trí sản phẩm trong cửa hàng, thiết kế các chương trình khuyến mãi, và xây dựng các hệ thống gợi ý sản phẩm (recommender systems). Ví dụ, nếu luật kết hợp cho thấy rằng khách hàng thường mua bánh mì và bơ cùng nhau, cửa hàng có thể đặt hai sản phẩm này gần nhau để tăng doanh số bán hàng.

5.2. Luật Kết Hợp Trong Dự Đoán Hành Vi Khách Hàng

Luật kết hợp có thể được sử dụng để dự đoán hành vi khách hàng và cá nhân hóa trải nghiệm mua sắm. Bằng cách phân tích lịch sử mua hàng của khách hàng, hệ thống có thể gợi ý các sản phẩm mà khách hàng có khả năng quan tâm. Thông tin này có thể được sử dụng để tăng tỷ lệ chuyển đổi và cải thiện sự hài lòng của khách hàng.

5.3. Các Ứng Dụng Khác Của Luật Kết Hợp Trong Các Lĩnh Vực

Luật kết hợp cũng được sử dụng trong nhiều lĩnh vực khác ngoài bán lẻ. Trong y học, nó có thể được sử dụng để tìm ra các mối liên hệ giữa các triệu chứng và bệnh tật. Trong tài chính, nó có thể được sử dụng để phát hiện gian lận và đánh giá rủi ro. Các ứng dụng tiềm năng của luật kết hợp là rất lớn và tiếp tục được khám phá.

VI. Kết Luận và Xu Hướng Phát Triển Của Khai Phá Dữ Liệu

Khai phá dữ liệu và luật kết hợp là những lĩnh vực quan trọng và đầy tiềm năng trong bối cảnh dữ liệu ngày càng gia tăng. Các thuật toán như Apriori và FP-growth đã đóng góp quan trọng vào sự phát triển của lĩnh vực này. Tuy nhiên, vẫn còn nhiều thách thức và cơ hội để cải thiện hiệu suất, mở rộng ứng dụng và phát triển các phương pháp mới.

6.1. Tóm Tắt Các Điểm Chính và Kết Quả Đạt Được

Đề tài đã trình bày tổng quan về khai phá dữ liệu, luật kết hợp, thuật toán Apriori và FP-growth, và các ứng dụng của chúng. Nghiên cứu cho thấy luật kết hợp là một công cụ mạnh mẽ để khám phá các mối quan hệ tiềm ẩn trong dữ liệu và hỗ trợ ra quyết định. Các thuật toán Apriori và FP-growth cung cấp các phương pháp hiệu quả để khai thác luật từ dữ liệu lớn.

6.2. Các Thách Thức và Hướng Nghiên Cứu Trong Tương Lai

Một trong những thách thức chính trong khai phá dữ liệu là xử lý dữ liệu lớn (Big Data) và dữ liệu phức tạp. Các thuật toán cần phải được tối ưu hóa để có thể xử lý dữ liệu với quy mô lớn và cấu trúc phức tạp. Ngoài ra, cần có các phương pháp mới để khai thác luật từ các loại dữ liệu phi cấu trúc, như văn bản và hình ảnh.

6.3. Vai Trò Của Khai Phá Dữ Liệu Trong Kỷ Nguyên Số

Khai phá dữ liệu đóng vai trò ngày càng quan trọng trong kỷ nguyên số, nơi dữ liệu được tạo ra với tốc độ chóng mặt. Khả năng khai thác thông tin từ dữ liệu là yếu tố then chốt để thành công trong nhiều lĩnh vực. Các doanh nghiệp và tổ chức cần đầu tư vào khai phá dữ liệu để có thể đưa ra các quyết định sáng suốt và cạnh tranh hiệu quả.

Nội dung chính

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

Khóa luận tốt nghiệp đại học ngành Công nghệ Thông tin với đề tài "Khai phá dữ liệu với luật kết hợp và ứng dụng trong trợ giúp ra quyết định" được thực hiện bởi sinh viên Anoulak Sidaralak (MSSV: 2113011029), dưới sự hướng dẫn của ThS. Lê Thị Nguyên An tại Khoa Công nghệ Thông tin, Trường Đại học Quảng Nam (tháng 5 năm 2017).

Trong bối cảnh hoạt động sản xuất và kinh doanh hiện đại, việc nắm bắt và xử lý thông tin được xác định là cơ sở nền tảng cho sự thành công của các cá nhân và tổ chức. Sự gia tăng vượt bậc về dung lượng và quy mô của các hệ thống cơ sở dữ liệu thương mại, quản lý và khoa học đã làm bộc lộ rõ hạn chế của các phương pháp xử lý truyền thống như thống kê cổ điển hay các phép đếm đơn giản. Thực tiễn đòi hỏi phải có những giải pháp thông minh hơn nhằm trích xuất tri thức tiềm ẩn từ các kho dữ liệu lớn, phục vụ công tác điều hành và hỗ trợ ra quyết định. Tại Việt Nam vào thời điểm nghiên cứu (năm 2017), kỹ thuật khám phá tri thức và khai phá dữ liệu (KDD/DM) nói chung và khai phá luật kết hợp nói riêng vẫn còn tương đối mới mẻ nhưng có tiềm năng ứng dụng thực tế rất lớn.

Tác giả xác định mục tiêu và nhiệm vụ nghiên cứu của đề tài gồm 3 nội dung chính:

1. Hiểu rõ được những khái niệm cơ bản của luật kết hợp.
2. Nắm vững một số thuật toán phát hiện luật kết hợp.
3. Xây dựng ứng dụng thuật toán Apriori và FP-growth để trợ giúp ra quyết định trong thực tế.

Đối tượng và phạm vi nghiên cứu của khóa luận được phân định cụ thể:

• Đối tượng nghiên cứu: Khung lý thuyết tổng quan về khai phá dữ liệu và các thuật toán phát hiện luật kết hợp trong cơ sở dữ liệu.
• Phạm vi nghiên cứu: Tập trung phân tích chuyên sâu hai giải thuật tiêu biểu là Apriori và FP-growth; phạm vi thực nghiệm ứng dụng được định vị trên bài toán phân tích giao dịch mua sắm tại hệ thống siêu thị bán lẻ (khảo sát mô hình vận hành của Siêu thị Metro Cash & Carry Việt Nam) và thực nghiệm xử lý bộ dữ liệu hàng hóa trên môi trường phần mềm khai phá dữ liệu Weka.

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

Khóa luận xây dựng hệ thống cơ sở lý thuyết dựa trên khung tiến trình khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) do Fayyad, Piatetsky-Shapiro và Smyth đề xuất năm 1989. Tác giả tổng hợp các quan điểm định nghĩa học thuật về khai phá dữ liệu của Ferruzza, Parsaye và Fayyad; trong đó khẳng định khai phá dữ liệu là một bước cốt lõi trong toàn bộ tiến trình KDD, đóng vai trò chiết xuất các mẫu và mô hình tiềm ẩn, có giá trị, mới lạ và có thể hiểu được từ các tập dữ liệu quy mô lớn.

Cơ sở toán học của luật kết hợp được xây dựng trên không gian giao dịch:

• Cho tập các mục dữ liệu (items) $I = {I_1, I_2, ..., I_m}$ và cơ sở dữ liệu giao dịch $D$, trong đó mỗi giao dịch $T$ là một tập con của $I$ ($T \subseteq I$) có định danh duy nhất (TID).
• Một luật kết hợp là một biểu thức có dạng $R: X \Rightarrow Y$, với $X, Y \subset I$ và $X \cap Y = \emptyset$. Trong đó $X$ là tiền đề (antecedent) và $Y$ là hệ quả (consequent).
• Hai độ đo cơ bản xác định độ giá trị của luật là Độ hỗ trợ (Support) và Độ tin cậy (Confidence):
  • $\text{Support}(X) = \frac{|{T \in D \mid X \subseteq T}|}{|D|}$ (Tỷ lệ phần trăm số giao dịch chứa tập mục $X$ trên tổng số giao dịch).
  • $\text{Confidence}(X \Rightarrow Y) = \frac{\text{Support}(X \cup Y)}{\text{Support}(X)} = P(Y \subseteq T \mid X \subseteq T)$.
• Bài toán phát hiện luật kết hợp được chia thành hai bài toán con: (1) Tìm tất cả các tập mục phổ biến có độ hỗ trợ thỏa mãn ngưỡng tối thiểu $\text{minsup}$; (2) Sinh ra các luật kết hợp từ các tập mục phổ biến có độ tin cậy thỏa mãn ngưỡng tối thiểu $\text{minconf}$.

Phương pháp nghiên cứu thực tế được tác giả triển khai bao gồm:

• Phương pháp phân tích, tổng hợp tài liệu chuyên khảo: Thu thập, hệ thống hóa các tài liệu lý thuyết trong và ngoài nước liên quan đến khai phá dữ liệu, luật kết hợp, cấu trúc dữ liệu cây tiền tố (prefix-tree) và thuật toán phân tích mẫu thường xuyên.
• Phương pháp so sánh - đối chiếu thuật toán: Phân tích cơ chế hoạt động, độ phức tạp tính toán và chi phí bộ nhớ giữa thuật toán sinh ứng viên lặp (Apriori) và thuật toán khai phá nén không sinh ứng viên (FP-growth).
• Phương pháp thực nghiệm: Sử dụng bộ công cụ phần mềm Weka (Waikato Environment for Knowledge Analysis) để cài đặt, thiết lập tham số và kiểm thử thuật toán Apriori trên tập dữ liệu giao dịch bán lẻ.

Nguồn dữ liệu nghiên cứu được tác giả tiếp cận từ hai nguồn: dữ liệu mô tả cấu trúc quản lý hóa đơn của Siêu thị Metro Cash & Carry Việt Nam và bộ dữ liệu giao dịch chuẩn supermarket.csv được tích hợp trong môi trường thử nghiệm Weka.

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

Chương 1: Tổng quan về khai phá dữ liệu

Chương này trình bày toàn diện các khái niệm, quy trình và các bài toán cốt lõi của công nghệ khai phá dữ liệu trong tiến trình KDD. Tác giả làm rõ quy trình KDD gồm 5 bước lặp:

1. Hình thành, xác định và định nghĩa bài toán: Tìm hiểu lĩnh vực ứng dụng, xác định mục tiêu và chọn phương pháp khai thác phù hợp.
2. Thu thập và tiền xử lý dữ liệu: Làm sạch dữ liệu (loại bỏ nhiễu), làm giàu dữ liệu (xử lý dữ liệu khuyết), biến đổi và rút gọn dữ liệu. Tác giả nhấn mạnh đây là bước chiếm nhiều thời gian nhất trong toàn bộ quy trình.
3. Khai phá dữ liệu: Trích xuất các mẫu hoặc mô hình ẩn dưới dữ liệu (gồm bài toán mô tả và bài toán dự báo).
4. Hiểu tri thức: Đánh giá, làm sáng tỏ các mô tả và dự đoán thu được.
5. Sử dụng tri thức: Tích hợp các tri thức phát hiện được vào các hệ thống hỗ trợ ra quyết định.

Về mặt giải thuật, tác giả phân tích 3 thành phần chính cấu thành một giải thuật khai phá dữ liệu: biểu diễn mô hình, kiểm định mô hình (sử dụng đánh giá chéo - cross validation theo logic hoặc thống kê) và phương pháp tìm kiếm (tìm kiếm tham số và tìm kiếm mô hình bằng các kỹ thuật heuristic).

Chương 1 cũng hệ thống hóa các phương pháp và nhiệm vụ khai phá dữ liệu điển hình:

• Các phương pháp tiếp cận: Suy diễn/quy nạp, phương pháp K-láng giềng gần (KNN - có độ phức tạp lũy thừa bậc 2 theo số bản ghi), phương pháp cây quyết định và luật, phương pháp phát hiện luật kết hợp.
• 6 nhiệm vụ chính: Phân lớp (classification), hồi quy (regression), phân nhóm (clustering), tổng hợp (summarization), mô hình hóa sự phụ thuộc (dependency modeling), phát hiện sự biến đổi và độ lệch (change and deviation detection).
• Các dạng dữ liệu có thể khai phá: CSDL quan hệ, CSDL đa chiều, CSDL giao dịch, CSDL hướng đối tượng, dữ liệu không gian - thời gian, chuỗi thời gian, đa phương tiện, dữ liệu văn bản và Web.
• Phân loại và xu hướng nghiên cứu: Phân loại hệ thống theo dữ liệu, theo loại tri thức, theo kỹ thuật và theo lĩnh vực ứng dụng. Xu hướng nghiên cứu tập trung vào tăng hiệu suất, giảm độ phức tạp tính toán, xử lý dữ liệu nhiễu, khai thác song song - phân tán, phát triển ngôn ngữ truy vấn khai phá dữ liệu (DMQL) và trực quan hóa tri thức.

Chương 2: Luật kết hợp trong khai phá dữ liệu

Chương 2 là phần trọng tâm lý thuyết của khóa luận, đi sâu vào cấu trúc toán học của luật kết hợp, các tính chất cơ bản và cơ chế vận hành chi tiết của hai giải thuật kinh điển: Apriori và FP-growth.

Tác giả tổng hợp các tính chất đại số quan trọng chi phối quá trình tìm kiếm luật kết hợp:

• Tính chất tập mục phổ biến: Nếu $A \subseteq B$ thì $\text{sup}(A) \ge \text{sup}(B)$. Mọi tập con của một tập mục phổ biến đều là tập mục phổ biến (tính chất Apriori). Ngược lại, một tập mục chứa một tập con không phổ biến thì bản thân nó cũng là tập không phổ biến.
• Tính chất của luật kết hợp: Luật kết hợp không có tính hợp luật (từ $X \Rightarrow Z$ và $Y \Rightarrow Z$ không suy ra được $X \cup Y \Rightarrow Z$); không có tính tách luật; không có tính bắc cầu (nếu $X \Rightarrow Y$ và $Y \Rightarrow Z$ thì không thể suy ra $X \Rightarrow Z$ do độ tin cậy bị nhân suy giảm: $\text{conf}(X \Rightarrow Z) \le \text{minconf}^2 < \text{minconf}$).

Tác giả phân loại các hướng tiếp cận luật kết hợp hiện đại: luật kết hợp nhị phân (Boolean), luật kết hợp với thuộc tính số và định danh (dùng kỹ thuật rời rạc hóa), luật kết hợp dựa trên tập thô, luật kết hợp nhiều mức, luật kết hợp mờ, luật kết hợp có trọng số (cho phép khai thác các luật hiếm nhưng có giá trị cao) và luật kết hợp song song.

Khóa luận phân tích chi tiết thuật toán Apriori (Rakesh Agrawal et al., 1993, 1996):

• Cơ chế vận hành: Sử dụng nguyên lý cắt tỉa không gian tìm kiếm dựa trên độ hỗ trợ. Thuật toán duyệt CSDL nhiều lần; lần duyệt thứ $k$ sử dụng tập các tập $(k-1)$-mục phổ biến ($L_{k-1}$) để sinh ra tập ứng viên $k$-mục ($C_k$) thông qua hai bước: Bước kết nối (Join step) và Bước tỉa (Prune step - hàm has_infrequent_subset). Sau đó quét toàn bộ CSDL để đếm tần suất xuất hiện thực tế của các ứng viên trong $C_k$ bằng cấu trúc cây băm (hash tree) nhằm chọn ra $L_k$.
• Công thức số luật tối đa: Với tập gồm $d$ hạng mục, tổng số luật kết hợp tiềm năng tối đa có thể sinh ra được xác định bởi công thức: $$R = 3^d - 2^{d+1} + 1$$ Tác giả đưa ra minh chứng: khi $d = 6$, số lượng luật tối đa có thể lên tới $R = 602$ luật.

Khóa luận phân tích thuật toán FP-growth (Frequent Pattern Growth - Jiawei Han, Jian Pei, Yiwen Yin, 2000):

• Ý tưởng cốt lõi: Khắc phục triệt để nhược điểm sinh tập ứng viên khổng lồ và việc phải quét CSDL nhiều lần của Apriori bằng cách nén toàn bộ cơ sở dữ liệu vào một cấu trúc cây gọi là FP-tree (Frequent Pattern Tree).
• Quy trình thực hiện: Quét CSDL lần 1 để đếm tần suất và xác định các 1-mục phổ biến, sắp xếp giảm dần theo độ hỗ trợ; quét CSDL lần 2 để chèn các giao dịch vào cây FP-tree thông qua các tiền tố chung (prefix paths). Sau đó, thuật toán áp dụng chiến lược chia để trị (divide-and-conquer) để khai phá đệ quy các cây FP-tree điều kiện (conditional FP-tree) từ các cơ sở mẫu điều kiện (conditional pattern base).
• Đánh giá thuật toán: FP-growth chỉ quét cơ sở dữ liệu đúng 2 lần; thời gian xây dựng cây và độ phức tạp không gian bộ nhớ đều ở mức tuyến tính $O(n)$ với $n$ là số lượng giao dịch; chiều cao của cây bị chặn bởi độ dài của giao dịch lớn nhất.

Tiêu chí so sánh	Thuật toán Apriori	Thuật toán FP-growth
Tác giả & Năm công bố	Rakesh Agrawal et al. (1993, 1996)	Jiawei Han, Jian Pei, Yiwen Yin (2000)
Cơ chế khai phá	Sinh tập ứng viên lặp ($C_k$) từ $L_{k-1}$	Khai phá đệ quy trên cây tiền tố (FP-tree)
Số lần quét CSDL	Quét lặp nhiều lần (bằng độ dài tập mục lớn nhất)	Quét cố định đúng 2 lần
Sinh tập ứng viên	Có (chi phí sinh và kiểm tra rất lớn)	Không sinh tập ứng viên
Cấu trúc dữ liệu chính	Cây băm (Hash tree)	Cây mẫu thường xuyên (FP-tree) & Header table
Độ phức tạp thời gian	Rất cao khi dữ liệu lớn hoặc ngưỡng hỗ trợ thấp	$O(n)$ - Tuyến tính theo số giao dịch
Khả năng mở rộng	Bị hạn chế khi tập mục phổ biến dài	Tốt trên cả mẫu phổ biến ngắn và dài

Chương 3: Thử nghiệm khai phá luật kết hợp

Chương 3 trình bày bài toán ứng dụng thực tế tại Siêu thị Metro (thuộc Công ty TNHH Metro Cash & Carry Việt Nam). Mô hình vận hành của Metro có đặc thù: khách hàng là hội viên có đăng ký kinh doanh, lượng khách mua sắm bình quân đạt từ 4.000 đến 5.000 lượt/ngày, giá trị thanh toán trung bình trên mỗi hóa đơn đạt 500.000 VNĐ.

Cơ sở dữ liệu hóa đơn của siêu thị ghi nhận các trường thông tin phong phú: số hóa đơn, mã khách hàng, tên khách hàng, địa chỉ, người đại diện, thời gian (ngày, giờ), mã thu ngân, quầy, mã hàng hóa, tên hàng, số lượng đóng gói, đơn vị tính, đơn giá, thành tiền trước và sau thuế VAT. Tác giả chỉ ra các yêu cầu cấp thiết của nhà quản trị siêu thị gồm:

• Phân tích sức mua sắm theo nghề nghiệp (công ty, cửa hàng, nhà máy).
• Phân tích sức mua theo khu vực địa lý (thành thị, nông thôn, ngoại tỉnh).
• Xác định chu kỳ mua sắm theo thời gian (ngày thường, ngày lễ, tết).
• Phát hiện các quy luật kết hợp giữa các mặt hàng trong cùng một giỏ hàng để phục vụ bài toán xếp đặt kệ hàng (product placement), bán chéo (cross-selling), lên kế hoạch nhân sự và liên kết cung ứng.

Khóa luận thiết lập quy trình thử nghiệm qua 2 giai đoạn:

1. Giai đoạn tiền xử lý: Trích xuất bảng dữ liệu bán hàng (LoaiHang), đưa dữ liệu về định dạng văn bản (text), ánh xạ các thuộc tính danh mục sản phẩm thành các số tự nhiên để xử lý tính toán.
2. Giai đoạn khai phá: Cài đặt và thực thi thuật toán trên phần mềm Weka.

Trong phần mềm Weka, tác giả nạp tập dữ liệu supermarket.csv gồm 10 đối tượng giao dịch và 4 thuộc tính. Tác giả cấu hình tab Associate với thuật toán Apriori và giải thích rõ vai trò của các tham số điều khiển:

• lowerBoundMinSupport: Ngưỡng cận dưới của độ hỗ trợ tối thiểu.
• upperBoundMinSupport: Ngưỡng cận trên của độ hỗ trợ tối thiểu (thuật toán sẽ lặp giảm dần từ cận trên xuống cận dưới).
• metricType: Loại độ đo đánh giá luật, Weka hỗ trợ 4 loại: Confidence (độ tin cậy), Lift (độ nâng), Leverage và Conviction.
• minimum metric score: Điểm ngưỡng tối thiểu của độ đo đã chọn để lọc luật.
• numRules: Số lượng luật tối ưu cần tìm và xuất ra màn hình (sắp xếp giảm dần theo metric).
• significanceLevel: Mức ý nghĩa thống kê của luật (áp dụng khi metricType là confidence).

Khi thiết lập ngưỡng độ hỗ trợ tối thiểu minsup = 0.5, thuật toán Apriori trong Weka đã tự động lọc và xuất ra 4 luật kết hợp tốt nhất, được sắp xếp giảm dần theo độ tin cậy (confidence).

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

Khóa luận đã trích xuất và phân tích cụ thể các kết quả định lượng thu được từ cả tính toán lý thuyết lẫn thử nghiệm phần mềm:

• Về mặt số liệu thực nghiệm trên Weka: Với tập dữ liệu giao dịch hàng hóa supermarket.csv ở ngưỡng độ hỗ trợ minsup = 0.5 (tương đương tần suất xuất hiện tối thiểu trong 50% số giao dịch), hệ thống đã lọc và xuất ra 4 quy tắc kết hợp có độ tin cậy cao nhất. Kết quả minh chứng thuật toán đã tự động loại bỏ các tổ hợp không đạt ngưỡng hỗ trợ ngay từ các bước lặp đầu tiên, giảm thiểu số lượng phép duyệt cơ sở dữ liệu.
• Về giải pháp quản lý thực tiễn: Dựa trên các luật kết hợp phát hiện được từ giỏ hàng siêu thị, tác giả đề xuất các giải pháp hỗ trợ ra quyết định kinh doanh:
  • Bố trí mặt hàng: Sắp xếp các cặp mặt hàng có quan hệ phụ thuộc cao ở các vị trí liền kề hoặc bố trí ở các quầy đối diện để kích thích nhu cầu mua sắm đồng thời.
  • Xúc tiến thương mại: Thiết kế các gói khuyến mãi kết hợp (combo) giữa sản phẩm chính và sản phẩm đi kèm nhằm gia tăng giá trị đơn hàng.
  • Quản trị chuỗi cung ứng: Lập kế hoạch nhập kho đồng bộ các nhóm hàng hóa có độ kết hợp cao, đặc biệt theo chu kỳ ngày lễ tết.
  • Phân bổ nhân sự: Bố trí số lượng nhân viên thu ngân và kiểm soát viên tương ứng với mật độ mua sắm theo khung giờ và chu kỳ tiêu dùng.

Về đóng góp học thuật so với các tài liệu trước, khóa luận đã tự nêu:

• Cung cấp một tài liệu hệ thống hóa đầy đủ, chi tiết và có tính sư phạm cao về lý thuyết khai phá luật kết hợp, tổng hợp từ các định nghĩa toán học đến các bước biến đổi thuật toán.
• Làm rõ sự cải tiến vượt bậc về cấu trúc dữ liệu và hiệu năng tính toán của thuật toán FP-growth so với Apriori (giảm số lần quét CSDL từ $k$ lần xuống cố định 2 lần, tối ưu bộ nhớ ở mức tuyến tính $O(n)$).
• Minh họa trực quan quy trình ứng dụng công cụ phần mềm Weka vào việc giải quyết bài toán phân tích dữ liệu bán lẻ thực tế.

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

Khóa luận tự xác định các hạn chế và đề xuất các hướng mở nghiên cứu dựa trên nội dung báo cáo:

• Hạn chế:
  • Quy mô dữ liệu thử nghiệm trong Weka còn hạn chế ở mức dữ liệu mẫu minh họa (supermarket.csv với 10 đối tượng và 4 thuộc tính), chưa xử lý trực tiếp trên toàn bộ kho dữ liệu thực tế hàng triệu bản ghi của Siêu thị Metro.
  • Khóa luận mới chỉ dừng lại ở việc thử nghiệm thuật toán Apriori có sẵn trên phần mềm mã nguồn mở Weka, chưa xây dựng một module phần mềm độc lập để tự động kết nối trực tiếp vào hệ thống cơ sở dữ liệu bán hàng của doanh nghiệp.
  • Chưa tiến hành cài đặt kiểm thử thực nghiệm đối đầu giữa thuật toán FP-growth và Apriori trên cùng một bộ dữ liệu lớn để đo đạc thời gian thực thi bằng biểu đồ định lượng.
• Hướng nghiên cứu tiếp:
  • Mở rộng nghiên cứu các biến thể nâng cao của luật kết hợp: khai phá luật kết hợp mờ (fuzzy association rules) để xử lý dữ liệu thuộc tính số liên tục, luật kết hợp có trọng số (weighted association rules) nhằm phát hiện các mặt hàng có giá trị sinh lời cao nhưng tần suất mua thấp.
  • Nghiên cứu thuật toán khai phá luật kết hợp song song và phân tán trên môi trường tính toán hiệu năng cao để đáp ứng yêu cầu xử lý dữ liệu lớn theo thời gian thực.
  • Tích hợp luật kết hợp với các hệ thống phân tích trực tuyến đa chiều (OLAP/ROLAP/MOLAP) và ngôn ngữ truy vấn khai phá dữ liệu (DMQL).

Giá trị tham khảo

Báo cáo khóa luận là tài liệu tham khảo phù hợp cho:

• Sinh viên chuyên ngành Công nghệ Thông tin, Khoa học Máy tính và Hệ thống Thông tin Quản lý đang học tập học phần Khai phá dữ liệu hoặc làm đồ án tốt nghiệp về chủ đề khám phá tri thức từ cơ sở dữ liệu.
• Các nhà nghiên cứu và người phát triển phần mềm đang tìm kiếm tài liệu giải thích chi tiết cơ chế hoạt động, các bước kết nối (join) và tỉa bớt (prune) của giải thuật Apriori, cũng như nguyên lý xây dựng cây FP-tree và khai phá trên cây điều kiện.
• Các chuyên viên phân tích dữ liệu bán lẻ (Retail Analytics / Market Basket Analysis) cần tài liệu hướng dẫn cấu hình và giải thích các tham số khai phá luật kết hợp trên môi trường phần mềm Weka.

Phần đáng giá nhất để tham khảo trong tài liệu là Chương 2 với hệ thống ví dụ tính toán thủ công từng bước cho thuật toán Apriori, bảng tính minh họa cơ chế sinh mẫu của thuật toán FP-growth trên tập dữ liệu AllElectronics và phần diễn giải chi tiết các tham số điều khiển của Weka trong Chương 3.

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

1. Bài toán khai phá luật kết hợp được chia thành hai bài toán con nào?

Theo văn bản, khai phá luật kết hợp được chia thành hai bài toán con độc lập:

• Bài toán 1: Tìm tất cả các tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng hỗ trợ tối thiểu ($\text{minsup}$) do người dùng xác định; các tập mục này được gọi là các tập mục phổ biến (frequent itemsets).
• Bài toán 2: Sử dụng các tập mục phổ biến tìm được ở bài toán 1 để sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin cậy tối thiểu ($\text{minconf}$) do người dùng thiết lập.

2. Vì sao luật kết hợp không có tính chất bắc cầu?

Văn bản chứng minh rằng nếu có hai luật $X \Rightarrow Y$ và $Y \Rightarrow Z$ cùng đạt ngưỡng tin cậy tối thiểu $\text{minconf}$, ta không thể suy ra luật $X \Rightarrow Z$ cũng đạt độ tin cậy đó. Lý do là độ tin cậy của luật bắc cầu bị suy giảm theo tích xác suất điều kiện: $$\text{conf}(X \Rightarrow Z) \le \text{minconf} \times \text{minconf} = \text{minconf}^2$$ Vì $\text{minconf} < 1$ (tương đương nhỏ hơn 100%) nên $\text{minconf}^2 < \text{minconf}$, dẫn đến luật $X \Rightarrow Z$ không đảm bảo đủ ngưỡng độ tin cậy tối thiểu.

3. Công thức tính số lượng luật kết hợp tối đa từ một tập gồm $d$ hạng mục là gì?

Với một cơ sở dữ liệu có $d$ hạng mục dữ liệu, tổng số tập mục ứng cử có thể tạo ra là $2^d$. Khi đó, tổng số luật kết hợp tiềm năng tối đa có thể sinh ra được tính bằng công thức: $$R = 3^d - 2^{d+1} + 1$$ Ví dụ cụ thể được tác giả đưa ra trong văn bản: khi số mục dữ liệu $d = 6$, số lượng luật kết hợp tối đa sinh ra có thể lên đến 602 luật.

4. Thuật toán FP-growth giải quyết những nhược điểm nào của thuật toán Apriori?

FP-growth khắc phục hai nhược điểm lớn nhất của Apriori:

• Loại bỏ hoàn toàn chi phí sinh tập ứng viên khổng lồ ($C_k$): Apriori phải sinh ra một lượng rất lớn các tập ứng viên ở mỗi bước lặp và kiểm tra sự tồn tại của chúng, trong khi FP-growth khai phá trực tiếp từ cây mẫu thường xuyên mà không cần sinh ứng viên.
• Giảm thiểu số lần quét CSDL: Apriori phải quét lại toàn bộ cơ sở dữ liệu sau mỗi bước tăng kích thước $k$ của tập mục, trong khi FP-growth nén dữ liệu vào cây FP-tree và luôn chỉ cần quét cơ sở dữ liệu đúng 2 lần, đạt độ phức tạp thời gian tuyến tính $O(n)$.

5. Trong phần mềm Weka, tham số metricType của thuật toán Apriori hỗ trợ những độ đo nào?

Trong giao diện cấu hình thuật toán Apriori của phần mềm Weka (được phân tích tại Chương 3), tham số metricType cho phép người dùng lựa chọn 4 loại độ đo chất lượng luật khác nhau gồm:

• Confidence (Độ tin cậy)
• Lift (Độ nâng)
• Leverage (Độ đòn bẩy)
• Conviction (Độ xác tín)

Kết luận

Khóa luận tốt nghiệp của sinh viên Anoulak Sidaralak đã hệ thống hóa một cách mạch lạc và toàn diện nền tảng lý thuyết về quy trình khám phá tri thức trong cơ sở dữ liệu và khai phá luật kết hợp. Công trình làm rõ bản chất toán học, các tính chất đại số và so sánh chi tiết cơ chế hoạt động giữa hai giải thuật nền tảng là Apriori và FP-growth. Thông qua việc phân tích bài toán thực tế tại hệ thống siêu thị Metro và thực nghiệm cấu hình trên phần mềm Weka, khóa luận đã chứng minh tính khả thi của việc ứng dụng kỹ thuật luật kết hợp trong phân tích hành vi mua sắm và hỗ trợ ra quyết định kinh doanh bán lẻ.

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

CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1. Khái niệm Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối ở thập kỷ 80 của thế kỷ XX. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu.

Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm khám phá tri thức trong cơ sở dữ liệu, để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn; trong đó khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu. Ở một mức độ trừu tượng nhất định có thể định nghĩa về khai phá dữ liệu: Data Mining là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khám phá tri thức (KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm đó được xem như hai lĩnh vực tương đương nhau. Nhưng, nếu phân chia một cách tách bạch thì khai phá dữ liệu là một bước chính trong quá trình KDD.

Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong CSDL. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất,. Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương pháp thống kê). Sau đây là các định nghĩa mang tính mô tả của nhiều tác giả về khai phá dữ liệu: Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phương pháp được dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu”.

Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong CSDL lớn”. 3 Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm thường nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu được”. Khai phá dữ liệu và phát hiện tri thức Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng thông tin có hiệu quả. Điều đó có nghĩa là từ các dữ liệu có sẵn phải tìm ra những thông tin tiềm ẩn mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng.

Thực hiện công việc đó chính là quá trình phát hiện tri thức trong cơ sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được các tri thức chính ra từ kỹ thuật khai phá dữ liệu. Nếu quan niệm tri thức là một quan hệ của các mẫu giữa các phần tử dữ liệu thì quá trình phát hiện tri thức chỉ toàn bộ quá trình trích xuất tri thức từ cơ sở dữ liệu, trong đó trải qua nhiều giai đoạn khác nhau như: Tìm hiểu và phát hiện vấn đề thu thập và tiền xử lý dữ liệu, phát hiện tri thức, minh họa và đánh giá tri thức đã phát hiện và đưa kết quả vào thực tế. Khai phá dữ liệu có những điểm khác nhau về mặt ngữ nghĩa so với phát hiện tri thức từ cơ sở dữ liệu nhưng thực tế ta thấy khai phá dữ liệu là chỉ một giai đoạn phát hiện tri thức trong một chuỗi các giai đoạn quá trình phát hiện tri thức trong cơ sở dữ liệu. Tuy nhiên đây là giai đoạn đóng vai trò chủ chốt và là giai đoạn chính tạo nên tính đa ngành của phát hiện tri thức trong cơ sở dữ liệu.

Quá trình khám phá tri thức trong CSDL Khám phá tri thức trong CSDL (KDD) là lĩnh vực liên quan đến các ngành như: thống kê, học máy, CSDL, thuật toán, trực quan hoá dữ liệu, tính toán song song và hiệu năng cao,… Mục đích của quá trình khám phá tri thức là rút ra tri thức từ dữ liệu trong CSDL lớn. Quá trình khai phá dữ liệu là quá trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở bất cứ bước nào. Quá trình đó có thể được mô tả theo hình sau: 4 Hình 1.1: Quá trình khám phá tri thức. Bước thứ nhất: Hình thành, xác định và định nghĩa bài toán.

Là tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. Bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức.

Do dữ liệu được lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và rời rạc hoá. Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu.

Giai đoạn này rất quan trọng, bao gồm các công đoạn như: chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, dùng phương pháp khai phá nào? Thông thường, các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đưa ra tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa trên dữ liệu hiện có. Tùy theo bài toán xác định được mà ta lựa chọn các phương pháp khai phá dữ liệu cho phù hợp. Bước thứ tư: Là hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện.

5 Bước thứ năm: Sử dụng các tri thức phát hiện được. Là hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Các kết quả của quá trình khám phá tri thức có thể được đưa và ứng dụng trong các lĩnh vực khác nhau.

Do các kết quả có thể là các dự đoán hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này. Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. Các phương pháp khai phá dữ liệu Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mục đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác định.

Có thể kể ra đây một vài phương pháp như: sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị trung bình, phát hiện luật kết hợp, …Các phương pháp trên có thể được phỏng theo và được tích hợp vào các hệ thống để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách thức về mặt hiệu quả và quy mô. Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm. - Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu tả các mẫu có thể khai thác được.

Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có mô hình chính xác cho dữ liệu. Tuy nhiên, nếu mô hình quá lớn thì khả năng dự đoán của học máy sẽ bị hạn chế. Như thế sẽ làm cho việc tìm kiếm phức tạp hơn cũng như hiểu được mô hình là không đơn giản hoặc sẽ không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Vì vậy, việc quan trọng là người phân tích dữ liệu là cần phải hiểu đầy đủ các giả thiết miêu tả.

Một điều cũng khá quan trọng là người thiết kế giải thuật cũng phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở lên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. 6 Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc lập mà biến đầu ra phụ thuộc vào.

Sau đó phải tìm những tham số mà bài toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với tham số được xác định dựa trên dữ liệu (trong một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập các dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu.

Mô hình sau đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi các tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS, … một số giải thuật học máy, mạng neuron, suy diễn hướng tình huống, các kỹ thuật phân lớp.