Home | Browse | Search | Credits | About
Register | User Area | DL-Harvest | Help
DLIST

Applying Associative Retrieval Techniques to Alleviate the Sparsity Problem in Collaborative Filtering

Huang, Zan and Chen, Hsinchun and Zeng, Daniel (2004) Applying Associative Retrieval Techniques to Alleviate the Sparsity Problem in Collaborative Filtering. ACM Transactions on Information Systems 22(1):pp. 116-142.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Recommender systems are being widely applied in many application settings to suggest products, services, and information items to potential consumers. Collaborative filtering, the most successful recommendation approach, makes recommendations based on past transactions and feedback from consumers sharing similar interests. A major problem limiting the usefulness of collaborative filtering is the sparsity problem, which refers to a situation in which transactional or feedback data is sparse and insufficient to identify similarities in consumer interests. In this article, we propose to deal with this sparsity problem by applying an associative retrieval framework and related spreading activation algorithms to explore transitive associations among consumers through their past transactions and feedback. Such transitive associations are a valuable source of information to help infer consumer interests and can be explored to deal with the sparsity problem. To evaluate the effectiveness of our approach, we have conducted an experimental study using a data set from an online bookstore. We experimented with three spreading activation algorithms including a constrained Leaky Capacitor algorithm, a branch-and-bound serial symbolic search algorithm, and a Hopfield net parallel relaxation search algorithm. These algorithms were compared with several collaborative filtering approaches that do not consider the transitive associations: a simple graph search approach, two variations of the user-based approach, and an item-based approach. Our experimental results indicate that spreading activation-based approaches significantly outperformed the other collaborative filtering methods as measured by recommendation precision, recall, the F-measure, and the rank score.We also observed the over-activation effect of the spreading activation approach, that is, incorporating transitive associations with past transactional data that is not sparse may “dilute” the data used to infer user preferences and lead to degradation in recommendation performance.

EPrint Type:Journal Article (Paginated)
Keywords:National Science Digital Library, NSDL, Artificial Intelligence Lab, AI Lab, Collaborative Filtering
Subjects:Internet
World Wide Web
Informetrics
ID Code:429
Deposited On:16 August 2004
Alternative Locations:http://ai.bpa.arizona.edu/go/papers.html
Eprint Statistics:View statistics for this eprint
Tell A Colleague:Tell a colleague about it.

AGGARWAL, C. C., WOLF, J. L., WU, K.-L., AND YU, P. S. 1999. Horting hatches an egg: A new graphtheoretic

approach to collaborative filtering. In Proceedings of the 5th ACM SIGKDD Conferenceon Knowledge Discovery and Data Mining (KDD’99) (San Diego, Calif.). ACM, New York, 201–

212.

ALBERT, R. AND BARABASI, A.-L. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys.

74, 47–97.

ANDERSON, J. R. 1983. A spreading activation theory of memory. J. Verb. Learn. Verb. Behav. 22,

261–295.

BALABANOVIC, M. AND SHOHAM, Y. 1997. FAB: Content-based, collaborative recommendation. Commun.

ACM 40, 3, 66–72.

BASU, C., HIRSH, H., AND COHEN, W. 1998. Recommendation as classification: Using social and

content-based information in recommendation. In Proceedings of the 15th National Conference

on Artificial Intelligence, 714–720.

BILLSUS, D. AND PAZZANI, M. J. 1998. Learning collaborative information filters. In Proceedings of

the 15th International Conference on Machine Learning, 46–54.

BOLLEN, J., VANDESOMPEL, H., AND ROCHA, L. M. 1999. Mining associative relations from website

logs and their application to context-dependent retrieval using spreading activation. In Proceedings

of the Workshop on Organizing Web Space (WOWS). ACM Digital Libraries 99.

BREESE, J. S., HECKERMAN, D., AND KADIE, C. 1998. Empirical analysis of predictive algorithms

for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence

(Madison, Wisc.). Morgan-Kaufmann, Reading, Mass. 43–52.

BURKE, R. 2000. Semantic ratings and heuristic similarity for collaborative filtering. In Proceedings

of the 17th National Conference on Artificial Intelligence.

CHEN, H. AND DHAR, V. 1991. Cognitive process as a basis for intelligent retrieval systems design.

Information Processing and Management 27, 5, 405–432.

CHEN, H., LYNCH, K. J., BASU, K., AND NG, D. T. 1993. Generating, integrating, and activating

thesauri for concept-based document retrieval. IEEE Exp., Spec. Series Artif. Intell. Text-based

