基于FP-Growth的频繁项集挖掘与基于社交图的关联规则挖掘

一、任务简介 1

二、数据集 1

三、基本思路 2

3.1、发掘各个会议的“核心”研究者 2

3.2、挖掘作者之间的合作关系 3

3.3、挖掘导师-学生关系 5

四、正确性验证 5

五、总结 5

?

?

一、任务简介

本次挖掘任务有三个：第一，发掘各个会议的“核心”研究者，具体包括在相应会议上的发表文章数量、活跃时间范围等；第二，挖掘作者之间的合作关系，并使用一定的权值表示合作的紧密程度；第三，挖掘导师-学生关系。

二、数据集

数据来自DBLP的十二个会议从2000年至今的所有论文，十二个会议分别是：{“SDM”:1,?”ICDM”:1,?”ECML/PKDD”:1,?”PAKDD”:1,?”WSDM”:1,?”DMKD”:1,?”CVPR”:1,?”ICML”:1,?”NIPS”:1,?”COLT”:1,?”SIGIR”:1,?”KDD”:1}。对于每一篇论文，提取出来的信息包括：发表的会议名称、发表的时间、论文的题目、论文的作者。

之所以从十五个会议中选择十二个会议，是因为这十二个会议有些共同的特点：第一，<inproceedings>是父标签；第二，可以直接使用<booktitle>标签来判断是否为所关心的会议，比如<booktitle>SDM</booktitle>。

最终提取出来的数据存储在“tranDB.txt”文件中，由于该文件比较大，所提交的文件仅是一个示例，可以通过运行“1xmlParser.py”获取完整数据。该文件中，提供了三种提取XML文件内容的代码，分别是DOMTree、SAX和基于字符串的方式；另外，每篇论文信息被表示成一行，具体格式如下：“confName????\t????year????\t????title????\t????author1|author2|..|authorn”

三、基本思路

3.1、发掘各个会议的“核心”研究者

由于只有四项数据（会议名称、发表时间、论文题目、论文作者），所以这里使用基于规则的方法来判断一个研究者是不是核心研究者；具体的，这里采用某个研究者在某个会议上发表的论文总数作为判断该研究者是否为该会议的核心研究者的依据。当然，还可以通过活跃时间（第一篇论文发表时间到最后一篇论文的发表时间间隔）等指标，但本质是一样的，所以代码没有做这些工作。另外，我们可以使用作者的合作关系图来挖掘核心研究者，以一个作者所代表的顶点的度（出度+入度）作为判断依据，但本质仍是一种基于规则的挖掘。最终结果保存在文件“CoreResearcher.txt”中。

3.2、挖掘作者之间的合作关系

合作关系本质上是一种共现关系，挖掘共现关系的典型方法是FP-Growth算法。FP-Growth算法的挖掘过程并没有什么特别之处，主要有两个数据结构比较有意思。

FP-Growth算法最大的特点是采用了FP-Tree（本质是前缀树）来压缩表示事务数据算法，从而使大量的事务数据能够通过较少的内存无损的表示出来，如果做不到这一点，反复扫描磁盘也就在所难免（实际上，对于挖掘的深入，每次只需要当前频繁项集的条件数据库，这往往是非常小的）。FP-Tree的关键是如何设计Tree?Node，具体实现时，我们采用了五元组，看名字就知道什么意思，不多做解释：

另外，FP-Growth算法还有一个重要的数据结构HeaderTable，其作用是存储全局频繁项集（如果是condition?HeaderTable，则存储当前已经找到的频繁项集）信息，另外，由于要考虑一些全局信息，所以我们具体实现的时候采用了五元组：

对于当前频繁项集的条件数据库，condition?HeaderTable只需要存储如下二元组（因为HeaderTable已经存储了其它全局信息）：

讲完了两个重要的数据结构，再简单说下FP-Growth算法的大致流程：第一，第一遍扫描事务数据库得到HeaderTable；第二，第二遍扫描事务数据库得到FP-Tree；第三，从HeaderTable中支持度最低的频繁项集开始挖掘，每次找到当前频繁项集的条件数据库和condition?HeaderTable，然后在此基础上递归挖掘更大的频繁项集。详细过程参考代码“3FP-Tree.py”。

最后，关于挖掘出的频繁项集，本质上就是作者的合作关系集合，由于每个频繁项集都对应一个支持度，该支持度在一定程度上能够表示合作的紧密程度；另外，还可以通过挖掘关联规则，进一步使用置信度和提升度来表示合作的紧密程度，但代码中没有实现该功能。最终结果保存在文件“finalFreqAuthorPattDict.txt”中。

3.3、挖掘导师-学生关系

和核心研究者类似，在只有四个信息的情况下，很难准确判断谁是导师谁是学生，只能通过一些人为地规则来判定（因为没有ground?truth，所以也不好去学习这些规则）；具体的，我们采用了活跃范围大于六年这个规则，同样，可以再增加发表文章数等规则，但本质一样。详细过程参考代码“3FP-Tree.py”；最终结果保存在文件“TeacherStudentRelationship.txt”中。

四、正确性验证

由于没有ground?truth，只能人工验证。发现无论核心研究者、合作关系还是师生关系，“Philip?S.?Yu”、“Jiawei?Han”、“Christos?Faloutsos”等人都被挖掘出来；另外，关于师生关系，以“Jiawei?Han”老师为例，参考http://dblp.uni-trier.de/pers/hc/h/Han:Jiawei.html发现挖掘出来的人确实都是他的学生。

五、总结

本次作业完成了三个任务：第一，发掘各个会议的“核心”研究者，主要通过基于规则的方法；第二，挖掘作者之间的合作关系，使用了FP-Growth算法；第三，挖掘导师-学生关系，也采用了基于规则的方法。

对于挖掘出来的结果，进行了人工验证，在一定程度上说明结果比较可信。