Khai Thác Top-k Chuỗi Tuần Tự Đóng Dựa Trên Mã Hóa Khối Nguyên Tố

• Tác giả: Trần Văn Hà
• Người hướng dẫn: TS. Phạm Thị Thiết
• Trường học: Trường Đại học Công nghiệp Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai thác Top-k chuỗi tuần tự đóng dựa trên mã hóa khối nguyên tố
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: Thành phố Hồ Chí Minh

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN THẠC SĨ
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI THÁC CHUỖI TUẦN TỰ
• 1.1. Giới thiệu tổng quan
• 1.2. Khai thác chuỗi tuần tự
• 1.2.1. Phát biểu bài toán
• 1.2.2. Khái niệm liên quan
• 1.2.3. Các thuật toán liên quan
• 1.2.3.1. Thuật toán GSP [11]
• 1.2.3.2. Thuật toán FreeSpan [12], Prefixspan [8]
• 1.2.3.3. Thuật toán SPADE [17]
• 1.2.3.4. Thuật toán SPAM [14]
• 1.2.3.5. Thuật toán PRISM [2]
• 1.2.4. Thuật toán khai thác top-k chuỗi tuần tự
• 1.2.4.1. Thuật toán TSP [5]
• 1.2.4.2. Thuật toán TKS [3]
• 2. CHƯƠNG 2: KHAI THÁC TOP-K CHUỖI TUẦN TỰ ĐÓNG
• 2.1. Phát biểu bài toán và các khái niệm về khai thác top-k chuỗi tuần tự đóng
• 2.1.1. Phát biểu bài toán
• 2.1.2. Một số khái niệm về khai thác top-k chuỗi tuần tự đóng
• 2.1.3. Thuật toán TKCS
• 3. CHƯƠNG 3: KHAI THÁC TOP-K CHUỖI TUẦN TỰ ĐÓNG DỰA TRÊN MÃ HÓA KHỐI NGUYÊN TỐ
• 3.1. Khối mã hóa nguyên tố
• 3.2. Khối mã hóa theo chuỗi
• 3.3. Khối mã hóa theo vị trí
• 3.4. Nén khối mã hóa nguyên tố
• 3.5. Tính độ hỗ trợ của chuỗi trên khối mã hóa nguyên tố
• 3.6. Phương pháp khai thác top-k chuỗi tuần tự đóng dựa trên mã hóa khối nguyên tố
• 3.6.1. Giới thiệu thuật toán đề xuất
• 3.6.2. Mã giả và mô tả thuật toán đề xuất
• 4. CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Môi trường thực nghiệm
• 4.2. CSDL thực nghiệm
• 4.3. Đối tượng so sánh
• 4.4. Kết quả thực nghiệm
• 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 5.1. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG

I. Tổng Quan Về Khai Thác Top K Chuỗi Tuần Tự Đóng

Khai thác chuỗi tuần tự là một lĩnh vực quan trọng trong khai thác dữ liệu, với nhiều ứng dụng rộng rãi. Vấn đề chọn ngưỡng hỗ trợ tối thiểu (minsup) phù hợp là thách thức lớn. Các thuật toán như TKCS đã được phát triển để giải quyết vấn đề này bằng cách tìm k chuỗi tuần tự đóng phổ biến nhất. Tuy nhiên, TKCS vẫn còn hạn chế về hiệu suất, đặc biệt trên các CSDL lớn. Nghiên cứu này tập trung vào việc cải thiện hiệu suất khai thác top k chuỗi tuần tự bằng cách sử dụng phương pháp mã hóa hiệu quả hơn, giúp giảm chi phí tính toán và bộ nhớ. Mục tiêu là tìm kiếm các chuỗi có độ hỗ trợ cao nhất một cách nhanh chóng và hiệu quả.

1.1. Giới thiệu bài toán khai thác chuỗi tuần tự đóng

Bài toán khai thác chuỗi tuần tự đóng tìm kiếm các chuỗi phổ biến trong cơ sở dữ liệu, đảm bảo không có chuỗi cha nào có cùng độ hỗ trợ. Điều này giúp giảm số lượng chuỗi kết quả, tập trung vào những chuỗi quan trọng nhất. Các thuật toán như GSP, PrefixSpan, và SPADE đã được phát triển cho bài toán này. Tuy nhiên, khi làm việc với dữ liệu lớn, các thuật toán này có thể trở nên chậm chạp và tốn kém. Khai thác dữ liệu chuỗi đóng vai trò quan trọng trong việc khám phá tri thức từ dữ liệu trình tự. Sequential pattern mining ngày càng được ứng dụng rộng rãi.

1.2. Ứng dụng thực tế của khai thác top K chuỗi tuần tự

Các ứng dụng của khai thác top-k sequence mining rất đa dạng, bao gồm phân tích hành vi khách hàng, dự đoán chuỗi sự kiện, và phát hiện gian lận. Ví dụ, trong thương mại điện tử, có thể sử dụng để dự đoán sản phẩm khách hàng sẽ mua tiếp theo dựa trên lịch sử mua hàng của họ. Trong lĩnh vực y tế, có thể giúp xác định các chuỗi triệu chứng liên quan đến một bệnh cụ thể. Ứng dụng khai thác chuỗi tuần tự trong nhiều lĩnh vực thúc đẩy việc nghiên cứu và phát triển các thuật toán hiệu quả hơn.

