Khai Thác Tập Mục Hữu Ích Cao Song Song: Luận Án Tiến Sĩ Tối Ưu

LỜI CAM ĐOAN

TÓM TẮT LUẬN ÁN TIẾN SĨ

ABSTRACT

LỜI CẢM ƠN

1. CHƯƠNG 1: TỔNG QUAN VỀ LĨNH VỰC NGHIÊN CỨU

1.1. Các nghiên cứu liên quan

1.2. Bài toán khai thác tập mục hữu ích cao

1.3. Bài toán khai thác tập mục hữu ích cao với biểu diễn đóng

1.4. Bài toán khai thác tập mục hữu ích cao trên CSDL phân cấp

1.5. Bài toán khai thác song song các tập mục hữu ích cao

1.6. Các bài toán khai thác tập mục hữu ích cao khác

2. CHƯƠNG 2: KHAI THÁC HIỆU QUẢ TẬP MỤC HỮU ÍCH CAO ĐÓNG TỪ CƠ SỞ DỮ LIỆU CÓ ĐỘ HỮU ÍCH BIẾN ĐỘNG

2.1. Giới thiệu bài toán

2.2. Một số định nghĩa cơ sở

2.3. Cải thiện hiệu năng quét CSDL

2.4. Giải thuật iEFIM-Closed

2.5. Đánh giá mức độ hiệu quả của P-set

2.6. Đánh giá độ phức tạp của giải thuật iEFIM-Closed

2.6.1. Môi trường thực nghiệm

2.6.2. Cơ sở dữ liệu thực nghiệm

2.6.3. Phương pháp đánh giá

2.6.4. Thời gian thực hiện

2.6.5. Mức độ sử dụng bộ nhớ

2.6.6. Chi phí quét CSDL

2.6.7. Khả năng thích nghi với việc mở rộng CSDL

2.6.8. Kết chương

3. CHƯƠNG 3: MÔ HÌNH SONG SONG HÓA KHAI THÁC TẬP MỤC HỮU ÍCH CAO ĐA MỨC

3.1. Giải thuật MCML-Miner

3.2. Một số định nghĩa

3.3. Mô hình song song hoá quá trình khai thác tập mục hữu ích cao đa mức trên CSDL phân cấp

3.4. Khai thác song song các tập mục hữu ích cao đa mức từ CSDL phân cấp

3.5. Khai thác tập mục hữu ích cao đa mức - đóng từ CSDL phân cấp

3.5.1. Kiểm tra nhanh tính đóng của một tập mục

3.5.2. Giải thuật MLC-Miner

3.5.3. Độ phức tạp của giải thuật MLC-Miner

3.6. Khai thác song song các tập mục hữu ích cao đa mức - đóng

3.6.1. Giải thuật PMLC-Miner

3.6.2. Độ phức tạp của giải thuật PMLC-Miner

3.7. Kết chương

4. CHƯƠNG 4: CẢI THIỆN HIỆU QUẢ MÔ HÌNH KHAI THÁC SONG SONG CÁC TẬP MỤC HỮU ÍCH CAO ĐA MỨC

4.1. Giải thuật MCML+

4.2. Giải thuật MCML++

4.3. Môi trường và CSDL thực nghiệm

4.4. Đánh giá về thời gian thực hiện

4.5. Đánh giá về mức độ sử dụng bộ nhớ

4.6. Đánh giá về khả năng thích nghi với việc mở rộng CSDL

4.7. So sánh giữa các chiến lược điều phối

4.8. Kết chương

5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

5.1. So sánh với các nghiên cứu trước đây

5.2. Phân tích hiệu quả của các giải thuật đề xuất

5.3. Hạn chế của nghiên cứu

5.4. Vấn đề phát sinh và cách giải quyết

5.5. Ý nghĩa của nghiên cứu

5.6. Hướng phát triển trong tương lai

5.6.1. Nghiên cứu và phát triển chiến lược cân bằng tải

5.6.2. Mở rộng mô hình xử lý song song trên môi trường phân tán

5.6.3. Tích hợp các phương pháp học sâu vào khai thác dữ liệu

5.6.4. Ứng dụng trong các lĩnh vực thực tiễn

5.6.5. Tăng cường tính khả mở của giải thuật

5.6.6. Phân tích và cải thiện các tiêu chí đánh giá

DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA HỌC VIÊN

1. Các công trình là tác giả chính

2. Các công trình đồng tác giả

TÀI LIỆU THAM KHẢO

I. Tổng Quan Về Khai Thác Tập Mục Hữu Ích Cao HUIM

