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

高级数据挖掘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值。算法的步骤如下所示：图模式挖掘图模式挖掘是指从单个大图或一组图中识别高频出现的子结构的过程，这些子图结构可能代表了一些重要的模式或特征，对于理解图的结构和特性具有重要意义。图模式挖掘是基于图同构概念的。简单而言，图同构是指两个图在结构上完全相同。

图模式挖掘考虑到实际应用的需求和数据特性的差异，图模式挖掘产生了单图和多图两种模式挖掘。单图模式挖掘主要关注单个图内的模式发现，适用于对单个复杂网络或图结构的分析。而多图模式挖掘则涉及多个图之间的比较和关联分析，适用于处理多个图或图集合的场景，下面分别给出了两种问题的简要叙述：单图模式挖掘：考虑一张图G，如果一个子图g在G中至少出现τ次，那么它就是一个频繁子图。多图模式挖掘：假设有一个由许多相对较小规模图组成的图集合D，如果D中包含子图g的所有图的数量大于等于τ，那么它就是一个频繁子图。其中τ是用户定义的阈值。单图模式挖掘在单个图中挖掘频繁子图的典型方法是Kuramochi等人提出的HSIGRAM算法，算法的具体流程如图所示：单图模式挖掘

多图模式挖掘多图模式挖掘的典型算法为Kuramochi等人提出的FSG（FrequentSubGraphDiscovery）算法，其具体步骤如图中的算法所示：多图模式挖掘

