Scala-recog accettato da scala-tools

Per me la buona notizia della settimana è che scala-recog è stato accettato da scala-tools quindi sarà scaricabile e importabile nei progetti scala con sbt, dallo stesso repository che contiene nientepopodimeno che scalaz, scalala, Lift, etc. etc.

scala-recog: flessibilità con logistic regression

In questa wiki page ho messo qualche esempio sulla flessibilità che si può raggiungere usando le stackable modification.

In realtà con la logistic regression con scala-recog era per ottenere più flessibilità senza rinunciare alle ottimizzazioni necessarie per un algoritmo di training.

Ma quel che vorrei raggiungere raggiunge uno sforzo estra di desgin. Mi piacerebbe una libreria molto generale, indipendente dal dominio di applicazione.

Per esempio mi piacerebbe poter scrivere qualcosa tipo:

import org.scalarecog.logisticregression.SigmoidClassifier._  
val myStuff = List( 
                Stuff(3, 2.1, "just"), 
                Stuff(2, 1.1, "an"), 
                Stuff(3, 1.2, "example") 
              )  
val trainingSet = myStuff toTrainingSet ( 
                   _.number, _.number2), _.classLabel 
                  )           
val classifier = trainingSet.train

Ma mi piacerebbe anche raggiungere questo tipo di flessibilità:

val classifier = ( 
    for(stuff <- trainingSet; writer <- stuff.toWriter ) 
  ) train  

(classifier.log) foreach(println(_))

Forse si può prevedendo un supporto per le monadi nei training set. Un esempio di monade può essere questo di Tony Morris.

Alberi di decisione con scala-recog

scala-recog è un progetto open-source che ho creato su Google Code, una libreria di algoritmi di machine learning totalmente scritta in Scala. Uno di questi è ID3, un algoritmo che permette di costruire un albero di decisione basandosi su un training set di elementi già classificati.

Esempio: classificare curricula

Supponiamo di avere un sito per la ricerca di lavoro e vogliamo classificare i curricula inseriti per mostrarli agli utenti che cercano delle determinate figure. Dai curricula si possono estrarre una enomre quantità di dati ma supponiamo di voler estrarre solo questi:

• se il candidato ha delle certificazioni
• se è una persona loquace
• se è iscritto al golf club
• se ha una laurea o un master

e mettiamo tutto in una classe:

  case class Person(
                val hasCertifications : Boolean,
                val isTalkative : Boolean,
                val golfClub : Boolean,
                val hasMasterDegree : Boolean,
                val job : String
               )

  val persons = Person(hasCertifications = true, isTalkative = false, 
                       golfClub = false, hasMasterDegree = true, 
                       job = "Programmer") ::
                Person(hasCertifications = false, isTalkative = false, 
                       golfClub = false, hasMasterDegree = true, 
                       job = "Junior Programmer") ::
                Person(hasCertifications = true, isTalkative = false, 
                       golfClub = false, hasMasterDegree = false, 
                       job = "Programmer") ::
                Person(hasCertifications = false, isTalkative = true, 
                       golfClub = false, hasMasterDegree = true, 
                       job = "Seller") ::
                Person(hasCertifications = false, isTalkative = true, 
                       golfClub = false, hasMasterDegree = false, 
                       job = "Seller") ::
                Person(hasCertifications = true, isTalkative = true, 
                       golfClub = false, hasMasterDegree = false, 
                       job = "Seller") ::
                Person(hasCertifications = false, isTalkative = true, 
                       golfClub = true, hasMasterDegree = true, 
                       job = "CEO") ::
                Person(hasCertifications = false, isTalkative = false, 
                       golfClub = true, hasMasterDegree = false, 
                       job = "CEO") ::
                Person(hasCertifications = false, isTalkative = false, 
                       golfClub = true, hasMasterDegree = false, 
                       job = "CEO") ::
                Nil

Nella lista persons ho messo il mio training set. Per usare l'algoritmo ID3, basta importare l'oggetto giusto e usare la lista come training set:

import org.scalarecog.decisiontree._

def toVector(p : Person) = Vector(p.hasCertifications, p.isTalkative, p.golfClub, p.hasMasterDegree)
val dataset = persons map (p => (toVector(p), p.job))

val tree = new ID3[Boolean,String] buildTree dataset

La funzione toVector server perché la classe ID3 ha bisogno di un Vector.
Ora tree può classificare una nuova persona:

val newPerson = Person(false, false, false, false, "?")
assert(
   tree.classify(toVector(newPerson)) == "Junior Programmer"
)

Ma sarebbe carino visualizzare l'albero di decisione creato da ID3. Con JGraph è semplicissimo e otteniamo questo:

Ehi! È proprio l'algoritmo usato nella vita reale! ^_^
Ecco qui il codice completo:

package scalarecoggraph

import org.scalarecog.decisiontree._
import javax.swing.JFrame
import com.mxgraph.swing.mxGraphComponent
import com.mxgraph.view.mxGraph

class Program(tree : DecisionTree[Vector[Boolean], String], propertyNames : Vector[String]) extends JFrame("ScalaRecog") {
  type Tree = DecisionTree[Vector[Boolean], String]
  type Vertex = (AnyRef, (Double, Double))

  draw()

