應(yīng)用屬性約簡(jiǎn)構(gòu)建含有缺失數(shù)據(jù)的譜系樹(shù)

朱 銳，馮宏偉，馮 筠，王惠亞，劉建妮，韓 健

1.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，西安 710127

2.西北大學(xué) 數(shù)學(xué)學(xué)院，西安 710127

3.西北大學(xué) 地質(zhì)學(xué)系，西安 710069

1 引言

隨著生物信息學(xué)的發(fā)展，譜系樹(shù)的構(gòu)建已成為生物信息學(xué)重要的組成部分。通過(guò)對(duì)譜系演化樹(shù)的研究，可以推測(cè)生物進(jìn)化模型，進(jìn)行生物差異性研究。目前國(guó)內(nèi)外常用的運(yùn)用形態(tài)學(xué)數(shù)據(jù)構(gòu)建譜系樹(shù)的方法有鄰接法[1]、最大簡(jiǎn)約法與貝葉斯法[2]，其中最大簡(jiǎn)約法是生物進(jìn)化研究中重要的分析方法，對(duì)于處理復(fù)雜的生物演化過(guò)程有著重要的意義[3]。

最大簡(jiǎn)約法（Maximum parsimony）是基于奧卡姆剃刀原則（Occam’srazor）發(fā)展起來(lái)的一種譜系樹(shù)重構(gòu)方法，基本思想是認(rèn)為物種之間真實(shí)的進(jìn)化關(guān)系應(yīng)該演化步驟最少[4]。最大簡(jiǎn)約法首先由Camin&Sokal提出[5]，在Hein的研究推廣下得到了極大地發(fā)展和應(yīng)用[6-7]。然而，隨著生物屬性數(shù)量的增加，譜系樹(shù)可能的拓?fù)浣Y(jié)構(gòu)呈現(xiàn)爆炸式的增長(zhǎng)，啟發(fā)式尋優(yōu)應(yīng)運(yùn)而生[1]。然而簡(jiǎn)約法啟發(fā)式搜索可能會(huì)產(chǎn)生多棵簡(jiǎn)約樹(shù)，此時(shí)通常選取一棵能概括這些簡(jiǎn)約樹(shù)的一致樹(shù)作為代表[8]，將最大簡(jiǎn)約法提升到了新的高度。

但是，隨著生物屬性缺失數(shù)據(jù)比例的增加，最大簡(jiǎn)約法中的啟發(fā)式查找的范圍不斷擴(kuò)大，造成譜系樹(shù)的結(jié)構(gòu)極其不穩(wěn)定。最大簡(jiǎn)約法在構(gòu)建含有缺失數(shù)據(jù)的譜系樹(shù)時(shí)會(huì)出現(xiàn)兩個(gè)問(wèn)題：（1）物種中的缺失數(shù)據(jù)的出現(xiàn)會(huì)導(dǎo)致其在譜系樹(shù)中位置的準(zhǔn)確率大大降低；（2）缺失數(shù)據(jù)物種中的缺失值對(duì)譜系樹(shù)中其他物種的種間關(guān)系產(chǎn)生影響[9]。并且生物形態(tài)學(xué)數(shù)據(jù)集一般為小樣本數(shù)據(jù)，由于數(shù)據(jù)量少而無(wú)法進(jìn)行回歸分析，對(duì)缺失數(shù)據(jù)的預(yù)測(cè)填補(bǔ)不具有統(tǒng)計(jì)正確性，阻礙著生物類(lèi)群譜系樹(shù)構(gòu)建的研究和發(fā)展[10]。

譜系樹(shù)是一種樹(shù)狀結(jié)構(gòu)的層次化分類(lèi)模型，在譜系樹(shù)中出現(xiàn)分支時(shí)可以把生物物種對(duì)應(yīng)地分類(lèi)成若干個(gè)集合。屬性約簡(jiǎn)是處理分類(lèi)模型重要的分析方法[11]，同時(shí)也是一種處理缺失數(shù)據(jù)的常用方法。屬性約簡(jiǎn)是在保證分類(lèi)能力不變的情況下，刪除其中不相關(guān)或不重要的屬性，大大提高系統(tǒng)潛在知識(shí)的清晰度[12]。從而用最簡(jiǎn)約的屬性保障分類(lèi)能力，進(jìn)而在出現(xiàn)缺失數(shù)據(jù)時(shí)保持分類(lèi)的穩(wěn)定性。

