简单详细解析PrefixSpan算法（附Python源码实现）数据挖掘算法详解

PrefixSpan算法详解

一、一些概念
二、PrefixSpan算法思想及其流程
三、Python代码实现
四、一个基于真实数据库的例子
五、PrefixSpan算法优缺点

本文为博主原创文章，转载请注明出处，并附上原文链接。
原文链接：https://blog.csdn.net/qq_39872846/article/details/106290802
引言： PrefixSpan算法的全称是Prefix-Projected Pattern Growth,即前缀投影的模式挖掘，也是一种关联规则挖掘算法，就像Apriori算法，Fp-Growth算法一样，它们都是挖掘某个出现次数频繁的东西。Apriori和FpGrowth算法都是挖掘频繁项集，而PrefixSpan算法挖掘的是频繁序列。
在以下的文章中，我不会直接把标准的数学语言搬上来，这种数学语言虽然很简洁，但太抽象了，如果您喜欢这种严谨的数学语言，可以去看看其他文章。后面我会尽力形象的描述一些相关概念，尽量把概念的意思结合图示来描述，重在理解，可能存在一些不严谨的地方，或者文字过于冗余，请大家多多包涵！
一、一些概念 1、项集和序列的关系
刚才说到频繁项集和频繁序列，PrefixSpan算法挖掘的是频繁序列，Apriori和FpGrowth算法都是挖掘频繁项集。先看两个表格：

文章图片

文章图片

左边的数据记录称为项集，右边的数据记录称为序列。(网上找的图，右边表格有些字母是蓝色的，不要理会这个，当蓝色不存在)
左边表格的第四条记录 b，e，f
右边表格的第四条记录 eg(af)cbc
看出什么不同了吗？右边表格出现了重复字母，而且有些被圆括号括了起来。
可以这样理解，左边表格的每一条记录称为项集（由不同字母组成）。右边表格的每一条记录，是由多个项集组成的，而且，组成序列的项集是有先后顺序的。
在形象一点，以超市的购物记录为例：

左边表格代表的含义是：每一条记录，都是某个顾客的一次购物信息，这个信息就是顾客购买的商品种类（我们不关心他买的数量，只关心种类）。有一点需要注意，不同的记录可能是由相同的人产生的，（也就是这些不同的购物记录，可以是同一个人在不同时间去这个超市购物，产生的购物信息）。比如，小红今天去超市购买了a，b，d，明天她又去这个超市购买的a，c，d，后天她还是去这个超市购买了a，d，e。于是就产生了3条购物信息，都来自同一人，对应到左边的表格中，就是前3条记录。我们把每条购物信息称为一个项集。
右边表格代表的含义是：不同的记录一定是不同的人产生的，4条记录就说明有4个不同的顾客来这个超市购物。如果这个人今天也来购物，明天也来，后天也来购物，我们就必须把这3次购物信息，放在同一条数据记录中。具体做法是，把同一次的所有购物信息用括号括起来，在按照她购物的时间排序。以刚才的小红举例，她在不同时间去了超市3次，就产生了3次购物信息，按照购物时间，那么形成的序列就是（abd)(acd)(ade)，也就是右边表格的第一条记录。在强调一下，不同记录，一定来自不同的顾客。

还有一个地方需要注意，在看一下刚才两个表格的第四条记录：
左边表格的第四条记录 b，e，f
右边表格的第四条记录 eg(af)cbc
您应当注意到了，右边的第四条记录有些怪异，我重新写一下右边表格的第四条记录：(e )(g )(af )(c )(b )(c )，现在我把括号加全了，意思应该很明显了，这条记录代表这个顾客总共来这家超市购物过6次，如果以后她又来这家超市购物，哪就把第7次的购物信息加到这条记录的后面，不能创建新的记录（不同记录一定是不同顾客产生的）。在标准定义中，如果这个顾客某次去超市购物，只买了一个商品，默认就不加括号了。如果买了两个或两个以上，就加括号（估计是嫌麻烦，所以这样规定的，看起来更简洁了，以后看到这样形式的要注意）。
总结：不同的序列由不同的顾客产生，每一条序列由多个项集有序排列。
2、前缀、前缀投影（前缀投影又称后缀）的概念、以及求某条记录的前缀投影
这个概念很简单，我直接以一个例子说明：
看这个表格：

文章图片

为了清晰起见，我把括号加全，见下表格（和上面的表格完全一样，就是把括号加全了，防止混淆）：

SID	序列（sequence）
10	( a )( abc )( ac)( d )( cf )
20	( ad )( c )( bc )( ae )
30	( ef )( ab )( df) ( c )( b )
40	( e )( g )( af )( c )( b )( c )

