- Tối ưu hóa KPCA bằng GA ñể chọn các thuộc tính ñặc trưng nhằm tăng hiệu quả phân lớp của thuật toán Random Forest. - Phân tích thành phần chính (PCA) là một phương pháp khá nổi tiếng và hiệu quả trong quá trình làm giảm số thuộc tính của tập dữ liệu ñầu vào. - Hiện nay phương pháp hàm nhân ñã ñược dùng ñể tăng khả năng áp dụng PCA khi giải quyết các bài toán phi tuyến. - Phương pháp này ñã ñược Scholkhof và ñồng nghiệp của ông ñưa ra với tên gọi là KPCA. - Trong bài báo này chúng tôi sẽ trình bày một cách tiếp cận mới dựa trên hàm nhân ñể có thể chọn ra những thuộc tính tốt nhất ñể tăng khả năng phân lớp của thuật toán Random Forest (RF). - Chúng tôi ñã sử dụng giải thuật di truyền ñể tìm ra hàm nhân tối ưu cho việc tìm ra cách chuyển ñổi phi tuyến tốt nhất nhằm làm tăng khả năng phân lớp của RF. - Cách tiếp cận của chúng tôi về cơ bản ñã tăng khả năng phân lớp của giải thuật RF. - Không chỉ tăng ñược khả năng phân lớp cho thuật toán RF, phương pháp ñề nghị còn cho thấy khả năng phân lớp tốt hơn một số phương pháp trích chọn ñã ñược công bố.. - Trong lĩnh vực nghiên cứu về khai phá dữ liệu nói chung cũng như trong nghiên cứu về các thuật toán phân lớp nói riêng, vấn ñề xử lý dữ liệu lớn ngày càng trở thành vấn ñề cấp thiết và ñóng vai trò chủ ñạo trong việc giải quyết các bài toán thực tế. - Phần lớn các thuật toán phân lớp ñã phát triển chỉ có thể giải quyết ñược với một lượng số liệu giới hạn cũng như với một ñộ phức tạp dữ liệu biết trước. - Trong khi ñó lượng dữ liệu mà chúng ta thu thập ñược ngày càng trở nên phong phú và ña dạng nhờ sự phát triển mạnh mẽ của khoa học kỹ thuật. - dù rất nhiều kỹ thuật khai phá dữ liệu dựa trên một số nền tảng lý thuyết khác nhau ñã ñược phát triển và ứng dụng từ rất lâu, nhưng thực tế cho thấy kết quả phụ thuộc rất nhiều vào ñặc tính dữ liệu cũng như khả năng xử lý dữ liệu thô của từng nhóm nghiên cứu. - Một ñiều hiển nhiên là với mỗi phương pháp chỉ có thể ñáp ứng và xử lý tốt trên một vài dữ liệu và ứng dụng cụ thể nào ñó. - Trong khai phá dữ liệu thì phương pháp trích chọn ñóng một vai trò quan trọng trong tiền xử lý số liệu. - Hướng tiếp cận này làm tăng hiệu năng thu nhận tri thức trong các ngành như tin sinh, xử lý dữ liệu web, xử lý tiếng nói, hình ảnh với ñặc tính là có rất nhiều thuộc tích (vài trăm cho ñến vài trăm ngàn thuộc tính) nhưng thường chỉ có một số lượng. - thống kê, học máy và khai phá dữ liệu [1-7].. - là một phương pháp khá nổi tiếng và hiệu quả trong quá trình làm giảm số thuộc tính của tập dữ liệu ñầu vào. - Gần ñây phương pháp hàm nhân ñã ñược áp dụng ñể có thể ứng dụng PCA vào giải quyết các bài toán phi tuyến tính.. - Phương pháp này ñã ñược Scholkhof và ñồng nghiệp của ông ñưa ra với tên gọi là KPCA [9].. - Trong phương pháp ñề nghị, chúng tôi sử dụng giải thuật di truyền ñể tìm ra hàm nhân tối ưu cho việc tìm ra cách chuyển ñổi phi tuyến tốt nhất nhằm làm tăng khả năng phân lớp của RF.. - Giảm dữ liệu cần lưu trữ và tăng tốc ñộ của thuật toán (tính toán trên dữ liệu ñó). - Tăng cường hiệu quả thuật toán: nhằm thu ñược tỷ lệ dự ñoán ñúng cao hơn. - Có tri thức về dữ liệu: thu ñược các tri thức về dữ liệu thông qua các phương pháp bóc tách dữ liệu ñể có thể tạo ra hay biểu diễn dữ liệu dễ dàng hơn.. - Về cơ bản chúng ta có thể phân loại các phương pháp trích chọn theo 2 cách tiếp cận khác nhau là filter/wrapper, ñược trình bày kỹ trong các tài liệu [1,2]. - Phần tô màu xám cho biết các thành phần mà hướng tiếp cận ñó sử dụng ñể ñưa ra kết quả cuối cùng.. - và hiệu quả với bộ dữ liệu không).. - Hai phương pháp (a) và (b) ñã ñược mô tả kỹ trong các tài liệu [1,2]. - Phương pháp (c) tương ñối giống cách tiếp cận (b) chỉ có ñiểm khác biệt là nó ghép phần sinh tập thuộc tính vào phần ñánh giá trong khi huấn luyện.. - Thuật toán di truyền. - Có lớp các bài toán hay mà người ta chưa tìm ñược thuật toán tương ñối nhanh ñể giải quyết chúng. - ðối với dạng bài toán này, ta thường chỉ có thể tìm ra một thuật toán cho kết quả gần tối ưu. - Ta cũng có thể dùng các thuật toán xác suất ñể xử lý chúng, những thuật toán này không ñảm bảo cho ra kết quả tối ưu. - Tuy nhiên, ta có thể giảm khá nhiểu tỷ lệ sai của kết quả bằng cách chọn ngẫu nhiên ñủ nhiều các “lời giải có thể”. - Nói một cách ñơn giản, việc giải một bài toán có thể xem như việc tìm kiếm lời giải tối ưu trong một không gian các lời giải có thể. - Vì cái ñích của chúng ta là “lời giải tốt nhất”, ta có thể coi công việc này là một quá trình tối ưu hóa. - ðối với không gian nhỏ, phương pháp “vét cạn” cổ ñiển là ñủ dùng;. - Một cá thể mới có thể mang những tính trạng của cha mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới (ñột biến). - Các thuật toán tiến hóa, tuy có những ñặc ñiểm khác biệt, nhưng ñều mô phỏng bốn quá trình cơ bản: Lai ghép, ñột biến, sinh sản và chọn lọc tự nhiên.. - Phương pháp PCA là một phương pháp ñược sử dụng khá phổ biến và tương ñối hiệu quả ñể biến ñổi từ dữ liệu có số lượng thuộc tính lớn và nhiễu nhưng có ñộ tương quan với nhau thành một bộ dữ liệu có số chiều nhỏ hơn dựa trên các phép biến ñổi tuyến tính [11].. - Tuy nhiên trong nhiều ứng dụng thực tế, hiệu quả của phương pháp này rất hạn chế vì nền tảng xây dựng thuật toán dựa trên dữ liệu tuyến tính [12].. - ðể có thể áp dụng thuật toán này vào dữ liệu phi tuyến, ñã có nhiều nghiên cứu ứng dụng các kỹ thuật khác nhau ñể có thể biến ñổi dữ liệu ñã cho thành dữ liệu ñược cho là tuyến tính. - Nghiên cứu của Kramer [13] vào năm 1991 ñã tìm cách phát triển thuật toán PCA phi tuyến dựa trên mạng nơ ron. - Nghiên cứu của Dong và McAvoy [12] cũng sử dụng mạng nơ ron với giả thiết rằng sự phi tuyến của dữ liệu ñầu vào có thể tương ứng với tổ hợp tuyến tính của một số ñại lượng ngẫu nhiên và vì vậy có thể tách thành tổng các hàm của các ñại lượng ñó. - Cách thức chuyển ñổi ñó chỉ có thể thực hiện ñược với một số rất hạn chế các bài toán phi tuyến.. - Trong khoảng những năm cuối của thế kỳ trước, một phương pháp PCA phi tuyến mới ñã ñược xây dựng và phát triển, có tên là KPCA (PCA dựa trên hàm nhân) bởi Scholkopf và ñồng nghiệp của ông [9,10]. - Phương pháp này thực hiện biến ñổi phi tuyến trên hệ tọa ñộ bằng cách tìm các phần tử cơ bản có liên hệ phi tuyến với các giá trị ñầu vào. - n, chúng ta có thể tính ñược ma trận tương quan (covariance matrix) của các giá trị ñầu vào. - Ý tưởng cơ bản của phương pháp hàm nhân [14] là các tính toán tương tự cũng có thể ñược thực hiện trong không gian tích vô hướng F có liên quan tới không gian giá trị ñầu vào thông qua một biến ñổi phi tuyến Φ: R m F và x X.. - Ta có thể biểu diễn ma trận tương quan trong không gian F như sau, với giả sử là dữ liệu ñã ñược chuyển về tâm của trục tọa ñộ. - và tương tự chúng ta có thể tính ñược các giá trị ñặc trưng tương tự như với PCA truyền thống với hàm nhân có dạng như sau. - Thuật toán Random Forest. - Random forest [15] là một thuật toán ñặc biệt dựa trên kỹ thuật lắp ghép (ensemble techniques [4. - Về mặt bản chất thuật toán RF ñược xây dựng dựa trên nền tảng thuật toán phân lớp CART sử dụng kỹ thuật có tên gọi là bagging [4]. - Bằng cách chia nhỏ không gian tìm kiếm thành các cây nhỏ hơn như vậy cho phép thuật toán có thể phân loại một cách rất nhanh chóng cho dù không gian thuộc tính rất lớn. - Các tham số ñầu vào của thuật toán khá ñơn giản bao gồm số các thuộc tính ñược chọn trong mỗi lần phân chia (mtry). - Tương tự như thuật toán CART, RF vẫn sử dụng công thức Gini [4] là công thức tính toán việc phân chia cây. - Kiến trúc cơ bản của hệ thống bao gồm ba phần chính: tiền xử lý số liệu, quá trình học ñể tìm ra tập các tham số tối ưu và cuối cùng là mô ñun phân lớp số liệu chưa ñược sử dụng trong các quá trình trước ñó.. - Kiến trúc tổng thể của phương pháp ñề nghị (KPCA-RF) với mô hình học ñể tìm ra. - hàm nhân tốt nhất... - Trong mô ñun tiền xử lý, chúng tôi ñã sử dụng kỹ thuật t-test [3,4] nhằm làm giảm số lượng các thuộc tính ñể làm giảm bớt khối lượng tính toán cũng như giảm ñộ nhiễu của dữ liệu. - Sau ñó dữ liệu ñược phân chia thành các tập dữ liệu huấn luyện và tập dữ liệu kiểm tra. - Bộ giá trị này ñược sử dụng ñể xây dựng công thức của hàm nhân nhằm biến ñổi từ không gian số liệu ban ñầu vào một không gian mới thông qua mô ñun KPCA. - Quá trình tìm bộ hệ số β ñược thực hiện dựa trên quá trình thực hiện các thủ tục của thuật toán di truy ền với hàm ñịnh giá dựa trên RF. - Quá trình này ñược lặp lại cho tới khi ñạt ñược kết quả tối ưu.. - Sau khi kết thúc quá trình tìm tập các hệ số dựa trên thuật toán di truyền, các kết quả này sẽ ñược chuyển ñầy ñủ sang mô ñun phân lớp với các dữ liệu chưa ñược phân loại trước ñó.. - Xây dựng hàm nhân và phương pháp học Như ñã trình bày ở các phần trên, việc chuyển ñổi không gian phi tuyến ban ñầu thành không gian tuyến tính ñể có thể dễ dàng thực hiện thuật toán PCA ñược thực hiện một cách dễ dàng và hiệu quả thông qua hàm nhân. - ðã có rất nhiều hàm nhân ñược xây dựng và công bố cho các ứng dụng cụ thể khác nhau, tuy nhiên việc chọn ra một hàm nhân ñủ tốt cho một ứng dụng hay một loại số liệu cụ thể luôn luôn là một thách thức không nhỏ ñối với các nhà nghiên cứu. - Ở ñây chúng tôi dựa vào một số kết quả trình bày trong các tài liệu [10,14] ñể giới thiệu. - một cách thức xây dựng hàm nhân phù hợp cho việc xử lý số liệu tin sinh học. - Hàm nhân do chúng tôi xây dựng ñược biểu diễn như sau. - Trong ñó K i là những hàm nhân ñã ñược xây dựng trước ñó, hệ số β i thể hiện ảnh hưởng của hàm nhân thứ i vào hàm nhân chính. - ðể chứng minh hàm nhân vừa ñược xây dựng thỏa mãn các ñiều kiện của một hàm nhân chúng ta có thể sử dụng bổ ñề 3.12 và nội dung của ñịnh lý Mercer ñã ñược trình bày trong [14]. - Hệ số β ñóng một vai trò rất quan trọng trong việc tạo ra hàm nhân phù hợp với dữ liệu ñầu vào. - Trong quá trình học, cấu trúc của tập dữ liệu huấn luyện sẽ ñược học một cách tự ñộng thông qua viêc thay ñổi hệ số này. - Như ñã trình bày ở phần trước, chúng tôi sử dụng thuật toán di truyền ñể tìm ra hệ số β phù hợp nhất sao cho tối thiểu hóa ñược lỗi phát sinh trong quá trình học.. - Kết quả và thảo luận. - Phương pháp ñề nghị ñược thực hiện trên ngôn ngữ R, ñây là ngôn ngữ chuyên dùng trong xác suất thống kê (có thể tải về tại ñịa chỉ http://www.r-. - Bộ dữ liệu ung thư ruột kết. - Bộ dữ liệu ung thư ruột kết (Colon Tumor cancer). - Bộ dữ liệu ung thư ruột kết [16] bao gồm thông tin về gen ñược trích ra từ hệ thống DNA microarray. - Bộ dữ liệu này bao gồm 62 mẫu với 22 mẫu của người bình thường và 40 mẫu của người có bệnh và có tổng số 2000 thuộc tính. - ðầu tiên chúng tôi thực hiện việc thu gọn dữ liệu sử dụng t-test, tiếp theo giải thuật di truyền ñược sử dụng ñể tìm ra hàm nhân phù hợp cho KPCA nhằm chuyển ñổi không gian tối ưu nhất cho việc áp dụng phân lớp RF. - Thực nghiệm ñã ñược thực hiện 50 lần ñể kiểm tra sự ổn ñịnh của phương pháp ñề nghị.. - Kỹ thuật t-test ñược áp dụng ñể lựa chọn khoảng 1000 thuộc tính tốt nhất và sau ñó ñược dùng là dữ liệu ñầu vào của chương trình KPCA_RF. - Hình vẽ 5 so sánh kết quả giữa thuật toán RF nguyên gốc và thuật toán học của chúng tôi thông qua 50 lần thực nghiệm. - Trung bình thuật toán RF cho kết quả là 77.64% với phương sai là 9.62%, còn thuật toán KPCA-RF cho kết quả ñoán nhận là 81.09% với phương sai là 9.82%. - Kết quả trên cho thấy thuật toán ñề nghị của chúng tôi ñã cho kết quả tốt hơn hẳn so với thuật toán RF cơ sở ban ñầu.. - So sánh kết quả ñoán nhận giữa thuật toán RF với thuật toán ñã ñược cải tiến KPCA-RF thông qua 50 lần thực nghiệm. - ðường nét ñậm thể hiện kết quả của thuật toán của chúng tôi,. - còn ñường mảnh thể hiện kết quả của thuật toán RF... - Bảng 1 cho biết kết quả dự ñoán của một số nghiên cứu có cùng hướng tiếp cận trích chọn nội dung ñã công bố. - So sánh với những kết quả này tỷ lệ dự ñoán của hệ thống ñề nghị ñã ñạt ñược kết quả tương ñối khả quan.. - So sánh kết quả phân lớp với một số nghiên cứu trước ñây với phương pháp ñề nghị trên cùng bộ dữ liệu. - Các phương pháp Tỷ lệ dự ñoán ñúng. - Trong bài báo này chúng tôi giới thiệu một phương pháp mới nhằm mục tiêu giảm số lượng thuộc tính của dữ liệu ñầu vào trước khi áp dụng một phương pháp phân lớp ñã biết. - Về cơ bản thì RF là một phương pháp tương ñối tốt. - Phương pháp ñề nghị của chúng tôi nhằm giảm thời gian tính toán cũng như giảm ñộ nhi ễu của dữ liệu ñầu vào bằng cách áp dụng kỹ thuật hàm nhân PCA. - Chúng tôi ñã xây dựng hàm nhân và phương pháp tìm ra hàm nhân tối ưu thông qua việc sử dụng giải thuật di truyền.. - Cách tiếp cận của chúng tôi về cơ bản ñã tăng khả năng phân lớp của giải thuật RF ñược thể hiện thông qua hình 4. - Không chỉ tăng ñược khả năng phân lớp cho thuật toán RF, phương pháp ñề nghị còn cho thấy khả năng phân lớp tốt hơn một số phương pháp trích chọn ñã ñược công bố (Bảng 1).