Подход к созданию средств тематической категоризации интернет-ресурсов

ПОДХОД К СОЗДАНИЮ СРЕДСТВ ТЕМАТИЧЕСКОЙ КАТЕГОРИЗАЦИИ ИНТЕРНЕТ-РЕСУРСОВ

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

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

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

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

Реализация системы тематической категоризации интернет-ресурсов предполагает решение следующих задач:

• индексация интернет-ресурсов (преобразование интернет-ресурсов к единому формату);

• автоматическая категоризация интернет-ресурсов, обучение системы и отнесение текстовой информации к заранее определенной категории;

• оценка качества категоризации с использованием метрик из информационного поиска.

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

Пусть дано множество интернет-ресурсов П, разделенное на два непересекающихся подмножества Тг и Тц, называемых обучающей и тестовой выборкой. На основании обучающей выборки строится классификатор категорий, а на тестовой выборке проверяется качество категоризации. Пусть также дано соответствие между интернет-ресурсами и некоторой категорией с в виде Ф: П ^ {0,1}, устанавливающее для каждого интернет-ресурса значение 1, в случае принадлежности интернет-ресурса категории, и 0 - в противном случае [3-6].

Необходимо построить, используя только информацию из обучающей выборки Тг, функцию Ф ^ {0,1}, аппроксимирующую Ф, чтобы число ошибок Е на тестовой выборке Тц было наименьшим.

mm.

Пусть T - множество терминов, каким-либо образом выделенное из интернет-ресурсов категории с. Тогда интернет-ресурс можно представить в виде терминологического вектора

dj =

где w]] - вес термина ti в интернет-ресурсе d].

Описания каждой из категорий представим в виде векторов той же размерности, что и вектора интернет-ресурсов:

с =

где ci - вес термина ti в описании категории с .

При таком подходе существуют два ограничения:

• нет дополнительной информации о категориях, к которым прикрепляются интернет-ресурсы;

• нет никакой внешней информации о интернет-ресурсе, кроме той информации, которая содержится в нем.

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

Процесс индексации представим следующим образом (рис. 1):

• очистка страницы;

• выделение терминов;

• исключение терминов, не несущих смысловой нагрузки;

• замена общих и специфичных терминов;

• присваивание терминам весовых коэффициентов.

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

т

s

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

Л

>

=г

СП

о

0) о:

У

Рис. 1. Индексация интернет-ресурсов.

Заключительным этапом является присвоение терминам весовых коэффициентов. Исходное представление интернет-ресурса выглядит следующим образом: Интернет-ресурс = коллекция слов (терминов) Т. Каждый термин X х е Т имеет определенный вес

^ 1} по отношению к интернет-ресурсу й. е П (рис. 2), т.е. встречаемость этого слова на

странице интернет-ресурса. Порядок слов учитывать не будем. На основании этих признаков каждому слову сопоставляется его вес.

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

Таким образом, каждый ресурс можно представить в виде вектора весов его терминов = {. Веса документов нормируем так, чтобы > 0 и < 1, где

1е (0,\Т\) и ] е (0Щ).

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

Вычисляем вес термина следующим образом:

г 1

w = tf f'

где tfj (частота термина) - это отношение числа терминов ti в интернет-ресурсе dj к

общему количеству терминов в этом интернет-ресурсе, таким образом, оценивается

важность термина ti в пределах одного интернет-ресурса:

f = ^,

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

Djl

f = d

где j = 1, ... , T, Dj - число интернет-ресурсов, в которых встретился термин ti , D -

общее количество интернет-ресурсов категории.

Таким образом, чем чаще термин встречается на странице интернет-ресурса, но реже встречается во всех интернет-ресурсах, тем выше будет его вес в данном интернет-ресурсе.

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

• вычисляется мера близости страницы интернет-ресурса и категории - степень соответствия ресурса категории;

• для каждой страницы выбирается категория, наиболее близкая к ресурсу;

• если значение степени соответствия ресурса превышает некоторое пороговое значение категории, ресурс добавляется в категорию;

• если значение степени соответствия ресурса не превысило порогового значение категории, ресурс не добавляется в категорию, и решение о принадлежности его к категории определяет эксперт.

Степень соответствия (CSV) между категорией c и интернет-ресурсом dj определяем как скалярное произведение между их векторными представлениями:

CSV

i

Будем принимать решение о принадлежности интернет-ресурса к категории, если степень соответствия достигнет заданного порога т . Таким образом, получаем: \1, CSV(c,dj) >т °'(c4-) = j9, CSV(c,d,) <т <8>

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