  def draw() {
    val graph: mxGraph = new mxGraph
    val root = graph.getDefaultParent

    def draw(t : Tree, parentPos : (Double, Double), offset : (Int, Int)) : Vertex = {
      def createVertex(label : String, action : Vertex => Unit = v => {}) : Vertex = {
        val vertexSize = (100, 30)
        val newPos = (parentPos._1 + offset._1, parentPos._2 + offset._2)
        val created = (graph.insertVertex(root, null, label, newPos._1, newPos._2 , vertexSize._1, vertexSize._2), newPos)
        action(created)
        created
      }
      def createEdge(label : String, from : Vertex, to : Vertex) = graph.insertEdge(root, null, label, from._1, to._1)

      t match {
        case a : DecisionLeaf[Vector[Boolean],String] => createVertex(a.label)
        case a : DecisionBranchVector[String,Boolean] =>
          createVertex(propertyNames(a.index), n => {
            for (  ((label, child), index) <- a.branches.zipWithIndex  )
              createEdge(label.toString, n, draw(child, n._2, (120*index, offset._2)))
            })
      }
    }

    graph.getModel.beginUpdate
    try {
      draw(tree, (0, 0), (120, 120))
    }
    finally {
      graph.getModel.endUpdate
    }
    getContentPane.add(new mxGraphComponent(graph))
  }
}

object Program  {

  case class Person(
                val hasCertifications : Boolean,
                val isTalkative : Boolean,
                val golfClub : Boolean,
                val hasMasterDegree : Boolean,
                val job : String
               )

  def main(args : Array[String]) : Unit = {

    val persons = Person(hasCertifications = true, isTalkative = false, golfClub = false, hasMasterDegree = true, job = "Programmer") ::
                  Person(hasCertifications = false, isTalkative = false, golfClub = false, hasMasterDegree = true, job = "Junior Programmer") ::
                  Person(hasCertifications = true, isTalkative = false, golfClub = false, hasMasterDegree = false, job = "Programmer") ::
                  Person(hasCertifications = false, isTalkative = true, golfClub = false, hasMasterDegree = true, job = "Seller") ::
                  Person(hasCertifications = false, isTalkative = true, golfClub = false, hasMasterDegree = false, job = "Seller") ::
                  Person(hasCertifications = true, isTalkative = true, golfClub = false, hasMasterDegree = false, job = "Seller") ::
                  Person(hasCertifications = false, isTalkative = true, golfClub = true, hasMasterDegree = true, job = "CEO") ::
                  Person(hasCertifications = false, isTalkative = false, golfClub = true, hasMasterDegree = false, job = "CEO") ::
                  Person(hasCertifications = false, isTalkative = false, golfClub = true, hasMasterDegree = false, job = "CEO") ::
                  Nil

    def toVector(p : Person) = Vector(p.hasCertifications, p.isTalkative, p.golfClub, p.hasMasterDegree)
    val dataset = persons map (p => (toVector(p), p.job))

    val tree = new ID3[Boolean,String] buildTree dataset

    val newPerson = Person(false, false, false, false, "?")
    assert(
      tree.classify(toVector(newPerson)) == "Junior Programmer"
    )

    val frame = new Program(tree, Vector("Has certifications?", "Is talkative?", "Likes playing golf?", "Has a master degree?"))
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
    frame.setSize(400, 320)
    frame.setVisible(true)
  }
}

algoritmo k-NN: meglio in Scala

Stavo leggendo questo libro su machine learning. È un buon libro ma mi ero stufato della verbosità di Python, con cui sono presentati gli algoritmi, quindi ho scritto un'implementazione dell'algoritmo k-NN in Scala:

package knn

class Knn[TData, TClass,
          TDistance <% Ordered[TDistance] ]
(
  val k : Int,
  val dataset : List[TData],
  val getClassOfData : TData => TClass,
  val getDistance : (TData, TData) => TDistance
)
{
  if(k < 1)
    throw new scala.IllegalArgumentException("k must be positive")

  def classify(data : TData) : TClass = {

    // Compute distances between tested data and dataset items
    val distances = for( d <- dataset ) yield (d, getDistance(d, data))

    // sort data by distance
    val sorted = distances sortBy ( d => d._2 )

    // take first k items
    val firstk = sorted take k

    // group by labels
    val classes = firstk groupBy (d => getClassOfData(d._1))

    // get most frequent label
    val classification = classes maxBy (g => g._2.length)

    classification._1
  }
}

Wow, ho scritto questa classe in dieci minuti funziona con ogni tipo di dataset dove sia definita una distanza e ovviamente una classificazione, come si può vedere con questo test (scritto con ScalaTest):

package knn

import org.scalatest._
import org.scalatest.matchers._
import scala.math._

class KnnTest extends FlatSpec with ShouldMatchers {

  "2nn" should " classify correctly with a sample near two well-known labelled items" in {
    val alg = new Knn(2,
          List((3, "ok"), (18, "ok"), (21, "high"), (64, "high")),
          (i : (Int, String)) => i._2,
          (i1: (Int, String), i2: (Int, String)) => abs(i1._1 - i2._1))

    val classified = alg.classify((4, ""))

    classified should equal ("ok")
  }
}

Naturalmente il codice può essere ottimizzato e generalizzato ma mostra come si possa scrivere codice veramente disaccoppiato e generale in Scala.