Методы кластеризации четкие и нечеткие

• Название: Методы кластеризации четкие и нечеткие
• Дата: 14.05.2023
• Размер: 267.87 Kb.
• Имя файла: lecture7.pdf
• Тип: Задача; #1130177

Альфацефей
Методы кластеризации: четкие и нечеткие.
Кластерный анализ – это метод разделение данных на классы объектов, в каждом из которых объекты имеют похожие свойства. Сам по себе кластерный анализ - это не конкретный алгоритм, а общая задача, которую необходимо решить с помощью различных алгоритмов. Не существует объективно «правильного» алгорит- ма кластеризации. Наиболее подходящий алгоритм кластеризации необходимо выбирать экспериментально,
в зависимости от набора данных, если только не существует математической причины предпочесть один алгоритм другому.
Методы кластеризации можно разделять по способу обработки данных, по способу анализа данных, по мас- штабируемости, по времени выполнения и так далее. Методы по способу анализа данных, в свою очередь,
разделяют на четкие (или традиционные) и нечеткие. К четким алгоритмам относятся те алгоритмы, в кото- рых каждый объект данных принадлежит одному кластеру. К нечетким алгоритмам кластеризации относятся те, в которых каждый объект данных принадлежит более одному кластеру с определенной степенью.
В 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

