«Новые информационные технологии в автоматизированных системах Материалы шестнадцатого научно-практического семинара Москва 2013 УДК 621.38 ББК 32.81 Н - 76 Н - 76 Новые информационные технологии в автоматизированных ...»

330–349, 2008.

[6] P. Ledda, A. Chalmers, T. Troscianko, and H. Seetzen, “Evaluation of tone mapping operators using a high dynamic range display,” ACM Transactions on Graphics (TOG), vol.

24, no. 3, pp. 640–648, 2005.

[7] M. Kuhna, M. Nuutinen, and P. Oittinen, “Method for evaluating tone mapping operators for natural high dynamic range images,” in IS&T/SPIE Electronic Imaging.

International Society for Optics and Photonics, 2011, pp. 78760O–78760O.

[8] T. Mertens, J. Kautz, and F. Van Reeth, “Exposure fusion: A simple and practical alternative to high dynamic range photography,” in Computer Graphics Forum. Wiley Online Library, 2009, vol. 28, pp. 161–171.

[9] Farbman, Zeev, Raanan Fattal, Dani Lischinski, and Richard Szeliski. "Edgepreserving decompositions for multi-scale tone and detail manipulation." In ACM Transactions on Graphics (TOG), vol. 27, no. 3, p. 67. ACM, 2008.

[10] М.А. Матросов, А.В. Игнатенко, «GMLePublish: web-система оценки алгоритмов тональной компрессии HDR-изображений», Сборник трудов научно-практического семинара «Новые информационные технологии в автоматизированных системах-16».

М.: ИПМ, 2013 г. сс. 37- трекинга объектов, меняющих форму МГУ им. Ломоносова, ф-т ВМК, кафедра АСВК, лаборатория КГиМ Аннотация. В статье представлен алгоритм пересегментации изображений, для которых известна предварительная разметка объект-фон. На основе предварительной разметки строится ее огрубление (овыпукление). Степень огрубления задается параметрически. Полученные сегментации могут использоваться в задаче трекинга объектов, меняющих форму, исчезающих и появляющихся вновь.

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

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

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

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

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

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

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

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

Обзор существующих алгоритмов В настоящее время существует довольно много алгоритмов автоматической и полуавтоматической сегментации изображений. Подробное описание базовых направлений можно найти в обзоре [2].

В статье «Алгоритмы детектирования разметки и дефектов дорожного покрытия» [3] рассматривается алгоритм выделения контура дефекта, в основе которого лежит метод активных контуров (“змея”-snake) [4]. На входе имеются только координаты какой-либо внутренней точки объекта. Поиск контура состоит из следующих этапов:

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

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

3) Постобработка: коррекция результата методом минимального разреза графа [5].

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

Метод разрастания регионов (region growing) [6] работает снизу-вверх (bottom-up).

Вначале определяется пиксель-семя (seed pixel) происходит его сравнение с соседями.

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

Алгоритм, о котором рассказывается в этой работе, базируется на методе разрастания регионов. Однако у него есть несколько отличий от классического алгоритма:

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

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

Алгоритм базируется на дистантном преобразовании [7] предварительной четкой маски и использует идеи метода разрастания регионов. С его помощью можно находить несколько объектов на изображении и четко их разграничивать. У алгоритма есть один параметр – порог максимальной компактности. Компактность (C) понимается как отношение квадрата периметра (P) к площади объекта (S):

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

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

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

3 В этом пике строится начальный объект – окружность с радиусом R = dmap(x0,y0).

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

Описание шага роста:

Ищется среднее и максимальное значение (medV и maxV) дистантного преобразования по всем точкам текущей границы объекта. Каждая точка границы расширяется пропорционально своему значению в дистантном преобразовании и значению среднего: d = dmap(i,j)*medV/maxV.

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

6 Занятая объектом область исключается из рассмотрения в алгоритме трекинга.

Рис. 3. Пример работы на сегментации в виде звезды. Шаг 1,2,4,7. ( Значения компактности Огрубляет контуры четкой маски при сохранении формы, препятствует нежелательному соединению различных разметок, строит огибающую с внешней стороны (разрастает исходную маску). Может применяться вкупе с методом нахождения неточной маски в тех случаях, когда гарантированно отсутствие внутренней фрагментации. Если возможно подразбиение четкой маски, то его использовать не рекомендуется. Умная морфология уничтожает внутренние неоднородности и помогает бороться с шумом. Параметр алгоритма – число шагов разрастания (степень огрубления) NSTEPS.

Описание работы: итерационно присоединяет к маски соседнюю область (как в стандартном методе разрастания регионов).

В пределе (NSTEPS = ) превращает объект в его огибающую прямыми линиями и наклонными линиями (и далее не разрастается).

расширение (150 шагов), закрытие (R = 75), открытие (R = 75) Рис. 6. Результат разметки без морфологии, с обычным расширением, с “умным” Пример использования приведенных алгоритмов в задаче трекинга Теперь рассмотрим более подробно, как встроить алгоритм пересегментации в имеющийся алгоритм трекинга. Рассмотрим случай постобработки видео. Это значит, что имеется буфер информации с кадрами от 1 до N. Про объекты нам известны ограничения на их относительные и абсолютные перемещения, также известен минимальный размер искомого объекта. Известно, что у объекта довольно хорошая компактность. Подходящие объекты: человек, машина, собака, самолет, футбольный мяч. Не подходящие: змея, пожарный шланг, ленточка гимнастки.

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

4 Выберем максимальный локальный пик (кадр K) и будем строить цепочки из локальных пиков в направлении кадра 1 и в направлении кадра N. Два локальных пика соединяются в цепочку при минимизации функционала близости. Функционал близости задается для двух точек в пространстве XYT, может использовать информацию о расстоянии, интенсивности, градиенте и 5 Для каждого узла цепочки и предварительных сегментаций выполним операцию нахождения компактной маски.

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

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

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

Список литературы 1. M. Calafut. Multiple-Object Tracking in the Infrared. Stanford University.

2. В. Конушин, В. Вежневец. Методы сегментации изображений: интерактивная сегментация. Компьютерная графика и мультимедиа. Выпуск №5(1)/2007.

3. С. Судаков, А. Семашко, О. Баринова, А. Конушин, В. Киншаков, А. Крылов.

Алгоритмы детектирования разметки и дефектов дорожного покрытия. 2008.

Графикон’2008, стр. 206- 4. M. Kass, A. Witkin and D. Terzopoulos “Snakes: Active Contour Models” International Journal of Computer Vision, vol. 1, pp. 321-331, 5. E.V. Zaugolnova, D.V. Yurin “Algorithm for Refinement of Preliminary Segmentation of Images with Smooth, Low Contrast 2D Objects Boundaries” In proc.

Graphicon, 6. R.M. Haralick and L.G. Shapiro. Survey: Image. Segmentation. Techniques.

CVGIP, vol. 29, 1985, pp. 100- 7. http://en.wikipedia.org/wiki/Distance_transform Приложение Рис. 7. Пример работы алгоритма для разложения на компоненты. Исходное изображение, умное расширение. Результат разметки с ограничением на компактность встраиванием цифровых водяных знаков Аннотация. В статье ставится задача создания метода для противодействия подделкам цифровых фотографий, описывается алгоритм защиты изображения.

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

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

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

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

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

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

Для повышения робастности вложения встроенных ЦВЗ к сжатию или масштабированию графических файлов в стегоалгоритмах стараются применять те же преобразования, что и в алгоритмах сжатия этих файлов [3]. Для формата JPEG таким алгоритмом является дискретное косинусное преобразование, для JPEG2000 – вейвлет-преобразование.

Графический формат JPEG2000 имеет ряд преимуществ по сравнению с форматом JPEG. Это лучшее качество изображения при равной степени сжатия, оптимизация качества кодирования, а также возможность сжатия без потерь. Поэтому при выборе формата сохранения цифровой фотографии лучше отдать предпочтение более современному JPEG2000. Разрабатываемый алгоритм встраивания информации должен быть основан на вейвлет-преобразовании, так как в этом случае ЦВЗ будет устойчив к сжатию изображения.

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

В статье [5] разбирался существующий метод встраивания ЦВЗ в фотоизображение в формате JPEG2000 с помощью вейвлет-преобразования маркировкой наиболее существенных участков данного изображения с учётом особенностей человеческого восприятия. Такой метод достаточно эффективен для доказательства подлинности цифровой фотографии, поскольку встроенную таким образом информацию сложно повредить или удалить, не ухудшив визуальных качеств самого изображения. Однако данный метод не вполне подходит для доказательства факта обрезки исходного изображения, а также удаления или замены его значащих частей.

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

Для достижения поставленной цели можно использовать следующий алгоритм.

1. Исходное изображение, которое можно представить как матрицу f(n,m) разбивается на одинаковые блоки aij размером 64 х 64 пикселя (рис. 1).

2. Выбирается алгоритм расположения ЦВЗ, являющихся матрицей w(m, n) размером х 4 пикселя, в этих блоках. Целесообразно встраивать в каждый блок по 4 ЦВЗ, отступая от края не менее чем на 3 пикселя, но располагая их несимметрично относительно этого блока (рис. 2).

3. ЦВЗ встраиваются в каждый блок изображения согласно выбранному алгоритму.

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

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

применения к изображению процедуры кадрирования.

Вернёмся к алгоритму.

Рис. 3. Пример алгоритма нанесения ЭЦП в блок изображения 4. Выбирается алгоритм нанесения в блоки различных ЭЦП (рис. 3).

5. Составляются ЭЦП в зависимости от их назначения.

6. ЭЦП встраиваются в блоки изображения в соответствии с выбранным алгоритмом.

7. ЭЦП каждого блока корректируется в зависимости от соседних блоков.

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

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

Для этого целесообразно действовать следующим образом.

1. Выполняя преобразование, находим все детектируемые ЦВЗ и проверяем регулярность структуры.

2. По меткам ЦВЗ находим ЦВЗ-ЭЦП и проверяем их регулярность.

Если расположение встроенных ЦВЗ и ЦВЗ-ЭЦП регулярно и соответствует алгоритму их расположения в блоках, можно сделать вывод, что это изображение не подвергалось внешним атакам.

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

Например, в случае удаления каких-либо объектов с исходной фотографии на месте удаленного объекта ЦВЗ и ЭЦП детектироваться не будут (рис. 4).

При смещении какого-либо объекта на исходной фотографии при проверке подлинности может быть выявлено смещение ЭЦП, а также перекрытие ЦВЗ (рис. 5).

на нем будет выявлено отсутствие маркировки (рис. 6).

Рис. 4. Удаление объекта. Слева исходное изображение, справа модифицированное, красной чертой обведено место с нарушением структуры вложений, блоки разбиения Рис. 5. Смещение объекта. Красной чертой обведено место с нарушением структуры вложений, блоки разбиения изображения показаны квадратами В случае если извлеченные ЭЦП и ЦВЗ извлечены корректно (не деформированы), необходимо проверить, соответствует ли расположение всех ЭЦП алгоритму их встраивания. В случае обрезки промаркированного изображения они будут смещены.

предполагается, что хрупкие ЭЦП будут разрушены, а ЦВЗ будут детектироваться.

Рис. 6. Вставка стороннего объекта. Красной чертой обведено место с нарушением структуры вложений, блоки разбиения изображения показаны квадратами Благодаря разбиению исходной цифровой фотографии на блоки, несимметричной маркировке блоков ЦВЗ и наличию в центре каждого блока ЭЦП, расположенных согласно выбранному алгоритму, при проверке подлинности изображения можно определить, подвергалось ли оно обрезке, фильтрации или другим атакам.

Список литературы 1. Цзянь Ван. Исследование устойчивости цифровых водяных знаков-логотипов, внедряемых в статические изображения. Автореферат. С.-Пб, 2010. – 20с.: ил.

2. О.В. Михайличенко. Методы и алгоритмы защиты цифровых водяных знаков при jpeg сжатии. Автореферат. С.-Пб, 2009. – 17с.: ил.

А.В. Аграновский, А.В. Балакин, В.Г. Грибунин, С.А. Сапожников Стеганография, цифровые водяные знаки и стеганоанализ. М.: Вузовская книга, 2009 г 4. В.Г. Грибунин. Вейвлеты в стеганографии. Статья. С.-Пб, 10с.: ил.

5. А.В. Немцов, Ю.А. Белобокова. Защита изображений встраиванием цифровых водяных знаков.

Модель искусственного интеллекта на реляционных множествах Компьютерные системы и сети, МГТУ им. Н.Э. Баумана.

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

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

Ключевые слова: модель, искусственный интеллект, реляционная модель, теория множеств, логические операции.

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

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

• Импликация («следует») ( ) • Эквивалентность («равны») (=) • Неэквивалентность («не равны») (!=) Их достаточно для отображения любой логики принятия решения для конечного алгоритма, и возможность их выполнения берется за показатель состоятельности системы ИИ (Искусственного Интеллекта). Однако на вычисления громоздких логических выражений уходит огромное количество времени, тогда как их можно выполнить побочно с более существенными преобразованиями над данными.

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

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

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

Сравнение выделенных объектов. Чтобы отразить с помощью мышления какие-либо связи и отношения между предметами или явлениями объективного мира, необходимо, прежде всего, в восприятии или представлении выделить эти явления.[3] Например, чтобы понять причину неудачного выполнения спортсменом данного физического упражнения, необходимо сосредоточить свою мысль на этом упражнении и на тех условиях, при которых оно выполнялось. Это выделение всегда связано с осознанием задачи, оно предполагает предварительную постановку вопроса, который и определяет собой выделение интересующих нас объектов. Сравнивая явления друг с другом, мы отмечаем как сходство, так и различие их в определенных отношениях, их тождество или противоположность. Например, низкий или высокий старты сходны между собой по своему назначению, являясь начальным моментом упражнения, но различаются по положению тела спортсмена.[4] Сравнивая выделенные в процессе мышления явления, мы точнее познаем их и глубже проникаем в их своеобразие.

различать отдельные свойства предметов, но и мыслить эти свойства отвлеченно от самих предметов.[3] Такая мыслительная операция называется абстракцией (от лат.

абстракций — отвлечение). Процесс абстрагирования есть мысленное (временное) отвлечение одного свойства вещи от других ее свойств, одного предмета от других предметов, с которыми он в действительности связан. Так, исследуя закономерности процесса реакции спортсмена на старте, психолог-эксперименталист выделяет только один элемент этого процесса — латентный период, отвлекаясь (пока, на время) от таких побочных явлений, как влияние на спортсмена зрителей, его личное отношение к данному соревнованию и т. д.[4] Абстракция позволяет проникнуть «вглубь»

предмета, выявить его сущность, образовав соответствующее понятие об этом предмете.

Обобщение. Абстракция всегда соединяется с обобщением; абстрагированные свойства предметов мы сейчас же начинаем мыслить в их обобщенном виде.

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

Конкретизация. Абстракция всегда предполагает противоположную ей мыслительную операцию — конкретизацию, т. е. переход от абстракции и обобщения обратно к конкретной действительности. В учебном процессе конкретизация часто выступает как приведение примера для установленного общего положения. В соединении с абстракцией конкретизация является важным условием правильного понимания действительности, так как она не позволяет мышлению отрываться от живого созерцания явлений. Благодаря конкретизации наше мышление становится жизненным, за ним всегда чувствуется непосредственно воспринимаемая действительность. Отсутствие конкретизации приводит к тому, что знания становятся голыми абстракциями, оторванными от жизни, а потому и бесполезными.[3] Анализ. Анализом называется мысленное разложение какого-либо сложного предмета или явления на составляющие его части. В практической деятельности анализ приобретает форму фактического расчленения предмета на составляющие его части. Возможность практически выполнить такое расчленение лежит в основе мысленного расчленения предмета на его элементы.[3] Например, думая о сложной структуре прыжка, мы мысленно выделяем в нем следующие основные части: разбег, толчок, фаза полета, приземление. Этот мысленный анализ облегчается тем, что и в действительности мы можем выделить эти моменты и совершенствовать в процессе тренировки скорость разбега, силу толчка, правильность группировки в полете и т.

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

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

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

Рис 2. Представление предложения структурой реляционных множеств Представление такой структурой, а именно реляционной структурой множеств, использует шесть основных аксиом множеств[1]:

• аксиому объёмности (два множества a и b равны тогда и только тогда, когда они имеют одни и те же элементы);

• аксиому о существовании «элементарных множеств»;

множество b, элементами которого являются те и только те элементы a, которые обладают свойством );

