10986

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

Лекция

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

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

Русский

2013-04-03

44.7 KB

27 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-й кластер.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

35147. Информационные системы. Общие сведения 10.58 MB
  К средствам извлечения информации относятся: штатные средства ручного ввода клавиатура мышь; средства автоматизированного ввода с твердых копий сканеры; специализированные средства ручного ввода дигитайзеры световые перья сенсорные экраны; средства ввода речевой информации; средства ввода данных с аппаратуры датчики измерительные устройства аппаратура связи. Это программное обеспечение может быть как достаточно простым и предполагать только передачу операционной системе данных от аппаратных компонентов так и сложным...
35148. редства удалённого выполнения заданий в Windows 38 KB
  Планировщик заданий Windows осуществляет настройку как для локального компьютера так и для удаленной системы. На удаленных системах эта возможность обеспечивается совместной работой нескольких служб и программ: Планировщик заданий это стандартная служба Windows управляющая планировщиком заданий. Создание заданий на локальном компьютере осуществляется через: ПускВсе программыСтандартныеНазначенные задания Создание заданий на удаленном компьютере осуществляется через: Сетевое окружениеОтобразить компьютеры рабочей группывыбираем...
35149. Средства удалённого доступа к сети в Windows 40 KB
  в ОС Windows XP имеются встроенные инструменты для организации таких подключений : Remote Desktop Удаленный рабочий стол Remote ssistnce Удаленный помощник. Remote ssistnce Remote ssistnce позволяет пригласить другого пользователя друга знакомого специалиста для оказания помощи. При этом приглашенный участник в отличие от использования Remote Desktop может наблюдать за действиями пользователя. При этом Remote ssistnt самостоятельно управляет настройками соединения подстраивая объем передаваемых данных под возможности канала...
35150. Виртуальные частные сети. Архитектура и протоколы 42.5 KB
  VPN англ. В зависимости от применяемых протоколов и назначения VPN может обеспечивать соединения трёх видов: узелузел узелсеть и сетьсеть. Уровни реализации Обычно VPN развёртывают на уровнях не выше сетевого так как применение криптографии на этих уровнях позволяет использовать в неизменном виде транспортные протоколы такие как TCP UDP. Пользователи Microsoft Windows обозначают термином VPN одну из реализаций виртуальной сети PPTP причём используемую зачастую не для создания частных сетей.
35151. Методы повышения надёжности хранения данных. Технология RAID 50.5 KB
  Технология RID Одна из причин ведущих к утрате информации аппаратные сбои и поломки. RID это акроним от Redundnt rry of Independent Disks. Этим набором устройств управляет специальный RIDконтроллер контроллер массива который инкапсулирует в себе функции размещения данных по массиву; а для всей остальной системы позволяет представлять весь массив как одно логическое устройство ввода вывода. В зависимости от уровня RID проводится или зеркалирование или распределение данных по дискам.
35152. Цели и задачи администрирования 25 KB
  чтобы предоставить пользователям ИС наилучшее возможности по эффективному использованию ресурсов ИС при объективных ограничениях. 3 квалифицируемая помощь пользователям. Здесь задача состоит в том чтобы реализовать в ИС выбранную стратегию ИБ на базе 1 или нескольких политик безопасности обеспечить использование ИС только санкционированным пользователям предусмотреть резервное копирование и восстановления отдельных ресурсов или всей ИС.
35153. Сетевое администрирование. Основные понятия. Сетевые ОС 26.5 KB
  Компьютерные сети – это совокупность компьютеров связанных коммуникационной системой необходимым программным обеспечением позволяющей пользователям и приложениям получить доступ к ресурсам компьютеров сети. клиентская часть средство запроса на доступ к удаленным серверам транспортные средства сетевой ОС обеспечивающие передачу доступных между компьютерами Среди компонентов сети выделяют сетевые службы – это программные модули работающие в установленном режиме которые предоставляют доступ к конкретным ресурсам компа через сеть....
35154. Модели управления доступом к ресурсам 27 KB
  Основными компонентами ролевой модели разрешения права пользователя Разрешение – определяет тип доступа к объекту или его свойству дается пользователям или группам . разрешения применяются к защищенным объектам Рекомендуется назначать разрешения группам. Существуют группы разрешений которые являются основными или обязательными чтение разрешения смена разрешения смена владельца удаление разрешения Существует специальный вид разрешения – владения которое назначается при создании объектов. Какие бы разрешения не были установлены для...
35155. Администрирование сетей Microsoft. Средства анализа состояния сети в Windows 29 KB
  Средства анализа состояния сети в Windows. Базовые принципы: 1 необходимо иметь точную схему и документацию сети: текущая топологическая схема подробная информация обо всем его сетевом оборудовании его конфигурации и использующихся протоколах IPадресах каналах связи WU сервера и сегментах пользовательских локальных сетей. 2 перед изменениями в сети а так же после этих изменений необходимо оценивать работу в сети для того чтобы делать выводы об отрицательном или положительном влиянии внешних изменений . В Windows отдается приоритет...