基于最大似然的網絡拓撲推斷技術研究（二）

王 黎，張潤生

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

基于最大似然的網絡拓撲推斷技術研究（二）

王 黎，張潤生

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

（接5月刊）

3.2 廣義似然比算法

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

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

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

則樣本數據關于參數集合｛μ1，μ2，σ1，σ2｝的似然函數為

假設σ1

2= σ2

2= σ2得到

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

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

在假設H0下

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

得

可得廣義似然比為

在假設H0下

可得

3.3 算法步驟

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

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

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

4　性能分析

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

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

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

可得

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

（未完待續）

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