Средства интеграции, улучшения качества и координации данных в информационных потоках металлургического холдинга

Кожитов, Сергей Львович

Системный анализ, управление и обработка информации (по отраслям)

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

кандидата технических наук: Кожитов, Сергей Львович
город: Москва
год: 2009
специальность ВАК РФ: 05.13.01
цена: 450 рублей

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

Автореферат диссертации по теме "Средства интеграции, улучшения качества и координации данных в информационных потоках металлургического холдинга"

Московский институт стали и сплавов (Технологический университет)

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

Кожитов Сергей Львович

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

Специальность 05.13.01. — «Системный анализ, управление и обработка информации (в производственной сфере)»

Автореферат

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

Москва 2009

003461858

Работа выполнена на кафедре АСУ Московского государственного института стали и сплавов (Технологического университета)

Научный руководитель: к.т.н., доцент, Громов C.B. Официальные оппоненты:

Доктор технических наук, профессор, Прошин Иван Александрович Кандидат технических наук Сергеев Леонид Георгиевич

Ведущая организация: ФГУП "ЦНИИчермет им.. И.П. Бардина"

Защита состоится "04" Марта 2009 г. в 16-00 часов на заседании диссертационного совета Д.212.132.07 в Московском Государственном институте стали и сплавов (Технологическом университете) по адресу: 119049, г. Москва, Крымский вал., д.З. Аудитория № К-325

С диссертацией можно ознакомиться в библиотеке Московского Государственного института стали и сплавов (Технологического университета)

Автореферат разослан " "_2009 г.

Учёный секретарь к.т.н., профессор

Диссертационного Совета

Калашников Е.А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

• исследование особенностей построения КИС в условиях металлургического холдинга (КИС MX);

• выявление проблематики, связанной с интеграцией, улучшением качества и координацией данных при создании КИС MX;

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

• разработка методов автоматической классификации электронных документов и оценка их качества.

Методы исследования. В работе использовались методы определения редакционного расстояния, метод N-грамм, генетические алгоритмы, метод динамического программирования и методы классификации с использованием мер близости, оценки качества по мере F1.

Научная новизна диссертации заключается в следующих положениях:

• решена задача унификации справочника контрагентов КИС MX.

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

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

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

• методом перебора решена задача выбора оптимальных коэффициентов в модели Rubiyx.

Практическая ценность состоит в том, что разработанная методика нашла свое применение в КИС ПК "Брэдфорд" на ОАО "ГМК "Норильский никель", ОАО «ММК», Северсталь, Евраз-Холдинг, Мечел.

Апробация работы. Основные положения и результаты работы обсуждались на Российско-Японских семинарах "Перспективные технологии и оборудование для материаловедения, микро и наноэлектроники" в 2003, 2004, 2005,2006,2007 годах.

Публикации. По теме диссертации опубликовано 12 работ, включая одну работу в издании, рекомендованном ВАК РФ.

Структура и объем диссертационной работы. Диссертация состоит из введения, трёх глав, заключения и списка литературы, включающего 158 наименований. Основной объём работы занимает 186 страниц, в том числе 52 рисунка и 18 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Мониторинг проблем, с которыми сегодня сталкиваются многие предприятия при построении своих информационных систем, позволяет сделать некоторые выводы:

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

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

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

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

5. ИТ-Результатом массового использования ЕТЬ- технологий является построение распределенных интеллектуальных информационных систем, в которых рядовые пользователи смогут самостоятельно инкапсулировать свои повседневные рутинные операции обработки данных в разного рода сетевые сервисы и программные интеллектуальные агенты.

Одним из приоритетных направлений исследований в рамках КИС МХ является качество первичной нормативно-справочной информации (НСИ). Учитывая, что эта проблема существенно обострилась в связи с процессом образования холдингов на основе предложенных решений на базе системы ПК "Брэдфорд" в АО "Промсталь" в течение ряда лет выполнялся комплекс работ по выверке массивов нормативно-справочной информации (НСИ):

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

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

ОДНОРОДНОСТЬ

- ВХОДЯЩИХ» п№№

ЦЕНТРАЛИЗАЦИЯ

флитю, жн^ормыосн к уфилсж<ескм фуккииЛ

>)ж>шж>:тт>>тт>

УПРАВЛЯЕМОСТЬ ХОЛДИНГА

основные факторы;

ЭФФЕКТИВНОСТЬ СИСТЕМЫ БЮДЖЕТНОГО УПРАВЛЕНИЯ

КОМАНДА

yipnneioMi ж хузлтурш (СПГО4ртЦ) угршж ЮС1

МОТИВАЦИЯ

l*JX0H№t

Информационные техшлегнн уприиеиня С Сспжетнэш, прсгриооо-БвЕмтяого. сктувдюнюго жар )

Ценюс» сводимой а бюктт информация

(о состоят* »иутреющх &*»имв к пропорций ■жшнв^копспхтурмоЛжсочхшАнз-лолктжчвсюк мфортцжж)

Информацноншя »дел

Программный федстаа

Рисунок 1. Основные факторы, влияющие на уровень управляемости холдинга.

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

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

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

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

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

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

Настоящая работа касается проблемы интеграции, улучшения качества и координации данных в информационных потоках металлургического холдинга. Эти проблемы обусловлены неоднородностью информационных систем, которая возникает, с одной стороны в процессе создания и развития приложений в рамках КИС каждого предприятия, и, с другой стороны, при интеграции нескольких предприятий в холдинг. Зарубежный и отечественный опыт создания КИС позволяет предложить целый ряд технологических и научных решений по преодолению проблемы неоднородности. Наиболее перспективными среди них являются ETL-технологии (Extract Transform Load технологий - технологии извлечения, трансформации и загрузки их в хранилища данных) и MDM-системы (Master Data Management). Эти подходы позволяют унифицировать информационное пространство холдинга с минимальными затратами.

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

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

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

В процессе поиска дубликатов в нормативно-справочной базе данных (материалы, контрагенты) используются методы и алгоритмы анализа строк. За последние 50 лет накоплен большой положительный опыт решения задачи анализа строк. Наилучшими решениями для задачи сопоставления строк является алгоритм Бойера-Мура, для задачи определения всех вхождений образца в текст - метод Бойера-Мура-Хорспула; для расчета расстояний между строками используют преимущественно метрики, основанные на расстоянии Хэмминга, расстоянии Левенштайна и расстоянии редактирования. Для решения задачи о наибольшей общей подпоследовательности в большинстве случаев наилучшие результаты показывает метод Хиршберга. Выбор оптимального метода, метрики и алгоритма во многом зависит от характера решаемой задачи интеграции, улучшения качества и координации дан-

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

В качестве платформы для проверки новых методов и алгоритмов классификации текстов и поиска дубликатов в НСИ очень хорошо подходит система «Бредфорд», которая прошла апробацию на целом ряде металлургических холдингов.

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

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

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

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

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

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

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

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

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

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

КVI* К2) + КУ2* К22+ + КУц* К2К

...................................................................................... ^

КУ]+КУ2+ + к\\-

где К20бщийи - суммарный коэффициент релевантности при многопараметрическом поиске;

- коэффициент влияния параметра на суммарный коэффициент релевантности;

К21 - коэффициент релевантности параметра.

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

Практическая проверка правильности выявленного алгоритма расчета суммарного коэффициента релевантности при многопараметрйческом поиске аналогов рассмотрена в третьей главе на примере работы подсистемы «Контроль контрагентов» Системы ведения нормативно-справочной информации ОДО «ГМК «Норильский никель».

В данной работе рассмотрены формальные методы решения задачи нечеткого сравнения строк и нахождения коэффициента релевантности К2, из (1).

Определим коэффициент сходства двух строк как число от 0 до Пусть имеется функция от двух строк, которая осуществляет отобра-

жение меры сходства двух строк на отрезок [0;1], где 1 соответствует полному смысловому совпадению строк.

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

Итак, если множество похожих пар строк обозначить как 5е, множество непохожих пар строк как 0, а функцию от двух строк — то формальная постановка задачи записывается так:

