你好,游客 登录
背景:
阅读新闻

韩家炜在数据挖掘上开辟的「小路」是什么

[日期:2018-02-26] 来源:网络大数据  作者: [字体: ]

  前些日子,数据挖掘领域的巨擘韩家炜教授 [1] 在中国计算机学会(CCF)主办的第 87 期 CCF 学科前沿讲习班(CCF Advanced Disciplines Lectures,简称 CCF - ADL) 做了一场精彩报告,报告题目叫做《大规模语料库的多维分析》(Multi-Dimensional Analysis of Massive Text Corpora)。笔者私以为这场报告对广大做数据挖掘的老师和学生有很大的指导意义,韩家炜在这场报告中讲述了他以及他带领的学生在过去以及未来十多年中研究方向的主线,即下面这张图:

大数据

  文章中还会多次遇到,这是这次演讲内容的一张「地图」,也是数据挖掘领域的一张「地图」

  韩家炜认为要想将现有的无结构的 Big Data 变成有用的 Knowledge,首先要做的就是将数据结构化。他提出两种结构化数据的形式,一种是异质网络(Heterogeneous Network),另一种是多维文本立方体(Multi-dimensional Text Cube)。由这种结构化数据生成 Knowledge 已经证明是很强大的,但是如何将原始无结构的数据变成有结构的数据(Network 或 Text Cube)则是非常困难的。

  在 Network/Text Cube 到 Knowledge 的问题上,韩家炜等人已经做了很多研究工作,也已经由此获得了很多奖项;在无结构文本数据到有结构 Network/Text Cube 的路上他们也做出了许多尝试和成果,现在仍在进行中。

  韩家炜认为这是一条很长的路,他们现在只是在这条路上突破了几个可以往前走的口子,还只是一条小路,要变成一条康庄大道则需要各国学者共同努力。

  下面我们一起来了解一下韩家炜教授报告的详细内容。

  [1] 韩家炜,美国伊利诺伊大学香槟分校(UIUC)计算机系教授,IEEE和ACM Fellow,曾任美国ARL资助的信息网络联合研究中心主任。曾担任KDD、SDM和ICDM等国际知名会议的程序委员会主席,创办了ACM TKDD学报并任主编。在数据挖掘、数据库和信息网络领域发表论文600余篇。出版了数据挖掘专著《Data Mining: Concepts and Techniques》,成为数据挖掘国内外经典教材。曾获ICDE 2002杰出贡献奖、SIGKDD 2004最佳创新奖、 2009年麦克道尔奖(the McDowell Award)。在谷歌学术的 H-index中,名列全球计算机科学领域高引作者前三。

  整体概览

  韩家炜教授本次的报告大致分为五个部分,如下图他列出的梗概。

韩家炜在数据挖掘上开辟的「小路」是什么

  分别为:

  1、如何从大数据到知识。在这里韩家炜提出了他们研究的三部曲;

  2、如何由 Network/Text Cube 到知识。韩家炜这里简单举了他们之前的一些研究,可以看到Network/Text Cube 有多么强大,这也侧面反映了为什么在挖掘数据时要先把数据结构化;

  3、如何从无结构文本中挖掘出结构。韩家炜认为从无结构文本中挖掘出结构是当前数据挖掘研究的重中之重。他就他们研究中的四个方面做了深入的解读;

  4、如何构建 Text Cube。承接前一步,挖掘出结构后,韩家炜讲解了如何构建多维 Text Cube;

  5、研究方向总结。最后韩家炜总结说,由 Big Data 走向 Actionable Knowledge 目前仍是一条小路,未来的康庄大道须各国学者来共同努力。

  一、如何由Big Data 走向Actionable Knowledge

  革命需要指导原则,研究也是。韩家炜首先讲述他们研究的总体思路。

  1.1 大量无结构数据普遍存在

  在我们这个时代,由于互联网的发展,产生了大量数据。这些数据尽管有大量是在表格中存放,但绝大部分(超过 80%)都是以文本等无结构或半结构的方式存储着。所以挖掘大数据,首先就是要研究如何系统地挖掘这些无结构的大量文本数据。

  1.2 如何系统地挖掘大数据

  韩家炜认为若想从 Big Data 中挖掘出有用的知识,就必须研究如何将无结构的文本变成有结构的文本,然后再从有结构的文本中挖掘知识。

  针对这种想法,他们提出了三个关键词:

  Structuring:将无结构的文本转化成有结构的、有类型的、关联的实体或关系

  Networking:利用大量有结构的关系构建网络

  Mining:在关系和网络上进行挖掘

  1.3 数据挖掘三部曲

  韩家炜认为他们做数据挖掘的研究工作可以总结为三部曲:

  (1)从文本数据中挖掘隐藏的结构。文本数据中隐藏着大量的结构,这步工作就是将这些数据挖掘出来。

  (2)将文本数据转化为有类型的 Network/Text Cube。将文本数据变成有结构、有类型的数据(Network/Text Cube)

  (3)挖掘 Network/Text Cube 生成有用的知识。最后一步才是挖掘。

