Высокорелевантный поиск и автоматическая категоризация ресурсов Интернета

С. В. Свечников

Высокорелевантный поиск и автоматическая категоризация ресурсов Интернета

●

Аннотация Предложен подход для реализации высокорелевантного поиска и автоматической категоризации интернетресурсов. Рассматривается механизм индексации интернетресурсов, т. е. преобразования их в единый формат посредством выделения терминов и присвоения им весовых коэффициентов, что позво ляет достаточно быстро и эффективно оценить содержимое интернетресурса. Рассматривается задача, связанная с автома тической категоризацией интернетресурсов, обучением систе мы и отнесением текстовой информации к заранее определен ной категории за счет использования степени соответствия между категорией и интернетресурсом. * * * Экспоненциальный рост объема информации, содержащей ся в Интернете является причиной возрастающей трудности по иска необходимых документов и организации их в виде струк турированных по смыслу каталогов. Большое количество источ ников информации, резко возрастающий объем данных в Интернете и необходимость их быстрой обработки вызвали потребность в создании специализированных систем высокоре левантного поиска и автоматической категоризации ресурсов Интернета. В настоящее время потребность в системах высокорелевант ного поиска и автоматической категоризации, а вместе с ними и системах для управления доступом к интернетресурсам не вызывает сомнений. Открытое информационное пространство содержит большое количество ресурсов различного содержания. Наряду с полезной информацией, Интернет содержит ресурсы, объективно опасные для нравственного здоровья общества, ока зывающие негативное воздействие в первую очередь на под растающее поколение. Российский сегмент сети — один из са мых быстроразвивающихся. Количество пользователей Интер

538

нета в России по различным данным составляет около 25 мил лионов человек, из них 2 миллиона дети [6]. Обеспечение учебных заведений и публичных библиотек доступом к сети Интернет увеличивает количество учащихся, пользующихся различными сервисами и информационными источниками, предоставляемыми глобальной сетью. Такой бес контрольный доступ к сети Интернет представляет серьезную угрозу для детей. Также Интернет бесконтрольно используется в личных целях работниками, имеющими доступ к глобальной се ти, что снижает эффективность их работы и снижает произво дительность корпоративной сети [1]. При этом методы прямого регулирования (цензуры) неэффективны, встречают протест пользователей Интернета и юридически несостоятельны, по скольку противоречат естественным правам граждан на свобо ду воли, высказываний и волеизъявления. В связи с этим решение этой проблемы надо искать не в цензуре, а в предоставлении инструмента для защиты от не желательного контента, который пользователи могут использо вать по своей воле и по своему усмотрению [2]. Реализация такого инструмента тесно связана с тематической категориза цией интернетресурсов, которая имеет много важных и вост ребованных в современном мире применений. Одним из них является механизм фильтрации полезной информации от агрес сивного контента. При этом все интернетресурсы разбиваются на категории и после соответствующего обучения становится возможной автоматическая фильтрация. Основные представленные на российском рынке програм мные продукты в области тематической категоризации интер нетресурсов принадлежат следующим компаниям: Производитель

Страна

Программный продукт

Secure computing

США

Sentian

Surfcontrol

США

Surfcontrol webfilter

Websense

США

Websense Enterprise

Cobion

Германия

Proventia Web Filter

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

539

Эти программные продукты позволяют: повысить эффективность работы сотрудников; ● оптимизировать пропускную способность сети; ● усилить безопасность сети; ● предотвратить появление неэтичных материалов; ● снизить расходы за доступ в Интернет. К достоинствам представленных программных продуктов можно отнести: ● обеспечение защиты от основных актуальных угроз без опасности; ● высокий уровень настраиваемости; ● поддержку большой и постоянно обновляемой базы дан ных URL; ● простоту использования. Все вышеуказанные системы прекрасно фильтруют, в пер вую очередь англоязычный контент. При работе с русскоязыч ным контентом эти продукты демонстрируют: ● некорректную работу с контентом по причине отсутствия специальных инструментов работы с информацией на рус ском языке; ● бедность базы данных русскоязычных ресурсов по причи не, указанной выше, а также потому, что Рунет составляет 5% от мировой сети Интернет и, вероятно, не является зо ной первоочередных интересов иностранных компаний; ● неучет национальных особенностей при категоризации русскоязычных ресурсов, потому что иностранные компа нии не всегда адекватно учитывают специфику и полити ческие реалии; ● систематическую погрешность категорирования сайтов, связанную, как правило, с полностью автоматическим опре делением категорий русскоязычных сайтов; ● низкую оперативность обновления; ● слабое сопровождение программного продукта; ● отсутствие возможности объединения данных от разных организаций с целью консолидации отчетности, потому что существующие системы рассчитаны преимущественно на локальное использование в коммерческих организациях. В связи с этим существует необходимость создания систе мы для высокорелевантного поиска и тематической категориза ции, адаптируемой для русскоязычных интернетресурсов. Реализация системы высокорелевантного поиска и темати ческой категоризации интернетресурсов предполагает решение следующих задач: ● индексация интернетресурсов (преобразование интернет ресурсов к единому формату); ● автоматическая категоризация интернетресурсов, обучение системы и отнесение текстовой информации к заранее оп ределенной категории; ●

