make.node <- function(atr.name,cond,list.of.succesors,decision=NA)
{
   list(atr.name = atr.name, cond=cond, list.of.succesors = list.of.succesors, decision=decision);
}

tree.growing <- function (S.x,S.y,split.criterion,stopping.criterion, height=0)
{

  root <- make.node(NA,NA,list(),NA)

  cat("h: ",height,"\n")
  
#  print(S.x);

  if (stopping.criterion(S.x,S.y,height))
  {
    root$decision =  names(sort(table(S.y),decreasing=TRUE))[1]
  }
  else
  {     
     s.c <- split.criterion(1:ncol(S.x),S.x,S.y)

     cat("s.c:", s.c,"\n\n")

     split <- which.max( s.c )

     vals <- unique(S.x[,split])

     for (v in vals) {
        v.att <- S.x[,split]==v

        if(0==sum(v.att)) continue;

        vnode <- tree.growing(S.x[v.att,],S.y[v.att],split.criterion,stopping.criterion,height+1)
        root$atr.name <- split
        vnode$cond <- v
#        vnode$pred <- root
        root$list.of.succesors[[length(root$list.of.succesors)+1]]  <- vnode
     }
  }

  root
}

simple.stopping.criterion <- function (S.x,S.y,height)
{
   (length(unique(S.y)) == 1)
}

entropy <- function(S.y)
{
   tab <- table(S.y)
   sumtab <- sum(tab)
    tab <- tab[tab>0]/sumtab
    

   return(sum(-tab*(log2(tab))))
}

information.gain <- function(S.x, S.y, att)
{
   vals <- unique(S.x[,att])
   ent <- entropy(S.y)
   len <- length(S.y)


   for (v in vals) 
   {
     S.y.v <- S.y[S.x[,att]==v]

     cat("S.y.v",S.y.v,"\n\n\n")


     if (length(S.y.v) > 0)
     {
      cat("ent-pre:",ent,"\n")
      cat("entropy(S.y.v)", entropy(S.y.v),"\n")
      cat("(length(S.y.v))/len",(length(S.y.v))/len,"\n\n\n")

       ent <- ent - (length(S.y.v))/len * entropy(S.y.v)
     }
   }
   return(ent)
}

information.gain.criterion <- function(attrs,S.x,S.y)
{
  for (i in attrs)
  {  

     cat("IG:",information.gain(S.x, S.y, i),"\n\n\n")	

     attrs[i] <- information.gain(S.x, S.y, i)
  }
  attrs
}

#----------------------------------------------------------
mushroom <- read.csv("c:/Users/kony/Desktop/teaching/2015/ZZD/mushroom.csv", header = TRUE, sep = ",", quote = "\"", dec = ".", fill = TRUE, comment.char = "", na.strings = "?")
mushroom.c <- mushroom[complete.cases(mushroom),]
mushroom.y <- mushroom.c[,2]
mushroom.x <- mushroom.c[,-(1:2)]

#----------------------------------------------------------
test <- function ()
{
  tree.growing(mushroom.x[,],mushroom.y[],information.gain.criterion,simple.stopping.criterion)
}
#----------------------------------------------------------
test.tree <- test()

classify <- function(tree, x)
{
   if (!is.na(tree$decision))
   {
      return(tree$decision)
   }
   else
   {
       val <- x[tree$atr.name]

       for (succ in tree$list.of.succesors)
       {
          print(val)
          #cat("val:",val)#,"succcond:",succ$cond,"\n")
          if (val==succ$cond)
          {
             return(classify(succ, x))
          }
       }
       return(NA)    
   }
}

classify(test.tree,mushroom.x[52,])

#trenovaci chyba?

check.error <- function(test.tree, S.x, S.y)
{
   fail <- 0
   success <- 0
   unk <- 0

   for (i in 1:length(S.y))
   {
      res <- classify(test.tree, S.x[i,])

      if (is.na(res))
      {
         unk <- unk + 1
      }
      else if (res == S.y[i])
      {
        success <- success + 1
      }
      else
      {
        fail <- fail + 1
      }
   }
   return(c(success/length(S.y),fail/length(S.y),unk/length(S.y)))
}

check.error(test.tree,mushroom.x,mushroom.y)

#-----------------------------------------------------------------
#odhad trenovaci chyby

#random sample
selection <- sample(nrow(mushroom.x), nrow(mushroom.x)/3)

test.mushroom.x <- mushroom.x[selection,]
train.mushroom.x <- mushroom.x[-selection,]

test.mushroom.y <- mushroom.y[selection]
train.mushroom.y <- mushroom.y[-selection]

test.tree <- tree.growing(train.mushroom.x,train.mushroom.y,information.gain.criterion,simple.stopping.criterion)
check.error(test.tree,test.mushroom.x,test.mushroom.y)


#-----------------------------------------------------------------

