Рекомендательные системы

Что это за системы, почему они окутаны завесой "тайны", что они делают и как у них такое получается? Как вообще возможно, что бы компьютер рекомендовал человеку фильмы и книги?

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

Давайте взглянем изнутри, на эту "магию".
Методов определения "похожести" тех или иных данных по какому либо из критериев существует множество и они широко известны. К ним относятся евклидово расстояние или коэффициент корреляции Пирсона или коэффициент Жаккарда или манхеттенское расстояние и множество других. Однако, обо всем по порядку.

Рынок рекомендаций

С ростом количества контента в сети интернет наиболее остро встает задача подбора тех товаров или услуг, в которых заинтересован конкретный пользователь. Причем, эта задача касается как подбора правильных рекламных баннеров, так и наиболее интересных для пользователя книг, фильмов, сайтов и прочего. От выработки правильных рекомендаций, зачастую зависит успех сервиса в сети и его аудитория. Если пользователю предлагают такие фильмы о которых он и не слышал и, они ему понравятся, то пользователь вернется на такой сайт еще раз.

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

Наиболее распространенные методики

При всем потенциале рынка и разнообразии объектов рекомендаций наибольшее распространение получили алгоритмы так называемой "коллаборативной фильтрации". Хотя, лежащие в его основе методы поиска подобия элементов на основе неких абстрактных величин, известны и применяются уже давно. К таковым методам относится евклидово расстояние или коэффициент корреляции Пирсона, однако термин "коллаборативной фильтрации" был впервые употреблен Дэвидом Голдбергом в 1992 году в статье "Using collaborative filtering to weave an information tapestry".

Алгоритм коллаборативной фильтрации по схожести пользователей

Алгоритм сводится к просмотру большой группы людей и отысканию в ней меньшей группы подобных друг другу, по какой либо метрике. Например, по выставленной оценке одному и тому же фильму. Ранжирования общего списка предпочтений для этой группы с последующим использованием полученного списка для всех людей (членов меньшей группы).

Алгоритм коллаборативной фильтрации по схожести образцов

Является небольшим улучшением фильтрации по схожести пользователей, но по сути своей отличается от него очень мало. Разница лишь в том, что на больших объемах данных неэффективно вычислять схожесть пользователей, в то время как схожесть образцов (товаров) является величиной статичной. Поэтому заранее вычислив схожесть образцов можно существенно сократить количества вычислений при формирования списка предпочтений для членов меньшей группы.

Вычисление степени подобия по евклидову расстоянию

  public static double calculateEuclideanDistance(List lst1, 

                                                  List lst2) {

    if (lst1==null||lst2==null) return 0;

    // Пересечение множеств

    boolean isEmpty = true;

    for (int i=0;i      if(lst2.contains(lst1.get(i))){isEmpty=false;break;}

    }

    if (isEmpty) return 0;

    // Квадраты разностей

    double sumq = 0.0;

    for (int i=0;i      Item ref1 = lst1.get(i);

      Item ref2 = null;

      for (int j=0;j        if(ref1.equals(lst2.get(j))){ref2=lst2.get(j);break;}

      }

      if(ref2!=null) sumq+=Math.pow(ref1.getRating()-

                                    ref2.getRating(),2);

    }

    return 1.0d/(1.0d+Math.sqrt(sumq));

  }

Вычисление степени подобия по коэффициенту корреляции Пирсона

  public static double calculatePearsonCoefficient(List lst1, 

                                                   List lst2) {

    if (lst1==null&&lst2==null) return 0;

    if (lst1!=null&&lst2==null||lst2!=null&&lst1==null) return -1;

    // Пересечение множеств

    List si = new LinkedList();

    for (int i=0;i      Item e=lst1.get(i); if(lst2.contains(e))si.add(e);

    }

    if (si.size()==0) return 0;

    // Простые суммы

    double sum1 = 0.0; double sum2 = 0.0;

    for (int i=0;i      Item e=lst1.get(i);if(si.contains(e))sum1+=e.getRating();

    } 

    for (int i=0;i      Item e=lst2.get(i);if(si.contains(e))sum2+=e.getRating();

    }

    // Суммы квадратов

    double sumq1 = 0.0; double sumq2 = 0.0;

    for (int i=0;i      Item e=lst1.get(i);

      if(si.contains(e))sumq1+=Math.pow(e.getRating(),2);

    } 

    for (int i=0;i      Item e=lst2.get(i);

      if(si.contains(e)) sumq2+=Math.pow(e.getRating(),2);

    }

    // Сумма произведений

    double sump = 0.0; 

    for (int i=0;i      Item e1 = lst1.get(i);

      Item e2 = null;

      for (int j=0;j        if(e1.equals(lst2.get(j))){e2=lst2.get(j);break;}

      }

      if (e2!=null) sump+=(e1.getRating()*e2.getRating()); 

    }

    double num=sump-(sum1*sum2/si.size());

    double den=Math.sqrt((sumq1-Math.pow(sum1,2)/si.size())*

                        (sumq2-Math.pow(sum2,2)/si.size()));

    if (den==0) return 0;

    return (num/den);

  }

