Các độ đo khoảng cách trên chuỗi dữ liệu thời gian ứng dụng trong phân tích và quản trị dữ liệu thông minh (Distance measures for Time series data in Smart Data Analytics and Management)

Chia sẻ: Liễu Yêu Yêu | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

19
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết "Các độ đo khoảng cách trên chuỗi dữ liệu thời gian ứng dụng trong phân tích và quản trị dữ liệu thông minh (Distance measures for Time series data in Smart Data Analytics and Management)" giới thiệu một số phương pháp xác định độ đo khoảng cách thường áp dụng trong việc xác định khoảng cách khác biệt giữa các điểm dữ liệu trong chuỗi dữ liệu theo thời gian. Đây là một vấn đề quan trọng trong việc xây dựng mô hình các bài toán về quản trị dữ liệu thông minh và phân tích dữ liệu thông minh trên các chuỗi dữ liệu theo thời gian (Time Series Data). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các độ đo khoảng cách trên chuỗi dữ liệu thời gian ứng dụng trong phân tích và quản trị dữ liệu thông minh (Distance measures for Time series data in Smart Data Analytics and Management)

CÁC ĐỘ ĐO KHOẢNG CÁCH TRÊN CHUỖI DỮ LIỆU THỜI GIAN ỨNG DỤNG TRONG PHÂN TÍCH VÀ QUẢN TRỊ DỰ LIỆU THÔNG MINH (Distance measures for Time series data in Smart Data Analytics and Management) VÕ XUÂN THỂ Khoa Công nghệ Thông tin. Trường Đại học Tài chính – Marketing Email: vxthe@ufm.edu.vn Tóm tắt: Bài viết này giới thiệu một số phương pháp xác định độ đo khoảng cách thường áp dụng trong việc xác định khoảng cách khác biệt giữa các điểm dữ liệu trong chuỗi dữ liệu theo thời gian. Đây là một vần đề quan trọng trong việc xây dựng mô hình các bài toán về quản trị dữ liệu thông minh và phân tích dữ liệu thông minh trên các chuỗi dữ liệu theo thời gian (Time Series Data). Có rất nhiều bài toán về dữ liệu thông minh trên chuỗi dữ liệu thời gian được áp dụng trong thực tiễn thuộc nhiều lĩnh vực khác nhau, như: kinh tế, xã hội, khoa học – kỹ thuật. Đây là những bài toán góp phần vào Cách mạng công nghiệp lần thứ 4 trên nền tảng BigData. Mỗi độ đo khoảng cách có tính hiệu quả nhất định cho từng bài toán Data Base theo từng dự án (Projetc) thực tiễn, vì vậy việc lựa chọn một độ đo khoảng cách hợp lý cho từng bài toán là rất cần thiết, và đó cũng là mục tiêu giới thiệu của bài viết này. Một số độ đo thông dụng thường áo dụng trên chuỗi dữ liệu theo thời gian, như: độ đo Hamming, độ đo tựa (tương tự) Cosin, độ đo Minkowski , độ đo Manhattan, độ đo Euclidean và độ đo Chebyshev sẽ được giới thiệu trong bài viết này. đặc biệt là độ đo Euclidean. Từ khóa: Chuỗi dữ liệu thời gian – Time series data, độ đo khoảng cách - Distance Measures, Phân tích dữ liệu thông minh – Smart Data analytics, Quản trị dữ liệu thông tin – Smart Data Management. 1. GIỚI THIỆU CHUNG Cuộc cách mạng công nghiệp lần thứ 4 đã và đang mang lại nhiều kết quả cũng như thách thức lớn cho ngành khoa học máy tính nói chung và lĩnh vực khai phá dữ liệu nói riêng, đặc biệt là dữ liệu có yếu tố thời gian như: tỷ giá ngoại tệ, giá vàng, chỉ số chứng khoán, dự báo thời tiết, thiên văn học, đo mực nước, điện tâm đồ,… Hướng nghiên cứu trong lĩnh vực khai phá dữ liệu và học máy được nhiều giới khoa học quan tâm hiện nay. Một trong nhưng khai phá dữ liệu phổ biến hiện nay là khai phá dữ liệu chuỗi thời gian đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trên thế giới. Có rất nhiều dạng bài toán khai phá dữ liệu chuỗi thời gian như: Gom cụm, Lập chỉ mục, Phân lớp, Phát hiện Motif, Phát hiện bất thường,. . .được áp dụng trong nhiều lĩnh 350
vực như: chứng khoán - tài chính – ngân hàng, y học, thiên văn học, địa chất, côn trùng học … Các lĩnh vực nghiên cứu như y học hay tài chính, ngân hàng, … thường yêu cầu về độ chính xác cao. Việc lựa chọn độ đo khoảng cách hợp lý cho các bài toán nêu trên là rất cần thiết, vì mỗi dữ liệu chuỗi thời gian có những đặc tính và đặc thù riêng của nó (tùy theo dự án: project đang thực hiện) nên độ đo khoảng cách thường ảnh hưởng nhiều đến các kết quả khai phá dữ liệu. Cho nên việc xác định độ đo khoảng cách trên dữ liệu chuỗi thời gian đóng vai trò quan trọng đối với những bài toán khai phá dữ liệu chuỗi thời gian. Bài viết này nhằm giới thiệu tổng quan mang tính học thuật về các độ đo khoảng cách thường áp dụng trên các chuỗi dữ liệu thời gian trong các các bài toán về phân tích và quản trị dữ liệu thông minh. Đối tượng tham khảo bài viết này gồm: các giảng viên đại học, người học, nhà nghiên cứu thuộc chuyên ngành Khoa học dữ liệu và Khoa học máy tính nói chung. 2. GIỚI THIỆU VỀ CHUỖI DỮ LIỆU THỜI GIAN 2.1. Chuỗi thời gian (Time Series Data: TSD) 1 Chuỗi thời gian T = t1, t2, … tn là một tập theo thứ tự các biến giá trị thực có chiều dài n. Ví dụ về chuỗi thời gian là: lưu lượng mưa hàng năm ở miền nam Việt Nam, kết quả điện tâm đồ (như Hình 11) [19], thời tiết… Hình 11. Minh họa về chuỗi dữ liệu thời gian Điện tâm đồ ECG 1 Có nhiều khái niệm về TSD (theo nhiều góc độ khác nhau), đây là khái niệm được tổng hợp và biên tập bởi tác giải bài viết này. 351
2.2. Chuỗi con Cho một chuỗi con Ti,m của chuỗi thời gian T = (t1, t2…, tn), là một tập hợp con liên tục các giá trị của T có độ dài m, bắt đầu từ vị trí i. Ti,m = (ti,ti+1,…,ti+m-1) với 1≤ i ≤ n-m+1 [1]. 2.3. Cửa sổ trượt (Sliding Window) Cho một dữ liệu chuỗi thời gian T có chiều dài n, để xác định được chuỗi con có chiều dài m, ta dùng một cửa sổ trượt có kích thước m trượt qua từng điểm từ trái sang phải trên chuỗi T để xác định mỗi chuỗi con Q như Hình 12. Hình 12. Minh họa cửa sổ trượt trên chuỗi dữ liệu thời gian 2.4. So trùng mẫu Cho một số thực R (gọi là phạm vi và do người dùng định nghĩa) và một dữ liệu chuỗi thời gian T chứa một chuỗi con C bắt đầu tại vị trí p và một chuỗi con M bắt đầu tại vị trí q, nếu hàm tính khoảng cách từ C đến M ký hiệu D(C, M) ≤ R (ta dùng công thức tính khoảng cách euclid để tính toán khoảng cách giữa 2 chuỗi con) [1] thì ta nói là chuỗi con M khớp được với chuỗi con C, như Hình 13. Hình 13. Minh họa về So trùng mẫu giữa chuỗi con C và chuỗi con M được trích từ chuỗi dữ liệu thời gian T 2.4.1. So trùng tầm thường Cho một số thực dương R và một chuỗi thời gian T. Một chuỗi con Ci của T bắt đầu tại vị trí i và một chuỗi con Cj của T bắt đầu tại vị trí j, nếu DIST(Ci , Cj) ≤ R thì Cj được gọi là chuỗi con tương tự của Ci. Các chuỗi con tương tự nhất với một chuỗi con Ci là các chuỗi con bắt đầu tại các 352
vị trí lệch một hay hai điểm về bên trái hay bên phải so với vị trí bắt đầu của chuỗi con Ci. Có nghĩa là chuỗi con mới lệch một khoảng so với chuỗi con cũ và hai chuỗi con này có chung một đoạn giá trị. Các trường hợp này được gọi là so trùng tầm thường, như Hình 14 [1]. Hình 14. So trùng tầm thường trên 2 chuỗi con của chuỗi dữ liệu thời gian T 2.4.2. So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n, chuỗi C và M có chiều dài m và là chuỗi con của chuỗi thời gian T. Chuỗi C bắt đầu tại vị trí p, chuỗi M bắt đầu tại vị trí q. Ta nói chuỗi con M và chuỗi con C so trùng không tầm thường nếu |p-q| ≥ m. [1] Đối với bài toán khoa học dữ liệu trên dữ liệu chuỗi thời gian, như: bài toán tìm kiếm tương tự, gom cụm, phân loại trên dữ liệu thời gian thì dữ liệu chuỗi thời gian là dãy các số thực T=t1, t2,…tn. Đối với những bài toán này đòi hỏi chúng ta phải định nghĩa một độ đo tương tự giữa các cặp chuỗi thời gian với nhau. Cho 2 chuỗi thời gian Q và C bất kỳ. Ta cần tính độ đo tương tự Dist(Q, C) của hai chuỗi thời gian này. Để tính toán chính xác thì các độ đo cần thỏa một số tính chất cơ bản sau: - Dist(Q,C) = 0 nếu và chỉ nếu Q = C - Dist(Q,C) = Dist(C,Q) - Dist(Q,C) ≥ 0 với mọi Q, C - Dist(Q,C) < Dist(Q, Z) + D(C, Z) Có nhiều độ đo khoảng cách khác biệt giữa các chuỗi con hoặc các điểm dữ liệu thường áp dụng trên chuỗi dữ liệu thời gian ban đầu như giới thiệu trong phần 353
3. GIỚI THIỆU VỀ CÁC ĐỘ ĐO KHOẢNG CÁCH Sau đây bài viết giới thiệu một số giá trị độ đo khoảng cách khác biệt giữa các chuỗi con hoặc điểm dữ liệu thường được áp dụng trên chuỗi dữ liệu thời gian trong các bài toán phân tích và và quản trị dữ liệu thông minh: + Độ đo khoảng cách khác biệt d giữa các chuỗi con giữ vai trò quan trọng trong các bài toán dữ liệu. + Độ đo khoảng cách d phải được xác định trước và nhất quán trong suốt quá trình bài toán. + Các hàm tính độ đo khoảng cách được áp dụng cho các bài toán với thuộc tính đầu vào xi thông thường là số thực. 3.1. Độ đo khoảng cách Hamming Thường được áp dụng các bài toán có xi trong chuỗi dữ liệu thời gian là nhị phân 𝑛 𝐷𝑖𝑠𝑡(𝑥, 𝑧) = ∑ 𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑐𝑒(𝑥𝑖 , 𝑧𝑖 ) 𝑖=1 Trong đó xi và zi là các giá trị nhi phân: difference (= 1, nếu xi và zi khác nhau; = 0 nếu xi và zi giống nhau) 3.2. Độ đo khoảng cách tựa (tương tự) Cosin Còn gọi là Cosine Similarity Distance Function [22]. Thường được áp dụng cho các bài toán có dữ liệu trong chuỗi dữ liệu thời gian dạng văn bản : xi là trọng số TF||IDF của từ khóa thứ i Term Trequency – Inverse Document Frequency 𝑥. 𝑧 ∑𝑛𝑖=1 𝑥𝑖 . 𝑧𝑖 𝐷𝑖𝑠𝑡(𝑥, 𝑧) = = ‖𝑥‖‖𝑧‖ √∑𝑛𝑖=1 𝑥𝑖 2 √∑𝑛𝑖=1 𝑧𝑖 2 3.3. Độ đo khoảng cách Minkowski Dùng gàm Minkowski (-norm). Nếu p =2 là Euclidean (thường dùng) Hầu hết các công trình nghiên cứu trên dữ liệu chuỗi thời gian đều dựa trên độ đo Minkowski để tính khoảng cách (hay mức độ tương tự) giữa hai chuỗi con. Công thức tính khoảng cách Minkowski được định nghĩa như sau: 𝑝 𝐷𝑖𝑠𝑡(𝑄, 𝐶) = √∑𝑛𝑖=1(𝑞𝑖 − 𝑐𝑖 )𝑝 ) 354
với qi ∈ Q, ci ∈ C, i = 1, …, n Khi p = 1 ta có khoảng cách Manhattan Khi p = 2 ta có khoảng cách Euclid Khi p = ∞ ta có khoảng cách Max Ở công thức trên thì giá trị của p có thể chọn bất kỳ, nhưng thông thường trong các nghiên cứu về chuỗi dữ liệu thời gian thì thường sử dụng độ đo Euclid vì nó đơn giản, dễ thực hiện và là khoảng cách hình học trong không gian đa chiều với độ chính xác chấp nhận được . Ưu điểm: + Tính toán nhanh, đơn giản. + Sử dụng trong nhiều bài toán khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân lớp, phát hiện bất thường trên dữ liệu chuỗi thời gian. + Độ đo Minkowski thỏa mãn bất đẳng thức tam giác nên có thể hỗ trợ việc lập chỉ mục dữ liệu, giảm thời gian phát hiện bất thường trên dữ liệu chuỗi thời Nhược điểm: + Nhạy cảm với nhiễu + Các chuỗi thời gian có độ dài như nhau + Đối với dữ liệu có đường căn bản khác nhau thì thuật toán này chưa xử lý tốt (Hình 5) + Không thích hợp khi dữ liệu có biên độ dao động khác nhau. (Hình 6) Hình 15. Chuỗi dữ liệu thời gian có đường căn bản khác biệt Hình 16. Chuỗi dữ liệu thời gian có biên độ dao động khác nhau Để khắc phục một số nhược điểm của độ đo này thì ta có thể sử dụng phương pháp chuẩn hóa dữ liệu (Data normalization). Hai phương pháp chuẩn hóa dữ liệu đang được sử dụng hiện nay là: ❖ Chuẩn hóa trung bình Zero [1]: Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]− 𝑚𝑒𝑎𝑛(𝑄) Q’[i] = 𝑣𝑎𝑟(𝑄) 355
Với mean(Q) là giá trị trung bình và var(Q) là độ lệch chuẩn của Q. Trong trường hợp không biết được giá trị lớn nhất và nhỏ nhất của tập dữ liệu hay có những giá trị cá biệt thì phương pháp này có thể được áp dụng. ❖ Chuẩn hóa Min-Max [1]: Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]−𝑀𝑖𝑛𝑜𝑙𝑑 𝑄’[𝑖] = (𝑀𝑎𝑥𝑛𝑒𝑤 − 𝑀𝑖𝑛𝑛𝑒𝑤 ) + 𝑀𝑖𝑛𝑛𝑒𝑤 𝑀𝑎𝑥𝑜𝑙𝑑 −𝑀𝑖𝑛𝑜𝑙𝑑 Với Minold và Maxold là giá trị nhỏ nhất và lớn nhất của chuỗi Q ban đầu. Minnew và Maxnew là giá trị nhỏ nhất và lớn nhất của chuỗi Q’ là chuỗi sau khi được chuẩn hóa. Chuẩn hóa Min-Max đảm bảo được mối quan hệ giữa các giá trị của dữ liệu ban đầu nhưng phương pháp này sẽ gặp phải lỗi ngoài giới hạn nếu một giá trị ban đầu vào tương lai nằm ngoài đoạn giá trị [Min – Max] ban đầu. 3.4. Độ đo khoảng cách Manhattan Dùng hàm Manhattan (=1): 𝐷𝑖𝑠𝑡 (𝑥, 𝑧) = ∑𝑛𝑖=1|𝑥𝑖 − 𝑧𝑖 | Là trường hợp các biệt của độ đo khoảng cách Minkowski với p =1 3.5. Độ đo khoảng cách Euclidean Dùng Hàm Euclidean (=2): 𝐷𝑖𝑠𝑡(𝑥, 𝑧) = √∑𝑛𝑖=1(𝑥𝑖 − 𝑧𝑖 )2 Cũng là trường hợp các biệt của độ đo khoảng cách Minkowski với p =2. Đây là độ đo khoảng cách phổ biết nhất áp dụng trong các bài toán khoa học dữ liệu, đặc biệt là bài toán trên chuỗi dữ liệu thời gian. 3.6. Độ đo khoảng cách Chebyshev 1 Dùng hàm Chebyshev (=) : 𝐷𝑖𝑠𝑡 (𝑥, 𝑧) = log 𝑝→ (∑𝑛𝑖=1|𝑥𝑖 − 𝑧𝑖 |𝑝 )𝑝 = 𝑚𝑎𝑥𝑖 |𝑥𝑖 − 𝑧𝑖 | 3.7. Độ đo khoảng cách xoắn thời gian động DTW: Dynamic Time Warping Khi hai đường biểu diễn là hai mẫu dữ liệu thời gian cần so sánh không giống nhau hoàn toàn nhưng hình dạng biển đổi giống nhau thì việc sử dụng các khoảng cách so sánh từng cặp điểm 1-1 để tìm ra độ tương tự giữa hai mẫu thì không phù hợp. Theo độ đo Euclidean thì ta có thể thấy 1 điểm trên chuỗi chời gian này sẽ ánh xạ với một điểm trên chuỗi thời gian bên kia hay các chuỗi cần tính khoảng cách phải có cùng độ dài. Để 356
khắc phục nhược điểm đó, thì một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không thẳng hàng. Phương pháp này gọi là xoắn thời gian động (Dynamic Time Warping – DTW) được đề xuất bởi Bernt và Clifford năm 1994, như Hình 17 [1]. Hình 17. Hình minh họa DTW: Dynamic Time Warping: độ đo khoảng cách "xoắn thời gian động" và độ đo Euclidean Cách tính: Xây dựng ma trận: Dm x n với m = |X| và n= |Y|. Khi đó, Dij = d(xi , yj ). Sau khi xây dựng ma trận D , ta tìm đường đi từ ô (0,0) đến ô (m,n) thỏa mãn những ràng buộc sau: - Không được đi qua trái hay đi xuống - Đường đi phải liên tục - Ô (i,j) thuộc đường đi phải thỏa |i - j|
Khoảng Euclide bậc 2 = Manhattan giữa x và z là 2 2 d(x, z) = √(𝑥𝐴𝑔𝑒 − 𝑧𝐴𝑔𝑒 ) + (𝑥𝐼𝑛𝑐𝑜𝑚𝑒 − 𝑧𝐼𝑛𝑐𝑜𝑚𝑒 )2 + (𝑥𝐻𝑒𝑖𝑔ℎ − 𝑧𝐻𝑒𝑖𝑔ℎ ) Trường hợp này Dom(Income) rất lớn so với 2 thuộc tính còn lại, nên quyết định hoàn toàn cho giá trị d Vì vậy, cần chuẩn hóa Dom của các thuộc tính đưa về cùng khoảng giá trị . Thường dùng BIN (0,1) . Với mỗi thuộc tính thứ i ta xác định giá trị mới xi = xi / max_value(fi) . Nhằm đảm bảo các thuộc tính có vai trò “tương đồng” nhau trong việc xác định giá trị d . Ngoài ra cần có trọng số w1 tương ứng từng thuộc tính xi 𝑛 𝑑(𝑥, 𝑧) = √∑ 𝑤𝑖 (𝑥𝑖 − 𝑧𝑖 )2 𝑖=1 Trọng số wi thường do các chuyên gia trong linh vực xác định và được tối ưu dần trong quá trình “học” 4.2. Áp dụng tính độ đo d vào k-NNC - Xét tập NB(z): gồm “mẫu” gần nhất với với “mẫu” mới z cần phân lớp - Nhiệm vụ: xác định các “mẫu” NN này quyết định thế nào đến “đoán” lớp cho z - Mức độ ảnh hưởng của các “mẫu” NN này tùy thuộc vào độ đo d(xj, z) - Gọi v là hàm xác định trong số theo khoảng cách Rõ ràng : v(x, z) tỷ lệ nghịch với d(x, z) + Với bài toán phân lớp: c(x, z) = arg 𝑚𝑎𝑥𝑐𝑗𝐶 ∑𝑥𝑁𝐵(𝑧) 𝑣(𝑥, 𝑧)𝐼𝑑𝑒𝑛𝑡𝑖𝑐𝑎𝑙(𝑐𝑗 , 𝑐(𝑥)) Với 𝐼𝑑𝑒𝑛𝑡𝑖𝑐𝑎𝑙 (𝑐𝑗 , 𝑐(𝑥)) = 1 nếu giống nhau, 0 nếu khác nhau + Với bài toán hồi quy | dự đoán: ∑𝑥𝑁𝐵(𝑧) 𝑣(𝑥,𝑧).𝑓(𝑥) 𝑓(𝑧) = ∑𝑥𝑁𝐵(𝑧) 𝑣(𝑥,𝑧) Với 𝐼𝑑𝑒𝑛𝑡𝑖𝑐𝑎𝑙 (𝑐𝑗 , 𝑐(𝑥)) = 1 nếu giống nhau, 0 nếu khác nha - Lựa chọn hàm xác định trọng số theo khoảng cách trong số tùy từng bài toán (với  là độ lệnh) 𝑑(𝑥,𝑧)2 1 1 − 𝑣(𝑥, 𝑧) = OR 𝑣(𝑥, 𝑧) = OR 𝑣(𝑥, 𝑧) = 𝑒 2 +𝑑(𝑥,𝑧) +𝑑(𝑥,𝑧)2 358
5. CÀI ĐẶT CÁCH TÍNH ĐỘ ĐO KHOẢNG CÁCH TRÊN CHUỖI DỮ LIỆU THỜI GIAN 5.1. Minh họa cài đặt trên Python 5.1.1. Bộ dữ liệu thực nghiệm + Bộ cơ sở dữ liệu Iris (Iris flower dataset): https://en.wikipedia.org/wiki/Iris_flower_data_set + Là bộ Bộ dữ liệu thông tin của ba loại hoa Iris (một loài hoa lan) khác nhau [số lớp c = 3]: . Iris setosa . Iris virginica và . Iris versicolor. Ví dụ về hình ảnh của ba loại hoa: Ví dụ về Iris flower dataset (Nguồn: Wikipedia) -> Mỗi loại có 50 bông hoa được đo với dữ liệu là 4 thông tin: . Chiều dài, chiều rộng đài hoa (sepal), . Chiều dài, chiều rộng cánh hoa (petal). Tức là, mỗi “mẫu” dữ liệu trong tập này là một vector 4 chiều 5.1.2. Cài đặt ứng dụng tính độ đo khoảng cách trên chuỗi dữ liệu thời gian 5.1.2.1. Mô tả chung về hệ thống + Tách Bộ dữ liệu Iris gồm 150 “mẫu” [|D| =150] dữ liệu ta chia thành 2 phần: Training Set và Test Set. + Nhiệm vụ bài toán kNN: dựa vào Training Set để dự đoán mỗi “mẫu” trong Test Set tương ứng với loại hoa nào? + Kết quả dự đoán sẽ được đối chiếu với loại hoa thật của mỗi “mẫu” trong test set để đánh giá hiệu quả của KNN. 5.1.2.2. Cài đặt mã lệnh + Khai báo thư viện (Iris flower dataset có sẵn trong thư viện scikit-learn: http://scikit- learn.org/) # -*- coding: utf-8 -*- """ Created on Mon Nov 23 03:58:20 2020 @author: VOXUAN """ 359
# NẠP CÁC TẬP THƯ VIỆN import numpy as np import matplotlib.pyplot as plt from sklearn import neighbors, datasets from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score + Nạp và hiện thị dữ liệu mẫu. # TẢI HIỂN THỊ SỐ LƯỢNG TẬP DỮ LIỆU IRIS CÓ SẴN TRONG SKLEARN iris = datasets.load_iris() iris_X = iris.data iris_y = iris.target print(u'Số lượng LỚP c được phân chia = %d' %len(np.unique(iris_y))) print(u'Số lượng MẪU dữ liệu = %d' %len(iris_y)) + Các lớp được gán nhãn là 0, 1, và 2. # GÁN NHÃN CHO 3 LỚP ẢNH TRONG TẬP IRIS X0 = iris_X[iris_y == 0,:] X1 = iris_X[iris_y == 1,:] X2 = iris_X[iris_y == 2,:] print(u'\nCác MẪU thuộc LOP 0 gồm:\n', X0[:5,:]) print(u'\nCác MẪU thuộc LOP 1 gồm:\n', X1[:5,:]) print(u'\nCác MẪU thuộc LOP 2 gồm:\n', X2[:5,:]) --------------KẾT QUẢ IN RA------ Number of classes: 3 Number of data points: 150 Samples from class 0: [[ 5.1 3.5 1.4 0.2] [ 4.9 3. 1.4 0.2] [ 4.7 3.2 1.3 0.2] [ 4.6 3.1 1.5 0.2] [ 5. 3.6 1.4 0.2]] Samples from class 1: [[ 7. 3.2 4.7 1.4] [ 6.4 3.2 4.5 1.5] [ 6.9 3.1 4.9 1.5] [ 5.5 2.3 4. 1.3] [ 6.5 2.8 4.6 1.5]] Samples from class 2: [[ 6.3 3.3 6. 2.5] [ 5.8 2.7 5.1 1.9] [ 7.1 3. 5.9 2.1] [ 6.3 2.9 5.6 1.8] [ 6.5 3. 5.8 2.2]] 5.1.2.3. Tách: Training Set Và Test Sets + Giả sử dùng 50 MẪU dữ liệu Test Set, 100 MẪU còn lại Training Set. + Scikit-learn có hàm cho phép lựa chọn ngẫu nhiên: # TÁCH TẬP TRAINING SET : 100 MẪU & TẬP TEST SET CÓ 50 MẪU X_train, X_test, y_train, y_test = train_test_split(iris_X, iris_y, test_size = 50) print(u'\nSố lượng MẪU thuộc tập Training Set: ', len(y_train)) print(u'\nSo61 lượng Mẫu thuộc tập Test Set: ', len(y_test)) 360
------------KẾT QUẢ--------------- Training size: 100 Test size : 50 5.1.2.4. Phân lớp theo KNN đối với các “mẫu” trong Test Sets + Xét trường hợp k = 1, tức là với mỗi MẪU Test data, chỉ xét 1 MẪU Training data gần nhất và lấy label của MẪU đó để dự đoán cho MẪU test. # DÙNG kNN PHÂN LỚP CHO CÁC MẪU TRONG TẬP TEST # tự định nghĩa trọng số def myweight(distance): sigma2 = 0.5 return np.exp(-distance**2/sigma2) cf = neighbors.KNeighborsClassifier(n_neighbors=10, p=2, weights=myweight) # p = 2 độ đo Euclide #cf = neighbors.KNeighborsClassifier(n_neighbors=10, p=2, weights='distance') # p = 2 độ đo Euclide cf.fit(X_train, y_train) y_result = cf.predict(X_test) #in Kết quả print(u'KẾT QUẢ PHÂN LỚP CÁC MẪU HOA IRIS TRONG BỘ TEST:\n') print(u'Theo phân lớp 1NN có kết quả là : \n') print(y_result) print(u'\nKết quả đúng (ground truth)của các MẪU trong bộ TEST là :\n') print(y_test) 5.1.2.5. Đánh giá độ chính xác (Evaluation Method) + Độ chính xác của giải thuật kNN Classifier = SUM(số MẪU trong test data đoán đúng) / SUM(số lượng MẪU trong tập Test data). + Trong Scikit-learn: dùng hàm accuracy_score để tính. # đánh giá tỷ lệ đúng (đoán bằng phân lớp kNN) print(u'Tỷ lệ đoán phân lớp 1NN đúng đối với tập Test Iris: %.2f %%' %(100*accuracy_score(y_test, y_result))) . Với 1NN dùng độ đo khoảng cách Euclide p=2: kết quả là 94% . Có thể thực nghiệm với k = 10 (major voting): kết quả 96% 5.1.2.6. Đánh trọng số các NN + Những MẪU “gần” hơn sẽ có trọng số cao hơn (càng thân cận thì càng tin tưởng). + Đơn giản là lấy nghịch đảo của khoảng cách. Chú ý: Trường hợp test data trùng với 1 MẪU trong training data, tức khoảng cách bằng 0, ta lấy luôn label của MẪU training data). + Trong Scikit-learn: tham số weights = 'distance'. (mặc định của weights = 'uniform': tất cả NN có trọng số bằng nhau) clf = neighbors.KNeighborsClassifier(n_neighbors = 10, p = 2, weights = 'distance') clf.fit(X_train, y_train) y_pred = clf.predict(X_test) print("Accuracy of 1NN: %.2f %%" %(100*accuracy_score(y_test, y_pred))) 361
==========KẾT QUẢ ================= Accuracy of 10NN (1/distance weights): 100.00 % . Với 10NN dùng độ đo khoảng cách Euclide p=2, dùng trọng số “khoảng cách” kết quả là 98% + Cũng có thể đánh trọng số các NN theo tùy chọn −‖𝑥 − 𝑥𝑖 ‖22 𝑤𝑖 = 𝑒𝑥𝑝 ( ) 2 Trong đó x là test data, xi là một MẪU trong NB(x), wi là trọng số của “MẪU” NN đó (ứng với MẪU dữ liệu đang test x), σ là một số dương. Hàm trên cũng thỏa mãn điều kiện: điểm càng gần x thì trọng số càng cao (max=1). def myweight(distances): sigma2 = .5 # we can change this number return np.exp(-distances**2/sigma2) clf = neighbors.KNeighborsClassifier(n_neighbors = 10, p = 2, weights = myweight) clf.fit(X_train, y_train) y_pred = clf.predict(X_test) print("Accuracy of 1NN: %.2f %%" %(100*accuracy_score(y_test, y_pred))) ============KẾT QUẢ============= Accuracy of 10NN (customized weights): 100.00 % 5.1.2.7. Full Codes # -*- coding: utf-8 -*- """ Created on Mon Nov 23 03:58:20 2020 @author: VOXUAN """ # NẠP CÁC TẬP THƯ VIỆN import numpy as np import matplotlib.pyplot as plt from sklearn import neighbors, datasets from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score # TẢI HIỂN THỊ SỐ LƯỢNG TẬP DỮ LIỆU IRIS CÓ SẴN TRONG SKLEARN iris = datasets.load_iris() iris_X = iris.data iris_y = iris.target print(u'Số lượng LỚP c được phân chia = %d' %len(np.unique(iris_y))) print(u'Số lượng MẪU dữ liệu = %d' %len(iris_y)) # GÁN NHÃN CHO 3 LỚP ẢNH TRONG TẬP IRIS X0 = iris_X[iris_y == 0,:] X1 = iris_X[iris_y == 1,:] X2 = iris_X[iris_y == 2,:] print(u'\nCác MẪU thuộc LOP 0 gồm:\n', X0[:5,:]) print(u'\nCác MẪU thuộc LOP 1 gồm:\n', X1[:5,:]) 362
print(u'\nCác MẪU thuộc LOP 2 gồm:\n', X2[:5,:]) # TÁCH TẬP TRAINING SET : 100 MẪU & TẬP TEST SET CÓ 50 MẪU X_train, X_test, y_train, y_test = train_test_split(iris_X, iris_y, test_size = 50) print(u'\nSố lượng MẪU thuộc tập Training Set: ', len(y_train)) print(u'\nSo61 lượng Mẫu thuộc tập Test Set: ', len(y_test)) # DÙNG kNN PHÂN LỚP CHO CÁC MẪU TRONG TẬP TEST # tự định nghĩa trọng số def myweight(distance): sigma2 = 0.5 return np.exp(-distance**2/sigma2) cf = neighbors.KNeighborsClassifier(n_neighbors=10, p=2, weights=myweight) # p = 2 độ đo Euclide #cf = neighbors.KNeighborsClassifier(n_neighbors=10, p=2, weights='distance') # p = 2 độ đo Euclide cf.fit(X_train, y_train) y_result = cf.predict(X_test) #in Kết quả print(u'KẾT QUẢ PHÂN LỚP CÁC MẪU HOA IRIS TRONG BỘ TEST:\n') print(u'Theo phân lớp 1NN có kết quả là : \n') print(y_result) print(u'\nKết quả đúng (ground truth)của các MẪU trong bộ TEST là :\n') print(y_test) # đánh giá tỷ lệ đúng (đoán bằng phân lớp kNN) print(u'Tỷ lệ đoán phân lớp 1NN đúng đối với tập Test Iris: %.2f %%' %(100*accuracy_score(y_test, y_result))) 4. KẾT LUẬN Với các bài toán phục vục việc phân tích và quản lý dự liệu thông minh thông thường phải xử lý trên chuỗi dữ liệu thời gian. Và vì vậy, việc xác định một độ đo khoảng cách phù hợp cho từng trường hợp số liệu cụ thể của bài toán theo một dự án (Project) xây dựng mô hình khai phá dữ liệu trong thực tiễn các cơ quan – doanh nghiệp sẽ quyết định đáng kế cho tính hiệu quả của bài toán dự án đó. Có nhiều phương pháp xác định độ đo khoảng cách khác biệt giữa các chuỗi con hoặc điểm dữ liệu trên chuỗi dữ liệu thời gian, như: khoảng cách Hamming, khoảng cách tựa (tương tự) Cosin, khoảng cách Minkowski, khoảng cách Manhattan, khoảng cách Euclidean, khoảng cách Chebyshev, khoảng cách xoắn thời gian động (DTW: Dynamic Time Warping). Mỗi phương pháp có ưu điểm riêng và nhược điểm của nó nên có khi phù hợp với bài toán project này nhưng không phù hợp với bài toán project khác và ngược lại. Việc tìm hiểu và nghiên cứu các độ đo khoảng cách trên dữ liệu chuỗi thời gian góp phần cải tiến tính hiệu quả các bài toán trong khoa học dữ liệu mở ra nhiều hướng ứng dụng trong thực tiễn tại các cơ quan – doanh nghiệp. 363
DANH MỤC MỘT SỐ TỪ VIẾT TẮT được dùng trong bài viết Tiếng Việt: 7. CMCN 4.0: Cách mạng công nghiệp lần thứ 4. Tiếng Anh: 8. DTW: Dynamic Time Warping: Độ đo khoảng cách xoắn thời gian động. 9. SQL: Structured Query Language: Ngôn ngữ vấn tin có cấu trúc. 10. TSD: Time Series Data: Chuỗi dữ liệu thời gian. TÀI LIỆU THAM KHẢO: [12]. Nguyễn Thành Sơn (2021), Đề tài nghiên cứu khoa học cấp trường trọng điểm: Dự báo trên chuỗi thời gian sử dụng phương pháp kết hợp mạng nơ-ron nhân tạo và so trùng mẫu dưới độ đo xoắn thời gian động, T2020-16TD, Trường Đại học Sư phạm Kỹ thuật Tp.HCM. [13]. Nguyễn Văn Thành (2021), luận văn thạc sỹ: Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách, 1981308, Trường Đại học Sư phạm Kỹ thuật Tp.HCM.. [14]. B. Liu, . L. Jianqiang and . C. Cheng, "Efficient Motif Discovery for LargeScale Time Series in Healthcare," IEEE Transactions on Industrial Informatics, vol. 11, no. 3, pp. 583 590, 2015. [15]. C. M. Yeh, Y. Zhu and H. D. Anh, "Matrix Profile I: All pairs similarity joins for Time Series," IEEICDM, 2016. [16]. Cheboli, “Anomaly Detection of Time Series”, Master Thesis, 2010 [17]. E. Keogh, E., Lin, J. and Fu, (2005), “A HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence”, In: Proc. of 5th IEEE Int. Conf. on Data Mining (ICDM), pp. 226-233. [18]. E. Keogh and S. Kasetty, "On the need for time series data mining benchmark: A surevey and empirical demonstration," in In the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 23 – 26, 2002. [19]. F. Chuah, M.C. Fu., “ECG anomaly detection via time series annalysis”, Lecturer notes in computer science, pp. 123-135. [20]. E. Keogh, C. A. Ratanamahatana, “Exact indexing of dynamic time warping”, Knowledge and Information Systems (2004), Knowledge and Information Systems (2004) [21]. Hansheng Ren và cộng sự, “Time-Series Anomaly Detection Service at Microsoft”, in KDD ’19, August 4–8, 2019, Anchorage, AK, USA, 2019 364
Websites [22]. https://cmry.github.io/notes/euclidean-v-cosine [23]. Keogh. Eamonn, http://www.cs.ucr.edu/~eamonn/discords/. 01.Jul.2020 [24]. UCR, "The UCR Matrix Profile Page," [Online]. Available: https://www.cs.ucr.edu/~eamonn/MatrixProfile.html. 01.Jul.2020 [25]. Tập dữ liệu thực tế 01.Mar.2021 https://github.com/numenta/NAB/tree/master/data 365