基于不可区分度的启发式快速完备约简算法

在已有的粗糙集属性约简算法基础上,给出了一个新的度量属性重要性的不可区分度函数,分析了不可区分度的性质,提出了一种能有效处理噪声的基于不可区分度的快速完备约简算法,最坏时间复杂度为max(O(|A||U|),O(|A|2|U/A|)).理论分析和实验结果表明,该约简算法在效率上较现有算法有显著提高,能较好抵制数据噪声,适于对大数据集进行处理.     

不完备信息系统的属性约简算法

根据不完备信息系统的定义和特点,建立基于集合容差关系的粗糙集模型,构造条件属性的可辨识矩阵,分析决策属性的重要性。阐述并比较3种属性约简方法,对同一个不完备信息表的处理结果表明,3种方法可以得到基本一致的约简结果,验证了其有效性。     

同可区分度属性约简的研究

通过具体算例指出基于同可区分度属性约简不是王国胤等提出的条件信息熵约简。理论上证明了基于同可区分度属性约简仅是基于差别矩阵的HU属性约简,它是一种基于梁吉业等提出的新条件信息熵属性约简。证明了同可区分度约简协调集一定是代数协调集和信息熵协调集,从而代数约简核属性和信息熵核属性一定是同可区分度约简核属性的子集。     

基于可区分度的连续空间属性约简算法研究

针对现有粗糙集属性约简方法中存在的连续数据处理时的信息丢失、粒化策略引入不一致信息、参数寻优困难等问题,提出一种适用于连续型数据、基于类别可区分度的非单调性启发式属性约简算法。首先以各样本的标签为依据对论域进行划分,同一标签的样本组合成一个簇,定义每个簇的类间可区分度和类内可区分度;其次,以最大化类间可区分度、最小化类内可区分度为约简原则,定义了一种新的属性重要性判别准则以确定最优约简集,从而提高后续分类器的分类性能。在十一个UCI数据集上与其他六种属性约简算法进行对比实验。结果表明,与六种算法相比,所提算法获得的约简集平均维度减小了1.16,平均分类精度提高了3.42%,其表现出更好的约简性能。     

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

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

可区分度与全粒度属性约简

全粒度粗糙集时空复杂度较高,难于计算属性约简.针对此问题,文中利用等价类定义信息系统中的可区分度,并研究其性质,证明基于可区分度的属性约简等价于绝对约简.定义决策系统中的正区域可区分度,并探究其性质,证明基于正区域可区分度约简是全粒度Pawlak约简的超集,但绝大部分情况下等于全粒度Pawlak约简,可作为全粒度Pawlak约简的近似.理论分析和实验表明,相比其它属性约简算法,基于正区域可区分度约简在计算复杂度和分类准确率等方面具有较大优势.     

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

在粗糙集理论中,知识约简已经成为其核心内容之一。针对相关文献中基于相容矩阵的不完备信息系统属性约简算法,提出了一种新的相容矩阵定义,该矩阵能够减少关注的条件属性。同时,也证明利用该矩阵所求的属性约简与相关文献中的属性约简是等价的。给出了其属性约简算法,提高了属性约简的速度。     

基于全序优势关系的不完备模糊信息系统及其属性约简

针对具有优势关系的不完备模糊决策信息系统,在分析了现有的两种优势关系的优缺点的基础上,利用属性值的概率分布原理提出了一种新的全序优势关系,这种关系合理地改进了扩展优势关系,克服了限制优势关系不能对论域中所有对象进行比较的缺点,并进一步给出了基于全序优势关系的上下近似表达式,相对约简的定义和具体的计算方法。最后用实例说明这种方法的有效性。     

基于局部可调节多粒度粗糙集的属性约简

