基于概念格的系統(tǒng)用例挖掘方法研究

蔣 平

(黃石理工學(xué)院計(jì)算機(jī)學(xué)院，湖北黃石435003)

0 引言

目前，遺留系統(tǒng)用例[1]挖掘方法的研究主要是通過檢查和分析面向?qū)ο笙到y(tǒng)的代碼來實(shí)現(xiàn)。但是許多遺留系統(tǒng)是在面向?qū)ο笙到y(tǒng)的設(shè)計(jì)方法出現(xiàn)之前產(chǎn)生的，并且遺留系統(tǒng)的代碼經(jīng)常無法得到，而那些可以得到的代碼也大多不能分析得到精確的系統(tǒng)功能需求。

形式概念分析(Formal Concept Analysis，簡(jiǎn)稱FCA)作為一個(gè)建立在數(shù)學(xué)基礎(chǔ)之上的數(shù)據(jù)挖掘方法，其核心數(shù)據(jù)結(jié)構(gòu)——概念格是提取規(guī)則知識(shí)門的一個(gè)很好的平臺(tái)，非常適合于用來發(fā)現(xiàn)規(guī)則型知識(shí)，可以將數(shù)據(jù)中內(nèi)在邏輯和組織結(jié)構(gòu)完整地圖示化。

提出一種基于形式概念分析的系統(tǒng)用例挖掘方法:主要針對(duì)具有豐富用戶界面且系統(tǒng)用戶交互頻繁的遺留系統(tǒng)[2]，通過檢查該系統(tǒng)的使用情況，采用形式概念分析技術(shù)，從應(yīng)用系統(tǒng)的實(shí)際運(yùn)行行為挖掘系統(tǒng)用例。將系統(tǒng)-用戶交互的追蹤記錄作為遺留系統(tǒng)用例挖掘的基本信息來源。

1 基本概念

1.1 用例

用例是指系統(tǒng)為了向參與者提供某些有價(jià)值的結(jié)果而執(zhí)行的動(dòng)作序列，代表的是外部執(zhí)行者所理解的系統(tǒng)功能，是外部執(zhí)行者與系統(tǒng)之間的一次典型的交互作用。

用例描述是一個(gè)簡(jiǎn)單的一致的關(guān)于參與者和用例如何交互的規(guī)格說明，它專注于系統(tǒng)的外在行為而忽略內(nèi)部究竟是如何實(shí)現(xiàn)的。用例描述一般包括:

1)簡(jiǎn)要描述:對(duì)用例的角色、目的的簡(jiǎn)要描述。

2)前置條件:執(zhí)行用例之前系統(tǒng)必須要處于的狀態(tài)或要滿足的條件。

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

4)其他事件流:表示行為或流程是可選的或備選的。

5)后置條件:用例執(zhí)行后系統(tǒng)所處的狀態(tài)。

1.2 概念格

形式概念分析是應(yīng)用數(shù)學(xué)的一個(gè)分支，它建立在概念和概念層次的數(shù)學(xué)化基礎(chǔ)之上。運(yùn)用形式概念分析的方法，可以發(fā)現(xiàn)、構(gòu)造和展示由屬性(Attributes)和對(duì)象(Objects)構(gòu)成的概念(Concept)及其之間的關(guān)系。

定義1 一個(gè)形式化的語境(Context)k=(G，M，I)，包括2個(gè)稽核(G和 M)和1個(gè)二元關(guān)系。在這個(gè)語境中，G中的元素稱為對(duì)象，M中的元素稱為屬性。

定義 2 對(duì)一個(gè)對(duì)象集A，定義A＇={m∈M|gIm，對(duì)所有的g∈A}(即 A中所有的對(duì)象共有的屬性集合)。相應(yīng)地，對(duì)一個(gè)屬性集B，定義B＇={g∈G|gIm，對(duì)所有的 m∈B}(即包含B中所有的屬性集合)。

定義3 一個(gè)形式化的背景(Context)C=(O，D，R)，其中O中的元素稱為對(duì)象，D為描述符(屬性)集合，R為 O和 D的二元關(guān)系?？捎胦Rd，或者(o，d)∈R來表達(dá)對(duì)象O和屬性D的關(guān)系。