本文針對(duì)含有缺失形態(tài)學(xué)數(shù)據(jù)難以建立有效譜系樹(shù)的問(wèn)題，提出應(yīng)用屬性約簡(jiǎn)構(gòu)建含有缺失數(shù)據(jù)譜系樹(shù)的方法。首先，利用相對(duì)完整的物種數(shù)據(jù)運(yùn)用最大簡(jiǎn)約法構(gòu)建出一棵初始譜系樹(shù)；其次，對(duì)初始譜系樹(shù)構(gòu)造層次化分類(lèi)節(jié)點(diǎn)，運(yùn)用屬性約簡(jiǎn)獲得屬性決策組集合，進(jìn)而建立基于初始譜系樹(shù)的先驗(yàn)決策模型；接著，將有缺失信息的物種嫁接到初始譜系樹(shù)中，完成譜系樹(shù)的構(gòu)建。本方法主要特色為：一方面利用了初始譜系樹(shù)的先驗(yàn)信息，提高了含有缺失數(shù)據(jù)的物種在譜系樹(shù)中的準(zhǔn)確率；另一方面，避免了缺失數(shù)據(jù)物種對(duì)完整數(shù)據(jù)構(gòu)建譜系樹(shù)的穩(wěn)定性影響。

2 應(yīng)用屬性約簡(jiǎn)構(gòu)建含有缺失數(shù)據(jù)的譜系樹(shù)

為了完成含有大量缺失信息的譜系樹(shù)構(gòu)建，基本思路是：首先，將數(shù)據(jù)集劃分為兩個(gè)部分，一部分為缺失比例較低的物種集，作為初始物種集，運(yùn)用最大簡(jiǎn)約法構(gòu)建可信度較高的初始譜系樹(shù)。另一部分為缺失比例較高的物種，做為待嫁接的物種，接入譜系樹(shù)中，最終完成整體譜系樹(shù)的構(gòu)建。

2.1 初始譜系樹(shù)的構(gòu)建以及節(jié)點(diǎn)的建立

首先，本文提出在生物形態(tài)學(xué)數(shù)據(jù)集中，將不含缺失數(shù)據(jù)或者含有少量缺失數(shù)據(jù)的物種提出來(lái)合并成一個(gè)數(shù)據(jù)集，運(yùn)用最大簡(jiǎn)約法構(gòu)建可信度較高的初始譜系樹(shù)，或根據(jù)研究者自己已有的先驗(yàn)知識(shí)構(gòu)建初始譜系樹(shù)。

其次，對(duì)初始譜系樹(shù)中出現(xiàn)分支的地方建立節(jié)點(diǎn)。如圖1中的N1～N4。初始譜系樹(shù)的末端為參與構(gòu)建譜系樹(shù)的物種，如圖1中的A～E。每個(gè)節(jié)點(diǎn)處都有著從屬于當(dāng)前節(jié)點(diǎn)的物種集合，并且把從屬物種分為幾類(lèi)。

圖1 初始譜系樹(shù)分支節(jié)點(diǎn)的建立

在圖1中，圓表示節(jié)點(diǎn)，方框表示物種。根據(jù)圖中的4個(gè)分支分別建立分支節(jié)點(diǎn)，標(biāo)號(hào)依次為N1、N2、N3、N4，每個(gè)分支節(jié)點(diǎn)都有著從屬于該節(jié)點(diǎn)的物種。在N1節(jié)點(diǎn)處，從屬物種為A、B、C、D、E，由節(jié)點(diǎn)處的分支可把從屬物種分為兩類(lèi)，A為一類(lèi)，B、C、D、E為一類(lèi)。而N2節(jié)點(diǎn)下的從屬物種為B、C、D、E，則把從屬物種分為B、C以及D、E兩類(lèi)。在N3和N4節(jié)點(diǎn)處從屬物種分別為B、C和D、E。兩個(gè)節(jié)點(diǎn)亦被分為兩類(lèi)，N3節(jié)點(diǎn)為B一類(lèi)以及C一類(lèi)，N4節(jié)點(diǎn)為D一類(lèi)和E一類(lèi)。

2.2 應(yīng)用屬性約簡(jiǎn)構(gòu)建先驗(yàn)決策模型

