基于逆向匹配的电子商务网站实体模板半自动构建方法

傅 彦，徐昭邦，夏虎，周俊临

(电子科技大学 计算机科学与工程学院 互联网科学中心，四川 成都 611731)



基于逆向匹配的电子商务网站实体模板半自动构建方法

傅 彦，徐昭邦，夏虎，周俊临

(电子科技大学 计算机科学与工程学院 互联网科学中心，四川 成都 611731)

Web页面中的主题信息一般分布比较集中，可利用网页的这一特性进行网页主题信息的自动提取。网页源代码中的HTML标签不规范，使得正向匹配难以生成嵌套结构准确的DOM树，该文提出一种通过逆向匹配的方法，构建完整的网页源代码DOM树。通过对DOM树进行剪枝，删除无关节点，对保留下来的信息块的节点标签进行人工选择与唯一性判定，从而生成提取模板。该方法能够实现对电子商务网站源网页中的主题信息进行提取，是一种半自动、通用的方法，可用于信息检索系统中的信息采集。

逆向匹配；DOM树；模板构建；信息提取

1 引言

随着网络技术和数据库技术的飞速发展，网络上的信息量越来越大，越来越多的人选择从网上获取自己需要的信息，其中也包括网上购物。电子商务网站上包含了大量信息，用户可以通过这些网页获取商品的主题、参数等信息，但其中的商品网页大多属于深层网络[1]，不便于被传统的搜索引擎检索。

电子商务网站的实体模板是用于提取目标网页中的商品主题和参数等信息的提取框架。通过逆向匹配构建商品源网页的DOM树，再对同一电子商务网站的多个商品网页的DOM树进行比较，删除其中的网页模板信息，然后通过人工选择所需提取的部分并进行唯一性判定，从而构建实体提取模板。实验表明，该方法可以准确的提取出所需要的信息，并且在同一网站具有通用性。通过构建多个电子商务网站的实体提取模板，进而对其中的大量商品网页的信息进行批量提取，生成购物搜索系统，用户通过查询，可以非常方便地获取所需查询商品的主题和参数信息。并且可以对多个电子商务网站的同一商品进行比较，优化购物环境。

2 相关研究

在电子商务信息网站信息提取领域，已经有了大量的研究工作，但大部分是通过构建静态抽取规则(静态模板)[2]或者通过分析源代码获得目标信息的路径[3]进行规则提取，而自动与半自动的构建方法也通常只适合新闻网页，对于电子商务网站的提取结果准确率较低，这是因为新闻网页基本都含有大量文字内容信息，易于与旁边的广告、推荐等无关信息区分开来，而电子商务网站的信息则分布较乱，并且不同的电子商务网站对于商品主题、参数等信息的组织不尽相同，难于将目标信息与旁边的无关信息区分开来。

周炘[2]等人通过分析网页源代码，制定了针对特定电子商务网站的静态提取模板。侯明燕[3]等人提出了基于网页信息定位的数据抽取技术，首先构建源网页的DOM树，然后经过分析找到目标信息所在的位置和路径信息，通过从根节点到目标信息节点的路径提取出目标信息。这两种方法能够得到较高的准确率，但缺乏通用性，并且当网页改版时，静态提取模板和路径信息都有可能会失效。

王琦[4]等人提出了STU-DOM树模型，对源网页构建具有语义信息的DOM树，在STU-DOM树中，每个具有语义属性的节点，即STU节点，都具有两个语义属性： 块内链接数和非链接文字数，通过比较两个语义属性的值进行判定局部相关度和上下文相关度，但这种方法只能对新闻、财经、e国等文字信息比较集中的网页进行提取，对于京东商城，亚马逊商城等结构复杂的电子商务网站没有较好的提取效果。

通过分析各个电子商务网站多个网页的源代码，发现在同一个网站中，绝大部分网页的源代码是由相同模板生成的，而每个网页的模板信息是相同且与特定商品的主题与参数等信息不相关，相对于本文要提取的目标信息属于无关信息，应该删除。本文提出了一种半自动构建电子商务网站提取模板的方法，通过比较同一电子商务网站的多个源网页的DOM树，删除其中相同的部分，再对每个子树中的链接数与非链接文字数进行比较，达到对DOM树进行剪枝的效果，然后通过人工选择目标信息，对目标信息所在位置的上下界进行唯一性判定，从而构建提取模板，是一种半自动、通用的方法。

3 算法综述

