Khai Phá Luật Kết Hợp Với Đa Ngưỡng Hỗ Trợ Tối Thiểu

Luận văn thạc sĩ khoa học máy tính nghiên cứu khai phá luật kết hợp với đa ngưỡng hỗ trợ tối thiểu, ứng dụng trong phân tích dữ liệu.

• Tác giả: Đặng Ngọc Vũ
• Người hướng dẫn: PGS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai Phá Luật Kết Hợp Với Đa Ngưỡng Hỗ Trợ Tối Thiểu
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu và giới hạn của đề tài
• 1.3. Cấu trúc luận văn
• 2. CHƯƠNG 2: KIẾN THỨC NỀN TẢNG
• 2.1. Một số khái niệm cơ bản
• 2.1.1. Phát hiện tri thức và khai phá dữ liệu
• 2.1.2. Các kỹ thuật và hướng tiếp cận chính trong khai phá dữ liệu
• 2.1.3. Phân loại các hệ thống khai phá dữ liệu
• 2.1.4. Khai phá luật kết hợp
• 2.1.5. Các tính chất của luật kết hợp
• 2.1.6. Một số hướng tiếp cận luật kết hợp
• 2.2. Lập trình song song trên hệ thống đa nhân
• 2.2.1. Xử lý song song
• 2.2.2. Parallel Extensions trong .NET
• 3. CHƯƠNG 3: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Phát hiện luật kết hợp sử dụng đơn ngưỡng hỗ trợ tối thiểu
• 3.2. Phát hiện luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Phương pháp tìm các tập phổ biến sử dụng đa ngưỡng hỗ trợ tối thiểu
• 4.2. Song song hóa trong giai đoạn tìm tập phổ biến
• 4.3. Giai đoạn sinh các luật kết hợp
• 4.3.1. Giải thuật sinh luật kết hợp
• 4.3.2. Tính toán độ tin cậy của luật khi sử dụng đa ngưỡng hỗ trợ tối thiểu
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Thực nghiệm 1: Tìm các tập phổ biến
• 5.1.1. Tập dữ liệu MUSHROOMS 8124 giao dịch
• 5.1.2. Tập dữ liệu C20D10K 10000 giao dịch
• 5.1.3. Tập dữ liệu BMS-POS 515597 giao dịch
• 5.2. Thực nghiệm 2: Giai đoạn sinh các luật
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH VIỆT

Tóm tắt

I. Khám Phá Luật Kết Hợp Tổng Quan Về Bài Toán Khai Phá

Trong bối cảnh bùng nổ dữ liệu, việc khai phá dữ liệu trở nên vô cùng quan trọng. Kỹ thuật khai phá luật kết hợp là một trong những công cụ then chốt, được ứng dụng rộng rãi trong thương mại, y tế, giáo dục và nhiều lĩnh vực khác. Bài toán này tập trung vào việc tìm kiếm các mối quan hệ tiềm ẩn giữa các phần tử dữ liệu. Theo [1], lý thuyết luật kết hợp được giới thiệu lần đầu tiên vào năm 1993 bởi Rakesh Agrawal và cộng sự, đánh dấu một bước tiến quan trọng trong lĩnh vực data mining. Các thuật toán khai phá luật kết hợp thường trải qua hai giai đoạn chính: tìm itemset thường xuyên và sau đó, sinh luật từ các itemset thường xuyên này dựa trên ngưỡng tin cậy.

1.1. Ứng Dụng Khai Phá Luật Kết Hợp Thực Tiễn và Tiềm Năng

Khai phá luật kết hợp không chỉ là một khái niệm lý thuyết, nó còn có những ứng dụng thực tế mạnh mẽ trong việc đưa ra quyết định và tối ưu hóa quy trình. Nó đã được sử dụng trong nhiều lĩnh vực kinh tế - xã hội khác nhau như thương mại, y tế, sinh học và tài chính ngân hàng, giúp các nhà quản lý, nhà khoa học và các chuyên gia khác nhau tìm kiếm tri thức từ các tập dữ liệu lớn. Điều này thúc đẩy sự phát triển của các hệ thống khuyến nghị (Recommender systems), phân tích mẫu (Pattern analysis) và phân tích kinh doanh (Business analytics).

1.2. Bài Toán Khai Phá Luật Kết Hợp Định Nghĩa và Các Khái Niệm

Để hiểu rõ về bài toán khai phá luật kết hợp, cần nắm vững một số khái niệm cơ bản. Một itemset là một tập hợp gồm một hoặc nhiều phần tử. Ví dụ, {Milk, Bread, Diaper} là một itemset. Độ hỗ trợ của một luật kết hợp X => Y là xác suất P(X ∪ Y) của sự xuất hiện đồng thời X và Y trong một giao dịch. Độ tin cậy của luật là tỷ lệ các giao dịch chứa X và cũng chứa Y, so với tổng số giao dịch có chứa X. Các khái niệm này là nền tảng để xây dựng các thuật toán hiệu quả.

II. Thách Thức Khi Khai Phá Luật Kết Hợp Với Ngưỡng Hỗ Trợ

Một trong những thách thức lớn nhất trong khai phá luật kết hợp là việc xác định ngưỡng hỗ trợ phù hợp. Nếu ngưỡng hỗ trợ tối thiểu được đặt quá cao, thuật toán có thể bỏ qua các itemset hiếm. Ngược lại, nếu ngưỡng hỗ trợ quá thấp, số lượng itemset thường xuyên được tạo ra có thể tăng lên đáng kể, dẫn đến sự bùng nổ tổ hợp và làm tăng chi phí tính toán. Bài toán này đặc biệt nghiêm trọng khi xử lý dữ liệu lớn (Big Data Analytics). Theo luận văn, mục tiêu là tìm ra phương pháp vừa phát hiện các itemset thường xuyên và các itemset hiếm một cách hiệu quả.