经典的多粒度粗糙集模型采用多个等价关系(多粒度结构)来逼近目标集。根据乐观和悲观策略,常见的多粒度粗糙集分为两种类型:乐观多粒度粗糙集和悲观多粒度粗糙集。然而,这两个模型缺乏实用性,一个过于严格,另一个过于宽松。此外,多粒度粗糙集模型由于在逼近一个概念时需要遍历所有的对象,因此非常耗时。为了弥补这一缺点,进而扩大多粒度粗糙集模型的使用范围,首先在不完备信息系统中引入了可调节多粒度粗糙集模型,随后定义了局部可调节多粒度粗糙集模型。其次,证明了局部可调节多粒度粗糙集和可调节多粒度粗糙集具有相同的上下近似。通过定义下近似协调集、下近似约简、下近似质量、下近似质量约简、内外重要度等概念,提出了一种基于局部可调节多粒度粗糙集的属性约简方法。在此基础上,构造了基于粒度重要性的属性约简的启发式算法。最后,通过实例说明了该方法的有效性。实验结果表明,局部可调节多粒度粗糙集模型能够准确处理不完备信息系统的数据,降低了算法的复杂度。     

基于辨识矩阵的不完备多粒度约简

面向具有缺失属性值的不完备数据,文中从辨识矩阵的角度构造不完备信息系统和不完备决策系统的多粒度约简结构.首先,讨论基于悲观和乐观多粒度近似的不完备信息系统的约简性质,构造不完备信息系统和不完备决策系统的3种多粒度辨识矩阵.然后,理论性证明通过对构造的辨识矩阵进行析取、合取逻辑运算,可精确得到不完备信息系统和不完备决策系统的所有多粒度近似约简.最后通过实例验证文中多粒度约简方法的有效性和实用性.     

基于优化可辨识矩阵和改进差别信息树的属性约简算法

运用可辨识矩阵表示信息系统中所有对象的区分信息,为研究属性约简提供了新方向。然而,传统的可辨识矩阵在构造结束后才利用核属性消除冗余元素项,忽略了核属性在矩阵构建过程中的作用。针对这一问题,文中做了以下研究:1)优化可辨识矩阵的构造方式,在计算任意两个对象的区分信息之前,先判断核属性上的取值是否相等,如果不相等,则直接将对应元素项记为Φ,忽略对其他条件属性的判断;2)提出属性加权重要度的概念,综合考虑每个条件属性占可辨识矩阵中非空元素项的比率(称为宏观重要度)与每个属性对区分对象的贡献程度(称为微观重要度),并通过例子说明了该度量方法的合理性;3)针对优化后的矩阵仍然存在大量冗余元素和空集这一缺陷,结合差别信息树的概念提出基于优化可辨识矩阵和属性加权重要度的差别信息树。按照属性加权重要度对优化可辨识矩阵中所有非空元素项进行排序,使得重要度高的属性被更多的节点共享;且在构建过程中将不包含核属性的元素项映射到树中的一条路径上,而包含核属性的元素项则被直接忽略。最后,提出基于优化可辨识矩阵和改进差别信息树的约简算法HSDI-tree。在UCI的5个数据集上分别比较了HSDI-tree算法与CDI-tree,DI-tree和IDI-tree算法的约简结果和节点个数,实验结果表明HSDI-tree算法能有效找到最小属性约简且空间压缩能力更好。     

Attribute Reduction Based on Inclusion Degree for Incomplete and Fuzzy Decision Information Systems

The information systems with incomplete attribute values and fuzzy decisions commonly exist in many applications whose knowledge reduction is one of the most important practical significance. Model of incomplete and fuzzy decision information system is firstly constructed. On the basis of the notion of inclusion degree between fuzzy sets, the attribute reduction for incomplete and fuzzy decision information system, which ensures invariable inclusion degree between every tolerance class and fuzzy decision set, is raised. To reduce the complexity of finding attribute reduction, discernibility sets, discernibifity matrixes and the minimal disjunctive normal form of discernibility sets for incomplete and fuzzy decision information system are introduced. Finally, the algorithm and an example are given, and the solution of the example is proved that the approach to attribute reduction based on inclusion degree is valid.     

基于改进分辨矩阵的属性约简方法

