ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据堆栈大作业--频繁模式挖掘 [打印本页]

---

作者: 卖不甜枣    时间: 2024-11-17 09:59
标题: 数据堆栈大作业--频繁模式挖掘
数据堆栈大作业--频繁模式挖掘

1. 实行综述

关联分析常常用于从大规模数据库中探求元素的隐含关系，是数据堆栈中数据挖掘的最常用的方法。本实行旨在实现基本的数据挖掘算法（Apriori算法），选取部分数据集数据进行挖掘。在探寻数据隐含关系的同时，试图评估数据挖掘算法的性能和特性。
本陈诉主要包括以下部分：

• 实行原理（包括算法详细形貌、算法特点等）
  
• 实行环境搭建（数据集的选取、挖掘的问题、编程环境简述）
  
• 实行发现
  
• 算法性能分析
  

本陈诉的核心亮点：

• 实现了Apriori算法，并对算法效率进行了实证性研究，应用了埋伏解决方案。
  
• 进行了多粒度的数据挖掘（选取了句子和段落作为两种篮子，并比较二者区别）。
  
• 探索了多个支持度值的应用大概。
  
• 进行了多数据集的应用（GutenBerg &&DBLP），对每个数据集进行了多个问题多个角度的研究探讨。
  

2. 实行原理

大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘使命分解为两个主要的子使命 – 频繁项集产生（发现满足最小支持度阈值的所有项集），规则的产生（从上一步发现的频繁项集中提取所有高置信度的规则）。
此中，频繁项集产生所需的计算开销远大于产生规则所需的计算开销。因此，在关联规则挖掘中遇到的主要问题是加速频繁项集的产生。
在本部分中，将对本次实行选取的数据挖掘算法 – Apriori算法睁开详细形貌。
2.1 Apriori算法原理

Apriori算法主要基于两个定律：
Apriori定律1：如果一个聚集是频繁项集，则它的所有子集都是频繁项集。
Apriori定律2：如果一个聚集不是频繁项集，则它的所有超集都不是频繁项集。
因此，可以采用条理序次的方法来实现频繁项集的挖掘。
起首，挖掘一阶频繁项集L1，在此底子上，形成二阶候选项集；然后进行二阶频繁项集的挖掘；以此类推。主要靠“生成候选集–裁剪–计数”的流程。
算法形貌如下：

1. 1 令 k=1
2. 2 生成K阶频繁项集
3. 3 循环直到没有频繁项集产生:
4. 4         从K阶频繁项集生成K+1阶频繁项集的候选集
5. 5         对K+1阶频繁项集的候选集进行剪枝，如果一个候选频繁项有子集不是k阶频繁项，那么这个候选频繁项也不是频繁项
6. 6         对K+1阶频繁项集的候选集进行筛选，挑选出符合最小支持度要求的频繁项

复制代码

2.2 Apriori算法性能

Apriori算法的性能不高，频繁项集大概出现爆炸征象。对于                                   N                              N                  N个事务，大概出现时间上和空间上                                   O                         (                                   N                            2                                  )                              O(N^2)                  O(N2)的复杂度。因此如果选择的最小支持度较小，会出现内存爆炸的征象。
因此，对于Apriori算法，需要着重关注怎样降低计算速度，以及淘汰频繁项集的数目。本实行关注淘汰频繁项集数目这一点，利用“多最小支持度”进行挖掘。
3. 实行环境搭建及运行

本次环境选取GutenBerg数据集和DBLP数据集进行挖掘，下面分别对各个数据集的筛选和数据预处理等进行说明。
3.1 Gutenburg数据集的模式挖掘

数据集筛选：
​ 林肯演讲集(见/data/Lincoln)
篮子的获取：
①分句：调用nltk工具包对数据集进行分句，收集每个句子的单词，利用克制词去除了常用介词数词等干扰词汇。nltk是一套基于python的自然语言处理工具集，在本次实行中只是调用此中的tokenizer工具进行文本分句。
②分段：直接根据段落空行进行分段。
源代码：
(见/src/Gutenberg/)

1. ------ ls /src/Gutenberg/ -----
2. Associations.py                #获得关联规则，程序主入口
3. Apriori.py                         #获取频繁项集
4. datasetHandle.py         #数据预处理
5. stopwords.txt                #停止词列表
6. ##运行：
7. python Associations.py

复制代码

数据结果：
见/result/Gutenburg，保存了下面实行中的频繁项集。挖掘出的关联规则见本文档。
3.2 DBLP数据集

