Содержание к диссертации
Введение
ГЛАВА I. Аналитический обзор методов анализа структуры взаимосвязей между компонентами многомерного случайного признака . 14
1.1. Метод В-коэффициентов 14
1.2. Два алгоритма экстремальной группировки признаков 18
Первый алгоритм экстремальной группировки 19
Второй алгоритм экстремальной группировки 20
1.3. Алгоритм Лумельского 23
1.4. Метод корреляционных плеяд 25
1.5. Деревья зависимостей 27
Прямые и опосредованные связи 28
1.6. Метод Чоу 30
Качество оценок 31
1.7. Метод Демпстера 33
Итерационная процедура алгоритма Демпстера 36
1.8. Теоретико -информационный подход к структуре случайной величины 39
Энтропия и информация случайной величины 39
Алгоритм определения жесткой структуры 41
Алгоритм приближенного определения жесткой структуры, коэффициент информативности 44
Энтропия и информация в случае нормального распределения 45
Выводы и результаты первой главы 48
ГЛАВА II. Программно-алгоритмическая реализация методов анализа структуры взаимосвязей между компонентами многомерного нормального вектора 49
II. 1. Выбор инструментальных средств 49
Хранение данных 49
Клиентское приложение 51
II.2. Структура базы данных
11.3. Библиотека матричных вычислений 58
11.4. Генерирование псевдослучайных нормально распределенных чисел с заданной ковариационной матрицей 63
Выводы и результаты второй главы 65
ГЛАВА III. Сравнительный анализ эффективности методов группировки признаков и выявления структуры связей. вычислительные эксперименты и практическое применение методов в исследованиях качества и образа жизни населения территорий 66
ПІЛ. Исследование эффективности алгоритмов группировки признаков и выявления структуры связей с помощью вычислительных экспериментов 66
III. 1.1. Анализ эффективности алгоритмов группировки признаков. 66
III. 1.2. Анализ эффективности методов выявления структуры связей многомерного случайного признака 77
Ш.2. Применение алгоритмов группировки признаков и выявления структуры связей в межрегиональных и межстрановых исследованиях 90
Ш.2.1. Эконометрический анализ синтетических категорий качества жизни населения субъектов РФ 90
Ш.2.2. Межстрановые исследования качества жизни населения 109
Выводы и результаты третьей главы 112
Заключение 113
Список литературы
- Два алгоритма экстремальной группировки признаков
- -информационный подход к структуре случайной величины
- Библиотека матричных вычислений
- Анализ эффективности методов выявления структуры связей многомерного случайного признака
Введение к работе
При изучении сложных объектов, характеризующихся большим количеством признаков (переменных) перед исследователем неизбежно встает проблема обработки исходных экспериментальных данных и их структурного анализа. Часто этот процесс сопряжен со значительными трудностями, и вполне естественным и логичным является желание сократить описание измеряемой информации с целью получения легко интерпретируемых результатов. Решение последней задачи осложнено тем, что, как правило, измеряемые признаки лишь косвенно отражают существенные факторы, характеризующие исследуемые объекты, так что возникает необходимость в разработке специальных методов для извлечения требуемой информации об этих факторах.
Например, в экономических исследованиях качества и образа жизни населения территорий измеряемыми признаками являются различные статистически регистрируемые показатели: ВВП на душу населения, уровень инфляции, среднедушевой доход, неграмотность, количество тяжких преступлений и др. Существенными же факторами являются такие синтетические категории, как «качество жизни», «уровень благосостояния», «качество социальной сферы», «качество населения», «качество экологической ниши» и др. В процессе изучения химических реакторов может быть измерена температура и давление в различных точках, расходы реагентов и т. п., тогда как существенными факторами, характеризующими состояние реактора, являются качество катализатора, интенсивность массообмена, граница жидкой и паровой фаз и т. д. В психологии измеряемыми признаками являются реакции людей на различные тесты, а существенными факторами - такие непосредственно не измеряемые характеристики субъекта, как «степень интеллектуальности», «работоспособность», «тип нервной системы» и т. д. В социологических исследованиях измеряемыми признаками являются ответы на различные вопросы анкет или реакции людей в условиях социологических
экспериментов, а существенным фактором - отношение людей к той или иной социальной или демографической группе.
В этих и других многочисленных примерах такого рода количество измеряемых признаков несоизмеримо больше числа существенных факторов и задача, прежде всего, заключается в том, чтобы выявить эти факторы. Когда такие факторы выявлены, естественно возникает задача сокращения числа измеряемых признаков (число показателей, определяющих качество жизни, число тестов в психологических исследованиях, число вопросов в социологических исследованиях и т. д.), при котором не теряется информация, нужная для определения существенных факторов.
Решение обеих указанных выше задач может опираться на следующее обстоятельство, как правило, имеющее место в приложениях, примеры которых были ранее приведены. В этих приложениях изменение какого-либо фактора сказывается неодинаково на всех измеряемых величинах, и поэтому среди измеряемых величин могут быть выделены группы, наиболее сильно реагирующие в отдельности на каждый из факторов.
Из сказанного вытекает следующее естественное предположение: измеряемые признаки наиболее сильно коррелируют друг с другом в том случае, когда они наиболее сильно зависят от одного и того же фактора. Приняв это предположение как исходную гипотезу, можно строить разбиение всех измеряемых признаков на такие непересекающиеся группы, что признаки, принадлежащие одной группе, в некотором смысле сильно коррелируют между собой, а признаки, принадлежащие разным группам, коррелированы относительно слабо. Задача такого рода называется задачей группировки признаков [Браверман (1970)], и может иметь как самостоятельное, так и вспомогательное значение. (Задача о выявлении факторов без группировки признаков, либо в условиях, когда эта группировка предопределена заранее, решается методами факторного анализа).
В упоминавшемся выше примере исследования качества и образа жизни населения задача группировки признаков имеет самостоятельное значение. В
7 этом случае набор переменных разбивается на непересекающиеся группы таким образом, чтобы первая группа хорошо характеризовала качество населения, вторая - уровень благосостояния и т.д.
Приведем примеры, в которых задача группировки признаков возникает как вспомогательная.
Некоторые методы факторного анализа, например би-факторный метод К. Холзингера [Харман (1972)], требуют предварительного разбиения признаков на группы с сильной внутренней связью. Как правило, это делается неформально исследователем-специалистом в данной области.
В задаче автоматической классификации (распознавание образов без обучения) часто бывает необходимо проводить классификацию в подпространствах разных групп признаков, каждая из которых характеризует какую-либо одну сторону объекта. Поэтому предварительно необходимо из всего имеющегося набора тестов выделить данные группы.
В качестве еще одного примера можно привести задачу построения интегрального латентного показателя качества сложной системы в том случае, когда в составе исследуемого набора частных показателей имеется определенное количество взаимно слабо коррелированных переменных, хотя каждая из них вносит существенный вклад в описание и интерпретацию анализируемого интегрального показателя. В этой ситуации аппроксимация всех исследуемых признаков по значению единственного скалярного индикатора может не давать удовлетворительного результата, и одним из способов решения задачи является разбиение исходного набора переменных на группы и построение интегрального показателя для каждой из групп [Айвазян (2003а)].
Известны несколько различных эвристических алгоритмов решения задачи группировки признаков. Большинство из них используют в качестве матрицы меры связи между переменными матрицу корреляций или ковариаций. Здесь мы дадим краткое описание алгоритмов на уровне идеи, более подробные сведения изложены в первой главе данной работы.
Метод ^-коэффициентов основывается на последовательном формировании групп посредством вычисления так называемого В-коэффициента (коэффициента принадлежности, определяемого как отношение среднего коэффициентов корреляции между признаками текущей группы к среднему коэффициентов корреляции признаков текущей группы со всеми остальными), и отслеживания момента резкого уменьшения значения указанного коэффициента [Харман (1972), с. 132-135].
Метод экстремальной группировки признаков, основан на экстремизации некоего функционала, зависящего как от способа группировки, так и от выбора скрытых факторов. Функционал выбирается таким образом, что его экстремизация (как по разбиению, так и по выбору факторов) интуитивно соответствует описанной содержательной задаче разбиения признаков на группы, также решая задачу выявления существенных факторов [Браверман (1970)].
Алгоритм Лумельского, позволяет группировать признаки на основе квадратной матрицы связей произвольной природы (например, матрицы дисперсионных отношений, ранговой корреляции и т.д.) В основе процедуры алгоритма лежит понятие меры близости между группами переменных и последовательное объединение наиболее близких групп до достижения заданного числа групп [Лумельский (1970)].
В различных версиях метода корреляционных плеяд по определенным правилам строится некоторый ненаправленный граф с вершинами, соответствующими переменным, и ребрами, соответствующими связям между переменными. На конечном шаге алгоритма, когда граф построен, задается пороговое значение коэффициента корреляции между признаками, и граф разбивается на подграфы, вершины каждого из которых соответствуют группам признаков [Айвазян, Мхитарян (2001), т.1, с. 577-580], [Лумельский (1970)].
Помимо разбиения множества исследуемых признаков на непересекающиеся группы, еще одним инструментом структурного анализа данного множества являются графы структуры зависимостей многомерной
9 случайной величины. Идея данного подхода состоит в представлении характера связей между переменными в виде ненаправленного графа, вершины которого (аналогично методу корреляционных плеяд) соответствуют признакам, а ребра - связям между ними. Однако ребрами соединяются только те вершины, которые соответствуют переменным, непосредственно связанным между собой, либо переменным, связь которых между собой статистически значима.
Графы структуры предоставляют исследователю инструмент визуального анализа, опирающийся на серьезный математический аппарат, и позволяют выявить те признаки (вершины графа), которые имеют наибольшее количество связей (ребер графа) с другими переменными, и, следовательно, играют центральную, ключевую роль в изучаемом наборе переменных. В некоторых случаях вокруг таких признаков могут образовываться выраженные группы переменных. Также граф структуры зависимостей может иметь изолированные вершины, соответствующие признакам, не связанным с остальными.
Теоретические аспекты подхода, опирающегося на графы структуры зависимостей многомерной случайной величины, подробно исследованы в работе [Гаврилец (1974), с. 117-166], в которой формализуется понятие структуры многомерной случайной величины и подробно исследуются ее свойства. В этой же работе предлагаются алгоритмы выявления графа структуры, основанные на теоретико-информационном подходе, которые будут рассмотрены в главе I.
Одной из реализаций графов структуры зависимостей являются деревья зависимостей, введенные в статистическую практику Чоу [Chow, Liu (1968)]. Предлагается представлять структуру связей между компонентами многомерного нормально распределенного признака в виде связанного графа без циклов {дерева), вершины которого, как и ранее, соответствуют переменным, а ребра - связям между ними. Весом ребра называется абсолютная величина коэффициента корреляции между признаками, которым соответствуют соединяемые данным ребром вершины графа [Айвазян, Енюков, Мешалкин (1985)]. В работе [Chow, Liu (1968)] доказывается, что задача
10 построения дерева структуры зависимостей на основании корреляционной матрицы может быть сведена к задаче построения дерева максимального веса на вершинах, соответствующих исходным признакам, которая, в свою очередь, решается с помощью алгоритма Крускала [Айвазян, Енюков, Мешалкин (1985)], [Weinberg (2005)]. Существуют модификации указанного метода для больших объемов данных [Meila (1999)].
Подход Демпстера к построению графа структуры зависимостей многомерного нормально распределенного случайного признака с нулевым вектором средних значений состоит в первоначальном предположении, что все переменные независимы, ковариационная (корреляционная) матрица имеет диагональный вид, ребра в графе отсутствуют. На каждом шаге выбирается такой из элементов выборочной ковариационной (корреляционной) матрицы, который дает наибольшее приращение оценке логарифмической функции максимального правдоподобия для этой матрицы, и строится соответствующее ребро графа. Процесс продолжается до тех пор, пока приращение на следующем шаге не станет статистически незначимым (уровень значимости задается исследователем). Построенный таким образом граф не обязательно будет представлять собой дерево [Dempster (1972)], [Weinberg (2005)].
Актуальность темы. Рассматриваемые в данной работе методы группировки признаков и выявления структуры взаимосвязей между признаками, имеют широкое применение в социально-экономических исследованиях, оперирующих большим количеством статистических показателей. На определенных этапах подобных исследований, как правило, возникает необходимость снижения количества обрабатываемой информации, ее структурного анализа, классификации сообразно целям исследования. Чаще всего решение перечисленных задач производится экспертом-исследователем на основании содержательных рассуждений о природе изучаемых объектов и, очевидно, при большом количестве признаков связано с серьезными
трудностями. В связи с этим становится актуальным применение математического инструментария для поиска решения описанных задач.
Анализ литературы показывает, что исследователями в разные годы проделана большая работа по разработке методов решения проблемы анализа и описания структуры статистических связей, существующих между исследуемыми статистическими показателями. Но на сегодняшний день указанные методы не получили широкого практического применения по причине очень малого числа работ, посвященного их сравнительному анализу, а также вследствие отсутствия программно-алгоритмической реализации, позволяющей автоматизировать их применение на практике. Высказанные соображения предопределили выбор темы, целей и задач данной работы.
Целью работы является создание программно-алгоритмической системы анализа структуры взаимосвязей между статистическими показателями и использование этой системы в межстрановом и межрегиональном анализе синтетических категорий качества жизни населения.
Задачи, возникающие в рамках достижения поставленной цели, можно обозначить следующим образом:
Аналитический обзор существующих методов выявления структуры взаимосвязей между компонентами многомерного случайного признака.
Сравнительный анализ эффективности рассматриваемых методов с помощью проведения вычислительных экспериментов на модельных и реальных данных.
Разработка необходимого программного обеспечения, т.е. создание программного комплекса, позволяющего осуществлять вычислительную реализацию каждого из рассматриваемых методов.
Структуризация и анализ переменных, характеризующих уровень материального благосостояния в межрегиональном исследовании субъектов РФ и качество жизни населения в межстрановых сопоставлениях.
12 В настоящее время существует множество программно-алгоритмических средств (пакетов), обладающих мощным статистическим инструментарием: EViews, SPSS, Statistica и др. Однако при всем богатстве предоставляемых исследователю методов, вышеперечисленные алгоритмы структурного анализа исследуемых показателей на сегодняшний день, насколько нам известно, в данных пакетах не представлены. Принимая во внимание указанный факт, приходим к следующему выводу.
Новизна и основные результаты предлагаемой работы:
Произведен сравнительный анализ эффективности методов структурного анализа взаимосвязей между компонентами многомерного случайного вектора, а именно: алгоритмов ^-коэффициентов, экстремальной группировки признаков, Лумельского, Чоу, Демпстера и алгоритмов, основанных на теоретико-информационном подходе. Создано программно-алгоритмическое средство, в рамках которого исследователю предоставляется возможность практического применения перечисленных методов структурного анализа статистических данных, которые не представлены, насколько нам известно, в распространенных статистических пакетах.
На базе методики построения синтетических показателей (интегральных индикаторов) качества жизни населения, предложенной в работе [Айвазян (20036)], разработанное программное средство использовано для построения и эмпирического анализа структуры связей, существующих между указанными индикаторами. Расчеты производятся на основе данных по странам [WCY (1996 - 2004)] и регионам Российской Федерации за 1997-2003 гг.
Кроме того, созданный программный продукт обладает удобным современным интерфейсом и предоставляет возможности полноценного ввода, хранения, обработки статистических данных, гибкого экспорта полученных результатов в другие приложения, а также ряд вспомогательных инструментов. Среди этих инструментов: унификация шкал измерений; основные операции матричной алгебры (вычисление определителей, обратных матриц, собственных значений); генерирование нормально распределенных
13
псевдослучайных величин с заданными параметрами; определение размерности
многокритериального пространства (многокритериальная классификация в
условиях отсутствия обучения); вычисление первых главных компонент,
включая модифицированные; определение удельной значимости каждой из
построенных интегральных характеристик (в случае разбиения исходного
набора признаков на группы); взвешенная многокритериальная процедура
индивидуального рейтингования наблюдений в пространстве
модифицированных первых главных компонент; ранжировка наблюдений по значению вычисленного интегрального индикатора, а также по экспертному значению индикатора (если экспертная оценка существует и известна); вычисление ранговых коэффициентов корреляции Спирмена.
При создании программного продукта в качестве инструментального средства использовалась среда разработки Borland Delphi 6. Роль хранилища данных выполняет Microsoft Access, как одно из наиболее доступных средств для большинства пользователей. В процессе проектирования и программирования автор всячески старался не ограничивать возможности расширения (масштабируемости) создаваемого приложения. В этой связи внутренняя реализация библиотеки операций над матрицами использует все основные преимущества объектно-ориентированного программирования. Кроме того, реализованное программное средство использует технологию Microsoft ADO [Кэнту (2001), с. 512-514] для связи с хранилищем данных и производит операции над данными посредством инструкций языка SQL [Грабер (2003)]. Примененный подход позволяет, в случае необходимости, с минимальными затратами преобразовать приложение в клиент-серверную систему, перенеся данные на мощную серверную платформу, например Oracle, Microsoft SQL Server, InterBase и т.п. Это даст возможность одновременного использования данных несколькими пользователями в сети и позволит производить трудоемкие расчеты на стороне сервера, что значительно повысит производительность и вычислительные возможности системы [Кэнту (2001), с. 465-167].
Два алгоритма экстремальной группировки признаков
Ниже мы рассмотрим два эвристических алгоритма группировки, предложенные в работе [Браверман (1970)] и называемые алгоритмами экстремальной группировки признаков. Отличительной особенностью данных алгоритмов является то, что помимо разбиения признаков на непересекающиеся группы, в каждой группе строится случайная величина, которая в некотором смысле наиболее сильно коррелирует со всеми переменными, входящими в данную группу. Эта случайная величина интерпретируется как искомый фактор, существенно влияющий на все переменные данной группы. Таким образом, одновременно решается задача выявления факторов, описываемых переменными каждой группы. Число групп, в отличие от предыдущего алгоритма, предполагается известным и задается заранее.
В основу обоих алгоритмов экстремальной группировки положен подход, связанный с экстремизацией некоторого функционала, зависящего как от способа группировки, так и от выбора факторов, что и объясняет название методов. Этот функционал выбирается так, что его экстремизация как по разбиению, так и по выбору факторов интуитивно соответствует поставленной содержательной задаче.
Первый алгоритм экстремальной группировки
Пусть множество признаков (переменных) Х\,Х2, ...,хр разбито на непересекающиеся группы A\,Ai, ...,Ат и заданы нормированные (т.е. с единичной дисперсией D/ = r(fj,/J)= 1) случайные величины /,/, ..,/т, называемые факторами.
Первый алгоритм экстремальной группировки признаков в качестве критерия оптимальности использует функционал л =2 ( ,- /,))2+Z( /2))2+...+X(r( / /j)2, ало) ieS\ ieS2 ieSm где r(x, /) - обычный парный коэффициент корреляции между признаком х и фактором / a S\,S2,...,Sm - подмножества индексов признаков, соответствующие группам, т.е. А1 = {х(, і є Sl}, I = 1, 2, ..., т.
Максимизация функционала (1.10) соответствует интуитивному требованию такого разбиения признаков, когда в одну группу попадают наиболее «близкие» между собой переменные. Действительно, при максимизации функционала (1.10) для каждого фиксированного набора случайных величин /\,/ъ -.-,/т в одну /-ю группу будут попадать такие признаки, которые наиболее «близки» к величине,//. В то же время среди всех возможных наборов случайных величин /,/, ...,/т будет отбираться такой набор, что каждая из величин / в среднем наиболее «близка» ко всем переменным из своей группы.
Очевидно, что при фиксированном разбиении оптимальный набор факторов /,/, ...,/т, удовлетворяющих условию нормировки, получается в результате независимой максимизации каждого слагаемого в выражении (1.10) и задается формулами: //= i l „. = 1.2 т, (1.11) где / - индекс группы, сс(/) =(а[/),а2),...,а )) - собственный вектор корреляционной матрицы Z/ элементов 1-й группы, соответствующий максимальному собственному значению А,/, т.е. Z/ -а(/) = А,, а(/). Считая известными факторы/\,/2, ...,/т, строим разбиение S\, S2, ..., Sm, максимизирующее J\ при фиксированном наборе факторов, следующим образом: S,={/:r2(x,,/,) r2(x,,./;), = 1,2,..., } (1.12) Соотношения (1.11) и (1.12) являются необходимыми условиями максимума функционала J\.
Для одновременного нахождения оптимального разбиения и оптимального набора факторов предлагается следующая рекуррентная процедура. Пусть на v-м шаге итерации построено разбиение признаков на группы А\, ..., Ат. Для каждой такой группы переменных строятся факторы /(,v) по формуле (1.11) и новое (v+ 1) разбиение признаков Л(,у+1),..., Л( +1) в соответствии с правилом: признак , относится к группе А \ если г2(Хі,/У) г2(Хі,/У), = 1,2,..., . (1.13)
Если для какого-то признака х, найдутся два или более фактора таких, что для х, и этих факторов в (1.13) имеет место равенство, то переменная х, относится к одной из соответствующих групп произвольно.
Очевидно, что на каждом шаге итераций функционал J\ не убывает, поэтому алгоритм будет сходиться к максимуму. Следует заметить, что максимум может быть локальным, и результат работы алгоритма может зависеть от начального разбиения. Подробнее на этом моменте остановимся в главе III, где будут показаны результаты вычислительных экспериментов.
-информационный подход к структуре случайной величины
Пусть - есть случайная величина (для определенности непрерывная) со значениями д: и плотностью fix). Ее энтропией называется величина, обозначаемая Н(,) и равная H) = -\f(x)\nf(x)dx. (1.52) X
Для дискретных случайных величин знак интеграла в выражении (1.52) заменяется суммой. В некоторых случаях удобнее бывает вместо натурального логарифма брать логарифм по основанию 2.
Энтропия распределения пары случайных величин и г) со значениями х и у соответственно и совместной плотностью J[x, у) определяется в виде H &vv = -\\f{x,y)\nf{x,y)dxdy (1.53) х у Условной энтропией величины по условию г\=у назовем число Н \ц = у) = Н ) = -1/ц(у)\Д(х\ц = у)\пД(х\ц = у)ахсІу, (1.54) У х где/,(у) - частная плотность случайной величины т, аД(х \ г\ =у) - условная плотность случайной величины при фиксированном значении г\ =у. Укажем основные свойства энтропии. 1. Я() 0, причем равенство достигается тогда и только тогда, когда х принимает только одно значение. 2. Значение Я() максимально, когда все возможные значения случайной величины JC равновероятны. 3. #() = Я. 4. Я( л) = Я( ) + Я4(л). 5. Я(,г)) Я() + Я(г), причем равенство достигается тогда и только тогда, когда случайные величины и г\ статистически независимы. 6. Я ) = 0. 7. ЯП( ) Я(), причем равенство достигается тогда и только тогда, когда случайные величины Ъ, и ц статистически независимы. Информацией о величине , содержащейся в величине т, назовем число /&Т1) = Я + Я(л) - Я&л) (1-55) Укажем основные свойства информации, которые легко следуют из свойств энтропии. і./&а=я($). 2. /(4,л) = /(ЛЛ) 3. /(%, г) 0 и /( , л) = 0 тогда и только тогда, когда Ъ, и л независимы. 4./( ,(л,р)) /( л). 5. /( , (л, р)) = /( Л) тогда и только тогда, когда выполняется соотношение / (х л = У, р = z) = / (х л = у)
С учетом свойств энтропии выражение (1.55) может быть переписано в виде 1(&г\) = Н()-Н ). (1.56)
Как легко видеть, в силу пятого свойства информации случайную величину со структурой можно определить с помощью равенств вида /( .,( , )) = /(5,,4/) Для всех марковских троек {,-, 5у, } на соответствующем графе структуры связей G(X) 5.
Теорема 1.4 [Гаврилец (1974), с. 140-141]. Для того чтобы тройка переменных {,-, 4у } была марковской (т.е. имело место / (xi \ j k) = Л,(х( I %j)) необходимо и достаточно выполнения соотношения Щ Лк)) = Щ,%і) + ЩЛк)-тЛк)- (1.57)
Будем называть жесткой структурой структуру многомерной случайной величины X, определяемую графом связей G{X), если равенства /$,(xi \ j =xjk=xk) = f\t(ХІ I% j = xj) x являются необходимым и достаточным условием того, что в графе G{X) отсутствует цепь, соединяющая вершины ,- и , не проходящая через "tj.
Если равенства f (х(. . = xJ,)k=xk) = / (xt . = Xj) для любого х выполняются и в том случае, когда существует цепь из в , не проходящая через -, то естественно назвать часть связей (выражаемых через упомянутую цепь) псевдосвязями. Псевдосвязи могут возникать, например, когда часть переменных есть случайная функция других. Ниже предлагается эвристический алгоритм поиска жесткой структуры, то есть исключается случай с возможными псевдосвязями Алгоритм определения жесткой структуры
Пусть известно, что многомерная случайная величина имеет некоторую жесткую структуру. Опишем алгоритм ее выявления.
1. На начальном шаге выявляются изолированные узлы графа, соответствующие переменным, которые полностью независимы от остальных. В силу доказанных в работе [Гаврилец (1974)] утверждений, такими переменными будут переменные, попарно независимые от других. Другими словами, равенство /(4/,40 = 0 V / означает изолированность /-го узла в графе структуры зависимостей G(X). Выявив все изолированные узлы, отбрасываем из набора соответствующие им переменные и далее рассматриваем только оставшиеся (граф G\).
2. Следующим шагом выявляются узлы, для которых существует только по одному смежному узлу. Для этого для каждого / сравниваются между собой все парные информации /( ,-, ) = 0 VкФг, и отбирается наибольшая из них: Д/» „)-І( іЛк) VкФі. Для случая к є Gx будет существовать единственный максимум; в противном случае у г-го узла более одного смежных узлов. Далее для данной пары узлов (/, ко) необходимо сравнить информацию /(4,-,4, )со всеми информациями /(4,-,(4 ,4/))» где ІФІ, 1Ф к0. Равенство 7(S,, ) = /(S,,( /))V/ означает, что G\ = {к0}. Отбросив поочередно все выявленные узлы / данного типа, переходим к следующему шагу (граф G2, не имеющий узлов данного типа).
Библиотека матричных вычислений
На данный момент, в языке программирования ObjectPascal нет собственной библиотеки для работы с матрицами, но существуют библиотеки сторонних разработчиков. К сожалению, эти библиотеки либо не доработаны, либо носят коммерческий характер, поэтому решение создать свою матричную библиотеку выглядит целесообразным. При этом были использованы некоторые процедуры, применявшиеся в свободно распространявшихся подобных библиотеках, но их количество было небольшим.
Процесс создания библиотеки состоит из двух основных этапов. Первый этап представляет собой проектирование некоего каркаса будущего класса, экземпляром которого будет являться объект (в нашем случае матрица). Понятия класса и объекта - базовые в объектно-ориентированном программировании (ООП), поэтому дадим их определения.
Класс - это тип данных, определяемый пользователем (программистом), который включает в себя набор допустимых значений (описание типа) и набор возможных операций над ним (поведение типа). Класс содержит внутри себя (инкапсулирует) набор данных и методов, реализованных при помощи процедур или функций, и обычно обобщает свойства однородных объектов. Объект является экземпляром класса или, иными словами, переменной типа данных, объявленного классом. Объект - реальная сущность, класс - только шаблон, на основе которого создаются объекты. Соотношение между объектом и классом аналогично соотношению между переменной и типом данных [Кэшу (2001), с. 70]. Важным понятием является наследование (inheritance), то есть создание одного класса на основе другого с добавлением или изменением некоторых свойств родительского класса [Кэнту (2001), с. 82-84].
На первом этапе создания библиотеки решается, какими основными свойствами и методами объект данного класса должен обладать. В нашем случае, к основным свойствам относятся, например, размерность матрицы, ее имя, значение определенного элемента, определитель и другие. Под методами понимаются функции и процедуры, изменяющие сам объект-матрицу, например, добавление строки, приведение к треугольному виду и т. п. После того, как будет получено ясное представление о том, какими свойствами и методами должен обладать экземпляр класса (объект «Матрица»), приступают к следующему этапу. Второй этап заключается в реализации свойств и методов класса, то есть в непосредственном программировании процедур и функций.
Несомненно, первый этап является наиболее важным, хоть и требует меньшего объема программирования и временных затрат. Логическая ошибка проектирования класса может повлечь за собой трудно преодолимые проблемы в дальнейшем. Существует несколько подходов к созданию объектно-ориентированной матричной библиотеки, подобной нашей. Как правило, набор основных свойств и методов объекта-матрицы во всех библиотеках примерно одинаков, что вполне естественно. Различия заключаются, в основном, в технической реализации хранения элементов матрицы и способов доступа к ним.
Во многих матричных библиотеках используются двумерные массивы для хранения элементов, то есть матрица представляет собой одномерный массив векторов (строк или столбцов), которые, в свою очередь, являются одномерными массивами элементов. Такой подход вполне логичен, но порождает некоторые технические трудности, особенно при выполнении операций, изменяющих размерность матрицы (например, удаление или вставка вектора). Возникающие трудности вполне преодолимы, но нами был выбран несколько иной технический подход.
В предложенной нами реализации все элементы матрицы хранятся в упорядоченном одномерном массиве, длина которого равна (р х п), где р - число строк матрицы, а п - число ее столбцов. Упорядочение производится по строкам: сначала идут п элементов первой строки, затем п элементов второй и так далее до /7-й строки включительно. Учитывая, что нумерация элементов массива в Object Pascal начинается с нуля, получаем, что для обращения к элементу /-й строки иу -го столбца матрицы достаточно вычислить значение nx{i-\) + j-\, (ИЛ) которое будет являться индексом элемента в упорядоченном одномерном массиве. Описанный подход несколько необычен, но не является чем-то принципиально новым. Похожая техника часто применяется при работе с форматированным текстом, когда он хранится не построчно, а в виде одной длинной строки (одномерный массив символов), в которой присутствуют символы перехода на новую строку и абзаца. Преимущество заключается в удобстве манипулирования элементами одномерного массива по сравнению с двумерным.
Ниже приведена та часть модуля матричных вычислений, в которой определен класс TMatrix. Приводится только объявление самых основных типов, свойств и функций класса без их реализации. Это сделано с целью краткого пояснения основных технических принципов проектирования класса.
Более подробно о классах вообще и, в частности, о классах в Delphi можно прочесть в работе [Кэнту (2001), с. 69-148]. Курсивом после символов « // » изображены комментарии. Троеточие указывает на некоторый пропущенный код.
Анализ эффективности методов выявления структуры связей многомерного случайного признака
Схема эксперимента для анализа алгоритмов определения структуры связей многомерной случайной величины отличается от схемы, предложенной для алгоритмов группировки. Сначала дадим краткое описание этапов эксперимента, затем рассмотрим каждый шаг более подробно. 1. Построение графа-дерева структуры связей некоторой неизвестной многомерной случайной величины. 2. Моделирование матрицы Е-1, обратной к ковариационной матрице случайной величины, соответствующей графу структуры зависимостей. 3. Вычисление ковариационной матрицы = (Е-1 )-1. 4. Моделирование наблюдений (О, )-нормальной случайной величины. 5. Применение алгоритмов к полученной матрице наблюдений с целью получения графа структуры связей. 6. Сравнение графа, полученного на предыдущем шаге, с исходным графом. 7. Многократное повторение шагов 4-6 с целью исследования устойчивости алгоритмов. Теперь рассмотрим описанную схему более подробно.
Поскольку при анализе структуры связей нашей целью является получение некоторого ненаправленного графа, вершины которого соответствуют переменным, а ребра - непосредственным связям между ними, то эксперимент начинаем с построения этого графа. Потребуем, чтобы этот граф имел р вершин, (р - 1) ребро и не имел циклов. Это означает, что многомерная случайная величина X имеет древообразную структуру зависимостей. Мы рассматривали в качестве исходного граф структуры зависимостей шестимерной случайной величины, изображенный на рисунке III. 1.
На втором шаге моделируется обратная к ковариационной матрица Е -1, в которой на позициях, соответствующих отсутствующим ребрам графа, расположены нулевые или близкие к нулевым элементы (см. теорему 1.1). Смоделированная матрица должна быть симметричной и положительно определенной, так как является обратной для ковариационной матрицы п.
Кроме того, над главной диагональю в Xj1 должно быть расположено ровно (р- 1) элементов, которые значимо отличаются от нуля, где р - размерность
Последнее условие соответствует тому, что между р переменными существует (р— 1) непосредственная связь. Моделирование подобной матрицы производится эмпирическим путем, чаще всего на основании матрицы, обратной к реальной корреляционной матрице путем ручного приближения к нулю некоторых элементов обратной матрицы. При этом необходимо помнить об условии положительной определенности и невырожденности (достаточной удаленности от нуля определителя матрицы).
Полученная описанным образом матрица изображена в таблице Ш.З. В ней светло-серым цветом выделена группа недиагональных элементов, достаточно удаленных от нуля, по сравнению с остальными. (Учитывается, что диагональные элементы преобладают и являются величинами одного порядка).
На третьем шаге вычисляем матрицу, обратную для матрицы Zx. В результате получаем симметричную положительно определенную матрицу Zz, которая рассматривается как ковариационная в силу того, что любая симметричная положительно определенная матрица является ковариационной матрицей некоторой случайной величины. Докажем последнее утверждение.
Рассмотрим случайную величину X размерности р такую, что ее ковариационная матрица совпадает с единичной (LX=I ), и некоторую симметричную положительно определенную матрицу А. Построим для матрицы А разложение Холецкого: А = ССТ, (III. 1) где С - нижняя треугольная матрица. Затем построим случайную величину Y = СХ, и вычислим для нее ковариационную матрицу: 1у = Е(ХХТ) = Е(СХХТСТ) = С(Е(ХХТ))СТ = С1рСт =ССТ = А. (Ш.2) Из выражения (Ш.2) следует, что А является ковариационной матрицей случайной величины Y.
Кроме того, имеет смысл перейти от ковариационной матрицы к корреляционной, нормировав вычисленную матрицу Их соответствующим образом. Полученная корреляционная матрица изображена в таблице Ш.4. Значимыми считаем корреляции, по модулю большие 0,45; они выделены в таблице светло-серым цветом фона.
