TSP算法及其應(yīng)用研究.pdf

1、在系統(tǒng)生物學(xué)中，從大量的數(shù)據(jù)中識(shí)別對(duì)所研究問題具有豐富價(jià)值的信息是一個(gè)十分重要的課題。TSP(Top Scoring Pair)算法是一種基于對(duì)“特征對(duì)”進(jìn)行評(píng)價(jià)且利用得分最高的的“特征對(duì)”建立分類器的算法。由于其簡(jiǎn)單可行以及結(jié)果容易解釋等優(yōu)點(diǎn)使其在基因組學(xué)數(shù)據(jù)分析領(lǐng)域已經(jīng)成為較有利的工具。k-TSP是基于TSP算法的一個(gè)拓展，其與TSP算法最明顯的區(qū)別在于k-TSP算法不是選擇一對(duì)特征，而是選擇“k”對(duì)。
　　本文改進(jìn)了TSP/

2、k-TSP算法的排名準(zhǔn)則，使其更能精準(zhǔn)的挑選出具有區(qū)分能力的特征，與此同時(shí)本文對(duì)判定準(zhǔn)則也進(jìn)行了相應(yīng)的修改以改進(jìn)模型的預(yù)測(cè)能力。本文使用8個(gè)公共數(shù)據(jù)集，通過與改進(jìn)前的TSP算法、隨機(jī)森林、支持向量機(jī)的比較，驗(yàn)證了改進(jìn)后的TSP算法確實(shí)是有效的。并且將修改后的算法應(yīng)用在了肝病血清數(shù)據(jù)上，通過實(shí)驗(yàn)驗(yàn)證知道改進(jìn)后的算法無論從分類性能還是從特征選擇的能力上都得到了提高。本文利用“特征對(duì)”構(gòu)造新變量的方式對(duì)所研究問題進(jìn)行了詳細(xì)分析。基于改進(jìn)后的算

3、法共選出27對(duì)特征，通過PCA分析最終樣本被較為明顯的區(qū)分開。
　　隨機(jī)森林是由一棵棵的樹狀結(jié)構(gòu)的判定規(guī)則（決策樹）構(gòu)成。選擇區(qū)分效果最好的特征作為該節(jié)點(diǎn)的判別特征，然后繼續(xù)生長(zhǎng)就這樣構(gòu)造一棵棵“樹”，再由多棵“樹”構(gòu)成隨機(jī)森林。本文將TSP算法對(duì)“特征對(duì)”的評(píng)價(jià)融入到?jīng)Q策樹節(jié)點(diǎn)的建立中提出了TSP-RF算法。在隨機(jī)森林的每個(gè)節(jié)點(diǎn)產(chǎn)生的過程中，由其隨機(jī)挑選的特征子集和當(dāng)前樣本組成了數(shù)據(jù)矩陣，通過TSP算法可以利用該矩陣計(jì)算出得分最

4、高的“特征對(duì)”，用該“特征對(duì)”建立分類模型與單特征的分類模型進(jìn)行比較，性能更優(yōu)者用于結(jié)點(diǎn)分裂。本文通過12個(gè)公共數(shù)據(jù)集（6個(gè)低維、6個(gè)高維）對(duì)TSP-RF算法分類性能進(jìn)行驗(yàn)證，TSP-RF算法比較于RF算法分類性能在9個(gè)數(shù)據(jù)集上得到了提高。隨機(jī)森林比較重要的兩個(gè)方面是強(qiáng)度與相關(guān)性:單棵決策樹的強(qiáng)度越高越好，決策樹之間的相關(guān)性越低越好。通過強(qiáng)度與相關(guān)性的分析，對(duì)該算法與隨機(jī)森林算法進(jìn)行比較分析，得出的結(jié)論是在強(qiáng)度沒有明顯變化的情況下，相關(guān)