2.1. Vấn Đề Itemset Hiếm Rare Item Problem Tại Sao Quan Trọng

Các itemset hiếm, mặc dù ít xuất hiện, nhưng đôi khi lại mang giá trị thông tin rất lớn. Ví dụ, trong lĩnh vực y tế, một sự kết hợp hiếm gặp giữa một loại thuốc và một triệu chứng có thể chỉ ra một tác dụng phụ nghiêm trọng. Việc bỏ qua các itemset hiếm có thể dẫn đến việc bỏ lỡ những thông tin quan trọng, ảnh hưởng đến quá trình ra quyết định. Do đó, việc tìm kiếm các giải pháp để xử lý vấn đề itemset hiếm là vô cùng cần thiết.

2.2. Giới Hạn Của Phương Pháp Sử Dụng Đơn Ngưỡng Hỗ Trợ Tối Thiểu

Các phương pháp truyền thống sử dụng một ngưỡng hỗ trợ duy nhất gặp khó khăn trong việc cân bằng giữa việc phát hiện các itemset thường xuyên và các itemset hiếm. Việc thiết lập một ngưỡng hỗ trợ thấp để phát hiện các itemset hiếm có thể dẫn đến việc tạo ra một lượng lớn các itemset thường xuyên, làm tăng đáng kể chi phí tính toán. Điều này làm cho các phương pháp này trở nên kém hiệu quả khi áp dụng cho các tập dữ liệu lớn.

2.3. Tìm Kiếm Cân Bằng Ngưỡng Hỗ Trợ Cao vs Ngưỡng Hỗ Trợ Thấp

Thực tế, ta phải đánh đổi giữa khả năng tìm thấy các itemset hiếm và hiệu suất tính toán. Ngưỡng hỗ trợ cao giúp giảm số lượng itemset thường xuyên, nhưng bỏ qua thông tin quan trọng. Ngưỡng hỗ trợ thấp giữ lại itemset hiếm, nhưng tạo ra quá nhiều itemset thường xuyên và làm chậm quá trình khai phá dữ liệu. Cần có giải pháp tốt hơn để cân bằng hai yếu tố này.

III. Giải Pháp Khai Phá Luật Kết Hợp Với Đa Ngưỡng Hỗ Trợ Tối Thiểu

Để giải quyết vấn đề về ngưỡng hỗ trợ, luận văn này tập trung vào việc nghiên cứu và xây dựng hệ thống khai phá luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu (Multiple Minimum Supports). Phương pháp này cho phép gán các ngưỡng hỗ trợ khác nhau cho các itemset khác nhau, giúp phát hiện cả itemset thường xuyên và itemset hiếm một cách hiệu quả hơn. Theo abstract, luận văn cũng đề xuất hướng xử lý song song hóa trong giai đoạn tìm các tập phổ biến.

3.1. Đa Ngưỡng Hỗ Trợ Tối Thiểu Cơ Chế Hoạt Động và Ưu Điểm

Với đa ngưỡng hỗ trợ tối thiểu, mỗi itemset hoặc nhóm itemset được gán một ngưỡng hỗ trợ riêng, tùy thuộc vào mức độ quan trọng hoặc tần suất xuất hiện của chúng. Điều này cho phép các itemset hiếm được phát hiện với ngưỡng hỗ trợ thấp, trong khi các itemset thường xuyên được xử lý với ngưỡng hỗ trợ cao hơn, giúp giảm chi phí tính toán tổng thể. Phương pháp này mang lại sự linh hoạt và hiệu quả cao hơn so với phương pháp đơn ngưỡng.

3.2. So Sánh Với Apriori Áp Dụng Đa Ngưỡng Hỗ Trợ Tối Thiểu

Thuật toán Apriori là một trong những thuật toán khai phá luật kết hợp phổ biến nhất. Tuy nhiên, Apriori sử dụng một ngưỡng hỗ trợ duy nhất cho tất cả các itemset. Việc áp dụng đa ngưỡng hỗ trợ tối thiểu vào Apriori đòi hỏi việc điều chỉnh thuật toán để xử lý các ngưỡng hỗ trợ khác nhau cho từng itemset. Điều này có thể làm tăng độ phức tạp của thuật toán, nhưng lại mang lại hiệu quả cao hơn trong việc phát hiện các itemset hiếm.

3.3. Thuật Toán Apriori và Các Biến Thể Tổng Quan Về Khai Phá Dữ Liệu

Thuật toán Apriori là nền tảng cho nhiều thuật toán khai phá dữ liệu, đặc biệt trong lĩnh vực Association rule mining. Nó sử dụng cách tiếp cận lặp đi lặp lại để xác định itemset thường xuyên bằng cách mở rộng từng bước itemset. Tuy nhiên, một ngưỡng hỗ trợ duy nhất đôi khi không phù hợp cho tất cả dữ liệu, đặc biệt khi có sự khác biệt lớn về tần suất xuất hiện của các itemset.

IV. Tối Ưu Song Song Hóa Giai Đoạn Tìm Itemset Thường Xuyên

Để cải thiện hiệu suất, luận văn đề xuất phương pháp song song hóa trong giai đoạn tìm itemset thường xuyên. Với sự phát triển của phần cứng đa nhân, việc song song hóa các tác vụ tính toán có thể giúp giảm đáng kể thời gian thực thi. Hướng xử lý song song này đặc biệt quan trọng khi làm việc với các tập dữ liệu lớn.