• аксиому множества подмножеств (для любого множества a существует множество b, состоящее из тех и только тех элементов, которые являются подмножествами множества a);

• аксиому объединения (для любого семейства a множеств существует множество, называемое объединением множества a, состоящее из тех и только тех элементов, которые содержатся в элементах множества • аксиому выбора (для каждого семейства непустых непересекающихся множеств существует (по меньшей мере одно) множество d, которое имеет только один общий элемент c c каждым из множеств b данного Ставя им в соответствие операции, выполняемые человеческой памятью (Рисунок 3):

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

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

• Вариантное (устанавливает отношение аналогии между членами) • Объединяющее (устанавливает отношение совокупности между членами) Реляционная модель данных (РМД) — логическая модель данных, которая является приложением к задачам обработки данных таких разделов математики как теории множеств и логики первого порядка.

Термин «реляционный» означает, что теория основана на математическом понятии отношения (relation). Для лучшего понимания РМД следует отметить три важных обстоятельства:

(абстрактными), а не физическими (хранимыми) структурами;

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

Реляционная модель данных включает следующие компоненты:

• Структурный аспект (составляющая) — данные представляют собой • Аспект (составляющая) целостности — отношения отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня • Аспект (составляющая) обработки (манипулирования) — РМД поддерживает операторы манипулирования отношениями (реляционная алгебра, реляционное исчисление).

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

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

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

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

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

• Осуществляется сборка ячейки нисходящей генерацией.

На рисунках 8,9 и 10, предоставлены модели описанных подзадач.

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

Список литературы 1. К. Куратовский, А. Мостовский Теория множеств / Перевод с английского М.

И. Кратко под редакцией А. Д. Тайманова. — М.: Мир, 1970. — 416 с.

2. А. Френкель, И. Бар-Хиллел Основания теории множеств / Перевод с английского Ю. А. Гастева под редакцией А. С. Есенина-Вольпина. — М.: Мир, 1966.

— 556 с.

3. Коган А. Б. Нейрофизиологические механизмы мышления человека // Основы физиологии высшей нервной деятельности. — второе, переработанное и дополненное. — Москва: Высшая школа, 1988. — С. 335—350. — 368 с. — экз. — ISBN 5-06-001444-4;

4. Маланов, С. В. Психологические механизмы мышления человека: мышление в науке и учебной деятельности / С. В. Маланов — М.: Издательство Московского психолого-социального института; Воронеж: Издательство НПО «МОДЭК», 2004. — 480 с.

5. Тихомиров О. К. Психология мышления. М.: 1984.

6. Dias F.M., Mota A.M. Comparison between Different Control Strategies using eural Networks // 9th Mediterranean Conference on Control and Automation. – Dubrovnik, Croatia, 2001.

7. Venayagamoorthy G.K., Harley R.G., Wunsch D.C. Implementation of Adaptive Criticbased Neurocontrollers for Turbogenerators in a Multimachine Power System”, IEEE Transactions on Neural Networks. – 2003. – Vol. 14, Issue 5. – P. 1047 – 1064.

8. McCalloch W.S., Pitts W. A logical calculus of the ideas immanent in nervous activity.// Bull. Math. Biophys. – 1943. – v.5. – pp. 115–133.

Центр информационных технологий в проектировании РАН Россия, Московская область, г. Одинцово, ул. Маршала Бирюзова, д.7а Введение Генетические алгоритмы (ГА), предложенные в 1975 году Джоном Холландом (John Holland) из Мичиганского университета, предназначены для решения задач оптимизации и отыскания глобального экстремума многоэкстремальной функции, но также нашли свое применение при решении задач «интеллектуального» анализа данных. Эти задачи характеризуются отсутствием априорных предположений о структуре выборки и виде распределений значений анализируемых показателей. В свою очередь генетические алгоритмы работают с кодовыми последовательностями (КП) безотносительно к их смысловой интерпретации и не привязаны к предметной области. Кодовая последовательность и ее структура задается понятием генотипа, а его интерпретация, с точки зрения решаемой задачи, понятием фенотипа. Каждая КП представляет, по сути, точку пространства поиска и называется особью или индивидуумом, а их набор образует исходное множество решений или популяцию.

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

1. Функционирование генетического алгоритма Функционирование ГА состоит из нескольких этапов. На первом, происходит кодирование признаков характеризующих объект. Эти закодированные признаки называются генами, а совокупность таких признаков – хромосомой. В свою очередь, набор хромосом особи формирует генотип, т.е. особями популяции могут быть генотипы либо единичные хромосомы, в случае, если генотип состоит из одной хромосомы.

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

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

Критерием останова может быть одно из трех событий:

• сформировано заданное число поколений;

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

После завершения работы ГА из конечной популяции выбирается та КП (особь), которая дает оптимальное значение целевой функции, и которая является, в итоге, результатом работы ГА.

2. Поиск логических закономерностей Существует целый ряд методов для определения логических закономерностей. В большинстве случаев задается множество возможных событий T = {T1,K, Tn }, и из этого множества строятся цепочки конъюнкций. Среди них тем или иным способом (перебор, вероятностные методы и т.д.) отбираются наиболее характерные для одного из классов и не характерные для других. Основной проблемой является, как определить возможные события. К таким методам могут быть отнесены алгоритм Кора и случайный поиск с адаптацией (СПА). Другим подходом для поиска логических закономерностей являются методы, основанные на применении деревьев решений. Их построение обычно осуществляется с использованием алгоритмов обработки примеров (CLS, ID3 (Interactive Dichotomizer), CART (classification and regression trees) и др.). Здесь следует отметить, что путь от вершины корня до вершины листа также представляет собой цепочку конкатенаций элементарных событий, и проблема их определения остается.

Рассмотрим задачу, в которой логические закономерности используются для отнесения объекта к одному из N классов A = { A1,K, AN }. Определим количество популяций равное количеству классов N. Выбор такого количества популяций обусловлен тем, что оценку показателей точности и полноты правил при выделении логических закономерностей целесообразно производить для каждого класса. При единственной популяции происходит усреднение данной оценки. Тем самым рассматриваемый подход можно отнести к так называемым островным алгоритмам [1].

Особью (хромосомой) является само правило. Количество особей, в отличии от большинства ГА, в популяции переменно и определяется с одной стороны минимально возможным числом для образования родительских пар, а с другой – максимально возможной полнотой популяции. Обучающая последовательность из n объектов задается в виде пар: < X i, ti >, i = 1 n где X i - m–мерный вектор параметров X i = ( x1i,K, xmi ), ti A - принадлежность к классу, тогда хромосома имеет постоянную длину равную m*2, где m – число параметров (признаков), по которым проводится классификация и представляется в виде: (( x1, min, x1,max ),…,( xm, min, xm, max )). Здесь xi, min, xi, max, соответственно верхняя и нижняя граница (область определения) значения которых выполняется условие: xi, min wijk wijk xi, max, i = 1 m, j = 1 N, k = 1 K, где K – количество особей в популяции. Таким образом, каждая особь в популяции представляет собой m – мерный гиперкуб в пространстве признаков со сторонами < wijk, wijk >, который соответствует некоторому правилу. Исходные популяции строятся случайным образом, так чтобы максимально покрыть пространство признаков.

получен из решения задачи поиска количества гиперкубов со сторонами, размер которых равновероятно распределен в диапазоне (0, xi, max xi, min ), причем этот набор с вероятностью P 1 должен закрывать все точки пространства признаков.

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

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

2.2. Целевая функция Критерием качества получаемого решения являются точность и полнота.

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

Здесь rkj - количество объектов, удовлетворяющих критерию, заданному в генотипе особи k (т.е. объектов, попавших в гиперкуб, соответствующий данной особи) и принадлежащих классу A j для популяции j (расстояние по Хэммингу).

Фактически целевая функция определяет точность правила. Тогда целью генетического алгоритма является нахождение такой популяции, в которой содержится подмножество особей K Rj K j, где K j - общее количество особей для популяции, моделирующей принадлежность к классу j, для которого Fkj 1 и число объектов, принадлежащих данному классу в обучающей выборке максимально, то есть U kj = SSO j. Здесь kj - множество объектов, удовлетворяющих критерию и принадлежащих классу A j, сформулированному для особи k, SSO j - множество объектов, принадлежащих к классу A j среди множества исходных объектов [1].

2.3. Выбор родительских особей.

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

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

Это означает, что КП с наибольшим значением точности правила могут входить в несколько родительских пар.

2.4. Основные операторы Непосредственная генерация новых КП осуществляется из двух родительских особей за счет оператора скрещивания (кроссовера, случайно–детерминированного обмена). Вероятность применения оператора скрещивания является одним из параметров генетического алгоритма и обычно выбирается достаточно большим, например от 0.9 до 1.

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

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

После этапа скрещивания, выполняется оператор мутации. Мутация представляет собой случайное изменение КП. В нашем случае осуществляется случайное изменение какого-либо элемента пары < wijk, wijk >, которая также выбирается случайным образом. Данные изменения должны удовлетворять требованиям: сохранение упорядоченности пары и попадание в диапазон области значений для заданной переменной. Оператор мутации позволяет находить локальные экстремумы с одной стороны и позволяет «перескочить» на другой локальный экстремум с другой. Вероятность выполнения этого оператора является еще одним параметром алгоритма.

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

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

Самыми распространенными операторами отбора являются:

• случайный равновероятный отбор;

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

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

• элитный отбор, который заключается в переносе некоторого количества (например, 10%) самых здоровых хромосом в следующее поколение;

• отбор с вытеснением или метод турнира, в котором из популяции отбирается k особей, которые затем соревнуются за право попасть в следующее поколение;

побеждает та хромосома, здоровье которой выше; турнир повторяется l раз.

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

Еще одной особенностью алгоритма является введение оператора миграции, который позволяет переносить кодовую последовательность (особь) из одной популяции в другую. Он выполняется с некоторой вероятностью, если в популяции j встречается особь k, для которой Fkj < Fkp, j p. Перенос осуществляется в популяцию p. Смысл этого оператора заключается в том, что правила, имеющие низкую точность для одного класса, могут иметь более высокую точность для другого класса. Такая ситуация наиболее часто возникает в начальных поколениях.

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

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

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

Однако, в этом виде алгоритм не лишен ряда недостатков, присущих другим подобным алгоритмам:

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

2. Могут встречаться подобные, фактически совпадающие правила.

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

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

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

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

• популяция – множество хромосом, вариантов наборов весовых коэффициентов (множество вариантов нейросети);

• эпоха – итерация, соответствующая созданию нового поколения хромосом.

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

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

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

Список литературы 1. Солодовников И.В., Доронин В.А. Генетический алгоритм для поиска логических закономерностей в данных - // Информационные технологии в управлении. № 7. М.:2005 г.

2. Дюк В., Самойленко А. Data Mining. Учебный курс. – СПб: Питер, 2001.

3. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных.

Интеллектуальная обработка информации. – М.: Нолидж, 2000.

4. Назаров А.В., Лоскутов А.И. Нейросетевые алгоритмы прогнозирования и оптимизации систем. – СПб: Наука и техника, 2003.

5. Ежов А., Шумский С., Нейрокомпьютинг и его применение в экономике и бизнесе,1998.

образования на основе модели нейронной сети ART «Компьютерные системы и сети», МГТУ им.Н.Э.Баумана Аннотация. Дистанционная форма обучения все увереннее заявляет о себе, особенно в высшем образовании. Давно просчитано, что экономически это более выгодная форма обучения, по сравнению с очной формой. В данной статье рассматриваются наиболее существенные недостатки в сфере дистанционного образования. Особое внимание обращается на проблему кластеризации пользователей с помощью архитектуры сети Гроссберга и модели нейронной сети ART1.

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

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

Системы дистанционного обучения на сегодняшний день являются одним из эффективных способов обучения [1,2,3,4].

Они предоставляют ряд преимуществ, таких как:

1) свободное планирование учебных курсов;

2) возможность выбора времени для занятий;

