一種基于特征模型和協(xié)同過濾的需求獲取方法

彭珍連　王　健　何克清　唐明董

1(軟件工程國家重點實驗室(武漢大學(xué))　武漢　430072)2(湖南科技大學(xué)計算機科學(xué)與工程學(xué)院　湖南湘潭　411201)

?

一種基于特征模型和協(xié)同過濾的需求獲取方法

彭珍連1,2王健1何克清1唐明董2

1(軟件工程國家重點實驗室(武漢大學(xué))武漢430072)2(湖南科技大學(xué)計算機科學(xué)與工程學(xué)院湖南湘潭411201)

(zlpeng@whu.edu.cn)

隨著互聯(lián)網(wǎng)和Web服務(wù)相關(guān)技術(shù)的快速發(fā)展，基于互聯(lián)網(wǎng)進行軟件開發(fā)越來越受到軟件開發(fā)從業(yè)者的青睞.軟件開發(fā)是一種多知識密集型過程，其中需求獲取對軟件系統(tǒng)的成功具有關(guān)鍵作用.基于互聯(lián)網(wǎng)的軟件需要滿足大量地理位置各異、類型不同的客戶需求，這增加了需求獲取的難度；與此同時，互聯(lián)網(wǎng)上相似類型的軟件眾多，這些具有大量相似功能的軟件為軟件需求獲取提供了新的途徑.為此，已有研究將推薦系統(tǒng)引入到軟件需求獲取過程中，借助于已有相似軟件需求描述，為新軟件推薦合適的缺失特征.為了提高推薦系統(tǒng)在軟件需求預(yù)測和輔助獲取過程中的準(zhǔn)確率，提出了FM_KNN算法，利用特征模型中的特征類型以及特征間的關(guān)聯(lián)關(guān)系，結(jié)合KNN(K-nearest neighbors)協(xié)同過濾推薦系統(tǒng)進行輔助需求獲取.通過在真實數(shù)據(jù)集和仿真數(shù)據(jù)集上的實驗和分析，驗證了所提方法在預(yù)測準(zhǔn)確率上具有更好的效果，從而為需求獲取提供更好的支持.

需求獲取；特征模型；協(xié)同過濾；推薦系統(tǒng)；特征推薦

隨著互聯(lián)網(wǎng)和Web服務(wù)技術(shù)的快速發(fā)展，基于互聯(lián)網(wǎng)進行軟件開發(fā)越來越受到軟件從業(yè)者的青睞.與傳統(tǒng)軟件開發(fā)類似，基于互聯(lián)網(wǎng)的軟件開發(fā)開始于需求收集階段，在此階段中各行業(yè)分析師與項目利益相關(guān)者合作以獲取軟件系統(tǒng)的需求.軟件需求獲取的質(zhì)量是軟件成功與否的關(guān)鍵.一個眾所周知的事實是在軟件開發(fā)后期階段糾正錯誤的代價將呈指數(shù)增長，如果在軟件需求獲取過程發(fā)現(xiàn)缺失或錯誤的需求，修改這些錯誤的代價將急劇降低[1].然而，在需求收集和獲取階段要檢查和確定丟失或錯誤軟件需求所要付出的努力是巨大、耗時且容易出錯的，因此如何選取有效的軟件需求獲取技術(shù)成為軟件開發(fā)實踐者和研究者關(guān)心的問題.

軟件需求獲取是從軟件用戶、消費者和各利益相關(guān)者收集軟件需求的過程.這是一個復(fù)雜的過程，因為它不僅是從軟件消費者收集需求的實踐過程，也需要軟件消費者、各利益相關(guān)者和需求分析師的參與來收集良好和一致的需求集合以真正解決問題的過程.已有許多研究根據(jù)待開發(fā)軟件系統(tǒng)的領(lǐng)域知識和(或)情景特點提出不同的軟件需求獲取方法或框架[1-4]，這些方法在軟件開發(fā)需求過程中能有效指導(dǎo)軟件需求獲取，減少需求過程中的工作負擔(dān)和錯誤風(fēng)險，同時領(lǐng)域知識構(gòu)造常常需要付出大量人工操作.基于互聯(lián)網(wǎng)的軟件需要滿足大量地理位置各異、類型不同的客戶需求，這增加了需求獲取的困難；同時，互聯(lián)網(wǎng)上相似軟件眾多，這些具有大量相似功能的軟件為軟件需求獲取提供了新的途徑.為此，已有研究將推薦系統(tǒng)引入到需求工程領(lǐng)域.Laurent等人[5]探索利用網(wǎng)絡(luò)論壇的方式進行供應(yīng)商主導(dǎo)的開源項目需求工程任務(wù).Castro-Herrera等人[6-7]使用組織者和發(fā)起者協(xié)同思想(organizer and promoter of collaborative ideas, OPCI)推薦系統(tǒng)來支持推薦領(lǐng)域?qū)＜?expert stakeholder)和需求主題，從而借助專家的領(lǐng)域知識輔助進行需求獲取.這些方法能夠指導(dǎo)面向網(wǎng)絡(luò)的軟件開發(fā)過程中需求組織者和分析師解決軟件需求獲取問題，但未充分利用已有相似軟件的公共領(lǐng)域知識.Hariri等人[8]設(shè)計了一個推薦系統(tǒng)來降低執(zhí)行領(lǐng)域分析時的人工操作負擔(dān)，使用數(shù)據(jù)挖掘算法抽取在線產(chǎn)品描述的公共特征以及這些特征之間的關(guān)聯(lián)關(guān)系，然后使用關(guān)聯(lián)規(guī)則(association rule)挖掘和KNN方法(本文記為AR_KNN)為具有部分特征的新軟件產(chǎn)品推薦其缺失的特征.該方法利用了特征之間的關(guān)聯(lián)關(guān)系，然而該方法只是挖掘特征之間的共現(xiàn)關(guān)系，并未考慮特征之間存在的如多選一、多選多、互斥等關(guān)聯(lián)關(guān)系，使得待開發(fā)軟件難以擁有必需的初始特征作為特征推薦的基礎(chǔ)，從而影響預(yù)測的準(zhǔn)確率.