3.1 逆向匹配构建DOM树 定义： DOM(document object model)文档对象模型，是W3C组织推荐的处理可扩展置标语言的标准编程接口。HTML文档被解析后转化为DOM树，使文档的结构更加清晰。通过对DOM树节点的判断与剪枝，可以方便地对无关信息进行删除和修改。

由于网页的HTML代码的语法要求不严格，在HTML中，如果上下文清楚地显示出段落或者列表键在何处结尾，那么就可以省略

或者之类的结束标记。这给正向匹配构建DOM树构成了障碍，导致无法准确判定各个HTML标签的嵌套结构，而通过逆向匹配识别HTML标签则可以构建完整的DOM树，因此本文提出了一种通过逆向匹配构建DOM树的方法。

1) 首先读取HTML文档为字符串形式。

2) 依次识别HTML标签，即等，忽略HTML文档注释<！-- -->，将识别到的标签依次存入栈stack1中，当读取的标签为开始标签时，如，则直接入栈stack1。(整个HTML文档初步解析以后，栈stack1中保存着此HTML文档的所有标签，栈stack2中保存着相对应的属性和文本信息。)

3) 将栈stack1中的标签依次取出，若当前取出的标签为结束标签，则直接存入栈stack3和栈stack0中，若当前取出的标签为开始标签，则将其加上“/”前缀后与stack0的栈顶字符串比较，若两字符串相等，则弹出栈stack0的栈顶元素，并且将从stack1中取出的那个开始标签加入栈stack3中，若此开始标签加上“/”前缀后与栈stack0的栈顶字符串不等价，则说明此开始标签在原HTML文档没有匹配的结束标签，故应将其补全，即将此开始标签加上“/”前缀后构成的结束标签加入栈stack3中，然后将此开始标签加入栈stack3中。依此规则将栈stack1中的标签全部转存如栈stack3中。

4) 将栈stack2中的属性和文本信息全部转存入栈stack4中。(此时，栈stack3中保存的信息为原栈stack1中补全后的逆序，而栈stack4中为原栈stack2中信息的逆序。)

5) 从栈stack3中取出一个栈顶元素，必定为开始标签，以此标签作为所要构建的DOM树的根节点标签，并同时将此根节点入栈stack5，即栈stack5中存的是DOM树的节点；在stack4中取出两个字符串作为根节点的属性信息和文本信息，以当前构建节点的子树形式表示。

6) 依次从栈stack3中取出栈顶元素，若此元素为开始标签，则以此标签作为栈stack5中栈顶节点的子节点，并在栈stack4中取出两个字符串作为刚建立的子节点的属性信息和文本信息，以子树形式表示；若从栈stack3中取出的栈顶元素为结束标签，则从栈stack5中弹出一个节点，表明此节点不再有子节点。依次规律直到栈stack3为空为止。

7) 构建好DOM树后，由于之前用空串代替了缺省的属性和文本信息，所以，若构建出的DOM树的节点中有空串属性或文本，则删除该属性或文本。

此时，构建DOM树完毕，可以通过将其存为XML文件以可视化。一个简单的示例及其构建的DOM树如表1所示。

表1 构建DOM树结果示例

其中构建的DOM树运用了前缀编码[5]，以唯一标示每个节点。

3.2 剪枝算法

剪枝算法是在保留需要提取的信息的前提下删除无关节点的过程。本算法通过比较同一网站的多个商品网页的DOM树，剪去其中相同的子树，达到删除大量无关节点的目的。同时通过采用链接数和非链接文字数两个语义信息进行辅助剪枝，进而最大化地删除无关节点，以方便人工选择。

本文需要提取的电子商务网站(以京东商城为例)的商品网页信息如图1、图2所示。

图1 电子商务网站主题信息

图2 电子商务网站参数信息

每次从同一电子商务网站取出n个不同商品的网页，记为Y={y1，y2，……，yn}；对它们分别构建DOM树： D={d1，d2，……，dn}；将d2～dn依次与d1比较(保存d1的副本，以用于唯一性判定)，若叶子节点中的属性与文本信息都相同，则剪去该叶子节点，若非叶子节点中的属性与文本信息都相同，且它的子节点都已被剪枝，则剪去该非叶子节点。当整个DOM树比较完毕时，则原商品网页中的模板信息已被剪枝。

图3中黑色部分表示DOM树中与其他DOM树相同的部分，通过比较剪枝，删除了这部分节点，得到右图为剪枝后的结果。

图3 对DOM树剪枝示例

