数据挖掘 课件 第七章 高级数据挖掘.pptx

高级数据挖掘

Contents图数据挖掘01时间序列数据挖掘02大数据与分布式数据挖掘03

图数据图是由顶点和边构成的抽象数据结构，图数据通过图结构表示实体及其相互之间的复杂关联关系，广泛存在于各类应用中：化学信息学：原子可视为图中的节点，节点可附带原子的种类、电荷等关键信息；边则代表了原子之间的化学键，用于表示原子之间的连接方式和相互作用，是理解分子结构和性质的基础。生物信息学：图数据被广泛用于复杂生物结构的表示与建模。例如，单个氨基酸或基因可被视作图的一个节点，而大量这样的节点通过边相互交织，构成了庞大的生物信息传递网络。计算机网络：图数据被用来准确刻画网络拓扑结构。通过将网络中的设备映射为图中的节点，设备之间的连接关系映射为边，从而构建出一个能够反映计算机网络实际连接情况的网络图。

图数据挖掘问题由于图数据的结构复杂,蕴含丰富的信息，因此如何挖掘其潜在规律，得到有价值的信息变得至关重要。图数据挖掘作为发现图数据中的模式和关联，分析提取图数据有价值信息的重要手段，已成数据挖掘领域的研究热点。下面将介绍图数据挖掘领域中两类重要问题：凝聚子图挖掘图模式挖掘

凝聚子图挖掘凝聚子图挖掘旨在发现具有高度内部连接性和紧密结构的子图，这些子图通常代表着图数据中重要的社区结构、功能模块或者其他潜在的有意义的子结构。为了适应不同的场景，研究者提出了各种凝聚子图挖掘模型，本节主要介绍三种主流的凝聚子图挖掘模型：团模型K-Core模型K-Truss模型

团模型团（Clique）被定义为一个子图，其中每两个顶点之间都有一条边，即在子图中的每个顶点都与其他任何顶点相邻。团可以被视为网络中最紧密的子结构。下面给出了团和极大团的定义：【团】给定图G=(V,E)，其中V表示图的点集，E表示边集。团是图G的一个导出子图H，即任意两个顶点之间都有一条边相连。【极大团】给定图G=(V,E)，团H不包含于图G的任何其他团，即不是任何其他团的真子集，则称团H是一个极大团。

团模型团（Clique）被定义为一个子图，其中每两个顶点之间都有一条边，即在子图中的每个顶点都与其他任何顶点相邻。团可以被视为网络中最紧密的子结构。下面给出了团和极大团的定义：【团】给定图G=(V,E)，其中V表示图的点集，E表示边集。团是图G的一个导出子图H，即任意两个顶点之间都有一条边相连。【极大团】给定图G=(V,E)，团H不包含于图G的任何其他团，即不是任何其他团的真子集，则称团H是一个极大团。

团模型找到一个图中所有的极大团是图算法领域的一个基本问题，针对这一问题的最经典算法是由CoenraadBron等人提出的Bron-Kerbosch算法，通常简称为BK算法。BK算法是一种基于递归和回溯的算法，其通过构造三个互不相交的集合R，P，X来记录极大团的有哪些信誉好的足球投注网站过程，每个集合的作用如下：R集合：记录当前计算的极大团中已经包含的点。P集合：记录与R集合中所有点存在边的点。团要求每个点之间都有边相连，因此只有这些点才满足构成团的条件。X集合：记录已经包含于某个极大团中的点，用于避免计算重复的极大团。

团模型BK算法的具体步骤如图所示：

K-Core模型考虑到团模型对子图的限制过于严格，Seidman等人提出了k-Core模型，其要求子图中的每个顶点都至少有k个邻居。K-Core可以用来识别图中连接最紧密的部分，并能够反应一个网络的整体结构和行为，下面给出了k-Core的具体定义：【k-Core模型】给定图G=(V,E)，其中V表示图的点集，E表示边集。k-Core是图G的一个导出子图H，子图H中任意顶点的邻居数量都大于等于k。

K-Core模型在对k-Core进行计算时，采用度数修剪算法，其核心任务在于识别并提取出图中那些满足给定核心度要求的子图结构。算法的步骤如下所示：

K-Truss模型Cohen等人提出了k-Truss模型，它是一个最大子图，其中每条边至少存在于子图中的k-2个三角形中。由于三角形表示紧密的关系，并且是复杂网络的基本构建块，k-Truss能够帮助我们识别出网络中连接最紧密、最具凝聚力的子图。下面分别给出了支持度以及k-Truss的概念。?

K-Truss模型Cohen等人同时提出了一种计算k-Truss的算法，该算法通过迭代方式，不断移除剩余图中支持度最低的边，进而计算出每条边的Truss值。算法的步骤如下所示：

图模式挖掘图模式挖掘是指从单个大图或一组图中识别高频出现的子结构的过程，这些子图结构可能代表了一些重要的模式或特征，对于理解图的结构和特性具有重要意义。图模式挖掘是基于图同构概念的。简单而言，图同构是指两个图在结构上完全相同。?

图模式挖掘考虑到实际应用的需求和数据特性的差异，图模式挖掘产生了单图和多图两种模式挖掘。单图模式挖掘主要关注单个图内的模式发现，适