从大数据中挖掘什么? By 李航博士

概要:大数据挖掘中最重要的是决定挖掘什么样的知识,这是在数据的收集、处理、挖掘的整个过程中都需要认真考虑的问题。本文首先提出大数据挖掘的几项策略,即尽量设想挖掘的场景,尽量多方面收集数据,尽量将数据整合,悉心观察数据特征。之后结合自己在互联网搜索中的大数据挖掘工作经验,分享对这些策略的体会。最后介绍一个互联网搜索中大规模日志数据挖掘的工作,展示大数据挖掘的威力,呈现大数据挖掘的挑战。

1. “挖什么”与“怎么挖”

1

大数据技术涉及存储、搜索、传输、计算、挖掘等多方面,本文只考虑大数据的挖掘。大数据挖掘旨在从大数据中挖掘出未知且有用的知识。通过挖掘,大数据的价值才得以体现,所以挖掘对大数据有着举足轻重的意义。

大数据挖掘有两个基本问题,即“挖什么(what to mine)”与“怎么挖(how to mine)”。前者决定从数据中抽取什么样的信息,统计什么样的规律,后者决定怎样具体进行抽取与统计。前者是在数据的收集、处理、挖掘中都要考虑的问题,后者往往仅限于挖掘。“怎么挖”通常是数据挖掘研究的核心,但是“挖什么”在数据挖掘的应用中往往更为重要,因为它决定了挖掘结果的价值。在实际问题中,决定是挖金银,还是挖铜铁,比决定是用锄头挖,还是用铲子挖更为关键。

2. 大数据挖掘策略

本文总结了大数据挖掘中判断“挖什么”的四项策略,即尽量设想挖掘的场景,尽量多方面收集数据,尽量将数据整合,以及悉心观察数据特征。下面,结合自己在互联网搜索中的大数据挖掘工作经验,介绍对这些策略的体会。

尽量设想挖掘的场景

收集数据是数据挖掘的第一步,需要判断记录、采集哪些数据,这直接影响了能从数据中挖掘什么样的知识。巧妇难为无米之炊,没有某一方面的数据,也就无法从中进行相关的挖掘。但是,存储、处理数据是有代价的,提高数据挖掘效率的关键也在于只记录、采集有用的数据。所以,需要对收集数据的内容进行合理的判断,这时,应该尽量设想挖掘的场景,在此基础上将可能有用的数据全部记录、采集下来。

某公司的工程师们开发了一个互联网浏览器中的工具栏(toolbar)。用户安装了工具栏后,在浏览器中的操作,如点击网页链接,拖动鼠标等,都会被记录下来。在得到用户允许的条件下,这些数据会被传送到该公司的云端服务器。工具栏记录的用户浏览器使用行为数据,可以用于互联网搜索引擎等诸多方面。工程师们对工具栏记录数据内容进行了精心的设计,考虑了各种可能的情况,希望收集的数据能支持多种挖掘任务。用户的IP地址,网页链接的点击时间等都被记录下来。然而,他们忘记记录了一个重要的信息,使得到的数据不利于挖掘使用。原来,用户关闭浏览器的时间没有被记录下来,从数据中无法判断用户何时结束了搜索或浏览行为。由于工程师们没有很好的想象如何使用数据,给之后的挖掘带来了一定的困难。

判断收集什么样的数据牵涉到如何认识世界这一哲学问题。哲学家康德的一个核心观点是:我们所认识的世界是我们用自己拥有的理论对自己观察的现象做出的解释。纸上的一条墨迹,数学家把它看成是平面上的直线,中国人把它看成汉字的“一”。其实,我们想怎样看世界决定了我们看到的世界是什么样的。只有当对数据挖掘的内容有比较清晰的想法的时候,才能对数据的收集范围有比较明确的界定。所以,尽量设想挖掘场景是必不可少的。

尽量多方面收集数据

事实上,我们很难事先穷尽所有可能的挖掘场景,所以也就很难完全准确地判断应该收集哪些数据,不应该收集哪些数据。作为弥补措施,可以考虑在存储、处理能力允许的条件下,尽量多方面收集数据。这是另一项策略。多收集数据总有可能对数据挖掘产生某些帮助。

