基于最大似然的網(wǎng)絡拓撲推斷技術(shù)研究（二）

王 黎，張潤生

（中國電子科技集團公司第五十四研究所，石家莊 050081）

基于最大似然的網(wǎng)絡拓撲推斷技術(shù)研究（二）

王 黎，張潤生

（中國電子科技集團公司第五十四研究所，石家莊 050081）

（接5月刊）

3.2 廣義似然比算法

我們可以通過廣義似然比（GLRT）算法［15］構(gòu)造假設檢驗來推斷兩個樣本集合的總體均值是否相等。設有兩個正態(tài)總體f1，f2，均值分別為μ1，μ2，方差為σ12，σ2

2，來自兩個總體的抽樣集合為S1=｛x1i，i=1，…，m｝，S2=｛x2i，i=1，…，n｝，樣本容量分別為m，n，可以構(gòu)造如下假設檢驗

H0： μ1= μ2= μ ， H1： μ1≠ μ2（3）

則樣本數(shù)據(jù)關(guān)于參數(shù)集合｛μ1，μ2，σ1，σ2｝的似然函數(shù)為

假設σ1

2= σ2

2= σ2得到

在假設H1下，似然函數(shù)可以用（5）式表示，可得μ1，μ2，σ2的最大似然估計為

將（6），（7），（8）式代入（5）得

在假設H0下

由（9）可得μ和σ的最大似然估計為

得

可得廣義似然比為

在假設H0下

可得

3.3 算法步驟

1）將所有葉子節(jié)點看成子樹，即令S=D；

3）通過GLRT算法判斷｛ i ， j ｝的合并方式，將｛ i ， j ｝合并成子樹k，更新集合S，S=S｛ i ， j ｝k；

4）如果集合S中元素個數(shù)為1，則結(jié)束，否則返回步驟2）。

4　性能分析

通過分析第三節(jié)提出的算法，可以發(fā)現(xiàn)樹狀拓撲推斷的正確概率由兩方面決定，一是最相關(guān)子樹尋找正確的概率；二是子樹合并方式判斷中假設檢驗的正確概率。

由于葉子節(jié)點相關(guān)性滿足單調(diào)性，因此在理想情況下，尋找最相關(guān)子樹不會發(fā)生錯誤，而實際中由于節(jié)點相關(guān)性測量誤差的存在，在測量樣本容量不大或者測量樣本集合中存在較多野值時，最相關(guān)子樹的尋找則可能發(fā)生錯誤，我們假設在序貫合并過程中，每次尋找最相關(guān)子樹的平均錯誤概率為γ，則隨著樣本容量。

在判斷子樹合并方式的假設檢驗時，我們給定顯著性水平為α，即檢驗犯第一類錯誤的概率（即兩節(jié)點是同一節(jié)點的情況下，判定為非同一節(jié)點的概率）為α。下面我們推導犯第二類錯誤的概率（即兩節(jié)點不是同一節(jié)點的情況下，判定為同一節(jié)點的概率），（14）（15）（16）式都是在假設H0的條件下得出，而在假設H1成立的條件下，設δ=μ1-μ2，則有

可得

通過分析可得，整個序貫合并過程需要尋找最大相關(guān)子樹Nr-1次，需要進行M-1次的假設檢驗，其中Nr為葉子節(jié)點個數(shù)，M為真實拓撲中內(nèi)部節(jié)點個數(shù)。因此，基于假設檢驗的序貫拓撲推斷算法的正確推斷概率。

（未完待續(xù)）

The Technology of Topology Based on Maximum Likelihood （II）

Wang Li， Zhang Runsheng
（The 54th Research Institute of CETC ， Shijiazhuang Hebei 050081， China）

10.3969/J.ISSN.1672-7274.2016.07.009

TN911 文獻標示碼：A

1672-7274（2016）07-0022-02