利用構(gòu)建好的初始譜系樹(shù)，確定分支節(jié)點(diǎn)后，將當(dāng)前節(jié)點(diǎn)的從屬物種分類(lèi)標(biāo)簽和從屬物種屬性作為一個(gè)決策表。決策表是一類(lèi)特殊而重要的知識(shí)表達(dá)系統(tǒng)，有著重要的作用[13]。對(duì)決策表進(jìn)行屬性約簡(jiǎn)進(jìn)而產(chǎn)生屬性決策組，多次建立屬性決策組完成決策點(diǎn)的建立。通過(guò)對(duì)譜系樹(shù)中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)決策點(diǎn)的建立，最終建立先驗(yàn)決策模型?；玖鞒倘鐖D2所示。

2.2.1 節(jié)點(diǎn)對(duì)應(yīng)決策點(diǎn)的建立

圖2 基于初始譜系樹(shù)的先驗(yàn)決策模型構(gòu)建流程

將節(jié)點(diǎn)從屬物種屬性集合與分類(lèi)標(biāo)簽看作決策表，進(jìn)行一次屬性約簡(jiǎn)，并沒(méi)有充分地利用先驗(yàn)信息。并且單一屬性決策組很容易因缺失數(shù)據(jù)的出現(xiàn)使得當(dāng)前決策失效。因此多次進(jìn)行屬性約簡(jiǎn)操作并得到屬性決策組集合，以此作為當(dāng)前決策點(diǎn)的決策判斷依據(jù)。

算法說(shuō)明：C={ai,i=1,2,…,m}稱(chēng)為節(jié)點(diǎn)從屬物種形態(tài)學(xué)屬性集，D={di,i=1,2,…,n}稱(chēng)為節(jié)點(diǎn)從屬物種類(lèi)標(biāo)簽屬性集。對(duì)整個(gè)條件屬性集進(jìn)行約簡(jiǎn)，利用正區(qū)域的啟發(fā)式信息逐步將該集合中不必要的屬性約去，但仍滿(mǎn)足當(dāng)前決策點(diǎn)的分類(lèi)，得到的屬性約簡(jiǎn)組，即屬性決策組Reduct1，剔除原來(lái)屬性集合中參與建立屬性決策組的屬性，對(duì)剩余的條件屬性集繼續(xù)進(jìn)行屬性約簡(jiǎn)并得到相應(yīng)的Reducti，直到條件屬性集不能再構(gòu)建屬性決策組為止。具體的算法描述如下：

輸入：節(jié)點(diǎn)從屬物種信息系統(tǒng)決策表。

輸出：屬性決策組集合reducti(i=1,2,…,n)。

步驟1計(jì)算決策點(diǎn)從屬物種分類(lèi)屬性D對(duì)于從屬物種屬性C的正區(qū)域POSc(D)。

步驟2對(duì)每個(gè)當(dāng)前節(jié)點(diǎn)從屬物種屬性ai計(jì)算pos=POSC(D)-POS(c-{ai})(D)。

步驟3令Reduct=C；將屬性ai按 pos從小到大的順序排列，對(duì)每個(gè)屬性執(zhí)行操作；若POS(Reduct-{ai})(D)=POSC(D)，則屬性 ai應(yīng)約簡(jiǎn)，Reduct=Reduct-{ai}；否則ai不能被約簡(jiǎn)，Reduct不變。

步驟4得到屬性決策組Reducti，對(duì)參與建立屬性決策組的屬性進(jìn)行剔除，即residue=C-Reducti。

步驟5把剩余條件屬性集residue賦予C，即C=residue。

步驟6執(zhí)行步驟1，建立決策點(diǎn)的多屬性組reducti(i=1,2,…,n)直到C條件屬性集無(wú)法構(gòu)建屬性決策組為止。

通過(guò)對(duì)節(jié)點(diǎn)從屬物種決策表進(jìn)行多次屬性約簡(jiǎn)，進(jìn)而構(gòu)建屬性決策組集合，得到與節(jié)點(diǎn)對(duì)應(yīng)的決策點(diǎn)，最終構(gòu)建出決策點(diǎn)模型，如圖3所示，reduct1到reductn為決策點(diǎn)中的屬性決策組集合。

圖3 決策點(diǎn)模型

2.2.2 基于決策點(diǎn)的先驗(yàn)決策模型構(gòu)建

