7) Кластерный анализ. Общая теория графов.

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

«Тематика исследований варьирует от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США

Для проведения классификации необходимо ввести понятие сходства объектов по наблюдаемым переменным. В каждый кластер (класс, таксон) должны попасть объекты, имеющие сходные характеристики.

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

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

• K-средних (выбор эталона)

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

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

• Алгоритмы семейства FOREL

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

  1. Метол дедрограмм

  2. Метод полных связей

  3. Метод средней связи

  4. Метод Уорда

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

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

• Алгоритмы семейства КRAB

• EM-алгоритм

• Алгоритм, основанный на методе просеивания

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Граф с 6 гранями и 7 ребрами

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