ReCoM: reinforcement clustering of multi-type interrelated data objects

ABSTRACT

Most existing clustering algorithms cluster highly related data objects such as Web pages and Web users separately. The interrelation among different types of data objects is either not considered, or represented by a static feature space and treated in the same ways as other attributes of the objects. In this paper, we propose a novel clustering approach for clustering multi-type interrelated data objects, ReCoM (Reinforcement Clustering of Multi-type Interrelated data objects). Under this approach, relationships among data objects are used to improve the cluster quality of interrelated data objects through an iterative reinforcement clustering process. At the same time, the link structure derived from relationships of the interrelated data objects is used to differentiate the importance of objects and the learned importance is also used in the clustering process to further improve the clustering results. Experimental results show that the proposed approach not only effectively overcomes the problem of data sparseness caused by the high dimensional relationship space but also significantly improves the clustering accuracy.

REFERENCES

• 1: P. Berkhin, Survey of Clustering Data Mining Techniques, http://www.accrue.com/products/researchpapers.html, 2002.
• 2: J. S. Breese et al, Empirical Analysis of Predictive Algorithms for Collaborative Filtering, Technical report, Microsoft Research, 1998.
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: Soumen Chakrabarti, Data mining for hypertext (tutorial session) (title only), Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.533, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347526]
• 5: Liren Chen , Katia Sycara, WebMate: a personal agent for browsing and searching, Proceedings of the second international conference on Autonomous agents, p.132-139, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280789]
• 6: D. Cohn & T. Hofman, The Missing Link - A Probabilistic Model of Document Content and Hypertext Connectivity, in Proc. Neural Information Processing Systems, 2001.
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: I. Dhillon et al, Efficient Clustering of Very Large Document Collections, In Data Mining for Scientific and Engineering Applications, Kluwer Academic Publishers, 2001.
• 9: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 10: J. Heer and E. H. Chi, Identification of Web User Traffic Composition Using Multi-Modal Clustering and Information Scent, in 1st SIAM ICDM, Workshop on Web Mining, Chicago, 2001.
• 11: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 12: Bing Liu , Yiyuan Xia , Philip S. Yu, Clustering through decision tree construction, Proceedings of the ninth international conference on Information and knowledge management, p.20-29, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354775]
• 13: J. Neville and D. Jensen, Iterative Classification in Relational Data, In Proc. AAAI-2000 Workshop on Learning Statistical Models from Relational Data, AAAI Press, 2000.
• 14: Seán Slattery , Mark Craven, Combining Statistical and Relational Methods for Learning in Hypertext Domains, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.38-52, July 22-24, 1998
• 15: M. Steinbach et al, A Comparison of Document Clustering Techniques, in 6th ACM SIGKDD, World Text Mining Conference, Boston, 2000.
• 16: Z. Su , Q. Yang , H. Zhang , X. Xu , Y. Hu, Correlation-based Document Clustering using Web Logs, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 5, p.5022, January 03-06, 2001
• 17: B. Taskar et al, Probabilistic Classification and Clustering in Relational Data, in Proc. of IJCAI-01, 17th International Joint Conference on Artificial Intelligence, 2001.
• 18: L. H. Ungar, D.P.Foster, Clustering Methods for Collaborative Filtering, In Workshop on Recommendation System at the 15th National Conference on Artificial Intelligence, 1998.
• 19: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 20: Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, A Unified Framework for Clustering Heterogeneous Web Objects, Proceedings of the 3rd International Conference on Web Information Systems Engineering, p.161-172, December 12-14, 2002
• 21: Open Directory Project, http://dmoz.org/

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Performance

Keywords:
clustering, interrelated, multi-type, reinforcement