Файл: Методы кластеризации четкие и нечеткие.pdf

Альфацефей
Методы кластеризации: четкие и нечеткие.
Кластерный анализ – это метод разделение данных на классы объектов, в каждом из которых объекты имеют похожие свойства. Сам по себе кластерный анализ - это не конкретный алгоритм, а общая задача, которую необходимо решить с помощью различных алгоритмов. Не существует объективно «правильного» алгорит- ма кластеризации. Наиболее подходящий алгоритм кластеризации необходимо выбирать экспериментально,
в зависимости от набора данных, если только не существует математической причины предпочесть один алгоритм другому.
Методы кластеризации можно разделять по способу обработки данных, по способу анализа данных, по мас- штабируемости, по времени выполнения и так далее. Методы по способу анализа данных, в свою очередь,
разделяют на четкие (или традиционные) и нечеткие. К четким алгоритмам относятся те алгоритмы, в кото- рых каждый объект данных принадлежит одному кластеру. К нечетким алгоритмам кластеризации относятся те, в которых каждый объект данных принадлежит более одному кластеру с определенной степенью.
В 1965 году L. Zadeh [21] представил аксиоматическую структуру – нечеткое множество. Первое применение теории нечетких множеств к кластерному анализу было сделано в 1969 году E.H. Ruspini [16]. Однако только после появления работ J.C. Dunn [9] и J.C. Bezdek [4] теория нечетких множеств приобрела актуальность для кластерного анализа и теории распознавания образов.
В 1993 году R. Krishnapuram и J.M. Keller в работе [11] представили возможностный алгоритм кластеризации.
Из этой работы также выросла целая ветвь алгоритмов кластеризации.
Методы кластеризации относятся к классу задач обучения без учителя и широко используются в теории распознавания образов, анализе изображений, поиске информации, биоинформатике, сжатии данных, ком- пьютерной графике и машинном обучении.
В данной лекции мы подробно рассмотрим некоторые четкие и нечеткие алгоритмы кластеризации и расска- жем о преимуществах и недостатках каждого. Начнем с хорошо известного ЕМ-алгоритма.
1 EM-алгоритм.
EM-алгоритм – это итеративный метод нахождения оценок максимального правдоподобия параметров ста- тистической модели, когда модель зависит от скрытых ненаблюдаемых переменных. Каждая итерация ал- горитма состоит двух шагов. На шаге ожидания (expectation) вычисляется ожидаемое значение функции правдоподобия с использование текущей оценки параметров. На шаге максимизации (maximization) вычис- ляются параметры, максимизирующие ожидаемую функцию максимального правдоподобия, найденную на шаге ожидания. Впервые такое название алгоритма появилось в работе [7], хотя подобная итерационная процедура рассматривалась гораздо раньше многими авторами, например, A. G. McKendrick [14] и М. И.
Шлезингером [3].
1.1 Общее описания алгоритма. [1]
Пусть ???? и ???? – случайные величины, принимающие значения в пространствах R
????
и R
????
соответственно, где
????, ???? ≥ 1
. Пусть ???? – параметр из некоторого множества Θ произвольной природы. Плотность совместного распределения (???? + ????)-мерного случайного вектора (????, ???? ) обозначим
????
????
(????, ????), ???? ∈ R
????
, ???? ∈ R
????
, ???? ∈ Θ.
Условная плотность случайной величины ???? при условии ???? = ???? определяется как
????
????
(????|????) =
????
????
(????, ????)
????
????
????
(????)
, ???? ∈ R
????
,
(1)
где
????
????
????
(????) =
∫︁
R
????
????
????
(????, ????)????
????
(????????)
1

