SPADE算法介绍

《SPADE算法介绍》由会员分享，可在线阅读，更多相关《SPADE算法介绍（26页珍藏版）》请在装配图网上搜索。

1、姓名姓名：专业专业：SPADE算法GSP算法随着迅速增长的数据信息，人们受到“信息爆炸”的巨大压力的同时又陷入“数据太多，知识太少”的窘境。数据挖掘技术的产生与发展为人们摆脱这种困境提供了强有力的手段。数据挖掘(Data Mining，简称DM)，又称为数据库中的知识发现（Knowledge Discovery Database，简称KDD)指从大型数据库或数据仓库中提取隐舍的、未知的、非平凡的及有潜在应用价值的信息或者模式模式是指从生产经验和生活经验中经过抽象和升华提炼出来的核心知识体系。模式（Pattern）其实就是解决某一类问题的方法论。SPADEGSP分类模式序列模式关联模式Aprio

2、ri系列算法聚类模式关联模式挖掘模式 算法序列模式挖掘是挖掘频繁出现的有序事件或子序列首先首先找出所有的频繁集，这些项集出现的频繁性至少和预定义的最小支持度一样；然后然后由频集产生强关联规则，这些规则必须满足最小支持度和最小置信度。支持度支持度=序列出现次数/总序列数置信置信度度=序列出现次数/特定子序列出现次数例：例：9 个月以前购买奔腾 PC 的客户很可能在一个月内订购新的 CPU 芯片Mohammed J:SPADE:An Efficient Algorithm for Mining Frequent SequencesJ.Machine Learning,2001(42):31-60.

3、Mohammed J针对Apriori算法需要多次扫描数据库和采用哈希树作为主要存储结构的缺点，提出了SPADE算法。利用组合性质将原始问题分解为能够在主内存中解决的子问题，采用了基于序列格的搜索技术和简单的连接操作。格的定义格的定义：设（L，）是偏序集，若L中任意两个元素都存在上确界以及下确界，则称（L，）是格（格（lattice），为了方便，这样的格称为偏序格偏序格。“格”一种特殊的偏序集，所考虑的元素之间具有某种顺序。采用垂直ID-list数据库格式：将序列与它发生所在的对象和时间戳清单进行关联；采用序列格方法将原始搜索空间（格）分解为较小的块（子格），子格能够独立的进行处理；将问题分解

4、与搜索模式分开，在每个子格中，都提供深度和广度搜索两种策略来枚举频繁序列。序列(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则称序列为序列的子序列，又称序列包含序列，记为 。序列数据库序列数据库对象（SID）时间戳（EI

5、D）事件A A1 11 1，2 2，4 4A A2 22 2，3 3，4 4A A3 34 4，5 5B B1 11 1，2 2B B2 22 2，3 3B B3 35 5CC1 11 1，2 2CC2 24 4包含包含3 3个序列：个序列：S S1 1=S S2 2=S S3 3=S S1 1包含包含3 3个事个事件件，8 8个项，长度个项，长度即为即为8 8，成为，成为8 8序列；序列；S S2 2以及以及S S3 3都为都为S S1 1的子序列。的子序列。1-频繁序列对数据库中每一项的ID-list进行读取存入内存【水平数据库向垂直数据库的转换】；扫描垂直数据库一边，存入内存，为遇到的每

6、个新对象增加支持度。水平垂直数据库区别水平垂直数据库区别在于数据库中存储数据的结构不一样，在于数据库中存储数据的结构不一样，因此扫描数据库的效率不一样。因此扫描数据库的效率不一样。水平数据格式水平数据格式序列ID（SID）序列1234水平数据存储格式：水平数据存储格式：GSPGSPSPADESPADE：垂直数据格式：垂直数据格式SIDEID项111121，2，3131，3144153，6211，4223232，3241，54631 1序列的序列的ID_listID_list12SIDEIDSIDEID1112122313422135244532432 2序列的序列的ID_listID_list

7、SIDEID(1)EID(2)112213325435垂直垂直数据存储格式数据存储格式垂直垂直数据库向水平数据库转换数据库向水平数据库转换当前k-1频繁序列构成了k序列的原子项，通过k-1序列之间的连接操作产生k序列候选集。规则：1.事件原子项：PB、PD，进行连接得到PBD。2.事件与序列：PB、P A，进行连接得到PBA。3.事件与事件：P A、P F，进行连接得到P AF、P A F、P F A。只需将2个k-1序列的ID-list进行简单的连接操作，检查其基数。随着序列变大，ID-list将不断缩小，进而越来越快。伪代码实现频繁序列的枚举伪代码实现频繁序列的枚举任一频繁项集的所有非空子

8、集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的。过滤候选项集，减少工作量。频繁频繁3 3序列：序列：候选产生：候选产生：14131 25 候选剪枝：候选剪枝：由k-1项生成k项序列，进行剪枝操作，再遍历数据库计算支持度。产生候选集：首先每项加入频繁k-1序列，然后进行修剪，删除至少有一个子集不是频繁序列的k序列。为了快速计数，候选集存储在hash树中选择频繁序列：遍历hash树，计算支持度。垂直存储结构基于格理论的连接操作水平存储结构基于哈希树的遍历操作GSPSPADE采用ID-list的简单连接操作，序列越长，处理速度越快；没有采用哈希树等，因此具有很好的

9、局域性；随着支持度阀值降低，序列长度变长，优势将更加明显采用哈希树存储序列信息，不用遍历数据库，加快了处理速度；但是需要多次对数据库进行扫描缺陷：候选集过多缺陷：候选集过多数据挖掘序列分析应用科学研究：天文学、基因工程、社会发展规律、人类行为规律（解决社会问题）市场行销：数据库行销（分析新用户购买的可能性）、货篮分析（识别顾客的购买行为模式）欺诈甄别：总结正常行为和诈骗行为的关系产品制造：控制参数和产品质量之间的关系通信网络管理：警告之间的先后关系记录定位和预测故障网络应用：网络信息挖掘，Web用户访问模式 Mohammed J:SPADE:An Efficient Algorithm for Mining Frequent SequencesJ.Machine Learning,2001(42):31-60.陈黎：序列挖掘算法研究D.重庆大学，2001.Srikant,R.and Agrawal,R：Mining sequential patterns:Generalizations and performance improvements.In Proc.of the 5th International Conference on Extending Database Technology.Avignon，1996.