大规模层次分类中的候选类别搜索

摘要

大规模层次分类问题研究如何将互联网上的网页文档准确地分到类别层次中的各个类别.因为类别层次规模巨大,通常可以达到数千甚至数万个类别,严重影响了分类性能.对此,已有研究通过搜索待分类文档在类别层次中的候选类别对文档进行分类,但结果表明候选类别搜索成为了其中瓶颈.文中首先对候选搜索问题的计算复杂性进行了分析,证明了该问题是NP难的,接下来提出了一个基于贪心策略的启发式候选搜索算法,并且证明了该贪心策略在求解过程中是一个局部最优选择.作者采用DMOZ目录中的简体中文网页数据进行了实验论证,实验结果显示,相比已有算法,文中提出的候选类别搜索算法在候选类别搜索的准确率上提高了大约7.5％.