模式识别与数据挖掘 课件 第13章-结构模式识别

第十三章

复杂数据挖掘主讲人：某某某PatternRecognitionandDataMining模式识别与数据挖掘目录Contents引言Introduction时序数据挖掘Time

Series

Data

Mining流式数据挖掘Streaming

Data

Mining图数据挖掘Graph

Data

Mining01020304小结与讨论SummaryandDiscussion05复杂数据定义：复杂数据是指那些无法用传统的、静态的二维关系表（即简单的行列表格）有效表示和处理的数据集合。特性：具有异构性、时变性、非线性结构或无限流式的特征，打破了传统数据挖掘中“数据点是独立同分布（I.I.D.）”的基本假设。数据挖掘新挑战传统数据挖掘主要针对多媒体和结构化数据，然而现实世界中充斥着更加复杂的数据类型：时序数据(TimeSeries)：股市波动、心电信号、气候变化。流式数据(StreamData)：实时交通监控、网络日志、高频交易。图数据(GraphData)：社交网络、交通路网、生物分子结构。核心挑战：数据的异构性、时变性、无限性以及复杂的关联结构。引言：复杂数据的世界时序数据挖掘02Time

Series

Data

Mining时间序列数据的来源与规模日常生活中的时序数据时序数据无处不在：股价波动、气候变化、心电信号、用户行为等，承载丰富动态信息。规模爆炸式增长随互联网、物联网、工业数字化发展，来自数字媒介、传感器、监控设备的海量数据每日产生，累计达到PB级别，推动“有效处理与深入挖掘”成为关键问题时序分析的关键特性一维数据分布特性时间序列分析最显著特点在于其“一维的数据分布特性”，任何任务都必须考虑这一点，不能当作无序数据处理。现实数据的典型困难由于数据来源多样，常遇到长度不一、采样频率不同、含噪声的时间序列；因此分析时不仅要看数值，更要处理时间结构与尺度差异。形式转换/统一为了有效地借鉴其他领域的数据挖掘方法,如何标准化并转换时序数据的形式成为一个重要议题同一个信号进行相同采样点数N，不同采样频率采样后的plot图像时间序列的统一表示按时间t_i升序排列的三元组序列其中𝑋𝑖Xi​表示𝑡𝑖ti​时刻变量值，𝑌𝑖Yi​表示标签值。一般意义的时间序列常用(𝑥𝑖,𝑡𝑖)，但为了适配涉及的多种任务，扩展为(𝑥𝑖,𝑡𝑖，yi)标签扩展与多变量yi可表示插补任务中的缺省标签、分类任务中的类别标签、异常检测中的异常标签等，使统一表示能覆盖不同任务。当一个时间点记录温度、湿度、压力等多个传感器数据时，教材用

𝑋X（以及

𝑌Y）表示多变量变量值（以及标签值），便于统一建模时间序列介绍图：时序列分解（原始数据、趋势项、周期项、残差项）

时间序列子序列按时间t_i升序排列的三元组序列S是T的一个长度为m的子序列；因此T也可视为保持有序性的子序列集合。便于在更长尺度上做分类、聚类等任务。标签扩展与多变量子序列之间是否重叠、是否等长，在不同任务中有不同定义；子序列与分段图：庆阳年月平均图时序数据相似性欧氏距离的局限性(EuclideanDistance)传统的欧氏距离要求两个序列长度相等，且对应时间点严格对齐。问题1：相位偏移(PhaseShift)：两个形状相似但发生时间略有错位的波形，欧氏距离会很大。问题2：长度不一：无法直接计算不同长度序列的距离。问题3：频率扭曲：语速快慢不同，但内容相同的语音信号。图左：欧氏距离硬性对齐（误差大）图右：DTW弹性对齐（匹配波峰波谷）DTW算法核心思想：核心目标动态时间规整（DTW）可以动态自适应地对齐不同时间序列，更准确地说，DTW可找到Tx与Ty的一种对应关系。不同时间序列可能因采样频率不同，在频域/时域上发生伸缩或弯曲，因此需要对齐后再计算距离（如MSE/MAE/欧式距离）。DTW对齐关系：索引对与三条约束约束1：覆盖性（不遗漏）每个变量值至少应包含在某个索引对中，确保没有遗漏。约束2：边界性（首尾对齐）对应关系必须包含起点(1,1)与终点(M,N),且首尾元素索引对可有多个。约束3：单调性（时间顺序不反转）