回到工具栏的例子。工具栏记录的用户互联网访问的行为数据,能大大帮助搜索引擎提高对用户的理解,提高搜索结果的相关性。研究发现,从用户在浏览器中的简单操作中都可以发现许多有用的信息,帮助推断用户的兴趣、意图等[1]。比如,从用户在浏览器中的鼠标移动轨迹中可以估计出他对网页的关注范围,从用户对网页链接的点击可以猜测出他的信息需求,从用户对窗口的关闭动作可以推测出他的兴趣转移。

尽量将数据整合

让数据发挥更大作用的办法是将相关数据整合在一起,用于挖掘。数据整合有助于帮助了解事物的全貌,发现未知的关系,提升预测的准确率。局部数据只是“罗之一目”,而整体数据才是“弥天大网”。

图1所示为互联网搜索中的用户行为模型。该模型虽简单,但属于基本模型,互联网搜索中用户的行为数据都可以纳入其中,可以对用户的行为进行描述。现实中,该模型的数据需要从多个数据源中获取,并通过整合处理而得到。

互联网搜索中首先有许多用户。每个用户会多次使用搜索引擎,每次使用完成一个查询任务,构成一个会话(session),每个会话又由多个查询组成。每个查询中,用户提交查询语句,搜索引擎返回结果,用户根据其内容判断网页的相关性,点击相关网页的链接,浏览网页。浏览过程中,用户可能按照网页的链接,浏览多个网页,之后返回搜索结果,也可能直接离开。用户在浏览器中的动作,可以通过工具栏记录下来,传送给搜索引擎,但是,基于效率等考虑,搜索引擎返回的结果往往不会被工具栏记录。相反,搜索的结果会被搜索引擎记录下来。所以,将客户端与搜索引擎端的数据进行整合变成互联网搜索数据挖掘工作中的一项重要任务。浏览器记录的用户ID与搜索引擎记录的用户ID往往不一致,将同一用户的不同ID联系起来并非易事。

2

 

 1. 用户搜索行为的模型

悉心观察数据特征

决定从数据中挖掘什么,首先需要对数据有深入的了解,需要对数据进行认真细致地观察。只有对数据有深刻的认识,才有可能从中挖掘出深层的知识。AOL隐私泄露事件是一个著名的“人肉数据挖掘”成功事例,说明只要细致观察与推理,我们可以从数据中发现许多事情。

2006AOL公司,为了促进研究,发布了搜索查询数据集,包括65万用户三个月中在AOL搜索提交的2千多万查询。为了保护用户隐私,AOL将用户的个人信息删除,对每个用户赋予了一个ID。纽约时报的一个记者对AOL数据进行了观察、分析,利用电话号码簿,很快确定出ID4417749的用户是居住在佐治亚州的60岁的单身妇女Thelma Arnold[3]。具体地,这位用户提交了“landscapers in Lilburn, Ga”的查询,从此可以推断此人大概住在佐治亚州Lilburn。该用户又提交了多个含有Arnold的人名查询,可以揣测此人大概姓Arnold。该用户又搜了“60 single men”,可以猜想此人可能是60岁左右的妇女,等等。

AOL事件说明了数据挖掘中保护用户隐私问题的重要性(本文不讨论隐私保护问题),同时也说明了认真观察数据,可以挖掘到许多深层的信息。

3. 大数据挖掘事例

互联网搜索引擎,索引几十亿以上的网页,每天有几十亿次查询,收集几十TB的日志数据。这些数据是典型的大数据。

下面介绍一个互联网搜索日志数据挖掘例子:查询副主题挖掘。这是与微软前同事等的工作[4]。互联网搜索中的查询,或者表示多个语义,或者表示事物的多个侧面,统称为副主题(subtopic)。前者的例子,如图2所示, 查询“harry shum”意味着用户可能要搜索微软的副总裁,也可能是搜索美国的演员。后者的例子,如查询“xbox”意味着用户可能想找游戏攻略,也可能想购买游戏机。如果能判断查询的副主题,那么可以将该搜索结果进行聚类,把同一个副主题的网页放在一起,帮助用户迅速找到想要找的所有信息。根据副主题对搜索结果聚类是一个热门研究课题。传统的方法根据搜索结果中网页摘要的相似度对网页进行聚类,效果并不理想。我们提出的方法事先从搜索日志数据中挖掘出查询的副主题,用户搜索时,根据挖掘好的副主题,对查询结果进行聚类,效果提升显著。副主题挖掘利用了用户搜索的两个现象。

