中国人工智能学会通讯第12期_在线翻页电子书免费阅读,发布_云展网
阅读云展网其他3D杂志
喜欢这样的3D电子杂志？您也可以在几分钟内把文档免费上传到云展网变成翻页书！[点击上传我的文档]
中国人工智能学会通讯第12期
《中国人工智能学会通讯》
第6卷 第12期
新世纪知识工程—— 在哪里跨越………………………………… 陆汝钤
01 科技前沿主办
大数据环境下序列模式挖掘及应用中国人工智能学会
………………………………………敖翔，李宏伟，罗平，何清 01主编
接触追踪: 传染病防控的AI方法…………………………杨博，陈贺昌 08李德毅（CAAI理事长，中国工程院院士）
时空众包: 共享经济时代的新型计算范式执行主编
…………………………………童咏昕，宋天舒，许可，吕卫峰 14马少平（CAAI副理事长，清华大学教授）
基于众包的数据提纯……………………………………………胡卉芪 20
基于众包的知识库补全研究………………………………………范举 24副主编王国胤（CAAI副理事长，重庆邮电大学教授）
02 百家论坛王卫宁（CAAI秘书长，北京邮电大学研究员）
分类型数据聚类算法研究进展编委员名单（按姓氏拼音排序）
………………………………………………曹付元，白亮，梁吉业 32曹 鹏 陈 杰 董振江 杜军平
贾英民韩力群 何 清 黄河燕 黄心汉
知识图谱研究综述………………………………………李涓子，侯磊 38蒋昌俊 焦李成 李 斌 李德毅
基于不确定性的大数据学习模型………………………王熙照，朱红 44刘 民 刘成林 刘增良 鲁华祥
乔俊飞马少平 马世龙 苗夺谦 朴松昊
03 学会动态任福继 任友群 孙富春 孙长银
王万森王 轩 王飞跃 王国胤 王捍贫
不确定性人工智能专委会2016年度学术沙龙在清华大学举行… … … 48王卫宁 王小捷 王亚杰 王志良
吴文俊人工智能科学技术奖在深圳揭晓……………………………… 50吴晓蓓 夏桂华 严新平 杨 强
首期“人工智能前沿讲习班”成功举办……………………………… 51杨放春 余 凯 余有成 张学工
人工智能60周年高峰论坛暨周志华 祝烈煌 庄越挺
“科艺杯”创新大赛颁奖典礼胜利召开……………………………… 53
2016机器智能前沿论坛成功召开……………………………………… 56编辑部主 任：孙伟玲副 主 任：刘奕群责任编辑：于 蕙 卢军强通讯地址：北京市海淀区西土城路10号
北京邮电大学167信箱电 话：010-电子信箱：网 址：http://caai.cn创刊日期：2011年主办单位：中国人工智能学会编辑出版：中国人工智能学会通讯编辑部印 刷：北京北邮印刷有限公司本刊声明本通讯刊登的文章仅反映作者的观点，不代表本刊立场。其原创文章转载，请申请授权，并注明出处。中国人工智能学会通讯
新 世 纪 知 识 工 程 —— 在 哪 里 跨 越
陆汝钤 / 中国科学院数学与系统科学研究院
知识工程诞生于上世纪 60~70 年代。知识工程的诞生帮助人工智能摆脱了当时社会对它的信任危机，是人工智能中最接近实际、接近社会应用的分支。然而传统的知识工程经历了不太长的一段辉煌以后，又逐渐显示出它的诸多不足。这并不是因为知识工程这个研究方向先天地就缺乏存在价值，而是因为社会的进步使传统的知识工程理论和技术越来越显得不能适应。进入新世纪（21 世纪）以后，知识工程面临一个崭新的形势：万维网网站数呈现摩尔定律，每 15 个月翻一番；知识工程荣登超大规模时期；因特网浏览成为最重要的知识来源；以维基百科为代表的网上知识产品贡献巨大；大数据时代来临；MapReduce 的兴起为分布式处理技术的新突破开了个头；知识图谱技术走红。这一切都引发人们思考：知识工程的下一步应该是什么？
我们认为：首先，浏览器技术需要更新换代，改变每逢查询便推出一大堆网页的做法，代之以自动为用户提炼和综合知识；其次，为了实现伯纳斯的语义网理想，应有一桥飞架自然语言和 RDF 文本；第三，维基百科文章目前还类似一个个自生自灭的知识孤岛，如何加强管理并使其产生裂变和聚变的能量是当务之急；第四，知识图谱的技术目前还很原始，应该令其加速冲出初级阶段；第五，从大数据到大知识，路漫漫其修远兮；第六，知识驱动的分布式敏捷开发，是知识工程、分布式计算和软件敏捷开发的三结合，前程远大；第七，发展微小型分布式知识工程，打通能源循环的微血管，将会有助于我国抢占智能微网系统的国际领先技术；第八，知识服务应该提高到国家事业的高度，居一切服务之首。
综上所述，知识工程的形势总结和前途展望可以概括为八个词：网络、超大、微小、分布、敏捷、服务、产业、体系。
中国科学院数学与系统科学研究院研究员，中国科学院院士。研究兴趣为人工智能、知识工程和基于
知识的软件工程。中国人工智能学会通讯科技前沿大数据环境下序列模式挖掘及应用
敖 翔，李宏伟，罗 平，何 清 / 中国科学院计算技术研究所摘 要：尽管已经提出了许多序列模式挖掘的算法，但是在大数据环境下序列模式挖掘依然是一个挑战性问题。原因是序列模式挖掘拥有巨大的解搜索空间并且算法经常会输出大量的中间结果，从而使得算法的时间和空间效率低下。因此，截至目前仍然有许多研究围绕这一问题开展，并且取得了很大的进步。本文将结合大数据环境特点对近年来序列模式挖掘及其扩展问题的节点性工作和重要应用进行综述，同时对该方向未来的发展趋势进行展望。1. 绪 论
个挖掘问题的问题描述如下：
模式发现问题诞生于 1993 年 [1]，与分类、聚
设 I={I1, I2, …, Im} 是所有项的集合。给定一个类和异常点检测并称为数据挖掘四大问题 [2]。它指
序列集合 D，其中任意一条序列 Si 由一个元素列表的是从数据库找出频繁共现的“项”，被称为频繁
组成，每一个元素则由 I 中的项组成，以及一个用模式。模式发现问题在数据挖掘领域地位重要，有
户指定的最小支持度阈值 min_sup，序列模式挖掘大量关于模式发现的论文发表在重要数据挖掘、数
是指从 D 中挖掘出现频率不低于 min_sup 的子序列，据 库 会 议。Google Scholar 记 录 的 Agrawal 等 人 [1]
它们被称为频繁序列模式。提出的经典模式发现算法 Apriori 的论文单篇 , 被引用次数近 1.8 万次，已成为数据挖掘领域引用最多
如表 1 所示的一个序列集合中，字母代表项，的论文之一。
括号中的项视为无序，若设置最小支持度 min_sup
为 2，子序列〈(bc)a〉是一个频繁序列模式，它共
序列模式 (Sequential pattern)[3]（及其扩展情景
出现了 2 次，分别位于 s1 和 s2 中。模式 (Episode)[4]）是引入了时间关系和约束的数据模式，它指的是从时序数据中挖掘频繁出现的子序
表 1 序列模式挖掘示例序列集合列。这类模式因为蕴含了时间维度的补充信息，为推荐或者预测提供了潜在的帮助 [2]。序列模式挖掘
序列曾成功应用于网络挖掘 [5-6]、设备故障检测 [7]、软件 bug 检测 [8]、时空数据分析 [9]、股票趋势预测 [10]、
s1 a(abc)(ac)d(cf)化学与生物模式 [11-12] 和新闻分析 [13-14] 等。由于其
s2 (ad)c(bc)(ae)广泛的应用，它逐渐成为数据挖掘领域中一个专门
s3 e(ab)(cf)(bc)的研究主题。
s4 ae(bd)cbc
由于序列模式挖掘是从频繁模式挖掘 [1] 演化而
来，因此 Agrawal 和 Srikant[3] 最初提出该问题也是为了挖掘用户购物数据中行为模式来辅助决策。这
频繁情景模式挖掘，作为序列模式挖掘的扩展，
则考虑的是从一条长事件序列中挖掘频繁的子序
列，其问题描述如下：
设 E={E1, E2, …, Em} 是所有事件的集合。情景
01中国人工智能学会通讯模式发现问题是指从一条单一的事件长序列 S 中挖
一种经典的序列模式挖掘算法，它直接从频繁模式掘出现频率不小于 min_sup 的子序列，min_sup 是
挖掘的 Apriori 算法扩展而来。GSP 采用了水平的用户指定的最小支持度阈值参数。其中，S 中的任
数据格式，通过生成候选序列及扫描数据库的方法意一个事件集合均由 E 的事件组成。挖掘出来的频
逐层挖掘频繁序列模式。这里的水平数据格式指的繁子序列被称作频繁情景模式。
是依然以序列作为主要的观察对象。此外，GSP 还
采用了序列模式支持度的向下封闭性用于剪枝。与
如图 1 所示的一条事件序列中，字母代表事件，
Apriori 不同的是，GSP 在生成候选序列的时候考虑数字代表事件发生的时间，若设置最小支持度 min_
了有序和无序两种情况，比频繁模式挖掘中的候选sup 为 3，子序列〈A, B〉是一个频繁情景模式，它
项集生成过程更为复杂。采用了类似思想的算法还共出现了 3 次，在序列中用虚线矩形框标注。
有 AprioriAll[3] 和 PSP[18] 等。
图 1 频繁情景模式发现问题示例事件序列
SPADE (Sequential PAttern Discovery using
Equivalence classes)[19] 则是一种采用了垂直数据格
由于序列模式挖掘（及其扩展频繁情景模式挖
式的序列模式挖掘算法。它与 GSP 等算法的最大掘）和频繁模式挖掘的相关性，其算法多数也是由
不同是将数据库转化成了垂直格式，即以项作为核频繁模式挖掘算法改进而来，这些算法大致可以分
心观察对象，将包含项的序列 id 作为数据，从而为基于 Apriori 的算法 [3] 和模式增长算法 [15] 两类。
将原始数据库转换为一种垂直数据集进行挖掘。在其中，基于 Apriori 思想的算法主要思想是通过生
SPADE 算法中，长度为 2 的序列可以通过合并两个成候选集，以及扫描数据库进行逐层挖掘。这些算
长度为 1 的频繁项的垂直序列 id 列表得到。以此类法通常还基于 Apriroi 算法的支持度的向下封闭性
推，SPADE 最终可以逐层地挖掘出所有频繁的子序（downward closure）进行剪枝，即任何不频繁模
列。与 GSP 算法相比，SPADE 一定程度上缩小的式的超模式也不会频繁。但是在频繁情景挖掘问题
搜索空间，具有一定的性能优势。与 SPADE 类似中，这种性质不一定适用 [16]。这些算法虽然可以使
的算法还有 SPAM[20]、LAPIN-SPAM[21] 等。用剪枝技术提升效率，但是它们实际的缺点是生成了大量的候选序列并需要重复扫描数据库对每一个
类 似 地， 在 频 繁 情 景 模 式 挖 掘 领 域，Mannila候选序列计算支持度，这样的迭代过程使得挖掘效
等人提出的 WINEPI（WINdow EPIsode）算法是最率低下。为了缓解这些问题，基于模式增长的算法
早的一种基于 Apriori 思想的算法。在 WINEPI 算开始涌现。它们大多采用了分治思想，以当前的频
法中，一种基于时间窗口的情景模式频率的定义被繁序列模式作为前缀将原始序列分割成若干个投影
提出，并且采用了类似 GSP 算法的流程用于频繁数据库（projected databases），并在这些投影区域内
情 景 模 式 挖 掘。 但 与 GSP 不 同 的 是，WINEPI 在进行挖掘。相较于前一大类算法，基于模式增长的
进行候选序列频率统计时，只在划分出的时间窗口方法的好处是不需要生成序列的候选集合，并且缩
中进行。后来，Mannila 等人又提出了 MINEPI 算小了数据库扫描的范围，在性能上具有一定的优势。
法，用于挖掘频繁情景模式的最小发生（Minimal
occurrence）。在 MINEPI 算 法 中，除 了 情 景模 式
近年来，为了能够处理持续快速增长的大数据，
频率的定义采用了一种新定义的最小发生外，其余序列模式挖掘（及其扩展频繁情景模式挖掘）在并
流程均与 WINEPI 相同。行、增量和近似算法上也取得了显著进步。本文将从算法角度综述主要的序列模式挖掘（以及频繁情
由 于 频 繁 情 景 模 式 挖 掘 存 在 多 种 频 率 定 义，景模式挖掘）算法，并且回顾适用于大数据的序列
Achar 等人 [16] 提出了一种统一的基于 Apriori 的频模式挖掘（频繁情景模式挖掘）代表性算法。
繁情景模式挖掘算法，将各种常见的频率定义均可
以转化为该算法的特例。2. 序列模式挖掘算法综述
2.2 基于模式增长的序列模式挖掘算法2.1 基于 Apriori 的序列模式挖掘算法
FreeSpan[15] 和 PrefixSpan[22] 都 是 由 Han 和 Pei
GSP（Generalized Sequential Patterns）[17] 是
等人提出的基于模式增长的序列模式挖掘算法。它02中国人工智能学会通讯们都是基于频繁模式挖掘中的 FP-growth[23] 思想而
并行算法 pSPADE。pSPADE 的并行性主要来源于被 提 出 的。 其 中，FreeSpan 基 于 频 繁 项 将 数 据 库
对垂直格式数据库的划分，这种划分既可以横向也划 分 成 若 干 投 影 子 数 据 库， 然 后 在 各 个 子 数 据 库
可以纵向，最终实现了并行。采用了相似策略的算中进行序列模式的挖掘。PrefixSpan 则优化了构建
法还有 Par-ASP[29] 和 Par-CSP[30] 等。投 影 数 据 库 的 过 程， 它 首 先 检 查 前 缀 序 列 的 位 置并且只对后缀子序列进行投影，从而进一步缩小了
近 年 来， 随 着 数 据 量 的 不 断 增 大、 数 据 类 型搜索空间。当挖掘出长度的 l 的频繁序列模式后，
的不断变化，以及新型并行计算框架（如 HadoopFreeSpan 和 PrefixSpan 都会以该模式作为前缀，并
MapReduce 和 Spark）的不断涌现，并行序列模式根据各自的投影数据库构建方法构建新的投影数据
挖掘算法开始面向更大的数据及更加复杂的应用。库，然后挖掘长度为 l+1 的频繁序列模式。与 GSP
Berberich 等 人 [31] 提 出 了 基 于 MapReduce 的 并 行等基于 Apriori 的算法相比，FreeSpan 和 PrefixSpan
序列模式挖掘算法，从大规模的文本语料中挖掘 n的优势是仅通过短的频繁序列模式扩展出更长的子
元语法模式。Miliaraki 等人 [32] 考虑了更为复杂的序列，而不会产生投影数据库中不存在的候选序列
带 有 间 隔 约 束 的 序 列 模 式 挖 掘 问 题， 提 出 了 基 于集合。
MapReduce 的大规模带间隔约束的并行序列模式算
法 MS-FSM。该算法提出了一系列对序列集合的改
在频繁情景模式挖掘领域，基于模式增长的思
写方法，使得在 MapReduce 的任务划分更加平衡，想特别适合挖掘以最小发生作为频率定义的频繁
从而取得更好的并行效率。Beedkar 等人 [33] 又继续情 景 模 式， 因 此 有 相 关 算 法 被 提 出。MINEPI+[24]
对 MS-FSM 算法进行扩展，解决更为复杂的带有是一种改进的 MINEPI 算法，它采用了与 SPADE
层次结构的间隔约束序列模式挖掘问题。所提出的算法相近的垂直数据格式，以事件作为观察核心
LASH 算法在大规模文本数据集上的实验结果显示，将事件序列进行切分和投影，并通过事件发生时
当数据具有或者不具有层次结构时，LASH 算法的间列表的合并，发现情景模式的最小发生。这里，
表现均优于 MS-FSM 算法。我们最近的工作将序列MINEPI+ 将短的频繁情景模式作为前缀挖掘更长
模式挖掘技术与基于线段树的索引技术相结合，实的频繁情景模式，因此是一种典型的基于模式增长
际用于我国证券市场“老鼠仓”发现应用中，实现的算法。EPT[25] 算法则提出了一种情景模式前缀
了基于 MapReduce 和 Spark 的高可扩展趋同行为发树的结构，并通过一种前缀扩展的方式挖掘基于
现并行算法，将同等规模任务的运行时间从“天”最小发生的情景模式。Wu 等人提出的 UP-Span[26]
级缩短到分钟级。算 法 和 Achar 等 人 提 出 的 DFS 算 法 [27] 虽 然 都 是面向的其他频繁情景模式挖掘任务，但通过模式
3.2 增量序列模式挖掘增长的方式找到情景模式的最小发生都是其一项
在动态更新的流式数据中进行数据挖掘的需求重要步骤。
由来已久 [34]，对于序列模式挖掘来说，当数据发生3. 大数据环境下的序列模式挖掘
少量更新时对全体数据重新进行挖掘是不可取的。
因此，一些增量序列挖掘算法被提出以适应不断增
大 数 据 环 境 的 4V 特 性 中 的 Volume、Velocity
长的数据，这类算法在更新迅速的大数据中显得十和 Variety 对序列模式挖掘算法提出了新的挑战。为
分重要。了适应大数据环境、一些并行算法、增量式算法，以及近似算法被相继提出，下面简单回顾其中一些
Parthasarathy 等人 [35] 提出的 ISM 增量序列模代表性算法。
式挖掘算法，基于 SPADE 算法进行扩展，以最小
的 I/O 和计算代价处理新增数据。具体地，一种增3.1 并行序列模式挖掘
量序列晶格的结构被用于存储所有频繁序列 , 以及
早期的并行序列模式挖掘算法大多被用于解决
原数据库中位于负边界中的所有序列。这些位于负
边界中的序列可能由于新增数据的加入 , 而变成频算法效率低下的问题。因此，许多并行算法是由其
繁序列模式。Masseglia 等人 [36] 则提出了一种基于串行版本改进得到。例如，Zaki[28] 扩展了由他自己
Apriori 思想的增量序列模式挖掘算法 ISE。ISE 利提出的 SPADE 算法，提出了在内存共享框架下的
03中国人工智能学会通讯用尽可能少的老频繁序列模式的信息最小化计算
LCA 算法存在少计算项集频率的情况，这个误差代价，挖掘出新增数据中的频繁模式。Cheng 等
的上界是 εn ，这里 ε 是用户设定的一个误差率参人 [37] 提出的 IncSpan，通过维护一个“几乎频繁”
数。类似地，如 Carma 算法 [42]、estDec 算法 [43]、的序列集合作为新增数据中可能成为频繁序列模
FP-Stream 算法 [44] 和 FDPM 算 法 [45] 都 考 虑 了 类式的候选集 , 高效地进行增量挖掘。Gao 等人 [38]
似的挖掘问题并借鉴了类似思想设计算法。又如则提出了 StreamCloSeq 算法增量，挖掘频繁闭序
前文所述的文献 [39] 中的算法也是一种近似算法，列模式。
用于动态数据中的频繁情景模式挖掘。此外，Kum
等人 [46] 则对序列模式的形式进行近似，提出了近
对于频繁情景模式挖掘，Patnaik 等人 [39] 较早
似序列模式挖掘的概念，它的基本思想是挖掘那些在 频 繁 情 景 挖 掘 问 题 中 考 虑 了 数 据 动 态 问 题。 在
可能被多个序列共享的近似的序列模式，而不是找Patnaik 所描述的问题中，事件序列以批量方式更新；
到那些确定的序列模式。然后，对于一段新的事件序列，首先使用已有的频繁情景挖掘算法在增量序列上挖掘候选的情景模式。
4. 序列模式挖掘趋势展望他们工作的主要贡献是提出了一个频率的下界，凡是频率超过此下界的情景模式很有可能在更新后的
近年来，数据挖掘会议和期刊中将模式与统计序列中是一个 top k 的频繁情景模式。我们 [40] 率先
结合成为较热门的研究方向 [47-49]，通过统计方法对将频繁情景模式发现算法推广到在线形式，提出的
数据模式进行剪枝、判断模式的“有趣性”成为热点。MESELO 算法从动态更新的序列中 , 不断快速地挖
例如，Nakagawa 等人 [50] 提出基于统计的安全剪枝掘出最新的频繁情景集合。这里，事件序列总是一
规则对数据模式进行剪枝；Tatti[47] 提出的基于概率个时刻接一个时刻地连续不断更新，而不是批量的
的划分模型 , 可以根据所预测的“有趣性”对无间更新数据。这个问题中数据更新更快，对算法的响
隔的频繁情景模式进行排序。此外，在数据库会议应时间要求更加严格。具体地，在 MESELO 算法中，
和期刊中，面向大规模数据的具有高可扩展能力的一种最后情景发生的概念被提出，基于最后情景发
序列模式挖掘算法也不断发表 [33,51]。生，动态更新的事件序列中的情景最小发生可以快速地被找到。另外，一种高度压缩的场景 trie 则被
笔者认为 , 近年来面向大数据需求的序列模式提出用来高效存储事件序列的更新信息，辅助算法
挖掘算法将成为新的研究趋势与热点。首先，学术快速计算。MESELO 算法是首个单遍历的频繁情景
界普遍承认在传统序列模式挖掘输出的模式数量模式挖掘算法，较传统的方法提高了 1~2 数量级，
多，存在冗余。因此，如何减少模式的输出数量，响应时间通常不超过 1 s。
降低冗余度成为面向大数据的特别需求。目前，热
门解决方案是引入概率统计的思想初步解决该问3.3 序列模式挖掘近似算法
题，此方向仍需要更多深入的研究。其次，打破传
统的频率框架，设计新的“有趣性”度量，定义适
数据中通常蕴含大量的频繁模式。确定性算法
用于特定应用的数据模式也可能是解决冗余问题的能够挖掘出所有频繁的模式，具有最高的准确性，
一条途径。第三，在新的大数据计算框架下，研究但通常会花费大量计算时间，并且消耗大量内存。
高可扩展的序列模式挖掘算法仍将会是一个主流趋而序列模式挖掘近似算法是适应大数据的另一种方
势。与传统并行算法所不同的是，近年涌现出的并式。但是，近似算法所挖掘的结果中却存在着误差。
行序列模式挖掘算法更加追求任务划分上的负载均因此，错误误差的估计通常是近似算法重点关注的
衡，充分发挥大数据计算框架的优势，从而取得了对象。其中，Manku 等人 [41] 提出的 LCA（Lowest
性能大幅提升。Common Ancestors） 算 法 是 一 个 代 表 性 的 从 流 数据中挖掘频繁模式的近似算法。在 LCA 算法中，
5. 结束语增量数据以大小为 B 的块更新。对于第 n 批数据，LCA 先计算新增数据中的数据模式及其频率，然后
本文回顾了序列模式挖掘及其扩展问题频繁情更新到历史的结果中。但是，对于那些发生次数小
景模式挖掘的问题定义及若干代表性算法的主要思于 n 的模式，LCA 会将它们从内存中删除。因此，
想；结合大数据特性，还从并行、增量和近似算法04中国人工智能学会通讯三个维度，对相关序列模式挖掘算法和频繁情景模
相关文献，分析和展望了序列模式挖掘领域未来可式挖掘算法进行了简要综述；此外结合最新发表的
能的发展趋势。参考文献[1] Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases.ACM
SIGMOD Record, 22(2): 207-216, 1993.[2] Aggarwal C, Han J. Frequent pattern mining. Springer, 2014.[3] Agrawal R, Srikant R. Mining sequential patterns. In Proceedings of IEEE ICDE’95, pages: 3-14, 1995.[4] Mannila H, Toivonen H, Verkamo A I. Discovery of frequent episodes in event sequences. Data Mining and
Knowledge Discovery, 1(3): 259-289, 1997.[5] Chen M S, Park J S, Yu P S. Efficient data mining for path traversal patterns. IEEE Transactions on
Knowledge and Data Engineering, 10(2): 209-221, 1998.[6] Srivastava J, Cooley R, Deshpande M, et al. Web usage mining: Discovery and applications of usage
patterns from web data. ACM SIGKDD Explorations Newsletter, 1(2): 12-23, 2000.[7] Laxman S, Sastry P S, Unnikrishnan K P. A fast algorithm for finding frequent episodes in event streams. In
Proceedings of ACM SIGKDD’07, pages: 410-419, 2007.[8] Li Z, Lu S, Myagmar S, et al. CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System
Code. In Proceedings of OSDI’04, pages: 289-302, 2004.[9] O r a k z a i F, D e v o g e l e T, C a l d e r s T. To w a r d s D i s t r i b u t e d C o n v o y P a t t e r n M i n i n g . a r X i v p r e p r i n t
arXiv:, 2015.[10] Ng A, Fu A W C. Mining frequent episodes for relating financial events and stock trends. In Proceedings of
PAKDD’03, pages: 27-39, 2003.[11] Deshpande M, Kuramochi M, Wale N, et al. Frequent substructure-based approaches for classifying chemical
compounds. IEEE Transactions on Knowledge and Data Engineering, 17(8): , 2005.[12] Zhang S, Wang J T L. Discovering frequent agreement subtrees from phylogenetic data. IEEE Transactions
on Knowledge and Data Engineering, 20(1): 68-82, 2008.[13] Ao X, Luo P, Li C, et al. Discovering and learning sensational episodes of news events. In Proceedings of
WWW’14, pages: 217-218, 2014.[14] Fahed L, Brun A, Boyer A. Episode rules mining algorithm for distant event prediction. Research report, 2014.[15] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.-C. Hsu, “Freespan: frequent pattern-projected
sequential pattern mining,” In Proceedings of ACM SIGKDD’00, pages: 355–359, 2000.[16] Achar A, Laxman S, Sastry P S. A unified view of the apriori-based algorithms for frequent episode discovery.
Knowledge and information systems, 31(2): 223-250, 2012.[17] R. Srikant and R. Agrawal, “Mining sequential patterns: Generalizations and performance improvements,” In
Proceedings of ACM EDBT’96, pages: 3-17, 1996.[18] F. Masseglia, F. Cathala, and P. Poncelet, “The psp approach for mining sequential patterns,” In Proceedings
of PKDD’98, pages: 176-184, 1998.[19] M.J.Zaki, “Spade: An efficient algorithm for mining frequent sequences,” Machine Learning, vol. 42, no.1-2,
pages: 31-60,2001.[20] J. Ayres, J. Flannick, J. Gehrke, and T. Yiu, “Sequential pattern mining using a bitmap representation,” In
Proceedings of ACM SIGKDD’02 pages: 429-435, 2002.[21] Z.Yang and M.Kitsuregawa, “Lapin-spam: An improved algorithm for mining sequential pattern,” In IEEE ICDE
Workshops, 2005.
05中国人工智能学会通讯[22] J. Pei, J. Han, B. Mortazavi-asl, H. Pinto, Q. Chen, U. Dayal, and M. chun Hsu, “Prefixspan: Mining
sequential patterns efficiently by prefix-projected pattern growth,” In Proceedings of IEEE ICDE’01, pages:
215-224, 2001[23] J. Han and J. Pei, “Mining frequent patterns by pattern-growth: methodology and implications,” SIGKDD
Explor. Newsl., vol. 2, no. 2, pages: 14-20, Dec. 2000.[24] Huang K Y, Chang C H. Efficient mining of frequent episodes from complex sequences. Information Systems,
33(1): 96-114, 2008.[25] Ma X, Pang H H, Tan K L. Finding constrained frequent episodes using minimal occurrences. In Proceedings
of IEEE ICDM’04, pages: 471-474, 2004.[26] Wu C W, Lin Y F, Yu P S, et al. Mining high utility episodes in complex event sequences. In Proceedings of
ACM SIGKDD’13, pages: 536-544, 2013.[27] Achar A, Ibrahim A, Sastry P S. Pattern-growth based frequent serial episode discovery. Data & Knowledge
Engineering, 87: 91-108, 2013.[28] Mohammed J. Zaki. Parallel sequence mining on shared-memory machines. JPDC, 2001.[29] Shengnan Cong, Jiawei Han, Jay Hoeflinger, and David Padua. A sampling-based framework for parallel data
mining. In Proceedings of PPoPP’05, 2005.[30]
Shengnan Cong, Jiawei Han, and David Padua. Parallel mining of closed sequential patterns. In Proceedings
of KDD’05, 2005.[31] Berberich K, Bedathur S. Computing n-gram statistics in MapReduce. In Proceedings of ACM EDBT’13,
pages: 101-112, 2013.[32] Miliaraki I, Berberich K, Gemulla R, et al. Mind the gap: large-scale frequent sequence mining. In Proceedings
of ACM SIGMOD’15, pages:797-808, 2013.[33] Beedkar K, Gemulla R. LASH:Large-Scale Sequence Mining with Hierarchies. In Proceedings of ACM
SIGMOD’15, pages:491-503, 2015.[34] Babcock B, Babu S, Datar M, et al. Models and issues in data stream systems. In Proceedings of ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages: 1-16, 2002.[35] S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas, “Incremental and interactive sequence mining,”
In Proceedings of CIKM’99, pages: 251-258, 1999.[36] F. Masseglia, P. Poncelet, and M. Teisseire, “Incremental mining of sequential patterns in large databases,”
DKE, 46(1): 97-121, 2003.[37] H. Cheng, X. Yan, and J. Han, “Incspan: incremental mining of sequential patterns in large database,” In
Proceedings of ACM SIGKDD’04 pages: 527-532, 2004.[38] C. Gao, J.Wang, and Q.Yang, “Efficient mining of closed sequential patterns on stream sliding window,” In
Proceedings of IEEE ICDM’11, 2011.[39] Patnaik D, Laxman S, Chandramouli B, et al. Efficient episode mining of dynamic event streams. In
Proceedings of IEEE ICDM’12, pages: 605-614, 2012.[40] Ao X, Luo P, Li C, et al. Online Frequent Episode Mining. In Proceedings of IEEE ICDE’15, pages: 891-902,
2015.[41] Manku G S, Motwani R. Approximate frequency counts over data streams. In Proceedings of VLDB’02,
pages: 346-357, 2002.[42] Hidber C. Online association rule mining. ACM, 1999.[43] Chang J H, Lee W S. Finding recent frequent itemsets adaptively over online data streams. In Proceedings of
ACM SIGKDD’03, pages: 487-492, 2003.[44] Giannella C, Han J, Pei J, et al. Mining frequent patterns in data streams at multiple time granularities. Next06中国人工智能学会通讯[22] J. Pei, J. Han, B. Mortazavi-asl, H. Pinto, Q. Chen, U. Dayal, and M. chun Hsu, “Prefixspan: Mining
sequential patterns efficiently by prefix-projected pattern growth,” In Proceedings of IEEE ICDE’01, pages:
215-224, 2001[23] J. Han and J. Pei, “Mining frequent patterns by pattern-growth: methodology and implications,” SIGKDD
Explor. Newsl., vol. 2, no. 2, pages: 14-20, Dec. 2000.[24] Huang K Y, Chang C H. Efficient mining of frequent episodes from complex sequences. Information Systems,
33(1): 96-114, 2008.[25] Ma X, Pang H H, Tan K L. Finding constrained frequent episodes using minimal occurrences. In Proceedings
of IEEE ICDM’04, pages: 471-474, 2004.[26] Wu C W, Lin Y F, Yu P S, et al. Mining high utility episodes in complex event sequences. In Proceedings of
ACM SIGKDD’13, pages: 536-544, 2013.[27] Achar A, Ibrahim A, Sastry P S. Pattern-growth based frequent serial episode discovery. Data & Knowledge
Engineering, 87: 91-108, 2013.[28] Mohammed J. Zaki. Parallel sequence mining on shared-memory machines. JPDC, 2001.[29] Shengnan Cong, Jiawei Han, Jay Hoeflinger, and David Padua. A sampling-based framework for parallel data
mining. In Proceedings of PPoPP’05, 2005.[30]
Shengnan Cong, Jiawei Han, and David Padua. Parallel mining of closed sequential patterns. In Proceedings
of KDD’05, 2005.[31] Berberich K, Bedathur S. Computing n-gram statistics in MapReduce. In Proceedings of ACM EDBT’13,
pages: 101-112, 2013.[32] Miliaraki I, Berberich K, Gemulla R, et al. Mind the gap: large-scale frequent sequence mining. In Proceedings
of ACM SIGMOD’15, pages:797-808, 2013.[33] Beedkar K, Gemulla R. LASH:Large-Scale Sequence Mining with Hierarchies. In Proceedings of ACM
SIGMOD’15, pages:491-503, 2015.[34] Babcock B, Babu S, Datar M, et al. Models and issues in data stream systems. In Proceedings of ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages: 1-16, 2002.[35] S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas, “Incremental and interactive sequence mining,”
In Proceedings of CIKM’99, pages: 251-258, 1999.[36] F. Masseglia, P. Poncelet, and M. Teisseire, “Incremental mining of sequential patterns in large databases,”
DKE, 46(1): 97-121, 2003.[37] H. Cheng, X. Yan, and J. Han, “Incspan: incremental mining of sequential patterns in large database,” In
Proceedings of ACM SIGKDD’04 pages: 527-532, 2004.[38] C. Gao, J.Wang, and Q.Yang, “Efficient mining of closed sequential patterns on stream sliding window,” In
Proceedings of IEEE ICDM’11, 2011.[39] Patnaik D, Laxman S, Chandramouli B, et al. Efficient episode mining of dynamic event streams. In
Proceedings of IEEE ICDM’12, pages: 605-614, 2012.[40] Ao X, Luo P, Li C, et al. Online Frequent Episode Mining. In Proceedings of IEEE ICDE’15, pages: 891-902,
2015.[41] Manku G S, Motwani R. Approximate frequency counts over data streams. In Proceedings of VLDB’02,
pages: 346-357, 2002.[42] Hidber C. Online association rule mining. ACM, 1999.[43] Chang J H, Lee W S. Finding recent frequent itemsets adaptively over online data streams. In Proceedings of
ACM SIGKDD’03, pages: 487-492, 2003.[44] Giannella C, Han J, Pei J, et al. Mining frequent patterns in data streams at multiple time granularities. Next06中国人工智能学会通讯 科技前沿
接触追踪 : 传染病防控的 AI 方法
杨 博 ，陈贺昌 / 吉林大学摘 要：2016 年 10 月，IBM 位于南非约翰内斯堡实验室的研究人员发布了他们最新的研究成果：使用廉价的无线电标签匿名追踪结核病的接触传播路径 [1]。这项研究是 IBM 助力 WHO（世界卫生组织）终止结核病的一项重要举措。接触追踪是传染病防控的一项关键技术。在面临突发传染病袭击时，接触追踪系统可以帮助人们迅速定位、隔离感染者和高风险个体，及时阻止传染病的进一步扩散和大规模爆发。此外，通过接触追踪技术建立的传染病传播网络还可以帮助人们可视化病毒的实际传播路径，模拟传播过程，评估爆发趋势，进而制定更加有效的防控策略。建立行之有效的接触追踪系统意义重大，受到了各国政府、学界及业界的广泛重视，涌现出多种方法和技术。实际上，采用便携式无线传感设备追踪传染病的技术只是其中之一，早在 2006 年就被提出，在物联网和大数据技术炙手可热的今天，又重新焕发活力。本文主要从 AI（人工智能）和大数据的视角分析接触追踪技术的发展现状和面临的挑战，希望能为相关领域的研究者提供有益的参考和启发。引言
个月就夺去 122 人的生命 [3]，3 个月后死亡人数上
升至 591 人。由此可见，在人类抵抗各类传染病入
传染病的每次爆发都会给人类社会带来巨大损
侵的斗争中，仅仅依靠研发新疫苗的“亡羊补牢式”失。1918 年的西班牙大流感导致 2 000 多万人死亡。
策略远不够用，还需更加积极有效的“主动防控”截止到 2013 年，全球约有 33 亿人感染过疟疾，每
方法，以迅速发现和封锁突发和新发传染病的传播60 秒就有一人死于疟疾。肺结核致死率已经超过艾
途径，将它们禁锢在最小范围，直至根除。滋病，成为世界上最致命的传染病，南非约有 80%的人口患有潜伏性肺结核，仅在 2013 年就有 45 万
大多数传染病都通过人与人的“接触”传播。例肺结核阳性患者。传染病在威胁人类生命的同时
在计算传染病学中，人与人之间的接触被定义为“相也带来了巨大经济损失。据统计，疟疾每年给非洲
同 物 理 环 境 中 不 同 个 体 间 的 交 互 行 为 ”[4]。 人 与 人各国造成的经济损失多达 120 亿美元，季节性流感
的接触行为构成传播病毒的“接触网络”，网络结每年给美国造成的经济负担高达 870 亿美元 [2]。
点表示个体，网络链接表示接触关系。接触网络的
结构显著影响着病毒扩散的时空模式。以通过飞沫
医学的进步提供了抵抗各种传染病的疫苗和药
扩散的呼吸道传染病为例，个体间面对面的谈话、物，大大降低了它们对人类社会的危害，但由病毒
握手，以及人群的聚集、乘坐交通工具等行为都会的抗药性和变异性所导致的突发和新发传染病依然
引起病毒的扩散，增加感染者传染易感者的几率。令我们猝不及防、束手无策，始终处于“被动挨打”
追踪人的接触行为，还原出“隐形”的病毒传播通道，的 局 面。 例 如，2009 年 爆 发 的 H1N1 流 感， 变 异
不仅可以快速定位和隔离接触过感染者的高风险个为 2014 年的 H7N9 流感和 2015 年的 H3N2 流感。
体，还可以帮助人们定量分析传染病传播的途径、H3N2 病毒于 2015 年 1 月开始在香港扩散，短短 1
过程和趋势，制定相应的疫情控制策略。08中国人工智能学会通讯
接触追踪面临的最大困难在于，直接描述接 度和接触频率等信息构建出局部校园的接触网络，触行为的数据难以获取。由于个体间的接触行为常 并基于该网络模拟了校园内部的流感爆发过程 [7]。常是琐碎、多样，不易被直接观测和记录，因此很 他们研究中发现，教室内部是校园接触的多发场景，难收集到足够多、高质量的接触数据，供接触追踪 课间和午休是校园接触的多发时段。使用。在疾病传播过程中，我们能观测到的是疾病
传播所产生的影响，而非个体间的直接相互作用。如图 1 所示，在 H7N9 禽流感爆发过程中，我们很难确定一名患者在出行途中通过接触传染了哪些个体，而仅能观测到不同时间和空间内新增的 H7N9病例数和死亡人数。
（a）问卷调查
（b）移动通讯设备
图 2 两种常用的个体接触追踪方法
问卷调查方法获得的个体接触信息通常不完
整，为了提高个体接触记录的准确性，一些研究者
开始寻求移动通讯设备（如手机）或无线传感设备
（如可穿戴传感器）的帮助。
图 1 2013 年 H7N9 在中国大陆爆发前期的累计病
早 在 2006 年， 由 MIT 媒 体 实 验 室 研 究 员
Nathan Eagle 和 Alex Pentland 提 出 的 现 实 挖 掘
例空间分布 [5]
（reality mining）就建议采用可穿戴无线传感设备
记录人们的日常活动信息 [8-9]。他们开发了一个实
流行病学和计算机科学的学者对如何准确捕获
验系统，记录了一些 MIT 学生在教学楼内一段时间个体接触行为数据、如何从其他数据源间接推断出
的活动轨迹，进而建立了一个描述他们接触关系的接触网络做了很多探索，提出了多种方法。这些方
小型社会网络 [10]。法大都广泛采用了与 AI 相关的技术，如智能感知、网络分析、数据可视化、机器学习、多源异构数据
2011 年，Yoneki 研发了首个基于手机终端的挖掘、数据驱动的逆向工程和多智能体模拟等。根
接触模式发现软件 FluPhone，该软件可自动检测据接触建模的粒度，现有方法又可分为个体接触追
并记录用户之间的接触行为 [11]。研究者通过该软踪、群体接触追踪和动态接触追踪，下面分别叙述
件收集了剑桥大学校园内 36 名用户的接触信息，和讨论。
构建了用户间不同时段的接触网络，并结合 SEIR
模型在该网络上模拟了流感爆发过程。由于 GPS研究现状分析
和 蓝 牙 功 耗 大， 导 致 手 机 待 机 时 间 短，Yoneki 等
人 将 能 耗 小、 使 用 时 间 长 的 可 穿 戴 传 感 器 应 用个体接触追踪
于 FluPhone 软 件 中， 研 发 了 新 的 接 触 追 踪 软 件
该类方法通过记录个体接触的时间、地点、接
EpiMap[12]。考虑到流行病爆发的高危地区多分布
在经济落后的发展中国家，这些地区的无线通讯设触频率、持续时间等详细信息来构建细粒度的“个
施落后，EpiMap 采用卫星通讯对接触数据进行传体到个体”接触网络。目前常用的接触信息记录手
输和存储。段是调查问卷 [6]、无线通信和无线传感。图 2 示出了两种常用的个体接触追踪方法。
由于可以持续、准确的记录个体的接触事件（如
时间、地点、对象、时长），可穿戴无线传感器逐
2012 年，Potter 等人采用问卷调查方法研究了某高中 1 074 名学生的接触行为，根据接触时间长
09中国人工智能学会通讯渐成为一种收集“小范围”内高精度接触数据的工
备追踪个体接触的另一个问题是隐私问题。这些用具，应用于医院和校园等场景中的接触模式研究。
作医疗数据收集的追踪器除了记录接触行为，也很Salathé 等人利用无线传感器收集了美国一所高中
容易追踪和记录人的移动轨迹，而这些通常都会被788 名学生一天的接触行为，据此构建了一个基于
认为是侵犯隐私的做法。另一个敏感的问题在于，个体的校园接触网络 [13]，进而发现校园接触网络
佩戴追踪器等于向别人宣告自己是某种传染病的患具有高密度连接和小世界结构的特征 [14]。Isella 等
者。例如，在非洲国家，肺结核患者会被打上社会人使用射频识别设备采集了美国一所儿童医院 119
偏见的烙印。人（包括医护人员、重症儿童和护理人员）之间的16 000 次接触，建立了医院场景的接触结构 [15]。类
群体接触追踪似的，Stehlé 等人使用无线射频识别设备采集了一
为了克服细粒度个体接触数据难以获取的困所法国小学内学生的接触数据 [16]。
难，近年来，能够刻画人口异构特征，并能建模流
无线射频追踪器的收发距离有限，只能在某一
行病传播动力学的复合群体模型（见图 4）正日益特定区域正常工作。2016 年，IBM 非洲实验室的研
受到关注。这类模型不仅具备模拟传播过程的能力，究员 Kurien 和 Shingirirai 发明了一种无线电标签，
还能刻画更大规模人口的接触结构。复合群体模型解决了追踪器收发距离短的问题，并将该技术用于
将人口按年龄属性或者空间位置划分为若干亚人群结核病追踪 [1]（见图 3）。每块标签包含有一个小
(meta-population)， 使 得 同 一 亚 人 群 中 的 个 体 具 有型传感器、存储设备和电池。被个体携带的无线电
相似的生物学特性（如易感性、传染力、潜伏期、标签可以互相通讯，当两个标签互联时，个体接触
恢复期），进而利用亚人群间的群体接触行为代替行为就被记录下来。无线电标签收集的接触数据集
个体接触行为建模流行病的传播过程 [17]。基于该模中呈现在一个三维可视化系统中，利用该系统提供
型，流行病的感染和传播可以被描述为一个反应扩的智能数据分析方法，医疗人员能够实时查看结核
散 (reaction-diffusion) 过程 [18]。反应，刻画了亚人病患者的时空分布，追踪结核病毒的传播路径，发
群内的个体感染过程；扩散，则刻画了流行病通过现高风险易感人群。由于结核病疫苗费用很高，这
群体接触结构在亚人群间的转移过程。此外，由于些接触数据还可帮助医疗人员确定疫苗接种个体的
流行病控制策略通常是面向复合群体的，例如，在优先级。
考虑如何规划疫苗分配策略时，接种人群通常按年
龄进行分组，构建复合群体的接触网络也具有实际
图 4 复合群体的反应扩散模型 [19]
图 3 IBM 研究人员手持无线电结核病追踪器 [1]
基于调查问卷的方法首先被用于构建复合群体
的接触网络。2008 年，Mossong 等人在欧洲开展了
虽然使用分发 / 收集调查问卷、移动通讯设备
Polymod 研究项目，组织了一次大范围的接触行为或无线传感设备可以收集到非常细致的个体接触信
调查，包括来自欧洲 8 个国家的 7 290 名参与者，息，但由于过于昂贵的成本，这类方法大都局限在小规模人口的实验中，还没有推广到大范围、大规模个体接触行为的追踪与分析。采用无线可穿戴设10中国人工智能学会通讯共收集了 97 904 条接触记录 [20]。他们对该问卷数
Iozzi 等人基于 55 773 人的问卷调查数据建模据的研究发现，接触行为具有明显的空间异构性，
了具有意大利社会特征的虚拟社会，通过智能体在绝大多数的个体接触发生在家庭 (23%)、工作场所
该虚拟社会中模拟人的日常迁移行为，得到复合群(21%)、学校 (14%)、娱乐场所 (16%) 和交通工具 (3%)
体的接触矩阵 [4]，并基于该矩阵较好的模拟了意中，并且不同场景下的接触结构具有明显不同的特
大利 B19（人类微小病毒）的爆发过程。类似的，征。该研究还发现一些与个体年龄相关的接触模式，
Eubank 等人使用大规模智能体仿真模拟了城市内的如在许多场景中（如学校），个体更倾向于与年龄
个体移动，并据此建模了群体接触结构 [22]。他们使相近的人接触；孩子和家长的接触大多发生在家里，
用的数据包括人口普查数据、土地使用、人口移动而成年人间的接触则多发生在工作场所。根据这些
及其他日常行为数据。发现，他们将人口按年龄分成若干个亚人群，构成基于年龄分组的复合群体模型，进而根据问卷数据
动态接触追踪估计出不同年龄组间的交互概率，建立了基于复合
上述工作大都只关注建模接触行为的静态属群体的接触矩阵，如图 5 所示。
性，如接触对象（和谁接触）、接触场景（在哪接触）、
A Household
接触频率和接触时长等。换言之，这些工作假设个
体的接触模式静止不变。然而，在现实世界中，人85+
的接触行为常常随时间变化，呈现出不同的时空模
式。例如，接触行为会随着天气和季节呈周期性变45 45
化；接触行为在工作日、周末、假期会有明显不同；
在疾病爆发期间，个体会调整自身的接触行为，如
减少出行或戴口罩出行，以应对疫情的威胁 [23-24]。
此外，政府实施的疫情控制手段也会显著改变个体
DGeneral community
的 接 触 模 式 。[17,25-26] 例 如， 在 2009 年 香 港 H1N185+
流感爆发过程中，减少航班、关闭学校和接种疫苗
等干预措施都会显著改变个体的接触行为 [24]。45 45
个体之间的动态接触比静态接触更加难以观测0
和记录。由于涉及隐私保护等问题，我们不能指望
大部分个体都同意佩戴无线传感设备，并实时收集
他们的动态接触行为。面对这些困难，我们能否另
图 5 复合群体接触矩阵 [21（] A. 家庭场景；B. 学校场景；
辟蹊径，不“直接”去捕获和记录个体的动态接触
行为，而是从其他易于获得的数据源中“间接”推
C. 工作场景；D. 公共场景）
断出大规模人口的动态接触模式？
基于多智能体的仿真模拟方法也被应用于接触网络构建（见图 6）。这类方法一般结合问卷调查和人口普查等数据，构建复合群体的接触结构。
随着信息技术在医疗领域的广泛应用，类似图
1 所示的传染病监控数据与日俱增。这些监控数据
图 6 基于多 Agent 系统模拟的接触追踪
记录了与传染病扩散相关的时空信息，是传播模型
作用于真实接触网络的结果（如图 7(a) 所示），可
看作是隐含接触网络的一种外在表现形式。这启发
我们可以尝试从传染病监控数据中“反推出”产生
这些数据的动态接触网络（如图 7(b) 所示）。本质上，
这是一个复杂的逆向工程问题，即从观察到的动力
学现象推断出导致该现象出现的动态结构；或者说，
利用传染病传播趋势的时变性反推出接触行为的时
11中国人工智能学会通讯共收集了 97 904 条接触记录 [20]。他们对该问卷数
Iozzi 等人基于 55 773 人的问卷调查数据建模据的研究发现，接触行为具有明显的空间异构性，
了具有意大利社会特征的虚拟社会，通过智能体在绝大多数的个体接触发生在家庭 (23%)、工作场所
该虚拟社会中模拟人的日常迁移行为，得到复合群(21%)、学校 (14%)、娱乐场所 (16%) 和交通工具 (3%)
体的接触矩阵 [4]，并基于该矩阵较好的模拟了意中，并且不同场景下的接触结构具有明显不同的特
大利 B19（人类微小病毒）的爆发过程。类似的，征。该研究还发现一些与个体年龄相关的接触模式，
Eubank 等人使用大规模智能体仿真模拟了城市内的如在许多场景中（如学校），个体更倾向于与年龄
个体移动，并据此建模了群体接触结构 [22]。他们使相近的人接触；孩子和家长的接触大多发生在家里，
用的数据包括人口普查数据、土地使用、人口移动而成年人间的接触则多发生在工作场所。根据这些
及其他日常行为数据。发现，他们将人口按年龄分成若干个亚人群，构成基于年龄分组的复合群体模型，进而根据问卷数据
动态接触追踪估计出不同年龄组间的交互概率，建立了基于复合
上述工作大都只关注建模接触行为的静态属群体的接触矩阵，如图 5 所示。
性，如接触对象（和谁接触）、接触场景（在哪接触）、
A Household
接触频率和接触时长等。换言之，这些工作假设个
体的接触模式静止不变。然而，在现实世界中，人85+
的接触行为常常随时间变化，呈现出不同的时空模
式。例如，接触行为会随着天气和季节呈周期性变45 45
化；接触行为在工作日、周末、假期会有明显不同；
在疾病爆发期间，个体会调整自身的接触行为，如
减少出行或戴口罩出行，以应对疫情的威胁 [23-24]。
此外，政府实施的疫情控制手段也会显著改变个体
DGeneral community
的 接 触 模 式 。[17,25-26] 例 如， 在 2009 年 香 港 H1N185+
流感爆发过程中，减少航班、关闭学校和接种疫苗
等干预措施都会显著改变个体的接触行为 [24]。45 45
个体之间的动态接触比静态接触更加难以观测0
和记录。由于涉及隐私保护等问题，我们不能指望
大部分个体都同意佩戴无线传感设备，并实时收集
他们的动态接触行为。面对这些困难，我们能否另
图 5 复合群体接触矩阵 [21（] A. 家庭场景；B. 学校场景；
辟蹊径，不“直接”去捕获和记录个体的动态接触
行为，而是从其他易于获得的数据源中“间接”推
C. 工作场景；D. 公共场景）
断出大规模人口的动态接触模式？
基于多智能体的仿真模拟方法也被应用于接触网络构建（见图 6）。这类方法一般结合问卷调查和人口普查等数据，构建复合群体的接触结构。
随着信息技术在医疗领域的广泛应用，类似图
1 所示的传染病监控数据与日俱增。这些监控数据
图 6 基于多 Agent 系统模拟的接触追踪
记录了与传染病扩散相关的时空信息，是传播模型
作用于真实接触网络的结果（如图 7(a) 所示），可
看作是隐含接触网络的一种外在表现形式。这启发
我们可以尝试从传染病监控数据中“反推出”产生
这些数据的动态接触网络（如图 7(b) 所示）。本质上，
这是一个复杂的逆向工程问题，即从观察到的动力
学现象推断出导致该现象出现的动态结构；或者说，
利用传染病传播趋势的时变性反推出接触行为的时
11中国人工智能学会通讯[2] N. Molinari, I. Ortega-Sanchez, M.L. Messonnier, W.W. Thompson, P.M. Wortley, E. Weintraub, C.B. Bridges. The
annual impact of seasonal influenza in the US: measuring disease burden and costs. Vaccine, ): 5086-
5096.[3] Center for Health Protection of Hong Kong. Flu express, ), 1-5. Published on Jan 29, 2015.[4] F. Iozzi, F. Trusiano, M. Chinazzi, F.C. Billari, E. Zagheni, S. Merler, M. Ajelli, E. Del Fava, P. Manfredi. Little Italy:
an agent-based approach to the estimation of contact patterns-fitting predicted matrices to serological data. PLoS
Computational Biology, ): e1001021.[5] 腾讯新闻网 : http://news.qq.com/zt/huizong.htm.[6] A. Melegaro, M. Jit, N. Gay, E. Zagheni, W.J. Edmunds. What types of contacts are important for the spread of
infections? Using contact survey data to explore european mixing patterns. Epidemics, ): 143-151.[7] G.E. Potter, M.S. Handcock, I.M. Longini, M.E. Halloran. Estimating within-school contact networks to understand
influenza transmission. The Annals of Applied Statistics, ): 1-26.[8] N. Eagle, A. Pentland. Realty mining: sensing complex social systems. Personal and Ubiquitous Computing, 2006,
10: 255-268.[9] G. Pickard, W. Pan, L. Rahwan, M. Cebrian, R. Crane, A. Madan, A. Pentalnd. Time-critical social mobilization.
Science, 55): 509-512.[10] D.O. Olguin, P.A. Gloor, A. Pentland. Capturing individual and group behavior with wearable sensor. In: AAAI Spring
Symposium on Human Behavior Modeling. Stanford, CA. March, .[11] E. Yoneki. FluPhone study: virtual disease spread using haggle. In: Proceedings of the ACM MobiCom Workshop
on Challenged Networks (CHANTS'11), September, 2011, Las Vegas, Nevada, USA, 1-2.[12] E. Yoneki, J. Crowcroft. EpiMap: Towards Quantifying Contact Networks and Modelling the Spread of Infections in
Developing Countries. Ad Hoc Networks, ): 83-93.[13] P. Hui, J. Crowcroft. Human mobility models and opportunistic communications system design. Philosophical
Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 72): 2005-
2016.[14] D. J. Watts, S. H. Strogatz. Collective dynamics of small world networks. Nature, 84): 440-442.[15] L. Isella, M. Romano, A. Barrat, C. Cattuto, V. Colizza. Close encounters in a pediatric ward: measuring face-to-
face proximity and mixing patterns with wearable sensors. PLoS One, ): e17144.[16] J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, L. Isella, J.F. Pinton, M. Quaggiotto, W. Van den Broeck, C. Régis, B.
Lina, P.Vanhems. High resolution measurements of face-to-face contact patterns in a primary school. PloS One,
): e23176.[17]
S. Meloni, N. Perra, A. Arenas, S. Gómez, Y. Moreno, A. Vespignani. Modeling human mobility responses to the
large-scale spreading of infectious diseases. Scientific Reports, 2011, 1, article 62: 1-7.[18] B. Wang, L. Cao, H. Suzuki, K. Aihara. Safety-information-driven human mobility patterns with metapopulation
epidemic dynamics. Scientific Reports, 2012, 2, article 887: 1-98.[19] A. Vespignani. Modelling dynamical processes in complex socio-technical systems. Nature Physics. 2012 Jan
1;8(1):32-39.[20] J. Mossong, N. Hens, M. Jit, P. Beutels, K. Auranen, R. Mikolajczyk, M. Massari, S. Salmaso,G. S. Tomba, J.
Wallinga et al. Social contacts and mixing patterns relevant to the spread of infectious diseases. PLoS Medicine,
): e74.[21] B. Yang, H. Pei, H. Chen, J. Liu, S. Xia. Characterizing and Discovering Spatiotemporal Social Contact
Patterns for Healthcare. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016 (DOI: 10.1109/
TPAMI.).[22] S. Eubank, H. Guclu, V. A. Kumar, M. V. Marathe, A. Srinivasan, Z. Toroczkai, N. Wang. Modelling disease
outbreaks in realistic urban social networks. Nature, 88): 180-184.
（下转第 23 页）
13中国人工智能学会通讯[2] N. Molinari, I. Ortega-Sanchez, M.L. Messonnier, W.W. Thompson, P.M. Wortley, E. Weintraub, C.B. Bridges. The
annual impact of seasonal influenza in the US: measuring disease burden and costs. Vaccine, ): 5086-
5096.[3] Center for Health Protection of Hong Kong. Flu express, ), 1-5. Published on Jan 29, 2015.[4] F. Iozzi, F. Trusiano, M. Chinazzi, F.C. Billari, E. Zagheni, S. Merler, M. Ajelli, E. Del Fava, P. Manfredi. Little Italy:
an agent-based approach to the estimation of contact patterns-fitting predicted matrices to serological data. PLoS
Computational Biology, ): e1001021.[5] 腾讯新闻网 : http://news.qq.com/zt/huizong.htm.[6] A. Melegaro, M. Jit, N. Gay, E. Zagheni, W.J. Edmunds. What types of contacts are important for the spread of
infections? Using contact survey data to explore european mixing patterns. Epidemics, ): 143-151.[7] G.E. Potter, M.S. Handcock, I.M. Longini, M.E. Halloran. Estimating within-school contact networks to understand
influenza transmission. The Annals of Applied Statistics, ): 1-26.[8] N. Eagle, A. Pentland. Realty mining: sensing complex social systems. Personal and Ubiquitous Computing, 2006,
10: 255-268.[9] G. Pickard, W. Pan, L. Rahwan, M. Cebrian, R. Crane, A. Madan, A. Pentalnd. Time-critical social mobilization.
Science, 55): 509-512.[10] D.O. Olguin, P.A. Gloor, A. Pentland. Capturing individual and group behavior with wearable sensor. In: AAAI Spring
Symposium on Human Behavior Modeling. Stanford, CA. March, .[11] E. Yoneki. FluPhone study: virtual disease spread using haggle. In: Proceedings of the ACM MobiCom Workshop
on Challenged Networks (CHANTS'11), September, 2011, Las Vegas, Nevada, USA, 1-2.[12] E. Yoneki, J. Crowcroft. EpiMap: Towards Quantifying Contact Networks and Modelling the Spread of Infections in
Developing Countries. Ad Hoc Networks, ): 83-93.[13] P. Hui, J. Crowcroft. Human mobility models and opportunistic communications system design. Philosophical
Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 72): 2005-
2016.[14] D. J. Watts, S. H. Strogatz. Collective dynamics of small world networks. Nature, 84): 440-442.[15] L. Isella, M. Romano, A. Barrat, C. Cattuto, V. Colizza. Close encounters in a pediatric ward: measuring face-to-
face proximity and mixing patterns with wearable sensors. PLoS One, ): e17144.[16] J. Stehlé, N. Voirin, A. Barrat, C. Cattuto, L. Isella, J.F. Pinton, M. Quaggiotto, W. Van den Broeck, C. Régis, B.
Lina, P.Vanhems. High resolution measurements of face-to-face contact patterns in a primary school. PloS One,
): e23176.[17]
S. Meloni, N. Perra, A. Arenas, S. Gómez, Y. Moreno, A. Vespignani. Modeling human mobility responses to the
large-scale spreading of infectious diseases. Scientific Reports, 2011, 1, article 62: 1-7.[18] B. Wang, L. Cao, H. Suzuki, K. Aihara. Safety-information-driven human mobility patterns with metapopulation
epidemic dynamics. Scientific Reports, 2012, 2, article 887: 1-98.[19] A. Vespignani. Modelling dynamical processes in complex socio-technical systems. Nature Physics. 2012 Jan
1;8(1):32-39.[20] J. Mossong, N. Hens, M. Jit, P. Beutels, K. Auranen, R. Mikolajczyk, M. Massari, S. Salmaso,G. S. Tomba, J.
Wallinga et al. Social contacts and mixing patterns relevant to the spread of infectious diseases. PLoS Medicine,
): e74.[21] B. Yang, H. Pei, H. Chen, J. Liu, S. Xia. Characterizing and Discovering Spatiotemporal Social Contact
Patterns for Healthcare. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016 (DOI: 10.1109/
TPAMI.).[22] S. Eubank, H. Guclu, V. A. Kumar, M. V. Marathe, A. Srinivasan, Z. Toroczkai, N. Wang. Modelling disease
outbreaks in realistic urban social networks. Nature, 88): 180-184.
（下转第 23 页）
13中国人工智能学会通讯时空众包工作流程
台。度量该应用服务质量的重要指标为用户的等待
时间，即从用户发布外卖派送任务至其拿到外卖的
时空众包工作流程如图 2 所示。时空众包用户
时间。为优化这一指标，既需要考虑外卖派送任务包括任务发起者和众包参与者，其通过时空众包平
出现的时空随机性和派送员的时空分布，又需要为台建立联系。发起者设置任务的时空约束后，即可
派送员规划取餐和送餐顺序。将任务发布至平台并等待平台反馈。参与者为完成任务，需要提交自己的时空信息以供平台判定其是
2. 实时交通监控应用否满足相关时空约束。根据不同应用特点，有些平
实时路况信息对人们的出行规划会有很大影台允许参与者浏览并自主选择任务，有些平台则直接为参与者分配任务。平台负责对所请求任务和参
响。近年来，许多移动导航类软件，如国内的高德与者信息进行综合处理。一般地，平台首先将任务
地图、百度地图和国外的 Waze[15] 等，已能够较为/ 参与者信息进行预处理，然后基于任务特点和优
精准地提供实时路况信息。其能够提供高质量实时化目标进行任务分配，并将相应信息反馈给发起者
路况信息的原因在于，当用户使用这些应用时，平和参与者。特别地，对于不同任务需求 , 平台可先
台可利用用户移动设备的 GPS 数据来获取有关路面对执行结果进行汇聚 , 再反馈给请求者。
交通流量的信息。此类场景在移动互联网研究中也
被称为“参与感知 (Participatory Sensing)”。具体时空众包平台
而言，这类移动导航类软件潜在地发布了一项获取
不同时段和路段车速的时空众包任务，而用户在使任务反馈
用这类软件进行导航时，被动地成为了众包参与者，
在享受导航服务的同时，也向应用提供了当前时段结
其所在路段的交通信息。通过对大量用户提供的实果 任务分配
时 GPS 数据进行分析和综合 [16]，该类应用即可较汇
为准确地获知各个路段的实时交通情况，从而为用聚
户提供更高质量的导航服务。
任务/工人信息预处理
3. 数据集成应用
数据集成是指将众多的异构数据源进行有效地发布任务
清洗、去冗、归并、匹配，且最终将融合后的数据设置时空约束
提交时空信息
形成统一视图的过程 [17]。时空众包可对时空数据进
行有效集成。典型的时空数据集成需求包括地图数任务发起者
众包参与者
据集成、城市兴趣点 (Point of Interest,POI) 标注 [18]
等。以地图数据集成的为例，传统的地图数据集成
图 2 时空众包工作流程
主要通过测绘等手段完成，数据构建和维护成本均
较高。Google 公司每年维护地图数据的花费高达 10代表性应用
亿美金。时空众包技术为地图数据集成提供了一种
新思路，通常称为众包地图 (Crowdsourced Map)。
下面介绍时空众包的三类代表性应用，即实时
开 放 街 道 地 图 (Open Street Map，OSM)[19] 是 众 包O2O 应用、实时交通监控应用和数据集成应用。
地图应用的典型代表，可将其视为地图版的维基百
科。OSM 通过招募志愿者 ( 众包参与者 ) 对地图进1. 实时 O2O 应用
行编辑、标注，实现对地图数据的集成。在该应用
O2O 商业模式借助移动互联网通过线上招募的
中，平台同时也是时空众包任务发起者，任务为构
建地图。志愿者们提供和维护世界各地关于道路、方式来整合调度线下空闲资源，以达到线下空闲资
小道、咖啡馆、铁路车站等各种各样的数据，并使源的高效共享，是共享经济时代典型的互联网 + 商
用航空图像、GPS 设备与传统的地区地图等来确保业模式之一。当前具有代表性的 O2O 应用包括实时
OSM 的精确性和时效性。截止至 2013 年，OSM 已专车类的滴滴出行 [10]、神州专车 [11] 与 Uber[12] 等，以及物流派送类的百度外卖 [13] 与 Gigwalk[14] 等。以百度外卖为例，该应用支持用户随时随地发布外卖派送任务。随后，平台分配某位外卖派送员执行该任务，为用户前往指定地点取餐并送至用户手中。可以将外卖派送任务视为时空众包任务，外卖派送员则为众包参与者，百度外卖 APP 即是时空众包平
15中国人工智能学会通讯经拥有超过 100 万注册用户，并收集了 2 100 万英
该模型的研究一直认为贪心算法求解此问题会产生里以上的道路数据和超过 7 800 万条建筑物数据。
极差的效果。然而，若采用平均情况分析，可发现
最差情况分析理论下的最差实例在平均情况分析下核心研究问题与研究现状
的竞争比仅为 3.195。实验也显示出贪心算法实际
求解该模型具有很好的效果。
下面介绍时空众包领域的 4 个核心研究问题及其研究现状。1. 任务分配
(a) t1 抵达时匹配结果 (b) w2 抵达时匹配结果
任务分配指时空众包平台根据任务和参与者的
时空属性和其他相关信息，为每个任务分配适当的众包参与者。现存研究根据不同应用场景下任务分配的具体需求，通常采用二分图匹配模型和任务规划模型这两种算法模型对该问题进行建模。
（1）基于匹配的分配模型
(c) w3 抵达时匹配结果 (d) t
抵达时匹配结果
在每次为众包参与者分配一项任务的应用场景
图 3 在线双边加权二分图匹配模型下，如滴滴出行等专车类服务，可使用基于匹配的分配模型。具体而言，该模型将任务分配问题规约
（2）基于规划的分配模型为最大化或最小化加权二分图匹配问题 [20]。根据
当众包参与者在给定时间内要求执行多项众包任务实时性要求的差异，该模型又可分为静态离
任务时，可使用基于规划的分配模型。该模型适用线场景和动态在线场景的匹配模型。在静态离线
于百度外卖等物流派送类服务，其中平台需为众包场景下，将任务和参与者建模为二分图两个不相
参与者规划任务执行的路径。现存基于规划的任务交的顶点集合，并基于时空约束和应用特点构造
分配模型也可根据任务的实时性要求不同分为静态加权二分图。时空众包任务分配的早期研究大都
离线场景与动态在线场景的规划模型。静态离线场采用此模型 [21-23]。 然而，现实应用中平台通常难
景下的任务规划问题通常被规约为经典的旅行商问以提前获知众包任务和参与者的时空信息，研究者
题或者定向问题 (Orienteering Problem)，而在动态转而采用动态在线匹配模型进行建模。在动态在线
在线场景下，每当有新任务在众包平台发布时，平场景下，每当任务或参与者出现在平台时，由于无
台需为每位参与者实时地决定是否将此项新任务加法获知后续参与者和任务的时空信息，匹配决策仅
入到其当前的任务规划之中 [28]。可根据当前已知信息进行。换言之，需仅根据部分二分图信息来进行匹配决策 [24-27]。文献 [24] 首次提
2. 质量控制出了在线双边加权二分图匹配模型来建模该问题，该模型允许任务与参与者以任意顺序动态地出现在
质量控制问题在传统众包中被广泛研究 [29-30]，二维空间中的任意位置。求解此类任务分配问题的
并在时空众包领域面临新的挑战。一方面，与传统算法被称为在线算法，其算法性能既受制于二分图
众包中的质量控制相似，一些时空众包任务由多位结构，又特别依赖于二分图顶点的出现顺序。如图
众包参与者重复完成时，则可通过对不同参与者的3 所示 , 图 3(d) 显示了完整的离线二分图结构。然而，
反馈进行汇聚来控制最终结果的质量。但在时空众由于任务和参与者动态出现，仅根据局部二分图信
包中，参与者通常受到空间服务范围的限制，因此息进行任务分配决策。假设给定任务和参与者的抵
在结果汇聚过程中还需考虑空间信息对结果汇聚质达顺序为〈w1, t1, t2, w2, t3, w3, t4, w4, t5〉，且采用简
量的影响。另一方面，许多时空众包任务实时性要单的在线贪心算法（其指每次决策仅选择当前未分
求较高，而参与者移动到任务所在位置的时间消耗配边中权值最大的边），部分任务和参与者抵达时
对任务的完成质量或任务发起者的满意度都有较大的算法分配情况，如图 3(a)~(c) 所示。此外，文献 [25]
影响。因此，这种由移动时间引起的延迟也是时空提出了动态在线最小化二分图权值和匹配模型，并
众包质量控制面临的新挑战。下面分别介绍针对上发现了一项有悖于该模型过去 25 年研究的新结论。16中国人工智能学会通讯述两类问题的时空众包质量控制方法。
针对不用时空众包应用场景，研究人员还提出了在
线拍卖、多属性拍卖、组合拍卖、全付拍卖、双向
（1）基于结果汇聚的质量控制
拍卖、VCG 拍卖等拍卖模型 [34]。
该类研究旨在对不同众包参与者的反馈进行有效汇聚，汇聚结果通常受两类因素影响：参与者的
（2）基于多臂赌博机的激励机制可靠性和结果汇聚机制。传统众包研究已广泛涉及
多 臂 赌 博 机 (Multi-armed Bandit) 模 型 [35] 是如何估计参与者的可靠性 [31-32]，而在时空众包环境
在 线 学 习 (Online Learning) 研 究 领 域 中 的 一 个 重下，如何将空间信息有效集成至众包结果汇聚机制
要模型。该模型假设存在一个多臂赌博机 , 每摇其中是当前研究的重点。具体而言，对于每个众包任
中一个臂 , 就可根据该臂相关的某概率分布获得务给定一组众包参与者，根据参与者历史表现评估
收 益。 该 模 型 的 一 个 变 种 为 上 下 文 的 多 臂 赌 博 机其完成任务的可靠性，研究的核心问题通常为使得
(Contextual Multi-armed Bandit)，其摇臂收益所依至少一位或超过半数参与者正确完成该任务的概率
从的概率分布和某上下文信息 X 以及某一未知参数超过某一阈值 [22]。
θ 有关。使用该模型对众包任务进行定价，上下文
信息 X 包含众包参与者和任务的时空属性以及价格
（2） 基于时空约束的质量控制
信息，将参与者对任务的接受率视为摇臂收益，则
实时性时空众包应用通常将完成任务所需的
可通过学习未知参数并根据 θ 对任务进行定价。时间开销视为其质量控制的关键指标。如在实时专车服务平台如滴滴出行中，当司机 ( 众包参与
4. 隐私保护者 ) 接单后，其接到乘客的时间花费将直接影响该乘客的用户体验。文献 [25] 提出动态在线最小
隐私保护问题是时空众包面临的新挑战。传统化二分图权值和匹配模型来解决上述问题。在该模
众包中，由于任务发起者和众包参与者无需提供其型下，众包任务随机发布在平台，平台需立即决定
在真实物理世界中的个人信息，隐私保护并未被特将此任务分配给某位当前在线的众包参与者或令该
别研究。而在时空众包中，众包任务发起者和参与任务等待后续出现的参与者。为优化众包参与者抵
者均需提供其在真实物理世界中的时空信息，一旦达众包任务位置的时间，每项众包任务与其匹配参
时空众包平台遭受攻击，他们的个人隐私信息将面与者间的时空距离成为此类时空众包任务质量控制
临泄漏的风险。因此，针对上述挑战有必要设计合的最终目标。
理的隐私保护策略。另一方面，任务发起者与参与
者的时空信息也是任务分配和质量控制所需考虑的3. 激励机制
因素，因此需在保护隐私的同时又不对任务分配和
对于一项指定的时空众包任务，众包平台应能
质量控制产生较大影响。目前，时空众包隐私保护
的研究主要基于以下两种模型。够有效激励足够多的众包参与者完成此任务，这类研究被称为激励机制研究。时空众包应用中的激励
（1）基于差分隐私的保护模型方式以金钱激励为主，因此激励机制设计问题又可
在差分隐私保护模型下 [36]，众包参与者首先将视为定价问题，即为某一时空众包任务设定合理价
自身的位置信息提交至可信任的移动服务商，移动格。激励机制的相关研究，主要包括基于拍卖的激
服务商基于差分隐私保护的相关技术将位置信息转励机制和基于多臂赌博机 (Multi-armed Bandit) 的激
化为索引点。时空众包平台根据索引点信息，可将励机制。
任务分配给附近合适的众包参与者。
（1）基于拍卖理论的激励机制
（2）基于隐蔽位置的保护模型
拍卖理论 [33] 是博弈论的分支，研究拍卖的性
在基于隐蔽位置的隐私保护模型下 [37]，众包参质和拍卖活动中人的行为。在拍卖过程中，卖家和
与者的位置信息是隐蔽的。具体而言，平台仅能获买家对商品价格进行协商，并最终达成共识。在传
知众包参与者所在的区域，以及其存在于此区域任统的拍卖中，竞标者通过出价竞争购买某一商品，
一点的概率密度函数，而无法获知精确位置。基于价高者得。而在时空众包激励机制的研究中，反向
该模型，可对所有众包参与者移动至所分配时空众拍卖模型更受青睐。在反向拍卖中，竞标者通过开
包任务的距离加和进行优化。此外，还可允许参与价竞争执行某项任务，价低者得。基于反向拍卖并
者用自己的精确位置对匹配结果进行调整，以减轻
位置的不确定性对匹配的影响。
17中国人工智能学会通讯述两类问题的时空众包质量控制方法。
针对不用时空众包应用场景，研究人员还提出了在
线拍卖、多属性拍卖、组合拍卖、全付拍卖、双向
（1）基于结果汇聚的质量控制
拍卖、VCG 拍卖等拍卖模型 [34]。
该类研究旨在对不同众包参与者的反馈进行有效汇聚，汇聚结果通常受两类因素影响：参与者的
（2）基于多臂赌博机的激励机制可靠性和结果汇聚机制。传统众包研究已广泛涉及
多 臂 赌 博 机 (Multi-armed Bandit) 模 型 [35] 是如何估计参与者的可靠性 [31-32]，而在时空众包环境
在 线 学 习 (Online Learning) 研 究 领 域 中 的 一 个 重下，如何将空间信息有效集成至众包结果汇聚机制
要模型。该模型假设存在一个多臂赌博机 , 每摇其中是当前研究的重点。具体而言，对于每个众包任
中一个臂 , 就可根据该臂相关的某概率分布获得务给定一组众包参与者，根据参与者历史表现评估
收 益。 该 模 型 的 一 个 变 种 为 上 下 文 的 多 臂 赌 博 机其完成任务的可靠性，研究的核心问题通常为使得
(Contextual Multi-armed Bandit)，其摇臂收益所依至少一位或超过半数参与者正确完成该任务的概率
从的概率分布和某上下文信息 X 以及某一未知参数超过某一阈值 [22]。
θ 有关。使用该模型对众包任务进行定价，上下文
信息 X 包含众包参与者和任务的时空属性以及价格
（2） 基于时空约束的质量控制
信息，将参与者对任务的接受率视为摇臂收益，则
实时性时空众包应用通常将完成任务所需的
可通过学习未知参数并根据 θ 对任务进行定价。时间开销视为其质量控制的关键指标。如在实时专车服务平台如滴滴出行中，当司机 ( 众包参与
4. 隐私保护者 ) 接单后，其接到乘客的时间花费将直接影响该乘客的用户体验。文献 [25] 提出动态在线最小
隐私保护问题是时空众包面临的新挑战。传统化二分图权值和匹配模型来解决上述问题。在该模
众包中，由于任务发起者和众包参与者无需提供其型下，众包任务随机发布在平台，平台需立即决定
在真实物理世界中的个人信息，隐私保护并未被特将此任务分配给某位当前在线的众包参与者或令该
别研究。而在时空众包中，众包任务发起者和参与任务等待后续出现的参与者。为优化众包参与者抵
者均需提供其在真实物理世界中的时空信息，一旦达众包任务位置的时间，每项众包任务与其匹配参
时空众包平台遭受攻击，他们的个人隐私信息将面与者间的时空距离成为此类时空众包任务质量控制
临泄漏的风险。因此，针对上述挑战有必要设计合的最终目标。
理的隐私保护策略。另一方面，任务发起者与参与
者的时空信息也是任务分配和质量控制所需考虑的3. 激励机制
因素，因此需在保护隐私的同时又不对任务分配和
对于一项指定的时空众包任务，众包平台应能
质量控制产生较大影响。目前，时空众包隐私保护
的研究主要基于以下两种模型。够有效激励足够多的众包参与者完成此任务，这类研究被称为激励机制研究。时空众包应用中的激励
（1）基于差分隐私的保护模型方式以金钱激励为主，因此激励机制设计问题又可
在差分隐私保护模型下 [36]，众包参与者首先将视为定价问题，即为某一时空众包任务设定合理价
自身的位置信息提交至可信任的移动服务商，移动格。激励机制的相关研究，主要包括基于拍卖的激
服务商基于差分隐私保护的相关技术将位置信息转励机制和基于多臂赌博机 (Multi-armed Bandit) 的激
化为索引点。时空众包平台根据索引点信息，可将励机制。
任务分配给附近合适的众包参与者。
（1）基于拍卖理论的激励机制
（2）基于隐蔽位置的保护模型
拍卖理论 [33] 是博弈论的分支，研究拍卖的性
在基于隐蔽位置的隐私保护模型下 [37]，众包参质和拍卖活动中人的行为。在拍卖过程中，卖家和
与者的位置信息是隐蔽的。具体而言，平台仅能获买家对商品价格进行协商，并最终达成共识。在传
知众包参与者所在的区域，以及其存在于此区域任统的拍卖中，竞标者通过出价竞争购买某一商品，
一点的概率密度函数，而无法获知精确位置。基于价高者得。而在时空众包激励机制的研究中，反向
该模型，可对所有众包参与者移动至所分配时空众拍卖模型更受青睐。在反向拍卖中，竞标者通过开
包任务的距离加和进行优化。此外，还可允许参与价竞争执行某项任务，价低者得。基于反向拍卖并
者用自己的精确位置对匹配结果进行调整，以减轻
位置的不确定性对匹配的影响。
17中国人工智能学会通讯
Mathematics, 2009.[21] Kazemi L, Shahabi C. Geocrowd: Enabling query answering with spatial crowdsourcing. In: Proc. of the
SIGSPATIAL 2012 Int’l Conf. on Advances in Geographic Information Systems. 8.[22] Kazemi L, Shahabi C, Chen L. GeoTruCrowd: Trustworthy query answering with spatial crowdsourcing. In: Proc. of
the SIGSPATIAL 2013 Int’l Conf. on Advances in Geographic Information Systems. 3.[23] To H, Shahabi C, Kazemi L. A server-assigned spatial crowdsourcing framework. ACM Trans. on Spatial Algorithms
and Systems, ):2.[24] Tong Y, She J, Ding B, et al. Online mobile micro-task allocation in spatial crowdsourcing. In: Proc. of the 32nd Int’l
Conf. on Data Engineering. .[25] Tong Y, She J, Ding B, et al. Online minimum matching in real-time spatial data: Experiments and analysis. Proc. of
the VLDB Endowment, ):.[26] Ho C J, Vaughan J W. Online task assignment in crowdsourcing markets. In: Proc. of the 26th AAAI Conf. on
Artificial Intelligence. .[27] Karger D R, Oh S, Shah D. Budget-Optimal task allocation for reliable crowdsourcing systems. Operations
Research, ): 1-24.[28] Li Y, Yiu M L, Xu W. Oriented online route recommendation for spatial crowdsourcing task workers. In: Proc. of the
14th Int’l Conf. on Advances in Spatial and Temporal Databases. 6.[29] Li G, Wang J, Zheng Y, et al. Crowdsourced data management: A survey. ACM Trans. on Knowledge and Data
Engineering, ):.[30] 冯剑红 , 李国良 , 冯建华 . 众包技术研究综述 . 计算机学报 ,3-1726.[31] Whitehill J, Wu T, Bergsma J, et al. Whose vote should count more: Optimal integration of labels from labelers of
unknown expertise. In: Proc. of the 23rd Annual Conf. on Neural Information Processing Systems. -2043.[32] Sheng V S, Provost F, Ipeirotis P G. Get another label? Improving data quality and data mining using multiple, noisy
labelers. In: Proc. of the 14th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. 2.[33] Krishna V. Auction theory. Academic press, 2009.[34] Zhang X, Yang Z, Sun W, et al. Incentives for Mobile Crowd Sensing: A Survey. IEEE Communications Surveys &
Tutorials, ):54-67.[35] Gittins J, Glazebrook K, Weber R. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.[36] To H, Ghinita G, Shahabi C. A framework for protecting worker location privacy in spatial crowdsourcing. In: Proc. of
the VLDB Endowment, ):919-930.[37] Pournajaf L, Xiong L, Sunderam V, et al. Spatial task assignment for crowd sensing with cloaked locations. In: Proc.
of the 15th Int’l Conf. on Pervasive Computing and Communications. .[38] Tong Y, She J, Meng R. Bottleneck-Aware arrangement over event-based social networks: The max-min approach.
World Wide Web Journal, ):.[39] Tong Y, Cao C C, Chen L. TCS: Efficient topic discovery over crowd-oriented service data. In: Proc. of the 20th
ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. 0.童咏昕
宋天舒博士，北京航空航天大学计算机学
北京航空航天大学计算机学院硕士研院副教授。工作于北航软件开发环
究生。主要研究方向为群智计算（又境 国 家 重 点 实 验 室。 主 要 研 究 方 向
称众包计算）、时空数据管理与挖掘等。为 群 智 计 算（ 又 称 众 包 计 算）、 时空数据管理、数据区块链、社交网
吕卫峰络分析与不确定数据处理等。
博士，北京航空航天大学计算机学院许可
院长，教授。软件开发环境国家重点
实验室副主任，国家科技资源共享与博士，北京航空航天大学计算机学
服务工程中心主任，国家智慧城市标院教授。工作于北航软件开发环境
准总体组组长。主要研究方向为海量国家重点实验室。主要研究方向为
信息系统、数据挖掘与人工智能。算法、数据挖掘和网络等。
19中国人工智能学会通讯 科技前沿
基于众包的数据提纯
胡卉芪 / 华东师范大学1简介
有一个任务分配模块会为每个工人分配一定数量的
任务，然后通过众包平台收集工人的答案，并交由
随着基于位置服务的蓬勃发展 , 随之出现了大
一个推断模型来得到包括工人质量在内的中间信量相关的空间文本数据。空间文本数据包括两方面
息。这些中间信息会进一步指导分配模块对下一波信息，一个空间位置信息 , 通常与一个空间兴趣点
请求任务的工人进行任务分配。这个分配 - 推断的相关，由一个经纬度坐标点表示数据所处的地理位
过程一直重复进行，直到预算全部花费完毕。这时置；一个文本信息，通常是由一组关键词构成的类
由推断模型根据所有收集到的工人答案，推断出每似标签的文本描述。目前，这些关键词标签的生成
个数据关键词是否正确合理。下面介绍并解决这一方式主要通过人工添加与机器算法自动生成，由于
过程中需要处理的问题。来源广泛，这些生成的关键词质量参差不齐，很多质量难以保证。这些错误的数据在实际应用中将带
(a) (b)给用户非常糟糕的体验，甚至误导用户，造成损失。比如当前很多基于位置的服务通过关键词标签为用
图 1 基于众包的空间文本数据提纯户提供兴趣点推荐服务，若兴趣点的标签是错误的，那会给用户带来极大的困扰。由此很多产生的空间
2 问题描述文本数据很难在实际中使用。为有效缓解这一问题，本文研究基于众包的空间文本数据提纯问题，通过
基 于 众 包 的 空 间 文 本 数 据 提 纯 任 务： 给 出 需众包方法优化收集到空间文本数据的关键词，排除
要质量优化的一个空间文本数据集合 T={t1, t2,…,其中错误不合理的关键词。
t|T|}，众包平台将这些数据发布作为任务，一个任务
对应一个空间文本数据。每个任务 t={Ot, Lt} 由一
众包是这几年兴起的通过人力智慧解决问题的
个拥有地理位置的空间兴趣点 Ot 和一个文本描述关可靠途径。 很多计算机难以有效解决的问题，如复
键词集合 Lt={lt,1, lt,2,…, lt