分類算法應用程序的蛻變測試方法研究

吳金波 唐前進 楊 明

(公安部第三研究所 上海 201204)

0 引 言

隨著信息技術的飛速發展，人類進入了大數據時代，來自商業、社會、科學、工程、醫療以及日常生活的大量數據在飛速產生并實現存儲。如何從如此巨量的、無序的、離散的數據中提取有效信息成為當前計算機領域的研究熱點，促進了大數據及數據挖掘技術的快速發展。

近年來，人工智能蓬勃發展，引起了數據挖掘技術的又一次革命，研究人員提出了一系列優秀的數據挖掘算法，并證明了這些算法的最優性能。然而，理論上的證明并不能保證算法實現(即數據挖掘應用程序)的正確性，因此針對數據挖掘應用程序進行正確性測評是必要的。

由于數據挖掘本身具有一定的“主觀色彩”，所以，數據挖掘應用程序在進行測評時很難找到預知的分析結果與程序輸出進行精確的對比，即存在所謂的“Oracle”問題[1]。它指的是，在對某些應用程序進行正確性測評過程中，由于很難構造預期輸出等原因而造成的無法確定程序輸出是否正確的問題。這是數據挖掘應用程序與普通應用程序在正確性測評方面存在的最重要區別，分類算法作為數據挖掘領域的常用算法，其應用程序測試同樣存在著“Oracle”問題。

為了解決該問題，香港中文大學的Chen等提出了蛻變測試[2-3]方法。該方法的核心思想是：對于為數較少的通過測試的正確用例，雖然沒有發現應用程序的錯誤[4]，但能夠以該用例為基礎，采用一定的蛻變策略構造新的測試用例(稱為蛻變用例)及預期輸出(稱為蛻變輸出)。通過檢查蛻變用例的程序輸出與蛻變輸出是否契合來更全面地檢測應用程序的正確性[5]。

本文以數據挖掘算法中經典的分類算法為例，對蛻變測試技術在分類算法中的應用進行深入研究。針對分類算法的特點，參考了文獻[3]和文獻[18]中描述的蛻變關系構造的基本準則，構造了一系列蛻變關系(Metamorphic Relation,MR)，并在KNN算法應用程序的正確性測評上進行了實踐，對測評結果進行了分析。

1 問題描述

1.1 蛻變測試綜述

蛻變測試以通過測試的正確用例為基礎，利用一定的變換規則來生成蛻變測試用例[2]，蛻變測試用例與原測試用例間的邏輯關系(稱為蛻變關系)可以確定蛻變測試用例的輸入在經過被測程序處理后得到的理論輸出(稱為蛻變輸出)，通過檢驗實際輸出與理論輸出是否一致來判斷程序的正確性[7-8]，從而實現更全面的應用程序正確性測試[6]。蛻變測試技術是緩解“Oracle”問題的有效途徑之一，其普適性較好[6]。蛻變測試的形式化描述如下。

定義1蛻變關系[2,5]。設算法f的實現程序為p，算法f有n個輸入i1，i2，…，in(n≥1)，函數輸出為o1，o2，…，om(m≥1)。若i1，i2，…，in之間滿足關系r，則o1，o2，…，om滿足關系rf，即：

r(i1,i2，…，in)?rf(o1,o2，…，om)

(1)

則稱(r,rf)是算法f的蛻變關系[3,6,8]。

由于程序p是實現算法f的應用程序，若程序p是正確的，必然滿足：

r(I1,I2，…，In)?rf(O1,O2，…，Om)

(2)

式中：I1，I2，…，In是程序p中對應于i1，i2，…，in的輸入，O1，O2，…，Om是程序輸出。顯然，在進行蛻變測試時，只需要檢測式(2)是否成立即可判斷被測程序的正確性。

定義2蛻變測試。利用蛻變關系進行的程序正確性測試稱為蛻變測試。蛻變測試是一種有效的軟件測試方法，在拓展程序正確性測試覆蓋面上能夠發揮重要作用[9-10]。

定義3原始用例和蛻變用例。利用其他測試方法生成，且用例中的輸入經過程序p的處理后得到的實際輸出與預期輸出一致的測試用例稱為原始用例。原始用例經過蛻變關系(r,rf)轉換得到的區別于原始用例的測試用例稱為原始用例基于(r,rf)的蛻變用例，簡稱為蛻變用例。

1.2 分類算法

