Статьи

Вычисление матрицы сопутствующих явлений с Hadoop

Сентябрь 10, 2018

Этот пост продолжается нашей серией реализации алгоритмов MapReduce, которые можно найти в  книге « Интенсивная обработка текста с помощью MapReduce» . На этот раз мы будем создавать матрицу совпадений слов из совокупности текста. Предыдущие посты в этой серии:

  1. Работа с интенсивной обработкой текста с помощью MapReduce
  2. Работа с интенсивной обработкой текста с помощью MapReduce — локальная агрегация, часть II

Смежности Матрица может быть описана как отслеживание события, и с учетом определенного окна времени или пространства, какие другие события, кажется, происходят. Для целей этого поста нашими «событиями» являются отдельные слова, найденные в тексте, и мы будем отслеживать, какие другие слова встречаются в нашем «окне», позиции относительно целевого слова. Например, рассмотрим фразу «Быстрая коричневая лиса перепрыгнула через ленивую собаку». При значении окна, равном 2, совпадение для слова «прыжок» будет [коричневый, лис, над,]. Матрица совместного вхождения может быть применена к другим областям, которые требуют расследования того, когда происходит «это» событие, какие другие события, по-видимому, происходят одновременно. Чтобы построить нашу матрицу совместного вхождения текста, мы будем реализовывать алгоритмы пар и полос, описанные в главе 3 «Интенсивная обработка текста с помощью MapReduce».Тело текста, использованное для создания нашей матрицы совпадений, — это коллективные произведения Уильям Шекспир .

Пары

Реализация парного подхода проста. Для каждой строки, переданной при вызове функции map, мы разделим пробелы, создавая String Array. Следующим шагом будет создание двух петель. Внешний цикл будет перебирать каждое слово в массиве, а внутренний цикл будет перебирать «соседей» текущего слова. Количество итераций для внутреннего цикла определяется размером нашего «окна» для захвата соседей текущего слова. В нижней части каждой итерации во внутреннем цикле мы будем выдавать объект WordPair (состоящий из текущего слова слева и соседнего слова справа) в качестве ключа и счетчик единиц в качестве значения. Вот код для реализации пар:

public class PairsOccurrenceMapper extends Mapper<LongWritable, Text, WordPair, IntWritable> {
    private WordPair wordPair = new WordPair();
    private IntWritable ONE = new IntWritable(1);

    @Override
    protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        int neighbors = context.getConfiguration().getInt("neighbors", 2);
        String[] tokens = value.toString().split("\\s+");
        if (tokens.length > 1) {
          for (int i = 0; i < tokens.length; i++) {
              wordPair.setWord(tokens[i]);

             int start = (i - neighbors < 0) ? 0 : i - neighbors;
             int end = (i + neighbors >= tokens.length) ? tokens.length - 1 : i + neighbors;
              for (int j = start; j <= end; j++) {
                  if (j == i) continue;
                   wordPair.setNeighbor(tokens[j]);
                   context.write(wordPair, ONE);
              }
          }
      }
  }
}

Реализация редуктора для пар просто суммирует все числа для данного ключа WordPair:

public class PairsReducer extends Reducer<WordPair,IntWritable,WordPair,IntWritable> {
    private IntWritable totalCount = new IntWritable();
    @Override
    protected void reduce(WordPair key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
        int count = 0;
        for (IntWritable value : values) {
             count += value.get();
        }
        totalCount.set(count);
        context.write(key,totalCount);
    }
}

полосы

Реализация подхода с полосами к совместному появлению одинаково проста. Подход тот же, но все «соседние» слова собраны в HashMap с соседним словом в качестве ключа и целым числом в качестве значения. Когда все значения были собраны для данного слова (нижняя часть внешнего цикла), слово и hashmap испускаются. Вот код для нашей реализации Stripes:

public class StripesOccurrenceMapper extends Mapper<LongWritable,Text,Text,MapWritable> {
  private MapWritable occurrenceMap = new MapWritable();
  private Text word = new Text();

  @Override
 protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
   int neighbors = context.getConfiguration().getInt("neighbors", 2);
   String[] tokens = value.toString().split("\\s+");
   if (tokens.length > 1) {
      for (int i = 0; i < tokens.length; i++) {
          word.set(tokens[i]);
          occurrenceMap.clear();

          int start = (i - neighbors < 0) ? 0 : i - neighbors;
          int end = (i + neighbors >= tokens.length) ? tokens.length - 1 : i + neighbors;
           for (int j = start; j <= end; j++) {
                if (j == i) continue;
                Text neighbor = new Text(tokens[j]);
                if(occurrenceMap.containsKey(neighbor)){
                   IntWritable count = (IntWritable)occurrenceMap.get(neighbor);
                   count.set(count.get()+1);
                }else{
                   occurrenceMap.put(neighbor,new IntWritable(1));
                }
           }
          context.write(word,occurrenceMap);
     }
   }
  }
}

Подход «Редуктор для полос» немного сложнее из-за того, что нам нужно будет перебрать коллекцию карт, а затем для каждой карты перебрать все значения в карте:

public class StripesReducer extends Reducer<Text, MapWritable, Text, MapWritable> {
    private MapWritable incrementingMap = new MapWritable();

    @Override
    protected void reduce(Text key, Iterable<MapWritable> values, Context context) throws IOException, InterruptedException {
        incrementingMap.clear();
        for (MapWritable value : values) {
            addAll(value);
        }
        context.write(key, incrementingMap);
    }

    private void addAll(MapWritable mapWritable) {
        Set<Writable> keys = mapWritable.keySet();
        for (Writable key : keys) {
            IntWritable fromCount = (IntWritable) mapWritable.get(key);
            if (incrementingMap.containsKey(key)) {
                IntWritable count = (IntWritable) incrementingMap.get(key);
                count.set(count.get() + fromCount.get());
            } else {
                incrementingMap.put(key, fromCount);
            }
        }
    }
}

Вывод

Рассматривая два подхода, мы видим, что алгоритм пар генерирует больше пар ключ-значение по сравнению с алгоритмом полос. Кроме того, алгоритм Pairs фиксирует каждое отдельное событие вхождения, в то время как алгоритм Stripes фиксирует все вхождения для данного события. И реализации Пары и Полосы выиграют от использования Combiner. Поскольку оба дают коммутативные и ассоциативные результаты, мы можем просто повторно использовать каждый редуктор Mapper в качестве Combiner. Как указывалось ранее, создание матрицы совместного использования имеет применимость к другим областям помимо обработки текста и представляет полезные алгоритмы MapReduce, которые можно иметь в своем арсенале. Спасибо за ваше время.

Ресурсы

35
Share: