針對MicroRNA(miRNA)靶基因樣本數據不平衡導致陽性樣本預測準確率低和整體分類效果不佳的問題，提出一種基于欠采樣技術的集成學習算法——支持向量機(SVM)-嵌入下采樣和權重平滑(IUSW)集成學習算法。算法采用SVM作為基學習算法，以AdaBoost為集成框架，迭代過程中嵌入基于聚類的欠采樣以降低陰陽樣本數據分布不平衡程度，同時在自適應樣本權重調整過程中，以樣本權重平滑機制剔除陰性樣本中的異常點以避免過學習，最終以帶權重的投票機制組合多個弱分類器預測結果作為miRNA集成分類器的預測結果。實驗表明，在不平衡數據集上SVM-IUSW算法和其他算法相比，不但有效提高了陽性靶標的預測準確率和整體分類效果，還增強了miRNA靶標分類器的泛化能力。
引用本文： 陳志茹, 洪文學. 嵌入欠采樣技術的支持向量機集成分類算法的MicroRNA靶標預測. 生物醫學工程學雜志, 2016, (1): 72-77. doi: 10.7507/1001-5515.20160014 復制
引言
MicroRNA(miRNA)是長20~22個堿基的內源性非編碼RNA基因，廣泛存在于真核生物細胞內[1]。miRNA通過與靶標mRNA 3′端堿基完全或不完全匹配而裂解靶標基因或抑制其蛋白質表達水平，參與細胞增殖、凋亡、分化、代謝、發育等重要的生命活動[2]。自從1993年人們發現lin-4和let-7兩個miRNA以來，miRNA的發現及靶標識別日益受到關注[1-2]。
miRNA靶標鑒定的生物實驗方法具有吞吐量小、成本高、耗時長、可重現性差、效率低等弊端[3]。利用miRNA和靶基因之間相互作用的規律性，人們設計了幾十種算法來實現高通量靶標預測[4-6]。這些算法可分為兩類：①基于常規規則的miRNA靶標預測算法，如miRanda、TargetSan[4]等。算法主要從miRNA靶位點的同源保守性、miRNA 5′端種子區與mRNA 3′端序列的互補性等方面設計算法，算法能識別少部分已知miRNA陽性靶標。②基于機器學習的miRNA靶標預測算法。算法突破了靶位點跨物種保守性，將二聚體結構和熱力學等特征考慮進去，經訓練集上學習智能判定識別規則，進而構建高性能的分類器模型。其中支持向量機算法(support vector machine，SVM)[5]嘗試從統計學角度分析miRNA與靶標的作用特征，成為miRNA靶標預測算法研究領域的熱點。基于SVM的miRNA靶標預測算法，例如miTarget[6]、SVMicro[6]等算法，雖明顯改善了miRNA靶標分類識別性能，對已知的miRNA靶標預測有較高的特異性和敏感度，但對未知的靶基因預測泛化性能差、假陽性率高[7]。
在整個真核生物基因組中，miRNA陽性靶標數量遠遠少于陰性靶標，miRNA靶標分類是一個典型的不平衡分類問題。現有的機器學習算法都是面向類分布平衡和分類精度最大化而設計，在分類miRNA不平衡陰陽靶標樣本時，陰性樣本對最優分類超平面的確定影響較大，造成最優分類超平面受到陰性樣本的影響而產生偏斜，從而傾向于將陽性預測成陰性，降低了陽性樣本分類精度，分類效果并不理想。本文提出一種用于預測miRNA靶標的嵌入欠采樣技術的集成學習算法——SVM-嵌入下采樣和權重平滑(integration of under-sampling and weight,IUSW)集成學習算法，以解決訓練樣本集不平衡對陽性靶標分類精度、整體分類性能造成的影響和分類器泛化能力比較弱的問題。
1 面向不平衡數據集的miRNA靶標預測集成算法
1.1 AdaBoost算法
集成學習就是構造若干子分類器模型并將它們的預測值加權用于新樣本的預測，類似于多個決策者進行同一個決策。它能夠有效地提高少類樣本的分類精度，提高單一分類器的泛化能力[8]。AdaBoost[8]是一種典型的集成學習算法。其基本思想：首先，對訓練樣本均賦以一個相同的權重，以表征該樣本被某子分類器選入訓練集中的概率。其次，通過若干輪訓練得到若干子分類器。在每一輪迭代過程中，計算該輪子分類器所對應的誤差，并據此增大被當前子分類器錯分樣本的權重，降低被正確分類樣本的權重，以此降低其被下一輪子分類器選中的概率，使得下一輪的訓練在更新權重的樣本集上側重那些錯分(難分)的樣本。最后，將這些子分類器按照帶權重的投票組合機制組合成一個強分類器。具體算法描述如下。
輸入：訓練集S={(xi,yi)｜i∈I={1,2,…,l}}，yi∈{+1,-1}。其中陽性樣本集S+，陰性樣本集S-。
輸出：miRNA靶基因分類器 H(x)
Begin：
Step 1：初始化樣本權重ω1(i)=1/l(i=1,2,…,l)，設置子分類器個數T，令t=0。
Step 2：do t=t+1。
Step 3：對訓練集S采用子分類器學習訓練，得到第t個子分類器Ht(x) 。
Step 4：計算Ht(x)在當前樣本分布的誤差
Step 5：計算Ht(x)在集成分類器中的組合權重
Step 6：調整訓練樣本集權重：
| $\begin{align} & {{\omega }_{t+1}}\left( i \right) & =\omega \left( i \right)\frac{\exp \left\{ -{{\beta }_{t}}{{y}_{i}}{{H}_{t}}\left( {{x}_{i}} \right) \right\}}{{{Z}_{t}}} \\ & =\frac{{{\omega }_{t}}\left( i \right)}{{{Z}_{t}}}\left\{ \begin{matrix} {{\text{e}}^{-{{\beta }_{t}}}} & \text{if}\left( {{y}_{i}}={{H}_{t}}\left( {{x}_{i}} \right) \right) \\ {{\text{e}}^{{{\beta }_{t}}}} & \text{if}\left( {{y}_{i}}\ne {{H}_{t}}\left( {{x}_{i}} \right) \right) \\ \end{matrix} \right., \end{align}$ |
其中，Zt為歸一化因子，使
Step 7：While(εt≠0 & εt＜50%)
Step 8：輸出集成分類器：
End；
Sign(x)為符號函數，I(x)為指示函數。子分類器的誤差記為
AdaBoost算法具有兩個顯著的特點。一是它對整個訓練樣本集維持了一個可自適應調整的權重分布。算法在迭代過程中以公式(1)對樣本權重進行自適調整。假設測試樣本xi 被第t個子分類器錯分，則yi與Ht(xi)異號，即yiHt(xi)=-1，相應的exp{-βtyiHt(xi)}＞1。如果測試樣本被正確分類，則0＜exp{-βtyiHt(xi)}＜1。子分類器權重βt越高，exp{-βtyiHt(xi)}值越大，錯分樣本被賦予的權重也就越高。顯然，這種權重調整機制既受到當前子分類器分類性能的影響，又與錯分樣本當前權重有關，能夠有效提高子分類器分類性能。二是它對子分類器進行帶權重的投票組合機制。子分類器的組合權重
1.2 基于類別不平衡數據集的集成分類算法
將AdaBoost算法直接應用于miRNA靶標不平衡數據集的分類問題時，存在兩個問題：①AdaBoost算法沒有考慮類別不平衡對分類問題帶來的影響，陰、陽訓練集的樣本數不平衡造成陽性樣本分類效果和整體分類效果不好。②受到噪聲的影響，在miRNA靶標樣本訓練集中包含很難被正確分類的異常陰性樣本。隨著迭代次數的增加，異常樣本容易被錯分，權重會變得越來越大，對異常樣本賦予過高的權重會誤導子分類器的訓練學習，使得它們容易對訓練數據“過學習”，造成分類器對這些樣本過于敏感，從而導致陽性類樣本的分類性能下降。
1.2.1 欠采樣在miRNA靶標預測算法中的研究
考慮類別不平衡對分類問題帶來的影響，在AdaBoost算法迭代循環過程中，嵌入基于聚類的欠采樣。欠采樣的基本思想是保持陽性樣本不變的同時從陰性樣本集中抽取一部分子集參與訓練，以此降低陰陽兩類樣本數據分布的不平衡程度。采用先聚類后欠采樣的方法，以減少欠采樣所導致樣本信息丟失。具體過程為在迭代循環之前，首先利用K-NN聚類算法將miRNA靶基因陰性樣本集劃分成若干個互不相交的子集，保持陽性訓練樣本集數量不變；然后在迭代開始的時候，在這些子集上按比例進行欠采樣，子集規模越大的被分配到的抽樣數量越大，將這些子集欠采樣得到的樣本形成獨立同分布的陰性訓練集；最后將原始的陽性訓練樣本和經過欠采樣后得到的陰性樣本組成新的且相對平衡的訓練樣本集，供子分類器學習訓練。具體做法是在1.1節算法中的step 2之前插入step 1.1、step 1.2，在step 3之前插入step 2.1。
Step 1.1：利用K-NN聚類算法將原始陰性樣本集S_劃分為k個不相交的子集S_(1)K S_(k)。
Step1.2：對每個子集S_(i)分配相應的抽樣數量ci=Round(c｜S_(i)｜/l_)，i=1,K,k；其中c=Round(rl_+(1-r)l+)是整個抽樣樣本容量，Round(·)表示取整函數，r表示欠采樣率。
Step 2.1：對樣本子集S_(i)進行隨機欠采樣(random under-sampling)，得到容量為ci的自助樣本集_(i)，令_=∪ki=1_(i)以及S=_US+。
1.2.2 融入權重平滑機制的miRNA靶標預測集成算法——SVM-IUSW
針對陰性樣本集存在難分的異常樣本對miRNA靶標分類器造成的影響，對上述的樣本權重調整機制加以改進，在AdaBoost算法原有的權重調整機制中融入一種簡單而又平穩的權重平滑機制對樣本權重進行平滑處理，降低異常陰性樣本被選入訓練集的概率，避免過學習現象，使分類器兼顧陽性樣本和陰性樣本的分類精度。權重平滑機制要抑制異常陰性樣本的權重，因此只需對陰性樣本權重分配進行改進。在1.1節算法中的step2之后、step2.1之前加入權重平滑機制。具體做法描述如下。
首先，定義每個陰性訓練樣本(xi,yi)覆蓋集：
| $Cov\left( x \right)=\{{{x}_{i}}D(x,{{x}_{i}})\le d\left( x \right),({{x}_{i}},{{y}_{i}})\in S\_\}$ |
其中D(x,xi)為x與xi兩個樣本點之間的歐式距離，d(x)=min(D(x,xi)｜(xi,yi)∈S+)為xi與所有陽性訓練樣本之間的最小距離。樣本覆蓋集Cov(x)的幾何意義如圖 1所示。
圖1
樣本覆蓋集示意圖
Figure1.
Sample covering sets
在圖 1中，假設x陰性樣本為異常樣本，那么它周圍一定范圍內將更多地分布著陽性樣本，而同類樣本則距其較遠，即該異常陰性樣本的覆蓋集內將包含極少的同類樣本點，甚至極可能只含有該異常樣本自身。這樣就能通過計算某一陰性樣本覆蓋集內同類樣本的個數來判斷該樣本是否為異常樣本點，然后對陰性訓練集進行權重平滑處理，減少異常樣本點權重。
其次，利用覆蓋集Cov(x)對陰性樣本集的權重進行平滑。設利用公式(1)已獲得各個訓練樣本的權重ω，對于陰性樣本實例xi按下式重新進行調整:
| ${{\omega }_{i}}\leftarrow \sum\limits_{j:{{x}_{j}}\in Cov\left( {{x}_{i}} \right)}{{{\omega }_{j}},\forall i\in I\_}$ |
然后歸一化處理
2 實驗過程
2.1 實驗樣本集建立
miRNA靶基因訓練集由TarBase v6.0[9]數據庫中的人類(Human)、褐家鼠(Rattus norvegicus)、小家鼠(Mus musculus)、牛(Bos taurus)、綿羊(Ovis aries)5種高等哺乳動物靶標序列組成。篩選去除miRNA∶mRNA二聚體結構中存在多環的數據，得到138條實驗驗證的陽性miRNA靶基因和58條驗證的陰性miRNA靶基因。由于在真核生物基因組上，存在miRNA靶位點的基因相比整個基因組來說少之又少，陰性靶基因數量和陽性靶基因數量嚴重不平衡，為了更好地模擬miRNA靶標預測過程中靶基因陰陽樣本不平衡的情況，故人工構造一些置信度較高的陰性樣本集。
本文使用了100條構造的成熟miRNA。這些miRNA序列中A、U、G、C所占的比列分別34%、29%、18%、19%[10]。這一特征使得它們與真正的miRNA區分開來。利用miRanda軟件，在人類3′UTR序列中搜尋與這100條構造miRNA配對的靶基因。其中miRanda參數MFE(最小自由能)值設為25 kcal/mol，SC參數(scale，5′端11個堿基得分值乘以該值，然后和3′端11個堿基得分值相加作為堿基互補得分)設為180，得到數千個陰性miRNA靶基因。刪除其中miRNA∶mRNA二聚體結構中存在多環的數據，從中隨機抽取1 000個樣本同58個己被證實的數據組成陰性樣本集，最后得到1 058個陰性miRNA靶基因。
獨立測試集包括從miRecord[11]數據庫中下載的187個人類陽性靶標和39個人類和其他哺乳動物的陰性靶標。
2.2 miRNA∶mRNA綁定點特征提取
成熟的miRNA與靶標基因mRNA 3′UTR區域堿基互補配對[12]，形成雙鏈結構，即miRNA∶mRNA二聚體結構。miRNA序列自5′端分為種子區和非種子區[12]。
從miRNA∶mRNA二聚體的種子區和非種子區域，提取5類83個特征，包括：①結構的序列特征。整個區域中A-U匹配數量、G-U匹配數量、G-C匹配數量、堿基匹配總數和不匹配總數，提取10個特征。miRNA序列及其靶標序列中不匹配的個數，提取2個特征。種子區域和整個區域上miRNA與其靶標mRNA配對中的鼓包個數、靠近種子區域前三個鼓包中的堿基個數、鼓包中堿基的最大值、最小值和平均值，提取10個特征。miRNA序列及其靶標mRNA序列中的連續4mer匹配的堿基個數和連續3mer不匹配的堿基個數，提取14個特征。共提取結構的序列特征36個。②自由能特征。miRNA∶mRNA二聚體的穩定結構所具有的最小自由能[13]特征作為1個特征進行提取。二聚體的氫鍵對數量和種子區域上的氫鍵對比例分別作為1個特征進行提取。共提取3個特征。③基于綁定位置特征提取。對種子區域第1個到第8個堿基匹配狀態特征進行提取，每個堿基有四種匹配狀態，共提取得到8個堿基的匹配狀態特征。④靶標作用體上的懲罰特征：分別將種子區和非種子區凸環出現的位置和個數信息特征提取出來，共提取靶標作用體上的懲罰特征4個。⑤3′和5′的上下文特征：計算各自上下文區域中各核苷酸和其2mer組合分別占兩段序列的比重，共計32個特征。
miRNA∶mRNA綁定位點特征提取之后，一方面特征之間的相關性和冗余性會降低分類的精度，另一方面特征過多會提高分類器的復雜度，造成過擬合現象，降低分類器的泛化能力。因此需對特征集合進行選擇和優化，本文采用最大相關最小冗余算法[14](maximum relevance and minimum redundancy，mRMR)選擇特征。mRMR根據最大統計依賴性原則選擇特征，從特征空間中尋找與目標類別有最大相關性且相互之間具有最少冗余性的m個特征。實驗證明，當特征子集個數分別選取18、29、46和83的時候，由于特征子集個數為18的時候不能包含足夠多的樣本信息，分類效果只有66.5%，而其他對應訓練得到的miRNA靶基因分類器的分類效果相差不大且由29個特征組成的特征子集作為最優子集時，算法的時間復雜度最低，因此將選取的29個特征組成最優特征子集。
2.3 子分類器學習模型和參數優化
SVM作為集成學習算法中子分類器學習模型，對陰、陽兩類樣本的誤分損失采用不同的懲罰因子。
| $\begin{align} & \min \frac{1}{2}{{\left\| \omega \right\|}^{2}}+{{C}_{+}}\sum\limits_{\left( i\left| y=+1 \right. \right)}{{{\xi }^{2}}+{{C}_{-}}\sum\limits_{\left( i\left| y=-1 \right. \right)}{{{\xi }^{2}}}} \\ & s.t.{{y}_{i}}\left( \left( \omega \cdot \Phi \left( {{x}_{i}} \right) \right)+b \right)\ge 1-{{\xi }_{i}} \\ & {{\xi }_{i}}\ge 0,i=1\text{L}n \\ \end{align}$ |
其中，實驗選取RBF核函數作為子分類器的核函數。
SVM-IUSW算法是利用軟件libsvm3.1軟件包基于MatlabR2010a開發環境實現。RBF核參數σ以及懲罰因子C+和C-構成了分類器參數組合。實驗采用遺傳算法對miRNA靶標分類器參數組合尋優。
2.4 實驗結果與分析
SVM-IUSW算法和經典的SVMicro、miRanda、mirTarget、SVMicro算法在相同的獨立測試集上的對比結果如圖 2所示。實驗采用接受者操作特征曲線(receiver operating characteristic,ROC)下方圖面積(area under the ROC curve,AUC)值[15]作為分類器性能評價標準。
圖2
獨立測試集上的ROC曲線及其它算法在同一測試集上的預測性能
Figure2.
Receiver operating characteristic curves of an independent test dataset of this algorithms and scatter plot of sensitivity versus the false positive rate (1-specificity) for different target prediction algorithms used to predict the test dataset
圖 2中ROC曲線圖橫坐標為1－特異性(假陽性率)，縱坐標為敏感度(真陽性率)，圖中坐標點分別表示各個miRNA靶基因預測算法在測試集中的預測指標。由圖 2可知，SVM-IUSW算法與其他三個經典算法相比，當敏感度相同時，SVM-IUSW算法假陽性識別率最低。尤其是當敏感度大于0.8時，其他三種算法往往側重于將所有測試樣本識別為miRNA陰性靶標，導致miRNA靶標假陽性率高；當1-特異性相同時，SVM-IUSW算法敏感度最高，當1－特異性較低時(＜0.2)，其他三種算法敏感度均低于0.6，陽性靶標被誤識別為陰性靶標的次數增加。SVM-IUSW算法與其他算法具體比較結果如表 1所示。
表1
SVM-IUSW算法和3個經典算法實驗結果比較
Table1.
Experimental results of SVM-IUSW algorithm compared with those of other three classical algorithms
由表 1可知，針對miRNA靶基因陰性、陽性數據不均衡問題，SVM-IUSW算法的敏感度(陽性樣本預測精度)相比其他三種算法有很大的提高，在兼顧敏感度和特異性的基礎上，算法在預測miRNA靶基因不平衡數據集時，與SVMicro、miRanda、mirTarget算法相比較，SVM-IUSW算法特異性90.36%，敏感度86.32%，整體分類精度88.12%，取得的ROC曲線覆蓋面積最大，分類效果和泛化性能明顯提高。這些說明SVM-IUSW算法將欠采樣與集成學習的優勢相結合，一方面在迭代過程中嵌入基于聚類的欠采樣，采用先聚類后欠采樣的方法，以減少欠采樣所導致的樣本信息丟失；另一方面在AdaBoost算法原有的權重調整機制中融入權重平滑機制對樣本權重進行平滑處理，降低異常陰性樣本被選入訓練集的概率，避免了過學習。
3 結論
miRNA靶標在基因組上是個不平衡的數據集。本文將欠采樣技術和樣本平滑機制嵌入到集成學習算法中，提出了SVM-IUSW算法。在相同的獨立測試集上，SVM-IUSW和SVMicro、miRanda、miTarget算法相比，具有很高的特異性和敏感度，AUC值達到0.84，整體分類精度較高。運用該算法構造的miRNA靶標集成分類器在解決miRNA靶基因不平衡問題時，具有很好的分類性能和泛化能力，有效提高了miRNA靶基因分類器的預測性能。
引言
MicroRNA(miRNA)是長20~22個堿基的內源性非編碼RNA基因，廣泛存在于真核生物細胞內[1]。miRNA通過與靶標mRNA 3′端堿基完全或不完全匹配而裂解靶標基因或抑制其蛋白質表達水平，參與細胞增殖、凋亡、分化、代謝、發育等重要的生命活動[2]。自從1993年人們發現lin-4和let-7兩個miRNA以來，miRNA的發現及靶標識別日益受到關注[1-2]。
miRNA靶標鑒定的生物實驗方法具有吞吐量小、成本高、耗時長、可重現性差、效率低等弊端[3]。利用miRNA和靶基因之間相互作用的規律性，人們設計了幾十種算法來實現高通量靶標預測[4-6]。這些算法可分為兩類：①基于常規規則的miRNA靶標預測算法，如miRanda、TargetSan[4]等。算法主要從miRNA靶位點的同源保守性、miRNA 5′端種子區與mRNA 3′端序列的互補性等方面設計算法，算法能識別少部分已知miRNA陽性靶標。②基于機器學習的miRNA靶標預測算法。算法突破了靶位點跨物種保守性，將二聚體結構和熱力學等特征考慮進去，經訓練集上學習智能判定識別規則，進而構建高性能的分類器模型。其中支持向量機算法(support vector machine，SVM)[5]嘗試從統計學角度分析miRNA與靶標的作用特征，成為miRNA靶標預測算法研究領域的熱點。基于SVM的miRNA靶標預測算法，例如miTarget[6]、SVMicro[6]等算法，雖明顯改善了miRNA靶標分類識別性能，對已知的miRNA靶標預測有較高的特異性和敏感度，但對未知的靶基因預測泛化性能差、假陽性率高[7]。
在整個真核生物基因組中，miRNA陽性靶標數量遠遠少于陰性靶標，miRNA靶標分類是一個典型的不平衡分類問題。現有的機器學習算法都是面向類分布平衡和分類精度最大化而設計，在分類miRNA不平衡陰陽靶標樣本時，陰性樣本對最優分類超平面的確定影響較大，造成最優分類超平面受到陰性樣本的影響而產生偏斜，從而傾向于將陽性預測成陰性，降低了陽性樣本分類精度，分類效果并不理想。本文提出一種用于預測miRNA靶標的嵌入欠采樣技術的集成學習算法——SVM-嵌入下采樣和權重平滑(integration of under-sampling and weight,IUSW)集成學習算法，以解決訓練樣本集不平衡對陽性靶標分類精度、整體分類性能造成的影響和分類器泛化能力比較弱的問題。
1 面向不平衡數據集的miRNA靶標預測集成算法
1.1 AdaBoost算法
集成學習就是構造若干子分類器模型并將它們的預測值加權用于新樣本的預測，類似于多個決策者進行同一個決策。它能夠有效地提高少類樣本的分類精度，提高單一分類器的泛化能力[8]。AdaBoost[8]是一種典型的集成學習算法。其基本思想：首先，對訓練樣本均賦以一個相同的權重，以表征該樣本被某子分類器選入訓練集中的概率。其次，通過若干輪訓練得到若干子分類器。在每一輪迭代過程中，計算該輪子分類器所對應的誤差，并據此增大被當前子分類器錯分樣本的權重，降低被正確分類樣本的權重，以此降低其被下一輪子分類器選中的概率，使得下一輪的訓練在更新權重的樣本集上側重那些錯分(難分)的樣本。最后，將這些子分類器按照帶權重的投票組合機制組合成一個強分類器。具體算法描述如下。
輸入：訓練集S={(xi,yi)｜i∈I={1,2,…,l}}，yi∈{+1,-1}。其中陽性樣本集S+，陰性樣本集S-。
輸出：miRNA靶基因分類器 H(x)
Begin：
Step 1：初始化樣本權重ω1(i)=1/l(i=1,2,…,l)，設置子分類器個數T，令t=0。
Step 2：do t=t+1。
Step 3：對訓練集S采用子分類器學習訓練，得到第t個子分類器Ht(x) 。
Step 4：計算Ht(x)在當前樣本分布的誤差
Step 5：計算Ht(x)在集成分類器中的組合權重
Step 6：調整訓練樣本集權重：
| $\begin{align} & {{\omega }_{t+1}}\left( i \right) & =\omega \left( i \right)\frac{\exp \left\{ -{{\beta }_{t}}{{y}_{i}}{{H}_{t}}\left( {{x}_{i}} \right) \right\}}{{{Z}_{t}}} \\ & =\frac{{{\omega }_{t}}\left( i \right)}{{{Z}_{t}}}\left\{ \begin{matrix} {{\text{e}}^{-{{\beta }_{t}}}} & \text{if}\left( {{y}_{i}}={{H}_{t}}\left( {{x}_{i}} \right) \right) \\ {{\text{e}}^{{{\beta }_{t}}}} & \text{if}\left( {{y}_{i}}\ne {{H}_{t}}\left( {{x}_{i}} \right) \right) \\ \end{matrix} \right., \end{align}$ |
其中，Zt為歸一化因子，使
Step 7：While(εt≠0 & εt＜50%)
Step 8：輸出集成分類器：
End；
Sign(x)為符號函數，I(x)為指示函數。子分類器的誤差記為
AdaBoost算法具有兩個顯著的特點。一是它對整個訓練樣本集維持了一個可自適應調整的權重分布。算法在迭代過程中以公式(1)對樣本權重進行自適調整。假設測試樣本xi 被第t個子分類器錯分，則yi與Ht(xi)異號，即yiHt(xi)=-1，相應的exp{-βtyiHt(xi)}＞1。如果測試樣本被正確分類，則0＜exp{-βtyiHt(xi)}＜1。子分類器權重βt越高，exp{-βtyiHt(xi)}值越大，錯分樣本被賦予的權重也就越高。顯然，這種權重調整機制既受到當前子分類器分類性能的影響，又與錯分樣本當前權重有關，能夠有效提高子分類器分類性能。二是它對子分類器進行帶權重的投票組合機制。子分類器的組合權重
1.2 基于類別不平衡數據集的集成分類算法
將AdaBoost算法直接應用于miRNA靶標不平衡數據集的分類問題時，存在兩個問題：①AdaBoost算法沒有考慮類別不平衡對分類問題帶來的影響，陰、陽訓練集的樣本數不平衡造成陽性樣本分類效果和整體分類效果不好。②受到噪聲的影響，在miRNA靶標樣本訓練集中包含很難被正確分類的異常陰性樣本。隨著迭代次數的增加，異常樣本容易被錯分，權重會變得越來越大，對異常樣本賦予過高的權重會誤導子分類器的訓練學習，使得它們容易對訓練數據“過學習”，造成分類器對這些樣本過于敏感，從而導致陽性類樣本的分類性能下降。
1.2.1 欠采樣在miRNA靶標預測算法中的研究
考慮類別不平衡對分類問題帶來的影響，在AdaBoost算法迭代循環過程中，嵌入基于聚類的欠采樣。欠采樣的基本思想是保持陽性樣本不變的同時從陰性樣本集中抽取一部分子集參與訓練，以此降低陰陽兩類樣本數據分布的不平衡程度。采用先聚類后欠采樣的方法，以減少欠采樣所導致樣本信息丟失。具體過程為在迭代循環之前，首先利用K-NN聚類算法將miRNA靶基因陰性樣本集劃分成若干個互不相交的子集，保持陽性訓練樣本集數量不變；然后在迭代開始的時候，在這些子集上按比例進行欠采樣，子集規模越大的被分配到的抽樣數量越大，將這些子集欠采樣得到的樣本形成獨立同分布的陰性訓練集；最后將原始的陽性訓練樣本和經過欠采樣后得到的陰性樣本組成新的且相對平衡的訓練樣本集，供子分類器學習訓練。具體做法是在1.1節算法中的step 2之前插入step 1.1、step 1.2，在step 3之前插入step 2.1。
Step 1.1：利用K-NN聚類算法將原始陰性樣本集S_劃分為k個不相交的子集S_(1)K S_(k)。
Step1.2：對每個子集S_(i)分配相應的抽樣數量ci=Round(c｜S_(i)｜/l_)，i=1,K,k；其中c=Round(rl_+(1-r)l+)是整個抽樣樣本容量，Round(·)表示取整函數，r表示欠采樣率。
Step 2.1：對樣本子集S_(i)進行隨機欠采樣(random under-sampling)，得到容量為ci的自助樣本集_(i)，令_=∪ki=1_(i)以及S=_US+。
1.2.2 融入權重平滑機制的miRNA靶標預測集成算法——SVM-IUSW
針對陰性樣本集存在難分的異常樣本對miRNA靶標分類器造成的影響，對上述的樣本權重調整機制加以改進，在AdaBoost算法原有的權重調整機制中融入一種簡單而又平穩的權重平滑機制對樣本權重進行平滑處理，降低異常陰性樣本被選入訓練集的概率，避免過學習現象，使分類器兼顧陽性樣本和陰性樣本的分類精度。權重平滑機制要抑制異常陰性樣本的權重，因此只需對陰性樣本權重分配進行改進。在1.1節算法中的step2之后、step2.1之前加入權重平滑機制。具體做法描述如下。
首先，定義每個陰性訓練樣本(xi,yi)覆蓋集：
| $Cov\left( x \right)=\{{{x}_{i}}D(x,{{x}_{i}})\le d\left( x \right),({{x}_{i}},{{y}_{i}})\in S\_\}$ |
其中D(x,xi)為x與xi兩個樣本點之間的歐式距離，d(x)=min(D(x,xi)｜(xi,yi)∈S+)為xi與所有陽性訓練樣本之間的最小距離。樣本覆蓋集Cov(x)的幾何意義如圖 1所示。
圖1
樣本覆蓋集示意圖
Figure1.
Sample covering sets
在圖 1中，假設x陰性樣本為異常樣本，那么它周圍一定范圍內將更多地分布著陽性樣本，而同類樣本則距其較遠，即該異常陰性樣本的覆蓋集內將包含極少的同類樣本點，甚至極可能只含有該異常樣本自身。這樣就能通過計算某一陰性樣本覆蓋集內同類樣本的個數來判斷該樣本是否為異常樣本點，然后對陰性訓練集進行權重平滑處理，減少異常樣本點權重。
其次，利用覆蓋集Cov(x)對陰性樣本集的權重進行平滑。設利用公式(1)已獲得各個訓練樣本的權重ω，對于陰性樣本實例xi按下式重新進行調整:
| ${{\omega }_{i}}\leftarrow \sum\limits_{j:{{x}_{j}}\in Cov\left( {{x}_{i}} \right)}{{{\omega }_{j}},\forall i\in I\_}$ |
然后歸一化處理
2 實驗過程
2.1 實驗樣本集建立
miRNA靶基因訓練集由TarBase v6.0[9]數據庫中的人類(Human)、褐家鼠(Rattus norvegicus)、小家鼠(Mus musculus)、牛(Bos taurus)、綿羊(Ovis aries)5種高等哺乳動物靶標序列組成。篩選去除miRNA∶mRNA二聚體結構中存在多環的數據，得到138條實驗驗證的陽性miRNA靶基因和58條驗證的陰性miRNA靶基因。由于在真核生物基因組上，存在miRNA靶位點的基因相比整個基因組來說少之又少，陰性靶基因數量和陽性靶基因數量嚴重不平衡，為了更好地模擬miRNA靶標預測過程中靶基因陰陽樣本不平衡的情況，故人工構造一些置信度較高的陰性樣本集。
本文使用了100條構造的成熟miRNA。這些miRNA序列中A、U、G、C所占的比列分別34%、29%、18%、19%[10]。這一特征使得它們與真正的miRNA區分開來。利用miRanda軟件，在人類3′UTR序列中搜尋與這100條構造miRNA配對的靶基因。其中miRanda參數MFE(最小自由能)值設為25 kcal/mol，SC參數(scale，5′端11個堿基得分值乘以該值，然后和3′端11個堿基得分值相加作為堿基互補得分)設為180，得到數千個陰性miRNA靶基因。刪除其中miRNA∶mRNA二聚體結構中存在多環的數據，從中隨機抽取1 000個樣本同58個己被證實的數據組成陰性樣本集，最后得到1 058個陰性miRNA靶基因。
獨立測試集包括從miRecord[11]數據庫中下載的187個人類陽性靶標和39個人類和其他哺乳動物的陰性靶標。
2.2 miRNA∶mRNA綁定點特征提取
成熟的miRNA與靶標基因mRNA 3′UTR區域堿基互補配對[12]，形成雙鏈結構，即miRNA∶mRNA二聚體結構。miRNA序列自5′端分為種子區和非種子區[12]。
從miRNA∶mRNA二聚體的種子區和非種子區域，提取5類83個特征，包括：①結構的序列特征。整個區域中A-U匹配數量、G-U匹配數量、G-C匹配數量、堿基匹配總數和不匹配總數，提取10個特征。miRNA序列及其靶標序列中不匹配的個數，提取2個特征。種子區域和整個區域上miRNA與其靶標mRNA配對中的鼓包個數、靠近種子區域前三個鼓包中的堿基個數、鼓包中堿基的最大值、最小值和平均值，提取10個特征。miRNA序列及其靶標mRNA序列中的連續4mer匹配的堿基個數和連續3mer不匹配的堿基個數，提取14個特征。共提取結構的序列特征36個。②自由能特征。miRNA∶mRNA二聚體的穩定結構所具有的最小自由能[13]特征作為1個特征進行提取。二聚體的氫鍵對數量和種子區域上的氫鍵對比例分別作為1個特征進行提取。共提取3個特征。③基于綁定位置特征提取。對種子區域第1個到第8個堿基匹配狀態特征進行提取，每個堿基有四種匹配狀態，共提取得到8個堿基的匹配狀態特征。④靶標作用體上的懲罰特征：分別將種子區和非種子區凸環出現的位置和個數信息特征提取出來，共提取靶標作用體上的懲罰特征4個。⑤3′和5′的上下文特征：計算各自上下文區域中各核苷酸和其2mer組合分別占兩段序列的比重，共計32個特征。
miRNA∶mRNA綁定位點特征提取之后，一方面特征之間的相關性和冗余性會降低分類的精度，另一方面特征過多會提高分類器的復雜度，造成過擬合現象，降低分類器的泛化能力。因此需對特征集合進行選擇和優化，本文采用最大相關最小冗余算法[14](maximum relevance and minimum redundancy，mRMR)選擇特征。mRMR根據最大統計依賴性原則選擇特征，從特征空間中尋找與目標類別有最大相關性且相互之間具有最少冗余性的m個特征。實驗證明，當特征子集個數分別選取18、29、46和83的時候，由于特征子集個數為18的時候不能包含足夠多的樣本信息，分類效果只有66.5%，而其他對應訓練得到的miRNA靶基因分類器的分類效果相差不大且由29個特征組成的特征子集作為最優子集時，算法的時間復雜度最低，因此將選取的29個特征組成最優特征子集。
2.3 子分類器學習模型和參數優化
SVM作為集成學習算法中子分類器學習模型，對陰、陽兩類樣本的誤分損失采用不同的懲罰因子。
| $\begin{align} & \min \frac{1}{2}{{\left\| \omega \right\|}^{2}}+{{C}_{+}}\sum\limits_{\left( i\left| y=+1 \right. \right)}{{{\xi }^{2}}+{{C}_{-}}\sum\limits_{\left( i\left| y=-1 \right. \right)}{{{\xi }^{2}}}} \\ & s.t.{{y}_{i}}\left( \left( \omega \cdot \Phi \left( {{x}_{i}} \right) \right)+b \right)\ge 1-{{\xi }_{i}} \\ & {{\xi }_{i}}\ge 0,i=1\text{L}n \\ \end{align}$ |
其中，實驗選取RBF核函數作為子分類器的核函數。
SVM-IUSW算法是利用軟件libsvm3.1軟件包基于MatlabR2010a開發環境實現。RBF核參數σ以及懲罰因子C+和C-構成了分類器參數組合。實驗采用遺傳算法對miRNA靶標分類器參數組合尋優。
2.4 實驗結果與分析
SVM-IUSW算法和經典的SVMicro、miRanda、mirTarget、SVMicro算法在相同的獨立測試集上的對比結果如圖 2所示。實驗采用接受者操作特征曲線(receiver operating characteristic,ROC)下方圖面積(area under the ROC curve,AUC)值[15]作為分類器性能評價標準。
圖2
獨立測試集上的ROC曲線及其它算法在同一測試集上的預測性能
Figure2.
Receiver operating characteristic curves of an independent test dataset of this algorithms and scatter plot of sensitivity versus the false positive rate (1-specificity) for different target prediction algorithms used to predict the test dataset
圖 2中ROC曲線圖橫坐標為1－特異性(假陽性率)，縱坐標為敏感度(真陽性率)，圖中坐標點分別表示各個miRNA靶基因預測算法在測試集中的預測指標。由圖 2可知，SVM-IUSW算法與其他三個經典算法相比，當敏感度相同時，SVM-IUSW算法假陽性識別率最低。尤其是當敏感度大于0.8時，其他三種算法往往側重于將所有測試樣本識別為miRNA陰性靶標，導致miRNA靶標假陽性率高；當1-特異性相同時，SVM-IUSW算法敏感度最高，當1－特異性較低時(＜0.2)，其他三種算法敏感度均低于0.6，陽性靶標被誤識別為陰性靶標的次數增加。SVM-IUSW算法與其他算法具體比較結果如表 1所示。
表1
SVM-IUSW算法和3個經典算法實驗結果比較
Table1.
Experimental results of SVM-IUSW algorithm compared with those of other three classical algorithms
由表 1可知，針對miRNA靶基因陰性、陽性數據不均衡問題，SVM-IUSW算法的敏感度(陽性樣本預測精度)相比其他三種算法有很大的提高，在兼顧敏感度和特異性的基礎上，算法在預測miRNA靶基因不平衡數據集時，與SVMicro、miRanda、mirTarget算法相比較，SVM-IUSW算法特異性90.36%，敏感度86.32%，整體分類精度88.12%，取得的ROC曲線覆蓋面積最大，分類效果和泛化性能明顯提高。這些說明SVM-IUSW算法將欠采樣與集成學習的優勢相結合，一方面在迭代過程中嵌入基于聚類的欠采樣，采用先聚類后欠采樣的方法，以減少欠采樣所導致的樣本信息丟失；另一方面在AdaBoost算法原有的權重調整機制中融入權重平滑機制對樣本權重進行平滑處理，降低異常陰性樣本被選入訓練集的概率，避免了過學習。
3 結論
miRNA靶標在基因組上是個不平衡的數據集。本文將欠采樣技術和樣本平滑機制嵌入到集成學習算法中，提出了SVM-IUSW算法。在相同的獨立測試集上，SVM-IUSW和SVMicro、miRanda、miTarget算法相比，具有很高的特異性和敏感度，AUC值達到0.84，整體分類精度較高。運用該算法構造的miRNA靶標集成分類器在解決miRNA靶基因不平衡問題時，具有很好的分類性能和泛化能力，有效提高了miRNA靶基因分類器的預測性能。
