Розробка рекомендаційного алгоритму книжок



Ця робота присвячена рекомендаційним мережам книжок. Метою даної роботи є розробка спеціального рекомендаційного алгоритму для соціального графу книжок на основі поєднання існуючих рекомендаційних алгоритмів, які використовують соціальний граф в якості моделі. Наукова новизна полягає в тому, що було запропоновано новий рекомендаційний алгоритм, який воснові використовує соціальний граф.

рекомендаційні системи, соціальний граф, центральність, PageRank, Link Prediction

Developing of a recommender algorithm for the books

Dmytro Svynarenko, Software Engineer, EPAM Systems

Ukraine,Kyiv

This work is about recommender systems for the books. The aim of this work is to develop a special recommender algorithm for the books social graph through a combination of existing recommender algorithms that use the social graph as a model. Scientific innovation is that it proposed a new recommender algorithm, which is based on using the social graph.

recommender systems, social graphs, centrality,PageRank, Link Prediction

Рекомендаційні системи виникли і почали розвиватися з середини 90-х років минулого століття. Основне завдання рекомендаційної системи – це надання персоналізованих рекомендацій користувачу, які враховують його уподобання при виборі предметів (товарів, об’єктів або послуг).

Рекомендаційні сервіси книжок є дуже актуальними зараз, оскільки дозволяють значно скоротити час пошуку схожих книжок за змістом до даної книги. Проте значною проблемою є точність рекомендацій. Дуже важливо мати рекомендаційну мережу, яка може надавати точні результати.

У наш час не так багато дійсно якісних рекомендаційних мереж нехудожньої літератури. Більшість з них надають дуже неточні результати і такі мережі не являються ефективними.

В якості моделі рекомендаційних мереж, як правило, використовується соціальний граф. Соціальний граф (англ.Social graph) — це граф, вузли якого представлені соціальними об'єктами, такими як профілі користувача з різними атрибутами (наприклад: ім'я, день народження, рідне місто, тощо), співтовариства, медіа-контент, тощо, а ребра — соціальними зв'язками між ними [1, с. 2].

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

При фільтрації вмісту створюються профілі користувачів і об'єктів. Профілі користувачів можуть містити демографічну інформацію або відповіді на певний набір питань. Профілі об'єктів можуть містити назви жанрів, імена акторів, імена виконавців, тощо. Або якусь іншу інформацію в залежності від типу об'єкта.

При колаборативній фільтрації використовується інформація про поведінку користувачів у минулому — наприклад, інформація про придбання або оцінки. В цьому разі не має значення, з якими типами об'єктів ведеться робота, але при цьому можна брати до уваги неявні характеристики, які складно було б врахувати при створенні профілю. Основна проблема цього типу рекомендаційних систем — «холодний старт»: відсутність даних про користувачів чи об'єкти, які нещодавно з'явились у системі.

Наведені вище методики мають один значну специфіку – вони орієнтовані на графи, які містять данні про користувачів та об’єкти. Проте пристворенні рекомендаційного сервісу книжок немає даних про користувачів, а є інформація тільки про книжки. Але інформація про книжки є відносно зв’язною, оскільки кожна книжка має бібліографічний покажчик на інші книжки. Цю властивість «є в бібліографії» можна використати при побудові соціального графу книжок. Якщо в соціальному графі в якості вершини виступає профіль користувача,то у випадку з книжками профіль книги буде вершиною, а властивість «є в бібліографії» будуть слугувати ребрами графу. Таким чином отримаємо соціальний граф для книжок.

Після отримання соціального графу з книжками можна приступати до його аналізу, для цього можна використати: алгоритми, які використовують метрику центральності [1, с. 3]; алгоритм випадкового графу [2, с. 913]; алгоритм PageRank [3, с. 163]; алгоритм LinkPrediction [4, с. 2].

Центральність (англ. Centrality)— ступінь, яка показує «важливість» або «вплив» певної вершини (кластера вершин) всередині графа. Стандартні методи вимірювання «центральності» включають в себе центральність з посередництва, центральність по близькості, центральність власного вектора, альфа центральність та центральність за ступенем. Таким чином можна знайти «найвпливовішу» книгу в графі.