索引对应遵循单调原则，不允许时间顺序“反向匹配”。DTW算法DTW：把对齐看成“走格子”的最短路径DTW距离定义为：所有合法对应关系中“总距离最小”的那一个。因此可抽象为走格子：

起点(1,1)>终点(M,N)每一步只能向上、向右、右上走。每个格子的代价是两点间度量

可以用平方差（对应MSE）或绝对差（对应MAE）等。动态规划递推用dp表示到(i,j)的最小累计代价，通过三种前驱取min得到。求得dp[M,N]即DTW度量值；路径本身就是对应矩阵。DTW算法DTW效果与应用提示DTW的优势来自“良好的对齐性质”，在时序预测、时序分类中常表现良好。在语音的孤立词识别任务中，DTW至今仍广泛应用。

计算代价:经典DP时间复杂度为O(MN)工程优化:限制对齐窗口、剪枝、下界加速等（用于检索/批量匹配）。图：同一词语在两个不同人身上的音频信号符号化目的：三元组定义中，每个时间点的变量值X都可以对应一个确定的标签Y，这种离散表示不仅支持划分子序列，也能支持基于字符串匹配的模式挖掘。但很多时候X是连续实数：若要用“字符串算法/离散结构”（哈希、后缀结构、模式发现等），需要先把实值离散化为符号。SAX是典型的时间序列符号化方法：先降维（PAA），再用阈值区间映射到字母表。时间序列符号化图：Rawtimeseries→PAA→SAX

PAA分段聚合近似：给定长度为,选择一个较小的整数按段数w作为目标长度,把原序列按时间顺序划分成划分为w个子序列段。每段用平均值代表,实现降维(通常w<<n)因此，PAA的本质是：用w个“段均值”去近似表示原来的n个点。直观效果：保留整体轮廓/趋势，平滑局部噪声参数含义：w控制压缩率与细节保留的权衡；w小更快更粗，w大更细但开销更高。作用：为SAX的离散化做准备（先降维再映射符号）。PAA算法SAX：离散化与字母表：SAX一般会先把原始序列归一化，再进行离散化；归一化后PAA序列可视为服从正态分布的设定基础。按“等概率”原则，把数值范围切成m份（字母表大小为m），阈值取正态分布的m分位数。如·示例（m=3）：阈值约为-0.43与0.43（对应三分位），从而形成a/b/c三个区间映射。字母表更大时仍按相同方法用分位数划分。SAX算法为什么要从时域到频域：DFT与DWT是信号处理的重要分析工具，目标都是把数据从时域转换到频域，以便更好分析处理时序，但转换细节与应用场景不同。频域视角能帮助我们：

1.看周期性/主频成分2.做去噪、压缩与特征提取3.分析平稳/非平稳差异时间序列频域表示同一信号在时域表现为随时间变化的波形，在频域表现为不同频率成分的谱线（通过FFT从时域转换到频域）。DFT离散傅里叶变换：基本思想：DFT/FFT把离散信号表示为一组离散频率的正弦/余弦（或复指数）基函数的线性组合；局限性：不适合处理非平稳信号，因为它默认分析窗口内统计性质不变。DWT离散小波变换：基本思想：DWT是多分辨率分析方法，用小波函数分解信号，能同时提供时间与频率上的局部化信息。缺点：运算量很大；只有数值解，没有解析解。DFT/DWT算法DFT更偏“全局频谱”、平稳信号；DWT偏“多尺度局部”、非平稳信号。输出类型+粒度划分：时序任务可按输出分为：连续输出与离散输出。同时要考虑任务粒度（granularity）：从细到粗“点

