粗糙集中正区域和近似精度的递归计算及应用

本文分析粗糙集中不同正区域之间的定量关系,给出正区域和近似精度计算的一个简洁的递归公式.在一类扩展型属性约简算法中(如Hu算法,Jelonek算法等),应用该递归公式来完成大量的正区域或近似精度以及与之相关的属性重要性的计算,可以较大幅度地减少计算量,提高属性约简算法的速度.     

基于粗糙集的决策表属性约简方法的研究

求核和属性约简是粗糙集理论研究的一个核心问题。文中主要针对现有的一些决策表属性约简算法存在的不足,尤其是基于信息熵的属性约简算法在较大数据集上效率不高的问题提出改进。主要通过结合粗糙集的相关理论来改进原有的属性约简算法在求核中的约束条件,进而在原有算法的基础上提出了一种改进算法。在求约简属性集时,利用新提出的约简算法,使计算复杂度降低,同时保持了高效的决策准确率。实验结果表明改进后的决策表属性约简方法能够更加快速有效地找到约简集。     

决策表的高效属性约简算法

粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。对现有决策表的属性约简算法进行了比较研究,在此基础上设计了两个合理度量属性重要性的公式,并给出了该公式的递归计算方法,利用新公式作为启发式信息设计了一种新的基于决策表的高效属性约简算法。实例与实验表明,该约简算法在效率上较现有算法有显著的提高。     

基于属性排斥矩阵的约简方法

针对启发式算法难以获得最小约简的问题,研究最小约简约束下属性之间的排斥特性,提出了针对部分最小约简必要条件的属性排斥矩阵.在此基础上,分别结合典型加法类和减法类启发式约简算法提出两种改进的基于属性排斥矩阵的启发式属性约简算法,采用UCI(加州大学欧义分校)机器学习数据集所进行的测试结果表明,属性排斥矩阵能够全面提高启发式属性约简算法的性能,有利于获得最小约简.     

基于粗糙集的决策规则约简

粗糙集理论是一个新的数据挖掘方法，正越来越被人们所重视。其主要思想是保持分类能力不变的情况下，利用等价类，通过属性约简和决策规则约简，达到发掘知识并简化知识的目的。但是属性约简是一个NP问题，对属性的约简和决策规则的约简只能通过启发式算法实现。该文针对属性约简和决策规则约简，各提出了一个启发式算法。     

增量式的高效属性约简算法

属性约简是Rough集理论的核心内容之一，计算所有的属性约简已经被证明是NP完全问题．在深入研究Rough集理论的基础上，仔细分析了对象集的增加与属性约简的关系，给出了增量式属性约简的判定定理，从而提供了计算所有属性约简的增量式算法，分析了算法的时间复杂度．理论分析和实验结果表明，该约简算法在效率上较现有的算法有显著提高．     

一种属性与值约简简化算法

Rough Set理论是处理不确定性知识、不完整数据的重要工具，在Rough Set中属性最小约简与规则提取NP—hard的．本文针对现有属性约简与值约简算法的问题，分析了区分矩阵的特性，在此基础上，提出了属性与值约简的简化算法，并用实例作了验证．     

一种基于粗糙集的决策系统属性约简算法

从大量数据发现知识时，属性约简是一个关键问题，本文提出了一种新的算法用于粗集中的属性约简，该算法基于Hu的差别矩阵，在对差别矩阵进行化简的基础上，先得到核，然后在逐步减小的差别矩阵中挑选出最频繁的属性加入直到成为一个约简。文中还对求核的正确性，算法的正确性进行了证明，同时对算法复杂度进行了分析，最后给出了一个例子来说明算法的有效性。     

一种基于粗糙集属性频度约简算法的改进

为了获得有效的属性最小相对约简,在基于属性频度的启发式约简算法的基础上,提出了一种同时满足属性重要性和频度改进的启发式约简算法。该算法的基本思想是：以属性的核为基础,以频度作为选择属性的启发信息,即把属性频度最大的属性添加到核属性中,这样就把分类能力较强的属性添加到约简集合中,从而能够获得较优的约简。     

一种基于粗糙集属性频度约简算法的改进

为了获得有效的属性最小相对约简,在基于属性频度的启发式约简算法的基础上,提出了一种同时满足属性重要性和频度改进的启发式约简算法.该算法的基本思想是:以属性的核为基础,以频度作为选择属性的启发信息,即把属性频度最大的属性添加到核属性中,这样就把分类能力较强的属性添加到约简集合中,从而能够获得较优的约简.     

Kneser–Ney Smoothing With a Correcting Transformation for Small Data Sets

