ALGORITM OF RESTORATION OF THE DATA ON A FILD OF THE «BAD» DATA

Abstract

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.

Full Text

Для современной науки характерно непрерывное возрастание сложности изучаемых объектов. Одним из характерных свойств «сложных объектов» является то, что для описания используются переменные раз- личной физической природы. Например, при изучении причин миграции населения социолог вынужден учи- тывать большое число факторов, отражающих эконо- мические, географические, природно-климатические, культурно-бытовые условия и т. д. Часто при работе на «сложных объектах» приходится сталкиваться с ситуацией, когда отсутствуют те или данные. Причи- ны этого различны: ошибки, допущенные при сборе сведений; невозможность в силу каких-либо причин заполнить значения и т. д. При этом для анализа дан- ных требуется непрерывный набор значений. Пропу- щенные значения могут серьезно повлиять на резуль- таты анализа. Поэтому возникает задача наиболее точного заполнения пропусков. Алгоритмов решения данной задачи весьма мно- го - от самых простых до весьма сложных математи- ческих подходов [1-3]. Следует отметить, что при формировании модели «сложного объекта», как правило, возникают трудности, что объясняется сущест- венным недостатком знаний о его внутренних функ- циональных взаимосвязях. В настоящее время широкое распространение получили локальные алгоритмы заполнения пропуска на основе использования зависимостей, определенных на части данных в некоторой окрестности пропуска в отличие от других, основанных на предположении, что зависимость заданного (например, линейного) типа реализована на всех данных, поэтому и в опреде- лении зависимости участвуют все строки и столбцы исходного поля данных. Многолетний опыт использования локальных ал- горитмов показал их высокую эффективность по сравнению с другими известными алгоритмами за- полнения пробелов, редактирования таблиц и прогно- зирования характеристик динамических (меняющихся во времени или пространстве) объектов [1]. Вместе с тем, по мере накопления опыта решения реальных задач возникает необходимость модификации сущест- вующих локальных алгоритмов и разработки новых. В процессе исследований изучается влияние различных способов нормировки столбцов, сравниваются разные стратегии выбора компетентных подматриц и 1 æ n n ö image n b = ç å yi - aå xi ÷. различные способы заполнения пробелов по компе- è i =1 i =1 ø тентным подматрицам. Делается попытка создать ал- горитм заполнения пробелов в так называемых трех- входовых таблицах или кубах данных типа «обьект- свойство-время» [1]. Одним из основных локальных алгоритмов восста- новления пропусков данных является алгоритм ZET. Авторы предлагают модификацию данного алгоритма и приводят результаты сравнительного исследования предложенного модифицированного алгоритма на данных типа «обьекты-свойства-время». Работа предложенной модификации алгоритма ZET для восстановления пропуска на многомерных данных, описывающих «сложные объекты», основана на следующей гипотезе: если восстанавливаемое из- мерение попадает в один таксон с другими измере- ниями и за счет анализа избыточной информации данный таксон не меняется, то между восстанавли- ваемым (оцениваемым) измерением и другими измере- ниями есть линейная зависимость. Основные этапы предложенного алгоритма: Разбиваем многомерные данные на двухмерные так, чтобы между ними была зависимость. Определяем таксоны на двухмерных данных. Определяем устойчивый таксон на основе пред- ложенной эмпирической гипотезы: в среднем объекты (данные) с большей вероятностью появления в иссле- дуемом таксоне в разные исследуемые интервалы несут большее количество информации. Определяем, к какому таксону принадлежит элемент, стоящий на месте пропуска, на основе анали- за других факторов. Пропуск будем относить к тому таксону, к которому относятся элементы, попавшие в устойчивый таксон в восстанавливаемом факторе (см. рисунок, где пунктирной линией отмечена при- надлежность пропуска к таксону, которому принадле- жат выделенные измерения). Проводим восстановление пропуска с помощью линейной регрессии yi(x) = b + a × x по значениям, по- павшим в устойчивый таксон по другому фактору: n n n å xi å yi - nå xi yi а = i =1 i =1 i =1 ; 2 æ n ö n ç å i ÷ å i Определяем степень влияния одного признака (фактора) на другой (k) на основе построенного нечет- кого графа иерархии с корневыми вершинами на рас- сматриваемом поле данных [4]. Восстанавливаем пропуск на основе учета сте- пени влияния каждого признака (фактора), попавшего в устойчивый таксон: y(x) = k1y1(x) + k2y2(x) + … + kiyi(x). Апробацию предложенной модификации проведем на данных типа «обьекты-свойства-время» по пред- приятиям РАО ЕЭС России. Исследуемые данные бы- ли представлены в трехмерном пространстве по сле- дующим осям: объекты (предприятия), исследуемые признаки (факторы) и ось времени. Объем выборки составил порядка - 700 измерений. Следует отметить, что по оси «факторы» измерения имеют разную физи- ческую природу. На исходном поле данных было сделано 15 % про- пусков на основе нормального закона распределения с использованием датчика случайных чисел (табл. 1). На полученном поле данных проведено восстанов- ление пропусков на основе алгоритма ZET и предло- женной модификации (табл. 2). Предложенная модификация алгоритма ZET при использовании его на данных типа «обьект-свойство- время» дает хорошие результаты: так, из 16 пропусков удалось восстановить 12 значений с ошибкой менее 15 %. Следует отметить, что у двух значений не уда- лось определить принадлежность к таксону. С помо- щью алгоритма ZET удалось восстановить только 3 значения из 16 пропусков с ошибкой менее 15 %. Таким образом, предложенная модификация алгорит- ма показала большую эффективность по сравнению базовым при применении на многомерных данных. Также предложенная модификация алгоритма ZET позволила расширить работу базового алгоритма на многомерные данные и устранить такие недостатки, как попадание в компетентную матрицу неинформа- тивных строк, и, как следствие, неинформативных столбцов, фиксированность размера компетентной матрицы. Оценивать эффективность предложенной модифи- кации алгоритма по сравнению с базовым будем на основе проведения численных экспериментов на x è i =1 ø n x2 i =1 сформированном ранее поле данных с пропусками. image Определение отношения пропуска к таксону Сформированное поле данных с пробелами Таблица 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 Ошибка алгоритма ZET, % Восстановленное значение, модифицированный алго- ритм ZET Ошибка восстановления, модифицированный алго- ритм ZET, % 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 Отличие данного подхода от метода «скользящего vt = arg(min( Dv )). vÎt экзамена» заключается в следующем. В методе «скользящего экзамена» сначала закрывается один известный элемент b11, стоящий на пересечении стро- На практике удобнее ошибку предсказания эле- мента считать в процентах: ки a1 и столбца x1, и происходит его предсказывание с помощью всех исследуемых алгоритмов F поочеред- но. Каждый алгоритм fv предскажет свое значение b11v, eijv bijv - bij image = . bij которое будет отличаться от исходного («истинного») значения на величину d11v = |b11v - b11|. Далее восстанавливаем в таблице элемент b11, убе- рем элемент b12 и повторим процедуру. Получим от- клонение d12v. Проделав это по очереди со всеми эле- ментами таблицы, и просуммировав полученные от- клонения, мы получим суммарную величину отклоне- ний Dv для каждого алгоритма v. Наилучшим из них Тогда ошибку предсказывания таблицы размера N ´ M можно вычислять по формуле å eijv , 1£i £ N E = 1£jM . v N × M В предлагаемом подходе закрываются сразу все неизвестные элементы в таблице и происходит их вос- становление на основе исследуемых алгоритмов, по- естественно считать такой алгоритм минимальную сумму отклонений: v f t , который дает сле чего считается ошибка предсказывания по таблице так же, как и в методе «скользящего экзамена». Затем генерируются новые пропуски, и процесс восстанов- ления повторяется. По итогу получается интегральная ошибка восстановления на основе нескольких повто- рений, которая также позволяет судить об устойчиво- сти исследуемых алгоритмов и отражает более дейст- вительно поведение алгоритмов в реальных условиях пропуска. Полученные интегральные характеристики восста- новления пропусков на основе 5 повторений приведе- ны в табл. 3. На основе анализа проведенного эксперимента можно сделать вывод, что предложенная модифика- ция алгоритма дает значительно лучшие результаты восстановления, чем немодифицированный при ис- пользовании избыточной информации многомерных данных. Применять предложенную модификацию следует на данных, в которых нет выраженной зако- номерности между значением элементов в строках или в столбцах, и измерения являются более разроз- ненными без явных тенденций и группировок по строкам (столбцам), что характерно показывает при- менение данных алгоритмов на данном поле данных для восстановления по фактору «технологические на- рушения» (табл. 4). Из проведенных численных экспериментов следу- ет, что ошибка предсказания в алгоритме ZET зависит от «похожести» столбцов и строк, по которым проис- ходит предсказывание, на строку и столбец, в котором есть пропуск, в то время как ошибка предложенной модификации зависит от того, насколько разные зна- чения элементов попали в устойчивый таксон; и чем более разрозненным является исходное поле данных, тем худшие результаты показывает базовый алгоритм и лучшие - модифицированный. Следует отметить, что чем строже мы указываем критерии для выделе- ния таксона на исходном поле данных, тем точность предсказывания выше с одновременным увеличением доли невосстановленных значений за счет невозмож- ности определить устойчивый таксон. На двухмерном поле данных, отвечающем требо- ваниям данных алгоритмов, ошибка восстановления подтверждает ранее сделанные предположения о том, что если в строках (столбцах) есть выраженные зави- симости, то данные алгоритмы показывают хороший результат (табл. 5); и наоборот, при разрозненных данных в столбцах (строках) исходные алгоритмы показываю значительно хуже результаты [5]. Практическое применение локальных алгоритмов, как уже отмечалось в работах Н. Г. Загоруйко, весьма широко - от техники до медицины и финансов. Пред- ложенная модификация локального алгоритма восста- новления пропусков ZET позволит расширить приме- нение данного класса алгоритмов на многомерные массивы данных, описывающих «сложные объекты». Библиографический список Загоруйко, Н. Г. Прикладные методы анализа данных и знаний / Н. Г. Загоруйко. Новосибирск : Изд. ин-та математики, 1999. Лбов, Г. С. Методы обработки разнотипных экс- периментальных данных / Г. С. Лбов. М., 1981. Калинин, А. В. Методы восстановления пропус- ка данных / А. В. Калинин, С. В. Ченцов // Информа- тика и системы управления. 2002. № 8. Калинин, А. В. Анализ аномалий на поле данных для выявления внутренних взаимосвязей / А. В. Кали- нин, С. В. Ченцов // САКС 2004 : сб. тез. докл. Крас- ноярск, 2004. Раскулов, С. Н. Разработка и исследование новых версий алгоритма ZET заполнения пробелов в эмпирических таблицах [Электронный ресурс] / С. Н. Раскулов ; Новосиб. гос. ун-т. Электрон. дан. Режим доступа: http:// zetbraid.narod.ru. Загл. с экрана. Интегральные ошибки предсказания алгоритмом ZET и предложенной модификации на данных типа «обьекты-свойства-время» по фактору «травматизм» Таблица 3 Базовый алгоритм ZET, % Модифицированный алгоритм ZET, % 49,5 9,85 (21,8 % пропусков не удалось восстановить) Таблица 4 Интегральные ошибки предсказания алгоритмом ZET и предложенной модификации на данных типа «обьекты-свойства-время» по фактору «технологические нарушения» Ошибка восстановления алгоритма ZET, % Ошибка восстановления модифицированным алгоритмом ZET, % 23,9 12,04 (50 % пропусков не удалось восстановить) Интегральные ошибки предсказания алгоритма ZET, ZETBraid Таблица 5 Поле данных Алгоритм ZET, % Алгоритм ZetBraid, % «Биоинформатика» (24 строки, 142 столбца) - таблица исследований психо- физических показателей различных групп людей, полученная в результате исследования уровня тревожности 18,9 15,4 «Минэнерго» (31 строка, 14 столбцов) - таблица данных министерства энер- гетики США с 1970 по 2000 г. 2,6 2,2