Prawdopodobnie większość czytelników zna serwis Last.Fm, gdzie jedną z funkcjonalności jest możliwość porównania swojegu gustu muzycznego z innym użytkownikiem (w polskiej wersji językowej nazwane zostało to "Gustometr").

W tym artykule opiszę jak uzyskać zbliżoną funkcjonalność.

Jako platformy rozwojowej użyłem Django w wersji 0.96.1 (niemniej korzystam jedynie z wbudowanego ORM celem prostszego dostępu do danych znajdujących się w bazie danych).

Czytelników, którzy nie posiadają zainstalowanego frameworka odsyłam do strony projektu, gdzie mogą pobrać pakiet instalacyjny i przeczytać opis instalacji. Niezbędna będzie jeszcze baza danych (ja użyłem PostgreSQL w wersji 8.2) i odpowiedni moduł pythonowy (w moim przypadku pakiet python-psycopg2 w ubuntu).

Z założeń - projekt djangowy zostanie założony w katalogu $HOME/python.

Zaczynamy więc, tworzymy projekt o nazwie gusta:

mkdir -p $HOME/python
cd $HOME/python
django-admin.py startproject gusta
cd gusta

Teraz ustawiamy zmienne systemowe wymagane przez django:

export DJANGO_SETTINGS_MODULE=gusta.settings
export PYTHONPATH=$HOME/python

W ramach projektu gusta tworzymy aplikację dane, która będzie służyć do składowania danych:

django-admin.py startapp dane

Teraz tworzymi odpowiednie modele:

emacs dane/models.py

Plik models.py wygląda następująco:

from django.db import models

class Osoba(models.Model):
    # w tym modelu zapisujemy osoby
    imie = models.CharField(maxlength=32, unique = True)

class Wykonawca(models.Model):
    # w tym modelu przechowujemy wykonawców
    nazwa = models.CharField(maxlength = 128, unique = True)

class Ocena(models.Model):
    # w tym modelu przechowujemy punktację
    punkty = models.IntegerField()
    wykonawca = models.ForeignKey(Wykonawca)
    osoba = models.ForeignKey(Osoba)

Edytujemy teraz plik settings.py dodając ustawienia do naszej bazy danych oraz dodajemy aplikację dane:

emacs settings.py

Odpowiednie fragmenty powinny wyglądać następująco:

DATABASE_ENGINE = 'postgresql_psycopg2'
DATABASE_NAME = 'gusta'
DATABASE_USER = 'bluszcz'
INSTALLED_APPS = (
    'django.contrib.auth',
    'django.contrib.contenttypes',
    'django.contrib.sessions',
    'django.contrib.sites',
    'gusta.dane'
)

Tworzymy bazę danych (zmieniając nazwę użytkownika oczywiście ;) ):

createdb gusta -O bluszcz

Teraz tworzymy modele djangowe w bazie danych:

django-admin.py syncdb

Ostatnim etapem jest wczytanie danych testowych (django udostępnia mechanizm fixtures):

django-admin.py loaddata oceny.json

Ok, co do algorytmu wyliczenia podobieństwa. Wyciągnijmy z testowej bazy kilka głosów:

In [1]: from gusta.dane.models import Osoba, Wykonawca, Ocena

In [2]: ocena1 =  Ocena.objects.filter(osoba = Osoba.objects.get(imie = 'Rafał'))

In [4]: ocena1.get(wykonawca = Wykonawca.objects.get(nazwa = 'The Cure')).punkty
Out[4]: 4

In [5]: ocena1.get(wykonawca = Wykonawca.objects.get(nazwa = 'Joy Division')).punkty
Out[5]: 6

In [6]: ocena2 =  Ocena.objects.filter(osoba = Osoba.objects.get(imie = 'Joanna'))

In [7]: ocena2.get(wykonawca = Wykonawca.objects.get(nazwa = 'The Cure')).punkty
Out[7]: 6

In [8]: ocena2.get(wykonawca = Wykonawca.objects.get(nazwa = 'Joy Division')).punkty
Out[8]: 6

In [9]: ocena1.get(wykonawca = Wykonawca.objects.get(nazwa = 'The Cure')).punkty
Out[9]: 4

