实验六数据挖掘之关联分析

2019-06-28 本文已影响0人 keeeeeenon

实验六、数据挖掘之关联分析

一、实验目的

1. 理解Apriori算法的基本原理

2. 理解FP增长算法的基本原理

3. 学会用python实现Apriori算法

4. 学会用python实现FP增长算法

二、实验工具

1. Anaconda

2. sklearn

3. Pandas

三、实验简介

Apriori算法在发现关联规则领域具有很大影响力。算法命名源于算法使用了频繁项集性质的先验（prior）知识。在具体实验时，Apriori算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则。其中，挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。

在对深度优先数据挖掘算法的研究工作中，Han等人没有采用潜在频繁项集的方法求解频繁项集，而是提出了称为频率模式增长（FP_growth）的算法。该算法通过扫描数据库创建FP_tree的根节点并标示为null，对数据库D中的每一个事务Tran，按L中的次序对Tran中的频繁项排序，设Tran中排序后的频繁项列表[p|P]，这里p是第一个元素，P是保留列表。接着调用函数insert_tree（[p|P]，T），如果树T有一个子节点N且N.item_name=p.item_name，就将N节点计数加1；否则就创建一个新节点N，设计数为1，它的父节点连接到T，节点连接到同名的节点连接结构上。如果P是非空的，就递归调用insert_tree（P，N）。由于压缩了数据库内容，并且在将频繁项写入FP_tree结构时，保留了项集间的相连信息。求解频繁项集的问题，就转化为递归地找出最短频繁模式并连接其后缀构成长频繁模式的问题。

四、实验内容

1. 利用python语言编写Apriori算法，挖掘出下表中数据集的频繁项集，最小支持度为30%。

from numpy import *
 
# 构造数据
#a=1,b=2,c=3,d=4,e=5
def loadDataSet():
    return  [ ['a', 'b', 'd', 'e'],
                ['b', 'c', 'd'],
                ['a', 'b', 'd', 'e'],
                ['a', 'c', 'd', 'e'],
                ['b', 'b', 'd', 'e'],
                ['b', 'd', 'e'],
                [ 'c', 'd'],
                ['a', 'b', 'c'] ,
                ['a', 'd', 'e'],
                ['b', 'd',]]
 
# 将所有元素转换为frozenset型字典，存放到列表中
def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    # 使用frozenset是为了后面可以将这些值作为字典的键
    return list(map(frozenset, C1))  # frozenset一种不可变的集合，set可变集合
 
# 过滤掉不符合支持度的集合
# 返回 频繁项集列表retList 所有元素的支持度字典
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):   # 判断can是否是tid的《子集》 （这里使用子集的方式来判断两者的关系）
                if can not in ssCnt:    # 统计该值在整个记录中满足子集的次数（以字典的形式记录，frozenset为键）
                    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.insert(0, key)
        supportData[key] = support
    return retList, supportData # 排除不符合支持度元素后的元素 每个元素支持度
 
# 生成所有可以组合的集合
# 频繁项集列表Lk 项集元素个数k  [frozenset({2, 3}), frozenset({3, 5})] -> [frozenset({2, 3, 5})]
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk): # 两层循环比较Lk中的每个元素与其它元素
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]  # 将集合转为list后取值
            L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()        # 这里说明一下：该函数每次比较两个list的前k-2个元素，如果相同则求并集得到k个元素的集合
            if L1==L2:
                retList.append(Lk[i] | Lk[j]) # 求并集
    return retList  # 返回频繁项集列表Ck
 
# 封装所有步骤的函数
# 返回 所有满足大于阈值的组合 集合支持度列表
def apriori(dataSet, minSupport = 0.3):
    D = list(map(set, dataSet)) # 转换列表记录为字典  [[1, 2, 4,5], [2, 3, 4], [1, 2, 4, 5],[1, 3, 4, 5],[2, 3, 4, 5],
            # [2, 4, 5],[3, 4],[1, 2,3],[1, 4,5],[2,4]]
    C1 = createC1(dataSet)      # 将每个元素转会为frozenset字典    [frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
    L1, supportData = scanD(D, C1, minSupport)  # 过滤数据
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):    # 若仍有满足支持度的集合则继续做关联分析
        Ck = aprioriGen(L[k-2], k)  # Ck候选频繁项集
        Lk, supK = scanD(D, Ck, minSupport) # Lk频繁项集
        supportData.update(supK)    # 更新字典（把新出现的集合:支持度加入到supportData中）
        L.append(Lk)
        k += 1  # 每次新组合的元素都只增加了一个，所以k也+1（k表示元素个数）
    return L, supportData
 
dataSet = loadDataSet()
L,suppData = apriori(dataSet)
print(L)
print(suppData)

实验结果：

image.png

2. （选做）利用python语言编写FP增长算法，挖掘出上表中数据集的频繁项集，最小支持度为30%。

def loadSimpDat():
    simpDat = [ ['a', 'b', 'd', 'e'],
                ['b', 'c', 'd'],
                ['a', 'b', 'd', 'e'],
                ['a', 'c', 'd', 'e'],
                ['b', 'b', 'd', 'e'],
                ['b', 'd', 'e'],
                [ 'c', 'd'],
                ['a', 'b', 'c'] ,
                ['a', 'd', 'e'],
                ['b', 'd',]]
    return simpDat

def createInitSet(dataSet):
    retDict = {}
    for trans in dataSet:
        fset = frozenset(trans)
        retDict.setdefault(fset, 0)
        retDict[fset] += 1
    return retDict

class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name = nameValue
        self.count = numOccur
        self.nodeLink = None
        self.parent = parentNode
        self.children = {}

    def inc(self, numOccur):
        self.count += numOccur

    def disp(self, ind=1):
        print('   ' * ind, self.name, ' ', self.count)
        for child in self.children.values():
            child.disp(ind + 1)


def createTree(dataSet, minSup=1):
    headerTable = {}
    #此一次遍历数据集， 记录每个数据项的支持度
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item, 0) + 1

    #根据最小支持度过滤
    lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))
    for k in lessThanMinsup: del(headerTable[k])

    freqItemSet = set(headerTable.keys())
    #如果所有数据都不满足最小支持度，返回None, None
    if len(freqItemSet) == 0:
        return None, None

    for k in headerTable:
        headerTable[k] = [headerTable[k], None]

    retTree = treeNode('φ', 1, None)
    #第二次遍历数据集，构建fp-tree
    for tranSet, count in dataSet.items():
        #根据最小支持度处理一条训练样本，key:样本中的一个样例，value:该样例的的全局支持度
        localD = {}
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0]

        if len(localD) > 0:
            #根据全局频繁项对每个事务中的数据进行排序,等价于 order by p[1] desc, p[0] desc
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable


def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:  # check if orderedItems[0] in retTree.children
        inTree.children[items[0]].inc(count)  # incrament count
    else:  # add items[0] to inTree.children
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        if headerTable[items[0]][1] == None:  # update header table
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])

    if len(items) > 1:  # call updateTree() with remaining ordered items
        updateTree(items[1:], inTree.children[items[0]], headerTable, count)


def updateHeader(nodeToTest, targetNode):  # this version does not use recursion
    while (nodeToTest.nodeLink != None):  # Do not use recursion to traverse a linked list!
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

simpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()

实验结果：FP树