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. Giới thiệu vấn đề Các phương pháp phân lớp chuỗi thời gian (time series) đòi hỏi việc huấn luyện một bộ phân lớp (classifier) trên một tập dữ liệu, mỗi mẫu dữ liệu là một tập có thứ tự của các thuộc tính mà giá trị của nó là số thực và được gắn nhãn lớp. Phương pháp phân lớp chuỗi thời gian đã và đang được nghiên cứu trong nhiều lĩnh vực, ví dụ như khai phá dữ liệu, thống kê, học máy, xử lý tín hiệu, v.v… Nhiều công trình nghiên cứu đã cải thiện độ chính xác của phương pháp phân lớp chuỗi thời gian.
Các nhà nghiên cứu trong lĩnh vực khai phá dữ liệu chuỗi thời gian đồng thuận rằng “bộ phân lớp một lân cận gần nhất là rất khó đánh bại” [3]. Ding và các cộng sự (2008) [4] bằng thực nghiệm đã cho thấy giải thuật 1-lân cận gần nhất (1-NN) kết hợp với độ đo DTW với kích thước cửa sổ xoắn được thiết lập thông qua kiểm tra chéo đã được chấp nhận là tiêu chuẩn vàng một cách rộng rãi. Trong công trình của Lines và các cộng sự (2015) [5], các tác giả đã dựa vào nghiên cứu của Ding và các cộng sự (2008) và tìm ra rằng tổ hợp bộ phân lớp 1-NN với các độ đo khoảng cách đàn hồi (elastic distance measure) khác nhau cho ra kết quả chính xác hơn bộ phân lớp đơn lẻ sử dụng độ đo DTW. Lines và các cộng sự tạo ra tổ hợp các bộ phân lớp 1-NN với bảy độ đo khoảng cách đàn hồi như sau: Dynamic Time Warping (DTW), Weighted Dynamic Time Warping (WDTW), Longest Common Subsequence (LCS), Edit Distance with Real Penalty (EDRP), Time Warping Edit Distance (TWED) và Move-Split-Merge (MSM).
Được gợi cảm hứng từ công trình của Lines và các cộng sự, năm 2020, Phạm Minh Trí [1], [2] đề xuất một phương pháp phân lớp 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 bao gồm các độ đo khoảng cách đàn hồi (elastic) và các độ đo khoảng cách không đàn hồi (non-elastic). Phạm Minh Trí tạo ra tổ hợp các bộ phân lớp 1-NN với năm độ đo khoảng cách như sau: DTW, 1 DDTW, DTW với cận dưới LB_Keogh (CDTW), độ đo Euclid và độ đo Bất biến với Độ Phức tạp (CID). Kết quả thực nghiệm trên 14 bộ dữ liệu mẫu cho thấy phương pháp phân lớp mà Trí đề xuất đã đạt được hiệu quả phân lớp khá tốt. Tuy nhiên nghiên cứu của Phạm Minh Trí (2020) cũng như nhiều công trình nghiên cứu đi trước khác chưa tối ưu tốc độ thực thi cho tổ hợp bộ phân lớp.
Chuỗi thời gian là dữ liệu có số chiều lớn gây tốn kém nhiều chi phí trong việc xử lý và lưu trữ. Ngoài hướng tiếp cận thu giảm số chiều mà vẫn giữ được các đặc trưng quan trọng, còn có hướng tiếp cận sử dụng sức mạnh xử lý song song của phần cứng như GPU (graphics processing unit) để tăng tốc tổ hợp bộ phân lớp. Tính toán bằng GPU đang được áp dụng rộng rãi trong các ứng dụng thông thường cũng như tính toán hiệu suất cao [6]. Mục tiêu của đề tài này là nghiên cứu chuyển đổi các phần của phương pháp phân lớp chuỗi thời gian sử dụng tổ hợp bộ phân lớp 1-NN với các độ đo khác nhau từ chạy tuần tự sang chạy song song với mô hình tính toán song song CUDA (Compute Unified Device Architecture) trên GPU của Nvidia.
Đề tài này hướng tới việc sử dụng sức mạnh trong tính toán song song của GPU để tăng tốc độ của phương pháp gốc đang tốn nhiều thời gian để thực thi. Bên cạnh đó, đề tài bổ sung thêm một độ đo khoảng cách mới để tăng thêm sự đa dạng của tổ hợp bộ phân lớp. Đề tài sẽ so sánh: (1) độ chính xác của phương pháp khi có thêm độ đo mới và (2) thời gian thực thi của phương pháp khi chạy trên GPU. Từ những kết quả đạt được, chúng ta sẽ biết được khả năng tăng tốc khi xử lý bằng GPU có tốt hơn hay không và tốt hơn bao nhiêu lần so với xử lý bằng CPU.
Điều này có ý nghĩa quan trọng khi lượng dữ liệu hiện nay ngày càng lớn, cũng như sức mạnh của GPU cũng ngày càng được nâng cao. 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 tổ hợp bộ phân lớp đề xuất khi thực thi trên GPU với các 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 thời gian, với các vấn đề chính như sau: - Thêm vào tổ hợp bộ phân lớp mà Phạm Minh Trí đề xuất một bộ phân lớp 1-NN với một độ đo khoảng cách không đàn hồi mới: Độ đo hệ số nén (Compression Rate Distance) (Vinh & Anh, 2015 [7]) 2 - Sử dụng sức mạnh xử lý song song của GPU để tăng tốc tổ hợp bộ phân lớp. 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 một tổ hợp bộ phân lớp 1-NN với các độ đo khoảng cách khác nhau và công nghệ GPU”. Kết quả này là tiền đề cho việc nghiên cứu tăng độ chính xác cũng như thời gian phân lớp đối với dữ liệu chuỗi thời gian.
Những 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. ‐ Hiểu rõ độ đo bất biến với độ phức tạp CID. ‐ Hiểu rõ độ đo khoảng cách Hệ Số Nén CRD.
‐ 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 tổ hợp bộ phân lớp 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, DDTW, CID, CRD trên GPU. ‐ So sánh độ chính xác của tổ hợp bộ phân lớp 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, DDTW, CID, CRD, tổ hợp bộ phân lớp 1-NN với các độ đo khoảng cách trên không bao gồm độ đo CRD. Kết quả thực nghiệm cho thấy tổ hợp bộ phân lớp 1-NN với các độ đo bao gồm độ đo CRD có độ chính xác cao hơn tổ hợp bộ phân lớp 1-NN với các độ đo khoảng cách không bao gồm độ đo CRD.
‐ So sánh thời gian xử lý của tổ hợp bộ phân lớp 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, DDTW, CID, CRD trên GPU và tổ hợp bộ phân lớp 1-NN 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, CRD trên CPU. Kết quả cho thấy thời gian xử lý của tổ hợp bộ phân lớp trên GPU nhanh hơn trên CPU trung bình 48 lần. 3 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.
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, các phương pháp phân lớp dữ liệu chuỗi thời gian, lý thuyết về các độ đo khoảng cách của chuỗi thời gian và lý thuyết về lập trình CUDA trên GPU. Chương 3 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, tổ hợp bộ 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 phương pháp 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 tổ hợp bộ phân lớp 1-NN với 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 và thời gian thực thi của phương pháp phân lớp đề xuất. 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. 4 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 chuỗi thời gian, các tiêu chí đánh giá độ chính xác trong kỹ thuật phân lớp. Chuỗi thời gian Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu có thứ tự, mỗi điểm biểu diễn một giá trị là số thực được đo tại những thời điểm cách đều nhau.
Chuỗi thời gian được sử dụng trong xác suất thống kê, tài chính, nhận dạng mẫu, dự đoán thời tiết, v.v… và được sử dụng nhiều trong các lĩnh vực khoa học ứng dụng và kỹ thuật. Chuỗi thời gian thường được giả định là được sinh ra tại những thời điểm cách đều nhau, do đó được gọi là chuỗi thời gian thông thường (regular time series). Một chuỗi thời gian bất quy tắc (irregular time series) là một chuỗi các điểm dữ liệu có thứ tự nhưng không được đo tại các thời điểm cách đều nhau. Có vô số cách thể hiện một chuỗi thời gian.
Tuy nhiên, khi chúng ta quan sát chuỗi thời gian, chúng ta nhận thấy rằng dữ liệu chuỗi thời gian thường chia thành bốn dạng phổ biến đó là xu hướng (trend), chu kỳ (cyclical), mùa (seasonal) và bất quy tắc (irregular). Phân lớp dữ liệu 2. Khái niệm phân lớp dữ liệu Phân lớp dữ liệu là giải thuật xác định một mẫu dữ liệu thuộc vào lớp nào trong một tập các lớp thông qua việc phân tích các thuộc tính quan trọng của mẫu dữ liệu đó. Một số bộ phân lớp làm việc bằng cách so sánh khoảng cách giữa các mẫu với nhau.
Một giải thuật hiện thực phân lớp dữ liệu được gọi là một bộ phân lớp (classifier). Quá trình xây dựng một bộ phân lớp gồm có hai bước: huấn luyện (training) và phân lớp (classification).
