Содержание к диссертации
Введение
1 Анализ методов визуального представления структур многомерных взаимосвязей. Задачи диссертации 10
2 Определение и визуализация структуры взаимосвязей на основе задачи іУтел и нечеткой кластеризации 46
2.1 Состав и требования, предъявляемые к исходным данным 47
2.2 Определение структуры взаимосвязей на основе задачи 50
2.2.1 Математическая модель системы взаимодействующих пузырьков 50
2.2.2 Итерационный алгоритм решения задачи ., 60
2.2.3 Сходимость и точность получаемого решения 69
2.2.4 Необходимые условия для проведения точной визуализации 79
2.2.5 Выявление ошибок визуализации, варианты применения разработанного метода 86
2.2.6 Состав и чтение получаемых диаграмм, простые примеры визуализации 89
2.3 Нечеткая кластеризация полных групп на основе комбинаторного подхода. Построение графа нечеткой кластерной структуры взаимосвязей 100
2.4 Программное средство, реализующее разработанные алгоритмы 113
3 Применение полученных результатов 118
3.1 Определение структуры взаимосвязей котировок акций, входящих в портфель 118
3.2 Определение структуры потребительских предпочтений к возможным вариантам конфигурации товара 121
3.3 Определение структуры симпатий и антипатий внутри малых социальных групп 134
Заключение 159
Список использованных источников 161
Публикации по теме диссертации 169
- Состав и требования, предъявляемые к исходным данным
- Необходимые условия для проведения точной визуализации
- Нечеткая кластеризация полных групп на основе комбинаторного подхода. Построение графа нечеткой кластерной структуры взаимосвязей
- Определение структуры потребительских предпочтений к возможным вариантам конфигурации товара
Введение к работе
Актуальность работы. В настоящее время разработано и широко применяется множество различных методов визуального отображения многомерных данных Это связано с тем, что визуализация является удобным, а в некоторых случаях и необходимым, способом представления данных либо результатов их обработки, обеспечивая для исследователя интуитивно понятное и удобное восприятие, а также легкость сопоставления и сравнения
Проведение визуального отображения многомерных данных зачастую сопряжено с решением задачи как можно более точного их переноса из многомерного пространства на визуализационную плоскость Из-за отсутствия однозначности в решении указанной проблемы и предъявления различных требований к характеристикам получаемых визуализаций - научная задача по разработке методов визуального отображения многомерных данных (каждый из которых имеет свою целевую направленность, сильные и слабые стороны) остается актуальной как в настоящее время, так и в перспективе Также очевидно, что совместное взаимодополняющее применение различных методов визуализации позволяет провести более глубокий и многосторонний анализ исследуемых данных В качестве основных применений методов визуализации можно указать следующие наглядное представление геометрической метафоры данных, лаконичное описание внутренних закономерностей, заключенных в наборе данных, сжатие информации, заключенной в данных, восстановление пробелов в данных, решение задач прогноза и построения регрессионных зависимостей между признаками
При рассмотрении сложных статистических систем в качестве одной из основ для определения и анализа структур, заложенных в них взаимосвязей, выступают матрицы расстояний (близости) между объектами, составляющими систему Указанные матрицы получают путем введения той или иной метрики, а их содержательной основой является набор многомерных данных, характеризующих взаимосвязи между объектами системы Визуализация подобных матриц как визуализация структуры взаимосвязей между объектами статистической системы является одним из направлений разработки и применения методов визуального отображения многомерных данных Представляемая диссертационная работа посвящена развитию одного из подходов к визуализации структур взаимосвязей между объектами статистической системы
Целью диссертационной работы является развитие подхода к визуализации структур взаимосвязей между объектами статистической системы, основывающегося на фундаментальной задаче небесной механики - физической задаче N тел, а также определение возможностей его практического применения совместно с алгоритмами кластеризации
Данная цель достигается решением следующего комплекса задач 1 Проведение сравнительного анализа существующих методов, позволяющих визуализировать структуры многомерных взаимосвязей между объектами статистической системы
Выявление наиболее перспективных форм визуального представления структуры взаимосвязей, между объектами статистической системы, с точки зрения их развернутости и информативности, интуитивной понятности, наглядности и легкости восприятия
Выявления достоинств и недостатков методов визуализации структур взаимосвязей, между объектами статистической системы, основывающихся на задаче Л?" тел либо ее модификациях Определение наиболее перспективных направлений их совершенствования
Учитывая выявленные недостатки, разработка более совершенного метода визуализации структур взаимосвязей между объектами статистической системы, основывающегося на модификации задачи N тел
Для анализа получаемых визуальных отображений многомерных структур взаимосвязей рассмотреть возможности применения алгоритмов кластеризации При необходимости разработать специализированные алгоритмы кластеризации, непосредственно адаптированные к применению совместно с разработанным методом визуализации
Разработать программное средство, реализующее построенные алгоритмы
Используя созданную компьютерную программу, провести исследования по практическому применению разработанных алгоритмов
Методы исследования основываются на использовании известных из физики законов Ньютона, математической модели задачи N тел, численных методов, кластерном анализе, теории графов, математическом и системном анализе, комбинаторике, компьютерном моделировании В разработке программного обеспечения использовалась технология объектно-ориентированного программирования
Теоретическая значимость и научная новизна:
впервые предложен специальный вид пузырьковых диаграмм как способ визуального представления структуры взаимосвязей между объектами статистической системы,
разработан новый метод визуализации структуры взаимосвязей, между объектами статистической системы, в виде пузырьковых диаграмм В основе метода лежит модификация задачи N тел,
разработан новый комбинаторный алгоритм точного определения нечеткой кластерной структуры с неизвестным заранее числом кластеров, разбивающий исходное исследуемое множество взаимосвязанных элементов на возможно пересекающиеся подмножества их полных групп Предложено представление результатов работы алгоритма в визуальной форме в виде специального неориентированного графа
Практическая значимость. На основе разработанных алгоритмов создано программное приложение, которое реализует для пользователей эффективные инструменты визуального представления и анализа структур взаимосвязей, описываемых симметричными матрицами Программная реализация разработанных алгоритмов может найти широкое практическое применение в различ-
ных областях исследований экономика, медицина и биология, психология, филология, социология и многие другие Реализация результатов работы:
— результаты диссертационного исследования принимают участие в ведомст
венной целевой программе развития научного потенциала высшей школы -
МОН, РНП2 1 2 412 - Метод моментов в управлении линейными нестацио
нарными системами, 2006-2007, а также в НИР БП 1 11 06 «Динамика и
управление системами с переменными параметрами»,
- создано программное средство, реализующее разработанные в работе алго
ритмы - зарегистрировано в Федеральной службе по интеллектуальной соб
ственности, патентам и товарным знакам - свидетельство об официальной
регистрации программы для ЭВМ №2005612595,
— программная реализация алгоритмов, разработанных в диссертационной ра
боте, внедрена в Красноярской государственной медицинской академии как
инструмент анализа корреляционных матриц биологических данных, и в
компании ОАО КЗХ «Бирюса» (Красноярск) как инструмент определения и
анализа структуры потребительских предпочтений на основе данных анкет
ных опросов
Положения, выносимые на защиту.
Пузырьковая диаграмма как способ визуального представления многомерной структуры взаимосвязей между объектами статистической системы
Математическая модель силового взаимодействия множества взаимосвязанных элементов и алгоритм, позволяющий на ее основе рассчитывать и получать пузырьковые диаграммы структуры взаимосвязей объектов статистической системы
Комбинаторный алгоритм точного определения нечеткой кластерной структуры с неизвестным заранее числом кластеров, разбивающий исходное исследуемое множество взаимосвязанных элементов на возможно пересекающиеся подмножества их полных групп (подмножества групп элементов имеющих связи типа все со всеми)
Апробация работы. Основные результаты диссертации докладывались и обсуждались на
Межрегиональной научно-практической конференции "Молодежь Сибири -науке России" (Красноярск, 2003),
Всероссийское! научной конференции молодых ученых "Паука Технологии Инновации" (Новосибирск, 2003),
III межвузовской конференции аспирантов "Актуальные проблемы современной науки и пути их решения" (Красноярск, 2003),
VII Всероссийской научной конференции 'Тешетневские чтения" (Красноярск, 2003),
VII конференции по финансово-актуарной математике (Красноярск, 2003),
— III Всероссийской конференции по финансово-актуарной математике (Крас
ноярск, 2004),
- Конференции, посвященной дню космонавтики (Красноярск, 2004),
VIII конференции по финансово-актуарной математике (Красноярск, 2004),
VI Всероссийской конференции по финансово-актуарной математике и смежным вопросам (Красноярск 2005),
Всероссийской научно-практической конференции студентов, аспирантов и молодых специалистов "Актуальные проблемы авиации и космонавтики" (Красноярск, 2006)
Публикации. Основные результаты диссертации опубликованы в 11 статьях, в том числе одна статья в издании из списка ВАК
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка использованных источников и трех приложений Объем диссертации 175 страниц
Состав и требования, предъявляемые к исходным данным
Определим состав и требования, предъявляемые к исходным данным, которые будут использоваться для расчета и построения пузырьковых диаграмм взаимосвязей.
Пусть имеется некоторое множество А, состоящее из п элементов, имеющих между собой определенные связи:
А = {ах,аг,---,ап}.
Каждый из элементов рассматриваемого множества соответствует одному из объектов изучаемой статистической системы. Мера парной связи между элементами а( и ai рассматриваемого множества определяется исследователем произвольно в зависимости от направления исследуемого характера связей в системе. Основное требование, предъявляемое к используемой мере связи - это ее симметричность, т.е. si j =sjr Связь элемента с самим собой в рассмотрение не включается.
В общем, связи между элементами рассматриваемого множества представляются симметричной матрицей связей S размерностью пхп: Очевидно, что используемые исследователем меры связей между объектами могут варьироваться в различных диапазонах и нести разную смысловую нагрузку при принятии тех или иных значений. Поэтому для определения однородности исходных данных, которые будут использоваться в разрабатываемых методах, коэффициенты связей s, . между элементами рассматриваемого множества преобразуются и нормируются к интервалу значений [0;l] и представляются соответствующей симметричной матрицей коэффициентов связей С пхп:
Таким образом, коэффициенты парных связей ctj (i,j = \,n) принимают значения в интервале [0; 1] и соответствуют значениям связей st. исходной матрицы S. В дальнейшем при решении поставленной задачи именно матрица связей С, полученная на основе исходной матрицы S, будет подлежать визуальному представлению, призванному раскрыть заложенную в ней общую структуру связей между элементами рассматриваемого множества - объектами изучаемой статистической системы.
Рассмотрим в качестве примера исходной матрицы связей S матрицу линейных корреляций Пирсона, как широко применяемую в исследованиях статистических зависимостей. В данном случае коэффициенты связей как коэффициенты корреляции, могут принимать значения в интервале [-l;l]. Могут быть использованы различные способы преобразования коэффициентов исходной матрицы связей S к матрице связей
Необходимые условия для проведения точной визуализации
Отображение матрицы взаимосвязей элементов С в виде пузырьков на диаграмме с диаметрами w и взаимными расстояниями в соответствии с матрицей расчетных расстояний DC относится к классу задач по отображению многомерных данных в пространстве меньшей размерности (в данном случае в двухмерном Евклидовом пространстве). Общей проблемой для таких отображений является обеспечение как можно большей их точности.
В зависимости от размерности матрицы взаимосвязей С для того, чтобы ее точная визуализация была в принципе возможной, можно выделить определенные условия, которые должны выполняться для соответствующих значений расчетных расстояний в матрице DC. Так, исходя из того, что каждому из пузырьков на диаграмме соответствует точка его центра, а матрица DC содержит в себе информацию о (необходимых для правильного отражения структуры взаимосвязей) расстояниях между центрами пузырьков - условия возможности точной визуализируемое структуры взаимосвязей на евклидовой плоскости определяют возможность размещения на ней точек-центров пузырьков на расстояниях в соответствии с матрицей DC: 1) если матрица взаимосвязей имеет размерность 2x2 - два визуализируемых элемента, то очевидно, что данная взаимосвязь всегда может быть отражена на евклидовой плоскости без наложения каких либо условий - две точки на расстоянии в соответствии с матрицей DC.
2) Если матрица взаимосвязей имеет размерность 3x3 - то, представляя точ ки центров пузырьков как вершины треугольника, а расстояния между ними как длины его сторон - для обеспечения возможности построения данного треугольника на плоскости необходимо выполнение правила треугольника в евклидовом пространстве (рисунок 2.13):
3) Если матрица взаимосвязей имеет размерность 4x4 - то, аналогично предыдущей ситуации необходимо, чтобы для соответствующих расстояний в матрице DC для всех возможных троек элементов выполнялось условие (2.3) при я = 4. Но в данном случае это будет являться лишь необходимым, но уже не достаточным условием возможности точной визуализации на плоскости структуры взаимосвязей - его выполнение обеспечивает лишь возможность отображения "треугольных" связей, но не их совместную компоновку. Так, если представить центры пузырьков четырех визуа лизируемых элементов как некоторые вершины на плоскости, попарно соединенные линиями, длины которых должны соответствовать расстояниям в матрице DC (рисунок 2.14 а), то, учитывая количество имеющихся вершин, в состав данной геометрической конфигурации будет входить треугольника, которые будут иметь по одной из смежных сторон друг с другом. Это вытекает из того, что суммарное количество вершин для двух треугольников соответственно равно шести, а имеющихся в рассматриваемой конфигурации всего четыре - соответственно две вершины будут смежными - смежная сторона, а две нет. Учитывая, что для треугольника задание длин всех его сторон однозначно определяет его геометрическую конфигурацию, то расстояние между несмежными вершинами двух произвольно выбранных треугольников в рамках рассматриваемой геометрической конфигурации (рисунок 2.14 б, в) тоже может быть выражено через длины их сторон. При этом будет иметь два возможных значения - для случая, когда несмежные вершины треугольников лежат по одну сторону смежной стороны и по разные.
Нечеткая кластеризация полных групп на основе комбинаторного подхода. Построение графа нечеткой кластерной структуры взаимосвязей
Существует множество методов кластеризации, которые можно классифицировать на четкие и нечеткие [30, 50, 51, 81]. Четкие методы кластеризации разбивают исходное множество объектов А на несколько непересекающихся подмножеств Ак. При этом любой объект из А принадлежит только одному кластеру Ак. Нечеткие методы кластеризации позволяют одному и тому же объекту принадлежать одновременно нескольким (или даже всем) кластерам, но с различной степенью. Нечеткая кластеризация во многих ситуациях более "естественна", чем четкая, например, для объектов, расположенных на границе кластеров. К таким случаям относится и использование указанных алгоритмов для условного разбиения пузырьковых диаграмм взаимосвязей (графов взаимосвязей) на возможно пересекающиеся поддиаграммы (подграфы) по тем или иным критериям. Ведь в рамках всей структуры взаимосвязей вполне вероятна ситуация, когда один и тот же элемент может принадлежать нескольким кластерам одновременно.
При проведении визуального анализа получаемых пузырьковых диаграмм в некоторых случаях (такие примеры можно увидеть в п.3.2 и 3.3), одной из важных практических задач оказалось точное определение ее нечеткой кластерной подструктуры в виде полных групп (группы, в которых все элементы имеют связь типа все со всеми). Следует отметить, что как было сказано выше, для решения данной задачи могут быть использованы и существующие алгоритмы нечеткой кластеризации, однако они не дают 100% гарантии в точности определения указанной подструктуры [30, 50, 81]. Среди известных алгоритмов, разработанных в теории графов [8, 27, 31, 33, 38, 70], алгоритма, решающего данную узконаправленную прикладную задачу, не разработано.
В связи со всем вышесказанным, а также в связи с тем, что одним из подходов для точного решения поставленной задачи может быть использование переборных алгоритмов [48, 61, 68] - в данном разделе диссертации разрабатывается комбинаторный алгоритм точного определения нечеткой кластерной структуры с неизвестным заранее числом кластеров пк, разбивающий исходное исследуемое множество А, состоящее из п взаимосвязанных элементов, на подмножества полных групп элементов Д, со следующими свойствами:
Условие (1) указывает на то, что все элементы должны быть распределены по кластерам; при этом ни один из кластеров не может быть пустым, но может одновременно содержать все элементы рассматриваемого множества -условие (2).
Данными для работы алгоритма определения нечеткой кластерной структуры в виде полных групп служит матрица взаимосвязей (близости / схожести) С (см. п.2.1) множества рассматриваемых элементов. Критерием отнесения элемента UCZAK кластеру Ак является его взаимосвязь, в соответствии с матрицей С, с остальными элементами этого же кластера: где: АI - мощность множества - количество элементов в кластере Ак; jk - номера элементов исходного множества А внутри кластера Ак; с .. - взаимосвязь элементов множества А с индексами і и /. . Очевидно точным, но и не оптимизированным способом выявления всех кластеров, содержащихся в матрице С, удовлетворяющих поставленным условиям, был бы перебор и проверка всех возможных сочетаний элементов. При больших размерах матриц взаимосвязей такой перебор может "заставить задуматься" даже современные высокопроизводительные персональные компьютеры, поэтому вполне обоснована разработка оптимизирующего алгоритма.
Один из способов оптимизации без потери гарантии выявления всех содержащихся в структуре кластеров является также перебор сочетаний, но не самих элементов, а их парных сочетаний, причем только тех, для которых имеется взаимосвязь между соответствующими элементами. Реализация данной идеи представлена алгоритмом упорядоченного перебора парных сочетаний взаимосвязанных элементов. Алгоритм состоит из следующих шагов: Шаг 1: Выделение, на основе матрицы взаимосвязей С, всех парных сочетаний элементов, имеющих взаимосвязь больше нуля (число элементов в выделяемых сочетаниях т = 2); Шаг 2: Построение сочетаний следующего, более высокого порядка (состоящих из числа элементов т + 1). Для этого попарно рассматриваются уже составленные на предыдущем шаге сочетания объектов порядка т, причем такие, которые отличаются в своем составе друг от друга только одним элементом. Такой перебор более удобно реализовать путем упорядоченного расположения элементов в сочетаниях -по возрастанию, и соответствующего упорядоченного перебора таких сочетаний (рисунок 2.19). Наличие связи между единственно различающимися элементами проверяется с помощью исходной матрицы взаимосвязей или, что эквивалентно, наличием данной пары элементов в исходно отобранном, на шаге №1, множестве сочетаний парно взаимосвязанных элементов. Если связь между единственно отличающимися элементами в сравниваемой паре сочетаний присутствует, то соответственно эта пара сочетаний может быть представлена в виде одного кластерного сочетания следующего более высокого порядка т + 1.
Определение структуры потребительских предпочтений к возможным вариантам конфигурации товара
Рассмотрим возможности применения, разработанных методов визуализации общей структуры взаимосвязей и ее нечеткой кластерной подструктуры в виде полных групп в области маркетинговых исследований.
Одним из подходов, используемых при проведении маркетинговых исследований для оценки конкурентоспособности товара, является композиционный подход [19, 20]. При использовании данного подхода производится определение полной полезности товара на основе измерений значимости и полезности определенных его характеристик путем изучения мнений потребителей, учитывающих их индивидуальные предпочтения [62, 67]. Далее осуществляется свертывание оценок полезности отдельных характеристик товара в итоговую, интегральную оценку. Одним из используемых приемов свертки является применение аддитивной модели, при которой интегральная оценка для товара, описываемого N характеристиками, находится по следующей формуле [9, 91]: где N-соответственно количество оцениваемых характеристик товара; Д є [0;1]-относительная важность /-ой характеристики товара, причем 0,є[0тіп;0тах]-оценка z -ой характеристики товара (Отіп-самая низкая оценка, Omwi - самая высокая оценка, зависит от выбранной для исследования шкалы оценивания). ИО(Х) є[Ошіп,Отах]-итоговая интегральная оценка товара (Omin-самая низкая оценка, Отах - самая высокая оценка). Таким образом, при использовании данного способа свертки, интегральная оценка может принимать значения в интервале соответствующем используемому в исследовании интервалу варьирования индивидуальных оценок О,, рассматриваемых характеристик товара. В случае, когда исследование проводится не в полном объеме - только с выявлением оценок характеристик, без определения их степени важности - все характеристики могут приниматься одинаково важными 5. нахождения интегральной оценки принимает вид средней оценки: Следует учитывать, что в таком варианте оценивания товара (без учета важности характеристик), полученная интегральная оценка может оказаться в значительной мере неадекватной по отношению к реальным потребительским предпочтениям.
Характеристики товара могут быть условно разделены на две группы:
1) характеристики, для которых принимаемые значения в плане «лучше/хуже» для потребителя однозначно определены. Например, уровень потребления электроэнергии бытовым электроприбором - чем ниже, тем лучше;
2) характеристики, для которых такой однозначной определенности «лучше/хуже» нет. Например, такие характеристики напитка, как цвет, вкус, запах.
Так, для второй группы характеристик помимо их оценки и степени важности, для потребителя оказывается значимым и вариант компоновки конкретных значений характеристик в товарном продукте.
В рамках композиционного подхода, для определения более адекватной интегральной оценки конкурентоспособности товара, включающего в свои свойства вторую группу характеристик (с целью учета не только индивидуальных оценок и важностей характеристик товара, но также и степени сочетаемости принимаемых ими значений), в формуле определения интегральной оценки может быть предложено применение помимо коэффициентов важности характеристик товара также и коэффициентов сочетаемости, принимаемых ими значений по отношению друг к другу. Таким образом, формула нахождения интегральной оценки преобразуется к следующему виду: где С, є [0;1]-коэффициент сочетаемости значения /-ой характеристики со значениями остальных характеристик второй группы/подгруппы, присутствующих в оцениваемом товаре (0 - совершенная не сочетаемость для потребителя значения /-ой характеристики со значениями остальных характеристик, 1 -полная сочетаемость значений характеристик). Учитывая, что свойства товара в общем случае могут составлять как характеристики первой, так и характеристики второй группы - для характеристик первой группы коэффициенты сочетаемости принимаются равными единице, так как их лучшие значения априори известны и не зависят от сочетаемости с другими значениями характеристик, и в общей интегральной оценке их вклад определяется лишь соответствующими индивидуальными оценками и значимостью. Вторая же группа характеристик в общем случае может быть представлена и несколькими подгруппами. Так, если свойства товара описываются N характеристиками, из которых К составляют характеристики второй группы, то формула интегральной оценки ЯО(3) может быть записана следующим образом:
Таким образом, формула нахождения интегральной оценки конкурентоспособности товара ИО{]] (3.1) является частным случаем формулы ЯО(3) (3.3) для варианта, когда в свойствах товара характеристики второй группы либо отсутствуют вообще, либо степень их сочетаемости не учтена Интересно показать, что с помощью разработанных в диссертации методов визуализации общей структуры взаимосвязей и ее нечеткой кластерной подструктуры в виде полных групп - структура сочетаемости характеристик второй группы может представляться в удобной для восприятия, анализа и принятия управленческих решений форме. Рассмотрим такой практический пример для характеристик дизайна бытовых холодильников.
Для примера используется результаты всероссийского опроса проведенного компанией ОАО "КЗХ Бирюса". Опрос был проведен с помощью анкет (см. приложение В) с вопросами закрытого типа, т.е. ко всем вопросам респондентам давалась возможность дать только конкретный вариант ответа. В рамках приводимого примера используется лишь часть анкет от их общего количества (являющегося репрезентативной выборкой) в связи с тем, что полный объем информации является коммерческой тайной компании.