韩家炜在数据挖掘上开辟的「小路」是什么

  为什么要经过中间的一步,将无结构文本先转化为 Network/Text Cube,而不是直接对文本进行挖掘呢?韩家炜随后举了两个例子来说明这样做的好处。

  二、由Network/Text Cube到知识

  2.1 Network 的强大

韩家炜在数据挖掘上开辟的「小路」是什么

  如果将 DBLP 的文献信息(例如论文、作者、出版地等)整合到 Network 中,那么显然这个网络中蕴涵着丰富的信息,例如我们可以通过排名函数从网络中挖掘出谁是 Web 研究的领军人物,或者通过相似性搜索函数从网络中挖掘出一个学者的同行;通过关系预测来挖掘一个学者未来的合作者将是谁;通过网络演化来发掘 Data Mining 学科是如何出现和发展的等等。

韩家炜在数据挖掘上开辟的「小路」是什么

  这里面韩家炜讲了一个故事。2010 年韩被 ECML-PKDD 邀请去做一个 keynote,报告的主题为《结构就是信息:挖掘结构信息网络》(Structure is Informative: On Mining Structured Information Networks)。报告结束后的提问环节,坐在下面的 Christos Faloutsos 举手问道:「你做的这个 Network 很 powerful,但是你能否预测到我明年写什么文章?」韩回答道:「我连自己的都预测不到,更别提你的啦。」于是当时下面哄堂大笑。回去后韩家炜将这个笑话讲给当时还在他手下读博士的孙怡舟听。孙怡舟很严肃地认为这不是一个简单的笑话。经过分析和讨论后孙怡舟定了一个新课题,预测 Christos 今后几年会有哪些新的 authors 合作。

  这个课题导致孙怡舟随后提出了我们现在广泛使用的 Meta path 的概念,并于 2011 年在 ASONAM 上发表了一篇影响力巨大的文章。在文章中,孙怡舟预测了裴建的合作者。根据裴建在 [1996-2002] 年间的文章(作为特征集)准确地预测了他在 [2003-2009] 年间会有哪些合作者(测试集),排名前五的预测中只有一个没有出现在测试集中。

韩家炜在数据挖掘上开辟的「小路」是什么

  另外一个是预测错误吗?并不是,裴建和 Osmar 也有合作,只不过他们合作的 paper 发表在 2011 年;没有被统计进测试集中而已。

  这就说明如果有一个 Network 将 Big Data 结构化后,其预测能力(或者别的能力)将是非常强的。

  2.2 Text Cube的强大

韩家炜在数据挖掘上开辟的「小路」是什么

  我们知道如果在 Database(也即 Data Cube)上做统计和分析是非常方便的。现在分析无结构的 Text,如果能够将 Text 放入到一个类似的多维 Cube 中,那么很显然这将对分析 Text 起到很好的作用。

  Text Cube 其中一个应用就是 Comparative Summarization。例如将 NY Times 的新闻放入到这样一个 Cube 中,我们想要总结「2016」、「China」、「Economy」的信息。与这些关键词相关的 Documents 有很多很多,没有人原意去一个一个地查看。如果只是简单地用统计的方法来获取信息,就会发现有很多不是「Economy」的信息,例如「Hong Kong」、「United States」等。而如果我们事先已经将这些 Text 放入到 Cube,则根据 Integrity、Popularity、Distinctness 等标准,通过与每个维度上相邻的 Cell 做比较,就可以很容易地找到非常准确地信息。

