Алгоритм восстановления пропусков на поле «Плохих» данных

цикла программной системы требуется грубая (предварительная) оценка, которая может иметь точность до ±200 % [2], а в конце этапа анализа требований оценка требуется более точная, поскольку на ее основе рассчитывается бюджет проекта и сумма контракта. В предложенной методике уровень точности оценки зависит от детализации функциональных блоков, которые могут иметь статус от элементарных блоков системы до компонент и подсистем, что существенно упрощает использование методики.

В развитии предложенной методики планируются следующие исследования:

1) получение параметров модели (оценки сложности (Si у ) и значимости (весов) проектов (рк)), на

основе статистических данных исходных проектов;

2) разработка методов оценки степени достоверности данных исходных проектов;

3) идентификация и классификация функциональных блоков программных систем;

4) идентификация параметров, влияющих на стоимость программного проекта и на их основе уточнение модели и методики.

Библиографический список

1. Михайловский, Н. Сравнение методов оценки стоимости проектов по разработке информационных систем [Электронный ресурс] / Н. Михайловский. Электрон. дан. Режим доступа: http://www.pmproiy.ru/content/rus/79/797-article.asp. Загл. с экрана.

2. Макконнелл, С. Остаться в живых. Руководство для менеджера программных проектов / С. Маккон-нелл. СПб. : Питер, 2006. 240 с. (Библиотека программиста).

Yu. Yu. Yakunin

ESTIMATION OF LABOUR PRODUCTIVITY OF DEVELOPMENT OF PROGRAM SYSTEM

The technique and mathematical model of an estimation of labour productivity of the program project on the basis of the metrics based on functional points are described.

УДК 621.314

А. В. Калинин, С. В. Ченцов АЛГОРИТМ ВОССТАНОВЛЕНИЯ ПРОПУСКОВ НА ПОЛЕ «ПЛОХИХ» ДАННЫХ

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

Ключевые слова: восстановление пропусков, многомерные данные 2БТ алгоритм.

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

Алгоритмов решения данной задачи весьма много - от самых простых до весьма сложных математических подходов [1-3]. Следует отметить, что при формировании модели «сложного объекта», как пра-

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

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

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

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

Одним из основных локальных алгоритмов восстановления пропусков данных является алгоритм 2БТ. Авторы предлагают модификацию данного алгоритма и приводят результаты сравнительного исследования предложенного модифицированного алгоритма на данных типа «обьекты-свойства-время».

Работа предложенной модификации алгоритма 2БТ для восстановления пропуска на многомерных данных, описывающих «сложные объекты», основана на следующей гипотезе: если восстанавливаемое измерение попадает в один таксон с другими измерениями и за счет анализа избыточной информации данный таксон не меняется, то между восстанавливаемым (оцениваемым) измерением и другими измерениями есть линейная зависимость.

Основные этапы предложенного алгоритма:

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

2. Определяем таксоны на двухмерных данных.

3. Определяем устойчивый таксон на основе предложенной эмпирической гипотезы: в среднем объекты (данные) с большей вероятностью появления в исследуемом таксоне в разные исследуемые интервалы несут большее количество информации.

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

5. Проводим восстановление пропуска с помощью линейной регрессии у,(х) = Ь + а  х по значениям, попавшим в устойчивый таксон по другому фактору:

п п п

X х- X у<- пХ хУ

6. Определяем степень влияния одного признака (фактора) на другой (к) на основе построенного нечеткого графа иерархии с корневыми вершинами на рассматриваемом поле данных [4].

7. Восстанавливаем пропуск на основе учета степени влияния каждого признака (фактора), попавшего в устойчивый таксон: у(х) = к1у1(х) + к2у2(х) + ... + ку-(х).

Апробацию предложенной модификации проведем на данных типа «обьекты-свойства-время» по предприятиям РАО ЕЭС России. Исследуемые данные были представлены в трехмерном пространстве по следующим осям: объекты (предприятия), исследуемые признаки (факторы) и ось времени. Объем выборки составил порядка - 700 измерений. Следует отметить, что по оси «факторы» измерения имеют разную физическую природу.

На исходном поле данных было сделано 15 % пропусков на основе нормального закона распределения с использованием датчика случайных чисел (табл. 1).

На полученном поле данных проведено восстановление пропусков на основе алгоритма 2БТ и предложенной модификации (табл. 2).

