admin / 09.10.2018
Метод ближайшего соседа
.
Множество методов иерархического кластерного анализа различается не только используемыми мерами сходства и различия, но и алгоритмами классификации. Из них наиболее распространен метод ближайшего соседа. Этот метод известен также под названием метод одиночной связи.
Пусть требуется провести классификацию заданного множества объектов методом ближайшего соседа. Расстояние между двумя классами определяется как расстояние между ближайшими их представителями.
Перед началом работы алгоритма рассчитывается матрица расстояний между объектами. На каждом шаге в матрице расстояний ищется минимальное значение, соответствующее расстоянию между двумя наиболее близкими кластерами. Найденные кластеры объединяются, образуя новый кластер. Эта процедура повторяется до тех пор, пока не будут объединены все кластеры. Допустим, задана следующая матрица расстояний:
Решение:
Шаг 1. На первом шаге каждый объект представляет собой отдельный кластер: 
и 
.
Согласно критерию классификации, объединение происходит между кластерами, расстояние между ближайших представителей которых наименьшее: кластеры 
и 
. Расстояние, на котором произошло объединение – 
. Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:
Шаг 2. Кластеры на данном шаге: 
и . Согласно новой матрицы расстояний, кластеры 
и наиболее близкие.
Содержание
- Метод ближайших соседей
- Распознавание речи
- Понимание смысла сказанного
- Распознавание текста
- Компьютерное зрение и классификация изображений
- Рекомендации, прогнозы и анализ взаимосвязей
- Творчество
- Метод ближайших соседей
- Машинное обучение и анализ данных. Лекция для Малого ШАДа ЯндексаTutorial
- Метод ближайших соседей (kNN)
Метод ближайших соседей
Расстояние объединения – 
. Необходимо произвести перерасчет матрицы расстояний с учетом нового кластера:
Шаг 3. Кластеры на данном шаге: 
и 
. Расстояние между кластерами равно 
– это расстояние между 
и 
объектом. Образование кластеров закончено. Результат классификации методом ближайшего соседа представлен в виде дендрограммы:
При использовании метода ближайшего соседа особое внимание следует уделять выбору меры расстояния между объектами. На основе нее формируется начальная матрица расстояний, которая и определяет весь дальнейший процесс классификации.
Прочитал на днях статью «Применение машинного обучения для дизайнеров» и книгу «Машинное обучение для дизайнеров». Разочарован: не понимаю, для кого это всё пишут. Куча размахиваний руками в воздухе и псевдо-сложных рассуждений. Ноль практического применения.
Но я задумался — а где реально обычный дизайнер интерфейсов (или любой не-специалист в computer science) может столкнуться с машинным обучением в повседневных проектах, да ещё с русскоязычными данными. Я попробовал собрать несколько примеров вместе с инструментами.
Поехали!
Распознавание речи
Что это. Программа слушает запись голоса и преобразует её в текст.
Инструменты. Распознавать речь умеют все крупные вендоры: Гугл, Амазон, Микрософт. Они сделали удобные облачные сервисы и библиотеки, только с русским всё печально. Поэтому для русской речи я использовал SpeechKit от Яндекса.
Речь распознавать он более-менее умеет, но качество очень так себе. По моему опыту, короткие бытовые фразы распознаются на 70%, а если говорит ребёнок или у человека плохая дикция — 50%. То есть это далеко не продакшен-качество, использовать голос как единственный способ ввода нельзя.
Есть одно исключение: адреса. Их Яндекс распознаёт очень хорошо (возможно, вы замечали это по яндекс-навигатору).
Лучше человека. Так что для ввода адресов SpeechKit реально можно использовать.
Понимание смысла сказанного
Что это. Программа анализирует текст и пытается понять, что имел в виду человек. По такому принципу работают голосовые помощники вроде Siri и «умные» чат-боты (тупые же ориентируются по ключевым словам, без всякого машинного обучения).
Инструменты. Всё ещё хуже, чем с распознаванием речи. Тот же SpeechKit умеет проводить морфологический анализ предложения (части речи, лица, падежи). Плюс-минус умеет вычленять даты, адреса и ФИО. Но не умеет главного — понимать смысл: выделять действия, объекты, характеристики и обстоятельства.
Распознавание текста
Что это. Программа распознаёт печатный и рукописный текст на сканах и из видео, извлекает текст из фотографий документов и банковских карт, считывает штрихкоды.
Инструменты. На этой поляне давно и прочно играет ABBYY с их FineReader Engine, а ещё есть Smart Engines.
Smart Engines распознаёт паспорт, СНИЛС или водительское удостоверение за секунду и предупреждает, если не уверен в распознавании.
Компьютерное зрение и классификация изображений
Что это. Программа анализирует изображение и относит его к одной из категорий (спортивная машина, ребёнок, цветок и т. п.) Отсеивает «взрослые» фото, считывает текст и логотип с фотографии. Находит лица, определяет количество людей и их пол. Выделяет основные цвета.
Инструменты. Тут работают Cloud Vision от Гугла и свеженький Data Factory от Яндекса.
Про решение от Яндекса толком ничего не известно, а Гугл справляется хорошо. Вот Антон Мальцев на Хабре отлично разобрал каждую возможность и сравнил с конкурентами.
Рекомендации, прогнозы и анализ взаимосвязей
Рекомендации — это «классическое» машинное обучение, которое уже лет двадцать работает на том же Амазоне: проанализировать действия пользователя, понять его предпочтения, предложить что-то интересное. Аналогично Фейсбук формирует ленту, рекомендует друзей и группы — изучая предпочтения пользователя.
Прогнозы — «обучить» программу на известной выборке данных, чтобы дальше она «предсказывала» результат по новым данным.
Например, банк скармливает программе базу людей, которые брали кредиты, и по каждому человеку указывает итог — вернул он долг или просрочил. Дальше программа сама выдаёт прогноз для новых заёмщиков — просрочит человек выплату или нет.
Еще пример: та же программа предсказывает, сколько конкретно денег можно ссудить человеку, чтобы он без проблем выплатил потом кредит.
Анализ взаимосвязей — программа смотрит на данные и замечает закономерности, которые человек не может увидеть самостоятельно. Например, тот же банк может получить ответ на вопрос «что общего у заёмщиков, которые просрочили выплату по кредиту?»
Инструменты. Тут много алгоритмов, я не буду вдаваться в подробности. Много готовых библиотек и сервисов, которые их реализуют. Вот хороший обзор, а вот пример использования гуглового облака для рекомендаций в интернет-магазине, на русском.
Творчество
Что это. Программа выступает «соавтором» дизайнера. Человек задаёт условия задачи, алгоритм анализирует варианты решения и предлагает оптимальный.
Метод ближайших соседей
Это направление ещё называют генеративным дизайном.
Генеративный дизайн используют в архитектуре, промышленности, медицине. Задача, которую решает программа — уменьшить вес и увеличить прочность конструкции (например, детали самолёта или протеза). Маловероятно, что вы столкнётесь с таким проектом, но мало ли ツ
Инструменты. Для генеративного дизайна используют софт компании Autodesk.
⌘ ⌘ ⌘
Конечно, это очень поверхностный обзор. Если завзятый технарь каким-то чудом дочитает до этого места, он будет раскалён как чайник ツ С другой стороны, я надеюсь, что получилось понятное для не-специалистов введение в тему.
Описанные техники машинного обучения встречаются в повседневных проектах, поэтому хорошо понимать, про что они — даже если вы далеки от «компьютерных наук».
Машинное обучение и анализ данных. Лекция для Малого ШАДа ЯндексаTutorial
Алгоритмы, Блог компании Яндекс, Учебный процесс в IT
Все чаще и чаще мы сталкиваемся с необходимостью выявлять внутренние закономерности больших объёмов данных. Например, для распознавания спама необходимо уметь находить закономерности в содержании электронных писем, а для прогнозирования стоимости акций — закономерности в финансовых данных.
Метод ближайших соседей (kNN)
К сожалению, выявить их «вручную» часто невозможно, и тогда на помощь приходят методы машинного обучения. Они позволяют строить алгоритмы, которые помогают находить новые, ещё не описанные закономерности. Мы поговорим о том, что такое машинное обучение, где его стоит применять и какие сложности могут при этом возникнуть. Принципы работы нескольких популярных методов машинного обучения будут рассмотрены на реальных примерах.
Лекция предназначена для старшеклассников — студентов Малого ШАДа, но и взрослые с ее помощью смогут составить представление об основах машинного обучения.
Основная идея машинного обучения заключается в том, что имея обучающуюся программу и примеры данных с закономерностями, мы можем построить некоторую модель закономерности и находить закономерности в новых данных.
Метод ближайшего соседа
Для примера решим простую задачу. У нас на плоскости разбросаны точки двух цветов: красные и синие. Координаты и цвет каждой из них нам известны. Нужно определить цвет новой точки. Каждая точка — изучаемый объект, а координаты и цвет — его параметры. Например, объекты — люди, координаты — рост и длина волос человека, а цвет — пол человека.
Попробуем решить ее методом ближайшего соседа. Пусть новый объект принадлежит к тому же классу, что и его ближайший сосед. Сделаем прогноз для каждой точки на нашей плоскости: если ближайшая точка синяя, значит, и новый объект, появившийся в этой точке – синий. И наоборот.
Таким образом, у нас получаются две области: в одной велика вероятность появления красных точек, а в другой – синих.
Далее попробуем немного изменить алгоритм, и ориентироваться на несколько (k) ближайших соседей. Пускай k будет равно пяти.
В этом случае мы сможем отсечь потенциально шумовые объекты и получить более ровную границу разделения классов.
Вот так будет выглядеть разделение на большем количестве объектов, полученных путем нормального распределения.
Качество и параметры алгоритмов
Снова представим, что у нас есть плоскость, на которой определенным образом расположены красные и синие точки.
Провести границу между ними можно разными способами. Результат будет зависеть от того, насколько алгоритм подстроился под данные.
Как правило, склонность модели к переобучению связана с количеством ее параметров. Так, например, модель с малым количеством параметров вряд ли сможет переобучиться
В общем случае в задачах машинного обучения рассматриваются точки в многомерном пространстве, а не на плоскости. Каждая координата — признак. Поэтому обучающую выборку можно представлять в следующей виде:
Но какой алгоритм выбрать, и как оценить качество его работы? Для этого размеченную обучающую выборку разбивают на две части. На первой части происходит непосредственно обучение, а вторая часть используется в качестве контрольной. На ней мы будем проверять, сколько ошибок выдал алгоритм.
Цикл решения задачи
Примерный цикл решения задачи по машинному обучению выглядит так:
Сначала мы проводим предварительную обработку данных, затем выбираем метод классификации и параметры, проводим обучение и оцениваем качество. Если качество нас утраивает, задача считается выполненной. В противном случае возвращаемся к подбору метода и параметров.
Более подробная информация, примеры реальных задач для машинного обучения, а также рассказ о гиперплоскостях, нейронных сетях. deep learning, методе Виолы-Джонса, решающих деревьях и бустинге доступны в видеозаписи лекции.
ШАД, Малый ШАД, машинное обучение
наверх
Источник статей: Хабр.
Время указано в том часовом поясе, который установлен на Вашем устройстве.
Версия сайта: 0.8.
Об ошибках, предложениях, пожалуйста, сообщайте через Telegram пользователю @leenr, по e-mail i@leenr.ru или с помощью других способов связаться.
Всегдабр (расширение для Google Chrome)
Статистика посещений
СоХабр в ВК (новости проекта)
.
FILED UNDER : IT