韩家炜在数据挖掘上开辟的「小路」是什么

  使用这种方法,韩家炜领导的小组通过 NY Times 在 2016 年的新闻很容易就挖掘出了当时美国两党辩论过程中的主要议程(例如、等)Top 10 的关键信息。

韩家炜在数据挖掘上开辟的「小路」是什么

  一个很有意思的故事是,韩家炜在 UCLA 做了关于上述研究的报告后,引起了 UCLA 医学教授的兴趣。UCLA 在心脏病方面的研究在全美范围内是非常先进的。

  这些教授告诉韩家炜说,心脏病其实不是一类病,而是六类病;每类疾病大多都是由某种蛋白质引起的。他们希望韩家炜能够帮助他们从大量文献中找出哪种蛋白质与哪类心脏病有紧密关联。

  这个任务对这些医学教授们来说是非常艰难的,因为每年会有超过 100 万的生物医学论文发表,而每个针对某类心脏病的研究总会列出一大堆相关蛋白质,从如此庞大的信息中找出对应某类心脏病的蛋白质是极为困难的。

  讨论过后,韩家炜等人从 PubMed(一个医学文献库)中抓取了「心血管疾病」相关的十年的数据,大约有 50 万篇 paper。他们使用这 50 万篇 paper、6 类心脏病以及医学教授们列出的 250 种蛋白质,根据和挖掘 NY Times 一样的算法,很快就得到了针对每一类心脏病的相关蛋白质排序,如下表(仅列出 Top 5)。

韩家炜在数据挖掘上开辟的「小路」是什么

  这些医学教授看到结果后高兴坏了。首先,韩家炜等人列出的结果中,排名 No.1 的蛋白质和他们已知的情况完全符合,这说明这种算法有效。但是他们的经验表明有些病人(例如小孩)按照这种蛋白质病因去治疗往往无效,这说明这些病人的这类心脏病并不是由该蛋白质引起的。所以韩家炜等人列出的排名 No.2、No.3 等的蛋白质就给他们一个很大的线索,他们可以集中精力针对这些蛋白质去做临床试验,这大大地促进了他们的研究。

  这样一个简单的例子说明 Text Cube 很有用,而且有着巨大的潜力。

  三、从无结构文本中挖掘结构

  上述两个方向的研究(「从 Network 中找知识」和「从 Text Cube 中找知识」)表明,如果有了结构化的 Network/Text Cube,那么从中挖掘知识就相当容易。但是现实世界中,我们所拥有的数据大多是无结构的 Text,如何将这些无结构的 Text 变成有结构的 Network/Text Cube 仍然是未解决的问题。

  韩家炜团队的人员近几年主要的研究工作正是围绕着这个问题进行的,即怎样从 Text 中挖掘 Phrases、怎样从 Text 中挖掘 Typed Entities、以及怎样把这些 Phrases/Typed Entities 变成 Network/Text-cube(第四节内容)。

  3.1 Phrase Mining

韩家炜在数据挖掘上开辟的「小路」是什么

  单独的一个字意义往往不明显,如果能够从 Text 中挖掘出词组(Phrase),那么对挖掘文本结构将有很重要的意义。韩家炜团队的人员先后提出了三种方法,分别为无监督的 TopMine、弱监督的 SegPhrase 和远程监督的 AutoPhrase。这些研究的代码在 Github 上都有公开,任何人都可以下载下来使用或重复其工作。

  (1)TopMine:频率模式挖掘+统计分析

  这项工作主要是对语料库文本的 Topic 进行挖掘。但是它的方法不同于以往采用 Uni-gram 的方法,而是将 Topic 挖掘分成了两个步骤:通过 Phrase Mining 对文本进行分割;随后进行基于 Phrase 约束的 Topic 模型。

  对文本进行 Phrase Mining 的一个基本思想就是,Phrase 中的字同时出现的频率较高。具体来说就是这么一个公式:

