基于集合覆盖的不完备信息系统属性约简方法

深入分析了不完备信息系统的特点以及相似关系的定义,通过构造不完备信息系统的相关矩阵,把不完备信息系统的最小属性约简问题与最小集合覆盖问题联系起来,将不完备信息系统的最小属性约简问题转化为最小集合覆盖问题,给出了基于集合覆盖的不完备信息系统最小属性约简算法。实例分析证明该算法可行,高效。     

基于最小集合覆盖的属性约简算法

在粗糙集理论的各种应用中,属性约简算法具有重要的意义,因而对属性约简算法的研究一直是粗糙集理论研究中的重点问题之一。在对属性约简算法充分研究的基础上提出一种基于最小覆盖集的粗糙集属性约简算法,即通过构造知识系统的一种改进的相关矩阵将属性约简简化为最小覆盖问题。将该算法与文献[7]中的算法进行实验比较并对结果进行分析,实验结果表明,当随着数据量增大时该算法具有更小的时间复杂度。     

图支配集问题的粗糙集属性约简方法

探讨粗糙集的属性约简和图的支配集问题之间的联系。通过构造信息系统,将粗糙集的属性约简问题与图的支配集问题相联系,从而把图的支配集问题转化为粗糙集的属性约简问题。首先证明图的极小支配集恰是其构造的信息系统的属性约简,然后提出一种基于信息熵的最小支配集算法,最后通过实例验证该算法的可行性和有效性。     

基于分治的属性约简复杂性分析

属性约简是粗糙集理论研究的主要内容之一,该文采用了分治策略,提出了一个新的属性约简方法,将计算整个全域上的属性约简问题转化为计算相应划分的子区域上属性约简问题。将原有计算POSX0(Y)的算法复杂度O(｜A｜｜U｜2)犤4犦降为O(｜A｜(｜Y1｜2+｜Y2｜2+……+｜Yn｜2)),对于一般比较大的｜U｜来说,明显地提高了属性约简可计算性和计算效率。     

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

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

属性约简中核的计算方法

属性约简是粗糙集理论研究的主要内容之一,该文首次采用了分治策略,提出了一个新的属性约简方法,将在计算整个全域上的属性约简问题转化为计算在相应划分的子区域上属性约简问题。将原有计算核的算法复杂度为O(｜A｜｜U｜2)犤1犦,降为O(｜A｜(｜Y1｜2+｜Y2｜2+……+｜Yn｜2)),对于一般比较大的｜U｜而言,提高效率非常明显,提高了属性约简的可计算性。     

基于疫苗提取及免疫优化的粗糙集属性约简

针对约简属性组合的爆炸问题,将RS属性核参数作为先验信息的免疫疫苗引入抗体编码,概率性对种群接种疫苗.将属性集合的分类近似标准作为抗体适应度,通过在免疫克隆选择过程中引入聚类竞争机制,提高抗体群分布的多样性及亲和力成熟,从而获得多个属性约简及最小约简的平衡.实验结果表明,这种粗糙集属性约简方法对于多维条件属性集是快速且有效的.     

粗糙集属性约简算法研究

粗糙集理论是一个新的处理不确定性问题的数学工具，属性约简是粗糙集理论的核心问题之一。但求解最优约简已被证明是一个NP—hard问题。基于属性重要度的启发式算法在属性约简中应用的较多．文中分别介绍了基于区分矩阵、基于相关矩阵和基于信息量的属性约简算法。对其思想进行了剖析和总结。     

基于粗糙集和多通道词向量的中文文本情感特征分析

粗糙集是一种能够有效处理不精确、不完备和不确定信息的数学工具,粗糙集的属性约简可以在保持文本情感分类能力不变的情况下对文本情感词特征进行约简。针对情感词特征空间维数过高、情感词特征表示缺少语义信息的问题,该文提出了RS-WvGv中文文本情感词特征表示方法。利用粗糙集决策表对整个语料库进行情感词特征建模,采用Johnson粗糙集属性约简算法对决策表进行化简,保留最小的文本情感词特征属性集,之后再对该集合中的所有情感特征词进行词嵌入表示,最后用逻辑回归分类器验证RS-WvGv方法的有效性。另外,该文还定义了情感词特征属性集覆盖力,用于表示文本情感词特征属性集合对语料库的覆盖能力。最后,在实验对比的过程中,用统计检验进一步验证了该方法的有效性。     

基于邻域粗糙集下知识划分的信息表降维

Pawlak粗糙集的知识约简包括对决策表的知识约简和对信息表的知识约简。作为Pawlak粗糙集的扩展,邻域粗糙集在针对决策表的属性约简方面应用广泛,而针对信息表的属性约简方面应用鲜少。为了设计一种适用于信息表的属性约简算法,根据Pawlak粗糙集的信息表知识约简标准,首先提出一种邻域粗糙集的信息表知识约简标准,然后根据这种标准,结合贪心思想,进一步提出了一种适用于聚类任务的信息表属性约简算法。与主成分分析(principal component analysis,PCA)算法相比,实验结果表明用该算法对数据集降维后,得到的属性约简集合的属性个数较多,K-means算法根据属性集合进行聚类的精度较高。实验结果证明该算法能有效地应用于信息表的属性约简方面。     

