Дерево решений и случайный лес — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
Строка 216: Строка 216:
 
   '''import''' weka.classifiers.trees.RandomForest;
 
   '''import''' weka.classifiers.trees.RandomForest;
  
   // read dataset
+
   <font color="green">// read dataset</font>
 
   '''var''' trainingDataSet = getDataSet(...);
 
   '''var''' trainingDataSet = getDataSet(...);
 
   '''var''' testingDataSet = getDataSet(...);
 
   '''var''' testingDataSet = getDataSet(...);
   // create random forest classifier
+
   <font color="green">// create random forest classifier</font>
 
   '''var''' forest = new RandomForest();
 
   '''var''' forest = new RandomForest();
 
   forest.setMaxDepth(15);
 
   forest.setMaxDepth(15);
 
   forest.setNumFeatures(2);
 
   forest.setNumFeatures(2);
 
   forest.buildClassifier(trainingDataSet);
 
   forest.buildClassifier(trainingDataSet);
   // evaluate the model on test dataset and print summary
+
   <font color="green">// evaluate the model on test dataset and print summary</font>
 
   '''var''' eval = new Evaluation(trainingDataSet);
 
   '''var''' eval = new Evaluation(trainingDataSet);
 
   eval.evaluateModel(forest, testingDataSet);
 
   eval.evaluateModel(forest, testingDataSet);

Текущая версия на 17:23, 8 апреля 2019

Дерево решений — логический алгоритм классификации, решающий задачи классификации и регрессии. Представляет собой объединение логических условий в структуру дерева.

Дерево решений[править]

Определение:
Дерево решений (англ. decision tree, DT) — алгоритм классификации [math]a(x) = (V_{внутр}, v_0, V_{лист}, S_v, \beta_v)[/math], задающийся деревом (связным ациклическим графом), где:
  • [math] V = V_{внутр} \cup V_{лист} [/math] — множество вершин , [math]v_0 \in V[/math] — корень дерева;
  • [math] S_v : D_v \rightarrow V_v [/math] — функция перехода по значению предиката в множество детей вершины [math]v[/math];
  • [math] \beta_v : X \rightarrow D_v [/math] — предикат ветвления, [math]v \in V_{внутр}[/math] и [math]|D_v| \lt \infty[/math];
  • Для листьев [math]v \in V_{лист}[/math] определена метка класса [math]y_v \in Y[/math].


Определение:
Бинарное дерево решений — частный случай дерева решений, для которого [math] D_v = \{0,1\} [/math].
Классификация объекта [math] x \in X [/math] бинарным решающим деревом
function classify(x):
  [math]v = v_0[/math]
  if [math]\beta_v(x) = 1 [/math] 
     [math]v := R_v[/math]
  else
     [math]v := L_v[/math]
  return [math]y_v[/math]

Информативность ветвления[править]

Для того, чтобы оценивать качество разбиения объектов по предикату [math]\beta[/math], введем понятие информационного выигрыша разбиения.
Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие меры неопределенности распределения.

Определение:
Частотная оценка вероятности класса [math]y[/math] в вершине [math]v \in V_{внутр}[/math] :
[math]p_y = P(y | x \in U) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}[y_i = y][/math]


Определение:
Мера неопределенности (англ. impurity) распределения [math]p_y[/math]:
  • минимальна, когда [math]p_y \in \{0,1\}[/math];
  • максимальна, когда [math]p_y = \frac{1}{|Y|}[/math] для всех [math]y \in Y[/math];
  • не зависит от перенумерации классов
[math]Ф(U) = \sum\nolimits_{y \in Y} p_y L(p_y) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}L(P(y_i | x_i \in U)) \rightarrow min[/math],
где [math]L(p)[/math] убывает и [math]L(1) = 0[/math], например: [math]-log_2(p)[/math], [math]1 - p[/math], [math]1 - p^2[/math]


Примерами мер неопределенности распределения являются:

  • Энтропия: [math]Ф(U) = -\sum\limits_{i}^N p_i log_2p_i[/math], определяется для каждого множества из разбиения, [math]N[/math] — количество возможных классов, и [math]p_i[/math] — вероятность объекта принадлежать [math] i[/math]-ому классу.
  • Критерий Джини: [math]Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)[/math], максимизацию этого критерия можно интерпретировать как максимизацию числа пар объектов одного класса, оказавшихся после разбиения в одном множестве.

Теперь определим суммарную неопределенность распределения в разбиении.

Определение:
Неопределенность распределения [math]P(y_i | x_i \in U_{\beta(x_i)})[/math] после ветвления вершины [math]v[/math] по предикату [math]\beta[/math] и разбиения [math]U = \bigcup_{k \in D_v} U_k[/math]:
[math]Ф(U_0, ... ,U_{D_v}) = \frac{1}{|U|} \sum\nolimits_{k \in D_v} \sum\nolimits_{x_i \in U_k}L(P(y_i | x_i \in U_k)) = \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k)[/math]