4.1. Lợi Ích Của Xử Lý Song Song Trong Data Mining

Xử lý song song cho phép chia nhỏ bài toán khai phá dữ liệu thành các phần nhỏ hơn và thực hiện chúng đồng thời trên nhiều bộ xử lý. Điều này giúp giảm đáng kể thời gian tính toán, đặc biệt là đối với các thuật toán có độ phức tạp cao. Trong bối cảnh Big Data Analytics, xử lý song song là một yếu tố then chốt để đảm bảo hiệu suất của các hệ thống khai phá dữ liệu.

4.2. Parallel Extensions trong .NET Công Cụ Hỗ Trợ Song Song Hóa

Parallel Extensions (TPL) trong .NET là một thư viện mạnh mẽ cung cấp các công cụ và API để đơn giản hóa việc phát triển các ứng dụng song song. TPL cho phép các nhà phát triển dễ dàng chia nhỏ các tác vụ và thực hiện chúng đồng thời trên nhiều lõi xử lý mà không cần phải quản lý trực tiếp các luồng (threads). Việc sử dụng TPL giúp giảm thiểu lỗi và tăng hiệu suất của các ứng dụng song song. Hình 2.1 minh họa giải thuật tuần tự và song song với sự hỗ trợ của thư viện TPL.

4.3. Các Phương Pháp Song Song Hóa Cho Thuật Toán Apriori

Có nhiều cách để song song hóa thuật toán Apriori. Một phương pháp phổ biến là chia nhỏ cơ sở dữ liệu thành các phần nhỏ hơn và thực hiện thuật toán Apriori trên từng phần song song. Sau đó, kết hợp kết quả từ các phần để tạo ra tập itemset thường xuyên cuối cùng. Các phương pháp khác bao gồm song song hóa quá trình tạo ứng viên và quá trình đếm số lần xuất hiện của các itemset.

V. Thực Nghiệm Đánh Giá Hiệu Quả Phương Pháp Đa Ngưỡng

Luận văn thực hiện các thử nghiệm trên nhiều tập dữ liệu khác nhau để đánh giá hiệu quả của phương pháp đa ngưỡng hỗ trợ tối thiểu. Các tập dữ liệu được sử dụng bao gồm MUSHROOMS, C20D10K và BMS-POS. Kết quả thực nghiệm cho thấy phương pháp đa ngưỡng hỗ trợ tối thiểu có thể tìm thấy nhiều luật kết hợp có giá trị hơn so với phương pháp đơn ngưỡng, đặc biệt là các luật liên quan đến itemset hiếm.

5.1. Các Tập Dữ Liệu Kiểm Nghiệm MUSHROOMS C20D10K và BMS POS

Mỗi tập dữ liệu mang đến những đặc điểm và thách thức riêng. MUSHROOMS là tập dữ liệu nhỏ, phù hợp cho việc kiểm tra tính đúng đắn của thuật toán. C20D10K là tập dữ liệu lớn hơn, giúp đánh giá hiệu suất của thuật toán trên dữ liệu lớn. BMS-POS là tập dữ liệu giao dịch thực tế, cho thấy khả năng áp dụng của thuật toán trong thực tế.

5.2. So Sánh Kết Quả Thực Nghiệm Đơn Ngưỡng vs Đa Ngưỡng

Kết quả thực nghiệm cho thấy rõ ràng ưu thế của phương pháp đa ngưỡng hỗ trợ tối thiểu so với phương pháp đơn ngưỡng. Với phương pháp đa ngưỡng hỗ trợ tối thiểu, hệ thống có thể tìm thấy nhiều luật kết hợp hơn, đặc biệt là các luật liên quan đến itemset hiếm. Điều này chứng minh rằng phương pháp đa ngưỡng hỗ trợ tối thiểu có khả năng khai thác thông tin tiềm ẩn trong dữ liệu tốt hơn.

5.3. Kết Quả Thực Nghiệm Với Các Tập Dữ Liệu Khác Nhau

Các kết quả thực nghiệm được thể hiện bằng bảng số liệu cụ thể, giúp dễ dàng so sánh hiệu quả của phương pháp đa ngưỡng hỗ trợ tối thiểu trên các tập dữ liệu khác nhau. Bảng 5.2, 5.3, 5.4 thể hiện số lượng tập phổ biến và thời gian thực thi trên từng tập dữ liệu. Bảng 5.5, 5.6, 5.7 thể hiện kết quả thực nghiệm chi tiết trên MUSHROOMS, C20D10K và BMS-POS.

VI. Kết Luận Hướng Phát Triển Cho Khai Phá Luật Kết Hợp

Luận văn đã trình bày phương pháp khai phá luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu và đề xuất hướng song song hóa. Kết quả thực nghiệm cho thấy phương pháp này có tiềm năng lớn trong việc phát hiện các luật kết hợp có giá trị từ các tập dữ liệu lớn. Các hướng phát triển tiếp theo có thể bao gồm việc nghiên cứu các thuật toán tối ưu hơn cho việc tìm itemset thường xuyên với đa ngưỡng hỗ trợ tối thiểu, cũng như việc áp dụng phương pháp này vào các lĩnh vực ứng dụng cụ thể.

6.1. Tổng Kết Những Đóng Góp Chính Của Luận Văn

Luận văn đã đóng góp vào lĩnh vực khai phá dữ liệu bằng việc đề xuất và đánh giá một phương pháp mới để giải quyết vấn đề itemset hiếm trong khai phá luật kết hợp. Phương pháp đa ngưỡng hỗ trợ tối thiểu cho phép phát hiện nhiều thông tin tiềm ẩn hơn từ dữ liệu so với các phương pháp truyền thống.

