WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

8369

УДК 62-50

МЕТОДОЛОГИЯ СТРУКТУРНОКЛАССИФИКАЦИОННОГО

ИССЛЕДОВАНИЯ СЛОЖНО

ОРГАНИЗОВАННОЙ ИНФОРМАЦИИ

В ЗАДАЧАХ ИНТЕЛЛЕКТУАЛЬНОГО

АНАЛИЗА ДАННЫХ

А.А. Дорофеюк

Институт проблем управления им. В.А. Трапезникова РАН Россия, 117997, Москва, Профсоюзная ул., 65 E-mail: adorof@ipu.ru Ю.А. Дорофеюк Институт проблем управления им. В.А. Трапезникова РАН Россия, 117997, Москва, Профсоюзная ул., 65 E-mail: dorofeyuk_julia@mail.ru Ключевые слова: структурно-классификационный подход, интеллектуальный анализ данных, структуризация объектов, группировка параметров, информативные параметры, иерархические алгоритмы распознавания образов, размытая постановка задач структурно-классификационного анализа, рекуррентные алгоритмы Аннотация: В докладе даны новые постановки задач интеллектуального анализа данных. Для решения этих задач в рамках методологии структурно-классификационного исследования сложно организованной информации разработаны новые методы и алгоритмы: снижения размерности пространства исходных параметров, позволяющие повысить эффективность алгоритмов интеллектуального анализа данных; формирования пространства информативных параметров, размерность которого существенно меньше размерности исходного пространства; интеллектуального структурного анализа объектов (кластеризации) и построения сжатого описания исследуемого множества объектов в многомерном пространстве информативных параметров для различных функционалов качества структуризации, как в детерминированной, так и в размытой постановке. На базе вариационного подхода разработаны новые рекуррентные реализации структурноклассификационных алгоритмов, проведен их теоретический анализ и компьютерное моделирование.

1. Введение В последние годы было разработано достаточно много частных алгоритмов классификационного анализа, ориентированных на решение конкретных прикладных задач [1]. В то же время для получения полного представления о функционировании сложной системы необходимо использовать достаточно универсальные методы интеллектуального анализа сложно организованных данных и распознавания образов. В работе поXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ ВСПУ- Москва 16-19 июня 2014 г.

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

Структура исходных данных. Функционирование сложной системы описывается состоянием составляющих ее элементов (объектов) и их взаимодействием. Соответственно, данные о системе представляют собой либо таблицу значений некоторых параметров, характеризующих состояние объектов, либо таблицу, отражающую взаимодействие между объектами, либо, наконец, таблицу связи между параметрами. Далее ограничимся таблицами первого типа: «объекты-параметры». Данные о системе обычно фиксируются ни в один момент времени, а многократно в течение некоторого периода (например, ежемесячно, ежеквартально или ежегодно в течение несколько лет работы системы). Характерной особенностью исследования реальных систем является невозможность получения значений всех параметров по всем объектам во все моменты времени, что приводит к пропускам в данных. Итак, исходный материал о функционировании исследуемой системы представляет собой куб данных «объекты-параметрывремя» x ij t ; i 1, n; j 1, k ; t 1, T, причем в данных возможны пропуски (здесь x ij t – значение j-го параметра на i-м объекте в t-й момент времени).

Основная цель комплексного подхода к задачам структурно-классификационного анализа состоит в выявлении наиболее общих закономерностей функционирования анализируемой системы, в том числе: структуризация набора параметров для выявления групп тесно связанных параметров; построение на базе полученной структуризации небольшого числа интегральных показателей и информативных параметров функционирования исследуемой системы [2-4]; структуризация множества объектов, для чего необходимо выделить в пространстве выбранных информативных параметров области, отражающие типовые режимы деятельности отдельных объектов системы [4, 5]; построение (аппроксимация) входо-выходных моделей функционирования исследуемой системы [6]; выявление динамических свойств исследуемой системы (например, за счет выделения характерных траекторий изменения параметров во времени) [7]; анализ фазовых характеристик (например, исследование зависимостей между параметрами с учетом временного сдвига) [1] и т.д.

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

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

ВСПУ- Москва 16-19 июня 2014 г.

2. Предобработка, структуризация параметров, выбор информативных параметров 2.1. Процедуры предобработки и фильтрации исходных данных До проведения классификационного анализа необходима предварительная обработка: статистический анализ, выявление грубых ошибок в данных, заполнение пропусков в данных и т.п. [8].

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

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

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

