'

Обучение без учителя

Понравилась презентация – покажи это...





Слайд 0

Обучение без учителя Владимир Вежневец, Антон Конушин Александр Вежневец Компьютерное зрение МГУ ВМК, Осень 2006


Слайд 1

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


Слайд 2

Обучение без учителя Пусть, имеется набор наблюдений: Требуется некоторым образом сделать суждения о наблюдаемых данных Трудно придумать более общую постановку, неправда ли?


Слайд 3

Обучение без учителя Кластеризация Разбиение наблюдений на некоторые группы, с максимально близкими наблюдениями внутри групп и максимально далекими между Понижение размерности Понижение размерности наблюдений с сохранением описательной силы Анализ плотности распределения Получить аппроксимацию плотности распределения вероятности наблюдений или поиск их особых точек


Слайд 4

Обучение без учителя Кластеризация К-средних Смесь нормальных распределений … Понижение размерности Метод главных компонент SOM … Анализ плотности распределения Аппроксимация плотности распределения через обучение с учителем Сдвиг среднего для поиска экстремумов плотности распределения …


Слайд 5

Отличие от классификации Множество ответов неизвестно Нет четкой меры качества решений Задачи поставлены крайне нечетко


Слайд 6

Кластеризация Постановка задачи (1) Пусть, имеется набор наблюдений: Требуется разбить на некоторые непересекающиеся подмножества (группы, кластеры), таким образом, что объекты внутри одной группы соотносились сильнее чем объекты из разных групп


Слайд 7

Кластеризация Постановка задачи (2) Пусть, так же, имеется некоторая мера , характеризующая «схожесть» между объектами Тогда, требуется найти некоторое разбиение: Такое, что минимизируется И максимизируется


Слайд 8

Кластеризация Модель кластеров Под моделью кластеров будем понимать некоторое параметрическое семейство отображений из исходного пространства в множество индексов кластеров Множество параметров, пространством поиска Нахождения параметров - кластеризацией


Слайд 9

Алгоритм К-средних Кто хочет рассказать как он работает? Случайным образом выбрать k средних mj j=1,…,k; Для каждого xi i=1,…,p подсчитать расстояние до каждого из mj j=1,…,k, Отнести (приписать) xi к кластеру j’, расстояние до mj’ минимально; Пересчитать средние mj j=1,…,k по всем кластерам; Повторять шаги 2, 3 пока кластеры не перестанут изменяться;


Слайд 10

Иллюстрация


Слайд 11

Алгоритм К-средних Мера схожести Евклидово расстояние в пространстве Х Модель кластеров Пространство поиска - центры масс


Слайд 12

Алгоритм К-средних Однопараметрический Требует знания только о количестве кластеров Рандомизирован Зависит от начального приближения Не учитывает строения самих кластеров


Слайд 13

EM алгоритм Общая идеология Пусть есть вектор неизвестных величин и параметрическая модель с так же неизвестным параметром(ами) Пусть возможно рассчитать правдоподобие Наша задача подобрать такие и , чтобы правдоподобие было максимальным


Слайд 14

EM алгоритм Общая идеология Возьмем некоторые начальные приближения Итеративно t =1… делаем два шага: Expect: согласно текущему значению высчитываем наиболее вероятные значения Maximize: согласно текущем значениям высчитываем новое значение максимизирующее функцию правдоподобия Остановимся когда правдоподобие стабилизируется


Слайд 15

Кластеризация смесью нормальных распределений Будем считать, что наблюдения сгенерированы смесью нормальных распределений, то есть: Пусть k известно заранее, будем осуществлять кластеризацию ЕМ алгоритмом - Индексы кластеров наблюдений


Слайд 16

Кластеризация смесью нормальных распределений Возьмем некоторые (случайные) начальные приближения Итеративно для t =1… : E: согласно текущему значению высчитываем наиболее вероятные значения индексов кластеров для наблюдений из M: согласно текущем значениям индексов пересчитаем параметры распределений (методом максимального правдоподобия)


Слайд 17

Иллюстрация


Слайд 18

