寧一璇

(浙江理工大學(xué) 信息學(xué)院，杭州311121)

0 引 言

近年來，人工智能與機(jī)器學(xué)習(xí)技術(shù)已經(jīng)越來越成熟，已經(jīng)滲透到人們生活的方方面面。例如，圖像識(shí)別、無人駕駛等領(lǐng)域。伴隨著智能技術(shù)的發(fā)展，人們對(duì)于機(jī)器學(xué)習(xí)程序高質(zhì)量的需求日益增加，但現(xiàn)階段對(duì)機(jī)器學(xué)習(xí)算法的分析與理解不足，并且傳統(tǒng)的軟件測(cè)試方法和評(píng)價(jià)標(biāo)準(zhǔn)也并不適用機(jī)器學(xué)習(xí)算法［1］。如何分析機(jī)器學(xué)習(xí)算法，已成為亟待解決的問題。

目前對(duì)機(jī)器學(xué)習(xí)進(jìn)行質(zhì)量分析，主要集中在以下幾種方法:

（1）提高數(shù)據(jù)集質(zhì)量。如Chakarov等人［2］提出PSI工具。認(rèn)為對(duì)于分類任務(wù)，訓(xùn)練集中的錯(cuò)誤會(huì)導(dǎo)致大量的分類錯(cuò)誤。

（2）測(cè)試訓(xùn)練好的模型。如Groce等［3］提出了WYSIWYT／ML框架，幫助終端用戶測(cè)試機(jī)器學(xué)習(xí)系統(tǒng)。

（3）利用蛻變測(cè)試方法，來測(cè)試機(jī)器學(xué)習(xí)程序代碼。如Xie等人［4］嘗試用蛻變測(cè)試來進(jìn)行機(jī)器學(xué)習(xí)程序的測(cè)試。但從算法上對(duì)機(jī)器學(xué)習(xí)進(jìn)行質(zhì)量分析的研究甚少。

程序不變量常被用于追蹤軟件缺陷［5］、硬件錯(cuò)誤［6］和軟件評(píng)估［7］。在程序運(yùn)行時(shí)，能夠反映程序代碼在整個(gè)運(yùn)行過程中，具有不變性質(zhì)的邏輯斷言。不僅如此，還可以反映程序數(shù)據(jù)結(jié)構(gòu)等各方面的信息，在程序的設(shè)計(jì)、測(cè)試等各方面都發(fā)揮著巨大的作用［8］。因此，可以將程序不變量用于機(jī)器學(xué)習(xí)算法的質(zhì)量分析。

基于此，本文提出了基于不變量的機(jī)器學(xué)習(xí)算法分析。該分析方法將程序不變量與關(guān)鍵變量篩選提取方法相結(jié)合，通過對(duì)不同參數(shù)輸入下的機(jī)器學(xué)習(xí)算法進(jìn)行程序不變量的生成，然后對(duì)生成得到的不變量集合進(jìn)行關(guān)鍵變量的提取，進(jìn)而對(duì)機(jī)器學(xué)習(xí)算法進(jìn)行分析。本文使用5種機(jī)器學(xué)習(xí)算法作為示例算法，并對(duì)每個(gè)示例算法選取一種對(duì)算法性能產(chǎn)生影響的參數(shù)作為輸入。實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以從算法內(nèi)部的屬性特點(diǎn)，分析機(jī)器學(xué)習(xí)算法的參數(shù)設(shè)置對(duì)算法準(zhǔn)確率的影響。

1 方法概述

1.1 問題描述