定義4 如果(a1，b1)，(a2，b2)是形式化背景中的概念，由層次關(guān)系而構(gòu)建的所有反映了概念間的層次關(guān)系(O，D，R)的概念記作β(O，D，R)，被叫作概念格(Concept Lattice)。

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

2.1 方法描述

利用形式概念分析方法，用完成系統(tǒng)任務(wù)所對(duì)應(yīng)的軌跡(Scenarios)作為對(duì)象，用系統(tǒng)界面各個(gè)組成部分(Component)所對(duì)應(yīng)的變量作為屬性，構(gòu)造出上下文，并使用形式概念分析的LATTICE算法生成概念格，使用概念格水平分解算法，將生成的概念格分解成若干獨(dú)立的只和最上、最下元素相連的子概念格，計(jì)算每一個(gè)子概念格對(duì)應(yīng)的總概念，分解概念格得到用例及其描述。FCA挖掘用例流程圖如圖1所示。

圖1 FCA挖掘用例流程圖

第1步:對(duì)已知遺留系統(tǒng)的界面進(jìn)行分析，利用Eclipse平臺(tái)的Wizard框架，分解系統(tǒng)界面成為單獨(dú)的組成部分(Component)。

第2步:使用 Lean Cuisine+[3]方法，并采用LeNDI[4]對(duì)用戶使用系統(tǒng)的軌跡進(jìn)行追蹤記錄，從而實(shí)現(xiàn)對(duì)用戶-系統(tǒng)的交互[5]的形式化描述，即軌跡序列(Scenarios)[6]。

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

第4步:使用概念格水平分解算法，將生成的概念格分解成相互獨(dú)立的多個(gè)子概念格，驗(yàn)證各個(gè)概念格相互之間的關(guān)聯(lián)。

第5步:對(duì)比系統(tǒng)界面描述，分析得到用例。

2.2 方法分析

2.2.1 界面分解

利用Eclipse的 Wizard框架將按鈕區(qū)和其他界面區(qū)分離出來，用類似 MVC的方式實(shí)現(xiàn)Wizard框架。在 Eclipse SWT中，有幾個(gè)重要的界面部件，一個(gè)是 Shell-界面的最外層容器，另一個(gè)就是Composite-界面元素的集合的容器。界面分解從 Composite開始，首先在Shell中裝配上一個(gè)空的 Composite，然后將具體界面元素都定義在 Composite里，這樣就把Composite邏輯從 Shell中分離出來了，因此現(xiàn)在有了2個(gè)類:

1)Editor:該類處理Shell的邏輯，如顯示-show，關(guān)閉-close，它負(fù)責(zé)創(chuàng)建和銷毀 Editor Composite。

2)Editor Composite:該類處理 Composite的界面邏輯，如創(chuàng)建界面元素。

通過對(duì)各自類中元素的屬性與具體系統(tǒng)界面的對(duì)照與關(guān)聯(lián)，得到系統(tǒng)界面的各個(gè)組成部分(如按鈕、文本區(qū)等)。

2.2.2 交互軌跡

LENDI包括特征提取、屏幕分類和行為標(biāo)識(shí)3個(gè)過程[3]。特征提取是抽取可以把相似的截圖歸納在一起的特征的過程;屏幕分類過程是根據(jù)特征提取過程的3個(gè)特性來評(píng)估2個(gè)屏幕截圖是否歸為一類;行為標(biāo)識(shí)過程是標(biāo)識(shí)出從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的行為。

根據(jù)LeNDI方法，采用對(duì)圖形界面以任務(wù)為中心的構(gòu)造系統(tǒng)-用戶交互軌跡的方法，并記錄。利用 Lean Cuisine+方法，對(duì)遺留系統(tǒng)界面采取以任務(wù)為中心的形式化描述，從而間接或者直接地得到系統(tǒng)-用戶交互軌跡，并且予以形式化描述。

2.2.3 概念格構(gòu)造

比較著名的概念格構(gòu)造算法有 Ganter’s Next-Concept Algorithm，Christian Lindig的 Fast Concept Analysis等，這些算法計(jì)算出了格的所有概念以及層次關(guān)系。這里使用一種自底向上[7]的計(jì)算方式計(jì)算出概念格。

1)算法描述。

給定形式化背景(O，D，R)，求出概念格的概念并生成相應(yīng)的概念格圖。

