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

1、Prefixspan算法设计与实现摘要：序列模式挖掘算法有AprioriAll、GSP、FreeSpan、Prefixspan，本文将对PrefixSpan算法进行研究，来对序列模式挖掘有更深入的剖析。 关键字：序列模式挖掘，Prefixspan算法一. Prefixspan算法思想：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。PrefixSpan算法就是基于序列投影的一种模式增长算法。PrefixSpan算法是一种深度优先搜索算法，其基本思想是使用频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。首先检查前缀子序列，只将其相应的后缀

2、子序列投影到数据库中。该算法同时采用分治(divide and conquer)的策略，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。二.算法描述：(1)扫描序列数据库，生成所有长度为1的序列模式。(2)根据长度为1的序列模式，构造不同前缀所对应的投影数据库。(3)在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止。三、Prefixspan算法的具体实现 完整算法实现程序见附录。用程序实现理论过程：以下是程序各模块的实现：a.数据的读取和存储:本程序数据信息存放在ccc.txt中。读入到两个数据结构中： transact

3、ion 相当于一个二维数组保存了所有数据，按照字符形式读入；record里保存的是序列中每一个元素包含项的个数，例如，在record 中保存形式为：1 3 2 1 2。b.提取长度为1 的序列模式: 对每一行进行扫描，用counter向量保存每一个项和其出现的位置。数据的格式为a,4 (1,0) (2,0) (3,1) (4,1) ，表明a的支持度为4，在向量中出现的位置为第1行的第0个，和第2行的第0个数据等。c.扫描所包含的所有字符，并记录所有字符在每一行第一次出现的位置（行号，位置号）:for (unsigned int i = 0; i projected.size(); i+) in

4、t pos = projectedi.second; /root 值为-1,每一个都是从-1开始起始。 unsigned int id = projectedi.first; /行号 unsigned int size = transactionid.size(); /所在行长度 map tmp; for (unsigned int j = pos + 1; j size; j+) char item = transactionidj; /读取本行每个字符 string mine; int low=0,high=0; for(int tt=0;ttrecordid.size();tt+) lo

5、w=high; high+=recordidtt; if(j=low&pos=low&poshigh) mine+=_; break; mine+=transactionidj; /这里形成比较项集。 if (tmp.find (mine) = tmp.end() tmpmine = j ; /提取出所有出现的字符，记录每个字符第一次出现的字符及位置。 for (map :iterator k = tmp.begin(); k != tmp.end(); +k) /counter中存入的是每个字母出现的频率和位置。值:行号，行中位置;行号，行中位置 counterk-first.push_ba

6、ck (make_pair (id, k-second); d.根据1中扫描结果得到每个字符支持度，删除小于输入参数最小支持阈值minsup的:/对counter中的值进行扫描，从第一个开始 /counter中存入的是每个字母出现的频率和位置。 for (map string, vector pair :iterator l = counter.begin ();l != counter.end (); ) if (l-second.size() minsup) map string, vector pair :iterator tmp = l; tmp = l; +tmp; counter.

7、erase (l); /把小于的删除 l = tmp; else +l; /不删除则向后扫描。 e.形成投影数据库，递归:对counter中保存的长度为1的序列模式，通过迭代器iterator l = 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，表示从

8、-1之后处理)，进行下一次的递归运算，因为这里按照这个顺序扫描原始数组便可以得到投影数组。f.递归后的操作:而递归的结束条件为counter.size () = 0，即没有符合条件的项集，这样就返回，返回之后要进入下一个条件之前， pattern.pop_back()需要把向量中的内容弹出，举例这就是代表a,b项集的结束下一个项集开始时，要弹出b，在进行扫描，扫描出a,c或者其他的项集，不然就会接着a,b,c出现这样的序列。g.合并数据项:在扫描1项集的过程中，要对record 记录进行扫描tt=0;ttrecordid.size();tt+ low=high; high+=recordidt

9、t; if(j=low&pos=low&poshigh) mine+=_;/这里增加的就是投影数据中的_ 这里就在mine中增加了_,当在输出时，监测在_就要把数据写到一起，即当a,_b出现时，就写成ab的形式。h.在对应的投影数据库，用递归方法，在上一次记录的位置之后重新开始:for (map string, vector pair :iterator l = counter.begin ();l != counter.end(); +l) if (pattern.size () maxpat) /pattern中记录数据，记录形成的序列模式。 pattern.push_back (make

10、_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 #i

11、nclude #include #include #include #include using namespace std;template class PrefixSpan private: vector vector transaction;/保存所有的字符 vector vector record;/记录每行字符串大小(黑色屏幕中出现的那些) vector pair pattern;/pattern-保存识别出的字符序列 unsigned int minsup; unsigned int minpat; unsigned int maxpat; bool all; bool where

12、; string delimiter; bool verbose; ostream *os;/report-输出识别出的字符序列 void report (vector pair &projected) if (minpat pattern.size() return;/序列要大于最小长度for (unsigned int i = 0; i pattern.size(); i+) *os (patterni.first) ; *os ; for (i = 0; i projected.size(); i+) *os (i ? : ) projectedi.first; *os endl; /构

13、造序列，并 保存在pattern中 void project (vector pair &projected) if (all) report(projected);/输出找到的序列 map string, vector pair counter;/值:行号，行中位置;行号，行中位置 /对每行进行处理，保存所有字符串的第一次出现的子串及在行中的位置 for (unsigned int i = 0; i projected.size(); i+) /对每行处理 int pos = projectedi.second;/root 值为-1 unsigned int id = projectedi.

14、first;/行号 unsigned int size = transactionid.size();/所在行长度 map tmp; int low=0,high=0,len,start; for(unsigned int j = pos + 1; j =1;len-)for(start=0;start+len=pr_string.size();start+)for(int t=start;tstart+len;t+) mine+=pr_stringt;if (tmp.find (mine) = tmp.end() tmpmine = j;mine=; /把每一行出现的子串汇总起来，按照 串值

15、:行号，行中位置;行号，行中位置，. 的方式保存 for (map :iterator k = tmp.begin(); k != tmp.end(); +k) counterk-first.push_back (make_pair (id, k-second); /比最小频率小的值要删掉 for (map string, vector pair :iterator l = counter.begin (); l != counter.end (); ) if (l-second.size() minsup) map string, vector pair :iterator tmp = l;

16、tmp = l;+tmp;counter.erase (l);l = tmp; else +l; /现在保留下来的子串都是支持度大于2的 for ( l = counter.begin (); l != counter.end(); +l) if (pattern.size () maxpat) /把子串存起来，放到pattern里面， pattern.push_back (make_pair (l-first, l-second.size(); /把行号，行中位置;行号，行中位置，. 再次传入project函数中 project (l-second); pattern.pop_back();

17、 public: PrefixSpan (unsigned int _minsup = 2, unsigned int _minpat = 1, unsigned int _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), verbo

18、se (_verbose) ; PrefixSpan () ; istream& read (istream &is) string line; vector tmp; string item;string cc;/record;/vectortemp; while (getline (is, line) tmp.clear (); /temp.clear(); istrstream istrs (char *)line.c_str(); while (istrs item) tmp.push_back (item);/每行的数据保存在vector里 / istrstream iistrs (char *)line.c_str(); /while(iistrs cc) /temp.push_back(cc.size();coutcc.size() ; transaction.push_back (tmp);/transaction 相当于一个二维数组保存了所有数据 /record.push_back(temp); /coutrecord.size