We present a technique which improves the Kneser-Ney smoothing algorithm on small data sets for bigrams, and we develop a numerical algorithm which computes the parameters for the heuristic formula with a correction. We give motivation for the formula with correction on a simple example. Using the same example, we show the possible difficulties one may run into with the numerical algorithm. Applying the algorithm to test data we show how the new formula improves the results on cross-entropy.     

一种信息系统的快速属性约简算法

在分析目前已有的基于Rough Set的属性约简算法后,认为计算属性的重要性的算法复杂度可以进一步降低,同时给出了一个新的较为合理的度量属性重要性的计算公式,并分析了该计算公式的性质,然后给出了一个时间复杂度为max｛O｜A‖U｜log｜U｜,O(｜A｜2｜U｜)｝的快速属性约简算法,最后用一个实例说明了算法的有效性。     

LTL公式到自动机的转换

在LTL公式和自动机理论的基础上,给出了一种从LTL公式到自动机的转换算法.该算法先简化LTL公式,然后再对简化的LTL公式转换,形成选择Buchi自动机.此算法与其他算法相比,具有可扩展性的优点,可以在此基础上形成属性描述语言PSL向自动机的转换.     

A wavelet based multiresolution algorithm for rotation invariant feature extraction

The present work aims at proposing a new wavelet representation formula for rotation invariant feature extraction. The algorithm is a multilevel representation formula involving no wavelet decomposition in standard sense. Using the radial symmetry property, that comes inherently in the new representation formula, we generate the feature vectors that are shown to be rotation invariant. We show that, using a hybrid data mining technique, the algorithm can be used for rotation invariant content based image retrieval (CBIR). The proposed rotation invariant retrieval algorithm, suitable for both texture and nontexture images, avoids missing any relevant images but may retrieve some other images which are not very relevant. We show that the higher precision can however be achieved by pruning out irrelevant images.     

命题公式真值表的生成算法

真值表是命题逻辑理论中的一个重要概念,利用它可以求命题公式的主范式、判定命题公式的类型以及进行命题逻辑的推理等。本文给出了任意命题公式真值表的生成算法,为利用计算机解决命题逻辑中的其它问题奠定了基础.     

基于相关系数的决策树优化算法

通过分析ID3算法的基本原理及其多值偏向问题,提出了一种基于相关系数的决策树优化算法。首先通过引进相关系数对ID3算法进行改进,从而克服其多值偏向问题,然后运用数学中泰勒公式和麦克劳林公式的性质,对信息增益公式进行近似简化。通过具体数据的实例验证,说明优化后的ID3算法能够解决多值偏向问题。标准数据集UCI上的实验结果表明,在构建决策树的过程中,既提高了平均分类准确率,又降低了构建决策树的复杂度,从而还缩短了决策树的生成时间,当数据集中的样本数较大时,优化后的ID3算法的效率得到了明显的提高。     

基于目标空间分解和连续变异的多目标粒子群算法

针对当前多目标粒子群优化算法收敛性和多样性不佳等问题,提出了一种基于目标空间分解和连续变异的多目标粒子群优化算法。利用目标空间分解方法将粒子群分配到预先设定好的子区域中,在该过程中,通过一种新适应值公式来对每个子区域中的粒子进行择优筛选,该适应值公式融入了支配强度因素;在全局搜索过程中,使用差分变异、高斯变异和柯西变异对全局引导粒子的位置进行连续变异操作。将该算法与当前主流的一些多目标优化算法进行对比实验,结果表明,本文提出的算法在提高粒子收敛性的同时,多样性也得到了提升。     

Fractional alpha stable network traffic model and its application in QoS routing

It is not a simple and trivial work to set up an appropriate network traffic model. A fractional Alpha model is proposed in this paper and two proofs based on flow and session level, respectively, are given. Based on this model, the lower bound for the residual of the queueing distribution is deduced. Comparing the residual distribution function (RDF) based on our model with it based on other models, we find our formula matches the real RDF better. Based on this formula, we can predict the need for forwarding performance. Then a novel QoS routing algorithm based on this prediction is proposed. Last we demonstrate a simple example to denote how our algorithm can effectively improve the utility of bandwidth and amount of traffic and guarantee QoS.     

一个在Horn子句中求解极大缩减的算法

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.     

自然数编码遗传算法的最优群体规模

选择适当的群体规模是使用遗传算法面临的首要问题。对于给定字符串长ｌ，当采用自然数编码时，从理论上证明了遗传算法的最优群体规模的存在性，给出了相应的计算方法，本文工作对于遗传算法的实际应用具有指导意义。