3) индивидуальное обучение.

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

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

К сожалению, в системе дистанционного обучения невозможно предоставить каждому учащемуся таких же возможностей, как при индивидуальной работе с преподавателем, но при этом возможно сделать упор на индивидуальное обучение [3,4].

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

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

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

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

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

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

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

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

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

1) нейросеть должна иметь способность к адаптации;

2) возможность работы без обучающей выборки, то есть обучение нейросети должно осуществляться в процессе работы;

3) нейросеть, при имеющейся адаптивности, должна быть стабильной;

4) нейросеть должна формировать устойчивые кластеры;

5) нейросеть должна иметь возможность менять свою чувствительность.

Подобной нейронной сетью, обладающей всеми вышеперечисленными свойствами, является модель нейронной сети адаптивно-резонансной теории ART1, которая позволяет проводить кластеризацию двоичных входных векторов, и при этом решает дилемму стабильности-пластичности [5,6,7,9,10,11].

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

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

Структурная схема нейронной сети ART Нейронная сеть ART1, позволяющая стабилизировать процесс обучения, является логическим развитием архитектуры сети Гроссберга [12, 13, 14].

ART1 представляет собой двухслойную нейронную сеть, в которой все нейроны первого слоя связаны со всеми нейронами второго слоя (связи «Слой 1 — Слой 2»

или L1-L2), и также обратные связи всех нейронов второго слоя с нейронами первого слоя (связи «Слой 2 — Слой 1» или L2-L1). Также в модель ART1 входит подсистема ориентирования (это один специфический нейрон, который отличается от нейронов в слоях) и управление усилением (либо это два дополнительных нейрона, либо дополнительная обратная связь из второго слоя к первому слою).