数据集筛选：
​ 选用数据集是 2007 年以来 IJCAI, AAAI, COLT, CVPR, NIPS, KR, SIGIR,SIGKDD 八个会议的数据集。
​ (见/data/DBLP)
篮子的获取：
​ 按照每条记录。
源代码：
(见/src/DBLP/)

1. ------ ls /src/DBLP/ -----
2. Apriori.py                         #获取频繁项集（由于和Gutenburg基本一致，因此注释较少）
3. dataset.py                         #数据预处理（由于和Gutenburg基本一致，因此注释较少）
4. task1_active.py                #任务1
5. task2_group.py                #任务2
6. task3_topic.py                #任务3
7. #运行：
8. python task1_active.py                #任务1
9. python task2_group.py                #任务2
10. python task3_topic.py                #任务3

复制代码

数据结果：
见/result/DBLP/，保存了各个使命的结果。
4. 实行结论 – GutenBerg – 林肯演讲集：挖掘常用词共同出现

本部分主要研究GutenBerg数据集中林肯演讲集中的常用词是否会有共同出现的趋势。采用多个篮子粒度和多研究角度进行研究。
4.1 Sentence模式：以句子作为Basket进行挖掘

4.1.1 数据集的筛选及关联规则的定义

由于数据集太过巨大，而且范围涵盖多个主题和体裁导致挖掘信息杂糅，因此我选取Gutenberg dataset中Lincoln的演讲集部分作为实行数据，并实行从中挖掘信息。数据集共16个txt文件。起首，把句子作为篮子进行数据挖掘，共31598个句子， 11587个段落
本次实行中，希望挖掘出：
①什么单词组合在同一个句子中出现的概率更高，
②一个单词（或组合）出现后，通常还会出现什么单词。
对置信度定义如下：
                                    c                         o                         n                         f                         i                         d                         e                         n                         c                         e                         =                                              s                               u                               p                               p                               (                                           X                                  1                                                      X                                  2                                          .                               .                               .                                           X                                  z                                          )                                                 s                               u                               p                               p                               (                               X                               1                               X                               2...                                           X                                               z                                     −                                     1                                                      )                                                 confidence = \frac{supp(X_1X_2 ...X_z)}{supp(X1X2...X_{z-1})}                  confidence=supp(X1X2...Xz−1​)supp(X1​X2​...Xz​)​
得到频繁项集之后，探求所有由k项集到(k+1)项集符合最小关联度要求的关联规则。
4.1.2 最小支持度的选取理论

选取最小支持度为0.5%
选取标准：
​ 在预实行中，①选取最小支持度为5%，直接导致一阶频繁项为空；
​ ②选取最小支持度为1%，获得58个一阶频繁项集，3个二阶项集和1个三阶项集，较不充分。
​ ③选取最小支持度为0.5%，获得200个一阶频繁项集，15个二阶项集，和1个三阶项集，比1%时充分了一些。
因此，本实行选取最小支持度为0.5%。
4.1.3 最小置信度的选取理论

选取二阶频繁项集的最小置信度为56%（也就是获得Top10)
选取标准：
​ 在收集完频繁项集之后，我将每个k项集的置信度统计出来，统计结果如下图。
从图中可以看出：
从一项集推二项集（如果一个单词出现，另一个单词出现）的置信度通常比较低，中位数约为20%
从二项集推三项集（如果两个单词出现，另一个单词出现）的置信度通常比较高，中位数约99.75%（只有一个）。
数听说明：
从二项集推三项集的置信度远高于从一项集推二项集的置信度，是由于只有一个关联规则，缺乏代表性。
选择Top10为置信度标准，为56%
4.1.4 挖掘结果

下面针对两个问题分别进行回答
①什么单词组合在同一个句子中出现的概率更高
即研究符合最小支持度的频繁项集。

1. #一阶频繁项集
2. slavery people washington united time government war judge constitution union
3. #二阶频繁项集
4. executive        mansion
5. executive        washington
6. mansion        washington
7. department        war
8. president        united
9. secretary        war
10. constitution        people
11. slavery        territory
12. constitution        slavery
13. people        slavery
14. #三阶频繁项集
15. executive        mansion        washington

复制代码

实行结论：

• 从出现次数较多的单词，可以直接领会文章的主要内容：人民、连合、黑奴、华盛顿，由这些很容易想到是林肯的演讲集。
  
• 从共同出现频率最高的单词对上，可以领会单词常常的用法。
  

②一个单词（或组合）出现后，通常还会出现什么单词
选取符合最小置信度的关联规则，如下：