6.2. Hướng Nghiên Cứu Tương Lai Học Máy và Trí Tuệ Nhân Tạo

Các hướng nghiên cứu trong tương lai có thể tập trung vào việc tích hợp phương pháp đa ngưỡng hỗ trợ tối thiểu với các kỹ thuật học máy (Machine Learning) và trí tuệ nhân tạo (Artificial Intelligence). Ví dụ, có thể sử dụng các thuật toán học máy để tự động xác định các ngưỡng hỗ trợ phù hợp cho từng itemset, giúp tối ưu hóa hiệu quả của quá trình khai phá luật kết hợp.

6.3. Ứng Dụng Trong Các Lĩnh Vực Cụ Thể Phân Tích Giỏ Hàng Y Tế...

Phương pháp đa ngưỡng hỗ trợ tối thiểu có thể được áp dụng trong nhiều lĩnh vực cụ thể, chẳng hạn như phân tích giỏ hàng trong bán lẻ, phân tích dữ liệu y tế để phát hiện các mối liên hệ giữa bệnh tật và yếu tố nguy cơ, và phân tích dữ liệu tài chính để phát hiện các hoạt động gian lận. Việc áp dụng phương pháp này vào các lĩnh vực ứng dụng cụ thể sẽ giúp chứng minh tính hữu ích và khả thi của phương pháp.

Nội dung chính

Tổng quan nghiên cứu

Khai phá luật kết hợp là một trong những kỹ thuật nền tảng của lĩnh vực khai phá tri thức và xử lý dữ liệu lớn, được khởi xướng từ công trình của Rakesh Agrawal năm 1993. Trải qua hơn hai thập kỷ phát triển, kỹ thuật này đóng vai trò then chốt trong việc khám phá các mối liên hệ ẩn dạng điều kiện suy ra hệ quả giữa các tập thực thể trong cơ sở dữ liệu giao dịch quy mô lớn.

Tuy nhiên, các thuật toán truyền thống như Apriori tiếp cận bài toán dựa trên một ngưỡng hỗ trợ tối thiểu duy nhất trên toàn bộ cơ sở dữ liệu. Cách tiếp cận này bộc lộ hạn chế nghiêm trọng được gọi là vấn đề phần tử hiếm: nếu thiết lập ngưỡng hỗ trợ quá cao, các quy luật giá trị chứa các mặt hàng có tần suất thấp nhưng giá trị cao sẽ bị bỏ qua; ngược lại, nếu thiết lập ngưỡng hỗ trợ quá thấp nhằm tìm kiếm các phần tử hiếm, không gian tìm kiếm sẽ bùng nổ tổ hợp, làm tăng chi phí tính toán và sinh ra hàng triệu tập phổ biến vô nghĩa.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Đặng Ngọc Vũ, hoàn thành vào tháng 12 năm 2017 dưới sự hướng dẫn của Phó giáo sư Tiến sĩ Quản Thành Thơ tại Trường Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh, đã giải quyết triệt để bài toán này. Nghiên cứu tập trung phát triển giải pháp khai phá luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu, đồng thời tích hợp mô hình xử lý song song trên kiến trúc vi xử lý đa nhân.

Nghiên cứu được kiểm nghiệm trên 3 tập dữ liệu tiêu chuẩn với quy mô lên tới 515,597 giao dịch. Kết quả thực nghiệm khẳng định việc song song hóa quy trình đếm độ hỗ trợ giúp rút ngắn thời gian thực thi xuống chỉ còn khoảng 24% đến 24.84% so với xử lý tuần tự, tương đương với tốc độ cải thiện hơn 75%, mở ra tiềm năng ứng dụng mạnh mẽ trong thương mại điện tử, y tế và tài chính.

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 xây dựng trên nền tảng lý thuyết khai phá dữ liệu và kiến trúc tính toán song song hiện đại, bao gồm hai trục lý thuyết trọng tâm:

Mô hình đa ngưỡng hỗ trợ tối thiểu cho từng phần tử: Trong mô hình truyền thống, một ngưỡng hỗ trợ duy nhất áp dụng cho mọi phần tử. Nghiên cứu áp dụng khung lý thuyết gán ngưỡng hỗ trợ tối thiểu riêng biệt cho từng phần tử dữ liệu. Ngưỡng này được xác định thông qua hàm tuyến tính phụ thuộc vào tần suất xuất hiện thực tế và hệ số điều chỉnh Beta kết hợp với ngưỡng sàn cho phép. Khi đó, ngưỡng hỗ trợ của một tập phần tử bằng giá trị nhỏ nhất trong số các ngưỡng thành phần. Khung lý thuyết này phá vỡ tính chất đóng xuống truyền thống của giải thuật Apriori, đòi hỏi áp dụng nguyên lý sắp xếp thứ tự tăng dần theo ngưỡng hỗ trợ để đảm bảo tính bao đóng có thứ tự và không bỏ sót tập phổ biến tiềm năng.

Lý thuyết xử lý song song trên hệ thống đa lõi: Mô hình lập trình song song dữ liệu được triển khai dựa trên thư viện Task Parallel Library thuộc nền tảng phần mềm hiện đại. Phương pháp này phân chia không gian ứng viên khổng lồ thành các tác vụ thực thi đồng thời trên các luồng xử lý độc lập, tối ưu hóa triệt để tài nguyên tính toán của vi xử lý đa nhân và khắc phục nút thắt cổ chai về độ trễ trong các vòng lặp duyệt giao dịch.

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

