首页 科技正文

武汉新闻联播:嫌弃Apriori算法太慢?使用FP-growth算法让你的数据挖掘快到飞起

admin 科技 2020-05-15 32 0

本文始发于小我私家民众号:TechFlow,原创不易,求个关注


今天是机械学习专题的第20篇文章,我们来看看FP-growth算法。

这个算法挺冷门的,至少比Apriori算法冷门。许多数据挖掘的课本还会提一提Apriori,然则提到FP-growth的相对要少许多。缘故原由也简朴,由于从功效的角度上来说,FP-growth和Apriori基本一样,相当于Apriori的性能优化版本。

但不得不说有时刻优化是一件很尴尬的事,由于优化意味着性能要求很高。然则反过来说,对于性能有着更高要求的应用场景,无论是企业也好,照样学术研究也罢,现在早就有了更好的选择,完全可以用更壮大的算法和模子,没需要用这么个古老算法的优化版。对于那些性能要求不高的场景,简朴的Apriori也就够了,优化的需要也不是很大。

然则不管这个算法运气若何,至少从原理和思绪理念上来说的确有为人称道的部门。下面我们就来看看它的详细原理吧。

FP-growth与FP-tree

FP-growth的焦点价值在于加速,在之前先容的Apriori算法当中,我们每一次从候选集当中筛选出频仍项集的时刻,都需要扫描一遍全量的数据库来盘算支持度,显然这个开销是很大的,尤其是我们数据量很大的时刻。

FP-growth的精髓是构建一棵FP-tree,它只会扫描完整的数据集两次,因此整体运行的速率显然会比Apriori快得多。之以是能做到这么快,是由于FP-growth算法对于数据的挖掘并不是针对全量数据集的,而只针对FP-tree上的数据,因此这样可以省略掉很大一部门数据,从而节省下许多盘算资源。

从这里我们可以看出,FP-tree是整个算法的精髓。在我们先容整个树的构建方式以及一些细节之前,我们先来看下FP这两个字母的寄义。信赖许多同砚从一最先的时刻就最先疑惑了,实在FP这两个字母是frequent pattern的缩写,翻译过来是频仍模式,实在也可以明了成频仍项,说白了,FP-tree这棵树上只会存储频仍项的数据,我们每次挖掘频仍项集和关联规则都是基于FP-tree,这也就过滤了不频仍的数据。

这是一棵天生好的FP-tree,我们先来看一下它的样子,再来详细解读其中的细节和原理。

头指针表

上图这个结构初看会以为很杂乱,完全不知道应该怎么明了。这是很正常的,但若是我们把上图拆开,可以分成两个部门,左边的部门是一个链表,右边是一棵树。只不过左边的链表指到了右边的树上,以是整体看起来有些庞大。

我们先忽略右侧的树的部门,以及指针表和树之间关联的指针,单纯地来看一下左侧的头指针表。仅仅看这一部门就简朴多了,它实在是一个单频仍项的聚集。

前面我们提到我们在使用FP-growth算法的历程当中,一共只需要遍历两次数据集。其中第一次遍历数据集就在这里,我们首先遍历了一遍数据集,求出了所有元素泛起的次数。然后凭据阈值过滤掉不频仍的元素,保留下来的效果就是单个频仍项的聚集。

这里的逻辑异常简朴,只有两件事,第一件事是统计每个单独的项泛起的次数,第二件事是凭据阈值将不频仍的项过滤掉。

def filter_unfreq_items(dataset, min_freq):
    data_dict = defaultdict(int)
    # 统计每一项泛起的次数
    for trans in dataset:
        for item in trans:
            data_dict[item] += 1
        
    # 凭据阈值过滤
    ret = {}
    for k, v in data_dict.items():
        if v >= min_freq:
            ret[k] = v
    return ret

通过这个方式,我们就天生了头指针内外的数据。之后我们要在确立FP-tree的历程当中将这份数据转化成链表,也就是左边的头指针表。虽然我们还不领会建树的原理,但至少我们可以把dict转化成指针表,这个逻辑异常简朴,说白了我们只需要在dict的value当中增添一个引用即可。

def transform_to_header_table(data_dict):
    return {k: [v, None] for k, v in data_dict.items()}

这里的None要存的就是链表下一个位置的引用,只是现在我们只有链表头,以是所有设置为None。

确立FP-tree

我们有了头指针表的数据,也就是高频的单个元素的数据之后,显然要将它用起来。很明显,我们可以用它来过滤整个数据集,过滤掉其中低频的元素。

实在本质上来说FP-tree的构建历程,实在就是一个将过滤之后的效果插入到树上的历程。后面的事情后面再说,我们首先来看过滤。

单纯的过滤固然异常简朴,我们只需要判断数据集中的元素是否在头指针表中泛起即可。然则不仅如此,由于我们之后想要将它插入到树中。这里行使了huffman树的头脑,我们希望频次越高的元素存放的位置距离根节点越近。频次越低的离根节点越远,从而优化我们查询的效率。要做到这点,需要我们对数据举行排序。

我们来实现这部门内容,这部门内容分为两块,第一块是凭据头指针表举行过滤,第二块是凭据头指针表中泛起的频次举行排序。

def rank_by_header(data, header_dict):
    rank_dict = {}
    for item in data:
        # 若是元素是高频的则保留,否则则抛弃
        if item in header_dict:
            rank_dict[item] = header_dict[item]
    
    # 对元素根据整体泛起的频次排序
    item_list = sorted(rank_dict.items(), lambda x: x[1], reverse=True)
    return [i[0] for i in item_list]

有了这份数据之后,我们距离建树只有一步之遥。FP-tree的构建适才也提到过,异常简朴粗暴,就是将元素根据泛起的频次举行排序之后从树根最先依次插入。在插入的历程当中,对路径上的节点举行更新,我这么说一定很费解,然则看一张图就一定明了了:

一最先的时刻树为空,什么也没有,接着插入第一条数据{r, z}。由于z泛起的次数大于r,以是先插入z再插入r,之后插入了一条{z,x,y,s,t},同样是根据整体泛起的频次排序的。由于z已经插入了,以是我们将它泛起的次数更新成2,之后发现没有重复的元素,那么就构建出一条新的分支。

本质上来说就是根据频次排序之后,由浅到深依次插入,若是相同的元素之前已经泛起过了,那么就更新它泛起的次数。

这个逻辑应该很好明了,在我们实现逻辑之前,我们先来建立树节点的类。

class Node:
    def __init__(self, item, freq, father):
        self.item = item
        self.freq = freq
        # 父节点指针
        self.father = father
        # 界说指针
        self.ptr = None
        # 孩子节点,用dict存储,利便凭据item查找
        self.children = {}
    
    # 更新频次
    def update_freq(self):
        self.freq += 1

    # 新增孩子
    def add_child(self, node):
        self.children[node.item] = node

这个类我们只需要看代码就好了,应该完全没有难度,固然若是你愿意你也可以给它加上一个可视化方式用来debug。但老实说树结构单凭打印很难显示得很清晰,以是我就不加了。

树节点的界说写好了之后,接下来就到了最主要的实现更新FP-tree的环节了。实在若是对上面的逻辑都明了了,这部门代码也异常简朴,我们只需要套用适才的代码将天生的数据根据顺序插入进树上即可。

这种在树上传入一个序列依次插入的做法异常常见,在许多数据结构当中有类似的操作,最经典的就是Trie树了。若是你学过,会发现这个插入操作真的和Trie险些一模一样,若是你没学过,也没有关系,这也不难明了。

def create_FP_tree(dataset, min_freq=3):
    header_dict = filter_unfreq_items(dataset, min_freq)
    root = Node('Null', 0, None)
    for data in dataset:
        # 凭据整体泛起次数举行排序
        item_list = rank_by_header(data, header_dict)
        print(item_list)
        head = root
        # 根据排序顺序依次往树上插入
        for item in item_list:
            if item in head.children:
                head = head.children[item]
            else:
                new_node = Node(item, 0, head)
                head.add_child(new_node)
                head = new_node
            head.update_freq()
    return root

更新头指针表

FP-tree已经完成了,接下来我们要把更新头指针表的逻辑加上,使得对于每一个项来说,我们都可以凭据头指针表找到这个元素在FP-tree上所有的位置。

我们仔细观察一下上面的那张图,我们选择其中的一条链路举行高亮:

从上图当中我们会发现,头指针表的作用就是确立一个链表,将元素所有泛起的位置所有串联起来

那么什么情况下我们需要向这个链表当中添加值呢?

稍微剖析一下就会发现,实在就是我们在树上建立新节点的时刻。想通了这点就很简朴了,我们只需要在上面的代码当中增添几行,使得在树上建立新的节点的时刻,用同样的值更新一下头指针链表。

def create_FP_tree(dataset, min_freq=3):
    header_dict = filter_unfreq_items(dataset, min_freq)
    root = Node('Null', 0, None)
    for data in dataset:
        # 凭据整体泛起次数举行排序
        item_list = rank_by_header(data, header_dict)
        print(item_list)
        head = root
        # 根据排序顺序依次往树上插入
        for item in item_list:
            if item in head.children:
                head = head.children[item]
            else:
                new_node = Node(item, 0, head)
                head.add_child(new_node)
                # 头指针指向的位置为空,那么我们直接让头指针指向当前位置
                if head_table[item][1] is None:
                    head_table[item][1] = new_node
                else:
                    # 否则的话,我们将当前元素添加到链表的末尾
                    insert_table(head_table[item][1], new_node)
                head = new_node
            head.update_freq()
    return root

这里添加到末尾的操作,我们可以再建立一个dict来维护头指针表的末尾节点,但我这里偷懒了一下,就用最简朴的设施,先遍历到链表的末端,再举行添加:

def insert_table(head_node, node):
    while head_node.ptr is not None:
        head_node = head_node.ptr
    head_node.ptr = node

通过FP-tree快速查找数据

现在,我们已经完整实现了FP-tree的构建,接下来就到了重头戏,也就是频仍项集的挖掘。我们有了这棵FP-tree之后应该怎么用呢?

若是我们仔细观察一下FP-tree的话,会发现这棵树实在是数据的浓缩。可以认为是之前完整的数据集去除了非频仍的元素之后提炼获得的数据。凭据APriori算法的原理,我们接下来要做的就是用长度为1的频仍项集去构建长度为2的频仍项集,以此类推,直到找出所有的频仍项集为止。

然则在FP-growth算法当中,我们对这个逻辑稍稍做了一点点修正,我们每次牢固一个元素,查找所有它组成的频仍项集。我们要查找频仍项集,首先需要获取数据集,原始的数据包罗了太多无关的信息,我们已经用不到了,我们可以通过FP-tree高效地获取我们需要的数据。

由于我们之前在插入FP-tree的时刻,是严酷根据元素泛起的次数排序的,泛起频次高的元素放置的位置越高。这样树上某一个链路在数据集中泛起的次数,就即是链路中最底层的节点的数字。

我们来看个例子:

武汉新闻联播:嫌弃Apriori算法太慢?使用FP-growth算法让你的数据挖掘快到飞起 第1张

红框当中s的位置最低,以是整个链路上{z, x, y, s}在整个数据集当中泛起的次数就是2,那么我们确定了s之后,通过向上FP-tree,就可以还原出所有包罗s的频仍项组成的数据。

我们首先实现一个辅助方式,用来向上遍历整个链路所有的元素:

def up_forward(node):
    path = []
    while node.father is not None:
        path.append(node)
        node = node.father
    # 过滤树根
    return path

第二个辅助方式是牢固某个元素之后,还原所有这个元素的数据。要还原所有数据,只拿到一个节点是不够的,我们需要知道这个元素在FP-tree上所有泛起的位置。这个时刻就需要用到头指针表了,行使头指针表,我们可以找到所有元素在FP-tree中的位置,我们只需要挪用上面的方式,就可以还原出数据集了。

这段逻辑同样并不难题,实在就是遍历一个链表,然后再挪用上面向上遍历树的方式,获取所有的数据。

def regenerate_dataset(head_table, item):
    dataset = {}
    if item not in head_table:
        return dataset
    # 通过head_table找到链表的起始位置
    node = head_table[item][1]
    # 遍历链表
    while node is not None:
        # 对链表中的每个位置,挪用up_forward,获取FP-tree上的数据
        path = up_forward(node)
        if len(path) > 1:
            # 将元素的set作为key
            # 这里去掉了item,为了使得新构建的数据当中没有item
            # 从而挖掘出以含有item为条件的新的频仍项
            dataset[frozenset(path[1:])] = node.freq
        node = node.ptr
    
    # 将kv花样的数据还原成数组形式
    ret = []
    for k, v in dataset.items():
        for i in range(v):
            ret.append(list(k))
    return ret