540

оценка качества категоризации с использованием метрик из информационного поиска. Представленные подзадачи связаны, в первую очередь, с анализом текстовой информации webстраницы, т. е. ее содер жанием (контентом). Пусть дано множество интернетресурсов D, разделенное на два непересекающихся подмножества Tr и Ts , называемых обучающей и тестовой выборкой. На основании обучающей вы борки строится классификатор категорий, а на тестовой выбор ке проверяется качество категоризации. Пусть также дано соот ветствие между интернетресурсами и некоторой категорией c в виде Ф  D → {0,1}, устанавливающее для каждого интернет ресурса значение 1, в случае принадлежности интернетресурса категории, и 0 — в противном случае [2,3,4,7]. Необходимо построить, используя только информацию из обучающей выборки Tr , функцию Ф'  D → {0,1}, аппроксимиру ющую Ф, чтобы число ошибок E на тестовой выборке Ts было наименьшим. ●

|Ф – Ф' | → min. E = 

(1)

Ts

Пусть T — множество терминов, какимлибо образом, вы деленное из интернетресурсов категории c. Тогда интернетре сурс можно представить в виде терминологического вектора: dj = (w1j , ... w|T|j)T,

(2)

где wlj — вес термина ti в интернетресурсе dj . Описания каждой из категорий представим в виде векторов той же размерности, что и вектора интернетресурсов: c = (c1, ... , c|T|)T,

(3)

где ci — вес термина ti в описании категории c. При таком подходе существуют два ограничения: ● нет дополнительной информации о категориях, к которым прикрепляются интернетресурсы; ● нет никакой внешней информации о интернетресурсе, кроме той информации, которая содержится в нем. Каждый интернетресурс — это вектор, где номера терми нов (слов) — его координаты, а веса терминов — значения ко ординат; размерность вектора — это количество терминов, встречающихся в интернетресурсе. Так как учитываются все термины, вектора получаются большого размера, что затрудня ет процесс индексации, поэтому необходимо уменьшить раз мерность вектора. Для уменьшения размерности вектора в каче стве терминов используем не слова, а устойчивые словосочета ния, не учитываем редкие слова, которые не несут полезной информации, не рассматриваем часто встречающиеся слова.

541

Процесс индексации пред ставим следующим образом (рис. 1): ● очистка страницы; ● выделение терминов; ● исключение терминов, не несущих смысловой на грузки; ● замена общих и специ фичных терминов; ● присваивание терминам весовых коэффициентов. Сначала проводится очистка страницы интернет ресурса, т. е. удаляется навига ционная часть, теги html, скрипты, стопслова — частот ные слова языка, не несущие смысловой нагрузки (предло ги, союзы, частицы, местоиме ния, некоторые глаголы). За счет этого уменьшается объем поисковой базы и повышается Рис. 1. Индексация интернетре производительность поиска [9, сурсов 10, 11]. После этого в тексте с помощью функции анализа контента интернетресурса выделя ются термины — логические выражения, состоящие из слов и словосочетаний, связанные операторами AND, OR, NOT. Для исключения терминов, не несущих смысловой нагрузки, исполь зуется пометка «исключение», которая показывает, что термин не относится к теме. Оставшиеся термины могут также обладать недостатками: существуют термины, которые слишком специ фичны или, наоборот, значение которых слишком общо, поэто му их необходимо заменить более подходящими терминами. Это увеличивает полноту индексирования. Для замены специ фичных терминов используется тезаурус RCO, который пред ставляет собой словарь общей лексики с семантическими отно шениями между словами [8]. Использование тезауруса повышает качество анализа текста и полноту поиска информации, позво ляя расширять запрос синонимичными, более общими и более частными понятиями. Общие термины заменяются сочетаниями терминов или несколькими связанными терминами, имеющими более определенное значение. После того как были определены термины, необходимо провести лемматизацию — приведение терминов к нормальной форме (мужской род, единственное число). Тем самым уменьшается словарь терминов и повышает ся скорость работы индексации.

