Alle Programme können von hier heruntergeladen werden.

Problembeschreibung

Recommender Systeme machen auf Grund der Erfassung von Daten über das Verhalten von Personen Voraussagen für ds zukünftige Verhalten. Es stehen verschiedenen Datenquellen zur Verfügung, mit denen die Verfahren wirklichkeitsnah untersucht werden können:

Buchverkauf:
http://www2.informatik.uni-freiburg.de/~cziegler/BX/

Musik:
http://www.dtic.upf.edu/~ocelma/MusicRecommendationDataset/

Links zu verschiedener Datensammlungen:
https://vincentarelbundock.github.io/Rdatasets/datasets.html

Hier wird exemplarisch eine Datensammlung über die Empfehlung von Filmen beim Online-Filmverleih Netflix ausgegangen. Die csv-formattierenten Dateien können von

http://grouplens.org/datasets/movielens

heruntergeladen werden. Man wählt am besten die Datensammlung ml-latest-small.zip in der sich die Dateien:

links.csv, movies.csv, ratings.csv, tags.csv, README.txt

extrahieren lassen. Die Sammlung enthält 100'000 Empfehlungen von 700 Benutzern über 9000 verschiedene Filme. Die Version vom Oktober 2016 kann auch von hier heruntergeladen werden.

Dateinaufbereitung

Für grosse Datensammlungen ist es wichtig, die Datenmenge soweit als möglich zu reduzieren, bevor sie weiter untersucht wird. Sonst verschwendet man viel Rechenzeit, da die Datensammlung in der Regel mehrmals durchlaufen werden muss.

In der Datei ratings.csv sind die Empfehlungen der User zeilenweise komma-getrennt gespeichert. Tabellarisch dargestellt:

userId ist eiine User-Identifikation ist eine anonymisierte Beichnung für den Benutzer. Alle Benutzer mit gleicher Id sind nacheinander angeordnet. movieId ist eine Kennzeichnung des Films gemäss den Einträgen in der Datei movies.csv, welche den Filmtitel und den Filmgenre auflistet. rating ist eine Bewertung im Bereich 1 bis 6 in Halbzahlschritten. Aus timestamp lässt sich das Datum des Eingangs der Bewertung ermitteln. Diese Information wird hier nicht verwendet. Weitere Hinweise entnimmt man der Datei README.txt. Jeder Datensatz bezieht sich also auf einen einzigen Film.

Als erstes wird aus der Datei ratings.csv die Datei ratings.dat erstellt, die nur noch die Information, ob ein User einen Film positiv beurteilt (also empfiehlt) enthält. Dabei wird eine Schwelle ratingLevel festgelegt, von der an der Film empfohlen wird. Datensätze mit Filmen, die unter diese Schwelle fallen, werden nicht mehr aufgenommen. Tabellarisch darsgestellt enthält also ratings.dat die folgenden Daten:

Das Programm schreibt auch noch den Bereich der Film-Ids aus. Es werden aber nicht alle Zahlen in diesem Bereich verwendet.

Programm: [►]

# Prepare.py

import sys

ratingLevel = 3.0  
csvRatings = "ratings.csv"
datRatings = "ratings.dat"
movieInfo = "movies.csv"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

fInp = open(csvRatings, 'r')
fOut = open(datRatings, "w")
idMin = sys.maxint
idMax = 0
count = 0
for line in fInp:
    line = line[:-1]  # remove \n
    if len(line) == 0:  # empty line
        continue
    li = line.split(",")
    try:
        if float(li[2]) >= ratingLevel:
            sample = li[0] + "," + li[1] + "\n"
        else:
            continue
    except:
        continue
    fOut.write(sample)
    count += 1
    if int(li[1]) < idMin:
        idMin = int(li[1])
    if int(li[1]) > idMax:
        idMax = int(li[1])    
fInp.close()
fOut.close()
print "Data reduction finished.\nNumber of records:", count, \
      ". Film ids in range:", idMin, "...", idMax