Информационный выигрыш от разбиения определяется как изменение неопределенности в системе.

Определение:
Информационный выигрыш от разбиения по предикату [math]\beta[/math]
[math]Gain(\beta, U) = Ф(U) - Ф(U_1, ... ,U_{|D_v|}) = Ф(U) - \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k) \rightarrow max_{\beta \in B} [/math]


Рекурсивный алгоритм построения бинарного дерева решений ID3[править]

Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм [math]ID3[/math] (англ. Induction of Decision Tree) заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату [math]\beta[/math], который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида [math]\beta(x) = [f_j(x) \gt = d_j][/math].
Проще всего записать этот алгоритм в виде рекурсивной процедуры [math]ID3[/math], которая строит дерево по заданной подвыборке [math]U[/math] и возвращает его корневую вершину.

1:function ID3([math]U[/math]):
2:   if [math]for all[/math] [math]u \in U[/math]: [math]y_u = y[/math], [math]y \in Y[/math]
        // создать листовую вершину [math]v[/math] c меткой класса [math]y_v[/math] 
3:      v = createLeafVertex([math]y_v[/math])
4:      return v
     // найти предикат с максимальным информационным выигрышом 
     [math]\beta= \mathrm{arg}\max_{\beta\in B} [/math] Gain([math]\beta[/math], [math]U[/math])
     // разбить выборку на две части [math]U = U_0 \cup U_1[/math] по предикату [math]\beta[/math] 
5:   [math]U_0 := \{x \in U: \beta(x) = 0\}[/math]
6:   [math]U_1 := \{x \in U: \beta(x) = 1\}[/math]
7:   if [math]U_0 = \emptyset[/math] || [math]U_1 = \emptyset[/math] 
        // найти класс, в котором находится большинство объектов из [math]U[/math] 
8:      [math]y_v[/math] = majorClass([math]U[/math])
9:      v = createLeafVertex([math]y_v[/math])
     else
        // создать внутреннюю вершину [math]v[/math]
10:     v = createVertex()
11:     [math]\beta_v = \beta[/math]
12:     [math]S_0[/math] = ID3([math]U_0[/math])
13:     [math]S_1[/math] = ID3([math]U_1[/math])
14:  return [math]v[/math]

Редукция решающих деревьев[править]

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

Предредукция[править]

Предредукция (англ. pre-pruning) или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность [math]I(\beta, U)[/math] для всех возможных предикатов [math]\beta[/math] не дотягивает до заданного порогового значения [math]I_0[/math].
Для этого на шаге 8 алгоритма [math]ID3[/math] условие [math]U_0 = \emptyset[/math] или [math]U_1 = \emptyset[/math] заменяется условием [math]I(\beta, U) \lt = I_0 [/math]. Порог [math]I_0 [/math] является управляющим параметром метода.
Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции.

Постредукция[править]

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

Критерием замены является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов.

Для реализации постредукции контрольная выборка [math]X^k[/math] пропускается через построенное дерево. При этом в каждой внутренней вершине [math]v[/math] запоминается подмножество [math]S_v \subseteq X_k[/math] попавших в неё контрольных объектов. Если [math]S_v = \emptyset [/math], то вершина [math]v[/math] считается ненадёжной и заменяется терминальной по мажоритарному правилу:
в качестве [math]y_v[/math] берётся тот класс, объектов которого больше всего в обучающей подвыборке [math]U[/math], пришедшей в вершину [math]v[/math].
Затем для каждой внутренней вершины [math]v[/math] вычисляется число ошибок, полученных при классификации выборки [math]S_v[/math] следующими способами:

  • [math]r(v)[/math] — классификация поддеревом, растущим из вершины [math]v[/math];
  • [math]r_L(v)[/math] — классификация поддеревом левой дочерней вершины [math]L_v[/math];
  • [math]r_R(v)[/math] — классификация поддеревом правой дочерней вершины [math]R_v[/math];
  • [math]r_c(v)[/math] — отнесение всех объектов выборки [math]S_v[/math] к классу [math]y \in Y[/math].

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

  • сохранить поддерево вершины [math]v[/math];
  • заменить поддерево вершины [math]v[/math] поддеревом левой дочерней вершины [math]L_v[/math];
  • заменить поддерево вершины [math]v[/math] поддеревом правой дочерней вершины [math]R_v[/math];
  • заменить поддерево [math]v[/math] терминальной вершиной класса [math]y_v = \mathrm{arg}\min_{y\in Y}r_c(v) [/math].

Алгоритмы построения деревьев решения[править]

Недостатки рассмотренного алгоритма ID3:

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

Алгоритм CART (англ. Classification And Regression Trees)[править]

  • В отличие от ID3 работает и с непрерывными значениями признаков: на каждом шаге построения дерева последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него. Разбивает объекты на две части;
  • Использует редукцию для избежания переобучения;
  • Обрабатывает пропущенные или аномальные значения признаков.