Contents图数据挖掘01时间序列数据挖掘02大数据与分布式数据挖掘03时间序列数据时间序列的定义时间序列是一系列按时间顺序排列的观测值，这些值反映了变量随时间的变动情况，包括趋势、周期性和突变点。时间序列的重要性时间序列对于揭示现象的内在规律和特征至关重要，它支持对金融市场、气候变化等领域进行深入分析，从而做出准确预测和决策。时间序列的应用范围时间序列广泛应用于金融、医疗、能源等多个领域，通过数据挖掘提取隐藏信息和模式，支持股市波动识别、疾病诊断及消费趋势分析等。123时间序列特点数据规模庞大时间序列数据因其庞大的规模，存储与处理成为首要挑战。这种大规模数据需要高效的存储系统和强大的计算能力来支持数据分析与挖掘。快速生成速度时间序列数据以极快的速度生成，要求数据处理系统能够实时收集和分析数据，以确保信息的最新性和准确性，对系统的实时响应能力提出更高要求。时间序列的应用气象领域利用时间序列数据挖掘技术，可以预测未来的天气变化，为天气预报提供精确数据，同时为防灾减灾工作提供科学预警，减少自然灾害带来的损失。金融领域通过分析股票价格、汇率等时间序列数据，投资者和分析师能够更准确地把握市场动态，为制定投资策略提供科学依据。交通领域交通流量数据分析能够准确反映不同时间段的交通状况，帮助城市交通规划者理解交通拥堵的原因，从而制定有效的缓解措施。相似性度量算法：欧氏距离欧氏距离的定义欧氏距离是衡量两点在空间中绝对距离的度量方法，常用于时间序列分析中，通过计算序列间对应点的数值差异来评估相似性。欧氏距离的应用限制尽管欧氏距离在比较等长时间序列方面简单直观，但它要求被比较的时间序列必须长度相等，这一条件在实际应用中可能难以满足，限制了其应用范围。欧氏距离的局限性欧氏距离仅关注时间序列在特定时间点的数值差异，忽略了序列的整体形状和趋势信息，可能导致对形态和趋势相似的序列给出不准确的相似度评估。123相似性度量算法：动态时间规整动态时间规整的定义动态时间规整是一种算法，用于测量不同长度的时间序列之间的相似度。通过非线性映射动态时间，它可以对齐时间轴上的相似部分，从而处理不等长时间序列的问题。动态时间规整的应用动态时间规整不仅适用于等长的时间序列，还能提高相似性度量的准确性。它考虑时间序列的整体形状和趋势，广泛应用于语音识别、数据挖掘等领域。动态时间规整的局限性动态时间规整的计算过程包括构建距离矩阵并寻找最优弯曲路径。这条路径代表序列间的匹配关系，使得路径上所有匹配点对的距离和最小，从而实现精确的时间序列相似度测量。123时间序列异常检测技术风险预警与问题识别异常检测在时间序列分析中扮演着关键角色，通过识别出与常规模式显著不同的子序列，它能够及时发出风险预警并识别潜在问题，从而采取预防措施。跨领域应用价值时间序列异常检测技术不仅限于单一领域，其在网络安全、金融、工业制造和医疗健康等多个领域均有广泛应用，通过监控和分析数据，为各领域的决策提供科学依据。提升效率与安全性通过及时发现和处理设备故障或生产流程中的异常，时间序列异常检测不仅能够保障生产安全，还能显著提高生产效率，同时在医疗健康领域，对疾病进展的监测也为治疗提供了重要支持。123时间序列异常检测技术为了有效地检测这些异常的子序列，可以采用动态时间规整距离和K近邻法算法。在时序异常检测场景中，K近邻法的基本思想是如果一个序列在特征空间中距离其最近的K个邻居都很远，那么它被认为是异常的。算法基本步骤如下：时间序列分类与聚类时间序列分类时间序列分类是将时间序列数据划分为不同类别的过程。时间序列分类的目标是根据这些观测值的模式或特征，将时间序列分配到预定义的类别中。时间序列分类在金融、医疗、能源等多个领域都有广泛应用。时间序列聚类时间序列聚类旨在将具有相似特征的时间序列数据划分到不同的簇中。与分类方法不同，时间序列聚类无需依赖预定义的类别标签，它完全基于数据本身的相似性和差异性进行自动分组，因此更具灵活性和探索性。12时间序列分类与聚类在时间序列分类中，可以采用动态时间规整算法进行距离计算决定度量后，应用K近邻算法进行分类。算法基本过程如下：时间序列分类与聚类在时间序列聚类中，可以采用动态时间规整算法进行距离度量，应用凝聚的层次聚类算法进行聚类。算法基本过程如下：Contents图数据挖掘01时间序列数据挖掘02大数据与分布式数据挖掘03大数据与分布式数据挖掘随着信息科技的飞速发展，日常生活已经被大量的数字信息所包围。这些信息来自于各个方面，形成了庞大的数据集，即我们所说的大数据。随着大数据时代的到来，其存储和计算的问题也逐渐凸显出来。传统的数据存储系统在处理大规模数据时，往往会遇到性能瓶颈，无法满足实时、高效的数据处理需求。传统的计算模式也难以应对大数据的复杂性，需要更加灵活、可扩展的计算系统来支持。分布式文件系统分布式文件系统（DistributedFileSystem）是通过网络连接多台主机以实现文件分布式存储的新型文件系统，用户可以更简便地访问分布在网络上的共享文件。分布式文件系统将多个存储节点聚集在一起，并将数据逻辑地分布到具有各自计算能力和存储能力的多个节点上，为大数据的存储和访问提供了一种高效、灵活且可扩展的解决方案。下面将从三个方面进行介绍：计算机集群结构分布式文件系统结构Hadoop分布式文件系统计算机集群普通的文件系统主要依赖于单个计算机节点，这个节点内部包含了处理器、内存、高速缓存以及本地磁盘等核心组件，这些组件协同工作完成文件的存储和处理任务。分布式文件系统将文件分散存储到多个计算机节点上。这些数量庞大的节点彼此间通过网络相连，共同构成了计算机集群。计算机集群计算机集群结构集群中的计算机节点被有序地存放在机架（Rack）上，机架作为物理存储单元，其能够容纳一定数量的节点。机架内的节点之间通过网络连接，网络通常采用高速且稳定的千兆以太网，确保节点间数据的快速交换和同步。计算机集群优势数据被分散存储在多个节点上，实现了数据的冗余备份，提高了数据的可靠性和安全性。集群中的节点可以并行处理数据，大大提高了数据处理的速度和效率。集群的扩展变得轻而易举，只需增加新的节点或机架，就能轻松提升整个集群的计算和存储能力。分布式文件系统结构这种系统便是分布式文件系统，其专为集群环境而设计，其整体架构通常为主从结构，这一结构由大量的计算机节点构成，这些节点根据功能的不同，主要分为以下几类：主节点（MasterNode）：主节点不仅是文件和目录管理的核心，负责文件的创建、删除和重命名等操作，还负责维护着数据节点和文件块之间的映射关系。主节点的稳定运行和高效处理，对于整个分布式文件系统的性能和可靠性至关重要。从节点（SlaveNode）：从节点则主要承担着数据的存储和读取任务。从节点会根据主节点的命令，执行数据块的创建、删除和复制等操作。从节点之间的协同工作，使得数据的存储和访问变得高效而可靠。客户端（Client）：客户端通过访问主节点获取文件块的存储位置信息，然后直接与从节点进行数据的读取或写入。这种设计使得客户端能够高效地访问和使用分布式文件系统中的数据，满足各种大数据应用的需求。Hadoop分布式文件系统Hadoop分布式文件系统（HDFS）是一个高度可扩展的分布式文件系统。HDFS采用主从式的分布式架构：主节点称为名称节点（NameNode），负责存储文件的元数据，包括目录、文件、权限、文件分块、副本存储等信息，并对HDFS的全局情况进行管理。从节点称为数据节点（DataNode），负责自身存储的数据块，并根据名称节点指令，对存储的文件数据块进行读写，并定期向名称节点上报节点以及数据的健康情况。Hadoop分布式文件系统HDFS进行写数据过程：在数据写入时，客户端首先与名称节点进行通信，发送写入请求。名称节点选择合适的数据节点来存储新的数据块，并返回给客户端。客户端将待写入的数据切分成数据块，并按照顺序发送给选定的数据节点。数据节点接收到写入请求后，将数据块存储在本地磁盘上，同时将数据块复制到其他数据节点以提供冗余备份，确保数据的容错性。当所有副本全部写入完成后，客户端会收到名称节点的确认响应，代表写入过程的完成。Hadoop分布式文件系统HDFS进行读数据过程：在数据读取时，客户端向名称节点发送读取请求，包含要读取的文件路径和偏移量。名称节点验证请求和文件信息后，返回包含数据块位置信息的元数据给客户端。客户端根据就近原则选择距离自己最近的一个数据节点作为主读取节点，然后直接与该数据节点建立数据传输通道，并行读取所需的数据块。读取完成后，客户端会对接收到的数据块进行组合和处理，以还原成完整的文件。MapReduce大数据处理框架MapReduce是一种用于并行计算的编程模型和软件框架，主要用于分布式计算环境下的数据处理和计算，主要分为以下几个步骤：Map任务：将数据块转换为一系列键值对。按键分组：收集每个Map任务中的键值对并按键排序。键被分配给所有的Reduce任务，所以所有具有相同键的键值对都在相同的Reduce任务中结束。Reduce任务：一次处理一个键，并以某种方式组合与该键相关的所有值。Hadoop分布式文件系统Map阶段是MapReduce工作流程的第一个阶段。它的主要任务是将输入数据（如文件）划分为一系列的键值对，然后对每个键值对应用用户定义的Map函数：Map任务的输入由元素（elements）组成，元素可以是任何类型，比如元组或文档。Map函数将输入元素作为参数，并产生零个或多个键值对。键和值的类型都是任意的。此外，键并非通常意义上的“键”，它们不必是唯一的。相反，Map任务甚至可以从同一个元素中产生几个具有相同键的键值对。Map阶段的输出被临时存储在本地文件系统中，等待后续的按键分组和Reduce任务处理。Map任务通常是并行的，多个Map任务可以同时处理输入数据的不同部分。Hadoop分布式文件系统

