Wie weiss ein Computer, was der Benutzer eventuell mag? Amazon ist der Vorreiter bei der Anwendung dieser Algorithmen. Wenn ein Artikel angeschaut wird, erscheint die Sektion „Andere Benutzer haben auch gekauft...“.
In jedem Buch, das erklärt, wie solche Recommender funktionieren, wird klargemacht, dass es nicht einen „besten“ Algorithmus für die Erzeugung von Empfehlungen gibt. Welcher Algorithmus der beste ist, muss jeweils empirisch an realen Daten ermittelt werden. Wieso nicht eine Kombination verschiedener Recommender? Skalierbarkeit und Performance leiden stark darunter – hier trotzdem ein Versuch...
Kombination verschiedener Algorithmen
Um das beste Resultat zu erhalten, habe ich eine eigene Implementierung vom Interface
Recommender.java, Teil der
Apache Mahout Library, erstellt, welche mit variabler Gewichtung Empfehlungen aus drei bestehenden Algorithmen generiert:
- User-Similarity: Für jeden Nutzer wird eine „Nachbarschaft“ von den ähnlichsten anderen Nutzern generiert (z.B. aus den meisten ähnlichen Bewertungen). Empfohlen sind alle Events, welche die Nachbarschaft bewertet hat, der Nutzer selbst aber noch nicht kennt.
- Item-Similarity: Ähnlich wie Tanimoto-Koeffizient: Die Ähnlichkeit zwischen Benutzern wird aus der Anzahl der gemeinsamen Events berechnet. Die Mathematik dahinter könnte alleine ein ganzes Buch füllen. Für die Distanz zwischen den Items wird mit der Log-Likelihood-Funktion berechnet.
- Slope-One: Empfehlungen werden berechnet, indem der durchschnittliche Unterschied zwischen den Bewertungen der Events berücksichtigt wird. Beispielsweise wird Zirkus Knie immer um 1 besser bewertet als der Zirkus Monti. Und zudem wird Zirkus Knie durchschnittlich gleich bewertet wie Zirkus Royal. Ein Nutzer bewertet nun Monti mit 2, und Royal mit 4. Wie wäre nun die geschätzte Wertung für Knie? Wenn wir von Monti ausgehen würden, wäre dies 2 + 1 = 3. Ausgegangen von Royal wäre es 4 + 0 = 4 (immer gleich wie Knie). Als Schätzung gibt der Computer nun eine durchschnittliche Bewertung von 3.5 an.
public class MyRecommenderBuilder implements RecommenderBuilder {
@Override
public Recommender buildRecommender(DataModel dataModel) throws TasteException {
// this map holds all recommenders
Map<Recommender, Integer> recommenders = new HashMap<Recommender, Integer>();
if (userSimilarityFactor > 0) recommenders.put(getUserSimilarityRecommender(dataModel), userSimilarityFactor);
if (logLikelihoodFactor > 0)recommenders.put(getLogLikelihoodRecommender(dataModel), logLikelihoodFactor);
if (slopeOneFactor > 0) recommenders.put(getSlopeOneRecommender(dataModel), slopeOneFactor);
// create the recommender
return new CombinatedRecommender(recommenders);
}
}
public class CombinatedRecommender implements Recommender {
private final Map<Recommender, Integer> recommenders; // holds all recommenders
private int sumWeight = 0; // total weight of the recommenders
public CombinatedRecommender(Map<Recommender, Integer> recommenders) {
this.recommenders = recommenders;
for (Map.Entry<Recommender, Integer> recommender : recommenders.entrySet()) {
sumWeight += recommender.getValue();
}
@Override
public List<RecommendedItem> recommend(long userID, int howMany) throws TasteException {
// Map holding all recommendations and the according score (weighted)
Map<Long, Float> allRecommendations = new Hashtable<Long, Float>();
// get recommendations of all recommenders
for (Map.Entry<Recommender, Integer> recommender : recommenders.entrySet()) {
// iterate through all recommendations of this recommender
for (RecommendedItem thisRec : recommender.getKey().recommend(userID, howMany)) {
long itemID = thisRec.getItemID();
// to weight the recomendations, multiply the accuracy of the recommendation with the
// weight of the recommender
float thisScore = thisRec.getValue() * recommender.getValue();
// adds this recommendation to the map of all recommended items. If this recommendation has already
// been done by another recommender, increase the score of the recommendation
addOrInsert(allRecommendations, itemID, thisScore);
}
}
// ... next steps ...
// 1. sort the result descending (highest score first) and limit the size to ‘howMany’
// 2. return this list
}
}
Code 1: MyRecommenderBuilder.java erstellt drei Recommender und gewichtet diese (in einer Map abgelegt). CombinatedRecommender.java erhält diese Map im Konstruktor . Der Aufruf von recommend(...) iteriert durch alle vorhandenden Recommender und lässt, unabhängig von den anderen Recommendern, Empfehlungen generieren. Die Resultate werden in allRecommendations gespeichert. Wenn mehrere Recommender dieselbe Empfehlung machen, erhält diese Empfehlung mehr Gewicht.
Mit JUnit die Faktoren verbessern
Eine flexible Gewichtung ermöglicht die einfache Anpassung an reale Daten. In einer Test-Klasse werden alle möglichen Kombinationen von Gewichtungen ausprobiert und die Deckung (0-100%) berechnet. Die Kombination mit der grössten Deckung wird dann übernommen. Der nächste Code-Ausschnitt zeigt einen Teil aus dem parametrierten JUnit-Test, der die beste Faktorenkombination berechnet. Diese Faktoren können dann im Code 1 produktiv eingesetzt werden.
private final int userSimFactor;
private final int logLikelihoodFactor;
private final int slopeOneFactor;
private static int bestFactor1;
private static int bestFactor2;
private static int bestFactor3;
private static double bestScore = Double.NaN;
@Test
public void testFactors() throws TasteException {
RecommenderEvaluator evaluator = new AverageAbsoluteDifferenceRecommenderEvaluator();
MyRecommenderBuilder recommenderBuilder = new MyRecommenderBuilder(userSimFactor,
logLikelihoodFactor, slopeOneFactor);
// how accurate are those factors?
double score = evaluator.evaluate(recommenderBuilder, null, dataModel, 0.9, 1.0);
if (score < bestScore) {
// new improved score --> Save these factors
bestFactor1 = userSimFactor;
bestFactor2 = logLikelihoodFactor;
bestFactor3 = slopeOneFactor;
bestScore = score;
}
}
Code 2: Test-Methode berechnet mittels RecommenderEvaluator.evaluate(...) den Deckungsgrad für beliebige Faktoren und ermittelt die beste Kombination.
Weitere Verbesserungen konnten innerhalb der bereits bestehenden Recommendern vorgenommen werden. Beispielsweise wird für die User-Similarity eine Nachbarschaft mit einer vordefinierten Anzahl von nächsten Usern berechet. Je nach Test-Daten ist es möglich, dass eine Nachbarschaft von nur zwei Benutzern das beste Resultat liefert. Bei anderen Test-Daten ist ein Optimum bei einer Nachbarschaft von über 100 weiteren Benutzern durchaus normal. Code 3 zeigt einen weiteren JUnit-Test, der, analog zu testFactors() die beste Nachbarschaftsgrösse ermittelt.
private final int neighborhoodSize;
private static int bestNeighborhoodSize;
private static double bestScore = Double.NaN;
@Test
public void testNeighborhoodSize() {
RecommenderEvaluator evaluator = new AverageAbsoluteDifferenceRecommenderEvaluator();
RecommenderBuilder recommenderBuilder = new RecommenderBuilder() {
@Override
public Recommender buildRecommender(DataModel dataModel) throws TasteException {
// use the Euclidian distance. Test with oder Similarities can be done
UserSimilarity userSimilarity = new EuclideanDistanceSimilarity(dataModel, Weighting.WEIGHTED);
// calculate neighborhood of the users with the parameterized size
UserNeighborhood neighborhood = new NearestNUserNeighborhood(neighborhoodSize, userSimilarity, dataModel);
// get recommendations
return new GenericUserBasedRecommender(dataModel, neighborhood, userSimilarity);
}
};
// how accurate is this neighborhood size
double score = evaluator.evaluate(recommenderBuilder, null, dataModel, 0.9, 1.0);
if (score < bestScore) {
// found a better neighborhood than before --> save better
bestNeighborhoodSize = neighborhoodSize;
bestScore = score;
}
}
Code 3: Wie bei ‚Code 1’ berechnet diese Test-Methode den Deckungsgrad, dieses Mal aber mit variierender Nachbarschaftsgrösse.
Performance – was noch zu retten ist
Somit wäre noch das Thema Performance anzusprechen. Solche Empfehlungsgeneratoren skalieren sehr schnell (oft quadratisch mit der Anzahl der User). Wenn Real-Time-Empfehlungen berechnet werden sollen, müssen Resultate in genügend schneller Zeit zurückgeliefert werden. Ein grosser Nachteil der obigen Implementierung ist, dass gleich drei Recommender parallel laufen. Wenn nun beispielsweise 25 Empfehlungen gefragt sind, müssen alle drei Recommender je 25 Empfehlungen erstellen. Danach werden diese gewichtet und zusammengemischt. Der Speicherbedarf der Empfehlungs-Engine ist von deren Konfiguration abhängig.
Eine Performance-Verbesserung für Live-Empfehlungen wäre eine gleichzeitige Berechnung der Empfehlungen durch mehrere Recommender. Mehrere Threads erlauben eine optimale Speicher- und Prozessorauslastung.