Предложенная модификация алгоритма 2БТ при использовании его на данных типа «обьект-свойство-время» дает хорошие результаты: так, из 16 пропусков удалось восстановить 12 значений с ошибкой менее 15 %. Следует отметить, что у двух значений не удалось определить принадлежность к таксону. С помощью алгоритма 2БТ удалось восстановить только 3 значения из 16 пропусков с ошибкой менее 15 %. Таким образом, предложенная модификация алгоритма показала большую эффективность по сравнению базовым при применении на многомерных данных.

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

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

1 фактор

3 фактор

и пропуска к таксону

4 фжгор

Таблица 1

Сформированное поле данных с пробелами

Общий травматизм 1993 1994 1995 1996 1997 1998 1999

Алтайэнерго 21 14 19 21 21 16 20

Бурятэнерго 24 21 19 14 16 15 14

Красноярскэнерго 46 34 31 26 37 25 17

Кузбассэнерго 30 43 68 44 31 43 31

Иркутскэнерго 42 58 52 52 53 53 46

Новосибирскэнерго 24 21 30 17 35 25 8

Омскэнерго 24 16 23 19 11 14 25

Томскэнерго 9 8 5 7 3 3 5

Хакасэнерго 2 9 8 3 6 3 3

Читаэнерго 9 11 10 5 3 7 3

Саяно-Шушенская ГЭС 6 8 4 5 0 2 2

Березовская ГРЭС-1 3 4 10 8 9 6 3

Гусиноозерская ГРЭС 4 7 3 1 3 6 3

Красноярская ГРЭС-2 3 3 5 3 5 2 3

Бийская ТЭЦ-1 4 7 10 10 2 9 14

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

Таблица 2

Сравнительные результаты заполнения пробелов

Восстанавливаемое значение Восстановленное значение алгоритм ZET Ошибка алгоритма 7БТ, % Восстановленное значение, модифицированный алгоритм 7БТ Ошибка восстановления, модифицированный алгоритм 7БТ, %

3 2,37 20,9 2,89 3,7

10 13,85 38,5 10 0

8 5,14 35,7 9,12 13,99

43 46,24 7,53 43,26 0,6

21 27,98 33,21 21,67 3,6

9 8,51 5,4 9 0

24 15,75 34 нет 100

6 9,71 52,84 нет 100

17 34,59 103,5 62,33 233

7 3,55 49,31 7,75 10,82

6 3,42 42,9 6 0

9 6,37 29,2 4,23 52,95

3 7,01 133 3,16 5,57

6 9,69 61,5 6,54 8,97

6 3,89 35,2 6 0

25 11,26 54,95 25 0

Отличие данного подхода от метода «скользящего экзамена» заключается в следующем. В методе «скользящего экзамена» сначала закрывается один известный элемент Ъ1Ь стоящий на пересечении строки а1 и столбца х1, и происходит его предсказывание с помощью всех исследуемых алгоритмов Е поочередно. Каждый алгоритм/у предскажет свое значение Ъ11у, которое будет отличаться от исходного («истинного») значения на величину = |Ъ11у - Ъп|.

Далее восстанавливаем в таблице элемент Ъ11, уберем элемент Ъ12 и повторим процедуру. Получим отклонение ^2у. Проделав это по очереди со всеми элементами таблицы, и просуммировав полученные отклонения, мы получим суммарную величину отклонений Бу для каждого алгоритма V. Наилучшим из них естественно считать такой алгоритм /V, который дает минимальную сумму отклонений:

v = arg(min( D )).

vît

На практике удобнее ошибку предсказания эле-

мента считать в процентах:

bv - ь

Ъ\

Тогда ошибку предсказывания таблицы размера N х М можно вычислять по формуле

E =

Z *

1<i £ N 1< jM

N M

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

е.. =

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

Полученные интегральные характеристики восстановления пропусков на основе 5 повторений приведены в табл. 3.

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

Из проведенных численных экспериментов следует, что ошибка предсказания в алгоритме 2БТ зависит от «похожести» столбцов и строк, по которым происходит предсказывание, на строку и столбец, в котором есть пропуск, в то время как ошибка предложенной модификации зависит от того, насколько разные значения элементов попали в устойчивый таксон; и чем более разрозненным является исходное поле данных, тем худшие результаты показывает базовый алгоритм и лучшие - модифицированный. Следует отметить, что чем строже мы указываем критерии для выделения таксона на исходном поле данных, тем точность предсказывания выше с одновременным увеличением

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

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

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

Библиографический список

1. Загоруйко, Н. Г. Прикладные методы анализа данных и знаний / Н. Г. Загоруйко. Новосибирск : Изд. ин-та математики, 1999.