第1步:建立一維數(shù)據(jù)表 M，存放中間節(jié)點(diǎn)，用節(jié)點(diǎn)(I，J)抽象表示一個(gè)(對(duì)象，屬性)概念。

第2步:統(tǒng)計(jì)并計(jì)算出 Max=|J|max，即節(jié)點(diǎn)(I，J)所對(duì)應(yīng)的單一對(duì)象所具備的屬性個(gè)數(shù)的最大值。

第3步:檢查數(shù)據(jù)表M中的屬性個(gè)數(shù)大于或等于1的節(jié)點(diǎn)(I，J)，并將其插入數(shù)據(jù)表 M中，其存放位置由|J|決定。

第4步:檢查M中相同屬性的節(jié)點(diǎn)，同時(shí)將M中Max所對(duì)應(yīng)的節(jié)點(diǎn)作為第1層(即UP)節(jié)點(diǎn)。

第5步:從第n(n≥1)層開始，循環(huán)1～4步，同時(shí)，如果對(duì)第n+1層的每個(gè)節(jié)點(diǎn)(i，j)，滿足i∩I=i，則將他們之間連接起來;如果對(duì)第n-x(1≤x≤n)層的每個(gè)節(jié)點(diǎn)(l，m)，滿足l∩I=l且|I|-|l|=1，則連接。

第6步:算法結(jié)束。

2)算法說明。

經(jīng)計(jì)算，算法的時(shí)間復(fù)雜度為O(counter3*pro_num)，其中 counter的最大取值為，最小取值為 ele_num。所以該概念格構(gòu)造算法的最大時(shí)間復(fù)雜度計(jì)算得出:(1/8)*O((ele_num2-ele_num)3*pro_num);最小時(shí)間復(fù)雜度:O(ele_num3*pro_num)。其中pro_num為初始屬性個(gè)數(shù)，ele_num為初始元素個(gè)數(shù)。

2.2.4 概念格的分解

主要采用概念格水平分解算法對(duì)構(gòu)造好的概念格進(jìn)行分解。

1)變量說明。

L:已經(jīng)構(gòu)造完成的概念格;

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

M:子集，其中，使得集合 M滿足以下條件:M?u(M)，u(u(M))=u(M);

L1，L2:概念格的子格;

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

2)算法。

計(jì)算出M;

3)算法說明。

該算法主要應(yīng)用Ganter的概念格算法進(jìn)行，本算法J(L)和M(L)都是可以估算出來的。經(jīng)計(jì)算，它的時(shí)間復(fù)雜度為O(n2*|L|3)。

3 實(shí)例研究

圖2中描述的是一個(gè)WEB研究生工作管理子系統(tǒng)，本研究主要對(duì)問題解答、學(xué)員交流、師生交流3個(gè)任務(wù)(Task)進(jìn)行分析，即這里分別記作W1、W2和W3。通過點(diǎn)擊其下拉菜單中框中的部分，經(jīng)過下面的按鈕區(qū)，點(diǎn)擊進(jìn)入相關(guān)文本框，最終再通過表單的形式鍵盤輸入，確認(rèn)后提交相關(guān)頁面的內(nèi)容，從而完成W1、W2和W3 3個(gè)任務(wù)。

圖2 研究生工作管理子系統(tǒng)截圖

以任務(wù) W1為例，采用 2.1中的描述方法，分別就系統(tǒng)界面的分解、系統(tǒng)執(zhí)行軌跡的描述及獲取、概念格的構(gòu)造和分解、系統(tǒng)用例的分析加以實(shí)現(xiàn)。

3.1 界面分解組成

由上述分析可知，界面分解后主要包括輸入(文本框F、按鈕B和菜單D等)和輸出(表單G、表格T等)2個(gè)部分。T1任務(wù)的界面分解如下所示。

輸入:問題解答(D1)、問題解答(F1)、回復(fù)帖子(B1)、發(fā)表話題(B2)、編輯(F2)、預(yù)覽(B3)、提交(B4)。

輸出:問題解答(G1)、帖子列表(T1)、帖子主題(T2)、相關(guān)回復(fù)(T3)。

3.2 交互軌跡獲取

利用Lean Cuisine+方法，可以將W1分解為:提出問題 A1、回復(fù)問題 A2和瀏覽問題A3。Lean Cuisine+方法描述系統(tǒng)執(zhí)行軌跡如圖3所示。

