/ machine learning

KNN - Métodos de clasificación

Revisemos ahora la estrategia conocida como clustering (agrupamiento) para problemas de clasificacion e implementemos una version sencilla en JavaScript

problema

Los métodos de clustering son comunmente utilizados para encontrar asociaciones entre elementos, por ejemplo, supongamos que tenemos una tienda, y la persona encargada de hacer el suministro de los productos trajo nuevos productos, pero no sabemos en que categorías ponerlos, esta categorización de elementos es conocida como clasificación

lógica

Imaginemos el siguiente problema:

Como Project Manager, recién entraste a un proyecto, las cosas no van muy bien, y te gustaría identificar a tus mejores desarrolladores para que ayuden con los problemas más complicados o para apoyar a resolver dudas técnicas al resto del equipo. Pero esta es una pregunta un tanto subjetiva:

  • Perspectiva del Product Owner - Un buen desarrollador es alguien que entrega las cosas en un corto tiempo y funcionales
  • Perspectiva de otro desarrollador - Un buen desarrollador es alguien con grandes conocimientos técnicos, hace código limpio y siempre trata de mejorar la calidad de la solución (sin mencionar las perspecitvas de un Senior, Junior, Lead)

Entonces, decides que las cualidades más sencillas para describir a un desarrollador fuerte inicialmente serán:

  • cantidad de tickets resueltos
  • cantidad de bugs reportados en sus tickets

obteniendo la información

Imaginemos que en el proyecto están utilizando una herramienta para manejo de tickets como Jira ó Redmine, donde podemos obtener esta información fácilmente

Suponiendo que la información base es de un sólo sprint:

team_member,resolved_tickets,bugs_introduced
rocio,8,1
juan,10,2
pedro,5,3
melissa,6,1
pablo,6,5
andres,10,3

Veamos ahora como se ven estos datos en un gráfico de dos dimensiones, en el eje X tenemos la cantidad de tickets resueltos, y en el eje Y tenemos los bugs introducidos

dataset1

Aquí la idea sería que nuestros MVPs serán esas personas que tengan más tickets resueltos (más a la derecha) y menos bugs introducidos (más abajo), por ejemplo:

export

Podemos marcar manualmente a esos dos puntos (posiblemente el tercero de la derecha tambien, pero mantengamos un estándard más alto), así que nuestra información claificada sería ahora:

team_member,resolved_tickets,bugs_introduced,is_mvp
rocio,8,1,true
juan,10,2,false
pedro,5,3,false
melissa,6,1,true
pablo,6,5,false
andres,10,3,false

evolución del problema

Ahora, como PM, pediste más recursos para mejorar la situación y sacar algunos features más en paralelo, reducir la deuda técnica, etc.

Entonces, dejas pasar un sprint y observas sus resultados y quieres clasificarlos utilizando la información anterior

team_member,resolved_tickets,bugs_introduced
jose,6,2
miguel,8,3
nancy,7,1

export--1-

algoritmo

Después de este gran interludio

La idea es encontrar los "vecinos" (puntos) más cercanos de cada punto nuevo, en base a la clasificación de dichos vecinos, se agregará la clase del punto nuevo; la cantidad de vecinos a definir se conoce como K, de aquí el nombre KNN = K Nearest Neighbors (K vecinos más cercanos)

Para calcular los vecinos, utilizaremos la distancia euclidiana, que para la nuestro caso de dos dimensiones (eje x y eje y):

Screenshot-from-2019-11-28-20-10-24

Aunque la fórmula generalizada para N dimensiones es la siguiente:

Screenshot-from-2019-11-28-20-11-48

implementación

Primero definamos una clase para persistir los datos de cada punto

class Point {
  constructor({ x=0, y=0, mvp=false, name='anonymous' }) {
    this.x = x
    this.y = y
    this.mvp = mvp
    this.name = name
  }
}

Función para la distancia euclideana entre dos puntos

const euclideanDistanceFromAToB = ({ pointA, pointB }) => {
  const x1 = pointA.x
  const y1 = pointA.y
  const x2 = pointB.x
  const y2 = pointB.y
  
  const sum = Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)
  
  return Math.sqrt(sum)
}

Necesitamos, también, una forma para clasificar cualquier punto

const classify = ({ point, k=3, labeledData }) => {

  // obtener todas las distancias
  const distances =
    labeledData.map(labeledPoint => {
        const distance = euclideanDistanceFromAToB({
          pointA: point,
          pointB: labeledPoint
        })

        // usamos la distancia para ordenar
        // y la clase para deducir posteriormente
        return { distance, label: labeledPoint.mvp }
      }
    )

  // considerar que la cantidad de elementos tal vez sea menor que K
  const realK = Math.min(distances.length, k)
  console.log('using k', realK)

  // ordenar los resultados (podria ser mejor usando otro tipo de estructura de datos)
  const kNearestPoints = distances.sort((a, b) => a.distance - b.distance).slice(0, realK)

  return decideLabel(kNearestPoints)
}

Para decidir cuál de las clasificaciones de los vecinos cercanos es la que será utilizada puedes considerar varias estrategias, por ejemplo:

  • el punto más cercano
  • la clasificación con mayor ocurrencia (esto puede depender del tamaño de K)

En nuestro caso, utilizaremos la clasificación con mayor ocurrencia:

const decideLabel = knn => {

  const labelCounter = {}

  let maxLabel = null
  let counter = 0

  // cuenta la ocurrencia de cada etiqueta
  knn.forEach(n => {
    labelCounter[n.label] = (labelCounter[n.label] || 0) + 1

    if (labelCounter[n.label] > counter) {
      counter = labelCounter[n.label]
      maxLabel = n.label
    }
  })

  // retornar la clasificacion
  return maxLabel
}

Probando el códig obtenemos las siguientes clasificaciones:

>node  knn-tutorial.js

using k 3
developer jose is mvp? true
using k 3
developer miguel is mvp? false
using k 3
developer nancy is mvp? true

conclusión

El método de clasificación KNN deriva de lógica bastante visual y pragmática para la medición para la clasificación de elementos, sin embargo, esta es muy costosa computacionalmente, como puedes darte cuenta, la cantidad de operaciones es alta y el procesamiento será elevado conforme utilicemos más información

Una ventaja de este método es que es sencillo aumentar la implementación para N dimenciones, esto es, por si queremos agregar más atributos para tomar en consideración, la implementación no variaría mucho de lo que tenemos actualmente

Cabe mencionar que en la implementación mostrada aquí no consideramos la distancia mínima para obtener a un vecino como "cercano", esto es, por ejemplo, si vives en un lugar muy alejado, puede que tu vecino más cercano viva a un kilómetro, esto podría no ser considerado ya un vecino y debería escaparse del conteo final

Esperamos que te haya sido de ayuda, puedes encontrar el código de ejemplo aquí