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

Проблема поиска дубликатов в данных актуальна для многих предметных областей. Существует множество подходов к ее решению, их обзор представлен в [10], однако всегда в основе лежит операция сравнения между двумя объектами [11]. В данной работе используется подход обучения с учителем, как один из методов дающих наиболее точный результат при поиске дубликатов [12].

Все рассмотренные работы [10, 11, 12] направлены на исследование поиска сходства пары объектов и не предлагают решения проблемы поиска групп дубликатов. В данной работе предлагается такой алгоритм поиска дубликатов, который на основе полученной функции сходства между парой объектов находит кластеры дубликатов.

Задача де-дупликации разбивается на несколько этапов:

1. Поиск функции сходства двух объектов.

2. Формирование матрицы сходства.

3. Кластеризации матрицы сходства (получение групп дубликатов).

4. Обобщение дубликатов (выбор представителя группы и отсеивание копий).

Функция сходства должна включать в себя определение разницы между двумя объектами и определение на основе данной разницы вероятности сходства.

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

Функция для нахождения разности между двумя объектами получает на вход два объекта со всеми полями для сравнения, а на выходе новый объект, значения полей которого равны разнице соответствующих полей входных объектов:

где n - общее количество полей объектов, a, b - значения сравниваемых полей двух объектов.

Для нахождения разницы между числовыми полями достаточно вычислить их квадрат разности: или модуль разницы: .

Полученная величина будет служить мерой близости значений числовых полей:

.

Для сравнения строк необходимо перевести их в векторный вид (числовой). Широко используемый метод для этого - статистическая мера tf_idf, которая часто используется при обработке естественного языка. Ее расчет основан на поиске частоты употребления слова в каждом отдельном документе (tf) и поиске обратной частоты (idf). Tf - отношение количества вхождений определенного слова в документ к общему количеству слов этого документа [24]:

,

где - количество вхождений слова t в документ d, N - количество всего слов в d.

Idf измеряет важность слова и считается следующим образом [24]:

,

где - общее количество документов, - количество документов, в которых есть t.

Мера tf_idf находится как произведение tf и idf:

.

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

Следующим этапом в расчете разности двух строк является сравнение двух векторов (A, B), полученных с помощью расчета tf_idf для всех слов каждой строки. Близость двух векторов рассчитывается с использованием меры косинусного сходства [25]:

,

где a, b-строковые поля, A, B-вектора значений этих строк.

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

Таблица 2.1. Пример расчета разницы между двумя объектами

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

.

Функция сходства должна определять вероятность того, что два объекта являются дубликатами (p), получая на вход разницу между ними.

Для создания функции сходства могут быть использованы методы машинного обучения с учителем. Наиболее универсальным методом, который зарекомендовал себя на практике, является gradient boosting decision trees [26]. Использование этого метода в данной работе не отвергает другие, возможно, более эффективные решения. Для того, чтобы модуль анализа был как можно более универсальным и мог работать с различного вида данными, в дальнейшем необходимо добавлять другие методы решения задачи поиска функции сходства, например, нейронные сети [15].

Алгоритм gradient boosting decision trees реализован в библиотеке xgboost. Особенности его работы подробно описываются авторами этой библиотеки [27].

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

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

Обучающая выборка состоит не из пар объектов, а из разницы между ними. Функции предсказания на вход также подается разница межу объектами. Именно для этого на первом этапе выбраны два способа для поиска разницы между полями объектов.

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

Таблица 2.2 Структура матрицы сходства

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

Полученная матрица сходства ничто иное как матричная форма графа, вершинами которого являются объекты, а ребра между ними означают наличие связи между объектами и имеют значение функции сходства.

Несмотря на то, что пары-дубликаты уже найдены, необходимо найти все дубликаты каждого объекта, то есть сгруппировать полученные пары. Кластеризация матрицы сходства (графа) может быть осуществлена с помощью нескольких алгоритмов. Наиболее известные - это k_medoids [6] и методы иерархической кластеризации [28].