因此，如何快速準(zhǔn)確地預(yù)測缺失特征成為軟件需求獲取過程需要解決的問題.為此，本文借鑒上述文獻的思想，結(jié)合文獻[9]中對特征的內(nèi)涵和外延2方面的定義(就內(nèi)涵而言特征是由一組相對緊密關(guān)聯(lián)的單個需求構(gòu)成的集合，就外延而言特征是一種具有用戶價值的軟件特點)，利用已有的相似軟件領(lǐng)域知識即軟件特征模型輔助引導(dǎo)用戶進行需求描述，使用推薦系統(tǒng)為具有部分特征的待開發(fā)軟件推薦特征，從而進行需求輔助獲取，以降低需求獲取過程中復(fù)雜而繁瑣的人工負擔(dān).具體而言，本文方法是在特征模型的基礎(chǔ)上，將某一具體領(lǐng)域內(nèi)各個已存在軟件看作推薦系統(tǒng)中的歷史用戶，各個軟件所擁有的特征看作推薦系統(tǒng)中的項目，充分利用特征模型中各個特征之間存在的關(guān)聯(lián)關(guān)系，結(jié)合KNN協(xié)同過濾[10-12]推薦系統(tǒng)，通過預(yù)測可能的特征來補充待開發(fā)軟件的需求.通過在真實數(shù)據(jù)集和仿真數(shù)據(jù)集上的實驗分析，本文所提方法比普通KNN協(xié)同過濾預(yù)測算法和AR_KNN協(xié)同過濾算法準(zhǔn)確率要高，最高提高了大約6%.

1　背景知識

1.1特征模型

特征模型來源于軟件工程學(xué)科，用來表示某一領(lǐng)域的軟件系統(tǒng)中的共性和可變性.根據(jù)文獻[13-15]的描述，特征圖是特征模型的圖形化表示，一般組織成樹形結(jié)構(gòu)，樹的根節(jié)點稱為根特征，表示一個領(lǐng)域概念，樹的分支可以被定義成精化關(guān)系，即必選(Mandatory)特征、可選(Optional)特征、多選多(OR)關(guān)系和多選一(XOR)關(guān)系；另外，特征之間存在交叉樹約束關(guān)系，如依賴(Requires)關(guān)系和互斥(Excludes)關(guān)系.圖1顯示了本文所用數(shù)據(jù)集中移動終端搜索引擎軟件(Wiki軟件)領(lǐng)域的特征模型示例(部分)，圖1中根節(jié)點為“Wiki Software”，代表一個軟件族；根節(jié)點的子特征“Data Storage”和“Development Language”為必選特征，“Search Means”為可選特征；特征“Data Storage”的子特征“Database”和“File”與其父特征構(gòu)成多選多關(guān)系，即“Data Storage”可以同時為“Database”和“File”；特征“Development Language”的子特征包括“Java”，“PHP”，“Python”，它們之間為多選一關(guān)系，即對某個具體的“Wiki Software”而言，“Development Language”只能是“Java”，“PHP”，“Python”中的一種；特征“File Name”依賴特征“File”，即“Search Means”為“File Name”時，必須確保“Data Storage”包含“File”.

本文引用文獻[13-14]對特征模型、特征模型配置的定義如下：

定義1. 特征模型(feature model， FM).定義為一個七元組FM=(G，EMAND，EOPT，GXOR，GOR，RE，EX).其中，G=(F，E，r)是一個有根樹，F(xiàn)=(Ffun，F(xiàn)att)是軟件特征的有限集合，F(xiàn)fun是軟件功能特征，F(xiàn)att是軟件非功能特征(也稱屬性特征)，E?F×F是有限邊集合，r∈F是根特征；EMAND?E定義必選特征與它們父特征的邊集合；EOPT?E定義可選特征與它們父特征的邊集合；GXOR?P(F)×F，GOR?P(F)×F定義特征組，表示兒子特征與它們公共父特征的值對集合；RE定義依賴關(guān)系，形式化為A?B；EX定義互斥關(guān)系，形式化為A?B，A∈F，且B∈F.

定義2. 特征模型配置.定義為一組選擇的特征集合.它是在軟件產(chǎn)品配置過程中可選方案的一種決策結(jié)果，它僅代表一個滿足特征模型中語義約束的軟件產(chǎn)品設(shè)計，可以充當(dāng)軟件產(chǎn)品實現(xiàn)的輸入并記錄軟件產(chǎn)品設(shè)計決策.

圖1中的特征模型示例，(“Wiki Software”，“Data Storage”，“Database”，“Development Language”，“Java”)是一個特征模型配置；而(“Wiki Software”，“Data Storage”，“Database”，“Search Means”，“File Name”)不是特征模型配置，因為它違反了依賴(Requires)關(guān)系.

1.2推薦系統(tǒng)

推薦系統(tǒng)是解決信息超載問題的有效辦法.常用的推薦系統(tǒng)技術(shù)包括基于協(xié)同過濾(collaborative filtering，CF)推薦[10-12]、基于內(nèi)容的(content-based，CB)推薦[10,16]以及矩陣分解(matrix factorization，MF)方法[17].根據(jù)文獻[18]的研究，當(dāng)推薦的數(shù)據(jù)為0-1矩陣時，KNN協(xié)同過濾推薦系統(tǒng)的效果要優(yōu)于矩陣分解方法，由于特征模型的數(shù)據(jù)被表示為0-1矩陣，故本文不考慮矩陣分解方法.

KNN協(xié)同過濾推薦系統(tǒng)的基本思想是用戶往往喜歡與其偏好和背景相似用戶所喜歡的項目.在0-1矩陣數(shù)據(jù)中，KNN協(xié)同過濾算法往往針對一組(如m個)用戶和一組(如n個)項目，用戶對項目的偏好可以通過一個用戶-項目矩陣R=(Ri j)表示，Ri j=1表示用戶i對項目j有偏好關(guān)系，Ri j=0表示用戶i對項目j無偏好關(guān)系.

