基于属性分类的形式概念研究-霍思林.docx

《基于属性分类的形式概念研究-霍思林.docx》由会员分享，可在线阅读，更多相关《基于属性分类的形式概念研究-霍思林.docx（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、lllil11 密级 : 保密期限 : 硕士学位论文 基于属性分类的形式概念研究 Research on formal concept based on attribute classification 学 号 姓 名 学位类别 学 科 专 业 (工程领域） 指导教师 完成时间 答 辩 委 员 会 主席签名 E14201029 霍思林 工学硕士 计算机应用技术 徐怡副教授 2017年 4月 牧切 、 _ 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为

2、获得安徽大学或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学 位 论 文 作 者 签 名 ： 签 字 日 期 ： 年 厂 月 if曰 学位论文版权使用授权书 本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关 数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 (保密的学位论文在解密后适用本授权书 ） 穩、作 学位论文作者签名： 导师签名： 签 字 曰

3、 期 ： 年 V月沁曰 签字日期： .卩年了月 v“/曰 _ Y3215535 摘要 德国 Wille教授于 1982年首次提出了形式概念分析理论，它是一种能够从形 式背景中进行数据分析和规则提取的工具。对于形式概念分析理论，现有的研宄 主要集中在形式背景知识的获取和形式概念的计算，其中形式背景是形式概念分 析的数据来源；形式概念的计算是形式概念分析的数据结构。本文重点就形式背 景知识和形式概念的计算两个方面，基于粒计算的思想，对形式概念进行了属性 约简、属性分类以及动态计算的研宄，获得的成果如下所示： (1) 本文提出了基于属性分类关系的形式概念属性约简算法。首先，针对 目前己有的形式概念属

4、性约简算法存在着一些明显的不足，如计算属性约简的时 间复杂度偏高；属性等价类和属性约简是分开计算的，因此存在冗余计算；形式 背景知识向覆盖知识转换的过程中增加了系统存储的开销等等。针对这些不足， 文中定义了两个启发式算子，并计算出属性之间的分类关系。然后，本文提出了 基于属性分类关系的形式概念属性约简算法。该算法在降低计算时间复杂度条件 下，并减少了冗余计算和系统存储的开销，提高了属性约简的计算效率。最后， 通过实例和仿真实验对基于属性分类关系的形式概念属性约简算法的有效性进 行了验证。 (2) 本文提出了基于属性分类的多层次形式概念分析模型及基于属性分类 的形式概念动态构造算法。在传统形式概

5、念分析中，属性分析是单粒度单层次的 结构，然而现实中树形结构的属性分类是普遍存在的。因此，本文提出了基于属 性分类的多层次形式概念模型，分析了形式概念在不同层次泛化空间下的相关性 质，并提出了基于形式概念分析的属性泛化与细化方法，其中属性泛化约简概念， 属性细化提高精度。在此基础上，基于属性分类层次的变化，提出了一种动态形 式概念构造算法，该算法采用自学习的方式对己有的知识加以使用，它不仅继承 了己有的渐进式算法的优点，而且还能处理形式概念自身数据动态变化的问题。 最后，通过实例和仿真实验说明本文所提方法的有效性。 关键词：形式概念分析；粒计算；概念 格；属性约简；属性泛化 Abstract

6、In 1982, Professor Wille first proposed the theory of formal concept analysis, which is a tool for data analysis and rule extraction from formal context For the theory of formal concept analysis, the existing researches mainly focus on the acquisition of formal context knowledge and the calculation

7、of formal concept. The formal context is the data source of formal concept analysis, and the calculation of formal concept is the data structure of formal concept analysis. This paper focuses on two aspects: the knowledge of formal context and the calculation of formal concept. Based on the idea of

8、granular computing, this paper studies the attribute reduction, attribute classification and dynamic calculation of formal concept, and the results obtained are shown as follows. (1) This paper proposes a formal concept attribute reduction algorithm based on attribute classification relation. Firstl

9、y, there are some obvious shortcomings in the existing formal concept attribute reduction algorithms, such as the time complexity of computing attribute reduction is high; the attribute equivalence class and attribute reduction are calculated separately, there is redundant computation; the conversio

10、n of formal context knowledge to the covering knowledge increases the cost of system storage and so on. In order to solve these problems, two heuristic operators are defined in this paper, and the relationship between attributes is calculated. Then, this paper proposes an attribute reduction algorit

11、hm based on attribute classification relation. This algorithm can effectively reduce the computational time complexity, and reduce the redundant computation and the system storage cost, and improves the computational efficiency of the attribute reduction* Finally， the validity of the formal concept

12、attribute reduction algorithm based on attribute classification relation is verified by examples and experiments. (2) In this paper， we propose a hierarchical formal concept analysis model based on attribute classification and a dynamic construction algorithm based on attribute classification. First

13、 of all, in the traditional formal concept analysis, the attributes are single granularity and single level. However, the attribute classification of tree structure is a common problem in reality. Then， this paper proposes a multi-level formal concept model based on attribute classification， and ana

14、lyzes the related properties of formal concept in different levels of generalization space, and puts forward a method of attribute generalization and refinement based on formal concept analysis, in which attribute generalization simplifies concept and attribute refinement improves accuracy. On the b

15、asis of this, a dynamic formal concept construction algorithm is proposed based on the change of attribute classification level, the algorithm adopts the self-learning method to use the existing knowledge, which not only inherits the advantages of the existing incremental algorithm, but also can dea

16、l with the problem of its own data dynamic changes of the formal concept. Finally, the effectiveness of the proposed method is illustrated by examples and simulation experiments. Keywords: formal concept analysis; granular computing; concept lattice; attribute reduction; attribute generalization m m

17、m . i Abstract . . II . IV 第一章绪论 . 1 U研宄目的和意义 . 1 1.2国内外研宄现状 . 2 1.3论文主要内容 . 3 1.4组织结构 . 4 第二章理论基础 . 6 2.1形式概念分析的理论基础 . 6 2.1.1形式概念分析的数学基础 . 6 2丄 2形式概念分析的基本定义 . 8 2.1.3形式概念的计算方法 . 11 2.2粒计算理论基础 . 13 2.3属性约简 . 16 第三章基于属性分类关系的形式概念属性约简模型 . 24 3.1基于属性分类关系的形式概念分析属性约简模型介绍 . 24 3.2基于属性分类关系的形式概念属性约简算法 . 27

18、3.2.1算法介绍 . 27 3.2.2实例分析 . 28 3.2.3仿真实验 . 30 3.3本章小结 . 32 第四章基于属性分类的多层次的形式概念分析模型 . 34 4.1基于属性分类的多层次的形式概念分析模型介绍 . 34 4丄 1模型介绍 . 34 4.1.2实例分析 . 39 4.2基于属性分类的多层次形式概念动态构造算法 . 40 4.2.1算法介绍 . 40 4.2.2实例分析 . 42 4.2.3仿真实验 . 44 4.3本章小结 . 49 第五章总结与展望 . 50 参考文献 . 52 Pftt . 56 附录 A图索引 . 56 附录 B表索引 . 56 雜 . 57 攻

19、读硕士学位期间发表的学术论文 . 58 第一章绪论 1.1研宄目的和意义 现今，由于信息技术的快速发展，各个领域上都聚集着大量的或海量的数据。 对于这些海量数据中隐含着潜在的价值，如何挖掘出有用的信息，并加以使用， 将是如今人类面临的问题和挑战。 显然，对于海量的数据，若仅是通过人工手段去分析和处理，会耗时耗力； 而且这些数据本身也不具有直观性，往往还需要进行相应的选择、推导才能得到 有用的信息。因此，若能通过某种技术手段去研宄和分析这些海量的数据，自动 实现数据提炼、分类、整理，这将会为社会生产和科学研宄提供便利。目前对海 量的数据研宄和分析中，数据挖掘、机器学习以及知识发现等相关技术己引起

20、人 们的广泛关注，其中形式概念分析方法作为一个重要的研宄对象，它主要研宄属 性和对象之间的关联关系，并用概念一词来表示，通过研宄和分析这些概念，达 到知识发现、知识分析和获取知识的目的。一直以来，形式概念分析都被认为是 数据挖掘中关于数据信息处理最有效的手段。 目前，形式概念分析中还有很多不完善的地方，主要表现为三个方面：一， 现有的形式概念分析中，属性都是单粒度单层次 的，然而现实中树形结构的属性 分类是普遍存在的。针对属性分类具有多粒度多层次的情况，在不同的粒度和不 同的层次下形式概念分析的效果区别很大，若只是从单粒度单层次角度分析，不 利于解决实际问题，如果条件属性的粒度过粗，那么对应属

21、性的外在特征较明显， 反之条件属性粒度过细，对应属性的内在特征较明显，所以属性粒度的选择对形 式概念分析的结果至关重要。二，数据在变化的情况下，尤其是自身数据的改变， 现有的形式概念算法很少有人研究和关注。因为数据在更新时，可以利用之前己 计算的形式概念结果，所以形式概念构造算法应具备 动态适应的能力，并提高形 式概念计算的效率。三，针对于目前形式概念的属性约简算法复杂度偏高、属性 约简过程中存在的冗余计算以及系统存储开销等的问题，所以急需要一个有效的 方法来提高形式概念属性约简的计算效率，并能减少冗余计算和系统存储的开 销。 虽然形式概念一直被认为是一个强大的分析工具，但是面对海量的数据，分

22、 析的效果也会大大降低，此时若能结合粒计算的思想，将复杂问题通过分析、划 分变成若干简单问题，这必然会大大提高分析的效率。 1.2国内外研宄现状 形式概念分析理论 1_6，是德国 Wille教授于 1982年首次提出的一种能够从 形式背景进行数据分析和规则提取的强有力工具。形式概念分析理论是根据概念 的哲学思想所提出的一种数学方法从新的视角对知识发现进行定义，对问 题背景中的对象、属性以及对象属性关系等用形式化的语境表述出来，并根据语 境，构造出格结构，一般称为概念格。通过研宄概念格的结构来达到知识发现、 知识分析和获取知识的目的。形式概念分析广泛应用于软件工程，信息处理，知 识发现，数据挖掘

23、等相关领域 形式概念分析研宄的主要方向有形式概念的属性约简 19_26和形式概念的构 造算法27 两个方面。在形式概念的属性约简中，每个属性都具有不同的作用， 并且对应的特征也是不同的。目前，关于形式概念的属性约简算法大多数是基于 属性的可辨识矩阵或可辨识函数进行研宄的，如 21 132提出了一种新的属性约 简概念可在形式背景中保留所有概念及其层次结构，同时给出了一种基于差别矩 阵的属性约简方法； Wei33 提出了基于粗糙集理论的概念格属性约简，利用概念 格的依赖空间找到最小的属性子集；基于粒计算的思想， wu34j利用信息粒的方 式研宄形式概念的属性约简； Medinatw研宄了面向对象和

24、面向属性的概念格的 属性约简。然而以上这些形式概念属性约简算法时间复杂度都偏高。至此，林国 平 36等人提出概念格的属性约简算法，基于覆盖粗糙集的思想，利用覆盖交约简 的方法实现概念格的属性约简，降低计算时间复杂度。然而该方法在属性约简过 程中存在冗余计算和系统存储开销大的问题。因此，从形式概念的属性约简角度 分析看，有必要在降低计算时间复杂度的情况下，减少冗余计算和系统存储的开 销，从而提高形式概念属性约简的计算效率。对于形式概念的计算，一般是以 概 念格的构造算法方式表示，经过国内外学者多年潜心的研宄 3： M4，已得到了广泛 的应用。其中概念格构造算法主要有两种形式：批处理算法 45,4

25、6和渐进式算法 【 4749。此外，并行算法 5Q等都是计算形式概念的相关算法。然而对于同一个形式 背景，计算出的概念格结构是不变的，它不因数据中的属性和对象的排序方式影 响。其中批处理算法构造概念格的思想是：首先生成所有的概念节点 “ ，然后建立 这些节点的直接前驱和直接后继关系。因构造格结构的方式不同有三种算法形 式 ：一、自顶向下算法，二、自底向上算法，三、枚举算法。其中自顶向下算法 是最典型的，首先构造出最上层节点，然后依次往下构造节点，最后生成概念格 (即各节点之间的关系），例如 Border算法；自底向上算法刚好与自顶向下算法 相反，首先构造出最底层的节点，然后向上扩展构造节点。如

26、 Cheiri算法。枚举 算法是按照一定的规律枚举格中的所有节点，然后再建立这些节点的直接前驱和 直接后继关系生成概念格。如 Ganter算法， Nourine算法等。对于渐进式算法构 造概念格的思想是：首先计算单个属性的对象集合，然后再与己有 的概念集合进 行相交，最后根据相交的结果采取不同的方式选取。关于渐进式构造概念格算法 主要有： Godin算法、 Capineto算法、 TBHo算法。并行构造算法是由于并行计 算机强大的计算和存储能力，而提出了新的方法来处理概念格构造，如 ParallelNextClosure算法。针对以上形式概念构造算法的研宄，属性大多是基于 单粒度和单层次的结构

27、，忽视了在实际应用中树形结构的属性分类是普遍存在 的，属性具有多粒度和多层次的结构。不同粒度层次的属性选择会影响形式概念 分析的精度或效率，所以基于形式背景构造形式 概念时，根据实际问题的求解需 要，将粗粒度属性细化为两个或多个细粒度属性，可以提高问题分析的精度，将 两个或多个细粒度属性泛化为粗粒度属性，可以提高问题分析的效率。因此，属 性分类的多层次多粒度分析和研宄会引起形式背景中的数据发生变化。然而目前 的形式概念的计算方法却不能处理自身数据变化的情况，对于当前信息技术的快 速发展，信息会不断更替，对于形式概念分析的结果，很快就会因为数据的变化， 而需要重新去分析。从问题分析长远的角度看，有必要将属性多粒度多层次模型 与数据动态变化情况考虑到形式概念的计算中，希望可 以借助于粒计算的思想 51对属性粒度进行充分分析，来提高问题分析的精度或计算的效率，以及能够 实现一个动态形式概念计算方法，可以处理更新后的数据信息，提高分析效率。 1.3论文主要内容 本文主要内容由以下几个部分组成： (1) 针对形式概念的属性约简算法，本文通过两个启发式算子来计算出属 性之间的分类关系（等价、包含、独立 )，为了降低算法的时间复杂度、减少冗 余计算以及系统存储的开销，以此提高属性约简算法的计算效率。具体的工作：