(上面的每个括号都代表一个项集，代表一次购物记录，不同ID代表不同顾客)
比如，对上面的表格求（a）序列的前缀：如下表

前缀	前缀序列（后缀）
（a）	( abc )( ac)( d )( cf )
（a）	( _d )( c )( bc )( ae )
（a）	( _b )( df) ( c )( b )
（a）	( _f )( c )( b )( c )

求前缀投影的方法是：对每条数据记录，从头开始扫描，如果不是前缀就删除这个元素，如果这个元素和前缀相同，也删除这个元素，此时对这一条记录的扫描停止，并开始下一条数据记录的扫描。
==为什么出现了一个下划线 ‘_’ 呢？==下划线称为占位符。看这个例子，这条数据记录 ( ef )( ab )( df) ( c )( b )，求（a）的前缀，按照刚才所说，从头扫描，把和前缀不相同的都依次删除，第三个元素和前缀相同，都是 a，此时发现这个 a 所在的项集有2个及2个以上的元素（即 ab 在同一个项集内），那么，删除 a 后，要用一个占位符下划线，代替 a 的位置。
在看这个例子 ( a )( abc )( ac)( d )( cf )，求（a）的前缀时，第一个恰好和 a 相同，而且 a 所在的项集只有她1个元素，那么直接删除就好，不用加下划线。
当然也可以求 (a)(a) 这个序列的前缀投影，用标准数学语言，可以写为 aa，（前面说了，如果某个项集只用1个元素就不用加括号了，为了直观方便，我就加了括号），(a)(a) 的前缀投影见下表格：

前缀	前缀投影（后缀）
(a)(a)	( _bc )( ac)( d )( cf )
(a)(a)	( e )
(a)(a)
(a)(a)

(表格中有些没有 (a)(a) 序列的前缀投影，是空)
我不在详细介绍如何求一个长度大于1 的序列，它的前缀投影如何求，在二、PrefixSpan算法思想及其流程这个段落中，我会介绍如何用程序实现，其实本质就是递归，我们只要直到长度为1的序列，它的前缀投影如何求即可，如何逐次递归，叠加，就可以求出一个长度大于1 的序列，它的前缀投影。（看不懂这段没关系，后面会详细介绍）
二、PrefixSpan算法思想及其流程 PrefixSpan算法的目的是挖掘出满足最小支持度的频繁序列，和 Apriori算法类似，它是从长度为1的前缀开始挖掘序列模式，搜索对应的前缀投影数据库，得到长度为1的前缀对应的频繁序列，然后递归的挖掘长度为2的前缀所对应的频繁序列，依次类推。直到某个前缀的前缀投影数据库为空时，就结束。
以实际的例子来讲解这个算法流程，设最小支持度为2：
所用数据库如下：

SID	序列（sequence）
10	( a )( abc )( ac)( d )( cf )
20	( ad )( c )( bc )( ae )
30	( ef )( ab )( df) ( c )( b )
40	( e )( g )( af )( c )( b )( c )

（特意把括号加全，看起来更清楚了）

step1 ：
扫描整个数据库，找出所有不同的元素，结果如下：
a b c d e f g 共7个不同元素
在求出每个元素在表格中出现的次数（如果某个元素在同一条数据记录中出现多次，也只认为是出现了一次，例如 ( a )( abc )( ac)( d )( cf ) 这个序列，a元素在这条记录中，出现了多次，但是只记为出现1次），最后结果如下（数字代表出现次数）：

文章图片

显然 g 元素出现的次数比2小，所以直接删除，g元素单独出现的次数少，那么任何含g元素的序列，出现次数也一定少。（Apriori两大定律）。
那么将g 元素从上面的数据库中删除，一个都不留，结果如下（就是把第4条记录的g直接删除了）：
（下表记为数据库1号，我就随便起个编号，方便后续的一个概念说明，不要在意）

SID 序列（sequence）

10 ( a )( abc )( ac)( d )( cf )

20 ( ad )( c )( bc )( ae )

30 ( ef )( ab )( df) ( c )( b )

40 ( e )( af )( c )( b )( c )
- step2 ：
  对与这个新的数据库，依次以刚才的频繁元素为前缀，求其前缀投影，结果如下图：
  
  文章图片
  
  前缀投影的表格中，空白的意思是，该记录没有这个前缀的前缀投影。
  - step3 ：
  现在我们开始挖掘频繁序列，以 a 的前缀投影数据库为例：
  （下面是 a 的投影数据库，记为数据库2号，为了方便后续说明特意起的名字）
  
  文章图片
  
  同样的，对这个新的数据记录，求她的所有不同的元素，并求出现次数，结果如下表：
  
  文章图片
  
  可能您已经注意到了， _b 这个元素明明只出现了1次（就在第3条记录中），为什么我写的是 2 次呢？