本文要研究的問題可以轉(zhuǎn)化為某0-1向量(待開發(fā)軟件)缺失特征值的預(yù)測問題.本文采用的方法是需要根據(jù)KNN協(xié)同過濾算法計算最相似(最近)鄰居，利用這些最相似鄰居數(shù)據(jù)對包含部分特征的待開發(fā)軟件的缺失特征值進行預(yù)測.為了提高預(yù)測準(zhǔn)確率，針對待開發(fā)軟件可能存在的特征數(shù)據(jù)稀疏性，采用特征模型中語義約束關(guān)系來擴充待開發(fā)軟件的特征偏好信息.

2　基于特征模型和協(xié)同過濾的需求獲取

2.1需求獲取方法框架

本文提出的基于特征模型和協(xié)同過濾的軟件需求獲取方法假設(shè)領(lǐng)域?qū)＜乙呀?jīng)收集相當(dāng)數(shù)量相似軟件的需求描述文檔，方法框架如圖2所示.需求獲取過程分為以下4個階段：

1) 領(lǐng)域?qū)＜沂紫仁占⑤斎胍延熊浖枋鑫臋n，然后利用領(lǐng)域分類算法將一些相關(guān)的描述文檔分類到不同的領(lǐng)域.該階段中涉及的領(lǐng)域分類算法采用本課題組前期工作提出的面向主題的領(lǐng)域分類算法[19]，可以自動化完成.

2) 在與待開發(fā)軟件相同的領(lǐng)域中，對于分類得到的需求描述文檔，利用領(lǐng)域分析工具(如Screen-Scraper[15])結(jié)合領(lǐng)域?qū)＜业念I(lǐng)域知識分析得到已有軟件-特征的0-1矩陣.該階段工作半自動化完成.

3) 根據(jù)前面得到的同一領(lǐng)域軟件的0-1矩陣，領(lǐng)域?qū)＜依梦墨I[13]提出的特征模型提取算法，構(gòu)建已有相似軟件的特征模型.該階段工作是自動化完成的.

4) 需求分析師輸入具有部分特征的軟件描述(表示為0-1向量)，根據(jù)由以上步驟構(gòu)建的特征模型和已存在的軟件-特征0-1矩陣，利用基于特征模型的特征推薦算法，得到輸出結(jié)果為具有補充特征的軟件描述(表示為0-1向量)，供需求分析師進一步進行需求獲取操作.該階段工作是自動化完成的.

由以上描述可知，前3個階段的工作可以由需求領(lǐng)域?qū)＜依矛F(xiàn)成的算法或工具實現(xiàn)，本文工作聚焦在最后一個階段，即利用前面階段得到的軟件-特征0-1矩陣和軟件特征模型，采用軟件特征推薦算法，為需求分析師得到更加豐富的軟件需求描述信息，減輕軟件獲取過程中的人工操作負擔(dān)和盡量減少需求獲取過程中出現(xiàn)的錯誤概率.

Fig. 2　Framework for requirements elicitation method based on feature model.圖2　基于特征模型的需求獲取方法框架

2.2需求獲取算法流程

本節(jié)主要介紹本文需求獲取算法的實現(xiàn)流程.圖3顯示了該流程，主要包含3部分：1)FM語義關(guān)系條件轉(zhuǎn)換.利用FM特征的類型與特征之間關(guān)聯(lián)關(guān)系對當(dāng)前用戶的初始特征偏好向量補充一部分缺失特征值，得到中間特征向量.2)推薦系統(tǒng).采用KNN協(xié)同過濾算法，根據(jù)中間特征向量和歷史軟件數(shù)據(jù)，先尋找到K個最近鄰的鄰居用戶，然后利用K個最近鄰的鄰居用戶對特征的偏好值對當(dāng)前用戶中缺失特征值進行預(yù)測(0或1)，得到具有補充值的軟件特征偏好向量.3)軟件-特征矩陣數(shù)據(jù)庫.主要功能是為推薦系統(tǒng)提供歷史軟件描述數(shù)據(jù).新得到的向量可以作為一條新的軟件描述數(shù)據(jù)加入軟件-特征數(shù)據(jù)庫以更新歷史數(shù)據(jù)，以實現(xiàn)歷史數(shù)據(jù)的迭代式生成.

Fig. 3　Process of requirements elicitation algorithm.圖3　需求獲取算法流程

2.3示例

首先通過一個示例闡述本文方法的基本思路.假設(shè)圖4所示為一個簡單的軟件-特征矩陣示例，其中，Si表示軟件集合中第i個軟件，F(xiàn)j表示特征集合中第j個特征，如果第i行第j列單元格內(nèi)容為1表示第i個軟件Si擁有第j個特征Fj；反之，如果該單元格內(nèi)容為0表示第i個軟件Si不擁有第j個特征Fj.圖4中S1～S4為歷史軟件，S5為待開發(fā)軟件；F1～F9為軟件特征；符號“？”表示軟件S5中表達不清楚或不確定的軟件特征.

F1F2F3F4F5F6F7F8F9

Fig. 4Software-feature matrix sample.
圖4軟件-特征矩陣示例

采用文獻[13]的特征模型提取算法，構(gòu)建其對應(yīng)的特征模型如圖5所示:

Fig. 5　An example of feature model.圖5　特征模型示例

2.4FM語義約束條件轉(zhuǎn)換規(guī)則

如1.1節(jié)所述，F(xiàn)M關(guān)聯(lián)關(guān)系主要有精化關(guān)系如必選、可選、多選多和多選一，約束關(guān)系如依賴和互斥.在為當(dāng)前用戶擴充特征偏好信息過程中，特征模型的精化關(guān)系和約束關(guān)系可以轉(zhuǎn)換為一系列條件規(guī)則.

定義3. FM語義關(guān)系轉(zhuǎn)換規(guī)則.該規(guī)則指的是在具體的軟件需求應(yīng)用領(lǐng)域，F(xiàn)M語義關(guān)系可以轉(zhuǎn)換為以下規(guī)則對軟件缺失特征值進行預(yù)測：

