Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.1.2. Описание алгоритмовРазличные нечеткие эвристические кластер-процедуры в качестве основы используют различные понятия и определения, так что их необходимо рассматривать перед изложением схемы алгоритма в каждом конкретном случае. 3.1.2.1. Алгоритм Гитмана — Левина[90] является одной из первых эвристических процедур, использующих понятие нечеткого множества, и строит разбиение нечеткого множества объектов, подлежащих классификации, на унимодальные нечеткие множества. Основные понятия и определения Пусть
и
где Нечеткое множество В является симметричным в том и только в том случае, если Нечеткое множество В является унимодальным в том и только в том случае, если четкое множество Дискретные нечеткие множества Некоторой точке что результат разбиения на группы Таким образом, если некоторая мода является внутренней точкой подмножества, то она является локальным максимумом функции Авторская версия алгоритма состоит из двух процедур, причем первая процедура, в свою очередь, состоит из двух частей: первая часть разбивает дискретное нечеткое множество В точек, подлежащих классификации, на симметричные нечеткие подмножества, а вторая часть отыскивает локальные максимумы мультимодальной функции принадлежности нечеткого множества В. Вторая процедура разбивает нечеткое множество В на унимодальные нечеткие множества, используя в качестве основы полученную в результате работы первой процедуры информацию о числе, взаимном расположении и значениях функции принадлежности точек Параметры алгоритма: Входными данными является матрица Хтул Схема алгоритма: 1 Строятся следующие последовательности: 1.1. последовательность 1.2. последовательность первым «кандидатом» в группу 2. Если 3. Производится формирование групп в соответствии со следующим правилом: пусть к некоторому моменту построено G групп, то есть сконструированы последовательности 3.1. если 3.2. если 3.3. если Процесс продолжается до исчерпания последовательности 4. Для каждой группы до точки 5. Ко всем точкам, за исключением локальных максимумов Приведенная версия процедуры основана на предположении, что при Может оказаться, что наибольшее значение функции принадлежности в некоторой группе сложно определить, какая из них является локальным максимумом. В качестве метода, позволяющего преодолеть подобное затруднение, может быть использовано на шаге 4 приведенной выше процедуры следующее правило: пусть Следует также указать, что в изложении схемы алгоритма, представленной в [22, с. 53-56], не описывается шаг, соответствующий второй процедуре авторской версии и, соответственно, шагу 5 версии, представленной выше, где группы 3.1.2.2. Алгоритм Тамуры — Хигути — Танаки[163] использует (max-min)-транзитивное замыкание нечеткой толерантности Г, описывающей исходные данные в виде матрицы близости Основные понятия и определения Пусть Параметры алгоритма: с — число кластеров в искомом разбиении Схема алгоритма: 1. Строится транзитивное замыкание f исходного отношения нечеткой толерантности Т в соответствии с формулой (2.40); 2. Вычисляются 3. Из полученной иерархии разбиений выбирается разбиение на Таким образом, объекты оказываются однозначно распределенными по четким классам, представляющим собой множества уровня а. Результат представляется в виде матрицы разбиения
3.1.2.3. Алгоритм Кутюрье — Фьолео[71] использует понятие так называемого максимально внутренне устойчивого множества (stable set internally maximal). Особенностью метода является возможность пересечения нечетких кластеров. Основные понятия и определения Пусть X — множество классифицируемых объектов, на котором задано нечеткое отношение обычного несходства I в виде соответствующей матрицы 1) нет элемента 2) для всех элементов 3) только для некоторых элементов Новое множество максимально внутренне устойчивых множеств упрощено: все максимально внутренне устойчивые множества, включенные в другие максимально внутренне устойчивые множества, выбывают из рассмотрения. Кластеры представляют собой максимально внутренне устойчивые множества, удовлетворяющие двум условиям: 1) условию представительства, в соответствии с которым любое максимально внутренне устойчивое множество с небольшим числом элементов не рассматривается; максимально внутренне устойчивое множество 2) условию разделимости, в соответствии с которым для любых двух максимально внутренне устойчивых множеств число элементов в области их пересечения не должно превышать пороговое значение w, задаваемое исследователем. Таким образом, множество кластеров
где символ 3 обозначает множество максимально внутренне устойчивых множеств. Параметры алгоритма: а — порог различия элементов, объединяемых в нечеткие кластеры,
Схема алгоритма: 1. Для некоторого задаваемого исследователем порога различия
2. Вычисляются максимально внутренне устойчивые множества для построенного четкого отношения несходства 3. В соответствии с критерием (3.3) для заданных исследователем параметров и и w из множества 3 максимально внутренне устойчивых множеств выделяются кластеры 4. Для каждого кластера
5. Строится матрица
Алгоритм был применен 3.1.2.4. Алгоритм Берштейна — Дзюбы[11] в качестве критерия оптимизации разбиения вершин исходного нечеткого графа на два класса использует наибольшую степень двудольности. Основные понятия и определения Пусть Степень двудольности нечеткого графа
где Для определения степени двудольности S, может быть использован любой из двух следующих способов. Первый способ определения степени двудольности заключается в том, что любую часть
где значения
В дальнейшем, для упрощения обозначений, ребра, являющиеся элементами множества I, будут обозначаться символом Второй способ определения степени двудольности состоит в ее вычислении по следующей формуле:
где, в свою очередь, некоторого ребра Максимальная двудольная часть графа G представляет собой двудольную часть, не являющуюся частью никакой другой. Если число вершин в нечетком графе G является нечетным, то в общем случае число максимальных двудольных частей, которые можно выделить в данном максимальном нечетком графе, может быть вычислено по формуле
где символом
Если же число вершин в нечетком графе G является четным, то число максимальных двудольных частей, которые можно выделить в данном максимальном нечетком графе, вычисляется в соответствии с формулой
Критерием оптимизации разбиения вершин исходного нечеткого графа на два класса является наибольшая степень двудольности Параметры алгоритма: Нечеткий граф задается в виде матрицы гпхл Схема алгоритма: 1. В нечетком графе G ранжируются все ребра 2. Рассматривается первое ребро 3 Для остальных ребер из последовательности 3.1. если 3.2. если 3.3. если 3.4. если 3.5. если 3.6. если 3.6.1. вершина х, помещается в список 3.6.2. вершина х, помещается в список 4 Если были просмотрены все ребра, вычислить степени двудольности Частными случаями задачи являются ситуации, когда оказывается необходимым выделить для исходного графа с четным числом вершин такую максимальную нечеткую двудольную часть с наибольшей степенью двудольности, которая содержит одинаковое число вершин в каждой из долей, а для графа с нечетным числом вершин необходимо выделить такую максимальную нечеткую двудольную часть с наибольшей степенью двудольности, которая содержит в одной доле 1) если число вершин 2) если число вершин Таким образом, после упорядочивания ребер на шаге 1 сложность алгоритма зависит от числа несмежных ребер исходного графа, которые находятся в последовательности рядом друг с другом [11, с. 119-120]. Необходимо также еще раз подчеркнуть, что данный алгоритм разбивает множество объектов 3.1.2.5. Другие алгоритмы,представляющие эвристическое направление нечеткого подхода в кластерном анализе, также сравнительно немногочисленны. К примеру, в работе [123] описывается метод, использующий, как и в алгоритме Тамуры — Хигути [47] рассматривается процедура кластеризации, исходными данными для которой также является нечеткое отношение сходства. В работе [178] описывается человеко-машинный подход к решению нечеткой модификации задачи кластерного анализа. Сущность предлагаемого подхода состоит в том, что нечеткие кластеры, являющиеся нечеткими множествами уровня а, в свою очередь, порожденными некоторой нечеткой толерантностью Т, матрица которой является матрицей исходных данных, образуют так называемое представление
|
1 |
Оглавление
|