Альфацефей является маргинальной плотностью случайной величины ???? относительно меры ????
????
. Выражение (1) имеет смысл, если ????
????
????
(????) ̸= 0
. Аналогично определяется условная плотность случайной величины ???? при условии
???? = ????
:
????
????
(????|????) =
????
????
(????, ????)
????
????
????
(????)
, ???? ∈ R
????
(2)
Выражение (2) имеет смысл, если маргинальная плотность случайной величины ???? относительно меры ????
????
????
????
????
(????) =
∫︁
R
????
????
????
(????, ????)????
????
(????????) ̸= 0.
В качестве мер ????
????
и ????
????
рассматривается либо мера Лебега, либо другая считающая мера (формальный эквивалент количества элементов множества). Из соотношений (1), (2) вытекает, что
????
????
(????, ????) = ????
????
(????|????)????
????
????
(????) = ????
????
(????|????)????
????
????
(????).
(3)
Будем считать, что случайная величина ???? имеет смысл наблюдаемых данных, в то время как скрытая (нена- блюдаемая) случайная величина ???? играет вспомогательную роль. Зная совместную плотность ????
????
(????, ????)
и зна- чение ???? наблюдаемой величины ???? можно формально определить полную функцию правдоподобия
????(????; ????, ????) = ????
????
(????, ????), ???? ∈ Θ,
(4)
как функцию параметра ????. При этом
????(????; ????) = ????
????
????
(????), ???? ∈ Θ,
(5)
функция правдоподобия параметра ???? при неполных данных.
Цель ЕМ-алгоритма – найти значения параметра ????, максимизирующее функции (4) или (5) при неизвестном значении ???? или, другими словами, найти оценки максимального правдоподобия параметра ????. Процедура
EM-алгоритма состоит из вычисления последовательности значений {????
(????)
}
, ???? ≥ 1 параметра ????. Если задано некоторое значение ????
(????)
, то вычисление следующего значения ????
(????+1)
можно разделить на два этапа. Опишем эти этапы.
1. (E-этап) Определим функцию ????(????, ????
(????)
)
, как условное математическое ожидание логарифма полной функции правдоподобия при известном значении наблюдаемой компоненты ????:
????(????, ????
(????)
) = ????
????
(????)
(log ????
????
(????, ???? )|????).
(6)
В этом определении ???? является аргументом, а ????
(????)
и ???? параметрами. При известном значении ???? = ????
символ ????
????
(????)
означает среднее значение случайной величины ???? относительно условного распределения
????
????
(????)
(????|????)
, то есть:
????(????, ????
(????)
) =
∫︁
R
????
(log ????
????
(????, ???? ))????
????
(????)
(????|????)????
????
(????????).
2. (М-этап) На этом этапе вычисляется
????
(????+1)
= arg max
????
????(????, ????
(????)
).
(7)
Далее выбирается метрика ????(·, ·) и фиксируется малое положительное ????. Итерационный процесс оста- навливается на m-ом шаге, если ????(????
(????)
, ????
(????+1)
) < ????
Отметим свойство монотонности EM-алгоритма, которое впервые было установлено в работе [3]. Однако этого недостаточно, чтобы утверждать, что последовательность оценок параметров, построенная ЕМ-алгоритмом,
гарантировано сходится к локальному максимуму функции правдоподобия. Чтобы установить такую сходи- мость, приходится предполагать, что рассматриваемые распределения удовлетворяют дополнительным усло- виям регулярности, и, в частности, условиям гладкости (подробнее смотри в [1]). Одновременно монотонность
ЕМ-алгоритма свидетельствует о его сильной зависимости от выбора начального (стартового) приближения.
2