1) 如果特征Fi為Mandatory特征，則所有的軟件都擁有該特征，即所有軟件中Fi=1.

2) 如果特征Fi為Optional特征且包含若干子特征，某軟件中其子特征至少有一個值為1，則該軟件中Fi=1.

3) 如果特征Fi，F(xiàn)j，F(xiàn)k有共同的父特征并且滿足OR關(guān)系，則Fi，F(xiàn)j，F(xiàn)k在每一個軟件中至少有一個值為1，即Fi，F(xiàn)j，F(xiàn)k的值不能同時為0.

4) 如果特征Fi，F(xiàn)j，F(xiàn)k有共同的父特征且滿足XOR關(guān)系，則Fi，F(xiàn)j，F(xiàn)k在每一個軟件中有且僅有一個值為1，其他的值為0.

5) 如果特征Fi和特征Fj滿足FiRequiresFj，在每一個軟件中，若Fj=0，則Fi=0；若Fj=1，則Fi=1或者Fi=0.

6) 如果特征Fi和特征Fj滿足FiExcludesFj，在每一個軟件中，若Fi=0，則Fj=1；若Fi=1，則Fj=0.

7) 如果特征Fi為特征Fj的子特征，且Fj=0，則在每一個軟件中，F(xiàn)i=0.

2.5尋找最近鄰居

對于待開發(fā)軟件的中間向量，我們采用KNN協(xié)同過濾算法，先通過相似度計算在歷史軟件-特征數(shù)據(jù)中尋找最近鄰居.有許多方法用來計算待開發(fā)軟件數(shù)據(jù)和歷史軟件數(shù)據(jù)之間的相似度如Pearson相關(guān)度、余弦相似度、Spearman相似度和Tanimoto(即Jaccard)相似度[12].本文數(shù)據(jù)是0-1矩陣，因此使用Tanimoto相似度來計算待開發(fā)軟件與歷史軟件之間的相似度：

(1)其中，Sa表示待開發(fā)軟件，Si表示某歷史軟件，|Sa∩Si|表示待開發(fā)軟件與該歷史軟件中特征值相等的數(shù)目，|Sa|表示待開發(fā)軟件中特征值已知的數(shù)目，|Si|表示該歷史軟件中特征值已知的數(shù)目.通過計算待開發(fā)軟件與歷史軟件之間的相似度，并按降序排列，就可以選擇出待開發(fā)軟件的最近鄰居.

2.6缺失特征值預(yù)測

為了預(yù)測待開發(fā)軟件缺失特征值，我們通過計算prefer值來確定待開發(fā)軟件是否擁有缺失特征，用式(2)表示：

prefer(Sa,Fj)=

(2)

其中，Neighbor(Sa)表示待開發(fā)軟件Sa的鄰居軟件集合，F(xiàn)j表示待開發(fā)軟件Sa中的某個缺失特征，Vj表示Si中的Fj特征的值.設(shè)定一個閾值α(本文取值0.5)，如果該預(yù)測值小于α，說明大多數(shù)鄰居軟件在該特征上的取值為0，因此該缺失特征預(yù)測值取值為0，否則取值為1.

2.7需求獲取算法

本文提出了軟件需求獲取算法FM_KNN(feature model andK-nearest neighbors)，如算法1所示.

算法1. 軟件需求獲取算法FM_KNN.

輸入：歷史軟件集S(|S|=m)、軟件特征集F(|F|=n)、軟件特征模型FM、具有缺失特征值(標(biāo)記為Null)的待開發(fā)軟件(標(biāo)記為Sa)特征偏好向量μ(1×n的0-1向量)、最近鄰居數(shù)K、閾值α；

輸出：預(yù)測的具有補充值的待開發(fā)軟件特征的偏好向量λ(1×n的0-1向量).

① 調(diào)用算法FMSCF(μ)并將結(jié)果更新到μ；

② for eachSi∈S

③ 根據(jù)式(1)計算similarity(Sa，Si)的值；

④ end for

⑤ 按降序排序similarity(Sa，Si)的值；

⑥ 尋找Sa的K個最近鄰居Neighbor(Sa)?S；

⑦ for eachFj∈F

⑧ if (μ(Fj)=Null)

⑨ 根據(jù)式(2)計算prefer(Sa，F(xiàn)j)的值；

⑩ if (prefer(Sa，F(xiàn)j)≥α)

算法1中調(diào)用了特征模型語義約束過濾(feature model semantic constraints filter, FMSCF)算法，為待開發(fā)軟件的初始偏好向量μ進行初步預(yù)測，補充部分缺失特征值.算法2描述了FMSCF算法的過程.

算法2. 特征模型語義約束過濾算法FMSCF.

輸入：軟件特征模型FM、軟件特征集F、具有缺失特征值的待開發(fā)軟件特征偏好向量μ；

輸出：補充部分缺失特征值的向量ν(1×n的0-1向量).

① for eachFj∈F

② if (μ(Fj)=Null)

③ if ((Fj.par，F(xiàn)j)∈EMAND&&

μ(Fj.par)=1)*Fj.par為Fj的

④μ(Fj)=1；

⑤ end if

⑥ if ((Fj.par，F(xiàn)j)∈GOR&&μ(Fj.par)=

⑦ if (?F′((F′≠Fj) && (Fj.par，

F′)∈GOR&&μ(F′)=0))

⑧μ(Fj)=1；

⑨ end if

⑩ end if

μ(Fj.par)=1)*Fj，F(xiàn)j.par滿足

F′)∈GXOR&&μ(F′)=1))

在時間復(fù)雜度方面，F(xiàn)M_KNN算法除了行①以外其他各步與KNN算法完全相同，KNN算法時間復(fù)雜度為O(mn+m2)，而FM_KNN算法中行①為FMSCF算法的調(diào)用，該FMSCF算法時間復(fù)雜度為O(K′n)，其中，K′為常數(shù)(表示單個特征關(guān)聯(lián)關(guān)系數(shù)最大值)，故FM_KNN算法整體時間復(fù)雜度仍為O(mn+m2).