韩家炜在数据挖掘上开辟的「小路」是什么

  举个例子,对于一个论文标题「Markov Blanket Feature Selection for Support Vector Machines」,不同的分割方法可能会将它划分到不同的 Topic 里面,例如仅仅根据「Vector」,可能会把这篇文章划分到数学、物理的 Topic 中。但是显然「Support Vector Machines」是一个整体,它是属于计算机的 Topic。根据上述公式的迭代,则可以将这个标题进行如下的 Phrase 分割。

韩家炜在数据挖掘上开辟的「小路」是什么

  这种方法有多好呢?韩家炜又讲了一个故事。David Blei 是做 Topic Model 非常权威的专家,某次去 UIUC 访问,看到了这个结果之后非常震惊,因为他从来没有见过这么好的结果。

  结果好的原因,归结起来在于 TopMine 将 Topic Model 分为了两步,先做了 Phrase Mining,然后才做 Topic model。这种方法避免了长度同意的 gram 将一个 Phrase 中的 Word 分割开。

  (2)SegPhrase:弱监督、高质量的 Phrase Mining

  韩家炜的学生刘佳硉认为 TopMine 的方法完全是无监督的,如果有少量的 Label 数据可能会在很大程度上提高 Topic Model 的结果。于是他精心选择了 300 个高质量的 Labels(150 个正例,150 个反例)。

  这篇论文发表在 SIGMOD 2015 上后,不久 Yelp 就给他们颁发了一个「Grand prize of 2015 Yelp Data Set Challenge」的奖,并且这个方法还被应用在了 TripAdvisor 等平台上。

  (3)AutoPhrase:自动的 Phrase Mining

  韩家炜的学生商静波认为人工挑选 300 个高质量 Labels 还是挺费精力的,于是选择使用 Wikipedia 的词条作为 Label,这样可以很快就得到几十万的 Labels。

  这种方法的一个问题是,有一些 Phrase 并不在 Wikipedia 中,这些 Phrase 并不一定是 Nagative Label。他们通过 ranking 解决了这个问题。

韩家炜在数据挖掘上开辟的「小路」是什么

  这种方法的结果与其他方法相比有显著提升。

  3.2 识别Typed Entity

韩家炜在数据挖掘上开辟的「小路」是什么

  知道了 Phrase 以后,还需要让 Phrase make sense,也即识别实体、标注 Type。按照韩家炜的话:

  Identifying token span as entity mentions in documents and labeling their types

  ——Enabling structured analysis of unstructured text corpus

  这有几个难点:

  领域限制。用一般语料获得的实体标注在特定领域、动态领域或者新兴的领域无法很好的工作。

  名称的歧义性。多个实体可能共享同一个表面名字(Surface Name,例如「Washington」,它可能是州、市、人名、球队名等)

  上下文稀疏。对同一个关系可能有许多种表示方法。(想想中文有多少中表示体育比赛结果的方法)

  (1)ClusType

  韩家炜讲了他们发表在 KDD 2015 上的一篇文章。在这篇文章中他们构建了如下一张异质结构图,其中 c1、c2、c3 代表实体的 Surface Name,p1、p2 ……代表文本中 Surface Name 左右的 Phrase,而 m1、m2 ……代表实体(Entity Mention)。每个 Entity Mention 都是没有歧义的独立对象。

韩家炜在数据挖掘上开辟的「小路」是什么

  将 Surface Name 、Phrase 和 Entity Mention 连接起来,其中两个对象越有可能共享相同的 label,连接它们的边的权重就越大。

  基于这样一张异质图,他们将两个任务联合起来构建了一个基于图的半监督学习:

  在图中进行类型演化。通过聚类的同义关系 Phrase 推断连接起来的实体类别(例如,「Kabul is an ally of Washington」,如果已知 Kabul 的类别是「government」,那么可以推断这里的「Washington」的类别也是「government」)。

  将关系 phrase 进行聚类。反过来,已经标注类型的实体也可以作为很好的 feature 来对 phrase 进行聚类。

  将这两个步骤循环进行将得到很好的结果。从结果中可以看出其 F1-score 远远超出了其他 NLP 领域顶尖的研究。

