1
$\begingroup$

Input X: A numpy array whose size gives the number of instances. X contains each instance's attribute value. Y: A numpy array which contains each instance's corresponding target label.

Output : Conditional Entropy

Can you please help me code the conditional entropy calculation dynamically which will further be subracted from total entropy of the given population to find the information gain.

I tried something like the below code example. But the only input data I have are the two numpy arrays. can you please help me correct this ? [code]

def gain(data, attr, target_attr):

    val_freq = {}
    subset_entropy = 0.0                                                   
for record in data:
        if (val_freq.has_key(record[attr])):
            val_freq[record[attr]] += 1.0
        else:
            val_freq[record[attr]]  = 1.0                                 
for val in val_freq.keys():
        val_prob = val_freq[val] / sum(val_freq.values())
        data_subset = [record for record in data if record[attr] == val]
        conditional_entropy += val_prob * entropy(data_subset, target_attr)
$\endgroup$
2
$\begingroup$

Formula for conditional entropy is:

$H(X|Y)=\sum_{v\epsilon values(Y)}P(Y=v)H(X|Y=v)$ for X given Y.

Mutual information of X and Y:

$I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)$ I assume you already know the formula for H(X), the entropy. For more information I would suggest: http://www.cs.cmu.edu/~venkatg/teaching/ITCS-spr2013/notes/lect-jan17.pdf

After knowing these formulas coding part shouldn't be that hard. Python takes care of most of the things for you such as: log(X), when X is matrix python just takes log of every element.

For the sum you can use iterative approach or use np.sum(). If you have a code consider posting it so we can revive and tell you what is wrong, right and how to improve.

$\endgroup$
7
  • $\begingroup$ Hi @J.Smith, Thanks for the input, much appreciated. I added the code example like you said, can you please help me correct it to the input I have ? $\endgroup$ – VishwaV Sep 2 '19 at 22:23
  • $\begingroup$ I've been looking at your code but I didn't really understand how you tried to make it work. Are those fors inside the function? But I found a resource for you. github.com/gregversteeg/NPEET/blob/master/npeet/… This is a python library that contains everything you are trying to do know. Implementations are there, you may get a correct idea from there. $\endgroup$ – J.Smith Sep 2 '19 at 23:09
  • $\begingroup$ Hi @J.Smith, Yeah those fors are inside the function. I went through the link you gave, my problem is that the only packages I'm allowed to use are math, numpy and collections packages. The use of other packages are forbidden in the question. $\endgroup$ – VishwaV Sep 2 '19 at 23:14
  • $\begingroup$ @VishwaV I don't say use the library. Look at the implementation of the library. They have written the functions you are trying to write, with just using numpy, math, and scipy. For example 'centropy' function is what you are trying to find out. Get the idea from that function, and implement your own. You can just copy paste but you wouldn't learn anything. $\endgroup$ – J.Smith Sep 2 '19 at 23:31
  • $\begingroup$ Yeah got it, will try this out and get back to you. Thanks @J.Smith, much appreciated. $\endgroup$ – VishwaV Sep 2 '19 at 23:41
4
$\begingroup$
##Entropy
def entropy(Y):
    """
    Also known as Shanon Entropy
    Reference: https://en.wikipedia.org/wiki/Entropy_(information_theory)
    """
    unique, count = np.unique(Y, return_counts=True, axis=0)
    prob = count/len(Y)
    en = np.sum((-1)*prob*np.log2(prob))
    return en


#Joint Entropy
def jEntropy(Y,X):
    """
    H(Y;X)
    Reference: https://en.wikipedia.org/wiki/Joint_entropy
    """
    YX = np.c_[Y,X]
    return entropy(YX)

#Conditional Entropy
def cEntropy(Y, X):
    """
    conditional entropy = Joint Entropy - Entropy of X
    H(Y|X) = H(Y;X) - H(X)
    Reference: https://en.wikipedia.org/wiki/Conditional_entropy
    """
    return jEntropy(Y, X) - entropy(X)


#Information Gain
def gain(Y, X):
    """
    Information Gain, I(Y;X) = H(Y) - H(Y|X)
    Reference: https://en.wikipedia.org/wiki/Information_gain_in_decision_trees#Formal_definition
    """
    return entropy(Y) - cEntropy(Y,X)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.