欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

机器学习实战(10) FP-growth 基于python3

程序员文章站 2024-03-24 11:46:28
...


记录下FP-growth,由于赶着把正本机器学习看完,所以好多没来得及写笔记,这里先把今天看的FP-growth补上。

fp-growth理论

FP树描述
1.FP树中,一个元素可以出现多次,FP会存储项集的出现频率
2.存在相同元素的集合会共享树的一部分
3.当集合完全不同时,树才会分叉
FP构建
1.首先构建FP树,对所有元素项出现次数进行计数
2.去掉不满足最小支持度的元素项,读入每个项集并将其假如一条已经存在的路径中
3.每个事务是一个元素集合,我们会将每个集合基于绝对出现频率排序
首先构建一个树的子节点的类,这里主要的作用有两个:一是记录出现的频数,当已有该元素时,直接增加计数,当没有该节点时,创建一个新节点;二是header的指针链接,在nodelink会保存下一个相同元素的树节点。这两点至关重要

fp-growth code

class treenode():
    def __init__(self,value,num,parnode):
        self.name = value
        self.cnt = num
        self.nodelink = None
        self.parent = parnode
        self.children = {}
    def inc(self,num):
        self.cnt += num
    def disp(self,ind=1):#ind控制打印间隔
        print(' '*ind,self.name,' ', self.cnt)#*ind打印多次空格
        for child in self.children.values():
            child.disp(ind+1)

接下来是创建树的主代码,这里不难。

def crtree(data,minsup=1):
    header = {}
    for trans in data:
        for item in trans:
            header[item] = header.get(item,0) + data[trans]#计算元素出现次数
    for k in list(header.keys()):#dictionary changed size during iteration
        if header[k]<minsup:
            del(header[k])
    freqset = set(header.keys())
    if len(freqset)==0:
        return None,None
    for k in header:
        header[k] = [header[k],None]
    rettree = treenode('Null Set',1,None)
    #header = {'z': [5, None], 'r': [3, None], 'y': [3, None], 'x': [4, None], 's': [3, None], 't': [3, None]}
    for tran,count in data.items():
        localD={}
        for item in tran:
            if item in freqset:
                localD[item] = header[item][0]#{item:'频数'}
        if len(localD)>0:
            orderitem = [v[0] for v in sorted(localD.items(),key=lambda p: p[1],reverse=True)]#排序后的item列表
            #print(orderitem)
            updatetree(orderitem,rettree,header,count)
    return rettree,header

crtree函数有两个重要的辅助函数,updatetree输入一个排序的元素列表、父节点、header、count(集合出现的次数)来更新树。updatetree通过节点的nodelink不断调用到一个元素的最新nodelink,然后更新为最新建立的一个树节点。

def updatetree(items,intree,header,count):#items-orderitem  intree-rettree  header-
    print(items)
    if items[0] in intree.children:#如果已有该child,添加计数
        intree.children[items[0]].inc(count)#计算加tree.count + count,每一个元素一棵树
    else:
        intree.children[items[0]] = treenode(items[0],count,intree)#创建一个树的子节点
        if header[items[0]][1] == None:
            header[items[0]][1] = intree.children[items[0]]#更新该元素的头指针表
        else:
            updateheader(header[items[0]][1],intree.children[items[0]])
            #header不会迭代下去,header只记录第一个元素的树的子节点,通过该子节点迭代link为空时,则指定它的link指向下一个该元素的子节点
    if len(items)>1:
        updatetree(items[1::],intree.children[items[0]],header,count)
def updateheader(nodetotest,targetnode):#nodetotest-header[item[0]][1]  targetnode-intree.children[item[0]]
    while (nodetotest.nodelink != None):#nodetotest.link指向下一个相同元素的树,循环到链表末尾
        nodetotest = nodetotest.nodelink
    nodetotest.nodelink = targetnode  

接下来导入数据集,这里我们自己写入一个数据集,然后对数据做预处理,输出结果如下,这里的initset函数是我自己写的,没有做过多的测试,对于一次出现的集合是没有问题,感觉原书的代码太没有诚意啦。