韩家炜在数据挖掘上开辟的「小路」是什么

  (2)Cotype:going deeper

  上述的类别往往比较粗糙,例如只区分了「person」、「food」、「job」、「event」、「government」等等,粒度比较大。以特朗普为例,特朗普的大的类别是「person」,但是作为一个「person」,特朗普可以是一个政治家,也可以是一个商人或者艺术家等。如何进行更精细的类别分类呢?方法就是 Embedding。

韩家炜在数据挖掘上开辟的「小路」是什么

  韩家炜举了一个他们在 WWW 2017 上发表的一篇文章。[4] 在这篇文章中,他们发明了叫做 CoType 的方法,将 Entity 和 Phrase 全部都 Embedding 到一个低维空间中(而不仅仅是 Embedding Entity)。

韩家炜在数据挖掘上开辟的「小路」是什么

  例如在这个 Embedding 空间中,如果要标记的「Trump」和「Hillary」相近,则很明显应该给这个「Trump」标记为「politician」;如果是和企业相关的 Phrase 相近,那么就标记为「businessman」。通过 Entity 和 Phrase 的相互促进来提升整体的标记内容。

韩家炜在数据挖掘上开辟的「小路」是什么

  [4] 论文中举的例子是「Obama」,这里用的是韩家炜报告中的例子。

  3.3 寻找Meta Pattern

韩家炜在数据挖掘上开辟的「小路」是什么

  韩家炜考虑地其实更远,不光是找 Phrase,也不光是找 Type,还要找文本中的 Pattern,通过 Pattern 来从文本中自动并大量地挖掘结构信息。

  何谓 Pattern 呢?其实通俗点儿来说,就是「套路」。我们语言很多都是在套用模板,例如「the government of USA」,「the government of China」,「the goverment of Burkina Faso」等等。你可能一下子不知道「Burkina Faso」是什么,但是通过类似的模式,你知道这肯定是一个国家。

  同样的,这对机器来说也并不难。只要有 Pattern,机器可以迅速地从文本中挖掘出相同 Pattern 的大量信息。韩家炜举了他们实验室读博士后的蒋朦在 KDD 2017 上发表的文章。

  这篇工作也是在 Phrase 的工作上来做的,但这是 Meta Pattern 的 Meta Phrase。

韩家炜在数据挖掘上开辟的「小路」是什么

  从上面这个图可以很清晰看出他们的工作流程:对语料文本进行 Meta Pattern 分割,得到 Meta Pattern;通过 Meta Pattern 可以找到大量相符的三元组;再通过这些三元组数据进一步地改进 Meta Pattern,例如提升粒度或获得同义的 Meta Pattern。值得注意的是,这种方法并不需要大量的标注数据,也不需要相应的领域知识,同样也不需要搜索日志。

  他们将这种方法应用到新闻语料库中,一下子就把所有的国家和领导人,以及大大小小的公司和他们的 CEO 挖了出来。

韩家炜在数据挖掘上开辟的「小路」是什么

  同样的方法应用在医学研究的语料中,迅速就挖掘出相应的疾病和治疗方案,细菌和抗体。这项工作的思想很简单,但是结果却很 amazing。

韩家炜在数据挖掘上开辟的「小路」是什么

  3.4 建立层级分类

韩家炜在数据挖掘上开辟的「小路」是什么

  在以上工作的基础上,很多人也在研究如何建立起 Entity 的层级分类。人类经过训练后可以很容易地给不同的 Entity 进行分类,例如 Machine Learning、Computer Science 显然不是同一个层级的。能否让机器根据文本的 Title 来自动生成 Entity 的层级分类呢?

  韩家炜说,自动建立层级分类其实「挺难的」。他们经过多种尝试后,提出了两种有效的方法:Adaptive Spherical Clustering 和 Local Embedding。

  (1)Adaptive Spherical Clustering

韩家炜在数据挖掘上开辟的「小路」是什么

  通过考虑 Popularity 和 Concentration 两个特性,设计一个排名模型,通过排名模型选出每一个聚类的代表性 Phrases(Representative Phrases)。随后将那些背景性 Phrases(Background Phrases)向上一级或向下一级(根据 Embedding 后距离的远近)推移。最重要的一点就是,不强求每个 Phrase 必须属于某个 Cluster。

  (2)Local Embedding

