精华内容
下载资源
问答
  • 关联规则挖掘

    2017-08-03 14:25:12
    关联规则挖掘

    关联规则挖掘是推荐技术的基础。

    数据表示:
    全项集:I={i1,i2,…im} (商品库)
    交易t:记录一次交易中顾客购买的所有元素(t∈I)
    交易数据集 T ={t1,t2,…,tn}
    如:超市交易数据集:
    t1:{面包,牛奶,果酱}
    t2:{苹果,香蕉,鸡蛋,牛肉}

    tn:{鸡蛋,牛肉,牛奶}
    k 项集:有 k 个元素组成的集合。
    关联规则:X→Y (这便是我们要挖掘出来的)
    X,Y 是项集,X,Y∈I 且 X∩Y=ø

    规则强度指标

    支持度(Support):交易数据集中同时包含X和Y的交易占所有交易的比例。
    对关联规则普遍性的衡量。
    support=(XUY).countn
    置信度(Confidence):交易数据集中同时包含X和Y的交易占所有包含 X 的交易的比例。
    对关联规则准确性的衡量。
    confidence=(XUY).countX.count

    支持数(Support count):项集 X 的支持数(X.count)指交易数据集中所有包含 X 的交易的数量。

    如果 A→B 的confidence 为100%,说明买A的用户一定会买B。那么 B→A的confidence 也可能很小,因为分子相同,分母不同。B可能是一个流行度非常高的商品。推荐系统需要新颖度,如果B是每个用户都必买的(比如矿泉水),那么就没有必要给用户推荐。推荐系统要挖掘用户不知道但感兴趣的东西。给用户惊喜。可以对商品做一个流行度的惩罚。
    

    关联规则挖掘

    找出满足给定的最小支持度(minimum support,minsup)和最小置信度(minimum confidence,minconf)的关联规则。

    给定交易数据集,minsup and minconf ,结果规则集合是唯一的。

    算法通常分两步:
    1. 挖掘满足minsup 的所有项集(频繁项集,frequent itemset)
    2. 利用frequent itemset 生成minconf 的关联规则。

    Apriori 算法
    input:交易数据集T;minsup
    output: frequent itemset L

    算法:
    1. 找出频繁 1 项集L1。
    2. 利用频繁 k 项集生成候选频繁 k+1 项集Ck+1。
    3. 过滤Ck+1 中不满足的 minsup 要求的项集,等到Lk+1。
    4. 循环步骤2-3,知道Lk+1 为空。
    Apriori 算法过程实例
    要求:最小支持数为 2

    交易数据集T

    transaction itemts
    T1 I1,I2,I5
    T2 I2,I4
    T3 I2,I3
    T4 I1,I2,I4
    T5 I1,I3
    T6 I2,I3
    T7 I1,I3
    T8 I1,I2,I3,I5
    T9 I1,I2,I3

    扫描T,对每个候选集计数
    C1

    项集 支持数
    {I1} 6
    {I2} 7
    {I3} 6
    {I4} 2
    {I5} 2

    过滤不满足minsup 要求的候选集得到L1
    L1

    项集 支持数
    {I1} 6
    {I2} 7
    {I3} 6
    {I4} 2
    {I5} 2

    有L1 产生候选集C2
    C2

    候选项集
    {I1I2}
    {I1I3}
    {I1I4}
    {I1I5}
    {I2I3}
    {I2I4}
    {I2I5}
    {I3I4}
    {I3I5}
    {I4I5}

    注意对项集进行排序,尽量让左边项相同。

    扫描T,对每个候选集计数(注意:每次在计数时需要在原始交易数据集中扫描,很耗性能)

    C2

    项集
    {I1I2} 4
    {I1I3} 4
    {I1I4} 1
    {I1I5} 2
    {I2I3} 4
    {I2I4} 2
    {I2I5} 2
    {I3I4} 0
    {I3I5} 1
    {I4I5} 0

    过滤不满足minsup 的候选集

    L2

    {I1I2} 4
    {I1I3} 4
    {I1I5} 2
    {I2I3} 4
    {I2I4} 2
    {I2I5} 2

    由L2产生候选集C3

    候选项集
    I1,I2,I3
    I1,I3,I5

    注意:
    1. 在链接时,我们只需链接那些只有最后一项不同的项(理由和剪枝一样)。
    2. 这里用了剪枝。
    在C3 中每一项的所有两两组合都应该在L2中存在,如果不在那么他可定不满足最小支持度,所在在这里做剪枝。减少后边在统计支持数时,对交易数据集扫描次数。

    扫描T,对每个候选集计数
    C3

    项集 支持数
    I1,I2,I3 2
    I1,I3,I5 2

    过滤不满足minsup要求的候选集

    L3

    项集 支持数
    I1,I2,I3 2
    I1,I3,I5 2

    由于L3,生成C4
    剪枝后C4为null,得到最终 frequest itemset 是 L1+L2+L3

    算法代码
    这里写图片描述

    候选集生成代码
    候选集生成代码

    关联规则生成
    得到频繁项集后,再生成关联规则

    方法:对一个频繁项集X,设A为X的一个非空子集,B=X-A,则A→B就是一条关联规则,如果其满足最小置信度条件。
    support(A→B)=support(A∪B)=support(X)
    confidenct(A→B)=support(A∪B)/support(A)

    Apriori 算法缺点:
    1. 需要生成大量的候选 ( 耗内存 )
    2. 需要频繁扫描交易数据集 (耗性能)

    FP-Growth 算法

    频繁模式增长(Frequent-Pattern Growth)
    是对Priori 算法的一种优化。优化了Apriori 的两个缺点。

    步骤:
    1. 从交易数据集构造FP树 (精简表示了交易数据集的信息)
    2. 从FP树挖掘频繁模式
    1. 生成条件模式库
    2. 产生条件 FP 树
    FP-Tree 生成

    最小支持数为 3
    这里写图片描述

    扫描交易数据集,得到频繁1项集(包含了过滤不满minsup 项)红框中的数据(注意已经排序降序)。
    安装L1 中顺序对所有交易中项排序(降序),同时去掉非频繁项(L1不包括的项)就是(ordered)frequent items 列。

    构造FP-Tree
    这里写图片描述

    注意:根节点为null
    将(ordered)frequent items,从根节点依次插入树中,如果按照frequant Items 项的顺序插入时,树中以后此节点,那么加 1.

    我们经常需要统计FP-Tree中 p 一共多少个节点。我们需要将树遍历一边才知道。这样是很大浪费。于是我们要建立一个索引(头表)
    如图:头表将 L1 所有项在PF-Tree中串起来。便于查找。
    这里写图片描述

    展开全文
  • 第三章 关联规则挖掘理论和算法;第三章 关联规则挖掘理论和算法;3.1 基本概念与解决方法;支持度与频繁项目集 ;支持度与频繁项目集 ;可信度与关联规则;关联规则挖掘基本过程;第三章 关联规则挖掘理论和算法;项目集格...
  • 关联规则挖掘可以让我们从数据集中发现项与项(item 与 item)之间的关系,它在我们的生活中有很多应用场景,“购物篮分析”就是一个常见的场景,这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系,进而...

    4d7dface2b674a2702273fdd21e522ce.png

    关联规则挖掘可以让我们从数据集中发现项与项(item 与 item)之间的关系,它在我们的生活中有很多应用场景,“购物篮分析”就是一个常见的场景,这个场景可以从消费者交易记录中发掘商品与商品之间的关联关系,进而通过商品捆绑销售或者相关推荐的方式带来更多的销售量。所以说,关联规则挖掘是个非常有用的技术。
    比如你打开京东的沃尔玛超市,在里面搜索尿布,拉到最下面就能惊奇地发现有啤酒的推荐。但是你在别的超市或者在生活中的实体超市可能看不到这种情况。
    一个超市购物的例子,下面是几名客户购买的商品列表:

    a8595159f13dd89052850798876ffd7c.png

    关于关联规则有三个比较重要的概念,可以结合上面的图表进行说明。什么是支持度?
    支持度是个百分比,它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高,代表这个组合出现的频率越大。在这个例子中,我们能看到“牛奶”出现了 4 次,那么这 5 笔订单中“牛奶”的支持度就是 4/5=0.8。同样“牛奶 + 面包”出现了 3 次,那么这 5 笔订单中“牛奶 + 面包”的支持度就是 3/5=0.6。什么是置信度?
    它指的就是当你购买了商品 A,会有多大的概率购买商品 B,在上面这个例子中:置信度(牛奶→啤酒)=2/4=0.5,代表如果你购买了牛奶,有多大的概率会购买啤酒?所以说置信度是个条件概念,就是说在 A 发生的情况下,B 发生的概率是多少,相当于一种条件概率。(还有一个置信区间,记得区分下)什么是提升度?
    我们在做商品推荐的时候,重点考虑的是提升度,因为提升度代表的是“商品 A 的出现,对商品 B 的出现概率提升的”程度。
    还是看上面的例子,如果我们单纯看置信度 (可乐→尿布)=1,也就是说可乐出现的时候,用户都会购买尿布,那么当用户购买可乐的时候,我们就需要推荐尿布么?实际上,就算用户不购买可乐,也会直接购买尿布的,所以用户是否购买可乐,对尿布的提升作用并不大。
    我们可以用下面的公式来计算商品 A 对商品 B 的提升度:
    提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)
    这个公式是用来衡量 A 出现的情况下,是否会对 B 出现的概率有所提升。所以提升度有三种可能:
    提升度 (A→B)>1:代表有提升;
    提升度 (A→B)=1:代表有没有提升,也没有下降;
    提升度 (A→B)<1:代表有下降。
    因此根据公式可以计算出
    提升度(尿布->啤酒) = (2/5)/(2/5) = 1
    提升度(牛奶->啤酒) = (2/4)/(2/5) = 5/4
    这里显示牛奶对啤酒地提升更大,而尿布对啤酒并没有什么提升。但这里只是单纯地举个例子,并不代表实际情况,因此没有实际的参考价值,只是为了进行概念的说明。并且也可以说不同国家相差也会很大,并不一定有沃尔玛超市的那个情况。Apriori算法
    首先我们把上面案例中的商品用 ID 来代表,牛奶、面包、尿布、可乐、啤酒、鸡蛋的商品 ID 分别设置为 1-6,上面的数据表可以变为:

    0cf62ee19e08acf6f92ad149a2e2ffc0.png

    Apriori 算法其实就是查找频繁项集 (frequent itemset) 的过程,所以首先我们需要定义什么是频繁项集。
    频繁项集就是支持度大于等于最小支持度 (Min Support) 阈值的项集,所以小于最小值支持度的项目就是非频繁项集,而大于等于最小支持度的项集就是频繁项集。
    项集这个概念,英文叫做 itemset,它可以是单个的商品,也可以是商品的组合。我们再来看下这个例子,假设我随机指定最小支持度是 50%,也就是 0.5。
    首先,我们先计算单个商品的支持度,也就是得到 K=1 项的支持度:

    61bca42db62808ffdab2cad63ac23d82.png

    因为最小支持度是 0.5,所以你能看到商品 4、6 是不符合最小支持度的,不属于频繁项集,于是经过筛选商品的频繁项集就变成:

    72116f1992d741fd1ecff167af9a75d5.png

    在这个基础上,我们将商品两两组合,得到 k=2 项的支持度:

    3bc78c670e5e78fb5572fe182d79f0bf.png

    我们再筛掉小于最小值支持度的商品组合,可以得到:

    3c8042ab034555b6201cb29b53c5c5a7.png

    我们再将商品进行 K=3 项的商品组合,可以得到:

    0bf72c48f0f28093c47613415d20b323.png

    再筛掉小于最小值支持度的商品组合,可以得到:

    6328b8519535321c557b222e94c120c4.png

    到这里可以将上面的计算流程表达如下:

    1. K=1,计算 K 项集的支持度;
    2. 筛选掉小于最小支持度的项集;
    3. 如果项集为空,则对应 K-1 项集的结果为最终结果。否则 K=K+1,重复 1-3 步。

    FP-Growth 算法
    我们刚完成了 Apriori 算法的模拟,你能看到 Apriori 在计算的过程中有以下几个缺点:

    1. 可能产生大量的候选集。因为采用排列组合的方式,把可能的项集都组合出来了;(浪费空间)
    2. 每次计算都需要重新扫描数据集,来计算每个项集的支持度。(浪费时间)

    改进的方法,FP-Growth 算法

    1. 对于数据浪费存储空间的问题,可以使用FP存储繁项集,只要是数据存储基本就是树了,二叉树不行就多叉树;比如最开始的Word2Vec的哈夫曼树存储单词词频,或者是数据库的B树,B+树都是如此。唯一变的就是树的设计规则。
    2. 对于计算问题,FP-Growth整个生成过程只用遍历数据两遍。

    FP树的创建过程如下:创建项头表(item header table),创建项头表的作用是为 FP 构建及频繁项集挖掘提供索引。
      这一步的流程是先扫描一遍数据集,对于满足最小支持度的单个项(K=1 项集)按照支持度从高到低进行排序,这个过程中删除了不满足最小支持度的项。项头表包括了项目、支持度,以及该项在 FP 树中的链表。初始的时候链表为空。
      这里其实也和Word2Vec的哈夫曼树创建类似,不过在时间上应该是FP树更早。Word2vec将单词按照词频从小到大排序,然后依次构造出哈夫曼树,对词频太少的也可以进行一定的过滤。但是最终发明了更高效的办法,负采样。而FP树是从大到小排列,进行构造。

    120a6fcc83d4300dc029a940710aab5c.png

    构造 FP 树,FP 树的根节点记为 NULL 节点。
      整个流程是需要再次扫描数据集,对于每一条数据,按照支持度从高到低的顺序进行创建节点(也就是第一步中项头表中的排序结果),节点如果存在就将计数 count+1,如果不存在就进行创建。同时在创建的过程中,需要更新项头表的链表。这里需要注意的是,构建的时候,在每一条数据的内部要先按照之前统计出的支持度进行排序。

    c51353e1d7e7f7628108df349c95a372.png

    比如对第一条数据,牛奶面包尿布,排序后为尿布牛奶面包, 按照这个顺序创建节点。尿布不在,因此创建,而牛奶面包也不在也是单独创建并更新链表头。更具体的可以参见知乎另一篇代码拆解.通过 FP 树挖掘频繁项集
      到这里,我们就得到了一个存储频繁项集的 FP 树,以及一个项头表。我们可以通过项头表来挖掘出每个频繁项集。具体的操作会用到一个概念,叫“条件模式基”,它指的是以要挖掘的节点为叶子节点,自底向上求出 FP 子树,然后将 FP 子树的祖先节点设置为叶子节点之和。
    以“啤酒”的节点为例,从 FP 树中可以得到一棵 FP 子树,将祖先节点的支持度记为叶子节点之和,得到:

    0041d971dd092b0ade00211f371ae7a8.png

    当然 Apriori 的改进算法除了 FP-Growth 算法以外,还有 CBA算法、GSP算法。实际使用
    sklearn里并没有上述两种算法, 需要使用时需要独立安装对应的库,这里直接使用pip install efficient-apriori就行。
    核心的代码就这一行

    itemsets, rules = apriori(data, min_support,  min_confidence)

    对于上面啤酒的例子:

    # -*- coding: utf-8 -*-
    from efficient_apriori import apriori
    # 设置数据集
    data = [('牛奶','面包','尿布'),
               ('可乐','面包', '尿布', '啤酒'),
               ('牛奶','尿布', '啤酒', '鸡蛋'),
               ('面包', '牛奶', '尿布', '啤酒'),
               ('面包', '牛奶', '尿布', '可乐')]
    # 挖掘频繁项集和频繁规则
    itemsets, rules = apriori(data, min_support=0.5,  min_confidence=1)
    print(itemsets)
    print(rules)
    

    运行结果

    {1: {('啤酒',): 3, ('尿布',): 5, ('牛奶',): 4, ('面包',): 4}, 2: {('啤酒', '尿布'): 3, ('尿布', '牛奶'): 4, ('尿布', '面包'): 4, ('牛奶', '面包'): 3}, 3: {('尿布', '牛奶', '面包'): 3}}
    [{啤酒} -> {尿布}, {牛奶} -> {尿布}, {面包} -> {尿布}, {牛奶, 面包} -> {尿布}]

    挖掘导演是如何选择演员的

    在实际工作中,数据集是需要自己来准备的,比如今天我们要挖掘导演是如何选择演员的数据情况,但是并没有公开的数据集可以直接使用。因此我们需要使用之前讲到的 Python 爬虫进行数据采集。不同导演选择演员的规则是不同的,因此我们需要先指定导演。数据源我们选用豆瓣电影。

    数据抓取

    # -*- coding: utf-8 -*-
    # 下载某个导演的电影数据集
    from efficient_apriori import apriori
    from lxml import etree
    import time
    from selenium import webdriver
    import csv
    driver = webdriver.Chrome()
    # 设置想要下载的导演 数据集
    director = u'宁浩'
    # 写CSV文件
    file_name = './' + director + '.csv'
    base_url = 'https://movie.douban.com/subject_search?search_text='+director+'&cat=1002&start='
    out = open(file_name,'w', newline='', encoding='utf-8-sig')
    csv_write = csv.writer(out, dialect='excel')
    flags=[]
    # 下载指定页面的数据
    def download(request_url):
      driver.get(request_url)
      time.sleep(1)
      html = driver.find_element_by_xpath("//*").get_attribute("outerHTML")
      html = etree.HTML(html)
      # 设置电影名称,导演演员 的XPATH
      movie_lists = html.xpath("/html/body/div[@id='wrapper']/div[@id='root']/div[1]//div[@class='item-root']/div[@class='detail']/div[@class='title']/a[@class='title-text']")
      name_lists = html.xpath("/html/body/div[@id='wrapper']/div[@id='root']/div[1]//div[@class='item-root']/div[@class='detail']/div[@class='meta abstract_2']")
      # 获取返回的数据个数
      num = len(movie_lists)
      if num > 15: #第一页会有16条数据
        # 默认第一个不是,所以需要去掉
        movie_lists = movie_lists[1:]
        name_lists = name_lists[1:]
      for (movie, name_list) in zip(movie_lists, name_lists):
        # 会存在数据为空的情况
        if name_list.text is None: 
          continue
        # 显示下演员名称
        #print(name_list.text)
        names = name_list.text.split('/')
        # 判断导演是否为指定的director
        if names[0].strip() == director and movie.text not in flags:
          # 将第一个字段设置为电影名称
          names[0] = movie.text
          flags.append(movie.text)
          csv_write.writerow(names)
      print('OK') # 代表这页数据下载成功
      print(num)
      if num >= 14: #有可能一页会有14个电影
        # 继续下一页
        return True
      else:
        # 没有下一页
        return False
    
    # 开始的ID为0,每页增加15
    start = 0
    while start<10000: #最多抽取1万部电影
      request_url = base_url + str(start)
      # 下载数据,并返回是否有下一页
      flag = download(request_url)
      if flag:
        start = start + 15
      else:
        break
    out.close()
    print('finished')

    在Windows下运行这段代码可能会报错: 显示的报错信息如下:

    selenium.common.exceptions.WebDriverException: Message: Service chromedriver.exe unexpect

    针对这个问题有如下解决方案

    • 在chrome输入chrome://version/, 第一行就是你的浏览器的版本Google Chrome80.0.3987.163(正式版本)(64 位)(cohort: Stable)
    • 根据这个版本到这里下载 , win32的就可以,如果是Windows下的话
    • 下载好后, 有两种方法引入这个driver, 可以配置对应的环境变量,具体参考这里 , 第二种直接在代码里更改driver = webdriver.Chrome("D:Pythonchromedriver_win32chromedriver.exe")

    对得到数据进行关联分析

    # -*- coding: utf-8 -*-
    from efficient_apriori import apriori
    import csv
    director = u'宁浩'
    file_name = './'+director+'.csv'
    lists = csv.reader(open(file_name, 'r', encoding='utf-8-sig'))
    # 数据加载
    data = []
    for names in lists:
         name_new = []
         for name in names:
               # 去掉演员数据中的空格
               name_new.append(name.strip())
         data.append(name_new[1:])
    # 挖掘频繁项集和关联规则
    itemsets, rules = apriori(data, min_support=0.5,  min_confidence=1)
    print(itemsets)
    print(rules)

    得到结果:

    {1: {('田启文',): 4, ('李尚正',): 3}} 
    []

    这里就是支持度设置的过大,而且实际上我们也知道, 周星驰自己导演的电影并不算多, 虽然他参演的电影都是经典作品。然后也可以看到可以去百度下这两个人, 其中的李尚正就很熟悉, 比如美人鱼里和文章一起的另一个警察。更多的的也可参见这里。

    参考博客:

    https://blog.csdn.net/susht/article/details/51457158

    https://blog.csdn.net/u013007900/article/details/54890950

    https://time.geekbang.org/column/article/82628?gk_activity=0

    https://blog.csdn.net/baixiangxue/article/details/80335469

    https://zhuanlan.zhihu.com/p/60984376

    展开全文
  • 关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree关联规则挖掘 FP-tree
  • 数据挖掘进阶之关联规则挖掘FP-Growth算法 绪 近期在写论文方面涉及到了数据挖掘,需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用...

    数据挖掘进阶之关联规则挖掘FP-Growth算法

    近期在写论文方面涉及到了数据挖掘,需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用基于有趣性度量标准的FP-Growth算法,序列模式挖掘使用基于有趣性度量标准的GSP算法。若想实现以上优化算法,首先必须了解其基本算法,并编程实现。关键点还是在于理解算法思想,只有懂得了算法思想,对其进行优化操作易如反掌。源代码方面,其实是自己从网络中查找并进行阅读,在理解的基础上进行优化。下面首先介绍一下基本的FP-Growth算法的实现过程:

    原理介绍

    基本思路:不断地迭代FP-tree的构造和投影过程。

    对于每个频繁项,构造它的条件投影数据库和投影FP-tree。对每个新构建的FP-tree重复这个过程,直到构造的新FP-tree为空,或者只包含一条路径。当构造的FP-tree为空时,其前缀即为频繁模式;当只包含一条路径时,通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。

    算法实现

    本算法采用Java实现,主要根据序列模式的情况,算法共有2个类:

    MyFptree类:算法核心类。FP-Growth算法的核心操作:建树挖掘频繁项操作都在这里实现。在使用该算法时,也是需要通过使用该类的方法来实现GSP算法。

    TreeNode2类:元素类。在本算法实现中,元素类中含有元素属性集,在使用时也是使用该属性。另外,在该类中还封装了对元素的操作以及一些其他操作。

    有关源码请点击下载

    有关序列模式挖掘的GSP算法,详见鄙人博客中“数据挖掘进阶之序列模式挖掘GSP算法”一文。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,173
精华内容 1,669
关键字:

关联规则挖掘