Альфацефей
1.2 Применение EM-алгоритма к задаче разделения смесей вероятностных рас- пределений. [1]
Задача поиска наиболее правдоподобных оценок параметров смесей вероятностных распределений является одним из самых популярных приложений EM-алгоритма. Предполагается, что данные в каждом кластере подчиняются определенному закону распределения. Для наглядности будем рассматривать смеси одномерных распределений. В рамках данной задачи плотность распределения наблюдаемой случайной величины ???? имеет вид
????
????
????
(????) =
????
∑︁
????=1
????
????
????
????
(????; ????
????
),
(8)
где ???? ≥ 1 – известное натуральное число, ????
1
, . . . ????
????
– известные плотности распределения, ???? = (????
1
, . . . , ????
????
, ????
1
, . . . , ????
????
)
– неизвестный параметр, причем каждое ????
????
≥ 0
и ????
1
+ . . . + ????
????
= 1
, ????
????
, ???? = 1, . . . , ????, – многомерные парамет- ры. Плотности ????
1
, . . . , ????
????
будем называть компонентами смеси (8), а ????
1
, . . . , ????
????
– весами соответствующих компонент.
Задачей разделения смеси (8) называется задача статистического оценивания параметров ???? = (????
1
, . . . , ????
????
, ????
1
, . . . , ????
????
)
по известным реализациям случайной величины ????.
Предположим, что имеется независимая выборка значений ???? = (????
1
, . . . , ????
????
)
случайной величины ????. В рамках модели (8) логарифм классической (неполной) функции правдоподобия параметра ???? имеет вид:
log ????(????; ????) = log
????
∏︁
????=1
????
????
????
(????
????
) =
????
∑︁
????=1
log
(︃
????
∑︁
????=1
????
????
????
????
(????
????
; ????
????
)
)︃
Непосредственный поиск точки максимума этой функции затруднителен. Однако, если мы будем трактовать наблюдения ????, как неполные, то функцию правдоподобия можно записать в более удобном виде.
Предположим, что наряду с наблюдаемой случайной величиной ???? задана ненаблюдаемая случайная величина
????
со значениями (????
1
, . . . , ????
????
)
, где ????
????
∈ {1, 2, . . . , ????}
содержат информацию о номерах компонент, в соответствии с которыми "генерируется" наблюдение ???? = (????
1
, . . . , ????
????
)
. Будем предполагать, что пары значений (????
????
, ????
????
)
являются стохастически независимыми реализациями пары случайных величин (????, ???? ).
Совместную плотность случайных величин ???? и ???? , как и раньше, обозначим ????
????
(????, ????)
. Так как дискретная случайная величина ???? абсолютно непрерывна относительно считающей меры и принимает значения ???? =
1, 2, . . . , ????
, то ее маргинальная плотность равна
????
????
????
(????) = ????
????
, ???? = 1, 2, . . . , ????,
а условная плотность случайной величины ???? при фиксированном значении ???? = ???? равна
????
????
(????|????) = ????
????
(????; ????
????
).
Поэтому, если бы значения ???? = (????
1
, . . . , ????
????
)
были известны, то логарифм полной функции правдоподобия имел бы вид:
log ????(????; ????, ????) = log
????
∏︁
????=1
????
????
(????
????
, ????
????
) =
????
∑︁
????=1
log ????
????
(????
????
, ????
????
) =
????
∑︁
????=1
log
(︀????
????
(????
????
|????
????
)????
????
????
(????
????
)
)︀ =
????
∑︁
????=1
log ????
????
????
+
????
∑︁
????=1
log ????
????
????
(????
????
; ????
????
????
).
После некоторых преобразований (подробнее в [1]), условное математическое ожидание логарифма полной функции правдоподобия при фиксированных значениях ???? = (????
1
, . . . , ????
????
)
наблюдаемой случайной величины
????
имеет вид:
????(????, ????
(????)
) =
????
∑︁
????=1
????
∑︁
????=1
????
????
(????|????
????
) log ????
????
+
????
∑︁
????=1
????
∑︁
????=1
????
????
(????|????
????
) log ????
????
(????
????
; ????
????
).
(9)
Для поиска максимума функции (9) по ???? = (????
1
, . . . , ????
????
, ????
1
, . . . , ????
????
)
можно максимизировать слагаемые в правой части (9) независимо друг от друга, так как они зависят от разных параметров: первое зависит только от весов ????
1
, . . . , ????
????
, а второе - только от параметров ????
1
, . . . , ????
????
компонент смеси. Учитывая ограничение
????
∑︁
????=1
????
????
= 1,
3

