錢昭勇，曹裕華，史增凱，張 雷

(1.航天工程大學，北京 102206；2.國防大學聯(lián)合勤務學院，北京 100858；3.西安衛(wèi)星測控中心，陜西 西安 710043)

1 引 言

衛(wèi)星導航系統(tǒng)定位的精確性是其在役考核過程中的關鍵問題。影響定位精確性的多維度因素可以理解為多指標評價問題，各指標間并不一定完全獨立，分析指標間相互影響的關聯(lián)規(guī)則有助于更好地掌握和改進定位方式和策略，規(guī)避相關風險和誤區(qū)。馬寧等[1]認為裝備體系是一個復雜系統(tǒng)，系統(tǒng)中各元素在執(zhí)行任務的過程具有一定的關聯(lián)和協(xié)同關系。傳統(tǒng)的效能評估體系框架大多采用同一等級各元素相互獨立的樹形結(jié)構(gòu)，從而忽略指標間的各種相關關系，指出可以基于大量仿真數(shù)據(jù)進行分析，挖掘各指標間的關聯(lián)關系，使得評估結(jié)果可信度更高[2,3]。

研究與定位精度相關聯(lián)的指標和規(guī)則，首先要明確所選擇指標的范圍，因為影響定位精度的因素很多，既有定性指標，又有定量指標，既有衛(wèi)星和接收機等系統(tǒng)因素，又有目標運動狀態(tài)、采樣率等人為因素，選擇合適的指標范圍(例如，可選擇全部指標集或部分相關性更高的指標集)將直接影響考核評估的結(jié)果。其次，分析指標間關聯(lián)關系的方法有很多，其中，最經(jīng)典的關聯(lián)算法是Apriori和FP-Growth，在分析航天器異常[4，5]、評價指標信息挖掘和指標約簡[6]、業(yè)務對口推薦和廣告推送等方面都有廣泛應用價值[7]。本文從關聯(lián)規(guī)則數(shù)量和實效兩個維度對比這兩種算法在不同數(shù)據(jù)范圍的挖掘結(jié)果，探索關聯(lián)規(guī)則算法在衛(wèi)星定位精度分析中的適用性，以期得到有意義的結(jié)論。

2 相關理論

2.1 Xgboost算法

Xgboost的全稱是eXtreme Gradient Boosting，主要通過將多個弱分類器集成轉(zhuǎn)化為一個強分類器，從而達到更精準的分類或者預測效果，同時其可以給出因子的重要性排序[8]。通過使損失函數(shù)在迭代過程中沿梯度方向下降，從而提升算法的穩(wěn)定性。在此基礎上對損失函數(shù)進行二階泰勒展開，并在損失函數(shù)之外對正則項求得最優(yōu)解。具體的重要性指標評價包括兩步：第一，求出每個特征的得分score；第二，求出各特征得分占比score/sum(score)。

2.2 Apriori算法

Apriori模型是由Agrawal等[9]在1994年提出的關聯(lián)規(guī)則挖掘方法，使用支持度作為判斷頻繁項集的標準，其目標是找到最大的K項頻繁集。Apriori算法具體步驟如表1所示。

表1 Apriori算法流程

2.3 FP-Growth算法

FP-Growth算法采用分治策略[10]，與Apriori的最大區(qū)別在于其不產(chǎn)生候選集，只需兩次遍歷數(shù)據(jù)庫，算法具體步驟見表2。

表2 FP-Growth算法流程

3 分析流程與指標篩選

3.1 基于指標篩選的關聯(lián)分析流程

關聯(lián)分析可識別指標間的關聯(lián)性和相關性，即可以確定與定位精度關聯(lián)度更高的指標。當指標較多時，算法計算時長和復雜度都會隨著維度的增加而增加。為此，不僅可以在所有指標上進行關聯(lián)規(guī)則挖掘，也可以先縮小搜索范圍，使用Xgboost算法確定各指標對定位精度影響度的高低，把搜索范圍改為與定位精度相關度更高的指標，從而提高算法效率。總體而言，相關流程如圖1所示。

圖1 衛(wèi)星導航系統(tǒng)定位精度考核關聯(lián)分析

3.2 相關指標篩選

采用某中心的仿真數(shù)據(jù)集，包含13個變量，共30162個樣本。表3詳細描述了變量名稱、標簽和含義。

表3 數(shù)據(jù)變量和含義

由于影響導航系統(tǒng)定位精度的指標參數(shù)數(shù)量巨大，如果分析挖掘所有指標(全域)屬性的關聯(lián)關系，將導致規(guī)則數(shù)量太過繁雜，且運行時間難以接受。通過構(gòu)建Xgboost模型得到對定位精度指標影響程度高的指標排序，如圖2所示，對定位精度指標影響程度高的指標依次為：DOP值A10，導航系統(tǒng)類型A1，軌道類型A11，觀測值類型A9，采樣率A4，載噪比A5，目標運動狀態(tài)A3，誤碼率A6，接收機類型A8，傳輸時延A12，信號頻點A7，信號捕獲概率A2。設置指標重要性大于0.05為高影響程度，其指標參數(shù)集即為精簡域，包括DOP值、導航系統(tǒng)類型、軌道類型、觀測值類型、采樣率、載噪比。

