夜凉如水

机器学习课第三次作业记录

夜凉如水 机器学习数据挖掘Python频繁模式挖掘编程

2017-12-13 周三 晴 北京 清华大学 开始
2017-12-17 周日 晴 北京 清华大学 完成一半
2017-12-29 周五 霾 北京 清华大学 开始另一半
2017-12-31 周日 晴 北京 清华大学 完成

0 作业内容

数据集DBLP 数据库中的IJCAI, AAAI, COLT, CVPR, NIPS, KR, SIGIR, SIGKDD八个会议中从2007年至今的所有数据。也可在DBLP中适当扩展数据集,但这八个会议必须包含在内。

  • 任务1
    (1-1)每⼀个会议都有各⾃的⽀持者,现在请你将每个会议各⾃的研究者寻找出来,并且根据时间信息,看看哪些⼈依然活跃,哪些⼈不再活跃。
    (1-2)在找到各⾃的研究者群体后,我们希望找到经常性在⼀起合作的学者,将之称为‘团队’。请你根据研究者合作发表论⽂次数为根据进⾏频繁模式挖掘,找出三个⼈以上的‘团队’。

  • 任务2
    (2-1)每⼀篇论⽂都会涉及到⼀个或多个主题,请你先定出主题词,然后根据每个‘团队’发表的论⽂的情况,提炼出这个团队最常涉猎的主题。
    (2-2)团队和主题多是会随着时间⽽动态变化。请你根据⾃⼰所定的时间段(五年,三年,两年或是⼀年)描述团队的构成状况以及其研究主题的变化情况。

