SPADE算法相关介绍.pptx

SPADE算法汇报姓名：专业：BackgroundApplication应用背景SPADE算法Algorithm算法GSP算法问题由来Background背景随着迅速增长的数据信息，人们受到“信息爆炸”的巨大压力的同时又陷入“数据太多，知识太少”的窘境。数据挖掘技术的产生与发展为人们摆脱这种困境提供了强有力的手段。数据挖掘Background背景数据挖掘(Data Mining，简称DM)，又称为数据库中的知识发现（Knowledge Discovery Database，简称KDD)指从大型数据库或数据仓库中提取隐舍的、未知的、非平凡的及有潜在应用价值的信息或者模式．模式是指从生产经验和生活经验中经过抽象和升华提炼出来的核心知识体系。模式（Pattern）其实就是解决某一类问题的方法论。挖掘模式Apriori系列算法BackgroundGSP背景SPADE挖掘模式算法分类模式关联模式关联模式序列模式聚类模式序列模式挖掘是挖掘频繁出现的有序事件或子序列序列模式Background背景首先找出所有的频繁集，这些项集出现的频繁性至少和预定义的最小支持度一样；然后由频集产生强关联规则，这些规则必须满足最小支持度和最小置信度。支持度=序列出现次数/总序列数置信度=序列出现次数/特定子序列出现次数例：9 个月以前购买奔腾 PC 的客户很可能在一个月内订购新的 CPU 芯片SPADE算法的来历Background背景Mohammed J:SPADE: An Efficient Algorithm for Mining Frequent Sequences[J].Machine Learning,2001(42):31-60.Mohammed J针对Apriori算法需要多次扫描数据库和采用哈希树作为主要存储结构的缺点，提出了SPADE算法。主要思想Algorithm算法利用组合性质将原始问题分解为能够在主内存中解决的子问题，采用了基于序列格的有哪些信誉好的足球投注网站技术和简单的连接操作。格的定义：设（L，≤）是偏序集，若L中任意两个元素都存在上确界以及下确界，则称（L，≤）是格（lattice），为了方便，这样的格称为偏序格。“格”一种特殊的偏序集，所考虑的元素之间具有某种顺序。问题说明Algorithm序列(sequence)：将与对象A有关的所有事务按时间戳增序排序，就得到对象A的一个序列s；序列包含的项的数量记作序列的长度; 事件（event）：序列是事务的有序列表，可以记作s=e1,e2,e3,…,en；项 （item）：事件e是一个项集，可以记作e=（i1,i2,i3,…,in；序列数据库：包含一个或多个序列数据的数据集；子序列：设序列? = a1a2…an，序列? = b1b2…bm，ai 和bi都是元素。如果存在整数1 = j1 j2 … jn = m，使得a1 ? bj1，a2 ? bj2，…， an ? bjn则称序列?为序列?的子序列，又称序列?包含序列?，记为? ? ?。算法示例序列数据库对象（SID）时间戳（EID）事件A11，2，4A22，3，4A34，5B11，2B22，3B35C11，2C24Algorithm算法包含3个序列：S1=(1,2,4),(2,3,4),(4,5)S2=(1,2),(2,3),5S3=(1,2),4S1包含3个事件，8个项，长度即为8，成为8序列；S2以及S3都为S1的子序列。算法结构Algorithm算法?主要模块Algorithm算法1-频繁序列对数据库中每一项的ID-list进行读取存入内存【水平数据库向垂直数据库的转换】；扫描垂直数据库一边，存入内存，为遇到的每个新对象增加支持度。?水平垂直数据库区别在于数据库中存储数据的结构不一样，因此扫描数据库的效率不一样。主要特色Algorithm算法水平数据格式序列ID（SID）序列11,(1,2,3),(1,3),4,(3,6)2(1,4),3,(2,3),(1,5)3(5,6),(1,2),(4,6),3,245,7,(1,6),3,2,3水平数据存储格式：GSP1序列的ID_list12…SIDEIDSIDEID…111212231342213524453243SPADE：垂直数据格式SIDEID项111121，2，3131，3144153，6211，4223232，3241，5………4632序列的ID_list1,2…SIDEID(1)EID(2)…112213325435垂直数据存储格式主要模块Algorithm算法垂直数据库向水平数据库转换主要模块：产生k-序列候选集Algorithm算法当前k-1频繁序列构成了k序列的原子项，通过k-1序列之间的连接操作产生k序列候选集。规则：事件原子项：PB、PD，进行连接得到PBD。事件与序列：P