基于冲突域渐减的属性约简算法

针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率, 首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的. 然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据, 研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上, 设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O(|C|²|U/C|)和O(|U|). 最后的实例和实验结果表明该方法是正确的,高效的.     

一个基于正区域的快速求核算法

现有利用差别矩阵设计的基于正区域的求核算法,其时间复杂度为O(|C‖U|2)。为降低求核算法的时间复杂度,给出了简化差别矩阵的定义和基于简化差别矩阵核的定义,并证明了该核与基于正区域的核是等价的。由于求简化差别矩阵的关键是求划分U/C,故利用基数排序的思想设计了一个快速求划分U/C的算法,其时间复杂度为O(|C‖U|)。在此基础上,利用简化差别矩阵设计了一个基于正区域的快速求核算法,其时间复杂度降为max{O(|C‖U|),O(|C‖U/C‖Up′os)}。实例说明了新算法的有效性。     

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

为降低基于修正差别矩阵的属性约简算法的时间复杂度和空间复杂度,首先给出了简化差别矩阵的定义,并证明了该矩阵所包含的信息量与修正差别矩阵的信息量等价.其次设计了一个高效的求U/C的算法,其时间复杂度被降为O∑|C|i=1|ki||U|.然后分析了基于修正差别矩阵的属性约简算法的不足,并使用上述高效求U/C的算法,设计了一个基于简化差别矩阵的属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为maxO(|C|2(|Up′os||U/C|)),O∑|C|i=1|ki||U|和max{O|C|(|Up′os||U/C|)),O(|U|)}.最后用一实例说明了新算法的高效性.     

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

在分析目前已有基于Rough Set的属性约简算法后,给出了一个新的度量属性重要性的计算公式,分析了该计算公式的性质,然后给出了一个时间复杂度为max{O(|A||U|log|U|),O(|A|2|U|)}的快速属性约简算法,最后用一个实例说明了算法的有效性.     

基于相对分辨能力的属性约简算法

在粗糙集理论中,分辨能力反映拥有知识的多少;为此,给出分辨能力相关概念、性质和计算方法,并提出基于相对分辨能力的约简定义,同时研究该约简定义与Hu差别矩阵约简之间的等价性,指出Hu差别矩阵约简可由相对分辨能力约简获得.为了进一步提高求解效率,通过减少约简过程中基数排序次数来提升效率,设计了相对分辨能力的约简算法,其时间复杂度为O(|C|~2|U|).实例分析和UcI中数据集的实验比较表明所提出的约简算法是有效的、可行的.     

粗等价类双边递减下多次Hash的渐增式求核与约简算法

为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析1,0,-1三类粗等价类的性质,把求正区域等价转化为0-粗等价类双边递减下的渐增式计算,结合1和-1-粗等价类的传递性,设计双边横向删减实体和纵向删减属性的优化规则,可在每一轮增量计算中缩减计算域,基于此设计多次Hash的属性增量划分方法;最后给出新的渐增式快速求核与约简算法,其中求核基于纵向优化规则,可在一次计算中求得多个非核属性,无需遍历全部属性.基于UCI、海量和超高维3类数据集进行多个实验,实验结果证明本文求核与约简算法是高效完备的,在海量数据与超高维数据集下有较大优势.     

粗糙集中属性约简的一个贪心算法

利用单属性的逼近精度、由决策属性定义划分的粗糙逼近精度以及它们的均值和方差 ,给出了属性重要性程度的一种度量方式。在此基础上 ,提出了粗糙集中属性约简的一个贪心算法 ,将各属性按照重要性由大到小依次加入到约简属性集中 ,直到满足约简条件为止 ,其特点是简单、容易实现 ,在条件属性较多的情况下 ,往往能够迅速求得一个属性约简。     

改进分辨矩阵下的增量式条件属性约简算法

通过分析现有分辨矩阵的不足,给出了基于条件熵的分辨矩阵定义,以得到不一致决策信息系统下的合理条件属性约简结果.基于改进分辨矩阵的定义,提出了相应的条件属性约简算法,并证明了其约简为不同于代数观点下的约简,而与信息观点下的约简相同.进一步,对该改进分辨矩阵做进一步修正,提出了一个增量式条件属性约简算法.实验结果表明:所提出的改进分辨矩阵下的条件约简算法总体上优于同类求解算法,而其增量条件约简算法能够获得稳定可靠的约简结果,同时约简效率得到较大的提高.     

一种基于新的条件信息量的属性约简算法

为了获得决策系统中更好的相对约简,讨论了属性约简与条件信息量的关系,提出了新的条件信息量,由此定义新的属性重要性。统一了一致决策表和不一致决策表属性约简方法,以新的属性重要性为启发信息,给出了计算新的条件信息量的高效算法。理论分析和实验结果表明,与现有的基于条件信息量的约简算法相比,该算法时间复杂度较低,同时约简后的属性数目更少。     

基于距离的直觉模糊粗糙模型及应用

将直觉模糊和区间直觉模糊集(数)的距离测度引入直觉模糊信息系统和区间直觉模糊信息系统,建立基于距离的粗糙集模型,并给出该模型两种约简-上下近似约简的定义.通过构造分辨函数,设计距离直觉模糊粗糙模型的知识约简及规则提取算法.最后将距离直觉模糊粗糙模型应用于信息系统安全审计风险判断,这不仅可为从直觉模糊和区间直觉模糊信息系统中获取知识提供一种粗糙集方法,而且还为信息系统安全审计风险的有效判断提供决策支持.     

信息系统的属性约简

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

含时变时滞函数的GM(1,1|τ_i)模型及其应用

针对带有时滞效应的小样本数据序列的预测建模问题,现有模型通常假设时滞期为固定值,忽略了时滞值动态变化对模型效果的影响.为了克服这一局限性,本文考虑系统时滞的动态变化效应,将GM(1,1|τ,r)模型的静态时滞参数推广为时变时滞函数,设计出非整数时滞取值区间对应的时变时滞参数表达式.提出以灰关联理论为基础的时变时滞函数的参数优化方法,推导出GM(1,1|τ_i)模型参数估计值以及预测序列的时间响应式.该方法不仅提高了模型对所分析序列的拟合度,还可充分利用时滞参数函数的数学性质,进一步研究时滞因素对系统发展趋势的影响.最后,将GM(1,1|τ_i)模型应用于福建省全省沿海港口货物吞吐量预测,并将建模预测结果与经典的GM(1,1)模型和GM(1,1,τ)模型进行比较.结果表明当原始序列具有时滞效应时,GM(1,1|τ_i)模型具有更高的建模精度,能够反映出更为复杂的系统时滞变化情况,扩展了含时滞参数灰色预测模型的适用范围.     

基于优先规则的复杂并行机调度问题研究

研究一类从实际指挥控制系统提炼的具有工件释放时间、机器可用时间和机器适用限制等约束的并行同速机调度问题.首先针对该问题建立混合整数规划模型;其次考虑到该问题的NPhard性以及实时调度的要求,提出基于优先规则的调度算法框架从而可以快速获得可行解;最后将该算法框架应用到实际案例并分析比较不同优先规则的效果,发现与工件释放时间相关的优先规则(如ERD,EFD)效果更好.值得一提的是,本文首次研究具有多重约束的并行机调度问题Pm|r_j,a_i,M_j|C_(max),TC.     

动态空间自回归固定效应面板模型的估计与应用

文章首次探寻了在空间系统稳定以及n和T均为很大的情况下,DSAC固定效应面板模型的拟极大似然估计量的渐近性质.研究发现:运用转换法估计时,在一般情况下得到拟极大似然估计量存在O(1/T)阶的偏差,当(n-1)/T→0时,转换法得到的估计量以√(n-1)/T的速度一致地收敛于真值,当(n-1)/T→∞时,估计量以T的速度收敛至一个退化分布;用直接法估计时,在一般情况下得到的估计量会产生max(O(1/T),O(1/n))阶的偏差,当n/T→0和n/T→∞时,估计量分别以n和T的速度收敛至不同的退化分布;偏差修正估计量比拟极大似然估计量具有更好的有限样本性质:当n/T³→0时,转换法得到的偏差修正估计量以√(n-1)/T1的速度一致地收敛于真值,当n/T³和n³/T同时趋于0时,直接法得到的偏差修正估计量以√nT的速度一致地收敛于真值;直接法可以一致地估计个体效应和时间效应而转换法不能;当扰动项存在空间相关结构时DSAC固定效应面板模型的有限样本性质优于DSAR面板模型;最后用一个实证研究的例子表明了DSAC模型的应用价值.     

局部几乎正则多部竞赛图中的分量共轭圈

一个n-部竞赛图是n-部完全图的一个定向.令V₁,V₂,…,V_n是n-部有向图D的部集.如果D中存在两个不相交的圈C和C'使得对于每一个i∈{1,2,…,n}都有V_i∩(V(C)∪V(C'))≠ƒ,则称C和C'是D的一对分量共轭圈.针对多部竞赛图的共轭圈问题,提出了分量共轭圈的定义,同时证明了每一个至少有6个顶点的部集具有相等基数的局部几乎正则多部竞赛图的分量共轭圈的存在性问题.     

系统可靠性决策规则发掘方法研究

为根据已有的经验提炼出对系统可靠性评判的决策准则,基于汪培庄的因素空间理论与笔者提出的空间事故树理论思想,构造了一套从决策经验中提取决策准则的方法.该方法适用于条件属性为域值的多因素影响系统.首先数据归一化构建基础信息决策表Ψ(T).计算x_i与x_j关于属性a_q的相似度S(x_i,x_j,a_q),形成相似性表Θ(U,C,S).根据相似性阈值f将Θ(U,C,S)化简得Θ′(U,C′,S).根据模糊度θ,将Θ′(U,C′,S)改造为模糊二项相似表Ω(Θ′,θ),从而构建区分矩阵Γ(Ω).对U进行决策组划分,形成决策项,组成决策归纳表L(T).利用L(T)和Ψ(T)得到了切合实际使用的决策语义表L(T).从方法处理实际问题的结果看,在只利用条件属性集合与对象集合的条件下,即可判断经验决策的合理性.经过一系列的数据处理最终得到的决策语义表L(T),它可以判断系统工作状态属于哪种系统可靠性的决策,并确定了这种决策的置信度.     

基于限制容差关系和集对分析的数据依赖在IIS中的应用

利用限制容差关系和集对分析方法,分别给出了不完备信息系统(IIS)下对象依赖和属性依赖的定义,并将其应用于IIS约简,提出了利用基于限制容差关系的对象依赖进行对象约简和利用基于集对分析的知识依赖进行属性约简的方法以及相应的算法,以这些算法为依据进行约简得到了较好的结果.最后结合两个实例加以分析,验证这种限制容差关系模型和集对分析方法相结合的方法对处理IIS是合理有效的.     

改进的加权复杂网络节点重要度评估的收缩方法

分析了加权复杂网络的结构特点,综合考虑了边权对节点重要度评估的影响,给出了加权节点重要度的新定义,并提出了改进的适用于加权网络的节点收缩方法.该方法认为最重要的节点就是收缩后加权网络凝聚度最大的节点,其算法的时间复杂度为O(n³).该方法有助于更准确地发现复杂网络中的关键节点.最后的实验分析验证了方法的有效性和可行性.