Tag clustering algorithm LMMSK:improved K-means algorithm based on latent semantic analysis

摘要

With the wide application of Web 2.0 and social soft-ware, there are more and more tag-related studies and applica-tions. Because of the randomness and the personalization in users' tagging, tag research continues to encounter data space and se-mantics obstacles. With the min-max similarity (MMS) to establish the initial centroids, the traditional K-means clustering algorithm is firstly improved to the MMSK-means clustering algorithm, the superiority of which has been tested; based on MMSK-means and combined with latent semantic analysis (LSA), here secondly emerges a new tag clustering algorithm, LMMSK. Finally, three al-gorithms for tag clustering, MMSK-means, tag clustering based on LSA (LSA-based algorithm) and LMMSK, have been run on Mat-lab, using a real tag-resource dataset obtained from the Delicious Social Bookmarking System from 2004 to 2009. LMMSK's cluster-ing result turns out to be the most effective and the most accurate. Thus, a better tag-clustering algorithm is found for greater appli-cation of social tags in personalized search, topic identification or knowledge community discovery. In addition, for a better compar-ison of the clustering results, the clustering corresponding results matrix (CCR matrix) is proposed, which is promisingly expected to be an effective tool to capture the evolutions of the social tagging system.