[HADOOP] MapReduce / Hadoop으로 고유 값 계산을 구현하는 방법은 무엇입니까?

MapReduce / Hadoop으로 고유 값 계산을 구현하는 방법은 무엇입니까?

PageRank가 고유 값의 한 형태이고 MapReduce가 도입 된 이유이기 때문에 가능합니다. 그러나 모든 슬레이브 컴퓨터가 매트릭스 사본을 유지해야하는 것과 같이 실제 구현에는 문제가있는 것 같습니다.

해결법

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

   1.PageRank는 네트워크의 정상 상태 이산 흐름 조건을 반복적으로 찾아 냄으로써 지배적 인 고유 벡터 문제를 해결합니다.

   PageRank는 네트워크의 정상 상태 이산 흐름 조건을 반복적으로 찾아 냄으로써 지배적 인 고유 벡터 문제를 해결합니다.

   NxM 행렬 A가 노드 n에서 노드 m까지의 링크 가중치 (흐름의 양)를 설명하면,

   p_{n+1} = A . p_{n} 
   

   p가 안정 상태 (p_n + 1 = p_n)로 수렴하는 한도에서 이것은 고유 값 1을 갖는 고유 벡터 문제입니다.

   PageRank 알고리즘은 행렬을 메모리에 보유 할 필요는 없지만 밀도가 높은 (비 스파 스) 행렬에서는 비효율적입니다. 밀도가 높은 행렬의 경우 MapReduce가 잘못된 솔루션입니다. 즉, 노드 간 지역 및 광범위한 교환이 필요하며 대신 LaPACK과 MPI 및 친구들을 살펴보아야합니다.

   wukong 라이브러리 (ruby의 경우 hadoop 스트리밍) 또는 Heretrix 페이지 랭크 하위 모듈에서 작업중인 페이지 랭크 구현을 볼 수 있습니다. (heretrix 코드는 Heretrix와 별개로 실행됩니다)

   (면책 조항 : 저는 wukong의 저자입니다.)

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

   2.전문:

   전문:

   적절한 데이터 격리가 이루어지면 모든 시스템에서 완벽한 데이터 세트없이 병렬 컴퓨팅 결과를 얻을 수 있습니다.

   다음 루프를 예로 들어 보겠습니다.

   for (int i = 0; i < m[].length; i++)
   {
       for (int j = 0; j < m[i].length; j++)
       {
           m[i][j]++; 
       }
   }
   

   그리고 다음과 같은 레이아웃의 행렬이 주어진다.

          j=0   j=1   j=2
    i=0  [   ] [   ] [   ]
    i=1  [   ] [   ] [   ]
    i=2  [   ] [   ] [   ]
   

   병렬 구조는 J 열이 각 컴퓨터로 전송 될 수 있고 단일 열이 병렬로 계산되도록 존재합니다. 병렬화의 어려운 부분은 종속성을 포함하는 루프가있을 때입니다.

   for (int i = 0; i < m[].length; i++)
   {
       for (int j = 0; j < m[i].length; j++)
       {
           //For obvious reasons, matrix index verification code removed
           m[i][j] = m[i/2][j] + m[i][j+7]; 
       }
   }
   

   분명히 위의 루프와 같은 루프는 매우 문제가됩니다 (매트릭스 인덱서에 주목하십시오). 그러나 이러한 유형의 루프를 풀고 효과적인 병렬 알고리즘을 만드는 기술은 존재합니다.

   대답:

   Google이 모든 슬레이브 컴퓨터에서 행렬의 사본을 유지하지 않고 고유 값을 계산하는 솔루션을 개발 한 것은 가능합니다. - 또는 - 그들은 몬테 카를로 (Monte Carlo) 또는 다른 근사 알고리즘 (Approximation Algorithm)과 같은 것을 사용하여 "충분히 근접한"계산을했습니다.

   사실, Google은 PageRank 알고리즘에 필요한 계산을 최대한 효율적으로 수행하기 위해 Google이 최대한 길게 갈 것이라고 말합니다. 이 같은 머신과 (이더넷 케이블에주의를 기울여야하는) 머신을 구동 할 때, 커다란 데이터 세트 (장비 100 대)를 전송할 수 없습니다. 왜냐하면 범용 NIC 카드의 하드웨어 제한 때문에 불가능하기 때문입니다.

   그렇게 말하면서, 구글은 프로그래머 커뮤니티가 놀랍고, 구현이 완전히 다를 수 있다는 점을 잘 알고있다.

   어쩔 수 없음 :

   병렬 컴퓨팅을위한 좋은 리소스에는 OpenMP와 MPI가 포함됩니다. 두 가지 병렬 구현은 매우 다른 패러다임에서 병렬 컴퓨팅에 접근합니다. 그 중 일부는 시스템 구현 (클러스터 대 분산 컴퓨팅)에서 비롯됩니다.

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

   3.나는 특수 구조 (예 : 스파 스 행렬 또는 특정 블록 패턴 포함)를 제외한 대부분의 행렬에서는 다루기가 쉽지 않다고 생각합니다. 행렬 계수와 고유 값 사이에 너무 많은 결합이 있습니다.

   나는 특수 구조 (예 : 스파 스 행렬 또는 특정 블록 패턴 포함)를 제외한 대부분의 행렬에서는 다루기가 쉽지 않다고 생각합니다. 행렬 계수와 고유 값 사이에 너무 많은 결합이 있습니다.

   페이지 랭크 (PageRank)는 특별한 형태의 매우 드문 드문 한 행렬을 사용하며, 그 고유치를 계산할 때의 결론은 일반 행렬로 확장되지 않습니다. (편집 : 흥미로운 다른 참고 자료가 있습니다.)

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

   4.나는 지금 나 자신에게 대답 할 수있다. 페이지 랭크 (PageRank) 알고리즘은 자체 곱셈을 사용하여 고유 값에서 수렴해야하는 희소 매트릭스를 이용합니다. 따라서 PageRank 연습에서는 Map / Reduce 절차가 유효합니다. Map 프로 시저에서 행렬 곱하기를 수행하고 Reduce 프로 시저에서 희소 행렬을 형성 할 수 있습니다. 그러나 일반적인 행렬 고유치를 찾는 경우에도 여전히 까다로운 문제입니다.

   나는 지금 나 자신에게 대답 할 수있다. 페이지 랭크 (PageRank) 알고리즘은 자체 곱셈을 사용하여 고유 값에서 수렴해야하는 희소 매트릭스를 이용합니다. 따라서 PageRank 연습에서는 Map / Reduce 절차가 유효합니다. Map 프로 시저에서 행렬 곱하기를 수행하고 Reduce 프로 시저에서 희소 행렬을 형성 할 수 있습니다. 그러나 일반적인 행렬 고유치를 찾는 경우에도 여전히 까다로운 문제입니다.

5. ==============================

   5.아파치 하마 프로젝트에는 Jacobi 고유 값 알고리즘의 흥미로운 구현이 있습니다. 그것은 hadoop에서 실행됩니다. 지도가 축소되지 않은 행렬 스캔에서 회전이 발생합니다.

   아파치 하마 프로젝트에는 Jacobi 고유 값 알고리즘의 흥미로운 구현이 있습니다. 그것은 hadoop에서 실행됩니다. 지도가 축소되지 않은 행렬 스캔에서 회전이 발생합니다.

from https://stackoverflow.com/questions/388302/how-to-implement-eigenvalue-calculation-with-mapreduce-hadoop by cc-by-sa and MIT license