对混沌自适应控制的控制强度的讨论之二

文中对文献[1]提出的混沌自适应控制方法中给出的控制强度取值范围的计算方法作出了重要修改,指出了上文忽略的与控制矩阵的复数本征值λ±对应的控制强度,对离散系统只要满足｜λ±｜＜1亦可控制混沌,且更有效。其次指出对连续性系统仅考虑文献[1]给出的条件是不够的,控制强度还要满足λ±值的实部小于零,即微分方程的李雅普诺夫渐近稳定条件才能有效控制混沌。     

一种基于绝对信息量的知识约简算法

粗糙集理论是一种新的处理模糊和不确定知识的数学工具。知识约简是粗糙集理论研究中的重要内容之一,现已证明寻找信息系统的最小约简是NP-hard问题。该文提出一个基于绝对信息量的知识约简的启发式算法,该算法的时间复杂性为O(｜R｜3｜U｜2)。通过例子分析,表明该算法是有效的。     

A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets

Traditional rough set theory is mainly used to extract rules from and reduce attributes in databases in which attributes are characterized by partitions, while the covering rough set theory, a generalization of traditional rough set theory, does the same yet characterizes attributes by covers. In this paper, we propose a way to reduce the attributes of covering decision systems, which are databases characterized by covers. First, we define consistent and inconsistent covering decision systems and their attribute reductions. Then, we state the sufficient and the necessary conditions for reduction. Finally, we use a discernibility matrix to design algorithms that compute all the reducts of consistent and inconsistent covering decision systems. Numerical tests on four public data sets show that the proposed attribute reductions of covering decision systems accomplish better classification performance than those of traditional rough sets.     

Bound on the cardinality of a covering of an arbitrary randomness test by frequency tests

We improve a well-known asymptotic bound on the number of monotonic selection rules for covering of an arbitrary randomness test by frequency tests. More precisely, we prove that, for any set S (arbitrary test) of binary sequences of sufficiently large length L, where ∨S∨ ≤ 2 ^L(1?δ), for sufficiently small δ there exists a polynomial (in 1/δ) set of monotonic selection rules (frequency tests) which guarantee that, for each sequence t ∈ S, a subsequence can be selected such that the product of its length by the squared deviation of the fraction of zeros in it from 1/2 is of the order of at least 0.5 ln 2 L[δ/ln(1/δ)](1 ? 2 ln ln(1/δ)/ln(1/δ)).     

Reoptimization of set covering problems

If an element is inserted into or removed from a set, then the set covering problem can be reoptimized with some ratio ( 2 - \frac1lnm + 1 ) \left( {2 - \frac{1}{{\ln m + 1}}} \right) , where m is the number of elements of the set. A similar result holds if an arbitrary number 1 < p < m of elements of the set is inserted or removed.     

Reduction Algorithms Based on Discernibility Matrix: The Ordered Attributes Method

1 IntroductionIn Rough Set Theory[1], Pawall has defined two sorts of infOrInion systems withoat and withdecision attributes, denoted as (U C} and (U C U D) respectthely Rere U is the forrse Of obects,Me C and D aJre the condition attribote set tal the decision attriliute set respectively Their reductsare called reduct and rel8Jtive reduct reSPecttwBy Pawha, a reduct must satisfy a indePendent conditbo, tha is, a reduct 0 / R G C, R is'independent if Vr C R, mD(R) / mD(R-- {r}) f…     

基于容错粗集理论的知识约简

粗集理论(RoughSetsTheory,RST)在处理不完全、不精确、不确定性智能信息问题等许多领域已取得成功的应用。然而RST理论还存在某些局限性,比如对等价关系的定义使得知识约简相对复杂化。该文提出利用容错粗集犤1犦RST的概念,建立属性值之间的容错关系,用容错关系对对象进行分类。该方法首先采用遗传算法求出属性阈值的最优组合,然后分别建立属性和对象的特殊矩阵,最后求出属性的相对约简和对象的相对商集。采用容错粗集进行知识约简减少了量化的过程,从而提高知识约简的有效性。该文最后提供了一个实例表明该方法是可行的。     

属性序下基于优势关系灰色信息系统约简

粗糙集和灰色理论在数据挖掘领域各有优点,它们最终目标都是为了发现知识。将粗糙集和灰色系统结合,研究了区间灰色信息系统在优势关系下的约简方法。在现实世界中,属性之间可能存在着一种属性序的关系,将这种属性序关系引入到基于优势关系的灰色信息系统中,给出了两种属性约简的算法：一种基于分辨矩阵的算法,另一种不基于分辨矩阵的算法。较好地适应了不完备信息系统和大数据集信息系统约简。最后通过实例对比,得出两种算法的约简结果是一致的,并分析了各自的适用范围。     

以优势关系为基础的粗糙集在地震数据挖掘中的应用

在地震数据挖掘应用中，可用粗糙集方法进行对震例数据的属性约减。但是，经典的粗糙集理论建立在由等价关系对对象集划分的基础上，而震例数据是有序的而不是分类的对象。现对经典粗糙集理论进行扩展，提出一种用优势关系代替等价关系的粗糙集方法，并在此基础上提出一种基于差别矩阵的属性约简算法。实验结果表明，用这种方法能得出一些采用传统粗糙集理论所无法得到的结果。