k_medoids метод разумно реализовывать самостоятельно, так как он не включен ни в одну библиотеку для машинного обучения для Python. Данный алгоритм отличается тем, что в качестве центров кластеров в нем используются сами объекты, которые называются медоидами. Сложность одной итерации алгоритма равна , что делает его практически неприменимым при больших значениях n и k. На вход алгоритм принимает множество объектов и количество кластеров, на выходе формируются кластеры объектов. Псевдокод алгоритма выглядит следующим образом [6]:

1) инициализация: выбор k из n объектов d в качестве медоидов (может быть осуществлена случайным образом);

2) связывание каждого объекта с ближайшим медоидом;

3) пока значение целевой функции больше или равно нулю повторять:

для каждого медоида m и не-медоида o повторять:

нач

заменить m на o во множестве медоидов;

если целевая функция увеличилась, то замена отменяется

конец

Иерархическая кластеризация действует по другому принципу: в зависимости от типа кластеризации разделяет крупные кластеры на более мелкие или объединяет мелкие в более крупные (см. рис.2.1).

Рисунок 2.1 Иерархическая кластеризация

Иерархическая кластеризация представлена во многих библиотеках для машинного обучения, в частности в scipy [29], которая использована в данной работе.

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

Метод поиска ассоциативных правил

Поиск закономерностей между событиями в базе данных (например анализ покупательских корзин и поиск продуктов, покупаемых совместно) в анализе данных ведется с помощью ассоциативных правил [7]. Поиск дополняющих объектов (часто встречающихся комбинаций в данных) также можно осуществить с помощью ассоциативных правил.

В основе ассоциативных правил лежит понятие транзакции - произошедшее одновременно множество событий.

В примере анализа меню питания пользователей транзакциями будут являться отдельно взятые приемы пищи из меню всех пользователей за все время. Появление нового меню в профиле пользователя (а именно список продуктов какого-либо отдельно взятого приема пищи) - новая транзакция. Например: {“овсянка”, “вареное яйцо”, “чай”}.

Помимо понятия транзакции существует структура правил и их основные свойства. Ассоциативное правило - импликация , при . Правило имеет поддержку s, если s процентов транзакций содержат X и Y, support () = support (XЃѕY). Вероятность того, что из X следует Y - это достоверность. Правило имеет достоверность c, если в c процентах случаев confidence () = support (XЃѕY) /support (X) [30].

Масштабируемым алгоритмом ассоциативных правил является алгоритм Apriori [8, 9]. Блок-схема с основными шагами алгоритма представлена на рис.2.2 [31]. Первым шагом алгоритм получает список часто встречающихся объектов (одноэлементных кандидатов) исходя из подсчитанной поддержки для каждого объекта. На основе данного списка далее будет сформирован список наборов 2_элементных кандидатов, подсчитана их поддержка и получены часто встречающиеся наборы. Далее над получившимися наборами выполняются те же самые операции, начиная с генерации кандидатов (n_элементных). Цикл повторятся до тех пор, пока сгенерировать очередной список кандидатов будет невозможно. На каждой итерации количество элементов в наборе уменьшается.

Рисунок 2.2 Общие шаги алгоритма Apriori

Алгоритм действует в соответсвии с утверждением, что часто встречающиеся наборы могут быть таковыми лишь в том случае, если все их подмножества являются часто встречающимися [31]. Таким образом, алгоритмом отсекаются те кандидаты, которые априори не смогут стать подмножеством часто встречающихся наборов. Получившиеся наборы данных есть искомые наборы дополняющих объектов, объектов, которые имеют связь и поэтому находятся в одной композиции.

Генерация правил позволяет создать таблицу "условие - следствие" с поддержкой и достоверностью для каждого (рис.2.3).

Рисунок 2.3 Визуализированное правило

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