回想一下，下划线是什么意思，它是怎么来到。前面讲过，下划线叫占位符，就是为前缀占的位，这个下划线其实代表的就是元素 a。我们的数据库2号是 a 的前缀投影，所以这个下划线才代表a，_b其实就是（ab) ，a和b在同一个项集内。
（假如我们的数据库2号是元素 c 的前缀投影数据库，那么下划线代表其实就是元素 c。）
在来看这个例子，_b出现了一次， ab也出现了1次，合起来自然就是2次了。
step4 ：
刚才我们求出了a的投影数据库，也就是数据库2号。并且求出了这个数据库中，所有的频繁元素，如下图：

文章图片

（可以看到递归的影子了把）
同样的，执行和前面相同的操作，以这些频繁元素为前缀，依次求这个数据库2号的前缀投影数据库，结果如下（注意 _b 和 b可不一样，求前缀投影时要格外注意，仔细观察这个新的投影数据库，看看以 b 为前缀的投影，和以 _b为投影的数据库有什么区别。提示一下，刚才说过 _b也可以看为 ab）：

文章图片

step5 ：
接着我们再次递归，这次选刚才的 d 为前缀的投影数据库为例：
（就是下面这个数据库，我记为数据库3号，为了方便后续说明特意起的名字）

文章图片

可以明显看到，这个数据库的所有元素，其出现次数都小于2，即没有频繁元素了，因此递归到这就结束了，不在往下递归了。也就是这一个分支的递归结束了，就是不在继续往后走了，开始往前看了。
（我要用到刚才标记的数据库2号和数据库3号了，如果忘了，请在看一下这两个数据库是怎么产生的）
简单回忆一下：
数据库3号是以d为前缀产生的前缀投影数据库，并且这个数据库3号没有频繁元素。
数据库2号是以a为前缀的投影数据库。
数据库2号的频繁元素分别是：a，b， _b， c， d， f。
这时候，一个重要的思想来了。此时程序往回走，就能求出一组频繁序列。
对于这条分支，(a)(d)就是一个频繁序列，（a）也是一个频繁序列，。
（写的有点乱，看不懂上面的话没事，请继续往下看）

文章图片

(a)(d)为什么是一个频繁序列呢？
是因为 a 和 d 都是各自的数据库中的频繁元素。在进一步思考，刚才我说数据库3号是 d 为前缀的投影数据库，其实是错的，数据库3号应该是 (a)(d) 为前缀的投影数据库，（别忘了数据库2号是以a为前缀的投影数据库，数据库3号是以d为前缀产生的前缀投影数据库，而数据库3号是由数据库2号产生的，所以说数据库3号应该是 (a)(d) 为前缀的投影数据库）
（a）也是一个频繁元素，这个很显然，因为它本来就是数据库2号的频繁元素。或者说，数据库2号的所有频繁元素，都分别是一个频繁序列。
在试想一种情况，假设数据库2号依旧是以a为前缀的投影数据库，现在有一个数据库4号，数据库4号是在数据库2号的基础上，以_b 为前缀，求出的前缀投影数据库。
那么此时，频繁序列就是 (ab) 和 (a)两个，【仔细看看，注意 (a)(b) 和 (ab) 的区别， (a)(b) 是指 a和b在不同项集， (ab) 指a和b在同一个项集】，这应该很容易理解，下划线本就是占位符，现在不过是把 a 又替换回来了，代表 ab 是处于同一个项集的。
（说的还是有点乱，看下面这张图应该更加清晰，下图是算法的某两个分支，从上往下看即可）
step6 ：
其他分支也是类似的过程，上图可以看到大量的相同操作，这些相同的操作就可以用递归表示。

到这里，整个算法流程基本讲述完毕了，就是一个不断递归求前缀投影数据库的过程，具体的代码下个段落。
三、Python代码实现运行环境：python3.6 PyCharm编译器
先给出运行结果：(图太长了，就截一半图把)

文章图片

python源码实现：