通常的軟件測(cè)試方法，是通過執(zhí)行測(cè)試用例集來發(fā)現(xiàn)程序源代碼中的錯(cuò)誤。但機(jī)器學(xué)習(xí)算法與普通的代碼不同，其輸出是沒有對(duì)錯(cuò)之分的，只有一個(gè)更適合于某個(gè)問題（數(shù)據(jù)集）的模型。機(jī)器學(xué)習(xí)算法的好壞程度，需要從正確率、時(shí)間空間復(fù)雜度以及數(shù)據(jù)集大小對(duì)算法效率的影響等幾個(gè)方面去比較分析［9］。若要保證算法結(jié)果的正確性，最重要的是:算法推導(dǎo)的正確性、算法效果的正確性以及算法應(yīng)用的正確性?？偠灾?，僅用軟件測(cè)試的方法考慮機(jī)器學(xué)習(xí)是不充分的，應(yīng)該從統(tǒng)計(jì)理論的角度，去分析一個(gè)機(jī)器學(xué)習(xí)算法是否優(yōu)秀，是否有足夠高的正確率。

軟件分析技術(shù)可以應(yīng)用在開發(fā)階段、維護(hù)階段以及復(fù)用階段。文獻(xiàn)［10］中，將軟件分析定義為:對(duì)軟件進(jìn)行人工或者自動(dòng)分析，以驗(yàn)證、確認(rèn)或發(fā)現(xiàn)軟件性質(zhì)（或規(guī)約、約束）的過程或活動(dòng)。軟件分析技術(shù)分為靜態(tài)分析與動(dòng)態(tài)分析技術(shù)。

靜態(tài)與動(dòng)態(tài)分析技術(shù)的一個(gè)基本過程如圖1所示。

圖1 靜態(tài)分析與動(dòng)態(tài)分析的基本過程Fig.1 The basic process of static analysis and dynamic analysis

在軟件分析技術(shù)中，程序不變量檢測(cè)技術(shù)是一種將靜態(tài)分析和動(dòng)態(tài)監(jiān)測(cè)相結(jié)合的有效分析方法。程序不變量是影響軟件質(zhì)量的要素之一，其在程序運(yùn)行的整個(gè)過程中，反映了程序代碼具有不變性質(zhì)的邏輯語句。不但能表現(xiàn)代碼的各種屬性特點(diǎn)，還能夠反映程序數(shù)據(jù)結(jié)構(gòu)等各方面的信息［10］。

在程序開發(fā)過程中，程序不變量檢測(cè)技術(shù)已經(jīng)開始被人們廣泛應(yīng)用。程序不變量可以作為斷言插入到程序中，保證程序在進(jìn)一步測(cè)試時(shí)隨著代碼的變化不被改變；可以過濾失效測(cè)試用例、驗(yàn)證并改進(jìn)測(cè)試套件、檢測(cè)軟件缺陷并對(duì)軟件進(jìn)行精確的錯(cuò)誤定位；可以檢測(cè)程序是否發(fā)生并發(fā)錯(cuò)誤［11，14］等等。

因此，對(duì)于機(jī)器學(xué)習(xí)算法來說，可以應(yīng)用程序不變量檢測(cè)技術(shù)，從算法內(nèi)部的邏輯屬性，來分析機(jī)器學(xué)習(xí)算法是否擁有足夠高的正確率。

1.2 方法提出

本文方法的實(shí)現(xiàn)步驟以及工作流程如圖2所示。其中最重要的2個(gè)步驟分別是生成不變量與關(guān)鍵變量篩選。

圖2 基于不變量的機(jī)器學(xué)習(xí)算法分析流程圖Fig.2 The flow chart of machine learning algorithm analysis based on invariants

1.2.1 Daikon生成不變量

Daikon［13］是一個(gè)應(yīng)用十分廣泛的不變量生成工具，其通過程序的動(dòng)態(tài)運(yùn)行來產(chǎn)生可能的不變量，可以對(duì)Java、C和C++等程序語言生成程序不變量。其產(chǎn)生不變量的過程如圖3所示。

圖3 Daikon處理流程圖Fig.3 Daikon processing flowchart

Daikon利用機(jī)器學(xué)習(xí)的原理，使用前端對(duì)程序注入特定的程序監(jiān)測(cè)點(diǎn)，動(dòng)態(tài)分析運(yùn)行程序后，得到相應(yīng)的數(shù)據(jù)軌跡文件（數(shù)據(jù)軌跡即為變量的行為，它反映了程序變量之間的關(guān)系），分析數(shù)據(jù)軌跡文件便能得到程序不變量。例如，本文使用一個(gè)名為Kvasir的前端對(duì)c++機(jī)器學(xué)習(xí)代碼生成數(shù)據(jù)軌跡文件，然后Daikon對(duì)數(shù)據(jù)軌跡文件進(jìn)行處理，從數(shù)據(jù)軌跡文件中動(dòng)態(tài)提取似然不變量，這些似然不變量在程序的某一或幾個(gè)特定的程序監(jiān)測(cè)點(diǎn)上保持成立［11-14］。

1.2.2 關(guān)鍵變量篩選

盡管程序不變量是觀察代碼內(nèi)部邏輯關(guān)系、檢測(cè)錯(cuò)誤的有效方法，但由于機(jī)器學(xué)習(xí)算法是智能算法，運(yùn)行時(shí)需要巨大的開銷，且其中產(chǎn)生的不變量過于龐大，而對(duì)系統(tǒng)中每個(gè)變量的監(jiān)控是不必要的。基于此，本文提出了對(duì)關(guān)鍵變量進(jìn)行篩選。在關(guān)鍵變量篩選階段，首先采用動(dòng)態(tài)過濾機(jī)制Ⅰ和動(dòng)態(tài)過濾機(jī)制Ⅱ，對(duì)成功執(zhí)行程序后得到的所有變量進(jìn)行過濾，得到一個(gè)關(guān)鍵變量集合［15］；然后使用靜態(tài)約簡(jiǎn)機(jī)制，對(duì)關(guān)鍵變量集合進(jìn)行進(jìn)一步的約簡(jiǎn)；最后從約簡(jiǎn)的關(guān)鍵變量集合中，手動(dòng)對(duì)算法正確性產(chǎn)生最大影響的關(guān)鍵變量提取。

1.2.2.1 動(dòng)態(tài)過濾機(jī)制Ⅰ

動(dòng)態(tài)過濾機(jī)制Ⅰ可以過濾第一類非關(guān)鍵變量。在程序分析階段，這類非關(guān)鍵變量并不會(huì)隨著參數(shù)的改變，對(duì)程序的結(jié)果產(chǎn)生關(guān)鍵的影響，因此不需要被監(jiān)控。文中使用增量△來表示變量值的增加或減少。△是通過當(dāng)前觀察值減去上一次的觀察值來獲得的［16］，如式（1）、式（2）所示。

△:＝CurrentValue-LastValue if LastValue≠?，（1）

△:＝0if LastValue＝?.（2）

動(dòng)態(tài)過濾機(jī)制Ⅰ可以過濾掉第一類非關(guān)鍵變量，并將篩選出的關(guān)鍵變量?jī)?chǔ)存到集合KEY1中。動(dòng)態(tài)過濾機(jī)制Ⅰ在訓(xùn)練階段的處理過程如下:

（1）當(dāng)觀察到第一個(gè)值Obersvation1時(shí)，給△賦值為0，最后一個(gè)值Last＿Observation更新為第一個(gè)值Obersvation1。

（2）在 下 一 次 觀 察 時(shí)，將 新 觀 察 到 的 值Obersvation2和最后一個(gè)值Last＿Observation之差更新為△。

（3）每次觀察后，生成一個(gè)更新的△（△2），并將其與當(dāng)前△進(jìn)行比較。若新△等于當(dāng)前的△，則繼續(xù)進(jìn)行判斷，否則將保存一個(gè)false標(biāo)志，并將該變量的信息儲(chǔ)存到集合KEY1中。

（4）退出訓(xùn)練過程，并返回關(guān)鍵變量集合KEY1。

1.2.2.2 動(dòng)態(tài)過濾機(jī)制Ⅱ

使用動(dòng)態(tài)過濾機(jī)制Ⅱ的目的，是從關(guān)鍵變量集合KEY1中再次過濾掉對(duì)算法的結(jié)果不產(chǎn)生影響、不需要被監(jiān)控的非關(guān)鍵變量。動(dòng)態(tài)過濾機(jī)制Ⅱ從關(guān)鍵變量集合KEY1中過濾掉這類非關(guān)鍵變量后，將剩余的關(guān)鍵變量?jī)?chǔ)存到新的關(guān)鍵變量集合KEY2中。動(dòng)態(tài)過濾機(jī)制Ⅱ在訓(xùn)練階段的處理過程如下:

