《R语言数据挖掘》——2.4 序列数据集挖掘
本节书摘来自华章出版社《R语言数据挖掘》一书中的第2章，第2.4节，作者［哈萨克斯坦］贝特·麦克哈贝尔（Bater Makhabel），李洪成 许金炜 段力辉 译，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.4 序列数据集挖掘
序列数据集挖掘的一个重要任务是序列模式挖掘。A-Priori-life算法被用来进行序列模式挖掘，这里使用的A-Priori-life算法，它是采用广度优先策略。然而，FP-growth算法，采用深度优先策略。出于不同的原因，算法有时还需要综合考虑一些约束。
从序列模式中，可以发现商店消费者的常见购买模式。在其他方面，特别是广告或市场营销，序列模式挖掘发挥重要作用。可以从网络日志挖掘、网页推荐系统、生物信息学分析、病历跟踪分析、灾害预防与安全管理等领域中预测个人消费者行为。
本章中的规则都是从序列模式中挖掘出来的，它们具有多种。其中一些类型序列模式如下所示：
序列规则：X→Y，其中XY。
标签序列规则（Label Sequential Rule，LSR）：形如X→Y，其中Y是一个序列，X是将序列Y中的若干项用通配符替换后而产生的序列。
类序列规则（Class Sequential Rule，CSR）：定义为X，若：
X→y，假设S为序列数据集，I是序列数据集S中所有项的集合，Y是类标签的集合，I∩Y=，X是一个序列且y∈Y。
2.4.1 序列数据集
序列数据集S定义为元组（sid, s）的集合，其中sid为序列ID，s为序列。
在序列数据集S中，序列X的支持度定义为S中包含X的元组数，即
supportS(X)={(sid, s)∨(sid, s)∈S←Xs}
这是序列模式的一个内在性质，它应用于相关的算法，如Apriori算法的Apriori性质。对于序列X及其子序列Y，support（X）≤support(Y)。
2.4.2 GSP算法
广义序列模式（Generalized Sequential Pattern，GSP）算法是一个类似Apriori的算法，但它应用于序列模式。该算法是逐层算法，采取宽度优先策略。它具有如下的特征：
GSP算法是Apriori算法的扩展。它利用Apriori性质（向下封闭），即，给定最小支持计数，若不接受某个序列，则其超序列也将丢弃。
需要对初始事务数据集进行多次扫描。
采用水平数据格式。
每次扫描中，通过将前一次扫描中发现的模式进行自连接来产生候选项集。
在第k次扫描中，仅当在第（k-1）次扫描中接受所有的（k-1）子模式，才接收该序列模式。
GSP算法为：
伪代码为：