基于概念格的系统用例挖掘方法研究

蒋 平

(黄石理工学院计算机学院，湖北黄石435003)

0 引言

目前，遗留系统用例[1]挖掘方法的研究主要是通过检查和分析面向对象系统的代码来实现。但是许多遗留系统是在面向对象系统的设计方法出现之前产生的，并且遗留系统的代码经常无法得到，而那些可以得到的代码也大多不能分析得到精确的系统功能需求。

形式概念分析(Formal Concept Analysis，简称FCA)作为一个建立在数学基础之上的数据挖掘方法，其核心数据结构——概念格是提取规则知识门的一个很好的平台，非常适合于用来发现规则型知识，可以将数据中内在逻辑和组织结构完整地图示化。

提出一种基于形式概念分析的系统用例挖掘方法:主要针对具有丰富用户界面且系统用户交互频繁的遗留系统[2]，通过检查该系统的使用情况，采用形式概念分析技术，从应用系统的实际运行行为挖掘系统用例。将系统-用户交互的追踪记录作为遗留系统用例挖掘的基本信息来源。

1 基本概念

1.1 用例

用例是指系统为了向参与者提供某些有价值的结果而执行的动作序列，代表的是外部执行者所理解的系统功能，是外部执行者与系统之间的一次典型的交互作用。

用例描述是一个简单的一致的关于参与者和用例如何交互的规格说明，它专注于系统的外在行为而忽略内部究竟是如何实现的。用例描述一般包括:

1)简要描述:对用例的角色、目的的简要描述。

2)前置条件:执行用例之前系统必须要处于的状态或要满足的条件。

3)基本事件流:描述该用例的基本流程。

4)其他事件流:表示行为或流程是可选的或备选的。

5)后置条件:用例执行后系统所处的状态。

1.2 概念格

形式概念分析是应用数学的一个分支，它建立在概念和概念层次的数学化基础之上。运用形式概念分析的方法，可以发现、构造和展示由属性(Attributes)和对象(Objects)构成的概念(Concept)及其之间的关系。

定义1 一个形式化的语境(Context)k=(G，M，I)，包括2个稽核(G和 M)和1个二元关系。在这个语境中，G中的元素称为对象，M中的元素称为属性。

定义 2 对一个对象集A，定义A＇={m∈M|gIm，对所有的g∈A}(即 A中所有的对象共有的属性集合)。相应地，对一个属性集B，定义B＇={g∈G|gIm，对所有的 m∈B}(即包含B中所有的属性集合)。

定义3 一个形式化的背景(Context)C=(O，D，R)，其中O中的元素称为对象，D为描述符(属性)集合，R为 O和 D的二元关系。可用oRd，或者(o，d)∈R来表达对象O和属性D的关系。

定义4 如果(a1，b1)，(a2，b2)是形式化背景中的概念，由层次关系而构建的所有反映了概念间的层次关系(O，D，R)的概念记作β(O，D，R)，被叫作概念格(Concept Lattice)。

2 用例挖掘方法描述及分析

2.1 方法描述

利用形式概念分析方法，用完成系统任务所对应的轨迹(Scenarios)作为对象，用系统界面各个组成部分(Component)所对应的变量作为属性，构造出上下文，并使用形式概念分析的LATTICE算法生成概念格，使用概念格水平分解算法，将生成的概念格分解成若干独立的只和最上、最下元素相连的子概念格，计算每一个子概念格对应的总概念，分解概念格得到用例及其描述。FCA挖掘用例流程图如图1所示。

图1 FCA挖掘用例流程图

第1步:对已知遗留系统的界面进行分析，利用Eclipse平台的Wizard框架，分解系统界面成为单独的组成部分(Component)。

第2步:使用 Lean Cuisine+[3]方法，并采用LeNDI[4]对用户使用系统的轨迹进行追踪记录，从而实现对用户-系统的交互[5]的形式化描述，即轨迹序列(Scenarios)[6]。

第3步:使用LATTICE算法生成概念格。

第4步:使用概念格水平分解算法，将生成的概念格分解成相互独立的多个子概念格，验证各个概念格相互之间的关联。

第5步:对比系统界面描述，分析得到用例。

2.2 方法分析

2.2.1 界面分解