對(duì)初始譜系樹(shù)中的每個(gè)節(jié)點(diǎn)建立對(duì)應(yīng)決策點(diǎn)，進(jìn)而獲得初始譜系樹(shù)的決策先驗(yàn)?zāi)Ｐ?，模型的?shù)狀拓?fù)浣Y(jié)構(gòu)與初始譜系樹(shù)的結(jié)構(gòu)一致，如圖4所示，圖中的圓表示決策點(diǎn)，方框表示物種。

圖4 初始譜系樹(shù)先驗(yàn)決策模型

圖2中初始譜系樹(shù)共有4個(gè)節(jié)點(diǎn)，對(duì)應(yīng)建立的決策點(diǎn)為圖4中的P1、P2、P3、P4。決策模型結(jié)構(gòu)的末端為物種，與圖2中物種對(duì)應(yīng)，為A、B、C、D、E。

2.3 基于先驗(yàn)決策模型的含有缺失數(shù)據(jù)譜系樹(shù)構(gòu)建

先驗(yàn)決策模型的構(gòu)建利用了初始譜系樹(shù)中物種間進(jìn)化關(guān)系的先驗(yàn)信息，將初始譜系樹(shù)轉(zhuǎn)換為了一個(gè)層次化結(jié)構(gòu)的分類(lèi)器。將含有較多缺失數(shù)據(jù)的嫁接物種帶入到先驗(yàn)決策模型分類(lèi)器中，自根決策點(diǎn)出發(fā)，逐層地進(jìn)行決策點(diǎn)嫁接物種歸屬的判斷。由于缺失數(shù)據(jù)的出現(xiàn)，在判斷的過(guò)程中會(huì)使當(dāng)前決策點(diǎn)的某些決策屬性組判斷失效，則判定其無(wú)法判斷物種歸屬，進(jìn)而依據(jù)其他的完整數(shù)據(jù)進(jìn)行決策屬性組物種歸屬判斷。

這里設(shè)屬于A樹(shù)的屬性組數(shù)為m，屬于B樹(shù)的屬性組數(shù)為n。

步驟1初始狀態(tài)令m=0，n=0。

步驟2通過(guò)對(duì)嫁接物種在決策點(diǎn)中的每個(gè)屬性組的屬性比對(duì)，如在對(duì)應(yīng)子樹(shù)出現(xiàn)相同屬性組，則判定屬于A樹(shù)或者屬于B樹(shù)，并對(duì)歸屬屬性組數(shù)進(jìn)行累加。

步驟3如果既不屬于A樹(shù)也不屬于B樹(shù)，或者因缺失數(shù)據(jù)而導(dǎo)致無(wú)法判斷歸屬，則m、n不進(jìn)行累加。

步驟4完成每個(gè)屬性組的歸屬判斷后，最終得出嫁接物種子樹(shù)歸屬的屬性組數(shù)m、n。則嫁接物種決策點(diǎn)歸屬判斷策略為：

按照上述決策點(diǎn)判斷策略，嫁接物種從先驗(yàn)決策模型的根決策點(diǎn)開(kāi)始判斷歸屬，認(rèn)定歸屬于A子樹(shù)或者B子樹(shù)后，針對(duì)歸屬子樹(shù)的根決策點(diǎn)繼續(xù)進(jìn)行歸屬判斷。反復(fù)執(zhí)行此操作直到停止判斷。

嫁接物種停止判斷后，該物種在先驗(yàn)決策模型中的判斷歷程結(jié)束，進(jìn)行嫁接物種嫁接過(guò)程。將嫁接物種嫁接在最終到達(dá)的決策點(diǎn)對(duì)應(yīng)的初始譜系樹(shù)節(jié)點(diǎn)中。嫁接物種嫁接子樹(shù)過(guò)程如圖5所示，在P決策點(diǎn)停止判斷歸屬歷程，并嫁接在P決策點(diǎn)對(duì)應(yīng)的初始譜系樹(shù)中的節(jié)點(diǎn)N上，成為初始譜系樹(shù)的新分支。

圖5 初始譜系樹(shù)節(jié)點(diǎn)建立分支示意圖

3 實(shí)驗(yàn)結(jié)果和分析

