基于增量计算的信息系统属性粒结构计算方法

针对不可分离信息系统的属性粒结构计算问题,提出一种利用分治和增量计算相结合的计算方法。首先,研究了在信息系统函数依赖集上增加新的函数依赖(FD)后,信息系统属性粒结构的变化规律,证明了信息系统结构增量定理;其次,通过移除部分函数依赖,使不可分离信息系统成为可分离信息系统,利用分解定理计算出可分离信息系统结构;然后,将移除的函数依赖加入可分离信息系统,利用增量定理计算出原信息系统结构;最后,给出了计算不可分离信息系统属性粒结构的算法,分析了算法复杂度。与直接计算不可分离信息系统的粒结构相比,该计算方法可将计算复杂度从O(n×m×2ⁿ)降低到小于O(n×k×2ⁿ)(k1×m₁×2^n₁)+O(n₂×m₂×2^n₂)(n=n₁+n₂,m=m₁+m₂)。理论分析和实例计算表明,所提方法能有效降低不可分离信息系统属性粒结构的计算复杂度。     

信息系统的属性信息粒计算方法

根据属性上的函数依赖关系,提出了信息系统属性信息粒的概念,并给出了可分离信息系统的粒结构计算方法。首先,定义了信息系统可分离性,证明了如果一个信息系统是可分离的,则该系统的粒结构可分解为该系统的子系统粒结构的笛卡儿乘积;其次,给出了信息系统可分离性的判别方法及信息系统分解算法;最后,分析了该计算方法的复杂度。分析结果表明,与直接计算信息系统的粒结构相比,该计算方法可将计算复杂度从O(2ⁿ)降低到O(2^n₁+2^n₂+…+2^n_k),n=n₁+n₂+…+n_k。理论分析和实例计算表明,该计算方法是可行的。     

序信息系统属性约简的一种启发式算法

在序信息系统中引入了知识的信息量和知识粒度的概念,得到了它们的若干性质和定理。证明了在知识约简过程中,信息量的变化趋势是递减的;利用信息量的概念,定义了属性的重要性,并以属性重要性作为启发信息,提出了一种基于信息量的属性约简启发式算法,该算法的时间复杂度为O（|A|³|U|²）;最后通过例子说明,该算法能得到序信息系统的一个约简。     

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

给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|）,最后用一个实例说明了新算法的高效性。     

基于信息熵的二进制差别矩阵属性约简算法

给出一个简化的二进制差别矩阵的属性约简定义,并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵,设计了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。在此基础上,设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法,其时间复杂度和空间复杂度分别为max{O（|C||U|）,O（|C|²|U/C|²）}和max{O（|C||U/C|²）,O（|U|）},最后用一个实例说明了新算法的高效性。     

信息量不完备决策表属性约简的一种新算法

目前,基于不完备决策表的属性约简研究较少。基于信息量的不完备决策表属性约简是一种新的属性约简。由于在该属性约简中,计算相容关系是最主要的计算,也比计算等价关系要难得多。基于信息量的不完备决策表的属性约简算法的时间复杂度一般为O（|C|²|U|²）。为降低其时间复杂度,首先分析了老算法的不足,然后给出了一个效率较好的计算相容类的算法。最后设计了一个新的基于信息量的不完备决策表的属性约简算法,其时间复杂度为O（|C|²|U|²）。     

基于相容矩阵的改进属性约简算法

原属性约简算法在计算相容关系时,存在大量重复计算,从而导致时间复杂度为O(|C|3|U|2)。针对该问题,基于不完备决策表,提出时间复杂度为O(|U|2)的高效相容矩阵计算算法,在此基础上,设计改进的基于相容矩阵的属性约简算法。通过实例证明,当空间复杂度相同时,改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。     

快速的属性约简算法

属性约简的效率是粗糙集等软计算理论的核心问题之一。为了提高约简效率,在分析不可分辨关系和基数排序特点的基础上,提出了一种时间复杂度为O（|C||U|）的求核算法。然后,运用改进的属性重要度作为启发信息,得到一种快速的属性约简算法,时间复杂度为O（|C|²|U|）。最后,通过UCI机器学习库中的一些数据集对算法进行测试,证明了算法对大型的数据集进行属性约简的高效性。     

基于有序差别集的高效属性约简算法

基于可分辨矩阵的属性约简算法需要占用大量的存储空间,可分辨矩阵中许多元素项对约简是多余的;并且随着问题规模的增大,该类算法的效率并不理想。针对上述不足,提出一种基于有序差别集的属性约简算法,该算法不需要创建可分辨矩阵和生成多余的元素项,大大降低了存储量和计算量,从而提高了属性约简效率,使算法的时间复杂度和空间复杂度分别降为max{O（|C|² |U/C|²）,O（|C|²|MsCount|）}和O（|MsCount|）。实验表明该算法是有效的、高效的。     

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

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i相似文献   

基于概念格的多层属性约简方法

属性约简是粗糙集理论中的核心问题之一,概念格是进行知识表示和数据分析的一种有效工具。文中利用概念格作为约简工具,给出基于概念格的多层属性约简算法,提出相融可辨概念、相融等价概念、亏n级等概念,研究内涵亏值对分类能力变化产生的影响,给出概念格中形式背景约简的判定定理。文中算法能完备地求出所有可约简的最大属性集合,从而为概念格中属性约简提供一种有效方法。最后,通过实例分析和实验对比说明该约简算法的可行性与有效性。     

Allocating tree structured programs in a distributed system withuniform communication costs

Studies the complexity of the problem of allocating m modules to n processors in a distributed system to minimize total communication and execution costs. When the communication graph is a tree, Bokhari has shown that the optimum allocation can be determined in O(mn²) time. Recently, this result has been generalized by Fernandez-Baca, who has proposed an allocation algorithm in O(mn^k+1) when the communication graph is a partial k-tree. The author shows that in the case where communication costs are uniform, the module allocation problem can be solved in O(mn) time if the communication graph is a tree. This algorithm is asymptotically optimum     

协调决策形式背景及其属性约简

主要讨论协调决策形式背景的属性约简。首先定义了形式背景基础上的二元关系,并给出了协调决策形式背景,决策约简的定义。同时,给出了决策可辨识矩阵,得到协调决策形式背景知识的约简方法。     

基于条件信息熵和相关系数的属性约简算法

粗糙集的属性约简是一个NP难问题,获得较为高效的算法是研究的主要目的。针对传统的粗糙集属性约简算法效率不高、速度不快的问题,提出基于相关系数和条件信息熵的属性约简算法,把决策表的非核属性约简过程转化为相关系数的运算,能减少对决策表的扫描次数,降低算法时间复杂度,降低算法冗余,提高属性约简的效率。并利用k-fold轮换对比方法计算相关系数,较大地减少了计算量,同时能得到次优属性约简结果。给出了算法内容,并结合实验进行了验证。     

不协调决策形式背景的矩阵型属性约简

形式概念分析的属性约简是知识表达和数据处理的一种有力的工具。对于不协调决策形式背景,已有多种属性约简的方法。从布尔矩阵运算的角度研究不协调决策形式背景的属性约简问题,提出属性约简的新的刻画。首先,借助矩阵的运算给出广义矩阵协调集的定义,并研究属性之间相似性的度量。接着,针对在属性约简过程中起不同作用的属性,将条件属性区分为核心属性和非核心属性,提出一个属性是否是核心属性的充要判断条件,以及得出属性约简的判别方法。最后,在此框架上设计出不协调决策形式背景属性约简的一种启发式算法,通过例题说明此算法的可行性和合理性。通过属性约简,该形式背景下的概念格计算更为简便。上述结果有助于进一步的应用及为研究形式概念分析的矩阵方法提供理论基础。     

协调决策形式背景下概念格的属性约简

概念格是知识处理与分析中的一个有力工具,对它进行约简可以提高效率简化问题。该文在协调决策形式背景下给出了协调集及属性特征的判定定理,并在此基础上得到了一种求属性约简的方法。     

基于改进A*算法的无人车路径规划

传统的A^*算法在无人车路径规划中存在规划时间较长和搜索范围较大的缺点。综合分析A^*算法的计算流程后,从四个方面对A^*算法进行改进：1）目标性拓展,即根据待扩展节点和目标节点的相对位置来有目标性地选择不同的象限进行节点拓展;2）目标可见性判断,即判断待扩展节点与目标点之间有无障碍物,若无障碍物则跳出A^*算法的探索过程,以此减少多余的搜索;3）改变A^*算法的启发函数,即增加待扩展节点的n辈父节点到目标点的代价估计,以此减少到目标点的代价估计的局部最优情况;4）改变扩展节点的选取方略,即改变传统的最小化启发函数来选择扩展节点的方式,通过引入模拟退火法来优化扩展节点的选择方式,使得搜索过程尽可能向靠近目标点的方向进行。最后通过Matlab仿真实验结果表明,在模拟的地图环境下,提出的改进A^*算法在运行时间上减少67.06%,经历的栅格数减少73.53%,优化路径长度浮动范围在±0.6%。