圖2 對定位精度影響的重要性排序

4 實驗分析

4.1 評價指標

設置有效規(guī)則為最小支持度0.05，最小置信度0.8，選擇定位精度作為定位精度，而關聯(lián)指標搜索范圍為全域和精簡域。本節(jié)主要選用有效性作為算法對比的指標，包括兩個方面含義：一是算法最終產(chǎn)生的關聯(lián)規(guī)則中只有用戶感興趣的事務項即目標事項，才對用戶有意義，這時的關聯(lián)規(guī)則才是有效的；二是挖掘出的規(guī)則置信度和支持度是有要求的，低置信度和支持度的規(guī)則不能稱為有效關聯(lián)規(guī)則。為檢測這兩個方面，定義3個有效性公式對算法進行評估，具體有效性公式如下：

E1=N1/N
E2=N2/N
E3=N2/N1

(1)

(2)

(3)

式中，N1是符合置信度和支持度要求的規(guī)則數(shù)量，N2是指符合置信度和支持度要求且與定位精確度相關的規(guī)則數(shù)量，N指的是整體挖掘規(guī)則的數(shù)量。

4.2 Apriori與FP-Growth全域關聯(lián)挖掘

基于經(jīng)典Apriori算法，實驗共提取了223378條規(guī)則(如圖3所示)，用時42.76s。其中，符合有效條件的關聯(lián)規(guī)則31495條(如圖4所示)，按照lift排序在表4中展示前5條內(nèi)容，均屬于4個或5個因素得出結(jié)論的關聯(lián)規(guī)則。

圖3 Apriori全域提取的關聯(lián)規(guī)則N

圖4 Apriori全域提取的關聯(lián)規(guī)則N1

表4 Apriori全域提取的關聯(lián)規(guī)則N1(前5條)

表中各變量具體取值：載噪比A5=低，誤碼率A6=高，信號頻點A7=低，DOP值A10=高，定位精確度B=低，觀測值類型A9=多普勒觀測值。其中，以定位精確度作為結(jié)論的規(guī)則共2429條(如圖5所示)，同樣地，按照lift排序在表5中展示前5條內(nèi)容。

圖5 Apriori全域提取的關聯(lián)規(guī)則N2

表5 Apriori全域提取的關聯(lián)規(guī)則N2(前5條)

表中各變量具體取值為：導航系統(tǒng)類型A1=GPS/Galileo/GLONASS/北斗某單一類型，目標運動狀態(tài)A3=動態(tài)，載噪比A5=低，誤碼率A6=高，觀測值類型A9=多普勒觀測值，定位精確度B=低。

在相同實驗背景下，使用FP-Growth算法共提取14263條規(guī)則(如圖6所示)，用時3.21s，符合有效條件的關聯(lián)規(guī)則為1250條(如圖7所示)，按照lift排序在表6中展示前5條內(nèi)容，發(fā)現(xiàn)這些規(guī)則都是以定位精度為結(jié)論。

圖6 FP-Growth全域提取的關聯(lián)規(guī)則

圖7 FP-Growth全域提取的關聯(lián)規(guī)則N1=N2

表6 FP-Growth全域提取的關聯(lián)規(guī)則N1=N2(前5條)

表中各變量具體取值：導航系統(tǒng)類型A1=GPS/Galileo/GLONASS/北斗某單一類型，目標運動狀態(tài)A3=動態(tài)，載噪比A5=低，誤碼率A6=高，觀測值類型A9=多普勒觀測值，傳輸時延A12=高，定位精確度B=低。

由式(1)-式(3)，Apriori挖掘有效性計算得：

E1=31495/223378=14.1%

(4)

E2=2429/223378=1.1%

(5)

E3=2429/31495=7.7%

(6)

同理，F(xiàn)P-Growth挖掘有效性計算得：

E1=1250/14263=8.8%

(7)

E2=1250/14263=8.8%

(8)

E3=1250/1250=100%

(9)

從上面的分析可知，設置同樣的數(shù)據(jù)集，同樣的條件參數(shù)，Apriori算法挖掘關聯(lián)規(guī)則有效性比FP-Growth算法挖掘關聯(lián)規(guī)則有效性指標E2和E3低，尤其是E3，只有評價指標E1略高。

4.3 Apriori與FP-Growth精簡域關聯(lián)挖掘

將搜索范圍改為上述6個影響程度高的指標集數(shù)據(jù)(精簡域)進行實驗。Apriori算法共提取2621條規(guī)則(見圖8)，用時1.75s，符合有效規(guī)則條件的關聯(lián)規(guī)則為310條(見圖9)，按照lift排序在表7中展示前5條內(nèi)容。表中所示的規(guī)則屬于2、3和4個因素結(jié)論的關聯(lián)規(guī)則。挑選與定位精度作為結(jié)論的有效規(guī)則共66條(見圖11)，按照lift排序在表8中展示前5條內(nèi)容。通過表8中的規(guī)則，同樣可以得到類似結(jié)論，當導航系統(tǒng)類型A1=GPS/Galileo/GLONASS/北斗組合類型，載噪比A5=高，DOP值A10=低，觀測值類型A9=載波相位，可以得出定位精度B=高的關聯(lián)規(guī)則結(jié)論。

圖8 Apriori精簡域提取的關聯(lián)規(guī)則N

圖9 Apriori精簡域提取的關聯(lián)規(guī)則N1

表7 Apriori精簡域提取的關聯(lián)規(guī)則N1(前5條)

表中各變量具體的水平值：導航系統(tǒng)類型A1=GPS/Galileo/GLONASS/北斗某單一類型，載噪比A5=高，DOP值A10=高，軌道類型A11=GEO/IGSO/MEO組合類型，定位精確度B=低，觀測值類型A9=多普勒觀測值。

在相同實驗背景下，使用FP-Growth算法共提取1077條規(guī)則(如圖10所示)，用時0.22s，符合有效規(guī)則條件的關聯(lián)規(guī)則為66條(如圖11所示)，按照lift排序在表8中展示前5條內(nèi)容。這些規(guī)則同樣都是以定位精度為結(jié)論。

圖10 FP-Growth精簡域提取的關聯(lián)規(guī)則N

圖11 Apriori與FP-Growth精簡域提取的關聯(lián)規(guī)則N2

表8 FP-Growth精簡域提取的規(guī)則(部分)

表中各變量具體的水平值：導航系統(tǒng)類型A1=GPS/Galileo/GLONASS/北斗某單一類型，載噪比A5=高，觀測值類型A9=載波相位，DOP值A10=低，軌道類型A11=GEO/IGSO/MEO組合類型，得出結(jié)論：定位精確度B=高。

Apriori挖掘有效性，由式(1)-式(3)計算得：

E1=310/2621=11.8%

(10)

E2=66/2621=2.5%

(11)

E3=66/310=21.3%

(12)

FP-Growth挖掘有效性，由式(1)-式(3)計算得：

E1=66/1077=6.1%

(13)

E2=66/1077=6.1%

(14)

E3=66/66=100%

(15)

綜合4.2、4.3部分的討論，并將指標對比，無論是在全指標情況下還是在與定位精度影響程度高的指標范圍內(nèi)，Apriori算法挖掘關聯(lián)規(guī)則有效性指標E2和E3比FP-Growth算法挖掘關聯(lián)規(guī)則的有效性指標都低一些，而有效性指標E1略高一些。這里需要格外關注有效性指標E3，F(xiàn)P-Growth算法得到的符合置信度和支持度的指標都是以定位精度為結(jié)論的規(guī)則，提取有效規(guī)則的效率大大提升。從FP-Growth算法與Apriori算法在不同指標范圍下生成關聯(lián)規(guī)則數(shù)量對比可以得出，F(xiàn)P-Growth算法相比Apriori算法生成的關聯(lián)規(guī)則要少。在全域范圍時，F(xiàn)P-Growth相比Apriori算法生成的符合置信度和支持度要求且以定位精度為結(jié)論的規(guī)則占整體規(guī)則的比例增加7.7%，符合置信度和支持度要求且以定位精度為結(jié)論的規(guī)則占有效規(guī)則的比例增加92.3%。在精簡域范圍時，F(xiàn)P-Growth相比Apriori算法生成的符合置信度和支持度要求且以定位精度為結(jié)論的規(guī)則占整體規(guī)則的比例增加3.6%，符合置信度和支持度要求且以定位精度為結(jié)論的規(guī)則占有效規(guī)則的比例增加78.7%。

5 結(jié) 論

指標的關聯(lián)性作為多維度指標分析的關鍵點，是進行數(shù)據(jù)多維度分析的切入點。將與定位精度影響度高的指標作為關聯(lián)指標的搜索范圍，便于得到更有實際指導意義的結(jié)果。在此搜索范圍應用關聯(lián)算法，可以針對定位精度不同的水平得到不同的強關聯(lián)指標。無論是在全指標情況下還是在對定位精度影響程度較高的指標范圍內(nèi)，Apriori算法比FP-Growth算法挖掘的符合置信度和支持度要求的關聯(lián)規(guī)則數(shù)量更多，但所需時間也更長，說明Apriori算法可以充分而全面地挖掘關聯(lián)規(guī)則，但時效性相對較弱。在關聯(lián)規(guī)則結(jié)論指標為定位精度后，F(xiàn)P-Growth算法挖掘的有效性和時效性都更好。當然，挖掘規(guī)則的正確性和實用性應在下一步予以充分考慮。為此，應該結(jié)合具體的導航應用場景和任務分析需求，選擇不同的挖掘方法，為解決考慮關聯(lián)的多指標評價問題提供參考思路。