3.1.2. Описание алгоритмов

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

3.1.2.1. Алгоритм Гитмана — Левина

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

Основные понятия и определения

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

и

где — некоторая метрика. Необходимо отметить, что при четкое множество представляет собой множество уровня а нечеткого множества В в смысле условия (2.1).

Нечеткое множество В является симметричным в том и только в том случае, если Очевидно, что если нечеткое множество В является симметричным, то справедливо соотношение

Нечеткое множество В является унимодальным в том и только в том случае, если четкое множество является связанным

Дискретные нечеткие множества определяют разбиение нечеткого множества В на G нечетких подмножеств. Точка , для которой выполняется условие будет именоваться модальной точкой или просто модой группы . Некоторая мода будет именоваться локальным максимумом функции и обозначаться символом , если для нее выполняется соотношение

Некоторой точке ставится в соответствие точка х,, такая, что тогда точка будет именоваться внутренней точкой подмножества А в том и только в том случае, если множество включает в себя по меньшей мере одну точку из множества А. Необходимо указать, что в оригинальной версии алгоритма используется пороговое значение так что и с каждой точкой сопоставляется число иными словами, — число точек в d - окрестности точки Очевидно, что если в качестве функции, сопоставляющей точке значение выступает функция принадлежности нечеткого множества В, то в качестве порога может быть выбрано некоторое значение а — порог различия элементов, объединяемых в кластеры, . Следует отметить,

что результат разбиения на группы полностью определяется порогом d, который должен быть не настолько низким, что , и не настолько высоким, чтобы

Таким образом, если некоторая мода является внутренней точкой подмножества, то она является локальным максимумом функции

Авторская версия алгоритма состоит из двух процедур, причем первая процедура, в свою очередь, состоит из двух частей: первая часть разбивает дискретное нечеткое множество В точек, подлежащих классификации, на симметричные нечеткие подмножества, а вторая часть отыскивает локальные максимумы мультимодальной функции принадлежности нечеткого множества В. Вторая процедура разбивает нечеткое множество В на унимодальные нечеткие множества, используя в качестве основы полученную в результате работы первой процедуры информацию о числе, взаимном расположении и значениях функции принадлежности точек локальных максимумов функции принадлежности В изложенном ниже варианте алгоритм представлен в виде единой кластер-процедуры.

Параметры алгоритма:

Входными данными является матрица Хтул параметром алгоритма — порог различия объектов

Схема алгоритма:

1 Строятся следующие последовательности:

1.1. последовательность точек исследуемой совокупности, х,, упорядоченных в соответствии со значениями их функции принадлежности, так что при где — функции принадлежности точек соответственно;

1.2. последовательность представляющая собой упорядоченную в соответствии с их расстояниями до точки то есть при последовательность точек — «кандидатов» в группу то есть группу, для которой точка будет являться модой, так что

первым «кандидатом» в группу будет точка следующей точкой — «кандидатом» в группу будет точка и так далее;

2. Если то распределяются в группу а точка рассматривается как мода второй группы, так что формируется последовательность в которой точки упорядочиваются по расстоянию до точки так что при подобный процесс выполняется для любой последовательности так что если — мода группы то первым «кандидатом» в группу будет точка

3. Производится формирование групп в соответствии со следующим правилом: пусть к некоторому моменту построено G групп, то есть сконструированы последовательности точек — «кандидатов» и пусть некоторую точку требуется приписать некоторой группе тогда как все предшествующие ей точки расклассифицированы, тогда оказываются возможными следующие ситуации:

3.1. если то точка включается в формируемую группу А;

3.2. если некоторого где L — множество индексов, представляющих те группы, точки — «кандидаты» которых идентичны у q, то точка включается в ту группу, к которой приписан ее ближайший сосед, имеющий наибольшее значение функции принадлежности;

3.3. если для то формируется новая группа, для которой точка является модой;

Процесс продолжается до исчерпания последовательности

4. Для каждой группы и соответствующей ей моды находится минимальное расстояние

до точки , являющейся ближайшей к группе А и лежащей вне ее: точка будет локальным максимумом, если множество включает в себя точки группы в противном случае точка является не локальным максимумом, а граничной точкой группы данная процедура применяется ко всем модам так что формируется последовательность локальных максимумов упорядоченная в соответствии со следующим правилом: для локальных максимумов локальные максимумы к расположены так, что

