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

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

Сорочинская Наталия Константиновна

РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ И ПРОГРАММНЫХ СРЕДСТВ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ИССЛЕДОВАТЕЛЬСКИХ ОТЧЕТОВ СИСТЕМ БОЛЬШОЙ РАЗМЕРНОСТИ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

- 6 ОКТ 2011

МОСКВА 2011

4855546

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

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

Ткаченко Владимир Максимович

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

Самохин Александр Борисович

кандидат технических наук Кожеватов Руслан Дмитриевич

Ведущая организация - ОАО "Институт электронных управляющих машин им. И.С.Брука"

Защита состоится 19 октября 2011г. в 15:00 на заседании диссертационного совета Д 212.131.05 при Московском государственном техническом университете радиотехники, электроники и автоматики по адресу: 119454 г. Москва, проспект Вернадского, дом 78.

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

Автореферат разослан " /5 " сентября 2011 года.

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

Е.Г. Андрианова

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

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

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

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

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

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

Объектом исследования являются системы большой размерности.

Предметом исследования является математическое обеспечение

извлечения знаний из исследовательских отчетов на естественном языке.

з

Цели и задачи исследования

Целью данной работы является исследование и разработка моделей, методов и программных средств автоматизированного извлечения знаний из печатных исследовательских отчетов для системы большой размерности (МАЛО). Для достижения указанной цели в работе решаются следующие задачи:

• разработать требования к инструментам извлечения знаний из систем большой размерности;

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

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

Основными теоретическими результатами работы, выносимыми на защиту и определяющими научную новизну работы, являются:

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

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

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

менее важные (наиболее слабо связанные с другими) элементы, упростить систему.

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

- как проводить анализ наличия системы знаний (идентификацию системы);

- как делать анализ взаимосвязей внутри системы (реконструкцию системы);

- как производить упрощение системы за счет сокращения наиболее слабо влияющих на поведение системы элементов (редукцию признаков).

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

Спроектированный модуль позволяет:

1. Выявлять подсистемы знаний из естественно-языковых печатных отчетов исследователей, проанализировать возможность объединения их в обобщенную систему и объединять их в систему.

2. На основе знаний из подсистем выявлять взаимосвязи между компонентами объединенной системы.

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

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

Апробация работы. Основные научные выводы и результаты работы докладывались на следующих конференциях: «Научно-техническая конференция МИРЭА» 56, 57 и 58 и Международной научно-технической

5

конференции Intermatic-2009. Материалы работы были опубликованы в 8-и печатных работах (тезисы и материалы международных и российских конференций). Три статьи опубликованы в журналах, рекомендованных ВАК. Имеется 2 акта внедрения результатов исследования в работу компании ООО "Форинтранс" и в работу кафедры МОВС МИРЭА.

Структура и объем работы: Диссертация, объемом в 119 страниц, состоит из введения, трех глав, заключения, списка использованной литературы из 129 наименований, двух приложений.

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

В первой главе содержится обзор проблем извлечения знаний и существующих методик извлечения знаний. Рассматриваются проблемы создания инструментария извлечения знаний из систем большой размерности. Формулируются требования к модулю автоматизированного анализа отчетов СБР. Делается обзор литературы по общей теории систем.

В разделе 1.1 рассматриваются особенности организации ввода/вывода данных в системах большой размерности.

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

В работе Долбоу подходы к проблеме наличия разных масштабов в системах большой размерности разделены на восемь категорий. Обычно при работе с разными масштабами используется совместно несколько нижеследующих методов:

1. «Мультирезолюционные» методы регулируют разрешение (масштаб) модели с помощью функции пространства, времени и данных.

2. Гибридные методы объединяют несколько моделей и числовых представлений в разных масштабах в рамках одной модели.

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

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

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

6. Методы определения неоднозначности данных при описании моделей.

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

8. Методы уменьшения размерности сокращают размерность модели до минимально возможной.