Кластеризация смесью нормальных распределений Плюсы Более полная модель кластеров (больше итоговой информации) Более качественная аппроксимация Эффективная оценка качества кластеризации (правдоподобие) Минусы Все равно некоторая ограниченная модель со строгой «геометрией» Чувствительность к размерности и нормализации данных


Слайд 19

Иллюстрация


Слайд 20

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


Слайд 21

Метод главных компонент Пусть имеется набор наблюдений Будем строить новый базис в пространстве , таким образом что: Центр координат совпадает с мат. ожиданием наблюдений (выборочным средним) Первый вектор направлен таким образом, что дисперсия вдоль него была максимальной Каждый последующий вектор ортогонален предыдущим и направлен по направлению максимальной дисперсии


Слайд 22

Метод главных компонент Расчет базиса Сдвинем все данные таким образом, чтобы их выборочное среднее равнялось нулю Рассчитаем ковариационную матрицу: Ковариация двух сл. величин Выборочное среднее


Слайд 23

Метод главных компонент Расчет базиса Векторами нового базиса будут являться собственные вектора ковариационной матрицы Собственные числа – значениями дисперсии наблюдений вдоль них


Слайд 24

Иллюстрация Убирая базисные вектора с малыми значениями мы можем сократить размерность без существенной потери информации *Вопрос: Почему это так?


Слайд 25

Случай нормального распределения Расстояние от центра распределения в новой системе координат равно: Так называемое расстояние Махалонобиса Пропорционально правдоподобию наблюдения


Слайд 26

Метод главных компонент Связь с линейной аппроксимацией Если рассмотреть систему проекций данных на первые главных компонент, то мы получим систему наилучших линейных приближений данных (в смысле среднеквадратичного отклонения)


Слайд 27

Метод главных компонент Следует применять: Данные распределены нормально и требуется привести их к более удобной форме Или предполагается, что данные содержатся в линейном многообразии исходного пространства и требуется выделить лишь его и сократить размерность НЕ следует применять: Распределение данных произвольно и далеко от нормального Данные нелинейные


Слайд 28

Самоорганизующиеся карты SOM (Карты Кохенена) Основная идея вписать в данные сетку низкой размерности, и анализировать ее, вместо самих данных


Слайд 29

SOM (Карты Кохенена) Модель сетки Матрица узлов Соседство - 4 или 8 связность Каждому узлу соответствует точка в исходном пространстве


Слайд 30

SOM (Карты Кохенена) Алгоритм построения Проинициализируем случайными значениями Далее, в случайном порядке будем предъявлять наблюдения и для каждого: Вычисляем ближайший узел Выберем множество соседей узла, такое что расстояние на сетке между ними меньше r Для некоторого множества соседей узла, включая сам узел, изменяем их положения согласно: Повторяем процедуру уменьшая r и пока сеть не стабилизируется


Слайд 31

SOM (Карты Кохенена) Иллюстрация: исходные данные


Слайд 32

SOM (Карты Кохенена) Иллюстрация: сетка


Слайд 33

SOM (Карты Кохенена) Иллюстрация: проекции на матрицу


Слайд 34

SOM (Карты Кохенена) Практическое использование Данные представляют некоторую поверхность, требуется сократить размерность Хорошо подходят для последующей кластеризации Могут работать «online» В случае слишком сложных данных не информативны


Слайд 35

Задание №2 Каждому будут выданы Данные (3 набора) Алгоритмы классификации, реализованные в MatLab Требуется Для каждого из наборов натренировать наилучший возможный классификатор (из выданных вам) Написать отчет (по форме лежащий на сайте) описывающий каким образом вы выбирали классификатор и настроили параметры Оценка складывается из: Аккуратности и полноты отчета Результатов работы Вами присланного классификатора на наших данных (часть выборки мы дали Вам, часть оставили себе)


Слайд 36

Содержание отчета Применявшиеся методы Список Алгоритм, по которому оценивались алгоритмы и выбирались параметры Результаты в виде Графиков Таблиц Выводы (кратко!) Какой классификатор был выбран в итоге Почему именно этот классификатор


Слайд 37

Оформление решения Классификаторы <Номер данных>_<Название метода> Например 23_SVM Отчет Файл в формате MS Word


×

HTML:





Ссылка: