César D. Rodas

Siguiendo la serie de entradas que comencé hace unos días atrás con Pensando en paralelo - Introducción a Map/Reduce, hoy voy a escribir sobre una de las maneras de sugerir amigos para una red social, o cual otra aplicación que puedan encontrar.

Antes que nada, hago una pequeña introducción hacia mi proyecto PHPCluster. Básicamente proyecto implementa (o trata) algoritmos para la clusterización de datos, que hablando mal y rápido son técnicas para encontrar elementos similares en grandes conjuntos sin tener conocimiento previo de ninguno de los datos . Hasta ahora implemente dos algoritmos, el K-means (actualmente esta en funcionamiento, y lo estoy optimizando con algunas ideas raras que me vienen a la cabeza) y el Biclustering (no esta funcionando es solo un esbozo ya que su eficiente computación es complicada).

Algunas aplicaciones practicas son, por ejemplo, buscar textos (entradas de blogs, noticias, sitios webs, etc) similares, algunas de mis ultimas y mejores pruebas pueden ser vistas en mi wiki-privado de proyectos. En este caso daré un enfoque diferente para resolver el el problema de sugerir potenciales amigos a usuarios.

require "phpcluster/k-means.php";

/**
 *  Clase descendiente de KMeans que sobre-escribe el método getFeatures,
 *  ya que la clase KMeans esta preparada para utilizar palabras como "features".
 */
final class GroupOfFriends extends KMeans
{
    protected function getFeatures($friends)
    {
        $ids = explode(" ", $friends);
        return array_combine($ids, array_fill(0,count($ids), 1));
    }
}

Ahora con su propio dataset, o podrían utilizar el que yo utilice, deberían codificar la búsqueda de usuarios similares basado en amigos. Del resultado de la búsqueda saldrán algunos grupos de usuarios (en mis pruebas fueron 42 grupos). Obj: Este programa debe ser ejecutado desde la consola, nunca jamas desde Apache o algún otro webserver ya que tarda algún tiempo

$fsuggest = new GroupOfFriends;
/* cuantos grupos de usuarios quiero buscar*/
$fsuggest->setCentroids(60);
/* porcentaje de similitud entre usuarios */
$fsuggest->setThreshold(45);

foreach(file("friendship-dataset.txt") as $line) {
    list($id, $friend) = explode("\t", trim($line), 2);
    $fsuggest->addElement($id, $friend);
}

/* a buscar los usuarios similares */
$clusters = $fsuggest->doCluster(300);

En uno de los grupos, al pertenece mi usuario, tuvo a los siguiente miembros, y me sorprendió mi idea ya que a casi todos los usuarios los conozco y todos somos informáticos (o casi todos). @pabloacastillo, @diegoplus, @crodas, @javox, @alejandroValdez, @willin64, @randallflagg, @eliaya, @bocho, @Robez, @xgurix, @chi83, @flyestudios. Dicha similitud de intereses no necesariamente significa que yo (@crodas) debería seguir a dichos usuarios, porque lo mas probable es que ya lo este haciendo (en este caso solo a 3 personas no les sigo en Twitter), sino que también a las personas que ellos siguen y que yo no son los potenciales amigos míos.

El resultado de la clusterizacion esta retornada en $cluster, que simplemente es una matriz que contiene como indice el numero de cluster (o grupo) y como valor una matriz con los usuarios que pertenecen al grupo. Como podrán notar, no todos los usuarios tienen un grupo, eso es gracias al $threshold lo cual asegura la calidad del clustering y a la vez reduce notablemente el numero de iteraciones. Como lo explicado en el párrafo anterior, esto no significa que el sistema no podrá sugerir potenciales amigos a dichos usuarios o a nuevos usuarios. El valor de $cluster debe ser guardar guardo en un medio persistente, para este ejemplo lo haré con json_* pero para la vida una base de datos MySQL o CouchDB son mejores alternativas.

Antes de guardar la informacion obtenida mediante el agrupamiento, son necesarios algunos pasos para hacer optima su lectura al momento de buscar amigos para una cierta persona. La primera es crear modelos de usuarios [1], porque es mas rápido comprar un usuario (a sugerirle amigos) contra esos modelos (en mis pruebas no pasaron de los 46) que comprarlo contra 7926 (la cantidad de usuarios en el dataset de pruebas). Los modelos de usuarios se forman a partir de los grupos de usuarios descubiertos, y tienen como amigos a todos los amigos de los usuarios en el grupo, si les parece confuso, miren el siguiente código:

