Exploiting hierarchical domain structure to compute similarity

ABSTRACT

The notion of similarity between objects finds use in many contexts, for example, in search engines, collaborative filtering, and clustering. Objects being compared often are modeled as sets, with their similarity traditionally determined based on set intersection. Intersection-based measures do not accurately capture similarity in certain domains, such as when the data is sparse or when there are known relationships between items within sets. We propose new measures that exploit a hierarchical domain structure in order to produce more intuitive similarity scores. We extend our similarity measures to provide appropriate results in the presence of multisets (also handled unsatisfactorily by traditional measures), for example, to correctly compute the similarity between customers who buy several instances of the same product (say milk), or who buy several products in the same category (say dairy products). We also provide an experimental comparison of our measures against traditional similarity measures, and report on a user study that evaluated how well our measures match human intuition.

REFERENCES

• 1: Kurt D. Bollacker , Steve Lawrence , C. Lee Giles, CiteSeer: an autonous Web agent for automatic retrieval and identification of interesting publications, Proceedings of the second international conference on Autonomous agents, p.116-123, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280786]
• 2: Breese, J. S., Heckerman, D., and Kadie, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence.
• 3: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 4: Das, G., Mannila, H., and Ronkainen, P. 1998. Similarity of attributes by external probes. In Proceedings of Knowledge Discovery and Data Mining (KDD), 23--29.
• 5: de Buenaga Rodríguez, M., Gómez-Hidalgo, J. M., and Díaz-Agudo, B. 1997. Using WordNet to complement training information in text categorization. In Proceedings of the Second International Conference on Recent Advances in Natural Language Processing.
• 6: Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., and Harshman, R. 1990. Indexing by latent semantic indexing. J. Amer. Soc. Inf. Sci. 41, 6, 391--407.
• 7: Feldman, R. and Dagan, I. 1995. Knowledge discovery in textual databases. In Proceedings of KDD-95.
• 8: Ganesan, P., Garcia-Molina, H., and Widom, J. 2002. Exploiting hierarchical domain structure to compute similarity. Tech. Rep., Available at http://dbpubs.stanford.edu/pub/2001-27.
• 9: David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
• 10: Nathaniel Good , J. Ben Schafer , Joseph A. Konstan , Al Borchers , Badrul Sarwar , Jon Herlocker , John Riedl, Combining collaborative filtering with personal agents for better recommendations, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.439-446, July 18-22, 1999, Orlando, Florida, United States
• 11: Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995
• 12: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 13: Jeh, G. and Widom, J. 2001. Simrank: A measure of structural-context similarity. Tech. Rep. Stanford University. Available at http://dbpubs.stanford.edu/pub/2001-41.
• 14: Joshi, A. and Krishnapuram, R. 2000. On mining Web access logs. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 63--69.
• 15: Young Whan Kim , Jin H. Kim, A model of knowledge based information retrieval with hierarchical concept, Journal of Documentation, v.46 n.2, p.113-136, Jun. 1990 [doi>10.1108/eb026857]
• 16: Lee, J. and Kim, M. 1993. Information retrieval based on a conceptual distance in is-a heirarchy. J. Doc. 49, 2, 188--207.
• 17: Lustig, G. 1967. A new class of association factors in mechanized information storage, retrieval and dissemination. In F. I. D./I. F. I. P. Joint Conference (Rome).
• 18: McGill, M. J. 1983. Introduction to Modern Information Retrieval. McGraw-Hill, New York.
• 19: Melnik, S., Garcia-Molina, H., and Rahm, E. 2002. Similarity flooding: A versatile graph matching algorithm. In Proceedings of ICDE 2002.
• 20: Miller, G. R. B. Fellbaum, C., Gross, D., and Miller, K. 1990. Introduction to WordNet: An on-line lexical database. J. Lexicog. 3, 4, 234--244.
• 21: Nasraoui, O., Frigui, H., Joshi, A., and Krishnapuram, R. 1999. Mining Web access logs using relational competitive fuzzy clustering. In Proceedings of the Eighth International Fuzzy Systems Association World Congress---IFSA 99 (Taipei).
• 22: OPD. The Open Directory Project. Available at http://dmoz.org/.
• 23: Rada, R., Mili, H., Bicknell, E., and Blettner, M. 1989. Development and application of a metric on semantic nets. IEEE Trans. Syst. Man Cybern. 19, 1, 17--30.
• 24: Resnick, P. 1995. Using information content to evaluate semantic similarity in a taxonomy. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 448--453.
• 25: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 26: Richardson, R. and Smeaton, A. F. 1995. Using WordNet in a knowledge-based approach to information retrieval. In Proceedings of the Seventeenth BCS-IRSG Colloquium on Information Retrieval.
• 27: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover''s Distance as a Metric for Image Retrieval, Stanford University, Stanford, CA, 1998
• 28: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 29: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 30: Sankoff, D. and Kruskal, J. B. 1983. Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA.
• 31: Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. 2000. Application of dimensionality reduction in recommender system---a case study. In Proceedings of the ACM WebKDD 2000 Workshop.
• 32: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 33: Badrul M. Sarwar , Joseph A. Konstan , Al Borchers , Jon Herlocker , Brad Miller , John Riedl, Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.345-354, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.289509]
• 34: Scott, S. and Matwin, S. 1998. Text classification using WordNet hypernyms. In Proceedings of the Use of WordNet in Natural Language Processing Systems. Association for Computational Linguistics.
• 35: Shasha, D. and Zhang, K. 1997. Approximate tree pattern matching. In Pattern Matching Algorithms, Oxford University Press, New York.
• 36: Shivakumar, N. and Garcia-Molina, H. 1995. Scam: A copy detection mechanism for digital documents. In Proceedings of the Second International Conference in Theory and Practice of Digital Libraries.
• 37: Sibson, R. 1972. Order invariant methods for data analysis. J. Roy. Stat. Soc. 34, 3, 311--349.
• 38: Sneath, P. and Sokal, R. 1973. Numerical Taxonomy. W. H. Freeman, San Francisco.
• 39: Soergel, D. 1967. Mathematical analysis of documentation systems. An attempt at a theory of classification and search request formulation. Inf. Stor. Retrieval 3, 3, 129--173.
• 40: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 41: Strehl, A., Ghosh, J., and Mooney, R. 2000. Impact of similarity measures on Web-page clustering. In Proceedings of the AAAI Workshop on AI for Web Search.
• 42: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms

Keywords:
Similarity measures, collaborative filtering, data mining, hierarchy