陳自力

（福建船政交通職業(yè)學(xué)院 信息與智慧交通學(xué)院，福建 福州 350007）

隨著科學(xué)技術(shù)的不斷發(fā)展，互聯(lián)網(wǎng)取得了巨大的進(jìn)步，智能設(shè)備的應(yīng)用范圍逐漸擴(kuò)大，并開始滲透到人們生活、工作的方方面面，涉及的應(yīng)用類型也呈現(xiàn)出明顯的多樣化趨勢［1］。為更好地滿足人們在對各類應(yīng)用程式使用過程中的使用需求，分類算法的應(yīng)用逐漸被重視，并逐漸成為應(yīng)用程序設(shè)計(jì)以及開發(fā)中的重要因素。分類算法的作用主要體現(xiàn)在提高對應(yīng)用程序內(nèi)所儲存的內(nèi)容進(jìn)行精準(zhǔn)劃分，在最短時(shí)間內(nèi)反饋用戶需求的信息［2］。為此，在對其進(jìn)行分類計(jì)算過程中，需要進(jìn)行蛻變測試，確保分類算法應(yīng)用程序輸出結(jié)果可靠性的重要手段?，F(xiàn)階段，蛻變測試方法的主要思路是采用已經(jīng)在正確性上得到驗(yàn)證的測試結(jié)果作為待測內(nèi)容進(jìn)行驗(yàn)證，將理論結(jié)果與實(shí)際驗(yàn)證結(jié)果進(jìn)行對比，并將其作為判斷待測內(nèi)容質(zhì)量的標(biāo)準(zhǔn)［3］。根據(jù)這一思路，已有諸多學(xué)者對于蛻變測試方法進(jìn)行了研究。其中，江競捷等［4］提出了關(guān)于圖像識別系統(tǒng)的蛻變測試方法研究，以圖像GAN 為基礎(chǔ)設(shè)計(jì)了對應(yīng)的蛻變測試方法，該方法對于提高圖像識別準(zhǔn)確率有明顯效果，但占用的內(nèi)存較大；鐘文康等［5］提出了面向翻譯系統(tǒng)的蛻變測試研究，在一定程度上提高譯文的質(zhì)量，但需要大量的樣本作為基礎(chǔ)，前期準(zhǔn)備工作相對較多。

基于此，提出分類算法應(yīng)用程序的蛻變測試方法研究。通過對分類算法特征進(jìn)行分析，建立了相應(yīng)的蛻變關(guān)系，以此實(shí)現(xiàn)對分類結(jié)果的測試。并通過試驗(yàn)驗(yàn)證了其有效性。通過研究，以期為分類算法應(yīng)用程序的測試提供參考。

1 蛻變測試流程設(shè)計(jì)

為實(shí)現(xiàn)分類算法應(yīng)用程序分類結(jié)果的正確性進(jìn)行有效測試，進(jìn)行測試是關(guān)鍵環(huán)節(jié)。因此，本文設(shè)計(jì)了針對該類程序的蛻變測試方法。對蛻變測試的主體流程進(jìn)行設(shè)計(jì)，通過在該流程中嵌入響應(yīng)的蛻變關(guān)系，實(shí)現(xiàn)對分類結(jié)果的精準(zhǔn)檢測。

利用已有的檢測方法對分類算法應(yīng)用程序中分類結(jié)果進(jìn)行測試，并選中最終輸出結(jié)果與預(yù)期結(jié)果保持一致的一組數(shù)據(jù)作為原始用例。在此基礎(chǔ)上，對程序的特征進(jìn)行分析，并以其特點(diǎn)為基礎(chǔ)，構(gòu)造與程序相適應(yīng)的蛻變關(guān)系，以原始用例為基礎(chǔ)，生成蛻變用例，將其再次輸入到分類算法應(yīng)用程序中，根據(jù)輸出的分類結(jié)果與本文設(shè)計(jì)的蛻變關(guān)系之間的契合度判斷程序是否存在異常?；玖鞒倘鐖D1 所示。