利用Eclipse的 Wizard框架将按钮区和其他界面区分离出来，用类似 MVC的方式实现Wizard框架。在 Eclipse SWT中，有几个重要的界面部件，一个是 Shell-界面的最外层容器，另一个就是Composite-界面元素的集合的容器。界面分解从 Composite开始，首先在Shell中装配上一个空的 Composite，然后将具体界面元素都定义在 Composite里，这样就把Composite逻辑从 Shell中分离出来了，因此现在有了2个类:

1)Editor:该类处理Shell的逻辑，如显示-show，关闭-close，它负责创建和销毁 Editor Composite。

2)Editor Composite:该类处理 Composite的界面逻辑，如创建界面元素。

通过对各自类中元素的属性与具体系统界面的对照与关联，得到系统界面的各个组成部分(如按钮、文本区等)。

2.2.2 交互轨迹

LENDI包括特征提取、屏幕分类和行为标识3个过程[3]。特征提取是抽取可以把相似的截图归纳在一起的特征的过程;屏幕分类过程是根据特征提取过程的3个特性来评估2个屏幕截图是否归为一类;行为标识过程是标识出从一种状态转换为另一种状态的行为。

根据LeNDI方法，采用对图形界面以任务为中心的构造系统-用户交互轨迹的方法，并记录。利用 Lean Cuisine+方法，对遗留系统界面采取以任务为中心的形式化描述，从而间接或者直接地得到系统-用户交互轨迹，并且予以形式化描述。

2.2.3 概念格构造

比较著名的概念格构造算法有 Ganter’s Next-Concept Algorithm，Christian Lindig的 Fast Concept Analysis等，这些算法计算出了格的所有概念以及层次关系。这里使用一种自底向上[7]的计算方式计算出概念格。

1)算法描述。

给定形式化背景(O，D，R)，求出概念格的概念并生成相应的概念格图。

第1步:建立一维数据表 M，存放中间节点，用节点(I，J)抽象表示一个(对象，属性)概念。

第2步:统计并计算出 Max=|J|max，即节点(I，J)所对应的单一对象所具备的属性个数的最大值。

第3步:检查数据表M中的属性个数大于或等于1的节点(I，J)，并将其插入数据表 M中，其存放位置由|J|决定。

第4步:检查M中相同属性的节点，同时将M中Max所对应的节点作为第1层(即UP)节点。

第5步:从第n(n≥1)层开始，循环1～4步，同时，如果对第n+1层的每个节点(i，j)，满足i∩I=i，则将他们之间连接起来;如果对第n-x(1≤x≤n)层的每个节点(l，m)，满足l∩I=l且|I|-|l|=1，则连接。

第6步:算法结束。

2)算法说明。

经计算，算法的时间复杂度为O(counter3*pro_num)，其中 counter的最大取值为，最小取值为 ele_num。所以该概念格构造算法的最大时间复杂度计算得出:(1/8)*O((ele_num2-ele_num)3*pro_num);最小时间复杂度:O(ele_num3*pro_num)。其中pro_num为初始属性个数，ele_num为初始元素个数。

2.2.4 概念格的分解

主要采用概念格水平分解算法对构造好的概念格进行分解。

1)变量说明。

L:已经构造完成的概念格;

U:映射集合2L-＞2L;

M:子集，其中，使得集合 M满足以下条件:M⊆u(M)，u(u(M))=u(M);

L1，L2:概念格的子格;

x1，x2:概念(x1，x2)∈L1╳ L2。

2)算法。

计算出M;

3)算法说明。

该算法主要应用Ganter的概念格算法进行，本算法J(L)和M(L)都是可以估算出来的。经计算，它的时间复杂度为O(n2*|L|3)。

3 实例研究

图2中描述的是一个WEB研究生工作管理子系统，本研究主要对问题解答、学员交流、师生交流3个任务(Task)进行分析，即这里分别记作W1、W2和W3。通过点击其下拉菜单中框中的部分，经过下面的按钮区，点击进入相关文本框，最终再通过表单的形式键盘输入，确认后提交相关页面的内容，从而完成W1、W2和W3 3个任务。

图2 研究生工作管理子系统截图

以任务 W1为例，采用 2.1中的描述方法，分别就系统界面的分解、系统执行轨迹的描述及获取、概念格的构造和分解、系统用例的分析加以实现。

3.1 界面分解组成

由上述分析可知，界面分解后主要包括输入(文本框F、按钮B和菜单D等)和输出(表单G、表格T等)2个部分。T1任务的界面分解如下所示。

输入:问题解答(D1)、问题解答(F1)、回复帖子(B1)、发表话题(B2)、编辑(F2)、预览(B3)、提交(B4)。

