В статье Топ-10 data mining алгоритмов мы обозначили наиболее популярные алгоритмы дата майнинга. Начинаем с алгоритма C4.5.
Алгоритм C4.5 строит классификатор в форме дерева решений. Чтобы сделать это, ему нужно передать набор уже классифицированных данных.
А что такое классификатор? Классификатор – это инструмент, применяемый в data mining, который использует классифицированные данные и на их основании пытается предсказать, к какому классу стоит отнести новые данные.
Как выглядит пример использования алгоритма? Предположим, что у нас есть набор данных – это данные о группе пациентов. Мы знаем различные параметры каждого пациента: возраст, пульс, кровяное давление, максимальное потребление кислорода, историю семьи и так далее. Эти параметры называются атрибутами.
Теперь:
На основании этих атрибутов мы хотим предсказать, может ли пациент заболеть раком. Пациент может попасть в один из 2 классов: будет болеть раком или не будет болеть раком. Алгоритму C4.5 сообщают класс каждого пациента.
Вот в чем суть:
Используя набор атрибутов пациента и соответствующий класс, C4.5 строит дерево решений, способное предсказать класс для новых пациентов на основании их атрибутов.
А что такое дерево решений? Классификация методом дерева решений создает некое подобие блок-схемы для распределения новых данных. Если вернуться к примеру с пациентом, то ветка блок-схемы может выглядеть так:
- у пациента в истории семьи есть заболевания раком;
- у пациента есть ген, который присутствует у пациентов, больных раком;
- у пациента опухоль;
- размер опухоли больше 5 см.
Таким образом:
В каждой точке блок-схемы задается вопрос о значимости того или иного атрибута, и в зависимости от этих атрибутов он или она [пациенты] попадают в определенный класс.
Требует ли этот метод обучения или он самообучающийся? Этот метод требует обучения, здесь тренировочный набор данных размечается классами. Снова возвращаясь к примеру с пациентами, отметим, что C4.5 не решает самостоятельно, заболеет пациент раком или нет. Как мы уже говорили, он создает дерево решений, которое используется для принятия решений.
Вот отличия C4.5 от других систем, использующих деревья решений:
- Во-первых, C4.5 использует приток информации, при создании дерева решений.
- Во-вторых, хотя другие системы также прореживают ветви дерева решений, C4.5 использует однопроходное прореживание, чтобы избежать переобучения. Отсечение ветвей улучшает модель.
- В третьих, C4.5 может работать с дискретными и непрерывными значениями. Он делает это, ограничивая диапазоны и устанавливая пороги данных, обращая непрерывные данные в дискретные.
- Наконец, пропущенные данные обрабатываются своими собственными способами.
Почему стоит использовать C4.5? Вероятно, самым большим достоинством деревьев решений является их простая интерпретация. Также они имеют довольно высокую скорость работы, а выходные данные легко понимаются человеком.
Где он используется? На OpenTox можно найти реализацию на Java, которая является инструментом для визуализации и анализа в методах data mining. Orange, набор open-source-инструментов для анализа и визуализации результатов дата майнинга, использует C4.5 в своем классификаторе дерева решений.
Pseudocode of C4.5
R код для C4.5/ID3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
C45 <- function(data,x){ result.tree <- NULL if ( IsEmpty(data) ) { node.value <- "Failure" result.tree <- CreateNode(node.value) return(result.tree) } if( IsEmpty(x) ){ node.value <- GetMajorityClassValue(data,x) result.tree <- CreateNode(node.value) return(result.tree) } if( 1 == GetCount(x) ){ node.value <- GetClassValue(x) result.tree <- CreateNode(node.value) return(result.tree) } <br> gain.ratio <- GetGainRatio(data,x)<br> best.split <- GetBestSplit(data,x,gain.ratio) data.subsets <- SplitData(data,best.split) values <- GetAttributeValues(data.subsets,best.split) values.count <- GetCount(values) node.value <- best.split result.tree <- CreateNode(node.value) idx <- 0 while( idx<=values.count ){ i dx <- idx+1 newdata <- GetAt(data.subsets,idx) value <- GetAt(values,idx) new.x <- RemoveAttribute(x,best.split) new.child <- C45(newdata,new.x) AddChildNode(result.tree,new.child,value) } result.tree } |
Алгоритм С4.5 в Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import math import utils def freq(table, col, v): """ Returns counts of variant _v_ in column _col_ of table _table_. """ return table[col].count(v) def info(table, res_col): """ Calculates the entropy of the table _table_ where res_col column = _res_col_. """ s = 0 # sum for v in utils.deldup(table[res_col]): p = freq(table, res_col, v) / float(len(table[res_col])) s += p * math.log(p, 2) return -s def infox(table, col, res_col): """ Calculates the entropy of the table _table_ after dividing it on the subtables by column _col_. """ s = 0 # sum for subt in utils.get_subtables(table, col): s += (float(len(subt[col])) / len(table[col])) * info(subt, res_col) return s def gain(table, x, res_col): """ The criterion for selecting attributes for splitting. """ return info(table, res_col) - infox(table, x, res_col) |
Полную реализацию данного алгоритма в Python можно найти, например, здесь.
Псевдокод алгоритма С4.5 в MapReduce
Алгоритм C4.5 медленно работает на сверхбольших и зашумленных наборах данных.