雪莉?陈哲（Shirley Zhe Chen）、迈克尔.J?卡法雷拉（Michael J. Cafarella）和艾唐?艾达尔（Eytan Adar）
密歇根大学
统计图表，或称之为数据驱动图表，是传递复杂信息的重要方法。对于很多技术性文档，图表可能是读者获取支持该文档结论的原始数据的唯一途径。
不幸的是，利用目前的检索系统搜索在线图表是非常困难的。基于文本的标准检索仅能检索到图表的附加文档。Web图像搜索引擎可能检索到一些图表，但是这通常是通过检查图像周围的文本内容实现的，因此会丢失很多图表内容的重要目的（Bhatia等人，2010年；Carberry等人，2006年）。即使图表中出现的文本的意义与其在图表结构中的几何位置密切相关，标题中数字的意义与x轴刻度上相同数字的意义可能也有很大的不同（贝尔丁，1983年）。
在利用SpringerImages（http://www.springerimages.com/）和Zanran（http://www.zanran.com/q/）这类数据搜索系统使数据驱动的图表更容易理解方面，有着不断增长的商业利益。虽然关于搜索和图像相关的主题的研究文献已经有很多了，但是对图表搜索自身的研究还几乎是空白。
在本文中，我们提出了一种专用于数据驱动图表的Web搜索引擎。和其它Web搜索引擎一样，我们的系统允许用户在文本框中输入关键词来获取目标的相关性排名列表。我们的系统解决了在其它搜索引擎中常见的多个问题，但是需要为数据驱动图表特别定制的解决方案。
图表语料库提取
获取一个Web文档中的文本通常像下载和解析一个HTML文件一样简单，但是与之相反，统计图表需要特殊的处理以提取有用的信息。它们嵌入在PDF文件中，难以将其与周围的文本区分开，嵌入在图表中的文本的风格是与其意义高度相关的，对于文本的确切作用非常敏感，而且，因为图表经常是高度工程化的文档的一个主要部分，它们可能在周围文本中有大量的数字引用形式的“隐含链接”。我们的图表提取器组件试图获取图表的所有相关文档，并且为每个字符串确定一个适当的语义标签（标题、y轴标签，等等）。
排名质量
所有的搜索引擎必须说明何如计算一个目标与搜索查询的相关性，但是计算图表的相关性可能会得出奇怪和意外的结果。我们使用从以前的步骤中提取的元数据来获得搜索质量，要比初级方法有明显的提高。
生成摘要
搜索到的内容的短小的总结，通常称之为摘要，允许用户在实际上选择内容查看之前，可以快速地浏览大量的搜索结果。传统的搜索引擎从原始文档中选取部分文本区域，而图形搜索引擎通常将原始图形缩小为较小的缩略图。这些方法都不能直接地应用于数据驱动的图表。显然，文本方法不能捕获到任何可视的元素。图1显示出图像缩放也是无效的：尽管照片和图像在较小尺寸上仍然是清晰的，但是图表很快变得难以理解。
本文介绍了用于搜索Web文档中数据驱动图表的一种搜索引擎DiagramFlyer。它解决了上述所有问题，实现了一种可以成功提取图表元数据来提供更高质量的排名和用于快速浏览结果的改进的图表“摘要”的搜索引擎。
我们提出的方法是通用的，可以用于在整个Web上发现的所有图表。但是，在我们目前的实验平台上，我们关注于从公共Web页面上发现和下载的关于互联网学术领域的PDF文件中提取的图表。我们生成的语料库包含了153,000个PDF文件和319,000个图表。我们发现DiagramFlyer和初级方法相比，在搜索质量上提高了52%。而且，我们发现DiagramFlyer的混合摘要产生器使用户得到的搜索结果要比标准的图像驱动摘要的准确率高出33%。我们还将DiagramFlyer的智能能力用于越来越多的域独立信息提取工作中—这种工作实现了从非结构化的文档中检索结构化的数据项，即使是主题（或者域）的数量无限时。
U.S. Population 1900-2100美国人口 1900-2100年
图1 为图片生成可视摘要时缩小图像方法效果良好，但是图表会很快变得难以辨认。
Web Pages页面 offline离线 online在线 diagram extractor图表提取器 metadata原数据 index builder索引生成器 search ranker搜索排名器 snippet generator摘要生成器 search interface搜索界面 query查询
图2 数据处理管道。一个离线爬虫组件在Web上收集PDF文件，提取统计图片，并且为得到的提取元数据构建一个倒转的文本索引。然后将这个索引和图表输入到在线系统中，这个系统根据用户的查询对图表进行排名，并且生成与查询相适应的搜索摘要。深蓝色方框表示本文介绍的搜索组件。
系统概述
与传统的Web搜索引擎一样，DiagramFlyer采用了一个离线语料库处理管道，其输出再用于在线的查询系统。该系统的架构如图2所示。
离线管道有三个组件：
1. PDF爬虫下载大量的Web托管的科技文献用于图表搜索。
2. 图表提取器接收得到的大约有153,000篇文章的数据流。提取器试图确定语料库中的所有图表，并且以适当的语义角色在每个图表中注释文本。如图3所示，图表提取器在图表中确定了八个角色（图例、说明、标题，等等）。它还会查找提及该图表的所有周围文本，将相关语句标记为“上下文”。对于测试平台系统，我们使用了二维数据驱动的划分图（包括散布图、时间序列以及条形图）。
Axis轴 scale刻度 title标题 caption说明 legend图例 context上下文
图3 用于简单图表的图表元数据标签。像标题和图例这样的标签对于不同的图形有不同的放置位置。
3. 索引生成器对提取和注释过的图表建立一个搜索索引。索引分别追踪每一个提取的字段，使得匹配图表各个部分的关键词可以在排名时进行不同的加权。
如图4所示，DiagramFlyer的在线搜索系统看起来和传统的Web搜索引擎类似。响应在线查询需要两个额外的组件：
1. 搜索排名器在其索引中评估每个图表的相关性。和标准的搜索排名器相比，我们的系统的主要优势是其能够使用图标提取器生成的文本特性。
2. 最后，摘要生成器为每个搜索点击生成一个简短的小结，根据搜索排名器进行排序。DiagramFlyer的摘要生成器产生同时包含图形和文本元素的特定图表的专用摘要。
算法
如上所述，我们的系统采用了三个创新的组件。因为空间有限，本文在此仅讨论图表提取器组件。
图表提取器使用一个PDF提取器从文档中获取所有的文本字符串。然后它采用分四个阶段的处理流程来获取与实时的数据驱动图表相对应标记文本字符串组：
1. 一个经过训练的基于文本的分类器严格地根据文本特性给字符串赋予一个初始标签，例如字符串的词汇数量、字符串是否是大写的、词性的分布，等等。
2. 然后我们将标记过的字符串共同分组为几何上相邻的、与图表松散对应的集合。抛弃没有重要标签的集合，例如相关的x和y轴数据。这就过滤掉了大量的与任何图表都不相关的字符串。
3. 然后我们为每个字符串重新计算标签，利用初始标签来计算一系列的位置敏感的特性。例如，一个重要的特性是一个文本字符串到最近的x轴刻度的距离。这一轮分类显著地提高了标签的查准率和查全率。
4. 最后，我们将得到的已经标记的字符串分组为表示最终图表估计值的集合。这个步骤高度依赖于上面应用的语义标签，例如，说明字符串应当始终在图表中靠下的区域。
图4 DiagramFlyer搜索系统的一副屏幕截图。
此输出馈送给搜索排名器和摘要生成器组件。
实验结果
图表提取器是一个与查询无关的组件，所以可以利用我们下载的科技论文进行严格的评估。我们从取自ClueWeb09数据集（http：//lemurproject.org/clueweb09.php/）的英语部分的47亿个链接开始。这些链接中，我们保留了那些指向PDF文档的链接。为了定位很可能包含图表的PDF文件，我们进一步将查找范围限制在.edu域名内。查询的工作量对于评估我们的搜索排名器和摘要生成器组件非常关键，但是我们在本文有限的篇幅内不讨论它们。
为了确定图表提取器的最佳实现，我们评估了三种略有不同的版本：
● 只有文本版：只是简单的文本分类器。
● 所有分类器版：文本分类器和位置敏感分类器，无过滤。
● 完全版：所有步骤。
我们使用从PDF语料库随机选取的超过260个数据驱动的图表得到的所有的文本段训练这些分类器；人工对文本段进行标记。我们使用180个类似方法产生和标记的图表对结果进行测试。评估结果如下表所示（每种任务的最好成绩以黑体字显示）。
|
|
查全率 |
|
|
查准率 |
|
|
|
|
只有文本 |
所有 |
完全 |
只有文本 |
所有 |
完全 |
|
标题 |
0.256 |
0.651 |
0.674 |
0.344 |
0.609 |
0.617 |
|
y-刻度 |
0.782 |
0.796 |
0.754 |
0.889 |
0.843 |
0.900 |
|
y-标签 |
0.835 |
0.864 |
0.874 |
0.775 |
0.752 |
0.797 |
|
x-刻度 |
0.903 |
0.835 |
0.835 |
0.616 |
0.915 |
0.896 |
|
x-标签 |
0.241 |
0.681 |
0.681 |
0.340 |
0.842 |
0.835 |
|
图例 |
0.520 |
0.623 |
0.656 |
0.349 |
0.615 |
0.631 |
|
说明 |
0.952 |
0.887 |
0.839 |
0.450 |
0.887 |
0.929 |
|
非图表 |
0.768 |
0.924 |
0.313 |
0.850 |
0.909 |
0.838 |
完全版的精度高于所有分类器版是由于图表组过滤器。对于一个有449个候选图表组的集合，这个过滤器去除了165个差组，仅去除了11个良好组。对于大部分标签，这个过滤器对查全率的影响不大。但是，在完全版的例子中，它显著地降低了非图表文本的查全率，从0.9239到了0.3126。在非图表的情况下，查全率的降低实际上是一个好的信号：大部分“差候选图表”是绘画式的，或是非数据驱动的，对于下游搜索引擎是没有意义的。降低这种标签的查全率意味着对任何图表都不必要的字符串被从输出和可能的下游图表检测中去除。尽管所有分类器版具有可比较的总体性能，但是我们在DiagramFlyer中选择完全版来强调查准率而不是查全率。
显然，标题和图例是最难以分类的元数据项。由于某些原因，结果并不令人意外：标题不是总有，而图例也可能出现在几个不同的位置。最后，我们还将评估我们进行图表重组的方法。我们成功地重新建立了119个图表中的89个，仅有20个重建不正确。这些不正确的输出是由于分割了一个单一的图表，或者合并了两个不同的图表。
相关工作
在文本搜索、摘要生成、图像搜索以及图像处理方面有着大量的学术研究；其中很多都与不常用的统计图表搜索需求无关。在专业的图表理解方面已经有了一些研究，例如处理电话系统的图表（Arias等人，1995年），但是这些研究工作都严格局限于有限的图表类型，不适用于通用的搜索应用。
只有少量的著作以适用于Web风格搜索的方式处理图表。黄等人（2003年）提出了一种自动机制来从图表的图形部分恢复实际的数值量；它可以大规模使用。黄等人（2005年）试图标记图表文本区域，类似于图表提取阶段，但是标签较少，准确率也有些低，而且他们的方法能否处理多图表图形也不清楚。最相关的工作是卡塔里亚（Kataria）等人（2008年）和卢（Lu）等人（2009年）所做的工作。他们从嵌入文件中的图表提取信息，恢复文本标签和图形元素；他们的文本恢复组件关注于恢复OCR（光学字符识别）文本，一定数量的标签恢复只是这种方法方法的副产品。他们的系统使用了一些与DiagramFlyer的图表提取器相同的特性，但是还不清楚他们的方法可以在多大程度上扩展来产生更细粒的标签，而且他们也不关注提取阶段的任何任务。
结论
我们已经说明了域无关的图表提取是可能的。在全面介绍中我们也证明了这个系统和使用标准方法相比能够实现更高质量的搜索相关性和摘要生成。
原件下载：  |
