用序关系求信息熵核的高效算法

目前设计基于信息熵的求核算法的主要方法是差别矩阵方法.在该种方法中,是通过搜索差别矩阵的所有差别元素得到核.由于是在所有的差别元素上搜索,故该方法比较耗时.为此,在简化决策表和简化差别矩阵的基础上,得到了核的一个新性质:当把简化决策表的对象按其条件属性值看成一个数时,其对象有序.利用这个序,只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,设计了一个高效求核算法,其时间复杂度max{O(|C|2 |U/Cl),O(|C ||U|)},其空间复杂度为O(|U|).由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了有效地改善.     

基于序关系的快速计算正区域核的算法

目前设计基于正区域的求核算法的主要方法是差别矩阵方法.该方法通过搜索差别矩阵的所有差别元素来得到核,故比较耗时.为此,在简化决策表和简化差别矩阵的基础上,若将其对象按条件属性值看成一个数,则对象是有序的.利用这个序,可将具有核属性的差别元素集映射到一个较小的搜索空间上,故只需判断简化差别矩阵的少量差别元素就可以找到核属性集.在此基础上,利用基数排序的思想,设计了一个高效求核算法,其时间复杂度为O(|C|2|U/C|)+O(|C||U|),空间复杂度为O(|U|).由于新算法只需判断简化差别矩阵的少量差别元素就可以找到核算属性集,故算法的效率得到了改善.     

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

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

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

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i相似文献   

一种不完备决策表的差别矩阵求核算法

计算不完备决策表的核属性是粗糙集理论的重要内容之一。目前关于不完备决策表的求核算法的研究相对较少,而且在一般的求核算法中,其时间复杂度为[O(|C||U|2)]。为了有效地降低算法的时间复杂度,给出了一个不完备决策表的差别矩阵定义和基于差别矩阵的核定义,并证明了该定义与基于不完备决策表的核定义是等价的。在此基础上,利用差别矩阵方法来设计一种计算不完备决策表的求核算法,其时间复杂度降为[O(|C||Upos||U|)]。最后用仿真实例说明了新算法的有效性。     

基于可分辨矩阵的快速求核算法

目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.     

基于区分对象对集的高效属性约简算法

给出区分对象对集的定义和基于区分对象对集的属性约简的定义,证明该定义与基于正区域的属性约简定义等价.由于求区分对象对集时,要求出U/C,故设计一个高效的求U/C的算法,其时间复杂度降为O(| C | | U |).进而提出一个基于区分对象对集的高效属性约简算法,其时间和空间复杂度分别降为O(|C| | U |)+O(| C| | U/C|2)和O(| U |)+O(| U/C |2).用1实例说明该算法的高效性.     

基于二进制有序差别集的属性约简算法

文献[6]给出的基于简化二进制可分辨矩阵的快速属性约简算法是不完备的,并且在处理大数据集时的效率不很理想.提出一种基于二进制有序差别集的属性约简算法,该算法不需要创建二进制可分辨矩阵,减少了数据处理量,大大提高了约简的效率,使算法的时间复杂度和空间复杂度分别降为max{O(|C|2|U/C|2),O(|C|2|BMsCount|)}和O(|BMsCount |).最后的实验结果表明该算法是正确的、高效的.     

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

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

改进的差别矩阵及其快速求核算法

求核是粗糙集中一个重要的研究内容之一。本文对杨明的基于差别矩阵求核方法进行研究,实例表明其方法还存在一些不完善。为了能够进一步提高求核效率,对差别矩阵进行改进,提出一种简化差别矩阵的定义,并给出求核方法,同时证明了由该方法获得的核与正区域的核是等价的,由此设计求核算法,其时间复杂度为max{O(|C||U|),O(|C||U/C||U′1|)},空间复杂度为O(|C||U/C||U′1|)。实验表明,该算法是有效的、高效的,且能适合大数据集的处理。     

基于区分对象对的不完备决策表求核

在差别矩阵的基础上,针对不完备决策表提出了基于差别矩阵的区分对象对集定义,并证明求不完备决策表的核可以转化到求基于差别矩阵的区分对象对集上。在此基础上,提出了一种基于区分对象对的不完备决策表求核算法,该算法的时间复杂度为：[max{O(|C||U||Upos|),O(K|C||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｜))｝。     

不完备决策表中基于对象矩阵属性约简算法

基于差别矩阵的属性约简是粗糙集属性约简中最常用的方法。对通常给出的以存储条件属性为基础差别矩阵进行比较后,给出一种对象矩阵的定义。对象矩阵从相容类内对象的决策值与条件属性的关系出发,存储的是对象集。给出对象矩阵的属性约简定义,证明了属性约简与基于正区域的属性约简的等价性。给出一个启发式的属性约简算法,其时间复杂度为max(O(|C|2|Upos||U|),O(|C||U|2)),空间复杂度为O(|C||U|2);通过实例说明方法的可行性。     

基于有序差别集的高效属性约简算法

基于可分辨矩阵的属性约简算法需要占用大量的存储空间,可分辨矩阵中许多元素项对约简是多余的;并且随着问题规模的增大,该类算法的效率并不理想。针对上述不足,提出一种基于有序差别集的属性约简算法,该算法不需要创建可分辨矩阵和生成多余的元素项,大大降低了存储量和计算量,从而提高了属性约简效率,使算法的时间复杂度和空间复杂度分别降为max{O（|C|² |U/C|²）,O（|C|²|MsCount|）}和O（|MsCount|）。实验表明该算法是有效的、高效的。     

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

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出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｜））}。     

一种改进的基于二进制可分辨矩阵属性约简算法

指出支天云的二进制可分辨矩阵约简算法存在的不足,给出简化的决策表定义和基于二进制可分辨矩阵的属性频率函数的定义。在此基础上,以核属性为初始约简集,以属性频率为启发式信息,提出了一种改进的基于二进制可分辨矩阵的属性约简算法,其最终可以获得一个最优约简,并且算法时间复杂度和空间复杂度分别为max{O（｜C｜ ｜U｜）,O（｜C｜^2｜ ｜U｜^2）}和0（｜C｜ ｜U｜^2）。通过实例验证,表明该算法是有效的。     

一种快速属性核求解算法

在Rough Set理论中,计算属性核是最重要的计算之一。以桶排序的思想设计了一个新的求解U/C的算法,其时间复杂度被降为O（|C||U|）。基于此,提出了一个新的求核算法,其时间复杂度被降为[O(|C|2|U|)]。通过实验证明了求核算法的高效性。     

基于数据库的属性约简模型的快速求核算法

对于基于数据库系统的属性约简模型,给出相应的简化差别矩阵和相应核的定义,并证明该核与基于数据库系统的属性约简模型的核是等价的。在此基础上设计了一个新的求核算法,其时间复杂度和空间复杂度分别为max{O（|C||U/C|²）,O（|C||U|）}和O（|U|）。