蔣 平
(黃石理工學(xué)院計(jì)算機(jī)學(xué)院,湖北黃石435003)
目前,遺留系統(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)用例挖掘的基本信息來源。
用例是指系統(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)。
形式概念分析是應(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)。
利用形式概念分析方法,用完成系統(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.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)。
圖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)。
由上述分析可知,界面分解后主要包括輸入(文本框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)。
利用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)界面元素。
利用形式概念分析的方法,將任務(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)的用例模型示意圖。
通過一種典型的系統(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