Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

APPECT: An Approximate Backbone-Based Clustering Algorithm for Tags

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 7120))

Included in the following conference series:

  • 1005Accesses

  • 4Citations

Abstract

In social annotation systems, users label digital resources by using tags which are freely chosen textual descriptions. Tags are used to index, annotate and retrieve resource as an additional metadata of resource. Poor retrieval performance remains a major problem of most social tagging systems resulting from the severe difficulty of ambiguity, redundancy and less semantic nature of tags. Clustering method is a useful tool to address the aforementioned difficulties. Most of the researches on tag clustering are directly using traditional clustering algorithms such as K-means or Hierarchical Agglomerative Clustering on tagging data, which possess the inherent drawbacks, such as the sensitivity of initialization. In this paper, we instead make use of the approximate backbone of tag clustering results to find out better tag clusters. In particular, we propose an APProximate backbonE-based Clustering algorithm for Tags (APPECT).The main steps of APPECT are: (1) we execute the K-means algorithm on a tag similarity matrix forM times and collect a set of tag clustering resultsZ = C1,C2,...,Cm; (2) we form the approximate backbone ofZ by executing a greedy search; (3) we fix the approximate backbone as the initial tag clustering result and then assign the rest tags into the corresponding clusters based on the similarity. Experimental results on three real world datasets namely MedWorm, MovieLens and Dmoz demonstrate the effectiveness and the superiority of the proposed method against the traditional approaches.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Zong, Y., Xu, G.D., Jin, P., et al.: A local information passing clustering algorithm for tagging systems. In: The Second Workshop on Social Networks and Social Media Mining on the Web, Hong Kong, pp. 333–343 (2011)

    Google Scholar 

  2. Durao, F., Dolog, P.: Extending a hybrid tag-based recommender system with personalization. In: SAC 2010: Proceedings of the 2010 ACM Symposium on Applied Computing, pp. 1723–1727. ACM, New York (2010)

    Google Scholar 

  3. Jäschke, R., Marinho, L., Hotho, A., Schmidt-Thieme, L., Stumme, G.: Tag Recommendations in Folksonomies. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladenič, D., Skowron, A. (eds.) PKDD 2007. LNCS (LNAI), vol. 4702, pp. 506–514. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  4. Tso-Sutter, K.H.L., Marinho, L.B., Schmidt-Thieme, L.: Tag-aware recommender systems by fusion of collaborative filtering algorithms. In: SAC 2008: Proceedings of the 2008 ACM Symposium on Applied Computing, pp. 1995–1999. ACM, New York (2008)

    Google Scholar 

  5. Gemmell, J., Shepitsen, A., Mobasher, M., Burke, R.: Personalization in folksonomies based on tag clustering. In: Proceedings of the 6th Workshop on Intelligent Techniques for Web Personalization and Recommender Systems (July 2008)

    Google Scholar 

  6. Shepitsen, A., Gemmell, J., Mobasher, B., Burke, R.: Personalized recommendation in social tagging systems using hierarchical clustering. In: Proceedings of the 2008 ACM Conference on Recommender Systems, pp. 259–266. ACM (2008)

    Google Scholar 

  7. Zong, Y., Jiang, H., Li, M.C.: Approximate backbone guided reduction clustering algorithm. Journal of Electronics and Information Technology 31(2), 2953–2957 (2009)

    Google Scholar 

  8. Astrain, J.J., Echarte, F., Córdoba, A., Villadangos, J.: A Tag Clustering Method to Deal with Syntactic Variations on Collaborative Social Networks. In: Gaedke, M., Grossniklaus, M., Díaz, O. (eds.) ICWE 2009. LNCS, vol. 5648, pp. 434–441. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  9. Simpson, E.: Clustering tags in enterprise and web folksonomies. HP Labs Technical Reports, citeulike: 2545406 (2008)

    Google Scholar 

  10. Boratto, L., Carta, S., Vargiu, E.: RATC: A Robust Automated Tag Clustering Technique. In: Di Noia, T., Buccafurri, F. (eds.) EC-Web 2009. LNCS, vol. 5692, pp. 324–335. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  11. Zhou, J.L., Nie, X.J., Qin, L.J., et al.: Web clustering based on tag set similarity. Journal of Computers 6(1), 59–66 (2011)

    Google Scholar 

  12. Matteo, N.R., Peroni, S., Tamburini, F., et al.: A parametric architecture for tags clustering in folksonomic search engines. In 9th international Conference on Intelligent Systems Design and Applications, Pisa, Italy, pp. 279–282 (2009)

    Google Scholar 

  13. Chen, H., Dumais, S.: Bringing order to the web: Automatically categorizing search results. In: Proceedings of the SIGCHI Conference on Human Factors in Computting Systems, pp. 145–152. ACM (2000)

    Google Scholar 

  14. van Dam, J., Vandic, D., Hogenboom, F., Frasincar, F.: Searching and browsing tagspaces using the semantic tag clustering search framework. In: 2010 IEEE Fourth International Conference on Semantic Computing (ICSC), pp. 436–439. IEEE (2010)

    Google Scholar 

  15. Lehwark, P., Risi, S., Ultsch, A.: Visualization and clustering of tagged music data. Data Analysis, Machine Learning and Applications, 673–680 (2008)

    Google Scholar 

  16. Miao, G., Tatemura, J., Hsiung, W., Sawires, A., Moser, L.: Extracting data records from the web using tag path clustering. In: Proceedings of the 18th International Conference on World Wide Web, pp. 981–990. ACM (2009)

    Google Scholar 

  17. Giannakidou, E., Koutsonikola, V., Vakali, A., Kompatsiaris, Y.: Co-clustering tags and social data sources. In: The Ninth International Conference on Web-Age Information Management, pp. 317–324. IEEE (2008)

    Google Scholar 

  18. Nicola, R.D., Silvio, P., Fabio, T., et al.: Of mice and terms: Clustering algorithms on ambiguous terms in folksonomies. In: Proceeding of the 2010 ACM Symposium on Applied Computing SAC 2010, pp. 844–848 (2010)

    Google Scholar 

  19. Jiang, Y.X., Tang, C.J., Xu, K.K., et al.: Core-tag clustering for web2.0 based on multi-similarity measurements. In: The Joint International Conference on Asia-Pacific Web Conference (APWeb) and Web-Age Information Management (WAIM), Suzhou, China, pp. 222–233 (2009)

    Google Scholar 

  20. Zou, P., ZHou, Z.H., Chen, G.L.: Approximate backbone guided fast ant algorithm to QAP. Journal of Software 16(10), 1691–1698 (2005)

    Article MATH  Google Scholar 

  21. Jiang, H., Zhang, X.C., Chen, G.L.: Exclusive overall optimal solution of graph bipartition problem and backbone compute complexity. Chinese Science Bulletin 52(17), 2077–2081 (2007)

    Article  Google Scholar 

  22. Jiang, H., Zhang, X.C., Chen, G.L.: Backbone analysis and algorithm design of QAP. Chinese Science 38(01), 1–14 (2008)

    Google Scholar 

  23. Guan, Z., Wang, C., Bu, J., Chen, C., Yang, K., Cai, D., He, X.: Document recommendation in social tagging services. In: Proceedings of the 19th International Conference on World Wide Web, pp. 391–400. ACM (2010)

    Google Scholar 

  24. Mika, P.: Ontologies Are US: A Unified Model of Social Networks and Semantics. In: Gil, Y., Motta, E., Benjamins, V.R., Musen, M.A. (eds.) ISWC 2005. LNCS, vol. 3729, pp. 522–536. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  25. Lin, X., Guo, L., Zhao, Y.E.: Tag-bsed social interest discovery. In: Proceeding of the 17th International World Wide Web Conference (2008)

    Google Scholar 

  26. Sibson, R.: SLINK: An optimally efficient algorithm for single-link cluster method. Computer Journal 16(1), 30–34 (1973)

    Article MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information and Engineering, West Anhui University, Luan, 237012, China

    Yu Zong & Ping Jin

  2. Department of Computer Science and Technology, University of Science and Technology, Hefei, 230036, China

    Yu Zong & EnHong Chen

  3. Center for Applied Informatics, Victoria University, PO Box 14428, VIC, 8001, Australia

    Guandong Xu & Yanchun Zhang

  4. Department of Computer Science, Aalborg University, Denmark

    Rong Pan

Authors
  1. Yu Zong
  2. Guandong Xu
  3. Ping Jin
  4. Yanchun Zhang
  5. EnHong Chen
  6. Rong Pan

Editor information

Editors and Affiliations

  1. Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, China

    Jie Tang  & Jianyong Wang  & 

  2. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, SAR, China

    Irwin King

  3. Faculty of Engineering and Information Technology, University of Technology, 2007, Sydney, NSW, Australia

    Ling Chen

Rights and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zong, Y., Xu, G., Jin, P., Zhang, Y., Chen, E., Pan, R. (2011). APPECT: An Approximate Backbone-Based Clustering Algorithm for Tags. In: Tang, J., King, I., Chen, L., Wang, J. (eds) Advanced Data Mining and Applications. ADMA 2011. Lecture Notes in Computer Science(), vol 7120. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25853-4_14

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp