【正文】 獲得最佳信息基因子集 *T 。 2 2 2 221111( ) ( ( ( ) / ( ) ) l n(( ) / ( 2 ) ) ) / 242cc j k j k j k j ki i i i i i i i ijkkjBFS C g ? ? ? ? ? ? ? ??? ?? ? ? ? ??? (7) 秩和檢驗(yàn)方法 采用 Bhattacharyya 距離及其變體需要假設(shè)數(shù)據(jù)服從高斯分布才能獲得最佳效果，而 當(dāng)數(shù)據(jù)不服從高斯分布時，這些信息基因選擇方法便不能獲得最佳實(shí)驗(yàn)結(jié)果 ,采用 Bhattacharyya 距離度量基因的分類能力便失去了理論基礎(chǔ) 。 Wilcoxon 秩和檢驗(yàn)方 法并不要求數(shù)據(jù)滿足某種分布假設(shè)且這種方法也非常適合小樣本數(shù)據(jù)集，它 根據(jù)基因表達(dá)數(shù)據(jù)的大小排序，然后得到數(shù)據(jù)的秩，再利用數(shù)據(jù)的秩而不是數(shù)據(jù)本身計(jì)算基因的秩和統(tǒng)計(jì)量。 陸巍等 [23]分別采用這兩種非參數(shù)秩和檢驗(yàn)方法以選擇腫瘤相關(guān)基因并分類腫瘤樣本集 亦 獲得了很好的實(shí)驗(yàn)結(jié)果。以 這一假設(shè) 為基礎(chǔ) 設(shè)計(jì)了一種 啟發(fā)式寬度優(yōu)先 搜索算法 (Heuristic Breadthfirst Search Algorithm, HBSA)以用于信息基因精選 。 HBSA 擴(kuò)展 搜索樹是 在 HBSA 算法搜索信息基因子集的過程中生成的，首先生成一個根結(jié)點(diǎn)，其值設(shè)定為： ?? ， ??pathN .10 ， ?parentN ， ?cN ， 并 對 根結(jié)點(diǎn)擴(kuò)展 p 個結(jié)點(diǎn) ， 且 置}{.1 jj gsetN ? ， }{.1 jj gpathN ? ， 且 pjGg j ??? 1,* ，然后對這 p 個結(jié)點(diǎn)進(jìn)行第 2 層擴(kuò)展， 因?yàn)?*G 是初選出來的 信息 基因集合，所以其結(jié)點(diǎn)擴(kuò)展實(shí)際上已經(jīng)利用了單個基因的分類能力啟發(fā)信息 )( jgBFSC ，每一個結(jié)點(diǎn) pjN j ??1,1 擴(kuò)展 1?p 個 子 結(jié)點(diǎn) ， 則第 2 層結(jié)點(diǎn)共有 )1( ?pp 個結(jié)點(diǎn)， 且置 }{.2 ij gsetN ? ，p a t hp a r e n tNs e tNp a t hN jjj .... 222 ?? ， ).(. 22 p a thNA cccN jj ? ， p a t hp a r e n tNgGg jii ..2* ??? ， 6 )1(1 ??? ppj ， pi??1 ， 再把 第 2 層的所有結(jié)點(diǎn) 按 降序排列， 檢查 ).m ax(arg2)1(1m a x cN jA c c ppj ????是否 滿足要求，如果滿足，則 算法 找到了滿足條件的基因子集，否則 選擇 排在 前 面的 p 個結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，繼續(xù)類似搜索。 顯然， HBSA 算法的搜索寬度 并不隨搜索深度的增加而 大幅 增加，因此，算法實(shí)際上是一個帶有啟發(fā)信息的定向柱形搜索算法 。 HBSA 算法還可以根據(jù)具體情況靈活使用，比如在選擇每一層的待擴(kuò)展節(jié)點(diǎn)時，未必每次都 固定 選擇 前 p 個 節(jié)點(diǎn)，也可以選擇 分類能力大于某一閾 值的所有節(jié)點(diǎn)作為待擴(kuò)展節(jié)點(diǎn)，這種情況下需要為每一層設(shè)置不同的 閾值，且下一層的閾值大于上一層的閾 值 ， 顯然這會 導(dǎo)致每一層所 選擇的待擴(kuò)展結(jié)點(diǎn)的數(shù)量不同，但 優(yōu)點(diǎn)是增加了算法的適應(yīng)性，其中 閾 值的設(shè) 定非常關(guān)鍵 。為實(shí)現(xiàn)上的方便 定義 了 分類矩陣pwjiaCM ?? )( , ， 直觀表示如式 (8)。 下面給出 HBSA 算法實(shí)現(xiàn)的基本框架 ， 算法中的 )(TAcc 可以采用 分類器 對樣本的實(shí)際分類準(zhǔn)確率來度量 ，我們的 實(shí)驗(yàn)采用 SVM 分類器來 完成對腫瘤數(shù)據(jù)集的分類任務(wù)，這時 )(TAcc 返回 信息基因子集 T 對 腫瘤 樣本 集 的 SVM 分類 準(zhǔn)確率 。 //B 為一數(shù)組，用以保存每個基因的 BFSC 分值 ； 3. End for 4. B:=Sort(B)。 //選擇前 p 個基因 構(gòu)成 初選信息 基因集合 *G ； 6. For each gene *Ggi? 7. }{:][ igiColumn ? ； 8. ][:][ iC o lu mniR o w ? ； 9. End for 10. iter:=1； 11. Repeat //第一次迭代求 CM 時， CM 為一個對稱矩陣 ,所以只需求下三角陣 ； 12. 構(gòu)造分類矩陣 CM ， 使 Row 的每一個分量依次對應(yīng)于 CM 每一行， 使 Column 依次對應(yīng)于 每一列； 13. 計(jì)算分類矩陣 CM ， ])[][(, jC o l u m niR o wA c ca ji ?＝ ； //計(jì)算前需要對 ][][ jC o lu mniR o w ?所標(biāo)記的樣本集做規(guī)格 化處理 (均值為 0，方差為 1)； 14. 把分類矩陣 CM 轉(zhuǎn)化為一維向量 ),( 21 pwvvvV ?? ? ， 使每一個分量][][].)1[( jC o l u m niR o ws e tjpiV ????－ ， jiacjpiV ,].)1[( ???－ ， 然后對 V 中的 分量 按 信息 基因子集的分類性能 指標(biāo) 降序排列 ，并選出前 w 個分量， 重新構(gòu)造 行標(biāo)記向量setiViRow ].[:][ ? ， wi??1 。 17. Until )100( ?accuracy or )iter( Depth＝ ； //當(dāng)分類準(zhǔn)確率達(dá) 到 100%或迭代 深度 達(dá)到預(yù)定 值Depth 時循環(huán)結(jié)束； 18. 依次選出 V 中分類 性能最大的 信息基因子集 ，并加入到 *A 中 ； 19. Return *A 。 對于能夠以 100％準(zhǔn)確率來分類的腫瘤樣本數(shù)據(jù)集，當(dāng) HBSA 算法發(fā)現(xiàn)了能夠以 100％準(zhǔn)確率來分類樣本集的信息基 因子集后，算法就結(jié)束了，但是對于不能夠以 100％準(zhǔn)確率來分類的腫瘤樣本數(shù)據(jù)集， 算法則執(zhí)行到指定的迭代 深度 Depth 時 結(jié)束，但我們并不知道 Depth 設(shè)為何值比較合適， Depth 值設(shè)置不當(dāng)會導(dǎo)致求得的信息基因子集 遠(yuǎn)離最佳條件 。 算法中最耗時的操作是 計(jì)算 )(TAcc ，如果把 計(jì)算 )(TAcc 看成 耗費(fèi) 一個 單位時間的 基本操作，則計(jì)算一次 CM 的時間復(fù)雜度為 )( pwO ? ，整個算法的時間復(fù)雜度為 )( pwDe pthO ?? 。 支持向量機(jī) SVM 是由 Vapnik[26]提出的基于統(tǒng)計(jì)學(xué)習(xí)理論并采用結(jié) 構(gòu)風(fēng)險(xiǎn)最小化原理的一種機(jī)器學(xué)習(xí)方法，具有較強(qiáng)的泛化能力， 采用數(shù)量有限 的訓(xùn)練集就可以得到一個針對獨(dú)立測試集的分類錯誤率相對較小的分類模型 。 我們的 實(shí)驗(yàn)采用了 Chang 等 開發(fā)的支持向量機(jī)軟件 LIBSVM[30]， 訓(xùn)練 SVM 需要指定調(diào)整參數(shù) C 和核函數(shù)參數(shù) ? 。通常 在分類前樣本 集已經(jīng)過規(guī)格 化處理，所以樣 本集對參數(shù) C 不敏感，因此 ， 在 實(shí)驗(yàn)中參數(shù) C 分別取 200、 400、 600、 800 和 1000 即可滿足需求 ， 而參數(shù) ? 可以這樣取值：對 C 的每一個取值，如果 ? 值在 110－ 量級則 ? 分別取 , ? ，如果 ? 值在210－ 量級則 ? 分別取 , ? ，依次類推， 限定 ? 最小取值在 510－ 量級， 最大取值在 10量級， 8 這相當(dāng)于在一個受限的二維網(wǎng)格上搜索最佳參數(shù)對，實(shí)驗(yàn)表明這是一個有效的尋找最佳參數(shù)對 （ C ， ? ）的方法 ，且能大 幅 減少計(jì)算量 。在腫瘤分類 領(lǐng)域， 通常采用 k折交叉驗(yàn)證方法 (kfold Cross Validation, kfold CV)來評估分類模型的泛化性能， 但 問題是究竟 k 取何值時 能夠獲得最佳的分類準(zhǔn)確率，或者說是哪種 k折交叉驗(yàn)證分類準(zhǔn)確率更能客觀反映腫瘤分類模型的泛化性能 。 我們的 實(shí)驗(yàn)發(fā)現(xiàn)，樣本集的不同劃分對分類準(zhǔn)確率有一定的影響 ，且 5折或 10折交叉驗(yàn)證分類準(zhǔn)確率也不能客觀反映腫瘤分類模 型的泛化性能。 記 ()CVk 表示 樣本集的 k折交叉驗(yàn)證 分類 準(zhǔn)確率， 其中 2 km?? ， m 為樣本總數(shù)， 則分類準(zhǔn)確率均值 定義為：21 ( ( ) )1 mkm e a n C V km ?? ? ?，而標(biāo)準(zhǔn)差 定義為：22( ( ( ) )2mkC V k me anstd m??? ?? 。 然而在 HBSA 算法中直接采用全折交叉驗(yàn)證分類準(zhǔn)確率作為啟發(fā)信息會大幅增加計(jì)算量，因此我們 首先 采用 計(jì)算量相對較小的 4折 交叉驗(yàn)證 分類準(zhǔn)確率作為 HBSA 算法的啟發(fā)信息， 搜索出所有具有最 高 4折交叉驗(yàn)證分類準(zhǔn)確率的 最佳信息 基因子集 *A 后，再采用 全折交叉驗(yàn)證方法來評估 *A 中的 基因子集 ， 實(shí)驗(yàn)證明 采用這種評估方法獲得的分類模型的分類性能與具體的樣本劃分關(guān)系不大。 在公開 發(fā)布的腫瘤數(shù)據(jù)集中，結(jié)腸癌數(shù)據(jù)集是最難分類的 腫瘤 數(shù)據(jù)集 之一 ， 絕大多數(shù) 分類 方法都很難 以 100％的 交叉驗(yàn)證 準(zhǔn)確率來分類該數(shù)據(jù)集。 表 1 網(wǎng)上發(fā)布的 與腫瘤有關(guān)的 二分類 樣本 集 （ Leukemia 和 Colon Tumor） 序號 數(shù)據(jù)集名稱與下載網(wǎng)址 基因數(shù)量 樣本總量 正類樣本數(shù)量 負(fù)類樣本數(shù)量 1 急性白血病數(shù)據(jù)集 (Leukemia Dataset)[1] 7,129 72 47(ALL) 25(AML) 2 結(jié)腸癌數(shù)據(jù)集 (Colon Tumor Dataset)[33] 2,000 62 40(Tumor) 22(Normal) 我們從網(wǎng)站 下載了 SRBCT 數(shù)據(jù)集，該數(shù)據(jù)集包括 88個樣本，每一個樣本包含 2,308 個基因。 63 個訓(xùn)練樣本包括 23 個 Ewing 腫瘤亞型 (EWS)、 20 個 rhabdomyosara 腫瘤亞型 (RMS)、 12 個 neuroblastoma 腫瘤亞型 (NB)和 8 個 Burkitt lymphomas 腫瘤亞型 (BL)。 表 2 SRBCT 數(shù)據(jù)集的特點(diǎn)描述 腫瘤亞型 原數(shù)據(jù)集 訓(xùn)練集 測試集 EWS 29 23 6 9 NB 18 12 6 RMS 25 20 5 BL 11 8 3 NonSRBCT 5 0 5 Total 88 63 25 實(shí)驗(yàn)方法 針對 Leukemia、 Colon Tumor和 SRBCT 三種腫瘤樣本集分別設(shè)計(jì)了三種實(shí)驗(yàn)方法： BFSC+HBSA+SVM、Wilcoxon+HBSA+SVM 和 KruskalWallis+HBSA+SVM，分別把這三種方法命名為方法 方法 2 和方法 3。對 表3 中其它行的 解釋與此相同，且 所有實(shí)驗(yàn)結(jié)果都是采用 4折交叉驗(yàn)證方法獲得的 。 表 3 實(shí)驗(yàn)中 針對三種 腫瘤樣本 集 的閾值設(shè)定情況 實(shí)驗(yàn)方法 數(shù)據(jù)集 兩基因子集 三基因子集 四基因子集 方法 1 BFSC+HBSA+SVM Leukemia 100%（ 7 個） N N Colon Tumor 90%（ 129 個） 95%（ 137 個） 100%（ 2 個） SRBCT 82%（ 216 個 ） 96%（ 92 個） 100%（ 433 個） 方法 2 Wilcoxon+HBSA+SVM Leukemia 100%（ 14 個） N N Colon Tumor 90%（ 230 個） 95%（ 307 個） 100%（ 7 個） 方法 3 KruskalWallis+HBSA+SVM SRBCT 83%（ 221 個） 96%（ 93 個） 100%（ 504 個） 實(shí)驗(yàn)結(jié)果 與分析 FSC 與 BFSC方法的比較 首先采用 FSC 和 BFSC 兩種 特征記分準(zhǔn)則 為每一個基因 Gg? 計(jì)算分值，然后 按每一個基因分值大小降序排列基因，并記 itop 表示排在前面的 i 個基因 所構(gòu)成的信息基因子集，圖 3 繪制了 針 對 Leukemia 和Colon Tumor 兩種數(shù)據(jù)集的 )701( ?? itopi 的 4折交叉驗(yàn)證分類準(zhǔn)確率的變化情況 。 對于 Colon Tumor 數(shù)據(jù)集， 采用 BFSC 方法 選出的 信息基因子集的分類性能也是 略 優(yōu) 于 FSC 方 法 ， 因?yàn)椴?用 BFSC 方法 獲 得了最高 CV 分類 準(zhǔn)確 率為 %的 信息基因子集，但采 用FSC 方 法只獲得了最高為 %的 CV 準(zhǔn)確 率 。 10 圖 3 Leukemia 和 Colon Tumor 兩個數(shù)據(jù)集 的 )701( ?? itopi 的分能性能比較 實(shí)驗(yàn)結(jié)果 表 4 給出了 采用 方法 1 在三種腫瘤數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn) 所獲得的 部分實(shí)驗(yàn)結(jié)果 ，表中的 C 和 ? 欄 表示分類器 SVM（ RBF） 所需要的參數(shù)，其值表示 相應(yīng)基因子集獲得最高 4折交叉驗(yàn)證分類準(zhǔn)確率時的參數(shù)取值（最佳參數(shù)對的取值 并不是唯一的） ， max 欄表示 相應(yīng)基因子集獲得的最 高 4折交叉驗(yàn)證分類準(zhǔn)確率， mean和 std 分別表示相應(yīng)基因子集 的全折交叉驗(yàn)證分類準(zhǔn)確率和標(biāo)準(zhǔn)差 。對于 Leukemia 數(shù)據(jù)集，兩個信息基因 子集 {X95735, HG1612HT1612}和 {L09209, X68560}都獲得了 100%的全折交叉驗(yàn)證準(zhǔn)確率； 對于 Colon Tumor 數(shù)據(jù)集 ，四基因子集 {M58050,H06524,R62549,H24030}雖然獲得了100%的 4折交叉驗(yàn)證準(zhǔn)確率，但其全折交叉驗(yàn)證準(zhǔn)確率為 %，表明采用該基因子集來分