Similarity Miner (виртуальный семинар)
Материал из MachineLearning.
|
Similarity Miner — учебный студенческий проект, программа для решения задач классификации на основе обучаемых функций сходства.
Мотивация
Один из популярных способов визуализации многомерных данных — построение всех возможных точечных графиков (scatter plot) в осях «признак–признак». Обычно эти графики собираются в большую матрицу графиков, строки и столбцы которой соответствуют признакам.
На рисунке показана знаменитая задача классификации, на примере которой Р. Фишер в 1936 году продемонстрировал работу линейного дискриминанта. Объекты — цветки ириса — описываются четырьмя количественными признаками: длина и ширина чашелистиков, длина и ширина лепестков; три класса — это три разновидности ирисов. На графиках можно заметить, что один класс очень хорошо отделим; два других — хуже, и существуют такие пары признаков, относительно которых классы разделяются хорошо.
Такой метод визуального анализа проходит, когда признаков четыре… Он всё ещё проходит, когда их 15. Дальше становится жалко пользователя. С другой стороны, разглядывание двумерных графиков очень полезно на стадии понимания данных.
Первая идея проекта заключается в том, чтобы придумать такие критерии, которые автоматически выделяли бы только наиболее интересные для пользователя графики. Сколько лучших графиков просмотреть, определяет сам пользователь.
В случае многомерных данных (с большим числом признаков), вряд ли найдутся отдельные признаки, и даже пары признаков, позволяющие хорошо отделять классы. Ирисы Фишера — это слишком простая задача, такое благолепие редко встречается в современных приложениях. В общем случае хотелось бы найти такие наборы признаков, которые с одной стороны позволяют построить хороший классификатор, с другой стороны содержат как можно меньше признаков. Чем меньше признаков, тем проще классификатор, тем легче его интерпретировать.
Вторая идея проекта — придумать такой способ наращивания набора признаков, чтобы пользователю по-прежнему показывались бы только двумерные графики, но каждая ось могла бы соответствовать нескольким признакам; и чтобы на этих графиках можно было бы проследить, как улучшается разделимость классов по мере добавления признаков. Многомерное шкалирование, карты сходства и карты Кохонена здесь не подходят, так как они искажают расположение многомерного множества точек на двумерной картинке, и разделяющую поверхность на ней уже не построить…
Третья идея проекта — использовать метод ближайших соседей, самый простой из классификаторов. Если метрику строить по короткому набору признаков, то классификатор будет обладать свойством интерпретируемости. Это означает, что результат классификации можно будет объяснять на человеческом языке, примерно так: «Объект S отнесён к классу A, так как он близок к эталонным (обучающим) объектам класса A (список прилагается) по совокупности признаков F (список прилагается)». Если прилагаемые списки будут достаточно короткими, то пользователь поймёт объяснение и будет больше доверять результату. Прецедентная логика хорошо воспринимается экспертами в таких слабо формализованных областях, как медицина, геология, юриспруденция и др.
Базовые требования
- Исходными данными является матрица объекты–признаки. Решается задача классификации на два класса.
- Для классификации используется метод ближайших соседей. Число соседей и вид ядра должны подбираться автоматически.
- Основная задача — найти метрики (функции сходства объектов, similarity functions), во-первых, обладающие хорошим качеством классификации; во-вторых, хорошо интерпретируемые, то есть зависящие от небольшого числа признаков.
- Метрика — взвешенная евклидова. Веса признаков в метрике должны настраиваться автоматически.
- Процесс подбора метрики может происходить как полностью автоматически, так и под контролем пользователя.
- С точки зрения пользователя процесс подбора метрики заключается в разглядывании серии графиков. Каждый график отображает выборку и разделяющую кривую; по осям могут откладываться как исходные признаки, так и новые, синтезированные программой. Графики позволяют увидеть задачу в различных разрезах и оценить, насколько улучшается качество классификации по мере добавления признаков в метрику. Ничего более сложного пользователю показывать нельзя.
- Программа сама должна отбирать и показывать пользователю только наиболее интересные графики. Пользователь должен иметь возможность «забраковать» метрику, если график ему «не нравится» или если он считает сочетание признаков в данной метрике неинтерпретируемым.
Идеи синтеза признаков
- Если уже есть kNN классификатор, то расстояние до разделяющей поверхности можно рассматривать как новый признак.
Дополнительные требования
- Число классов может быть произвольно. Реализовать стратегию «каждый против всех».
- Число объектов может быть как маленьким (десятки), так и большим (миллионы). Реализовать отбор эталонных объектов.
- Число признаков может быть как маленьким (единицы), так и большим (тысячи). Применить эвристики сокращения перебора.
- Должна автоматически строиться композиция из нескольких лучших kNN-классификаторов.
- Программа должна быть доступна в Интернет через веб-интерфейс.
Ссылки
- Машинное обучение (курс лекций, К.В.Воронцов).
- Близкий проект (но гораздо круче!) Юрия Лифшица; много полезных ссылок.
