Задача нахождения оптимальных путей просмотра результатов поиска является моей основной темой кандидаткой работы. Сегодня я хочу поделиться промежуточными результатами исследований, а также приложениями и SDK, которые были использованы в работе.

Решение о написании данной статьи было принято после просмотра семинара из цикла "Информационный поиск и анализ данных" на тему "Семантический анализ текстов с использованием Википедии", докладчиком которого был Максим Гринёв - доцент, старший преподаватель кафедры системного программирования, заведующий отделом ИСП РАН.

Вы можете посмотреть доклад, скачать доклад или посмотреть расписание других докладов.

Краткие научные выводы из семинара

Ниже будет кратко описано содержание семинара и основные полученные результаты.

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

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

Семантическое расстояние между статьями А и Б может быть рассчитано путем подсчета количества общих статей, на которые ссылаются статьи А и Б:

Рисунок 1

Семантическая близость является ключевым моментом в описываемых далее методах. Хочу упомянуть, что метод SimRank [1], описанная прошлом году, была признан не удачным.

От автора: кроме семантической близости для определения расстояния между двумя веб-документами можно использовать метод шинглов или критерий кси-квадрат Пирсона. Также по этому вопросу есть моя опубликованная статья "Метод оценки подобия веб-страниц" [2], где описывается обобщенный метод оценки подобия веб-страниц на базе некоторых семантических признаков.

Дальше речь шла извлечении ключевых слов по заданному термину и построении т.н. коммюнити (сообществ) или семантических графов [3]:

Рисунок 2

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

Пример реального семантического графа:

Рисунок 3

В ходе исследований оказалось, что "хорошие" сообщества имеют гораздо больший ранг чем остальные - менее релевантные.

Рисунок 4

Данный подход позволяет отсеивать не основной контент (top, bottom, see also), так как сообщества, полученные из терминов данных блоков будут иметь маленький ранг, и, соответственно, будут отсеяны в ходе вычислений.

Замечания и комментарии

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

В первую очередь хочу сделать акцент на некоторых слабых сторонах описанных методик и методов:

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

Ниже я опишу собственные наработки в контексте выше описанных методов.

Усовершенствованный метод кластеризации

Метод является доработкой классического алгоритма k-means, который является простым в плане реализации, но не точным. Причины, по которым данный алгоритм является не точным, есть две: алгоритм чувствителен к выбору начальных точек и количеству кластеров. Таким образом, если на вход будут поданы недостоверные данные, то качество результата будет желать лучшего.

В своей работе "Метод кластеризации на основе кластеров, распределенных по нормальному закону" [4] было предложено проверять закон распределения объектов внутри кластеров. Если кластер распределен по определенному закону, то его оставляем, если нет - делим на два дочерних и процесс проверки продолжается до тех пор, пока не будут найдены все кластеры, распределенные по определенному закону либо, когда превысим лимит на количество кластеров. Таким образом мы решаем проблему количества кластеров. Проблема выбора начальных точек решается путем задания максимально отделенных точек внутри бОльшего кластера в качестве начальных центров. На тестовых данных метод показал 95% точность.

Важность информационных блоков сайтов

Когда мы говорим о современной веб-страницы, мы имеем ввиду не только основной контент, ради которого, мы, собственно, пришли, а также о множестве дополнительной информации по бокам, внизу и т.д. Эти информационные блоки могут иметь разное предназначение - списки ссылок, статистика, связанные статьи, реклама. Понятно, что важность данного контента намного меньше основного.

Был разработал метод очищения веб-страниц от информационного шума [5], о котором я писал в общих чертах ранее [6]. Остановлюсь на важном моменте - процедура определения "важных" блоков строится на нечетком методе кластеризации, а простыми словами ищутся блоки с максимальными числовыми оценками (которые резко отличаются от других). Фактически этот же подход был использован для определения "хороших" сообществ, о котором рассказывал Максим Гринёв (см. рисунок 4).

Прототип доступен для загрузки на сайте codeplex:

Давайте еще посмотрим внимательно на рисунок 3 - граф взаимосвязей терминов. Фактически, это не что иное, как граф взаимосвязей веб-страниц, которые отвечают за конкретный термин.

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

Реальный пример работы системы по запросу "Microsoft" можно посмотреть ниже:

Рисунок 5 (в данном случае выбран неглубокий анализ ссылок)

Если присмотреться, то также можно увидеть некоторые "сообщества", которые свидетельствуют о принадлежности к разным категориям. Соответственно, выделив ключевые слова (либо другие свойства каждой веб-страницы), можно делать кластеризацию результатов поиска в рантайме. Заметьте, это работает для всего веба, не только для Википедии.

Нахождение оптимальных путей просмотра результатов поиска

Сейчас я подошел к самой интересной части, так как все выше перечисленное само по себе не имеет большого значения.

После того, как у нас есть граф взаимосвязей, информация о каждой веб-страницы (Google PageRank, расстояние между веб-страницами, "вес" страницы), мы можем найти оптимальный путь просмотра результатов поиска на графе. Т.е. другими словами, мы получим не линейный список сайтов, отранжированных по определенному алгоритму (весу), а набор рекомендаций по поводу того, в какой последовательности необходимо просматривать результаты веб-поиска [7].

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

Кроме того, пользователь может выбрать:

• глубину анализа
• максимальное (оптимальное) количество сайтов
• выбрать, что для него важно - скорость выполнения (т.е. запросы типа "что такое википедия"), либо глубокий анализ некоторого вопроса (например, "экономика стран Африки")
• все это он, конечно, может сохранить в личных настройках, таким образом перенастроить алгоритм под себя
  

Выводы

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

Надеюсь, данная статья поможет оценить состояние дел на поприще информационного поиска.

P.S. Не могу не упомянуть о разработанном Data Extracting SDK, с помощью которого были написаны практически все приложения, которые использовались для исследований.

[1] Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev, Denis Turdakov Accuracy Estimate and Optimization Techniques for SimRank Computation, VLDB 2008

[2] Метод оценки подобия веб-страниц

[3] Maria Grineva, Maxim Grinev, Dmitry Lizorkin.Extracting Key Terms From Noisy and Multitheme Documents. WWW2009: 18th International World Wide Web Conference

[4] Краковецький О.Ю. Метод кластеризації на основі кластерів, розподілених за нормальним законом // Міжнародний науково-технічний журнал «Інформаційні технології та комп’ютерна інженерія» №1(11). – 2008 р. – с.56-60.

[5] Метод очищения веб-страниц от информационного шума

[6] В.М. Дубовой, О.Ю. Краковецький, О.В. Глонь. Факторний аналіз оцінки важливості інформаційних блоків сайтів // Вісник Вінницького політехнічного інституту. - 2008. - №6. - C. 103-107

[7] Володимир Дубовой, Олександар Краковецький, Ольга Глонь Метод побудови оптимальних шляхів перегляду результатів веб-пошуку на основі евристичних алгоритмів