Блог

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

Я написал простую программу на python для вычисления энтропии. Это показано ниже:

 def _E(p, n):
    x = (p/(p n))
    y = (n/(p n))
    return(-1* (x*math.log2(x)) -1* (y*math.log2(y)))
  

Однако предположим, что у нас есть таблица, состоящая из 10 элементов следующим образом:

x = [1, 0, 1, 0, 0, 0, 0, 0, 0, 0]

y = [1, 1, 1, 0, 1, 0, 1, 0, 1, 0]

Где x — атрибут, а y — класс. Здесь P(0) = 0,8 и P(1) = 0,2. Энтропия будет следующей:

Энтропия (x) = 0,8 * _E(5,3) 0,2 * _E(2,0)

Однако второе разделение P(1) отлично классифицировано, и это приводит к математической ошибке, поскольку log2(0) равно отрицательной бесконечности. Как вычисляется энтропия в таких случаях?

Энтропия — это мера примеси.Итак, если узел чистый, это означает, что энтропия равна нулю.

Взгляните на это —

 def information_gain(data, column, cut_point):
    """
    For calculating the goodness of a split. The difference of the entropy of parent and 
    the weighted entropy of children.
    :params:attribute_index, labels of the node t as `labels` and cut point as `cut_point`
    :returns: The net entropy of partition 
    """
    subset1, subset2 = divide_data(data, column, cut_point) 
    lensub1, lensub2 = len(subset1), len(subset2)  
    #if the node is pure return 0 entropy
    if len(subset1) == 0 or len(subset2) == 0:
        return (0, subset1, subset2)     
    weighted_ent = (len(subset1)*entropy(subset1)   len(subset2)*entropy(subset2)) / len(data)  
    return ((entropy(data) - weighted_ent), subset1, subset2)
  

Энтропия разделения измеряет неопределенность, связанную с метками классов в этом разделении. В задаче двоичной классификации (классы = {0,1}) вероятность класса 1 (в вашем тексте, x) может варьироваться от 0 до 1. Энтропия максимальна (со значением 1) при x=0,5. Здесь оба класса равновероятны. Энтропия минимальна, когда один из классов отсутствует, т.Е. Либо x = 0, либо x = 1. Здесь нет неопределенности в отношении класса, следовательно, энтропия равна 0.

График зависимости энтропии (ось y) от x (ось x):

Следующий расчет показывает, как математически обрабатывать вычисление энтропии, когда x = 0 (аналогичный случай, когда x = 1):

В вашей программе вы могли бы рассматривать x = 0 и x = 1 как особые случаи и возвращать 0. Для других значений x приведенное выше уравнение можно использовать напрямую.