RW.KNN: A proposed random walk KNN algorithm for multi-label classification

Xin Xia, Xiaohu Yang, Shanping Li, Chao Wu, Linlin Zhou

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)

Abstract

Multi-label classification refers to the problem that predicts each single instance to be one or more labels in a set of associated labels. It is common in many real-world applications such as text categorization, functional genomics and semantic scene classification. The main challenge for multi-label classification is predicting the labels of a new instance with the exponential number of possible label sets. Previous works mainly pay attention to transforming the multi-label classification to be single-label classification or modifying the existing traditional algorithm. In this paper, a novel algorithm which combines the advantage of the famous KNN and Random Walk algorithm (RW.KNN) is proposed. The KNN based link graph is built with the k-nearest neighbors for each instance. For an unseen instance, a random walk is performed in the link graph. The final probability is computed according to the random walk results. Lastly, a novel algorithm based on minimizing Hamming Loss to select the classification threshold is also proposed in this paper.

Original languageEnglish
Title of host publicationCIKM 2011 Glasgow
Subtitle of host publicationPIKM'11 - Proceedings of the 2011 Workshop for Ph.D. Students in Information and Knowledge Management
PublisherAssociation for Computing Machinery (ACM)
Pages87-90
Number of pages4
ISBN (Print)9781450309530
DOIs
Publication statusPublished - 15 Dec 2011
Externally publishedYes
EventWorkshop for Ph.D. Students in Information and Knowledge Management, PIKM'11 - Glasgow, United Kingdom
Duration: 28 Oct 201128 Oct 2011
Conference number: 4th

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

ConferenceWorkshop for Ph.D. Students in Information and Knowledge Management, PIKM'11
CountryUnited Kingdom
CityGlasgow
Period28/10/1128/10/11

Keywords

  • knn
  • link graph
  • multi-label classification
  • random walk

Cite this

Xia, X., Yang, X., Li, S., Wu, C., & Zhou, L. (2011). RW.KNN: A proposed random walk KNN algorithm for multi-label classification. In CIKM 2011 Glasgow: PIKM'11 - Proceedings of the 2011 Workshop for Ph.D. Students in Information and Knowledge Management (pp. 87-90). (International Conference on Information and Knowledge Management, Proceedings). Association for Computing Machinery (ACM). https://doi.org/10.1145/2065003.2065022