Опишем процедуру более подробно. На первом шаге все пропуски заполняются средними значениями каждого параметра по всей выборке. Далее проводится классификация выборки с заполненными пропусками на r0 классов, где r0 выбирается из следующих соображений. В каждом классе число объектов должно быть достаточным для статистически значимой оценки среднего значения параметра, т.е. не меньше, чем 8- n точек. Поэтому r0нач (с учетом неоднородности распределения числа точек по классам). Если в полученной классификации для некоторого класса число входящих точек будет меньше 8, то такой класс присоединяется к ближайшему классу. Некоторые из таких классов могут объединиться между собой, тогда дальнейшее их объединение не производится, если число точек в образованном классе больше или равно 8. В качестве меры близости двух классов Ai, Aj используется величина K(Ai, Aj), определяеK xl, x p, где потенциальная функция мая соотношением: K ( Ai, A j ) K ( x, y ), определяющая близость точек x и y, рассчитывается по формуле дом из полученных классов ранее заполненные пропущенные наблюдения заполняются новыми значениями. А именно, пропущенное значение i-го параметра для j-го объекта заменяется средним известных значений i-го параметра для всех объектов из l-го класса (к которому принадлежит j-ый объект). Такое заполнение производится для всех значений параметров, пропущенных в исходной выборке. На втором шаге происходит точно такая же процедура для матрицы данных, полученной после первого шага. Процедура заканчивается на шаге, на котором классификация точек осталась неизменной относительно предыдущего шага.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

2.2. Структуризация исходного набора параметров Опыт использования алгоритмов классификационного анализа показывает, что классификация по всем исходным параметрам не всегда приводит к желаемым результатам [1]. Действительно, при сравнительно небольших выборках экспериментальных наблюдений и наличии помех (ошибки в определении значений параметров, сознательное искажение информации и т.д.) использование для классификации большого числа входных параметров приводит к сильному «перемешиванию» классов, а сами классы при этом плохо поддаются интерпретации. По этой причине классификацию целесообразно проводить не в исходном пространстве, а в пространстве наиболее существенных (информативных) параметров, имеющем значительно меньшую размерность [8]. Таким образом, классификационный анализ целесообразно начинать со структуризации (группировки) набора исходных параметров.

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

Пусть множество параметров (случайных величин) x(1),…, x(k) разбито на непересекающиеся группы A1, …, As и заданы случайные величины f1, …, fs, такие, что f j2 =1, j=1s, которые будем называть факторами. В качестве меры близости параметров (случайных величин) x и y будем использовать коэффициент корреляции, который в нормированном случае совпадает с коэффициентом ковариации x, y x, y. Введем в рассмотрение функционал [3]:

Разработан алгоритм максимизации этого функционала как по разбиению параметров на группы Aj, так и по выбору факторов fj, j=1s [2].

Максимизация функционала (1) соответствует интуитивному представлению о «хорошем» разбиении параметров, когда в одну группу попадают наиболее «близкие»

между собой параметры. Действительно, при максимизации функционала (1) для каждого фиксированного набора факторов fj, j=1s в j-ую группу будут попадать такие параметры, которые наиболее близки, в определенном выше смысле, к величине fj. В то же время, среди всех возможных наборов факторов (случайных величин) fj, j=1s будет отбираться такой набор, в котором каждая из величин fj была бы в среднем наиболее близка ко всем параметрам из своей группы.

Если заданы группы параметров A1, …, As, то максимум функционала J* может быть получен, если в качестве факторов выбрать такой набор случайных величин f1, …, fs, чтобы каждая из них удовлетворяла условию Фактор fj, удовлетворяющий условию (2) при фиксированном множестве параметров, входящих в группу Aj, находится по формуле

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

вующего ее наибольшему собственному значению.

С другой стороны, если величины f1, …, fs заданы, то разбиение параметров на группы A1, …, As, обеспечивающее максимум функционала J* должно удовлетворять условию: для каждого x (i ) A j так как в противном случае функционал J * можно увеличить, «перебросив» параметр x(i) из группы Aj в ту группу Aq, для которой соотношение (4) не выполнено. Соотношения (2) и (4) в совокупности являются необходимыми условиями максимума функционала J*.

Для одновременного определения групп A1, …, As и факторов f1, …, fs, удовлетворяющих этим условиям, был разработан алгоритм локальной оптимизации, который работает следующим образом [4].

