Характеристика моделирования, понятия модели (стр. 8 из 10)

Числовые характеристики первой группы, как правило, соответствуют аксиоматике Евклида. Для субъективных показателей возникает задача выбора приемлемой метрики, а в дальнейшем - сопоставимости показателей обеих групп. Для этого существуют различные искусственные методы включающие нормирование показателей, т. е. представление чисел в относительных единицах, как правило, на отрезке [0; 1].

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

-содержательной репрезентативности, т. е. информация должна отражать существенные для исследования свойства объектов классификации;

-полноте объема информации, достаточной для объяснения явлений;

-достоверности;

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

релевантности (степень соответствия запроса и найденного, то есть уместность результата или адекватность) экспертных оценок.

43. Целевые функции кластеризации

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

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

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

Сформулируем некоторые целевые функции, способные оценить качество классификации и выбрать оптимальные варианты.

А. Минимум объектов, не попавших ни в один кластер (потери классификации)

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

где:

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

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

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

В.Максимально возможная компактность каждого кластера

Компактность кластера можно определить следующим образом:

• разделить исходное множество на кластеры;

• у каждого кластера вычислить условный «центр массы».

С. Максимальное суммарное расстояние между границами (оболочками) кластеров

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

D. Максимальное совпадение признаков (однородность) в каждом кластере

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

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

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

Е. Максимальное приближение реального числа кластеров к теоретически идеальному.

F. Максимальная концентрация объектов в каждом кластере около расчетного ядра.

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

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

44. Методы кластеризации

-K-средних (K-means)

-Графовые алгоритмы кластеризации

-Статистические алгоритмы кластеризации

-Алгоритм ФОРЕЛЬ

-Иерархическая кластеризация или таксономия

-Нейронная сеть Кохонена

-Ансамбль кластеризаторов

45. Кластеризация полным перебором объектов

Методически этот способ кластеризации наиболее прост, но довольно трудоемок. Применяется при небольшом числе объектов и обычно дает до 5-6 кластеров.

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

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

46. Алгоритм «форель»

Существует последовательность действий, характерная для большинства известных процедур алгоритма «Форель»:

1. Случайно-интуитивным способом выбирается точка (объект классификации) в некотором метрическом пространстве.

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

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

4. Все объекты, попавшие в построенную сферу, становятся элементами кластера. Далее выбирается какой-либо новый элемент из сферы, который становится центром новой сферы того же радиуса.

5. Для выбора координат нового центра предпочтительно иметь какой-либо формальный критерий. Одним из логичных критериев может быть минимум расстояния от выбранного объекта до оболочки сферы.

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

7. Кластером в этом алгоритме будут называться все объекты, которые вошли хотя бы в одну из построенных сфер. Очевидно, независимо от количества попаданий объекта в разные сферы в кластере он учитывается только один раз.

В алгоритме «Форель» качество классификации во многом зависит от рациональности выбора объектов - центров сфер и радиуса поиска. Если фазовое пространство метрики имеет три, два или одно измерение, то оценить исходные данные алгоритма можно визуально, а в случае неудачи изменить их. В многомерном пространстве исходные параметры выбираются вслепую, и при неудачах приходится рассматривать все новые и новые варианты, количество которых может быть весьма значительно.