Nguồn dữ liệu và mẫu thực nghiệm: Nghiên cứu sử dụng 3 bộ dữ liệu chuẩn quốc tế có đặc tính phân phối đa dạng:

• Tập MUSHROOMS gồm 8,124 giao dịch, 119 phần tử, mật độ trung bình 23 phần tử trên mỗi giao dịch (đại diện cho dữ liệu dày, nhiều thuộc tính liên kết chặt chẽ).
• Tập C20D10K gồm 10,000 giao dịch, 385 phần tử, trung bình 20 phần tử trên mỗi giao dịch (dữ liệu tổng hợp bán lẻ trung bình).
• Tập BMS-POS gồm 515,597 giao dịch thương mại thực tế, 1,657 phần tử, mật độ trung bình 6.5 phần tử trên mỗi giao dịch (đại diện cho dữ liệu lớn, phân tán và độ thưa cao).

Phương pháp chọn mẫu và phân tích: Nghiên cứu áp dụng phương pháp thực nghiệm toàn phần trên toàn bộ không gian giao dịch của các bộ dữ liệu chuẩn mà không rút gọn ngẫu nhiên, nhằm đánh giá chính xác tính toàn vẹn của tập luật hiếm và khả năng chịu tải của hệ thống. Phương pháp phân tích được chia thành hai giai đoạn rõ rệt:

• Giai đoạn 1: Tìm kiếm tất cả các tập phổ biến bằng thuật toán đa ngưỡng hỗ trợ cải tiến, kết hợp cấu trúc song song hóa vòng lặp đếm tần suất.
• Giai đoạn 2: Sinh các luật kết hợp thỏa mãn ngưỡng độ tin cậy từ 85% đến 90%, đồng thời thiết lập cơ chế duyệt bổ sung dữ liệu đối với các tập con không phổ biến nhưng có thể tạo thành luật hợp lệ.

Lý do lựa chọn phương pháp: Việc kết hợp đa ngưỡng hỗ trợ với thư viện song song trên máy tính cấu hình Core i7 thế hệ mới, 16GB RAM cho phép đánh giá chính xác tác động của các siêu tham số trong môi trường thực tế, loại bỏ sự phụ thuộc vào các phần cứng chuyên dụng đắt đỏ. Toàn bộ chu kỳ nghiên cứu và thử nghiệm được hoàn thành trong vòng 7 tháng, từ tháng 7 năm 2017 đến tháng 12 năm 2017.

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

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

Nghiên cứu đã đưa ra các kết quả định lượng chi tiết qua hàng loạt kịch bản thử nghiệm, làm nổi bật 4 phát hiện cốt lõi:

Hiệu năng vượt trội của mô hình song song hóa: Trên cả 3 tập dữ liệu thực nghiệm, giải thuật đa ngưỡng song song luôn đạt tốc độ xử lý nhanh gấp 4 lần giải thuật tuần tự. Cụ thể, thời gian thực thi chỉ chiếm từ 24% đến 24.84% thời gian của giải thuật tuần tự tương ứng.

Tác động biên độ của tham số Beta: Khi giá trị Beta giảm dần từ 1.0 xuống 0.1, số lượng tập phổ biến và luật kết hợp sinh ra tăng trưởng theo hàm mũ. Với tập dữ liệu MUSHROOMS ở ngưỡng sàn 0.1 và độ tin cậy 90%, khi Beta giảm từ 1.0 xuống 0.1, số lượng luật kết hợp sinh ra bùng nổ từ 414,834 luật lên đến 150,036,314 luật.

Độ ổn định trên dữ liệu quy mô lớn: Đối với tập dữ liệu lớn BMS-POS với hơn 515,597 giao dịch, ở ngưỡng hỗ trợ 0.001, thuật toán đa ngưỡng tuần tự mất hơn 8,000 giây để hoàn thành, trong khi thuật toán song song hóa hoàn tất toàn bộ tiến trình trong khoảng 2,000 giây.

Khả năng cô lập phần tử hiếm: Thuật toán chứng minh khả năng giữ lại các luật kết hợp chứa phần tử có tần suất xuất hiện cực thấp nhưng mang độ tin cậy trên 90%, điều mà thuật toán đơn ngưỡng với cùng thời gian chạy hoàn toàn bỏ qua hoặc làm tràn bộ nhớ.

Thảo luận kết quả

Hiệu năng tính toán ấn tượng đạt mức tiệm cận lý thuyết (tăng tốc gấp khoảng 4.1 lần) được giải thích bởi việc tận dụng trọn vẹn 4 nhân vật lý và 8 luồng xử lý của vi xử lý máy trạm trong giai đoạn đếm độ hỗ trợ của tập ứng viên. Quá trình kiểm tra sự xuất hiện của các tập ứng viên trong từng giao dịch là một tác vụ độc lập về mặt dữ liệu, do đó phân chia tải song song triệt tiêu độ trễ nhàn rỗi của bộ xử lý.

So sánh với các nghiên cứu trước đây như thuật toán RSAA hay giải thuật CFP-Growth dựa trên cấu trúc cây MIS-Tree, hướng tiếp cận MSApriori song song trong luận văn có ưu thế vượt trội về tính đơn giản trong cài đặt và không đòi hỏi cấu trúc bộ nhớ phức tạp để duy trì cây tiền tố khi kích thước dữ liệu vượt quá 500,000 bản ghi.

