Парадигма развития науки. Идеологическое обеспечение (стр. 45 )

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

Кластеры и кластеризация

Главное, что характерно для результатов, представленных в этом разделе, заключается в формальном различении понятий кластер и кластеризация.

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

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

Необходимость в нечетких кластерах

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

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

С одной стороны, имеется структура, порожденная отношени­ем подобия, которое, в общем случае, представляет собой нетран­зитивное бинарное отношение. Другими словами, из «А подобно В» и «В подобно С» не следует, что «А подобно С».

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

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

3.10.3. Понятие кластера

Общепринятая формализация

Ниже будет дана формальная характеристика обще­принятой (т. е. не нечеткой) проблемы кластеризации. Несмотря на то, что эти результаты совершенно очевидны и полностью со­гласуются с неформальными комментариями предыдущего пункта настоящего раздела, они обеспечивают формальную основу для аксиоматического определения нечеткого кластера и оказываются полезными для лучшего понимания целесообразности такого определения.

Введем необходимые обозначения:

A. X — множество элементарных исходов.

Б. F — подмножество X, называемое выборочным множеством.

B. R — бинарное отношение на X, называемое отношением по­добия.

Если (х, y) R, то будем говорить, что х подобен у. В остальных случаях будем говорить, что х неподобен у или отличен от у. Предполагается, что отношение R:

1) рефлексивно, т. е. (х, x) R, если хХ,

2) симметрично, т. е.

Дополнение отношения R будет называться отношением различия.

Г. — дополнение подмножества А множества X.

Д. Р(х) —множество всех подмножеств множества X.

Е. R(A) —множество

Аналогично,

Определение. Подмножество А множества X называется R-кластером (или, для краткости, кластером) тогда и только тогда,, когда

Примечание. Это определение просто формализует нефор­мальное определение кластера, конкретизируя требование, соглас­но которому все точки, близкие А (т. е. точки R(A)) должны от­носиться к А, в то время как все точки, отличные от А (т. е. точ­ки , не должны относиться к А. Следующие, приводимые без доказательства результаты просты и представляют фор­мализацию сделанных комментариев относительно невозможнос­ти решений общепринятой проблемы кластеризации.

Утверждение. Пусть А — подмножество множества X. Тогда А — кластер в том и только в том случае, если

а) для всех х А,

б)для всех х А.

Следствие. Если А и В — кластеры, то они либо тождествен­ны, либо не пересекаются.

Определение. Пусть С — семейство непустых подмножеств, множества X. Тогда С называют покрытием X тогда и только тог­да, когда объединение всех элементов С совпадает с X.

Теорема существования. Пусть С — покрытие множества X. Для того чтобы каждый элемент С был кластером, необходимо в достаточно, чтобы:

а) отношение R было транзитивно,

б) C=X/R.

Последний результат можно перефразировать следующим об­разом: «Необходимое и достаточное условие существования по­крытия из кластеров состоит в том, чтобы R было отношением эквивалентности».

Таким образом, общепринятая кластеризация требует, чтобы отношение подобия было транзитивным. Поскольку в большинст­ве практических задач это требование не выполняется, то в общем случае решение проблемы кластеризации в традиционных терми­нах невозможно. Кроме того, процедуры, разработанные для пре­одоления этого недостатка, отображают числовую меру подобия на бинарное отношение эквивалентности (например, односвяз­ность) и деформируют природу исходной структуры, приводя к нежелательным результатам (например, к образованию цепей).

Определение нечеткого кластера

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

Введем необходимые обозначения:

A. X — обычное множество, называемое множеством элемен-тарных исходов или выборочным пространством.

Б. f — нечеткое подмножество X, называемое выборочным множеством.

B. r — рефлексивное, симметричное (нечеткое) отношение в X, называемое отношением подобия. Его дополнение d = 1—r называется отношением различия.

Г. F(х) — множество всех нечетких подмножеств X, имеющих непустое ядро (т. е. если f F(x), то существует некоторое х X, для которого f(x) = 1).

Д. Ω (f) — мощность нечеткого множества f.

Определение. Пусть g — нечеткое множество в X. Тогда g на-зывается нечетким r-кластером (или, для краткости, кластером) в том и только в том случае, когда

Примечание. Условие а) последнего определения обобща­ет оба условия определения обычного кластера.

Условие б) — это, по существу, условие непрерывности, не имеющее прототипа в обычном случае. Оно представляет собой простейшую формализацию утверждения о том, что нечеткие клас­сификации подобных точек должны быть подобны. Заметим, что никакое другое значение, кроме 1, не должно быть использовано в качестве множителя при разности в правой части, так как же­лательно, чтобы всякий раз, когда r(х, у) =0 на связь между клас­сификациями х и у не накладывалось никакого ограничения.

Из определения нечеткого кластера легко вывести следующие утверждения.

Утверждение. Если g и h — нечеткие кластеры, то они либо тождественны, либо их ядра не пересекаются.

Определение. Пусть С — семейство нечетких подмножеств множества X, такое, что: