УДК 550.832:681.5.03

Пельмегов Р. В., Куделин А. Г.
Применение теории подобия для оценки качества одномерных данных

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

Heuristic algorithm for assessing the quality of data with unknown distribution law

Р. В. Пельмегов, А. Г. Куделин

R. V. Pel’megov, A. G. Kudelin

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

Ukhta State Technical University,
Ukhta

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

Work is devoted to the development of scientific fundamentals, methods and technologies of automated quality control of regular digital signal. The design of the heuristic algorithm for solving the problem of quality control data using the methods of recovering data gaps. Considered in detail the mathematical apparatus and a geometric interpretation of the iterative methods for modeling incomplete data using linear, quasilinear and self-organizing low-dimensional manifolds used in the author’s implementation of the algorithm.

Ключевые слова: контроль качества, итерационное моделирование, автоматизация.

Keywords: quality control, iterative modeling, automation.

Введение

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

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

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

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

Известен парадокс Джонсона о том, что по мере накопления опыта процесс принятия решения экспертом все больше начинает носить неосознаваемый характер. Эксперт не всегда способен оценить важность тех или иных знаний для принятия решения, а накопленный опыт, сложно вербализовать и представить в формализованном виде. В статье «A Hierarchical Approach to Improving Data Quality» [1] присутствует во многом схожая проблематика и постановка. Предлагаемый авторами [1] подход к контролю качества геоинформационных данных основан на сопоставлении изображений одной местности, полученных из разных источников. Критерием качества считается величины взаимных уклонений пар матриц смежности графов, представляющих наборы данных. Подбор и сопоставление изображений выполняется экспертами вручную, являясь при этом актом формализации их опыта, поскольку основная проблема инженерии знаний – это процесс извлечения знаний. В работе [2] для проверки качества материалов геофизических исследований скважин авторы применяют способ многоскважинного статистического контроля, основанный на предположении о постоянстве распределения какого-либо геофизического параметра по площади для достаточно выдержанной мощной толщи пластов [3]. При наличии этого условия, очевидно, что распределение должно быть схожим в разных скважинах.

Алгоритм решения задачи

Основная идея предлагаемого метода базируется на представлении о том, что информационный сигнал формирует дискретное изображение информационного объекта. В случае исследования схожих объектов даже существенно отличающиеся по амплитуде и уровню шумов изображения, имеют и сходное содержание. Сравнивая тестируемое изображение с подобранными по содержанию изображениями из имеющейся базы эталонов, являющейся аккумулятором опыта эксперта, можно судить о качестве изучаемого материала. Для определения подобия сигналов обычно применяется некоторая мера расстояния, с помощью которой можно получить численную оценку их сходства. Два сигнала также могут называться подобными, если возможно такое преобразование определяющих параметров, после которых сигналы «выглядят» одинаковыми. Понятие меры сходства широко используется в теории подобия [4, 5, 6], более того, эта задача является одной из основных.

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

1. Нормирование сигналов по ограничиваемой их кривыми площади;

2. Нахождение градиентов нормированных кривых;

3. Вычисление интеграла модуля разности градиентов.

Для снятия ограничения на протяжённость исследуемых объектов предлагается использовать метод локального усреднения показателя, т. н. метод скользящего окна. Критерий подобия рассчитывается в пределах окна, полученное значение присваивается средней точке. Затем в заданном направлении окно перемещается на одну точку, и операция повторяется. Размер окна зависит от характера распределения и обычно включает от 10 до 50 ближайших точек. Результат подбора участков по разработанному алгоритму представлен на рисунке (рис. 1).

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

  • заполнение пробелов в данных;
  • ремонт данных, корректировка значений исходных данных так, чтобы наилучшим образом работали построенные модели.


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

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

1. Нормирование подобранных на предыдущем этапе кривых по мощности;

2. Удаление участка тестируемой кривой, качество которого подвергается сомнению;

3. Формирование из кривых матрицы (поверхности) с пробелами;

4. Восстановление участка по имеющимся избыточным данным;

