MapReduce-알고리즘
MapReduce 알고리즘에는 Map 및 Reduce라는 두 가지 중요한 작업이 포함됩니다.
- 맵 작업은 Mapper 클래스를 통해 수행됩니다.
- 감소 작업은 Reducer Class를 통해 수행됩니다.
매퍼 클래스는 입력을 받아 토큰 화하고 매핑하고 정렬합니다. Mapper 클래스의 출력은 Reducer 클래스의 입력으로 사용되며 일치하는 쌍을 검색하여 줄입니다.
MapReduce는 다양한 수학적 알고리즘을 구현하여 작업을 작은 부분으로 나누고 여러 시스템에 할당합니다. 기술적 인 측면에서 MapReduce 알고리즘은 Map & Reduce 작업을 클러스터의 적절한 서버로 보내는 데 도움이됩니다.
이러한 수학적 알고리즘에는 다음이 포함될 수 있습니다.
- Sorting
- Searching
- Indexing
- TF-IDF
정렬
정렬은 데이터를 처리하고 분석하는 기본 MapReduce 알고리즘 중 하나입니다. MapReduce는 매퍼의 출력 키-값 쌍을 키별로 자동 정렬하는 정렬 알고리즘을 구현합니다.
정렬 방법은 매퍼 클래스 자체에서 구현됩니다.
셔플 및 정렬 단계에서 매퍼 클래스의 값을 토큰 화 한 후 Context class (사용자 정의 클래스)는 일치하는 값 키를 컬렉션으로 수집합니다.
유사한 키-값 쌍 (중간 키)을 수집하기 위해 Mapper 클래스는 RawComparator 키-값 쌍을 정렬하는 클래스입니다.
주어진 Reducer에 대한 중간 키-값 쌍 세트는 Reducer에 표시되기 전에 키-값 (K2, {V2, V2,…})을 형성하기 위해 Hadoop에 의해 자동으로 정렬됩니다.
수색
검색은 MapReduce 알고리즘에서 중요한 역할을합니다. 결합기 단계 (선택 사항)와 감속기 단계에서 도움이됩니다. 예를 들어 검색이 어떻게 작동하는지 이해해 보겠습니다.
예
다음 예제는 MapReduce가 검색 알고리즘을 사용하여 주어진 직원 데이터 세트에서 가장 높은 급여를받는 직원의 세부 정보를 찾는 방법을 보여줍니다.
직원 데이터가 A, B, C, D의 네 가지 파일에 있다고 가정하겠습니다. 또한 모든 데이터베이스 테이블에서 직원 데이터를 반복적으로 가져 오기 때문에 4 개의 파일 모두에 중복 된 직원 레코드가 있다고 가정하겠습니다. 다음 그림을 참조하십시오.
The Map phase각 입력 파일을 처리하고 직원 데이터를 키-값 쌍으로 제공합니다 (<k, v> : <emp 이름, 급여>). 다음 그림을 참조하십시오.
The combiner phase(검색 기술)은 직원 이름과 급여가 포함 된 키-값 쌍으로 맵 단계의 입력을 받아들입니다. 컴 바이 너는 검색 기법을 사용하여 모든 직원 급여를 확인하여 각 파일에서 가장 높은 급여를받는 직원을 찾습니다. 다음 스 니펫을 참조하십시오.
<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary
if(v(second employee).salary > Max){
Max = v(salary);
}
else{
Continue checking;
}예상 결과는 다음과 같습니다.
|
Reducer phase− 각 파일을 작성하면 급여가 가장 높은 직원을 찾을 수 있습니다. 중복을 방지하려면 모든 <k, v> 쌍을 확인하고 중복 항목이있는 경우 제거하십시오. 4 개의 입력 파일에서 오는 4 개의 <k, v> 쌍 사이에 동일한 알고리즘이 사용됩니다. 최종 출력은 다음과 같아야합니다.
<gopal, 50000>인덱싱
일반적으로 인덱싱은 특정 데이터와 해당 주소를 가리키는 데 사용됩니다. 특정 매퍼의 입력 파일에 대해 일괄 인덱싱을 수행합니다.
MapReduce에서 일반적으로 사용되는 인덱싱 기술은 다음과 같이 알려져 있습니다. inverted index.Google 및 Bing과 같은 검색 엔진은 반전 된 인덱싱 기술을 사용합니다. 간단한 예제를 통해 인덱싱이 작동하는 방식을 이해해 보겠습니다.
예
다음 텍스트는 반전 된 인덱싱을위한 입력입니다. 여기서 T [0], T [1] 및 t [2]는 파일 이름이고 해당 내용은 큰 따옴표로 묶여 있습니다.
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"인덱싱 알고리즘을 적용한 후 다음과 같은 출력을 얻습니다.
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}여기서 "a": {2}는 T [2] 파일에 "a"라는 용어가 표시됨을 의미합니다. 마찬가지로 "is": {0, 1, 2}는 "is"라는 용어가 T [0], T [1] 및 T [2] 파일에 표시됨을 의미합니다.
TF-IDF
TF-IDF는 Term Frequency-Inverse Document Frequency의 줄임말 인 텍스트 처리 알고리즘입니다. 일반적인 웹 분석 알고리즘 중 하나입니다. 여기서 '빈도'라는 용어는 문서에서 용어가 나타나는 횟수를 의미합니다.
기간 빈도 (TF)
문서에서 특정 용어가 발생하는 빈도를 측정합니다. 문서에 단어가 나타나는 횟수를 해당 문서의 총 단어 수로 나눈 값입니다.
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)역 문서 빈도 (IDF)
용어의 중요성을 측정합니다. 텍스트 데이터베이스의 문서 수를 특정 용어가 나타나는 문서 수로 나눈 값으로 계산됩니다.
TF를 계산하는 동안 모든 용어는 똑같이 중요한 것으로 간주됩니다. 즉, TF는 "is", "a", "what"등과 같은 일반 단어에 대한 용어 빈도를 계산합니다. 따라서 다음을 계산하여 희귀 단어를 확장하면서 빈번한 용어를 알아야합니다.
IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).알고리즘은 작은 예제의 도움으로 아래에 설명되어 있습니다.
예
1000 개의 단어가 포함 된 문서를 생각해보십시오. hive50 번 나타납니다. TFhive 그러면 (50/1000) = 0.05입니다.
이제 1,000 만 개의 문서와 hive이 중 1000 개에 나타납니다. 그런 다음 IDF는 log (10,000,000 / 1,000) = 4로 계산됩니다.
TF-IDF 무게는 0.05 × 4 = 0.20의 양의 곱입니다.