输出:问题解答(G1)、帖子列表(T1)、帖子主题(T2)、相关回复(T3)。

3.2 交互轨迹获取

利用Lean Cuisine+方法，可以将W1分解为:提出问题 A1、回复问题 A2和浏览问题A3。Lean Cuisine+方法描述系统执行轨迹如图3所示。

图3 Lean Cuisine+方法描述系统执行轨迹

由此可以得到，W1分解成的A1子任务，所完成的轨迹记为a1，完成A1经过的系统界面元素记为:{D1，F1，T1，B2，B3，B4}。同样的道理，A2、A3子任务所完成的轨迹分别记做a2、a3，他们所经过的系统界面元素记为{D1，F1，T1，T2，B1，B3，B4}、{D1，F1，T1，T2}。依次类推，我们可以分别得到 W2、W3的交互轨迹及其系统界面元素。

3.3 概念格的构造

利用形式概念分析的方法，将任务(任务轨迹，系统组成)按照构造形式化语境的矩阵表示，如表1所示。

表1 任务W1的形式化语境

表1中，“╳”表示连接对象 -属性的符号，比如(a1，F1)可以组成一个语境。利用形式概念分析方法得到所对应的概念如下表2所示。

表2 系统概念集合

分析各个概念之间的联系，通过概念格构造算法，得出图4所示的系统概念格。

图4 问题解答子模块概念格描述

使用概念格水平分解算法，生成子概念格，求出每个子概念对应的总概念，进而得出系统用例的粗糙集。本例子中，有3个用例的侯选者，分别为 U1={C1 C2 C3 C5}、U2={C1 C2 C4 C5}和 U3={C1 C2 C3 C4 C5}。

通过与系统界面对比可以明显看出，对于这3个用例的描述(以U1为例)，验证了系统界面提取系统用例的可操作性。U1表示回复问题的用例。这个用例的文本描述如下:

用例:回复问题

参与者:系统用户

事件流:①进入帖子列表，包括浏览帖子。

②编辑字体、背景、格式等。

③设置回复内容权限。

④系统根据设置参数选择帖子。

其他用例采取类似方式，直至最终对整个系统模块进行分析处理，得到系统用例。同时，对于系统各个用例再进行分析处理化简，便可以得到系统的用例模型示意图。

4 结论

通过一种典型的系统任务轨迹与系统组成之间的关联模式挖掘，并对应于系统用例及用例模型之间的对应关系，避免了对烦琐的代码进行分析，提高了运算效率。实例中采用形式概念分析的方法挖掘图形界面系统的用例，由对系统界面的分析可知，方法的查准率(Precision ratio)对于分析所得界面与系统-用户交互之间的成功比率，由于忽略了任务之间的交互，因而，查准率接近100%，识别出的系统界面的组成部分(Component)占总组成部分的比例，即查全率为(Recall ratio)8/11≈73%，构建概念格算法的响应时间(Response time)约为800 ms。下一步工作就是针对各种不同模式下(如C/S、B/S等)的用例提取，适应各种不同需求的遗留系统的改造。

[1]雅各布森.面向对象软件工程(修订版)(英文版)[M].北京:人民邮电出版社，2003

[2]金龙飞，刘磊.一种基于形式概念分析的语句级自动化方面挖掘方法[J].小型微型计算机系统，2006，27(4):677-680

[3]Chris philips，chris scogings.Task and Dialogue Modelling:Bridging the Divide with Lean Cuisine+2000[J].Proc AUIC’2000，IEEE，Canberra，Australia，2000:81-87

[4]EI-Ramly M，Iglinski P.Modeling the System-User Dialog Using Interaction Traces[C].In:proc.8th Working Conf.Reverse Engineering.IEEE Computer Society，press，2001:110-117

[5]M El Ramly，E Stroulia，P Sorenson.Mining System-User Interaction Traces for Use Case Models[C].Proc.10th Int’l Workshop on Program Comprehension(IWPC’02).IEEE Computer Society Press，2002:21-29

[6]A Egyed.A Scenario-Driven Approach to Trace Dependency Analysis[J].IEEE Transactions On Software Engineering，2003，29(2):116-132

[7]Stumme G，Maedche A.FCA-merge:bottom-up merging of ontologies[C].17th Intl Conf on Artificial Intelligence(IJCAI’01).Germany:Springer，2001:225-230