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

Category Candidate Search in Large Scale Hierarchical Classification

作　　者：何力[1] 丁兆云[2] 贾焰[1] 韩伟红[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]国防科学技术大学信息系统与管理学院,长沙410073

出　　处：《计算机学报》2014年第1期41-49,共9页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2010AA012505;2011AA010702;2012AA01A401;2012AA01A402);国家自然科学基金(60933005;91124002;61303265);国家科技支撑计划项目(2012BAH38B04;2012BAH38B06);国家242信息安全计划项目(2011A010)资助~~

摘　　要：大规模层次分类问题研究如何将互联网上的网页文档准确地分到类别层次中的各个类别.因为类别层次规模巨大,通常可以达到数千甚至数万个类别,严重影响了分类性能.对此,已有研究通过搜索待分类文档在类别层次中的候选类别对文档进行分类,但结果表明候选类别搜索成为了其中瓶颈.文中首先对候选搜索问题的计算复杂性进行了分析,证明了该问题是NP难的,接下来提出了一个基于贪心策略的启发式候选搜索算法,并且证明了该贪心策略在求解过程中是一个局部最优选择.作者采用DMOZ目录中的简体中文网页数据进行了实验论证,实验结果显示,相比已有算法,文中提出的候选类别搜索算法在候选类别搜索的准确率上提高了大约7.5%.The large scale hierarchical classification problem researches how to classify web documents into the categories among a class hierarchy.As the class hierarchy is very large that generally containing thousands or even tens of thousands of categories,the performance of the classification is still lower.While a reduce-and-conquer strategy was proposed to make the problem tractable,the candidate search methods might be a bottleneck in the classification.In this paper,we first analyzed the computational complexity of the category candidate search problem,and proved that it was NP-hard.Then a heuristic algorithm based on greedy strategy for candidate search was proposed,and we proved that the proposed greedy strategy was a local optimum choice in the heuristic solving process.Experiments were conducted on the dataset of web pages from the Chinese Simplified branch of the DMOZ directory.The results show that our algorithm improved the candidate search performance and V10 scores achieved by our algorithm by up to 7.5％.

关 键 词：文本分类 大规模层次分类 类别层次 候选类别 候选搜索问题 社交网络 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]