Методология анализа данных, основанная на многоэтапной нечеткой кластеризации

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
1. Verfasser:	Вятченин, Д.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Интеллектуальный анализ данных
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/8028
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:	Методология анализа данных, основанная на многоэтапной нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2009. — № 3. — С. 33-46. — Бібліогр.: 22 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-8028
record_format	dspace
spelling	irk-123456789-80282010-04-27T12:00:52Z Методология анализа данных, основанная на многоэтапной нечеткой кластеризации Вятченин, Д.А. Интеллектуальный анализ данных В статье предлагается методология многоэтапного применения нечетких методов автоматической классификации в задачах интеллектуального анализа и обработки многомерных данных. Приводится результат вычислительного эксперимента при анализе искусственного набора данных и сформулированы предварительные выводы. A methodology of automatic classification fuzzy methods multistage application in problems of intelligent analysis and processing of multidimensional data is proposed in the paper. The result of a numerical experiment for the analysis of the artificial data set is presented and preliminary conclusions are formulated. 2009 Article Методология анализа данных, основанная на многоэтапной нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2009. — № 3. — С. 33-46. — Бібліогр.: 22 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/8028 519.237.8+510.22 ru Інститут проблем штучного інтелекту МОН України та НАН України
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	2009
topic_facet	Интеллектуальный анализ данных
url	http://dspace.nbuv.gov.ua/handle/123456789/8028
citation_txt	Методология анализа данных, основанная на многоэтапной нечеткой кластеризации / Д.А. Вятченин // Штучний інтелект. — 2009. — № 3. — С. 33-46. — Бібліогр.: 22 назв. — рос.
work_keys_str_mv	AT vâtčeninda metodologiâanalizadannyhosnovannaânamnogoétapnojnečetkojklasterizacii
first_indexed	2025-07-02T10:46:49Z
last_indexed	2025-07-02T10:46:49Z
_version_	1836531801435144192
fulltext	«Штучний інтелект» 3’2009 33 2В УДК 519.237.8+510.22 Д.А. Вятченин Объединенный институт проблем информатики НАН Беларуси, г. Минск viattchenin@mail.ru Методология анализа данных, основанная на многоэтапной нечеткой кластеризации В статье предлагается методология многоэтапного применения нечетких методов автоматической классификации в задачах интеллектуального анализа и обработки многомерных данных. Приводится результат вычислительного эксперимента при анализе искусственного набора данных и сформулированы предварительные выводы. Введение При решении различных социально-экономических задач, при проектировании разнообразных технических устройств и в процессе моделирования сложных систем особая роль отводится решению задач классификации, для решения которых традицион- но применяются методы кластерного анализа, именуемые также методами распознавания образов с самообучением или методами автоматической классификации. Обрабатываемая информация зачастую оказывается неточной, нечеткой и противоречивой, что требует обращения к нечетким и возможностным методам автоматической классификации [1-4], в которых, в отличие от традиционных методов кластеризации, указывается степень принадлежности объекта кластеру, выражаемая, как правило, величиной из единичного отрезка вещественной прямой, что позволяет получить, с одной стороны, точные, а с другой – содержательно осмысленные результаты решения задачи классификации. Вместе с тем кластеризация служит лишь средством решения задачи простой типологизации, то есть выявления стратификационной структуры исследуемой совокуп- ности объектов, основанной на представлении классифицируемого множества в виде однородных групп объектов [5]. В таком случае решение задачи классификации является необходимым этапом исследования, предваряющим решение задачи структурной типологизации, то есть исследования структуры взаимосвязей получен- ных классов, включающего построение соответствующих иерархических систем – как на элементах классифицируемого множества, так и на классах элементов [5]. Таким образом, осуществление структурной типологизации множества объектов },...,{ 1 nxxX  предполагает построение структурной классификационной схемы, кото- рая определяется составляющими ее классами и взаимодействиями между классами – с одной стороны, а также объектами в пределах каждого класса – с другой. Собственно задача структурной типологизации множества объектов не является новой – в [5] рассмотрены разнообразные варианты конечных прикладных целей для данной задачи классификации и изложен мощный статистический аппарат для ее решения. Однако в случае обращения для решения указанной задачи к методам нечеткой кластеризации представляется необходимым учитывать специфические особенности этих методов, связанные, в первую очередь, с интерпретацией результа- тов нечеткой кластеризации. Вятченин Д.А. «Искусственный интеллект» 3’2009 34 2В Целью данной работы является разработка общей схемы последовательного при- менения различных методов нечеткой и возможностной кластеризации в процессе анализа данных для решения задачи структурной типологизации исследуемой сово- купности объектов. Краткий обзор методов нечеткой кластеризации Как и в традиционных методах кластерного анализа, в рамках нечеткого подхода к решению задачи автоматической классификации выделяются эвристическое, оптимиза- ционное и иерархическое направления. Наиболее распространенным подходом к ре- шению нечеткой модификации задачи автоматической классификации является опти- мизационный подход, методы которого предусматривают нахождение оптимального, в смысле используемого критерия качества ))(( XPQ , разбиения },,{)( 1 cAAXP  на заданное число c нечетких кластеров, описываемых функциями принадлежности li , cl ,,1 , ni ,,1 , определенных на исследуемой совокупности объектов },...,{ 1 nxxX  , так что задача нечеткой кластеризации заключается в нахождении экстремума целевой функции ))(( XPQ , что в общем виде описывается формулой   )( ))(( XP extrXPQ , (1) где  – множество всех возможных нечетких разбиений )(XP множества класси- фицируемых объектов X , при ограничениях, определяемых условием 0li , 1 1   n i li , ni ,,1 , cl ,,1 , (2) именуемым также условием нечеткого c -разбиения или нечеткого разбиения в смысле Распини [3], которое описывается матрицей ][ lincP  , где )( iAli xl  – значение принадлежности элемента Xxi  некоторому нечеткому кластеру },,{ 1 cl AAA  . При выборе вида функционала ))(( XPQ для проведения исследования учитывает- ся, в первую очередь, вид матрицы исходных данных, а также вид шкалы, в которой измерены признаки объектов исследуемой совокупности. В силу ограниченности изложения дальнейшее рассмотрение предлагаемой методологии будет проводиться исходя из предположения, что исходные данные описываются матрицей «объект- признак», имеющей вид ]ˆ[ˆ t imn xX  , ni ,,1 , mt ,,1 , так что каждый объект Xxi  может рассматриваться как точка в m -мерном признаковом пространстве )(XI m . В случае, когда исходные данные представлены в форме матрицы «объект-объект» ]ˆ[ˆ ijnn   , nji ,,1,  , где общее обозначение ij̂ используется вместо значений взаимных расстояний ijd̂ или коэффициентов сходства ijr̂ между объектами, общая схема анализа данных не претерпевает принципиальных изменений. В случае, когда данные об исследуемой совокупности описываются матрицей вида «объект-признак», большинство критериев качества нечеткого разбиения в общем имеют вид      c l n i l ili II xdPQ 1 1 ),(),(   , (3) где ix – элемент исследуемой совокупности, l – прототип нечеткого кластера )(XPAl  , и, как правило, в качестве ),( l ixd  используется квадрат какого-либо расс- Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 35 2В тояния. Как отмечает И.Д. Мандель, функционал (3) представляет собой «наиболее распространенный и изученный вариант экстремальной постановки задачи кластер-ана- лиза в терминах размытых множеств» [6]. Некоторые модификации критерия (3) при- ведены в табл. 1. Таблица 1 – Критерии качества нечеткого c -разбиения Вид критерия Параметры алгоритма Ссылка     c l n i l ili II FCM xPQ 1 1 2 ),(   nc 2 – число класcов;  1 – показатель нечеткости; [1]         c l la al c l n i l ili II BOFCM xPQ 1 2 1 1 2 )1( ),(    nc 2 – число класcов;  1 – показатель нечеткости; 10   – параметр однородности; [7]                  c l n i c a al l ili II ICS c x n PQ 1 1 1 2 2 1),(    nc 2 – число класcов;  1 – показатель нечеткости; 0 – параметр классификации; [8]         c l n i li c l n i l ili II PIM xPQ 1 1 1 1 2 ),(     nc 2 – число класcов;  1 – показатель нечеткости; 0 – параметр классификации; [9] Одной из главных проблем при использовании оптимизационных методов явля- ется определение «реального» числа c нечетких кластеров, на которые «расслаивается» исследуемая совокупность, или, иными словами, проблема обоснования числа кластеров, встающая наиболее остро, когда исследователю число классов c вообще неизвестно. Для решения этой проблемы были предложены различные показатели, характери- зующие получаемое при использовании того или иного алгоритма нечеткое разбиение },,{)( 1* cAAXP  . В частности, при поиске нечеткого c -разбиения с помощью FCM-алго- ритма, минимизирующего приведенный в табл. 1 критерий ),( PQII FCM , а также его моди- фикаций [1], [2], были предложены различные показатели, ряд которых приведен в табл. 2. Таблица 2 – Показатели оптимальности числа классов в нечетком c -разбиении Наименование показателя Вид показателя Решение задачи Ссылка Коэффициент разбиения     c l n i lipc n PV 1 1 21)(   )(max PVpcc [10] Показатель нечеткого гиперобъема                     c l n i li n i Tl i l ili fh xx PV 1 1 1 ))(( det)(      )(min PV fhc [11] Вятченин Д.А. «Искусственный интеллект» 3’2009 36 2В Продолж. табл. 2 Показатель толщины оболочки                 c l l c l n i li n i l l ili st c R Rx PV 1 1 11)(    )(min PVstc [12] Показатель компактности и разделимости                               c l n i li n i Tl i l ili c l n i Tll li cs xx trace trace PV 1 1 1 1 1 ))(( ))(( )(        )(max PVcsc [13] Если исходные данные представлены в форме матрицы «объект-объект» ]ˆ[ˆ ijnn   , nji ,,1,  , то для решения задачи нечеткой кластеризации используются неметрические алгоритмы и соответствующие им показатели оптимальности числа классов, ряд которых рассматривается в работах [3], [4]. Касательно методов нечеткой кластеризации иерархического направления следует отметить, что соответствующие кластер-процедуры отличаются достаточно большим разнообразием – к примеру, различные иерархические кластер-процедуры основаны на различных определениях иерархии [14], [15], а относительно алгоритмов эвристического направления нечеткой кластеризации необходимо указать, что, как и в случае традицион- ного подхода к решению задачи автоматической классификации, эвристические методы нечеткой кластеризации играют большую роль на этапе разведочного анализа данных [5] – к примеру, MCM-алгоритм приближенной кластеризации [16] используется для определения числа классов c в искомом нечетком c -разбиении )(XP и инициализации прототипов l , cl ,,1 для последующей обработки данных оптимизационными мето- дами нечеткой кластеризации, а D-AFC-TC-алгоритм возможностной кластеризации [17], [18] применяется для построения множества значений наиболее возможного числа нечетких кластеров lA , cl ,,1 в искомом )(XP [19]. Этапы структурной типологизации Как указывалось выше, осуществление структурной типологизации предусматри- вает построение иерархий классов, а также иерархий объектов – элементов классов. В силу того, что иерархические кластер-процедуры обладают особенностью, заключающей- ся в резком возрастании, с ростом количества объектов классифицируемой совокупности, времени вычислений и требований к объему оперативной памяти ЭВМ, алгоритмы иерар- хического подхода применимы для классификации совокупностей объектов сравнительно небольшого объема и не могут быть прямо использованы для структурной типологизации больших массивов данных. Таким образом, проведение исследования с целью осущест- вления структурной типологизации множества объектов предполагает ряд этапов: 1) разбиение множества объектов на априори известное, или нет, число c классов; 2) построение иерархии на элементах каждого класса полученного разбиения; 3) построение иерархии классов полученного разбиения. Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 37 2В Указанные этапы структурной типологизации исследуемой совокупности объек- тов и последовательность их осуществления схематично изображены на рис. 1. Рисунок 1 – Этапы осуществления структурной типологизации исследуемой совокупности объектов Следует отметить, что в случае, когда число классов c априори неизвестно, то представляется необходимым проведение разведочного анализа данных с целью установ- ления числа классов c , либо подмножества },,{ *  ccC  возможных значений числа клас- сов в искомом разбиении. Кроме того, если число классов оказывается сравнительно незначительным, а число объектов, попавших в каждый класс, достаточно велико, то этап разбиения на классы может быть повторно применен уже к множествам объектов – классам полученного разбиения; при этом возникает необходимость установления числа субкластеров в каждом классе и построение иерархии субкластеров в пределах каждого класса, что позволит проводить детальное исследование структуры классифицируемой совокупности. В свою очередь, при построении иерархии классов в рамках структурной классифи- кационной схемы, каждый класс может быть представлен либо его геометрическим центром, или, иными словами, прототипом, либо некоторым типичным для того или иного класса элементом, при этом нужно также отметить, что, помимо иерархических кластер-процедур, для выявления межкластерных связей могут применяться алгоритмы классификации на графах. Необходимо, однако, указать, что в ситуации, когда искомая кластерная структура характеризуется таким видом неопределенности, как размытость [3], что требует обращения к методам нечеткой кластеризации, возникает проблема выделения значимых частей нечетких кластеров полученного в результате реализации первого этапа нечет- кого c -разбиения )(XP с целью проведения дальнейшего исследования и реализации второго и третьего этапов. Вятченин Д.А. «Искусственный интеллект» 3’2009 38 2В Концепция α-ядер нечетких кластеров При обращении к оптимизационным методам нечеткой кластеризации, в силу усло- вия нечеткого c -разбиения (2) каждому объекту Xxi будет соответствовать вектор при- надлежностей ),,( 1 cii   классам полученного нечеткого c -разбиения * 1( ) { , , }cP X A A  , вследствие чего возникает проблема интерпретации результатов классификации, то есть отнесения того или иного объекта к возможно меньшему числу классов. Наиболее распространенным методом интерпретации результатов является дефаззификация мат- рицы ][ lincP  нечеткого c -разбиения по правилу максимального значения принад- лежности, выражаемого соотношением ailil MM iP   e , ca ,,2,1  , la  , (4) так что значениями принадлежности MM li матрицы MM ncP  являются числа 0 и 1. Однако подобный подход является неприемлемым, если для некоторого объекта Xxi  его значения принадлежностей составляют cli 1 , cl ,,1 . Кроме того, недостатком ука- занного подхода является утрата значений принадлежности объектов нечетким клас- терам, позволяющая содержательно интерпретировать результаты кластеризации. В свою очередь, концепция  -ядер нечетких кластеров, предложенная в [20], предполагает нахождение такого порога  , ]1,0( , чтобы выполнялось условие   )())(( 1 XcardASuppcard c l l    , (5) где },,{ 1 nxxX  – исследуемая совокупность объектов,  -ядра )(lA , },,1{ cl  нечетких кластеров PAl  , },,1{ cl  для некоторого ]1,0( представляют собой нечеткие множества уровня, определяемые как }\|),{()(    lilii l xA , так что ll AA )( , ]1,0( , },,{ 1 cl AAA  , и ))(( lASupp – носитель  -ядра )(lA нечеткого кластера PAl  , причем ll AASupp  ))(( , то есть носитель  -ядра нечет- кого кластера PAl  , cl ,,1 будет представлять собой  -срез }\|{   lii l XxA этого кластера при соответствующем значении  , а значения принадлежности объекта  -ядру определяются в соответствии с формулой        l i l ili li Ax Ax     ,0 , . (6) Порог  выбирается таким образом, чтобы каждый объект Xxi  , ni ,,1 при- надлежал бы по меньшей мере одному  -ядру нечеткого кластера, и может вычисляться по формуле lili  maxminˆ  , (7) что, в свою очередь, позволило сформулировать теорему [20], в соответствии с кото- рой носители },,{ 1 cAA    -ядер )}(,),({ 1  cAA  кластеров нечеткого c -разбиения Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 39 2В },,{)( 1 cAAXP  исследуемой совокупности объектов },,{ 1 nxxX  образуют покрытие исследуемой совокупности },,{ 1 nxxX  в том и только в том случае, когда  ˆ , ]1,0( , где ]1,0(ˆ  вычисляется по формуле (7). Следствиями доказанной теоремы является ряд сформулированных также в [20] положений – в частности, если в условии (5) имеет место равенство, то носители },,{ 1 cAA    -ядер кластеров нечеткого c -разбиения образуют разбиение исследуемой совокупности },,{ 1 nxxX  на непересекающиеся множества; кроме того, если  ˆ , где значение ̂ вычисляется по формуле (7), то покрытие, образуемое носителями },,{ 1 cAA    -ядер )}(,),({ 1  cAA  кластеров нечеткого c -разбиения },,{)( 1 cAAXP  , минимально. Концепция  -ядер нечетких кластеров позволяет, с одной стороны, отнести каждый объект исследуемой совокупности к наименьшему числу c~, cc  ~1 нечетких кластеров нечеткого c -разбиения },,{)( 1 cAAXP  , являющегося результатом класси- фикации, а с другой – сохранить значения принадлежности li , которые можно интер- претировать как степени обладания объектом Xxi  свойств класса, ассоциированного с нечетким кластером lA , },,1{ cl  – элементом нечеткого c -разбиения )(XP . Общая схема последовательного применения методов нечеткой кластеризации в процессе анализа данных Как указывается в [20], «в случаях, когда объем исследуемой совокупности },,{ 1 nxxX  достаточно велик, носители },,{ 1 cAA    -ядер )}(,),({ 1  cAA  класте- ров нечеткого c -разбиения },,{)( 1 cAAXP  могут рассматриваться как множества объектов, подлежащие дальнейшей классификации». Данный тезис является отправной точкой при многоэтапном применении различных методов нечеткой кластеризации для осуществления структурной типологизации исследуемой совокупности объектов. В случае отсутствия априорных предположений о числе классов в исследуемой совокупности объектов целесообразно построить подмножество },,{ *  ccC  возможных значений числа классов в искомом нечетком c -разбиении, для чего можно восполь- зоваться предложенной в [19] методологией – в таком случае подмножество C будет представлять собой носитель нечеткого множества )}(,{ˆ ˆ  ccV V , Cc  , где значения функции принадлежности )(ˆ cV интерпретируются как степени адекватности значений числа Cc  классов в искомом нечетком c -разбиении )(XP , что, с одной стороны, позволит содержательно оценить «степень возможности» того или иного значения числа классов Cc  , а с другой – применить (m)FCM-CV-алгоритм, позволяющий обрабатывать данные в полностью автоматическом режиме [19]. После разбиения исследуемой совокупности объектов с помощью некоторой кластер-процедуры группы оптимизационных методов нечеткой кластеризации на оптимальное, в смысле используемого показателя оптимальности, число c классов, сле- Вятченин Д.А. «Искусственный интеллект» 3’2009 40 2В дует выделить  -ядра нечетких кластеров полученного нечеткого c -разбиения )(XP , и дальнейший анализ проводить отдельно для каждой группы объектов, являющихся элементами носителя соответствующего  -ядра. Следует, однако, отметить, что при необходимости построения нечеткого c -разбие- ния },,{)( 1 cAAXP  , в случае, когда носители  -ядер )}(,),({ 1  cAA  нечетких клас- теров образуют покрытие классифицируемого множества объектов, то, при принадлеж- ности объекта нескольким носителям  -ядер нечетких кластеров, отнесение объекта к тому или иному классу можно производить в соответствии с правилом максимальной принадлежности, которое в рассматриваемом случае можно сформулировать следующим образом: если некоторый объект Xxi  , },,1{ ni  принадлежит носителю  -ядра более чем одного нечеткого кластера, то он должен быть отнесен к носителю  -ядра того нечеткого кластера, значение принадлежности li которого в смысле определения (6) является наибольшим; при этом максимальное значение li сохраняется, а значения при- надлежностей  -ядрам других нечетких кластеров полагаются равными нулю; в случае же, если объект ix принадлежит носителям  -ядер нескольких нечетких кластеров с одинаковыми значениями принадлежности li , то ix относится к каждому такому  - ядру с этим значением li , и для таких элементов Xxi  строится матрица пересечений между классами. Сформулированное таким образом правило максимальной принад- лежности позволяет сохранить значение li элемента Xxi  для содержательной интер- претации результатов классификации. Подобным образом могут интерпретироваться результаты, полученные с помощью D-AFC(с)-алгоритма возможностной кластериза- ции [18], [21]. Если число объектов – элементов носителя  -ядра нечеткого кластера окажется приемлемым для использования иерархических кластер-процедур, то в подоб- ной ситуации оказывается возможным построение иерархии на элементах каждого выде- ленного класса объектов; в противном случае каждый класс аналогичным способом разбивается на субкластеры, и дальнейший анализ производится для субкластеров. Этап исследования межкластерных связей подразумевает замену каждого нечет- кого кластера его прототипом и применением к соответствующим точкам пространства )(XIm некоторого иерархического алгоритма нечеткой кластеризации, либо процедуры классификации на нечетких графах. Подобный методологический прием, позволяющий существенно сократить число классифицируемых объектов с целью применения иерар- хических кластер-процедур, описан на примере решения задачи экономико-геологичес- кого районирования территории, изложенном в [6]. Общая схема осуществления структурной типологизации множества объектов с помощью методов нечеткой кластеризации представлена на рис. 2. Необходимо указать, что, в силу большого разнообразия методов нечеткой клас- теризации и существования нескольких видов кластерных структур, характеризуемых размытостью, конкретный вариант представленной схемы диктуется, во-первых, усло- виями решаемой задачи и целями исследования, а во-вторых – особенностями того или иного алгоритма, применяемого на каждом этапе. Следует также отметить, что этапы, выделенные пунктирными овалами, могут отсутствовать при проведении того или иного конкретного исследования; кроме того, каждый из указанных этапов может реализовы- ваться с помощью различных кластер-процедур, что, в свою очередь, позволит углубить анализ и выявить устойчивость структуры, искомой на соответствующем этапе. Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 41 2В Рисунок 2 – Схема структурной типологизации исследуемой совокупности объектов, основанная на поэтапном применении методов нечеткой кластеризации Иллюстративный пример Представляется целесообразным проиллюстрировать сущность предложенной методологии на простом примере. Для проведения вычислительного эксперимента были выбраны изображенные на рис. 3 двумерные данные, представляющие собой совокупность 30 объектов },,{ 301 xxX  . Визуальный анализ данных демонстрирует, что число классов в искомом нечет- ком c -разбиении )(XP может варьироваться от 2 до 6 – так, можно выделить два класса объектов, в первый из которых попадают объекты с номерами от 1 по 19, а во второй – с 20 по 30 включительно, с другой стороны, рассматривая разбиение множества X на три класса, можно выделить группы },,{ 61 xx  , },,{ 197 xx  и },,{ 3020 xx  ; в свою очередь, разбиение множества X на четыре класса состоит из групп },,{ 61 xx  , },,,,,{ 1916117 xxxx  , },,{ 1512 xx  , },,{ 3020 xx  , а разбиение X на пять классов – из групп },,{ 61 xx  , },,,,,{ 1916117 xxxx  , },,{ 1512 xx  , },,{ 2520 xx  , и },,{ 3026 xx  . При разбиении X на 6 классов выделяются скопления },,{ 61 xx  , },,{ 117 xx  , },,{ 1512 xx  , },,{ 1916 xx  , },,{ 2520 xx  , и },,{ 3026 xx  , однако объект 8x занимает промежуточное положение между первой и второй группами, а объект 26x – между пятой и шестой, из чего явно следует размытость границ классов объектов, что предполагает необходимость обращения к нечетким методам классификации. Этапы осуществления структурной типологиза- ции исследуемой совокупности, с указанием методов решения соответствующих за- дач, представлены в табл. 3. Вятченин Д.А. «Искусственный интеллект» 3’2009 42 2В 2€x 1€x Рисунок 3 – Двумерные данные для вычислительного эксперимента Таблица 3 – Этапы структурной типологизации анализируемой совокупности Номер и содержание этапа Метод решения задачи Ссылка 1 Построение множества значений наиболее возможного числа классов Построение нечеткого множества наиболее возможного числа нечетких кластеров с помощью D-AFC-TC-алгоритма возможностной кластеризации [19] 2 Построение кластерной структуры на множестве объектов Построение нечеткого c -разбиения на оптимальное число классов с помощью (m)FCM-CV-алгоритма нечеткой кластеризации [19] 3 Интерпретация результатов нечеткой кластеризации Выделение  -ядер нечетких кластеров [20] 4 Исследование внутрикластерной структуры Построение иерархий на подмножествах объектов – элементов носителей  -ядер нечетких кластеров с помощью H-AFC-TC- алгоритма возможностной кластеризации [15] 5 Исследование межкластерной структуры Построение иерархии на множестве прототипов нечетких кластеров с помощью H-AFC-TC-алгоритма возможностной кластеризации [15] При обращении к D-AFC-TC-алгоритму для построения нечеткого множества возможных значений числа классов )}(,{ˆ ˆ  ccV V , },,{ *  ccCc  , были проведены эксперименты с относительным обобщенным расстоянием Хемминга, относительным евклидовым расстоянием и относительной евклидовой нормой [19], [22]. При исполь- Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 43 2В зовании относительного обобщенного расстояния Хемминга было получено распреде- ление )(XR по 51̂ c нечетким  -кластерам при 0,80001   , а при использовании относительного евклидова расстояния и относительной евклидовой нормы было получено 4ˆˆ 32  cc при 0,84182   и 0,97503   соответственно, что дало возмож- ность построить нечеткие числа TbamV )25,4,5( 1111  и TbamV )26,3,4( 2222  , объединение которых позволило построить нечеткую величину V с непрерывной функ- цией принадлежности )(lV , и далее – нечеткое множество )}(,{ˆ ˆ  ccV V , }10,,4{ *  ccCc  возможных значений числа классов. Следует указать, что носи- тели нечетких  -кластеров – элементов соответствующих распределений )(XR пред- ставляют собой элементы экспертных разбиений на 4 и 5 классов. На рис. 4 а) символом ○ обозначены значения функции принадлежности )(ˆ cV нечеткого множества )}(,{ˆ ˆ  ccV V , }10,,4{ c возможных значений числа классов, а на рис. 4 б) – поведение для построенного V̂ обобщенного коэффициента разбиения )(~ PVpc при обработке данных (m)FCM-CV-алгоритмом. а) б) Рисунок 4 – Построение нечеткого c -разбиения на оптимальное число классов: а) нечеткое множество )}(,{ˆ ˆ  ccV V возможных значений числа классов; б) значения )(~ PVpc при обработке данных (m)FCM-CV-алгоритмом В свою очередь, на рис. 5 изображены значения принадлежностей в смысле выра- жения (6) элементов исследуемой совокупности  -ядрам нечетких кластеров построен- ного с помощью (m)FCM-CV-алгоритма нечеткого c -разбиения )(XP . Значения при- надлежности  li первого класса изображены символом ○, второго – символом ■, третьего – символом □, четвертого – символом ●, пятого – символом  , и, наконец, шестого класса – символом ▲. Пороговое значение, вычисленное по формуле (7), соста- вило 798097,0ˆ  . Из рис. 5 очевидно, что носители  -ядер нечетких кластеров )(XPAl  , 6,,1l , не пересекаются и соответствуют группам объектов экспертного разбиения на 6 классов. )(€ cV )(~ PVpc c c Вятченин Д.А. «Искусственный интеллект» 3’2009 44 2В  li i Рисунок 5 – Значения принадлежности объектов  -ядрам нечетких кластеров полученного нечеткого c -разбиения )(XP на 6 классов При обращении к H-AFC-TC-алгоритму возможностной кластеризации для выявле- ния иерархической структуры классов объектов – носителей  -ядер нечетких кластеров )(XP эксперимент проводился с использованием относительного евклидова расстояния. На рис. 6 а) – е) изображены иерархии распределений )(XR по нечетким  -кластерам объектов, являющихся элементами носителей  -ядер нечетких кластеров – элементов построенного нечеткого c -разбиения )(XP . Типичные точки нечетких  -кластеров рас- пределений )(XR для каждого значения уровня сходства  обозначены символом ●, а объекты ix , }30,,1{ i со значениями типичности, меньшими 1 – символом □. а) б) в) г) д) е) Рисунок 6 – Иерархическая структура классов объектов – носителей  -ядер нечетких кластеров )(XP Методология анализа данных, основанная на многоэтапной нечеткой кластеризации «Штучний інтелект» 3’2009 45 2В Результаты классификации на данном этапе демонстрируют, что первый, третий и четвертый классы объектов однородны и обладают достаточно простой структурой, в то время как второй, пятый и шестой классы могут быть подразделены на суб- кластеры. Следует также отметить, что в построенных с помощью H-AFC-TC- алгоритма иерархиях содержательный смысл значений типичности объектов для нечет- ких  -кластеров распределений )(XR , как и смысл значений  , при которых эти рас- пределения получены, отличны от значений принадлежности  li объектов  -ядрам нечетких кластеров и соответствующего значения порога ̂ [18]. Иерархическая структура прототипов l , 6,,1l нечетких кластеров 61 ,, AA  , координаты которых, вычисленные с помощью (m)FCM-CV-алгоритма, приведены в табл. 4, изображена на рис. 7. При проведении вычислительного эксперимента с H-AFC- TC-алгоритмом для построения иерархии прототипов l , 6,,1l также было исполь- зовано относительное евклидово расстояние. Таблица 4 – Координаты прототипов нечетких кластеров Значения координат Номер прототипа, l 1x̂ 2x̂ 1 0,114676 0,113194 2 0,072383 0,748145 3 0,426081 0,974915 4 0,499381 0,498146 5 0,911948 0,152280 6 0,900523 0,803509 Рисунок 7 – Иерархическая структура прототипов нечетких кластеров Представленная на рис. 7 иерархия прототипов отличается от иерархии рассмотрен- ных выше экспертных разбиений объектов по классам, что очевидно уже при 619,0 , когда исследуемая совокупность прототипов расслаивается на два класса. Данное обстоя- тельство объясняется свойствами транзитивного замыкания, используемого H-AFC-TC- алгоритмом. Заключение Разнообразие методов нечеткой кластеризации позволяет использовать различные из них на каждом этапе исследования, и схема осуществления структурной типологиза- ции, диктуемая целями исследования, характером данных и имеющейся априорной инфор- мацией, может варьироваться в каждом конкретном случае. Таким образом, предложенная методология многоэтапной нечеткой кластеризации может быть эффективно использова- на при решении самых разнообразных задач, таких, к примеру, как анализ данных в соци- ально-экономических исследованиях, обработка результатов научных экспериментов, проектирование систем поддержки принятия решений, в том числе специального назна- чения, обработка и анализ изображений, а также для декомпозиции баз правил в системах нечеткого вывода. Помимо точности и релевантности результатов классификации, полу- ченных на каждом этапе, главным достоинством предложенного подхода к анализу данных является возможность обработки данных в полностью автоматическом режиме, что открывает широкие возможности для решения задач в условиях реального времени. Вятченин Д.А. «Искусственный интеллект» 3’2009 46 2В Литература 1. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms / Bezdek J.C. – New York : Plenum Press, 1981. – 230 p. 2. 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. 3. Вятченин Д.А. Нечеткие методы автоматической классификации / Вятченин Д.А. – Минск : УП Технопринт, 2004. – 219 с. 4. 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. 5. Прикладная статистика: Классификация и снижение размерности: [справ. изд]. / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин; под ред. С.А. Айвазяна. – М. : Финансы и статистика, 1989. – 607 с. 6. Мандель И.Д. Кластерный анализ / Мандель И.Д. – М. : Финансы и статистика, 1988. – 176 с. 7. Wang H.-F. Bi-criteria fuzzy C-means analysis / H.F. Wang, C. Wang, G.Y. Wu // Fuzzy Sets and Systems. – 1994. – Vol. 64. – P. 311-319. 8. Özdemir D. Fuzzy algorithms for combined quantization and dithering / D. Özdemir, L. Akarun // IEEE Transactions on Image Processing. – 2001. – Vol. 10. – P. 923-931. 9. Özdemir D. A fuzzy algorithm for color quantization of images / D. Özdemir, L. Akarun // Pattern Recognition. – 2002. – Vol. 35. – P. 1785-1791. 10. Dunn J.C. Well-separated clusters and the optimal fuzzy partitions / J.C. Dunn // Journal of Cybernetics. – 1974. – Vol. 4. – P. 95-104. 11. Gath I. Unsupervised optimal fuzzy clustering / I. Gath, A.B. Geva // IEEE Transactions on Pattern Analysis and Machines Intelligence. – 1989. – Vol. 11. – P. 773-780. 12. Davé R.N. Validating fuzzy partitions obtained through C-shells clustering / R.N. Davé // Pattern Recognition Letters. – 1996. – Vol. 17. – P. 613-623. 13. Bouguessa M. An objective approach to cluster validation / M. Bouguessa, S. Wang, H. Sun // Pattern Recognition Letters. – 2006. – Vol. 27. – P. 1419-1430. 14. Geva A.B. Hierarchical unsupervised fuzzy clustering / A.B. Geva // IEEE Transactions on Fuzzy Systems. – 1999. – Vol. 7. – P. 723-733. 15. Вятченин Д.А. Иерархический AFC-алгоритм нечеткой кластеризации, основанный на операции транзитивного замыкания / Д.А. Вятченин, П.Е. Савыгин, А.В. Шарамет // Сборник научных статей Военной академии Республики Беларусь. – 2006. – № 10. – С. 39-48. 16. Yager R.R. Approximate clustering via the mountain method / R.R. Yager, D.P. Filev// IEEE Tran- sactions on Systems, Man, and Cybernetics. – 1994. – Vol. 24. – P. 1279-1284. 17. Вятченин Д.А. Прямые алгоритмы нечеткой кластеризации, основанные на операции транзитив- ного замыкания и их применение к обнаружению аномальных наблюдений / Д.А. Вятченин // Искусственный интеллект. – 2007. – № 3. – С. 205-216. 18. Вятченин Д.А. О возможностной интерпретации значений принадлежности в методе нечеткой класте- ризации, основанном на понятии распределения / Д.А. Вятченин // Вести Института современных знаний. – 2008. – № 3. – С. 85-90. 19. Вятченин Д.А. Применение нечетких чисел для обоснования кластеров в методах нечеткой кластеризации / Д.А. Вятченин // Искусственный интеллект. – 2008. – № 3. – С. 523-533. 20. Вятченин Д.А. Метод мягкой интерпретации результатов нечеткой кластеризации / Д.А. Вят- ченин // Таврический вестник информатики и математики. – 2008. – № 1. – С. 107-114. 21. Viattchenin D.A. A new heuristic algorithm of fuzzy clustering / D.A. Viattchenin // Control & Cyber- netics. – 2004. – Vol. 33. – P. 323-340. 22. Кофман А. Введение в теорию нечетких множеств / А. Кофман / [пер. с фр. ; под ред. С.И. Трав- кина]. – М. : Радио и связь,1982. – 432 с. D.A. Viattchenin Methodology of Data Analysis Based on Multistage Fuzzy Clustering A methodology of automatic classification fuzzy methods multistage application in problems of intelligent analysis and processing of multidimensional data is proposed in the paper. The result of a numerical experiment for the analysis of the artificial data set is presented and preliminary conclusions are formulated. Статья поступила в редакцию 01.06.2009.

Методология анализа данных, основанная на многоэтапной нечеткой кластеризации

Institution

Ähnliche Einträge