MapReduce를 이용한 Ordinary Least Squares Big Data Analytics Short Courses MapReduce를 이용한 Ordinary Least Squares DataScience Lab. 박사과정 김희찬 2017-02-24 (금)

단순선형회귀는? 데이터를 잘 표현할 수 있는 직선을 찾아내는 것 데이터가 2차원이라고 가정하면… 이때 𝑦 , 𝜀 -> n x 1, 𝑋 -> n x p 데이터를 가장 잘 표현하는 함수 f는? 모든 데이터에 대하여 아래 수식의 값이 최소가 될 때 (Residual ei) 최소제곱법으로 풀어보자 제곱한 후 잔차의 합은? (sum of squared residuals) 𝑦 𝑖 =𝑓 𝑥 𝑖 = 𝑥 𝑖 𝑇 𝛽+ 𝜀 𝑖 𝑦=𝑋𝛽+𝑒 𝑒=𝑦−𝑋𝛽 𝑒 𝑇 𝑒= 𝑦−𝑋𝛽 𝑇 (𝑦−𝑋𝛽) = 𝑦 𝑇 𝑦− 𝛽 𝑇 𝑋 𝑇 𝑦− 𝑦 𝑇 𝑋𝛽+ 𝛽 𝑇 𝑋 𝑇 𝑋𝛽 = 𝑦 𝑇 𝑦−2 𝛽 𝑇 𝑋 𝑇 𝑦+ 𝛽 𝑇 𝑋 𝑇 𝑋𝛽

단순선형회귀는? 데이터를 잘 표현할 수 있는 직선을 찾아내는 것 에러를 최소화한다면 가장 적절한 직선을 찾을 수 있을 것 편미분 후 Normal Equation으로 설정 후 풀면 됨 𝜕 𝑒 𝑇 𝑒 𝜕𝛽 =−2 𝑋 𝑇 𝑦+2 𝑋 𝑇 𝑋𝛽=0 𝑋 𝑇 𝑋𝛽= 𝑋 𝑇 𝑦 𝛽= 𝑋 𝑇 𝑋 −1 𝑋 𝑇 𝑦 𝑋 𝑇 𝑋𝛽= 𝑋 𝑇 (𝑋𝛽+𝑒) 𝑦=𝑋𝛽+𝑒 𝑋 𝑇 𝑋𝛽= 𝑋 𝑇 𝑋𝛽+ 𝑋 𝑇 𝑒 𝑋 𝑇 𝑒=0

단순선형회귀는? 데이터를 잘 표현할 수 있는 직선을 찾아내는 것 예제 데이터로 풀어보자 𝑦=𝑎𝑥+𝑒 𝑦=𝑋𝛽 from text x y 3 1 16 2 24 37 4 44 5 56 𝑦=𝑎𝑥+𝑒 𝑦=𝑋𝛽 𝛽= 𝑋 𝑇 𝑋 −1 𝑋 𝑇 𝑦 X B Y 1 b1 3 b0 16 2 - 24 37 4 44 5 56

행렬을 자바에서 어떻게???? 역시나 라이브러리가 존재함 JAMA; JAva MAtrix package the package -> Jar file (Jama-1.0.3.jar) 받은 라이브러리를 테스트해볼 수 있게 프로젝트에 추가

행렬을 자바에서 어떻게???? 행렬 생성 방법 아래 표는 배열이 2중으로 있는 것으로 생각할 수 있음 JAMA에서 행렬 내 데이터는 실수(double)로 처리함 2중 배열은 배열을 표시하는 대괄호를 하나 더 넣어주는 것 x y 3 1 16 2 24 37 4 44 5 56 행 row 열 col

행렬을 자바에서 어떻게???? 데이터 불러오기 띄어쓰기 기준으로 숫자들이 저장되어있는 파일을 불러온다 띄어쓰기 기준으로 일단 나누지 않음 왜냐하면 배열을 만들어야하는데 전체 길이를 알 수 없기 때문에 리스트를 이용하여 먼저 데이터를 메모리에 모아둔다

행렬을 자바에서 어떻게???? 데이터로 행렬 만들기 띄어쓰기 기준으로 숫자들이 저장되어있는 파일을 불러온다 만들어야할 행렬은 먼저 두 개 (X6x2, Y6x1) X에 두번째 열이 전부 1인 이유는 b0를 bias로 하기 위함 X B Y 1 b1 3 b0 16 2 - 24 37 4 44 5 56

행렬을 자바에서 어떻게???? JAMA를 이용한 행렬 연산 JAMA로 어떻게 행렬을 계산하나? 𝑋 𝑇 𝑋 −1 𝑋𝑌 𝑋 𝑇 𝑌

행렬을 자바에서 어떻게???? JAMA를 이용한 행렬 연산 OLS로 B 행렬 계산 방법을 사용함 𝛽= 𝑋 𝑇 𝑋 −1 𝑋 𝑇 𝑦

MapReduce에서의 연산 어느 부분을 나누어서 작업할 수 있을까? 블럭 행렬(Block Matrix)을 이용하여 행렬 곱을 나누어 할 수 있음 𝑋= 𝑥 11 𝑥 12 𝑥 21 𝑥 22 𝑥 13 𝑥 14 𝑥 23 𝑥 24 𝑥 31 𝑥 32 𝑥 41 𝑥 42 𝑥 33 𝑥 34 𝑥 43 𝑥 44 = 𝑋 11 𝑋 12 𝑋 21 𝑋 22 𝑋 11 = 𝑥 11 𝑥 12 𝑥 21 𝑥 22 𝐴 𝑚×𝑝 𝑞 row partition column partition 𝑠 𝐵 𝑝×𝑛 𝑠 row partition column partition 𝑟 𝐶 𝛼𝛽 = 𝛾=1 𝑠 𝐴 𝛼𝛾 𝐵 𝛾𝛽 𝐶 𝑚×𝑛 =𝐴𝐵

