数据挖掘——序列模式挖掘
数据挖掘之序列模式挖掘
时间序列：表示为某一指标在不同时间段上的数值表现的一个有序集合序列。
时间序列的建模方法：
- 一元时间序列为基于单一随机过程的分析而揭示出其内在特征。
- 多元时间序列为多种因素共同影响的表现。
- 离散型时间为每个数据点对应的时间参数呈现间断状态。
- 连续型时间为每个数据点对应的时间参数构成连续的整体。
序列模式挖掘：
从数据集中识别出频繁子序列 用于进行模式识别的过程。
• 序列模式挖掘最初由Agrawal等人提出，并基于带有时间戳属性的事务数据库中识别出频繁项目序列来分析客户在特定时间段内的购买行为规律。
序贯模式辨识与关联式模式辨识存在显著区别：
• 在序贯数据库中可识别出各项目之间存在的次序关系。
• 在交易数据库中可识别出物品集合间的同时存在性联系。
• 关联式分析重点在于忽略不同交易间的时间位置信息，在此类场景下特别强调了事件发生时间的次序性特征。
基本概念
- 定义如下：令 I = {i₁,i₂,…,i_m} 代表一项集合，
则 S = ⟨(s₁,h₁), (s₂,h₂),…,(s_n,h_n)⟩ 被视为一个时间事务序列，
其中每个 s_i 均属于 I，
h_i 表示 s_i 发生的时间，并满足对于所有 i=1,2,…,n-1 都有 h_i < h_{i+1}。
若不考虑前后两个事务发生的时间间隔，则该时间事务序列可简化表示为 S=<s₁,s₂,…,sₙ)，并被称作一个序列（Sequence）。
其中每个项集 s_i 被称为该序列 S 的元素。
序列α的每一个元素都是序列β中的元素的真子集，并且元素存在次序关系，则序列α是序列β的子序列
-
定义2：若一个序列为S，并且S中含有k个项，则称S为k-序贯或长度为k的序贯。
-
定义3：设有两个序贯α=⟨α₁, α₂,…, αₙ⟩和β=⟨β₁, β₂,…, βₘ⟩。如果存在一组索引i₁<i₂<…<iₙ（其中每个索引都在合法范围内），使得对于所有的位置j都有αⱼ < β_{iⱼ}成立，则称序贯α是序贯β的一个子序贯（或称作序贯β包含有序贯α）。【其中每个元素都是对应位置上的真子集，并且按照顺序排列，则这样的情况称为子序贯
-
定义4：对于给定的数据库D和候选模式集合C（候选模式），候选模式c的支持度（Support）被定义为c在D中出现次数与D中所有候选模式总数之比。
• 一个候选模式c如果其支持度高于min_sup，则被称为数据库D上的频繁模式。
给定一个序列数据集D以及一个预设的支持度阈值minsup，在进行序列模式挖掘的过程中，请确定并提取出所有满足支持度条件（即至少达到minsup）的序列集合。
带交易时间的交易数据库的数据存储结构形式是由客户号（Customer-id）、带有时间戳属性（Transaction-Time）以及在每次交易中被记录的物品（Item）等组成的标准构成模式。
形式化的整理：一种理想的方法是将顾客的行为转化为时间序列数据的形式，并具体实施为按照交易发生的时间顺序将其转化为项目的排列顺序。
一般步骤
遵循Apriori类算法的水平格式方案将序列模式挖掘过程划分为五个具体的子步骤
Sorting stage 根据客户编号和交易时间对数据表执行排序操作（Sort），将同一个客户的事件整合在一起，并将其转换为按顺序处理的数据表结构。
大项集阶段
确定所有满足最小支持度的频繁项集，并同时得到了由所有频繁1-序列构成的集合L1。在实际操作中, 为了便于处理和提高效率, 常常会将大项集转换为连续的整数
- 转换阶段
• 将每个事件替换为其所属的所有 frequent item sets 的集合。
• 若某事件不含任何 frequent item sets, 则予以移除。
• 若某客户序列不含任何 frequent item sets, 则予以移除。
经过处理后, 每个客户序列将被替换成仅由 frequent item sets 组成的集合. 每个 frequent item sets 的集合表示为 {e1, e2, …, ek}, 其中 ei (1 ≤ i ≤ k) 代表每个 frequent item set.
-
序列阶段
（采用不同类型的序列模式算法）
• 在转换后的数据存储系统中检索频繁出现的模式，并将其称为主要模式。 -
选最大阶段
在大序列集中找出最长序列（Maximal Sequences）。
经典算法
1）主要采用Apriori特性的一类算法包括Apriori方法及其衍生版本如AprioriSome和AprioriAll等技术；此外还包括DynamicSome方法等。
2）垂直网格划分方法主要利用SPADE（Sequence Pattern Discovery using Equivalence classes）这一高效数据结构。
3）增量式序列模式挖掘研究的主要目标是探索如何在数据流环境中实时更新和维护序列数据库中的频繁项集；其典型代表包括ISM（Itemset-based Sequence Mining）、ISE（Inductive Sequence Evolution）、IUS（Incremental Update of Sequential Patterns）等方法。
4）针对多维数据环境中的序列模式发现问题；当前研究工作集中于开发高效处理高维数据的技术；其中包括Uni-Seq（Unidimensional Sequence Clustering）、Seq-Dim（Multi-dimensional Sequence Analysis）、Dim-Seq（Dimensional Sequence Matching）等多个著名方法。
5）在实际应用中；为了满足用户需求；通常会结合领域知识设定一系列约束条件；从而引导系统优先发现具有商业价值或社会意义的关键序列模式。
不同序列模式挖掘算法的应用领域：
根据其属性特征和元素分布情况，
将实际研究对象划分为密集型与稀疏化两类主要类型。
基于Apriori类算法的稀疏化场景分析相对较为适宜，
而针对密集型场景则难以满足需求。
当涉及带有特定限制条件（如相邻事件发生时间间隔要求）的序列模式挖掘问题时，
GSP方法表现更为突出。
PrefixSpan方法适用于多种场景下的数据分析与建模，
相比而言，在密集型数据集中PrefixSpan方法展现出更为显著的优势。
1. AprioriAll算法
AprioriAll主要是一种基于Apriori思想的扩展算法,将其核心原理应用于序贯数据挖掘领域.作为一个需要多次扫描数据库的过程存在.其主要区别在于，在生成候选项和识别频繁项时考虑了序贯元素之间的顺序关系，并将基于项的操作转换为基于序贯的操作.
每一轮扫描时都会利用上一轮产生的大规模候选序贯及其频繁程度来生成新的候选序贯.只有在整个数据集中完成完整的一轮扫描后才能确定这些候选序贯是否具有足够的支持度.
在第一次遍历之前,所有的大规模1-序贯都会被作为初始种子集合包含进去.
算法步骤：
排序环节：依据时间戳和订单编号对数据进行排序操作。
在大项集构建过程中（即"large itemset" phase），运行Apriori算法一次以获取满足最小支持度（min_sup）的所有频繁子模式/单个项目集合。
转换环节：基于前一阶段生成的大1-模式信息，在新批次的交易数据中应用MAP映射规则以获得新的模式集合。
替换原则：
若某个事务中没有被提取的大1-模式，则将其移除；
对于那些不具备被识别出的大1-模式的一次性购物记录，则将其从分析对象中剔除。
-
序列阶段：基于上一阶段所得的新项集反复运用Apriori算法以识别出新的频繁或长序列。自连接基于Apriori原则：只有当前后k-2个项目完全一致时才进行关联。首先构建所有满足第k-1个项目小于第k个项目的候选k长度系列；接着交换最后两个项目的顺序来创建另一个候选k长度系列。
-
最大化序列阶段：找出长度最长的序列模式
实例：
实例可参考：🔗（勘误<1，5>的支持数为3）
个人理解：
项集是I，对应商品，不重复计(考虑购买的顺序)
该算法存在的问题：
– 会产生规模较大的候选集合
– 必须反复访问数据库以完成数据扫描
– 难以识别长序列模式
– 在转换过程中会产生高昂的成本
2. AprioriSome算法
AprioriSome算法是一种基于AprioriAll算法的优化方法，在数据挖掘领域具有重要价值。其主要包含两个核心环节：第一阶段是识别预设长度下的长序列集合；第二阶段则是追踪不同长度下的长序列集合。
AprioriSome算法性能：
• 该算法通过跳跃计算候选项，在一定程度上降低了对数据集的访问频率。
• AprioriSome生成较多候选项时会在回溯阶段之前就已经占用满了内存空间。
• 特别在处理支持度较低且含有长序列的数据时，则采用AprioriSome算法会更加高效。
3. GSP算法
GSP（Generalized Sequential Pattern）是一种基于AprioriAll算法的知识扩展方法。该基本运行流程与AprioriAll相似：首先构建较小子项集列表；随后对这些短候选项进行冗余删减；接着通过拼接操作生成较长候选序列模式；. 最后评估所有候选模式的支持度。
该研究提出了一种基于AprioriAll算法框架的改进策略。其中针对不必要的候选模式进行了去除操作。同时采用了哈希树作为存储结构以提高效率。
GSP算法存在的问题如下：
– 在处理规模较大的序列数据集时
– 会导致产生大量候选序列
– 必须反复遍历该数据集
– 对于长序列模式的数据分析效率较低
优点
• GSP采用了时间窗口机制、滑动窗口模型以及层次化分类框架的技术体系，在设置扫描限制条件时进一步提升了候选序列筛选效率，并非仅仅停留在理论层面的改进上；该方法成功克服了传统序列模型的局限性问题，在实际应用中更加贴合需求导向；通过有效抑制无意义模式生成的数量占比，避免了模式爆炸式的泛化现象出现。
• GSP借助哈希树数据结构实现了高效的候选序列存储功能；通过创新性地将数据表示形式进行转换处理后得以实现更优模式匹配效果；这种双重优化策略使得系统在发现潜在候选项时既保证了准确性又提高了效率水平。
4. PrefixSpan算法
性能分析：
-
基于数据结构的无用序列生成
PrefixSpan算法是一种基于模式增长的方法，在处理数据库时不会生成任何没用的数据模式；相比之下，在优化算法中由于追求效率而采取的一些策略会导致处理时间呈指数级增长。 -
该算法采用了分治策略作为减少数据规模的关键手段
3.PrefixSpan算法在运行过程中内存占用较为稳定 -
该算法需要构建大量投影数据库，并且构建过程带来的计算开销较大；
-
该算法需反复扫描投影数据库以获取所需信息, 但这一过程带来了较高的计算负担, 同时也显著影响了算法的整体性能;
-
算法挖掘出的频繁序列模式均为按照严格的字典序进行组织, 这一特点无法完全满足现实中的需求