PageRank — сімейство алгоритмів оцінки важливості вершини графу за допомогою розв'язання систем лінійних рівнянь. Для кожної вершини обчислює дійсне число, чим більше число — тим «важливіша» ця вершина. Дуже схожий на центральність, проте використовує інший підхід при пошуку найвпливовішої книги.

Link Prediction ­­ – алгорит мипрогнозування потенційних зв’язків між двома вершинами графу в майбутньому. В основі лежать еволюції графу за певні проміжки часу, звідки й прогнозуються ймовірні зв’язки. Такі алгоритми дають змогу зв’язувати старі книжки з новими, які між собою не мають властивості «є в бібліографії», проте мають спільну тематику.

У результаті роботи цих алгоритмів можна отримати соціальний граф книжок, вершини якого доповнилися відповідними атрибутами «важливості» книги (за тим чи іншим алгоритмом) та ребрами «потенційно» зв’язаних вершин.

Як уже було зазначено раніше, в якості моделі рекомендаційного графу книжок буде використовуватися соціальний граф.

Вершини будуть містити властивості притаманні книжкам. До таких властивостей можна віднести: ISBN, назва, рік та назва видавництва, автор, коротка відомість про книгу, категорія/УДК. Ця інформація є необхідною умовою для подальшої роботи.

Ребра являють собою зв'язок між книжками типу «є в бібліографії». Наприклад, якщо книга А має в своїй бібліографіі посилання на книгу Б, то якщо перейти на мову графів – звершини А до вершини Б буде проведено відповідне однонаправлене ребро.

Для того, щоб звузити кількість потенційно схожих книжок зазначається категорія книжки або УДК. Це дає змогу виділити в соціальному графі соціальне коло, яке й буде підграфом, і воно надалі буде використовуватися в якості вхідних даних для рекомендаційного алгоритму.

Рік видавництва являється основною вимогою для роботи алгоритму Link Prediction, оскільки таким чином існує можливість відтворити відображення графу для певного проміжку часу. Наприклад, можна відстежити які книги були видані до 2015 року, потім додати нову книгу 2016 року, на яку не можуть посилатися книжки, які були видані раніше. Проте після роботи алгоритму Link Prediction старі книжки можуть отримати зв’язки з більш новими книжками, що суттєво збільшує точність і якість роботи алгоритму.

У загальному випадку запропонований соціальний граф книжок буде мати наступний вигляд:

B1,…B10 – вершини, які представляють книжки;

В1 – вершина, для якої будуються рекомендації;

В1, В2, В3, В4, В5 – соціальне коло, яке буде використовуватися для роботи алгоритму;

зв’язок «Вn«relatedTo» Bm» означає те, що книжка n має бібліографічне посилання на книжку m;

ребро, яке виділено пунктиром – результат роботи алгоритму Link Prediction, коли більш стара вершина отримує зв'язок з більш новою.

Основною задачею рекомендаційного алгоритму є пошук книжок, які можна рекомендувати для подальшого опрацювання після даної книжки. Таким чином алгоритм повинен знайти дуже схожі за змістом книги. Якщо перейти до мови графів, то в якості вхідних даних є соціальний граф книжок та вершина, для якої необхідно побудувати рекомендації.

Крок1. Для роботи алгоритму спочатку необхідно виділити соціальне коло з соціального графу книжок. Для цього можна визначити декілька можливих методів:

• для даної вершини будується підграф, глибина якого є довільне число. Таким чином обираються всі зв’язані вершини до даною з певною глибиною. Це є дуже простий метод, який дозволяє значно звузити область пошуку. Проте такий метод має свої недоліки. Основним недоліком є те, що такий метод дуже грубо відсікає область пошуку. Та водночас постає питання пошуку такого довільного числа глибини, при якому точність роботи алгоритму є найбільшою;

