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

Кудинов Павел Юрьевич

АДАПТИВНЫЕ МЕТОДЫ ИЗВЛЕЧЕНИЯ ИНФОРМАЦИИ ИЗ СТАТИСТИЧЕСКИХ ТАБЛИЦ, ПРЕДСТАВЛЕННЫХ В ТЕКСТОВОМ ВИДЕ

Специальность: 05.13.17 - теоретические основы информатики

1 7 НОЯ 2011

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Москва - 2011

005000802

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН.

Научный руководитель: доктор физико-математических наук

Воронцов Константин Вячеславович.

Официальные оппоненты: доктор технических наук

Миркин Борис Григорьевич, кандидат физико-математических наук Лещинер Дмитрий Роальдович.

Ведущая организация: Московский физико-технический институт

(государственный университет).

Защита диссертации состоится «8» декабря 2011 г. в ^ часов на заседании диссертационного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А.А.Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан «7» ноября 2011 г.

Учёный секретарь диссертационного совета

Д 002.017.02, д.ф.-м.н., профессор В. В. Рязанов

Общая характеристика работы

Диссертационная работа посвящена проблеме извлечения статистических показателей из таблиц, представленных в текстовом виде. Предлагается методология полуавтоматической обработки исходных данных, основанная на динамическом обучении с привлечением эксперта. Исследуются инкрементные алгоритмы машинного обучения, не совершающие ошибок на обучающей выборке. Описывается полуавтоматическая система извлечения статистических показателей из таблиц, разработанная на основе предложенной методологии. Актуальность темы. Социальная, экономическая, демографическая, финансовая статистика собирается и публикуется в бумажном и электронном виде различными организациями. Многие источники, например Росстат, ВЦИОМ, OECD, банки и финансовые организации предоставляют статистические данные в табличном виде (Рис. 1). Число таблиц, созданных ежегодно, измеряется сотнями тысяч. При этом в разных источниках могут использоваться разные термины и структуры таблиц для описания одних и тех же явлений. Это осложняет поиск, агрегацию и анализ динамики изменения статистических показателей.

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

Исходными данными для поисковой системы являются коллекции таб-

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

Распределение численности занятых в экономике регионов Российской

Всего а топ числе в возрасте, лет Средний возраст, лет

до 20 2029 3039 4049 5059 6072

Российская Федерация 100 2,0 21,5 27,2 зо.з 14Д 5,0 39,3

Центральный федеральный округ 100 1,6 20,0 26,6 30,1 15,7 6,1 40,1

Белгородская область 100 1,8 19,8 28,4 30,5 12,6 6,9 39,9

Брянская область 100 1,9 22,3 27,7 30,7 12,3 4,6 38,8

Владимирская область 100 2,2 21,0 26,5 30,6 14,4 5,2 39,4

Рогэпнежпсая

Рис. 1. Пример статистической таблицы.

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

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

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

Более рациональным представляется режим диалога, при котором система предъявляет размеченные ею таблицы, а эксперт только исправляет допущенные системой ошибки. Эти исправления формируют обучающую выборку в режиме адаптивного или инкрементного обучения (incremental learning). При этом к алгоритму обучения предъявляются требование корректности — он не должен совершать ошибок на всех исправлениях, сделанных экспертом ранее.

Корректные инкрементные методы обучения, способные эффективно обучаться по выборкам длиной в сотни тысяч объектов и более, в литературе практически не изучались.

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

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

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

2. Алгоритм инкрементного обучения композиций случайных деревьев (Random Incremental Forest, RIF).

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

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

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

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

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

— XI Всероссийская объединенная конференция «Интернет и современное общество» 1М8-2008 (Санкт-Петербург, 2008 год);

— XVI международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009» (Москва, 2009 год);

— 14-я всероссийская конференция «Математические методы распознавания образов» (Суздаль, 2009 год);

— 8-я международная конференция «Интеллектуализация обработки информации» ИОИ'Ю (Пафос, Республика Кипр, 2010 год);

— 6-я международная конференция «Служба экономических и социологических данных» Е8БЗ-2010 (Лондон, Великобритания, 2010 год);

