（计算机软件与理论专业论文）基于概念格的分类规则提取研究.pdf

基于概念格的分类规则提取研究 摘要 随 着数据库的不断增长，自 动从数据库中获取有用的知识成为人们日 益迫 切的需要。 概念格以其知识表示的直观、 简洁和完备特点而受到研究者的关注， 但概念格在结 构构造和规则求解方面存在低效的缺点，本文从数据分类的角度 研究概念格结构的简化问 题，主要讨论有确定类别属性和无确定类别属性的两 类分类问题。 有类别属性的分类的研究的重点 讨论数据噪声的处理、概念格的重构、分 类规则的简化问题，并对其中的有确定类别属性的相关算法进行实现。无确定 类别属性的的 分类问 题讨论了类别属性的确定，以及根据确定的类别属性，在 此基础之上引入支持率， 讨论近似格的 构造和有关近似格上规则求解的问题。 关 键 词 : 概 念 赢 /r“/ 广 识发现，分类规则。 r e s e a r c h o n d i s c o v e r y o f c l a s s i f i c a t i o n r u l e s b a s e d o n c o n c e p t l a t t i c e abs tract d a t a m i n i n g h a s b e e n a n u r g e n t n e e d b e c a u s e o f i n c r e a s i n g s i z e o f c u r r e n t d a t a b a s e s . b e i n g o f e x p l i c i t n e s s , s i m p l e n e s s a n d c o m p l e t e n e s s , c o n c e p t l a t t i c e h a s b e e n t h e o n e f o c u s o f r e s e a r c h e r s o n a i , b u t l o w p e r f o r ma n c e i n c o n s t r u c t i o n a n d r u l e s i n d u c t i o n c o m e a l o n g w i t h t h e s t ru c t u r e . i n t h i s t h e s i s , w e c o n s i d e r i m p r o v i n g t h e p e r f o r m a n c e b y s i m p l i f y i n g t h e s t r u c t u r e f r o m t h e a n g l e o f c l a s s i f i c a t i o n . o u r r e s e a r c h i s a b o u t t h e c l a s s i f i c a t i o n p r o b l e m s o n d a t a w i th a n d w i t h o u t c l a s s l a b e l s a t t r i b u t e . c l a s s i f i c a t i o n w i t h c l a s s l a b e l i s ma i n l y f o c u s o n d e a l i n g w i t h n o i s e , r e c o n s t r u c t i o n o f c o n c e p t l a tt i c e , s i m p l i f i c a t i o n o f c l a s s i f i c a t i o n ru l e s a n d a c l a s s i f i c a t i o n a l g o r i t h m o n c l a s s l a b e l e d d a t a h a s b e e n i m p l e m e n t e d . f o r c l a s s i f i c a t i o n w i t h o u t c l a s s l a b e l , w e d i s c u s s h o w t o f i n d a c l a s s a tt r i b u t e a s a c l a s s l a b e l , a n d o n t h i s b a s i s w e t h e n i n t r o d u c e s u p p o r t es c o e ff i c i e n t t o c o n s t r u c t a p p r o x i m a t e g a l o i s s t r u c t u r e . , a n d e x t r a c t i o n o f c l a s s i f i c a t i o n rul e s h a s a l s o b e e n d i s c u s s e d . k e y wo r d s : c o n c e p t l a tt i c e , k n o w l e d g e d i s c o v e r y , c l a s s i f i c a t i o n r u l e . 独 创 性 声 明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了 文中 特别加以标注和致谢的地方外， 论文中不包含其他人已 经发表或撰写 过 的 研究 成 果， 也不 包 含 为 获得合 肥工 业 大 学或 其 他 教 育机 构 的 学 位 或证 书 而 使 用过的 材料。与 我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明 并表示谢意。 学 位 论 文 作 者 签 名 : 倪瓦。签 字 日 期 ， 年 b a (3 fi 学位论文版权使用授权书 本学位论文作者完全了 解 宣a e i1 k 之 巫 置 兰 有关保留、使用学位论文的规定，有权保留 并向国 家有关部门 或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。 本人授权 宣 ac工a 11 堂- 可以 将学位论文的全部或部分内 容编入有关数据库进行检索，可以 采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学 位 论 文 作 者 签 名 : 农数阅 导师签名: 签 字 日 期 d 3 年6 月 今日 签字 日期:年月日 学位论文作者毕业后去向: 工作单位: 通讯地 址 : 电话: 邮编: 致谢 衷心感谢我的导师胡学钢老师在整个论文阶段给予的悉心指导和帮助.导 师不断从学业上、生活上关心作者。为作者创造了良 好的工作和学习环境;从 查阅文献开始， 言传身教， 使作者在理论研究和工程实践两个方面都得到了良 好的 锻炼， 使我终生受益。 没有导师付出的 辛勤劳动， 本论文是不可能完成的。 三年来， 胡老师严谨的治学态度和谆谆教导给我留下了 深刻的印象， 使作者终 身难忘。 同时，作者深深地感谢 k d d研究室的王浩老师对作者在积累资料和开展 课题方面的启发， 并为作者的 研究工作提出了 许多中肯、珍贵的意见。 我也要感谢欧阳一鸣老师和田卫东老师，在整个课题研究中的指导和帮 助。 另外还要感谢我的同学王德兴、马玉宝、司俊锋、聂成林、姚洪亮和方宝 富给予的无私帮助和支持。 感谢合肥工业大学研究生部及计算机与信息学院的 王新生老师、 徐静老师 和各 位院系领导对我的帮助与支持。 宛敏田 2 0 0 3 年 4月2 9日 第一章概述 伴随着数据库技术、网 络技术以 及许多高新技术的广泛应用，人们在享受 科技成果的同时，必须面对数据库数量激增和信息处理能力有限的现状，从数 据 库中 提 取 知识 ( k n o w le d g e d is c o v e r y in d a ta b a s e s , 简称k d d ) 应 运 而生， 并且成为一个研究和应用的 热点问 题。本章主要介绍 k d d的产生背景，有关 概念，以及 k d d的研究和应用的现状和面临的挑战。 1 . 1 引言 1 . 1 . 1 数据库技术的发展 目 前， 随着社会各领域中 信息的数字化， 电子商务的发展和e r p 技术的应 用， 使数据库技术及网络通讯已 成为重要的基础。数据库技术与网 络的发展既 促进了应用的展开，同时引发了一系列新的问题。 四十多年来，随着计算机应用的普及和数据处理在计算机应用中所占比 重 的上升， 数据库技术得到了 迅速发展，但是随着计算机硬件设计、 生产进步和 互联网的发展，也给数据库技术的研究提出了新的课题。 从2 0 世纪6 0 年代的 数据库技术出现到现在，己 经从大量数据的管理系统 演变成大量数据中信息的 提取和发现的综合信息系统 见图1 . 1 . 数据库是 6 0年代末期作为数据管理的最新技术而出 现的。 最初的数据信 息存 放于文件中，文件仅作为数据的存储方式， 文件管理与数据管理是同 一个 概念，不存在数据管理的概念。数据、文件、信息并没有区别开来。随着数据 数量和内 容的变化以及计算机由单纯的科学计算转变到数据处理， 数据管理的 方式由文件管理形式转变到数据库管理方式，在不到十年的时间内，经过不断 的研究和发展出 现了功能强大的数据库系统。 从 7 0年代开始，数据库和信息技术的研究和发展主要集中 在层次数据库 和网 状数据库系统方面。 主要的工作成果有:数据库系统、数据建模和数据组 织技术;存储技术;检索和事务处理等。 研究和开发主要集中在进一步地深化 数据管理和信息的处理方面。 8 0 年代中期以 来， 由 于数据类型的极大丰富和人们对数据处理的不断提高 的要求，关系数据库被广泛接受，由 此而展开的应用使得数据库管理系统的 发 展进入了新的高潮期。以 关系数据库管理系统为代表的数据库管理系统也逐渐 成熟。 数据收集和数据库创建 ( 2 0 世纪 6 0年代) 一原始文件处理 数据库管理系统 ( 7 0 年代) 一层次，网状，关系数据库系统; 一查询优化，事务处理，联机事务处理: 高级数据库系统 ( 8 0 年 代中期一 现在) 一高级数据模型; 一面向应用; 基于w e b 数据库系统 ( 9 0年代一现在) 一基 于x m l的数据库系统 一 w e b 挖掘 数据仓库和数据挖掘 ( 8 0 年代后期一现在) 一 数据仓库和o l a p 技术 一数据挖掘和知识发 现 新一 代综合信息系统 ( 2 0 0 0 - - - ) 图 1 . 1数据库技术的演化 1 . 1 . 2 网 络技术的发展 i n t e m e t 技术的出 现和发展促使人们对数据库技术提出了 更高的要求。 由 于 数据库技术在不同的应用领域迅速得到应用，造成数据库的格式不一致。 i n t e rn e t 技术的发展可能会造成数据的存储地点不同， 不同的用户需要通过网络 访问 处于不同 地点的不同 格式的数据库，因而需要运用一定方法来处理，数据 仓库 ( d a t a wa r e h o u s e ) 和联机分析处理 ( o l a p ) 随之出 现。 数据仓库是异种 数据统一的组织方式。 而联 机分析处理的数据分析技术对于数据的深层次 分析 存在不足。 面对信息时代的美好前途，一方面是迅速积累的海量数据，另一方面是人 们对数据处理和分析上的捉襟见肘甚 至是困惑，信息的有效利用率和其自 身的 快速膨胀极不相称。 据估计， 世界上的信息量每2 0 个月就要翻一番， 作为信息 的 主要 存 储形 式 之一的 数据 库的 规 模 和 数 量的 增 长 速度 则更 快 1 0 。 从其 中 获 得人们需要的信息是一个亚待解决的 课题，由 于现存的专家系统技术对用户和 专家的知识具有较大的依赖性，同时 分析过程常常 有偏差和错误，因此数据挖 掘 ( d m) 技术适应实际需求应运而生，经过不断的研究和实践，己经在商务 决策、 知识库和医 疗研究领域做出巨大 贡献，成为数据分析的主要工具。 ; 1 . 2 数据挖掘的概念 1 . 2 . 1 基本概念 知识发现 ( k n o w l e d g e d i s c o v e ry i n d a t a b a s e s -k d d ) 是从数据中识别有效 的、新颖的并且可能是有价值的可理解的模式的非凡过程 2 9 ( 也有人认为知 识发现和数据挖掘是同一个概念，本 文采用， 数据 挖掘是知识发现的一个阶段 的观点) 。 数据是实例或者事务、 样本的 集合。例如数据库中一条记录等。 一般地说，数据挖掘的数据类型可以是任何类型的信息。其数据的存在形 式有多种形式， 如可以是保存在本地的 关系数据库、 层次数据库、 网状数据库， 也可以是通过网络连接的异地的 异构数据库， 甚至是早期的展开文件( fl a t f i l e s ) , 还可能是多媒体数 据库、 空间 数据库等. 模式是以 某种语言描述的数据子 集， 或者是可用于该子集合的模型。 因此， 提取一个模式也称为对数据拟合一 个模型或从数据中发现结构， 或更一般地说 是发现数据集合的任意高级描述。 模式的表现形式多种多样，根据挖掘的 任务 的不同，模式的类型有:特征化和区 分:关联模式;分类和预测模式;聚类分 析;演变分析等。其中较常见的表达形式是规则的形式:特征规则的发现;关 联规则的发现;分类规则的发现; 序列模式的发现等，每一种规则都有其相应 的发现的方法。 由于 k d d的目 标是发现隐含在数据中的模式 ( 知识) ， 服务于用户， 提高 效率，因而模式的有效性、新颖性、 有价值和可理解性显得尤其重要。通常使 用兴趣度的 这一个重要的概念来刻画，其中己 经结 合了有效性、新颖性、有用 性和简化等指标。 兴趣程度函 数可由k d d 系统显式地定义或以发现的 模式或模 型的有序排列来隐含地给出。 其相关的 客观度量如支持度和置信度， 每个客观 度量都于一个用户所确定的闭 值相关 联，体现用户 对相关模式的认可程度，以 此来判断是否接受所挖掘的模式。其主观度量主要反映用户的需要和兴趣，因 人而异，因挖掘任务而异。 非凡过程意指某些搜索是复杂的，即不是一个象计算数据的平均值那样的 简单计算问题。同时也指明搜索的过程中不发现显而易见的模式， 而特指发现 隐含的模式。 1 . 2 . 2 k d d过程和任务 术语 “ 过程”意指 k d d包括许多阶段， 包括数据清理与集成、 换、数据挖掘、模式评估与表示、形成知识 见图1 . 2 0 选择 z= 二戈 转 换 曰 预 处 理 酬据 挖 漏评 估 与 表 片=抖之 d 工 二 二 菜 乳 j 匕 七 1 一 : 文二二一、 开二二尸/广/ 展区二| 数据库目 标数据可处理数据模式知识 图1 . 2 数据挖掘的一般过程 k d d过程中的数据清理主要用于消除噪声或不一致数据; 数据集成主要是 多种数据源的组装和集成， 可能需要集成的数据处于不同的位置或不同数据格 式;数据选择从数据库中检索与分析任务相关的数 据; 数据变换的目的是将来 自 各种数据源的数据变换成适合 挖掘的形式:数据挖掘根据不同的任务， 使用 有关方法发现其中的知识， 如各种规则:等价规则，蕴涵规则，关联规则等; 模式评估主要目的在于根据某种兴趣度度量， 识别表示知识的真正有趣的模式， 从整个知识发现的过程看， 模式评估在评价模式的同时 对所发现的 知识进行优 化，力求提交给用户的知识最实用， 最有价值。知识表示阶段使用可视化和知 识 表示技术，向 用户提交挖掘的结果， 为用户的易理解考虑， 这个阶段主要采 用可视化或者是相关的显示化的技术。 数据挖掘任务主要有两类: 预测和描述。 预测和描述之间的分界不明 显( 某 些预测模型可用于描述， 在某种程度上是可理解的) ， 但理解两者的 不同对理解 整个发现目 标是有用的。特定问题的 数据挖掘的 预测和描述是相当重要的。 然 而在 k d d 中 ，描述比预测更为重要。 而在许多模型学习和模式识别问题中， 预测常是主要目标. 1 .2 .3 数据挖掘系统的构成 数据挖掘系统至少经过图1 . 2 中 所述的一般过程，因此必须具备相关的 构 件 ( 见图 1 . 3 ) :数据预处理构件、数据挖掘引擎、 模式评估构件、 知识库构件 1 0 1 。 知识库 数据库数据仓库 图1 . 3典型地数据挖掘系统结构 数据预处理构件:主要是将不同形式的数据经过集成、转换为可以 被数据 挖掘引擎所能识别和使用的数据，为 挖掘准备数据。在这个阶段，除了完成多 种数据的集成外，还要进行数据的 预处理工作，将噪声和异常数据尽力删除， 并把所要进行挖掘的数据表示成一种合适的数据形式， 便于挖掘。 数据挖掘引擎: 接受处理过的 数据， 根据挖掘任务的要求选用合适的挖掘 算法， 从数据中提取有用的模式。 这个阶段的主要任务是完成算法、模式的生 成和对知识库中先验知识的利用。 同时为了 提高效率， 利用先验知识优化算法。 模型估价构件:模式的有效性、新颖性、有价值和可理解性是评价模式的 标准。如前所述， 通常使用兴趣度概念来刻画， 兴趣度在挖掘过程中可以是 用 户和挖掘引 擎的交互接口， 用户通过它控制挖掘集中到有趣的模式上。 有时 直 接将该构件集成在挖掘引擎中， 提高 挖掘的 效率。 知识库构件:知识库是经过专家和用户的检验和认可的模式。可以在新的 挖掘任务中使用和进化。 该系统的核心在于数据挖掘引擎和模式评估模块的设计，用户通过各个模 块的 接口控制或者是约束模块的行 为来达到挖掘的效率和精度要求。 k d d过程是一个数据、 用户和挖掘算法 相互作用的过程， 具有一些智能性 和交互性的特点。数 据挖掘根据不同的 挖掘任务， 最多只需要用户给定相关的 挖掘要求，如规则闭 值等，挖掘引擎就能自己 完成任务，很少再需要用户的干 预。 但是有用户的参与下， 往往利用相关的 先验知识， 提高挖掘的效率和精度。 因此在挖掘的过程中， 用户和专家的 参与程度与系统的智能 性相辅相成。 1 . 2 . 4 数据挖掘的相关研究领域 数据挖掘 ( k d d ) 是一个多 学科交叉的研究领域， 它涉及数据库技术、统计 学、机器学习、高性能计算、模式识别、神经网络等技术的集成，并和专家系 统等领 域紧密相关。 并借鉴了 这些 领域的研究成果， 不断丰富和发展自 己。 首先，k d d是以数据库技术为基础的，从 k d d 产生、发展的过程可以看出， 数据库基础研究的 发展促进了k d d 的发展。 其次， 另一个与 k d d 紧密相关的 领域是数据仓库，数据仓库试图从单个站 点来管理异种数据源的 数据库结构，并提供数据分析和决策支持。 与机器学习、 模式识别在特定数据挖掘理论和算法中的交叉:模拟数据和 提取模式的方法。 k d d集中在发现被认为是有用的或感兴趣的、并且可理解的 模式方面，强调对现实世界中大规模数据集的工作。因此，针对大规模数据集 的 算法的规模化性质是基本要求。 k d d也与统计学有许多共同的内容，特别是分析数据的方法。统计方法采 用精确的 方法定量化不确定性。 k d d软件系统常常在整个知识发现框架中调用 特定的统计过程来抽样、模型化、估价假设、处理噪音。与统计学传统方法相 比，k d d 方法在模型提取操作中一般要调用更多的搜索。 1 . 3 数据挖掘发展 数据挖掘是从数据库中 提取知识， 作为新一代数据库分析工具和技术， 借 助于计算机系统来进行自 动分析，发现其中有价值的知识。从出 现以来的短短 十多年的时间内迅速发展，并己 经取得了 许多 成果 2 9 0 数据库知识发现( k d d ) 在 1 9 8 9 年召开的第 1 1 届国际 人工智能联合学术会 议( i j c a i ) 上首次提出的。 在这届学术会议上举行了 以 k d d为主题的学术研讨 会， 在 1 9 9 1 年、1 9 9 3 年 和 1 9 9 4 年相继举行了k d d专题研讨会。随着k d d 的深入研究以及k d d在许多领域的成功 应用， 于 1 9 9 5 年在加拿大召开了第一 届知识发现和数据挖掘国际学术会议， 此后每年都召开大规模的国际会议。 第 一 本 关 于k d d的 国 际 学 术 杂 志 ( d a t a m i n in g a n d k n o w l e d g e d is c o v e r y 也 于 9 7年 3月创刊发行。 亚太地区 于 1 9 9 7年在新加坡召开了首次 k d d研讨会 ( p a k d d ) ，其后又在澳大利亚的墨尔本召开了 第二届， 在中国北京召开了 第三 届。目 前， 在 i j c a i , a a a i , v l d b , a c m - s i g m o d等代表人工智能与数据 库技术研究最高水平的国际学术会议上，知识发现的 研究都占有较大的比 例， 知识发现的研究己 经成为当今计算机科学与 技术研究、 应用的热点领域之一。 k d d的动力来 自 于其实际应用需求。许多公司也致力于这一领域的 研究、 开发。从大量的数据中找出感兴趣且有用的模式，为决策过程提供支持，是各 个企业和研究者共同关心的课题。 随 着知识发现在国际上的兴起， 我国也积极地开展了研究和应用。目 前， 在国内 许多学术会议如中国人工智能联合学术会议、数据库学术会议、机器学 习学术会议等也都将知识发现列为重要的 研究专题。一些高等院校与科研机构 也开展了知识发现系统的 研究。 我校是国内较早进行知识发现研究的单 位之一， 1 十年代末期以来相继在国家自 然科学基金资助下开展了 “ 从关系数据库中 提 取领域知识的自动化获取研究”，在国家教委博士学科点专项科研基金资助下 开展了 “ 从大规模数据库中自 动提取领域知识的算法与实现研究”，也开展了 国家自 然科学基金项目 “ 基于粗糙集合理论的概念格模型研究”。本文即 是在 上述背景下开展的研究。 数据量的激增和人们处理数据的要求的提高，产生了日益增强的对从数据 库中 提取知识的工具和技术的需要， 并为这一领域的发展提供了坚实的基础和 验证的 条件。 数据库知识发现， 是数据库与人工智能相结合的产物，但从事这一领域研 究和应用的有许多 领域的 科研人员。 有关k d d 研究和发展的 新情况见【 1 1 , 1 8 , 2 7 , 2 8 . 1 . 4 数据挖掘所面临的挑战 经过近十多年的发展， k d d在研究和应用方面取得丰硕的成果， 但依然面 临来自 研究和应用方面的挑战。在 k d d的 研究领域中，随着数据的激增和数 据形式的不断发展，必须解决下列问题: 1数据库的多样性问 题 关系的和复杂的数据类型的处理。由于关系数据库和数据仓库已 经广泛应 用，因而数据库中可能包括复杂的数据对象、 超文本和多媒体数据、 空间数据、 时间数据或事务数据等.由于数据不同，数据挖掘任务不同，实现所有的挖掘 任务的通用方法是不现实的。 而各种挖掘系统都是根据数据类型和挖掘任务来 决定挖掘系统。 2数据挖掘的 性能问 题 数据挖掘由于面向的是大规模数据库，因而算法的运算量较大，因此，改 进算法的时间和空间性能 一直是一个重要问 题。当前较常用的方法有并行的 挖 掘、 分布式的 挖掘和增量挖掘方法以 及利用先验知识来提高 挖掘的效率和精度。 3数据的预处理问题 噪声数据和不完全数据的存在， 使得数据集合呈现过分拟合的状态，在此 之上而进行的 挖掘必然受到影响，使得挖掘的效率 和精度得不到保障，因此必 须在预处理的过程中予以删除。 4先验知识的应用 利用背景知识指导挖掘过程，并使发现的模式以简捷的形式表达。先验知 识的运用可以 提高挖掘的 速度和准确率，同时，先验知识来自 于过去的实际数 据，需要适应现在的数据和进一步地调整。 夸 ， . 5 本文的组织 本文的 其余部分组织为:第二章介绍代数格和概念格的 基本理论， 说明 概 念格的缘起; 第三章介绍分类问题及当 前研究的相关动态; 第四章讨论在数据 库中有确定类别属性的分类问 题; 一 第五章讨论无类别的分类问 题:第 六章分类 规则原型系统的设计: 第七章为结束语， 说明概念格分类问题中待研究的问题。 第二章概念格研究 概念格从wi 1 1 e . r . 提出 经过近2 0 年的发展， 被应用在很多领域。 本章首先 介绍 格 理论 ( l a tt ic e t h e o r y ) 和 概念 格 ( c o n c e p t l a tt ic e ) 的 相 关 概 念; 接 着 介绍 当前出现的几个概念格的模型和相关研究;最后介绍概念格研究中的问题。 2 . 1 概念格的基础 2 . 1 . 1 代数格 格论形成于 1 9 3 5年左右，是代数学的一个重要分支，而且在近世解析几 何、半序空间等方面都有重要作用。 本节从有序集【 5 开始， 介绍代数格的一些 基本概念。 定义2 . 1 设a是一个集合，如果a上的一 个关系 r ，对于b x , y , z e a ， 满 足如下条件: x r x ( 自 反性) x r y , y r x = : x = y ( 反 对称 性) x r y ,y r z = x r z ( 传递性) 则称r是a上的一个偏 序关系， 把它记作 “ ” 。 序偶 a , _ 称为偏序集 定义2 . 2 设 a , 为偏序集且b c a为一个子集，如有a e a ， 且对 b 的任 意元素x ， 都满足 x _ a ， 则称a 为子集b的上界。同理， 且对 b的 任意元素x , 都满足a _ x ，则称a 为子集b的 下界。 定义2 . 3 设 a , 为偏序集且 b c a为一个子集， a 为b上的 任一上界， 若 对于b的 所 有上 界y 均 有a y ， 则 称a 为b的 最小 上 界( 上 确界 su p e r m u m ) , 记作s u p ( b ) 。 同 样 若b 为b 上的 任 一 下界 ， 若 对于b 的 所 有下 界z 均 有z - b , 则称b 为b的最大下界 ( 下确界 i n f i m u m ) ， 记作i n f ( b ) o 定义2 . 4 设 为偏序集， 如果a中 任意两个元素都有最小 上界和最大 下界， 则称 为格。 代数格中以 偏序关系为基础，集合的 元素之间存在上确界和下 确界所构成 的代数结构成为格。 格结构可以 用哈斯图 表示这种具有上下确界的代数结构。 一般来说格理论 2 , 2 0 ，主要指b i r k h o f f a n d d i l w o r t h 提出格论，许多作者 都在研究这个领域，用来处理层次结构系统。格论被集中 研究，出 现了许多成 果。一个原因是格结构提供了丰富的易于明白的 数学框架，用来代表某个特定 问题的内部层次。由于这些原因，过去几年中我们看到了 基于格的 系统被应用 到不同的领域如: 机器学习， 文档提取， 社会科学等。 2 . 1 . 2 概念格 概念格首先由wi 1 1 e .r . 2 1 于1 9 8 2 年提出 用来表达哲学 概念和概念的 层次。 传统观点 认为概念由 其内 涵和外延决定， 其中外延包括所有具有共同内涵特性 的对象，内 涵覆盖所有的 外延的共有特征。 概念格理论非常丰富，这里主要介 绍概念格的 基本概念， 试图反映从偏序集到代数格， 再到概念格的演化过程， 以 下术语和性质采用 2 0 提法， 详细内 容见 2 , 5 , 1 3 , 2 0 , 2 1 , 2 5 0 定义2 . 5 a , b为集合， c是变量，令函数f : b f a ，对于c c a ， 升腾函子 ( 算子) f 定 义为f ( c ) = ( a : a c c : f ( a ) ) 以 下 各 定 义中 ， a ,b 为 集 合， 函 数f i e a f b , f 2 e b f -a . 定义 2 . 6 函数对 ( f 1 , f 2 )称为伽罗华连接当且仅当 b x , y: x e b a y e a: f l ( x 夕即 = x - f 2 ( y ) 当a = b ,f 1 = f 2 时 ， 称 伽 罗 华 连 接 是相 似 的。 定 理2 .1 如 果( f l , f 2 ) 是 伽罗 华 连 接， 偏 序 集a , b 是 完 全 格， 则f 1 ( a ) 和f 2 ( b ) 同 构的 完备格。 上述的定理可应用到 特别的情况， a = ( p ( a ) , c ) 和b = ( p ( b ) , :d ) , a为对 象 集 合， b 为 属 性 集 合， p 为 幂 集，由 于 集合 是 有限 集 ， 所以 函 数 p 定 义 精 确。 我们常见的概念格就是该幂集函数的子集上形成的概念格。 定 义 2 . 7对 于关 系 r = a x b，从 b 定义 函数p ( a)为 : v a e a : a r = b :b e b , a r b 定义2 . 8 对于关系r = a x b ， 从a定义函数p ( b )为: d b e b : r b = a : a e a ,a r b ) . 函 数a r , r b 称为升腾算子。 定 义2 .9 对于 任 意a e p ( a ) 定 义 左极 线 为: a ) r = n a :a e a , a r ) ; 定 义2 .1 0 对 于 任 意b e p ( b ) 定 义 右极 线为 : r b 卜 r -) b :b e b , r b ) ; a的 左 右 极 线 分别 记 作双a ) , r ( a ) ，当a = a ) 时， 分 别 记 作r ( a ) r l( a ) o 定 理2 .2 极线 对 ( r , r ) 是 伽罗 华 连接。 概念格由伽罗华连接产生的。 伽罗华连接的组成成分为:一 对偏序集合和 一对函 数。 在概念格的情况下， 函数为极线， 偏序集为g和m的幂集。 集合g 和m的关系由r( 如r c g x m) 确定。 三元组 ( g , m , r )为上下文， 任意g e g , m e m , ( g , m ) e r当且仅当 对象 9 具有特征m 。 定义2 . 1 1 对于上下文 ( g , m , r ) , f o r a c g , b c m定义下列映像: a = m 二 m i g r m , v g 二 a b = g e g g r m , d m e b 定 理 2 .3 对 于 r c g x m, g e p ( g ) ， 且 m e p ( m ) ， 根 据等 价 g r = ) m =- g c r m ， 则仁 r , r _ 为伽罗华连接。 定 义2 .1 2 概念 是一 个 偏序 对( g ,m ) 且g = r ( m 卜r m ) , m = ( g 冰一 r . g . 定义2 . 1 3 上下文 ( g , m , r )的 概念格记作b ( g , m , r )， 是具有如下序 概 念 的 集 合: ( g i ,ml ) - ( g 2 , m 2 ) = g l c g 2 . 定 义2 .1 4 给定 形 式 概念 ( o 1 ,d l ) 和 ( 0 2 ,d 2 ) ，如 果o l c o 2 ( 等 价于d 2 c d l ) , 则 形 式 概念 (0 1 ,d l ) 是形 式 概 念(0 2 ,d 2 ) 的 子 概 念( 也 称后 继) ， 形 式 概念 ( 0 2 ,d 2 ) 是形式概念( 0 1 , d l ) 的超概念 ( 也称为前驱)，记为 ( 0 1 , d l ) a 和 b - + b 在g和m幂集上形成伽罗华连接。 定义2 . 1 6 对上下文 ( g , m , i ) 中的 概念 ( a 1 , b l )和 ( a 2 , b 2 ) ，超概念和 子概 念 ( a l , b l )( a 2 , b 2 ) t a a l c a 2 ( ab 1 z) b 2 ) e 定理 2 .4 令 ( g ,m ,i ) 为上下 文， 那么一 个完 全格(l ( g ,m ,i ) , 匀被称 为 ( g , m , i )的 概念格， 其上确界和下确界分别定义为: 门 ( a j , b j ) 一 ( 门 a j , ( 门 a j ) j e j j e j j e j u (a j , b j ) = ( ( n b j ), n b , ) j e j j e j j e j 反之， 如果l 是一个完备格，则l 二 l = ( l ( g , m, i ) , _ ) 当且仅当存在映射 y : g -4 l 和p : m -4l ， 且 y g 在l 中 上 紧 致 ( s u p r e m a -d e n s e ) , k m在l 中 下 紧 致 ( in f im u m -d e n s e ) , g im和 y g q e e ， 如果p n f ( x ) 4，则将 其并入更新 规则集 合e ; 当概念 格中的 节点h是更新 节点时， 直接加入( x , f ( x ) ) ( 4 ) 当概念格中 的节点是生 成节点时， 增加节点 n : ( x ( h ) v x , x ( h ) n f ( x ) ) 并增 加边h fn ，同 时连接新 增节点 的本次操作的 双亲和删除h的 非最大花双 亲; ( 5 )重新生成节点h的规则集合 ( 6 ) 对概念格中的所有节点都执行一次( 3 ) , ( 4 ) , ( 5 ) ; 该算法是建立在渐进式概念格构造算法的基础上，因此与构造算法不同的 是更新节点集合的同时更新规则集合， 产生子 h的规则集合是无冗余的规则集 合， 相关内 容见 3 0 1 . 2 . 2 . 2 扩展概念格 由于在定义概念及概念间关系中的限制，使得等价知识不能被有效地表示 出来。 在生成 概念格及构造规则时的 计算量偏大。 为此， h x g提出 对概念格结 构进行扩展， 提出了 扩展概念格【 2 9 以 使其能 在生 成空间和计算量能够接受的 范围内发现概念间的各种规则。 定 义 2 . 1 7 在 上 下 文 ( o ,d ,r ) 中 ， 对给 定的 对 象集 a e p ( o ) = 2 0 与 特征 集 b e p ( d ) = 2 0 ，记 ( 1 )b = g e o i g r m对 所 有m e b ; ( 2 ) a = m e d i g r m对 所 有g c- a ; ( 3 ) 如果存在b , c a 满足b 3 = a , 则称 b 为 a ， 的一 个等价特征组，简 称 为等价组。 特别地，a 是其自身的一个等价特征组。 定义e q u ( a ) = b l 旧 : c_ a 且b , = a o 命题2 .1 上下文 o , d , r ) 中 给定的对象 集a e p ( o ) 满足 a = u b l e e q u (a ) . 证明 : 设a e b , e e q u (a ) ， 则 由 定 义 可 知a e a ， 因 此， b , c a ， 故u b , c a ; 另一方面，对 任一a e a ， 如果 存在b , c a ， 使得a o b , ， 且( a - b ) = a , 则( a - b , ) 是a 的一个包含a 的 等价组，否则， a 是 包含a 的一个最小等 价组。因 此， 任 一a e a 一 定 在 一 个 等 价 组中 。 因 此 a 二 u b , 。 得 证。 定义 2 . 1 8 称从上下文得到的二元组( a ,b ) 为一个基本概念， 其中若一概念 的内 涵不存在等价内 涵， 则 称该 概念为单一概念。 若一概念的内 涵b ， 存在多 个 等价的内涵b 2 , ， 二 ， b k ，则 称这一 概念为多重概念。 将单 一概念和多重概念统称 为 扩展概念，简称 概念， 表示为 ( a , b i ， 二 ， b k ) = 定义 2 . 1 9 上下文中概念间的直接子概念一直接超概念定义为 ( a i,b i) - ( a 2 ,b 2 ) ， 如 果a , c a 2 ， 并 且 不 存 在 概 念 (a ,b ) 使 得a , c a c a 2 成 立 。 上下 文 c = ( o , d , r ) 中 带有这 一关系的 概念格也是 一个完全格， 称为 扩展概 念格 ( e x t e n d e d c o n c e p t l a t t i c e ， 简称e c l ) e 为了能更简捷地表示数据和知识，引入两个概念以便于知识发现和描述。 定义2 .2 0 在 概念c = ( a , b )中， 如果 存在b ; e b 满足l b , l= 1 ， 则称c为 b 、 的 初始概念， b ; 为c的一 个初始特征 ( 或内 涵) 。 如果 对 c的 两个直 接超概 念c i = ( a i,b i) 和c 2 二 (a i,b i) ， 存 在b ;e b 满 足b i= b ij u b 2k ， 则 称c 为c ， 和 c : 的 生成概念 ( 其中b 1j e b 1 , b 2 k e b 2 ) ， 相 应地， 称b ; 为c的 生成特征 ( 或内 涵 ) 。 命题2 . 2 一个概念是生成概念的 充分和必要条 件是存在多个直接 超概念， 一个 概念是纯初始概 念的 充分和必要 条件是只 有一个直 接超概念. 定义 2 . 2 1 设扩展概念格 e c l ( c ) 中概念 c l = ( a l , b i b b 1 2 , . . . , b l n l ) ) 和 c 2 = ( a 2 , ( b 2 1,b 2 2 ,. . . ,b 2 . 2 ) ) ，定义 c l 和 c 2 的积 c i * c 2 为 ( a 1 f l a 2, b ll u b 2 j l 1 = 1 ， 二 ， n l , j = l , . . . , n 2 ) ) . 命题 2 . 3 设扩展概念格 e c l ( c ) 中概念 c l = ( a l , 毛 b i i , b 1 2 , . . . , b l n l ) ) 和 c 2 = ( a 2 , b 2 1 , b 2 2 ， 二， b 2 . 2 ) ) ， 则由c ; 和c 2 共同 确定的概 念为c l * c 2 . 命题 2 . 4 假设初始概念 c l = ( a i , b o ) ) 和 c 2 = ( a 2 , b 2 1 , b 2 2 , . . . , b 2 2 ) ) 是 e c l ( c ) 中 的两个概念， 且ci c 2 ， 则概念c : 的内 涵为 b o , b o u b 2 1 , b o u b 2 2 , ， 二 ， b o u b 2 z ) 证明:由于 b o = a 1 c b 2 ; = a 2 ，因此 ( b o u b 2 1 )=b o f l b 2 ; = a l ,得证。 命题 2 . 5 设 e c l ( c ) 中的 两个概念 c 2 = ( a 2 , ( b 2 1 , b 2 2 , . . . ,b 2 . 2 ) ) 和初始概念 c l = (