→

子序列

→

序列”。越细粒度越强调即时性与流式处理；越粗粒度越强调语义与上下文理解。越细粒度越强调即时性与流式处理；越粗粒度越强调语义与上下文理解。右图给出典型任务分布：预测、插补、异常、变点等；离散细粒度常对应二分类，粗粒度常对应多分类。时间序列任务压缩/插补/预测：压缩：把原始时序变成更紧凑表示以节省存储；区别在于必须适应流式新增数据——新增点应能“直接压缩并合并”，不应频繁解压重压。一些典型思路如利用时间戳差分、异或计算或区间估计等降低存储占用。插补：真实采集会出现缺失值（传感器失效、传输错误等），缺失既可能发生在点级也可能发生在子序列级。例如点级插补可视作上采样，不仅补缺省值，非均匀采样下还要把变间距序列补成等间距序列。预测：利用历史序列预测未来时间点或未来窗口；压缩与插补也可视作特殊预测。预测的应用意义：金融风险评估、气象趋势周期分析、交通规划、电力网络稳定维护等。三个基础连续任务把时序变成“可迁移”的高维向量：深度学习带来新视角：时序任务中重要方向之一是表征学习（representationlearning）。目标：通过预训练任务，让网络输出的高维向量经全连接层即可适配多种任务，并获得一致良好表现预训练任务选择：预测是基础性任务，因此常用作预训练目标类比图像“掩码重建”，对完整序列随机加mask并恢复（把插补作为预训练任务）也是可选方案大规模预训练可能带来跨数据集泛化能力。理想表征在空间中会自然形成不同聚类，从而支持分类/聚类/异常检测等任务。表征学习三种表征模式：三种典型表征：按点（point-wise）、按片（patch-wise）、下采样（down-sampling）计算方式：把按固定模式收集到的实值向量与权重矩阵相乘得到表征（教材以矩阵

多变量序列需要考虑“变量间如何融合”：1.通道相关（channel-dependent）：不同变量的表征再经变量间权重矩阵聚合；2.通道独立（channel-independent）：不显式做变量间聚合。表征学习表征学习与压缩有关联——当能把数据集压缩为一组表征向量及其还原网络，意味着抓住了分析所需关键信息；这种“压缩”不仅是数据量减少，更是特征本质的捕获。异常vs变点：离散任务强调语义捕捉：标签往往来自领域专家对关键时序特征的标注，具有现实意义。异常：某个观测值（点）或一系列观测值（子序列）明显偏离一般分布；异常检测旨在识别不符合预期模式的数据点/子序列，用于故障、欺诈、市场异常预警等。变点：前后序列出现明确状态变化的转折点；常用“平稳性”刻画——均值/方差等统计量相对稳定为平稳，显著变化则为非平稳。离散型任务AR/MA/ARIMA经典统计模型：AR(p)：用过去p个观测回归预测当前值（自回归，预测值会进入后续预测）MA(q)：用过去q个误差项（噪声）构建预测，起到平滑噪声作用。RIMA(p,m,q)：在AR与MA之间加入

差分阶数m以处理非平稳序列；(p,m,q)为三类超参数。长期预测：分解

→

直接映射：将序列分解为趋势项+季节项等成分；分解后的成分做从历史窗到未来窗的直接映射（可线性或用网络），避免逐步自回归带来的累积误差。长期预测：分解

→

直接映射：核心递推：

判为变点并重置。阈值

𝜃θ：过大易阈值

𝜃θ：过大易漏检，过小易误报。漏检，过小易误报。离散型任务流式数据挖掘03Streaming

Data

