百科实例的分类算法探究
2015-05-04王超蔡润波
王超 蔡润波
摘 要：在互联网信息爆炸的时代，百科成为了互联网用户获取可信结构化信息的首选途径，然而，现有的百科文档的不规范、概念体系的不健全，造成了相当一大部分百科文档没能归入现有概念体系，影响了知识体系的构造和再生。文章以百度百科作为研究对象，采用基于信息框属性的分类算法，以及基于相关实体的分类算法对百度百科中的未分类文档进行分类，实验表明，两种算法都具有较高的分类准确率，结合两种算法能覆盖除部分只有标题信息的绝大部分未分类文档，因此，能对百科实例的分类问题给出较好的解答。
关键词：百科；分类；信息框；相关实体
引言
自互联网诞生以来，人类所面临的信息就呈现着爆炸式的增长。然而，面对着浩如烟海的海量信息，人类反而显得不知所从。搜索引擎出现了，搜索引擎通过关键词提取及信息检索技术，帮助互联网用户迅速地找到信息。然而，这并不能完全满足互联网用户的需求，因为互联网信息常常是非结构化的——用户想获取的信息常常以不同的方式散落在互联网的各个角落——而为了获取这些完整的信息，用户不得不翻阅很多网页，花费大量的时间和精力从这些信息中提取出有用的知识。如何有效、规范地定义并描述互联网的实体，以结构化的方式组织互联网上的知识，使得互联网上的知识能够有效地融合，就显得尤为迫切而重要。
百科作为互联网知识的经典表现形式，借助其开放性，互联网的百科文档成为了众多互联网用户获取知识的首选路径。然而，正是由于其开放性，互联网百科文档呈现出了诸多不规范性：如概念体系的不完整，分类体系的不健全，实际上，目前互联网百科文档中有相当一大部分并没有得到合适的分类，而这造成的结果是，一方面，对实例本身的描述不全面，另一方面，形成知识的孤岛，无法将实例文档融入现有的知识体系，也难以基于该实例文档推导出新的知识。因此，如何在现有百科的开放体系下，解决百科文档概念体系不完整的问题，进而构造富有活力的知识生态，就显得尤为重要。
因此，文章将以国内最大的中文知识库——百度百科为例，探究如何为未恰当标注类别的百科文档添加类别标签，以健全现有百科文档的知识体系。
1 问题定义
百科文档通常呈现半结构化的形式，百科文档通常由若干个相对规范的部分组成，即标题、类别、信息框、摘要、相关实体、正文等。因此可以用如下的六元组来表征百科文档。
d={title，catogories，infobox，abstract，link，essay}
受实验数据限制，在本实验中，正文项缺失，因此，文章所探讨的百科文档可以仅表示为如下的五元组。
d={title，catogories，infobox，abstract，link}
其中，信息框通常为一系列“键-值”对所构成，即信息框可以表示为<键，值>对的集合：
Infobox={（key1，value1），（key2，value2），…（keyn，valuen）}
不妨将其中的键所构成的集合称为keysetd。
此外，由于百科分类体系的不规范，同一个百科文档通常会被归为多个不同的类别，因此，类别字段通常也是一个组合，即由若干类标签构成的组合。
catogories={c1，c2，…，cn}
同样，同一个百科文档通常会与多个实体相关联，因此，相关实体字段也可以表示为一个集合，其中的每一个元素为一个百科文档中的实体，即：
link={ent1，ent2，...，entn}；
文章将探讨如何将百度百科中未分类的实例归到12个根类别中，即艺术、技术、文化、生活、地理、社会、人物、经济、科学、历史、自然、体育。因此，将百科的文档的根类别定义为label，其取值在上述的十二个根类别当中。标注的百科文档为“文档-标签”对，即：
ld={d，label}；
因此，可以将文章研究的百科文档分类问题定义为，寻找函数映射关系f，使得给定一个已标注的百科文档集合LdSet以及另一未标注的百科文档d，输出文档的类别属性l；
f：
也可以将该分类过程形式化为两个阶段：第一阶段，给定一个已标注的百科文档集合，训练出一个模型；第二阶段，给定一个未分类的百科文档，基于训练出来的模型即输入文档，输出该文档的类别属性，即：
f1：LdSet→Model
f2：
下面，我们将对本章形式化的问题进行求解，并对求解的方法进行评测。
2 方法描述
实际上，在本实验中，初始的数据并不是在上一章中所描述的标注文档集以及未标注文档，而是一个混合的文档集合--即该文档包含有类别属性的文档和没有类别属性的文档。其中，有类别属性的文档通常其类别集合不包含根类别，而这些文档中有一部分包含根分类的子孙类别属性，因此，基于百科的概念体系可以挂靠到根类别下，另外一部分文档则没有类别属性，或者是其类别属性不在现有的百科的概念体系中，因此无法挂靠到根类别下，而这正是文章需要分类的目标文档。因此，下面将首先介绍数据的预处理过程，即将输入文档转化为已标注的文档集及未标注的文档集，然后介绍基于该数据集定义的两个分类算法——基于信息框属性的分类算法，以及基于相关实体的分类算法。
2.1 数据的预处理
本实验的数据输入为一个混合的百科文档集，包括标注（但标注不规范）的百科文档和未标注的百科文档，并将文档规范化为<标题、类别、信息框、摘要、相关实体>五元组。
为了获取文档的根类属性首先必须构建百科文档的概念知识体系，百科的类别关系树，输入<父类，子类集合>构建一棵分类树，分类树中的每一条边表征一个类别的直接父子关系。
输入如下所示：
“Root艺术；技术；文化；生活；地理；社会；人物；经济；科学；历史；自然；体育
体育 体操Mid；棋牌运动；田径运动；体育周边；...”
输出为如图1所示的分类树。
图1
其中中心节点即概念体系的Root节点。
构建了如上的概念树之后，输入一个百科文档及其类别属性集Catogories，我们就可以通过如下的方式获取其根属性。
GetRoot（catogories）
foreach type in catogories
root<-GetRootInTree（type）
if root not null then
return root
return null；
end
GetRootInTree（Node）
if node not in Tree
return null；
while parent（node）！=“Root”
node=parent（node）；
return node；
end
基于上述的方法，我们可以获取一个输入文档的根类别属性（或者找不到根类别属性），若能为输入的文档找到根类别属性，则将其加入<文档，标签>集，若无法找到对应的根类别属性，则将其加入未分类的文档集，作为分类的目标对象。
2.2 基于信息框的分类算法
不同类别的百科文档通常具有不同的属性：如人物通常有“职业”，“毕业院系”等属性；生活相关的通常有“主要食材”，“功效”等属性等等。因此，一个文档所具有的信息框属性通常能够标识这个文档所属的类别。此外，相比文档的摘要、正文，信息框属性的维度更低、噪声也更小，因此，比文档的摘要和正文通常更具备有标识意义，也能够获得更高的分类准确度。因此，下面将基于文档的信息框属性给出百科文档的一个分类算法。
基于信息框属性的分类算法的基本流程如下：
（1）初始化信息框属性集合KeySet=？覫
（2）对输入的100万个百科文档（本实验仅研究实验数据中的前100个百科文档），提取其信息框属性（即键），若该属性不在集合KeySet中，则将其加入到KeySet中，并置其词频为1，否则，将相应键的词频加1。
（3）按照词频从高到低，选取前2000个信息框属性作为特征（第2000个信息框属性的出现次数已经不足100次）。
（4）初始化12个类别的特征向量Vec1=（0，0，...，0），...，Vec12=（0，0，...，0），其中每一个维度对应（3）中选取的一个信息框属性。
（5）对于已标注文档集合中的每个文档，若其信息框属性在（3）中选取的2000个属性中，则将其对应类别的特征的相应维度加1。
执行完上面五个步骤之后，我们可以得到12个类别的特征向量，特征向量的每一个维度对应一个信息框属性，特征向量表征该类别通常与那些信息框属性相关联。
有了12个类别的特征向量之后，就可以基于这12个特征向量对这未分类的文档进行分类了，其方法是：
（1）对于输入的文档，若其没有信息框属性，则直接返回，因为基于此方法无法给出分类。
（2）提取输入文档的信息框属性，并将其转换为特征向量，每一维度对应上面选取的一个信息框属性（共2000个）。
（3）计算输入的文档的特征向量与12个类别的特征向量之间的夹角的余弦，并以此表征输入文档与各类别之间的相关性：
Similarity=■
（4）将输入文档归入与之相似性最大的类别中，返回类别标签。
2.3 基于相关实体的分类算法
尽管基于信息框属性的分类算法已经能够获取不错的分类准确度，由于未分类文档中仍有相当大部分的比例没有信息框属性（100万文档约有30万文档没有信息框属性），上面的基于信息框属性的分类算法无法对这类文档进行分类，因此，需要提出新的分类算法，对没有信息框属性的文档进行分类。
对30万没有信息框属性的文档统计发现，其中约有13万实例只有标题，没有其他信息，由于这类文档的信息量太少，分类对于没有常识的计算机而言难度太大，在本实验中不予考虑；有约16万文档有相关实体属性，有约5万实例有摘要属性，考虑到摘要属性的词频信息更稀疏，噪声更大，而相关实体属性基本上能覆盖除了13万只有标题的文档外的绝大部分文档，噪声也更小，因此，本实验选取相关实体属性对剩下的实例进行分类。
为了基于相关实体进行分类，首先我们必须获取<实体，根类别>库，即2.1中得到的标注文档集合，仅取其标题（实体名）和根类别标签构成<实体、根类别>库。
对于输入的每一个文档，若其包含相关实体属性，对其中的每一个实体，若其属于根类别Ci，认为该实例通过相关实体和根类别之间有一条边。最后，将文档实例归入与其连边最多的根类别。即认为，该文档与哪一个类别中的最多实例相关联，则该文档属于该类别——基于同一个类别内的实体之间的关联大于类别间的实体的关联的假设。
3 方法评测
在上文中，我们给出了基于信息框属性以及基于相关实体的两个分类算法。下面，将对这两个算法进行评测。
表1为经过2.1数据预处理后（即根据实例的类别信息标注其根类别）后，各个类别的实例数：
表1
从表1中可以看出，在现有的百科概念体系下，有约31.5%的实例无法挂靠到任意一个根类别下。因此，给出一个百科实例的分类算法是必要而且重要的。
因此，文章提出了基于信息框属性和基于相关实体的分类算法。
表2为运行文章提出的基于信息框属性的分类算法之后，各个类别中的实例个数（仅针对在步骤1中无法区分根类别的314527个实体）。
表2
表2可以看出，由于未分类文档中大部分文档没有类别属性，因此，大部分未分类实体无法在这一步中给出根类别属性。
那基于信息框属性的分类算法的准确率如何呢？
表3是基于信息框属性的分类算法得到的文化实例的前10个实例：
表3
可以看出前十个实例都是属于文化类的，其中除了“民间叙述诗”之外，其他都是书籍或者书籍相关的简介。
表4是基于信息框属性的分类算法给出的人物实例的前10个实例：
表4
从表4可以看出，算法给出的10个实例都是属于人物类别的。由此可以，基于信息框的属性虽然召回率较低（受多数百科文档没有信息框属性限制），但是其准确率还是很高的。
针对基于信息框属性的分类算法无法完成分类的299940个文档，我们使用了基于关联实体的分类算法进行分类，在2.2中已经提到，针对约30万未分类的文档，除去约13万仅有标题的文档之后，其余有16万文档包含相关实体属性，因此基于相关属性的分类算法基本上能覆盖计算机所能分类的实体的大部分，由此，可以弥补基于信息框属性的分类方法召回率较低的劣势。
表5是基于相关实体的分类算法给出的经济类的前10个实例：
表5
可以看出，给出的十个实例中，有两个分错的实例，即“王铎（北京大学教授）”以及“沙鸥（鸟类）”，其中王铎（北京大学教授）是一位在北大教金融的老师，所以也是在经济圈的人物，所以从广义上讲，尽管将该实例分为人物更恰当，但将其归为经济类的一个实例也未尝不可。因此，整体上来说，基于相关实体的分类算法的准确度还是比较高的。
综上可知，基于信息框属性的分类算法具有较高的精确度，但受限于大部分未分类的百科文档没有信息框属性，召回率较低，而基于相关实体的分类算法能覆盖绝大部分计算机“能分”（除去13万只有标题的实例），其精确度虽然比基于信息框属性的方法略低一点，但是还是维持在比较高的水平，结合两者的优点，基本上能够对百科文档中的未分类实例进行较为准确的分类。
4 结束语
文章以百度百科作为研究对象，力图给出一个分类算法，能对百科中未分类的文档进行合理的归类，以此完善现有的知识体系。基于信息框属性具有较强的标识意义，噪声较小，实验表明，该方法具有较高的分类准确率，但首先于大部分文档没有信息框属性，无法解决所有文档的分类问题。因此，文章提出了基于相关实体的分类算法，该算法能覆盖除只有标题的文档外的绝大部分未分类文档，并具有较高的分类准确率，结合这两个方法，基本能解决百科文档的分类问题。当然，我们也意识到在分类结果中，仍然存在少数分错的实例，因此，算法仍然存在提升的空间，一方面，我们可以充分利用除了信息框属性和相关实体属性外的其他属性（如标题属性）。此外，我们也可以进一步改进我们的算法以获得更高的准确率及召回率。
文章通过对国内最大的中文知识库——百度百科的内容进行分析和改进让我们初步体会到了人可阅读的知识与对机器可阅读的知识之间的鸿沟。随着信息爆炸的时代来临，知识越来越需要能被机器理解，相信知识工程将会有更多的工具和更好的方法出现。
