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