Дерево решений. 
Методы машинного обучения в задаче распознавания символов

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

Post-fuzzification

Не изменяя алгоритм построения дерева C4.5 [Quinlan, 1993], модифицируем процесс классификации способом, рассмотренным в [Chiang et al., 2001] (так называемый post-fuzzification).

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

Рассмотрение всевозможных путей — полный перебор вершин дерева. Для оптимизации ограничимся локальным лучевым поиском [Рассел, 2006] - продолжением на каждом шаге лишь фиксированного количества путей, у которых в текущий момент самая высокая уверенность.

Ввести уверенности можно следующими способами. Первый — аппроксимировать распределение значений признака в вершинах нормальным распределением:

. (0.3).

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

. (0.4).

В формуле (0.4) , — минимальное и максимальное значение признака среди объектов из .

Random forest

Другим решением является random forest [Breiman, 2001] - голосование деревьев. Прямое его назначение — повышение точности (и в разделе 4 будет показано, что оно присутствует); но, кроме того, это и способ генерации гипотез.

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

Комбинация перечисленных способов

Отметим, что способы 3.3.1 и 3.3.2 могут быть скомбинированы: деревья, входящие в random forest, могут, в свою очередь, также выдавать несколько гипотез. Возможны различные варианты их комбинирования: например, по сумме уверенностей каждой буквы или по её максимуму.

Классификатор на основе решётки формальных понятий

Этот классификатор также может быть включён в состав random forest.