massive data는 어떻게 선형회귀분석을 적용할까?

massive data는 행이 많은 상태. (너무 많아서 저장이 불가능한 정도라고 가정하자)

 

이떄 우리는 분할 정복 알고리즘을 통해 이를 해결할 수 있다.

1. 10년치 데이터 있다고 치면 1년단위로 데이터를 쪼게서 저장한다.

2. 1년치 데이터를 계산한다.

3. 결과를 합한다.

 

여기서 가장 중요한 점은 이렇게 구한 결과가 나누기 전과 동일하도록 보장시켜야한다는 것이다.

이전 선형회귀에 대한 글을 생각해보자

(Xibi-yi)^2 를 모두 더한걸 우리는 미분했었다. 그래서 편미분의 결과로 나오는 p*1 행렬은 -2X^t(Xb-y) 를 통해 구했다.

 

그래도 결과로 나오는 행렬의 크기는 p*1 이다.

 

y = a0 + xa1 꼴을 생각해보자

식이 n개 있다면 결과로 나오는 행렬은 아래와 같다.

1항 : 2(a0 + x11a1 - y1) + 2(a0 + x12a1 - y2) +...+ 2(a0 + xn2a1 - yn)

2항 : x11(a0 + x11a1 - y1) + x21(a0 + x21a1 - y2) + ... + xn21(a0 + xn1a1 - yn)

 

식이 2n개가 있다면 어떻게 될까?

1항 : 2(a0 + x11a1 - y1) + 2(a0 + x12a1 - y2) +...+ 2(a0 + x2n2a1 - y2n)

2항 : x11(a0 + x11a1 - y1) + x21(a0 + x21a1 - y2) + ... + x2n1(a0 + x2n1a1 - y2n)

 

결국 b의 개수가 동일하다면 반을 나눠서 나중에 더하든 한번에 더하든 결과가 같은것이다.

-2X^t(Xb-y) = 0 는 동일하다는걸 봤지만

 

X^tX값을 모으고 X^ty값을 모으는 것도 성립할까?

더 쉽게

1 1 

2 2

3 3 

해당 행렬의 제곱은 아래와 같다.

1*1+ 2*2 +3*3 ; 1*1+ 2*2 +3*3

1*1+ 2*2 +3*3 ; 1*1+ 2*2 +3*3

 

1 1

2 2

해당 행렬의 제곱은 아래와 같다.

1*1+ 2*2; 1*1+ 2*2

1*1+ 2*2; 1*1+ 2*2 

 

3 3 

해당 행렬의 제곱은 아래와 같다.

3*3 ; 3*3

3*3 ; 3*3

 

[1 2 3 4 5] * [1 2 3 4 5]^t 의 결과는 

1*1 + 2*2 + .. + 5*5.

 

[6 7 8 9 10] * [6 7 8 9 10]^t 의 결과는

6*6 + 7*7 + .. + 10*10

[1 2 3... 10] * [1 2 3 .. 10]^t 의 결과는

1*1 + 2*2 + .. + 10*10 이다.

 

따라서 X^tX 를 모으고 X^ty를 모아 매우 많은 행의 데이터를 선형회귀할 수 있게 되었다.