Оценка алгоритмов для подбора литературы

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

Эта статья является продолжением [1] и ее цель показать результаты эксперимента по определению наиболее оптимального алгоритма для выполнения части, изложенной в статье [1] задачи. Задача состоит в том, чтобы, имея ряд книг, о которых известно, что они интересны пользователю, подобрать из множества книг те, которые также могут понравиться пользователю или, что более точно, близки к тем, что ему интересны. Наиболее существенной частью этой задачи является определение подмножества книг, которые будут близки к какой-то одной книге. Именно для этой подзадачи определяется оптимальный алгоритм в этом исследовании.

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

В статье [1] было выбрано несколько вариантов термов:

• n-грамма;
• слово;
• словосочетание.

В любом документе смысл несут слова и связи между ними (взаимное расположение), а также знаки препинания. Поэтому вариант n-граммы в качестве терма был отброшен как непригодный заранее – отдельная часть слова, особенно, если неизвестно даже, какая это его часть, не несет смысла сама по себе. И даже статистически куда уместнее брать целые слова, нежели n-граммы. Таким образом, остаются слова и словосочетания. Словосочетания могут быть разной длины и это, само собой, будет влиять на результат.

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

Обобщая все вышесказанное, суть эксперимента в следующем: есть база данных, состоящая из примерно десяти тысяч книг разных жанров, для нескольких из них определяются ближайшие 20 книг, выбранные с 4 различными видами термов по алгоритму косинусной близости: слово, словосочетание из 2, 3 и 4 слов. Все книги заранее обработаны и преобразованы в вектора, кроме того, ко всем словам применяется стеммер Портера.

Всего было выбрано 15 книг. Результат для одной из них – «Божественной комедии» Данте Алигьери, жанра античная литература, представлен в таблицах 1, 2, 3 и 4.

Таблица 1

Результат сравнения с использованием слов

Таблица 2

Результат сравнения с использованием словосочетаний длиной 2

Таблица 3

Результат сравнения с использованием словосочетаний длиной 3

Таблица 4

Результат сравнения с использованием словосочетаний длиной 4

Из приведенных результатов видно, что все полученные книги, так или иначе, близки к исходной. Степень схожести векторов, образованных словами, очень близка к единице, в то время как схожесть степени словосочетаний тем ниже, чем больше длина словосочетания, что и понятно. Также следует упомянуть про время поиска книг: для слов – 134 с., для словосочетаний длиной 2 – 471 с., для словосочетаний длиной 3 – 507 с. и для длины 4 – 557 с. Конкретное время, конечно же, зависит от многих факторов, но в сравнении алгоритмов эти величины имеют значение – время сравнения книг по словам в разы быстрее чем даже сравнение по словосочетанию наименьшей длины. Максимальная степень схожести для словосочетаний высокой длины сильно разнится в зависимости от жанра, если для античной литературы для словосочетания длиной 4 это значение близко к 0, то для фантастики близко к 0,7.

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

Таблица 5

Результат вычислений для терма – слова, жанра "античная литература"

В таблице 5 представлен пример результата для жанра “античная литература” с применением слова в качестве терма. Из-за того, что было несколько книг в жанре «античная литература», количество соответствующих им жанров пришлось нормализировать. Так уже видно, что абсолютное большинство соответствий приходится на античную литературу, т.е. соответствуют требуемому. Для сравнения, в таблице 6 представлены результаты для того же жанра, но с использованием словосочетаний длиной 2:

Таблица 6

Результат вычислений для терма – словосочетания длиной 2, жанра «античная литература»

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

Таблица 7

Обобщенные результаты эксперимента

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

В конечно счете можно сделать вывод, что поиск с использованием слов и словосочетаний длиной 2 дают наиболее релевантный результат.