Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Factorización de matriz de alta Skinny QR (TSQR) usando MapReduce

Este ejemplo muestra cómo calcular una factorización alta de QR (TSQR) delgada usando.mapreduce Muestra cómo encadenar llamadas para realizar varias iteraciones de factorizaciones y usa el argumento de la función Map para calcular las claves numéricas.mapreduceinfo

Preparar datos

Cree un almacén de datos utilizando el conjunto de información.airlinesmall.csv Este conjunto de datos de 12 megabyte contiene 29 columnas de información de vuelo para varias aerolíneas, incluidas las horas de llegada y salida. En este ejemplo, las variables de interés son (retardo de llegada del vuelo), (retardo de salida del vuelo) y (distancia total del vuelo).ArrDelayDepDelayDistance

ds = datastore('airlinesmall.csv', 'TreatAsMissing', 'NA'); ds.ReadSize = 1000; ds.SelectedVariableNames = {'ArrDelay', 'DepDelay', 'Distance'}; 

El almacén de datos trata los valores como ausentes y reemplaza los valores que faltan por valores predeterminados.'NA'NaN La propiedad le permite especificar cómo particionar los datos en fragmentos.ReadSize Además, la propiedad le permite trabajar solo con las variables de interés especificadas, que puede comprobar mediante.SelectedVariableNamespreview

preview(ds) 
 ans =    8x3 table      ArrDelay    DepDelay    Distance     ________    ________    ________          8          12         308            8           1         296           21          20         480           13          12         296            4          -1         373           59          63         308            3          -2         447           11          -1         954     

Encadenar llamadas MapReduce

La implementación del algoritmo TSQR de múltiples iteraciones necesita encadenar llamadas consecutivas.mapreduce Para demostrar el patrón de diseño de encadenamiento general, este ejemplo utiliza dos iteraciones.mapreduce La salida de las llamadas de función de mapa se pasa a un gran conjunto de reductores y, a continuación, la salida de estos reductores se convierte en la entrada para la siguiente iteración.mapreduce

Primera iteración MapReduce

En la primera iteración, la función Map, recibe un fragmento (la Ith) de los datos, que es una tabla de tamañotsqrMapper . El asignador computa el matriz de este fragmento de datos y lo almacena como un resultado intermedio. A continuación, agrega los resultados intermedios por clave única antes de enviarlos a la función de reducción.mapreduce Por lo tanto, envía todos los intermediosmapreduce matrices con la misma clave para el mismo reductor.

Puesto que el reductor utiliza, que es una función de MATLAB en memoria, lo mejor es asegurarse primero de que elqr matrices caben en la memoria. Este ejemplo divide el conjunto de datos en ocho particiones. La función Lee los datos en fragmentos y pasa los datos junto con alguna meta información a la función de mapa.mapreduce El argumento de entrada es la segunda entrada a la función Map y contiene la información de desplazamiento de lectura y tamaño de archivo necesaria para generar la clave,info

  key = ceil(offset/fileSize/numPartitions).

Mostrar el archivo de función de mapa.

 function tsqrMapper(data, info, intermKVStore) % Mapper function for the TSQRMapReduceExample.  % Copyright 2014 The MathWorks, Inc.  x = data{:,:}; x(any(isnan(x),2),:) = [];% Remove missing values  [~, r] = qr(x,0);  % intermKey = randi(4); % random integer key for partitioning intermediate results intermKey = computeKey(info, 8); add(intermKVStore,intermKey, r);  function key = computeKey(info, numPartitions) % Helper function to generate a key for the tsqrMapper function.  fileSize = info.FileSize; % total size of the underlying data file partitionSize = fileSize/numPartitions; % size in bytes of each partition offset = info.Offset; % offset in bytes of the current read  key = ceil(offset/partitionSize);  

La función de reducción recibe una lista del intermedio matrices, las concatenan verticalmente y computa el matriz de la matriz concatenada.

