基于XML配置框架下多維度擴展貪心算法

匡珍春, 冼遠清

(廣東海洋大學 數學與計算機學院, 廣東 湛江 524088)

數據挖掘就是從海量數據中發現對用戶更重要的知識節點和概念模式, 以便利用數據中的規律更好地為用戶服務. 隨著互聯網的快速發展, WEB技術也得到廣泛應用. 合理有序的交換標準已成為當前網絡數據挖掘的重要需求之一[1]. XML作為一種不規則、 不固定、 可擴展的標記性語言, 適合應用于互聯網, 能輔助人們識別計算機語言. 特別是XML的規范日益標準化, 憑著自身讀取數據的廣泛化、 邏輯思維的明確化、 傳統數據結構化等特點, 在實際應用中成為眾多項目的首選. 本文基于XML配置框架, 對數據挖掘算法進行研究, 找到效率更高、 更精準的方法, 實現軟件的開發與優化.

1 XML原理

1.1 XML數據模型 XML是由描述性的半結構化[2]數據形成的、 可挖掘異構的數據源, 有繼承性. 通過一些規則集合組成的規范性語言XML Schema, 用XML-RL形式語義, 實現數據存儲與挖掘.

1.2 XML框架模型編程 XML配置框架主要由表示層、 業務層和持久層組成, 每層結構[3]通過STRUTS,SPRING和IBATIS等框架實現應用程序邏輯的正常運行, 如圖1所示.

圖1 XML配置框架編程模型Fig.1 Programming model of XML configuration framework

在表示層, 框架STRUTS按照相應配置文件的規定, 利用控制類將JSP頁面提交的訂單交給ACTION類, ACTION類會得到一個邏輯結果串, 控制類收到結果串后, 會將整個操作反應給JSP頁面, 實現實際應用. 在業務層, 框架SPRING[4]按照相應配置文件的規定, 利用控制類將表單提交給ACTION類, ACTION類會得到一個邏輯結果串[5], 控制類收到結果串后, 會將結果串和控制流的操作反應給JSP頁面, 實現實際應用. 在持久層, 框架IBATIS利用SQL語句, 自動進行對象的關系映射.

2 算法建立

為了提高軟件工程代碼開發中數據挖掘[6]的效率, 本文在時間和空間資源都有限的條件下, 通過對測試例進行優先排序, 先執行滿足限制條件的測試例, 及時發現系統缺陷, 縮短運行周期.

2.1 前提條件 假設AG[7]為測試例是否需要重新測試的標準,N表示測試例重新測試時被覆蓋更新的數量,K表示測試例重復測試時的次數,M表示在系統運行中涉及到的函數數量,T表示根據之前測試時間推測的執行時間. 在系統執行中, 重要程度如下：

N>K>M,

(1)

其中, AG值會隨著N的增大而增大.

2.2 貪心策略算法 考慮到測試點存在相同更新點的情況, 本文選取更多的更新點以更高的密度權重AG進行測試. 假設權重AG仍相同, 則改變函數總數, 實現在數量不同環境下的研究與分析.

本文采用大X方法對該算法中的多變量進行分析. 大X方法是將多因素統一到單一的度量衡, 便于計算機計算的研究方法.X是測試例中設置的、 比原有目標函數相關系數大的數值. 每個測試例均有一個X, 存在如下關系：

AG=N×X×X+K×X+M,

(2)

其中,X是所有測試例的平均值, 即

(3)

考慮到測試例優先排序過程中存在的時間限制問題, 本文引入時間參數, 建立新的算法如下：

PAG=(N×X×X+K×X+M)/T,

(4)

其中, PAG表示測試例中單元時間發現的缺陷價值, 且PAG值隨著測試價值的增加而增大.AG自身具有執行時間長、 整體運行易發現錯誤的特點. 而PAG是一次執行多個測試例, 執行時間短, 但發現錯誤較少. 二者的整體效果相同. 本文采用PAG優化算法.

圖2 測試例優選排序流程Fig.2 Flow chart of test cases optimal sorting

2.3 測試分析 圖2為測試例優選排序流程, 每個環節表示一個調用函數, 箭頭的方向表示環節與環節之間的調用順序[8], 其中: 實線箭頭表示較簡單的函數關系; 虛線箭頭表示較復雜的函數關系; 用環形標注出的環節表示在測試例進行排序過程中發生變更的節點[9].

設測試例為8個, 涉及類別為4個,X=100, 根據式(4)計算PAG值, 所得結果列于表1. 由表1可見,T8的計算結果與其他結果相差較大, 因此忽略該測試例. 綜合排序為

T6>T5>T2>T4>T3>T1>T7.

3 算法改進

為了解決貪心策略在測試過程中處理更新點時存在覆蓋效率較低的問題, 本文引進多維度的概念, 從時間和空間雙重角度考慮, 全面對貪心算法進行改進, 提出一種多維度擴展貪心策略[10].

假設操作過程中距離某步驟最近的變更節點為y,Y為運行中涉及到的所有節點集合. 節點在執行過程中存在的缺陷程度S(y)由低到高分別是L(S),M(S)和H(S), 則有

F(y)=(F(y)+S(Y))/2,

(6)

F(m)=∑F(yi),yi∈F,

(7)

其中：F(y)表示測試例在計算執行過程中發生的缺陷程度；F(m)表示測試例在執行過程中的危害.

考慮到上述研究中的信息反饋, 將S的取值設定為1,5,9, 則得到優化的PAG算法----多維度擴展貪心算法公式為

(8)

多維度貪心策略是考慮到多個因素, 實現測試例選擇的優化貪心算法, 其能發現已經存在及潛在的系統缺陷, 通過將測試例按照存在缺陷的程度排序, 逐級運行, 在受到影響的測試例集中發現數據挖掘的缺陷. 該算法包括隨意算法、 貪心算法、 升級貪心算法、 針對流算法(MAG)及優化針對流算法(CMAG)等方法. 不同方法對應的測試優選結果列于表2.

表2 測試優選結果

由表2可見, MAG算法先去掉測試例中涉及到的變更點, 再根據MAG值將具有數值最大的測試例加入到第一個數據集合, 第二大的加入到第二個數據集合, 以此類推, 直到所有數據都被分配到集合中為止. 因此, MAG和CMAG方法都具有可信度高、 執行快速和覆蓋全面等優點.

4 實驗結果分析

本文利用JAVA語言編程, 通過對600個數據分別進行3次認證, 即認證1、 認證2和認證3, 3次認證結果列于表3.

表3 3次認證結果統計

由表3可見： 在認證1中, 通過對158個數據進行測試, 得到35個錯誤； 經過改進, 在認證2中, 通過對168個數據進行測試, 得到15個錯誤； 再進行改進后, 在認證3中, 通過對168個數據進行測試, 得到錯誤為0. 因此, 通過對系統不斷地改進, 結果越來越精確.

圖3 AP誤差驗證Fig.3 AP error verification

XML框架下數據挖掘軟件工程發現測試缺陷的情況由系統平均錯誤發現率表示, 計算公式為

(9)

其中： AP表示系統平均錯誤發現率；Fn表示在F排序過程中第一次發現錯誤n的測試例.

圖3為AP誤差驗證結果. 由圖3可見, 隨著測試數據的增加, 到一定程度時, 發現的錯誤呈持平狀態, 即錯誤數據是有限的, 且在測試過程中會被完全發現. 本文方法在有限的時間內實現了數據缺陷的驗證, 因此, XML配置框架的數據挖掘算法是一種有效的方法.