關(guān)聯(lián)規(guī)則算法在衛(wèi)星定位精度考核中的比較分析

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

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

1 引 言

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

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

2 相關(guān)理論

2.1 Xgboost算法

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

2.2 Apriori算法

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

表1 Apriori算法流程

2.3 FP-Growth算法

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

表2 FP-Growth算法流程

3 分析流程與指標(biāo)篩選

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

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

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

3.2 相關(guān)指標(biāo)篩選

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

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

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

圖2 對(duì)定位精度影響的重要性排序

4 實(shí)驗(yàn)分析

4.1 評(píng)價(jià)指標(biāo)

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

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

(1)

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E1=31495/223378=14.1%

(4)

E2=2429/223378=1.1%

(5)

E3=2429/31495=7.7%

(6)

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

E1=1250/14263=8.8%

(7)

E2=1250/14263=8.8%

(8)

E3=1250/1250=100%

(9)

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

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

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

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

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

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

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

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

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

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

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

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

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

E1=310/2621=11.8%

(10)

E2=66/2621=2.5%

(11)

E3=66/310=21.3%

(12)

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

E1=66/1077=6.1%

(13)

E2=66/1077=6.1%

(14)

E3=66/66=100%

(15)

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

5 結(jié) 論

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