對《HYDRA：Massively Compositional Model for Cross-Project Defect Prediction》的複現-GA phase

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

• GA phase：對源資料集 S=[S1,S2,...,SN] S = [ S 1 , S 2 , . . . , S N ] 以及目标資料集T，訓練 N N 個底層分類器（底層分類器均使用Logic Regression）。第ii個底層分類器使用的訓練集為 Si∪T^ S i ∪ T ^ ，其中 T^ T ^ 是從 T T 中抽取的部分（10%）帶有标簽的樣本，剩餘的90%作為測試集。對于TT中90%的樣本，同時作為第 N+1 N + 1 個底層分類器的訓練集與測試集，訓練得到第 N+1 N + 1 個底層分類器。此時共計得到 N+1 N + 1 個底層分類器，記為 clf_list=[clf1,clf2,...,clfN+1] c l f _ l i s t = [ c l f 1 , c l f 2 , . . . , c l f N + 1 ] 。為了将 clf_list c l f _ l i s t 中的底層分類器內建為GA分類器，需要 N+1 N + 1 個權值以及一個門檻值。GA階段就是通過遺傳算法，得到最優的（權值+門檻值）基因。

Genetic Algorithm

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

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

1. 輪盤賭選擇（Roulette wheel selection）

   　　輪盤賭選擇是最常用的選擇算子，來源于實際生活中的擲飛镖遊戲：擁有多個扇形區域的輪盤，每個區域占有一定的面積，遊戲者随機投擲一枚飛镖，該飛镖飛中的區域，即為被選中的區域。如果要将上述遊戲變成代碼，首先需要得到擁有各個扇形區域的圓盤。在GA中，也即求出每個個體能夠生存下去的機率。在遺傳算法中，每個個體會有一個适宜度評分 fitness f i t n e s s （論文中用 f1 f 1 作為 fitness f i t n e s s ），個體 i i 的存活率pi=fitnessi∑Mj=1fitnessjpi=fitnessi∑j=1Mfitnessj。對于個體數為 M M 的種群，求出所有個體的存活率還不好使，因為無法通過這個機率清單進行“投擲”飛镖。為此，可以将輪盤沿着某個扇形的邊剪開，得到一條線段，此時所有個體的存活率便展現在這條[0,1][0,1]的線段上。為了更好的确定投擲區間，此時需要計算每個個體的累積機率， qi=∑ij=1pj q i = ∑ j = 1 i p j 。至此，就将個體數為 M M 的種群投影到了[0,1][0,1]的線段上，随機一個 [0,1] [ 0 , 1 ] 的數字，便能在這條線段上選擇一個個體。

2. 單點交叉（Single point crossover）

   　　單點交叉算子是模拟生物界染色體上基因交叉，可以說是一種仿生技術。本文采取單點交叉，也即對于要配對的基因對（基因與個體一對一的關系，一個個體隻含有一條基因），随機選擇一個基因序号，從此序号之後的基因與搭檔交換，得到一對新的個體。

3. 随機變異（Random mutation）

   　　與單點交叉類似，對于一個個體，随機選擇一個基因序号，重新給該序号上的基因賦上一随機值（取值範圍之内），得到一個新的個體。

GA phase的實作過程

在介紹了GA算法之後，如何将其用于軟體缺陷預測呢？前面我們已經得到了 clf_list c l f _ l i s t ，現在我們的目标是如何給這些底層分類器配置設定權值，以及這 N+1 N + 1 個分類器通過何種方式，對于某一樣例進行預測。

我們不妨假設，現在已經擁有 N+1 N + 1 個權值，該權值清單記為 wight_list w i g h t _ l i s t ，下面給出判斷樣例 j j 是正例還是反例的計算公式：

