중위수 회귀분석
두 개의 점 A와 B가 있다고 치자. 둘을 잘 설명하는 직선은 다음과 같이 그려진다.
이 경우 흔히 아는 다음과 같은 공식으로 직선의 방정식을 구할 수 있다.
y-y_1 = \dfrac{y_2-y_1}{x_2-x_1}(x -x_1)
여러개의 점이 있다고 치자. 이들을 설명하는 직선을 회귀직선이라고 한다.
회귀직선의 경우, 점과 회귀선의 거리(\epsilon_n)를 최소화해야 한다.
\epsilon_n = y_n - (\beta_0 + \beta_1x)
이를 최소화하는 공식은 다음과 같다. 이를 \beta_0와 \beta_1로 편미분해 각각을 구해 선을 긋는다고 할 수 있다.
\displaystyle\min_{B_0,B_1}~
\sum~ \epsilon_i^2
~=~
\displaystyle\min_{B_0,B_1}~
\sum~
\{y_n - (\beta_0 + \beta_1x)\}^2
그런데, 제곱 대신 절댓값을 쓸 순 없을까?
\displaystyle\min_{B_0,B_1}~
\sum~ |\epsilon_i |
~=~
\displaystyle\min_{B_0,B_1}~
\sum~
|y_n - (\beta_0 + \beta_1x)|
이를 중위수 회귀분석, 영어로는 “Quantile Regression”이라고 한다.
이때 거리를 최소화하는 공식의 모양을 다시보자.
\displaystyle\min_{B_0,B_1}~
\sum~ |\epsilon_i |
~=~
\displaystyle\min_{B_0,B_1}~
\sum~
|y_n - (\beta_0 + \beta_1x)|
선형계획법의 목적함수와 같다.
따라서 중위수와 분위수를 구할 때, 심플렉스 알고리즘을 쓸 수 있다.
- 1차원 데이터에서의 분위수 회귀분석
- 중위수 구하기 (전체 데이터의 50%)
- 일반 사분위수 (전체 데이터의 n%)
- 2차원 데이터에서의 분위수 회귀분석
- 원점 지날 때 (전체 데이터의 50%)
- 원점 안 지날 때 (전체 데이터의 50%)
- 원점 지날 때 (전체 데이터의 n%)
1차원 데이터
중위수 구하기
심플렉스를 이용한 회귀직선 구하기로 중위수(=50% 분위수)를 구하자.
원래 중위수를 구하는 공식은 다음과 같다.
\displaystyle\min_{\mu}~
\sum |y_i - \mu|
이를 억지로 선형계획법처럼 만들어 보자.
목적함수
생각해보면, 중위수 공식을 풀어썼을 때 다음과 같다.
\displaystyle\min_{\mu}~
|y_1 - \mu| + |y_2 - \mu| + |y_3 - \mu| + \cdots
이를 벡터와 행렬로 바꾸면 다음과 같으며, 목적함수로 쓸 수 있다.
\displaystyle\min_{\mu}~
\begin{pmatrix}
1 & \cdots & 1
\end{pmatrix}
\begin{pmatrix}
|y_1 - \mu|
\\ \vdots
\\ |y_n - \mu|
\end{pmatrix}
\\[8pt]\downarrow\\[8pt]
\displaystyle\min_{\mu}~
\bold{1}^{\prime}
(\underline{y}-\underline{\mu})
제약조건 추가
어쨌든 선형계획법처럼 만들어야 하니 제약조건을 추가해야 한다.
위의 목적함수에서 제약조건이 될 수 있는 파트를 생각해 보면 y-\mu라고 할 수 있다.
그런데, 생각해야 할 것이 2개 있다.
-
y와 \mu에는 절댓값이 씌워져 있다. 계산이 꽤 불편하다.
따라서, 절댓값 테크닉을 쓰기 위해 새로운 변수를 넣어준다.
\text{s.t. }\;
y - \mu = u - v \\[10pt]
\Downarrow \\[14pt]
\begin{pmatrix}
y_1 - \mu_1 \\
\vdots \\
y_n - \mu_n \\
\end{pmatrix}
=
\begin{pmatrix}
u_1 - v_1 \\
\vdots \\
u_n - v_n \\
\end{pmatrix}
\\[10pt]
\updownarrow\\[10pt]
\text{s.t. }\;
\underline{y}-\underline{\mu} =
\underline{u}-\underline{v}
-
그렇다고 해도 \mu를 그냥 구하는 것 역시 불편하다.
따라서, \mu 역시 b_1과 b_2의 차으로 바꿔준다; \mu = b_1 - b_2
\text{s.t. }\;
y - (b_1 - b_2) = u - v\\[10pt]
\Downarrow \\[14pt]
\begin{pmatrix}
y_1 - b_1[1] + b_2[1]\\
\vdots \\
y_n - b_1[n] + b_2[n]\\
\end{pmatrix}
=
\begin{pmatrix}
u_1 - v_1 \\
\vdots \\
u_n - v_n \\
\end{pmatrix}
\\[10pt]
\updownarrow \\[14pt]
\text{s.t. }\;
\underline{y}-\underline{b_1}
+\underline{b_2} =
\underline{u}-\underline{v}
- 식을 y에 대해 정리한다.
- y = (주어지는 데이터) 이기 때문.
- y값만 넣고, 피봇연산으로 벡터 u,v만 조정하면 b1, b2를 구할 수 있다.
\text{s.t. }\;
\underline{y} =
\underline{b_1} -\underline{b_2} +
\underline{u}-\underline{v}
\\[15pt]
\Updownarrow \\[15pt]
\begin{matrix}
y_1\\
\vdots\\
y_n\\
\end{matrix}
~~~=~~~
\begin{matrix}
b_1[1] + b_2[1] \\
\vdots \\
b_1[n] + b_2[n]
\end{matrix}
~
\begin{matrix}
+u_1 & & &
-v_1 & & \\[3pt]
& \ddots & &
& \ddots & \\[3pt]
& & + u_n &
& &- v_n \\
\end{matrix}
\\[15pt]
\Updownarrow \\[15pt]
\text{s.t. }\;
\begin{bmatrix}
\bold{1} &
\bold{-1} &
\bold{I} &
\bold{-I}
\end{bmatrix}
\begin{bmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v} \\
\end{bmatrix}
목적함수 개조
- 목적함수에도 b_1, b_2 추가. 계산의 편의성을 위해서 넣어준다.
- 단 b1, b2에 해당하는 값은 0이다.
\displaystyle\min_{\mu}~
\begin{pmatrix}
0 & 0 & 1 & \cdots & 1
\end{pmatrix}
\begin{pmatrix}
0 \\ 0 \\
|y_1 - \mu|
\\ \vdots
\\ |y_n - \mu|
\end{pmatrix}
\\[8pt]\downarrow\\[8pt]
\displaystyle\min_{\mu}~
\begin{pmatrix}
0 & 0 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
결과적으로 목적함수와 제약조건은 다음과 같다.
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 &
\bold{1}^{\prime} &
\bold{1}^{\prime}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[30pt]
\text{s.t. }
&\begin{pmatrix}
\bold{1} &
\bold{-1} &
\bold{I} &
\bold{-I}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v} \\
\end{pmatrix}
=
\bold{y}
\end{align*}
예시 1
다음과 같은 순서통계량이 있다고 가정하자 ; A = [1,9,2,4,5]
제약식의 \underline{y} 벡터 부분 A를 넣고, 계속 피봇연산을 돌림.
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0&0 & 1&1&1&1&1 & 1&1&1&1&1 \\
& \textcolor{red}{-5}
&5 & 0&0&0&0&0 & 2&2&2&2&2 \\
\hline
\mu_1&\textcolor{red}{1}
&-1 &1&0&0&0&0&-1&0&0&0&0
&1\\
\mu_2&1&-1 &0&1&0&0&0&0&-1&0&0&0 &9\\
\mu_3&1&-1 &0&0&1&0&0&0&0&-1&0&0 &2\\
\mu_4&1&-1 &0&0&0&1&0&0&0&0&-1&0 &4\\
\mu_5&1&-1 &0&0&0&0&1&0&0&0&0&-1
&5\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0 & 0 & 5&0&0&0&0 &
\textcolor{red}{-3}
&2&2&2&2 \\
\hline
b_1&1&-1 &1&0&0&0&0&-1&0&0&0&0
&1\\
\mu_2&0&0 &0&1&0&0&0&1&-1&0&0&0 &8\\
\mu_3&0&0 &0&0&1&0&0&
\textcolor{red}{1}
&0&-1&0&0 &1\\
\mu_4&0&0 &0&0&0&1&0&1&0&0&-1&0 &3\\
\mu_5&0&0 &0&0&0&0&1&1&0&0&0&-1
&4\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|
rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0&0 & 2&0&3&0&0 & 0 &2&
\textcolor{red}{-1}
&2&2 \\
\hline
b_1&1&-1 &0&0&0&1&0 &0&0&-1&0&0
&2\\
\mu_2&0&0 &0&1&-1&0&0 &0&-1&1&0&0 &7\\
v_1&0&0 &-1&0&1&0&0 &1&0&-1&0&0 &1\\
\mu_4&0&0 &0&0&-1&1&0 &0&0&
\textcolor{red}{1}
&-1&0 &2\\
\mu_5&0&0 &0&0&-1&0&1 &0&0&1&0&-1
&3\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr
|rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0&0 & 2&0&2&1&3 & 0&2&0&1&2 \\
\hline
b_1&1&-1 &0&0&0&1&0&0&0&0&-1&0
&4\\
\mu_2&0&0 &0&1&0&0&0&0&-1&0&1&0 &5\\
v_1&0&0 &0&0&1&0&0&1&0&0&-1&0 &3\\
v_3&0&0 &0&0&0&1&0&0&0&0&-1&0 &2\\
\mu_5&0&0 &0&0&0&0&1&0&0&0&1&-1
&1\\
\end{array}
변수를 정리해보면 다음과 같다.
\def\arraystretch{1.5}
\begin{array} {rrrrr}
b_1 = 4 & b_2 = 0 \\
\mu_1 = 0 &
\mu_2 = 5 &
\mu_3 = 0 &
\mu_4 = 0 &
\mu_5 = 1 \\
v_1 = 3&
v_2 = 0&
v_3 = 2&
v_4 = 0&
v_5 = 0\\
\end{array}
\mu = b_1 - b_2 = 4-0 = 4
예시 2
다음과 같은 순서통계량이 있다고 가정하자 ; A = [1,-1,9]
이번에는 음수가 섞인 케이스이다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1
\\ \hline
\mu_1 & 1 & -1& 1& 0& 0& -1&0&0&1\\
\mu_2 & 1 & -1& 0& 1& 0& 0&-1&0&-1\\
\mu_3 & 1 & -1& 0& 0& 1& 0&0&-1&9\\
\end{array}
2번째 행 전체에 -1을 곱한다. 이때 기저도 바뀐다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 1 & 1 & 1
& 1 & 1 & 1 \\
& \textcolor{red}{-1}
& 1 & 0 & 2 & 0 & 2 & 0 & 2
\\\hline
\mu_1 & \textcolor{red}{1} & -1& 1& 0& 0& -1&0&0&1\\
v_2 & -1 & 1& 0& -1& 0& 0&1&0&1\\
\mu_3 & 1 & -1& 0& 0& 1& 0&0&-1&9\\
\end{array}
\\[10pt]
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 1 & 2 & 0 & 1 & 0 & 2
\\\hline
b_1 & 1 & -1& 1& 1& 0& 0& -1& 0& 1\\
v_2 & 0&0& 1&-1&0& -1&1&0&2\\
\mu_3 & 0&0& -1&0&1 &1&0&-1&8\\
\end{array}
\therefore\;\mu = b_1 - b_2 = 1
분위수 구하기
중위수(50%)를 확장해서 분위수(n%)를 구해보자.
기존의 식을 한번 쪼개보면 다음과 같다.
\displaystyle\min_{\mu}~
\sum |y_i - \mu|
=
\displaystyle\min_{\mu}~
\sum_
{\textcolor{red}{i \in A}}~
\frac{1}{2}~|y_i - \mu|
+
\displaystyle\min_{\mu}~
\sum_
{\textcolor{red}{i \in A^c}}~
\frac{1}{2}~|y_i - \mu|
\\[25pt]
\text{여기서 A는 다음과 같다.}
\\[10pt]
A = \{i~|~y_i \ge \mu\}
예를 들어 한번 보자.
순서통계량 [1,2,3,4,5] 가 있다고 치자.
만약 mu=3이면 A = [3,4,5]가 된다.
이때 식을 보면 다음과 같다.
min 0.5{(5-3)+(4-3)+(3-3)} + min 0.5{(2-3)+(1-3)}
이 값은 0이므로 최솟값이 성립한다.
기존의 식은 50분위수 였고, 지금은 n분위수니 식을 다음과 같이 바꾸면 된다.
\displaystyle\min_{\mu}~
\sum_{i \in A}~z~|y_i - \mu|
~+~
\displaystyle\min_{\mu}~
\sum_{i \in A^c}~(1-z)~|y_i - \mu|
\\[20pt]
A = \{i~|~y_i \ge \mu\}
~,~
0 \le z \le 1
목적함수와 제약조건
먼저 목적함수를 보자.
- \displaystyle \sum_{i \in A}~z~|y_i - \mu| 부분은 어차피 양수, u_i와 같다.
- \displaystyle \sum_{i \in A^c}~(1-z)~|y_i - \mu| 부분은 어차피 음수, v_i와 같다.
- 절댓값 테크닉에 따라 나눈 것.
\sum_{i \in A}~z~|y_i - \mu|
~+~
\sum_{i \in A^c}~(1-z)~|y_i - \mu|
\\[10pt]\Downarrow\\[10pt]
z~\underline{u_i} +
(1-z)~\underline{v_i}
\\[10pt]\Downarrow\\[10pt]
0~\cdot~b_1 +
0~\cdot~b_2 +
z~\underline{u_i} +
(1-z)~\underline{v_i}
\\[10pt]\Downarrow\\[10pt]
\begin{bmatrix}
0 & 0 & \bold{z} & \bold{1-z}
\end{bmatrix}
\begin{bmatrix}
b_1 \\ b_2 \\
\underline{u} \\
\underline{v} \\
\end{bmatrix}
제약조건을 살펴보자.
y_i - \mu
\\ \downarrow \\
y_i - \mu = u_i + v_i
\\ \downarrow \\
y_i = (b_1 - b_2) + u_i + v_i
\\[10pt] \Downarrow \\[10pt]
\underline{y} =
\underline{b_1} -\underline{b_2} +
\underline{u}-\underline{v}
\\[10pt] \Downarrow \\[10pt]
\begin{pmatrix}
\bold{1} &
\bold{-1} &
\bold{I} &
\bold{-I}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v} \\
\end{pmatrix}
=
\bold{y}
50분위수(중위수)의 제약조건과 비교해봐도 큰 변화가 없다.
식을 정리해보자.
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 &
\bold{z} &
\bold{1-z}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[30pt]
\text{s.t. }
&\begin{pmatrix}
\bold{1} &
\bold{-1} &
\bold{I} &
\bold{-I}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v} \\
\end{pmatrix}
=
\bold{y}
\end{align*}
예시 1
A = [1, 2, 7, 9, 10], z = 1/4 일때 100z 분위수는?
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0 & 0
&\frac{1}{4}&\frac{1}{4}
&\frac{1}{4}&\frac{1}{4}
&\frac{1}{4}
&\frac{3}{4}&\frac{3}{4}
&\frac{3}{4}&\frac{3}{4}
&\frac{3}{4}
\\
& 0 & 0
& 1&1&1&1&1
& 3&3&3&3&3
\\
& -5 & 5
& 0&0&0&0&0
& 4&4&4&4&4 \\
\hline
u_1&1
&-1 &1&0&0&0&0&-1&0&0&0&0
&1\\
u_2&1&-1 &0&1&0&0&0&0&-1&0&0&0 &2\\
u_3&1&-1 &0&0&1&0&0&0&0&-1&0&0 &7\\
u_4&1&-1 &0&0&0&1&0&0&0&0&-1&0 &9\\
u_5&1&-1 &0&0&0&0&1&0&0&0&0&-1
&10\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 &
\mu_3 & \mu_4 & \mu_5 &
v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0 & 0
& 5&0&0&0&0
& -1&4&4&4&4 \\
\hline
b_1
&1 &-1
&1&0&0&0&0
&-1&0&0&0&0 &1\\
u_2
&0 &0
&0&1&0&0&0
&1&-1&0&0&0 &1\\
u_3
&0 &0
&0&0&1&0&0
&1&0&-1&0&0 &6\\
u_4
&0 &0
&0&0&0&1&0
&1&0&0&-1&0 &8\\
u_5
&0& 0
&0&0&0&0&1
&1&0&0&0&-1 &9\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2
& \mu_1&\mu_2&\mu_3&\mu_4&\mu_5
& v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0 & 0
& 5&0&0&0&0
& -1&4&4&4&4 \\
\hline
b_1
&1 &-1
&1&0&0&0&0
&-1&0&0&0&0 &1\\
u_2
&0 &0
&0&1&0&0&0
&1&-1&0&0&0 &1\\
u_3
&0 &0
&0&0&1&0&0
&1&0&-1&0&0 &6\\
u_4
&0 &0
&0&0&0&1&0
&1&0&0&-1&0 &8\\
u_5
&0& 0
&0&0&0&0&1
&1&0&0&0&-1 &9\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrrrr|rrrrr|r}
& b_1 & b_2
& \mu_1&\mu_2&\mu_3&\mu_4&\mu_5
& v_1 & v_2 & v_3 & v_4 & v_5 & \\
& 0 & 0
& 4&1&0&0&0
& 0&3&4&4&4 \\
\hline
b_1
&1 &-1
&0&1&0&0&0
&0&-1&0&0&0 &1\\
v_1
&0 &0
&-1&1&0&0&0
&-1&1&0&0&0 &1\\
\mu_3
&0 &0
&0&0&1&0&0
&1&0&-1&0&0 &6\\
\mu_4
&0 &0
&\cdots&&\cdots&&\cdots
&\cdots&&\cdots&&\cdots &\cdot\\
\mu_5
&0& 0
&\cdots&&\cdots&&\cdots
&\cdots&&\cdots&&\cdots &\cdot\\
\end{array}
\therefore~\mu = b_1 - b_2 = 1
즉, [1,2,9,7,10] 중 25%에 해당 하는 수는 1이라는 뜻이다.
tip!
- Z가 클수록 계산량이 더 많아짐.
- 다만, 순서를 바꾸는 방법으로 해결 가능하다.
- 이렇게 구한 중위수는 항상 정수꼴이며, 원 데이터 안에 위치한다.
2차원 데이터
선형, 중위수, 원점 통과
원점을 지나는 회귀직선을 선형계획법으로 구해보자.
min \sum~ |y_i - \beta x_i|
1차원 데이터때와 달리 Beta에 -x_i가 곱해진 상태이다.
제약조건이 달라질수 밖에 없다.
y_i - \beta x_i = u_i + v_i \\
\Downarrow \\
\bold{y} - \beta\bold{x} = \bold{u} - \bold{v} \\
\bold{y} = \beta\bold{x} + \bold{u} - \bold{v} \\
\Downarrow \\
(b_1 - b_2)\bold{x} + \bold{u} - \bold{v} = \bold{y}\\
따라서 목적함수와 제약조건은 다음과 같다.
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 &
\bold{1}^{\prime} &
\bold{1}^{\prime}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[30pt]
\text{s.t. }
&\begin{pmatrix}
\bold{X} &
\bold{-X} &
\bold{I} &
\bold{-I}
\end{pmatrix}
\begin{pmatrix}
b_1 \\
b_2 \\
\underline{\mu} \\
\underline{v} \\
\end{pmatrix}
\end{align*}
예시
(1, 2), (3, 1), (4, 3)을 잇는 직선 구하기
- y값들을 y벡터가 들어갈 곳에 넣는다.
- x값들을 x벡터가 들어갈 곳에 넣는다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
& -8 & 8 & 0 & 0 & 0 & 2 & 2 & 2\\
\hline
\mu_1 & \textcolor{blue}{1}&
\textcolor{blue}{-1}&
1&0&0&-1&0&0&\textcolor{red}{2}\\
\mu_2 &
\textcolor{blue}{3}&
\textcolor{blue}{-3} &
0&1&0&
0&-1&0&\textcolor{red}{1}\\
\mu_3&
\textcolor{blue}{4}&
\textcolor{blue}{-4} &
0&0&1& 0&0&-1&\textcolor{red}{3}\\
\end{array}
이후 계속 기저를 고르고 피봇연산을 돌린다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& \textcolor{orange}{-8} & 8 & 0 & 0 & 0 & 2 & 2 & 2\\
\hline
\mu_1 & \textcolor{orange}{1}&
-1&
1&0&0&-1&0&0&2\\
\mu_2 &
3&-3 &
0&1&0&
0&-1&0&1\\
\mu_3&
4&-4 &
0&0&1& 0&0&-1&3\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 0 & \frac{8}{3} & 0 &
2 & \textcolor{orange}{-\frac{2}{3}} & 2\\
\hline
\mu_1 & 0 & 0&
1&-\frac{1}{3}&0&
-1&\frac{1}{3}&0&\frac{5}{3}\\
b_1 &
1&-1 &
0&\frac{1}{3}&0&
0&-\frac{1}{3}&0&\frac{1}{3}\\
\mu_3&
0&0&
0&-\frac{4}{3}&1&
0&\textcolor{orange}
{\frac{4}{3}}&-1&
\frac{5}{3}\\
\end{array}
\def\arraystretch{1.3}
\begin{array}{r|rr|rrr|rrr|r}
& b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 0 & 2 & \frac{1}{2} &
2 & 0 & 2\\
\hline
\mu_1 & 0 & 0&
1&0&-\frac{1}{4}&
-1&0&\frac{1}{4}&\frac{5}{4}\\
b_1 &
1&-1 &
0&0&\frac{1}{4}&
0&0&-\frac{1}{4}&\frac{3}{4}\\
v_2&
0&0&
0&-1&-\frac{3}{4}&
0&-1&-\frac{3}{4}&
\frac{5}{4}\\
\end{array}
\beta = b_1 - b_2 = \frac{3}{4} \\[10pt]
\therefore~~ y = \frac{3}{4}x
선형, 중위수, 원점 미통과
원점 안 지나는 회귀직선도 선형계획법으로 구해보자
min \sum~ |y_i - \beta_0 - \beta_1 x_i|
이번에는 회귀계수가 Beta_0과 Beta_1 두개로 늘어났다.
\beta_0 = a_1 - a_2
\beta_1 = b_1 - b_2
y_i -\beta_0 -\beta_1x_i = u_i + v_i \\
\Downarrow \\
\bold{y} - \beta_0 -\beta_1\bold{x} = \bold{u} - \bold{v} \\
\bold{y} = \beta_0 +\beta_1\bold{x} + \bold{u} - \bold{v} \\
\Downarrow \\
(a_1 - a_2)+
(b_1 - b_2)\bold{x} + \bold{u} - \bold{v} = \bold{y}\\
따라서 목적함수와 제약조건은 다음과 같다.
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 & 0 & 0 &
\bold{1}^{\prime} &
\bold{1}^{\prime}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[40pt]
\text{s.t. }
&\begin{pmatrix}
\bold{1} &
\bold{-1} &
\bold{X} &
\bold{-X} &
\bold{I} &
\bold{-I}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
\underline{\mu} \\
\underline{v} \\
\end{pmatrix}
\end{align*}
예시
(1, 2), (3, 1), (4, 3)을 잇는 직선 구하기
- y값들을 y벡터가 들어갈 곳에 넣는다.
- x값들을 x벡터가 들어갈 곳에 넣는다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rr|rrr|rrr|r}
&a_1 & a_2 & b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
& -3 & -3 & -8 & 8 & 0 & 0 & 0 & 2 & 2 & 2\\
\hline
\mu_1 & 1&-1& 1&-1 &
1&0&0& -1&0&0 &2\\
\mu_2 & 1&-1&
3&-3&0& 1&0&0&-1&0& 1\\
\mu_3 &
1&-1 &
4&-4&
0&0&1&
0&0&-1&
3\\
\end{array}
피봇연산을 진행해 보면 다음과 같다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rr|rrr|rrr|r}
&a_1 & a_2 & b_1 & b_2 & \mu_1 & \mu_2 & \mu_3
& v_1 & v_2 & v_3 & \\
& 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
& -3 & -3 & -8 & 8 & 0 & 0 & 0 & 2 & 2 & 2\\
\hline
\mu_1 & 1&-1& 1&-1 &
1&0&0& -1&0&0 &2\\
\mu_2 & 1&-1&
3&-3&0& 1&0&0&-1&0& 1\\
\mu_3 &
1&-1 &
4&-4&
0&0&1&
0&0&-1&
3\\
\end{array}
\beta_0 = \frac{5}{3} \\[10pt]
\beta_1 = \frac{1}{3} \\[10pt]
\therefore y = \frac{5}{3}x + \frac{1}{3}
선형, 분위수, 원점통과
- 여기서 n은 1~100
\displaystyle\min_{\mu}~
\sum_{i \in A}~z~
|y_i - \beta_0 - \beta_1x_i|
~+~
\displaystyle\min_{\mu}~
\sum_{i \in A^c}
~(1-z)~
|y_i - \beta_0 - \beta_1x_i|
\\[20pt]
A = \{i~|~y_i \ge \mu\}
~,~
0 \le z \le 1
계산량이 너무 많으므로 목적함수와 제약조건만 적어보자.
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 & 0 & 0 &
\bold{z} &
\bold{1-z}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[40pt]
\text{s.t. }
&\begin{pmatrix}
\bold{1} & \bold{-1} &
\bold{X} & \bold{-X} &
\bold{I} & \bold{-I}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
\underline{u} \\
\underline{v} \\
\end{pmatrix}
\end{align*}
tip!
- Z가 클수록 계산량이 더 많아짐.
- 다만, 순서를 바꾸는 방법으로 해결 가능하다.
- 이렇게 구한 중위수는 항상 정수꼴이며, 원 데이터 안에 위치한다.
비선형
min~ \sum~ |~y_i -\beta_0 -\beta_0x_i - \beta_2x_i^2~|
이번에는 회귀계수가 Beta_0과 Beta_1, Beta_2 3개로 늘어났다.
\beta_0 = a_1 - a_2
\beta_1 = b_1 - b_2
\beta_2 = c_1 - c_2
y_i -\beta_0 -\beta_0x_i - \beta_2x_i^2 = u_i - v_i\\[10pt]
\Downarrow \\[10pt]
\bold{y} - \beta_0 -\beta_1\bold{x}- \beta_2\bold{x}^2 = \bold{u} - \bold{v} \\[10pt]
\bold{y} = \beta_0 +\beta_1\bold{x} +\beta_2\bold{x}^2 + \bold{u} - \bold{v} \\[10pt]
\Downarrow \\[10pt]
(a_1 - a_2)+
(b_1 - b_2)\bold{x} +
(c_1 - c_2)\bold{x}^2 +
\bold{u} - \bold{v} = \bold{y}\\
이 경우 목적함수와 제약조건은…
\begin{align*}
\displaystyle\min_{\mu}~
&\begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 &
\bold{1}^{\prime} &
\bold{1}^{\prime}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
c_1 \\ c_2 \\
\underline{u} \\
\underline{v}
\end{pmatrix}
\\[40pt]
\text{s.t. }
&\begin{pmatrix}
\bold{1} & \bold{-1} &
\bold{X} & \bold{-X} &
\bold{X}^2 & \bold{-X}^2 &
\bold{I} & \bold{-I}
\end{pmatrix}
\begin{pmatrix}
a_1 \\ a_2 \\
b_1 \\ b_2 \\
c_1 \\ c_2 \\
\underline{\mu} \\
\underline{v} \\
\end{pmatrix}
\end{align*}
- \beta_0 = a_1 - a_2,~\beta_1 = b_1 - b_2,~\beta_2 = c_1 - c_2 로 놓은 것.
- 좀 길긴 하다.
예시
(1, 1), (2, 0), (3, 3), (4, 3)을 잇는 곡선 구하기
- y값들을 y벡터가 들어갈 곳에 넣는다.
- x값들을 x벡터가 들어갈 곳에 넣는다.
- x값의 제곱을 x^2벡터가 들어갈 곳에 넣는다.
\def\arraystretch{1.3}
\begin{array}{r|rr|rr|rr|rrrr|rrrr|r}
&a_1 & a_2 & b_1 & b_2 & c_1 & c_2 & \mu_1 & \mu_2 & \mu_3 & \mu_4
& v_1 & v_2 & v_3 & v_4\\
& 0 & 0 & 0 & 0 & 0 & 0
& 1 & 1 & 1 & 1
& 1 & 1 & 1 & 1 \\
& -4 & 4 & -10 & 10 & -30 & 30
& 0 & 0 & 0 & 0
& 2 & 2 & 2 & 2\\
\hline
\mu_1
& 1&-1& 1&-1 & 1 & -1
&1&0&0&0& -1&0&0&0
&1\\
\mu_2
& 1&-1& 3&-3 & 9 & -9
&0&1&0&0& 0&-1&0&0
&0\\
\mu_3
& 1&-1 & 4&-4& 16& -16
& 0&0&1&0& 0&0&-1&0
&3\\
\mu_4
& 1&-1 & 4&-4& 16& -16
&0&0 &
0&1& 0&0&0&-1
&3\\
\end{array}