[HADOOP] 지도에서 중간 값 계산

지도에서 중간 값 계산

누군가가지도의 중앙값 / 분위수 계산을 줄일 수 있습니까?

Datafu의 중간 값에 대한 나의 이해는 'n'매퍼가 데이터를 수집하고 정렬을 담당하는 "1"감속기로 데이터를 보냅니다. n 매퍼의 모든 데이터와 중앙값 (중간 값) 내 이해가 맞습니까?

그렇다면이 방법은 내가 단 하나의 감속기를 분명히 볼 수있는 엄청난 양의 데이터 마지막 일을하기 위해 애 쓰고 있습니다. 감사

해결법

1. ==============================

   1.일련의 중간 값 (가운데 숫자)을 찾으려고하면 "중간"값을 결정하기 위해 전체 감속기가 전달되어야합니다.

   일련의 중간 값 (가운데 숫자)을 찾으려고하면 "중간"값을 결정하기 위해 전체 감속기가 전달되어야합니다.

   입력 세트의 값과 범위의 고유성에 따라 각 값의 빈도를 출력하는 결합기를 도입하여 단일 감속기로 전송되는지도 출력 수를 줄일 수 있습니다. 감속기는 정렬 값 / 주파수 쌍을 소비하여 중앙값을 식별 할 수 있습니다.

   범위와 값의 대략적인 분포를 알고있는 경우 다시 범위를 조정할 수있는 또 다른 방법은 범위 버킷 (0-99는 감속기 0, 100-199는 감속기 2로 이동)에 따라 키를 분배하는 사용자 정의 분할기를 사용하는 것입니다. 에). 그러나 감속기 출력을 검사하고 최종 중앙값 계산을 수행하려면 일부 보조 작업이 필요합니다 (예 : 각 감속기의 키 개수, 감속기 출력에 중앙값이 포함되어 있는지, 어느 오프셋에서 계산되었는지 계산할 수 있음)

2. ==============================

   2.정확한 중앙값과 분위수가 정말로 필요합니까?

   정확한 중앙값과 분위수가 정말로 필요합니까?

   시간이 오래 걸리면 근사값을 얻는 것이 더 효과적이며 특히 작업 할 때 유용합니다. 데이터 파티셔닝.

   실제로, 대략 quantile을 사용하여 정확한 quantile (실제로는 O (n / p) 시간)을 빠르게 찾을 수 있습니다. 여기에 전략의 대략적인 개요가 있습니다.

   각 단계는 선형 시간입니다. 가장 비용이 많이 드는 단계는 전체 데이터 세트를 재배포해야하므로 O (n) 네트워크 트래픽을 생성하므로 파트 3입니다. 첫 x 째 반복에 대해 "대체"퀀 타이 저는을 선택하여 프로세스를 최적화 할 수 있습니다. 말하자면, 글로벌 중앙값을 찾고 싶습니다. 선형 프로세스에서 쉽게 찾을 수 없지만, k 파티션으로 분할 될 때 데이터 세트의 1 / kth로 축소 할 수 있습니다. 따라서 각 노드가 중간 값을보고하는 대신 각 노드가 (k-1) / (2k) 및 (k + 1) / (2k)에있는 객체를 추가적으로보고하게하십시오. 이렇게하면 진정한 중앙값이 중요한 위치에 있어야하는 값의 범위를 좁힐 수 있습니다. 따라서 다음 단계에서는 각 노드가 원하는 범위 내에있는 객체를 단일 마스터 노드로 보내고이 범위 내에서만 중앙값을 선택할 수 있습니다.

3. ==============================

   3.O ((n log n) / p)를 선택하여 O (1)을 정렬하면 중앙값을 구할 수 있습니다.

   O ((n log n) / p)를 선택하여 O (1)을 정렬하면 중앙값을 구할 수 있습니다.

   예 ... O (n / p)를 얻을 수 있지만 Hadoop의 기본 정렬 기능을 사용할 수는 없습니다. 병렬 k 번째 가장 큰 알고리즘을 코딩하기 위해 개발 시간을 2 ~ 20 시간으로 정당화 할 수 없다면 나는 정렬하고 가운데 아이템을 얻는다.

4. ==============================

   4.많은 실제 시나리오에서 데이터 집합의 값의 카디널리티는 상대적으로 작습니다. 이 경우 두 개의 MapReduce 작업으로 문제를 효율적으로 해결할 수 있습니다.

   많은 실제 시나리오에서 데이터 집합의 값의 카디널리티는 상대적으로 작습니다. 이 경우 두 개의 MapReduce 작업으로 문제를 효율적으로 해결할 수 있습니다.

   작업 1. 데이터 양을 크게 줄이고 완전히 병렬로 실행할 수 있습니다. 작업 2의 감속 기는 순진한 접근 방식과 마찬가지로 모든 값 대신 n (n = 귀중한 값 집합의 카디널리티) 항목을 처리해야합니다.

   아래 작업 2의 예제 감속기입니다. Hadoop 스트리밍에서 직접 사용할 수있는 Python 스크립트입니다. 데이터 집합의 값이 int라고 가정하지만 복식에 쉽게 적용될 수 있습니다.

   import sys
   
   item_to_index_range = []
   total_count = 0
   
   # Store in memory a mapping of a value to the range of indexes it has in a sorted list of all values
   for line in sys.stdin:
       item, count = line.strip().split("\t", 1)
       new_total_count = total_count + int(count)
       item_to_index_range.append((item, (total_count + 1,   new_total_count + 1)))
       total_count = new_total_count
   
   # Calculate index(es) of middle items
   middle_items_indexes = [(total_count / 2) + 1]
   if total_count % 2 == 0:
       middle_items_indexes += [total_count / 2]
   
   # Retrieve middle item(s) 
   middle_items = []
   for i in middle_items_indexes:
       for item, index_range in item_to_index_range:
           if i in range(*index_range):
               middle_items.append(item)
               continue
   
   print sum(middle_items) / float(len(middle_items))
   

   이 답변은 처음에 Chris White의 답변에서 나온 제안을 바탕으로 작성되었습니다. 대답은 결합기를 평균값으로 사용하여 값의 빈도를 계산하는 것입니다. 그러나 MapReduce에서는 결합자가 항상 실행되도록 보장되지 않습니다. 여기에는 몇 가지 부작용이 있습니다.

from https://stackoverflow.com/questions/10109514/computing-median-in-map-reduce by cc-by-sa and MIT license