logo资料库

PrefixSpan算法设计与实现.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.13M 资料格式：doc 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    Prefixspan 算法设计与实现 摘要：序列模式挖掘算法有 AprioriAll、GSP、FreeSpan、Prefixspan， 本文将对 PrefixSpan 算法进行研究，来对序列模式挖掘有更深入的 剖析。 关键字：序列模式挖掘，Prefixspan 算法 一. Prefixspan 算法思想： 采用分治的思想，不断产生序列数据库的多个更小的投影数据 库，然后在各个投影数据库上进行序列模式挖掘。PrefixSpan 算法 就是基于序列投影的一种模式增长算法。 PrefixSpan 算法是一种深度优先搜索算法，其基本思想是使用 频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。首先 检查前缀子序列，只将其相应的后缀子序列投影到数据库中。该算法 同时采用分治(divide and conquer)的策略，不断产生序列数据库的 多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖 掘。 二.算法描述： (1)扫描序列数据库，生成所有长度为 1 的序列模式。 (2)根据长度为 1 的序列模式，构造不同前缀所对应的投影数据 库。 (3)在相应的投影数据库上重复上述步骤，直到在相应的投影数 据库上不能产生长度为 1 的序列模式为止。
    三、Prefixspan 算法的具体实现 完整算法实现程序见附录。 用程序实现理论过程： 以下是程序各模块的实现： a.数据的读取和存储: 本程序数据信息存放在 ccc.txt 中。读入到两个数据结构中： transaction 相当于一个二维数组保存了所有数据，按照字符形式读 入； 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++) { int pos = projected[i].second; //root 值为-1,每一个都是从-1 开始起始。 unsigned int id = projected[i].first; //行号 unsigned int size = transaction[id].size(); //所在行长度 map tmp; for (unsigned int j = pos + 1; j < size; j++)
    { //读取本行每个字符 char item = transaction[id][j]; string mine; int low=0,high=0; for(int tt=0;tt=low&&pos>=low&&pos
    for (map ::iterator k = tmp.begin(); k != tmp.end(); ++k) //counter 中存入的是每个字母出现的频率 和位置。值:{行号，行中位置;行号，行中位置 } counter[k->first].push_back (make_pair (id, k->second)); } d.根据1中扫描结果得到每个字符支持度，删除小于输入参数最小支 持阈值minsup的: //对 counter 中的值进行扫描，从第一个开始 //counter 中存入的是每个字母出现的频率和位置。 for (map > >::iterator l = counter.begin ();l != counter.end (); ) { if (l->second.size() < minsup) { map > >::iterator tmp = l; tmp = l; ++tmp; counter.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， 表示从-1 之后处理)，进行下一次的递归运算，因为这里按照这个顺 序扫描原始数组便可以得到投影数组。 f.递归后的操作: 而递归的结束条件为 counter.size () == 0，即没有符合条件 的 项 集 ， 这 样 就 返 回 ， 返 回 之 后 要 进 入 下 一 个 条 件 之 前 ， pattern.pop_back()需要把向量中的内容弹出，举例这就是代表 a,b 项集的结束下一个项集开始时，要弹出 b，在进行扫描，扫描出 a,c 或者其他的项集，不然就会接着 a,b,c 出现这样的序列。 g.合并数据项: 在 扫 描 1 项 集 的 过 程 中 ， 要 对 record 记 录 进 行 扫 描
    tt=0;tt=low&&pos>=low&&pos > >::iterator l = counter.begin ();l != counter.end(); ++l) { if (pattern.size () < maxpat) //pattern 中记 录数据，记录形成的序列模式。 { 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 using namespace std; template class PrefixSpan {
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料