Bài toán khai thác tập phổ biến (FIM) được Agrawal và cộng sự đề xuất năm 1993, mở ra hướng phân tích hành vi khách hàng trong bán lẻ và thương mại điện tử. FIM phân tích các giao dịch để tìm ra những mặt hàng hoặc kết hợp mặt hàng thường được mua cùng nhau, gọi là "phổ biến" nếu tần suất vượt ngưỡng tối thiểu. Ngưỡng này, ký hiệu 𝑚𝑖𝑛𝑠𝑢𝑝, quyết định độ phổ biến. Để tổng quát, mặt hàng gọi là hạng mục và kết hợp mặt hàng là tập mục. Kết quả FIM tạo ra các luật kết hợp, giúp nhà quản lý hiểu quy luật kinh doanh hiệu quả hơn. Từ khi ra đời, FIM thu hút sự quan tâm lớn. Đầu vào là CSDL giao dịch và ngưỡng 𝑚𝑖𝑛𝑠𝑢𝑝, đầu ra là tập mục phổ biến. Nhiều nghiên cứu đã cải tiến FIM. Nhược điểm lớn nhất của FIM là chỉ xét tần suất, coi mọi hạng mục quan trọng như nhau, bỏ qua nhiều thông tin hữu ích khác trong CSDL giao dịch.

1.1. Ý nghĩa của Khai Thác Tập Mục Frequent Itemset Mining

Khai thác tập mục (FIM) là nền tảng cho nhiều ứng dụng phân tích dữ liệu. Nó giúp xác định các mối quan hệ ẩn giữa các mục trong một tập dữ liệu lớn. Điều này có giá trị trong việc đưa ra quyết định kinh doanh, cải thiện trải nghiệm người dùng, và phát hiện gian lận. Tuy nhiên, FIM truyền thống bỏ qua các yếu tố quan trọng như giá trị lợi nhuận của từng sản phẩm, khiến cho kết quả đôi khi không phản ánh đúng thực tế.

1.2. Hạn chế của FIM và Sự ra đời của HUIM High Utility Itemset Mining

FIM chỉ tập trung vào tần suất xuất hiện của các hạng mục, bỏ qua lợi nhuận hoặc giá trị mà mỗi hạng mục mang lại. Điều này dẫn đến việc các hạng mục có lợi nhuận thấp nhưng tần suất cao lại được ưu tiên hơn các hạng mục có lợi nhuận cao nhưng tần suất thấp. Để khắc phục hạn chế này, HUIM ra đời. HUIM xem xét cả số lượng và giá trị của từng hạng mục, từ đó xác định các tập mục mang lại lợi nhuận cao nhất cho doanh nghiệp. Theo tài liệu gốc, FIM chỉ quan tâm đến tần suất xuất hiện của các hạng mục và tập mục trong CSDL.

II. Thách Thức trong Khai Thác Tập Mục Hữu Ích Cao Song Song

Mặc dù HUIM (High Utility Itemset Mining) khắc phục được hạn chế của FIM bằng cách xem xét giá trị và số lượng của các hạng mục, việc triển khai HUIM song song vẫn còn nhiều thách thức. Các thuật toán HUIM thường có độ phức tạp tính toán cao, đặc biệt khi xử lý các CSDL lớn. Việc song song hóa các thuật toán này đòi hỏi phải phân chia công việc một cách hiệu quả để giảm thiểu thời gian thực hiện và tránh lãng phí tài nguyên. Hơn nữa, việc đồng bộ hóa giữa các tiến trình song song có thể gây ra overhead, làm giảm hiệu năng tổng thể. Do đó, cần có các phương pháp và kỹ thuật tối ưu hóa để khai thác hiệu quả sức mạnh của các hệ thống tính toán song song.

2.1. Độ phức tạp tính toán của HUIM High Utility Itemset Mining

HUIM có độ phức tạp tính toán cao hơn FIM do phải tính toán độ hữu ích của từng tập mục. Điều này đòi hỏi phải quét CSDL nhiều lần và thực hiện các phép tính phức tạp. Độ phức tạp này càng tăng lên khi kích thước CSDL và số lượng hạng mục tăng lên. Do đó, cần có các thuật toán và kỹ thuật tối ưu hóa để giảm thiểu độ phức tạp tính toán của HUIM.

2.2. Vấn đề đồng bộ hóa trong khai thác song song Parallel processing

Khi triển khai HUIM song song, cần phải đồng bộ hóa giữa các tiến trình để đảm bảo tính nhất quán của dữ liệu và tránh các lỗi xung đột. Việc đồng bộ hóa có thể gây ra overhead, làm giảm hiệu năng tổng thể. Cần có các kỹ thuật đồng bộ hóa hiệu quả để giảm thiểu overhead và tối ưu hóa hiệu năng khai thác song song.