5. Вычисление интеграла квадрата разности исходной и восстановленной кривой.

Оценка отклонения предстанет числом прямо пропорциональным величине неуверенности системы в качестве данного участка (рис. 2).

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


Рисунок 2. Кривая сомнения – q участка данных – d, искажённого неизвестной помехой

Методы итерационного моделирования неполных данных с помощью многообразий малой размерности

Рассматриваются две версии метода [8]: линейный – с моделированием данных последовательностью линейных многообразий малой размерности; существенно нелинейный – основанный на построении «главных кривых» с использованием вариационного принципа.

Столбец матрицы A есть вектор a с k пробелами, который представляется как k-мерное линейное многообразие La, параллельное k координатным осям, которые соответствуют удалённым данным.
При наличии априорных ограничений на пропущенные значения место La занимает прямоугольный параллелепипед P
⊂ La. Построим моделирующее эти данные линейное многообразие малой размерности следующим образом: за основу возьмём прямую f(x= xy+b, которая задаётся направляющим вектором y и проходит через точку, определяемую вектором b. Причём, задавая ограничения на значения свободного члена b, мы можем требовать, чтобы прямая проходила или не проходила через начало координат. Далее, расположим эту прямую так, чтобы она наилучшим (в некотором точном смысле) образом приближала исходные данные. Если взять в качестве проектора данных на эту прямую ортогональный проектор, то исходный вектор данных a ортогонально проецируется таким образом в вектор = Prf (a) на полученной прямой. Для исходных данных можно посчитать их уклонения от линейной модели, которые находятся из разницы между исходными данными и их проекциями на полученную прямую. Для множества уклонений снова строится простая модель и т. д., пока все уклонения не станут достаточно близки к нулю.

Пусть задана прямоугольная матрица = (aij), клетки которой заполнены действительными числами или значком @, означающим отсутствие данных.
Требуется представить исходную матрицу A в виде суммы одноранговых матриц

Pq: ,

где каждая Pq имеет вид xiyj + bj. Следовательно, ставится задача поиска наилучшего приближения A матрицей вида xiyj + bметодом наименьших квадратов:

        (1)

Решая эту задачу последовательными итерациями по явным формулам, мы получим линию, на которую не накладывается ограничение обязательного прохождения через начало координат. При фиксированных векторах yj и bj значения xi, доставляющие минимум форме (1), однозначно и просто определяются из равенств ∂Φ/∂xi=0:

        (2)

        (3)

Аналогично и при фиксированном векторе xi значения yj и bj, доставляющие минимум форме (1), определяются явно из двух равенств ∂Φ/∂yj = 0 и ∂Φ/∂bj = 0:

        (4)

        (5)

Представляя полученные значения в виде системы, получим:

        (6)

Решение полученной системы может быть найдено при помощи метода Крамера или метода квадратного корня [9]. Поскольку процедура является итерационной, то в качестве начального приближения вектора y возьмём случайное значение, но нормированное на 1, а в качестве b возьмём средние значения в соответствующих столбцах исходной матрицы A: y – случайный, нормирован на 1 (т. е. ).

        (7)

Задаваясь практически произвольными начальными приближениями для yи bj, ищем значение xi, далее объявляем неизвестными yj и bj, находим их значения при фиксированном xi и т. д. Эти простые итерации сходятся, так как на каждой итерации происходит уменьшение функционала (1). Решая задачу (1), для данной матрицы A находим наилучшее приближение матрицей P1 вида xiy+ bj. Далее, из матрицы A вычитаем полученную матрицу P1, и для полученной матрицы уклонений AP1 вновь ищем наилучшее приближение P2 этого же вида и т. д. Контроль ведётся, по остаточной дисперсии столбцов.

В результате исходная матрица данных A представляется в виде суммы матриц Pq, т. е. A=P1+P2+…+Pq. Если пробелы отсутствуют, т. е. все значения aij известны, то описанный метод приводит к методу главных компонент-сингулярному разложению центрированной исходной таблицы данных. В этом случае, начиная с q = 2, (= 0). В общем случае это не так. Следует обратить особое внимание на то, что центрирование к данным с пробелами неприменимо.

С использованием Q полученных факторов можно решать задачи заполнения пропусков в таблице и ремонта искажённых значений:

Q-факторное заполнение пропусков: пропущенные значения в исходной матрице A определяются из суммы Q полученных матриц вида xiyj + bj;

Q-факторный «ремонт» таблицы: значения в исходной матрице заменяются на сумму Q полученных матриц вида xiyj + bj.

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

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

Самоорганизующиеся карты Кохонена (Self-Organizingmap – SOM) [10] – это модификация алгоритма линейного векторного квантования данных, т. е. представления N точек данных меньшим числом точек-ядер. Каждое из ядер заменяет локальное сгущение данных (таксон).

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

Пусть SOM определяется набором точек (ядер) Y = {yij} (i,j = 1…m), будем считать, что сетка квадратная, но для прямоугольной все описанные формулы аналогичны), последовательно расположенных на квадратной сетке и требуется отобразить на ней набор точек данных . Введём преобразование П, которое каждому вектору xϵX сопоставляет ближайшую к нему точку из Y:

        (8)