本文采取的實(shí)驗(yàn)環(huán)境：Windows 7，8 GB內(nèi)存，編程語(yǔ)言是MATLAB。為了驗(yàn)證本文方法的有效性，實(shí)驗(yàn)運(yùn)用不含缺失數(shù)據(jù)或者含有少量缺失數(shù)據(jù)的具有明確譜系的生物形態(tài)學(xué)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，對(duì)其中的物種進(jìn)行隨機(jī)數(shù)據(jù)缺失處理，運(yùn)用本論文提出的方法與最大簡(jiǎn)約法譜系樹(shù)進(jìn)行實(shí)驗(yàn)對(duì)比得出結(jié)論。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)對(duì)象選取了利用形態(tài)學(xué)構(gòu)建譜系樹(shù)的已發(fā)表論文中的三個(gè)數(shù)據(jù)集[14-16]，數(shù)據(jù)集中的形態(tài)學(xué)編碼：0為原始性狀，1為進(jìn)化性狀。有些性狀為多態(tài)性狀，則連續(xù)的編碼為2、3。多態(tài)性狀均為無(wú)序性狀，在無(wú)序性狀中任何兩個(gè)狀態(tài)的性狀距離是相等的，例如0～1和0～2之間的進(jìn)化距離都為1，為缺失性狀，即不明性狀。

3.2 單個(gè)物種嫁接實(shí)驗(yàn)及對(duì)比分析

以Palaearctic parasite species of Testudinidae數(shù)據(jù)集為例來(lái)說(shuō)明實(shí)驗(yàn)過(guò)程。首先構(gòu)建用來(lái)評(píng)價(jià)的標(biāo)準(zhǔn)譜系樹(shù)，結(jié)果如圖6所示。

圖6 《Palaearctic parasite species of Testudinidae》標(biāo)準(zhǔn)譜系樹(shù)

對(duì)物種T.marocana的形態(tài)學(xué)數(shù)據(jù)進(jìn)行隨機(jī)缺失處理，數(shù)據(jù)缺失率為30%，運(yùn)用本論文提出的方法構(gòu)建譜系樹(shù)如圖7所示。嫁接點(diǎn)為實(shí)心圓處。

圖7 《Palaearctic parasite species of Testudinidae》本文方法構(gòu)建的譜系樹(shù)

本方法的對(duì)比實(shí)驗(yàn)是將含有缺失比例為30%的物種T.marocana與其他24個(gè)物種運(yùn)用最大簡(jiǎn)約法構(gòu)建譜系樹(shù)。構(gòu)建的譜系樹(shù)如圖8所示。

圖8 《Palaearctic parasite species of Testudinidae》最大簡(jiǎn)約法構(gòu)建的譜系樹(shù)

從圖6～8中的結(jié)果可以看出，本論文提出的方法相比較最大簡(jiǎn)約法，得出了更加接近標(biāo)準(zhǔn)譜系樹(shù)的結(jié)果。而進(jìn)行缺失數(shù)據(jù)處理運(yùn)用最大簡(jiǎn)約法得出的樹(shù)不僅使得T.marocana物種的種間關(guān)系產(chǎn)生紊亂，如圖8實(shí)線框部分，而且還影響了其他樣本的種間關(guān)系如圖8虛線框部分。

3.3 方法可靠性驗(yàn)證及分析

為了進(jìn)一步說(shuō)明本方法的優(yōu)勢(shì)，選取三個(gè)數(shù)據(jù)集，分別為 Palaearctic parasite species of Testudinidae、菜花露尾甲屬和木槿屬形態(tài)學(xué)數(shù)據(jù)集[14-16]進(jìn)行實(shí)驗(yàn)。提出了一種基于路徑的物種準(zhǔn)確率計(jì)算方法，并對(duì)每個(gè)物種集中的每個(gè)物種進(jìn)行上述實(shí)驗(yàn)，求得當(dāng)前缺失比例下的平均準(zhǔn)確率，缺失率實(shí)驗(yàn)點(diǎn)為0%～70%。

3.3.1 物種準(zhǔn)確率計(jì)算方法

為了評(píng)價(jià)生成譜系樹(shù)的準(zhǔn)確性，本文提出一種基于單個(gè)物種節(jié)點(diǎn)路徑的準(zhǔn)確率判定方法，以譜系樹(shù)嫁接物種的種間關(guān)系作為評(píng)價(jià)標(biāo)準(zhǔn)，能充分說(shuō)明在嫁接物種后譜系樹(shù)的樹(shù)形結(jié)構(gòu)變化。以嫁接物種為基準(zhǔn)，說(shuō)明嫁接物種與初始譜系樹(shù)中物種間的樹(shù)形結(jié)構(gòu)關(guān)系。

