【文章內(nèi)容簡介】 p a t hp a r e n tNgGg jii ..2* ??? ， 6 )1(1 ??? ppj ， pi??1 ， 再把 第 2 層的所有結點 按 降序排列， 檢查 ).m ax(arg2)1(1m a x cN jA c c ppj ????是否 滿足要求，如果滿足，則 算法 找到了滿足條件的基因子集，否則 選擇 排在 前 面的 p 個結點作為擴展結點，繼續(xù)類似搜索。 需要注意的是，不同節(jié)點的路徑 所代 表的信息基因集 在不考慮順序的前提下可能相同，因此在計算節(jié)點的分類性能時如果發(fā)現(xiàn)前面已計算過，則該節(jié)點的分類性能 記為 0 以避免擴展不 必要的節(jié)點。 顯然， HBSA 算法的搜索寬度 并不隨搜索深度的增加而 大幅 增加，因此，算法實際上是一個帶有啟發(fā)信息的定向柱形搜索算法 。雖然從局部看選擇 信息 基因的方式采用的是遞增方式，但宏觀看 則是混合方式，因為 那些 沒有潛力的基因組合在搜索過程中被拋棄了 。 HBSA 算法還可以根據(jù)具體情況靈活使用，比如在選擇每一層的待擴展節(jié)點時，未必每次都 固定 選擇 前 p 個 節(jié)點，也可以選擇 分類能力大于某一閾 值的所有節(jié)點作為待擴展節(jié)點，這種情況下需要為每一層設置不同的 閾值，且下一層的閾值大于上一層的閾 值 ， 顯然這會 導致每一層所 選擇的待擴展結點的數(shù)量不同，但 優(yōu)點是增加了算法的適應性，其中 閾 值的設 定非常關鍵 。 10N…… 11N21NpN112N12?pN…… )1(2?ppN…… 21N}{ 1?pg}{ pg}{ pg}{ 1g}{ 2g}{ 2g? 圖 2 啟發(fā)式寬度優(yōu)先 搜索信息基因 子集 示意圖 HBSA算法 實現(xiàn) 在獲得最佳信息基因子集 *A 的過程中， 并不需要真正構造搜索樹， 只需保留每一 次搜索到的滿足給定要求的信息基因 子集及其分類性能指標就能達到預期目標 。為實現(xiàn)上的方便 定義 了 分類矩陣pwjiaCM ?? )( , ， 直觀表示如式 (8)。 111 ,1 1 ,1 ,{ } { }ppww w pggT a aCMT a a????????? (8) 采用 行標記向量 ),( 21 wTTTR o w ?? 依次標記 CM 的每一行，其中 iT ( wi??1 )表示 已選擇的信息基因子集 ， 采用列標記向量 }){},{},({ 21 pgggC o l u m n ?? 依次標記 CM 的每一列 ，其中 *Ggk? ，pk??1 ， 而 ])[][(, jC o l u m niR o wA c ca ji ?＝ ， 其中 wi??1 ， pj??1 。 下面給出 HBSA 算法實現(xiàn)的基本框架 ， 算法中的 )(TAcc 可以采用 分類器 對樣本的實際分類準確率來度量 ，我們的 實驗采用 SVM 分類器來 完成對腫瘤數(shù)據(jù)集的分類任務，這時 )(TAcc 返回 信息基因子集 T 對 腫瘤 樣本 集 的 SVM 分類 準確率 。 算法： HBSA(M , p ,w ,Depth )； 輸入 ： 基因 表達譜 M ,p 為初選信息基因 個數(shù) , w 為選擇的基因子集個數(shù)， Depth 為迭代深度 ； 輸出 ： 最佳 信息基因集合 *A ； 1. For each gene Ggj? do 2. B[j]:= )( jgBFSC 。 //B 為一數(shù)組，用以保存每個基因的 BFSC 分值 ； 3. End for 4. B:=Sort(B)。 //對數(shù)組按降序排列 7 5. *G :=Selected(G ,B, p )。 //選擇前 p 個基因 構成 初選信息 基因集合 *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. 構造分類矩陣 CM ， 使 Row 的每一個分量依次對應于 CM 每一行， 使 Column 依次對應于 每一列； 13. 計算分類矩陣 CM ， ])[][(, jC o l u m niR o wA c ca ji ?＝ ； //計算前需要對 ][][ jC o lu mniR o w ?所標記的樣本集做規(guī)格 化處理 (均值為 0，方差為 1)； 14. 把分類矩陣 CM 轉(zhuǎn)化為一維向量 ),( 21 pwvvvV ?? ? ， 使每一個分量][][].)1[( jC o l u m niR o ws e tjpiV ????－ ， jiacjpiV ,].)1[( ???－ ， 然后對 V 中的 分量 按 信息 基因子集的分類性能 指標 降序排列 ，并選出前 w 個分量， 重新構造 行標記向量setiViRow ].[:][ ? ， wi??1 。 15. ).m ax ( cVa ccu ra cy ? ； 16. iter:=iter+1。 17. Until )100( ?accuracy or )iter( Depth＝ ； //當分類準確率達 到 100%或迭代 深度 達到預定 值Depth 時循環(huán)結束； 18. 依次選出 V 中分類 性能最大的 信息基因子集 ，并加入到 *A 中 ； 19. Return *A 。//算法結束 ,返回搜索到 的 最佳信息基因子集 ，我們認為 *A? 就是與腫瘤 的發(fā)生發(fā)展有 特 定 聯(lián) 系的基因集合 。 對于能夠以 100％準確率來分類的腫瘤樣本數(shù)據(jù)集，當 HBSA 算法發(fā)現(xiàn)了能夠以 100％準確率來分類樣本集的信息基 因子集后，算法就結束了，但是對于不能夠以 100％準確率來分類的腫瘤樣本數(shù)據(jù)集， 算法則執(zhí)行到指定的迭代 深度 Depth 時 結束，但我們并不知道 Depth 設為何值比較合適， Depth 值設置不當會導致求得的信息基因子集 遠離最佳條件 。 對于這種情況，則 以第 iter＋ 1 次迭代求得的最高分類準確率1?iteraccuracy 不大于第 iter 次求得的 iteraccuracy 為迭代結 束條件 是一個比較好的解決方法 。 算法中最耗時的操作是 計算 )(TAcc ，如果把 計算 )(TAcc 看成 耗費 一個 單位時間的 基本操作，則計算一次 CM 的時間復雜度為 )( pwO ? ，整個算法的時間復雜度為 )( pwDe pthO ?? 。盡管 這是一個 多項式時間復雜度算法，但 算法 的執(zhí)行仍然十分耗時，不過 最佳信息基因子集的選擇工作主要在實驗室完 成，臨床應用只是依據(jù)所選擇的 最佳信息基因子集 為標記基因 來診斷腫瘤，所以 HBSA 算法是可行的 。 支持向量機 SVM 是由 Vapnik[26]提出的基于統(tǒng)計學習理論并采用結 構風險最小化原理的一種機器學習方法，具有較強的泛化能力， 采用數(shù)量有限 的訓練集就可以得到一個針對獨立測試集的分類錯誤率相對較小的分類模型 。它將輸入數(shù)據(jù)映射到高維特征空間，構造最優(yōu)分類超平面，用來區(qū)分 帶有 標記的兩 類樣本，當線性不可分時，可用核函數(shù)把數(shù)據(jù)自動地映射到線性空間 ,在腫瘤分類領域常用 Gauss 徑向基核函數(shù) (Radial Basis Function, RBF) )e x p (),( 2yxyxK ??? ?來完成這一任務 [27]， SVM 非常 適合 這種 具有高維和小樣本特點的腫瘤 數(shù)據(jù)集 [28,29]。 我們的 實驗采用了 Chang 等 開發(fā)的支持向量機軟件 LIBSVM[30]， 訓練 SVM 需要指定調(diào)整參數(shù) C 和核函數(shù)參數(shù) ? 。 然而 ， 搜索最佳 參數(shù) 對 （ C ,? ） 是 一件 非常耗時的工作 。通常 在分類前樣本 集已經(jīng)過規(guī)格 化處理，所以樣 本集對參數(shù) C 不敏感，因此 ， 在 實驗中參數(shù) C 分別取 200、 400、 600、 800 和 1000 即可滿足需求 ， 而參數(shù) ? 可以這樣取值：對 C 的每一個取值，如果 ? 值在 110－ 量級則 ? 分別取 , ? ，如果 ? 值在210－ 量級則 ? 分別取 , ? ，依次類推， 限定 ? 最小取值在 510－ 量級， 最大取值在 10量級， 8 這相當于在一個受限的二維網(wǎng)格上搜索最佳參數(shù)對，實驗表明這是一個有效的尋找最佳參數(shù)對 （ C ， ? ）的方法 ，且能大 幅 減少計算量 。 由于分類器的泛化性能涉及它在獨立測試集上的預測能力，因此，分類器性能評估方法在實際的分類器設計中非常重要，因此，如何評估分類器的性能 是一個值得 進一步 探討的問題。在腫瘤分類 領域， 通常采用 k折交叉驗證方法 (kfold Cross Validation, kfold CV)來評估分類模型的泛化性能， 但 問題是究竟 k 取何值時 能夠獲得最佳的分類準確率，或者說是哪種 k折交叉驗證分類準確率更能客觀反映腫瘤分類模型的泛化性能 。 由于腫瘤樣 本規(guī)模小，許多文獻采用留一法 (Leaveoneout Cross Validation, LOOCV)來評估腫瘤分類模型，但是 , Breiman 等 [31]認為 5折 或 10折 交叉驗證方法優(yōu)于留一法 ，而 Asyali 等 [32]針對基因表達譜樣本集的交叉驗證評估方法也是這樣推薦的 。 我們的 實驗發(fā)現(xiàn)，樣本集的不同劃分對分類準確率有一定的影響 ，且 5折或 10折交叉驗證分類準確率也不能客觀反映腫瘤分類模 型的泛化性能。為消除樣本集的不同劃分對分類器泛化性能的影響，有必要設計 一種能夠客觀反映分類器性能的評估方法。 記 ()CVk 表示 樣本集的 k折交叉驗證 分類 準確率， 其中 2 km?? ， m 為樣本總數(shù)， 則分類準確率均值 定義為：21 ( ( ) )1 mkm e a n C V km ?? ? ?，而標準差 定義為：22( ( ( ) )2mkC V k me anstd m??? ?? 。 因此， 具有最大分類準確率均值與最小標準 差的基因子集的泛化誤差也是最小的 ，稱這種評估方法 為全折交叉驗證方法，采用這種方法獲得的分類準確率 均值 被稱為全折 交叉驗證分類準確率 ，而標準差表示樣本集的不同劃分對分類準確率的 影響程度 。 然而在 HBSA 算法中直接采用全折交叉驗證分類準確率作為啟發(fā)信息會大幅增加計算量，因此我們 首先 采用 計算量相對較小的 4折 交叉驗證 分類準確率作為 HBSA 算法的啟發(fā)信息， 搜索出所有具有最 高 4折交叉驗證分類準確率的 最佳信息 基因子集 *A 后，再采用 全折交叉驗證方法來評估 *A 中的 基因子集 ， 實驗證明 采用這種評估方法獲得的分類模型的分類性能與具體的樣本劃分關系不大。 4 實驗 實驗數(shù)據(jù) 為便于實驗結果比較，我們采用了三種研究得 比較充分的腫瘤數(shù)據(jù)集，一種是白血病數(shù)據(jù)集 (Leukemia dataset)[1]， 一種是結腸癌數(shù)據(jù)集 (Colon Tumor dataset)[33]，另一種是多腫瘤亞型的 SRBCT 數(shù)據(jù)集 [13]。 在公開 發(fā)布的腫瘤數(shù)據(jù)集中，結腸癌數(shù)據(jù)集是最難分類的 腫瘤 數(shù)據(jù)集 之一 ， 絕大多數(shù) 分類 方法都很難 以 100％的 交叉驗證 準確率來分類該數(shù)據(jù)集。 由于 Leukemia 和 Colon Tumor 這兩個數(shù)據(jù)集都是二分類數(shù)據(jù)集， 所以不妨稱一類為正類樣本，另一類為負類樣本，具體信息見表 1。 表 1 網(wǎng)上發(fā)布的 與腫瘤有關的 二分類 樣本 集 （ Leukemia 和 Colon Tumor） 序號 數(shù)據(jù)集名稱與下載網(wǎng)址 基因數(shù)量 樣本總量 正類樣本數(shù)量 負類樣本數(shù)量 1 急性白血病數(shù)據(jù)集 (Leukemia Dataset)[1] 7,129 72 47(ALL) 25(AML) 2 結腸癌數(shù)據(jù)集 (Colon Tumor Dataset)[33] 2,000 62 40(Tumor) 22(Normal) 我們從網(wǎng)站 下載了 SRBCT 數(shù)據(jù)集，該數(shù)據(jù)集包括 88個樣本，每一個樣本包含 2,308 個基因。根據(jù)發(fā)布者的建議 ，樣本被劃分為 63 個訓練樣本和 25 個測試樣本，且測試樣本集中 包括 5 個與腫瘤無關的樣本 , 其數(shù)據(jù)集特征描述見表 2。 63 個訓練樣本包括 23 個 Ewing 腫瘤亞型 (EWS)、 20 個 rhabdomyosara 腫瘤亞型 (RMS)、 12 個 neuroblastoma 腫瘤亞型 (NB)和 8 個 Burkitt lymphomas 腫瘤亞型 (BL)。 測試樣本集包括 6 個 EWS 樣本、 5 個 RMS 樣本、 6 個 NB 樣本、 3 個 BL 樣本和 5 個非腫瘤樣本， 在我們的 實驗中 去掉了這 5 個非腫瘤樣本。 表 2 SRBCT 數(shù)據(jù)集的特點描述 腫瘤亞型 原數(shù)據(jù)集 訓練集 測試集 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 實驗方法 針對 Leukemia、 Colon Tumor和 SRBCT 三種腫瘤樣本集分別設計了三種實驗方法： BFSC