【正文】 ................................... 78 致謝 ................................................................................................................................................ 79 上海大學(xué)碩士學(xué)位論文 2022 年 5 月 1 第一章 緒論 生物信息學(xué)簡介 20 世 紀(jì)后期，人類和其他生物物種基因組學(xué)的研究飛速發(fā)展，生物信息的增長驚人，生物科學(xué)技術(shù)極大地豐富了生物科學(xué)的數(shù)據(jù)資源。 [1] 目前生物信息學(xué)的主要任務(wù)是研究生物分子數(shù)據(jù)的獲取、存儲和查詢，發(fā)展數(shù)據(jù)分析方法，研究內(nèi)容主要包括三個方面： 第一， 收集和管理生物分子數(shù)據(jù)，將各種數(shù)據(jù)以一定的表示形式存放在計算機中，建立數(shù)據(jù)庫系統(tǒng)并提供數(shù)據(jù)查詢和數(shù)據(jù)通訊工具，使得生物學(xué)研究人員能夠方便地使用這些數(shù)據(jù)，并為信息分析和數(shù)據(jù)挖掘打下基礎(chǔ)。在蛋白質(zhì)一級結(jié)構(gòu)方面有SWISSPROT、 PIR 和 MIPS 等。在此基礎(chǔ)上解釋與生物分子信息復(fù)制、上海大學(xué)碩士學(xué)位論文 2022 年 5 月 2 傳遞、表達有關(guān)的生物過程，并解釋生物過程中出現(xiàn)的故障與疾病的關(guān)系，幫助發(fā)現(xiàn)新藥物作用目標(biāo)，設(shè)計新藥物分子，為進一步的研究和應(yīng)用打下基礎(chǔ)。本論文研究基于 機器學(xué)習(xí) 理論和算法 ， 通過 對蛋白質(zhì)序列分析，進而實現(xiàn) 亞細(xì)胞位置預(yù)測的工作 。 機器學(xué)習(xí)算法在生物信息學(xué)中的應(yīng)用 機器學(xué)習(xí)的研究主旨是使用計算機模擬人類的學(xué)習(xí)活動 ,它是研究計算機識別現(xiàn)有知識、獲取新知識、不斷改善性能和實現(xiàn)自身完善的方法。 序列比對是生物信息學(xué)的基礎(chǔ)。另外 ,還有動上海大學(xué)碩士學(xué)位論文 2022 年 5 月 3 態(tài)規(guī)劃算法、神經(jīng)網(wǎng)絡(luò)和隱 馬爾科夫 算法。 第二， 在人類基因組研究中的應(yīng)用。發(fā)現(xiàn)新基因和單核苷酸多態(tài)是當(dāng)前國際上基因組研究的熱點。 一般步驟為先通過蛋白質(zhì)序列數(shù)據(jù)庫比較來確定其功能。 b， 蛋白質(zhì)結(jié)構(gòu)預(yù)測的目的是利用已知的一級序列來構(gòu)建出蛋白質(zhì)的立體結(jié)構(gòu)模 型 ,對蛋白質(zhì)進行結(jié)構(gòu)預(yù)測需要具體問題具體分析 ,在不同的已知條件下對于不同的蛋白質(zhì)采取不同的策略。 生物芯片技術(shù)檢測及分析技術(shù)是生物信息學(xué)中目前實用性較強的研究領(lǐng)域。 QSAR 簡介 化合物的性質(zhì) /活性是化學(xué)的基本研究內(nèi)容之一，徐光憲先生將物質(zhì)結(jié)構(gòu)與性能的定量關(guān)系稱為化學(xué)的第二根本規(guī)律，并將其列為二十一世紀(jì)化學(xué)的四大難題（中長期）之一 [10]。后來人們發(fā)現(xiàn)，化合物拓?fù)浣Y(jié)構(gòu)是決定其化學(xué)性質(zhì)的重要因素。而后在二十世紀(jì) 60 年代，Hansch[16,17]和 Free、 Wilson[18,19]的研究開始建立在定量的基礎(chǔ)之上。二十世紀(jì) 80 年代后，考慮分子三維構(gòu)象的 3DQSAR 也逐步引起了研究者的關(guān)注。并運用 J2EE 技術(shù)，實現(xiàn)基于上述模型的在線預(yù)報功能。 本文的主要工作成果在于： 立起了用于蛋白質(zhì)序列亞細(xì)胞定位預(yù)報模型和 5脂氧化酶抑制活性預(yù)測模型； ，使預(yù)報模型能夠為 領(lǐng)域?qū)＜?，特別是實驗工作者 所用。其研究目標(biāo)是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng) ,其主要研究方法是不斷修改系統(tǒng)的控制參數(shù)和改進系統(tǒng)的執(zhí)行能力 ,不涉及與具體任務(wù)有關(guān)的知識。本階段的研究目標(biāo)是模擬人類的概念學(xué)習(xí)過程 ,并采用邏輯結(jié)構(gòu)或圖結(jié)構(gòu)作為機器內(nèi)部描述。 1980 年 ,在美國的卡內(nèi)基 — 梅隆 (CMU)召開了第一屆機器學(xué)習(xí)國際研討會 ,標(biāo)志著機器學(xué)習(xí)研究已在全世界興起。例如，圖 即為一棵決策樹，它將整個樣本空間分為三類。決策樹的質(zhì)量更加依靠好的停止 規(guī)則而不是劃分規(guī)則。沒有一種剪枝方法明顯優(yōu)于 其它 方法。 算法 [41] 設(shè) S 為訓(xùn)練集樣本總數(shù)，共有 m 類樣本 , ( 1, 2, 3.. ., )iC i m? ， Si 為類 Ci 中的樣本數(shù)，計算公式為： 上海大學(xué)碩士學(xué)位論文 2022 年 5 月 8 1 2 21( , , ... ) l o g ( )mm i iiI s s s p p??? ? () 其中，其中 pi 是任意樣本屬于 Ci 的概率，可用 Si/S 來估計 。使用“信息增益率函數(shù)”，它同時考慮了每一次劃分所產(chǎn)生的子結(jié)點的個數(shù)和每個子結(jié)點的大?。ò臄?shù)據(jù)實例的個數(shù)），考慮的對象主要是一個個地劃分，而不再考慮分類所蘊涵的信息量，屬性 X 的信息增益函數(shù)為： 12()() ( , , .. ., )vG a in XAX I s s s? () 其中 v 為該節(jié)點的分枝數(shù)， si 為第 i 個分枝下的記錄個數(shù)。另外，在節(jié)點處記下符 合條件的統(tǒng)計數(shù)據(jù)：該分枝總數(shù)、有效數(shù)、中止數(shù)和失效數(shù)。 對決策樹上的每個非葉 子結(jié)點，計算該分枝節(jié)點上的子樹被剪枝可能出現(xiàn)的期望錯誤率。 ()iFx表示記錄 x 的屬性 Fi 的值 ,具體結(jié)構(gòu)描述如下：樹中的每個結(jié)點表示一個問題 。分支結(jié)點的事例數(shù)太小以至于不能給出一個有統(tǒng)計意義的測試 。下面詳細(xì)介紹隨機決策樹的深度選擇和數(shù)目的選擇及其分類。 (2)選擇隨機決策樹的個數(shù)。非葉子結(jié)點不記錄經(jīng)過分支的事例數(shù)目 ,葉子中信息形式如 : 1 1 2 2{ ( , ) , ( , ) , ..., ( , ) }mmd s d s d s。當(dāng)對事例進行分類時 , 預(yù)測為預(yù)定類別 di 的概率11( 1 , 2 , . . . )NijjP i m PN ??? ?。Si 為該葉子結(jié)點處訓(xùn)練數(shù)據(jù)集中標(biāo)記為 di 類的數(shù)目。最新的研究表明 [6],構(gòu)造多分類器的集成 ,這樣可以提高分類精度 .隨機森林就是許多決策樹的集成 . 為了構(gòu)造 k 棵樹 ,我們得先產(chǎn)生 k 個隨機向量 12, ,..., k? ? ? ，這些隨機向量 i? 是相互獨立并且是同分布?？梢钥闯?,邊際越大分類的置信度就越高。 隨機森林的泛化誤差上界的定義為 _* 2 2(1 ) /P E s s??? () 其中 _? 是相關(guān)系數(shù)的均值 ,s 是樹的分類強度 。由于集成學(xué)習(xí)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國際機器學(xué)習(xí)界的研究熱點。他們的實驗結(jié)果表明，這一組神經(jīng)網(wǎng)絡(luò)形成的集成，比最好的個體神經(jīng)網(wǎng)絡(luò)的性能還好。但是這個算法存在著一個重大的缺陷，就是必須知道學(xué)習(xí)算法正確率的下限，這在實際中很難做到。廣義地來說，只要是使用多個學(xué)習(xí)器來解決問題，就是集成學(xué)習(xí) [47,48]。這種構(gòu)成 方法，用于集成的每個算法的輸入變量是原變量集的一個子集。 3. 樣本集重新抽樣法。不穩(wěn)定的算法指的是當(dāng)訓(xùn)練數(shù)據(jù)發(fā)生很小變化的時候，結(jié)果就能產(chǎn)生很大變化的算法。對于許多算法如神經(jīng)網(wǎng)絡(luò)、遺傳算法來說，在算法應(yīng)用的開始首先要解決的就是要選擇算法參數(shù)。 集成算法的作用主要體現(xiàn)在如下四個方面： 1. 提高預(yù)測結(jié)果的準(zhǔn)確性 。 2. 提高預(yù)測結(jié)果的穩(wěn)定性。在對己知的數(shù)據(jù)集合進行學(xué)習(xí)的時候，我們常常選擇擬 合度值最好的一個模型作為最后的結(jié)果。對于一些算法而言，如神經(jīng)網(wǎng)絡(luò)、遺傳算法，在解決實際問題的時候，需要選擇操作參數(shù)。 集成學(xué)習(xí)經(jīng)過了十幾年的不斷發(fā)展，各種不同的集成學(xué)習(xí)算法不斷被提了出來，其中以 Boosting 和 Bagging 的影響最大。 Kaerns 和 valiant 提出了弱學(xué)習(xí)算法與強學(xué)習(xí)算法的等價性問題，即是否可以將弱學(xué)習(xí)算法提升成強學(xué)習(xí)算法的問題。在 Freund 的方法中通過 Boosting 產(chǎn)生一系列神經(jīng)網(wǎng)絡(luò)，各網(wǎng)絡(luò)的訓(xùn)練集決定于在其之前產(chǎn)生的網(wǎng)絡(luò)的表現(xiàn)，被已有網(wǎng)絡(luò)錯誤判斷的示例將以較大的概率出現(xiàn)在新網(wǎng)絡(luò)的訓(xùn)練集中。 1995年， Freund 和 schapire 提出了 AdaBoost (Adaptive Boosting)算法 [46]， 該算法的效率與 Freund[9]算法很接近，而且 可以很容易地應(yīng)用到實際問題中，因此，該算法已成為目前最流行的 Boosting 算法。最終的分類器從這一系列的分類器中綜合得出。強分類器對數(shù)據(jù)進行分類，是通過弱分類器的多數(shù)投票機制進行的。 ? 將 h1分錯的數(shù)據(jù)和 其它 的新數(shù)據(jù)一起構(gòu)成一個新的有 N個訓(xùn)練數(shù)據(jù)的樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器 h2。 Adaboost 算法描述 對于 Boosting 算法，存在兩個問題 : 1. 如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練弱分類器得以進行。 ? 最終經(jīng)過提升的強分類器 1 2 3( , , )finalh M a jor it y V o te h h h? ? ?。該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能力。 Boosting 是一種將弱分類器通過某種方式結(jié)合起來得到一個分類性能大大提高的強分類器的分類方法。尤其是在學(xué)習(xí)完分類器之后，增加由之導(dǎo)致分類錯誤的訓(xùn)練示例的權(quán)值，并通過重新對 訓(xùn)練示例計算權(quán)值，再學(xué)習(xí)下一個分類器。另一方面，雖然 Boosting 方法能夠增強神經(jīng)網(wǎng)絡(luò)集成的泛化能力，但是同時也有可能使集成過分偏向于某幾個特別困難的示例。 1990 年， schapire[49] 通過 一個構(gòu)造性方法對該問題做出了肯定的證明，其構(gòu)造過程稱為 Boosting。在下面的章節(jié)中對這兩種算法進行了詳細(xì)的介紹。而且參數(shù)選擇不同，結(jié)果會有很大的差異。為了解決過擬合問題，按照集成學(xué)習(xí)的思想，可以選擇多個模型作為結(jié)果，對于每個模型賦予相應(yīng)的權(quán)重，從而集合生成合適的結(jié)果，提高預(yù)測精度。通過模型的集成，可以在多種數(shù)據(jù)集中以較高的概率普遍取得很好的結(jié)果。構(gòu)造單個高精度的學(xué)習(xí)器是一件相當(dāng)困難的事情，然而產(chǎn)生若干個只比隨機猜想略好的學(xué)勻器卻很容易。在實際應(yīng)用中，就需要操作者根據(jù)自己的經(jīng)驗進行選擇。但是對于穩(wěn)定的算法來說，效果不是很好。目前的大部分研究主要集中在使用這種構(gòu)成方法來集成學(xué)習(xí)，如 Bagging， Boosting 等等。 2. 輸出變量集重構(gòu)法。所以在廣義的情況下，集成學(xué)習(xí)已經(jīng)成為了一個包含內(nèi)容相當(dāng)多的、比較大的研究領(lǐng)域。 1996 年， Breiman[46]提出了與 Boosting 相似的技術(shù) Bagging，進一步 促進了集成學(xué)習(xí)的發(fā)展。 1990 年， Schapire[45]通過一個構(gòu)造性方法對弱 學(xué)習(xí)算法與強學(xué)習(xí)算法是否等價的問題作了肯定的證明，證明多個弱分類器可以集成為一個強分類器，他的工作奠定了集成學(xué)習(xí)的理論基礎(chǔ)。在此之后，集成學(xué)習(xí)的研究才逐漸引起了人們的關(guān)注。當(dāng)隨機森林中各個分類器的相關(guān)程度 _? 增大時，泛化誤差*PE 上界就增大；當(dāng)各個分類器的分類強度增大時，泛化誤差 *PE 上界就增大。 將上面的結(jié)論推廣到隨機森林 , ( ) ( , )kkh X h X ?? 。 給定 k 個分類器 12( ), ( ), ...., ( )kh x h x h x和隨機向量 x、 y,定義邊緣函數(shù) ( , ) ( ( ) ) m a x ( ( ) )k k k kjym g x y a v I h x y a v I h x j?? ? ? ? () 其中 ()I? 是示性函數(shù)。 由于完全隨機的選擇屬性 ,因而可能會出現(xiàn)某些屬性在整個決策樹構(gòu)造過程中沒有或很少被選取為分裂屬性 ,特別是當(dāng)該屬性對分類結(jié)果有較大貢獻時 ,這種缺少將導(dǎo)致分類正確率的不穩(wěn)定 ,當(dāng)屬性 數(shù)較少時 ,這種不穩(wěn)定性將更為明顯。 /jiP s S? 為每棵隨機決策樹輸出的后驗概率 。 12 ... mS s s s? 表示某一葉子結(jié)點記錄的總事例數(shù)。 (3)葉子 結(jié)點的更新。使用多個隨機樹的主要特色是多樣性導(dǎo)致較高的分類準(zhǔn)確率 ,多樣性不與深度成正比關(guān)系。在后 2 種情 況下 ,分類結(jié)果標(biāo)記為訓(xùn)練數(shù)據(jù)集中最普通的類 ,或是出現(xiàn)概率最高的類。隨機決策樹的構(gòu)造過程 :對根結(jié)點和分支結(jié)點隨機的從屬性集合中選擇分裂屬性 ,在一條分支路徑上離散屬性僅出現(xiàn)一次 ,連續(xù)屬性可以出現(xiàn)多次。如果剪去該節(jié)點導(dǎo)致較高的期望錯誤率，則保留該子樹；否則剪去該子樹，最后得到具有最小期望錯誤率的決策樹。過多的分枝會使得決策樹過分地依賴某一屬性，而信息增益不低于平均值保證了該屬性的信息量，使得有利于分類的屬性更早地出現(xiàn)。要是節(jié)點中所有樣本都在同一個類，則該節(jié)點成為樹葉，以該客戶類別標(biāo)記該樹葉。以屬性 X為分類所需的期望熵（條件熵）是： 1 11...( ) ( , .. ., )v j m j j m jjssE X I s ss???? ? () 其中 sij 是子集 Sj 中屬于類 Ci 的樣本數(shù)，121( , ..., ) l o g ( )mj m j i j i jiI s s p p??? ? ，ijijjsp s? 是 sj 中的樣本屬于 Ci 的概率。以上三個問題均已被證明為 NP 難題，所以 ,決策樹算法一般只能找到一棵近似最優(yōu)決策樹 [40]。后剪枝法主要有①訓(xùn)練和驗證集法，②使用統(tǒng)計的方法，③最小描述長度準(zhǔn)則。 圖 一顆決策樹實例 為了避免過度擬和現(xiàn)象的出現(xiàn)，在決策樹的生成階段要對決策樹進行必要修剪。 決策樹分類算法使用訓(xùn)練樣本集合構(gòu)造出一棵決策樹，從而實現(xiàn)了對樣本空間的劃分。第三階段從 20 世紀(jì) 70 年代中葉到 80 年代中葉 ,稱為復(fù)興時期。但這種學(xué)習(xí)的結(jié)果遠(yuǎn)不能滿足人們對機器學(xué)習(xí)系統(tǒng)的期望。第一階段是 20 世紀(jì) 50 年代中葉到 60 年代中葉 ,屬于熱烈時期。第二部分介紹了預(yù)測模型的具體構(gòu)建