Loading...
Please wait, while we are loading the content...
Similar Documents
Mutual k-Nearest Neighbor Graph Construction in Graph-based Semi-Supervised Classification
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ozaki, Kohei Shimbo, Masashi Komachi, Mamoru Matsumoto, Yuji |
| Copyright Year | 2013 |
| Abstract | Graph construction is an important step in graph-based semi-supervised classification. 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 evaluate the quality of the graphs apart from classification algortihms, we measure the assortativity of graphs. In addition, 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 knearest 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. |
| Starting Page | 400 |
| Ending Page | 408 |
| Page Count | 9 |
| File Format | PDF HTM / HTML |
| DOI | 10.1527/tjsai.28.400 |
| Volume Number | 28 |
| Alternate Webpage(s) | https://www.jstage.jst.go.jp/article/tjsai/28/4/28_400/_pdf |
| Alternate Webpage(s) | https://doi.org/10.1527/tjsai.28.400 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
