Similarity Miner (виртуальный семинар)
Материал из MachineLearning.
м (→Мотивация: викификация) |
|||
| (6 промежуточных версий не показаны.) | |||
| Строка 5: | Строка 5: | ||
== Мотивация == | == Мотивация == | ||
Один из популярных способов визуализации многомерных данных — | Один из популярных способов визуализации многомерных данных — | ||
| - | построение всех возможных точечных | + | построение всех возможных точечных графиков (scatter plot) в осях «признак–признак». |
| - | Обычно эти графики собираются в большую матрицу графиков, | + | Обычно эти графики собираются в большую матрицу графиков, строки и столбцы которой соответствуют признакам. |
| - | + | ||
| - | Такой метод визуального анализа проходит, когда признаков четыре… ещё проходит, когда их 15 | + | На рисунке показана знаменитая задача [[классификация|классификации]], |
| + | на примере которой Р. Фишер в 1936 году продемонстрировал работу [[Линейный дискриминант Фишера|линейного дискриминанта]]. | ||
| + | Объекты — цветки ириса — описываются четырьмя количественными признаками: длина и ширина чашелистиков, длина и ширина лепестков; три класса — это три разновидности ирисов. | ||
| + | На графиках можно заметить, что один класс очень хорошо отделим; два других — хуже, | ||
| + | и существуют такие пары признаков, относительно которых классы разделяются хорошо. | ||
| + | |||
| + | Такой метод визуального анализа проходит, когда признаков четыре… | ||
| + | Он всё ещё проходит, когда их 15. | ||
| + | Дальше становится жалко пользователя. | ||
| + | С другой стороны, разглядывание двумерных графиков очень полезно на стадии [[Понимание данных|понимания данных]]. | ||
[[Изображение:Fiher-Iris.png|355px|thumb|'''Ирисы Фишера.''' Все сочетания 2 из 4 признаков.]] | [[Изображение:Fiher-Iris.png|355px|thumb|'''Ирисы Фишера.''' Все сочетания 2 из 4 признаков.]] | ||
| Строка 17: | Строка 25: | ||
В случае многомерных данных (с большим числом [[признак]]ов), вряд ли найдутся отдельные признаки, и даже пары признаков, позволяющие хорошо отделять классы. ''Ирисы Фишера'' — это слишком простая задача, такое благолепие редко встречается в современных приложениях. В общем случае хотелось бы найти такие наборы признаков, которые с одной стороны позволяют построить хороший классификатор, с другой стороны содержат как можно меньше признаков. Чем меньше признаков, тем проще классификатор, тем легче его интерпретировать. | В случае многомерных данных (с большим числом [[признак]]ов), вряд ли найдутся отдельные признаки, и даже пары признаков, позволяющие хорошо отделять классы. ''Ирисы Фишера'' — это слишком простая задача, такое благолепие редко встречается в современных приложениях. В общем случае хотелось бы найти такие наборы признаков, которые с одной стороны позволяют построить хороший классификатор, с другой стороны содержат как можно меньше признаков. Чем меньше признаков, тем проще классификатор, тем легче его интерпретировать. | ||
| - | '''Вторая идея''' проекта — придумать такой способ наращивания признаков, чтобы пользователю по-прежнему | + | '''Вторая идея''' проекта — придумать такой способ наращивания набора признаков, чтобы пользователю по-прежнему показывались бы только двумерные графики, но каждая ось могла бы соответствовать нескольким признакам; и чтобы на этих графиках можно было бы проследить, как улучшается разделимость классов по мере добавления признаков. [[Многомерное шкалирование]], [[Карта сходства|карты сходства]] и [[Нейронная сеть Кохонена|карты Кохонена]] здесь не подходят, так как они искажают расположение многомерного множества точек на двумерной картинке, и разделяющую поверхность на ней уже не построить… |
| - | '''Третья идея''' проекта — использовать [[метод ближайших соседей]], самый простой из классификаторов. | + | '''Третья идея''' проекта — использовать [[метод ближайших соседей]], самый простой из классификаторов. |
| + | Если метрику строить по короткому набору признаков, то классификатор будет обладать свойством интерпретируемости. | ||
| + | Это означает, что результат классификации можно будет объяснять на человеческом языке, примерно так: | ||
| + | «Объект ''S'' отнесён к классу ''A'', так как он близок к эталонным (обучающим) объектам класса ''A'' (список прилагается) по совокупности признаков ''F'' (список прилагается)». | ||
| + | Если прилагаемые списки будут достаточно короткими, то пользователь поймёт объяснение и будет больше доверять результату. | ||
| + | Прецедентная логика хорошо воспринимается экспертами в таких слабо формализованных областях, как медицина, геология, юриспруденция и др. | ||
== Базовые требования == | == Базовые требования == | ||
| Строка 27: | Строка 40: | ||
* Метрика — взвешенная евклидова. Веса признаков в метрике должны настраиваться автоматически. | * Метрика — взвешенная евклидова. Веса признаков в метрике должны настраиваться автоматически. | ||
* Процесс подбора метрики может происходить как полностью автоматически, так и под контролем пользователя. | * Процесс подбора метрики может происходить как полностью автоматически, так и под контролем пользователя. | ||
| - | [[Изображение:kNN-2dim-example.png| | + | [[Изображение:kNN-2dim-example.png|280px|thumb|'''Пример.''' Выборка и разделяющая кривая.]] |
* С точки зрения пользователя процесс подбора метрики заключается в разглядывании серии графиков. Каждый график отображает выборку и разделяющую кривую; по осям могут откладываться как исходные признаки, так и новые, синтезированные программой. Графики позволяют увидеть задачу в различных разрезах и оценить, насколько улучшается качество классификации по мере добавления признаков в метрику. Ничего более сложного пользователю показывать нельзя. | * С точки зрения пользователя процесс подбора метрики заключается в разглядывании серии графиков. Каждый график отображает выборку и разделяющую кривую; по осям могут откладываться как исходные признаки, так и новые, синтезированные программой. Графики позволяют увидеть задачу в различных разрезах и оценить, насколько улучшается качество классификации по мере добавления признаков в метрику. Ничего более сложного пользователю показывать нельзя. | ||
* Программа сама должна отбирать и показывать пользователю только наиболее интересные графики. Пользователь должен иметь возможность «забраковать» метрику, если график ему «не нравится» или если он считает сочетание признаков в данной метрике неинтерпретируемым. | * Программа сама должна отбирать и показывать пользователю только наиболее интересные графики. Пользователь должен иметь возможность «забраковать» метрику, если график ему «не нравится» или если он считает сочетание признаков в данной метрике неинтерпретируемым. | ||
| Строка 42: | Строка 55: | ||
== Ссылки == | == Ссылки == | ||
| - | * [[Машинное обучение (курс лекций, К.В.Воронцов)]] | + | * [[Машинное обучение (курс лекций, К.В.Воронцов)]]. |
| + | * [http://simsearch.yury.name Близкий проект] (но гораздо круче!) [http://yury.name Юрия Лифшица]; много полезных ссылок. | ||
[[Категория:Метрические алгоритмы классификации]] | [[Категория:Метрические алгоритмы классификации]] | ||
[[Категория:Виртуальные семинары]] | [[Категория:Виртуальные семинары]] | ||
Текущая версия
|
Similarity Miner — учебный студенческий проект, программа для решения задач классификации на основе обучаемых функций сходства.
Мотивация
Один из популярных способов визуализации многомерных данных — построение всех возможных точечных графиков (scatter plot) в осях «признак–признак». Обычно эти графики собираются в большую матрицу графиков, строки и столбцы которой соответствуют признакам.
На рисунке показана знаменитая задача классификации, на примере которой Р. Фишер в 1936 году продемонстрировал работу линейного дискриминанта. Объекты — цветки ириса — описываются четырьмя количественными признаками: длина и ширина чашелистиков, длина и ширина лепестков; три класса — это три разновидности ирисов. На графиках можно заметить, что один класс очень хорошо отделим; два других — хуже, и существуют такие пары признаков, относительно которых классы разделяются хорошо.
Такой метод визуального анализа проходит, когда признаков четыре… Он всё ещё проходит, когда их 15. Дальше становится жалко пользователя. С другой стороны, разглядывание двумерных графиков очень полезно на стадии понимания данных.
Первая идея проекта заключается в том, чтобы придумать такие критерии, которые автоматически выделяли бы только наиболее интересные для пользователя графики. Сколько лучших графиков просмотреть, определяет сам пользователь.
В случае многомерных данных (с большим числом признаков), вряд ли найдутся отдельные признаки, и даже пары признаков, позволяющие хорошо отделять классы. Ирисы Фишера — это слишком простая задача, такое благолепие редко встречается в современных приложениях. В общем случае хотелось бы найти такие наборы признаков, которые с одной стороны позволяют построить хороший классификатор, с другой стороны содержат как можно меньше признаков. Чем меньше признаков, тем проще классификатор, тем легче его интерпретировать.
Вторая идея проекта — придумать такой способ наращивания набора признаков, чтобы пользователю по-прежнему показывались бы только двумерные графики, но каждая ось могла бы соответствовать нескольким признакам; и чтобы на этих графиках можно было бы проследить, как улучшается разделимость классов по мере добавления признаков. Многомерное шкалирование, карты сходства и карты Кохонена здесь не подходят, так как они искажают расположение многомерного множества точек на двумерной картинке, и разделяющую поверхность на ней уже не построить…
Третья идея проекта — использовать метод ближайших соседей, самый простой из классификаторов. Если метрику строить по короткому набору признаков, то классификатор будет обладать свойством интерпретируемости. Это означает, что результат классификации можно будет объяснять на человеческом языке, примерно так: «Объект S отнесён к классу A, так как он близок к эталонным (обучающим) объектам класса A (список прилагается) по совокупности признаков F (список прилагается)». Если прилагаемые списки будут достаточно короткими, то пользователь поймёт объяснение и будет больше доверять результату. Прецедентная логика хорошо воспринимается экспертами в таких слабо формализованных областях, как медицина, геология, юриспруденция и др.
Базовые требования
- Исходными данными является матрица объекты–признаки. Решается задача классификации на два класса.
- Для классификации используется метод ближайших соседей. Число соседей и вид ядра должны подбираться автоматически.
- Основная задача — найти метрики (функции сходства объектов, similarity functions), во-первых, обладающие хорошим качеством классификации; во-вторых, хорошо интерпретируемые, то есть зависящие от небольшого числа признаков.
- Метрика — взвешенная евклидова. Веса признаков в метрике должны настраиваться автоматически.
- Процесс подбора метрики может происходить как полностью автоматически, так и под контролем пользователя.
- С точки зрения пользователя процесс подбора метрики заключается в разглядывании серии графиков. Каждый график отображает выборку и разделяющую кривую; по осям могут откладываться как исходные признаки, так и новые, синтезированные программой. Графики позволяют увидеть задачу в различных разрезах и оценить, насколько улучшается качество классификации по мере добавления признаков в метрику. Ничего более сложного пользователю показывать нельзя.
- Программа сама должна отбирать и показывать пользователю только наиболее интересные графики. Пользователь должен иметь возможность «забраковать» метрику, если график ему «не нравится» или если он считает сочетание признаков в данной метрике неинтерпретируемым.
Идеи синтеза признаков
- Если уже есть kNN классификатор, то расстояние до разделяющей поверхности можно рассматривать как новый признак.
Дополнительные требования
- Число классов может быть произвольно. Реализовать стратегию «каждый против всех».
- Число объектов может быть как маленьким (десятки), так и большим (миллионы). Реализовать отбор эталонных объектов.
- Число признаков может быть как маленьким (единицы), так и большим (тысячи). Применить эвристики сокращения перебора.
- Должна автоматически строиться композиция из нескольких лучших kNN-классификаторов.
- Программа должна быть доступна в Интернет через веб-интерфейс.
Ссылки
- Машинное обучение (курс лекций, К.В.Воронцов).
- Близкий проект (но гораздо круче!) Юрия Лифшица; много полезных ссылок.