Алгоритм C4.5[править]

  • Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств;
  • Использует редукцию для избежания переобучения;
  • Обрабатывает пропущенные или аномальные значения признаков.

Случайный лес[править]

Случайный лес — один из примеров объединения классификаторов в ансамбль.
Алгоритм построения случайного леса, состоящего из [math]N[/math] деревьев на основе обучающей выборки [math]X[/math] такой:

for (n: 1,...,N):
   // сгенерировать выборку [math]X_n[/math] c помощью бутстрэпа
   [math]X_n[/math] = bootstrap([math]X[/math])
   // построить решающее дерево [math]t_n[/math] по выборке [math]X_n[/math]
   [math]t_n[/math] = ID3([math]X_n[/math]) 

Итоговый классификатор — [math]a(x) = \frac{1}{N} \sum\limits_{i = 1}^{N} t_i(x)[/math]. Для задачи классификации мы выбираем решение по большинству результатов, выданных классификаторами, а в задаче регрессии — по их среднему значению.

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

Примеры кода[править]

Примеры на языке Python[править]

  • В sklearn.ensemble также представлены методы классификации, основанные на ансамблях, в том числе: бэггинг и случайный лес, которые были описаны выше.


Так, в этом примере создается бэггинг ансамбль из классификаторов KNeighborsClassifier, каждый из которых обучен на случайных подмножествах из 50% объектов из обучающей выборки, и 50% случайно выбранных признаков.

from sklearn.ensemble import BaggingClassifier
from sklearn.neighbors import KNeighborsClassifier
bagging = BaggingClassifier(KNeighborsClassifier(), max_samples=0.5, max_features=0.5)

Пример использования классификатора на случайном лесе: Полную версию кода можно найти здесь

from sklearn import RandomForestClassifier
from sklearn.datasets import make_classification
// сгенерируем случайную обучающую выборку с классификацией по n_classes классам
X, y = make_classification(n_features=2, n_redundant=0, n_informative=2,
                          random_state=1, n_clusters_per_class=1, n_classes=2)
// разбиваем выборку на обучающую и тестовую 
X = StandardScaler().fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4, random_state=42)
// создадим классификатор на случайном лесе, состоящим из n_estimators деревьев
RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1)
clf.fit(X_train, y_train)
score = clf.score(X_test, y_test)

Результат классификации показан на рисунке.

Классификация RandomForestClassifier. Кружочками изображены объекты обучающей выборки, крестиками тестовой выборки. Справа цветом выделены границы принятия решений, в правом нижнем углу — значение accuracy.

Пример на языке Scala[править]

SBT зависимость:

 libraryDependencies += "com.github.haifengl" %% "smile-scala" % "1.5.2"

Пример классификации датасета и вычисления F1 меры[1] используя smile.classification.cart[2]:

 import smile.classification._
 import smile.data._
 import smile.plot._
 import smile.read
 import smile.validation.FMeasure
 val iris: AttributeDataset = read.table("iris.csv", delimiter = ",", response = Some((new NumericAttribute("class"), 2)))
 val x: Array[Array[Double]] = iris.x()
 val y: Array[Int] = iris.y().map(_.toInt)
 val dt: DecisionTree = cart(x, y, 1000)
 val predictions: Array[Int] = x.map(dt.predict)
 val f1Score = new FMeasure().measure(predictions, y)
 plot(x, y, dt)

Пример на языке Java[править]

Пример классификации с применением weka.classifiers.trees.RandomForest[3]

Maven зависимость:

 <dependency>
   <groupId>nz.ac.waikato.cms.weka</groupId>
   <artifactId>weka-stable</artifactId>
   <version>3.8.0</version>
 </dependency>
 import weka.classifiers.evaluation.Evaluation;
 import weka.classifiers.trees.RandomForest;
 // read dataset
 var trainingDataSet = getDataSet(...);
 var testingDataSet = getDataSet(...);
 // create random forest classifier
 var forest = new RandomForest();
 forest.setMaxDepth(15);
 forest.setNumFeatures(2);
 forest.buildClassifier(trainingDataSet);
 // evaluate the model on test dataset and print summary
 var eval = new Evaluation(trainingDataSet);
 eval.evaluateModel(forest, testingDataSet);
 System.out.println(eval.toSummaryString());

См. также[править]

Источники информации[править]

  1. Логические алгоритмы классификации — Лекция К. В. Воронцова
  2. Случайный лес — статья на Medium, Yury Kashnitskiy
  3. Деревья решений — scikit-learn.org
  4. Ансамбли классификаторов — scikit-learn.org.
    1. F1 мера
    2. Smile, Decision Trees
    3. Weka, Random Forest
    Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_решений_и_случайный_лес&oldid=70887»