XD blog

blog page

map reduce


2016-02-21 scikit-learn, dask and map reduce and examples on Python about machine learning

This is blog post about a couple of topics. The first one is about parallelizing a scikit-learn pipeline with dask. Pipelines and Reuse with dask. A little bit more and dask Introducing Dask Distributed. The module distributed distribute work on a local machine with syntax very close to map/reduce syntax. An example taken from the documentation:

def square(x): return x ** 2
def neg(x): return -x

from distributed import Executor
executor = Executor('127.0.0.1:8786')

A = executor.map(square, range(10))
B = executor.map(neg, A)
total = executor.submit(sum, B)
total.result()

I was being asked where to find examples, scripts about machine learning. Most of them happen to be written within a notebook such as the one posted on Kaggle: Python script posted on kaggle or examples from this blog: Yhat blog. Other examples can be found at ENSAE / Bibliography / Python for a Data Scientist. If you are looking for more examples of code, pick one kaggle competition and look for it on a search engine after adding the word "github", you may be able to find interesting projects. Just try kaggle github to begin with.

2015-02-06 Quelques trucs à propos de PIG

PIG a besoin de connaître le nombre exact de colonnes. Supposons que vous ayez quatre colonnes :

c1  c2  c3  c3
1   2   3   4
6   7   8   9
...

PIG ne dira rien si on écrit ceci :

A = LOAD '$CONTAINER/$PSEUDO/fichiers/ExportHDInsightutf8_noheader.txt'
          USING PigStorage('\t') 
           AS (c1:chararray,c2:chararray,c3:chararray) ;

La dernière colonne sera forcément incluse avec une autre, ce entraînera une erreur plus tard dans l'exécution du script. Une autre erreur causée par inadvertance :

2015-02-05 23:40:54,964 [main] ERROR org.apache.pig.tools.pigstats.SimplePigStats - 
ERROR 0: Exception while executing [POUserFunc 
(Name: POUserFunc(org.apache.pig.builtin.YearsBetween)[long] - 
scope-380 Operator Key: scope-380) children: null at []]: 
java.lang.IllegalArgumentException: ReadableInstant objects must not be null

Cette erreur apparaît par exemple lors de la conversion d'une chaîne de caractères au format Date. Par ailleurs, on sait que les valeurs de cette colonne ne sont jamais nulles. Alors pourquoi ? Le fichier importé sur Hadoop provient en fait d'un fichier texte enregistré à l'aide de pandas. La première ligne contient le nom des colonnes. Or, sous Hadoop, le nom des colonnes n'est jamais précisé dans un fichier. Il n'y a pas de concept de première ligne sous Hadoop. Un gros fichier est stocké sur plusieurs machines et en plusieurs blocs. Chaque blocs a une première ligne mais l'ensemble des blocs n'en a pas vraiment. Ces blocs ne sont d'ailleurs pas ordonnés. On n'insère donc jamais le nom des colonnes dans un fichier sur Hadoop car il n'y a pas de première ligne.

2014-05-24 Graphs and Map / Reduce

Implementing graph algorithm on map/reduce is still a challenge. But maybe because it is a challenge, people keep thinking about it. It is the purpose of GraphX which reduces the processing time for the Page Rank algorithm on a Spark environment. It is not as fast as PowerGraph which is not based on Map/Reduce but it is must faster than Mahout (see paper GraphX: A Resilient Distributed Graph System on Spark). One fact, the language Scala appears more and more. A sign: Mahout recently took the decision to stop implementing machine learning algorithm against Map/Reduce to switch to Spark.

2014-05-02 Map / Reduce

I wish sometimes bugs could let me go. I'm working on an map/reduce algorithm. The problem would be smaller I would not hesitate to avoid map/reduce but it is not. Any fast it can be, I find it very slow and impossible to run. So I polish. I wake up in the morning and a detail strikes me up. Shit, shit, shit, I should have written it that way. It works on a small sample but this sample is resistant to many mistakes. I see this algorithm working in my head from the beginning. But I missed this case, as if a train would hide another one and get me killed when I cross. That kind of stuff always happens with big data. Pruning, scaling...

Most of the time, the issue comes from skewed data. Skewness is a way to say that the data is not uniformly distributed. Precisely, when reducing a table or joining two tables, we group data sharing the same key (as we do a GROUP BY or a JOIN on SQL). People research about it: A Study of Skew in MapReduce Applications. But let's see on a example what it means: notebook on Reduce skew data.

2014-04-20 Les algorithmes sur les graphes ne sont pas aussi simples en Map/Reduce

Je ne suis plus d'où cette histoire est partie ni si elle est vraie mais on dit souvent que si on relie deux personnes quelconques dans le monde par une chaîne d'amis, cette chaîne ne sera pas plus longue que 7. Sans doute Facebook pourrait y trouver à redire. Ce qui m'intéresse ce soir est de savoir la longueur de la chaîne qui me relie au Président de la République.

Je serais bien incapable de vous donner la réponse mais je pourrais vous dire comment la trouver. Si un de vos amis connaît la réponse à cette question, si cette réponse est l, alors dans votre cas, la réponse sera l+1 et vos amis pourront dire que la réponse dans leur cas est l+2. Pour que toute personne dans Paris ait la réponse à cette question, il suffit qu'une vague parte du président et se propage à chacun d'entre nous.

L'algorithme est en lui-même assez simple à implémenter à condition que le graphe soit petit. Lorsqu'il est grand (plusieurs dizaines de millions de noeuds), cela prend du temps, beaucoup de temps même si cela ne peut plus se faire sur le même ordinateur. On pense alors au concept Map/Reduce qui permet d'effectuer des calculs distribués sur plusieurs machines. Mais dans ce cas-ci, ce n'est pas si évident. Et pour comprendre pourquoi, la lecture continue ici : Graphe et Map Reduce.

J'ajoute ici quelques commentaires qui me sont parvenus cette semaine.

Le nombre de connexions qui relient deux individus est un vieux problème : Small-world experiment, Le nombre d'Erdős. Les algorithmes sur des grands graphes ne sont jamais évidents, ne serait-ce que pour calculer (en un temps raisonnable) le plus court chemin entre deux pages Wikipedia comme sur Wikidistrict, décrite ici Wikidistrict, une exploration ludique de Wikipédia. Le premier réflexe lorsqu'on traite un grand nombre de données est de réduire la taille du problème ou de regardeer sur des examples. Cependant, s'il est facile de concevoir ce qu'est un échantillon au sein d'une population, qu'est-ce qu'un échantillon au sein d'un graphe, un échantillon qui respecte les propriétés du graphe. Vous trouverez quelques réponses ici : Statistical Analysis of Network Data (Eric D. Kolaczyk).

2014-04-14 A reference for Text Processing with Map Reduce

While reading some papers, I found this reference: Data-Intensive Text Processing with MapReduce. It is a good introduction for people who never used Map Reduce.


Xavier Dupré