基于邻域粗糙集的不完整决策系统特征选择算法

Feature subset selection algorithms for incomplete decision systems based on neighborhood rough sets

针对不完整决策系统属性约简算法时间复杂度较高问题,基于正域不变条件下,决策系统分类能力保持不变原则,提出不完整决策系统前向顺序特征选择算法.该算法从约简集为空集开始,根据在约简集合中加入各属性后对正域影响程度大小将属性降序排列,采用顺序前向搜索,选择当前最佳特征加入特征约简集合,确定最佳特征子集.将该算法扩展到基于邻域粗糙集的实值和混合型不完整决策系统,得到基于邻域粗糙集的不完整决策系统前向顺序特征选择算法.同时,将基于相容关系的不完整决策系统快速属性约简算法推广到实值和混合属性的不完整决策系统,得到适用于实值、混合属性的不完整决策系统后向特征选择算法.理论分析和University of California Irvine机器学习数据库数据集的实验共同表明,本文提出的基于邻域粗糙集的不完整决策系统前向特征选择算法有效降低了不完整决策系统特征选择算法的时间复杂度,在保持系统识别能力的情况下,用更少的时间得到决策系统的属性约简子集,即特征子集.然而,本文前向特征选择算法的缺陷是有可能因为无法选择到第一个最重要的特征(属性)而使特征选择过程不能进行下去,从而不能完成特征选择过程.

New feature subset selection algorithms are presented in this paper to reduce the heavy computational load of available algorithms to feature subset selection for incomplete decision systems.We firstly propose the forward sequential feature selection algorithm for incomplete decision systems based on the fact that that the discernibility of an incomplete decision system will not change with its unchangeable positive region;then we generalize the algorithm to heterogeneous incomplete decision systems based on neighborhood rough sets theory;finally we extend the fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets to the heterogeneous incomplete decision systems based on neighborhood rough sets theory to accomplish the feature subset selection procedure for incomplete decision systems with quantity or heterogeneous attributes.We rank features（attributes） in descending order according to their significance to positive region,then select the top one feature from current feature subset and add it to the reduction of attributes,whilst delete it from current feature subset,where the attribute reduction subset is empty at first,while current feature subset is initialized with all features.Theoretical analysis and experimental results on datasets from University of California Irvine（UCI） machine learning repository demonstrate that our forward sequential feature subset selection algorithms for incomplete decision systems based on neighborhood rough sets are more efficient than the backward feature subset selection algorithms.The potential disadvantage of our forward sequential feature subset selection algorithms is that the feature subset selection procedure may not be completed for the first important feature cannot be found at the first iteration.