机器学习day17 机器学习实战FP-growth挖掘频繁项集

作者:金牛区福生殡葬服务部 来源:www.cdfsbz.com 发布时间:2017-09-07 13:10:21
机器学习day17 机器学习实战FP-growth挖掘频繁项集

这两天进行了fp-growth的学习,这块知识确实很难理解,书上只是搪塞了这一块的细节,并且作者还有一个疏忽,导致一个很大的错误出现,这在后面会提到。这让读者很是费解,网上的资料或者博客也并没有介绍实现的细节,大多复制粘贴,这两天一直在研究这个算法,这篇文章可能写的不是很清楚,但可能是网上目前介绍fp-growth思想的最好的文章了,如果看了其他fp-growth的介绍没有看懂可以看下,建议之前有对fp-growth的简单理解,否则可能看不懂,表达能力太差了。

fp-growth算法是韩佳炜在2000年提出的频繁项集挖掘算法,前面我们介绍了Apriori挖掘频繁项集并且进行关联分析,这次的fp-growth和Apriori选择频繁集有点类似的地方,但是本质和Apriori完全不一样。

先写一下核心思想,再写一下实现的细节,最后有一个新闻挖掘的小实例。

fp-growth的核心思想:

假设我们的找出了频繁集,我们采取一种将频繁集排序的方法,把频繁集中出现最少的放在最后一位,按照最后一位划分多个小的频繁集合,因为这样按照最后一位划分的几个频繁集合因为最后一位不同,没有重合,互不冲突。这样在每一次划分频繁集的时候会把频繁集分为不重合的几个集合,并且可以在最后一项或几项为后缀的fp-tree上递归进行上述的步骤,直到遇到停止条件。

停止条件1:条件模式基组成的fp-tree都不频繁,头指针表头headertable为None。

停止条件2:条件模式基没有元素。

通俗解释:和分班级一样,1班和2班因为班级不同永远不会冲突,然后我们在班级里在进行类似于分班级的分组,就是上述中的递归,在分组中加入班级号,就是上述中的以前几项为后缀,递归进行,直到没有进行进一步分组的条件,即停止条件。

FPGrowth是一种比Apriori更高效的频繁项挖掘方法,它只需要扫描项目表2次。其中第1次扫描获得当个项目的频率,去掉不符合支持度要求的项,并对剩下的项排序。第2遍扫描是建立一颗FP-Tree,后面递归还需要对每个小的项目表扫描但是规模小忽略不计,弥补了Apriori的缺点。

fp-grow的细节实现:

step1:

读取简单数据并且格式化:

数据为书中的简单数据:

#创建简单数据集 def loadDataSet(): data = [['r', 'z', 'h', 'j', 'p'], ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'], ['z'], ['r', 'x', 'n', 'o', 's'], ['y', 'r', 'x', 'z', 'q', 't', 'p'], ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']] return data #整理数据集格式 def initDataSet(dataset): res = {} for line in dataset: res[frozenset(line)] = 1 return res

\


step2:

定义树的节点:

#FP-tree的定义 class treeNode: def __init__(self, namevalue, countvalue, pnode): self.name = namevalue self.count = countvalue self.parent = pnode self.children = {} self.nextlink = None def inc(self, number): self.count += number def show(self, ind = 1): print ' ' * ind, self.name, ' ', self.count for i in self.children.values(): i.show(ind + 1) step3:

创建fp-tree:

里面作者有个错误,在注释中。

#创建fp-tree def createTree(data, minsupport = 1): headertable = {} for line in data: for item in line: headertable[item] = headertable.get(item, 0) + data[line] for i in headertable.keys(): if headertable[i] < minsupport: del(headertable[i]) freqset = set(headertable.keys()) #如果没有频繁项集返回None if len(freqset) == 0: return None, None #初始化头指针表 for k in headertable.keys(): headertable[k] = [headertable[k], None] tree = treeNode('None set', 1, None) for line, count in data.items(): temp = {} for i in line: if i in freqset: temp[i] = headertable[i][0] newline = [v[0] for v in sorted(temp.items(), key = operator.itemgetter(1), \ reverse = True)] #书中疏忽了这一点,应判断一下newline是否为空 if len(newline) > 0: updateTree(tree, headertable, newline, count) return tree, headertable 创建完的树为:

\

step4:

递归更新树的信息,递归更新headertable头指针表:

#更新树的信息 def updateTree(tree, headertable, newline, count): if newline[0] in tree.children: tree.children[newline[0]].inc(count) else: tempnode = treeNode(newline[0], count, tree) tree.children[newline[0]] = tempnode if headertable[newline[0]][1] == None: headertable[newline[0]][1] = tempnode else: updateHeaderTable(headertable, tempnode, newline[0]) if len(newline) > 1: updateTree(tree.children[newline[0]], headertable, newline[1 : ], count) #更新头指针信息 def updateHeaderTable(headertable, n, x): t = headertable[x][1] while (t.nextlink != None): t = t.nextlink t.nextlink = n
step5:

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:荆门网站建设 http://jingmen.45qun.com

  • 上一篇:Python之函数作为返回值、闭包
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 金牛区福生殡葬服务部 ALL RIGHTS RESERVED.
    购买cdfsbz.com友情链接、项目合作请联系客服QQ:2500-38-100 邮箱:2500-38-100#QQ.com(#换@)
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100