面向单幅不确定大图的频繁模式挖掘技术研究

发布时间：2020-05-17 15:29

【摘要】：在军事信息系统中,军事情报分析与处理分系统占据重要地位。随着各类情报获取手段的演进,军事情报数据呈现出异构性和非结构化等特点,使得军事情报分析与处理面临极大的技术挑战。海量文本情报分析是情报分析与处理中最重要和最基础的组成部分。当前,一种从整体上把握文本情报的有效手段是构建以单个文本为节点、文本之间相互关系为联系的文档网络图,即单幅大图(网络)数据,并在此基础上开展一系列分析研判。本文以文本情报分析为应用背景研究单幅大图(网络)上的数据挖掘问题。由于噪声、测量误差、保密性、不完整性等原因,不确定性在现实世界的数据中广泛存在。作为一种具有广泛建模能力的数据模型,图数据中也存在着不确定性。除了前述的文档网络图,生物信息学、社会网络等领域中亦大量存在着不确定图。因此,针对不确定图的研究成为国内外的热点。本文使用不确定图建模文本军事情报,并在此基础上挖掘频繁模式;目前在单幅不确定大图上频繁子图挖掘的问题尚未见已公开的研究。首先,对单幅不确定大图上子图模式的支持度进行了定义,据此提出了基于枚举-评估的支持度评估方法。枚举策略采用与确定图挖掘时相同的方式,本文主要关注支持度评估过程。其次,通过证明在单幅不确定图上期望支持度的计算是#-P难的,设计了一种具有精度保证的近似算法以满足实际应用需求。然后,为进一步增强算法效率,提出了两种优化策略,一是考虑对样本图计算结果的重用,二是引入检查点机制和基于结构的上界,提前对不频繁的分枝进行剪枝。上述两种优化策略的应用提升了挖掘性能。最后,在实际数据集上进行的实验验证了该挖掘方法及优化策略的实际可用性和有效性。为了进一步评价所提技术的实际效用和意义,在真实文本情报数据上开展了应用研究。对于采集的公开文本情报数据,以文档为节点、文档间相似度为边建立文档关联。使用LDA模型为节点附加标签,使用基于知识库的算法衡量节点间相似度;当相似度大于给定阈值时,则连接一条边,并以相似度值作为边上的概率。最终建立文档网络图,并用所提技术对其进行挖掘。实验结果表明,发现的模式具有可解释性,所提挖掘技术具有较好的实际应用前景。
【图文】：

优化技术,运行时间

国防科学技术大学研究生院硕士学位论文5.3 评价优化技术本节实验评价在近似框架下，所提优化技术的效果。特别地，，我们比较了三个算法，为了表达清晰，分别表示为基本，+重用，+剪枝。基本：基本的基于蒙特卡洛仿真，挖掘单个不确定图的近似算法，即在 3.3 节中提出的算法 1；+重用：在基本上应用计算重用技术，即 4.1 节所提，重用三种开销；+剪枝：进一步引入在 4.2 节提出的，基于检查点机制的剪枝技术，在+重用的基础上，+剪枝包含所有提出的优化策略。

优化技术,样本量

(a)CIT 数据集 (b)COL 数据集图 5-3 优化技术样本量对比进一步鉴别剪枝技术，我们研究总的样本量。图 5-3(a)和(b)描绘了在 CIT 和COL 上需要的总的样本数量。重点需要观察的是剪枝策略使得提前结束成为可能，使得需要更少的样本。既然+重用并不考虑剪枝，那么其需要的样本数量和基本是一样的，因此我们忽略对其进行比较。两个图都反映了剪枝规则很有效，减少了约1 1~4 3的样本量。最终使得运行速度加快。总的来讲，+重用相比基本体现了优越性，而+剪枝比+重用更好。因此+剪枝作为最终的算法 fanta。接下来，我们评价参数值变化对于 fanta 不确定性，及可扩展性的影响。5.4 评价参数的影响除了，用户定义的参数与也会影响算法性能。在本组实验中，我们衡量与的变化对算法效率的影响程度，其中 fanta 与基本进行了比较与分析。我们
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：E11;TP391.1

【相似文献】