prefixspan算法设计与实现含代码.docx
《prefixspan算法设计与实现含代码.docx》由会员分享，可在线阅读，更多相关《prefixspan算法设计与实现含代码.docx（13页珍藏版）》请在冰点文库上搜索。
prefixspan算法设计与实现含代码
Prefixspan算法设计与实现
摘要：
序列模式挖掘算法有AprioriAll、GSP、FreeSpan、Prefixspan，本文将对PrefixSpan算法进行研究，来对序列模式挖掘有更深入的剖析。
关键字：
序列模式挖掘，Prefixspan算法
一.Prefixspan算法思想：
采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。
PrefixSpan算法就是基于序列投影的一种模式增长算法。
PrefixSpan算法是一种深度优先搜索算法，其基本思想是使用频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。
首先检查前缀子序列，只将其相应的后缀子序列投影到数据库中。
该算法同时采用分治（divideandconquer）的策略，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。
二.算法描述：
（1）扫描序列数据库，生成所有长度为1的序列模式。
（2）根据长度为1的序列模式，构造不同前缀所对应的投影数据库。
（3）在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止。
三、Prefixspan算法的具体实现
完整算法实现程序见附录。
用程序实现理论过程：
以下是程序各模块的实现：
a.数据的读取和存储:
本程序数据信息存放在ccc.txt中。
读入到两个数据结构中：
transaction相当于一个二维数组保存了所有数据，按照字符形式读入；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{
intpos=projected[i].second;//root值为-1,每一个都是从-1开始起始。
unsignedintid=projected[i].first;//行号
unsignedintsize=transaction[id].size（）;//所在行长度
maptmp;
for（unsignedintj=pos+1;j{
charitem=transaction[id][j];//读取本行每个字符
stringmine;
intlow=0,high=0;
for（inttt=0;tt{
low=high;
high+=record[id][tt];
if（j=low&&pos>=low&&pos{
mine+='_';
break;
}
}
mine+=transaction[id][j];//这里形成比较项集。
if（tmp.find（mine）==tmp.end（））
tmp[mine]=j;//提取出所有出现的字符，记录每个字符第一次出现的字符及位置。
}
for（map:
:
iteratork=tmp.begin（）;k!
=tmp.end（）;++k）//counter中存入的是每个字母出现的频率和位置。
值:
{行号，行中位置;行号，行中位置}
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（）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,1），所以把a可以保存结果向量中，l->second中（1,0）（2,0）（3,1）（4,1），把l->second值付给project（project每次传进去的参数是一个数组，包含数据库的信息，数组里面每个元素的第一个是行号，第二个是行号对应行的起始位置，初始值是-1，表示从-1之后处理），进行下一次的递归运算，因为这里按照这个顺序扫描原始数组便可以得到投影数组。
f.递归后的操作:
而递归的结束条件为counter.size（）==0，即没有符合条件的项集，这样就返回，返回之后要进入下一个条件之前，pattern.pop_back（）需要把向量中的内容弹出，举例这就是代表a,b项集的结束下一个项集开始时，要弹出b，在进行扫描，扫描出a,c或者其他的项集，不然就会接着a,b,c出现这样的序列。
g.合并数据项:
在扫描1项集的过程中，要对record记录进行扫描tt=0;tthigh+=record[id][tt];
if（j=low&&pos>=low&&posmine+='_';//这里增加的就是投影数据中的_
这里就在mine中增加了_,当在输出时，监测在_就要把数据写到一起，即当a,_b出现时，就写成ab的形式。
h.在对应的投影数据库，用递归方法，在上一次记录的位置之后重新开始:
for（map>>:
:
iteratorl=counter.begin（）;l!
=counter.end（）;++l）
{
if（pattern.size（）{
pattern.push_back（make_pair（l->first,l->second.size（）））;//l->second在上一次记录位置，并且下一次开始时在这里进行扫描，即形成投影数据库。
project（l->second）;//递归
pattern.pop_back（）;//当递归完成时，把上一次的弹出，然后进行下一次个数的扫描
}
}
}
经过上述步骤，用最小支持度阈值minsup进行判断选择直至结束，递归的结束条件为counter.size（）==0，即没有符合条件的项集，这样就返回。
结果保存在out.txt中。
附录：
算法实现程序：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
templateclassPrefixSpan{
private:
vector>transaction;//保存所有的字符
vector>record;//记录每行字符串大小（黑色屏幕中出现的那些）
vector>pattern;//pattern---保存识别出的字符序列
unsignedintminsup;
unsignedintminpat;
unsignedintmaxpat;
boolall;
boolwhere;
stringdelimiter;
boolverbose;
ostream*os;
//report---输出识别出的字符序列
voidreport（vector>&projected）
{
if（minpat>pattern.size（））return;//序列要大于最小长度
for（unsignedinti=0;i*os<<（pattern[i].first）<<'';
*os<<"";
for（i=0;i*os<<（i?
"":
""）<*os<<""<}
//构造序列，并保存在pattern中
voidproject（vector>&projected）
{
if（all）report（projected）;//输出找到的序列
map>>counter;//值:
{行号，行中位置;行号，行中位置}
//对每行进行处理，保存所有字符串的第一次出现的子串及在行中的位置
for（unsignedinti=0;iintpos=projected[i].second;//root值为-1
unsignedintid=projected[i].first;//行号
unsignedintsize=transaction[id].size（）;//所在行长度
maptmp;
intlow=0,high=0,len,start;
for（unsignedintj=pos+1;jstringpr_string=transaction[id][j];
stringmine;
for（len=pr_string.size（）;len>=1;len--）
for（start=0;start+len<=pr_string.size（）;start++）{
for（intt=start;tmine+=pr_string[t];
}
if（tmp.find（mine）==tmp.end（））tmp[mine]=j;
mine="";
}
}
//把每一行出现的子串汇总起来，按照串值:
{行号，行中位置;行号，行中位置，...}的方式保存
for（map:
:
iteratork=tmp.begin（）;k!
=tmp.end（）;++k）
counter[k->first].push_back（make_pair（id,k->second））;
}
//比最小频率小的值要删掉
for（map>>:
:
iteratorl=counter.begin（）;
l!
=counter.end（）;）{
if（l->second.size（）map>>:
:
iteratortmp=l;
tmp=l;
++tmp;
counter.erase（l）;
l=tmp;
}else{
++l;
}
}
//现在保留下来的子串都是支持度大于2的
for（l=counter.begin（）;l!
=counter.end（）;++l）{
if（pattern.size（）//把子串存起来，放到pattern里面，
pattern.push_back（make_pair（l->first,l->second.size（）））;
//把{行号，行中位置;行号，行中位置，...}再次传入project函数中
project（l->second）;
pattern.pop_back（）;
}
}
}
public:
PrefixSpan（unsignedint_minsup=2,
unsignedint_minpat=1,
unsignedint_maxpat=0xffffffff,
bool_all=true,
bool_where=true,
string_delimiter="/",
bool_verbose=true）:
minsup（_minsup）,minpat（_minpat）,maxpat（_maxpat）,all（_all）,
where（_where）,delimiter（_delimiter）,verbose（_verbose）{};
~PrefixSpan（）{};
istream&read（istream&is）
{
stringline;
vectortmp;
stringitem;
stringcc;
//record;
//vectortemp;
while（getline（is,line））{
tmp.clear（）;
//temp.clear（）;
istrstreamistrs（（char*）line.c_str（））;
while（istrs>>item）tmp.push_back（item）;//每行的数据保存在vector里
//istrstreamiistrs（（char*）line.c_str（））;
//while（iistrs>>cc）
//{temp.push_back（cc.size（））;cout<transaction.push_back（tmp）;//transaction相当于一个二维数组保存了所有数据
//record.push_back（temp）;
}
//cout<returnis;
}
ostream&run（ostream&_os）
{
os=&_os;
if（verbose）{*os<<"totallines:
"<vector>root;
for（unsignedinti=0;iroot.push_back（make_pair（i,-1））;
project（root）;
return*os;
}
voidclear（）
{
transaction.clear（）;
pattern.clear（）;
}
};
intmain（intargc,char**argv）
{
unsignedintminsup=2;
cout<<"inputtheminsup:
";
cin>>minsup;
ifstreammy_infile;
ofstreammy_ofile;
my_infile.open（"ccc.txt"）;
my_ofile.open（"out.txt"）;
PrefixSpanprefixspan（minsup）;
prefixspan.read（my_infile）;
prefixspan.run（my_ofile）;
system（"pause"）;
my_ofile.close（）;
//my_infile.close（）;
return0;
}
升级会员 