Mining深入探索动态、实时、海量数据流的分析技术什么是流式数据挖掘流式数据挖掘是指在动态、连续生成的海量数据流中，实时提取有价值信息的过程。定义与静态数据集不同，它必须在数据不断变化时迅速识别模式、趋势或异常。核心要求实时性(Real-time)：数据到达即处理，无延迟。增量学习(Incremental)：模型逐步更新，而非全量重训。一次性处理(One-pass)：数据流转瞬即逝，无法回溯。流式挖掘特色高实时性必须在数据到达瞬间做出分析与决策，延迟可能导致信息价值归零。资源受限数据无限而内存有限，无法存储所有历史数据，需依赖摘要结构。动态变化数据分布随时间变化（概念漂移），模型需具备自适应能力。流式数据与时间序列数据尽管两者都涉及“时间”维度，但处理方式和目标有本质区别。流式数据常带有噪声、缺失值，且到达顺序不可预测。关键区别点：数据是否完整？是否允许延迟？是否可以回溯访问？特性时间序列挖掘(TimeSeries)流式数据挖掘(DataStreams)数据状态静态、已预先收集完整动态、无限增长、实时到达访问方式可多次随机访问、回溯通常只能单次扫描(One-pass)时效性允许一定延迟，离线分析要求极高，需实时决策算法重点全量数据的深度分析高效更新、摘要提取、鲁棒性背景案例：高频交易(HFT)毫秒级的竞争在金融市场，延迟几毫秒可能意味着巨大的损失。高频交易依赖于捕捉极短时间内的价格微小波动。流式挖掘彻底改变了金融交易方式，是技术发展的重要动力。传统模式失效：传统的“存储-再分析”模式太慢。流式挖掘优势：数据到达即处理，实时预测趋势，自动执行买卖。挑战一：实时性与时效性案例：网络游戏监控游戏服务器每秒接收数百万用户行为（移动、攻击）。技术难点：如何在数据生成瞬间完成复杂的逻辑分析？需求：必须实时监控以优化体验并防止作弊。后果：几秒的延迟会导致作弊行为未被拦截，严重破坏游戏公平性。挑战二：内存限制技术难点：如何在资源受限情况下完成规模化数据处理与分析？案例：社交媒体分析(Twitter/Weibo)流式数据是“无穷”的，每秒都有成千上万条新内容。困境：内存有限，无法永久存储所有推文。策略：必须设计适应性算法，利用有限内存处理无限数据流。方法：滑动窗口(SlidingWindow)或摘要结构(Sketch)。挑战三：不确定性与噪声技术难点：

算法必须具备强鲁棒性，能自动清洗噪声并填补缺失案例：智慧城市交通监控遍布全城的传感器收集实时路况数据。问题：设备故障、网络延迟导致数据缺失或错误。风险：依赖缺陷数据可能导致误判拥堵，发出错误调度指令。挑战四：模型更新(概念漂移)技术难点：

如何在保证准确性的同时实现低成本的频繁更新？案例：电商推荐系统用户的购物偏好随季节、潮流不断变化。静态模型缺陷：仅基于过去的数据训练，推荐可能已过时。流式需求：模型需随新数据到达而动态更新，捕捉最新的用户兴趣。处理方式：滑动窗口模型只关注最近一段时间的数据，旧数据从窗口移出，新数据加入。解决问题：内存限制。保证算法始终处理最新数据。固定窗口：大小固定（如最近1小时）。自适应窗口：根据波动调整。波动剧烈时缩短窗口提高敏感度；平稳时延长窗口降低计算成本。处理方式：倾斜时间窗口赋予不同时间段不同权重近期数据：权重高，精度高（关注当下爆发点）。远期数据：权重低，精度低（仅保留长期趋势概要）。应用：微博热搜

快速捕捉突发新闻的热度上升，同时保留历史热点的衰退轨迹。处理方式：基于摘要的数据结构核心思想在内存极小的情况下，通过特定的数据结构保存数据的“草图”(Sketch)，而非原始数据。典型代表：布隆过滤器应用：垃圾邮件过滤能极快地检查某邮件是否在黑名单中，占用空间极小。虽有极低误判率，但换取了极高的效率。流式挖掘典型算法流式聚类实时对数据进行分类，捕捉群体模式变化。

