一种基于向量夹角的快速计算等价类算法

New Rapid Algorithm to Calculate the Equivalence Class Based on Vector Angle

等价类是Rough集理论的核心概念之一,如何高效地计算等价类是提高各相关算法性能的关键.引入高维空间向量夹角的概念,根据数据在机器中的存储特点,以字节内容的最大值加1作为基数对数据进行基数排序,在此基础上设计以计算向量夹角来求信息系统等价类的算法.该算法把原来计算等价类的逻辑比较转换为数值计算,非常显著地提高了等价类的计算效率,尤其对大规模高维数据.该算法的时间复杂度为O(|C‖U|log|U|),理论分析与实验结果表明了该算法的正确性和高效性.

Equivalence class is one of the core concepts of the Rough set theory. The efficiently calculation of equivalence class is the key to improve the performance of related algorithms. The paper introduce the concept of high dimensional space vector angle, and according to the characteristics of data stored in machine, This algorithm use radix sort method to sort the data by byte content maximum value plus 1. And on this basis the paper design an algorithm to calculate the equivalence class of information system with calculating the vector angle. By converting the logical comparison of the original calculation of equivalence class to the numerical calculation, the algorithm can significantly improve the efficiency of the calculation of equivalence class, especially for large-scale high-dimensional data. The time complexity of this algorithm is O（｜C‖U｜log｜U｜） ,the theoretical analysis and experimental results show the validity and effectiveness of the algorithm.