001/*-------------------------------------------------------------------------+
002|                                                                          |
003| Copyright 2005-2011 the ConQAT Project                                   |
004|                                                                          |
005| Licensed under the Apache License, Version 2.0 (the "License");          |
006| you may not use this file except in compliance with the License.         |
007| You may obtain a copy of the License at                                  |
008|                                                                          |
009|    http://www.apache.org/licenses/LICENSE-2.0                            |
010|                                                                          |
011| Unless required by applicable law or agreed to in writing, software      |
012| distributed under the License is distributed on an "AS IS" BASIS,        |
013| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
014| See the License for the specific language governing permissions and      |
015| limitations under the License.                                           |
016+-------------------------------------------------------------------------*/
017package org.conqat.lib.commons.datamining;
018
019import java.util.ArrayList;
020import java.util.Collections;
021import java.util.Comparator;
022import java.util.HashMap;
023import java.util.HashSet;
024import java.util.List;
025import java.util.Map;
026import java.util.Set;
027
028import org.conqat.lib.commons.collections.Pair;
029
030/**
031 * A user rating-based recommender using collaborative filtering.
032 */
033public class CFRatingRecommender<T> implements IRecommender<T> {
034
035        /** The database containing the ratings. */
036        private RecommenderRatingDatabase<T> ratingDatabase;
037        /** Number of neighbors to consider for computing recommendations */
038        private int numNeighbors;
039        /** Maximum number of recommendations */
040        private int maxRecommendations;
041
042        /** Constructor */
043        public CFRatingRecommender(RecommenderRatingDatabase<T> ratingDatabase, int numNeighbors, int maxRecommendations) {
044                this.ratingDatabase = ratingDatabase;
045                this.numNeighbors = numNeighbors;
046                this.maxRecommendations = maxRecommendations;
047        }
048
049        /** {@inheritDoc} */
050        @Override
051        public Set<Recommendation<T>> recommend(IRecommenderUser queryUser) {
052                Set<IRecommenderUser> users = ratingDatabase.getUsers();
053                List<Pair<Double, IRecommenderUser>> neighbors = new ArrayList<Pair<Double, IRecommenderUser>>();
054                for (IRecommenderUser user : users) {
055                        if (user.equals(queryUser)) {
056                                continue;
057                        }
058                        neighbors.add(new Pair<Double, IRecommenderUser>(user.similarity(queryUser), user));
059                }
060
061                Collections.sort(neighbors);
062                Collections.reverse(neighbors);
063
064                neighbors = neighbors.subList(0, numNeighbors);
065
066                Set<Recommendation<T>> result = new HashSet<Recommendation<T>>();
067                final Map<T, Double> recommendedItems = new HashMap<T, Double>();
068                double sumSimilarity = 0;
069
070                Set<T> userItems = ratingDatabase.getLikedItems(queryUser);
071                for (Pair<Double, IRecommenderUser> neighbor : neighbors) {
072                        sumSimilarity += neighbor.getFirst();
073                        Set<T> neighborItems = ratingDatabase.getLikedItems(neighbor.getSecond());
074                        for (T item : neighborItems) {
075                                if (!userItems.contains(item)) {
076                                        if (!recommendedItems.containsKey(item)) {
077                                                recommendedItems.put(item, 0d);
078                                        }
079                                        recommendedItems.put(item, recommendedItems.get(item) + neighbor.getFirst());
080                                }
081                        }
082                }
083
084                List<T> sortedItems = new ArrayList<T>(recommendedItems.keySet());
085                Collections.sort(sortedItems, new Comparator<T>() {
086                        @Override
087                        public int compare(T item1, T item2) {
088                                return recommendedItems.get(item2).compareTo(recommendedItems.get(item1));
089                        }
090                });
091
092                while (result.size() < maxRecommendations && !sortedItems.isEmpty()) {
093                        T item = sortedItems.get(0);
094                        double confidence = 0;
095                        if (sumSimilarity > 0) {
096                                confidence = recommendedItems.get(item) / sumSimilarity;
097                        }
098                        result.add(new Recommendation<T>(item, confidence));
099                        sortedItems.remove(0);
100                }
101
102                return result;
103
104        }
105
106}