- PHÂN LỚP DỮ LIỆU KHÔNG CÂN BẰNG VỚI ROUGHLY BALANCED BAGGING. - Trong bài báo này, chúng tôi trình bày một cải tiến của giải thuật Roughly Balanced Bagging (Hido &. - Kashima, 2008) cho việc phân lớp các tập dữ liệu không cân bằng.. - Chúng tôi đề xuất sử dụng các giải thuật tập hợp mô hình bao gồm Boosting (Freund &. - Chúng tôi cũng đề xuất điều chỉnh cách lấy mẫu giảm phần tử lớp đa số theo hàm phân phối nhị thức âm ở mỗi lần. - Kết quả thực nghiệm trên các tập dữ liệu không cân bằng được lấy từ nguồn UCI (Asuncion &. - Newman, 2007) cho thấy rằng phương pháp mà chúng tôi đề xuất cho hiệu quả phân loại chính xác hơn khi so sánh với giải Roughly Balanced Bagging gốc.. - Từ khoá: Dữ liệu không cân bằng, Roughly Balanced Bagging, Bagging, Boosting, AdaBoost, Rừng ngẫu nhiên, Cây quyết định, Phân phối nhị thức âm. - Phân lớp dữ liệu không cân bằng là một trong 10 vấn đề khó đang được cộng đồng máy học và khai mỏ dữ liệu quan tâm (Yang &. - Sự không cân bằng lớp nó ảnh hưởng rất lớn đến hiệu quả của các mô hình phân loại. - Với các tập dữ liệu của các bài toán phân lớp như vậy sẽ làm cho các mô hình học phân lớp gặp rất nhiều khó khăn trong dự báo cho dữ liệu lớp thiểu số. - Hầu hết giải thuật học như cây quyết định C4.5 (Quinlan, 1993), CART (Breiman et al., 1984), SVM (Vapnik, 1995) đều được thiết kế để cho độ chính xác tổng thể, không quan tâm đến bất kỳ lớp nào. - Chính vì lý do này, các giải thuật học phân lớp cho tập dữ liệu không cân bằng gặp phải vấn đề dự báo dễ làm mất lớp thiểu số mặc dù cho độ chính xác tổng thể rất cao. - Ví dụ như tập dữ liệu cho dự báo bệnh A có 40000 phần tử, trong đó lớp bệnh A là lớp thiểu số (người ta quan tâm hay lớp dương) chỉ có 10 phần tử và lớp còn lại (không bệnh, lớp âm) có 39990 phần tử. - Một giải thuật học dự báo sai hoàn toàn bệnh A (lúc nào cũng dự báo là không bị bệnh A) thì vẫn cho độ chính xác tổng thể là 99,975%. - Đây là một trong những sai lầm nghiêm trọng của giải thuật học phân lớp. - Chính vì lý do này, cộng đồng máy học cũng đã tập trung để giải quyết vấn đề phân lớp dữ liệu không cân bằng, chẳng hạn như các cuộc hội thảo khoa học (Chawla et al . - Nhiều giải pháp cũng đã được đề xuất để giải quyết vấn đề trên trong giải thuật học cây quyết định nhằm cải thiện dự báo lớp thiểu số nhưng không làm mất nhiều dự báo lớp đa số. - Kashima, 2008) đề xuất lấy mẫu giảm cho lớp đa số. - Chiến lược can thiệp trực tiếp giải thuật học cây quyết định, (Lenca et al., 2008) đề xuất thay đổi hàm phân hoạch dữ liệu nhằm cải thiện dự báo lớp thiểu số nhưng không làm mất nhiều dự báo lớp đa số. - Provost, 2003) đề xuất gán giá phải trả cho dự báo sai của các lớp khác nhau (giá của lớp thiểu số lớn hơn giá của lớp đa số). - Ngoài ra (Domingos, 1999) đề xuất điều chỉnh ước lượng xác suất tại nút lá của cây nhằm cải tiến dự báo lớp thiểu số.. - Chúng tôi đề xuất cải tiến giải thuật Roughly Balanced Bagging – RB Bagging (Hido &. - Kashima, 2008) giúp cải thiện dự báo lớp thiểu số nhưng không làm mất quá nhiều dự báo lớp đa số. - Chúng tôi đề xuất thay thế mô hình học cơ sở là cây quyết định C4.5 (Quinlan, 1993) dùng trong RB Bagging bằng giải thuật tập hợp mô hình mạnh hơn như rừng ngẫu nhiên (Breiman, 2001) và AdaBoost (Freund &. - Ngoài ra, chúng tôi cũng điều chỉnh cách lấy mẫu giảm phần tử lớp đa số theo hàm phân phối nhị thức âm ở mỗi lần của RB Bagging để không làm mất quá nhiều dự báo lớp đa số. - Kết quả thực nghiệm trên 10 tập dữ liệu không cân bằng từ kho dữ liệu UCI (Asuncion &. - Newman, 2007) cho thấy rằng phương pháp mà chúng tôi đề xuất (RB Bagging cải tiến) cho hiệu quả cao hơn khi so sánh với giải RB Bagging gốc, dựa trên các tiêu chí về precision, recall, F1- measure và accuracy (van Rijsbergen, 1979).. - Phần tiếp theo của bài báo được tổ chức như sau: Trong phần 2, chúng tôi sẽ trình bày ý tưởng chính của giải thuật RB Bagging và giải thuật cải tiến cho phân lớp dữ liệu không cân bằng. - 2 GIẢI THUẬT RB BAGGING CẢI TIẾN. - Giải thuật RB Bagging của (Hido &. - Kashima, 2008) cho vấn đề phân lớp dữ liệu không cân bằng với chiến lược thay đổi phân bố của tập dữ liệu. - RB Bagging tập trung cải thiện hiệu quả dự báo cho lớp thiểu số, bên cạnh đó cố gắng đảm bảo sử dụng hầu hết thông tin cho lớp đa số. - Để đạt được mục tiêu này, RB Bagging cố gắng cân bằng phân bố dữ liệu của lớp dương (lớp thiểu số mà người ta quan tâm) và lớp âm (lớp còn lại). - Giải thuật RB Bagging như trình bày trong giải thuật 1 có thể được trình bày ngắn gọn như sau.. - Giả sử tập dữ liệu không cân bằng D bao gồm N pos phần tử lớp dương trong D pos và N neg phần tử lớp âm trong D neg . - RB Bagging thực hiện xây dựng tập hợp K cây quyết định C4.5 (Quinlan, 1993). - Ở mỗi bước lặp k, RB Bagging thực hiện chiến lược lấy mẫu giảm trên lớp đa số (lớp âm) và toàn bộ lớp thiểu số (lớp dương) để xây dựng mô hình cơ sở cây quyết định. - RB Bagging sử dụng số lượng phần tử lớp dương (lớp thiểu số) bằng với số phần tử lớp dương N pos trong tập dữ liệu D pos . - RB Bagging sử dụng lấy mẫu giảm số phần tử lớp đa số (lớp âm) với số lượng được xác định theo phân phối nhị thức âm trong đó các tham số là số lượng phần tử bằng với N pos của lớp thiểu số (dương) và xác suất thành công q=0,5. - Tập mẫu vừa tạo được dùng để xây dựng mô hình cây quyết định ở bước lặp k. - Trong dự báo một phần tử mới đến dựa trên chiến lược bình chọn số đông từ kết quả dự báo của K mô hình cơ sở cây quyết định.. - Trong xử lý vấn đề không cân bằng lớp, chiến lược lấy mẫu của RB Bagging có thể hiểu như một việc lấy mẫu lặp lại từng mẫu một mà việc chọn lớp được lấy mẫu dựa trên xác suất tiên nghiệm cân bằng p(dương. - Kashima, 2008) cho thấy rằng RB Bagging sử dụng chiến lược lấy mẫu dựa trên phân phối nhị thức âm đảm bảo chất lượng của giải thuật Bagging gốc của (Breiman, 1996) nhưng sử dụng được hầu hết thông tin của lớp thiểu số. - Điều này dẫn đến việc RB Bagging cải tiến được dự báo lớp thiểu số (dương) nhưng lại làm mất dự báo lớp đa số (âm). - Để khắc phục khuyết điểm của RB Bagging gốc, chúng tôi đề xuất giải thuật cải tiến vẫn giữ được hiệu quả dự báo lớp thiểu số như RB Bagging gốc nhưng không làm mất nhiều dực báo lớp đa số.. - Giải thuật 1: Giải thuật RB Bagging. - Từ giải thuật RB Bagging gốc, chúng tôi điều chỉnh lại cách lấy mẫu giảm của lớp âm và thay thế mô hình học cơ sở cây quyết định bằng phương pháp tập hợp mô hình. - Do RB Bagging gốc lấy mẫu giảm quá nhiều lớp đa số ở mỗi lần lặp (chỉ sử dụng số lượng tương đương với lớp thiểu số) gây ra dự báo lệch quá nhiều sang lớp thiểu số và giảm đáng kể dự báo lớp đa số. - Trong cải tiến, chúng tôi đề nghị sử dụng lấy mẫu giảm lớp đa số cũng dựa trên phân phối nhị thức âm nhưng với tham số neg pos N pos. - n N thay vì là n = N pos như trong RB Bagging gốc. - Ngoài ra, để nâng cao hiệu quả của dự báo, chúng tôi cũng đề xuất sử dụng phương pháp tập hợp mô hình như rừng ngẫu nhiên (Breiman, 2001) và AdaBoost (Freund &. - Schapire, 1995) làm mô hình học cơ sở mạnh hơn mô hình đơn cây quyết định ở mỗi bước lặp của RB Bagging.. - Giải thuật rừng ngẫu nhiên cho độ chính xác cao khi so sánh với các thuật toán học có giám sát hiện nay, chịu đựng nhiễu tốt.. - D tập dữ liệu không cân bằng. - L giải thuật cơ sở (cây quyết định C4.5) K số bước lặp. - Xây dựng mô hình phân lớp RB Bagging:. - Chia tập dữ liệu D thành tập dữ liệu lớp âm D neg và lớp dương D pos Cho k 1 tới K. - Xây dựng mô hình f k (x) bằng giải thuật cơ sở L trên tập dữ liệu bao gồm D k neg và D k p os. - Dự báo phần tử x i mới đến:. - Giải thuật 2: Giải thuật rừng ngẫu nhiên. - Giải thuật AdaBoost (giải thuật 3) xây dựng tuần tự T mô hình, lặp lại quá trình học của một mô hình phân lớp yếu (cây quyết định) T lần. - Khởi tạo, trọng số của các phần tử bằng nhau. - Đặt trọng số cho các mô hình dựa trên lỗi của các mô hình cơ sở. - Kết thúc giải thuật sẽ dùng chiến lược bình chọn số đông với trọng số để phân lớp phần tử dữ liệu.. - Giải thuật 3: Giải thuật AdaBoost. - Việc điều chỉnh cách lấy mẫu giảm của lớp đa số và thay thế mô hình cơ sở bằng phương pháp tập hợp mô hình vì thế giúp cho giải thuật RB Bagging cải tiến mà chúng tôi đề xuất, xử lý tốt hơn khi phân lớp tập dữ liệu không cân bằng vì giữ được hiệu quả dự báo lớp thiểu số như giải thuật RB Bagging gốc nhưng vẫn đảm bảo không làm mất nhiều thông tin của lớp đa số. - Tuy nhiên, thời gian thực thi của nó lâu hơn so với giải thuật RB Bagging gốc.. - Để đánh giá hiệu quả của giải thuật RB Bagging cải tiến, chúng tôi tiến hành cài đặt tất cả chương trình bằng ngôn ngữ R (Ihaka &. - Thực nghiệm trên 10 tập dữ liệu không cân bằng được lấy từ nguồn UCI (Asuncion &. - Nếu tập dữ liệu có sẵn tập học và tập kiểm tra, chúng tôi dùng tập học để xây dựng mô hình và sau đó phân lớp tập kiểm tra bằng mô hình thu được kết quả phân lớp. - Nếu tập dữ liệu chưa có sẵn tập học và tập kiểm tra thì chúng tôi sử dụng nghi thức Hold-out để đánh giá hiệu quả. - Nghi thức Hold-out thực hiện lấy ngẫu nhiên 2/3 số phần tử từ tập dữ liệu để làm tập học và 1/3 còn lại của tập dữ liệu dùng cho kiểm tra, quá trình này có thể lặp lại k lần (k=3 trong thực nghiệm của chúng tôi) và sau đó tính giá trị trung bình trên k kết quả sinh ra làm kết quả cuối cùng.. - Để thấy rõ hiệu quả của giải thuật RB Bagging cải tiến mà chúng tôi đề xuất so với giải thuật RB Bagging gốc, chúng tôi tiến hành so sánh kết quả dựa trên các tiêu chí như precision, recall, accuracy và F1–measure (van Rijsbergen, 1979). - Bảng 1: Các tập dữ liệu không cân bằng.. - ID Tập dữ liệu Số phần tử Số thuộc tính Nghi thức Tỷ lệ lớp nhỏ. - Khi thực thi các giải thuật theo đúng nghi thức kiểm tra được mô tả như trên, chúng tôi thu được kết quả trong bảng 2. - Trong đó, cột DT0 là kết quả thu được khi chạy giải thuật RB Bagging gốc với việc dùng cây quyết định C4.5 như là mô. - tương ứng với ba mô hình học cơ sở dùng cây quyết định C4.5, rừng ngẫu nhiên và AdaBoost.M1. - Khi thực thi, các giải thuật RB Bagging gốc và cải tiến đều xây dựng 200 mô hình học cơ sở. - Bảng 2: Kết quả phân lớp của RB Bagging gốc và RB Bagging cải tiến. - Từ bảng kết quả phân lớp thu được khi xử lý 10 tập dữ liệu cho thấy giải thuật RB Bagging cải tiến mà chúng tôi đề xuất cho kết quả tốt hơn so với RB Bagging gốc của (Hido &. - Xét tiêu chí precision, thì RB Bagging cải tiến với mô hình cơ sở là rừng ngẫu nhiên và AdaBoost.M1 thắng tất cả 10 tập. - Dựa trên tiêu chí recall, thì RB Bagging cải tiến vẫn cho kết quả so sánh được với RB Bagging gốc (thắng 5 trên 10 tập). - Với tiêu chí F1 và accuracy, RB Bagging cải tiến thắng tất cả 10 tập. - Điều này lý giải cho việc thay đổi cách lấy mẫu và mô hình cơ sở trong RB Bagging cải tiến vẫn có được dự báo lớp thiểu số tốt nhưng không làm mất nhiều dự báo lớp đa số so với RB Bagging gốc.. - Hình 1: Đồ thị so sánh tiêu chí F1 của các giải thuật trên 10 tập dữ liệu. - Hình 2: Đồ thị so sánh tiêu chí Accuracy của các giải thuật trên 10 tập dữ liệu. - Quan sát các đồ thị biểu diễn các tiêu chí F1 (hình 1) và accuracy (hình 2) thu được của các giải thuật RB Bagging gốc và RB Bagging cải tiến khi phân lớp 10 tập dữ liệu không cân bằng trong thực nghiệm. - Chúng ta nhận thấy rằng đường DT0 của RB Bagging gốc luôn nằm cận dưới của các đường DT, RF, Ada của RB Bagging cải tiến. - Điều này chứng minh rằng giải thuật RB Bagging gốc cho hiệu quả phân loại bị lệch mạnh về lớp thiểu số và làm giảm hiệu quả dự báo của lớp đa số trong khi RB Bagging cải tiến thì vẫn cho kết quả dự báo tốt cho lớp thiểu số nhưng không làm mất hiệu quả dự báo lớp đa số.. - Qua kết quả đạt được, chúng tôi tin rằng giải thuật RB Bagging cải tiến mà chúng tôi đề xuất có thể xử lý tốt cho vấn đề phân lớp dữ liệu không cân bằng.. - Chúng tôi vừa trình bày giải thuật RB Bagging cải tiến cho phân lớp tập dữ liệu không cân bằng. - Ý tưởng mà chúng tôi đề xuất tận dụng được các ưu điểm của RB Bagging gốc (Hido &. - Kashima, 2008) cải tiến dự báo lớp thiểu số và khắc phục được yếu điểm làm giảm dự báo lớp đa số. - RB Bagging cải tiến tập trung cải thiện hiệu quả dự báo cho lớp thiểu số, bên cạnh đó cố gắng đảm bảo sử dụng hầu hết thông tin cho lớp đa số. - Để đạt được mục tiêu này, chúng tôi đề xuất hai cải tiến:. - điều chỉnh cách lấy mẫu giảm phần tử lớp đa số theo hàm phân phối nhị thức âm ở mỗi lần của RB Bagging để không làm mất quá nhiều dự báo lớp đa số, thay thế mô hình học cơ sở là cây quyết định C4.5 (Quinlan, 1993) dùng trong RB Bagging bằng giải thuật tập hợp mô hình mạnh hơn như rừng ngẫu nhiên (Breiman, 2001) và AdaBoost (Freund &. - Newman, 2007) cho thấy rằng RB Bagging cải tiến cho hiệu quả cao hơn khi so sánh với giải RB Bagging gốc, dựa trên các tiêu chí về precision, recall, F1-measure và accuracy (van Rijsbergen, 1979).. - Trong thời gian tới, chúng tôi sẽ thực hiện so sánh hiệu quả giải thuật RB Bagging