Nội dung

JOURNAL OF SCIENCE OF HNUE Educational Sci., 2015, Vol. 60, No. 7A, pp. 103-111 This paper is available online at http://stdb.hnue.edu.vn DOI: 10.18173/2354-1075.2015-0057 PHƯƠNG PHÁP MỚI DỰA TRÊN ĐƯỜNG BIÊN VÀ VÙNG AN TOÀN NÂNG CAO HIỆU QUẢ PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG 1 Khúc Quỳnh Hương, 2 Đào Thu Hiền, 1 Nguyễn Thị Hồng và 1 Đặng Xuân Thọ 1 Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội Toán-tin, Trường Đại học Sư phạm Hà Nội 2 Khoa Tóm tắt. Phân lớp đối với dữ liệu mất cân bằng là một bài toán có ý nghĩa quan trọng trong thực tế và đang trở thành xu hướng tiếp cận mới của nhiều nhà nghiên cứu. Đặc biệt, trong chẩn đoán y học, số người mắc bệnh chỉ chiếm tỉ lệ rất nhỏ trên tổng số người dân nên khả năng phát hiện người mắc bệnh gặp nhiều khó khăn hoặc sai lệch lớn, gây ra hậu quả nghiêm trọng, thậm chí ảnh hưởng tới tính mạng con người. Vì vậy, hiệu quả phân lớp mất cân bằng đòi hỏi phải có tính chính xác cao. Phương pháp tiền xử lí dữ liệu là một hướng giải quyết phổ biến và đạt kết quả tốt. Bài báo này sẽ giới thiệu một số phương pháp tiếp cận trong phân lớp dữ liệu mất cân bằng như Random Oversampling và Random Undersampling. Từ đó, đề xuất một phương pháp mới dựa trên khái niệm đường biên và vùng an toàn nhằm nâng cao hiệu quả phân lớp. Thuật toán mới được cải tiến dựa trên sự kết hợp từ hai thuật toán Random Boder Oversampling và Random Safe Undersampling nghĩa là đồng thời tăng thêm các phần tử trên đường biên ở lớp thiểu số và loại bỏ các phần tử an toàn ở lớp đa số một cách ngẫu nhiên. Chúng tôi đã cài đặt thuật toán và thực nghiệm trên các bộ dữ liệu chuẩn quốc tế UCI: Yeast, Breast-p, Glass và Pima. Ví dụ, kết quả phân lớp dữ liệu Yeast có chỉ số G-mean của dữ liệu nguyên gốc là 18,85% nhưng khi áp dụng Random Oversampling, Random Undersamling, Random Safe Oversampling, Random Safe Undersampling và Random Safe Undersampling - Random Border Oversampling thì G-mean tăng lên hẳn, lần lượt là 69,31%; 46,52%; 30,69%, 41,00% và 74,86%. Từ kết quả thực nghiệm cho thấy hiệu quả phân lớp dữ liệu mất cân bằng khi áp dụng phương pháp mới của chúng tôi được cải tiến một cách đáng kể. Từ khóa: Dữ liệu mất cân bằng; Phân lớp dữ liệu; Mức độ an toàn; Đường biên; Sinh thêm phần tử ngẫu nhiên; Giảm bớt phần tử ngẫu nhiên. 1. Mở đầu Với sự phát triển nhanh chóng của lĩnh vực công nghệ thông tin thì các kĩ thuật khai phá dữ liệu, trích rút thông tin lại càng được quan tâm nghiên cứu trong đó phân lớp dữ liệu là một trong những bài toán điển hình về nhận dạng mẫu. Phân lớp là bài toán có ứng dụng rộng rãi trong nhiều lĩnh vực: công nghệ thông tin, tài chính, viễn thông... Trong đó, rất nhiều bài toán mà phân bố dữ liệu có sự chênh lệch rất lớn, ví dụ trong chẩn đoán y khoa số người bị bệnh ung thư chiếm tỉ lệ Ngày nhận bài: 15/7/2015 Ngày nhận đăng: 01/11/2015 Liên hệ: Khúc Quỳnh Hương, e-mail: khucquynhhuong1490@gmail.com 103 Khúc Quỳnh Hương, Đào Thu Hiền, Nguyễn Thị Hồng và Đặng Xuân Thọ rất nhỏ trên tổng số người dân hay những cuộc gọi gian lận chiếm tỉ lệ rất ít trên tổng số các cuộc gọi [8]. Mặc dù số lượng những người bị ung thư hay số lượng cuộc gọi rất ít nhưng việc phát hiện ra người bị ung thư hay cuộc gọi gian lận đóng vai trò rất quan trọng. Việc nghiên cứu về bài toán phân lớp được rất nhiều nhà khoa học quan tâm. Đã có nhiều thuật toán học phân lớp được công bố như: k – láng giềng gần nhất, cây quyết định, Naı̈ve Bayes, máy véc tơ hỗ trợ [7]. . . Đó là những thuật toán chuẩn áp dụng cho các trường hợp phân lớp không mất cân bằng và đã được thực nghiệm kiểm chứng. Tuy nhiên, việc áp dụng những thuật toán này cho dữ liệu mà sự chênh lệch về số lượng các phần tử của các lớp lớn thì hiệu quả không cao. Vì vậy, cần có những hướng tiếp cận mới đối với trường hợp dữ liệu mất cân bằng. Mất cân bằng dữ liệu là trường hợp dữ liệu có số lượng các phần tử của các lớp có sự chênh lệch đáng kể. Khi đó, lớp có nhiều phần tử được gọi là lớp đa số (Majority Class), lớp có ít phần tử được gọi là lớp thiểu số (Minority Class). Khi xảy ra vấn đề mất cân bằng dữ liệu, nhiều thực nghiệm đã cho thấy, do sự áp đảo về số lượng các phần tử lớp đa số làm cho hiệu quả của quá trình phân lớp bị giảm đáng kể. Chẳng hạn, bộ dữ liệu Mamography gồm 11.183 mẫu dữ liệu, trong đó có 10.923 mẫu được gán nhãn “Negative” (không ung thư) và 260 mẫu được gán nhãn “Positive” (ung thư). Giả sử một mô hình phân lớp chỉ đạt độ chính xác 10% nghĩa là có 234 mẫu lớp thiểu số bị phân lớp sai thành lớp đa số dẫn đến 234 người bị ung thư nhưng được chẩn đoán là không bị ung thư [9]. Rõ ràng việc phân lớp nhầm bệnh nhân như vậy sẽ gây hậu quả nghiêm trọng hơn việc phân lớp nhầm từ không bị bệnh thành bị bệnh. Vì vậy, bài toán phân lớp dữ liệu mất cân bằng là bài toán có ứng dụng quan trọng trong thực tế vàđược rất nhiều nhà khoa học trong lĩnh vực khai phá dữ liệu quan tâm. Hiện nay có nhiều công trình nghiên cứu giải quyết bài toán phân lớp dữ liệu mất cân bằng theo những hướng tiếp cận khác nhau [8]. Trong đó, một trong những hướng tiếp cận hiệu quả là tiền xử lí dữ liệu bằng cách tạo ra các phần tử nhân tạo nhằm tăng số lượng các phần tử của lớp thiểu số để giảm tính mất cân bằng giữa các lớp. Sau đó, chúng ta có thể áp dụng các thuật toán học phân lớp chuẩn như đã nêu ở trên. 2. 2.1. Nội dung nghiên cứu Các phương pháp liên quan Để cải thiện kết quả phân lớp trong trường hợp dữ liệu mất cân bằng, người ta có thể tiếp cận bằng nhiều phương pháp khác nhau như tiếp cận trên mức độ dữ liệu nghĩa là điều chỉnh dữ liệu giảm bớt tính mất cân bằng, tiếp cận trên mức độ thuật toán nghĩa là điều chỉnh thuật toán phân lớp sao cho hiệu quả phân lớp dữ liệu mất cân bằng không bị giảm. Phương pháp điều chỉnh dữ liệu là một phương pháp đã được nhiều thực nghiệm chứng minh là đơn giản và đạt được hiệu quả cao trên nhiều bộ dữ liệu. Điều chỉnh dữ liệu cũng có nhiều cách: giảm kích thước mẫu dữ liệu hoặc tăng kích thước mẫu dữ liệu. Thuật toán đại diện cho kĩ thuật này là Random Oversamplingvà Random Undersampling. Ngoài ra, có thể kết hợp cả hai phương pháp trên để nâng cao hiệu quả phân lớp [1]. Ramdom Oversampling (RO) là một phương pháp điều chỉnh tăng kích thước mẫu. Thuật toán nàysẽ lựa chọn ngẫu nhiên các phần tử trong lớp thiểu số và nhân bản chúng, làm cho bộ dữ liệu giảm bớt sự mất cân bằng. Ngoài ra, cũng có một số cách sinh phần tử có chủ đích như: tăng phần tử thiểu số ở vùng an toàn (Safe level), tăng phần tử ở đường biên (Borderline) [2]. . . Phương pháp điều chỉnh giảm kích thước mẫu Random Undersampling (RU) sẽ loại bỏ các phần tử ở lớp đa số một cách ngẫu nhiên đến khi tỉ số giữa các phần tử lớp thiểu số và các phần tử lớp đa số phù hợp. Do đó số lượng các phần tử của tập huấn luyện sẽ giảm đáng kể. Hai phương pháp trên đã được thực nghiệm chứng minh là hiệu quả, nhưng trong một số 104 Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu... trường hợp vẫn chưa đạt kết quả mong muốn. Vì vậy, chúng tôi đã nghiên cứu cách thức tăng (giảm) phần tử của lớp mất cân bằng dựa trên khái niệm đường biên và mức độ an toàn. Đồng thời đề xuất một phương pháp mới vừa sinh các phần tử trên đường biên ở lớp thiểu số vừa loại bỏ các phần tử an toàn ở lớp đa số một cách ngẫu nhiên. 2.2. Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu mất cân bằng 2.2.1. Random Border Oversampling (RBO) Trong bài toán phân lớp dữ liệu mất cân bằng, tất cả các thuật toán phân loại và các thuật toán tiền xử lí dữ liệu đều cố gắng xác định được đường phân chia ranh giới giữa hai lớp càng chính xác càng tốt. Đường phân chia danh giới đó được gọi là đường biên của hai lớp. Phần tử biên (nằm trên hoặc gần đường biên) sẽ nằm gần với các phần tử lớp khác nhiều hơn so với những phần tử nằm xa biên. Do vậy những phần tử này thường bị gán nhãn sai cao hơn với những phần tử xa biên. Vì vậy, chúng có vai trò quan trọng trong việc quyết định hiệu quả phân lớp. Cải tiến thuật toán Random Oversampling và sử dụng việc sinh ngẫu nhiên phần tử trên đường biên, thuật toán Random Border Oversampling tìm ra các phần tử nằm ở biên của lớp thiểu số, sau đó chỉ sinh thêm các phần tử nhân tạo giữa các phần tử biên đã tìm được. Việc sinh thêm các phần tử nhân tạo giữa các phần tử biên làm tăng cường mật độ các phần tử trên đường biên lớp thiểu số, từ đó làm tăng khả năng nhận dạng các phần tử lớp thiểu số. Để xác định một phần tử có phải là phần tử biên hay không, thuật toán xác định dựa vào số láng giềng là thuộc lớp đa số m trong tổng số k láng giềng gần nhất. Nếu có k/2 ≤ m < k thì phần tử đó là phần tử biên. Ngược lại, nếu m < k/2 thì phần tử đó không phải phần tử biên [1, 3]. Khi đó, thuật toán sẽ chọn ngẫu nhiên n phần tử biên thuộc lớp thiểu số vừa tìm được, sao chép các phần tử đó thành những bản sao giống hệt nhau. Những phần tử mới được sinh thêm này giống hệt các phần tử lớp thiểu số được chọn từ thuộc tính đến nhãn lớp. Thuật toán này có ưu điểm hơn thuật toán Random Oversamping ở việc nhân bản có mục tiêu là những phần tử biên lớp thiểu số. Thuật toán Random Border Oversampling: Input: Bộ dữ liệu huấn luyện T trong đó có tập các phần tử lớp thiểu số D. t: Tỉ lệ phần trăm số phần tử positive biên sinh thêm. k: Số láng giềng gần nhất đối với một phần tử lớp đa số (k nguyên). m: Số phần tử lớp đa số trên đường biên. Output: Bộ dữ liệu huấn luyện T và tập các phần tử sinh ngẫu nhiên trên đường biên D’. Các bước thực hiện của thuật toán như sau: • D’ = Ø • Tính k láng giềng gần nhất của p trong T • Tính số láng giềng thuộc lớp đa số m • if (k/2 ≤ m) and (m < k) • Sinh thêm phần tử p biên đang xét theo tỉ lệ t • return D’. 2.2.2. Random Safe Undersampling (RSU) Phát triển từ thuật toán Random Undersampling kết hợp với khái niệm vùng an toàn, thuật toán Random Safe Undersampling sẽ loại bỏ các phần tử an toàn ở lớp đa số một cách ngẫu nhiên [5]. Thuật toán phân chia mỗi đối tượng xác định ở cấp độ an toàn trước khi loại bỏ các đối 105 Khúc Quỳnh Hương, Đào Thu Hiền, Nguyễn Thị Hồng và Đặng Xuân Thọ tượng ngẫu nhiên. Như vậy, trong thuật toán đã áp dụng cả hai cách để loại bỏ phần tử, đó là lựa chọn các phần tử an toàn để loại bỏ và loại bỏ các phần tử một cách ngẫu nhiên. Mức độ an toàn được ước tính bởi việc sử dụng láng giềng gần nhất của các đối tượng đa số. Bằng cách tổng hợp nhiều hơn các đối tượng đa số xung quanh cấp độ an toàn lớn hơn, chúng tôi đạt được một hiệu suất chính xác hơn so với trước và so với thuật toán Random Undersampling. Trong giải thuật Random Safe Undersampling, cấp độ an toàn Safe Level (SL) được định nghĩa như trong công thức số (1) [6]. Nếu cấp độ an toàn Safe level của một đối tượng gần với số 0, đối tượng đó gần với phần tử nhiễu. Nếu nó gần với k, đối tượng đó được đặt trong vùng an toàn. Mức độ an toàn của một phần tử negative được định nghĩa trong công thức số (2). Nó thường được chọn vị trí an toàn để loại bỏ các phần tử ở lớp đa số. Safe level (sl) = số láng giềng của lớp đa số trong k láng giềng gần nhất (1). Safe level area (sl_area) = sl của đối tượng thuộc lớp đa số / k láng giềng gần nhất của phần tử đang xét (2). Giả sử n là một phần tử dữ liệu lớp đa số đang xét, thì sl_area là mức độ an toàn của phần tử đó. Đối tượng lớp đa số có bị loại bỏ hay không phụ thuộc vào tỉ lệ sl_area. Nếu sl_area < 0.5, nghĩa là xung quanh phần tử đa số đang xét không có nhiều phần tử cùng nhãn với nó, hoặc có nhiều phần tử nhiễu. Nếu sl_area > 0.5, nghĩa là xung quanh phần tử đa số đang xét có nhiều phần tử cùng nhãn với nó, phần tử đa số đang xét được coi là an toàn, ta loại bỏ ngẫu nhiên phần tử này. Thuật toán Random Safe Undersampling: Input: Bộ dữ liệu huấn luyện T trong đó có tập các phần tử lớp đa số C. z: Số % negative an toàn bị loại bỏ ngẫu nhiên. k: Số láng giềng gần nhất của phần tử negative (k nguyên). Output: Bộ dữ liệu huấn luyện T và tập các phần tử ngẫu nhiên C’. Các bước thực hiện của thuật toán: • C’ = Ø • Tính k láng giềng gần nhất của n trong T • sl = số lượng các đối tượng negative trong k láng giềng gần nhất của n trong T • sl_area = sl / k • if (sl_area > 0.5) and (sl_area ≤ 1) • Loại bỏ phần tử an toàn đang xét theo tỉ lệ z • return C’. 2.2.3. Random Safe Undersampling và Random Border Oversampling (RSU_RBO) Thuật toán mới này sẽ dựa trên đường biên và mức độ an toàn của các đối tượng để vừa sinh thêm ngẫu nhiên các phần tử trên đường biên ở lớp thiểu số, vừa loại bỏ ngẫu nhiên các phần tử an toàn ở lớp đa số. Kết hợp thuật toán Random Safe Undersampling và thuật toán Random Border Oversampling ở trên ta có thuật toán như sau: • D’ = Ø, C’ = Ø • if class = “positive” Thực hiện Thuật toán RBO • if class = “negative” Thực hiện Thuật toán RSU • return D’ ∪ C’. 106 Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu... 2.3. Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu mất cân bằng 2.3.1. Các tiêu chí đánh giá Bảng 1. Ma trận nhầm lẫn cho vấn đề mất cân bằng hai lớp Positive thực tế Negative thực tế Positive dự đoán TP FP Negative dự đoán FN TN Phân lớp được đánh giá tương đối bởi một ma trận nhầm lẫn như minh họa trong Bảng 1. Các dòng của bảng là nhãn lớp thực tế của một đối tượng, và các cột của bảng là nhãn lớp dự đoán của một đối tượng. Tiêu biểu, nhãn lớp của phân lớp thiểu số gọi là postive, và nhãn lớp của phân lớp đa số gọi là negative. TP là số phần tử có nhãn lớp thực tế là Positive và cũng được mô hình phân lớp dự đoán là Positive. FP là số phần tử có nhãn lớp thực tế là Negative nhưng được mô hình phân lớp dự đoán là Positive. FN là số phần tử có nhãn lớp thực tế là Positive nhưng được mô hình phân lớp dự đoán là Negative. TN là số phần tử có nhãn lớp thực tế là negative và cũng được mô hình phân lớp dự đoán là Negative. Một số độ đo được định nghĩa dựa trên ma trận nhầm lẫn [8]: - Tỉ lệ phần tử Positive được phân loại đúng: TPrate = TP/(TP+FN) - Tỉ lệ phần tử Negative được phân loại đúng: TN rate = TN/(TN+FP) √ - Giá trị G-mean: T Prate ∗ T Nrate Trong đó, G-mean là độ đo biểu diễn hiệu quả phân lớp của cả hai lớp thiểu số và lớp đa số. Giá trị G-mean được xác định dựa vào hai giá trị TPrate và TNrate . Và trong phần thực nghiệm, chúng tôi đã sử dụng độ đo G-mean để đánh giá hiệu quả phân lớp giữa các thuật toán [3]. 2.3.2. Dữ liệu Chúng tôi tiến hành thực nghiệm trên các bộ dữ liệu mất cân bằng của từ kho dữ liệu chuẩn quốc tế UCI [10]. Bảng 2 là thông tin về một số bộ dữ liệu mà bài nghiên cứu khoa học sử dụng trong quá trình thực nghiệm. Tên dữ liệu Yeast Glass Breast-p Pima Bảng 2. Dữ liệu chuẩn từ UCI Số phần tử 1484 193 198 768 Số thuộc tính 4 9 32 8 Tỉ lệ mất cân bằng 1:29 1:6 1:3 1:2 Các bộ dữ liệu trong bảng trên đều là các bộ dữ liệu có sự mất cân bằng lớp. Dữ liệu được gán nhãn hai lớp, lớp đa số được gán nhãn là Negative và thiểu số được gán nhãn là Positive. Trong đó, bộ dữ liệu Yeast có tỉ lệ mất cân bằng rất lớn là 1:29, bộ dữ liệu Breast-p có tỉ lệ mất cân bằng là 1:4, bộ dữ liệu Glass có tỉ lệ mất cân bằng là 1:6 và bộ dữ liệu Pima có tỉ lệ mất cân bằng là 1:2. 2.3.3. Kết quả thực nghiệm và đánh giá Đối với thuật toán Random Oversampling, thuật toán Random Undersampling, thuật toán Random Border Oversampling, thuật toán Random Safe Undersampling và thuật toán kết hợp Random Border Oversampling - Random Safe Undersampling, chúng tôi thực hiện với tham số 107 Khúc Quỳnh Hương, Đào Thu Hiền, Nguyễn Thị Hồng và Đặng Xuân Thọ sinh thêm phần tử npos lần lượt là 100%, 200%, 300%, 400%, 500%, . . . , 800% (với mỗi phần tử được xét, ta sinh thêm tương ứng 1, 2, 3, 4, . . . , 8 phần tử ngẫu nhiên với các láng giềng của nó) và tỉ lệ loại bỏ mneg là 50, 60,. . . tương ứng với số phần tử negative an toàn sẽ bị loại bỏ lần lượt là 50%, 60%,. . . so với số phần tử negative an toàn ban đầu. Để thấy rõ hiệu quả thuật toán mới, chúng tôi tiến hành so sánh kết quả dựa trên nhiều tiêu chí như: T Pr ate, T Nr ate, G-mean. Và trong phần thực nghiệm, chúng tôi sử dụng độ đo G-mean để đánh giá hiệu quả phân lớp giữa các thuật toán. Sau khi cài đặt, thống kê kết quả, chúng tôi thực hiện đánh giá hiệu của các thuật toán trên từng bộ dữ liệu như sau: Hình 1. Biểu đồ so sánh G-mean của bộ dữ liệu Glass Bộ dữ liệu Glass với số phần tử là 213, khi áp dụng thuật toán mới Random Safe Undersampling kết hợp thuật toán Random Border Oversampling thì giá trị G-mean thu được là 86,79% cao hơn so với phương pháp sử dụng thuật toán Random Oversampling có giá trị G-mean là 85,03%; phương pháp sử dụng thuật toán Random Undersampling có giá trị G-mean là 86,18%; phương pháp sử dụng thuật toán Random Safe Oversampling có giá trị G-mean là 86,79%; phương pháp sử dụng thuật toán Random Safe Undersampling có giá trị G-mean là 85,99% và phương pháp chỉ chạy bộ dữ liệu gốc có giá trị G-mean là 85,06%. Hình 2. Biểu đồ so sánh G-mean của bộ dữ liệu Yeast Bộ dữ liệu Yeast với số phần tử là 1484, khi áp dụng thuật toán mới Random Safe Undersampling kết hợp với Random Border Oversampling thì giá trị G-mean thu được là 74,86% cao hơn so với phương pháp sử dụng thuật toán Random Oversampling có giá trị G-mean là 69,31%; phương pháp sử dụng thuật toán Random Undersampling có giá trị G-mean là 46,52%; 108 Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu... phương pháp sử dụng thuật toán Random Safe Oversampling có giá trị G-mean là 30,69%; phương pháp sử dụng thuật toán Random Safe Undersampling có giá trị G-mean là 41,00% và phương pháp chỉ chạy bộ dữ liệu gốc có giá trị G-mean là 18,85%. Hình 3. Biểu đồ so sánh G-mean của bộ dữ liệu Breast-p Bộ dữ liệu Breast-p với số phần tử là 197, khi áp dụng thuật toán mới Random Safe Undersampling kết hợp với thuật toán Random Border Oversampling thì giá trị G-mean thu được là 66,42% cao hơn hẳn so với phương pháp sử dụng thuật toán Random Oversampling có giá trị G-mean là 64,97%; phương pháp sử dụng thuật toán Random Undersampling có giá trị G-mean là 58,26%; phương pháp sử dụng thuật toán Random Safe Oversampling có giá trị G-mean là 36,26%; phương pháp sử dụng thuật toán Random Safe Undersampling có giá trị G-mean là 57,20% và phương pháp chỉ chạy bộ dữ liệu gốc có giá trị G-mean là 35,5%. Hình 4. Biểu đồ so sánh G-mean của bộ dữ liệu Pima Bộ dữ liệu Pima với số phần tử là 768, khi áp dụng thuật toán mới Random Safe Undersampling kết hợp với Random Border Oversampling thì giá trị G-mean thu được là 75,45% cao hơn so với phương pháp sử dụng thuật toán Random Oversampling có giá trị G-mean là 74,08%; phương pháp sử dụng thuật toán Random Undersampling có giá trị G-mean là 74,61%; phương pháp sử dụng thuật toán Random Safe Oversampling có giá trị G-mean là 73,66%; phương pháp sử dụng thuật toán Random Safe Undersampling có giá trị G-mean là 73,46% và phương pháp chỉ chạy bộ dữ liệu gốc có giá trị G-mean là 69,21%. Các biểu đồ trên so sánh hiệu quả phân lớp của các bộ dữ liệu bằng thuật toán SVM (Support Vector Machine) trước và sau khi điều chỉnh dữ liệu bởi Random Oversampling, 109 Khúc Quỳnh Hương, Đào Thu Hiền, Nguyễn Thị Hồng và Đặng Xuân Thọ Random Undersampling, Random Safe Oversampling, Random Safe Undersamplingvà Random Safe Undersampling - Random Border Oversampling. Kết quả cho thấy, sau khi điều chỉnh bằng thuật toán Random Safe Undersampling - Random Boder Oversampling, hiệu quả phân lớp có tăng lên, điển hình là bộ dữ liệu Yeast và Breast-p tăng lên một cách đáng kể. Thuật toán Random Safe Undersampling-Random Border Oversampling đã sinh thêm các phần tử positive biên thuộc lớp thiểu số, đồng thời xóa các phần tử negative an toàn trong lớp đa số một cách ngẫu nhiên. Làm như vậy, Random Safe Undersampling - Random Border Oversampling không những làm giảm số phần tử lớp negative, mà còn làm tăng số phần tử positive một cách khoa học, tạo nên sự cân bằng dữ liệu. 2.4. Kết quả Trong nghiên cứu này, chúng tôi đã trình bày tổng quan về thuật toán mới dựa trên đường biên và vùng an toàn nhằm nâng cao hiệu quả phân lớp dữ liệu. Thông qua việc sinh ngẫu nhiên phần tử trên đường biên ở lớp thiểu số và loại bỏ phần tử an toàn ở lớp đa số đã tạo ra khả năng khai phá những cơ sở dữ liệu có kích thước lớn, nâng cao hiệu quả tính toán, làm giảm mức độ mất cân bằng dữ liệu, đồng thời làm tăng độ chính xác của các kết quả phân lớp dữ liệu. Bảng 3 thống kê số lượng phần tử an toàn thuộc lớp đa số và tỉ lệ số phần tử an toàn thuộc lớp đa số so với số phần tử đa số của bộ dữ liệu. Bảng 3. Thống kê số phần tử Tên dữ liệu Yeast Glass Breast-p Pima Tổng số phần tử Số positive (A) Số negative (B) Số positive biên (C) 1484 213 197 768 51 28 46 268 1433 185 151 500 33 2 40 114 Số negative an toàn (D) 1419 184 138 421 Tỉ lệ C/A (%) Tỉ lệ D/B (%) 64.7 7,1 87 42,5 99 99,5 91,4 84,2 Nhìn vào Bảng 3, ta dễ dàng nhận thấy trong 4 bộ dữ liệu, riêng bộ Glass có tỉ số positive biên trên tổng số positive nhỏ (7,1%) tức là trong tổng số positive trên toàn bộ dữ liệu, số positive biên rất nhỏ. Điều này cho thấy, thuật toán mới RSU_RBO cho hiệu quả phân lớp cao trên các bộ dữ liệu có số positive biên lớn và có số lượng negative an toàn cao. 3. Kết luận Trên cơ sở nghiên cứu và các kết quả đạt được, chúng tôi nhận thấy có nhiều vấn đề cần được tiếp tục nghiên cứu. Đồng thời, chúng tôi sẽ nghiên cứu kết hợp việc sinh thêm (loại bỏ) phần tử ngẫu nhiên với các phương pháp khác như Safe level, Boderline-SMOTE, Add-Boder-SMOTE hoặc phát triển thuật toán theo hướng ngược lại Random Safe Oversampling - Random Border Undersampling để đạt được hiệu quả cao hơn trong việc giải quyết vấn đề mất cân bằng lớp. TÀI LIỆU THAM KHẢO [1] H. Han, W. Wang, and B. Mao, 2005. “Borderline-SMOTE: A New Over-Sampling Method in,” ICIC, pp. 878–887. [2] Xu-Ying Liu, Jianxin Wu, and Zhi-Hua Zhou, Senior Member, IEEE, 2006. Exploratory Undersampling for Class- Imbalance Learning, 6th IEEE International Conference on Data Mining (ICDM’06), 965-969. 110 Phương pháp mới dựa trên đường biên và vùng an toàn nâng cao hiệu quả phân lớp dữ liệu... [3] Nguyễn Thị Hồng, Nguyễn Mạnh Cường, Đặng Xuân Thọ, 2014. “Add-border-SMOTE: Phương pháp mới sinh thêm phần tử trong dữ liệu mất cân bằng”. Tạp chí Khoa học và Kĩ thuật - Học viện KTQS - Số 164 (10-2014). [4] Jiawei Han, Micheline Kamber and Jian Pei, 2012. Data Mining: concepts and techniques. The Morgan Kaufmann Series of ELSEVIER. [5] Chumphol Bunkhumpornpat, Krung Sinapiromsaran, and Chidchanok Lursinap, 2009. “Safe-Level-Smote: Safe-Level-Synthetic Minority Over Samling Technique for Handling the Class Imbalanced Problem”. PAKDD, pp. 475 – 482. [6] Chawla, N., Japkowicz, N., Kolcz, 2004. “Special Issue on Learning from Imbalanced Data Sets”. Sigkdd Exploration, Volume 6, Issue 1. [7] X. Wu, V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, P. S. Yu, Z.-H. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg 2007. “Top 10 algorithms in data mining.” Knowl. Inf. Syst., Vol. 14, No. 1, pp. 1–37. [8] Y. Sun, A. K. C. Wong, and M. S. Kamel, 2009. Classification of imbalanced data: A review. Int. J. Pattern Recognit, Artificial Intell, Vol 23, No. 4, pp.687-719. [9] E. a. Garcia, “Learning from Imbalanced Data,” IEEE Trans. Knowl. Data Eng., Vol. 21, No. 9, pp. 1263–1284, Sep. 2009. [10] A.&Newman, 2007. D.J: UCI Machine Learning Repository. Irvine, CA: University of California, School of Information and Computer Science. ABSTRACT The new method based on safe zone improves the efficiency of imbalanced data classification Classifying imbalanced data is important and is being looked at by many researchers. In particular, in medical diagnostics, the number of infected people is very small compared to the total population which makes it difficult to detect disease and may lead to large deviations with serious consequences to human beings. Therefore, efficiency of classification of imbalanced data requires high accuracy level. Preprocessing data brings good results. This article will introduce several ways to deal with imbalanced data classification such as Random Oversampling and Random Undersampling. We propose a new method based on the concept of a borderline and safe area to enhance the classification efficiency. A new algorithm combines the two algorithms Random Boder Oversampling and Random Safe Undersampling, which means adding more elements in the minority class boundary while randomly reducing safe elements in the majority class. We have installed the algorithm and experimented on international standard UCI datasets: Yeast, Breast-p, Glass và Pima. For example, Yeast data classification results in 18.85 percent of G-mean index but the index increases significantly when applying Random Oversampling, Random Undersampling, Random Safe Oversampling, Random Safe Undersampling or Random Safe Undersampling - Random Border Oversampling, which are 69.31%; 46.52%; 30.69%, 41.00% and 74.86% respectively. The experimental results reflect the improved efficiency of imbalanced data classification when our new method is applied. Keywords: Classification, imbalanced data, Random Oversampling, Random Undersampling, Random Border Oversampling, Random Safe Oversampling. 111