Hadoop分布式文件系统Reduce任务是MapReduce工作流程的最后一个阶段。它的主要任务是对按键分组后的数据进行处理，并生成最终的输出结果：Reduce函数的输入参数是由特定键及其对应的值列表所组成的配对数据。这些值列表是在Map阶段通过按键分组后，与相应键相关联的所有值的集合。随后，Reduce函数根据用户定义的逻辑进行归约操作。归约操作的具体形式取决于数据的性质和处理需求，可以是求和、计数、求平均值等。并生成一个或多个键值对的序列作为输出。最终，所有Reduce任务的输出会被合并成一个文件，这些结果通常被写入到HDFS中的文件或其他存储系统中。MapReduce大数据处理框架以Hadoop分布式文件系统为例介绍MapReduce框架在分布式文件系统上的执行过程：环境初始化：用户编写MapReduce程序，提交到名称节点中的JobTracker进行处理。JobTracker将用户提交的作业分解为数据处理任务，分发给集群中的数据节点上的TaskTracker运行。Map任务：JobTracker启动数据节点上的TaskTracker执行Map任务。结果以<key,value>的形式存放在各个节点的本地磁盘中。Reduce任务：Map任务结束后，JobTracker会在各个节点上启动TaskTracker执行Reduce任务，把具有相同key的<key,value>对，收集到一起进行汇总计算，并最终得到结果，然后将结果输出到HDFS系统中。Spark大数据处理框架Spark是一个基于内存计算的大数据并行处理框架，是当前主流的大数据处理框架之一，可用于构建大型的、低延迟的数据分析应用程序。Spark将数据抽象为一种分布式共享内存模型，从而实现了基于内存进行计算，减少了磁盘的读写次数，使得其速度可以达到MapReduce的数倍甚至数十倍。除此以外，Spark引入了执行图结构来表示数据的计算过程，使其不仅局限于Map和Reduce两种操作，能够更灵活地描述各种复杂问题，并对执行过程进行优化。Spark模型的应用场景非常广泛，包括批处理、实时流处理以及机器学习等。Spark大数据处理框架Spark通过将数据抽象为弹性分布式数据集（ResilientDistrustedDataset，RDD）实现基于内存的分布式计算。RDD提供了许多操作，可以分为两种类型：转换操作（Transformation）：由于RDD是不可更新的，因此对一个RDD执行转换操作时并不会立即触发计算，而是返回一个新的RDD，这种延迟计算的机制使得用户可以在不实际执行计算的情况下构建出计算图，提高了数据处理的灵活性。典型的转换操作包括map、filter、groupBy、join等。动作操作（Action）：而当动作操作施加于RDD时，系统将对RDD进行计算，并返回值而非RDD作为最终的结果。典型的动作包括count、collect、reduce、save等。Spark大数据处理框架Spark会将用户提交的应用程序划分为若干个作业（Job），一个Spark作业可以看作对RDD执行一系列计算操作，最后得到输出的过程。Spark采用一个有向无环图（DirectedAcyclicGraph，DAG）来对作业进行描述，它在Spark作业执行过程中起到了至关重要的作用。Spark会根据RDD、转换操作以及动作操作构造一个DAG，来表达一系列复杂的计算过程。Spark大数据处理框架Spark会将RDD分成多个分区，RDD的每个分区对应一个任务（Task），其是Spark应用程序中执行的最小单位。在DAG里，当对父RDD执行转换操作时会生成一个子RDD，此时两个父子RDD之间就建立了依赖关系。父子RDD的各个分区之间有两种依赖关系：窄依赖：指每个父RDD的分区，最多被一个子RDD的分区使用到，如进行map、filter、join