Для оценки качества категоризации интернет-ресурсов применяем метрики из информационного поиска, такие как полнота, точность, Б-мера [11].

Пусть БГ - множество интернет-ресурсов, категоризированных экспертами, а Ба

- множество интернет-ресурсов, категоризированных автоматически.

Полнота категоризации интернет-ресурсов по категории вычисляется как отношение количества правильно категоризированных интернет-ресурсов системой к общему числу интернет-ресурсов, относящихся к этой категории. \Па I Пг\

Г =

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

Па 1 Пг\

Р =

Па

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

Р =---

г + р '

Алгоритм осуществления сбора и обработки данных интернет-ресурсов выглядит следующим образом (рис. 3).

Информационные ресурсы интернета

Системы контентной фильтрации

Внешний поисковик

Поисковые выражения

Тематическая категоризация

Поисковый профиль

Рис. 3. Сбор и обработка данных интернет-ресурсов.

Блок поиска информации в интернете получает от блока тематической категоризации поисковые профили и преобразует их в поисковые выражения для внешних поис-

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

Блок тематической категоризации запрашивает контент информационных ресурсов, адреса которых были добавлены в базу, но еще не были категорированы, или те, для которых пришло время повторной категоризации.

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

Блок сканирования Интернета по полученным адресам скачивает контент информационных ресурсов интернета и возвращает этот контент для проведения категоризации.

Для решения задач обработки информации интернет-ресурсов используются следующие два алгоритма:

1. поступление и обработка нового ресурса;

2. актуализация существующих интернет-ресурсов.

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

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

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

ПС «Поиск новых сайтов»

Новые адреса сайтов

_I_

I

Обновление базы

Изменения-

Данные о работе

Страницы для классификации

ПС «Каталогизация сайтов»

-Настройка-

ПС «Контроль и настройка процедуры классификации»

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

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

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

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

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

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

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

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

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

Разрабатываемые средства тематической категоризации интернет-ресурсов позволяют:

• составлять тематический каталог интернет-ресурсов за счет поиска веб-сайтов и поступления их от локальных систем контентной фильтрации при посещении пользователями веб-страниц;

• обеспечивать высокую точность категоризации интернет-ресурсов за счет составления тематических профилей при описании категорий;

• проводить актуализацию существующих интернет-ресурсов, т.е. заново осуществлять обход сайта, проверять изменения страниц, уточнять принадлежность сайта категориям;

• осуществлять обмен данными с локальными системами контентной фильтрации для защиты от нежелательного контента.

Литература

1. Фонд «Общественное мнение». <http://www.fom.ru/>.

2. Абсалямов А. Борьба с киберслэкингом // Windows 2000 Magazine, 2000. №3.

3. Плешко В В., Ермаков А.Е., Голенков В.П. RCO на РОМИП 2004 / Российский семинар по оценке методов информационного поиска (РОМИП 2004). Пущино, 2004. С. 43-61.

4. Плешко В.В., Ермаков А.Е., Митюхин В.А. RCO на РОМИП 2003: отчет об участии в семинаре по оценке методов информационного поиска / Труды Первого российского семинара по оценке методов информационного поиска. Под ред. И. С. Некре-стьянова - СПб: НИИ химии СПбГУ, 2003. С. 42-51.

5. Поляков И.Е. Опыт создания системы фильтрации агрессивного web-контента / Труды XII Всероссийской научно-методической конференции «Телематика 2005», 6-9 июня 2005. СПб: СПбГУ ИТММО, 2005.

6. Sebastiani F. Machine Learning in Automated Text Categorization, <http ://nmi s.isti. cnr. it/sebastiani/>.

7. Некрестьянов И.С., Павлова Е.Ю. Обнаружение структурного подобия HTML-документов. / Труды Четвертой всероссийской конференции RCDL'2002. Дубна, Россия, 2002. С. 38-54.

8. Ziv Bar-Yossef, Sridhar Rajagopalan Template Detection via Data Mining and its Applications // Proceedings of WWW2002, May 7-11, 2002, Honolulu, Hawaii, USA.

9. Gupta S., Kaiser G., Grimm P., Chiang M., Starren J. Automating Content Extraction of HTML Documents // World Wide Web Journal. January 2005.

10. Russian Context Optimizer. Технологии анализа и поиска текстовой информации. <http://www.rco.ru/>.

11. Поляков П.Ю., Плешко В.В. RCO на РОМИП 2006 / Труды Четвертого российского семинара по оценке методов информационного поиска. СПб: НИИ химии СПбГУ, 2003. С. 72-79.