序列模式增量挖掘与高效采样算法解析

# 序列模式增量挖掘与高效采样算法解析 ## 1. IncSpan算法概述 在序列模式增量挖掘领域，IncSpan算法是一种重要的方法。其算法大纲如下： ### 算法：IncSpan(D’, min_sup, µ, FS, SFS) - **输入**：追加数据库D’、最小支持度min_sup、原数据库D中的频繁序列集FS和半频繁序列集SFS。 - **输出**：更新后数据库D’中的频繁序列集FS’。 - **方法**： 1. 初始化FS’和SFS’为空集。 2. 扫描LDB以查找新的单个项目。 3. 将新的频繁项目添加到FS’中。 4. 将新的半频繁项目添加到SFS’中。 5. 对于FS’中的每个新项目i，执行PrefixSpan(i, D’|i, µ * min_sup, FS’, SFS’)。 6. 对于FS或SFS中的每个模式p： - 检查∆sup(p) = supdb(p)。 - 如果supD’(p) = supD(p) + ∆sup(p) ≥ min_sup，则将p插入FS’。 - 如果supLDB(p) ≥ (1 - µ) * min_sup，则执行PrefixSpan(p, D’|p, µ * min_sup, FS’, SFS’)；否则，将p插入SFS’。 7. 返回结果。 ## 2. IncSpan算法的关键问题 通过分析发现，IncSpan算法存在一些不足，主要体现在以下几个方面： ### 2.1 新单项目发现不完整 扫描LDB无法找到D’中完整的新单个频繁/半频繁项目集。因为扫描LDB通常只能发现LDB中的新单个频繁/半频繁项目，对于在LDB和D中不频繁但在D’中变得频繁/半频繁的单个项目，该算法无法发现。例如，在Counter example 3.1中，若仅扫描LDB，新的频繁项目(f)将无法被发现，从而导致所有以(f)为前缀的新频繁序列丢失。 ### 2.2 前缀子序列缺失问题 在IncSpan中，如果D中的一个不频繁序列p’在D’中变得频繁，可能其前缀子序列p不在FS中。如Counter example 3.2所示，<(a)(c)>在D中不频繁但在D’中变得频繁，但其前缀子序列<(a)>不在FS中。 ### 2.3 半频繁序列前缀问题 如果D中的一个不频繁序列p’在D’中变得半频繁，可能其前缀子序列p既不在FS中也不在SFS中。例如Counter example 3.3，<(be)>在D中不频繁但在D’中变得半频繁，但其前缀子序列<(b)>不在SFS中。 ### 2.4 定理扩展 为了对FS或SFS中的任何模式p应用基于定理2.1的剪枝技术，定理2.1可以扩展为：对于D中的任何模式p，如果其在LDB中的支持度supLDB(p) < (1 - µ) * min_sup，则不存在以p为前缀的序列p’从D中的不频繁变为D’中的频繁。 ## 3. IncSpan+算法的提出 针对IncSpan算法的不足，提出了改进算法IncSpan+。 ### 算法：IncSpan+(D’, min_sup, µ, FS, SFS) - **输入**：追加数据库D’、最小支持度min_sup、原数据库D中的频繁序列集FS和半频繁序列集SFS。 - **输出**：更新后数据库D’中的频繁序列集FS’和半频繁序列集SFS’。 - **方法**： 1. 初始化FS’和SFS’为空集。 2. 确定LDB，根据D’中序列总数调整min_sup（如果需要）。 3. 扫描整个D’以查找新的单个项目。 4. 将新的频繁项目添加到FS’中。 5. 将新的半频繁项目添加到SFS’中。 6. 对于FS’中的每个新项目i，执行PrefixSpan(i, D’|i, µ * min_sup, FS’, SFS’)。 7. 对于SFS’中的每个新项目i，执行PrefixSpan(i, D’|i, µ * min_sup, FS’, SFS’)。 8. 对于FS或SFS中的每个模式p： - 检查∆sup(p) = supdb(p)。 - 如果supD’(p) = supD(p) + ∆sup(p) ≥ min_sup，则将p插入FS’。 - 如果supLDB(p) ≥ (1 - µ) * min_sup，则执行PrefixSpan(p, D’|p, µ * min_sup, FS’, SFS’)。 - 否则，如果supD’(p) ≥ µ * min_sup，则将p插入SFS’并执行PrefixSpan(p, D’|p, µ * min_sup, FS’, SFS’)。 9. 返回结果。 ### 3.1 IncSpan+算法的正确性 IncSpan+算法能够输出更新后数据库D’中完整的频繁模式集FS’和半频繁模式集SFS’。FS’和SFS’的完整集合来自两个来源： - 新的频繁/半频繁单个项目以及所有以这些新单个项目为前缀的频繁/半频繁超序列。 - FS、SFS以及前缀在FS或SFS中的序列。 ### 3.2 IncSpan+算法的改进 与原始的IncSpan算法相比，IncSpan+具有以下改进： - 能够找到完整的FS’，保证了挖掘结果的正确性。 - 能够找到完整的SFS’，有助于增量维护频繁模式以进行进一步的数据库更新。 ## 4. 高效采样算法 ### 4.1 采样的背景和问题 随着存储数据量的不断增加，采样成为一种常