В процессе подготовки задачи для вступительного испытания на летнюю школу GoTo , мы обнаружили, что на русском языке практически отсутствует качественное описание основных метрик ранжирования (задача касалась частного случая задачи ранжирования - построения рекомендательного алгоритма). Мы в E-Contenta активно используем различные метрики ранжирования, поэтому решили исправить это недоразуменее, написав эту статью.

Задача ранжирования сейчас возникает повсюду: сортировка веб-страниц согласно заданному поисковому запросу, персонализация новостной ленты, рекомендации видео, товаров, музыки… Одним словом, тема горячая. Есть даже специальное направление в машинном обучении, которое занимается изучением алгоритмов ранжирования способных самообучаться - обучение ранжированию (learning to rank). Чтобы выбрать из всего многообразия алгоритмов и подходов наилучший, необходимо уметь оценивать их качество количественно. О наиболее распространенных метриках качества ранжирования и пойдет речь далее.

Кратко о задаче ранжирования

Ранжирование - задача сортировки набора элементов из соображения их релевантности . Чаще всего релевантность понимается по отношению к некому объекту . Например, в задаче информационного поиска объект - это запрос, элементы - всевозможные документы (ссылки на них), а релевантность - соответствие документа запросу, в задаче рекомендаций же объект - это пользователь, элементы - тот или иной рекомендуемый контент (товары, видео, музыка), а релевантность - вероятность того, что пользователь воспользуется (купит/лайкнет/просмотрит) данным контентом.

Формально, рассмотрим N объектов и M элементов . Реузальтат работы алгоритма ранжирования элементов для объекта - это отображение , которое сопоставляет каждому элементу вес , характеризующей степень релевантности элемента объекту (чем больше вес, тем релевантнее объект). При этом, набор весов задает перестановку на наборе элементов элементов (считаем, что множество элементов упорядоченное) исходя из их сортировки по убыванию веса .

Чтобы оценить качество ранжирования, необходимо иметь некоторый «эталон», с которым можно было бы сравнить результаты алгоритма. Рассмотрим - эталонную функцию релевантности, характеризующую «настоящую» релевантность элементов для данного объекта ( - элемент идеально подходит, - полностью нерелевантен), а так же соответствующую ей перестановку (по убыванию ).

Существует два основных способа получения :
1. На основе исторических данных. Например, в случае рекомендаций контента, можно взять просмотры (лайки, покупки) пользователя и присвоить просмотренным весам соответствующих элементов 1 (), а всем остальным - 0.
2. На основе экспертной оценки. Например, в задаче поиска, для каждого запроса можно привлечь команду асессоров, которые вручную оценят релевантности документов запросу.

Стоит отметить, что когда принимает только экстремальные значения: 0 и 1, то престановку обычно не рассматривют и учитывают лишь множество релевантных элементов, для которых .

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

Mean average precision

Mean average precision at K (map@K) - одна из наиболее часто используемых метрик качества ранжирования. Чтобы разобраться в том, как она работает начнем с «основ».

Замечание: "*precision" метрики используется в бинарных задачах, где принимает только два значения: 0 и 1.

Precision at K

Precision at K (p@K) - точность на K элементах - базовая метрика качества ранжирования для одного объекта. Допустим, наш алгоритм ранжирования выдал оценки релевантности для каждого элемента . Отобрав среди них первые элементов с наибольшим можно посчитать долю релевантных. Именно это и делает precision at K:

Замечание: под понимается элемент , который в результате перестановки оказался на -ой позиции. Так, - элемент с наибольшим , - элемент со вторым по величине и так далее.

Average precision at K

Precision at K - метрика простая для понимания и реализации, но имеет важный недостаток - она не учитывает порядок элементов в «топе». Так, если из десяти элементов мы угадали только один, то не важно на каком месте он был: на первом, или на последнем, - в любом случае . При этом очевидно, что первый вариант гораздо лучше.

Этот недостаток нивелирует метрика ранжирования average precision at K (ap@K) , которая равна сумме p@k по индексам k от 1 до K только для релевантных элементов , деленому на K:

Так, если из трех элементов мы релевантным оказался только находящийся на последнем месте, то , если угадали лишь тот, что был на первом месте, то , а если угаданы были все, то .

Теперь и map@K нам по зубами.

Mean average precision at K

Mean average precision at K (map@K) - одна из наиболее часто используемых метрик качества ранжирования. В p@K и ap@K качество ранжирования оценивается для отдельно взятого объекта (пользователя, поискового запроса). На практике объектов множество: мы имеем дело с сотнями тысяч пользователей, миллионами поисковых запросов и т.д. Идея map@K заключается в том, чтобы посчитать ap@K для каждого объекта и усреднить:

Замечание: идея эта вполне логична, если предположить, что все пользователи одинаково нужны и одинаково важны. Если же это не так, то вместо простого усреднения можно использовать взвешенное, домножив ap@K каждого объекта на соответствующий его «важности» вес.

Normalized Discounted Cumulative Gain

Normalized discounted cumulative gain (nDCG) - еще одна распространенная метрика качества ранжирования. Как и в случае с map@K, начнем с основ.

Cumulative Gain at K

Вновь рассмотрим один объект и элементов с наибольшим . Cumulative gain at K (CG@K) - базовая метрика ранжирования, которая использует простую идею: чем релевантные элементы в этом топе, тем лучше:

Эта метрика обладает очевидными недостатками: она не нормализована и не учитывает позицию релевантных элементов.

Заметим, что в отличии от p@K, CG@K может использоваться и в случае небинарных значений эталонной релевантности .

Discounted Cumulative Gain at K

Discounted cumulative gain at K (DCG@K) - модификация cumulative gain at K, учитывающая порядок элементов в списке путем домножения релевантности элемента на вес равный обратному логарифму номера позиции:

Замечание: если принимает только значения 0 и 1, то , и формула принимает более простой вид:

