Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов

Предложен метод кластеризации объектов с варьирующимися в интервале значениями признаков в случаях неустойчивой кластерной структуры множества объектов. Приводятся результаты вычислительного эксперимента....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Вятченин, Д.А., Доморацкий, А.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Schriftenreihe:	Штучний інтелект
Schlagworte:	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/60234
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов / Д.А. Вятченин, А.В. Доморацкий // Штучний інтелект. — 2011. — № 3. — С. 479-489. — Бібліогр.: 25 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-60234
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-602342025-02-09T18:18:47Z Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов Побудова нечіткого с-розбиття у разі нестійкої кластерної структури безлічі об’єктів Constructing Fuzzy C-Partition in Case of Unstable Cluster Structure of Set of Objects Вятченин, Д.А. Доморацкий, А.В. Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Предложен метод кластеризации объектов с варьирующимися в интервале значениями признаков в случаях неустойчивой кластерной структуры множества объектов. Приводятся результаты вычислительного эксперимента. Запропонований метод кластеризації об’єктів із значеннями ознак, що варіюються в інтервалі, у випадках нестійкої кластерної структури безлічі об’єктів. Наводяться результати обчислювального експерименту. A method of clustering of objects for varying in an interval attributes values in a case of the unstable cluster structure of the set of objects is proposed. Results of the numerical experiment are presented. 2011 Article Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов / Д.А. Вятченин, А.В. Доморацкий // Штучний інтелект. — 2011. — № 3. — С. 479-489. — Бібліогр.: 25 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60234 519.237.8+510.22 ru Штучний інтелект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
spellingShingle	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Нейронные сети и нейросетевые технологии. Информационная безопасность ИС Вятченин, Д.А. Доморацкий, А.В. Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов Штучний інтелект
description	Предложен метод кластеризации объектов с варьирующимися в интервале значениями признаков в случаях неустойчивой кластерной структуры множества объектов. Приводятся результаты вычислительного эксперимента.
format	Article
author	Вятченин, Д.А. Доморацкий, А.В.
author_facet	Вятченин, Д.А. Доморацкий, А.В.
author_sort	Вятченин, Д.А.
title	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
title_short	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
title_full	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
title_fullStr	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
title_full_unstemmed	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
title_sort	построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2011
topic_facet	Нейронные сети и нейросетевые технологии. Информационная безопасность ИС
url	https://nasplib.isofts.kiev.ua/handle/123456789/60234
citation_txt	Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов / Д.А. Вятченин, А.В. Доморацкий // Штучний інтелект. — 2011. — № 3. — С. 479-489. — Бібліогр.: 25 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT vâtčeninda postroenienečetkogosrazbieniâvslučaeneustojčivojklasternojstrukturymnožestvaobʺektov AT domorackijav postroenienečetkogosrazbieniâvslučaeneustojčivojklasternojstrukturymnožestvaobʺektov AT vâtčeninda pobudovanečítkogosrozbittâurazínestíjkoíklasternoístrukturibezlíčíobêktív AT domorackijav pobudovanečítkogosrozbittâurazínestíjkoíklasternoístrukturibezlíčíobêktív AT vâtčeninda constructingfuzzycpartitionincaseofunstableclusterstructureofsetofobjects AT domorackijav constructingfuzzycpartitionincaseofunstableclusterstructureofsetofobjects
first_indexed	2025-11-29T14:06:39Z
last_indexed	2025-11-29T14:06:39Z
_version_	1850133929957261312
fulltext	«Штучний інтелект» 3’2011 479 8В УДК 519.237.8+510.22 Д.А. Вятченин, А.В. Доморацкий Объединенный институт проблем информатики НАН Беларуси, г. Минск, Беларусь viattchenin@mail.ru УП «Геоинформационные системы» НАН Беларуси, г. Минск, Беларусь a.damaratski@gmail.com Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов Предложен метод кластеризации объектов с варьирующимися в интервале значениями признаков в случаях неустойчивой кластерной структуры множества объектов. Приводятся результаты вычислительного эксперимента. Введение В задачах автоматической классификации динамических объектов, то есть объектов, признаки которых могут изменять свои значения с течением времени или при наличии внешних воздействий [1], именуемых также задачами динамической кластеризации, признаки 1ˆ tx , 11 ,,1 mt  объектов Xxi  могут принимать значения в непрерывном интервале безотносительно к моменту измерения соответствующей характеристики объекта, так что каждый признак 1ˆ tx , 11 ,,1 mt  для объекта ix , ni ,,1  представляет собой интервал значений ]ˆ,ˆ[ (max)(min) 11 t i t i xx . Кластерная структура исследуемой совокуп- ности, состоящей из подобных объектов, также является динамической, и зависит от значений признаков в момент классификации. На содержательном уровне задача по- строения устойчивой кластерной структуры в [1] формулируется следующим образом: найти такое априори неизвестное число c областей признакового пространства m , в которых отображаются кластеры при различных значениях принимаемых объектами исследуемой совокупности X признаков 1ˆ tx , 11 ,,1 mt  , варьирующихся в интервале ]ˆ,ˆ[ (max)(min) 11 t i t i xx . В свою очередь, перед решением указанной задачи в первую очередь необходимо установить тип динамических изменений кластерной структуры, для чего в [1] определены понятия устойчивой, квазиустойчивой и неустойчивой кластерной стру- ктуры. Если при изменении в соответствующем интервале ]ˆ,ˆ[ (max)(min) 11 t i t i xx значений приз- наков 1ˆ tx , 11 ,,1 mt  объектов Xxi  исследуемой совокупности число c кластеров },...,{ 1 cAA не изменяется и не изменяются координаты их прототипов },,{ 1 c  , то структура, образуемая кластерами },,...,{ 1 cAA называется устойчивой; если с измене- нием значений признаков объектов число c кластеров },...,{ 1 cAA не изменяется, но изменяются координаты их прототипов },,{ 1 c  , то соответствующая кластерная структура именуется квазиустойчивой, а если при изменении значений признаков Вятченин Д.А., Доморацкий А.В. «Искусственный интеллект» 3’2011 480 8В наблюдаемых объектов Xxi  изменяется число c кластеров, то кластерная струк- тура является неустойчивой. В [1] представлен метод определения типа кластерной структуры совокупности объектов с варьирующимися в интервале значениями приз- наков, в основе которого лежит D-AFC-TC-алгоритм [2] построения распределения объектов по априори неизвестному числу нечетких  -кластеров. В случае, когда кластерная структура, образуемая объектами исследуемой сово- купности, является неустойчивой, ей соответствуют такие типы динамических измене- ний, как образование новых кластеров, слияние кластеров, расщепление кластеров и элиминация кластеров, а в случае квазиустойчивости кластерной структуры число кластеров не изменяется, однако имеет место дрейф прототипов кластеров, и, как про- демонстрировано в [1], изменяются типичные точки кластеров. В отличие от ситуации неустойчивой кластерной структуры, где ее изменения носят скачкообразный характер, в ситуации квазиустойчивой кластерной структуры изменения носят непрерывный и, как следствие, латентный характер. Метод построения распределения объектов по классам в случае квазиустойчивости кластерной структуры представлен в работе [3]. Целью предпринятого исследования является решение задачи построения нечет- кого с -разбиения множества объектов, описываемых динамическими признаками, в случае, когда кластерная структура является неустойчивой. Основой предлагаемого ме- тода является реляционный подход к решению задачи нечеткой кластеризации в со- четании с представлением объектов исследуемой совокупности как интервально-значных нечетких множеств и последующим построением матрицы коэффициентов различия на соответствующем универсуме. Реляционные методы оптимизационного подхода к решению задачи нечеткой кластеризации При решении задач динамической кластеризации могут использоваться подходы, основанные на методах нечеткой и возможностной кластеризации [2], в которых резуль- татом классификации является не только отнесение i -го объекта исследуемой совокуп- ности },,{ 1 nxxX  к l -му классу ,lA cl ,,1  но и указание функции принадлеж- ности ]1,0[li , cl ,,1  , ni ,,1  с которой объект Xxi  , ni ,,1 принадлежит тому или иному нечеткому кластеру clAl ,,1,  . В нечетких методах автоматической классификации оптимизационного направле- ния [4] нечеткая кластеризация понимается как разбиение классифицируемой совокуп- ности объектов },...,{ 1 nxxX  на семейство его нечетких множеств, так что в качестве входного параметра в существующих оптимизационных нечетких методах нечеткой кла- стеризации, как правило, задается число нечетких кластеров c , причем при данном подходе под нечетким кластером может пониматься любое нечеткое множество, опре- деленное на универсуме. Нечеткие множества ,lA cl ,,1 с соответствующими функ- циями принадлежности cii  ,,1  образуют нечеткое c -разбиение, если для каждого объекта Xxi  выполняется условие 1 1   c l li , и нечеткая модификация задачи кластери- зации в экстремальной постановке заключается в нахождении экстремума некоторого функционала )(PQ на множестве  всех возможных нечетких c -разбиений P клас- сифицируемого множества объектов X , что описывается формулой   P extrPQ )( . Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры… «Штучний інтелект» 3’2011 481 8В Если исходные данные представлены матрицей вида «объект – свойство» ]ˆ[ˆ 1 1 t imn xX  , ni ,,1  , 11 ,,1 mt  задача классификации заключается в минимизации критерия, в который введена некоторая метрика, и типичным примером подобных функционалов является критерий, предложенный Дж. Данном [5] и позже обобщен- ный Дж. Беждеком [6]     c l n i l iliFCM xPQ 1 1 2 ),(   , (1) процедура минимизации которого широко известна под обозначением FCM-алгоритма. Критерий (1), где символом l обозначен прототип l -го нечеткого кластера, а сим- волом  – задаваемый исследователем коэффициент нечеткости классификации, такой, что  1 , послужил основой для целого семейства функционалов и соответствую- щих им нечетких кластер-процедур, которые подробно рассматриваются в [4]. В случае представления данных в виде матрицы «объект – объект» )],([ jinn xxdd  , nji ,,1,  , элементами которой являются попарные коэффициенты различия, то для классификации объектов исследуемой совокупности используются так называемые ре- ляционные процедуры, основанные на минимизации соответствующих функционалов, которые будут рассмотрены подробнее. Одним из первых примеров такого рода функционалов может послужить критерий М. Рубенса [7]      c l n i n j jiljliFNM xxdPQ 1 1 1 22 ),()(  , (2) процедура минимизации которого именуется в литературе FNM-алгоритмом. В выра- жении (2) символом ),( ji xxd обозначается коэффициент различия между объектами ix и jx , nji ,,1,  исследуемой совокупности nXcardX )(, , а li – значение принадлеж- ности i -го объекта l -му нечеткому кластеру. В работе [8] Р.Дж. Гэтвэем, Дж. Беждеком и Дж.В. Дэвенпортом предложен реляционный аналог критерия (1), процедура минимизации которого получила обоз- начение RFCM-алгоритма. Метод основан на минимизации критерия вида                   c l n k lk n j n i jiljliRFCM xxdPQ 1 11 1 2),()(   , (3) с учетом того, что для всех nji ,,1,  имеет место выполнение условия евклидовой согласованности 2 ),( jiji xxxxd  , (4) то есть матрица попарных расстояний )],([ jinn xxdd  , nji ,,1,  описывает геометри- ческую структуру исследуемой совокупности в некотором 1m -мерном евклидовом про- странстве 1m . Необходимо указать, что в работе [9] предложена модификация RFCM- алгоритма, не требующая выполнения условия (4), в силу чего получившая обозначение NERFCM-алгоритма. В работе [10] М.П. Уиндхемом был предложен AP-алгоритм, минимизирующий критерий      c l n i n j jiljliAP xxdPQ 1 1 1 22 ),()(  , (5) при ограничениях на значения весов прототипов    n j lj 1 1 , cl ,,1  , nj ,,1  , (6) Вятченин Д.А., Доморацкий А.В. «Искусственный интеллект» 3’2011 482 8В представляющий собой «наиболее сильное обобщение среди всех оптимизационных методов решения нечеткой модификации задачи кластерного анализа, и с содержа- тельной точки зрения, минимизация (5) отыскивает оптимальное отклонение нечет- ких принадлежностей объектов от нечетких центров кластеров» [11]. Таким образом, нечеткой является не только степень принадлежности объекта класссу, но и сам представитель класса – каждый элемент классифицируемого множества },...,{ 1 nxxX  в различной степени может быть, с одной стороны, прототипом того или иного класса, а с другой – просто элементом этого и всех остальных классов. Результатом работы алгоритма, доставляющего минимум функционалу (5), являются матрица раз- биения ][ lincP  , где nicl ,,1,,,1   , и матрица весов прототипов ][ lincK  , где также cl ,,1  , ni ,,1  , и совместный анализ которых позволяет детально исследовать структуру множества объектов X . В свою очередь, является ARCA-алгоритм, предложенный в [12], состоит в на- хождении экстремума функционала                c l n i n j l jjiliARCA xdxxdPQ 1 1 2 1 2 ),(),(),(   , (7) где для показателя нечеткости классификации  , как и в критерии (1), выполняется условие  1 , ),( ji xxd – коэффициент различия объектов ix и jx , а значение ),( l jxd  выражает различие между объектом jx и прототипом l нечеткого кластера clAl ,,1,  , для некоторого объекта Xxi  . Результатом работы кластер-процедуры будет матрица ][ lincP  нечеткого c -разбиения P , а также матрица ][ linc dD  , ),( l ili xdd  расстояний объектов nixi ,,1,  от прототипов l , cl ,,1 , смысл кото- рых во многом схож со смыслом вспомогательной функции принадлежности lj в критерии (5), однако, в отличие от AP-алгоритма, в предложенном в [12] методе на значения lid , cl ,,1 , ni ,,1 не налагается условия 1 1   n i lid ; кроме того, на значения ),( ji xxd в матрице исходных данных не налагается никаких ограничений. В силу того, что c является параметром любой оптимизационной кластер-проце- дуры, одной из главных проблем при использовании оптимизационных методов является проблема обоснования числа c нечетких кластеров, встающая наиболее остро, когда ис- следователю число классов c вообще неизвестно, для решения которой были предло- жены различные показатели, характеризующие получаемое при использовании того или иного алгоритма нечеткое c -разбиение },,{ 1 cAAP  . В частности, для FCM-алгорит- ма и его модификаций различными исследователями был введен ряд показателей, наи- более известными из которых являются: – коэффициент разбиения     c l n i lipc n PV 1 1 21 )(  , (8) предложенный Дж. Данном [13] и для которого решение задачи определения опти- мального числа классов в P отыскивается в виде   1,,2,)(max  ncPV pc c  ; – энтропия разбиения     c l n i lilipe n PV 1 1 ln 1 )(  , (9) Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры… «Штучний інтелект» 3’2011 483 8В предложенная Дж. Беждеком, М.П. Уиндхемом и Р. Эрлихом [14], так что оптимальному числу классов в P соответствует   1,,2,)(min  ncPV pe c  ; – индекс разделимости 2 1 1 22 min 1 )( kl kl c l n i l ili si x n PV          , (10) предложенный Х.Л. Хи и Ж. Бени [15], где оптимальное число классов в P опреде- ляется, исходя из условия   1,,2,)(min  ncPVsi c  . Как указывается в [16], для реля- ционных кластер-процедур приемлемыми оказываются непрямые индексы, такие, как (8) или (9); с другой стороны, в работе [12] отмечается, что, в силу возможности гене- рирования прототипов, показатель (10) также применим для использования с ARCA- алгоритмом. Таким образом, применимость реляционных методов нечеткой кластеризации к классификации данных, описываемых матрицей вида «объект – свойство», обусловли- вается выбором метрики для получения матрицы вида «объект – объект». Следовательно, возникает вопрос о построении матрицы попарных коэффициентов различия для объектов, признаки которых описываются интервалами значений. Методы обработки интервально-значных данных При обработке интервально-значных данных представляется целесообразным при- бегнуть к аппарату так называемых интервально-значных нечетких множеств, являющих- ся частным случаем нечетких множеств типа 2, которые также используются в задачах динамической кластеризации [17]. Пусть },...,{ 1 nxxX  – множество объектов, так что каждый объект ix описывается 1m числом признаков и может быть представлен в виде вектора ),,,,( 111 m i t iii xxxx  , а каждый признак, в свою очередь 1ˆ tx , 11 ,,1 mt  описывается 2m значениями, так что )ˆ,,ˆ,,ˆ(ˆ )()()1( 212111 mt i tt i t i t i xxxx  . Таким образом, тринаправленные данные могут быть представлены в виде полиматрицы ]ˆ[ˆ )( 21 21 tt immn xX  , ni ,,1  , 11 ,,1 mt  , 22 ,,1 mt  , которая может быть обработана с помощью обобщенной нормализации )( , )( )( 21 2 21 21 ˆmax ˆ tt i ti tt itt i x x x  , (11) или обобщенной унитаризации )( , )( , )( , )( )( 21 2 21 2 21 2 21 21 ˆminˆmax ˆminˆ tt i ti tt i ti tt i ti tt i tt i xx xx x    , (12) так что каждый объект ix , ni ,,1 множества },,{ 1 nxxX  может рассматриваться как нечеткое множество типа 2 с функциями принадлежности )( )()( 2121 tt x tt i xx i  , ni ,,1 ; 11 ,,1 mt  , 22 ,,1 mt  , ]1,0[)( 2 1 21 )(  t t tt xx  , 11 ,,1 mt  , 22 ,,1 mt  . В слу- чае тринаправленных данных каждый объект ix , ni ,,1 описывается ][ )( )( 21 21 tt immi xX  , 11 ,,1 mt  , 22 ,,1 mt  . Вятченин Д.А., Доморацкий А.В. «Искусственный интеллект» 3’2011 484 8В В ситуации интервальной неопределенности исследователь обладает информацией, что действительное значение 1ˆ t ix некоторого признака 1ˆ tx , },,1{ 11 mt  для объекта ix , },,1{ ni  принадлежит некоторому интервалу и, если max}{min,2 t , то ]ˆ,ˆ[ˆ (max)(min) 111 t i t i t i xxx  . Таким образом, интервально-значные данные представляют собой частный случай три- направленных данных, когда 22 m , что описывается выражением )ˆ,ˆ(ˆ (max)(min) 111 t i t i t i xxx  . Очевидно, что в случае )()()1( 21211 ˆˆˆ mtttt xxx   для всех 11 ,,1 mt  , ni ,,1 , исходные данные представляются обычной матрицей «объект – свойство», ]ˆ[ˆ 1 1 t imn xX  . Для интервально-значных нечетких множеств Х. Юу и Х. Юаном в [18] был определен ряд мер близости, одна из которых определяется выражением           1 1 1111 1 (max)(min)(max)(min) 1 2 )()( 2 )()(1 1),( m t t x t x t x t x jiI xxxx m xxs jjii (13) для всех значений  1 , так что применение к полученной матрице коэффициен- тов сходства )],([ jiInn xxsS  , nji ,,1,  операции дополнения ),(1),( jiIjiI xxsxx  , ji xx , , nji ,,1,  , (14) дает в результате матрицу нечеткого отношения несходства )],([ jiInn xxI  . Кроме того, П. Гжегожевским в [19] было предложено следующее расстояние между интервально-значными нечеткими множествами, основанное на метрике Хаусдорфа:        1 1 1111 1 2(max)(max)2(min)(min) 1 )()(,)()(max 1 ),( m t t x t x t x t xjiI xxxx m xxe jiji  . (15) В свою очередь, учитывая, что интервально-значные нечеткие множества пред- ставляют собой частный случай нечетких множеств типа 2, где, как указывалось выше, max}{min,2 t , то для построения матрицы исходных данных оказывается возможным применение к нормализованным интервально-значным данным обобщений расстояний для нечетких множеств типа 2, предложенным в [17]. В частности, обобщение квадрата относительного евклидова расстояния для случая интервально-значных нечетких мно- жеств примет вид                 1 1 2 2121 1 max} {min, 2)()( 2 1 )()( 2 11 ),( m t t tt x tt xjiI xx m xx ji  , (16) применение которого к ix , ni ,,1 также позволяет построить матрицу нечеткого от- ношения несходства )],([ jiInn xxI  . Необходимо указать, что построенное с помощью формулы (16) нечеткое отношение, в общем, не является отношением несходства, так как сохраняет только свойство симметричности, но не является транзитивным и не удовлет- воряет условию даже слабой антирефлексивности, так что обобщение квадрата отно- сительного евклидова расстояния (16) представляет собой не расстояние, а меру различия. Метод построения оптимального нечеткого с-разбиения Задача построения нечеткого c -разбиения P на множестве },...,{ 1 nxxX  дина- мических объектов заключается, таким образом, в построении функции распределения возможностей числа классов в искомом нечетком c -разбиении и построении матрицы коэффициентов различия с последующей обработкой некоторой реляционной кластер- Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры… «Штучний інтелект» 3’2011 485 8В процедурой, с одновременным вычислением некоторого показателя валидности, при раз- личных значениях числа классов ̂ˆ Dсg  , для чего оказывается необходимым построение множества )( )ˆ(ˆ  DSuppD  наиболее возможных значений числа классов в искомом не- четком c -разбиении P . Метод построения функции распределения возможностей )ˆ( gс числа классов в искомой кластерной структуре, описанный в [20] и являющийся обоб- щением предложенного в [21] метода, заключается в построении нечеткого множества ))ˆ((S )2ˆ( 2 ˆˆ gVt cD t , представляющего собой нечеткое объединение нечетких множеств )}ˆ(,ˆ{ˆ )2ˆ( 2 ˆ )ˆ( gVg t ccV t , max}{min,2 t , построенных на основе результатов обработки матриц нормированных данных «объект – свойство» ][ (min)1 1 t imn xX  , ][ (max)1 1 t imn xX  с помощью D-AFC-TC-алгоритма, с последующим построением нечеткого множества уровня  ))ˆ()ˆ(,( )ˆ()ˆ( gDgDg ccDcD    , где )ˆ( ˆ 2 2 minˆ t t   , max}{min,2 t и }ˆ)ˆ(\|ˆˆ{ˆ   gDg cCcD , так что )( )ˆ(ˆ  DSuppD  и )ˆ()ˆ( )ˆ( ggD сc    . Следует указать, что под нечетким объе- динением подразумевается некоторая S -норма, представляющая собой двухместную действительную функцию ]1,0[]1,0[]1,0[:S  , удовлетворяющую условиям ограничен- ности, монотонности, коммутативности и ассоциативности. Если U – некоторый универ- сум, на котором определены нечеткие множества A и B , то наиболее распространен- ными S -нормами являются следующие [22]: – операция максимума: ))(),(max())(),((S1 uuuu BABA   , (17) – алгебраическая сумма: )()()()())(),((S2 uuuuuu BABABA   , (18) – ограниченная сумма: ))()(,1min())(),((S3 uuuu BABA   , (19) так что функция распределения возможностей, в конечном итоге, зависит от выбранного в качестве параметра D-AFC-TC-алгоритма расстояния между нечеткими множествами и выбранной S -нормы [20]. Таким образом, метод построения нечеткого c -разбиения мно- жества },...,{ 1 nxxX  , где значения признаков классифицируемых объектов описываются интервалами, может быть представлен в виде следующей последовательности шагов: 1. Производится нормировка исходных данных, представленных в виде матри- цы интервально-значных данных ]ˆ,ˆ[ˆ (max)(min) 11 1 t i t imn xxX  , ni ,,1  , 11 ,,1 mt  , и полу- ченная матрица нормированных данных разделяется на две матрицы, ][ (min)1 1 t imn xX  и ][ (max)1 1 t imn xX  , каждая из которых обрабатывается D-AFC-TC-алгоритмом. 2. В соответствии с выбранной S -нормой строится функция распределения возможностей числа классов в искомом P и выделяется множество )( )ˆ(ˆ  DSuppD  наиболее возможных значений числа нечетких кластеров. 3. Путем применения к матрице нормализованных интервально-значных данных ],[ (max)(min) 11 1 t i t imn xxX  выбранной метрики строится матрица нечеткого отношения не- сходства )],([ jiInn xxI  , после чего производится ее обработка выбранного реля- ционного алгоритма нечеткой кластеризации и показателя валидности при всех зна- чениях числа классов ̂ˆ Dсg  . Вятченин Д.А., Доморацкий А.В. «Искусственный интеллект» 3’2011 486 8В Изложенный метод построения нечеткого c -разбиения представляет собой част- ный случай метода построения устойчивой кластерной структуры, предложенного в Ра- боте [23]. Иллюстративный пример Для иллюстрации предложенного метода были выбраны интервально-значные дан- ные по восьми типам жиров – шести растительным и двум животным, рассмотренные М. Итино и Х. Ягути в [24], так что исследуемая совокупность должна расслаиваться на два класса. При проведении вычислительного эксперимента были выбраны данные по трем признакам [25], представленные в табл. 1, наиболее часто используемые в сравнительных исследованиях. Таблица 1 – Интервально-значные данные М. Итино и Х. Ягути Виды масел Удельный вес Содержание йода Значение омыления Льняное масло 0,930 – 0,935 170 – 204 118 – 196 Перилловое масло 0,930 – 0,935 192 – 208 188 – 197 Хлопковое масло 0,916 – 0,918 99 – 113 189 – 198 Кунжутное масло 0,920 – 0,926 104 – 116 187 – 193 Камелиевое масло 0,916 – 0,917 80 – 82 189 – 193 Оливковое масло 0,914 – 0,919 79 – 90 187 – 196 Говяжий жир 0,860 – 0,870 40 – 48 190 – 199 Свиной жир 0,858 – 0,864 53 – 77 190 – 202 Для применения предложенного метода была выбрана нормировка (12), а в ка- честве параметра D-AFC-TC-алгоритма – квадрат относительного евклидова расстояния. На рис. 1 а) – в) изображены функции распределения возможностей )ˆ( gс числа клас- сов в P , построенные для S -норм (17) – (19) соответственно. а) б) в) Рисунок 1 – Функции распределения возможностей числа классов Вычислительный эксперимент проводился с использованием ARCA-алгоритма, а в качестве показателя валидности – коэффициента разбиения (8), значения которого на множестве }4,,2{ˆ ˆ  Dсg для всех рассмотренных мер различия (13) – (16) изобра- жены на рис. 2 а) – в) соответственно. а) б) в) Рисунок 2 – Значения коэффициента разбиения при различных мерах несходства Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры… «Штучний інтелект» 3’2011 487 8В Результаты кластеризации в виде матрицы нечеткого c -разбиения и матрицы рас- стояний от объектов до прототипов кластеров, полученные при использовании обобще- ния квадрата относительного евклидова расстояния (16) для построения матрицы попарных коэффициентов различия, представлены в табл. 2. Таблица 2 – Результаты кластеризации данных М. Итино и Х. Ягути Виды масел Значения принадлежности Расстояния до прототипов Класс 1 Класс 2 Класс 3 Класс 1 Класс 2 Класс 3 Льняное масло 0,9542 0,0301 0,0157 0,1454 0,2462 0,6282 Перилловое масло 0,9270 0,0558 0,0172 0,0736 0,1466 0,5286 Хлопковое масло 0,0021 0,9962 0,0017 0,1778 0,0069 0,2017 Кунжутное масло 0,0207 0,9668 0,0125 0,1553 0,0091 0,2461 Камелиевое масло 0,0073 0,9845 0,0082 0,2321 0,0066 0,1751 Оливковое масло 0,0049 0,9896 0,0055 0,2251 0,0070 0,1786 Говяжий жир 0,0006 0,0013 0,9981 0,5965 0,1971 0,0090 Свиной жир 0,0006 0,0013 0,9981 0,5633 0,2035 0,0104 Результаты кластеризации, полученные с помощью расстояний (13) – (15) аналогич- ны приведенным в табл. 2. Таким образом, исследуемая совокупность разбивается на 3 класса – класс растительных жиров расслаивается на 2 субкластера, что соответствует приведенному в [24] результату иерархической классификации исследуемой совокупности. Следует также отметить, что выбор в качестве кластер-процедуры ARCA-алгоритма, минимизирующего критерий (7), обусловлен его возможностью обрабатывать матрицы коэффициентов различия, не удовлетворяющие условию антирефлексивности, что позво- ляет использовать для предобработки данных меру различия (16), а получаемый результат в виде матриц нечеткого c -разбиения ][ lincP  и расстояний от объектов до прототипов нечетких кластеров ][ linc dD  позволяет углубить анализ. С другой стороны, следует отметить, что применение аналогичного метода с ис- пользованием в качестве кластер-процедуры возможностного D-AFC(c)-алгоритма с со- ответствующим показателем валидности [23] строит распределение по 2 нечетким клас- терам для каждой из рассмотренных мер (13), (15) и (16), однако удовлетворительный результат был получен только для меры близости (13). Заключение Результаты вычислительного эксперимента наглядно демонстрируют высокую эф- фективность предложенного метода построения нечеткого c -разбиения для оптималь- ного, в смысле выбираемого показателя валидности, числа классов. Метод является гибким и эффективным с точки зрения возможности выбора кластер-процедуры, пока- зателя валидности и меры различия между объектами; кроме того, помимо точности результатов классификации, достоинством предложенного метода является возмож- ность обработки интервально-значных данных в полностью автоматическом режиме. Литература 1. Вятченин Д.А. Анализ устойчивости кластерной структуры в задачах нестационарной кластеризации / Д.А. Вятченин // Доклады БГУИР. – 2009. – № 6. – С. 91-98. 2. Вятченин Д.А. Прямые алгоритмы нечеткой кластеризации, основанные на операции транзитивного замыкания и их применение к обнаружению аномальных наблюдений / Д.А. Вятченин // Искусственный интеллект. – 2007. – № 3. – С. 205-216. 3. Вятченин Д.А. Построение распределения по нечетким кластерам в случае квазиустойчивой кла- стерной структуры множества объектов / Д.А. Вятченин, А.В. Доморацкий // Доклады БГУИР. – 2010. – № 1. – С. 46-52. Вятченин Д.А., Доморацкий А.В. «Искусственный интеллект» 3’2011 488 8В 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. Dunn J.C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters / J.C. Dunn // Journal of Cybernetics. – 1974. – Vol. 3. – P. 32-57. 6. Bezdek J.C. A convergence theorem for the fuzzy ISODATA clustering algorithms / J.C. Bezdek // IEEE Transactions on Pattern Analysis and Machines Intelligence. – 1980. – Vol. 2. – P. 1-8. 7. Roubens M. Pattern classification problems and fuzzy sets / M. Roubens // Fuzzy Sets and Systems. – 1978. – Vol. 1. – P. 239-253. 8. Hathaway R.J. On relational data versions of C-means algorithms / R.J. Hathaway, J.C. Bezdek, J.W. Dawenport // Pattern Recognition Letters. – 1996. – Vol. 17. – P. 607-612. 9. Hathaway R.J., Bezdek J.C. NERF C-means: non-Euclidean relational fuzzy clustering // Pattern Recognition. – 1994. – Vol. 27. – P. 429-437. 10. Windham M.P. Numerical classification of proximity data with assignment measures / M.P. Windham // Journal of Classification. – 1985. – Vol. 2. – P. 157-172. 11. Вятченин Д.А. Нечеткие методы автоматической классификации / Вятченин Д.А. – Минск : УП Технопринт, 2004. – 219 с. 12. Corsini P. A new fuzzy relational clustering algorithm based on fuzzy C-means algorithm / P. Corsini, B. Laz- zerini, F. Marcelloni // Soft Computing. – 2005. – Vol. 9. – P. 439-447. 13. Dunn J.C. Well-separated clusters and the optimal fuzzy partitions / J.C. Dunn // Journal of Cybernetics. – 1974. – Vol. 4. – P. 95-104. 14. Bezdek J.C. Statistical parameters of cluster validity functionals / J.C. Bezdek, M.P. Windham, R. Ehrlich // International Journal of Computer Information Sciences. – 1980. – Vol. 9. – P. 323-336. 15. Xie X.L. A validity measure for fuzzy clustering / X.L. Xie, G. Beni // IEEE Transactions on Pattern Analysis and Machines Intelligence. – 1991. – Vol. 13. – P. 841-847. 16. 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. 17. Viattchenin D.A. An outline for a heuristic approach to possibilistic clustering of the three-way data / D.A. Viattchenin // Journal of Uncertain Systems. – 2009. – Vol. 3. – P. 64-80. 18. Ju H. Similarity measures on interval-valued fuzzy sets and application to pattern recognition / H. Ju, X. Yan // Fuzzy Information and Engineering / Ed. by D.Y. Cao. – Berlin : Springer-Verlag, 2007. – P. 875-883. 19. Grzegorzewski P. Distances between intuitionistic fuzzy sets and/or on interval-valued fuzzy sets based on Hausdorff metric / P. Grzegorzewski // Fuzzy Sets and Systems. – 2004. – Vol. 148. – P. 319-328. 20. Viattchenin D.A. An approach to constructing a possibility distribution for the number of fuzzy clusters / D.A. Viattchenin // Pattern Recognition and Information Processing: Proceedings of the 11th International Conference PRIP’2011(Minsk, Belarus, May 18 – 20, 2011) / Ed. by R. Sadykhov [et. al.] – Minsk : BSUIR, 2011. – P. 188-194. 21. Вятченин Д.А. Применение нечетких чисел для обоснования кластеров в методах нечеткой класте- ризации / Д.А. Вятченин // Искусственный интеллект. – 2008. – № 3. – С. 523-533. 22. Нечеткие множества в моделях управления и искусственного интеллекта / А.Н. Аверкин, И.З. Батыршин, А.Ф. Блишун [и др.]; под ред. Д.А. Поспелова. – М. : Наука, 1986. – 312 с. 23. Viattchenin D.A. Constructing stable clustering structure for uncertain data set / D.A. Viattchenin // Acta Electrotechnica et Informatica. – 2011. – Vol. 11, № 3. (to appear) 24. Ichino M., Yaguchi H. Generalized Minkowski metrics for mixed feature-type data analysis / M. Ichino, H. Yaguchi // IEEE Transactions on Systems, Man, and Cybernetics. – 1994. – Vol. 25. – P. 698-708. 25. Sato-Ilic M. Innovations in Fuzzy Clustering: Theory and Applications / M. Sato-Ilic, L.C. Jain. – Heidelberg : Springer-Verlag, 2006. – 152 p. Literatura 1. Vjatchenin D.A. Doklady BGUIR. №6. 2009. S. 91-98. 2. Vjatchenin D.A Iskusstvennyj intellekt. № 3. 2007. S. 205-216. 3. Vjatchenin D.A. Doklady BGUIR. №1 2010. S. 46-52. 4. Höppner F. Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition. Chichester: Wiley Intersciences. 1999. 289 p. 5. Dunn J.C. Journal of Cybernetics. Vol. 3. 1974. P. 32-57. 6. Bezdek J.C. IEEE Transactions on Pattern Analysis and Machines Intelligence. Vol. 2. 1980. P. 1-8. Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры… «Штучний інтелект» 3’2011 489 8В 7. Roubens M. Fuzzy Sets and Systems. Vol. 1. 1978. P. 239-253. 8. Hathaway R.J. Pattern Recognition Letters. Vol.17. 1996. P. 607-612. 9. Hathaway R.J. Pattern Recognition. Vol. 27. 1994. P. 429-437 10. Windham M.P. Journal of Classification. Vol 2. 1985. P. 157-172. 11. Vjatchenin D.A. Nechetkie metody avtomaticheskoj klassifikacii. Minsk.: UP Tehnoprint. 2004. 219 s. 12. Corsini P. Soft Computing. Vol 9. 2005. P. 439-447 13. Dunn J.C. Journal of Cybernetics. Vol 4. 1974. P. 95-104. 14. Bezdek J.C. International Journal of Computer Information Sciences. Vol. 9. 1980. P. 323-336. 15. Xie X.L. Transactions on Pattern Analysis and Machines Intelligence. Vol. 13. 1991. P. 841-847. 16. Bezdek J.C. Fuzzy Models and Algorithms for Pattern Recognition and Image Processing. New York: Springer Science. 2005. 776 p. 17. Viattchenin D.A. Journal of Uncertain Systems. Vol. 3. 2009. P. 64-80. 18. Ju H. Fuzzy Information and Engineering. Berlin: Springer-Verlag. 2007. P. 875-883. 19. Grzegorzewski P. Fuzzy Sets and Systems. Vol 148. 2004. P. 319-328. 20. Viattchenin D.A. Pattern Recognition and Information Processing: Proceedings of the 11th International Conference PRIP’2011(Minsk, Belarus, May 18-20, 2011). Minsk: BSUIR. 2011. P. 188-194. 21. Vjatchenin D.A. Iskusstvennyj intellekt. № 3. 2008. S. 523-533. 22. Averkin A.N. Nechetkie mnozhestva v modeljah upravlenija i iskusstvennogo intellekta. M.: Nauka. 1986. 312 s. 23. Viattchenin D.A. Acta Electrotechnica et Informatica. Vol. 11. №.3. 2011 (to appear) 24. Ichino M. IEEE Transactions on Systems, Man, and Cybernetics. Vol 25.1994. P. 698-708. 25. Sato-Ilic M. Innovations in Fuzzy Clustering: Theory and Applications. Heidelberg: Springer-Verlag. 2006. 152 p. Д.А. Вятченін, А.В. Доморацький Побудова нечіткого с-розбиття у разі нестійкої кластерної структури безлічі об’єктів Запропонований метод кластеризації об’єктів із значеннями ознак, що варіюються в інтервалі, у випадках нестійкої кластерної структури безлічі об’єктів. Наводяться результати обчислювального експерименту. D.A. Viattchenin, A.V. Damaratski Constructing Fuzzy C-Partition in Case of Unstable Cluster Structure of Set of Objects A method of clustering of objects for varying in an interval attributes values in a case of the unstable cluster structure of the set of objects is proposed. Results of the numerical experiment are presented. Статья поступила в редакцию 22.06.2011.

Построение нечеткого с-разбиения в случае неустойчивой кластерной структуры множества объектов

Institution

Ähnliche Einträge