VI Международная студенческая научная конференция Студенческий научный форум - 2014

 

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

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

Типы входных данных

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

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

• Матрица сходства между объектами. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется Q-типом анализа, а в случае сравнения признаков, на основе объектов — R-типом анализа. Существуют попытки использования гибридных типов анализа (например, RQ-анализ), но данная методология ещё должным образом не разработана.

Цели кластеризации

• Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).

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

• Обнаружение новизны (англ. novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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

Формальная постановка задачи кластеризации

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

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

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

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин (как считает ряд авторов):

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

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

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

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

Для проведения кластерного анализа выбран метод кластеризации Уорда, метрика – квадратичная евклидова. Результаты кластерного анализа представлены на рис. 1-3 и табл. 1-4.

Рис. 1. Дендрограмма результатов проведения кластерного анализа. Метрика – квадратичная Евклидова

Таблица 1

Результаты проведения кластерного анализа, метрика – квадратичная Евклидова, 5 кластеров

Таблица 2

Распределение элементов по кластерам

Рис. 2. График расположения кластеров на плоскости «Сдержанность» - «неуверенность»

Таблица 3

Результаты проведения кластерного анализа, метрика – Евклидова, 5 кластеров

Таблица 4

Распределение элементов по кластерам

Рис. 3. Дендрограмма результатов проведения кластерного анализа. Метрика – Евклидова

Вывод

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

Кластерный анализ выявил 5 групп качеств со сходными оценками показателей, в каждой группе от 5 до 10 качеств.

По полученным данным можно заключить, что в первый кластер попадают студенты, имеющие низкие значения признака H (сдержанность), средними значениями остальных признаков, 2 кластер – с высоким значением M (практичность) и низким значением признака N (простота, легкость в общении). 3 кластер – c низким N и высоким L (доверчивость). В 5 кластер попали студенты с высоким значением эмоциональной чувствительности (I), остальные студенты без ярко выраженных значений признаков попали в 4 кластер.

Код для цитирования: Скопировать