欢迎来到天天文库
浏览记录
ID:957232
大小:137.00 KB
页数:16页
时间:2017-10-20
《prefixspan算法设计与实现(含代码)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、Prefixspan算法设计与实现摘要:序列模式挖掘算法有AprioriAll、GSP、FreeSpan、Prefixspan,本文将对PrefixSpan算法进行研究,来对序列模式挖掘有更深入的剖析。关键字:序列模式挖掘,Prefixspan算法一.Prefixspan算法思想:采用分治的思想,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据库上进行序列模式挖掘。PrefixSpan算法就是基于序列投影的一种模式增长算法。PrefixSpan算法是一种深度优先搜索算法,其基本思想是使用频繁前缀划分搜索空间和投影序列数据库,并搜索相关的序列。首先检查前缀子序列,只将其相应
2、的后缀子序列投影到数据库中。该算法同时采用分治(divideandconquer)的策略,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据库上进行序列模式挖掘。二.算法描述:(1)扫描序列数据库,生成所有长度为1的序列模式。(2)根据长度为1的序列模式,构造不同前缀所对应的投影数据库。(3)在相应的投影数据库上重复上述步骤,直到在相应的投影数据库上不能产生长度为1的序列模式为止。三、Prefixspan算法的具体实现完整算法实现程序见附录。用程序实现理论过程:以下是程序各模块的实现:a.数据的读取和存储:本程序数据信息存放在ccc.txt中。读入到两个数据结构中:tran
3、saction相当于一个二维数组保存了所有数据,按照字符形式读入;record里保存的是序列中每一个元素包含项的个数,例如,在record中保存形式为:13212。b.提取长度为1的序列模式:对每一行进行扫描,用counter向量保存每一个项和其出现的位置。数据的格式为’a’,[4](1,0)(2,0)(3,1)(4,1),表明a的支持度为4,在向量中出现的位置为第1行的第0个,和第2行的第0个数据等。c.扫描所包含的所有字符,并记录所有字符在每一行第一次出现的位置(行号,位置号):for(unsignedinti=0;i4、e();i++){intpos=projected[i].second;//root值为-1,每一个都是从-1开始起始。unsignedintid=projected[i].first;//行号unsignedintsize=transaction[id].size();//所在行长度maptmp;for(unsignedintj=pos+1;j5、tt++){low=high;high+=record[id][tt];if(j=low&&pos>=low&&pos::iteratork=tmp.begin();k!=tmp.end();++k)//counter中存入的是每个字母出现的频率和位置。值:{行号,6、行中位置;行号,行中位置}counter[k->first].push_back(make_pair(id,k->second));}d.根据1中扫描结果得到每个字符支持度,删除小于输入参数最小支持阈值minsup的://对counter中的值进行扫描,从第一个开始//counter中存入的是每个字母出现的频率和位置。for(map>>::iteratorl=counter.begin();l!=counter.end();){if(l->second.size()7、){map>>::iteratortmp=l;tmp=l;++tmp;counter.erase(l);//把小于的删除l=tmp;}else{++l;//不删除则向后扫描。}}e.形成投影数据库,递归:对counter中保存的长度为1的序列模式,通过迭代器iteratorl=counter.begin()继续对其进行扫描,l中数据格式’a’,[4](1,0)(2,0)(3,1)(4,
4、e();i++){intpos=projected[i].second;//root值为-1,每一个都是从-1开始起始。unsignedintid=projected[i].first;//行号unsignedintsize=transaction[id].size();//所在行长度maptmp;for(unsignedintj=pos+1;j5、tt++){low=high;high+=record[id][tt];if(j=low&&pos>=low&&pos::iteratork=tmp.begin();k!=tmp.end();++k)//counter中存入的是每个字母出现的频率和位置。值:{行号,6、行中位置;行号,行中位置}counter[k->first].push_back(make_pair(id,k->second));}d.根据1中扫描结果得到每个字符支持度,删除小于输入参数最小支持阈值minsup的://对counter中的值进行扫描,从第一个开始//counter中存入的是每个字母出现的频率和位置。for(map>>::iteratorl=counter.begin();l!=counter.end();){if(l->second.size()7、){map>>::iteratortmp=l;tmp=l;++tmp;counter.erase(l);//把小于的删除l=tmp;}else{++l;//不删除则向后扫描。}}e.形成投影数据库,递归:对counter中保存的长度为1的序列模式,通过迭代器iteratorl=counter.begin()继续对其进行扫描,l中数据格式’a’,[4](1,0)(2,0)(3,1)(4,
5、tt++){low=high;high+=record[id][tt];if(j=low&&pos>=low&&pos::iteratork=tmp.begin();k!=tmp.end();++k)//counter中存入的是每个字母出现的频率和位置。值:{行号,
6、行中位置;行号,行中位置}counter[k->first].push_back(make_pair(id,k->second));}d.根据1中扫描结果得到每个字符支持度,删除小于输入参数最小支持阈值minsup的://对counter中的值进行扫描,从第一个开始//counter中存入的是每个字母出现的频率和位置。for(map>>::iteratorl=counter.begin();l!=counter.end();){if(l->second.size()7、){map>>::iteratortmp=l;tmp=l;++tmp;counter.erase(l);//把小于的删除l=tmp;}else{++l;//不删除则向后扫描。}}e.形成投影数据库,递归:对counter中保存的长度为1的序列模式,通过迭代器iteratorl=counter.begin()继续对其进行扫描,l中数据格式’a’,[4](1,0)(2,0)(3,1)(4,
7、){map>>::iteratortmp=l;tmp=l;++tmp;counter.erase(l);//把小于的删除l=tmp;}else{++l;//不删除则向后扫描。}}e.形成投影数据库,递归:对counter中保存的长度为1的序列模式,通过迭代器iteratorl=counter.begin()继续对其进行扫描,l中数据格式’a’,[4](1,0)(2,0)(3,1)(4,
此文档下载收益归作者所有