基于RS理论的快速属性约简求核方法

粗糙集是用来处理不确定、不完备数据的重要工具之一.属性约简是粗糙集理论研究的一个重要内容,属性核则是属性约简所涉及的一个重要概念,对简化属性约简具有不可替代的重要性.文中指出属性约简的作用,及其涉及到的一个重要概念--属性核的概念和重要性.分析了目前常用求属性核方法,大都建立在内存中,需要构造差别矩阵.存在时空复杂度较大的不足.提出了一种无需建立差别矩阵的简单求属性核方法,并通过实例验证了正确性.     

一种基于改进差别矩阵的核增量式更新算法

提出一种基于改进差别矩阵的核增量式更新算法,主要考虑对象动态增加情况下核的更新问题．该算法在更新差别矩阵时仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核的更新效率．理论分析和实验结果表明,该算法是有效可行的．     

基于优势区分矩阵的求核方法

在提出基于优势关系粗糙集方法下的类区分矩阵概念后,为解决不一致数据问题,新的优势区分矩阵定义及其求核方法被提出,但是该方法计算代价高。为了能够快速求出存在不一致数据的信息系统的核,该文给出改进的优势区分矩阵定义和求核算法,其空间和时间复杂度都优于现有的算法。实验证明,该算法适用于处理大数据集。     

不完备信息系统中一种新的求核算法

在不完备信息系统基于差别矩阵的属性约简算法中,相容类和最大相容类中的对象具有不确定性.针对上述问题,提出一种新的差别矩阵及其核的定义,证明在不完备信息系统中该差别矩阵的核与基于正区域的核是一致的.在此基础上给出一个求核算法,通过实例证明,由于减少了差别矩阵中的元素,因此算法的求核效率得到较大提高.     

改进的优势区分矩阵及其求核方法

研究了优势关系下不协调决策表的优势区分矩阵及其求核方法。用反例指出利用文献[6]中的优势区分矩阵来求核的方法是错误的,给出一个改进的优势区分矩阵的定义和求核方法,其空间和时间复杂度都优于现有的算法。     

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

为获取一个较优的属性约简集,在对粗糙集中基于差别矩阵的属性约简算法研究的基础上,文中提出了一种新的属性约简算法.该算法对由差别矩阵得到的属性差别集进行运算,得到一种集合内元素之间没有包含关系的新集合,在分析该集合性质的基础上,给出针对该集合的一个较优属性约简集.最后对时间复杂度进行了分析,并给出了完备性证明.     

基于差别矩阵的属性核快速更新算法

核求解是粗糙集理论的重要内容之一,尽管在核求解问题上已有大量的研究成果,但有关核更新算法的报道却不多,有人提出一种在对象增加情况下核的增量式更新算法,但未讨论对象动态删除的情况．对此,提出一种基于差别矩阵的属性核快速更新算法——FUAC．该算法在更新差别矩阵时仅需删除某一行及某一列,或插入某一行,因而可有效提高核的更新效率．理论分析表明,该算法是有效可行的．     

一种新的决策表核属性计算方法

属性约简是粗糙集理论研究的一个核心问题,而核属性的确定往往是决策表中属性约简的基础。结合决策表的树型结构表示,给出了决策表中正域和非正域的计算方法,并从核属性的定义出发,计算树型决策表中正域和非正域相对于属性全集正域和非正域的变化,提出了一种计算决策表中核属性的方法。对其时间和空间复杂度的分析,以及对一个气象决策表例子的实验结果,证明了这些方法的有效性。     

差别矩阵浓缩及其属性约简求解方法

属性约简是粗糙集理论的重要研究内容之一,已出现大量的属性约简算法,其中基于差别矩阵的属性约简算法是高效属性约简算法之一,但这些算法主要针对一致决策表,而对于不一致决策表,某些情况下不能得到属性约简。为此,本文提出改进的差别矩阵及其属性约简求解方法,统一考虑决策表一致和不一致情况两种情况下的属性约简,有效改进经典的基于差别矩阵求解属性约简的不足。同时,为适应大数据集属性约简需要,提出一种新的差别矩阵浓缩策略,以此提高属性约简的效率。     

一种基于不完备决策表的求核方法

求核是粗糙集理论的重要研究内容之一,现有的求核算法大部分都是基于完备决策表的,对基于不完备决策表的求核研究很少。提出了不完备决策表二进制差别矩阵的构造方法,在此基础上,利用二进制差别矩阵设计了一种不完备决策表的求核算法。从理论上证明了基于二进制差别矩阵的求核与基于正区域的求核是相等的。新算法的时间复杂度是[O(|C||U|2)],用实例分析说明了新算法的正确性。     

一个基于差别矩阵思想的高效求核算法

目前,关于属性约简已有不少算法,其中在很多算法中,都要求先求出核属性集,但利用差别矩阵求核属性这一算法中,生成差别矩阵时,有许多不必要的元素被生成,这些无用的元素在求核时又要进行比较,因而效率不高。利用差别矩阵的思想设计一种不必生成那些不必要的元素的求核算法,从而使算法的效率得到提高。最后,给出了一个实例说明新算法的高效性。     

一种基于改进区分矩阵的属性约简算法

现有的很多约简算法都是由构造决策表的区分矩阵出发,将矩阵中非空元素的合取范式转化为极小析取范式。但是,基于Skowron提出的区分矩阵约简算法对不相容决策表会产生错误的结果。为此,提出一种改进的区分矩阵的定义,以及基于此区分矩阵的属性约简算法,该算法对相容或不相容决策表都是适用的,特别对不相容决策表会得到更加稀疏的区分矩阵,可大大节省计算时间和存储空间,该算法是一种简单、有效、普遍适用的求解属性约简方法。     

一个新的二进制可辨识矩阵及其核的计算

首先用反例指出文献[4]中的利用R．Felix等人提出的二进制可辨识矩阵来求决策表的相对核的方法是错误的，然后给出一个新的二进制可辨识矩阵的定义和求核方法，并从理论上证明了方法的正确性。     

基于压缩树的快速求核算法

利用差别矩阵进行求核运算时,矩阵中大量的空元素和重复差别元素会浪费很多存储空间及计算时间。针对上述问题,结合频繁模式树,设计一种新的数据结构——压缩树(C_Tree),在此基础上提出一种快速求核算法。理论与实例分析结果证明,该算法的时空复杂度取决于求简化决策表和构造C_Tree的时空复杂度,因此求核效率得到较大的提高。     

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

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

一种基于区分矩阵的属性约简算法

属性约简是粗糙集理论研究的关键问题之一。文章以属性在区分矩阵中出现的频率作为启发,对HORAFA算法做了一些改进。它是以核为基础,加入属性重要性最大的属性,直到不能再加。为了能找到信息系统的最优约简,在此基础上加了一个反向消除过程,直到不能再删为止。最后通过一个实例完整演示了该方法,证实其有效性。     

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

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