3

2. 查询“harry shum”有两个副主题(subtopic

我们观察到的第一个现象是“同一查询同一副主题(one subtopic per search)”。用户每次进行查询时,往往只考虑一个副主题,要搜副总裁的Harry Shum,就不会搜演员的Harry Shum,反之亦然。这一点会反映在用户的日志点击数据上。在同一次搜索中,用户点击的多个网页链接往往集中在同一个副主题上。将某一查询的大量的点击数据汇集起来,根据链接是否常在同一次搜索中被共同点击,可以将它们聚类,就可以挖掘到该查询的副主题,这时,链接的每个类对应一个副主题。

第二个现象是“加关键词明确副主题(Subtopic Clarification by Additional Keyword)”,也可以用于副主题挖掘。用户在查询时,会主动明确副主题,在主查询词的后面(或前面)加上关键词,如“harry shum microsoft”,“harry shum jr”。属于同一副主题的网页链接往往在被加同样关键词的查询中点击,根据链接是否在加同样关键词查询中被点击,可以将它们聚类,得到的类也对应于副主题。

我们的方法能够根据以上两个现象挖掘出查询的每个副主题,副主题由网页链接、以及附加关键词表示。利用特殊的数据结构,可以将Bing的三个月日志数据在一天内进行一次高效的挖掘。对于高频查询,可以得到非常精准的挖掘结果(详见[4])。可以看出,大数据确实能够发挥巨大作用。

另一方面,我们的方法对低频查询无法适用,因为没有足够的点击数据,也就是说会遇到长尾挑战[5]。用户的行为数据大多遵循幂率分布(power law distribution),现在基于统计的数据挖掘方法对尾部数据依然是束手无策。

4. 总结

大数据挖掘关键是决定挖什么,这比决定怎么挖更为重要。收集数据时,应该尽量设想挖掘的场景,尽量多方面地记录、采集数据;收集数据后,应该尽量将数据整合在一起;数据挖掘前,应该悉心观察数据,以帮助判断挖掘什么样的知识。只有这样,大数据挖掘的价值才能得以体现。

大数据挖掘极具威力,但也有局限性,会遇到长尾挑战。结合事先给定的知识进行挖掘,或许是解决长尾挑战的一条出路。纽约时报记者能从搜索查询数据中挖掘出用户的身份,也是因为用了基于常识的推理。机器要变得具有同样的智能,需要采用相同的手段。

大数据时代刚刚开始,相信今后在各个领域,各种应用中,大数据挖掘都会推动创新,对技术发展带来巨大影响。这一点确实令人振奋。

大家都想一想从自己拥有的数据中可以挖掘出什么样的金子吧!

参考文献

1. S. Fox, K. Karnawat, M. Mydland, S. Dumais, and T. White, Evaluating Implicit Measures to Improve Web Search. ACM Transactions on Information Systems 23, 147-168, 2005.

2. Daxin Jiang, Jian Pei, Hang Li, Mining Search and Browse Logs for Web Search: A Survey, ACM Transactions on Intelligent Systems and Technology, 2013, to appear.

3A Face Is Exposed for AOL Searcher No. 4417749, New York Times, 2006.

4Yunhua Hu, Yanan Qian, Hang Li, Daxin Jiang, Jian Pei, Mining Query Subtopics from Search Log Data, In Proceedings of the 35th Annual International ACM SIGIR Conference (SIGIR’12), 305-314, 2012.

5.李航,克服长尾挑战(Overcoming the Long Tail Challenge),新浪博客,http://blog.sina.com.cn/u/20607508302012.

转自 李航的博客

欢迎加入我爱机器学习QQ13群:550972653

微信扫一扫,关注我爱机器学习公众号

微博:我爱机器学习

发表评论

电子邮件地址不会被公开。 必填项已用*标注