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

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

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

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

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

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

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

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