Phát hiện bất thường trên dữ liệu chuỗi thời gian bằng giải thuật disk aware :Luận văn thạc sĩ - Chuyên ngành: Khoa học máy tính

BỘ CÔNG THƯƠNG

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

-------------------

TRẦN MINH TIẾN

PHÁT HIỆN BẤT THƯỜNG TRÊN DỮ LIỆU

CHUỖI THỜI GIAN BẰNG GIẢI THUẬT

DISK AWARE

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 2017

Công trình được hoàn thành tại: Trường Đại học Công Nghiệp TP.HCM

Cán bộ hướng dẫn khoa học : TS. Nguyễn Thành Sơn

Người phản biện 1 : TS. Võ Thị Ngọc Châu

Người phản biện 2 : 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 Tp. HCM ngày 09 tháng 8 năm 2017.

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

(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ĩ)

1. PGS.TS. Phạm Thế Bảo Chủ tịch HĐ

2. TS. Võ Thị Ngọc Châu Phản biện 1

3. TS. Phạm Văn Chung Phản biện 2

4. TS. Lê Nhật Duy Uỷ viên

5. TS. Phạm Thị Thiết Thư ký

Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý

chuyên ngành sau khi luận văn đã được sửa chữa (nếu có).

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

BỘ CÔNG THƯƠNG CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP Độc lập - Tự do - Hạnh phúc

THÀNH PHỐ HỒ CHÍ MINH

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

Họ tên học viên: Trần Minh Tiến MSHV: 15001271

Ngày, tháng, năm sinh: 11- 03 – 1985 Nơi sinh: Tây Ninh

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

I. TÊN ĐỀ TÀI:

PHÁT HIỆN BẤT THƯỜNG TRÊN DỮ LIỆU CHUỖI THỜI GIAN

BẰNG GIẢI THUẬT DISK AWARE DISCORD DISCOVERY

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

Nội dung báo cáo luận văn tốt nghiệp về tìm hiểu và cài đặt thuật toán phát hiện bất

thường trên dữ liệu chuỗi thời gian dựa trên phương pháp Disk Aware Discord

Discovery của tác giả Yankov và cộng sự đề xuất (2008). Ngoài ra, báo cáo còn cải

tiến phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian bằng giải thuật

Disk Aware Discord Discovery của Yankov và cộng sự. Cuối cùng, báo cáo trình bày

kết quả thực nghiệm trên các tập dữ liệu chuỗi thời gian, sau đó so sánh độ hiệu quả

và thời gian xử lý giữa ba thuật toán: Brute Force, Disk Aware Discord Discovery và

thuật toán cải tiến được đề xuất trong luận văn.

II. NGÀY GIAO NHIỆM VỤ: 29 – 12 - 2016

III. NGÀY HOÀN THÀNH NHIỆM VỤ: 29 – 06 -2017.

IV. CÁN BỘ HƯỚNG DẪN: TS. NGUYỄN THÀNH SƠN

Tp. HCM, ngày 29 tháng 6 năm 2017

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

(Họ tên và chữ ký) (Họ tên và chữ ký)

Nguyễn Thành Sơn

TRƯỞNG KHOA …..

(Họ tên và chữ ký)

i

LỜI CẢM ƠN

Em xin chân thành cảm ơn sự hướng dẫn tận tình trong suốt thời gian qua của thầy

Nguyễn Thành Sơn, khoa Công nghệ thông tin trường Đại học Sư phạm Kỹ thuật

Tp.HCM. Thầy đã định hướng, góp ý và cung cấp cho em rất nhiều kiến thức về một

lĩnh vực mới khi em bắt đầu thực hiện luận văn.

Em cũng xin gửi lời cảm ơn chân thành đến các thầy, cô trong khoa Công nghệ thông

tin trường Đại Học Công Nghiệp TP. HCM, cũng như các thầy cô trong trường Đại

Công Nghiệp Tp.HCM đã giảng dạy giúp đỡ em trong những năm học vừa qua.

ii

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

Dữ liệu chuỗi thời gian được sử dụng phổ biến trong các lĩnh vực khoa học, công

nghệ, tài chính, thương mại, y học, thời tiết, môi trường, địa lý. Theo khảo sát của

Tufte [1] (1992), từ 4000 hình được lấy ngẫu nhiên trong các báo tin tức trên thế giới

được xuất bản trong giai đoạn từ 1974 đến 1989 cho thấy hơn 75% là các hình biểu

diễn dữ liệu chuỗi thời gian.

Phát hiện bất thường trên dữ liệu chuỗi thời gian đã và đang nhận được rất nhiều sự

quan tâm trong cộng đồng nghiên cứu trong những năm qua. Nó đã và đang được sử

dụng để giải nhiều bài toán trong các lĩnh vực ứng dụng khác nhau như các chẩn đoán

lỗi, phát hiện các giao dịch lừa lọc, phát hiện sự xâm nhập mạng, các thay đổi trong

thói quen của khách hàng, làm sạch dữ liệu…

Nhiều thuật toán đã được giới thiệu để giải quyết vấn đề này như thuật toán Brute

Force Discord Discovery (BFDD) [2], thuật toán Heuristic Discord Discovery (HDD)

[2], tuy nhiên chưa đem lại hiệu quả cao. Vì vậy, việc nghiên cứu đề xuất các thuật

toán mới hoặc cải tiến các thuật toán đã có sao cho hiệu quả hơn vẫn luôn được các

nhà nghiên cứu quan tâm thực hiện.

Trong luận văn này, em tìm hiểu và cài đặt ba thuật toán: Brute Force Discord

Discovery, Disk Aware Discord Discovery của Yankov và cộng sự đề xuất và thuật

toán cải tiến được đề xuất trong luận văn.

Luận văn thực nghiệm trên các bộ dữ liệu, sau đó so sánh độ hiệu quả (về mặt thời

gian và vị trí bất thường) của thuật toán cải tiến được đề xuất trong luận văn so với

hai thuật toán Brute Force Discord Discovery và Disk Aware Discord Discovery được

Yankov và cộng sự đề xuất.

iii

ABSTRACT

Time series data are commonly used in the fields of science, technology, finance,

commerce, medicine, weather, the environment, and geography. According to Tufte's

survey (1992) [1], 4,000 photographs taken randomly in world newsletters published

between 1974 and 1989 showed that more than 75% were sequence data

representations time.

Unusual discovery in the time series has been receiving a great deal of interest in the

research community over the years. It has been used to solve many problems in

various application areas such as error diagnosis, fraud detection, network intrusion

detection, changes in customer habits. , Data cleaning, etc.

Many algorithms have been introduced to solve this problem, such as Brute Force

Discord Discovery algorithm (BFDD) [2], Heuristic Discord Discovery algorithm

[2], however they are not effective. Therefore, the research proposed new algorithms

or improved algorithms have been more effective is always taken care of by

researchers.

In this topic, The experimental thesis on data sets, then compare the fficiency

(processing time and location appear) of the algorithm proposed improvements in

the thesis compared to two algorithms Brute Force Discord Discovery and Disk

Aware Discord Discovery is proposed by Yankov et al.