在當今大數據時代，如何在海量、無序、離散的數據中獲取有用的信息成為了目前的研究熱點，而分類作為有效組織和管理數據的方法受到了廣泛關注。目前，較為流行的分類算法包括KNN[11]、決策樹[12]、SVM[13]、Native Bayes[14]以及基于深度學習的分類算法等，其中KNN算法以其實現簡單、魯棒性好等優點成為了數據挖掘領域的經典分類算法之一。本文將以KNN算法為具體實例開展針對分類算法的蛻變測試研究。

KNN算法又稱K最近鄰分類(K-Nearest Neighbor Classification)，是一種經典的模式識別算法，廣泛應用于機器學習領域[16]。其核心思想是在訓練樣本中找到與待分類樣本距離最近的K個樣本(稱為K近鄰)，根據K近鄰中最占優勢的類別來確定待分類樣本的類別。即：K個最近鄰樣本中哪個類別的樣本數量最多，則待分類樣本就屬于該類別[17]。

KNN算法步驟的描述如下：

第一步計算距離。分別計算待分類樣本與訓練樣本集中每一個樣本的距離(歐氏距離、馬氏距離以及余弦相似度等)。

第二步尋找最近鄰。將訓練樣本集按照第一步計算所得的距離進行排序，找到與待分類樣本距離最近的K個訓練樣本。

第三步確定分類。將待分類樣本確定為K近鄰中最占優勢的類別。

KNN算法的關鍵問題是K值的選擇、距離的計算以及樣本的排序。

2 分類程序的蛻變測試方法

2.1 蛻變測試流程

蛻變測試的一般流程如下：

(1) 利用其他方法獲得被測程序的原始用例，且原始用例的程序輸出與預期輸出完全一致。

(2) 研究被測程序的特點，構造一組蛻變關系。

(3) 利用蛻變關系，基于原始用例生成蛻變用例。

(4) 通過檢驗蛻變用例的輸入在經過被測程序的處理后得到的輸出是否滿足蛻變關系來確定被測程序是否存在錯誤。

在蛻變測試自動化方面，Gotlieb等[15]提出了自動蛻變測試的框架。蛻變測試的一般流程如圖1所示。

圖1 蛻變測試流程

2.2 蛻變關系構造

為了便于蛻變關系的描述，針對KNN算法的特點，給出如下定義：

本文模型的主要目的是實現多節點間組成區域內鏈路狀態的預測,但節點數的增加會導致局部區域鏈路狀態的復雜度呈指數倍上升,使得預測難度大大增加.為了探尋節點數和預測效果之間的關系,本次實驗切片時長為320s,預測區域的節點數分別為:2、3、4,共進行了30次預測,實驗結果如圖12所示.

定義5相似類。若待分類樣本相對于類型C的類型相似度大于0，則類型C稱為待分類樣本的相似類。

定義6最大相似類。待分類樣本的所有相似類中，若類型C的類型相似度最大，則類型C稱為待分類樣本的最大相似類。顯然，最大相似類就是利用KNN算法得到的分類結果。

定義7最小相似類。待分類樣本的所有相似類中，若類型C的類型相似度最小，則類型C稱為待分類樣本的最小相似類。

定義8完全隸屬類。若待分類樣本相對于類型C的類型相似度為1，則類型C稱為待分類樣本的完全隸屬類。

定義9不相關類。若待分類樣本相對于類型C的類型相似度為0，則類型C稱為待分類樣本的不相關類。

關于蛻變關系的構造，文獻[3]表述了有效蛻變關系構造的基本要求，即有效的蛻變關系應能夠對被測程序的核心功能進行有效測試，并對程序錯誤具有較高的敏感性。基于以上的基本要求，文獻[18]對蛻變關系的構造提出了更為明確的5個基本準則。

基于以上參考文獻中描述的蛻變關系構造的基本準則，考慮到基于KNN算法的分類程序自身特點，構造以下蛻變關系(設訓練樣本集容量為n)。

MR1線性平移。若對訓練樣本集中每一個樣本的每一個屬性值xi均做線性平移f(xi)=xi+bi,bi≠0，并且對待分類樣本的每一個屬性值做完全一致的線性平移，則分類結果不變。

MR2等比例縮放。若對訓練樣本集中每一個樣本的每一個屬性值xi均做等比例縮放f(xi)=axi,a>0，并且對待分類樣本的每一個屬性值做完全一致的等比例縮放，則分類結果不變。

MR4屬性列置換。若對訓練樣本集中每一個樣本及待分類樣本的任意兩個屬性列ci、cj做置換操作，則分類結果不變。

MR5樣本亂序。若對訓練樣本集中樣本的排列順序進行隨機重排，則分類結果不變。