Выходы нейронов обоих слоев представляет собой краткосрочную память (STM – short-term memory), а весовые матрицы связей между слоями, в свою очередь, — долгосрочную память (LTM – long-term memory).

Замечание. В сети Гроссберга связи «Слой 2 — Слой 1», подсистема ориентирования и управление усилением отсутствуют.

Структурная схема сети ART1 показана на рисунке 2.

Описание работы сети ART Связи «Слой 1 — Слой 2» обеспечивают операцию кластеризации. Когда входной образ предъявлен сети, то он нормализуется в первом слое, а затем умножается на весовую матрицу связей «Слой 1 — Слой 2». Затем во втором слое (который является однослойной нейронной сетью конкурентного обучения) происходит состязание, которое позволяет определить, какая строка весовой матрицы наиболее близка к входному вектору. Именно эта строка будет в дальнейшем замещена текущим входным вектором.

После окончания обучения нейронной сети каждая строка весовой матрицы «Слой 1 — Слой 2» будет содержать образ кластера, так называемого прототипа. В сети ART1 для обучения используются также обратные связи «Слой 2 — Слой 1», которые являются связями выходной звезды Гроссберга (outstars) [10-11], которые обеспечивают повторный вызов образа. То есть, когда узел во втором слое активирован, то он создает сигнал ожидания (expectation), который передается в первый слой. Сигнал ожидания является образом прототипа, соответствующего активному выходному нейрону второго слоя. Далее, первый слой осуществляет сравнение образа ожидания и входной образ.

