基于知识粒度的不完备决策表求核方法

为降低不完备决策表求核算法的时间复杂度,本文构造了粒度二进制的差别矩阵.然后定义属性重要性及相应的核,由此设计了一个基于不完备决策表的粒度二进制差别矩阵的求核算法,并分析新算法的时间复杂度,其时间复杂度降为max{O(|C||U||Upos|),O(K|C||U|)},优于同类算法的时间复杂度,最后用实例说明了该算法的有效性.     

基于Skowron分明矩阵的有效属性约简算法

为降低基于Skowron分明矩阵属性约简算法的复杂度,提出了简化分明矩阵及其相应属性约简的定义,并证明了基于简化分明矩阵的属性约简与基于原分明矩阵的属性约简等价.在简化决策表的基础上,定义了一个函数,该函数能度量条件属性在简化分明矩阵中出现的频率,并给出了计算该函数的快速算法,其时间和空间复杂度均为O(|U/C|).用该函数设计了一个有效的基于原分明矩阵属性约简算法,算法的时间复杂度降为O(|C||U|)+O(|C|2|U/C|),空间复杂度降为O(|U|);并用实例证明了算法的有效性.     

基于修正差别矩阵的高效属性约简算法

为降低基于修正差别矩阵的属性约简算法的复杂度,给出了基于修正差别矩阵的简化差别矩阵,证明了基于该简化差别矩阵的属性约简定义与基于原修正差别矩阵的属性约简定义是等价的.在此基础上设计了一个基于简化差别矩阵的属性约简算法,其空间和时间复杂度分别被降为O(|C|(|U'pos||U/C|))和max{O(|C|2(|U'pos||U/C|)),O(|C||U|log|U|)}.实例说明:用新算法进行属性约简,不仅减少了计算量,而且减少了存储空间,因而是一种高效的属性约简算法.     

一种高效的启发式属性约简算法

属性约简是粗糙集的精髓,差别矩阵算法是属性约简中的常见方法之一。差别矩阵算法需大量空间存储差别元素,且有很高的时间复杂度。为降低时间、空间复杂度,给出不可鉴别信息量定义,计算属性重要性,并以此为启发信息,设计一种启发式约简算法,使原来的时间复杂度由O(|R|~2|U|~2)降为max(O(|R|~2|U/R|),O(|R||U|)),空间由O(|R||U|~2)降为O(U/R),并通过实例验证该算法的高效性和正确性。     

基于差别矩阵的属性集求核算法

通过对差别矩阵的研究,提出一种压缩差别矩阵的构造方法及相关的属性集求核算法,减少了差别矩阵中大量的空值存储,并且避免对象之间的盲目比较.算法的时间复杂度为max(O(|C||U_1||U_2|),O(|C'||U_1'|~2)),空间复杂度为max(O(|C||U_1'||U_2'),O(|U_1'|~2)),提高了已有差别矩阵算法的求核效率.实例分析与实验结果均验证了构建算法的有效性.     

粗糙集中基于信息量的决策表属性约简算法

高效的属性约简算法是粗糙集理论应用于知识发现的基础,要在令人可接受的时间内获得约简的通常做法是基于启发式的约简方法。本文提出了决策表中决策属性集相对条件属性集的条件信息量的概念,同时用知识的条件信息量定义了属性的重要性,在此基础上,提出了一种新的基于信息量的属性约简算法,该算法的时间复杂度为(O|C|3|U|2),通过实例分析,表明该算法是有效的。     

一种新的快速求核算法

为了解决核影响属性约简算法的速度和效率等问题，提出了一种基于正区域的求核算法．采用基数排序思想计算正区域，分别得到决策属性正区域的条件属性集和除决策属性正区域的一个条件属性之外的条件属性集，并且计算这2种属性集的基数之差，以判断该条件属性是否是核属性，依次判断所有条件属性，从而快速获得所需要的核．基于正区域求核算法的时间复杂度为O（｜C｜｜U｜）．实验结果表明，利用该算法求核，所耗时间将随对象数的增加呈线性增长，且当对象数最大时，求核所耗时间仅为对比算法的0．6％，同时证明了该算法对各种数据集均有很好的适应性．     

一种快速强化学习方法研究

在对资格迹理论研究的基础上,提出了一种延迟快速强化学习算法DFSARSA(λ)(延迟快速SARSA(λ)算法).算法的主要思想是通过对资格迹的重新定义和对即时差分TD(λ)偏差的跟踪,使强化学习中Q值在需要时进行更新,而SARSA(λ)每一步都对Q值进行更新,该方法使SARSA(λ)算法的更新计算复杂度从O(|S||A|)降到了O(|A|),提高了强化学习速度,仿真实验证明了该算法的有效性.     

一种基于粗集的决策表求核算法

决策表是粗集理论的处理对象,其核属性的计算往往是决策信息约简过程的出发点和关键.大多数决策表的求核方法是基于差别矩阵的,具有较高的时间复杂度和空间复杂度.基于区分表,提出一种效率更高的计算核属性的算法,并验证了算法的正确性.     

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

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

基于数据库系统的知识约简算法

该文基于粒度和粒度计算,设计了信息系统约简以及决策表约简算法,实例证明了算法的有效性。文中分析了算法的时间复杂度,并同几种主要知识约简算法做了对比,结果表明该文算法时间复杂度最小。     

A Clas of Distributed Recognition Algorithms for Acyclic Database Schemes

各种非环的数据库模式有许多好的性质，特别是在分布式环境中，研究关系数据库的非环性程度是一个重要的课题．对Ａｌｐｈａ，Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ这几种非环数据库模式，我们给出一组分布式算法．该算法的最坏消息复杂度是Ｏ（｜Ｎ｜２），而最坏时间复杂度是Ｏ（｜Ｎ｜２），其中｜Ｎ｜是给定的网络中结点的个数．     

用属性单值表示的决策表简化算法及属性核计算

为了降低决策表的存储空间,提高计算属性核的效率,提出了一种用属性单值表示的决策表简化算法.给出了条件属性的尺度、权值、属性单值和简化决策表的定义,以及尺度运算、权值运算、每个对象的条件属性值集合转换为一个属性单值的简化运算的严密公式,并通过决策表的可逆定理证明了简化决策表与原始决策表具有相同的信息表达能力.利用该算法简化决策表,条件属性的表达由多维降低为一维,从而有效地降低了决策表的存储空间.实验结果表明,简化决策表属性核的计算效率明显比现有决策表属性核的计算效率高,尤其是对于大型决策表,这种优势更加明显.     

Feature Selection Based on Difference and Similitude in Data Mining

Feature selection is the pretreatment of data mining. Heuristic search algorithms are often used for this subject. Many heuristic search algorithms are based on discernibility matrices, which only consider the difference in information system. Because the similar characteristics are not revealed in discernibility matrix, the result may not be the simplest rules. Although differencesimilitude（DS） methods take both of the difference and the similitude into account, the existing search strategy will cause some important features to be ignored. An improved DS based algorithm is proposed to solve this problem in this paper. An attribute rank function, which considers both of the difference and similitude in feature selection, is defined in the improved algorithm. Experiments show that it is an effective algorithm, especially for large-scale databases. The time complexity of the algorithm is O（｜ C ｜^2｜U ｜^2）.     

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

基于决策支持度的不完备信息系统约简算法

提出了一种基于决策属性支持度的属性相对约简算法。通过引入决策属性支持度对不完备决策表中属性的重要性进行了定义,并以此作为启发信息进行属性的选择,该算法的时间复杂度是多项式的。寻找决策表中最小相对约简问题是典型的NP-hard问题,采用该算法可降低问题复杂度。通过实例说明,该算法能得到不完备决策表的最小相对约简。     

基于压缩决策表的乐观多粒度粗糙集粒度约简算法

粒度约简是多粒度粗糙集研究的一个关键问题。为了从乐观多粒度粗糙集的角度研究粒度约简问题,消除冗余数据,提高粒度约简的效率,提出基于压缩决策表的乐观多粒度粗糙集粒度约简算法。针对乐观多粒度粗糙集模型,引入下近似分布粒度约简的概念;利用线性时间排序算法进行等价类划分,为决策表的压缩和下近似集的计算打下基础;以冗余的决策表为研究对象,以核粒度为初始粒度约简集,以粒度重要性为启发式信息,运用粒度约简算法进行粒度约简,并通过实例分析和实验验证了该算法的有效性。结果表明,算法降低了计算下近似集的时间复杂度,具有较高的粒度约简效率。