Label(j)=⎧⎩⎨1(i.e.,defective),0(i.e.,defectfree),if Comp(j) >= thresholdotherwiseLabel(j)={1(i.e.,defective),if Comp(j) >= threshold0(i.e.,defectfree),otherwise

其中,

Comp(j)=∑N+1i=1αi∗Scorei(j)LOC(j) C o m p ( j ) = ∑ i = 1 N + 1 α i ∗ S c o r e i ( j ) L O C ( j )

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

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

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

此處貼出GA phase 主要代碼

# Genetic Algorithm
from sklearn.linear_model import LogisticRegression
import random
import numpy as np
from Tools.EvaluationTool import EvaluationTool


class GA:
def __init__(self, pop_size, max_gen=100, crossover_rate=0.6, mutation_rate=0.1):
    # 初始化
    self.pop_size = pop_size  # 種群數
    self.max_gen = max_gen  # 最大繁殖代數
    self.crossover_rate = crossover_rate  # 交叉率
    self.mutation_rate = mutation_rate  # 變異率
    self.genes_num = None  # 基因數目
    self.clf_list = None
    self.target_data = None
    self.target_label = None
    self.pop_f1_list = []  # 記錄種群中每個個體的f1值，避免重複計算

def fit(self, source_data_list, source_label_list, target_data, target_label):
    # 得到一衆基礎分類器
    clf_list = self.get_base_clf(source_data_list, source_label_list, target_data, target_label)
    self.clf_list = clf_list
    # 個體->染色體->list of genes
    # 确定基因的個數 = 分類器個數 + 門檻值
    genes_num = len(clf_list) + 1
    self.genes_num = genes_num
    # 初始化種群
    pop = np.random.random((self.pop_size, self.genes_num))
    # 最後一列門檻值的取值範圍由（0,1）調整到(0,genes_num-1)
    pop[:, -1] = pop[:, -1] * (genes_num - 1)
    # 計算初始群體中的最優解
    pre_solution, pre_f1 = self.get_best_from_pop(pop)
    # 繁殖
    cur_gen = 0  # 目前代數為0
    while cur_gen < self.max_gen:
        temp_pop = pop.copy()
        pop_new = self.ga_generation(temp_pop)
        cur_solution, cur_f1 = self.get_best_from_pop(pop_new)
        if cur_f1 > pre_f1:
            pre_f1 = cur_f1
            pre_solution = cur_solution
        cur_gen += 1
    print(pre_f1)
    return pre_solution, pre_f1

# 訓練得到一衆基礎分類器
def get_base_clf(self, source_data_list, source_label_list, target_data, target_label):
    # 将target中一部分樣例添加到source中，當做訓練集
    sdl, sll, td, tl = self.transfer_target_to_source(source_data_list, source_label_list,
                                                      target_data, target_label)
    self.target_data, self.target_label = td, tl
    clf_list = []
    for index in range(len(source_data_list)):
        # 論文中用的是邏輯回歸，感覺效果不是很好
        clf = LogisticRegression()
        # 換成C4.5
        # clf = tree.DecisionTreeClassifier(criterion='entropy', splitter='random', max_depth=30)
        clf.fit(sdl[index], sll[index])
        clf_list.append(clf)
    # 使用target訓練，得到(N+1)th clf
    clf = LogisticRegression()
    clf.fit(td, tl)
    clf_list.append(clf)
    return clf_list

# 從target中轉移部分樣例到source中
# 20180806 将for循環改成清單推導式
@staticmethod
def transfer_target_to_source(source_data_list, source_label_list, target_data, target_label):
    # 随機移除10%的樣例
    t_sample_num = target_data.shape[0]
    t_remove_num = round(t_sample_num * 0.1)  # 四舍五入取整
    t_remove_index = random.sample(range(0, t_sample_num), t_remove_num)
    t_other_index = [i for i in range(0, t_sample_num) if i not in t_remove_index]
    # 新的target
    target_data_new = np.array([target_data[i, :] for i in t_other_index])
    target_label_new = np.array([target_label[i] for i in t_other_index])
    # 移出的樣例以及标簽
    temp_data = np.array([target_data[i, :] for i in t_remove_index])
    temp_label = np.array([target_label[i] for i in t_remove_index])
    # 新的source
    temp_data_list = [np.append(source_data_list[i], temp_data, axis=0) for i in range(len(source_data_list))]
    temp_label_list = [np.append(source_label_list[i], temp_label, axis=0) for i in range(len(source_label_list))]
    return temp_data_list, temp_label_list, target_data_new, target_label_new

# 從種群中選出最優的個體（染色體）
def get_best_from_pop(self, pop):
    if len(self.pop_f1_list) != 0:
        self.pop_f1_list.clear()
    # 比較每一個個體的F1值
    pre_f1, best_index = 0, 0
    for index in range(pop.shape[0]):
        cur_f1 = self.score(pop[index])
        self.pop_f1_list.append(cur_f1)
        if cur_f1 > pre_f1:
            pre_f1 = cur_f1
            best_index = index
    return pop[best_index], pre_f1

# 預測目标資料集的标簽并計算分數
def score(self, pop_item):
    # 計算target中每一個樣例的得分
    predict_label = []
    for sample in range(self.target_data.shape[0]):
        # comp = from i to N+1 (wight * clf prediction) / loc(sample)
        comp = 0
        for i in range(len(self.clf_list)):
            comp += pop_item[i] * self.clf_list[i].predict(self.target_data[sample].reshape(1, -1))[0]
        # comp /= self.target_data[sample, 0]
        if comp >= pop_item[-1]:
            predict_label.append(1)
        else:
            predict_label.append(0)
    score = EvaluationTool.cal_f1(np.array(predict_label), self.target_label)
    return score

# 繁殖疊代
def ga_generation(self, pop):
    # 選擇階段
    pop_select = self.select(pop)
    # 交叉階段
    pop_cross = self.crossover(pop_select)
    # 變異階段
    pop_mutation = self.mutation(pop_cross)
    return np.array(pop_mutation)

# 選擇
# 20180807 隻修改到這裡 下次從這裡開始
def select(self, pop):
    fit_list, q_list = [], []  # 适應度清單，累積機率清單
    choose_index = set()  # 被選中的個體
    fit_sum = sum(self.pop_f1_list)   # 适應度總和
    p_list_array = np.divide(np.array(self.pop_f1_list), fit_sum)  # 遺傳到下一代機率清單
    for i in range(len(p_list_array)):
        # 計算每個個體的累積機率
        q = 0
        for j in range(i+1):
            q += p_list_array[j]
        q_list.append(q)
    # 産生一個随機數清單，用于選擇
    rand_list = np.random.rand(pop.shape[0])
    for i in range(len(rand_list)):
        choose_index.add(self.get_index_from_list(rand_list[i], q_list))
    pop_new = [pop[i] for i in choose_index]
    return np.array(pop_new)

# 從目标清單中，傳回傳入參數所對應的位置，傳入參數應位于兩個值之間
@staticmethod
def get_index_from_list(num, target_list):
    for i in range(len(target_list)):
        if i == 0 and num <= target_list[0]:
            return 0
        else:
            if target_list[i-1] < num <= target_list[i]:
                return i

# 交叉
def crossover(self, pop):
    son_list = []
    pair_num = int(pop.shape[0]/2)
    for i in range(pair_num):
        rand_num = random.random()
        if rand_num < self.crossover_rate:
            # 随機選取交叉位置
            rand_cross_index = random.randint(0, pop.shape[1]-1)  # ???是否減一
            # 交叉并産生新子代
            parent_a = pop.copy()[i*2, :]
            parent_b = pop.copy()[i*2+1, :]
            temp_parent_a = parent_a.copy()[rand_cross_index:]
            parent_a[rand_cross_index:] = parent_b[rand_cross_index:]  # 新子代a
            parent_b[rand_cross_index:] = temp_parent_a  # 新子代b
            son_list.append(parent_a)
            son_list.append(parent_b)
    if len(son_list) != 0:
        pop_new = np.append(pop, np.array(son_list), axis=0)
    else:
        pop_new = pop
    return pop_new

# 變異
def mutation(self, pop):
    son_list = []
    for i in range(pop.shape[0]):
        rand_num = random.random()
        if rand_num < self.mutation_rate:
            # 随機産生變異位置
            rand_mutation_index = random.randint(0, pop.shape[1]-1)  # ???是否減一
            # 變異産生新子代
            parent = pop.copy()[i, :]
            if rand_mutation_index == pop.shape[1]-1:
                # 最後一列變異
                r = random.random()*(self.genes_num-1)
                parent[rand_mutation_index] = r
            else:
                # 其他列變異
                r = random.random()
                parent[rand_mutation_index] = r
            son_list.append(parent)
    if len(son_list) != 0:
        pop_new = np.append(pop, np.array(son_list), axis=0)
    else:
        pop_new = pop
    return pop_new