Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

A METHOD OF GROUPING BASIC INFORMATION FOR INFORMATION PROCESSES OF COMPLEX SYSTEMS

Sumin V.I. 1 Dybova M.A. 1 Smolentseva T.E. 2
1 FSE VPO «Voronezh Institute of the Federal penitentiary service of Russia»
2 FGBOU VPO «Lipetsk State Technical University»
This article discusses the technique of grouping objects for information processes of complex systems into classes, which are most similar in their characteristics to the objects. The process of grouping data iterative methods, and the use of iterative cluster analysis method for grouping objects of basic information for information processes of complex systems based on the values of the analyzed characteristics, comprising the following steps: forming the source partition to the desired number of classes to check if the object class, the calculation of the threshold value, which is determined by the identity of the object class. Determined the source data partitioning objects into classes.
iterative method of cluster analysis
basic information
the center of gravity of the clusters
1. Vagin V.N. Golovina E.Ju. Dostovernyj i pravdopodobnyj vyvod v intellektual’nyh sistemah. M. :Fizmatlit, 2004.
2. Zhiljakov E.G., Lomazov V.A., Lomazova V.I. Komp’juternaja klasterizacija sovokupnosti additivnyh matematicheskih modelej vzaimosvjazannyh processov // Voprosy radiojelektroniki. Ser. JeVT. 2011. Vyp. 1. рр. 115–119.
3. Zhuravlev Ju.I., Rjazanov V.V., Sen’ko O.V. «Raspoznavanie». Matematicheskie metody. Programmnaja sistema. Prakticheskie primenenija. M.: Fazis, 2006.
4. Zhiljakov E.G., Skubilin V.V. O nekotoryh modeljah kratkosrochnogo prognozirovanija // Nauchnye vedomosti Belgorod. gos. un-ta. Ser. Istorija Politologija Jekonomika Informatika. 2013. no. 22 (165). Vyp. 28/1.
5. Mendel’, I.D. Klasternyj analiz. M.: Finansy i statistika, 1988. 176 р.
6. Sumin V.I., Smolenceva T.E. Modelirovanie obuchenija s ispol’zovaniem vremennyh rjadov nabljudenij: monografija. M.: Izdatel’sko-poligraficheskij centr «Nauchnaja kniga», 2014. 104 р.
7. Sumin V. I., Cvetkov V.V. Ob algoritmah i modeljah, dannyh v reshenijah zadach prinjatija reshenija // Nauchnye vedomosti Belgorod. gos. un-ta. Ser. Istorija Politologija Jekonomika Informatika. 2010. no. 13 (84). Vyp. 15/1. рр. 120–128.

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

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

Основной задачей кластерного анализа является определение групп схожих объектов в выборке данных (кластеров). Сходство количественных данных оценивается на основе понятия метрики при определении точки пространства на основе метрического расстояния между ними. Причем размерность пространства определяется числом характеристик, которые описывают объект [5].

Группа схожих объектов при выборке данных использует следующие кластерные методы:

– иерархические алгомеративные и дивизимные методы;

– итеративные методы группировки;

– факторные методы;

– поиск модальных значений плотности;

– сгущений;

– использования теории графов.

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

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

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

На рисунке представлен процесс группирования данных итеративными методами.

Рассмотрим применение итеративного метода кластерного анализа к процессу группирования объектов базовой информации для информационных процессов сложных систем на основе значений параметров анализируемых характеристик [6].

Представим базовую информацию, циркулирующую в системе, в виде множеств

{Pi,j, Ai, Bj},

где sumin01.wmf – индекс объектов, носителя первичной информации; sumin02.wmf – индекс выбранных или всех характеристик объектов; Pi,j – количественное значение j-й характеристики i-го объекта; Ai – наименование i-гo объекта; Вj – наименование j-й характеристики.

Все элементы Pi,j необходимо с точностью TI разбить на Кэ классов.

Значение TI определяет количество итераций. При увеличении количество итераций уменьшается количество шагов, но в то же время уменьшается точность разбиения, определяемая ЛПР. Значение Кэ также определяется ЛПР в зависимости от требуемой точности получения классификации разбиения (меньше Кэ – грубее классификация) [3, 7].

Чтобы в процессе исходного разбиения получить требуемое количество классов не меньше величины Кэ необходимо ввести масштабный коэффициент L. Масштабному коэффициенту L вначале присваивается значение равное 1.0. В том случае, если увеличить количество классов, L уменьшается и наоборот.

Алгоритм разбиения на классы представлен ниже:

0. Для формирования исходного разбиения на нужное число классов необходимо:

Сформировать множество {ri, di, ai, ki}размерностью I = 1,I:

ri – смешанный момент корреляции Карла Пирсона или угловая мера

sumin03.wmf

где sumin04.wmf

di – евклидово расстояние от начала координат до Pi,j

sumin05.wmf

ai – индекс объекта в соответствии с Pi,j; ki – номер класса, к которому будет принадлежать i-й объект, первоначально все ki = 0.

