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

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

基于变精度和浓缩布尔矩阵的属性约简

属性约简是粗糙集理论研究的重要内容。传统的基于差别矩阵的属性约简方法只能处理一致决策表,改进的差别矩阵针对决策表中一致和不一致的对象做不同的处理,从而解决了这一问题。浓缩布尔矩阵进一步节省了矩阵的存储空间并提高了矩阵的生成效率,从而可以快速计算得到约简。在此基础上,结合变精度的思想把部分不一致对象合理地加入到一致对象的集合中,从而增加了一致数据的信息量,并通过使用浓缩布尔矩阵有效降低了约简的计算消耗。实验表明,所提方法在运行速度和分类精度方面均表现出了优势。     

基于布尔矩阵表示的粗集属性约简启发式算法

属性约简是粗糙集理论研究中的核心内容之一，现已证明寻找最小约简是NP-hard问题。该文对信息系统中属性的条件区分能力给出定义。在此基础上，提出了一种基于条件区分能力的属性约简的启发式算法。通过实例分析表明，在多数情况下该算法能够得到信息系统的最小约简。     

一种基于布尔矩阵的新的属性约简完备算法

属性约简是粗糙集理论研究的核心问题之一。现已有学者证明属性约简在布尔矩阵和代数两种不同表示下是等价的,且布尔矩阵表示更加直观。基于此理论本文提出了一种基于布尔矩阵的新的属性约简完备算法,并在此基础上加了一个反向删除过程,直到不能再删为止,保证了算法的完备性。最后通过实例分析证实了其有效性。     

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

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

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

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

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

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

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

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

基于浓缩树结构的启发式属性约简算法

属性约简是粗糙集理论的重要研究内容之一,对浓缩树结构中属性出现的频率进行加权,以属性频率的权重作为启发,以核为基础,从树中删除属性重要性最大的属性结点,直到树为空;为了找到信息系统的最优约简,在此基础上加了一个逆向消除的过程,直到不能再删为止。最后通过一个实例完整演示了该方法,证实其有效性。     

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

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

正碳离子氢原子移位重排反应研究

正碳离子是重要的有机化学反应中间产物,而氢原子移位则是正碳离子异构化的主要反应途径。本文利用量子化学方法对丙基伯正碳离子和仲正碳离子的结构和生成热进行了研究,优化了丙基伯正碳离子和仲正碳离子的结构,计算得到了这两种正碳离子的能量。结果表明,丙基伯正碳离子的生成热为214.4kcal/mol,丙基仲正碳离子的生成热为197.3kcal/mol,伯正碳离子的生成热比仲正碳离子的生成热高17.1kcal/mol,表明丙基伯正碳离子能够通过氢原子移位转变为丙基仲正碳离子。以丙基伯正碳离子和仲正碳离子的结构为起点进行过渡态搜索,得到了丙基伯正碳离子通过氢原子移位转化为丙基仲正碳离子,从而进行正碳离子重排反应的过渡态,并通过振动方式分析,对过渡态进行了确认。计算得到的丙基正碳离子通过氢原子移位进行重排反应的能垒为3.5kcal/mol,表明丙基伯正碳离子很容易转化为仲正碳离子。     

Constructing irreducible coverings of a Boolean matrix

A polynomial delay algorithm for searching for irreducible coverings of a Boolean matrix is constructed. A similar result is obtained for the problem of constructing maximal conjunctions of a monotone Boolean function specified by its conjunctive normal form. Elena V. Djukova born 1945. Graduated from Moscow State University in 1967. Candidate’s degree in Physics and Mathematics in 1979. Doctoral degree in Physics and Mathematics in 1997. Dorodnicyn Computing Center, Russian Academy of Sciences, leading researcher. Moscow State University, lecturer. Moscow Pedagogical University, lecturer. Scientific interests: discrete mathematics and mathematical methods of pattern recognition. Author of 76 papers. Andrey S. Inyakin born 1978. Graduated from Moscow State University in 2000. Candidate’s degree in Physics and Mathematics in 2000. Dorodnicyn Computing Center, Russian Academy of Sciences, junior researcher. Scientific interests: discrete mathematics and mathematical methods of pattern recognition. Author of sixteen papers.     

A sparse matrix algorithm on the Boolean vector machine

The Boolean Vector Machine (BVM) is a large network of extremely small processors with very small memories operating in SIMD mode using bit serial arithmetic. Individual processors communicate via a hardware implementation of the Cube Connected Cycles (CCC) network. A prototype BVM with 2048 processing elements, each with 200 binary bits of memory, is currently being built using VLSI technology.

The BVM's bit-serial arithmetic and the small memories of individual processors are apparently a drawback to its effectiveness when applied to large numerical problems. In this paper we analyze an implementation of a basic matrix-vector iteration algorithm for sparse matrices on the BVM. We show that a 2²⁰ Pe BVM can deliver over 1 billion (10⁹) useful floating-point operations per second for this problem. The algorithm is expressed in a new language (BVL) which has been defined for programming the BVM.     

Complexity of monotone networks for Boolean matrix product

Any computation of Boolean matrix product by an acyclic network using only the operations of binary conjunction and disjunction requires at least IJK conjunctions and IJ(K?1) disjunctions for the product of matrices of sizes I×K and K×J. Furthermore any two such networks having these minimum numbers of operations are equivalent using only the commutativity of both operations and the associativity of disjunction.     

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.     

序区间值决策系统中最优可信规则获取与约简

基于描述子的规则获取可导出序值决策系统中的所有可信规则,但对包含区间值序决策系统却不能有效支持。因此,首先根据每个属性值域的范围,提出了一个区间段值的概念,用以将序区间值决策系统转换为序区间段值决策系统;然后,在序区间段值决策系统中提出了基于区间段值的优势和弱势描述子概念,用以导出序区间值决策系统中的所有可信规则;最后,研究了两种新的描述子的约简以及相对约简问题,给出了相应的判定定理与区分函数。以上为从序区间值决策系统中获取有效的最优可信决策规则提供了一种新理论基础与操作手段。     

基于布尔矩阵的关联规则算法研究*

针对可快速在大型交易事务数据库中挖掘关联规则的问题,基于布尔矩阵提出一种新的挖掘算法。该算法通过仅需存储布尔位节约了内存,通过简单布尔运算提高了求解频繁项集的效率。实验证明该算法较之于Apriori 算法有更好的性能。     

基于布尔矩阵的区间数排序方法

讨论了10 个区间数排序的可能度公式, 分析了它们各自的特点. 从可能度的含义和保序性两个角度指出, 基于可能度矩阵的区间数排序方法有时会导出不合理的排序结果. 通过分析可能度矩阵与模糊判断矩阵的关系, 剖 析了导致这种不合理排序结果的原因. 最后, 利用可能度矩阵构造一个布尔矩阵, 基于布尔矩阵给出一个改进的区间 数排序算法, 并从理论上证明了所提出的排序方法的科学性.