Array ( [article_id] => 162 [article_title] => Prefixspan [article_keyword] => Prefixspan,prefixspan算法,pagerank算法应用 [article_description] => Prefixspan算法采用后缀序列转前缀序列的方式来构造频繁序列。 [article_detail] => 采用后缀序列转前缀序列的方式来构造频繁序列 [article_content] => <div class="rightwrap collegeDetail"> <h1 class="algorithmName"> Prefixspan </h1> <div class="clearfix topcontent"> <p> 机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。主要研究计算机怎样模拟或实现人类的学习行为，以获取新的知识和技能，重新组织已有的知识结构，不断的改善自身的性能。 </p> <p> 机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。这些算法是一类能从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。简而言之，机器学习主要以数据为基础，通过大数据本身，运用计算机自我学习来寻找数据本身的规律，而这是机器学习与统计分析的基本区别。 </p> <p> 机器学习主要有三种方式：监督学习，无监督学习与半监督学习。 </p> <p> （1）监督学习：从给定的训练数据集中学习出一个函数，当新的数据输入时，可以根据函数预测相应的结果。监督学习的训练集要求是包括输入和输出，也就是特征和目标。训练集中的目标是有标注的。如今机器学习已固有的监督学习算法有可以进行分类的，例如贝叶斯分类，SVM，ID3，C4.5以及分类决策树，以及现在最火热的人工神经网络，例如BP神经网络，RBF神经网络，Hopfield神经网络、深度信念网络和卷积神经网络等。人工神经网络是模拟人大脑的思考方式来进行分析，在人工神经网络中有显层，隐层以及输出层，而每一层都会有神经元，神经元的状态或开启或关闭，这取决于大数据。同样监督机器学习算法也可以作回归，最常用便是逻辑回归。 </p> <p> （2）无监督学习：与有监督学习相比，无监督学习的训练集的类标号是未知的，并且要学习的类的个数或集合可能事先不知道。常见的无监督学习算法包括聚类和关联，例如K均值法、Apriori算法。 </p> <p> （3）半监督学习：介于监督学习和无监督学习之间,例如EM算法。 </p> <p> 如今的机器学习领域主要的研究工作在三个方面进行：1）面向任务的研究，研究和分析改进一组预定任务的执行性能的学习系统；2）认知模型，研究人类学习过程并进行计算模拟；3）理论的分析，从理论的层面探索可能的算法和独立的应用领域算法。 </p> </div> <div class="lemma_catalog clearfix"> <h2 class="block_title"> 目录 </h2> <div class="lemma_list"> <a href="#a_2">1、算法描述</a><a href="#a_5">2、算法背景</a><a href="#a_7">3、相关应用</a><a href="#a_9">4、参考资料</a><a href="#a_12">5、实例</a><a href="#a_20">6、输入输出</a><a href="#a_23">7、相关条目</a><a href="#a_25">8、优缺点</a> </div> </div> <a name="a_2"></a><a class="para_title"><span class="number">一</span>算法描述</a> <p> 前缀投影序列模式增长（PrefixSpan）算法是采用后缀序列转前缀序列的方式来构造频繁序列的，在转换过程中，从后缀序列中提取出1项加入到前缀序列中，变化的规则就是从左往右扫描，找到某元素的对应的项，然后做出改变；根据此规则，继续递归，直到后续的序列不满足最小支持度阈值的情况。 </p> <p> PrefixSpan是一种不需要产生候选集的频繁模式挖掘方法，采用分治的思想，不断产生序列数据库的多个更小的投影数据库（后缀子序列），然后在各个投影数据库上进行序列模式挖掘。 </p> <a name="a_5"></a><a class="para_title"><span class="number">二</span>算法背景</a> <p> Prefixspan算法是由韩家炜在2004年提出的序列模式算法，目的是为了避免产生候选序列。该算法将前端序列片段进行投影，挖掘其中的频繁项，然后扩充到Prefix中，继续挖掘，直到挖掘出所有的频繁序列。 </p> <a name="a_7"></a><a class="para_title"><span class="number">三</span>相关应用</a> <p> PrefixSpan在序列事务及有关信息处理中有着广泛的应用，如客户购物习惯、Web访问模式、科学实验过程分析、自然灾害预测、疾病治疗、药物检验及DNA等。 </p> <a name="a_9"></a><a class="para_title"><span class="number">四</span>参考资料</a> <p> 1毛国军,段丽娟,王实,石云.数据挖掘原理与算法[M].北京：清华大学出版社.2005 </p> <p> 2范明,孟小峰译.数据挖掘：概念与技术.北京：机械工业出版社.2007 </p> <a name="a_12"></a><a class="para_title"><span class="number">五</span>实例</a> <p> 给定一个序列数据库S，假设最小支持度计数为2，数据库中项的集合为{a,b,c,d,e,f,g}，数据库中包含4个序列，使用PrefixSpan算法产生频繁项集。具体如下表所示 </p> <table class="college_table"> <tbody> <tr class="thead"> <td> 序列ID </td> <td> 序列 </td> </tr> <tr> <td> 1 </td> <td> &lt;a(abc)(ac)d(cf)&gt; </td> </tr> <tr> <td> 2 </td> <td> &lt;(ad)c(bc)(ae)&gt; </td> </tr> <tr> <td> 3 </td> <td> &lt;(ef)(ab)(df)cb&gt; </td> </tr> <tr class="lasttr"> <td> 4 </td> <td> &lt;eg(af)cbc&gt; </td> </tr> </tbody> </table> <p> 求解过程如下： </p> <p> （1）得到长度为1的序列模式。扫描S一次，找出序列中所有的频繁项。每个频繁项都是长度为1的序列模式。它们是&lt;a&gt;:4,&lt;b&gt;:4,&lt;c&gt;:4,&lt;d&gt;:3,&lt;e&gt;:3和&lt;f&gt;:3，其中符号“&lt;模式&gt;:计数”表示模式和它的支持度计数。 </p> <p> （2）划分搜索空间。序列模式的完全集可根据6个前缀划分成以下6个子集：前缀为&lt;a&gt;的子集，前缀为&lt;b&gt;的子集，前缀为&lt;c&gt;的子集，前缀为&lt;d&gt;的子集，前缀为&lt;e&gt;的子集，前缀为&lt;f&gt;的子集。 </p> <p> （3）找出序列模式的子集。步骤2）提到的序列模式的子集可以通过构建相应的投影数据库并递归的挖掘每一个候选序列集。得到的结果如下 </p> <table class="college_table"> <tbody> <tr class="thead"> <td> 前缀 </td> <td> 投影数据库 </td> <td> 序列模式 </td> </tr> <tr> <td> &lt;a&gt; </td> <td> &lt;(abc)(ac)d(cf)&gt;,&lt;(-d)c(bc)(ae)&gt; </td> <td> &lt;(-b)(df)eb&gt;,&lt;(-f)cbc&gt; </td> </tr> <tr> <td> &lt;a&gt;,&lt;aa&gt;,&lt;ab&gt;,&lt;a(bc)&gt;,&lt;a(bc)a&gt;,&lt;aba&gt;,&lt;abc&gt;,&lt;(ab)&gt;,&lt;(ab)c&gt;,&lt;(ab)d&gt;,&lt;(ab)f&gt;,&lt;(ab)dc&gt;,&lt;ac&gt;,&lt;aca&gt;,&lt;acb&gt;,&lt;acc&gt;,&lt;ad&gt;,&lt;adc&gt;,&lt;af&gt; </td> <td> &lt;b&gt; </td> <td> &lt;(-c)(ac)d(cf)&gt;,&lt;(-c)(ae)&gt;, </td> </tr> <tr> <td> &lt;(df)cb&gt;,&lt;c&gt; </td> <td> &lt;b&gt;,&lt;ba&gt;,&lt;bc&gt;,&lt;(bc)&gt;,&lt;(bc)a&gt;,&lt;bd&gt;,&lt;bdc&gt;,&lt;bf&gt; </td> <td> &lt;c&gt; </td> </tr> <tr> <td> &lt;(ac)d(cf)&gt;,&lt;(bc)(ae)&gt;, </td> <td> &lt;(df)cb&gt;,&lt;c&gt; </td> <td> &lt;c&gt;,&lt;ca&gt;,&lt;cb&gt;,&lt;cc&gt; </td> </tr> <tr> <td> &lt;d&gt; </td> <td> &lt;(cf)&gt;,&lt;c(bc)(ae)&gt;,&lt;(-f)cd&gt; </td> <td> &lt;d&gt;,&lt;db&gt;,&lt;dc&gt;,&lt;dcb&gt; </td> </tr> <tr> <td> &lt;e&gt; </td> <td> &lt;(-f)(ab)(df)(cb)&gt;,&lt;(af)cbc&gt; </td> <td> &lt;e&gt;,&lt;ea&gt;,&lt;eab&gt;,&lt;eac&gt;,&lt;eacb&gt;,&lt;eb&gt;,&lt;ebc&gt;,&lt;ec&gt;,&lt;ecb&gt;,&lt;ef&gt;,&lt;efb&gt;,&lt;efc&gt;,&lt;efcb&gt; </td> </tr> <tr class="lasttr"> <td> &lt;f&gt; </td> <td> &lt;(ab)(df)cb&gt;,&lt;cbc&gt; </td> <td> &lt;f&gt;,&lt;fb&gt;,&lt;fbc&gt;,&lt;fc&gt;,&lt;fcb&gt; </td> </tr> </tbody> </table> <a name="a_20"></a><a class="para_title"><span class="number">六</span>输入输出</a> <p> 输入数据类型：数值型数据、字符型数据。（要求输入的数据应满足序列的模式） </p> <p> 输出结果：挖掘出所有满足最小支持度的序列模式 </p> <a name="a_23"></a><a class="para_title"><span class="number">七</span>相关条目</a> <p> 序列模式、GSP算法、SPADE算法 </p> <a name="a_25"></a><a class="para_title"><span class="number">八</span>优缺点</a> <p> 优点：不产生任何的候选集，减少空间；投影数据库规模不断在减少；采用分而治之的方法，提高了算法效率，而且与SPADE和GSP算法相比，在内存使用上更加的稳定。 </p> <p> 缺点：如果序列多且对每个序列建立一个投影数据库，会加大内存的使用，从而降低计算速度；实现难度大。 </p> </div> [is_show] => 1 [cat_id] => 67 [article_img] => [article_order] => 1 [article_time] => 1481348113 [isdel] => 0 )
Prefixspan

Prefixspan

机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。主要研究计算机怎样模拟或实现人类的学习行为，以获取新的知识和技能，重新组织已有的知识结构，不断的改善自身的性能。

机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。这些算法是一类能从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。简而言之，机器学习主要以数据为基础，通过大数据本身，运用计算机自我学习来寻找数据本身的规律，而这是机器学习与统计分析的基本区别。

机器学习主要有三种方式：监督学习，无监督学习与半监督学习。

（1）监督学习：从给定的训练数据集中学习出一个函数，当新的数据输入时，可以根据函数预测相应的结果。监督学习的训练集要求是包括输入和输出，也就是特征和目标。训练集中的目标是有标注的。如今机器学习已固有的监督学习算法有可以进行分类的，例如贝叶斯分类，SVM，ID3，C4.5以及分类决策树，以及现在最火热的人工神经网络，例如BP神经网络，RBF神经网络，Hopfield神经网络、深度信念网络和卷积神经网络等。人工神经网络是模拟人大脑的思考方式来进行分析，在人工神经网络中有显层，隐层以及输出层，而每一层都会有神经元，神经元的状态或开启或关闭，这取决于大数据。同样监督机器学习算法也可以作回归，最常用便是逻辑回归。

（2）无监督学习：与有监督学习相比，无监督学习的训练集的类标号是未知的，并且要学习的类的个数或集合可能事先不知道。常见的无监督学习算法包括聚类和关联，例如K均值法、Apriori算法。

（3）半监督学习：介于监督学习和无监督学习之间,例如EM算法。

如今的机器学习领域主要的研究工作在三个方面进行：1）面向任务的研究，研究和分析改进一组预定任务的执行性能的学习系统；2）认知模型，研究人类学习过程并进行计算模拟；3）理论的分析，从理论的层面探索可能的算法和独立的应用领域算法。

目录

1、算法描述2、算法背景3、相关应用4、参考资料5、实例6、输入输出7、相关条目8、优缺点
一算法描述

前缀投影序列模式增长（PrefixSpan）算法是采用后缀序列转前缀序列的方式来构造频繁序列的，在转换过程中，从后缀序列中提取出1项加入到前缀序列中，变化的规则就是从左往右扫描，找到某元素的对应的项，然后做出改变；根据此规则，继续递归，直到后续的序列不满足最小支持度阈值的情况。

PrefixSpan是一种不需要产生候选集的频繁模式挖掘方法，采用分治的思想，不断产生序列数据库的多个更小的投影数据库（后缀子序列），然后在各个投影数据库上进行序列模式挖掘。

二算法背景

Prefixspan算法是由韩家炜在2004年提出的序列模式算法，目的是为了避免产生候选序列。该算法将前端序列片段进行投影，挖掘其中的频繁项，然后扩充到Prefix中，继续挖掘，直到挖掘出所有的频繁序列。