2.3. Cân bằng tải trong môi trường tính toán song song optimization

Trong môi trường tính toán song song, việc cân bằng tải là rất quan trọng để đảm bảo tất cả các tiến trình đều được sử dụng hiệu quả. Nếu một tiến trình phải xử lý nhiều công việc hơn các tiến trình khác, nó sẽ trở thành nút thắt cổ chai, làm giảm hiệu năng tổng thể. Cần có các chiến lược cân bằng tải để phân chia công việc một cách đồng đều giữa các tiến trình.

III. iEFIM Closed Khai Thác Tập Mục Hữu Ích Cao Đóng Hiệu Quả

Luận án đề xuất mô hình cho phép khai thác hiệu quả các tập mục hữu ích cao đóng từ CSDL có chứa các hạng mục với độ hữu ích động trong quá trình khai thác nhằm phản ánh sát hơn nữa các CSDL trong thực tế. Đóng góp này áp dụng mô hình độ hữu ích động kết hợp với phương pháp để giảm chi phí quét CSDL nhằm cải thiện hiệu năng của quá trình khai thác tập mục hữu ích cao đóng. Chương 2 trình bày nghiên cứu và mô hình đề xuất thông qua giải thuật iEFIM-Closed.

3.1. Mô hình độ hữu ích động dynamic utility values trong iEFIM Closed

Mô hình độ hữu ích động cho phép độ hữu ích của các hạng mục thay đổi trong quá trình khai thác. Điều này phản ánh thực tế là giá trị của các sản phẩm có thể thay đổi theo thời gian do các yếu tố như cung cầu, cạnh tranh, và xu hướng thị trường. iEFIM-Closed sử dụng mô hình này để xác định các tập mục thực sự có giá trị cao.

3.2. Giảm chi phí quét CSDL với iEFIM Closed data mining

iEFIM-Closed sử dụng các kỹ thuật để giảm thiểu số lần quét CSDL, từ đó giảm chi phí tính toán và cải thiện hiệu năng. Một trong những kỹ thuật này là sử dụng cấu trúc dữ liệu P-set để lưu trữ thông tin về các tập mục tiềm năng và chỉ quét CSDL khi cần thiết.

3.3. Giải thuật iEFIM Closed Chi tiết và Phân tích frequent itemset mining algorithms

Giải thuật iEFIM-Closed là một thuật toán hiệu quả để khai thác các tập mục hữu ích cao đóng từ các CSDL có độ hữu ích động. Thuật toán này sử dụng các kỹ thuật tối ưu hóa để giảm thiểu chi phí tính toán và đảm bảo rằng chỉ các tập mục thực sự có giá trị cao mới được khai thác.

IV. MCML Miner Xử Lý Song Song Khai Thác Tập Mục Đa Mức

Luận án mở rộng bài toán để áp dụng với dạng CSDL có sự phân cấp các hạng mục dựa trên các nghiên cứu từ Đóng góp thứ nhất, và đề xuất mô hình xử lý song song đa nhân để giải quyết bài toán này thông qua việc tận dụng năng lực xử lý của các CPU đa nhân để giảm chi phí về mặt thời gian. Nội dung của đóng góp được trình bày tại Chương 3. Thực nghiệm cho thấy mô hình đề xuất có sự cải thiện rõ rệt về thời gian khai thác.

4.1. Mô hình CSDL phân cấp hierarchical databases và ứng dụng

CSDL phân cấp là một loại CSDL trong đó các hạng mục được tổ chức theo một cấu trúc cây. Điều này cho phép khai thác các tập mục ở nhiều mức độ chi tiết khác nhau. Ví dụ, trong một CSDL bán lẻ, các sản phẩm có thể được phân loại theo danh mục, loại sản phẩm, và nhãn hiệu. Mô hình CSDL phân cấp cho phép khai thác các tập mục ở các mức độ khác nhau, ví dụ như 'khách hàng thường mua sản phẩm từ danh mục A và loại sản phẩm B'.

4.2. Tối ưu hiệu năng nhờ xử lý song song đa nhân parallel processing

MCML-Miner tận dụng sức mạnh của các CPU đa nhân để xử lý song song các tác vụ khai thác tập mục. Điều này giúp giảm đáng kể thời gian thực hiện, đặc biệt khi xử lý các CSDL lớn. Giải thuật này chia nhỏ bài toán thành các tác vụ nhỏ hơn và phân phối chúng cho các nhân xử lý khác nhau.

4.3. Giải thuật MCML Miner Multi Core Multi Level HUI Miner Phân tích chuyên sâu