3　實驗分析

3.1實驗準(zhǔn)備

本節(jié)通過實驗來檢驗該預(yù)測方法的有效性.我們分別在真實數(shù)據(jù)集和仿真數(shù)據(jù)集上開展實驗，實驗在MyEclipse 8.6中實現(xiàn)，所有實驗運行于臺式機，機器配置如下：操作系統(tǒng)為Win7_64旗艦版，CPU為intel CoreTMi7-4790 CPU@3.60 GHz(4 core)，內(nèi)存為8 GB.

當(dāng)前公開的軟件特征模型數(shù)據(jù)比較稀少，本文的實驗數(shù)據(jù)之一來源于德國軟件公司CosmoCode發(fā)布的針對移動專業(yè)人群的Wiki軟件及其特征數(shù)據(jù)①，截至2014年12月31日，其發(fā)布頁面已有141個Wiki軟件，每個Wiki軟件最多含有140個特征.我們利用頁面數(shù)據(jù)爬取技術(shù)獲取這些Wiki軟件及其包含的特征數(shù)據(jù).采用文獻[13]提出的特征模型抽取方法，在本課題組2位博士研究生和2位碩士研究生幫助下，過濾去掉狀態(tài)為正在編輯或特征不完全的Wiki，最終選取了92個Wiki軟件，每個軟件的特征數(shù)為130，在這組軟件對應(yīng)的特征模型中包括4個Mandatory特征、5個帶子特征的Optional特征、4組XOR關(guān)系、5組OR關(guān)系以及3組Requires關(guān)系.考慮到上述真實數(shù)據(jù)集的規(guī)模相對較小，我們進一步隨機生成了一組模擬軟件數(shù)據(jù)，包含3 000個軟件，每個軟件的特征數(shù)為100，采用與Wiki數(shù)據(jù)同樣的處理方法，在這組軟件對應(yīng)的特征模型中包括5個Mandatory特征、3個帶子特征的Optional特征、4組XOR關(guān)系、5組OR關(guān)系、4組Requires關(guān)系和3組Excludes關(guān)系.2組數(shù)據(jù)都是采用0-1矩陣形式進行存儲.

3.2評估指標(biāo)

本文使用準(zhǔn)確率以及運行時間作為方法有效性的評價參數(shù).其中，準(zhǔn)確率類似于推薦系統(tǒng)中的命中率hit-ratio[12]，即推薦的項目與測試集中的項目的交集除以推薦項目的總數(shù)，常常與命中排序hit-rank[12]一起使用，考慮推薦的項目在項目列表中的位置.本文使用的準(zhǔn)確率與推薦系統(tǒng)中的不同，不考慮命中排序，而只是考慮待開發(fā)軟件中預(yù)測正確的缺失特征值數(shù)與需要預(yù)測的缺失特征總數(shù)的比值，用式(3)表示：

(3)

其中，1≤j≤n，n表示特征集數(shù)目；pre表示預(yù)測值；real表示實際值，其他符號如前所述.precision=1表示本文預(yù)測方法能夠提供正確預(yù)測，而precision=0表示方法不能提供正確預(yù)測.

3.3實驗結(jié)果與分析

考慮到應(yīng)用場景及計算簡便性，對于第1組數(shù)據(jù)(簡稱Wiki數(shù)據(jù))，我們采取隨機抽取Wiki軟件作為待開發(fā)軟件，剩下的其他Wiki軟件作為歷史軟件數(shù)據(jù)，隨機重復(fù)實驗，每次實驗以不同的比率隨機將待開發(fā)軟件的特征值抽取出去設(shè)為缺失特征值(例如數(shù)據(jù)密度為10%表示隨機去除90%的特征值)，然后利用預(yù)測方法對其缺失的值進行預(yù)測.而對于第2組數(shù)據(jù)(簡稱Custom數(shù)據(jù))，為了消除數(shù)據(jù)敏感性，我們將數(shù)據(jù)分為3個子部分，隨機從其中某子部分抽取軟件隨機處理后作為待開發(fā)軟件，將另2個部分作為歷史軟件數(shù)據(jù)，然后采用與第1組數(shù)據(jù)類似的方法進行實驗.

實驗采用本文所提方法FM_KNN與KNN協(xié)同過濾算法以及文獻[8]中關(guān)聯(lián)規(guī)則的KNN方法AR_KNN進行比較，其中，AR_KNN最小支持度設(shè)為20%，最小信任度設(shè)為50%.共有3組實驗進行評估：第1組實驗是判斷待開發(fā)軟件的數(shù)據(jù)密度對預(yù)測準(zhǔn)確率的影響；第2組實驗是最近鄰相似軟件的數(shù)量對預(yù)測準(zhǔn)確率的影響；第3組是3種方法在不同數(shù)據(jù)密度下運行時間的比較.

實驗1. 待開發(fā)軟件數(shù)據(jù)密度對準(zhǔn)確率的影響.

待開發(fā)軟件的數(shù)據(jù)密度依次從10%以5%的步長逐步遞增到90%，Wiki數(shù)據(jù)每次計算重復(fù)實驗10次取平均值，Custom數(shù)據(jù)每次交叉計算重復(fù)實驗10次取平均值，2組數(shù)據(jù)下的實驗結(jié)果分別如圖6和圖7所示.

Fig. 6　Comparison of precision under different data density (Wiki data). (K=20)圖6　不同數(shù)據(jù)密度的預(yù)測準(zhǔn)確率比較(Wiki數(shù)據(jù)) (K=20)

Fig. 7　Comparison of precision under different data density (Custom data). (K=200)圖7　不同數(shù)據(jù)密度的預(yù)測準(zhǔn)確率比較(Custom數(shù)據(jù)) (K=200)