function Array_Merge_ex1(&$arr, $arr1)
{
    foreach ($arr1 as $value) {
        if (!isset($arr[$value])) {
            $arr[$value] = 0;
        }
       $arr[$value] += 1;
    }
}

$knowledge = array();

foreach ($cluster as $group) {
    $data = & $knowledge[];
    $data = new stdclass;
    $following = array();
    foreach ($group as $member) {
        Array_Merge_Ex1($following, explode(" ",$member[0]) );
    }
    arsort($following);
    $data->value   = $following;
    $data->members = array_keys($group);
}

file_put_contents("knowledge.json", json_encode($knowledge));

Ahora se viene la parte interesante, el código que toma lo aprendido y sugiere posibles amigos. El algoritmo es relativamente sencillo y rápido de ejecutar (que es lo mejor), se carga en memoria lo aprendido y buscar el grupo mas similar al usuario y luego se sugieren los amigos del grupo que sean todavía sus amigos.

class FriendFinder
{
    /**
     *  distance, esta es la funcion que compara a un usuario
     *  con el modelo de usuarios.
     *
     */
    protected function distance($gfriend, $friends)
    {
        $shr = 0;
        $c1 = count($gfriend);
        $c2 = count($friends);

        foreach($friends as $item) {
            if (isset($gfriend[$item])) {
                $shr++;
            }
        }
        return 1 - ($shr/($c1+$c2 - $shr));
    }

    /**
     *  Retorna los detalles de los amigos de un usuario.
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserFriends($uid)
    {
        foreach(file("friendship-dataset.txt") as $line) {
            list($id, $friends) = explode("\t", trim($line), 2);
            if ($id == $uid) {
                return explode(" ", $friends);
            }
        }
        throw new Exception("User ($uid) not found");
    }

    /**
     *  Retorna los detalles de los un usuario
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserDetails($uname)
    {
        foreach(file("userids.txt") as $line) {
            list($id, $extra)  = explode(" ", trim($line),2);
            list($name, $user) = explode("|", $extra);
            if ($user == $uname) {
                return array($id, $user, $name, $this->_getUserFriends($id));
            }
        }
        throw new Exception("User ($uname) not found");
    }

    /**
     *  Retorna los detalles de los un usuario por ID.
     *  (esto debe re-escrito en sitios de produccion)
     */
    final private function _getUserDetailsById($uid)
    {
        foreach(file("userids.txt") as $line) {
            list($id, $extra)  = explode(" ", trim($line),2);
            list($name, $user) = explode("|", $extra);
            if ($id == $uid) {
                return $user;
            }
        }
        /* todavia no tenemos el ID del usuario, en teoria nunca pasaria */
        /* pero como no tenemos toda la DB de twitter,  por suerte existe el */
        /* YSQL para consultar */
        $q    = "?q=select%20*%20from%20twitter.user.profile%20where%20id%3D";
        $q   .= "'${uid}'&format=json&env=http%3A%2F%2Fdatatables.org%2Falltable";
        $q   .= "s.env&callback=";

       $content = file_get_contents("https://query.yahooapis.com/v1/public/yql?$q");
        $content = json_decode($content);
        return $content->query->results->item->meta[1]->content;
    }

    /**
     *  Esta funcion carga en memoria lo previamente aprendido
     *  (esto debe re-escrito en sitios de produccion)
     */
    final public function getPossibleFriends($name)
    {
        $info   = $this->_getUserDetails($name);
        $groups = json_decode(file_get_contents("knowledge.json")); 

        $distance = 20;
        foreach ($groups as $id => $group) {
            /* json_decode trata los arrays como objectos de stdclass (PHP5)*/
            $gfriend = get_object_vars($group->value);
            $d = $this->distance($gfriend, $info[3]);
            if ($d < $distance) {
                $distance = $d;
                $gmatch   = $id;
            }
        }

        $group = get_object_vars($groups[$gmatch]->value);
        $cands = array();

        foreach (array_keys($group) as $buddy) {
            if (array_search($buddy, $info[3])===false && $buddy != $info[0]) {
                $cands[] = $this->_getUserDetailsById($buddy);
            }
            if (count($cands)==15) break;
        }

        return $cands;
    }
}

