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

Лекция 3.1 Кластерный анализ ТЕХНОЛОГИИ ОБРАБОТКИ ИНФОРМАЦИИ к.т.н., доцент Буряченко Владимир Викторович Красноярск, 2019 Содержание лекции 2  Понятие классификации объектов.  Понятие кластерного анализа.  Кластеризация.  Матрица близости объектов.  Метрики расстояния между объектами.  Пример классификации объектов.  Дендрограмма наблюдений. Кластерный анализ 3 Кластерный анализ позволяет определить принадлежность объектов к некоторым группам, поделить их на классы по определенным критериям.  Синонимами термина "кластерный анализ" являются "автоматическая классификация объектов без учителя" и "таксономия".  Кластер - это множество объектов, близких между собой по некоторой мере сходства. Классификация объектов 4  Задача классификации – отнесение объекта к определенной группе. Если данные понимать как точки в признаковом (многомерном) пространстве, то задача кластерного анализа формулируется как выделение "сгущений точек", разбиение совокупности на однородные подмножества объектов. Наиболее широко распространенные формы скоплений Понятие кластеризации 5  Кластеризация - это процесс разбиения множества объектов на кластеры (группы объектов, близких по мере сходства). Методы кластеризации делятся на две группы: классификация с обучением и классификация без обучения.  Классификация с обучением означает, что категории установлены до отнесения объектов к классам.  В классификации без обучения классификационная схема имеет целью определение естественных популяций на основе параметрических или непараметрических критериев. Понятие кластеризации 6 а) Объекты до кластеризации б) Объекты после кластеризации Характеристики кластера 7  Для изучения полученного разбиения объектов на однородные группы применяют характеристики кластеров: математические Характеристики кластера 8  Центр кластера – это среднее геометрическое место точек в пространстве переменных.  Дисперсия кластера – это мера рассеяния точек в пространстве относительно центра кластера.  Радиус кластера – максимальное расстояние точек от центра кластера. Методы иерархической классификации 9  Численная классификация или численная таксономия не занимается распределением объектов по известным классам, а устанавливает классификацию либо не существующую ранее, либо если это желательно, игнорирующую предшествующие работы и пересматривающую данные заново.  Ее цель почти всегда состоит в упрощении матрицы данных, слишком обширной для непосредственного анализа человеком.  Различные численные стратегии, как правило, приводят к совершенно разным результатам. Следовательно, необходима помощь специалиста при выборе типа стратегии. Иерархическая классификация 10  Исходная информация может быть представлена в форме матрицы "объект - свойство": (1) (1) (1) 𝑥1 𝑥2 ⋯ 𝑥𝑛 ⋯ ⋯ 𝑋= ⋯ (3.1) ⋯ . (𝑝) (𝑝) 𝑥1 ⋯ ⋯ 𝑥𝑛  Здесь X(i)j значение j-го признака на i-м статистически обследованном объекте. 𝑋𝑖 =  характеризует (1) (2) (𝑝) 𝑥𝑖 , 𝑥𝑖 , ⋯ , 𝑥𝑖 ′ объект Oi ,т.е. представляет результат его статистического обследования по всем анализируемым параметрам (переменным). Матрица близости объектов 11  Исходная информация, также, может быть задана в форме матрицы попарно взаимных расстояний (мер близости) объектов: 𝜌11 𝜌= ⋯ 𝜌𝑛1 𝜌12 ⋯ ⋯ ⋯ ⋯ ⋯ 𝜌1𝑛 ⋯ . 𝜌𝑛𝑛 (3.2)  Здесь pij характеризует взаимную отдаленность или близость объектов Oi и Oj. Расстояние между классами и мера близости классов 12  При кластеризации целесообразно ввести понятие расстояния между целыми группами объектов, так же, как и меру близости двух групп объектов. .  Si – i-й кластер.  nj – число объектов образующих Si кластер.  𝑋 𝑖 − среднее арифметическое векторных наблюдений, т.е. 𝑋 𝑖 − центр тяжести i-го кластера.  p(Si, Sm) – расстояние между кластерами Si и Sm. Расстояние между классами и мера близости классов 13  Расстояние, измеряемое по (Nearest neighbor): 𝜌𝑚𝑖𝑛 𝑆𝑙 , 𝑆𝑚 = min принципу 𝑋𝑖 ∈𝑆𝑙 ; 𝑋𝑗 ∈𝑆𝑚  Расстояние, измеряемое по (Furthest neighbor): 𝜌𝑚𝑎𝑥 𝑆𝑙 , 𝑆𝑚 = max 𝑋𝑖 ∈𝑆𝑙 ; 𝑋𝑗 ∈𝑆𝑚 𝑑(𝑋𝑖 , 𝑋𝑗 ) принципу 𝑑(𝑋𝑖 , 𝑋𝑗 ) "ближнего соседа" (3.3) "дальнего соседа" (3.4)  Расстояние, измеряемое по "центрам тяжести групп" (Centroid clustering): 𝜌 𝑆𝑙 , 𝑆𝑚 = 𝑑 𝑋 𝑙 , 𝑋 𝑚 (3.5) Расстояние между классами и мера близости классов 14 Примеры расстояний:  Обычное евклидово расстояние: 𝑑𝐸 𝑋𝑖 , 𝑋𝑗 = (1) 𝑋𝑖 − (1) 2 𝑋𝑗 + (2) 𝑋𝑖 − (2) 2 𝑋𝑗 + ⋯+ (𝑝) 𝑋𝑖 − (𝑝) 2 𝑋𝑗 (3.6)  "Взвешенное" евклидово расстояние: 𝑑𝐸 𝑋𝑖 , 𝑋𝑗 = = ⋯+ (1) 𝜔1 𝑋𝑖 (𝑝) 𝜔𝜌 𝑋𝑖 − − (1) 2 𝑋𝑗 (𝑝) 2 𝑋𝑗 . + (2) 𝜔2 𝑋𝑖 − (2) 2 𝑋𝑗 +⋯ = (3.7)  Определение весов 𝜔𝑖 , как правило, связано с дополнительными исследованиями. Стандартизация переменных 15  Непосредственное использование переменных в анализе может привести к тому, что классификацию будут определять переменные, имеющие наибольший разброс значений.  Поэтому применяются различные виды стандартизации, одним из которых являются Z-шкалы (Z-Scores). Из значений переменных вычитается их среднее значение, и эти значения делятся на стандартное отклонение. Метрика Махаланобиса 16  В общем случае зависимых компонент 𝑥 (1) , 𝑥 (2) , ⋯ , 𝑥 (𝑝) вектора наблюдений 𝑋 и их различной значимости в решении задачи классификации пользуются обобщенным ("взвешенным") расстоянием махаланобисского типа: 𝑑0 𝑋𝑖 , 𝑋𝑗 = ′ 𝑋𝑖 − 𝑋𝑗 ⋀′ ∑−1 ⋀ 𝑋𝑖 − 𝑋𝑗 (3.8)  Здесь ∑ −ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения 𝑋𝑖 ;  ⋀ − некоторая симметричная неотрицательно определенная матрица "весовых" коэффициентов 𝜆𝑚𝑞 , которая чаще всего выбирается диагональной. Хеммингово расстояние 17  Используется как мера различия дихотомическими признаками: объектов, задаваемых 𝑝 𝑑𝐻 𝑋𝑖 , 𝑋𝑗 = 𝑋𝑖 𝑆 − 𝑋𝑗 𝑆 . (3.9) 𝑆=1  Следовательно, это расстояние равно числу 𝜈𝑖𝑗 несовпадений значений соответствующих признаков в рассматриваемых 𝑖–м и 𝑗– м объектах. Стратегия объединения 18  Для всех систем вычисляются все 𝑛(𝑛 − 1)/2 мер различия и пара индивидов с наименьшей мерой объединяется в одну группу.  Далее необходимо определить подходящую меру различия между этой группой и остальными 𝑛 − 2 индивидами.  Стратегия объединения определяется именно мерой различия между группами. Комбинаторные решения 19  Пусть первоначально задана матрица различий (расстояний). Имеются две группы 𝑖 и 𝑗 с 𝑛𝑖 и 𝑛𝑗 элементами соответственно. Мера различия между этими группами обозначается 𝑑𝑖𝑗 и пусть это минимальная мера из всех оставшихся.  Обозначим новую группу через 𝑘 ⇒ 𝑛𝑘 = 𝑛𝑖 + 𝑛𝑗 элементов. группе ℎ ⇒ 𝑛ℎ элементов. Перед объединением известны следующие значения: 𝑑ℎ𝑖 , 𝑑ℎ𝑗 , 𝑑𝑖𝑗 , 𝑛ℎ , 𝑛𝑗 , 𝑛𝑖 . Тогда:  В 𝑑ℎ𝑘 = 𝛼𝑖 𝑑ℎ𝑖 + 𝛼𝑗 𝑑ℎ𝑗 + 𝛽𝑑𝑖𝑗 + 𝛾 𝑑ℎ𝑖 − 𝑑ℎ𝑗 𝛼𝑖 , 𝛼𝑗 , 𝛽 и классификации.  Параметры 𝛾 − определяют (3.10) сущность стратегии Монотонность. Определение стратегии классификации 20  Для графического представления процесса объединения все индивиды размещаются в соответствующем порядке на оси абсцисс. Множество стратегий объединения:  стратегия "ближнего соседа" 𝛼𝑖 = 𝛼𝑗 = 1 2 , 𝛽 = 0, 𝛾 = −1/2.  Это монотонная стратегия, сильно сжимающая пространство.  стратегия " дальнего соседа"  𝛼𝑖 = 𝛼𝑗 = 1 2 , 𝛽 = 0, 𝛾 = 1/2. монотонная сильно растягивающая стратегия  гибкая стратегия: 𝛼𝑖 + 𝛼𝑗 + 𝛽 = 1, 𝛼𝑖 = 𝛼𝑗 ,  𝛽 < 1, 𝛾 = 0. применима для любой меры различия и определяется четырьмя ограничениями. Пример классификации объектов 21  Имеются 5 объектов, для которых заданы меры различия 𝑑𝑖𝑗 , образующие матрицу 𝐷: 1 2 3 4 5 1 - 0.227 0.250 0.422 0.897 2 0.227 - 0.492 0.387 0.917 3 0.250 0.492 - 0.356 1.000 4 0.422 0.387 0.356 - 0.773 5 0.897 0.917 1.000 0.773 -  Шаг 1. Вычисление минимального значения Dij min 𝐷 = 𝑑12 = 0.227 Пример классификации объектов 22  Т.к. min 𝐷 = 𝑑12 = 0.227, то объекты 1 и 2 объединяются в группу 6. Затем вычислим 𝑑36 , 𝑑46 , 𝑑56 . Для вычисления воспользуемся гибкой стратегией: 𝛽 = −0.25; 𝛼𝑖 = 𝛼𝑗 = 0.625; 𝛾 = 0.  Согласно (3.10) запишем: 𝑑𝑛𝑘 = 𝛼𝑖 𝑑𝑛𝑖 + 𝛼𝑗 𝑑𝑛𝑗 + 𝛽𝑑𝑖𝑗 ; 𝑖 𝑗 ⇒ 𝑘. В результате вычислений получим:  𝒅𝟑𝟔 =0,625*0,250+0,625*0,492-0,25*0,227=0,407 (i=1, j=2, n=3, k=6)  𝑑36 = 0.407, 𝑑46 = 0.449, 𝑑56 = 1.077. 6 3 4 5 6 - 0.407 0.449 1.077 3 0.407 - 0.356 1.000 4 0.449 0.356 - 0.773 5 1.077 1.000 0.773 - Пример классификации объектов 23 𝐦𝐢𝐧 𝐃 = 𝐝34 = 0.356, т.е. на втором шаге объединим группы 3 и 4, новую группу обозначим номером 7.  Шаг 2. 6 3 4 5 6 - 0.407 0.449 1.077 3 0.407 - 0.356 1.000 4 0.449 0.356 - 0.773 5 1.077 1.000 0.773 -  d57=𝛼𝑖 𝑑54 + 𝛼𝑗 𝑑53 + 𝛽𝑑34 = 0,625 ∗ 0,773 + 0,625 ∗ 0,1 − 0,25 ∗ 0,356  d67=𝛼𝑖 𝑑64 + 𝛼𝑗 𝑑63 + 𝛽𝑑34 = 0,625 ∗ 0,449 + 0,625 ∗ 0,407 − 0,25 ∗ 0,356 6 7 5 6 - 0,446 1.077 7 0,446 - 0,456625 5 1.077 0,456625 - Пример классификации объектов 24 Т.к. 𝐦𝐢𝐧 𝐃 = 𝐝67 = 0.446, то на третьем шаге объединяем группы 6 и 7, новую группу обозначим номером 8.  Шаг 3. 6 7 5 6 - 0,446 1.077 7 0,446 - 0,456625 5 1.077 0,456625 -  d58=𝛼𝑖 𝑑56 + 𝛼𝑗 𝑑57 + 𝛽𝑑67 = 0,625 ∗ 1,077 + 0,625 ∗ 0,456625 − 0,25 ∗ 0,446 8 8 5 0,847016  Шаг 4. 5 0,847016 - На последнем шаге объединяем оставшиеся две группы на уровне 𝐝58 = 0,847. Новую группу обозначим номером 9 Дендрограмма наблюдений 25 9 Уровень объединения 0,6 0,4 8 7 6 0.2 1 2 3 Кластеры 4 5 Дендрограмма наблюдений 26 9 Уровень объединения 0,6 0,4 7 6 0.2 2 2 3 4 5 1 - 0.227 0.250 0.422 0.897 2 0.227 - 0.492 0.387 0.917 3 0.250 0.492 - 0.356 1.000 4 0.422 0.387 0.356 - 0.773 5 0.897 0.917 1.000 0.773 - Матрица близости объектов 8 1 1 3 Кластеры 4 Дендрограмма наблюдений 5