1. Первоначальное разбиение на классы.

1.1. Для начала итеративного процесса:

– первоначально Ck = 0, k1 = 1, i = 1, Ci = 1;

– вычисляется среднее расстояние s между всеми элементами di:

sumin06.wmf

1.2. Вычисляется пороговое значение α, по которому определяется принадлежность i-го объекта к Ck классу:

– α = s∙L;

– i = Ci.

1.3. Вычисляется расстояние между очередным элементом и следующим:

Δd = di – d(i + 1).

1.4. Проверяется принадлежность i + 1 – го объекта к классу Ck.

Если Δd ≤ α, то k(i + 1) = Ck, i = i + 1 и:

– если i ≤ I,то переход к пункту 1.3;

– если i > I, то переход к пункту 1.5.

Если Δd > α, то Ck = Ck + 1, i = i + 1, Ci = i и переход к пункту 1.2.

1.5. Объединяются с использованием смешанного момента корреляции Карла Пирсона ri.

1.6. В начале:

– элементы {ri, ki} переупорядочиваются по возрастанию элементов ki и ri соответственно;

– первоначально определяются Ck = 1, Ckt = 1, k1 = 1, i = 1, Ci = 1.

1.7. Вычисляется пороговое значение α, по которому определяется принадлежность i + объекта Ci классу:

α = (ri – r(i + 1))∙L.

Если α = 0, то i = i + 1 и а вычисляется заново.

Если sumin07.wmf, то sumin08.wmf и i = Ci.

1.8. Проверяется, закончились ли объекты Ckt класса.

Если Ckt = ki, то переход к пункту 1.9.

ЕслиCkt ≠ ki , то Ckt = Ckt + 1, Ck = Ck + 1, i = i + 1, Ci = I и:

– если i > I, то переход к пункту 1.11;

– если i ≤ I, то переход к пункту 1.7.

1.9. Вычисляется расстояние между очередным и следующим элементами

Δr = ri – r(i + 1).

1.10. Проверяется принадлежность i + объекта к Ck классу:

Если Δr ≤ α , то k(i + 1) = Ck, i = i + 1, и:

– если i ≤ I, то переход к пункту 1.9;

– если i > I, то переход к пункту 1.11.

Если Δd > α, то Сk = Ck + 1, i = i + 1, Ci = i и переход к пункту 1.7.

1.11. Результаты Pi,j разбиты на «К» классов.

Если К = Кэ, то требуемое разбиение получено и переход к пункту 2 [1].

2. Если К > Кэ, то увеличивается параметр L и переход к пункту 1.1. Если К < Кэ, то уменьшается параметр L и переход к пункту 1.1.

3. Вычисляются sumin09.wmf – центры тяжести полученных классов:

sumin10.wmf sumin11.wmf – индекс полученных классов.

4. Проверяется, находится ли каждый объект в ближайшем классе.

4.1. Первоначально i = 1, n = 0.

4.2. Вычисляется квадрат отклонения объекта ai от центра тяжести всех классов:

sumin12.wmf

где sumin13.wmf – индекс полученных классов; sumin14.wmf – индекс характеристики, участвовавшей в формировании результата Pi,jai объекта.

4.3. Если min(Fkai) достигается при k = ki, то объект ai находится в ближайшем классе, изменения его класса не происходит.

Если min(Fkai) достигается при k ≠ ki, то объект ai не находится в ближайшем классе, поэтому ki = k (класс объекта заменился на ближайший) и n = п + 1 (объект ai перешел в другой класс).

4.4. Увеличивается i = i + 1 и проверяется:

– если i > I, то закончился просмотр всех объектов и переход к пункту 5;

– если i ≤ I, то переход к пункту 4.2.

pic_4.wmf

Процесс группирования данных итеративными методами

 

5. Если sumin15.wmf то требуемая точность итеративного процесса не достигнута и переход к пункту 2.

Если sumin16.wmf то требуемая точность итеративного процесса достигнута. Получено окончательное разбиение Pi,j по классам.

К исходным данными разбиения объектов на классы относятся: sumin17.wmf – индекс объекта; sumin18.wmf – индекс характеристики объекта; Pi,j – количественное значение j-й характеристики i-го; Ai – наименование i-го объекта; Bj– наименование j-й характеристики; TI – точность разбиения в процентах; Кэ – количество классов разбиения.

Результатом разбиения объектов на классы являются: К – количество полученных классов; sumin19.wmf – центры тяжести полученных классов; ki – номер класса, к которому принадлежит i-й объект; ai – индекс объекта в соответствии с Pi,j.

Рецензенты:

Филатов Г.Ф., д.ф.-м.н., профессор кафедры математики Военного учебного научного центра Военно-воздушных сил, «Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина», г. Воронеж;

Чопоров О.Н., д.т.н., профессор, проректор по научной работе Воронежского института высоких технологий, г. Воронеж.

Работа поступила в редакцию 02.03.2015.