吳金波 唐前進(jìn) 楊 明

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

0 引 言

隨著信息技術(shù)的飛速發(fā)展，人類進(jìn)入了大數(shù)據(jù)時(shí)代，來自商業(yè)、社會、科學(xué)、工程、醫(yī)療以及日常生活的大量數(shù)據(jù)在飛速產(chǎn)生并實(shí)現(xiàn)存儲。如何從如此巨量的、無序的、離散的數(shù)據(jù)中提取有效信息成為當(dāng)前計(jì)算機(jī)領(lǐng)域的研究熱點(diǎn)，促進(jìn)了大數(shù)據(jù)及數(shù)據(jù)挖掘技術(shù)的快速發(fā)展。

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

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

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

本文以數(shù)據(jù)挖掘算法中經(jīng)典的分類算法為例，對蛻變測試技術(shù)在分類算法中的應(yīng)用進(jìn)行深入研究。針對分類算法的特點(diǎn)，參考了文獻(xiàn)[3]和文獻(xiàn)[18]中描述的蛻變關(guān)系構(gòu)造的基本準(zhǔn)則，構(gòu)造了一系列蛻變關(guān)系(Metamorphic Relation,MR)，并在KNN算法應(yīng)用程序的正確性測評上進(jìn)行了實(shí)踐，對測評結(jié)果進(jìn)行了分析。

1 問題描述

1.1 蛻變測試綜述

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

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

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

(1)

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

由于程序p是實(shí)現(xiàn)算法f的應(yīng)用程序，若程序p是正確的，必然滿足：

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

(2)

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

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

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

1.2 分類算法

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

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

KNN算法步驟的描述如下：

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

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

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

KNN算法的關(guān)鍵問題是K值的選擇、距離的計(jì)算以及樣本的排序。

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

2.1 蛻變測試流程

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

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

(2) 研究被測程序的特點(diǎn)，構(gòu)造一組蛻變關(guān)系。

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

(4) 通過檢驗(yàn)蛻變用例的輸入在經(jīng)過被測程序的處理后得到的輸出是否滿足蛻變關(guān)系來確定被測程序是否存在錯(cuò)誤。

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

圖1 蛻變測試流程

2.2 蛻變關(guān)系構(gòu)造

為了便于蛻變關(guān)系的描述，針對KNN算法的特點(diǎn)，給出如下定義：

本文模型的主要目的是實(shí)現(xiàn)多節(jié)點(diǎn)間組成區(qū)域內(nèi)鏈路狀態(tài)的預(yù)測,但節(jié)點(diǎn)數(shù)的增加會導(dǎo)致局部區(qū)域鏈路狀態(tài)的復(fù)雜度呈指數(shù)倍上升,使得預(yù)測難度大大增加.為了探尋節(jié)點(diǎn)數(shù)和預(yù)測效果之間的關(guān)系,本次實(shí)驗(yàn)切片時(shí)長為320s,預(yù)測區(qū)域的節(jié)點(diǎn)數(shù)分別為:2、3、4,共進(jìn)行了30次預(yù)測,實(shí)驗(yàn)結(jié)果如圖12所示.

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

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

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

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

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

關(guān)于蛻變關(guān)系的構(gòu)造，文獻(xiàn)[3]表述了有效蛻變關(guān)系構(gòu)造的基本要求，即有效的蛻變關(guān)系應(yīng)能夠?qū)Ρ粶y程序的核心功能進(jìn)行有效測試，并對程序錯(cuò)誤具有較高的敏感性?；谝陨系幕疽?，文獻(xiàn)[18]對蛻變關(guān)系的構(gòu)造提出了更為明確的5個(gè)基本準(zhǔn)則。

基于以上參考文獻(xiàn)中描述的蛻變關(guān)系構(gòu)造的基本準(zhǔn)則，考慮到基于KNN算法的分類程序自身特點(diǎn)，構(gòu)造以下蛻變關(guān)系(設(shè)訓(xùn)練樣本集容量為n)。

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

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

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

MR5樣本亂序。若對訓(xùn)練樣本集中樣本的排列順序進(jìn)行隨機(jī)重排，則分類結(jié)果不變。

MR6無效屬性列增加。若對訓(xùn)練樣本集中的每一個(gè)樣本和待分類樣本增加屬性值相同的無效屬性列，則分類結(jié)果不變。