Пусть на p-ом шаге итерации построено разбиение параметров на группы A1(p), …, As(p). Для каждой такой группы параметров по формуле (3) строят факторы fj(p), j=1s и новое, (p+1)-ое, разбиение параметров на группы A1(p+1), …, As(p+1) в соответствии с правилом: параметр x(i) относится к группе Aj(p+1), если выполнено (4) для p-го шага, то есть (5) В том случае, когда существуют два или более факторов и такой параметр x(i), что для этих факторов и этого параметра в (5) имеет место равенство, параметр x(i), относится к группе с наименьшим номером.

Доказана теорема о сходимости этого алгоритма к локальному максимуму функционала J* за конечное число шагов (итераций).

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

(6) где ni – число параметров, отнесенных к фоновой группе A0, k – общее число исходного набора параметров, константа B – «цена» отнесения параметров к фоновой группе (чем больше B, тем больше параметров попадает в фоновую группу).

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

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

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

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

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

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

3. Структурно-классификационный анализ исходного 3.1. Формальная постановка задачи, конечная выборка Формальная постановка задачи классификационного анализа, в рамках используемого вариационного подхода [10], базируется на трех основных категориях: классифицируемое множество объектов, класс допустимых классификаций и критерий качества классификации (разбиения).

Классифицируемое множество объектов. Как и ранее будем предполагать, что исходные данные представлены (возможно с пропусками) в виде куба данных «объектыпараметры-время» x ij t ; i 1, n; j 1, k ; t 1, T. Для статических задач кластеризаx ij ; i 1, n; j 1, k, ции используется только матрица данных «объекты-параметры»

где x ij – значение j-го параметра для i-го объекта xi ( x 1i,..., x ki ), то есть исследуемые объекты могут быть представлены как точки в k-мерном евклидовом пространстве исходных параметров Rk.

Вначале, в качестве классифицируемого множества рассмотрим конечное множество n объектов (k-мерных векторов), т.е. необходимо классифицировать множество X x1,..., xn. В этом случае удается избежать рассмотрения громоздких формул, которые появляются, в основном, из-за того, что функция распределения вероятностей появления объектов в бесконечной выборке имеет весьма сложный вид и априори неизвестен даже ее параметрический класс. Именно поэтому в случае конечной выборки удается проследить основную идею выбора функционала качества структуризации, отвечающего интуитивным представлениям о «хорошей классификации», а также оцеXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ нить специфику «работы» выбранного математического инструментария для разработки алгоритмов структурно-классификационного анализа, в особенности для постановок задач размытой классификации.

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

Класс допустимых классификаций. Размытой классификацией множества X x1,..., xn на r классов называется такая r-мерная вектор-функция H x h1 x,..., hr x (hi(x) – функция принадлежности x к i-му классу), что для любого x значение H(x) принадлежит некоторому подмножеству V единичного симплекса Подмножество V отражает, во-первых, естественное предположение о том, что сумма функций принадлежностей объекта ко всем классам равна единице, а во-вторых, дает возможность ввести дополнительные ограничения hi(x) для конкретной задачи.

Для решения прикладных, слабо формализованных задач, помимо «обычных»

классов, часто вводят в рассмотрение так называемый фоновый класс h0(x) (нулевой класс, джокер-класс, класс «мусора» и др.). В этом случае условие нормировки выгляr дит следующим образом фонового класса абсолютно не влияет на выбор и результаты использования математического инструментария исследования. По этой причине, для того, чтобы не делать формальные выкладки более громоздкими, далее рассматривается постановка задачи размытой классификации без фонового класса.

Критерий качества классификации. Критерий качества классификации строится следующим образом:

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

(7) где h – монотонно возрастающая функция, отображающая отрезок [0,1] на себя, причем 0 0 и 1 1 ; A – вектор эталонов классов A 1,..., r, причем эталон iго класса i определяется как решение следующей оптимизационной задачи:

(8) Заметим, что для постановки задачи с фоновым классом функционал (7) принимает вид (9) где константа B – «вес» фонового класса. Критерий качества классификации (9) позволяет хорошо фильтровать случайные неполяризованные помехи (типа белого шума), необъяснимые «выбросы» значений исходных параметров, «проскочившие» фильтры

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

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

Задача классификационного анализа состоит в максимизации критерия (7) по вектор-функции H x h1 x,..., hr x и по вектору эталонов классов A 1,..., r, i.

