Luận văn Thạc sĩ Công nghệ thông tin: Khai thác mẫu tuần tự nén

Luận văn Thạc sĩ Công nghệ thông tin: Khai thác mẫu tuần tự nén được thực hiện với nhiệm vụ nhằm mã hóa dữ liệu tuần tự bằng cách gán các codeword đối với các khoảng cách nhỏ, rồi từ đó tiến hành xử lý trên mẫu với khoảng cách lớn hơn, tính toán độ phức tạp của quá trình khai phá mẫu nén trên cơ sở dữ liệu tuần tự, nghiên cứu thuật toán GoKrimp để khai phá trực tiếp trên mẫu đã được nén dựa trên thuật toán tham lam. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Khai thác mẫu tuần tự nén BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- TRỊNH MINH SỸ KHAI THÁC MẪU TUẦN TỰ NÉN LUẬN VĂN THẠC SĨ Chuyên ngành : Công Nghệ Thông Tin Mã số ngành: 60480201 TP. HỒ CHÍ MINH, tháng 10 năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM ----------oOo---------- TRỊNH MINH SỸ KHAI THÁC MẪU TUẦN TỰ NÉN LUẬN VĂN THẠC SĨ Chuyên ngành : Công Nghệ Thông Tin Mã số ngành: 60480201 CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS.TS. LÊ HOÀI BẮC TP. HỒ CHÍ MINH, tháng 10 năm 2015 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hướng dẫn khoa học : PGS.TS. LÊ HOÀI BẮC Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM ngày 17 tháng 10 năm 2015 Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: TT Họ và tên Chức danh Hội đồng 1 PGS.TS. Nguyễn Xuân Huy Chủ tịch 2 PGS.TS. Quản Thành Thơ Phản biện 1 3 TS. Nguyễn Thị Thúy Loan Phản biện 2 4 TS. Võ Đình Bảy Ủy viên 5 TS. Cao Tùng Anh Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận Văn sau khi Luận Văn đã được sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV TRƯỜNG ĐH CÔNG NGHỆ TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG QLKH – ĐTSĐH Độc lập – Tự do – Hạnh phúc TP. HCM, ngày 03 tháng 04 năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên:TRỊNH MINH SỸ. Giới tính: Nam Ngày, tháng, năm sinh: 07/10/1960 Nơi sinh: Bình Định Chuyên ngành:Công Nghệ Thông Tin MSHV: 1341860052 I- Tên đề tài: KHAI THÁC MẪU TUẦN TỰ NÉN II- Nhiệm vụ và nội dung: Mã hóa dữ liệu tuần tự bằng cách gán các codeword đối với các khoảng cách nhỏ, rồi từ đó tiến hành xử lý trên mẫu với khoảng cách lớn hơn. Tính toán độ phức tạp của quá trình khai phá mẫu nén trên cơ sở dữ liệu tuần tự. Nghiên cứu thuật toán GoKrimp để khai phá trực tiếp trên mẫu đã được nén dựa trên thuật toán tham lam. Tiến hành thực nghiệm trên các bộ dữ liệu khác nhau và đánh giá kết quả, đề xuất cải tiến. III- Ngày giao nhiệm vụ: 03/04/2015 IV - Ngày hoàn thành nhiệm vụ: 07/09/2015 V - Cán bộ hướng dẫn: Phó Giáo Sư. Tiến Sĩ. Lê Hoài Bắc CÁN BỘ HƯỚNG DẪN KHOA QUẢN LÝ CHUYÊN NGÀNH i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này cũng như các trích dẫn hay tài liệu học thuật tham khảo đã được cảm ơn đến tác giả và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn Trịnh minh Sỹ ii của Thầy PGS.TS. Lê Hoài Bắc. ớng dẫn và giúp đỡ tận tình ầy/Cô Khoa Công Nghệ Thông Tin Đại Học Công Nghệ TP. HCM, các bạn học cùng lớp LỜI CÁM ƠN iii TÓM TẮT Khai thác mẫu tuần tự đóng đối với dữ liệu dạng văn bản đã được áp dụng thành công trong nhiều bài toán khác nhau của khai thác dữ liệu. Tuy nhiên, kết quả khai thác vẫn còn một số mặt hạn chế như: - Vấn đề dư thừa của mẫu đã trích ra. - Mẫu trích ra bị trùng lắp. - Một số mẫu tối nghĩa. Để khắc phục những mặt hạn chế trên, ý tưởng dựa trên nguyên lý mô tả chiều dài tối thiểu (MDL minimum description length) được đề xuất nhằm khai thác mẫu tuần tự nén đối với cơ sở dữ liệu tuần tự. Với dữ liệu là itemset, thuật toán Krimp [7] dựa trên mô tả chiều dài tối thiểu đã tỏ ra khá hiệu quả trong việc giải quyết vấn đề dư thừa của mẫu, trích ra những mẫu ít trùng lắp và dễ hiểu hơn. Với dữ liệu tuần tự, đề tài đề xuất hai thuật toán SeqKrimp và GoKrimp. Trong đó, thuật toán chính của đề tài là GoKrimp. • SeqKrimp là thuật toán khai thác mẫu nén gồm hai pha: -Pha thứ nhất: lấy những mẫu tuần tự đóng bởi hàm GetCandidate() đã có. -Pha thứ nhì: từ những mẫu tuần tự đóng đã lấy ở trên chọn lại chỉ còn những mẫu nén dữ liệu tốt nhất. Vậy mẫu nén dữ liệu như thế nào là tốt nhất? Đề tài nghiên cứu hai phần: -Cách thức nén dữ liệu: chọn nén dữ liệu theo phương pháp mã hóa Huffman[3], xây dựng cây nhị phân để mã hóa, cây nhị phân như vậy sẽ thỏa tính chất mã tiền tố nghĩa là không có từ mã nào là phần đầu của từ mã khác. -Hiệu quả nén: là hiệu số giữa số bit trước khi nén và sau khi nén dữ liệu. iv • GoKrimp là thuật toán khai thác trực tiếp mẫu nén, khác với SeqKrimp ở pha thứ nhất, nghĩa là, thuật toán không lấy mẫu tuần tự đóng đã có sẵn mà khai thác t ...