In [10]: ocena3 =  Ocena.objects.filter(osoba = Osoba.objects.get(imie = 'Agnes'))

In [11]: ocena3.get(wykonawca = Wykonawca.objects.get(nazwa = 'The Cure')).punkty
Out[11]: 1

In [12]: ocena3.get(wykonawca = Wykonawca.objects.get(nazwa = 'Joy Division')).punkty
Out[12]: 1

Zwizualizujmy głosy na zespoły The Cure i Joy Division (zespoły są osiami, a głosy punktami na wykresie). W ten sposób widzimy jak blisko siebie są osoby (jeśli pod uwagę weźmiemy te dwa zespoły i daną trójkę słuchaczy).

[img:2]

Aby obliczyć odłegłość między jedną osobą a drugą posłużę się funkcją nazwaną odległością euklidesową - jej opis znajdziemy na stronach wikipedii. Ponieważ zależy nam na zamknięciu wyników w przedziale <0,1>, dodajemy jeden do wyniku funkcji i odwracamy (udokumentowane w poniższym kodzie).

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from math import sqrt
from gusta.dane.models import Osoba, Wykonawca, Ocena
def get_distance(osoba1, osoba2):
    """ Funkcja zwracająca informację o tym,
        jak bardzo podobny gust mają dwie osoby.
        Funkcja zwraca wartości typu float
        od 0 do 1 gdzie:
        0 oznacza najmniejszą zgodność,
        1 oznacza największą zgodność """

    # słownik wspólnych wykonawców
    wspolne = {}

    # pobieramy oceny wykonawców dla [osoba1, osoba2]
    ocena1 =  Ocena.objects.filter(osoba = Osoba.objects.get(imie = osoba1))
    ocena2 =  Ocena.objects.filter(osoba = Osoba.objects.get(imie = osoba2))
    wykonawcy1 = [ x.wykonawca.nazwa for x in ocena1]
    wykonawcy2 = [ x.wykonawca.nazwa for x in ocena2]
    for wykonawca in wykonawcy1:
        if wykonawca in wykonawcy2:
            """ jeśli dany wykonawca został oceniony przez obydwie osoby
                zostaje dodany do słownika """
            wspolne[wykonawca] = 1

    # jeśli nie mają wspólnyh wykonawców - zwracamy zero
    if len(wspolne)==0:
        return 0
    lista = []
    for wykonawca in wykonawcy1:
        if wykonawca in wykonawcy2:
            o1 = float(ocena1.get(wykonawca = Wykonawca.objects.get(nazwa = wykonawca)).punkty)
            o2 = float(ocena2.get(wykonawca = Wykonawca.objects.get(nazwa = wykonawca)).punkty)
            lista.append(pow(o1-o2,2))

    # zwracamy miernik gustu
    # używamy odległości euklidesowej - aby maksymalny zbieżność 
    # wynosiła jeden odwracamy wynik (1 dielimy na sumę odległości zsumowaną 
    # z jedynką celem uniknięcia dzielenie przez zero
    return 1/(1+sqrt(sum(lista)))

def print_distance(osoba1, osoba2):
    # funkcja pomocnicza służąca do drukowania zgodności w czytelnej postaci
    print "%s,%s = " % (osoba1, osoba2) , get_distance(osoba1, osoba2)

print_distance('Rafał', 'Joanna')
print_distance('Sebastian', 'Joanna')
print_distance('Rafał', 'Sebastian')
print_distance('Joanna', 'Sebastian')
print_distance('Joanna', 'Agnes')
print_distance('Joanna', 'Krzysiek')

Testujemy:

[23:55:27] bluszcz@amnezja:~/private/python/gusta
$ python pokaz_gusta.py
Rafał,Joanna =  0.333333333333
Sebastian,Joanna =  0.217129272955
Rafał,Sebastian =  0.333333333333
Joanna,Sebastian =  0.217129272955
Joanna,Agnes =  0.0994491992363
Joanna,Krzysiek =  0.11606619484
[23:55:31] bluszcz@amnezja:~/private/python/gusta
$ 

Proszę zachować dane - będziemy na nich bazować w następnych częściach :)