数据挖掘自学笔记(4)

现在数据都清洗的“白白净净”了,我们应该做些什么了吧!根据前面的流程,应该要把数据放到数据仓库,以备后续的数据分析。

但是,我感觉不一定非要放到数据仓库啦,不同的分析需求可能不同,或许是放到数据库,也或许是放到文件系统。不管我们的需求要求我们把数据放哪,我们都要对数据做些什么。

我们要做的就是数据挖掘。

数据有了,如何挖掘?挖掘不是一把抓,也要根据我们的需求。我们想要什么,我们就去挖什么。

我们想要的第一个东西——关联规则。

关联规则(Association rules)

什么是关联规则?

超市发现我们在买啤酒的时候很多情况下会同时购买卫生纸,于是超市就把啤酒和卫生纸放在一起,或者搞一些促销什么的,到了月末发现超市营业额增长了不少。所以,通过这样的方式,超市多赚了钱,他们很开心。

买啤酒的同时会买卫生纸,这就是一条关联规则。但是,如何得到关联规则?

这就需要关联规则挖掘。

从事务数据库,关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。

所以,关联规则挖掘的是一些频繁出现的模式,这些模式来源于项集。项集可以理解为项目的集合,如{啤酒、卫生纸}就是一个项集,因为有2个元素,所以叫做2-项集。

仅仅是这样还不能进行关联规则的挖掘。因为我们还缺乏一种度量,来评估关联规则。

所以就有了支持度(Support)和置信度(Confidence)。而我们使用最小支持度和最小置信度来过滤一些规则, 只有符合要求的规则才能通过“海选”。所以,这个“度”是用来限制(要求)规则的。

最小支持度:要求这个规则必需涵盖的最少数据数目

最小置信度:要求这个规则必需超过最小的预测强度

举例来说,如果要产生A=>B(当A发生时,B也会发生)这个关联规则,我们需要找出项集{AB}。假设数据库中有10000条记录,最小支持的我们限定为40%,则{AB}出现的次数必需要不小于10000*40%=4000。也就是说,这10000条记录中必需有4000条记录同时记录了A和B(A和B被同时购买了)。

如果数据库中真的有4000多条记录有{AB},我们就称{AB}为频繁项集。但是,即便是这样,也不能直接得到A=>B这条规则。还需要经过最小置信度的筛选。

如果我们把最小置信度限定为60%,则要求数据库中包含A的记录中,有60%的记录同时包含了B。假设包含A的记录有5000条,则需要至少有3000条记录包含B。如果{AB}通过了最小支持度和最小置信度的层层筛选,可以得到A=>B,即购买A的时候会购买B,我们称{AB}为强关联规则

但是,支持度、置信度的评估方式并不完善。

对于支持度,如果某件商品本身就卖的特别少(比如印泥),支持度直接就把它淘汰了。对于置信度,尽管我们可以得到在购买啤酒的同时会购买薯片,但是不购买啤酒的时候也会售出大量薯片,所以啤酒和薯片基本上是独立的事件,这样的置信度没多大用处。所以,就有了提升度(Lift)来解决这个问题。

$$Lift(A=>B) = c(A=>B) / s(B)$$

有了评价,就可以放心大胆的进行关联规则挖掘了,挖出来了评一下,好的则留下,不好的则扔掉。

关联规则挖掘(Association rules mining)

我们要挖掘的规则有很多种,如布尔关联规则、量化关联规则、单维关联规则、多维关联规则、单层关联规则、多层关联规则等。

看到这里就不想挖掘了,太麻烦了。不过还好,我们主要学习简单的关联规则挖掘,即单维、单层、布尔关联规则的挖掘。

挖掘是需要算法的,总不能想怎么挖就怎么挖吧!接触第一个数据挖掘算法:Apriori算法。

Apriori