Альфацефей
3. Перевычислить центры кластеров по формуле (16) для новых элементов матрицы 𝑊 из пункта 2;
4. Сравнить 𝑊
(𝑡+1)
с 𝑊
(𝑡)
, где 𝑡 – номер итерации. Если ‖𝑊
(𝑡+1)
− 𝑊
(𝑡)
‖ < 𝜀
(для заданного 𝜀), то останавливаемся, иначе – переходим на первый шаг.
Число кластеров 𝑐, как и в случае алгоритма 𝑘-средних, необходимо знать заранее. Чем больше экспоненци- альный вес 𝑚, тем более "размазанной" становится конечная матрица нечеткого разбиения 𝑊 . При 𝑚 → ∞
элементы матрицы 𝑊 будут равны 1/𝑐. Это будет говорить о том, что все наблюдаемые элементы принадле- жат всем кластерам с одной и той же степенью 1/𝑐. При 𝑚 → 1 элементы матрицы 𝑊 будут сходится либо к 0, либо к 1, что говорит о четком разделении наблюдаемых элементов на кластеры, а функция минимиза- ции будет совпадать с функцией минимизации в алгоритме 𝑘-средних. Кроме того, экспоненциальный вес 𝑚
позволяет при вычислении координат центров кластеров усилить влияние объектов с большими значениями степеней принадлежности и уменьшить влияние объектов с малыми значениями степеней принадлежности.
На сегодня не существует теоретически обоснованного правила выбора значения экспоненциального веса.
Обычно устанавливают 𝑚 = 2.
Несмотря на успехи алгоритма нечеткой кластеризации в более естественном разделении данных на кластеры,
проблема чувствительности к шуму осталась. Достаточно рассмотреть простой пример. Пусть у нас есть два кластера. Если наблюдения 𝑥
𝑘
равноудалены от центров обоих кластеров, то в независимости от удаленности от этих центров, их степени принадлежности из условия (14) совпадают и равны 0.5. Поэтому шумовым точ- кам, находящимся далеко, но равноудаленно от центров двух кластеров, тем не менее может быть присвоено равное членство в обоих кластерах, тогда как кажется гораздо более естественным, чтобы такие точки имели очень низкую степень принадлежности или даже не принадлежали ни к какому-либо кластеру.
К недостатками алгоритма нечеткой кластеризации также можно отнести зависимость от выбора значений степеней принадлежности 𝑤
𝑖𝑗
на начальном этапе, а также сходимость к локальным минимумам.
Форма кластеров в любом алгоритме кластеризации определяется функцией, которая исследуется на мини- мум, в которой в свою очередь участвует расстояние, индуцирующее топологическую метрику в R
𝑑
. Поэтому в алгоритме нечеткой кластеризации кластеры могут принимать форму, близкую к сферической, как и в случае алгоритма k-средних. Чтобы преодолеть это ограничение алгоритмы нечеткой кластеризации пошли в своем развитии по следующим направлениям.
Первое направление относится к алгоритмам, основу которых составила работа D.E. Gustafson and W.C.
Kessel [10]. В ней предложено заменить норму расстояния ‖𝑥
𝑖
− 𝛽
𝑗
‖
2
в функции, исследуемой на минимум, на альтернативную норму ‖𝑥
𝑖
−𝛽
𝑗
‖
2
𝐴
𝑗
= (𝑥
𝑖
−𝛽
𝑗
)
𝑇
𝐴
𝑗
(𝑥
𝑖
−𝛽
𝑗
)
, где 𝐴
𝑗
– симметричные положительно-определенные матрицы и det 𝐴
𝑗
= 𝜌
𝑗
, 𝜌
𝑗
> 0
. Таким образом, каждый кластер принимает форму, которая заложена в
𝐴
𝑗
. Также они признали, что необходимые условия для поиска локального минимума, имеют сходство с уравнениями максимального правдоподобия в EM-алгоритме, применяемом для разделения смеси гауссиан.
Второе направление, по которому развивались нечеткие алгоритмы, появилось из работы [5], в которой нечет- кие кластеры имеют форму линии. Из этой работы выросло целое направление разных алгоритмов нечеткой кластеризации, в которых центры кластеров заменяются на более общие структуры, типа линий, плоскостей,
гиперкубов и так далее.
4 Возможностный алгоритм кластеризации (PCM).
R. Krishnapuram и J.M. Keller [11] предложили идею ослабления ограничения (14) путем добавления второго члена в функции (11), что позволило решить проблему с шумовыми точками.
Пусть задано множество наблюдений 𝑋 = (𝑥
1
, . . . , 𝑥
𝑁
)
, где 𝑥
𝑖
∈ R
𝑑
, 𝑖 = 1, . . . , 𝑁, 𝛽 = (𝛽
1
, . . . , 𝛽
𝐶
)
– центры кластеров, 𝑑
2
𝑖𝑗
– расстояние от точки 𝑥
𝑖
до центра 𝛽
𝑗
, а 𝑈 = {𝑢
𝑖𝑗
}
– матрица размером 𝐶 × 𝑁, элементы которой являются характеристическими значениями элемента 𝑥
𝑗
по отношению к кластеру 𝑆
𝑖
. Требуется разбить множество наблюдений 𝑋 на 𝐶 нечетких кластеров 𝑆
1
, . . . , 𝑆
𝐶
, таким образом, чтобы минимизировать функцию потерь arg min
(𝑈,𝛽)
𝐶
∑︁
𝑖=1
𝑁
∑︁
𝑗=1
𝑢
𝑚
𝑖𝑗
𝑑
2
𝑖𝑗
+
𝐶
∑︁
𝑖=1
𝜂
𝑖
𝑁
∑︁
𝑗=1
(1 − 𝑢
𝑖𝑗
)
𝑚
,
(17)
6