（1）在程序第一次執(zhí)行期間，范圍不變量Range＿Invariable會(huì)隨著給定變量的每次觀察而不斷更新，并將其范圍賦值給最新的Last＿Range＿Invariable。

（2）在下一次成功執(zhí)行后，得到新的范圍不變量觀察值Range＿Invariable。判斷新的Range＿Invariable是否在上一次執(zhí)行得到的Last＿Range＿Invariable范圍內(nèi)。若在范圍內(nèi)，則繼續(xù)進(jìn)行下一次執(zhí)行；否則保存一個(gè)false標(biāo)志，并將該變量的信息儲(chǔ)存到集合KEY2中。

（3）退出訓(xùn)練，并得到一個(gè)更新的關(guān)鍵變量集合KEY2。

1.2.2.3 靜態(tài)約簡(jiǎn)機(jī)制

靜態(tài)約簡(jiǎn)機(jī)制是通過分析函數(shù)之間的調(diào)用關(guān)系，對(duì)KEY2集合中的關(guān)鍵變量進(jìn)一步的過濾約簡(jiǎn)，并得到新的關(guān)鍵變量集合KEY3。

函數(shù)調(diào)用圖可以描述一個(gè)程序中各個(gè)函數(shù)之間的調(diào)用關(guān)系［17］。一般來說，函數(shù)調(diào)用圖可以分為靜態(tài)函數(shù)調(diào)用圖和動(dòng)態(tài)函數(shù)調(diào)用圖兩類，靜態(tài)函數(shù)調(diào)用圖展示了程序在不運(yùn)行狀態(tài)下的函數(shù)調(diào)用情況，而動(dòng)態(tài)函數(shù)調(diào)用圖記錄了程序運(yùn)行時(shí)的函數(shù)調(diào)用情況。在本文中，使用工具Cflow和Graphviz，構(gòu)建靜態(tài)函數(shù)調(diào)用圖。例如，本文利用遺傳算法，解決TSP問題的tsp.cpp程序的靜態(tài)函數(shù)調(diào)用圖如圖4所示。

圖4 GA-tsp.cpp程序的函數(shù)調(diào)用圖Fig.4 Function call graph of GA-tsp.cpp program

1.2.2.4 關(guān)鍵變量提取

使用2個(gè)動(dòng)態(tài)過濾機(jī)制和靜態(tài)約簡(jiǎn)機(jī)制對(duì)程序中的變量進(jìn)行過濾后，得到了一個(gè)關(guān)鍵變量集合KEY3。通過運(yùn)行程序，調(diào)整程序運(yùn)行時(shí)的輸入?yún)?shù)。在KEY3中發(fā)現(xiàn)，隨著參數(shù)的改變，將有一個(gè)變量會(huì)產(chǎn)生明顯的變化，而這個(gè)變量在程序中也與歐氏距離有著直接的關(guān)系，則定義這個(gè)變量為關(guān)鍵變量，并對(duì)其進(jìn)行提取分析。

2 實(shí)驗(yàn)與分析

實(shí)驗(yàn)中共有5個(gè)機(jī)器算法程序，見表1。

表1 5種機(jī)器學(xué)習(xí)算法參數(shù)表Tab.1 5 machine learning algorithms

其中，Key＿N表示每個(gè)程序關(guān)鍵變量集合中關(guān)鍵變量的個(gè)數(shù)；Para＿N表示每個(gè)程序所取參數(shù)的個(gè)數(shù)；Run＿N表示每個(gè)參數(shù)運(yùn)行次數(shù)。

2.1 遺傳算法

本文使用的第一個(gè)程序，是用遺傳算法求解TSP問題（Traveling Salesman Problem，旅行商問題）。