Giải thuật MCML-Miner là một giải thuật hiệu quả để khai thác các tập mục hữu ích cao đa mức từ các CSDL phân cấp. Thuật toán này sử dụng các kỹ thuật tối ưu hóa để giảm thiểu chi phí tính toán và tận dụng sức mạnh của các CPU đa nhân. MCML-Miner bao gồm các giai đoạn như tiền xử lý, khai thác tập mục tiềm năng, và đánh giá độ hữu ích.

V. MCML MCML Cải Tiến Mô Hình Khai Thác Song Song Đa Mức

Dựa trên các kết quả nghiên cứu từ Đóng góp thứ 2 và Đóng góp thứ nhất, luận án triển khai việc áp dụng mô hình xử lý song song trên nhiều giai đoạn khác nhau của quá trình khai thác, triển khai sâu hơn nữa mô hình song song trong quá trình khai thác. Ngoài ra, một chiến lược điều phối cũng được đề xuất để giảm thời gian chờ giữa các tác vụ song song. Toàn bộ đóng góp thứ ba nhắm đến việc tận dụng triệt để hơn nữa sức mạnh xử lý của các CPU đa nhân với chi phí phù hợp vào bài toán khai thác tập mục hữu ích cao từ định dạng CSDL phân cấp, có độ hữu ích động. Thực nghiệm cho thấy với mô hình được đề xuất trong Đóng góp thứ ba, hiệu năng khai thác của bài toán được nâng lên đáng kể so với tiếp cận không song song, đặc biệt trên các CSDL có kích thước lớn.

5.1. MCML Tối ưu hóa khai thác song song đa mức optimization

MCML+ là một phiên bản cải tiến của MCML-Miner, tập trung vào việc tối ưu hóa quá trình khai thác song song đa mức. Giải thuật này sử dụng các kỹ thuật để giảm thiểu thời gian chờ giữa các tác vụ song song và cải thiện hiệu quả sử dụng tài nguyên CPU.

5.2. MCML Chiến lược điều phối tác vụ thông minh parallel processing

MCML++ tiếp tục cải tiến MCML+ bằng cách áp dụng các chiến lược điều phối tác vụ thông minh. Các chiến lược này giúp phân bổ công việc một cách hiệu quả giữa các nhân xử lý và giảm thiểu thời gian thực hiện tổng thể.

5.3. So sánh hiệu năng giữa MCML MCML và MCML

Luận án cung cấp các kết quả thực nghiệm so sánh hiệu năng của MCML, MCML+, và MCML++ trên các CSDL khác nhau. Kết quả cho thấy MCML+ và MCML++ có hiệu năng tốt hơn MCML, đặc biệt trên các CSDL lớn và phức tạp.

VI. Kết Luận và Hướng Phát Triển Cho Khai Thác Tập Mục Hữu Ích

Luận án đã đề xuất các mô hình và giải thuật hiệu quả để khai thác tập mục hữu ích cao trên môi trường tính toán song song. Các giải thuật iEFIM-Closed, MCML-Miner, MCML+, và MCML++ đã chứng minh được khả năng cải thiện hiệu năng khai thác, đặc biệt trên các CSDL lớn và phức tạp. Nghiên cứu này có ý nghĩa thực tiễn trong nhiều lĩnh vực như phân tích giỏ hàng, phân tích web, và phân tích dữ liệu y tế. Hướng phát triển trong tương lai bao gồm nghiên cứu các chiến lược cân bằng tải, mở rộng mô hình xử lý song song trên môi trường phân tán, và tích hợp các phương pháp học sâu vào khai thác dữ liệu.

6.1. Ứng dụng thực tiễn của HUIM trong các lĩnh vực khác nhau applications of frequent itemset mining

HUIM có thể được ứng dụng trong nhiều lĩnh vực khác nhau như phân tích giỏ hàng trong bán lẻ, phân tích hành vi người dùng trên web, và phân tích dữ liệu y tế để phát hiện các mối quan hệ giữa các bệnh và các yếu tố rủi ro.

6.2. Nghiên cứu và phát triển chiến lược cân bằng tải optimization

Cân bằng tải là một vấn đề quan trọng trong xử lý song song. Các chiến lược cân bằng tải giúp phân phối công việc một cách đồng đều giữa các nhân xử lý và giảm thiểu thời gian thực hiện tổng thể.

6.3. Tích hợp học sâu vào khai thác tập mục hữu ích data mining

Học sâu là một lĩnh vực phát triển nhanh chóng và có nhiều tiềm năng ứng dụng trong khai thác dữ liệu. Việc tích hợp các phương pháp học sâu vào khai thác tập mục hữu ích có thể giúp cải thiện độ chính xác và hiệu quả của quá trình khai thác.

Khai thác tập mục hữu ích cao trên môi trường tính toán song song