II. Thách Thức Trong Mã Hóa Khối Nguyên Tố Cho Chuỗi Tuần Tự

Mã hóa khối nguyên tố là một phương pháp hiệu quả để biểu diễn dữ liệu chuỗi, nhưng cũng đặt ra nhiều thách thức. Việc lựa chọn kích thước khối phù hợp là rất quan trọng, vì kích thước quá nhỏ có thể dẫn đến tăng chi phí lưu trữ, trong khi kích thước quá lớn có thể làm giảm hiệu quả của việc nén dữ liệu. Bên cạnh đó, việc tính toán độ đo tương tự chuỗi trên dữ liệu đã mã hóa cũng đòi hỏi các thuật toán đặc biệt. Mục tiêu là tối ưu hóa khai thác chuỗi sao cho cân bằng giữa hiệu suất và độ chính xác.

2.1. Vấn đề về kích thước khối và chi phí tính toán

Kích thước khối ảnh hưởng trực tiếp đến chi phí lưu trữ và tính toán. Khối nhỏ tăng số lượng khối, tốn bộ nhớ. Khối lớn giảm số lượng khối nhưng làm giảm độ chính xác. Phải chọn kích thước tối ưu. Nghiên cứu về element block encoding giúp giải quyết bài toán này.

2.2. Ảnh hưởng của mã hóa khối tới độ chính xác kết quả

Việc mã hóa có thể làm mất thông tin, ảnh hưởng đến độ chính xác của các chuỗi được khai thác. Cần có các phương pháp đảm bảo thông tin quan trọng được giữ lại sau khi mã hóa. Độ đo tương tự chuỗi cần được điều chỉnh phù hợp với dữ liệu đã được mã hóa.

2.3. Tính toán độ hỗ trợ trên dữ liệu đã mã hóa khối

Việc tính toán độ hỗ trợ chuỗi trên dữ liệu đã mã hóa khối đòi hỏi các thuật toán đặc biệt. Các phép toán cần được thực hiện hiệu quả trên các khối mã hóa để đảm bảo hiệu suất. Các phương pháp constraint-based sequence mining có thể được áp dụng để giảm không gian tìm kiếm.

III. Phương Pháp Khai Thác Top K Chuỗi Tuần Tự Bằng TKCSP

Luận văn đề xuất thuật toán TKCSP (Top-K Closed Sequential Patterns) dựa trên mã hóa khối nguyên tố để giải quyết các hạn chế của TKCS. TKCSP loại bỏ các khối chuỗi rỗng trong biểu diễn thông tin của các chuỗi ứng viên, giảm việc tính toán tại mỗi bước xử lý, xác định độ hỗ trợ của các ứng viên nhanh chóng. Thuật toán sử dụng bảng tra giá trị để giảm chi phí tính toán, mã hóa khối giúp giảm dung lượng lưu trữ. Các thử nghiệm cho thấy TKCSP vượt trội hơn TKCS về thời gian và bộ nhớ.

3.1. Mô tả chi tiết thuật toán TKCSP

Thuật toán TKCSP sử dụng mã hóa khối nguyên tố để biểu diễn dữ liệu chuỗi. Quá trình khai thác bao gồm các bước tạo ứng viên, tính toán độ hỗ trợ, và chọn ra top k chuỗi phổ biến nhất. Thuật toán sử dụng các kỹ thuật nén dữ liệu để giảm dung lượng lưu trữ.

3.2. Ưu điểm của việc sử dụng mã hóa khối nguyên tố

Mã hóa khối nguyên tố giúp giảm dung lượng lưu trữ, tăng tốc độ tính toán, và cải thiện hiệu suất khai thác. Phương pháp này đặc biệt hiệu quả trên các CSDL chuỗi lớn, giải quyết bài toán tối ưu hóa khai thác chuỗi. Khai thác top k chuỗi tuần tự hiệu quả hơn nhờ giảm không gian tìm kiếm.

3.3. So sánh TKCSP với các thuật toán khai thác chuỗi khác

TKCSP vượt trội hơn TKCS về thời gian và bộ nhớ. So với các thuật toán khác như TSP, TKCSP cũng cho kết quả tốt hơn nhờ vào kỹ thuật mã hóa khối. Thuật toán khai thác chuỗi tuần tự TKCSP được đánh giá cao về hiệu suất.

IV. Kết Quả Thực Nghiệm Và Đánh Giá Thuật Toán TKCSP

Thuật toán TKCSP đã được triển khai và đánh giá trên nhiều bộ dữ liệu khác nhau. Kết quả cho thấy TKCSP có hiệu suất tốt hơn so với TKCS về chi phí thời gian và bộ nhớ. Đặc biệt, TKCSP hoạt động hiệu quả trên các CSDL chuỗi lớn với số lượng itemsets lớn. Các kết quả thực nghiệm chứng minh tính hiệu quả của phương pháp mã hóa khối nguyên tố trong việc khai thác top k chuỗi tuần tự.

