丽水英才网:详解十大经典数据挖掘算法之——Apriori

admin 4周前 (05-07) 科技 7 0

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


今天是机械学习专题的第19篇文章,我们来看经典的Apriori算法。

Apriori算法号称是十大数据挖掘算法之一,在大数据时代威风无两,哪怕是没有听说过这个算法的人,对于谁人著名的啤酒与尿布的故事也耳熟能详。但遗憾的是,随着时代的演进,大数据这个观点很快被机械学习、深度学习以及人工智能取代。纵然是笼络投资人的创业者也很少会讲到这个故事了,虽然时代的变迁令人唏嘘,然则这并不故障它是一个优异的算法。

我们来简朴回首一下这个故事,据说在美国的沃尔玛超市当中,啤酒和尿布经常被摆放在同一个货架当中。若是你仔细观察就会觉得很新鲜,啤酒和尿布无论是从应用场景照样商品自己的属性来分都不应该被放在一起,为什么超市要这么摆放呢?

看似不合理的征象背后往往都有更深条理的缘故原由,据说是沃尔玛引进了一种全新的算法,它剖析了所有主顾在超市消费的纪录,然后盘算商品之间的关联性,发现这两件商品的关联性异常高。也就是说有大量的主顾会同时购置啤酒和尿布这两种商品,以是经由数据的剖析,沃尔玛下令将这两个商品放在同一个货架上举行销售。果真这么一搞之后,两种商品的销量都提升了

这个在背后剖析数据,出谋划策充当智囊一样决议的算法就是Apriori算法。

关联剖析与条件概率

我们先把这个故事的真假放在一边,先来剖析一下故事背后折射出来的信息。我们把问题举行抽象,沃尔玛超市当中的商品种类也许有数万种,我们的算法做的着实是凭据售卖数据盘算剖析这些种类之间的相关性。专业术语叫做关联剖析,这个从字面上很好明白。但从关联剖析这个角度出发,我们会有些不一样的洞见。

我们之前都学过条件概率,我们是不是可以用条件概率来反映两个物品之间的关联性呢?好比,我们用A示意一种商品,B示意另外一种商品,我们完全可以凭据所有订单的情形盘算出P(A|B)和P(B|A),也就是说用户在购置了A的情形下会购置B的概率以及在购置B的情形下会购置A的概率。这样做看起来也很科学啊,为什么不这样做呢,还要引入什么新的算法呢?

这也就是算法需要性问题,这个问题解决不了,我们好像会很难说服自己去学习一门新的算法。着实回覆这个问题很简朴,就是。大型超市当中的商品一样平常都有几万种,而这几万种商品的销量差异伟大。一些热门商品好比水果、蔬菜的销量可能是冷门商品,好比冰箱、洗衣机的上千倍甚至是上万倍。若是我们要盘算两两商品之间的相关性显然是一个伟大的开销,由于对于每两个商品的组合,我们都需要遍历一遍整个数据集,拿到商品之间配合销售的纪录,从而盘算条件概率。

我们假设商品的种类数是一万,超市的订单量也是一万好了,那么两两商品之间的组合就有一亿条,若是再乘上每次盘算需要遍历一次整个数据集,那么整个运算的庞大度也许会是一万亿。若是再思量多个商品的组合,那这个数字加倍恐怖。

但现实上一个大型超市订单量一定不是万级其余,至少也是十万或者是百万量级甚至更多。以是这个盘算的庞大度是异常重大的,若是思量盘算带来的开销,这个问题在商业上就是不能解的。由于纵然算出来效果带来的收益也远远无法肩负支出的盘算价值,这个盘算价值可能比许多人想得大得多,纵然是使用现成的云盘算服务,也会带来极为昂贵的开销。若是思量数据平安,不能使用其他公司的盘算服务的话,那么自己维护这些数据和人工带来的消耗也是凡人难以想象的。

若是想要得出切实可行的效果,那么优化算法一定是必须的,否则可能没有一家超市愿意支出这样的价值。

在我们先容Apriori算法之前,我们可以先试着自己思索一下这个问题的解法。我真的试着想过,然则我没有获得很好的谜底,对比一下Apriori算法我才发现,这并非是我小我私家的问题,而是由于我们的头脑有误区。