Resultat:
Für eine typische Datensammlung erhält man die Ausgabe:

Data reduction finished.
Number of records: 82170 . Film ids in range: 1 ... 163949

Empfehlungslisten

Eine weitere Datenreduktion ergibt sich aus der Zusammenfassung der Empfehlungen jedes Users. Hat dieser also (unabhängig vomn Zeitpunkt) die Filme 31, 122, 546, und 333 emfohlen, so entsprich dies der Empfehlungsliste [31, 122, 546, 333]

Man kann eine solche Liste wie eine Einkaufliste für Produkte betrachten, d.h. jeder User "erzeugt" mit allen seinen Empfehlungen eine einzige Einkaufsliste. Grundsätzlich handelt es sich in diesem Kapitel um die gleichen Probleme wie im Kapitel "Affinitätsanalyse", in dem Einkaufslisten eines Supermarkts untersucht wurden.

Programm: [►]

# CreateSamples.py
# Group recommendations for every person (like a shopping list)

datRatings = "ratings.dat"
recData = "rec.dat"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def saveRecord(li):
    purchaseStr = [str(e) for e in li]                
    sample = ','.join(purchaseStr)
    fOut.write(sample + "\n")

samples = loadData(datRatings)
fOut = open(recData, "w")
myId = 1
li = []
count = 0
# precondition: recommendations of every person are consecutive
for sample in samples:
    personId = int(sample[0])
    if personId != myId:  # next person
        count += 1
        saveRecord(li)
        myId = personId
        li = [sample[1]]
    else:
        li.append(sample[1]) # same person
fOut.close()
print "Number of records:", count

Resultat:
Für eine typische Datensammlung erhält man die Ausgabe:

Number of records: 670

Es ist instruktiv, die entstandene Datei etwas unter die Lupe zu nehmen. Man erkennt, dass offenbar gewisse User sehr viele Empfehlungen abgegeben haben.

Extraktion der Affinitäten zwischen zwei Filmen

Gemeinsamkeiten von Filmen sollen so herausgefunden werden, dass untersucht wird, welche Paare von Filmen gemeinsam empfohlen werden. Ist diese Zahl für bestimmte Paare besonders hoch, so betrachtet man die Filme als besonders affin, da viele User den einen und den anderen Film positiv beurteilt haben. Im nachfolgenden Recommender-System wird dann einem User, der den einen Film bestellt, dazu besonders affine Filme zum Kauf empfohlen.

In diesem Schritt werden die interessanten Informationen wiederum in einer "Zwischendatei" affinity.dat abgepeichert, die dann einfach weiter verwendet werden kann. Diese Datei enthält zeilenweise und geordnet alle möglichen Filmpaare mit der Anzahl, wie oft diese Paare empfohlen wurden. Also tabularisch dargestellt:

Bei der Erstellung dieser Datei wird offenbar, dass die Verarbeitung grosser Datenmengen zu einer beträchtlichen Laufzeit führen kann und dass es darum notwendig ist, sich Mühe zu geben, den Code bezüglich der Laufzeit zu optimieren. Für lediglich die ersten 100 Filme kann die Laufzeit durchaus je nach verwendeter Computerhardware und Programmiersystem (Python 2.7 oder TigerJython) einige Minuten dauern. Darum wird im Programm die Laufzeit ausgeschrieben.

Um die vorhandenen Film-Ids zu bestimmen, wird die Datei movies.csv gelesen und die Ids in eine Liste movieIds gespeichert.

Programm: [►]

# CreatePairs.py

import time