Альфацефей где 𝑚 ∈ [1, +∞) – экспоненциальный вес, 𝜂
𝑖
– подходящие положительные числа. На характеристические значения 𝑢
𝑖𝑗
взамен (12)–(14) накладываются следующие ограничения:
𝑢
𝑖𝑗
∈ [0, 1]
для всех 𝑖, 𝑗,
(18)
0 <
𝑁
∑︁
𝑗=1
𝑢
𝑖𝑗
≤ 𝑁
для всех 𝑖,
(19)
max
𝑖
𝑢
𝑖𝑗
> 0
для всех 𝑗.
(20)
Минимизация функции (17) предполагает, чтобы в первом слагаемом расстояние от точки 𝑥
𝑖
до центра кла- стера 𝛽
𝑗
было как можно меньше, в то время, как во втором слагаемом 𝑢
𝑖𝑗
должно быть как можно ближе к 1. Если бы в (17) отсутствовало бы второе слагаемое, то без ограничения вида (14) на 𝑢
𝑖𝑗
, минимизация функции приводила бы к тривиальному решению 𝑢
𝑖𝑗
= 0
для всех 𝑖, 𝑗.
Заметим, что строки и столбцы матрицы 𝑈 = {𝑢
𝑖𝑗
}
независимы друг от друга. Поэтому минимизацию функ- цию (17) можно свести к минимизации 𝐶𝑁 независимых функций
𝑢
𝑚
𝑖𝑗
𝑑
2
𝑖𝑗
+ 𝜂
𝑖
(1 − 𝑢
𝑖𝑗
)
𝑚
(21)
Согласно необходимым условиям локального экстремума, получаем:
𝑢
𝑖𝑗
=
1 1 +
(︁
𝑑
2
𝑖𝑗
𝜂
𝑖
)︁
1
𝑚−1
, 𝑖 = 1, . . . 𝐶, 𝑗 = 1, . . . , 𝑁,
(22)
𝛽
𝑗
=
∑︀
𝑁
𝑗=1
𝑢
𝑚
𝑖𝑗
𝑥
𝑗
∑︀
𝑁
𝑗=1
𝑢
𝑚
𝑖𝑗
, 𝑖 = 1, . . . , 𝐶.
(23)
Элементы матрицы 𝑈 = {𝑢
𝑖𝑗
}
сильно зависит от выбора параметра 𝜂
𝑖
. Если 𝜂
𝑖
маленькое, то и 𝑢
𝑖𝑗
маленькое.
Если 𝜂
𝑖
большое, то 𝑢
𝑖𝑗
также большое. Также 𝜂
𝑖
определяет степень, с которой второе слагаемое в (17)
сравнимо с первым. Если оба слагаемых в (17) равновесны, то 𝜂
𝑖
должно быть порядка 𝑑
2
𝑖𝑗
. R. Krishnapuram и J.M. Keller предложили следующие соотношения для 𝜂
𝑖
( [11], [12]):
𝜂
𝑖
=
∑︀
𝑁
𝑗=1
𝑢
𝑚
𝑖𝑗
𝑑
2
𝑖𝑗
∑︀
𝑁
𝑗=1
𝑢
𝑚
𝑖𝑗
, 𝑖 = 1, . . . , 𝐶,
(24)
𝜂
𝑖
=
∑︀
𝑢
𝑖𝑗
>𝛼
𝑑
2
𝑖𝑗
∑︀
𝑢
𝑖𝑗
>𝛼
1
, 𝑖 = 1, . . . , 𝐶,
(25)
где 0 < 𝛼 < 1. Параметр 𝜂
𝑖
может быть фиксированным для всех итераций алгоритма, если кластеры имеют похожую форму. В общем случае 𝜂
𝑖
меняется в каждой итерации алгоритма, что может привести к неустой- чивости, так как необходимые условия локального экстремума получены для фиксированного 𝜂
𝑖
. Поэтому часто сначала применяют алгоритм нечеткой кластеризации для инициализации 𝑢
𝑖𝑗
, далее вычисляют 𝜂
𝑖
по формуле (24), после чего применяют возможностный алгоритм кластеризации, в котором 𝜂
𝑖
вычисляется по формуле (25).
Значение 𝑚 играет важную роль в определении характеристических значений 𝑢
𝑖𝑗
. На следующем рисунке видно, что при 𝑚 → 1 характеристические значения 𝑢
𝑖𝑗
стремятся к нулю для тех точек 𝑥
𝑗
, для которых 𝑑
2
𝑖𝑗
больше, чем 𝜂
𝑖
. При 𝑚 → ∞ характеристические значения перестают стремится к нулю. Значение 𝑚 = 2 дает хорошие результаты в алгоритме нечеткой кластеризации. Однако, в возможностном алгоритме для такого значения 𝑚 характеристические функции убывают не достаточно быстро для больших значения 𝑑
2
𝑖𝑗
. Поэтому более подходящий выбор 𝑚 = 1.5 [12].
7