若是你做过LeetCode,学过算法导论和数据结构,那么你在思索问题的时刻,往往会情不自禁地从最优解以及最佳解的偏向出发。反映在这个问题当中,你可能会倾向于找到所有高关联商品,或者是盘算出所有商品对之间的关联性。然则在这个问题当中,条件可能就是错的。由于谜底的完整性和庞大度之间往往是挂钩的,找出所有的谜底必然会带来更多的开销,而且落着实现实当中,牺牲一些完整性也是有原理的。由于对于超市而言,加倍关注高销量的商品,好比电冰箱和洗衣机,纵然得出结论它们和某些商品关联性很高对超市来说也没有太大意义,由于电冰箱和洗衣机一天总共也卖不出若干台。

你仔细思索就会发现这个问题和算法的靠山比我们一开始想的和明白的要深刻得多,以是让我们带着一点点敬畏之心来看看这个算法的详细吧。

频仍项集与关联规则

在我们详细领会算法的原理之前,我们先来熟悉两个术语。第一个属于叫做频仍项集,英文是frequent item sets。这个翻译很接地气,我们直接看字面意思应该就能明白。意思是经常会泛起在一起的物品的聚集。第二个属于叫做关联规则,也就是两个物品之间可能存在很强的关联关系。

用啤酒和尿布的故事举个例子,好比许多人经常一起购置啤酒和尿布,那么啤酒和尿布就经常泛起在人们的购物单当中。以是啤酒和尿布就属于同一个频仍项集,而一小我私家买了啤酒很有可能还会购置尿布,啤酒和尿布之间就存在一个关联规则。示意它们之间存在很强的内在联系。

有了频仍项集和关联规则我们会做什么事情?很简朴会去盘算它们的概率

对于一个聚集而言,我们要思量的是整个聚集泛起的概率。在这个问题场景当中,它的盘算异常简朴。即用聚集当中所有元素一起泛起的次数,除以所有的数据条数。这个概率也有一个术语,叫做支持度,英文称作support。

对于一个关联规则而言,它指的是A物品和B物品之间的内在关系,着实也就是条件概率。以是A->B关联规则的概率就是P(AB)/P(A)和条件概率的公式一样,不外在这个问题场景当中,也有一个术语,叫做置信度,英文是confidence。

着实confidence也好,support也罢,我们都可以简朴地明白成泛起的概率。这是一个盘算概率的模子,可以认为是条件概率运算的优化。其中关联规则是基于频仍项集的,以是我们可以先把关联规则先放一放,先来主要看频仍项集的求解历程。既然频仍项集的支持度本质上也是一个概率,那么我们就可以使用一个阈值来举行限制了。好比我们划定一个阈值是0.5,那么通常支持度小于0.5的聚集就不用思量了。我们先用这个支持渡过一遍全体数据,找出知足支持度限制的单个元素的聚集。之后当我们寻找两个元素的频仍项集的时刻,它的候选集就不再是全体商品了,而只有那些包罗单个元素的频仍项集。

同理,若是我们要寻找三项的频仍项集,它的候选集就是含有两项元素的频仍项集,以此类推。表面上看,我们是把候选的局限限制在了频仍项集内从而简化了运算。着实它背后有一个很深刻的逻辑,即不是频仍项集的聚集,一定不能能组成其他的频仍项集。好比电冰箱天天的销量很低,它和任何商品都不能能组成频仍项集。这样我们就可以排除掉所有那些不是频仍项集的所有情形,大大减少了运算量。

上图当中的23不是频仍项集,那么对应的123和023显然也都不是频仍项集。着实我们把这些非频仍的项集去掉,剩下的就是频仍项集。以是我们从正面或者是反面明白都可以,逻辑的内核是一样的。

Apriori算法及实现

着实Apriori的算法精髓就在上面的表述当中,也就是凭据频仍项集寻找新的频仍项集。我们整理一下整个算法的流程,然后一点点用代码来实现它,对照代码和流程很容易就搞清楚了。

首先,我们来建立一批假的数据用来测试:

def create_dataset():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

