Luận văn ThS: Khai thác mẫu tuần tự nén

140 lượt xem
Share

Luận văn Khai thác mẫu tuần tự nén nghiên cứu mô hình mã hóa dữ liệu tuần tự, mã Huffman, mã Elias; nghiên cứu thuật toán SeqKrimp; nghiên cứu thuật toán GoKrimp để khai phá trực tiếp trên mẫu nén; tiến hành thực nghiệm trên các 8 bộ dữ liệu khác nhau và đánh giá kết quả.

Mục lục nội dung

Luận văn ThS: Khai thác mẫu tuần tự nén

1. Mở đầu

1.1 Đặt vấn đề

Vấn đề khai thác mẫu tuần tự phổ biến từ cơ sở dữ liệu tuần tự đã được ứng dụng thành công trong lĩnh vực khai thác dữ liệu. Trong những năm gần đây nhiều công trình khai thác mẫu tuần tự đóng đã đóng góp nhiều ứng dụng cụ thể cho lĩnh vực khai thác dữ liệu. Tuy vậy khi quan sát  20 mẫu tuần tự phổ biến đóng được trích ra từ tập dữ liệu Journal of Machine Learning Research (JMLR), bộ dữ liệu này chứa cơ sở dữ liệu của 787 cụm từ, mỗi cụm từ tương ứng với tóm tắt của một bài báo trong JMLR có nhận xét rằng:

  • Mẫu trùng lắp mặc dù có độ hỗ trợ cao ví như mẫu algorithm algorithm
  • Mẫu tối nghĩa ví như hai mẫu learn algorithm và algorithm learn nếu mẫu này có nghĩa thì mẫu kia tối nghĩa
  • Mẫu dư thừa, rườm rà ví như mẫu algorithm algorithm algorithm

1.2 Mục tiêu nghiên cứu

Mục tiêu đề tài là đi tiếp theo của ý tưởng MDL (mô tả chiều dài tối thiểu) để đưa ra đặc tả ngữ cảnh của dữ liệu tuần tự. Và đặc biệt trọng tâm là việc lấy ý tưởng MDL để khám phá mẫu tuần tự nén đáng quan tâm, có nghĩa và khả dụng.

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

Phương pháp luận: Nghiên cứu về lý thuyết các thuật toán có liên quan đến đề tài cùng với các khái niệm đi kèm, trong mỗi thuật toán giải thích ý nghĩa, cho ví dụ minh họa từng bước giải quyết của thuật toán.

Phương pháp nghiên cứu: Đọc hiểu về lý thuyết cách mã hóa dữ liệu, tìm chọn mô hình mã hóa tối ưu dữ liệu, từ đó sẽ cho hiệu quả nén tốt để kết quả đưa ra những mẫu dễ hiểu hơn, giảm dư thừa và khả dụng.

2. Nội dung

2.1 Cơ sở lí thuyết

Mã Huffman

  • Mã tiền tố
  • Cây nhị phân biểu diễn từ mã

Khai thác mẫu tuần tự nén

  • Khai thác mẫu tuần tự đóng
  • Nguyên lý nén dữ liệu

Phương pháp mã hóa dữ liệu

  • Mã hóa và giải mã số tự nhiên
  • Phương pháp nén và hiệu quả nén

Mã hóa và giải mã một dãy các từ

Bài toán tìm mẫu nén

  • Định nghĩa (Bài toán nén dãy)
  • Kết luận

2.2 Thuật toán khai thác mẫu nén

Thuật toán SeqKrimp

  • Thuật toán lấy mẫu tuần tự đóng GetCandidate
  • Thuật toán so khớp với chi phí tối thiểu MinGapMatch
  • Thuật toán tính hiệu quả nén Compress
  • Thuật toán khai thác mẫu nén SeqKrimp

Thuật toán GoKrimp

  • Kiểm tra sự kiện có liên quan 
  • Thuật toán nới rộng mẫu GetNextPattern
  • Thuật toán khai thác trực tiếp mẫu nén GoKrimp

2.3 Thực nghiệm và kết luận

Bộ dữ liệu thử nghiệm

  • Bộ dữ liệu JMLR
  • Bộ dữ liệu Parallel

Thời gian thực thi

Độ chính xác phân lớp

Tính nén

Hiẹu lực của sự kiện liên quan

3. Kết luận

Các mô hình khai thác chuỗi tuần tự nén thường được thực hiện trên các cơ sở dữ liệu khác nhau trên thế. Tuy nhiên, hầu hết các cơ sở dữ liệu thế giới thực cập nhật với tiến bộ của thời gian. Qua nghiên cứu một số thuật toán khai thác mẫu tuần tự nén SeqKrimp và GoKrimp ta nhận thấy, thuật toán GoKrimp đã đạt được nhiều cải tiến về mặt thời gian thực hiện các mẫu nén và các mẫu nén được trích ra tỏ ra hữu dụng hơn, giảm thiểu khả năng trùng lắp của các mẫu kết quả. Tác giả luận văn cũng đã hiểu và xây dựng được các ví dụ cụ thể cho từng thuật toán nhằm giúp người đọc dễ tiếp cận các thuật toán hơn.

4. Tài liệu tham khảo

D. Chakrabarti, S. Papadimitriou, D. Modha, and C. Faloutsos, “Fully automatic cross-associations”, KDD, 2004, 79–88. Statistical Analysis and Data Mining DOI:10.1002/sam 52 Statistical Analysis and Data Mining, Vol. 7 (2014)

D. Fradkin and F. Moerchen, Margin-Closed “Frequent Sequential Pattern Mining”, Workshop on Mining Useful Patterns, KDD, 2010.

D. Huffman, “A method for the construction of minimumredundancy codes”, Proc IRE 40(9) (1952), 1098–1102.

H. T. Lam, F. Moerchen, D. Fradkin, and T. Calders , “Mining Compressing Sequential Patterns”, Statistical Analysis and Data Mining: The ASA Data Science Journal, Volume 7, Issue 1, pages 34–52, February 2014.....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn trên ---

140 lượt xem
Share
Ngày:03/09/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM