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

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

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

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

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

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

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

通过对差别矩阵的研究,提出一种压缩差别矩阵的构造方法及相关的属性集求核算法,减少了差别矩阵中大量的空值存储,并且避免对象之间的盲目比较.算法的时间复杂度为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|2|U|log|U|),为降低该求核算法的时间复杂度,给出了基于正区域的简化决策表定义和相应核的定义.证明了该简化决策表的核与原决策表的核等价.由于求正区域的简化决策表首先要求划分U/C,而求划分U/C的最好算法的时间复杂度为O(|C||U|log|U|),因此以基数排序的思想设计了一个新的求划分U/C的算法,其时间复杂度为O(|C||U|).最后以快速缩小搜索空间为目的设计了一个新的求正区域POSC(D)的算法.在此基础上,利用核的性质设计了一个新的求核算法,其时间复杂度为max(O(|C||U|,O(|C|2|U/C|)).并用实例说明了算法的实用性.     

一种简化差别矩阵的属性约简方法

针对现存差别矩阵属性约简算法存在的缺陷,以及通过差别矩阵求约简属性时过程比较复杂,对比做了部分改进.通过对条件属性进行归类分组,提取代表性记录来生成差别矩阵,简化了差别矩阵的阶数和求约简属性的复杂度.从而在算法的时间复杂度和空间复杂度方面做了优化,节约了算法的时间和空间复杂度.实例表明算法可以有效地对属性进行约简,可获得理想的结果,并且改进后的算法简单、高效.     

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

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

一种基于二进制可辨矩阵的属性约简算法

基于可辨矩阵的属性约简算法都是从信息系统中直接求得约简，提出了分两步求得约简，降低了算法的时间复杂度为O(mn^2)，第一步计算出近似约简，第二步去掉其中的冗余属性。改变了过去人们认为基于可辨矩阵的特征选择算法的时间复杂度不低于O(m^2n^2)的观点(其中m为数据集中特征／属性的个数，n为数据集中样本的个数)。最后给出了实验结果.     

分类算法中基于差别矩阵的属性约简方法

差别矩阵中会出现大量的重复元素占用大量内存,当数据太稠密时,构成的差别矩阵太大不容易操作且计算代价较高。本文提出了一种基于简化差别矩阵的属性约简算法(SDMAR),在属性约简之前,通过计算属性相似度,对属性进行了合并操作,得到简化决策表。根据简化决策表构造差别矩阵,计算差别矩阵中出现次数最多的属性并删除包含该属性的元素,当差别矩阵为空时终止操作,以达到对决策表属性约简的目的。通过算法及实例分析得到属性约简过程的时间复杂度有所减小。     

判别圈向量的一个有效算法

从圈空间?(G)中任取出一向量c,判别它是否圈矩阵之冗余行,可以用c与?(G)中其余各向量比较的办法来解决,所耗时间为O(2|E(G)|-V|G|),,本文通过关联矩阵的变换,给出一个有效算法,其时间复杂度为O(|V(G)|~2|E(G)|)。设B(G)是图G之关联矩阵,c=(q_1,q_2,…q_ε)是圈空间?(G)中任一向量;本文只考虑无向有限单图,计算在0-1二元域内进行。判别c是否圈向量算法如下:     

粗糙集高效遗传约简算法

提出了简化差别函数的概念及其算法，简化差别函数不仅具有与决策表相同的决策能力，而且剔除了由决策表导出的原始差别函数中的重复项和冗余项．为了降低遗传约简算法适应度函数的搜索空间，有效提高计算速度，又提出了一种高效遗传约简算法，其将染色体时简化差别函数的覆盖度以及染色体中包含1的个数作为适应度函数的参数，从而保证了算法朝着最小约简收敛，并从理论上证明了算法的属性约简结果为最优，算法的时间复杂度为O（｜f′｜｜｜C｜｜U｜^2）,同时，通过4个实例对算法进行了验证，结果表明简化差别函数的项分别为原来的0．39％、0．0008％、0．00008％和0．0003%，且在500代以内能够获得最小属性约简．     

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

影响基于差别矩阵的属性约简算法效率的主要因素有计算U/C等价类和差别矩阵的大小.为了解决差别矩阵大小影响属性约简算法计算效率,分析了基于差别矩阵的属性约简算法中差别矩阵定义的不足,重新定义了一种压缩差别矩阵,删除差别矩阵中大量的空元素和相同元素,从而进一步减少了差别矩阵元素的个数,并设计基于压缩差别矩阵的属性约简算法.对UCI及其他数据库进行仿真,实验结果表明该算法具有高效性.     

基于粗糙集理论的决策表属性约简算法

属性约简是粗糙集理论的一个重要内容,是进行知识获取中的核心问题之一.本文在粗糙集理论的基础上构造了区分图,在区分图上以属性的重要度作为启发信息,快速缩小搜索空间,求解最小属性约简.给出了一个最坏情况下时间复杂度为max（O（｜C｜^2）,O（｜C‖U｜^2））的快速属性约简算法.该算法统一考虑一致性决策表和不一致性决策表两种情况下的属性约简.     

一种快速属性约简算法

基于差别矩阵的属性约简算法，先要求出差别矩阵，随着问题的规模增大，存放差别矩阵的空间和算法的执行时间过大和过长，让计算机难以承受．针对这一问题，提出了差别对象对集的定义，给出了基于差别对象对的属性约简定义，并证明了该定义等价于基于差别矩阵的属性约简定义．利用差别对象对，设计了一个新的属性约简算法．由于这一算法在求属性约简的过程中不用生成差别矩阵和大量的无用元素，因而大大减少了存储量和计算量，从而提高了算法的效率．计算实例说明了新算法的高效性．     

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

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

一种信息系统求核的新方法

为简化用差别矩阵求核的计算方法,给出了差别矩阵与核关系的定理,并在此基础上给出了一种新的求核方法．新算法从差别矩阵中直接提取出核属性元素并利用该定理的结论给出信息系统中核的构成．经计算,该算法的复杂度为O(n^2√m)。     

因素空间理论的因素约简算法

为讨论差转计算在多因素决策问题中对因素系统的约简性能,通过理论分析与实证检验,在算法原理与机制的基础上深入讨论了算法的因素约简能力,并与基于差别矩阵的粗糙集因素约简算法进行比较.研究结果表明:差转计算在进行决策的过程中,确保了对结果有重要影响的因素进入经验推理系统,影响不大的因素在决策的过程中自动地被舍弃,从而实现了因素的约简.在6个UCI数据集上,通过对因素约简结果与时间复杂度两个方面的讨论,得出差转计算的因素约简能力同差别矩阵算法相当,在时间复杂度方面远优于差别矩阵算法.     

基于链表的不完备决策表属性约简算法

差别矩阵作为决策信息系统属性约简的方法是有效的;但空间利用率不高。通过对算法空间利用率及时间效率进行研究,提出基于链表的改进算法;并引入链表的基本运算。该算法通过使用链表的节点存储基于限制容差关系下有效的差别矩阵元素,并在约简过程中通过不断删除不必要的节点以节省时间。通过理论与实例证明其有效性和正确性。     

排序距离矩阵蛋白质结构比对算法

提出一种改进的SortMatAlign算法, 通过快速排序预处理距离矩阵, 使MatAlign算法的时间复杂度由O(N₄)降为O(N₃). 结果表明, SortMatAlign算法计算出的RMSD值平均是MatAlign算法的1.098倍, 使用残基个数和RMSD综合衡量标准的S值平均是MatAlign算法的0.968倍, 在同等条件下, 运行速度比MatAlign提高18.276倍.     

复杂性O(|υ|1/2*|A|)s-t连通度算法

使用简单网络的最大流算法给出复杂性为O(|μ|1/2*|A|)s-t连通度算法.此算法为一有效的多项式时间算法.