В разделе 1.2 первой главы дается набор требований к инструментам автоматизированного извлечения знаний. Анализируется применимость стандартных средств Data Mining для систем большой размерности. Недостатки стандартных средств подтолкнули нас к созданию нового инструмента для извлечения знаний который должен позволять:

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

2. Автоматически извлекать знания для решения задач в типичных и проблемных ситуациях.

3. Выявлять подсистемы данных.

4. Объединять подсистемы данных в обобщенную систему.

5. Анализировать взаимосвязи между элементами и подсистемами.

6. Упрощать системы данных.

Реализовать вышеперечисленные требования можно с помощью методов системологии. В частности в книге Дж. Клира приведены методы идентификационного и реконструктивного анализа отвечающие требованиям 4-6.

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

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

Для выделения синонимов из текста и составления тезауруса синонимов нами применяется подход, основанный на использовании понятий "однородность" и "соответствие".

Соответствие - понятие принадлежит нескольким категориям, но не большинству категорий (измеряется как 1СБ - обратная частота соответствия):

где ёу - частота понятия 3 в категории ру - вероятность того, что понятие ] находится в категории и п - число категорий.

Понятие должно быть значимым для категории, т.е. должна поддерживаться однородность. Однородность понятия ] в категории 1 может быть измерена как:

1СЯг-ЯыРцЬШРц

- ¿и

(1)

где Чу - вероятность, что понятие 3 есть в документе к ¡-ой категории, {/¡^¡-частота определения] в документе к, и п - число категорий.

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

А.ои - И,, (3)

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

с 1

с 1 с2 с3 .. с/ [и\] и2_/ иЗ_/ ,.иу

Л

СП

"»Л,

»11 и2\

ип\

ц.. т

и\т .... и2т «V

ипт

= К

П

И У

1к.. 1ш ¡к].. ш/],„

где Чу - однородность понятия ] в категории г, - подобие понятия ] к определению к; а ^ и С| указывают .¡-ое понятие, к-ой строки ¡-ой категории, соответственно.

Преобразуем 1><ш матрицу ^ в тхт матрицу Я (матрицу подобия понятия). Матрица Я, является симметричной, поскольку элемент Бу равен элементу б^ в матрице Я. Понятия будут группироваться, если количество их общих черт превысит определенный порог (назначаемый специалистом). Все понятия в группе можно рассматривать как

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

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

Эти задачи называют соответственно задачей реконструкции и задачей идентификации. Реконструкция может быть определена с помощью процедуры соединения '/и 2f, обозначаемой как '/ * 7f.

Для определения несмещенной реконструкции в эксперименте нами используется вероятностный вариант базовой процедуры соединения. В случае, когда окончательный результат процедуры соединения не соответствует заданной структурированной системе, применяется итеративная процедура соединения. Задаются локально согласованная структурированная система с поведением (SF) с вероятностными функциями поведения Jf функция f, полученная с помощью

базовой процедуры соединения, примененной к SF, и Д е [0, 1] - точность определения функции поведения несмещенной реконструкции. Значение А в нашей системе берется по умолчанию равным величине на порядок меньшей второго по возрастанию информационного расстояния. Выполняется алгоритм:

1) присвоить ./-О, ¡=1 и fa =f,

2)сделать соответствующее разбиение аргументов 'f и '"'/и выполнить операцию соединения Jf* '"'/ —>'/;

3) если i Ф 0(mod q), то / + 1 —»i,j+1 (mod q) —* j, и перейти на 2;

4)если \ft(c) - '"У(с)| > Д для какого-то с б С, то г+1 —»¡',/+1 (mod q) —> j, перейти на 2;

5) конец.

ю

Если после выполнения итеративной процедуры соединения fF(c) - А < 'f(c) < fF{c) + Д, для всех се С, то система согласована; в противном случае данная структурированная система SF глобально не согласована и реконструкции SF не существует, то есть fF = 0, и, следовательно, SF бессодержательна.

Если последовательность порождаемых процедурой функций поведения сходится к несмещенной реконструкции1, то подсистемы объединяются в систему.

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

d(/, V)=г-Ц! „с m iog2 -Ш- (4)

log2|c|^ / (с)

Для определения реконструируемости системы рассматриваются реконструктивные гипотезы, основанные на использовании С-структур, проводится ЛС-процедура. На основании изучения удачных реконструктивных гипотез можно строить аналитические выводы о важности конкретных подсистем и возможной редукции отдельных признаков. Результат операции - модель (либо модели) системы на которой показаны взаимосвязи элементов и сила этих взаимосвязей (Рис. 2).

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

11

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

Определение 1. Квадруплет S=(U, А, V, f) называют информационной системой, где U - непустое конечное множество объектов, названных областью обсуждения; А - непустое конечное множество признаков равное CUD, С - условное множество признаков, D -множество признаков решения, CCiD=0. Пусть Va - множество значений атрибута "а",/- конкретное значение признака А. Если существуют x6U,

а£С такие, что f(x, а) неизвестна (обозначается f (х, а)=*), информационная

система неполна; иначе - полна. Система неполна если неизвестно хотя бы одно значение признака.

Определение 2. Для таблицы неполного решения S=(U, CUD, V, f), ЬеВЕС, b является необязательным на В относительно признаков

решения, если существует x€U, и Db\{i,}(x)=Db(x).

Определение 3. Для таблицы неполного решения S=(U, CUD, V, f), все относительно необходимые признаки в В^С называют относительным

ядром В, обозначаемым CoreD(B).

Определение 4. Для таблицы неполного решения S=(U, CUD, V, f), RedD£B называется относительным редуцированием В, если DR(x) = DB(x)

и Redo относительно независим.

Свойство 1. Согев{В) =ПRedI>(B'), где RedD(B) представляет

относительную редукцию В.

Определение 5. Для таблицы неполного решения S=(U, CUD, V, f),

U={x,,x2..... x„}. U/D={Y|,Y2, ..., Ym}, матрица значений условного

подмножества признака В^С определена как:

Мв=(шву)„хт

fl

тхта " [о f(YJ,D)eDs(xi) (5)

Определение 6. Для таблицы неполного решения S=(U, CUD, V, f), Ме, Mf - матрицы значений условных подмножеств признаков Е, F соответственно, тогда расстояние между Ме, Mf обозначим как:

d(M°,Mf) = , \mff - mfj\, (6)

где

К ~mU =

О mf, = mf,

l] 'J /?ч

.1 mfj^mf, к>

Расстояние между матрицами значений может использоваться для описания относительного значения признака к подмножеству признаков.

Определение 7. Относительное значение признака ЬбВ^С в В

определено как:

п т

^вт(Ь) = = «Г-< I (8)

/-1 У-]

Свойство 2. Признак ЬбВ относительно необходим в В если

^8в\(ь)(Ь)>0.

Свойство 3. согео(В)={Ь€В |31§В\(Ь)(Ь)>0}.

Определение 8. Относительное значение признака Ь6С\В к В определено как:

«Ев{Ь) = с1(Ма,М^) = ±±\т'-т^ | (9)

Из Свойства 3 мы можем легко оценить относительное ядро согеа(С) неполной таблицы решений.

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

о

И H Mh- н

И о о о о

О О О О О H

о о о о о о

II

И И ИИ Й M

H И о о о о

О О ОО hi И

о о е> о о о

II

и* и о о о о

О О О О О И

О О ОО о о

оиирии^НИР о ии ни H ç> О о О О ОООО о о о о и

НООООООООО

s

о

Ч|

О ИИ И ЙИР И

О 1-й НИ H H О О О О ОООО О О О О H

и G О О О о с» о о о

.п

N»

II

О H H h-» H н-»ИИИИ

О ИИ ИИ и с* о о о ООООООИООИ

