最近很多小伙伴都在问FP-Growth序列频繁模式挖掘和fpgrowth算法发现频繁项目集这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展(原创)时间戳概念的频繁模式挖掘：GSP算
最近很多小伙伴都在问FP-Growth序列频繁模式挖掘和fp growth算法发现频繁项目集这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展(原创)时间戳概念的频繁模式挖掘：GSP算法、SPADE算法、(原创)频繁模式挖掘Apriori算法详解、(源码)关于A->B*->D的时间序列频繁模式挖掘的思考 1.26更新、6.数据挖掘概念笔记——挖掘频繁模式、关联和相关性术等相关知识，下面开始了哦！
本文目录一览：- FP-Growth序列频繁模式挖掘（fp growth算法发现频繁项目集）
- (原创)时间戳概念的频繁模式挖掘：GSP算法、SPADE算法
- (原创)频繁模式挖掘Apriori算法详解
- (源码)关于A->B*->D的时间序列频繁模式挖掘的思考 1.26更新
- 6.数据挖掘概念笔记——挖掘频繁模式、关联和相关性术
FP-Growth序列频繁模式挖掘（fp growth算法发现频繁项目集）
1算法设计目标
输入不同的命令是用户使用Linux服务器的基本途径，通过长时间采集不同用户在使用服务器过程中所使用的命令序列，挖掘其中频繁出现的命令序列，可以帮助我们了解用户使用该服务器的基本规律。
此外，如果存在多台服务器，那么我们可以分析挖掘这些服务器中用户输入的命令序列，挖掘其中存在的频繁模式，可以了解用户使用这些服务器的根本目的。如果当这些服务器被同一个黑客攻击，或者这些服务器遭受了同一种类型的攻击，那么我们挖掘出的频繁命令模式中会存在黑客输入的命令序列，据此可以尝试理解黑客的攻击手段，还原攻击场景，为防范奠定基础。
本项目拟采用FP-Growth算法实现用户输入命令序列频繁模式的挖掘，以在不同时间段采集到的用户输入命令序列为基础，通过用户shell+ip+主机名按不同用户的登录（三者都相同才视为同一用户）构建事务，以此为基础实现用户输入命令序列频繁模式的挖掘
2 算法基本原理
FP-Growth算法主要解决挖掘在多个集合中出现次数达到一定阈值的频繁项的集合。FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把事务映射到FP树中的一条路径来构造，由于不同的事务可能会有若干个相同的项，因此它们的路径可能部分重叠。路径相互重叠越多，使用FP树结构获得的压缩效果越好。下表显示了一个数据集，它包含10个事务和5个项。
| TID |
项 |
| 1 |
{a,b} |
| 2 |
{b,c,d} |
| 3 |
{a,d,e} |
| 4 |
{a,e} |
| 5 |
{a,b,c} |
| 6 |
{a,c d} |
| 7 |
{a} |
| 8 |
{a,c} |
| 9 |
{a,d} |
| 10 |
{b,e} |
2.1 FP树构造的基本过程
在下图给出了读入三个事务之后的FP树的结构以及最终完成构建的FP树，初始，FP树仅包含一个根节点，用符号null标记，随后，用如下方法扩充FP树：
Step1：扫描一次数据，确定每个项的支持度计数，丢弃非频繁项，而将频繁项按照支持度递减排序，对于上面给出的数据集，出现频度由高到低依次是a,e。
Step2：算法第二次扫描数据集，构建FP树，读入第一个事务{a,b}后，创建标记为a和b的节点，然后形成null->a->b的路径，对该事务编码，该路径上的所有节点频度为1。
Step3：读入第二个事务{b,d}之后，为项b,d创建新的节点集，然后连接null->b->c->d形成一条新的节点集，形成一条代表该事务的路径，该路径的每个节点的频度计数也等于1，尽管前两个事务有一个共同项b,但是他们的路径不相交，因为这两个事务没有共同的前缀
Step4：第三个事务{a,e}与第一个事务共享一个共同前缀项a,所以第三个事务的路径null->a->c->d->e与第一个事务的路径null->a->b部分重叠，因为他们的路径有重叠，所以节点a的频度计数增加为2，而新创建的节点c,d和e的频度计数等于1
Step5：继续该过程直到每个事务都映射到FP树的一条路径，读入所有的事务后形成FP树
Step6：FP树还包含一个连接具有相同项的节点的指针列表，这些指针再上图中用虚线表示，有助于快速访问树中的项。
2.2 频繁项挖掘的过程
FP-growth是一种以自底向上方式探索树，由FP树产生频繁项集的算法，给定上面构建的FP树，算法按e,a的顺序在每一颗条件FP树中递归查找以其结尾的频繁项集。由于每一个事务都映射到FP树中的一条路径，因此通过仅考察包含特定节点（例如e）的路径，就可以发现以e结尾的频繁项集，使用与节点e相关联的指针，可以快速访问这些路径。
第一步收集包含e节点的所有路径，这些初始的路径称为前缀路径，如下图a所示。
Step1：由图a中所显示的前缀路径，通过把与节点e相关联的支持度计数相加得到e的支持度计数。假定最小支持度为2，因为{e}的支持度是3所以它是频繁项集
Step2：由于{e}是频繁的，因此算法必须解决发现以de,ce,be和ae结尾的频繁项集的子问题，在解决这些问题之前，必须先将前缀路径转化为条件FP树，除了用于发现以某特定后缀结尾的频繁项集之外，条件FP树的结构与FP树类似，条件FP树通过以下步骤得到。
Step2.1：首先，必须更新前缀路径上的支持度计数，因为某些计数包含那些不含项e的事务。例如，下图中的最右边路径null->b:2->c:2->e:1,包含并不含项e的事务{b,c},因此,必须将前缀路径上的计数调整为1，以反映包含{b,e}事务的实际个数。
Step2.2：删除e的节点，修剪前缀路径，删除这些节点是因为，沿这些前缀路径的支持度计数已经更新，以反映包含e的那些事务，并且发现以de,be,ae结尾的频繁项集的子问题不再需要节点e的信息。
Step2.3：更新沿前缀路径上的支持度计数之后，某些项可能不再是频繁的，例如，节点b只出现了一次，它的支持度计数等于1，这就意味着只有一个事务同时包含b和e,因为所有以be结尾的项集一定都是非频繁的，所以在以后的分析中可以安全的忽略b。
Step2.4：e的条件FP树显示在下图b中，该树看上去与原来的前缀路径不同，因为频度计数已经更新，并且节点b和e已经被删除，由于不是单个路径的树，所以需要继续挖掘。
Step2.5：FP增长使用e的条件FP树来解决发现以de,和ae结尾的频繁项集的子问题，为了发现以de结尾的频繁项集，从项e的条件FP树收集d的所有前缀路径，通过将与节点d相关联的频度计数求和，得到项集{d,e}的支持度计数。因为项集{d,e}支持度计数等于2，所以它是频繁项集，接下来，算法采用上一个步骤中的方法构建de的条件FP树。更新了支持度计数并删除了非频繁项c之后，de的条件FP显示在下图d中，因为该条件FP树只包含一个支持度等于最小支持度的项a，是单路径FP树，所以将路径上的节点排列组合与{e,d}组合，提取出{a,e}并转到下一个子问题，产生以ce结尾频繁项集，处理c的前缀路径后，只发现项集{c,e}是频繁的，接下来，算法继续解决下一个子问题并发现项集{a,e}是剩下唯一的频繁项集。
发现以e结尾的频繁项集之后，算法通过处理与节点d相关联的路径，进一步寻找以d为结尾的频繁项集，继续该过程，直到处理了所有与节点c,b和a相关联的路径为止。每一次递归，都要通过更新前缀路径中的支持度计数和删除非频繁的项来构建条件FP树，由于子问题时不相交的，因此FP增长不会产生任何重复的项集，此外，与节点相关联的支持度计数允许算法在产生相同的后缀项时进行支持度计数。
(原创)时间戳概念的频繁模式挖掘：GSP算法、SPADE算法
本文核心理论依托于MOHAMMED J. ZAKI于Machine Learning,42,31–60,2001发表的文章，由于国内暂时没有相应文献对SPADE算法做详细讲解，本人翻译原文后以通俗易懂的形式展现给读者。英文水平捉急，若有个别地方理解有误望批评指正。
1.什么是时间戳概念的频繁模式挖掘？
所谓时间戳(time-stamp)就是加入了时间序列的概念，即每次发生的时间都有时间先后的顺序，在前面讲解的Apriori算法中并没有加入此概念，虽然Apriori加入了先验性质以减少每轮遍历的次数，但是由于加入了“时间发生先后”的概念，导致时间复杂度大大增加，无疑需要一种新颖的办法解决该问题。
2.GSP算法
GSP算法是加入了垂直列表数据库和哈希树概念的Apriori算法，并且依旧使用连接步、剪枝步完成计算。其处理思路如下：
上图是我们的原始数据，其中SID表示事件号，EID表示时间戳(即什么时候发生了该动作)，我们可以看到，在一个事件内可以在多个时间发生动作，在一个时间点内也可以发生多个动作，诸如x->y这样的行为表示先发生了x，之后发生了y，之间隔了多长时间无所谓，但是一定要在一个SID中。
如果假定支持度为2，那么1成员频繁序列有A、B、D、F四个成员，出现的次数如右图，以成员A为例，则表示A成员在SID=1~4这四个事件中都出现过，在计算2成员频繁序列中采用广度搜索的哈希树作为遍历手段，如下图所示：
我们可以看到，再加入时间戳概念后，遍历的复杂度大大提高，因为不光要考虑诸如AB这样的“同时发生”的概念，概要考虑A->B这样的先后次序发生概念，在本data中寻找2成员频繁项集一共需要(3*2)*4=24次，然后每次需要在遍历全部的data来判断该项目是否频繁，那么一共需要计算24*10=240次，几百次对计算机来说不成问题。最终计算结果如下图：
我可以看到，3成员频繁项集虽然看起来匹配的很轻松，但是依旧要遍历8次原始数据，一旦数据巨大，无疑这笔开销会异常恐怖，为了进一步提升效率，学者研发了SPADE算法。
2.SPADE算法
SPADE算法依旧使用传统的先验性质，即连接步+剪枝步的经典组合，思想跟GSP大致相同，其中寻找1成员和2成员频繁项集方法跟GSP完全形同，在之后的3成员及之后的频繁项计算中，采取了一种“作弊”的办法 (= -) ，该办法套用了三种屡试不爽的公式，如下：
1.如果诸如成员PA,PD这样的形式出现在2频繁项集中，则能推导出PBD这样的三成员元素。
2.如果出现诸如PB,P->A这样的形式出现在2频繁项集中，则能推导出PB->A这样的三成员元素。
3.如果出现诸如P->A，P->F这样的形式出现在2频繁项集中，则能推导出P->AF或P->A->F或P->F->A这样的三成员元素。
以上推推导出的三成员元素注意！仅仅是“有可能”是频繁的元素，至于是不是频繁的，还得去原始data中进一步遍历、判断。
比如在本例中AB，AF是两个频繁的2成员项，那么有可能注意是“有可能”存在且仅存在ABF这样的3成员频繁项，经过10次计算遍历了一遍data发现ABF确实是频繁的。
(原创)频繁模式挖掘Apriori算法详解
本数据挖掘算法是本人进入研究生学习阶段进行的第一项“比较难”的学习，下文除了源代码有参考Zealseeker博主之外均为原创手打，如有哪里写的不严谨，望请谅解。
首先频繁模式(Frequent Patten)表示频繁的出现在数据集中的模式，举个例子，去烧烤摊点串，这种菜单上的内容就是一种频繁模式，因为会有某种串被点了很多根，那么这就视为是一种“频繁”的成员，同时还有两个比较重要的概念是“支持度”和“置信度”，支持度表示表示两种事务同时发生的概率，举个例子，这家店今天有一百桌吃饭，其中同时点了羊肉串和牛肉串的有20桌，那么就认为该事件的支持度为20%；同时，点了牛肉串的有50桌，在这50桌里有20桌点了羊肉串，那么支持度为40%。“最小支持度阈值”即我们设定的支持度下限，“最小置信度阈值同理”。
Apriori使用一种逐层迭代的方法来搜索频繁项集，所谓频繁项集，即在上文中出现的“牛肉串、羊肉串同时购买”这样的两种或多种时间同时发生并且至少达到预设的最小支持度的事件。下面我依据《数据挖掘：概念与技术（第三版）》中的某分店实物数据进行详细阐述。
T100=[I1,I2,I5]
T200=[I2,I4]
T300=[I2,I3]
T400=[I1,I4]
T500=[I1,I3]
T600=[I2,I3]
T700=[I1,I3]
T800=[I1,I3,I5]
T900=[I1,I3]
在这里我设置最小频繁度为2，即出现了两次我就认为它是频繁的。
如果用传统的思想解决这个问题，我们会找到满足最小频繁度的一成员频繁项集，随即根据排列组合用两个for循环遍历所有的情况，在上面的原始数据中，I1~I5均是频繁的；在下面的寻找二成员频繁项集中就会排列组合出所有的情况，在这些情况中进行筛选。例子中的原始数据非常小，看起来不复杂，如果数据量巨大，光排列组合加每个集合对比这两个工作就会产产生指数倍的复杂度，最可怕的是其中可能会有大量的运算是无效的，因为某集合如果不是频繁的，那么更大的集合也一定不频繁，传统笨方法会将这种情况也进行运算，因此消耗大量计算及资源。
Apriori算法采用了一种新颖的“先验性质”，即频繁项集的所有非空子集也一定是频繁的。根据这个原则，Apriori将运算分为两步：（1）连接步 （2）剪枝步
（1）连接步：连接步意味着小的频繁集合如何变成更大的集合，就像原始数据中I1可以跟I2变成[''I1'',''I2'']，以此类推，再复杂一点比如(1,2),(1,3),5),(2,4),5)这样的集合连接方法是：如果每个集合中有k-1项，前k-2项都相同，那么就把他们组成更大的k项集合，因此可以组成(1,2,3,4,5)组成四个成员的集合同理。
（2）剪枝步：剪枝步优先将该集合内的所有成员进行一次排列组合，比如(1,3)能排列成(1,3)，（代码中使用itertools.combinations函数来快速分割）,其中这三个子集全都是频繁的，那么我们就认为(1,3)是频繁的，并append()到一个装有频繁项集列表中；如果它的子集中有一个不是频繁的，那它就不频繁，拒绝append。
下面的代码是强化注释版Apriori算法，亲测能运行，注释非常之详细，傻瓜级。
#coding:utf-8
import itertools
class Apriori:
def __init__(self,min_sup=0.2,dataDic={}):
self.data = dataDic
self.size = len(dataDic) #Get the number of events
self.min_sup = min_sup
self.min_sup_val = min_sup * self.size #这个数值是频繁算法的分子整数部分
def find_frequent_1_itemsets(self):
FreqDic = {} #{itemset1:freq1,itemsets2:freq2} 不管频繁度如何，先计算频繁度，然后装到这里面
for event in self.data: #event表示字典里的键值，比如T100
for item in self.data[event]:
if item in FreqDic: #该成员是否出现过，出没出现过都要对它进行赋值
FreqDic[item] += 1 #出现过则+1
else:
FreqDic[item] = 1 #没出现过则初始值为1
L1 = []
for itemset in FreqDic: #遍历第一轮“频繁”的成员
if itemset >= self.min_sup_val: #如果频繁度大于设定值
L1.append([itemset]) #将该成员推入列表,仅仅是将成员推入列表，频度不管
return L1
def has_infrequent_subset(self,c,L_last,k): #这是一个进行排列组合的函数
subsets = list(itertools.combinations(c,k-1)) #在列表c中选择k-1个元素进行无序组合
for each in subsets: #遍历这些组合的情况
each = list(each) #把元素强制转换成列表
if each not in L_last: #如果上一轮筛选出的集合中的成员没有在该组合中出现，则返回一个True，出现过则继续遍历所有组合的情况
return True
return False
def apriori_gen(self,L_last): #L_last means frequent(k-1) itemsets 难点！！！
k = len(L_last[0]) + 1 #len()对于列表，则返回成员的个数 如[''I1'',''I2'']就返回2
Ck = [] #候选项集集合
for itemset1 in L_last: #循环遍历L_last中的成员
for itemset2 in L_last:
#join step
flag = 0
for i in range(k-2):
if itemset1[i] != itemset2[i]:
flag = 1 #the two itemset can''t join
break
if flag == 1:
continue
if itemset1[k-2] < itemset2[k-2]:
c = itemset1 + [itemset2[k-2]] #例：[''I1'']<[''I2'']成立，则推入一个[''I1'',''I2'']，并且先不计算它的频繁度
else:
continue
#pruning setp
if self.has_infrequent_subset(c,k):
continue
else:
Ck.append(c) #候选项集集合,还没有计算频繁度，先把各种组合扔进去
return Ck
def do(self):
L_last = self.find_frequent_1_itemsets()
L = L_last
i = 0
while L_last != []: #只要本组频繁项集不空则继续循环
Ck = self.apriori_gen(L_last) #候选项集集合(仅仅是各种排列组合，没筛选频繁度)推入Ck中
FreqDic = {}
for event in self.data: #遍历原始Data数据
#get all suported subsets
for c in Ck: #遍历候选的所有项集集合
if set(c) <= set(self.data[event]):#set()表示无序不重复元素集,如果c元素集是原始数据这个集合的子集
if tuple(c) in FreqDic: #如果元组c在字典中
FreqDic[tuple(c)]+=1 #这个元组的值+1，即又出现了一次
else:
FreqDic[tuple(c)]=1
print FreqDic #将候选项集集合，以及出现的次数，以字典的形式打印出来，到这里时仍然没计算频繁度
Lk = [] #满足频繁度集合的列表
for c in FreqDic: #遍历字典里的所有候选集合
if FreqDic[c] > self.min_sup_val: #如果大于设定的频繁度
Lk.append(list(c)) #将该列表推入列表Lk中
L_last = Lk #将该列表定义为满足频繁度的最后一组列表
L += Lk #最终结果的列表为L
return L
#******Test******
Data = {''T100'':[''I1'',''I2'',''I5''],''T200'':[''I2'',''I4''],''T300'':[''I2'',''I3''],''T400'':[''I1'',''T500'':[''I1'',''T600'':[''I2'',''T700'':[''I1'',''T800'':[''I1'',''I3'',''T900'':[''I1'',''I3'']}
a=Apriori(dataDic=Data)
print a.do() 后面还有对该算法的优化算法，能力有限，还没来得及看，活几天研究一下，有时间我会放上导师留下的“变态延展问题”
(源码)关于A->B*->D的时间序列频繁模式挖掘的思考 1.26更新
这个算法是导师课题的一个部分，感觉对时间序列频繁模式挖掘的学习还是很有帮助的，在博客里做一下记录。
首先要明确一下什么是A->B*->D模式：
A->B->D表示在A事件发生后又发生了B事件，又发生了D事件，由于我应用在社交网络，那么这三种事件就可以表示为三个人在某微博下的留言。
什么是A->B*->D模式？这里的*表示不管在A与D时间发生的时间点当中有多少个B事件发生，都可以这个标记这种模式，比如:
A->B->B->D或A->B->B->B->D都可以写成A->B*->D的形式，但看A->B->D和A->B->B->D和A->B->B->B->D可能每个都不是频繁的，但如果把他们看成一种形式A->B*->D就有可能是频繁的，我所要解决的就是这个问题。
这里有个前提条件，就是我所研究的背景是社交网络，也就是说每个事件发生的时间点一定不可能一样，也就是说，每个事件之间一定有先后的发生顺序，综上所述，我只考虑时间序列的频繁模式挖掘，而不考虑传统的频繁模式挖掘。
程序流程图：
本算法里面的字母理论上应该是社交网络中的各个事件，目前正在搜索合适的数据集，将其封装成一个类就可以像算法里的字母一样表示了。数据集的搜索目前还在进行中。
1.26更新 ver1.1
增加多重序列识别功能：ABDBDF -> A(BD)F
增加多重序列内存在的多重序列识别功能 :
ABBDDBBDDF -> A(B)(D)(B)(D)F -> A(BD)F
增加多重序列内重复序列识别功能:
ABBBBF有这样一种形式 A(BB)F 可化为 A(B)F，目的是为了避免重复
源代码：（数据集是自己造的，比较具有代表性的小数据，肉眼可以识别出本算法在运行上没有问题）
#coding:utf-8
__author__ = ''ChiXu_15s103144_HIT''
import copy
import sys
#----------------------------------------------------------#
# 计算Frequent_1 #
#----------------------------------------------------------#
def freq1(dataSet,freq_num):
freq_1 = [] ; Ele = []
for i in range(len(dataSet)):
SID = splitToAlphabet(dataSet[i])
setSID = list(set(SID))
Ele += setSID
setEle = list(set(Ele))
for item in setEle:
if Ele.count(item) >= freq_num:
freq_1.append(item)
print(''the Frequent_1 elements are:%s'' %freq_1)
return freq_1
#----------------------------------------------------------#
# 计算Frequent_more #
#----------------------------------------------------------#
def freq_more(dataSet,freq_num,freq_1):
x = []
queue = []
queueBrief = []
for a in freq_1:
x.append(a)
queue.append(x)# queue = [[''A''],[''B''],[''D''],[''F'']]
x = []
while queue != []: # 先处理多重形式
queueDemo = extendMember(queue,freq_1) # 扩展queue成员 example:[[''A'',''A''],[''A'',''B''],''D''],[''B'',[''D'',''D'']]
queue = []
for item in queueDemo:
itemFreqNum = frequentNum(dataSet,item)
if itemFreqNum > 0: # 只要出现过
briefItemList = toBriefItem(item) # item的缩略形式 example: [''D(BD)'',''(BB)D'']
if briefItemList != []: # 如果有缩略形式的话
for BriefItem in briefItemList:
queueBrief.append(BriefItem)
queue.append(item)
else: # 如果没有缩略形式
queue.append(item)
print queueBrief
# 下面处理非多重形式
for a in freq_1:
x.append(a)
queue.append(x)# queue = [[''A''],[''F'']]
x = []
# queueBrief去括号:
queueBriefNoBrancket = []
for briefString in queueBrief: # briefString: ''D(BD)''
briefAlphabet = splitToAlphabet(briefString) # briefAlphabet: [''D'',''('',''B'',''D'','')'']
while ''('' in briefAlphabet:
briefAlphabet.remove(''('')
briefAlphabet.remove('')'')
# 至此 briefAlphabet: [''D'',''D'']
queueBriefNoBrancket.append(combinToString(briefAlphabet))
while queue != []:
queueDemo = extendMember(queue,freq_1)
queue = []
for item in queueDemo: # item: [''A'',''B'']
itemFreqNum = frequentNum(dataSet,item)
itemBrief = toBriefItem(item) # itemBiref:有缩略形式:[''A(B)''] 没有:[]
if itemFreqNum >= freq_num or (itemBrief!=[] and queueBrief.count(itemBrief) >= freq_num):
print(''频繁的形式: %s'' %item)
queue.append(item)
#----------------------------------------------------------#
# 将queue成员进行扩展 #
#----------------------------------------------------------#
def extendMember(queue,freq_1): #queueDemo
queueDemo = []
for item in queue:
itemString = combinToString(item)
for alphabet in freq_1:
String = itemString + alphabet
queueDemo.append(splitToAlphabet(String))
#print(queueDemo)
return queueDemo
#----------------------------------------------------------#
# 计算item频度 ##
#----------------------------------------------------------#
def frequentNum(dataSet,item): #freq_num
# item: [''A'',''D'']
flag = 0
alphabetAppearTimes = 0
freq_num = 0
for SID in dataSet:
SIDalphabetList = splitToAlphabet(SID) # 将该SID分解为字母列表
for alphabet in item:
if alphabet in SIDalphabetList: # 该字母存在于SID中
while flag <= len(SIDalphabetList)-1:
if SIDalphabetList[flag] == alphabet:
flag += 1
alphabetAppearTimes += 1 # 记录有几个item字母在该SID中出现过
break
else:
flag += 1
else:
break # item中某个字母在列表中没有出现则不用检查SID了
if alphabetAppearTimes == len(item): # 这几个字母都在这个SID中出现了
freq_num += 1
flag = 0
alphabetAppearTimes = 0
return freq_num
#----------------------------------------------------------#
# ABBD -> A(B)D #
#----------------------------------------------------------#
def toBriefItem(item): #briefItem
# item = [''A'',''F''] 每一个扩展的成员
briefItem = [] # return
queue = [] # 待鉴别列表
briefItemDemo = [] # example: [''D(B)DBDBD'',''DB(BD)'',''DBB(DB)D'',''(DB)D'',''D(BD)'']
item.append('''')
item.insert(0,'''')
queue.append(item)
while queue != []:
lenth = 1 # 识别字符串的长度
alphabetList = queue[0]
alphabetListLenth = len(alphabetList) # 不算首末的空位
del queue[0] # 删除第一个待鉴别成员
while lenth <= (alphabetListLenth)/2: # 以lenth长的串为一组,寻找相邻组有没有相重的
flag = 0
for i in range(lenth):
groupNewDemo = []
group = makeGroup(alphabetList,lenth,flag) # 进行分组,比如两两一组或者三三一组,flag是分组的起始位置
longestNum = longestItemNum(group,lenth) # 看两两一组或者三三一组的组数有多少
if longestNum == 1:
break
else:
groupNew = copy.deepcopy(group)
j = flag+1
while j<len(groupNew)-1:
if groupNew[j]==groupNew[j+1] and groupNew[j]!=groupNew[j-1] and len(groupNew[j])==len(groupNew[j+1])==lenth: # 添加左括号
groupNew.insert(j,''('')
j += 2
elif groupNew[j]!=groupNew[j+1] and groupNew[j]==groupNew[j-1] and len(groupNew[j])==len(groupNew[j-1])==lenth: # 添加右括号
groupNew.insert(j+1,'')'')
j += 2
else:
j += 1
# example: groupNew = ['''',''A'',''BD'','')'',''F'','''']
sign = 1
if ''('' in groupNew:
while sign<len(groupNew)-1: # 只要groupNew里面还有未处理的对子
if groupNew[sign]!=''('':
groupNewDemo.append(groupNew[sign])
sign += 1
else: # 遇到了''(''
groupNewDemo.append(''('')
groupNew.remove(''('')
groupNewDemo.append(groupNew[sign])
groupNewDemo.append('')'')
positionBracket = groupNew.index('')'')
groupNew.remove('')'')
sign = positionBracket
for i in range(sign,len(groupNew)-1):
groupNewDemo.append(groupNew[sign])
# groupNewDemo = [''A'',''F'']
#下面判断括号里面有没有重复的形式,反例: ''A(BCBC)D'' 或 ''A(BB)D''
while ''('' in groupNewDemo:
positionBrancketLeft = groupNewDemo.index(''('')
# ''BB'' -> [''B'',''B'']
checkedString = splitToAlphabet(groupNewDemo[positionBrancketLeft+1])
if toBriefItem(checkedString) != []: # 遇到''BB''或者''BDBD''这样的形式的话
break
else:
sys.stdout.write(''item:%s -> '' %combinToString(item)) # print: ABDBDF
print(combinToString(groupNewDemo)) # print: A(BD)F
briefItemDemo.append(combinToString(groupNewDemo))
groupNewDemo.remove(''('') # 去除从左到右第一个''(''
groupNewDemo.remove('')'') # 去除从左到右第一个'')''
# 至此括号里的对子都只缩到一个了
x = []
k = 0
if ''('' in groupNewDemo:
while k < len(groupNewDemo):
if groupNewDemo[k]!=''('' and groupNewDemo[k]!='')'':
x.append(groupNewDemo[k])
k = k+1
else:
k = k+1
#briefItem.append(x)
x.append('''')
x.insert(0,'''')
queue.append(x) # 增加一个鉴别成员
flag += 1
lenth += 1
# 去掉list中首末的''''
for i in range(len(briefItem)):
briefItem[i].pop(0)
briefItem[i].pop(-1)
item.pop(-1)
item.pop(0)
#下面选出最短字符串的,带括号的字串
i = len(briefItemDemo) - 1
while i >= 0:
if len(briefItemDemo[i]) > len(briefItemDemo[-1]):
break
else:
briefItem.append(briefItemDemo[i])
i -= 1
return briefItem
# example: briefItem:[''D(BD)'',''(DB)D'']
#----------------------------------------------------------#
# 计算item在全转成大写的特殊列表中存在的次数 #
#----------------------------------------------------------#
def changeSpecialNum(changeSpecial,item): #appearTimes
if item not in changeSpecial:
return 0
else:
appearTimes = changeSpecial.count(item)
return appearTimes
#----------------------------------------------------------#
# 将字符串分解为字母 ##
#----------------------------------------------------------#
def splitToAlphabet(item): #alphabetList
alphabetList = []
for i in range(len(item)):
alphabetList.append(item[i])
return alphabetList
#----------------------------------------------------------#
# 将字母合成成字符串 ##
#----------------------------------------------------------#
def combinToString(briefItemList): #briefItem
briefItem = ''''
for alphabet in briefItemList:
briefItem += alphabet
return briefItem
#----------------------------------------------------------#
# 将字符串进行分组 # alphabetList=['''','''']
#----------------------------------------------------------#
def makeGroup(alphabetList,num,flag): # group num:几几一组
alphabet = ''''
alphabetListNew = []
#alphabetList = [''A'',''D'']
if num == 1:
#print(alphabetList)
return alphabetList
else:
alphabetList.pop(0)
alphabetList.pop(-1) # 把首末的空位去掉
for i in range(flag):
alphabetListNew.append(alphabetList[i])
while len(alphabetList) - flag >= num:
for i in range(num):
alphabet += alphabetList[flag+i]
alphabetListNew.append(alphabet)
flag = flag + num # 标志位后移num
alphabet = ''''
for i in range(flag,len(alphabetList)): # 把剩下几个字母扔进去
alphabetListNew.append(alphabetList[i])
alphabetListNew.insert(0,'''')
alphabetListNew.append('''')
# alphabetListNew = ['''',''AB'',''BB'','''']
#print(alphabetListNew)
alphabetList.append('''')
alphabetList.insert(0,'''')
return alphabetListNew
#----------------------------------------------------------#
# 两两一组或三三一组的组数有多少 #
#----------------------------------------------------------#
def longestItemNum(group,lenth):
longest = 0
itemNum = 0
if lenth == 1:
return len(group) - 2
else:
for item in group:
if len(item) == longest:
itemNum += 1
elif len(item) > longest:
itemNum = 1
longest = len(item)
else:
continue
return itemNum
#main
#dataSet = [''ABDBD'',''FDDDA'',''BDBDD'',''ABDFF'',''BDDBFBD'']
dataSet = [''ABD'',''ABBD'',''ABBBD'']
freq_1 = freq1(dataSet,2)
freq_more(dataSet,2,freq_1)
#makeGroup(['''',''''],3,0)
#toBriefItem([''A'',''A''])
#longestItemNum(['''',''BDD'',''BBD'',''ABC'',3)
#extendMember([[''A''],[''F'']],''F''])
6.数据挖掘概念笔记——挖掘频繁模式、关联和相关性术
6.数据挖掘概念笔记——挖掘频繁模式、关联和相关性术
欢迎转载，转载请标明出处：http://www.voidcn.com/article/p-usinzjzh-qp.html
频繁模式挖掘搜索给定数据集中反复出现的联系。
有哪些频繁项集挖掘方法：
答：类Apriori算法；基于频繁模式增长的算法；使用垂直数据格式的算法。
什么是Apriori算法？
答：是为布尔关联规则挖掘频繁项集的原创性算法。
所有强关联规则都是有趣的么？
答：非也，应当用模式评估度量来扩展支持度-置信度框架。
关于FP-Growth序列频繁模式挖掘和fp growth算法发现频繁项目集的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于(原创)时间戳概念的频繁模式挖掘：GSP算法、SPADE算法、(原创)频繁模式挖掘Apriori算法详解、(源码)关于A->B*->D的时间序列频繁模式挖掘的思考 1.26更新、6.数据挖掘概念笔记——挖掘频繁模式、关联和相关性术等相关知识的信息别忘了在本站进行查找喔。
本文标签：
