Классификация (машинное обучение)

Классифика́ция — один из разделов машинного обучения, посвященный решению следующей задачи. Имеется множество "объектов " (ситуаций), разделённых некоторым образом на "классы ". Задано конечное множество объектов, для которых известно, к каким классам они относятся. Это множество называется "обучающей выборкой ". Классовая принадлежность остальных объектов не известна. Требуется построить алгоритм, способный классифицировать произвольный объект из исходного множества.

Классифици́ровать объект — значит, указать номер (или наименование класса), к которому относится данный объект.

Классифика́ция объекта — номер или наименование класса, выдаваемый алгоритмом классификации в результате его применения к данному конкретному объекту.

В математической статистике задачи классификации называются также задачами дискриминантного анализа.

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

Типология задач классификации

Типы входных данных

* Признаковое описание — наиболее распространённый случай. Каждый объект описывается набором своих характеристик, называемых "признаками ". Признаки могут быть числовыми или нечисловыми.
* Матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов обучающей выборки. С этим типом входных данных работают немногие методы, в частности, метод ближайших соседей, метод парзеновского окна, метод потенциальных функций.
* Временной ряд или сигнал представляет собой последовательность измерений во времени. Каждое измерение может представляться числом, вектором, а в общем случае — признаковым описанием исследуемого объекта в данный момент времени.
* Изображение или видеоряд.
* Встречаются и более сложные случаи, когда входные данные представляются в виде графов, текстов, результатов запросов к базе данных, и т. д. Как правило, они приводятся к первому или второму случаю путём предварительной обработки данных и извлечения признаков.

Классификацию сигналов и изображений называют также распознаванием образов.

Типы классов

* Двухклассовая классификация. Наиболее простой в техническом отношении случай, который служит основой для решения более сложныхзадач.
* Многоклассовая классификация. Когда число классов достигает многих тысяч (например, при распознавании иероглифов или слитной речи), задача классификации становится существенно более трудной.
* Непересекающиеся классы.
* Пересекающиеся классы. Объект может относиться одновременно к нескольким классам.
* Нечёткие классы. Требуется определять степень принадлежности объекта каждому из классов, обычно это действительное число от 0 до 1.

Классификация: формальная постановка

Пусть $X~$ — множество описаний объектов, $Y~$ — множество номеров (или наименований) классов. Существует неизвестная "целевая зависимость " — отображение$y^\{*\}colon\; X\; o\; Y$,значнения которой известны только на объектах конечной обучающей выборки$X^m\; =\; \{(x\_1,y\_1),dots,(x\_m,y\_m)\}$.Требуется построить алгоритм $acolon\; X\; o\; Y$,способный классифицировать произвольный объект$x\; in\; X$.

Вероятностная постановка задачи

Более общей считается вероятностная постановка задачи.Предполагается, что множество пар «объект, класс» $X\; imes\; Y$является вероятностным пространством с неизвестной вероятностной мерой $mathsf\; P$. Имеется конечная обучающая выборка наблюдений$X^m\; =\; \{(x\_1,y\_1),dots,(x\_m,y\_m)\}$, сгенерированная согласно вероятностной мере $mathsf\; P$. Требуется построить алгоритм $acolon\; X\; o\; Y$,способный классифицировать произвольный объект$x\; in\; X$.

Признаковое пространство

"Признаком " называется отображение$fcolon\; X\; o\; D\_f~$, где$D\_f~$ — множество допустимых значений признака. Если заданы признаки $f\_1,dots,f\_n~$, то вектор $\{mathbf\; x\}\; =\; (f\_1(x),dots,f\_n(x))$называется "признаковым описанием " объекта $xin\; X$.Признаковые описания допустимо отождествлять с самими объектами.При этом множество$X\; =\; D\_\{f\_1\}\; imesdots\; imes\; D\_\{f\_n\}$называют "признаковым пространством ".

В зависимости от множества $D\_f$ признаки делятся на следующие типы:

* "бинарный " признак: $D\_f=\{0,1\}$;
* "номинальный " признак: $D\_f$ — конечное множество;
* "порядковый " признак: $D\_f$ — конечное упорядоченное множество;
* "количественный " признак: $D\_f$ — множество действительных чисел.

Часто встречаются прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы.

Примеры прикладных задач

Задачи медицинской диагностики

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

Ценность такого рода систем в том, что они способны мгновенноанализировать и обобщать огромное количество прецедентов —возможность, недоступная специалисту-врачу.

Предсказание месторождений полезных ископаемых