и ОООО о о о о о

с

W

II

о ииии иииии

ОНННННОООО

ооооооооои ИООООООООО

M

Е л s о

ы »

п> 2

а

(Î s s

SC

о и о

В!

я о

3

я

йч

CT«

о е> я ■в s

ы

я g

Множество объектов и

о 00 <1 о\ и> ю

¿5 <2> о о С/З

С) ¿5 О ¡75 к>

о О О О ел ш

о «¿> о о * е> £> 00

о * о О О кл и*

с> о о о о е> л со

о о О С) л © о о о О

и» о о (Л о о (Л о ь-» о о 1Л о о 1Л ы о а.

4* -< м < ><

•< о

а о и х о п>

2 Я о

о г> н ш о

я •а к и Я в> я о ш

О

Мн-во признаков решения Э

н

ю о\

Ы Я

С р

н

(в ?

К

к р

■о а

В (й я

Далее мы можем отдельно вычислить 518С/{Б1}(51) =5|ес/{52}(52)= 5|еС/{55}(55)=1; 51ес/{зз}(53)= 51ес/{54}(54)=0; 5^С/{56}(56)=5.

Шаг 2: для каждого с£С находим, что релятивное ядро -

соге0(С)={8ь 82, Б,, 86,}.

Шаг 3: пусть В=соге0(С), так как М°=МС, с)(Мс,Мв)=0 верно. Переходим к Шагу 4.

Шаг 4: Получаем, что минимальная относительная редукция В={8ь Бг, 85, Бб,}.

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

Таблица 2. Таблица неполного решения.

Условное множество признаков С

8, 82 8з 84 85 86 Л

1 0 0 0 0 0 0 0,20 }¥з

2 * 0 0 0 1 0 0,05

3 0 * * 1 0 0 0,05 V,

4 0 * * 0 0 0 0,05

5 1 * 0 0 1 0 0,10

6 1 1 1 0 0 0 0,05 у,

7 1 1 1 0 1 0 0,05

8 1 1 1 1 0 0 0,10 У 2

9 1 1 1 1 1 0 0,05 У,

10 1 1 1 1 1 1 0,30 н

я о

а

и

Он

со о

я

СП

я о.

с

0 м

1

я 2

1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0

1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0

1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0

с_1 1 0 0 м^1 1 0 0 1 0 0 мс/5з=1 1 0 0

1 1 0 0 1 0 0 2 1 1 0 0 3 1 1 0 0

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0

0 0' 0 1 0 0 1 0 0 0 1 0 0 0 1

1 0 1 0 1 0 1 0 1 0 1 0

1 0 0 0 1 0 1 0 1 0 0 0

1 0 1 0 1 0 0 0 1 0 0 0

1 0 •1 0 1 0 1 0 1 0 1 0

1 1 0 0 0 0 мс/ц 1 1 0 0 0 0 м<*6=; 1 1 0 0 0 0

1 1 0 0 1 1 0 0 1 1 0 0

1 1 0 0 1 1 0 0 0 1 0 0

1 1 0 0 1 1 0 0 1 1 0 1

0 0 0 1 0 0 0 1 1 1 0 1

Тогда относительные значения признаков равны соответственно:

81ёс/{81}(81> = 2

818су{52}(82)=81ёс/{54}(84)=81ес/{35}С85)=1;

согес(С)={81; Бг, 84, Бз, 86,}.

Минимальная относительная редукция В={81, 82, 84, 85, 86,}. Все относительно важные признаки сохранены, признак 83 сокращен.

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

Общий алгоритм работы МААО следующий. На вход системы подаются пороговое значение и, пороговое значение 1СБ, отчеты на естественном языке (в формате *ЛхО.

Шаг 1: Извлечение определений (важных с точки зрения пользователя лексем) из отчетов.

Шаг 2: Формирование и преобразование набора смысловых выражений. Анализ полноты информации. Если информация неполная переходим к шагу 3. Если информация полна - шаг 10.

Шаг 3: Выбор существенных определений, соответствие которых превышает пороговое значение, для формирования 1СЕ-набора.

Шаг 4: Из ЮИ-набора определений выбираются существенные определения для категорий, по теме исследования, на основании однородности.

Шаг 5: Формируется матрица ^ содержащая общие черты определения ] и других определений.

Шаг 6: Матрица ^ преобразуется в матрицу подобия К.

Шаг 7: Группируются элементы, количество общих черт которых превышает заданный порог.

Шаг 8: Валидация тезауруса синонимов специалистом.

Шаг 9: Расширение набора смысловых выражений за счет словаря синонимов. Проверка полноты информации. Если информация неполна -переходим к шагу 13. Если полна - шаг 10.

Шаг 10: Проверка идентифицируемости. В случае если сходимость не подтверждается - переходим к шагу 13.

Шаг 11: Реконструкция системы (формирование таблицы функций поведения, построение реконструктивных гипотез с помощью 11С процедур, выделение общей подсистемы и обработка укрупненных гипотез).

Шаг 12: Вывод результатов реконструктивного анализа. Окончание работы алгоритма.

Шаг 13: Вычисление матрицы значений Мс условного набора признака С.

Шаг 14: Поиск з1£С\|с>(с), при согес!(С)={с£С|з^С\{с1(с)>0}.

Шаг 15: Пусть В = соге^С), повторить:

(1) Определяется, верно ли d(Mc, Мв)=0. Если равенство верно,

тогда переход на Шаг 16, если нет - то (2).

(2) Выбирается признак с£С\В, который подходит под равенство

sigB(c)=maxc eC4BsigB(c') и объедяется с В=В U{c}, переход в (1).

Шаг 16: Вывод В (одной относительной редукции S). Окончание работы алгоритма.

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

На первом этапе из отчетов выделяются смысловые выражения: автоматически отбираются предложения содержащие важные лексемы и слова из словаря омонимов. Словарь омонимов содержит пары слов вида "растет-снижается", "увеличивается-уменьшается". Фрагмент отчета из рисунка 1п. преобразуется к виду, представленному в таблице 3.

Составитель: Иванова A.A.

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

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

Отчет № 12354

Рисунок 1. Фрагмент отчета о грузоперевозках с выделенными лексемами.

Таблица 3. Фрагмент отчета.

Здесь V, - выделенная лексема, a N(c) - частота с которой данное состояние встречается в отчетах. Если к лексеме Vi относится омоним, означающий увеличение показателей, то в таблице ставится значение "1", в случае уменьшения - "О". После анализа всех отчетов по выбранной тематике (в данном примере анализировались отчеты по перевозкам на маршруте г. Москва - г. Штутгарт) показатели N(c) преобразуются в соответствующие вероятности_Дс).

Ниже приведена таблица 4 по 180 отчетам о перевозке грузов по маршруту г.Москва-г.Штутгарт. В таблице рассматриваются структурированные системы по лексемам "простой", "количество рейсов", "штрафные санкции" (Vb V2, V3 соответственно).

Таблица 4. Вероятности состояний.

V, v2 'f(c) N(c) V, V3 N(c) v2 V3 Jf(c) N(c)

0 0 0.2 36 0 0 0,15 27 0 0 0,3 54

0 1 0,05 9 0 1 0,4 72 0 1 0,3 54

1 0 0,5 90 1 0 0,35 63 1 0 0,05 9

1 1 0,25 45 1 1 0,1 18 1 1 0,35 63

В этом эксперименте все состояния системы известны, по-этому мы можем проводить дальнейший анализ без поиска синонимов. На таблице 5 представлены данные идентификации.

Таблица 5. Идентификация системы (базовая процедура соединения, итеративная процедура соединения, проверка на сходимость).

V, v2 V, i—1 i=I6

0 0 0 0,05819398 0,05375808 0,09705094

0 0 1 0,141806 0,1462419 0,2869422

0 1 0 0,001987529 0,0009860699 0,001226729

0 1 1 0,04801247 0,04901393 0,1876463

1 0 0 0,3964844 0,4303799 0,2029491

1 0 1 0,1035156 0,06962015 0,01305782

1 1 0 0,06967213 0,06319926 0,04877327

1 1 1 0,1803279 0,1868007 0,1623537

Результаты базовой процедуры соединения (значения 2Г(2/*'Л) не соответствуют заданной структурированной системе. Так [^{у^уг} (0 0)]= 0,141806+0,05819398=0,19999998 не равно ^(0 0)=0,2, следовательно необходимо воспользоваться итеративной процедурой соединения. Последовательность порождаемых процедурой функций сходится к несмещенной реконструкции (на 16-й итерации).

Для того чтобы проанализировать зависимость между элементами обобщенной системы мы проводим реконструкцию системы (формирование таблицы функций поведения, построение реконструктивных гипотез с помощью ЯС процедур, выделение общей подсистемы и обработка укрупненных гипотез). Результаты реконструкции представлены в таблице 6. Из таблица 6 видно что наиболее слабая связь -У[Уг. При значении Д>0,004186408 эту связь можно удалить из системы, тем самым упростив её (рис. 2).

Таблица 6. Информационные расстояния в результате изъятия

одной из связей из системы.

V, V, V, V, У2 V, V, У2У3

0 0 0 0,05198794 0,1299081 0,04814521

0 0 1 0,09831183 0,07009188 0,1518548

0 1 0 0,008193568 0,01194327 0,0120363

0 1 1 0,09150665 0.03805672 0,0379637

1 0 0 0,4026904 0.3247702 0,310771

1 0 1 0,1470098 0,1752297 0,189229

1 1 0 0,06346609 0,05971638 0,1553855

1 1 1 0,1368337 0,1902836 0,09461452

Инс ). расст. 0,004186408 0,07655564 0,03859381

Рисунок 2. Вывод результатов реконструктивного анализа.

малотоннажные пере&озки

Маршрут Мз2

Отчет по маршруту

0,0765556'

простой (VI)

, Маршрут N»6

тоннажные п)ревоз^аршругМг5

¡трефные санкцм! (V)

0.03359361

весовой контроль

^Маршрут («4

Маршрут №7 (\'9) количество рвйсов](У2)

Еоннэжныв и»

0.03997091

.Маршрут М«1

0,02303095

стоимость рейса\у5)

0,02180637

'Маршрут №3

5отная плата.

автомобильные пепйвозки

количество автбпоЬдоБ

автопаркдо 150 л. с.

¡рвдепьные ста;

железнодорожные. пдрекозки^

мврские перевс

(®иа перевозу (грузопоток1эХлэрк до, 0(0

жы на топливо

мультимодальные перевод

автопарк до 200,

автопарк до,250 л.с.

Из рисунка 2 видно что лексемы "количество рейсов" и "простой" не связаны напрямую. На рисунке 3 показана графовая модель отчетов о грузоперевозках. В модели отчета №7 на связях цифрами показаны информационные расстояния от модели без этих связей до исходной модели. С помощью этих показателей можно делать вывод о том, какие связи необходимо исследовать в первую очередь.

;0 Отчеты по маршрутам

Отчеты по мультимодальным перевозкам

Рисунок 3. Графовая модель отчетов о грузоперевозках Если в результате удаления связей информационное расстояние которых меньше заданного Д образуются элементы не связанные с

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

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

В приложениях приведены: ГОЕБО диаграммы работы модуля и экспериментальные данные, полученные с помощью реализации МААО СБР.

Основные результаты исследования:

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

2. Предложена модификация методов системологии, включающая в себя:

• составление тезауруса синонимов;

• выделение и преобразование в числовую матрицу важной информации;

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

• решение задачи редуцирования признаков на неполных системах.

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

4. Предложена опытная реализация модуля автоматизированного анализа исследовательских отчетов СБР, которая позволила построить

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

22

Основные публикации по теме диссертации Публикации в изданиях, рекомендованных ВАК

1. Сорочинская Н.К. Интеллектуальный интерфейс системы большой размерности для обработки естественно-языковых отчетов. Наукоемкие технологии №6, т.11, Москва 2010. с.49-54;

2. Сорочинская Н.К., Сорочинский A.A. Нечеткий язык запросов для объектно-характеристической базы данных. Естественные и технические науки № 5, Москва 2010;

3. Сорочинская Н.К., Сорочинский A.A., Ткаченко В. М. Решение задач идентификации и реконструкции на неполных наборах данных в программном комплексе "система большой размерности". Труды ИСА РАН 2010. Т. 49 (1). с. 224-235

Публикации в других изданиях

1. Д.Э.Федотова, В.М.Ткаченко, Н.К.Сорочинская. Современные подходы к созданию «дружественно» интерфейса. Сборник трудов 57-й НТК МИРЭА. М.: МИРЭА, 2008;

2. Д.Э.Федотова, В.М.Ткаченко, Н.К.Сорочинская. Развитие POST-WIMP интерфейсов. Сборник трудов 58-й НТК МИРЭА. М.: МИРЭА, 2009;

3. Д.Э.Федотова, В.М.Ткаченко, Н.К.Сорочинская. Внедрения метода «Создания сценариев» в педагогическую практику для студентов направления «Информатика и Вычислительная Техника». Сборник трудов IX региональной научно-практической конференции «Профессиональная ориентация о методики преподавания с системе «школа-вуз» в условиях перехода к единой форме государственной аттестации выпускников общеобразовательных учреждений». М.: МИРЭА, 2009;

4. Сорочинская Н.К. Особенности организации ввода/вывода данных для системы большой размерности. Материалы Международной

научно-технической конференции «Фундаментальные проблемы радиоэлектронного приборостроения». М.: Энергоатомиздат, 2009;

5. Сорочинская Н.К. объектно-характеристическая база данных для задач моделирования структурированных систем. Объединенный научный журнал. Выпуск 10 (288), М.: АНП, 2009;

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 03.05.2011 Тираж 100 экз. Усл. п.л. 1,5 Печать авторефератов (495)730-47-74,778-45-60

ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

Введение.

ГЛАВА 1 СОВРЕМЕННЫЕ МЕТОДЫ ПРОЕКТИРОВАНИЯ И РЕАЛИЗАЦИИ СРЕДСТВ АВТОМАТИЗИРОВАННОГО ИЗВЛЕЧЕНИЯ ЗНАНИЙ.

1.1 Особенности организации ввода/вывода данных для системы большой размерности.

1.1.1 Области применения систем большой размерности. Методы анализа систем большой размерности.

1.1.2 Определение системы большой размерности.

1.1.2.1 Факторы, влияющие на сложность системы.

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

1.1.2.2.1 Семантическая сеть для хранения естественно-языковой информации системы большой размерности.

1.1.2 Поиск данных в информационных системах (Data Mining).

1.1.2.2 Основные минусы DM для работы с системами большой размерности.

1.3 Структуры программного комплекса системы большой размерности

Выводы по главе.

ГЛАВА 2 ОПИСАНИЕ ИСПОЛЬЗОВАННЫХ И РАЗРАБОТАННЫХ РАСЧЕТНЫХ МЕТОДИК И АЛГОРИТМОВ МОДЕЛИРОВАНИЯ.

2.1 Разработка и исследование методов автоматизированной обработки естественно-языковой информации.

2.2 Составление тезауруса синонимов.

2.2.1 Соответствие и однородность.

2.2.2 Тезаурус синонимов.

2.3 Общие понятия системного анализа.

2.3.1 Задачи идентификации и реконструкции.

2.3.2 Задача идентификации систем.

2.3.3 Коэффициент идентифицируемости.

2.3.4 Единственный выбор из реконструктивного семейства.

2.3.5 Процедуры соединения.

2.3.6 Базовая процедура соединения.

2.3.7 Итеративная процедура соединения.

2.3.8 Задача реконструкции.

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

2.4.1 Неполная информационная система. Определение.

2.4.3 Матрицы значений, базирующиеся на алгоритме редукции признака

2.4.4 Адаптация алгоритма для работы с экспериментальными данными

Выводы по главе.

ГЛАВА 3 РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ МОДУЛЯ АВТОМАТИЗИРОВАННОГО АНАЛИЗА ИССЛЕДОВАТЕЛЬСКИХ ОТЧЕТОВ ПРОГРАММНОГО КОМПЛЕКСА ДЛЯ СИСТЕМЫ БОЛЬШОЙ РАЗМЕРНОСТИ.

3.1 Задачи программного средства.

3.2 Архитектура модуля.

3.3 Модуль автоматизированного анализа отчетов.

3.5 Экспериментальные данные.

3.5.1 Решение задач идентификации и реконструкции с неизвестными подсистемами.

3.5.2 Решение задач идентификации и реконструкции с неполными данными.

3.5.3 Обработка отчетов о грузоперевозках.

3.6 Общий алгоритм работы модуля обработки естественно-языковых отчетов системы большой размерности.

Выводы по главе.

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

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

При разработке компьютерной дедуктивной системы синтеза и исследования описаний сложных явлений [1], выявилась необходимость разработки нового модуля автоматизированного анализа отчетов пользователя, позволяющего автоматически извлекать знания из систем большой размерности (СБР).

Исследования проблемы извлечения знаний из больших баз данных сосредоточены на развитии новых алгоритмов или усовершенствовании скорости или точности существующих [3]: концепция Фаяда [2], нечеткие ОМ [4], концепция Рейнартса [5].

Современные программные продукты, предназначенные для извлечения знаний [6-8], не подходят для решения вопросов, требующих привлечения большого числа узких специалистов. В первую очередь это вызвано сложностью в их освоении; требованиями к предварительной подготовке данных и большим количеством нерелевантных результатов. Практическая значимость подходов к решению проблем извлечения знаний, необходимость использования новых методов извлечения информации обуславливают актуальность данного диссертационного исследования.

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

Объектом исследования являются системы большой размерности.

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

Цели и задачи исследования

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

• разработать требования к инструментам извлечения знаний из систем большой размерности;

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

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

Основными теоретическими результатами работы, выносимыми на защиту и определяющими научную новизну работы, являются:

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

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

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

- как проводить анализ наличия системы знаний (идентификацию системы);

- как делать анализ взаимосвязей внутри системы (реконструкцию системы);

- как производить упрощение системы за счет сокращения наиболее слабо влияющих на поведение системы элементов (редукцию признаков).

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

1. Выявлять подсистемы знаний из естественно-языковых печатных отчетов исследователей, проанализировать возможность объединения их в обобщенную систему и объединять их в систему.

2. На основе знаний из подсистем выявлять взаимосвязи между компонентами объединенной системы.

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

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

Апробация работы. Основные научные выводы и результаты работы докладывались на следующих конференциях: «Научно-техническая конференция МИРЭА» 56, 57 и 58 и Международной научно-технической конференции 1гйегта1лс-2009. Материалы работы были опубликованы в 8-и печатных работах (тезисы и материалы международных и российских конференций). Три статьи опубликованы в журналах, рекомендованных ВАК. Имеется 2 акта внедрения результатов исследования в работу компании ООО "Форин-транс" и в работу кафедры МОВС МИРЭА.

Структура и объем работы: Диссертация, объемом в 119 страниц, состоит из введения, трех глав, заключения, списка использованной литературы из 129 наименований, двух приложений.