本文采用信息提取算法[4]进行辅助剪枝，对其中的阈值进行重新测试，以达到较高的覆盖率。该算法提出运用链接数和非连接文字数两个语义信息进行计算局部相关度和上下文相关度，通过确定局部相关度阈值和上下文相关度阈值进行判断节点与主题的相关性，进而达到剪枝的效果，通过两次剪枝，可将剪枝率最大化，从而方便人工选择。

3.3 人工选择与唯一性判定

通过剪枝算法进行剪枝后，DOM树中已经删除了大量无关信息，通过进行人工选择与唯一性判定可增强目标信息提取的准确性。

首先制定一个人工选择界面，将剪枝后的DOM树中的叶子节点放入预选区；然后人工选择目标信息，程序自动记录所选叶子节点的编码；在之前保存的d1的副本中查找所选编码的叶子节点；确定目标叶子节点的上下界，并在网页源代码y1中进行唯一性判定，直到找到唯一的上下界为止；保存上下界信息，以用于构建提取模板。

3.4 构建模板

通过上下界的唯一性判定后，可以构建XML文件形式的提取模板，其中存储了每段目标信息的上下界，通过读取此XML文件，可以从相应于此模板的电子商务网站中的各个商品网页中提取出目标信息，其中还包含了许多HTML标签，所以还需有一个去除HTML标签的程序对提取结果进行修正。

一个京东商城模板构建结果如表2所示。

表2 模板构建结果示例

4 实验结果

爬取京东商城、亚马逊商城、淘宝网等网站的各类商品网页源代码，分别构建网页的DOM树，每次比较2～8个网页DOM树(即n取2～8)，对于每个n值重复50次取平均值，比较剪枝效果，确定最好的n值，然后运用不同的局部相关性阈值与上下文相关度阈值进行测试。

图4展示了固定上下文相关度为10时，剪枝率和覆盖率随局部相关度的变化情况。随着局部相关度的增大，剪枝率不断增大，而覆盖率在局部相关度大于2时不再为100%；图5展示了固定局部相关度为2时剪枝率和覆盖率随上下文相关度的变化情况。随着上下文相关度的增大，剪枝率不断增大，但覆盖率在局部相关度大于10时不再为100%。

图4 固定上下文相关度为10时剪枝率和覆盖率随局部相关度变化表

图5 固定局部相关度为2时剪枝率和覆盖率随上下文相关度变化表

为了保证模板提取的准确率，剪枝结果的覆盖率必须保证为100%，以确保能最后保留主题和参数信息，通过图4、图5可以看出，上下文相关度取10，局部相关度取2在京东商城网站上能获得最好的结果，而通过对亚马逊和淘宝等网站的测试，这两个值也能得到覆盖率为100%，如表3所示。

表3 对三个电子商务网站的商品网页的DOM树剪枝结果(局部相关度取2，上下文相关度取10)

来源网站剪枝率/%覆盖率/%京东 82．25100亚马逊44．87100淘宝 63．09100

其中，剪枝率表示剪去的DOM树节点占整个DOM树的平均比例；覆盖率表示剪枝结束后剩下的DOM树节点中目标信息占所有应提取的目标信息的比例。

实验表明，每次比较的网页数n取4，局部相关度阈值取2，上下文相关度阈值取10，最小长度值取1时能得到最好的剪枝结果，并且在各个网站中具有较高的通用性。

本方法与同领域的其他方法相比，优于周炘等人和侯明燕等人的方法，不需要对目标网站的商品网页进行深入分析，只需选择所要提取的目标信息就可自动构建模板；对于结构复杂的电子商务网站的信息提取，优于王琦等人的方法，能够准确的提取出目标信息。

5 总结与展望

在电子商务网站的商品网页信息提取领域，人工编写抽取规则能得到很高的准确率，但需要在网页每次改版以及有新的电子商务网站出现时进行配置模板，本文的方法在保证较高的准确率的条件下减少了大量人工参与工作，简化了提取过程。

在剪枝算法中，充分利用了同一电子商务网站中的商品网页均有相同模板生成的特点，大量提高了剪枝率，为人工选择减少了大量工作。但是一个商品网页的源代码相对于人工操作比较庞大，即使达到现在的剪枝率，剩下的DOM树也依然较大，寻找提高剪枝率的办法，能为人工选择提供方便。另外当能把所有无关信息都进行剪枝时，可实现模板的自动构建。

[1] 杨晓琴，鞠时光，曹庆皇等.面向Deep Web数据自动抽取的模板生成方法[J].计算机应用，2010，27(1)： 200-203.

