基于遺傳優化獲取微陣列最佳分類規則

摘要：基于遺傳編程（GP）提出一種最優規則遺傳算法（BRGA）對分類規則進行優化的方法，獲取最佳分類規則集，此算法可以調整分類器模型的相關參數，在適當增加迭代基礎上大幅提高分類的精確度，具有相當的靈活性和可理解性.利用6個基因數據集檢驗了算法的性能.仿真結果表明，本文提出的算法與其他文獻的方法相比，在具有較高分類精確度和穩定性前提下大幅降低了計算復雜度及冗余.



關鍵詞：最優規則遺傳算法;微陣列;遺傳編程;分類規則;計算復雜度

中圖分類號：TP391 文獻標識碼：A

生物醫學研究表明，人類大多數疾病的發病機制，比如癌癥，從根本上來說都和基因息息相關.微陣列數據是將樣本實驗形成的影像轉為基因表達矩陣，矩陣行表示基因，列表示類別樣本，矩陣中的元素描述不同基因在不同樣本的表達水平.

由于微陣列芯片技術［1］獲得的基因數據數量遠大于樣本數量，隨著維數的增加，最大的障礙則是在高維特征空間運算時存在的“維數災難”.微陣列大量基因數據僅為樣本分類提供了少數有分類意義的、具有明顯特征的基因.因此，在樣本分類之前，選擇特征基因是至關重要的，這直接影響到之后生成的分類器性能.微陣列分類作為生物指標的探索成為生物信息學一個重要的課題，事實上，由于存在更多的癌癥類型和潛在的癌癥子類，如果展開腫瘤分類問題到多重腫瘤類別，數據集包含更多的類別和非常少量的樣本，問題將變得更具有挑戰性.

一些研究報告指出，在基因選擇部分使用遺傳算法能改進微陣列數據的分類性能［1-2］，因此，遺傳算法已廣泛用于解決包括數據分類的各種難題［3-4］.本文提出一種最優規則遺傳算法（Best Rule Genetic Algorithm，BRGA），選用一種基于遺傳優化的分類算法生成分類規則，用二進制向量表示分類規則，初始化規則集，設定相應的適應度及初始種群的規模，通過變異產生一定數量的最優分類規則.通過實驗，使用6個基因表達數據集來驗證算法的性能.

微陣列數據分類技術通常包含2部分內容：1）基因選擇；2）構建分類器模型.文獻［5］在基因選擇部分使用排列值計分RBS算法，很好地解釋了基因之間的相關性，大幅降低基因矩陣維度，在一定程度上減少了計算復雜性；在構建分類器部分提出了LCR方法，可以用很少的基因構造形成分類規則，提高了算法的可理解性.但分類規則的形成過程仍存在很多不足，如分類器模型中規則形成框架過于縝密，容易導致過擬合，產生龐大規則集的迭代過程相當繁瑣，并產生大量冗余的規則，導致計算復雜度較高且算法收斂速度較低.分類器的構建則是整個技術的核心所在，傳統的微陣列分類方法有：加權投票(WV)［6］，K近鄰（kNN）［7］，支持向量機（SVM）［8］，費舍爾線性判別分析(LDA)［9］ ，人工神經網絡（ANN）［10］，遺傳規劃（GP）［11］，最小二乘邏輯回歸［12］和樸素貝葉斯方法［13］等.由于它們僅僅聚焦于分類性能，而不能進一步提供任何醫學和生物學依據，導致這些分類算法往往產生僵硬的分類系統，存在穩定性弱和開銷大的特征，缺乏可擴展性.決策樹算法［14］和隨機森林算法［15］基于決策規則產生分類器模型，此類算法獲得的分類規則在某種意義上包含了生物體基因之間的相關性，但如果訓練樣本存在小的差異會導致決策樹結構產生大的變化，致使分類器缺乏穩定性，這些分類方法仍然存在很大的局限性.

1 BRGA方法的基本思想

BRGA算法是在遺傳優化的基礎上，將分類規則集作為種群，使用二進制串表示其中任意一條分類規則，計算對應于基因屬性的比較關系的分類規則適應度值，經過若干代的繁殖過程，包括選擇、交叉和變異運算，反復迭代優化，獲取具有較高適應度的最佳分類規則.

4 結論

本文提出的BRGA算法很好地解決了用微陣列基因表達值構建分類決策規則普遍速度慢的難題，通過調整適合規則的適應度值及相關參數對初始規則集進行優化，該算法能很快收斂于最優分類規則集.采用6個數據集驗證了該算法的性能，實驗結果表明，BRGA算法具有較高的精確度和極少的分類運算耗時（CPU time）.當然，由于實驗條件和生物學發展的局限性，該算法有待進一步提高和完善.

參考文獻

［1］ HENGPRAPROHM S，MUKVIBOONCHAI S，THAMMASANG R，et al.A GAbased classifier for microarray data classification［C］// Proceedings of 2010 International Conference on Intelligent Computing and Cognitive Informatics(ICICCI 2010).Kuala Lumpur:IEEE Computer Society，2010:199-202.