Использование логарифма как функции дисконтирования можно объяснить следующими интуитивными соображениями: с точки зрения ранжирования позиции в начале списка отличаются гораздо сильнее, чем позиции в его конце. Так, в случае поискового движка между позициями 1 и 11 целая пропасть (лишь в нескольких случаях из ста пользователь заходит дальшей первой страницы поисковой выдачи), а между позициями 101 и 111 особой разницы нет - до них мало кто доходит. Эти субъективные соображения прекрасно выражаются с помощью логарифма:

Discounted cumulative gain решает проблему учета позиции релевантных элементов, но лишь усугубляет проблему с отсутствием нормировки: если варьируется в пределах , то уже принимает значения на не совсем понятно отрезке. Решить эту проблему призвана следующая метрика

Normalized Discounted Cumulative Gain at K

Как можно догадаться из названия, normalized discounted cumulative gain at K (nDCG@K) - не что иное, как нормализованная версия DCG@K:

где - это максимальное (I - ideal) значение . Так как мы договорились, что принимает значения в , то .

Таким образом, наследует от учет позиции элементов в списке и, при этом принимает значения в диапазоне от 0 до 1.

Замечание: по аналогии с map@K можно посчитать , усредненный по всем объектам .

Mean reciprocal rank

Mean reciprocal rank (MRR) - еще одна часто используемая метрика качества ранжирования. Задается она следующей формулой:

где - reciproсal rank для -го объекта - очень простая по своей сути величина, равная обратному ранку первого правильно угаданного элемента .

Mean reciprocal rank изменяется в диапазоне и учитывает позицию элементов. К сожалению он делает это только для одного элемента - 1-го верно предсказанного, не обращая внимания на все последующие.

Метрики на основе ранговой корреляции

Отдельно стоит выделить метрики качества ранжирования, основанные на одном из коэффициентов ранговой корреляции . В статистике, ранговый коэффициент корреляции - это коэффициент корреляции , который учитывает не сами значения, а лишь их ранг (порядок). Рассмотрим два наиболее распространенных ранговых коэффициента корреляции: коэффициенты Спирмена и Кендэлла.

Ранговый коэффициент корреляции Кендэлла

Первый из них - коэффициент корреляции Кендэлла, который основан на подсчете согласованных
(и несогласованных) пар у перестановок - пар элементов, котором перестановки присвоили одинаковый (разный) порядок:

Ранговый коэффициент корреляции Спирмена

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

где - коэффициент корреляции Пирсона.

Метрики на основе ранговой корреляции обладают уже известными нам недостатком: они не учитывают позицию элементов (еще хуже чем p@K, т.к. корреляция считается по всем элементам, а не по K элементам с наибольшим рангом). Поэтому на практике используются крайне редко.

Метрики на основе каскадной модели поведения

До этого момента мы не углублялись в то, как пользователь (далее мы рассмотрим частный случай объекта - пользователь) изучает предложенные ему элементы. На самом деле, неявно нами было сделано предположение, что просмотр каждого элемента независим от просмотров других элементов - своего рода «наивность». На практике же, элементы зачастую просматриваются пользователем поочередно, и то, просмотрит ли пользователь следующий элемент, зависит от его удовлетворенности предыдущими. Рассмотрим пример: в ответ на поисковый запрос алгоритм ранжирования предложил пользователю несколько документов. Если документы на позиции 1 и 2 оказались крайне релевантны, то вероятность того, что пользователь просмотрит документ на позиции 3 мала, т.к. он будет вполне удовлетворен первыми двумя.

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

Expected reciprocal rank

Expected reciprocal rank (ERR) - пример метрики качества ранжирования, основанной на каскадной модели. Задается она следующей формулой:

где ранг понимается по порядку убывания . Самое интересное в этой метрике - вероятности. При их расчете используются предположения каскадной модели:

где - вероятность того, что пользователь будет удовлетворен объектом с рангом . Эти вероятности считаются на основе значений . Так как в нашем случае , то можем рассмотреть простой вариант:

который можно прочесть, как: истинная релевантность элемента оказавшегося на позиции В заключении приведем несколько полезных ссылок

По оттоку клиентов телеком-оператора.

Загрузим необходимые библиотеки и посмотрим на данные

import pandas as pd import matplotlib.pyplot as plt from matplotlib.pylab import rc, plot import seaborn as sns from sklearn.preprocessing import LabelEncoder, OneHotEncoder from sklearn.model_selection import cross_val_score from sklearn.linear_model import LogisticRegression from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier from sklearn.metrics import precision_recall_curve, classification_report from sklearn.model_selection import train_test_split df = pd.read_csv("../../data/telecom_churn.csv")

df.head(5)

Предобработка данных

# Сделаем маппинг бинарных колонок # и закодируем dummy-кодированием штат (для простоты, лучше не делать так для деревянных моделей) d = {"Yes" : 1, "No" : 0} df["International plan"] = df["International plan"].map(d) df["Voice mail plan"] = df["Voice mail plan"].map(d) df["Churn"] = df["Churn"].astype("int64") le = LabelEncoder() df["State"] = le.fit_transform(df["State"]) ohe = OneHotEncoder(sparse=False) encoded_state = ohe.fit_transform(df["State"].values.reshape(-1, 1)) tmp = pd.DataFrame(encoded_state, columns=["state " + str(i) for i in range(encoded_state.shape)]) df = pd.concat(, axis=1)

Accuracy, precision и recall

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

	True Positive (TP)	False Positive (FP)
	False Negative (FN)	True Negative (TN)

Здесь - это ответ алгоритма на объекте, а - истинная метка класса на этом объекте.
Таким образом, ошибки классификации бывают двух видов: False Negative (FN) и False Positive (FP).

Обучение алгоритма и построение матрицы ошибок

