（计算机软件与理论专业论文）基于概念层次的概念格更新构造算法研究.pdf

基于概念层次的概念格更新构造算法研究 中文摘要 概念格是一种有效的知识发现与数据挖掘工具，由形式背景生成概念格的过程， 实质上是一种概念聚类过程，反映了概念之间的特化和泛化关系。当形式背景中属 性的概念层次发生变化时，如何高效地更新概念格，提高概念格构造效率具有重要 意义。本文从提高概念格构造效率出发，当属性的概念层次发生变化，对概念格的 高效更新算法进行了研究。主要研究工作如下： ( 1 ) 给出了一种基于概念提升的概念格更新构造算法u c p 。当形式背景中的多 个属性进行合并( 即概念提升或泛化) 时，概念格中的一些概念从低层泛化或提升 到一个较高层，利用概念提升前所构造的概念格，只对内涵中含有合并属性的概念 进行操作，若该概念的内涵与合并属性的交集为空，则不做任何操作；否则，根据 交集的不同生成新增概念或更新概念；然后，合并或删除更新过程中出现的冗余概 念，从而得到新的形式背景对应的概念格；最后，以离散化的恒星光谱数据作为形 式背景和经典的g o d i n 算法做比较，实验验证了u c p 算法的正确性和有效性。 ( 2 ) 给出了一种基于概念特化的概念格更新构造算法u c c s 。该算法主要针对 形式背景中单属性分解为多属性的问题进行研究，概念格中的一些概念从较高层次 特化或例化成较低层次的概念。首先，利用属性分解后的新属性形成的形式背景， 构造其相应的概念格；再将此概念格和原概念格的一个子概念格进行比较，得到更 新概念、新增概念和特化概念，而不是和原概念格比较进行概念格的更新构造，从 而节省了时间，提高了概念格更新构造的效率；最后，以离散化的天体光谱数据作 为形式背景，实验验证了u c c s 算法的正确性和有效性。 ( 3 ) 基于概念层次的概念格更新构造原型系统设计。在w i n d o w sx p 操作系统， 采用v c + + 6 o 和o r a c l e 9 i 开发工具，以离散化的天体光谱数据作为形式背景，设 计并实现了基于概念层次的概念格更新构造原型系统。 关健词：概念格；概念层次；概念提升；概念特化；天体光谱数据 r e s e a r c ho nc o n c e p tl a t t i c eu p d a t i n gc o n s t r u c t i o na l g o r i t h m sb a s e d o nc o n c e p th i e r a r c h y m a jo r ：c o m p u t e rs o f t w a r ea n dt h e o r y g r a d u a t en a m e ：d uq i u x i a n g d i r e c t e db y ：z h a n gj i f up r o f e s s o r z h a n gs u - l a na s s o c i a t ep r o f e s s o r a b s t r a c t c o n c e p tl a t t i c ei s a ne f f e c t i v et o o lf o rk n o w l e d g ed i s c o v e r i n ga n dd a t a m i n i n g t h ep r o c e s s o ff o r m i n gc o n c e p tl a t t i c ef r o mf o r m a lc o n t e x ti s a c t u a l l yac o n c e p tc l u s t e r i n gp r o c e s s c o n c e p tl a t t i c er e f l e c t st h er e l a t i o n s h i p o fg e n e r a l i z a t i o na n ds p e c i a l i z a t i o na m o n gc o n c e p t s h o wt ou p d a t ec o n c e p t l a t t i c e e f f e c t i v e l y a n d i m p r o v e t h ec o n s t r u c t i o n e f f i c i e n c y h a v e g r e a t s i g n i f i c a n c ew h i l et h ec o n c e p th i e r a r c h yo fa t t r i b u t e sc h a n g ei nt h ef o r m a l c o n t e x t a ne f f e c t i v e u p d a t i n ga l g o r i t h mi sp r e s e n t e da c c o r d i n g t ot h e c h a n g e so fa t t r i b u t e sc o n c e p th i e r a r c h yt oi m p r o v et h eu p d a t i n gc o n s t r u c t i o n e f f i c i e n c yo fc o n c e p tl a t t i c e t h em a i nr e s e a r c h e sa r ea sf o l l o w s ： ( 1 ) a nu c pa l g o r i t h mo fc o n c e p tl a t t i c eu p d a t i n gc o n s t r u c t i o nb a s e do n c o n c e p tp r o m o t i n gi sp r o p o s e d w h e nm u l t i - a t t r i b u t ei nt h ef o r m a lc o n t e x t i s c o m b i n i n g ( c o n c e p tp r o m o t i o no rg e n e r a l i z a t i o n ) ，s o m ec o n c e p t si nc o n c e p t l a t t i c ea r ep r o m o t e do rs p e c i a l i z e df r o mal o wl e v e lt oah i g h e ro n e b y m a k i n gu s e o ft h ec o n c e p tl a t t i c ec o n s t r u c t e db e f o r ec o n c e p tp r o m o t i o n ，t h e c o n c e p to n l yc o n t a i n i n gc o m b i n a t i o na t t r i b u t e si nt h ei n t e n ti so p e r a t e d i f t h e i n t e r s e c t i o no fc o n c e p ti n t e n ta n dc o m b i n a t i o na t t r i b u t ei sn u l l ，t h e nd on o t o p e r a t ea n y t h i n g ，e l s e ，n e w l ya d d e dc o n c e p to ru p d a t ec o n c e p ti s b u i l t a c c o r d i n gt ot h ed i f f e r e n ti n t e r s e c t i o n t h e n ，r e d u n d a n c yc o n c e p t sw h i c h a p p e a r i n gd u r i n gu p d a t ep r o c e s sa r ec o m b i n e do rd e l e t e da n dt h ec o n c e p t i l a t t i c eo fn e wf o r m a lc o n t e x ti sg e n e r a t e d f i n a l l y , b yt a k i n gd i s c r e t ec e l e s t i a l s p e c t r u md a t aa st h ef o r m a lc o n t e x ta n dc o m p a r i n gw i t ht h eg o d i na l g o r i t h m ， t h ee x p e m e n tr e s u l t ss h o wt h ec o r r e c t n e s sa n d l e v a l i d i t yo ft h eu c p a l g o r i t h m ( 2 ) a nu c c sa l g o r i t h mo fc o n c e p tl a t t i c eu p d a t i n gc o n s t r u c t i o nb a s e d o nc o n c e p t s p e c i a l i z a t i o n i s p r o p o s e d t h i sa l g o r i t h mm a i n l ya i m sa t p r o b l e m sw h i c hs i n g l ea t t r i b u t ei sd i v i d e di n t om u l t i a t t r i b u t ei nt h ef - o n n a l c o n t e x t ，n a m e l ys o m ec o n c e p t si nt h ec o n c e p tl a t t i c ea r e s p e c i a l i z e do r e x e m p l i f i e df r o mh i g h e rl e v e lo n e st ol o w e rl e v e lo n e s f i r s t l y , b ym a k i n g u s eo fn e wa t t r i b u t e sd i v i d e db ya t t r i b u t e ，c o n c e p tl a t t i c e i sc o n s t r u c t e d c o r r e s p o n d i n g t h e n ，t h ec o n c e p tl a t t i c ei sc o m p a r e dw i t has u b c o n c e p t l a t t i c eo ff o r m e rc o n c e p tl a t t i c e ，a n dt h e u p d a t e dc o n c e p t ，n e w l ya d d e d c o n c 印ta n ds p e c i a l i z a t i o nc o n c e p ta r eg e n e r a t e d b e c a u s eo fn o tc o m p a r i n g w i t ht h ef o r m e r c o n c e p tl a t t i c e ，t h e t i m ei ss a v e da n dt h e u p d a t i n g c o n s t r u c t i o ne f f i c i e n c yo fc o n c e p tl a t t i c ei s i m p r o v e d f i n a l l y , e x p e r i m e n t r e s u l t ss h o wt h ec o r r e c t n e s sa n dt h ev a l i d i t yo ft h eu c c sa l g o r i t h mb y t a k i n gt h ed i s c r e t ec e l e s t i a ls p e c t r u md a t aa st h ef o r m a lc o n t e x t ( 3 ) t h eu p d a t i n gc o n s t r u c t i o np r o t o t y p es y s t e mo ft h ec o n c e p tl a t t i c ei s d e s i g n e db a s e do nc o n c e p tl e v e l s i nt h ew i n d o w sx p o p e r a t i n gs y s t e m ，b v t a k i n g v c + + 6 0a n do r a c l e 9 ia s d e v e l o p m e n tt o o l s u s i n gd i s c r e t e c e l e s t i a ls p e c t r u md a t aa sf o r m a lc o n t e x t ，d e s i g na n dr e a l i z ec o n c e p tl a t t i c e u p d a t i n gc o n s t r u c t i o np r o t o t y p es y s t e mb a s e do nc o n c e p th i e r a r c h y k e y w o r d s ：c o n c e p tl a t t i c e ；c o n c e p th i e r a r c h y ；c o n c e p tp r o m o t i o n ；c o n c e p t s p e c i a l i z a t i o n ；c e l e s t i a ls p e c t r u md a t a i v 承诺书承话吊 本人郑重声明：所呈交的学位论文，是在导师指 导下独立完成的，学位论文的知识产权属于太原科技 大学。如果今后以其他单位名义发表与在读期间学位 论文相关的内容，将承担法律责任。除文中已经注明 引用的文献资料外，本学位论文不包括任何其他个人 或集体已经发表或撰写过的成果。 学位论文作者( 签章) ：才蹄膏 2 0 0 客年y 月, f - a 第一章引言 第一章引言 1 1数据挖掘 1 1 1 数据挖掘的产生 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已经从 单台机器发展到网络环境。近年来由于数据采集技术的不断更新和人们获取数据手 段的多样化，产生了大规模的数据，数据以百万计的数据库系统在运行，而且每天 都在增加。随着数据的急剧增长，现有的管理系统中的数据分析工具已无法适应新 的需求。数据库技术作为一种基本的信息存储和管理方式，仍然以联机事务处理 ( o n l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) 为核心应用，缺少对决策、分析、预测等高 级功能的支持机制。众所周知，随着数据库容量的膨胀，特别是数据仓库( d a t a w a r e h o u s e ) 以及w e b 等新型数据源的日益普及，联机分析( o n l i n e a n a l y t i c p r o c e s s i n g ，o l a p ) 、决策支持( d e c i s i o ns u p p o r t ) 以及分类( c l a s s i f i c a t i o n ) 、聚类 ( c l u s t e r i n g ) 等复杂应用成为必然。面对这一挑战，数据挖掘( d a t am i n i n g ) 和知 识发现( k n o w l e d g ed i s c o v e r y ) 技术应运而生。 归纳数据挖掘产生的技术背景，下面一些相关技术的发展起到了决定性的作用 【l 】： 数据库、数据仓库和i n t e m e t 等信息技术的发展 计算机性能的提高和先进的体系结构的发展。 统计学和人工智能等方法在数据分析中的研究和应用 1 1 2 数据挖掘的定义 数据挖掘( d m ，d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息和 知识的过程【2 1 。而更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中 寻找模式的决策支持过程【3 1 。 所以，数据挖掘的对象可以是结构化的，如关系数据库中的数据；也可以是半 结构化的，如文本、图形和图像数据，甚至是分布在网络上的异构型数据。发现知 识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发 现的知识可以被用于信息管理、查询优化、决策支持和过程控制等，还可以用于数 据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次 的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚 1 基于概念层次的概念格更新构造算法研究 了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术 及并行计算等方面的学者和工程技术人员投身到数据挖掘这一新兴的研究领域，形 成新的技术热点。实际上，所有发现的知识都是相对的，是有特定前提和约束条件， 面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达所发现的 结果。 1 1 3 数据挖掘的方法 数据挖掘中常用的方法主要有：神经网络、决策树、聚类、可视化技术和概念 格等。 神经网络具有学习的能力，它的工作过程可分为两个阶段【4 】：首先要对神经 网络进行训练( 学习期) ，在学习期主要是利用给定的数据或知识来调整网络的各参 数。当学习结束后，神经网络便学到了所要求的知识。然后，利用学习期所学到的 知识，对网络输入作出正确的响应。神经网络的学习方式有3 种：监督学习( 有导 师学习) 、非监督学习( 无导师学习) 和再励学习( 强化学习) 。而常用的神经网络 学习算法有：b p ( 反向传播) 学习算法，遗传算法，最t j , - - 乘学习算法等。 决策树【4 l 学习是以样本为基础的归纳学习方法，主要用于分类和预测。决策 树的表现形式是类似于流程图的树结构，在决策树的内部节点进行属性测试，并根 据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。基于决策树的学 习算法在学习过程中不需要用户了解很多背景知识，只要训练样本能够用属性一值 的方式表述，就可以使用该算法来学习。决策树学习的基本算法是贪心算法，采用 自顶向下的递归方式构造决策树。最早的决策树算法是h u n t 等人于1 9 6 6 年提出的 概念学习系统c l s 。以后又有q u i n l a n 于1 9 7 9 年提出了著名的i d 3 方法。其它决策 树的方法还有i d 3 的增量版本i d 4 和i d 5 等。 聚类【4 】是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过 程。聚类分析输入的是一组未分类记录，并且这些启示应分成几类事先并不知道。 它将待分析数据根据一定的分类规则，合理地划分数据集合，确定每个数据所在类 别。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。聚类分析的 方法很多，其中包括系统聚类算法、分解法、加入法、动态聚类法、模糊聚类法、 运筹方法等。而经典的聚类算法主要有k 平均算法、k 中心方法、凝聚的和分裂的 层次聚类等。 2 第一章引言 可视化技术【5 】是一种图形显示技术。数据挖掘可视化是指寻找和分析数据库， 以找到潜在的有用信息的过程。对数据挖掘过程可视化并进行人机交互可提高数据 挖掘的效果。可视化方法具体有：( 1 ) 提取几何图元，是可视化系统的主要部分， 由不同类型的数据构造成表面或体素模型。它是构造、仿真、分析数据分布模型的 有效手段。( 2 ) 绘制，是利用计算机图形学中的成果，进行图像生成、消隐、光照 效应及绘制的部件。( 3 ) 显示和演放，为了取得显示效果，显示和演放将提供图片 组合、标准文件、着色、旋转、放大和存储等功能。目前，常用的可视化绘制方法 有几何法、彩色法、多媒体法和光学法。 概念格是一种有效的数据挖掘及知识发现的新方法，是形式概念分析中的核 心数据结构，最初于1 9 8 2 年由德国的r w i l l e 教授提出1 6 】。概念格的每个概念由两 部分组成：外延和内涵，外延是概念覆盖的对象的集合，内涵是外延具有的共同属 性。由于概念格自身的完备性，可以进行多种不同知识的挖掘，如对蕴含规则、关 联规则、分类规则等知识的提取，都取得了良好的效果。另外，在数字图书馆、软 件工程和信息检索等领域得到了广泛的应用。近几年来，概念格一直是人们研究的 一个热点领域，这也使得概念格得到了快速的发展。 1 2 概念格国内外研究现状 分析目前掌握的资料，国内外学者对概念格的研究主要表现在以下几个方面： 1 2 1 对概念格构造算法的研究 概念格的构造算法主要分为两大类：批处理算法和渐进式算法【7 - l5 1 。一般认为渐 进式算法是比较有前途的一类算法。 ( 1 ) 批处理算法。这种算法的主要思想是一次生成所有的概念格结点，然后根 据结点间的前驱一后继关系，生成边进而完成概念格的构造。批处理算法只有少数 算法能生成h a s s e 图，根据它生成概念格方式的不同，可以分为三类不同的建格方 式。 自顶向下建格算法，首先构造最上层结点，再逐渐向下，如b o r d a t 算、法【引。 b o r d a t 算法的主要思想是：先生成最上层的概念，再生成它的所有子结点和相应的 边，然后对每个子结点都递归重复该过程，直到生成所有的概念。 自底向上算法是首先构造最底层的结点再逐渐向上扩展的建格算法，如 c h e i n 算法【引。 基于概念层次的概念格更新构造算法研究 枚举算法是按照一定的顺序枚举概念格的所有结点，然后再生成哈希图，即 结点间的关系，典型的算法有g a n t e r 算法【l o 】。 ( 2 ) 渐进式建格算法。渐进式建格算法又分为增加对象和增加属性两类概念格 的渐进式构造。其主要思想是：将当前要插入的对象或属性与格中所有的概念进行 交运算，根据交运算结果的不同可以将结点分成三种情况：不变结点、更新结点和 新增结点，从而采取不同的行动。 增加对象构造概念格。增加对象的经典算法是g o d i n 算、法【l l 】，以及对g o d i n 算法的一些改进，例如：谢志鹏等人提出的一种基于索引树结构的概念格构造算法， 采用树结构对概念格结点进行组织，采用辞典排序树，提出了一种高效的构造概念 格的算法【1 2 】；胡立华等提出一种新的基于剪枝的概念格渐进构造算法，通过去除建 格过程中的冗余结点，提高了算法的效率【1 3 】。 增加属性构造概念格。典型算法有基于属性的概念格渐进式生成算法【l4 1 、 a d d i n t e n t 算法【l5 】等，a d d i n t e n t 算法是一种自底向上的建格算法，只考虑概念的内涵， 不考虑概念的外延，根据要插入概念的内涵寻找标准产生子和更新概念，只考虑标 准产生子之上的概念，这样自底向上更新概念格，概念的外延通过边的更新而更新。 另外，还有一些其它算法的改进，如：利用图的深度优先遍历算法和数据库技 术来生成概念格【l6 】；结合批处理算法便于并行运算的特点和渐进式算法时间性能好 的特点，从而提出的一种新的概念格并行构造方法【1 7 】。 1 2 2 基于概念格的知识发现 概念格是一种有效的数据分析和知识发现工具，它的每个结点本质上是一个最 大项目集，可以从概念格中提取蕴含规则，关联规则，分类规则，聚类知识和异常 知识等。目前，对概念格上提取关联规则的研究比较成熟。而规则提取主要成功的 系统有g o d i n 在渐进式构造的格上提取蕴含规则系统1 引，g a l o i s 聚类系统【1 9 】和 l e g a l 分类系统1 2 0 。规则提取代表性的算法主要有：谢志鹏等人提出的关联规则格 及在其上的关联规则提取算、法【2 1 】；概念格的递增修正关联规则挖掘算法【2 2 】；胡可云 提出的在概念格上将分类与关联规则集成挖掘的算法【2 3 】；梁吉业在2 0 0 4 年提出的在 闭标记格上提取规则产生集的算法【2 4 1 ；刘亚波等人提出的基于两阶段计数的关联规 则提取算法【2 5 】等。 1 2 3 概念格的扩展 4 第一章引言 目前对概念格的扩展主要有：扩展概念格【2 6 1 ，约简概念格1 2 7 】，量化概念格【2 8 】， 加权概念格【2 9 3 0 1 ，约束概念格【3 l 】，压缩的伪代码格【3 2 】等。扩展概念格是在提出等价 内涵的基础上提出的一种概念格的扩展形式，把不同的内涵对应的相同外延放在一 起，并在数据对象增加和删除时如何维护概念格提出了一种新的有效的渐进式构造 算法；约简概念格是在扩展概念格的基础上，消除冗余内涵而产生的一种概念格； 量化概念格是在其内涵中引入等价关系，将其外延量化得到的一种概念格，利用量 化概念格通过计算外延的个数来代替外延，有利于关联规则和分类知识的提取；加 权概念格是根据内涵重要性的不同，给内涵赋予不同的权值，有利于关联规则的提 取；压缩的伪代码格是一种在格中去除一些结点以后剩余的部分仍然能成为用户感 兴趣的概念格。 1 2 4 概念格与其它理论的融合 目前，概念格和其它理论的融合主要有：与模糊集【3 3 3 4 】、粗糙集【3 5 , 3 6 】的融合等， 从概念格的数学性质上研究概念格。从原始的形式背景出发，根据对象的属性具有 模糊性、不确定性等特点，将概念格与模糊集、粗糙集相结合，进行格的构造与知 识提取。如：强宇，刘宗田等人将“模糊”引入概念格，并提出了从模糊概念格上 提取不确定规则、计算规则支持度、置信度的原则和方法【3 4 】；刘宗田提出的基于容 差空间的概念格构造【3 7 1 ，利用粗糙集理论中的近似空间和与概念格之间的对应的关 系，提出了容差近似空间的一种格模型一广义概念格，并描述了该模型建立的方法 及其产生规则的原则。 1 2 5 概念格的更新及概念层次 概念格的更新问题可以分为两大类：横向更新和纵向更新3 8 4 0 1 。横向更新就是指 当形式背景中对象增加或减少的时候，概念格的更新维护问题；纵向更新就是指当 形式背景中属性增加或减少的时候概念格的更新维护问题。概念格的合并问题，也 是一种格的更新方法，比直接在形式背景上构造概念格的效率要高【4 1 , 4 2 】。 概念分层( c o n c e p th i e r a r c h y ) 定义一个映射序列，将低层概念映射到更一般的 高层概斜4 3 1 。概念分层可以由系统用户、领域专家、知识工程师人工地提供，也可 以根据数据分布的统计分析自动地产生。概念分层允许我们在各种抽象级处理数据。 概念层次树作为数据分类的方法，可以将大量详细的细节数据总结上升到较高的概 念层，也可以将较抽象的数据特化成较详细的数据，从而为人们的不同需求提供了 方便。针对概念层次的应用有：一种快速的基于概念提升的多层次关联规则更新采 掘方法与算法】：还有基于遗传算法的概念提升学习方法，在遗传算法和知识发现 基于概念层次的概念格更新构造算法研究 相结合的研究方面做了一些有益的探索1 4 5 】等。 概念格的h a s s e 图形式形象的反映了父子概念间的层次关系，而针对概念层次， 以概念分层为基础，也可以逐层进行概念格的构造，不会生成冗余的概念【矧。在概 念格中，由较低层概念通过概念泛化得到较高层概念，称之为概念提升；反之，由 较高层概念通过概念例化得到较低层概念，称为概念特化。本文从概念层次以及概 念概念特化和概念例化的角度，对基于概念层次的概念格更新构造进行研究，取得 了较好的效果。 1 3 本文的主要研究内容及论文结构的组织与安排 1 3 1 论文的主要研究内容 根据概念格概念间父子关系的泛化与特化关系，本文从概念层次的角度出发， 主要给出了基于概念提升的概念格更新构造算法u c p 和基于概念特化的概念格更新 构造算法u c c s 。当形式背景中的属性进行合并或分解时，概念格中的概念也发生相 应的变化。即当形式背景中多个属性进行合并，新的概念格中出现较之原概念格更 加泛化的概念，概念格中的概念得到提升：当形式背景中某个属性分解为多个新属 性，新概念格中出现较之原概念格更加特化的概念，这两种情况都要构造新的形式 背景对应的概念格。由于概念格的构造效率仍然是概念格应用的瓶颈之一，所以对 原概念格进行更新构造，而不是在新的形式背景上重新构造概念格，从而提高了概 念格的构造效率。最后，都以天体光谱数据作为形式背景，实验验证了u c p 算法和 u c c s 算法的正确性和有效性。 1 3 2 论文的组织结构 论文共分为六章，具体组织如下： 第一章介绍了数据挖掘的相关知识，以及概念格研究的国内外现状及本文的主 要研究内容。 第二章介绍了概念格的基本概念和定义以及概念格构造的常用方法。 第三章主要介绍基于概念提升的概念格更新构造方法及算法，即当形式背景中 若干个属性进行合并，概念格中的概念得到提升时，概念格的更新构造问题。 第四章主要介绍基本概念特化的概念格更新构造方法及算法，即当形式背景中 某个属性分解为多个新属性，概念格中得到更加特化的概念时，如何进行概念格的 更新构造。 第五章介绍基于概念层次的概念格更新构造原型系统，在w i n d o w s x p 操作系统， 6 第一章引言 采用v c + + 6 0 和o r a c l e 9 i 为主要开发工具，以离散化的恒星天体光谱数据作为形式 背景，实现了基于概念层次的概念格更新构造原型系统。 第六章对本文研究内容的总结以及对进一步研究工作的展望。 7 第二章概念格的相关概念及其构造算法 第二章概念格的相关概念及其构造算法 2 1 概念格的基本概念 概念格是由相应的形式背景构造得到的，概念格的每个概念由两部分组成，外 延和内涵。由于概念格自身的完备性，它的外延是具有内涵属性的所有对象的集合， 内涵是外延具有的共同属性集合。下面介绍概念格的基本概念： 定义2 1 一个三元组k - ( g ，m ，i ) ，其中g 为对象，m 为属性，i 为g 和m 之间 的二元偏序关系，这个二元偏序关系构成一个概念格l 。若( g ，m ) i 或g i m 表示 对象g 具有属性m 。 定义2 2 设c ( a ，b ) 为概念格l 的一个概念，则a 称为概念的外延，记为e x t e n t ( c ) ， b 被称为概念的内涵，记为i n t e r n ( c ) 。 定义2 3设c 1 ( a l ，b 1 ) ，c 2 ( a 2 ，b 2 ) 为概念格l 的两个不同概念，若c 1 c 2 a lc a 2 b ecb i ，并且不存在c 3 ( a 3 ，b 3 ) 有c 1 c 3 ( x ，yu u ) ) 对( x ，y ) 的子孙结点也做相同的操作 e n di f 转 e l s e 与6 中i f 对应 将( p ， u ) uv ) 插入l 中，更新父子关系 对( p ， u ) u v ) 的子孙结点，执行过程7 - 8 生成( p ， u u v ) 的子结点放入b u c k e t 将b u c k e t 中的结点与l 中( p ， u ) u v ) 的子结点作比较 胪设b u c k e t 中任一结点为c w h i l ec b u c k e ta n dc 芒l d o 将c 加入l 中，并且c c l ( x lux 2 ，y a ) ， 删除c 2 ，更新父子关系 2 5e n di f 2 6i f c l q 7c 2 ( a 2 ，b 2 ) 更新为( a 2 ，b 2u ( b p ) ) 8 c 1 ( a l ，b 1 ) 更新为( a l ，( b 1 p ) u b 2 ) 9e n di f 1 0e l s ei f a ln a 2 9 产生一特化概念c 1 1生成特化概念c ( a ln a 2 ，( b 1 p ) u b 2 ) 1 2 增加边c l