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

найти непрерывно дифференцируемую кривую

такую, что

(где — скалярное произ­ведение в RN),

и такую, что

где криволинейный интеграл берется вдоль — градиент функции обобщенного расстояния d* (g, h) от второго арумента, взятый при h=g.

Для экономии места производная точных формул для обобще­ния будет опущена.

Поскольку реальный расчет геодезических кривых на F(X) может быть слишком сложным, субоптимальное решение можно получить, следуя по линии «наименьшего сопротивления» от g0 к f, т. е. принимая v(s) за единичный вектор в конусе

для которого скалярное произведение

минимально.

Кластеризуемость

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

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

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

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

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

3.10.6. Представления и кластеризации

Одна из главных характеристик излагаемой здесь теории кластеризации состоит в проведении семантического и формаль­ного разграничения понятия кластера и кластеризации.

В предыдущем пункте приведено определение кластеров как особых подмножеств выборочного множества и обсуждены вопро­сы, связанные с этим определением.

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

Минимальные представления

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

Определение. Пусть r — отношение похожести в X и пусть с и f — нечеткие подмножества X. Если

где суммы берутся по всем уХ, то с называется нечетким r-представленпем нечеткого подмножества f (или, короче, просто представлением).

Примечание. Это определение выявляет формальный смысл понятия представления через требование, согласно которо­му выборочное множество f должно представляться линейной комбинацией нечетких кластеров в X (всех тех, которые имеют степень принадлежности Особо отметим, что выведенное из модифицированной алеф-1 логики выражение для объединений нечетких множеств — выражение аддитивного типа.

Определение. Пусть Н есть функция, отображающая нечеткие подмножества X в неотрицательные действительные числа. Тогда если с* таково, что а) с* есть представление f, для любого с-представления f, то с* называется Н-минимальным представлением f (или, короче, минимальным представлением).

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

(где суммирование ведется по X и β — действительное число в от­крытом (0, 1) интервале числовой прямой) обладает определен­ными желаемыми характеристиками представления.

Итеративное порождение кластеров

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

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

Определение. Пусть х — точка множества X, r — отношение похожести в X, f — нечеткое подмножество X. Если через rz обо­значить нечеткое подмножество X, определенное выражением

то rх будет называться главной компонентой f тогда и только тогда, когда для всех уХ

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

где сумма берется по всем уХ.

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

может быть сама по себе исследована для выделения основных компонент. Этот процесс может продолжаться до тех пор, пока не выполнится условие для некоторого малого положительного ε.

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

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

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

2) разработку адаптивных процедур кластеризации, которые непрерывно и автоматически модифицируют таксономии в ответ на динамические изменения базовой структуры подобия,