基于核与改进的条件区分能力的反向删除属性约简算法

粗糙集理论的布尔矩阵表示形式具有直观、易于理解的优点,它的引入为研究粗糙集的理论提供了一个新的思路。在对布尔矩阵性质研究的基础上,针对已有的基于布尔矩阵算法没有考虑到核属性在浓缩布尔矩阵时的重要性的不足,将属性重要性与改进的条件区分能力相结合,提出基于核与改进的条件区分能力的属性约简算法,借助反向删除确保约简集的完备性。实例表明改进后的算法在条件区分能力上更加准确,并且使约简结果更具有较强的完备性。     

决策表中粗糙集的布尔矩阵表示

建立了布尔矩阵与逻辑方程组的解和决策表中的属性集之间的关系;然后在此基础上给出了决策表中的粗糙集理论的布尔矩阵表示;最后证明了属性约简在布尔矩阵和代数两种不同表示下是等价的。这些结论有助于人们深刻理解粗糙集理论的本质,同时为寻找高效的属性约简算法奠定了基础。     

粗糙集概念与运算的布尔矩阵表示

建立了属性集与布尔矩阵以及逻辑方程组的解之间的关系;在此基础上给出了粗糙集理论中概念与运算的布尔矩阵表示;最后证明了属性约简在布尔矩阵和代数两种不同表示下是等价的。     

基于改进的Wap算法的Web序列模式的研究

基于不完备决策表的属性约简定义有多种,现研究基于知识粒度的属性约简。研究发现,差别矩阵是一种较好的设计属性约简算法的方法。为此,定义了一种粒度差别矩阵和基于该差别矩阵的属性约简,并证明了该差别矩阵的属性约简定义与基于知识粒度的属性约简定义等价。在此基础上,设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度得以降低。     

置换矩阵算法在粗糙集属性约简中的应用

介绍了粗糙集的布尔矩阵表示和置换矩阵的概念,导出了属性约简与置换矩阵之间的关系,讨论了逻辑关系方程组解的理论,提出了基于置换矩阵的粗糙集属性约简的新算法,通过实例分析证明了该方法的有效性,表明该算法在粗糙集属性约简中具有参考价值,对粗糙集理论的应用具有一定的实际意义。     

Discernibility Matrix Algorithm of Attribute Reduction Based on Knowledge Granulaion in Incomplete Decision Table

基于不完备决策表的属性约简定义有多种,现研究基于知识粒度的属性约简.研究发现,差别矩阵是一种较好的设计属性约简算法的方法.为此,定义了一种粒度差别矩阵和基于该差别矩阵的属性约简,并证明了该差别矩阵的属性约简定义与基于知识粒度的属性约简定义等价.在此基础上,设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度得以降低.     

采用布尔矩阵不完备信息系统的属性约简

对于不完备信息系统完备化问题,现在常采用的方法是数据补齐法和扩充法,在研究和分析了其优劣后,提出一种完全依据信息系统提供的信息来产生布尔可辨矩阵的方法。给出一个基于对布尔可辨矩阵进行化简的求属性约简（或最小属性约简）的高效算法。     

改进的布尔冲突矩阵的高效属性约简算法

近年来,诸多学者喜欢用差别矩阵的方法来设计属性约简的算法,但由于计算差别矩阵不仅费时且还浪费空间,导致这些属性约简算法都不够理想。为了降低属性约简算法的复杂度,在布尔冲突矩阵的基础上,定义了一个启发函数,该函数能求出决策表中条件属性导致的冲突个数,同时给出了计算该启发函数的快速算法。然后用该启发函数设计了一个有效的基于改进的布尔冲突矩阵的不完备决策表的高效属性约简算法,该算法能够有效降低时间复杂度。最后实验结果说明了新算法的有效性。     

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

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

改进的相容矩阵的属性约简算法

在粗糙集理论中,知识约简已经成为其核心内容之一。针对相关文献中基于相容矩阵的不完备信息系统属性约简算法,提出了一种新的相容矩阵定义,该矩阵能够减少关注的条件属性。同时,也证明利用该矩阵所求的属性约简与相关文献中的属性约简是等价的。给出了其属性约简算法,提高了属性约简的速度。     

不协调决策形式背景的矩阵型属性约简

形式概念分析的属性约简是知识表达和数据处理的一种有力的工具。对于不协调决策形式背景,已有多种属性约简的方法。从布尔矩阵运算的角度研究不协调决策形式背景的属性约简问题,提出属性约简的新的刻画。首先,借助矩阵的运算给出广义矩阵协调集的定义,并研究属性之间相似性的度量。接着,针对在属性约简过程中起不同作用的属性,将条件属性区分为核心属性和非核心属性,提出一个属性是否是核心属性的充要判断条件,以及得出属性约简的判别方法。最后,在此框架上设计出不协调决策形式背景属性约简的一种启发式算法,通过例题说明此算法的可行性和合理性。通过属性约简,该形式背景下的概念格计算更为简便。上述结果有助于进一步的应用及为研究形式概念分析的矩阵方法提供理论基础。     

基于布尔函数的Rough集差别矩阵属性约简方法

Rough集理论是对大型数据库进行知识发现的主要方法之一。根据属性集核和相对等价类的概念,对数据库属性集中的属性进行约简,提取相应的规则(知识),是用Rough集知识发现的精髓。该文基于Rough集差别矩阵,提出了属性集的布尔函数的构造方法,并应用吸收律、分配律和等幂律对属性集布尔函数化简。论文证明了属性集布尔函数的化简与属性集的差别矩阵约简等价,同时给出了求相对决策属性基本集的算法和IRIS提供的数据仿真实验结果。     

优势关系下基于浓缩布尔矩阵的属性约简方法

在优势关系粗糙集方法(DRSA)的框架下,针对不协调的目标信息系统求属性约简。基于优势矩阵的方法是最常用的一类约简方法,但矩阵中不是所有的元素都有效。浓缩优势矩阵只保留对求约简有用的最小属性集,因而可以明显降低约简过程中的计算量。进一步地,浓缩布尔矩阵通过布尔代数的形式有效地弥补了优势矩阵生成效率低的缺点。文中将等价关系上的浓缩布尔矩阵属性约简方法扩展到优势关系上,针对优势矩阵提出了浓缩布尔矩阵的概念,建立了相应的高效约简方法,使效率得到明显提高。最后采用9组UCI数据进行实验,结果验证了所提方法的有效性。     

基于可辨识布尔矩阵的协调决策表的属性约简

将条件属性分成核心属性、相对必要属性和绝对不必要属性,给出协调决策表的快速属性约简算法。提出协调决策表的可辨识布尔矩阵和布尔矩阵的初等行变换的概念,建立属性约简的数学模型。用布尔矩阵的初等行变换把可辨识布尔矩阵化为最简矩阵,给出通过可辨识布尔矩阵和最简矩阵判定3种条件属性的3个充分必要条件以及一种新的属性约简算法。     

Classification of Boolean functions by the invariants of their matrix representation

A variant of matrix representation for Boolean functions is designed such that these functions can be classified by matrix invariants. By way of example, the Deutsch problem is solved to illustrate the advantages of this classification.     

Solution of boolean differential equations on systolic arrays

Conclusion The proposed method for solving Boolean differential equations relies on matrix interpretation of the representation and solution of Boolean differential equations. The algorithm is accordingly interpreted in the language of parallel computations, producing an efficient solution of the problem on parallel structures. This approach is consistent with the requirements and development trends in VLSI technology. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 36–53, January–February, 1996.     

Exact and heuristic methods for solving Boolean games

Boolean games are a framework for reasoning about the rational behavior of agents whose goals are formalized using propositional formulas. Compared to normal form games, a well-studied and related game framework, Boolean games allow for an intuitive and more compact representation of the agents’ goals. So far, Boolean games have been mainly studied in the literature from the Knowledge Representation perspective, and less attention has been paid on the algorithmic issues underlying the computation of solution concepts. Although some suggestions for solving specific classes of Boolean games have been made in the literature, there is currently no work available on the practical performance. In this paper, we propose the first technique to solve general Boolean games that does not require an exponential translation to normal-form games. Our method is based on disjunctive answer set programming and computes solutions (equilibria) of arbitrary Boolean games. It can be applied to a wide variety of solution concepts, and can naturally deal with extensions of Boolean games such as constraints and costs. We present detailed experimental results in which we compare the proposed method against a number of existing methods for solving specific classes of Boolean games, as well as adaptations of methods that were initially designed for normal-form games. We found that the heuristic methods that do not require all payoff matrix entries performed well for smaller Boolean games, while our ASP based technique is faster when the problem instances have a higher number of agents or action variables.     

Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation

In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n×n Walsh matrix, for example, the BDD representation is of size O(log n). No other special-case representation in common use represents this matrix in space less than O(n²). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.