Khai thác Motif trên dữ liệu chuỗi thời gian dựa vào kỹ thuật băm :Luận văn thạc sĩ - Chuyên ngành: Khoa học máy tính

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

Họ tên học viên: Nguyễn￾Đương￾Thời ........................... MSHV: 15001261................

Ngày,￾tháng,￾năm￾sinh: 02/02/1992................................ Nơi￾sinh: Tây Ninh ..............

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

I. TÊN￾ĐỀ TÀI:

Nhận dạng motif trên dữ liệu chuỗi thời gian dựa vào kỹ thuật￾băm

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

- Tìm hiểu giải thuật MK

- Trình bày giải thuật khai thác motif trên dữ liệu chuỗi thời gian dựa vào kỹ thuật

băm.

- Hiện thực, thử nghiệm và￾đánh￾giá￾trên giải thuật MK và giải thuật đã￾trình￾bày

II. NGÀY GIAO NHIỆM VỤ: 01/12/2017 ................................................................

III. NGÀY HOÀN THÀNH NHIỆM VỤ: 30/06/2017..............................................

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

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

NGƯỜI￾HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN￾ĐÀO￾TẠO

TRƯỞNG KHOA/VIỆN….………

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

i

LỜI CẢM￾ƠN

Lời￾ đầu tiên, em xin gửi lời cảm￾ ơn￾chân￾thành￾và sâu sắc￾ đến TS. Phạm￾Văn￾Chung,

giáo viên￾đã￾tận￾tình￾hướng dẫn em trong suốt quá trình tìm hiểu và nghiên cứu￾cũng￾như￾

tạo mọi￾điều kiện thuận lợi nhất￾để em có thể hoàn thành luận￾văn￾tốt nghiệp này.

Em cũng￾xin￾cảm￾ơn￾những ý kiến￾đóng￾góp￾cũng￾như￾lời￾động viên của các bạn trong

tập thể lớp CHKHMT5A. Qua￾ đó￾ em đã￾ có￾thêm￾ động lực￾ để nghiên cứu￾ và￾ đạt￾ được

nhiều tiến bộ trong kiến thức￾cũng￾như￾kỹ năng￾làm￾việc.

Cuối cùng, em xin gửi lời cảm￾ ơn￾ đến các thầy, cô trong bộ môn Khoa học máy tính,

Khoa Công nghệ thông tin, Trường￾Đại học Công nghiệp￾TPHCM￾đã￾tạo mọi￾điều kiện

tốt nhất￾để em hoàn thành luận￾văn￾này.

Dù￾đã￾cố gắng hết sức cùng với sự tận tâm của thầy￾hướng dẫn￾song￾cũng￾khó￾tránh khỏi

những thiếu sót. Rất mong nhận￾được sự góp ý của thầy, cô và các bạn.

TPHCM, ngày 07 tháng 07 năm￾2017

Học viên

Nguyễn￾Đương￾Thời

ii

LỜI￾CAM￾ĐOAN

Em cam￾đoan￾rằng, ngoại trừ các kết quả tham khảo từ các￾công￾trình￾khác￾như￾đã￾trình￾

bày trong luận￾văn,￾các￾công￾trình￾được trình bày trong luận￾văn￾do￾chính￾em thực hiện

và￾chưa￾có￾phần nội dung nào của luận￾văn￾này￾được nộp￾để lấy bằng cấp ở trường này

hoặc￾trường khác.

Học viên

Nguyễn￾Đương￾Thời

iii

ABSTRACT

Research on the extracting of the pattern without the previously unknown, and regular

patterns of occurrences are called the motif in the time series data. The following patterns

are useful for the other time series data discovery, this pattern have been attracted

universal interest of the research. So searching motif of the time series data is a one of the

general technique of data mining

Motif in time series data is the similar subsequences which appear repeatedly many times

in the data set. Usually, the size of the time series data is very large and growing more

and more. This is the challenge that makes it difficult for the motif discovery algorithm.

In this these, we propose a new algorithm, Hashing algorithm which can find motif on the

very large time series data. From the initial raw data, after executing normalization step,

we will perform dimentionality reduction and discretization. Using the sliding window of

size w (w defined by the user), it slides through all the symbols in the string. The

subsequence generated by the sliding window is called the word, each word is considered

as a feature. A hash table is used to contain these features, tow match features will be

stored together in the same bucket. Finding bucket with the largest size, the

corresponding key of this bucket will be the motif candidate. We can find motif instances

from the motif candidate and basing on the dissimilarity maximum thresholdMax

(thresholdMax defined by user based on Euclid distance function).

Hashing algorithm solves the motif discovery problem in linear time with the size of the

data set, using memory space is an almost constant.

iv

TÓM TẮT LUẬN￾VĂN

Việc nghiên cứu trên sự rút trích hữu hiệu các mẫu không￾ được biết￾ trước, các mẫu

thường xuyên xuất hiện￾được gọi là các motif trong dữ liệu chuỗi thời gian, đã￾thu hút

được nhiều sự quan tâm của các nhà nghiên cứu. Các mẫu này rất hữu ích cho các công

việc khai thác dữ liệu chuỗi thời￾gian￾khác￾nhau.￾Do￾đó việc tìm kiếm motif của dữ liệu

chuỗi thời gian là một trong những kỹ thuật phổ biến trong việc khai thác dữ liệu chuỗi

thời gian.

Motif trong dữ liệu chuỗi thời gian là những chuỗi￾con￾(Subsequense)￾tương￾tự xuất hiện

lặp￾đi￾lặp lại nhiều lần trong tập dữ liệu thời gian.￾Kích￾thước của dữ liệu chuỗi thời gian

thường rất lớn￾và￾ngày￾càng￾gia￾tăng￾là￾vấn￾đề gây￾khó￾khăn￾cho￾các￾giải thuật khai thác

motif.

Trong luận￾văn￾này￾sử dụng kỹ thuật￾băm￾được gọi là giải thuật Hashing phát hiện motif

trên tập dữ liệu chuỗi thời￾gian￾có￾kích￾thước lớn. Từ dữ liệu￾thô￾(raw￾data)￾ban￾đầu sau

khi thực hiện￾ bước chuẩn hóa (nomalization) sẽ tiếp tục thực hiện thu giảm số chiều

(dimensionality reduction) và rời rạc hóa (discretization) về dạng chuỗi ký tự. Sử dụng

cửa sổ trượt￾(sliding￾window)￾có￾kích￾thước￾w￾(w￾do￾người￾dùng￾định￾nghĩa)￾trượt qua tất

cả các ký tự trong chuỗi dữ liệu. Các chuỗi con sinh ra từ cửa sổ trượt gọi là các từ

(word), mỗi từ được￾xem￾như￾một￾đặc￾trưng￾(feature).￾Một bảng￾băm￾(hash￾table)￾được

dùng￾để chứa￾các￾đặc￾trưng￾này,￾hai￾đặc￾trưng￾khớp (match) với nhau sẽ được chứa trong

cùng một￾thùng￾băm￾(bucket).￾Tìm￾thùng￾băm￾có￾kích￾thước lớn nhất, các phần tử trong

thùng￾băm￾này￾sẽ là ứng viên motif. Thực hiện tìm các thể hiện motif từ ứng viên motif

và ngưỡng khoảng cách tối￾đa￾ThresholdMax (ThresholdMax do￾người￾dùng￾định￾nghĩa)￾dựa

trên hàm tính khoảng cách Euclid. Giải thuật Hashing giải quyết bài toán khai thác motif

trong thời gian tuyến tính với￾kích￾thước tập dữ liệu, không gian sử dụng bộ nhớ gần￾như

hằng số.