基于ProGEP的代價敏感分類算法研究.pdf

1、近年來數(shù)據(jù)挖掘技術(shù)被廣泛應(yīng)用在市場營銷、商業(yè)管理、企業(yè)危機管理、產(chǎn)品制造和Internet等方面。目前全世界計算機存儲的未使用的海量數(shù)據(jù)還在快速增長，數(shù)據(jù)類型和結(jié)構(gòu)也愈發(fā)復雜，這對降低挖掘成本，提高算法效能均帶來嚴峻的挑戰(zhàn)。因此，改進挖掘算法流程、提高算法運行效率對于高效取得較為滿意的挖掘結(jié)果有著重要意義。
　　本文就對數(shù)據(jù)挖掘中常用的遺傳算法衍生的一種新算法——基因表達式編程展開研究并作出相關(guān)改進，提出并設(shè)計 ProGEP算法，

2、并將該算法應(yīng)用于代價敏感分類問題，設(shè)計并實現(xiàn)了CSC-ProGEP算法。主要工作有以下四個方面：
　　1.綜述了國內(nèi)外GEP及代價敏感學習算法的研究現(xiàn)狀；概述了GEP算法的構(gòu)成及流程；簡述了目前幾種常用的代價敏感分類算法。
　　2.改進GEP算法并提出ProGEP算法。針對基本GEP算法重復遍歷表達式樹的染色體評估方法效率低下的不足，在研究目前流行的改進算法——基因閱讀運算器的改進思想后，提出了逆波蘭表達式——堆棧法評估（R

3、PE_SD），通過后續(xù)遍歷一次表達式樹獲得逆波蘭表達式，采用重復讀取線性的堆棧結(jié)構(gòu)進行存儲和計算，實現(xiàn)染色體評估效率的提高；其次，就基本GEP未給定具體常數(shù)參數(shù)的生成方法和完全隨機化的初始種群生成方式指出給定合理的常數(shù)參數(shù)的必要性和向種群插入優(yōu)勢個體對進化初期的促進作用，提出粗糙的多元線性回歸初始化——自適應(yīng)修正常數(shù)（RMLR_AC），該算法將多元回歸獲得的全變量系數(shù)參數(shù)作為常數(shù)變量引入染色體的基因表達式結(jié)構(gòu)中，并通過進化過程實現(xiàn)系數(shù)常

4、數(shù)的修正；再次，觀察發(fā)現(xiàn)基本GEP在進化種群中存在染色體個體基因型相同的現(xiàn)象，定義了重復染色體及隱重復染色體的概念，研究指出該現(xiàn)象的產(chǎn)生原因及對基因片多樣性、進化效率的不利影響和對種群其他個體的惡性同化作用，提出消除（隱）重復個體（DSC）算法，并通過創(chuàng)建種群副本進行二次選擇（CPCSC）來改進GEP選擇流程；最后，再次觀察種群結(jié)構(gòu)特征，指出并定義了GEP的同族染色體和種族斷層現(xiàn)象，為避免該現(xiàn)象存在導致的基因片在全種族范圍內(nèi)的交流受阻及

5、進化結(jié)果向局部最優(yōu)解收斂，提出基于線程機制的周期性種群多樣性分化（TM_PDI）改進進化流程，并給出對主線程的種群進行排序后再分段克隆，補充隨機化個體（SHS_RRI）的初始化子線程種群算法。融合基本GEP算法和上述的四點改進，本文提出并描述了ProGEP算法。
　　3.將ProGEP應(yīng)用于代價敏感分類問題。通過構(gòu)建代價敏感矩陣并融入 ProGEP的適應(yīng)度函數(shù)，獲得CSC-ProGEP算法。在描述該算法流程的基礎(chǔ)上，本文給出了對稀

6、有類分類效果的評判方法。
　　4.實驗環(huán)境的構(gòu)建與算法的驗證及應(yīng)用。由于對基本GEP的基因評估算法、選擇流程、進化流程等方面均作出修改，為了能方便地描述算法細節(jié)，靈活地進行實驗結(jié)果的統(tǒng)計計算，本文基于Microsoft Visual Studio2012，使用 C＃語言，采用面向?qū)ο蟮脑O(shè)計方法實現(xiàn)了GEP基本模型結(jié)構(gòu)以及ProGEP相關(guān)改進。實驗驗證了ProGEP的算法性能及CSC-ProGEP的應(yīng)用效果。為獨立觀察每個改進帶來的

7、提升，將四個改進分步引入 GEP，多次實驗后觀察比對引入前后的效果。在驗證 ProGEP的有效性之后，選取五組UCI數(shù)據(jù)集，采用10-折交叉驗證法進行CSC實驗，并將獲得的分類器和其他分類算法訓練的分類器比較，實驗表明 CSC-ProGEP在解決代價敏感分類問題中，相對于傳統(tǒng)分類算法（C4.5、BN、BP）和代價敏感分類算法（AdaCost），在保證了分類準確率的同時也獲得了更高的稀有類召回率及精度。
　　本文所做研究的意義，一方