Альфацефей с помощью метода неопределенных множителей Лагранжа находим значение ???? = (????
1
, . . . , ????
????
, ????
1
, . . . , ????
????
)
, достав- ляющие максимум функции (9). Подразумевая, что значения ????
(????)
= (????
(????)
1
, . . . , ????
(????)
????
, ????
(????)
1
, . . . , ????
(????)
????
)
параметра
????
на ????-ой итерации известны, находим ????
(????+1)
1
, . . . , ????
(????+1)
????
на ???? + 1-итерации ЕМ-алгоритма.
Отметим, что в прикладных работах ЕМ-алгоритм чаще всего применяется к исследованию модели (8), где
????
????
(????; ????
????
)
– плотность нормального распределения вероятностей. Однако, именно эта модель не удовлетворяет условиям, гарантирующим правильную работу ЕМ-алгоритма. А именно, сходимость ЕМ-алгоритма доказа- на при обязательном условии ограниченности логарифма функции правдоподобия. Для смесей нормальных распределений указанное условие, вообще говоря, не выполняется. Также наличие большого числа локальных максимумов логарифма функции правдоподобия для модели (8) с большим числом (???? ≥ 2) нормальных ком- понент приводит к большой неустойчивости по отношению к начальному приближению и исходным данным.
2 Алгоритм k-средних.
Алгоритм k-средних разбивает ???? наблюдений на ???? ≤ ???? кластеров, при этом каждое наблюдение принадле- жит тому кластеру, к центру которого оно ближе всего. Термин "k-средних" впервые появился в работе [13].
Алгоритм прост в реализации, но в тоже время требует больших вычислительных ресурсов. Он похож на EM- алгоритм, применяемый для разделения смеси гауссиан. Оба они используют итеративный подход уточнения,
а кластерные центры используются для моделирование данных. Однако алгоритм k-средних стремится найти не пересекающиеся кластеры, имеющие сферическую форму, в то время, как EM-алгоритм позволяет кла- стерам пересекаться и иметь любую форму, так как функции распределения, используемые в ЕМ-алгоритме,
имеют дисперсию и ковариацию.
Пусть задано множество наблюдений ???? = (????
1
, . . . , ????
????
)
, где ????
????
∈ R
????
, ???? = 1, . . . , ????. Требуется разбить множество наблюдений ???? на ???? непересекающихся кластеров ????
1
, . . . , ????
????
, ????
????
∩ ????
????
= ∅, ???? ̸= ????,
⋃︀
????
????=1
????
????
= ????
, таким образом,
чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра (центра масс кластера), что равносильно поиску arg min
????
????
∑︁
????=1
∑︁
????∈????
????
‖???? − ????
????
‖
2
,
(10)
где ????
????
– центры кластеров ????
????
, ???? = 1, . . . , ????, ‖???? − ????
????
‖
2
=
∑︀
????̸=????∈????
????
(???? − ????
????
)(????
????
− ????)
Процедура алгоритма k-средних состоит из следующих шагов. Случайным образом выбираются центры кла- стеров ????
(1)
1
, . . . , ????
(1)
????
. Далее происходит итерация между двумя шагами.
1. Каждое наблюдение ????
????
присваивается тому кластеру, центр которого ближе всего к наблюдению, то есть
????
(????)
????
= {????
????
: ‖????
????
− ????
(????)
????
‖
2
≤ ‖????
????
− ????
(????)
????
‖
2
,
для любого ???? = 1 . . . , ????},
где ????
????
присваивается только одному ????
(????)
????
, даже если его можно отнести к двум и более кластерам.
2. Перевычисление центров кластеров для уже присвоенных различным кластерам наблюдений:
????
(????+1)
????
=
1
|????
(????)
????
|
∑︁
????
????
∈????
(????)
????
????
????
Алгоритм останавливается, когда ????
(????)
????
= ????
(????+1)
????
для любого ????.
Заметим, что число кластеров ???? необходимо знать заранее. Неправильный выбор ???? может привести к плохим результатам. Поэтому перед применением алгоритма k-средних важно выполнять диагностическую проверку для определения количества кластеров в наборе данных. Также к недостатками алгоритма k-средних можно отнести зависимость от выбора исходных центров кластеров, чувствительность к шуму, а также сходимость только к локальным минимумам. При этом данный алгоритм прост в применении, поэтому часто используется в качестве этапа предварительной обработки.
4

