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

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

基于Skowron差别矩阵属性约简的矩阵表示

针对目前基于Skowron差别矩阵的属性约简中缺少矩阵表示的问题,定义一种新的矩阵,并给出基于新矩阵的属性约简定义,证明该定义与基于Skowron差别矩阵的属性约简等价。以矩阵为基础,定义属性的重要性,设计一个基于Skowron差别矩阵的属性约简算法,实例证明了算法的有效性。

基于粗糙集Skowron差别矩阵的矿井火灾风险评价指标约简

在安全评价过程中,当构建的指标体系过于庞大,数据繁琐,不利于进行安全评价工作。为了对矿井火灾风险评价指标体系进行快速简化,基于粗糙集理论属性约简功能,采用理论与实例分析相结合的方法,利用Skowron差别矩阵算法对矿井火灾风险评价决策表进行属性约简。研究表明:通过约简,矿井火灾风险评价指标由原来的16个缩减为6个,大大减少了后续评价过程中权重确定的计算量,降低了评价的复杂程度,减少了评估工作量。同时约简结果也为矿井火灾防治工作提供了一些指导意见,体现了差别矩阵在决策表的属性约简中的高效性。

基于Skowron差别矩阵的建筑施工安全评价指标约简

为了科学合理地对建筑施工现场安全评价指标进行优化,在结合相关规范标准和实地调研的结果等基础上,构建了建筑施工现场安全评价的指标;然后,运用粗糙集理论中Skowron差别矩阵对指标进行了约简。结果表明:在不影响结果的前提下,通过约简,建筑施工现场安全评价指标由15个缩减为5个,减少了后续的评价工作量,同时也为建筑施工现场预防安全事故提供指导。

基于三支决策的差别矩阵属性约简算法

属性约简是粗糙集理论研究的核心内容之一,也是粗糙集理论的重要组成部分。该方法旨在减少冗余信息,提取出最具代表性和关键性质的属性集合。在属性约简的过程中,差别矩阵通常用于度量属性之间的关系,通过分析差别矩阵,研究者可以识别那些在描述系统行为方面贡献相似信息的属性,从而进行属性约简。基于三支决策的差别矩阵属性约简算法从差别矩阵的属性出发,首先刻画核以外的属性重要度,并以三支决策理论为基础构建一种新的属性约简方法。算法将传统概率粗糙集的上、下近似划分为三支决策中的正域、负域、边界域,基于不同的区域给出了决策规则,并通过决策损失函数来控制三支决策阈值。与同类算法相比,所提算法可以得到更为简洁的约简集和决策规则,且具有更小的时间复杂度。

基于信息熵和差别矩阵的属性约简方法

针对无决策属性的信息系统,定义了无决策属性的差别矩阵,利用商空间理论下信息熵的计算方法,提出了一种“空不变”无决策属性约简方法。该方法从属性约简的本质出发,将属性造成等价类发生改变的可能性数值化,进而实现属性约简。通过实例验证了方法的有效性,并通过与已有方法的对比和实验结果分析,进一步证实了该方法能更准确地识别出关键属性,完成属性约简。

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

给出简化差别矩阵和相应核的定义,并证明该核与差别矩阵的核是等价的。在此基础上设计了一个新的求核算法,使得新算法的时间复杂度和空间复杂度分别被降为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|)}.实例说明:用新算法进行属性约简,不仅减少了计算量,而且减少了存储空间,因而是一种高效的属性约简算法.

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

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

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

为了解决基于差别矩阵的属性约简完备算法得不到最小约简的问题,提出了一种改进的属性约简方法.该方法将信息论定义的属性重要性作为启发式信息,并通过构造一个条件信息熵算子对差别集合进行运算,同时利用算子来计算候选属性的剔除次序,采用宽度优先搜索策略使约简集合中含有最重要的属性,这样就解决了完备算法约简率低的问题.结合该方法并在分析对象集增量与差别矩阵关系的基础上,证明了增量约简定理,由此提出了一种增量式约简完备算法(CAIR),当新数据加入决策表时,算法可增量构造差别集合.实验结果表明,所提CAIR在大大缩短计算差别集合时间的同时,约简率比非完备算法提高了20.3%,是同条件下完备算法执行效率的13.2倍.

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

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

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

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出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｜))｝。

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

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

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

差别矩阵非空元素的个数,直接影响基于差别矩阵的Rough集属性约简算法的效率。分析了几种差别矩阵的不足,基于此,重新定义了一种差别矩阵,该差别矩阵把划分U/C={[x1]C,[x2]C,…,[xn]C}的一个等价类看成一条规则参与区分,从而大大减少了差别矩阵非空元素的个数,提高了Rough集属性约简算法的效率。给出了这几种差别矩阵非空元素的计算公式及其相关定理。提出了一种带启发式知识的约简算法,该算法在很大程度上能找到决策表的最小属性约简。最后给出了对UCI一些数据库的仿真结果。

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

分析了传统属性频率函数作为属性重要度的不足,重新定义了属性重要度,提出了一种基于差别矩阵属性重要度的属性约简完备算法,即CRABSA(Complete Reduction Algorithm Basedonthe Significance of Attribute)。该算法采用迭代思想,在每次迭代过程中根据属性重要度SGF(a)选择必要的条件属性加入约简R中。由SGF(a)的定义可知,算法能确保在大多数情况下能得到决策表的最小约简。分析了算法在最坏情况下的时间复杂度,给出了该算法相对Pawlak约简的完备性的证明。

基于简化差别矩阵的增量式属性约简

新对象添加到决策表后,已有的属性约简将会发生改变,需要对其动态更新。为此,首先给出简化决策表和简化差别矩阵的定义,并证明了基于简化差别矩阵的属性约简与正区域的属性约简是等价的;然后,分析增量对象的不同情况,将增量属性约简映射到简化决策表上来实现,由此设计基于简化差别矩阵的增量式属性约简算法,并对算法进行改进;最后,利用实例和实验验证了所提出算法的正确性和高效性。

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

提出了一种基于差别矩阵的粗糙集属性约简完备算法,算法的求解策略是在每次迭代过程中只选择必要的条件属性,如果在某次迭代过程中找不到这样的条件属性,则任意排除一条件属性,为下一次迭代中找到必要的条件属性做准备.分析了算法在最坏情况下的时间复杂性,给出了该算法相对Pawlak约简的完备性的证明.同已有的同类约简算法相比,该算法在最坏情况下具有更小的时间复杂性.

三种差别矩阵的比较

差别矩阵是Rough集理论中重要概念之一,使用差别矩陈可以计算决策表的核和约简。当前有多种定义差别矩阵的方法,导致差别矩阵有多种定义的原因是决策表的不一致性。本文分析一致决策表和不一致决策表关系,给出将不一致决策在转换为一致决策表的方法,并给出差别矩阵的等价性定义。在此基础上,讨论并证明三种差别矩阵的关系,结果表明利用这种转换方法和等价性定义可以将三种差别矩阵统一起来,从而保证在实际应用中可以用统一方法来构造差别矩阵。

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

基于差别矩阵的属性约简算法是重要的属性约简算法之一,它具有直观、易于理解的性质.由于在构造差别矩阵的时候往往会产生大量的重复元素以及无用的元素,这不仅浪费了大量的空间,还大大降低了算法的高效性.在现实生活中这种数据往往是不可避免的.本文以去掉重复元素以及降低无用元素的个数为目的构造了一个二叉树来存储差别属性集,该二叉树在保留直观、易于理解的特征的前提下降低了存储空间.然后设计了一个相应的算法,该算法依据差别矩阵属性约简的思想,对二叉树进行减枝处理,实现最终的属性约简,最后用实例说明算法的高效性.

基于不完备决策表的正区域属性约简的压缩差别矩阵方法

差别矩阵、二进制差别矩阵方法易懂,易设计,一直以来为广大学者所喜欢。但两方法在运算时会产生大量的重复元素与无用元素(若A是B的子集,则称B是A的无用元素),这些重复、无用元素会占用大量的空间,影响算法的效率。针对以往文献中基于差别矩阵的属性约简算法存储代价高的问题,结合二进制差别矩阵引入二叉树(B_Tree)的设计思想,提出基于压缩存储的属性约简算法。该算法将二进制差别矩阵的属性集存储在二叉树(B_Tree)的相应路径上,通过边存边剪枝(剪枝的思想就是从二叉树上删除那些在同一条路径上的重复、无用属性集)的思想,有效地降低了算法的时空效率。最后通过实例分析验证了新算法的有效性和可行性。