MapReduce에서의 연산 어느 부분을 나누어서 작업할 수 있을까? 우리 데이터를 기준으로 생각하면? 𝑋= 𝑥 11 𝑥 12 𝑥 12 𝑥 22 = 𝑋 11 𝑋 21 𝑋 2×𝑚 𝑇 𝑞=1 row partition column partition 𝑠=# 𝑜𝑓 𝑀𝑎𝑝 𝑋 𝑚×2 𝑠=# 𝑜𝑓 𝑀𝑎𝑝 row partition column partition 𝑟=1 𝑋 𝑇 𝑋 11 = 𝛾=1 𝑠 𝐴 1𝛾 𝐵 𝛾1 𝑋 𝑇 𝑋 2×2 𝑋 𝑇 𝑋= 𝑋 1 𝑇 𝑋 1 + 𝑋 2 𝑇 𝑋 2 𝑋 1 =𝑋

MapReduce에서의 연산 어느 부분을 나누어서 작업할 수 있을까? 우리 데이터를 기준으로 생각하면? 𝑋 𝑇 𝑋 𝑋 𝑇 𝑦 입력된 데이터로 아래 두 행렬 곱의 일부를 계산할 수 있음 그럼 키는? 2가지가 필요 리듀스에서는 각 키마다 합을 구하면 위 두 행렬 곱을 계산할 수 있음 계산은 아직 더 남았다 역행렬과 한 번의 연산이 더 남았다 2x2 행렬 때문에 맵리듀스를 다시 돌려야하나? 한방에 어떻게 하고 싶다! 𝑋 𝑇 𝑋 𝑋 𝑇 𝑦 𝛽= 𝑋 𝑇 𝑋 −1 𝑋 𝑇 𝑦

MapReduce에서의 연산 어느 부분을 나누어서 작업할 수 있을까? 우리 데이터를 기준으로 생각하면? Map Reduce 겨우 몇번의 Summation 때문에 Reduce를 여러 개 할 필요는 없지 않나 리듀스에서 데이터를 구분할 수 있게 하자 데이터를 문자열로 바꾸고, 문자열의 맨 앞에 앞서 키로 사용하였던 것을 추가하여 값을 구분할 수 있도록 하자(마커 추가) Reduce에서 값의 맨 앞을 보고 나누어서 더하는 것! 행렬을 문자열로 상호 치환하는 메소드가 필요 OLSRegressionTest에 있죠? Map Reduce <K, V> <“1”, “A1234”> <“1”, [“A1234”, “B1234]”> <“1”, “B1234”> 𝑋= 𝑥 11 𝑥 12 𝑥 21 𝑥 22 " 𝑥 11 𝑥 12 @ 𝑥 21 𝑥 22 "

MapReduce에서의 연산 어느 부분을 나누어서 작업할 수 있을까? 우리 데이터를 기준으로 생각하면? 1millions 아래 명령어로 확인 가능 hadoop fs –ls /bigCourse/input 각 파일의 데이터 형태는 다음과 같음 한 줄에 백 만개의 데이터 쌍이 존재함 쌍의 구분은 @를 기준으로 나눔 x y 3 1 16 2 24 37 4 44 5 56 " 𝑥 11 𝑥 12 @ 𝑥 21 𝑥 22 @….." 1millions " 𝑥 11 𝑥 12 @ 𝑥 21 𝑥 22 @….." “0 3@1 16@2 24@3 37@4 44…”

MapReduce에서의 연산 새로 만든 OLS의 형태 행렬을 적절히 주고 받기 위한 입출력 형태 문자열로 행렬을 풀어서 표현했으므로, 모두 Text

MapReduce에서의 연산 새로 만든 OLS의 형태 main()에서 행렬을 표현하는 외부 라이브러리의 추가 HDFS 에 업로드한 후 해당 경로를 적어줌

MapReduce에서의 연산 새로 만든 OLS의 형태 map에서는 읽어온 문자열을 행렬로 변경한 후 연산 및 출력 우리는 출력을 key는 하나 value에서 두 행렬을 구분할 수 있도록 마커 추가

MapReduce에서의 연산 새로 만든 OLS의 형태 reduce에서는 모든 value 중 map에서 정한 마커에 따라 XX, XY를 합함 전부 합한 후에는 inverse 연산과 곱 연산을 통하여 B 행렬을 계산 그 후 다시 문자열로 변환하여 출력

MapReduce에서의 연산 OLS를 전부 짠 후에는? 외부 라이브러리로 반출 Xshell로 hadoop 클러스터 접속 및 개인 폴더로 이동 cd bigCourse/[학번] Xshell을 통하여 hadoop 클러스터에 복사 hadoop 에서 job 실행 hadoop jar OLSMR.jar OLSMR /bigCourse/input /bigCourse/[학번]/output 에러가 나는 경우는 output 폴더가 이미 존재하는 경우 hadoop fs –rmr /bigCourse/[학번]/output 결과를 hadoop에서 컴퓨터로 복사하기 hadoop fs –copyToLocal /bigCourse/[학번]/output/part-r-00000 . 결과 확인하기 cat part-r-00000

Appendix OLS template 및 테스트용 데이터 https://drive.google.com/open?id=0B2C49wBdxcD5VHdWV2I0TzFWdDQ https://drive.google.com/open?id=0B2C49wBdxcD5SGFyWExncVhiMmM

THANKS