MR6無效屬性列增加。若對訓練樣本集中的每一個樣本和待分類樣本增加屬性值相同的無效屬性列，則分類結果不變。

MR7-1全樣本復制。若對訓練樣本集中的所有樣本都復制一次，使得訓練樣本集容量由n變為2n，則分類結果不變。

MR7-2部分樣本復制。若在訓練樣本集中將待分類樣本的最大相似類(樣本數為m)內所有樣本均復制一次，使得訓練樣本集容量由n變為n+m，則分類結果不變。

MR8不相關類復制。若在訓練樣本集中選擇待分類樣本的不相關類(樣本數為m)進行一次復制，并按隨機順序插入到訓練樣本集中，使得訓練樣本容量由n變為n+m，則分類結果不變。

MR9最小相似類去除。若在訓練樣本集中選擇待分類樣本的最小相似類(樣本數為m)，將該類的樣本從訓練樣本集中去除，使得訓練樣本容量由n變為n-m，則分類結果不變。

3 實 驗

3.1 實驗程序

為了對以上的蛻變關系的有效性進行驗證，本文選擇了最有具代表性的歐氏距離作為距離度量方法，基于C++語言編寫了基于KNN算法的分類程序。

設n維向量空間中存在數據集D，樣本點X(x1,x2,…,xn)和Y(y1,y2,…,yn)的歐氏距離do定義為：

(3)

歐氏距離能夠表征兩個樣本點的整體距離(不相似性)，是分類算法中最常用的距離度量方法。其缺點是將不同向量元素同等對待，在各向量元素的量綱不相同的情況下可能導致距離度量偏離實際情況，因此在本文的分類程序中首先對訓練樣本和待分類樣本進行了歸一化處理。

3.2 實驗數據

本文選取文獻[19]中的約會網站數據集作為實驗數據集。該數據集內有1 000個樣本，每一個樣本包含3個元素:每年的飛行里程數,玩視頻游戲所占時間比,每周消費的冰淇淋(L)。通過3個元素將約會對象分為不喜歡的人、魅力一般的人和極具魅力的人。

3.3 實驗過程

本文采用如下的流程來對蛻變關系的有效性進行評估。

(1) 數據準備。待分類樣本集：從實驗數據中隨機抽取10%的樣本，以及在每個屬性的取值范圍內取隨機數生成待分類樣本。訓練樣本集：實驗數據中除待分類樣本以外的樣本組成訓練數據集。

(2) 運行分類程序得出分類結果，并統計“最大相似類平均相似度”和“相似類總數指標”。

(3) 按照2.2節中所述的蛻變關系對訓練數據集進行處理，構造蛻變用例。

(4) 以蛻變用例的輸入作為程序輸入，重新運行分類程序，驗證蛻變用例輸出是否與預期結果一致，并檢查各項分類指標是否發生變化。

(5) 對分類結果和分類指標的變化進行分析，確認每一條蛻變關系是否有效。

3.4 實驗結果

首先給出本文用于評估蛻變測試效果的指標定義：分類結果、最大相似類平均相似度以及相似類總數。分類結果定義見定義6。

定義10最大相似類平均相似度。若待分類樣本集的樣本容量為n，設該樣本集中第i個樣本的最大相似類相似度為si，則當前待分類樣本集的最大相似類平均相似度定義為：

(4)

定義11相似類總數。若待分類樣本集的樣本容量為n，設該樣本集中第i個樣本的相似類數量為ai，則當前待分類樣本集的相似類總數定義為：

(5)

表1匯總了實驗結果，顯示了原始用例與蛻變用例基于“分類結果”、“最大相似類平均相似度”以及“相似類總數”三個指標的對比結論。當原始用例和蛻變用例輸出的指標一致時，則表中填入“不變”；當原始用例和蛻變用例輸出的指標不一致，且指標值無法確定增大或減小，則表中填入“變化”；當原始用例和蛻變用例輸出的指標不一致，且指標值確定增大，則表中填入“提高”；當原始用例和蛻變用例輸出的指標不一致，且指標值確定減小，則表中填入“降低”。

3.5 結果分析

由表1可以看出，原始用例經過以上10種蛻變關系變換后的蛻變用例在“分類結果”這一指標上都未發生變化，與預期的結果一致，說明分類程序在分類正確性上利用以上的蛻變關系未能發現錯誤。在“最大相似類平均相似度”和“相似類總數”這兩個更為精細的指標上，某些蛻變用例發生了變化。這些變化可能是程序隱含錯誤導致的，也可能是另有原因，需要對程序實現細節及蛻變關系本身進行深入細致的分析。

MR1、MR2、MR3、MR4的所有指標均未發生變化，與預期一致，不做討論。

MR5對訓練樣本集進行隨機亂序，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”和“相似類總數”兩個指標均發生變化。通過對KNN分類程序源代碼分析可知，為提高程序運行效率，距離差小于一定閾值，KNN分類程序不對訓練樣本做基于距離的排序調整。因此，在極少數情況下，原始用例中K近鄰內個別距離較遠的樣本在蛻變用例中可能因為排序問題未入選K近鄰(稱為淘汰樣本)，而入選了其他樣本(稱為新入選樣本)。若新入選樣本為最大相似類中的樣本，則“最大相似類平均相似度”指標提高；若新入選樣本不是最大相似類中的樣本且被淘汰樣本是最大相似類中的樣本，則“最大相似類平均相似度”指標降低。MR5的“最大相似類平均相似度”指標提高或降低不明確，因此該指標表現為“變化”。進而，在某些最大相似類不占絕對優勢的情況下，可能引起分類結果發生變化。若新入選樣本入選K近鄰后，其所屬類由不相關類變為相似類，則“相似類總數”指標提高；若淘汰樣本被淘汰出K近鄰后，其所屬類由相似類變為不相關類，則“相似類總數”指標降低。MR5的“相似類總數”指標提高或降低不明確，因此該指標表現為“變化”。

MR6增加值相同的無效屬性列，所有指標均未發生變化，與預期一致。若增加的無效屬性采用不同的賦值(隨機值)，則可能對分類結果帶來不可預知的變化。由此可以得出結論，在進行分類計算時，非關鍵屬性的引入可能對分類結果的正確性帶來嚴重的負面影響。

MR7-1對訓練樣本集進行全樣本復制，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”指標提高，“相似類總數”指標降低。通過對KNN分類程序源代碼分析可知，若原始用例中入選K近鄰的最大相似類樣本數量為n，則對訓練樣本集進行復制以后，蛻變用例中入選K近鄰的最大相似類樣本數量將接近2n，顯然“最大相似類平均相似度”指標在蛻變用例中會提高。由于最大相似類復制樣本對K近鄰的“填充”，導致入選K近鄰的非最大相似類樣本減少，使得某些類由相似類變為不相關類，因此“相似類總數”指標降低。

MR7-2對最大相似類內的樣本進行復制，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”指標提高、“相似類總數”指標降低。引起指標變化的原因與MR7-1基本一致。

MR8對不相關類內的樣本進行復制，并隨機插入到訓練樣本集中，形成蛻變用例，與原始用例相比，“相似類總數”指標發生了變化。引起指標變化的原因與MR5相同，在極少數情況下，由于程序性能優化和樣本排序問題在蛻變用例中引起不相關類和相似類變化，從而導致“相似類總數”指標提高或降低。

MR9從訓練樣本中去除最小相似類，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”指標提高，“相似類總數”指標變化。通過對KNN分類程序源代碼分析可知，最小相似類的樣本去除后，必然會有新的樣本入選待分類樣本的K近鄰，用以填補去除最小相似類樣本后的“空白”，新入選K近鄰的樣本若屬于最大相似類，則“最大相似類平均相似度”指標提高。若新入選K近鄰的樣本全部屬于最大相似類，則“相似類總數”指標可能降低；若新入選K近鄰的樣本屬于2個以上不相關類，則“相似類總數”指標可能提高。因此，“相似類總數”指標表現為“變化”。

3.6 實驗結論

本文構建的KNN分類程序經過以上10種蛻變測試，有效的測試用例明顯增加，雖然未能發現程序錯誤，但在程序的實現方式及分類規則的構建上發現了可改進空間。

(1) 參與分類的樣本屬性需要經過慎重的篩選，非關鍵屬性的引入可能影響分類結果的正確性。

(2) 對分類程序的性能優化可能影響分類結果，因此在進行程序性能優化時在優化方法及優化閾值的合理性上需要進行詳細的測試論證。

4 結 語

本文提出的基于蛻變關系的KNN分類程序測試方法，不僅能夠有效拓展測試用例集，達到核查程序正確性的目的，還能夠對程序的優化起到一定的指導作用。以上基于蛻變關系的測試思路可以推廣到其他具備蛻變特性的數據挖掘程序測試上，在進行具體的蛻變關系構造時由測試專家和算法專家一起配合，分析數據挖掘算法的特點，識別蛻變關系，更全面地構造有效的蛻變用例，緩解數據挖掘算法程序測試上的“Oracle”問題。