Apriori算法实现

Apriori算法是一种经典的频繁项集挖掘算法，用于发现数据集中频繁出现的项集。它基于两个重要的性质：支持度和置信度。支持度是指项集在数据集中出现的频率，而置信度是指包含某个项集的数据项也包含另一个特定项的概率。

Apriori算法的主要思想是利用“先验知识”来减少搜索空间。如果一个项集是频繁的，那么它的所有子集也必须是频繁的。因此，我们可以通过反复地进行子集测试来减少搜索空间，直到找到所有频繁项集为止。

以下是一个简单的Python实现：

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

def create_c1(dataset):
    c1 = []
    for transaction in dataset:
        for item in transaction:
            if not [item] in c1:
                c1.append([item])
    c1.sort()
    return list(map(frozenset, c1))

def scan_dataset(dataset, candidates, min_support):
    counts = {}
    for transaction in dataset:
        for candidate in candidates:
            if candidate.issubset(transaction):
                counts[candidate] = counts.get(candidate, 0) + 1
    num_items = float(len(dataset))
    freq_items = []
    support_data = {}
    for itemset in counts:
        support = counts[itemset] / num_items
        if support >= min_support:
            freq_items.append(itemset)
            support_data[itemset] = support
    return freq_items, support_data

def apriori_gen(freq_sets, k):
    ret_list = []
    len_lk = len(freq_sets)
    for i in range(len_lk):
        for j in range(i+1, len_lk):
            l1 = list(freq_sets[i])[:k-2]
            l2 = list(freq_sets[j])[:k-2]
            l1.sort()
            l2.sort()
            if l1 == l2:
                ret_list.append(freq_sets[i] | freq_sets[j])
    return ret_list

def apriori(dataset, min_support=0.5):
    C1 = create_c1(dataset)
    D = list(map(set, dataset))
    L1, support_data = scan_dataset(D, C1, min_support)
    L = [L1]
    k = 2
    while len(L[k-2]) > 0:
        Ck = apriori_gen(L[k-2], k)
        Lk, supk = scan_dataset(D, Ck, min_support)
        support_data.update(supk)
        L.append(Lk)
        k += 1
    return L, support_data

其中，`load_dataset`函数用于加载数据集，`create_c1`函数用于生成候选项集C1，`scan_dataset`函数用于扫描数据集并计算频繁项集，`apriori_gen`函数用于生成新的候选项集，`apriori`函数是Apriori算法的主要实现。

使用示例：

dataset = load_dataset()
L, support_data = apriori(dataset, min_support=0.5)
print("频繁项集：", L)
print("支持度：", support_data)

输出：

频繁项集： [[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({5})], [frozenset({1, 3}), frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5})], [frozenset({2, 3, 5})], []]
支持度： {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 3}): 0.5, frozenset({3, 5}): 0.5, frozenset({2, 5}): 0.75, frozenset({2, 3, 5}): 0.5}

输出结果中，第一个列表表示频繁1项集，第二个列表表示频繁2项集，第三个列表表示频繁3项集，最后一个列表为空，表示没有更多频繁项集了。支持度是指每个项集在数据集中出现的频率。