Выбор наилучшего разбиения

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

#  Вычислить счетчики вхождения каждого результата в множество строк

#  (результат – это последний столбец в каждой строке) def uniquecounts(rows):

results={} for row in rows: # Результат находится в последнем столбце r=row[len(row)-1] if r not in results: results[r]=0 results[r]+=1 return results

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

Коэффициент Джини

Предположим, что есть множество образцов, принадлежащих нескольким категориям. Коэффициентом Джини называется вероятность того, что при случайном выборе образца и категории окажется, что образец не принадлежит к указанной категории. Если все образцы в множестве принадлежат к одной и той же категории, то гипотеза всегда будет верна, поэтому вероятность ошибки равна 0. Если в группе в равной пропорции представлены четыре возможных результата, то в 75% случаев гипотеза окажется неверной, поэтому коэффициент ошибки равен 0,75.

Ниже показана функция для вычисления коэффициента Джини:

#  Вероятность того, что случайный образец принадлежит не к той категории def giniimpurity(rows):

total=len(rows)

counts=uniquecounts(rows)

imp=0

for k1 in counts:

p1=float(counts[k1])/total for k2 in counts: if k1==k2: continue p2=float(counts[k2])/total imp+=p1*p2 return imp

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

Энтропия

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

#  Энтропия вычисляется как сумма p(x)log(p(x)) по всем различным

#  результатам

def entropy(rows): from math import log log2=lambda x:log(x)/log(2) results=uniquecounts(rows) # Теперь вычислим энтропию ent=0.0

for r in results.keys( ):

p=float(results[r])/len(rows) ent=ent-p*log2(p) return ent

Функция entropy вычисляет частоту вхождения каждого образца (количество его вхождений, поделенное на общее число образцов – строк) и применяет следующие формулы:

p(i) = частота вхождения = количество вхождений / количество

строк

Энтропия = сумма p(i) x log(p(i)) по всем результатам Эта величина является мерой того, насколько результаты отличаются друг от друга. Если все они одинаковы (например, вам повезло и все пользователи оформили премиальную подписку), то энтропия равна 0. Чем менее однородны группы, тем выше их энтропия. Наша цель состоит в том, чтобы разбить данные на две новые группы, так чтобы энтропия уменьшилась. Протестируйте метрики, основанные на коэффициенте Джини и на энтропии, в интерактивном сеансе:

>>> reload(treepredict)

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

>>> treepredict.giniimpurity(treepredict.my_data)

0.6328125

>>> treepredict.entropy(treepredict.my_data)

1.5052408149441479

>>> set1,set2=treepredict.divideset(treepredict.my_data,2,’yes’) >>> treepredict.entropy(set1)

1.2987949406953985

>>> treepredict.giniimpurity(set1)

0.53125

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

Вы можете следить за любыми ответами на эту запись через 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