Альфацефей
Процедура возможностного алгоритма кластеризации выглядит следующим образом. Генерируем элементы матрицы 𝑈 = {𝑢
𝑖𝑗
}
. Вычисляем кластерные центры по формуле (23). Далее происходит итерация между шагами:
1. Расcчитать расстояние 𝑑
𝑖𝑗
от каждого наблюдения 𝑥
𝑖
до центров кластеров 𝛽
𝑗
;
2. Вычислить 𝜂
𝑖
по формуле (24) или (25);
3. Пересчитать элементы матрицы 𝑈 по формуле (22);
4. Перевычислить центры кластеров 𝛽
𝑗
по формуле (23) для новых элементов матрицы 𝑈 из пункта 3;
5. Сравнить 𝑢
(𝑡+1)
𝑖𝑗
с 𝑢
(𝑡)
𝑖𝑗
, где 𝑡 – номер итерации. Если ‖𝑢
(𝑡+1)
𝑖𝑗
− 𝑢
(𝑡)
𝑖𝑗
‖
2
< 𝜀
(для заданного 𝜀), то останав- ливаемся, иначе – переходим на первый шаг.
Предложенный R. Krishnapuram и J.M. Keller возможностный алгоритм – это только некоторая реализация общей идеи возможностного подхода. Возможностный подход означает, что характеристическое значение точки по отношению к кластеру представляет собой возможность точки принадлежать кластеру.
Так как минимизация функции (17) сводится к минимизации 𝐶𝑁 независимых функций (21) , то могут воз- никнуть совпадающие кластеры. Это проблема типична для функций, которые можно выразить, как сумму независимых функций. Причина кроется не в плохом выборе второго слагаемого в (17), а скорее в отсутствии подходящих ограничений на 𝑢
𝑖𝑗
. С одной стороны ограничение (14) в алгоритме нечеткой кластеризации слишком сильное – оно заставляет шумовые точки принадлежать одному или нескольким кластерам с доста- точно высокими степенями принадлежности. С другой стороны, ограничение (19) в возможностном алгоритме слишком слабое, так как матрица 𝑈 сильно зависит от выбора параметров 𝑚 и 𝜂
𝑖
. И хотя возможностный алгоритм кластеризации более робастный к шуму, так как шумовые точки будут принадлежать кластерам с маленькими характеристическими значениями, платить за это придется совпадающими кластерами.
Чтобы преодолеть проблему чувствительности к шуму, а также проблему совпадающих кластеров, было предложено несколько алгоритмов. Например, в работе [15] была предложена возможностно-нечеткая мо- дель кластеризации (PFCM), в которой функция, исследуемая на минимум, включала и характеристические значения 𝑢
𝑖𝑗
, и степени принадлежности 𝑤
𝑖𝑗
. Однако этот алгоритм по-прежнему сталкиваются с проблемами инициализации и выбора параметров модели. Еще один алгоритм, предложенный в [23], основан на идее, что на начальном этапе все наблюдаемые данные являются центрами кластеров. Затем происходит процедура ав- томатического слияния точек специальным образом в соответствии с исходной структурой данных. При этом число кластеров находится автоматически с сохранением робастности алгоритма. Тот факт, что все точки используются в качестве начальных центров кластеров, является серьезной проблемой при масштабировании этого алгоритма для больших объемов данных и высокой размерности.
Конечно, все направления по развитию алгоритмов кластеризации, основанных на теории нечетких множеств
L. Zadeh, здесь описать мы не можем. Но некоторые постарались донести в простой и понятной форме.
8