numberOfMovies = 100
samples = "rec.dat"
affinity = "affinity.dat"
moviesInfo = "movies.csv"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def loadIntData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [int(i) for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def getMovieIds():
    movies = loadData(moviesInfo)
    movieIds = []
    for i in range(1,len(movies)):
        movieIds.append(int(movies[i][0]))
    return movieIds

X = loadIntData(samples)
startTime = time.time()
print "Working..."
fOut = open(affinity, "w")
movieIds = getMovieIds()
for id1 in movieIds[0:numberOfMovies]:
    for id2 in movieIds[id1:numberOfMovies]:
        nb = 0
        for recommendation in X:
            if id1 in recommendation and id2 in recommendation:
               nb += 1
        fOut.write(str(id1) + ";" + str(id2) + ";" + str(nb) + "\n")
fOut.close()
print "Done in", time.time() - startTime, "seconds."

Bemerkungen:
Es wäre sehr ineffizient, die Film-Ids statt als Integer als Strings einzulesen und den Test

if id1 in recommendation and id2 in recommendation:

mit Strings durchzufühen.

Wem es zu lange geht, kann die Datei affinity.dat für alle 9000 Filme von hier herunterladen.

Antworten auf interessante Fragen

Nach diesen Vorbereitungen sind wir endlich in der Lage, interessante Fragen zu beantworten.

1. Frage: Welches sind die Filme mit den meisten Empfehlungen?

Wir verwenden dazu die Datei rec.dat, welche die Empfehlungen enthält.

Programm: [►]

# Recommender1.py

from operator import itemgetter

samples = "rec.dat"
moviesInfo = "movies.csv"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def loadIntData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [int(i) for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def getMovieIds():
    movies = loadData(moviesInfo)
    movieIds = []
    for i in range(1,len(movies)):
        movieIds.append(int(movies[i][0]))
    return movieIds

def getMovieTitle(movieId):
    for movie in movies:
        try:
            if int(movie[0]) == movieId:
                return movie[1]
        except:
            continue
    return ""  

movies = loadData(moviesInfo)
recommendations = loadIntData(samples)
movieRatings = []
for movieId in getMovieIds():
    count = 0
    for recommendation in recommendations:
        if movieId in recommendation:
            count += 1
    movieRatings.append([movieId, count])
sortedRatings = sorted(movieRatings, key = itemgetter(1))
top = sortedRatings[-10:]  # last 10 elements
top.reverse()
for rank in range(10):
    movieId = top[rank][0]
    print "Rank ", rank + 1, ":", getMovieTitle(movieId)

Resultat:
Für eine typische Datensammlung erhält man die Ausgabe:

Rank 1 : Forrest Gump (1994)
Rank 2 : Pulp Fiction (1994)
Rank 3 : Shawshank Redemption
Rank 4 : Silence of the Lambs
Rank 5 : Star Wars: Episode IV - A New Hope (1977)
Rank 6 : Jurassic Park (1993)
Rank 7 : Matrix
Rank 8 : Schindler's List (1993)
Rank 9 : Star Wars: Episode V - The Empire Strikes Back (1980)
Rank 10 : Toy Story (1995)

2. Frage: Ein User wählt einen bestimmten Film. Welches sind die Filme mit der besten Affinität?

Wir verwenden dazu die Datei affinity.dat, um zum gewählten Film (Prämisse) die Filme mit den höchsten Affinitäten zu finden und diejenigen mit mindestens 20 Emfehlungen sortiert auszuschreiben. (Download affinity.dat für 100 Filme, für 3000 Filme.)

Programm: [►]

# Recommender2.py

from operator import itemgetter

affinity = "affinity.dat"
moviesInfo = "movies.csv"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def getCollection(fileName, premise):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        li = [int(i) for i in line.split(";")]
        if premise == li[0]:
            out.append(li)
        elif premise == li[1]:
            out.append([li[1], li[0], li[2]])   # exchange first two elements 
    fData.close()
    return out

def getMovieTitle(movieId):
    for movie in movies:
        try:
            if int(movie[0]) == movieId:
                return movie[1]
        except:
            continue
    return ""       

def getAll():
    sum = 0
    for item in collection:
        sum += item[2]
    return sum


movies = loadData(moviesInfo)

premise = 3  # selected movieId
collection = getCollection(affinity, premise)
collection = sorted(collection, key = itemgetter(2)) # sort by number
collection = collection[::-1] # reverse list
print "Ordered affinities with movie --->", getMovieTitle(premise)
print "---------------------------------------------------"
for item in collection:
    if item[2] < 20:
        break
    print  item[2], "persons --->", getMovieTitle(item[1])

Resultat:
Für eine typische Datensammlung erhält man die Ausgabe:

Ordered affinities with movie ---> Grumpier Old Men (1995)
---------------------------------------------------
31 persons ---> Independence Day (a.k.a. ID4) (1996)
27 persons ---> Rock
26 persons ---> Twister (1996)
26 persons ---> Toy Story (1995)
25 persons ---> Willy Wonka & the Chocolate Factory (1971)
25 persons ---> Fargo (1996)
24 persons ---> Phenomenon (1996)
24 persons ---> Mission: Impossible (1996)
24 persons ---> Twelve Monkeys (a.k.a. 12 Monkeys) (1995)
23 persons ---> Executive Decision (1996)
23 persons ---> Star Wars: Episode IV - A New Hope (1977)
22 persons ---> Forrest Gump (1994)
21 persons ---> Broken Arrow (1996)
20 persons ---> Jurassic Park (1993)
20 persons ---> Birdcage
20 persons ---> Sabrina (1995)

3. Frage: Welches ist zu jedem Film derjenige mit der besten Affinität?

Das Programm ist fast identisch mit dem vorhergehenden, aber es wird nur der Film mit der höchsten Affinität bestimmt und in eine Datei geschrieben..

Programm: [►]

# Recommender3.py

from operator import itemgetter

affinity = "affinity.dat"
moviesInfo = "movies.csv"
bestAffinity = "bestaffinity.dat"

def loadData(fileName):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        line = line[:-1]  # remove \n
        if len(line) == 0:  # empty line
            continue
        li = [i for i in line.split(",")]
        out.append(li)
    fData.close()
    return out

def getSamples(fileName, premise):
    try:    
        fData = open(fileName, 'r')
    except:
        return []
    out = []
    for line in fData:
        li = [int(i) for i in line.split(";")]
        if premise == li[0]:
            out.append(li)
        elif premise == li[1]:
            out.append([li[1], li[0], li[2]]) # exchange first two elements 
    fData.close()
    return out

def getMovieIds():
    movieIds = []
    for i in range(1,len(movies)):
        movieIds.append(int(movies[i][0]))
    return movieIds

def getMovieTitle(movieId):
    for movie in movies:
        try:
            if int(movie[0]) == movieId:
                return movie[1]
        except:
            continue
    return ""       

fOut = open(bestAffinity, "w")
myId = 1
movies = loadData(moviesInfo)
movieIds = getMovieIds()[0:100]
print "Starting..."
fOut.write("Movie --->  Movie with best affinites\n")
for premise in movieIds:
    samples = getSamples(affinity, premise)
    samples = sorted(samples, key = itemgetter(2)) # sort by number
    last_sample = samples[-1]
    highest = last_sample[1]
    fOut.write(getMovieTitle(premise) + " --> " + getMovieTitle(highest) + "\n")
fOut.close()
print "all done"

Resultat:
Für eine typische Datensammlung findet man in der Datei bestaffinities.dat die 10 ersten Zeilen:

Toy Story (1995) --> Forrest Gump (1994)
Jumanji (1995) --> Forrest Gump (1994)
Grumpier Old Men (1995) --> Independence Day (a.k.a. ID4) (1996)
Waiting to Exhale (1995) --> Silence of the Lambs
Father of the Bride Part II (1995) --> Mission: Impossible (1996)
Heat (1995) --> Pulp Fiction (1994)
Sabrina (1995) --> Independence Day (a.k.a. ID4) (1996)
Tom and Huck (1995) --> Independence Day (a.k.a. ID4) (1996)
Sudden Death (1995) --> Executive Decision (1996)
GoldenEye (1995) --> Jurassic Park (1993)
American President --> Forrest Gump (1994)
Dracula: Dead and Loving It (1995) --> Independence Day (a.k.a. ID4) (1996)