递归建树,挖掘频仍项集

到这里,我们对FP-tree应该有一个对照清晰的认识了,它的功效就是可以快速地查找某些元素组合的聚集的频次,由于相同元素组成的聚集都被存储在统一条树链上了。

那么我们怎么凭据FP-tree来挖掘频仍项集呢?

这里才是真正的算法的精髓。

我们照样看下上面的例子:

武汉新闻联播:嫌弃Apriori算法太慢?使用FP-growth算法让你的数据挖掘快到飞起 第2张

我们假设我们牢固的元素是r,我们通过FP-tree可以快速找到和r配合泛起的频仍项有z,x,y,s。通过适才上面的方式,我们可以获得一个新的必须包罗r和频仍项的新的数据集。我们把r从这份数据当中去除,然后对剩下的数据构建新的FP-tree,若是新的FP-tree当中另有其他元素,那么这个元素一定可以和r组成二元的频仍项集。假设这个元素是x,那么我们继续重复上面的操作,再将x从数据中去除,再次构建FP-tree来挖掘包罗x和r的三元频仍项集,直到组成的FP-tree当中没有元素了为止。

这就成了一个递归挪用的历程,也就是说FP-tree自己并不能挖掘频仍项集,只能挖掘频仍项。然则我们可以人为加上条件条件,当我们以必须包罗x的数据为条件挖掘出来的频仍项,实在就是包罗x的二元频仍项集。我们加上的条件越来越多,也就是挖掘的频仍项集的元素越来越多。

若是你另有点蒙,没有关系,我们来看下代码:

def mine_freq_lists(root, head_table, min_freq, base, freq_lists):
    # 对head_table排序,根据频次从小到大排
    frequents = [i[0] for i in sorted(head_table.items(), key=lambda x: x[0])]
    for freq in frequents:
        # base是被列为条件的频仍项集
        new_base = base.copy()
        # 把当前元素加入频仍项集
        new_base.add(freq)
        # 加入谜底
        freq_lists.append(new_base)
        # 通过FP-tree获取当前频仍项集(new_base)为基础的数据
        new_dataset = regenerate_dataset(head_table, freq)
        # 天生新的head_table
        new_head_table = transform_to_header_table(filter_unfreq_items(new_dataset, min_freq))
        # 若是为空,说明没有更长的频仍项集了
        if len(new_head_table) > 0:
            # 若是另有,就构建新的FP-tree
            new_root = create_FP_tree(new_dataset, new_head_table, min_freq)
            # 递归挖掘
            mine_freq_lists(new_root, new_head_table, min_freq, new_base, freq_lists)
            
            
    
if __name__ == "__main__":
    dataset = create_dataset()
    data_dict = filter_unfreq_items(dataset, 3)
    head_table = transform_to_header_table(data_dict)
    root = create_FP_tree(dataset, head_table, 3)

    data = regenerate_dataset(head_table, 'r')

    freq_lists = []
    mine_freq_lists(root, head_table, 3, set([]), freq_lists)

末端

到这里,整个FP-growth挖掘频仍项集的算法就竣事了,相比于Apriori,它的技术细节要多得多,若是初学者以为不太好明了,这也是正常的,可以抓大放小,先从焦点思绪最先明了。

Apriori的焦点思绪是用两个长度为l的频仍项集去构建长度为l+1的频仍项集,而FP-growth则稍有差别。它是将一个长度为l的频仍项集作为条件,筛选出包罗这个频仍项集的数据集。用这个数据集构建新的FP-tree,从这个FP-tree当中寻找新的频仍项。若是能找到,那么说明它可以和长度为l的频仍项集组成长度为l+1的频仍项集。然后,我们就重复这个历程。

这个焦点思绪明了了,怎么构建FP-tree,怎么维护头指针表都是很简朴的问题了。

列位看官大人,请关注我吧~

武汉新闻联播:嫌弃Apriori算法太慢?使用FP-growth算法让你的数据挖掘快到飞起 第3张

,

诚信企业在线企业邮局

诚信企业在线企业邮局(现:阳光在线官网)现已开放诚信在线手机版、诚信在线电脑客户端下载。诚信在线娱乐游戏公平、公开、公正,用实力赢取信誉。

版权声明

本文仅代表作者观点,
不代表本站Allbet的立场。
本文系作者授权发表,未经许可,不得转载。

评论