Не так давно получил распространение термин «большие данные», обозначивший новую прикладную область — поиск способов автоматического быстрого анализа огромных объёмов разнородной информации. Наука о больших данных ещё только оформляется, но уже сейчас она очень востребована — и в будущем будет востребована только больше. С её помощью можно решать невероятные задачи: оценивать состояние печени по кардиограмме, предсказывать зарплату по описанию вакансии, предлагать пользователю музыку на основании его анкеты в интернете. Большими данными может оказаться что угодно: результаты научных экспериментов, логи банковских транзакций, метеорологические наблюдения, профили в социальных сетях — словом, всё, что может быть полезно проанализировать. Самым перспективным подходом к анализу больших данных считается применение машинного обучения — набора методов, благодаря которым компьютер может находить в массивах изначально неизвестные взаимосвязи и закономерности. На факультете компьютерных наук ВШЭ и в Школе анализа данных есть люди, активно использующие машинное обучение и разрабатывающие новые подходы к нему. Именно они — преподаватели этого курса. Вы изучите основные типы задач, решаемых с помощью машинного обучения — в основном речь пойдёт о классификации, регрессии и кластеризации. Узнаете об основных методах машинного обучения и их особенностях, научитесь оценивать качество моделей — и решать, подходит ли модель для решения конкретной задачи. Наконец, познакомитесь с современными библиотеками, в которых реализованы обсуждаемые модели и методы оценки их качества. Для работы мы будем использовать реальные данные из реальных задач. Краткая программа курса: Неделя 1. Введение. Примеры задач. Логические методы: решающие деревья и решающие леса. Неделя 2. Метрические методы классификации. Линейные методы, стохастический градиент. Неделя 3. Метод опорных векторов (SVM). Логистическая регрессия. Метрики качества классификации. Неделя 4. Линейная регрессия. Понижение размерности, метод главных компонент. Неделя 5. Композиции алгоритмов, градиентный бустинг. Нейронные сети. Неделя 6. Кластеризация и визуализация. Частичное обучение. Неделя 7. Прикладные задачи анализа данных: постановки и методы решения. Слушателю нужно знать об основных понятиях математики: функциях, производных, векторах, матрицах. Для выполнения практических заданий потребуются базовые навыки программирования. Очень желательно знать Python. Задания рассчитаны на использование этого языка и его библиотек numpy, pandas и scikit-learn. Чтобы успешно завершить курс, нужно набрать проходную сумму баллов за тесты и практические задания, а также выполнить финальный проект, посвящённый решению прикладной задачи анализа данных. Мы уверены, что этот курс будет полезен каждому, кто хочет постичь искусство предсказательного моделирования и освоить интеллектуальный анализ данных.
Метод ближайших соседей
Loading...
From the course by National Research University Higher School of Economics
Введение в машинное обучение
1667 ratings
From the lesson
Метрические методы классификации
Метрические методы проводят классификацию на основе сходства, благодаря чему могут работать на данных со сложной структурой — главное, чтобы между объектами можно было измерить расстояние. Мы изучим метод k ближайших соседей, а также способ его обобщения на задачи регрессии с помощью ядерного сглаживания.
Meet the Instructors
Константин Вячеславович ВоронцовПрофессор
Факультет компьютерных наук НИУ ВШЭ, Школа анализа данных Яндекса
Evgeny SokolovSenior Lecturer
HSE Faculty of Computer Science
[БЕЗ ЗВУКА] Сегодня
мы рассмотрим один важный класс методов машинного обучения — это методы,
использующие функции расстояния или метрики в пространстве объектов.
Исходная идея их использования лежит в предположении,
что в практических задачах часто встречаются зависимости,
которые непрерывны.
Таких зависимостей вообще очень много в природе, в технике.
Но это понятие непрерывности оно скорее подходит для задач
восстановления регрессии.
А в задачах классификации аналогом непрерывности является так
называемая гипотеза компактности — предположение о том, что близкие объекты,
как правило, лежат в одном классе.
Что такое близость между объектами, как ее можно формализовать?
Как правило, задается некая функция расстояния — это функция от пары объектов,
которая паре ставит соответствие — неотрицательное число.
Часто еще накладывают требование, чтобы это была метрика в пространстве объектов,
то есть чтобы она была и симметричной, и выполнялось неравенство треугольника.
Однако формально в методах нигде не используется предположение о том,
что это метрика, поэтому, в общем-то, и функции расстояния,
не являющиеся метриками, нам тоже подходят.
Самым известным примером расстояния, наверное,
является евклидово расстояние в признаковом пространстве.
Напомню, что объекты, как правило, у нас задаются n признаками.
Если эти признаки числовые,
то мы можем использовать знакомую нам со школы конструкцию — евклидово расстояние.
Можно эту конструкцию слегка обобщить,
чтобы получить дополнительную гибкость в модели: например,
ввести вместо двойки какую-то другую степень p или
ввести веса признаков wj-тое.
Но появление параметров оно, конечно, всегда потребует от нас неких
дополнительных усилий, неких процедур, которые будут обучать эти параметры.
Но далеко не всегда, не во всех задачах,
именно использование евклидовой метрики осмысленно, и есть масса задач,
где у нас исходно нет признаковых описаний объектов, и гораздо проще пользоваться
не признаками, а непосредственно мерять расстояние между объектами.
Примеры таких объектов — это символьные строки.
Это могут быть тексты естественного языка, это могут быть нуклеотидные или
аминокислотные последовательности, которые изучаются в биоинформатике.
И вот в таких задачах, чтобы сравнить текстовые строки, вообще говоря,
произвольной длины, часто используется так называемое редакторское расстояние
Левенштейна — это количество вставок и замен символов,
которое необходимо произвести, чтобы привести одну строку в другую.
Ну вот описать две сравниваемых строки признаками было бы намного труднее,
чем посчитать вот такое вот расстояние,
которое к тому же достаточно эффективно считается.
Другой, очень похожий пример, но уже между объектами еще более сложной природы:
допустим, мы хотим сравнить 2 подписи,
которые сделали люди специальным пером электронным,
которое запоминает координаты кончика пера ну и еще азимут движения пера.
Значит, мы как подпись имеем 3 кривые, 3 временных ряда,
и нам нужно сравнивать такие временные ряды.
Ну, на картинке представлен пример такого сравнения,
когда 2 похожие буквы сравниваются, и мы видим, что эти 3 кривые они очень похожи с
точностью до каких-то сжатий, растяжений, выравниваний.
Можно придумать модель расстояния между такими траекториями,
как модель пружинок, которые слегка сжимаются или растягиваются
между маленькими локальными кусочками этих кривых, и посчитать
энергию сжатий и растяжений пружинок — это и будет расстояние между этими объектами.
Расстояние посчитать легко,
а придумать здесь признаки было бы значительно сложнее.
Таким образом, расстояния бывают разные в прикладных задачах.
Допустим, что кто-то нам уже дал функцию расстояния и теперь перед нами
стоит задача — научиться классифицировать объекты.
Ну, наверное, самый простой алгоритм классификации вообще из всех алгоритмов,
известных в машинном обучении, — это алгоритм ближайшего соседа.
Чтобы классифицировать объект x,
давайте возьмем все объекты обучающей выборки и найдем среди них ближайший к x,
и отнесем x к тому же классу, к которому принадлежит этот объект.
Ну, конечно же, использовать для классификации только одного ближайшего
соседа — это не очень удачная идея, лучше взять окрестность,
учесть несколько ближайших соседей, как-то по ним усреднить.
И поэтому возникает такая обобщенная идея: давайте упорядочим все
объекты обучающей выборки по возрастанию расстояний до нашего
классифицированного объекта x и еще дополнительно введем вес
i-того соседа или его ценность, полезность при классификации объекта x.
Будем обозначать этот вес w(i, x),
то есть это функция от объекта и от порядкового номера соседа.
Ну если мы усредним в каждом классе значение вот этих весов, то мы получим в
итоге оценку близости объекта к классу: мы ее обозначаем Γ с индексом y от объекта x.
Индекс y показывает, что такая оценка она относится к определенному классу.
Ну и самый естественный принцип классификации — это отнести объект x к
тому классу, для которого эта оценка близости максимальна.
Есть масса частных случаев этой общей формы
метрического алгоритма классификации.
Ну, например, это метод ближайших соседей или совсем уж его частный
самый простой случай — это метод первого ближайшего соседа.
Преимущество этого метода в том, что он очень просто реализуется, еще говорят,
что это «ленивое» обучение, потому что, собственно,
никакого обучения здесь не происходит — мы просто запоминаем выборку,
и потом классификация заключается в поиске ближайших соседей.
Ну вот параметр k — число соседей, которое мы учитываем, он очень полезен тем,
что его можно пытаться оптимизировать и выбрать его так,
чтобы классификация была максимально надежной.
Дело в том, что если мы берем слишком мало соседей,
то среди них могут оказаться какие-то случайные шумовые выбросы.
Если мы берем слишком много соседей, то мы слишком простой классификатор построим,
который в любой точке пространства по сути будет выдавать одно и то же значение.
И где-то посередине находится тот классификатор,
который действительно будет прилично работать.
Проблемы метода ближайших соседей, во-первых,
в том, что мы можем столкнуться с ситуацией,
когда для двух классов оценки степени близости объекта к классу совпадают,
и мы поэтому не понимаем, к какому из этих двух классов отнести наш объект.
А другой недостаток в том, что мы нигде не учитываем сами значения расстояний.
После того как мы отранжировали объекты обучения по возрастанию расстояний,
у нас остались только порядковые номера этих объектов.
Может возникнуть ситуация, когда вы, например, классифицируете по пяти
ближайшим соседям: четыре соседа находятся действительно близко от объекта,
а пятый где-то совсем далеко.
Конечно, в таком случае его надо было бы учесть с меньшим весом.
Ну а...
И пару слов о том, как происходит оптимизация
параметра числа ближайших соседей и почему обязательно надо использовать функционалы,
которые сам классифицируемый объект изымает из обучающей выборки.
Нам этом графике приведены две кривые: это
известная уже вам выборка цветков ириса,
и использованы два алгоритма.
Первый алгоритм — это классификация методом k ближайших соседей.
И когда классифицируется некий объект обучающей выборки,
сам же он является своим собственным соседом, и это дает синюю кривую.
Если же сам объект исключается из числа своих соседей, получается красная кривая.
Ну видно, что синяя кривая нам дает оптимистически смещенную оценку
числа ошибок на контрольных выборках.
И видно, что...
Нам кажется, что оптимально использовать одного соседа,
но если объект сам же является своим собственным соседом,
то понятно, что это некий обман и так делать нельзя.
И здесь на красной кривой мы видим, что в данной
задаче оптимально брать где-то от 30 до 60 соседей, а синяя кривая нам
дает ложный ответ, что надо пользоваться методом первого ближайшего соседа.
Этот метод практически никогда не работает надежно.
[БЕЗ ЗВУКА]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