[2] 周炘.面向电子商务网站的深度搜索与信息抽取研究[D].江西： 江西师范大学软件学院硕士学位论文，2011.

[3] 侯明燕.基于网页信息定位的数据抽取技术的研究[D].广东： 暨南大学硕士学位论文，2011.

[4] 王琦，唐世渭，杨冬青等.基于DOM树的网页主题信息自动提取[J].计算机研究与发展，2004，41(10)： 1786-1792.

[5] Beyer K, Viglas S D, Tatarinov I, et al. Storing and querying ordered XML using a relational database system[C]//Proceedings of the 2002 ACM SIGMOD International Conference, 2002: 204-215.

傅彦(1962—)，硕士，教授，博士生导师，主要研究领域为数据挖掘。E⁃mail：fuyan@uestc．edu．cn徐昭邦(1991—)，硕士研究生，主要研究领域为数据挖掘。E⁃mail：xzhaobang@163．com夏虎(1981—)，博士，助理研究员，主要研究领域为数据挖掘、复杂网络。E⁃mail：xiahu@uestc．edu．cn

全国第十四届计算语言学会议(CCL 2015)及第三届基于自然标注大数据的自然语言处理

国际学术研讨会(NLP-NABD 2015)联合征稿启事

“第十四届全国计算语言学学术会议”(The Fourteenth China National Conference on Computational Linguistics, CCL 2015)将于2015 年11月13日—14日在广东外语外贸大学举行。作为国内最大的自然语言处理专家学者的社团组织——中国中文信息学会(CIPS)的旗舰会议，全国计算语言学会议从1991年开始每两年举办一次，从 2013 年开始每年举办一次，经过 20 余年的发展历程，已形成了十分广泛的学术影响，成为国内自然语言处理领域权威性最高、口碑最好、规模最大(2014年参会人数超过了 400 名)的学术会议。CCL 着重于中国境内各类语言的计算处理，为研讨和传播计算语言学最新的学术和技术成果提供了高水平的深入交流平台。

CCL 2015征集各类与汉语和中国少数民族语言相关的计算语言学方面的原创研究和应用论文。论文包括但不限于以下内容：

· 语言处理的认知建模和心理语言学

· 篇章、共指和语用学

· 评测方法

· 语言资源和标注

· 词汇语义学和词汇本体论

· 大规模知识获取和推理

· 机器翻译

· 多语言自然语言处理

· 自然语言处理应用

· 社交媒体中的自然语言处理

· 命名实体识别与链接

· 开放领域的问答系统

· 语义学

· 情感分析、意见挖掘与文本分类

· 社会计算

· 语音识别与合成

· 自然语言处理的统计与机器学习方法

· 文本摘要和生成

· 句法分析与网页分析

· 词性标注和组块分析

· 文本蕴含·文本挖掘、开放域信息抽取与网页机器阅读

· 互联网信息检索

· 资源稀缺的自然语言处理

· 分词

· 词义消歧

· 多模态处理

· 医学自然语言处理CCL 2015同时接受中文和英文投稿。录用的稿件分为两类：口头报告(Oral)和海报张贴(Poster)。被录用的Oral 中文稿件将在中国自然语言处理领域最具影响力的期刊《中文信息学报》发表，但作者必须根据会议和期刊的审稿意见进行 相应修改，《中文信息学报》对未完成修改的稿件保留不予发表的权利。被录用的Poster 中文稿件将推荐至其他计算机类中国科技核心期刊(中国科学技术信息研究所制定) 。部分期刊会要求再审，通过后方能发表。被录用的英文稿件将由 Springer Lecture Notes in Artificial Intelligence (LNAI)出版。

“第三届基于自然标注大数据的自然语言处理国际学术研讨会”(The Third International Symposium on Natural Language Processing based on Naturally Annotated Big Data, NLP-NABD 2015)将与CCL 2015同时召开。NLP-NABD涵盖了前面列举的所有自然语言处理的研究内容，尤其关注在大数据时代自然语言处理的前沿方法和技术。这里所谓的“自然标注”是指由互联网用户根据其自身目的(而不是出于自然语言处理研究的目的) 对各种互联网资源进行的“不自觉”的手工标注，计算语言学家们可以将这些标注自觉地和系统性地应用在自然语言处理的各种研究中。典型的例子是，标点符号有助于词边界的识别，社交媒体中的社会标签

