基于区分对象对集的快速求核算法

Quick algorithm for computing core based on discernibility object pair set

为降低基于正区域求核算法的时间复杂度,首先给出了简化决策表和简化差别矩阵及其核的定义。然后给出了简化决策表中条件属性的区分对象对集的定义,并得出区分对象对集与决策表核属性的关系,证明了求决策表的核可以转化到求条件属性的区分对象对集上。再结合简化差别矩阵的核的性质,设计了一个基于区分对象对集的快速求核算法。该算法的时间复杂度优于同类算法的时间复杂度。最后用实例说明了新算法的有效性。

For cuting down the time complexity of the algorithm for computing core based on the positive region, the definitions of simplified decision table and simplifed discernibility matrix and the core correspond to simplifed discernibility matrix based on the positive region are first provided. Then the definition of discernibility object pair set of condition attribute in simplified decision table is proposed. At the same time, the relationship between the discernibility object pair set and the core of decision table is obtained. Acoording to this relationshp, it is proved that computing the core of decision table is equal to computing the discernibility object pair set. By considering the property of the core correspond to simplified discernibility matrix, a new algorithm for computing core based on the discernibility object pair set is designed. Its time complexity is better than the time complexity of the same kind of algorithms. Finally, an example is used to illustrate the effectiveness of the new algorithm.