圖3 Lean Cuisine+方法描述系統(tǒng)執(zhí)行軌跡

由此可以得到，W1分解成的A1子任務(wù)，所完成的軌跡記為a1，完成A1經(jīng)過的系統(tǒng)界面元素記為:{D1，F(xiàn)1，T1，B2，B3，B4}。同樣的道理，A2、A3子任務(wù)所完成的軌跡分別記做a2、a3，他們所經(jīng)過的系統(tǒng)界面元素記為{D1，F(xiàn)1，T1，T2，B1，B3，B4}、{D1，F(xiàn)1，T1，T2}。依次類推，我們可以分別得到 W2、W3的交互軌跡及其系統(tǒng)界面元素。

3.3 概念格的構(gòu)造

利用形式概念分析的方法，將任務(wù)(任務(wù)軌跡，系統(tǒng)組成)按照構(gòu)造形式化語境的矩陣表示，如表1所示。

表1 任務(wù)W1的形式化語境

表1中，“╳”表示連接對(duì)象 -屬性的符號(hào)，比如(a1，F(xiàn)1)可以組成一個(gè)語境。利用形式概念分析方法得到所對(duì)應(yīng)的概念如下表2所示。

表2 系統(tǒng)概念集合

分析各個(gè)概念之間的聯(lián)系，通過概念格構(gòu)造算法，得出圖4所示的系統(tǒng)概念格。

圖4 問題解答子模塊概念格描述

使用概念格水平分解算法，生成子概念格，求出每個(gè)子概念對(duì)應(yīng)的總概念，進(jìn)而得出系統(tǒng)用例的粗糙集。本例子中，有3個(gè)用例的侯選者，分別為 U1={C1 C2 C3 C5}、U2={C1 C2 C4 C5}和 U3={C1 C2 C3 C4 C5}。

通過與系統(tǒng)界面對(duì)比可以明顯看出，對(duì)于這3個(gè)用例的描述(以U1為例)，驗(yàn)證了系統(tǒng)界面提取系統(tǒng)用例的可操作性。U1表示回復(fù)問題的用例。這個(gè)用例的文本描述如下:

用例:回復(fù)問題

參與者:系統(tǒng)用戶

事件流:①進(jìn)入帖子列表，包括瀏覽帖子。

②編輯字體、背景、格式等。

③設(shè)置回復(fù)內(nèi)容權(quán)限。

④系統(tǒng)根據(jù)設(shè)置參數(shù)選擇帖子。

其他用例采取類似方式，直至最終對(duì)整個(gè)系統(tǒng)模塊進(jìn)行分析處理，得到系統(tǒng)用例。同時(shí)，對(duì)于系統(tǒng)各個(gè)用例再進(jìn)行分析處理化簡(jiǎn)，便可以得到系統(tǒng)的用例模型示意圖。

4 結(jié)論

通過一種典型的系統(tǒng)任務(wù)軌跡與系統(tǒng)組成之間的關(guān)聯(lián)模式挖掘，并對(duì)應(yīng)于系統(tǒng)用例及用例模型之間的對(duì)應(yīng)關(guān)系，避免了對(duì)煩瑣的代碼進(jìn)行分析，提高了運(yùn)算效率。實(shí)例中采用形式概念分析的方法挖掘圖形界面系統(tǒng)的用例，由對(duì)系統(tǒng)界面的分析可知，方法的查準(zhǔn)率(Precision ratio)對(duì)于分析所得界面與系統(tǒng)-用戶交互之間的成功比率，由于忽略了任務(wù)之間的交互，因而，查準(zhǔn)率接近100%，識(shí)別出的系統(tǒng)界面的組成部分(Component)占總組成部分的比例，即查全率為(Recall ratio)8/11≈73%，構(gòu)建概念格算法的響應(yīng)時(shí)間(Response time)約為800 ms。下一步工作就是針對(duì)各種不同模式下(如C/S、B/S等)的用例提取，適應(yīng)各種不同需求的遺留系統(tǒng)的改造。

[1]雅各布森.面向?qū)ο筌浖こ?修訂版)(英文版)[M].北京:人民郵電出版社，2003

[2]金龍飛，劉磊.一種基于形式概念分析的語句級(jí)自動(dòng)化方面挖掘方法[J].小型微型計(jì)算機(jī)系統(tǒng)，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