3.3.2.2. Алгоритм Думитреску (FDH algorithm)

[81] является дивизимной процедурой, последовательно строящей бинарное дерево нечеткой иерархии.

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

Пусть, как и ранее, — исследуемая совокупность объектов, данные о которых представлены в виде матрицы «объект-свойство» , то есть каждый объект представляет собой точку в пространстве признаков Кластерная структура исследуемого множества объектов X описывается семейством с разделенных нечетких множеств, образующих разбиение на нечеткие кластеры. Если некоторый нечеткий кластер неоднороден, то можно рассматривать его субструктуру, которая, в свою очередь, также может быть описана некоторым разбиением нечеткого множества так что образуется многоуровневая нечеткая классификация, и каждое последующее разбиение является уточнением разбиения, соответствующего предыдущему уровню классификации. Перед рассмотрением основных определений, введенных Д. Думитреску, следует оговорить, что операции нечеткими множествами, в частности, рассмотренные в главе 2 операции пересечения и объединения нечетких множеств, в общем, определяются с помощью треугольных норм (-норм), обозначаемых символом Т, и треугольных конорм (-конорм, -норм), обозначаемых символом S [34, с. 29-36]; однако в данном случае полное рассмотрение треугольных норм нецелесообразно. При разработке процедуры Д. Думитреску [81, с. 146] определил операции пересечения и объединения нечетких множеств с помощью треугольных норм и треугольных конорм следующим образом:

1) Пересечение нечетких множеств А и В определяется в соответствии с формулой

    (3.112)

где

2) Объединение нечетких множеств А и В определяется в соответствии с формулой

где

При дальнейшем рассмотрении метода, предложенного Д. Думитреску, будет приниматься, что операции пересечения и объединения нечетких множеств определены с помощью (3.112) и (3.113).

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

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

Поскольку символом П обозначается множество всех нечетких разбиений исследуемой совокупности объектов то множество всех нечетких разбиений некоторого нечеткого множества будет обозначаться символом П и пусть имеет место Нечеткое разбиение предшествует нечеткому разбиению или, как выражается автор процедуры [81, с. 146], «уточняет» нечеткое разбиение что обозначается в том случае, если каждый элемент, или, по выражению автора алгоритма, атом разбиения может быть представлен объединением атомов разбиения что можно записать также следующим образом: если и только если z и и существует разбиение множества такое, что вьшолняется условие и условие

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

кластер может быть представлен прототипом, или, иными словами, центром

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

    (3.114)

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

    (3.115)

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

    (3.116)

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

    (3.117)

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

    (3.118)

представляющей собой ни что иное, как функционал Дж. Беждека — Дж. Данна в виде (3.46) при так что, естественно, интерес представляет задача минимизации функционала (3.118).

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

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

    (3.119)

если выполняются условия

    (3.120)

где — центр нечеткого кластера — степень принадлежности некоторой точки нечеткому кластеру А, a — степень принадлежности некоторой точки нечеткому кластеру

Таким образом, используя в алгоритме Беждека — Данна соотношения (3.120) и (3.121) для вычисления центров нечетких кластеров и построения нечетких разбиений, можно получить процедуру, которую Д. Думитреску назвал обобщенной иечеткой процедурой ISODATA (Generalized Fuzzy ISODATA), или, сокращенно, GFI алгоритмом [81, с. 148]. В частности, при данная процедура превращается в описанный выше алгоритм Беждека — Данна при

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

и степень поляризации нечеткого разбиения может рассматриваться как мера качества разбиения.

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

    (3.122)

так что отношение представляет собой определенный на предпорядок.

Пусть — нечеткое множество и — нечеткое разбиение Степень поляризации бинарного нечеткого разбиения нечеткого множества представляет собой функцию удовлетворяющую следующим условиям:

Из условия 2) очевидно, что если Р является разбиением исследуемой совокупности объектов X, то только в том случае, если Р является четким разбиением Данное обстоятельство вместе с условием 3) позволяют рассматривать как своего рода «меру неразмытости» нечеткого разбиения Р.

Степени принадлежности компактным и хорошо разделенным, или, используя авторскую терминологию, «реальным», кластерам, полученные последовательной бинарной декомпозицией данных, сохраняют поляризацию в областях 0 и 1. Значение степени принадлежности в области 0.5 говорит об отсутствии структурированности данных.

