不完备信息系统下的一种概率属性约简算法

不完备信息系统中的属性约简一直是粗糙集研究领域的一个难点．在不完备信息系统中,用以往的属性约简算法得到的约简结果中,某一属性要么属于该约简,要么不属于该约简．但在实际生活中,当属性以比较大的概率可区分两对象时,这就表明该属性可能以某一概率属于约简结果．基于这种想法,文中通过构造概率区分矩阵,并在此基础上给出相应的区分函数,提出了一种概率属性约简算法,分析了算法正确性．从该算法得到的约简,可以看出各属性属于约简的可能性．最后用实例表明该算法是有效和可行的．     

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

根据粗糙集理论讨论了属性约简问题,基于传统的区分矩阵属性约简算法提出了一种改进的约简算法:首先,根据决策表构造区分矩阵;然后,删除区分矩阵中包含核和伪核的项;最后,化简区分矩阵中剩余项得到约简结果.通过对某发动机故障数据进行处理验证了算法的有效性.     

基于区分矩阵求决策算法的约简

利用区分矩阵的特点，给出了另一种求决策表的属性约简与属性核、决策规则的约简与核的方法，进而给出了一种求决策算法约简的方法，这种方法简单易行，尤其在求决策规则约简时更体现了它的优越性。     

粗集理论的属性约简在石化营销信息处理与决策中的应用

属性约简是粗集理论的一个重要问题,而基于区分矩阵的属性约简是其主要算法之一,在最近几年被广泛研究。本文将粗集理论引入到石化营销决策中,通过基于区分矩阵的属性约简,生成营销决策规则,为拓展粗集的应用领域做出了有益的探索。     

基于区分矩阵和区分函数进行属性约简的数据分类

数据分类的方法直接影响着分类效果。用粗糙集理论中的区分矩阵和区分函数进行的属性约简可以很好地用于数据分类当中，基于此，提出一种数据分类方法，即用区分矩阵和区分函数约简掉信息系统中的冗余属性，得到必要的属性集；然后再约简掉每一条规则中的冗余属性值，提取出决策规则，最后按照决策规则进行分类。实验证明，用该方法实现的数据分类复杂馋低，且能有效提高分类效果。     

不一致决策表的分配序约简

在不一致决策表中定义了分配序约简，给出分配序一致集的判定定理。通过定义分配序区分矩阵给出求分配序约简的区分矩阵法。为克服区分矩阵法时间复杂度随系统大小的增加而指数增长的缺陷，通过定义属性的相对重要性，提出一种求分配序约简的启发式算法。通过实例分析说明启发式算法的有效性，为从不一致决策表中获取知识提供了一种有效方法。     

基于区分函数与强等价集理论的属性约简算法

提出了基于区分函数与强等价集理论的属性相对约简算法.在决策表的相对约简过程中采用区分矩阵来表达知识,并在区分函数的化简过程中引进强等价集的概念,通过去除强等价集的方法,使约简效率提高.现在已经证明,寻找决策表最小相对约简是典型的NP-hard问题,采用本文所提供的算法可降低问题复杂度,同时又可节省大量的计算存储空间.通过实例分析,证明该算法是求解全部属性相对约简的快速有效的方法.     

基于免疫遗传算法的粗糙集属性约简

属性约简是粗糙集合研究的核心内容之一,现已证明寻找最小约简是NP-hard问题。本文利用一种新的区分矩阵与免疫遗传算法结合方法,通过简化区分函数方法求得核属性,有效提高计算速度,能够实现相容/不相容决策表的属性约简,改进后的算法可以求取属性的一个约简。     

基于粗糙集理论的决策表属性约简算法

属性约简是粗糙集理论的一个重要内容,是进行知识获取中的核心问题之一.本文在粗糙集理论的基础上构造了区分图,在区分图上以属性的重要度作为启发信息,快速缩小搜索空间,求解最小属性约简.给出了一个最坏情况下时间复杂度为max（O（｜C｜^2）,O（｜C‖U｜^2））的快速属性约简算法.该算法统一考虑一致性决策表和不一致性决策表两种情况下的属性约简.     

基于区分向量的不完备决策系统属性约简算法

区分矩阵是属性约简的一种有效方法.针对不完备的决策系统,定义了区分矩阵的概念,给出了区分矩阵构造方法,并根据区分矩阵稀疏性的特点,定义了区分向量的概念,在此基础上,给出了一种基于区分向量的不完备决策系统属性约简算法.最后,采用恒星光谱数据,实验验证了该算法的有效性.     

分类算法中基于差别矩阵的属性约简方法

差别矩阵中会出现大量的重复元素占用大量内存,当数据太稠密时,构成的差别矩阵太大不容易操作且计算代价较高。本文提出了一种基于简化差别矩阵的属性约简算法(SDMAR),在属性约简之前,通过计算属性相似度,对属性进行了合并操作,得到简化决策表。根据简化决策表构造差别矩阵,计算差别矩阵中出现次数最多的属性并删除包含该属性的元素,当差别矩阵为空时终止操作,以达到对决策表属性约简的目的。通过算法及实例分析得到属性约简过程的时间复杂度有所减小。     

一种快速属性约简算法

基于差别矩阵的属性约简算法,先要求出差别矩阵,随着问题的规模增大,存放差别矩阵的空间和算法的执行时间过大和过长,让计算机难以承受．针对这一问题,提出了差别对象对集的定义,给出了基于差别对象对的属性约简定义,并证明了该定义等价于基于差别矩阵的属性约简定义．利用差别对象对,设计了一个新的属性约简算法．由于这一算法在求属性约简的过程中不用生成差别矩阵和大量的无用元素,因而大大减少了存储量和计算量,从而提高了算法的效率．计算实例说明了新算法的高效性．     

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

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

不完备信息系统的增量式约简算法

针对经典粗糙集模型在处理不完备、动态数据方面的不足,通过分析容差关系模型,引入先验概率在知识估计中的方法,给出了一种基于区分矩阵的增量式属性约简算法.以属性重要度为启发信息,对区分矩阵的构造过程进行改进,仅需简单的矩阵运算就可以得到约简结果.最后通过示例分析处理增量式数据的算法复杂度有效,算法正确可行.     

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

利用差别矩阵计算约简的算法,具有直观、易理解和完备性的特点,但也存在一定缺点,差别矩阵中存在大量冗余元素,这类元素的生成和存储将造成时空上的浪费.文章给出的算法在生成差别矩阵时,判断其元素是否冗余,若是冗余立即约去它,从而提高属性的约简效率.实例表明,该算法是正确和有效的。     

基于启发式二分策略的属性约简方法

分辨矩阵为属性约简与求核运算提供了一种规范精确的数学模型,通过分辨矩阵模型可方便地获取决策系统全体属性约简.本文基于分辨矩阵运用启发式信息与二分策略扩展结点,设计了一种构造约简树求取全体属性约简的有效算法,该约简树从根结点到叶结点全体路径构成的析取范式与系统分辨函数等价,其极小析取范式所有析取项即为决策系统全体属性约简.该方法适用于满足任意约简准则的分辨矩阵,能够显著地减少搜索空间和保证全体约简求解的完备性,理论分析与实验结果说明了算法的可行性与有效性.     

基于决策分类的分块差别矩阵及其求核算法

属性约简是粗糙集理论进行数据挖掘的基本途径, 相关算法主要基于核。 核的差别矩阵表示及相关求核计算具有重要意义, 但已有的差别矩阵及其求核算法还具有时空局限性。对此, 依据差别矩阵的稀疏性与大规模性, 提出基于决策分类的分块差别矩阵及其求核算法, 直接地将决策分类信息融入形式结构与问题求解。 首先, 基于决策分类来定义分块差别矩阵, 设计其计算算法; 其次, 基于分块差别矩阵, 确定核的内涵与算法; 最后, 进行实例分析与实验验证, 说明所建方法的有效性。基于决策分类的分块差别矩阵有效地实施了信息提取与维度降低, 相关的求核算法较好地减少了差别矩阵求核算法的时空复杂性。     

An improved reduction algorithm based on the degree of attribute discernibility

This paper deals with the problem of attribute discernibility reduction and proposes some new concepts to rough set theory （RST） based on the discernibility matrix of Skowron, such as secondary core, regeneration matrix and the degree of attribute discernibility （DAD）. This paper puts forward an attribute reduction algorithm based on maximum discernibility degree, which opens up an effective way of gaining minimum attribute reduction of decision table. The efficacy of this algorithm has been verified by practical application in a diagnostic system of loader, which substantially decreases information gathering requirement and lowers the overall cost with no loss of accuracy.     

改进的差别矩阵属性约简方法

针对目前属性约简方法计算量过大、复杂度高的问题,在已有差别矩阵定义和求核方法的基础上,根据二元决策表所特有的性质,提出一种新的差别矩阵的定义,将一个大的差别矩阵分化成两个小矩阵。与建立一个差别矩阵的方法相比,改进的差别矩阵方法减少了矩阵中元素的比较次数。数据分析表明,该方法在改进差别矩阵定义的同时简化了计算过程,提高了运算效率。     

二进制可辨矩阵空间复杂度的研究

二进制可辩矩阵是用二进制的方法对可辨矩阵的改进，针对二进制可辨矩阵的空间上存在不必要的开销，提出了一种可降低二进制可辨矩阵空间及时间开销的方法。把二进制可辨矩阵的建立和化简过程合成为一个过程，动态使用二进制可辨矩阵中的有用的信息，不保留其中的冗余信息，节省了空间；并且在行化简的比较运算过程中，自动生成一个偏序集，使每一行与最可能将其化简的行先比较，从而提高了行化简的命中率，节省了时间。最后给出了试验实例。