Альфацефей
3 Алгоритм нечеткой кластеризации (FCM).
Алгоритмом нечеткой кластеризацией (FCM) называется кластеризация, в которой каждое из ???? наблюдений может принадлежать сразу нескольким кластерам с разной степенью принадлежности. Таким образом, дан- ные, расположенные на границах кластеров, не обязаны полностью принадлежать одному кластеру, а могут быть в составе многих кластеров со степенью частичной принадлежности от 0 до 1.
В 1965 году Lotfi Zadeh [21] представил аксиоматическую структуру - нечеткое множество. Нечеткое мно- жество было задумано чтобы разобраться с проблемой распознавания образов в контексте неточно опреде- ленных категорий. Подробнее об этом в нашей первой части серии лекций по Теории возможностей. В 1969
году E.H. Ruspini [16] опубликовал статью, которая стала основой для большинства алгоритмов нечеткой кластеризации. Он впервые применил теорию нечетких множеств к кластерному анализу. Однако, только после появления работ J.C. Bezdek [4] и J.C. Dunn [9] алгоритмы нечеткой кластеризации стали важной вехой в теории кластерного анализа, так как была четко установлена актуальность теории нечетких множеств для кластерного анализа и распознавания образов.
Алгоритм нечеткой кластеризации очень похож на алгоритм k-средних. Пусть задано множество наблюдений
???? = (????
1
, . . . , ????
????
)
, где ????
????
∈ R
????
, ???? = 1, . . . , ????. Требуется разбить множество наблюдений ???? на ???? нечетких кластеров (????
1
, . . . , ????
????
)
с центрами (????
1
, . . . , ????
????
) = ????
таким образом, чтобы минимизировать функцию потерь arg min
(????,????)
????
∑︁
????=1
????
∑︁
????=1
????
????
????????
‖????
????
− ????
????
‖
2
,
(11)
где ????
????????
∈ [0, 1]
– степень принадлежности элемента ????
????
кластеру ????
????
с центром ????
????
, которая удовлетворяет ограничениям
????
????????
∈ [0, 1]
для всех ????, ????,
(12)
0 <
????
∑︁
????=1
????
????????
< ????
для всех ????,
(13)
????
∑︁
????
????
????????
= 1
для всех ????.
(14)
Число ???? ∈ [1, +∞) в функции (11) – экспоненциальный вес, определяющий нечеткость кластеров. Из необ- ходимых условий локального экстремума получаем:
????
????????
=
1
∑︀
????
????=1
(︁
‖????
????
−????
????
‖
‖????
????
−????
????
‖
)︁
2
????−1
, ???? = 1, . . . , ????, ???? = 1, . . . , ????,
(15)
????
????
=
∑︀
????
????=1
????
????
????????
????
????
∑︀
????
????=1
????
????
????????
, ???? = 1, . . . , ????.
(16)
Ограничение (14) обобщает соотношение, первоначально предложенное L.A. Zadeh [21], для определения сте- пени принадлежности любой точки ???? нечеткому множеству ???? и его дополнению ????
′
. А именно, дополнение ????
′
к нечеткому множеству ???? определяется равенством ????
????
′
(????) = 1 − ????
????
(????)
, где ????
????
(????) : ???? → [0, 1]
– характеристи- ческая функция нечеткого множества ????, которая ставит в соответствие каждой точке из ???? действительное число из отрезка [0, 1](см. первую часть лекций по теории возможностей). Из-за своего сходства с аддитив- ным законом вероятностей, соотношение (14) часто называют вероятностным ограничением. Однако, закон
(14) описывает природу классифицируемого набора данных, а не статистическое предположение о случайном процессе, который генерирует набор данных.
Процедура алгоритма нечеткой кластеризации состоит из следующих шагов. Случайным образом сгенериро- вать матрицу нечеткого разбиения ????
(1)
= {????
(1)
????????
}
, ???? = 1, . . . , ????, ???? = 1, . . . , ????. Вычислить центры кластеров по формуле (16). Далее происходит итерации между шагами.
1. Расчитать расстояние от каждого наблюдения ????
????
до центров кластеров ????
????
, то есть ‖????
????
− ????
????
‖
;
2. Пересчитать элементы матрицы нечеткого разбиения ???? по формуле (15);
5