以嫁接物種為基準(zhǔn)，從根節(jié)點(diǎn)到嫁接物種的最后一個(gè)嫁接節(jié)點(diǎn)構(gòu)建一個(gè)物種序列，每次遇到節(jié)點(diǎn)時(shí)構(gòu)建的序列為當(dāng)前節(jié)點(diǎn)另一分支的物種編號(hào)集合。以圖2中的譜系樹(shù)為標(biāo)準(zhǔn)，建立以E物種為基準(zhǔn)的物種序列，節(jié)點(diǎn)路徑依次為1、2、4，則物種的序列對(duì)應(yīng)為（（（A）B，C）D）。

以未經(jīng)過(guò)缺失數(shù)據(jù)處理的物種運(yùn)用最大簡(jiǎn)約法構(gòu)建的譜系樹(shù)做為標(biāo)準(zhǔn)，建立該物種的序列，稱(chēng)為標(biāo)準(zhǔn)序列。對(duì)該物種進(jìn)行屬性隨機(jī)缺失處理后，分別運(yùn)用本論文方法和最大簡(jiǎn)約法生成新樹(shù)，并分別建立該物種的序列，并與標(biāo)準(zhǔn)序列進(jìn)行比對(duì)。與標(biāo)準(zhǔn)序列匹配的物種個(gè)數(shù)稱(chēng)為路徑匹配物種數(shù)，標(biāo)準(zhǔn)序列物種總數(shù)稱(chēng)為路徑物種總數(shù)。則準(zhǔn)確率的計(jì)算公式為：

3.3.2 驗(yàn)證過(guò)程

依次統(tǒng)計(jì)本文方法與最大簡(jiǎn)約法生成樹(shù)的每個(gè)物種的準(zhǔn)確率，進(jìn)而求得兩種方法在此缺失率下的所有物種的平均準(zhǔn)確率。在此基礎(chǔ)上對(duì)數(shù)據(jù)集中的數(shù)據(jù)繼續(xù)進(jìn)行隨機(jī)缺失處理并逐步提高缺失數(shù)據(jù)率，數(shù)據(jù)缺失率實(shí)驗(yàn)點(diǎn)分別為0%、10%、20%、30%、40%、50%、60%、70%。

將數(shù)據(jù)集中的嫁接物種進(jìn)行隨機(jī)缺失處理，利用文中提出的方法與最大簡(jiǎn)約法構(gòu)建的譜系樹(shù)進(jìn)行準(zhǔn)確率比較。在圖9～11中，橫坐標(biāo)表示物種的缺失數(shù)據(jù)比例，從0%到70%?？v坐標(biāo)表示物種的平均準(zhǔn)確率。

圖9 木槿屬缺失數(shù)據(jù)比例與物種平均準(zhǔn)確率

圖10 菜花露尾甲屬缺失數(shù)據(jù)比例與物種平均準(zhǔn)確率

圖11 《Palaearctic parasite species of Testudinidae》缺失數(shù)據(jù)比例與物種平均準(zhǔn)確率

3.3.3 結(jié)果分析

從以上實(shí)驗(yàn)結(jié)果可以看出，相比最大簡(jiǎn)約法構(gòu)建的譜系樹(shù)，本論文提出方法可以更準(zhǔn)確地預(yù)測(cè)含有缺失數(shù)據(jù)物種所在譜系樹(shù)中的位置。缺失數(shù)據(jù)比例超過(guò)10%時(shí)，本方法構(gòu)建的譜系樹(shù)中的樣本準(zhǔn)確率明顯地高于最大簡(jiǎn)約法。

當(dāng)缺失數(shù)據(jù)比例大于10%時(shí)，本文提出的方法在實(shí)驗(yàn)過(guò)程中隨著缺失數(shù)據(jù)比例的不斷上升，某些個(gè)別物種會(huì)出現(xiàn)表現(xiàn)不佳的情況，這時(shí)最大簡(jiǎn)約法的表現(xiàn)也隨著降低。最大簡(jiǎn)約法在某些個(gè)別物種上的表現(xiàn)優(yōu)于本論文提出的方法，但是總體物種的平均準(zhǔn)確率卻比本論文的方法低。

