Category Candidate Search in Large Scale Hierarchical Classification
Lin He · Chinese Journal of Computers · 2014
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%.