So sánh tìm kiếm motif trên chuỗi thời gian của hai giải thuật sequitur và hashing

BỘ CÔNG THƯƠNG

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH

NGUYỄN MINH TÚ

SO SÁNH TÌM KIẾM MOTIF TRÊN CHUỖI

THỜI GIAN CỦA HAI GIẢI THUẬT

SEQUITUR VÀ HASHING

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã chuyên ngành: 60480101

LUẬN VĂN THẠC SĨ

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2021

Công trình được hoàn thành tại Trường Đại học Công nghiệp TP. Hồ Chí Minh.

Người hướng dẫn khoa học: TS. Phạm Văn Chung

Luận văn thạc sĩ được bảo vệ tại Hội đồng chấm bảo vệ Luận văn thạc sĩ Trường Đại

học Công nghiệp thành phố Hồ Chí Minh ngày 25 tháng 12 năm 2021

Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:

1. PGS.TS. Huỳnh Trung Hiếu - Chủ tịch Hội đồng

2. PGS.TS. Nguyễn Hòa - Phản biện 1

3. TS. Phạm Thị Thiết - Phản biện 2

4. TS. Lê Thành Sách - Ủy viên

5. TS. Lê Nhật Duy - Thư ký

(Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ)

CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA

CÔNG NGHỆ THÔNG TIN

BỘ CÔNG THƯƠNG

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP

THÀNH PHỐ HỒ CHÍ MINH

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ

Họ tên học viên: Nguyễn Minh Tú MSHV: 17112901

Ngày, tháng, năm sinh: 30/09/1988 Nơi sinh: Kiên Giang

Chuyên ngành: Khoa học máy tính Mã chuyên ngành: 60480101

I. TÊN ĐỀ TÀI:

So sánh tìm kiếm motif trên chuỗi thời gian của hai giải thuật Sequitur và Hashing.

NHIỆM VỤ VÀ NỘI DUNG:

- Nghiên cứu giải thuật tìm kiếm motif.

- Nghiên cứu giải thuật Sequitur

- Nghiên cứu giải thuật Hashing

- Hiện thực cả hai giải thuật trên dữ liệu thực để đánh giá hiệu quả.

II. NGÀY GIAO NHIỆM VỤ: Theo Quyết định số 1611/QĐ-ĐHCN ngày 06 tháng

09 năm 2019 về việc giao đề tài và cử người hướng dẫn luận văn thạc sĩ

III. NGÀY HOÀN THÀNH NHIỆM VỤ: Ngày 29 tháng 11 năm 2021

IV. NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Phạm Văn Chung

Tp. Hồ Chí Minh, ngày … tháng ... năm ….

NGƯỜI HƯỚNG DẪN

TS. Phạm Văn Chung

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO

TRƯỞNG KHOA CÔNG NGHỆ THÔNG TIN

i

LỜI CẢM ƠN

Lời đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến Tiến sĩ Phạm Văn

Chung. Người Thầy đã tận tình chỉ bảo, hướng dẫn cho tôi trong suốt quá trình thực

hiện luận văn cũng như tạo mọi điều kiện tốt nhất để tôi có thể hoàn thành luận văn

này.

Tôi cũng xin cảm ơn đến tất cả quý thầy cô trong ngành Khoa học máy tính, Khoa

Công nghệ thông tin tại Trường Đại học Công Nghiệp TPHCM đã truyền đạt các

kiến thức cần thiết và quý báu cho tôi trong suốt quá trình học tập tại trường.

Cuối cùng, tôi xin cảm ơn những đóng góp ý kiến cũng như các lời động viên của

thầy cô, gia đình và bạn bè. Nhờ đó mà tôi đã có thêm động lực để tiếp tục nghiên

cứu và hoàn thiện tốt luận văn.

Tôi xin chân thành cảm ơn tất cả.

ii

ABSTRACT

Time series data mining search has attracted many researchers' attention recently. In

particular, the study of finding motifs in time series data is becoming more and

more popular. Due to the fact that the extremely increasing amount of information

in society makes it an advantage to conduct research on time series data. Because of

the great size and the increasing time series data, when studying the algorithms for

searching for motifs, it is desperately necessary to reduce the number of

dimensions. Motif finding is the process of discovering a variety of similar

substrings repeated many times in a time series.The thesis used Sequitur and

Hashing algorithms to search for motifs in time series. Using a real-world dataset,

we test the accuracy and efficiency of the two algorithms.

iii

TÓM TẮT LUẬN VĂN THẠC SĨ

Tìm kiếm khai thác dữ liệu theo chuỗi thời gian đã thu hút nhiều sự chú ý của các

nhà nghiên cứu trong thời gian gần đây. Đặc biệt, việc nghiên cứu tìm kiếm các

motif trong dữ liệu chuỗi thời gian ngày càng trở nên phổ biến. Do lượng thông tin

ngày càng tăng trong xã hội khiến việc nghiên cứu dữ liệu chuỗi thời gian trở thành

một lợi thế. Do kích thước lớn và dữ liệu chuỗi thời gian ngày càng tăng, khi nghiên

cứu các thuật toán tìm kiếm motif, việc giảm số chiều là rất cần thiết. Tìm kiếm

motif là quá trình khám phá nhiều chuỗi con giống nhau được lặp lại nhiều lần trong

một chuỗi thời gian. Luận văn sử dụng các thuật toán Sequitur và Hashing để tìm

kiếm các motif trong chuỗi thời gian. Sử dụng tập dữ liệu trong thế giới thực, chúng

tôi kiểm tra độ chính xác và hiệu quả của hai thuật toán.