5. Ко всем точкам, за исключением локальных максимумов порождающих кластеры применяется следующее правило: точка , расположенная в последовательности в -й позиции, то есть распределяется в ту группу в которой находится ее ближайший сосед с более высоким значением функции принадлежности, так что строится разбиение и алгоритм прекращает работу.

Приведенная версия процедуры основана на предположении, что при выполняется неравенство Вместе с тем, возможной оказывается также ситуация, когда значение функции принадлежности оказывается одинаковым для нескольких точек, то есть . В таком случае проблема решается внесением изменения на шаге 3 процедуры и перестановкой элементов в последовательности А следующим образом: при сформированных G группах некоторая точка подлежит включению в некоторую группу Если для и если то необходимо проверить выполнение равенства Новая группа с модой образуется только в том случае, если ни одна из точек имеющих такое же значение функции принадлежности, как и точка не идентична с точкой

Может оказаться, что наибольшее значение функции принадлежности в некоторой группе получают несколько точек, поэтому

сложно определить, какая из них является локальным максимумом. В качестве метода, позволяющего преодолеть подобное затруднение, может быть использовано на шаге 4 приведенной выше процедуры следующее правило: пусть подмножество точек из А, имеющих, как и точка максимальное значение функции принадлежности; каждая из точек подмножества проверяется как мода группы А, и если хотя бы одна из них является пограничной для группы А, то точка f не рассматривается как локальный максимум.

Следует также указать, что в изложении схемы алгоритма, представленной в [22, с. 53-56], не описывается шаг, соответствующий второй процедуре авторской версии и, соответственно, шагу 5 версии, представленной выше, где группы нечеткого множества В порождают унимодальные нечеткие множества Вместо этого предлагается следующая процедура построения нечетких кластеров с: пусть с — сформированная последовательность локальных максимумов; если на множестве задана нечеткая толерантность Г, так что — степень сходства элементов то степень принадлежности элемента кластеру может быть вычислена по формуле Многочисленные вычислительные эксперименты — для 1000 сгенерированных объектов — показали достаточно высокую скорость вычислений при небольших затратах памяти, а получаемые кластеры могут иметь как эллиптическую форму, так и форму окружности.

3.1.2.2. Алгоритм Тамуры — Хигути — Танаки

[163] использует (max-min)-транзитивное замыкание нечеткой толерантности Г, описывающей исходные данные в виде матрицы близости и состоит из трех шагов.

Основные понятия и определения

Пусть — множество классифицируемых объектов, на котором задана нечеткая толерантность Т в виде матрицы глхи близости объектов (1.3).

Параметры алгоритма:

с — число кластеров в искомом разбиении

Схема алгоритма:

1. Строится транзитивное замыкание f исходного отношения нечеткой толерантности Т в соответствии с формулой (2.40);

2. Вычисляются -уровни, полученного нечеткого отношения эквивалентности Т и для каждого выделяются кластеры в соответствии с правилом: если для некоторых то объекты принадлежат кластеру

3. Из полученной иерархии разбиений выбирается разбиение на классов соответствующее некоторому порогу , и алгоритм прекращает работу.

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

3.1.2.3. Алгоритм Кутюрье — Фьолео

[71] использует понятие так называемого максимально внутренне устойчивого множества (stable set internally maximal). Особенностью метода является возможность пересечения нечетких кластеров.

Основные понятия и определения

Пусть X — множество классифицируемых объектов, на котором задано нечеткое отношение обычного несходства I в виде соответствующей матрицы Пусть для некоторого четкое отношение является а-уровнем нечеткого отношения обычного несходства I и некоторое подмножество исследуемой совокупности объектов, Пусть обозначает множество объектов, наиболее отличающихся по крайней мере от некоторого одного элемента . Тогда подмножество будет именоваться максимально внутренне устойчивым множеством, если выполняются условие и условие При вычислении максимально внутренне устойчивых множеств рассматриваются три варианта:

1) нет элемента такого, что для некоторого выполняется : максимально внутренне устойчивое множество замещается множеством

2) для всех элементов выполняется условие добавляется новое максимально внутренне устойчивое множество

3) только для некоторых элементов выполняется условие так что максимально внутренне устойчивое множество разбивается на два подмножества, где — подмножество элементов подобных элементу — подмножество элементов отличных от элемента создается новое максимально внутренне устойчивое множество

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