В случае, когда входной образ существенно отличается от образа ожидания (степень «похожести» определяется параметром бдительности), то в подсистеме ориентирования формируется сигнал сброса (reset) для второго слоя. Этот сброс дезактивирует текущий нейрон-победитель и удаляет соответствующее этому нейрону ожидание. Причем этот нейрон переходит в неактивное состояние до самого окончания работы с текущим входным вектором. Далее во втором слое опять повторяется состязание, и на этот раз выигрывает другой нейрон, который передает новый сигнал ожидания в первый слой через связи «Слой 2 — Слой 1». Этот процесс продолжается до тех пор, пока ожидание в связях «Слой 2 — Слой 1» не обеспечит необходимой близости с входным образом.

Работа нейронной сети строится по следующему алгоритму [5]:

1. На вход сети поступает образ;

2. Входной образ сравнивается с имеющимися образами-прототипами;

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

4. Если степень схожести входного образа и образа-прототипа не удовлетворяет параметру бдительности, то нейрон, соответствующий этому образу-прототипу, тормозится и далее снова выполняется шаг 2, иначе шаг 5.

5. Если степень схожести входного образа и образа-прототипа удовлетворяет параметру бдительности, то в сети наступает резонанс – все выходные нейроны выполняется шаг 6.

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

7. Входной образ убирается, восстанавливаются сигналы всех заторможенных нейронов и далее снова выполняется шаг 1.

Основные этапы кластеризации учащихся показаны на Рисунке 3.

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

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

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

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

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

1. Кречетников К.Г., Черненко Н.Н. Дистанционное обучение. Достоинства, http://www.hr-portal.ru/article/distantsionnoe-obuchenie-dostoinstva-nedostatki-voprosyorganizatsii-krechetnikov-k-g-cherne (дата доступа: 20.09.2012) 2. Полат Е.С. Педагогические технологии дистанционного обучения [Электронный ресурс] // http://www.distant.ioso.ru/seminary/09-02tezped.htm (дата доступа: 18.09.2012) 3. Полат Е.С, Моисеева М.В., Петров А.Е. Педагогические технологии дистанционного обучения / Под ред. Е.С.Полат. — М., "Академия", 2006.

4. Концепция создания и развития единой системы дистанционного образования в России: утверждена Постановлением Госкомитета РФ по высшему образованию от 31 мая 1995 г. № 6 // КонсультантПлюс: ВысшаяШкола: Программа информационной поддержки российской науки и образования: Специальная подборка правовых документов и учебных материалов для студентов: учебное пособие. - 2007. Вып.4.

5. Джонс М.Т. Программирование искусственного интеллекта в приложениях/ М.Тим Джонс.- М.: ДМК Пресс, 2006.

6. Гроссберг С. Внимательный мозг [Электронный ресурс]// Открытые системы, №4, 1997. – URL: http://www.osp.ru/os/1997/04/179198/ (дата обращения:06.04.2011) 7. Комарцова Л.Г. Нейрокомпьютеры: Учеб. Пособие для вузов.

/Л.Г.Комарцова, А.В.Максимов. – 2-е изд., перераб. и доп. –М.: изд-во МГТУ им.Н.Э.Баумана, 8. Хайкин С. Нейронные сети: полный курс, 2-е изд., испр. – М.: OOO «И.Д.Вильямс», 2006.

9. Carpenter G.A. A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine / G.Carpenter, S. Grossberg //Computing Vision, Graphics, and Image Processing, 37. pp. 54-115, 10. Grossberg S. Adaptive Pattern Classification and Universal Recording: I. Parallel Development and Coding of Neural Feature Detectors // Biological Cybernetics, No. 23, 11. Grossberg S. Adaptive Pattern Classification and Universal Recording: II.

Feedback, Expectation, Olfaction, Illusion // Biological Cybernetics, No. 23, 12. Barbara M. ART and Pattern Clustering. - Proceedings of the 1988 Connectionist Model Summer. - Published by M.Kaufmann, San Mateo, CA, pp. 174-185.

13. Devaux S. Classification hybride ART-CS: Apprentissage par renforcement, vision et rorotique. Rapport de projet de fin d'etudes [Электронный ресурс] / Tours, [1996]. URL: http://sde.eduvax.net/artcs/ (дата обращения: 06.04.2011).

14. Hagan M.T. Neural Network Design / M.T. Hagan, H.B. Demuth, M.H. Beale. Boston, MA: PWS Publishing, 1996.

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

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

За последнее десятилетие анализ многомерных данных стал одним из основных направлений прикладной математики, активно развивающимся и применяющимся практически во всех областях исследований. Анализ многомерных данных (АМД или MDA – Multidimensional Data Analysis) является одной из наиболее популярных и востребованных междисциплинарных областей знания и активным инструментом синтеза различных дисциплин [1]. Одним из наиболее известных методов анализа многомерных данных является метод главных компонент и его обобщения для нелинейных случаев [2]. Методы анализа многомерных данных реализуются в тесной взаимосвязи и взаимодействии с методами факторного и кластерного анализа [3].

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

2. Общая постановка задачи анализа многомерных данных Рассмотрим функцию F ( ), заданную дискретным образом в области, расположенной в n-мерном пространстве X n. Пространство X n задано с помощью конечного множества ортогональных векторов X = ( X 1, X 2,..., X n ). Многомерные данные – это числовые значения функции F ( ), заданные в точках n-мерного пространства ( x1, x2,..., xn ). Для определения расстояния в пространстве X n выбирается метрика. Далее будем предполагать в качестве метрики обычное евклидово расстояние.

Таким образом, многомерные данные представляют собой набор числовых значений, заданный в точках области : F ( ) = F ( x1, x2,..., xn ).

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

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

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

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

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

- методы и подходы, позволяющие понизить размерность исследуемого пространства до стандартной;

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

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

Пусть имеется математическая модель нестационарного процесса и надежный численный метод для решения этой модели. В этом случае мы можем решать прямую задачу численного моделирования нестационарного процесса. Допустим, что в моделируемом процессе происходит некое событие (явление, эффект). Численное решение F = F ( x, x1,..., xn ) выбранной задачи формируется в процессе математического моделирования и определяется управляющим параметром x и конечным набором определяющих параметров задачи ( x1,..., xn ). Обозначим X = ( x, x1,..., x n ) и введем функционал события Ф( F ( X )), который на решении задачи принимает, подобно логической переменной, два значения: 1 – если событие, интересующее исследователя, наступило (независимо от рода события) и 0 – если событие не наступило.

Ф( F ( X )) = 1 - событие наступило.

Пусть x - значение управляющего параметра, при котором наступает изучаемое явление. Тогда общую постановку задачи можно записать формально следующим образом:

( x1,..., xn ), где I ( x ) - функционал следующего вида Таким образом, наша задача формально состоит в минимизации функционала I ( x ) при помощи вариации управляющего параметра. А в реальности, варьируя x, мы должны с приемлемой точностью отыскать значение x, то есть то значение управляющего параметра, при котором событие наступает.

Мы получаем одно значение x ( x1,..., xn ) для управляющего параметра при фиксированных определяющих параметрах. Но задача исследования состоит в том, чтобы построить зависимость x ( x1,..., xn ) для всех возможных значений определяющих параметров. Таким образом, если мы имеем в диапазоне разбиения каждого определяющего параметра M точек, то для того чтобы найти значения x управляющего параметра для всех наборов ( x1,..., xn ), необходимо решить M n однотипных задач вида (2). В результате решения этого набора задач находятся все точки в исследуемом пространстве определяющих параметров, где происходит событие.

Рассматривая ( x1,..., xn ) как набор базисных векторов, можно представить пространство определяющих параметров L( x1,..., xn ), имеющее размерность n.

Тогда в общем случае задачу оптимизационного анализа можно сформулировать как нахождение в пространстве L всех подобластей L*, где наблюдается изучаемое событие, т.е. Ф(L* ) = 1.

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

последовательном режиме вычислений представлен в работе [4]. Данный алгоритм в целом предполагает решение очень большого количества обратных задач численного моделирования ( M n ), каждая из которых предполагает, в свою очередь решение большого количества прямых задач. Это обстоятельство делает реализацию вышеизложенного алгоритма весьма затруднительной с точки зрения временных затрат. В работе [6] рассматривается наиболее простой и эффективный вариант распараллеливания данного алгоритма. В силу того, что процессы решения ОЗ происходят фактически без обменов информацией между процессорами, распараллеливание здесь сводится к организации интерфейса, управляющего распределением вариантов по процессорам и сбором данных в единый массив результатов. Идеология параллельных вычислений в данном случае принимает форму «многозадачного рассматриваемой оптимизационной задачи в параллельном режиме позволяет быстро определяющих параметров задачи x ( x1,..., xn ) в виде многомерного массива.

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

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

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

