Using the Mutual k-Nearest Neighbor Graphs for Semi-supervised Classification on Natural Language Data
Using the Mutual k-Nearest Neighbor Graphs for Semi-supervised Classification on Natural Language Data
复制标题
DOI：
--
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Kohei Ozaki;M. Shimbo;Mamoru Komachi;Yuji Matsumoto
中科院分区：
文献类型：
--
作者：
Kohei Ozaki;M. Shimbo;Mamoru Komachi;Yuji Matsumoto
基于图的半监督分类的第一步是从输入数据构造图。虽然k近邻图已经成为图构建的事实上的标准方法，但本文提倡在高维自然语言数据中使用不太知名的相互k近邻图。为了比较这两种图构建方法的性能，我们在词义消歧和文档分类任务中对两种图运行半监督分类方法。实验结果表明，如果与最大生成树相结合，互k近邻图的性能始终优于k近邻图。我们将互k近邻图的更好性能归因于它更不容易产生中心点。相互k近邻图与最先进的b匹配图构造相比，也表现得同样好，甚至更好，尽管它们的计算复杂性较低。
The first step in graph-based semi-supervised classification is to construct a graph from input data. While the k-nearest neighbor graphs have been the de facto standard method of graph construction, this paper advocates using the less well-known mutual k-nearest neighbor graphs for high-dimensional natural language data. To compare the performance of these two graph construction methods, we run semi-supervised classification methods on both graphs in word sense disambiguation and document classification tasks. The experimental results show that the mutual k-nearest neighbor graphs, if combined with maximum spanning trees, consistently outperform the k-nearest neighbor graphs. We attribute better performance of the mutual k-nearest neighbor graph to its being more resistive to making hub vertices. The mutual k-nearest neighbor graphs also perform equally well or even better in comparison to the state-of-the-art b-matching graph construction, despite their lower computational complexity.