Кластеры представляют собой максимально внутренне устойчивые множества, удовлетворяющие двум условиям:

1) условию представительства, в соответствии с которым любое максимально внутренне устойчивое множество с небольшим числом элементов не рассматривается; максимально внутренне устойчивое множество является кластером, если где — порог, задаваемый исследователем;

2) условию разделимости, в соответствии с которым для любых двух максимально внутренне устойчивых множеств число элементов в области их пересечения не должно превышать пороговое значение w, задаваемое исследователем.

Таким образом, множество кластеров должно удовлетворять следующему условию:

где символ 3 обозначает множество максимально внутренне устойчивых множеств.

Параметры алгоритма: а — порог различия элементов, объединяемых в нечеткие кластеры,

— минимальное число элементов в нечетком кластере

— максимальное число элементов в области пересечения любых двух нечетких кластеров;

Схема алгоритма:

1. Для некоторого задаваемого исследователем порога различия строится — a-уровень нечеткого отношения несходства I в соответствии с условием

2. Вычисляются максимально внутренне устойчивые множества для построенного четкого отношения несходства

3. В соответствии с критерием (3.3) для заданных исследователем параметров и и w из множества 3 максимально внутренне устойчивых множеств выделяются кластеры

4. Для каждого кластера определяется точка являющаяся его центром, и строится функция принадлежности которая удовлетворяет следующему условию:

5. Строится матрица нечеткого покрытия элементами которой являются степени сходства элементов множества с центрами кластеров в соответствии со следующей формулой:

Алгоритм был применен для анализа состояния 165 французских фирм в 1995 финансовом году при различных значениях входных параметров и в сравнении с алгоритмом Беждека — Данна показал хорошие результаты.

3.1.2.4. Алгоритм Берштейна — Дзюбы

[11] в качестве критерия оптимизации разбиения вершин исходного нечеткого графа на два класса использует наибольшую степень двудольности.

Основные понятия и определения

Пусть — нечеткий граф, где — множество вершин, а — нечеткое множество ребер нечеткого графа G, где — функция принадлежности ребра так что

Степень двудольности нечеткого графа определяется в соответствии с выражением

где символом обозначается степень двудольности 1-й двудольной части нечеткого графа G, а символом с — число различных максимальных двудольных частей данного нечеткого графа

Для определения степени двудольности S, может быть использован любой из двух следующих способов.

Первый способ определения степени двудольности заключается в том, что любую часть где можно рассматривать как нечеткую двудольную часть графа G со степенью двудольности, вычисляемой в соответствии с формулой

где значения определяются по формулам

В дальнейшем, для упрощения обозначений, ребра, являющиеся элементами множества I, будут обозначаться символом а ребра, являющиеся элементами множества II, — символом

Второй способ определения степени двудольности состоит в ее вычислении по следующей формуле:

где, в свою очередь, — значение функции принадлежности некоторого ребра — значение функции принадлежности

некоторого ребра - максимально возможное число ребер между вершинами множества — максимально возможное число ребер между вершинами множества а символами обозначено число вершин во множестве X и множестве соответственно. В дальнейшем степень двудольности, вычисленная в соответствии с первым способом, то есть по формуле (3.5), будет обозначаться символом а если для этой цели применяется второй способ, то есть формула (3.8) — соответственно, символом поскольку, в общем, Таким образом, представляется очевидным, что если во множествах вершин графа, полученного в результате выделения двудольной части, не существует ни одной дуги, то степень двудольности такого графа равна 1, причем независимо от способа вычисления величины

Максимальная двудольная часть графа G представляет собой двудольную часть, не являющуюся частью никакой другой. Если число вершин в нечетком графе G является нечетным, то в общем случае число максимальных двудольных частей, которые можно выделить в данном максимальном нечетком графе, может быть вычислено по формуле

где символом обозначается округление величины в меньшую сторону, а символ традиционно обозначает число сочетаний:

Если же число вершин в нечетком графе G является четным, то число максимальных двудольных частей, которые можно выделить в данном максимальном нечетком графе, вычисляется в соответствии с формулой

Критерием оптимизации разбиения вершин исходного нечеткого графа на два класса является наибольшая степень двудольности или

Параметры алгоритма:

Нечеткий граф задается в виде матрицы гпхл отношения нечеткой толерантности. Ребра процессе выполнения алгоритма не рассматриваются. Входные параметры как таковые отсутствуют.

