一种从维基百科半结构化数据自动构建分类树的方法
技术领域
[0001] 本发明涉及知识获取技术领域，特别涉及一种利用维基百科半结构化数据自动构建分类树的方法。
背景技术
[0002] 互联网促使信息数字化的进程加速，其上信息以指数增长。目前数字信息已呈现数量庞大、类型繁多、更新迅速等发展趋势。著名的Web搜索引擎Google索引的网页数量目前已经达到500亿。信息时代带来了海量的数字化文本，日益积累的数据使得信息的获取越来越困难。
[0003] 在数量巨大的页面中含有人工编辑的半结构化数据，这些数据散落在不同的页面中，造成人们无法从大量页面中迅速而准确地找到这些有用的半结构化信息。
[0004] 维基百科(www.wikipedia.org)是目前访问量最大的十个网站之一，维基百科页面由志愿者共同编辑，含有大量高质量的半结构化数据，这些半结构化数据中蕴藏着大量的上下位关系，因而需要自动化的抽取方法从这些半结构化数据中获取上下位关系，并进行融合最终形成分类树。
[0005] 现有技术中尚未找到有关从维基百科半结构化数据中抽取上下位关系抽取及构建分类树的专利或者文献；只检索到了一篇与本专利相关的已授权专利：一种基于Web数值表格抽取的数据挖掘方法[专利号：ZL200910084507.9]；该专利的发明人基于领域知识库，提出一种从Web数值表格抽取数值知识元库的方法。该专利所述方法依赖领域知识库，且只能处理数值表格，无法识别表格中字符串表示的实体及实体间的关系。
发明内容
[0006] 本发明的目的是提供一种从维基百科半结构化数据自动构建分类树的方法，通过分析半结构化数据中的模式和实体，自动抽取出半结构化数据中的实体及它们间的上下位关系，从而可以大大减少计算量，降低计算复杂度。所述实体是指维基百科页面的标题及结构化数据中的最小处理单元。所述实体间的上下位关系是指实体间内在的分类关系。
[0007] 为达到以上目的，本发明是采取如下技术方案予以实现的：
[0008] 一种从维基百科半结构化数据自动构建分类树的方法，包括以下步骤：
[0009] 第1步、半结构化数据的抽取：通过分析获取到页面的HTML，识别出含有半结构化数据的页面，所述半结构化数据指维基百科目录页面及维基百科条目页面中的导航表格；
[0010] 第2步、半结构化数据中上下位关系的抽取：抽取维基百科目录页面中上下位关系和导航表格中上下位关系；
[0011] 第3步、源于不同半结构化数据的上下位关系融合：依据抽取到的上下位关系集构建有向无权简单图，然后基于图的深度优先遍历算法生成分类树。
[0012] 本发明进一步的改进在于：第1步具体包括以下步骤：
[0013] 第1.1步：从维基百科网站首页www.wikipedia.org开始，通过解析页面的超链接逐层爬取所有页面，依据页面URL前缀“http：//en.wikipedia.org/wiki/”获取条目页面，依据URL前缀“http：//en.wikipedia.org/wiki/Category：”获取目录页面，每个页面对应一个实体，页面标题为该实体的名字；
[0014] 第1.2步：根据条目页面是否含有HTML标签
，筛选出含有导航表格的条目页面。[0015] 本发明进一步的改进在于：第1步具体包括以下步骤：
[0016] 1)：通过Web页面爬取工具爬取维基百科首页http：//www.wiki pedia.org/并进行解析，然后依据HTML标签
和找出该页面中的所有匹配模式http\：\/\/[a-z]+\.wikipedia\.org\/的超链接，记为{head_linki}n，其中n表示所有不同语言的维基子网站数目；每个这样的超链接head_linki对应一种语言的维基百科子网站，并且是该子网站的首页，枚举每个维基子网站首页的超链接head_linki；
[0017] 2)：构建空的哈希表 该哈希表用来记录某个页面是否已经被爬取过，使用页面的URL地址来标识不同的页面；
[0018] 3)：设置当前爬取页面地址为当前维基子网站首页，current_link＝head_linki；
[0019] 4)：在HashSet查询current_link，如果命中，表明页面已经被爬取过，则不再爬取跳转到第8步；如果该页面没有爬取过，则通过Web页面爬取工具爬取该页面，并将该链接加入到HashSet中，即执行HashSet.add(current_link)；
[0020] 5)：如果该页面URL前缀是“http：//en.wikipedia.org/wiki/Category：”，则保存该页面到ArticleSet，并跳转到第7)步；
[0021] 6)：如果该页面URL前缀是“http：//en.wikipedia.org/wiki/”，进一步判断该条目页面是否含有HTML标签
，如有则保存该页面到CategorySet；[0022] 7)：解析该页面，依据HTML标签
和找出该页面中的所有超链接{hyperlinki}m，将所有这些超链接压入超链接栈LinkStack中，即LinkStack.pushAll({hyperlinki}m)；
[0023] 8)：如果LinkStack不为空，current_link＝LinkStack.pop()，跳转到第4步；如果LinkStack为空，退出。
[0024] 本发明进一步的改进在于：第2步中目录页面中上下位关系的抽取包括以下步骤：
[0025] 第2.1.1步：解析目录页面的HTML结构，根据页面HTML标签定位目录页面的逻辑块，包括标题块、子目录块、子页面块及父目录块，逻辑块中的每个超链指向的页面表示一个实体，定义上下位关系集HRS，并设
[0026] 第2.1.2步：依据HTML标签
和
定位标题块，解析标题块中标签和得到目录页面的标题，表示为ct；[0027] 第2.1.3步：依据HTML标签
和
定位子目录块，依据HTML标签
和识别子目录块中的超链接，并抽取超链接的title属性值，表示为sci，所有超链接的title属性值的集合表示为{sci}m，其中m表示子目录块中超链接的个数；子目录块中超链接title属性值的集合{sci}m与目录页面标题ct形成上下位关系集{
}m，其中表示第i个上下位关系，sci表示下位实体，ct表示上位实体，最后将{}m加入HRS，即HRS＝HRS∪{}m；[0028] 第2.1.4步：依据HTML标签
和
定位子页面块，依据HTML标签
和识别子页面块中的超链接，并抽取超链接的title属性值，表示为sai，所有超链接的title属性值的集合表示为{sai}n，其中n表示子页面块中超链接的个数；子页面块中超链接title属性值的集合{sai}n与目录页面标题ct形成上下位关系集{
}m，sai表示下位实体，ct表示上位实体，最后将{}m加入HRS，即HRS＝HRS∪{}n；[0029] 第2.1.5步：依据HTML标签
和
定位父目录块，依据HTML标签
和识别父目录块中的超链接，并抽取超链接的title属性值，表示为fci，所有超链接的title属性值的集合表示为{fci}k，其中k表示父目录块中超链接的个数；目录页面标题ct与父目录块中超链接title属性值的集合{fci}k形成上下位关系集{
}k，ct表示下位实体，fci表示上位实体，最后将{}k加入HRS，即HRS＝HRS∪{}k。[0030] 本发明进一步的改进在于：第2步中导航表格中上下位关系的抽取包括以下步骤：
[0031] 第2.2.1步：针对每个包含导航表格的页面，根据导航表格的HTML标签
，定位每个表格的起始位置和结束位置；
[0032] 第2.2.2步：根据导航表格标题字体的格式和，识别导航表格的标题title；
[0033] 第2.2.3步：在 表 格 范 围 内 根 据 是 否 存 在 HTML标 签
判断表格下面是否嵌套子表格，如果嵌套则抽取每个子表格STi的标题subti并执行HRS＝HRS∪{}，针对每个STi重复执行第2.2.3步；如果不包含子表格则执行第2.2.4步；[0034] 第 2.2.4步：导 航 表 格 由 两 列 组 成，根 据HTML 标 签
和 | 抽取导航表格第1列的实体，形成实体集合{group_entityi}u，其中u是导航表格的行数，然后组合title与{group_entityi}u形成上下位关系集合{}u，并将{}u加入到HRS，即HRS＝HRS∪{}u；[0035] 第2.2.5步：针对抽取导航表格第2列的每个元素，分别根据是否存在 HTML 标 签
和 判断是否嵌套sub_group和sub_box两种子表格，如果嵌套则迭代执行第2.2.4步并 添 加到HRS 中，否 则根 据HTML标 签| 和 | 解析得到列表中的实体集合{list_entityj}υ，其中υ表示列表中实体的个数，然后组合group_entityi与{list_entityj}υ形成上下位关系集合并将加入到HRS，即
[0036] 本发明进一步的改进在于：第3步源于不同半结构化数据的上下位关系融合具体包括以下步骤： [0037] 第3.1步：构建一个有向无权简单图G＝(V，E)，其中V表示实体集合，E表示实体间的上下关系，开始G为空； [0038] 第3.2步：从HRS中取出一个上下位关系ei＝∈HRS，同时执行HRS＝HRS-{ei}； [0039] 第3.3步：判断在V中某个下位实体与hypo是否等价。如果不存在等价实体，则将hypo加入V，V＝V∪{hypo}； [0040] 第3.4步：判断在V中某个上位实体与hyper是否等价。如果不存在等价实体，则将hyper加入V，V＝V∪{hyper}； [0041] 第3.5步：如果hyper或hypo任何一个在V中不存在等价实体，则将ei作为G的一条新的边，即E＝E∪{ei}； [0042] 第3.6步：执行第3.2步，直到HRS为空；得到有向无权简单图G； [0043] 第3.7步：根据实体root∈V及G，通过有向无权简单图G的深度优先遍历得到以root为根的分类树T＝(V′，E′，root)，其中 [0044] 一种从维基百科半结构化数据自动构建分类树的方法，包括以下步骤： [0045] 第1步、半结构化数据抽取：维基百科中的半结构化数据包括目录页面和导航表格，首先根据URL地址前缀的不同，从维基百科网站www.wikipedia.org所有页面中识别出维基目录页面与维基条目页面；进一步根据条目页面是否包含HTML标签 找出包含导航表格的条目页面；[0046] 第2步、半结构化数据中上下位关系hypernym/hyponym relation抽取：首先，解析目录页面的HTML结构，得到页面不同的逻辑块，依据逻辑块之间的布局关系获取目录页面内所包含的实体间的上下位关系；其次是解析导航表格，得到表格的逻辑结构及所包含的实体，然后根据逻辑结构获取表格中实体间的上下位关系； [0047] 第3步、源于不同半结构化数据的上下位关系融合：首先是依据第2步得到的上下位关系集合HRS构建一个有向无权简单图G＝(V，E)，其中V表示一个实体集合，E表示实体间的上下位关系；其次是根据实体root∈V及G生成以root为根的分类树T＝(V′，E′，root)，其中 [0048] 相对于现有技术，本发明具有以下优点： [0049] 1)本发明依据HTML标签解析维基页面的目录页面及条目页面中的导航表格，准确解析其中的上下位关系，从而得到大量的上下位关系，该技术简单高效。 [0050] 2)本发明充分利用了散落在不同的维基页面中的上下位关系，进而将来源不同的上下位融合在一起，形成一个一致的上下位关系图。 [0051] 3)由于本发明的上下位关系来源于领域专家的手工编辑，从而造成通过该方法得到分类树更具有权威性。 附图说明[0052] 图1是从维基百科半结构化数据自动构建分类树的流程图。 [0053] 图2是半结构化数据抽取的流程图。 [0054] 图3是目录页面中上下位关系抽取的流程图。 [0055] 图4是导航表中上下位关系抽取的流程图。 [0056] 图5是不同源上下位关系融合的流程图。 [0057] 图6是目录页面示意图。 [0058] 图7是导航表示意图。 [0059] 图8是上下位关系图。 [0060] 图9是以“树”为根的分类树。 具体实施方式[0061] 以下结合附图及实例对本发明作进一步的说明。 [0062] 请参阅图1所示，本发明一种从维基百科半结构化数据自动构建分类树的方法，分为如下3个过程： [0063] 第1步：半结构化数据抽取，包括2个步骤。 [0064] 第1.1步：从维基百科网站首页www.wikipedia.org开始，通过解析页面的超链接逐层爬取所有页面，依据页面URL前缀“http：//en.wikipedia.org/wiki/”获取条目页面，依据URL前缀“http：//en.wikipedia.org/wiki/Category：”获取目录页面，每个页面对应一个实体，页面标题为该实体的名字； [0065] 第1.2步：根据条目页面是否含有HTML标签 ，筛选出含有导航表格的条目页面。[0066] 这些步骤的流程如图2所示，比如图6及图7分别给出“数据结构”目录页面和“数据结构”页面中的导航表格。 [0067] 第1步半结构化数据的抽取按照如下过程： [0068] 1)：通过Web页面爬取工具爬取维基百科首页http：//www.wiki pedia.org/并进行解析，然后依据HTML标签 和找出该页面中的所有匹配模式http\：\/\/[a-z]+\.wikipedia\.org\/的超链接，记为{head_linki}n，其中n表示所有不同语言的维基子网站数目。每个这样的超链接head_linki对应一种语言的维基百科子网站，并且是该子网站的首页，枚举每个维基子网站首页的超链接head_linki。 [0069] 2)：构建空的哈希表 该哈希表用来记录某个页面是否已经被爬取过，使用页面的URL地址来标识不同的页面。 [0070] 3)：设置当前爬取页面地址为当前维基子网站首页，current_link＝head_linki比如英文维基子网站首页地址为“http：//en.wikipedi a.org/wiki/Main_Page”。 [0071] 4)：在HashSet查询current_link，如果命中，表明页面已经被爬取过，则不再爬取跳转到第8步；如果该页面没有爬取过，则通过Web页面爬取工具爬取该页面，并将该链接加入到HashSet中，即执行HashSet.add(current_link)。 [0072] 5)：如果该页面URL前缀是“http：//en.wikipedia.org/wiki/Category：”，则保存该页面到ArticleSet，并跳转到第7)步。 [0073] 6)：如果该页面URL前缀是“http：//en.wikipedia.org/wiki/”，进一步判断该条目页面是否含有HTML标签 ，如有则保存该页面到CategorySet。[0074] 7)：解析该页面，依据HTML标签 和找出该页面中的所有超链接{hyperlinki}m，将所有这些超链接压入超链接栈LinkStack中，即LinkStack.pushAll({hyperlinki}m)。 [0075] 8)：如果LinkStack不为空，current_link＝LinkStack.pop()，跳转到第4步；如果LinkStack为空，退出。
[0076] 第2步：半结构化数据中上下位关系(hypernym/hyponym relation)抽取目录页面中上下位关系和导航表格中上下位关系，其中前者包含5个步骤。 [0077] 如图3所示，目录页面中上下位关系的抽取包括以下步骤： [0078] 第2.1.1步：解析目录页面的HTML结构，根据页面HTML标签定位目录页面的逻辑块，包括标题块、子目录块、子页面块及父目录块，逻辑块中的每个超链指向的页面表示一个实体，定义上下位关系集HRS，并设 [0079] 第2.1.2步：依据HTML标签 和定位标题块，解析标题块中标签和得到目录页面的标题，表示为ct；[0080] 第2.1.3步：依据HTML标签 和 定位子目录块，依据HTML标签 和识别子目录块中的超链接，并抽取超链接的title属性值，表示为sci，所有超链接的title属性值的集合表示为{sci}m，其中m表示子目录块中超链接的个数；子目录块中超链接title属性值的集合{sci}m与目录页面标题ct形成上下位关系集{ }m，其中表示第i个上下位关系，sci表示下位实体，ct表示上位实体，最后将{}m加入HRS，即HRS＝HRS∪{}m；[0081] 第2.1.4步：依据HTML标签 和 定位子页面块，依据HTML标签 和识别子页面块中的超链接，并抽取超链接的title属性值，表示为sai，所有超链接的title属性值的集合表示为{sai}n，其中n表示子页面块中超链接的个数；子页面块中超链接title属性值的集合{sai}n与目录页面标题ct形成上下位关系集{ }m，sai表示下位实体，ct表示上位实体，最后将{}m加入HRS，即HRS＝HRS∪{}n；[0082] 第2.1.5步：依据HTML标签 和 定位父目录块，依据HTML标签 和识别父目录块中的超链接，并抽取超链接的title属性值，表示为fci，所有超链接的title属性值的集合表示为{fci}k，其中k表示父目录块中超链接的个数；目录页面标题ct与父目录块中超链接title属性值的集合{fci}k形成上下位关系集{ }k，ct表示下位实体，fci表示上位实体，最后将{}k加入HRS，即HRS＝HRS∪{}k。[0083] 这些步骤的流程如图3所示，比如基于图6即可以得到表1左侧所示的上下位关系集合。 [0084] 请参阅图4所示，导航表格中抽取上下位关系的步骤为： [0085] 第2.2.1步：针对每个包含导航表格的页面，根据导航表格的HTML标签 ，定位每个表格的起始位置和结束位置； [0086] 第2.2.2步：根据导航表格标题字体的格式和，识别导航表格的标题title；
[0087] 第2.2.3步：在 表 格 范 围 内 根 据 是 否 存 在 HTML标 签 判断表格下面是否嵌套子表格，如果嵌套则抽取每个子表格STi的标题subti并执行HRS＝HRS∪{}，针对每个STi重复执行第2.2.3步；如果不包含子表格则执行第2.2.4步；[0088] 第 2.2.4步：导 航 表 格 由 两 列 组 成，根 据HTML 标 签 和 | 抽取导航表格第1列的实体，形成实体集合{group_entityi}u，其中u是导航表格的行数，然后组合title与{group_entityi}u形成上下位关系集合{}u，并将{}u加入到HRS，即HRS＝HRS∪{}u；[0089] 第2.2.5步：针对抽取导航表格第2列的每个元素，分别根据是否存在 HTML 标 签 和 判断是否嵌套sub_group和sub_box两种子表格，如果嵌套则迭代执行第2.2.4步并 添 加到HRS 中，否 则根 据HTML标 签| 和 | 解析得到列表中的实体集合{list_entityj}υ，其中υ表示列表中实体的个数，然后组合group_entityi与{list_entityj}υ形成上下位关系集合并将加入到HRS，即
[0090] 这些步骤的流程如图4所示，比如基于图7即可以得到表1右侧所示的上下位关系集合。 [0091] 表1中每个ID对应一个上下位关系，分别由上位实体和下位实体组成。 [0092] 表1从目录页面及导航表格中得到的上下位关系集合 [0093] [0094] 第3步：请参阅图5所示，源于不同半结构化数据的上下位关系融合，包括如下7个步骤。 [0095] 第3.1步：构建一个有向无权简单图G＝(V，E)，其中V表示实体集合，E表示实体间的上下关系，开始G为空； [0096] 第3.2步：从HRS中取出一个上下位关系ei＝∈HRS，同时执行HRS＝HRS-{ei}； [0097] 第3.3步：判断在V中某个下位实体与hypo是否等价。如果不存在等价实体，则将hypo加入V，V＝V∪{hypo}； [0098] 第3.4步：判断在V中某个上位实体与hyper是否等价。如果不存在等价实体，则将hyper加入V，V＝V∪{hyper}； [0099] 第3.5步：如果hyper或hyppo任何一个在V中不存在等价实体，则将ei作为G的一条新的边，即E＝E∪{ei}； [0100] 第3.6步：执行第3.2步，直到HRS为空；得到有向无权简单图G； [0101] 第3.步：根据实体root∈V及G，通过有向无权简单图G的深度优先遍历算法得到以root为根的分类树T＝(V′，E′，root)，其中 [0102] 这些步骤的流程如图5所示，比如基于表格1构建的上下位关系图如图8所示。如果选择“tree”作为root节点，那么通过有向无权简单图的深度优先遍历算法即可获得以“tree”节点为根的分类树，如图9所示。
| |
