Find-S Algorithm – Ruby

I created this a while back. One of the first Machine Learning algorithms that I implemented in Ruby.

Hope it helps people out.


########
# Title: Ruby Implemintation of (Find-S Algorithm)
# Description: Find-S algorithm allows us to get a hypothesis that will categorize
# our data set to its MOST GENERAL FORM.
# Author: Armando Padilla
# California State University Los Angeles
# Computer Science
#
# Email: mando81@prodigy.net
# Home Page: http://www.armando.ws
# ========================================================================
# Find-S: Find S is a Machine Learning Algorithm, one of many, that
# given a set of training data will identify the best hypothesis
# to categorize possitive examples in the data. Note this algorithm will
# ONLY take into account user specifid possitive examples in the MOST SPECIFIC CASE.
#
# LIMITATION: The problem of the Find-S hypothesis is that, it is
# too general and may not take into account noise that the training data may hold.
# Also it can not attain ALL possible hypothesis in our hypothesis space. What is
# the user wanted the most general hypothesis? It also only considers only conjunctive hypothesis.
#===========================================================================
########

#### IGNOR!!! BENCH MARKING IGNOR!!! ####
starttime = Time.now
#############################

hypothesis = Array.new;
data = Array.new;

#Initializa Data to use
data = [[“Sunny”, “Warm”, “Normal”, “Strong”, “Warm”, “Same” , “Yes”],
[“Sunny”, “Warm”, “High” , “Strong”, “Warm”, “Same” , “Yes”],
[“Rainy”, “Cold”, “High” , “Strong”, “Warm”, “Change”, “No”],
[“Sunny”, “Warm”, “High” , “Strong”, “Cold”, “Change”, “Yes”]
];

#Initialize hypothesis
#We set out initial hypothesis to its most Specific Case represented by “%”
hypothesis = [“%”, “%”, “%”, “%”, “%”, “%”];

#Remove all negative records from our data
print “\n——- REMOVING ALL NEGATIVE DATA ———\n”;

i = 0;
lastElement = data[1].size-1;
while(i < data.length)
if(data[i][lastElement].to_s.downcase == “no”)
puts “Removing ::: “+data[i].to_s;
data.delete_at(i);
end
i = i+1;
end

######
# Find S
# For each element check if we can make it a more general term
# to ultimately derive a hypothesis that can classify all data
# % => Most Specific Case
# ? => Most General Case
# => Some Specific Case
#####
k=0;
while(k
change = 0;

i=0;
while(i

if(hypothesis[k].to_s.downcase != data[i][k].to_s.downcase)
hypothesis[k] = data[i][k].to_s;
change = change+1;
end

i=i+1;
end

#if we have changed the value for the attribute in k possition more than
#twice it might be a safe bet that we can generalize that attribute and make
#it ‘?’
if(change > 1)
hypothesis[k] = “?”;
end

k=k+1;
end

########################################
# Displays the Hypothesis that BEST Fits
# our data.
########################################
print “\n\n”;
print “\t– Find-S Hypothesis –\n\t”;
i=0;
while(i
print hypothesis[i]+” “;
i=i+1;
end
print “\n\n”;

### END – BENCH MARK & DISPLAY ###
endtime = Time.now
print “Execution Time: ” + (endtime-starttime).to_s + “\n”;
########################