Признаками являются данные геологической разведки.Наличие или отсутствие тех или иных пород на территории районакодируется бинарными признаками.Физико-химические свойства этих пород могут описыватьсякак количественными, так и качественными признаками.Обучающая выборка составляется из прецедентов двух классов:районов известных месторожденийи похожих районов, в которых интересующее ископаемое обнаружено не было.При поиске редких полезных ископаемыхколичество объектов может оказаться намного меньше,чем количество признаков.В этой ситуации плохо работают классические статистические методы.Задача решается путёмпоиска закономерностей в имеющемся массиве данных.В процессе решения выделяются короткие наборы признаков,обладающие наибольшей информативностью —способностью наилучшим образом разделять классы.По аналогии с медицинской задачей,можно сказать, что отыскиваются «синдромы» месторождений.Это важный побочный результат исследования,представляющий значительный интерес для геофизиков и геологов.

Оценивание кредитоспособности заёмщиков

Эта задача решается банками при выдаче кредитов.Потребность в автоматизации процедуры выдачи кредитов впервые возниклав период бума кредитных карт 60-70-х годов в США и других развитых странах.Объектами в данном случае являются физические или юридические лица, претендующие на получение кредита.В случае физических лиц признаковое описание состоит из анкеты,которую заполняет сам заёмщик, и, возможно, дополнительной информации,которую банк собирает о нём из собственных источников.Примеры бинарных признаков: пол, наличие телефона.Номинальные признаки — место проживания, профессия, работодатель.Порядковые признаки — образование, занимаемая должность.Количественные признаки — сумма кредита, возраст, стаж работы, доход семьи,размер задолженностей в других банках.Обучающая выборка составляется из заёмщиков с известной кредитной историей.В простейшем случае принятие решенийсводится к классификации заёмщиков на два класса:«хороших» и «плохих».Кредиты выдаются только заёмщикам первого класса.В более сложном случае оценивается суммарное число баллов (scoreref-en) заёмщика,набранных по совокупности информативных признаков.Чем выше оценка, тем более надёжным считается заёмщик.Отсюда и название — кредитный скоринг.На стадии обучения производится синтез и отбор информативных признакови определяется, сколько баллов назначать за каждый признак,чтобы риск принимаемых решений был минимален.Следующая задача — решить, на каких условиях выдавать кредит:определить процентную ставку, срок погашения,и прочие параметры кредитного договора.Эта задача также может быть решения методами обучения по прецедентам.

Предсказание оттока клиентов

Оптическое распознавание символов

Распознавание речи

Обнаружение спама

Классификация документов

Методы решения

* Байесовский классификатор:
** квадратичный классификатор;
** линейный дискриминант Фишера;
** наивный байесовский классификатор;
** метод парзеновского окна;
** разделение смеси вероятностных распределений (EM-алгоритм);
** метод потенциальных функций или метод радиальных базисных функций;
** метод ближайших соседей.

* Нейронная сеть:
** персептрон;
** многослойный персептрон;
** гибридная сеть встречного распространения;

* Линейный разделитель:
** линейный дискриминант Фишера;
** наивный байесовский классификатор;
** однослойный персептрон;
** логистическая регрессия;
** машина опорных векторов.

* Индукция правил:
** решающее дерево;
** решающий список;
** решающий лес;
** тестовый алгоритм;
** алгоритм вычисления оценок.

* Алгоритмическая композиция:
** взвешенное голосование;
** бустинг;
** бэггинг;
** метод комитетов;
** смесь экспертов.

* Сокращение размерности:
** селекция признаков;
** метод главных компонент;
** метод независимых компонент;
** многомерное шкалирование.

* Выбор модели:
** минимизация эмпирического риска;
** структурная минимизация риска;
** минимум длины описания;
** скользящий контроль;
** извлечение признаков
** самоорганизация моделей;
** случайный поиск с адаптацией;
** генетический алгоритм.

Ссылки

* [http://www.machinelearning.ru www.MachineLearning.ru] — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных
* "Константин Воронцов ". Курс лекций [http://www.ccas.ru/voron/teaching.html Математические методы обучения по прецедентам] , МФТИ, 2004-2008
* "Юрий Лифшиц ". [http://yury.name/internet/06ia.pdf Автоматическая классификация текстов] (Слайды) - лекция №6 из курса [http://yury.name/internet.html «Алгоритмы для Интернета»]

Литература

# "Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. " Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
# "Вапник В. Н. " Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
# "Журавлев Ю. И., Рязанов В. В., Сенько О. В. " «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
# "Загоруйко Н. Г. " Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
# "Шлезингер М., Главач В. " Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
# "Hastie T., Tibshirani R., Friedman J. " The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
# "Mitchell T. " Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.

Категории