1. mansion  ============>  executive mansion       Condidence= 1.0
2. mansion washington  ============>  executive mansion washington       Condidence= 1.0
3. executive washington  ============>  executive mansion washington       Condidence= 0.99
4. dred  ============>  dred scott       Condidence= 0.98
5. mansion  ============>  mansion washington       Condidence= 0.84
6. executive mansion  ============>  executive mansion washington       Condidence= 0.84
7. scott  ============>  dred scott       Condidence= 0.83
8. executive  ============>  executive mansion       Condidence= 0.77
9. executive  ============>  executive washington       Condidence= 0.65
10. department  ============>  department war       Condidence= 0.56

复制代码

实行结论：

• 从中可以观察到，前两个关联规则置信度为1，因此可以认为executive总是和mansion起出现；
  
• scott大多数和dred一起出现；dred大多数和scoot一起出现；因此可以推测，这两个每每一起出现。
  
• washington大多和mansion一起出现；war每每和department一起出现。
  

4.2 推广！Paragraph模式：以段落作为Basket进行挖掘

4.2.1 最小支持度和最小置信度的选取

同Sentence模式一样，选取最小支持度为0.5%，结果可以发现701个一阶频繁项集，这个数据太多，以是我决定降低进步置信度。
留意在Sentence模式中，最小置信度为1%时，由于获取频繁项集较少，因此被淘汰。在Paragraph模式中，选用最小支持度为1%时，获得了260个一阶频繁项集，77个二阶频繁项集，3个三阶频繁项集。认为数量刚好。
因此选用最小置信度为1%
得到关联规则的置信度分布如下图：
但是为了和Sentence结果进行对比，仍选取56%作为最小置信度。
4.2.2 挖掘结果及与Sentence模式的对比

选取符合最小置信度的关联规则，如下：

1. mansion  ============>  executive mansion       Condidence= 1.0
2. dred  ============>  dred scott       Condidence= 1.0
3. mansion washington  ============>  executive mansion washington       Condidence= 1.0
4. executive washington  ============>  executive mansion washington       Condidence= 0.99
5. department washington  ============>  department war washington       Condidence= 0.94
6. mansion  ============>  mansion washington       Condidence= 0.84
7. executive mansion  ============>  executive mansion washington       Condidence= 0.84
8. war washington  ============>  department war washington       Condidence= 0.81
9. executive  ============>  executive mansion       Condidence= 0.80
10. scott  ============>  dred scott       Condidence= 0.79
11. representatives  ============>  house representatives       Condidence= 0.75
12. free slave  ============>  free slave slavery       Condidence= 0.70
13. territory  ============>  slavery territory       Condidence= 0.68
14. executive  ============>  executive washington       Condidence= 0.68
15. territories  ============>  slavery territories       Condidence= 0.66
16. department  ============>  department war       Condidence= 0.62
17. slave slavery  ============>  free slave slavery       Condidence= 0.60
18. north  ============>  north south       Condidence= 0.59
19. free slavery  ============>  free slave slavery       Condidence= 0.56
20. slave  ============>  slave slavery       Condidence= 0.54

复制代码

实行结论：

• 在以Paragraph作为Basket时，设定最小支持度，能够发现更多符合最小支持度的频繁项集。我认为这是符合直觉的。由于一句话的长度是有限的，很多出现次数较高的单词并不会在这句话出现，导致单词的支持度降低。
  
• 由于频繁项集更多，在以Paragraph作为Basket时，也能找到更多符合最小置信度要求的关联规则。
  
• 观察在Sentence模式和Paragraph模式发现的关联规则，发现Paragraph模式发现的关联规则包罗了Sentence模式的关联规则，
  
• 综上所述，对这个问题，我认为Paragraph是合适的数据分析的粒度。
  

###4.3 推广！选取多个最小支持度
####4.3.1 问题引入
在Sentence模式中，当我们选取最小支持度为1%时，只能获得58个一阶频繁项集，3个二阶项集和1个三阶项集，较不充分。而留意到一个规律：越高阶的频繁项出现的概率越低。尤其是在文本数据库中，收集如许的二阶项集需要放低最小支持度。
因此提出采用多个最小支持度的标准：一阶频繁项集的最小支持度为1%，二阶及高阶为0.2%。
获得了58个一阶频繁项集，77个二阶频繁项集，3个三阶频繁项集。
####4.3.2 置信度的分布问题
在收集完频繁项集之后，我将每个k项集的置信度统计出来，统计结果如下图。
从图中可以看出：
从一项集推二项集（如果一个单词出现，另一个单词出现）的置信度通常比较低，中位数约为11.85%。
从二项集推三项集（如果两个单词出现，另一个单词出现）的置信度通常比较高，中位数约84.49%。
数据分析：
这个明显的看似错误的差异，是由于最小置信度选取标准的差别导致的。由于一阶项集的最小支持度选为1%，高阶的最小支持度选为0.2%，因此存在明显差异。但是由于我们要探求一个单词（或组合）出现后，通常还会出现什么单词， 因此对高阶项集更关注。以是对这一问题临时不做修正。
选取二阶频繁项集的最小置信度为65%（也就是获得Top10)
4.3.3 挖掘结果

