Demonstrate and Implement Candidate Elimination Algorithm !

Question

For a given set of training data examples stored in a .CSV file, implement and demonstrate the Candidate-Elimination algorithm to output a description of the set of all hypotheses consistent with the training examples.

Answer 1

Candidate Elimination

• You can consider this as an extended form of Fund-S algorithm.
• Consider both positive and negative examples.
• Actually, positive examples are used here as Find-S algorithm (Basically they are generalize  from the specification).
• While negative example is specified from generalize form.

Terms Used 

• Concept learning: Concept learning is basically learning task of machine (Learn by Train data)
• General Hypothesis:Not Specifying features to learn machine.
• G= {'?', '?','?','?'...} -Number of attributes 
• Specific Hypothesis: Specifying features to learn machine (Specific feature)
• S= {'pi','pi','pi'...} -Number of pi depends on number of attributes.
• Version Space: It is intermediate of general hypothesis and Specific hypothesis.It not only just written one hypothesis but a set of all possible hypothesis based on training data-set.

Algorithm Concept:

Step1:Load Data set

Step2: Initialize General Hypothesis  and Specific  Hypothesis.

Step3: For each training example 

Step4: If example is positive example 

if attribute_value == hypothesis_value:

Do nothing 

else:

replace attribute value with '?' (Basically generalizing it)

Step5: If example is Negative example 

Make generalize hypothesis more specific.

Implementation of Candidate-Elimination Algorithm

Click Here to download data-set used in this question  

#Importing Important Libraries 

import numpy as np

import pandas as pd

data = pd.DataFrame(data=pd.read_csv('CE.csv'))

print(data)

Output

concepts = np.array(data.iloc[:,0:-1])

target = np.array(data.iloc[:,-1])

print(target)

print(concepts)

Output

Note:- Defining Target and Concepts (Features) to train the model

#Defining Model (Candidate Elimination algorithm concepts)

def learn(concepts, target):

    specific_h = concepts[0].copy()

    print("Initialization of specific_h and general_h")

    print("specific_h: ",specific_h)

    general_h = [["?" for i in range(len(specific_h))] for i in range(len(specific_h))]

    print("general_h: ",general_h)

    print("concepts: ",concepts)

    for i, h in enumerate(concepts):

        if target[i] == "yes":

            for x in range(len(specific_h)):

                #print("h[x]",h[x])

                if h[x] != specific_h[x]:

                    specific_h[x] = '?'

                    general_h[x][x] = '?'

        if target[i] == "no":

            for x in range(len(specific_h)):

                if h[x] != specific_h[x]:

                    general_h[x][x] = specific_h[x]

                else:

                    general_h[x][x] = '?'

    print("\nSteps of Candidate Elimination Algorithm: ",i+1)

    print("Specific_h: ",i+1)

    print(specific_h,"\n")

    print("general_h :", i+1)

    print(general_h)

    indices = [i for i, val in enumerate(general_h) if val == ['?', '?', '?', '?', '?', '?']]

    print("\nIndices",indices)

    for i in indices:

        general_h.remove(['?', '?', '?', '?', '?', '?'])

    return specific_h, general_h

s_final,g_final = learn(concepts, target)

print("\nFinal Specific_h:", s_final, sep="\n")

print("Final General_h:", g_final, sep="\n")

Note:

Output 

Note:- To understand output try to understand Code (Model) concepts

Click here for more programs of  RTU ML LAB

Click here for more programs of  VTU ML & AI LAB