Visualice el archivo de función de reducción.

 function tsqrReducer(intermKey, intermValIter, outKVStore) % Reducer function for the TSQRMapReduceExample.  % Copyright 2014 The MathWorks, Inc.  x = [];  while (intermValIter.hasnext)     x = [x;intermValIter.getnext]; end % Note that this approach assumes the concatenated intermediate values fit % in memory. Consider increasing the number of reduce tasks (increasing the % number of partitions in the tsqrMapper) and adding more iterations if it % does not fit in memory.  [~, r] =qr(x,0);  outKVStore.add(intermKey,r);  

Se utiliza para aplicar el mapa y reducir las funciones al almacén de datos,.mapreduceds

outds1 = mapreduce(ds, @tsqrMapper, @tsqrReducer); 
******************************** *      MAPREDUCE PROGRESS      * ******************************** Map   0% Reduce   0% Map  10% Reduce   0% Map  20% Reduce   0% Map  30% Reduce   0% Map  40% Reduce   0% Map  50% Reduce   0% Map  60% Reduce   0% Map  70% Reduce   0% Map  80% Reduce   0% Map  90% Reduce   0% Map 100% Reduce   0% Map 100% Reduce  11% Map 100% Reduce  22% Map 100% Reduce  33% Map 100% Reduce  44% Map 100% Reduce  56% Map 100% Reduce  67% Map 100% Reduce  78% Map 100% Reduce  89% Map 100% Reduce 100% 

Devuelve un almacén de datos de salida, con archivos en la carpeta actual.mapreduceoutds1

Segunda iteración de MapReduce

La segunda iteración utiliza la salida de la primera iteración, como entrada.outds1 Esta iteración utiliza un asignador de identidades, que simplemente copia sobre los datos con una sola clave,.identityMapper'Identity'

Visualice el archivo de asignador de identidades.

 function identityMapper(data, info, intermKVStore) % Mapper function for the MapReduce TSQR example. % % This mapper function simply copies the data and add them to the % intermKVStore as intermediate values.  % Copyright 2014 The MathWorks, Inc.  x = data.Value{:,:}; add(intermKVStore,'Identity', x);  

La función reductor es la misma en ambas iteraciones. El uso de una sola clave por la función de mapa significa que sólo llama a la función de reducción una vez en la segunda iteración.mapreduce

Visualice el archivo de función de reducción.

 function tsqrReducer(intermKey, intermValIter, outKVStore) % Reducer function for the TSQRMapReduceExample.  % Copyright 2014 The MathWorks, Inc.  x = [];  while (intermValIter.hasnext)     x = [x;intermValIter.getnext]; end % Note that this approach assumes the concatenated intermediate values fit % in memory. Consider increasing the number of reduce tasks (increasing the % number of partitions in the tsqrMapper) and adding more iterations if it % does not fit in memory.  [~, r] =qr(x,0);  outKVStore.add(intermKey,r);  

Se usa para aplicar el asignador de identidades y el mismo reductor a la salida de la primera llamada.mapreducemapreduce

outds2 = mapreduce(outds1, @identityMapper, @tsqrReducer); 
******************************** *      MAPREDUCE PROGRESS      * ******************************** Map   0% Reduce   0% Map  11% Reduce   0% Map  22% Reduce   0% Map  33% Reduce   0% Map  44% Reduce   0% Map  55% Reduce   0% Map  66% Reduce   0% Map  77% Reduce   0% Map  88% Reduce   0% Map 100% Reduce   0% Map 100% Reduce 100% 

Ver resultados

Lea los resultados finales del almacén de datos de salida.

r = readall(outds2); r.Value{:} 
 ans =     1.0e+05 *      0.1091    0.0893    0.5564          0   -0.0478   -0.4890          0         0    3.0130  

Referencia

  1. Paul G. Constantine y David F. Gleich. 2011. Factorizaciones QR altas y delgadas en arquitecturas MapReduce. En actas del segundo taller internacional sobre MapReduce y sus aplicaciones (MapReduce ' 11). ACM, Nueva York, NY, EE.UU., 43-50. DOI = 10.1145/1996092.1996103https://doi.acm.org/10.1145/1996092.1996103

Consulte también

|

Temas relacionados