| 词条 | GSP算法 |
| 释义 | GSP算法是AprioriAll算法的扩展算法，而AprioriAll算法为Apriori类算法，故GSP算法也是一个Apriori类算法。在GSP算法中，引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量，同时还克服了基本序列模型的局限性，更切合实际，减少多余的无用模式的产生。另外，GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量，同时对数据序列的表示方法进行了转换，这样就可以有效地发现一个候选项是否是数据序列的子序列。 算法思想类似于Apriori算法，采用冗余候选模式的剪除策略和特殊的数据结构-----哈希树来实现候选模式的快速访存。 GSP算法描述1）扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集 2）根据长度为i 的种子集Li ，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集 3）重复第二步，直到没有新的序列模式或新的候选序列模式产生为止 产生候选序列模式主要分两步： 连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中 修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除 候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数 哈希树哈希树GSP采用哈希树存储候选序列模式。哈希树的节点分为三类： 1、根节点； 2、内部节点； 3、叶子节点。 根节点和内部节点中存放的是一个哈希表，每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。 添加候选序列模式从根节点开始，用哈希函数对序列的第一个项目做映射来决定从哪个分支向下，依次在第n层对序列的第n个项目作映射来决定从哪个分支向下，直到到达一个叶子节点。将序列储存在此叶子节点。 初始时所有节点都是叶子节点，当一个叶子节点所存放的序列数目达到一个阈值，它将转化为一个内部节点。 计算候选序列模式的支持度给定一个序列s是序列数据库的一个记录： 1）对于根节点，用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作 2）。 2）对于内部节点，如果s是通过对单项x做哈希映射来到此节点的，则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射，然后从相应的表项向下迭代做操作 2）或 3）。 3）对一个叶子节点，检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。 这种计算候选序列的支持度的方法避免了大量无用的扫描，对于一条序列，仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容量 GSP算法存在的主要问题如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式 需要对序列数据库进行循环扫描 对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。