• для даної вершини будується підграф, який являється категорію або УДК даної книги. Такий метод дозволяє покращити якість звуження області пошуку. Недоліком такого метода є те, що він відсікає рекомендації з інших категорій, що також може виключити з пошуку досить релевантні результати;

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

Крок 2. Після того, було отримане соціальне коло далі необхідно провести ранжування всіх вершин. Для цього можна застосувати наступні методи:

• для кожної вершини підраховується кількість спільних зв’язків з даною вершиною – ${{k}_{cr}}.$ Наприклад, книжка А має бібліографічне посилання на книжки Б, В, Г, Д, а книжка Я має посилання на книжки В, Г, Д, Ж. Таким чином кількість спільних зв’язків буде дорівнювати 3. Фактично для двох книжок кількість спільних зв’язків показує кількість спільних книжок в їх бібліографіях. Чим більше таких зв’язків, тим більше ці книжки пов’язані міжсобою і тим більша ймовірність того, що в ній можна знайти додаткову інформацію, якої немає в даній книжці, а отже її можна рекомендувати для подальшого опрацювання;

• для кожної вершини розраховується значення центральності за посередництвом – ${{k}_{c}}.$ Таким чином можна обрати книги, через які можна провести найбільше зв’язків. Це дозволяє ранжувати книги за важливістю та центральністю;

• для кожної вершини розраховується значення PageRank – ${{k}_{PR}}.$ Якщо розглянути всі книжки як мережу, а кожну книгу як сторінку, то можна використати алгоритм PageRank, який зможе виділити книгу, посилання якої має найбільшу вагу.

Крок 3. Використавши ці методи можна отримати значення рекомендації – $R.$ Чим більше це значення, тим більше ймовірність того, що саме ця книга являється максимально схожою до даної і саме її можна рекомендувати для подальшого опрацювання.

У загальному випадку значення рекомендації для вершини $i$ буде виглядати наступним чином:

\[{{R}_{i}}={{b}_{cr}}\cdot {{k}_{c{{r}_{i}}}}+{{b}_{c}}\cdot{{k}_{{{c}_{i}}}}+{{b}_{PR}}\cdot {{k}_{P{{R}_{i}}}},\]

де ${{b}_{cr}}$ – значення коефіцієнту підсилення значення кількості спільних зв’язків,

${{k}_{c{{r}_{i}}}}$ – значення кількості спільних зв’язків для вершини $i$,

${{b}_{c}}$ – значення коефіцієнту підсилення значення центральності за посередництвом,

${{k}_{{{c}_{i}}}}$ – значення центральності за посередництвом для вершини $i$,

${{b}_{PR}}$ – значення коефіцієнту підсилення значення PageRank,

${{k}_{P{{R}_{i}}}}$ – значення PageRank для вершини $i$.

Значення коефіцієнтів підсилення підбирається експериментальним шляхом на реальних даних.

Для покращення якості роботи алгоритму час від часу для соціального графу необхідно застосовувати алгоритм Link Prediction. Це дозволить створити зв’язки між старими та новими книжками.

Отриманий алгоритм можна широко використовувати для рекомендаційних мереж нехудожньої літератури, проте слід зазначити, що максимальної точності необхідно налаштувати коефіцієнти підсилення для різних наборів даних.

Список використаної літератури

  1. J.M. Podolny, J.N. Baron. Resources and relationships: Social networks and mobility in the workplace. — American Sociological Review, 1997

  2. L. Lu. “The Diameter of Random Massive Graphs”. In SODA’00, Proceedings of the Twelth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 912–921. ACM/SIAMPress, 2000.

  3. David Liben-Nowell, Anand Rajaraman, Jeffrey D. Ullman (2014). 5.1 PageRank. Miningof Massive Datasets.

  4. J.M. Podolny, Jon Kleinberg. The Link Prediction Problem for Social Networks. — ACM/SIAMPress, 2004
  • Рецензент: к.т.н, ст. викл. каф. ТК НТУУ "КПІ" Сирота О.П.
May 30, 2016