Phương pháp DEC-SVM phân lớp dữ liệu mất cân bằng

này, tác giả đã nghiên cứu thuật toán DEC-SVM điều chỉnh dữ liệu bằng cách sinh thêm phần tử cho lớp thiểu số, sau đó sử dụng kỹ thuật phân cụm để loại bỏ bớt phần tử dư thừa. Thực nghiệm cho thấy DEC-SVM có khả năng nâng cao hiệu quả phân lớp cho các bộ dữ liệu mất cân bằng. Từ khóa: Phân cụm; phân lớp; dữ liệu mất cân bằng; SVM. Abstract In this article, authors study the DEC-SVM algorithm that modulates data by adding elements to the minority class, and then uses clustering techniques to eliminate redundant elements. Empirical evidence show that the DEC-SVM is capable of enhancing class efficiency for imbalanced data sets. Keywords: Clustering; classification; imbalanced data; SVM. 1. GIỚI THIỆU CHUNG Ngày nay, khi vấn đề khai thác và xử lý thông tin ngày càng được chú trọng, kỹ thuật phân lớp dữ liệu đã góp phần hữu hiệu giúp con người khai thác một cách có hiệu quả khối dữ liệu mà họ đang nắm giữ. Tuy nhiên, dữ liệu thu thập được trong thực tế ngày càng xuất hiện nhiều các bộ dữ liệu mất cân bằng, nghĩa là trong tập dữ liệu có sự chênh lệch lớn về số lượng các phần tử giữa các lớp. Các bộ dữ liệu trong nhiều ứng dụng thực tế như phát hiện các giao dịch gian lận, phát hiện xâm nhập mạng, dự đoán rủi ro trong quản lý, chẩn đoán y khoa,, đều là các bộ dữ liệu mất cân bằng mà trong đó, lớp người ta cần quan tâm lại chiếm tỉ lệ rất nhỏ so với lớp còn lại. Sự chênh lệch về số lượng giữa lớp đa số và lớp thiểu số làm cho việc phân lớp đúng các mẫu thuộc lớp thiểu số bị giảm hiệu quả. Tỷ lệ mất cân bằng của tập dữ liệu càng cao thì việc phát hiện đúng các mẫu của lớp thiểu số càng khó khăn. Trong các ứng dụng thực tế, tỷ lệ mất cân bằng có thể là 1:100, 1:1000, thậm chí có thể hơn [11]. Vì thế, phân lớp dữ liệu mất cân bằng đã và đang là bài toán được các nhà khoa học đặc biệt quan tâm. Người phản biện: 1. GS.TSKH. Thân Ngọc Hoàn 2. TS. Trần Trọng Hiếu Đối với các bộ dữ liệu mất cân bằng, các bộ phân lớp chuẩn thường có xu hướng thiên vị đối với lớp đa số và bỏ qua lớp thiểu số (xử lý chúng như là nhiễu) [4]. Vì vậy, khi áp dụng các giải thuật phân lớp truyền thống chưa thể xây dựng được một bộ phân lớp tốt. Việc phân loại sai các mẫu thuộc lớp thiểu số có thể gây nên những tổn thất lớn đối với các lĩnh vực thực tế. Để giải quyết vấn đề về phân lớp đối với các bộ dữ liệu mất cân bằng, hiện nay có nhiều phương pháp khác nhau, trong đó, có hai hướng tiếp cận chính: tiếp cận ở mức độ dữ liệu và hướng tiếp cận ở mức độ thuật toán. Trong [12], tác giả cải tiến thuật toán sinh thêm mẫu nhân tạo lớp thiểu số (SMOTE) bằng cách kết hợp thuật toán nhúng tuyến tính cục bộ (locally linear embedding - LLE). Thuật toán LLE ánh xạ dữ liệu có số chiều cao vào một không gian với số chiều thấp hơn. Sau đó, các mẫu nhân tạo sinh ra sẽ được ánh xạ trở lại không gian mẫu ban đầu thông qua LLE. Từ bộ dữ liệu đã điều chỉnh, thực nghiệm trên 3 bộ dữ liệu với ba kỹ thuật phân lớp Bayes, K-NN, SVM cho thấy kỹ thuật SVM có độ chính xác theo tiêu chí AUC cao nhất với trung bình là 76.5%. Trong [13], tác giả trình bày giải thuật GSVM -RU (Granular Support Vector Machines Repetitive Undersampling) sử dụng SVM cho việc lấy mẫu. Với những mẫu quan trọng trong quá trình phân lớp, giảm thiểu mất thông tin các mẫu đa số khi loại bỏ và tối đa mẫu thiểu số 18 NGHIÊN CỨU KHOA HỌC Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 khi làm sạch dữ liệu trong quá trình lấy mẫu để chỉ giữ lại các mẫu cần thiết và các mẫu khác có thể được loại bỏ một cách an toàn mà không ảnh hưởng đến phân loại. Việc trích chọn vectơ ít hơn, do đó tăng tốc độ dự đoán. Kết quả thực nghiệm với các đánh giá G-Mean (85.2%), AUC (92.4%), F-Measure (66.5%). Trong [14], tác giả đề xuất phương pháp Bagging of Extrapolation Borderline- SMOTE SVMs (BEBS) sử dụng phương pháp lấy mẫu thích nghi Extrapolation Borderline-SMOTE và tập hợp bootstrapping vào tập dữ liệu không cân bằng ban đầu. Khi sử dụng SVM, ranh giới quyết định nghiêng về phía các mẫu thiểu số và có thể được thay đổi dựa vào các mẫu nhân bản. Kết quả thực nghiệm đánh giá dựa trên tiêu chí G-Mean đạt 76.2%. Tuy nhiên, với đặc thù của các tập dữ liệu hầu hết không giống nhau, không có giải pháp nào là hữu hiệu cho mọi tập dữ liệu. Trong bài báo này, chúng tôi đề xuất thuật toán DEC-SVM để phân lớp dữ liệu. Cụ thể, nghiên cứu thuật toán điều chỉnh dữ liệu cho bài toán phân lớp dữ liệu mất cân bằng – thuật toán DEC (a novel Differential Evolution Clustering hybrid resampling) được công bố vào năm 2010 của nhóm tác giả Leichen Chen, Zhihua Cai, Lu Chen và Qiong Gu [1]. Thuật toán này là sự kết hợp giữa phương pháp sinh thêm phần tử cho lớp thiểu số và sử dụng kỹ thuật phân cụm, K-means để loại bỏ bớt phần tử dư thừa, nhiễu trong dữ liệu. Với mỗi mẫu thuộc lớp thiểu số, tạo ra một mẫu đột biến từ hai trong số những láng giềng gần nó nhất, sau đó sử dụng thuật toán di truyền để sinh thêm phần tử cho lớp thiểu số từ mẫu thiểu số ban đầu và mẫu đột biến mới tạo ra. Sau khi điều chỉnh dữ liệu bằng thuật toán DEC, chúng tôi sử dụng kỹ thuật SVM để phân lớp cho tập dữ liệu huấn luyện mới để tạo ra mô hình phân lớp. Kết quả cho thấy, khi sử dụng DEC-SVM thì hiệu quả phân lớp các bộ dữ liệu mất cân bằng cao hơn. 2. PHƯƠNG PHÁP DEC-SVM CHO BÀI TOÁN PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG 2.1. Hướng tiếp cận ở mức độ dữ liệu Tiếp cận ở mức độ dữ liệu mục đích là điều chỉnh tỉ lệ mất cân bằng giữa hai lớp trong bộ dữ liệu, cụ thể sử dụng các hình thức lấy mẫu: sinh thêm các phần tử lớp thiểu số (sinh ngẫu nhiên, sinh thêm phần tử nhân tạo,), loại bỏ các phần tử lớp đa số, hoặc kết hợp cả hai phương pháp trên. 2.1.1. Sinh thêm phần tử lớp thiểu số Có nhiều phương pháp sinh thêm phần tử cho lớp thiểu số như: sinh ngẫu nhiên phần tử lớp thiểu số, lựa chọn phần tử lớp thiểu số, sinh thêm mẫu nhân tạo. Sinh ngẫu nhiên các phần tử ở lớp thiểu số là phương pháp đơn giản nhất nhằm cân bằng phân lớp thông qua việc nhân bản ngẫu nhiên các mẫu lớp thiểu số. Ý tưởng là lựa chọn ngẫu nhiên các mẫu thuộc lớp thiểu số và nhân bản chúng tạo ra mẫu mới giống hệt chúng. Hình 1 minh họa phương pháp sinh thêm phần tử cho lớp thiểu số. Hình 1. Sinh ngẫu nhiên phần tử lớp thiểu số Phương pháp sinh thêm mẫu nhân tạo lớp thiểu số SMOTE (Synthetic Minority Over-sampling Technique) như sau: Với mỗi mẫu thuộc lớp thiểu số, tìm láng giềng gần nhất của nó trong lớp thiểu số, lựa chọn ngẫu nhiên các láng giềng gần nhất (hoặc tất cả láng giềng) tùy theo số lượng mẫu cần sinh thêm. Mẫu nhân tạo sẽ được sinh ra theo cách sau: lấy độ lệch giữa vector thuộc tính của mẫu đang xét và láng giềng của nó nhân với một số ngẫu nhiên trong khoảng (0, 1) rồi cộng kết quả thu được với vector thuộc tính của mẫu đang xét. Kết quả cuối cùng chính là vector thuộc tính của mẫu nhân tạo, nhãn của mẫu nhân tạo sẽ được gán là nhãn của lớp thiểu số [9] và được minh họa trong hình 2. Hình 2. Minh họa sinh thêm phần tử nhân tạo bằng thuật toán SMOTE Giả mã của thuật toán SMOTE [9]: SMOTE (N, T, k) Input: Số mẫu lớp thiểu số T; tổng số SMOTE N%, số láng giềng gần nhất k. Output: (N/100)*T mẫu thiểu số nhân tạo 1. (Nếu N nhỏ hơn 100%, chọn ngẫu nhiên các mẫu lớp thiểu số mà chỉ một phần trăm của chúng sẽ được SMOTE) 2. IF N< 100 3. Then chọn ngẫu nhiên T mẫu lớp thiểu số 4. T = (N/100)*T 5. N = 100 LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 19 6. Endif 7. N = (int) (N/100) (Số luợng SMOTE được giả định là bội số của 100) 8. k = số láng giềng gần nhất 9. numattrs = số thuộc tính 10. sample [ ][ ]: mảng các mẫu thiểu số ban đầu 11. newindex: chỉ số của mẫu nhân tạo được tạo ra, khởi tạo là 0 12. synthetic [ ][ ]: mảng các mẫu nhân tạo (tính k láng giềng gần nhất cho mỗi mẫu lớp thiểu số.) 13. For to T 14. Tính k láng giềng gần nhất cho i và lưu vào mảng nnarray. 15. Populate (N, i, nnarray) 16. Endfor Populate (N, i, nnarray) (hàm sinh các mẫu nhân tạo) Input: Số mẫu cần sinh thêm N, mỗi mẫu lớp thiểu số i, mảng các láng giềng gần nhất nnarray. Output: Vector thuộc tính của mẫu nhân tạo 1. While N≠0 2. Chọn ngẫu nhiên một số nn giữa 1 và k 3. For attr←1 to numattrs 4. Tính dif=Sample[nnarray[n,n]][attr]-Sample[i][attr] 5. Tính gap = một số ngẫu nhiên giữa 0 và 1 6. Synthentic[newindex][attr]=Sample[i][ attr]+gap*dif 7. Endfor 8. ++ 9. N=N-1 10. Endwhile 11. Return (kết thúc hàm Populate) Ngoài ra còn có một số thuật toán được cải tiến từ thuật toán SMOTE như: Borderline-SMOTE [6], Safe-level SMOTE [3] cũng đem lại những hiệu quả nhất định hỗ trợ quá trình phân lớp cho các bộ dữ liệu mất cân bằng. 2.1.2. Loại bỏ phần tử lớp đa số Là phương pháp điều chỉnh phân bố dữ liệu bằng cách giảm bớt số lượng phần tử lớp đa số. Loại bỏ một cách ngẫu nhiên các mẫu thuộc lớp đa số là đơn giản nhất. Phương pháp này thực hiện loại bỏ ngẫu nhiên phần tử thuộc lớp đa số trong tập huấn luyện (hình 3a) cho tới khi có được tỷ lệ phù hợp giữa hai lớp. Với lý do này, số lượng phần tử trong tập huấn luyện giảm đáng kể (hình 3b). M M u thi u s (a) (b) Hình 3. Minh họa loại bỏ phần tử lớp đa số Tuy nhiên, việc loại bỏ mẫu có thể sẽ làm hao hụt thông tin và có khả năng làm mất đi những mẫu mang thông tin quan trọng cho quá trình xây dựng mô hình phân lớp. Khắc phục hạn chế của phương pháp trên, một số phương pháp loại bỏ mẫu theo mục tiêu được đề xuất như: Tomek links, One-side Selection, Neighborhood Cleaning Rule [7]. 2.2. Hướng tiếp cận ở mức độ thuật toán Tiếp cận ở mức độ thuật toán nghĩa là điều chỉnh các thuật toán phân lớp để tăng cường độ chính xác khi phân lớp đối với dữ liệu mất cân bằng. Chiến lược chung để đối phó với vấn đề mất cân bằng trong các bộ dữ liệu là lựa chọn một khuynh hướng quy nạp thích hợp. Ví dụ như đối với phương pháp cây quyết định, cách tiếp cận có thể là điều chỉnh dự đoán xác xuất ở lá, hoặc phát triển phương pháp cắt tỉa mới. Hay đối với phương pháp phân lớp SVM, có thể sử dụng hằng số phạt khác nhau cho các lớp hoặc điều chỉnh ranh giới lớp dựa trên ý tưởng liên hết hạt nhân [11]. Đối với phương pháp phân lớp K-NN, có thể đề xuất một hàm khoảng cách có trọng số. Ý tưởng này nhằm bù cho sự mất cân bằng trong mẫu huấn luyện mà không làm thay đổi sự phân lớp. 2.3. Thuật toán DEC-SVM cho bài toán phân lớp dữ liệu mất cân bằng Phương pháp sinh thêm phần tử nhân tạo cho lớp thiểu số là phương pháp hiệu quả cho các bài toán phân lớp dữ liệu mất cân bằng. Tuy nhiên, trong nhiều trường hợp, việc sinh thêm mẫu có thể sẽ tạo ra những mẫu dư thừa hoặc nhiễu làm ảnh hưởng tới hiệu quả phân lớp. Thuật toán DEC-SVM dựa trên việc tạo ra phần tử nhân tạo trên lớp thiểu số nhằm giảm tỷ lệ mất cân bằng, 20 NGHIÊN CỨU KHOA HỌC Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 sau đó sử dụng kỹ thuật phân cụm cho tập dữ liệu để loại bỏ những mẫu dư thừa hoặc nhiễu. Bằng cách lấy mẫu kết hợp với làm sạch dữ liệu, các mẫu hữu ích vẫn được giữ lại và nâng cao hiệu quả phân lớp. 2.3.1. Điều chỉnh dữ liệu bằng thuật toán DE Với thuật toán SMOTE, mẫu mới sẽ được sinh ra từ một mẫu positive (mẫu lớp thiểu số) ban đầu và một trong những láng giềng của nó. Với nền tảng là thuật toán MOTE, tuy nhiên, trong thuật toán DE, từ hai trong số các láng giềng gần nhất của một mẫu positive sẽ tạo ra một mẫu “đột biến”, và mẫu mới được sinh ra bằng cách lai ghép chéo mẫu đột biến này và mẫu positive ban đầu. 2.3.1.1. Đột biến Trong tập dữ liệu huấn luyện, đầu tiên chọn ngẫu nhiên một mẫu positive và tìm k láng giềng gần nhất của nó, sau đó chọn ngẫu nhiên hai láng giềng trong láng giềng đó: x n1 và x n2 . Một mẫu đột biến x mu sẽ được tạo ra bằng cách sử dụng công thức (1) với rand(0,1) là hằng số ngẫu nhiên trong khoảng [0,1]: x mu=x i+rand(0,1) × (x n1-x n2) (1) 2.3.1.2. Crossover Qua bước đột biến, ta tạo ra số lượng mẫu đột biến đúng bằng số lượng mẫu positive ban đầu trong tập dữ liệu huấn luyện. Ở bước này, ta sẽ sử dụng các mẫu đột biến cùng với các mẫu positive ban đầu để tạo ra mẫu nhân tạo mới. Cụ thể, các mẫu mới sẽ được hình thành dựa theo (2): xnew,j= xi,j nếu rand(j)>CR và j ≠ rand(s) (2) xmu,j nếu rand(j) ≤ CR hoặc j=rand(s) trong đó: xi,j là thuộc tính thứ j của mẫu thứ i; CR là hằng số crossover được lựa chọn ngẫu nhiên trong [0, 1] và được xác định trước bởi người dùng; rand(j) là giá trị được lựa chọn ngẫu nhiên trong khoảng [0, 1]. Giá trị của biến rand(s) là chỉ số của các thuộc tính được lấy một cách ngẫu nhiên, đảm bảo rằng mẫu mới sinh ra sẽ có ít nhất một thuộc tính từ mẫu đột biến. Số mẫu nhân tạo được tạo ra đúng bằng số mẫu positive ban đầu, và các mẫu nhân tạo này được gán nhãn là positive. Tùy thuộc vào số lượng mẫu positive cần lấy, lặp lại các bước đột biến và crossover cho dữ liệu huấn luyện. 2.3.2. Kỹ thuật làm sạch dữ liệu sử dụng phân cụm Sau khi thực hiện thuật toán DE, dữ liệu thu được đã được cải thiện hơn về tỉ lệ giữa hai lớp. Tuy nhiên, không loại trừ khả năng sinh ra những mẫu dư thừa hoặc nhiễu. Để khắc phục, ta sẽ sử dụng kỹ thuật phân cụm để phân cụm cho tập dữ liệu với mục đích loại bỏ những mẫu không cần thiết. Chẳng hạn ta thu được các cụm và giả sử được đặt tên là A, B, C, D, E, F như hình 4. Trong đó, một số cụm chứa tất cả các mẫu có cùng nhãn lớp (các cụm C, D, E và F), những cụm khác chứa các mẫu có nhãn lớp khác nhau (cụm A và B), dự đoán rằng có thể siêu phẳng của SVM [2, 8] sẽ đi qua các cụm này. Hình 4. Minh họa phân cụm tập dữ liệu mất cân bằng Nếu như tất cả các mẫu trong một cụm đều có cùng một nhãn lớp (tức là hoặc cùng là positive hoặc cùng là negative), ta sẽ tiến hành loại bỏ những mẫu dư thừa hoặc nhiễu. Giả sử với cụm F có chứa tất cả các mẫu negative, ta làm như sau: ‒ Xác định ngưỡng tương đồng trong (0,1] ‒ Tính theo công thức (3): LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 21 (3) ‒ Tìm mẫu trung tâm gần nhất ‒ Tính độ tương đồng Sic giữa mỗi mẫu và theo (4). Nếu Sic lớn hơn ngưỡng tương đồng thì xi sẽ bị loại khỏi F. Ngưỡng tương đồng càng nhỏ thì càng nhiều mẫu bị loại bỏ. Trong đó: ni là số lượng mẫu trong cụm thứ i; xik là thuộc tính thứ k của mẫu I; Sij là độ tương đồng giữa xi và xj 2.3.3. Thuật toán Phương pháp sinh thêm phần tử cho lớp thiểu số bằng thuật toán DE kết hợp với kỹ thuật loại bỏ phần tử dư thừa (nhiễu) bằng phân cụm tạo nên thuật toán điều chỉnh dữ liệu DEC. Sau khi điều chỉnh dữ liệu bằng thuật toán DEC, sử dụng kỹ thuật SVM để phân lớp cho bộ dữ liệu tạo nên mô hình phân lớp. Quá trình thực hiện phân lớp dữ liệu được mô tả trong hình 5. Hình 5. Quá trình phân lớp dữ liệu bằng thuật toán DEC-SVM Thuật toán DEC-SVM được mô tả như sau: DEC-SVM (N, m, k, s, T) Input: Số mẫu lớp thiểu số 𝑁, số thuộc tính 𝑚, số cụm 𝑘, ngưỡng tương đồng 𝑠, số lượng của DE 𝑇% Output: Mô hình huấn luyện. Bước 1: Sinh thêm mẫu nhân tạo cho lớp thiểu số bằng thuật toán DE. 1.1. Tính số lượng mẫu lớp thiểu số được tạo ra 𝐺 = (𝑁 * T%) 1.2. Với mỗi mẫu thuộc lớp thiểu số xi, tìm k láng giềng gần nhất của nó. 1.3. Chọn ngẫu nhiên hai trong số k láng giềng của xi: xn1, xn2 để tạo ra mẫu đột biến theo công thức: x mu=x i+rand(0,1) × (x n1-x n2) 1.4. Tạo ra mẫu thiểu số mới từ xi và mẫu đột biến của nó theo x mu công thức: với xi,j là thuộc tính j của mẫu thứ i, , 1.5. Nhãn của mẫu nhân tạo được gán là nhãn của lớp thiểu số. Bước 2: Loại bỏ mẫu dư thừa (nhiễu) bằng phân cụm. Sử dụng thuật toán 𝑘-𝑚𝑒𝑎𝑛 phân cụm cho dữ liệu huấn luyện. Tại các cụm có các mẫu thuộc cả hai lớp: 2.1. Chọn , tính với và tìm mẫu trung tâm của cụm. 22 NGHIÊN CỨU KHOA HỌC Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 2.2. Tính độ tương đồng giữa mỗi mẫu trong cụm với bằng công thức: với xik là thuộc tính thứ k của mẫu . 2.3. Nếu , loại bỏ . Bước 3: Sử dụng SVM phân lớp cho tập dữ liệu để tạo ra mô hình phân lớp. 3. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 3.1. Các tiêu chí đánh giá 3.1.1. Ma trận nhầm lẫn Trong tập dữ liệu, với quy ước các phần tử lớp đa số là negative, phần tử lớp thiểu số là positive, ta có ma trận nhầm lẫn như trong bảng 1 [11]. Bảng 1. Ma trận nhầm lẫn Dự đoán là positive Dự đoán là negative Thực tế là positive TP FN Thực tế là negative FP TN Trong đó các hàng của ma trận là nhãn lớp thực tế, các cột của ma trận là nhãn lớp dự đoán. TN: số lượng phần tử lớp đa số được phân loại chính xác. FN: số lượng phần tử lớp thiểu số bị phân loại nhầm là phần tử lớp đa số. TP: số lượng phần tử lớp thiểu số được phân loại chính xác. FP: số lượng phần tử lớp đa số bị phân loại nhầm là phần tử lớp thiểu số. Từ đó, độ chính xác của mô hình được tính theo công thức sau: Ngoài ra còn có một số độ đo đánh giá khác dựa trên ma trận nhầm lẫn như: 3.1.2. F-Measure Một độ đo cũng thường được dùng để đánh giá mô hình phân lớp đó là F-measure hay F-core được tính dựa trên hai độ đo khác là precision và recall, và được tính như sau [5]: 3.1.3. G-mean G-mean là độ đo thể hiện sự cân bằng giữa hai giá trị và , G-mean được tính theo công thức sau [11]: 3.1.4. Đường cong ROC và độ đo AUC ROC (receiver operating characteristic) là phương pháp xuất phát từ lĩnh vực quân sự, là phương pháp được ứng dụng trong việc phát hiện tàu địch trên màn hình radar trong Chiến tranh thế giới thứ hai [10]. ROC được dùng để đánh giá các kết quả của một dự đoán. Cho tới nay, ROC đã được ứng dụng hiệu quả ở một số lĩnh vực như học máy (đánh giá các kết quả của học máy), chẩn đoán và tiên lượng y khoa (chẩn đoán một người có mắc bệnh hay không). Đường cong ROC (hình 6) là một đồ thị với trục tung là tỉ lệ True Positive (TPrate) và trục hoành là tỉ lệ False Positive (FPrate) cho một hệ thống phân loại nhị phân. Diện tích phía dưới đường cong ROC được gọi là AUC, là thước đo độ chính xác cho bài toán phân lớp dữ liệu [10]. Hình 6. Đường cong ROC LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 23 3.2. Dữ liệu và thiết lập thực nghiệm 3.2.1. Dữ liệu thực nghiệm Ðể thấy được hiệu quả của thuật toán DEC-SVM, tác giả tiến hành thực nghiệm với 4 bộ dữ liệu được lấy từ kho dữ liệu UCI. Thông tin về các bộ dữ liệu được thể hiện trong bảng 2. Bảng 2. Bộ dữ liệu sử dụng cho thực nghiệm Tên bộ dữ liệu Số thuộc tính Số mẫu lớp thiểu số Số mẫu lớp đa số Tỉ lệ mất cân bằng Breast-w 10 241 458 1:1,9 Glass 10 29 185 1:6,38 Heart 14 120 150 1:1,25 Pima 9 268 500 1:1,87 Các bộ dữ liệu nêu trên đều có sự mất cân bằng giữa các lớp. Trong đó, glass là bộ dữ liệu có tỷ lệ mất cân bằng cao nhất. Ngoại trừ dữ liệu glass, ba bộ dữ liệu còn lại đều là các dữ liệu trong y học. Dữ liệu breast-w là dữ liệu về ung thư vú, heart là dữ liệu về bệnh tim và pima là dữ liệu bệnh tiểu đường tại Ấn Ðộ. Hình 7. Tỉ lệ mất cân bằng các bộ dữ liệu Trong các bộ dữ liệu trên, lớp đa số được gán nhãn là Negative và lớp thiểu số được gán nhãn Positive. 3.2.2. Thiết lập thực nghiệm Ðể nâng cao tính chính xác của các độ đo theo các tiêu chí đánh giá đã nêu trên, ta sử dụng phương pháp k-Fold Cross Validation với k = 10. Bộ dữ liệu ban đầu được chia thành 10 tập con (10 fold) với kích thước tương đương nhau. Thực hiện 10 lần lặp, tại mỗi lần lặp, sử dụng 1 tập con làm dữ liệu kiểm tra (Test Set) và 9 phần còn lại được dùng làm dữ liệu huấn luyện (Training Set). Với tập dữ liệu huấn luyện, ta áp dụng một phương pháp điều chỉnh dữ liệu, sau đó được sử dụng mô hình phân lớp bằng thuật toán phân lớp SVM. Nhằm so sánh hiệu quả của thuật toán DEC-SVM, ta cũng đồng thời áp dụng một số phương pháp điều chỉnh dữ liệu bao gồm: SVM, SMOTE-SVM, DE-SVM. Cuối cùng, sử dụng mô hình phân lớp để phân lớp cho dữ liệu kiểm tra. Kết quả đánh giá phân lớp sau mỗi lần 10-fold là trung bình cộng của các giá trị trong 10 lần lặp. Ðể đánh giá chính xác hơn hiệu quả của mô hình phân lớp, ta thực hiện 10 lần 10-fold. Ngôn ngữ được sử dụng để cài đặt chương trình là ngôn ngữ R. R là một ngôn ngữ sử dụng cho thống kê và đồ họa được sáng tạo bởi hai nhà thống kê học là Ross Ihaka và Robert Gentleman. 3.3. Kết quả thực nghiệm và đánh giá Bảng 3 là kết quả đánh giá hiệu quả phân lớp cho các bộ dữ liệu sử dụng thuật toán DE-SVM. Bảng 4 là kết quả đánh giá hiệu quả phân lớp cho các bộ dữ liệu sử dụng thuật toán DEC-SVM. Bảng 3. Phân lớp dữ liệu sử dụng thuật toán DE-SVM Datasets AUC G-mean F-measure TPrate TNrate PPvalue Breast 0.974 0.974 0.956 0.991 0.925 0.956 Glass 0.914 0.894 0.866 0.833 0.994 0.975 Pima 0.725 0.699 0.658 0.906 0.544 0.519 Heart 0.747 0.727 0.748 0.90 0.593 0.643 Bảng 4. Phân lớp dữ liệu sử dụng thuật toán DEC-SVM Datasets AUC G-mean F-measure TPrate TNrate PPvalue Breast 0.970 0.969 0.954 0.975 0.963 0.934 Glass 0.928 0.922 0.892 0.867 0.989 0.942 Pima 0.753 0.745 0.683 0.854 0.652 0.57 Heart 0.798 0.79 0.788 0.875 0.720 0.723 24 NGHIÊN CỨU KHOA HỌC Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 Bảng 5 so sánh hiệu quả của hai thuật toán DESVM và DEC-SVM khi sử dụng cho các bộ dữ liệu thử nghiệm. Bảng 5. Bảng so sánh hiệu quả phân lớp Ðộ đo đánh giá Thuật toán Dữ liệu Breast-w Glass Pima Heart AUC SVM 0.960 0.910 0.720 0.745 SMOTE 0.957 0.912 0.71 0.768 DE-SVM 0.974 0.914 .725 0.747 DEC-SVM 0.970 0.928 0.753 0.797 G-MEAN SVM 0.960 0.900 0.701 0.750 SMOTE 0.96 0.900 0.7 0.775 DE-SVM 0.974 0.894 0.699 0.727 DEC-SVM 0.969 0.921 0.745 0.790 F-MEASURE SVM 0.94 0.861 0.627 0.720 SMOTE 0.947 0.82 0.76 0.8 DE-SVM 0.956 0.866 0.657 0.748 DEC-SVM 0.954 0.892 0.683 0.788 Hình 8, hình 9, hình 10 là biểu đồ so sánh lần lượt các giá trị AUC, G-mean, F-measure khi sử dụng các thuật toán SVM, SMOTE, DE-SVM và DEC-SVM với 4 bộ dữ liệu thực nghiệm. Hình 8. Biểu đồ so sánh giá trị AUC Hình 9. Biểu đồ so sánh giá trị G-mean Hình 10. Biểu đồ so sánh giá trị F-measure 4. KẾT LUẬN Có thể thấy, với thuật toán DE-SVM, các kết quả đánh giá phân lớp đạt giá trị tương đối khả quan. Tuy nhiên, sau khi kết hợp thêm kỹ thuật phân cụm làm sạch dữ liệu tạo ra thuật toán DEC-SVM, hiệu quả phân lớp đã cao hơn. Trong 4 bộ dữ liệu thực nghiệm thì ở các bộ dữ liệu glass, pima và heart, kết quả đánh giá phân lớp của thuật toán DEC-SVM đều cao hơn thuật toán DE-SVM. Riêng đối với bộ dữ liệu breast-w, các tiêu chí đánh giá AUC, G-mean của giải thuật DEC-SVM đều cao hơn các giải thuật còn lại. Chỉ có tiêu chí F-measure thì thuật toán DE-SVM (đạt 0.956) tỏ ra hiệu quả hơn DEC-SVM (đạt 0.954). Ta thấy, giá trị khác biệt này không lớn, điều đó khẳng định hiệu LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 25 quả của phương pháp DEC-SVM trong phân lớp dữ liệu mất cân bằng. TÀI LIỆU THAM KHẢO [1]. Leichen Chen, Zhihua Cai, Lu Chen (2010). A Novel Different Evolution-Clustering Hybrid Resampling Algorithm on Imbalanced Datasets. In Knowledge Discovery and Data Mining, 2010. WKDD ‘10. Third International Conference on, pp. 81-85. [2]. Corinna Cortes & Vladimir Vapnik (1995). Support-Vector Networks. Machine Learning, vol. 20, pp. 273-297. [3]. Chumphol Bunkhumpornpat, Krung Sinapiromsaran, Chidchanok Lursinsap (2009). Safe-Level-SMOTE: Safe-Level-Synthetic Minority Over Sampling Technique for Handling the Class Imbalanced Problem. In Advances in Knowledge Discovery and Data Mining: Springer-Verlag Berlin Heidelberg, vol. 5476, pp. 475-482. [4]. Mikel Galar, Alberto Fernandez, Edurne Barrenechea, Humberto Bustince (2011). A Review on Ensembles for the Class Imbalance Problem: Bagging – Boosting, and Hybrid-Based Approaches. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 42, no. 4, pp.463-484. [5]. Haibo He and Edwardo A. Garcia (2009). Learning from Imbalanced Data (2009). IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 9, pp. 1263 - 1284. [6]. Han Hui, Wang Wen-Yuan, and Mao Bing-Huan (2005). Borderline-SMOTE: A New Over-Sampling Method in Imbalanced Data Sets Learning. In ICIC 2005, pp. 878-887. [7]. Sotiris Kotsiantis, Dimitris Kanellopoulos, Panayiotis Pintelas (2006). Handling imbalanced datasets: A review. GESTS International Transactions on Computer Science and Engineering, vol.30. [8]. David Meyer (2015). Support Vector Machines: The Interface to libsvm in package e1071. pp. 1-8. [9]. Chawla Nitesh V., Bowyer Kevin W., O. Hall Lawrence, and Kegelmeyer W. Philip (2002). SMOTE: Synthetic Minority Over-sampling Technique. Artificial Intelligence Research, vol. 16, pp. 321–357. [10]. Hanley JA, McNeil BJ (1982). The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, vol. 143(1), pp.29-36. [11]. Sun Yanmin, Wong Andrew K.C., and Kamel Mohamed S. (2009). Classification of imbalanced data: A review. International Journal of Pattern Recognition and Artificial Intelligence, vol. 23, pp. 687–719. [12]. Juanjuan Wang, Mantao Xu, Hui Wang, Jiwu Zhang. Classification of Imbalanced Data by Using the SMOTE Algorithm and Locally Linear Embedding. [13]. Yuchun Tang, Yan-Qing Zhang, Nitesh V. Chawla, Sven Krasser. SVMs Modeling for Highly Imbalanced Classification. [14]. Qi Wang, ZhiHao Luo, JinCai Huang, YangHe Feng, and Zhong Liu. A Novel Ensemble Method for Imbalanced Data Learning: Bagging of Extrapolation- SMOTE SVM.