каждому ядру yij сопоставляется его таксон:

        (9)

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

        (10)

        (11)

    ;    (12)

Таким образом, для построения SOM требуется минимизировать функционал:

        (13)

где    λ, μ – параметры связности и нелинейности – «модули упругости» (деление на число точек |X| и число ядер m означает нормировку «на одно слагаемое» и позволяет для выборок разной мощности использовать одинаковые способы изменения λ и μ).

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

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

2. При заданных положениях узлов сетки производится разбиение множества точек данных на таксоны – подмножества Kij.

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

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

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

        (14)

Где:

    

    

    

    

    

    

    

    

    

где    nkl – число элементов в таксоне Kkl,,
dij – символ Кронекера, множители вида (1 – dij) введены для того, чтобы учесть «краевые эффекты».

Если индексы k, l при ykl не соответствуют никакому узлу сетки, то этот множитель автоматически обратит это слагаемое в ноль. Уравнения , k=1…p, l=1…q дают m систем линейных уравнений (по одной на каждую из m компонент векторов ykl). «Вытянем» набор ядер ykl в один столбец. В результате вектор неизвестных будет:

    

Система имеет вид Ax=b, где s-ая компонента вектора свободных членов равна:

    , , ,

где […] – операция взятия целой части числа.

    , где     

Влияние качества экспертной выборки на результат оценки

Материалы базы эталонов являются главным элементом предложенной системы оценки качества данных – неявным аккумулятором опыта и знаний эксперта. От полноты и актуальности базы напрямую зависит качество оценок достоверности данных или «квалификация» системы. Рассмотрим примеры оценок получаемых при использовании различных экспертных выборок при других равных параметрах алгоритма. Пусть имеется некоторый набор данных содержащий неочевидные зависимости и помехи (рис. 3). Требуется оценить его качество по данным двух разных экспертных выборок.


Рисунок 3. Исследуемый набор данных – d

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


Рисунок 4. Кривая сомнения – q, набор данных – d

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


Рисунок 5. Кривая сомнения – q, набор данных – d

Практическое применение алгоритма

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

Для анализа каротажных данных автором был разработан программно-вычислительный комплекс «Комплекс инструментов для автоматизированного контроля качества данных ГИС» (свидетельство о государственной регистрации программы для ЭВМ № 2014611497), использующий представленную эвристическую технологию. Результаты вычислительных экспериментов позволяют утверждать о применимости и конкурентоспособности предлагаемого метода. При наличии слабых гармонических помех в наблюдениях он, по-видимому, является наиболее предпочтительным. Реализация подобного подхода к решению задачи автоматизированного контроля качества записи данных способна в значительной мере снизить вероятность получения недостоверных результатов ГИС. Дальнейшее развитие предложенного решения с включением моделей сред в качестве контролируемых данных позволит строить новые интерпретационные схемы в скважинной геофизике.

Заключение

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

Список литературы

1. Marcey L. Abate, Kathleen V. Diegert, Heather W. Allen A Hierarchical Approach to Improving Data Quality // Data Quality Journal. 1998. Vol. 4. No. 1.

2. Ботвиновская О. А., Ганичев Д. И., Хамитов И. Г., Хасанова Р. Г. Многоскважинные технологии интерпретации данных ГИС в ОАО «НК «Роснефть». URL:http://prime.geotec.ru/ROSNEFT.doc (дата обращения: 4.04.2014).

3. Губерман Ш. А., Овчинникова М. И. Некоторые возможности использования статистических характеристик геологических разрезов // Изв. АН СССР. Сер. Геофиз. 1964. № 7. С. 87–94.

4. Веников В. А. Теория подобия и моделирование // М. : Высшая школа, 1968.

5. Седов Л. И. Методы подобия и размерности в механике. 10-е изд., доп. М. : Наука. Гл. ред. физ.-мат. лит., 1987. 432 с.

6. Герасимато Ф. Г. Теория подобия // Академия Тринитаризма. 2013. № 77-6567.

7. Сергиенко А. Б. Цифровая обработка сигналов. СПб. : Питер, 2002.

8. Россиев А. А. Итерационное моделирование неполных данных с помощью многообразий малой размерности. Красноярск, 2000.

9. Самарский А. А. Введение в численные методы. М. : Наука. Главная редакция физико-математической литературы, 1982. 272 с.

10. Зиновьев А. Ю. Визуализация многомерных данных. Изд-во КГТУ, 2000.

11. ГОСТ Р 54362-2011. Геофизические исследования скважин. Термины и определения. URL:http://sanse.ru/text/GOST_2008.pdf (дата обращения: 4.04.2014).

List of references

1. Marcey, L., Abate, Kathleen, V., Diegert, Heather, W., «Allen A Hierarchical Approach to Improving Data Quality,» Data Quality Journal, vol. 4, no. 1, 1998.

2. Botvinovskaya, O. A., Ganichev, D. I., Khamitov, I. G., Khasanov, R. G., Multi-well technology well logging data interpretation in OAO «NK «Rosneft», URL: http://prime.geotec.ru/ROSNEFT.doc (accessed: 4.04.2014).

3. Guberman, Sh. A., Ovchinnikova, I. M., «Some possibilities for using the statistical characteristics of geological sections», Izv. USSR ACADEMY OF SCIENCES. Ser. Geophys., no. 7, pp. 87–94, 1964.

4. Venikov, V. A., Theory of similarity and modeling, Moscow: Vysshaya SHKOLA, 1968.

5. Sedov, L. I. Methods of similarity and dimension in mechanics, 10th ed., EXT., Moscow: Nauka. GL. ed. Fiz.-Mat. lit., 1987, 432 p.

6. Gerasimo, F. H., «Similarity theory,» Academy of Trinitarism, no. 77-6567, 2013.

7. Sergienko, A. B., Digital signal processing, SPb.: Peter, 2002.

8. Rossiev, A. A., Iterative modeling of incomplete data with the help of manifolds of small dimension, Krasnoyarsk, 2000.

9. Samarskiy, A. A., Introduction to numerical methods, Moscow: Nauka. Home edition physical and mathematical literature, 1982, 272 p.

10. Zinoviev, A. Yu., Visualization of multidimensional data, Publishing house KGTU, 2000.

11. GOST R 54362-2011. Geophysical investigations of wells. Terms and definitions. URL: http://sanse.ru/text/GOST_2008.pdf (date accessed: 4.04.2014).

VN:F [1.9.17_1161]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.17_1161]
Rating: 0 (from 0 votes)
VN:F [1.9.17_1161]
Стиль изложения
Информативность
Сложность вопроса
Научная новизна
Коммерциализуемость
Rating: 0.0/5 (0 votes cast)