Структуризация данных для целей анализа экономических систем

Размещено на http://www.allbest.ru/

Структуризация данных для целей анализа экономических систем

Макаров Е.И., Макаров А.Е.

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

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

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

Исходные данные представляются в виде матрицы размером nхm. Пусть индекс i нумерует объекты, а индекс к нумерует количественные признаки. Далее необходимо выбрать метод вычисления расстояния dij между объектами в многомерном пространстве. Вычисление расстояний между объектами в зависимости от вида метрики производится различными способами - по Евклидову расстоянию, сумме квадратов, Брею - Картису и др [1].

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

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

Уравнение движения частиц в вязкой жидкости имеет вид

где - вектор положения i-ой частицы системы; -потенциальная энергия притяжения выделенной частицы к остальным частицам .

Для задачи анализа структуры произвольных данных m указывает размерность данных. Параметр определяет скорость обучения системы. Выбором масштаба времени t всегда можно положить .

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

Энергию взаимодействия «частиц» следует выбирать парной, что обеспечит аддитивность энергий и сил.

Вид энергии должен обеспечивать притяжение «частиц» (точек).

Притяжение должно исчезать при соединении точек.

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

С целью автоматизации вышеизложенной методики кластеризации была разработана программа AutoClasterisation 1.0 (зарегистрирована в ОФАП №50200401195 от 11.10.2004). В программе реализован механизм кластеризации объектов методом древовидной (иерархической) классификации.

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

С помощью программы AutoClasterisation 1.0 пользователь может проследить образование кластеров и произвести построение дерева классификации n объектов посредством иерархического объединения их в кластеры.

Алгоритм, реализованный в программе AutoClasterisation 1.0, включает следующие шаги.

Ввод данных

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

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

Таблица 1 - Исходные данные для кластеризации

Выбор параметров для кластеризации

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

Нормализация данных

Данные по всем параметрам объектов нормализуются, т.е. принимают сопоставимый вид в диапазоне от 0 до 1:

хji' = (хji - хjmin) / (xjmax - xjmin) ,

где хji' - нормализованное значение j -го параметра i-го объекта; хji - исходное значение j -го параметра i-го объекта; хjmin (xjmax) - минимальное (максимальное) значение j -го параметра в системе данных.

Это необходимо для того, чтобы координаты (параметры) объектов имели сопоставимый вид при проецировании на плоскость.

Таблица 2 - Данные после нормализации

Проецирование объектов на плоскость в виде точки с координатами

В нашем примере осями Ох и Оу являются расстояния до поставщиков №2 и №3, тогда точки для объектов (потребителей) будут иметь следующие координаты: Потребитель №1 (0.561; 0.336); Потребитель №2 (0.427; 0.429); Потребитель №3 (0.037; 1) и т.д.

Замена старых координат объекта на новые

После каждого шага происходит замена старых координат объекта на новые, которые определяются по правилу:

,

где xml'- новое значение l -координаты m -объекта (рассчитывается по каждому объекту для каждой из 6-ти координат); хml - старое значение l -координаты m -объекта; t - скорость обучения (размер шага, в нашем случае t = 0,01); Em - потенциальная энергия (сила) притяжения m -объекта к остальным объектам, рассчитывается для каждого объекта в отдельности по формуле

xki - значение k -координаты i -объекта; Vj - рассчитывается по следующей формуле:

,

После проведенного расчета для всех 26 объектов по 4-м координатам будет сделан 1-ый шаг. Шаги следует повторять до тех пор, пока не произойдет образование нескольких визуально различимых кластеров.

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

Выделение кластеров

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

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

С помощью программы AutoClasterisation 1.0 была проведена группировка потребителей строительного щебня (филиалов ОАО «Воронежавтодор») по близости к поставщикам, с учетом их географического положения, представляющая для них практический интерес

Воронежская область имеет площадь 52,4 тыс. кв. км и простирается на сотни километров. Поэтому потребители территориально тяготеют не только к основному поставщику щебня - ОАО «Павловскгранит» (гранитный щебень), расположенному на Юго-Западе области, но и к ОАО «Новолипецкий металлургический комбинат» (шлаковый щебень), расположенному к северу от области, к карьерам Ростовской области (гранитный, известняковый щебень), расположенных к югу, к ОАО «Лебединский ГОК» Белгородской области (шлаковый щебень), расположенному к западу от области.

Результаты кластеризации, проведенные с помощью программы AutoClasterisation 1.0, дали следующие результаты (см. рисунок).

Северные филиалы ОАО «Воронежавтодор» образуют кластер потребителей, тяготеющих к ОАО «Новолипецкий металлургический комбинат», это: «Воронежский №1», «Воронежский №2», «Воронежский №3», «Новоусманский», «Верхнехавский», «Эртильский», «Панинский», «Аннинский», «Грибановский».

Южные филиалы образуют кластер потребителей, тяготеющих к карьерам Ростовской области (официальный дилер ООО «Руда»): «Кантемировский», «Богучарский».

Западные филиалы образуют кластер потребителей, тяготеющих к ОАО «Лебединский ГОК» Белгородской области: «Хохольский», «Репьевский», «Ольховатский», «Нижнедевицкий», «Острогожский», «Лискинский». графический вычислительный данный координата

Остальные филиалы образуют кластер потребителей, тяготеющих к ОАО «Павловскгранит».

Рисунок 1 - Кластеризация филиалов ОАО «Воронежавтодор» по близости к поставщикам

Литература

1. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Исследование зависимостей. Справочное издание под ред. Айвазяна С.А. - М.: Финансы и статистика, 1985. - 471с.

2. Бендат Дж., Пирсол А. Применение корреляционного и спектрального анализа.- М.: Мир, 1979.- 311с.

Размещено на Allbest.ru