10986

Кластерный анализ

Лекция

Математика и математический анализ

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

Русский

2013-04-03

44.7 KB

31 чел.

Кластерный анализ

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

Кластер - это множество объектов, близких между собой по некоторой мере сходства.

Задача классификации – отнесение объекта к определенной группе.

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

Рис. 1. Наиболее широко распространенные формы скоплений

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

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

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

В классификации без обучения: классификационная схема имеет целью определение естественных популяций на основе параметрических или непараметрических критериев. Примерами классификации без обучения являются: иерархическая классификация и метод ISODATA рис.2.

 а) Объекты до кластеризации

б) Объекты после кластеризации

Рис. 2. Кластеризация объектов

На рис.2а изображено скопление "белых", неклассифицированных точек. Кластеризованные данные (см. рис.2б) окрашены в разные цвета, причем каждый кластер образуют облако точек одного цвета.

Для изучения полученного разбиения объектов на однородные группы применяют математические характеристики кластеров рис. 3.

Рис. 3. Графическая иллюстрация основных характеристик кластера

Центр кластера – это среднее геометрическое место точек в пространстве переменных.

Дисперсия кластера – это мера рассеяния точек в пространстве относительно центра кластера.

Радиус кластера – максимальное расстояние точек от центра кластера.

Методы иерархической классификации

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

Ее цель – почти всегда состоит в упрощении матрицы данных, слишком обширной для непосредственного анализа человеком. Не существует, однако, единственно "правильной" классификации, какого либо набора данных. Различные численные стратегии, как правило, приводят к совершенно разным результатам. Следовательно, необходима помощь специалиста – выбрать тип стратегии.

Итак, исходная информация может быть представлена в форме матрицы  "объект - свойство":

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

Исходная информация, также, может быть задана в форме матрицы  попарно взаимных расстояний (близостей) объектов:

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

Следует помнить: . Требование максимального сходства объекта с самим собой , и монотонное требование: из .

Расстояние между классами и мера близости классов

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

-й кластер.

число объектов образующих кластер.

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

 расстояние между кластерами  и .

Рассмотрим наиболее употребительные и наиболее общие расстояния и меры близости между классами объектов.

Расстояние, измеряемое по принципу "ближнего соседа" (Nearest neighbor):

Расстояние, измеряемое по принципу "дальнего соседа" (Furthest neighbor):

Расстояние, измеряемое по принципу "дальнего соседа" (Furthest neighbor):

Расстояние, измеряемое по "центрам тяжести групп" (Centroid clustering):

Примеры расстояний

Обычное евклидово расстояние:

"Взвешенное" евклидово расстояние:

Определение весов , как правило, связано с дополнительными исследованиями.

Стандартизация.

Непосредственное использование переменных в анализе может привести к тому, что классификацию будут определять переменные, имеющие наибольший разброс значений. Поэтому применяются различные виды стандартизации, одним из которых являются Z-шкалы (Z-Scores). Из значений переменных вычитается их среднее значение, и эти значения делятся на стандартное отклонение. Данная стандартизация приводит все переменные к единому диапазону значений от -3 до +3.

Общий вид метрики махаланобисского типа.

В общем случае зависимых компонент  вектора наблюдений  и их различной значимости в решении задачи классификации пользуются обобщенным ("взвешенным") расстоянием махаланобисского типа:

Здесь ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения ;

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

Хеммингово расстояние.

Это расстояние используется как мера различия объектов, задаваемых дихотомическими признаками:

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

Стратегия объединения (агломеративные системы)

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

Стратегия объединения определяется именно мерой различия между группами.

Рассмотрим комбинаторные решения

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

Параметры  и  определяют сущность стратегии.


 

А также другие работы, которые могут Вас заинтересовать

32498. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ ПО ИНФОРМАТИКЕ 90.5 KB
  Теория и методика обучения информатики УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ ПО ИНФОРМАТИКЕ. Некомпьютерные средства обучения информатике Понятие и дидактические функции технических средств обучения Еще основоположник классноурочной системы обучения Ян Амос Коменский отмечал: . Наиболее высокое качество усвоения достигается при непосредственном сочетании слова учителя и предъявляемого учащимся с помощью технических средств обучения ТСО изображения в процессе передачи учебной информации. Техническими средствами обучения называют проекционную...
32499. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПО КУРСУ ИНФОРМАТИКИ 49.5 KB
  В систему средств обучения наряду с учебниками учебными и методическими материалами и программным обеспечением для компьютеров входят и сами компьютеры образующие единую комплексную среду которая и позволяет учителю достигать поставленных целей обучения. Вот перечень основных компонентов рекомендуемой системы средств обучения информатике в школе: программнометодическое обеспечение курса информатики включающее как программные средства для поддержки преподавания так и инструментальные программные средства ИПС обеспечивающие учителю...
