Определение предпочтительного числа кластеров. Момент остановки метода одиночной связи | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 22 августа, печатный экземпляр отправим 9 сентября.

Опубликовать статью в журнале

Библиографическое описание:

Мелков, Н. А. Определение предпочтительного числа кластеров. Момент остановки метода одиночной связи / Н. А. Мелков, М. А. Ржавитина, А. С. Пак, А. Ю. Спиридонов. — Текст : непосредственный // Молодой ученый. — 2020. — № 27 (317). — С. 16-18. — URL: https://moluch.ru/archive/317/72327/ (дата обращения: 08.08.2020).



Кластерный анализ является одним из основных методов предварительной классификации большого количества информации. Актуальной задачей остаётся определение момента остановки процесса кластеризации. Можно рассмотреть кластерный анализ данных методом «одиночной связи» в виде дискретного случайного процесса и определить момент остановки с помощью квадратичных форм погрешности приближения «минимальных расстояний» функцией. В статье даётся определение «аппроксимационно-оценочным критериям». Применён один из критериев для кластеризации множества из 33 точек.

Ключевые слова: кластер, метод одиночной связи, аппроксимация, квадратичная форма, кластерный анализ.

Метод одиночной связи

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

Итерации алгоритма можно описать следующим образом: на первом шаге необходимо определить расстояния между всеми n кластерами, построить множество минимальных расстояний, затем найти минимальное. Два кластера, расстояние между которыми минимально, объединяются, их центроида перевычисляется, получаем n-1 кластер [2]. Без остановки алгоритм в конечном итоге объединит все точки в один кластер, что является неудовлетворительным результатом.

Остановка процесса кластеризации

Множество минимальных расстояний является монотонно неубывающим, и при объединении больших кластеров испытывает «скачок». Например, для множества из 33 точек [2]

X={(0; 0); (2; 4); (3; 3); (1; 2); (3; 0); (3; 1); (1; 1); (12; 18); (13; 17); (11; 15); (13; 14); (14; 16); (11; 16); (12; 15); (13; 18); (12; 5); (13; 2); (14; 4); (12; 3); (13; 1); (14; 2); (24; 19); (22; 22); (21; 24); (23; 21); (24; 20); (22; 39); (23; 38); (24; 39); (21; 37); (2; 26); (24; 6); (10; 36)} график множества минимальных расстояний указан на рис.1.

Множество минимальных расстояний. На оси абсцисс указаны номера итераций, на оси ординат — расстояние между кластерами Множество минимальных расстояний. На оси абсцисс указаны номера итераций, на оси ординат — расстояние между кластерами

Рис. 1. Множество минимальных расстояний. На оси абсцисс указаны номера итераций, на оси ординат — расстояние между кластерами

Для того чтобы избежать проблемы объединения точек в один большой кластер, необходимо ввести критерий остановки. Будем приближать множество минимальных расстояний функцией для того, чтобы зафиксировать скачок (объединение кластеров). Хорошие результаты даёт приближение не всех точек сразу, а последовательно по 3 или 4 точкам. «Аппроксимационно-оценочные критерии» [1] являются квадратичными формами, оценивающими разность между квадратичной погрешностью линейной аппроксимации и квадратичной погрешностью одного из видов нелинейной аппроксимации (например, биквадратной — четвёртой степени). С вычислением критериев можно ознакомиться в работе [1]. Биквадратный аппроксимационно-оценочный критерий по четырём точкам имеет вид:

Здесь три переменные, но точек четыре. Это связано с введением упрощения: — первая точка, по которой проводится аппроксимация, — вторая, — третья, — четвёртая; мы обнуляем первую точку и от значений остальных отнимаем — по сути, мы переносим начало координат в . Подставляем вычисленные минимальные расстояния и считаем квадратичную форму — получаем число. Если это число больше нуля, то процесс кластеризации следует остановить, если меньше нуля — то следует продолжить. Данная квадратичная форма — разность погрешности аппроксимации линейной и биквадратной функциями по четырём точкам, и если линейная точнее, то вычисленное значение будет отрицательным. Это означает отсутствие скачка. Если приближение биквадратной функцией точнее, то функция испытывает скачок, и значение становится положительным. [1]

Результаты использования

Чувствительность критерия можно задать с помощью коэффициента q при линейном преобразовании , где i — номер итерации, — значение минимального расстояния на i итерации, q — чувствительность критерия.