三相关应用

PrefixSpan在序列事务及有关信息处理中有着广泛的应用，如客户购物习惯、Web访问模式、科学实验过程分析、自然灾害预测、疾病治疗、药物检验及DNA等。

四参考资料

1毛国军,段丽娟,王实,石云.数据挖掘原理与算法[M].北京：清华大学出版社.2005

2范明,孟小峰译.数据挖掘：概念与技术.北京：机械工业出版社.2007

五实例

给定一个序列数据库S，假设最小支持度计数为2，数据库中项的集合为{a,b,c,d,e,f,g}，数据库中包含4个序列，使用PrefixSpan算法产生频繁项集。具体如下表所示

序列ID 序列
1 <a(abc)(ac)d(cf)>
2 <(ad)c(bc)(ae)>
3 <(ef)(ab)(df)cb>
4 <eg(af)cbc>

求解过程如下：

（1）得到长度为1的序列模式。扫描S一次，找出序列中所有的频繁项。每个频繁项都是长度为1的序列模式。它们是<a>:4,<b>:4,<c>:4,<d>:3,<e>:3和<f>:3，其中符号“<模式>:计数”表示模式和它的支持度计数。

（2）划分搜索空间。序列模式的完全集可根据6个前缀划分成以下6个子集：前缀为<a>的子集，前缀为<b>的子集，前缀为<c>的子集，前缀为<d>的子集，前缀为<e>的子集，前缀为<f>的子集。

（3）找出序列模式的子集。步骤2）提到的序列模式的子集可以通过构建相应的投影数据库并递归的挖掘每一个候选序列集。得到的结果如下

前缀 投影数据库 序列模式
<a> <(abc)(ac)d(cf)>,<(-d)c(bc)(ae)> <(-b)(df)eb>,<(-f)cbc>
<a>,<aa>,<ab>,<a(bc)>,<a(bc)a>,<aba>,<abc>,<(ab)>,<(ab)c>,<(ab)d>,<(ab)f>,<(ab)dc>,<ac>,<aca>,<acb>,<acc>,<ad>,<adc>,<af> <b> <(-c)(ac)d(cf)>,<(-c)(ae)>,
<(df)cb>,<c> <b>,<ba>,<bc>,<(bc)>,<(bc)a>,<bd>,<bdc>,<bf> <c>
<(ac)d(cf)>,<(bc)(ae)>, <(df)cb>,<c> <c>,<ca>,<cb>,<cc>
<d> <(cf)>,<c(bc)(ae)>,<(-f)cd> <d>,<db>,<dc>,<dcb>
<e> <(-f)(ab)(df)(cb)>,<(af)cbc> <e>,<ea>,<eab>,<eac>,<eacb>,<eb>,<ebc>,<ec>,<ecb>,<ef>,<efb>,<efc>,<efcb>
<f> <(ab)(df)cb>,<cbc> <f>,<fb>,<fbc>,<fc>,<fcb>
六输入输出

输入数据类型：数值型数据、字符型数据。（要求输入的数据应满足序列的模式）

输出结果：挖掘出所有满足最小支持度的序列模式

七相关条目

序列模式、GSP算法、SPADE算法

八优缺点

优点：不产生任何的候选集，减少空间；投影数据库规模不断在减少；采用分而治之的方法，提高了算法效率，而且与SPADE和GSP算法相比，在内存使用上更加的稳定。

缺点：如果序列多且对每个序列建立一个投影数据库，会加大内存的使用，从而降低计算速度；实现难度大。