（应用数学专业论文）概念格结构及建格算法的研究.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 概念格是根据 元关系建立起来的一种概念层次结构 是进行数据分析 和炽曼i 提取的有效工具 已经在理论和应用两方面有了广泛的研究 在概念掺 的应用中 首先要根据形式背景建立概念格 所以高效的建格算法是概念格 在应用中实现豹前提 因此 本文农研究概念格的性质的基稿士 对概念格的 建格算法进行了研究 另一方面为了拓广概念格的应用范围 对模糊概念格 也进行了一定的研究 主要点作有以下凡个方面 1 概念格及其h a s s e 圈的一些性质的研究 2 模糊概念格及其建格算法 讨论了模糊对象映射和模糊属性映射的一 些性质 并定义了模糊属性映射鄹模糊对象映射豹隶属函数 在模糊关系豹 截集的基础上 引进相关度a 构造了一种模糊概念格的建格算法 3 概念格的纵向会并算法 从形式背蓉的并置 黧置出发 定义了满性 榘相同的形式背景和概念的纵向合并运算 然后证明了子背景所对应的予概 念格的纵向合并所得的概念格和予背景会并生成的概念格相同 最后 结合 裔序概念格的定义 提出一种多个属性集相同的概念格的合并算法 同时生 成概念格的h 8 s s e 图 并通过实例来说瞬该算法 4 橛念格的分解算法 从概念格分解函数的定义出发 研究了把 个概 念格分解为两个属性集相间的子概念格的方法 证明了如果将概念格按外延 的基的势序排列 分解j 舞得瓣磐延若是第一次崮现 尉生裁予概念格的节点 且内涵等于被分解的节点的内涵 同时讨论了原概念格和分解所得的子概念 格的关系 然后 绘出将一个概念格分解为两个属性集相同的子概念格的方 法 并通过实例说明了该算法 最后说明了概念格的纵向合并运算和分解运 算是互逆 x 嚣南交通大学硕士研究生学僚论文第 贾 第1 章绪论 概念格 l c o n c e p t1 a t t i c e 和形式概念矜柝汹 f o r m a lc o n c e p t a n a l y s i s 是德国的w i l l e 教授在1 9 8 2 年提出的 形式概念分析是研究集对 闽的二元关系弓l 出的屡次结构的一门学科 是在使概念格和概念的艨次结构 清晰数学化的推动下发展起来的格论的一个分支 这种按集的包含关系排序 的集对组成的结构满足完备格的性质 在b i r k h o f f 的著作中首次提到潮 忿 初定义为g a l o i s 格并引起了广泛的研究1 4 l 术语概念格和形式概念分析是由 w i l l e 首先提出的 对形式概念分析的研究确立了撅念掊和其他已知的偏序 结构间的联系 偏序和格的概念簧遗溯到1 9 世纪对逻辑的研究 起源于对概 念的层次即予概念和超概念的研究 对序的这种观点屡来被w i l l e 应用于形 式概念和相应的层次结构 即概念格的研究 作为数据分析和知识处瑗的有力工具 概念格理论已经渗透蠲规簧q 提取 信息检索 知识发现 软件工程等领域 本文主要从概念格的拣震和建格算法 方嚣作进一步的研究工作 1 1 国内外研究现状 i i l l e 教授在1 9 8 2 年发表的有 r e s t r u c t i n gl a 饥i e et h e o r y a n a p p r o a c hb a s e do nh i e r a r c h i e so fc o n o e p t 8 1 j 标志麓概念格理论的建立 f o r l l l a lc o n c e p t 绷a l y s i s 2 3 设概念格理论进一步成熟 其中 寸论了它的 完备性等若干性质 随后 又有学者研究了它的同构性h 近几年 又有入提 出邻域 w 闭包c 6 极大和随机概念格l 等概念 总的来说 关于概念格的建 格算法傲的研究比较多 建格的过程实际上是概念聚类的过程 对同一批数 据 所生成的格也是唯一的 概念格建格算法可以分为两类 批处理算法和增 堂算法 批处理算法的思想怒首先生成所有概念 然后根据它们之间的直接前 驱一后继关系 生成边 完成撼念格的构造 摄摆其构造格瓣不同方式 批处 壤算法又可毅分为3 类 执臻向下篝法 自底丙上算法 枚举算法 扶顶向下 算法首先构造格的最上层节点 荐逐渐向下 耍瓣b o r d a t 算法1 8 j o s h 黼算 西南交通太学硕士研究生学位论文第2 页 法 9 j 良底两上算法蓠先构造底部的节点 再向上扩展 如c h e i n 的算法 1 0 枚举算法剩怒按照一定腰序枚举格的所有节点 然厢褥生成格的 i a s s e 鍪 如g a n t e r 1 1 j n 0 u r i n e 算法n 增量算法是把当前要插入的对蒙和概念格中 所有的概念相交 由交的结果把格中节煮分为不交节点 更新节点和新增节 点 凝据交的结果然后采取不同的方法 如g o d i n 的算法嘲 c a p i n e t o 算法 n t b h o 算法n 渐进式生成算法 8 其中 概念格的维护算法a t 2 b j 主 要涉及到黠象的撬入 测除 修改和隅性靛增加 嬲除 魄瘸予概念格的增 量算法 在概念格发展的基础上 吴刚 胡学钢等人对概念格进彳亍了扩展 逶 过弓l 入等馀内涵定义了扩展概念樯 e x t e n d e dc o n c e p tl a t t i c e s 1 2 并 证明扩展搬念格和其对应豹一般概念壤是弱构的 随后又定义了约箍概念格 r e d u c e dc o n c e p tl a t t i c e s 俐 简化了扩展概念格 使其更利于大规模 数据库知识发现的廒用 针对约繁格巾豹生成内涵霹以从其父概念海潍中获 褥 对约筠概念格进一步篱纯又提出了相对约衡概念格 r e l a t i v er e d u c e d c o n c e p t1 a t t i c e s j 在概念格的内涵中引入等价关系并将其外延赞化 得到了量化概念格 q u a n t i t a t i v ec o n c e p t 矧 利用量化概念格可以曼清 糍靛表示知识 从箍便于挖掘包括关联规翼 j 在内的多种规则 并且用户霹缀 据垂己豹兴趣交曩的挖搦关联规则 不霈要计算频繁项强热 骥丽提高了挖 掘瓶弼的效率 在提崮这些新概念格豹基础上 并对这类概念格髓性质 构造 及其维护徽了一定的研究膨 另外结合z a d e t h 的模糊集理论 f u z z ys e t s t h e o r y f 2 7 j 1 9 6 5 每提出 a b u r u s c o 和r 轴e n t e s 秘j 予1 9 9 4 年提出了乙 一模糊概念格 讨论了它的层次结构 证明全体l 一模糊概念是一个完备格 并对其算法做了一定的研究诤尊l 2 0 0 2 年 陈墩粳和獠里眷又提出了描述概念 内涵和外延模糊关系的模糊概念格印j 建立了橇念的内涵与辨延的模糊映 射 爝摸糊集接述模糊概念思维 并进一步揉讨了模糨属性歌射和模糊对象 映射的隶属酾数的 些基本数学性质 证明全体模糊概念构成一个完备格 西南交通大学硕士研究生学位论文第3 页 楣关熬研究王律对模糊概念刻画 模糨雄理 模糊形式语亩具有麓要的理论 与应用价值 以上都楚针对单个概念格进行的 随着阏络技术尤其是互联网的飞速发 展 数据的分布式存储和并行处理的需求越来越迫切 对多概念格的合并算 法也有了一些研究 其中 李云h 1 j 通过定义概念的横向加运算 提出了 种 多褫念格的横向合并算法 该算法适瘸子对概念格进行分布并行处理 概念格的研究并不仅仅限于理论方砸 谯应用上也有一定的发展 如在 软件工程 信息检索 知识发现 数据挖掘 规则提取 聚类分析d 2 j 等领 域 尤以在规则提取方面的研究较多 如提取关联规则 蕴涵规剜 分类规则 等 在知识发现领域 概念格可以从关系数据中提取各种类型的知识 如关联 规则 蕴涵规则 分类规则等 在软件工程领域 概念格可以从类库以及类 瘁的规范说明上擒造 从面对类痒的可视化以及类席的重构和优化提供支持 在知识工程领域 概念格可以用于知识库的篥新结构化 在信息检索方面 概念格可以实现对信息的有机缀绫并过滤摔茏用的信惠 如和粗糙集理论泌j 相结含对信息系统进行属性约篱l 辨 j 来篱化馆患表 蟊蓠 趣宥入在应用 概念格进行搜索引擎方面的研究 露且 有人指出概念格将会在生物和生命科 学领域有重大应用 1 2 本文的研究思想 德国的w i l l e 提出形式概念分耩 f o r 腑lc o n c e p t8 n a l y s i s f c a 班 来 作为形式概念分析的核心数据结构一一概念格 c o n c e p t1 a t t i c e 引起了 许多学者的广泛关注 并在众多领域得到一定的应用 概念格的构造是形式概念分柝应用的前提 构造算法的效率一直是概念 格的一个核心问题 要解决这个问题 仅研究概念格节点之间的关系是不够 的 蕊概念格的h a s s e 豳生动的体现格中节患阗豹瀑次关系 所 2 卫 可 足通过 研究h a s s e 图的性质来减少算法的复杂度 并且可以通过增加格节点的辅助 信惠 帮对格节点进行羟震来表示更为丰富瓣语义来提蔫算法速度 针对瑗实 世界中出现的大薰模糊性概念 对概念的内涵和外延之闻是模糊关系的概念 格的构造算法的研究也将成为一个亟待解狭的问遥 另步 随着飘联网的飞速 发展 数据分布式存储与并行处理的需求越来越迫切 概念格作为数据分析的 西南交通大学硕士研究生学位论文第4 页 一种工具 这种需求必将涉及到它的合并与分解算法的研究 本文正是基于上 述问题 为了丰富概念格理论并推广概念格的有关工作 对概念格的性质及其 建格算法作了进一步的研究工作 1 3 本文的研究工作 本文从概念格的代数性质出发 对概念格的性质及其构造算法方面进行 了研究 并结合模糊集的知识 提出了一种模糊概念格的建格算法 主要做了 以下几方面的工作 1 概念格及其h a s s e 图的一些性质 2 模糊概念格及其建格算法 讨论了模糊对象映射和模糊属性映射的一 些性质 并定义了模糊属性映射和模糊对象映射的隶属函数 在模糊关系的 截集的基础上 引进相关度a 构造了一种模糊概念格的建格算法 3 概念格的纵向合并算法 从形式背景的并置 叠薏出发 定义了属性 集相同的形式背景和概念的纵向合并运算 然后证明了子背景所对应的子概 念格的纵向合并所得的概念格和子背景合并生成的概念格相同 最后 结合有 序概念格的定义 提出一种多个属性集相同的概念格的合并算法 同时生成 概念格的h a s s e 图 4 概念格的分解算法 从概念格分解函数的定义出发 研究了把一个概 念格分解为两个属性集相同的子概念格的方法 证明了将概念格按外延的基 的升序排列 如果分解所得的外延是第一次出现 则生成子概念格的节点 且内涵等于被分解的节点的内涵 同时讨论了原概念格和分解所得的予概念 格的关系 然后 给出将一个概念格分解为两个属性集相同的子概念格的例 子 最后说明了概念格的纵向合并运算和分解运算是互逆的 本文共有四章 第二章讲述概念格及其性质 第三章为模糊概念格及其 建格算法 第四章研究了概念格的纵向合并算法和分解算法 西南交通大学硕士研究生学位论文第5 页 第2 章概念格 概念格是根据数据集中对象与属性之间的二元关系提出的一种概念层次 结构 是数据分析和规 q 提取的一种有效工具 本章主要介绍一下概念格的基本概念及本文中要用到的知识 然后从概念格的代数 性质出发 讨论了概念格及其h 跚c 圈的一些性质 2 1 基本概念 一个概念由它的外延和内涵确定 外延由属于概念的对象组成 内涵是对 象所共有属性的总和 传统哲学关于概念的定义提供了形式上定义它的依据 例如 表2 1 是一个病例信息系统 表21 病例信息系统 对象是病人甲 乙 丙 丁 属性是关于体温较高 高 正常和是否咳嗽 五个症状性质 第f 个对象具有第j 种属性在表中的位置用 女 表示 这个关 系所确定的概念由序对0 曰 组成 4 外延 是四个病人的子集 丑 内涵 是五种性质的子集 概念由它的外延和内涵确定 亦即口恰好为4 中病人具有 的所有症状性质 4 中病人恰好具有嚣所有的症状 寻找概念的过程可以简 单描述如下 取 个对象 比如乙 令占是乙具有的属性的集合 且 体温一高 咳嗽一否 再令一是具有日中所有属性的所有病人的集 一 乙 丁 则扫 口 是一个概念 我们抽象出前面例子的本质 就可以得到概念格的定义 我们抽象出前面例子的本质 就可以得到概念格的定义 西南交通犬学硕士研究生学位论文第6 页 定义2 1 1 嘲一个形式背景 f o r m a lc n t e x t 是一个三元组 必 d r 其中d 遍对象集 o b j e c t ss e t d 是嘱性集 a t t r i b u t e s s e t 只是d 与d 之间的二元关系 遂常塌脚表示扛 冠 意思为 对象x 具裔属性y 对于4 p d 与丑 p d 可以建妲如下两个殃射 p o 和p d 分别为d 和d 的幂集 p 一p 咎 如 d l 垤 z 砌 g p 一p 0 髫舾 g 口i v 肼笆d 鳓 称 为属性 或内涵 映射 g 为对象 或外延 映射 0 表示子集会a 中 所有对象其有所有共同满性 g 汹 表示予集合居中所有耧性瓴含豹所有共 同对象 刘称每一个满怒 一g 嚣x 嚣一 0 豹二元组c 0 嚣 为一个形式概 念 f o r m a lc o n c e p t 其中爿称为c 的外延 e x t e n t 口称为c 的内涵 i n t e n t 每一对概念攒述了一缎对象及其公共的特征 其中包禽所存对象的 概念穆为全概念 外延为空的概念嚣为空概念 所衮概念构成的集会称为形式 背景蜀一 o d r 对应的概念格 洼2 1 本文用 d d r 袭示形式背景 d d r 对斑的概念格 并蓝本 论文只讨论对黎和属性为有限的情形 定义2 1 2 2 设p d r 是一给定豹形式背索 c l 焉 和 c 一 嚣 是概念格 o d r 豹疆个橇念 在概念格中定义 无关系 c l 釜g 静4 4 尊曩 皿 称c 为c 的父概念 节点 c 为q 的予概念 节点 如果二者之间不存 在另外一个节点c 使c 卜c 卜c 煎4 称c 1 为c 的直接父概念 节点 c 2 为 西南交通大学硕士研究生学位论文 第8 页 7 搿4 o 厂 囊 s 占 苗易 一盆g 岛 4 9 4 一g 4 g 4 马垡琶一 g 嚣1 3 占 岛 定理2 1 2 嘲设p d r 是一形式背景 d d 置 为其对应的概念格 如果 是完备格 则工同构予工 0 d r 当且仅当存在映射y d 一五及 p d 一三 满足y g 在l 中并 稠密 l 的每一个元都是r g 中一些元素的 并 芦 d 在l 中交一稠密 l 的每一个元都是p d 中一些元索的交 且 v 占 d 埘已d 脚z 等价于y k s 肛b 特别的 对任意完备格厶 l 同构 于工惦 厶s 定理2 1 3 f 2 设 d d r 是一个形式背景 o d 赏 为其对应的概念 格 其上确秀耜下确赛由下式给出 善 4 曩 g 譬爿 盆马 垒 4 矗 一 2 4 g 譬誓 由定瑗2 l 3 知道 o d 霞 任意强个元素都有上下确界 所以按照 上面定义2 1 2 定义的偏序关系生成的代数结构是一种格 被定义为概念格 最初的时候 概念格被定义为g a l o i s 格 这是因为由属性映射 和外延 映射g 构成的序对 g 是p o 和p d 之闻的一个g a l o i s 联络 g a l o i s 联 络约定义如下 定义2 1 3 m 1 设p q 是两个偏序集 浃射 妒 p q 与妒 q p 西南交通大学硕士研究生学位论文 第9 页 x 卜 了 y y 明做一个g a l o i 8 联络 如果满足 1 若墨蓝屯 剐0 苫o 溉 屯 p 2 若 墨y 2 则 l 乏y 2 v y l 2 q 3 x 蓝 并 ys v z p q 由定义直接可得 在上述g a l o i s 联络下 有 陋 戡 p y q 由定义2 1 1 定理2 1 1 的前六个性质 可以看出序对 暑 是p p 和 p d 之间的一个g 8 l o i s 联络 这也楚之所以概念疆又称为为g a l o i s 格的原 因 定理2 1 4 汹l 设 0 d r 是一个形式背景 乞 o d r 为其对应的概念 格 在p 0 上的运算 一 g 和p d 上的运算 一占 称为g a l o i s 闭包运 算 对v d l d 慨g d 满足以下性质 1 d 1 q 2 i l g d 1 一譬 d 1 3 q 占 d 1 静d i q 注2 1 2 在不引起混淆的情援下 以盾本文中 培用 表示 g 和g 用 表示 定义2 1 5 时 设 p 墨 是一个偏序集 如果存在尸到熬数集z 的映射 函 数 暑 p z 满足 1 s 4 9 x g y v x y p 一望童塞堂查堂塑士研究生学位论文第1 0 页 一 二二二 二 z 2 z x y 辛g y g x l 戡 y p 则称p 被函数g 所分次 称g 为分次函数 p 口q 做分次偏序集 定理2 1 5 m 设c 6 点蕞s 恐墨 g 露 打是偏序集f 只 内一个有 限链 则 1 c 是界于n 6 间的极大链 而 蕾 o o 1 2 h 一1 2 c 是p 内的极大链静疗是p 的极大冗 6 燕p 的极小元 并且 鼍 2 一 4 6 c 3 一 5 口耐 4 毋 曲以 把两个概念格中节点按内涵基的舞序排歹l j 编号如图中所示 现将五溆 中节 点按上面描述的建格算法依次插入三 过程用下露抟表格表示 见下夏 根据五伍 中有寿概念的潞径联边 帮为级囱台弗嚣掰褥豹概念格的 h a s s e 图 即图2 1 利用有序概念提出概念格的一种纵向合并算法 这样不需骚考虑形成的 节点和更新节点或产生父节点之阆边的变化关系 最后一次生戒所剪的边 龇篓矬意5 c 一 l 和 3 c 1 1 3 4 5 聊w 一 8 1 盎l 和 4 鼢 一 一 一 一 一 1 和 鼠翰 一 一一 一 和 6 c 一 一 一 一 l 羁舯融 一 一 一 l 帮 b c 一 一一 一 冀黧饿 蚋 4 2 释般 跌 2 髓 b 唧 一 一 一 一 2 和 3 c 1 一 一 一 兰篡恼o 暑国瓣 醵鞫 5 枷4 3 4 务c 吲嵩 2 和髑 c 一 2 和 7 似 2 帮 8 嘲 一 一 3 粼l 鼢 一 鹳毫纛毯 i 2 耐 二乙 盈 3 和 4 积 1 2 5 耐j 则 1 3 娟 c j 2 3 4 涵 l j c 3 4 曲c 固 囝 1 1 2 5 辑d 苏二豁当 壁一 一 一 兰 d 一 一 甜 一 一 一 n 一 一 越 一一 辅协 一一 堇釉 二 堡曼窑塑查堂翌圭塑塞宝兰垡笙塞兰 戛 4 2 1 概念格分解的理论基确 设形式背景k 0 d 尺 对应的概念格为 k 若把鬣分解为两个属性 集相同的子形式背景蜀一 0 l d 墨 玛 0 2 d 恐 其中继u 吼一d 0 1n d 一庐 由文献 2 知 五伍 可以遴过一个函数秧射到予概念格五 k 帮 工暖 上 定理4 2 1 2 1 设l 和t 如为属性集相同的概念格 且丘和如为l 的子 概念格 存在 个函数妒 工一厶 三2 妒妇蛳 爿n o l o nd 1 4n 0 2 on 0 2 跏 把搋念格二上的一个概念 b 映射到子概念格上一对概念 该对概念的外延 为似 露 豹赡延与子形式背景对象集的交 魏定理4 2 1 我 给出把一个概念格分解为两个属性集的子概念格的 分解酌数的定义 是义4 2 1 设五k 和五憾 工 为属性集棚冈的概念格 且工k 和 五慨 为工似 的子概念格 对概念格三伍 中的任意概念 嚣 称函数 驴 上取 一 c i 囊 五犯 2 妒 一 嚣 一nd t n q y n 啦 似n0 2 为概念格互伍 的分解函数 定理4 2 2 1 函数舻是单射5 2 涵数 是保序的 证明设任意的 避 嚣 五 墨 则有 西南交通大学硕士研究生学位论文第3 5 页 爿 彳nd 1 u a n o i 4 u 4 丑 爿 1 2 若a 卜艿 即嚣量 根据形式背景的爱嚣 2 4 岿然能和 4 子 节点生成一个内涵大于嚣的节点 若漆涵等予丑 合并成的节点即为c 因 为4 n 4 丑 不妨设为c 代 则 c o 三僻 且c c 所以 矗c 彳 4 no l 4 nd 1 2 4 n q 一 因而 nd l 4 即c o 分解最生成一个步 延为 的节点 与题设矛盾 所以4 丑 同理 若c 的傣意予节点分解嚣的节点外延不等予 即小于 c 2 豹外延 都有i n t e n t c 2 一嚣 推论4 2 1 设概念格中的节点按外延的蒸韵井序排列 将概念格分解 为属性集相同的两个予概念格 如果节点c 是在节点c 8 之蜃进行分解且经过 妒分解后产生的节点c l 的外延已经存在 剥在节点c 的分解过程中不考虑q 这个节点 诚明设节点g 是在节点c 和q 分解的过程中都生成 若概念格工伍 中 的节点按外延的基的升序排列 猁在五伍 中节点c o 为c 的子节点或者g 和 c 有一下确界c 且e x t e n t c e x t e n t c 1 由定理5 1 2 有 i n t e n t c i n t e n t 或者i n t e 航 c 1 i n t e n t c7 所以肇点e 分解过程中生成韵c l 可以不考虑 哥以带来运算的馕便 西南交通大学硕士研究生学位论文第3 6 页 由定理4 2 3 和推论4 2 1 将三k 中节点按外延的基的井序排列 只 需考虑分勰所得子概念格节点的外延 若外延是第一次出现刚生成子概念格 中节点 且内涵等于对应被分解的节点的内涵 若不是第一次出现则不予考 虑 这样就解决了予概念格中节点髂生成翔遂 在概念格的构造过程中还有边的生成问题 我们通过研究原概念格和分 解所季导概念格之闽的关系来解决这个问题 注4 2 1 1 函数留下的像 若第一个节点在对应子概念格中为父节点 第二个节点在对应子概念格中不一定为父节点 如节点 1 2 磁 和节点 1 5 口耐 2 将概念格中节点按外延的基的升序排列后 节点在分解函数妒下的 像对应到分解所得子概念格中 外廷不一定按升序排列 如第二章中形式背 景2 对应的橇念格节点 4 5 6 球d 年珏 1 2 3 4 幻 其中 妒 4 5 6 口c d 妒 4 矗 4 5 毛露c d 驴 1 2 3 4 动 1 2 3 曲 4 口6 c 够 3 原概念格中两节点不具有益接父子关系 但妒下盼像可熊具有直接父 子关系 如节点也痒6 耐 和 1 2 5 积 在伊下豹像对应具有直接父予关系 定理4 2 4 概念格工伍 中最大元与最小元在分解函数妒下的像分嗣对 应子格 奴 和上僻 的最大元和最小元 证锅没概念格 k 的最大元和最小元分剐为 和o 因为 的步 延为所 有对象的集合 o 为所有节点的下界 对应外延最小 由分解竭数豹定义 显然成立 由定理4 2 3 和定理4 2 4 显然有 推论4 2 2 将概念格工伍 分解为两个属性集相同的予概念格 则所得 予概念格 慨 和l 慨 的最小元小内涵相同 都为属性集d 最大元的内 西南交通大学硕士研究生学位论文第3 7 页 涵和 最大元的内涵相同 定理4 2 5 将概念格上k 中节点按外延的基的升序排列 分解为属性 集相同的两个子概念格 则分解所得予概念格中的节点的予节点必然在其父 节点之前出现 证明设概念格工 r 中一任意节点c l 一 韪 妒 c 1 b q 其中 c 三k c 1 三慨 不妨设c l 的任意子节点为c 下面诞明c l 已经 在c l 之前分解所得 若c 是由c l 的予节点分解所褥 显然q i 在c l 之前生成 若c 2 不是由 c 1 的子节点分姆所得 而是由另一节点 设该节点为c 一0 四 分解所 得 由分解函数定义 显然 e x t e n t c 2 4nd l 又因为 e x t e n t c 2 1 ce x t e n t q 1 4 n q 所以 e x t e n t 留2 1 e x t e n t 投1 ne x t e n t c 2 1 n0 1 n 0 nd 1 4 n 以n0 l 因为一眩 c 2 n 以 o t n 鸣y 且为c t 和c 2 的公共予节点 又有 妒 c c 势 n 爿 no l o t n 以n q y 4 n 爿 f 0 2 n 呜nd 2 y 所以c 2 可以由节点 c l c 分解所得 已经在q 之慈生成 由定理4 2 3 和定理4 2 5 如果将概念撩分解为两个属性粲相同的予 概念格 只需将子概念格中一个节点的予节患按出现的先后糇穿编号 就砑 以很清楚着出它们之间的直接父子关系 只要按编号联边 就报容易得到子 概念格的 a s s e 图 西南交通大学硕士研究生学位论文第3 8 页 4 2 2 概念格的分解算法 根据良上定理 本节给出把一个概念格分解为两个属性集相同豹子概念 格的算法 其中忙伍 t 掰 其步骤如下 将概念格三伍 中节点按外延的升序排刿 编号 ft 1 令工 k t 庐 工0 a 矗办r 并 x 力一知 f o l 取出工伍 中一个节点乜 曰 j 令e x t o j q j 一 n q 如果上 中存在一个节点辨延为e x t 协 8 令 一j l 继续该步 否刘令f l 臼 嚣 扭 nd i 嚣 并把该节点存入工憾 将 0 鼠o 存入正 在 中找出 嚣 妊 除本身外所有的予节点 在其予节点的每条 路径之届楼添加上编号e 作为该节点的路径 如果一个子节点 设为c 抟编号已经在另一子节点路径中出现 则该子节点c 的路径不予考虑 对节点 0 丑 r 的路径 只保馨踌径中最后两个编号相同的任意一条路径 如果 jm m 令l f l 转向第 步 否则令 一 1 转向第 步 直到i 2 对 分剐取岛五伍 中元素 按其路径连边 即可自底而上 生成所要的予概念格的h a s s e 图 工阮 中元素为分解历樽子概念格的所有 节点 铡4 2 把形式背景l 对应的概念格 h 8 8 s e 图见强2 1 分解为两个属 性集相同的子概念格工伍 和上取 其中0 l 氟2 田 d 4 首先将 三伍 中节点按外延的基的升序排列 节点在分解函数妒下的像分别如下 其 中划横线的节点为乡 延第一次出现的予概念掺中的节点 妒 n 6 磁 一 受 堡 型j 丝 垒型 j 西南交通大学硕士研究生学位论文第4 4 页 致谢 衷心感谢我的导拜朱振明教授 本文是在导师宋振瞎教授的悉心指导下 完成的 三年来 导师给以我在学习 生活和学术上的关心 帮助和指导 导 师讲授的模糊数学 不确定性推理帮概念捂的知识使我视野开澜 著培养了 我独立从事科学研究的能力 提供的课余实践机会 使我对本科学过的知识 有了科学系统的复习碱固 为以后王圣筝打下了坚实的基础 也使我在研究臭 学习阶段能够自食其力 总之 我的每一点进步都凝聚了导师的辛勤劳动 导 师渊博的知识 严谨的治学态度 茏私髂奉献精神和忘我的工作热情 永远 激融着我拼搏遴取 奋发淘上 在i 毙 谨表对导师崇高豹敬意移诚挚的感谢 衷心感谢我的家人 是他们在生活和学习上给予我关心 照顾 支持和 教育 使我能安心学习 顺利完成学业 他们对我的殷切期塑也将激励着我 不断进步 阕时 翔给予我支持和帮助的老掰和邸冗 师嬉 炳弟 师妹和同学们 致以诚挚的谢意 谣南交通大学硕士研究生学伎论文第4 6 页 a m h e r s t e l s e v i e r 1 9 9 3 3 3 4 0 1 5 t b h o i n c r e m e n t a lc o n c e p t u a lc l u s t e r i n gi nt h ef r a r n e w o r ko f g a l o i s1 a t t i c e i n 乙u m o t o d ah l i uh e d s k d d t e c h n i q u e sa n d a p p l i c a t i o n 8 w o r l ds i e n t i f i c 1 9 9 7 4 9 6 4 1 6 j 谢意搁 刘宗田 概念格的快速渐进式构造算法 计算机学报 2 0 0 2 2 5 5 4 9 0 一4 9 6 1 7 李云 支寸宗酯 陈螋等 基于属性的概念格渐进式生成算法 小型微型计 算机系统 2 0 0 4 2 5 1 0 1 7 6 8 一1 7 7 1 1 8 沈夏炯 韩道翠 刘宗田 概念格构造算法的改进 计算机工程与应用 2 0 0 4 2 4 l o o 1 0 3 1 9 屠莉 陈螳 李云 一种基予属性的概念格生成及维护算法 计算机应用 2 0 0 4 2 4 1 0 h 6 一1 1 8 2 0 张春荚 郭暴峰 刘保相 基予属性链表的概念格纵横向维护算法 计算 机工稷与寂翔 2 0 0 4 5 1 8 争1 8 7 2 1 简宋全 胡学钢 蒋美华 扩展概念格的渐进式构造 计算机工程与应用 2 0 0 l 1 5 i 3 2 一1 3 4 2 2 胡学钢 筒采全等 扩展概念格的渐进式求解 国际 贬太 微机应用学 术会议论文集 2 0 0 0 2 1 2 2 l4 2 3 张意德 简宋全 赵文兵等 相对约筒格及其构造 诗算机王程与应用 2 0 0 2 6 1 9 6 1 9 7 2 3 9 2 4 王德兴 胡学钢 王浩 蒸孳 蠹纯概念格静关联规则挖搦 会月鞋王业大学 学报 2 0 0 2 2 5 5 6 7 8 6 8 2 2 5 赵文兵 篱宋全 王浩等 约简横念格的级向维护算法 计算机工耩与应 用 2 0 0 2 7 2 0 9 2 1 1 2 6 吴剐 篱宋全 胡学钢等 扩展概念格的维护 计算机工程与应用 2 0 0 2 2 7 6 7 8 2 7 z 8 d e t h f u z z ys e t s i n f o r m a t i o na n dc o n t r 0 1 1 9 6 5 2 8 a b u r u s c o r f u e n t e 8 t h es t u d yo ft h el f u z z yc o n c e p 七l a t t i c e m a t h w a r es o f tc o p u t o r 1 9 9 4 1 3 2 0 9 2 1 8 2 9 a b u r u s c o r f u e n t e s c o n s t r u c t i o no ft h el f u z z ye o n c e p t l a t t i c e f u z z ys e t s8 n ds y s t e m s 1 9 9 8 9 7 rusco r fuentes constructionofthel fuzzyeoncept 西南交通大学硕士研究生学位论文第4 7 贾 3 1 李云 刘宗困 陈峻等 多概念格的横向合并算法 电子学擐 2 0 0 4 3 2 1 1 1 8 4 9 一1 8 5 4 3 2 m f a i d r m i s s a o i r g o d i n 赫i n i n gc o m p l e xs t r u c t u r e su s i n g c o n t e x tc o n c a t e n a t i o ni nf o r i i j a lc o n c e p ta n a l y s i s i n t e r n 8 t i o n a l k r u s es y m p o s i u m v a n e o u v e r 王9 9 7 3 3 n p a s q u i e r y b a s t i d e t t a o u i l l l a k h a l e f f i e i e n tm i n i n g o fa s s o c i a t i o nr u l e su s i n gc l o s e di t e ms e t1 a t t i c e 8 i n f o r m a t i o n a n ds y s t e i i s 1 9 9 9 2 4 1 2 5 4 6 3 4 黼 j z a k i c 一t h o s c 8 l a b l ea l g o r i t h m sf o ra s s c c i 8 t i o nm i n i n g 1 e e et r a n s k n o w l e d g ed a t 8e n g 2 0 0 0 1 2 2 3 7 2 3 9 0 c 3 5 m b a r b u t b m o n j a r d e t 0 r d r ee tc 1 8 s s i f i c a t i o n c 1 8 s s i q u e s h a c h e t t e 1 9 7 0 3 6 r g o d i n 1 馘i l i g 驿 m i n e 8 ue t c d e s i g no fc l a 8 sh i e r a r e h i e s b a 8 e do nc o n c e p t g a l o i s l a t t i c e 8 t h