题目分析

  1. 任务(1-1)貌似不需要什么频繁模式挖掘,对于每个会议的数据,提取作者时间信息,同一作者出现次数多的即为会议的支持者。再根据不同时间段的出现次数,可以知道这些人是否依然活跃。
  2. 任务(1-1)目前的难点在于:一是数据量大,按照每篇论文2位作者,即每条信息6行计算,大约有199992/6=3.3万条论文信息。二是数据为文本信息,提取的工作怎么进行?直接处理字符串?对名字编号?还是HashMap?别忘了后面还会寻找主题词呢,这可就真的是文本了。所以,有没有什么工具?12.14日:查了一下,共有27454篇文章。
  3. 任务(1-2)是在(1-1)的基础上,对于寻找到的这些研究者后,寻找多次一起发文章的团队。这就需要频繁模式挖掘了,其实就是找到在一起发文章次数多的这些人。那么是直接找三人以上法文章的,还是说两个人同时与另外一个人都发文章多也算?这个问题是次要的。
  4. 任务(2-1)让我们先定出主题词,这个主题词是从文章标题中获得的,只需要文章标题。那么一个单词算是主题词吗?有同学说主题词都是些learning、model之类的,是不是不够好?我还没有自己找一下试试呢。另外,有同学说,貌似有主题抽取算法,不知道能不能找到。
  5. 然后,任务(2-1)要求根据每个团队发表论文的情况,提炼出其最常涉猎的主题。题目也说了,每一篇论文都会涉及一个或多个主题,那么问题更清楚了,即:对于每一篇文章,都定出其主题词;然后对于某团队的文章,找到出现次数多的主题词
  6. 任务(2-2)与(1-1)第二个要求类似,即再对不同时间段内的文章,分别研究团队的研究主题。
  7. 任务(2-2)还说了,还要研究团队的构成状况,这个貌似就比较难:对于一个团队,如果走了一个人,那么这还是原来的团队吗?如果说团队一直在增加人数,应该算是一个团队,但是到底要怎样处理呢?
  8. 以上面内容来看,可以先不管任务2,先做任务1即可。做任务2时,可以先调研主题抽取算法。
  9. 那么首要的问题就是找工具还是自己编?先找工具吧!
  10. 但是我又突然想到一点,能不能通过所有文章,定出有限的主题词,然后对于每一个文章标题,通过机器学习-预测的方式,得到它的主题词呢?可能行不通?优点想远了。
  11. 所以说还是要找工具,或者说,先解决数据的问题,因为都是字符串,看看有没有能搞定的工具。答:查到的工具可以处理字符串,没问题。
  12. 12.14日:查到的pyfpgrowth工具很给力啊,找频繁项集没有问题!目前数据量来说不怎么影响,运算很快!
  13. 现在任务1基本上已经解决了,后面就是要根据时间信息来处理了。这里还是存在一个难点,那就是研究者与时间的绑定问题。频繁项集挖掘得到的结果是名字,那么怎样去找到这个名字下的文章呢?我们也来使用字典把作者与其文章序号绑定?答:字典搞定,行得通!
  14. 任务1算是完成基本要求了,找到了频繁的作者,也匹配了他们的文章,也就找到了活跃时间;然后又找到了一起发文章多的团体。不过没有匹配团队的文章:如果只找共同发过的文章,还是需要写一些程序的;如果找每个人发过的文章,那么就容易很多。
  15. 后面任务2就是要找主题词了。对于团队的主题词来说,可能先把所有的论文(即不一定是共同发表的)都放进来,然后定出其主题词
  16. 任务(2-2)先抛开团队构成情况不管。那么解决了任务(2-1),再分时间段分析,就完成了。所以说,现在重点就是任务(2-1)的要求。
  17. 对于主题词的获取我想到了一个思路(单个单词的):把每篇文章的标题看做一个事务,每个单词看为一项,进行频繁项集挖掘。当然,标题内的副词之类的(the、on、to……)要去掉。试试吧。还有,标点符号(:)怎样去掉?答:去掉已经去掉了。上面的思路也实现得差不多。能够得到一些关键词。
  18. 下面就是拿到某个团队所有文章的标题,再确定其关注的主题。这个怎样与已经获得的主题进行匹配?任务(2-1)的要求还是得仔细推敲一下。
  19. 12.15日:今天又做了一些处理,把原数据中一些没有作者的奇怪文章去掉。另外又加了一些介词,试图把标题清理得更干净些。
  20. 还是第18条中讲的,怎样将这些关键词与团队关键词进行匹配
  21. 还有,我想找到最频繁的数据,在字典里怎样去找
  22. 然后就是要找到一个团队的所有文章,来抽取关键词。答:这个已经实现得差不多了。
  23. 从现在来看,因为一个团队发的文章怎么也有几篇,找到出现2次以上的关键词基本上是没有问题的。那么由此看来,当需要找某个团队全部论文的关键词时,不一定需要进行匹配。而在分了具体年月后,可能文章数目比较少,不容易获得关键词,就需要匹配了。
  24. 下面就试试能不能分时间段来分析。07到17共11年,先按照两年分析?
  25. 刚才看群里,助教说,关键词可以用nlp方法来获得。但是这是啥玩意啊。我查到sklearn貌似可以做nlp,什么词向量特征构建之类的:利用sklearn做自然语言处理(NLP)——词向量特征构建。那就看看例子是啥东西。
  26. 我又想到一个点子,那就是,从全部论文获得的关键词,特别是单个词语,根据其出现的次数/比例,为这个词语添加一项权重,这一个权重呢,会对我们最终的结果产生影响。比如,就让大权重的词语的支持度再大一些。
  27. 接上条,我可以试试看看是不是每篇文章标题都有频繁的词汇。答:对于IJCAI会议的3859篇文章标题,统计出现10及以上的单词,定义为频繁单词或者关键词。再对每个文章标题,统计其中出现关键词的次数,得到的结果中,只有123篇没有频繁单词。这说明我的方法还是行得通的。
  28. 现在我想到的方法是:对于单篇文章标题来说,如果要确定其关键词,那么就选其中前两到三个最频繁的单词。对于团队文章呢,就不一样了,一是要参考单词是否频繁,还要参考单词在团队论文中出现的频次,其实这两项呢,可以互为权重。另外,对于团队来说,还要参考其频繁的多单词模式。12.16日:目前这个权重是使用两者相乘的方法。我感觉还是有一定意义的。我使用sorted函数,对频繁单词进行了排序,可以得到最频繁的单词,即团队的主题。
  29. 刚刚又想到一点,有的学者是多个会议的支持者,对于他们的文章要总体研究吗?不过这个问题现在看还是比较简单的,相比于单个会议的情况,只不过是把数据集扩大而已。这个后面如果有时间,可以总体来看的。
  30. 对于没有频繁单词的文章呢?怎么办?选最长的一个?哈哈
  31. 不同会议的文章数目不同,在选择频繁阈值的时候,是不是要对此进行考虑?
  32. 12.16日:下面就是对团队的论文进行分时间段的分析。要注意两点:一是如果时间段内文章很少,比如就一篇,那么其主题怎么选?应该选出现频率最高的那个词。但是如果恰好这篇文章又没有频繁单词,怎么办?鉴于这种情况出现的概率非常小,我们可以认为,此时间段内,没有研究主题
  33. 07到17共11年,先按照两年分析?因为11是一个质数,怎么分呢?先按照三年来分吧:07~09,10~12,13~15,16~17。我估计16、17的文章可能多一些,所以先这样吧,四个时间段。
  34. 分时间段后获取关键词也完成了,反正就是某个时间段有关键词最好,没有那就没有,无所谓。
  35. 现在对于某个时间段只有一篇文章的情况还没处理。可以把这个加上。加是加上了,现在感觉这个倒不是大问题。我反而觉得这个还不如不加呢。三年就这么一篇文章,还谈什么主题。是吧,不行这个先不要了。
  36. 12.17日:现在基本的工作已经做得差不多了。现在只是做了一个团队,后面可能需要完善程序,一下子把所有团队数据搞出来。因为12.25日考试,这个作业现在就先暂停。等到29号考完试之后,再进行下一步工作。
  37. 当然还有一点,那就是关于任务(2-2)中要求的不同时间段的“团队的构成状况”。对于这一点,本来我觉得是比较难处理的。我想到的一个方案就是,把团队每个时间段内文章的所有作者拿出来,以这个作为团队的构成。也就是说,最开始寻找的三个人以上的团队,这里面的三个人可以认为是团队的“核心”成员,而其他的人呢,也算是团队的构成,从这样来看呢,也算是一种解释对吧。反正,有比没有好。在这突然就想到建模竞赛的时候,一般最后一题很难做,但是总得做点什么呀,编也得编出来,自己能够说通,让人听上去有一定道理就行。
  38. 对了,我还想起一个问题,就是减小阈值的时候,反而论文标题带频繁单词的数目减少了,不知道是什么问题,需要研究下。
  39. 作业到此暂停。再回来的时候,需要先完成36、37、38条中的内容。
  40. 12.29日:到今天,所有考试都结束了,现在剩下这一个作业。按照原定计划,应该把36~38条的内容完成。而且,现在就要考虑了,最后的结果是怎样的一个呈现形式?得到的结果是很多的。我感觉每个小题的结果应该独立给出。比如任务(1-1)给出,每个会议支持者的名字、文章数目以及每篇文章的时间任务(1-2)给出,每个会议支持者团队内名字、合作发表的文章数目任务(2-1)给出,每个会议支持者团队内名字、所有文章数目、涉及的主题词(包括单个的和多个词的、加权不加权的)及其次数任务(2-2)给出,每个会议支持者团队内名字、不同时间段内的主题词以及核心成员以外的作者
  41. 12.31日:按照40条的要求,已经将任务(1-1)和(1-2)的结果保存完毕。
  42. 任务(2-1)的结果,包括频繁单词和频繁多词,以及加权重和不加权重的,这样来说,对每个团队就包括四个结果。怎样保存呢?四种结果感觉还是按照字典的方式比较好看些。答:任务(2-1)的结果已经保存完毕。在KDD中韩佳炜团队的主题词结果中,明显能看出权重与非权重的区别。
  43. 团队的作者结果中还有一点小问题,就是其中有些三人的团队还合并成了四人以上的团队,这就存在一定的重复。不过这不是太大的问题,可以先不去管他。考虑到实际得到的团队数量并不多,写程序判断一下,将重复的去掉也是可以的,这个看后面有没有时间吧。
  44. 任务(2-2)的结果是在(2-1)的基础上更加复杂了,分了时间段。那么对每一个时间段,分别保存其主题词。答:(2-2)的主题词结果已经处理完了,而且也加上了对只有一篇情况的处理。
  45. 其实还漏了一点,那就是如果两三篇文章没有重复单词的情况。答:这个问题现在也已经解决了。从这可以看出权重的用处了,如果只有一篇文章,或者几篇文章没有重复的单词,那么就没有频繁模式可言,也就无法判断哪个词是主题词。而本文通过对权重的引入,能够对每个单词的“重要性”进行比较,进而从中选择出主题词。例子:在*SIGIR会议中,团队(‘Alistair Moffat’, ‘Justin Zobel’, ‘William Webber’)*在2010 ~ 2012年有2篇文章,但是没有重复单词。。**在*IJCAI会议中,团队(‘Christian Bessiere’, ‘George Katsirelos’, ‘Toby Walsh’)*在2010 ~ 2012年有1篇文章。
  46. 好了,接下来就是再把团队信息加上了。答:很简单,信息已经加上了。至此,题目已经基本上完成了。还存在的问题的话,就是对于38条,不过这个我暂时不想整了。我觉得这次作业做到这个程度已经可以了,毕竟只是一次作业,没有必要太较真。后面两天多花点时间,把报告写得好一点,这才是重要的。*KDD*会议中*韩佳炜*团队是一个很好的案例

