Một phương pháp trích trọn thuộc tính hiệu quả cho dữ liệu có số chiều lớn

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

29
lượt xem 3
download

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

Bài báo đề xuất một phương pháp học máy cho giải thuật phân lớp này nhằm tăng hiệu quả phân lớp của thuật toán. Cách tiếp cận này về cơ bản đã làm tăng khả năng phân lớp của giải thuật RF, phương pháp đề xuất 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ố. Như vậy, hướng cải tiến mà bài báo đề xuất là có khả thi và thu được kết quả tương đối cao. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Một phương pháp trích trọn thuộc tính hiệu quả cho dữ liệu có số chiều lớn

Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Một phương pháp trích trọn thuộc tính hiệu quả cho dữ liệu có số chiều lớn Hà Văn Sang1, Đồng Thị Ngọc Lan1 và Ngô Thị Thu Trang2 1 Khoa Hệ thống thông tin Kinh tế, Học Viện Tài chính Viễn thông, Học viện Công nghệ Bưu chính Viễn thông 2 Khoa Email: sanghv@hvtc.edu.vn, landn0101@gmail.com, trangntt1@gmail.com Abstract— Phân lớp là một trong những bài toán cơ bản trong pháp này có ảnh hưởng ngay lập tức đến các ứng dụng như khai phá tri thức và dữ liệu. Một thách thức của bài toán phân tăng tốc độ của các thuật toán khai phá dữ liệu, cải thiệu chất lớp là số lượng thuộc tính thường rất lớn, việc phân lớp sao cho lượng dữ liệu và vì vậy tăng hiệu suất khai phá dữ liệu, kiểm chính xác và hiệu quả hiện vẫn là một nghiên cứu thú vị cho các soát được các kết quả của thuật toán. nhà khoa học trong lĩnh vực khoa học máy tính. Bài báo đi sâu vào nghiên cứu giải thuật phân lớp thuộc tính random forest Trong bài báo này chúng tôi sẽ trình bày một đề xuất mới (RF). Đây là một giải thuật đã được nhiều nghiên cứu chứng để dựa vào đó xây dựng mô hình trích chọn đặc trưng tối ưu minh là rất hiệu quả trong phân lớp thuộc tính đối với bộ dữ liệu giúp giảm kích cỡ của dữ liệu theo hướng chỉ giữ lại các thuộc có số lượng thuộc tính lớn. Trên cơ sở đó bài báo đề xuất một tính đặc trưng, loại bỏ những thuộc tính không liên quan và phương pháp học máy cho giải thuật phân lớp này nhằm tăng những thuộc tính nhiễu nhằm tăng tốc độ các thuật toán phân hiệu quả phân lớp của thuật toán. Cách tiếp cận này về cơ bản đã lớp cải thiện chất lượng dữ liệu và vì vậy sẽ tăng hiệu suất của làm tăng khả năng phân lớp của giải thuật RF, phương pháp đề việc khai phá dữ liệu. Cụ thể, phương pháp đề xuất sẽ chọn ra xuất còn cho thấy khả năng phân lớp tốt hơn một số phương những thuộc tính tốt nhất để làm tăng năng suất của thuật toán pháp trích chọn đã được công bố. Như vậy, hướng cải tiến mà bài phân lớp Random Forest. báo đề xuất là có khả thi và thu được kết quả tương đối cao. II. CƠ SỞ LÝ THUYẾT Keywords- randomforest, trích chọn thuộc tính, phân lớp dữ liệu, khai phá dữ liệu. A. Trích chọn thuộc tính Trích chọn thuộc tính là một bước cơ bản nhất trong việc I. GIỚI THIỆU tiền xử lý dữ liệu, nó làm giảm bớt số chiều của mẫu. Lựa chọn Trong xu hướng hội nhập quốc tế, thời đại thông tin bùng thuộc tính có thể là một phần vốn có của trích chọn thuộc tính nổ, chúng ta đang “ngập lụt” trong dữ liệu nhưng lại “đói” về ví dụ như phương pháp phân tích thành phần cơ bản hoặc thậm tri thức, cho nên một trong các vấn đề cấp thiết đó là làm sao chí là một thiết kế xử lý thuật toán ví dụ như trong thiết kế cây phân tích và xử lý một khối lượng thông tin khổng lồ liên tục quyết định. Tuy nhiên, lựa chọn thuộc tính thường là một bước được cập nhật để đáp ứng các yêu cầu về phát triển mọi mặt cô lập riêng biệt trong một chuỗi xử lý [7]. văn hoá, kinh tế, chính trị, xã hội của đất nước. Hiện nay phần Có thể định nghĩa lựa chọn thuộc tính là một quá trình tìm lớn các thuật toán phân lớp đã phát triển chỉ có thể giải quyết ra M thuộc tính từ tập N thuộc tính ban đầu, như vậy phải xác được một lượng số liệu giới hạn cũng như một độ phức tạp dữ định tiêu chuẩn lựa chọn thuộc tính [8]. Theo cách này, kích cỡ liệu biết trước. Trong khi đó nhờ sự phát triển mạnh mẽ của của không gian đặc trưng được rút ngắn tối đa theo một tiêu khoa học và kỹ thuật, khối lượng dữ liệu mà chúng ta thu thập chuẩn định lượng nhất định. Khi kích cỡ của một lĩnh vực được được ngày càng phong phú và đa dạng. Hơn nữa, tuỳ thuộc vào mở rộng, số phần tử của tập N sẽ tăng lên, vì vậy việc tìm ra từng loại dữ liệu và ứng dụng cụ thể mà mỗi thuật toán có độ một tập đại diện tốt nhất thường gặp khó khăn và có nhiều vấn tốt xấu không giống nhau. Các nghiên cứu cho thấy có rất đề liên quan đến tập được chọn. Nhìn chung, một thuật toán nhiều hướng cải tiến các thuật toán phân lớp như áp dụng các trích chọn gồm 4 bước cơ bản: Sinh tập con, lượng giá tập con, thuật toán lai ghép (ensemble method), các thuật toán dựa vào điều kiện dừng và xác nhận kết quả. phương pháp nhân (kernel-based method), hoặc áp dụng các Quá trình sinh tập con là một thủ tục tìm kiếm, về cơ bản phương pháp trích chọn đặc trưng (feature extraction/ selection nó sinh ra những tập con dùng cho việc lượng giá. Gọi N là số method). Với các phương pháp kể trên phương pháp trích chọn các đại diện (đặc trưng) của tập dữ liệu gốc ban đầu, thì tổng số đặc trưng trở nên nổi trội và có một số ưu điểm phù hợp trong các tập con có thể được sinh ra sẽ là 2 n, 2n tập này sẽ liệt kê việc xử lý dữ liệu có số lượng thuộc tính lớn (vài nghìn đến vài toàn bộ các tập con của không gian. Mỗi tập con được sinh ra trăm nghìn thuộc tính) nhưng đồng thời chỉ có một số lượng bằng thuật toán cần được lượng giá trị bằng một tiêu chuẩn khá nhỏ các mẫu phân tích (vài chục hoặc vài trăm). Trong lượng giá trị nhất định và được so sánh với tập con tốt nhất đã khai phá dữ liệu thì phương pháp trích chọn đóng một vai trò tìm được trước nó. Nếu không có điều kiện dừng phù hợp, quan trọng để trích chọn và chuẩn bị dữ liệu. Hướng tiếp cận thuật toán này có thể sẽ chạy mãi không dừng. Điều kiện dừng này làm tăng hiệu năng thu nhận tri thức trong các ngành như của một quá trình sinh phải rơi vào một trong số các trường tin sinh, xử lý dữ liệu web, xử lý tiếng nói, hình ảnh,... Phương hợp sau: ISBN: 978-604-67-0635-9 82 82
HộiHội Thảo Quốc Thảo Gia Quốc 2015 Gia 2015về vềĐiện ĐiệnTử, Tử,Truyền TruyềnThông vàCông Thông và CôngNghệ Nghệ Thông Thông TinTin (ECIT (ECIT 2015) 2015) - Toàn bộ các phần tử của tập hợp đều được chọn. cây trong các tập nói trên. Đối với cây thứ k trong tập các cây, một véc tơ ngẫu nhiên Θk được tạo ra, véc tơ này độc lập với - Các phần tử chưa chọn bị lặp lại. các véc tơ được tạo ra trước đó Θ1, Θ2, …, Θk-1 nhưng sự - Sinh thêm một tập con nữa cũng không cho kết quả phân bố của các véc tơ này là tương tự nhau. Một cây được tốt hơn. phát triển dựa vào tập huấn luyện và véc tơ Θk kết quả là được một phân lớp h(x, Θk) trong đó x là véc tơ đầu vào. Sau khi - Đã chọn đủ số tập con thoả mãn điều kiện tiêu chuẩn. một số lượng lớn các cây được tạo ra các cây này “bỏ phiếu” Tập con tốt nhất được chọn ra phải được lượng giá trong cho lớp phổ biến nhất. những trường hợp khác nhau và nó cùng với tập gốc phải biểu Random forest được định nghĩa như sau [8]: Một random diễn được với dữ liệu thực tế. Lựa chọn các thuộc tính có thể forest là một phân lớp bao gồm một tập các phân lớp có cấu tiến hành theo hai cách: cách thứ nhất là xếp loại các thuộc tính trúc cây {h(x, Θk), k=1,… trong đó {Θk} là những véc tơ độc theo một tiêu chuẩn nào đó và lấy ra k thuộc tính đầu tiên, cách lập, tương tự nhau được phân bố một cách ngẫu nhiên và mỗi này là dựa vào ngưỡng để chọn thuộc tính. Cách thứ hai là cây sẽ bỏ một phiếu bầu cho lớp phổ biến nhất ở véc tơ đầu vào chọn ra tập con nhỏ nhất mà không làm giảm đi quá trình học, x. cách này tự động xác định số lượng thuộc tính. Ý tưởng chính của giải thuật random forest: Lựa chọn thuộc tính có thể dựa vào các mô hình, các chiến lược tìm kiếm, thước đo chất lượng thuộc tính và ước lượng. • Ở mỗi lần phân chia cây một tập ngẫu nhiên m thuộc Có ba loại mô hình như Filter, Wrapper, Embedded. Các chiến tính được lấy ra và chỉ m thuộc tính này tham gia vào việc phân lược tìm kiếm bao gồm: forward, backward, floating, branch chia cây. and bound, randomized. • Đối với mỗi cây phát triển dựa trên một mẫu boostrap, Ước lượng của việc chọn lựa thuộc tính bao gồm hai nhiệm tỷ lệ lỗi của các phần tử không thuộc vào bootstrap là được vụ: một là so sánh hai giai đoạn: trước và sau khi lựa chọn kiểm soát. Tỷ lệ lỗi này được gọi là tỷ lệ lỗi “out-of-bag” thuộc tính. Hai là so sánh hai thuật toán lựa chọn thuộc tính [1]. (OOB). Tóm lại lựa chọn thuộc tính được xem như là sự tổng hợp của Qua những tìm hiểu trên về giải thuật RF ta có nhận xét ba thành phần chính: tìm kiếm, đánh giá, chọn lựa mô hình. Về rằng RF là một phương pháp phân lớp tốt do: (1) Trong RF các cơ bản có thể phân loại các phương pháp lựa chọn thuộc tính sai số (variance) được giảm thiểu do kết quả của RF được tổng gồm có Filter, Wrapper và Embedded. hợp thông qua nhiều bộ học (learner), (2) Việc chọn ngẫu Hướng tiếp cận Filter (Các thuộc tính được chọn độc lập nhiên tại mỗi bước trong RF sẽ làm giảm mối tương quan với thuật toán khai phá dữ liệu)[13] (correlation) giữa các người học trong việc tổng hợp các kết quả. Ngoài ra, chúng ta cũng thấy rằng lỗi chung của một rừng Hướng tiếp cận Wrapper (Các thuộc tính được chọn phụ các cây phân lớp phụ thuộc vào lỗi riêng của từng cây trong thuộc theo 1 nghĩa nào đó với thuật toán khai phá dữ liệu)[13] rừng cũng như mỗi tương quan giữa các cây. Để thực hiện được các thuật toán trích chọn chúng ta phải thực hiện được một số công việc sau: III. MÔ HÌNH ĐỀ XUẤT - Phương pháp để sinh ra tập thuộc tính đặc Bài báo sử dụng mô hình Wrapper với hàm mục tiêu để đánh trưng(tương ứng với các chiến lược tìm kiếm) giá ở đây là thuật toán toán Random Forest được biểu diễn như - Định nghĩa hàm đánh giá (Đưa ra tiêu chí để xác định hình 3.1 dưới đây. 1 thuộc tính hay 1 nhóm thuộc tính là tốt hay xấu) - Ước lượng hàm đánh giá (Kiểm chứng hàm đánh giá có thực sự phù hợp và hiệu quả với bộ dữ liệu không). B. Thuật toán Random Forest Random Forest (rừng ngẫu nhiên) [14, 15, 16] là phương phân lớp thuộc tính được phát triển bởi Leo Breiman tại đại học California, Berkeley. Về bản chất RF sử dụng kỹ thuật có tên gọi là bagging. Kỹ thuật này cho phép lựa chọn một nhóm nhỏ các thuộc tính tại mỗi nút của cây phân lớp để phân chia thành các mức tiếp theo. Do đó, RF có khả năng phân chia không gian tìm kiếm rất lớn thành các không gian tìm kiếm nhỏ hơn, nhờ thế thuật toán có thể thực hiện việc phân loại một cách nhanh chóng và dễ dàng. Trong random forest, sự phát triển của một tập hợp các cây đã làm cải thiện một cách đáng kể độ chính xác phân lớp, mỗi cây trong tập hợp sẽ “bỏ phiếu” cho lớp phổ biến nhất. Để phát Hình 3.1: Mô hình đề xuất triển các tập hợp cây này thông thường các véc tơ ngẫu nhiên Kiến trúc của hệ thống gồm hai phần chính: được tạo ra, các véc tơ này sẽ chi phối sự phát triển của mối 83 83
HộiHội ThảoThảo Quốc Quốc Gia Gia 2015vềvềĐiện 2015 ĐiệnTử, Tử,Truyền TruyềnThông Thông và và Công CôngNghệ NghệThông ThôngTinTin (ECIT 2015) (ECIT 2015) Phần 1 được sử dụng để tìm ra bộ thuộc tính tốt nhất. Một 2.69 GHz, RAM 4GB. Phương pháp học máy được thực hiện cách tổng quát là hệ thống sinh ra các bộ thuộc tính con, sau đó trên ngôn ngữ R, đây là ngôn ngữ chuyên dùng trong xác suất sử dụng thuật toán học máy RF để đánh giá các bộ thuộc tính thống kê, có thể tải về từ địa chỉ www.r-project.org, gói con này. Quá trình này lặp đi lặp lại tới khi thỏa mãn điều kiện random forest cũng được tải về từ địa chỉ này, các mô đun khác dừng hệ thống sẽ thu được bộ thuộc tính tối ưu nhất. là hoàn toàn tự xây dựng, không sử dụng hay kế thừa lại của bất cứ nguồn nào. Phần 2 để kiểm chứng lại xem mô hình đưa ra có phù hợp không. 4.2 Quá trình thực nghiệm và kết quả Thuật toán đề xuất Chúng tôi đã sử dụng bộ dữ liệu có trên thực tế để kiểm nghiệm hệ thống là bộ dữ liệu mô tả về bệnh ung thư dạ dày. Chúng tôi đề xuất thuật toán để đánh giá và tìm ra tập các Kết quả thực nghiệm được trình bày dưới đây. thuộc tính tốt từ tập các thuộc tính ban đầu như sau: Bộ dữ liệu ung thư dạ dày (Stomach) Bước 1: Tạo ra m bộ thuộc tính từ tập n thuộc tích ban đầu. Bộ dữ liệu Stomach Cancer gồm 137 mẫu bao gồm Mỗi bộ chứa 2*n/m thuộc tính. Gồm: các thông tin về gen của các bệnh nhân bị bệnh và không bị n/m thuộc tính đều nhau bệnh. Trong đó có 67 mẫu của bệnh nhân bình thường và 70 mẫu của người bị bệnh. Bộ dữ liệu này được cung cấp bởi n/m thuộc tính ngẫu nhiên Trung tâm nghiên cứu về bệnh ung thư của Đại học Quốc gia Bước 2: Tính thang điểm ước lượng cho từng bộ thuộc tính Seoul tại Seoul, Hàn Quốc [17]. - Dùng RF tính thang điểm ước lượng cho các bộ thuộc Bộ dữ liệu là bảng hai chiều 137 x 119, gồm 137 bản ghi, tính. mỗi bản ghi có 119 thuộc tính. Các bản ghi trong bộ dữ liệu được phân thành hai lớp ký hiệu là normal (bệnh nhân bình = > Được tập các giá trị ước lượng f(i) (i=1,..,m) thường) và cancer (bệnh nhân bị ung thư). Bước 3: Tính ranking theo trọng số của từng thuộc tính. Kết quả và phân tích thực nghiệm trên bộ dữ liệu Stomach Trọng số của mỗi thuộc tính i được tính theo công Phần 1: Thực thi thuật toán RF trên bộ dữ liệu thức: Stomach gốc 20 lần, mỗi lần chạy lại thực hiện kiểm chứng chéo 5 lần với số cây lần lượt là 100,300,500,800,1000 ta được kết quả như sau : (1) Bảng 4.1 Giá trị trung bình, độ lệch chuẩn khi chạy RF 20 kij = 0 nếu thuộc tính thứ i không được chọn trong bộ thuộc lần trên bộ dữ liệu Stomach với số cây lần lượt bằng tính thứ j 100,300,500,800,1000. kij = 1 nếu thuộc tính thứ i được chọn trong bộ thuộc tính Giá thứ j Số Giá trị Giá trị trị cây trung Độ lệch nhỏ lớn Bước 4: Xây dựng tập mới gồm p% thuộc tính tốt nhất bình chuẩn nhất nhất Quay lại B1. Điều kiện dừng: 100 0.7765 0.02539685 0.73 0.82 a) Số thuộc tính < ngưỡng cho phép, hoặc bộ thuộc tính 300 0.781 0.0148324 0.76 0.81 mới có độ thích hợp không lớn hơn bộ thuộc tính vừa xác định trước đó. 500 0.7875 0.01996708 0.76 0.83 b) Số vòng lặp xác định 800 0.795 0.01538968 0.77 0.81 Trên đây là hướng đề xuất để tìm ra bộ thuộc tính tối ưu nhỏ 1000 0.796 0.0146539 0.76 0.82 nhất, cách làm này mục đích là để hạn chế số lượng thuộc tính Ta thấy số cây tăng lên thì độ chính xác phân lớp của RF đầu ra. Các thuộc tính ban đầu được phân chia đều để đảm bảo cũng tăng lên, độ lệch chuẩn nhỏ dần, điều đó rõ ràng là đúng tất cả các thuộc tính đều được chọn, rồi kết hợp với cách phân với tư tưởng của thuật toán, vì RF thực hiện phân lớp bằng chia các thuộc tính ngẫu nhiên để tạo được các bộ con thuộc phương pháp xây dựng cây, mỗi cây sẽ bỏ phiếu cho một phân tính mới. Sau đó dùng thuật toán học máy RF tính độ phù hợp lớp, số lượng cây càng lớn thì số phiều bầu cho phân lớp càng của các bộ thuộc tính. Dựa trên các giá trị độ phù hợp vừa tính nhiều, do độ độ chính xác phân lớp càng cao. Từ kết quả độ được chúng ta tìm ra bộ thuộc tính có số lượng thuộc tính ít lệch chuẩn tính được chứng tỏ RF chạy tương đối ổn định. hơn mà vẫn đảm bảo được mục tiêu của bài toán. IV. KẾT QUẢ 4.1 Môi trường thực nghiệm Tất cả các thực nghiệm được thực hiện trên máy Laptop với bộ xử lý Intel (R) Core (TM) i7 -2620 M CPU @ 2.70 GHz 84 84
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Bảng 4.2 Thời gian (phút) trung bình,nhỏ nhất, lớn nhất khi Bảng 4.4 Thời gian trung bình,nhỏ nhất, lớn nhất khi huấn huấn luyện và kiểm tra RF 20 lần trên Stomach với số cây lần luyện và kiểm tra RF 20 lần trên Stomach tối ưu với số cây lần lượt bằng 100,300,500,800,1000. lượt bằng 100,300,500,800,1000. Thời Thời Thời Thời Thời Thời Thời Thời Thời Thời Thời Thời gian gian gian gian gian gian gian gian gian gian gian gian Số huấn huấn huấn kiểm kiểm kiểm Số huấn huấn huấn kiểm tra kiểm kiểm cây luyện luyện luyện tra tra tra cây luyện luyện luyện trung tra tra trung nhỏ lớn trung nhỏ lớn trung nhỏ lớn bình nhỏ lớn bình nhất nhất bình nhất nhất bình nhất nhất nhất nhất 100 0.379 0.366 0.402 0.0294 0.018 0.04 100 0.1235 0.11 0.16 0.011 0 0.02 300 0.9621 0.946 0.986 0.0339 0.024 0.046 300 0.319 0.29 0.39 0.0165 0 0.03 500 1.5574 1.502 1.846 0.0386 0.03 0.046 500 0.5445 0.51 0.61 0.0205 0.01 0.05 800 2.4123 2.366 2.482 0.0361 0.03 0.042 800 0.8555 0.81 0.92 0.0275 0.01 0.05 1000 3.0899 3.01 3.146 0.0391 0.032 0.048 1000 1.031 0.99 1.08 0.03 0.01 0.06 4.3 Nhận xét Số lượng cây càng lớn thì thời gian huấn luyện và kiểm tra So sánh bảng 4.1 với bảng 4.3 ta thấy tỉ lện đoán nhận của càng tăng vì số cây càng lớn thì số phép toán thực hiện càng RF với bộ thuộc tính mới tăng lên rõ ràng, ước tính tăng nhiều nên thời gian thực hiện cũng tăng theo. khoảng 5%, thuật toán RF cho kết quả đoán nhận trung bình là 78% trên bộ dữ liệu ban đầu, còn RF chạy trên bộ dữ liệu sau Phần 2: Tiến hành lựa chọn bộ dữ liệu tối ưu từ bộ dữ khi lựa chọn các thuộc tính bằng thuật toán đề xuất cho kết quả liệu Stomach ban đầu bằng phương pháp đề xuất ở trên. Với đoán nhận trung bình là 83%. Từ bảng 4.2 và 4.4 ta cũng thấy tập các thuộc tính ban đầu, chúng ta thực hiện chia thành m bộ thời gian huấn luyện và thời gian kiểm tra đều giảm đi đáng kể. thuộc tính con bằng cách sử dụng hàm sample( , ,replace=True) Tỉ lệ đoán nhận trên bộ thuộc tính mới tăng lên cho thấy bộ sao cho mỗi bộ chứa n/m thuộc tính phân phối đều và n/m thuộc tính mới đã loại bỏ được một số thuộc tính nhiễu, thuộc thuộc tính ngẫu nhiên, với n là tổng số thuộc tính, m là tham số tính dư thừa. Còn thời gian giảm đi là vì số lượng thuộc tính đã phân chia(cụ thể thực nghiệm chọn m=10). Mất khoảng 20 giảm xuống tương đối nhiều, cụ thể từ 119 thuộc tính ban đầu, phút để lựa chọn được một bộ thuộc tính mới có độ chính xác sau khi lựa chọn bộ thuộc tính mới còn là 36 thuộc tính, như đoán nhận gần 84% . Cụ thể, file kết quả BestDPos cho biết bộ vậy số thuộc tính đã giảm khoảng 69% số thuộc tính ban đầu. thuộc tính mới gồm 36 thuộc tính có vị trí tương ứng trong số Điều đó chứng tỏ phương pháp thực nghiệm mà bài báo đưa ra 119 thuộc tính ban đầu là : cho hiệu quả tương đối tốt. Tuy nhiên, để tìm ra một bộ thuộc 2 8 15 16 19 26 27 28 34 tính mới chúng ta đã tiêu tốn một khoảng thời gian tương đối 45 50 53 57 58 59 61 64 66 68 lớn. Với bộ dữ liệu Stomach chúng ta mất khoảng 20 phút để 69 71 77 80 82 90 93 95 tìm ra được một bộ thuộc tính tối ưu hơn, và với các bộ dữ liệu 101 102 103 107 109 110 116 118 119 lớn hơn thì thời gian đó lại tăng lên, nhưng chúng ta chỉ mất thời gian 1 lần tìm bộ thuộc tính tối ưu. Sau đó, tất cả các bài Với bộ thuộc tính mới tìm được ta lại thực hiện lại phần 1 toán sử dụng bộ dữ liệu này khi thực thi trên bộ thuộc tính mới đã trình bày ở trên được kết quả đoán nhận của RF khi chạy 20 sẽ giảm thời gian tính toán trên tất cả các lần chạy. Và từ đó, lần trên bộ thuộc tính mới biểu diễn bởi bảng 4.3 thì thời gian làm việc sẽ giảm đi đáng kể. Bảng 4.3 Giá trị trung bình, độ lệch chuẩn khi chạy RF 20 Bộ thuộc tính mới tìm được theo phương pháp đề lần trên Stomach tối ưu với số cây lần lượt bằng xuất, đáp ứng được các mong muốn của chúng ta là nâng cao 100,300,500,800,1000. hiệu suất phân lớp và giảm thời gian học và thời gian kiểm thử. Giá trị Đặc biệt, trên các bảng 4.1, 4.3 ta thấy độ lệch chuẩn khi chạy Số RF trên bộ thuộc tính mới chỉ bằng 1/4 đến 1/3 độ lệch chuẩn trung Độ lệch Giá trị Giá trị cây khi chạy RF trên bộ dữ liệu ban đầu, chứng tỏ chạy RF trên bộ bình chuẩn nhỏ nhất lớn nhất dữ liệu mới ổn định hơn trên bộ dữ liệu ban đầu. Những điều 100 0.825288 0.009637 0.803843 0.846115 vừa nhận xét được minh họa rõ nét hơn trên các hình 4.1-4.2 300 0.822774 0.007596 0.806182 0.836424 sau đây. Các hình vẽ đó phản ánh cho chúng ta thấy chạy RF trên bộ dữ liệu mới cho kết quả cao hơn và ổn định hơn và 500 0.826391 0.008341 0.803342 0.842774 chạy nhanh hơn khi chạy RF trên bộ dữ liệu Stomach ban đầu. 800 0.832055 0.007423 0.821053 0.846784 1000 0.833693 0.00556 0.824561 0.840769 85 85
HộiHội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) việc thay đổi một số tham số còn làm thuật toán tiêu tốn thời gian hơn nữa. Để giải quyết hạn chế của phương pháp học máy được đề xuất ở trên trong thời gian tới chúng tôi sẽ chú trọng tìm hiểu, cải tiến nhằm tăng tốc độ phân lớp của giải thuật. Đồng thời, chúng tôi cũng tiến hành thử nghiệm phương pháp trên nhiều bộ dữ liệu khác nhau nhằm đánh giá độ chính xác và ổn định của phương pháp đối với từng loại dữ liệu cụ thể. Chúng tôi sẽ tìm hiểu một số phương pháp phân lớp khác như cây quyết định hoặc phương pháp véc tơ hỗ trợ (SVM), để thay thế thuật toán Random Forest khi đánh giá kết quả dự đoán. Rồi tiến Hình 4.1 Biểu đồ so sánh kết quả chạy RF 20 lần trên bộ dữ hành so sánh giữa các phương pháp này với nhau. Qua đó, liệu mới và bộ dữ liệu ban đầu với số cây bằng chúng tôi hy vọng có thể đóng góp thêm một chọn lựa cho các 100,300,500,800,1000. nhà phát triển ứng dụng khi phát triển các ứng dụng liên quan đến phân lớp dữ liệu. TÀI LIỆU THAM KHẢO [1] Nguễn Hà Nam, 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, Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 25 (2009) 84-93 [2] Nguyễn Đình Thúc, Lập trình tiến hóa, Nhà xuất bản giáo dục, 2001 [3] Huan Liu and Hiroshi Motoda, Co mputational Methods of Feature Selection, Chapman & Hall/CRC, 2008 [4] YongSeog Kim and Filipppo Meczenc, Feature Selection in Data Mining, 2005 [5] Jacek Jarmu lak and Susan Craw, Genetic Algorith ms for Featu re Selection and Weighting, IJCAI 99 workshop, 1999 [6] Jihoon Yang and Vasant Honavar, Feature Subset Selection Using a Genetic Algorithm, Artifical Intelligence Research Group Hình 4.2 Biểu đồ so sánh thời gian chạy trung bình của 20 [7] Krzysztof J.Cios, Witold Deddrycz, Ro man W.Swin iarski, Lu kasz lần chạy RF trên bộ dữ liệu mới và bộ dữ liệu ban đầu với số A.Kurgan, Data M ining A Knowledge Discovery Approach, Springer, cây bằng 100,300,500,800,1000. 2007 [8] Lu is Carlos Molina et at, Feature Selection for A lgorith ms: A Survey V. KẾT LUẬN and Experimental Evaluation, 2000 [9] Ron Kohavi and George H. John, Wrapper for Feature Subset Selection, Trong bài báo này chúng tôi đã tập trung nghiên cứu, tìm hiểu AIJ special issuse on relevance, 1996 về thuật toán di truyền và Random Forest cùng với một số [10] Sancho Salcedo –Sanz etc, Feature Select ion via Genetic Optimization, phương pháp tiền xử lý dữ liệu khác. Từ những tìm hiểu này, 2000 bài báo đề xuất hướng cải tiến hiệu quả phân lớp của thuật toán [11] Ha Nam Nguyen, Syng Yup Ohn, A Learning Algorith m based for RF theo phương pháp tìm ra bộ thuộc tính tối ưu nhỏ nhất từ Searching Optimal Co mb ined Kernal Function in Support Vector Machine, 2005 một bộ thuộc tính rất lớn của dữ liệu ban đầu. [12] Translation of M icroarray Data into Clin ically Relevant Cancer Bài báo đã trình bày chi tiết các bước trong nội dung thuật toán Diagnostic Tests Using Gege Exp ression Ratios in Lung Cancer And đề xuất, sau đó tiến hành thực nghiệm để chứng minh tính đúng Mesothelioma, Cancer Research, 2002 đắn của thuật toán. Thực nghiệm đã sử dụng bộ dữ liệu được [13] R. Kohavi, G.H. John, Wrappers for FeatureSubset Selection, Artificial lấy từ các công trình nghiên cứu trước đó là dữ liệu gen của các Intelligence Vol 97(1997) 273. bệnh nhân bị ung thư dạ dày (Stomach). Trong quá trình thực [14] L. Breiman (2002), Manual On Setting Up, Using, And Understanding Random Forests V3.1, Available: nghiệm chúng tôi tiến hành chạy rất nhiều lần, sau đó đánh giá kết quả nhận được giữa chương trình RF nguyên bản và http://oz.berkeley.edu/users/breiman/Using_random_forests_V3.1.pdf phương pháp đề xuất, có phân tích và vẽ biểu đồ so sánh. Từ [15] L. Breiman (2001), "Random Forests", Machine Learn ing Journal Paper, vol. 45. đó, chúng ta thấy được kết quả thực nghiệm trên cả hai bộ dữ [16] A. C. Leo Breiman, Random Forests, Available: liệu đều phản ánh rằng phương pháp đề xuất làm cho thuật toán http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm phân lớp RF chạy nhanh hơn, ổn định hơn và có khả năng đoán [17] Ha Nam Nguyen, Syng Yup Ohn (2005), A Learning A lgorith m based nhận chính xác hơn. Tuy nhiên, phương pháp đề xuất này có for Search ing Optimal Co mbined Kernal Function in Support Vector nhược điểm là phải tiêu tốn một khoảng thời gian chạy để tìm Machine. ra bộ thuộc tính tối ưu tương đối lớn. Nhưng lại giảm được thời gian huấn luyện và kiểm thử cho tất cả các lần sử dụng bộ dữ liệu về sau này. Nếu muốn kết quả dự đoán chính xác hơn thì 86 86