Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
В статье проводится анализ оптимизационных методов нечеткой кластеризации FCM, NC, PCM, FRC. Рассматриваются вопросы определения значений параметров методов нечеткой кластеризации: начальных значений центроидов и параметров доверительных границ основных кластеров. Исследуется проблема устойчивости р...
Saved in:
| Published in: | Штучний інтелект |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/58480 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров / К.М. Залесская // Штучний інтелект. — 2010. — № 4. — С. 359-369. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860248990564483072 |
|---|---|
| author | Залесская, К.М. |
| author_facet | Залесская, К.М. |
| citation_txt | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров / К.М. Залесская // Штучний інтелект. — 2010. — № 4. — С. 359-369. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | В статье проводится анализ оптимизационных методов нечеткой кластеризации FCM, NC, PCM, FRC. Рассматриваются вопросы определения значений параметров методов нечеткой кластеризации: начальных значений центроидов и параметров доверительных границ основных кластеров. Исследуется проблема устойчивости решений задачи нечеткой кластеризации к определению значений указанных параметров.
Проводиться аналіз оптимізаційних методів нечіткої кластеризації FCM, NC, PCM, FRC. Розглядаються питання щодо визначення значень параметрів методів нечіткої кластеризації: початкових значень центроїдів і параметрів довірчих меж основних кластерів. Досліджується проблема стійкості рішень задачі нечіткої кластеризації відносно визначення значень вказаних параметрів.
The analysis of optimization of fuzzy clustering methods FCM, NC, PCM, FRC is being made. The question of definition of parameters values of fuzzy clustering method such as initial values of centroids and the parameters of the primal cluster confidence limits is being considered. The question of the stability of fuzzy clustering problem solution with reference to the definition of the parameters specified values is being researched.
|
| first_indexed | 2025-12-07T18:40:37Z |
| format | Article |
| fulltext |
«Штучний інтелект» 4’2010 359
5-З
УДК 519.237.8:510.22
К.М. Залесская
ОАО «Агат-Систем», г. Минск, Беларусь
k.zaleskaya@gmail.com
Анализ устойчивости методов нечеткой
кластеризации к выбору их параметров
В статье проводится анализ оптимизационных методов нечеткой кластеризации FCM, NC, PCM, FRC.
Рассматриваются вопросы определения значений параметров методов нечеткой кластеризации: начальных
значений центроидов и параметров доверительных границ основных кластеров. Исследуется проблема
устойчивости решений задачи нечеткой кластеризации к определению значений указанных параметров.
Введение
Одной из важнейших проблем практического применения методов нечеткой клас-
теризации является неустойчивость их решений к наличию аномальных наблюдений
в исследуемой совокупности наблюдений. Под аномальными наблюдениями здесь по-
нимаются наблюдения, принадлежащие классам, число представителей которых в ис-
следуемой совокупности существенно мало в сравнении с числом представителей ос-
новных классов.
Для решения задачи нечеткой кластеризации в условиях наличия в исследуемой
совокупности аномальных наблюдений разработаны специальные оптимизационные
методы, которые принято называть робастными [1]. Среди наиболее известных робаст-
ных методов нечеткой кластеризации необходимо выделить методы: Noise Clustering
(NC) [2], Possibilistic C-Means (PCM) [3], Fuzzy Robust Clustering (FRC) [4].
Несмотря на широкое применение указанных методов, необходимо отметить
недостаточное внимание, которое уделено вопросу выбора значений их параметров.
Существование проблемы выбора значений параметров кластеризации для произ-
вольной совокупности наблюдений признается исследователями и нашло отражение
в немногочисленных рекомендациях [1-4].
В данной работе исследуется проблема устойчивости решений задачи кластери-
зации оптимизационных методов NC, PCM, FRC по отношению к определению значе-
ний параметров кластеризации: начальных значений центроидов и значений парамет-
ров доверительных границ основных классов, – а также анализируются рекомендации
по определению значений указанных параметров на основе предварительного анализа
исследуемой совокупности.
Проблема выбора значений параметров
методов нечеткой кластеризации
Основой для разработки большинства оптимизационных методов нечеткой клас-
теризации послужил целевой функционал Дж. Данна и Дж. Беждека [5], лежащий в
основе классического метода нечеткой кластеризации Fuzzy C-Means (FCM):
2
1 1
( )
c n
FCM ij ij
i j
F P dγµ
= =
= ∑∑ , (1)
Залесская К.М.
«Искусственный интеллект» 4’2010 360
5-З
где P – нечеткое c -разбиение исследуемой совокупности наблюдений X на задан-
ное число c нечетких множеств , 1, ,iA i c= K ; ),( ijij xdd τ= – функция расстояния от
наблюдения Xx j ∈ до центроида iτ нечеткого кластера },,{ 1 ci AAA K∈ ; ∞<<γγ 1: –
показатель нечеткости кластеризации; 0:)( ≥= ijjiij x µµµ – функция принадлежности
наблюдения jx нечеткому кластеру iA , удовлетворяющая условию:
1
1
=∑
=
c
i
ijµ . (2)
Попытки решения проблемы устойчивости метода FCM к аномальным наблюде-
ниям привели к появлению методов NC, PCM, FRC. Указанные методы кластеризации
допускают, что исследуемой совокупности могут принадлежать наблюдения неоснов-
ных классов, что приводит к ослаблению условия (2):
1
1
≤∑
=
c
i
ijµ , (3)
где c – число основных классов, задаваемое до процедуры кластеризации.
Целевые функционалы методов NC, PCM и FRC могут быть представлены соот-
ветствующими выражениями:
∑ ∑∑∑
= == =
−+=
n
j
c
i
ij
c
i
n
j
ijijNC dPF
1 1
2
1 1
2 )1()( γγ µδµ , (4)
∑ ∑∑∑
= == =
−+=
с
i
n
j
iji
c
i
n
j
ijijPCM dPF
1 1
2
1 1
2 )1()( γγ µδµ , (5)
( )∑∑∑∑
= == =
−++=
c
i
n
j
p
iijijij
c
i
n
j
p
ijijFRC dPF
1 1
2
1 1
2 )log(*1)( δµµµµ , (6)
где γ , p – показатели нечеткости кластеризации; δ , c
ii 1}{ =δ – параметры, определяю-
щие доверительные границы основных кластеров.
Оптимизационную процедуру поиска экстремума вышеуказанных функционалов
предваряет задание числа основных классов и выбор начальных значений центроидов,
показателей нечеткости кластеризации и параметров, определяющих доверительные
границы основных кластеров. Выбор значений параметров для кластеризации произ-
вольной совокупности наблюдений является открытым вопросом нечеткой кластери-
зации.
Задача выбора начальных значений центроидов
Одним из важных вопросов, связанных с применением оптимизационных мето-
дов, разработанных для задач кластеризации в условиях возможного влияния аномаль-
ных наблюдений, является вопрос выбора начальных значений центроидов.
В работах [1-4], описывающих наиболее известные робастные методы нечеткой
кластеризации, сообщается о важности правильного выбора начальных значений цент-
роидов ввиду их влияния на конечные результаты кластеризации. Но сама проблема
устойчивости решений задачи кластеризации к выбору начальных значений центрои-
дов как таковая не рассматривается.
В вышеупомянутых работах даются краткие рекомендации по определению на-
чальных значений центроидов в случае отсутствия предварительной информации о рас-
пределении наблюдений основных классов исследуемой совокупности.
Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
«Штучний інтелект» 4’2010 361
5-З
В работе [1] при использовании робастных методов кластеризации предлагается
выполнять итерационную процедуру оптимизационного поиска оптимального разбие-
ния поочередно для всех возможных начальных значений центроидов, после чего осу-
ществлять оценку полученных разбиений и выбирать на ее основании оптимальный
результат кластеризации. При этом в качестве возможных начальных значений цент-
роидов рекомендуется рассматривать все наблюдения исследуемой совокупности,
хотя очевидно, что такая рекомендация неприемлема в вычислительном плане.
В работе [4] для метода FRC предлагается рассматривать не все возможные наб-
людения в качестве начальных значений центроидов, а лишь наиболее удаленные друг
от друга.
В работе [3] рекомендуется для определения начальных значений параметров
метода PCM делать предварительную оценку исследуемой совокупности каким-либо
другим методом кластеризации.
Для исследования устойчивости методов кластеризации FCM, NC, PCM, FRC к
выбору начальных значений центроидов представим целевые функционалы методов
как функции от центроидов )(τFF = (где ),...,( 21 cττττ = – вектор центроидов основных
кластеров) при заданной исследуемой совокупности наблюдений и определенных па-
раметрах кластеризации δ , c
ii 1}{ =δ , γ и p с учетом оптимальности выбора парамет-
ров ijµ в соответствии с выражениями из [2-5]:
1
1
1
1
2
2
),(
),(
)(
−
=
−
= ∑
c
k jk
jiFCM
ij xd
xd γ
τ
τ
τµ ; (7)
1
1
1
1
2
21
1
2
2
),(
),(),(
)(
−
=
−−
+
= ∑
c
k jk
jijiNC
ij xd
xdxd γγ
τ
τ
δ
τ
τµ ; (8)
1
1
1
2
2 ),(
1)(
−
−
+=
γ
δ
τ
τµ
i
jiPCM
ij
xd ; (9)
−=
p
i
jiFRC
ij
xd
2
2 ),(
exp)(
δ
τ
τµ . (10)
Таким образом, целевые функционалы примут вид:
∑∑
= =
=
n
j
c
i
jijiFCM xdF
1 1
2 ),()()( ττµτ γ ; (11)
∑ ∑∑∑
= == =
−+=
n
j
c
i
ji
n
j
c
i
jijiNC xdF
1 1
2
1 1
2 ))(1(),()()( γγ τµδττµτ ; (12)
∑ ∑∑∑
= == =
−+=
c
i
n
j
ijii
n
j
c
i
jiijiPCM xdF
1 1
2
1 1
2 ))(1(),()()( γγ τµδττµτ ; (13)
( )∑∑∑∑
= == =
−++=
c
i
p
i
n
j
ijiijiiji
n
j
c
i
ji
p
ijiFRC xdF
1
2
11 1
2 )())(log()(1),()()( δτµτµτµττµτ . (14)
Залесская К.М.
«Искусственный интеллект» 4’2010 362
5-З
Исследуем проблему выбора начальных значений центроидов на элементарном
частном примере. Пусть необходимо решить задачу кластеризации совокупности наб-
людений X , заданных в одномерном пространстве в соответствии с табл. 1.
Таблица 1 – Пример исследуемой совокупности наблюдений
x1 x2 x3 x4 x5 x6
– 0,1 – 0,05 0 0,05 0,1 2
Пусть определено число основных классов 1=c . Очевидно, наблюдение 6х сле-
дует считать аномальным по отношению к основному классу, представленному наблю-
дениями },,,,{ 54321 ххххх .
Пусть определены значения параметров кластеризации согласно табл. 2.
Таблица 2 – Пример исследуемой совокупности наблюдений
Наименование параметра FCM NC PCM FRC
Число основных классов 1=c 1=c 1=c 1=c
Доверительная граница основных кластеров – 3,0=δ 3,01 =δ 3,01 =δ
Показатель нечеткости кластеризации 2=γ 2=γ 2=γ 1=p
Рассмотрим однопараметрические функции )(τFF = (11) – (14), соответствую-
щие каждому из методов FCM, NC, PCM и FRC, построенные для заданной совокуп-
ности наблюдений.
Функция )(τFCMF имеет один локальный экстремум в точке, смещенной относи-
тельно действительного центроида основного кластера в сторону аномального наблю-
дения (рис. 1 a).
В данном случае можно утверждать, что поиск оптимального разбиения мето-
дом FCM приведет к решению, соответствующему смещению центроида основного
кластера относительно действительного расположения. Учитывая единственность экс-
тремума функции )(τFCMF , можно говорить об отсутствии влияния выбора начального
значения центроида на результат кластеризации методом FCM. Стоит заметить, что это
утверждение нельзя обобщить на общий случай для произвольного числа кластеров.
а б
Рисунок 1 – Графики функций )(τFCMF (а);
)(τFRCF – « −−− », )(τNCF и )(τPCMF –« −» (б)
Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
«Штучний інтелект» 4’2010 363
5-З
Функции )(τNCF , )(τPCMF , )(τFRCF имеют два локальных экстремума: в точке,
близкой к действительному центроиду основного кластера, и в точке, близкой к ано-
мальному наблюдению (рис. 1 б).
Таким образом, при использовании методов NC, PCM и FRC в качестве конеч-
ного результата кластеризации заданной совокупности может быть получено одно из
двух решений: верное, соответствующее совпадению центроида с действительным цент-
роидом основного кластера, или ложное с центроидом в точке, близкой к аномальному
наблюдению. Ложное решение возможно, если начальное значение центроида принад-
лежит локальной области аномального наблюдения.
Данный пример показывает различие влияния выбора начального значения цент-
роида на решения робастных методов NC, PCM и FRC в сравнении с методом FCM.
При условии корректного выбора начальных значений центроидов отклонение
решений робастных методов NC, PCM и FRC от действительных центроидов основ-
ных классов в условиях аномальных наблюдений существенно мало в сравнении с ре-
шениями метода FCM. Это может быть объяснено характерным свойством целевых
функционалов методов NC, PCM и FRC, которое выражается в незначительном из-
менении доли, вносимой аномальными наблюдениями в значения функционалов, в
случае изменения положения центроидов в локальной области основных кластеров [6].
Иными словами, поиск оптимального значения центроида робастными методами осу-
ществляется среди наблюдений локальной области заданного начального значения
центроида, в отличие от метода FCM, для которого на решение задачи кластеризации
одинаково влияют все наблюдения исследуемой совокупности. Это также объясняет
то, что ошибочный выбор начального значения одного из центроидов в области ано-
мального наблюдения неминуемо приводит робастные методы к ложному решению.
Рассмотренный пример показывает влияние ошибки выбора начального значе-
ния центроида на результат поиска оптимального положения отдельно взятого цент-
роида. Учитывая особенность некоторых методов решать задачу нечеткой кластериза-
ции при условии взаимозависимости центроидов, целесообразно исследовать влияние
ошибки инициализации одного центроида на общее решение задачи кластеризации
для случая нескольких кластеров.
Для этого рассмотрим следующую элементарную задачу кластеризации наблю-
дений в одномерном признаковом пространстве для случая двух основных кластеров.
Пусть исследуемая совокупность состоит из двух наблюдений 01 =x и 12 =x . Заданную
совокупность можно считать прототипом двух компактных хорошо разделимых клас-
теров одинаковой мощности. Пусть определены значения параметров кластеризации
согласно табл. 2.
На рис. 2 представлены функции )(τFCMF , )(τNCF , )(τPCMF , )(τFRCF (11) – (14),
характеризующие значения соответствующих целевых функционалов при различном
расположении центроидов относительно фиксированных значений наблюдений.
Заметим, что все указанные функции имеют глобальные экстремумы, соответ-
ствующие действительным значениям центроидов.
Как известно, функционалы )(PFPCM и )(PFFRC представимы как суммы независи-
мых оценок оптимальности расположения каждого отдельного центроида основного
кластера [1]. Поэтому методы FRC и PCM допускают совпадение оптимальных зна-
чений центроидов ),(),( 1121 хх=ττ и ),(),( 2221 хх=ττ .
Залесская К.М.
«Искусственный интеллект» 4’2010 364
5-З
а б
в
г
Рисунок 2 – Графики функций )(τFCMF (а), )(τNCF (б), )(τPCMF (в), )(τFRCF (г)
Пусть для центроида 1τ найдено ложное устойчивое положение вне локальной об-
ласти основных кластеров ( 11 х<<τ или 21 х>>τ ). Тогда, как следует из графиков, для
методов NC, PCM и FRC оптимальным положением центроида 2τ являются действи-
тельные центроиды основных кластеров ( 12 х=τ и 22 х=τ ). Для методов PCM и FRC
это обусловлено независимостью оценок оптимальности расположения центроидов.
Заметим, что метод NC, подобно методам PCM и FRC, в случае ошибки инициализации
одного из центроидов позволяет верно определять оптимальное положение остальных.
Представленное свойство закономерно, поскольку влияние совокупности наблюдений
на оценку оптимального положения центроида ограничено локальной областью. При тех
же условиях для метода FCM оптимальным положением центроида 2τ является точка,
равноудаленная от действительных центроидов основных кластеров: ( ) 2212 хх +=τ .
Таким образом, ошибка выбора начального значения одного центроида приводит к
ошибке решения задачи кластеризации в целом.
Вышеприведенные примеры позволяют сформировать представление о послед-
ствиях ошибочного выбора начальных значений центроидов.
Пользуясь выводами проведенного исследования, можно утверждать, что неко-
торые рекомендации [1-4] по выбору начальных значений центроидов для робастных
методов являются в общем случае неправомерными. При выборе начальных значений
Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
«Штучний інтелект» 4’2010 365
5-З
центроидов среди наиболее удаленных друг от друга наблюдений, либо среди произ-
вольных наблюдений исследуемой совокупности, велика вероятность выбора аномаль-
ного наблюдения в качестве центроида, что может привести к нахождению ложного
разбиения. Многократное решение задачи кластеризации при переборе значений па-
раметров инициализации трудоемко и не всегда доступно исследователю.
Рекомендацию использования процедуры предварительной оценки исследуемой
совокупности с помощью альтернативного метода кластеризации, не обязательно не-
четкого, для определения начальных значений центроидов, приведенную в [3], следует
считать применимой не только для метода РСМ, но и для методов NC и FRC. При ис-
пользовании метода FCM для предварительной оценки необходимо помнить о чувст-
вительности решений данного метода к аномальным наблюдениям.
Задача выбора значений параметров
доверительных границ основных кластеров
Целевой функционал )(PF методов NC, РСМ, FRC может быть охарактеризован
показательной функцией ( )xQQ = , значение которой в произвольной точке x являет-
ся некоторой долей, вносимой наблюдением x в общую оценку разбиения P при ус-
ловии принадлежности x исследуемой совокупности [6]. Функции ( )xQ методов NC,
РСМ, FRC ограничены во всем признаковом пространстве и имеют асимптотическое
поведение вне локальных областей заданных центроидов основных кластеров. Данное
свойство позволяет ограничить влияние на оценку разбиения аномальных наблюде-
ний, находящихся вне определенных локальных областей центроидов основных клас-
теров. Размер каждой из таких локальных областей центроидов определяется соотве-
тствующим параметром доверительной границы основного кластера, что объясняет
чувствительность решения задачи кластеризации к выбору значений этих параметров.
Обобщим рекомендации по выбору значений параметров доверительных гра-
ниц основных кластеров δ , c
ii 1}{ =δ , приведенные в работах [1-4], [7]. В соответствии
с указанными источниками значения параметров δ , c
ii 1}{ =δ должны быть установлены
на этапе, предваряющем процедуру кластеризации методами NC, PCM и FRC. В про-
цессе кластеризации значения выбранных изначально параметров δ , c
ii 1}{ =δ не изме-
няются или корректируются.
Согласно работе [2] параметр δ для метода NC предлагается выбирать в соот-
ветствии с выражением:
∑∑=
n
j
c
i
ijxd
nc
),( τλδ , (15)
где λ – масштабирующий параметр; c – число кластеров; iτ – центроид нечеткого
кластера },,{ 1 ci AAA K∈ ; n – количество наблюдений исследуемой совокупности. В дан-
ной рекомендации для определения значений параметров λ и c
ii 1}{ =τ требуется оценка
исследуемой совокупности, предваряющая инициализацию параметра δ .
Авторы работы [7] предлагают избежать предварительного определения значе-
ний центроидов c
ii 1}{ =τ , используя для выбора значения параметра δ выражение:
rαδ = , (16)
Залесская К.М.
«Искусственный интеллект» 4’2010 366
5-З
где α – масштабирующий параметр, r – радиус с равновеликих гиперобъемов ми-
нимального размера, выделенных в признаковом пространстве и способных вместить
все наблюдения исследуемой совокупности. Для использования данной рекоменда-
ции исследователю необходимо самостоятельно определить алгоритм выделения ги-
перобъема.
В работах [1], [3], [4] для выбора значений параметров c
ii 1}{ =δ методов PCM и FRC
предлагается использовать результаты предварительной кластеризации. В частности,
начальные значения c
ii 1}{ =δ рекомендуется определять как взвешенные внутриклассо-
вые расстояния соответствующих кластеров c
i
iA 1}{ = :
∑
∈
=
α
τωλδ
)(
2 ),(
ij Px
ijij
i
i xd
n , (17)
где λ – масштабирующий параметр; in – нормирующий коэффициент, оценивающий
количество наблюдений нечеткого кластера iA , в качестве которого могут выступать
α)( iP – мощность подмножества α -уровня нечеткого c -разбиения P исследуемой со-
вокупности наблюдений X , либо ∑
=
n
j
ij
1
γµ – сумма степеней принадлежности наблюде-
ний кластеру iA ; ijω , ]1,0[∈jω – весовой коэффициент, характеризующий оценку при-
надлежности наблюдения jx нечеткому кластеру iA , в качестве которого могут ис-
пользоваться значения степеней принадлежности ijµ .
В работе [4] предлагается выбирать начальные значения параметров }{ iδ функцио-
налов )(PFPCM и )(PFFRC в соответствии с выражением:
{ } ikikki ≠−= ,min ττδ , (18)
причем в качестве начальных значений центроидов c
ii 1}{ =τ допускается выбирать наб-
людения, находящиеся на наибольшем удалении друг от друга.
Для оценки данных рекомендаций проведем исследование устойчивости роба-
стных методов кластеризации к выбору значений параметров доверительных границ
основных кластеров.
Представим целевые функционалы )(PFPCM и )(PFFRC как суммы компонент ),( iiR δτ ,
ci ,,1K= , каждый из которых является оценкой оптимальности расположения цент-
роида iτ с соответствующим ему параметром iδ по отношению к исследуемой сово-
купности наблюдений:
∑
=
=
c
i
iiRPF
1
),()( δτ , (19)
∑∑
==
−+=
n
j
j
n
j
jjPCM xdR
1
2
1
2 ))(1(),()(),( γγ τµδττµδτ , (20)
( )∑∑
==
−++=
n
j
jjj
p
n
j
j
p
jFRC xdR
1
2
1
2 )())(log()(1),()(),( τµτµτµδττµδτ . (21)
Исследуем проблему выбора параметров доверительной границы основных клас-
теров на элементарном частном примере. Пусть необходимо решить задачу кластери-
Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
«Штучний інтелект» 4’2010 367
5-З
зации совокупности наблюдений X , заданных в одномерном пространстве в соответ-
ствии с табл. 3.
Таблица 3 – Пример исследуемой совокупности наблюдений
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12
–0,125 –0,075 –0,025 0,025 0,075 0,125 0,85 0,9 0,95 1,05 1,1 1,15
Исследуемая совокупность X (табл. 3) представлена двумя хорошо разделимы-
ми классами одинаковой мощности с центрами в точках 0 и 1.
На рис. 3 представлены графики функций ),( δτPCMR и ),( δτFRCR при разных зна-
чениях параметра δ .
а б
Рисунок 3 – Графики функций PCMR « −», FRCR « −− »
при значении параметра 2,0=δ (а) и 9,0=δ (б)
Графики показывают, что в зависимости от выбора значения параметра δ , функ-
ции ),( δτPCMR и ),( δτFRCR могут иметь различное число локальных экстремумов.
В случае выбора значения параметра δ , близкого к значению расстояния от
действительного центроида основного кластера до наиболее удаленного наблюдения
этого кластера, функции ),( δτPCMR и ),( δτFRCR имеют два локальных экстремума в
точках, близких к центрам классов.
При выборе значения параметра δ , превышающего половину расстояния между
центрами классов, функции ),( δτPCMR и ),( δτFRCR вырождаются в функции, имеющие
один локальный экстремум. Это может быть объяснено пересечением доверительных
границ основных кластеров и их объединением в один кластер. При таком выборе
значения δ оптимальным расположением центроида является точка, находящаяся
между действительными центрами кластеров.
При выборе значения параметра δ значительно меньше значения расстояния
от действительного центроида основного кластера до наиболее удаленного наблюде-
ния этого кластера вероятно появление нескольких экстремумов функций ),( δτPCMR
и ),( δτFRCR , соответствующих одному и тому же основному кластеру (рис. 4). Такое
разделение кластера возможно в случае, если наблюдения распределены по закону, от-
личному от нормального.
Залесская К.М.
«Искусственный интеллект» 4’2010 368
5-З
Рисунок 4 – Графики функций PCMR « −», FRCR « −− » при значении параметра 05,0=δ
Вышеприведенные примеры позволяют сформировать представление о послед-
ствиях ошибочного выбора параметров доверительных границ основных кластеров.
Отметим еще одну важную особенность робастных методов PCM и FRC. Упо-
мянутые методы кластеризации допускают выбор различных параметров доверитель-
ных границ для различных основных кластеров. Пусть для двух кластеров
1i
A и
2i
A
определены соответственно значения параметров доверительных границ
1i
δ и
2i
δ , при-
чем
21 ii δδ > . Тогда для любой невырожденной выборки для любых значений τ спра-
ведливо неравенство:
),(),(
21 ii RR δτδτ > .
Это свойство функций ),( δτPCMR и ),( δτFRCR является следствием выражений
(20) и (21). Данное свойство исключает возможность сравнения оценок разбиения
)(PFPCM и )(PFFRC , полученных при выборе различных значений параметров }{ iδ .
Результаты проведенного исследования позволяют выявить характер последст-
вий ошибочного выбора значений параметров доверительных границ основных клас-
теров. Заметим неправомерность некоторых рекомендаций.
При выборе значения каждого из параметров iδ , ci ,,1K= как расстояния
между центроидами { } ikiki ≠− ,min ττ , согласно [4], велика вероятность объеди-
нения кластеров kA и iA , что не соответствует действительному разбиению.
Изменение значений параметров }{ iδ согласно [3] в рамках многократного вы-
полнения процедуры оптимизационного поиска решения не позволяет оценивать ре-
зультаты кластеризации, непосредственно сравнивая значения функционалов. Для срав-
нения должны быть использованы иные критерии оценки разбиения.
Для правильного выбора значений параметров δ , }{ iδ методов NC, PCM и FRC
обязательным условием должно быть наличие некоторой предварительной оценки рас-
пределения каждого основного класса исследуемой совокупности.
Представленные в [2], [3] рекомендации выбора значений параметров δ , }{ iδ , ос-
нованные на предварительной оценке совокупности наблюдений с помощью альтерна-
тивного метода кластеризации, следует считать применимыми не только для методов
NC и РСМ, но и для метода FRC.
Анализ устойчивости методов нечеткой кластеризации к выбору их параметров
«Штучний інтелект» 4’2010 369
5-З
Выводы
Как известно, наличие аномальных наблюдений в выборке приводит к сущест-
венным ошибкам решений задачи нечеткой кластеризации с использованием класси-
ческого метода FCM. Решение проблемы может быть найдено в применении робастных
методов кластеризации, среди которых наиболее известными являются методы NC,
PCM и FRC. Следует заметить, что ослабление влияния аномальных наблюдений на
решения задачи кластеризации методами NC, PCM и FRC достигается с помощью вы-
деления некоторых доверительных областей основных кластеров. Наблюдения, находя-
щиеся вне доверительных областей основных кластеров, вносят приблизительно оди-
наковую долю в общую оценку разбиения и не оказывают значительного влияния на
результаты кластеризации. Применение указанных робастных методов нечеткой клас-
теризации осложняется проблемой определения значений их параметров, характери-
зующих доверительные области основных кластеров.
В данной работе проведен анализ влияния ошибки определения параметров ме-
тодов кластеризации NC, PCM и FRC: начальных значений центроидов и параметров
доверительных границ основных кластеров. Проведено сравнение устойчивости реше-
ний робастных методов кластеризации NC, PCM и FRC и метода FCM к выбору на-
чальных значений центроидов. На примере методов PCM и FRC исследовано влияние
ошибки определения значений параметров доверительных границ основных кластеров.
На основании частных элементарных примеров сделан вывод о неправомерности
некоторых авторских рекомендаций упрощенного выбора значений указанных параметров.
В рамках исследований была установлена необходимость предварительной оцен-
ки распределения основных классов исследуемой совокупности наблюдений для оп-
ределения значений параметров робастных методов NC, PCM и FRC и возможность
использования с этой целью методов кластеризации.
Литература
1. Davé R.N. Robust Clustering Methods: A Unified View / R.N. Davé, R. Krishnapuram // IEEE Transacti-
ons on Fuzzy Systems. – 1997. – № 5. – P. 270-293.
2. Dave R.N. Characterization and detection of noise in clustering / R.N. Davé // Pattern Recognition. –
1991. – Vol. 11, № 12. – Р. 657-664.
3. Krishnapuram R. A possibilistic approach to clustering / R. Krishnapuram, J.M. Keller // IEEE Trans. Fuzzy
Systems. – 1993. – № 1 – P. 98-110.
4. Yang T.-N. Competitive algorithm for the clustering of noisy data / T.-N. Yang, S.-D. Wang // Fuzzy Sets
and Systems. – 2004. – № 141. – P. 281-299.
5. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms / Bezdek J.C. – New York. :
Plenum Press, 1981. – 230 p.
6. Садовская К.М. Анализ устойчивости методов нечеткой кластеризации к аномальным наблюдени-
ям / К.М. Садовская // Информатика. – 2009. – 4. – № 24.
7. Rehm F. A novel approach to noise clustering for outlier detection / F. Rehm, F. Klawonn, R. Kruse //
Soft Comput. – 2007. – № 11. – P. 489-494.
К.М. Залеська
Аналіз стійкості методів нечіткої кластеризації щодо вибору їх параметрів
Проводиться аналіз оптимізаційних методів нечіткої кластеризації FCM, NC, PCM, FRC. Розглядаються
питання щодо визначення значень параметрів методів нечіткої кластеризації: початкових значень центроїдів і
параметрів довірчих меж основних кластерів. Досліджується проблема стійкості рішень задачі нечіткої
кластеризації відносно визначення значень вказаних параметрів.
K.M. Zaleskaya
The Analysis of Fuzzy Clustering Methods Stability to the Choice of their Parameters
The analysis of optimization of fuzzy clustering methods FCM, NC, PCM, FRC is being made. The question
of definition of parameters values of fuzzy clustering method such as initial values of centroids and the parameters
of the primal cluster confidence limits is being considered. The question of the stability of fuzzy clustering
problem solution with reference to the definition of the parameters specified values is being researched.
Статья поступила в редакцию 01.06.2010.
|
| id | nasplib_isofts_kiev_ua-123456789-58480 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:40:37Z |
| publishDate | 2010 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Залесская, К.М. 2014-03-25T14:50:50Z 2014-03-25T14:50:50Z 2010 Анализ устойчивости методов нечеткой кластеризации к выбору их параметров / К.М. Залесская // Штучний інтелект. — 2010. — № 4. — С. 359-369. — Бібліогр.: 7 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/58480 519.237.8:510.22 В статье проводится анализ оптимизационных методов нечеткой кластеризации FCM, NC, PCM, FRC. Рассматриваются вопросы определения значений параметров методов нечеткой кластеризации: начальных значений центроидов и параметров доверительных границ основных кластеров. Исследуется проблема устойчивости решений задачи нечеткой кластеризации к определению значений указанных параметров. Проводиться аналіз оптимізаційних методів нечіткої кластеризації FCM, NC, PCM, FRC. Розглядаються питання щодо визначення значень параметрів методів нечіткої кластеризації: початкових значень центроїдів і параметрів довірчих меж основних кластерів. Досліджується проблема стійкості рішень задачі нечіткої кластеризації відносно визначення значень вказаних параметрів. The analysis of optimization of fuzzy clustering methods FCM, NC, PCM, FRC is being made. The question of definition of parameters values of fuzzy clustering method such as initial values of centroids and the parameters of the primal cluster confidence limits is being considered. The question of the stability of fuzzy clustering problem solution with reference to the definition of the parameters specified values is being researched. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные системы планирования, управления, моделирования и принятия решений Анализ устойчивости методов нечеткой кластеризации к выбору их параметров Аналіз стійкості методів нечіткої кластеризації щодо вибору їх параметрів The Analysis of Fuzzy Clustering Methods Stability to the Choice of their Parameters Article published earlier |
| spellingShingle | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров Залесская, К.М. Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| title | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| title_alt | Аналіз стійкості методів нечіткої кластеризації щодо вибору їх параметрів The Analysis of Fuzzy Clustering Methods Stability to the Choice of their Parameters |
| title_full | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| title_fullStr | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| title_full_unstemmed | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| title_short | Анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| title_sort | анализ устойчивости методов нечеткой кластеризации к выбору их параметров |
| topic | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| topic_facet | Интеллектуальные системы планирования, управления, моделирования и принятия решений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/58480 |
| work_keys_str_mv | AT zalesskaâkm analizustoičivostimetodovnečetkoiklasterizaciikvyboruihparametrov AT zalesskaâkm analízstíikostímetodívnečítkoíklasterizacííŝodoviboruíhparametrív AT zalesskaâkm theanalysisoffuzzyclusteringmethodsstabilitytothechoiceoftheirparameters |