542

Рис. 2. Интернетресурсы, содержащие термины

Заключительным этапом является присвоение терминам весовых коэффициентов. Исходное представление интернет ресурса выглядит следующим образом: интернетресурс = кол лекция слов (терминов) T. Каждый термин ti ∈ T имеет опреде ленный вес wij по отношению к интернетресурсу dj ∈ D (рис. 2), т. е. встречаемость этого слова на странице интернет ресурса. Порядок слов учитывать не будем. На основании этих признаков каждому слову сопоставляется его вес. Таким образом, каждый ресурс можно представить в виде вектора весов его терминов dj = {w1j,...w|T| j }. Веса документов нормируем так, чтобы wij ≥ 0 и wij ≤ 1, где i ∈ (0,|T|) и j ∈ (0,|D|). Для вычисления веса термина на странице интернетресур са используем классический частотный метод вычисления сте пени соответствия интернетресурса, так как этот метод отно сительно прост и имеет несложный алгоритм, что принципи ально при обработке больших объемов документов. Вычисляем вес термина следующим образом: 1 wij = t fij ⋅ , d fj

(4)

где t fij (частота термина) — это отношение числа терминов ti в интернетресурсе dj к общему количеству терминов в этом ин тернетресурсе. Таким образом, оценивается важность термина ti в пределах одного интернетресурса: t fij

=

Tij

,

(5)

Ti

где j = 1, ... , T, i = 1, ... , D, Tij — число терминов ti в интернетресурсе dj, Ti , — общее число терминов в интернетресурсе dj. d f j (частота интернетресурса) — это отношение количест ва интернетресурсов категории, в которых встретился термин ti к общему количеству интернетресурсов категории: d fj =

Dj

,

(6)

D

где j = 1, ... , T,

543

Dj — число интернетресурсов, в которых встретился тер мин ti , D — общее количество интернетресурсов категории. Таким образом, чем чаще термин встречается на странице данного интернетресурса, но реже во всех интернетресурсах, тем выше будет его вес в данном интернетресурсе. Наиболее трудоемкой частью реализации системы является разработка процесса, отвечающего за автоматическую категори зацию интернетресурсов, обучение системы на уже категори зированных интернетресурсах и определение соответствия категории. Алгоритм автоматической категоризации интернетресур сов заключается в следующем (рис. 3):

Рис. 3. Алгоритм авто матической категориза ции интернетресурсов

544

вычисляется мера близости страницы интернетресурса и категории — степень соответствия ресурса категории; ● для каждой страницы выбирается категория, наиболее близкая к ресурсу; ● в случае если значение степени соответствия ресурса пре вышает некоторое пороговое значение категории, ресурс добавляется в категорию; ● в случае если значение степени соответствия ресурса не превысило порогового значение категории, ресурс не до бавляется в категорию и решение о принадлежности его к категории определяет эксперт. Степень соответствия (CSV) между категорией c и интер нетресурсом dj определяем как скалярное произведение между их векторными представлениями: (7) CSV (c, d j ) = c ⋅ d j = ∑ cidij , ●

i

Будем принимать решение о принадлежности интернетре сурса к категории, если степень соответствия достигнет задан ного порога τ . Таким образом, получаем:

Φ ′ (c, dj ) =

⎧1, ⎨0, ⎩

CSV (c, d j ) ≥ τ CSV (c, d j ) < τ

.

(8)

После того как вычислена степень соответствия между категорией и интернетресурсом, а также пороговое значение категории, необходимо провести обучение. Цель обучения — настройка весовых коэффициентов и порогового значения таким образом, чтобы процедура категоризации относила поло жительные примеры к категории, а отрицательные примеры — не относила, т. е. чтобы суммы весовых коэффициентов всех по ложительных примеров были равны либо превышали пороговое значение, а суммы для отрицательных примеров были ниже по рога. Для оценки качества категоризации интернетресурсов применяем метрики из информационного поиска, такие, как полнота, точность, Fмера [5]. Пусть Dr — множество интернетресурсов, категоризиро ванных экспертами, а Da — множество интернетресурсов, кате горизированных автоматически. Полнота категоризации интернетресурсов по категории вычисляется как отношение количества правильно категоризи рованных интернетресурсов системой к общему числу интер нетресурсов, относящихся к этой категории: r=

Da

∩ Dr

.

(9)

Dr

Точность категоризации интернетресурсов вычисляется как отношение количества правильно категоризированных ин

545

тернетресурсов системой к общему числу интернетресурсов, автоматически категоризированных системой: p=

Da

∩ Dr

.

Da

(10)

Для идеального алгоритма полнота и точность должны быть равны 100%. Fмера, т. е. сводная оценка качества категоризации, опре деляется как гармонически среднее полноты и точности: F=

2⋅r ⋅ p . r+p

(11)

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

Рис. 4. Структура системы и взаимодействие ее подсистем

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

546

Далее вся информация о новых ресурсах поступает в под систему «Ведение информационных ресурсов». При этом есть только базовая информация о ресурсе, он не привязан к кате гориям. После этого в работу включается подсистема «Обход интер нетресурсов». В рамках данной подсистемы осуществляется об ход сайта и получение набора страниц, которые можно анали зировать тематически. Следующим является подсистема каталогизации интернет ресурсов, которая анализирует тексты страниц, составляет их профиль и на основании этого решает об отнесении сайта к той или иной тематической категории. Процессом, контролирующим качество классификации, уп равляет подсистема «Контроль и настройка процедуры класси фикации». В результате классификации в рамках подсистемы «Ведение информационных ресурсов» сайты получают соответствие кате гориям. Дополнительно ведется специализированный журнал отсле живания изменений о сайтах и категориях, который использу ется подсистемой «Обмен с системами контентной фильтрации (СКФ)» для обновления данных в базах СКФ и получения от них новых неизвестных адресов для анализа. Подсистема «Ведение пользователей и управление правами доступа» позволяет использовать систему в многопользователь ском режиме, с разграничением прав доступа между пользова телями и контролем действий, выполняемых пользователем. Подсистема «Отчеты и статистика» собирает информацию от всех модулей и предоставляет ее для анализа. Разрабатываемая система позволит выполнять поиск новых ресурсов в сети Интернет, анализировать текстовое содержимое этих ресурсов, актуализировать накопленную информацию в со ответствии с заданным списком, состоящим из 48 категорий, которые охватывают более 200 тем.

Литература 1. Абсалямов А. Борьба с киберслэкингом / А. Абсалямов // Windows 2000 Magazine. — 2000. — № 3. 2. Плешко В. В. RCO на РОМИП 2004 / В. В. Плешко, А. Е. Ер маков, В. П. Голенков // Российский семинар по оценке методов информационного поиска (РОМИП 2004). — Пущино, 2004. 3. Плешко В. В. RCO на РОМИП 2003: отчет об участии в российском семинаре по оценке методов информационного поиска / В. В. Плешко, А. Е. Ермаков, В. А. Митюхин // Труды пер вого российского семинара по оценке методов информацион

547

ного поиска / под ред. И. С. Некрестьянова. — СПб.: НИИ химии СПбГУ, 2003. 4. Поляков И. Е. Опыт создания системы фильтрации агрес сивного webконтента / И. Е. Поляков // Труды XII Всероссий ской научнометодической конференции «Телематика’2005» (6— 9 июня 2005 г., СанктПетербург). — СПб., 2005. 5. Поляков П. Ю. RCO на РОМИП 2006 / П. Ю. Поляков, В. В. Плешко // Труды четвертого российского семинара по оценке методов информационного поиска. — СПб.: НИИ химии СПбГУ, 2003. 6. Фонд «Общественное мнение», http://www.fom.ru 7. Sebastiani F. Machine Learning in Automated Text Categorization, http://nmis.isti.cnr.it/sebastiani 8. Russian Context Optimizer. Технологии анализа и поиска текстовой информации, http://www.rco.ru 9. Некрестьянов И. С. Обнаружение структурного подобия HTMLдокументов / И. С. Некрестьянов, Е. Ю. Павлова // Труды четвертой всероссийской конференции RCDL’2002. — Дубна, 2002. 10. Ziv BarYossef. Template Detection via Data Mining and its Applications / Ziv BarYossef, Sridhar Rajagopalan // Proceedings of WWW2002, May, 7—11, 2002, Honolulu, Hawaii, USA. 11. Automating Content Extraction of HTML Documents / S. Gupta, G. Kaiser, P. Grimm, M. Chiang, J. Starren // World Wide Web Journal. — January, 2005.