韩家炜在数据挖掘上开辟的「小路」是什么

  所谓 Local Embedding,就是说只选用与 Cluster 相关的 Phrases 进行 Embedding。之所以这样,是因为当把所有的 Phrase 放在一起进行 Embedding(Global Embedding),其他 Cluster 的 Phrases 就会产生很多噪声,这会湮没真正有用的东西。而如果使用 Local Embedding 则可以把真正有用的 Phrase 显露出来。

  四、构建多维Text Cube

  以上这些研究的目的是什么呢?韩家炜说,主要是想要建立一个多维 Text Cube。

韩家炜在数据挖掘上开辟的「小路」是什么

  一个可能的疑问是,前面 2.2 节不是已经有了建好的 Text Cube 吗,为什么还要构建?我们需要注意的是,那个 Text Cube 是 NY Times 的数据,这是已经按照 Topic(sport、economic、political、science...)或者 Location(China、USA、Japan...)等标签构建好的 Text Cube;而真实的世界中的文本则大多并没有标签,这需要我们自己来构建。

  一个现实的问题就是,假如给你 100 万个 Documents,而只有少量几个标签(例如上述 Location、Topic 的标签),那么你能否自动地生成成百上千的标签,并将文本正确地放入到这些标签构建的多维 Text Cube 中呢?

  首先去做的当然是 Embedding,但是已知的标签太少了。所以韩家炜他们建了一个 L-T-D(Label-Term-Document)图,其中的 Term 是从文本中抽取出来的。

韩家炜在数据挖掘上开辟的「小路」是什么

  我们查看每个 Term 在每个已知 Label 中的分布情况。

韩家炜在数据挖掘上开辟的「小路」是什么

  例如「stock market」,它在每个 Location 维度中分布的概率基本一致,这说明「stock market」这个 term 不属于 Location 这个维度;而另一方面,它在 Topic 维度的分布则有很强的差别性。根据一个称为 Dimension-Focal Score 的标准可以判别出它是属于 economy 标签下的。

  依据上面的方法以及该 term 在这个标签下的普遍程度(如果大于某个值),则可以判断出这个 Term(例如「stock market」)属于相应标签维度下的一个标签。藉此,我们可以自动地生成大量的标签,并同时将文本放入到这些标签构建的多维度 Text Cube 当中。

韩家炜在数据挖掘上开辟的「小路」是什么

  构建出这样的 Text Cube 之后,再去进行数据挖掘就会方便很多。

  五、研究方向总结

韩家炜在数据挖掘上开辟的「小路」是什么

  韩家炜最后做了报告总结,这里我们将韩的原话整理如下,稍做修改:

  我们认为,要把大的数据变成大的 Knowledge,其中很重要的一条就是要有结构。我们找到两种结构,一个是 Network,一个是 Text Cube。用这两种结构导出 Knowledge,我们已经有很好的例子,而且很 powerful。当然这两种结构在某种程度上是应该结合起来的,现在我们有人在研究怎样将它们结合起来。

  真实的数据到结构化数据,再到有用的知识,这仍然是一条很长的路。我们这么多年做 Data Mining 也是沿着这条路走的。从 2000 年我们出的第一本书(注:2011 年第三版),随后 Philip、Faloutsos 和我在 2010 年合著了《Link Mining》,再往后是孙怡舟做的《Mining Heterogeneous Information Network》;随后是王箎做的《Mining Latent Entity Structures》;最近呢,是刘佳硉、商静波他们把 Phrase mining 做了出来(《Phrase Mining From Massive Text and Its Application》)。这些以后都会成为书。我们接下来有任翔他们,还会接着往下走。

  在这条路上,我们现在只是找到了几个口子可以往前走。现在这还不是一条大路,只是一条小路。要想变成一条康庄大道,需要大家共同努力。这条路通宽了,将来我们就可以从大量的无结构的文本,变成大量的有用的知识。这是我要讲的重点。

韩家炜在数据挖掘上开辟的「小路」是什么

  感谢韩家炜教授在百忙之中对本文的指正。





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款