CluStream,DenStream频繁模式挖掘识别高频出现的项集（如关联商品）。

LossyCounting,FP-Stream异常检测迅速识别欺诈、入侵等偏离正常模式的事件。

kNN流检测一、流式数据聚类与传统聚类(K-Means/DBSCAN)的区别关键技术：微簇(Micro-cluster)

不仅存储数据点，而是维护一组由于数据点聚集而成的“微型统计特征”，随新数据动态调整。传统：假设数据静态，内存可全量载入，多次迭代。流式：数据无法一次性存储，必须增量更新。一、流式数据聚类微簇(Micro-cluster)的结构微簇是CluStream的核心数据结构，它是一个五元组，包含：通过仅存储这些统计量，极大地节省了内存。中心(Center)：数据点的质心。权重(Weight)：包含的数据点数量。时间戳(Timestamp)：最后更新时间，用于衰减历史权重。平方和与线性和：用于计算半径和密度。一、流式数据聚类核心算法：CluStreamCluStream创新性地将聚类过程分为两个阶段，平衡了实时性与准确性。第一阶段：在线(Online)实时维护微簇处理高速数据流，生成并更新微簇的统计信息（中心、权重、时间戳）。这是对数据的初步压缩。第二阶段：离线(Offline)宏聚类生成当用户请求时，基于微簇（而非原始数据）使用传统算法（如K-Means）生成最终的高层聚类结果。一、流式数据聚类核心算法：CluStream、DenStream等优缺点比较二、流式频繁模式挖掘应用场景挑战：内存有限，不能像Apriori算法那样多次扫描数据库。电商推荐：实时发现“啤酒+尿布”式的关联购买。网络安全：识别频繁出现的攻击特征序列。IoT监控：发现传感器读数的频繁异常组合。二、流式频繁模式挖掘核心算法：FP-StreamFP-Stream结合了FP树数据结构与滑动窗口技术。紧凑存储：FP树高效压缩存储频繁项集，减少内存。模式衰减(Decay)：引入衰减因子，旧的频繁模式权重随时间降低，确保关注近期趋势。批量更新：仅处理窗口内的新数据，动态裁剪树结构。二、流式频繁模式挖掘核心算法：有LossyCounting、FP-Stream等算法比较三、流式异常检测识别“与众不同”的数据在连续数据流中，实时发现偏离正常模式的点。难点：概念漂移（正常的定义可能会随时间改变）。网络安全：DDoS攻击流量监测。金融反欺诈：信用卡盗刷实时拦截。工业预测：机器故障前的振动异常。三、流式异常检测常用的流式异常检测算法三、流式异常检测k近邻流异常检测算法（1）局部密度假设:通过评估新数据点与其k个最近邻的相对距离来判断其是否为异常。（2）基于邻居的异常评分:算法维护一个动态的邻居集,通过计算新数据点与其k个邻近点的距离,获得一个异常评分。（3）滑动窗口机制:在流式数据场景中,算法使用滑动窗口的方式,实时更新邻居集合,以便适应数据流的变化。随着新数据的到来,旧的数据点被逐步移除,确保邻居集合始终保持最新。图数据挖掘04Graph

Data

Mining图数据挖掘概述什么是图数据?图数据是一种用于描述实体间关系的半结构化数据类型。核心价值:揭示复杂网络中的潜在模式，如影响力用户、最优路径、关键功能模块等。•节点(Node/Vertex):表示实体（如用户、基因、路由器）。•边(Edge):表示实体之间的关系（如关注、相互作用、连接）。•图数据挖掘三大核心1.节点分析度量节点的重要性，揭示其在网络中的地位（如KOL、核心服务器）。2.路径分析理解节点间的连通性、最短路径及传播效率（如导航、病毒传播）。3.社区发现识别关系紧密的节点群体，发现潜在的兴趣组或功能模块。一、节点分析目的识别和理解图中具有特殊地位的节点。这些关键节点往往对系统的稳定性和效率有显著影响。典型应用场景•社交网络:识别影响力强的用户（信息传播核心）。•互联网/电信:识别核心服务器或路由器（流量管理）。•生物网络:识别关键基因或蛋白质（疾病靶点）。节点重要性度量如何衡量一个节点在网络中有多“重要”？我们将学习三种最经典的方法：度中心性DegreeCentrality"谁的朋友最多？"接近中心性ClosenessCentrality"谁能最快联系到所有人？"PageRank网页排序算法"谁被重要的人关注？"度中心性（Degree