import copy#用与深拷贝def getElem(dataList):#求出这个数据集的所有不同的元素 elem = [] for i in dataList[:]: for j in i[:]: for k in j[:]: if k not in elem:#这个元素没有出现过，就添加如这个列表 elem.append(k)elem = sorted(elem)#排序 #print(elem) return elemdef deleteNotFreElem(data, notFreElem):#从数据集中删除出现次数不频繁的元素 if len(notFreElem) == 0: returnfor i in data[:]: for j in i[:]: for k in j[:]: if k in notFreElem: x = data.index(i) y = i.index(j) z = j.index(k)#上面3行，获取这个元素所在的位置 data[ x ][ y ].remove(k)#获取到位置后，移除这个不频繁的元素 while [] in i: i.remove([])#要是删除后，某个项变为空列表，就删除这个空列表 while [] in data: data.remove([])#要是删除后，某个项变为空列表，就删除这个空列表#print(data) returndef getPrefixData(e, data): #得到前缀投影的数据库 copyData = https://www.it610.com/article/list(copy.deepcopy(data))#要用深拷贝deepcopy，深拷贝是创建一块地址，内容和原来一样，但两个完全没联系 #浅拷贝copy只是地址不同，但一个变化，另一个可能会变化？在这个里面是 #若列表里全是不可变元素，则浅拷贝和深拷贝差不多 flage = 0 #一个标志变量#但若列表里包含可变元素，如字典，多维列表，等，那浅拷贝就不合适了，得用深拷贝 for i in copyData[:]: for j in i[:]: for k in j[:]: if len(j) <= 1:#如果这一行的某一个项，只有 1 个元素，若不相等直接去除就是了 if e != k: j.remove(k)#如果不是e就移除，直到 k==e 时，停止 else: j.remove(k) flage = 1#一个标志变量，如果 k==e ，则设置为 1 ，此时退出循环，加入下一条数据，去除它的前缀 break else: if e != k: j.remove(k) else: j.remove(k) j[0] ='_'+j[0]#这一行的某一个项的元素个数不是1个，当 k==e 时，去掉k，并且要在前面加下划线 ‘_’ flage = 1 break while [] in i: i.remove([])#在求后缀过程中，某个项集成了空，就删除这个空的，别让它占位置if flage == 1: flage = 0#进入下一条数据时，要把它置0 break while [] in copyData: copyData.remove([])#在求后缀过程中，某个项集成了空，就删除这个空的，别让它占位置 #print(copyData) return copyData#得到elem中每个元素的新的数据集，（就是在这个dataList数据集中，依次去掉每个元素，形成的新的数据集，为了递归往下挖掘） def getAllPrefixData( elem, prefixE, dataList): data1 = list(copy.deepcopy(dataList))#深拷贝一封数据集 allPrefixData = https://www.it610.com/article/[]#是一个四维列表，每一列都是在原来的数据集中，去除prefixE这个前缀后形成的新的数据集for e in elem: if set('_').issubset(e):#例如 _e 和 e 可不是同一个元素，要分开讨论 temp = useCycleGetPrefixData(e, prefixE, data1) allPrefixData.append(temp) else: temp2 = getPrefixData( e,data1) allPrefixData.append( temp2 )#求出 e 的后缀数据库后，加入这个类别return allPrefixData#求某个前缀的频繁元素与非频繁元素 def useCycleGetFreElem(dataList, prefixE, elem, minsup):#如果是第一次循环，没有前缀，那么 prefixE就置为 -1elemsup = {}#存放每个不同元素的出现次数，要尤其注意 _e和 e 的区别 for e in elem: for i in dataList[:]: for j in i: if set('_').issubset(e):#_e和 e 的区别，想想下划线是怎么来的，就是某个项集有2个元素及以上时，前缀字母删除后，加的下划线，这个下划线其实就是这个前缀字母 temp = e[1] if set([prefixE, temp]).issubset(set(j)):#当有下划线时，要格外注意，这个时候对 _e 计数，要看当前字面上一个元素是不是前缀元素，如果是，_e加1 elemsup[e] = elemsup.get(e, 0) + 1 if e in j: elemsup[e] = elemsup.get(e, 0) + 1 break #print(elemsup) freElem = [] notFreElem = [] for i in elemsup.keys(): if elemsup[i] >= minsup:#分辨频繁元素和非频繁元素 freElem.append(i) else: notFreElem.append(i) #print(freElem) #print(elemsup) return freElem, notFreElemdef useCycleGetPrefixData(e,prefixE, data):#这个是在带前缀的情况下，求某元素的投影 copyData = https://www.it610.com/article/list(copy.deepcopy(data))#要用深拷贝deepcopy，深拷贝是创建一块地址，内容和原来一样，但两个完全没联系flage = 0#标志变量，如果为1，表示循环要进入下一条数据记录 for i in copyData[:]: for j in i[:]: if set('_').issubset(e): if set([prefixE, e[1]]).issubset(set(j)):#下划线本来就是一个占位符，表示前缀字母，现在又变回来了了 for l in j[:]: if (l == prefixE) or (l == e[1]):#如果这个两个字母整体在这个项集里，就把这个整体都移除，形成下一个前缀的投影，也就是新的数据记录 j.remove(l) break for k in j[:]: if len(j) <= 1: if e != k: j.remove(k) else: j.remove(k) flage = 1 break else: if e != k: j.remove(k) else: j.remove(k) j[0] = '_'+j[0] flage = 1 break while [] in i: i.remove([])if flage == 1: flage = 0 break while [] in copyData: copyData.remove([]) #print(copyData) return copyDatadef cycleGetFreElem(preFixData, e, minsup):#递归调用，求出频繁序列 copyPreFixData = https://www.it610.com/article/list(copy.deepcopy(preFixData)) allFreSequence = []#存放这个项集的所有频繁序列,然后返回allElem = getElem(copyPreFixData)#返回所有单个元素 #print(allElem) freElem, notFreElem = useCycleGetFreElem(copyPreFixData, e, allElem, minsup)#求某个前缀数据库的频繁元素，和GetFreElem基本一样，就是多了个参数 #print(freElem, notFreElem) deleteNotFreElem(copyPreFixData, notFreElem)#从数据集删除非频繁元素 thisAllPrefixData = getAllPrefixData(freElem, e, copyPreFixData)#得到这个元素的投影数据库，这个函数是为了循环专用的函数 #print(thisAllPrefixData)for x in freElem: if set('_').issubset(set(x)):#有下划线就把下划线在换为前缀字母，这个整体是在一起的 newElem = [[e , x[1]]] allFreSequence.append( newElem )#生成频繁序列 else: temp2 = [[e],[x]]#没下划线，就分开放，在同一个序列，但是不在同1个项集 allFreSequence.append( temp2 )#生成频繁序列，加入lengthFreElem = len(freElem) for i in range(lengthFreElem): temp = cycleGetFreElem(thisAllPrefixData[i], freElem[i], minsup)#递归调用，求下一个前缀的频繁序列，返回它的频繁序列 for x in temp:# x 就是表示它的前缀，是一个序列 if set('_').issubset(x[0][0]):#如果有下划线一定在最前面 t = copy.deepcopy(x) t[0] = [e , str(t[0][0])[1] ]#有下划线就把下划线在换为前缀字母，这个整体是在一起的 allFreSequence.append( t ) else: t2 = copy.deepcopy(x) t2.insert(0, [e])#没有下划线，就把前缀放入第一个位置 allFreSequence.append(t2)#allFreElem.append(list(temp)) #print(allFreSequence) return allFreSequencedef prefixSpan(dataList, minsup = 2):#prefixSpan流程 elem = getElem( dataList )#得到数据集中所有不同的元素 freElem, notFreElem = useCycleGetFreElem(dataList,'-1', elem, minsup)#返回的是列表，不含支持度,一个是频繁项，一个是非频繁项，没有前缀就把 prefixE这个变量置为-1 #print(freElem, notFreElem)#['a', 'b', 'c', 'd', 'e', 'f'] ['g'] deleteNotFreElem(dataList, notFreElem)#从数据集中删除不频繁的元素 #print(dataList) allPrefixData = https://www.it610.com/article/getAllPrefixData(freElem,'-1' , dataList)#返回每个频繁元素的后缀数据库，用一个4维列表表示 #print(allPrefixData)allfreSequence = {}#收集所有的频繁序列 allListFreSequence = []#也是收集所有的频繁序列，不过是列表表示，为了输出好看点，特意弄的 lengthFreElem = len(allPrefixData) for x in range(lengthFreElem): l = cycleGetFreElem(allPrefixData[x], freElem[x], minsup)#循环递归，得到频繁序列 l.insert(0, [[freElem[x]]])#把当前循环的前缀字母放入列表最前面 #print(l) allfreSequence[freElem[x]] = l allListFreSequence.append(l)#收集所有的频繁序列，不过是用列表表示，为了输出好看点，特意弄的，当然你可以不用写for lengthE in range(lengthFreElem):#这就是一个输出，我为了输出好看一点才加的，嫌麻烦就不用写下面这个循环了 print(freElem[lengthE],'这个前缀的，它的频繁序列见下面--------------->>>>>>>>>>') for x in allListFreSequence[lengthE]: print(x)#print(allfreSequence) return allfreSequenceif __name__ == '__main__':#所用数据库如下 mydata = https://www.it610.com/article/[ [['a'], ['a', 'b', 'c'], ['a', 'c'], ['d'], ['c', 'f']], [['a', 'd'], ['c'], ['b', 'c'], ['a', 'e']], [['e' ,'f'] , ['a', 'b'], ['d', 'f'] , ['c'] ,['b']], [['e'], ['g'] ,['a', 'f'] , ['c'] ,['b'] ,['c']], ] minsup = 2 q = prefixSpan( mydata, minsup )# for x in q:#输出 #print(x,'::', q[x])

