Методы классификации (распознавания образов)

[Парджеттер]

Уважаемые форумчане!

Не могли бы вы посоветовать мне нечто вот по какому вопросу.
Есть задачи классификации (или распознавания образов), в частности, есть задачи обучения с учителем (или по прецедентам).
Меня интересуют три метода
- метод ближайшей точки (или соседа);
- метод потенциальных функций;
- метод отсечений.

Я так понимаю, первые два метода достаточно распространенные. Вот по последнему не могу найти вообще ничего. Либо это просто сюда не относится (я знаю только метод отсечений в целочисленном программировании), либо, быть может, имеет какое-то более распространенное название? Ну либо я просто плохо искал.

Интересует, главным образом, литература именно по алгоритмической реализации методов, а не по формальной части, потому что с математической точки зрения я уже кое-что нашел. Хотя, конечно, я буду благодарен вообще за любые ссылки или пояснения.

Подскажите пожалуйста. Заранее благодарен.

[Yuri Gendelman]

Парджеттер писал(а):

... метод отсечений.
...
Либо это просто сюда не относится (я знаю только метод отсечений в целочисленном программировании), либо, быть может, имеет какое-то более распространенное название?

Я встречал только метод отсечений Гомори, о котором Вы пишете, и еще метод альфа-бета отсечений в задачах игрового программирования.

Может быть речь идет о чем-то вроде понижения размерности пространства признаков? Его ведь можно интерпретировать и как "отсечение малоинформативных параметров". Но это не столько классификатор, сколько предварительная обработка данных. Для снижения размерности еще может применяться преобразование (кажется) Карлюена-Лоева.

Замечание: метод потенциальных функций хорошо работает, если классы образуют выпуклые области в пространстве признаков. Для невыпуклых (например, бананоподобных) областей я использовал "метод таксономии (автоматической классификации) с помощью построения покрывающего дерева". В основе лежит алгоритм построения покрывающего дерева (см. Э.Дейкстра. Дисциплина программирования. М. "Мир". 1978. Раздел 22). Ссылка на источник алгоритма таксономии не сохранилась. Возможно, это был сборник "Алгоритмы обучения распознаванию образов". ред. В.Н.Вапник. М."Сов.Радио", 1973. Во всяком случае алгоритм реализации метода потенциальных функций я брал отсюда.
Если интересно: у меня в архиве сохранился код на Фортране.

[Парджеттер]

Yuri Gendelman писал(а):

Может быть речь идет о чем-то вроде понижения размерности пространства признаков? Его ведь можно интерпретировать и как "отсечение малоинформативных параметров". Но это не столько классификатор, сколько предварительная обработка данных. Для снижения размерности еще может применяться преобразование (кажется) Карлюена-Лоева.

Спасибо, надо будет поискать

Yuri Gendelman писал(а):

Если интересно: у меня в архиве сохранился код на Фортране.

Конечно, был бы вам очень признателен

Хотя вот мне тут подкинули какую-то реализацию, правда на дискетах. А у меня в компьютере дисковода нет (за ненадобностью), поэтому буду ждать удобного случая перекинуть все это. Так что я даже не знаю, что там за язык и вообще как это все сделано.

[Yuri Gendelman]

http://rapidshare.com/files/96070051/Pat_Rec.zip.html (19 Кб).
Здесь два проекта, ПФ и Дерево, для MS Fortran Power Station 1 (Fortran 77 с некоторми расширениями). Файлы датированы 97-м, когда я их проверил и положил в архив. Но все это делалось лет на 10 раньше.
В обоих проектах реализуется автоматическая классификация с автоматическим же выбором числа классов.

Информация к размышлению: есть флоппи-дисководы с USB-интерфейсом, стоят в США порядка $40. У меня года 4 назад был такой в комплекте к лэптопу от Dell.

[PAV]

Вообще-то, конечно, материалов по этим вопросам немеряно есть. Я буду в ближайшее время наводить порядок в своей локальной библиотеке, если что-то подходящее найду, напишу. Недавно наткнулся в интернете на учебные материалы Воронцова, поглядите.

[Парджеттер]

Yuri Gendelman, большое спасибо!
Насчет флоппи вопрос буквально только что решился. Программа на Pascal написана лет 10 назад или больше. В ближайшее время буду ее изучать.

PAV писал(а):

Я буду в ближайшее время наводить порядок в своей локальной библиотеке, если что-то подходящее найду, напишу.

Буду Вам очень признателен.

PAV писал(а):

Недавно наткнулся в интернете на учебные материалы Воронцова, поглядите.

Да, я на это тоже наткнулся как раз, когда начал поиски. Там неплохо изложен вопрос в разделе "Метрические алгоритмы".

[PAV]

А Вы можете привести англоязычные аналоги названий метода отсечений и потенциальных функций? Я как-то с англоязычными терминами больше дружу в этой области.

Добавлено спустя 40 минут 12 секунд:

Вообще неплохие источники

Friedman J., Hastie T., Tibshirani R. — The Elements of Statistical Learning

(или Hastie T., Tibshirani R., Friedman J. — The Elements of Statistical Learning Data Mining, Inference and Prediction - кажется, это одно и то же)

а также

Suykens J.A.K., Horvath G., Basu S. — Advances in learning theory: methods, models and applications

[PAV]

Abe Sh. — Support Vector Machines for Pattern Classification

[Парджеттер]

PAV, большое вам спасибо.

Сейчас нашел и изучаю
Friedman J., Hastie T., Tibshirani R. — The Elements of Statistical Learning

Действительно, очень хорошая книжка.

Думаю, скоро доберусь и до двух остальных.

p.s. Извините, что отвечаю с такой задержкой, просто я занимаюсь двумя темами, которые друг с другом не связаны и вот сейчас только вернулся вновь к классификации.

