1. Введение
В этом уроке мы узнаем все об алгоритме Slope One в Java.
Мы также покажем пример реализации задачи Collaborative Filtering (CF) — метода машинного обучения, используемого рекомендательными системами .
Это можно использовать, например, для прогнозирования интересов пользователей к определенным элементам.
2. Совместная фильтрация
Алгоритм Slope One представляет собой систему совместной фильтрации на основе элементов. Это означает, что он полностью основан на рейтинге пользовательских элементов. Когда мы вычисляем сходство между объектами, мы знаем только историю ранжирования, а не сам контент. Затем это сходство используется для прогнозирования рейтинга потенциальных пользователей для пар «пользователь-элемент», отсутствующих в наборе данных.
На изображении ниже показан полный процесс получения и подсчета рейтинга для конкретного пользователя:
Сначала пользователи оценивают разные элементы в системе. Далее алгоритм вычисляет подобия. После этого система делает прогнозы для рейтингов пользовательских элементов, которые пользователь еще не оценил.
Для более подробной информации по теме совместной фильтрации мы можем обратиться к статье в Википедии .
3. Алгоритм наклона один
Slope One был назван простейшей формой нетривиальной совместной фильтрации на основе элементов на основе оценок. Он принимает во внимание как информацию от всех пользователей, которые оценили один и тот же элемент, так и информацию о других элементах, оцененных тем же пользователем, для расчета матрицы сходства.
В нашем простом примере мы собираемся прогнозировать рейтинг пользователей по товарам в магазине.
Давайте начнем с простой модели Java для нашей проблемы и предметной области.
3.1. Java-модель
В нашей модели у нас есть два основных объекта — элементы и пользователи. Класс Item содержит имя элемента:
private String itemName;
С другой стороны, класс User содержит имя пользователя:
private String username;
Наконец, у нас есть класс InputData , который будет использоваться для инициализации данных. Предположим, что мы создадим в магазине пять разных товаров:
List<Item> 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<User, HashMap<Item, Double>> data;
3.2. Матрицы различий и частот
На основе имеющихся данных мы рассчитаем отношения между элементами, а также количество вхождений элементов. Для каждого пользователя мы проверяем его/ее рейтинг предметов:
for (HashMap<Item, Double> user : data.values()) {
for (Entry<Item, Double> e : user.entrySet()) {
// ...
}
}
На следующем шаге мы проверяем, существует ли элемент в наших матрицах. Если это первый случай, мы создаем новую запись в картах:
if (!diff.containsKey(e.getKey())) {
diff.put(e.getKey(), new HashMap<Item, Double>());
freq.put(e.getKey(), new HashMap<Item, Integer>());
}
Первая матрица используется для расчета различий между оценками пользователей. Его значения могут быть положительными или отрицательными (поскольку разница между оценками может быть отрицательной) и сохраняются как Double . С другой стороны, частоты сохраняются как целочисленные значения.
На следующем шаге мы собираемся сравнить рейтинги всех элементов:
for (Entry<Item, Double> 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);
}
Если кто-то уже оценил элемент ранее, мы увеличиваем количество частот на единицу. Кроме того, мы проверяем среднюю разницу между оценками элемента и вычисляем новую наблюдаемую разницу .
Обратите внимание, что мы помещаем сумму oldDiff и visibleDiff в качестве нового значения элемента.
Наконец, мы вычисляем оценки сходства внутри матриц:
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<User, HashMap<Item, Double>> 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());
}
}
// ...
}
После этого нам нужно подготовить «чистые» прогнозы, используя код ниже:
HashMap<Item, Double> clean = new HashMap<Item, Double>();
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);
}
}
Хитрость, которую следует учитывать при работе с большим набором данных, заключается в использовании только тех записей элементов, которые имеют большое значение частоты (например, > 1). Обратите внимание, что если прогноз невозможен, его значение будет равно -1.
Наконец, очень важное замечание. Если наш алгоритм работает правильно, мы должны получить прогнозы для элементов, которые пользователь не оценил, а также повторные оценки для элементов, которые он оценил . Эти повторяющиеся рейтинги не должны меняться, иначе это означает, что в реализации вашего алгоритма есть ошибка.
3.4. Советы
Есть несколько основных факторов, влияющих на алгоритм Slope One. Вот несколько советов, как повысить точность и время обработки:
- рассмотрите возможность получения рейтингов пользовательских элементов на стороне БД для больших наборов данных
- установить временные рамки для получения оценок, так как интересы людей могут меняться со временем — это также сократит время, необходимое для обработки входных данных
- разбивайте большие наборы данных на более мелкие — не нужно каждый день рассчитывать прогнозы для всех пользователей; вы можете проверить, взаимодействовал ли пользователь с предсказанным элементом, а затем добавить/удалить его/ее из очереди обработки на следующий день
4. Вывод
В этом уроке мы смогли узнать об алгоритме Slope One. Кроме того, мы представили проблему совместной фильтрации для систем рекомендаций по элементам.
Полную реализацию этого туториала можно найти в проекте GitHub .