Centrality）最简单直观的度量，衡量节点的直接连接数。其中deg(v)是连接边数，N-1用于归一化。物理意义无向图公式:•社交网络:活跃度、受欢迎程度。•无向图:网络的“枢纽”。•局限性:仅关注局部连接，忽略全局位置和边权重。有向图中的度中心性意义:“受关注度”或“声望”。例如：微博大V，被很多人关注。意义:“活跃度”或“传播力”。例如：信息转发者，发出很多链接。入度中心性(In-degree)出度中心性(Out-degree)接近中心性（ClosenessCentrality）衡量节点到其他所有节点的平均最短距离。反映了节点在网络中的“中心”位置及传播效率。值越大，越接近中心，传播越快。应用场景•物流/交通:寻找最佳配送中心或交通枢纽。•流行病学:识别超级传播者（处于传播路径中心）。•社交营销:高效推广品牌信息的人。PageRank算法节点的重要性不仅取决于被多少节点指向（入度），还取决于指向它的节点本身的权重。核心思想"随机浏览者"模型:假设用户在网页间随机点击链接(概率d)，或随机跳转到任意页面(概率1-d)。PageRank计算公式d(阻尼因子)通常设为0.85。代表用户继续点击链接的概率。M(v)指向节点v的所有节点集合。迭代计算PR值通过多次迭代更新，直到收敛（变化量小于阈值）。节点分类（Node

Classification）基于节点的特征和网络结构，预测未知节点的类别标签。任务目标利用已知标签的节点信息，推断未标记节点的属性（如用户兴趣、账号真伪）。主要方法1基于属性的方法(传统ML)2基于图结构的方法(LPA,正则化)3基于神经网络的方法(Embedding,GNN)传统分类方法1.基于属性(Attributes)仅利用节点自身特征，忽略图结构。2.基于图结构(Structure)利用图的拓扑结构进行推断。•算法:逻辑回归,SVM,随机森林。•优点:简单，模型可解释性强。•缺点:丢失了重要的连接信息。•标签传播(LPA):"近朱者赤"，标签在邻居间扩散。•拉普拉斯正则化:强制相邻节点具有相似的预测结果。基于神经网络的方法随机游走+EmbeddingDeepWalk/Node2Vec通过在图上随机游走生成序列，利用Word2Vec学习节点的向量表示，保留局部结构。图神经网络(GNN)GCN/GAT通过聚合邻居节点的信息来学习特征。GCN利用卷积聚合，GAT引入注意力机制分配权重。GraphTransformer全局注意力捕捉长程依赖关系，克服GNN只关注局部邻域的局限。图神经网络（GNN）架构示意GNN的核心机制

GNN使得深度学习能够处理非欧几里得空间的图数据。•消息传递(MessagePassing):节点从邻居处接收信息。•聚合(Aggregation):整合邻居信息（如求和、平均）。•更新(Update):结合自身特征与聚合信息更新状态。2.路径分析研究图中节点之间的路径关系，揭示内在规律与连通性。最短路径Dijkstra,Floyd-Warshall,A*

应用：导航、路由优化连通性分析连通分量(SCC/WCC)

应用：社交圈检测、网络鲁棒性结构稳定性割点(ArticulationPoints)&割边(Bridges)

应用：寻找脆弱环节2.最短路径:Dijkstra算法一种贪心策略算法，用于计算非负权图中单源最短路径。初始化起点距离设为0，其余无穷大。松弛(Relax