也有助于关键词抽取，而维基百科中的条目类别信息则可以为文本分类提供帮助。在这些例子中，“自然标注”都是以显式的形式出现的，但在很多情况下，也可以以隐式的形式出现，如短语“Beijing and other cities”“cities such as Beijing”中所蕴含的两个模式“cities such as NOUN”“NOUN and other cities” 就是一种隐式的“自然标注”，可用于抽取常识知识 ISA(NOUN, city)。NLP-NABD 2015 聚焦国内外在此方向上的各种前沿研究进展，如：如何在自然标注大数据上有效进行大规模无监督/半监督机器学习(如深度学习)，如何将学习到的资源、模型和已有的手工标注的核心资源和核心语言计算模型结合起来，等等。NLP-NABD 2015 受到国家973 计划项目“面向三元空间的互联网中文信息处理理论与方法”(编号：2014CB340500)资助支持。

NLP-NABD 2015 针对世界各种语言的研究(不仅限于中文)，只接受英文投稿。录用稿件将与CCL 2015录用的英文论文一起由Springer发表于LNAI系列上。

CCL 2015 和 NLP-NABD 2015 的中文投稿不超过 10 页，英文投稿不超过 12页 。 中文投稿的格式请参照中文信息学报的投稿指南(http://www.cipsc.org.cn/jsip/tougao.php)，英文投稿的格式请参照Springer的投稿指南(http://www.springer.de/comp/lncs/authors.html)。Springer会将LNAI出版的论文提交给EI以申请进入其检索。根据Springer以往的经验，论文获得EI收录的机会相当高。2013年和2014年CCL和NLP-NABD录取的英文稿件全部被EI收录。更多关于LNAI索引的信息请参阅： http://www.springer.com/computer/lncs?SGWID=0-164-6-1068921-0。

自2014年起，CCL和NLP-NABD开始设立最佳论文奖，对高质量中文和英文稿件分别予以奖励。CCL 2015和NLP-NABD 2015将设立两项最佳论文奖，由程序委员会负责评选。其中，“CCL 2015 最佳论文奖”用于奖励中文信息处理方面的优秀中文论文，“NLP-NABD 2015最佳论文奖”用于奖励大数据环境下自然语言处理方面的优秀英文论文。程序委员会将为每篇获奖论文颁发 3000 元人民币奖金和获奖证书。

CCL 2015 和 NLP-NABD 2015 时间表：

· 论文投稿的截止日期：2015年6月1日

· 录用通知发出日期：2015年7月26日

· 最终版提交日期：2015年8月10日

投稿信息：本次会议将采用双盲审稿，所以作者姓名和单位不可以出现在投稿的论文中，作者的自引不可采用“我们提出…”，而是用“作者名字提出…”。所有稿件要求以 PDF 文件形式通过 START 系统提交，提交网址为https://www.softconf.com/e/ccl2015/。

关于平行投稿政策：本次会议允许作者将同一稿件同时投向自然语言处理领域的顶级国际会议(如EMNLP 2015)，只要该国际会议也有类似的平行投稿政策。在投稿时，必须注明该稿件同时投至此类会议。作者在接收到录用通知后，必须在最终版提交日期(2015 年8月10日)之前告知程序委员会是否在本次会议发表。一旦确定，必须撤回在其他会议的稿件。本次会议不接收任何与已经公开发表的论文完全相同或者高度重合的稿件。

Reverse Match Based Semi-automatic Entity Template Extraction for E-commerce Websites

FU Yan, XU Zhaobang, XIA Hu, ZHOU Junlin

(Web Sciences Center, School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu, Sichuan 611731, China)

Generally, the distribution of the subject information in the Web page is centralized .Therefore，we can utilize this characteristics of Web page to extract the subject information automatically. Due to the fact that the HTML label in the page source code is not well qualified, it is difficult to construct a DOM tree with accurate structure through the forward matching. This article presents a new method which applies the reverse matching to construct a complete DOM tree. By deleting the insignificant node the DOM tree, we can select from the remained information node labels manually to finalize the templeaterdeciden if they are unique. This is a general and semi- automatic method, and experiments on the e-commerce webpages are reported in this paper.

reverse matching; DOM tree; template extraction; information extraction

1003-0077(2015)02-0157-06

2013-04-08 定稿日期： 2013-07-11

国家自然科学基金(61103109，11105024，61003231)，中央高校基本科研业务费(ZYGX2011J057，ZYGX2012J071，ZYGX2012J085)，四川省科技项目(2010HH0002，2011GZ0106，20112Z0001, 2012RZ0002, 2012RZ0003)，高等学校博士学科点专项科研基金(20120185120017)

TP391

A