实现机器学习的分步指南 XII - Apriori

引言

Apriori 是一种用于学习频繁项集和关联规则的算法。Apriori 是一种自底向上的方法，在每次迭代中扩展一个对象以获得频繁项集。当没有对象可扩展时，算法终止。

Apriori 模型

频繁项集

频繁项集是指通常同时出现的对象集合。

传统方法需要多次遍历数据集。为了减少计算量，研究人员发现了一种称为 Apriori 原则的东西。Apriori 原则帮助我们减少可能的有趣项集数量。Apriori 原则指出，如果一个项集是频繁的，那么它的所有子集都是频繁的。乍一看这似乎没有用。但是，如果我们将其反过来，它表明如果一个项集不是频繁的，那么它的所有超集都不是频繁的。这意味着在自底向上的过程中，如果底层项集不是频繁的，我们就不需要处理顶层的集合。例如，存在一个集合 A = {1, 2, 3, 4}。由 A 生成的所有可能的项集如下所示

如果项集 {0, 1} 不是频繁的，那么所有包含 {0, 1} 的项集都不是频繁的，这意味着我们可以跳过这些项集，如图中蓝色圆圈所示。

频繁项集的生成包括以下步骤

1. 首先，计算单例集。所有元素都被视为候选集。

       def createSingletonSet(self, data):
           singleton_set = []
           for record in data:
               for item in record:
                   if [item] not in singleton_set:
                       singleton_set.append([item])
           singleton_set.sort()
           singleton_set = list(map(frozenset, singleton_set))   # generate a invariable set
           return singleton_set

2. 合并单例集以生成更多的候选集。

       def createCandidateSet(self, frequent_items, k):
           candidate_set = []
           items_num = len(frequent_items)
           # merge the sets which have same front k-2 element
           for i in range(items_num):
               for j in range(i+1, items_num):
                   L1 = list(frequent_items[i])[: k-2]
                   L2 = list(frequent_items[j])[: k-2]
                   if L1 == L2:
                       candidate_set.append(frequent_items[i] | frequent_items[j])
           return candidate_set

3. 计算所有候选集的支持度，并选择支持度大于最小支持度的候选集作为频繁项集。

   

       def calculateSupportDegree(self, data, candidate_set):
           sample_sum = len(data)
           data = map(set, data)                   # transform data into set
   
           # calculate the frequency of each set in candidate_set appearing in data
           frequency = {}
           for record in data:
               for element in candidate_set:
                   if element.issubset(record):  # elements in record
                       frequency[element] = frequency.get(element, 0) + 1
   
           # calculate the support degree for each set
           support_degree = {}
           frequent_items = []
           for key in frequency:
               support = frequency[key]/sample_sum
               if support >= self.min_support:
                   frequent_items.insert(0, key)
               support_degree[key] = support
           return frequent_items, support_degree

4. 上述功能的组合

       def findFrequentItem(self, data):
           singleton_set = self.createSingletonSet(data)
           sub_frequent_items, sub_support_degree = 
                     self.calculateSupportDegree(data, singleton_set)
           frequent_items = [sub_frequent_items]
           support_degree = sub_support_degree
           k = 2
   
           while len(frequent_items[k-2]) > 0:
               candidate_set = self.createCandidateSet(frequent_items[k-2], k)
               sub_frequent_items, sub_support_degree = 
                        self.calculateSupportDegree(data, candidate_set)
               support_degree.update(sub_support_degree)
               if len(sub_frequent_items) == 0:
                   break
               frequent_items.append(sub_frequent_items)
               k = k + 1
           return frequent_items, support_degree

关联规则

关联规则是指某种事情发生导致其他事情发生。例如，存在一个频繁项集 {啤酒，尿布}。可能存在一个关联规则尿布->啤酒，这意味着购买尿布的人也可能购买啤酒。请注意，该规则是单向的，这意味着规则啤酒->尿布可能不正确。

关联规则的生成包括以下步骤

1. 计算每个频繁项集的置信度，并选择置信度大于最小置信度的项集。

   

       def calculateConfidence(self, frequent_item, support_degree, candidate_set, rule_list):
           rule = []
           confidence = []
           for item in candidate_set:
               temp = support_degree[frequent_item]/support_degree[frequent_item - item]
               confidence.append(temp)
               if temp >= self.min_confidence:
                   rule_list.append((frequent_item - item, item, temp))  # association rule
                   rule.append(item)
           return rule

2. 合并频繁项集以生成更多的关联规则

       def mergeFrequentItem(self, frequent_item, support_degree, candidate_set, rule_list):
           item_num = len(candidate_set[0])
           if len(frequent_item) > item_num + 1:
               candidate_set = self.createCandidateSet(candidate_set, item_num+1)
               rule = self.calculateConfidence
                    (frequent_item, support_degree, candidate_set, rule_list)
               if len(rule) > 1:
                   self.mergeFrequentItem(frequent_item, support_degree, rule, rule_list)

3. 上述功能的组合

       def generateRules(self, frequent_set, support_degree):
           rules = []
           for i in range(1, len(frequent_set)):    # generate rule from sets 
                                                    # which contain more than two elements
               for frequent_item in frequent_set[i]:
                   candidate_set = [frozenset([item]) for item in frequent_item]
                   if i > 1:
                       self.mergeFrequentItem
                         (frequent_item, support_degree, candidate_set, rules)
                   else:
                       self.calculateConfidence
                          (frequent_item, support_degree, candidate_set, rules)
           return rules

结论与分析

Apriori 是一种生成频繁项集和关联规则的简单算法。但它更适合稀疏数据集。现在，我们有一个数据集如下。让我们看看 Apriori 的结果。结果是一个元组，形式为 (X, Y, 置信度)。

本文相关的代码和数据集可以在 MachineLearning 中找到。