圖1 蛻變測試流程圖

2 分類算法應(yīng)用程序特征分析

現(xiàn)階段分類算法的種類和方式多種多樣，其中應(yīng)用最為廣泛的是KNN（K-Nearest Neighbor Classification）算法［6］，具有明顯的計(jì)算過程簡單、空間占用小、魯棒性高的特點(diǎn)［7］。所以，本文以KNN 算法為基礎(chǔ)，對其特點(diǎn)進(jìn)行了全面分析，并進(jìn)行相應(yīng)的蛻變測試研究。

KNN 算法是一種經(jīng)典的模式識別算法。核心是找到最接近的K 個(gè)樣本，在這K 個(gè)近鄰中計(jì)算出優(yōu)勢最明顯的數(shù)據(jù)群體，以確定對應(yīng)的樣本分類結(jié)果。以此為基礎(chǔ)，本文歸納了KNN 算法的主要特征如下所示：

需要對待分類樣本與訓(xùn)練樣本集中每一個(gè)樣本的距離進(jìn)行計(jì)算［8］，對不同的樣本類型，計(jì)算距離的方式也不同，可以是歐氏距離也可以是馬氏距離，對于部分樣本，也可以采用余弦相似度的方式來間接表示距離。在確定了距離之后，需要對最近鄰數(shù)據(jù)進(jìn)行搜索，并將距離排名前K 的訓(xùn)練樣本作為最近鄰進(jìn)行采集。根據(jù)最近鄰的實(shí)際情況，對數(shù)據(jù)進(jìn)行分類。因此，KNN 算法實(shí)現(xiàn)的關(guān)鍵主要在于K 值的選擇、距離的計(jì)算以及樣本的排序。

為了便于蛻變關(guān)系的描述，作出了如下定義：

定義1：數(shù)據(jù)類型相似度。在待分類樣本距離范圍內(nèi)的K個(gè)近鄰樣本中，隸屬于類型A 的樣本數(shù)量為KA，那么，待分類樣本與類型A 之間存在的相似度則表示為KA/K。

定義2：數(shù)據(jù)相似類。當(dāng)待分類樣本與類型A之間的相似度大于0 時(shí)，則默認(rèn)類型A 為待分類樣本的相似類。

定義3：數(shù)據(jù)最大相似類。在待分類樣本的所有相似類中，若類型A 的類型相似度最大，則類型A 即為待分類樣本的最大相似類。最大相似類也就是分類算法應(yīng)用程序最終分類結(jié)果。

定義4：數(shù)據(jù)最小相似類。在待分類樣本的相似類中，若類型A 的類型相似度最小，其即為待分類樣本的最小相似類。

定義5：完全隸屬類。當(dāng)待分類樣本與類型A之間的相似度為1 時(shí)，則稱類型A 為待分類樣本的完全隸屬類。其也是相似度閾值的最大值，因此，完全隸屬類也就是樣本的最終分類。

定義6：不相關(guān)類。當(dāng)待分類樣本與類型A之間的相似度為0 時(shí)，則稱類型A 為待分類樣本的不相關(guān)類。上面的定義2 中，已經(jīng)給出了成為待分類樣本相似類的條件為相似度大于0，因此，不相關(guān)類不作為待分類樣本的備選分類考慮，可以直接對其進(jìn)行淘汰處理。

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

在上述基礎(chǔ)上，本文以蛻變關(guān)系構(gòu)造的基本準(zhǔn)則為標(biāo)準(zhǔn)，以KNN 算法分類程序的特征分析結(jié)果為依據(jù)，假設(shè)以訓(xùn)練樣本為n，構(gòu)造了以下的蛻變關(guān)系。

