Adapting K-Nearest Neighbor for Tag Recommendation

Folksonomies, otherwise known as Collaborative Tagging Systems, enable Internet users to share, annotate and search for online resources with user selected labels called tags. Tag recommendation, the suggestion of an ordered set of tags dur-ing the annotation process, reduces the user effort from a keyboard entry to a mouse click. By simplifying the anno-tation process tagging is promoted, noise in the data is re-duced through the elimination of discrepancies that result in redundant tags, and ambiguous tags may be avoided. Tag rec-ommenders can suggest tags that maximize utility, offer tags the user may not have previously considered or steer users toward adopting a core vocabulary. In sum, tag recommenda-tion promotes a denser dataset that is useful in its own right or can be exploited by a myriad of data mining techniques for additional functionality. While there exists a long history of recommendation algo-rithms, the data structure of a Folksonomy is distinct from those found in traditional recommendationproblems. We first explore two data reduction techniques, p-core processing and Hebbian deflation, then demonstrate how to adaptK-Nearest Neighbor for use with Folksonomies by incorporating user, resource and tag information into the algorithm. We further investigate multiple techniques for user modeling required to compute the similarity among users. Additionally we demon-strate that tag boosting, the promoting of tags previously ap-plied by a user to a resource, improves the coverage and ac-curacy ofK-Nearest Neighbor. These techniques are evaluated through extensive experimen-tation using data collected from two real Collaborative Tag-ging Web sites. Finally the modified K-Nearest Neighbor algorithm is compared with alternative techniques based on popularity and link analysis. We find thatK-Nearest Neigh-bor modified for use with Folksonomies generates excellent recommendations, scales well with large datasets, and is ap-plicable to both narrow and broadly focused Folksonomies