基于抽样的随机约简算法

属性约简作为粗糙集理论的一个重要应用被较多学者关注。然而,由于其计算复杂度与数据的规模成平方级增长,基于粗糙集的属性约简在大规模数据上的应用效率较低。考虑到随机抽样是降低大规模数据的计算的一种有效的统计方法,因而我们将其引入约简算法中,提出一种随机约简算法,从而大幅提升了属性约简的效率。该算法的主要贡献是基于最小冗余和最大相关的选择属性过程中引入了随机抽样的思想。首先,在每次选择最重要属性时,并不需要在所有的示例上计算依赖度,而是随机选了部分示例,从而既选择了最大相关的属性,又大大降低了算法的计算复杂度。其次,在选择属性的过程中,每次迭代的样本是不同的,而且样本之间具有较少的信息交叉,从而选取了最小冗余的属性。最后,通过数值实验,我们比较了随机约简算法与非随机约简算法的性能。