- PHÂN LỚP DỮ LIỆU VỚI GIẢI THUẬT NEWTON SVM Đỗ Thanh Nghị 1 , Nguyễn Minh Trung 2 và Phạm Nguyên Khang 1. - Giải thuật Newton support vector machine, trọng số thích nghi và kết hợp, ARC- x4, phân lớp dữ liệu lớn. - 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).. - Mặc dù có được những ưu điểm kể trên, việc huấn luyện của giải thuật máy học SVM rất mất thời. - Độ phức tạp tối thiểu huấn luyện của giải thuật máy học SVM luôn là bậc 2 so với số lượng phần tử dữ liệu. - Do đó, cần thiết phải có những cải tiến để giải thuật học SVM có thể xử lý được các tập dữ liệu với kích thước lớn về số phần tử cũng như số chiều.. - Để cải tiến việc huấn luyện giải thuật máy học SVM cho các tập dữ liệu lớn. - Nghiên cứu của đã đề nghị xây dựng giải thuật học tăng truởng, chỉ nạp dữ liệu từng phần rồi cập nhật mô hình theo dữ liệu mà không cần nạp toàn bộ tập dữ liệu trong bộ nhớ.. - Công trình nghiên cứu của [13] đề nghị giải thuật song song trên mạng để cải thiện tốc độ huấn luyện. - Koller [14] đề nghị phương pháp chọn tập con dữ liệu thay vì phải học trên toàn bộ tập dữ liệu gốc.. - Trong bài viết này, chúng tôi muốn trình bày một giải thuật học mới, ARC-x4-NSVM, dùng cho phân loại các tập dữ liệu lớn trên máy tính cá nhân.. - Chúng tôi mở rộng giải thuật học NSVM của Mangasarian [10]. - Giải thuật học NSVM chỉ cần giải các hệ phương trình tuyến tính thay vì là bài toán quy hoạch toàn phương phức tạp hơn như giải thuật máy học SVM chuẩn. - Chúng tôi đã phát triển theo hướng thích ứng giải thuật NSVM cho phân loại dữ liệu có số chiều lớn thường gặp trong các vấn đề về phân loại văn bản hay trong sinh tin học.. - Sau đó, chúng tôi kết hợp với giải thuật ARC-x4 của Breiman trong [3] tiếp tục phát triển giải thuật ARC-x4-NSVM có thể phân loại được dữ liệu có kích thước lớn cả về số dòng và số lượng chiều. - Chúng tôi cũng tiến hành đánh giá hiệu quả dựa trên tiêu chí như thời gian huấn luyện và độ chính xác của giải thuật ARC-x4-NSVM sử dụng máy tính cá nhân (Pentium 2.4 GHz, 2 GB RAM, Linux). - Kết quả chạy thử nghiệm trên các tập dữ liệu lớn y sinh học [9] cho thấy giải thuật ARC-x4-NSVM của chúng tôi đề nghị có thời gian huấn học rất nhanh và cho độ chính xác cao khi so sánh với các giải thuật máy học SVM chuẩn như LibSVM [4].. - Phần 2 sẽ trình bày tóm tắt về giải thuật máy học. - ARC-x4-NSVM cho phân loại dữ liệu lớn. - 2 GIẢI THUẬT MÁY HỌC NSVM. - Cho m phần tử x 1 , x 2. - x m trong không gian n chiều, biểu diễn bởi ma trận A[mxn], có nhãn (lớp) của các phần tử là y 1 , y 2. - 2.1 Giải thuật SVM. - Giải thuật học SVM của Vapnik [15] tìm siêu phẳng tối ưu (xác định bởi véc-tơ pháp tuyến w và độ lệch của siêu phẳng b) dựa trên 2 siêu phẳng hỗ trợ của 2 lớp.. - Các phần tử A i của lớp +1 nằm bên phải của siêu phẳng hỗ trợ cho lớp +1, các phần tử A j lớp -1 nằm phía bên trái của siêu phẳng hỗ trợ cho lớp -1.. - e (3) trong đó e là véctơ cột mà tất cả các phần tử của nó đều bằng 1.. - Hình 1: Phân lớp tuyến tính với máy học SVM. - Việc tìm kiếm siêu phẳng tối ưu của giải thuật máy học SVM bằng với việc cực đại hóa lề ( lề càng lớn, mô hình phân lớp càng an toàn ) và cực tiểu hóa lỗi. - Giải thuật SVM dẫn đến bài toán quy hoạch toàn phương sau:. - Việc phân loại cho phần tử mới dựa trên siêu phẳng kết quả (w, b) được tính theo công thức sau:. - Độ phức tạp tính toán của bài toán quy hoạch toàn phương (5) tối thiểu là O(m 2 ) trong đó m là số lượng phần tử được dùng để huấn luyện. - Điều này làm cho giải thuật SVM không phù hợp với dữ liệu lớn.. - 2.2 Giải thuật Newton SVM (NSVM) Giải thuật NSVM do Mangasarian [10] đề nghị, cải biên bài toán SVM gốc bằng cách:. - Giải thuật SVM được viết lại dưới dạng (7):. - Giải thuật được mô tả như Bảng 1. - Mangasarian cũng chứng minh rằng dãy các giá trị {u i } của giải thuật lặp Newton hội tụ đến nghiệm tối ưu toàn cục. - Trong hầu hết các trường hợp kiểm thử trong thực tế thì giải thuật lặp Newton hội tụ đến nghiệm trong khoảng từ 5 đến 8 bước lặp. - Chú ý rằng, giải thuật lặp NSVM chỉ yêu cầu giải các hệ phương trình tuyến tính (10) có (n+1) biến (thay vì là bài toán quy hoạch toàn phương như giải thuật SVM chuẩn). - Do đó, nếu số chiều dữ liệu n trong bậc nhỏ hơn 100 thì thậm chí số phần tử dữ liệu m lên đến hàng triệu, giải thuật lặp NSVM có thể phân lớp chúng trong vài giây trên một máy tính cá nhân.. - Bảng 1: Giải thuật lặp NSVM. - 3 GIẢI THUẬT ARC-X4-NSVM CHO PHÂN LỚP TẬP DỮ LIỆU LỚN. - 3.1 Giải thuật NSVM cho dữ liệu có số chiều lớn nhưng ít phần tử. - Trong các ứng dụng như sinh tin học hay phân loại văn bản, các tập dữ liệu cần xử lý có số chiều n thường rất lớn (hơn 1000) nhưng có số phần tử m nhỏ (khoảng 50 đến 250 phần tử). - Với những tập dữ liệu dạng này, ma trận vuông (n+1)x(n+1) Hesse. - Để thích ứng giải thuật NSVM cho trường hợp này, chúng tôi áp dụng định lý Sherman- Morrison-Woodbury [7] để tính ma trận nghịch đảo. - Vì thế, độ phức tạp tính toán của NSVM lúc này chỉ phụ thuộc vào số lượng các phần tử chứ không phải số chiều. - Cách biến đổi lại bài toán như thế này có thể xử lý được các tập dữ liệu có số chiều rất lớn nhưng ít phần tử.. - 3.2 Giải thuật ARC-x4-NSVM cho dữ liệu có số phần tử và số chiều lớn. - Đối với việc phân lớp các tập dữ liệu vừa có số chiều lớn đồng thời số lượng phần tử cũng rất lớn (trên 10 4. - ví dụ như trong phân loại văn bản, sẽ có ít nhất 2 vấn đề cần giải quyết: thời gian huấn luyện tăng lên tỉ lệ thuận với số phần tử dùng để huấn luyện và bộ nhớ dùng để lưu trữ dữ liệu cũng phải tăng lên.. - Để giải quyết bài toán trong trường hợp dữ liệu có số chiều và số phần tử đều lớn, chúng tôi áp dụng cách tiếp cận boosting như Adaboost của Freund &. - Giải thuật Adaboost là một phương pháp tổng quát để cải tiến độ chính xác của các giải thuật phân lớp yếu. - Giải thuật lặp lại việc huấn luyện bằng các giải thuật phân lớp yếu t lần, mỗi lần trên một tập con được lấy mẫu từ tập dữ liệu dùng để huấn luyện. - Lần lặp sau tập trung huấn luyện trên các phần tử bị phân loại sai trong lần lặp trước đó.. - Để làm được điều này, mỗi phần tử được gán một - Đầu vào: tập dữ liệu huấn luyện, A[mxn] và D[mxm]. - Sau mỗi bước lặp các phần tử bị phân lớp sai sẽ được tăng trọng số lên. - Việc phân loại phần tử mới sử dụng kết quả bình chọn trọng số từ t bộ phân lớp yếu. - ARC-x4 cũng tương tự như Adaboost ngoại trừ ARC-x4 tập trung huấn luyện trên các phần tử bị phân loại sai trong tất cả các lần lặp trước đó và việc phân loại phần tử mới dựa trên kết quả bình chọn số đông (không có trọng số).. - Chúng ta có thể xem NSVM như một bộ phân lớp yếu vì việc huấn luyện trong từng bước lặp chỉ thực hiện trên tập con của tập dữ liệu huấn luyện.. - Với tập dữ liệu có số phần tử lớn, số chiều nhỏ hơn 100, thì sử dụng NSVM như trong (10). - Với dữ liệu có số chiều lớn hay đồng thời lớn về số chiều và số phần tử, boosting của NSVM vẫn có thể giải quyết được nhanh chóng vì mặc dù số chiều lớn nhưng trong mỗi lần lặp số lượng phần tử để huấn luyện sẽ nhỏ nên có thể áp dụng (15) để giải.. - Chú ý rằng thời gian huấn luyện NSVM nhanh. - Chúng tôi đã xây dựng giải thuật ARC-x4- NSVM để giải quyết bài toán dữ liệu lớn. - Để tiến hành đánh giá hiệu quả của giải thuật ARC-x4-NSVM cho phân lớp các tập dữ liệu lớn, chúng tôi đã cài đặt giải thuật bằng ngôn ngữ lập trình C/C. - Ngoài ra, chúng tôi cũng cần so sánh hiệu quả về thời gian và độ chính xác phân lớp của giải thuật đề xuất ARC-x4-NSVM với một giải thuật SVM chuẩn, được sử dụng phổ biến trong cộng đồng máy học là LibSVM [4]. - Tất cả các giải thuật đều được thực hiện trên một máy tính cá nhân (2.4 GHz Pentium IV, 2GB RAM) chạy hệ điều hành Linux.. - Bảng 2: Mô tả các tập dữ liệu y sinh học. - Tập dữ liệu Số lớp Số phần tử Số chiều Nghi thức kiểm tra. - Các tập dữ liệu thực nghiệm được lấy về từ website của Jinyan &. - Đây là các tập dữ liệu y sinh học, có số chiều lớn, bậc hàng ngàn và số phần tử từ vài chục đến hàng chục ngàn. - Xét tập dữ liệu như Ovarian Cancer, với 253 phần tử, 15154 chiều. - Nếu sử dụng giải thuật gốc NSVM của Mangasarian [10], mỗi bước lặp phải lấy nghịch đảo ma trận kích thước 15155x15155 ((n+1)x(n+1. - Trong khi giải thuật cải tiến của chúng tôi đề xuất ở mỗi bước lặp thực hiện nghịch đảo ma trận 253x253 (mxm) với độ phức tạp tương ứng là 253 3 . - Qua đây có thể thấy rằng giải thuật cải tiến hiệu quả so với giải thuật gốc trong trường hợp dữ liệu y sinh học.. - Bảng 2 mô tả các tập dữ liệu thực nghiệm. - Cột cuối của bảng 2 mô tả nghi thức kiểm tra của các giải thuật. - Ba tập dữ liệu ALL-AML Leukemia, Breast Cancer, Lung Cancer đều được chia thành tập huấn luyện (trn) và tập kiểm tra (tst). - Đối với các tập dữ liệu này, chúng ta cần huấn luyện mô hình học sử dụng tập huấn luyện, tính thời gian huấn luyện và dùng tập kiểm tra để tính độ chính xác cho phân lớp. - Tập Ovarian Cancer thì sử dụng nghi thức leave-1-out, lặp lại 253 lần huấn luyện và kiểm tra, mỗi lần chỉ lấy 1 phần tử làm tập kiểm tra độ chính xác và 252 phần tử còn lại làm tập huấn luyện để tính thời gian huấn luyện, cuối cùng tính trung bình thời gian huấn luyện và độ chính xác.. - Tập Translation Initiation Sites thì sử dụng nghi thức hold-out, lấy ngẫu nhiên 2/3 tập dữ liệu gốc làm tập huấn luyện để tính thời gian huấn luyện mô hình học và 1/3 còn lại làm tập kiểm tra để tính độ chính xác khi phân lớp.. - Bảng 3: Kết quả phân lớp dữ liệu y sinh học. - Tập dữ liệu LibSVM ARC-x4-NSVM. - phân lớp. - luyện (giây) Độ chính xác phân lớp. - Giải thuật ARC-x4-NSVM xây dựng 30 mô hình NSVM, mỗi mô hình được xây dựng trên mẫu 30% tập dữ liệu gốc. - Hình 2, 3 cung cấp đồ thị so sánh về thời gian huấn luyện và độ chính xác phân lớp.. - Hình 2: So sánh thời gian huấn luyện. - Hình 3: So sánh độ chính xác phân lớp So sánh kết quả cho thấy được giải thuật ARC-. - phân lớp của ARC-x4-NSVM có thể xem là tương đương với LibSVM.. - Chúng tôi vừa trình bày giải thuật máy học mới ARC-x4-NSVM cho phân lớp tập dữ liệu lớn trên máy tính cá nhân. - Chúng tôi đề xuất mở rộng giải thuật NSVM của Mangasarian để xây dựng giải thuật ARC-x4-NSVM. - Chúng tôi đã áp dụng định lý Sherman-Morrison-Woodbury để thích ứng giải thuật NSVM khi phân lớp dữ liệu có số chiều lớn nhưng số phần tử nhỏ, thường gặp trong ứng dụng sinh tin học, phân lớp văn bản. - Đề xuất áp dụng ARC-x4 lên NSVM cho phép giải thuật mới có thể phân lớp nhanh dữ liệu có đồng thời số phần tử và số chiều cùng lớn trên máy tính cá nhân. - Kết quả thực nghiệm trên các tập dữ liệu y sinh học cho thấy rằng giải thuật ARC-x4-NSVM học nhanh, phân lớp chính xác khi so sánh với giải thuật LibSVM.. - Trong tương lai gần, chúng tôi phát triển giải thuật song song cho phép tăng tốc quá trình huấn luyện và phân lớp của giải thuật SVM.