Альфацефей
Обзор по этой теме можно посмотреть [18].
Литература
[1] В.Ю. Королев, ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятност- ных распределений. Теоретический обзор. ИПИ РАН Москва, 2007.
[2] Ю.П. Пытьев, Возможность. Элементы теории и применения. М.: Эдиториал УРСС, 2000.
[3] М. И. Шлезингер, О самопроизвольном распознавании образов. – в сб.: Читающие автоматы. “Наукова думка”, Киев, 1965.
[4] J. C. Bezdek, Fuzzy Mathematics in Pattern Classification, Ph.D. thesis, Cornell Univ., Ithaca, NY, 1973.
[5] J. C. Bezdek, R. Gunderson, R. Ehrlich, and T. Meloy, On the extension of fuzzy k-means algorithms for the detection of linear clusters, in Proc. IEEE Conf. Decision and Control, 1978, pp. 1438–1443.
[6] A.P. Dempster, Upper and Lower Probabilities Induced by a Multivalued Mapping, Ann. Math. Statist., V.38,
1967.
[7] A. P. Dempster, N. M. Laird and D. B. Rubin, Maximum Likelihood from Incomplete Data via the EM
Algorithm, Journal of the Royal Statistical Society, Series B, V. 39, No. 1, 1977.
[8] D. Dubois and H. Prade, Possibility Theory, Probability Theory and Multiple-valued Logics: A Clarification,
Annals of Mathematics and Artificial Intelligence 32, 2001.
[9] J.C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact, well-separated clusters,
J. Cybern. 3 ,1974.
[10] D. E. Gustafson and W. C. Kessel, Fuzzy clustering with a fuzzy covariance matrix, in Proc. IEEE Conf.
Decision and Control, pp. 761–766. 1978.
[11] R. Krishnapuram and J.M. Keller, A possibilistic approach to clustering, IEEE Trans. Fuzzy Syst. 1 (2) 1993.
[12] R. Krishnapuram and J. M. Keller, The Possibilistic C-Means Algorithm: Insights and Recommendations,
IEEE Trans. Fuzzy Syst. 4(3) 1996.
[13] J.B. MacQueen, Some Methods for classification and Analysis of Multivariate Observations. Proceedings of
5th Berkeley Symposium on Mathematical Statistics and Probability. Vol.1: Statistics, University of California
Press.,1967.
[14] A. G. McKendrick, Applications of mathematics to medical problems. – Proceedings of the Edinburgh
Mathematical Society, 1926, vol. 44, p. 98-130.
[15] N.R. Pal, K. Pal, J. M. Keller and J. C. Bezdek, A Possibilistic Fuzzy C-Means Clustering Algorithm, IEEE
Trans. Fuzzy Syst. 13(4) 2005.
[16] E. H. Ruspini, A new approach to clustering, Inf. Control, vol. 15, no. 1, 1969.
[17] E. H. Ruspini, On the semantics of fuzzy logic, Int. J. Approx. Reason., vol. 5, no. 1, 1991.
[18] E. H. Ruspini, J. C. Bezdek and J. M. Keller, Fuzzy Clustering: A Historical Perspective, IEEE Computational
Intelligence Magazine, 14(1) 2019.
[19] L. J. Savage, The foundations of statistics. Dover Publication, Inc., New York, 1972.
[20] G. Shafer, A mathematical theory of evidence, Princeton University Press, 1976.
[21] L.A. Zadeh, Fuzzy sets, Information and Control, V.8, 1965.
[22] L.A. Zadeh, Calculus of fuzzy restrictions in: L.A. Zadeh, K.S. Fu, K. Tanaka and M. Shimura, eds., Fuzzy
Sets and Their Applications to Cognitive and Decision Processes, Academic Press, New York, 1975.
[23] M.-S. Yang and C.-Y. Lai, A robust automatic merging possibilistic clustering method, IEEE Trans. Fuzzy
Syst., 19(1) 2011.
9