Функция h и множество V характеризуют тип размытости оптимальной классификации, то есть за счет выбора функции h можно рассматривать либо детерминированную, либо размытую (с различными типами размытости) постановку задачи классификационного анализа. Такая постановка является достаточно универсальной, она весьма удобна для решения прикладных, слабо формализованных задач, когда, варьируя свободные параметры алгоритма, разработанного в рамках такой постановки, удается выбрать адекватный этой задаче вариант размытости. Именно поэтому в приложениях функция h задается параметрически, например, в виде h h t, t 1. Такая функция h совместно с V I r соответствует, в частности, размытому варианту алгоритма кластерного анализа ISODATA [11].

Будем рассматривать V I r и следующие три варианта функции h :

1) 1 h h, легко доказать, что этот случай соответствует детерминированной постановке задачи, то есть оптимальная классификация будет четкой;

2) 2 h ht, t 1, было доказано, что этот случай соответствует собственно размытой постановке задачи, то есть оптимальная классификация будет реально размытой (каждый объект x с некоторым весом hi(x)0 будет принадлежать каждому i-му классу);

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

Одним из базовых понятий разработанного комплексного подхода к структурноклассификационному анализу сложно организованных данных является понятие опорной классификации [10]. Классификация HF для линейного функционала F(H) называется опорной, если:

(10) Для случаев, когда функционал качества классификации (например, (7)) дифференцируем, а функционал F(H) определяется вектором эталонов классов A 1,..., r, опорная классификация (10) называется эталонной. Другими словами классификация H A x называется эталонной для заданного вектора эталонов классов A 1,..., r, если (11) Была доказана следующая теорема:

Теорема 1. Оптимальная для (7) классификация является эталонной.

Следствие: Вид функционала (7) определяет класс решающих правил оптимальной эталонной классификации.

Пусть задан вектор эталонов классов A 1,..., r. Было установлено, что эталонная классификация (11) для каждого из 3-х вариантов функции j h определяется следующим образом:

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

(13) Для каждого объекта x и эталона каждого класса i подсчитываются числа Введем обозначение:

Обозначим через r число классов, для которых sign(vi(1) ) 1. Затем подсчитываются числа:

По ним определяются функции принадлежностей для этого случая:

(14) Таким образом, для любого вектора эталонов A 1,..., r можно определить эталонную классификацию H A x h1A x,..., hrA x для всех рассматриваемых типов функции j h (12-14).

3.2. Итерационный алгоритм структурно-классификационного анализа Теорема 1 и следствие из нее позволяют разработать итерационный алгоритм максимизации функционала (7), основанный на его поочередной оптимизации по классификации (при фиксированном векторе эталонов классов) и по эталонам классов (при фиксированной классификации), который состоит из двух последовательных шагов:

на первом шаге по данному решающему правилу – вектору эталонов A1 1,..., r находится соответствующая эталонная классификация H A1 x h1A1 x,..., hrA1 x ;

на втором шаге находится градиент функционала (7) в точке, соответствующей этой эталонной классификации, то есть определяется новый вектор эталонов A2 1,..., r. Далее цикл повторяется.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

Рассмотрим алгоритм более подробно. Пусть задан некоторый начальный вектор A0, то есть начальная классификация H0. Далее алгоритм строится итерационно.

На l-ом шаге, в соответствии с алгоритмом, по вектору эталонов Al строится эталонная классификация H Al. Затем находится градиент функционала (7) в точке H Al, по которому строится вектор эталонов Al+1.

На (l+1)-ом шаге по вектору эталонов Al+1 строится эталонная классификация. Затем находится градиент функционала (7) в точке H Al1, по которому строится вектор эталонов Al+2.

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

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

(15) Из (15) и формулы (8) непосредственно следует, что для фиксированной классификации оптимальные эталоны классов будут совпадать с центрами классов:

(16) Градиентом функционала (15), в точке H является вектор-функция:

(17) т.е. решающая функция fi(x) в оптимальной классификации соответствует мере близости (расстоянию со знаком «–») точки x к эталону (в этом случае – центру) i-го класса.

Заметим, что множество D(J2) всех допустимых градиентов критерия (15) состоит из функционалов вида (17). Таким образом, в описанном алгоритме максимизации критерия (7) для случая (15) можно ограничиться решающими функциями (компоненты градиента критерия качества классификации), задаваемыми через эталоны i по формуле (17).

Постановка задачи. В качестве классифицируемого множества далее будет рассматриваться произвольное множество объектов X, – точек k-мерного евклидова пространства Rk, с заданной на нем вероятностной мерой (законом распределения вероятностей появления объектов выборки) P(x), xX. Далее рассматривается размытая постановка задачи структурно-классификационного анализа, то есть, как и ранее, структура (классификация) задается вектор-функцией H(x)=(h1(x),…,hr(x)), где hi(x) – функция принадлежности x к i-му классу, r – число классов. Функция H(x) удовлетворяет следующим условиям: H(*)L2(X,P) и для любого x значение H(x) принадлежит некоторому ограниченному множеству V пространства значений вектор-функции H(x), т.е.

H(x)V Rk. Будем рассматривать класс критериев качества классификации метода обобщенного среднего (7), который для случая бесконечной выборки имеет вид:

(18)

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

2 H pi, M i i 1,..., r, j 1,..., mr, где pi и M i – вероятность (нулевой момент) и j-ые ненормированные моменты i-го класса соответственно. Этот критерий является важным частным случаем (18), охватывающий многие критерии, используемые при решении прикладных задач. Для того, чтобы рассматривать только первые ненормированные моменты классов, введем в рассмотрение вектор-функцию z(x) (z: XZ=Rk).

Пространство Z называют спрямляющим пространством [3], так как в нем все рассматриваемые моменты являются первыми. Предполагается, что выполняются следующие два очевидных ограничения: 1) множество X ограничено по мере P; 2) мера точек z, сосредоточенных на любой плоскости пространства Rk равно 0.

Рассмотрим первые ненормированные моменты и вероятности классов (нулевые моменты):

(19) Обозначим через H pi, M i i 1,..., r r(k+1)-мерный вектор, составленный из вероятностей (нулевых моментов) и первых ненормированных моментов классов. Тогда критерий Ф2(H) для спрямляющего пространства Z имеет следующий вид:

где – выпуклая функция от r(k+1)-мерного вектора (H).

Вид оптимальной классификации. Пусть задан r(k+1)-мерный вектор =(di,ci; i=1,…, r), где diR1, ciRk. Назовем линейной с вектором коэффициентов классификация (функционал) H (x) является опорной размытой классификацией для частного вида линейного функционала F(H). Кроме того, из (11) следует, что H (x) является эталонной классификацией с вектором эталонов H pi, M i i 1,..., r.

Доказана следующая лемма о виде оптимальной классификации для критерия (20).

Лемма 1. Если – субградиент функции в точке (H), то ((H )) ((H)), т.е.

оптимальная для (20) классификация является линейной.

Рекуррентный алгоритм классификации для бесконечной выборки. Обозначим через S={x1,…,xn,…} бесконечную выборку объектов, появляющихся независимо в соответствии с, вообще говоря, неизвестным законом распределения P(x).

На каждом шаге алгоритма по конечной подвыборке объектов Sn={x1,…,xn} для классификации H(x)=(h1(x),…,hr(x)), построенной к этому шагу, строятся оценки ненормированных моментов и вероятностей классов:

(21) Обозначим через (H) r(k+1)-мерный вектор частот и оценок моментов классов.

Лемма 2. Для любых 0 и 0 с вероятностью большей 1 – одновременно для всех классификаций H выборки Sn выполняется где – субградиент в точке (H), а D –константа.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

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

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

где n – субградиент функции в точке n.

Доказана следующая теорема о достаточных условиях сходимости алгоритма (22) к классификации, обеспечивающей стационарное значение критерия (20):

Теорема 2. Если все субградиенты функции ограничены, то в силу алгоритма (22) с вероятностью единица справедливо: 1) lim 2 H n lim 2 n =C(S), где C(S) – константа, зависящая от выборки S, являющаяся односторонне-стационарным значением функции ; 2) если, кроме того, – дважды непрерывно дифференцируемая функция, то C(S) – стационарное значение функции и любая предельная точка последовательности {n} является стационарной. При доказательстве Теоремы 2 существенно используются Леммы 1 и 2.

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

Работа выполнена при частичной финансовой поддержке РФФИ, гранты 14-07а, 13-07-00992-а.

1. Дорофеюк А.А. Методология экспертно-классификационного анализа в задачах управления и обработки сложноорганизованных данных (история и перспективы развития) // Проблемы управления.

2009. № 3.1. С. 19-28.

2. Дорофеюк А.А., Дорофеюк Ю.А. Экспертно-классификационные методы анализа сложно организованных данных в задачах управления слабо формализованными системами. Пленарный доклад. // Управление развитием крупномасштабных систем MLSD '2011: Программа и пленарные доклады Пятой Международной конференции. М.: ИПУ РАН, 2011. С. 72-81.

3. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 4. Киселева Н.Е., Дорофеюк А.А., Дорофеюк Ю.А. Размытый алгоритм m-локальной оптимизации в задачах кластер-анализа объектов и группировки параметров // Интеллектуализация обработки информации: 9-я Международная конференция. Черногория, г. Будва, 2012 г.: Сборник докладов. М.:

Торус Пресс, 2012. С. 118-121.

5. Дорофеюк А.А., Бауман Е.В., Дорофеюк Ю.А. Методы интеллектуальной обработки информации на базе алгоритмов стохастической аппроксимации. Пленарный доклад // Математические методы распознавания образов. 15-я Международная конференция: Сборник докладов. М.: МАКС ПРЕСС, 2011.

С. 108-113.

6. Дорофеюк А.А., Дорофеюк Ю.А. Методы структурной идентификации модели функционирования сложных объектов управления. Пленарный доклад. // Управление развитием крупномасштабных систем MLSD '2012: Материалы Шестой Международной конференции. Т. 1. М.: ИПУ РАН, 2012. С.

7. Гольдовская М.Д., Дорофеюк Ю.А., Киселева Н.Е. Методы структурного анализа в прикладных задачах исследования временных рядов // Проблемы управления. 2013. № 3. С. 33-41.

8. Дорофеюк Ю.А., Киселева Н.Е., Покровская И.В. Комплекс алгоритмов интеллектуального анализа данных для исследования функционирования сложных систем // Управление развитием крупномасштабных систем MLSD '2013: Труды Седьмой международной конференции. М.: ИПУ РАН, 2013. С.

220-234.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ

9. Дорофеюк А.А., Дорофеюк Ю.А., Покровская И.В., Чернявский А.Л. Интеллектуальные модели и методы экспертизы, экспертного анализа и прогнозирования в слабо формализованных системах управления. Пленарный доклад // Интеллектуализация обработки информации: 9-я Международная конференция. Черногория, г. Будва, 2012 г.: Сборник докладов. М.: Торус Пресс, 2012. С. 102-105.

10. Бауман Е.В., Дорофеюк А.А. Классификационный анализ данных / Избранные труды Международной конференции по проблемам управления. М.: СИНТЕГ, 1999. Т. 1. С. 62-77.

11. Advances in Fuzzy Clustering and its Applications / Edited by W. Pedrycz, J. Valente de Oliveira. New York: Wiley, 2007. 454 p.

XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ





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

«Отчет о деятельности Министерства информатизации и связи Республики Татарстан в 2011 году 18 Итоги 2011 года. Задачи на 2012 год. | Министерство информатизации и связи Республики Татарстан Нормативно-правовые документы, разработанные Министерством информатизации и связи Республики Татарстан в 2011 году Постановление Кабинета Министров Республики Татарстан от 19.01.2011 №21 О Плане перехода на предоставление государственных, муниципальных и социально значимых услуг в электронном виде в...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.И. ЛОБАЧЕВСКОГО В.Е. АЛЕКСЕЕВ, В.А. ТАЛАНОВ ГРАФЫ. МОДЕЛИ ВЫЧИСЛЕНИЙ. СТРУКТУРЫ ДАННЫХ Учебник Нижний Новгород Издательство Нижегородского госуниверситета 2004 1 Предисловие В этой книге под одной обложкой собраны учебные тексты, по внешности разнородные, но относящиеся к одной сравнительно молодой области человеческой деятельности. Это деятельность по созданию и исследованию алгоритмов, для которой...»

«Книга Секреты исцеляющих программ Практическое руководство по аудиотрансу, самогипнозу, гипнотерапии Издание второе, переработанное и дополненное Эдуард Михайлович Каструбин СЕКРЕТЫ ИСЦЕЛЯЮЩИХ ПРОГРАММ Практическое руководство по аудиотрансу, самогипнозу, гипнотерапии. Издание второе, переработанное и дополненное. - М.: Деловой мир 2000, 2004. - 352с. ISBN 5-93681-006-2 Секреты исцеляющих программ сочетают в себе достижения современной гипнотерапии с уникальными знаниями древних цивилизаций...»

«Мультиварка-скороварка RMC-PM4507 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ УВАЖАЕМЫЙ ПОКУПАТЕЛЬ! Благодарим вас за то, что вы отдали предпочтение бытовой технике от компании REDMOND. REDMOND — это новейшие разработки, качество, надежность и внимательное отношение к нашим покупателям. Надеемся, что и в будущем вы будете выбирать изделия нашей компании. Мультиварка-скороварка REDMOND RMC-PM4507 — современ- нии его приготовления. Также успешно REDMOND RMC-PM4507 ное многофункциональное устройство, призванное...»

«Серия ЕстЕствЕнныЕ науки № 1 (5) Издается с 2008 года Выходит 2 раза в год Москва 2010 Scientific Journal natural ScienceS № 1 (5) Published since 2008 Appears Twice a Year Moscow 2010 редакционный совет: Рябов В.В. ректор МГПУ, доктор исторических наук, профессор Председатель Атанасян С.Л. проректор по учебной работе МГПУ, кандидат физико-математических наук, профессор Геворкян Е.Н. проректор по научной работе МГПУ, доктор экономических наук, профессор Русецкая М.Н. проректор по инновационной...»

«Лихошвай Виталий Александрович Математическое моделирование и компьютерный анализ генных сетей 03.00.28 – биоинформатика Диссертация на соискание ученой степени доктора биологических наук Научный консультант Чл.-кор. РАН, д.б.н, проф. Колчанов Н.А. Новосибирск, 2008 Актуальность вытекает из потребностей систематизации и теоретического осмысления накопленных экспериментальных данных о закономерностях функционирования живых систем под управлением генетических программ, а также из современных...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ УТВЕРЖДАЮ Заместитель Министра образования Российской Федерации В.Д.Шадриков 23.03.2000г. Номер государственной регистрации 200ен/бак_ ГОСУДАРСТВЕННЫЙ ОБРАЗОВАТЕЛЬНЫЙ СТАНДАРТ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Направление 510200 Прикладная математика и информатика Степень — бакалавр прикладной математики и информатики Вводится с момента утверждения Москва 2000. 1. ОБЩАЯ ХАРАКТЕРИСТИКА НАПРАВЛЕНИЯ 510200 - ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА 1.1....»

«Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт Н.М. Чепурнова Муниципальное право Российской Федерации Учебно-практическое пособие Москва 2007 1 Муниципальное право Российской Федерации УДК 342.9 ББК 67.401 Ч 446 Автор Чепурнова Наталья Михайловна, доктор юридических наук, профессор Чепурнова Н.М. Ч 446 МУНИЦИПАЛЬНОЕ ПРАВО РОССИЙСКОЙ ФЕДЕРАЦИИ: Учебнопрактическое пособие/Евразийский...»