在分辨矩阵的属性约简算法的研究中,需比较决策系统中各对象生成矩阵元素,导致所得分辨矩阵过于庞大,且造成较大的时间开销.为降低利用分辨矩阵求取属性约简算法的复杂度,依据条件等价类将原决策系统分解为一相容对象集与一非相容对象集,给出条件相对于决策的可辨识关系定义与改进的分辨矩阵定义,将条件相对于决策的可辨识关系变化作为属性约简的判定标准,结果证明改进分辨矩阵的属性约简与保持正域不变的属性约简等价.推理证明与仿真实例说明,改进方法的高效性与完备性.     

基于改进差别矩阵的属性约简增量式更新算法

针对目前基于差别矩阵的属性约简算法需要耗费大量的时间和空间,粗糙集中求属性核和属性约简更新效率低以及有关属性约简的增量式更新算法目前还比较少等问题,提出了一种基于改进差别矩阵的属性约简增量式更新算法.该算法在更新差别矩阵时,仅须插入某一行及某一列,或删除某一行并修改相应的列,因而可有效地提高核和属性约简的更新效率.然后在分析新增对象x与原决策系统对象的关系的基础上,给出了属性约简增量更新算法.理论与实验分析表明,提出的算法提高了属性约简的更新效率,明显降低了时间和空间复杂度.     

基于粒计算与区分能力的属性约简算法?

传统的属性约简方法将整个数据集一次性装入内存,很难适应大数据背景下的数据分析。为此文中提出基于粒计算与区分能力的属性约简算法。该算法运用统计学中的分层抽样技术,拆分原始大数据集为多个样本子集(粒),在每个粒上运用属性的区分能力进行属性约简,最后将各粒约简结果进行加权融合,得到原始大数据集的属性约简结果。实验表明该算法对海量数据集进行属性约简的可行性和高效性。     

基于差别矩阵启发式决策表属性约简算法

属性约简是粗糙集理论研究的核心内容之一,足知识获取的关键步骤.针对大规模数据集,基于决策表差别矩阵属性约简不具备可操作性缺点;以及基于差别矩阵属性频度的约简算法没有考虑到差别矩阵元素中属性个数多少的缺陷.基于差别矩阵元素的基数越小,其属性越重要的思想,按照基数由小到大的顺序,利用矩阵中具有相同基数的矩阵元素的簇集中属性出现的频度,确定属性的重要度,提出一种快速搜索属性约简算法,能快速搜索到属性的最优或次优约简.实验结果表明算法是可行、有效的.     

差别矩阵属性约简的信息观解释

常见的属性约简定义有三种,即基于代数观的属性约简,基于信息观的属性约简和基于HU差别矩阵的属性约简。已有文献证明这三种属性约简彼此之间不等价。王国胤教授定义了一种新的决策表信息熵计算方法,在此方法基础上给出了粗糙集理论代数观的一种新的信息观解释。最近有学者提出了一种基于新信息熵的属性约简。经深入研究,我们证明了该属性约简与基于HU差别矩阵的属性约简是等价的,从而给出了基于HU差别矩阵的属性约简的信息观解释。     

基于知识粒度的不完备决策表的属性约简的矩阵算法

通过考虑云计算环境下的服务器资源负载严重、资源描述方式单一以及资源配置方法效率不高的问题以及云计算本身的特点,根据本体论和多代理机制提出一种高效实用的基于域(DOMAIN)和虚拟组织(Virtual Organiza-tion i.e.VO)的完全分布的、高效的资源配置策略。在这个策略中,每个节点都采用CCSM(Cloud Computing SystemModel)体系结构,该体系结构根据本体论引入了多代理的分层结构,并利用本体论表达语义信息来对资源进行管理,根据分层结构可以减少远程访问的时间,提高访问效率。根据语义信息来获得对概念的统一理解形式,过滤掉无关信息以缩小查询范围,并利用概念关联进行推理以实现对查询请求的泛化,由此可以提高查询过程中的查全率和查准率。     

基于可辨识矩阵的启发式属性约简方法及其应用

在基于可辨识矩阵的属性约简算法的基础上，提出了基于可辨识矩阵的计算属性重要性的方法，并以此作为启发式知识来约简决策表中的冗余属性。这种方法直接源于评审数据，思路清晰，拟合结果表明本约简算法合理、可靠。