, —> тах для всех пар строк <5д е 5° при условии У(5'1,5,2) > ,

/(5,, 52) —> шах для всех пар строк <Б/ е Б 0

при условии /(5,, 52) < Кп,

где К„ - пороговый коэффициент сходства. Кп может принимать значения из интервала (0,1).

При ослабленном условии необходимо всего лишь найти такую функцию/, значение которой на множестве похожих пар строк будет больше заданного порогового коэффициента Кп, на множестве непохожих пар строк меньше заданного порогового коэффициента К„

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

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

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

¿ф.ДУ ~>тт (2)

¿(Я^) = к,1 + к2Я + к£> + к4М, (3)

где Бь Бг - сравниваемые строки, I - количество операций вставки символа, Я - количество операций замены символа другим символом, Б - количество операций удаления символа,

М - количество «пустых» операций, когда на шаге не делается ничего.

Коэффициенты в зависимости от конкретного применения выбираются различными. В данной задаче к1=к2=к}=1, а к4~0. Программная реализация системы позволяет выбирать в зависимости от того, какой именно символ каким заменяется (алфавитно-взвешенное редакционное расстояние). Соответственно, искомая функция сходства строк выглядит так:

/(5„52) = 1-—

тах(| |,! |) ^ ^

где с1($1,$2) - редакционное расстояние между строками 5/ и 15^1 - ДЛИНЫ СТРОК 5/ И Б].

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

Пусть задан некоторый конечный алфавит Ух = {«''}, где - отдельный символ. Множество цепочек (строк) конечной длины, состоящих из символов алфавита Ут , называется языком на алфавите Ут и обозначается ЦУТ ). Отдельную цепочку из языка ЦУТ) будем называть высказыванием на этом языке. 1Ч-граммой на алфавите Ут называется цепочка дайной N. >1-грамма может совпадать с каким-то высказыванием, быть его подстрокой или вообще не входить в ЦУТ).

При использовании методов, основанных на ТЧ-граммах, математически задача сводится к разбиению обеих сравниваемых строк на множество Тиграм м, нахождение среди них повторяющихся элементов и вычисление пересечения и объединения множеств Ы-грамм первой и второй строки .

Алфавитом для строк в данном случае являются буквы русского алфавита, цифры и специальные символы (например, кавычки). Допустим, слово А - а!а2а3а4а2а} и слово В = Ь1Ь2а4а2а3, а длина И-граммы равна двум.

Задача заключается в том, чтобы найти все кортежи вида <а;, ар', <^2. <Ь), Ь!>,.... Также предполагается дополнение слов начальным и конечным пробелом, т.е. в данном примере необходимо учесть кортежи вида <_, а{>,

<а3, _>,-•

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

где а и р~ множества Ы-грамм слов А и В.

Ниже приведено подробное описание каждого из этапов алгоритма определения коэффициентов сходства строк.

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

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

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

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

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

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

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

Блок-схема алгоритма представлена на рис. 2.

Рисунок 2 - Алгоритм определения коэффициентов сходства строк

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

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

и,

Рисунок 3. Плотность распределения ошибок 14

Первым очевидным критерием качества модели является интегральная оценка количества ложных срабатываний 2-го рода. Согласно рисунку 3, модель

¿4

считается хорошей, если значение минимально. В данном случае:

Л'(Л) =

АГ„0<Д<Д,

лг2,д, <Л<Д2

ЛГзД <Д<Дз'

л^д <д<д4 дд>д4

(6)

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

и,,

Т" шах Ц

—р- тах кг

--ГОШ к.2

N„-2 --шах кг

СЬ

- Ш1П к2

N„-1 • тах кг

• Ш1П к.2

--тт кг

Рисунок 4. Отсев значений на первоначальных шкалах

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

(7)

где Ь - общее количество интервалов, на которых производится сравнение,

N1 — количество ложных срабатываний 2-го рода на ьм интервале. Если Ы, = 0, то принимается равным нулю. N0 определяется как

У N. . Значение Р будет стремиться к нулю с улучшением качества модели.

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

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

Задача классификации.

В рамках системы электронного документооборота (СЭД) КИС холдинга задача автоматической классификации текстовых документов имеет особую актуальность. Документооборот крупных металлургических холдингов достигает до 10000 документов в день.

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

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

Задача автоматической классификации текстов в общем виде формулируется как задача нахождения значения величины из {0,1} для каждого входа а¡, матрицы решения в соответствии с рисунком 5.

¿1 й} <1п

С1 «11 «и «1п

<* «<1 Щп

Стп «тп! ат1 атп

Рисунок 5. Матрица решения

1 Таких систем, как Дело, Оокител^т, Евфрат, Инталев-Документооборот и т. п.

На рисунке 5.С={с1,...,ст} является набором определенных категорий, аО™^,,...,^} - набор документов, которые нужно классифицировать. Величина равная 1 для а у указывает, что документ с!) относится к категории с,, тогда как величина равная 0 указывает, что документ с1у не относится к категории с .

Технология классификации ЛиЬгух включает следующие элементы.

1) Тематический (макро-) словарь специального формата.

2) Набор рубрик.

3) Набор текстов-образцов (по 2-5) для каждой рубрики.

4) Микро-словари специального формата (по одному для каждой рубрики).

5) Пороговые значения для каждой рубрики.

6) Формула для расчета коэффициента близости рубрики и документа.

7) Процедуры обучения классификатора и решения задачи классификации.

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

к = У^-му2*/С2 + >У3*^ .]00% 3

Тогда условие Р1 вхождения в класс (рубрику) документа <11 выглядит как:

Г 1, если К1> К* Р>= А

I 0, если Ю < К*

где , К*-пороговое значение К