— 15-я всероссийская конференция «Математические методы распознавания образов» (Петрозаводск, 2011 год).

Описания отдельных результатов работы включены в отчёты по проектам РФФИ №№08-07-00305-а, 10-07-00609-а, 11-07-00480-а. Личный вклад. Вклад автора работы в результаты, выносимые на защиту, является определяющим.

Публикации. Материалы диссертации опубликованы в 5 статьях [1-5], в одной статье в журнале, включённом в Перечень ведущих рецензируемых научных журналов и изданий [7]. Одна статья в журнале из этого перечня находится в печати [6].

Структура и объём диссертации. Работа состоит из оглавления, введения, трёх глав, заключения и списка литературы. Содержание работы изложено на 105 страницах. Список литературы включает 46 наименований. Текст работы иллюстрируется 39 рисунками и 7 таблицами.

Содержание работы

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

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

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

Система поиска статистической информации состоит из нескольких основных подсистем:

• подсистема поиска новых источников данных (статистических таблиц);

• подсистема извлечения статистических показателей из найденных таблиц;

• подсистема поиска релевантных статистических показателей и их отображения.

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

1) распознавание типа ячеек;

2) распознавание суперстрок;

3) распознавание вложенных ячеек;

4) извлечение названия таблицы из окружающего текста;

5) поиск содержимого ячеек и названия таблицы в словарях;

6) извлечение периода времени;

7) извлечение единиц измерения;

8) построение статистического показателя.

Задачи 1), 2), 3) являются задачами классификации, и для их решения предлагается использовать методы обучения по прецедентам. Объектами в этих задачах являются соответственно: ячейки, строки и некоторые пары соседних ячеек таблиц. Заметим, что если число таблиц (при самом скромном подсчёте) имеет порядок 104, то суммарное число ячеек — уже порядка 106. Таким образом, к эффективности применяемых методов обучения предъявляются серьёзные требования.

Основной проблемой является определение логической структуры статистической таблицы. Ббльшая часть таблиц содержит блоки ячеек описания

9

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

ЙиНИмИ кмШтйМюв

1 щ 1 ' ч". ' ячеек данных . К А- ч\;\' V V ч\\\ X V- < \>, о :<• ■ »

Рис. 2. Статистическая таблица простой структуры.

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

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

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

Рис. 3. Статистическая таблица с суперстроками.

1

1-1 . Уровень 1

Уровень 2

Уровень 2

Уровень 1

\ УроаеньЗ

■ • . Уровень 2 "

Уровень 1

Рис. 4. Фрагмент таблицы с вложенными ячейками.

раженным в текстовой форме. Например, статистические данные по учебным заведениям обычно заданы для учебного года. Задача состоит в том, чтобы для каждого статистического показателя получить интервал времени [¿1, ¿2] -В тексте одной ячейки может содержаться несколько ключей (элементарных характеристик статистических явлений). Поэтому задача построения названия извлекаемого статистического показателя формулируется как задача поиска всевозможных словесных представлений ключей в текстах ячеек описания, определяющих этот показатель.

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

извлечения статистических показателей из таблиц, основанной на динамическом обучении.

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

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

Во второй главе вводятся основные понятия, определения и обозначения, описываются особенности статистических таблиц, приводится постановка задачи извлечения статистических показателей, излагаются все этапы её решения. Для этапов, представляющих из себя задачи распознавания, приводятся постановки соответствующих задач, определяются признаки классифицируемых объектов. Описанные задачи распознавания предлагается решать инкрементными алгоритмами машинного обучения. Проводится сравнение инкрементных алгоритмов и обосновывается выбор алгоритма построения дерева решений ITI. Предлагается новый корректный алгоритм построения композиции случайных деревьев решений (RIF).

В разделе 2.1 вводятся основные понятия и определения.

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

12

ключу ki Е /С соответствует множество его допустимых словесных описаний Д. Оно включает все словесные эквиваленты одной и той же статистической характеристики, представленной в текстовом виде. Множества словесных описаний могут быть получены из Общероссийских классификаторов или наполнены вручную.