［2］ OOI C H，TAN P.Genetic algorithms applied to multiclass prediction for the analysis of gene expression data［J］.Bioinformatics，2003，19 (1):37-44.

［3］ BANDYOPADHYAY S，MURTHY C A，PAL S K.Pattern classification with genetic algorithms［J］.Pattern Recognition Letters，1995，16(8):801-808.

［4］ BANDYOPADHYAY S，MURTHY C A，PAL S K.VGAclassifier: design and applications［J］. IEEE Transactions on Systems， Man and CyberneticsPart B，Cybernetics，2000， 30(6)：890-895.

［5］ GANESHKUMAR P，AMMU V，VICTOIRE T A A.Building decision rules using a novel data driven method for microarray data classification［C］//2011 International Conference on Process Automation，Control and Computing(PACC 2011).Coimbatore:IEEE Express Conference Publishing，2011:1-6.

［6］ GOLUB T R，SLONIM D K，TAMAYO P，et al.Molecular classification of cancer: class discovery and class prediction by gene expression monitoring［J］.Science，1999，286(5439):531-537.

［7］ WU Wei， XING E P，MYERS C，et al.Evaluation of normalization methods for cDNA microarray data by kNN classification［J］.BMC Bioinformatics，2005，6:191-211.

［8］ YOONKYUNG L，CHEOLKOO L .Classification of multiple cancer types by multicategory support vector machines using gene expression data［J］. Bioinformatics， 2003，19(9): 1132-1139.

［9］ JAEWON L，JUNGBOK L，MIRA P，et al.An extensive comparison of recent classification tools applied to microarray data［J］.Computational Statistics Data Analysis， 2005， 48(4): 869-885.

［10］KHAN J，JUN S，RINGNER M，et al.Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks［J］.Nat Med， 2001，7(6):673-679.

［11］HONG J H，CHO S B. The classification of cancer based on DNA microarray data that uses diverse ensemble genetic programming［J］.Artificial Intelligence in Medicine，2006，36(1):43-58.

［12］TANG E K，SUGANTHAN P N，YAO X.Gene selection algorithms for microarray data based on least square support vector machine［J］. BMC Bioinf，2006，7:95-110.

［13］JOHNSON W E，LI C，RABINOVIC A. Adjusting batch effects in microarray expression data using empirical bayes methods［J］. Biostatistics，2007，8(1):118-127.

［14］YU WANG，IGOR V T，MARK A H，et al.Gene selection from microarray data for cancer classification—a machine learning approach［J］. Computational Biology and Chemistry，2005， 29(1): 37-46.

［15］RAMON D U， SARA A A. Gene selection and classification of microarray data using random forest［J］. BMC Bioinformatics，2006，7:3.

［16］WELSH J B，SAPINOSO L M，SU A I，et al.Analysis of gene expression identifies candidate markers and pharmacological targets in prostate cancer［J］.Cancer Res， 2001，61: 5974-5978.

［17］ALON U，BARKAI N，NOTTERMAN D A，et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays［J］.PNAS， 1999， 96(12): 6745-6750.

［18］Broad Institute. Cancer program data sets［EB/OL］. ［2012-01-01］. http://www.broadinstitute.org /cgibin/cancer/datasets.cgi.

［19］ASH A A，MICHAEL B E，ERIC R D，et al.Distinct types of diffuse large Bcell lymphoma identified by gene expression profiling［J］. Nature， 2000， 403(4): 503-511. 

［20］BHATTACHARJEE A，RICHARDS W，STAUNTON J，et al.Classification of human lung carcinomas by mRNA expression profiling reveals distinct adenocarcinoma subclasses［J］. PNAS， 2001，98(24): 13790-13795.

［21］SCOTT L P，PABLO T，MICHELLE G，et al.Gene expression-based classification and outcome prediction of central nervous system embryonal tumors［EB/OL］. ［2012-01-01］.http://www.broadinstitute.org/mpr/CNS/. 

［22］SHI Chao，CHEN Lihui.Feature dimension reduction for microarray data analysis using locally linear embedding［C］//Proceedings of 3rd AsiaPacific Bioinformatics Conference(APBC 2005).Singapore:Imperial College Press，2005:211-217.

［23］TAN A，NAIMAN D，XU L，et al.Simple decision rules for classifying human cancers from gene expression profiles［J］. Bioinformatics， 2005， 21(20): 3896-3904.

［24］FUREY T S，CRISTIANINI N，DUFFY N，et al.Support vector machine classification and validation of cancer tissue samples using microarray data［J］.Bioinformatics， 2000， 16(10): 906-914.

［25］JUNBAI W，TROND H B，INGE J，et al.Tumor classification and marker gene prediction by feature selection and fuzzy cmeans clustering using microarray data［J］. BMC Bioinformatics，2003， 4:60-71.