Для рассмотренного множества Х данный способ показывает хорошие результаты — при q от 0.18 до 0.63 процесс кластеризации методом одиночной связи заканчивается после 25 итерации (рис.2)

Множество Х, разбитое на кластеры, после 25 итерации. Начало координат находится в левом верхнем углу

Рис. 2. Множество Х, разбитое на кластеры, после 25 итерации. Начало координат находится в левом верхнем углу

Выводы

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

Литература:

  1. Орехов А. В. Аппроксимационно-оценочные критерии напряженно-деформируемого состояния твердого тела // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018. Т. 14. Вып. 3. С. 230–242. https://doi.org/10.21638/11702/spbu10.2018.304
  2. Орехов А. В. Марковский момент остановки агломеративного процесса кластеризации в евклидовом пространстве // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019. Т. 15. Вып. 1. С. 00–00.
Основные термины (генерируются автоматически): одиночная связь, кластер, квадратичная форма, расстояние, кластерный анализ, квадратичная погрешность, биквадратная функция, чувствительность критерия, расстояние функцией, множество.


Ключевые слова

аппроксимация, кластер, кластерный анализ, метод одиночной связи, квадратичная форма

Похожие статьи

Поэтапный процесс кластерного анализа данных на основе...

Имеется выборка и функция, отображающая расстояние между объектами Алгоритм кластеризации — это функция которая всем

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

Аппроксимация полиномов n степени методом наименьших...

Вданной статье рассмотрено решение проблемы уменьшения суммы квадратов отклонений определённых функций от искомых переменных для полиномиальных уравнений n степени. Приведено подробное решение для уравнений 2 степени, рассматриваемой проблемы.

Применение методов кластеризации для обработки новостного...

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

Кластерный анализ разработки современных алгоритмов... Еще одно достоинство – это огромное количество

Кластер-кластерная агрегация. С тех пор как была реализована...

Решение задачи настройки функции принадлежности методом...

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

Методика определения функций принадлежности для...

Во множество параметров системы может также входить количество функций

Рис. 1. Нечеткая система интерполирует расстояние между заданными значениями (в данном случае

Однако в зависимости от выбора формы функций принадлежности, а также методов...

О непараметрическом оценивании взаимно неоднозначных...

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

Сравнение трехмерных объектов. Критерии оценки сходства

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

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

Спектр и квадратичный числовой образ обобщенной модели...

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

здесь ; фиксированные вещественные числа, вещественнозначная непрерывная функция на

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

Метод k средних при решении задачи распознавания диктора по...

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

Исследование статической устойчивости Навоийской ТЭС...

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

Для положительной определенности квадратичной формы (11) согласно критерию Сильвестера (см. [9]) необходимо и достаточно...

Похожие статьи

Поэтапный процесс кластерного анализа данных на основе...

Имеется выборка и функция, отображающая расстояние между объектами Алгоритм кластеризации — это функция которая всем

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

Аппроксимация полиномов n степени методом наименьших...

Вданной статье рассмотрено решение проблемы уменьшения суммы квадратов отклонений определённых функций от искомых переменных для полиномиальных уравнений n степени. Приведено подробное решение для уравнений 2 степени, рассматриваемой проблемы.

Применение методов кластеризации для обработки новостного...

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

Кластерный анализ разработки современных алгоритмов... Еще одно достоинство – это огромное количество

Кластер-кластерная агрегация. С тех пор как была реализована...

Решение задачи настройки функции принадлежности методом...

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

Методика определения функций принадлежности для...

Во множество параметров системы может также входить количество функций

Рис. 1. Нечеткая система интерполирует расстояние между заданными значениями (в данном случае

Однако в зависимости от выбора формы функций принадлежности, а также методов...

О непараметрическом оценивании взаимно неоднозначных...

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

Сравнение трехмерных объектов. Критерии оценки сходства

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

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

Спектр и квадратичный числовой образ обобщенной модели...

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

здесь ; фиксированные вещественные числа, вещественнозначная непрерывная функция на

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

Метод k средних при решении задачи распознавания диктора по...

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

Исследование статической устойчивости Навоийской ТЭС...

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

Для положительной определенности квадратичной формы (11) согласно критерию Сильвестера (см. [9]) необходимо и достаточно...

Задать вопрос