Выполнимая задача науки о данных
Эта история является частью моей серии Наука о данных.
В машинном обучении дерево решений является одним из самых основных методов. Его можно использовать для регрессии, а также для классификации в обучении с учителем. Более того, он может иметь дело со всеми видами переменных признаков, такими как непрерывные, дискретные, категориальные и т. д.
Хотя деревья решений технически очень просты, их модели, как правило, хорошо соответствуют данным во многих сценариях, но должны быть тщательно проверены из-за их склонности к переобучению. Еще одним преимуществом деревьев решений по сравнению с другими типами моделей является их прозрачный вывод, который можно использовать даже для представления результата в виде дерева.
В этой статье я хочу показать, как можно реализовать дерево регрессии на Rust с помощью популярного крейта Polars. Реализация не должна быть готова к производству, а должна служить чисто образовательным источником.
«Один из лучших способов изучить тип модели — это реализовать ее».
Алгоритм
Давайте быстро вспомним, как получить дерево регрессии:
Пусть {X_1, X_2, ..., X_n} обозначает набор функций, а Y непрерывную переменную результата. То есть данные состоят из записей, каждая из которых имеет значение для каждой переменной функции и результата.
Цель состоит в том, чтобы построить функцию f, которая сопоставляет каждый набор функций с прогнозируемым результатом: f: (X_1, X_2, ..., X_n) |-> Y
Деревья решений основаны на идее разделения допустимой области признаковых переменных на непересекающиеся подмножества. Это делается следующим образом:
Выберите одну функцию за другой, скажем, X_i, и для этого выберите все возможные разделения s:
L = { j : X_ij < s }
R ={ j : X_ij >= s }
Здесь X_ij обозначает значение X_i для j-й записи. Это разбивает данные на два непересекающихся набора L и R.
Затем мы определяем значения c_L, c_R, которые минимизируют следующую дисперсию:
Поскольку это квадратичные функции в c_L соотв. c_R легко показать, решив первую производную для 0, что оптимальные значения для c_L и c_R являются соответствующими средними значениями:
Мы выбираем функцию X_k вместе с разбиением s_k, для которого указанная выше сумма становится наименьшей.
Другими словами, мы искали функцию вместе с разделением данных, которое лучше всего уменьшает дисперсию при аппроксимации Y константой в каждой области разделения.
Эту процедуру мы рекурсивно применяем в обоих регионах L и R. Поскольку на каждом шаге создаются две новые области, общая структура становится бинарным деревом. Мы останавливаемся, когда либо один из регионов становится пустым, либо достигается заданная максимальная высота дерева. Затем листья дерева образуют раздел допустимого множества и присваивают каждому такому разделу прогнозируемое значение для Y.
Более подробную информацию можно найти здесь".
Выполнение
Это предполагает некоторое знакомство с Rust, но то, что вы можете легко получить здесь.
Как уже было сказано, наша цель здесь — реализовать только самую рудиментарную версию дерева решений. Кроме того, мы используем крейт поляры, который предоставляет очень простые в использовании и эффективные инструменты для обработки больших данных.
Зависимости в cargo.toml будут выглядеть так:
[dependencies]
polars = {version = "0.27.2", features = ["lazy", "csv-file", "describe"] }
Прежде чем перейти к реальному алгоритму, давайте познакомимся с полярами, прочитав некоторые данные из файла CSV:
let mut df = CsvReader::from_path("data/weather/weather.csv")
.expect("problem reading the file")
.has_header(true)
.with_null_values(Some(NullValues::AllColumnsSingle(String::from("NA"))))
.finish()
.unwrap();
df = df.drop_nulls(None).unwrap();
Идея, лежащая в основе Polars, похожа на знаменитый обработчик данных python/pandas. Приведенный выше код считывает данные в DataFrame, принимает во внимание строку заголовка и удаляет все записи, имеющие нулевые значения.
Возвращенный DataFrame позволяет нам легко выполнять манипуляции и ограничения данных.
Затем мы вводим следующие структуры, напоминающие разделение признаков (см. выше) и само дерево решений:
pub struct FeatureSplit {
feature: String,
split: f64,
}
pub struct DecisionTree {
feature_split: Option<FeatureSplit>,
left: Option<Box<DecisionTree>>,
right: Option<Box<DecisionTree>>,
value: f64,
}
Функция, которая будет поддерживать разделение данных на две области, будет следующей:
fn do_split(df: &DataFrame, split: f64, feature: &str) ->
(DataFrame, DataFrame) {
let [mask_1, mask_2] = [
df.column(feature).unwrap().lt_eq(split).unwrap(),
df.column(feature).unwrap().gt(split).unwrap(),
];
(df.filter(&mask_1).unwrap(), df.filter(&mask_2).unwrap())
}
Таким образом, функция представлена своим именем заголовка и разделена f64. Для удобства предполагается, что все наши функции являются непрерывными переменными.
df.column(feature) выбирает соответствующий столбец для данной функции.
df.column(feature).lt_eq(split) создает маску (серию значений true/false), которую можно использовать для разделения DataFrame на df.split(&mask1) для получения нового ограниченного DataFrame.
Для заданной функции нам нужно найти наилучшее разделение. Это можно сделать так:
// returns the best split and the corresponding variance
fn get_optimal_split(df: &DataFrame, feature: &str, outcome: &str)
-> (f64, f64) {
get_unique_values(&df, feature)
.f64()
.unwrap()
.into_iter()
.map(|s| {
let (df_1, df_2) = do_split(df, s.unwrap(), feature);
let [y_1, y_2] = [df_1.column(outcome).unwrap(),
df_2.column(outcome).unwrap()];
(s.unwrap(), compute_r_square(y_1) + compute_r_square(y_2))
})
.min_by(|(_, r_a), (_, r_b)| r_a.total_cmp(r_b))
.unwrap()
}
// returns all uniques values for a given feature
fn get_unique_values(df: &DataFrame, feature: &str) -> Series {
df.column(feature)
.unwrap()
.unique()
.unwrap()
.cast(&DataType::Float64)
.unwrap()
}
fn compute_r_square(y: &Series) -> f64 {
if y.len() > 0 {
let squares = y.sub(y.mean().unwrap());
(&squares * &squares).sum().unwrap()
} else {
0.0
}
}
get_unique_values производит все возможные разбиения для данной функции, а compute_r_square — это просто вычисление дисперсии Y, ограниченное некоторыми регионами. В полярах Series данных, как правило, не типизированы вызовом .f64(), мы можем создать типизированное представление базовых Series.
Как указано в алгоритме, оптимальное разделение должно быть найдено для каждой функции, чтобы получить лучшую функцию с соответствующим лучшим разделением:
fn find_best_feature_and_split(features: &[&str],
df: &DataFrame, outcome: &str) -> FeatureSplit {
let (feature_best, (s_best, _)) = features
.into_iter()
.map(|feature| (feature, get_optimal_split(&df, feature, outcome)))
.min_by(|(_, (_, r_a)), (_, (_, r_b))| r_a.total_cmp(r_b))
.unwrap();
FeatureSplit {
feature: String::from(*feature_best),
split: s_best,
}
}
Это дает нам все доступные методы для реализации построения рекурсивного дерева:
pub fn create_decision_tree(
df: &DataFrame,
features: &[&str],
outcome: &str,
max_height: u8,
level: u8,
) -> Option<Box<DecisionTree>> {
if level > max_height || df.height() == 0 {
None
} else {
let FeatureSplit { feature, split } =
find_best_feature_and_split(&features, &df, outcome);
let feature_split = FeatureSplit {
feature: feature.clone(),
split,
};
let value = df.column(outcome).unwrap().mean().unwrap();
let (df_left, df_right) = do_split(df, split, &feature);
Some(Box::new(DecisionTree {
feature_split: Some(feature_split),
left: create_decision_tree(
&df_left, features, outcome, max_height, level + 1
),
right: create_decision_tree(
&df_right, features, outcome, max_height, level + 1
),
value,
}))
}
}
На каждой итерации он решает либо создать лист и остановиться, либо создать еще один FeatureSplit и рекурсивно продолжить.
Набор данных, на котором я тестировал приведенный выше код, называется этот.
Не придавая этому особого смысла, я просто выбрал несколько столбцов в качестве функций:
let features = [
"Temp9am",
"WindSpeed9am",
"Humidity9am",
"Pressure9am",
"Cloud9am",
];
и использовал это, чтобы предсказать:
let outcome = "Temp3pm";
Вызов нашей реализации для создания дерева высотой 2 вместе с выводом результата:
let decision_tree = create_decision_tree(&df, &features, outcome, 2, 0);
println!("{:#?}", create_decision_tree(&df, &features, outcome, 2, 0));
дает:
Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Temp9am",
split: 14.5,
},
),
left: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Temp9am",
split: 11.3,
},
),
left: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Temp9am",
split: 7.1,
},
),
left: None,
right: None,
value: 13.823134328358208,
},
),
right: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "WindSpeed9am",
split: 7.0,
},
),
left: None,
right: None,
value: 18.8537037037037,
},
),
value: 15.26808510638298,
},
),
right: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Temp9am",
split: 17.1,
},
),
left: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Pressure9am",
split: 1015.8,
},
),
left: None,
right: None,
value: 22.33035714285714,
},
),
right: Some(
DecisionTree {
feature_split: Some(
FeatureSplit {
feature: "Cloud9am",
split: 5.0,
},
),
left: None,
right: None,
value: 27.304761904761904,
},
),
value: 25.315,
},
),
value: 19.55640243902439,
},
)
Конечно, есть лучшие способы представить дерево решений, но приведенное выше выполняет свою задачу в качестве краткого обзора.
Также стоит упомянуть, что в приведенной выше очень элементарной реализации отсутствуют методы оптимизации, такие как обрезка деревьев и другие. На выборке из 25% данных прогнозируемое значение по сравнению с реальным значением выглядит так:
┌─────────┬───────────┐ │ Temp3pm ┆ predicted │ │ --- ┆ --- │ │ f64 ┆ f64 │ ╞═════════╪═══════════╡ │ 18.1 ┆ 13.823134 │ │ 12.4 ┆ 13.823134 │ │ 28.6 ┆ 27.304762 │ │ 13.8 ┆ 13.823134 │ │ ... ┆ ... │ │ 22.0 ┆ 18.853704 │ │ 13.9 ┆ 18.853704 │ │ 25.1 ┆ 27.304762 │ │ 18.8 ┆ 18.853704 │ └─────────┴───────────┘
Как мы увидели, совместно с Polars реализовать дерево решений на Rust — вполне посильная задача. К счастью, помимо образовательных соображений, нам не нужно делать это самостоятельно — уже есть хорошие библиотеки, поддерживающие деревья решений. Но об этом в следующем рассказе.
Спасибо за чтение!