旅行商問題（TSP）是引起數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家廣泛關(guān)注的一個(gè)問題，特別是因?yàn)槠涿枋銎饋砑热菀子蛛y以解決。問題簡(jiǎn)單地表述為:如果一個(gè)旅行推銷員希望一次訪問m個(gè)城市列表中的每個(gè)城市一次（從i到j(luò)的旅行成本為cij），然后返回家鄉(xiāng)，那么旅行推銷員如何選擇最短的路徑［18］。

以規(guī)模較小的城市為例（這里取14個(gè)）。其中，種群數(shù)目sizepop＝100；交叉概率pc＝0.8；變異概率pm＝0.02；染色體長(zhǎng)度（即城市個(gè)數(shù)）Lenchrom＝14。選擇最大進(jìn)化代數(shù)maxgen為可變參數(shù)，并取20、40、60、80、100這5種參數(shù)和14個(gè)城市坐標(biāo)作為輸入。首先，對(duì)最大進(jìn)化代數(shù)為20的程序進(jìn)行不變量生成，以14個(gè)城市的坐標(biāo)點(diǎn)為輸入。通過2次動(dòng)態(tài)篩選機(jī)制和靜態(tài)篩選機(jī)制，過濾掉了一些非關(guān)鍵變量，并得到關(guān)鍵變量集合見表2。

表2 GA-TSP中關(guān)鍵變量集合Tab.2 Collection of key variables in GA-TSP

接下來，對(duì)表2中的關(guān)鍵變量集合進(jìn)行關(guān)鍵變量提取，提取出main（）:::EXIT程序點(diǎn)中的關(guān)鍵變量::min＿distance進(jìn)行對(duì)比分析。由已經(jīng)生成的主函數(shù)調(diào)用圖4中可以發(fā)現(xiàn)，關(guān)鍵變量::min＿distance是用歐式距離定義的變量。

得到關(guān)鍵變量后，需對(duì)其它4個(gè)參數(shù)（最大進(jìn)化代數(shù)為40、60、80、100）的程序進(jìn)行不變量的生成和關(guān)鍵變量::min＿distance的提取。由于遺傳算法每次運(yùn)行得到的結(jié)果波動(dòng)較大，因此對(duì)每一個(gè)參數(shù)都進(jìn)行10次運(yùn)行和關(guān)鍵變量的篩選與提取，并做了平均數(shù)比較。如圖5所示，圖中橫軸是每個(gè)參數(shù)運(yùn)行的次數(shù)，縱軸是關(guān)鍵變量::min＿distance的大小。從圖中可知，隨著參數(shù)的變化，即最大進(jìn)化代數(shù)的增大，::min＿distance逐漸趨于穩(wěn)定，不會(huì)輕易產(chǎn)生較大的結(jié)果波動(dòng)，也不會(huì)輕易地陷入局部最優(yōu)解。如圖6所示，在做了平均值對(duì)比后，隨著參數(shù)（最大進(jìn)化代數(shù)）的增大，::min＿distance是一個(gè)持續(xù)減小的過程，更加說明了機(jī)器學(xué)習(xí)算法的正確率與穩(wěn)定性，會(huì)隨著參數(shù)的變化越來越好，從而印證了該方法的可行性。

圖5 每個(gè)參數(shù)運(yùn)行10次Fig.5 Run 10 times for each parameter

圖6 不同參數(shù)的關(guān)鍵變量Fig.6 Key variables for different parameters

2.2 蟻群算法

本文使用的第二個(gè)程序，是以蟻群系統(tǒng)為模型的蟻群算法程序（非螞蟻周模型），并以TSP問題為測(cè)試對(duì)象。蟻群算法是一種基于種群的啟發(fā)式隨機(jī)搜索算法，具有正反饋、魯棒性、并行性等優(yōu)點(diǎn)，可以使用蟻群算法解決最短路徑問題。在計(jì)算最短路徑時(shí)，使用最近鄰方法是從源節(jié)點(diǎn)出發(fā)，每次選擇一個(gè)距離最短的點(diǎn)來遍歷所有的節(jié)點(diǎn)得到的路徑（距離可以用歐式距離公式來表示）。但蟻群算法在計(jì)算兩節(jié)間的最短距離時(shí)易陷入局部最優(yōu)，且隨著算法復(fù)雜程度的增加其收斂速度慢，還有可能出現(xiàn)停滯現(xiàn)象。