Схема алгоритма:

1. В нечетком графе G ранжируются все ребра в порядке убывания их степеней принадлежности так что формируется последовательность

2. Рассматривается первое ребро с максимальной степенью принадлежности из последовательности и вершина инцидентная этому ребру, помещается в первую долю, то есть список а вершина х, — в другую долю, то есть список

3 Для остальных ребер из последовательности

3.1. если , то вершина помещается в список

3.2. если то вершина помещается в список X;

3.3. если , то вершина помещается в список

3.4. если то вершина х, помещается в список X;

3.5. если или то ребро прибавляется к нечеткой двудольной части;

3.6. если или то оказываются возможны два варианта:

3.6.1. вершина х, помещается в список , вершина х, помещается в список

3.6.2. вершина х, помещается в список вершина помещается в список

4 Если были просмотрены все ребра, вычислить степени двудольности и/или по соответствующим формулам, и алгоритм прекращает работу; в противном случае осуществляется переход на шаг 3.

Частными случаями задачи являются ситуации, когда оказывается необходимым выделить для исходного графа с четным числом вершин такую максимальную нечеткую двудольную часть с наибольшей степенью двудольности, которая содержит одинаковое число вершин в каждой из долей, а для графа с нечетным числом вершин необходимо выделить такую максимальную нечеткую двудольную часть с наибольшей степенью двудольности, которая содержит в одной доле вершин и в другой доле вершин. В таких случаях в шаг 3 вышеприведенной версии алгоритма следует включить проверку дополнительного условия в одной из следующих двух формулировок:

1) если число вершин в исходном графе G — четное и или число вершин в исходном графе G — нечетное и то все остальные, не просмотренные ранее вершины помещаются в список X

2) если число вершин в исходном графе G — четное и или число вершин в исходном графе G — нечетное и то все остальные, не просмотренные ранее вершины помещаются в список X.

Таким образом, после упорядочивания ребер на шаге 1 сложность алгоритма зависит от числа несмежных ребер исходного графа, которые находятся в последовательности рядом друг с другом [11, с. 119-120].

Необходимо также еще раз подчеркнуть, что данный алгоритм разбивает множество объектов представленных в виде вершин графа, на два класса. Если же при решении задачи классификации множество объектов необходимо разбить на большее число групп, то сначала выделяется двудольная структура, после чего каждый из выделенных классов снова разбивается на два подкласса и так далее до тех пор, пока классифицируемое множество не будет разделено на заданное число классов [11, с. 121].

3.1.2.5. Другие алгоритмы,

представляющие эвристическое направление нечеткого подхода в кластерном анализе, также сравнительно немногочисленны. К примеру, в работе [123] описывается метод, использующий, как и в алгоритме Тамуры — Хигути Танаки, операцию транзитивного замыкания, а в исследовании И. 3. Батыршина

[47] рассматривается процедура кластеризации, исходными данными для которой также является нечеткое отношение сходства.

В работе [178] описывается человеко-машинный подход к решению нечеткой модификации задачи кластерного анализа. Сущность предлагаемого подхода состоит в том, что нечеткие кластеры, являющиеся нечеткими множествами уровня а, в свою очередь, порожденными некоторой нечеткой толерантностью Т, матрица которой является матрицей исходных данных, образуют так называемое представление исследуемой совокупности объектов для некоторого уровня если выполняется условие и число нечетких кластеров в представлении оказывается не меньшим, чем два, так что решение задачи классификации подразумевает выбор некоторого единственного представления из множества различных представлений для различных значений Значение а, таким образом, представляет собой порог сходства элементов, объединяемых в некоторый нечеткий кластер. Метод оправдан с гносеологической точки зрения, позволяет выделять кластеры сложной формы и классифицировать объекты, когда матрица близости классифицируемых объектов представляет собой матрицу любой нечеткой толерантности более того, поскольку нечеткие кластеры представляются как нечеткие множества уровня, то допускается их пересечение [17]. Вместе с тем, применение данного подхода вызывает затруднения обработки данных при большом объеме исследуемой совокупности; кроме того, выбор термина «представление» (representation), используемого для определения искомой структуры, является неудачным, поскольку традиционно в задачах кластер-анализа данный термин имеет отличный от используемого в [178] смысл.