Update README.md

machinelearning_algorithms
==========================

This repository will contain Java implementation of different machine learning algorithms.

FIRST ONE IS THE ID3

Which Attribute Is the Best Classifier?

The central choice in the ID3 algorithm is selecting  which  attribute to test at each node in the tree. We would like to select the attribute that is most useful for classifying examples. What is a good quantitative measure of the worth of an attribute? We  will  define a  statistical property, called informution gain, that measures how well a given attribute separates the training examples according to their target classification. ID3 uses this information gain measure to select among the candidate attributes at each step while growing the tree. 

ENTROPY MEASURES HOMOGENEITY
In order to define information gain precisely, we begin by defining a measure com- 
monly used in information theory, called entropy, that characterizes the (im)purity 
of an arbitrary collection of examples. Given a collection S, containing positive 
and negative examples of some target concept, the entropy of S relative to this 
boolean classification is 

Entropy(S) =-p(+)log p(+) - p(-)log p(-)


Psuedo Code:
- ID3(Examples, Targetattribute, Attributes) 
 
 /*Examples are the training examples. Targetattribute is the attribute whose value is to be 
    predicted by the tree. Attributes  is a list of other attributes that may be tested by the learned 
     decision tree. Returns a decision tree that correctly classiJies the given Examples. */

- //Create a Root node for the tree 

- If all Examples are positive, Return the single-node tree Root, with label = + 

- If all Examples are negative, Return the single-node tree Root, with label = - 

- If Attributes is empty,  Return the  single-node tree Root, with label = most  common value of Targetattribute in Examples 

- Otherwise Begin 

      - the attribute from Attributes that best* classifies Examples 

      - The decision attribute for Root c A 

      - For each possible value, vi, of A, 

           - Add a new tree branch below Root, corresponding to the test A = vi 

           - Let Examples,, be the subset of Examples that have value vi for A 

           - If Examples,, is empty 

              - Then below this new branch  add  a  leaf  node with label = most common value of Target attribute in        
              Examples 
          
          - Else below this new branch add the subtree 
          
              - ID3(Examples,,, Targetattribute, Attributes - (A))) 
          
          - End 

- Return Root 

Notes:
if  the  target  attribute can  take  on c 
different values, then the  entropy of S relative to this c-wise classification is 
defined as 
C 
Entropy(S) -  -pi log, pi 
i=l 
where pi is the proportion of S belonging  to class i. Note the logarithm is  still 
base 2 because entropy is a  measure of the expected encoding length measured 
in bits. Note also  that if the  target attribute can  take on c possible values, the 
entropy can be as large as log, c.