蔣 平

(黃石理工學院計算機學院，湖北黃石435003)

0 引言

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

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

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

1 基本概念

1.1 用例

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

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

1)簡要描述:對用例的角色、目的的簡要描述。

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

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

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

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

1.2 概念格

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

定義1 一個形式化的語境(Context)k=(G，M，I)，包括2個稽核(G和 M)和1個二元關(guān)系。在這個語境中，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的二元關(guān)系?？捎胦Rd，或者(o，d)∈R來表達對象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ù)所對應的軌跡(Scenarios)作為對象，用系統(tǒng)界面各個組成部分(Component)所對應的變量作為屬性，構(gòu)造出上下文，并使用形式概念分析的LATTICE算法生成概念格，使用概念格水平分解算法，將生成的概念格分解成若干獨立的只和最上、最下元素相連的子概念格，計算每一個子概念格對應的總概念，分解概念格得到用例及其描述。FCA挖掘用例流程圖如圖1所示。

圖1 FCA挖掘用例流程圖

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

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

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

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

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

2.2 方法分析

2.2.1 界面分解

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

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

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

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

2.2.2 交互軌跡

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

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

2.2.3 概念格構(gòu)造

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

1)算法描述。

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

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

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

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

第4步:檢查M中相同屬性的節(jié)點，同時將M中Max所對應的節(jié)點作為第1層(即UP)節(jié)點。

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

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

2)算法說明。

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

2.2.4 概念格的分解

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

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)算法。

計算出M;

3)算法說明。

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

3 實例研究

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

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

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

3.1 界面分解組成

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

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

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

3.2 交互軌跡獲取

利用Lean Cuisine+方法，可以將W1分解為:提出問題 A1、回復問題 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中，“╳”表示連接對象 -屬性的符號，比如(a1，F(xiàn)1)可以組成一個語境。利用形式概念分析方法得到所對應的概念如下表2所示。

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

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

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

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

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

用例:回復問題

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

事件流:①進入帖子列表，包括瀏覽帖子。

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

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

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

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

4 結(jié)論

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

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

[2]金龍飛，劉磊.一種基于形式概念分析的語句級自動化方面挖掘方法[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