2. Лбов, Г. С. Методы обработки разнотипных экспериментальных данных / Г. С. Лбов. М., 1981.

3. Калинин, А. В. Методы восстановления пропуска данных / А. В. Калинин, С. В. Ченцов // Информатика и системы управления. 2002. № 8.

4. Калинин, А. В. Анализ аномалий на поле данных для выявления внутренних взаимосвязей / А. В. Калинин, С. В. Ченцов // САКС 2004 : сб. тез. докл. Красноярск, 2004.

6. Раскулов, С. Н. Разработка и исследование новых версий алгоритма 2БТ заполнения пробелов в эмпирических таблицах [Электронный ресурс] / С. Н. Раскулов ; Новосиб. гос. ун-т. Электрон. дан. Режим доступа: Шр:// zetbraid.narod.ru. Загл. с экрана.

Таблица 3

Интегральные ошибки предсказания алгоритмом ZET и предложенной модификации на данных типа «обьекты-свойства-время» по фактору «травматизм»

Базовый алгоритм 7БТ, % Модифицированный алгоритм 7БТ, %

49,5 9,85

Таблица 4

Интегральные ошибки предсказания алгоритмом 2ЕТ и предложенной модификации на данных типа «обьекты-свойства-время» по фактору «технологические нарушения»

Ошибка восстановления алгоритма 7БТ, % Ошибка восстановления модифицированным алгоритмом 7БТ, %

23,9 12,04

Таблица 5

Интегральные ошибки предсказания алгоритма 2ЕТ, 2ЕТБга1и

Поле данных Алгоритм 7БТ, % Алгоритм ZetBraid, %

«Биоинформатика» (24 строки, 142 столбца) - таблица исследований психофизических показателей различных групп людей, полученная в результате исследования уровня тревожности 18,9 15,4

«Минэнерго» (31 строка, 14 столбцов) - таблица данных министерства энергетики США с 1970 по 2000 г. 2,6 2,2

A. V. Kalinin, S. V. Chentsov ALGORITM OF RESTORATION OF THE DATA ON A FILD OF THE «BAD» DATA

The updating algorithm ZET of the data restoration on the basis of the informative field and data multiregularities analysis is considered. It is given the results of the comparative analysis of data restoration on the basis of the updating algorithm ZET.

Keywords: restoration of the data, multiregularities of the data, algorithm ZET.

УДК 004.4'242

П. А. Корягин

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

С ВЕБ-ИНТЕРФЕЙСОМ

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

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

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

Уже на этапе проектирования ИС возникают проблемы нечеткого оформления технического описания со стороны заказчика. Проблема усугубляется сроком их разработки (как правило, от 0,5 до 1,5 лет), в течение которого изменяются первоначальные идеи и претензии потребителей ИС. Возникает противоречие -осознание смены потребительских качеств будущей ИС порой опережает сроки их создания. В этой связи, с одной стороны, труд разработчика-программиста требует интенсификации, с другой - необходимо изменить концептуальные основы проектирования ИС.

Наиболее полное удовлетворение потребностей заказчика ИС может обеспечить проективный подход [2]. К сожалению, популярные сегодня методы разработки показывают плохие результаты, при частом пересмотре требований к системе (Карл И. Вигерс. Разработка требований к программному обеспечению).

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

Были поставлены следующие задачи:

1. Определить основные компоненты среды разработки ИС с Веб-интерфейсом и разработать проективный подход к их разработке на основе смешанных парадигм программирования.

2. Осуществить оценку эффективности предложенного метода на примере разработки конкретных проективных систем.

Исследование среды. Проведен анализ 30 проектов, выставленных на электронной бирже weblanc-er.net в категории Web-программирование. В результате обнаружено, что в 7 из них имеется техническое задание, в котором сформулированы следующие требования:

1) какие данные должны храниться в системе;

2) каким образом данные должны попадать в систему и выводиться ею.

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

Пример описания, потребителя, приведен на рис. 1.

Опытный программист может сформировать представление о модели данных по описанию, сделанному со слов потребителя (рис. 1). Он может привести ее в нормальную форму и описать базу данных на языке SQL или построить UML-диаграмму в CASE-системе.

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

- непосредственная генерация базы данных;

- описание полей формы ввода;

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

- подготовка значения к выводу в HTML;

- подготовка значения к вводу в базу данных;

- инициализация значений «по умолчанию».

В то же время известно, что в большинстве случаев как в пределах одного проекта, так и в разных проектах, к переменной поля заданного типа (например, «Текст с форматированием в формате HTML») будут применены идентичные алгоритмы.