（计算机软件与理论专业论文）基于形式概念分析的用例挖掘方法研究.pdf

摘要 用例对遗留系统的理解、维护、移植和再工程有重要意义。目前， 遗留系统用例挖掘的研究主要是通过检查和分析面向对象系统的代 码来实现。但是许多遗留系统是在面向对象的设计方法出现之前产生 的，并且遗留系统的代码经常无法得到，而那些可以得到的代码也大 多不能分析得到精确的系统功能需求。 本文的研究主要是针对具有丰富用户界面且系统用户交互频繁 的遗留系统，通过检查该系统的使用情况，采用形式概念分析技术， 从应用系统的实际运行行为挖掘系统用例。论文将系统用户交互的 追踪记录作为遗留系统用例挖掘的基本信息来源。由于用户是通过应 用系统完成系统的业务，因而挖掘得到的用例反映了系统的业务功能 需求。 本文在分析国内外用例挖掘方法的现状、形式概念分析及其概念 格构造算法的基础上，提出了一种基于形式概念分析的用例挖掘方 法，论述了基于系统用户交互的概念格构造过程，实现了概念格的 改进构造算法，通过对概念格的水平分解及分析挖掘出系统用例。 论文最后以“研究生工作管理子系统”为实验平台，详细地说明了 从构建概念格、分解概念格到最终挖掘出系统用例的过程，并用相关 数据说明了该方法的可行性。 关键词遗留系统，用例挖掘，形式概念分析，概念格，水平分解 a bs t r a c t u s ec a s ei sv e r yi m p o r t a n tt ou n d e r s t a n d i n g ，m a i n t e n a n c e ，t r a n s p l a n t - a t i o na n d r e e n g i n e e r i n go fl e g a c ys y s t e m a tp r e s e n t ，r e s e a r c ho nm i n i n g u s ec a s e sf o c u so ne x a m i n i n ga n da n a l y z i n gt h ec o d eo f o b j e c t o r i e n t e d s y s t e m h o w e v e r , m a n yl e g a c ys y s t e m sw e r ed e v e l o p e db e f o r et h e a p p e a r i n go fo b j e c t - o r i e n t e dd e s i g nm e t h o d ，t h e i rc o d e sw e r eu s u a l l yh a r d t oo b t a i n ，a n dm o s to ft h o s ec o d e sw h i c hc a nb eg o r e na l s oc a n n o tb e a n a l y z e dt op r e c i s e l yo b t a i nt h en e e d so fb u s i n e s sf u n c t i o n so fs y s t e m t h i st h e s i sf o c u s e so nm i n i n gu s ec a s e sf r o ma p p l i c a t i o ns y s t e m s a c t u a lm o v e m e n tb e h a v i o r , b yc h e c k i n go u tt h eu s eo ft h el e g a c ys y s t e m w h i c hh a sr i c hu s e ri n t e r f a c ea n df r e q u e n ts y s t e m u s e ri n t e r a c t i o n ，u s i n g t h ef o r m a lc o n c e p ta n a l y s i st e c h n i q u e t h et h e s i st r e a t sr e c o r d so ft h e s y s t e m u s e ri n t e r a c t i o na sb a s i cs o u r c e so fi n f o r m a t i o nf o re x t r a c t i n gu s e c a s e so fl e g a c ys y s t e m u s e rc o m p l e t e ss y s t e m ss e r v i c et h r o u g ht h e a p p l i c a t i o ns y s t e m ，s ot h em i n e du s ec a s e sr e f l e c tt h en e e d so fb u s i n e s s f u n c t i o n so fs y s t e m a f t e ri n t r o d u c i n gt h em i n i n gm e t h o do fu s ec a s e sa th o m ea n d a b r o a d w i t ht h ep r e s e n t d e v e l o p m e n t ，f o r m a lc o n c e p ta n a l y s i sa n d a l g o r i t h mo fc o n s t r u c t i n gc o n c e p tl a t t i c e ，t h i st h e s i sp r o p o s e s a m e t h o do f m i n i n gu s e c a s e sb a s e do nf o r m a lc o n c e p ta n a l y s i s ，d i s c u s s e st h e c o n s t r u c t i o no f c o n c e p t l a t t i c e sb a s e do n s y s t e m u s e ri n t e r a c t i o n ， i m p l e m e n t si m p r o v e da l g o r i t h mo fc o n s t r u c t i n gc o n c e p tl a t t i c e ，a n d m i n i n gs y s t e mu s ec a s e st h r o u g hh o r i z o n t a ld e c o m p o s i t i o na n da n a l y s i s o fc o n c e p tl a t t i c e f i n a l l y , t h i st h e s i su s e s p o s t g r a d u a t ew o r km a n a g e m e n ts y s t e m s a s a e x p e r i m e n tp l a t f o r m ，e x p l a i n s t h e p r o c e s s i nd e t a i lf r o mt h e c o n s t r u c t i o na n dd e c o m p o s i t i o no fc o n c e p tl a t t i c et ot h ef i n a le x c a v a t i o n o fas y s t e m su s ec a s e s ，a n du s e sr e l e v a n td a t at op r o v et h ef e a s i b i l i t yo f t h i sm e t h o do fs t u d y k e yw o r d s l e g a c ys y s t e m ，u s ec a s em i n i n g ，f o r m a lc o n c e p ta n a l y s i s ， c o n c e p tl a t t i c e ，h o r i z o n t a ld e c o m p o s i t i o n u 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了论文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究 成果，也不包含为获得中南大学或其他单位的学位或证书而使用 过的材料。与我共同工作的同志对本研究所作的贡献均已在在论 文中作了明确的说明。 作者签名： 逐堑日期：丛年月日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并根据国家或湖南省有关部门规定送交学 位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。 同时授权中国科学技术信息研究所将本学位论文收录到中国学 位论文全文数据库，并通过网络向社会公众提供信息服务。 期：上丛年上月且e l 硕士学位论文第一章绪论 1 1 论文背景 第一章绪论 当软件系统难以修改和演化的时候，就变成了遗留系纠1 1 。但是，包含在遗 留系统中的知识构成了相当重要的企业资源。假设这些系统仍能够提供相当重要 的企业价值，那么就必须对它们进行现代化改造或者替换。由于遗留系统存在技 术陈旧、系统结构混乱、文档缺失和维护成本高等问题，越来越多的企业和组织 采用新技术将遗留系统再工程到新的软件或硬件平台，以提高系统的可靠性、可 重用性、可维护性和运行性能1 2 】。当传统的演化实践( 例如维护) 在不能获取所希 望的系统属性的时候，有人就试图通过软件现代化改造来演化一个遗留系统，或 者系统的组成。 在这个现代化改造过程中，用例【3 , 4 1 作为一个非常重要的工具，在系统开发 及改造过程成起着非常重要的作用。 用例是贯穿整个系统开发的一条主线，用例模型是系统既定功能及系统环境 的模型，它可以作为客户和开发人员之间的契约，一个用例模型即为需求工作流 程的结果，可当作分析设计工作流程以及测试工作流程的输入使用。在使用u m l 的开发过程中，需求是用用例来表达的，界面是在用例的辅助下设计的，很多类 是根据用例来发现的，测试实例是根据用例来生成的，包括整个开发的管理和任 务分配，也是依据用例来组织的。可见，用例对于指导和提高遗留软件系统的改 造效率具有很大的意义。 高效、准确地挖掘遗留系统的用例，对于遗留系统的后续改造过程具有非常 重要的意义。传统的挖掘方法一般都是从系统源代码着手分析，如i p m 、a p r i o r 方法等，这些方法对于庞大而复杂的遗留系统的用例挖掘效率比较低。 形式概念分析f 5 6 】理论以数学化的概念和概念层次为基础，是格理论【6 ，7 】的一 个分支，可以作为数据挖掘的一个算法，用于数据分析和知识处理。形式概念分 析的核心数据结构概念格是提取规则知识门的一个很好的平台，其概念格结 点体现了概念内涵和外延的统一，非常适合于用来发现规则型知识。因此，运用 形式概念分析理论，结合数据库等相关背景，从大量数据中抽取出有用的知识， 如概念等，是切实可行并且是有意义的，其主要优点在于可以将数据中( 无论是 表面的还是隐含的) 内在逻辑和组织结构完整地图示化( h a s s e 图) ，从而为分析概 念数据之间的关联提供系统的可视化工具。 硕士学位论文第一章绪论 自从德国的w i l l e 教授在2 0 世纪8 0 年代初提出了形式概念分析以来，经过近 二十年的发展，概念格【8 9 1 ( c o n c e p tl a t t i c e ) 作为形式概念分析理论中的核心数据 结构，已经在知识工程和软件工程等领域得到了广泛的应用玲o 1 1 1 。 在知识发现领域，概念格可以从关系数据中构造出来，然后从概念格上可以 提取各种类型的知i , u , t 圪l ，如蕴含规则、关联规裂、分类觏则等等。在软件工程 领域，概念格可以从类库的规范说明上构造，从而对类库结构的可视化以及类库 的重构和优化提供支持【婚】。在知识工程领域，概念格霹以用于知识库的重薪结 构化。在信息检索方面，概念格可以实现对信息的有机组织。概念格的构造在其 应用过程中具有重要的意义，研究人员已提出了一系列构造概念格的算法i 悼1 3 1 。 1 2 国内外研究现状 近年来，有很多专家、学者都在从事对遗整系统瘸例及用例模型的恢复工作， 并取得了一定的成效。通过对文献的总结，得出了主要的以下两类主要方法：基 于系统源代码的用铡挖撼方法和基于系统用户界面的用铡挖掘方法。 1 2 1 基于系统源代码的用倒挖掘方法 国内外的许多学者在这方面已经做了比较深入的研究，文献描述主要有利用 线索、分支结构穰面向方面等几种方法，但是由于其较大、较复杂的运算，褥到 的用例比较粗糙。 1 利用线索 d il u c c a 等入在程序源戗筠分析的基础上，定义一个线索：t “一些连接在许 多系统对象之间不断进行信息传递的方法序【1 9 1 , 。直观地说也就是程序巾从任一 个输入l 到任一个输出。之间所有经过的路径。 将程序进行分析，将每一个输入和输如分别用“o i x ”和“o o x ”标注，中间 经过的代码( 函数) 用“( ) i ”标注，这样就可以得到一个序列，这时可以构造一 种瓣q 徽“m e t h o d m e s s a g eg r a p h ”的方法对这些序列进行分析。 按照线索的定义，从而勾画出系统主要的线索图。然后，定义出次线索：“每 一个岔有输入或者输塞或中闽函数黪，且没有交叉的组序捌”。将主要线索表 示的m m 图中通过次线索进行划分。从而得到相互关联的块，这些块构成了用 例的粗糙集。 2 硕士学位论文 第一章绪论 2 利用分支结构 这种方法充分考虑到了函数调用与分支嚣个方面对系统代码的分析，利用一 种u t l b r c g t 2 。l ( b r a n c h r e s e r v i n gc a l lg r a p h ) 的形式化描述方法。在b r c g 描述 方法中，程序的每一段代码都可以是一个函数，一个分支或者一个分支里面的分 支。程序豹代码之闻只有两种关系：顺序关系和分支关系。 ( 1 ) 分析源程序代码得至i j b r c g ： b r c g ( b r , m c h - r e s e r v i n g c a l lg r a p h ) 可以形式化描述成为如下定义的结构： b r c g = 满足以下条件：n 为邈数集合、分支结构或者分支结构里面的分支；s 为顺 序关系集合；b 为分支关系集合。 上述条件中，前3 个条件定义出b r c g 就是表示两种关系的图，而第4 个条件 刘规定一种代码岛其附属代码只能具备一种关系。b 畦 ( 2 ) 锘l j 定每段代码剪辑出的b r c g 的重要性，从而得到更为简练的b r c g ； b r c g 化简依据的是代码的复杂度为基础的重要性原则，即可以剪辑掉低价 值的时节点。 ( 3 ) 通过剪辑出的b r c g 得出用例： 通过遍历最终得到的b r c g ，获得所有可能的执行路径，褥除去重复的路 径从而得到用例。 3 蘑向方面 面向方面编程的改造过程包括两个步骤： ( 1 ) 方面挖掘( a s p e c tm i n i n g ) ：也称关注点挖掘，在源代码中识别关注点的过 程。 ( 2 ) 方面重构( a c p e c tr e f a c t o r i n g ) ：将识别出的关注点封装成方面，从而将源 代码重构为面向方面风格的过程。 正是通过这样一种思想，t o mt o u r w e 等人提出了基于f c a ( f o r m a lc o n c e p t a n a l y s i s ) l 拘l 方面挖掘1 2 1 】的方法，但是，这些方法都侧重于类的方法级的挖掘，挖 掘的结采使用于较高层次麓重构，丽不能直接解决语句级的代码纠缠窝代码分散 的问题。 从蒸进一步懿有作者提出一种基予f c a 的语句级自动讫方面挖掘方法 f a a m 方法【2 2 】。这种方法的思想是：将源代码中的语句按照变量关系进行分类， 从而形成方面的候选者，为后续的方面重构提供输入。 在f a a m 方法中，首先使用j a v a c c l 2 3 1 分析源代码，生成擒象语法树，再使 用访问者设计模式遍历抽蒙语法树，生成变量注释语法树，得到形式概念分析所 需的上下文，然后使用形式概念分析的认h l c 嚣算法1 1 4 l 生成概念格，接着傻尾概 3 硕士学位论文第一章绪论 念格水平分解算法，将生成的概念格分解成若干独立的只和最上、最下元素相连 的子概念格，最后计算每一个子概念格对应的总概念，作为一个关注点的候选者， 显示最后的结果以供后续处理来使用。 以上分析介绍了基于系统源代码的用例挖掘方法，这些方法挖掘的结果均是 以语句为单位，可以直接显示出语句级的代码纠缠和代码分散情况。 1 2 2 基于系统用户界面的用例挖掘方法 这种方法主要是在l e n d l ( l e g a c yn a v i g a t i o nd o m a i ni d e n t i f i e r ) 方法【2 4 2 5 】的 研究基础之上，通过引入一种交互模式挖掘( i p m ) 算法f 2 6 1 ，这种算法以一个交互 追踪序列集和一个定义的标准为输入，抽取得到遗留系统的用例。 该方法的主要思想是：用户任务是在遗留界面行为追踪中频繁出现的模式， 用户在执行这些任务的时候可能在任务片段中间出现一些额外的状态。i p m 算法 是基于a p r i o r i 算法发展而来的，它使用从短的模式发展为长的模式的策略。但是 i p m 算法通过采用一种位置列表避免了对输入的频繁查询。同时，它采用了一种 矩形数据结构来最大限度地限制合成模式的数量。 i p m 算法的输入是一个序列集s 和一个标准c ，输出s 中所有有质量的模式。 这个算法包含如下两个不同的阶段。 阶段1 产生初始候选模式集； 在这个阶段要不断地查找输入序列来确定所有的长度为2 的候选模式，这种 候选模式要满足“最小支持度”和“最大错误数”。对于每一个这样的模式构建一个 位置列表，这个模式列表p t l i s t 是一个i a i l a i 矩形。每个矩形列表中元素p t l i s t i j 】 包含每个模式p 。 阶段2 从短的模式产生长的模式。 在这个阶段将延长候选模式集。对于两个长度为l 的模式p l 和p 2 ，如果 s u f f i x ( p 2 ) = p r e f i x ( p 1 ) ，则可以得到长度为l + l 的模式p 3 ，其q h p 3 = p 2 + p l 【l 】，然后p 3 储存至l j p t l i s t p 1 1 ，p l 【l 】。但是，p l 仅仅能够延伸储存在p t l i s t p l 【1 】，p l 1 l 】 中的模式。 4 硕士学位论文 第一章绪论 1 3 研究的目的及意义 随蔫软件规模和复杂度的增加，理解和维护遗留系统的难度也不断增加。用 例是贯穿整个系统开发的一条主线，用例模型是系统既定功能及系统环境的模 型，它可以俸为客户和开发入员之间的契约，一个用铡模型郾为需求工作流程戆 结果，可当作分析设计工作流程以及测试工作流程的输入使用。在使用u m l 的 开发过程中，需求是用用例来表达的，界面是在用例的辅助下设计的，很多类是 根据用例来发现的，测试实例是根据用例来生成的，包括整个开发的管理和任务 分配，也是依据用例来组织的。因此，对用例及用例模型的分析是系统至关重要 的一个环节，如何高效、准确地抽取遗警系统的震例，对于指导耩提高遗留软件 系统的改造效率具有很大的意义。 蓦嚣，通过对遗蜜系统的分析从而提取出系统魇例的方法在园内外都有耀关 人员取得了一定的进展与成就，主要采用直接扫描和分析源程序代码或者通过交 互界面，再利用相关描述方法挖掘系统用例。但是，直接扫描代码工作量太大， 尤其是对一些大型软件的改造来说受是耗时耗力，效率也不高。阉时，有些遗留 系统的部分代码难以获取，或者是含有相当一部分的垃圾代码，这也给直接分析 源代码来提取用铡带来了很大的影响，很难壤确提取用铡甚至可髓是错误的焉 例。有些通过界面获取的挖掘模式集也不是频繁集合，有的算法仅适合部分带有 大量成熟稳定的系统，丽对于批处理系统或者有非常少界面的系统来说，就不能 很好的挖掘出系统用倒。 基予以上考虑，由于对用户界面而言，相对于代码较为直观凰清晰。若是通 过对系统用户交互的角度凌发，构造塞用户使用系统的行魏模型，即焉户轨迹 图( g r a p ho f u s e ri n t e r f a c e ，简称g u i ) ，再采用形式概念分析的方法，对所得的 g u i 进行关联挖撼，通过构造其关联的概念格进行模型的化筒，将具有相似或相 同属性特征的概念格进行l 罔并，最终通过所有格之间的联系派生国系统用例。 本文提出了基于形式概念分析( f o r m a lc o n c e p ta n a l y s i s , 简称f c a ) 的系统的 用侧挖掘方法的研究课题，最后透过一个匿形界面系统的实铡验诞了该方法首先 不用去对大量的或者是无用的代码进行分析，节约了再工程的成本与时间；其次， 由于是采取形式概念分析的方法对关联规则进行挖掘，其准确率霹露信度较直接 通过代码挖掘用例有明显改善。这种方法的应用，对于系统一用户交互频繁的遗 留系统界面具有良好的实用性能。同时，由于遗留系统的平台多样性，本方法也 不可能针对所有模式下、所有语言残孀下的系统，本文主要针对露商对象语言开 发的遗留系统。 s 硕士学位论文第一章绪论 1 4 论文组织结构与内容 本文主要是对遗留系统的界面进行分析，通过形式概念分析方法，最终提取 出系统用例，并提出优化评价标准，得出结论。仔细研究概念格构造算法，并最 终实现交互式的格构建平台，实现了由抽象的元素属性关系到直观、生动的格图 的转换。 具体来说，本文的结构及内容组织如下： 第一章，绪论。介绍国内外用例挖掘的发展现状，概括性描述形式概念分析 应用于系统用例挖掘研究的背景以及这一课题研究的意义。 第二章，形式概念分析基本定义及应用。首先介绍了形式概念分析的一些相 关的概念如：概念、语境、概念格等，以及概念格构造算法的研究。接下来介绍 了形式概念分析概念格在软件工程上的一些应用。 第三章，基于系统用户交互概念格的构造。首先介绍了基于形式概念分析 的用例挖掘方法的研究背景及概述，阐述了方法的基本思想，然后具体介绍方法 的流程与相关技术，最后对方法的性能加以分析，得出结论。 第四章，基于概念格分解的用例挖掘及分析。介绍了概念格水平分解算法 的基本概念及定义性质，并描述了该算法的实现流程，最后对分解后的概念格作 了与用例对应的分析。 第五章，实例研究与分析。介绍了基于形式概念分析的用例挖掘方法所用 到的一些算法、软件等，然后用一个实例对方法进行实现，最后分析实验结果及 性能。 第六章，总结与展望。回顾论文所做的工作，并展望了论文进一步的研究 方向及目标。 6 硕士学位论文第二章形式概念分析 第二章形式概念分析 形式概念分析作为一个建立在数学基础之上的数据挖掘方法，其核心数据结 构概念格非常适合于用来发现规则型知识，可以将数据中内在逻辑和组织结 构完整地图示化。本章主要介绍了形式概念分析方法的基本概念及定义，然后介 绍了相关的概念格构造算法，最后介绍了概念格在软件工程中的应用。 2 1 基本描述及定义 在过去的l o 年中，形式概念分析【5 6 ( f o r m a lc o n c e p ta n a l y s i s ，简称f c a ) 的 应用领域发生了巨大的变化，其主要应用领域逐步从数学转向计算机科学。f c a 被看作是概念化知识处理( c o n c e p t u a lk n o w l e d g ep r o c e s s i n g ，简称c k p ) 数学基础。 i s 0 7 0 4 标准将概念划分为三个层次：对象层，概念层和表示层。其中，对象和 名字之间不存在直接关系，仅由概念为它们提供间接关系。对象为概念层提供概 念的外延，对象具有的共同属性又为概念层提供概念的内涵。 由于“概念”是人类思维最基本的单元，它自然而然地成为人工智能 ( a r t i f i c i a li n t e l l i g e n c e ，简称a i ) 领域的重要研究手段。在知识表示( k n o w l e d g e r e p r e s e n t a t i o n ，简称k r ) ( 如语义网络( s e m a n t i cn e t w o r k s ) ，概念化图( c o n c e p t u a l g r a p h s ) 和描述逻辑( d e s c r i p t i o nl o g i c s ) 等) 中经常可以用至u f c a ；除此之外，f c a 也应用于机器学( m a c h i n el e a r n i n g ) ( 如概念化聚类( c o n c e p t u a lc l u s t e r i n g ) 和概 念学( c o n c e p t u a ll e a r n i n g ) 等) ，软件工程( s o f t w a r ee n g i n e e r i n g ) 和数据挖掘( d a t a m i n i n g ) 等众多研究领域中。 1 9 7 9 年，r w i l l e 提出了f c a ，当时是作为一个数学原理提出的，目的是 为了“重构格理论”( r e s t r u c t u r el a t t i c et h e o r y ) ，这使早期( 8 0 年代至j j 9 0 年代初) 的 f c a 主要分成以下三个研究领域：格理论，例如格的构造与分解算法；定性数 据分析，例如综合测量理论；格应用，例如调查分析。 9 0 年代以前，a i 和f c a 是各自独立发展的。从9 0 年代开始，f c a 研究者们 开始进入知识获取( k n o w l e d g ea c q u i s i t i o n ) 研究领域，同时a i 研究者们也开始将 f c a 作为新的研究工具。f c a 与a i 的结合标志着f c a 正式进入计算机科学中。不 久就产生了c k p 。1 9 9 3 年，e r n s t s c h r o d e rc e n t e rf o rc o n c e 刖a l k n o w l e d g ep r o c e s s i i n g 在德国的d a r m s t a d t 成立，目的是支持和促进c k p 的发展。一年以后，成立了d a r m s t a d t 理工大学分校n a v i c o ng m b h ，目的是 7 硕士学位论文第二章形式概念分析 提供有关f c a 的咨询。 1 9 9 5 年，成立了概念化结构国际会议( i n t e r n a t i o n a lc o n f e r e n c e so nc o n c e p t u a l s t r u c t u r e s ，简称i c c s ) ，标志着f c a 独立成为一项研究领域，这就更加促进了 f c a 与计算机科学的结合。从1 9 9 8 年起，f c a 开始应用于数据挖掘，主要用 来提高数据挖掘算法的效率。如今f c a 已经广泛应用于计算机科学的各个领域。 2 0 0 0 年1 1 月，概念化知识处理研究中心( r e s e a r c hc e n t e rf o rc o n c e p t u a l k n o w l e d g ep r o c e s s i n g ) 在d a r m s t a d t 理工大学成立，预示着f c a 将继续蓬勃发 展。那么f c a 未来的发展方向将如何呢? 结合c k p 与新兴的研究领域? 本体 论工程( o n t o l o g ye n g i n e e r i n g ) 将会得到结论。现今在计算机科学中关于o e 最流 行的定义是t g r u b e r 提出的。他认为“本体”是一个共享的，概念化的，形式化 的，明确的说明( f o r m a l ，e x p l i c i ts p e c i f i c a t i o no f as h a r e dc o n c e p t u a l i z a t i o n ) ，其中“概 念化”是指将现实世界中某一现象中可能出现的概念识别出来，从而形成这个现 象的抽象模型；“明确的”是指本体不是个人私有的，而应当被整个群体所接受。 下面将介绍f c a 的一些基本概念。这些概念是其核心数据结构概念格 的重要组成部分，同时，对概念格的构造、分解过程提供了更为直观清晰的理论 依据及说明。 形式概念分析提供了一种将具有相同属性的一组对象统一起来的方法。隐 藏在f c a 背后的数学原理是由b i 舳o f f 在1 9 4 0 年提出的。描述如下 2 1 1 概念与语境 f c a 的应用是建立在c o n t e x t 上的，一个c o n t e x t 是一个三元函数： c = ( s ，p ，j ) 表2 1 哺乳动物的例子：描述了元素一属性间的二元关系 公式( 2 - 1 ) p l f o u r - l e g g e d h a i r - c o v e r e d i n t e l l i g e n t m a n n et h u m b e d c a t s d o g s x d o l p h i n s g i b b o n s h u m a n s x 、枷a l e s 硕士学位论文 第二章形式概念分析 s 是元素的一个子集，p 是约束性条件的一个子集，i 是g 和p 的一个二元关 系组：j 6 x p ，i 通常用表格r 来描述。表2 1 中展示了我们例子中的二元关系， 在表中，我们看到的元素就是哺乳动物，约束性条件就是它们的特征。 我们可以看到元组( w h a l e s ，m a r i n e ) 在i 中，但是元组( c a t s ，i n t e l l i g e n t ) 不在， 中。设x s 、ycp ，则定义c r ( x ) = p piv e x ：( p ，口) i ) ，表示x 中对 象的共同属性之集和定义r ( r ) = e 引坳y ：( p ，e ) ，) ，表示具有共同属性y 的对象之集，形成了一个g a l o i s 关系。这就是说，这些映射是非单调的： x ls 五一a ( x 2 ) a ( x i ) ，e 专f ( 砭) f ( z ) 和厂坦的：x f ( 仃( x ”。 在那个动物的例子中：仃( c a t s ，g i b b o n s ) = h a i r - c o v e r e d ， z ( m a r i n e ) = d o l p h i n s ，w h a l e s l 。 在前面定义的基础上我们定义一个概念。概念【5 】是一对集合：元素的集合( 外 延) 和属性的集合( 内涵) ( x ，y ) ，例如：y = c r ( x ) 和x = r 0 0 因此，一个概念就是一个有共同属性的元素的最大集合，通俗的说这样一个 概念在交叉表t 中对应着一个最大的矩形：任意的e s 在p 中有所有的属性，所 有的属性p p 对应着s 中所有的元素。在哺乳动物的例子里：( c a t s ，d o g s ， f o u r - l e g g e d ，h a i r - c o v e r e d ) 是一个概念，但( c a t s ，g i b b o n s ， h a i r - c o v e r e d ) 不是一个概念。仃( c a t s ，g i b b o n s ) = h a i r - c o v e r e d ，z ( h a i r - c o v e r e d ) = c a t s ， d o g s ，g i b b o n s 说明它不是一个概念。表2 2 给出了所有的概念。很重要的一点 是它说明了表t 中的行列变化时概念是不变的。 表2 - 2 哺乳动物事例中的概念 t o p ( c a t s ，g i b b o n s ，d o g s ，d o l p h i n s ，h u m a n s ，w h a l e s ，) c 6( g i b b o n s ，d o l p h i n s , h u m a n s , w h a l e s ， i n t e l l g e n t ) c ，( c a t s ，g i b b o n s ，d o g s ， h a i r - c o y e r e d ) c 4( d o l p h i n s ，w h a l e s ， i n t e l l i g e n t ，m a r i n e ) c 3( g i b b o n s ，h u m a n s ， i n te l l i g e n t ，t h u m b e d ) c 2 ( c a t s ， d o g s ， h a i r c o v e r e d ，f o u r l e g g e d ) c i( g i b b o n s ， h a i r - c o v e r e d ，i n t e l l i g e n t ，t h u m b e d ) b o t t o m ( ， f o u r l e g g e d ，h a i r c o ye r e d ，i n te l l i g e n t ，m a r i n e ，t h u m b e d ) 9 硕士学位论文 第二章形式概念分析 2 1 2 概忿格 一个给定语境的所有概念的集合形成了一个完整的偏序关系。从而我们定义 概念( 托，k ) 是概念( x ，i ) 的一个子概念，表示为： ( x 。，k ) g ( x 。，k )如果x o x 。( 或者k ) 。 例如，( d o l p h i n ，w h a l e s ) ， i n t e l l i g e n t ，m a r i n e ) 是( g i b b o n s ，d o l p h i n s ， h u m a n s ，w h a l e s ) ， i n t e l l i g e n t ) 的一个子概念，这些概念组成了一个概念格l ( i ) 。 图2 1 中展示了哺乳动物事例中的概念格。 在表2 2 中，格中的每一个节点都表示是一个概念，给定概念格中两个元组 ( 巨，只) 和( 易，最) ，它们的下界或者交集被定义为： ( e i ，最) n ( 易，) = ( e 。n e ：，o - ( e ln e ：) ) ，它们的上界或者并集被定义为： ( 置，只) u ( 易，罡) = ( f ( 只u b ) ，只u 只) 。 n 0 童 4 2 1 哺乳动物事例中用经典符号表示的格图 1 0 硕士学位论文 第二章形式概念分析 图2 - 2 哺乳动物事例中用完整符号表示的格图 哺乳动物事例中e 3n c 5 和qu 包的结果是： 包n 吃= ( g i b b o n s ，h u m a n s ， i n t e l l i g e n t ，t h u m b e d ) c 、( c a t s ，g i b b o n s ，d o g s ， h a i r - c o v e r e d ) = ( g i b b o n s ，c r ( g i b b o n s ) ) = ( g i b b o n s ， h a i r c o v e r e d , i n t e l l i g e n t ，t h u m e d ) = c - c lu c 2 = ( g i b b o n s ， h a i r c o v e r e d ，i n t e l l i g e n t ，t h u m b e d ) u ( c a t s ，d o g s ， h a i r - c o v e r e d ，f o u r l e g g e d ) = ( r ( h a i r - c o y e r e d ) ，o r h a i r c o v e r e d ) = ( c a t s ，d o g s ，g i b b o n s ， h a i r - c o v e r e d ) = c 硕士学位论文第二章形式概念分析 概念格的基本理论【7 1 讲述的子概念和总概念的关系如下： y ( x ，e ) = 0 ( ir ) ) ，i 影 & k ( 2 - 2 ) j g i i t lt 日 这个理论的意义在于个概念集最小的总概念能够通过交叉它们的内涵并 找到交叉结果中共同的元素计算出来。同样我们能够定义集合： i ( 置，z ) = ( i 置，仃( i 置) ) 公式( 2 - 3 ) i e i 1 日t e l 总概念被称为c o v e r s ，子概念被称为s u b o r d i n a t e s t r l 。概念d 包含概念c ，如果 c c d 并且没有概念e 满足c c e c d 。如果d 包含c ，那么我们称“c 包含于d ”。包含概 念c 的概念的集合表示成c o v s ( c ) 。包含于概念d 中的子概念的集合是概念c 的集合， c 满足cg d ，表示成s u b s ( d ) 。 从概念的计算里面，在概念格中还介绍了两种特殊的概念。假设 c = ( ，p ，j ) ，可以推断出： t o p = p ( ) ，c r ( f ( 妒) ) ) = ( s ，) b o t t o m = ( r ( 仃( 妒) ) ，仃( 庐) ) = ( 痧，尸)公式( 2 - 4 ) 概念t o p 反映出没有一个属性能够适合所有的元素，概念b o t t o m 反映出没有 一个元素满足所有的属性。 概念格里的概念标识： 在标识概念的时候有两种方法，假设概念c = ( e ，p ) ，标识，( c ) 被定义为： ( 1 ) l ( c ) = ( e x t e n t ( c ) ，i n t e n t ( c ) ) = ( e ，p ) ，这就是说，标识列出了所有的为概念 计算出来的元素和属性。 ( 2 ) ，( c ) = ( e n ，己) ，如果c 是最大的概念且它的内涵满足p ( 匕) ，c 是最小的 概念且它的外延满足e ( ee 。) 。p 标识的( 唯一的) 格节点被定义为： ，( p ) = v c ( c ) ip i n t ( c ) ) ，p 标识的( 唯一的) 格节点被定义为： l u ( e ) = c ( k ) i e e x t ( c ) 。 这两种标识都是很有用的，但是具体选择那一个取决于我们要进行什么样 的研究。第一种情况下你有所有概念的内涵和外延，并且每一个的节点都拥有所 有相关的信息，不同的是在第二种情况下，你知道丫( c ) 和r t ( c ) ，关于概念的唯一 的信息是明显的，但是如果我们想得到所有的信息，我们需要忽略总概念和子概 念。使用过形式概念分析的用户喜欢选择第二种符号，因为它使用起来比较灵活。 1 2 硕士学位论文 第二章形式概念分析 2 2 概念格生成算法的研究 生成概念格的过程实际上就是概念聚类的过程，对于同一批数据，所生成的 概念格也是唯一的。也就是说，生成概念格不受数据或属性排列次序的影响，这 也是概念格的优点之一概念格的生成算法基本可以分为两类：批处理式算法和增 量式算法【l 引。 性质2 1 给定上下文( g ，m ，1 ) ，对任意ac _ - g ，能形成概念( 彳”，a ) ( 或者等价地， 对任意bu m ，形成概念( f ，f ) ) 。 定义2 1 设 p ( g ，m ，d ，9 是一个概念格，取( a l ，b i ) ，( a 2 ，b 2 ) e p ( g ， m ，d ，当心，b 2 ) ( a 1 ，b 1 ) 时，则称( a l ，b 1 ) 是( a 2 ，b 2 ) 的父辈结点，也称( a 2 ， b 2 ) 是( a l ，b 1 ) 的子辈结点。 定义2 - 2 设 p ( g ，m ，i ) ，9 是一个概念格，取( a l ，b i ) ，( a 2 ，b 2 ) e p ( g ， m ，d ，当( a 2 ，b 2 ) ( a i ，b i ) 且不存在( a ，b ) 瞰g ，m ，i ) ，使得( a 2 ，b 2 ) ( a ，b ) ( a l ，b 1 ) 时，则称( a l ，b 1 ) 是( a 2 ，b 2 ) 的直接父结点，也称( a 2 ，b 2 ) 是( a 1 ， b 1 ) 的直接子结点对应于h a s s e 上，若( a 2 ，b 2 ) 是似1 ，b i ) 的直接子结点，则 他们之间有连线。 2 2 1 批处理式算法 利用性质2 1 ，产生所有的概念，然后根据它们之间的父子关系确定概念之 间的序： 第l 步：对任意a - g ，生成所有a 。： 第2 步：对第1 步得到的每个，求出a ”： 第