论文部分内容阅读
目前设计基于信息熵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.为此,在简化决策表和简化差别矩阵的基础上,得到了核的一个新性质:当把简化决策表的对象按其条件属性值看成一个数时,其对象有序.利用这个序,只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,设计了一个高效求核算法,其时间复杂度m ax{O(|C|2|U/C|),O(|C‖U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.
At present, the main method of kernel algorithm based on information entropy is differential matrix method, in which the kernels are obtained by searching all the difference elements of the difference matrix. Since this method searches for all the difference elements, Therefore, on the basis of simplifying the decision table and simplifying the difference matrix, a new property of the kernel is obtained: when the objects of the simplified decision table are regarded as a number according to their condition attribute values, the objects are ordered. We can find the kernel attribute set just by judging a few difference elements of the simplified difference matrix.On the base of this, we design an efficient algorithm for finding kernels, whose time complexity m ax {O (| C | 2 | U / C | ), O (| C | U |)}, and its space complexity is O (| U |). The efficiency of the new algorithm is obtained because the new algorithm can only find the set of accounting attributes by judging only a few difference elements of the simplified difference matrix Effectively improve.