Apriori是一个挖掘布尔关联规则频繁项集的算法。也就是说,它只关心某个商品买了还是没买,不关心买了多少个,所以是“布尔”。Apriori挖掘出来的是频繁项集,也就是最小支持度检测合格的项集。所以,这样的项集,即频繁项集还要经过最小置信度的检验。

Apriori算法利用频繁项集性质的先验知识(Prior knowledge),通过逐层搜索的迭代方法,即将k-项集用于探察(k+1)-项集,来穷尽数据集中的所有频繁项集。Apriori算法包括连接和剪枝两个步骤。

Apriori算法示例如下(摘自王灿老师PPT),最小支持度为50%:

其中,$C_k$表示项集$L_k$的超集,也就是说前者的范围更大,所有频繁的k-项集都包含在其中,也可能包含不频繁的。总之,这里面有我们想要的频繁k-项集。

因为最小支持度为50%,数据源中有4条记录,所以最小计数为2,即必须出现2次才可以成为频繁项集。第一次扫描得到所有的1-项集C1,但是里面有一些小于最小计数得到元素,如元素D。所以需要把D删除掉,得到频繁1-项集。

有了频繁1-项集,就可以继续生成2-项集C2,生成的方法是把L1中的所有元素进行自由组合(无重复),得到2-项集C2。同理,2-项集里也有不符合最小计数的元素,删除后得到频繁2-项集L2。

以此类推,指导$L_k$只含有一个元素。至此,我们得到了$\lbrace L_1,L_2, \dots, L_k\rbrace$,这就是我们想要的频繁项集,其中L1没什么用。频繁项集经过最小置信度检验后,可以得到我们想要的最终结果,关联规则。

到了这里,似乎有了动态规划和贪心感觉(_^__^_)

疯狂的实现一下Apriori算法吧,实现代码如下,其中GenC为生成候选项集的函数,GenL为生成频繁项集的函数,GenComb从给定的元素中生成取k个元素的所有组合。(太虐心了,写了一下午-_-)

    import copy
    SPLITTER = '-'
    # 生成集合keys中取k个元素的所有组合
    def GenComb(keys, k):
        if k == len(keys):
            return sorted([keys])
        res = GenComb(keys[1:], k)
        length = len(res)
        for i in range(length):
            for j in range(len(res[i])):
                tmp = copy.deepcopy(res[i])
                tmp[j] = keys[0]
                res.append(sorted(tmp))
        new_res = []
        # 去除重复的组合
        for i in res:
            if i not in new_res:
                new_res.append(i)
        return new_res
    # 计算第0个频繁项集,从0开始计数
    def GenL0(D, NUM, min_sup):
        l = {}
        for i in range(NUM):
            sup = sum([ lst[i] for lst in D ])
            if sup >= min_sup: 
                l[str(i)] = sup
        return l
    # 计算候选的项集
    def GenC(D, l, k):
        if len(l) == 1:
            return None
        c = {}
        keys_dict = {}
        for i in l:
            for j in i.split(SPLITTER):
                keys_dict.update({j:0})
        comb = GenComb(list(set(keys_dict)), k)
        for i in comb:
            for record in D:
                flag = True
                for k in i:
                    if record[int(k)] == 0:
                        flag = False
                        break
                key = str(i).replace(', ', SPLITTER).replace('[', '').replace(']', '').replace('\'', '')
                if flag:
                    if c.has_key(key):
                        c[key] += 1
                    else:
                        c[key] = 1
        return c
    # 计算由c生成的频繁项集
    def GenL(c, min_sup):
        l = {}
        for i in c:
            if c[i] >= min_sup:
                l[i] = c[i]
        return l
    def Apriori(D, NUM, min_sup):
        L = []
        l = GenL0(D, NUM, min_sup)
        L.append(l)

        k = 1
        while l:
            c = GenC(D, L[k-1], k+1)
            if c:
                l = GenL(c, min_sup)
                L.append(l)
            else:
                break
            k += 1
        return L
    if __name__ == '__main__':
        D = [
        #    A B C D E
            [1,0,1,1,0],
            [0,1,1,0,1],
            [1,1,1,0,1],
            [0,1,0,0,1]
            ]
        NUM = len(D[0])
        min_sup = 0.5*len(D)
        print Apriori(D, NUM, min_sup)