MR1 線性平移。在訓(xùn)練樣本中，當(dāng)對所有個(gè)體和屬性xi同時(shí)進(jìn)行相同規(guī)模的線性平移時(shí)，不影響最終的分類結(jié)果。

其中，f(xi)表示測試樣本，b i表示平移距離。

MR2 等比例縮放。在訓(xùn)練樣本中，當(dāng)對所有個(gè)體和屬性xi同時(shí)進(jìn)行相同比例的縮放時(shí)，不影響最終的分類結(jié)果。

其中，a表示放縮比例。

MR3 對稱變換。當(dāng)對訓(xùn)練樣本中所有樣本的所有屬性值xi整體進(jìn)行完全一致取反處理，以坐標(biāo)軸為基準(zhǔn)進(jìn)行對稱變換時(shí)，不影響最終的分類結(jié)果。

MR4 屬性列置換。在訓(xùn)練樣本中，當(dāng)對任意屬性列Ai、Aj 進(jìn)行置換操作時(shí)，不影響最終的分類結(jié)果。

MR5 樣本亂序。當(dāng)訓(xùn)練樣本中，樣本的排列順序被打亂時(shí)，不影響最終的分類結(jié)果。

MR6 無效屬性列增加。在訓(xùn)練樣本中，增加無效屬性列不影響最終的分類結(jié)果。

MR7-1 樣本全復(fù)制。在訓(xùn)練樣本中，對所有樣本及其屬性進(jìn)行完整的復(fù)制操作，使樣本數(shù)量變?yōu)?n 時(shí)，不影響最終的分類結(jié)果。

MR7-2 最大相似類復(fù)制。在訓(xùn)練樣本中，假設(shè)最大相似類的樣本數(shù)為m，當(dāng)對其進(jìn)行復(fù)制操作，不影響最終的分類結(jié)果。

MR8 不相關(guān)類復(fù)制。在訓(xùn)練樣本集中，假設(shè)不相關(guān)類樣本數(shù)為j，對其進(jìn)行復(fù)制，并采用隨機(jī)的方式再待測樣本中選擇j 個(gè)位置對其進(jìn)行插入操作，不影響最終的分類結(jié)果。

MR9 最小相似類剔除。在訓(xùn)練樣本中，假設(shè)最小相似類的樣本數(shù)為i，對其進(jìn)行剔除操作，不影響最終的分類結(jié)果。

4 試驗(yàn)測試

為測試本文設(shè)計(jì)蛻變測試方法的有效性，對其進(jìn)行了試驗(yàn)測試。

4.1 測試環(huán)境

本文測試環(huán)境為Window 8，APU 2G，內(nèi)存4G。試驗(yàn)設(shè)計(jì)了一個(gè)總系統(tǒng)帶寬10 MHz 的單小區(qū)作為試驗(yàn)環(huán)境，在管理區(qū)域中，用戶數(shù)設(shè)置為228，并將每個(gè)決策時(shí)間內(nèi)的用戶數(shù)量控制在一個(gè)的定值上。將 KNN 算法部署到小區(qū)中心位置，同時(shí)，設(shè)置用戶被在以中心為基礎(chǔ)隨機(jī)分布的距離為100 m。按比例對用戶的計(jì)算任務(wù)進(jìn)行劃分，并在一段時(shí)間內(nèi)對每個(gè)用戶服務(wù)類型進(jìn)行修改，任務(wù)主要包括5 類，分別為迭代、疊加、存儲、傳遞以及篩選。其中，KNN 算法是計(jì)算能力為8 GHz/sec，用戶任務(wù)的數(shù)據(jù)大小以 kbit 為單位進(jìn)行統(tǒng)計(jì)，在（300，500）范圍內(nèi)均勻分布。本文通過上述任務(wù)指標(biāo)，對用戶進(jìn)行分類。

4.2 測試方法

對本文設(shè)計(jì)的蛻變關(guān)系進(jìn)行驗(yàn)證的方法如下所示，通過該方法實(shí)現(xiàn)對蛻變測試方法有效性的評估。

（1）數(shù)據(jù)的準(zhǔn)備。首先構(gòu)建待分類樣本集，采用隨機(jī)取樣的方式從試驗(yàn)準(zhǔn)備的數(shù)據(jù)中選擇10%作為樣本數(shù)據(jù)，即228 條數(shù)據(jù)，并在對應(yīng)的5 個(gè)任務(wù)類型中抽取對應(yīng)數(shù)量，以此作為試驗(yàn)的待分類樣本文集；其次，構(gòu)建試驗(yàn)所需的訓(xùn)練集，本文將剩余的全部數(shù)據(jù)信息作為試驗(yàn)的訓(xùn)練集。

（2）運(yùn)用本文設(shè)計(jì)的蛻變關(guān)系，對訓(xùn)練集的數(shù)據(jù)進(jìn)行處理，構(gòu)造蛻變關(guān)系。

（3）將蛻變關(guān)系作為輸入值，輸入程序中，并再次運(yùn)行該分類程序，驗(yàn)證蛻變關(guān)系的輸出結(jié)果與預(yù)期結(jié)果之間的差異性，并檢查各項(xiàng)分類指標(biāo)變化情況。

（4）分析分類結(jié)果和分類指標(biāo)，確認(rèn)蛻變關(guān)系的實(shí)際有效價(jià)值。

4.3 測試結(jié)果

采用上述方法對試驗(yàn)數(shù)據(jù)的分類結(jié)果進(jìn)行統(tǒng)計(jì)，觀察了不同蛻變關(guān)系下不同類別的用戶數(shù)量，結(jié)果如表1 所示。

表1 輸入蛻變關(guān)系后程序的輸出結(jié)果/個(gè)

續(xù)表1 輸入蛻變關(guān)系后程序的輸出結(jié)果/個(gè)

從表1 中可以看出，在不同蛻變關(guān)系約束下，不同屬性的分類結(jié)果也存在明顯的差異性，這主要是因?yàn)樵谠囼?yàn)數(shù)據(jù)中，存在一個(gè)用戶包含多個(gè)屬性的同種類信息。因此，在不同的蛻變關(guān)系下，其分類組別也會不同。

在上述基礎(chǔ)上，對比了在不同蛻變關(guān)系下分類結(jié)果的平均相似度，其結(jié)果如表2 所示。

表2 不同蛻變關(guān)系下分類結(jié)果的平均相似度/%

從表2 中可以看出，在不同的蛻變關(guān)系下，不同分類組別中的平均相似度均在95%以上，表明分類結(jié)果具有較高的精確度。在上述基礎(chǔ)上，本文對比了蛻變后程序的分類結(jié)果中，最大組群屬性數(shù)據(jù)之間的平均相似度情況。根據(jù)上文的統(tǒng)計(jì)結(jié)果，10 個(gè)組別對應(yīng)的最大屬性組群均為配送時(shí)間，從表2 中可以看出，在不同的蛻變關(guān)系下，配送時(shí)間分類結(jié)果的平均相似度基本在96%左右，蛻變關(guān)系MR5 和MR6 略低，最高值為97.37%，出現(xiàn)在MR7-1 蛻變關(guān)系下。這也表明本文設(shè)計(jì)的蛻變測試方法具有良好的分類效果。

5 結(jié)語

在應(yīng)用程序不斷發(fā)展的今天，對于其高精度發(fā)展的研究已經(jīng)成為了一種不可阻擋的趨勢。對分類算法應(yīng)用程序而言，分類的準(zhǔn)確性和精確性是其賴以生存和發(fā)展的基礎(chǔ)。本文提出了分類算法應(yīng)用程序的蛻變測試方法研究，實(shí)現(xiàn)了提高分類精度，確保分類準(zhǔn)確性的目的，對實(shí)際使用具有一定的參考價(jià)值。