[VoKoV]

Уважаемый Парджеттер, а чем продиктован выбор именно из этих трёх методов? Первый примитивен, второй морально устарел (на его смену пришёл RBF - radial basis function), третий, скорее всего, чьё-то неприжившееся изобретение. Весь мир вроде бы предпочитает пользоваться SVM, нейронными сетями, бустингом над решающими деревьями и прочими "state of the art".

По поводу третьего метода есть подозрение, что это что-то вроде решающего списка гиперплоскостей: находим гиперплоскость, отсекающую часть объектов только одного класса, по оставшимся объектам находим вторую гиперплоскость, отсекающую ещё одну порцию объектов (возможно, уже другого) класса, и т.д. В итоге получается кусочно-линейная разделяющая поверхность. Такие идеи были популярны в конце 60-х. Похожие методы - "альфа-процедура" В.И.Васильева (который из ин-та Глушкова в Киеве) и метод ДРЭТ - дробящихся эталонов Н.Г.Загоруйко.

Рекомендую книгу:
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. http://lib.mexmat.ru/books/5081

Библиография по методам классификации, машинного обучения и смежным темам:
http://www.ccas.ru/frc/bib-bysections.html

Добавлено спустя 23 минуты 17 секунд:

Мега-проект века: MachineLearning.Ru

Уважаемые коллеги!

Недавно начал функционировать Ресурс http://www.MachineLearning.Ru - профессиональный информационно-аналитический ресурс, посвященный машинному обучению и интеллектуальному анализу данных. Сделан на основе движка Википедии, т.е. каждый в него может писать свои статьи!

Присоединяйтесь!

[Парджеттер]

Уважаемый VoKoV! Насколько я понимаю, вы и есть Константин Вячеславович Воронцов. Приятно с вами познакомиться.

VoKoV писал(а):

Уважаемый Парджеттер, а чем продиктован выбор именно из этих трёх методов? Первый примитивен, второй морально устарел (на его смену пришёл RBF - radial basis function), третий, скорее всего, чьё-то неприжившееся изобретение.

Понимаете, к сожалению, я не располагаю информацией по вопросу "чем обсусловлен выбор этих методов". Не я автор задачи. Но думаю, что именно их примитивностью.

VoKoV писал(а):

Весь мир вроде бы предпочитает пользоваться SVM, нейронными сетями, бустингом над решающими деревьями и прочими "state of the art".

Полагаю, что и до этого дойдет... рано или поздно...

VoKoV писал(а):

По поводу третьего метода есть подозрение, что это что-то вроде решающего списка гиперплоскостей: находим гиперплоскость, отсекающую часть объектов только одного класса, по оставшимся объектам находим вторую гиперплоскость, отсекающую ещё одну порцию объектов (возможно, уже другого) класса, и т.д. В итоге получается кусочно-линейная разделяющая поверхность.

Мерси. Насколько я понимаю, это то, что изложено в ч.4 курса Л.М.Местецкого? Я именно на этот метод и подумал. Но надо будет уточнить у "заказчика".

VoKoV писал(а):

Рекомендую книгу:
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.

Библиография по методам классификации, машинного обучения и смежным темам:

Огромное спасибо! Буду изучать.

VoKoV писал(а):

Недавно начал функционировать Ресурс www.MachineLearning.Ru - профессиональный информационно-аналитический ресурс, посвященный машинному обучению и интеллектуальному анализу данных. Сделан на основе движка Википедии, т.е. каждый в него может писать свои статьи!

Я, кстати, вышел на этот ресурс в самом начале поисков. Но насколько я понимаю, он лишь зарождается?

p.s. А не могли бы вы подсказать, вкратце, для какого класса задач используются генетические алгоритмы? Используются ли для задач распознавания? Я просто встерчаю упоминания, но не могу найти нормального описания - чтоб кратко и ясно зачем и что. Обычно очень пространные какие-то описания попадаются...

[VoKoV]

Было бы интересно узнать поподробней, что за задача. Тогда, возможно, посоветовал бы что-то поконкретней. Можно по почте: vokov собака forecsys точка ru.

Генетические алгоритмы используются по-разному. Самое частое применение - для выбора информативного подмножества признаков (features selection) - об этом есть немного в моих лекциях, глава "Оценивание и выбор моделей". Родственное применение - для синтеза логических закономерностей (rule induction), глава "Логические алгоритмы классификации", но сама генетика там не описана. Есть очень интересная статья о применении генетики для синтеза правил в алгоритмах предсказания ухода клиентов: http://citeseer.ist.psu.edu/645115.html. Ещё одно популярное применение - для оптимизации структуры нейронных сетей. Есть и более экзотические применения, ведь генетика универсальна и особенно хороша для дискретной оптимизации, к которой сводятся многие задачи обучения.

[Парджеттер]

VoKoV писал(а):

Было бы интересно узнать поподробней, что за задача. Тогда, возможно, посоветовал бы что-то поконкретней. Можно по почте: vokov собака forecsys точка ru.

Пока есть только задел. Дальше, наверное, пойдет развитие в разные стороны.
А задел простой как апельсин - есть объект, который характеризуется N параметрами. Садится эксперт, оценивает обучающую выборку, происходит обучение по заданному алгоритму. Т.е. самая простая постановка, которая, наверное, может быть.

Я еще хотел вам задать один вопрос насчет генетических алгоритмов, но пока, что-то, не получается у меня его сформулировать. Постараюсь попозже.

p.s. Кстати, нашел достаточно интересную книжку (правда в некоторых местах очень обзорную)
Л.Г.Комарцова, А.В.Максимов Нейкрокомпьютеры
(очень хорошее качество электронной версии, как мне показалось)

Но я ее купил в бумажном виде... за 100 рублей