圖9和圖11中，缺失數(shù)據(jù)比例小于10%時(shí)，最大簡(jiǎn)約法的準(zhǔn)確率高于本論文提出的方法。而圖10則表明缺失數(shù)據(jù)比例小于10%，本論文方法準(zhǔn)確率高于最大簡(jiǎn)約法，但無(wú)缺失時(shí)最大簡(jiǎn)約法的準(zhǔn)確率要高于本論文方法。

兩種方法在缺失數(shù)據(jù)比例為10%到50%時(shí)，準(zhǔn)確率是趨于平穩(wěn)的；在缺失比例小于10%或大于50%時(shí)，兩種方法的準(zhǔn)確率都會(huì)出現(xiàn)比較大的波動(dòng)。

綜上所述，在運(yùn)用生物形態(tài)學(xué)數(shù)據(jù)構(gòu)建譜系樹(shù)時(shí)，單個(gè)物種缺失數(shù)據(jù)比例超過(guò)10%時(shí)，本論文方法的表現(xiàn)是優(yōu)于最大簡(jiǎn)約法的；而在缺失數(shù)據(jù)比例小于10%時(shí)，最大簡(jiǎn)約法則表現(xiàn)更好。實(shí)驗(yàn)結(jié)果表明在生物形態(tài)學(xué)數(shù)據(jù)缺失值比例大于10%時(shí)，運(yùn)用本論文提出的方法所構(gòu)建的譜系樹(shù)有著較高的準(zhǔn)確率。

3.4 方法穩(wěn)定性驗(yàn)證及分析

本論文提出的基于先驗(yàn)決策的譜系樹(shù)構(gòu)建方法在判斷物種間的進(jìn)化關(guān)系時(shí)依賴(lài)著判斷歸屬?zèng)Q策點(diǎn)的屬性決策組，嫁接物種屬性的隨機(jī)缺失影響著物種歸屬的判斷，對(duì)本方法的穩(wěn)定性產(chǎn)生了一定的影響，為此實(shí)驗(yàn)對(duì)單一物種的屬性進(jìn)行多次的隨機(jī)缺失處理，并對(duì)本方法的穩(wěn)定性進(jìn)行評(píng)估。

在穩(wěn)定性方面，運(yùn)用Palaearctic parasite species of Testudinidae數(shù)據(jù)集中的單個(gè)物種在每個(gè)實(shí)驗(yàn)點(diǎn)中進(jìn)行多次隨機(jī)缺失處理，并求得準(zhǔn)確率方差，來(lái)說(shuō)明本方法在不同缺失率下的穩(wěn)定性。從0%～70%共8個(gè)實(shí)驗(yàn)點(diǎn)分別進(jìn)行多次隨機(jī)缺失處理，每個(gè)實(shí)驗(yàn)點(diǎn)隨機(jī)處理次數(shù)為100次，計(jì)算相對(duì)應(yīng)的缺失數(shù)據(jù)物種準(zhǔn)確率，并進(jìn)行方差的計(jì)算。則單個(gè)物種多次隨機(jī)缺失處理準(zhǔn)確率方差如圖12所示。

圖12 單個(gè)物種多次隨機(jī)缺失準(zhǔn)確率方差

從圖12中可以看出，缺失數(shù)據(jù)比例小于50%時(shí)，單個(gè)物種的準(zhǔn)確率方差較低，因此本論文提出的方法有著較好的穩(wěn)定性。在缺失數(shù)據(jù)比例較低的情況下，缺失數(shù)據(jù)的數(shù)量還不足以打破決策點(diǎn)多屬性組的歸屬判斷，因而在多次隨機(jī)缺失處理的情況下本方法還保持著較低的準(zhǔn)確率方差。而在缺失比例大于50%時(shí)，單個(gè)物種的準(zhǔn)確率方差會(huì)出現(xiàn)猛然的上升趨勢(shì)，本方法的穩(wěn)定性有所降低。隨著缺失數(shù)據(jù)比例的上升，隨機(jī)抽取得到的缺失數(shù)據(jù)導(dǎo)致的多屬性組歸屬判斷的穩(wěn)定性會(huì)大大的降低，因此導(dǎo)致了準(zhǔn)確率方差的突然提高。綜上所述，本方法在缺失比例小于50%時(shí)有著較好的穩(wěn)定性，而在缺失數(shù)據(jù)比例大于50%穩(wěn)定性的表現(xiàn)則欠佳。

4 結(jié)束語(yǔ)