下面针对两个问题分别进行回答
①什么单词组合在同一个句子中出现的概率更高
选取（即获得Top10的关联规则，枚举如下）

1. #出现频率最高的单词(Top 10)：
2. slavery people washington united time government war judge constitution union
3. #出现频率最高的单词对(Top 10)：
4. executive        mansion
5. executive        washington
6. mansion        washington
7. department        war
8. secretary        war
9. president        united
10. constitution        people
11. slavery        territory
12. constitution        slavery
13. people        slavery
14. #出现频率最高的三元组：
15. people        slavery          territory
16. executive        mansion          washington
17. president        proclamation        united
18. department        war  washington

复制代码

②一个单词（或组合）出现后，通常还会出现什么单词

1. mansion  ============>  executive mansion       Condidence= 1.0
2. mansion washington  ============>  executive mansion washington       Condidence= 1.0
3. executive washington  ============>  executive mansion washington       Condidence= 0.99
4. department washington  ============>  department war washington       Condidence= 0.95
5. war washington  ============>  department war washington       Condidence= 0.93
6. executive mansion  ============>  executive mansion washington       Condidence= 0.84
7. mansion  ============>  mansion washington       Condidence= 0.84
8. executive  ============>  executive mansion       Condidence= 0.77
9. people territory  ============>  people slavery territory       Condidence= 0.69
10. executive  ============>  executive washington       Condidence= 0.65

复制代码

实行结论：

• 观察挖掘结果和上面两种模式的对比可以发现，选用多个最小置信度时，挖掘出的关联规则中，二阶项集推三阶项集占比要大大增加。这是由于4.3.2提出的置信度分布问题，由于最小支持度差别，在研究一阶项集和二阶项集的关联规则时，会使得置信度成倍降低。
  
• 二阶项集中拔尖的仍然可以被选出，三阶项集中包罗了Sentence模式和Paragraph模式的关联规则。
  
• 如果要着重关注高阶项集的关联规则，应该采用多个最小支持度的方法。
  

5. 实行结论 – DBLP – 论文团队与主题

5.1 问题形貌及数据集选取

选用数据集是 2007 年以来 IJCAI, AAAI, COLT, CVPR, NIPS, KR, SIGIR,SIGKDD 八个会议的数据集。
**问题1：**每个会议都有本身的“支持者”，也就是在该会议上发表文章的研究者。起首，需要找出每个会议各自的研究者。在此底子上，根据研究者每年发表的文章数，可以判断出哪些研究者仍然是活跃的，而哪些研究者已经不再活跃。
**问题2 ：**有一些研究者常常在一起合作，可以称之为一个“团队”。通过频繁模式挖掘，可以从数据集中找出三个人以上的“团队”。
问题3： 每一篇论文都会涉及到一些主题。可以通过对论文标题进行频繁模式挖掘找出主题词。根据每个团队发表的论文的标题，就可以确定这个团队最常常研究的主题了。
5.2 使命1 – 探求活跃支持者

为了找出每个会议各自的研究者，对数据集进行扫描：
对于数据集的每一条数据， 如果其作者不在会议的研究者中，则添加进去。扫描竣事后，就得到了每个会议全部的 研究者。完整的结果保存在 authors.txt 中。
为了找出活跃的研究者，规定最小支持度为5。同样对数据集进行扫描，统计出每个作者在每个会议上每年发表的文章数。如果一个作者在一个会议上一年发表的文章数大于 5，就认为该作者在该会议上于该年是活跃的。如果一个作者在近来三年（2015、2016、2017 年）在一个会议上至少有一年是活跃的，就认为该作者在该会议上“依然活跃”，否则认为“不再活跃”。
挖掘结果：
完整的活跃研究者结果保存在*author.txt
例如，SIGIR的依然活跃的研究者有：

1. Tat-Seng Chua, Liqiang Nie, Yiqun Liu, Shaoping Ma, Min Zhang, Pavel Serdyukov, Maarten de Rijke, Jimmy J. Lin, Charles L. A. Clarke, Guido Zuccon, Jamie Callan, Jimmy Lin, W. Bruce Croft, Leif Azzopardi, Adam Roegiest, Craig Macdonald, Iadh Ounis, Krisztian Balog, Chenyan Xiong, Jaap Kamps, Hamed Zamani。

