文档介绍：基于谱分析的无监督特征选择算法
收稿日期:2011-02-18;修回日期:2011-04-18。
基金项目:国家自然科学基金资助项目(71001072);广东省自然科学基金资助项目(9451806001002694)。
作者简介:潘锋(1977-),男,河南正阳人,讲师,博士研究生,主要研究方向:数据挖掘、机器学****王建东(1945-),男,江苏南京人,教授,博士生导师,主要研究方向:数据挖掘、机器学****知识工程; 牛奔(1980-),男,安徽全椒人,副教授,博士,主要研究方向:智能系统、人工生命。
文章编号:1001-9081(2011)08-02108-03doi:.
(,南京210016; ,广东深圳518060)
(stridence@)
摘要:为提高无监督状态下特征选择的准确度,基于图谱理论证明了标准化Laplacian矩阵前K个最小特征值分布表现了簇结构的可识别性,使用谱分析方法指导无监督特征选择,提出了特征重要度排序算法。对大容量数据集特征选择,应用Nystr?m方法降低时间复杂度。实验结果表明,使用该算法与使用主流无监督特征选择方法及全部特征相比能得到更高的聚类性能评分。
关键词:数据挖掘;聚类算法;无监督学****谱分析;特征选择
中图分类号: TP18; :A
Unsupervised feature selection approach based on spectral analysis
PAN Feng1,2, WANG Jian-dong1, NIU Ben2
(1. College puter Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu 210016, China;
2. College of Management, Shenzhen University, Shenzhen Guangdong 518060, China)
Abstract: To improve the performance of feature selection under the unsupervised scenario, the relationship between the distribution of the first K minimal eigenvalues for a normalized graph Laplacian matrix and the structure of the clusters was identified, and a new feature selection algorithm based on the spectral analysis was proposed. The feature selection algorithm might be time-consuming; hence the Nystr?m method was applied to reduce putational cost of the eigen-position. The experiments on synthetic and real-world data sets show the efficiency of the proposed approach.
Key words: data mining; clustering algorithm; unsupervised learning; spectral analysis; feature selection
0 引言
许多数据挖掘问题必须处理较高维度的数据,如图像、文本及客户关系数据等,这使得传统意义上的数据挖掘算法不再适用。一般的解决办法是对数据进行预处理,即在数据分析之前根据处理目的提取相关特征,舍弃不相关或冗余特征。根据数据是否带有标记,特征选择可分为针对有标记数据的有监督特征选择与针对无标记数据的无监督特征选择。对有监督特征选择研究较为深入,相关文献也比较多。无监督特征选择见诸文献较少,这是由于样本无标记使得特征约简缺乏统一有效的选择标准。常见的特征选择技术主要有Filter类方法与Wrapper类方法。前者与具体学****器无关,可以视为数据分析的预处理器,这种方法效率较高但效果不如后者。Wrapper方法则是将特征选择步骤集成于某种特定的学****器(如K-mea