zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Phương pháp phân loại dữ liệu bất cân bằng dựa trên tiền xử lý dữ liệu và SVM

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Báo xấu

2
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề xuất một phương pháp mới cho phép phân loại hiệu quả các tập dữ liệu bất cân bằng. Phương pháp này phân cụm lớp đa số dùng thuật toán k-means và lấy mẫu lên lớp thiểu số dùng kỹ thuật SMOTE.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp phân loại dữ liệu bất cân bằng dựa trên tiền xử lý dữ liệu và SVM

Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 PHƯƠNG PHÁP PHÂN LOẠI DỮ LIỆU BẤT CÂN BẰNG DỰA TRÊN TIỀN XỬ LÝ DỮ LIỆU VÀ SVM Nguyễn Mạnh Hiển Đại học Thủy lợi, email: hiennm@tlu.edu.vn 1. GIỚI THIỆU Tuy nhiên, thuật toán này không có giá trị sử Các thuật toán học máy chuẩn thường dụng vì nó không nhận ra được bất cứ mẫu nào không đạt được hiệu suất cao trên các tập dữ của lớp dương. Nguyên nhân của vấn đề này là liệu bất cân bằng, trong đó lớp dương (thiểu các thuật toán học chuẩn chỉ tập trung tối ưu số) có kích thước rất nhỏ so với lớp âm (đa hóa độ chính xác tổng thể trên toàn bộ tập huấn số). Bài báo đề xuất một phương pháp mới luyện, do đó chúng ít quan tâm đến lớp thiểu cho phép phân loại hiệu quả các tập dữ liệu số. Vì độ chính xác tổng thể không thể chỉ ra bất cân bằng. Phương pháp này phân cụm lớp hiệu suất phân loại tốt hay kém trên lớp thiểu đa số dùng thuật toán k-means và lấy mẫu lên số, bài báo này sẽ dùng một độ đo hiệu suất lớp thiểu số dùng kỹ thuật SMOTE. Bằng phù hợp hơn gọi là g-mean (xem ở phần sau). cách coi mỗi cụm dữ liệu của lớp đa số như Nhiều phương pháp đã được đề xuất để giải một lớp mới, chúng tôi biến đổi tập huấn quyết vấn đề bất cân bằng dữ liệu. Một số luyện hai lớp bất cân bằng ban đầu thành một phương pháp thay đổi các thuật toán học chuẩn tập huấn luyện đa lớp cân bằng hơn. Sau đó, để chúng làm việc tốt hơn trên dữ liệu bất cân chúng tôi huấn luyện các bộ phân loại SVM bằng, như căn chỉnh đường ranh giới quyết trên tập huấn luyện đa lớp thu được. Kết quả định của SVM [11]. Những nghiên cứu khác thực nghiệm cho thấy phương pháp đề xuất thực hiện tái cân bằng tập huấn luyện dùng các có hiệu suất phân loại đo bằng g-mean cao kỹ thuật lấy mẫu [8], bao gồm lấy mẫu lên lớp hơn các phương pháp khác. thiểu số và lấy mẫu xuống lớp đa số. 2. VẤN ĐỀ BẤT CÂN BẰNG DỮ LIỆU 3. PHƯƠNG PHÁP ĐỀ XUẤT Vấn đề phân loại dữ liệu bất cân bằng đã thu Trong một tập huấn luyện bất cân bằng, hút được sự chú ý của nhiều nhà nghiên cứu kể lớp đa số có kích thước lớn và có thể kèm từ đầu những năm 2000 [7]. Các tập dữ liệu bất theo cả cấu trúc dữ liệu phức tạp. Chúng tôi cân bằng xuất hiện phổ biến trong nhiều ứng dùng thuật toán k-means để chia lớp đa số dụng, như phát hiện giao dịch thẻ tín dụng gian thành các cụm nhỏ hơn, qua đó làm giảm lận [2], phát hiện vết dầu loang trong ảnh vệ mức độ bất cân bằng lớp cũng như làm giảm tinh [9] và phân loại văn bản [6]. Mặc dù vậy, độ phức tạp cấu trúc của lớp đa số. Các bước các thuật toán học chuẩn thường không đạt chính trong thuật toán đề xuất như sau: được hiệu suất mong muốn khi phân loại dữ  Bước 1: Ước lượng số cụm tối ưu k của liệu bất cân bằng. Xét ví dụ với một tập huấn lớp đa số dùng chỉ số DB (Davies- luyện gồm 1% dữ liệu thuộc về lớp dương và Bouldin) [10]. 99% dữ liệu còn lại thuộc về lớp âm. Một thuật  Bước 2: Phân chia lớp đa số thành k cụm toán học tầm thường có thể đạt được độ chính dùng thuật toán k-means. xác 99% trên tập dữ liệu này bằng cách xác  Bước 3: Lấy mẫu lên lớp thiểu số dùng kỹ định tất cả các mẫu dữ liệu thuộc về lớp âm. thuật SMOTE [4] cho đến khi lớp thiểu số 115
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 đạt kích thước trung bình của các cụm dữ được sinh ngẫu nhiên trên các đoạn thẳng nối liệu trong lớp đa số. một mẫu dữ liệu thiểu số  với các láng giềng  Bước 4: Biến đổi tập huấn luyện hai lớp gần nhất của  (trong cùng lớp thiểu số). ban đầu thành tập huấn luyện đa lớp, trong đó mỗi cụm đa số trở thành một lớp mới. 4. THỰC NGHIỆM  Bước 5: Huấn luyện các bộ phân loại Chúng tôi thực hiện các thí nghiệm đánh SVM trên tập huấn luyện đa lớp mới theo giá hiệu suất phân loại của phương pháp đề kiểu “một đấu một”, tức là huấn luyện một xuất trên sáu tập dữ liệu UCI [5]. Các tập dữ SVM riêng biệt cho mỗi cặp lớp. liệu này có số lớp biến thiên từ 2 đến 28.  Bước 6: Dự đoán nhãn lớp của các mẫu Chúng tôi đã chọn một lớp làm lớp thiểu số kiểm thử dùng kỹ thuật bỏ phiếu đa số. và ghép tất cả các lớp còn lại thành lớp đa số. Hình 1 minh họa ý tưởng của phương pháp Lớp thiểu số được chọn là 0 cho tập dữ liệu đề xuất với ba cụm dữ liệu của lớp đa số và Spect (chẩn đoán bệnh tim), 7 cho Glass (xác một lớp thiểu số được lấy mẫu lên. định loại kính), 0 cho Vowel (nhận dạng nguyên âm), 5 cho Yeast (định vị protein), 5 cho Abalone (dự đoán tuổi bào ngư) và 4 cho Page-blocks (phân loại khối trang). Tóm tắt của sáu tập dữ liệu này có trong Bảng 1. Bảng 1. Các tập dữ liệu bất cân bằng Tập dữ Số thuộc Số mẫu Tỉ số bất liệu tính dữ liệu cân bằng Spect 22 267 4 Glass 9 214 6 Vowel 10 990 10 Hình 1. Minh họa phương pháp đề xuất Yeast 8 1484 28 Trong bước 1 của thuật toán đề xuất, chỉ Abalone 8 4177 35 số DB cho phép đánh giá chất lượng phân cụm dữ liệu; chất lượng phân cụm tốt nếu độ Page- 10 5473 61 phân tán dữ liệu bên trong mỗi cụm nhỏ đồng blocks thời khoảng cách giữa các cụm lớn. Gọi Ci là Các thuộc tính trong các tập dữ liệu được cụm thứ i và zi là véc-tơ trung bình của nó. chuẩn hóa tuyến tính về khoảng [-1; 1]. Mỗi Khi đó, chỉ số DB được tính như sau: tập dữ liệu được chia ngẫu nhiên thành tập 1 k huấn luyện và tập kiểm thử theo tỉ lệ 1:1 sao DB  x cho giữ nguyên tỉ số bất cân bằng lớp. k i 1 Chúng tôi so sánh phương pháp đề xuất trong đó Sj và Sj là độ phân tán dữ liệu trong với ba phương pháp sau đây: các cụm Ci và Cj, còn dịj là khoảng cách giữa  SVM: Huấn luyện SVM chuẩn trên tập các cụm Ci và Cj, và được tính như sau: huấn luyện bất cân bằng.  CS-SVM (Cost-Sensitive SVM) [1]: Định 1 k Si   x  zi trọng số các mẫu đa số bằng 1 và các mẫu | Ci | x Ci thiểu số bằng tỉ số bất cân bằng lớp. dij  zi  z j  SMOTE: Dùng SMOTE với tỉ lệ lấy mẫu khác nhau tùy theo tỉ số bất cân bằng lớp; Trong bước 3 của thuật toán đề xuất, kỹ cụ thể là 200% cho Spect, 400% cho thuật SMOTE sinh ra các mẫu nhân tạo để bổ Glass, 500% cho Vowel và 1000% cho ba sung vào lớp thiểu số. Các mẫu nhân tạo tập dữ liệu còn lại. Tỉ lệ lấy mẫu N% có 116
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5 nghĩa là sinh ra lượng mẫu nhân tạo bằng bằng hơn. Kết quả thực nghiệm cho thấy N% lần lớp thiểu số ban đầu. phương pháp đề xuất có hiệu suất phân loại Đối với thuật toán k-means trong phương cao hơn các phương pháp khác. pháp đề xuất, chúng tôi thiết lập số bước lặp tối đa của nó bằng 100. Thuật toán k-means 6. TÀI LIỆU THAM KHẢO được lặp lại 10 lần với mỗi giá trị của k trong [1] R. Akbani, S. Kwek, and N. Japkowicz khoảng từ 2 đến n , với n là là kích thước (2004) “Applying support vector machines của lớp đa số, để tìm ra kết quả phân cụm tốt to imbalanced datasets,” ECML, pp. 39-50. nhất ứng với chỉ số DB nhỏ nhất [10]. [2] P. Chan and S. Stolfo (1998) “Toward Đối với việc huấn luyện SVM, chúng tôi scalable learning with non-uniform class and cost distributions: A case study in credit dùng thư viện LIBSVM [3] với các tham số card fraud detection,” KDD, pp. 164-168. ngầm định. Để giảm ảnh hưởng của yếu tố [3] C. Chang and C. Lin (2011) “LIBSVM: A ngẫu nhiên khi phân chia và lấy mẫu dữ liệu, library for support vector machines,” ACM chúng tôi lặp lại các thí nghiệm mười lần và TIST, vol. 2, no. 3, pp. 27:1-27:27. tính hiệu suất trung bình dùng độ đo g-mean: [4] N. Chawla, K. Bowyer, L. Hall, and W. g-mean:  acc   acc  Kegelmeyer (2002) “SMOTE: Synthetic minority over-sampling technique,” JAIR, trong đó acc+ và acc là độ chính xác phân vol. 16, pp. 321-357. loại trên các lớp thiểu số và đa số. [5] A. Frank and A. Asuncion (2010) “UCI Chúng tôi báo cáo kết quả thí nghiệm machine learning repository.” Available at trong Bảng 2, trong đó giá trị g-mean tốt http://archive.ics.uci.edu/ml. nhất cho mỗi tập dữ liệu được viết bằng chữ [6] E. Frank and R. Bouckaert (2006) “Naive in đậm. Kết quả cho thấy phương pháp đề Bayes for text classification with xuất có hiệu suất phân loại tốt nhất trên năm unbalanced classes,” PKDD, pp. 503-510. tập dữ liệu, chỉ kém phương pháp SMOTE [7] H. He and E. Garcia (2009) “Learning from trên một tập dữ liệu còn lại (Abalone) imbalanced data,” TKDE, vol. 21, no. 9, pp. nhưng với sai khác không lớn, chỉ 0,5 điểm 1263-1284. phần trăm. [8] J. Hulse, T. Khoshgoftaar, and A. Napolitano (2007) “Experimental Bảng 2. Hiệu suất phân loại (%) đo bằng perspectives on learning from imbalanced g-mean trên các tập dữ liệu bất cân bằng data,” ICML, pp. 935-942. [9] M. Kubat, R. Holte, and S. Matwin (1998) Tập dữ CS- PP đề SVM SMOTE “Machine learning for the detection of oil liệu SVM xuất spills in satellite radar images,” MLJ, vol. Spect 61,0 62,5 65,6 71,4 30, no. 2-3, pp. 195-215. Glass 88,4 90,1 86,5 91,0 [10] U. Maulik and S. Bandyopadhyay (2002) Vowel 70,3 73,6 42,2 “Performance evaluation of some clustering 87,7 algorithms and validity indices,” TPAMI, Yeast 17,5 33,2 57,8 65,5 vol. 24, no. 12, pp. 1650-1654. Abalone 1,3 3,2 62,9 62,4 [11] G. Wu and E. Chang (2005) “KBA: Kernel Page- boundary alignment considering blocks 90,7 89,6 91,2 91,9 imbalanced data distribution,” TKDE, vol. 17, no. 6, pp. 786-795. 5. KẾT LUẬN Bài báo đã giới thiệu một phương pháp phân loại dữ liệu bất cân bằng mới. Phương pháp này phân cụm lớp đa số và lấy mẫu lên lớp thiểu số để tạo ra tập huấn luyện mới cân 117

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.