Особенности наиболее распространенных методик

Среди особенностей коллаборативной фильтрации (самых распространенных методик) можно выделить такие:

• Преобладающие матричные вычисления, при вычислении коэффициентов подобия, которые не всегда легко адаптировать для параллельных вычислений на распределенном кластере;
• Унифицированные методы вычисления коэффициента подобия по 2-ум характеристика, даже если элементы имеют несколько характеристик, зачастую, все они сводятся к такому виду, что бы можно было легко найти геометрически близкие на плоскости элементы;
• Детерминированность методов вычисления подобия не позволяет работать с плохо формализуемыми свойствами рекомендуемых образцов;
• Зачастую, подобие образцов можно сформировать более эффективно на основе совершенно других признаков, нежели выставленных пользователями оценок (например, по ценовым диапазонам или по соотношению цены и качества и прочему);
• Результат рекомендации образцов детерминирован, предсказуем и основывается не на индивидуальных предпочтениях конкретного пользователя, а на усредненных "групповых" предпочтениях;
• Очень важным недостатком коллаборативной фильтрации является её "слепость" к новым образцам. Т.е. пока новому образцу не выставлена хотя бы одна оценка, он не попадает в рекомендательную выдачу.

Почему это работает плохо

Далее, рассмотрим некоторые особенности личности и, постараемся ответить на вопрос - насколько адекватны рекомендации хомяков, по критерию понравился/не понравился пылесос для чернокожего русского из Бруклина, по методу Голдберга...

Типы характеров по К. Леонгарду – демонстративный, педантичный, застревающий, возбудимый

Характер (греч. — "чеканка", "отпечаток") есть совокупность устойчивых индивидуальных особенностей личности, складывающихся и проявляющихся в деятельности и общении, обусловливающих типичные для нее способы поведения. Те особенности личности, которые относятся к характеру, называют чертами характера. Черты характера — это не случайные проявления личности, а устойчивые особенности поведения человека, особенности, которые стали свойствами самой личности. В характере выражаются не случайные, а наиболее типичные, существенные особенности человека. 


Демонстративный тип, который получил свое название из-за способности людей подобного типа очень сильно выражать свои эмоции, с точки зрения окружающих — более сильно, чем они их переживают в данный момент. У демонстративной личности развита способность вытеснять из сознания некоторые травмирующие представления: она может лгать, не сознавая, что лжет, при этом ложь демонстративной личности отличается от сознательной лжи притворяющегося человека. Она не притворяется, а действительно в данный момент верит в то, в чем пытается убедить окружающих. Демонстративная личность глубоко вживается в требуемый ситуацией образ, ей присуща высокая артистичность в выражении любого чувства: горя, восхищения и т. д. Излюбленные образы, в которые перевоплощается демонстративная личность – невинная жертва, человек, которого не оценили, злоупотребили его доверием, использовали его редкие душевные и интеллектуальные качества и пр., либо благодетель человечества, уникальный специалист, нежное, тонкое существо, нуждающееся в неустанной опеке. При положительном социальном развитии демонстративная личность может стать прекрасным писателем, актером, социальным работником — благодаря умению вжиться в другой образ, понять другого человека.

Демонстративный тип часто восприимчив к сюжету фильма, имеет склонность к мелодраматичности, характерен частой сменой “фокуса” интересов. Очень ценит свою индивидуальность и слабо восприимчив к рекомендованным по коллаборативному принципу образцам.

Противоположностью демонстративному является педантичный характер. Если демонстративная личность принимает решения стремительно, импульсивно, процесс обдумывания сведен к минимуму, то педантичная личность долго колеблется и тщательно обдумывает свои действия. Негативными чертами такого характера могут быть нерешительность, боязнь несчастного случая или ошибки, что вызывает необходимость постоянно проверять и перепроверять свои действия выключен ли газ, нет ли в отчете ошибки, не грязные ли руки и пр., если, конечно, это не единичные случаи, а устойчивое поведение. Но, как известно, наши достоинства являются продолжением наших недостатков, и педантичный характер может выразиться в таких прекрасных качествах, как пунктуальность, аккуратность, ответственность, предусмотрительность, рассудительность, забота о собственном здоровье, избежание эксцессов — словом, весь комплекс, которого демонстративной личности явно не хватает.

Педантичный тип наиболее склонен к восприятию рекомендаций по коллаборативному принципу. Тщательное обдумывание при принятии решения часто опирается на чужой опыт (советы).

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

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

