English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
I. Принципы决策树
Дерево решений строится с использованием свойств примера в качестве узлов и значений свойств в качестве ветвей.
Корневой узел дерева решений является свойством с наибольшим информационным объемом среди всех примеров. Средние узлы дерева являются свойствами, которые имеют наибольший информационный объем в подмножестве примеров, являющихся поддеревом от данного узла. Листовые узлы дерева являются значениями классов примеров. Дерево решений является формой представления знаний, представляющей высокую степень обобщения всех данных примеров. Дерево решений может точно определить класс всех примеров и эффективно определить класс новых примеров.
Основная идея алгоритма ID3 для создания дерева решений:
Сначала находим наиболее дискриминирующий атрибут, делим примеры на несколько подмножеств, для каждого подмножества выбираем наиболее дискриминирующий атрибут для разделения, и продолжаем до тех пор, пока все подмножества не будут содержать данные только одного типа. В конце концов, мы получаем дерево решений.
Работа J.R.Quinlan была направлена на введение концепции информации增益 из теории информации, которую он назвал information gain, как меры способности свойства к классификации, и设计了 рекурсивный алгоритм для построения дерева решений.
Примеры помогают лучше понять:
Для проблемы классификации климата свойствами являются:
Погода (A1) значения: солнечно, облачно, дождь
Температура (A2) значения: холодно,适中, тепло
Влажность (A3) значения: высокая, нормальная
Ветер (A4) значения: есть ветер, нет ветра
Каждый пример принадлежит к различным классам, в данном примере их два,分别为 P и N. Примеры классов P и N называются положительными и отрицательными примерами. Комбинация известных положительных и отрицательных примеров образует тренировочный набор.
С помощью алгоритма ID3 можно получить дерево решений для каждого примера в правильной классифицирующей тренировочной выборке, см. изображение ниже.
Листовые узлы决策树 обозначают имя класса, то есть P или N. Другие узлы состоят из свойств примера, каждый различный набор значений свойства соответствует ветви.
Если нужно классифицировать пример, начинаем тестирование с корня дерева, следуя ветвям по значениям свойств, до достижения листовых узлов, при этом пример классифицируется как принадлежащий к классу, обозначенному этим листовым узлом.
Используя диаграмму, рассмотрим конкретный пример:
Однажды утром описание климата было:
Погода: облачно
Температура: холодно
Влажность: Нормально
Ветер: Без ветра
Какой климат он принадлежит?-----------------Из изображения можно определить, что этот пример принадлежит классу P.
ID3 заключается в том, чтобы из обучающего набора данных таблицы construir решающее дерево. На самом деле, может быть несколько решений, которые могут правильно классифицировать обучающий набор данных. Алгоритм ID3 Quinlan может вывести решающее дерево с минимальным количеством узлов.
Алгоритм ID3:
1. Для текущего набора примеров рассчитывается информация о增益 каждого свойства;
2. Выбирается свойство Ak с наибольшим增益 информации;
3. Примеры с одинаковыми значениями свойства Ak объединяются в одно подмножество, количество значений Ak равно количеству подмножеств;
4. Для подмножеств, содержащих как положительные, так и отрицательные примеры, рекурсивно вызывается алгоритм построения дерева;
5. Если подмножество содержит только положительные или отрицательные примеры, пометьте соответствующую ветвь P или N и верните вызов.
Обычно, если涉及到 дерево, часто используется рекурсия.
Для конкретного расчета проблемы классификации климата:
1. Расчет энтропии: где S - множество примеров, P(ui) - вероятность появления класса i:
|S| означает общее количество примеров в наборе примеров S, |ui| означает количество примеров класса ui. Для 9 положительных и 5 отрицательных примеров:
P(u1) = 9/14
P(u2) = 5/14
H(S) = (9/14)log(14/9) + (5/14)log(14/5) = 0,94 бит
2. Расчет информации о增益:
Где A - свойство, Value(A) - множество значений свойства A, v - одно из значений свойства A, Sv - множество примеров S с значением A = v, | Sv | - количество примеров в Sv.
Примером может служить свойство A1, согласно формуле расчета информации о增益, информация о增益 свойства A1 составляет
S=[9+,5-] // В оригинальном наборе примеров всего 14 примеров, 9 положительных, 5 отрицательных
Sясно=[2+,3-]// Примеры с значением A1 ясного неба составляют 5, 2 положительных, 3 отрицательных
Sоблачно=[4+,0-] // Примеры с значением A1 облачно составляют 4, 4 положительных, 0 отрицательных
Sдождь=[3+,2-] // Примеры с значением A1 ясного неба составляют 5, 3 положительных, 2 отрицательных
Следовательно
3. Результат:
Информация о增益 свойства A1 максимальна, поэтому он выбран в качестве корневого узла.
4. Построение корня и листьев решающего дерева
Алгоритм ID3 выбирает свойство с наибольшим增益 информации погоду в качестве корня дерева, разветвляется на три значения погоды в 14 примерах, три ветви соответствуют трем подмножествам,分别是:
Все примеры в S2都属于 класс P, поэтому соответствующая ветвь помечена P, а остальные две подмножества содержат как положительные, так и отрицательные примеры, и вызывается рекурсивно алгоритм построения дерева.
5. Построение дерева рекурсивно
Отдельно для подмножеств S1 и S3 рекурсивно вызывается алгоритм ID3, и для каждого подмножества рассчитывается информация о增益 свойств.
(1) Для S1, наибольшая информация о增益 свойств влажности, поэтому он является корневым узлом ветви, и продолжайте разветвляться вниз. Примеры с высокой влажностью都属于 класс N, ветвь помечена N. Примеры с нормальным значением都属于 класс P, ветвь помечена P.
(2) For S3, the information gain of the wind attribute is the largest, so it is used as the root node of this branch. Further branching, wind takes all N classes when there is wind, and this branch is marked as N. When there is no wind, all are P classes, and this branch is marked as P.
2. Python implementation of decision tree algorithm classification
This code is an example from Chapter 3 of machine learning in action, tested and proven correct.
1. Calculate the shannon value for the given data function:
def calcShannonEnt(dataSet):
# calculate the shannon value
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: # create the dictionary for all of the data
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2) # get the log value
return shannonEnt
2. Create data function
def createDataSet():
dataSet = [[1,1,'yes'],
[1,1, 'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing','flippers']
return dataSet, labels
3. Divide the data set according to the given feature
def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: # abstract the feature reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
4. выбор наилучшего способа разделения данных
def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0])-1 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 for i in range(numFeatures): featList = [example[i] for example in dataSet] uniqueVals = set(featList) newEntropy = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i , value) prob = len(subDataSet)/float(len(dataSet)) newEntropy +=prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
5. рекурсивное создание дерева
функция для поиска класса с наибольшим количеством出现的
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
Функция кода для создания дерева
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
# Типы одинаковые, поэтому классификация останавливается
if classList.count(classList[0]) == len(classList):
return classList[0]
# Пройтись по всем характеристикам и выбрать наиболее частую характеристику
if (len(dataSet[0]) == 1):
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel: {}}
del(labels[bestFeat])
# Получить список, который имеет все свойства
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
Затем в python вводите такую команду в интерпретатор:
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
Результат:
{"no surfacing": {0: 'нет', 1: {'flippers': {0: 'нет', 1: 'да'}}}}
6. Функция для классификации с использованием полезного决策ного дерева
def classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else: classLabel = secondDict[key]
возврат classLabel
В командной строке Python, введите:
trees.classify(myTree, labels, [1, 0])
Получен результат:
'нет'
Ура. Да. Ты это сделал.!!!
Это все содержимое статьи, надеюсь, что это поможет вам в изучении, также希望大家多多支持呐喊教程。
Заявление: данное содержимое предоставлено из Интернета, авторские права принадлежат соответствующему автору. Содержимое предоставлено пользователями Интернета, сайт не имеет права собственности, не был отредактирован вручную и не несет ответственности за связанные с этим юридические вопросы. Если вы обнаружите контент,涉嫌侵犯版权， пожалуйста, отправьте письмо по адресу: notice#oldtoolbag.com (во время отправки письма, пожалуйста, замените # на @) для сообщения о нарушении и предоставьте соответствующие доказательства. При подтверждении факта нарушения сайт немедленно удаляет涉嫌侵权的内容.