下面我们要天生只有一个项的所有聚集。这一步很好明白,我们需要对所有有买卖的商品天生一个清单,也就是将所有买卖纪录中的商品购置纪录举行去重。由于我们天生的效果在后序会作为dict的key,而且我们知道set也是可变工具,也是不能以作为dict中的key的。以是我们要做一点转换,将它转换成frozenset,它可以认为是不能以修改的set。

def individual_components(dataset):
    ret = []
    for data in dataset:
        for i in data:
            ret.append((i))
    # 将list转化成set即是去重操作
    ret = set(ret)
    return [frozenset((i, )) for i in ret]

执行事后,我们会获得这样一个序列:

[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]

上面的这个序列是长度为1的所有聚集,我们称它为C1,这里的C就是component,也就是聚集的意思。下面我们要天生的f1,也就是长度为1的频仍聚集。频仍聚集的选取是凭据最小支持渡过滤的,以是我们下面要实现的就是盘算Ck中每一个聚集的支持度,然后过滤掉那些支持度不知足要求的聚集。这个应该也很好明白:

def filter_components_with_min_support(dataset, components, min_support):
    # 我们将数据集中的每一条转化成set
    # 一方面是为了去重,另一方面是为了举行聚集操作
    dataset = list(map(set, dataset))
    # 纪录每一个聚集在数据集中的泛起次数
    components_dict = defaultdict(int)

    for data in dataset:
        for i in components:
            # 若是聚集是data的子集
            # 也就是data包罗这个聚集
            if i <= data:
                components_dict[i] += 1
rows = len(dataset)
frequent_components = []
supports = {}
<span class="hljs-keyword" style="color: #333; font-weIGht: bold; LINE-height: 26px;">for</span> k,v <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> components_dict.items():
    <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 支持度就是聚集在数据集中的泛起次数除以数据总数</span>
    support = v / rows
    <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 保留知足支持度要求的数据</span>
    <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">if</span> support &gt;= min_support:
        frequent_components.append(k)
    supports[k] = support
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> frequent_components, supports

我们将支持度设置成0.5来执行一下,会获得以下效果:

可以发现数据中的4被过滤了,由于它只泛起了1次,支持度是0.25,达不到我们设置的阈值,和我们的预期一致。

现在我们有了方式建立长度为1的项集,也有了方式凭据支持渡过滤非频仍的项集,接下来要做的已经很明显了,我们要凭据长度为1的频仍项集天生长度为2的候选集,然后再行使上面的方式过滤获得长度为2的频仍项集,再通过长度为2的频仍项集天生长度为3的候选集,云云往复,直到所有的频仍项集都被挖掘出来为止。

凭据这个思绪,我们接下来另有两个方式要做,一个是凭据长度为n的频仍项集天生长度n+1候选集的方式,另一个方式是行使这些方式挖掘所有频仍项集的方式。

我们先来看凭据长度为n的项集天生n+1候选集的方式,这个也很好实现,我们只需要用所有元素依次加入现有的聚集当中即可。

def generate_next_componets(components):
    # 获取聚集当中所有单个的元素
    individuals = individual_components(components)
    storage = set()
    for i in individuals:
        for c in components:
            # 若是i已经在聚集中了则跳过
            if i <= c:
                continue
            cur = i | c
            # 否则合并,加入存储
            if cur not in storage:
                storage.add(cur)
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> list(storage)

这些方式都有了之后,剩下的就很好办了,我们只需要重复挪用上面的方式,直到找不到更长的频仍项集为止。我们直接来看代码:

def apriori(dataset, min_support):
    # 天生长度1的候选聚集
    individuals = individual_components(dataset)
    # 天生长度为1的频仍项集
    f1, support_dict = filter_components_with_min_support(dataset, individuals, min_support)
    frequent = [f1]
    while True:
        # 天生长度+1的候选聚集
        next_components = generate_next_componets(frequent[-1])
        # 凭据支持度筛选出频仍项集
        components, new_dict = filter_components_with_min_support(dataset, next_components, min_support)
        # 若是筛选效果为空,说明不存在更长的频仍项集了
        if len(components) == 0:
            break
        # 更新效果
        support_dict.update(new_dict)
        frequent.append(components)
    return frequent, support_dict

最后,我们运行一下这个方式查看一下效果:

红色框中就是我们从数据聚集当中挖掘出的频仍项集了。在一些场景当中我们除了想要知道频仍项集之外,可能还会想要知道关联规则,看看哪些商品之间存在隐形的强关联。我们凭据类似的思绪可以设计出算法来实现关联规则的挖掘。

关联规则

明白了频仍项集的观点之后再来算关联规则就简朴了,我们首先来看一个很简朴的变形。由于我们需要盘算频仍项集之间的置信度,也就是条件概率。我们都知道P(A|B) = P(AB) / P(B),这个是条件概率的基本公式。这里的P(A) = 泛起A的数据条数/ 总条数,着实也就是A的支持度。以是我们可以用支持度来盘算置信度,由于刚刚我们在盘算频仍项集的时刻算出了所有频仍项集的支持度,以是我们可以用这份数据来盘算置信度,这样会简朴许多。

我们先来写出置信度的盘算公式,它异常简朴:

def calculate_confidence(comp, subset, support_dict):
    return float(support_dict[comp]) / support_dict[comp-subset]

这里的comp示意聚集,subset示意我们要推断的项。也就是我们挖掘的是comp-item这个聚集与subset聚集之间的置信度。

接着我们来看候选规则的天生方式,它和前面天生候选聚集的逻辑差不多。我们拿到频仍项集之后,扣除其中的一个子集,将它作为一个候选的规则。

def generate_rules(components, subset):
    all_set = []
    # 天生所有子集,也就是长度更小的频仍项集的聚集
    for st in subset:
        all_set += st
rules = []
<span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 遍历所有子集</span>
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> i <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> all_set:
    <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 遍历频仍项集</span>
    <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> comp <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> components:
        <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 若是子集关系建立,则天生了一条候选规则</span>
        <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">if</span> i &lt;= comp:
            rules.append((comp, i))
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> rules

最后,我们把上面两个方式串联在一起,先天生所有的候选规则,再凭据置信渡过滤掉相符条件的关联规则。行使之前频仍项集时刻天生的数据,很容易实现这点。

def mine_rules(frequent, support_dict, min_confidence):
    rules = []
    # 遍历长度大于即是2的频仍项集
    for i in range(1, len(frequent)):
        # 使用长度更小的频仍项集作为自己,构建候选规则集
        candidate_rules = generate_rules(frequent[i], frequent[:i])
        # 盘算置信度,凭据置信度举行过滤
        for comp, item in candidate_rules:
            confidence = calculate_confidence(comp, item, support_dict)
            if confidence >= min_confidence:
                  rules.append([comp-item, item, confidence])
    return rules

我们运行一下这个方式,看一下效果:

从效果来看还不错,我们挖掘出了所有的关联规则。要注意一点A->B和B->A是两条差别的规则,这并不重复。举个简朴的例子,买乒乓拍的人往往都市买乒乓球,然则买乒乓球的人却并不一定会买乒乓拍,由于乒乓拍比乒乓球贵得多。而且乒乓球是消耗品,乒乓拍不是。以是乒乓拍可以关联乒乓球,但反之不一定建立。

末端、升华

到这里,Apriori算法和它的应用场景就讲完了。这个算法的原理并不庞大,代码也不难题,没有什么高深的推导或者是艰涩的运算,然则算法背后的逻辑并不简朴。怎么样为一个庞大的场景涉及简朴的指标?怎么样缩小我们盘算的局限?怎么样权衡数据的价值?着实这些并不是空穴来风,显然算法的设计者是支出了大量思索的。

若是我们顺着解法出发去试着倒推那时设计者的思索历程,你会发现看似简朴的问题背后着实并不简朴,看似自然而然的原理,也并不自然,这些看似寻常的背后都隐藏着逻辑,这些背后的思索和逻辑,才是算法真正名贵的部门。

今天的文章就到这里,原创不易,需要你的一个关注,你的举手之劳对我来说很主要。

,

SuNBet

Sunbet www.43zhekou.com在即将到来的2019年,将以更暖心的服务,更完善的技术,更足够的资金,为所有Sunbet的代理、会员提供更好的开户、买分服务。

皇冠APP下载声明:该文看法仅代表作者自己,与本平台无关。转载请注明:丽水英才网:详解十大经典数据挖掘算法之——Apriori

网友评论

  • (*)

最新评论

文章归档