prefixspan算法设计与实现(含代码)

《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;i

4、e();i++){intpos=projected[i].second;//root值为-1,每一个都是从-1开始起始。unsignedintid=projected[i].first;//行号unsignedintsize=transaction[id].size();//所在行长度maptmp;for(unsignedintj=pos+1;j

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,