Chương 1 TỔNG QUAN VỀ VẤN Ề NGHIÊN CỨU Chương này của luận án giới thiệu các kiến thức cơ bản về bài toán phân lớp nhị phân có tính chất dữ liệu không cân bằng và các vấn ề liên quan khi ứng dụng vào bài toán dự oán ồng tác giả ược mô hình hóa theo dạng phân lớp. Một số phương pháp tiếp cận giải quyết bài toán và thuật toán phân lớp nhị phân nổi bật cũng ược phân tích ể ưa ra các ịnh hướng nghiên cứu cải tiến các thuật toán. Bài toán phân lớp với dữ liệu không cân bằng Dữ liệu không cân bằng là khái niệm ề cập ến các bộ dữ liệu có ặc iểm phân bố số lượng mẫu trong mỗi lớp có sự chênh lệch cao. Bài toán phân lớp trên dữ liệu không cân bằng là một vấn ề thách thức trong học máy.
ể giải quyết bài toán phân lớp trên dữ liệu không cân bằng nói chung, các nghiên cứu tập trung vào hai hướng giải quyết chính ó là: sửa ổi tập dữ liệu ể giảm mức ộ không cân bằng mẫu giữa các lớp và cải tiến thuật toán thông qua việc iều chßnh các tham số. Các phương pháp tiếp cận mức dữ liệu sử dụng các kỹ thuật can thiệp vào bộ dữ liệu gốc ể tạo ra bộ dữ liệu huấn luyện có tÿ lệ phân bố mẫu cân bằng hơn, từ ó làm cơ sở cho các thuật toán phân lớp truyền thống hoạt ộng hiệu quả hơn. Có thể thay ổi sự phân bố số lượng mẫu trong bộ dữ liệu (ReSampling) bằng cách sinh thêm các phần tử cho lớp thiểu số (Over Sampling) như Ran- dom Oversampling, Synthetic Minority Oversampling Technique (SMOTE) [25], Border-line-SMOTE [26], Adaptive Synthetic Sampling (ADA-SYN)[27] over- sampling dựa trên cụm (Cluster Based Sampling-CBO) [28], SMOTEBoost [29], OSD [30]. hay giảm bớt các phần tử thuộc lớp a số (Under Sampling) như EasyEnsemble [31], BalanceCascade [32], KNN-NearMiss [33],.
ể bộ dữ liệu trở nên cân bằng hơn, từ ó sử dụng các thuật toán học máy mạnh ể phân lớp. Một số kỹ thuật làm sạch dữ liệu (data cleaning techniques) như Tomek links ược dùng ể loại bỏ sự trùng lặp hoặc chồng lẫn của các mẫu trong tập dữ liệu sau khi thực hiện các thuật toán tạo các mẫu tổng hợp (Over Sampling) [34][35]. 11 Các phương pháp tiếp cận ở mức thuật toán hướng tới việc iều chßnh các thuật toán phân lớp truyền thống ể vẫn ạt ược hiệu quả cao trên các tập dữ liệu không cân bằng. Các phương pháp phổ biến như học dựa trên nhạy cảm chi phí [36][37][38], iều chßnh xác suất ước lượng [30][39], sử dụng các hằng số phạt khác nhau cho các nhãn lớp khác nhau [40][41].
Một số thuật toán ược nghiên cứu cải tiến iển hình như: Boosting [20], AdaC1, AdaC2, AdaC3 [42][43][44][45][46], sử dụng Cây quyết ịnh (Cost-Sensitive Decision Trees) [38][47], sử dụng các hàm kernel máy vectơ hỗ trợ SVM, sử dụng kỹ thuật học sâu,. Một số nghiên cứu khác sử dụng kết hợp cải tiến thuật toán và sửa ổi mẫu như [19][48][49][50][51]. Việc sử dụng các phương pháp tiếp cận ở mức dữ liệu trong một số trường hợp nào ó có thể dẫn ến mất i những thông tin quan trọng của bộ dữ liệu hoặc ưa nhiễu vào tập dữ liệu. Do ó, luận án tiếp cận giải quyết bài toán có dữ liệu không cân bằng ở mức thuật toán, tức là nghiên cứu cải tiến các thuật toán truyền thống ể nó ạt ược hiệu quả phân lớp tốt trên dữ liệu không cân bằng.
Trong ó, luận án lựa chọn các giải thuật mạnh như học kết hợp boosting hay SVM có trọng số ể nghiên cứu cải tiến, giải quyết vấn ề phân lớp trên dữ liệu không cân bằng. Phân tích một số phương pháp tiếp cận ở mức thuật toán ể giải quyết không cân bằng dữ liệu, các phương pháp dựa trên cải tiến dựa trên AdaBoost [42], cải tiến dựa trên SVMs [21][52] và các phương pháp học sâu dựa trên CNN [53] thu hút rất nhiều sự quan tâm bởi tính tùy biến mở rộng của các thuật toán cho các bài toán có dữ liệu có tính chất khác nhau là rất hiệu quả. Thuật toán học kết hợp AdaBoost do Freund [20] ề xuất dựa trên quan iểm là: khi sử dụng một bộ phân lớp ơn lẻ có thể sẽ không xem xét một cách ầy ủ các ặc iểm của tập dữ liệu, do ó việc kết hợp sử dụng nhiều bộ phân lớp thành viên khác nhau ể tạo thành một bộ phân lớp tổng hợp có thể sẽ xem xét kỹ hơn các ặc tính của dữ liệu và em lại hiệu quả phân lớp tốt hơn. ể sử dụng kết hợp các bộ phân lớp con, thường có hai cách kết hợp là tuần tự (boosting) hoặc song song (bagging).
AdaBoost là kiểu kết hợp tuần tự và sửa lỗi phân lớp thích nghi qua mỗi lần lặp. Về phương pháp học kết hợp dạng song song, nổi bật nhất là thuật toán rừng ngẫu nhiên (Random forest). Thuật toán này chia nhỏ bộ dữ liệu gốc thành các tập dữ liệu con bằng kỹ thuật bootstrap và sử dụng các bộ phân lớp thành viên cho các tập dữ liệu con, sau ó kết quả phân lớp chung cuối cùng sẽ ược tổng hợp từ các bộ phân lớp thành viên. Tuy 12 nhiên trong trường hợp dữ liệu không cân bằng, ặc biệt là dữ liệu không cân bằng mức cao, số lượng mẫu nhãn dương +1 là rất ít.
Vì vậy việc lấy mẫu ngẫu nhiên ể tạo ra các bộ dữ liệu con khó ảm bảo ầy ủ tính chất của dữ liệu. Do ó, thuật toán học kết hợp AdaBoost ược luận án lựa chọn ể thực hiện nghiên cứu cải tiến. SVM [21] là một thuật toán phân lớp mạnh trong học máy. SVM ã ược nghiên cứu rộng rãi và ược chứng minh là một phương pháp phân lớp mạnh trong các kết quả thực nghiệm.
Giải thuật này ặc biệt hiệu quả ối với các dữ liệu phân biệt tuyến tính. Ngoài ra, thuật toán cũng khá mềm dẻo và có khả năng cải tiến mở rộng ể ạt hiệu quả cao trên những bộ dữ liệu có ặc tính khác nhau. ối với bài toán phân lớp dữ liệu không cân bằng, ã có rất nhiều các nghiên cứu cải tiến SVM như là Weighted-SVM [22], Kernel-SVM, ặc biệt là Fuzzy SVM [23], Fuzzy SVM-CIL [24]. Một iều cần lưu ý nữa là hai thuật toán AdaBoost và SVM ều sử dụng hàm xét dấu (−/+) ể ưa ra kết quả phân lớp nên nó trở thành lựa chọn hợp lý và phù hợp ể cải tiến cho bài toán phân lớp nhị phân có dữ liệu không cân bằng mà luận án hướng tới.
Bên cạnh vấn ề dữ liệu không cân bằng về số lượng mẫu trong các lớp, một vấn ề chung ể nâng cao chất lượng mô hình phân lớp là cần xử lý tốt việc phân lớp chính xác trong các vùng không gian nhạy cảm như: mẫu dữ liệu là nhiễu hoặc mẫu dữ liệu phân bố trong không gian ranh giới phân lớp của hai lớp. ể xác ịnh các vùng không gian chứa các mẫu nhạy cảm này, chúng ta cần các phương pháp o lường khoảng cách hoặc xem xét phân bố các mẫu. Do vậy chúng ta cần lưu ý ến việc sử dụng các thuật toán như K-nearest neighbors (KNN) và Tomek link ể ịnh vị các mẫu trong không gian phân bố. Mặt khác SVM là thuật toán phân lớp dạng tuyến tính dựa trên lề và có các tham số iều chßnh ể mở rộng hoặc co hẹp không gian biên lề phân lớp.
Khi sử dụng SVM làm bộ phân lớp cơ sở, chúng ta hoàn toàn có thể xác ịnh ược vùng không gian nhạy cảm là biên lề phân lớp. Ngoài ra, với dữ liệu không ầy ủ, không chắc chắn, phương pháp xử lý mờ dựa trên lý thuyết tập mờ của Zadeh [54] ưa ra vào năm 1965 tỏ ra hiệu quả. Nhiều nghiên cứu ã ề xuất các phương pháp xử lý mờ ể giải quyết vấn ề này. Vì vậy việc nghiên cứu vận dụng và cải tiến các thuật toán như AdaBoost, SVM có trọng số, KNN, Tomek link [55] và các gải thuật phân lớp mờ Fuzzy SVM, Fuzzy SVM-CIL cho dữ liệu không cân bằng mang ến nhiều triển vọng.
13 Dựa vào việc phân tích trên, trong phần tiếp theo, luận án sẽ trình bày tóm lược các thuật toán liên quan làm cơ sở cho các nghiên cứu cải tiến nhằm hướng ến giải quyết bài toán phân lớp nhị phân trên dữ liệu không cân bằng nói chung và ứng dụng trong bài toán dự oán cộng tác ồng tác giả nói riêng. Một số thuật toán liên quan 1. Thuật toán SVM Thuật toán 1.1: Thuật toán SVM Input: Tập dữ liệu X = {(x1 , y1 ),. , (xN , yN )} với yi = {−1, +1}; C : tham số iều chßnh kiểm soát sự ồng nhất của siêu phẳng phân lớp.
Output: Hệ số w: véc-tơ trọng số của các thuộc tính, b: thuộc tính ộ lệch ể xác ịnh siêu phẳng phân lớp. 1 Khởi tạo w và b 2 for Lặp ến khi hội tụ do 3 for Duyệt từng mẫu huấn luyện xi do 4 Tính di = yi (w · xi + b) 5 Tính hàm chi phí cho mẫu xi : costi = max(0, 1 − di ) Tính hàm mục tiêu: J(w, b) = 12 ||w||22 + C N i=1 costi ; P 6 7 Cập nhật w và b bằng phương pháp tối ưu hóa: minJ(w, b) 8 return h(x) = sign(w · x + b). SVM ã ược nghiên cứu, thử nghiệm và chứng minh là một phương pháp phân lớp mạnh, ặc biệt hiệu quả ối với các dữ liệu phân biệt tuyến tính. Ngoài ra, thuật toán cũng khá mềm dẻo và có khả năng cải tiến mở rộng ể ạt hiệu quả cao trên những bộ dữ liệu có ặc tính khác nhau.
ối với vấn ề phân lớp nhị phân, với tập dữ liệu D = {(xi , yi )|i = 1, 2, · · · , N }, trong ó xi ∈ Rn ại diện cho một iểm dữ liệu n chiều và yi ∈ {−1, +1} là nhãn lớp của xi. Mục tiêu của thuật toán SVM là tìm ra một siêu phẳng phân tách các iểm dữ liệu này thành hai lớp trong không gian ặc trưng Rn. Hàm mục tiêu cần tối ưu cho siêu phẳng phân tách trong không gian ặc trưng Rn ược biểu thị bằng: ïω, xð + b = 0, (1.1) trong ó ω là ma trận tham số, b là hệ số. Các bước huấn luyện của SVM ược trình bày cụ thể ở Thuật toán 1.
Thuật toán Weighted-SVM ối với vấn ề học máy trên dữ liệu không cân bằng hai nhãn lớp, ã có nhiều cải tiến của thuật toán SVM ược ề xuất như [24][56][57][58][59]. Một cải tiến nổi bật, iển hình trong số ó là thuật toán Weighted-SVM (WSVM) [22].