k.fold.cross.validation <- function(k,S.x,S.y)
{
  step <- floor(nrow(S.x)/k)

  results <- c(0,0,0)


  for (i in seq(from = 1, by = step, length.out = k))
  {
    test.interval <- i:(i+k)
    test.x <- S.x[test.interval,]
    test.y <- S.y[test.interval]

    train.x <- S.x[-test.interval,] 
    train.y <- S.y[-test.interval]
 
    da.tree <- tree.growing(train.x,train.y,information.gain.criterion,simple.stopping.criterion)
    results <- results + check.error(da.tree,test.x,test.y)    
  }
  return(results/k)
}

k.fold.cross.validation(10,mushroom.x,mushroom.y)

#-----------------------------------------------------------------

tree.height <- function(tree)
{
   if (!is.na(tree$decision))
   {
     return(0)
   }
   else
   {  
      max.subtree.height <- 0
      for (s in tree$list.of.succesors)
      {
         max.subtree.height <- max(max.subtree.height, tree.height(s)) 
      }
      return(1+max.subtree.height)
   }
}

tree.height(test.tree)

#------------------------------------------------------------------

voting <- read.csv("c:/Users/kony/Desktop/teaching/2015/ZZD/voting.csv", header = FALSE, sep = ",", quote = "\"", dec = ".", fill = TRUE, comment.char = "", na.strings = "?")
voting.c <- unique(voting[complete.cases(voting),])
voting.y <- voting.c[,1]
voting.x <- voting.c[,-1]

test.tree <- tree.growing(voting.x,voting.y,information.gain.criterion,simple.stopping.criterion)

for (i in 1:160)
{
   cat(i,":",classify(test.tree,voting.x[3,]),"\n")
}

k.fold.cross.validation(10,voting.x,voting.y)

voting.x
nrow(unique(voting.x))
length(voting.y)

voting.x

#------------------------------------------------------------------

gini <- function(S.y)
{
   tab <- table(S.y)
   sumtab <- sum(tab)
   tab <- tab[tab>0]/sumtab
    

   return(1- sum(tab^2))
}


gini.gain <- function(S.x, S.y, att)
{
   vals <- unique(S.x[,att])
   gin <- gini(S.y)
   len <- length(S.y)


   for (v in vals) 
   {
     S.y.v <- S.y[S.x[,att]==v]

     cat("S.y.v",S.y.v,"\n\n\n")


     if (length(S.y.v) > 0)
     {
      cat("ent-pre:",ent,"\n")
      cat("entropy(S.y.v)", entropy(S.y.v),"\n")
      cat("(length(S.y.v))/len",(length(S.y.v))/len,"\n\n\n")

       gini <- gini - (length(S.y.v))/len * gini(S.y.v)
     }
   }
   return(ent)
}

gini.gain.criterion <- function(attrs,S.x,S.y)
{
  for (i in attrs)
  {  
     attrs[i] <- gini.gain(S.x, S.y, i)
  }
  attrs
}

#------------------------------------------------------------------

misclassification.error <- function(S.y)
{
   tab <- table(S.y)
   sumtab <- sum(tab)
   tab <- tab[tab>0]/sumtab
    

   return(1- max(tab^2))
}


misclassification.error.gain <- function(S.x, S.y, att)
{
   vals <- unique(S.x[,att])
   miss  <- miss(S.y)
   len <- length(S.y)


   for (v in vals) 
   {
     S.y.v <- S.y[S.x[,att]==v]

     cat("S.y.v",S.y.v,"\n\n\n")


     if (length(S.y.v) > 0)
     {
      cat("ent-pre:",ent,"\n")
      cat("entropy(S.y.v)", entropy(S.y.v),"\n")
      cat("(length(S.y.v))/len",(length(S.y.v))/len,"\n\n\n")

       miss  <- miss - (length(S.y.v))/len * miss(S.y.v)
     }
   }
   return(ent)
}

misclassification.error.gain.criterion <- function(attrs,S.x,S.y)
{
  for (i in attrs)
  {  
     attrs[i] <- misclassification.error.gain(S.x, S.y, i)
  }
  attrs
}


height.stopping.criterion <- function (S.x,S.y,height)
{
   (length(unique(S.y)) == 1) || (height == 3)
}

test.tree <- tree.growing(voting.x,voting.y,information.gain.criterion,height.stopping.criterion)

tree.height(test.tree)


k.fold.cross.validation <- function(k,S.x,S.y)
{
  step <- floor(nrow(S.x)/k)

  results <- c(0,0,0)


  for (i in seq(from = 1, by = step, length.out = k))
  {
    test.interval <- i:(i+k)
    test.x <- S.x[test.interval,]
    test.y <- S.y[test.interval]

    train.x <- S.x[-test.interval,] 
    train.y <- S.y[-test.interval]
 
    da.tree <- tree.growing(train.x,train.y,information.gain.criterion,height.stopping.criterion)
    results <- results + check.error(da.tree,test.x,test.y)    
  }
  return(results/k)
}

k.fold.cross.validation(10,voting.x,voting.y)