复制代码

5.3 使命2 – 探求团队

设定最小支持度为3。
得到每一年发文章数大于等于 3 的三个人以上的“团队”。
完整的团队结果保存在 *****group.txt 中。
例如，2007 年，发文章数大于等于 3 的、三个人以上的“团队”有：

1. 1. Deng Cai, Jiawei Han 0001, Xiaofei He
2. 2. Dou Shen, Qiang Yang 0001, Zheng Chen  
3. 3. Qiang Yang 0001, Jeffrey Junfeng Pan, Sinno Jialin Pan  
4. 4. Wiebe van der Hoek, Michael Wooldridge, Thomas Ågotnes
5. 5. Brian D. Davison 0001, Lan Nie, Baoning Wu  
6. 6. Guy Shani, Solomon Eyal Shimony, Ronen I. Brafman  
7. 7. Junsong Yuan, Ying Wu, Ming Yang
8. 8. Kangmiao Liu, Jiajun Bu, Chun Chen
9. 9. Roberto Cipolla, Tae-Kyun Kim, Shu-Fai Wong  

复制代码

5.4 使命3 -主题与团队

通过对所有会议的所有热门主题进行汇总统计可以得到主题词的参考范围，从中选出具有代表性的几个词作为使命要求事先给定的主题词，之后再根据使命一第二问挑选出来的每年的 团队做一个匹配，即对于每年的每个团队都找出他们常涉猎的主题，
例如 2017 年的部分结 果展示如下：

1. [neural, networks] Hongyuan Zha, Junchi Yan, Xiaokang Yang
2. [learning] Deng Cai, Xiaofei He, Yueting Zhuang, Zhou Zhao
3. [learning] Chunyuan Li, Lawrence Carin, Ricardo Henao, Yunchen Pu
4. [learning] Jianshu Li, Jiashi Feng, Shuicheng Yan, Zhecan Wang
5. [neural, networks] Jiashi Feng, Shuicheng Yan, Xiaodan Liang
6. [neural, networks] Chunyuan Li, Lawrence Carin, Yunchen Pu, Zhe Gan
7. [learning] Guiguang Ding, Jungong Han, Yuchen Guo, Yue Gao
8. [learning] Dan Xu, Elisa Ricci, Nicu Sebe, Wanli Ouyang, Xiaogang Wang
9. [deep, learning] Anton van den Hengel, Chunhua Shen, Lingqiao Liu

复制代码

6. 算法性能分析

Apriori算法的性能不高，频繁项集大概出现爆炸征象。对于                                   N                              N                  N个事务，大概出现时间上和空间上                                   O                         (                                   N                            2                                  )                              O(N^2)                  O(N2)的复杂度。因此如果选择的最小支持度较小，会出现内存爆炸的征象。
因此，对于Apriori算法，需要着重关注怎样降低计算速度，以及淘汰频繁项集的数目。本实行关注淘汰频繁项集数目这一点，利用“多最小支持度”进行挖掘。
6.1 针对Sentence模式的时间复杂度实证研究

在本实行中，我针对Sentence模式的最小支持度，探究Apriori算法所泯灭的时间，从而视图验证复杂度为                                   O                         (                         N                         )                              O(N)                  O(N)的说法。
最小支持度耗时(s)一项集二项集三项集5%1501%9058310.50%331200151 我选取了最小支持度为5%，1%和0.5%，进行他们的耗时研究。发现耗时呈指数增长。
6.2 效率改进–多支持度

留意到一个规律：越高阶的频繁项出现的概率越低。尤其是在文本数据库中，收集如许的二阶项集需要放低最小支持度。
因此提出采用多个最小支持度的标准：一阶频繁项集的最小支持度为1%，二阶及高阶为0.2%。
获得了58个一阶频繁项集，77个二阶频繁项集，3个三阶频繁项集。
最小支持度耗时(s)一项集二项集三项集1%9058311%5958773 对比发现，耗时明显淘汰，而且可以发现更多项集。对比试验数据，发现很多规律都是相同的，因此可以发现有用规律。
7. 试验总结

本陈诉的核心亮点：

• 实现了Apriori算法，并对算法效率进行了实证性研究，应用了埋伏解决方案。
  
• 进行了多粒度的数据挖掘（选取了句子和段落作为两种篮子，并比较二者区别）。
  
• 探索了多个支持度值的应用大概。
  
• 进行了多数据集的应用（GutenBerg &&DBLP），对每个数据集进行了多个问题多个角度的研究探讨。
  

如需代码，请私信接洽

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4