У возбудимых личностей так же, как у демонстративных и застревающих, часто констатируется весьма неровное течение жизни, однако не потому, что они постоянно избегают трудностей, а потому, что часто высказывают недовольство, проявляют раздражительность и склонность к импульсивным поступкам, не утруждая себя взвешиванием последствий. Неумение управлять собой ведет к конфликтам.

Выбор возбудимого типа всегда больше спонтанен, нежели осознан и продиктован необходимостью. Наиболее сложный для выработки рекомендаций тип характера. Так же слабо восприимчив к рекомендациям по коллборативному принципу.

Даже используя такую, относительно примитивную, классификацию характера, можно заметить, что коллаборативная фильтрация это инструмент из "другого мира". Он не предназначен для учета ваших персональных предпочтений и особенностей, скорее коллективных. Возможно, менталитет рядового американца и соответствует среднестатистическому и, поэтому, к нему применимы такие коллективные методы. В русскоязычной части интернета индивидуальность пользователей, при выборе контента, все же доминирует на стадным чувством. Поэтому применение методов коллаборативной фильтрации может быть не эффективным.

Пример рекомендательной системы

Если коллаборация не работает или работает плохо, и если все такие разные то, спросите вы, где же та "серебряная пуля" или как построить "правильную" рекомендательную систему? Уверен, что ответ в синергии нескольких подходов. Т.е. в создании такой рекомендательной системы, которая может рекомендовать образцы множеством различных методов (среди которых есть и коллеборативная фильтрация) и умеет адаптироваться под конкретного пользователя, максимально учитывая его сезонность, региональные особенности, настроение, и прочее...

Пример такой рекомендательной системы, созданной мною, в настоящий момент эксплуатируется в VOD сервисе Yota.Play - http://yotaplay.ru (не забываем регистрироваться).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Выводы

1) "Магия" рекомендаций сильно преувеличена и коллаборативная фильтрация работает "правильно" только для ограниченного круга людей (в лабораторных условиях).

2) Пирсон - это всегда лучше чем Жаккард (при вычислении коэффициента подобия).

3) Создавайте новое, а не копируйте алгоритмы и метОды 70х гг. прошлого века, какими бы модными они сегодня не были.

4) Учитывайте специфику своей аудитории и индивидуальность каждого человека.

"Новости для меня" или в чём отличие rss4me от множества аггрегаторов?

Здравствуйте уважаемые!

Очень часто пользователи задают один и тот же вопрос: в чём отличие сервиса RSS для Меня от множества существующих подобных RSS аггрегаторов?

Я люблю отвечать анекдотом:

Блондинка в магазине сотовой связи.
- скажите пожалуйста, а в чем отличие между этим и этим телефонами?
- девушка, отличие в том, что это фотоаппарат, а это видеокамера.

Что предоставляют множество существующих RSS аггрегаторов?

Они объединяют множество указанных вами RSS источников в одну общую ленту. Далее эту ленту можно читать прямо на сайте аггрегатора. Так делает и Яндекс и Kanban и Google Reader и еще многие другие. Чтение новостей на сайте - это один из самых не удобных способов чтения, который отнимает время и зачастую сопровождается рекламой. А когда в общую ленту попадают и профессиональные новости и анекдоты и прочий мусор это перестает быть лентой новостей, а превращается в мутный поток среди которого следует выискивать действительно интересное. Проблемы конечно не стоит, если вы весь день перечитываете мутные потоки или переписываетесь в одноклассниках. Если же вы цените свое время, тогда продолжим.

Они (RSS аггрегаторы) требуют обязательной регистрации, что бы вы могли создать один или более мутных потоков.

Они (RSS аггрегаторы) редко позволяют вам читать результирующий, хоть и мутный, поток внешними средствами. Например, стационарными RSS клиентами.

Некоторые из них (RSS аггрегаторов), например, такие как Яндеск умеют искать по ключевым словам в блогах. Но проблема в том, что поиск производится в том же множестве в котором производится и обычный интернет поиск. В результате, в отфильтрованный мутный поток начинают попадать обрывки чужих переписок или комментариев в форумах, а то куски текста и вовсе на неизвестных вам языках.

Что хочется от RSS аггрегатора?

Без регистрации и анонимно объединить несколько вами выбранных источников новостей в одну RSS ленту и повыкидывать из нее весь мусор. Или загрузить все свои ленты как один OPML файл. Ограничить сферу интересов ключевыми словами (через запятую). Затем получить URL адрес этой ленты и иметь уже не мутный, а отфильтрованный поток в какой нибудь RSS клиент (с чтением на сайте или в off-line). Конечно, хочется среди источников новостей выбирать не только специализированные форматы (RSS или Atom), но и простую HTML страницу. Хочется что бы сервис сам вырезал рекламу из новостей, а она уже там появляется. Ну и хочется иметь более точный фильтр нежели поиск в Яндексе.

Все это и есть сервис RSS для Меня.

Экономьте свое время!