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

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