users. For example, for 14,000 users the number of
comparisons was decreased by almost an order of
magnitude (by 87%). Other experiment shows that
the number of comparisons roughly remains
unchanged when K increases. This allows us to
increase the number of nearest neighbors to be
retrieved (and to improve the accuracy of the
prediction) with a very minor computational
overhead.
In the accuracy experiments we compare the
neighborhoods and the predictions found by CAN-
based KNN and by the traditional KNN. The found
neighborhoods are similar and the recommendations
are very close, which indicates on a high accuracy of
the proposed algorithm. In summary, comparing the
proposed heuristic KNN search with traditional
exhaustive search shows that our algorithm achieves
high accuracy (similar to the accuracy of the
traditional exhaustive search), while significantly
decreasing the required computational effort.
In this work, we assumed that user's ratings on
all the items are available. Thus, the mapping of the
ratings vectors to CAN space is straightforward.
However, this is unachievable in many real-life
scenarios, where an average user rates only a small
portion of the available items. In the future, we plan
to study CAN-based management of incomplete
vectors, where part of the ratings is missing. Using
statistical methods to complete the vectors through
predicting the missing ratings might be a promising
research direction.
In addition to decreasing the computational
effort, our algorithm can naturally be extended to
distribute it among multiple users. In traditional
implementations of the CF, the Similarity
Computation and the Neighborhood Formation
stages are performed in a single central location.
However, as the underlying CAN platform is
originally distributed Peer-to-Peer platform, it
inherently allows distributed and fully decentralized
storage of the ratings matrix. In future, we plan to
implement a distributed variant of the algorithm and
to investigate the distribution issues.
The current work is limited to the Mean Squared
Difference similarity metric, since the injective
mapping to a multi-dimensional CAN-like space
inherently supports it. However, for other metrics,
such as Cosine Similarity or Pearson correlation,
CAN space might be inappropriate and new types of
topologies and the respective mappings should be
developed. We plan to study other metrics and to
produce a general framework for efficient heuristic
Collaborative Filtering.
REFERENCES
Aguzzoli, S., Avesani, P., Massa, P., 1997, Collaborative
Case-Based Recommender System, in proceedings of
the ECCBR Conference.
Breese, J., Heckerman, D., Kadie, C., 1998, Empirical
Analysis of Predictive Algorithms for Collaborative
Filtering, in proceedings of the UAI Conference.
Chee, S.H.S., Han, J., Wang, K., 2001, RecTree: An
Efficient Collaborative Filtering Method, in
proceedings of the DaWaK Conference.
Goldberg, K., Roeder, T., Gupta, D., Perkins, C., 2001,
Eigentaste: A Constant Time Collaborative Filtering
Algorithm”, in Information Retrieval Journal, vol.
4(2).
Good N., Schafer, J.B., Konstan, J.A., Borchers A.,
Sarwar, B., Herlocker, J., Riedl, J., 1999, Combining
Collaborative Filtering with Personal Agents for
Better Recommendations, in proceedings of the AAAI
Conference.
Han, P., Xie, B., Yang, F., Shen, R., 2004, A Scalable P2P
Recommender System Based on Distributed
Collaborative Filtering, in Expert Systems with
Applications Journal, vol. 27(2).
Herlocker, J.L., Konstan, J.A., Borchers, A., Riedl, J.,
1999, An Algorithmic Framework for Performing
Collaborative Filtering, in proceedings of the SIGIR
Conference.
Miller, B.N., Konstan, J.A., Riedl, J., 2004, PocketLens:
Toward a Personal Recommender System, in ACM
Transactions on Information Systems, vol.22 (3).
Pennock, D.M., Horvitz, E., Giles, C.L., 2000, Social
Choice Theory and Recommender Systems: Analysis
of the Axiomatic Foundations of Collaborative
Filtering, in proceedings of the AAAI Conference.
Ratnasamy, S., Francis, P., Handley, M., Karp, R.,
Shenker, S., 2001, A Scalable Content-Addressable
Network, in proceedings of the SIGCOMM
Conference.
Resnick, P., Varian, H.R., 1997, Recommender Systems, in
Communications of the ACM, vol. 40(3).
Sarwar, B., Karypis, G., Konstan, J., Riedl, J., 2000,
Analysis of Recommendation Algorithms for E-
Commerce, in proceedings of the EC Conference.
Sarwar, B.M., Konstan, J.A., Riedl, J., 2001, Distributed
Recommender Systems: New Opportunities for
Internet Commerce, in “Internet Commerce and
Software Agents: Cases, Technologies and
Opportunities”, Idea Group Publishers.
Shardanand, U., Maes, P., 1995, Social Information
Filtering: Algorithms for Automating "Word of Mouth,
in proceedings of the CHI Conference.
Tveit, A., 2001, “Peer-to-Peer Based Recommendations
for Mobile Commerce”, in proceedings of the WMC
Workshop.
ICEIS 2006 - ARTIFICIAL INTELLIGENCE AND DECISION SUPPORT SYSTEMS
98