MR7-1全樣本復(fù)制。若對訓(xùn)練樣本集中的所有樣本都復(fù)制一次，使得訓(xùn)練樣本集容量由n變?yōu)?n，則分類結(jié)果不變。

MR7-2部分樣本復(fù)制。若在訓(xùn)練樣本集中將待分類樣本的最大相似類(樣本數(shù)為m)內(nèi)所有樣本均復(fù)制一次，使得訓(xùn)練樣本集容量由n變?yōu)閚+m，則分類結(jié)果不變。

MR8不相關(guān)類復(fù)制。若在訓(xùn)練樣本集中選擇待分類樣本的不相關(guān)類(樣本數(shù)為m)進(jìn)行一次復(fù)制，并按隨機(jī)順序插入到訓(xùn)練樣本集中，使得訓(xùn)練樣本容量由n變?yōu)閚+m，則分類結(jié)果不變。

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)程序

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

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

(3)

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

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

3.3 實(shí)驗(yàn)過程

本文采用如下的流程來對蛻變關(guān)系的有效性進(jìn)行評估。

(1) 數(shù)據(jù)準(zhǔn)備。待分類樣本集：從實(shí)驗(yàn)數(shù)據(jù)中隨機(jī)抽取10%的樣本，以及在每個(gè)屬性的取值范圍內(nèi)取隨機(jī)數(shù)生成待分類樣本。訓(xùn)練樣本集：實(shí)驗(yàn)數(shù)據(jù)中除待分類樣本以外的樣本組成訓(xùn)練數(shù)據(jù)集。

(2) 運(yùn)行分類程序得出分類結(jié)果，并統(tǒng)計(jì)“最大相似類平均相似度”和“相似類總數(shù)指標(biāo)”。

(3) 按照2.2節(jié)中所述的蛻變關(guān)系對訓(xùn)練數(shù)據(jù)集進(jìn)行處理，構(gòu)造蛻變用例。

(4) 以蛻變用例的輸入作為程序輸入，重新運(yùn)行分類程序，驗(yàn)證蛻變用例輸出是否與預(yù)期結(jié)果一致，并檢查各項(xiàng)分類指標(biāo)是否發(fā)生變化。

(5) 對分類結(jié)果和分類指標(biāo)的變化進(jìn)行分析，確認(rèn)每一條蛻變關(guān)系是否有效。

3.4 實(shí)驗(yàn)結(jié)果

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

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

(4)

定義11相似類總數(shù)。若待分類樣本集的樣本容量為n，設(shè)該樣本集中第i個(gè)樣本的相似類數(shù)量為ai，則當(dāng)前待分類樣本集的相似類總數(shù)定義為：

(5)

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

3.5 結(jié)果分析

由表1可以看出，原始用例經(jīng)過以上10種蛻變關(guān)系變換后的蛻變用例在“分類結(jié)果”這一指標(biāo)上都未發(fā)生變化，與預(yù)期的結(jié)果一致，說明分類程序在分類正確性上利用以上的蛻變關(guān)系未能發(fā)現(xiàn)錯(cuò)誤。在“最大相似類平均相似度”和“相似類總數(shù)”這兩個(gè)更為精細(xì)的指標(biāo)上，某些蛻變用例發(fā)生了變化。這些變化可能是程序隱含錯(cuò)誤導(dǎo)致的，也可能是另有原因，需要對程序?qū)崿F(xiàn)細(xì)節(jié)及蛻變關(guān)系本身進(jìn)行深入細(xì)致的分析。

MR1、MR2、MR3、MR4的所有指標(biāo)均未發(fā)生變化，與預(yù)期一致，不做討論。

MR5對訓(xùn)練樣本集進(jìn)行隨機(jī)亂序，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”和“相似類總數(shù)”兩個(gè)指標(biāo)均發(fā)生變化。通過對KNN分類程序源代碼分析可知，為提高程序運(yùn)行效率，距離差小于一定閾值，KNN分類程序不對訓(xùn)練樣本做基于距離的排序調(diào)整。因此，在極少數(shù)情況下，原始用例中K近鄰內(nèi)個(gè)別距離較遠(yuǎn)的樣本在蛻變用例中可能因?yàn)榕判騿栴}未入選K近鄰(稱為淘汰樣本)，而入選了其他樣本(稱為新入選樣本)。若新入選樣本為最大相似類中的樣本，則“最大相似類平均相似度”指標(biāo)提高；若新入選樣本不是最大相似類中的樣本且被淘汰樣本是最大相似類中的樣本，則“最大相似類平均相似度”指標(biāo)降低。MR5的“最大相似類平均相似度”指標(biāo)提高或降低不明確，因此該指標(biāo)表現(xiàn)為“變化”。進(jìn)而，在某些最大相似類不占絕對優(yōu)勢的情況下，可能引起分類結(jié)果發(fā)生變化。若新入選樣本入選K近鄰后，其所屬類由不相關(guān)類變?yōu)橄嗨祁?，則“相似類總數(shù)”指標(biāo)提高；若淘汰樣本被淘汰出K近鄰后，其所屬類由相似類變?yōu)椴幌嚓P(guān)類，則“相似類總數(shù)”指標(biāo)降低。MR5的“相似類總數(shù)”指標(biāo)提高或降低不明確，因此該指標(biāo)表現(xiàn)為“變化”。

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

MR7-1對訓(xùn)練樣本集進(jìn)行全樣本復(fù)制，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”指標(biāo)提高，“相似類總數(shù)”指標(biāo)降低。通過對KNN分類程序源代碼分析可知，若原始用例中入選K近鄰的最大相似類樣本數(shù)量為n，則對訓(xùn)練樣本集進(jìn)行復(fù)制以后，蛻變用例中入選K近鄰的最大相似類樣本數(shù)量將接近2n，顯然“最大相似類平均相似度”指標(biāo)在蛻變用例中會提高。由于最大相似類復(fù)制樣本對K近鄰的“填充”，導(dǎo)致入選K近鄰的非最大相似類樣本減少，使得某些類由相似類變?yōu)椴幌嚓P(guān)類，因此“相似類總數(shù)”指標(biāo)降低。

MR7-2對最大相似類內(nèi)的樣本進(jìn)行復(fù)制，形成蛻變用例，與原始用例相比，“最大相似類平均相似度”指標(biāo)提高、“相似類總數(shù)”指標(biāo)降低。引起指標(biāo)變化的原因與MR7-1基本一致。

MR8對不相關(guān)類內(nèi)的樣本進(jìn)行復(fù)制，并隨機(jī)插入到訓(xùn)練樣本集中，形成蛻變用例，與原始用例相比，“相似類總數(shù)”指標(biāo)發(fā)生了變化。引起指標(biāo)變化的原因與MR5相同，在極少數(shù)情況下，由于程序性能優(yōu)化和樣本排序問題在蛻變用例中引起不相關(guān)類和相似類變化，從而導(dǎo)致“相似類總數(shù)”指標(biāo)提高或降低。

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

3.6 實(shí)驗(yàn)結(jié)論

本文構(gòu)建的KNN分類程序經(jīng)過以上10種蛻變測試，有效的測試用例明顯增加，雖然未能發(fā)現(xiàn)程序錯(cuò)誤，但在程序的實(shí)現(xiàn)方式及分類規(guī)則的構(gòu)建上發(fā)現(xiàn)了可改進(jìn)空間。

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

(2) 對分類程序的性能優(yōu)化可能影響分類結(jié)果，因此在進(jìn)行程序性能優(yōu)化時(shí)在優(yōu)化方法及優(yōu)化閾值的合理性上需要進(jìn)行詳細(xì)的測試論證。

4 結(jié) 語

本文提出的基于蛻變關(guān)系的KNN分類程序測試方法，不僅能夠有效拓展測試用例集，達(dá)到核查程序正確性的目的，還能夠?qū)Τ绦虻膬?yōu)化起到一定的指導(dǎo)作用。以上基于蛻變關(guān)系的測試思路可以推廣到其他具備蛻變特性的數(shù)據(jù)挖掘程序測試上，在進(jìn)行具體的蛻變關(guān)系構(gòu)造時(shí)由測試專家和算法專家一起配合，分析數(shù)據(jù)挖掘算法的特點(diǎn)，識別蛻變關(guān)系，更全面地構(gòu)造有效的蛻變用例，緩解數(shù)據(jù)挖掘算法程序測試上的“Oracle”問題。