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

LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA<br /> <br /> <br /> Phương pháp DEC-SVM phân lớp dữ liệu mất cân bằng<br /> Imbalanced data classification based on DEC-SVM<br /> 1 1 2<br /> Phạm Thị Hường , Phạm Văn Kiên , Đỗ Ngọc Quỳnh<br /> Email: ngocquynh.ydhn@gmail.com<br /> 1<br /> Trường Đại học Sao Đỏ<br /> 2<br /> Trường Cao đẳng Y Dược Hà Nội<br /> Ngày nhận bài: 21/8/2018<br /> Ngày nhận bài sửa sau phản biện: 29/10/2018<br /> Ngày chấp nhận đăng: 27/12/2018<br /> Tóm tắt<br /> Trong bài báo 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<br /> 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<br /> 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.<br /> Từ khóa: Phân cụm; phân lớp; dữ liệu mất cân bằng; SVM.<br /> Abstract<br /> In this article, authors study the DEC-SVM algorithm that modulates data by adding elements to the<br /> minority class, and then uses clustering techniques to eliminate redundant elements. Empirical evidence<br /> show that the DEC-SVM is capable of enhancing class efficiency for imbalanced data sets.<br /> Keywords: Clustering; classification; imbalanced data; SVM.<br /> <br /> <br /> 1. GIỚI THIỆU CHUNG Đối với các bộ dữ liệu mất cân bằng, các bộ phân<br /> lớp chuẩn thường có xu hướng thiên vị đối với lớp<br /> Ngày nay, khi vấn đề khai thác và xử lý thông tin<br /> đa số và bỏ qua lớp thiểu số (xử lý chúng như là<br /> ngày càng được chú trọng, kỹ thuật phân lớp dữ<br /> nhiễu) [4]. Vì vậy, khi áp dụng các giải thuật phân<br /> liệu đã góp phần hữu hiệu giúp con người khai<br /> lớp truyền thống chưa thể xây dựng được một bộ<br /> thác một cách có hiệu quả khối dữ liệu mà họ<br /> phân lớp tốt. Việc phân loại sai các mẫu thuộc lớp<br /> đang nắm giữ. Tuy nhiên, dữ liệu thu thập được<br /> thiểu số có thể gây nên những tổn thất lớn đối với<br /> trong thực tế ngày càng xuất hiện nhiều các bộ<br /> các lĩnh vực thực tế. Để giải quyết vấn đề về phân<br /> dữ liệu mất cân bằng, nghĩa là trong tập dữ liệu<br /> lớp đối với các bộ dữ liệu mất cân bằng, hiện nay<br /> có sự chênh lệch lớn về số lượng các phần tử<br /> có nhiều phương pháp khác nhau, trong đó, có hai<br /> giữa các lớp. Các bộ dữ liệu trong nhiều ứng dụng<br /> hướng tiếp cận chính: tiếp cận ở mức độ dữ liệu<br /> thực tế như phát hiện các giao dịch gian lận, phát<br /> và hướng tiếp cận ở mức độ thuật toán.<br /> hiện xâm nhập mạng, dự đoán rủi ro trong quản<br /> lý, chẩn đoán y khoa,…, đều là các bộ dữ liệu mất Trong [12], tác giả cải tiến thuật toán sinh thêm<br /> cân bằng mà trong đó, lớp người ta cần quan tâm mẫu nhân tạo lớp thiểu số (SMOTE) bằng cách<br /> lại chiếm tỉ lệ rất nhỏ so với lớp còn lại. kết hợp thuật toán nhúng tuyến tính cục bộ (locally<br /> linear embedding - LLE). Thuật toán LLE ánh xạ<br /> Sự chênh lệch về số lượng giữa lớp đa số và lớp<br /> dữ liệu có số chiều cao vào một không gian với số<br /> thiểu số làm cho việc phân lớp đúng các mẫu<br /> chiều thấp hơn. Sau đó, các mẫu nhân tạo sinh<br /> thuộc lớp thiểu số bị giảm hiệu quả. Tỷ lệ mất<br /> ra sẽ được ánh xạ trở lại không gian mẫu ban<br /> cân bằng của tập dữ liệu càng cao thì việc phát<br /> đầu thông qua LLE. Từ bộ dữ liệu đã điều chỉnh,<br /> hiện đúng các mẫu của lớp thiểu số càng khó<br /> thực nghiệm trên 3 bộ dữ liệu với ba kỹ thuật phân<br /> khăn. Trong các ứng dụng thực tế, tỷ lệ mất cân<br /> lớp Bayes, K-NN, SVM cho thấy kỹ thuật SVM<br /> bằng có thể là 1:100, 1:1000, thậm chí có thể hơn<br /> có độ chính xác theo tiêu chí AUC cao nhất với<br /> [11]. Vì thế, phân lớp dữ liệu mất cân bằng đã và<br /> trung bình là 76.5%. Trong [13], tác giả trình bày<br /> đang là bài toán được các nhà khoa học đặc biệt<br /> giải thuật GSVM -RU (Granular Support Vector<br /> quan tâm.<br /> Machines Repetitive Undersampling) sử dụng<br /> SVM cho việc lấy mẫu. Với những mẫu quan trọng<br /> Người phản biện: 1. GS.TSKH. Thân Ngọc Hoàn trong quá trình phân lớp, giảm thiểu mất thông tin<br /> 2. TS. Trần Trọng Hiếu các mẫu đa số khi loại bỏ và tối đa mẫu thiểu số<br /> <br /> <br /> Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 17<br />  NGHIÊN CỨU KHOA HỌC<br /> <br /> <br /> khi làm sạch dữ liệu trong quá trình lấy mẫu để nhân tạo. Sinh ngẫu nhiên các phần tử ở lớp thiểu<br /> chỉ giữ lại các mẫu cần thiết và các mẫu khác có số là phương pháp đơn giản nhất nhằm cân bằng<br /> thể được loại bỏ một cách an toàn mà không ảnh phân lớp thông qua việc nhân bản ngẫu nhiên các<br /> hưởng đến phân loại. Việc trích chọn vectơ ít hơn, mẫu lớp thiểu số. Ý tưởng là lựa chọn ngẫu nhiên<br /> do đó tăng tốc độ dự đoán. Kết quả thực nghiệm các mẫu thuộc lớp thiểu số và nhân bản chúng<br /> với các đánh giá G-Mean (85.2%), AUC (92.4%), tạo ra mẫu mới giống hệt chúng. Hình 1 minh họa<br /> F-Measure (66.5%). Trong [14], tác giả đề xuất<br /> phương pháp sinh thêm phần tử cho lớp thiểu số.<br /> phương pháp Bagging of Extrapolation Borderline-<br /> SMOTE SVMs (BEBS) sử dụng phương pháp lấy<br /> mẫu thích nghi Extrapolation Borderline-SMOTE<br /> và tập hợp bootstrapping vào tập dữ liệu không<br /> cân bằng ban đầu. Khi sử dụng SVM, ranh giới<br /> quyết định nghiêng về phía các mẫu thiểu số và<br /> có thể được thay đổi dựa vào các mẫu nhân bản.<br /> Kết quả thực nghiệm đánh giá dựa trên tiêu chí<br /> G-Mean đạt 76.2%. Hình 1. Sinh ngẫu nhiên phần tử lớp thiểu số<br /> <br /> Tuy nhiên, với đặc thù của các tập dữ liệu hầu hết Phương pháp sinh thêm mẫu nhân tạo lớp thiểu<br /> không giống nhau, không có giải pháp nào là hữu số SMOTE (Synthetic Minority Over-sampling<br /> hiệu cho mọi tập dữ liệu. Trong bài báo này, chúng Technique) như sau: Với mỗi mẫu thuộc lớp thiểu<br /> tôi đề xuất thuật toán DEC-SVM để phân lớp dữ số, tìm láng giềng gần nhất của nó trong lớp thiểu<br /> liệu. Cụ thể, nghiên cứu thuật toán điều chỉnh dữ số, lựa chọn ngẫu nhiên các láng giềng gần nhất<br /> liệu cho bài toán phân lớp dữ liệu mất cân bằng (hoặc tất cả láng giềng) tùy theo số lượng mẫu<br /> – thuật toán DEC (a novel Differential Evolution cần sinh thêm. Mẫu nhân tạo sẽ được sinh ra theo<br /> Clustering hybrid resampling) được công bố vào<br /> cách sau: lấy độ lệch giữa vector thuộc tính của<br /> năm 2010 của nhóm tác giả Leichen Chen, Zhihua<br /> mẫu đang xét và láng giềng của nó nhân với một<br /> Cai, Lu Chen và Qiong Gu [1]. Thuật toán này là<br /> số ngẫu nhiên trong khoảng (0, 1) rồi cộng kết quả<br /> sự kết hợp giữa phương pháp sinh thêm phần tử<br /> cho lớp thiểu số và sử dụng kỹ thuật phân cụm, thu được với vector thuộc tính của mẫu đang xét.<br /> K-means để loại bỏ bớt phần tử dư thừa, nhiễu Kết quả cuối cùng chính là vector thuộc tính của<br /> trong dữ liệu. Với mỗi mẫu thuộc lớp thiểu số, tạo mẫu nhân tạo, nhãn của mẫu nhân tạo sẽ được<br /> ra một mẫu đột biến từ hai trong số những láng gán là nhãn của lớp thiểu số [9] và được minh họa<br /> giềng gần nó nhất, sau đó sử dụng thuật toán di trong hình 2.<br /> truyền để sinh thêm phần tử cho lớp thiểu số từ<br /> mẫu thiểu số ban đầu và mẫu đột biến mới tạo ra.<br /> Sau khi điều chỉnh dữ liệu bằng thuật toán DEC,<br /> chúng tôi sử dụng kỹ thuật SVM để phân lớp cho<br /> tập dữ liệu huấn luyện mới để tạo ra mô hình phân Hình 2. Minh họa sinh thêm phần tử nhân tạo<br /> lớp. Kết quả cho thấy, khi sử dụng DEC-SVM thì bằng thuật toán SMOTE<br /> hiệu quả phân lớp các bộ dữ liệu mất cân bằng<br /> cao hơn. Giả mã của thuật toán SMOTE [9]:<br /> <br /> 2. PHƯƠNG PHÁP DEC-SVM CHO BÀI TOÁN SMOTE (N, T, k)<br /> PHÂN LỚP DỮ LIỆU MẤT CÂN BẰNG<br /> Input: Số mẫu lớp thiểu số T; tổng số SMOTE<br /> 2.1. Hướng tiếp cận ở mức độ dữ liệu N%, số láng giềng gần nhất k.<br /> Tiếp cận ở mức độ dữ liệu mục đích là điều chỉnh Output: (N/100)*T mẫu thiểu số nhân tạo<br /> tỉ lệ mất cân bằng giữa hai lớp trong bộ dữ liệu, cụ<br /> thể sử dụng các hình thức lấy mẫu: sinh thêm các 1. (Nếu N nhỏ hơn 100%, chọn ngẫu nhiên các<br /> phần tử lớp thiểu số (sinh ngẫu nhiên, sinh thêm mẫu lớp thiểu số mà chỉ một phần trăm của chúng<br /> phần tử nhân tạo,…), loại bỏ các phần tử lớp đa sẽ được SMOTE)<br /> số, hoặc kết hợp cả hai phương pháp trên. 2. IF N< 100<br /> 2.1.1. Sinh thêm phần tử lớp thiểu số<br /> 3. Then chọn ngẫu nhiên T mẫu lớp thiểu số<br /> Có nhiều phương pháp sinh thêm phần tử cho lớp<br /> 4. T = (N/100)*T<br /> thiểu số như: sinh ngẫu nhiên phần tử lớp thiểu<br /> số, lựa chọn phần tử lớp thiểu số, sinh thêm mẫu 5. N = 100<br /> <br /> <br /> 18 Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018<br />  LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA<br /> <br /> <br /> 6. Endif 3. For attr←1 to numattrs<br /> 7. N = (int) (N/100) (Số luợng SMOTE được giả 4. Tính dif=Sample[nnarray[n,n]][attr]-Sample[i][attr]<br /> định là bội số của 100)<br /> 5. Tính gap = một số ngẫu nhiên giữa 0 và 1<br /> 8. k = số láng giềng gần nhất<br /> 6. Synthentic[newindex][attr]=Sample[i][ attr]+gap*dif<br /> 9. numattrs = số thuộc tính<br /> 7. Endfor<br /> 10. sample [ ][ ]: mảng các mẫu thiểu số ban đầu<br /> 8. ++<br /> 11. newindex: chỉ số của mẫu nhân tạo được tạo<br /> 9. N=N-1<br /> ra, khởi tạo là 0<br /> 10. Endwhile<br /> 12. synthetic [ ][ ]: mảng các mẫu nhân tạo<br /> 11. Return (kết thúc hàm Populate)<br /> (tính k láng giềng gần nhất cho mỗi mẫu lớp<br /> thiểu số.) Ngoài ra còn có một số thuật toán được cải tiến<br /> 13. For to T từ thuật toán SMOTE như: Borderline-SMOTE [6],<br /> Safe-level SMOTE [3] cũng đem lại những hiệu<br /> 14. Tính k láng giềng gần nhất cho i và lưu vào<br /> quả nhất định hỗ trợ quá trình phân lớp cho các bộ<br /> mảng nnarray.<br /> dữ liệu mất cân bằng.<br /> 15. Populate (N, i, nnarray)<br /> 2.1.2. Loại bỏ phần tử lớp đa số<br /> 16. Endfor<br /> Là phương pháp điều chỉnh phân bố dữ liệu bằng<br /> Populate (N, i, nnarray) (hàm sinh các mẫu nhân tạo) cách giảm bớt số lượng phần tử lớp đa số. Loại<br /> Input: Số mẫu cần sinh thêm N, mỗi mẫu lớp bỏ một cách ngẫu nhiên các mẫu thuộc lớp đa số<br /> thiểu số i, mảng các láng giềng gần nhất nnarray. là đơn giản nhất. Phương pháp này thực hiện loại<br /> Output: Vector thuộc tính của mẫu nhân tạo bỏ ngẫu nhiên phần tử thuộc lớp đa số trong tập<br /> huấn luyện (hình 3a) cho tới khi có được tỷ lệ phù<br /> 1. While N≠0<br /> hợp giữa hai lớp. Với lý do này, số lượng phần tử<br /> 2. Chọn ngẫu nhiên một số nn giữa 1 và k trong tập huấn luyện giảm đáng kể (hình 3b).<br /> <br /> M<br /> M u thi u s<br /> <br /> (a) (b )<br /> <br /> Hình 3. Minh họa loại bỏ phần tử lớp đa số<br /> Tuy nhiên, việc loại bỏ mẫu có thể sẽ làm hao mới. Hay đối với phương pháp phân lớp SVM, có<br /> hụt thông tin và có khả năng làm mất đi những thể sử dụng hằng số phạt khác nhau cho các lớp<br /> mẫu mang thông tin quan trọng cho quá trình hoặc điều chỉnh ranh giới lớp dựa trên ý tưởng<br /> xây dựng mô hình phân lớp. Khắc phục hạn chế liên hết hạt nhân [11].<br /> của phương pháp trên, một số phương pháp loại<br /> bỏ mẫu theo mục tiêu được đề xuất như: Tomek Đối với phương pháp phân lớp K-NN, có thể đề<br /> links, One-side Selection, Neighborhood Cleaning xuất một hàm khoảng cách có trọng số. Ý tưởng<br /> Rule [7]. này nhằm bù cho sự mất cân bằng trong mẫu<br /> huấn luyện mà không làm thay đổi sự phân lớp.<br /> 2.2. Hướng tiếp cận ở mức độ thuật toán<br /> 2.3. Thuật toán DEC-SVM cho bài toán phân<br /> Tiếp cận ở mức độ thuật toán nghĩa là điều chỉnh lớp dữ liệu mất cân bằng<br /> các thuật toán phân lớp để tăng cường độ chính<br /> Phương pháp sinh thêm phần tử nhân tạo cho<br /> xác khi phân lớp đối với dữ liệu mất cân bằng.<br /> lớp thiểu số là phương pháp hiệu quả cho các bài<br /> Chiến lược chung để đối phó với vấn đề mất cân<br /> toán phân lớp dữ liệu mất cân bằng. Tuy nhiên,<br /> bằng trong các bộ dữ liệu là lựa chọn một khuynh<br /> trong nhiều trường hợp, việc sinh thêm mẫu có<br /> hướng quy nạp thích hợp.<br /> thể sẽ tạo ra những mẫu dư thừa hoặc nhiễu làm<br /> Ví dụ như đối với phương pháp cây quyết định, ảnh hưởng tới hiệu quả phân lớp. Thuật toán<br /> cách tiếp cận có thể là điều chỉnh dự đoán xác DEC-SVM dựa trên việc tạo ra phần tử nhân tạo<br /> xuất ở lá, hoặc phát triển phương pháp cắt tỉa trên lớp thiểu số nhằm giảm tỷ lệ mất cân bằng,<br /> <br /> <br /> Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018 19<br />  NGHIÊN CỨU KHOA HỌC<br /> <br /> <br /> sau đó sử dụng kỹ thuật phân cụm cho tập dữ liệu xi,j nếu rand(j)>CR và j ≠ rand(s) (2)<br /> để loại bỏ những mẫu dư thừa hoặc nhiễu. Bằng xnew,j=<br /> xmu,j nếu rand(j) ≤ CR hoặc j=rand(s)<br /> cách lấy mẫu kết hợp với làm sạch dữ liệu, các<br /> mẫu hữu ích vẫn được giữ lại và nâng cao hiệu trong đó: xi,j là thuộc tính thứ j của mẫu thứ i;<br /> quả phân lớp. CR là hằng số crossover được lựa chọn ngẫu<br /> 2.3.1. Điều chỉnh dữ liệu bằng thuật toán DE nhiên trong [0, 1] và được xác định trước bởi<br /> người dùng;<br /> Với thuật toán SMOTE, mẫu mới sẽ được sinh ra<br /> rand(j) là giá trị được lựa chọn ngẫu nhiên trong<br /> từ một mẫu positive (mẫu lớp thiểu số) ban đầu và<br /> khoảng [0, 1].<br /> một trong những láng giềng của nó. Với nền tảng<br /> là thuật toán MOTE, tuy nhiên, trong thuật toán Giá trị của biến rand(s) là chỉ số của các thuộc tính<br /> được lấy một cách ngẫu nhiên, đảm bảo rằng mẫu<br /> DE, từ hai trong số các láng giềng gần nhất của<br /> mới sinh ra sẽ có ít nhất một thuộc tính từ mẫu<br /> một mẫu positive sẽ tạo ra một mẫu “đột biến”, và<br /> đột biến.<br /> mẫu mới được sinh ra bằng cách lai ghép chéo<br /> Số mẫu nhân tạo được tạo ra đúng bằng số mẫu<br /> mẫu đột biến này và mẫu positive ban đầu.<br /> positive ban đầu, và các mẫu nhân tạo này được<br /> 2.3.1.1. Đột biến gán nhãn là positive. Tùy thuộc vào số lượng<br /> mẫu positive cần lấy, lặp lại các bước đột biến và<br /> Trong tập dữ liệu huấn luyện, đầu tiên chọn ngẫu<br /> crossover cho dữ liệu huấn luyện.<br /> nhiên một mẫu positive và tìm k láng giềng gần<br /> nhất của nó, sau đó chọn ngẫu nhiên hai láng 2.3.2. Kỹ thuật làm sạch dữ liệu sử dụng<br /> giềng trong láng giềng đó: x n1 và x n 2 . Một phân cụm<br /> <br /> mẫu đột biến x mu sẽ được tạo ra bằng cách Sau khi thực hiện thuật toán DE, dữ liệu thu được<br /> đã được cải thiện hơn về tỉ lệ giữa hai lớp. Tuy<br /> sử dụng công thức (1) với rand(0,1) là<br /> nhiên, không loại trừ khả năng sinh ra những mẫu<br /> hằng số ngẫu nhiên trong khoảng [0,1]:<br /> dư thừa hoặc nhiễu. Để khắc phục, ta sẽ sử dụng<br /> x m u = x i + r a nd(0,1) × (x n 1 -x n 2 ) (1) kỹ thuật phân cụm để phân cụm cho tập dữ liệu<br /> 2.3.1.2. Crossover với mục đích loại bỏ những mẫu không cần thiết.<br /> <br /> Qua bước đột biến, ta tạo ra số lượng mẫu đột Chẳng hạn ta thu được các cụm và giả sử được<br /> đặt tên là A, B, C, D, E, F như hình 4. Trong đó,<br /> biến đúng bằng số lượng mẫu positive ban đầu<br /> một số cụm chứa tất cả các mẫu có cùng nhãn<br /> trong tập dữ liệu huấn luyện. Ở bước này, ta sẽ sử lớp (các cụm C, D, E và F), những cụm khác chứa<br /> dụng các mẫu đột biến cùng với các mẫu positive các mẫu có nhãn lớp khác nhau (cụm A và B), dự<br /> ban đầu để tạo ra mẫu nhân tạo mới. Cụ thể, các đoán rằng có thể siêu phẳng của SVM [2, 8] sẽ đi<br /> mẫu mới sẽ được hình thành dựa theo (2): qua các cụm này.<br /> <br /> <br /> <br /> <br /> Hình 4. Minh họa phân cụm tập dữ liệu mất cân bằng<br /> <br /> Nếu như tất cả các mẫu trong một cụm đều có có chứa tất cả các mẫu negative, ta làm như sau:<br /> cùng một nhãn lớp (tức là hoặc cùng là positive ‒ Xác định ngưỡng tương đồng trong (0,1]<br /> hoặc cùng là negative), ta sẽ tiến hành loại bỏ<br /> những mẫu dư thừa hoặc nhiễu. Giả sử với cụm F ‒ Tính theo công thức (3):<br /> <br /> <br /> 20 Tạp chí Nghiên cứu khoa học - Đại học Sao Đỏ, ISSN 1859-4190 Số 4(63).2018<br />  LIÊN NGÀNH ĐIỆN - ĐIỆN TỬ - TỰ ĐỘNG HÓA<br /> <br /> thứ i; xik là thuộc tính thứ k của mẫu I; Sij là độ<br /> (3)<br /> tương đồng giữa xi và xj<br /> ‒ Tìm mẫu trung tâm gần nhất 2.3.3. Thuật toán<br /> ‒ Tính độ tương đồng Sic giữa mỗi mẫu và Phương pháp sinh thêm phần tử cho lớp thiểu số<br /> theo (4). Nếu Sic lớn hơn ngưỡng tương đồng<br /> bằng thuật toán DE kết hợp với kỹ thuật loại bỏ<br /> thì xi sẽ bị loại khỏi F.<br /> phần tử dư thừa (nhiễu) bằng phân cụm tạo nên<br /> thuật toán điều chỉnh dữ liệu DEC. Sau khi điều<br /> chỉnh dữ liệu bằng thuật toán DEC, sử dụng kỹ<br /> thuật SVM để phân lớp cho bộ dữ liệu tạo nên mô<br /> Ngưỡng tương đồng càng nhỏ thì càng nhiều mẫu hình phân lớp. Quá trình thực hiện phân lớp dữ<br /> bị loại bỏ. Trong đó: ni là số lượng mẫu trong cụm liệu được mô tả trong hình 5.<br /> <br /> <br /> <br /> <br /> Hình 5. Quá trình phân lớp dữ liệu bằng thuật toán DEC-SVM<br /> <br /> Thuật toán DEC-SVM được mô tả như sau: 1.4. Tạo ra mẫu thiểu số mới từ xi và mẫu đột biến<br /> <br /> DEC-SVM (N, m, k, s, T) của nó theo x m u công thức:<br /> <br /> Input: Số mẫu lớp thiểu số