Analysis of the text and digital information for process modeling

Abstract

The article presents the description of the simplest classifiers, and compares popular algorithms for text categorization using test samples.

Full Text

Введение Ежегодно увеличивается объем существующей в мире информации, и поэтому становится все более актуальной задача автоматического анализа и классификации текстовой информации. Это обусловлено необходимостью иметь возможность поиска по имеющемуся массиву текста. Также это необходимо для того чтобы иметь возможность контролировать перемещение информации по сети между компьютерами. Виды классификаторов Для решения этой задачи часто применяются различные тематические классификаторы, рубрикаторы и т.д., которые позволяют производить поиск документов удовлетворяющих некоторым критериями в некоторой информационной базе. Существует несколько видов классификаторов: 1. «Ручные классификаторы». Классификатор этого типа обычно представляет собой множество рубрик, объединенных в иерархию (рубрикатор). К каждой рубрике приписываются соответствующие ее тематике документы. Иерархия рубрик может являться деревом, однако возможны ситуации, когда некоторые рубрики являются дочерними сразу для нескольких родительских рубрик. Пример: «новости математики» может являться дочерней одновременно для рубрики «математика» и рубрики «новости науки». Рисунок 1. Пример рубрикатора Существенный недостаток классификационного поиска в том, что документы, как правило, приходится классифицировать вручную. То есть при добавлении в массив нового документа сначала нужно его проанализировать и определить, к каким рубрикам классификатора он относится (микропроцессорные системы, сотрудничество компьютерных фирм, изобразительное искусство средневековья и т.д.). После этого документ станет доступным для поиска по классификатору. Очевидно, что при большом потоке входных документов применение ручной классификации становится очень трудоемким. Обеспечить высокую полноту ручной классификации большого объема документов оказывается сложно даже при помощи большого количества специалистов. Это обусловлено тем, что при ручной классификации часто возникает ситуация, что документ, соответствующий сразу нескольким рубрикам, оказывается приписан только части из них. Обычно количество таких ошибок пропорционально размерности рубрикатора. 2. «Автоматические классификаторы». Классификатор этого типа представляет собой систему, принимающую решение об определении документа в категорию автоматически. Это делается в частности с помощью частотного анализа по заданным ключевым словам. Существует 3 варианта автоматической классификации: 1. Поиск в искомом тексте лексем из документов обучающей выборки. В данном случае документ А из обучающей выборки и классифицируемый документ Б разделяется на лексемы (словоформы), поиск которых осуществляется в классифицируемом документе. Таким образом поиск дает положительный результат для слов в разных падежах, а также однокоренных слов, присутствующих в обоих документах. Доля найденных лексем обучающего документа среди всех лексем принимается за вероятность принадлежности документа к категории. 2. Полнотекстовый поиск. В этом случае осуществляется поиск слов из исходного документа в классифицируемом без учета лексем(словоформ). Такой поиск даст положительный результат для слова только в случае полного совпадения. Все слова из обучающего документа А сравниваются со всеми словами из классифицируемого документа Б. Доля общих слов документов А и Б есть вероятность принадлежности документа к категории. 3. Поиск по строгому соответствию. Это самый простой и малоэффективный тип поиска. В нем положительный результат возможен только если есть полное соответствие фрагментов текста документов А и Б. Сравнение алгоритмов Сравним эффективность трех вышеуказанных алгоритмов с помощью ЭВМ на примере трех наборов обучающих документов: 1. Коллекция новостных сообщений с сайтов RBK и Инфоарт. 2. Фрагмент юридической базы Консультант-плюс. 3. Аннотации к ресурсам, участвующим в рейтинге top100 Рамблера. Отличительной особенностью данного набора является наличие в нем поискового спама (специальных текстов, предназначенных для повышения позиции сайта в выдаче поисковой машины Рамблер). Характеристики наборов показаны в таблице 1. Таблица 1 Характеристики наборов данных для анализа № базы рубрик документов Примечание 1 243 14403 (140 Мб) новости РБК, ИнфоАрт 2 29 1590 (155 Мб) часть базы Консультант+ 3 57 101013 (42 Мб) каталог Rambler s top100 Для оценки качества классификации будем использовать другой набор документов (тестовый), содержащий соответственно случайно выбранные новостные статьи, юридические документы, и описания к сайтам, не содержащиеся в первом наборе документов. Рисунок 2. Зависимость полноты классификации от способа сопоставления терминов Проведем следующий эксперимент: попарно (новости с новостями и.т.д.) сравним тестовый набор документов с исходной базой, среднюю вероятность принадлежности документа к категории будем использовать в качестве оценки полноты алгоритма. За полноту принимается доля от общего числа соответствующих документов которые распознались классификатором. Также проанализируем точность классификации. Точность зависит от процента ошибок второго рода, то есть когда документ был ложно приписан к категории. Чем выше точность, тем меньше таких ошибок. Рисунок 3. Зависимость точности классификации от способа сопоставления терминов Выводы Как видно из диаграмм, классификатор, использующий лексемы дает большую полноту при ощутимо меньшей точности. Это в основном связано с многозначностью терминов, попавших в семантически образы рубрик. Классификация с использованием полнотекстового поиска эффективнее, процент ошибок меньше. Использование поиска по строгому совпадению дает максимальную точность, но количество ошибок первого рода очень велико. Различия между методами максимальны для больших тестовых наборов, как видно на примере набора №3, различия для которого минимальны в силу его малого размера. Эффективность классификации в зависимости от метода сопоставления показана в следующей таблице: Таблица 2 Зависимость эффективности классификации от метода сопоставления. Метод набор № I набор №2 набор №3 Лексемы 0,62 0,36 0,45 Полнотекстовый поиск 0,81 0,45 0,61 Строгое совпадение 0,36 0,16 0,16 Таким образом эффективность классификации максимальна при полнотекстовом поиске словосочетаний, который обеспечивает баланс между полнотой, характерной для традиционных методов, использующих однословные термины, и точностью, характерной для традиционных методов, использующих многословные термины.