Собрав данные о том, что людям нравится, нужно как-то определить, насколько их вкусы схожи. Для этого каждый человек сравнивается со всеми другими и вычисляется коэффициент подобия (или оценка подобия). Для этого есть несколько способов, я расскажу о двух из них: евклидовом расстоянии и коэффициенте корреляции Пирсона. Примеры будем разбирать, отталкиваясь от задачи поиска схожести вкусов людей к фильмам, исходя из их оценок.

У коэффициента корреляции Пирсона есть одно интересное свойство, которое можно наблюдать на рисунке – он корректирует обесценивание оценок! Что я имею ввиду? А то, что представьте. 2 человека сравнивают цены и 2й всегда ставит на 1-2 бала ниже(ну пессимист он эдакий)))) А теперь начертите прямую в голове(или листочке)) и увидите, что прямая все равно проходит почти по диагонали, а значит считает, что они могут понравиться друг-другу (сугубо с точки зрения вкусов к фильмам…а может и нет))))!

Проблема нормализации

Но также у данного коэффициента есть одна плохая сторона. Он рассчитан наприменение к данным с нормальным распределением. А что будет, если какой то пользователь ставит всем фильмам одинаковые оценк
и? Можете подставить в формулу, например за место X и увидите, что в таком случае и знаменатель и числитель вырождаются в 0! Ведь это не правильно! Бывает так, что вы смотрели вместе 10 великолепных картин и он и вы ставили только 10ки и получается, что заместо коэффициента=1 мы получим 0! Геометрически такое поведение можно объяснить вырождением прямой в точку. Не знаю, как эта проблема решается правильно, а я предлагаю сделать искусственную нормализацию распределения оценок. Каким образом, а просто добавим и тому и другому оценку за несуществующий фильм отличную от тех, что они ставят, но одинаковые между собой. Причем опытным путем было замечено. что чем оценка меньше, тем меньше она влияет на коэффициент.

select
v1.user_id, v2.user_id,
1/(1+(|/sum((v1.vote-v2.vote)^2))),--евклидово не взвешенное расстояние
count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.film_id=v2.film_id 
and v1.user_id < v2.user_id --гениально и просто убираем дубли self джойна))
where v1.user_id <> v2.user_id
--and v2.user_id=113
group by v1.user_id, v2.user_id
order by 1/(1+(|/sum((v1.vote-v2.vote)^2))) desc, count(1) desc

У меня он выдал 197184 результата за 703882 ms. Короче чуть не уснул и это тысячах на 6 юзверях, но если вы подождете, то будете вознаграждены) Поиск же для кого-то конкретного проходит на ура и в миллисекунды 🙂 Нужно сразу сказать, что здесь ф-ия евклида вычисляется для мнений по одному и тому же фильму и по этому эта оценка не взвешенная! Например есть люди, которые идеально друг другу подходят (т.е. 1 выдало 😉 и все потому, что у них всего 1 общий фильм из 1000 и каждый поставил по 2 балла)))) Не думаю, что таких людей можно рекомендовать друг-дружке, как братьев по вкусу))) Поэтому результаты нужно взвесть и чем больше общих фильмов оценено — тем лучше(если что count(1) именно это и считает)

#Для ярых питонистов плюющих в души sql ворую код
# на вход prefs - словарь {чел1:{фильм1:оценка1, фильм2:оценка2,...}, чел2:{фильм?:оценка?,...}}
# кто-то может расширить ф-ию сравнения не 2х челов, а N :)
from math import sqrt

def sim_distance(prefs):

person1, person2 = prefs.keys()

# Получаем список фильмов, оцененных обоими
si={item:1 for item in prefs[person1] if item in prefs[person2]}

if si:

# сложить квадраты разностей оценок
sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2)
for item in prefs[person1] if item in prefs[person2]])

return 1/(1+sqrt(sum_of_squares))#sqrt добавил сам, кажись автор забыл)

# если нет ни одной общей оценки, return 0
return 0

Практика Пирсона

select
    v1.user_id, v2.user_id,
    case when (sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float) <> 0
    then
        (sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float)))
    else
        0
    end,
    count(1)--кол-во общих фильмов(вес для ф-ии)
from votes v1
join votes v2 on v1.film_id=v2.film_id 
where v1.user_id <> v2.user_id 
and v2.user_id=113 --ищем для конкретного пользователя(так быстрее)
group by v1.user_id, v2.user_id
order by 
    case when (sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float) <> 0
    then
        (sum(v1.vote*v2.vote)-(sum(v1.vote)*sum(v2.vote))/count(1)::float)/(|/((sum(v1.vote^2)-(sum(v1.vote)^2)/count(1)::float)*(sum(v2.vote^2)-(sum(v2.vote)^2)/count(1)::float)))
    else
        0
    end
    desc,
    count(1) desc

Снова сворую чужую функцию для Питонистов, но теперь с решением проблемы нормализации:

#На вход тоже, что и раньше
def sim_pearson(prefs):

#вспомогательная ф-ия для удаления повторяющейся оценки
def rem_vote(votes, choice_list):
vote_for_rem = votes.pop()
if vote_for_rem in choice_list:
choice_list.remove(vote_for_rem)
return choice_list#это не обязательно, т.к. элемент и так удален по ссылке, но явное лучше не явного)))

# Получаем список фильмов, оцененных обоими
si={}
p1, p2 = prefs.keys()

for item in prefs[p1]:
if item in prefs[p2]: si[item]=1

#делаем нормализацию, если кто-то ставит одинаковые оценки всем фильмам
#опытным путем пришел к тому, что чем меньше число добавляем, тем меньше его влияние
votes1 = set([prefs[p1][it] for it in si])
votes2 = set([prefs[p2][it] for it in si])

if len(votes1) == 1 or len(votes2) == 1:

choice_list = range(1, 4)#список возможных оценок от 1 до 4
#удаляем повторяющиеся оценки
if len(votes1) == 1:
choice_list = rem_vote(votes1, choice_list)
if len(votes2) == 1:
choice_list = rem_vote(votes2, choice_list)

it = 0#id несуществующего фильма
si[it] = 1#говорим, что оба оценивали фильм с этим id
rand_vote = random.choice(choice_list)
prefs[p1][it] = prefs[p2][it] = rand_vote
##############################

# Число общих фильмов
n=len(si)

# Если общих фильмов нет
if n==0: return 0

# Суммы всех предпочтений
sum1=sum([prefs[p1][it] for it in si])
sum2=sum([prefs[p2][it] for it in si])

# Суммы квадратов предпочтений
sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
sum2Sq=sum([pow(prefs[p2][it],2) for it in si])

# Сумма произведений
pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])

# Вычисляем коэффициент
num=pSum-(sum1*sum2/n)
den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
if den==0: return 0

r=num/den

return r

Немного о чувствительности критериев

К слову о том, каким критерием пользоваться, не стоит забывать об их чувствительности к деградации. О чем я? Например я сравнил себя с другим пользователем и оказалось, что мы оценили 5 общих фильмов. Причем он всем поставил 10 баллов, а я двум 9ки. Таким образом я потерял 2/50 не взвешенных баллов от 1. Но если мы вычислим реальные коэффициенты, то получим следующие результаты: Евклид=0.414, Пирса=0.981. Таким образом видно, что ф-ия Евклида очень чувствительна при малом кол-ве общих оценок.

Советую почитать

• http://forexaw.com/TERMs/Economic_terms_and_concepts/Exchange_Terminology/l675_Корреляция_Correlation_это