Подобные рассуждения непосредственно подводят к следующему способу определения степени поляризации:

    (3.123)

где, в свою очередь, — значение принадлежности i-й точки нечеткому множеству уровня 0.5, определяемому в соответствии с выражением (2.4), что в данной ситуации также можно записать в следующем виде:

    (3.124)

и 0, иначе

Знаменатель в выражении (3.123) представляет собой просто количество точек в кластерах разбиения Таким образом, для степени поляризации, определяемой в соответствии с выражением (3.123), в силу условий 1) — 4), и можно допустить, что нечеткое разбиение описывает «реальные» кластеры в том и только в том случае, если для каждого класса существует х, такой, что . В таком случае представляет собой некоторый порог, выражающий уверенность в том, что кластеры являются «реальными». Для иллюстрации вышеизложенного целесообразно рассмотреть следующий пример [81, с. 151].

Пусть — исследуемая совокупность объектов и нечеткое разбиение совокупности X описывается матрицей, представленной таблицей 3.2.

Таблица 3.2. Матрица нечеткого разбиения Р совокупности X на два класса

В соответствии с так что при к: нечеткие кластеры, описываемые разбиением Р, могут рассматриваться как «реальные».

Далее, пусть — нечеткое разбиение кластера описываемое матрицей, представленной таблицей 3.3.

Таблица 3 3. Матрица нечеткого разбиения кластера на два класса

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

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

Таблица 3.4. Матрица нечеткого разбиения кластера А на два класса

При вычислении значения степени поляризации становится очевидным, что являются «реальными» кластерами при причем нечеткий кластер А: содержит только объект

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

1) , либо либо для всех

2) для каждого , так что где

Иными словами, — множество всех нечетких подмножеств, составляющих нечеткое множество Нечеткая иерархия Н

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

Стратификационный индекс всюду определенной нечеткой иерархии Н представляет собой функцию удовлетворяющую следующим условиям:

1) для любых имеет место неравенство

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

    (3.125)

где X; представляет собой элемент матрицы «объект-свойство» (1.1), то есть значение признака на объекте.

Если атомы не являются «реальными» кластерами, можно говорить об отсутствии кластерной структуры в исследуемой совокупности объектов Если же атомы являются «реальными» кластерами, то полагается Следует указать на небольшое изменение смысла обозначений: в обозначении разбиения индекс обозначает уровень декомпозиции, символ I — номер разбиения соответствующего уровня, а символ обозначает кластер, разбиения уровня декомпозиции. Далее, используя -алгоритм, вычисляем бинарные нечеткие разбиения

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

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

    (3.126)

Естественно, что число классов в разбиении уровня будет равно одному, а в разбиении уровня — двум, так что при число собственно разбиений будет равно одному, следовательно, при обозначении разбиений верхний индекс I можно опускать.

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

Исходные данные задаются в виде матрицы «объект-свойство» (1.1). Входные параметры как таковые отсутствуют. В процессе работы алгоритма используется счетчик терминальных узлов с. Процесс присвоения номеров I разбиениям ) детально не рассматривается.

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

1 Полагается

2 Для текущего уровня нумеруются разбиения для каждого разбиения просматриваются все атомы, и для каждого непустого

пустого нечеткого кластера осуществляется выполнение условия, описанного на шаге 4; все кластеры терминальные узлы распределяются в нечеткое разбиение и в дальнейшем не подвергаются обработке GH алгоритмом;

3. Если для всех I текущего уровня выполняется то алгоритм прекращает работу, в противном случае полагается ! и осуществляется переход на шаг 2;

4. Для каждого атома разбиения при помощи GFI алгоритма вычисляется нечеткое разбиение если являются «реальными» кластерами, то они образуют разбиение -го уровня в противном случае атом не образует разбиения уровня и считается неделимым нечетким кластером — терминальным узлом, полагается с и осуществляется переход к рассмотрению другого атома.

Следует отметить, что, как отмечает Д. Думитреску [81, с Л 53], число терминальных узлов с в бинарном дереве соответствует «оптимальному» числу классов в исследуемой совокупности объектов так что ГОН алгоритм может использоваться для отыскания естественного числа классов перед применением оптимизационной кластер-процедуры, использующей число классов с в качестве входного параметра.

В работе [81] также предлагается адаптивная метрика для случая различного размера кластеров.