從圖6和圖7可以看出，3種方法都遠大于隨機方法的平均值50%，說明利用相似軟件的特征值來預(yù)測待開發(fā)軟件的特征值是可行的；隨著待開發(fā)軟件數(shù)據(jù)密度的增加，3種方法的預(yù)測準(zhǔn)確率呈線性增加，說明KNN預(yù)測隨著待開發(fā)軟件特征信息量的增加其預(yù)測性能不斷提高；當(dāng)數(shù)據(jù)密度比較低時，F(xiàn)M_KNN算法的準(zhǔn)確率比AR_KNN和KNN提高更加明顯，說明本文所提方法在待開發(fā)軟件特征描述數(shù)據(jù)稀疏性擴充方面優(yōu)勢更加明顯.

另外，AR_KNN的預(yù)測準(zhǔn)確率要優(yōu)于KNN，而 FM_KNN比KNN和AR_KNN的預(yù)測準(zhǔn)確率平均值都要高.Wiki數(shù)據(jù)下分別平均提升1.4%和0.62%，最高提升了2.15%和1.08%；Custom數(shù)據(jù)下，分別平均提升了4.43%和1.79%，最高提升了5.24%和2.94%；進一步說明擴充待開發(fā)軟件特征信息能夠提高預(yù)測準(zhǔn)確率，且FM_KNN算法充分考慮了軟件的領(lǐng)域知識，而比AR_KNN算法對待開發(fā)軟件特征信息的擴充更為充分.

實驗2. 最近鄰居數(shù)對準(zhǔn)確率的影響.

Wiki數(shù)據(jù)集選定數(shù)據(jù)密度為70%，鄰居數(shù)量依次從2以步長2逐步遞增到30，每次計算重復(fù)實驗10次取平均值；Custom數(shù)據(jù)集選定數(shù)據(jù)密度為70%，鄰居數(shù)量從20以20的步長遞增到300，每次交叉計算重復(fù)實驗10次取平均值.2組數(shù)據(jù)下的實驗結(jié)果分別如圖8和圖9所示.

Fig. 8　Comparison of precision under different neighbor number (Wiki data). (density=70%)圖8　不同鄰居數(shù)的預(yù)測準(zhǔn)確率比較(Wiki數(shù)據(jù)) 　　　(density=70%)

Fig. 9　Comparison of precision under different neighbor number (Custom data). (density=70%)圖9　不同鄰居數(shù)的預(yù)測準(zhǔn)確率比較(Custom數(shù)據(jù)) 　　　(density=70%)

從圖8和圖9可以看出，隨著鄰居數(shù)的增加預(yù)測準(zhǔn)確率逐漸提高，但是到了一定的臨界值(Wiki數(shù)據(jù)下大約為20，Custom數(shù)據(jù)下大約為220)之后預(yù)測準(zhǔn)確率不但不提高還有下降的趨勢，說明選擇合適的鄰居數(shù)量能取得較好的預(yù)測準(zhǔn)確率.另外，Wiki數(shù)據(jù)集下，3種方法的預(yù)測準(zhǔn)確率在75%～87%之間， FM_KNN比KNN，AR_KNN方法的預(yù)測準(zhǔn)確率平均值都要高，分別平均提升了1.51%和0.84%，最高分別提升了4.62%和1.43%；Custom數(shù)據(jù)集下，3種方法的預(yù)測準(zhǔn)確率在65%～78%之間，F(xiàn)M_KNN比KNN，AR_KNN的預(yù)測準(zhǔn)確率平均值要高，平均提升了3.85%和1.66%，最高提升了6%和2.58%.從而說明本文所提方法的有效性.

實驗3. 不同數(shù)據(jù)密度下運行時間比較.

本文驗證3種算法的運行時間，數(shù)據(jù)密度依次從10%以10%的步長逐步遞增到90%，Wiki數(shù)據(jù)集每次計算重復(fù)實驗10次取平均值，Custom數(shù)據(jù)每次交叉計算重復(fù)實驗10次取平均值，2組數(shù)據(jù)下的實驗結(jié)果分別如圖10和圖11所示.

Fig. 10　Comparison of execution time with different data density (Wiki data). (K=20)圖10　不同數(shù)據(jù)密度的運行時間比較(Wiki數(shù)據(jù)) (K=20)

Fig. 11　Comparison of execution time with different data density (Custom data).(K=200)圖11　不同數(shù)據(jù)密度的運行時間比較(Custom數(shù)據(jù)) (K=200)

從圖10和圖11可以看出，KNN所耗時間最少，F(xiàn)M_KNN次之，AR_KNN的所耗時間最長.對于Wiki數(shù)據(jù)，KNN，AR_KNN，F(xiàn)M_KNN方法在各種密度下的平均運行時間分別為25 ms，80.1 ms和26.4 ms；對于Custom數(shù)據(jù)，分別為84.6 ms，166 ms和89.5 ms.這是由于AR_KNN尋找頻繁項集，然后根據(jù)頻繁項集產(chǎn)生簡單關(guān)聯(lián)規(guī)則，需要不斷地掃描歷史軟件描述數(shù)據(jù);而FM_KNN雖然比KNN多了條件過濾步驟，但在條件過濾步驟中可能會補充一部分缺失特征值，這些值就不需要在后面的預(yù)測過程中進行預(yù)測，從而節(jié)省了時間，故FM_KNN和KNN算法的運行時間相差不大.

4　相關(guān)工作

