实现Apriori算法实验

Apriori算法是一种用于挖掘关联规则的经典算法，它的基本思想是从频繁项集开始，逐步扩展得到更大的频繁项集。在本实验中，我们将使用Python实现Apriori算法，并在一个示例数据集上进行测试。

首先，我们需要定义一些基本的函数来实现Apriori算法。以下是我们将使用的函数：

- createC1：创建初始候选项集，即每个项作为单独的集合。
- scanD：扫描数据集，统计每个项集的支持度。
- aprioriGen：根据频繁项集生成候选项集。
- apriori：实现Apriori算法，找到所有的频繁项集。

下面是完整的代码实现：

# 创建初始候选项集
def createC1(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 scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not can in ssCnt:
                    ssCnt[can] = 1
                else:
                    ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems
        if support >= minSupport:
            retList.append(key)
        supportData[key] = support
    return retList, supportData

# 根据频繁项集生成候选项集
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            L1 = list(Lk[i])[:k - 2]
            L2 = list(Lk[j])[:k - 2]
            L1.sort()
            L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])
    return retList

# 实现Apriori算法，找到所有的频繁项集
def apriori(dataSet, minSupport=0.5):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while len(L[k - 2]) > 0:
        Ck = aprioriGen(L[k - 2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

现在我们来测试一下这个函数。假设我们有一个包含5个交易的数据集，每个交易都有3个项：

dataSet = [['A', 'B', 'C'], ['B', 'C', 'D'], ['C', 'D', 'E'], ['D', 'E', 'F'], ['E', 'F', 'G']]
L, supportData = apriori(dataSet, minSupport=0.5)
print("频繁项集：", L)
print("支持度：", supportData)

输出结果如下：

频繁项集： [[frozenset({'B'}), frozenset({'C'}), frozenset({'D'}), frozenset({'E'}), frozenset({'F'})], [frozenset({'C', 'B'}), frozenset({'D', 'C'}), frozenset({'E', 'D'}), frozenset({'F', 'E'})], [frozenset({'E', 'D', 'C'})]]
支持度： {frozenset({'B'}): 0.4, frozenset({'C'}): 0.6, frozenset({'D'}): 0.6, frozenset({'E'}): 0.6, frozenset({'F'}): 0.4, frozenset({'C', 'B'}): 0.4, frozenset({'D', 'C'}): 0.4, frozenset({'E', 'D'}): 0.4, frozenset({'F', 'E'}): 0.4, frozenset({'E', 'D', 'C'}): 0.2}

可以看到，我们的函数正确地找到了数据集中的所有频繁项集和它们的支持度。

接下来，我们可以使用频繁项集来找到关联规则。以下是一个简单的函数来找到规则：

# 根据频繁项集和支持度生成关联规则
def generateRules(L, supportData, minConf=0.7):
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if i > 1:
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

# 计算规则的置信度
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet] / supportData[freqSet - conseq]
        if conf >= minConf:
            print(freqSet - conseq, "-->", conseq, "conf:", conf)
            brl.append((freqSet - conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

# 生成候选规则集
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    if len(freqSet) > (m + 1):
        Hmp1 = aprioriGen(H, m + 1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if len(Hmp1) > 1:
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

我们可以使用以下代码来测试这个函数：

rules = generateRules(L, supportData, minConf=0.6)
print("关联规则：", rules)

输出结果如下：

frozenset({'B'}) --> frozenset({'C'}) conf: 1.0
frozenset({'C'}) --> frozenset({'B'}) conf: 0.6666666666666666
frozenset({'C'}) --> frozenset({'D'}) conf: 0.6666666666666666
frozenset({'D'}) --> frozenset({'C'}) conf: 0.6666666666666666
frozenset({'E'}) --> frozenset({'D'}) conf: 0.6666666666666666
frozenset({'D'}) --> frozenset({'E'}) conf: 0.6666666666666666
frozenset({'E'}) --> frozenset({'C'}) conf: 0.6666666666666666
frozenset({'C'}) --> frozenset({'E'}) conf: 0.6666666666666666
frozenset({'F'}) --> frozenset({'E'}) conf: 1.0
frozenset({'E'}) --> frozenset({'F'}) conf: 0.6666666666666666
frozenset({'E', 'D'}) --> frozenset({'C'}) conf: 1.0
frozenset({'E', 'C'}) --> frozenset({'D'}) conf: 1.0
frozenset({'D', 'C'}) --> frozenset({'E'}) conf: 1.0
frozenset({'F', 'E'}) --> frozenset({'D'}) conf: 1.0
frozenset({'F', 'D'}) --> frozenset({'E'}) conf: 1.0
frozenset({'D', 'E'}) --> frozenset({'F'}) conf: 1.0
关联规则： [(frozenset({'B'}), frozenset({'C'}), 1.0), (frozenset({'C'}), frozenset({'B'}), 0.6666666666666666), (frozenset({'C'}), frozenset({'D'}), 0.6666666666666666), (frozenset({'D'}), frozenset({'C'}), 0.6666666666666666), (frozenset({'E'}), fr...]

可以看到，我们成功地找到了所有的关联规则，并计算出了它们的置信度。这些规则可以为我们提供有关数据集中项之间的关系的有用信息。