1 数据集

  1. 原始数据中的有用信息也就是作者、标题、时间、会议四项内容,因此,助教筛选的数据信息是足够的。也就是说主题词只能从标题里面定了。
  2. 题目中说的一个会议是SIGKDD,而助教给的是KDD,两者一样吗?答:一样,已经确认。
  3. 我看数据集的文档中,有“Person”这类数据,不知道会不会有用。
  4. 八个会议分别是什么可能首先要搞清楚。答:见下面的表格。
  5. 从题目要求来看,八个会议之间没有什么关系,所以各自分开处理即可。
  6. 12.14日:因为昨天找到的工具,可以直接对字符串进行频繁项集挖掘,所以现在首要的任务是对助教提供的数据集进行处理,把数据保存成需要的形式。首先第一步,应该把数据分为八个会议的数据
  7. 那么是用Python来处理?还是说用C++?用C++建个类的话,可能也比较好处理。Python的话肯定也行啊,但是不太熟。学一下Python的class?
  8. 使用Python建立了类,并且从文本中获取文章信息,27454篇文章的信息瞬间读取完毕,速度还是很给力的。
  9. 下面就好做了,先提取一个会议的数据看看。
会议 全称 主要方向
IJCAI International Joint Conferences on Artificial Intelligence AI综合
AAAI Association for the Advancement of Artificial Intelligence AI
COLT Annual Conference on Learning Theory 学习
CVPR IEEE Conference on Computer Vision and Pattern Recognition 计算机视觉
NIPS Conference and Workshop on Neural Information Processing Systems 神经信息处理
KR Principles of Knowledge Representation and Reasoning 知识表示和推理
SIGIR Special Interest Group on Information Retrieval 信息检索
SIGKDD Special Interest Group on Knowledge Discovery and Data Mining 数据挖掘