在蟻群算法中，主要有6個(gè)參數(shù):信息啟發(fā)因子α，期望啟發(fā)因子β，全局信息素?fù)]發(fā)參數(shù)ρ，局部信息素?fù)]發(fā)參數(shù)α1，螞蟻數(shù)量M，以及最大循環(huán)次數(shù)NcMax。本實(shí)驗(yàn)探究最大循環(huán)次數(shù)NcMax與蟻群算法性能之間的關(guān)系。函數(shù)調(diào)用如圖7所示。

圖7 ACO-tsp.cpp程序的函數(shù)調(diào)用圖Fig.7 Function call graph of ACO-tsp.cpp program

通過2次關(guān)鍵變量篩選機(jī)制和關(guān)鍵變量提取，得到直接反應(yīng)歐氏距離的關(guān)鍵變量::Lnn。對(duì)每個(gè)參數(shù)進(jìn)行20次運(yùn)行和關(guān)鍵變量的篩選與提取，并做了平均數(shù)比較，結(jié)果如圖8所示。得到的關(guān)鍵變量集合見表3。

表3 ACO-TSP中關(guān)鍵變量集合Tab.3 Set of key variables in ACO-TSP

由圖8可知，最大循環(huán)次數(shù)NcMax對(duì)算法的正確性以及穩(wěn)定性有較大影響，可以直接從與歐氏距離相關(guān)的關(guān)鍵變量中反映出來。當(dāng)循環(huán)次數(shù)越大，蟻群算法的性能越好，也越穩(wěn)定。

2.3 模擬退火算法

本文使用的第三個(gè)程序，是用模擬退火算法解決TSP問題。該問題給定平面上10個(gè)點(diǎn)的名稱與坐標(biāo)，2點(diǎn)之間的距離為其歐幾里得距離。求一條路徑，剛好經(jīng)過每個(gè)點(diǎn)一次，使其路徑長(zhǎng)度最短。

模擬退火算法是一種基于自身退火原理的隨機(jī)搜索算法，其準(zhǔn)確率與最優(yōu)解的精度主要與退火速率Δ、初始溫度T、終止溫度e、以及循環(huán)代數(shù)L有關(guān)。根據(jù)實(shí)驗(yàn)可得:當(dāng)循環(huán)代數(shù)L越大時(shí)，與歐幾里得距離直接相關(guān)的關(guān)鍵變量this-＞loc＿distance和this-＞min＿distance越來越小，模擬退火算法越能跳出局部最優(yōu)解，得到最短路徑。關(guān)鍵變量集合與實(shí)驗(yàn)結(jié)果見表4和圖9所示。

圖9 不同參數(shù)的關(guān)鍵變量Fig.9 Key variables of different parameters

表4 SA-TSP中關(guān)鍵變量集合Tab.4 Set of key variables in SA-TSP

2.4 K-means聚類算法

第四個(gè)示例程序，是一個(gè)K-means聚類算法實(shí)現(xiàn)。輸入數(shù)據(jù)集為所有點(diǎn)的集合，是一個(gè)二維矩陣。給定k值，將數(shù)據(jù)集中的所有點(diǎn)分為k類，計(jì)算k個(gè)中心點(diǎn)（質(zhì)心）、每個(gè)點(diǎn)所屬的歸類以及距離值。其中，每個(gè)點(diǎn)與質(zhì)心的距離由歐氏距離定義與計(jì)算。如圖10所示，取k＝｛2，3，4，5，6｝后發(fā)現(xiàn)，當(dāng)k值越大時(shí)，聚類效果越好。

圖10 k-means聚類結(jié)果Fig.10 K-means clustering results

