测试代价敏感粗糙集中属性约简算法的研究

发布时间：2018-01-05 21:02

本文关键词：测试代价敏感粗糙集中属性约简算法的研究　出处：《广西师范大学》2016年硕士论文　论文类型：学位论文

【摘要】：粗糙集是一种刻画不完整和不确定性问题的数学工具,其不需要任何先验知识对数据进行分析和处理。面对如今高速的信息时代中海量数据的形成,粗糙集在分析处理数据中发挥了重要的作用。属性约简作为粗糙集理论研究的重要内容之一,其核心思想就是保证知识库的分类能力不变的前提下,删除冗余、错误或者不需要的知识。而代价敏感学习是目前机器学习、数据挖掘等领域研究热点之一,代价包括测试代价、误分类代价、计算代价和获取样本的代价等,其目的是以最小代价为目标建立分类器。将代价敏感学习引入粗糙集理论中的属性约简问题值得深入研究,目前将误分类代价引入粗糙集理论中的相关研究取得了不错的研究的成果,而测试代价敏感粗糙集理论的相关研究近几年才开始发展。本文主要研究测试代价敏感粗糙集中属性约简问题,分别以完备决策表和不完备决策表作为研究对象,主要的研究工作有以下几个方面。(1)为了解决测试代价敏感属性约简的高效性和准确性问题,提出一种基于免疫量子粒子群优化的最小测试代价属性约简算法。依据条件信息熵和测试代价因素定义适当的适应值函数,将最小测试代价属性约简问题转化为0-1组合优化问题,提出最小属性的属性约简问题是一种具有特殊测试代价的最小测试代价属性约简问题。最后结合量子粒子群和人工免疫方法给出约简算法,实验分别对比已有的最小属性约简算法和测试代价敏感属性约简算法,实验结果表明该算法是有效可行的。(2)在不完备决策表中,给出高效的计算容差类算法。提出不一致对象概念,研究不一致对象的性质,根据其性质给出在不一致对象下的核属性和属性约简的定义并设计求核属性算法。提出一个新的属性重要性定义,最后依据新的属性重要性定义设计一个最坏情况下时间复杂度和空间复杂度分别为O(k|C|2|U|)和O(|U|)的启发式属性约简算法,其中k为条件属性中缺省对象所产生的容差类最大的个数。算法过程只需逐步要求容差类的基数,大大减少了算法的计算过程。最后通过理论分析、实例分析和实验分析说明该算法是高效和可行性的属性约简算法,并且该算法同时适用于不一致不完备决策表和一致不完备决策表,给不完备决策表属性约简算法提供了新的方法。(3)提出不完备决策表测试代价敏感属性约简问题,给出不一致对象集定义以及求解不一致对象集的算法。根据不一致对象的性质改进属性重要性定义,考虑测试代价因素以及不一致对象个数的改变量给出一个新的属性重要性的定义和属性重要性中权重的设置方法,并给出属性重要性的计算算法。在此基础上,给出一个时间复杂度O(k|C|2|U|)和空间复杂度为O(|U|)启发式属性约简算法,其中k为条件属性中缺省对象所产生的容差类最大的个数,并通过理论分析、实例分析和实验分析说明该算法准确性和可行性。
[Abstract]:Rough set is a characterization of incomplete and uncertain problems of the mathematical tools, does not require any prior knowledge to analyze and process the data in the information age. The formation of massive data high speed today, played an important role in the data analysis of attribute reduction in rough set. As one of the important content of theoretical research rough set, its core idea is the guarantee to delete the redundant unchanged classification capacity of the knowledge base under the wrong, or do not need knowledge. And cost sensitive learning is one of the machine learning, data mining and other research hot areas, including the cost of the test cost, misclassification cost, computation cost and obtain the sample cost. Its purpose is to establish minimum cost as target classifier. Cost sensitive learning into the attribute reduction problem in the theory of rough set is worthy of further study, the misclassification cost The introduction of rough set theory in related research has achieved good results, and the test cost sensitive rough set theory research in recent years began to develop. This paper mainly studies the test cost sensitive rough set attribute reduction problem, respectively, to complete decision table and incomplete decision table as the research object, the main research work there are the following aspects. (1) in order to solve the problem of high efficiency and accuracy of the test cost sensitive attribute reduction, this paper proposes a minimal test cost immune algorithm of attribute reduction based on quantum particle swarm optimization. Based on the conditional information entropy and test cost factors defining appropriate fitness function, the minimum test cost attribute reduction into 0-1 a combinatorial optimization problem, the minimum attribute reduction attribute is a kind of special test cost minimum test cost. Finally, node attribute reduction problem Quantum particle swarm optimization and artificial immune method reduction algorithm, minimum attribute reduction algorithm and test cost sensitive attribute reduction algorithm were compared with existing experiments, experimental results show that this algorithm is effective and feasible. (2) in incomplete decision table, calculating the tolerance class algorithm is given. The inconsistent objects, concepts, research inconsistent with the nature of the object, according to its nature are defined in the inconsistent objects under the core attributes and attribute reduction and design for core attribute algorithm. Proposed a new definition of attribute importance, according to a new attribute to the definition of design a worst-case time complexity and space complexity respectively. O (k|C|2|U|) and O (|U|) heuristic attribute reduction algorithm, which produced by K as the default object condition attribute in the largest number of tolerance class. The algorithm only needs gradually tolerance class base, Greatly reduce the process of the algorithm. Finally, through theoretical analysis, case analysis and experimental analysis shows that this algorithm is feasible and efficient attribute reduction algorithm, and the algorithm is also applicable to inconsistent incomplete decision table and consistent incomplete decision table, for incomplete decision table attribute reduction algorithm provides a new method. (3) the incomplete decision table test cost sensitive attribute reduction problem, given inconsistent object set definition and solving inconsistent object set algorithm. According to the nature of inconsistent objects improved attribute importance is defined, considering the test cost and the method to set weight change given inconsistent object number of a new attribute the definition and importance of attribute importance in the calculation, and algorithm is given to the importance of attributes. On this basis, give a time complexity of O (k|C|2|U|) and the space complexity is O (|U|) heuristic attribute reduction algorithm, where k is the largest number of tolerance classes generated by default objects in conditional attributes. Theoretical analysis, case analysis and experimental analysis show that the algorithm is accurate and feasible.

【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】