X = df.drop("Churn", axis=1) y = df["Churn"] # Делим выборку на train и test, все метрики будем оценивать на тестовом датасете X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y, test_size=0.33, random_state=42) # Обучаем ставшую родной логистическую регрессию lr = LogisticRegression(random_state=42) lr.fit(X_train, y_train) # Воспользуемся функцией построения матрицы ошибок из документации sklearn def plot_confusion_matrix(cm, classes, normalize=False, title="Confusion matrix", cmap=plt.cm.Blues): """ This function prints and plots the confusion matrix. Normalization can be applied by setting `normalize=True`. """ plt.imshow(cm, interpolation="nearest", cmap=cmap) plt.title(title) plt.colorbar() tick_marks = np.arange(len(classes)) plt.xticks(tick_marks, classes, rotation=45) plt.yticks(tick_marks, classes) if normalize: cm = cm.astype("float") / cm.sum(axis=1)[:, np.newaxis] print("Normalized confusion matrix") else: print("Confusion matrix, without normalization") print(cm) thresh = cm.max() / 2. for i, j in itertools.product(range(cm.shape), range(cm.shape)): plt.text(j, i, cm, horizontalalignment="center", color="white" if cm > thresh else "black") plt.tight_layout() plt.ylabel("True label") plt.xlabel("Predicted label") font = {"size" : 15} plt.rc("font", **font) cnf_matrix = confusion_matrix(y_test, lr.predict(X_test)) plt.figure(figsize=(10, 8)) plot_confusion_matrix(cnf_matrix, classes=["Non-churned", "Churned"], title="Confusion matrix") plt.savefig("conf_matrix.png") plt.show()

Accuracy

Интуитивно понятной, очевидной и почти неиспользуемой метрикой является accuracy - доля правильных ответов алгоритма:

Эта метрика бесполезна в задачах с неравными классами, и это легко показать на примере.

Допустим, мы хотим оценить работу спам-фильтра почты. У нас есть 100 не-спам писем, 90 из которых наш классификатор определил верно (True Negative = 90, False Positive = 10), и 10 спам-писем, 5 из которых классификатор также определил верно (True Positive = 5, False Negative = 5).
Тогда accuracy:

Однако если мы просто будем предсказывать все письма как не-спам, то получим более высокую accuracy:

При этом, наша модель совершенно не обладает никакой предсказательной силой, так как изначально мы хотели определять письма со спамом. Преодолеть это нам поможет переход с общей для всех классов метрики к отдельным показателям качества классов.

Precision, recall и F-мера

Для оценки качества работы алгоритма на каждом из классов по отдельности введем метрики precision (точность) и recall (полнота).

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

Именно введение precision не позволяет нам записывать все объекты в один класс, так как в этом случае мы получаем рост уровня False Positive. Recall демонстрирует способность алгоритма обнаруживать данный класс вообще, а precision - способность отличать этот класс от других классов.

Как мы отмечали ранее, ошибки классификации бывают двух видов: False Positive и False Negative. В статистике первый вид ошибок называют ошибкой I-го рода, а второй - ошибкой II-го рода. В нашей задаче по определению оттока абонентов, ошибкой первого рода будет принятие лояльного абонента за уходящего, так как наша нулевая гипотеза состоит в том, что никто из абонентов не уходит, а мы эту гипотезу отвергаем. Соответственно, ошибкой второго рода будет являться "пропуск" уходящего абонента и ошибочное принятие нулевой гипотезы.

Precision и recall не зависят, в отличие от accuracy, от соотношения классов и потому применимы в условиях несбалансированных выборок.
Часто в реальной практике стоит задача найти оптимальный (для заказчика) баланс между этими двумя метриками. Классическим примером является задача определения оттока клиентов.
Очевидно, что мы не можем находить всех уходящих в отток клиентов и только их. Но, определив стратегию и ресурс для удержания клиентов, мы можем подобрать нужные пороги по precision и recall. Например, можно сосредоточиться на удержании только высокодоходных клиентов или тех, кто уйдет с большей вероятностью, так как мы ограничены в ресурсах колл-центра.

Обычно при оптимизации гиперпараметров алгоритма (например, в случае перебора по сетке GridSearchCV ) используется одна метрика, улучшение которой мы и ожидаем увидеть на тестовой выборке.
Существует несколько различных способов объединить precision и recall в агрегированный критерий качества. F-мера (в общем случае ) - среднее гармоническое precision и recall:

В данном случае определяет вес точности в метрике, и при это среднее гармоническое (с множителем 2, чтобы в случае precision = 1 и recall = 1 иметь )
F-мера достигает максимума при полноте и точности, равными единице, и близка к нулю, если один из аргументов близок к нулю.
В sklearn есть удобная функция _metrics.classificationreport , возвращающая recall, precision и F-меру для каждого из классов, а также количество экземпляров каждого класса.

report = classification_report(y_test, lr.predict(X_test), target_names=["Non-churned", "Churned"]) print(report)

class	precision	recall	f1-score	support
Non-churned	0.88	0.97	0.93	941
Churned	0.60	0.25	0.35	159
avg / total	0.84	0.87	0.84	1100

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

AUC-ROC и AUC-PR

При конвертации вещественного ответа алгоритма (как правило, вероятности принадлежности к классу, отдельно см. SVM) в бинарную метку, мы должны выбрать какой-либо порог, при котором 0 становится 1. Естественным и близким кажется порог, равный 0.5, но он не всегда оказывается оптимальным, например, при вышеупомянутом отсутствии баланса классов.

Одним из способов оценить модель в целом, не привязываясь к конкретному порогу, является AUC-ROC (или ROC AUC) - площадь (A rea U nder C urve) под кривой ошибок (R eceiver O perating C haracteristic curve). Данная кривая представляет из себя линию от (0,0) до (1,1) в координатах True Positive Rate (TPR) и False Positive Rate (FPR):

TPR нам уже известна, это полнота, а FPR показывает, какую долю из объектов negative класса алгоритм предсказал неверно. В идеальном случае, когда классификатор не делает ошибок (FPR = 0, TPR = 1) мы получим площадь под кривой, равную единице; в противном случае, когда классификатор случайно выдает вероятности классов, AUC-ROC будет стремиться к 0.5, так как классификатор будет выдавать одинаковое количество TP и FP.
Каждая точка на графике соответствует выбору некоторого порога. Площадь под кривой в данном случае показывает качество алгоритма (больше - лучше), кроме этого, важной является крутизна самой кривой - мы хотим максимизировать TPR, минимизируя FPR, а значит, наша кривая в идеале должна стремиться к точке (0,1).