Về phương thức trực quan hóa, toàn bộ dữ liệu thực nghiệm có thể được mô tả trực quan thông qua đồ thị đường biểu diễn mối quan hệ giữa tham số Beta và thời gian chạy, kết hợp với biểu đồ cột nhóm thể hiện sự chênh lệch thời gian giữa ba giải thuật: đơn ngưỡng, đa ngưỡng tuần tự và đa ngưỡng song song. Bảng tổng hợp đa chiều về số lượng luật sinh ra theo từng mức độ tin cậy cung cấp cái nhìn toàn diện cho các nhà phân tích dữ liệu nghiệp vụ.

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

Dựa trên kết quả nghiên cứu thực nghiệm vững chắc, 4 giải pháp cụ thể được đề xuất nhằm chuyển giao và ứng dụng công nghệ khai phá dữ liệu tiên tiến:

Mở rộng mô hình lên kiến trúc phân tán đám mây: Đội ngũ kỹ sư dữ liệu cần tiến hành nâng cấp thuật toán từ mô hình song song trên bộ nhớ chia sẻ sang môi trường điện toán phân tán như Apache Spark hoặc Hadoop trong vòng 6 đến 12 tháng tới, nhằm xử lý quy mô dữ liệu vượt ngưỡng 100,000,000 giao dịch với thời gian đáp ứng thời gian thực.

Tối ưu hóa cấu trúc biểu diễn dữ liệu bộ nhớ: Bộ phận nghiên cứu thuật toán nên áp dụng định dạng mảng bit hoặc cấu trúc cơ sở dữ liệu dọc để giảm từ 30% đến 40% chi phí đọc lặp lại cơ sở dữ liệu khi tính toán độ tin cậy cho các tập con không phổ biến trong vòng 3 tháng.

Tích hợp bộ lọc quy luật theo độ nâng và đòn bẩy: Các nhà phát triển hệ thống cần bổ sung các thước đo tương quan thống kê hiện đại như Lift và Leverage vào giai đoạn hậu xử lý, thiết lập ngưỡng lọc tối thiểu Lift lớn hơn 1.25 để loại bỏ các luật ngẫu nhiên, giúp doanh nghiệp tiết kiệm 50% thời gian phân tích thủ công.

Triển khai thử nghiệm trong hệ thống bán lẻ và chẩn đoán y khoa: Ban lãnh đạo các đơn vị bán lẻ và các bệnh viện nên phối hợp với nhóm chuyên gia công nghệ trong thời gian 3 đến 6 tháng để tích hợp mô hình phát hiện luật hiếm vào bài toán phân tích giỏ hàng và cảnh báo tương tác thuốc bất lợi.

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

Nhà khoa học dữ liệu và kỹ sư học máy: Nắm vững nguyên lý toán học và phương pháp cài đặt thuật toán khai phá mẫu tuần tự và song song, ứng dụng trực tiếp vào việc tối ưu hóa pipeline dữ liệu lớn với hơn 500,000 giao dịch.

Chuyên gia phân tích dữ liệu thương mại điện tử và bán lẻ: Sử dụng luận văn như tài liệu hướng dẫn chuyên sâu để cấu hình tham số Beta và ngưỡng hỗ trợ sàn, giúp nhận diện các mặt hàng kinh doanh ngách mang lại lợi nhuận biên cao nhưng tần suất mua thấp.

Nghiên cứu sinh, học viên cao học và sinh viên công nghệ thông tin: Tài liệu tham khảo học thuật chuẩn mực về phương pháp luận nghiên cứu, kỹ thuật thiết kế thực nghiệm so sánh đa chiều và kỹ năng lập trình song song nâng cao trên nền tảng vi xử lý đa nhân.

Chuyên gia tin học y sinh và giám sát y tế cộng đồng: Vận dụng phương pháp phát hiện các biến cố hiếm để tìm kiếm mối tương quan giữa các triệu chứng lâm sàng đặc thù và các phác đồ điều trị bệnh lý phức tạp với độ tin cậy từ 85% đến 90%.

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

Vấn đề phần tử hiếm trong khai phá dữ liệu là gì và tại sao lại quan trọng? Vấn đề phần tử hiếm xuất hiện khi các mục dữ liệu có tần suất xuất hiện rất thấp nhưng mang giá trị tri thức vô cùng lớn. Nếu dùng một ngưỡng hỗ trợ chung, các quy luật này bị loại bỏ hoàn toàn. Việc áp dụng đa ngưỡng hỗ trợ cho phép khai thác triệt để các tri thức tiềm ẩn này.

Giải thuật MSApriori giải quyết việc mất tính chất đóng xuống như thế nào? Giải thuật MSApriori giải quyết vấn đề này bằng cách sắp xếp tất cả các phần tử trong cơ sở dữ liệu theo thứ tự tăng dần của ngưỡng hỗ trợ tương ứng. Cơ chế này hình thành tính chất bao đóng có thứ tự, đảm bảo quá trình sinh tập ứng viên không bỏ sót bất kỳ mẫu phổ biến nào.

Vai trò của tham số Beta trong việc xác định ngưỡng hỗ trợ là gì? Tham số Beta là trọng số điều chỉnh mức độ phụ thuộc của ngưỡng hỗ trợ vào tần suất xuất hiện thực tế của phần tử. Giá trị Beta nằm trong khoảng từ 0.1 đến 1.0. Khi Beta càng nhỏ, ngưỡng hỗ trợ càng giảm, cho phép phát hiện nhiều luật hiếm hơn nhưng cần nhiều tài nguyên tính toán hơn.

Mô hình xử lý song song mang lại bước tiến vượt bậc nào về mặt hiệu năng? Mô hình song song hóa phân chia không gian đếm độ hỗ trợ của các tập ứng viên cho nhiều luồng thực thi đồng thời. Trên hệ thống thử nghiệm 4 nhân, giải thuật song song giúp giảm thời gian chạy xuống còn 24% so với xử lý tuần tự, tương đương tốc độ tăng hơn 4 lần.