$friend = new FriendFinder;
var_dump($friend->getPossibleFriends('crodas'));

A continuación los resultados para algunos amigos míos y sus recomendaciones.

array(15) {
  [0]=>
  string(8) "cleonati"
  [1]=>
  string(6) "chelun"
  [2]=>
  string(11) "grungelover"
  [3]=>
  string(8) "nambucom"
  [4]=>
  string(11) "marcoarturo"
  [5]=>
  string(10) "tipocracia"
  [6]=>
  string(10) "biblosfera"
  [7]=>
  string(9) "Mailplane"
  [8]=>
  string(13) "oscarsanchezo"
  [9]=>
  string(13) "punkgodangell"
  [10]=>
  string(6) "dsosap"
  [11]=>
  string(8) "IRONLOBO"
  [12]=>
  string(8) "sigridee"
  [13]=>
  string(10) "horaciusdr"
  [14]=>
  string(9) "wordpress"
}

array(15) {
  [0]=>
  string(8) "Kokochon"
  [1]=>
  string(10) "maxwellweb"
  [2]=>
  string(6) "eliaya"
  [3]=>
  string(7) "taguiar"
  [4]=>
  string(6) "czayas"
  [5]=>
  string(6) "pp1713"
  [6]=>
  string(10) "LadyIracix"
  [7]=>
  string(11) "manuelacuna"
  [8]=>
  string(11) "javierpreda"
  [9]=>
  string(11) "fabiojose80"
  [10]=>
  string(8) "cleonati"
  [11]=>
  string(11) "grungelover"
  [12]=>
  string(8) "nambucom"
  [13]=>
  string(7) "mharcos"
  [14]=>
  string(14) "SantiagoValdez"
}

array(15) {
  [0]=>
  string(4) "GLun"
  [1]=>
  string(12) "LauEsplendix"
  [2]=>
  string(11) "flyestudios"
  [3]=>
  string(8) "willin64"
  [4]=>
  string(7) "carlink"
  [5]=>
  string(4) "QLRP"
  [6]=>
  string(7) "rubuntu"
  [7]=>
  string(14) "littletiramisu"
  [8]=>
  string(5) "kirai"
  [9]=>
  string(9) "galletita"
  [10]=>
  string(8) "PoKeTiTa"
  [11]=>
  string(6) "lastfm"
  [12]=>
  string(11) "daveexplosm"
  [13]=>
  string(6) "Pk_JoA"
  [14]=>
  string(14) "pisitoenmadrid"
}

array(15) {
  [0]=>
  string(6) "eliaya"
  [1]=>
  string(4) "GLun"
  [2]=>
  string(7) "lettuix"
  [3]=>
  string(7) "carlink"
  [4]=>
  string(4) "QLRP"
  [5]=>
  string(14) "littletiramisu"
  [6]=>
  string(5) "kirai"
  [7]=>
  string(9) "galletita"
  [8]=>
  string(8) "PoKeTiTa"
  [9]=>
  string(6) "lastfm"
  [10]=>
  string(11) "daveexplosm"
  [11]=>
  string(6) "Pk_JoA"
  [12]=>
  string(14) "pisitoenmadrid"
  [13]=>
  string(6) "Aterea"
  [14]=>
  string(9) "Baratijas"
}

array(15) {
  [0]=>
  string(7) "piojita"
  [1]=>
  string(14) "pabloacastillo"
  [2]=>
  string(5) "abcpy"
  [3]=>
  string(13) "sheldoncooper"
  [4]=>
  string(4) "GLun"
  [5]=>
  string(12) "LauEsplendix"
  [6]=>
  string(8) "willin64"
  [7]=>
  string(15) "ElRinconDelGeek"
  [8]=>
  string(7) "carlink"
  [9]=>
  string(4) "QLRP"
  [10]=>
  string(7) "rubuntu"
  [11]=>
  string(14) "littletiramisu"
  [12]=>
  string(5) "kirai"
  [13]=>
  string(9) "galletita"
  [14]=>
  string(8) "PoKeTiTa"
}