ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG VĂN TRÌU TÌM HIỂU PHƯƠNG PHÁP TÌM THUỘC TÍNH TỐI ƯU NHẰM TĂNG HIỆU QUẢ PHÂN TÍCH TRONG PHÂN TÍCH DỮ LIỆU LỚN LUẬN VĂN THẠC SỸ - NGÀNH CÔNG NGHỆ THÔNG TIN ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG VĂN TRÌU TÌM HIỂU PHƯƠNG PHÁP TÌM THUỘC TÍNH TỐI ƯU NHẰM TĂNG HIỆU QUẢ PHÂN TÍCH TRONG PHÂN TÍCH DỮ LIỆU LỚN Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã Số: 60480103 LUẬN VĂN THẠC SỸ - NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGUYỄN HÀ NAM HÀ NỘI - 2015 Lời cam đoan Tôi xin cam đoan luận văn “ Tìm hiểu phương pháp tìm thuộc tính tối ưu nhằm tăng hiệu phân tích phân tích liệu lớn ” công trình nghiên cứu riêng Các số liệu, kết trình bày luận văn hoàn toàn trung thực Tôi trích dẫn đầy đủ tài liệu tham khảo, công trình nghiên cứu liên quan Ngoại trừ tài liệu tham khảo này, luận văn hoàn toàn công việc riêng Luận văn hoàn thành thời gian học viên Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội Hà Nội, ngày 31 tháng 08 năm 2015 Học viên Hoàng Văn Trìu Lời cảm ơn Lời đầu tiên, xin gửi lời cảm ơn lòng biết ơn sâu sắc tới PGS.TS Nguyễn Hà Nam tận tình hướng dẫn suốt trình thực luận văn tốt nghiệp Tôi chân thành cảm ơn anh nghiên cứu sinh Hà Văn Sang anh nghiên cứu sinh Lữ Đăng Nhạc tận tình bảo trình thực luận văn Tôi cảm ơn người bạn nhóm nghiên cứu PGS.TS Nguyễn Hà Nam bên chia sẻ kinh nghiệm học tập sống Tôi chân thành cảm ơn thầy, cô tạo cho điều kiện thuận lợi để học tập nghiên cứu trường Đại học Công Nghệ Tôi xin gửi lời cảm ơn tới bạn lớp cao học K19 ủng hộ, khuyến khích suốt trình học tập trường Tôi xin chân thành cảm ơn! Hà Nội, ngày 31 tháng 08 năm 2015 Học viên Hoàng Văn Trìu Mục lục Giới thiệu Chương Giới thiệu Khai phá liệu 1.1 Tổng quan Khai phá liệu 1.2 Tổng quan trích chọn thuộc tính 2.3 Kết luận Chương Họ thuật toán k-Láng giềng gần Thuật toán Di truyền 2.1 Họ thuật toán k-Láng giềng gần 2.1.1 Khái niệm 2.1.2 Thuật toán Láng giềng gần (NN) 2.1.3 Thuật toán k-Láng giềng gần (kNN) 2.1.4 Thuật toán Đánh trọng số k-Láng giềng gần (WkNN) 10 2.1.5 Thuật toán Hàm nhân k-Láng giềng gần (Kernel k-NN) 15 2.2 Thuật toán Di truyền (GA) 18 2.2.1 Giới thiệu 18 2.2.2 Thuật toán Di truyền (GA) 19 2.3 Kết luận 24 Chương Mô hình GA_Kernel k-NN kết thực nghiệm 26 3.1 Giới thiệu 26 3.2 Mô hình GA_Kernel k-NN 26 3.2.1 Kiến trúc GA_Kernel k-NN 26 3.2.2 Môi trường thực nghiệm 29 3.2.3 Mô tả chương trình 29 3.3 Kết thực nghiệm 32 3.3.1 Dữ liệu sử dụng 32 3.3.2 Kết chạy liệu Arcene 33 3.3.3 Kết chạy liệu DLBCL (Diffuse large B-cell lymphoma) 37 3.4 Kết luận 41 Kết luận 42 Tài liệu tham khảo 43 Danh mục hình vẽ Hình 1.1: Quá trình phát tri thức sở liệu Hình 1.2 : Hướng tiếp cận Filter Hình 1.3 : Hướng tiếp cận Wrapper Hình 2.1: Ví dụ thuật toán kNN 10 Hình 2.2: Ví dụ thuật toán WkNN 14 Hình 2.3 : Các thành phần thuật toán GA 20 Hình 2.4 : Các toán tử thuật toán GA 24 Hình 3.1:Mô hình thuật toán GA_Kernel k-NN 28 Hình 3.2: Độ xác GA_RF GA_Kernel k-NN liệu Arcene 34 Hình 3.3: Thuộc tính chọn GA_RF GA_Kernel k-NN liệu Arcene 35 Hình 3.4: Độ xác GA_Kernel k-NN công bố khác Arcene 37 Hình 3.5: Độ xác GA_RF GA_Kernel k-NN liệu DLBCL 38 Hình 3.6: Thuộc tính chọn GA_RF GA_Kernel k-NN liệu DLBCL 39 Hình 3.7: Độ xác GA_Kernel k-NN công bố khác DLBCL 41 Danh mục bảng Bảng 2.1: Các hàm trọng số tiêu biểu 11 Bảng 2.2: Một số hàm nhân hay dùng 16 Bảng 3.1: Danh sách tên hàm cài đặt thuật toán GA_Kernel k-NN 32 Bảng 3.2: Tổng quan liệu sử dụng 33 Bảng 3.3: Tóm tắt độ xác GA_Kernel k-NN GA_RF Arcene 34 Bảng 3.4: Số thuộc tính trích trọn GA_Kernel k-NN GA_RF Arcene 35 Bảng 3.5: Độ xác GA_Kernel k-NN công bố Arcene 36 Bảng 3.6: Tóm tắt độ xác GA_Kernel k-NN GA_RF DLBCL 38 Bảng 3.7: Số thuộc tính trích chọn GA_Kernel k-NN GA_RF DLBCL 39 Bảng 3.8: Độ xác GA_Kernel k-NN công bố DLBCL 40 Danh mục viết tắt STT Thuật ngữ Từ viết tắt Nearest Neighbors NN Genetic Algorithms GA Genetic Algorithms_Kernel k-Nearest Neighbors GA_Kernel k-NN Genetic Alorithms_Random Forest GA_RF Weighted k-Nearest Neighbors WkNN k-Nearest Neighbors kNN Kernel k-Nearest Neighbor Kernel k-NN Random Forest RF Proximity Measure - Support Vector Machine Rfprox-SVM Giới thiệu Khoa học kỹ thuật phát triển, với phát triển không ngừng liệu kích thước chủng loại Nhiệm vụ khai phá liệu nói chung nghiên cứu thuật toán phân lớp nói riêng trở nên ngày thiết đóng vai trò trung tâm việc giải toán cụ thể Thực tế cho thấy, tìm số thuật toán phù hợp với số loại liệu cụ thể bị giới hạn kích thước liệu Kết thuật toán phụ thuộc nhiều vào việc xử lý liệu thô Trong khai phá liệu, phương pháp trích chọn đóng vai trò quan trọng tiền xử lý số liệu, đặc biệt ngành tin sinh học, xử lý liệu âm thanh, hình ảnh, liệu mạng xã hội Đặc điểm chung lĩnh vực kích thước lớn (hàng trăm, hàng trăm nghìn thuộc tính) số thuộc tính có giá trị dùng để phân tích Trích chọn thuộc tính giúp tìm thuộc tính có ích, loại bỏ thuộc tính dư thừa Phương pháp tác động trực tiếp đến kết thuật toán tăng tốc độ xử lý, cải thiện liệu, tăng hiệu xuất khai phá Thuật toán k-Láng giềng gần (kNN) [10] kỹ thuật bản, đơn giản trực giác lĩnh vực phân tích thống kê Bộ phân lớp dựa thuật toán kNN học lười (lazy learner), không cần thực trình học cho mô hình Nó cần sử dụng tất đối tượng liệu tập tham chiếu để định gán nhãn lớp cho quan sát Thực nghiệm cho thấy, thuật toán kNN đơn giản, thường cho kết tốt Tuy nhiên hiệu thuật toán hạn chế tảng xây dựng dựa liệu tuyến tính Để áp dụng thuật toán vào liệu phi tuyến, có nhiều nghiên cứu ứng dụng kỹ thuật khác để biến đổi liệu tuyến tính thành liệu phi tuyến Hướng tiếp cận luận văn sử dụng phép biến đổi từ không gian ban đầu sang không gian sau áp dụng thuật toán kNN Việc tính toán không gian phi tuyến công việc thuật toán Hàm nhân – k Láng giềng gần (Kernel - k Nearest Neighbor) [12] Thuật toán Di truyền (GA) [1] kỹ thuật tìm kiếm tối ưu ngẫu nhiên theo trình thích nghi tiến hóa quần thể sinh vật Tư tưởng thuật toán GA mô phát triển tự nhiên, kế thừa đấu tranh sinh tồn sinh vật Thực tế có sinh vật liên tục tiến hóa để thích nghi với hoàn cảnh tồn phát triển GA xét đến toàn lời giải cách, trước tiên chọn tập lời giải sau loại bỏ lời giải không thích hợp chọn lời giải thích hợp để tiến hành lai ghép đột biến nhằm mục đích tạo nhiều lời giải có độ thích nghi ngày cao GA giúp tìm lời giải tối ưu hay tốt điều kiện thời gian không gian cho phép Trong luận văn đưa cách tiếp cận mới, kết hợp thuật toán GA Kernel k-NN theo mô hình Wrapper GA giúp tìm tập thuộc tính Kernel k-NN trả kết hàm mục tiêu GA Hay nói cách khác, GA chọn tập thuộc tính coi tốt quần thể thuộc tính, tập thuộc tính tốt hiểu ngữ cảnh thuộc tính trích chọn giúp phân lớp tốt dựa kết hàm tính khoảng cách thuật toán Kernel k-NN GA giúp tăng độ xác phân lớp nhờ việc tối ưu liệu đầu vào cho thuật toán Kernel k-NN Nội dung luận văn chia thành chương sau: Chương 1: Giới thiệu Khai phá liệu Chương 2: Cơ sở lý thuyết Chương 3: Mô hình GA_Kernel k-NN kết thực nghiệm Kết luận: Tóm lược kết đạt luận văn 30 - Hoạt động thuật toán GA_Kernel k-NN Bước 1: Dữ liệu ban đầu giảm chiều (giảm nhiễu) thông qua lọc nearZeroVar, findCorrelation, filterVarImp predict Bước : Chia ngẫu nhiên tập liệu thành hai tập: liệu huấn luyện liệu kiểm chứng Kích thước hai tập theo tỉ lệ 70/30 Bước : Tập huấn luyện ma trận kích cỡ m x n, với n số cột thuộc tính m số dòng (Gen) Tiến hành khởi tạo quần thể ban đầu, thuật toán GA tạo chuỗi Gen hệ Bước : Từ giá trị bít (trong chuỗi Gen) xác định số thuộc tính chọn Xây dựng ma trận tham số đầu vào hàm mục tiêu GA Trong thuật toán Kernel k-NN chia thuộc tính thành hai tập liệu huấn luyện và tập liệu kiểm chứng, theo tỉ lệ 70/30 Bước : Từ công thức ánh xạ phi tuyến 2.6 Dựa liệu huấn luyện tập liệu kiểm chứng, Tính ma trận chuyển đổi dựa hàm nhân Radial Basis ( , ) = exp − ‖ ‖ (2.9) Bước : Tính khoảng cách chuẩn không gian đối tượng quan sát tập liệu kiểm chứng với đối tượng quan sát tập liệu huấn luyện Sử dụng công thức: ( ), ( ) = ‖ ( ) − ( )‖ = 〈 ( ), ( )〉 − 2〈 ( ), ( )〉 + 〈 ( ), ( )〉 (2.8) = ( , )−2 ( , )+ ( , ) Bước : Với quan sát tập kiểm chứng, ta chọn k+1 láng giềng gần tập huấn luyện Bước : Thực chuẩn hóa k khoảng cách đối tượng quan sát tập kiểm chứng (ứng với k láng giềng gần nhất) sử dụng láng giếng gần thứ k+1 Ta có: ∈ [0,1), ( = 1, , = 1, ) Với m kích thước tập kiểm chứng Bước 9: Phân lớp cho quan sát tập kiểm chứng Tính tỉ lệ lỗi: 31 = với ≤ ổ ố ố á ị ℎâ ậ ể ℎứ (2.10) ≤ Tính độ xác = Bước 10 : Ghi nhớ tập thuộc tính và độ xác phân lớp tương ứng Bước 11 : Sử dụng thủ tục lại tạo, chọn lọc, đột biến để xây dựng chuỗi Gen (bộ thuộc tính) Thế hệ tiếp theo, thực bước Bước 12 : Kết thúc, dựa vào danh sách ghi nhớ bước 10, xác định tập thuộc tính có độ xác phân lớp cao chuỗi Gen tốt Tóm lại : thuật toán GA giúp tìm thuộc tính tối ưu (giảm chiều liệu) để tăng hiệu phân tích (phân lớp) thuật toán Kernel k-NN - Cài đặt thuật toán Tên hàm Diễn giải gafs(x, y, iters = 3, popSize = 150 Hàm chính, nhận tham số ma trận liệu, vector lớp tương ứng, số lần ) khởi tạo quần thể, số lần chuỗi Gen tạo createFolds ( ), lapply ( ) Một số hàm sử dụng từ thư viện R, thư viện Caret, chọn liệu ngẫu nhiên theo tập liêu huấn luyện tập liệu kiểm chứng ga_select (x, y, iters = 3, popSize Hàm xây dựng chuỗi Gen thông qua phương thức chọn lọc, lai tạo đột = 150 ) biến thuật toán GA ga_wrapper (ind, x, y, funcs ) Sử dụng thuật toán Kernel k-NN làm hàm mục tiêu thuật toán GA print.gafs (x ) Hiển thị thông tin đối tượng thuật toán GA 32 kernelKNN.cv (xtr, ytr, cv.fold=5, kvalue, sigma=0.066, isweight) Từ tập thuộc tính : - Phân chia ngẫu nhiên thành hai tập huấn luyện kiểm chứng - Xây dựng ma trận chuyển đổi (dùng công thức 2.6), sử dụng tham số sigma ( ) tính giá trị công thức Radial Basis – Thuật toán Kernel k-NN phân lớp trả độ xác phân lớp kernelKNN.predict (kxtrtr, kxtrte, kxtete, y, kvalue=5, ytr, isweight=TRUE) Từ ma trận chuyển đổi: - Sử dụng công thức 2.8, tính khoảng cách đối tượng quan sát tập liệu kiểm chứng với đối tượng quan sát tập liệu huấn luyện - Chuẩn hóa k khoảng cách (kvalue) đối tượng quan sát tập kiểm chứng (ứng với k láng giềng gần nhất) sử dụng láng giếng gần thứ k+1 Bảng 3.1: Danh sách tên hàm cài đặt thuật toán GA_Kernel k-NN 3.3 Kết thực nghiệm 3.3.1 Dữ liệu sử dụng Trong luận văn sử dụng hai liệu Gen thông dụng Đặc điểm chung hai số thuộc tính lớn số mẫu tương đôi nhỏ Dữ liệu DLBCL (Diffuse large B-cell lymphoma) liệu mở nghiên cứu bệnh nhân ung thư [4] Dữ liệu Arcene lấy từ UCI Machine Learning Reposotory (https://archive.ics.uci.edu/ml) Hai liệu phân làm hai lớp tương ứng với Gen (có bệnh / bình thường) Bảng 3.2 mô tả tổng quan liệu sử dụng bao gồm tên, số thuộc tính, số mẫu (số lượng Gen), số lớp 33 Dữ liệu Số thuộc tính Số mẫu Số lớp Arcene 10000 100 DLBCL 5469 77 Bảng 3.2: Tổng quan liệu sử dụng Đầu tiên thực việc thu gọn liệu thông qua lọc (trình bày chi tiết mục 3.2.1) Tổng số thuộc tính rút gọn sau : - Bộ liệu Arcene từ 10000 thuộc tính ban đầu giảm 451 thuộc tính - Bô liệu DLBCL từ 5469 thuộc tính ban đầu giảm 2773 thuộc tính Các liệu liệu đầu thuật toán GA_Kernel k-NN thuật toán GA_RF Thuật toán Rừng ngẫu nhiên (RF) thuật toán điển hình, cho kết phân tích liệu cao Kết hợp giải thuật Di truyền RF giúp nâng cao kết phân tích liệu Việc lấy kết thuật toán GA_RF để đối chiếu, chứng tỏ tính hiệu cao từ thuật toán để xuất Tôi sử dụng tổng số thuộc tính trích chọn độ xác phân lớp tiêu trí để so sánh Hai thuật toán chạy 50 lần để kiểm tra độ ổn định 3.3.2 Kết chạy liệu Arcene - Bộ liệu Arcene : Bộ liệu Arcene gồm 10000 thuộc tính 100 mẫu Gen liên quan bệnh ung thư, bao gồm mẫu Gen bị bệnh mẫu Gen bình thường Giá trị thuộc tính thu từ việc đo độ tập trung phổ Kiểu liệu thuộc tính kiểu số thực Bộ liệu Arcene luận văn sử dụng, năm liệu tổ chức NIPS (Neural Information Processing Systems) cung cấp Phân tích liệu Arcene, cụ thể việc phân lớp mẫu Gen thách thức NIPS đưa năm 2003 Bộ liệu Arcene đối tượng nghiên cứu điển hình nhiều nhà phân tích liệu - Độ xác phân lớp GA_Kernel k-NN GA_RF Đầu tiên thực việc chuẩn hóa liệu thông qua lọc nearZeroVar, findCorrelation, filterVarImp predict Bộ liệu Arcene từ 10000 thuộc tính giảm xuống 451 thuộc tính Các lọc loại bỏ nhiều thuộc tính dư thừa số mẫu thuộc tính phân lớp không đổi 34 Đối với thuật toán GA_Kernel k-NN xác định tham số đầu vào sau :  GA : số lần khởi tạo quần thể 3, số lần chuỗi Gen tạo 150  Kernel k-NN : tham số k=7, sigma = 0.066, isweightvalue = true Hình 3.2: Độ xác GA_RF GA_Kernel k-NN liệu Arcene Trong Hình 3.2, đường nét đậm thể kết thuật toán GA_Kernel k-NN Đường nét đứt thể kết thuật toán GA_RF sau chạy 50 lần Độ xác phân lớp (Accuracy) Thuật toán Thấp Trung bình Cao GA_Kernel k-NN 85.98 % 90.50 % 96.02 % GA_RF 83.04 % 88.12 % 92.01 % Bảng 3.3: Tóm tắt độ xác GA_Kernel k-NN GA_RF Arcene Bảng 3.3 minh họa kết tóm tắt 50 lần thực nghiệm, độ xác phân lớp trung bình sử dụng thuật toán GA_Kernel k-NN cao 2.38 % so với GA_RF Nếu lấy độ xác phân lớp thấp nhất, GA_Kernel k-NN so với GA_RF cao 2.94 % Và lấy độ xác phân lớp cao nhất, GA_Kernel k-NN cao 4.01 % Phương sai độ xác phân lớp chạy thuật toán GA_Kernel k-NN 2.03 % thuật toán GA_RF 2.12 % - Kết tổng số thuộc tính trích chọn GA_Kernel k-NN GA_RF 35 Hình 3.3: Thuộc tính chọn GA_RF GA_Kernel k-NN liệu Arcene Trong Hình 3.3, đường nét đậm thể kết tôi, đường nét đứt thể kết thuật toán GA_RF Số thuộc tính trích chọn Thuật toán Thấp Trung bình Cao GA_Kernel k-NN 112 213.5 257 GA_RF 87 265.5 409 Bảng 3.4: Số thuộc tính trích trọn GA_Kernel k-NN GA_RF Arcene Với tổng số 450 thuộc tính liệu Arcene, sau thực thuật toán GA_Kernel k-NN, số thuộc tính trung bình giảm 213.5 thuộc tính, trung bình giảm 47.44 % Phương sai 34.97 thuộc tính Đối với thuật toán GA_RF, số thuộc tính giảm trung bình 265.5 thuộc tính, trung bình giảm 59.00 % Phương sai 75.51 thuộc tính Từ biểu đồ số liệu thống kê cho thấy số lượng thuộc tính trích trọn thuật toán GA_Kernel k-NN đồng thuận toán GA_RF - Độ xác phân lớp GA_Kernel k-NN số công bố khác Tôi lấy độ xác trung bình sau 50 lần thực nghiệm thuật toán GA_Kernel k-NN so sánh với số công bố Tài liệu [15] công bố thuật toán SBFC (Selective Bayesian Forest Classifier) với độ xác phân lớp 72.20 %, 36 phương sai 4.00 %, kết số thuật toán phân lớp điển hình khác Tài liệu [8] công bố thuật toán Rfprox-SVM (Proximity Measure and Support Vector Machine) sử dụng hai tham số Jaccard index Kuncheva index với độ xác phân lớp 64.00% 78.00 % Phương pháp Độ xác phân lớp GA_Kernel k-NN 90.05 % +/- 2.03 Rfprox-SVM (Jaccard index) [8] 64.00 % Rfprox-SVM (Kuncheva index) [8] 78.00 % Selective Bayesian Forest Classifier (SBFC) [15] 72.20 % +/- 4.00 Bayesian Additive Regression Trees (BART) 71.60 % +/- 5.00 Random Forest (RF) 73.60 % +/- 9.00 Na’ıve Bayes (NB) 69.00 % +/- Classification and Regression Trees (CART) 63.00 % +/- C5.0 66.00 % +/- Logistic Regression (LR) 52.00 % +/- Support Vector Machines (SVM) 72.00 % +/- Lasso 65.60 % +/- 5.00 Bảng 3.5: Độ xác GA_Kernel k-NN công bố Arcene 37 Hình 3.4: Độ xác GA_Kernel k-NN công bố khác Arcene Hình 3.4 minh họa cho số liệu Bảng 3.5, Cột vị trí thể cho độ xác phân lớp trung bình thuật toán GA_Kernel k-NN sau 50 lần thực nghiệm Với độ xác 90.05 % phương sai 2.03 %, việc áp dụng thuật toán cho kết cao ổn định Đối với liệu Arcene, việc sử dụng số lọc để chuẩn hóa liệu làm số lượng thuộc tính giảm nhiều từ 10000 451, giúp cải thiện nhiều thời gian thực thi thuật toán đề xuất, cho kết phân lớp cao, phương sai nhỏ, số thuộc tính trích chọn tương đối đồng lần thực nghiệm Vì vậy, việc lựa chọn số lọc áp dụng thuật toán đề xuất liệu hiệu 3.3.3 Kết chạy liệu DLBCL (Diffuse large B-cell lymphoma) - Mô tả liệu : Bộ liệu DLBCL (Diffuse large B-cell lymphoma) chứa mẫu Gen bệnh ung thư ác tính u lym phô phổ biến người lớn, mẫu Gen liệu xuất khoảng 50% bệnh nhân Bộ liệu bao gồm 5649 thuộc tính 77 mẫu phân thành hai lớp bị bệnh không bị bệnh, kiểu liệu thuộc tính kiểu số thực - Độ xác phân lớp GA_Kernel k-NN GA_RF 38 Việc chuẩn hóa liệu thông qua lọc nearZeroVar, findCorrelation, filterVarImp predict thực Bộ liệu DLBCL từ 5649 thuộc tính giảm xuống 2773 thuộc tính Các lọc loại bỏ thuộc tính nhiễu số mẫu thuộc tính phân lớp không đổi Đối với thuật toán GA_Kernel k-NN xác định tham số đầu vào sau :  GA : số lần khởi tạo quần thể 3, số lần chuỗi Gen tạo 150  Kernel k-NN : tham số k=7, sigma = 0.066, isweightvalue = true Hình 3.5: Độ xác GA_RF GA_Kernel k-NN liệu DLBCL Trong Hình 3.5, đường nét đậm thể kết thuật toán GA_Kernel k-NN, đường nét đứt thể kết thuật toán GA_RF Độ xác phân lớp (Accuracy) Thuật toán Thấp Trung bình Cao GA_Kernel k-NN 85.63 % 89.63 % 93.54 % GA_RF 80.40 % 89.59 % 92.26 % Bảng 3.6: Tóm tắt độ xác GA_Kernel k-NN GA_RF DLBCL Bảng 3.6 tóm tắt kết 50 lần thực nghiệm, thấy độ xác phân lớp sử dụng GA_Kernel k-NN so với GA_RF cao 0.04 % Nếu xét độ xác phân lớp thấp nhất, GA_Kernel k-NN cao 5.23% so với GA_RF.Và xét độ xác phân lớp cao nhất, GA_Kernel k-NN so với GA_RF cao 39 1.28 % Phương sai độ xác phân lớp chạy thuật toán GA_Kernel kNN 1.98 % đó, thuật toán GA_RF 2.15 % Từ số liệu thống kê trên, thuật toán đề xuất cho kết phân lớp cao ổn định so thuật toán GA_RF - Kết số thuộc tính trích chọn GA_Kernel k-NN GA_RF Hình 3.6: Thuộc tính chọn GA_RF GA_Kernel k-NN liệu DLBCL Trong hình 3.6, đường nét đậm thể kết tôi, đường nét đứt thể kết chạy thuật toán GA_RF Số thuộc tính trích chọn Thuật toán Thấp Trung bình Cao GA_Kernel k-NN 249 546.0 842 GA_RF 258 1093.5 2444 Bảng 3.7: Số thuộc tính trích chọn GA_Kernel k-NN GA_RF DLBCL Với tổng số 2773 thuộc tính liệu DLBCL, sau thực thuật toán GA_Kernel k-NN, số thuộc tính trung bình giảm 546.0 thuộc tính, trung bình giảm 19.69 % Phương sai 162.40 thuộc tính Đối với thuật toán GA_RF, số thuộc tính giảm trung bình 1093.0 thuộc tính, trung bình giảm 39.42 % Phương sai 549.72 thuộc tính Từ biểu đồ số liệu thống kê cho thấy số lượng thuộc tính trích trọn thuật toán GA_Kernel k-NN đồng nhiều so thuận toán GA_RF 40 - Độ xác phân lớp GA_Kernel k-NN số công bố khác Tài liệu [5] đề xuất thuật toán tối ưu hóa phận quần thể PSO (Particle Swarm Optimisation) Thuật toán kết hợp việc tìm kiếm cục (PSO-LS) sử dụng chế thiết lập tham số gbest (PSO-RG), mô hình Wrapper sử dụng để trích chọn thuộc tính Việc kết hợp đặt tên thành PSO – LSRG, thuật toán cho độ xác 98.66 % Tài liệu [8] đề xuất thuật toán Rfprox-SVM (Proximity Measure and Support Vector Machine) tương ứng hai tham số Jaccard index Kuncheva index với độ xác phân lớp 82.00% 90.00 % Tài liệu [9] đề xuất thuật toán kết hợp phi tuyến tảng lựa chọn thuộc tính không giám sát (Nonlinear Mixture Models) với độ xác phân lớp 96.25 % Do tài liệu [8, 9] không công bố phương sai phương pháp họ đề xuất, nên lấy độ xác phân lớp cao 50 thực nghiệm chạy thuật toán GA_Kernel k-NN 93.54% để đối chiếu Nếu so tài liệu [9] thuật toán đề xuất cho độ xác phân lớp thấp 2.71%, so tài liệu [5] thuật toán cho độ xác phân lớp thấp 5.12% Nhưng so kết với tài liệu [8], thuật toán GA_Kernel k-NN có độ xác phân lớp cao 11.54 % 3.54% Phương pháp Độ xác phân lớp GA_Kernel k-NN 93.54 % Nonlinear Mixture Models [9] 96.25 % PSO – LSRG [5] 98.66 % Rfprox-SVM (Jaccard index) [8] 82.00 % Rfprox-SVM (Kuncheva index) [8] 90.00 % Bảng 3.8: Độ xác GA_Kernel k-NN công bố DLBCL Hình 3.7 minh họa số liệu bảng 3.8 Cột vị trí minh họa cho độ xác phân lớp cao 50 lần thực nghiệm thuật toán GA_Kernel k-NN liệu DLBCL Khi đối chiếu, thuật toán đề xuất cho kết khả quan 41 Hình 3.7: Độ xác GA_Kernel k-NN công bố khác DLBCL Đối với liệu DLBCL, việc áp dụng số lọc để chuẩn hóa liệu giúp giảm liệu dư thừa qua giảm thời gian thực thi thuật toán, kết phân lớp không thay đổi nhiều, số thuộc tính trích chọn đồng Dữ liệu DLBCL có đặc điểm số thuộc tính lớn, việc mở rộng không gian tìm kiếm thuật toán GA, hội mang lại cho thuật toán GA_Kernel kNN tìm được tập thuộc tính tốt có kích thước đủ nhỏ giúp nâng cao độ xác phân lớp Nhưng đổi lại thời gian thực thuật toán tăng lên, chi phí tài nguyên dành cho hệ thống tăng lên 3.4 Kết luận Độ xác phân lớp liên quan mật thiết với số thuộc tính trích chọn, số thuộc tính trích chọn gây mát thông tin lớn thường dẫn đến kết phân lớp không cao Từ kết thực ngiệm trên, việc kết hợp hai thuật toán GA Kernel k-NN mang lại kết khả quan GA giúp tối ưu liệu đầu vào, từ nâng cao độ xác phân lớp thuật toán Kernel k-NN Thuật toán GA_Kernel k-NN chứng tỏ việc trích chọn thuộc tính tốt mang lại kết phân lớp cao Các kết thực nghiệm minh chứng phương pháp đề xuất có tiềm ứng dụng rộng rãi toán phân lớp thực tế 42 Kết luận Trong luận văn giới thiệu phương pháp kết hợp thuật toán GA thuật toán Kernel k-NN Về thuật toán GA thuật toán Kernel k-NN thuật toán tốt sử dụng phân tích thống kê, áp dụng liệu có số chiều tương đối lớn (hàng trăm, hàng trăm nghìn thuộc tính) Việc kết hợp hai thuật toán, giúp kế thừa ưu điểm đồng thời khắc phục phần nhược hai thuật toán Cụ thể, thuật toán Kernel kNN giúp giải việc tính toán khoảng cách không gian liệu phi tuyến, thuật toán GA cho kết phân tích tốt tập n kết tìm với kích thước xác định, số lần lặp giới hạn biết trước Theo mô hình Wrapper, GA dùng để tìm tập thuộc tính coi tốt nhất, Kernel k-NN trả kết hàm mục tiêu GA Cách tiếp cận giúp tăng độ xác thuật toán Kernel k-NN Không tăng độ xác phân lớp so với thuật toán Kernel k-NN thuật toán GA_RF, thuật toán GA_Kernel k-NN cho thấy khả phân lớp tốt so sánh với số phương pháp phân lớp khác chạy liệu [8] [15] Cụ thể, với liệu Arcene phương pháp đề xuất cho kết phân lớp cao 90.05%, phương sai 2.03% Tuy nhiên, việc xác định giá trị k, xác định tham số đầu vào hàm nhân, ảnh hưởng đến kết thuật toán Kernel kNN Đối với thuật toán GA, kích cỡ không gian khảo sát ảnh hưởng đến chất lượng kết tìm kiếm Về mặt lý thuyết, quẩn thể lớn có nhiều hội tìm nhiều thuộc tính tốt hơn, tìm cự tiểu toàn cục không gian rộng Tuy nhiên, kích cỡ quần thể ? để tránh tượng “quá” không gian khảo sát dẫn đến lãng phí tài nguyên hệ thống, thời gian thực thi độ ổn định Vì việc tối ưu liệu, thuật toán đề xuất tiếp tục nâng cao hiệu tối ưu thêm tham số đầu vào hai thuật toán GA Kernel k-NN Đây hướng nghiên cứu mở rộng sau luận văn 43 Tài liệu tham khảo  Tiếng Việt [1] Bùi Văn Bình – CNCK, Giới thiệu Giải Thuật di truyền (GA) http://www.epu.edu.vn/cnck/Default.aspx?BT=14258 [2] Nguyễn Hà Nam (2009), "Tối ưu hóa KPCA GA để chọn thuộc tính đặc trưng nhằm tăng hiệu phân lớp thuật toán Random Forest", Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên Công nghệ, số 25, tr 84-93  Tiếng Anh [3] A.L Blum, P Langley, “Selection of Relevant Features and Examples in Machine Learning”, Artificial Intelligence Vol 97 (1997) 245 [4] Alexander Statnikov, Constantin F Aliferis, Ioannis Tsamardinos, Douglas Hardin, Shawn Levy, “A comprehensive evaluation of multicategory classification methods for microarray gene expression cancer diagnosis, Bioinformatics”, 21(5), 2005, 631-643 [5] Binh Tran, Bing Xue, and Mengjie Zhang, “Improved PSO for Feature Selection on High-Dimensional Datasets”, page 503, Simulated Evolution and Learning 10th International Conference, SEAL 2014 [6] Dong-Sheng Cao, Jian-Hua Huang, Jun Yan, Liang-Xiao Zhang, Qian-Nan Hu, Qing-Song Xu, Yi-Zeng Liang (2012), “Kernel k-nearest neighbor algorithm as a flexible SAR modeling tool”, Chemometrics and Intelligent Laboratory Systems 114 (2012) 19–23 [7] Hechenbichler Klaus, Schliep Klaus (2004), “Weighted k-Nearest-Neighbor Techniques and Ordinal Classification”, Discussion Paper 399, SFB 386, Ludwig-Maximilians University Munich [8] Huazhen Wang, Cheng Wang∗ , Bing Lv, Xiaoming Pan (2015), “Improved Variable Importance Measure of Random Forest via Combining of Proximity Measure and Support Vector Machine for Stable Feature Selection” Journal of Information & Computational Science 12:8 (2015) 3241–3252 44 [9] Ivica Kopriva, “A Nonlinear Mixture Model based Unsupervised Variable Selection in Genomics and Proteomics”, BIOINFORMATICS 2015 – International Conference on Bioinformatics Models, Method and Algorithms [10] Leif E.Peterson (2009), “K-Nearest Neighbor”, Scholarpedia, (2) [11] Krzysztof J.Cios, Witold Deddrycz, Roman W.Swiniarski, Lukasz A.Kurgan, “Data Mining A Knowledge Discovery Approach”, Springer, (2007) [12] Kai Yu, Liang Ji, Xuegong Zhang (2002), “Kernel Nearest-Neighbor Algorithm”, Neural Processing Letters, 15 (2), pp.147-156 [13] R Kohavi, G.H John, “Wrappers for Feature Subset Selection”, Artificial Intelligence Vol 97 (1997) 273 [14] Rutgers University, Chapter :Genetic Algorithm http://www.cs.rutgers.edu/~mlittman/courses/ml04/ch9.pdf [15] Viktoriya Krakovna, Jiong Du, Jun S Liu (2015), “ Selection Bayesian Forest Classifier : Simultaneous Variable Selection and Classification” arXiv:1506.02371v1 [start.ML] Jun 2015 [...]... đoạn trích chọn nhằm tìm ra thuộc tính đại diện phù hợp yêu cầu phân tích, loại bỏ thuộc tính dư thừa, thuộc tính nhiễu, tăng hiệu suất và kết quả khai phá dữ liệu Có rất nhiều phương pháp và các hướng tiếp cận khác nhau, tựu chung lại đều hướng đến mục tiêu :  Tăng tốc độ thuật toán  Giảm không gian lưu trữ dữ liệu  Tăng kết quả phân lớp, đoán nhận  Giúp biểu diễn, minh họa dữ liệu dễ dàng hơn... các thuộc tính Hình 1.2 : Hướng tiếp cận Filter Theo mô hình Filter, các thuộc tính được chọn độc lập với thuật toán khai phá dữ liệu Ngược lại, mô hình Wrapper các thuộc tính được chọn phụ thuộc theo một nghĩa nào đó với thuật toán khai phá dữ liệu Dữ liệu huấn luyện Tìm kiếm thuộc tính Tập thuộc tính lựa chọn Đánh giá kết quả Dữ liệu huấn Tập thuộc Thuật toán phấn lớp (Kiểm chứng) tính Đánh giá thuộc. .. Chương 1 Giới thiệu Khai phá dữ liệu 1.1 Tổng quan Khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời cuối những năm 80 của thế kỷ trước Nó bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có giá trị tiềm ẩn trong dữ liệu lớn. Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu Năm 1989,... từ kết quả của các giai đoạn sau Đánh giá và trình diễn Tri thức Dữ liệu khái phá Lựa chọn và chuyển dạng Làm sạch và tích hợp Kho dữ liệu Mẫu Dữ liệu chuyển dạng Dữ liệu Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu Một số phương pháp khai phá dữ liệu tiêu biểu:  Phân lớp (Classification) : Khai thác một hàm đã được huấn luyện trước để phân loại một đối tượng dữ liệu vào một trong các... nhất trong tập dữ liệu Trong giai đoạn tiền xử lý số liệu, việc trích chọn thuộc tính đóng vai trò quan trọng 1.2 Tổng quan trích chọn thuộc tính Về cơ bản việc trích chọn thuộc tính có ích sẽ bao gồm hai công đoạn cơ bản gồm công đoạn xây dựng dữ liệu và công đoạn trích chọn thuộc tính Xây dựng dữ liệu là tạo ra bộ các thuộc tính, một công việc rất quan trọng trong việc phân tích số liệu Yêu cầu đặt... phá dữ liệu chỉ là một khâu quan trọng trong khai phá tri thức Một quá trình phát hiện tri thức trong cơ sở dữ liệu bao gồm các giai đoạn chính sau : (1) Làm sạch dữ liệu (Data Cleaning): Khử nhiễu và các dữ liệu mâu thuẫn (2) Tích hợp dữ liệu (Data Integration): Kết hợp nhiều nguồn dữ liệu khác nhau (3) Lựa chọn dữ liệu (Data Selection): Chắt lọc lấy những dữ liệu liên quan đến nhiệm vụ phân tích. .. gồm ba phần chính : tiền xử lý số liệu, quá trình học để tìm tập thuộc tính tối ưu, và cuối cùng là mô đun phân lớp dữ liệu sử dụng trong quá trình trước đó - Phần một : dữ liệu ban đầu lần lượt đi qua các các bộ lọc, dữ liệu trả về của bộ lọc trước là dữ liệu đầu vào của bộ lọc sau Việc chuẩn hóa dữ liệu chỉ cần tiến hành một lần duy nhất, dữ liệu trả về sẽ được lưu lại và là tham số đầu vào của thuật... lượng thuộc tính của Gen đặc trưng cho một loại bệnh là rất nhỏ Việc lựa chọn chuẩn hóa dữ liệu làm đầu vào cho mô hình dự đoán giúp nâng cao tính chính xác và tối ưu thời gian công việc Dữ liệu luận văn sử dụng là một số bộ dữ liệu thông tin về Gen, được tổ chức dưới dạng ma trận, trong đó mỗi dòng là một Gen, mỗi cột là thuộc tính của Gen Các thuộc tính có kiểu dữ liệu số thực, giá trị thuộc tính. .. chi tiết trong Chương 3 26 Chương 3 Mô hình GA_Kernel k-NN và kết quả thực nghiệm 3.1 Giới thiệu Hầu hết các kỹ thuật khai phá dữ liệu hiện nay đều không đạt hiệu quả cao với tập dữ liệu có số chiều lớn, độ chính xác và hiệu quả truy vấn giảm nhanh khi số chiều tăng lên Ngoài ra việc thu thập dữ liệu cũng tốn rất nhiều thời gian, công sức và tiền bạc Thực tế số thuộc tính (số chiều) trong dữ liệu cần... preProcess để tiền xử lý dữ liệu (áp dụng một số chiến thuật như hướng tâm, mở rộng ) ước lượng từ dữ liệu huấn luyện và áp dụng trên dữ liệu khác với các tham số tương tự Bộ lọc predict có thể được chạy trên dữ liệu huấn luyện hoặc một số phần lặp lại của dữ liệu huấn luyện, qua đó dự đoán dữ liệu kiểm thử và tính xác suất phân lớp - Phần hai : Dữ liệu sau khi chuẩn hóa được phân chia một cách ngẫu ... HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG VĂN TRÌU TÌM HIỂU PHƯƠNG PHÁP TÌM THUỘC TÍNH TỐI ƯU NHẰM TĂNG HIỆU QUẢ PHÂN TÍCH TRONG PHÂN TÍCH DỮ LIỆU LỚN Ngành: Công nghệ thông tin Chuyên ngành: Kỹ... đoan Tôi xin cam đoan luận văn “ Tìm hiểu phương pháp tìm thuộc tính tối ưu nhằm tăng hiệu phân tích phân tích liệu lớn ” công trình nghiên cứu riêng Các số liệu, kết trình bày luận văn hoàn... phá liệu Dữ liệu huấn luyện Tìm kiếm thuộc tính Tập thuộc tính lựa chọn Đánh giá kết Dữ liệu huấn Tập thuộc Thuật toán phấn lớp (Kiểm chứng) tính Đánh giá thuộc tính Tập thuộc tính lựa chọn Tính