2 频繁模式挖掘

  1. 关联规则挖掘:先寻找频繁项集,再找关联规则。频繁项集只与支持度(即出现的频率)有关,关联规则与支持度和置信度(条件概率)都有关。
  2. 频繁模式与关联规则在这是一回事吗?答:不一样。频繁模式里面包含频繁项集、关联规则等。或者说,频繁模式更多的对应的是频繁项集?
  3. 在任务(1-2)中,其实是频繁项集挖掘。对于此问题,每篇文章的多个作者名字作为一个事务。
  4. 其实对于任务(1-1)也可以认为是频繁项集挖掘,只不过挖掘的是频繁的“1-项集”而已。对于这个问题,每个作者的名字作为一个事务。
  5. 12.17日:对于FP-Growth算法,感觉这篇文章讲的可以看懂:关联分析:FP-Growth算法。看过这篇博文后,我对FP-Growth算法基本上算是明白了。如果出一个简单的题目的话,我应该可以算出来。
  6. 对于Apriori算法,参考这篇博文:数据挖掘十大算法之Apriori详解。说得还是比较清楚的。这个算法比较容易看懂,看来容易的算法计算量可能就会大。
  7. 我看老师的课件里,对于Apriori算法还有一个优化的算法,为了减少扫描数据库次数的,叫DIC。我知道了,DIC的基本思路就是:把数据分成几个部分,类似于公交站点。每一站就更新项集的支持度。但是只要子集的支持度超过了阈值(此时可能其支持度还没算完),那么就可以得到候选的父集,在下一站计算时,父集就可以参与支持度的计算了。这样来看,每一次完整扫描,不仅仅扫描了k-项集,还有可能扫描k+1-项集,k+2-项集,所以减少了扫描的次数。

