论文部分内容阅读
随着数据挖掘研究的深入，越来越多的问题呈现在我们面前，也提出了更高的要求。当前，复杂类型数据的挖掘需求上升，专家学者开始关注这方面的新应用和理论研究，并试图利用结构化数据挖掘方面的经验和方法论来帮助解决新问题。而连通子图挖掘问题就是本文所致力研究的问题。
本文主要研究了N连通子图挖掘问题和多信息连通子图挖掘问题。N连通子图发现问题是在一个很大的图中寻找一个较小的子图来表现几个给定节点在图中的关系的问题。多信息连通子图挖掘问题是在一个边有多种类型的图中寻找连通几个特定结点的，能够满足问题约束的连通子图的问题。本文的主要工作和特色如下：
1．本文提出了一个新的解决N-连通子图挖掘问题的方法。首先分析了问题并定义了一个评价函数来评价一个子图表现N个给定节点之间关系的好坏。同时设计了一个特殊的UTM编码来表示一个确定结点数的图的拓扑结构。使用UTM编码能够避免在进化过程中多余的编码步骤，能够减小算法的时间和空间消耗。在UTM编码和评价函数的基础上，设计了一个演化算法来对图的拓扑结构进行优化。实验结果显示该算法能够有效地在不同类型的网络上发现连通子图。
2．在N连通子图挖掘问题之后，本文针对多信息连通子图发现问题的特点，提出了一个通用的进化算法。设计了一种表示多信息子图拓扑结构的特殊编码——多信息子图编码MSC。使用MSC编码能够很好的表示多信息连通子图，这个编码能够在进化过程中能够减少时间和空间的消耗。同时在真实数据上的实验结果显示该算法是有效的。
3．在前面两个算法的基础上，将连通子图挖掘问题与对象层次的搜索问题相结合，能够解决对象层次的查询项扩展问题。对于算法的两个部分使用了不同的快速优化策略。对于候选子图算法，计算量最大的部分可以提前预处理并且存储下来，在算法的过程中只需要执行简单的计算，无须多次遍历原始图。对于进化算法，使用不同的算子和参数设置能够使算法收敛更快，也能更好的避免算法陷入局部最优解。