民航旅客同行子圖抽取旨在從旅客-航班異構(gòu)網(wǎng)絡(luò)中抽取具有最緊密同行關(guān)系的旅客,并將這些旅客劃分到同一子圖中,使得子圖內(nèi)部連接緊湊,子圖間連接稀疏。民航旅客子圖抽取一方面可幫助航空公司實施旅客個性化服務(wù),提高旅客服務(wù)質(zhì)量,在行業(yè)競爭時獲得旅客數(shù)量的優(yōu)勢,另外一方面可幫助機(jī)場對危險旅客及其同行旅客進(jìn)行監(jiān)控,保證民航安全運(yùn)行。由于旅客總體出行記錄數(shù)量龐大但個體出行記錄稀疏,旅客-航班異構(gòu)網(wǎng)絡(luò)呈現(xiàn)高度稀疏,而現(xiàn)有子圖抽取方法難以應(yīng)用于稀疏的旅客-航班異構(gòu)網(wǎng)絡(luò)。針對上述問題,該文開展基于旅客-航班異構(gòu)網(wǎng)絡(luò)的子圖抽取研究,主要從以下兩個方面開展研究,并在旅客訂票記錄中開展驗證性實驗。該文主要工作如下:針對旅客-航班異構(gòu)網(wǎng)絡(luò)的高度稀疏性,提出了基于旅客-航班異構(gòu)網(wǎng)絡(luò)隨機(jī)游走的旅客同行子圖抽取方法。該方法首先根據(jù)旅客訂票記錄構(gòu)建旅客-航班異構(gòu)網(wǎng)絡(luò),然后通過隨機(jī)游走以更新網(wǎng)絡(luò)中節(jié)點(diǎn)間關(guān)系,最后基于完全子圖的標(biāo)簽傳播方法進(jìn)行旅客同行子圖的抽取。在民航旅客訂票記錄數(shù)據(jù)集上的實驗結(jié)果表明,該方法相較于擴(kuò)展的標(biāo)簽傳播方法、基于標(biāo)簽傳播的重疊子圖發(fā)現(xiàn)算法、派系過濾等基準(zhǔn)算法,具有更高的模塊度、標(biāo)準(zhǔn)化互信息和子圖抽取... 

【文章來源】：中國民航大學(xué)天津市

【文章頁數(shù)】：58 頁

【學(xué)位級別】：碩士

【部分圖文】：

014-2018年民航旅客總周轉(zhuǎn)量在出行的時候，人們往往會和自己熟悉的人一起訂票出行，例如家人和朋友

中國民航大學(xué)碩士學(xué)位論文23標(biāo)簽傳播算法如表3.3所示：表3.3以標(biāo)簽傳播方法進(jìn)行子圖抽取輸入：初始化后的旅客同行網(wǎng)絡(luò)M，迭代次數(shù)T,后處理閾值r輸出：節(jié)點(diǎn)標(biāo)簽列表ilist(1)同步更新，根據(jù)鄰居節(jié)點(diǎn)標(biāo)簽信息對目標(biāo)節(jié)點(diǎn)更新；(2)如果目標(biāo)節(jié)點(diǎn)鄰居節(jié)點(diǎn)出現(xiàn)最多的標(biāo)簽唯一，修改目標(biāo)節(jié)點(diǎn)的標(biāo)簽；否則根據(jù)旅客同行網(wǎng)絡(luò)中旅客-旅客的權(quán)值，選擇權(quán)值最高的旅客節(jié)點(diǎn)的標(biāo)簽作為目標(biāo)節(jié)點(diǎn)的標(biāo)簽；(3)重復(fù)上述步驟(1)-(2),直到達(dá)到迭代次數(shù)或標(biāo)簽穩(wěn)定；(4)記錄每次目標(biāo)節(jié)點(diǎn)的標(biāo)簽，在迭代結(jié)束后，計算互異標(biāo)簽出現(xiàn)的概率；(5)根據(jù)節(jié)點(diǎn)互異標(biāo)簽的概率和后處理閾值，選擇最終作為目標(biāo)節(jié)點(diǎn)的標(biāo)簽，并刪除其余標(biāo)簽。標(biāo)簽傳播進(jìn)行子圖抽取算法示例如圖3-4所示。圖3-4標(biāo)簽傳播進(jìn)行子圖抽取算法示例

中國民航大學(xué)碩士學(xué)位論文28進(jìn)行性能比較具有較強(qiáng)的不確定性。為了減少隨機(jī)影響，算法在相同參數(shù)下運(yùn)行多次，取多次性能的平均值。與基準(zhǔn)算法對比的實驗結(jié)果如表3.7所示。本章在模塊度標(biāo)準(zhǔn)化互信息和子圖抽取準(zhǔn)確度方面均有提升。表3.7子圖抽取性能比較算法迭代次數(shù)T/次模塊度標(biāo)準(zhǔn)化互信息子圖抽取準(zhǔn)確度SLPA200.4390.4620.517COPRA200.4310.4680.472CPM200.4090.4720.583本章算法200.4420.4910.6253.6.7實驗分析由表3.7可以看出，本章算法在模塊度、標(biāo)準(zhǔn)化互信息子圖抽取準(zhǔn)確度三個指標(biāo)上，相比于其他算法具有更好效果，說明本文算法的有效性。隨機(jī)游走次數(shù)n控制旅客節(jié)點(diǎn)之間的相似度，在n值增大的情況下，會導(dǎo)致節(jié)點(diǎn)間的相似度增大，旅客節(jié)點(diǎn)之間具有關(guān)聯(lián)的邊也會增多，因此，本實驗需要探究隨機(jī)游走次數(shù)n的值如何反應(yīng)節(jié)點(diǎn)間的相似度。在隨機(jī)游走次數(shù)n=1時，由于旅客節(jié)點(diǎn)間的聯(lián)系較為稀疏，因此NMI、旅客同行準(zhǔn)確度的值較低，隨著隨機(jī)游走次數(shù)的增多，旅客節(jié)點(diǎn)間同行關(guān)系也被挖掘出來，因此在n增大時，子圖抽取算法的NMI增加。而在n≥4時，出現(xiàn)了過擬合現(xiàn)象，導(dǎo)致子圖抽取算法準(zhǔn)確度下降。如圖3-5所示，其中橫坐標(biāo)為隨機(jī)游走迭代次數(shù)，縱坐標(biāo)為子圖抽取的標(biāo)準(zhǔn)化互信息（NMI）。圖3-6為在不同隨機(jī)游走次數(shù)下旅客同行子圖抽取準(zhǔn)確度。圖3-5隨機(jī)游走次數(shù)敏感性分析


本文編號：3561753