# Machine learning notes - information gain and Shannon entropy

### Concept description

How to divide data sets reasonably? The general principle of dividing data sets is to make disordered data more orderly. One way to organize disordered data is to use information theory to measure information. The change of information before and after dividing the data set is called information gain. Knowing how to calculate the information gain, we can calculate the information gain obtained by dividing the data set by each eigenvalue. The feature with the highest information gain is the best choice.

Before we can evaluate which data partition method is the best data partition, we must learn how to calculate the information gain. The measurement of set information is called Shannon entropy or entropy for short, which comes from Claude Shannon, the father of information theory.

Entropy is defined as the expected value of information. Before clarifying this concept, we must know the definition of information. If the transaction to be classified may be divided into multiple classifications, the information of the symbol xi is defined as  Where p(xi) is the probability of selecting the classification.

In order to calculate entropy, we need to calculate the expected value of information contained in all possible values of all categories, which is obtained by the following formula:

Where n is the number of classifications.

### Partitioning data sets using entropy

In addition to measuring the information entropy, the classification algorithm in machine learning also needs to divide the data set and measure the entropy of the divided data set, so as to judge whether the data set is divided correctly. We will calculate the information entropy of the result of dividing the data set according to each feature, and then judge which feature is the best way to divide the data set.

The following is a simple data set. The first and second columns of each sample are the characteristics respectively, and the last column is the label (fish and non fish)

`[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]`

Code for calculating entropy

```from math import log

def calcShannonEnt(dataSet):
numEntries = len(dataSet)  #
labelCounts = {}
# The following five lines create a dictionary for all possible categories
for featVec in dataSet:
currentLabel = featVec[-1]  #Extract the last item as a label
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1  # There are mistakes in the book
# 0:{"yes":1} 1:{"yes":2}  2:{"no":1} 3:{"no":2} 4:{"no":3}
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries  # Calculation probability
# Find logarithm based on 2
shannonEnt -= prob * log(prob,2) # Decreasing sum entropy
return shannonEnt

# Manual calculation: Ent = -0.4*log(2,0.4)-0.6*log(2,0.6)
# Ent_mannual = -(0.4 * log(0.4,2)) - (0.6 * log(0.6,2))
# print(Ent_mannual)

# Create a dataset
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

def splitDataSet(dataSet,axis,value): # Three input parameters: the data set to be divided, the characteristics of the divided data set, and the value of the characteristics to be returned
# Create a new list object
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:  # Do the following when dataSet[0]=0
# The following three lines are extracted
reducedFeatVec = featVec[:axis]   # featVec[:0] = [], which generates an empty list
reducedFeatVec.extend(featVec[axis + 1:]) # Add elements after index==1: 0 / 1 / 2, skip, 3:1, 4:1
retDataSet.append(reducedFeatVec) #As a whole, add 3: [[1, "no"]], 4: [[1, "no"], [1, "no"]]
return retDataSet

# Select the best data set division method
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # Remove label item
baseEntropy = calcShannonEnt(dataSet) # Computational entropy
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
# The following two lines create a unique list of classification labels
featList = [example[i] for example in dataSet] # i=0:[1,1,1,0,0]  i=1:[1,1,0,1,1]
uniqueVals = set(featList)  # i=0:{0,1}  i=1:{0,1}
newEntropy = 0.0
# The following five lines calculate the information entropy of each division method
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
print(subDataSet)
# i=0:{(0,0),(0,1)} return: [[1, 'no'], [1, 'no']] [[1, "yes"], [1, "yes"], [0, "no"]]
# i=1:{(1,0),(1,1)} return: [[0, "no"] [[1, "yes"], [1, "yes"], [1, "no"], [1, "no"]]
prob = len(subDataSet)/float(len(dataSet))
# i=0:{(0,0),(0,1)} return: 2 / 5 3 / 5
# i=1:{(1,0),(1,1)} return: 1 / 5 4 / 5
newEntropy += prob * calcShannonEnt(subDataSet)  # Note that this is a subDataSet, not a dataSet
print("When i={}The entropy obtained is".format(i),newEntropy)
infoGain = baseEntropy - newEntropy # information gain
if (infoGain > bestInfoGain):
# Calculate the best information gain
bestInfoGain = infoGain
bestFeature = i
return bestFeature

if __name__ == "__main__":
myDat,labels = createDataSet()
a = splitDataSet(myDat,0,0)
# print(a)
b = chooseBestFeatureToSplit(myDat)
print(b)

# Comparison between append() method and extend() method:
# a = [1,2,3]
# b = [4,5,6]
# c = [7,8,9]
# a.append(b)
# print(a) # out:[1, 2, 3, [4, 5, 6]]
# b.extend(c)
# print(b)  # out:[4, 5, 6, 7, 8, 9]```