Apriori算法改进

但是,我们也发现了Apriori算法的一些问题:

  1. 要对数据进行多次扫描
  2. 产生了大量的候选项集
  3. 对候选项集的支持度计算非常繁琐

所以,就有了一些改进算法的方法:

  1. 基于Hash表的项集计数
  2. 事务压缩
  3. 划分
  4. 选样
  5. 动态项集计数

经过分析,我们发现Apriori算法的主要开销在于产生大量候选集和重复扫描数据库(通过模式匹配来检查一个很大的候选集合)。

FP-tree算法

FP-tree(Frequent Pattern Tree)算法与Apriori算法不同,它是把原始信息(一般是数据库的事务信息)保存(压缩)到一棵树(FP-tree,即频繁模式树),然后对这个树进行关联规则的挖掘。当然,挖掘的结果同样是频繁项集。FP-tree使用的是divide-and-conquer思想,学算法好有用!

通过一个例子可以理解FP-tree算法的思想,算法示例如下(摘自王灿老师PPT),最小支持度为50%,所以最小计数应该为5x50%≈3。

前两列是数据库中存储是事务信息,先不要管第三列。我们首先要根据数据库的信息导出频繁1-项集,并按照降序排列,这个和Apriori的L1差不多,只不过是排好序了,注意最小计数为3,如下图。

有了这个排序的频繁1-项集,就可以得到第一个图的第三列了。第三列是这个频繁1-项集和每一条事务记录的交集,并且按照频繁1-项集的顺序进行排列。

以上做的这些,都是在为构造一颗FP-tree做准备。现在可以构造出这课树了。我们使用一个叫做null的节点作为根节点。然后依次读取每一天事务记录的频繁项集,并添加节点。节点使用key-value的格式,第一次添加时value为1。很显然,当读取第二、第三等后续的记录时,有些节点已经添加过,所以此时无需重复添加节点,只需把value值加1即可,如下图。

经过若干次添加节点以后,我们就有了这课FP-tree。注意上面的频繁1-项集,上面写着frequency head。其实,这个频繁1-项集构成的表就是项头表。我们的最后一项任务就是把这个项头表和FP-tree“合体”,如下图。

项头表和FP-tree合体的方式是通过把表的每一条记录都指向树的节点,如果有多个节点,则把它们“串联”起来。

至此,我们的所有准备工作已经完成。我们开始对这个树进行频繁模式的挖掘。

挖掘是从项头表的底部开始,即支持度计数小的开始,也就是从p开始。我们可以得到p-条件模式基:fcam:2、cb:1。可以看到,挖掘的方法就是从根部到p的路径上,记录下沿途经过的节点。对于p来说,有两条路径到达p,因为有2个p。所以就有了fcam和cb,2和1是由p决定的。通过这样的方式,就可以分别得到p、m、b、a、c、f的条件模式基。

为什么要得到条件模式基?“基”就是基础的意思,有了个这个条件模式基,就可以生成所有的频繁模式。

下面来生成所有的频繁模式。对于p来说,p-条件模式基为fcam:2、cb:1。我们对这两个进行累计计数,得到2个f,3个c,2个a,2个m,1个b。因为最小支持计数为3,所以只有c符合要求,根据p-条件模式基生成的频繁模式就是p、cp。

再考察一下根据m-条件模式基生成频繁模式。m-条件模式基为:fca:2、facb:1。经过累计计数,可以得到3个f、3个c、3个a。所以根据m-条件模式基生成的频繁模式就是:m、fm、cm、am、fcm、fam、cam、fcam。

同理,可以得到所有出现在项头表中每个元素的条件模式基,并生成相应的频繁模式。感觉这个算法用python不是很好写啊,以后再写吧o(╯□╰)o

总结一下FP-tree算法的过程吧。

要先有一个1-项集递减排序组成的项头表。根据这个表来得到每条事务记录的项集,当然,这个项集也要按照项头表的顺序来排序。

有了项头表,也有了排序好的项集,就可以构造FP-tree啦。树的根节点是null,然后根据每一条事务对应的项集来添加节点,节点是key-value类型的。鼓捣完这棵树以后,还需要把项头表和FP-tree合体,合体就是用表的元素指向树的节点,依次串联起树的所有节点。

然后就是对这棵FP-tree进行频繁模式的挖掘。挖掘的顺序是从项头表的底部开始,由FP-tree得到某节点的条件模式基,然后生成频繁模式。

所以,别小看了这个项头表,它时刻在发光呢。对比Apriori,FP-tree挖掘出来的是符合最小支持度的频繁模式,Apriori挖掘出来的是符合最小支持度的频繁项集。有点绕,频繁项集也是一种频繁模式,总之里面包括满足最小支持度的元素,也就是同时出现的次数太多了,满足了最小支持度设定的门槛,获得了晋级。

但是,这仅仅是获得了最小支持度的认可,以后能不能成为关联规则(如买啤酒的人大部分会买卫生纸),还要看最小置信度。

多层、多维关联规则挖掘

多层关联规则挖掘

什么是单层,什么是多层?买啤酒的人大多也买卫生纸,这是单层。买青岛啤酒的人大多会买卫生纸和买啤酒的人大多会买卫生纸,这就是多层。

可以看到,多层指的是概念分层里的“层”。为什么要进行多层的关联规则挖掘呢?

因为,我们不一定喜欢在同一层次上得到的关联规则。比如,买数码产品的人也可能会买床上用品。这样的规则就太模糊了。再比如,买华为路由器的人也可能买青岛啤酒。这样的话就太详细了,看到这样的规则我们肯定想知道买路由器和啤酒的关系是什么样的。

所以,多层的挖掘是有必要的。

但是,有一个问题,随着概念分层层次的降低,支持度会变小(因为所有低层次的概念都可以用高层次的概念替换)。我们挖掘的参考依据最小支持度还合适吗?设置的太大,上层的挖掘就有点粗略了。设置的太小,下层的挖掘就太“狠”了。

所以,就有了使用一致支持度递减支持度分组的最小支持度挖掘方法。

多层挖掘有好的地方,也有不好的地方。比如,我们得到了两条规则:买啤酒的人可能买卫生纸;买青岛啤酒的人可能买卫生纸。这样就出现了规则的冗余。很显然,第一条规则更有价值。

多维关联规则挖掘

什么是单维,什么是多维?我们前面一直说“买”东西的事情,这就是单维,因为谓词只有一个,就是“买”。

这样情况就是多维的规则:买啤酒的人更有可能是中年男人。

当然,也可能是这样的规则:买啤酒和卫生纸的人更有可能是中年男人。(因为有两个“买”,所以又称作混合维关联规则。如果只有一个“买”,就称作维间关联规则..好蛋疼)

还有更蛋疼的..如果属性是一种事物的名称,如啤酒、卫生纸,这样的就叫做“标称”属性。如果属性是数值类型的,如100元、30岁,这样的属性就叫做“量化”属性。

对于标称属性,我们可以使用概念分层属性离散化,使用数据立方体就可以了,有上钻下卷什么的。

不管怎样,一旦和数据立方体关联了,挖掘就很方便了。支持度的求解可以通过数据立方体的操作来计数出来,如果数据立方体已经物化了,就会更方便快捷了。

对于量化属性,我们也可以对其离散化,根据数值分布、聚类等方式把数值映射到某个区间,再对区间进行编号或者命名,然后进行挖掘。可以使用数据立方体或者ARCS(关联规则聚类系统)来挖掘。

-- EOF --