Статистическим показателем будем называть четвёрку s = (К, U, d, v), определяющую множество ключей К = {ki,..., kn] с /С, единицу измерения U с К, интервал времени d = [¿ь ¿2], где t\, £2 — даты, и значение ибК.

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

Рассмотрим квадратную сетку GMxN из М строк и N столбцов и зададим её полное покрытие непересекающимися прямоугольными областями. Элемент покрытия будем называть ячейкой. Множество всех ячеек обозначим через С. Каждой ячейке с 6 С поставим в соответствие текстовую строку text (с), возможно пустую, которую назовём содержимым ячейки или её текстом. Множество С задаёт физическую структуру таблицы.

Определение 1. Таблицей будем называть пару (GMxN, С).

Пространство всех таблиц обозначим через Т.

Будем полагать, что каждая ячейка с имеет один из трёх типов: ячейка данных, ячейка описания или неинформативная ячейка. Определим отображение 91: Су —> 2°к, где Су — множество ячеек данных и С к — множество ячеек описаний. Отображение £R ставит в соответствие каждой ячейке данных множество ячеек описания, т. е. задаёт логическую структуру таблицы.

Определение 2. Статистической таблицей будем называть четвёрку

Множество всех статистических таблиц обозначим через %■ Будем полагать, что если таблица Т является статистической, то для неё определено отображение 6 : Т —> %■

В разделе 2.2 приводится постановка задачи извлечения статистических показателей из таблиц, которая состоит в том, чтобы построить отображение Ш:Т ^ 21.

Решение этой задачи разбивается на два основных этапа: распознавание статистической таблицы, т. е. построение отображения 6, а затем построение отображения 3 : Та 21.

Первый этап состоит из следующих шагов.

1. Распознавание типа каждой ячейки, т. е. построение множеств Су и Сц.

2. Распознавание суперстрок.

3. Распознавание вложенных ячеек.

4. Чтение таблицы, т. е. построение отображения

Второй этап состоит из следующих шагов.

1. Чтение ячеек описания — извлечение ключей из текста всех ячеек описания.

2. Извлечение названия таблицы из текста.

3. Извлечение периода времени и единицы измерения.

4. Построение множества статистических показателей.

Распознавание типа ячеек. Положение ячейки с € С в таблице описывается координатами левого верхнего (г^с), сх(с)) и правого нижнего (г2(с), с2(с)) углов прямоугольника по сетке СМхЛГ. Для каждой ячейки с € С определим следующие признаки:

1) /i(c) ~ количество чисел в iezt(c);

2) /2(с) — количество слов в text(c);

3) /з(с) — количество символов в text (с);

4) /4(c) = (п(с) + г2(с))/2М — вертикальное положение;

5) /5(с) = (ci(c) + сг(с))/2Ы — горизонтальное положение ячейки с;

6) /б (с) = Гг(с) - г\ (с) — число строк сетки, занимаемых ячейкой с;

7) /7(c) = сг(с) — ci(c) — число столбцов, занимаемых ячейкой с.

Классификация суперстрок. Рассмотрим задачу классификации строк таблицы на два класса: «обычная строка» и «суперстрока». Для каждой строки 5 С С будем строить следующий набор признаков:

1) fi(S) — количество ячеек в строке;

2) /2(5) — N — ширина таблицы;

3) /з(5) — высота строки;

4) /4(5) — количество пустых ячеек;

5) /5(5) — (minci(c) +maxc2(c))/2N — количество непустых ячеек.

ceS cg5

Вложенные ячейки. Для определения вложенности решается задача классификации, в которой объектами являются пары последовательно идущих ячеек р = (Xi, Х2) в левом блоке ячеек описания, разделённых на три класса: «ячейки находятся на одном уровне», «хг сдвинута вправо относительно х\» и «i2 сдвинута влево относительно Х\ь. Для этих объектов вычисляется следующий набор признаков:

1) flip) ~ текст х\ заканчивается на «:»;

2) hip) ~ количество начальных пробельных символов в тексте

3) hip) ~ тип первого непробельного символа в хг'- «цифра», «буква» или «знак»;

4) h(p) — первая буква в х\ является прописной;

5) h{v) — первая буква в является прописной;

