[發(fā)明專利]一種針對分類問題的進(jìn)化集成學(xué)習(xí)方法

在審

• 申請?zhí)枺?/td>: 202110038912.8
• 申請日: 2021-01-12
• 公開（公告）號: CN112734051A
• 公開（公告）日: 2021-04-30
• 發(fā)明（設(shè)計）人: 陳皓;張國鑫;賈蓉
• 申請（專利權(quán)）人: 西安郵電大學(xué)
• 主分類號: G06N20/20
• 分類號: G06N20/20;G06N3/12;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種針對分類問題的雙進(jìn)化架構(gòu)自動集成學(xué)習(xí)方法，所述方法包括以下步驟：

步驟1：初始化基學(xué)習(xí)器個體種群，可表示為N_t是基學(xué)習(xí)器個體數(shù)量，分類樹初始最小深度為D_min，最大深度為D_max，節(jié)點(diǎn)生成概率為P_node；每個節(jié)點(diǎn)Node由一個四元組表示，每個組件都是一個數(shù)值，可以在進(jìn)化過程中進(jìn)行修改，四元組中第一個元素是分裂屬性的整數(shù)索引；第二個是實(shí)數(shù)，表示閾值的分割值；第三個是整數(shù)，1表示該節(jié)點(diǎn)是終端節(jié)點(diǎn)，0表示該節(jié)點(diǎn)是非終端節(jié)點(diǎn)；第四個是預(yù)測的分類標(biāo)簽值，具體為：

步驟1.1：生成根節(jié)點(diǎn)，從訓(xùn)練樣本中隨機(jī)選擇一個特征并隨機(jī)選擇該特征的分割閾值作為當(dāng)前節(jié)點(diǎn)的內(nèi)部屬性；

步驟1.2：遞歸的生成樹結(jié)構(gòu)，當(dāng)樹的深度大于D_min且小于D_max時，則生成隨機(jī)數(shù)Rand與P_node比較，若小于P_node則生成中間節(jié)點(diǎn)，從訓(xùn)練樣本中隨機(jī)選擇一個特征并隨機(jī)選擇該特征的分割閾值作為節(jié)點(diǎn)的內(nèi)部屬性；若大于P_node則生成葉子節(jié)點(diǎn)，隨機(jī)選擇分類標(biāo)簽作為節(jié)點(diǎn)的內(nèi)部屬性；當(dāng)樹的深度等于D_max時，執(zhí)行步驟1.3；

步驟1.3：當(dāng)樹的深度等于D_max時，則生成葉子節(jié)點(diǎn)，隨機(jī)選擇分類標(biāo)簽作為該節(jié)點(diǎn)的內(nèi)部屬性，然后轉(zhuǎn)至步驟2；

步驟2：基學(xué)習(xí)器個體的搜索過程，在雙進(jìn)化搜索過程中我們依靠針對樹形編碼設(shè)計的交叉和變異機(jī)制來產(chǎn)生基學(xué)習(xí)器子代個體，節(jié)點(diǎn)交叉概率為P_cross，節(jié)點(diǎn)變異概率為P_muate，具體為：

步驟2.1：交叉操作，首先從決策樹群體T中隨機(jī)選擇兩個個體t_i和t_j，并分別從根節(jié)點(diǎn)開始向下遍歷，每遍歷一個節(jié)點(diǎn)生成隨機(jī)數(shù)Rand與P_cross比較，若小于P_cross則當(dāng)前節(jié)點(diǎn)為一個交叉點(diǎn)，否則繼續(xù)遍歷；當(dāng)兩個個體都確定交叉點(diǎn)后，如果兩個交叉點(diǎn)都是終端節(jié)點(diǎn)則交換交叉點(diǎn)的分類標(biāo)簽，否則將兩個叉點(diǎn)的子樹進(jìn)行交換；

步驟2.2：變異操作，變異將對分類樹進(jìn)行局部調(diào)整，具體方式包括：改變節(jié)點(diǎn)上的數(shù)值，以及改變節(jié)點(diǎn)的分支結(jié)構(gòu)；首先對交叉后生成的子代群體中每個個體t_i，從樹的根節(jié)點(diǎn)開始遍歷，每經(jīng)過一個節(jié)點(diǎn)生成隨機(jī)數(shù)Rand與P_muate比較，若小于P_muate則當(dāng)前節(jié)點(diǎn)為選擇的變異節(jié)點(diǎn)，結(jié)束遍歷，然后按相等的概率隨機(jī)選擇上述的方式對節(jié)點(diǎn)進(jìn)行變異；

步驟3：集成學(xué)習(xí)器個體的搜索過程，一個集成器個體e可用一個二進(jìn)制串表示，若e(i)＝1表示決策樹t_i被選中，若e(i)＝0則表示決策樹t_i沒有被選中，故e可表達(dá)決策樹群體的一個子集，集成器的搜索將基于二進(jìn)制遺傳算法來實(shí)現(xiàn)對當(dāng)前基學(xué)習(xí)器父代群體中個體的組合優(yōu)化，具體為：

步驟3.1：交叉操作：參與交叉的父輩個數(shù)k從2到群體規(guī)模N之間隨機(jī)確定，公式如下：

其中，i＝{1，2，...，N}為個體的基因編碼位數(shù)，j＝{1，2，...，k}為父輩個體數(shù)，e_j(i)為第j個父輩個體的的第i位基因編碼，e′(i)為交叉操作產(chǎn)生的子代個體的第i位基因編碼，sign(·)為符號函數(shù)對當(dāng)前累加和大于0時取1，小于或等于0時取0，W_j為第j個父輩準(zhǔn)確度值在所有父代個體準(zhǔn)確度值總和中所占的比重；

