SPADE算法介绍

SPADE算法汇报 姓名 专业 SPADE算法 GSP算法 问题由来 随着迅速增长的数据信息 人们受到 信息爆炸 的巨大压力的同时又陷入 数据太多 知识太少 的窘境 数据挖掘技术的产生与发展为人们摆脱这种困境提供了强有力的手段 数据挖掘 数据挖掘 DataMining 简称DM 又称为数据库中的知识发现 KnowledgeDiscoveryDatabase 简称KDD 指从大型数据库或数据仓库中提取隐舍的 未知的 非平凡的及有潜在应用价值的信息或者模式 模式是指从生产经验和生活经验中经过抽象和升华提炼出来的核心知识体系 模式 Pattern 其实就是解决某一类问题的方法论 挖掘模式 SPADE GSP 分类模式 序列模式 关联模式 Apriori系列算法 聚类模式 关联模式 挖掘模式算法 序列模式挖掘是挖掘频繁出现的有序事件或子序列 序列模式 首先找出所有的频繁集 这些项集出现的频繁性至少和预定义的最小支持度一样 然后由频集产生强关联规则 这些规则必须满足最小支持度和最小置信度 支持度 序列出现次数 总序列数置信度 序列出现次数 特定子序列出现次数 例 9个月以前购买奔腾PC的客户很可能在一个月内订购新的CPU芯片 SPADE算法的来历 MohammedJ SPADE AnEfficientAlgorithmforMiningFrequentSequences J MachineLearning 2001 42 31 60 MohammedJ针对Apriori算法需要多次扫描数据库和采用哈希树作为主要存储结构的缺点 提出了SPADE算法 主要思想 利用组合性质将原始问题分解为能够在主内存中解决的子问题 采用了基于序列格的搜索技术和简单的连接操作 格的定义 设 L 是偏序集 若L中任意两个元素都存在上确界以及下确界 则称 L 是格 lattice 为了方便 这样的格称为偏序格 格 一种特殊的偏序集 所考虑的元素之间具有某种顺序 主要特色 采用垂直ID list数据库格式 将序列与它发生所在的对象和时间戳清单进行关联 采用序列格方法将原始搜索空间 格 分解为较小的块 子格 子格能够独立的进行处理 将问题分解与搜索模式分开 在每个子格中 都提供深度和广度搜索两种策略来枚举频繁序列 问题说明 序列 sequence 将与对象A有关的所有事务按时间戳增序排序 就得到对象A的一个序列s 序列包含的项的数量记作序列的长度 事件 event 序列是事务的有序列表 可以记作s 项 item 事件e是一个项集 可以记作e i1 i2 i3 in 序列数据库 包含一个或多个序列数据的数据集 子序列 设序列 序列 ai和bi都是元素 如果存在整数1 j1 j2 jn m 使得a1 bj1 a2 bj2 an bjn则称序列 为序列 的子序列 又称序列 包含序列 记为 示例 包含3个序列 S1 S2 S3 S1包含3个事件 8个项 长度即为8 成为8序列 S2以及S3都为S1的子序列 算法结构 主要模块 1 频繁序列对数据库中每一项的ID list进行读取存入内存 水平数据库向垂直数据库的转换 扫描垂直数据库一边 存入内存 为遇到的每个新对象增加支持度 水平垂直数据库区别在于数据库中存储数据的结构不一样 因此扫描数据库的效率不一样 主要特色 水平数据存储格式 GSP 垂直数据存储格式 主要模块 垂直数据库向水平数据库转换 主要模块 产生k 序列候选集 当前k 1频繁序列构成了k序列的原子项 通过k 1序列之间的连接操作产生k序列候选集 规则 事件原子项 PB PD 进行连接得到PBD 事件与序列 PB P A 进行连接得到PB A 事件与事件 P A P F 进行连接得到P AF P A F P F A 主要模块 计算k序列支持度 只需将2个k 1序列的ID list进行简单的连接操作 检查其基数 随着序列变大 ID list将不断缩小 进而越来越快 主要模块 k 频繁序列 伪代码实现频繁序列的枚举 剪枝操作 任一频繁项集的所有非空子集也必须是频繁的 反之 如果某个候选的非空子集不是频繁的 那么该候选肯定不是频繁的 过滤候选项集 减少工作量 频繁3序列 候选产生 候选剪枝 GSP算法 由k 1项生成k项序列 进行剪枝操作 再遍历数据库计算支持度 产生候选集 首先每项加入频繁k 1序列 然后进行修剪 删除至少有一个子集不是频繁序列的k序列 为了快速计数 候选集存储在hash树中选择频繁序列 遍历hash树 计算支持度 垂直存储结构基于格理论的连接操作 SPADE GSP 水平存储结构基于哈希树的遍历操作 GSP SPADE 采用ID list的简单连接操作 序列越长 处理速度越快 没有采用哈希树等 因此具有很好的局域性 随着支持度阀值降低 序列长度变长 优势将更加明显 采用哈希树存储序列信息 不用遍历数据库 加快了处理速度 但是需要多次对数据库进行扫描 缺陷 候选集过多 数据挖掘 序列分析应用 科学研究 天文学 基因工程 社会发展规律 人类行为规律 解决社会问题 市场行销 数据库行销 分析新用户购买的可能性 货篮分析 识别顾客的购买行为模式 欺诈甄别 总结正常行为和诈骗行为的关系产品制造 控制参数和产品质量之间的关系通信网络管理 警告之间的先后关系记录定位和预测故障网络应用 网络信息挖掘 Web用户访问模式 MohammedJ SPADE AnEfficientAlgorithmforMiningFrequentSequences J MachineLearning 2001 42 31 60 陈黎 序列挖掘算法研究 D 重庆大学 2001 Srikant R andAgrawal R Miningsequentialpatterns Gener