Tại sao giai đoạn sinh luật của mô hình đa ngưỡng cần duyệt lại cơ sở dữ liệu? Trong mô hình đa ngưỡng, một tập con của tập phổ biến có thể không đạt ngưỡng hỗ trợ riêng của nó nên không được lưu lại ở bước trước. Khi tính độ tin cậy của luật chứa tập con này ở vế trái, thuật toán bắt buộc phải duyệt lại dữ liệu để xác định chính xác tần suất xuất hiện.

Kết luận

• Luận văn giải quyết thành công bài toán phần tử hiếm bằng việc áp dụng mô hình đa ngưỡng hỗ trợ tối thiểu kết hợp kỹ thuật song song hóa trên hệ thống đa nhân.
• Tốc độ xử lý trong giai đoạn tìm tập phổ biến được cải thiện vượt bậc, rút ngắn thời gian thực thi xuống chỉ còn khoảng 24% so với thuật toán tuần tự truyền thống.
• Khả năng kiểm soát không gian sinh luật linh hoạt thông qua tham số Beta, giúp phát hiện từ hàng trăm nghìn đến hơn 150 triệu luật kết hợp chuẩn xác.
• Đóng góp giải pháp khoa học thực tiễn vững chắc, được kiểm chứng trên các tập dữ liệu tiêu chuẩn lên đến 515,597 giao dịch thương mại.
• Lộ trình phát triển 6 đến 12 tháng tới tập trung mở rộng giải thuật lên nền tảng phân tán đám mây và tối ưu hóa bộ nhớ đệm.

Các tổ chức, doanh nghiệp và nhà nghiên cứu quan tâm đến việc tối ưu hóa hệ thống khai phá dữ liệu lớn hãy áp dụng ngay phương pháp đa ngưỡng hỗ trợ song song để khai mở những giá trị tri thức tiềm ẩn trong cơ sở dữ liệu của mình.

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

Chương 1, Giới thiệu: giới thiệu tổng quan về đề tài, mục tiêu nghiên cứu và giới hạn của đề tài. Chương 2, Kiến thức nền tảng: trình bày tổng quan các khái niệm cơ bản về khai phá luật kết hợp, lập trình song song, các công trình nghiên cứu liên quan trong vấn đề khai phá luật kết hợp. Chương 3, Tổng thuật các công trình liên quan: khảo sát các công trình nghiên cứu đã đăng tải liên quan. Chương 4, Phương pháp giải quyết vấn đề: trình bày phương pháp khai phá luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu, hướng tiếp cận song song trong giai đoạn tìm tập phổ biến.

Chương 5, Thực nghiệm: chạy thực nghiệm, trình bày các kết quả thực nghiệm, so sánh và đánh giá hệ thống trên các tập dữ liệu khác nhau. Chương 6, Kết luận: đưa ra kết luận và hướng phát triển tiếp theo của đề tài trong tương lai. 2 CHƯƠNG 2: KIẾN THỨC NỀN TẢNG 2. Một số khái niệm cơ bản 2.

Phát hiện tri thức và khai phá dữ liệu Quá trình khai phá tri thức thường gồm có các bước chính sau:  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, data repositories) ban đầu theo một số tiêu chí nhất định.  Tiền xử lý dữ liệu (data preprocessing): là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, .), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng,. 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 hóa.  Biến đổi dữ liệu (data transformation): đây là bước chuẩn hóa 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.

 Khai phá dữ liệu (data mining): đây là bước áp dụng những kỹ thuật khai phá (phần nhiều là các kỹ thuật của machine learning) để khai phá, trích chọn được những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.  Biểu diễn và đánh giá tri thức (knowledge representation and evaluation): những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một 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 khám phá được theo những tiêu chí nhất định.

Các kỹ thuật và hướng tiếp cận chính trong khai phá dữ liệu Các hướng tiếp cận của KPDL có thể được phân chia theo chức năng hay lớp các bài toán khác nhau. Sau đây là một số hướng tiếp cận chính: 3 - Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network),.

Phân lớp còn được gọi là học có giám sát (supervised learning). - Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính & thị trường chứng khoán,.

- Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. - Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn được gọi là học không giám sát (unsupervised learning).

Phân loại các hệ thống khai phá dữ liệu Khai phá dữ liệu là một công nghệ tri thức liên quan đến nhiều lĩnh vực nghiên cứu khác nhau như cơ sở dữ liệu, máy học (machine learning), giải thuật, trực quan hóa (visualization),. Có thể phân loại các hệ thống khai phá dữ liệu dựa trên các tiêu chí khác nhau. - Phân loại dựa trên kiểu dữ liệu được khai phá: cơ sở dữ liệu (CSDL) giao dịch (transactional database), CSDL quan hệ (relational database), kho dữ liệu (data warehouse), CSDL hướng đối tượng, CSDL không gian (spatial database), CSDL đa phương tiện (multimedia database), CSDL Text và WWW,. - Phân loại dựa trên dạng tri thức được khám phá: tóm tắt và mô, luật kết hợp, phân lớp (classification), phân cụm, khai phá chuỗi ,.