步驟3.2：變異操作，對集成交叉產(chǎn)生的所有個體e_i，以1/N的概率隨機(jī)翻轉(zhuǎn)的每一位基因，生成變異個體，N為每個個體的基因長度；

步驟4：評估機(jī)制；

步驟4.1：基學(xué)習(xí)器個體的評估，分類樹的多樣性是衡量樹群中子樹之間的差異性，公式如下：

其中f_DF(t_i)表示決策樹t_i在種群中的相似度，DF(t_i，t_j)是t_i和t_j兩個個體對相同樣本都預(yù)測錯誤的數(shù)量，Spl是樣本總數(shù)，當(dāng)f_DF(t_i)＝1時表示多樣程度最低，f_DF(t_i)目的是減少種群中個體之間常見錯誤的重疊，以使不同個體的輸出彼此不相關(guān)；因?yàn)榉诸悩涫嵌鏄洌乙呀?jīng)限制了樹的橫向生長，故通過對最大深度的限制可以降低決策樹的復(fù)雜度，因此決策樹復(fù)雜度可定義如下：

f_depth(t_i)＝max_depth(t_i) (5)

其中max_depth(t_i)是個體t_i的最大深度；分類樹與其他個體的協(xié)作程度也就是對集成器的貢獻(xiàn)程度，這個指標(biāo)衡量了分類樹參與集成后的平均表現(xiàn)，公式如下：

其中f_coop(t_i)表示t_i與群體中其它個體的協(xié)作程度，hum是在集成進(jìn)化過程中t_i被選中的次數(shù)；f_acc(t_i∈E)表示集成模型E包含決策樹t_i時的準(zhǔn)確率，表示集成模型E去除決策樹t_i時的準(zhǔn)確率，兩個的差值作為t_i對集成模型E的貢獻(xiàn)，f_coop(t_i)越小代表t_i與其它成員的協(xié)作程度越好，如果t_i沒有參與任何集成無法評估其表現(xiàn)，在這種情況下f_coop(t_i)默認(rèn)為0.5；分類樹的準(zhǔn)確度是分類樹對樣本預(yù)測正確所占的比例，公式如下：

其中f_acc(t_i)是分類樹t_i的準(zhǔn)確率，Acc(t_i)是對樣本正確分類的數(shù)量；綜合上述考量，分類樹個體需要計算4個指標(biāo)：

F_t(t_i)＝(f_DF(t_i)，f_depth(t_i)，f_coop(t_i)，f_acc(t_i)) (8)

步驟4.2：集成器個體評估，集成器群體優(yōu)化的目標(biāo)是尋找最佳的分類樹組合，適應(yīng)度函數(shù)以準(zhǔn)確率和最小集成規(guī)模為目標(biāo)：

其中，f_acc(e_i)是集成器e_i的分類準(zhǔn)率，len(e_i)是集成器e_i包含的基學(xué)習(xí)器個數(shù)；

步驟5：群體迭代機(jī)制；

步驟5.1：基學(xué)習(xí)器群體進(jìn)行多目標(biāo)選擇，父代個體和搜索產(chǎn)生的子代個體將組成大小為2N的群體，通過多目標(biāo)選擇產(chǎn)生規(guī)模為N的下代群體，具體操作如下：

步驟5.1.1：首先根據(jù)4個目標(biāo)函數(shù)計算群體中所有個體的優(yōu)勢等級(即支配關(guān)系)，然后根據(jù)優(yōu)勢等級進(jìn)行分層；

步驟5.1.2：針對同一層的個體，其他的多目標(biāo)優(yōu)化算法根據(jù)不同的密度估計方法進(jìn)行排序，目的是維護(hù)群體的多樣性，由于在適應(yīng)度評估中已經(jīng)計算了基學(xué)習(xí)器之間的多樣性，這與其他密度估計方法類似，所以同一層個體根據(jù)它們的多樣性進(jìn)行排序；

步驟5.1.3：從優(yōu)勢等級為0的層開始向后續(xù)層次截斷前N個個體作為下代群體，為了與集成學(xué)習(xí)器的編碼對應(yīng)，截斷后的N個下代群體中，來自父代的個體放入原始的編碼位置，來自子代的個體放入空置的編碼位置；此過程中由于被選擇的子代個體比被淘汰的父代個體更優(yōu)秀，所以替換后并不會降低集成學(xué)習(xí)器的性能；

步驟5.2：集成學(xué)習(xí)器群體選擇操作，父代個體和子代個體組成大小為2N的群體，然后依據(jù)集成器個體的準(zhǔn)確度挑選產(chǎn)生規(guī)模為N的下代群體，具體操作如下：

步驟5.2.1：為了保持集成學(xué)習(xí)器之間的多樣性，將每個集成器對驗(yàn)證集的預(yù)測標(biāo)簽作為集成器的特征，然后通過AP聚類算法對集成器進(jìn)行聚類，因?yàn)锳P聚類不需要指定最終的聚類族個數(shù)，并且對數(shù)據(jù)的初始值不敏感，不需要進(jìn)行隨機(jī)選取初值步驟；

步驟5.2.2：聚類后的每個簇內(nèi)都是相似度較高的集成學(xué)習(xí)器集合，故首先在每個簇中按集成學(xué)習(xí)器的準(zhǔn)確度進(jìn)行排名，然后依次從每個簇中選擇前半部分集成器個體加入下代群體，最終獲得個體數(shù)量為N的下代群體；

步驟6：判斷當(dāng)前迭代次數(shù)是否滿足最大迭代次數(shù)，若不滿足則轉(zhuǎn)至步驟2，否則將當(dāng)前基學(xué)習(xí)器群體和最優(yōu)集成器組合作為集成模型，輸出分類結(jié)果。