Рекурсивное построение дерева

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

Определив условие для корневого узла, алгоритм создает две ветви: по одной надо будет идти, когда условие истинно, по другой – когда ложно (рис. 7.2).

Рис. 7.2. Дерево решений после одного расщепления

Наблюдения разбиваются на удовлетворяющие и не удовлетворяющие условию. Для каждой ветви алгоритм определяет, нужно ли разбивать ее далее или мы уже пришли к однозначному заключению. Если какую-то из новых ветвей можно разбить, то с помощью описанного выше метода отыскивается подходящий атрибут. Результат после второго расщепления показан на рис. 7.3.

Рис. 7.3. Дерево решений после двух расщеплений

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

Добавьте в файл treepredict.py функцию buildtree. Она рекурсивно строит дерево, выбирая на каждом шаге наилучший критерий расщепления:

def buildtree(rows,scoref=entropy):

if len(rows)==0: return decisionnode( ) current_score=scoref(rows)

#       Инициализировать переменные для выбора наилучшего критерия best_gain=0.0

best_criteria=None best_sets=None

column_count=len(rows[0])-1 for col in range(0,column_count):

#       Создать список различных значений в этом столбце column_values={}

for row in rows: column_values[row[col]]=1

#       Пробуем разбить множество строк по каждому значению

#       из этого столбца

for value in column_values.keys( ): (set1,set2)=divideset(rows,col,value)

# Информационный выигрыш p=float(len(set1))/len(rows)

gain=current_score-p*scoref(set1)-(1-p)*scoref(set2) if gain>best_gain and len(set1)>0 and len(set2)>0: best_gain=gain best_criteria=(col,value) best_sets=(set1,set2)

#       Создаем подветви if best_gain>0:

trueBranch=buildtree(best_sets[0]) falseBranch=buildtree(best_sets[1])

return decisionnode(col=best_criteria[0],value=best_criteria[1], tb=trueBranch,fb=falseBranch)

else:

return decisionnode(results=uniquecounts(rows)) При первом вызове этой функции передается весь список строк. Она в цикле перебирает все столбцы (кроме последнего, в котором хранится результат) и по каждому значению, присутствующему в текущем столбце, разбивает множество строк на два подмножества. Для каждой пары подмножеств вычисляется средневзвешенная энтропия, для чего энтропия подмножества умножается на число попавших в него строк. Запоминается, у какой пары эта энтропия оказалась самой низкой. Если средневзвешенная энтропия наилучшей пары подмножеств не меньше, чем у текущего множества, то рост этой ветви прекращается и сохраняются счетчики возможных результатов. В противном случае для каждого подмножества снова вызывается buildtree и результаты вызова присоединяются к ветвям true и false, исходящим из текущего узла. В итоге будет построено все дерево.

Описанный алгоритм можно применить к исходному набору данных. Приведенный выше код пригоден как для числовых, так и для дискретных данных. Кроме того, предполагается, что в последнем столбце каждой строки находится результат, поэтому для построения дерева достаточно передать только набор строк: >>> reload(treepredict)

<module ‘treepredict’ from ‘treepredict.py’>

>>> tree=treepredict.buildtree(treepredict.my_data)

Сейчас в переменной tree находится обученное дерево решений. В следующем разделе вы увидите, как построить его визуальное представление, а затем – как с его помощью делать прогнозы.

Отображение дерева

Итак, дерево у нас есть, но что с ним делать? Прежде всего, хотелось бы на него взглянуть. Функция printtree распечатывает дерево в текстовом виде. Представление получается не очень красивым, но это простой способ визуализировать небольшие деревья:

def printtree(tree,indent=”): # Это листовый узел? if tree.results!=None:

print str(tree.results) else:

#      Печатаем критерий

print str(tree.col)+’:’+str(tree.value)+’? ‘

#      Печатаем ветви print indent+’T->’,

printtree(tree.tb,indent+’ ‘) print indent+’F->’, printtree(tree.fb,indent+’ ‘)

Это еще одна рекурсивная функция. Она принимает на входе дерево, которое вернула функция buildtree, и обходит его сверху вниз. Обход прекращается, когда встретился узел, содержащий результаты (results). В противном случае печатается критерий выбора ветви true или false, а потом для каждой ветви снова вызывается printtree с предварительным увеличением ширины отступа.

