Объективный кластерный анализ данных на основе МГУА
Розглядається проблема об’єктивного кластерного аналізу даних на основі самоорганізації кластеризацій відповідно до принципів МГУА. Запропоновано єдиний підхід до класифікації методів вибору інформативних ознак і пошуку найкращої кластеризації. Розглянуто нові зовнішні критерії оцінки якості кластер...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/209124 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Объективный кластерный анализ данных на основе МГУА / Л.В. Сарычеваs // Проблемы управления и информатики. — 2008. — № 2. — С. 86-104. — Бібліогр.: 33 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860060295398948864 |
|---|---|
| author | Сарычева, Л.В. |
| author_facet | Сарычева, Л.В. |
| citation_txt | Объективный кластерный анализ данных на основе МГУА / Л.В. Сарычеваs // Проблемы управления и информатики. — 2008. — № 2. — С. 86-104. — Бібліогр.: 33 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглядається проблема об’єктивного кластерного аналізу даних на основі самоорганізації кластеризацій відповідно до принципів МГУА. Запропоновано єдиний підхід до класифікації методів вибору інформативних ознак і пошуку найкращої кластеризації. Розглянуто нові зовнішні критерії оцінки якості кластеризації та міри подібності між кластеризаціями. Розроблено алгоритм об’єктивного кластерного аналізу просторово-часових даних.
The problem of objective cluster analysis of the data is considered on the basis of self-organizing of clusterizations according to GMDH principles. The unified approach to classification of selection methods of informative features and search of the best clusterization is proposed. New external criteria of a clusterization quality estimation and measures of similarity between clusterizations are considered. The algorithm of objective cluster analysis of the spatially-temporary data is developed.
|
| first_indexed | 2025-12-07T17:04:03Z |
| format | Article |
| fulltext |
© Л.В. САРЫЧЕВА, 2008
86 ISSN 0572-2691
УДК 519.711:004.8:681.3
Л.В. Сарычева
ОБЪЕКТИВНЫЙ КЛАСТЕРНЫЙ
АНАЛИЗ ДАННЫХ НА ОСНОВЕ МГУА
Введение
«Кластерный анализ — совокупность математических методов, предназна-
ченных для формирования относительно «отдаленных» друг от друга групп
«близких» между собой объектов по информации о расстояниях или связях (ме-
рах близости) между ними» (Статистический словарь, 1989).
Класс методов и алгоритмов кластерного анализа обширен — агломеративные
и дивизимные алгоритмы иерархической кластеризации, k-средних, ISODATA,
FOREL, PAM, KLARA, CHAMELEON, Объективной Компьютерной Кластериза-
ции (ОКК) и др. [1–9]. В каждом конкретном случае применяются методы, учиты-
вающие особенности исходных данных: объем выборок, число признаков, апри-
орную информацию и т.д. Число кластеров, на которое нужно разделить объекты,
и число признаков объектов в большинстве алгоритмов являются входными пара-
метрами.
Разнообразие алгоритмов кластер-анализа приводит к тому, что на одних и
тех же данных порождаются, вообще говоря, различные классификации. Поэтому
требуется валидация структуры (модели, группировки), которую кластерный ана-
лиз вносит в данные, необходимо анализировать такие свойства кластеров, как
плотность, дисперсия, размеры, форма, отделимость. Однозначные количествен-
ные характеристики этих свойств в литературе отсутствуют. Большинство уни-
версальных пакетов анализа данных (Statistica, MatLab, SPSS), предлагая широкий
спектр методов кластеризации, не имеют в своем арсенале процедур проверки ка-
чества полученного решения.
Взгляд на кластеризацию как на модель позволяет перенести в теорию кла-
стерного анализа все основные понятия и приемы теории самоорганизации мо-
делей на основе метода группового учета аргументов (МГУА) [9, 10]. Самоор-
ганизацией кластеризаций называется их перебор в целях выбора оптимальной
кластеризации. Чем больше неточность данных — тем проще оптимальная кла-
стеризация (сложность измеряется числом кластеров и числом признаков).
В алгоритмах объективного кластерного анализа кластеры образуются по внут-
реннему критерию (чем сложнее, тем точнее), а оптимальное их число и состав
ансамбля признаков определяются по внешнему критерию (образующему мини-
мум в области недоусложненной кластеризации, оптимальной для заданного
уровня дисперсии помех).
Цель данной публикации — разработка методов объективного кластерного
анализа данных в соответствии с основными принципами МГУА: многоэтапность
поиска лучшей кластеризации, оценивание качества кластеризации с помощью
внутреннего и внешнего критериев, использование наборов методов образования
кластеров и выбора информативных признаков, мер сходства между двумя объек-
тами, объектом и кластером, двумя кластерами, двумя кластеризациями.
1. Постановка задачи
Пусть ijx — измерения признаков, характеризующих заданное множество
объектов-наблюдений ni ,,2,1( = — номер наблюдения, n — число наблюдений,
mj ,,2,1 = — номер признака, m — число признаков). Исходные данные пред-
Проблемы управления и информатики, 2008, № 2 87
ставляют собой матрицу )( jix типа объект-свойство: T
21 ),,,( njjj
j xxx =X —
вектор-столбец значений j-го признака для n объектов; ),,,( 21 imiii xxx =X —
вектор-строка значений m признаков i-го объекта.
Кластеризацией },,,,{ 21 kKKKK = ,1 nk ≤≤ множества X называется се-
мейство непустых, попарно непересекающихся подмножеств (кластеров) ,qK
,,,2,1 kq = множества X, объединение которых совпадает с X:
,21 XKKK k =∪∪∪ ,∅=∪ ji KK
,ji ≠ ,∅≠qK .,,2,1,, kqji =
Пусть Φ — множество всех допустимых разбиений (кластеризаций) заданно-
го множества X. Наилучшей по критерию качества J(K) является кластеризация,
для которой
)(maxarg
Ф
KJK
K⊆
∗ = (или )).(minarg
Ф
KJK
K⊆
∗ (1)
Получение по выборочным наблюдениям кластеризации (1) с последующим
анализом ее свойств — задача кластерного анализа в узком смысле. Если априор-
но неизвестно, какие именно компоненты из множества X (оптимальное множе-
ство признаков) следует включать в критерий качества кластеризации объектов
множества X, то говорят о задаче кластерного анализа, поставленной в широком
смысле.
Число кластеров k может быть заранее неизвестным при постановке задачи
кластеризации как в узком, так и в широком смысле.
Для решения задачи кластеризации необходимо:
а) дать определение кластера, т.е. указать свойства, общие для всех объектов
отдельного кластера (мера сходства между объектами);
б) задать способ образования кластеров (сортировка, перегруппировка, объ-
единение, разбиение, добавление, поиск) [3, 4, 8];
в) указать критерий J качества кластеризации (мера сходства между классами);
г) организовать движение к минимуму (максимуму) критерия J (при этом
определяется ансамбль признаков и число кластеров).
Отметим, что способы образования кластеров, выбора оптимального под-
множества признаков, меры сходства (между объектами, кластерами, объектом
и кластером, кластеризациями) и методы поиска оптимума критериев, как пра-
вило, независимы между собой и могут применяться в различных сочетаниях
(рис. 1). Поэтому можно предложить различные методы решения задачи клас-
теризации.
Критерий качества
кластеризации
• внешний
• внутренний
Способ выбора
оптимального
подмножества
признаков
Способ выбора
числа кластеров
Меры сходства
между
• объектами
• кластерами
• объектом и кластером
• кластеризациями
Методы
кластеризации
Способ образования
кластеров
• сортировка
• перегруппировка
• объединение
• разбиение
• добавление
• поиск
Рис. 1
88 ISSN 0572-2691
Объективной является кластеризация ,Φ⊆∗K «которая меньше других от-
личается от экспертной по числу кластеров, используемых переменных и несоот-
ветствий» [11].
Требуется: по выборке Z найти объективную кластеризацию, т.е. число k и
состав объективно существующих кластеров .,,, 21
kKKK
2. Меры сходства
В табл. 1 приведены меры сходства между двумя объектами, двумя класте-
рами, объектом и кластером.
Таблица 1
Меры сходства
между объектами,
d(Xi, Xj)
между кластерами,
d(Ki, Kj)
между объектом
и кластером, d(X, Ki)
евклидово расстояние
2/1
1
2
E
)(
),(
−=
=
∑
=
m
l
jlil
ji
xx
d XX
ближнего соседа
),(min
),(
,
min
ml
KK
ji
d
KKd
jmil
XX
XX ∈∈
=
=
ближайшего соседа
),(min
),(min
j
K
i
d
Kd
ij
XX
X
X ∈
=
=
взвешенное евклидово
расстояние
2/1
1
2
W
)(
),(
−ω=
=
∑
=
m
l
jlill
ji
xx
d XX
дальнего соседа
),(max
),(
,
max
ml
KK
ji
d
KKd
jmil
XX
XX ∈∈
=
=
функция меры близости
i
ij
n
j
K
i
d
Kd
/1
FMC
),(
),(
=
=
∏
∈
XX
X
X
потенциальная функция
,0
,)),(1(
),(
12
E
P
>α
α+=
=
−
ji
ji
d
d
XX
XX
среднего соседа
∑ ∑
∈ ∈
=
=
il jmK
ml
Kji
ji
d
nn
KKd
X X
XX ),(1
),(mean
расстояние Махаланобиса
)()(
),(
1T
M
iii
iKd
µ−µ−=
=
− XCX
X
или
)),((exp
),(
2
E
P
ji
ji
d
d
XX
XX
α−=
=
или
расстояние между центрами
тяжести
),(),( Ec jiji dKKd µµ=
потенциальная функция
∑
∈
Π=
=
ij K
j
i
i
d
n
Kd
X
XX
X
),(1
),(P
),(
)),((sin
),(
2
E
2
E
P
ji
ji
ji
d
d
d
XX
XX
XX
α
α
=
=
потенциальная функция
∑ ∑
∈ ∈
=
=
il jmK
ml
Kji
ji
d
nn
KKd
X X
XX ),(1
),(
Π
P
угловая мера подобия
i
ij
n
j
K
iKd
/1
PSI
),(sin
),(
=
=
∏
∈
XX
X
X
угловая мера
⋅
⋅
=
=
ji
ji
jid
XX
XX
XX
arccos
),(
расстояние Махаланобиса
)()(
),(
1T
M
jiji
ji KKd
µ−µµ−µ=
=
−C
расстояние до «центра
тяжести» кластера
),(),( Ec ii dKd µ= XX
где
i
Kj
j
ji
n
X
X
∑
∈
=µ
1 — вектор средних кластера K j, lω — весовой коэффициент, Сi — ковариацион-
ная матрица кластера K i, С=С i=С j
Выбор меры сходства между кластерами влияет на вид выделяемых геомет-
рических группировок объектов в пространстве признаков. Так, алгоритмы, осно-
ванные на расстоянии ближайшего соседа, хорошо работают в случае группиро-
вок, имеющих сложную, в частности, цепочечную структуру. Расстояние дальне-
го соседа применяется, когда искомые группировки образуют в пространстве
признаков шаровидные облака. Промежуточное место занимают алгоритмы, ис-
пользующие расстояния центров тяжести и среднего соседа, которые лучше всего
работают в случае группировок эллипсоидной формы.
Проблемы управления и информатики, 2008, № 2 89
Для оценки близости между двумя различными кластеризациями =K
},,,,{
121 kKKK = и },,,{
221 kQQQQ = множества объектов X можно ис-
пользовать меру сходства [12]
,
2
1
2
1
),(
21
2121
1
2
1
2
2
11
2
1
2
1
+
−
+
=
∑∑
∑∑∑∑
==
====
k
i
i
k
i
i
ji
k
j
k
i
i
k
i
i
k
i
QK
QKQK
QKd
(2)
где k1, k2 — число кластеров в кластеризациях K и Q; ,iK ,jQ ;,,2,1 1ki =
,,,2,1 2kj = — число элементов в кластерах iK и .jQ
Величина d(K, Q) принимает значения от 0 до 1: d(K, Q)=0 — при cовпа-
дающих разбиениях в кластеризациях K и Q; d(K, Q)=1 — при полностью несов-
падающих.
Например, пусть для множества X={a, b, c, d, e, f, g, h, l, m} получено две
кластеризации K и Q:
)};,(),,(),,,(),,,{( mlhqfedсbaK = ;41 =k ;321 == KK ;243 == KK
)};,,,(),,,,(),,{( mlhgfedcbaQ = ;32 =k ;21 =Q .43 =Q
Тогда ;262233 222224
1
=+++=∑
=
i
i
K ;36442 22223
1
=++=∑
=
i
i
Q
},,{11 bаQK = ;211 =QK ,13 ∅=QK ;013 =QK
},{21 cQK = ;121 =QK ,23 ∅=QK ;023 =QK
,31 ∅=QK ;031 =QK },,{33 hgQK = ;233 =QK
,12 ∅=QK ;012 =QK ,14 ∅=QK ;014 =QK
},,,{22 fedQK = ;322 =QK ,24 ∅=QK ;024 =QK
,32 ∅=QK ;032 =QK },,{34 mlQK = .234 =QK
;2222312 222223
1
4
1
=++++=∑∑
==
ji
ji
QK .3,0
31
2236)0,5(26),( ≈
−+
=QKd
Рассмотрим всевозможные пары объектов Xji ⊂),( XX и определим:
а) число таких пар, когда оба объекта принадлежат одному кластеру в K и
одному кластеру в Q:
,),(,
1
1
, ∑∑
=
−
=
α=
n
ij
jiQK
n
i
QKa XX
⊂⊂
=α
случае;противномв0
,),(,),(если,1
),(,
sjiqji
jiQK
QK XXXX
XX
б) число таких пар, когда оба объекта принадлежат одному кластеру в K и
разным кластерам в Q:
90 ISSN 0572-2691
∑∑
=
−
=
β=
n
ij
jiQK
n
i
QKb ),,(,
1
1
, XX
≠⊂⊂⊂
=β
случае;противномв0
,,,,),(если,1
),(,
slQQK sjliqji
jiQK
XXXX
XX
в) число таких пар, когда оба объекта принадлежат одному кластеру в Q и
разным кластерам в K:
∑∑
=
−
=
γ=
n
ij
jiQK
n
i
QKc ),,(,
1
1
, XX
≠⊂⊂⊂
=γ
случае;противномв0
,,,,),(если,1
),(,
gqKKQ gjqisji
jiQK
XXXX
XX
}.,,1{,},,,1{, 21 klskgq ⊂⊂
На основе этих величин можно вводить меры сходства, например:
,),(
,,,
,
QKQKQK
QK
G cba
a
QKd
++
=
.),(
,,
,
,,
,
QKQK
QK
QKQK
QK
M ca
a
ba
a
QKd
+
⋅
+
=
Чем выше значения величин ),,( QKdG ),,( QKdM тем меньше различаются
кластеризации.
3. Выбор информативных признаков и поиск наилучшей кластеризации:
единый подход к классификации методов
Пусть имеется k классов объектов: .,,, 21 kKKK Каждый объект описыва-
ется m признаками. Класс ,lK ,,,2,1 kl = содержит ln объектов:
.21 nnnn k =+++
Под выбором информативных признаков понимают сужающее отображе-
ние F:
},{}{ 1mFm XX → ,1 mm < ),,,,( 21 kKKKFF =
при котором достигается экстремум некоторого функционала качества ).(FJ X
Каждому такому отображению можно поставить в соответствие вектор
),...,, ,( 21 mvvv=v
где ,1=iv если iX входит в состав выбираемых признаков, и 0=iv в противном
случае. Тогда функционал )(FJ X можно рассматривать как функцию ),(
1
vmg
заданную на вершинах единичного гиперкуба [0, 1]m. Из всех вершин нужно
найти такую, на которой достигается экстремум ).(
1
vmg
Математическая постановка задачи выбора информативной подсистемы при-
знаков из исходной может быть представлена в виде
;min)(
1 D
mg
⊂
→
v
v },10;{ ∨=== j
m vRD v (3)
Проблемы управления и информатики, 2008, № 2 91
если размерность 1m искомой подсистемы не определена, или в виде
;min)(
1 G
mg
⊂
→
v
v ,; 1
1
1
=⊂= ∑
=
mvDG j
m
j
v (4)
если размерность искомой подсистемы задана. Элементами множества D являют-
ся вершины решетки разбиений — единичного m-мерного гиперкуба. На рис. 2
приведен пример гиперкуба выбора признаков для .4=m
1111
9
11 13
13
13
12 17
18 20 18
17
10 16
16 16
0111
0011
0001 0010 1000 0100
1001
1011
0110 0101
1101 1110
1100 1010
0000
Рис. 2
Особенность задачи состоит в том, что в большинстве случаев функция мно-
гоэкстремальна и не может быть исследована аналитически, поэтому для нахож-
дения ее экстремума используются различные процедуры перебора вершин с те-
кущей оценкой их ценности. Критерий качества определяется, исходя из априор-
ных данных и предварительного анализа совокупности признаков.
Для нахождения оптимального подмножества признаков в общем случае из-
вестен только один метод — полный перебор всевозможных подмножеств исход-
ного множества признаков. Число вариантов при этом огромно — для выбора
наилучшего подмножества 1m признаков из общего числа m признаков требуется
)!(!
!
11 mmm
m
−
сравнений значений функции ),(
1
vmg поэтому на практике приме-
няют субоптимальные методы поиска, сокращающие перебор вариантов.
В зависимости от способа построения алгоритма, задающего последователь-
ность прохождения вершин в гиперкубе (см. рис. 2), методы выбора признаков
можно разделить на следующие группы.
1. Последовательный перебор вариантов [13]:
а) полный перебор (РР);
б) ранжировка (RA);
в) последовательное присоединение (AD);
г) последовательное отбрасывание (EL);
д) различные комбинации последовательного присоединения и последова-
тельного отбрасывания (ADEL, ELAD);
е) двусторонний поиск и др.
2. Случайный поиск и его модификации [14]:
а) обычный случайный поиск (метод Монте-Карло) (SP);
б) случайный поиск с адаптацией (SPA);
в) случайный поиск с возвратом;
г) модифицированный случайный поиск с адаптацией и др.
92 ISSN 0572-2691
3. Комбинированные методы [15]:
а) метод ветвей и границ;
б) минимаксный метод;
в) метод синтеза;
г) beam-поиск;
д) (r, s)-поиск и др.
4. Генетические методы (комбинаторика и случайный поиск) [16]:
а) при доминирующем влиянии оператора скрещивания;
б) при доминирующем влиянии оператора мутации.
Сравнение методов AD, EL, ADEL, RA, SP, SPA проведено в [17]. Типичные
пути поиска оптимального подмножества приведены на рис. 3, где а — полный пе-
ребор; б — ранжировка; в — последовательное присоединение; г — последователь-
ное отбрасывание; д — двусторонний поиск; е — последовательное присоединение
и отбрасывание; ж — метод ветвей и границ; з — beam-поиск; и — (r, s)-поиск.
а
г
ж з и
д е
б в
Рис. 3
В задаче выбора признаков и в задаче поиска наилучшей кластеризации в ка-
честве исходных данных используется одна и та же таблица «объект-признак».
Если под поиском (выбором) наилучшей кластеризации понимать сужающее
отображение Φ множества исходных объектов X на множество кластеров K:
},{}{ Ф
kn KX →
,nk ≤ ),,,,( 21 mXXX Φ=Φ
при котором достигается экстремум некоторого функционала качества ),(ΦXI то
каждому такому отображению можно поставить в соответствие разбиение W мно-
жества исходных объектов. Тогда )(ΦXI можно рассматривать как функцию
),(Wqk заданную на вершинах решетки разбиений исходного множества объек-
тов. Из всех вершин нужно найти ту, на которой достигается экстремум ).(Wqk
Математическую постановку задачи поиска кластеризации можно предста-
вить в виде, аналогичном (3), если число кластеров не задано, или в виде, анало-
гичном (4), если число k кластеров задано. Пример решетки разбиений для
случая n = 4 представлен на рис. 4. Поэтому существует соответствие между ме-
тодами выбора информативных признаков и методами поиска наилучшей клас-
теризации. Например, методу последовательного присоединения соответствует
построение дивизимного иерархического дерева, а методу последовательного от-
брасывания — агломеративного.
Такой подход к классификации методов кластеризации и методов выбора
признаков, в котором и кластеризация, и выбор признаков являются задачами
дискретной оптимизации на вершинах решетки разбиений, позволяет увидеть
Проблемы управления и информатики, 2008, № 2 93
новые направления развития этих методов. Например, при построении иерар-
хических деревьев кластеризации можно навстречу друг другу строить два де-
рева: дивизимное и агломеративное; там, где они встретятся, и будет опти-
мальная кластеризация [18]. Такое построение соответствует двустороннему по-
иску (см. рис. 3, д). Число кластеров k определяется из условия максимального
сходства между кластеризациями K и Q, полученными соответственно диви-
зимным и агломеративным алгоритмами:
},1,,3,2{)),(),((minarg −∈=∗ nkkQkKdk
k
(5)
где d(K, Q) вычисляется по формуле (2).
},,,{ 4321 XXXX
},,{},{ 4321 XXXX
},,{},{ 4312 XXXX
},,{},{ 4213 XXXX },,{},{ 3214 XXXX
},{},{},{ 4231 XXXX
},{},{},{ 4321 XXXX
},{},{},{ 3241 XXXX
},{},{},{ 4132 XXXX
},{},{},{ 3142 XXXX
},{},{},{ 2143 XXXX
},{},,{ 4231 XXXX
},{},,{ 3241 XXXX
},{},,{ 4321 XXXX
},,,{ 4321 XXXX
Рис. 4
4. Критерии оценки качества кластеризации
В [19–22] даны определения внутренних и внешних критериев МГУА, при-
ведена классификация внешних критериев.
Общность принципов самоорганизации моделей и кластеризаций позволяет
определить для кластеризации внешние критерии (аналогичные критериям точно-
сти, непротиворечивости и другим) для исследования валидности кластеров в за-
висимости от используемых данных.
Для обоснования способа разбиения и выбора критерия оценки качества кла-
стеризации рассмотрим гипотетическую ситуацию, когда число k° и состав объек-
тивно существующих кластеров
kKKK ,,, 21 известны, т.е. известна объектив-
ная кластеризация }.,,,{ 21
kKKKK =
Введем предположения:
П1) ;minmax Rr <
П2) ,,,2,12
kglng =∀=
где ,maxmax q
q
rr = };,,2,1{
kq∈ nq — число объектов в кластере Kq; =qr
),(max
,
ki
K
d
qki
XX
XX ∈
= — расстояние между самыми удаленными объектами в кла-
стере Kq; ,min ,
,
min qg
qg
RR = ;qg ≠ },,,2,1{,
kqg ∈ ),(, qgqg KKdR = — рас-
стояние между кластерами Kg и Kq.
94 ISSN 0572-2691
Исходную выборку X, содержащую n объектов, разобьем на две непересека-
ющихся равномощных подвыборки A и B размерности (n /2)×m, A ∩B=Ø,
A ∪B=X , .][ TTT
BA XXX =
А. Вычисляем n (n–1)/ 2 расстояний d(Xi, X j ) между объектами Xi и X j,
,1,,2,1 −= ni .,,2,1 niij ++=
Б. Определяем объекты Xq и Xs такие, что ).,(min),(
,
ji
ji
sq dd XXXX =
В. Объект Xq зачисляем в подвыборку А, а ближайший к нему объект Xs —
в подвыборку В.
Г. Повторяем шаги Б, В для оставшихся объектов и расстояний между ни-
ми, пока все объекты не будут зачислены в A и B. Подвыборка А содержит объ-
екты с номерами ,,,, 2/21 nqqq а подвыборка В — объекты с номерами
2/21 ,,, nsss (n предполагается четным, при нечетном n какой-либо один объект
последней пары рассматривается дважды).
Будем параллельно вести кластеризацию для подвыборки В и для подвыбор-
ки А и рассчитывать сумму внутрикластерных расстояний на В по результатам
кластеризации на А и, наоборот, — такую же величину на А по результатам кла-
стеризации на В (соответствие объектов подвыборок А и В установлено их при-
надлежностью одной паре):
).,(),(
,1,1
B
q
B
q
A
n
ji
k
q
A
q
A
q
B
n
ji
k
q
AB jidjidJ
B
q
B
q
B
q
B
A
q
A
q
A
q
A
∑∑∑∑
==
+= (6)
Здесь q — номер кластера, kA — текущее число кластеров в выборке А; kB — те-
кущее число кластеров в выборке В; A
q
A
q ji , — номера объектов в выборке А;
B
q
B
q ji , — номера объектов в выборке В; A
qn — текущее число объектов в кластере
Kq в выборке А; B
qn — текущее число объектов в кластере Qq в выборке В;
),( A
q
A
q
B jid — расстояние между двумя объектами в выборке В, первый из которых
имеет в паре объект ,A
qi а второй — объект ,A
qi ),( B
q
B
q
A jid — расстояние между
двумя объектами в выборке А, первый из которых имеет в паре объект ,B
qi а вто-
рой — объект .B
qj
Можно доказать, что если в качестве меры сходства между двумя объектами
взято евклидово расстояние, а в качестве меры сходства между объектом и кла-
стером, двумя кластерами взято расстояние ближайшего соседа, кластеризация
проводится по агломеративному алгоритму, в котором формула пересчета рассто-
яний от объединенного кластера 21 SS ∪ до других кластеров S зафиксирована
в виде
),),(),(),(),((
2
1),( 212121 SSdSSdSSdSSdSSSd −−+=∪
выполнены П1 и П2, то критерий JАВ (6) имеет минимум при k=kº.
Аналогично внешним критериям МГУА для моделей (формулы (12), (13)
в [23]), используя в качестве RSS сумму внутрикластерных расстояний, можно
определить внешние критерии для кластеризации:
,RS
AB
ABX
J
JJJ −
= (7)
Проблемы управления и информатики, 2008, № 2 95
,
AB
X
D J
J
J =
где XJ — сумма внутрикластерных расстояний на выборке X=A∪B.
Для поиска кластеризации, в которой центры соответствующих друг другу на
подвыборках А и В кластеров согласованы, служит критерий
,)(1 2
11
B
ij
A
ij
m
j
k
i
R xx
mk
J −
⋅
= ∑∑
==
(8)
где k = kA = kB — текущее число кластеров в выборках А и В; m — число коорди-
нат, B
ij
A
ij xx , — j-координаты центров i-х кластеров, построенных на А и В.
В качестве внешних критериев можно использовать также коэффициенты
Рэнда, Жаккарда, Фолка-Мэллоу [24]. Чем выше их значения, тем более вероятна
полученная кластерная структура.
Любой метод кластеризации имеет свой внутренний критерий. Большинство
известных методов кластеризации основано на применении внутренних (точност-
ных либо информационных) критериев. Назовем наиболее распространенные
внутренние критерии оценки качества кластеризации [6, 7, 25, 26]:
1) критерий внутрикластерных дисперсий (применяется в методе k-средних)
,),(
1
2
E1 ∑ ∑
= ∈
µ=
k
j
ji
K
dJ
ji
X
X
(9)
где i
Kj
j
ji
n
X
X
∑
∈
=µ
1 — центр тяжести кластера Kj; nj — число объектов в нем;
2) критерий попарных внутрикластерных расстояний между объектами
);,(1 2
E
,1
2 gi
Kj
k
j
d
n
J
jgi
XX
XX
∑∑
∈=
= (10)
3) критерий межкластерного разброса объектов (чем больше величина J3
),10( 3 << J тем бóльшая часть общего разброса объектов объясняется межклас-
совым разбросом и тем лучше качество разбиения):
,13 S
WJ −= (11)
где:
;
1
∑
=
=
k
j
jWW ∑
∈
µ=
ji K
jij dW
X
X ),(2 — внутрикластерный разброс;
∑
=
=
n
i
idS
1
2 ),( XX — общее рассеивание;
∑
=
=
n
i
in 1
1 XX — общий центр тяжести;
4) обобщенная внутрикластерная дисперсия:
= ∑
=
j
k
j
jnJ C
1
4 det или ,)(det
1
*
4 ∏
=
=
k
j
n
j
jJ C
где det(C) — определитель матрицы C; Cj — ковариационная матрица кластера Kj.
96 ISSN 0572-2691
Более громоздкие в вычислительном плане точечно-бисериальный коэффи-
циент корреляции, коэффициенты компактности, сгущения.
Общепринятый точностной подход к кластеризации эффективен только при
точных и полных исходных данных; при полном отсутствии помех все критерии
(как внешние, так и внутренние) указывают истинную кластеризацию [9]. Так как
нужно находить недоусложненные кластеризации не столько точные на выборке,
как отвечающие объективным свойствам объекта (т.е. непротиворечивые), не-
обходимые при зашумленных данных, то при самоорганизации кластеризаций
должны использоваться внешние критерии. Поэтому объективный кластерный
анализ характеризуется обязательным использованием внешних критериев наряду
с внутренними [25, 26].
5. Объективная кластеризация
Проблема объективной компьютерной кластеризации (ОКК) исследовалась во
многих работах академика А.Г. Ивахненко [9–11, 19–22]. Алгоритм ОКК и его мо-
дификации успешно применены для решения практических задач. Но, к сожалению,
пока не получена «система систем кластеризаций» [19], позволяющая находить ре-
ально существующие кластеры в экспериментальных зашумленных данных. В то
же время теория поиска ОКК, основанная А.Г. Ивахненко, позволяет разрабатывать
новые методы и алгоритмы объективной кластеризации, даже при .nm >
Объективной назовем кластеризацию },,,,{ 21
kKKKK = 1< k < n, для
которой выполняются условия:
rmax < Rmin, (12)
).(minarg KJK AB
ФK⊆
= (13)
Если решается задача кластеризации в широком смысле (набор признаков
,X характеризующих объекты, не установлен точно, а известно лишь, что он
принадлежит некоторому, может быть, расширенному исходному набору), то
объективная кластеризация удовлетворяет еще и третьему условию:
),,(minarg BA
XX
QKdK
m
= (14)
где ),( BA
X QKd
— мера сходства, аналогичная (2), между кластеризациями KA
и QB подвыборок А и В, полученными на подмножестве X исходного множества
признаков.
Для объективной кластеризации наибольшее число объектов пар ),( ll sq
,2/,,2,1 nl = находится в соответствующих кластерах подвыборок А и В.
Например, если объекты с номерами 1073 ,, qqq попали в один кластер подвы-
борки А, а объекты с номерами 1073 ,, sss — в один кластер подвыборки В и
структура кластеров на А и В совпадает (число кластеров, число объектов в соот-
ветствующих кластерах на А и В одинаково и пары ),( ll sq ,2/,,2,1 nl = нахо-
дятся в соответствующих кластерах), то кластеризация объективная (рис. 5).
Проверка условий П1 и П2 в реальных условиях невозможна, поэтому поиск
объективной кластеризации предполагает интерактивную схему, в которой для
каждой кластеризации-кандидата выполняется проверка условий П1 и П2 по по-
лученным результатам. Учитывая, что «перебор кластеризаций-кандидатов прин-
ципиально не отличается от перебора множества моделей-кандидатов» [19], для
поиска объективной кластеризации используем многорядный итерационный ал-
горитм МГУА [27].
Проблемы управления и информатики, 2008, № 2 97
A
B
K2A
K2B
KjA
K1B
KjB
Xq3
Xs3
Xs7
Xq7
K1A
Рис. 5
Класс синтезируемых кластеризаций имеет вид
)},(ˆ,),(ˆ),(ˆ{)(ˆ
21 XKXKXKXK k= ,1 nk << (15)
где k — число кластеров, )(ˆ XKi — i-й кластер, ni — число объектов в нем,
.21 nnnn k =+++
Частной кластеризацией будем называть любую кластеризацию ),(ˆ XZ полу-
ченную на некоторой итерации алгоритма как приближение объективной класте-
ризации ).(XK
Структурой частной кластеризации будем называть набор параметров ni и k,
определяющих )(ˆ XZ в представлении (15). Частная кластеризация описывается
вектором ẑ размерности n номеров кластеров: j-я координата вектора содержит
номер кластера, в который попал j-й объект.
Для построения итерационного алгоритма МГУА необходимо:
1) указать начальную частную кластеризацию ;ˆ Z
2) определить оператор R, осуществляющий отображение ,ˆˆ 1 rr R ZZ →−
,2,1=r — номер итерации;
3) указать правило завершения итераций.
Общий вид матрицы частных кластеризаций rẐ определим следующим об-
разом:
],ˆˆˆ[ˆ
g21
rrrr
f+= zzzZ (16)
где ,ˆ r
jz ,,,2,1 fgj += — векторы размерности n, частные кластеризации; g —
число лучших частных кластеризаций, передаваемых от итерации к итерации;
f — число кластеризаций-«соседей» лучших частных кластеризаций итерации
(r–1), ,2cgf ×≤ где 2с — число «соседей» для одной лучшей кластеризации.
Например, если лучшая кластеризация содержит 5 кластеров, то кластеризация-
ми-«соседями» при с =1 будут кластеризации с числом кластеров 4=k и .6=k
Обозначим:
],ˆˆˆ[ˆ
21
rrrr
gzzzG = ].ˆˆˆ[ˆ
21
rr
g
r
g
r
fg+++= zzzC
Алгоритм состоит из следующих шагов.
1. Заполняется начальная матрица частных кластеризаций :ˆ Z
].ˆˆ[ˆ
CGZ =
Для этого последовательно осуществляются: нормировка, формирование
таблицы межточечных расстояний, формирование списка пар точек, ранжирован-
98 ISSN 0572-2691
ных по возрастанию межточечного расстояния, разделение исходной выборки на
подвыборки А и В, генерация кластеров для подвыборок А и В, каждой в отдель-
ности (иерархическим агломеративным или двусторонним алгоритмом, k-средних
или ISODATA). Из всех генерируемых частных кластеризаций, для которых вы-
полняется условие (12), отбирается g лучших по критерию (6). Отобранные луч-
шие частные кластеризации, ранжированные по увеличению величины (6), ис-
пользуются при формировании матрицы
].ˆˆˆ[ˆ
21
gzzzG =
Число кластеров в лучших кластеризациях — ),1(k ),2(k …, ).(gk Mатри-
ца Ĉ формируется из «соседей» лучших частных кластеризаций.
2. Определяется оператор R. Для заданных способа нормировки, меры сход-
ства между объектами, разбиения исходного множества на подмножества А и В,
метода образования кластеров генерируются частные кластеризации в предполо-
жении, что число реально существующих кластеров равно
.)(,,1)(,1)(,,)( 1111 cgkgkgkcgk rrrr ++−− −−−−
Из всех генерируемых частных кластеризаций по критерию (6) отбирается
g лучших.
Отобранные лучшие частные кластеризации, ранжированные по увеличе-
нию величины J, сравниваются с кластеризациями предыдущей итерации
]ˆˆˆ[ˆ 11
2
1
1
1 −−−− = rrrr
gzzzG и используются при формировании матрицы =rĜ
].ˆˆˆ[ 21
rrr
gzzz = Mатрица rС̂ формируется из «соседей» лучших частных кла-
стеризаций матрицы .ˆ rG
Таким образом, определяется оператор R преобразования ,ˆˆ 1 rr R ZZ →−
.,2,1 =r
3. Правило остановки для итерационной схемы: вычисления заканчиваются
на итерации ,∗r если выполнено условие
,)ˆ()ˆ( 1
r
r
F
r
F JJ δ<−
∗∗− ZZ
где )ˆ(
∗r
FJ Z — значение критерия для лучшей частной кластеризации итерации r;
rδ — заданная величина.
Если решается задача кластеризации в широком смысле, то сначала описан-
ный алгоритм последовательно применяется к множеству, содержащему только
один признак, и выбираются f кластеризаций, лучших по критерию (14), затем
методом последовательного присоединения признаков составляется f × (m–1) ан-
самблей, состоящие из двух признаков, и опять выбираются лучшие по крите-
рию (14) кластеризации и сравниваются с отобранными на предыдущем этапе и т.д.
6. Кластеризация пространственно-временных данных
Пусть xij (ts) — измерения признаков, характеризующих заданное множество
объектов Z={Z1, Z2,…, Zn} в момент времени ts ( i=1, 2,…, n — номер наблюде-
ния, n — число наблюдений, j=1, 2,…, m — номер признака, m — число призна-
ков, s=1, 2,…, L — номер момента времени); w(Z1), w(Z2),…, w(Zn) — географи-
Проблемы управления и информатики, 2008, № 2 99
ческие координаты объектов. Исходные данные представляют собой блочную
матрицу
)).()()(( 21 Lttt XXXW
где W — матрица размерности n×2 (или n×3) географических координат объектов,
,
)()()(
)()()(
)()()(
)(
21
22221
11211
=
snmsnsn
smss
smss
s
txtxtx
txtxtx
txtxtx
t
X ....,,2,1 Ls = (17)
Кластеризация пространственно-временных данных основывается на трех
предположениях.
1. Учет временного соседства. Объекты, близкие по своим свойствам (вхо-
дящие в один кластер) в момент времени t, могут быть близки и в момент вре-
мени ( t +1) (рис. 6). Это предположение используется для нахождения кластери-
зации K( t, t +1), оптимизирующей критерий γ(K) непротиворечивости (например,
min,)( →γ K где γ(K) — мера сходства между кластеризациями K(ts) s=1, 2,…, L,
для отдельных временных срезов ,stt = и всей совокупности данных).
K(t)
K(t+1)
K1(t+1)
K2(t+1)
K2(t ) K1(t )
K(t , t+1)
K2
K1
Рис. 6
2. Учет географической смежности. Объекты, соседствующие в географиче-
ском пространстве, могут образовать однородные по свойствам группировки, соот-
ветствующие связным областям (целостным территориальным зонам). Это предпо-
ложение используется для нахождения кластеризации, оптимизирующей критерий
β(K) (например, β(K) → max; β(K) — сумма элементов в матрице смежности объ-
ектов отдельных кластеров, рассматриваемых в пространстве географических ко-
ординат).
3. Учет близости в пространстве признаков. Это распространенное для
большинства методов кластерного анализа предположение используется для
нахождения кластеризации, оптимизирующей критерий α(K) (например, α(K) →
→ min; α(K) — сумма внутрикластерных расстояний, где K — кластеризация
множества Z без учета географических координат). Объекты, соседствующие в
пространстве признаков X, могут образовать однородные по свойствам группи-
ровки — кластеры.
Предположение 1 используется для определения преемственности кластери-
заций, соответствующих двум последовательным моментам времени.
Пусть )}(,),(),({)( 21 sksss tKtKtKtK = — кластеризация объектов в мо-
мент времени ,stt = s=1, 2,…, L, где k — число кластеров, ,1 nk << полученная
на основе матрицы X( ts).
100 ISSN 0572-2691
Каждому объекту Zi (отождествленному с вектором Xi= (xi1(ts), xi2(ts),…
…, xim(ts)), ,,,2,1 ni = евклидова пространства Rm) кластеризация K(ts) ставит в
соответствие номер кластера, к которому он принадлежит в момент времени .stt =
По результатам кластеризаций K(ts) и K(ts+1) строится матрица =+ ),( 1ss ttA
),,( 1+= ssij tta ,,,2,1, kji = где элемент ),( 1+ssij tta определяет число объек-
тов, одновременно входящих в кластер Ki (ts) и кластер Kj (ts+1) (табл. 2)
Таблица 2
K(ts)
K(ts+1)
K1(ts+1) K2(ts+1) … Kj(ts+1) … Kk(ts+1)
K1(ts) A11 a12 … a1j … a1q
K2(ts) A21 a22 … a2j … a2k
… … … … … … …
Ki(ts) ai1 ai2 … aij … aik
… … … … … … …
Kk(ts) ak1 ak2 … akj … akk
Элементы ),( 1+ssij tta матрицы ),( 1+ss ttA подсчитываются следующим об-
разом:
,)(
1
∑
=
=
n
e
eijij ZFa ,,,2,1, kji =
=+∈∈
=
случае.противномв0
true,))1(())((если,1
)( stjKeZ&stiKeZ
ZF eij (18)
Сумма элементов матрицы ),( 1+ss ttA равна числу кластеризуемых объектов:
∑ ∑
= =
+ =
k
i
k
j
ssij ntta
1 1
1),( ∀s=1, 2,…, L–1.
Номер кластера является не более чем меткой, т.е. можно поменять нумера-
цию кластеров, сохранив при этом состав входящих в них элементов. Поэтому для
определения преемственности кластеризации K(ts+1) по отношению к K(ts) в мат-
рице ),( 1+ss ttA производится перестановка столбцов таким образом, чтобы мак-
симальный элемент i-й строки попал на главную диагональ:
).,(max)( 11 ++ ↔ ssii
i
si ttatK
Обозначим
).,(1),( 11 ++ = ssss tt
n
tt AP
Сумма элементов матрицы ),( 1+ss ttP равна единице:
∑ ∑
= =
+ =
k
i
k
j
ssij ttp
1 1
1 1),( ∀s=1, 2,…, L–1.
Элемент ),( 1+ssij ttp можно рассматривать как вероятность того, что объект,
принадлежащий кластеру ),( si tK попадет в кластер ).( 1+si tK
Проблемы управления и информатики, 2008, № 2 101
Заметим, что в построенной таким образом последовательности матриц
)},,({ 1+ss ttA s=1, 2,…, L–1, выполняются следующие отношения:
},,2,1{ ki ∈∀ ,0),( 1 ≠+ssij tta ),,(),( 11 +− ≥ ssijssij ttatta s=2,…, L–1,
},,,,{},,,{},,,{ 1
)1(
1
2
1
1
1
)1(
1
2
1
1)(21 iii n
L
Ln
LLL
Ln
LL jjjjjjjjj ⊂⊂⊂ −
−
−−
где s
sn
ss
i
jjj )(21 ,,, — номера объектов, вошедших в кластер );( si tK =)(sni
)( si tK= — число объектов в ),( si tK ,)(
1
∑
=
=
k
i
i nsn s=1, 2,…, L , .1,,2 −= Ls
Предположение 2 необходимо для кластеризации пространственно распреде-
ленных данных, учитывающей в явном виде свойство географического соседства
объектов, например, геоматическим алгоритмом [28].
Меры сходства, применяемые в кластеризации пространственных и про-
странственно-временных данных, представлены в табл. 1. Для оценки сходства
двух кластеризаций K и Q используется формула (2).
Кластеризация GeoTime пространственно-временных данных изложена
в [29, 30]. Она включает в себя основные шаги геоматической кластеризации и
усложняет ее процедурой выделения (на основе преемственности кластеризаций в
последовательные моменты времени) ядер — кластеров, образующих целостную
пространственную область.
Общая схема GeoTime-кластеризации следующая.
1. Найти матрицу смежности G= (gij), ,,,2,1, nji = между объектами
nZZZ ,,, 21 в географическом пространстве; gij определяется одним из спо-
собов:
а)
ε<ρ
=
,случаепротивномв0
,если,1 ij
ijg б)
−−
=
случае,противномв0
,соседииесли,1 ji
ij
ZZ
g
где ρij — евклидово расстояние между объектами Zi и Zj в географическом про-
странстве (W — исходная матрица для его вычисления), ε — порог.
2. Вычислить матрицу D= (dij ), ,,,2,1, nji = где ),(),( jijiij dZZdd XX== —
мера сходства между Zi и Zj в пространстве признаков (см. табл. 1) =X(
)]()()([ 21 Lttt XXX = — исходная матрица для вычисления dij ). Для каждого
момента времени ts , s =1, 2,…, L , вычислить матрицу (используя (17)) D(ts)=
= (dij ( ts)) = (d(Xi( ts), Xj ( ts))), аналогичную D.
3. Определить центры кластеров начального разбиения (ядра) ,,,,
21 kiii ZZZ
используя изложенный алгоритм определения преемственности кластеризаций
в последовательные моменты времени. Принять
}.{,},{},{ 11
2
1
1 21 kikii ZKZKZK ===
4. Положить r=1.
5. Пусть на шаге r∈{1,…, n– k} получены классы ....,,1
r
k
r KK
6. Найти j∈{1, 2, …, n}, v∈{1,…, k}:
102 ISSN 0572-2691
}}.,,2,1{,1:{min kqgKXdd jmqmjiji qv
∈=∈∃=
7. Положить ∀i∈{1, 2,…, k}
≠
=∪
=+
.,
;},{1
viK
viZK
K
r
i
j
r
ir
i
(Шаги 6, 7 используют предположение 2.)
8. Положить .∞=
vjid
9. Если ,knr −= конец, иначе положить r=r+1 и перейти к шагу 5.
Таким образом, выделяя в каждом кластере несколько объектов, образующих
целостную пространственную область, полагают их ядрами. Выделенные ядра
кластеров расширяют доклассификацией оставшихся объектов.
Объективная кластеризация пространственно-временных данных включает в
себя основные шаги GeoTime-кластеризации. При этом исходная выборка данных
делится на две подвыборки А и В таким образом, что в подвыборку А попадают
наблюдения в четные моменты времени, а в подвыборку В — в нечетные. В каче-
стве внешних критериев качества кластеризации используются критерии (6)–(8).
Многочисленные эксперименты на реальных данных [28, 31–33] показали,
что объективная, геоматическая и GeoTime-кластеризации имеют лучшие пока-
затели критериев качества (9)–(11), чем кластеризация, полученная методом
k-средних.
Заключение
Приведены следующие результаты объективного кластерного анализа дан-
ных на основе самоорганизации кластеризаций в соответствии с принципами
МГУА.
1. Рассмотрены меры сходства (между объектами, кластерами, объектом и
кластером), используемые в кластеризации, и предложены новые меры сходства
между кластеризациями.
2. Предложен единый подход к классификации методов выбора информа-
тивных признаков и поиска наилучшей кластеризации (в котором и кластериза-
ция, и выбор признаков являются задачами дискретной оптимизации на верши-
нах решетки разбиений), позволяющий увидеть новые направления развития
этих методов.
3. Предложены новые внешние критерии оценки качества кластеризации, об-
разующие минимум в области недоусложненных кластеризаций и позволяющие
находить кластеризации оптимальной сложности в случае зашумленных данных.
4. Разработан многорядный итерационный алгоритм поиска объективной
кластеризации, отличительные особенности которого: оценивание качества кла-
стеризации с помощью внутреннего и внешнего критериев, использование набо-
ров мер сходства и способов образования кластеров, поиск числа реально суще-
ствующих кластеров и оптимального подмножества признаков.
5. Разработан алгоритм объективной кластеризации пространственно-времен-
нх данных, преимущества которого: учет топологических свойств местораспо-
ложений объектов для выделения целостных пространственных зон, образуемых
отдельными кластерами; учет временных тенденций изменения признаков для
выделения начальных ядер кластеров; возможность содержательной интерпрета-
ции выделенных кластеров.
Дальнейшие исследования по самоорганизации кластеризаций планируется
проводить с помощью экстраполяции геометрического места минимумов внеш-
них критериев при зашумленных данных. Отметим, что эта идея для идентифи-
Проблемы управления и информатики, 2008, № 2 103
кации модели рассматривалась академиком А.Г. Ивахненко еще в 80-х годах
прошлого века [9].
Л.В. Саричева
ОБ’ЄКТИВНИЙ КЛАСТЕРНИЙ АНАЛІЗ
ДАНИХ НА ОСНОВІ МГУА
Розглядається проблема об’єктивного кластерного аналізу даних на основі са-
моорганізації кластеризацій відповідно до принципів МГУА. Запропоновано
єдиний підхід до класифікації методів вибору інформативних ознак і пошуку
найкращої кластеризації. Розглянуто нові зовнішні критерії оцінки якості клас-
теризації та міри подібності між кластеризаціями. Розроблено алгоритм
об’єктивного кластерного аналізу просторово-часових даних.
L.V. Sarycheva
OBJECTIVE CLUSTER ANALYSIS
OF THE DATA ON THE BASIS OF THE GMDH
The problem of objective cluster analysis of the data is considered on the basis of
self-organizing of clusterizations according to GMDH principles. The unified ap-
proach to classification of selection methods of informative features and search of
the best clusterization is proposed. New external criteria of a clusterization quality
estimation and measures of similarity between clusterizations are considered. The al-
gorithm of objective cluster analysis of the spatially-temporary data is developed.
1. Мендель И.Д., Миркин Б.Г. Кластер-анализ и смежные вопросы (краткий обзор основных
направлений) // Автоматика. — 1987. — № 2. — С. 72–82.
2. Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. —
М. : Статистика, 1974. — 240 с.
3. Дюран Б., Оделл П. Кластерный анализ: Пер. с англ. — М. : Статистика, 1977. — 128 с.
4. Жамбю М. Иерархический кластер-анализ и соответствия : Пер. с франц. — М. : Финансы
и статистика, 1988. — 342 с.
5. Классификация и кластер / Под ред. Дж. Ван Рицина. — М. : Мир, 1980. — 390 с.
6. Прикладная статистика. Классификация и снижение размерности / С.А. Айвазян,
В.М. Бухштабер, И.С. Енюков и др. — М. : Финансы и статистика, 1989. — 608 с.
7. Ту Дж., Гонсалес Р. Принципы распознавания образов : Пер. с англ. — М. : Мир, 1978. —
411 с.
8. Факторный, дискриминантный и кластерный анализ : Пер. с англ. / Дж.-О. Ким, Ч.У. Мюл-
лер, У.Р. Клекка и др. — М. : Финансы и статистика, 1989. — 215 с.
9. Ивахненко А.Г. Объективная кластеризация на основе теории самоорганизации моделей //
Автоматика. — 1987. — № 5. — С. 6–15.
10. Ивахненко А.Г. Алгоритмы метода группового учета аргументов (МГУА) при непрерывных
и бинарных признаках / Препр. Ин-т кибернетики им. В.М. Глушкова. — Киев, 1992. —
49 с.
11. Ивахненко А.Г., Коппа Ю.В., Петухова С.А., Ивахненко М.А. Применение самоорганизации
для разбиения множества данных на заранее незаданное число кластеров // Автоматика. —
1985. — № 5. — С. 9–16.
12. Дубницкий В.Ю. Оценка устойчивости алгоритмов кластерного анализа // Информацион-
ные системы: Сб. научн. тр. — 1997. — Вып. 1(5). — С. 129–134.
13. Методы, критерии и алгоритмы, используемые при преобразовании, выделении и выбо-
ре признаков в анализе данных / К.А. Чепонис, Д.А. Жвиренайте, Л.В. Мирошниченко,
Б.С. Бусыгин — Вильнюс : Изд-во ИМК АН ЛитССР, 1988. — 149 с.
14. Раудис Ш. Определение числа полезных признаков в задаче классификации // Статистиче-
ские проблемы управления. — Вильнюс : ИМК АН ЛитССР, 1976. — Вып. 14. — С. 137–150.
104 ISSN 0572-2691
15. Siedelcki W., Sklansky J. On automatic feature selection // IEEE Pattern Recognition and Art. Int. —
1988. — 2, N 2. — P. 197–220.
16. Курейчик В.М. Генетические алгоритмы. — Таганрог : ТРТУ, 1998. — 242 с.
17. Мирошниченко Л.В. Сравнение алгоритмов выбора наилучшего подмножества признаков в
распознавании образов // Статистические проблемы управления. — Вильнюс : ИМК АН
Литвы, 1990. — Вып. 93. — С. 78–91.
18. Сарычева Л.В. Единый подход к классификации методов кластеризации и методов выбора
информативных признаков // Актуальні проблеми автоматизації та інформаційних техно-
логій. Зб. наук. праць, Т. 6. — Дніпропетровськ : Навч. книга, 2002. — С. 137–144.
19. Ивахненко А.Г. Метод последовательного опробования (перебора) кластеризаций-
кандидатов по критериям дифференциального типа // Распознавание, классификация, про-
гноз. Мат. методы и их применение. — М. : Наука, 1989. — Вып. 2. — С. 126–158.
20. Ивахненко А.Г. Моделирование сложных систем. Информационный подход. — Киев : Ви-
ща шк., 1987. — 63 с.
21. Непараметрические прогнозирующие модели МГУА. Часть 3. Модели на языке паттерн- и
кластер-анализа для прогнозирования процессов в экономических макросистемах /
А.Г. Ивахненко, Н.А. Ивахненко, Ю.В. Костенко, И.А. Мюллер, А.П. Сарычев, Ю.П. Юрач-
ковский // Автоматика. — 1989. — № 3. — С. 3–17.
22. Ивахненко А.Г. Непрерывность и дискретность. Переборные методы моделирования и кла-
стеризации. — Киев : Наук. думка, 1990. — 224 с.
23. Степашко В.С., Кочерга Ю.Л. Методы и критерии решения задач структурной идентифи-
кации // Автоматика. — 1985. — № 5. — С. 29–37.
24. Halkidi M., Batistakis Y., Vazirgiannis M. Cluster validity methods: Part I. — Department of In-
formatics, Athens University of Economics&Business, 2001.
25. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. — Новосибирск : Изд-во
ИМ СО РАН, 1999. — 270 с.
26. Дюк В., Самойленко А. Data Mining. Уч. курс. — С.П. : Питер, 2001. — 368 с.
27. Ивахненко А.Г., Юрачковский Ю.П. Моделирование сложных систем по эксперименталь-
ным данным. — М. : Радио и связь, 1987. — 120 с.
28. Sarycheva L., Boyko A. Geomatic clusterization based on ecological-social-economical moni-
toring rates // Scientific Bulletin of NMU, 2006. — № 5. — P. 76–81.
29. Sarycheva L. The spatial-temporary approach in problems of clusterization // Proceedings of In-
ternational Workshop on Inductive Modelling «IWIM–2007» (22–26 September 2007, Pra-
gue). — Электр. ресурс. URL: http://www.iwim2007.org/Proceedings.
30. Сарычева Л.В. Алгоритм GeoTime кластеризации пространственно-привязанных данных
// Штучний інтелект. — 2006. — № 3. — С. 646–653.
31. Сарычева Л.В. Компьютерный эколого-социально-экономический мониторинг регионов.
Математическое обеспечение: Монография. — Днепропетровск : Национальный горный
ун-т, 2003. — 222 с.
32. Sarycheva L., Zhuykov A. Cluster analysis of territories by the totality of ecological and socio-
economic indices // IEEE 2001 Intern. Geoscience and Remote Sensing Symposium, 9–13 July,
2001, UNSW. — P. 663–664.
33. Sarycheva L.V. Using GMDH in ecological and socio-economical monitoring problems // Sys-
tems Analysis Modelling Simulation. — 2003. — 43, N 10. — P. 1409–1414.
Получено 21.12.2007
http://www.iwim2007.org/Procedings
Введение
1. Постановка задачи
2. Меры сходства
3. Выбор информативных признаков и поиск наилучшей кластеризации: единый подход к классификации методов
4. Критерии оценки качества кластеризации
5. Объективная кластеризация
6. Кластеризация пространственно-временных данных
Заключение
|
| id | nasplib_isofts_kiev_ua-123456789-209124 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T17:04:03Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Сарычева, Л.В. 2025-11-14T10:45:56Z 2008 Объективный кластерный анализ данных на основе МГУА / Л.В. Сарычеваs // Проблемы управления и информатики. — 2008. — № 2. — С. 86-104. — Бібліогр.: 33 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209124 519.711:004.8:681.3 10.1615/JAutomatInfScien.v40.i4.30 Розглядається проблема об’єктивного кластерного аналізу даних на основі самоорганізації кластеризацій відповідно до принципів МГУА. Запропоновано єдиний підхід до класифікації методів вибору інформативних ознак і пошуку найкращої кластеризації. Розглянуто нові зовнішні критерії оцінки якості кластеризації та міри подібності між кластеризаціями. Розроблено алгоритм об’єктивного кластерного аналізу просторово-часових даних. The problem of objective cluster analysis of the data is considered on the basis of self-organizing of clusterizations according to GMDH principles. The unified approach to classification of selection methods of informative features and search of the best clusterization is proposed. New external criteria of a clusterization quality estimation and measures of similarity between clusterizations are considered. The algorithm of objective cluster analysis of the spatially-temporary data is developed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Распознавание образов и кластеризация Объективный кластерный анализ данных на основе МГУА Об’єктивний кластерний аналіз даних на основі МГУА Objective cluster analysis of the data on the basis of the GMDH Article published earlier |
| spellingShingle | Объективный кластерный анализ данных на основе МГУА Сарычева, Л.В. Распознавание образов и кластеризация |
| title | Объективный кластерный анализ данных на основе МГУА |
| title_alt | Об’єктивний кластерний аналіз даних на основі МГУА Objective cluster analysis of the data on the basis of the GMDH |
| title_full | Объективный кластерный анализ данных на основе МГУА |
| title_fullStr | Объективный кластерный анализ данных на основе МГУА |
| title_full_unstemmed | Объективный кластерный анализ данных на основе МГУА |
| title_short | Объективный кластерный анализ данных на основе МГУА |
| title_sort | объективный кластерный анализ данных на основе мгуа |
| topic | Распознавание образов и кластеризация |
| topic_facet | Распознавание образов и кластеризация |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/209124 |
| work_keys_str_mv | AT saryčevalv obʺektivnyiklasternyianalizdannyhnaosnovemgua AT saryčevalv obêktivniiklasterniianalízdanihnaosnovímgua AT saryčevalv objectiveclusteranalysisofthedataonthebasisofthegmdh |