3 工具

  1. 查到了一个FP-Growth算法的Python工具:pyfpgrowth 1.0,不知道这个能不能处理字符串型数据。答:经测试,可以处理字符串,貌似OK!测试可用啊,还可以啊!
  2. 查到了一个FP-Growth算法的Matlab工具: FP-Growth Association Rule Mining

4 Python相关

  1. Python建立类。从这里学的:Python 面向对象
  2. Python打开文本文件遇到 UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0x11 in position 3111: illegal multibyte sequence 这样的问题,说明文件打开的编码格式不对。在我的软件里,默认使用的是gbk格式,然而对于所给的数据集,使用的是utf-8格式,所以在文件打开时,使用f = open("FilteredDBLP.txt", 'r', encoding='utf-8'),即添加一个encoding参数即可。
  3. Python 字典(Dictionary):即“key->value”的组合。搜到的pyfpgrowth返回的频繁项集就是字典。
  4. Python 元组(Tuple):Python的元组与列表类似,不同之处在于元组的元素不能修改。元组使用小括号,列表使用方括号。元组创建很简单,只需要在括号中添加元素,并使用逗号隔开即可:tup1 = ('physics', 'chemistry', 1997, 2000)。元组中只包含一个元素时,需要在元素后面添加逗号tup1 = (50,)。搜到的pyfpgrowth返回的频繁项集是字典,字典的键值(key)是用元组表示的。
  5. 判断字典dict中是否存在键值key,只需使用key in dict即可,返回bool值。
  6. 字典的遍历可以使用for key, value in patterns.items()
  7. Python如何判断一个元组(列表)是否完全包含另一元组(列表),参考:https://www.cnblogs.com/for-my-life/p/8038250.html。将元组或列表转换为set类型,使用issubset()函数:set(list1).issubset(set(list2))
  8. Python将字符串中的标点符合去掉:re即正则表达式,re.sub()即替换,
import re
from string import punctuation
a = "a b ccc: d, d"
delSet = punctuation
# delSet = ".:()"
b = re.sub("["+delSet+"]", "", a)
print(b)
  1. Pyhton的字符串转换为小写:str1 = str.lower()
  2. Python去掉字符串两端的某符号(如空格):str1 = str.strip(' ')
  3. Python的逻辑运算符是andnotor
  4. Python–关于dict:dict 的查找速度快,无论dict有10个元素还是10万个元素,查找速度都一样。而list的查找速度随着元素增加而逐渐下降。 dict的缺点是占用内存大,还会浪费很多内容,list正好相反,占用内存小,但是查找速度慢。
  5. Lambda表达式:参考Lambda 表达式有何用处?如何使用?
  6. Python中访问列表最后一个元素,其id为-1。而如果想要访问列表list的最后几个元素(如最后3个),可以使用list[-3:]。即:后面不加数字就认为是到列表最后。
  7. Python中sorted函数的用法
  8. Python 字典输出value最大值所对应的key怎么实现
  9. Python读写文本文件,参考Python 文件I/O。下面是写文本文件的例子:
f = open("output.txt", 'w')
f.write("Articles count: %d" % 22)
f.close()
  1. 两个list组成字典:Python - 两个列表(list)组成字典(dict)。使用dictionary = dict(zip(keys, values)),其中keysvalues是两个list。
夜凉如水
人丑就要多读书