Lecture4_Part1_Clustering


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Анализ данных на практике

Кластеризация

Виктор Кантор

Как могут выглядеть кластеры







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

Простой метод͗
k
-
Means

Подбор числа кластеров͗
BisectKMeans

Более сложный метод
:
EM


ݔ
=

ݓ



ݔ


=
1
,


ݔ
=

(


;
ݔ
)


E
-
шаг͗


g
ji
=


ݔ

=
ݓ



(
ݔ

)

(
ݔ

)


М
-
шаг͗


ݓ

=
1







=
1
















=
�����
ݔ



௝௜
ln

(

;
ݔ
)


=
1

Задача разделения смеси
распределений


ݔ
=

ݓ



ݔ


=
1
,


ݔ
=

(


;
ݔ
)

Задача разделения смеси
распределений


ݔ
=

ݓ



ݔ


=
1
,


ݔ
=

(


;
ݔ
)

ݓ

,

=
�����
ݔ

,


ln

(
ݔ

)


=
1

Выборка из смеси
гауссовских

распределений


ݔ
=
1
2

4
0
,
1
+
1
2

8
0
,
1



,

=
1
2�

2
|

|



1
2








1






аочки сгенерированы из смеси͗

Кластеризация
EM
-
алгоритмом


ݔ
=
ݓ
1

1
ݔ
+
ݓ
2

2
ݔ


E
-
шаг͗

g
ji
=


ݔ

=




(


)

(


)


М
-
шаг͗


ݓ

=
1







=
1





=
1





௜௝
ݔ



=
1


Σ

=
1

ݓ


1


௜௝
(
ݔ




)
(
ݔ




)




=
1

Относим

ݔ


к

кластеру


,
для

которого


больше



ݔ

=

௜௝

Идея
density
-
based
методов

DBSCAN

1:

Пометить все точки, как основные,
пограничные или шумовые
.


2͗ Отбросить

точки

шума
.


3͗ Соединить все основные точки, находящиеся
на расстоянии
Eps

радиуса одна от другой
.


4͗ Объединить

каждую
группу

соединенных

основных

точек

в
отдельный

кластер
.


5͗ Назначить

каждую

пограничную точку

одному
из

кластеров,
ассоциированных
с ней основных
точек͘

Идея иерархической кластеризации


Вводим расстояние на объектах


Пытаемся выстроить «иерархию»
вложенных друг в друга кластеров


Получаем дерево, вершины в котором
кластеры


Дерево можно «обрезать» на какой
-
то
фиксированной глубине и получить нужное
число кластеров͘ Или оставить только
достаточно большие кластеры͘

Аналогия из биологии

Дендрограмм
ы

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

дормула
Ланса
-
Вильямса

Попробуем систематизировать


По структуре кластеров͗


Иерархические


Агломеративные


Дивизионные


Плоские



По форме


Кластеры выпуклой формы


Кластеры
-
ленты


Сгустки на «фоне»


͙



По присвоению объектов к кластерам͗


Жесткая кластеризация


Мягкая кластеризация

Бонусные
слайды

Как проверить наличие кластерной
структуры

1.
Генерируем
p
случайных точек
из равномерного
распределения и
p
случайных
из обучающей выборки

2.
Вычисляем величину
(статистика
еопкинса
):

Анонс
одной из следующих лекций͗
PCA


PDDP
-

Principal Direction Divisive
Partition

Шаг

1:
центрирование данных

Шаг 2
:
делим по знаку проекции на
главную компоненту

Шаг

3:
повторяем для кластера с
наибольшим разбросом

Шаг

N

Повторяем разделения, пока качество
кластеризации увеличивается

DBSCAN:
выбор параметров


Приложенные файлы

  • pdf 15596366
    Размер файла: 978 kB Загрузок: 0

Добавить комментарий