從不變量角度看，取k＝｛2，3，4，5，6｝后，會(huì)產(chǎn)生｛2，3，4，5，6｝個(gè)類別。每個(gè)類別里，質(zhì)心與歸類的每個(gè)點(diǎn)之間的歐氏距離，即關(guān)鍵變量＿＿first［］.minDist會(huì)越來越小，如圖11所示。關(guān)鍵變量集合見表5。

圖11 關(guān)鍵變量趨勢(shì)圖Fig.11 Trend chart of key variables

表5 k-means中關(guān)鍵變量集合Tab.5 Set of key variables in k-means

2.5 KNN分類算法

第五個(gè)示例程序假設(shè)了一個(gè)場(chǎng)景，用KNN分類算法為坐標(biāo)上的點(diǎn)進(jìn)行分類，如圖12所示。由圖所見，共提供13個(gè)坐標(biāo)點(diǎn)，每個(gè)坐標(biāo)點(diǎn)都有相應(yīng)的坐標(biāo)（x，y）以及其所屬的類別A或B?，F(xiàn)給定一個(gè)點(diǎn)坐標(biāo)（1.5，-0.5），判斷其屬于類別A或類別B。對(duì)于KNN分類算法:參數(shù)k是指選擇樣本數(shù)據(jù)中前k個(gè)最相似數(shù)據(jù)；計(jì)算待分類點(diǎn)與已知類別點(diǎn)之間的歐氏距離；選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為測(cè)試數(shù)據(jù)的分類。

圖12 KNN示例程序Fig.12 KNN sample program

本次示例中選取k＝｛3，5，7，9｝。經(jīng)過不變量的生成和關(guān)鍵變量的篩選與提取后，可以發(fā)現(xiàn)，前k個(gè)歐式距離最短的關(guān)鍵變量在分類中起著決定性的作用。而隨著k的增大，最相似數(shù)據(jù)的數(shù)量不斷增大，歐式距離最短的關(guān)鍵變量所代表的數(shù)據(jù)標(biāo)簽出現(xiàn)的可能性也會(huì)越來越大，這時(shí)分類結(jié)果也會(huì)更加的準(zhǔn)確。關(guān)鍵變量集合見表6，其中:distance即為該實(shí)例程序中與歐氏距離直接相關(guān)的關(guān)鍵變量。

表6 KNN中關(guān)鍵變量集合Tab.6 Set of key variables in KNN

3 結(jié)束語

本文提出了一種基于不變量的機(jī)器學(xué)習(xí)算法分析方法。通過改變算法的參數(shù)，得到不同參數(shù)下的關(guān)鍵變量并分析其變化?？梢缘贸?當(dāng)機(jī)器學(xué)習(xí)算法的準(zhǔn)確性，隨著參數(shù)的調(diào)整越來越好時(shí)，基于歐氏距離的關(guān)鍵變量總會(huì)以一種特定的規(guī)律變化。使用靜態(tài)分析加動(dòng)態(tài)分析的方法，從程序不變量的角度初步探索了機(jī)器學(xué)習(xí)算法的質(zhì)量，驗(yàn)證了對(duì)應(yīng)算法的魯棒性；探索了機(jī)器學(xué)習(xí)算法中的不變量，有別于普通程序和并發(fā)程序的不變量；機(jī)器學(xué)習(xí)算法中的不變量數(shù)量龐大，并且具有很大的不穩(wěn)定性，需要進(jìn)行反復(fù)多次的實(shí)驗(yàn)和變量的篩選。

進(jìn)一步的研究將把本文方法擴(kuò)展到更大、更復(fù)雜的機(jī)器學(xué)習(xí)算法中，改進(jìn)關(guān)鍵變量的篩選機(jī)制，研究是否有更多的關(guān)鍵變量對(duì)算法正確率有影響，以及不同的算法與關(guān)鍵變量之間的關(guān)系。希望可以通過除Daikon以外其它的工具來生成不變量。此外，需要改進(jìn)和研究的方面主要包括:開發(fā)一種方法來獲得更加完整的關(guān)鍵變量集合；在更龐大、更復(fù)雜的機(jī)器學(xué)習(xí)算法上進(jìn)行實(shí)驗(yàn)驗(yàn)證。