Operation results

The first one: classify with the first feature and calculate the entropy obtained after classification

[[1, 'no'], [1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]
When i=0, the entropy is 0.550977504326937

The second is to classify with the second feature and calculate the entropy obtained after classification
[[1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
When i=1, the entropy is 0.8

If we divide the data according to the first feature attribute, that is, the first feature with 1 is placed in one group and the first feature with 0 is placed in another group, how is the data consistency? Divide the data set according to the above method. The first marine biological grouping with feature 1 will have two belonging to fish and one belonging to non fish; The other group is all non fish.

If you group according to the second feature, what is the result? The first group of marine animals will have two belonging to fish and two belonging to non fish; The other group had only one non fish. The first partition handles the relevant data well.

Posted by hfzhoulin at Sep 20, 2021 - 2:34 PM
The text passage is a set of notes on machine learning, specifically discussing the concept of information gain and Shannon entropy in the context of data set partitioning. It includes a detailed explanation of the concepts, a simple data set, and Python code to calculate entropy and choose the best feature to split the data set.
no_question

the passage does not contain a direct mathematical question or a request for a calculation. it provides an explanation and code, but does not ask the reader to solve a specific problem or verify a calculation.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Machine learning notes - information gain and Shannon entropy

### Concept description

How to divide data sets reasonably? The general principle of dividing data sets is to make disordered data more orderly. One way to organize disordered data is to use information theory to measure information. The change of information before and after dividing the data set is called information gain. Knowing how to calculate the information gain, we can calculate the information gain obtained by dividing the data set by each eigenvalue. The feature with the highest information gain is the best choice.

Before we can evaluate which data partition method is the best data partition, we must learn how to calculate the information gain. The measurement of set information is called Shannon entropy or entropy for short, which comes from Claude Shannon, the father of information theory.

Entropy is defined as the expected value of information. Before clarifying this concept, we must know the definition of information. If the transaction to be classified may be divided into multiple classifications, the information of the symbol xi is defined as  Where p(xi) is the probability of selecting the classification.

In order to calculate entropy, we need to calculate the expected value of information contained in all possible values of all categories, which is obtained by the following formula:

Where n is the number of classifications.

### Partitioning data sets using entropy

In addition to measuring the information entropy, the classification algorithm in machine learning also needs to divide the data set and measure the entropy of the divided data set, so as to judge whether the data set is divided correctly. We will calculate the information entropy of the result of dividing the data set according to each feature, and then judge which feature is the best way to divide the data set.

The following is a simple data set. The first and second columns of each sample are the characteristics respectively, and the last column is the label (fish and non fish)

`[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]`

Code for calculating entropy

```from math import log

def calcShannonEnt(dataSet):
numEntries = len(dataSet)  #
labelCounts = {}
# The following five lines create a dictionary for all possible categories
for featVec in dataSet:
currentLabel = featVec[-1]  #Extract the last item as a label
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1  # There are mistakes in the book
# 0:{"yes":1} 1:{"yes":2}  2:{"no":1} 3:{"no":2} 4:{"no":3}
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numEntries  # Calculation probability
# Find logarithm based on 2
shannonEnt -= prob * log(prob,2) # Decreasing sum entropy
return shannonEnt

# Manual calculation: Ent = -0.4*log(2,0.4)-0.6*log(2,0.6)
# Ent_mannual = -(0.4 * log(0.4,2)) - (0.6 * log(0.6,2))
# print(Ent_mannual)

# Create a dataset
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

def splitDataSet(dataSet,axis,value): # Three input parameters: the data set to be divided, the characteristics of the divided data set, and the value of the characteristics to be returned
# Create a new list object
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:  # Do the following when dataSet[0]=0
# The following three lines are extracted
reducedFeatVec = featVec[:axis]   # featVec[:0] = [], which generates an empty list
reducedFeatVec.extend(featVec[axis + 1:]) # Add elements after index==1: 0 / 1 / 2, skip, 3:1, 4:1
retDataSet.append(reducedFeatVec) #As a whole, add 3: [[1, "no"]], 4: [[1, "no"], [1, "no"]]
return retDataSet

# Select the best data set division method
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # Remove label item
baseEntropy = calcShannonEnt(dataSet) # Computational entropy
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
# The following two lines create a unique list of classification labels
featList = [example[i] for example in dataSet] # i=0:[1,1,1,0,0]  i=1:[1,1,0,1,1]
uniqueVals = set(featList)  # i=0:{0,1}  i=1:{0,1}
newEntropy = 0.0
# The following five lines calculate the information entropy of each division method
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
print(subDataSet)
# i=0:{(0,0),(0,1)} return: [[1, 'no'], [1, 'no']] [[1, "yes"], [1, "yes"], [0, "no"]]
# i=1:{(1,0),(1,1)} return: [[0, "no"] [[1, "yes"], [1, "yes"], [1, "no"], [1, "no"]]
prob = len(subDataSet)/float(len(dataSet))
# i=0:{(0,0),(0,1)} return: 2 / 5 3 / 5
# i=1:{(1,0),(1,1)} return: 1 / 5 4 / 5
newEntropy += prob * calcShannonEnt(subDataSet)  # Note that this is a subDataSet, not a dataSet
print("When i={}The entropy obtained is".format(i),newEntropy)
infoGain = baseEntropy - newEntropy # information gain
if (infoGain > bestInfoGain):
# Calculate the best information gain
bestInfoGain = infoGain
bestFeature = i
return bestFeature

if __name__ == "__main__":
myDat,labels = createDataSet()
a = splitDataSet(myDat,0,0)
# print(a)
b = chooseBestFeatureToSplit(myDat)
print(b)

# Comparison between append() method and extend() method:
# a = [1,2,3]
# b = [4,5,6]
# c = [7,8,9]
# a.append(b)
# print(a) # out:[1, 2, 3, [4, 5, 6]]
# b.extend(c)
# print(b)  # out:[4, 5, 6, 7, 8, 9]```

Operation results

The first one: classify with the first feature and calculate the entropy obtained after classification

[[1, 'no'], [1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]
When i=0, the entropy is 0.550977504326937

The second is to classify with the second feature and calculate the entropy obtained after classification
[[1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
When i=1, the entropy is 0.8

If we divide the data according to the first feature attribute, that is, the first feature with 1 is placed in one group and the first feature with 0 is placed in another group, how is the data consistency? Divide the data set according to the above method. The first marine biological grouping with feature 1 will have two belonging to fish and one belonging to non fish; The other group is all non fish.

If you group according to the second feature, what is the result? The first group of marine animals will have two belonging to fish and two belonging to non fish; The other group had only one non fish. The first partition handles the relevant data well.

Posted by hfzhoulin at Sep 20, 2021 - 2:34 PM
user
The text passage is a set of notes on machine learning, specifically discussing the concept of information gain and Shannon entropy in the context of data set partitioning. It includes a detailed explanation of the concepts, a simple data set, and Python code to calculate entropy and choose the best feature to split the data set.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or a request for a calculation. It provides an explanation and code, but does not ask the reader to solve a specific problem or verify a calculation.