Inf. Systems 8, 2, 25–34.

CHEN, H. ANDNG,D. T. 1995. An algorithmic approach to concept exploration in a large knowledge

network (automatic thesaurus consultation): Symbolic branch-and-bound search vs. Connectionist

Hopfield net activation. J. ASIS 46, 5, 348–369.

CLAYPOOL, M., GOKHALE, A., MIRANDA, T., MURNIKOV, P., NETES, D., AND SARTIN, M. 1999. Combining

content-based and collaborative filters in an online newspaper. In Proceedings of the ACMSIGIR

Workshop on Recommender Systems. ACM, New York.

COHEN, P. R. AND KJELDSEN, R. 1987. Information retrieval by constrained spreading activation

in semantic networks. Information Processing and Management 23, 4, 255–268.

COLLINS, A. M. AND LOFTUS, E. F. 1975. A spreading activation theory of semantic processing.

Psych. Rev. 82, 6, 407–428.

CONDLIFF,M. K., LEWIS, D. D.,MADIGAN, D., AND POSSE, C. 1999. Bayesian mixed-effects models for

recommender systems. In Proceedings of the ACM SIGIR Workshop on Recommender Systems.

ACM, New York.

CRESTANI, F. AND LEE, P. L. 2000. Searching the web by constrained spreading activation. Inf.

Proc. Manage. 36, 585–605.

CROUCH, C. AND YANG, B. 1992. Experiments in automatic statistical thesaurus construction. In

Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development

in Information Retrieval, (Copenhagen, Denmark). ACM, New York, 77–88.

GOLDBERG, K., ROEDER, T., GUPTA, D., AND PERKINS, C. 2001. Eigentaste: A constant time collaborative

filtering algorithm. Inf. Ret. 4, 2, 133–151.

GOOD, N., SCHAFER, J., KONSTAN, J., BORCHERS, A., SARWAR, B., HERLOCKER, J., AND RIEDL, J. 1999.

Combining collaborative filtering with personal agents for better recommendations. In Proceedings

of the 16th National Conference on Artificial Intelligence, 439–446.

GORDON, M. 1988. Probabilistic and genetic algorithm for document retrieval. Commun. ACM

31, 10, 1208–1218.

HILL, W., STEAD, L., ROSENSTEIN, M., AND FURNAS, G. 1995. Recommending and evaluating choices

in a virtual community of use. In Proceedings of the ACM CHI’95 Conference on Human Factors

in Computing Systems. ACM, New York, 194–201.

HUANG, Z., CHUNG, W., AND CHEN, H. 2003. A graph model for e-commerce recommender systems.

J. ASIST, in press.

HUANG, Z., CHUNG, W., ONG, T.-H., AND CHEN, H. 2002. A graph-based recommender system for

digital library. In Proceedings of the 2nd ACM/IEEE-CS Joint Conference on Digital Libraries

(Portland, Ore.). ACM, New York, 65–73.

JUNG, G. AND RAGHAVAN, V. 1990. Connectionist learning in constructing thesaurus-like knowledge

structure. In Proceedings of the AAAI Spring Symposium on Text-based Intelligent Systems.

KARYPIS, G. 2001. Evaluation of item-based top-n recommendation algorithms. In Proceedings of

the 10th International Conference on Information and Knowledge Management (CIKM) (Atlanta,

Ga.).

KNIGHT, K. 1990. Connectionist ideas and algorithms. Commun. ACM 33, 11, 59–74.

KONSTAN, J. A.,MILLER, B.N.,MALTZ,D.,HERLOCKER, J. L.,GORDON, L. R., AND RIEDL, J. 1997. Group-

Lens: Applying collaborative filtering to Usenet news. Commun. ACM 40, 3, 77–87.

LIN, W., ALVAREZ, S. A., AND RUIZ, C. 2002. Efficient adaptive-support association rule mining for

recommender systems. Data Mining Knowl. Disc. 6, 1, 83–105.

MIRZA, B. J. 2001. Jumping connections: A graph-theoretic model for recommender systems.

Computer Science Department, Virginia Polytechnic Institute and state university,

(http://scholar.lib.vt.edu/theses/available/etd-02282001-175040/unrestricted/etd.pdf).

MIRZA, B. J., KELLER, B. J., AND RAMAKRISHNAN, N. 2003. Studying recommendation algorithms by

graph analysis. J. Intel. Inf. Syst. 20, 2, 131–160.

MOBASHER, B. H., DAI, T. L., NAKAGAWA, M., SUN, Y., ANDWILTSHIRE, J. 2000. Discovery of aggregate

usage profiles for web personalization. In Proceedings of the Workshop on Web Mining for ECommerce—

Challenges and Opportunities.

NASRAOUI, O., FRIGUI, H., JOSHI, A., AND KRISHNAPURAM, R. 1999. Mining web access logs using

relational competitive fuzzy clustering. In Proceedings of the 8th International Fuzzy Systems

Association World Congress—IFSA 99.

PAZZANI,M. 1999. A framework for collaborative, content-based and demographic filtering. Artif.

Intel. Rev. 13, 5–6, 393–408.

PAZZANI, M. AND BILLSUS, D. 1997. Learning and revising user profiles: The identification of interesting

web sites. Mach. Learn. 27, 3, 313–331.

PIROLLI, P., PITKOW, J., AND RAO, R. 1996. Silk from a sow’s ear: Extracting usable structures from

the web. In Proceedings of the ACMCHI 96 Conference on Human Factors in Computing Systems.

118–125.

RESNICK, P., IACOVOU, N., SUCHAK, M., BERGSTROM, P., AND RIEDL, J. 1994. GroupLens: An open architecture

for collaborative filtering of NetNews. In Proceedings of the ACMCSCW’94 Conference

on Computer-Supported Cooperative Work. ACM, New York, 175–186.

SALTON, G. AND BUCKLEY, C. 1988. On the use of spreading activation methods in automatic information.

In Proceedings of the 11th ACM SIGIR International Conference on Research and

Development in Information Retrieval. ACM, New York, 147–160.

SARWAR, B., KARYPIS, G., KONSTAN, J., AND REIDL, J. 2000a. Analysis of recommendation algorithms

for e-commerce. In Proceedings of the ACMConference on Electronic Commerce. ACM, New York,

158–167.

SARWAR, B., KARYPIS, G., KONSTAN, J., AND RIEDL, J. 2000b. Application of dimensionality reduction

in recommender systems: A case study. In Proceedings of the WebKDD Workshop at the ACM

SIGKKD. ACM, New York.

SARWAR, B.,KONSTAN, J., BORCHERS, A.,HERLOCKER, J.,MILLER, B., AND RIEDL, J. 1998. Using filtering

agents to improve prediction quality in the GroupLens research collaborative filtering system.

In Proceedings of the ACM Conference on Computer Supported Cooperative Work (CSCW). ACM,

New York, 345–354.

SARWAR, B. M., KARYPIS, G., KONSTAN, J. A., AND RIEDL, J. T. 2001. Item-based collaborative filtering

recommendation algorithms. In Proceedings of the 10th InternationalWorldWideWeb Conference.

285–295.

SCHAFER, J., KONSTAN, J., AND RIEDL, J. 2001. E-commerce recommendation applications. Data

Min. Knowl. Disc. 5, 1–2, 115–153.

SCHEIN, A. I., POPESCUL, A., UNGER, L. H., AND PENNOCK, D.M. 2002. Methods and metrics for coldstart

recommendations. In Proceedings of the 25th Annual International ACMSIGIR Conference

on Research and Development in Information Retrieval (SIGIR 2002). (Tampere, Finland), 253–

260.

SHARDANAND, U. ANDMAES, P. 1995. Social information filtering: Algorithms for automating “word

of mouth”. In Proceedings of the ACM CHI’95 Conference on Human Factors in Computing Systems.

ACM, New York, 210–217.

SOBOROFF, I. AND NICHOLAS, C. 2000. Collaborative filtering and the generalized vector space

model. In Proceedings of the 23rd Annual International Conference on Research and Development

in Information Retrieval (Athens, Greece). 351–353.

TERVEEN, L., HILL, W., AMENTO, B., MCDONALD, D., AND CRETER, J. 1997. PHOAKS: A system for

sharing recommendations. Commun. ACM 40, 3, 59–62.

WONG, S. K. M., ZIARKO, W., AND WONG, P. C. N. 1985. Generalized vector spaces model in information

retrieval. In Proceedings of the 8th Annual International ACM SIGIR Conference on

Research and Development in Information Retrieval. ACM, New York, 18–25.

EPrints dLIST, an open access archive for the Information Sciences, is supported by the School of Information Resources and Library Science and Learning Technologies Center, University of Arizona. Established in 2002, dLIST has a global Advisory Board and is a part of the Information Technology & Society Research Lab. Open Archives
Contact: Admin | Donate