«Стр 1 из 198 7 апреля 2013 г. Форма 4 заполняется на каждую образовательную программу Сведения об обеспеченности образовательного процесса учебной литературой по блоку общепрофессиональных и специальных дисциплин Иркутский государственный технический университет 120101 Прикладная геодезия Наименование дисциплин, входящих в Количество заявленную образовательную программу обучающихся, Автор, название, место издания, издательство, год издания учебной литературы, № п/п Количество (семестр, в...»

«КОНЦЕПЦИЯ ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА РЕСПУБЛИКИ КАЗАХСТАН г. Астана 2004 г 2 СОДЕРЖАНИЕ 1. ВВЕДЕНИЕ 2. ОСНОВНЫЕ ПОНЯТИЯ И СОКРАЩЕНИЯ 3. ЦЕЛИ И ЗАДАЧИ ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА 4. ТЕКУЩЕЕ СОСТОЯНИЕ ИНФОРМАТИЗАЦИИ ГОСУДАРСТВЕННЫХ ОРГАНОВ 5 5. НЕОБХОДИМЫЕ УСЛОВИЯ РЕАЛИЗАЦИИ ИНФРАСТРУКТУРЫ ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА 5.1. Правовая готовность 5.2. Информационная готовность госорганов 5.3. Технологическая готовность 5.4. Социальная готовность 6. АРХИТЕКТУРА ЭЛЕКТРОННОГО ПРАВИТЕЛЬСТВА 7. ОТНОШЕНИЯ...»

«Министерство образования и науки Российской Федерации Амурский государственный университет УТВЕРЖДАЮ Зав. кафедрой ОМиИ _Г.В. Литовка _2012 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ МАТЕМАТИКА И ИНФОРМАТИКА для направления подготовки 031100.62 – Лингвистика Составитель: О.А. Лебедь, старший преподаватель Благовещенск, 2012 Печатается по решению редакционно-издательского совета факультета математики и информатики Амурского государственного университета О.А. Лебедь Учебно-методический...»

«Министерство связи и информатизации Республики Беларусь Научно-инженерное республиканское унитарное предприятие Институт прикладных программных систем (НИРУП ИППС) ГОСУДАРСТВЕННЫЕ РЕГИСТРЫ ИНФОРМАЦИОННЫХ РЕСУРСОВ И ИНФОРМАЦИОННЫХ СИСТЕМ РЕСПУБЛИКИ БЕЛАРУСЬ ИНФОРМАЦИОННЫЕ РЕСУРСЫ И СИСТЕМЫ БЕЛАРУСИ КАТАЛОГ Выпуск 9 Минск Адукацыя i выхаванне 2010 1 УДК 002(085)(476)(035.5) ББК 32.81я И Рекомендовано к изданию постановлением коллегии Министерства связи и информатизации Республики Беларусь от...»

«Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский университет Высшая школа экономики Факультет бизнес-информатики Программа дисциплины Алгебра для направления 231000.62 Программная инженерия подготовки бакалавра Авторы программы: А.П. Иванов, к.ф.-м.н., ординарный профессор, IvanovAP@hse.perm.ru А.В. Морозова, ст. преподаватель, MorozovaAV@hse.perm.ru Одобрена на заседании...»

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

«Образовательная деятельность ОБРАЗОВАТЕЛЬНАЯ ДЕЯТЕЛЬНОСТЬ Лицензирование образовательной деятельности На протяжении 2010 г. университет продолжил реализацию стратегии по расширению спектра реализуемых образовательных программ засчет лицензирования новых специальностей и направлений подготовки по ГОС ВПО второго поколения (получена лицензия по 5 направлениям подготовки бакалавров – 010400.62 Информационные технологии, 071400.62 Социально-культурная деятельность, 040200.62 Социология, 220600.62...»

«:гентство овязи Федора_ттьное € еверо -1{авказский филиа_тт государственного образовательного бтодкетного г{рех(дения федера-тльного вь1с1пего профоссионального образования ]!1осковского технического университота связи и информатики смк_о-1.02-01-14 скФ мтуси смк_о_1.02-01'!4 Фтчёт о самообследовании утввРкдА!о мтуси Аир9крр скФ мецко отчвт самообследовании скФ мтуси смк_о_1.02-0|- Берсия 1. Ростов-на-Аону ]- / Фамшлия/|1одппсь Аата.(олэкность [.[1.Беленький щ }Р ?а/4а. €оставил }ам....»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра общей математики и информатики УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ ЭКОНОМЕТРИКА Основной образовательной программы по направлению подготовки 080100.62 – Экономика Благовещенск 2013 2 УМКД разработан старшим преподавателем кафедры ОМиИ Киселевой Аленой Николаевной Рассмотрен и рекомендован на...»

«Высшее образование БАКАЛАВРИАТ ИНТЕГРИРОВАННЫЕ КОММУНИКАЦИИ Учебник Под редакцией О. В. САГИНОВОй Для студентов учреждений высшего образования, обучающихся по направлению подготовки Реклама и связи с общественностью УДК 659(075.8) ББК 65.290-2я73 И73 Р е ц е н з е н т ы: директор Института менеджмента, зав. кафедрой маркетинга и коммерции Московского государственного университета экономики, статистики и информатики, д-р экон. наук, проф. Л. А. Данченок;...»

«МАТЕМАТИЧЕСКАЯ БИОЛОГИЯ И БИОИНФОРМАТИКА, 2006, том 1, №1, с.70-96, http://www.matbio.org/downloads/Kozlov2006(1_70) .pdf =================================БИОИНФОРМАТИКА============================== УДК 577.21 Математический анализ генетических кодов ©2006 Козлов Н.Н. ИПМ им. М.В.Келдыша РАН Обзор завершенного цикла исследований по математическому анализу взаимосвязи структуры генетического кода и необычных способов записи генетической информации - так называемых перекрывающихся генов, когда...»

«5 марта 2008 года N 205-ПК ПЕРМСКИЙ КРАЙ ЗАКОН О БИБЛИОТЕЧНОМ ДЕЛЕ В ПЕРМСКОМ КРАЕ Принят Законодательным Собранием Пермского края 21 февраля 2008 года Настоящий Закон является правовой основой организации, сохранения и развития библиотечного дела в Пермском крае, устанавливает принципы деятельности библиотек, гарантирующие права человека на свободный доступ к информации, духовное развитие, приобщение к ценностям национальной и мировой культуры, а также на культурную, научную, образовательную и...»














 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.