對《HYDRA》的復現-GA phase

08-25

來自專欄宇先生說軟體工程

論文《HYDRA：Massively Compositional Model for Cross-Project Defect Prediction》（以下簡稱論文），發表於2016的TSE。其模型演算法主要分為兩個階段（GA phase & EL phase），本篇主要講GA phase的復現。

GA phase：對源數據集 $(S=left[S_1,S_2,...,S_N ight])$ 以及目標數據集T，訓練 $(N)$ 個底層分類器（底層分類器均使用Logic Regression）。第 $(i)$ 個底層分類器使用的訓練集為 $(S_icuphat{T})$ ，其中 $(hat{T})$ 是從 $(T)$ 中抽取的部分（10%）帶有標籤的樣本，剩餘的90%作為測試集。對於 $T$ 中90%的樣本，同時作為第 $(N+1)$ 個底層分類器的訓練集與測試集，訓練得到第 $(N+1)$ 個底層分類器。此時共計得到 $(N+1)$ 個底層分類器，記為 $(clf\_list=left[clf_1, clf_2, ..., clf_{N+1} ight])$ 。為了將 $(clf\_list)$ 中的底層分類器集成為GA分類器，需要 $(N+1)$ 個權值以及一個閾值。GA階段就是通過遺傳演算法，得到最優的（權值+閾值）基因。

Genetic Algorithm

以下介紹遺傳演算法，用偽代碼的形式展現：

以下介紹在選擇、交叉、變異階段用到的演算法

輪盤賭選擇（Roulette wheel selection）　　輪盤賭選擇是最常用的選擇運算元，來源於實際生活中的擲飛鏢遊戲：有多個扇形區域的輪盤，每個區域佔有一定的面積，遊戲者隨機投擲一枚飛鏢，該飛鏢飛中的區域，即為被選中的區域。如果要將上述遊戲變成代碼，首先需要得到擁有各個扇形區域的圓盤。在GA中，也即求出每個個體能夠生存下去的概率。在遺傳演算法中，每個個體會有一個適宜度評分 $(fitness)$ （論文中用 $(f_1)$ 作為 $(fitness)$ ），個體 $(i)$ 的存活率 $(p_i = frac {fitness_i}{sum_{j=1}^M{fitness_j}})$ 。對於個體數為 $(M)$ 的種群，求出所有個體的存活率還不好使，因為無法通過這個概率列表進行「投擲」飛鏢。為此，可以將輪盤沿著某個扇形的邊剪開，得到一條線段，此時所有個體的存活率便體現在這條 $(left[0, 1 ight])$ 的線段上。為了更好的確定投擲區間，此時需要計算每個個體的累積概率， $(q_i = sum_{j=1}^i{p_j})$ 。至此，就將個體數為 $(M)$ 的種群投影到了 $(left[0, 1 ight])$ 的線段上，隨機一個 $(left[0, 1 ight])$ 的數字，便能在這條線段上選擇一個個體。
單點交叉（Single point crossover）

　　單點交叉運算元是模擬生物界染色體上基因交叉，可以說是一種仿生技術。本文採取單點交叉，也即對於要配對的基因對（基因與個體一對一的關係，一個個體只含有一條基因），隨機選擇一個基因序號，從此序號之後的基因與搭檔交換，得到一對新的個體。
隨機變異（Random mutation）
　　與單點交叉類似，對於一個個體，隨機選擇一個基因序號，重新給該序號上的基因賦上一隨機值（取值範圍之內），得到一個新的個體。

GA phase的實現過程

在介紹了GA演算法之後，如何將其用於軟體缺陷預測呢？前面我們已經得到了 $(clf\_list)$ ，現在我們的目標是如何給這些底層分類器分配權值，以及這 $(N+1)$ 個分類器通過何種方式，對於某一樣例進行預測。

我們不妨假設，現在已經擁有 $(N+1)$ 個權值，該權值列表記為 $(wight\_list)$ ，下面給出判斷樣例(j)是正例還是反例的計算公式： $Labelleft(j ight) = egin{cases} 1(i.e., defective), & mbox{if }Compleft(j ight)mbox{ >= threshold} \ 0(i.e., defect free), & otherwise end{cases}$ 其中, $Compleft(j ight) = frac {sum_{i=1}^{N+1} alpha_i * Score_ileft(j ight)}{LOCleft(j ight)}$ 。

從公式中可以看到，判斷一個樣例是正例還是反例，會先通過底層分類器進行判斷，然後加權累加，得到的 $Comp$ 與閾值進行比較。由此可知，閾值的取值範圍不再是 $left[0, 1 ight]$ ，而是 $left[0, N+1 ight]$ 。

此時我們便能確定基因的序列了。論文中的基因長度為 $N+2$ ，其中，前 $N+1$ 項的取值範圍為 $left[0, 1 ight]$ ，第 $N+2$ 項的取值範圍為 $left[0, N+1 ight]$ 。

確定了基因序列，便能用GA演算法生成最優的權值與閾值了。詳細代碼，見github