Код отрисовки ROC-кривой

sns.set(font_scale=1.5) sns.set_color_codes("muted") plt.figure(figsize=(10, 8)) fpr, tpr, thresholds = roc_curve(y_test, lr.predict_proba(X_test)[:,1], pos_label=1) lw = 2 plt.plot(fpr, tpr, lw=lw, label="ROC curve ") plt.plot(, ) plt.xlim() plt.ylim() plt.xlabel("False Positive Rate") plt.ylabel("True Positive Rate") plt.title("ROC curve") plt.savefig("ROC.png") plt.show()

Критерий AUC-ROC устойчив к несбалансированным классам (спойлер: увы, не всё так однозначно) и может быть интерпретирован как вероятность того, что случайно выбранный positive объект будет проранжирован классификатором выше (будет иметь более высокую вероятность быть positive), чем случайно выбранный negative объект.

Рассмотрим следующую задачу: нам необходимо выбрать 100 релевантных документов из 1 миллиона документов. Мы намашинлернили два алгоритма:

• Алгоритм 1 возвращает 100 документов, 90 из которых релевантны. Таким образом,

• Алгоритм 2 возвращает 2000 документов, 90 из которых релевантны. Таким образом,

Скорее всего, мы бы выбрали первый алгоритм, который выдает очень мало False Positive на фоне своего конкурента. Но разница в False Positive Rate между этими двумя алгоритмами крайне мала - всего 0.0019. Это является следствием того, что AUC-ROC измеряет долю False Positive относительно True Negative и в задачах, где нам не так важен второй (больший) класс, может давать не совсем адекватную картину при сравнении алгоритмов.

Для того чтобы поправить положение, вернемся к полноте и точности:

• Алгоритм 1

• Алгоритм 2

Здесь уже заметна существенная разница между двумя алгоритмами - 0.855 в точности!

Precision и recall также используют для построения кривой и, аналогично AUC-ROC, находят площадь под ней.

Здесь можно отметить, что на маленьких датасетах площадь под PR-кривой может быть чересчур оптимистична, потому как вычисляется по методу трапеций, но обычно в таких задачах данных достаточно. За подробностями о взаимоотношениях AUC-ROC и AUC-PR можно обратиться сюда .

Logistic Loss

Особняком стоит логистическая функция потерь, определяемая как:

здесь - это ответ алгоритма на -ом объекте, - истинная метка класса на -ом объекте, а размер выборки.

Подробно про математическую интерпретацию логистической функции потерь уже написано в рамках поста про линейные модели.
Данная метрика нечасто выступает в бизнес-требованиях, но часто - в задачах на kaggle .
Интуитивно можно представить минимизацию logloss как задачу максимизации accuracy путем штрафа за неверные предсказания. Однако необходимо отметить, что logloss крайне сильно штрафует за уверенность классификатора в неверном ответе.

Рассмотрим пример:

def logloss_crutch(y_true, y_pred, eps=1e-15): return - (y_true * np.log(y_pred) + (1 - y_true) * np.log(1 - y_pred)) print("Logloss при неуверенной классификации %f" % logloss_crutch(1, 0.5)) >> Logloss при неуверенной классификации 0.693147 print("Logloss при уверенной классификации и верном ответе %f" % logloss_crutch(1, 0.9)) >> Logloss при уверенной классификации и верном ответе 0.105361 print("Logloss при уверенной классификации и НЕверном ответе %f" % logloss_crutch(1, 0.1)) >> Logloss при уверенной классификации и НЕверном ответе 2.302585

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

Видно, что чем ближе к нулю ответ алгоритма при ground truth = 1, тем выше значение ошибки и круче растёт кривая.

Подытожим:

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

Любой data scientist ежедневно работает с большими объемами данных. Считается, что около 60% – 70% времени занимает первый этап рабочего процесса: очистка, фильтрация и преобразование данных в формат, подходящий для применения алгоритмов машинного обучения. На втором этапе выполняется предобработка и непосредственное обучение моделей. В сегодняшней статье мы сконцентрируемся на втором этапе процесса и рассмотрим различные техники и рекомендации, являющиеся результатом моего участия более чем в 100 соревнованиях по машинному обучению. Несмотря на то, что описанные концепции имеют достаточно общий характер, они будут полезны при решении многих конкретных задач.

Все примеры кода написаны на Python!

Данные

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

Data in Database – данные в базе данных. Data Munging – фильтрация данных. Useful Data – полезные данные. Data Conversion – преобразование данных. Tabular Data – табличные данные. Data – независимые переменные (признаки). Labels – зависимые переменные (целевые переменные).

После того, как данные преобразованы в табличное представление, их можно использовать для обучения моделей. Табличное представление является наиболее распространенным представлением данных в сфере машинного обучения и интеллектуального анализа данных. Строки таблицы являются отдельными объектами (наблюдениями). Столбцы таблицы, содержат независимые переменные (признаки), обозначаемые X , и зависимые (целевые) переменные, обозначаемые y . В зависимости от класса задачи, целевые переменные могут быть представлены как одним, так и несколькими столбцами.

Типы целевых переменных

Целевые переменные определяют класс задачи и могут быть представлены одним из следующих вариантов:

• Один столбец с двоичными значениями: задача двухклассовой классификации (binary classification), каждый объект принадлежит только одному классу.
• Один столбец с действительными значениями: задача регрессии, прогнозируется одна величина.
• Несколько столбцов с двоичными значениями: задача многоклассовой классификации (multi-class classification), каждый объект принадлежит только одному классу.
• Несколько столбцов с действительными значениями: задача регрессии, прогнозируется несколько величин.
• Несколько столбцов с двоичными значениями: задача классификации с пересекающимися классами (multi-label classification), один объект может принадлежать нескольким классам.

