PHÂN LỚP DỮ LIỆU VỚI GIẢI THUẬT NEWTON SVM

Đỗ Thanh Nghị * , Phạm Nguyên Khang và Nguyễn Minh Trung

* Tác giả liên hệ (dtnghi@ctu.edu.vn)

Article Sidebar

Full Text: PDF

Ngày nhận bài: 19-02-2014
Ngày duyệt đăng: 30-06-2014
Ngày xuất bản: 12-10-2014
Title: Data classification using The Newton Support Vector Machine algorithm
Lượt xem
45
Downloads
26
Trích dẫn
Nghị, Đ. T., Khang, P. N., & Trung, N. M. (2014). PHÂN LỚP DỮ LIỆU VỚI GIẢI THUẬT NEWTON SVM. Tạp chí Khoa học Đại học cần Thơ, (32), 35-41. Truy vấn từ https://ctujsvn.ctu.edu.vn/index.php/ctujsvn/article/view/153
Số báo
Số. 32 (2014)
Chuyên mục
Công nghệ thông tin

Abstract

In this paper, we propose a new machine learning algorithm, called the ARC-x4 of finite Newton Support Vector Machine (NSVM) for classifying very large datasets on standard personal computers (PCs). SVM and kernel related methods have provided accurate classification models but their learning tasks usually need a quadratic programming with the requirement of large memory capacity and long time. We extend the recent NSVM proposed by Mangasarian for building a boosting-SVM algorithm. We have used the Sherman-Morrison-Woodbury formula to adapt the NSVM to process datasets with a very large number of dimensions. We have also applied the ARC-x4 approach proposed by Breiman to NSVM for classifying massive datasets with a very large number of datapoints as well as a very large number of dimensions. We have evaluated its performance on bio-medical datasets with a PC (2.4 GHz Pentium IV, 2 GB RAM).
Keywords: Newton support vector machine algorithm, adaptive reweighting and combining, ARC-x4, classifying large datasets

Tóm tắt

Chúng tôi trình bày trong bài viết một giải thuật học mới, ARC-x4 Newton support vector machine (ARC-x4-NSVM), cho phân loại tập dữ liệu lớn trên máy tính cá nhân. Máy học véc-tơ hỗ trợ (SVM) và phương pháp hàm nhân cung cấp mô hình phân lớp dữ liệu chính xác nhưng quá trình huấn luyện mô hình cần giải bài toán quy hoạch toàn phương rất mất thời gian và cần nhiều bộ nhớ. Chúng tôi đề xuất mở rộng giải thuật học NSVM của Mangasarian để xây dựng giải thuật cải tiến SVM. Chúng tôi đề xuất áp dụng công thức Sherman-Morrison-Woodbury vào giải thuật NSVM để có thể xử lý dữ liệu có số chiều rất lớn. Tiếp theo sau, chúng tôi kết hợp với phương pháp ARC-x4 của Breiman để xây dựng giải thuật ARC-x4-NSVM có thể phân loại dữ liệu với kích thước lớn về số phần tử cũng như số chiều. Chúng tôi đánh giá hiệu quả của giải thuật đề xuất trên tập dữ liệu y sinh học sử dụng máy tính cá nhân (2.4 GHz Pentium IV, 2 GB RAM).
Từ khóa: Giải thuật NSVM, trọng số thích nghi và kết hợp, ARC-x4, phân lớp dữ liệu lớn

Article Details

Tài liệu tham khảo

K. Bennett and C. Campbell. Support vector ma chines: Hype or hallelujah?. SIGKDD Explorations, 2(2): 1-13, 2000.

B. Boser, I. Guyon, and V. Vapnik. An training algorithm for optimal margin classifiers. ACM Annual Workshop on Computational Learning Theory, pages 144-152, 1992.

L. Breiman. Arcing classifiers. The annals of statistics, 26(3): 801–849, 1998.

C-C. Chang and C-J. Lin. Libsvm - a library for support vector machines. 2001-2014.

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, 2000.

Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. in EuroCOLT, 1995, pp. 23–37.

G. Golub and C. van Loan. Matrix Computations. The John Hopkins University Press,Baltimore, Maryland, 1996.

I. Guyon. Web page on svm applications. 1999-2014.

L. Jinyan and L. Huiqing. Kent ridge bio-medical dataset repository. 2002.

O. Mangasarian. A finite newton method for classification problems. Data Mining Institute Technical Report 01-11, Computer Sciences Department, University of Wisconsin, 2001.

J. Platt. Fast training of support vector machines using sequential minimal optimization. Advances in Kernel Methods - Support Vector Learning, pages 185-208, 1999.

F. Poulet and T-N. Do. Mining very large datasets with support vector machine algorithms. Enterprise Information Systems V, pages 177-184, 2004.

Liu H. Syed, N. and K. Sung. Incremental learning with support vector machines. ACM SIGKDD, 1999.

S. Tong and D. Koller. Support vector machine active learning with applications to text classification. ICML, pages 999-1006, 2000.

V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995.