為了幫助需求分析師、各利益相關(guān)者和客戶有效獲取待開發(fā)軟件需求，已有許多學(xué)者提出了各種軟件需求獲取技術(shù).金芝[2]提出了一種基于本體的需求獲取方法，利用企業(yè)本體和領(lǐng)域本體構(gòu)造軟件需求模型，指導(dǎo)軟件需求獲取.舒風(fēng)笛等人[3]提出一種用戶主導(dǎo)的需求獲取方法，為用戶提供領(lǐng)域需求資產(chǎn)推薦和對多用戶協(xié)同需求獲取的建議.王波等人[4]針對問題驅(qū)動的需求獲取方法提出了協(xié)同的問題分析與解決方法，并進行了實例研究.這些方法在軟件開發(fā)需求過程中能有效指導(dǎo)軟件需求獲取，減少需求過程中的工作負擔(dān)和錯誤風(fēng)險.我們課題組的前期研究提出一種面向服務(wù)的軟件需求建模框架RGPS[20]，即利用角色、目標(biāo)、流程和服務(wù)4個要素對服務(wù)需求進行建模，在體現(xiàn)領(lǐng)域共性需求的領(lǐng)域模型的基礎(chǔ)上對個性化需求進行定制建模從而指導(dǎo)軟件的需求獲取.Nguyen等人[21]提出了面向特征的Web服務(wù)定制方法，認為特征建模技術(shù)能提取用戶需求的可變性(即用戶的個性化需求)以簡化Web服務(wù)定制過程.

基于互聯(lián)網(wǎng)的軟件需要滿足大量地理位置各異、類型不同的客戶需求，這增加了需求獲取的困難；同時，互聯(lián)網(wǎng)上相似軟件眾多，這些具有大量相似功能的軟件為軟件需求獲取提供了新的途徑.為此，已有研究將推薦系統(tǒng)引入需求工程領(lǐng)域.Laurent等人[5]探索利用網(wǎng)上論壇的方式進行供應(yīng)商主導(dǎo)的開源項目需求工程任務(wù).Castro-Herrera等人[6-7]考慮使用推薦系統(tǒng)OPCI來支持推薦專家利益相關(guān)者和需求主題，并可選地支持管理實際的討論需求主題線程.這些方法能夠很好地指導(dǎo)需求組織者和分析師集思廣益，尋找到新的軟件需求，解決軟件的需求獲取問題，然而這些方法主要從軟件項目利益相關(guān)者的角度出發(fā)，沒有考慮利用互聯(lián)網(wǎng)上大量存在的已有軟件的領(lǐng)域知識.Hariri等人[8]使用數(shù)據(jù)挖掘(關(guān)聯(lián)規(guī)則挖掘)算法抽取在線產(chǎn)品描述的公共特征以及這些特征之間的關(guān)聯(lián)關(guān)系，然后使用KNN協(xié)同過濾算法為具有部分特征的新軟件產(chǎn)品推薦其缺失的特征，該方法考慮了需求之間的關(guān)聯(lián)關(guān)系，然而該方法的思路是求解當(dāng)一個特征出現(xiàn)時另一個特征出現(xiàn)的概率，反映的是特征之間的共現(xiàn)關(guān)系，未能考慮特征之間的多選多、多選一和互斥等其他關(guān)系，可能造成待開發(fā)軟件仍然難以擁有必需的初始特征作為特征推薦的基礎(chǔ)，從而影響缺失特征的預(yù)測準(zhǔn)確率.本文提出了一種基于特征模型和協(xié)同過濾的軟件需求獲取方法，通過考慮特征之間必選、可選、多選多、多選一、依賴和互斥等關(guān)系，為待開發(fā)軟件提供更多的初始特征，然后利用KNN協(xié)同過濾推薦系統(tǒng)推薦缺失特征.

5　結(jié)束語

針對軟件需求獲取過程中的復(fù)雜性和準(zhǔn)確性問題，借鑒本領(lǐng)域已有相似軟件的需求描述來預(yù)測和輔助獲取待開發(fā)軟件的需求為緩解這一復(fù)雜問題提供了一種新的思路.為了提高預(yù)測準(zhǔn)確率，本文提出了一種基于特征模型和協(xié)同過濾的軟件需求獲取方法，輔助軟件需求組織者和分析師進行軟件需求獲取.本文主要工作如下：提出了軟件需求獲取方法框架；引入了特征模型，利用特征模型的特征類型和特征之間的關(guān)聯(lián)關(guān)系為待開發(fā)軟件補充部分缺失特征信息作為推薦的基礎(chǔ).利用與待開發(fā)軟件同一領(lǐng)域內(nèi)已有歷史軟件數(shù)據(jù)，結(jié)合KNN協(xié)同過濾推薦系統(tǒng)，提出了軟件需求預(yù)測算法FM_KNN，為軟件需求預(yù)測和輔助獲取提供自動化或半自動化支持；分別在真實和仿真數(shù)據(jù)集上設(shè)計了具體實驗對軟件需求預(yù)測算法進行了驗證分析.下一步研究的工作主要包括：由于本文方法只能為待開發(fā)軟件推薦已有軟件特征列表中的特征，對于已有列表之外的新特征的推薦問題是值得研究的內(nèi)容之一；在軟件需求推薦過程中不同特征的重要性問題等也是值得進一步考慮的因素.

