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

11 Citations (Scopus)


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)
Number of pages4
ISBN (Print)9781450309530
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


ConferenceWorkshop for Ph.D. Students in Information and Knowledge Management, PIKM'11
CountryUnited Kingdom


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

Cite this