You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by ro...@apache.org on 2010/02/13 21:54:31 UTC
svn commit: r909912 [7/10] - in
/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste: common/
eval/ hadoop/ hadoop/cooccurence/ hadoop/item/ hadoop/pseudo/
hadoop/slopeone/ impl/common/ impl/common/jdbc/ impl/eval/ impl/model/
impl/model/...
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemAverageRecommender.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemAverageRecommender.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemAverageRecommender.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemAverageRecommender.java Sat Feb 13 20:54:05 2010
@@ -17,6 +17,12 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.Collection;
+import java.util.List;
+import java.util.concurrent.Callable;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
import org.apache.mahout.cf.taste.common.NoSuchUserException;
import org.apache.mahout.cf.taste.common.Refreshable;
import org.apache.mahout.cf.taste.common.TasteException;
@@ -33,27 +39,22 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.Collection;
-import java.util.List;
-import java.util.concurrent.Callable;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
-
/**
- * <p>A simple recommender that always estimates preference for an item to be the average of all known
- * preference values for that item. No information about users is taken into account. This
- * implementation is provided for experimentation; while simple and fast, it may not produce very good
- * recommendations.</p>
+ * <p>
+ * A simple recommender that always estimates preference for an item to be the average of all known preference
+ * values for that item. No information about users is taken into account. This implementation is provided for
+ * experimentation; while simple and fast, it may not produce very good recommendations.
+ * </p>
*/
public final class ItemAverageRecommender extends AbstractRecommender {
-
+
private static final Logger log = LoggerFactory.getLogger(ItemAverageRecommender.class);
-
+
private final FastByIDMap<RunningAverage> itemAverages;
private boolean averagesBuilt;
private final ReadWriteLock buildAveragesLock;
private final RefreshHelper refreshHelper;
-
+
public ItemAverageRecommender(DataModel dataModel) {
super(dataModel);
this.itemAverages = new FastByIDMap<RunningAverage>();
@@ -67,26 +68,26 @@
});
refreshHelper.addDependency(dataModel);
}
-
+
@Override
- public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer)
- throws TasteException {
+ public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException {
if (howMany < 1) {
throw new IllegalArgumentException("howMany must be at least 1");
}
- log.debug("Recommending items for user ID '{}'", userID);
+ ItemAverageRecommender.log.debug("Recommending items for user ID '{}'", userID);
checkAverageDiffsBuilt();
-
+
FastIDSet possibleItemIDs = getAllOtherItems(userID);
-
+
TopItems.Estimator<Long> estimator = new Estimator();
-
- List<RecommendedItem> topItems = TopItems.getTopItems(howMany, possibleItemIDs.iterator(), rescorer, estimator);
-
- log.debug("Recommendations are: {}", topItems);
+
+ List<RecommendedItem> topItems = TopItems.getTopItems(howMany, possibleItemIDs.iterator(), rescorer,
+ estimator);
+
+ ItemAverageRecommender.log.debug("Recommendations are: {}", topItems);
return topItems;
}
-
+
@Override
public float estimatePreference(long userID, long itemID) throws TasteException {
DataModel dataModel = getDataModel();
@@ -97,7 +98,7 @@
checkAverageDiffsBuilt();
return doEstimatePreference(itemID);
}
-
+
private float doEstimatePreference(long itemID) {
buildAveragesLock.readLock().lock();
try {
@@ -107,13 +108,13 @@
buildAveragesLock.readLock().unlock();
}
}
-
+
private void checkAverageDiffsBuilt() throws TasteException {
if (!averagesBuilt) {
buildAverageDiffs();
}
}
-
+
private void buildAverageDiffs() throws TasteException {
try {
buildAveragesLock.writeLock().lock();
@@ -137,7 +138,7 @@
buildAveragesLock.writeLock().unlock();
}
}
-
+
@Override
public void setPreference(long userID, long itemID, float value) throws TasteException {
DataModel dataModel = getDataModel();
@@ -163,7 +164,7 @@
buildAveragesLock.writeLock().unlock();
}
}
-
+
@Override
public void removePreference(long userID, long itemID) throws TasteException {
DataModel dataModel = getDataModel();
@@ -183,23 +184,23 @@
}
}
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
refreshHelper.refresh(alreadyRefreshed);
}
-
+
@Override
public String toString() {
return "ItemAverageRecommender";
}
-
+
private final class Estimator implements TopItems.Estimator<Long> {
-
+
@Override
public double estimate(Long itemID) {
return doEstimatePreference(itemID);
}
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemUserAverageRecommender.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemUserAverageRecommender.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemUserAverageRecommender.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/ItemUserAverageRecommender.java Sat Feb 13 20:54:05 2010
@@ -17,6 +17,12 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.Collection;
+import java.util.List;
+import java.util.concurrent.Callable;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
import org.apache.mahout.cf.taste.common.NoSuchUserException;
import org.apache.mahout.cf.taste.common.Refreshable;
import org.apache.mahout.cf.taste.common.TasteException;
@@ -33,29 +39,25 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.Collection;
-import java.util.List;
-import java.util.concurrent.Callable;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
-
/**
- * <p>Like {@link ItemAverageRecommender}, except that estimated preferences are adjusted for the users' average
- * preference value. For example, say user X has not rated item Y. Item Y's average preference value is 3.5. User X's
- * average preference value is 4.2, and the average over all preference values is 4.0. User X prefers items 0.2 higher
- * on average, so, the estimated preference for user X, item Y is 3.5 + 0.2 = 3.7.</p>
+ * <p>
+ * Like {@link ItemAverageRecommender}, except that estimated preferences are adjusted for the users' average
+ * preference value. For example, say user X has not rated item Y. Item Y's average preference value is 3.5.
+ * User X's average preference value is 4.2, and the average over all preference values is 4.0. User X prefers
+ * items 0.2 higher on average, so, the estimated preference for user X, item Y is 3.5 + 0.2 = 3.7.
+ * </p>
*/
public final class ItemUserAverageRecommender extends AbstractRecommender {
-
+
private static final Logger log = LoggerFactory.getLogger(ItemUserAverageRecommender.class);
-
+
private final FastByIDMap<RunningAverage> itemAverages;
private final FastByIDMap<RunningAverage> userAverages;
private final RunningAverage overallAveragePrefValue;
private boolean averagesBuilt;
private final ReadWriteLock buildAveragesLock;
private final RefreshHelper refreshHelper;
-
+
public ItemUserAverageRecommender(DataModel dataModel) {
super(dataModel);
this.itemAverages = new FastByIDMap<RunningAverage>();
@@ -71,26 +73,26 @@
});
refreshHelper.addDependency(dataModel);
}
-
+
@Override
- public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer)
- throws TasteException {
+ public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException {
if (howMany < 1) {
throw new IllegalArgumentException("howMany must be at least 1");
}
- log.debug("Recommending items for user ID '{}'", userID);
+ ItemUserAverageRecommender.log.debug("Recommending items for user ID '{}'", userID);
checkAverageDiffsBuilt();
-
+
FastIDSet possibleItemIDs = getAllOtherItems(userID);
-
+
TopItems.Estimator<Long> estimator = new Estimator(userID);
-
- List<RecommendedItem> topItems = TopItems.getTopItems(howMany, possibleItemIDs.iterator(), rescorer, estimator);
-
- log.debug("Recommendations are: {}", topItems);
+
+ List<RecommendedItem> topItems = TopItems.getTopItems(howMany, possibleItemIDs.iterator(), rescorer,
+ estimator);
+
+ ItemUserAverageRecommender.log.debug("Recommendations are: {}", topItems);
return topItems;
}
-
+
@Override
public float estimatePreference(long userID, long itemID) throws TasteException {
DataModel dataModel = getDataModel();
@@ -101,7 +103,7 @@
checkAverageDiffsBuilt();
return doEstimatePreference(userID, itemID);
}
-
+
private float doEstimatePreference(long userID, long itemID) {
buildAveragesLock.readLock().lock();
try {
@@ -119,13 +121,13 @@
buildAveragesLock.readLock().unlock();
}
}
-
+
private void checkAverageDiffsBuilt() throws TasteException {
if (!averagesBuilt) {
buildAverageDiffs();
}
}
-
+
private void buildAverageDiffs() throws TasteException {
try {
buildAveragesLock.writeLock().lock();
@@ -138,8 +140,8 @@
for (int i = 0; i < size; i++) {
long itemID = prefs.getItemID(i);
float value = prefs.getValue(i);
- addDatumAndCreateIfNeeded(itemID, value, itemAverages);
- addDatumAndCreateIfNeeded(userID, value, userAverages);
+ ItemUserAverageRecommender.addDatumAndCreateIfNeeded(itemID, value, itemAverages);
+ ItemUserAverageRecommender.addDatumAndCreateIfNeeded(userID, value, userAverages);
overallAveragePrefValue.addDatum(value);
}
}
@@ -148,10 +150,8 @@
buildAveragesLock.writeLock().unlock();
}
}
-
- private static void addDatumAndCreateIfNeeded(long itemID,
- float value,
- FastByIDMap<RunningAverage> averages) {
+
+ private static void addDatumAndCreateIfNeeded(long itemID, float value, FastByIDMap<RunningAverage> averages) {
RunningAverage itemAverage = averages.get(itemID);
if (itemAverage == null) {
itemAverage = new FullRunningAverage();
@@ -159,7 +159,7 @@
}
itemAverage.addDatum(value);
}
-
+
@Override
public void setPreference(long userID, long itemID, float value) throws TasteException {
DataModel dataModel = getDataModel();
@@ -194,7 +194,7 @@
buildAveragesLock.writeLock().unlock();
}
}
-
+
@Override
public void removePreference(long userID, long itemID) throws TasteException {
DataModel dataModel = getDataModel();
@@ -219,29 +219,29 @@
}
}
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
refreshHelper.refresh(alreadyRefreshed);
}
-
+
@Override
public String toString() {
return "ItemUserAverageRecommender";
}
-
+
private final class Estimator implements TopItems.Estimator<Long> {
-
+
private final long userID;
-
+
private Estimator(long userID) {
this.userID = userID;
}
-
+
@Override
public double estimate(Long itemID) {
return doEstimatePreference(userID, itemID);
}
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NearestNeighborClusterSimilarity.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NearestNeighborClusterSimilarity.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NearestNeighborClusterSimilarity.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NearestNeighborClusterSimilarity.java Sat Feb 13 20:54:05 2010
@@ -17,6 +17,8 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.Collection;
+
import org.apache.mahout.cf.taste.common.Refreshable;
import org.apache.mahout.cf.taste.common.TasteException;
import org.apache.mahout.cf.taste.impl.common.FastIDSet;
@@ -25,48 +27,53 @@
import org.apache.mahout.cf.taste.impl.common.SamplingLongPrimitiveIterator;
import org.apache.mahout.cf.taste.similarity.UserSimilarity;
-import java.util.Collection;
-
/**
- * <p>Defines cluster similarity as the <em>largest</em> similarity between any two users in the clusters --
- * that is, it says that clusters are close when <em>some pair</em> of their members has high similarity.</p>
+ * <p>
+ * Defines cluster similarity as the <em>largest</em> similarity between any two users in the clusters -- that
+ * is, it says that clusters are close when <em>some pair</em> of their members has high similarity.
+ * </p>
*/
public final class NearestNeighborClusterSimilarity implements ClusterSimilarity {
-
+
private final UserSimilarity similarity;
private final double samplingRate;
-
+
/**
- * <p>Constructs a {@link NearestNeighborClusterSimilarity} based on the given {@link UserSimilarity}. All user-user
- * similarities are examined.</p>
+ * <p>
+ * Constructs a {@link NearestNeighborClusterSimilarity} based on the given {@link UserSimilarity}. All
+ * user-user similarities are examined.
+ * </p>
*/
public NearestNeighborClusterSimilarity(UserSimilarity similarity) {
this(similarity, 1.0);
}
-
+
/**
- * <p>Constructs a {@link NearestNeighborClusterSimilarity} based on the given {@link UserSimilarity}. By setting
- * <code>samplingRate</code> to a value less than 1.0, this implementation will only examine that fraction of all
- * user-user similarities between two clusters, increasing performance at the expense of accuracy.</p>
+ * <p>
+ * Constructs a {@link NearestNeighborClusterSimilarity} based on the given {@link UserSimilarity}. By
+ * setting <code>samplingRate</code> to a value less than 1.0, this implementation will only examine that
+ * fraction of all user-user similarities between two clusters, increasing performance at the expense of
+ * accuracy.
+ * </p>
*/
public NearestNeighborClusterSimilarity(UserSimilarity similarity, double samplingRate) {
if (similarity == null) {
throw new IllegalArgumentException("similarity is null");
}
- if (Double.isNaN(samplingRate) || samplingRate <= 0.0 || samplingRate > 1.0) {
+ if (Double.isNaN(samplingRate) || (samplingRate <= 0.0) || (samplingRate > 1.0)) {
throw new IllegalArgumentException("samplingRate is invalid: " + samplingRate);
}
this.similarity = similarity;
this.samplingRate = samplingRate;
}
-
+
@Override
public double getSimilarity(FastIDSet cluster1, FastIDSet cluster2) throws TasteException {
if (cluster1.isEmpty() || cluster2.isEmpty()) {
return Double.NaN;
}
- LongPrimitiveIterator someUsers =
- SamplingLongPrimitiveIterator.maybeWrapIterator(cluster1.iterator(), samplingRate);
+ LongPrimitiveIterator someUsers = SamplingLongPrimitiveIterator.maybeWrapIterator(cluster1.iterator(),
+ samplingRate);
double greatestSimilarity = Double.NEGATIVE_INFINITY;
while (someUsers.hasNext()) {
long userID1 = someUsers.next();
@@ -84,16 +91,16 @@
}
return greatestSimilarity;
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
alreadyRefreshed = RefreshHelper.buildRefreshed(alreadyRefreshed);
RefreshHelper.maybeRefresh(alreadyRefreshed, similarity);
}
-
+
@Override
public String toString() {
return "NearestNeighborClusterSimilarity[similarity:" + similarity + ']';
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NullRescorer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NullRescorer.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NullRescorer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/NullRescorer.java Sat Feb 13 20:54:05 2010
@@ -18,64 +18,70 @@
package org.apache.mahout.cf.taste.impl.recommender;
import org.apache.mahout.cf.taste.recommender.IDRescorer;
-import org.apache.mahout.common.LongPair;
import org.apache.mahout.cf.taste.recommender.Rescorer;
+import org.apache.mahout.common.LongPair;
-/** <p>A simple {@link Rescorer} which always returns the original score.</p> */
+/**
+ * <p>
+ * A simple {@link Rescorer} which always returns the original score.
+ * </p>
+ */
public final class NullRescorer<T> implements Rescorer<T>, IDRescorer {
-
+
private static final IDRescorer userOrItemInstance = new NullRescorer<Long>();
private static final Rescorer<LongPair> itemItemPairInstance = new NullRescorer<LongPair>();
private static final Rescorer<LongPair> userUserPairInstance = new NullRescorer<LongPair>();
-
+
public static IDRescorer getItemInstance() {
- return userOrItemInstance;
+ return NullRescorer.userOrItemInstance;
}
-
+
public static IDRescorer getUserInstance() {
- return userOrItemInstance;
+ return NullRescorer.userOrItemInstance;
}
-
+
public static Rescorer<LongPair> getItemItemPairInstance() {
- return itemItemPairInstance;
+ return NullRescorer.itemItemPairInstance;
}
-
+
public static Rescorer<LongPair> getUserUserPairInstance() {
- return userUserPairInstance;
+ return NullRescorer.userUserPairInstance;
}
-
+
private NullRescorer() {
- // do nothing
+ // do nothing
}
-
+
/**
- * @param thing to rescore
- * @param originalScore current score for item
+ * @param thing
+ * to rescore
+ * @param originalScore
+ * current score for item
* @return same originalScore as new score, always
*/
@Override
public double rescore(T thing, double originalScore) {
return originalScore;
}
-
+
@Override
public boolean isFiltered(T thing) {
return false;
}
-
+
@Override
public double rescore(long ID, double originalScore) {
return originalScore;
}
-
+
@Override
public boolean isFiltered(long ID) {
return false;
}
-
+
@Override
public String toString() {
return "NullRescorer";
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/RandomRecommender.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/RandomRecommender.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/RandomRecommender.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/RandomRecommender.java Sat Feb 13 20:54:05 2010
@@ -17,30 +17,30 @@
package org.apache.mahout.cf.taste.impl.recommender;
-import org.apache.mahout.cf.taste.recommender.IDRescorer;
-import org.apache.mahout.cf.taste.recommender.RecommendedItem;
-import org.apache.mahout.cf.taste.common.TasteException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Random;
+
import org.apache.mahout.cf.taste.common.Refreshable;
+import org.apache.mahout.cf.taste.common.TasteException;
+import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.model.PreferenceArray;
-import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator;
+import org.apache.mahout.cf.taste.recommender.IDRescorer;
+import org.apache.mahout.cf.taste.recommender.RecommendedItem;
import org.apache.mahout.common.RandomUtils;
-import java.util.List;
-import java.util.Collection;
-import java.util.Random;
-import java.util.ArrayList;
-
/**
- * Produces random recommendations and preference estimates. This is likely only useful as
- * a novelty and for benchmarking.
+ * Produces random recommendations and preference estimates. This is likely only useful as a novelty and for
+ * benchmarking.
*/
public final class RandomRecommender extends AbstractRecommender {
-
+
private final Random random = RandomUtils.getRandom();
private final float minPref;
private final float maxPref;
-
+
public RandomRecommender(DataModel dataModel) throws TasteException {
super(dataModel);
float maxPref = Float.NEGATIVE_INFINITY;
@@ -62,7 +62,7 @@
this.minPref = minPref;
this.maxPref = maxPref;
}
-
+
@Override
public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException {
DataModel dataModel = getDataModel();
@@ -78,19 +78,19 @@
}
return result;
}
-
+
@Override
public float estimatePreference(long userID, long itemID) {
return randomPref();
}
-
+
private float randomPref() {
return minPref + random.nextFloat() * (maxPref - minPref);
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
getDataModel().refresh(alreadyRefreshed);
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/SimilarUser.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/SimilarUser.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/SimilarUser.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/SimilarUser.java Sat Feb 13 20:54:05 2010
@@ -21,47 +21,47 @@
/** Simply encapsulates a user and a similarity value. */
public final class SimilarUser implements Comparable<SimilarUser> {
-
+
private final long userID;
private final double similarity;
-
+
public SimilarUser(long userID, double similarity) {
this.userID = userID;
this.similarity = similarity;
}
-
+
long getUserID() {
return userID;
}
-
+
double getSimilarity() {
return similarity;
}
-
+
@Override
public int hashCode() {
return (int) userID ^ RandomUtils.hashDouble(similarity);
}
-
+
@Override
public boolean equals(Object o) {
if (!(o instanceof SimilarUser)) {
return false;
}
SimilarUser other = (SimilarUser) o;
- return userID == other.getUserID() && similarity == other.getSimilarity();
+ return (userID == other.getUserID()) && (similarity == other.getSimilarity());
}
-
+
@Override
public String toString() {
return "SimilarUser[user:" + userID + ", similarity:" + similarity + ']';
}
-
+
/** Defines an ordering from most similar to least similar. */
@Override
public int compareTo(SimilarUser other) {
double otherSimilarity = other.getSimilarity();
return similarity > otherSimilarity ? -1 : similarity < otherSimilarity ? 1 : 0;
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TopItems.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TopItems.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TopItems.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TopItems.java Sat Feb 13 20:54:05 2010
@@ -17,6 +17,12 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.Queue;
+
import org.apache.mahout.cf.taste.common.NoSuchItemException;
import org.apache.mahout.cf.taste.common.NoSuchUserException;
import org.apache.mahout.cf.taste.common.TasteException;
@@ -26,33 +32,31 @@
import org.apache.mahout.cf.taste.recommender.IDRescorer;
import org.apache.mahout.cf.taste.recommender.RecommendedItem;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-import java.util.PriorityQueue;
-import java.util.Queue;
-
-/** <p>A simple class that refactors the "find top N things" logic that is used in several places.</p> */
+/**
+ * <p>
+ * A simple class that refactors the "find top N things" logic that is used in several places.
+ * </p>
+ */
public final class TopItems {
-
+
private static final long[] NO_IDS = new long[0];
-
- private TopItems() {
- }
-
+
+ private TopItems() { }
+
public static List<RecommendedItem> getTopItems(int howMany,
LongPrimitiveIterator possibleItemIDs,
IDRescorer rescorer,
Estimator<Long> estimator) throws TasteException {
- if (possibleItemIDs == null || estimator == null) {
+ if ((possibleItemIDs == null) || (estimator == null)) {
throw new IllegalArgumentException("argument is null");
}
- Queue<RecommendedItem> topItems = new PriorityQueue<RecommendedItem>(howMany + 1, Collections.reverseOrder());
+ Queue<RecommendedItem> topItems = new PriorityQueue<RecommendedItem>(howMany + 1, Collections
+ .reverseOrder());
boolean full = false;
double lowestTopValue = Double.NEGATIVE_INFINITY;
while (possibleItemIDs.hasNext()) {
long itemID = possibleItemIDs.next();
- if (rescorer == null || !rescorer.isFiltered(itemID)) {
+ if ((rescorer == null) || !rescorer.isFiltered(itemID)) {
double preference;
try {
preference = estimator.estimate(itemID);
@@ -60,7 +64,7 @@
continue;
}
double rescoredPref = rescorer == null ? preference : rescorer.rescore(itemID, preference);
- if (!Double.isNaN(rescoredPref) && (!full || rescoredPref > lowestTopValue)) {
+ if (!Double.isNaN(rescoredPref) && (!full || (rescoredPref > lowestTopValue))) {
topItems.add(new GenericRecommendedItem(itemID, (float) rescoredPref));
if (full) {
topItems.poll();
@@ -77,7 +81,7 @@
Collections.sort(result);
return result;
}
-
+
public static long[] getTopUsers(int howMany,
LongPrimitiveIterator allUserIDs,
IDRescorer rescorer,
@@ -87,7 +91,7 @@
double lowestTopValue = Double.NEGATIVE_INFINITY;
while (allUserIDs.hasNext()) {
long userID = allUserIDs.next();
- if (rescorer != null && rescorer.isFiltered(userID)) {
+ if ((rescorer != null) && rescorer.isFiltered(userID)) {
continue;
}
double similarity;
@@ -97,7 +101,7 @@
continue;
}
double rescoredSimilarity = rescorer == null ? similarity : rescorer.rescore(userID, similarity);
- if (!Double.isNaN(rescoredSimilarity) && (!full || rescoredSimilarity > lowestTopValue)) {
+ if (!Double.isNaN(rescoredSimilarity) && (!full || (rescoredSimilarity > lowestTopValue))) {
topUsers.add(new SimilarUser(userID, similarity));
if (full) {
topUsers.poll();
@@ -109,7 +113,7 @@
}
}
if (topUsers.isEmpty()) {
- return NO_IDS;
+ return TopItems.NO_IDS;
}
List<SimilarUser> sorted = new ArrayList<SimilarUser>(topUsers.size());
sorted.addAll(topUsers);
@@ -121,23 +125,25 @@
}
return result;
}
-
+
/**
- * <p>Thanks to tsmorton for suggesting this functionality and writing part of the code.</p>
- *
+ * <p>
+ * Thanks to tsmorton for suggesting this functionality and writing part of the code.
+ * </p>
+ *
* @see GenericItemSimilarity#GenericItemSimilarity(Iterable, int)
* @see GenericItemSimilarity#GenericItemSimilarity(org.apache.mahout.cf.taste.similarity.ItemSimilarity,
* org.apache.mahout.cf.taste.model.DataModel, int)
*/
- public static List<GenericItemSimilarity.ItemItemSimilarity> getTopItemItemSimilarities(
- int howMany, Iterable<GenericItemSimilarity.ItemItemSimilarity> allSimilarities) {
- Queue<GenericItemSimilarity.ItemItemSimilarity> topSimilarities =
- new PriorityQueue<GenericItemSimilarity.ItemItemSimilarity>(howMany + 1, Collections.reverseOrder());
+ public static List<GenericItemSimilarity.ItemItemSimilarity> getTopItemItemSimilarities(int howMany,
+ Iterable<GenericItemSimilarity.ItemItemSimilarity> allSimilarities) {
+ Queue<GenericItemSimilarity.ItemItemSimilarity> topSimilarities = new PriorityQueue<GenericItemSimilarity.ItemItemSimilarity>(
+ howMany + 1, Collections.reverseOrder());
boolean full = false;
double lowestTopValue = Double.NEGATIVE_INFINITY;
for (GenericItemSimilarity.ItemItemSimilarity similarity : allSimilarities) {
double value = similarity.getValue();
- if (!Double.isNaN(value) && (!full || value > lowestTopValue)) {
+ if (!Double.isNaN(value) && (!full || (value > lowestTopValue))) {
topSimilarities.add(similarity);
if (full) {
topSimilarities.poll();
@@ -148,22 +154,22 @@
lowestTopValue = topSimilarities.peek().getValue();
}
}
- List<GenericItemSimilarity.ItemItemSimilarity> result =
- new ArrayList<GenericItemSimilarity.ItemItemSimilarity>(topSimilarities.size());
+ List<GenericItemSimilarity.ItemItemSimilarity> result = new ArrayList<GenericItemSimilarity.ItemItemSimilarity>(
+ topSimilarities.size());
result.addAll(topSimilarities);
Collections.sort(result);
return result;
}
-
- public static List<GenericUserSimilarity.UserUserSimilarity> getTopUserUserSimilarities(
- int howMany, Iterable<GenericUserSimilarity.UserUserSimilarity> allSimilarities) {
- Queue<GenericUserSimilarity.UserUserSimilarity> topSimilarities =
- new PriorityQueue<GenericUserSimilarity.UserUserSimilarity>(howMany + 1, Collections.reverseOrder());
+
+ public static List<GenericUserSimilarity.UserUserSimilarity> getTopUserUserSimilarities(int howMany,
+ Iterable<GenericUserSimilarity.UserUserSimilarity> allSimilarities) {
+ Queue<GenericUserSimilarity.UserUserSimilarity> topSimilarities = new PriorityQueue<GenericUserSimilarity.UserUserSimilarity>(
+ howMany + 1, Collections.reverseOrder());
boolean full = false;
double lowestTopValue = Double.NEGATIVE_INFINITY;
for (GenericUserSimilarity.UserUserSimilarity similarity : allSimilarities) {
double value = similarity.getValue();
- if (!Double.isNaN(value) && (!full || value > lowestTopValue)) {
+ if (!Double.isNaN(value) && (!full || (value > lowestTopValue))) {
topSimilarities.add(similarity);
if (full) {
topSimilarities.poll();
@@ -174,15 +180,15 @@
lowestTopValue = topSimilarities.peek().getValue();
}
}
- List<GenericUserSimilarity.UserUserSimilarity> result =
- new ArrayList<GenericUserSimilarity.UserUserSimilarity>(topSimilarities.size());
+ List<GenericUserSimilarity.UserUserSimilarity> result = new ArrayList<GenericUserSimilarity.UserUserSimilarity>(
+ topSimilarities.size());
result.addAll(topSimilarities);
Collections.sort(result);
return result;
}
-
+
public interface Estimator<T> {
double estimate(T thing) throws TasteException;
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender.java Sat Feb 13 20:54:05 2010
@@ -17,53 +17,56 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.Callable;
+import java.util.concurrent.locks.ReentrantLock;
+
import org.apache.mahout.cf.taste.common.Refreshable;
import org.apache.mahout.cf.taste.common.TasteException;
import org.apache.mahout.cf.taste.impl.common.FastByIDMap;
import org.apache.mahout.cf.taste.impl.common.FastIDSet;
import org.apache.mahout.cf.taste.impl.common.FullRunningAverage;
import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator;
-import org.apache.mahout.cf.taste.recommender.IDRescorer;
-import org.apache.mahout.common.Pair;
-import org.apache.mahout.common.RandomUtils;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.recommender.ClusteringRecommender;
+import org.apache.mahout.cf.taste.recommender.IDRescorer;
import org.apache.mahout.cf.taste.recommender.RecommendedItem;
+import org.apache.mahout.common.Pair;
+import org.apache.mahout.common.RandomUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-import java.util.Random;
-import java.util.concurrent.Callable;
-import java.util.concurrent.locks.ReentrantLock;
-
/**
- * <p>A {@link org.apache.mahout.cf.taste.recommender.Recommender} that clusters users, then determines the
- * clusters' top recommendations. This implementation builds clusters by repeatedly merging clusters until only a
- * certain number remain, meaning that each cluster is sort of a tree of other clusters.</p>
- *
- * <p>This {@link org.apache.mahout.cf.taste.recommender.Recommender} therefore has a few properties to note:</p>
- *
+ * <p>
+ * A {@link org.apache.mahout.cf.taste.recommender.Recommender} that clusters users, then determines the
+ * clusters' top recommendations. This implementation builds clusters by repeatedly merging clusters until
+ * only a certain number remain, meaning that each cluster is sort of a tree of other clusters.
+ * </p>
+ *
+ * <p>
+ * This {@link org.apache.mahout.cf.taste.recommender.Recommender} therefore has a few properties to note:
+ * </p>
+ *
* <ul>
* <li>For all users in a cluster, recommendations will be the same</li>
- * <li>{@link #estimatePreference(long, long)} may well return {@link Double#NaN};
- * it does so when asked to estimate preference for an item for
- * which no preference is expressed in the users in the cluster.</li>
+ * <li>{@link #estimatePreference(long, long)} may well return {@link Double#NaN}; it does so when asked to
+ * estimate preference for an item for which no preference is expressed in the users in the cluster.</li>
* </ul>
*/
public final class TreeClusteringRecommender extends AbstractRecommender implements ClusteringRecommender {
-
+
private static final Logger log = LoggerFactory.getLogger(TreeClusteringRecommender.class);
-
+
private static final int NUM_CLUSTER_RECS = 100;
private static final FastIDSet[] NO_CLUSTERS = new FastIDSet[0];
private static final Random r = RandomUtils.getRandom();
-
+
private final ClusterSimilarity clusterSimilarity;
private final int numClusters;
private final double clusteringThreshold;
@@ -75,27 +78,34 @@
private boolean clustersBuilt;
private final ReentrantLock buildClustersLock;
private final RefreshHelper refreshHelper;
-
+
/**
- * @param dataModel {@link DataModel} which provdes users
- * @param clusterSimilarity {@link ClusterSimilarity} used to compute cluster similarity
- * @param numClusters desired number of clusters to create
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>numClusters</code> is less than 2
+ * @param dataModel
+ * {@link DataModel} which provdes users
+ * @param clusterSimilarity
+ * {@link ClusterSimilarity} used to compute cluster similarity
+ * @param numClusters
+ * desired number of clusters to create
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>numClusters</code> is less than 2
*/
- public TreeClusteringRecommender(DataModel dataModel,
- ClusterSimilarity clusterSimilarity,
- int numClusters) {
+ public TreeClusteringRecommender(DataModel dataModel, ClusterSimilarity clusterSimilarity, int numClusters) {
this(dataModel, clusterSimilarity, numClusters, 1.0);
}
-
+
/**
- * @param dataModel {@link DataModel} which provdes users
- * @param clusterSimilarity {@link ClusterSimilarity} used to compute cluster similarity
- * @param numClusters desired number of clusters to create
- * @param samplingRate percentage of all cluster-cluster pairs to consider when finding next-most-similar
- * clusters. Decreasing this value from 1.0 can increase performance at the cost of accuracy
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>numClusters</code> is less than 2, or
- * samplingRate is {@link Double#NaN} or nonpositive or greater than 1.0
+ * @param dataModel
+ * {@link DataModel} which provdes users
+ * @param clusterSimilarity
+ * {@link ClusterSimilarity} used to compute cluster similarity
+ * @param numClusters
+ * desired number of clusters to create
+ * @param samplingRate
+ * percentage of all cluster-cluster pairs to consider when finding next-most-similar clusters.
+ * Decreasing this value from 1.0 can increase performance at the cost of accuracy
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>numClusters</code> is less than 2, or samplingRate
+ * is {@link Double#NaN} or nonpositive or greater than 1.0
*/
public TreeClusteringRecommender(DataModel dataModel,
ClusterSimilarity clusterSimilarity,
@@ -108,7 +118,7 @@
if (numClusters < 2) {
throw new IllegalArgumentException("numClusters must be at least 2");
}
- if (Double.isNaN(samplingRate) || samplingRate <= 0.0 || samplingRate > 1.0) {
+ if (Double.isNaN(samplingRate) || (samplingRate <= 0.0) || (samplingRate > 1.0)) {
throw new IllegalArgumentException("samplingRate is invalid: " + samplingRate);
}
this.clusterSimilarity = clusterSimilarity;
@@ -127,32 +137,38 @@
refreshHelper.addDependency(dataModel);
refreshHelper.addDependency(clusterSimilarity);
}
-
+
/**
- * @param dataModel {@link DataModel} which provdes users
- * @param clusterSimilarity {@link ClusterSimilarity} used to compute cluster similarity
- * @param clusteringThreshold clustering similarity threshold; clusters will be aggregated into larger clusters until
- * the next two nearest clusters' similarity drops below this threshold
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link
- * Double#NaN}
+ * @param dataModel
+ * {@link DataModel} which provdes users
+ * @param clusterSimilarity
+ * {@link ClusterSimilarity} used to compute cluster similarity
+ * @param clusteringThreshold
+ * clustering similarity threshold; clusters will be aggregated into larger clusters until the next
+ * two nearest clusters' similarity drops below this threshold
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link Double#NaN}
*/
public TreeClusteringRecommender(DataModel dataModel,
ClusterSimilarity clusterSimilarity,
double clusteringThreshold) {
this(dataModel, clusterSimilarity, clusteringThreshold, 1.0);
}
-
+
/**
- * @param dataModel {@link DataModel} which provides users
- * @param clusterSimilarity {@link ClusterSimilarity} used to compute cluster similarity
- * @param clusteringThreshold clustering similarity threshold; clusters will be aggregated into larger clusters until
- * the next two nearest clusters' similarity drops below this threshold
- * @param samplingRate percentage of all cluster-cluster pairs to consider when finding next-most-similar
- * clusters. Decreasing this value from 1.0 can increase performance at the cost of
- * accuracy
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link
- * Double#NaN}, or samplingRate is {@link Double#NaN} or nonpositive or greater than
- * 1.0
+ * @param dataModel
+ * {@link DataModel} which provides users
+ * @param clusterSimilarity
+ * {@link ClusterSimilarity} used to compute cluster similarity
+ * @param clusteringThreshold
+ * clustering similarity threshold; clusters will be aggregated into larger clusters until the next
+ * two nearest clusters' similarity drops below this threshold
+ * @param samplingRate
+ * percentage of all cluster-cluster pairs to consider when finding next-most-similar clusters.
+ * Decreasing this value from 1.0 can increase performance at the cost of accuracy
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link Double#NaN},
+ * or samplingRate is {@link Double#NaN} or nonpositive or greater than 1.0
*/
public TreeClusteringRecommender(DataModel dataModel,
ClusterSimilarity clusterSimilarity,
@@ -165,7 +181,7 @@
if (Double.isNaN(clusteringThreshold)) {
throw new IllegalArgumentException("clusteringThreshold must not be NaN");
}
- if (Double.isNaN(samplingRate) || samplingRate <= 0.0 || samplingRate > 1.0) {
+ if (Double.isNaN(samplingRate) || (samplingRate <= 0.0) || (samplingRate > 1.0)) {
throw new IllegalArgumentException("samplingRate is invalid: " + samplingRate);
}
this.clusterSimilarity = clusterSimilarity;
@@ -184,41 +200,40 @@
refreshHelper.addDependency(dataModel);
refreshHelper.addDependency(clusterSimilarity);
}
-
+
@Override
- public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer)
- throws TasteException {
+ public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException {
if (howMany < 1) {
throw new IllegalArgumentException("howMany must be at least 1");
}
checkClustersBuilt();
-
- log.debug("Recommending items for user ID '{}'", userID);
-
+
+ TreeClusteringRecommender.log.debug("Recommending items for user ID '{}'", userID);
+
List<RecommendedItem> recommended = topRecsByUserID.get(userID);
if (recommended == null) {
return Collections.emptyList();
}
-
+
DataModel dataModel = getDataModel();
List<RecommendedItem> rescored = new ArrayList<RecommendedItem>(recommended.size());
// Only add items the user doesn't already have a preference for.
// And that the rescorer doesn't "reject".
for (RecommendedItem recommendedItem : recommended) {
long itemID = recommendedItem.getItemID();
- if (rescorer != null && rescorer.isFiltered(itemID)) {
+ if ((rescorer != null) && rescorer.isFiltered(itemID)) {
continue;
}
- if (dataModel.getPreferenceValue(userID, itemID) == null &&
- (rescorer == null || !Double.isNaN(rescorer.rescore(itemID, recommendedItem.getValue())))) {
+ if ((dataModel.getPreferenceValue(userID, itemID) == null)
+ && ((rescorer == null) || !Double.isNaN(rescorer.rescore(itemID, recommendedItem.getValue())))) {
rescored.add(recommendedItem);
}
}
Collections.sort(rescored, new ByRescoreComparator(rescorer));
-
+
return rescored;
}
-
+
@Override
public float estimatePreference(long userID, long itemID) throws TasteException {
DataModel model = getDataModel();
@@ -238,26 +253,26 @@
// Hmm, we have no idea. The item is not in the user's cluster
return Float.NaN;
}
-
+
@Override
public FastIDSet getCluster(long userID) throws TasteException {
checkClustersBuilt();
FastIDSet cluster = clustersByUserID.get(userID);
return cluster == null ? new FastIDSet() : cluster;
}
-
+
@Override
public FastIDSet[] getClusters() throws TasteException {
checkClustersBuilt();
return allClusters;
}
-
+
private void checkClustersBuilt() throws TasteException {
if (!clustersBuilt) {
buildClusters();
}
}
-
+
private void buildClusters() throws TasteException {
buildClustersLock.lock();
try {
@@ -276,22 +291,22 @@
findClusters(newClusters);
}
topRecsByUserID = computeTopRecsPerUserID(newClusters);
- clustersByUserID = computeClustersPerUserID(newClusters);
+ clustersByUserID = TreeClusteringRecommender.computeClustersPerUserID(newClusters);
allClusters = newClusters.toArray(new FastIDSet[newClusters.size()]);
} else {
topRecsByUserID = new FastByIDMap<List<RecommendedItem>>();
clustersByUserID = new FastByIDMap<FastIDSet>();
- allClusters = NO_CLUSTERS;
+ allClusters = TreeClusteringRecommender.NO_CLUSTERS;
}
clustersBuilt = true;
} finally {
buildClustersLock.unlock();
}
}
-
+
private void findClusters(List<FastIDSet> newClusters) throws TasteException {
if (clusteringByThreshold) {
- Pair<FastIDSet, FastIDSet> nearestPair = findNearestClusters(newClusters);
+ Pair<FastIDSet,FastIDSet> nearestPair = findNearestClusters(newClusters);
if (nearestPair != null) {
FastIDSet cluster1 = nearestPair.getFirst();
FastIDSet cluster2 = nearestPair.getSecond();
@@ -312,7 +327,7 @@
}
} else {
while (newClusters.size() > numClusters) {
- Pair<FastIDSet, FastIDSet> nearestPair = findNearestClusters(newClusters);
+ Pair<FastIDSet,FastIDSet> nearestPair = findNearestClusters(newClusters);
if (nearestPair == null) {
break;
}
@@ -327,27 +342,27 @@
}
}
}
-
- private Pair<FastIDSet, FastIDSet> findNearestClusters(List<FastIDSet> clusters) throws TasteException {
+
+ private Pair<FastIDSet,FastIDSet> findNearestClusters(List<FastIDSet> clusters) throws TasteException {
int size = clusters.size();
- Pair<FastIDSet, FastIDSet> nearestPair = null;
+ Pair<FastIDSet,FastIDSet> nearestPair = null;
double bestSimilarity = Double.NEGATIVE_INFINITY;
for (int i = 0; i < size; i++) {
FastIDSet cluster1 = clusters.get(i);
for (int j = i + 1; j < size; j++) {
- if (samplingRate >= 1.0 || r.nextDouble() < samplingRate) {
+ if ((samplingRate >= 1.0) || (TreeClusteringRecommender.r.nextDouble() < samplingRate)) {
FastIDSet cluster2 = clusters.get(j);
double similarity = clusterSimilarity.getSimilarity(cluster1, cluster2);
- if (!Double.isNaN(similarity) && similarity > bestSimilarity) {
+ if (!Double.isNaN(similarity) && (similarity > bestSimilarity)) {
bestSimilarity = similarity;
- nearestPair = new Pair<FastIDSet, FastIDSet>(cluster1, cluster2);
+ nearestPair = new Pair<FastIDSet,FastIDSet>(cluster1, cluster2);
}
}
}
}
return nearestPair;
}
-
+
private FastByIDMap<List<RecommendedItem>> computeTopRecsPerUserID(List<FastIDSet> clusters) throws TasteException {
FastByIDMap<List<RecommendedItem>> recsPerUser = new FastByIDMap<List<RecommendedItem>>();
for (FastIDSet cluster : clusters) {
@@ -359,25 +374,24 @@
}
return recsPerUser;
}
-
- private List<RecommendedItem> computeTopRecsForCluster(FastIDSet cluster)
- throws TasteException {
+
+ private List<RecommendedItem> computeTopRecsForCluster(FastIDSet cluster) throws TasteException {
DataModel dataModel = getDataModel();
FastIDSet possibleItemIDs = new FastIDSet();
LongPrimitiveIterator it = cluster.iterator();
while (it.hasNext()) {
possibleItemIDs.addAll(dataModel.getItemIDsFromUser(it.next()));
}
-
+
TopItems.Estimator<Long> estimator = new Estimator(cluster);
-
- List<RecommendedItem> topItems =
- TopItems.getTopItems(NUM_CLUSTER_RECS, possibleItemIDs.iterator(), null, estimator);
-
- log.debug("Recommendations are: {}", topItems);
+
+ List<RecommendedItem> topItems = TopItems.getTopItems(TreeClusteringRecommender.NUM_CLUSTER_RECS,
+ possibleItemIDs.iterator(), null, estimator);
+
+ TreeClusteringRecommender.log.debug("Recommendations are: {}", topItems);
return Collections.unmodifiableList(topItems);
}
-
+
private static FastByIDMap<FastIDSet> computeClustersPerUserID(Collection<FastIDSet> clusters) {
FastByIDMap<FastIDSet> clustersPerUser = new FastByIDMap<FastIDSet>(clusters.size());
for (FastIDSet cluster : clusters) {
@@ -388,25 +402,25 @@
}
return clustersPerUser;
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
refreshHelper.refresh(alreadyRefreshed);
}
-
+
@Override
public String toString() {
return "TreeClusteringRecommender[clusterSimilarity:" + clusterSimilarity + ']';
}
-
+
private class Estimator implements TopItems.Estimator<Long> {
-
+
private final FastIDSet cluster;
-
+
private Estimator(FastIDSet cluster) {
this.cluster = cluster;
}
-
+
@Override
public double estimate(Long itemID) throws TasteException {
DataModel dataModel = getDataModel();
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/TreeClusteringRecommender2.java Sat Feb 13 20:54:05 2010
@@ -17,55 +17,61 @@
package org.apache.mahout.cf.taste.impl.recommender;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.concurrent.Callable;
+import java.util.concurrent.locks.ReentrantLock;
+
import org.apache.mahout.cf.taste.common.Refreshable;
import org.apache.mahout.cf.taste.common.TasteException;
import org.apache.mahout.cf.taste.impl.common.FastByIDMap;
import org.apache.mahout.cf.taste.impl.common.FastIDSet;
import org.apache.mahout.cf.taste.impl.common.FullRunningAverage;
import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator;
-import org.apache.mahout.cf.taste.recommender.IDRescorer;
-import org.apache.mahout.common.RandomUtils;
import org.apache.mahout.cf.taste.impl.common.RefreshHelper;
import org.apache.mahout.cf.taste.impl.common.RunningAverage;
import org.apache.mahout.cf.taste.model.DataModel;
import org.apache.mahout.cf.taste.recommender.ClusteringRecommender;
+import org.apache.mahout.cf.taste.recommender.IDRescorer;
import org.apache.mahout.cf.taste.recommender.RecommendedItem;
+import org.apache.mahout.common.RandomUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.ListIterator;
-import java.util.concurrent.Callable;
-import java.util.concurrent.locks.ReentrantLock;
-
/**
- * <p>A {@link org.apache.mahout.cf.taste.recommender.Recommender} that clusters users,
- * then determines the clusters' top recommendations. This implementation
- * builds clusters by repeatedly merging clusters until only a certain number remain, meaning that each cluster is sort
- * of a tree of other clusters.</p>
- *
- * <p>This {@link org.apache.mahout.cf.taste.recommender.Recommender} therefore has a few properties to note:</p> <ul>
+ * <p>
+ * A {@link org.apache.mahout.cf.taste.recommender.Recommender} that clusters users, then determines the
+ * clusters' top recommendations. This implementation builds clusters by repeatedly merging clusters until
+ * only a certain number remain, meaning that each cluster is sort of a tree of other clusters.
+ * </p>
+ *
+ * <p>
+ * This {@link org.apache.mahout.cf.taste.recommender.Recommender} therefore has a few properties to note:
+ * </p>
+ * <ul>
* <li>For all users in a cluster, recommendations will be the same</li>
- * <li>{@link #estimatePreference(long, long)} may well return {@link Double#NaN}; it does so
- * when asked to estimate preference for an item for which no preference is expressed in the
- * users in the cluster.</li> </ul>
- *
- * <p>This is an <em>experimental</em> implementation which tries to gain a lot of speed at the cost of accuracy in
- * building clusters, compared to {@link TreeClusteringRecommender}. It will
- * sometimes cluster two other clusters together that may not be the exact closest two clusters in existence. This may
- * not affect the recommendation quality much, but it potentially speeds up the clustering process dramatically.</p>
+ * <li>{@link #estimatePreference(long, long)} may well return {@link Double#NaN}; it does so when asked to
+ * estimate preference for an item for which no preference is expressed in the users in the cluster.</li>
+ * </ul>
+ *
+ * <p>
+ * This is an <em>experimental</em> implementation which tries to gain a lot of speed at the cost of accuracy
+ * in building clusters, compared to {@link TreeClusteringRecommender}. It will sometimes cluster two other
+ * clusters together that may not be the exact closest two clusters in existence. This may not affect the
+ * recommendation quality much, but it potentially speeds up the clustering process dramatically.
+ * </p>
*/
public final class TreeClusteringRecommender2 extends AbstractRecommender implements ClusteringRecommender {
-
+
private static final Logger log = LoggerFactory.getLogger(TreeClusteringRecommender2.class);
-
+
private static final int NUM_CLUSTER_RECS = 100;
-
+
private final ClusterSimilarity clusterSimilarity;
private final int numClusters;
private final double clusteringThreshold;
@@ -76,17 +82,18 @@
private boolean clustersBuilt;
private final ReentrantLock buildClustersLock;
private final RefreshHelper refreshHelper;
-
+
/**
- * @param dataModel {@link DataModel} which provides users
- * @param clusterSimilarity {@link ClusterSimilarity} used to compute
- * cluster similarity
- * @param numClusters desired number of clusters to create
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>numClusters</code> is less than 2
+ * @param dataModel
+ * {@link DataModel} which provides users
+ * @param clusterSimilarity
+ * {@link ClusterSimilarity} used to compute cluster similarity
+ * @param numClusters
+ * desired number of clusters to create
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>numClusters</code> is less than 2
*/
- public TreeClusteringRecommender2(DataModel dataModel,
- ClusterSimilarity clusterSimilarity,
- int numClusters) {
+ public TreeClusteringRecommender2(DataModel dataModel, ClusterSimilarity clusterSimilarity, int numClusters) {
super(dataModel);
if (clusterSimilarity == null) {
throw new IllegalArgumentException("clusterSimilarity is null");
@@ -109,15 +116,18 @@
refreshHelper.addDependency(dataModel);
refreshHelper.addDependency(clusterSimilarity);
}
-
+
/**
- * @param dataModel {@link org.apache.mahout.cf.taste.model.DataModel} which provides users
- * @param clusterSimilarity {@link org.apache.mahout.cf.taste.impl.recommender.ClusterSimilarity} used to compute
- * cluster similarity
- * @param clusteringThreshold clustering similarity threshold; clusters will be aggregated into larger clusters until
- * the next two nearest clusters' similarity drops below this threshold
- * @throws IllegalArgumentException if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link
- * Double#NaN}
+ * @param dataModel
+ * {@link org.apache.mahout.cf.taste.model.DataModel} which provides users
+ * @param clusterSimilarity
+ * {@link org.apache.mahout.cf.taste.impl.recommender.ClusterSimilarity} used to compute cluster
+ * similarity
+ * @param clusteringThreshold
+ * clustering similarity threshold; clusters will be aggregated into larger clusters until the next
+ * two nearest clusters' similarity drops below this threshold
+ * @throws IllegalArgumentException
+ * if arguments are <code>null</code>, or <code>clusteringThreshold</code> is {@link Double#NaN}
*/
public TreeClusteringRecommender2(DataModel dataModel,
ClusterSimilarity clusterSimilarity,
@@ -144,41 +154,40 @@
refreshHelper.addDependency(dataModel);
refreshHelper.addDependency(clusterSimilarity);
}
-
+
@Override
- public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer)
- throws TasteException {
+ public List<RecommendedItem> recommend(long userID, int howMany, IDRescorer rescorer) throws TasteException {
if (howMany < 1) {
throw new IllegalArgumentException("howMany must be at least 1");
}
checkClustersBuilt();
-
- log.debug("Recommending items for user ID '{}'", userID);
-
+
+ TreeClusteringRecommender2.log.debug("Recommending items for user ID '{}'", userID);
+
List<RecommendedItem> recommended = topRecsByUserID.get(userID);
if (recommended == null) {
return Collections.emptyList();
}
-
+
DataModel dataModel = getDataModel();
List<RecommendedItem> rescored = new ArrayList<RecommendedItem>(recommended.size());
// Only add items the user doesn't already have a preference for.
// And that the rescorer doesn't "reject".
for (RecommendedItem recommendedItem : recommended) {
long itemID = recommendedItem.getItemID();
- if (rescorer != null && rescorer.isFiltered(itemID)) {
+ if ((rescorer != null) && rescorer.isFiltered(itemID)) {
continue;
}
- if (dataModel.getPreferenceValue(userID, itemID) == null &&
- (rescorer == null || !Double.isNaN(rescorer.rescore(itemID, recommendedItem.getValue())))) {
+ if ((dataModel.getPreferenceValue(userID, itemID) == null)
+ && ((rescorer == null) || !Double.isNaN(rescorer.rescore(itemID, recommendedItem.getValue())))) {
rescored.add(recommendedItem);
}
}
Collections.sort(rescored, new ByRescoreComparator(rescorer));
-
+
return rescored;
}
-
+
@Override
public float estimatePreference(long userID, long itemID) throws TasteException {
Float actualPref = getDataModel().getPreferenceValue(userID, itemID);
@@ -197,68 +206,65 @@
// Hmm, we have no idea. The item is not in the user's cluster
return Float.NaN;
}
-
+
@Override
public FastIDSet getCluster(long userID) throws TasteException {
checkClustersBuilt();
FastIDSet cluster = clustersByUserID.get(userID);
return cluster == null ? new FastIDSet() : cluster;
}
-
+
@Override
public FastIDSet[] getClusters() throws TasteException {
checkClustersBuilt();
return allClusters;
}
-
+
private void checkClustersBuilt() throws TasteException {
if (!clustersBuilt) {
buildClusters();
}
}
-
+
private static final class ClusterClusterPair implements Comparable<ClusterClusterPair> {
-
+
private final FastIDSet cluster1;
private final FastIDSet cluster2;
private final double similarity;
-
- private ClusterClusterPair(FastIDSet cluster1,
- FastIDSet cluster2,
- double similarity) {
+
+ private ClusterClusterPair(FastIDSet cluster1, FastIDSet cluster2, double similarity) {
this.cluster1 = cluster1;
this.cluster2 = cluster2;
this.similarity = similarity;
}
-
+
FastIDSet getCluster1() {
return cluster1;
}
-
+
FastIDSet getCluster2() {
return cluster2;
}
-
+
double getSimilarity() {
return similarity;
}
-
+
@Override
public int hashCode() {
return cluster1.hashCode() ^ cluster2.hashCode() ^ RandomUtils.hashDouble(similarity);
}
-
+
@Override
public boolean equals(Object o) {
if (!(o instanceof ClusterClusterPair)) {
return false;
}
ClusterClusterPair other = (ClusterClusterPair) o;
- return cluster1.equals(other.getCluster1()) &&
- cluster2.equals(other.getCluster2()) &&
- similarity == other.getSimilarity();
+ return cluster1.equals(other.getCluster1()) && cluster2.equals(other.getCluster2())
+ && (similarity == other.getSimilarity());
}
-
+
@Override
public int compareTo(ClusterClusterPair other) {
double otherSimilarity = other.getSimilarity();
@@ -270,22 +276,22 @@
return 0;
}
}
-
+
}
-
+
private void buildClusters() throws TasteException {
buildClustersLock.lock();
try {
DataModel model = getDataModel();
int numUsers = model.getNumUsers();
-
+
if (numUsers == 0) {
-
+
topRecsByUserID = new FastByIDMap<List<RecommendedItem>>();
clustersByUserID = new FastByIDMap<FastIDSet>();
-
+
} else {
-
+
List<FastIDSet> clusters = new LinkedList<FastIDSet>();
// Begin with a cluster for each user:
LongPrimitiveIterator it = model.getUserIDs();
@@ -294,51 +300,50 @@
newCluster.add(it.nextLong());
clusters.add(newCluster);
}
-
+
boolean done = false;
while (!done) {
done = mergeClosestClusters(numUsers, clusters, done);
}
-
+
topRecsByUserID = computeTopRecsPerUserID(clusters);
- clustersByUserID = computeClustersPerUserID(clusters);
+ clustersByUserID = TreeClusteringRecommender2.computeClustersPerUserID(clusters);
allClusters = clusters.toArray(new FastIDSet[clusters.size()]);
-
+
}
-
+
clustersBuilt = true;
} finally {
buildClustersLock.unlock();
}
}
-
- private boolean mergeClosestClusters(int numUsers, List<FastIDSet> clusters, boolean done)
- throws TasteException {
+
+ private boolean mergeClosestClusters(int numUsers, List<FastIDSet> clusters, boolean done) throws TasteException {
// We find a certain number of closest clusters...
LinkedList<ClusterClusterPair> queue = findClosestClusters(numUsers, clusters);
-
+
// The first one is definitely the closest pair in existence so we can cluster
// the two together, put it back into the set of clusters, and start again. Instead
// we assume everything else in our list of closest cluster pairs is still pretty good,
// and we cluster them too.
-
+
while (!queue.isEmpty()) {
-
- if (!clusteringByThreshold && clusters.size() <= numClusters) {
+
+ if (!clusteringByThreshold && (clusters.size() <= numClusters)) {
done = true;
break;
}
-
+
ClusterClusterPair top = queue.removeFirst();
-
- if (clusteringByThreshold && top.getSimilarity() < clusteringThreshold) {
+
+ if (clusteringByThreshold && (top.getSimilarity() < clusteringThreshold)) {
done = true;
break;
}
-
+
FastIDSet cluster1 = top.getCluster1();
FastIDSet cluster2 = top.getCluster2();
-
+
// Pull out current two clusters from clusters
Iterator<FastIDSet> clusterIterator = clusters.iterator();
boolean removed1 = false;
@@ -346,32 +351,31 @@
while (clusterIterator.hasNext() && !(removed1 && removed2)) {
FastIDSet current = clusterIterator.next();
// Yes, use == here
- if (!removed1 && cluster1 == current) {
+ if (!removed1 && (cluster1 == current)) {
clusterIterator.remove();
removed1 = true;
- } else if (!removed2 && cluster2 == current) {
+ } else if (!removed2 && (cluster2 == current)) {
clusterIterator.remove();
removed2 = true;
}
}
-
+
// The only catch is if a cluster showed it twice in the list of best cluster pairs;
// have to remove the others. Pull out anything referencing these clusters from queue
- for (Iterator<ClusterClusterPair> queueIterator = queue.iterator();
- queueIterator.hasNext();) {
+ for (Iterator<ClusterClusterPair> queueIterator = queue.iterator(); queueIterator.hasNext();) {
ClusterClusterPair pair = queueIterator.next();
FastIDSet pair1 = pair.getCluster1();
FastIDSet pair2 = pair.getCluster2();
- if (pair1 == cluster1 || pair1 == cluster2 || pair2 == cluster1 || pair2 == cluster2) {
+ if ((pair1 == cluster1) || (pair1 == cluster2) || (pair2 == cluster1) || (pair2 == cluster2)) {
queueIterator.remove();
}
}
-
+
// Make new merged cluster
FastIDSet merged = new FastIDSet(cluster1.size() + cluster2.size());
merged.addAll(cluster1);
merged.addAll(cluster2);
-
+
// Compare against other clusters; update queue if needed
// That new pair we're just adding might be pretty close to something else, so
// catch that case here and put it back into our queue
@@ -388,16 +392,15 @@
queueIterator.add(new ClusterClusterPair(merged, cluster, similarity));
}
}
-
+
// Finally add new cluster to list
clusters.add(merged);
-
+
}
return done;
}
-
- private LinkedList<ClusterClusterPair> findClosestClusters(int numUsers, List<FastIDSet> clusters)
- throws TasteException {
+
+ private LinkedList<ClusterClusterPair> findClosestClusters(int numUsers, List<FastIDSet> clusters) throws TasteException {
boolean full = false;
LinkedList<ClusterClusterPair> queue = new LinkedList<ClusterClusterPair>();
int i = 0;
@@ -407,10 +410,8 @@
while (it2.hasNext()) {
FastIDSet cluster2 = it2.next();
double similarity = clusterSimilarity.getSimilarity(cluster1, cluster2);
- if (!Double.isNaN(similarity) &&
- (!full || similarity > queue.getLast().getSimilarity())) {
- ListIterator<ClusterClusterPair> queueIterator =
- queue.listIterator(queue.size());
+ if (!Double.isNaN(similarity) && (!full || (similarity > queue.getLast().getSimilarity()))) {
+ ListIterator<ClusterClusterPair> queueIterator = queue.listIterator(queue.size());
while (queueIterator.hasPrevious()) {
if (similarity <= queueIterator.previous().getSimilarity()) {
queueIterator.next();
@@ -429,9 +430,8 @@
}
return queue;
}
-
- private FastByIDMap<List<RecommendedItem>> computeTopRecsPerUserID(Iterable<FastIDSet> clusters)
- throws TasteException {
+
+ private FastByIDMap<List<RecommendedItem>> computeTopRecsPerUserID(Iterable<FastIDSet> clusters) throws TasteException {
FastByIDMap<List<RecommendedItem>> recsPerUser = new FastByIDMap<List<RecommendedItem>>();
for (FastIDSet cluster : clusters) {
List<RecommendedItem> recs = computeTopRecsForCluster(cluster);
@@ -442,30 +442,27 @@
}
return recsPerUser;
}
-
- private List<RecommendedItem> computeTopRecsForCluster(FastIDSet cluster)
- throws TasteException {
-
+
+ private List<RecommendedItem> computeTopRecsForCluster(FastIDSet cluster) throws TasteException {
+
DataModel dataModel = getDataModel();
FastIDSet possibleItemIDs = new FastIDSet();
LongPrimitiveIterator it = cluster.iterator();
while (it.hasNext()) {
possibleItemIDs.addAll(dataModel.getItemIDsFromUser(it.next()));
}
-
+
TopItems.Estimator<Long> estimator = new Estimator(cluster);
-
- List<RecommendedItem> topItems =
- TopItems.getTopItems(NUM_CLUSTER_RECS, possibleItemIDs.iterator(), null, estimator);
-
- log.debug("Recommendations are: {}", topItems);
+
+ List<RecommendedItem> topItems = TopItems.getTopItems(TreeClusteringRecommender2.NUM_CLUSTER_RECS,
+ possibleItemIDs.iterator(), null, estimator);
+
+ TreeClusteringRecommender2.log.debug("Recommendations are: {}", topItems);
return Collections.unmodifiableList(topItems);
}
-
- private static FastByIDMap<FastIDSet>
- computeClustersPerUserID(Collection<FastIDSet> clusters) {
- FastByIDMap<FastIDSet> clustersPerUser =
- new FastByIDMap<FastIDSet>(clusters.size());
+
+ private static FastByIDMap<FastIDSet> computeClustersPerUserID(Collection<FastIDSet> clusters) {
+ FastByIDMap<FastIDSet> clustersPerUser = new FastByIDMap<FastIDSet>(clusters.size());
for (FastIDSet cluster : clusters) {
LongPrimitiveIterator it = cluster.iterator();
while (it.hasNext()) {
@@ -474,25 +471,25 @@
}
return clustersPerUser;
}
-
+
@Override
public void refresh(Collection<Refreshable> alreadyRefreshed) {
refreshHelper.refresh(alreadyRefreshed);
}
-
+
@Override
public String toString() {
return "TreeClusteringRecommender2[clusterSimilarity:" + clusterSimilarity + ']';
}
-
+
private class Estimator implements TopItems.Estimator<Long> {
-
+
private final FastIDSet cluster;
-
+
private Estimator(FastIDSet cluster) {
this.cluster = cluster;
}
-
+
@Override
public double estimate(Long itemID) throws TasteException {
DataModel dataModel = getDataModel();
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/ConjugateGradientOptimizer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/ConjugateGradientOptimizer.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/ConjugateGradientOptimizer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/ConjugateGradientOptimizer.java Sat Feb 13 20:54:05 2010
@@ -20,20 +20,22 @@
import java.util.Arrays;
public final class ConjugateGradientOptimizer implements Optimizer {
-
+
private static final double CONVERGENCE_LIMIT = 0.1;
private static final int MAX_ITERATIONS = 1000;
-
+
/**
- * <p>Conjugate gradient optimization. Matlab code:</p>
- *
- * <p><pre>
+ * <p>
+ * Conjugate gradient optimization. Matlab code:
+ * </p>
+ *
+ * <p>
+ *
+ * <pre>
* function [x] = conjgrad(A,b,x0)
- *
* x = x0;
* r = b - A*x0;
* w = -r;
- *
* for i = 1:size(A);
* z = A*w;
* a = (r'*w)/(w'*z);
@@ -45,24 +47,27 @@
* B = (r'*z)/(w'*z);
* w = -r + B*w;
* end
- *
* end
- * </pre></p>
- *
- * @param A matrix nxn positions
- * @param b vector b, n positions
+ * </pre>
+ *
+ * </p>
+ *
+ * @param A
+ * matrix nxn positions
+ * @param b
+ * vector b, n positions
* @return vector of n weights
*/
@Override
public double[] optimize(double[][] A, double[] b) {
-
+
int k = b.length;
double[] x = new double[k];
double[] r = new double[k];
double[] w = new double[k];
double[] z = new double[k];
- Arrays.fill(x, 3.0 / (double) k);
-
+ Arrays.fill(x, 3.0 / k);
+
// r = b - A*x0;
// w = -r;
for (int i = 0; i < k; i++) {
@@ -75,9 +80,9 @@
r[i] = ri;
w[i] = -ri;
}
-
- for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
-
+
+ for (int iteration = 0; iteration < ConjugateGradientOptimizer.MAX_ITERATIONS; iteration++) {
+
// z = A*w;
for (int i = 0; i < k; i++) {
double v = 0.0;
@@ -87,7 +92,7 @@
}
z[i] = v;
}
-
+
// a = (r'*w)/(w'*z);
double anum = 0.0;
double aden = 0.0;
@@ -96,24 +101,24 @@
aden += w[i] * z[i];
}
double a = anum / aden;
-
+
// x = x + a*w;
// r = r - a*z;
for (int i = 0; i < k; i++) {
x[i] += a * w[i];
r[i] -= a * z[i];
}
-
+
// stop when residual is close to 0
double rdot = 0.0;
for (int i = 0; i < k; i++) {
double value = r[i];
rdot += value * value;
}
- if (rdot <= CONVERGENCE_LIMIT) {
+ if (rdot <= ConjugateGradientOptimizer.CONVERGENCE_LIMIT) {
break;
}
-
+
// B = (r'*z)/(w'*z);
double Bnum = 0.0;
double Bden = 0.0;
@@ -123,15 +128,15 @@
Bden += w[i] * zi;
}
double B = Bnum / Bden;
-
+
// w = -r + B*w;
for (int i = 0; i < k; i++) {
w[i] = -r[i] + B * w[i];
}
-
+
}
-
+
return x;
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/KnnItemBasedRecommender.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/KnnItemBasedRecommender.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/KnnItemBasedRecommender.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/KnnItemBasedRecommender.java Sat Feb 13 20:54:05 2010
@@ -17,9 +17,10 @@
package org.apache.mahout.cf.taste.impl.recommender.knn;
+import java.util.List;
+
import org.apache.mahout.cf.taste.common.TasteException;
import org.apache.mahout.cf.taste.impl.common.FastIDSet;
-import org.apache.mahout.common.LongPair;
import org.apache.mahout.cf.taste.impl.common.LongPrimitiveIterator;
import org.apache.mahout.cf.taste.impl.recommender.GenericItemBasedRecommender;
import org.apache.mahout.cf.taste.impl.recommender.TopItems;
@@ -28,18 +29,19 @@
import org.apache.mahout.cf.taste.recommender.RecommendedItem;
import org.apache.mahout.cf.taste.recommender.Rescorer;
import org.apache.mahout.cf.taste.similarity.ItemSimilarity;
-
-import java.util.List;
+import org.apache.mahout.common.LongPair;
/**
- * <p>The weights to compute the final predicted preferences are calculated using linear interpolation, through an
- * {@link Optimizer}. This algorithm is based in the paper of Robert M. Bell and Yehuda Koren in ICDM '07.</p>
+ * <p>
+ * The weights to compute the final predicted preferences are calculated using linear interpolation, through
+ * an {@link Optimizer}. This algorithm is based in the paper of Robert M. Bell and Yehuda Koren in ICDM '07.
+ * </p>
*/
public final class KnnItemBasedRecommender extends GenericItemBasedRecommender {
-
+
private final Optimizer optimizer;
private final int neighborhoodSize;
-
+
public KnnItemBasedRecommender(DataModel dataModel,
ItemSimilarity similarity,
Optimizer optimizer,
@@ -48,27 +50,24 @@
this.optimizer = optimizer;
this.neighborhoodSize = neighborhoodSize;
}
-
+
private List<RecommendedItem> mostSimilarItems(long itemID,
LongPrimitiveIterator possibleItemIDs,
int howMany,
- Rescorer<LongPair> rescorer)
- throws TasteException {
+ Rescorer<LongPair> rescorer) throws TasteException {
TopItems.Estimator<Long> estimator = new MostSimilarEstimator(itemID, getSimilarity(), rescorer);
return TopItems.getTopItems(howMany, possibleItemIDs, null, estimator);
}
-
-
- private double[] getInterpolations(long itemID, long userID, long[] itemNeighborhood)
- throws TasteException {
-
+
+ private double[] getInterpolations(long itemID, long userID, long[] itemNeighborhood) throws TasteException {
+
int k = itemNeighborhood.length;
double[][] A = new double[k][k];
double[] b = new double[k];
int i = 0;
-
+
DataModel dataModel = getDataModel();
-
+
int numUsers = getDataModel().getNumUsers();
for (long iitem : itemNeighborhood) {
PreferenceArray iPrefs = getDataModel().getPreferencesForItem(iitem);
@@ -91,7 +90,7 @@
}
i++;
}
-
+
PreferenceArray iPrefs = getDataModel().getPreferencesForItem(itemID);
int iSize = iPrefs.length();
i = 0;
@@ -110,46 +109,47 @@
b[i] = value / numUsers;
i++;
}
-
+
return optimizer.optimize(A, b);
}
-
+
@Override
protected float doEstimatePreference(long theUserID, long itemID) throws TasteException {
-
+
DataModel dataModel = getDataModel();
PreferenceArray prefs = dataModel.getPreferencesFromUser(theUserID);
int size = prefs.length();
- FastIDSet possibleItemIDs = new FastIDSet(size);
+ FastIDSet possibleItemIDs = new FastIDSet(size);
for (int i = 0; i < size; i++) {
possibleItemIDs.add(prefs.getItemID(i));
}
possibleItemIDs.remove(itemID);
-
- List<RecommendedItem> mostSimilar = mostSimilarItems(itemID, possibleItemIDs.iterator(), neighborhoodSize, null);
+
+ List<RecommendedItem> mostSimilar = mostSimilarItems(itemID, possibleItemIDs.iterator(),
+ neighborhoodSize, null);
long[] theNeighborhood = new long[mostSimilar.size()];
int nOffset = 0;
for (RecommendedItem rec : mostSimilar) {
theNeighborhood[nOffset++] = rec.getItemID();
}
-
+
double[] weights = getInterpolations(itemID, theUserID, theNeighborhood);
-
+
int i = 0;
double preference = 0.0;
double totalSimilarity = 0.0;
for (long jitem : theNeighborhood) {
-
+
Float pref = dataModel.getPreferenceValue(theUserID, jitem);
-
+
if (pref != null) {
preference += pref * weights[i];
totalSimilarity += weights[i];
}
i++;
-
+
}
return totalSimilarity == 0.0 ? Float.NaN : (float) (preference / totalSimilarity);
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/NonNegativeQuadraticOptimizer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/NonNegativeQuadraticOptimizer.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/NonNegativeQuadraticOptimizer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/NonNegativeQuadraticOptimizer.java Sat Feb 13 20:54:05 2010
@@ -20,21 +20,23 @@
import java.util.Arrays;
/**
- * Non-negative Quadratic Optimization. Based on the paper of Robert M. Bell and Yehuda Koren in ICDM '07. Thanks to Dan
- * Tillberg for the hints in the implementation.
+ * Non-negative Quadratic Optimization. Based on the paper of Robert M. Bell and Yehuda Koren in ICDM '07.
+ * Thanks to Dan Tillberg for the hints in the implementation.
*/
public final class NonNegativeQuadraticOptimizer implements Optimizer {
-
+
private static final double EPSILON = 1.0e-10;
private static final double CONVERGENCE_LIMIT = 0.1;
private static final int MAX_ITERATIONS = 1000;
private static final double DEFAULT_STEP = 0.001;
-
+
/**
* Non-negative Quadratic Optimization.
- *
- * @param A matrix nxn positions
- * @param b vector b, n positions
+ *
+ * @param A
+ * matrix nxn positions
+ * @param b
+ * vector b, n positions
* @return vector of n weights
*/
@Override
@@ -42,10 +44,10 @@
int k = b.length;
double[] r = new double[k];
double[] x = new double[k];
- Arrays.fill(x, 3.0 / (double) k);
-
- for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
-
+ Arrays.fill(x, 3.0 / k);
+
+ for (int iteration = 0; iteration < NonNegativeQuadraticOptimizer.MAX_ITERATIONS; iteration++) {
+
double rdot = 0.0;
for (int n = 0; n < k; n++) {
double sumAw = 0.0;
@@ -55,10 +57,10 @@
}
// r = b - Ax; // the residual, or 'steepest gradient'
double rn = b[n] - sumAw;
-
+
// find active variables - those that are pinned due to
// nonnegativity constraints; set respective ri's to zero
- if ((x[n] < EPSILON) && (rn < 0.0)) {
+ if ((x[n] < NonNegativeQuadraticOptimizer.EPSILON) && (rn < 0.0)) {
rn = 0.0;
} else {
// max step size numerator
@@ -66,11 +68,11 @@
}
r[n] = rn;
}
-
- if (rdot <= CONVERGENCE_LIMIT) {
+
+ if (rdot <= NonNegativeQuadraticOptimizer.CONVERGENCE_LIMIT) {
break;
}
-
+
// max step size denominator
double rArdotSum = 0.0;
for (int n = 0; n < k; n++) {
@@ -81,14 +83,14 @@
}
rArdotSum += r[n] * SumAr;
}
-
+
// max step size
double stepSize = rdot / rArdotSum;
-
+
if (Double.isNaN(stepSize)) {
- stepSize = DEFAULT_STEP;
+ stepSize = NonNegativeQuadraticOptimizer.DEFAULT_STEP;
}
-
+
// adjust step size to prevent negative values
for (int n = 0; n < k; n++) {
if (r[n] < 0.0) {
@@ -96,19 +98,19 @@
stepSize = Math.min(absStepSize, Math.abs(x[n] / r[n])) * stepSize / absStepSize;
}
}
-
+
// update x values
for (int n = 0; n < k; n++) {
x[n] += stepSize * r[n];
- if (x[n] < EPSILON) {
+ if (x[n] < NonNegativeQuadraticOptimizer.EPSILON) {
x[n] = 0.0;
}
}
-
- //TODO: do something in case of divergence
+
+ // TODO: do something in case of divergence
}
-
+
return x;
}
-
+
}
Modified: lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/Optimizer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/Optimizer.java?rev=909912&r1=909911&r2=909912&view=diff
==============================================================================
--- lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/Optimizer.java (original)
+++ lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/recommender/knn/Optimizer.java Sat Feb 13 20:54:05 2010
@@ -18,7 +18,7 @@
package org.apache.mahout.cf.taste.impl.recommender.knn;
public interface Optimizer {
-
+
double[] optimize(double[][] A, double[] b);
-
+
}