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

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

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

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

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

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

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

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

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

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

Иллюстрация

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

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

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

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

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

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

Иллюстрация

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

Иллюстрация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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