基于链表结构的启发式属性约简算法

梁 宝 华

(巢湖学院计算机与信息工程学院　安徽 合肥 238000)



基于链表结构的启发式属性约简算法

梁 宝 华

(巢湖学院计算机与信息工程学院安徽 合肥 238000)

属性约简是粗糙集理论研究的主要内容之一，正区域计算是多数属性约简算法的关键。为了减少正区域的计算时间，提出基于链表存储的正区域计算方法。将属性值相同的数据存储在链表同一结点对象中，收集过程中不断删除基数为1的子划分，通过降低样本数据的规模来减少计算耗时，加速属性约简。同时，给出不可区分对象对数定义，并以此度量属性重要性，设计一种高效的启发式属性约简方法。通过实例和实验与经典约简算法进行性能测试比较，结果证实该算法在时间和空间效果上切实有效、可行。

粗糙集属性约简链表正区域不可区分对象对数

0　引　言

RoughSet作为一种处理不确定、不精确数据的有力数学工具[1]，已广泛应用于机器学习、模式识别和数据挖掘等领域。属性约简是RoughSet研究的核心问题之一，也是知识获取的关键步骤。在保持区分能力不变的情况下，用较少属性表示数据集的特征。现有的属性约简算法有基于正区域属性约简算法[2]、基于信息熵的约简算法[3]、基于差别矩阵的属性约简算法[4,5]及其他启发式属性约简算法[6,7,12]。

多数属性约简算法先对挖掘的决策表进行简化，因为此过程效率高低影响整个算法的时间和空间性能。目前，求简化决策表效率较高的算法有文献[2]基于基数排序的属性约简算法，时间复杂度为O(|C‖U|)、基于文献[8]快速排序思想的属性约简算法，时间复杂度为O(|C‖U‖log(U)|)。……