（应用数学专业论文）概念格结构及布局优化方法的研究.pdf

河南大学研究生硕士学位论文第l 页 摘要 形式概念分析作为一种用于数据组织和数据分析的形式化工具，在理论研究 和实际应用上都具有重要意义，它己经在多个领域获得了成功的应用。概念格作 为形式概念分析中核心的数据结构，本质上描述了对象和特征之间的联系，表明 了概念之间的泛化与例化关系，其相应的布局图( h a s s e 图) 则实现了对数据的 可视化。 概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法， 概念格的构造和良好的布局是形式概念分析应用的前提。在概念格的构造和布局 过程中，利用现有的方法布局出的概念格图形，在层与层之间产生了过多的边交 叉数，使整个格图看起来杂乱无章，用户很难从中找到有用的信息，直接影响了 概念格图形的可读性。因此，减少格图中的边交叉数，将概念格的可视化表示形 式清晰、美观地展现出来显得尤为重要。 本文在目前已有的概念格构造算法和模型的基础上，结合遗传算法对概念格 图形的布局进行了研究，提出了基于遗传算法的概念格结构布局优化策略，通过 一个概念格分层图模型，介绍了求解边交叉数以及最优边交叉数问题的方法。 本文的主要成果包括： 1 、从概念格分层图的角度提出了“边的跨度 和“规则概念格图形的概念。 并给出了从“非规则概念格图形”到“规则概念格图形”的转换方法。 2 、设计了概念格的矩阵表示，通过此方法可以用二进制字符串表示出编码后 的概念格。 3 、将遗传算法引入概念格分层图布局中边交叉数优化问题的求解，提出了基 于遗传算法的概念格图形布局优化算法。并对实验结果进行了分析，然后和传统 的概念格图形分层布局算法进行了比较。 关键词：概念格，分层图，边交叉数，遗传算法，自动布局 河南大学研究生硕士学位论文第1 li 页 a bs t r a c t f o 咖a lc o n c 印ta n a l y s i s ，r e g a r d i n g 勰a 内r m a 王i z a t i o nt o o lw h i c hi su s e df 0 rd a t a o 曜a m z a t i o na n dd a t ea n a l y s i s ，w l l i c hh a sp r o f o u n ds i g m n c a n c eo nb o t ht h e o 巧r e s e 盯c h a i l dp m c t i c a la p p l i c a t i o n ，a n di th a sr e c e i v e ds u c c e s s 如la p p l i c a t i o ni nm a n yf i e l d s a s 也ec e 砷暇ld a t as t n l c n l r ei nf o n i l a lc o n c e p t 加l a l y s i s ，t h ec o n c e p tl a 钍i c e sd e s c 曲e sm e c o n n e c t i o nb e t 、v e e no 巧e c t sa n d 兜a n l r c si ne s s e n c e ，a n di ti l l l _ s t r a t e st h ec o 衄e c t i o n b e t w e e ng e n e r a l i z a t i o na i l ds p e c i a l i z a t i o no fc o n c e p t s n eh a s s ed i a 铲锄o fac o n c e p t l a 壮i c ei m p l e m e n t s l ev i s u a l i z a t i o no fd a t a t h ev i s u a l i z a t i o nc o n c e p tl a t t i c e sp r o v i d ea i li n t u i t i o n i s tm e t h o df o ra i ：吼l y z i n ga n d o b s e i n gt l l ei n t e m a lr c l a t i o no fk n o w l e d g ec o m p o n e n t s t h ec o n c e p tl a t t i c es 仃u c t u r e a n dg o o dl a y o u ta r et h ep r e c o n d i t i o n so f 也ea l l a l y s i sa n da p p l i c a t i o no ff o m a lc o n c e p t i nt l l ep r o c e s so fc o n c e p tl a t t i c e sc o n s t n 屺t i o na i l d l a y o u t ，i ti sd i m c u l tt ou s et t l e e x i s t i n gm e t h o dt o f i n dm eu s e 如li n f b 朐a t i o n 如ru s e r s ，b e c a u s eo ft h ee x c e s s i v e 删m b e ro fe 始ec r o s s i n gb e 觚e e nl a y e r s 1 1 1 i sk i n do fc o n c e p tl a t t i c e ss t r u c t u r ei st o o c o m p l e x 时t 0r e a da n du n d e r s t a n d t h e r e f o r e ，i no r d e rt om a k et h ev i s u a l i z a t i o no f c o n c e p tl a 钍i c e sc l e a r l y ，an e wv a l i da i l df e a s i b l em e t h o df o rc o n c e p tl a t t i c e sl a y o u tt o r e d u c et h en u m b e ro fe d g ec r o s s i n gi se s p e c i a l l yi nn e e d o nt 1 1 eb a s eo ft h ec u r r e n tc 叽s t m c t i l r ea l g o r i t 胁s 觚dm o d e l so fc o i l c 印tl a l t i c e s ， t h i sp 印e rs t u d i e sc o n c e p tl a t t i c e s 挚印h i c sl a y o u tc o i r l b i n i n gg e n e t i c a l g o r i t h ma 1 1 d p r o p o s e sa0 p t i l l l i 2 a t i o ns 仃a t e g ) ， o fc o n c 印t】甜i c e ss 仃u c t u r eb a s e do ng e n e t i c a l g o r i t h m s t h e nt l l r o u 曲al a y o u tm o d e lo fc o n c e p tl 砒i c e s ，i n t r o d u c i n gh o wt of i n dm e m e t h o d st 0c a l c u l a t et h en m n b e ro f e d g ec r o s s i n ga n dt h eo p t i m i z a t i o nn 啪b c ro fe d g e c o r s s m gb e t 、e e nl a y e r s 协em a i n6 1 l i t so f t h ed i s s e l l l 砸o ni n c l u d e s 1 p u t t i n g 如删st 王l ec o n c 印to f ”r c g u l a rc o n c 印tl a t t i c e s 伊印h i c s ”f 如mt h e 站m d p o i n to f n c e p tl 撕c e sh i e r a r c h i c a lg r a p h i c s g i v i n gt h ec o n v e r s i o nm e t h o df r o m ”i r r e g u l a rc o n c e p tl a n i c e sg r a p l l i c s ”t 0 ”r c g u l a rc o n c e p tl a t t i c e s 聊h i c s ” 2 d e s i g l l i n gc o n o 印tl a t t i c e sm a ：t r i xi n d i c a t i o n ，w h i c hc a l le x p r e s st h ce n c o d e d c o n c 印ti a n i c e st l l r o u 曲t h eb i n a 巧s t r i n g s 第l v 页 塑堕奎兰堡窒生堡主堂垡笙奎 一一 _ - - - _ - _ - _ _ _ _ _ _ _ _ _ _ _ 一一 3i n t r o d u c i n gg e n e t i ca l g o r i 恤nt ot h es e e k i n g s o l v i n go f0 p t i m l z a n o np r o b l e m s f o rm en n b c ro fe d g ec r o s s i n gi i lc o n c e p tl a t t i c e sg r a p h i c sl a y o u t ，雒dp u t s 士f o n 删s 廿硷o p t i m i z a t i o na l g o r i t h mo fc o n c 印tl a t t i c e s 黟印l l i c sl a y o u t i nt e m so tg e n e t l c a l g o m m a n a l y z e dt h ee x p e r i m e n t a l r e s u h st oc o m p a r et 0t h et r a d i t i o n a lg r a p m c a l k e r 2 u r c h i c a la l g o r i t l l i i lo fc o n c e p tl a t t i c e s k e y w o r d s ：c o n c e p tl a t t i c e s ，l a y o u t 伊印h i c s ，n l en u m b e ro fe d g ec r o s s i n g ，g e n c t i c 2 l l g o r i t h m ，a u t o m a t i cl a y o u t 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为荻得任何教育、科研机构酌学位或证书而 使用过的材料。与我一同工作的同事时本研究所做的任何贡献均已在论文中作 _ j， 1 i j ，j。|。 - 、j j ；j jr ? j 0 ：一1l 。一。 ? i i j ， “t!j 本人经河南大学审核批准嫒子领士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目妁- 可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电于文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 2 0o 学位论文指删币弛罩豫： 2 0 胡年莎月和目 河南大学研究生硕士学位论文第1 页 第l 章绪论 形式概念分析反映了概念的哲学理解，并被用于概念的发现、排序和显示。 而概念格作为其核心的数据结构，是根据数据集中对象与属性之间的二元关系提 出的一种概念层次结构，描述了对象和特征之间的联系，表明了概念之间的泛化 和例化关系，概念格是数据分析和规则提取的一种有效工具，相应的h a s s e 图实 现了对数据的可视化。 1 1 国内外研究现状 形式概念分析【1 】理论以数学化的概念和概念层次为基础，是格理论l 4 8 j 的一个 分支，可以作为数据挖掘的一个算法，用于数据分析和知识处理。形式概念分析 的核心数据结构一概念格是提取规则知识l b 6 j 的一个很好的平台，其概念格结点体 现了概念内涵和外延的统一，非常适合于用来发现规则型知识。因此，运用形式 概念分析理论，结合数据库等相关背景，从大量数据中抽取出有用的知识，如概 念等，是切实可行并且是有现实意义的，其主要优点在于可以将数据中( 无论是表 面的还是隐含的) 内在逻辑和组织结构完整地图示化( h a s s e 图) ，从而为分析概念 数据之间的关联提供系统的可视化工具。 概念格的可视化给人们提供了直观的分析与观察知识单元内在关系的方法， 概念格的构造和良好的布局是形式概念分析应用的前提，格图的构造布局算法在 概念格可视化中一直占有比较重要的地位。依据现有的概念格构造算法构造出概 念格之后，将其以图形的形式展现出来称为概念格布局。目前的布局方式主要有 两种：交互式手工布局和计算机自动布局。交互式手工布局允许用户根据具体情 况调整节点的位置，从而达到方便浏览的目的，然而交互式手工布局费时费力， 效率较低；自动布局虽然解决了交互式手工布局存在的效率问题，但是由于它是 根据固定的算法实现的，因此难免会存在格节点布局不灵活、整体结构不美观等 缺陷。 目前，国内外已有很多专家学者从不同的领域研究形式概念分析理论及其在 数据挖掘中的应用，在应用形式概念分析的过程中，首先要从形式上下文中构造 概念格，因此研究概念格生成算法，是实现形式概念分析的首要问题，国内外已 第2 页河南大学研究生硕士学位论文 提出的生成概念格的算法一般分为批处理算法【5 3 ，s 4 ，5 5 ，1 3 ，1 0 ，s 6 ，5 7 】和增量算法 【1 0 ，5 8 ，5 9 ，6 0 ，6 1 1 。批处理算法根据其生成格的不同方法，可以分为自顶向下算法、自 底向上算法、枚举法等。增量算法中比较著名的是g o d i n 的算法，他们采用渐进 式算法来生成概念格，其关键在于找出生成的子结点。 在国内， 3 2 ，7 0 ，2 5 ，3 3 ，2 7 ，2 4 】等文献中也提出了一些关于构建概念格的改 进算法和概念格自动布局的方法。 3 2 ，7 0 】提出的概念格的快速渐进式构造算法是给定特征集一个全排序t ，任 意一个特征子集便唯一的对应全排序特征集的一个有序子集，由这些子集可建立 索引树：首先将索引树初始化为一个根部节点，它对应着内涵为空的概念。然后 可以将概念集合中的每个概念逐个插入到索引树中。接着定义对索引树的遍历： 先访问树根，再依次遍历它的所有子树，遍历的次序由大到小。当访问每个格节 点时，识别出节点的类型并执行相应的操作。 2 7 】对g o d i n 算法在两个方面进行了改进：一是利用图的深度优先遍历算法， 确保不会产生不满足条件的边，减少遍历次数，加快了寻找产生子的速度，从而 提高了g o d j n 算法的效率。二是通过增加格节点的说明信息：内涵集合中的元素 个数和父节点信息，辅助查找新生格节点的子节点。并且，找出了影响g o d 1 算 法效率的因素一对象的输入顺序。最后得出结论：在形式背景中对象的属性分布 均匀的情况下，一个最佳的对象输入序列是按照它们所包含属性的从多到少的顺 序。 在概念格的可视化方面，【2 4 】提出了基于三维空间的概念格自动布局的方法 策略。基于三维布局的概念格图形主要解决二维布局中的横向过度扩张和线段交 叉的问题，由于三维布局减少了二维布局中的节点调整次数，因此生成概念格图 形的速度相对较快。 1 2 本文研究的工作和意义 图形结构的美观准则是一个主观的概念，对于不同的应用，不同的用户，对 于图形画法的美观准则可以是不同的，这就要求画图算法便于修改。再者，即使 对于给定的一组美观准则，要得到满足给定美观准则的最好画法也不是一件容易 的事情。一般而言，判断格图结构是否清晰、美观，概念格分层图中层与层之间 边交叉数的多少是一项重要的判定标准，它直接影响着概念格的可读性和可理解 河南大学研究生硕士学位论文第3 页 性。因此如何既能实现人机交互方便操作，又能有效地减少边的交叉数，已成为 目前概念格图形布局研究中亟待解决的重要问题。在概念格图形布局中，减少边 的交叉数问题是一个n p 完全问题l 7j ，解决此类问题具有很大的现实意义。例如， 在将概念格模型应用到w e b 信息浏览以及结果聚类时，减少边的交叉数能大大提 高浏览清晰度，为用户提供切实有用的信息等。 本文以目前现有的许多从单值形式背景构造概念格的算法为基础，提出了基 于遗传算法的概念格结构布局优化策略，通过一个概念格分层图模型，介绍了求 解边交叉数以及最小化边交叉数问题的方法，该方法的主要思想是：首先依靠随 机搜索的方式确定每一层格节点的位置，然后通过目标函数和遗传运算计算出概 念格分层图的边交叉数最少时格节点的布局序列，然后再根据此布局序列绘制概 念格图形，从而达到在绘制格图时能够尽量减少边交叉数的目的，较好地解决了 概念格图形绘制中边的交叉问题。 1 3 本文的组织结构 本文共分为六章，各章节主要内容如下。 第二章首先对形式概念分析及其概念格模型进行简单的介绍，然后简述了概 念格常用的构造算法，最后，对形式概念分析和概念格等方面的应用进行了简单 介绍。 第三章主要讲述了概念格的可视化形式，概念格分层图布局时的相关概念和 概念格分层图的布局准则。 第四章主要讲述了遗传算法的一些基本概念、基本原理、基本流程及其特点。 第五章主要讲述了在概念格图形布局中边交叉数的计算方法，以及基于遗传 算法的概念格图形布局算法，概念格图形布局时的优化策略和遗传算法收敛性分 析。 最后一章对论文的工作做了综合性的介绍，并提出算法的不足之处和有待于 进一步研究的问题。 第4 页河南大学研究生硕士学位论文 第2 章概念格及其应用 概念格是根据数据集中对象与属性之间的二元关系提出的一种概念层次结 构，是数据分析和规则提取的一种有效工具。本章主要介绍概念格的一些基本概 念、概念格的构造算法和相关的研究内容。 2 1 形式概念分析的理论基础 人类在认识过程中，把所感觉事物的共同特点抽出来，加以概括，就称为概 念。在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学思想，德国的r w 川e 教授于1 9 8 2 年首先提出了形式概念分析p z 。 概念格也称为g a i o i s 格，概念格的每个节点是一个形式概念，在形式概念分析中， 概念的外延被理解为属于这个概念的所有对象的集合，而内涵则被认为是所有这 些对象所共有的特征( 或属性) 集，这实现了对概念的哲学理解的形式化。所有的概 念连同它们之间的泛化例化关系则构成一个概念格。概念格结构模型是形式概念 分析理论中的核心数据结构。它本质上描述了对象和特征之间的联系，表明了概 念之间的泛化与例化关系，其相应的h a s s e 图则实现了对数据的可视化。 这里首先介绍形式概念分析中的一些基本概念，更详尽的描述可参考文献 1 】。 【定义2 1 】一个形式背景( f o r m a ic o n t e t ) k ：= ( ，g ，m r ，) 由集合g 、m 以及它们之间的关系r 组成，尺s o 洲，g 的元素称为对象( o b j e c t s ) ，m 的元 素称为属性( a t t r b u t e s ) 。为了表示一个对象9 和一个属性m 在关系尺中，可 以写成g 尺m 或缸m ) 尺，并且读成“对象9 有属性m 。在不混淆的前提下， 形式背景简称为背景( c o n t e t ) 。 一个小的形式背景可以用一个交叉表( c r o s s t a b i e ) 来表示。在交叉表中一行代表一个对象，一列代 表一个属性，第g 行和第m 列的交叉点有一个“”， 表示对象“夕具有属性m ”。如图2 1 所示。 【定义2 2 】给定背景船= 俺m 刚，对于对象 围2 1 交叉表表示形式背景 子集a 互g ，定义 河南大学研究生硕士学位论文第5 页 彳_ m m i 唯4 球肌 表示“月中全体对象所共有的属性集”。相应地，对于属性子集8 m ，定义 b ：= g g fv 聊b g r 朋 表示“同时具有8 中所有属性的对象的集合”。 【命题2 1 】对子集a ，肖j ，月2 g ，有 1 月j a 2 二涓2 a ， 2 a a 3 a ，- 肖 对称地，对子集8 ，8 j ，8 2 彤，有 1 。8 】8 2 8 2 8 ， 2 。j e l 8 3 b ，一8 ” 注意到，这两个导出算子组成集合g 的幂集和集合m 幂集之间的一个g a i o i s 连接。 【定义2 3 】形式背景跽净侮m 刚上的一个形式概念( 简称概念) 定义为 一个二元组( a ，b ) ，满足： 月g ，8 m ，a ，_ 8 ，8 ，_ 月 其中，a 称为概念( a ，b ) 的外延( e t e n t ) ，b 称为概念( a ，b ) 的内涵( i n t e n t ) 。 一个形式背景可能有许多概念。事实上，形式概念的数目是形式背景大小的 指数。形式背景艇滓f ，6 ，m 彤上的所有概念的集合记为豸f ，g ，m 彤。 【定义2 4 】阴，j e i 夕和心d 夕是形式背景0 ：= ( ，g ，m 刚上的任何两个概念， 称伪，8 ) 是 d 夕的超概念；等价地， d ) 为伪，b ) 的子概念，当且仅 当b d ( 等价地，c 4 ) ，记为 d 夕伪，8 夕即： ( c ，d ) ( 么，召) 营曰d ( c 彳) 通过这种序关系，得到一个有序集墅( g ，m ，尺) = ( 磐( g ，m ，尺) ，) ，称为形式背景 m r ) 的概念格。 概念格中的每个概念都是一个序偶，记为( x ，y ) ，且有性质； 1 ) = x g 、y y ，x i y 第6 页河南大学研究生硕士学位论文 2 ) y = y m x x ，i y 概念格是所有形式概念在子概念和超概念下的序集。因此，概念格可以图形 化表示为其所对应的h a s s e 图。这使得给定数据背景的概念结构变得清晰和易于 理解，从而实现了概念格的可视化。表2 1 给出一个形式背景的例子。其中，行 标为“对象”，列标为“属性”，值为“ 表示该对象具有该属性，值为“” 表示该对象不具有该属性。 表2 1 一个形式背景的例子 属性 i abcde f g hi 1 2 3 对 4 5 x 象 6 7 8 图2 2 是与表2 1 中的形式背景对应的概念格的h a s s e 图表示。通过该图可 以清楚的了解到各个概念之间的关系。其中，概念格中外延最大的概念( 对应于 内涵最小) 为概念格中的最大概念，它位于概念格的最顶部；相应的，概念格中 内涵最大的概念( 对应于外延最小) 则为格中的最小概念，它位于概念格的最底 部。 在h a s s e 图中，直接由一条边相连的两个概念节点之间是“上邻一下邻 ( u p p e r _ n e i g h b o r s & i o w e rn e i g h b o r s ) 的关系。给定一个概念集，要进一步 的生成概念格，其过程就是确定在这个概念集中的所有的“上邻一下邻 关系。 河南大学研究生硕士学位论文第7 页 ( 1 2 3 4 5 b t 吼i ) c 巾i b c “f 画i ) 图2 2 与表格2 1 中形式背景对应的概念格 2 2 概念格的构造 概念格的构造过程实际上是概念聚类的过程，是应用形式概念分析的前提。 通常，概念格的大小是在指数量级上的，而且要处理的数据又多数是海量的，概 念格构造算法的研究始终是形式概念分析中的一个主要问题。概念格的构造算法 可分为两类：批处理算法和增量算法。 1 批处理算法( b a t c ha l g o r i 恤n ) 使用批处理算法构造概念格要完成两项任务：一是要生成所有的格节点，即 所有概念的集合；二是要建立这些格节点间的直接前驱直接后继关系。按照这两 项任务完成次序的不同，我们可以将批处理算法分为任务分割生成模型和任务交 叉生成模型。任务分割生成模型是首先生成全部的概念集合，然后再找出这些概 念之间的直接前驱直接后继关系；任务交叉生成模型是在生成概念的过程中同时 确定概念之间的关系。 已有的任务分割生成模型算法包括：n e x t c l o u r s e 算法【5 3 1 、t j t a n i c 算法【5 4 1 、 c h e i n 算法【5 5 1 、n o u r i n e 算法【1 3 】和a i a o u i 算法【1 0 】等。其中，算法n e t c i o u r s e 算法、t i t a n i c 算法和c h e i n 算法只生成所有概念集合，并未确定概念之间的父子 第8 页河南大学研究生硕士学位论文 关系。而算法a i a o u i 的功能是生成概念间的父子关系。已有的任务交叉生成模型 算法包括：b o r d a t 算法【5 6 】和l - n d i g 算法【5 7j 等。下面简要地介绍一下几个著名 的算法。 n e x t c i o u r s e 算法是最著名的概念格构造算法，它以字典排序的顺序从形式 背景中计算出所有的概念。具体做法是：以位向量来表示特征子集，某位为1 表 示含有该特征，为0 表示不包含该位所对应的特征。位向量从小到大的次序反映 了特征集合上一种字典排序。通过对位向量的枚举来生成所有的内涵集，从而得 到所有的概念。然而n e t c i o u r s e 算法本身并不能直接得到格结构。 t t a n i c 算法利用计算频繁项集的关联规则数据挖掘技术对概念的生成过程 进行优化。和频繁集计算相似，它采用的是一种自顶向下的次序来逐层地生成所 有概念节点。实验结果表明，该算法要明显地优于n e x t c l o u r s e 算法。t i t a n j c 算法也只是计算出所有的概念节点，而没有生成格结构关系。 c h e i n 算法采用自底向上的次序生成所有的节点，即从对象概念开始逐层地 求取两个概念的内涵交集来生成新的概念，并不断地去除已生成的概念。这个算 法在对象数据较多的情况下，在开始阶段会产生大量的重复节点，因此在数据分 析中使用的较少。 n o u r i n e 算法首先生成所有的概念节点，这些概念节点通过一个词典排序树 进行索引，接着通过一个算法计算出所有的节点的父子关系。其中生成所有节点 的时间复杂性为0 ( ( i g i + i m i ) l m i i l l ) ，完成这些节点之间链接的时间复杂 性也是0 ( ( igi + lmi ) i 卜1i ll i ) 。 a i a o u i 算法则是用于计算概念节点之间的父一子关系，从而将概念节点集合 链接成概念格结构的一个简单算法，它的时间复杂度为o ( il iz ) 其中ll i 表示概念 格中节点的数目。 b o r d a t 算法从格的顶端节点开始构造，为每个节点生成的它的所有子节点并 完成子节点到父节点之间的链接。其算法的思想在于：如果当前节点为( g 1 ，m 1 ) ， 找出属性子集m 2 m 一卜1 1 ，使得卜1 2 在g l 中能保持完全二元组的性质，则m 1um 2 构成了当前节点的一个子节点的内涵。这个算法存在的一个问题是，每个二元组 被生成多次( 等于最终格结构中该节点的父节点数目) 。为了避免重复，必须检 查每个节点是否已经生成过。 l i n d i g 算法是一个较为高效的算法。对于第一个过程，它利用了类似于 n e x t c l o u r s e 算法的方法来为概念格中的每个节点生成它的所有子节点：对于第 河南大学研究生硕士学位论文第9 页 二个过程，它则将所有已经生成的概念节点通过一棵词典排序树组织起来，作为 一个索引结构，从而可以快速地判断某个节点是否已经生成。试验结果表明， l n d i g 算法要明显优于n e t c i o u r s e 算法。 2 渐进式构造算法( i n c r e m e n t a la 1 9 0 r i t l 吼) 渐近式构造算法的基本思想是将当前要插入的对象与格中所有的概念求交， 根据交的结果进行不同的操作。典型的算法有：g o d i n 算法l 1 u j 、c a p j n e t o 算法 【5 8 1 、a d d a t o m 算法 5 9 】和a d d i n t e n t 算法【6 0 1 。其中，a d d i n t e n t 算法是 a d d a t o m 算法的改进版本。h o 等【6 l j 也提出了一个增量算法，但和g o d i n 的算 法的思想基本相同。这里简要介绍g o d i n 算法、c a p i n e t o 算法和a d d i n t e n t 算 法。 g o d i n 算法在插入一个新实例时，格中的节点被分为三类：一类是不变节点， 这些节点的内涵和要插入实例的特征集没有交集，它们将在新格中保持不变；第 二类是更新节点，这些节点的内涵包含于要插入实例的特征集，因此只需将其外 延更新，包括要插入实例即可；第三类是新增节点，当所要插入的实例的特征集 与原来格中某个节点的内涵交集在格中没有出现过，这时需要增加新的节点，该 新节点的内涵即为该交集。可以证明，新增节点的父节点必然是某个新增节点或 者更新节点，这使得连接过程很容易实现。g o d i n 还给出了一个改进算法，当一 个新实例插入时，不必对格中所有节点进行检查，只需检查那些和新实例有共同 属性的节点。这是通过维护记录每个属性首次在格中出现的指针来实现的。 c a p n e t o 算法与g o d i n 算法的基本思想类似，它将生成新概念的条件分为： 交为空、交已存在和交包含在已有概念中。主要的不同出现在连接过程中。 c a r p i n e t o 算法是找到该新节点的最小上界和最大下界，删除它们之间的边，并 将其连接到新概念。 a d d i n t e n t 算法不但生成概念集，也生成概念的格结构。算法增量地将下一 个对象合并到前面对象已生成的图结构中。因此，该算法更适合于既需要概念集 又需要格结构的应用。实验结果表明，在某些时候，a d d i n t e n t 算法构造整个格 结构的时间比其它算法单单从概念集构造格结构的时间还要少。 第1 0 页河南大学研究生硕士学位论文 2 3 概念格的应用 作为数据分析和知识处理的形式化工具，形式概念分析已经获得了广泛而成 功的应用。在软件工程领域，形式概念分析为再工程、软件重用、面向对象程序 设计等领域中某些问题的解决提供了理论支持，并已经取得了一系列的应用成果。 在数据挖掘领域，由于形式概念分析以概念格的形式使数据有机地组织起来，概 念格节点体现了概念内涵和外延的统一，因此非常适合于用来发现规则型知识。 除了在软件工程和数据挖掘领域获得的研究成果外，概念格还被成功地应用于信 息检索、知识库组织等诸多领域。 2 4 本章小结 本章主要介绍了形式概念分析、概念格的基本理念概念和目前常用的概念格 构造方法，以及概念格在各个领域中的应用。本章的基础知识为后续章节的内容 作出了铺垫。 河南大学研究生硕士学位论文第11 页 第3 章概念格的可视化形式 在概念格的可视化方面，常见的表达方式有表格和图形两种方式。由于图形 描述可以清晰地表达形式概念及其相互之间的关系，给人带来一目了然的感觉， 因此用图形描述概念格就变得非常重要。w 川e 在1 9 9 3 年发表的论文 4 6 中这样 解释：格是用于进行数据分析的，而不是仅限于一种数学描述，格中蕴含了很多 意义。因此，将格用图形表示出来不仅仅是反映一种数学结构，而是给出了一种 有多种意义的数据表达形式或表示方法。 概念格常用的图形表示形式主要有线图表示法、附加线图表示法、分层图表 示法等几种布局方法。其中分层图表示法不仅保留了其他图形表示方法的优点， 还能够将概念格图形分层布局，提高了概念格图形的可读性，并达到了美观的效 果。 3 1 线图 线图( l n ed i a g r a m ) 是最基本的概念格表示方法。在线图中，每一个节点 表示一个形式概念，然后把符合h a s s e 图性质的关联节点用连线连接起来，从而 使概念之间的结构变得清晰和易于理解。 线图是以h a s s e 图为基础的，在线图中，每一个节点都是一个形式概念，在 这种表示法中，将节点1 画在节点2 的下面表示x 1 x 2 。为了表示图中每一个 节点的含义，可以给节点加上标签，即每一个节点用上下两个标签表示，上面的 标签表示概念的内涵，下面表示概念的外延，如果两个节点存在偏序关系，就用 一条连线将它们连在一起。 连线图使得给定数据背景的概念结构变得清晰和易于理解，为实现概念格的 其它自动布局方式奠定了基础。 3 2 附加线图 附加线图( a d d i t i v e1 n ed i a g r a m ) 是由g a n t e r 和w 川e 引入的【1 1 ， g a n t e r 和w 川e 是这样描述附加线图的：设l 是一个格，r e p 是格l 中的节点 第12 页河南大学研究生硕士学位论文 表达函数( r e p r e s e n t a t i o n ) ，对于格l 引入表达集p ，p 中的每一个元素都是一 个二维向量( 分量和y 分量，记为v e c ( p ) ) ，函数r e p ：l ( p ) 表示对格中的每一 个元素( 属性对象) ，都有p 中的一个向量与之对应，约束条件为： v x i ，艺：五砭r 印( x 2 ) 尸印( x 1 ) 其中l ，2 是概念格中的两个概念。 为了保证h a s s e 图的特征，即如果1 x 2 ，则概念格中节点1 的位置必然 在节点2 的下方，因此规定每个节点坐标的位置在垂直方向( y 坐标方向) 均为 正值。因此规定表达集p 中的每一个元素都用正的y 分量表示，而分量则不作 限制，于是格中每个概念a 的坐标位置可以定义为： p d s ( 口) = 刀+ ：v g c ( p ) p r e p ( 口) 其中n 是一个向量，用于调整坐标系中的偏移量，其值可以根据图的要求任 意选择。 有两种表示附加线图的方法，一种是属性表示法，另一种是属性一对象表示法。 在属性表示法中，直接把属性集作为表达集，即定义表达集为： r e p ( ) = i n t ( ) 其中i n t ( ) 表示概念的内涵。 属性表示法的优点是：如果要找某个概念的内涵属性有哪些，可以分解该位 置的向量，所得到的分向量就是其内涵。缺点是有些概念的纵向位置可能在图中 扩张的太厉害，由于在基于属性表示法的图形中，纵向的分向量都是正值，因此 如果一个具有大量属性的概念的内涵与它的父节点的内涵不同的话( 比如图中最 下面的节点) ，就会导致该节点与其父节点的纵向距离可能比所有节点的平均距离 要大得多。 为了解决这个问题，可以考虑将对象也作为表达集中的成员，对于概念格 旦( g ，m ，i ) 中的概念( a ，b ) ，定义概念( a ，b ) 的表达集是其内涵b 和不包含其外延 a 的格中其它所有对象的并集，即： r e p ( ( a ，b ) ) = bu ( g a ) 其中g a 表示从对象集g 中去掉子集a 所得到的新的对象集。 这样，就可以得到概念格的另一种表示形式，通过这种方法得到附加线图的 河南大学研究生硕士学位论文第13 页 方法称为属性一对象表示法。 用属性一对象表示法表示的附加线图虽然解决了某些节点扩张太厉害而导致 图形在纵向层次上脱节的问题，但是，该方法仅适用于比较简单的特定概念格， 对些复杂的概念格仍然无法得到理想的效果图。 3 3 有向力定位布局 有向力定位布局( f o r c ed i r e c t e dp l a c e m e n t ，f d p ) 是布局图中非常著名 的一种技术【5 1 。它将弹簧原理( 距离越大，拉力越大) 和电磁力原理( 距离越小， 斥力越大) 应用于布局图中，并寻求一种最小的受力配置。 在弹簧沿边作用于顶点的斥力算法中，力的大小均用下式转换为一个变化速 率函数： 薏吨m ，圳 此处f j j 是第i 个顶点的第j 个分向量，然后通过移动顶点或者向量进行优化 处理。 事实上，一个“好 图或者“美观 的图依赖于视觉上的主观判断，并没有 明确的判断标准。然而一个明显的必要条件是尽量避免线段的交叉，在二维图中 这个问题更为突出。 3 。4 分层图 在概念格的分层图中，通过某种方法把节点分为n 个部分，每个部分被划分 为一层，同层节点之间没有边相连接。如图3 - l 所示。 第1 4 页河南大学研究生硕士学位论文 ，) l a y e r l ，)l a y e r 2 ，一 l a y e r 3 ，l a v e r 4 图3 - 1 简单的概念格分层图模型 为了方便概念格分层图的布局及优化，我们特作出以下定义。 【定义3 1 】一个n 层的概念格图形由一个三元组g ：( ，e ”) 构成，其中n 是节点的集合，e 是边的集合，n 是概念格图形的层数。在分层图中有如下性质： ( 1 ) n 是由n 个非空子集组成，= lu 2u um ，并且fnm = 矽，( f ) ， 其中f ( 江l ，2 ，) 是指第f 图层。 ( 2 ) 如果边( p ，g ) e ，则有p j ，留m ，并且f 。 ( 3 ) 对于任意的节点n 和q ，( 七= 1 ，2 ，m ) ，如果见和g ，排列在同一层，则仇所 表示的内涵中的属性个数和g ，所表示的内涵中的属性个数一定相等。 【定义3 2 】一个n 层概念格图形g = e 川，如果边( p ，g ) e ，这里 p n i ，q ni ，a i t ，则以 进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 第2 0 页河南大学研究生硕士学位论文 4 3 遗传算法的特点 图4 1 遗传算法的基木流稗 为解决各种优化计算i u j 题，人们提出了各种各样的优化算法，如肾纯形法、 梯度法、动态舰划法、分枝定界法等。这些优化算法各有各的适，订范围，也各有 各的限制。遗传算法是一类兀j 用于复杂系统优化计算的鲁棒搜索算法，与其他的 一些优化算法相比，它丰要有以下特点【4 j 。 1 遗传算法以决策变量的编码作为运算对象。传统的优化算法i 往直接利用 决策变量的实际值本身来进行优化计算，但遗传算法不足直接以决策变量值，而 是以决策变量的某种形式的编码为运算对象。这种埘决策变量的编码处理方式， 使得我们在优化计算过程中可以计算借鉴生物学中染色体和基因等概念，可以模 仿自然界中生物的遗传和进化等机理，也使得我们几j 以方便的应川遗传操作算子。 特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化刈题，编码 处理办式更显示出了其独特的优越性。 2 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用 目标函数值，而且往往需要目标函数的导数值等其他一些车 i 助信息j 能确定搜索 方向。而遗传算法仪使用由h 标函数值变换来的适应度函数值，就i 叮确定进一步 河南大学研究生硕士学位论文第2 1 页 的搜索范围，无需目标函数的导数值等其他一些辅助信息。这个特点对很多目标 函数是无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合优 化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导数这个障碍。 再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到 适应度较高的部分搜索空问中，从而提高了搜索效率。 3 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空 间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息毕 竟不多，所以搜索效率不高，有时甚至使搜索过程陷于局部最优解而停滞不前。 遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从 一个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等运算，产生 出的乃是新一代的群体，在这之中包括了很多群体信息。这些信息可以避免搜索 一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的 一种隐含并行性。 4 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的 搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这 种确定性往往也有可能使得搜索达不到最优点，因而也限制了算法的应用范围。 而遗传算法属于自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概 率的方式来进行的，从而增加了起搜索过程的灵活性。虽然这种概率特性也会使 群体中产生一些适应度不高的个体，但随