基于局部条件区分能力的高效属性约简算法

作     者：康猛 蒙祖强 KANG Meng;MENG Zuqiang

作者机构：广西大学计算机与电子信息学院广西南宁530004 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2022年第42卷第2期

页      面：449-456页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(61762009) 

主　　题：属性约简 区分矩阵 区分能力 条件区分能力 大数定律 局部条件区分能力 

摘      要：基于区分矩阵的传统属性约简方法具有直观易理解的优点,但时间和空间复杂度都很高,当数据规模较大或条件属性较多时,会无法快速得到约简结果。为解决该问题,在区分关系的基础上构造了条件区分能力来进行属性选择,提出一种基于条件区分能力的属性约简算法。而为了进一步加快属性重要性的计算、提高约简效率,依据大数定律中频率的稳定性,通过采样的方式将条件区分能力扩展为局部条件区分能力,提出基于局部条件区分能力的属性约简算法。理论证明了条件区分能力在属性的选择上比正区域更严格,并将该算法与基于区分度的高效前向属性约简算法(FAR-DV)、基于k近邻属性重要度和相关系数的属性约简算法(K2NCRS)及基于正区域排序升序决策表的快速正区域约简算法(FPRA)进行了对比。实验结果显示,该算法在属性选择顺序、约简率和分类精度上与FARDV基本一致,在约简效率上比上述三种算法提高了10倍以上;且随着数据规模的增大或条件属性的增多,在约简效率上的提升越明显。可以看出,所提算法具有更低的时空复杂度,适用于海量数据属性约简。