四、一个基于真实数据库的例子（我这里还有一个模拟的数据库，从网上下载的，比文章讲述的例子数据量更大一些，而且我们需要对这个数据库进行一些处理才可以使用，我将上文的python算法做了一些改变，增加了一些函数，用来处理这种真实的数据库，从中挖掘频繁序列）
数据库下载链接：https://download.csdn.net/download/qq_39872846/12451382
python算法如下：（大部分和前面的差不多，就加了几个处理数据库的函数）

import copydef mergeData(originData):#合并原始的数据集，返回一个合并后的数据集（1个用户可能会在不同时间多次去该超市购买物品。 # 我们现在就是将他所有产生的购买记录，合并为一个偏序集合） dataList = []#偏序就是与时间有关的序列，按时间顺序排序，同一个时间购买的物品用括号括起来i = 1#dataList的列表中，第一行是表头，所以跳过 allId = {}#合并数据时，需要记录不同用户所在的位置（即合并后，这个用户产生的数据在第几行），因为你不知道用户会在什么时候再来买东西。 # 所以用字典记录，以后遇到这个用户后，就查询字典，看他的数据在第几行，#我们在把他这次的数据记录插进去 count = 0 #表示，目前我们处理到第几行数据了，就是指向记录的指针 length = len(originData) while(i len( dataList[ allId[id] ] ):#用户会多次来购买，每次购买，就创建一个列表存放他这次购买的商品，按照时间把他买的商品加在属于他的那一行， dataList[ allId[id] ].append([])dataList[ allId[id] ][ time-1 ].append(item)#按照时间把他买的商品加在属于他的那一 i = i+1#指向下一条记录 return dataListdef getElem(dataList):#求出这个数据集的所有不同的元素 elem = [] for i in dataList[:]: for j in i[:]: for k in j[:]: if k not in elem:#这个元素没有出现过，就添加如这个列表 elem.append(k)elem = sorted(elem)#排序 #print(elem) return elemdef getFreElem(dataList, elem, minsup):#得到出现次数频繁的元素，以及不频繁的元素。大于最小支持度就是频繁元素elemsup = {} for e in elem: for i in dataList[:]: for j in i: if e in j: elemsup[e] = elemsup.get(e, 0) + 1#统计每个元素在总记录总出现的次数，在同1条数据记录中出现多次，依旧认为是出现1次 break freElem = [] notFreElem = [] for i in elemsup.keys(): if elemsup[i] >= minsup:#如果出现次数大于等于最小支持度，就可以说是频繁元素 freElem.append(i) else: notFreElem.append(i)#收集不频繁的元素 #print(freElem) #print(elemsup) return freElem, notFreElemdef deleteNotFreElem(data, notFreElem):#从数据集中删除出现次数不频繁的元素 if len(notFreElem) == 0: returnfor i in data[:]: for j in i[:]: for k in j[:]: if k in notFreElem: x = data.index(i) y = i.index(j) z = j.index(k)#上面3行，获取这个元素所在的位置 data[ x ][ y ].remove(k)#获取到位置后，移除这个不频繁的元素 while [] in i: i.remove([])#要是删除后，某个项变为空列表，就删除这个空列表 while [] in data: data.remove([])#要是删除后，某个项变为空列表，就删除这个空列表 #print(data) #print('1111111111111111') returndef getPrefixData(e, data): copyData = https://www.it610.com/article/list(copy.deepcopy(data))#要用深拷贝deepcopy，深拷贝是创建一块地址，内容和原来一样，但两个完全没联系 #浅拷贝copy只是地址不同，但一个变化，另一个可能会变化？在这个里面是 #若列表里全是不可变元素，则浅拷贝和深拷贝差不多 flage = 0 #一个标志变量#但若列表里包含可变元素，如字典，多维列表，等，那浅拷贝就不合适了，得用深拷贝 for i in copyData[:]: for j in i[:]: for k in j[:]: if len(j) <= 1:#如果这一行的某一个项，只有 1 个元素，若不相等直接去除就是了 if e != k: j.remove(k)#如果不是e就移除，直到 k==e 时，停止 else: j.remove(k) flage = 1#一个标志变量，如果 k==e ，则设置为 1 ，此时退出循环，加入下一条数据，去除它的前缀 break else: if e != k: j.remove(k) else: j.remove(k) j[0] ='_'+j[0]#这一行的某一个项的元素个数不是1个，当 k==e 时，去掉k，并且要在前面加下划线 ‘_’ flage = 1 break while [] in i: i.remove([])#在求后缀过程中，某个项集成了空，就删除这个空的，别让它占位置if flage == 1: flage = 0#进入下一条数据时，要把它置0 break while [] in copyData: copyData.remove([])#在求后缀过程中，某个项集成了空，就删除这个空的，别让它占位置 #print(copyData) return copyData#得到elem中每个元素的新的数据集，（就是在这个dataList数据集中，依次去掉每个元素，形成的新的数据集，为了递归往下挖掘） def getAllPrefixData( elem, prefixE, dataList): data1 = list(copy.deepcopy(dataList))#深拷贝一封数据集 allPrefixData = https://www.it610.com/article/[]#是一个四维列表，每一列都是在原来的数据集中，去除prefixE这个前缀后形成的新的数据集for e in elem: if set('_').issubset(e):#例如 _e 和 e 可不是同一个元素，要分开讨论 temp = useCycleGetPrefixData(e, prefixE, data1) allPrefixData.append(temp) else: temp2 = getPrefixData( e,data1) allPrefixData.append( temp2 )#求出 e 的后缀数据库后，加入这个类别return allPrefixData#求某个前缀的频繁元素与非频繁元素 def useCycleGetFreElem(dataList, prefixE, elem, minsup):#和getFreElem不同，在个是求，在某个前缀的前提下，求支持度elemsup = {}#存放每个不同元素的出现次数，要尤其注意 _e和 e 的区别 for e in elem: for i in dataList[:]: for j in i: if set('_').issubset(e):#_e和 e 的区别，想想下划线是怎么来的，就是某个项集有2个元素及以上时，前缀字母删除后，加的下划线，这个下划线其实就是这个前缀字母 temp = e[1] if set([prefixE, temp]).issubset(set(j)):#当有下划线时，要格外注意，这个时候对 _e 计数，要看当前字面上一个元素是不是前缀元素，如果是，_e加1 elemsup[e] = elemsup.get(e, 0) + 1 #print('22222222222222') if e in j: elemsup[e] = elemsup.get(e, 0) + 1 break #print(elemsup) freElem = [] notFreElem = [] for i in elemsup.keys(): if elemsup[i] >= minsup:#分辨频繁元素和非频繁元素 freElem.append(i) else: notFreElem.append(i) #print(freElem) #print(elemsup) return freElem, notFreElemdef useCycleGetPrefixData(e,prefixE, data):#这个是在带前缀的情况下，求某元素的投影 copyData = https://www.it610.com/article/list(copy.deepcopy(data))#要用深拷贝deepcopy，深拷贝是创建一块地址，内容和原来一样，但两个完全没联系flage = 0#标志变量，如果为1，表示循环要进入下一条数据记录 for i in copyData[:]: for j in i[:]: if set('_').issubset(e): if set([prefixE, e[1]]).issubset(set(j)):#下划线本来就是一个占位符，表示前缀字母，现在又变回来了了 for l in j[:]: if (l == prefixE) or (l == e[1]):#如果这个两个字母整体在这个项集里，就把这个整体都移除，形成下一个前缀的投影，也就是新的数据记录 j.remove(l) break for k in j[:]: if len(j) <= 1: if e != k: j.remove(k) else: j.remove(k) flage = 1 break else: if e != k: j.remove(k) else: j.remove(k) j[0] = '_'+j[0] flage = 1 break while [] in i: i.remove([])if flage == 1: flage = 0 break while [] in copyData: copyData.remove([]) #print(copyData) return copyDatadef cycleGetFreElem(preFixData, e, minsup): copyPreFixData = https://www.it610.com/article/list(copy.deepcopy(preFixData)) allFreSequence = []#存放这个项集的所有频繁序列,然后返回allElem = getElem(copyPreFixData)#返回所有单个元素 #print(allElem) freElem, notFreElem = useCycleGetFreElem(copyPreFixData, e, allElem, minsup)#求某个前缀数据库的频繁元素，和GetFreElem基本一样，就是多了个参数 #print(freElem, notFreElem) deleteNotFreElem(copyPreFixData, notFreElem)#从数据集删除非频繁元素 thisAllPrefixData = getAllPrefixData(freElem, e, copyPreFixData)#得到这个元素的投影数据库，这个函数是为了循环专用的函数 #print(thisAllPrefixData)for x in freElem: if set('_').issubset(set(x)):#有下划线就把下划线在换为前缀字母，这个整体是在一起的 newElem = [[e , x[1]]] allFreSequence.append( newElem )#生成频繁序列 else: temp2 = [[e],[x]]#没下划线，就分开放，在同一个序列，但是不在同1个项集 allFreSequence.append( temp2 )#生成频繁序列，加入lengthFreElem = len(freElem) for i in range(lengthFreElem): temp = cycleGetFreElem(thisAllPrefixData[i], freElem[i], minsup)#递归调用，求下一个前缀的频繁序列，返回它的频繁序列 for x in temp:# x 就是表示它的前缀，是一个序列 if set('_').issubset(x[0][0]):#如果有下划线一定在最前面 t = copy.deepcopy(x) t[0] = [e , str(t[0][0])[1] ]#有下划线就把下划线在换为前缀字母，这个整体是在一起的 allFreSequence.append( t ) else: t2 = copy.deepcopy(x) t2.insert(0, [e])#没有下划线，就把前缀放入第一个位置 allFreSequence.append(t2)#allFreElem.append(list(temp)) #print(allFreSequence) #print('ppppppppppppppppppppppppppp') return allFreSequencedef prefixSpan(dataList, minsup = 2): elem = getElem( dataList )#得到数据集中所有不同的元素 freElem, notFreElem = getFreElem(dataList, elem, minsup) #返回的是列表，不含支持度,一个是频繁项，一个是非频繁项 #print(freElem, notFreElem)#['a', 'b', 'c', 'd', 'e', 'f'] ['g'] deleteNotFreElem(dataList, notFreElem)#从数据集中删除不频繁的元素 #print(dataList) allPrefixData = https://www.it610.com/article/getAllPrefixData(freElem,'-1' , dataList)#返回每个频繁元素的后缀数据库，用一个4维列表表示 #print(allPrefixData)allfreSequence = {}#收集所有的频繁序列 allListFreSequence = []# 也是收集所有的频繁序列，不过是列表表示，为了输出好看点，特意弄的 lengthFreElem = len(allPrefixData) for x in range(lengthFreElem): l = cycleGetFreElem(allPrefixData[x], freElem[x], minsup)#循环递归得到频繁序列 l.insert(0, [[freElem[x]]]) #print(l) allfreSequence[freElem[x]] = l allListFreSequence.append(l)# 收集所有的频繁序列，不过是用列表表示，为了输出好看点，特意弄的，当然你可以不用写for lengthE in range(lengthFreElem): print(freElem[lengthE],'这个前缀，它的频繁序列见下面--------------->>>>>>>>>>') for x in allListFreSequence[lengthE]: print(x) #print(allfreSequence) return allfreSequenceif __name__ == '__main__':with open("runcase.txt", "r") as f: originDataList = f.readlines()#获取原始数据，事务数据库，用列表存储 f.close() #print(dataList) #print(originDataList[1][4])[1 2 3][1][4]=3[1][0]=1[1][2] = /tdataList = mergeData(originDataList)#得到合并后的数据集，是个3重列表 #print(dataList)minsup = 2 dictE = prefixSpan( dataList, minsup) # for x in dictE: #print(x, '::', dictE[x])''' 整理后的数据集就是下面这个 [ [['1', '4', '5'], ['2', '3', '6'], ['1', '4'], ['1', '2', '6'], ['1', '4', '6']], [['3', '4'], ['1', '2', '3', '6'], ['3', '4', '5'], ['6'], ['2', '5', '6'], ['1', '4', '6']], [['1', '3', '4'], ['1', '2', '6'], ['4'], ['2', '3', '5'], ['3', '4', '5'], ['2', '4']] ] '''

五、PrefixSpan算法优缺点 PrefixSpan算法由于不用产生候选序列，且投影数据库缩小的很快，内存消耗比较稳定，作频繁序列模式挖掘的时候效果很高。比起其他的序列挖掘算法有较大优势。
PrefixSpan运行时最大的消耗在递归的构造投影数据库。如果序列数据集较大，项数种类较多时，算法运行速度会有明显下降。
【简单详细解析PrefixSpan算法（附Python源码实现）】由于本人学识尚浅，文章中的讲解和代码难免会有错误，还请大家指正，本人不胜感激！