分類問題的一種可伸縮特征選擇算法_圖文

1、 1228 計 算 機 學 報 2005 年 (續(xù) 表 樣本集 Func. 5 Func. 6 Func. 7 Func. 8 Func. 9 Func. 10 樣本數 :1000 文件大小 :37 . 8 KB 0 . 033 0 . 034 0 . 043 0 . 041 0 . 039 0 . 032 樣本數 :10000 文件大小 :375 KB 0 . 112 0 . 121 0 . 090 0 . 010 0 . 098 0 . 090 運行時間 ( s 樣本數 :100000 文件大小 :3 . 67MB 0 . 761 0 . 741 0 . 791 0 . 781 0 . 7

2、61 0 . 754 樣本數 :1000000 文件大小 :36 . 7MB 6 . 643 6 . 599 6 . 810 6 . 792 6 . 629 6 . 781 樣本數 :10000000 文件大小 :367MB 64 . 943 64 . 221 68 . 794 67 . 943 66 . 982 64 . 943 注 :表中每格的運行時間均為 10 次平均 . 圖2 Benchmark2 樣本數在 10 6 107 時 , Sta FSOS 的耗時曲線 圖 3 Realworld 上 ,StaFSOS 組件與 GRSR 組件的性能比較 第 3 類數據集來源于真實保險單的信用評

3、定 , 使用基于 Sta FSOS 和 GRSR 算法的 COM 組件在 相同的硬件平臺上進行實驗 . 原始特征集有 20 個特 征 , 兩個類別 . 用基于粗糙集的特征選擇算法 GRSR 18 ( 這是 目前較快的一種特征選擇算法 的 COM 組件得到 的結果為 Checki n g ( 1 , D u ration ( 2 , Pu r pose ( 4 , A m ount ( 5 , I nst al l p ( 8 , P ropert y ( 12 , A ge ( 13 . 用 Sta FSOS 算法的 COM 組件在 = 85 % ,= 7 . 5 %時得到的結果為 Check

4、i n g ( 1 , D u ration ( 2 , H istor y ( 3 , A mount ( 5 , M ari t al ( 9 , A ge ( 13 , Ot her ( 14 . 可以看出 GRSR 和 Sta FSOS 的結果中 Chec2 ki n g ( 1 , D u ration ( 2 , A m ount ( 5 , A ge ( 13 4 個特 征是完全一致的 . 大多數相關領域專家認為 : Chec2 ki n g ( 1 , D u ration ( 2 , H istory ( 3 , Pu r pose ( 4 , A 2 mount ( 5 ,

5、 A ge ( 13 是這個數據集的目標特征集 , 因 此 Sta FSOS 基本保留了對分類最為重要的特征 ,準 確 性 是 有 保 證 的 . 在 數 據 集 較 小 時 , GRSR 和 Sta FSOS 都能很快得出結果 ; 而當數據集較大時 , Sta FSOS 要明顯地快于 GRSR ( 詳見圖 3 , 圖中所有 情形下的執(zhí)行時間均是 100 次的平均值 . 在 14 個實驗中雖然和值設置有些變化 . 但 是的意義容易理解 , 容易設定 , 因此條件 不變 , 而條件 可以變?yōu)?:將所有的特征按 SCD 測度值從 大到小排序輸出 , 前 n 項就是所要的 n 個特征 . 相應 在

6、Sta FSOS 算法的第 6 步按特征的 SCD 值排序即 可 . 此時 Sta FSOS 變得更加靈活 . 5 結束語 本文的基本結論 : 我們提出了一種描述特征與 類別相關度的 SCD 測度 , 并給出了相關理論和證 明 ,根據這個測度構造的 Sta FSOS 算法在實驗中結 果準確 ,效率很高 , 是一種 I/ O 線性的可伸縮特征 選擇算法 , 適于面向大數據量的數據挖掘 . 參 1 2 考 文 獻 Dash M. , Liu H. . Feat ure selection for classification. Intelli2 gent Data Analysis , 1997

7、, 1 (3 : 131156 Siedklecki W. , Sklansky J . . On automatic feat ure selection. International Journal of Pattern Recognition and Aritifical In2 telligence , 1988 , 2 : 197220 3 Sheinvald J . , Do m B. , Niblack W. . A modelling app roach to feat ure selection. In : Proceedings of t he 10t h Internat

8、ional Conference on Pattern Recognition , 1990 , 1 : 535539 4 Almuallim H. , Dietterich T. G. . Learning wit h many irrele2 vant feat ures. In : Proceedings of t he 9t h National Conference on Artificial Intelligence , Cambridge , Massachusett s , 1992 , 547552 5 Narendra P. M. , Fukunaga K. . A bra

9、nch and bound algorit hm © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 7期 張 巍等 : 分類問題的一種可伸縮特征選擇算法 1229 for feat ure selection. IEEE Transactions on Co mp uters , 1977 , C 226 (9 : 917922 6 Kira K. , Rendell L . A. . The feat ure selection problem : t radi2 tional met

10、 hods and a new algorit hm. In : Proceedings of t he 9t h National Conference on Artificial Intelligence , 1992 , 129134 7 Cardie C. . U sing decision t rees to improve case2based learning In : Proceedings of t he 10t h International Conference on Ma2 chine Learning , 1993 , 2532 8 Ucciardi A. N. ,

11、Go se E. E. . A co mparison of seven techniques for choo sing subset s of pattern recognition. IEEE Transactions on Computers , 1971 , C 220 : 10231031 9 Liu H. , Setiono R. . A p robabilistic approach to feat ure selec2 tion : A filter solution. In : Proceedings of International Confer2 ence on Mac

12、hine Learning , 1996 , 319327 10 Liu H. , Setiono R. . Feat ure selection and classification : A probabilistic wrapper approach , In : Proceedings of t he 9t h In2 ternational Conference on Indust rial and Engineering Applica2 tions of A I and ES , 1996 , 284292 11 Kohavi R. . Feat ure subset select

13、ion using t he wrapper met h2 od : Overfitting and dynamic search space topology. In : Pro2 ceedings of AAA I Fall Sympo sium on Relevance , 1994 , 109 113 12 13 Han J . , Kamber M. . Data Mining Concept s and Techniques. Morgan Kauf mann , 2000 Skowron R. A. , Suraj Z. . Discovery of concurrent dat

14、a f rom experimental data tables : A rough set app roach. Instit ute of Co mp uter Science , Warsaw Universit y of Technology , Re2 search Report , 1995 14 Zhong N. , Dong J . . U sing rough set s wit h heuristics for fea2 t ure selection. Journal of Intelligent Information Systems , 2001 , 16 : 199

15、214 15 Swiniarski R. W. , Skowron A. . Rough set met hods in feat ure 22 21 20 19 18 17 16 selection and recognition. Pattern Recgnization Letters , 2003 , 24 : 833849 Zhang Xiang2De , Zhang Wei , Liu Yu2Rong. The greedy2 roughset att ribute reducing algorit hms for classification min2 ing. Journal

16、of Nort heastern Universit y ( Nat ural Science , 2001 , 22 (5 : 580583 (in Chinese ( 張祥德 ,張 巍 ,劉玉蓉 . 數據挖掘分類問題的貪婪粗糙集約 簡算法 . 東北大學學報 , 2001 , 22 (5 : 580583 Pedrycz W. , Vukovichc G. . Feat ure analysis t hrough informa2 tion granulation and f uzzy set s. Pat tern Recognition , 2002 , 35 : 825834 Fan

17、Jin2Song , Fang Ting2Jian. Analysis and evaluation on main factors for feat ure selection and abst raction. Co mputer Engi2 neering and Applications , 2001 , 37 (13 : 9599 ( 范勁松 ,方廷健 . 特征選擇和提取要素的分析及其評價 . 計算 機工程與應用 , 2001 , 37 (13 : 9599 He Jin2Song , Shi Ze 2Sheng. Met hod of feat ure selection usin

18、g signal analysis. Journal of Universit y of Science and Technolo2 gy of China , 2001 , 31 (1 : 7478 , 56 (in Chinese ( 何勁松 ,施澤生 . 特征選擇方法中信號分析方法的研究 . 中國 科技大學學報 , 2001 , 31 (1 : 7478 , 56 Li H. X. , Xu L . D. . Feat ure space t heory : A mat hematical foundation for data mining. Knowledge Based Syste

19、m , 2001 , 14 : 253257 Zhou Guang2 Ya , Zhao Wen , Zhao Zhen2Quan. Multivariate Statistical Met hod. Changchun : Jilin Universit y Press , 1988 (in Chinese ( 周光亞 ,趙 文 ,趙振全 . 多元統(tǒng)計方法 . 長春 : 吉林大學出版 社 ,1988 Agrawal R. , Imielinski T. , Swami A. . Database mining : A performance perspective. IEEE Transac

20、tions on Knowledge and Data Engineering , 1993 , 5 (6 : 914925 ZHANG Wei , born in 1975 , Ph.D. His main research interest s include data mining and statistical analysis , data driven technology , scalable T TS sys2 tem. ZOU Xiang , born in 1977 , Ph.D. His research interest s include data mining ,

21、dist ributed system. WU Xiao2 Ru , bo rn in 1972 , Ph. D. . His research inter2 est s include speech recognition and T TS , data driven tech2 nology. Background This wo rk is f rom t he p roject of Scalable Speech Syt he2 sis ( Text to Speech System , which is supported by t he Na2 tio nal High Technology Research and Develop me