CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Trong chương này, chúng tôi sẽ trình bày các vấn đề mà đề tài tập trung nghiên cứu, các động cơ để thực hiện, mục tiêu cụ thể của đề tài. Ngoài ra, chúng tôi sẽ mô tả các kết quả đạt được trong quá trình nghiên cứu, khảo sát nội dung của đề tài.1 Giới thiệu vấn đề Việc nghiên cứu và ứng dụng kỹ thuật phân lớp chuỗi dữ liệu thời gian hiện nay đang được thu hút nhiều sự chú ý của các nhà nghiên cứu dữ liệu. Với sự phát triển nhanh về công nghệ, dữ liệu chuỗi thời gian được thu thập bởi rất nhiều thiết bị. Việc khai phá dữ liệu của dữ liệu chuỗi thời gian mang lại lợi ích hữu hiệu trải dài nhiều lĩnh vực từ y tế đến dự báo thời tiết.
Đối với dữ liệu chuỗi thời gian, vấn đề đặt ra là chúng ta cần thực hiện phân lớp (classification) chúng để có thể sử dụng hiệu quả cho các mục đích khác nhau: phân tích dữ liệu, dự báo. Phân lớp dữ liệu chuỗi thời gian là xây dựng một bộ phân lớp (classifier) dựa trên các chuỗi thời gian đã được gắn nhãn lớp để xác định nhãn lớp cho các chuỗi thời gian chưa được phân lớp. Một số phương pháp truyền thống để thực hiện bài toán phân lớp như: k-lân cận gần nhất, mạng nơ ron, cây quyết định,… Mặc dù có khá nhiều công trình nghiên cứu về bài toán phân lớp dữ liệu thông thường, hầu hết các giải thuật kinh điển trong hai lĩnh vực học máy và khai phá dữ liệu đã không làm việc tốt với dữ liệu chuỗi thời gian, do những tính chất đặc biệt của loại dữ liệu này. Ba tính chất của dữ liệu chuỗi thời gian gồm có: (i) Số chiều nhiều, (ii) mối tương quan cao giữa các điểm dữ liệu trên chuỗi thời gian và (iii) dữ liệu có thể có nhiễu đã khiến cho việc phân tích và khai phá dữ liệu trên loại dữ liệu này trở nên khó khăn và đầy thách thức.
1 Phương pháp phân lớp chuỗi dữ liệu thời gian có thể chia làm ba loại chính: phương pháp dựa vào đặc trưng, phương pháp dựa vào mô hình, phương pháp dựa vào khoảng cách. Thứ nhất, trong phương pháp phân lớp dựa vào đặc trưng, dữ liệu chuỗi thời gian được chuyển đổi thành các vector đặc trưng và sau đó phân lớp bởi các bộ phân lớp thông dụng như mạng neutron nhân tạo hoặc cây quyết định,. Một số phương pháp trích xuất đặc trưng bao gồm các phương pháp phổ như: biến đổi chuỗi Fourier rời rạc(Discrete Fourier transform - DFT) hoặc biến đổi wavelet rời rạc (Discrete Wavelet transform - DWT), Shapelet[1] ,… Thứ hai, phương pháp dựa vào mô hình, mô hình phân lớp được giả định rằng tất cả chuỗi thời gian trong một lớp được tạo ra bởi cùng mô hình cơ bản và do đó một chuỗi thời gian mới được gán với lớp của mô hình hợp hợp nhất với nó. Một vài tiếp cận dựa vào mô hình như: tự hồi quy(auto-regressive) , Markov ẩn( hidden Markov),… Cuối cùng, phương pháp dựa vào khoảng cách, sử dụng các đo độ tương tự hoặc không tương tự để đo khoảng cách giữa các chuỗi thời gian và sau đó các khoảng cách này được sử dụng trong các mô hình phân lớp như: k-nearest neighbor(k-NN) và SVM(Support Vector Machines ),.
Trong luận văn này, chúng tôi chọn cách tiếp cận ở phương pháp cuối cùng, phương pháp phân lớp dựa vào khoảng cách. Đối với phương pháp phân lớp chuỗi thời gian dựa trên khoảng cách, các độ đo khoảng cách được sử dụng và sau đó khai thác chúng trong bộ phân lớp k-NN. Nhiều đánh giá đã được thực hiện Ding và các cộng sự năm 2008 [2] cho thấy rằng bộ phân lớp 1-NN là một trong những bộ phân lớp tốt nhất trong các phương pháp phân lớp dữ liệu chuỗi thời gian. Trong các độ đo khoảng cách (distance measures) được sử dụng trong dữ liệu chuỗi thời gian.
Mỗi loại dữ liệu chuỗi thích ứng với một số độ đo nhất định. Nhằm mục tiêu tăng độ chính xác độ phân lớp của dữ liệu chuỗi thời gian. Câu hỏi đặt ra rằng liệu rằng chúng ta xây dựng một tổ hợp(ensemble) các độ đo này sau đó sử dụng chúng vào kỹ thuật phân lớp 1-NN. Vì vậy, đề tài luận văn này sẽ đưa ra một cách tiếp cận để giải quyết bài toán tăng độ chính xác phân lớp bằng cách kết hợp các độ đo khoảng cách dữ liệu chuỗi thành một tổ hợp (ensemble) các độ đo khoảng cách và phân lớp dữ liệu dựa trên tổ hợp này.2 Mục tiêu Chúng tôi thực hiện đề tài này nhằm đánh giá hiệu năng của giải thuật 1-NN với tổ hợp các độ đo khoảng cách: Euclid, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, DDTW, CID với tiêu chí: (1) độ chính xác phân lớp và (2) đánh giá thời gian thực thi trong việc phân lớp chuỗi thời gian cho bài toán phân lớp chuỗi dữ liệu thời gian, với các vấn đề chính như sau: o Nghiên cứu tính toán độ đo xoắn thời gian động DTW với kỹ thuật tính chặn dưới LB_Keogh.
o Nghiên cứu độ đo DDTW, biến thể của độ đo DTW. o Nghiên cứu độ đo bất biến với độ phức tạp CID. o Nghiên cứu hiện thực giải thuật 1-NN với các độ đo khoảng cách: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, CID. o Nghiên cứu hiện thực giải thuật 1-NN với tổ hợp các độ đo khoảng cách: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, DDTW, CID.
o So sánh độ chính xác(tỉ lệ lỗi phân lớp càng nhỏ, đo chính xác càng cao) giữa giải thuật 1-NN với các độ đo tương ứng và 1-NN với tổ hợp các độ đo trên một số dữ liệu mẫu lấy từ website [3].3 Phạm vi nghiên cứu Phạm vi của đề tài này là đề xuất, nghiên cứu, hiện thực, đánh giá” Phân lớp dữ liệu chuỗi thời gian dựa vào tổ hợp bộ phân lớp 1-NN với các độ đo khoảng cách khác nhau”. Kết quả này là tiền đề cho việc nghiên cứu tăng độ chính xác phân lớp đối với dữ liệu chuỗi thời gian.4 Tóm lược kết quả đạt được Sau thời gian nghiên cứu và hiện thức, chúng tôi đạt được các kết quả như sau: - Hiểu rõ độ đo xoắn thời gian động DTW thuần tuý và DTW với kỹ thuật tính chặn dưới LB_Keogh. - Hiểu rõ độ đo DDTW, một biến thể của độ đo DTW. 3 - Hiểu rõ độ đo bất biến với độ phức tạp CID.
- Nắm được giải thuật k- lân cận gần nhất (k-NN) dùng cho bài toán phân lớp dữ liệu chuỗi thời gian. - Hiện thực thành công giải thuật 1-NN với các độ đo: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, DDTW, CID. - Hiện thực thành công giải thuật 1-NN với bộ tổ hợp các độ đo khoảng cách: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, DDTW, CID. - So sánh độ chính xác của giải thuật 1-NN các độ đo: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, DDTW, CID và giải thuật 1-NN với bộ tổ hợp các độ đo khoảng cách trên.
Kết quả thực hiện cho thấy giải thuật 1-NN với bộ tổ hợp các độ đo có độ chính xác cao hơn giải thuật 1-NN với các đo đo khoảng cách riêng rẻ. Nhưng đổi lại thời gian chạy giải thuật 1-NN với bộ tổ hợp các độ đo rất lâu so với giải thuật 1-NN với độ đo khoảng cách riêng rẻ. - So sánh độ chính xác và thời gian xử lý của giải thuật 1-NN với các độ đo thành phần. Kết quả cho thấy độ đo CID có độ chính xác và thời gian chạy nhanh hơn so với các độ đo còn lại.
- Qua thực nghiệm, chúng tôi cũng đề xuất cải tiến thuật toán song song đa luồng và kết quả thu được là thời gian phân lớp nhanh hơn 2, 3 lần so với thời gian phân lớp 1-NN với bộ tổ hợp các độ đo. Như vậy, về cơ bản chúng tôi đã đáp ứng được yêu cầu của đề tài đặt ra. Chúng tôi sẽ trình bày chi tiết trong các phần sau.5 Cấu trúc của luận văn Tổ chức các thành phần còn lại của luận văn gồm các phần như sau: Chương 2 là các cơ sở lý thuyết mà chúng tôi sử dụng trong luận văn này. Bao gồm các lý thuyết cơ bản về chuỗi thời gian, lý thuyết về các độ đo khoảng cách của chuỗi thời gian, các phương pháp phân lớp chuỗi dữ liệu chuỗi thời gian, các phương pháp chuẩn hoá dữ liệu và các tiêu chí đánh giá độ chính xác trong kỹ thuật phân lớp.
4 Chương 3 của đề tài sẽ giới thiệu các công trình nghiên cứu liên quan. Các công trình này trình bày về các kỹ thuật phân lớp, các độ đo khoảng cách trong dữ liệu chuỗi thời gian, từ cơ sở này đề xuất giải thuật nhằm tăng độ chính xác phân lớp trong việc phân lớp dữ liệu chuỗi thời gian. Chương 4 bao gồm các nội dung chi tiết cho việc thiết kế và hiện thực kỹ thuật phân lớp 1-NN với bộ tổ hợp các độ đo khoảng cách khác nhau. Chương 5 của đề tài này sẽ trình bày các kết quả thực nghiệm đạt được trong quá trình nghiên cứu, qua đó đánh giá được độ chính xác của kỹ thuật phân lớp, so sánh độ chính xác giữa kỹ thuật phần lớp 1-NN với độ đo khoảng cách: ED, DTW, DTW với kỹ thuật tính chặn dưới LB_Keogh, CID và kỹ thuật phân lớp 1-NN với bộ tổ hợp các độ đo khoảng cách.
Đồng thời, qua việc thực nghiệm, đánh giá được độ chính xác và thời gian thực thi của các độ đo khoảng cách khi được sử dụng trong kỹ thuật phân lớp 1-NN. Chương 6 là một số kết luận, đóng góp của đề tài và hướng phát triển trong tương lai của đề tài. 5 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bày cơ sở lý thuyết về chuỗi thời gian, các thành phần của chuỗi thời gian, các độ đo khoảng cách sử dụng cho dữ liệu chuỗi thời gian, các kỹ thuật ràng buộc, các phương pháp phân lớp chuỗi dữ liệu chuỗi thời gian, các tiêu chí đánh giá độ chính xác trong kỹ thuật phân lớp.1 Chuỗi thời gian Một chuỗi thời gian (time series), ký hiệu toán học là T, là chuỗi giá trị số thực, trong đó mỗi trị biểu diễn một giá trị tại những thời điểm cách đều nhau: T = 𝑡" , 𝑡$ , … , 𝑡&. Phân tích chuỗi thời gian có mục đích là nhận dạng và tập hợp các yếu tố, những biến đổi theo thời gian mà nó ảnh hưởng đến giá trị của biến quan sát.
Dữ liệu chuỗi thời gian có lượng dữ liệu rất lớn và xuất hiện trong nhiều lĩnh vực ngày nay như y học, kỹ thuật, tài chính, v.