Метрика

При решении любой задачи машинного обучения, необходимо иметь возможность оценивать результат, то есть, необходима метрика. Например, для задачи двухклассовой классификации в качестве метрики обычно используется площадь под ROC-кривой (ROC AUC). В случае многоклассовой классификации обычно применяется категорийная кросс-энтропия (categorical cross-entropy). В случае регрессии – среднее квадратов отклонений (mean squared error, MSE).

Мы не будем подробно рассматривать метрики, поскольку они могут быть достаточно разнообразны и выбираются под конкретную задачу.

Библиотеки

Первым делом необходимо установить базовые библиотеки, необходимые для выполнения вычислений, такие как numpy и scipy . Затем можно приступить к установке наиболее популярных библиотек для анализа данных и машинного обучения:

• Исследование и преобразование данных: pandas (http://pandas.pydata.org/).
• Широкий спектр различных алгоритмов машинного обучения: scikit-learn (http://scikit-learn.org/stable/).
• Лучшая реализация градиентного бустинга (gradient boosting): xgboost (https://github.com/dmlc/xgboost).
• Нейронные сети: keras (http://keras.io/).
• Визуализация: matplotlib (http://matplotlib.org/).
• Индикатор прогресса выполнения: tqdm (https://pypi.python.org/pypi/tqdm).

Следует сказать, что я не использую Anaconda (https://www.continuum.io/downloads). Anaconda объединяет в себе большинство популярных библиотек и существенно упрощает процесс установки, но мне необходимо больше свободы. Решать вам. 🙂

Фреймворк для машинного обучения

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

Рисунок из публикации: Такур А., Крон-Гримберге А. AutoCompete: фреймворк для соревнований по машинному обучению. (A. Thakur and A. Krohn-Grimberghe, AutoCompete: A Framework for Machine Learning Competitions.)

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

На первом шаге определяется класс задачи. Это можно сделать, проанализировав целевую переменную. Задача может представлять собой классификацию или регрессию, классификация может быть двухклассовой или многоклассовой, классы могут пересекаться или не пересекаться. После того, как класс задачи определен, мы разделяем исходный набор данных на две части и получаем обучающий набор (training set) и валидационный набор (validation set), как показано на рисунке ниже.

В том случае, если мы имеем дело с классификацией, разделение данных необходимо выполнить таким образом, чтобы в полученных наборах соотношение количеств объектов, относящихся к разным классам, соответствовало этому соотношению для исходного набора данных (stratified splitting). Это легко можно сделать с помощью класса StratifiedKFold библиотеки scikit-learn .

Для задачи регрессии подойдет обычное разделение с помощью класса KFold , который также доступен в библиотеке scikit — learn .

Кроме того, для задачи регрессии существуют более сложные методы разделения данных, обеспечивающие одинаковое распределение целевой переменной в полученных наборах. Эти подходы остаются на самостоятельное рассмотрение читателю.

В примере кода выше размер валидационного набора (eval_size ) составляет 10% от исходного набора данных. Это значение следует выбирать, ориентируясь на объем исходных данных.

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

На следующем шаге мы определяем типы признаков. Наиболее распространены три типа: числовой, категорийный и текстовый. Давайте рассмотрим набор данных из популярной задачи о пассажирах «Титаника» (https://www.kaggle.com/c/titanic/data).

В этом наборе данных столбец survival содержит целевую переменную. На предыдущем шаге мы уже отделили целевую переменную от признаков. Признаки pclass , sex и embarked являются категорийными. Признаки age , sibsp , parch и подобные являются числовыми. Признак name является текстовым. Впрочем, я не думаю, что имя пассажира будет полезно при прогнозировании, выжил этот пассажир или нет.

Числовые признаки не нуждаются в преобразовании. Такие признаки в исходном виде готовы к нормализации и обучению моделей.

Не забудьте, что перед применением OneHotEncoder , необходимо преобразовать категории в числа с помощью LabelEncoder .

Поскольку данные из соревнования «Титаник» не содержат хорошего примера текстового признака, давайте сформулируем общее правило преобразование текстовых признаков. Мы можем объединить все текстовые признаки в один, а затем применить соответствующие алгоритмы, позволяющие преобразовать текст в числовое представление.

Текстовые признаки можно объединить следующим образом:

Затем мы можем выполнить преобразование с помощью класса CountVectorizer или TfidfVectorizer библиотеки scikit-learn .

Как правило, TfidfVectorizer обеспечивает лучший результат, чем CountVectorizer . На практике я выяснил, что следующие значения параметров TfidfVectorizer являются оптимальными в большинстве случаев:

Если вы применяете векторизатор только к обучающему набору, не забудьте сохранить его на диске, чтобы в последствии применить к валидационному набору.

На следующем шаге признаки, полученные в результате описанных выше преобразований, передаются в стекер (stacker). Этот узел фреймворка объединяет все преобразованные признаки в одну матрицу. Обратите внимание, в нашем случае речь идет о стекере признаков (feature stacker), который не следует путать со стекером моделей (model stacker), представляющим другую популярную технологию.

Объединение признаков можно выполнить с помощью функции hstack библиотеки numpy (в случае неразреженных (dense) признаков) или с помощью функции hstack из модуля sparse библиотеки scipy (в случае разреженных (sparse) признаков).

В том случае, если выполняются другие этапы предобработки, например, уменьшение размерности или отбор признаков (будут рассмотрены далее), объединение полученных признаков можно эффективно выполнить с помощью класса FeatureUnion библиотеки scikit — learn .

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

• RandomForestClassifier
• RandomForestRegressor
• ExtraTreesClassifier
• ExtraTreesRegressor
• XGBClassifier
• XGBRegressor

Чтобы применять линейные модели, необходимо выполнить нормализацию признаков с помощью классов Normalizer или StandardScaler библиотеки scikit-learn .

Данные методы нормализации обеспечивают хороший результат только в случае неразреженных (dense) признаков. Чтобы применить StandardScaler к разреженным (sparse) признакам, в качестве параметра необходимо указать with_mean=False .

Если описанные выше шаги обеспечили для нас «хорошую» модель, можно переходить к настройке гиперпараметров. Если же модель нас не удовлетворяет, мы можем продолжить работу с признаками. В частности, в качестве дополнительных шагов мы можем применить различные методы уменьшения размерности.

Чтобы не усложнять, мы не будем рассматривать линейный дискриминантный анализ (linear discriminant analysis, LDA) и квадратичный дискриминантный анализ (quadratic discriminant analysis, QDA). В общем случае, для уменьшения размерности данных применяется метод главных компонент (principal component analysis, PCA). При работе с изображениями следует начинать с 10 – 15 компонент и увеличивать это значение до тех пор, пока результат существенно улучшается. При работе с другими видами данных можно начинать с 50 – 60 компонент.

В случае текстовых данных, после преобразования текста в разреженную матрицу можно применить сингулярное разложение (singular value decomposition, SVD). Реализация сингулярного разложения TruncatedSVD доступна в библиотеке scikit-learn .

Количество компонент сингулярного разложения, которое, как правило, обеспечивает хороший результат в случае признаков, полученных в результате преобразования с помощью CountVectorizer или TfidfVectorizer , составляет 120 – 200. Большее количество компонент позволяет незначительно улучшить результат ценой существенных вычислительных затрат.

Выполнив описанные шаги, не забываем нормализовать признаки, чтобы иметь возможность применять линейные модели. Далее мы можем либо использовать подготовленные признаки для обучения моделей, либо выполнить отбор признаков (feature selection).

Существуют различные методы отбора признаков. Одним из популярных методов является жадный алгоритм отбора признаков (greedy feature selection). Жадный алгоритм имеет описанную далее схему. Шаг 1: обучаем и оцениваем модель на каждом из исходных признаков; отбираем один признак, обеспечивший лучшую оценку. Шаг 2: обучаем и оцениваем модель на парах признаков, состоящих из лучшего признака, отобранного на предыдущем шаге, и каждого из оставшихся признаков; отбираем лучший признак из оставшихся. Повторяем аналогичные шаги, пока не отберем нужное количество признаков, или пока не будет выполнен какой-либо другой критерий. Вариант реализации данного алгоритма, где в качестве метрики используется площадь под ROC-кривой, доступен по следующей ссылке: https://github.com/abhishekkrthakur/greedyFeatureSelection . Следует отметить, что данная реализация неидеальна и требует определенных модификаций под конкретную задачу.

Другим более быстрым методом отбора признаков является отбор с помощью одного из алгоритмов машинного обучения, которые оценивают важность признаков. Например, можно использовать логистическую регрессию (logistic regression) или В дальнейшем отобранные признаки можно использовать для обучения других алгоритмов.

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

Отбор признаков также можно выполнить с помощью алгоритмов на основе градиентного бустинга. Рекомендуется использовать библиотеку xgboost вместо соответствующей реализации из scikit-learn , поскольку реализация xgboost намного более быстрая и масштабируемая.

Алгоритмы RandomForestClassifier , RandomForestRegressor и xgboost также позволяют выполнять отбор признаков в случае разреженных данных.

Другой популярной техникой отбора неотрицательных признаков является отбор на основе критерия хи-квадрат (chi-squared). Реализация этого метода также доступна в библиотеке scikit-learn .

В коде выше мы применяем класс SelectKBest совместно с критерием хи-квадрат (chi 2 ), чтобы отобрать 20 лучших признаков. Количество отбираемых признаков, по сути, является гиперпараметром, который необходимо оптимизировать, чтобы улучшить результат модели.

Не забывайте сохранять все преобразователи, которые вы применяли к обучающему набору. Они понадобятся, чтобы оценить модели на валидационном наборе.

Следующим шагом является выбор алгоритма машинного обучения и настройка гиперпараметров.

В общем случае, выбирая алгоритм машинного обучения, необходимо рассмотреть следующие варианты:

• Классификация:
  • Случайный лес (random forest).
  • Логистическая регрессия (logistic regression).
  • Наивный Байес (naive Bayes).
  • Метод k ближайших соседей (k-nearest neighbors).
• Регрессия:
  • Случайный лес (random forest).
  • Градиентный бустинг (gradient boosting).
  • Линейная регрессия (linear regression).
  • Гребневая регрессия (ridge regression).
  • Lasso-регрессия (lasso regression).
  • Метод опорных векторов (support vector machine).

В таблице ниже представлены основные гиперпараметры каждого алгоритма и диапазоны их оптимальных значений.

Метка RS* в таблице означает, что невозможно указать оптимальные значения и следует выполнить случайный поиск (random search).

Еще раз напомню, не забывайте сохранять все примененные преобразователи:

И не забывайте применять их к валидационному набору:

Рассмотренный нами подход и основанный на нем фреймворк продемонстрировали хорошие результаты на большинстве наборов данных, с которыми мне приходилось работать. Безусловно, при решении очень сложных задач, эта методика не всегда дает хороший результат. Ничто не совершенно, но, обучаясь, мы совершенствуемся. Точно так же, как это происходит в машинном обучении.

Зачастую в практике системного аналитика, составляющего FRD, встречаются вещи неформализуемые. Примером могут быть требования типа:

• Приложение должно работать быстро
• Приложение должно потреблять мало трафика
• Видеоматериал должен быть качественным.

Такие требования, будучи записанными в FRD «как есть», являются чудовищным источником проблем впоследствии. Формализация таких требований — постоянная головная боль аналитика. Обычно аналитик решает задачу в два приема: сначала выдвигается «эквивалентное» формальное требование, затем в процессе общения (с заказчиком, экспертом предметной области и т.п.) доказывается, что такое формальное требование может заменить собой исходное требование. Вообще говоря, полученное нами требование не является функциональным; оно описывает не «что» должна уметь делать система, а «как делать». При этом «как делать» должно быть сформулировано с конкретной качественной характеристикой.

Это была преамбула к тезису о том, что системный аналитик должен хорошо владеть математическим аппаратом и заодно уметь объяснять «математику» заказчику. А теперь рассмотрим пример.

О задаче классификации

Предположим, что мы пишем FRD для системы контекстной рекламы, похожей на Amazon Omakase . Одним из модулей нашей будущей системы будет контекстный анализатор:

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

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

Метрики оценки

Рассмотрим метрики оценки, применимые к задаче классификации. Допустим, что мы знаем правильные категории для некоторого числа документов. Сгруппируем ответы нашего гипотетического анализатора следующим образом:

• Истинно-положительные (true positives ) — те категории, которые мы ожидали увидеть и получили на выходе
• Ложно-положительные (false positives ) — категории, которых быть на выходе не должно и анализатор их ошибочно вернул на выходе
• Ложно-отрицательные (false negatives ) — категории, которые мы ожидали увидеть, но анализатор их не определил
• Истинно-отрицательные (true negatives ) — категории, которых быть на выходе не должно и на выходе анализатора они тоже совершенно правильно отсутствуют.

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

Левая колонка таблицы — это «правильные» сочетания документов и категорий (присутствия которых мы ожидаем на выходе), правая — неправильные. Верхняя строка таблицы — положительные (positive) ответы классификатора, нижняя — отрицательные (в нашем случае — отсутствие категории в ответе). Если число всех пар документ — категория равно N , то нетрудно увидеть, что

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

В числителе мы видим диагональ матрицы — суммарное число правильных ответов, который делится на общее число вопросов. Например, анализатор, давший 9 правильных ответов из 10 возможных, имеет accuracy 90%.

Метрика F 1

Простым примером неприменимости accuracy-метрики является задача определения обувного бренда. Допустим, мы хотим подсчитать число упоминаний обувных брендов в тексте. Рассмотрим задачу классификации, целью которой будет определить, является ли указанная сущность обувным брендом (Timberland, Columbia, Ted Baker, Ralph Lauren и т.п.). Иначе говоря, мы разбиваем сущности в тексте на два класса: A — Обувной бренд, B — Все остальное.

Теперь рассмотрим вырожденный классификатор, который просто возвращает класс B (Все остальное) для любых сущностей. Для этого классификатора число истинно-положительных ответов будет равно 0. Вообще говоря, давайте подумаем на тему, а часто ли при чтении текста в интернете нам встречаются обувные бренды? Оказывается, как ни странно, что в общем случае 99.9999% слов текста не являются обувными брендами . Построим матрицу распределения ответов для выборки в 100.000:

Вычислим его accuracy, который будет равен 99990 / 100000 = 99.99%! Итак, мы легко построили классификатор, который по сути не делает ничего, однако имеет огромный процент правильных ответов. В то же время совершенно понятно, что задачу определения обувного бренда мы не решили. Дело в том, что правильные сущности в нашем тексте сильно «разбавлены» другими словами, которые для классификации никакого значения не имеют. Учитывая этот пример, вполне понятно желание использовать другие метрики. Например, значение tn явно является «мусорным» — оно вроде как означает правильный ответ, но разрастание tn в итоге сильно «подавляет» вклад tp (который нам важен) в формулу accuracy.

Определим меру точности (P, precision) как:

Как нетрудно заметить, мера точности характеризует, сколько полученных от классификатора положительных ответов являются правильными. Чем больше точность, тем меньше число ложных попаданий.

Мера точности, однако, не дает представление о том, все ли правильные ответы вернул классификатор. Для этого существует так называемая мера полноты (R, recall):

Мера полноты характеризует способность классификатора «угадывать» как можно большее число положительных ответов из ожидаемых. Заметим, что ложно-положительные ответы никак не влияют на эту метрику.

Precision и Recall дают довольно исчерпывающую характеристику классификатора, причем «с разных углов». Обычно при построении подобного рода систем приходится все время балансировать между двумя этими метриками. Если вы пытаетесь повысить Recall, делая классификатор более «оптимистичным», это приводит к падению Precision из-за увеличения числа ложно-положительных ответов. Если же вы подкручиваете свой классификатор, делая его более «пессимистичным», например, строже фильтруя результаты, то при росте Precision это вызовет одновременное падение Recall из-за отбраковки какого-то числа правильных ответов. Поэтому удобно для характеристики классификатора использовать одну величину, так называемую метрику F 1:

Фактически это просто среднее гармоническое величин P и R. Метрика F 1 достигает своего максимума 1 (100%), если P = R = 100%.
(нетрудно прикинуть, что для нашего вырожденного классификатора F 1 = 0). Величина F 1 является одной из самых распространенных метрик для подобного рода систем. Именно F 1 мы и будем использовать, чтобы сформулировать пороговое качество нашего анализатора в FRD.

В вычислении F 1 для задачи классификации есть два основных подхода.

• Суммарный F 1 : результаты по всем классам сводим в одну единую таблицу, по которой затем вычисляется метрика F 1 .
• Средний F 1 : для каждого класса формируем свою contingency matrix и свое значение F 1 , затем берем простое арифметическое среднее для всех классов.

Зачем нужен второй способ? Дело в том, что размеры выборки для разных классов могут сильно различаться. Для каких-то классов у нас может быть очень мало примеров, а для каких-то — много. В итоге метрики одного «большого» класса, будучи сведенными в одну общую таблицу, будут «забивать» все остальные. В ситуации, когда мы хотим оценить качество работы системы более-менее равномерно для всех классов, второй вариант подходит лучше.

Обучающая и тестовая выборка

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

Прежде всего, мы должны зафиксировать товарные категории. Ситуация, когда мы гарантируем какую-то величину F 1 , а набор классов при этом может неограниченно расширяться, практически тупиковая. Поэтому дополнительно оговаривается, что набор категорий фиксирован.

Мы вычисляем значение F 1 по заданной выборке, которая известна заранее. Эта выборка обычно называется обучающей . Однако мы не знаем, как поведет себя классификатор на тех данных, которые нам неизвестны. Для этих целей обычно используется так называемая тестовая выборка , иногда называемая golden set . Разница между обучающей и тестовой выборкой чисто умозрительная: ведь имея некоторое множество примеров, мы можем разрезать его на обучающую и тестовую выборку как нам угодно. Но для самообучающихся систем формирование правильной обучающей выборки очень критично. Неправильно подобранные примеры могут сильно повлиять на качество работы системы.

Типична ситуация, когда классификатор показывает хороший результат на обучающей выборке и совершенно провальный — на тестовой выборке. Если наш алгоритм классификации основан на машинном обучении (т.е. зависит от обучающей выборки), мы можем оценить его качество по более сложной «плавающей» схеме. Для этого все имеющиеся у нас примеры делим, скажем, на 10 частей. Изымаем первую часть и используем ее для обучения алгоритма; оставшиеся 90% примеров используем как тестовую выборку и вычисляем значение F 1 . Затем изымаем вторую часть и используем в качестве обучающей; получаем другое значение F 1 , и т.д. В итоге мы получили 10 значений F 1 , теперь берем их среднее арифметическое значение, которое и станет окончательным результатом. Повторюсь, что это способ (называемый также cross-fold validation ) имеет смысл только для алгоритмов, основанных на машинном обучении.

Возвращаясь к написанию FRD, замечаем, что у нас ситуация куда хуже. Мы имеем потенциально неограниченный набор входных данных (все веб-страницы интернета) и нет никакого способа оценить контекст страницы, кроме как участие человека . Таким образом, наша выборка может быть сформирована только вручную, причем сильно зависеть от капризов составителя (а решение о том, отнести ли страницу к какой-то категории, принимает человек). Мы можем оценить меру F 1 на известных нам примерах, но никак не можем узнать F 1 для всех страниц интернета . Поэтому для потенциально неограниченных наборах данных (таких, как веб-страницы, коих неисчислимо много), иногда используют «метод тыка» (unsupervised). Для этого случайным образом выбирают определенное число примеров (страниц) и по ним оператор (человек) составляет правильный набор категорий (классов). Затем мы можем испытать классификатор на этих выбранных примерах. Далее, считая, что выбранные нами примеры являются типичными , мы можем приближенно оценить точность алгоритма (Precision). При этом Recall мы оценить не можем (неизвестно, сколько правильных ответов находятся за пределами выбранных нами примеров), следовательно, не можем вычислить и F 1 .

Таким образом, если мы хотим узнать, как ведет себя алгоритм на всех возможных входных данных, самое лучшее, что сможем оценить в этой ситуации — это приближенное значение Precision. Если же все согласны использовать заранее определенную фиксированную выборку, то можно вычислить средние значение F 1 по этой выборке .

В итоге?

А в итоге нам придется сделать следующее:

1. Зафиксировать обучающую выборку. Обучающая выборка будет построена исходя из представлений заказчика о «правильном» контексте.
2. Зафиксировать набор категорий для нашего анализатора. Не можем же мы вычислять F 1 по неопределенному набору классов?
3. Описать требование в виде: Анализатор должен определять контекст с средней величиной F 1 не менее 80%. (например)
4. Объяснить это заказчику.

Как видим, написать FRD на такую систему нелегко (особенно последний пункт), но возможно. Что касается порогового значения F 1 , в таких случаях можно отталкиваться от значений F 1 для похожих задач классификации.

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

Метрики оценки качества

Полная точность (accuracy)

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

Точность, полнота и F-мера

Такие метрики, как точность (precision) и полнота (recall) впервые получили широкое распространение в оценке качества работы систем решающих задачу информационного поиска. Точность системы в пределах одного класса представляет собой долю объектов действительно принадлежащих определенному классу относительно всех объектов отнесенных системой к этому классу. Полнота выражается как доля найденных классификатором объектов принадлежащих классу относительно всех объектов этого класса . Таблица 4 представляет собой таблицу сопряженности отдельного класса, где TP (true positive) - истинно-положительное решение, TN (true negative) - истинно-отрицательное решение, FP (false positive) - ложно-положительное решение и FN (false negative) - ложно-отрицательное решение.

Таблица 1 - Таблица сопряженности класса объектов

Таким образом, точность и полнота вычисляются как:

F-мера объединяет в себе информацию о точности и полноте оцениваемого алгоритма. Вычисляется она как гармонические среднее показателей точности и полноты:

В силу того, что F-мера вычисляется отдельно для каждого класса ее удобно использовать для поиска и анализа конкретных ошибок алгоритма, для оценки классификации с несколькими классами. При этом в случае большого числа классов необходима характеристика, которая бы агрегировала полноту и точность по всем классам и характеризовала бы общее поведение системы. В данной работе для этой цели применяется следующие агрегированные величины: макро точность (macro precision), которая вычисляется как среднее арифметическое значения точности по всем классам, макро полнотой (macro recall), которая вычисляется как среднее арифметическое значение полноты по всем классам и макро F-мера (Macro F-score), которая является гармоническим средним между ними .

Кросс-валидация

Одним из наиболее распространенных методов для проведения полноценного тестирования и оценки качества работы различных алгоритмов машинного обучения, является скользящий контроль (cross-validation). Для независимой выборки данный метод позволяет получить несмещенную оценку вероятности ошибки в отличие от средней ошибки на обучаемой выборке, которая может являться смещенной оценкой вероятности ошибки из-за переобучения алгоритма . Другим достоинством данной процедуры является способность получения оценки вероятности ошибки алгоритма, при отсутствии специально разработанной для тестирования контрольной выборки.

Допустим, что - множество признаковых описаний объектов, на котором задана конечная выборка прецедентов, где - конечное множество классов. Задано отображение, которое произвольной выборке прецедентов ставит в соответствие алгоритм. Тогда качество работы алгоритма по произвольной выборке прецедентов оценивается с помощью функционала качества:

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