Рассмотрим наиболее распространенные практические способы понижения размерности.

Первый способ представляет собой поиск координатного направления с наименьшей дисперсией. Согласно общей схеме анализа данных в процессе общей обработки данных вычисляются средние значения функции S i и дисперсии Di по координатным направлениям. С помощью полученного набора D1, D2,... Dn находим координатное направление j с наименьшей дисперсией данных Dmin = min{ Di }.

Далее проверяем выполнение следующего условия:

где - малая величина, задаваемая пользователем.

Если условие (3) выполняется, то по координатному направлению j значения исследуемой функции заменяются на константу, равную среднему значению функции многомерного пространства понижается на единицу.

Изложенный подход обладает рядом недостатков:

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

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

- условие (3) выполняются далеко не всегда, например, если данные образуют в многомерном пространстве гиперсферу, то эти условия заведомо не выполняются;

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

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

Второй распространенный способ понижения размерности заключается в построении графических проекций на стандартное число измерений с фиксацией переменных, не участвующих в построении проекции. Далее проводится анализ вида проекций, который во многих случаях позволяет определить визуально координатное направление с наименьшей диперсией, и, исключив его, понизить размерность рассматриваемой области. Также данный подход очень полезен в тех случаях, когда из набора дисперсий по направлениям D1, D2,... Dn нельзя выделить существенно наименьшую. В этих случаях в задачах небольшой размерности n = 4;5 для построения аналитической зависимости часто используется метод разделения переменных, приведенный в [6].

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

Более современным способом понижения размерности массива данных является метод главных компонент (англ. Principal Components Analysis, PCA). Суть метода состоит в переходе от исходной системы координат к новому ортогональному базису в рассматриваемом многомерном пространстве, оси которого ориентированы по направлениям максимальной дисперсии массива данных. Различные варианты реализации метода главных компонент и его обобщений для нелинейных случаев подробно представлены в работах [2,7]. Геометрическая постановка задачи нахождения главных компонент формулируется согласно [7] следующим образом. В многомерном пространстве ищется вектор направления, задающий прямую, вдоль которой дисперсия максимальна (или сумма квадратов расстояний от точек данных до прямой минимальна). Таким образом определяется первая главная компонента.

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

Так рассчитывается вторая главная компонента. Снова рассчитывается множество векторов вторых остатков и т.д.

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

5. Пример решения конкретной задачи Данный подход к организации параллельного расчета был применен к конкретной задаче о нестационарном взаимодействии сверхзвуковых струй [4]. В качестве события рассматривалось возникновение новой пространственно-временной структуры течения (ПВС), в качестве управляющего параметра использовалась скорость повышения нерасчетности струи V *, а в качестве определяющих параметров были выбраны характерные числа Маха, Рейнольдса, Прандтля и Струхаля ( M, Re, Pr, Sh ) для данной задачи. Рассматривались разбиения определяющих параметров по 5 и 10 точек на каждый параметр в диапазоне его изменения, что вело к необходимости расчета 625 и 10000 обратных задач соответственно. Общая задача решалась в параллельном режиме. Для проведения расчетов использовался вычислительный комплекс К100 (ИПМ им.М.В.Келдыша РАН). При организации интерфейса для управления параллельным расчетом использовалась технология MPI [8]. В результате расчетов был получен 4-мерный массив результатов V ( M, Re, Pr, Sh ). К полученному массиву было применено логарифмическое преобразование по координатному направлению Re и проведено сравнение дисперсий по координатным направлениям. Оценка дисперсий по направлениям показала, что дисперсия по направлению lg Re существенно меньше дисперсий по остальным направлениям. Построение и анализ трехмерных проекций исходного 4-мерного массива данных подтвердило этот результат. На рис. представлена зависимость V * ( M, Re, Pr ) в виде изоповерхностей.

Это позволило понизить размерность и рассматривать уже трехмерный массив V * ( M, Pr, Sh ) в виде изоповерхностей.

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

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

2 с использованием приемов понижения размерности и визуального представления.

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

[1] Esbensen K. Multivariate Data Analysis – in Practice. 5-th Edition, 2002, CAMO Process AS, Oslo, Norway.

[2] A. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, LNCSE 58, Springer, Berlin – Heidelberg – New York, 2007.

[3] Ким Дж., Мюллер Ч. и др. Факторный, дискриминантный и кластерный анализ.

М.: Финансы и статистика, 1989. – 216 с.

[4] Бондарев А.Е. Оптимизационный анализ нестационарных пространственновременных структур с применением методов визуализации / научный электронный журнал «Научная визуализация», Национальный Исследовательский Ядерный Университет "МИФИ", М., 2011, Т.3, N 2, C.1-11.

[5] Бондарев А.Е., Галактионов В.А., Чечеткин В.М. Анализ развития концепций и методов визуального представления данных в задачах вычислительной физики / Журнал вычислительной математики и математической физики, 2011, Т. 51, N 4, С.

669–683.

[6] Бондарев А.Е., Галактионов В.А. Анализ многомерных данных в задачах многопараметрической оптимизации с применением методов визуализации / Научная визуализация. Т.4, № 2, с.1-13, 2012.

[7] Зиновьев А. Ю., Визуализация многомерных данных, Красноярск, Изд. КГТУ, 2000. 180 с.

[8] Pacheco P., Ming W. MPI User's Guide in Fortran, http://parallel.ru/ftp/mpi проектирования технологических процессов Московский институт электроники и математики «МИЭМ ВШЭ», кафедра ИТАС Построение и использование имитационных моделей при проектировании технологических процессов требует разработки и использования специальных подходов, учитывающих особенности применяемых физических явлений и реализованных на их основе технологических процессов.

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

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

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