[1]Tiwari S, Rathore S S, Gupta A. Selecting requirement elicitation techniques for software projects[C]Proc of the 6th CSI Int Conf on Software Engineering (CONSEG). Piscataway, NJ: IEEE, 2012: 1-10[2]Jin Zhi. Ontology-based requirements elicitation[J]. Chinese Journal of Computers, 2000, 23(5): 486-492 (in Chinese)(金芝. 基于本體的自動需求獲取[J]. 計算機學(xué)報, 2000, 23(5): 486-492)[3]Shu Fengdi, Zhao Yuzhu, Wang Jizhe, et al. User-driven requirements elicitation method with the support of personalized domain knowledge [J], Journal of Computer Research and Development, 2007, 44(6): 1044-1052 (in Chinese)(舒風(fēng)笛, 趙玉柱, 王繼喆, 等. 個性化領(lǐng)域知識支持的用戶主導(dǎo)需求獲取方法[J]. 計算機研究與發(fā)展, 2007, 44(6): 1044-1052)[4]Wang Bo, Zhao Haiyan, Zhang Wei, et al. An approach to analyzing and resolving problems in the problem-driven requirements elicitation [J]. Journal of Computer Research and Development, 2013, 50(7): 1513-1523 (in Chinese)(王波, 趙海燕, 張偉, 等. 問題驅(qū)動的需求捕獲中問題分析與解決技術(shù)研究[J]. 計算機研究與發(fā)展, 2013, 50(7): 1513-1523)[5]Laurent P, Cleland-Huang J. Lessons learned from open source projects for facilitating online requirements processes[G]Requirements Engineering: Foundation for Software Quality. Berlin: Springer, 2009: 240-255[6]Castro-Herrera C, Cleland-Huang J, Mobasher B. Enhancing stakeholder profiles to improve recommendations in online requirements elicitation[C]Proc of the 17th IEEE Int Conf on Requirements Engineering. Piscataway, NJ: IEEE, 2009: 37-46[7]Castro-Herrera C, Duan C, Cleland-Huang J, et al. Using data mining and recommender systems to facilitate large-scale, open, and inclusive requirements elicitation processes[C]Proc of the 16th IEEE Int Conf on Requirements Engineering. Piscataway, NJ: IEEE, 2008: 165-168[8]Hariri N, Castro-Herrera H, Mirakhorli M, et al. Supporting domain analysis through mining and recommending features from online product listings[J]. IEEE Trans on Software Engineering, 2013, 39(12): 1736-1752[9]Zhang Wei, Mei Hong. Feature-oriented software reuse technology—state of the art[J]. Chinese Science Bulletin, 2014, 59(1): 21-42 (in Chinese)(張偉, 梅宏. 面向特征的軟件復(fù)用技術(shù)—發(fā)展與現(xiàn)狀[J]. 科學(xué)通報, 2014, 59(1): 21-42) [10]Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749[11]Deshpande M, Karypis G. Item-based top-nrecommendation algorithms[J]. ACM Trans on Information Systems, 2004, 22(1): 143-177[12]Herlocker J L, Konstan J A, Terveen L G, et al. Evaluating collaborative filtering recommender systems[J]. ACM Trans on Information Systems, 2004, 22(1): 5-53[13]Acher M, Cleve A, Perrouin G, et al. On extracting feature models from product descriptions[C]Proc of the 6th Int Workshop on Variability Modeling of Software-Intensive Systems. New York: ACM, 2012: 45-54[14]Benavides D, Segura S, Ruiz-Cortés A. Automated analysis of feature models 20 years later: A literature review[J]. Information Systems, 2010, 35(6): 615-636[15]Dumitru H, Gibiec M, Hariri N, et al. On-demand feature recommendations derived from mining public product descriptions[C]Proc of the 33rd Int Conf on Software Engineering (ICSE). Piscataway, NJ: IEEE, 2011: 181-190[16]Pazzani M J, Billsus D. Content-based recommendation systems[G]The Adaptive Web. Berlin: Springer, 2007: 325-341[17]Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009 (8): 30-37[18]Castro-Herrera C, Cleland-Huang J. Utilizing recommender systems to support software requirements elicitation[C]Proc of the 2nd Int Workshop on Recommendation Systems for Software Engineering. New York: ACM, 2010: 6-10[19]Zhang Jia, Wang Jian, Hung P, et al. Leveraging incrementally enriched domain knowledge to enhance service categorization[J]. International Journal of Web Services Research, 2012, 9(3): 43-66[20]He Keqing, Peng Rong, Liu Wei, et al. Networked Software[M]. Beijing: Science Press, 2008 (in Chinese)(何克清, 彭蓉, 劉瑋, 等. 網(wǎng)絡(luò)式軟件[M]. 北京: 科學(xué)出版社, 2008) [21]Nguyen T, Colman A. A feature-oriented approach for Web service customization[C]Proc of the 8th IEEE Int Conf on Web Services (ICWS). Piscataway, NJ: IEEE, 2010: 393-400

Peng Zhenlian, born in 1979. PhD candidate. Member of China Computer Federation. His current research interests include software engineering and service computing.

Wang Jian, born in 1980. PhD and lecturer. Member of China Computer Federation. His current research interests include software engineering and service computing.

He Keqing, born in 1947. PhD, professor and PhD supervisor. Senior member of China Computer Federation. His current research interests include software engineering and service computing.

Tang Mingdong, born in 1978. PhD and associate professor. Member of China Computer Federation. His current research interests include computer network and service computing.

A Requirements Elicitation Approach Based on Feature Model and Collaborative Filtering

Peng Zhenlian1, 2, Wang Jian1, He Keqing1, and Tang Mingdong2

1(StateKeyLaboratoryofSoftwareEngineering(WuhanUniversity),Wuhan430072)2(SchoolofComputerScienceandEngineering,HunanUniversityofScienceandTechnology,Xiangtan,Hunan411201)

With the rapid development of Internet and Web service related technologies，developing software system on Internet is increasingly popular. Software development is a multi-knowledge-intensive process in which requirements elicitation plays a key role. Software systems deployed on Internet need to meet the needs of various kinds of customers and users who are geographically distributed，which increases the difficulties of software requirements elicitation. Meanwhile，more and more software systems that share similar functions are deployed on Internet，which provides a new way to elicit software requirements. Toward this end，recommender systems have been leveraged in the requirements elicitation to recommend missing features for software products by comparing the requirements descriptions of existing similar software systems. In order to improve the prediction accuracy of the recommended features of the software system，a requirements elicitation approach based on feature model andKNN (K-nearest neighbors) collaborative filtering recommendation system is proposed in this paper. An algorithm named FM_KNN is presented by utilizing constraint relations between features inKNN collaborative filtering recommendation system. Experiments conducted on a real data set and a simulated data set, by comparing the proposed FM_KNN with two existing methods, i.e.,KNN and an approach that combines association rule mining withKNN, show that the proposed approach can achieve higher precision.

requirement elicitation; feature model; collaborative filtering; recommender system; feature recommendation

2015-06-01；

2015-12-16

國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2014CB340404)；國家自然科學(xué)基金項目(61373037，61202031，61572186，61562073)

王健(jianwang@whu.edu.cn)

TP311

This work was supported by the National Basic Research Program of China (973 Program)(2014CB340404) and the National Natural Science Foundation of China (61373037，61202031，61572186，61562073).