def loadsimdat():
    simdat = [['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 simdat
#补充个createinitset数据集预处理程序,没有具体测试
def initset(data):
    dataset = {}
    cnt = 1
    datafro = []
    for k in data:
        datafro.append(frozenset(k))#frozenset会自动排列元素顺序      
    for k in datafro:
        if k in dataset.keys():
            continue
        for j in datafro[datafro.index(k)+1:]:
            if k==j: 
                cnt += 1
        dataset[k] = cnt
    return dataset
output:
{frozenset({'z'}): 1,
 frozenset({'h', 'j', 'p', 'r', 'z'}): 1,
 frozenset({'s', 't', 'u', 'v', 'w', 'x', 'y', 'z'}): 1,
 frozenset({'n', 'o', 'r', 's', 'x'}): 1,
 frozenset({'p', 'q', 'r', 't', 'x', 'y', 'z'}): 1,
 frozenset({'e', 'm', 'q', 's', 't', 'x', 'y', 'z'}): 1}

导入数据,数据预处理,查看结果

data = loadsimdat()
dataset = initset(data)
fptree,headertab = crtree(dataset,3)
fptree.disp()
output:
  Null Set   1
   z   5
    r   1
    x   3
     y   3
      s   1
       t   1
      r   1
       t   1
      t   1
       s   1
   x   1
    r   1
     s   1

会发现跟其他的结果有点出入,原因在第二个t 1和s 1处没有跟y 3合并,这里我们打印下处理的流程。s和t的出现次数是相同的,所以出现两个集合的排序有点差别。

header = {'z': [5, None], 'r': [3, None], 'y': [3, None], 'x': [4, None], 's': [3, None], 't': [3, None]}
['z', 'r']
['r']
['z', 'x', 'y', 's', 't']
['x', 'y', 's', 't']
['y', 's', 't']
['s', 't']
['t']
['z']
['x', 'r', 's']
['r', 's']
['s']
['z', 'x', 'y', 'r', 't']
['x', 'y', 'r', 't']
['y', 'r', 't']
['r', 't']
['t']
['z', 'x', 'y', 't', 's']
['x', 'y', 't', 's']
['y', 't', 's']
['t', 's']
['s']

我们这里把orderitem加一个排序条件就可以啦,结果如下:

orderitem = [v[0] for v in sorted(localD.items(),key=lambda p: (p[1],p[0]),reverse=True)]
output:
  Null Set   1
   z   5
    r   1
    x   3
     y   3
      t   3
       s   2
       r   1
   x   1
    s   1
     r   1

构建频繁项集

从一颗FP树种挖掘频繁项集
1.从FP树中获得条件模式基
2.利用条件模式基,构建一个条件FP树
3.重复步骤1和2,直到树包含一个元素项为止
首先构建两个辅助函数来获取条件模式基,也就是获取元素的prepath。首先通过header开始,通过nodelink连接到最后一个元素,对于每一个元素通过ascendtree获取整个前缀路径。

def ascendtree(leafnode,prepath):#prepath前缀路径
    if leafnode.parent != None:
        prepath.append(leafnode.name)
        ascendtree(leafnode.parent,prepath)#提取leafnode
def findprepath(basepat,treenode):
    condpats = {}
    while treenode != None:#从header里元素第一次出现时开始迭代,直到最后一个,终止条件是treenode.nodelink is None
        prepath = []
        ascendtree(treenode,prepath)
        if len(prepath)>1:
            condpats[frozenset(prepath[1:])] = treenode.cnt
        treenode = treenode.nodelink
    return condpats

然后通过递归查找频繁项集,这里应该是FP-growth最难理解的地方,我们以上述的树为例,首先会遍历header中的元素,对于每个元素我们以y为例,通过获取y的前缀路径,然后创建前缀路径的树,会删除与y不频繁的元素,我们只需要将剩下的元素组合,组合的方式就是通过递归调用该minetree函数,通过newfrest保存集合,freqlist保存当时状态的集合。当递归到myhead为None时停止,我们可以理解为该元素的前缀路径为空,也就是递归到了根节点。

def minetree(intree,headertab,minsup,prefix,freqlist):#prefix=set([]) freqlist=[]
    bigl = [v[0] for v in sorted(headertab.items(),key=lambda p:p[1][0])]#元素排序并组成列表['r','s','t','y','x','z']
    for basepat in bigl:#basepat 元素例如'y'
        print(basepat)
        newfreqset = prefix.copy()#初始为set()
        newfreqset.add(basepat)#set('y')
        freqlist.append(newfreqset)#[set('y')]
        condpatbases = findprepath(basepat,headertab[basepat][1])#获取'y'前缀路径{frozenset({'x', 'z'}): 3}
        mycondtree,myhead = crtree(condpatbases,minsup)#创建’r‘前缀路径的树
        print(myhead)
        if myhead != None:#这个判断条件有点难以理解,这里其实是看是否还有prepath,没有prepath就不需要递归下去,如果有prepath继续递归
            minetree(mycondtree,myhead,minsup,newfreqset,freqlist)
            #minetree(tree,{'x': [3, treenode], 'z': [3, treenode]},3,set('y'),[set('y')])
    return freqlist

然后执行函数,得到频繁项集

freqlist = []
minetree(fptree,headertab,3,set([]),freqlist)

到这里,整个FP-growth代码就结束啦,不得不说,FP-growth算法是本书学到现在遇到最难的部分了,还需要多看看。
接下来测试一下新闻网站点击流的数据挖掘。

with open(filename) as fr:
    parseddat = [line.split() for line in fr.readlines()]
initset = createinitset(parseddat)
myfptree,myheadertab = crtree(initset,100000)
myfreqlist = []
minetree(myfptree,myheadertab,100000,set([]),myfreqlist)
output:
[{'1'},
 {'1', '6'},
 {'3'},
 {'11', '3'},
 {'11', '3', '6'},
 {'3', '6'},
 {'11'},
 {'11', '6'},
 {'6'}]

未完待续…