面向單幅不確定大圖的頻繁模式挖掘技術(shù)研究.pdf

1、在軍事信息系統(tǒng)中，軍事情報分析與處理分系統(tǒng)占據(jù)重要地位。隨著各類情報獲取手段的演進(jìn)，軍事情報數(shù)據(jù)呈現(xiàn)出異構(gòu)性和非結(jié)構(gòu)化等特點，使得軍事情報分析與處理面臨極大的技術(shù)挑戰(zhàn)。海量文本情報分析是情報分析與處理中最重要和最基礎(chǔ)的組成部分。當(dāng)前，一種從整體上把握文本情報的有效手段是構(gòu)建以單個文本為節(jié)點、文本之間相互關(guān)系為聯(lián)系的文檔網(wǎng)絡(luò)圖，即單幅大圖（網(wǎng)絡(luò)）數(shù)據(jù)，并在此基礎(chǔ)上開展一系列分析研判。本文以文本情報分析為應(yīng)用背景研究單幅大圖（網(wǎng)絡(luò)）上的數(shù)據(jù)

2、挖掘問題。
　　由于噪聲、測量誤差、保密性、不完整性等原因，不確定性在現(xiàn)實世界的數(shù)據(jù)中廣泛存在。作為一種具有廣泛建模能力的數(shù)據(jù)模型，圖數(shù)據(jù)中也存在著不確定性。除了前述的文檔網(wǎng)絡(luò)圖，生物信息學(xué)、社會網(wǎng)絡(luò)等領(lǐng)域中亦大量存在著不確定圖。因此，針對不確定圖的研究成為國內(nèi)外的熱點。本文使用不確定圖建模文本軍事情報，并在此基礎(chǔ)上挖掘頻繁模式；目前在單幅不確定大圖上頻繁子圖挖掘的問題尚未見已公開的研究。
　　首先，對單幅不確定大圖上子圖模

3、式的支持度進(jìn)行了定義，據(jù)此提出了基于枚舉-評估的支持度評估方法。枚舉策略采用與確定圖挖掘時相同的方式，本文主要關(guān)注支持度評估過程。其次，通過證明在單幅不確定圖上期望支持度的計算是＃-P難的，設(shè)計了一種具有精度保證的近似算法以滿足實際應(yīng)用需求。然后，為進(jìn)一步增強算法效率，提出了兩種優(yōu)化策略，一是考慮對樣本圖計算結(jié)果的重用，二是引入檢查點機制和基于結(jié)構(gòu)的上界，提前對不頻繁的分枝進(jìn)行剪枝。上述兩種優(yōu)化策略的應(yīng)用提升了挖掘性能。最后，在實際數(shù)據(jù)

4、集上進(jìn)行的實驗驗證了該挖掘方法及優(yōu)化策略的實際可用性和有效性。
　　為了進(jìn)一步評價所提技術(shù)的實際效用和意義，在真實文本情報數(shù)據(jù)上開展了應(yīng)用研究。對于采集的公開文本情報數(shù)據(jù)，以文檔為節(jié)點、文檔間相似度為邊建立文檔關(guān)聯(lián)。使用LDA模型為節(jié)點附加標(biāo)簽，使用基于知識庫的算法衡量節(jié)點間相似度；當(dāng)相似度大于給定閾值時，則連接一條邊，并以相似度值作為邊上的概率。最終建立文檔網(wǎng)絡(luò)圖，并用所提技術(shù)對其進(jìn)行挖掘。實驗結(jié)果表明，發(fā)現(xiàn)的模式具有可解釋性，