Báo cáo " 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 "

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

96
lượt xem 18
download

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

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...

Chủ đề:

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

Lưu

Nội dung Text: Báo cáo " 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 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 Nguy n Hà Nam* Khoa Công Ngh Thông Tin, Trư ng ðH Công Ngh , ðHQGHN, 144 Xuân Th y, Hà N i, Vi t Nam Nh n ngày 2 tháng 4 năm 2007 Tóm t t. 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à ñ n g 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 . T khóa: PCA, Hàm nhân, KPCA, Random Forest, trích ch n thu c tính. dù r t nhi u k thu t khai phá d li u d a trên 1. Gi i thi u ∗ m t s n n t ng lý thuy t khác nhau ñã ñư c Trong lĩnh v c nghiên c u v khai phá d phát tri n và ng d ng t r t lâu, nhưng th c t li u nói chung cũng như trong nghiên c u v cho th y k t qu ph thu c r t nhi u vào ñ c các thu t toán phân l p nói riêng, v n ñ x lý tính d li u cũng như kh năng x lý d li u d li u l n ngày càng tr thành v n ñ c p thi t thô c a t ng nhóm nghiên c u. M t ñi u hi n và ñóng vai trò ch ñ o trong vi c gi i quy t nhiên là v i m i phương pháp ch có th ñáp các bài toán th c t . Ph n l n các thu t toán ng và x lý t t trên m t vài d li u và ng phân l p ñã phát tri n ch có th gi i quy t d ng c th nào ñó. Trong khai phá d li u thì ñư c v i m t lư ng s li u gi i h n cũng như phương pháp trích ch n ñóng m t vai trò quan v i m t ñ ph c t p d li u bi t trư c. Trong tr ng trong ti n x lý s li u. Hư ng ti p c n khi ñó lư ng d li u mà chúng ta thu th p ñư c này làm tăng hi u năng thu nh n tri th c trong ngày càng tr nên phong phú và ña d ng nh s các ngành như tin sinh, x lý d li u web, x lý phát tri n m nh m c a khoa h c k thu t. M c 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 ∗ Tel.: 84-4-37547813. E-mail: namnh@vnu.edu.vn 84
85 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 tương ñ i nh các m u dùng ñ hu n luy n d ng b các thu c tính là m t công vi c r t (thư ng là vài trăm). Phương pháp trích ch n s quan tr ng trong vi c x lý s li u. Khi xây giúp gi m kích c c a không gian d li u, lo i d ng d li u chúng ta c n ph i ñ m b o không b nh ng thu c tính không liên quan và nh ng ñ m t nhi u thông tin quá cũng như không quá thu c tính nhi u. Phương pháp này có nh t n kém v m t chi phí. Ph n th hai có m c hư ng ngay l p t c ñ n các ng d ng như tăng tiêu tìm ra nh ng thu c tính ñ i di n cho ñ i t c ñ c a thu t toán khai phá d li u, c i thi n tư ng, lo i b nh ng thu c tính th a và gây ch t lư ng d li u và vì v y tăng hi u su t khai nhi u nh m tăng hi u su t c a các thu t toán phá d li u, ki m soát ñư c k t qu c a thu t khai phá d li u. Có r t nhi u p hương pháp toán. Phương pháp này ñã ñư c gi i thi u t cũng như hư ng ti p c n khác nhau bao g m nh ng năm 1970 trong các tài li u v xác su t các phương pháp kinh ñi n [1-3] v i b d li u th ng kê, h c máy và khai phá d li u [1-7]. tương ñ i nh và các hư ng ti p c n hi n ñ i [5-7]. Tuy v y chúng ñ u có m t s các yêu c u Phân tích các thành ph n cơ b n (PCA) [4] chung như sau: 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 • 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 ñó) 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 • Gi m b t hu c tính nh m ti t ki m không vào gi i quy t các bài toán phi tuy n tính. gian lưu tr Phương pháp này ñã ñư c Scholkhof và ñ ng • Tăng cư ng hi u qu thu t toán: nh m thu nghi p c a ông ñưa ra v i tên g i là KPCA [9]. ñư c t l d ñoán ñúng cao hơn Trong bài báo này chúng tôi s trình bày m t • Có tri th c v d li u: thu ñư c các tri th c cách ti p c n m i d a trên hàm nhân ñ có th v d li u thông qua các phương pháp bóc ch n ra nh ng thu c tính t t nh t ñ tăng kh tách d li u ñ có th t o ra hay bi u di n năng phân l p c a thu t toán Random Forest d li u d dàng hơn. (RF). Trong phương pháp ñ ngh , chúng tôi s V cơ b n chúng ta có th phân lo i các d ng gi i thu t di truy n ñ tìm ra hàm nhân t i phương pháp trích ch n theo 2 cách ti p c n ưu cho vi c tìm ra cách chuy n ñ i phi tuy n t t khác nhau là filter/wrapper, ñư c trình bày k nh t nh m làm tăng kh năng phân l p c a RF. trong các tài li u [1,2]. Lư c ñ th c hi n c a hai cách ti p c n này ñư c gi n lư c hóa trong hình v 1 và 2 dư i ñây. 2. Cơ s lý thuy t 2.1. Gi i thi u v trích ch n n i dung V cơ b n vi c bóc tách các thu c tính ñ c Hình 1. Hư ng ti p c n filter (các thu c tính ñư c trưng bao g m hai ph n là xây d ng các thu c ch n ñ c l p v i thu t toán khai phá d li u) [1]. tính và l a ch n các thu c tính ñ c trưng. Xây
86 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 Hình 2. Hư ng ti p c n 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) [1]. Hình 3. Ba cách ti p c n cơ b n c a trích ch n n i dung. 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.
87 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 ð th c hi n ñ ư c các thu t toán trích ch n, phương pháp t i ưu ñ c bi t. Gi i thu t di chúng ta c n ph i th c hi n m t s công vi c truy n là m t trong s các phương pháp ñ c bi t sau: ñó. • Phương pháp ñ sinh ra t p thu c tính ñ c Thu t toán di truy n, cũng như các thu t trưng (có th hi u tương ng v i các chi n toán ti n hóa nói chung, hình thành d a trên lư c tìm ki m) quan ni m cho r ng: quá trình ti n hóa t nhiên là hoàn h o nh t, h p lý nh t và t nó ñã mang • ð nh nghĩa hàm ñánh giá (ñưa ra các tiêu tính t i ưu. Quan ni m này có th ñư c xem chí ñ có th xác ñ nh m t thu c tính hay như là m t tiên ñ ñúng và không ch ng minh nhóm thu c tính là t t hay không t t) ñư c, nhưng phù h p v i th c t khách quan. • Ư c lư ng hàm ñánh giá ñó (ki m ch ng Quá trình ti n hóa th hi n tính t i ưu ch , th l i xem hàm ñánh giá có th c s phù h p h sau bao gi cũng t t hơn, phát tri n hơn, và hi u qu v i b d li u không). hoàn thi n hơn th h trư c. Ti n hóa t nhiên Hình v 3 th hi n s khác nhau gi a các ñư c duy trì nh hai quá trình cơ b n: sinh s n cách ti p c n Filter, Wrapper và Embedded [8]. và ch n l c t nhiên. Xuyên su t quá trình ti n Hai phương pháp (a) và (b) ñã ñ ư c mô t k hóa t nhiên, các th h m i luôn ñư c sinh ra trong các tài li u [1,2]. Phương pháp (c) tương ñ b sung và thay th cho th h cũ. Cá th nào ñ i gi ng cách ti p c n (b) ch có ñi m khác phát tri n hơn, thích ng hơn v i môi trư ng s bi t là nó ghép ph n sinh t p thu c tính vào t n t i, cá th nào không thích ng v i môi ph n ñánh giá trong khi hu n luy n. trư ng s b ñào th i. S thay ñ i môi trư ng là ñ ng l c thúc ñ y quá trình ti n hóa. Ngư c l i, ti n hóa cũng tác ñ ng tr l i góp ph n làm 2.2. Thu t toán di truy n thay ñ i môi trư ng. Có l p các bài toán hay mà ngư i ta chưa Trong thu t gi i di truy n, các cá th m i tìm ñư c thu t toán tương ñ i nhanh ñ gi i liên t c ñư c sinh ra trong quá trình ti n hóa quy t chúng. Nhi u bài toán trong l p này là nh s lai ghép th h cha m . M t cá th m i các bài toán quy ho ch mà thư ng n y sinh có th mang nh ng tính tr ng c a cha m (di trong các ng d ng c th . ð i v i d ng bài truy n), cũng có th mang nh ng tính tr ng toán này, ta thư ng ch có th tìm ra m t thu t hoàn toàn m i (ñ t bi n). Di truy n và ñ t bi n toán cho k t qu g n t i ưu. Ta cũng có th là hai cơ ch có vai trò quan tr ng như nhau dùng các thu t toán xác su t ñ x lý chúng, trong ti n hóa, dù r ng ñ t bi n x y ra v i xác nh ng thu t toán này không ñ m b o cho ra k t su t nh hơn nhi u so v i hi n tư ng di truy n. qu t i ưu. Tuy nhiên, ta có th gi m khá nhi u Các thu t toán ti n hóa, tuy có nh ng ñ c ñi m t l sai c a k t q u b ng cách ch n ng u nhiên khác bi t, nhưng ñ u mô ph ng b n quá trình ñ nhi u các “l i gi i có th ”. Nói m t cách cơ b n: Lai ghép, ñ t bi n, sinh s n và ch n l c ñơn gi n, vi c gi i m t bài toán có th xem như t nhiên. vi c tìm ki m l i gi i t i ưu trong m t không Như v y q uá trình ti n hóa càng lâu thì gian các l i gi i có th . Vì cái ñích c a chúng ta càng có ñi u ki n cho các cá th t t ñư c sinh là “l i gi i t t nh t”, ta có th coi công vi c này ra, và ch t lư ng c a các cá th càng ñư c nâng là m t quá trình t i ưu hóa. ð i v i không gian lên. nh , phương pháp “vét c n” c ñi n là ñ dùng; còn nh ng không gian l n hơn ñòi h i các
88 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 Sau ñó gi i h phương trình ñ tìm giá tr ñ c 2.3. Thu t toán KPCA trưng λ và véc tơ ñ c trưng λv = Cv Phương pháp PCA [4, 9, 10] là m t phương Ý tư ng cơ b n c a p hương pháp hàm nhân pháp ñư c s d ng khá ph bi n và tương ñ i [14] là các tính toán tương t cũng có th ñư c hi u qu ñ bi n ñ i t d li u có s lư ng th c hi n trong không gian tích vô hư ng F có thu c tính l n và nhi u nhưng có ñ tương quan liên quan t i không gian giá tr ñ u vào thông v i nhau thành m t b d li u có s chi u nh qua m t bi n ñ i phi tuy n Φ: Rm F và x X. hơn d a trên các phép bi n ñ i tuy n tính [11]. Ta có th bi u di n ma tr n tương quan trong Tuy nhiên trong nhi u ng d ng th c t , hi u không gian F như sau, v i gi s là d li u ñã qu c a phương pháp này r t h n ch vì n n ñư c chuy n v tâm c a tr c t a ñ t ng xây d ng thu t toán d a trên d li u tuy n tính [12]. n ∑ (Φ ( x )Φ ( x ) ) T ð có th áp d ng thu t toán này vào d j j (2) i, j =0 Cov(Φ ( xi ), Φ( x j )) = li u phi tuy n, ñã có nhi u nghiên c u ng n −1 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 và tương t chúng ta có th tính ñư c các giá tr tính. Nghiên c u c a Kramer [13] vào năm ñ c trưng tương t như v i PCA truy n th ng 1991 ñã tìm cách phát tri n thu t toán PCA phi v i hàm nhân có d ng như sau tuy n d a trên m ng nơ ron. Tuy nhiên m ng K i , j = Φ ( x j )Φ ( x j )T (3) này tương ñ i ph c t p và r t khó tìm ñư c giá tr t i ưu do có 5 l p. 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 2.4. Thu t toán Random Forest có th tương ng v i t h p tuy n tính c a m t Random forest [15] là m t thu t toán ñ c s ñ i lư ng ng u nhiên và vì v y có th tách bi t d a trên k thu t l p ghép (ensemble thành t ng các hàm c a các ñ i lư ng ñó. Cách techniques [4]). V m t b n ch t thu t toán RF th c chuy n ñ i ñó ch có th th c hi n ñư c ñư c xây d ng d a trên n n t ng thu t toán v i m t s r t h n ch các bài toán phi tuy n. phân l p CART s d ng k thu t có tên g i là Trong kho ng nh ng năm cu i c a th k ỳ bagging [4]. K thu t này cho phép l a ch n trư c, m t phương pháp PCA phi tuy n m i ñã m t nhóm nh các thu c tính t i m i nút c a ñư c xây d ng và phát tri n, có tên là KPCA cây ñ phân chia cho m c ti p theo c a cây (PCA d a trên hàm nhân) b i Scholkopf và phân l p. B ng cách chia nh không gian tìm ñ ng nghi p c a ông [9,10]. Phương pháp này ki m thành các cây nh hơn như v y cho phép th c hi n bi n ñ i phi tuy n trên h t a ñ b ng thu t toán có th p hân lo i m t cách r t nhanh cách tìm các ph n t cơ b n có liên h phi tuy n chóng cho dù không gian thu c tính r t l n. Các v i các giá tr ñ u vào. Gi s giá tr ñ u vào là tham s ñ u vào c a thu t toán khá ñơn gi n xk n m trong không gian Rm v i k=1,…, n, bao g m s các thu c tính ñư c ch n trong m i chúng ta có th tính ñư c ma tr n tương quan l n p hân chia (mtry). Giá tr m c ñ nh c a t ham (covariance matrix) c a các giá tr ñ u vào s này là căn b c hai c a p v i p là s lư ng các thu c tính. Tương t như thu t toán CART, RF n ∑ ( x − µ )( x −µj) i i j v n s d ng công th c Gini [4] là công th c (1) i , j =0 Cov( xi , x j ) = tính toán vi c p hân chia cây. S lư ng cây ñư c n −1
89 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 ñư c t o ra là không h n ch và cũng không s bao g m m t s m u là c a b nh nhân ung thư d ng b t kỳ k thu t ñ h n ch m r ng cây. còn m t s khác bình thư ng. Chúng ta ph i l a ch n tham s cho bi t s Ti p theo, chúng tôi s d ng thu t toán di lư ng cây (ntree) s ñư c sinh ra sao cho ñ m truy n ñ tìm h s t t nh t ñ xây d ng hàm b o r ng s m i m t thu c tính s ñư c ki m nhân theo công th c (4) s ñư c trình bày tra m t vài l n. Thu t toán s d ng k thu t ph n 3.2. Hàm nhân này ñ ư c s d ng trong OOB (out-of -bag) [15] ñ xây d ng t p hu n KPCA như m t cách ñ bi n ñ i không gian luy n và phương pháp ki m tra trên nó. ban ñ u thành không gian m i v i hy v ng có th phân l p d dàng và hi u qu hơn d a trên mô ñun phân l p RF. ñây thu t toán di truy n 3. N i dung và k t qu nghiên c u ñư c s d ng ñ t o ra m t b các giá tr th c β n m trong kho ng (0, 1). B giá tr này ñư c s d ng ñ xây d ng công th c c a hàm nhân 3.1. Mô hình ñ ngh 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 Ki n trúc cơ b n c a h th ng bao g m ba KPCA. Phép bi n ñ i này ñ ư c ñánh giá thông ph n chính: ti n x lý s li u, quá trình h c ñ qua t l l i phân l p ñư c t o ra b i mô ñ un tìm ra t p các tham s t i ưu và cu i cùng là mô RF. Quá trình tìm b h s β ñ ư c th c hi n ñun phân l p s li u chưa ñư c s d ng trong d a trên quá trình th c hi n các th t c c a các quá trình trư c ñó. 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 ñó. 3.2. 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 Hình 4. Ki n trúc t ng th c a phương pháp ñ ngh hi n thu t toán PCA ñư c th c hi n m t cách (KPCA-RF) v i mô hình h c ñ tìm ra d dàng và hi u q u thông qua hàm nhân. ðã có hàm nhân t t nh t.. 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 Trong mô ñun ti n x lý, chúng tôi ñã s vi c ch n ra m t hàm nhân ñ t t cho m t ng d ng k thu t t-test [3,4] nh m làm gi m s d ng hay m t lo i s li u c th luôn luôn là lư ng các thu c tính ñ làm gi m b t kh i m t thách th c không nh ñ i v i các nhà lư ng tính toán cũng như gi m ñ nhi u c a d nghiên c u. [10] 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 ñâ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
90 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 project.org), các mô ñ un KPCA và RF cũng m t cách th c xây d ng hàm nhân phù h p cho ñư c t i v t ñ a ch trên. 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 4.2. B d li u ung thư ru t k t m K c = ∑ βi × K i (4) i =1 B d li u ung thư ru t k t (Colon Tumor Th a mãn cancer). B d li u ung thư ru t k t [16] bao g m t hông tin v gen ñ ư c trích ra t h th ng m β ∈ [0,1] , ∑ βi = 1 DNA microarray. B d li u này bao g m 62 i =1 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 Trong ñó Ki là nh ng hàm nhân ñã ñư c thu c tính. Chúng tôi ch n ng u nhiên 40 m u xây d ng trư c ñó, h s βi th hi n nh hư ng làm t p hu n luy n và 22 m u còn l i ñư c s c a hàm nhân th i vào hàm nhân chính. ð d ng làm t p ki m tra. 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 4.3. Quy trình th c nghi m và k t qu lý Mercer ñã ñư c trình bày trong [14] ð u tiên chúng tôi th c hi n vi c thu g n H s β ñóng m t vai trò r t quan tr ng d li u s d ng t-test, ti p theo gi i thu t di trong vi c t o ra hàm nhân phù h p v i d li u truy n ñ ư c s d ng ñ tìm ra hàm nhân phù ñ u vào. Trong quá trình h c, c u trúc c a t p h p cho KPCA nh m chuy n ñ i không gian t i d li u hu n luy n s ñư c h c m t cách t ưu nh t cho vi c áp d ng phân l p RF. Th c ñ ng thông qua viêc thay ñ i h s này. Như ñã nghi m ñã ñư c th c hi n 50 l n ñ ki m tra s trình bày ph n trư c, chúng tôi s d ng thu t n ñ nh c a phương pháp ñ ngh . toán di truy n ñ tìm ra h s β phù h p nh t K thu t t-test ñư c áp d ng ñ l a ch n sao cho t i thi u hóa ñ ư c l i phát sinh trong kho ng 1000 thu c tính t t nh t và sau ñó ñư c quá trình h 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 4. K t qu và th o lu n 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 4.1. Môi trư ng th c nghi m 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 T t c các th c nghi m ñư c th c hi n trên máy tính Pentium IV 1.8GHz. Phương pháp ñ ñ ngh c a chúng tôi ñã cho k t q u t t hơn ngh ñư c th c hi n trên ngôn ng R, ñây là h n so v i thu t toán RF cơ s ban ñ u. 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-
91 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 1 2 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 RF Pred. Kpca Pred. Hình 5. 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.. trong vi c x lý s li u v i s chi u tương ñ i B ng 1 cho bi t k t qu d ñoán c a m t s l n và v i s lư ng m u hu n luy n tương ñ i nghiên c u có cùng hư ng ti p c n trích ch n nh . Phương pháp ñ ngh c a chúng tôi nh m n i dung ñã công b . So sánh v i nh ng k t qu gi m th i gian tính toán cũng như gi m ñ này t l d ñoán c a h th ng ñ ngh ñã ñ t nhi u c a d li u ñ u vào b ng cách áp d ng k ñư c k t qu tương ñ i kh quan. thu t hàm nhân PCA. Chúng tôi ñã xây d ng B ng 1. So sánh k t qu phân l p v i m t s n ghiên hàm nhân và phương pháp tìm ra hàm nhân t i c u trư c ñây v i phương pháp ñ ngh trên cùng b ưu thông qua vi c s d ng gi i thu t di truy n. d li u Cách ti p c n c a chúng tôi v cơ b n ñã tăng Các phương pháp T l d ñoán kh năng phân l p c a gi i thu t RF ñư c th ñúng (%) hi n thông qua hình 4. Không ch tăng ñư c Bootstrapped GA\SVM [17] 80.0 kh năng phân l p cho thu t toán RF, phương Combined kernel for SVM [18] 75.33±7.0 pháp ñ ngh còn cho th y kh năng phân l p KPCA-RF 81.09+9.85.2 t t hơn m t s phương pháp trích ch n ñã ñư c công b (B ng 1). K t lu n Trong bài báo này chúng tôi gi i thi u m t L i c m ơn phương pháp m i nh m m c tiêu gi m s lư ng Công trình này ñ ư c tài tr m t ph n t ñ thu c tính c a d li u ñ u vào trư c khi áp tài mang mã s : QG.08.01, ð i h c Qu c gia d ng m t phương pháp phân l p ñã bi t. V cơ Hà N i. b n thì RF là m t phương pháp tương ñ i t t
92 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 (Adaptive Computation and Machine Learning), References MIT press, 2002. [1] R. Kohavi, G.H. John, Wrappers for Feature [11] B.M. Wise, N.B. Gallagher, The process Subset Selection, Artificial Intelligence Vol 97 chemometrics approach to process monitoring (1997) 273. and fault detection, Journal of Process Control 6 (1996) 6. [2] A.L. Blum, P. Langley, Selection of Relevant Features and Examples in Machine Learning, [12] D. Dong, T.J. McAvoy, Nonlinear principal Artificial Intelligence Vol 97 (1997) 245. component analysis based on principal curves [3] Pang-Ning Tan, Michael Steinbach, and Vipin and neural networks, Computers and Chemical Kumar, Introduction to Data Mining, Addison Engineering 20 (1996) 65. Wesley; 1st edition, May 2, 2005. [13] M.A. Kramer, Nonlinear principal component [4] R. O. Duda, P. E. Hart, D. G. Stork, Pattern analysis using autoassociateive neural networks, Classification (2nd Edition), John Wiley & Sons A.I.Ch.E. Journal 37 (1991) 233. Inc, 2001. [14] N. Cristianini, J. Shawe-Taylor, An introduction [5] Luis Carlos Molina, Luis Belanche, Àngela to Support Vector Machines and other kernel- Nebot: Feature Selection Algorithms, A Survey based learning methods, Cambridge, (2000). and Experimental Evaluation, Technical report, [15] L. Breiman, Random forest, Technical report, Universitat Politècnica de Catalunya Statistics Department University of California Departament de Llenguatges i Sistemes Berkeley (2001). Informátics, France, 2002. [16] U. Alon, N. Barkai, D. Notterman, K. Gish, S. [6] H. Liu, L. Yu, Feature Selection for Data Ybarra, D. Mack, A. Levine.: Broad Patterns of Mining, Technical report, Department of Gene Expression Revealed by Clustering Computer Science and Engineering Arizona Analysis of Tumor and Normal Colon Tissues State University, America, 2002. Probed by Oligonucleotide Arrays, Proceedings [7] I. Guyon, A. Elisseeff, An introduction to of National Academy of Sciences of the United variable and feature selection. Journal of States of American (1999). Machine Learning Research 3 (2003) 1157. [17] Xue-wen Chen, Gene Selection for Cancer [8] I. Guyon, J. Weston, S. Barnhill, V. Vapnik, Classification Using Bootstrapped Genetic Gene Selection for Cancer Classification using Algorithms and Support Vector Machines, IEEE Support Vector Machines, Machine Learning, Vol 46 (2002) 389. Computer Society Bioinformatics Conference (2003). [9] B. Scholkopf, A.J. Smola, K. Muller, Nonlinear [18] H.N Nguyen, S.Y. Ohn, J. Park, K.S. Park, component analysis as a kernel eigenvalue problem, Neural Computation 10 (5), 1998. Combined Kernel Function Approach in SVM for Diagnosis of Cancer, Proceedings of the [10] B. Scholkopf, A.J. Smola, Learning with First International Conference on Natural Kernels: Support Vector Machines, Computation (2005). Regularization, Optimization, and Beyond .
93 N.H. Nam / Tạp chí Khoa học ĐHQGHN, Khoa học Tự Nhiên và Công nghệ 25 (2009) 84-93 Optimization of KPCA by GA for selecting relevant features to improving the effection of Random Forest classifier Nguyen Ha Nam Falcuty of Information Technology, College of Technology, Vietnam National University, Hanoi, 144 XuanThuy, Hanoi, Vietnam This paper proposed a combination of kernel functions Kernel Principle Component Analysis and its learning method which is help to not only transform the input space to a lower dimension feature space but also increase the classification performance. We defined the combined kernel function as the weighted sum of a set of difference types of basis kernel function consisting of polynomial, gausian and neural kernels, which is trained by a novel learning method based on genetic algorithm. The weights of basis kernel functions in the combined kernel are determined in learning phase and used as the parameters in the decision model in the classification phase. The unified kernel and the learning method were applied to obtain the optimal decision model for the classification of a public data set for diagnosis of cancer diseases. The experiment showed fast convergence in learning phase and resulted in the optimal decision model with the better performance than other kernels. Therefore, the proposed kernel function has the greater flexibility in representing a problem space than other kernel functions. Keywords: PCA, Kernel function, KPCA, Random Forest, Feature Selection.