32500. ОСНОВНЫЕ ФОРМЫ ОРГАНИЗАЦИИ ОБУЧЕНИЯ ИНФОРМАТИКЕ В СРЕДНЕЙ ШКОЛЕ 68 KB
  Все это приемлемо и на уроках по информатике. Применение ИКТ может существенно изменять характер школьного урока что делает еще более актуальным поиск новых организационных форм обучения которые должны наилучшим образом обеспечивать образовательный и воспитательный процесс. Главный признак урока это его дидактическая цель показывающая к чему должен стремиться учитель. Цель  тип урока  содержание урока  методы  форму познавательной деятельности учащихся  результат Основные типы уроков: урок формирования знаний; урок закрепления...
32501. МЕТОДЫ И ПРИЕМЫ ФОРМИРОВАНИЯ СИСТЕМНО-НАУЧНЫХ ПОНЯТИЙ НА УРОКАХ ИНФОРМАТИКИ И ВО ВНЕУРОЧНОЕ ВРЕМЯ 48 KB
  Теория и методика обучения информатики МЕТОДЫ И ПРИЕМЫ ФОРМИРОВАНИЯ СИСТЕМНОНАУЧНЫХ ПОНЯТИЙ НА УРОКАХ ИНФОРМАТИКИ И ВО ВНЕУРОЧНОЕ ВРЕМЯ. Методы и приемы формирования системноинформационных понятий на уроках информатики и во внеурочной работе со школьниками Философские аспекты современного школьного курса информатики Проблема существования и бытия человека в полностью технизированном и информатизированном мире не могла не занимать философов что вызвало к жизни концепцию информационного общества. Пропедевтика методов системного анализа...
32502. ОБЩИЕ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПРИ ИЗУЧЕНИИ ИНФОРМАТИКИ, МЕТОДЫ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ 84.5 KB
  Теория и методика обучения информатики ОБЩИЕ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПРИ ИЗУЧЕНИИ ИНФОРМАТИКИ МЕТОДЫ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ. Общие методические рекомендации и принципы обучения информатике. Принцип освоения методики самообучения. Методы обучения с использованием ИКТ Методы обучения система взаимодействия преподавателя и обучаемого с использованием ИКТ обеспечивающая усвоение образовательной программы.
32503. ОРГАНИЗАЦИЯ ПРОВЕРКИ И ОЦЕНКИ РЕЗУЛЬТАТОВ ОБУЧЕНИЯ. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМЫ И ХАРАКТЕРИСТИКА МЕТОДОВ КОНТРОЛЯ. ОСНОВНЫЕ ФОРМЫ КОНТРОЛЯ. МОДЕЛЬ НЕПРЕРЫВНОГО КОНТРОЛЯ. ШКАЛЫ ОЦЕНОК 92.5 KB
  ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМЫ И ХАРАКТЕРИСТИКА МЕТОДОВ КОНТРОЛЯ. ОСНОВНЫЕ ФОРМЫ КОНТРОЛЯ. МОДЕЛЬ НЕПРЕРЫВНОГО КОНТРОЛЯ. В ходе контроля оценивается степень и уровень обученности.
32504. ПРЕПОДАВАНИЕ ПРОПЕДЕВТИЧЕСКОГО КУРСА ИНФОРМАТИКИ В НАЧАЛЬНЫХ КЛАССАХ СРЕДНИХ УЧЕБНЫХ ЗАВЕДЕНИЙ 58 KB
  Целью курса информатики в начальной школе является формирование первоначальных базовых понятий информатики что обеспечит дальнейшее создание информационной картины мира представлений о свойствах информации способах работы с ней формирование представления о компьютере как универсальной информационной машине развитие информационной культуры ребенка и интеллектуальных способностей учащихся. В соответствии с целями обучения информатике в начальной школе выделяется ряд задач на которые нужно опираться при проведении уроков информатики в...
32505. ПРЕПОДАВАНИЕ БАЗОВОГО КУРСА ИНФОРМАТИКИ В СРЕДНИХ УЧЕБНЫХ ЗАВЕДЕНИЯХ 47 KB
  Среди них: теория информации теория алгоритмов теоретическая кибернетика математическое и информационное моделирование дискретная математика искусственный интеллект и др. К аппаратным средствам относятся компьютеры технические средства хранения и отображения информации передачи данных по сетям. Она заключается в формировании представлений об информации информационных процессах как одного из трех основополагающих понятий: вещества энергии информации на основе которых строится современная научная картина мира. В этом отношении...
32506. МЕТОДИКА ИЗУЧЕНИЯ СОДЕРЖАТЕЛЬНОЙ ЛИНИИ: «ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ». 83 KB
  Ключевыми вопросами данной содержательной линии являются: определение информации; измерение информации; хранение информации; передача информации; обработка информации. Проблемы определения и измерения информации Нельзя дать единого универсального определения информации. Но в науке и в практике известны различные подходы к информации и в рамках каждого из них дается определение этого понятия Субъективный подход. При раскрытии понятия информация с точки зрения субъективного бытового человеческого подхода следует отталкиваться...