Не так давно получил распространение термин «большие данные», обозначивший новую прикладную область — поиск способов автоматического быстрого анализа огромных объёмов разнородной информации. Наука о больших данных ещё только оформляется, но уже сейчас она очень востребована — и в будущем будет востребована только больше. С её помощью можно решать невероятные задачи: оценивать состояние печени по кардиограмме, предсказывать зарплату по описанию вакансии, предлагать пользователю музыку на основании его анкеты в интернете. Большими данными может оказаться что угодно: результаты научных экспериментов, логи банковских транзакций, метеорологические наблюдения, профили в социальных сетях — словом, всё, что может быть полезно проанализировать. Самым перспективным подходом к анализу больших данных считается применение машинного обучения — набора методов, благодаря которым компьютер может находить в массивах изначально неизвестные взаимосвязи и закономерности. На факультете компьютерных наук ВШЭ и в Школе анализа данных есть люди, активно использующие машинное обучение и разрабатывающие новые подходы к нему. Именно они — преподаватели этого курса. Вы изучите основные типы задач, решаемых с помощью машинного обучения — в основном речь пойдёт о классификации, регрессии и кластеризации. Узнаете об основных методах машинного обучения и их особенностях, научитесь оценивать качество моделей — и решать, подходит ли модель для решения конкретной задачи. Наконец, познакомитесь с современными библиотеками, в которых реализованы обсуждаемые модели и методы оценки их качества. Для работы мы будем использовать реальные данные из реальных задач. Краткая программа курса: Неделя 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
Введение в машинное обучение
1601 ratings
From the lesson
Кластеризация и визуализация
Этот модуль посвящен новому классу задач в машинном обучении — обучению без учителя. Под этим понимаются ситуации, в которых нужно найти структуру в данных или произвести их "разведку". В этом модуле мы обсудим две таких задачи: кластеризацию (поиск групп схожих объектов) и визуализацию (отображение объектов в двух- или трехмерное пространство).
Meet the Instructors
Константин Вячеславович ВоронцовПрофессор
Факультет компьютерных наук НИУ ВШЭ, Школа анализа данных Яндекса
Evgeny SokolovSenior Lecturer
HSE Faculty of Computer Science
[ЗАСТАВКА] Кластеризация
— это отдельный класс задач машинного обучения, отличающийся от классификации
тем, что у объектов обучающей выборки нет заранее заданных ответов учителя.
Рассмотрим формальную постановку задачи: имеется пространство объектов,
среди которых конечное множество объектов — обучающая выборка,
и на этих объектах задана функция расстояния,
то есть мы знаем расстояние между этими объектами,
и требуется найти метки кластеров этих объектов.
То есть так разделить конечное множество объектов на группы или кластеры,
чтобы близкие объекты оказались внутри каждой группы,
а между объектами разных групп расстояния были достаточно большие.
Эту задачу можно решать большим числом способов,
она некорректно поставлена, её решение неоднозначно.
И нету каких-то общепризнанных
правильных критериев качества кластеризации, нету какого-то
единого метода и подхода, который всеми бы признавался как единственно правильный,
но и сама функция расстояния, как правило,
формируется экспертами, и можно сделать это по-разному.
И также и количество кластеров тоже мы, как правило, не знаем заранее.
Вот в этих условиях, тем не менее, задачу решать хочется, есть много разных целей,
ради которых решаются задачи кластеризации.
Как правило, это упрощение представления о большом количестве объектов,
понимание их внутренней структуры,
что они всё-таки состоят из каких-то групп однородных объектов,
дальше с этими отдельными выделенными группами уже можно делать какой-то анализ,
ну и так далее, то есть решать задачи кластеризации тем не менее нужно,
несмотря на принципиальную некорректность постановки этой задачи.
Рассмотрим несколько частных случаев.
Интуитивно, когда мы говорим «кластеризация»,
в голове тут же представляем несколько компактных сгустков точек,
между которыми есть чёткие разделяющие области.
Это далеко не всегда так.
Иногда у кластеров можно считать, что мы хотим найти какую-то
определенную геометрическую форму, например, выделить шарообразные кластеры.
Иногда у этих шарообразных кластеров могут образовываться перемычки между ними,
и алгоритмы должны и в этих условиях давать достаточно устойчивые результаты.
Должны они также работать и в тех случаях,
когда в пространстве объектов разбросаны какие-то отдельные шумовые объекты.
Имеются также более сложные задачи,
когда кластеры имеют не шарообразную форму, а так называемую ленточную.
Они представляют собой значительную трудность для многих алгоритмов
кластеризации, основанных на предположении,
что расстояние между точками внутри кластера меньше,
чем расстояние между точками различных кластеров.
Когда у нас ленты, то расстояние внутрикластерные могут быть
существенно больше, чем межкластерные, как показано на рисунке.
Также отдельную трудность представляют собой кластеры,
которые могут быть наложены друг на друга,
но при это отличаться друг от друга существенно плотностью точек.
И мы с вами, глядя на рисунок, чётко видим здесь два кластера,
но для алгоритмов, основанных на попарных близостях точек,
эта ситуация будет представлять значительную трудность.
Также иногда мы интуитивно под кластером понимаем какие-то сложные
геометрические закономерности, которые мы,
имея априорные представления о геометрии пространства, чётко различаем и видим,
что, например, на третьей картинке здесь два кластера, но для метрических
алгоритмов кластеризации эта задача также будет практически нерешаемой.
На практике часто возникают и такие ситуации, когда заказчик очень хочет
получить кластеризацию и узнать кластерную структуру большого множества объектов,
но оказывается, что никакой структуры де-факто, реально не существует.
Есть одно большое облако точек, где-то оно может быть погуще, где-то поплотнее,
где-то поразреженней, и никакими
алгоритмами кластеризации выделить там компактные области не удаётся.
Один из самых простых, базовых методов кластеризации — это метод k-средних.
Этот метод применим в тех случаях, когда объекты исходно задаются
признаковыми описаниями, то есть у нас имеется n вещественных признаков,
и поэтому возникает возможность эти векторы признаков складывать,
умножать на число, и для любого подмножества объектов искать
центр кластера просто путём усреднения векторов-признаков этого кластера.
Так называемый центр масс-кластера.
И вот на этом приёме основан алгоритм, который итерационно повторяет два шага.
На первом шаге каждый объект относится к кластеру ближайшему,
то есть выбирается ближайший центр, а на втором шаге уже,
зная кластерную принадлежность каждого объекта, мы берём каждый кластер и по всем
объектам этого кластера вычисляем среднее как новое положение центра этого кластера.
Эти два шага повторяются в итерациях, пока центры не перестанут существенно меняться.
В качестве начального приближения инициализации берут либо случайные точки,
ну это иногда плохо работает и можно делать
и более интересные инициализации, о которых я расскажу чуть ниже.
Этот алгоритм плох тем, что он застревает в локальных экстремумах.
Конечно, он решает некую оптимизационную задачу,
но локальных оптимумов у этого функционала слишком много, и
в зависимости от начального приближения мы можем получать не очень хорошее решение.
Эту проблему решают многими способами,
в частности есть так называемая «мягкая кластеризация»,
которая позволяет вести итерационный процесс
более мягко и не застревать в локальных экстремумах.
Отличие заключается вот в чем: что теперь мы будем не жестко
относить каждый объект только к одному кластеру,
а мы будем оценивать степень близости каждого объекта ко всем центрам кластеров.
Получается, что каждый объект размазывается по всем кластерам, но,
тем не менее, мы всё равно можем взять тот кластер, оценка близости для которого
максимальна, и всё равно и жёстко отнести объект именно к этому кластеру.
Но тот факт, что объект вот так вот размазан и принадлежит
одновременно всем кластерам в разной степени позволяет точнее,
мягче оценивать центры этих кластеров, и они не так сильно...
не так сильно и не так резко изменяются, как в предыдущем алгоритме,
где центр кластера всегда перескакивает на какую-то определённую величину,
и эти шаги дискретны, потому что состав кластеров всегда дискретен.
Вот. В данном случае, опять таки, два шага.
Первый шаг — это оценивание близости каждого объекта ко всем центрам,
а второй шаг — это вычисление новых положений центров.
При этом, в отличие от предыдущего алгоритма.
где мы по каждому кластеру вычисляли среднее,
здесь мы вычисляем среднее по всей выборке, но у каждого кластера
есть свои степени принадлежности объектов — giy,
и поэтому для каждого кластера y получается своё положение центра.
Обращу внимание, что здесь заодно вычисляются также и мощности кластеров.
Вот этого момента не было в предыдущем алгоритме.
Мы можем усреднить по всем объектам обучающей
выборки вот эти степени принадлежности giy и получить величину wy,
которая говорит, какую долю во всей выборке занимает данный кластер.
И эту величину интересно можно использовать для того,
чтобы подправить близость, близость объекта к центру кластера теперь
еще и пропорциональна мощности этого кластера,
это тоже несколько улучшает качество работы этого алгоритма.
Ну и итерации продолжаются до тех пор,
пока принадлежности объектов кластерам не перестанут изменяться.
В этом алгоритме также, как и в предыдущем, всё равно надо аккуратно
подбирать начальное приближение, и сейчас мы этот вопрос тоже рассмотрим.
Есть много разных методов выбора начальных приближений.
Одна из идей заключается в том, что если мы хотим получить k кластеров,
то давайте возьмём k наиболее удалённых друг от друга объектов обучающей выборки.
Сделать это можно очень простым алгоритмом,
который на слайде представлен в шагах 3 и 4.
Мы сначала находим два самых удалённых друг от друга объектов обучающей выборки,
а затем начинаем по очереди пристраивать к ним третий объект,
четвёртый и так далее так, чтобы каждый новый объект имел максимальное
расстояние до ближайшего из уже выбранных объектов.
Вот такой вот минимаксный принцип жадного отбора объектов по очереди.
Но в этом алгоритме тоже есть один недостаток.
Если объекты распределены в пространстве так,
что кроме сгустков кластеров есть ещё некий фон,
или если могут попадаться объекты, которые очень далеко улетают от всех кластеров
и находятся где-то на периферии выборки, они нам будут мешать в этом алгоритме.
потому что именно они будут в первую очередь выбираться как вот такие опорные
объекты, но тем не менее они не представительны,
они не принадлежат никаким кластерам.
Чтобы справиться с этой проблемой,
мы можем сделать следующий эвристический приём: посчитать среднее расстояние
до q ближайших соседей для каждого объекта, и понятно, что такой периферийный
объект-выброс будет иметь наибольшее расстояние до своих ближайших соседей.
Именно такие объекты надо отбросить.
И поэтому мы упорядочиваем всю выборку вот по этим расстояниям
ri до q ближайших соседей и отбрасываем шумовые объекты,
для которых эти расстояния самые большие.
Параметр (какую долю отбросить) Δ, является параметром этого
метода точно также, как и сколько ближайших соседей брать
(q) тоже параметр, ну и число кластеров k — это тоже параметр,
тот самый, который дальше будет использоваться в алгоритме k- средних.
Вот с помощью такой инициализации можно вычислить неплохое
начальное приближение для k-средних как в жёстком варианте, так и в мягком.
Ну, резюмируя, ещё раз повторю, что недостаток
этих методов — это чувствительность к выбору начального приближения.
Рассказанный способ далеко не единственный,
есть много других хороших идей.
Например, можно делать мультистарт, выбирать много случайных
начальных приближений, из них стартовать алгоритм, а потом выбирать кластеризацию,
которая окажется лучшей по какому-то функционалу качества.
Можно пользоваться идеей сэмплирования из всей большой
выборки выбирать случайное подмножество и его кластеризовать.
Сделать так можно много раз и из всех полученных кластеризаций выбрать ту,
которая окажется наилучшей в смысле функционала качества заданного,
посчитанного по уже теперь полной выборке.
Ну и, наконец, есть много способов задавать число кластеров.
Можно определять их в ходе итераций,
это потребует существенной модификации рассказанных методов,
либо можно несколько раз задать число k и выбрать наилучшее,
но, опять-таки, для этого нужен некоторый функционал качества кластеризации.
Ещё существуют иерархические методы, где число кластеров вообще не определяется,
его можно определить после того, как сделана такая иерархическая
кластеризация, но об этом в следующей лекции.
[ЗАСТАВКА] [ЗАСТАВКА]
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.
