属性约简中核的计算方法

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

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

在分析目前已有的基于Rough Set的属性约简算法后,认为计算属性的重要性的算法复杂度可以进一步降低,同时给出了一个新的较为合理的度量属性重要性的计算公式,并分析了该计算公式的性质,然后给出了一个时间复杂度为max｛O｜A‖U｜log｜U｜,O(｜A｜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(C｜｜2｜U｜log｜U｜).为降低算法的时间复杂度,本文首先给出了基于信息熵的简化差别矩阵及相应核的定义,并证明了该核与基于信息熵的属性约简的核是等价的.然后以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度为O(｜C｜｜U｜).在此基础上,设计了一个新求核算法,其时间复杂度被降为max{O(｜C｜｜U/C｜2),O(｜C｜｜U｜)}.最后用一个实例说明了新求核算法的高效性.     

基于相对熵的一种属性约简算法

知识约简是粗糙集理论研究的主要内容之一。在信息系统中引入了知识的相对熵的概念,证明了在知识相对约简过程中相对熵的变化趋势是递减的;利用相对熵的概念,定义了属性的相对重要性,提出了一种基于相对熵的新的属性约简启发式算法,该算法的时间复杂度为O(｜C｜3｜U｜2),通过例子分析,表明该算法是有效的。     

不一致信息系统的粗糙集快速约简算法

针对以依赖性作为属性重要性度量的约简算法效率较低、不能有效处理不一致信息系统的问题,提出一种时间复杂度为O（｜A｜2｜U｜）、基于错误分类率（ER）的快速约简算法。根据等价类计算的包含关系和正区域与属性个数的单调关系,采用ER作为属性重要性的度量。在UCI数据集合上测试该算法,结果证明了其有效性。     

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

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

一种基于粗糙熵的知识约简算法

描述了知识的粗糙性,提出了知识的粗糙熵概念,建立了信息系统中知识与粗糙熵之间的关系,并通过知识的粗糙熵对属性的重要性进行了定义。在此基础上,提出了基于粗糙熵的知识约简算法,该算法的时间复杂性为O(｜R｜3｜U｜2)。通过例子分析,表明该算法是有效的。     

基于简化的二进制差别矩阵的快速属性约简算法

目前,基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想;所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义,证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中,要先求出IND（C）,故设计了一个较好的求IND（C）的算法,其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法,其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。     

一个基于决策表的快速属性约简算法

在目前已出现的基于Rough Set的属性约简算法中，认为以近似质量为启发信息并非十分理想，以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式，并给出了该公式的递归计算方法，计算该公式的算法的复杂度被降低到O（｜C-P｜｜U—UP｜），然后给出了一个时间复杂度为max（O｜C｜｜U｜log｜U｜，O（｜C｜^2｜U｜））的快速属性约简算法，最后用一个实例说明了算法的有效性．     

一种关系积和遗传算法相结合的属性约简算法

属性约简是粗糙集(rough set,RS)理论进行规则提取中的重要步骤之一.决策表的最小属性约简是NP-hard问题.遗传算法(genetic algorithm,GA)是求解此类问题的有效方法之一,但在利用遗传算法求解属性约简过程中,需要计算各个个体的适应度,每计算一个个体的适应度,需要根据该个体代表的属性组,组织决策表,对组织后的决策表进行扫描,这样,算法就需要多次对决策表进行操作,影响到算法的执行效率.我们基于集合理论,提出了关系积概念,把决策表的属性约简过程转化为关系积的运算,利用关系积计算遗传算法各个体的适应度,不需要扫描决策表,避免了对决策表的操作,提高了遗传算法求解属性约简的效率,通过实例对这一算法进行了详细的描述.     

地震预报专家系统中学习样本的构建

如何选择和处理学习样本是地震预报专家系统中非常重要的问题。该文在分析以前方法的特点和不足的基础上,提出了异常驱动样本构造法,并用基于RBF神经网络的属性约简方法来处理学习样本。使用异常驱动样本构造法可以方便、科学地根据异常属性出现的频率选择学习样本的属性和根据每条样本的空缺属性率选择学习样本。基于RBF神经网络的属性约简方法利用RBF(RadialBasisFunction)神经网络的特点来量化各维属性对结果的影响程度,从而约简对结果影响程度小的属性。通过实验,表明了用该文方法进行地震预报样本的选择和处理,能明显地提高地震预报的精度。     

基于互信息变化率的属性约简算法

属性约简是粗糙集理论中的基本内容之一,但获得决策系统的最小相对约简是一个NP问题。文章从信息论的角度,结合微积分中的变化率思想,定义了一种基于互信息变化率的属性重要性度量方法,然后在此基础上提出了两种相对属性约简的启发式算法。最后,通过实验结果证明该方法能有效地对决策系统进行约简。     

基于分辨能力指数的属性约简算法

在粗糙集理论研究的诸多方面中,属性约简是其核心问题之一.为寻求高效、快捷的属性约简算法,从粗糙集理论出发,在可分辨关系和对象差异矩阵概念的基础上,构造出"基于分辨能力指数的启发式约简算法".算法采用自底向上的方法,以属性集的核作为求解约简的基础,利用分辨能力指数信息作为属性选取的依据.算法简化了计算,无需生成中间结果,没有增加系统的时空开销.最后,UCI数据集的测试结果表明,启发式约简算法有效、可行.     

不完备决策表中基于对象矩阵属性约简算法

基于差别矩阵的属性约简是粗糙集属性约简中最常用的方法。对通常给出的以存储条件属性为基础差别矩阵进行比较后,给出一种对象矩阵的定义。对象矩阵从相容类内对象的决策值与条件属性的关系出发,存储的是对象集。给出对象矩阵的属性约简定义,证明了属性约简与基于正区域的属性约简的等价性。给出一个启发式的属性约简算法,其时间复杂度为max(O(|C|2|Upos||U|),O(|C||U|2)),空间复杂度为O(|C||U|2);通过实例说明方法的可行性。     

不完备邻域粗糙集的不确定性度量和属性约简

针对现有的属性约简算法不适合处理数值型属性和符号型属性共同存在的不完备数据,提出了一种拓展不完备邻域粗糙集模型。首先,通过考虑属性值的概率分布来定义缺失属性值之间的距离,可以度量具有混合属性的不完备数据;其次,定义了邻域混合熵来评价属性约简的质量,分析证明了相关的性质定理,并构造了一种基于邻域混合熵的不完备邻域粗糙集属性约简算法;最后从UCI数据集中选取了7组数据进行实验,并分别与基于依赖度的属性约简（ARD）、基于邻域条件熵的属性约简（ARCE）、基于邻域组合测度的属性约简（ARNCM）算法进行了比较。理论分析和实验结果表明,所提算法约简属性比ARD、ARCE、ARNCM分别减少了约1,7,0个,所提算法的分类精度比ARD、ARCE、ARNCM分别提高了约2.5,2.1,0.8个百分点。所提算法不仅能够获得较少的约简属性,同时具有较高的分类精度。     

多粒度粗糙集粒度约简的高效算法

针对已有多粒度粗糙集粒度约简算法效率较低的问题,提出一种多粒度粗糙集粒度约简的高效算法（EAGRMRS）。首先,以决策信息系统为对象,定义决策类下近似布尔矩阵,该矩阵能够将粒度约简过程中过多且有重复的集合运算转换为布尔运算,基于该矩阵给出计算决策类下近似算法和计算粒度重要度算法。然后,针对计算粒度重要度时存在冗余计算的问题,提出粒度动态增加时快速计算粒度重要度的算法,并在此基础上,提出EAGRMRS,该算法的时间复杂度为O（|A|·|U|²+|A|²·|U|）,其中|A|表示粒度集合大小,|U|表示决策信息系统中实例数。在UCI数据集上的实验结果验证了所提算法的有效性和高效性,并且随着数据集的增大,EAGRMRS相较于多粒度粗糙集粒度约简的启发式算法（HAGSS）效率优势更加明显。     

Sparse Normalized Local Alignment

Given two strings, X and Y, both of length O(n) over alphabet Σ, a basic problem (local alignment) is to find pairs of similar substrings, one from X and one from Y. For substrings X' and Y' from X and Y, respectively, the metric we use to measure their similarity is normalized alignment value: LCS(X',Y')/(|X'|+|Y'|). Given an integer M we consider only those substrings whose LCS length is at least M. We present an algorithm that reports the pairs of substrings with the highest normalized alignment value in O(n log|Σ|+rM log log n) time (r—the number of matches between X and Y). We also present an O(n log|Σ|+rL log log n) algorithm (L = LCS(X,Y)) that reports all substring pairs with a normalized alignment value above a given threshold.