基于简化的二进制差别矩阵的快速属性约简算法

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出IND（C），故设计了一个较好的求IND（C）的算法，其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法，其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。

基于简化的二进制差别矩阵的快速求核算法

目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为m ax{O(C(U’p os‖U/C)),O(C‖U)}和m ax{O(U),O(C(U’p os‖U/C))}.

简化的二进制差别矩阵属性约简算法的改进

目前,基于二进制差别矩阵的属性约简算法有以下不足:所得到的属性约简与基于正区域的属性约简不一致。文献[7]中给出一种基于简化的二进制差别矩阵的快速属性约简算法,但该算法不完备。分析了算法不完备的原因,在此基础上,提出了一种改进的完备算法,该算法的时间复杂度为max(O(∣C||U∣),O(∣C∣2∣U pos||U/C))。

基于信息熵的二进制差别矩阵属性约简算法

给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O(|C||U)|。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O(|C||U)|,O(|C|2|U/C|2)}和max{O(|C||U/C|2),O(|U)|},最后用一个实例说明了新算法的高效性。

一种使用二进制差别矩阵的属性约简方法

针对区分矩阵属性约简算法中区分矩阵存在空值元素和重复元素等缺点,提出了一种基于二进制差别矩阵的属性约简算法.该算法不仅保证了属性约简的完整性和正确性,同时也降低了运算所需的时间和空间.

一个基于修正的二进制差别矩阵的快速求核方法

本文研究了二进制差别矩阵中核属性的性质,指出并证明了二进制差别矩阵求核的理论依据,在此基础上给出了一种二进制差别矩阵的修正方法及求核方法。该方法不仅适用于任何决策表信息系统(相容决策表和不相容决策表),而且有效地降低了计算代价。

基于简化差别矩阵的完备属性约简算法

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。

基于系统熵的属性约简的简化差别矩阵方法

基于系统熵的属性约简是一种新型的属性约简。该模型由于同时考虑了条件属性集和决策属性集对决策表的分类能力,它是一种考虑较周全的属性约简模型。为设计高效的属性约简算法,首先引入简化差别矩阵,同时给出了基于该简化差别矩阵的属性约简定义,并证明该定义与基于系统熵的属性约简定义等价;然后用简化差别矩阵设计了一个基于系统熵的完备属性约简算法;最后用实例说明了新算法。

基于二进制区分矩阵的离散化算法

提出离散化中基本二进制区分矩阵的定义及其简化方法和基于简化二进制区分矩阵的离散化算法,把符号运算转变成二进制运算,有效地节约了存储空间和运算时间。从区分度和区分率两个不同层次考察断点的重要性,引导求解过程趋于最优化,只采用新增加的断点对应位与矩阵的行相应位进行运算,进一步提高计算效率。实例分析表明算法是正确有效的。

对新简化差别矩阵的研究

通过反例证明当决策表含不一致对象时,无法通过简化差别矩阵得到正确的核和约简。产生该问题的原因在于简化差别矩阵和简化决策表对不一致对象的处理均存在欠缺。提出新简化差别矩阵(NSDM)定义,通过利用新简化决策表把一致对象和不一致对象分开存放的特点修正了这两处缺陷。NSDM能够处理含多种不一致对象的决策表,并且能够得到正确的核和约简。利用前人的基于差别矩阵的求核和求约简算法分别以NSDM和简化差别矩阵为基础求核和约简,然后再利用核和约简的定义求核和约简,通过比较证明以NSDM为基础得到的核和约简是正确的。这说明NSDM可以有效地处理不一致对象并且通过NSDM能够得到正确的核和约简。这个实验同时验证了原有的以差别矩阵为基础的求核和求约简的算法不加改动就可以在新差别矩阵上使用。

一个基于差别矩阵的快速求核算法

给出简化差别矩阵和相应核的定义,并证明该核与差别矩阵的核是等价的。在此基础上设计了一个新的求核算法,使得新算法的时间复杂度和空间复杂度分别被降为max｛O(CU/C2),O(CU)｝和max｛O(U),O(CU/C2)｝。

基于修正差别矩阵的高效属性约简算法

为降低基于修正差别矩阵的属性约简算法的复杂度,给出了基于修正差别矩阵的简化差别矩阵,证明了基于该简化差别矩阵的属性约简定义与基于原修正差别矩阵的属性约简定义是等价的.在此基础上设计了一个基于简化差别矩阵的属性约简算法,其空间和时间复杂度分别被降为O(|C|(|U′pos||U/C|))和max{O(|C|2(|Up′os||U/C|)),O(|C||U|log|U|)}.实例说明:用新算法进行属性约简,不仅减少了计算量,而且减少了存储空间,因而是一种高效的属性约简算法.