4.1. Thiết lập môi trường thực nghiệm và bộ dữ liệu

Môi trường thực nghiệm bao gồm máy tính với cấu hình phần cứng và phần mềm nhất định. Các bộ dữ liệu được sử dụng bao gồm Sign, Snake*, Chess, và Leviathan. Các bộ dữ liệu này có đặc điểm khác nhau về kích thước và số lượng itemsets, giúp đánh giá hiệu suất của thuật toán trong các tình huống khác nhau. CSDL thực nghiệm được lựa chọn kỹ lưỡng để đảm bảo tính khách quan.

4.2. So sánh hiệu suất giữa TKCSP và TKCS

Kết quả thực nghiệm cho thấy TKCSP có thời gian thực thi ngắn hơn và sử dụng ít bộ nhớ hơn so với TKCS. Đặc biệt, sự khác biệt về hiệu suất trở nên rõ rệt hơn khi kích thước CSDL tăng lên. Thuật toán TKCS bị vượt trội bởi TKCSP.

4.3. Phân tích ảnh hưởng của tham số k đến hiệu suất

Giá trị k ảnh hưởng đến thời gian thực thi và bộ nhớ sử dụng của thuật toán. Khi k tăng lên, thời gian thực thi cũng tăng lên, nhưng không đáng kể. TKCSP vẫn duy trì hiệu suất tốt ngay cả khi k lớn. K chuỗi tuần tự phổ biến nhất được tìm thấy hiệu quả.

V. Ứng Dụng Khai Thác Top K Chuỗi Trong Thực Tế

Khai thác top k chuỗi tuần tự đóng dựa trên mã hóa khối nguyên tố có nhiều ứng dụng thực tế. Trong lĩnh vực thương mại điện tử, có thể sử dụng để dự đoán hành vi mua hàng của khách hàng, cá nhân hóa trải nghiệm người dùng, và tối ưu hóa chiến dịch marketing. Trong lĩnh vực y tế, có thể giúp xác định các chuỗi triệu chứng liên quan đến bệnh tật, dự đoán nguy cơ mắc bệnh, và cải thiện quá trình chẩn đoán. Trong lĩnh vực tài chính, có thể sử dụng để phát hiện gian lận, dự đoán xu hướng thị trường, và quản lý rủi ro.

5.1. Ứng dụng trong thương mại điện tử

Phân tích hành vi mua hàng của khách hàng, dự đoán sản phẩm khách hàng sẽ mua tiếp theo, cá nhân hóa trải nghiệm người dùng, và tối ưu hóa chiến dịch marketing. Khai thác dữ liệu chuỗi giúp tăng doanh thu và cải thiện sự hài lòng của khách hàng.

5.2. Ứng dụng trong lĩnh vực y tế

Xác định các chuỗi triệu chứng liên quan đến bệnh tật, dự đoán nguy cơ mắc bệnh, và cải thiện quá trình chẩn đoán. Thuật toán khai thác chuỗi tuần tự giúp bác sĩ đưa ra quyết định điều trị chính xác hơn.

5.3. Ứng dụng trong lĩnh vực tài chính

Phát hiện gian lận, dự đoán xu hướng thị trường, và quản lý rủi ro. Constraint-based sequence mining giúp các nhà quản lý tài chính đưa ra quyết định đầu tư thông minh hơn.

VI. Kết Luận Và Hướng Phát Triển Cho Thuật Toán TKCSP

Luận văn đã trình bày một phương pháp hiệu quả để khai thác top k chuỗi tuần tự đóng dựa trên mã hóa khối nguyên tố. Thuật toán TKCSP đã được chứng minh là vượt trội hơn TKCS về hiệu suất thời gian và bộ nhớ. Hướng phát triển tiếp theo bao gồm việc nghiên cứu các phương pháp mã hóa khối hiệu quả hơn, tối ưu hóa các thuật toán tính toán độ hỗ trợ, và áp dụng TKCSP vào các ứng dụng thực tế khác nhau. Nghiên cứu này đóng góp vào lĩnh vực khai thác dữ liệu chuỗi và mở ra nhiều hướng nghiên cứu mới.

6.1. Tóm tắt những đóng góp chính của luận văn

Đề xuất thuật toán TKCSP dựa trên mã hóa khối nguyên tố, chứng minh tính hiệu quả của TKCSP so với TKCS, và thực hiện đánh giá thực nghiệm trên nhiều bộ dữ liệu khác nhau.

6.2. Các hướng nghiên cứu tiếp theo cho TKCSP

Nghiên cứu các phương pháp mã hóa khối hiệu quả hơn, tối ưu hóa các thuật toán tính toán độ hỗ trợ, và áp dụng TKCSP vào các ứng dụng thực tế khác nhau. Nghiên cứu về frequent sequence mining và pattern mining có thể được áp dụng.

6.3. Tiềm năng ứng dụng của TKCSP trong tương lai

TKCSP có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau, bao gồm thương mại điện tử, y tế, tài chính, và an ninh mạng. Ứng dụng khai thác chuỗi tuần tự sẽ ngày càng trở nên quan trọng trong tương lai.