本文提出方法，充分利用了初始譜系樹(shù)的先驗(yàn)知識(shí)。能在物種含有較多缺失數(shù)據(jù)的情況下保持良好的準(zhǔn)確率。并且由于含有缺失數(shù)據(jù)物種都是在初始譜系樹(shù)的基礎(chǔ)上進(jìn)行嫁接，因而在構(gòu)建進(jìn)樹(shù)的過(guò)程中都能夠保證含有完整數(shù)據(jù)的譜系樹(shù)的穩(wěn)定性。解決了在缺失數(shù)據(jù)不斷上升的情況下而導(dǎo)致的生成譜系樹(shù)的紊亂的問(wèn)題。

本論文方法的不足之處：（1）相比最大簡(jiǎn)約法，本方法需要初始譜系樹(shù)的先驗(yàn)信息，先驗(yàn)先驗(yàn)信息越多，本方法的預(yù)測(cè)效果也就越好。（2）本模型只會(huì)在當(dāng)前缺失數(shù)據(jù)的比例下給出物種在譜系樹(shù)中的位置，而不是像最大簡(jiǎn)約法，即使含有缺失數(shù)據(jù)也會(huì)給最終啟發(fā)式搜索的最終結(jié)果。將在后續(xù)的工作中繼續(xù)探索和研究。

：

[1]Mucherino A，Seref O.Modeling and solving real-life global optimization problems with meta-heuristic methods[M]//Advances in Modeling Agricultural Systems.US：Springer，2009：403-419.

[2]Yang Z，Rannala B.Molecular phylogenetics：Principles and practice[J].Nature Reviews Genetics，2012，13（5）：303-14.

[3]鄭巍，羅阿蓉，史衛(wèi)峰，等.系統(tǒng)發(fā)育分析中的最大簡(jiǎn)約法及其優(yōu)化[J].昆蟲(chóng)學(xué)報(bào)，2013，56（10）：1217-1228.

[4]Bj?rklund M.Sober，E.1988.Reconstructing the Past.Parsimony，Evolution，and Inference.MIT Press，Cambridge（Mass），London，265 pp.$37.25[J].Journal of Evolutionary Biology，1990，3（5/6）：477.

[5]Camin J H，Sokal R R.A method for deducing branching sequences in phylogeny[J].Evolution，1965，19（3）：311-326.

[6]Hein J.Reconstructing evolution of sequences subject to recombination using parsimony[J].Mathematical Biosciences，1990，98（2）：185-200.

[7]Hein J.A heuristic method to reconstruct the history of sequences subject to recombination[J].Journal of Molecular Evolution，1993，36（4）：396-405.

[8]Taylor M P，Wedel M J，Cifelli R L.A new sauropod dinosaur from the Lower Cretaceous Cedar Mountain Formation，Utah，USA[J].Acta Palaeontologica Polonica，2011，56（1）：75-98.

[9]Wiens J J.Missing data and the design of phylogenetic analyses[J].Journal of Biomedical Informatics，2006，39（1）：34-42.

[10]Wiens J J.Missing data，incomplete taxa，and phylogenetic accuracy[J].Systematic Biology，2003，52（4）：528-538.

[11]Ma X，Wang G，Yu H，et al.Decision region distribution preservation reduction in decision-theoretic rough set model[J].Information Sciences，2014，278：614-640.

[12]張智磊，劉三陽(yáng).基于回溯搜索算法的決策粗糙集屬性約簡(jiǎn)[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（10）：71-74.

[13]張騰飛，肖健梅，王錫淮.粗糙集理論中屬性約簡(jiǎn)算法[J].電子學(xué)報(bào)，2005，33（11）：2080-2083.

[14]Bouamer S，Morand S.Phylogeny of palaearctic pharyngodonidae parasite species of testudinidae：A morphological approach[J].Canadian Journal of Zoology，2003，81（11）：1885-1893.

[15]林曉麗.中國(guó)菜花露尾甲屬分類(lèi)及系統(tǒng)發(fā)育初探（鞘翅目：露尾甲科：訪花露尾甲亞科）[D].陜西咸陽(yáng)：西北農(nóng)林科技大學(xué)，2015.

[16]唐麗丹，原蒙蒙，李妍，等.基于形態(tài)學(xué)性狀的木槿屬系統(tǒng)發(fā)育分類(lèi)研究[J].河南農(nóng)業(yè)科學(xué)，2014，43（2）：105-111.