Если вызвать эту функцию для построенного выше дерева, получится такая картина:

>>> reload(treepredict)

>>> treepredict.printtree(tree)

0:google? T-> 3:21? T-> {‘Premium’: 3} F-> 2:yes? T-> {‘Basic’: 1} F-> {‘None’: 1} F-> 0:slashdot? T-> {‘None’: 3} F-> 2:yes? T-> {‘Basic’: 4} F-> 3:21? T-> {‘Basic’: 1} F-> {‘None’: 3}

Это визуальное представление процедуры, выполняемой деревом решений при попытке классифицировать новый образец. В корневом узле проверяется условие «в столбце 0 находится Google?». Если это условие выполнено, то мы идем по ветви T-> и обнаруживаем, что каждый пользователь, пришедший с Google, становится платным подписчиком, если просмотрел 21 страницу или более. Если условие не выполнено, мы идем по ветви F-> и проверяем условие « в столбце 0 находится Slashdot? ». Так продолжается до тех пор, пока мы не достигнем узла с результатами. Как уже упоминалось выше, возможность увидеть логику рассуждений – одно из существенных достоинств деревьев решений.

Графическое представление

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

Для этого нужно знать полную ширину всех его потомков и глубину узла, чтобы оценить, сколько места по вертикали потребуется для его ветвей. Полная ширина узла равна сумме ширин его дочерних узлов или 1, если дочерних узлов нет:

def getwidth(tree):

if tree.tb==None and tree.fb==None: return 1 return getwidth(tree.tb)+getwidth(tree.fb)

Глубина узла равна 1 плюс глубина самого глубокого из дочерних узлов:

def getdepth(tree):

if tree.tb==None and tree.fb==None: return 0 return max(getdepth(tree.tb),getdepth(tree.fb))+1

Для рисования дерева нам потребуется библиотека Python Imaging Library. Ее можно скачать с сайта http://pythonware.com, а в приложении А приведена дополнительная информация по установке. Добавьте в начало файла treepredict.py следующее предложение:

from PIL import Image,ImageDraw Функция drawtree вычисляет требуемый размер и подготавливает холст. Затем она передает холст и корневой узел дерева функции drawnode. Добавьте ее в файл treepredict.py:

def drawtree(tree,]peg=’tree.]pg’): w=getwidth(tree)*100 h=getdepth(tree)*100+120

img=Image.new(‘RGB’,(w,h),(255,255,255)) draw=ImageDraw.Draw(img)

drawnode(draw,tree,w/2,20) img.save(jpeg,’JPEG’)

Функция drawnode отвечает за изображение узлов дерева решений. Она сначала рисует текущий узел и вычисляет позиции его дочерних узлов, а затем рекурсивно вызывает себя для каждого из дочерних узлов. Добавьте ее в файл treepredict.py:

def drawnode(draw,tree,x,y): if tree.results==None:

#       Вычислить ширину каждой ветви w1=getwidth(tree.fb)*100 w2=getwidth(tree.tb)*100

#       Вычислить, сколько всего места нужно данному узлу left=x-(w1+w2)/2

right=x+(w1+w2)/2

#       Вывести строку, содержащую условие

draw.text((x-20,y-10),str(tree.col)+’:’+str(tree.value),(0,0,0))

#       Нарисовать линии, ведущие к дочерним узлам draw.line((x,y,left+w1/2,y+100),fill=(255,0,0)) draw.line((x,y,right-w2/2,y+100),fill=(255,0,0))

# Нарисовать дочерние узлы drawnode(draw,tree.fb,left+w1/2,y+100) drawnode(draw,tree.tb,right-w2/2,y+100) else:

txt=’ \n’.]oin([‘%s:%d’%v for v in tree.results.items( )]) draw.text((x-20,y),txt,(0,0,0))

Попробуйте нарисовать текущее дерево в интерактивном сеансе:

>>> reload(treepredict)

<module ‘treepredict’ from ‘treepredict.pyc’> >>> treepredict.drawtree(tree,jpeg=’treeview.jpg’)

В результате будет создан файл treeview.jpg, изображенный на рис. 7.4. Метки True и False для ветвей не печатаются, так как они лишь загромождают диаграмму; просто следует иметь в виду, что ветвь True всегда правая. При таком соглашении становится легко следить за процессом рассуждения.

Рис. 7.4. Дерево решений для прогноза платных подписчиков

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100