覆盖概率粗糙集的模糊性

在经典覆盖近似空间中定义了论域上任意元素x的最小子覆盖,基于任意元素的最小子覆盖给出了覆盖粗糙集上、下近似新的描述,进而给出了已有覆盖概率粗糙集模型在最小子覆盖意义下的描述。同时,以覆盖概率粗糙集的粗糙隶属函数为基础,应用经典模糊集熵的概念讨论了覆盖概率粗糙集模糊性的度量。     

Solution of Fuzzy Equations with Max-Product Composition in Inverse Control and Decision Making Problems

A system of max-product type of equations, to which many inverse problems of fuzzy sets and relations, is solved. The minimal solution of this type of equations is determined from the solution of covering problems, which are NP-complete problems. A compatibility criterion for a system and redundancy criteria for equations and variables are formulated in terms of coverings. Possibilities for the reduction of the dimension of a covering problem and its solution methods are examined.     

结合类内集中度和最小集合覆盖的特征选择

特征选择是文本分类中的核心研究课题之一。简单分析了词频和文档频,在此基础上提出了类内集中度,把集合覆盖的思想引入粗糙集并提出了一个基于最小集合覆盖的属性约简算法,把该属性约简算法同类内集中度结合起来,提出了一个新的特征选择方法。该方法利用类内集中度进行特征初选以过滤掉一些词条来降低特征空间的稀疏性,利用所提约简算法消除冗余,从而获得较具代表性的特征子集。实验结果表明此种特征选择方法效果良好。     

基于最小/最大描述的多粒度覆盖粗糙直觉模糊集模型

覆盖粗糙集和直觉模糊集都是处理不确定性问题的基础理论,它们有着很强的互补性,且覆盖粗糙集和直觉模糊集的融合研究是一个新的热点。对多粒度覆盖粗糙集和直觉模糊集的融合进行深入研究。首先将最小描述、最大描述从单一粒度推广到多个粒度,提出了多粒度的最小描述和最大描述,讨论了多粒度的融合;其次,分别给出了基于最小描述和最大描述的模糊覆盖粗糙隶属度、非隶属度的概念,构建了两种新的模型即基于最小描述的多粒度覆盖粗糙直觉模糊集和基于最大描述的多粒度覆盖粗糙直觉模糊集,并讨论了它们的性质,同时举例说明;最后,分析和研究了两种模型的关系。该研究为多粒度覆盖粗糙集和直觉模糊集的融合提供了一种方法。     

图的最小顶点覆盖问题的DNA表面计算模型

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。     

用关键特征集对逻辑进行优化

提出了一个两级逻辑优化的新算法，与通过函数质蕴涵集求解覆盖的传统算法不同，文中将求解逻辑函数的质蕴涵项与推导覆盖问题相结合，直接得出覆盖问题的解。算法的主要问题可以简化为：对于立方描述的单元，求解最小覆盖，在这个过程中又提出了一种改进的覆盖吸收算法，基于关键特征集合的选拔吸收算法，此算法不用求所有的立方，通过标准的测试例子与原来的Espresso算法作比较，对于大电路，在计算时间上，新算法有明显的改进。     

Minimal covering problem and PLA minimization

Solving the minimal covering problem by an implicit enumeration method is discussed. The implicit enumeration method in this paper is a modification of the Quine-McCluskey method tailored to computer processing and also its extension, utilizing some new properties of the minimal covering problem for speedup. A heuristic algorithm is also presented to solve large-scale problems. Its application to the minimization of programmable logic arrays (i.e., PLAs) is shown as an example. Computational experiences are presented to confirm the improvements by the implicit enumeration method discussed.This work was supported in part by the National Science Foundation under Grants Nos. MCS77-09744 and MCS81-08505 and also by the Department of Computer Science.M.-H. Young was with the Department of Computer Science, University of Illinois, Urbana, Illinois.     

基于覆盖算法的条件信息熵表示及属性约简

利用覆盖算法对数据进行处理,得到论域U的一个划分,定义一种基于覆盖的条件信息熵,由新的条件信息熵定义新的属性重要性,并证明了对于一致决策表,它与代数定义下的重要性是等价的。以新的属性重要性为启发信息设计约简算法,并给出计算新的条件信息熵的算法。实验结果表明该约简算法能快速搜索到最优或次优约简。     

直接加权优化辨识的最小概率设计

研究非线性系统辨识的一种新方法-直接加权优化辨识,对于该方法中未知权重值求取,采用统计学习理论中的最小概率准则作为逼近的误差准则函数。最小概率策略选择为最小化估计误差边界应小于某指定门限值的概率,此估计误差边界来源于有限个数的数据点。将最小概率准则转化为一个最大化问题,对于此最大优化问题,通过代数运算来求解此最大化问题以得到未知权重值的显式表达式。权重估计值有类似核估计的渐近收敛特性,且为独立未知噪声方差值的显式形式。最后用仿真算例验证本文方法的有效性。     

抗压缩的照片图像与真实感计算机图形识别

数字图像取证是计算机取证、信息安全领域的一门新学科。为实现照片图像与真实感计算机图形的可靠识别,提出一种基于图像稀疏表示的数字图像取证方法,该方法在抵抗压缩方面具有较好性能,从而保证图像压缩不会改变照片图像与真实感计算机图形的真实性本质。Tetrolet变换为保护图像局部几何结构,在L1-范数最小约束下搜索4×4图像块的最优覆盖(Covering)形式,获得图像的稀疏表示。观察自适应值c的统计分布,得到一幅图像中117种Covering出现次数的归一化直方图,从而得到图像的HoC(histogram of covering)特征。实验结果表明,在饱和度(S)分量提取的HoC特征能够很好地刻画照片图像与真实感计算机图形在局部几何结构上的不同统计特性,算法在识别能力、泛化能力,尤其是抵抗压缩能力上表现出良好性能,能够应用于图像真实性检测及照片图像与计算机图形的自动分类。     

一种不完备信息系统的约简方法

提出了一种基于覆盖粗糙集理论,利用最大一致块技术进行不完备信息系统约简的方法。在证明利用最大一致块技术生成的相容类构成论域的最简覆盖基础上,利用覆盖粗糙集理论对已利用最大一致块技术进行属性约简的信息系统进行属性值约简,并提出一种新的约简算法。     

一种不完备信息系统的约简方法

提出了一种基于覆盖粗糙集理论，利用最大一致块技术进行不完备信息系统约简的方法。在证明利用最大一致块技术生成的相容类构成论域的最简覆盖基础上，利用覆盖粗糙集理论对已利用最大一致块技术进行属性约简的信息系统进行属性值约简，并提出一种新的约简算法。     

Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems

In this paper, a deadlock prevention policy for flexible manufacturing systems (FMS) is proposed, which can obtain a maximally permissive liveness-enforcing Petri net supervisor while the number of control places is compressed. By using a vector covering approach, the sets of legal markings and first-met bad markings (FBM) are reduced to two small ones, i.e., the minimal covering set of legal markings and the minimal covered set of FBM. A maximally permissive control purpose can be achieved by designing control places such that all markings in the minimal covered set of FBM are forbidden and no marking in the minimal covering set of legal markings is forbidden. An integer linear programming problem is designed to minimize the number of control places under an assumption that a control place is associated with a P-semiflow. The resulting net has the minimal number of control places on the premise that the assumption holds, and possesses all permissive states of a plant. The only problem of the proposed method is its computational complexity that makes it inapplicable to large-scale Petri net models. An FMS example from the literature is presented to illustrate the proposed method.     

部分四值逻辑中保二元正则可离关系非最小覆盖的剔除

为确定部分四值逻辑的最小覆盖,根据部分K值逻辑的完备性理论、正则可离关系以及准完 备集之间的相似关系理论,对部分四位逻辑的最小覆盖进行分析,证明了270个保二元正则可离关系函数集中的222个函数集必不属于部分四值逻辑中最小覆盖的成员.     

Deriving minimal solutions for fuzzy relation equations with max-product composition

This work considers fuzzy relation equations with max-product composition. The critical problem in solving such equations is to determine the minimal solutions when an equation is solvable. However, this problem is NP-hard and difficult to solve [A.V. Markovskii, On the relation between equations with max-product composition and the covering problem, Fuzzy Sets and Systems 153 (2005) 261-273]. This work first examines the attributes of a solvable equation and characteristics of minimal solutions, then reduces the equation to an irreducible form, and converts the problem into a covering problem, for which minimal solutions are correspondingly determined. Furthermore, for theoretical and practical applications, this work presents a novel method for obtaining minimal solutions. The proposed method easily derives a minimal solution, and obtains other minimal solutions from this predecessor using a back-tracking step. The proposed method is compared with an existing algorithm, and some applications are described in detail.     

Entropy Based Approach to Data Loss Reparation Through the Indeterminate Fine-Grained Parallel Computation

The new method of a gap recovery in symbol sequences is presented. A covering is combined from the suitable reasonably short strings of the parts of a sequence available for observation. Two criteria are introduced to choose the best covering. It must yield the maximum of entropy of a frequency dictionary developed over the sequence obtained due to the recovery, if an overlapping combined from the copies of strings from the available parts of the sequence exists. The second criterion identifies the best covering in case when one has to use any string to cover the gap; here the best covering must yield the minimum of specific entropy of the frequency dictionary developed over the available parts of the sequence against the one developed over the entire sequence obtained due to the recovery. Kirdin kinetic machine which is the ideal fine-grained structureless computer has been used to resolve the problem of the reconstruction of a gap in symbol sequence.     

P*4中保四元正则可离关系非最小覆盖的剔除*

为确定部分四值逻辑的最小覆盖,根据部分K值逻辑的完备性理论、正则可离关系以及准完备集之间的相似关系理论, 对部分四值逻辑的最小覆盖进行分析,证明了109个保四元正则可离关系函数集中的67个函数集必不属于部分四值逻辑中最小覆盖的成员。     

覆盖多粒度粗糙集的数值特征

通过极大描述和极小描述获取的覆盖多粒度粗糙集,可以更好地应用于实际.首先通过极小描述和极大描述的交并运算定义4个悲观覆盖多粒度粗糙集模型,并讨论其基本性;在此基础上进一步分析其证据结构,并得出覆盖多粒度粗糙集具有信任结构的充分条件,即上、下近似满足对偶性、可加性和可乘性.通过上述研究,进一步丰富了多粒度粗糙集的研究.     

基于凸四边形曲率的三角剖分优化准则

由3D散乱点集构造三角剖分在曲面造型中有着十分重要的作用，而剖分所采用的优化准则决定了最终的剖分结构。从曲率这一曲面内在特性入手，提出了一种空间凸四边形的曲率估计算法，据此还提出了一种新的基于该曲率的优化准则，即一种曲率最小优化准则，并通过一个例子详细地将这一新的优化准则与几种常用的优化准则做了比较，实验结果的分析表明，运用该优化准则得到的三角剖分具有较好的几何特性，在曲面重构和曲面设计等方面有很好的实用价值。     

Approaches to knowledge reduction of covering decision systems based on information theory

In this paper, we propose some new approaches for attribute reduction in covering decision systems from the viewpoint of information theory. Firstly, we introduce information entropy and conditional entropy of the covering and define attribute reduction by means of conditional entropy in consistent covering decision systems. Secondly, in inconsistent covering decision systems, the limitary conditional entropy of the covering is proposed and attribute reductions are defined. And finally, by the significance of the covering, some algorithms are designed to compute all the reducts of consistent and inconsistent covering decision systems. We prove that their computational complexity are polynomial. Numerical tests show that the proposed attribute reductions accomplish better classification performance than those of traditional rough sets. In addition, in traditional rough set theory, MIBARK-algorithm [G.Y. Wang, H. Hu, D. Yang, Decision table reduction based on conditional information entropy, Chinese J. Comput., 25 (2002) 1-8] cannot ensure the reduct is the minimal attribute subset which keeps the decision rule invariant in inconsistent decision systems. Here, we solve this problem in inconsistent covering decision systems.