Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации

Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации

В статье рассматривается метод определения оптимального числа кластеров в нечетком с-разбиении, основанный на построении интервала значений наиболее возможного числа классов с использованием нечетких чисел. Предложена модификация FCM-CV-алгоритма и приводится результат вычислительного эксперимент...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2008
Автор: Вятченин, Д.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2008
Теми:
Нейросетевые и нечеткие системы
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/7150
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2008. — № 3. — С. 523-533. — Бібліогр.: 13 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-7150
record_format dspace
spelling Вятченин, Д.А.
2010-03-24T18:17:42Z
2010-03-24T18:17:42Z
2008
Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2008. — № 3. — С. 523-533. — Бібліогр.: 13 назв. — рос.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/7150
519.237.8+510.22
В статье рассматривается метод определения оптимального числа кластеров в нечетком с-разбиении, основанный на построении интервала значений наиболее возможного числа классов с использованием нечетких чисел. Предложена модификация FCM-CV-алгоритма и приводится результат вычислительного эксперимента.
У статті розглядається метод визначення оптимального числа кластерів у нечіткому с-розбитті, заснований на побудові інтервалу значень найбільш можливого числа класів з використанням нечітких чисел. Запропонована модифікація FCM-CV-алгоритму і наводиться результат обчислювального експерименту.
This paper considers a method of detection of the optimal number of clusters in the fuzzy c-partition based on constructing an interval of values of the most possible numbers of classes with using of fuzzy numbers. A modification of the FCM-CV-algorithm is proposed and a result of the numerical experiment is given.
Исследования проводились при поддержке гранта Президиума Национальной академии наук Беларуси в соответствии с Постановлением № 157 Бюро Президиума НАН Беларуси от 11.04.2007.
ru
Інститут проблем штучного інтелекту МОН України та НАН України
Нейросетевые и нечеткие системы
Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
Використання нечітких чисел задля обґрунтування кластерів у методах нечіткої кластеризації
An Application of Fuzzy Numbers for Cluster Validity in Fuzzy Clustering Methods
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
spellingShingle Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
Вятченин, Д.А.
Нейросетевые и нечеткие системы
title_short Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
title_full Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
title_fullStr Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
title_full_unstemmed Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
title_sort применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации
author Вятченин, Д.А.
author_facet Вятченин, Д.А.
topic Нейросетевые и нечеткие системы
topic_facet Нейросетевые и нечеткие системы
publishDate 2008
language Russian
publisher Інститут проблем штучного інтелекту МОН України та НАН України
format Article
title_alt Використання нечітких чисел задля обґрунтування кластерів у методах нечіткої кластеризації
An Application of Fuzzy Numbers for Cluster Validity in Fuzzy Clustering Methods
description В статье рассматривается метод определения оптимального числа кластеров в нечетком с-разбиении, основанный на построении интервала значений наиболее возможного числа классов с использованием нечетких чисел. Предложена модификация FCM-CV-алгоритма и приводится результат вычислительного эксперимента. У статті розглядається метод визначення оптимального числа кластерів у нечіткому с-розбитті, заснований на побудові інтервалу значень найбільш можливого числа класів з використанням нечітких чисел. Запропонована модифікація FCM-CV-алгоритму і наводиться результат обчислювального експерименту. This paper considers a method of detection of the optimal number of clusters in the fuzzy c-partition based on constructing an interval of values of the most possible numbers of classes with using of fuzzy numbers. A modification of the FCM-CV-algorithm is proposed and a result of the numerical experiment is given.
issn 1561-5359
url https://nasplib.isofts.kiev.ua/handle/123456789/7150
citation_txt Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2008. — № 3. — С. 523-533. — Бібліогр.: 13 назв. — рос.
work_keys_str_mv AT vâtčeninda primenenienečetkihčiseldlâobosnovaniâklasterovvmetodahnečetkoiklasterizacii
AT vâtčeninda vikoristannânečítkihčiselzadlâobgruntuvannâklasterívumetodahnečítkoíklasterizacíí
AT vâtčeninda anapplicationoffuzzynumbersforclustervalidityinfuzzyclusteringmethods
first_indexed 2025-11-27T02:54:31Z
last_indexed 2025-11-27T02:54:31Z
_version_ 1850795579603419136
fulltext «Штучний інтелект» 3’2008 523 7В УДК 519.237.8+510.22 Д.А. Вятченин Объединенный институт проблем информатики НАН Беларуси, г. Минск viattchenin@mail.ru Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации∗ В статье рассматривается метод определения оптимального числа кластеров в нечетком с-разбиении, основанный на построении интервала значений наиболее возможного числа классов с использованием нечетких чисел. Предложена модификация FCM-CV-алгоритма и приводится результат вычислительного эксперимента. Введение Теория нечетких множеств, предложенная в 1965 году Л.А. Заде [1], нашла свое применение практически в любой области научных исследований, в том числе и при разработке новых методов автоматической классификации, именуемой также кластерным анализом, численной таксономией или распознаванием образов с само- обучением [2], в связи с чем Л.А. Заде отмечал, что «глубинная связь между теорией нечетких множеств и распознаванием образов основана на том обстоятельстве, что большинство реальных классов размыты по своей природе в том смысле, что переход от принадлежности к непринадлежности для этих классов скорее постепенен, чем скачкообразен» [3]. В работах [4-6] подробно рассматриваются предложенные различными исследователями методы нечеткой кластеризации эвристического, оптимизационного и иерархического направлений. Оптимизационные методы нечеткого подхода к решению задач кластеризации являются наиболее распространенными, однако при обращении к указанным кластер-процедурам возникает проблема обоснова- ния числа классов, для решения которой традиционно используются различные показатели оптимальности числа нечетких кластеров. Вместе с тем, при большом количестве предположений о числе классов использование этих показателей также затруднительно, и задача состоит в построении множества наиболее возможного числа нечетких кластеров. Целью предпринятого исследования является решение поставленной задачи, в основе которого лежит использование аппарата нечетких чисел. В работе предла- гается метод построения допустимого множества значений наиболее возможного числа нечетких кластеров в искомом нечетком c -разбиении, основанный на построении нечетких величин, исходя из экспертных оценок или результатов разведочного анализа данных, а также рассматривается соответствующая модификация предложенного в [7] FCM-CV-алгоритма. Приводятся результаты вычислительного эксперимента и форму- лируются предварительные выводы об эффективности предложенного подхода. ∗Исследования проводились при поддержке гранта Президиума Национальной академии наук Беларуси в соответствии с Постановлением № 157 Бюро Президиума НАН Беларуси от 11.04.2007. Вятченин Д.А. «Искусственный интеллект» 3’2008 524 7В Оптимизационное направление решения нечеткой модификации задачи кластеризации В нечетких методах автоматической классификации, объединяемых в оптими- зационное направление, нечеткая кластеризация понимается как разбиение классифи- цируемой совокупности объектов },...,{ 1 nxxX = на семейство его нечетких множеств, так что в качестве входного параметра в существующих нечетких методах оптимизационного направления автоматической классификации задается число нечетких кластеров c , причем при данном подходе под нечетким кластером может пониматься любое нечеткое множество, определенное на универсуме. Нечеткие множества clAl ,,1, …= с соответст- вующими функциями принадлежности cii µµ ,,1 … каждого объекта ix , определенные на универсуме },...,{ 1 nxxX = , образуют нечеткое c -разбиение, иногда называемое также нечетким разбиением в смысле Э.Г. Распини [3], если для каждого объекта Xxi ∈ выпол- няется условие 1 1 =∑ = c l liµ , и нечеткая модификация задачи автоматической классифи- кации в экстремальной постановке заключается в нахождении экстремума некоторого функционала )(PQ на множестве Π всех возможных нечетких c -разбиений P клас- сифицируемого множества объектов X , что описывается формулой Π∈ → P extrPQ )( . Если исходные данные представлены матрицей вида «объект-объект» njnixxdd jinn ,,1,,,1)],,([ …… ===× , элементами которой являются попарные коэффи- циенты различия между объектами, то для классификации объектов исследуемой совокупности используются так называемые реляционные процедуры, основанные на минимизации соответствующих функционалов. Примером такого функционала может послужить критерий М. Рубенса [8] ∑∑∑ = = = = c l n i n j jiljli I Ro xxdPQ 1 1 1 22 },()( µµ , (1) процедура минимизации которого именуется в литературе MND2-алгоритмом [8] или FNM-алгоритмом [6]. В выражении (1) символом ),( ji xxd обозначается коэф- фициент различия между объектами ix и jx , nji ,,1, …= исследуемой совокупности X , nXcard =)( , а liµ – значение принадлежности i -го объекта l -му нечеткому кластеру. В случае же представления исходных данных в виде матрицы «объект – свойство» mtnixX t imn ,,1,,,1],€[€ …… ===× , задача классификации заключается в минимизации критерия, в который введена некоторая метрика, и типичным примером подобных функционалов является критерий, предложенный Дж. Данном [9] и позже обобщен- ный Дж. Беждеком [10] ∑∑ = = −=Τ c l n i l ili II DB xPQ 1 1 2 ),( τµ γ , (2) процедура минимизации которого широко известна под обозначением FCM-алгоритма. Критерий (2), где символом lτ обозначен прототип l -го нечеткого кластера, а символом γ – задаваемый исследователем коэффициент нечеткости классификации, такой, что ∞<< γ1 , послужил основой для целого семейства функционалов и соответствующих им нечетких кластер-процедур, которые подробно рассматриваются в [4]. Применение нечетких чисел для обоснования кластеров в методах… «Штучний інтелект» 3’2008 525 7В В силу того, что c является параметром любой оптимизационной кластер-про- цедуры, одной из главных проблем при использовании оптимизационных методов является определение «реального» числа c нечетких кластеров, на которые «рас- слаивается» исследуемая совокупность, или, иными словами, проблема обоснования числа кластеров, встающая наиболее остро, когда исследователю число классов c вообще неизвестно. Для решения этой проблемы были предложены различные пока- затели, характеризующие получаемое при использовании того или иного алгоритма нечеткое c -разбиение },,{ 1* cAAP …= . В частности, для FCM-алгоритма и его модифика- ций различными исследователями был введен ряд показателей, наиболее известными из которых являются − коэффициент разбиения ∑∑ = = = c l n i lipc n PV 1 1 2 ,1)( µ (3) предложенный Дж. Данном [11] и для которого решение задачи определения оптималь- ного числа классов в *P отыскивается в виде ( ) 1,,2,)(max −= ncPV pcc … ; − энтропия разбиения ∑∑ = = ⋅−= c l n i lilipe n PV 1 1 ln1)( µµ , (4) предложенная Дж. Беждеком, М.П. Уиндхемом и Р. Эрлихом [12], так что оптималь- ному числу классов в *P соответствует ( ) 1,,2,)(min −= ncPV pec … ; − индекс разделимости 2 1 1 22 min 1 )( kl kl c l n i l ili si x nPV ττ τµ − − = ≠ = = ∑∑ , (5) предложенный Х.Л. Хи и Ж. Бени [13], где оптимальное число классов в *P опреде- ляется, исходя из условия ( ) 1,,2,)(min −= ncPVsic … . Для других нечетких кластер- процедур оптимизационного направления также предлагается ряд показателей опти- мальности числа классов в нечетком c -разбиении – в частности, в [14] рассматриваются показатели оптимальности нечетких кластеров при разбиении исследуемой совокуп- ности с помощью FNM-алгоритма. Для всех показателей числа классов в нечетком c -разбиении решение задачи определения оптимального числа классов в искомом нечетком разбиении определяется общим выражением ( ) 1,,2,)( −= ncPVextr cc … , (6) где символом )(PVc обозначен какой-либо показатель. Таким образом, необходимым является проведение серии экспериментов при различных значениях числа классов c , для чего оказывается необходимым построение множества },,{ ∗ ∗= ccC … наиболее воз- можных значений числа классов в искомом нечетком c -разбиении ∗P , где ∗c – наимень- шее, а ∗c – наибольшее из значений множества C . В [15] было предложено объединить FCM-алгоритм с процедурой вычисления соответствующего показателя оптимальности числа нечетких классов )(PVc в иско- мом нечетком c -разбиении ∗P в рамках одной процедуры, параметрами которой явля- ются значения наименее возможного *c и наиболее возможного *c числа нечетких кла- Вятченин Д.А. «Искусственный интеллект» 3’2008 526 7В стеров в искомом нечетком c -разбиении ∗P . Вместе с тем, предложенная в [15] про- цедура предъявляет достаточно высокие требования к оперативной памяти ПЭВМ, особенно при обработке совокупностей сравнительно большого объема, и в [7] была предложена модификация предложенной в [15] процедуры, получившая, от англоязычных терминов fuzzy c -means и cluster validity, название FCM-CV-алгоритма. Рассмотренный в предпринятом исследовании метод построения множества наиболее возможного числа нечетких кластеров в искомом нечетком c -разбиении ∗P позволяет модифи- цировать FCM-CV-алгоритм, и соответствующая модификация процедуры будет рассмотрена в процессе дальнейшего изложения. Построение множества значений возможного числа нечетких кластеров на основе нечетких чисел Для дальнейшего рассмотрения представляется необходимым напомнить опре- деления понятий нечеткой величины, нечеткого интервала и нечеткого числа. Если некоторое нечеткое множество V определено на множестве действительных чисел, то есть представляет собой отображение ]1,0[→ℜ , то V именуется нечеткой величиной. Каждое значение ℜ∈ix будет называться модальным значением нормальной нечет- кой величины V , если ix является элементом ядра )(VCore нечеткой величины V , то есть 1)( =iV xµ . В случае, если ( ) 1)( =VCorecard , то V является унимодальной нечет- кой величиной, в случае же, когда ( ) 1)( >VCorecard , нечеткая величина V называется мультимодальной [16]. Пусть L или R – невозрастающая функция ]1,0[→ℜ+ , такая, что 1)0()0( == RL и 0)(,1,1)(,0 ><∀<>∀ iiii xLxxLx ; 0)1( =L либо имеет место ii xxL ∀> ,0)( и 0)( =+∞L . Тогда нечеткое множество V называется нечетким интервалом LR -типа с функцией принадлежности )( iV xµ , определяемой формулой           ≥      − ≤≤ ≤      − = mx b mx R mxm mx a xm L x i i i i i iV , ,1 , )(µ , (7) где m называется нижним модальным значением ,V m – верхним модальным значе- нием, а параметры 0>a и 0>b называются левым и правым коэффициентами нечет- кости соответственно. Таким образом, нечеткий интервал LR -типа может быть пред- ставлен в виде четверки параметров, что записывается в виде LRbammV ),,,(= . Если LRbammV ),,,(= является нечетким интервалом LR -типа, то при условии совпадения нижнего и верхнего модальных значений mmm == нечеткий интервал LR -типа V именуется нечетким числом LR -типа с функцией принадлежности, опре- деляемой в соответствии с выражением        ≥      − ≤      − = mxпри b mx R mxпри a xm L x i i i i iV , , )(µ , (8) Применение нечетких чисел для обоснования кластеров в методах… «Штучний інтелект» 3’2008 527 7В где m называется модальным значением нечеткого числа LR -типа, символически записываемого в виде LRbamV ),,(= , а a и b – левым и правым индексами нечет- кости соответственно. При использовании оптимизационных методов нечеткой кластеризации число классов c в искомом нечетком c -разбиении ∗P может определяться с помощью ре- зультатов разведочного анализа данных, к примеру, при анализе диаграммы рассеивания [2] или экспертных оценок. Пусть },1,€2|))€(,€{(€ € kencccC eeCee e =∀≤≤= µ – множество одноточечных нечетких множеств, выражающих мнения k экспертов о числе c кластеров в искомом нечетком c -разбиении ∗P , так что предполагаемому e -м экспертом числу ec€ нечетких кластеров в ∗P соответствует степень уверенности ]1,0()€(€ ∈eC c e µ . Для каждого ke ,,1…= значение ec€ может рассматриваться как мо- дальное значение нечеткого числа, и для каждого из строящихся нечетких чисел kebamV LReeee ,,1,),,( …== с модальными значениями ee cm €= соответственно значе- ния kel eV ,,1),( …=µ будут полагаться равными нулю в точках 1=c и nc = , так что },,1{,0)()1( ken ee VV …∈∀== µµ , левый коэффициент нечеткости будет определяться выражением ( )1€ −= ee ca , а правый – ( )ee cnb €−= , так что носителем )( eVSupp нечеткого числа keVe ,,1, …= будет открытый интервал ( ) ( )nbcac eeee ,1€,€ =+− , а )(l eVµ будет определяться выражением        ≥      − ≤      − = e e e e e e e e V clпри b cl R clпри a lc L l e €, € €, € )(µ , (9) где индекс e функций L и R подчеркивает, что они могут выбираться для каждого нечеткого числа kebamV LReeee ,,1,),,( …== отдельно. Таким образом, если на коор- динатной плоскости по оси абсцисс откладывать число классов ),1( nl∈ , а по оси ор- динат – значения функции принадлежности )(l eVµ нечеткого числа eV , то функция представления формы нечеткого числа keVe ,,1, …= будет иметь вид кривой, дости- гающей максимума в точке с координатами 1)(,€ == lcl eVe µ . При построении нечетких чисел keVe ,,1, …= для того, чтобы каждое keVe ,,1, …= описывалось бы непрерывной функцией принадлежности )(l eVµ , подразумевается, что ℜ⊂∈ ),1( nl . Далее следует построить нечеткую величину V с непрерывной функцией при- надлежности )(lVµ , для чего ко всем kebamV LReeee ,,1,),,( …== можно применить операцию объединения, причем в данном случае операция объединения понимается в широком смысле, то есть может быть осуществлена с помощью какой-либо выбранной исследователем S -нормы [17]. После построения V выбирается порог )€(min € eCe c e µα = , для которого строится })()(|))(,{( )()()( αµµµ ααα ≥== llllV VVV – нечеткое множество уровня α с непрерывной функцией принадлежности )( )( lV α µ . Носитель не- четкого множества )(αV в таком случае будет представлять собой интервал действи- тельных чисел ( ) ]",'[)( ccVSupp =α , и множество },,{ * ∗= ccC … возможных значений Вятченин Д.А. «Искусственный интеллект» 3’2008 528 7В числа классов в искомом нечетком c -разбиении ∗P может быть определено как под- множество натуральных чисел, определяемое выражением    { }+⊂≤≤ Zcccc |"' , (10) где   ∗= cc' – округление числа 'c до ближайшего сверху целого из интервала ]",'[ cc ,   ∗= cc" – округление числа "c до ближайшего снизу целого из интервала ]",'[ cc , а +Z – множество положительных целых чисел. Для элементов c множества допус- тимых значений числа нечетких кластеров },,{ * ∗= ccC … можно определить значения принадлежности Cccllc VV ∈== ,),()( )(€ α µµ , так что множество C будет представлять собой носитель нечеткого множества CcccV V ∈= )},(,{€ €µ с дискретной функцией принадлежности. Значения функции принадлежности CccV ∈),(€µ могут интерпре- тироваться как степени адекватности значений Cc ∈ , так что обобщенный пока- затель оптимальности числа нечетких классов )(~ PVc может быть определен в виде )()()(~ € cPVPV Vcc µ⋅= , где Cc ∈ – число кластеров в P . Для построения множества одноточечных нечетких множеств keCe ,,1,€ …= можно воспользоваться предложенным в [18] эвристическим D-AFC-TC-алгоритмом нечет- кой кластеризации с выбором различных расстояний между нечеткими множествами. Результатом работы D-AFC-TC-алгоритма является распределение )(* XR объектов исследуемой совокупности X по априори неизвестному числу ncc <≤2, нечетких α -кластеров для некоторого вычисленного порога сходства α , позволяющего коли- чественно оценить наименьшую степень сходства объектов в нечетких α -кластерах распределения )(* XR . Полученное в результате работы D-AFC-TC-алгоритма при некотором выбранном расстоянии число c нечетких α -кластеров в )(* XR может за- даваться как ec€ , а значение порога сходства α полученного распределения )(* XR – как значение )€(€ eC c e µ . Схема модифицированного FCM-CV-алгоритма Построение нечеткого множества CcccV V ∈= )},(,{€ €µ с помощью D-AFC-TC- алгоритма либо его модификаций является этапом, предваряющим построение нечет- кого c -разбиения ∗P , оптимального в смысле выбранного показателя )(PVc . Общая схема предлагаемой модификации FCM-CV-алгоритма, основанной на вычислении )(~ PVc для всех Cc ∈ , и которую можно обозначить как (m)FCM-CV- алгоритм, выглядит следующим образом. 1. Полагается *1 : cc = и *: cc p = и значения числа классов c в искомом ∗P упорядочиваются следующим образом: 12 1 −≤<<<<≤ nccc p…… . 2. Полагается 1:= . 3. Вычислять: 3.1. с помощью FCM -алгоритма вычисляется нечеткое c -разбиение )(cP исследуемой совокупности на c классов; Применение нечетких чисел для обоснования кластеров в методах… «Штучний інтелект» 3’2008 529 7В 3.2. вычисляется значение показателя )()()(~ € cPVPV Vcc µ⋅= для полученного нечеткого c -разбиения )(cP ; 3.3. производится проверка условия: если 2< , то осуществляется переход на шаг 5, иначе осуществляется переход на шаг 4. 4. Производится проверка условия: если *)(~)(~ PVPV cc > , то осуществляется переход на шаг 5, иначе осуществляется переход на шаг 6. 5. Полагается *)( PcP = . 6. Производится проверка условия: если p< , то полагается 1: += и осуществляется переход на шаг 3, иначе нечеткое c -разбиение *P является искомым результатом и алгоритм прекращает работу. Схема (m)FCM-CV-алгоритма построена, исходя из предположения, что в качест- ве )(PVc используется коэффициент разбиения (3), так что в случае, когда в качестве )(PVc используется другой показатель, для которого решение задачи определения оптимального числа классов отыскивается в виде ( ),)(min PVcc 1,,2 −= nc … , на шаге 4 представленной выше схемы следует производить проверку условия *)()( PVPV cc < ; следует также указать, что (m)FCM-CV-алгоритм требует сохранения в оперативной памяти ПЭВМ только двух нечетких разбиений – вычисленного )(cP и текущего *P , вместо множества { }pcPcc ,,1|)(),( …==Π ∗ ∗ возможных решений задачи классифи- кации. При CccV ∈∀= ,1)(€µ , предложенная схема будет являть собой FCM-CV- алгоритм [7]. Иллюстративный пример Для проведения вычислительного эксперимента были выбраны изображенные на рис. 1 двумерные данные, предложенные в качестве тестовых К.Г. Луни [19], представ- ляющие собой совокупность 15 объектов },,{ 151 xxX …= . При проведении вычисли- тельных экспериментов исходные данные были пронормированы в соответствии с выражением t ii t it i x x x €max € = , (11) и обработаны D-AFC-TC-алгоритмом с использованием относительного обобщен- ного расстояния Хемминга, относительного евклидова расстояния и относительной евклидовой нормы [18]. Вятченин Д.А. «Искусственный интеллект» 3’2008 530 7В Рисунок 1 – Данные для проведения вычислительного эксперимента При использовании относительного обобщенного расстояния Хемминга было получено распределение по 2€1 =c при 0.81251 =∗α , а при использовании относитель- ного евклидова расстояния и относительной евклидовой нормы было получено 3€€ 32 == cc при 0.80652 = ∗α и 0.96263 = ∗α соответственно, что дает возможность пост- роить нечеткие числа LRbamV ),,( 1111 = и LRbamV ),,( 2222 = с модальными значениями 3,2 21 == mm и функциями принадлежности        ≤≤            + − − − ≤≤            + − − + = 152, 2 152 215 sin 2 1 2 1 21, 2 21 12 sin 2 1 2 1 )( 1 ll ll lV π π µ , (12) и        ≤≤            + − − − ≤≤            + − − + = 153, 2 153 315 sin 2 1 2 1 31, 2 31 13 sin 2 1 2 1 )( 2 ll ll lV π π µ . (13) Рисунок 2 – Функция принадлежности нечеткой величины V и значения принадлежностей нечеткого множества V€ Применение нечетких чисел для обоснования кластеров в методах… «Штучний інтелект» 3’2008 531 7В Для построения V в качестве S -нормы была выбрана операция объединения нечетких множеств, а значение α было выбрано как 3,2,1,min == ∗ eee αα и составило 0.80652 = ∗α , так что множество C представляет собой совокупность }6,5,4,3,2{=C . На рис. 2 непрерывной кривой изображена функция принадлежности )(lVµ , а симво- лом ○ обозначены значения CccV ∈),(€µ нечеткого множества V€. На рис. 3 изображено поведение для построенного V€ обобщенного индекса разделимости )(~ PVsi при обработке данных (m)FCM-CV-алгоритмом. а) б) в) г) Рисунок 3 – Значения )(~ PVsi (а) и )(~ PVsi при CccV ∈∀= ,1)(€µ (б) при обработке исходных данных (m)FCM-CV-алгоритмом На рис. 4 изображено поведение для построенного V€ показателя )(~ PV pc . В обоих случаях оптимальным числом классов в искомом нечетком c -разбиении является 3=c . Значения принадлежностей объектов совокупности },,{ 151 xxX …= первому нечеткому кластеру оптимального *P изображены на рис. 4 символом ○, второму – символом ∆ и третьему – символом ■. Вятченин Д.А. «Искусственный интеллект» 3’2008 532 7В Рисунок 4 – Значения принадлежностей объектов классам оптимального *P Анализ исходных данных, приведенных на рис. 1, позволяет визуально выде- лить три довольно четкие совокупности точек, и приведенные на рисунке 4 значения принадлежности объектов исследуемой совокупности трем классам нечеткого c -раз- биения, оптимального в смысле критерия (2), соответствуют относительной близости объектов прототипам нечетких кластеров. Кроме того, результаты проведенного эксперимента показывают корректность определенного в результате работы (m)FCM- CV-алгоритма числа нечетких кластеров в искомом *P , оптимальном как в смысле индекса разделимости )(PVsi , так и в смысле коэффициента разбиения )(PV pc . Заключение Результаты проведенного исследования наглядно демонстрируют, что аппарат нечетких чисел является эффективным средством для построения множества значе- ний наиболее возможного числа классов в искомом нечетком c -разбиении, а метод построения нечетких чисел для решения указанной задачи является достаточно простым и вполне объяснимым с содержательной точки зрения. Кроме того, предло- женный подход к построению нечетких чисел на основе задаваемых модальных значений является гибким в том смысле, что функция представления формы нечеткого числа, с одной стороны, а также S -норма для построения нечеткой величины – с другой могут быть выбраны в зависимости от условий задачи. Так как FCM-алгоритм, отыскивающий минимум функционала (2), представ- ляет собой параметрическое семейство по γ при фиксированном числе кластеров c [2], и при увеличении значения γ возрастает неопределенность классификации, что в свою очередь влияет на поведение показателей )(PVc , то при больших значениях γ иногда оказывается невозможным определить локальный экстремум показателя )(PVc . Этим обстоятельством диктуется целесообразность использования обобщенного показателя )(~ PVc в предложенном (m)FCM-CV-алгоритме, анализ данных с помощью которого позволяет в значительной мере снизить требования к оперативной памяти ПЭВМ при Применение нечетких чисел для обоснования кластеров в методах… «Штучний інтелект» 3’2008 533 7В обработке больших массивов данных. В свою очередь, главным достоинством предло- женного двухэтапного подхода к решению задачи нечеткой кластеризации, заключаю- щегося в совместном использовании D-AFC-TC-алгоритма и (m)FCM-CV-алгоритма, является возможность обработки данных в полностью автоматическом режиме. Литература 1. Zadeh L.A. Fuzzy Sets // Information and Control. – 1965. – Vol. 8. – P. 338-353. 2. Прикладная статистика: Классификация и снижение размерности: Справ. изд. / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин; Под ред. С.А. Айвазяна. – М.: Финансы и статистика, 1989. – 607 с. 3. Заде Л.А. Размытые множества и их применение в распознавании образов и кластер-анализе // Классификация и кластер / Под ред. Дж. Вэн Райзина: Пер с англ. / Под ред. Ю.И. Журавлева. – М.: Мир, 1980. – С. 208-247. 4. Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition / F. Höppner, F. Klawonn, R. Kruse, T. Runkler. – Chichester: Wiley Intersciences, 1999. – 289 p. 5. Вятченин Д.А. Нечеткие методы автоматической классификации. – Минск: УП «Технопринт», 2004. – 219 с. 6. Fuzzy Models and Algorithms for Pattern Recognition and Image Processing / J.C. Bezdek, J.M. Keller, R. Krishnapuram, N.R. Pal. – New York: Springer Science, 2005. – 776 p. 7. Вятченин Д.А., Хижняк А.В., Шевяков А.В. Методология построения нечеткого С-разбиения мно- жества объектов на оптимальное число классов // Вестник Военной академии Республики Беларусь. – 2006. – № 4. – С. 16-24. 8. Sun H., Wang S., Jiang Q. FCM-Based Model Selection Algorithms for Determining the Number of Clusters // Pattern Recognition. – 2004. – Vol. 37. – P. 2027-2037. 9. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике: Пер. с фр. В.Б. Тарасова. – М.: Радио и связь, 1990. – 288 с. 10. Нечеткие множества в моделях управления и искусственного интеллекта / А.Н. Аверкин, И.З. Батыршин, А.Ф. Блишун и др. / Под ред. Д.А. Поспелова. – М.: Наука, 1986. – 312 с. 11. Вятченин Д.А. Прямые алгоритмы нечеткой кластеризации, основанные на операции транзитив- ного замыкания и их применение к обнаружению аномальных наблюдений // Искусственный интеллект. – 2007. – № 3. – С. 205-216. 12. Looney C.G. Interactive clustering and merging with a new fuzzy expected value // Pattern Recognition. – 2002. – Vol. 35. – P. 2413-2423. 13. Hathaway R.J., Bezdek J.C., Dawenport J.W. On Relational Data Versions of C-means Algorithms // Pat- tern Recognition Letters. – 1996. – Vol. 17. – P. 607-612. Д.А. Вятченін Використання нечітких чисел задля обґрунтування кластерів у методах нечіткої кластеризації У статті розглядається метод визначення оптимального числа кластерів у нечіткому с-розбитті, заснований на побудові інтервалу значень найбільш можливого числа класів з використанням нечітких чисел. Запропонована модифікація FCM-CV-алгоритму і наводиться результат обчислювального експерименту. D.A. Viattchenin An Application of Fuzzy Numbers for Cluster Validity in Fuzzy Clustering Methods This paper considers a method of detection of the optimal number of clusters in the fuzzy c-partition based on constructing an interval of values of the most possible numbers of classes with using of fuzzy numbers. A modification of the FCM-CV-algorithm is proposed and a result of the numerical experiment is given. Статья поступила в редакцию 30.05.2008.

Схожі ресурси