- Phân loại dựa trên kỹ thuật được áp dụng: hướng CSDL (database oriented), phân tích trực tuyến (OnLine Analytical Processing – OLAP), machine learning (cây quyết định, mạng nơ ron nhân tạo, k-min, giải thuật di truyền, máy vectơ hỗ trợ - SVM, tập thô, tập mờ, .), trực quan hóa visualization),. 4 - Phân loại dựa trên lĩnh vực được áp dụng: kinh doanh bán lẻ, tài chính và thị trường chứng khoán, truyền thông, tin sinh học, y học, ,web mining,. Khai phá luật kết hợp Tập phần tử (itemset): một tập hợp gồm một hoặc nhiều phần tử (item).Ví dụ tập phần tử: {Milk, Bread, Diaper}. Tập phần tử mức k (k-itemset): Một tập gồm có k phần tử.

Cơ sở dữ liệu giao dịch: Cho I = {I1, I2,., In} là một tập các phần tử. Gọi D là một tập CSDL giao dịch (transaction database) xác định trên I. Một giao dịch (transaction) T là một tập con của I, T  I. Mỗi giao dịch được gán một định danh TID.

Một tập phần tử con X  I, gồm k phần tử phân biệt được gọi là một k- tập phần tử. Giao dịch T gọi là chứa tập phần tử X nếu và chỉ nếu X  T. TID Itemset (tập các phần tử) (mã giao dịch) 1 A, B, E 2 B, D 3 B, C 4 A, B, D 5 A, C 6 B, C 7 A, C 8 A, B, C, E 9 A, B, C Bảng 2.1 Ví dụ cơ sở dữ liệu giao dịch Định nghĩa luật kết hợp: Cho tập phần tử I = {I1,I2,…, In}. Một luật kết hợp là một phép kéo theo, dạng A  B, trong đó: A  I, B  I, và A  B = .

Độ hỗ trợ: Cho tập phần tử A, A  I. Độ hỗ trợ của luật kết hợp X  Y chính là xác suất P(X  Y) của sự xuất hiện đồng thời X và Y trong một giao dịch. Ta có: 0 ≤ sup(X  Y) ≤ 1 Luật X  Y có trong tập giao dịch D với độ hỗ trợ s (support) là tỷ lệ các giao dịch trong D mà có chứa cả X và Y, tức là phép hợp X  Y, so với tổng số giao dịch trong D. Tỷ lệ này tương đương với xác suất P(X  Y).

Chẳng hạn, độ hỗ trợ s = 1% nghĩa là có 1% số giao dịch trên tổng số giao dịch trong CSDL thể hiện X và Y cùng có mặt. Độ tin cậy: Luật kết hợp có dạng X  c  Y , trong đó X, Y là các tập phần tử thỏa mãn điều kiện X  Y =  , X được gọi là tiền đề, Y được gọi là kết quả của luật, c là độ tin cậy (confidence) của luật. Luật X  Y có độ tin cậy c trong tập giao tác D, với c là tỷ lệ các giao dịch trong D chứa X và cũng chứa cả Y, so với tổng số giao dịch có chứa X. 6 Độ tin cậy (confidence) của luật kết hợp X  Y, ký hiệu là conf(X  Y), là tỷ lệ phần trăm giữa số giao dịch chứa X  Y và số giao dịch chứa X trong CSDL giao dịch D.

Xác suất có điều kiện P(Y/X) – xác xuất mà một giao dịch có chứa Y với điều kiện giao dịch đó đã chứa X. Ví dụ với độ tin cậy confidence = 50% nghĩa là trong một giao dịch nếu X đã có mặt thì khả năng có tới 50% là Y sẽ có mặt trong đó. Khi đó độ tin cậy của luật X  Y được biểu diễn bằng: sup( X  Y ) conf ( X  Y )  P(Y / X )  sup( X ) 2. Các tính chất của luật kết hợp Luật kết hợp có một số tính chất sau: - Tính chất 1: Không hợp các luật kết hợp Nếu có hai luật X  Y và Y  Z trong D thì không nhất thiết XY  Z là đúng Xét trường hợp X  Z = và các giao dịch trong D hỗ trợ Z nếu và chỉ nếu chúng hỗ trợ mỗi X hoặc Y, khi đó luật XY  Z có độ hỗ trợ 0%.

Tương tự : X  Y  X  Z thì không nhất thiết X  YZ là đúng. - Tính chất 2: Không tách luật Nếu XY  Z thì X  Z và Y  Z chưa chắc đã xảy ra 7 Ví dụ trường hợp Z có mặt trong một giao dịch chỉ khi cả hai X và Y cũng có mặt, tức là sup(XY) = sup(Z), nếu độ hỗ trợ của X và Y thỏa mãn s(X) > s(XY) và s(Y) > s(XY) thì hai luật riêng biệt sẽ không đủ độ tin cậy. - Tính chất 3: Các luật kết hợp không có tính bắc cầu. Nếu XY và YZ thì không thể suy ra XZ.

- Tính chất 4: Nếu luật X  (L - X) không thoả mãn độ tin cậy cực tiểu thì luật Y  (L - Y) cũng không thoả mãn, với X, Y, L là các tập phần tử và Y  X. Ta có s(Y) ≥ s(X) nên: s (L) s ( L) c(Y(L-Y))=   min_conf s (Y ) s ( X ) Nếu có luật (L-X)  X thỏa mãn độ tin cậy thì ta có luật (L-Y) Y cũng thỏa mãn độ tin cậy, với X, Y, L là các tập phần tử và Y  X. Một số hướng tiếp cận luật kết hợp Luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Dưới đây là một số hướng chính: - Luật kết hợp nhị phân (Binary association rule hay Boolean association rule): là hướng nghiên cứu đầu tiên của luật kết hợp.

Theo luật này, các phần tử chỉ quan tâm là xuất hiện hay không trong cơ sở dữ liệu giao dịch.