6) /в(р) = Ы^) - ri(xi) - высота х:;

7) Мр) = 02(2:2) - 01(2:2) - ширина х%-

Чтение ячейки описания. Задача состоит в том, чтобы каждой ячейке-описанию с 6 Ск поставить в соответствие множество ключей К (с) с 1С, то есть построить отображение С к 2К. При этом необходимо учитывать, что, во-первых, допустимы ошибки в словах, а во-вторых — разделение строки на ключи может быть не однозначно.

Текст ячейки описания будем рассматривать как последовательность слов (xi,... ,х„). Для каждого слова xt строится множество близких слов Xi = {я G W : p{x,Xi) < t},W — все слова и словоформы, р — расстояние Левенштейна, г — параметр. После этого строится семейство всех подстрок строки х, включающее всевозможные комбинации близких слов.

X = {(xi,. ..,Xj), 1 < i < j < n,xi € Xi.Vi = i,j}.

Обозначим через в(х) множество номеров слов, входящих в строку х.

Построим X-d = X П Х> — множество всех строк X, являющихся описаниями ключей V = (J Д. Рассмотрим множество всех разбиений X на i=l...|K|

ключи:

^={562^: Vsi, s2 € S 0(sj) П 0(a2) = 0}-

Обозначим множество номеров слов исходной строки х, не содержащихся ни в одной из строк множества S € Х-р через

Q(S) = {Mi} \{Je(s),a(s) = £>(1,®).

ssS xes

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

E{S) = 7|ВД| + У a{s) min . fts

Минимизация функционала осуществляется на основе перебора всех элементов множества Х-р.

Утверждение 2.1. При полном переборе сложность построения множества Хр равна 0(п2/п\Т>\), f — шах

t=l,...,n

Для построения множества Хц в работе предлагается использовать обобщённые суффиксные деревья, построенные над множеством V в алфавите номеров слов Еуу = {1,...,|W|}. Доказывается следующее утверждение: Утверждение 2.2. При использовании суффиксных деревьев сложность построения множества Х-р равна 0(n2f"), f = max \Xi\.

1=1,... ,71

В разделе 2.3 рассматриваются корректные инкрементные алгоритмы классификации, основанные на деревьях решений. Обозначим всё множество объектов через X, а множество признаков — через Т — {/ь ■••, /а/}, где fi : X -> Dfr Если l-D/J < оо, то fj — номинальный признак, иначе — числовой. Множество классов обозначим через Y. Пусть дана обучающая выборка X1 = {(xi, yi)i=i}, состоящая из I пар объект-ответ.

Определение 3. Алгоритм называется корректным на выборке X1, если классификация каждого объекта х € X1 безошибочна.

Алгоритм Incremental Tree Induction, ITI (Utgoff, 1997) предполагает ин-крементное построение бинарного дерева решений. В узловой вершине и ин-крементного дерева хранится пятёрка (L^, Rv, Д,, Хи, s„), где L„, Rv, — левая, правая вершина и предикат соответственно, Х„ с X1 — список объектов, прошедших через узел v, sv — состояние узла. Если через него прошли новые объекты, то sv = 1, иначе sv = 0. Будем рассматривать Р„(х) = [fj(x) < а] в

случае числового признака и р„{х) = \fjix) = а] — в случае номинального. Каждому листу и соответствует метка класса.

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

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

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

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

По начальной обучающей выборке строится композиция решающих деревьев МР = {{ШТгееиМг)У{=1, где ШТгеег — инкрементное дерево, построенное по некоторому набору признаков М,- С Т. Этот набор может быть получен случайным образом или в результате отбора признаков. Для построения каждого дерева используется одна и та же исходная выборка. Результатом классификации композиции является результат голосования входящих в неё деревьев.

Для каждого г-го дерева генерируется поднабор из М ^ признаков. Каждое дерево строится на основе алгоритма 1Т1 с небольшим измене-

нием — поиск наилучшего условия ветвления в узлах дерева осуществляется не по всему подможеству признаков, а по случайному признаку из М;.

Лемма 2.2. Композиция случайных инкрементных деревьев ШР, построенная по непротиворечивой выборке, является корректным алгоритмом классификации.

Получающиеся в ходе инкрементного обучения деревья могут существенно отличаться по качеству. В случае длинных обучающих выборок можно осуществить отбор деревьев по критерию качества классификации новых (контрольных объектов).

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

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

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

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

В третьей главе описывается архитектура программной системы из-

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

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

В разделе 3.2 приводятся результаты экспериментов. Эксперименты проводились для сравнения нового алгоритма ЮТ с алгоритмом 1Т1 на задачах репозитория иС1 и реальной выборке из 600 таблиц Росстата из коллекций «Регионы России, 2008» и «Финансы России, 2010».

Для оценки качества работы алгоритма использовался скользящий контроль. Инкрементное обучение запускалось несколько раз на одной выборке с её случайным перемешиванием. Сначала алгоритм обучался на небольшой начальной части обучающей выборки. Затем все объекты классифицировались по очереди. После этого объект подавался на дообучение. Строились кривые обучения — зависимости средней частоты ошибок от длины обучающей выборки.

В результате экспериментов оказалось, что новый алгоритм построения случайного инкрементного леса с отбором деревьев работает лучше на 7 задачах из 8 по сравнению с алгоритмом 1Т1 с транспозицией и без. Доля ошибок на задачах классификации при извлечении статистических показателей для алгоритма МР составила 0,07% на задаче распознавания типа ячеек, 0,03% на задаче распознавания суперстрок и 2,8% для задачи распознавания вложенных ячеек.

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

Список публикаций

[1] Интегрированная база данных по социально-демографической статистике: ресурс и пользовательские сервисы для поддержки гуманитарных исследований / А. В. Богомолова, О. И. Карасев, П. Ю. Кудинов и др. // Труды XI Всероссийской объединенной конференции «Интернет и современное общество» IMS—2008 (Санкт-Петербург, 28-30 октября 2008 года). — СПб.: Факультет филологии и искусств СПбГУ, 2008. — С. 58-59.

[2] Кудинов П. Ю. Задача распознавания статистических таблиц // Доклады 14-й Всероссийской конференции «Математические методы распознавания образов» ММРО-2009. — М.: МАКС Пресс, 2009,- С. 552-555.

[3] Кудинов П. Ю. Об одном подходе к организации системы распознавания таблиц, содержащих статистические данные // Материалы XVI Международной конференции студентов, аспирантов и молодых учёных «Ломо-носов-2009». — М.: Издательский отдел факультета ВМиК МГУ; МАКС Пресс, 2009. - С. 44.

[4] Кудинов П. Ю., Полежаев В. А. Динамическое обучение распознаванию статистических таблиц // Доклады 8-й Международной конференции «Интеллектуализация обработки информации» ИОИ-2010 (Республика Кипр, г. Пафос, 17-24 октября 2010).- М.: МАКС Пресс, 2010. — С. 512-515.

[5] Кудинов П. Ю., Полежаев В. А. Инкрементное обучение деревьев решений в задаче распознавания структуры статистических таблиц // Доклады 15-й Всероссийской конференции «Математические методы распознавания образов» ММРО-2011.- М.: МАКС Пресс, 2011,- С. 593-596.

[6] Кудинов П. Ю., Полежаев В. А. Композиция случайных инкремент-

21

ных деревьев и восстановление структуры таблиц (в печати) // Бизнес-информатика. — 2011. — № 4(18).

[7] Kudinov Р. У. Extracting statistics indicators from tables of basic structure // Pattern Recognition and Image Analysis. — 2011.— Vol. 21, no. 4.— Pp. 630-636.

Напечатано с готового оригинал-макета

Подписано в печать 02.11.2011г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 463.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ИМ. А.А.ДОРОДНИЦЫНА РАН

61 12-5/1574

На правах рукописи

У

КУДИНОВ ПАВЕЛ ЮРЬЕВИЧ

АДАПТИВНЫЕ МЕТОДЫ ИЗВЛЕЧЕНИЯ ИНФОРМАЦИИ ИЗ СТАТИСТИЧЕСКИХ ТАБЛИЦ, ПРЕДСТАВЛЕННЫХ В ТЕКСТОВОМ ВИДЕ

05.13.17 - теоретические основы информатики

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель

доктор физико-математических наук

К. В. Воронцов

Москва - 2011

Оглавление

Введение ......................................................................4

Глава 1. Концепция извлечения информации в полуавтоматическом режиме..............................11

1.1. Разработка системы поиска статистической информации . ... 11

1.1.1. Поиск новых источников данных..... ........12

1.1.2. Методы извлечения статистической информации из таблиц ..............................13

1.1.3. Инструменты поиска и отображения статистических показателей ..........................25

1.2. Концептуальная основа адаптивных методов извлечения статистической информации......................27

1.3. Основные выводы.......... ................30

Глава 2. Методы поиска и распознавания статистических данных .....................................33

2.1. Особенности структуры статистических таблиц.........33

2.1.1. Понятия и определения ..................34

2.1.2. Ключи в статистических таблицах............37

2.2. Задача извлечения статистических показателей.........38

2.2.1. Постановка задачи.....................38

2.2.2. Решение задачи.......................38

2.3. Алгоритмы динамического обучения...............60

2.3.1. Известные алгоритмы динамического обучения.....60

2.3.2. Решающие деревья........ .............64

2.3.3. Инкрементное построение дерева решений........67

2.4. Алгоритм ЮТ............................71

2.4.1. Обучение...........................72

2.4.2. Классификация и внедрение нового объекта.......73

2.4.3. Отбор деревьев.......................74

2.5. Основные выводы..........................79

Глава 3. Система поиска статистических данных 81

3.1. Архитектура системы извлечения данных............81

3.1.1. Предварительная обработка таблиц............82

3.1.2. Генерация признаков....................83

3.1.3. Динамическое обучение и классификация........84

3.1.4. Интерфейс оператора....................85

3.1.5. База данных.........................86

3.2. Эксперименты............................88

3.2.1. Оптимальное число деревьев...............89

3.2.2. Сравнение композиции и среднего дерева........91

3.2.3. Отбор деревьев.......................92

3.2.4. Задачи распознавания структуры таблиц........92

3.2.5. Вычислительная эффективность.............95

3.3. Основные выводы..........................96

Заключение..................................98

Литература..................................100

Введение

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

Актуальность темы. Социальная, экономическая, демографическая, финансовая статистика собирается и публикуется в бумажном и электронном виде различными организациями. Многие источники, например Росстат, ВЦИОМ, OECD, банки и финансовые организации предоставляют статистические данные в табличном виде (Рис. 1). Число таблиц, созданных ежегодно, измеряется сотнями тысяч. При этом в разных источниках могут использоваться разные термины и структуры таблиц для описания одних и тех же явлений. Это осложняет поиск, агрегацию и анализ динамики изменения статистических показателей.

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

является актуальной проблемой.

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

Распределение численности занятых в экономике регионов Российской _Федерации по возрастным группам в 2000 г. (в процентах)_

Всего в том числе в возрасте, лет Средний возраст, лет

до 20 2029 3039 4049 5059 6072

Российская Федерация 100 2,0 21,5 27,2 30,3 14,1 5,0 39,3

Центральный федеральный округ 100 1,6 20,0 26,6 30,1 15,7 6,1 40,1

Белгородская область 100 1,8 19,8 28,4 30,5 12,6 6,9 39,9

Брянская область 100 1,9 22,8 27,7 30,7 12,3 4,6 38,8

Владимирская область 100 2,2 21,0 26,5 30,6 14,4 5,2 39,4

Рпппнржпкая

Рис. 1. Пример статистической таблицы.

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

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

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

Более рациональным представляется режим диалога, при котором система предъявляет размеченные ею таблицы, а эксперт только исправляет допущенные системой ошибки. Эти исправления формируют обучающую выборку в режиме адаптивного или инкрементного обучения (incremental learning). При этом к алгоритму обучения предъявляются требование корректности — он не должен совершать ошибок на всех исправлениях, сделанных экспертом ранее.

Корректные инкрементные методы обучения, способные эффективно обучаться по выборкам длиной в сотни тысяч объектов и более, в литературе

практически не изучались.

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

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

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

2. Алгоритм инкрементного обучения композиций случайных деревьев (Random Incremental Forest, RIF).

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

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

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

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

— XI Всероссийская объединенная конференция «Интернет и современное общество» 1М8-2008 (Санкт-Петербург, 2008 год);

— XVI международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009» (Москва, 2009 год);

— 14-я всероссийская конференция «Математические методы распознавания образов» (Суздаль, 2009 год);

— 8-я международная конференция «Интеллектуализация обработки информации» ИОИ'Ю (Пафос, Республика Кипр, 2010 год);

— 6-я международная конференция «Служба экономических и социологических данных» Е808-2010 (Лондон, Великобритания, 2010 год);

— 15-я всероссийская конференция «Математические методы распознавания образов» (Петрозаводск, 2011 год).

Описания отдельных результатов работы включены в отчёты по проектам РФФИ Ж№Ю8-07-00305-а, 10-07-00609-а, 11-07-00480-а. Личный вклад. Вклад автора работы в результаты, выносимые на защиту, является определяющим.

Публикации. Материалы диссертации опубликованы в 7 статьях [3-8, 24], из них 2 работы [8, 24] — в журналах, включённых в Перечень ведущих рецензируемых научных журналов и изданий.

Структура и объём диссертации. Работа состоит из оглавления, введения, трёх глав, заключения и списка литературы. Содержание работы изложено на 105 страницах. Список литературы включает 46 наименований. Текст работы иллюстрируется 39 рисунками и 7 таблицами. Краткое содержание работы по главам.

В первой главе описывается общая проблематика извлечения статистической информации из таблиц, рассматриваются и анализируются известные подходы. Формулируется концепция построения поисковой системы по статистическим таблицам. Описываются особенности входящих в неё подсистем, реализация каждой из которых является сложной научно-технической задачей. Детально анализируется основная часть поисковой системы — подсистема извлечения статистических показателей из таблиц, представленных в текстовом виде. Предлагается методология, лежащая в основе разработки этой подсистемы.

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

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

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

В заключении подводятся итоги работы.

Глава 1

Концепция извлечения информации в полуавтоматическом режиме

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

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

1.1. Разработка системы поиска статистической информации

Система поиска статистической информации состоит из нескольких основных подсистем:

• подсистема поиска новых источников данных (статистических таблиц);

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

• подсистема поиска релевантных статистических показателей и их отображения.

1.1.1. Поиск новых источников данных

Поисковые роботы (crawlers) известных поисковых систем предназначены для прохода по всем страницам интернета или конкретных веб-сайтов и занесения их содержимого в поисковую базу данных. При поиске статистических данных интересны только те HTML-страницы, на которых находятся статистические таблицы. Таким образом, каждая страница должна быть проанализирована на предмет наличия в ней статистических таблиц. Существует два основных способа успешного распознавания этих таблиц — использование эвристических приёмов [21] и методов машинного обучения [41].

Первый способ подразумевает использование фиксированных правил определения того, является ли таблица информационной, или она используется для вёрстки HTML страницы. В работе Hsin-Hsi Chen и др. [21] предлагается руководствоваться двумя правилами для фильтрации неинформативных таблиц:

1) таблица содержит как минимум две ячейки;

2) таблица не содержит большого количества гиперссылок (определяется на основе порога).

Идея второй способа, предложенного Yalin Wang и Jianying Ни [41], заключается в использовании нескольких групп признаков, учитывающих разметку таблицы, тип содержимого и особенности содержимого текстовых ячеек. Значения признаков вычисляются на основе анализа HTML кода таблиц. Для классификации применяются известные методы машинного обучения,

такие как решающие деревья и машины опорных векторов (support vector machine, SVM).

Значительное число работ [10, 12, 20, 27, 31, 34] посвящено извлечению таблиц из изображений и текстовой псевдографики. Эти методы также могут быть использованы как средство получения структурированных таблиц в формате HTML.

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

1.1.2. Методы извлечения статистической информации из таблиц

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

1.1.2.1. Этапы извлечения статистических показателей

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

1) распознавание типа ячеек;

2) распознавание суперстрок;

3) �