В формуле (8) К,, К2, К3 - промежуточные коэффициенты по терминам из 1-го, 2-х и 3-х слов, отражающие степень вхождения терминов в классифицируемые документы (И (Ы, N 21, N 3 0 относительно общего количества терминов в микрословаре (| М, | М21, | М3|).

К1 = М, •100%

К2 =(Ы21/\М2 \) -100% >-для / = 1 ... п

к3 =сы31/|м31)-100%

, \\'2, И'з - весовые коэффициенты, отражающие вклад однословных, двухсловных и трехсловных терминов в общее значение коэффициента близости К. Сумма коэффициентов подчиняется условию:

IV, +Н> 2 з - 3 (9)

Рассмотрим формальную постановка задачи определения значений коэффициентов \У2, \Уз в формуле (8) для расчета меры близости документа к рубрике.

Имеется случайная выборка объемом 3299 документов из тестовой коллекции К.еи(егз-21578 по множеству рубрик с^ Для каждого документа ^ рассчитывается коэффициент Ку, определяющий принадлежность документа 1 к рубрике ; ^ Будем менять веса \уь луд. Для каждой комбинации весов \уь W2, Wз оценивается качество классификации по мере Р1. Найти такую комбинацию \л'ь у/2, ш3> которая обеспечит выполнение следующих критериев <

ш ^ ,

МахС^Ь) (10)

где РIя — значение меры И! для к-ой рубрики, т - число рубрик.

и-, < < \\'з 1 ■ (11)

В целях сокращения пространства поиска в качестве шага дискретизации было выбрано значение 0,2. Также на значения весов \у2 и были наложены дополнительные ограничения:

(0,2 < ш, < 1,4) Л (0,2 < w2 < 1,8) Л (0,2 < < 2,6) (12)

Таким образом, с учетом ограничений (9), (11) и (12) пространство поиска сократилось до 25 комбинаций.

Для проведения расчетов, были выбраны пятнадцать наиболее популярных рубрик коллекции 11еи1ег5-21578.

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

Таблица 1. Сводные данные по максимальным значениям показателей качества

Топик Старое Максималь- Номер комбинации весовых

значе- ное значение коэффициентов, обеспечиваю-

ние Fl Fl щей максимум Fl

Ship 0,82 0,882 3,5,9,10,13-15, 18-25

Acq 0,85 0,886 10,14,15,19

Corn grain 0,89 0,898 6,9,10, 13,18,22

wheat

Crude 0,9 0,921 3,5,8,12, 17,21,24

Earn interest 0,85 0,861 6,9, 13,14,19

Dlr 0,85 0,800 1,2,4,7,11,16,20,23,25

Gnp 0,84 0,921 14, 19,

Money-fx 0,88 0,880 2,3,15

Money-supply 0,81 0,836 3,5,8,12,17,21,24

Oilseed 0,73 0,800 10,14,15,19

Trade 0,88 0,880 3,5,6,8,9,12,13,17,18,21,22,24

Sugar 0,75 0,750 10,14,15,19

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

Таблица 2. Значения суммы И по каждому варианту комбинации весовых ко__эффициентов__

Номер ком- Сумма показателей ка- Число мак- Оценка значения

бинации чества П по всем рубрикам (3') симумов в рубриках

Исходный 10,050 Исходное значение

вариант

1 9,803 1 Хуже исходного

2 9,844 1 Хуже исходного

3 10,115 4 Лучше исходного

4 9,847 1 Хуже исходного

5 10,100 4 Лучше исходного

б 9,953 3 Хуже исходного

7 9,877 1 Хуже исходного

8 10,066 3 Лучше исходного

9 10,017 4 Хуже исходного

10 10,110 5 Лучше исходного

И 9,854 1 Хуже исходного

12 10,046 3 Хуже исходного

13 10,017 4 Хуже исходного

14 10,189 6 Мах

15 10,150 5 Лучше исходного

16 9,827 1 Хуже исходного

17 10,048 3 Хуже исходного

18 10,045 3 Хуже исходного

19 10,189 6 Мах

20 9,843 2 Хуже исходного

21 10,112 4 Лучше исходного

22 10,015 3 Хуже исходного

23 9,855 2 Хуже исходного

24 10,130 4 Лучше исходного

25 9,873 2 Хуже исходного

Как можно видеть из таблицы 2 лишь 9 из 25 комбинаций весовых коэффициентов имеют значения лучше исходной комбинации. Это говорит о том, что поставленная задача не тривиальная и имеет решение. Максимальное значение суммы Р1 (10,189) имеют две комбинации с номерами 14 и 19. Для этих комбинаций наблюдается и максимальное число локальных мак-

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

Таблица 3. Результаты численного эксперимента

Номер эксперимента W1 W2 W3 Сумма F1 по рубрикам

Исходные значения 0,2 1,3 1,5 10,050

14 0,8 1 1,2 10,189

19 0,8 1,2 1* 10,189

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

Wi <W2 = W3 (13)

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

В третьей главе рассмотрена практика работы поискового механизма АРМа «Контроль контрагентов» ОАО «ГМК «Норильский никель» в вариантах монопараметрического поиска и в варианте многопараметрического поиска с использованием алгоритмов расчета весовых коэффициентов и логарифмического коэффициента уровня качества поиска, разработанных в рамках настоящей диссертации.

Автоматизированное рабочее место эксперта (АРМ) «Контроль контрагентов» разработано как специализированная конфигурация программного конструктора «BRADFORD», используемого как средство интеграции, улучшения качества и координации, данных металлургического холдинга. Такой выбор доя практической реализации решений настоящей диссертации обусловлен не только тем, что этот софт с 1995 года активно используется на основных металлургических холдингах в России, но и тем, что по данным Агентства CNews данный программный комплекс входит в число восьми ведущих

российских разработок в классе Master Data Management2 (управления нормативно-справочной информацией).

Предназначение программного комплекса:

1. Для выполнения работ по объединению и выверке массивов НСИ (в том числе - перед загрузкой в ERP-системы), создания на их основе централизованных корпоративных справочников и классификаторов с таблицами переходных ключей.

2. Для обеспечения обязательной перепроверки на дублирование всех вновь вводимых записей в справочники и классификаторы системы НСИ

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

В главе представлено описание действующей поисковой системы АРМа «Контроль контрагентов» с вариантами расчета коэффициента релевантности на основе сравнения контрагентов по одному параметру (последовательно) и настройка многопараметрического поиска по разработанной в настоящей диссертации модели.

АРМ «Контроль контрагентов» предназначен для автоматизации регулярных процессов выявления двойников в корпоративном справочнике контрагентов ОАО «ГМК «Норильский никель».

Основные функции АРМ «Контроль контрагентов»:

1. Формирование таблицы новых поступлений контрагентов в КУДС (MDM-система, играющая роль хранилища сводного корпоративного справочника контрагентов) и мониторинга результатов ее обработки.

2. Поиск возможных двойников контрагентов для каждой позиции таблицы новых поступлений контрагентов по специально настроенному и согласованному с Заказчиком Сценарию с использованием методов точного поиска, приближенного (LDCE) поиска и поиска с механизмом нечеткой логики (NOM).

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

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

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

2 Иногда для MDM используется альтернативное название — управление справочными данными (Reference Data Management, RDM

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

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

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

Примеры двойников в справочнике контрагентов с расчетом суммарного коэффициента релевантности по полям «наименование» и «адрес» см. в таблице 4.

Таблица 4. Двойники в справочнике контрагентов с суммарного расчетом суммарного коэффициента релевантности

№ Наименование! Адрес 1 Ш общ ш кг наим. К2 адр. Наименованне2 Адрес2

66 Архангельская контора филиал ОАО ГМК горно металлурги чески й металлургическая Норильский никель Россия, 660059, Красноярский кран, г. КРАСНОЯРСК, ул. КОММУНАЛЬНАЯ, Д.2-А 100 100 100 Архангельская контора -филиал ОАО "ГМК "Норильский никель" Россия, 660059, Красноярский край, г. КРАСНОЯРСК, ул. КОММУНАЛЬНАЯ, д.2-А

66 Архангельская контора филиал ОАО ГМК горно металлургический металлургическая Норильский никель Россия, 660059, Красноярский край, г. КРАСНОЯРСК, ул. КОММУНАЛЬНАЯ, Д.2-А 79 100 69,1 Архангельская контора -филиал ОАО "ГМК "Норильский никель" Россия, 354008, Краснодарский край, г. СОЧИ, ул. ПИРОГОВА 10,

28 Заполярный филиал ОАО ГМК горно металлургический металлургическая Норильский никель Россия, 354008, Краснодарский край, г. СОЧИ, ул. ПИРОГОВА ю, 100 100 100 Заполярный филиал ОАО "ГМК"Норильский никель" Россия, 354008, Краснодарский край, г. СОЧИ, ул. ПИРОГОВА 10,

28 Заполярный филиал ОАО ГМК горно металлургический металлургическая Норильский никель Россия, 354008, Краснодарский край, г. СОЧИ, ул. ПИРОГОВА ю, 72 49,56 100 Главный офис ОАО "ГМК "Норильский никель" Россия, 354008, Краснодарский край, г. СОЧИ, ул. ПИРОГОВА 10,

78 1 ОАО "Кольчугинский завод по обработке цветных металлов им С. Орджоникидзе" Россия, 600017, Владимирская область, г. ВЛАДИМИР, ул. (ГОРОХОВАЯ, д.15 100 100 100 ОАО "Кольчугинский завод по обработке цветных металлов им. С. Орджоникидзе" Россия, 600017, Владимирская область, г. ВЛАДИМИР, ул. ГОРОХОВАЯ, д.15

Использование результатов исследования по многопараметрическому методу поиска двойников в подсистеме «Контроль контрагентов» Системы ведения НСИ ОАО «ГМК «Норильский никель» позволило повысить общие показатели эффективности работы информационно-поисковой системы и обеспечить требуемый уровень качества сводного корпоративного справочника контрагентов.

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

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

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

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

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

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

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

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

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

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

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

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

Была описана система с автоматизированным рабочим местом для сотрудников службы ведения НСИ.

Результаты исследований применяются во множестве систем документооборота металлургических холдингов России, таких как ОАО "ГМК "Норильский никель" Мечел, ММК, Северсталь, Евраз-Холдинг.

Основные результаты диссертации опубликованы в следующих работах

1.Калашников Е.А., Дубравина Т.В., Кожитов СЛ. Гибридный генетический алгоритм для решения транспортных задач // Материалы 4-го Российского-Японского семинара "Перспективные технологии и оборудование для материаловедения, микро и наноэлеюроники": 22-23 мая 2006 Астрахань. Астраханский государственный университет, 2006 год, с.453-456.

2.Бодров Д.А., Поляков В.Н., С.Л. Кожитов Автоматизация текстового оборота на металлургическом предприятии и новые поисковые технологии // Материалы 4-го Российско-Японского семинара "Перспективные технологии и оборудование для материаловедения, микро и наноэлеюроники": 22-23 мая 2006 Астрахань, Астраханский государственный университет, 2006 год, с.487-494.

3. Громов C.B., Кожитов С.Л. Подход к созданию инструментов поддержки принятия решений при разработке технологических процессов. // Материалы Российско-Японского семинара "Материаловедение и металлургия. Перспективные технологии и оборудование" 25 марта 2003 года Москва. Московский государственный институт стали и сплавов, 2003 год, с.361-366.

4.Yu.N. Pronin, S.L. Kozhitov. Wide use of intégration tools as the best means оf optimization of quality and coordination of information data flows in holding structures/ of 2nd Russian-Japanese Seminar "Perspective Technologies, Materials and

Equipments of Solid-State Electronic Components ": April 6, 2004-Moscow, Moscow State Institute of Steel and Alloys (Technological University), 2004, p. 417-426.

5. S.V. Gromov, S.L. Kozhitov. Development of Tools о fan in-line Processing of the Data and Decision Making for the Companies with a Complex Organization Structure on the Basis of Technologies of Web-Services // Proceedings of 2nd Russian-Japanese Seminar "Perspective Technologies, Materials and Equipments of Solid-State Electronic Components ": April 6,2004-Moscow, Moscow State Institute of Steel and Alloys (Technological University), 2004, p. 428-435.

6. Е.А.Калашников, T.B. Дубравина, C.Jl. Кожитов. Применение генетического алгоритма для решения модифицированных специальных задач линейного программирования с множеством квазиоптимальных решений // Металл оборудование инструмент, май-август 2005. Издательский дом "ИКАР", Московский институт стали сплавов с.57-59.

7. S.V. Gromov, S.L. Kozhitov. Development and research of components for the distributed data processing and decision-making for the companies with complex organizational structure/ Труды III Российско-Японского семинара "Оборудование и технологии для производства компонентов твердотельной электроники и нано-материалов", 12 апреля Москва 2005. Московский институт стали и сплавов, 2005 год с.163-167.

8. Ю.Н. Пронин, A.M. Перепёлкина, C.JI. Кожитов. О построении корпоративных информационных систем // Образование, наука и производство, Межву-зовый сборник научных трудов. Т. II. Экономика и Менеджмент. Московский государственный институт стали сплавов 2001 г. с. 134-137//

9. Ю.Н. Пронин, C.JI. Кожитов. Возможности ETL-технологий для построения гибких информационных систем управления холдингами на примере построения системы управления нормативно-справочной информацией //Научно-практический семинар "Научно-техническое обеспечение деятельности предприятий, институтов и фирм" Москва 1 июля 2003г., Москлвский Государственный Институт Стали и Сплавов с. 208-218//

10. Бодров Д.А., Кожитов C.JL, Поляков В.Н. Задачи интерактивной обработки поисковых запросов в теоретико-множественной постановке. //Известия Саратовского унив. Новая серия. Серия «Математика. Механика. Информатика» - Саратов, 2007, т.7. Вып. 1, стр. 78-83.//

11. Ю.Н. Пронин, Кожитов С.Л., Дорогова Л.В. Использование поисковой системы ПК BRADFORD для организации перевода открытого технического словаря eOTD ЕССМА /ГГруды V Российско-Японского семинара "Оборудование, технологии и аналитические системы для материаловедения, микро- и нано-электроники" Том 2,2007 г., с. 1016-1026//

12. Ю.Н. Пронин, Кожитов С.Л., Давидюк Н.В. Разработка и ведение российской версии открытого тезнического словаря eOTD ЕССМА при помощи специализированного программного комплекса BRADFORD/zTpyflbi V Российско-Японского семинара "Оборудование, технологии и аналитические системы для материаловедения, микро- и наноэлектроники" Том 2,2007 г., с. 1027-1039//

Соискатель

С.Л. Кожитов

Формат 60 х 90 7,6 Тираж 100 экз. Объем 1,75 пл. Заказ 2082

Отпечатано с готовых оригинал-макетов в типографии Издательского Дома МИСиС, 117419, Москва, ул. Орджоникидзе, 8/9 Тел.: 954-1922

Оглавление автор диссертации — кандидата технических наук Кожитов, Сергей Львович

ВВЕДЕНИЕ.

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

МЕТАЛЛУРГИЧЕСКОГО ХОЛДИНГА.

1.1. Развитие процессов интеграции в неоднородных информационных системах. Л

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

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

1.4. Характеристика полнотекстового документооборота на металлургическом пр едприятии.

1.5. Интеграция данных при создании КИС.

1.6. Проблемы интеграции разнородных данных.

1.7. Интеграция данных приложений.;.

1.8. Решение проблем интеграции данных на основе федеративных хранилищ данных.

1.9. Управление неоднородным контентом в системе корпоративного документооборота.

1.10. MDM системы.

1.10.1. Типы MDM-систем.

1.10.2. Зарубежные системы MDM-класса.

1.10.3. Отечественные системы MDM-класса.:.

1.10.4. Сертификация данных на соответствие ISO 8000.

1.11. Корпоративная поисковая система и ее предназначение.

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

1.13. Анализ методов построения мер близости текстовых реквизитов.

1.13.1. Принцип оптимальности в задаче динамического программирования.

1.13.2. Понятие редакционного расстояния между двумя строками.

1.13.3. Метод выравнивания строк vs редакционного предписания.

1.13.4. Алгоритмы анализа строк.

1.14. Модели оптимизации, построенные на эволюционных принципах.

1.15. Генетические алгоритм и его особенности.

1.16. Выводы.

ГЛАВА 2. МЕТОДЫ И МОДЕЛИ ИНТЕГРАЦИИ, УЛУЧШЕНИЯ КАЧЕСТВА И КООРДИНАЦИИ ДАННЫХ В НЕОДНОРОДНЫХ СИСТЕМАХ.

2.1. Выявление двойников в справочных информационных массивах металлургического холдинга.

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

2.1.2. Содержательная постановка задачи.

2.1.3. Математическая постановка задачи.

2.1.4. Метод вычисления минимального редакционного расстояния.

2.1.5. Методы решения с использованием N-грамм.

2.1.6. Формальный синтаксический анализ.

2.1.7. Алгоритм построения модели с учетом формального синтаксического анализа.

2.1.8. Задача принятия решений и обучение алгоритма.

2.1.9. Алгоритм определения коэффициентов сходства строк.

2.1.10. Проверка адекватности построенной модели.

2.1.11. Результаты работы программы.

2.2. Задача классификации документов в MDM-системе холдинга.

2.2.1. Проблема классификации текстов в СЭД.

2.2.2. Общая постановка задачи классификации.

2.2.3. Технология классификации по методу Rubryx.

2.2.4. Описание коллекции Reuters-21578.

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

2.3. Решение задачи выбора весовых коэффициентов с использованием генетических алгоритмов.

2.3.1. Исходная постановка.

2.3.2. Описание модификации генетического алгоритма.

2.3.2.1. Методы отбора.

2.3.2.2. Кроссинговер и мутация.

2.3.3. Программное обеспечение.

2.3.4. Описание основных модулей программы.

2.3.5. Пользовательский интерфейс.

2.4. Выводы.

ГЛАВА 3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МОДЕЛИ РАСЧЕТА СВОДНОГО КОЭФФИЦИЕНТА РЕЛЕВАНТНОСТИ ПРИ РЕШЕНИИ ЗАДАЧ ПОВЫШЕНИЯ

КАЧЕСТВА ОСНОВНЫХ ДАННЫХ В МЕТАЛЛУРГИЧЕСКОМ ХОЛДИНГЕ.

3.1. Описание проблемной ситуации.

3.2. Содержательная постановка задачи.

3.3. Автоматизированное рабочее место «Контроль контрагентов».

3.3.1. Основные функции АРМ «Контроль контрагентов.

3.3.2. Поисковая система АРМ «Контроль контрагентов».

3.3.3. Организация системы поиска.

3.3.4. Варианты поиска.

3.3.4.1. Точный поиск (LIKE-поиск).127.

3.3.4.2. НОМ-поиск.

3.3.4.3. Особенности НОМ-поиска. Ранг и коэффициент релевантности.

3.3.4.4. Особенности НОМ-поиска. Вспомогательные справочники.

3.3.5. Сценарий автоматического поиска двойников в АРМ «Контроль контрагентов».

3.3.6. Ручной поиск двойников в АРМ «Контроль контрагентов».

3.3.7. Методология работы АРМ «Контроль контрагентов».

3.4. Результат доработки АРМ «Контроль контрагентов».

3.5. Программный комплекс «Брэдфорд».

3.6. Выводы.

Введение 2009 год, диссертация по информатике, вычислительной технике и управлению, Кожитов, Сергей Львович

В современных условиях успешно координировать бизнес, и управлять бизнес-процессом возможно, лишь проанализировав и структурировав огромное количество информации. Поэтому очень важно максимально автоматизировать операции с данными: ввод, первичную обработку, структурирование и дальнейшее представление в виде удобном для лица, принимающего решение (ЛПР). Этой цели на предприятиях служат корпоративные информационные системы. Функциями КИС являются, в частности, такие важные разделы, как поддержка принятия решений и мониторинг на предприятии. Под мониторингом понимается процесс периодического обследования состояния какой-либо системы, отслеживания изменений этого состояния с течением времени, выявление и ранжирование факторов, обусловливающих эти изменения. Задача не сводится только к принятию решения о внедрении информационной системы на предприятии. Каждому предприятию нужна информационная система, разработанная под его индивидуальную схему функционирования. Например, данные, которые подлежат обработке, накапливаются годами. Из-за отсутствия единой системы они могут быть избыточными или неполными, различными по структуре, представленными в разных форматах. А формы отчётности и представления информации для ЛПР на каждом предприятии свои, зависящие от специфики его деятельности. Поэтому придётся использовать специализированные программные средства, предназначенные для работы с заведомо некачественными данными, позволяющие упорядочивать, согласовывать и выверять данные, прогоняя их через долгую цепочку сложных трудоёмких процедур. Итог как правило заключается в виде потери времени и немалых материальных затратах на дорогостоящее программное обеспечение и оборудование для него.

Острота проблемы возрастает в случае, если КИС внедряется в условиях холдинга, составные части которого являются самостоятельными бизнес-структурами, обладающими собственными стандартами представления и обработки данных.

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

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

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

В соотвегствии с поставленной целью были решены следующие задачи исследования:

• исследование особенностей построения КИС в условиях металлургического холдинга (КИС MX);

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

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

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

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

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

Метод оценки качества мер близости, основанных на мерах Pr, Re и F1.

Научная новизна диссертации заключается в следующих положениях.

Разработана методика интеграции разнородных данных в условиях КИС MX (рисунок 27).

Разработана архитектура системы для выверки массивов нормативно-справочной информации (рисунок 49).

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

На основе модели расчета сходства текстовых реквизитов разнородных баз данных разработан алгоритм.

Методом Левинсштайна решена задачи поиска оптимальных параметров модели расчета сходства текстовых реквизитов;

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

Методом перебора решена задача выбора оптимальных коэффициентов в модели

Rubryx.

Практическая ценность работы состоит в том, что разработанная методика нашла свое применение в рамках КИС таких крупных предприятий металлургического комплекса как: ОАО "ГМК "Норильский никель", ОАО «ММК», ОАО «Северсталь», «Евраз-Групп», «Меч ел».

Публикации. По теме диссертации опубликовано 12 работ, включая одну работу в издании, рекомендованном ВАК РФ.

1.Калашников Е.А., Дубравина Т.В., Кожитов C.JI. Гибридный генетический алгоритм для решения транспортных задач // Материалы 4-го Российского-Японского семинара "Перспективные технологии и оборудование для материаловедения, микро и наноэлектроники": 22-23 мая 2006 Астрахань. Астраханский государственный университет, 2006 год, с.453-456.

2.Бодров Д.А., Поляков В.Н., C.JI. Кожитов Автоматизация текстового оборота на металлургическом предприятии и новые поисковые технологии // Материалы 4-го Российско-Японского семинара "Перспективные технологии и оборудование для материаловедения, микро и наноэлектроники": 22-23 мая 2006 Астрахань, Астраханский государственный университет, 2006 год, с.487-494.

3. Громов С.В., Кожитов C.J1. Подход к созданию инструментов поддержки принятия решений при разработке технологических процессов. // Материалы Российско-Японского семинара "Материаловедение и металлургия. Перспективные технологии и оборудование" 25 марта 2003 года Москва. Московский государственный институт стали и сплавов, 2003 год, с.361-366.

4.Yu.N. Pronin, S.L. Kozhitov. Wide use of integration tools as the best means of optimization of quality and coordination of information data flows in holding structures/ of 2nd Russian-Japanese Seminar "Perspective Technologies, Materials and Equipments of Solid-State Electronic Components April 6, 2004-Moscow, Moscow State Institute of Steel and Alloys (Technological University), 2004, p. 417-426.

5. S.V. Gromov, S.L. Kozhitov. Development of Tools of an in-line Processing of the Data and Decision Making for the Companies with a Complex Organization Structure on the Basis of Technologies of Web-Services // Proceedings of 2nd Russian-Japanese Seminar "Perspective Technologies, Materials and Equipments of Solid-State Electronic Components ": April 6,2004-Moscow, Moscow State Institute of Steel and Alloys (Technological University), 2004, p. 428-435.

6. Е.А.Калашников, T.B. Дубравина, C.JI. Кожитов. Применение генетического алгоритма для решения модифицированных специальных задач линейного программирования с множеством квазиоптимальпых решений // Металл оборудование инструмент, май-август 2005. Издательский дом "ИКАР", Московский институт стали сплавов с.57-59.

7. S.V. Gromov, S.L. Kozhitov. Development and research of components for the distributed data processing and decision-making for the companies with complex organizational structure/ Труды III Российско-Японского семинара "Оборудование и технологии для производства компонентов твердотельной электроники и наноматериалов", 12 апреля Москва 2005. Московский институт стали и сплавов, 2005 год с. 163-167.

8. Ю.Н. Пронин, A.M. Перепёлкина, C.JI. Кожитов. О построении корпоративных информационных систем // Образование, наука и производство, Межвузовый сборник научных трудов. Т. II. Экономика и Менеджмент. Московский государственный институт стали сплавов 2001 г. с. 134-137//

10. Бодров Д.А., Кожитов C.JI., Поляков В.Н. Задачи интерактивной обработки поисковых запросов в теоретико-множественной постановке. //Известия Саратовского унив. Новая серия. Серия «Математика. Механика. Информатика» - Саратов, 2007, т.7. Вып. 1, стр. 78-83.//

11. Ю.Н. Пронин, Кожитов C.JI., Дорогова JI.B. Использование поисковой системы ПК BRADFORD для организации перевода открытого технического словаря eOTD ЕССМА //Труды V Российско-Японского семинара "Оборудование, технологии и аналитические системы для материаловедения, микро- и наноэлектроники" Том 2, 2007 г., с. 1016-1026//

12. Ю.Н. Пронин, Кожитов C.JI., Давидюк Н.В. Разработка и ведение российской версии открытого тсзнического словаря eOTD ЕССМА при помощи специализированного программного комплекса BRADFORD/ЛГруды V Российско-Японского семинара "Оборудование, технологии и аналитические системы для материаловедения, микро- и наноэлектроники" Том 2, 2007 г., с. 1027-1039//

Структура и объем диссертационно]'! работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 158 наименований. Общий объём работы занимает 186 страниц, в том числе 54 рисунка и 18 таблиц.

Заключение диссертация на тему "Средства интеграции, улучшения качества и координации данных в информационных потоках металлургического холдинга"

3.6. Выводы

В результате доработки ПК «Брэдфорд» по предложенной модели многопараметрического поиска двойников в настройке параметров НОМ-поиска реализована возможность настройки расчета коэффициентов релевантности по дополнительным полям со степенью их влияния на суммарный коэффициент релевантности по набору параметров. Использование результатов исследования по многопараметрическому методу поиска двойников в подсистеме «Контроль контрагентов» Системы ведения НСИ ОАО «ГМК «Норильский никель» позволило повысить общие показатели эффективности работы информационно-поисковой системы и обеспечить требуемый уровень качества сводного корпоративного справочника контрагентов.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Была описана система с автоматизированным рабочим местом для сотрудников службы ведения НСИ.

Результаты исследований применяются в составе систем документооборота металлургических холдингов России, таких как ОАО "ГМК "Норильский никель", Мечел, ММК, Северсталь, Евраз-Холдинг.

Библиография Кожитов, Сергей Львович, диссертация по теме Системный анализ, управление и обработка информации (по отраслям)

1. Елена Монахова. Блеск и нищета российских холдингов. PC WEEK/RE. № (239)17'2000.

2. Влад Боркус, Елена Монахова . Интеграция: новое решение старых проблем . PC Week №36/2003.

3. ETL ключ к готовности и корректности данных. Скотт Стейначер, Еженедельник «Computerworld Россия» 20/01/2001 №03.

4. QUOTE.RU: Информация о компаниях: отчеты эмитентов, бухгалтерские балансы, акции, аналитика, http://www.quote.ru/shares/baseemitent.shtml

5. Официальный сайт компании "Ростерминал" http://wvvw.rosterminal.com/

6. Data Integration: Using ETL, EAI, and EII Tools to Create an Integrated Enterprise. TDWI Report, http://wvvw.tdwi.org/

7. Informatica PowerCenter. Любые данные. В любой системе. В любое время. http://www.data-integration.ru/materiali.html

8. Informatica PowerCenter. Доступ к сложным данным. По требованию. http://www.data-integration.ru/materiali.html

9. Интеграция данных и приложений. Byte/Россия. № 6. 2006.

10. Дэвид Уэддингтон (David Waddington). Архитектурный подход к интеграции информации: обзор проблемы федеративных Хранилищ данных. (An Architected Approach to Information Integration Federated Enteiprise Data Warehousing Overview).

11. Хранилища данных: шаги от идеи до внедрения. Cnews. http://www.cnews.ru/reviews/index.shtml72006/08/17/208822l

12. Майкл Дж. Д. Саттон. Корпоративный документооборот: принципы, технологии, методологии внедрения. // Азбука, Б-Микро, 2002

13. Бодров Д. А., Поляков В.Н. Проблемы создания эффективных поисковых машин (обзорная статья) // Обработка текста и когнитивные технологии: Сборник (Вып. 7)

14. Под ред. Соловьева В. Д. — Казань: 2002. Стр. 8-55

15. Van Rijsbergen, С. J. Information Retrieval, 2nd edition— Dept. of Computer Science, University of Glasgow, 1979.

16. Fabrizio Sebastiani, Machine Learning in Automated Text Categorisation, Consiglio Nazionale delle Ricerche, Italy.

17. Joachims, T. 1998. Text categorization with support vector machines: learning with many relevant features. In Proceedings of ECML-98, 10th European Conference on Machine Learning (Chemnitz, DE, 1998), pp. 137-142.

18. Lam, W., Low, K. F., and Ho, C. Y. 1997. Using a Bayesian network induction approach for text categorization. In Proceedings of IJCAI-97, 15th International Joint Conference on Artificial Intelligence (Nagoya, JP, 1997), pp. 745-750.

19. Li, H. and Yamanishi, K. 1999. Text classification using ESC-based stochastic decision lists. In Proceedings of CIKM-99, 8th ACM International Conference on Information and Knowledge Management (Kansas City, US, 1999), pp. 122-130.

20. Yang, Y. and Liu, X. 1999. A re-examination of text categorization methods. In Proceedings of SIGIR-99, 22nd ACM International Conference on Research and Development in Information Retrieval (Berkeley, US, 1999), pp. 42-49.

21. Lewis, D. D. and Ringuette, M. 1994. A comparison of two learning algorithms for text categorization. In Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval (Las Vegas, US, 1994), pp. 81-93.

22. Apt'e, C., Damerau, F. J., and Weiss, S. M. 1994. Automated learning of decisionrules for text categorization. ACM Transactions on Information Systems 12, 3, 233-251.

23. Cohen, W. W. and Singer, Y. 1999. Context-sensitive learning methods for text categorization. ACM Transactions on Information Systems 17, 2, 141-173.

24. Moulinier, I., Ra"skinis, G., and Ganascia, J.-G. 1996. Text categorization: a symbolic approach. In Proceedings of SDAIR-96, 5th Annual Symposium on Document Analysis and Information Retrieval (Las Vegas, US, 1996).

25. Yang, Y. 1999. An evaluation of statistical approaches to text categorization. Information Retrieval 1, 1-2, 69-90.

26. Dagan, I., Karov, Y., and Roth, D. 1997. Mistake-driven learning in text categorization. In Proceedings of the 2nd Conference on Empirical Methods in Natural Language Processing (Providence, US, 1997), pp. 55-63.

27. Lam, W. and Ho, C. Y. 1998. Using a generalized instance set for automatic text categorization. In Proceedings of S1G1R-98, 21st ACM International Conference on Research and Development in Information Retrieval (Melbourne, AU, 1998), pp. 81-89.

28. Weiss, S. M., Apte, C., Damerau, F. J., Johnson, D. E., Oles, F. J., Goetz, Т., and Hampp, T. 1999. Maximizing text-mining performance. IEEE Intelligent Systems 14, 4, 63-69.

29. Schapire, R. E. and Singer, Y. 2000. BoosTexter: a boosting-based system for text categorization. Machine Learning. Forthcoming.

30. Вентцель E.C. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001.— 208 с.

31. Гасфилд Д. Строки, деревья и последовательности в алгоритмах./Пер. С английского И.В. Романовского. СПб.: Невский Диалект; БХВ-Петербург; 2003.

32. Левенштайн В.И. Двоичные коды с исправлением выпадений, вставок, изамещений символов-Доклады АН СССР. 1965. Т. 163.

33. Magic Quadrant for Master Data Management for Customer Data. 10 July 2008 John Radcliffe. Gartner RAS Core Research Note G00158340. http://mediaproducts.gartner.com/reprints/oracle/article28/article28.html

34. Sunday D.M. (1990) "A very fast substring search algorithm," Communications of the ACM, Vol. 33, No. 8, p. 132-42, August 1990.

35. Pirklbauer K. (1992) "A study of pattern-matching algorithms," Structured Programming, Vol. 13, p. 89-98, Springer Verlag New York.

36. Gonnet G.H., Baeza-Yates R. (1991) "Text algorithms," Chapter 7 (p. 251-88) of Handbook of Algorithms and Data Structures in Pascal and C, 2nd edition, Addison-Wesley, Wokingham UK.

37. Aho A.V. (1980) "Pattern matching in strings," in Book R.V. (ed.) Formal Language Theory, p. 325-47, Academic Press, New York.

38. Aho A.V. (1990) "Algorithms for finding patterns in strings," Chapter 5 (p. 255300) of Leeuwen J. van (ed.) Handbook of Theoretical Computer Science, Elsevier Science Publishers, Amsterdam.

39. Sedgewick R.(1983) "String searching," Chapter 19 (p. 241-55) of Algorithms, Addison-Wesley, Reading MA.

40. Horspool R.N. (1980) "Practical fast searching in strings," Software Practice and Experience, Vol. 10, No. 6, p. 501-6.

41. Smith T.F., Waterman M.S. (1981) "Identification of common molecular subsequences," Journal of Molecular Biology, Vol. 147, p. 195-7.

42. Baeza-Yates R.A. (1989a) "Improved string matching," Software Practice and Experience, Vol. 19, No. 3, p. 257-71, March 1989.

43. Davies G., Bowsher S. (1986) "Algorithms for pattern matching," Software -Practice and Experience, Vol. 16, No. 6, p. 575-601, June 1986.

44. Hume A., Sunday D.(1991) "Fast string searching," Software Practice and Experience, Vol. 21, No. 11, p. 1221-48, November 1991.

45. Knuth D.E., Morris J.H., Pratt V.R. (1977) "Fast pattern matching in strings," SIAM Journal on Computing, Vol. 6, No. 2, p. 323-50, June 1977.

46. Woude J. van der (1989) "Playing with patterns, searching for strings," Science of

47. Computer Programming, Vol. 12, No. 3, p. 177-90, Elsevier Science Publishers.

48. Menico C. (1989) "Faster string searches," Dr. Dobb's Journal, p. 74-5, July 1989.

49. Hamming R. (1982) "Coding and Information Theory," Prentice Hall, Englewood Cliffs NJ.

50. Sankofi D., Kruskall J.B. (eds.) (1983) "Time warps, string edits, and macromolecules: the theory and practice of sequence comparison," Addison-Wesley, Reading MA.

51. Wong C.K., Chandra A.K. (1976) "Bounds for the string editing problem," Journal of the ACM, Vol. 23, No. 1, p. 13-6, January 1976.

52. Aho A.V. Hirschberg D.S., Ullman J.D. (1976) "Bounds on the complexity of the longest common subsequence problem," Journal of the ACM, Vol. 23, No. 1, p. 1-12, January 1976.

53. Hirschberg D.S. (1978) "An information theoretic lower bound for the longest common subsequence problem," Information Processing Letters, Vol. 7, p. 40-1.

54. Lipman D.J., Pearson W.R. (1985) "Rapid and sensitive protein similarity searches," Science, Vol. 227, No. 4693, p. 1435-41, 22 March 1985.

55. Altschul S.F., Gish W„ Miller W., Myers E.W., Lipman D.J. (1990) "Basic local alignment search tool," Journal of Molecular Biology, Vol. 215, p. 403-10.

56. Lowrance R., Wagner R.A. (1975) "An extension of the string-to-string correction problem," Journal of the ACM, Vol. 22, No. 2, p. 177-83.

57. Maier D. (1978) "The complexity of some problems on subsequences and supersequences," Journal of the ACM, Vol. 25, No. 2, p. 322-36, April 1978.

58. Karp R.M. (1972) "Reducibility among combinatorial problems," in Miller R.E., Thatcher J.W. (eds.) Complexity of Computer Computations, p. 85-103, Plenum Press.

59. Baeza-Yates R.A. (1991) "Searching subsequences," Theoretical Computer Science, Vol. 78, No. 2, p. 363-76.

60. Jacobson G., Vo K-P. (1992) "Heaviest increasing/common subsequenceproblems," Proceedings of the Combinatorial Matching Conference, Tucson, Arizona, April 1992.

61. Vo K-P. (1986) "More <curses>: the <screen> library,» Technical Report, AT&T Bell Laboratories.

62. Landau G.M., Vishkin U., Nussinov R.(1985) "An efficient string matching algorithm with к differences for nucleotide and amino acid sequences," Technical Report TR-37/85, Department of Computer Science, Tel Aviv University.

63. Galil Z., Giancarlo R. (1988) "Data structures and algorithms for approximate string matching," Journal of Complexity, Vol. 4, p. 33-72.

64. Landau G.M., Vishkin U. (1985) "Efficient string matching in the presence of errors," Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science, p. 126-36.

65. Landau G.M., Vishkin U. (1986a) "Efficient string matching with к mismatches," Theoretical Computer Science, Vol. 43, p. 239-49.

66. Ivanov A.G. (1984) "Distinguishing an approximate word's inclusion on Turing machine in real time," Izv. Akademii Nauk SSSR Ser. Mat., Vol. 48, p. 520-68 (Russian).

67. Galil Z., Giancarlo R. (1986) "Improved string matching with к mismatches," SigactNews, Vol. 17, p. 52-4.

68. Sellers P.H. (1980) "The theory and computation of evolutionary distances: pattern recognition," Journal of Algorithms, Vol. 1, p. 359-73.

69. Ukkonen E. (1985b) "Finding approximate patterns in strings," Journal of Algorithms, Vol. 6, No. 6, p. 132-7.

70. Ukkonen E. (1983) "On approximate string matching," Proceedings of the International Conference on Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 158, p. 487-95, Springer-Verlag, Berlin.

71. Ukkonen E. (1985a) "Algorithms for approximate string matching," Information and Control, Vol. 64, p. 100-18.

72. Landau G.M., Vishkin U. (1988) "Fast string matching with к differences," Journal of Computer and System Sciences, Vol. 37, No. 1, p. 63-78.

73. Weiner P. (1973) "Linear pattern matching algorithm," Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, p. 1-11.

74. Harel D., Tarjan R.E. (1984) "Fast algorithms for finding nearest common ancestors," SIAM Journal on Computing, Vol. 13, No. 2, p. 338-55.

75. Schieber В., Vishkin U. (1988) "On finding lowest common ancestors: simplification and parallelization," SIAM Journal on Computing, Vol. 17, No. 6, p. 1253-62.

76. Landau G.M., Vishkin U. (1986b) "Introducing efficient parallelism into approximate string matching and a new serial algorithm," Proceedings of the 18th ACM Symposium on the Theory of Computing, p. 220-30.

77. Landau G.M., Vishkin U. (1989) "Fast parallel and serial approximate string matching," Journal of Algorithms, Vol. 10, p. 157-69.

78. Hollaar L.A. (1979) "Text retrieval computers," IEEE Computer, Vol. 12, p. 40-50.

79. Foster M.J., Kung H.T. (1980) "The design of special-purpose VLSI chips," IEEE Computer, Vol. 13, p. 26-40, January 1980.

80. Mukhopadhyay A.(1980) "Hardware algorithms for string processing," Proceedings oflCCC, p. 508-11.

81. Curry Т., Mukhopadhyay A.(1983) "Realization of eflcient non-numeric operations through VLSI," Proceedings of VLSI ^83.

82. Halaas A. (1983) "A systolic VLSI matrix for a family of fundamental search problem," Integration VLSI Journal, Vol. 1, No. 4, p. 269-82, December 1983.

83. Lee K.C., Мак V.W. (1989) "Design and analysis of a parallel VLSI string search algorithm," Lecture Notes in Computer Science, Vol. 368, p. 215-29.

84. Burkowski F.J. (1982) "A hardware hashing scheme in the design of a multiterm string comparator," IEEE Transactions on Computers, Vol. C-31, No. 9, p. 825-34, September 1982.

85. Lee D., Lochovsky F. (1985) "Text retrieval machine," Office Automation -Concepts and Tools, section 14, Springer-Verlag, New York.

86. Haskin R.L. (1981) "Special purpose processors for text retrieval," Database Engineering, Vol. 4, No. 1, p. 16-29, September 1981.

87. Robert D.C. (1982) "A specialized computer architecture for text retrieval," Proceedings of the 4th Workshop on Computer Architecture, p. 51 -9.

88. Haskin R.L., Hollaar L.A (1983) "Operational characteristics of a hardware-based pattern matcher," ACM Transactions on Database Systems, Vol. 8, No. 1, p. 15-40, March 1983.

89. Hall P.A.V., Dovvling G.R. (1980) "Approximate matching," Computing Surveys, Vol. 12, No. 4, p. 381-402, December 1980.

90. Salton G. (1980) "Automatic information retrieval," IEEE Computer, Vol. 13, p. 4155. September 1980.

91. Yianilos P.N. (1983) "A dedicated comparator matches symbol strings fast and intelligently," Electronics, Vol. 56, No. 5, p. 113-7, December 1983.

92. Yamada H., Hirata M., Nagai H., Takahashi K. (1987) "A high-speed string-search engine," IEEE Journal of Solid-State Circuits, Vol. SC-22, No. 5, p. 829-34, October 1987.

93. Hirata M., Yamada H., Nagai H., Takahashi K. (1988) "A versatile data string-search VLSI," IEEE Journal of Solid-State Circuits, Vol. 23, No. 2, p. 329-35, April 1988.

94. Polyakov V.N., Sinitsin V.V. "Rubryx: Technology of Text Classification Using Lexical Meaning Based Approach" in Proc. of International Conference Speech and Computer. SPECOM-2003. Moscow, MSLU, 137-143 (2003).

95. Vintsyuk Т.К. (1968) "Speech discrimination by dynamic programming," Cybernetics. Vol. 4, No. 1, p. 52-7, also (Russian) Kibemetika, Vol. 4, No. 1, p. 81-8.

96. Needleman S.B., Wunsch C.D. (1970) "A general method applicable to the search for similarities in the amino-acid sequence of two proteins," Journal of Molecular Biology, Vol. 48, p. 443-53.

97. Velichko V.M., Zagoruyko N.G. (1970) "Automatic recognition of 200 words," International Journal of Man-Machine Studies, Vol. 2, p. 223-34.

98. Sakoe H., Chiba S. (1970) "A similarity evaluation of speech patterns by dynamic programming," (Japanese) Institute of Electronic Communications Engineering of Japan, p. 136, July 1970.

99. Sakoe H., Chiba S. (1971) "A dynamic programming approach to continuous speech recognition," 1971 Proceedings of the International Congress of Acoustics, Budapest, Hungary, Paper 20 С 13.

100. Sankofi D. (1972) "Matching sequences under deletion-insertion constraints, " Proceedings of the National Academy of Sciences of the USA, Vol. 69, p. 4-6.

101. Reichert T.A., Cohen D.N., Wong A.K.C. (1973) "An application of information theory to genctic mutations and the matching of polypeptide sequences," Journal of Theoretical Biology, Vol. 42, p. 245-61.

102. Haton J.P. (1973) "Contribution a l'analyse, parametrisation et la reconnaissance automatique de la parole," These de doctorat d'etat, Universitfie de Nancy, Nancy France.

103. Wagner R.A., Fischer M.J. (1974) "The string-to-string correction problem," Journal of the ACM, Vol. 21, No. 1, p. 168-73, January 1974.

104. Hirschberg D.S. (1975) "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, Vol. 18, No. 6, p. 341-3, June 1975.

105. Hunt J.W., Mcllroy M.D. (1976) "An algorithm for differential file comparison." Computing Science Technical Report 41, AT&T Bell Laboratories, Murray Hill NJ.

106. Hunt J.W., Szymanski T.G. (1977) "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, No. 5, p. 350-3, May 1977.

107. Masek W.J., Paterson M.S. (1980) "A faster algorithm for computing string-edit distances," Journal of Computer and Systems Sciences, Vol. 20, No. 1. p. 18-31.

108. Myers E.W. (1986) "An 0(ND) difierence algorithm and its variations," Algorithmica, Vol. 1, p. 251-66.

109. Apostolico A., Guerra C. (1987) "The longest common subsequence problem revisited," Algorithmica, Vol. 2, p. 315-36.

110. Morrison D.R. (1968) "PATRICIA practical algorithm to retrieve information coded in alphanumeric," Journal of the ACM, Vol. 15, No. 4, p. 514-34.

111. Aho A.V., Hopcroft J.E., Ullman J.D. (1974) "The design and analysis of computer algorithms," Addison-Wesley, Reading, MA.

112. Majster M.E., Reiser A. (1980) "Efficient on-line construction and correction of position trees," SIAM Journal on Computing, Vol. 9, No. 4, p. 785-807, November 1980.

113. McCreight E.M. (1976) "A space-economical suffix tree construction algorithm," Journal of the ACM, Vol. 23, No. 2, p. 262-72, April 1976.

114. Rodeh M., Pratt V.R., Even S. (1981) "Linear algorithm for data compression via string matching," Journal of the ACM, Vol. 28, No. 1. p. 16-24, January 1981.

115. Crochemore M. (1986) "Transducers and repetitions," Theoretical Computer Science, Vol. 45, p. 63-86.

116. Blumer A., Blumer J., Ehrenfeucht A., Haussler D., McConnel R. (1984a) "Building a complete inverted file for a set of text files in linear time," Proceedings of the 16th ACM Symposium on the Theory of Computing, p. 349-58.

117. Blumer A., Blumer J., Ehrenfeucht A., Haussler D., Chen M.T., Seiferas J. (1985) "The smallest automaton recognizing the subwords of a word," Theoretical Computer Science. Vol. 40, No. l,p. 31 -56.

118. Blumer A., Blumer J., Haussler D., McConnel R., Ehrenfeucht A. (1987) "Complete inverted files for efficient text retrieval and analysis," Journal of the ACM, Vol. 34, No. 3, p. 578-95.

119. Apostolico A. (1985) "The myriad virtues of subword trees," in Apostolico A., Galil Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series, Vol. F12, p. 85-96, Springer-Verlag. Berlin.

120. Chen M.T., Seiferas J. (1985) "Eficient and elegant subword-tree construction," in Apostolico A., Galil Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series, Vol. F12, p. 97-107, Springer-Verlag, Berlin.

121. Ziv J., Lempel A. (1977) "A universal algorithm for sequential data compression," IEEE Transactions on Information Theory, Vol. IT-23, p. 337-43, May 1977.

122. Cook S.A. (1972) "Linear time simulation of deterministic two-way pushdown automata," Information Processing, Vol. 71, p. 75-80, North-Holland, Amsterdam.

123. Rivest R.L. (1977) "On the worst-case behaviour of string searching algorithms," SIAM Journal on Computing, Vol. 6, No. 4, p. 669-74.

124. Boyer R.S., Moore J.S. (1977) "A fast string searching algorithm," Communications of the ACM, Vol. 20, No. 10, p. 762-72, October 1977.

125. Galil Z. (1979) "On improving the worst case running time of the Boyer-Moore string searching algorithm," Communications of the ACM, Vol. 22, No. 9, p. 505-8.

126. Schaback R.(1988) "On the expected sublinearity of the Boyer-Moore algorithm," SIAM Journal on Computing, Vol. 17, No. 4, p. 648-58.

127. Smith P.D. (1991) "Experiments with a very fast substring search algorithm," Software Practice and Experience, Vol. 21, No. 10, p. 1065-74, October 1991.

128. Harrison M.C. (1971) "Implementation of the substring test by hashing," Communications of the ACM, Vol. 14, No. 12, p. 777-9, December 1971.

129. Karp R.M., Rabin M.O. (1987) "Efficient randomized pattern-matching algorithms," IBM Journal of Research and Development, Vol. 31, No. 2, p. 249-60, March 1987.

130. Что такое генетические алгоритмы Тимофей Струнков, PC Week RE, 19/99 http://www.neuroproiect.ru/gene.htm

131. Rudolph, G., "Convergence properties of canonical genetic algorithms," IEEE Trans, on Neural Networks, Vol. 5, N. I, 1994.

132. Grefenstette, J.J., "Optimization of control parameters for genetic algorithm"," IEEE Trans. Sys., Man and Cybem., Vol. 16, N. I, pp. 122-128, 1986.

133. Elben, A.E., Aarts, B;H., and Van Нее, K.M., "Global convergence of genetic algorithms: An Infinite Markov chain analysis," Parallel Problem Solving from Nature, H.-P. Schwefel and R. Manner, Eds. Heidelberg, Berlin: Springer-Verlag, pp. 4-12, 1991.

134. Fogel, D.B., "Asymptotic convergence properties of genetic algorithms and evolutionary programming: Analysis and experiments," Cybernetics and Systems, 1994.

135. Rudolph, G., "Convergence properties of canonical genetic algorithms," IEEE Trans, on Neural Networks, Vol. 5, N. I, 1994.

136. Holland, J.H., Adaptation in Natural and Artificial Systems.

137. Ann Arbor: Univ. of Michigan Press, 1975.

138. Xiaofeng Q., and Palmiet-i, F., "Theoretical analysis of evolutionary algorithms ijAlth an infinite population size in continuous space. Parts 1,11", IEEE Trans, on Neural Networks, Vol.5, No. 1, 102-130, 1994.

139. Ю.Н. Пронин, A.M. Перепёлкина, C.JI. Кожитов. О построении корпоративных ' информационных систем // Образование, наука и производство, Межвузовый сборник научных трудов. Т. II. Московский государственный институт стали сплавов 2001г. с. 134-137//

Похожие работы

Информатика, вычислительная техника и управление
05.13.00