предисловие
Примечание. Самородки пока не поддерживают латексные формулы, вы можете обратиться к моему блогу:Пак Ючон Trumpet.org/tags/Mac находится в…
В последнее время я намерен систематически изучать основные алгоритмы машинного обучения, поэтому, чтобы избежать своеволия, я решил реализовать все часто используемые базовые алгоритмы машинного обучения для углубления впечатления. Эта статья является первой из этой серии блогов о реализации алгоритма дерева решений (Дерево решений).В этой статье я обобщу алгоритмы, используемые в видах дерева решений, и приложу свой собственный соответствующий код реализации. Все коды алгоритмов и данные, используемые для обучения соответствующих моделей, будут размещены на GitHub (GitHub.com/pgirllab/ml БО…).
В этой статье я шаг за шагом построю дерево решений из набора данных MLiA о рецептах на контактные линзы и визуализирую дерево решений с помощью Graphviz.
текст
обучение дереву решений
Обучение дереву решений - это модель принятия решений, созданная с древовидной структурой в соответствии с атрибутами данных, которую можно использовать для решения задач классификации и регрессии. Общие алгоритмы включают CART (дерево классификации и регрессии), ID3, C4.5 и т. д. Мы часто строим дерево решений на основе набора данных. Одной из его важных задач является извлечение ряда правил для информации о знаниях, содержащейся в данных. Эти правила представляют собой процесс создания древовидной структуры, то есть процесс машинного обучение.
Структура дерева решений
Возьмем в качестве примера следующее простое дерево решений для прогнозирования того, покупать ли компьютер.Внутренние узлы в дереве представляют атрибут, производные от узлов ветви представляют все возможные значения этого атрибута, а конечные узлы представляют окончательные оценка результат, который является типом .
С помощью инструментов визуализации, таких как Graphviz, аннотаций matplotlib и т. д., созданная нами модель дерева решений может быть визуализирована и непосредственно понятна людям, что является функцией, которой нет у таких алгоритмов, как байесовская нейронная сеть.
алгоритм дерева решений
Алгоритм дерева решений в основном относится к алгоритму, который выбирает оптимальный признак при разделении дерева (разделении на набор данных) во время создания дерева решений.чистый, Самый большой принцип:Сделать неупорядоченные данные более упорядоченными
Вот три часто используемых метода:
- получение информации
- коэффициент усиления
- примесь Джини
Прирост информации
Это включает в себя некоторые концепции теории информации: количество информации о событии, информационная энтропия, прирост информации и т. д. Популярное объяснение информации о событии можно найти в описании Чжиху.отвечать
-
Информативность события $i$: отрицательный логарифм вероятности наступления этого события
?TI = -log(P(x_{i}))? -
Информационная энтропия – это количество информации, полученное событием в среднем, то есть математическое ожидание количества информации.
? H = \sum_{i=1}^{n}H(x_{i}) = -\sum_{i=1}^{n}P(x_{i})log(P(x_{i})) ?Любая последовательность может получить информационную энтропию последовательности, то есть после классификации последовательности подсчитывается вероятность каждого типа, а затем вычисляется по приведенной выше формуле, которая реализована на Python следующим образом:
def get_shanno_entropy(self, values): ''' 根据给定列表中的值计算其Shanno Entropy ''' uniq_vals = set(values) val_nums = {key: values.count(key) for key in uniq_vals} probs = [v/len(values) for k, v in val_nums.items()] entropy = sum([-prob*log2(prob) for prob in probs]) return entropy -
получение информации
После того, как мы разделим набор наборов данных, информационная энтропия данных изменится.Мы можем использовать формулу расчета информационной энтропии для расчета информационной энтропии разделенных наборов подданных и расчета их среднего (ожидаемого значения) в качестве сегментации. Информационная энтропия последнего набора данных. Значение уменьшения новой информационной энтропии по сравнению с информационной энтропией неразделенных данных равнополучение информацииДа, здесь я вначале неправильно понял, поэтому код, который я написал, не создает правильное дерево решений.
Предположим, мы делим набор данных $D$ на $k$ частей ${D_{1}, D_{2}, ..., D_{k}}$, информационная энтропия после деления:
? H_{splited} = \sum_{j=1}^{k}P(D_{j})H(D_{j}) = \sum_{j=1}^{k} \frac{len(D_{j})}{len(D)} H(D_{j}) ?
Прирост информации - это интерполяция двух информационных энтропий
? Gain_{splited} = H - H_{splited} ?Здесь я в основном использую получение информации для выбора атрибута.Конкретный код реализации выглядит следующим образом:
def choose_best_split_feature(self, dataset, classes): ''' 根据信息增益确定最好的划分数据的特征 :param dataset: 待划分的数据集 :param classes: 数据集对应的类型 :return: 划分数据的增益最大的属性索引 ''' base_entropy = self.get_shanno_entropy(classes) feat_num = len(dataset[0]) entropy_gains = [] for i in range(feat_num): splited_dict = self.split_dataset(dataset, classes, i) new_entropy = sum([ len(sub_classes)/len(classes)*self.get_shanno_entropy(sub_classes) for _, (_, sub_classes) in splited_dict.items() ]) entropy_gains.append(base_entropy - new_entropy) return entropy_gains.index(max(entropy_gains))
Коэффициент усиления
Коэффициент усиления - это расширение метода получения информации для преодоления слабости слабого обобщения, вызванной увеличением информации. Потому что выборка по приросту информации всегда будет стремиться выбирать признаки с большим количеством ветвей, так что информационная энтропия каждого подмножества будет наименьшей. Например, добавление уникального признака значения идентификатора к каждым данным, а затем классификация в соответствии с этим значением идентификатора — это получение наибольшего прироста информации, так что информационная энтропия в каждом подмножестве равна 0, но такая классификация бессмысленна.Обобщение отсутствует. способность, аналогичная переоснащению.
Следовательно, мы можем найти более подходящий критерий для измерения разделения данных, введя разбивку информации, то есть коэффициент усиления.
Формула для разделения информации выражается как:
?
SplitInfo(D) = \sum{j=1}^{k} \frac{len(D{j})}{len(D)} log(\frac{len(D_{j})}{len(D)})
?
Видно, что чем больше разделены данные, тем больше будет значение разделенной информации.
В это время помещение значения расщепленной информации в знаменатель нейтрализует недостатки прироста информации.
? GianRatio = \frac{Gain}{SplitInfo} ?
Конечно, SplitInfo может приближаться к 0. В это время коэффициент усиления станет очень большим и ненадежным, поэтому иногда необходимо добавить функцию сглаживания к знаменателю. Подробности см. в статьях, перечисленных в справочном разделе.
примесь Джини
Определение примеси Джини:
? I{G}(D) = 1 - \sum{i=1}^{m}p{i}^{2} ?
Где $m$ представляет количество категорий в наборе данных $D$, $p\{i}$ представляет вероятность появления определенного типа. Можно видеть, что когда имеется только один тип, значение примеси Джини равно 0, и в это время примесь является самой низкой.
Примесь Джини для набора данных, разделенного на k подмножеств, можно рассчитать по следующей формуле:
? I{G}^{splited}(D) = \sum{j=1}^{k} \frac{len(D{j})}{len(D)}I{G}(D))?
Из этого мы можем выбрать наибольшее количество атрибутов разделения дерева в соответствии с изменением примеси.
? \Delta I{G} = I{G} - I_{G}^{splited} ?
расщепление дерева
С помощью алгоритма выбора наилучшего атрибута разделения нам необходимо дополнительно разделить дерево в соответствии с выбранным атрибутом. Так называемое разбиение дерева — это просто разделение набора данных в соответствии с выбранными атрибутами, а затем повторный вызов метода выбора атрибутов в разделенном наборе данных для выбора средних атрибутов подмножеств наборов данных. Лучший способ сделать это — рекурсия.
Что касается структуры данных, используемой для представления дерева решений, в Python можно использовать словарь, чтобы легко представить вложенность деревьев решений.Корневой узел дерева — это атрибут, а значение, соответствующее атрибуту, — это новый словарь, где ключ это атрибут Возможные значения , где значение это новое поддерево.
Ниже приведена моя реализация Python для создания дерева решений из набора данных:
def create_tree(self, dataset, classes, feat_names):
''' 根据当前数据集递归创建决策树
:param dataset: 数据集
:param feat_names: 数据集中数据相应的特征名称
:param classes: 数据集中数据相应的类型
:param tree: 以字典形式返回决策树
'''
# 如果数据集中只有一种类型停止树分裂
if len(set(classes)) == 1:
return classes[0]
# 如果遍历完所有特征，返回比例最多的类型
if len(feat_names) == 0:
return get_majority(classes)
# 分裂创建新的子树
tree = {}
best_feat_idx = self.choose_best_split_feature(dataset, classes)
feature = feat_names[best_feat_idx]
tree[feature] = {}
# 创建用于递归创建子树的子数据集
sub_feat_names = feat_names[:]
sub_feat_names.pop(best_feat_idx)
splited_dict = self.split_dataset(dataset, classes, best_feat_idx)
for feat_val, (sub_dataset, sub_classes) in splited_dict.items():
tree[feature][feat_val] = self.create_tree(sub_dataset,
sub_classes,
sub_feat_names)
self.tree = tree
self.feat_names = feat_names
return treeСуществует два условия завершения разделения дерева.
-
Один из них - пройтись по всем свойствам
Видно, что при разбиении дерева длина вектора данных в нашем наборе данных постоянно укорачивается.Когда он укорачивается до 0, это означает, что набор данных исчерпал все атрибуты и не может быть разделен.Когда мы выберите режим в конечном наборе подданных в качестве окончательного результата классификации и поместите его в конечный узел. -
Другое дело, что во вновь разделенном наборе данных есть только один тип.
Если все наборы данных, на которые указывает узел, относятся к одному типу, то нет необходимости разделять их, даже если атрибуты не были пройдены.
Построить дерево решений
Здесь я использовал данные о контактных линзах, прилагаемые к книге MLiA, для создания дерева решений, которое включало состояние глаз пациента и тип контактных линз, рекомендованный врачом.
Сначала импортируйте данные и отделите функции данных того же типа, что и обучающие данные для создания деревьев решений.
from trees import DecisionTreeClassifier
lense_labels = ['age', 'prescript', 'astigmatic', 'tearRate']
X = []
Y = []
with open('lenses.txt', 'r') as f:
for line in f:
comps = line.strip().split('\t')
X.append(comps[: -1])
Y.append(comps[-1])Создайте дерево решений:
clf = DecisionTreeClassifier()
clf.create_tree(X, Y, lense_labels)Посмотрите на результирующее дерево решений:
In [2]: clf.tree
Out[2]:
{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'pre': 'soft',
'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}},
'young': 'soft'}},
'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses',
'presbyopic': 'no lenses',
'young': 'hard'}},
'myope': 'hard'}}}},
'reduced': 'no lenses'}}Визуальное дерево решений
Представление деревьев решений непосредственно с помощью вложенных словарей не просто для понимания людьми.Для визуализации древовидной структуры нам необходимо использовать инструменты визуализации.Здесь я буду использовать Graphviz для визуализации древовидной структуры. Для этого реализована функция генерации содержимого файла Graphviz Dot из дерева, представленного словарем.Общая идея состоит в том, чтобы рекурсивно получить все узлы всего дерева и ребра, соединяющие узлы, а затем записать эти узлы и ребра в файл в формате Dot.drawing.
Рекурсивно получить узлы и ребра дерева, где uuid используется для добавления атрибута id к каждому узлу, чтобы различать узлы с одним и тем же атрибутом.
def get_nodes_edges(self, tree=None, root_node=None):
''' 返回树中所有节点和边
'''
Node = namedtuple('Node', ['id', 'label'])
Edge = namedtuple('Edge', ['start', 'end', 'label'])
if tree is None:
tree = self.tree
if type(tree) is not dict:
return [], []
nodes, edges = [], []
if root_node is None:
label = list(tree.keys())[0]
root_node = Node._make([uuid.uuid4(), label])
nodes.append(root_node)
for edge_label, sub_tree in tree[root_node.label].items():
node_label = list(sub_tree.keys())[0] if type(sub_tree) is dict else sub_tree
sub_node = Node._make([uuid.uuid4(), node_label])
nodes.append(sub_node)
edge = Edge._make([root_node, sub_node, edge_label])
edges.append(edge)
sub_nodes, sub_edges = self.get_nodes_edges(sub_tree, root_node=sub_node)
nodes.extend(sub_nodes)
edges.extend(sub_edges)
return nodes, edgesГенерация содержимого точечного файла
def dotify(self, tree=None):
''' 获取树的Graphviz Dot文件的内容
'''
if tree is None:
tree = self.tree
content = 'digraph decision_tree {\n'
nodes, edges = self.get_nodes_edges(tree)
for node in nodes:
content += ' "{}" [label="{}"];\n'.format(node.id, node.label)
for edge in edges:
start, label, end = edge.start, edge.label, edge.end
content += ' "{}" -> "{}" [label="{}"];\n'.format(start.id, end.id, label)
content += '}'
return contentСодержимое файла Dot, сгенерированного из данных контактных линз, выглядит следующим образом:
digraph decision_tree {
"959b4c0c-1821-446d-94a1-c619c2decfcd" [label="call"];
"18665160-b058-437f-9b2e-05df2eb55661" [label="to"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="your"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="areyouunique"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="02073162414"];
"aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="ham"];
"18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="spam"];
"3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="spam"];
"44d1f972-cd97-4636-b6e6-a389bf560656" [label="spam"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="i"];
"a6f22325-8841-4a81-bc04-4e7485117aa1" [label="spam"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" [label="ldn"];
"51b9477a-0326-4774-8622-24d1d869a283" [label="ham"];
"16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="spam"];
"adb05303-813a-4fe0-bf98-c319eb70be48" [label="spam"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "18665160-b058-437f-9b2e-05df2eb55661" [label="0"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="0"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="0"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="1"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="1"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "44d1f972-cd97-4636-b6e6-a389bf560656" [label="1"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="1"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "a6f22325-8841-4a81-bc04-4e7485117aa1" [label="0"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "c181fe42-fd3c-48db-968a-502f8dd462a4" [label="1"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "51b9477a-0326-4774-8622-24d1d869a283" [label="0"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="1"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "adb05303-813a-4fe0-bf98-c319eb70be48" [label="1"];
}Таким образом, мы можем использовать Graphviz для рисования дерева решений.
with open('lenses.dot', 'w') as f:
dot = clf.tree.dotify()
f.write(dot)dot -Tgif lenses.dot -o lenses.gifЭффект следующий:
Используйте полученное дерево решений для классификации
Прогнозирование неизвестных данных в основном заключается в рекурсивном поиске конечных узлов в соответствии с узлами в дереве. z может быть оптимизирован для рекурсии здесь Код реализован следующим образом:
def classify(self, data_vect, feat_names=None, tree=None):
''' 根据构建的决策树对数据进行分类
'''
if tree is None:
tree = self.tree
if feat_names is None:
feat_names = self.feat_names
# Recursive base case.
if type(tree) is not dict:
return tree
feature = list(tree.keys())[0]
value = data_vect[feat_names.index(feature)]
sub_tree = tree[feature][value]
return self.classify(feat_names, data_vect, sub_tree)Хранение деревьев решений
Дерево решений представлено словарем, поэтому мы можем сохранить его на жестком диске через встроенный модуль pickle или json, а также можем прочитать структуру дерева с жесткого диска, что может сэкономить время построения решения. дерево, когда набор данных большой.
def dump_tree(self, filename, tree=None):
''' 存储决策树
'''
if tree is None:
tree = self.tree
with open(filename, 'w') as f:
pickle.dump(tree, f)
def load_tree(self, filename):
''' 加载树结构
'''
with open(filename, 'r') as f:
tree = pickle.load(f)
self.tree = tree
return treeСуммировать
В данной работе реализована пошаговая реализация дерева решений, в котором для определения оптимальных атрибутов деления используется алгоритм ID3, а построенное дерево решений визуализируется посредством Graphviz. Ссылки на код, связанные с этой статьей:GitHub.com/pgirllab/ml БО…
Ссылаться на:
- «Машинное обучение в действии»
- Серия Data Mining (6) Алгоритм классификации дерева решений