Система за съвместна филтрираща препоръка в Java

1. Въведение

В този урок ще научим всичко за алгоритъма Slope One в Java.

Ще покажем и примерната реализация за проблема за съвместно филтриране (CF) - техника за машинно обучение, използвана от препоръчителни системи .

Това може да се използва, например, за прогнозиране на потребителски интереси за конкретни елементи.

2. Съвместно филтриране

Алгоритъмът Slope One е система за съвместно филтриране, базирана на елементи. Това означава, че тя се основава изцяло на класирането на потребителските позиции. Когато изчисляваме сходството между обектите, ние знаем само историята на класирането, а не самото съдържание. След това това сходство се използва за прогнозиране на потенциални потребителски класирания за двойки потребителски елементи, които не присъстват в набора от данни.

Изображението по-долу показва пълния процес на получаване и изчисляване на рейтинга за конкретния потребител:

Отначало потребителите оценяват различни елементи в системата. След това алгоритъмът изчислява приликите. След това системата прави прогнози за рейтинги на потребителски елементи, които потребителят все още не е оценил.

За повече подробности по темата за съвместното филтриране можем да се обърнем към статията в Уикипедия.

3. Алгоритъм на наклон

Slope One беше посочен като най-простата форма на нетривиално съвместно филтриране на елементи въз основа на рейтинги. Той взема предвид както информацията от всички потребители, оценили един и същ елемент, така и от останалите елементи, оценени от същия потребител, за да се изчисли матрицата за сходство.

В нашия прост пример ще предвидим класиране на потребителите за артикулите в магазина.

Нека започнем с прост Java модел за нашия проблем и домейн.

3.1. Модел на Java

В нашия модел имаме два основни обекта - елементи и потребители. Класът Item съдържа името на елемента:

private String itemName;

От друга страна, потребителският клас съдържа потребителското име:

private String username;

И накрая, имаме клас InputData, който ще се използва за инициализиране на данните. Нека приемем, че ще създадем пет различни продукта в магазина:

List items = Arrays.asList( new Item("Candy"), new Item("Drink"), new Item("Soda"), new Item("Popcorn"), new Item("Snacks") );

Освен това ще създадем трима потребители, които произволно са оценили някои от гореспоменатите, използвайки скалата от 0.0-1.0, където 0 означава липса на интерес, 0.5 по някакъв начин заинтересовани и 1.0 означава напълно заинтересовани. В резултат на инициализацията на данни ще получим Карта с данни за класиране на потребителски елементи:

Map
    
      data;
    

3.2. Матрици на разликите и честотите

Въз основа на наличните данни ще изчислим връзките между елементите, както и броя на появите на елементите. За всеки потребител проверяваме неговата / нейната оценка на артикулите:

for (HashMap user : data.values()) { for (Entry e : user.entrySet()) { // ... } }

В следващата стъпка проверяваме дали елементът съществува в нашите матрици. Ако това се случва за първи път, ние създаваме новия запис в картите:

if (!diff.containsKey(e.getKey())) { diff.put(e.getKey(), new HashMap()); freq.put(e.getKey(), new HashMap()); } 

Първата матрица се използва за изчисляване на разликите между потребителските оценки. Стойностите му могат да бъдат положителни или отрицателни (тъй като разликата между рейтингите може да е отрицателна) и се съхраняват като Double . От друга страна, честотите се съхраняват като Integer стойности.

В следващата стъпка ще сравним оценките на всички елементи:

for (Entry e2 : user.entrySet()) { int oldCount = 0; if (freq.get(e.getKey()).containsKey(e2.getKey())){ oldCount = freq.get(e.getKey()).get(e2.getKey()).intValue(); } double oldDiff = 0.0; if (diff.get(e.getKey()).containsKey(e2.getKey())){ oldDiff = diff.get(e.getKey()).get(e2.getKey()).doubleValue(); } double observedDiff = e.getValue() - e2.getValue(); freq.get(e.getKey()).put(e2.getKey(), oldCount + 1); diff.get(e.getKey()).put(e2.getKey(), oldDiff + observedDiff); }

Ако някой е оценил елемента преди, ние увеличаваме броя на честотите с един. Освен това проверяваме средната разлика между рейтингите на артикула и изчисляваме новия наблюдаван Diff .

Моля, обърнете внимание, че ние поставихме сумата от oldDiff и наблюдаванDiff като нова стойност на елемент.

И накрая, изчисляваме резултатите за сходство вътре в матриците:

for (Item j : diff.keySet()) { for (Item i : diff.get(j).keySet()) { double oldValue = diff.get(j).get(i).doubleValue(); int count = freq.get(j).get(i).intValue(); diff.get(j).put(i, oldValue / count); } }

Основната логика е да се раздели изчислената разлика в рейтинга на артикулите на броя на неговите появявания. След тази стъпка можем да разпечатаме нашата матрица на окончателните разлики.

3.3. Прогнози

Като основна част от Slope One ще предвидим всички липсващи оценки въз основа на съществуващите данни. За да направим това, трябва да сравним оценките на потребителските елементи с матрицата на разликите, изчислена в предишната стъпка:

for (Entry
    
      e : data.entrySet()) { for (Item j : e.getValue().keySet()) { for (Item k : diff.keySet()) { double predictedValue = diff.get(k).get(j).doubleValue() + e.getValue().get(j).doubleValue(); double finalValue = predictedValue * freq.get(k).get(j).intValue(); uPred.put(k, uPred.get(k) + finalValue); uFreq.put(k, uFreq.get(k) + freq.get(k).get(j).intValue()); } } // ... }
    

After that, we need to prepare the “clean” predictions using the code below:

HashMap clean = new HashMap(); for (Item j : uPred.keySet()) { if (uFreq.get(j) > 0) { clean.put(j, uPred.get(j).doubleValue() / uFreq.get(j).intValue()); } } for (Item j : InputData.items) { if (e.getValue().containsKey(j)) { clean.put(j, e.getValue().get(j)); } else if (!clean.containsKey(j)) { clean.put(j, -1.0); } }

The trick to consider with larger data set is to use only the item entries that have a large frequency value (for example > 1). Please note, that if the prediction is not possible, the value of it will be equal to -1.

Finally, very important note. If our algorithm worked correctly, we should receive the predictions for items that user didn't rate, but also the repeated ratings for the items that he rated. Those repeated rating's should not change, otherwise it means that there is a bug in your algorithm implementation.

3.4. Tips

There are few major factors that affect Slope One algorithm. Here are the few tips how to increase the accuracy and processing time:

  • помислете за получаване на рейтинги на потребителски елементи от страната на DB за големи набори от данни
  • задайте времевата рамка за извличане на рейтинги, тъй като интересите на хората могат да се променят с течение на времето - това също ще намали времето, необходимо за обработка на входните данни
  • разделяйте големи масиви от данни на по-малки - не е нужно да изчислявате прогнози за всички потребители всеки ден; можете да проверите дали потребителят е взаимодействал с предсказания елемент и след това да го добавите / премахнете от опашката за обработка за следващия ден

4. Заключение

В този урок успяхме да научим за алгоритъма Slope One. Освен това въведохме проблема за съвместно филтриране на системите за препоръки на артикули.

Най- пълното прилагане на този урок може да се намери в проекта GitHub.