一种快速计算HU差别矩阵的属性约简算法

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度,首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.

一个计算Skowron差别矩阵核的新算法

为提高基于Skowron差别矩阵的求核算法的效率,引入简化决策表的定义,给出了简化Skowron差别矩阵和相应核的定义,证明了新核与基于Skowron差别矩阵的核是一致的。提出一个基于Skowron差别矩阵的快速求核新算法,其时间复杂度和空间复杂度分别降为max{O(|C||U/C|2)O(|C||U|)}和max{O(|U|)O(|C|)}。

基于差别矩阵的完备属性约简算法

基于差别矩阵思想的属性约简算法需要求出决策表的差别矩阵,然而差别矩阵的求取不但费时而且占用大量的存储空间。为此,提出一种基于差别矩阵中非空对象个数的改进属性约简算法。在利用差别矩阵思想的同时不生成差别矩阵,并给出属性重要度的定义及其快速计算公式,只需要U'POS和U'NEG就能计算出属性重要度。实例分析证明,该算法能节省计算时间,求出最小属性约简。

基于浓缩差别矩阵的规则获取算法

基于HU的差别矩阵方法不仅构造费时且占用空间大,使得执行效率不高。利用元素间两两比较的方法构造浓缩差别矩阵的算法则时间复杂度过高,不适用大数据的处理。而将差别元素压缩存储在一棵FP树上,却无法去除无用的元素。为此,引入二叉树的思想,对短差别集依次建树,长差别集依次进行比较查找,提出一种改进的浓缩差别矩阵算法,在此基础上,给出扩展的二进制差别矩阵,直接从矩阵中提取规则。实验结果证明,该算法不仅降低了时间复杂度,还能够去掉无用元素,减少存储空间。

基于二进制链表的粗糙集属性约简

差别矩阵是很多学者用来计算粗糙集属性约简的一种方法,该方法因其简单、直观、易于理解而得到广泛应用,但是包含在差别矩阵中的冗余元素不仅对属性约简不起作用反而增加存储空间,为消除这些冗余元素提出了一种新的存储结构:二进制链表,通过位运算将差别矩阵中所有的重复元素和父集元素删除,降低差别信息的存储空间。为验证二进制链表的有效性,提出了一种新的属性约简算法。通过UCI数据库中多组数据集对该方法进行测试,并将实验结果与其他算法进行比较,提出的算法可以更快地得到属性约简集并且能够有效地降低存储空间。

基于正区域和差别元素的增量式属性约简算法

决策表数据的动态变化要求约简结果不断更新,为了在保证得到最简约简结果的同时提高属性约简的效率,提出一种改进的决策表约简算法,得到一个和原决策表等价的简化决策表。在此基础上,综合正区域和差别矩阵两种思想并利用原决策表的约简结果,给出一种仅存储由新增对象所产生的差别元素的增量式属性约简算法。实例计算结果表明,该算法能在原决策表约简结果的基础上快速更新属性约简结果。

基于有序差别集和属性重要性的属性约简

针对粗糙集理论的属性约简问题,提出新的差别矩阵简化算法,该算法在无需排序和较少遍历次数的情况下简化了差别矩阵,明显提高了简化速度并最终得到简化的有序差别集。实验验证了该算法的高效性;给出度量属性重要性的新标准,即根据属性所在差别矩阵元素的权重、在差别集中出现的频数和吸收能力3方面来度量其重要性;在上述两者基础上,提出一种基于有序差别集和属性重要性的属性约简新方法,理论分析证明新方法的最坏时间复杂度低于其它基于差别矩阵的属性约简算法。大量实验结果也表明,新方法的有效性甚至可以在很大程度上得到最小属性约简。

基于简化差别矩阵的属性约简算法

为降低基于修正差别矩阵的属性约简算法的时间复杂度和空间复杂度,首先给出了简化差别矩阵的定义,并证明了该矩阵所包含的信息量与修正差别矩阵的信息量等价.其次设计了一个高效的求U/C的算法,其时间复杂度被降为O∑|C|i=1|ki||U|.然后分析了基于修正差别矩阵的属性约简算法的不足,并使用上述高效求U/C的算法,设计了一个基于简化差别矩阵的属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为maxO(|C|2(|Up′os||U/C|)),O∑|C|i=1|ki||U|和max{O|C|(|Up′os||U/C|)),O(|U|)}.最后用一实例说明了新算法的高效性.