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

Альфацефей
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