검색 엔진을 개발할 때, 인터넷의 웹 페이지들을 사용자에게 제공함에 있어, 중요한 페이지를 우선적으로 노출시켜 주는 것이 중요합니다.
이 때, 어떤 페이지가 중요한지를 어떻게 알 수 있을까요?

## PageRank

PageRank가 높으면 중요한 페이지로 인식을 하게 됩니다.
이제, 페이지에 PageRank를 매기는 방법을 알아봅시다.

![231206-230644](/posts/final_05/231206-230644.png)

우선 인터넷은 방향 그래프의 형태로 표현 가능합니다.
여기서 중요한 페이지는 무엇일까요?

중요한 페이지는 아래와 같은 특징이 있습니다.

- 중요한(믿을만한) 정보는 중요한 정보를 **서로** 가리키는 경향이 있음
- 특정 query에 대한 링크를 많이 갖고 있는 페이지는 해당 query의 중요한 응답 페이지임

이를 in-link로 정리하면 다음과 같아집니다.

- 중요한 페이지는 in-link가 많음
- 같은 in-link 개수라도, 중요한 페이지로부터 오는 in-link가 많을수록 중요한 페이지임

<tip>
 `in-link / out-link`
 
 ![231206-231125](/posts/final_05/231206-231125.png)
</tip>

### Surfer model

그렇다면 in-link의 개수와 세기를 이용해서 페이지의 중요도를 파악해야 하는데, 어떤 방식으로 파악하는 것이 좋을까요?
그에 대한 하나의 해답으로 surfer model이 있습니다.

동작 방식은 다음과 같습니다.

1. 랜덤한 페이지들에 surfer를 배치
2. 한 스탭마다 페이지의 out-link로 surfer 들을 이동
3. 2번 반복
4. surfer들이 페이지들에 특정한 분포로 수렴하도록 이동함

여기서 중요한 점은 초기에 surfer를 어떻게 배치하더라도 결국은 특정한 분포로 페이지들에 분포하게 된다는 것입니다.
(마치 자연계의 생물 개체수가 일정 비율로 유지되듯...)

그렇다면 2번에서 surfer를 어떻게 이동시키는 걸까요?
위의 예시를 이용해서 알아봅시다.

![231206-230644](/posts/final_05/231206-230644.png)

$r_i$를 페이지 i의 rank라고 하고 페이지 y, a, m의 rank를 계산하면 아래와 같습니다.

$$
r_y = r_y/2 + r_a/2 \\
r_a = r_y/2 + r_m \\
r_m = r_a/2
$$

**각 페이지로 in-link되는 페이지의 1/out-degree 의 합**으로서 표현되며, 수식화하면 아래와 같습니다.

$$
r_j = \sum_{i \to j} \frac{r_i}{d_i}
$$

그렇다면 PageRank는 위에서 나온 3개의 식을 연립하여 계산하면 됩니다... 만,
해가 무수히 많이 나오는 문제가 있습니다.
따라서 $\sum{r_i} = 1$ 이라는 제약 조건을 달아서 계산하면 됩니다. (1말고 다른것도 가능하지만, 1이 쉬워서..)

하지만, 이 경우 시간복잡도가 $O(n^3)$이 나오기 때문에 현실세계에선 사용하기 어렵습니다.
따라서 행렬로 계산하는 것이 좋습니다.

$$
1 \begin{bmatrix}
r_y \\
r_a \\
r_m
\end{bmatrix} = \begin{bmatrix}
\frac{1}{2} & \frac{1}{2} & 0\\
\frac{1}{2} & 0 & 1 \\
0 & \frac{1}{2} & 0
\end{bmatrix} \begin{bmatrix}
r_y \\
r_a \\
r_m
\end{bmatrix}
$$

$$
r = M \cdot r
$$

여기서 1은 $\sum{r_i} = 1$ 에서 나온 제약 조건입니다.

즉, 이렇게 하면 앞에서 글로만 적었던 Surfer model의 동작방식을 알고리즘화 할 수 있습니다.

1. Set r = \[1/N, 1/N, 1/N\]
2. r' = Mr
3. r = r'
4. Goto 2

참고삼아 방향성이 없은 graph 모델의 경우 PageRank는 아래와 같은 수식으로 구할 수 있습니다.

$$
r_v = \frac{d_v}{2m}
$$

여기서 $d_v$는 **노드 v에 연결된 edge의 수**를 의미하고, m은 **전체 edge의 수**를 의미합니다.

<notice>
 Degree(in-link)가 높다고 PageRank가 항상 더 높은 것은 아닙니다.
 
 ![231206-233606](/posts/final_05/231206-233606.png)
 
 위 경우에는 3의 PageRank가 더 높을거 같지만, 1이 더 높게 측정됩니다.
</notice>

### Google formulation

기존 surfer model에는 치명적인 문제가 있습니다.
바로 Dead-end, Spider-trap 문제입니다.

![231206-233818](/posts/final_05/231206-233818.png)

이 경우 페이지 m이 spider-trap입니다.
다른 페이지로의 out-link가 없고 특정 circle에 같히기 떄문이죠.
이련 경우에는 PageRank 계산시 $r_m = 1$ 이 되어버리고, 나머지는 0이되는 문제가 발생합니다.

![231206-233954](/posts/final_05/231206-233954.png)

이 경우 페이지 m이 dead-end입니다.
out-link가 아예 존재하지 않아 surfer가 이동하지 못하고 소멸하기 때문이죠.
이런 경우에는 PageRank 계산시 모두 0이되는 문제가 발생합니다.

이런 현실세계의 문제를 해결하기 위해 Google에서 개선한 알고리즘이 바로 이것입니다.

- spider-trap을 예방하기 위해 일정 확률(대충 0.1~0.2)로 링크로 연결된 페이지가 아닌 아예 생뚱맞은 페이지로 surfer를 점프
- dead-end의 경우(out-link가 없는 경우) surfer를 생뚱맞은 페이지로 점프

이를 반영한 PageRank 수식은 다음과 같습니다.

$$
r_j = \sum_{i \to j} \beta \frac{r_i}{d_i} + (1-\beta)\frac{1}{N}
$$

앞에 $\frac{r_i}{d_i}$ 부분은 위와 동일합니다.
다만, $\beta$의 확률로만 적용됩니다. (대략 0.8~0.9)

나머지 0.1~0.2의 확률로는 N개의 페이지 중 하나로 이동하는 방식을 적용한 것입니다!

그럼 여기서 의문점이 듭니다.

> spider-trap은 해결한거 같은데 dead-end는요?

spider-trap인지 아닌지는 판단할 수 있는 방법이 없기 때문에 위와 같이 확률에 의존하여 해결하였지만,
dead-end인지 아닌지는 판단할 수 있는 방법이 존재합니다. (단순히 out-link의 개수가 0이면 dead-end)
따라서 dead-end의 경우에는 그냥 surfer를 다른곳으로 점프시키면 됩니다.

위 식을 행렬식으로 변환해볼까요?

$$
\begin{bmatrix}
r_y \\
r_a \\
r_m
\end{bmatrix} = (0.8 \begin{bmatrix}
\frac{1}{2} & \frac{1}{2} & 0\\
\frac{1}{2} & 0 & 1 \\
0 & \frac{1}{2} & 0
\end{bmatrix} + 0.2 \begin{bmatrix}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3}
\end{bmatrix})\begin{bmatrix}
r_y \\
r_a \\
r_m
\end{bmatrix}
$$

인터넷 페이지의 중요도 순위를 매기는 방법을 알아봅니다.

PageRank

사람이 손수 작성한 추천목록, 플레이리스트 등 기존의 추천엔 한계가 있습니다.
따라서 개인화된 추천 시스템을 만들어야 하는데, 이를 개발할 때 여러 문제점들이 있습니다.

- 훈련 데이터를 얻기 힘듦
- 입력 안된 데이터를 채우기 힘듦 (평가 안된 항목 예측이 힘듦)
- 추천 방식의 성능을 평가할 방식을 찾기 힘듦

그렇기에 이러한 요소를 염두해두고 아래의 소개되는 추천 시스템을 비교하며 알아보도록 합시다.

## Content-based

기본적인 아이디어는 추천 대상을 여러가지 키워드의 벡터로 표현하고, 유저의 추천 대상에 대한 평점을 기반으로 벡터의 값을 계산해 비슷한 아이템을 추천하는 것입니다.

따라서, 우선 영화라고 한다면 감독, 배우, 장르 등등의 키워드로서 영화를 표현해야 하는데요, 특징을 추출하는데는 TF-IDF 휴리스틱 알고리즘이 사용됩니다.

### TF-IDF

IF-IDF score는 아래와 같은 수식으로 계산합니다.

$w_{ij} = TF_{ij} \times IDF_i$
_j: 문서, i: 단어_

여기서 TF는 i-단어가 j-문서에 얼마나 많이 등장하는지에 대한 척도로, 아래와 같이 계산됩니다.

$$
TF_{ij} = \frac{f_{ij}}{max_k f_{kj}}
$$

**i-단어의 등장횟수**를 **한 문서에 대해 가장 많이 등장하는 단어의 등장횟수**로 나눠줌으로서 문서의 길이에 비해 많이 나오는 정도(normalize)를 캐치합니다.

하지만, 모든 문서에 대해 빈번하게 등장하는 단어의 경우에는 키워드로서 부적절 할 것입니다.
따라서 이런 단어들에 대한 페널티를 부과하기 위해 IDF 항이 존재하며, 식은 아래와 같습니다.

$$
IDF_i = log \frac{N}{n_i}
$$

**전체 문서의 개수**를 **i-단어가 나온 문서의 수**로 나눠줍니다.
즉, 단어가 특이하게 많이 등장할수록 큰 점수를 부여하는 방식입니다.

### User Profiles

TF-IDF를 이용해서 item을 프로파일링 했으니, 이제 user를 프로파일링 해보겠습니다.

예로 들어 아래와 같이 프로파일링된 item들이 있다고 가정해보겠습니다.
TF-IDF에서 선택된 키워드는 1, 아닌 키워드는 0으로 표기됩니다.

| | keywordA | keywordB | keywordC | keywordD | keywordE |
|---|---|---|---|---|---|
| itemA | 1 | 1 | 0 | 0 | 0 |
| itemB | 1 | 0 | 1 | 0 | 0 |
| itemC | 0 | 0 | 0 | 1 | 1 |

그리고 user들이 이런 item에 평점을 매겼다고 가정해보겠습니다.

| | itemA | itemB | itemC | average |
|---|---|---|---|---|
| user1 | 5(1) | 3(-1) | 0 | 4 |
| user2 | 3(0) | 1(-2) | 2(-1) | 3 |
| user3 | 3(0) | 0 | 3(0) | 3 |
| rate(diff) ||||

user 프로파일링은 item profile에 대한 평점을 이용한 가중평균을 사용합니다.

| user1 | keywordA | keywordB | keywordC | keywordD | keywordE |
|---|---|---|---|---|---|
| itemA | 5 | 5 | 0 | 0 | 0 |
| itemB | 4 | 0 | 4 | 0 | 0 |
| itemC | 0 | 0 | 0 | 0 | 0 |
| average | 3 | 5/3 | 4/3 | 0 | 0 |

하지만, 이렇게되면 유저가 평가하지 않은 항목에 대해서는 반드시 부정적인 평가가 이루어지게 되는 문제가 있습니다.
따라서, **유저의 평점에서 평점의 평균 뺀 값 (diff)** 을 사용해서 가중평균을 구하는 것이 좋습니다.

| user1 | keywordA | keywordB | keywordC | keywordD | keywordE |
|---|---|---|---|---|---|
| itemA | 1 | 1 | 0 | 0 | 0 |
| itemB | -1 | 0 | -1 | 0 | 0 |
| itemC | 0 | 0 | 0 | 0 | 0 |
| average | 0 | 1/3 | -1/3 | 0 | 0 |

같은 방식으로 user를 모두 프로파일링 하면 다음과 같은 profile을 얻을 수 있습니다.

| | keywordA | keywordB | keywordC | keywordD | keywordE |
|---|---|---|---|---|---|
| user1 | 0 | 1/3 | -1/3 | 0 | 0 |
| user2 | -2/3 | 0 | -2/3 | -1/3 | -1/3 |
| user3 | 0 | 0 | 0 | 0 | 0 |

<tip>
 user profile를 이용해서 비슷한 사용자를 찾을 때는 cosine 유사도, L1-norm 유사도의 방법을 사용하곤 합니다.
 cosine 유사도(방향)는 취향 유사도를 판단할 때 쓰이고, L1-norm(차원별 거리)는 구매력 유사도를 판단할 때 사용하면 좋습니다.
</tip>

<tip>
 user profile를 이용해서 비슷한 item을 찾을 때는 [`LSH`](https://wjlee611.github.io/blog/univ_mmds/final_01)를 사용하면 됩니다.
</tip>

### Pros & Cons

장점
- 다른 유저가 없어도 item을 추천할 수 있다(cold start 문제가 없다)
 (물론, user profiling은 cold start 문제가 있다)
- 독특한 취향의 사람에게도 추천할 수 있다
- 새로운 item이나, 독특한 item의 경우에도 잘 동작한다
- 추천에 대한 설명도 제공할 수 있다

단점
- 분야에 따라 추출해야 하는 keyword를 찾아야 한다
- 새로운 user에 대한 추천은 어렵다
- 너무 사용자 전용 추천이 되어버린다
 (관심 밖은 추천이 아예 안되고, 다른 사람의 취향(트렌드)를 따르지 않음)

---

## Collaborative Filtering

위에서는 item을 프로파일링 했다면, Collaborative Filtering 방식은 그런 프로파일을 작성하지 않습니다.
이 방식은 단순히 utility matrix(위에 user의 item에 대한 평점 matrix)를 사용합니다.

### User-User C.F.

나와 비슷한 유저를 추천해주는 시스템을 만들기 위해 User-User Collaborative Filtering을 사용합니다.
빠르게 LSH로 찾을 수도 있겠지만, 정밀한 추천을 위해 예시와 함께 다른 추천방법을 알아봅시다.

우선, 유저 A~D의 item에 대한 평점정보가 아래와 같이 있다고 가정해봅시다.

| | item1 | item2 | item3 | item4 | item5 | item6 | item7 | avg |
|---|---|---|---|---|---|---|---|---|
| A | 4 | | | 5 | 1 | | | 10/3 |
| B | 5 | 5 | 4 | | | | | 14/3 |
| C | | | | 2 | 4 | 5 | | 11/3 |
| D | | 3 | | | | | 3 | 3 |

만약 Jaccard 유사도를 기준으로 측정한다면 어떻게 될까요?
A-B 유사도는 1/5, A-C 유사도는 1/2가 나올 것입니다.
Jaccard 유사도는 영화의 평점을 반영하지 못하기 때문에 여기서 사용하는 것은 부적절해 보입니다.

이번엔 Cosine 유사도를 기준으로 측정해봅시다.
A-B 유사도는 0.380, A-C 유사도는 0.322가 나올 것입니다.
B가 C보다 A와 비슷하다는 점은 잘 캐치하는 것을 볼 수 있습니다.
하지만, C가 A와 비슷한게 아니라 취향이 다르다는 점은 캐치하지 못합니다.

Negative도 캐치할 수 있도록 피어슨 상관계수를 기준으로 측정해봅시다.
<tip>
 피어슨 상관계수는 평점을 평점의 평균으로 뺀 값을을 코사인 유사도를 측정한 것입니다.
 피어슨 상관계수를 사용하면 좋은게, 부정적인 정도도 나타낼 수 있을 뿐만 아니라,
 사용자가 평가하지 않은 항목은 0으로 출력한다는 점에서 좋습니다.
</tip>
A-B 유사도는 0.092, A-C 유사도는 -0.559가 나올 것입니다.
이제는 얼마나 다른지도 \[-1, 1\] 범위로 잘 측정할 수 있습니다.

이렇게 나온 필터를 이용해서 유저에게 영화를 추천할 수 있습니다.
위에서 나온 가중평균을 이용하면 되는데요, 여기서는 소개하지 않겠습니다.
왜냐하면, Item-Item 필터로 추천하는 것이 성능이 더 좋기 때문입니다.
(user의 취향은 여러개가 동시에 존재할 수 있지만, item은 일정하고 간단하기 때문)

### Item-Item C.F.

이제 Item-Item Collaborative Filtering 을 이용해서 item의 평점을 예측하고, 그 평점을 바탕으로 user에게 추천을 주도록 해봅시다.

위의 예시를 그대로 사용하겠습니다.
여기서 item2을 userA에게 추천할만한지 판단하기 위해 userA의 item2에 대한 평점을 예측해보겠습니다. 

| | item1 | item2 | item3 | item4 | item5 | item6 | item7 |
|---|---|---|---|---|---|---|---|
| A | 4(2/3) | **\[!\]** | | 5(5/3) | 1(-7/3) | | |
| B | 5(1/3) | 5(1/3) | 4(-2/3) | | | | |
| C | | | | 2(-5/3) | 4(1/3) | 5(4/3) | |
| D | | 3(0) | | | | | 3(0) |
| $Sim_{item2}$ | 0.45 | 1.00 | -1.00 | 0 | 0 | 0 | 0 |

여기서 $Sim_{item2}$는 item2에 대한 각 item의 피어슨 상관계수를 구한 것입니다.
이제 item2의 가중평균을 아래와 같은 계산식으로 구해줍니다.

$$
\frac{0.45*4 + 0*5 + 0*1}{0.45 + 0 + 0} = 4
$$

즉, item2에 대한 userA의 평점을 4로 예측하였고, 이는 userA 평균평점 이상이기에 추천할만한 item이라 판단할 수 있겠습니다.

<notice>
 지금은 가중 평균 계산시 모든 item을 다 사용했지만,
 일반적으로는 Sim(유사도)이 높은 k개의 item만을 가지고 평점을 예측합니다.
</notice>

**장단점**은 Content-based와 정 반대입니다.

추가로, 유사한 k개를 찾을 때, 그 k를 구하는 것이 어렵다는 단점도 있습니다.
그럴때는 그냥 LSH, 클러스터링, 차원축소 등을 사용하는 것도 하나의 방법입니다.
추천 알고리즘의 정답은 없으니까요!

<tip>
 추천 시스템을 개발할 때는 일반적으로 복잡한 알고리즘을 쓰는 것 보다,
 단순한 알고리즘을 쓰되, 데이터를 많이 집어넣는게 좋습니다.
</tip>

---

## Evaluating Prediction

마지막으로 추천 시스템을 평가하는 방법을 알아봅시다.
대표적으로 아래의 평가 방법이 있습니다.

- RMSE
 오차의 제곱근(큰 오차에 대한 페널티 부여)의 평균을 이용합니다.
 $\sqrt{\frac{1}{N} \sum_{xi}(r_{xi}-r_{xi}^*)^2}$
- MAE
 오차의 절댓값의 평균을 이용합니다.
 $\frac{1}{N} \sum_{xi}|r_{xi}-r_{xi}^*|$

예시로 알아봅시다.

| | | MAE | RMSE |
|---|---|---|---|
| 실제 평점 | 2 2 2 | - | - | 
| 예측 A | 3 3 3 | 1 | 1 |
| 예측 B | 2 2 5 | 1 | $\sqrt{3}$ |

물론 이 측정 방법의 한계도 존재합니다.
바로, 아래의 상황을 반영하지 못하는 것이죠..

- 추천 다양성
 e.g. 어떤 영화를 많이 봤는데, 이와 다른 장르는 추천하지 않는 현상
- 추천 문맥
 e.g. 여행 당시에 사놓은 여행 서적의 기록을 갖고, 평상시에도 여행 서적을 추천하는 현상
- 추천의 순서
 e.g. 시리즈물은 순서별로 추천해야 하는데 그렇지 않은 현상

추천 시스템의 종류와 동작 방식에 대해 알아봅니다.

Recommender System

## Dimensionality Reduction

차원 축소 방법에 대해 알아보기 전에, 왜 차원축소를 하는걸까요?
다음과 같은 이유들이 있다고 생각합니다.

- [**차원의 저주**](https://wjlee611.github.io/blog/univ_mmds/final_02#curse-of-dimensionality) 해결
- 데이터 용량 절약
- 잠재된 관점(축)의 발견

그렇다면 차원 축소는 어떤 원리를 이용해서 하게 되는 걸까요?
아래의 예시를 봐봅시다.

![231204-135530](/posts/final_03/231204-135530.png)

좌측은 2차원 데이터인데 하나의 직선 위에 데이터들이 많이 밀집된 형태를 보입니다.
우측은 3차원 데이터인데 하나의 평면 위에 데이터들이 많이 밀집된 형태를 보입니다.

만약, 직선이나 평면에 데이터들을 적절하게 투영(projection)할 수 있다면?
데이터를 표현하기 위해 2, 3개의 파라미터를 사용해야 했던 것에 반해, 1, 2개의 파라미터 만으로 데이터를 표현할 수 있을 것입니다.

그렇지만, 무턱대고 투영하는 것은 좋지 않습니다.
최대한 데이터의 손실이 적도록 투영하는게 옳은 방법이겠죠?

데이터의 손실이 적도록 차원을 축소하기 위해서는 새로운(낮은) 차원의 축을 잘 선택해야 합니다.
축을 잘 선택하는 방법은 아래와 같은 순서로 진행하면 왠만하면 차원 축소할 때 데이터의 손실이 적을 것입니다.

1. 데이터의 분산이 가장 큰 방향의 축을 선택
2. 1에서 선택한 축의 수직인 방향의 축을 선택
3. 1, 2에서 선택한 축의 수직인 방향의 축을 선택... (반복)

### Rank

축을 선택하는 방법은 대강 알 거 같습니다.
그러면 얼마나 축을 뽑는게 좋은걸까요?

답은 행렬의 rank 에 해당하는 만큼 축을 뽑으면 됩니다.

<tip>
 `Rank`
 
 rank는 선형 독립적인 행의 개수를 의미합니다.
</tip>

예시와 함께 알아봅시다.

$$
A = \begin{bmatrix}
1 & 2 & 1 \\
-2 & -3 & 1 \\
3 & 5 & 0 \\
\end{bmatrix}
$$

rank(A) = 2 입니다.
왜냐하면 3행은 **1행 - 2행** 으로 표현되기 때문에 3행은 선형 종속적인 행이기 때문입니다.

즉, 기존 basis \[1 0 0\], \[0 1 0\], \[0 0 1\] 의 3축에서 \[1 2 1\], \[-2 -3 1\] 의 2축으로 차원을 축소할 수 있습니다.
그렇다면 A는 아래와 같이 변형되겠죠?

$$
A_{with\_new\_basis} = \begin{bmatrix}
1 & 0 \\
0 & 1 \\
1 & -1 \\
\end{bmatrix}
$$

---

## SVD

3차원은.. 좀만 노력하면 분해할 수 있지만, 30차원이 넘어간다면?
아마 특정 공식에 의존하여 분해하는 것이 좋을 것입니다.
차원을 직접적으로 축소하는 방법은 아니지만, 하나의 행렬을 의미가 담긴 3개의 행렬로 분해하는 방법이 바로 SVD, 고윳값 분해 입니다.

![231204-142024](/posts/final_03/231204-142024.png)

행렬 A는 $U \sum V^T$로 데이터 손실 없이 분해됩니다.
다만 차원을 줄이기 위해 r을 보다 작은 값으로 분해하여 약간의 데이터 손실과 함께 차원을 축소하는 것이죠.

아무튼, SVD는 위의 $U \sum V^T$ 형태의 3개의 행렬로 분해하는데, 각각 행렬마다 중요한 특징이 있습니다.
그 특징을 아래의 예시와 함께 살펴보겠습니다.

![231204-143118](/posts/final_03/231204-143118.png)

우선 **$A$** 부터 살펴보겠습니다.
예시로 든 행렬은 유저가 평가한 영화 평점에 대한 행렬입니다.
예로 들어, 4행의 유저는 SciFi한 영화에는 5점을 남겼지만, Romance 영화는 관심도 없다는 의미겠네요.

다음은 **$\sum$** 을 살펴보겠습니다.
$\sum$은 대각 행렬로, 원소가 좌상단부터 우하단으로 반드시 내림차순 정렬되어 있습니다.
그렇기 때문에 SVD시 $U \sum V^T$가 유일하게 결정됩니다.

여기서 $\sum$은 `concept`의 세기에 대한 정보를 담고 있습니다.
| Value | Concept |
|---|---|
| 12.4 | Sci-fi |
| 9.5 | Romance |
| 1.3 | Romance-Alien |

즉 데이터들이 Sci-fi, Romance 한 concept에 대해 분산이 크지만,
Romance-Alien 과 같은 잡스러운(?) concept에 대한 분산은 낮음을 알 수 있습니다.
(차후에 이를 이용해 차원 축소를 하게 됩니다)

다음은 **$U$** 를 살펴보겠습니다.
이 행렬은 유저에 대한 concept 정보를 담고 있습니다. (별로 안중요함)

마지막으로 **$V^T$** 를 살펴보겠습니다.
이 행렬은 영화에 대한 concept 정보를 담고 있습니다. (별로 안중요함)

### D.R. with SVD

이제 고윳값 분해 방식과 의미를 알았으니 차원을 실제로 축소해봅시다.

바로 위에서 다음과 같이 언급했었습니다.

> 즉 데이터들이 Sci-fi, Romance 한 concept에 대해 분산이 크지만,
> Romance-Alien 과 같은 잡스러운(?) concept에 대한 분산은 낮음을 알 수 있습니다.

분산이 크다는 것은 해당 축으로 투영시켰을 때, 데이터 손실이 적다는 것을 의미한다고 했었습니다.
즉, $\sum$의 값이 작은 부분을 제거한다면?
영향력이 적은 차원을 제거하는 꼴이 되어버려서 차원 축소를 달성할 수 있습니다!

![231204-144815](/posts/final_03/231204-144815.png)

이렇게 SVD로 분해된 세 행렬을 계산하면 다음과 같이 복원할 수 있습니다.

![231204-144924](/posts/final_03/231204-144924.png)

상당히 유사하지만, 데이터 손실 때문에 완벽하게 복원되지는 않았습니다.
즉, 데이터의 손실이 발생할 수 있는 점을 염두하여 차원을 축소해야 합니다.

그렇다면 차원축소는 얼마나 하는것이 좋을까요?

정해진 답은 없지만, 일반적으로 SVD된 $\sum$ 행렬의 에너지(대각선 제곱의 합)의 90% 이상 남기는 것이 좋다고 알려져 있습니다.
예로 들어서 차원 축소 전의 $\sum$ 에너지는 아래와 같습니다.

$$
12.4^2 + 9.5^2 + 1.3^2 = 245.7
$$

Romance-Alien concept를 제거한다면 에너지는 아래와 같이 감소합니다.

$$
12.4^2 + 9.5^2 = 244.01
$$

즉, Romance-Alien concept 차원을 제거하여 축소한다고 해도 원본의 99%에 해당하는 에너지가 해당되기에 차원을 축소해도 데이터 손실이 거의 없습니다.
하지만, 여기에서 Romance concept까지 제거한다면?

$$
12.4^2 = 153.76
$$

62.6%의 에너지밖에 남지 않습니다.
즉, 차원을 많이 줄일수는 있지만, 복원했을 때 유의미한 데이터를 얻을 수는 없을 것입니다.

---

## Application

이제 실제 예시와 함께 분석하는 방법을 알아봅시다.

![231204-144815](/posts/final_03/231204-144815.png)

위와 같이 관리되고 있는 추천 시스템 데이터에서 "Matrix" 와 같은 SciFi concept의 영화를 좋아하는 유저를 찾고싶다고 해봅시다.

![231204-150645](/posts/final_03/231204-150645.png)

그럴 때는 유저 벡터를 concept-space에 투영해서 그 방향(경향)을 비교하는게 좋습니다.
그리고 그 투영을 구하는 방법은 $q \cdot V_{concept}$ 이죠.

예로 들어 아래와 같은 유저 p, q의 영화 성향이 같은지 다른지를 판단해봅시다.

$$
p = \begin{bmatrix}
5 & 0 & 0 & 0 & 0 
\end{bmatrix}
$$
$$
q = \begin{bmatrix}
0 & 4 & 5 & 0 & 0 
\end{bmatrix}
$$

Jaccard 유사도, LSH와 같은 방식을 사용한다면, 두 사람은 전혀 다른 취향을 가진 사람이라고 판단할 것입니다.
하지만, $q \cdot V$을 이용하여 concept 벡터를 만들어 비교해본다면 어떨까요?

$$
p_{concept} = \begin{bmatrix}
5 & 0 & 0 & 0 & 0 
\end{bmatrix} \begin{bmatrix}
0.56 & 0.12 \\
0.59 & -0.02 \\
0.56 & 0.12 \\
0.09 & -0.69 \\
0.09 & -0.69
\end{bmatrix} = \begin{bmatrix}
2.8 & 0.6
\end{bmatrix}
$$
$$
q_{concept} = \begin{bmatrix}
0 & 4 & 5 & 0 & 0 
\end{bmatrix} \begin{bmatrix}
0.56 & 0.12 \\
0.59 & -0.02 \\
0.56 & 0.12 \\
0.09 & -0.69 \\
0.09 & -0.69
\end{bmatrix} = \begin{bmatrix}
5.2 & 0.4
\end{bmatrix}
$$

p, q 유저의 성향이 비슷하다고 판단되었습니다.
심지어 SVD 이후 차원까지 축소했는데도 말이죠!

이렇듯 취향을 판단하면서, 데이터를 압축해야 할 경우에는 SVD가 유리하게 작동합니다.
또한, 차원을 낮추면서 근사하는 방식에는 SVD가 최적해를 도출한다고 증명이 되었습니다.

하지만, 압축한 데이터에 대해서는 해석할 수 없으며, 원래 행렬의 대부분의 값이 0으로 채워진 경우에는 SVD를 하면 오히려 원소의 개수가 늘어난다는 단점도 있습니다.

차원 축소 기법과 고윳값 분해에 대해 알아봅니다.

Dimensionality Reduction & SVD

## Clustering

군집화란 여러개의 점(데이터)들의 집합이 주어졌을 때, 거리에 따라 점들을 그룹으로 묶는 행위를 의미합니다.
점들을 그룹으로 묶을 때는 유사도(거리)를 기준으로 cluster를 생성하게 되는데요, 사용되는 거리의 단위에는 아래와 같은 것들이 있습니다.

- **Euclidean**
 - $L_2$ norm
 일반적인 두 점 사이의 거리 ($\sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$)

 - $L_1$ norm (Manhattan distance)
 차원별로 두 점 사이의 거리 ($|x_a - x_b| + |y_a - y_b|$)

 즉, L1, L2 norm이 같은 경우는 같은 차원 축 위에 존재하는 경우밖에 없습니다. (L1의 값이 L2보다 같거나 더 큽니다)

 <tip>
 L2는 차원간 거리의 차이가 클 수록 페널티를 부여하는 효과가 있습니다.
 
 예로 들어, 점 x로 부터의 거리가 각 축별로 다음과 같다고 가정해봅시다.
 A = 2,3,4
 B = 1,3,5
 
 이 때 L1는 거리가 9로 같지만, L2는 B가 더 멀다고 판단합니다.
 (3축의 거리차가 더 크기에 더 큰 페널티 부여)
 </tip>


- **Cosine** (for vector)
 $cos(x,y) = \frac{x \cdot y}{||x|| \cdot ||y||}$
 방향성이 얼마나 비슷한지를 거리로 사용합니다.
 내적 식과 동일합니다.

- **Jaccard** (for sets)
 e.g. Jaccard 유사도가 1이다 &rarr; 두 원소가 완전 일치한다 &rarr; 거리는 0이다

- **Edit distance** (for strings)
 문자열 x가 문자열 y로 변환되기 위한 과정의 횟수를 거리로 사용합니다.
 여기서 LCS 라는 개념이 등장하는데, LCS는 끊겨도 상관없는 올바른 순서로 존재하는 공통 문자 쌍의 개수를 의미합니다.
 e.g. x = a**bcde**, y = **bcd**uv**e** &rarr; LCS(x, y) = **bcde**
 |x| - |y| - 2|LCS(x, y)| = 5 + 6 - 2*4 = 3 &rarr; **distance = 3**

 <tip>
 x = ab, y = ba의 경우에는 LCS가 a or b 로 2개 생길 수도 있습니다.
 이 경우의 x, y의 edit distance는 아무튼 2로 동일하긴 합니다.
 </tip>

단, 클러스터링을 하더라도, 특정 클러스터가 어떤 그룹인지는 알 수 없습니다.
사람이 직접 라벨링을 하거나, 데이터의 분포로 추측하는 수 밖에 없습니다.

### Curse of Dimensionality

그럼 단순하게 거리계산을 이용한 클러스터링? 쉬워 보입니다.
하지만 현실은 차원의 저주 때문에 클러스터링이 제대로 이뤄지지 않습니다.

차원의 저주란 고차원에서 보면 매우 달라보이는 두 데이터가 비슷하게 분류되는 문제를 의미합니다.
예시와 함께 알아봅시다.

구간 \[0, 1\] 사이에 1만개의 서로 다른 점이 있다고 가정해봅시다.
0.1%, 즉 10개의 이웃한 점을 추출한다고 했을 때 각 차원별로 축의 몇%에 해당하는 범위의 점들이 포함될까요?

1차원에서는 일직선 위의 0.1%, 즉, 축위의 0\~0.001 사이의 점들이 비슷한 정도 0.1%에 해당하는 점들입니다.
2차원에서는 평면위의 0.1%, 즉, 각 축위의 0\~0.032 사이의 점들이 비슷한 정도 0.1%에 해당하는 점들입니다. (0.032${^2} \approx$ 0.001)
n차원에서는 n차원의 0.1%, 즉, 각 축위의 0\~0.001$^{1/n}$ 사이의 점들이 비슷한 정도 0.1%에 해당하는 점들입니다. ((0.001$^{1/n}$)${^n}$ = 0.001)

즉, 차원이 높아질수록 각 축에서는 더 넓은 범위에서 비슷하다고 판단하게 됩니다.
10차원(n=10)의 경우에는 (0, 0, ... , 0)과 (0.5, 0.5, ..., 0.5)도 상위 0.1%로 비슷하다고 판단해 버립니다.

### Clustrting Strategies

클러스터링 전략은 크게 2가지로 나뉩니다.

1. 계층적 클러스터링
 1. bottom up
 각 점이 클러스터 1개를 생성사고, 가까운(비슷한) 클러스터끼리 병합하여 커지는 방식
 2. top down
 하나의 단일 클러스터로 시작하여 클러스터를 분리해나가는 방식

 ![231203-230112](/posts/final_02/231203-230112.png)

 중심 포인트가 구분되지 않는다면 hierachical 방식이 더 좋습니다.

2. 점 할당 클러스터링

 하나의 점을 향하는 점들끼리 클러스터링 하는 방식 (e.g. k-means)

 ![231203-230031](/posts/final_02/231203-230031.png)

 중심 포인트가 구분된다면 point-assignment 방식이 더 좋습니다.

또한, 데이터가 유클리드 공간에 표현할 수 있는 경우에는 거리를 L1, L2 norm과 같은 유클리드 거리로 계산하지만,
유클리드 공간에 표현 불가능한 경우에는 거리를 Cosine, Jaccard, Edit-distance 등으로 거리를 계산합니다.

---

## Hierachical Clustering

계층적 클러스터링 중에서 bottom-up 방식의 클러스터링에 대해 알아보겠습니다.
이 경우에는 클러스터링을 할 때, 다음과 같은 의문점을 해결해야 합니다.

1. 클러스터를 어떤식으로 표현하는가?
2. 가까운(비슷한) 클러스터의 기준이 무엇인가?
3. 합치는 과정을 언제 멈추는게 좋은가?

이 경우에는 유클리드 공간과 비 유클리드 공간에서 정의되는 경우를 나누어서 살펴보겠습니다.

### In Euclidean

**1에 대한 해결방법**으로 centroid 개념을 도입하면 됩니다.
Centroid란, 클러스터 내부 점들의 평균값으로 가상의 점을 생성하여 그 가상의 점을 centroid라고 합니다.

**2에 대한 해결방법**으로, 유클리드 공간의 경우 centroid간 거리가 가장 짧은 클러스터가 가장 가까운 클러스터가 됩니다.
즉, centroid가 가장 짧은 두 클러스터를 병합하면 됩니다.

**3에 대한 해결방법**으로, 아래와 같은 경우에 병합을 중단하는게 좋습니다.
- 클러스터의 직경이 너무 커질 경우
- 클러스터의 밀도가 너무 작을 경우
- 클러스터의 직경이나 밀도의 변화가 급작스럽게 변할 경우

중단에 대한 평가법은 비 유클리드 공간에서도 동일하게 사용되기 때문에 비 유클리드 공간에서는 굳이 2번 언급하지 않겠습니다.

### In Non-Euclidean

비 유클리드 공간에서는 centroid를 정의할 수 없습니다.
따라서 이를 대신할 방법이 2가지 정도가 존재합니다.

- A - clusteroid
- B - 클러스터 내부의 모든 점으로 표현

따라서 여기서 또 케이스를 나누어 살펴봅시다.

**1-A에 대한 해결방법**으로 clusteroid 개념을 도입합니다.
가상의 점인 centroid와 다르게 clusteroid는 실제로 존재하는 포인트 중 하나를 대표값으로 설정하는 방법입니다.
따라서 점들 중에서 어떤 점을 clusteroid로서 선택할지에 대한 여러 방법론이 존재합니다.

![231204-123642](/posts/final_02/231204-123642.png)

클러스터의 내부 점들이 아래와 같이 형성되었다고 가정해봅시다. (2, 3번은 outlier)

1. inf-norm

 다른 점들까지의 거리의 최댓값이 가장 작은 점을 선택하는 방법입니다.
 이 경우에는 2의 점이 clusteroid로 선택이 될 것입니다.

2. L1-norm

 다른 점들까지의 평균 거리가 가장 짧은 점을 선택하는 방법입니다.
 이 경우에는 1에 있는 점들 중 하나가 clusteroid로 선택이 될 것입니다.

3. L2-norm

 다른 점들까지의 거리 제곱의 평균이 가장 짧은 점을 선택하는 방법입니다.
 이 경우도 2번과 유사하게 동작합니다.
 하지만, 먼 거리일수록 패털티를 크게 부여한다는 점에서 다르게 사용될 수 있습니다.

**2-A에 대한 해결방법**으로, 유클리드 공간에서의 2번 해결법과 동일합니다.
다만, centroid가 아닌 clusteroid를 사용한다는 차이점만이 존재합니다.


**1-B에 대한 해결방법**으로 별도의 대표값을 지정하는 것이 아닌, 클러스터 내부의 점들 그 자체를 평가 요소로 사용합니다.
그렇다면 이 경우에는 거리를 측정하는 방법을 찾는게 가장 중요한 요소가 되겠죠?

**2-B에 대한 해결방법**으로 아래와 같은 방법을 생각해볼 수 있겠습니다.

- 클러스터 사이의 거리가 가장 짧은 점 2개를 기준으로 거리 측정
- 클러스터 사이의 거리가 가장 긴 점 2개를 기준으로 거리 측정
 &rarr; 이 경우에는 클러스터를 병합했을 때의 생성되는 클러스터의 직경을 의미하며 작을 수록 좋습니다.
- 모든 점들의 페어에 대한 거리의 평균으로 측정
 &rarr; 이 경우에는 클러스터간 점들의 평균 거리를 의미하며 역시 작을 수록 좋습니다.
- 직경이나 평균 거리를 구한 뒤에 그 안에 들어있는 점들의 개수(밀도)를 측정
 &rarr; 이 경우에는 위 방식들과 다르게 새로운 클러스터를 마지한다고 가정하고 진행합니다. 밀도가 높을수록 좋습니다.

이렇게 방법이 많은데 그럼 무슨 클러스터링 방법을 써야 할까요?
답은, 알 수 없습니다.
데이터의 케이스가 굉장히 다양하기 때문이죠..

![231204-125101](/posts/final_02/231204-125101.png)

이런 경우에는 centroid 방식으로는 잘 동작합니다. (색칠된 영역으로 클러스터가 병합됩니다)
하지만, `클러스터 사이의 거리가 가장 짧은 점 2개를 기준으로 거리 측정`하는 방식으로는 잘 동작하지 않을 것입니다. (A, C 클러스터가 병합해버림)

![231204-125304](/posts/final_02/231204-125304.png)

이런 경우에는 반대로 centroid 방식으로는 잘 동작하지 않을 것입니다.

여기서 알 수 있듯, 계층적 구조는 클러스터링에서 최적해를 보장하지 않는다는 것을 알 수 있습니다.

---

## K-means (Point-assignment) Clustering

K-means 알고리즘은 point-assignment clustering 방식의 대표적인 알고리즘 입니다.
k개의 클러스터를 찾는 알고리즘인데, 위의 계층적 클러스터링 방식과 마찬가지로 최적해를 보장하지는 않습니다.

알고리즘의 동작 방식은 다음과 같습니다.

1. 일단은 랜덤하게 k개의 중심을 정한다.
2. 각 점들은 가장 가까운 중심으로 연결한다. (임시 클러스터 생성)
3. 연결, 즉, 임시 클러스터가 생성되면 임시 클러스터의 점들의 실제 중심으로 중심을 이동시킨다.
 여담으로, 여기서 말하는 중심은 `In Non-Euclidean - 1-A에 대한 해결방법 - L2-norm`과 비슷하게 거리의 제곱이 최소화 되는 곳을 중심으로 합니다.
4. 2, 3 과정을 반복하며 클러스터의 centroid가 안정(수렴)되면 종료합니다.

단, k-means 방식은 결과 또한 보장받을 수가 없는게, 초기값의 영향을 많이 받기 때문에 무한루프에 빠질 가능성이 있기 때문입니다.
아래의 예시가 그러한 경우입니다.

![231204-130321](/posts/final_02/231204-130321.png)

따라서 이런 경우를 방지하기 위해 실제 점을 초기값으로 잡거나, k-means++ 방식을 사용합니다.

<tip>
 `K-means++`
 
 랜덤 중심을 정할 때, 이미 선택된 랜점 중심을 고려해서 고르자는 아이디어에서 출발하는 개선 알고리즘 입니다.
 이미 선택된 랜덤 중심으로부터 거리가 멀 수록 선택 확률을 높이는 방식으로 동작합니다.
</tip>

### vs. Hierachical

계층적 클러스터링과 비교했을 때, K-means의 장점은 거리 비교 횟수가 적다는 것입니다.
계층적 클러스터링 방식은 점들마다 다른 점들의 개수 만큼의 비교 횟수가 필요합니다.
하지만, k-means 방식은 점들마다 centroid의 개수 만큼의 비교 횟수만이 필요하기에 빠르게 군집화를 달성할 수 있습니다.

### Getting the k right

그렇다면 k 개수는 어느정도로 설정하는 것이 좋을까요?

![231204-131006](/posts/final_02/231204-131006.png)

centroid 까지의 거리가 유의미한 수준으로 줄어드는 정도에서 멈추는 것이 좋습니다.
즉, 거리가 줄어들긴 해도 유의미한 수준으로 줄어들지 않는다면 그 시점의 k의 개수를 선택하는 것입니다.

![231204-131019](/posts/final_02/231204-131019.png)
![231204-131033](/posts/final_02/231204-131033.png)
![231204-131046](/posts/final_02/231204-131046.png)

여러 군집화 방법에 대해 알아봅니다.

Clustering


## LSH

LSH는 비슷한 객체를 찾는 방식 중 하나로, 일반 해싱과 비슷하게 동작하지만, 큰 차이가 있습니다.

일반 해싱은 데이터가 조금만 달라져도 아웃풋이 완전히 달라지는 반면,
LSH는 해싱을 부분적으로 진행하기 때문에 조금만 달라지면 아웃풋도 조금만 달라지게 됩니다.

예시를 통해 알아봅시다.

![231203-203340](/posts/final_01/231203-203340.png)

LSH는 해싱을 진행할 때, 전체 데이터를 해싱하는 것이 아닌, 전체 데이터를 b등분한 b개의 bands를 각각 해싱합니다.
해싱된 band는 그 아웃풋에 해당하는 bucket에 담기게 됩니다.

만약 두 문서가 비슷하다면 어떨까요?
비슷한 두 문서는 높은 확률로 시그니처가 동일한 band를 갖고 있을 것입니다.
즉, 비슷한 분서는 같은 bucket에 담기는 band를 공유하고 있을 것입니다.

물론, 다른 입력에 대해 같은 아웃풋이 해싱에는 존재할 수 있습니다.
따라서 가능한 많은 bucket를 확보하여 분류하는 것이 좋습니다.
또는 각 band 별로 다른 해시 테이블을 사용하여 다른 버킷에 할당될 수 있도록 하는 것도 방법입니다.

그런데 LSH가 얼마나 효율적인지도 알아봐야겠죠?

10만개의 문서가 각각 길이 100의 시그니처를 갖고있다고 가정해봅시다.
80% 비슷한 문서, 즉 시그니처가 80개 이상 일치하는 비슷한 pair를 찾고싶다면, 일반적인 방법으로는 아래와 같은 연산 횟수가 필요합니다.

$$
100000 + ... + 2 + 1 = 100001 * 50000 \approx 5B
$$

즉 10만개의 문서을 일일이 비교하려면 약 50억 번의 비교 연산이 필요합니다.

하지만, LSH로 우선 비교 대상을 줄인다면?
LSH로 10만 번의 연산이 필요하고, 비교 대상이 100개로 줄어든다면 아래와 같은 연산 횟수가 필요합니다.

$$
100000 + 100 + ... + 2 + 1 = 100000 + 5050 = 105050
$$

LSH를 사용하는 것 만으로 연산 횟수가 기하급수적으로 줄어든 것을 확인할 수 있었습니다.
하지만, 앞서 언급했 듯, 다른 band도 같은 bucket에 들어갈 확률이 있습니다.

그렇기에 LSH는 false negative가 발생할 확률도 있기 때문에, 같은 bucket에 들어간 candidate pair에 대해 실제로도 비슷한지 전 시그니처를 검사하는 과정을 거쳐 유사도를 판단하는 게 좋습니다.
(LSH는 전처리 과정일 뿐!)

### Confidence

그렇다면, LSH의 신뢰도는 얼마나 될까요?

5int/band 단위로 길이 100의 시그니처를 20개의 bands로 분할하고, LSH를 적용한다고 가정해봅시다.

문서 $C_1$, $C_2$가 80% 확률로 비슷할 때, 한 band가 같은 버킷에 들어갈 확률은 다음과 같습니다.

$$
(0.8)^5 \approx 0.328
$$

그렇다면, 20개의 모든 밴드가 다른 버킷의 들어갈 확률은 다음과 같아집니다.

$$
(1-0.328)^20 \approx 0.00035
$$

즉, 문서 $C_1$, $C_2$가 80% 확률로 비슷하다면 약 99.99965%의 확률로 최소한 하나의 bucket에 두 band가 들어갈 것입니다.

40% 확률로 비슷한 경우는 어떨까요?

$$
(0.4)^5 \approx 0.01 \\
(1-0.01)^20 \approx 0.82
$$

즉, 40% 확률로 비슷하다면 약 18%의 확률로 최소한 하나의 bucket에 두 band가 들어갈 것입니다.

40%만 비슷해도 비슷하다고 판단해야 하는 시스템의 경우 88%의 케이스가 False positive가 되어버립니다.
그럼에도 불구하고 50억번 비교하는 것 보다는 나을 것입니다.

### Analysis

위의 경우 80% 유사도를 검사할 때는 신뢰도가 매우 높았지만, 40%을 검사할 때는 신뢰도가 상당히 낮았습니다.
신뢰도는 b(bands)와 r(ints/band)의 값에 영향을 받는데, 각각의 파라미터가 어느정도일 때 유사도에 따른 신뢰도는 어떻게 나오는 걸까요?

![231203-210605](/posts/final_01/231203-210605.png)

우선 band가 1개일 때의 신뢰도 입니다.
band가 1개라는 것은 그냥 데이터 전체를 해싱하는 것과 같습니다.

![231203-210859](/posts/final_01/231203-210859.png)

다음은 band가 b개이고, r ints/band 일 때의 일치율 s에 따른 신뢰도 입니다.
$$
1 - (1-s^r)^b
$$
$(1/b)^{1/r}$ 지점에서 신뢰도가 급격하게 증가하는 모습을 볼 수 있습니다.
b=20, r=5일 때 약 55% 일치율 지점에서 급격하게 증가합니다.

Locality-Sensitive Hashing과 응용에 대해 알아봅니다.

생김새가 비슷한 사이트를 묶거나, 표절 검사를 하거나, 비슷한 내용의 뉴스를 클러스터링 하는 등 여러 분야에서 사용될 수 있는 기술에 대해 설명합니다.

<notice>
 생김새가 비슷한 문서를 찾아내는 기술이지, 비슷한 토픽을 찾아내는 기술은 아닙니다.
</notice>

아래의 단계를 거쳐 비슷한 문서를 찾게 되는데, 각 단계에 대한 세부적인 내용은 추후에 설명합니다.

1. `Shingling`을 통해 데이터(문서)를 집합으로 변환
2. `Minhashing`을 통해 큰 집합을 작은 시그니처로 변환
3. `LSH`를 통해 시그니처를 분류 후 비슷한 집합 찾기

## Jaccard Similarity

세부내용 설명 전 개념 하나만 짚고 넘어가자.
유사도를 검사할 때, 다음과 같은 경우를 고려해보자.

A, B 모두 메이져한 게임들을 주로 플레이하고, A는 RPG를, B는 FPS를 주로 플레이한다고 가정하자.
이 때, 마이너한 장르의 게임을 예시로 들며 유사도를 검사하는데, A, B 모두 해당 게임을 보유하지 않는다고 두 사람의 유사도가 높다고 이야기 할 수 있을까?
두 사람은 그런 마이너한 장르의 게임에 관심이 없어서 갖고있지 않을 뿐인데, 둘 다 갖고있지 않다고 두 사람의 플레이스타일이 유사하다고 판단하는 것은 무리가 있다.

따라서 이런 유사도 파악의 오류를 해결하기 위해 Jaccard 유사도를 사용하여 유사도를 측정하게 된다.

$$
Sim(C_1, C_2) = \frac{|C_1 \cap C_2|}{|C_1 \cup C_2|}
$$

즉, **두 사람 중 한 사람이라도 해당 게임을 보유하고 있는 경우에만 두 사람이 동시에 해당 게임을 보유하는가**로 유사도를 검사하는 것이다.

---

## Shingling

문서의 유사도를 측정할 때 그 기준이 되는 토큰을 생성하는 방법입니다.
`k-shingle` 과 같은 용어를 사용하는데, 이는 k개의 문자로 이루어진 shingle을 의미합니다.
실제로 비슷한 문서를 싱글링 했을 때 집합의 원소도 일치하는 부분이 매우 많습니다.

예로 들어 \"The dog which chased the cat\" 이라는 문장이 있다고 했을 때, 여기서 2-shingle를 구하면 다음과 같습니다.

> th(보통 소문자로 변환), he, e_, _d, do, og, ...

하지만, 2-shingle로 하면 th, he, do와 같이 문장으로 볼 때는 상당히 유니크한 의미를 갖는 문장이 이렇게 아무데서나 나올법한 shingle이 되어버립니다.
따라서 보통은 `8~10`-shingle로 하는 것이 적당합니다.

### Tokens

10-shingle을 사용하는 경우에는 최대 $27^{10} \approx 200조$ 개의 싱글이 생성되게 됩니다.
이를 메모리상에서 관리하는 것은 현실적으로 불가능한 일입니다.

따라서 싱글을 해싱하여 4bytes의 자료형으로 변환하여 `Token`으로서 사용하게 됩니다.
4bytes로 최대 약 42억개의 서로 다른 싱글을 표현할 수 있습니다.
물론 다른 싱글에 대해 같은 토큰이 생성될 수 있지만, 그리 빈번한 경우는 아닐 것이며, 효율상 이 방법이 더 좋습니다.

즉, 같은 토큰을 보유한 문서가 있다면, 그 문서들은 같은 싱글을 갖고있다는 얘기이므로, 유사도가 있다고 판단할 수 있겠습니다.

---

## Minhashing

Minhashing을 알아보기 전, 데이터를 표현하는 행렬을 읽는 법을 알고가자.

| (token) | $C_1$ | $C_2$ |
|---|---|---|
| a | 0 | 0 |
| b | 1 | 0 |
| c | 0 | 1 |
| d | 1 | 1 |

a 토큰(싱글)은 문서(Column) 1, 2에서 모두 없다는 뜻이고, b는 문서 1에서만 갖고있다는 뜻으로 해석하면 된다.
참고로 위의 경우 두 문서의 Jaccard 유사도는 **1/3**이다. (a는 둘 다 없기에 비교대상이 아니다)

### Permute the rows

우선 행을 핸덤으로 뒤죽박죽 섞는다.
섞는다는 것은 실제로 맊 섞는다는 것이 아닌, 탐색 순서를 섞는다는 것을 의미하는데, 구현 관점에서 해싱을 돌리는 것과 같다.
예시를 보며 이해해보자.

| (row) | $C_1$ | $C_2$ | $C_3$ |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 |

$h_1(x) = x \% 5$ 해시함수를 적용하면 탐색 순서는 다음과 같아진다.

> **5**(0) &rarr; **1**(1) &rarr; **2**(2) &rarr; **3**(3) &rarr; **4**(4)

$h_2(x) = (2x+1) \% 5$ 해시함수를 적용하면 탐색 순서는 다음과 같아진다.

> **2**(0) &rarr; **5**(1) &rarr; **3**(2) &rarr; **1**(3) &rarr; **4**(4)

### Create signature

탐색 순서에 맞게 처음으로 1(토큰 보유)을 만나는 탐색 순서를 기록한다.

> $h_1$를 적용한 탐색시 생성되는 Singature matrix
> [1, 2, 1]
>
> $h_2$를 적용한 탐색시 생성되는 Singature matrix
> [1, 3, 1]

즉, $C_1$에 대한 시그니처는 11, $C_2$는 23, $C_3$은 11이 된다.

여기서 중요한 특징이 있는데, 시그니처의 길이가 길어질 수록(무작위 순서에 의한 탐색 횟수가 늘어날 수록) 시그니처가 일치할 확률이 Jaccard 유사도와 확률이 같아진다.
그 이유를 간단한 예시로 이해해보자.

우선, $C_2$과 $C_3$의 Jaccard 유사도는 **1/4**이다.
그런데 이 때, Singature가 같아지는 경우는 무엇일까? 바로 **최초로 1이 나오는 시점이 같다**는 이야기이다.
즉, 같은 row에 대해 둘 다 1이 들어가 있는 row를 고를 확률과 같아진다.
둘 다 0인 경우를 제외하면 4개 중에 둘 다 1인 row는 1개 존재하기에 Jaccard 유사도와 동일한 **1/4** 확률을 갖는다.

![231020-235719](/posts/mid_05/231020-235719.png)

이해를 돕기 위해 다른 예시도 보자.

원래대로라면 생성되는 모든 토큰(42억개)에 대해 유사도를 검사 했어야 했다.
하지만, 시그니처를 만드는 과정에서 무작위 순서로 탐색을 진핼할 때, 탐색개수를 제한을 걸면 검사 시간을 줄일 수 있다.
예로 들어 해시함수의 결과를 50까지만 검색한다면 42억개의 항목에 대해 검사를 진행하지 않아도 된다. 

이 때 검사 개수를 줄인 만큼 서로다른 해시를 여러 번 진행하면 신뢰도 역시 어느정도 확보할 수 있다.
예로 들어 서로 다른 해시함수 100개를 적용한다면, 시그니처의 길이가 100으로 결정되는데, 이 길이는 충분히 신뢰도를 확보할 수 있을 것이다.
즉, 42억개에서 100개로 압축되는 효과가 발생하는 것이다.

위의 사진을 예시로 실제 Jaccard 유사도와 시그니처 유사도를 비교해보며 시그니처 길이가 신뢰도에 어느정도 영향을 주는지 알아보자.

> Column 1, 2
> Jaccard Similarity: **1/4**
> Singature Similarity: **1/3**
>
> Column 2, 3
> Jaccard Similarity: **1/5**
> Singature Similarity: **1/3**
>
> Column 3, 4
> Jaccard Similarity: **1/5**
> Singature Similarity: **0**

### implement

의사코드로 구현해보고 시그니처 생성과정을 살펴보자.

```cpp:의사코드
// 처음에 무한대로 초기화
for (all i and c) M(i, c) = inf;

// 각 행에 대해 반복하는데, 여기에 탐색개수 50개와 같은 제한을 걸 수 있음
for (each row r) {
 for (each hash function h_i) {
 compute h_i(r);
 }
 for (each column c) {
 // 탐색지점에 1이 있는 경우
 if (c has 1 in row r) {
 for (each hash function h_1) {
 // 저장된 시그니처보다 새 탐색값이 작은 경우에만 업데이트
 if (h_i(r) is smaller them M(i, c)) {
 M(i, c) = h_i(r);
 }
 }
 }
 }
}
```

![231021-001859](/posts/mid_05/231021-001859.png)

유사도 높은 문서를 찾아내는 방법을 알아봅니다.

Finding Similar Items


## Application

연관 규칙을 응용할 수 있는 분야를 살펴보면서 대략적인 이해와 필요성에 대해 알아보자.

![231020-201233](/posts/mid_04/231020-201233.png)

장을볼 때 각 장바구니에 어떤 물건을 샀는지를 나타내는 표이다.
이 표를 간단하게 분석해보면, `Milk`를 산 사람은 대체로 `Coke`를 사는 경향이 있고, `Diaper, Milk`를 동시에 산 사람은 대체로 `Beer`를 산 경향이 있는걸로 보인다.
이렇게 사람들의 구매 경향을 분석할 때 사용하기도 한다.

또한 문서 상에서 **\{the\} &rarr; \{cat\}** 이라는 규칙이 있다면 the 라는 단어 뒤에는 대체적으로 cat 이라는 단어가 나온다는 뜻으로, 자연어처리시 문법을 파악하고 학습시키는데 도움이 될 수도 있다.

그 외에도 여러 분야에서 활용될 수 있지만, 섣부른 일반화는 안된다.
예로 들어 **비타민C를 많이 먹는 사람들은 불면증을 겪는 경향이 있다**는 규칙을 발견했다면, **비타민C를 안먹는 경우**에도 불면증 경향이 있는지 검사해봐야 확실해는 것이다.

## Frequent Itemset

Frequent Itemset을 구하는 방법은 [**`저번 포스트`**](https://wjlee611.github.io/blog/univ_mmds/mid_03)에서 알아봤으니, 이젠 용어과 수식을 통해 연관 규칙을 정의하는 것을 알아보자.

### Support

**Support for itemset I** 라고 한다면 itemset I가 등장한 횟수를 의미한다.
전체 basket에서 itemset I가 등장한 횟수를 카운트 하면 된다.
이 때, Support threshold S 보다 크다면 빈번하다고 판단하게 되는 것이다.

| Baskets | m(ilk), c(oke), p(epsi), b(read), j(am) |
| --- | --- |
| $B_1$ = **\{m, c, b\}** | $B_2$ = **\{m, p, j\}** |
| $B_3$ = **\{m, b\}** | $B_4$ = **\{c, j\}** |
| $B_5$ = **\{m, p, b\}** | $B_6$ = **\{m, c, b, j\}** |
| $B_7$ = **\{c, b, j\}** | $B_8$ = **\{b, c\}** |

예로 들어 위와 같이 목록들이 존재하고, Support threshold가 `3 baskets` 라고 주어진다면,
Frequent itemset은 아래와 같이 나오게 된다.

> **\{m\}, \{c\}, \{b\}, \{j\}, \{m, b\}, \{b, c\}, \{c, j\}**

## Association Rules

**특정 집합($I$)이 등장할 때 $j$ 하는 경향이 있다** 라는 연관 규칙을 수식화 하면 아래와 같이 표현이 가능하다.

> $\{i_1, \; i_2, \; ,... \; , i_k\}$ &rarr; $j$

### Confidence

이 떄, 그 경향에 대한 신뢰도, `Confidence`는 아래와 같이 수식화 할 수 있다.

$$
conf(I \rightarrow j) = \frac{support(I \cup j)}{support(I)}
$$

즉 조건부에 해당하는 itemset이 등장할 확률 기반으로 itemset + j 가 동시에 등장할 확률을 구하면 되는 것이다.

### Interest

하지만 신뢰도가 높다고 반드시 의미있는 규칙이 발견된 것은 아니다.

예로 들어 **X &rarr; milk** 라는 규칙을 발견했다고 가정하자.
그러나, 굳이 X가 아니더라고 그냥 milk는 많이 사기때문에 둘 사이에 연관성이 깊다고 판단하기에는 무리가 있다.

이 떄문에 `Interest`의 개념이 존재한다.

$$
Interest(I \rightarrow j) = | conf(I \rightarrow j) - Pr[j] | \\
Pr[j] = \frac{support(j)}{표본 \; 수}
$$

흥미도는 I 신뢰도에서 j가 등장할 확률을 뺀 값의 절댓값과 같다.

보통 해당 값이 `0.5보다 크다`면 해당 규칙이 의존성이 있다는 의미가 된다.
만약 `-0.5보다 작은` 경우에도 의존성이 있다는 의미가 있는데 이 경우에는 **I, j를 둘 다 사는 경우는 없다**는 뜻으로 해석할 수 있다.

| Baskets | m(ilk), c(oke), p(epsi), b(read), j(am) |
| --- | --- |
| $B_1$ = **\{m, c, b\}** | $B_2$ = **\{m, p, j\}** |
| $B_3$ = **\{m, b\}** | $B_4$ = **\{c, j\}** |
| $B_5$ = **\{m, p, b\}** | $B_6$ = **\{m, c, b, j\}** |
| $B_7$ = **\{c, b, j\}** | $B_8$ = **\{b, c\}** |

위애서 예시로 든 baskets에서 다음과 같은 연관 규칙을 찾았다고 해보자.

> **\{m, b\} &rarr; c**
>
> $support(\{m, b\} \cup c)$ = **2** (m, b, c 동시 등장 횟수)
> $support(\{m, b\})$ = **4** (m, b 동시 등장 횟수)
> $conf(\{m, b\} \rightarrow c)$ = 2/4 = **0.5**
> $Interest(\{m, b\} \rightarrow c)$ = | 0.5 - 5/8 | = **1/8**

즉, 이 경우에는 Interest가 낮기 때문에 그다지 의미 없는 규칙이라는 뜻이다.

### Mining Association Rules

1. 모든 빈발 항목 집합 I를 찾는다.
  (이건 [**`이전 포스트`**](https://wjlee611.github.io/blog/univ_mmds/mid_03)에서 찾는 법을 다룸)

2. 규칙 생성

이제 규칙을 생성하는 방식을 알아보자.

우선 생성된 빈발 항목 집합 I의 부분집합을 이용해서 생성 가능한 모든 연관 규칙을 만든다.
예로 들어 **I = \{a, b, c, d\}** 라면, **\{a, b, d\} &rarr; c, \{a, b\} &rarr; \{c, d\}** 등등과 같이 모든 조합에 대해 만들어 주는 것이다.

그 다음은 생성된 모든 규칙에 대해 Confidence, Interest를 분석해서 의미있는 규칙만 남도록 걸러내면 된다.
여기서 특정 규칙을 검사하고 나면 나머지 특정 규칙들은 검사할 필요가 없어지는 최적화가 가능한데, 그 이유를 알아보자.

예로 들어 **\{a, b, c\} &rarr; d** 의 confidence가 threshold 이하라면 **\{a, b, c\}** 의 부분집합이 조건부가 되는 규칙들(**\{a, b\} &rarr; \{c, d\}**, **\{b\} &rarr; \{a, c, d\}**, ...)은 검사를 진행할 필요가 없어진다.
왜냐하면 아래의 식을 잘 살펴보자.

$$
conf(I \rightarrow j) = \frac{support(I \cup j)}{support(I)}
$$

여기서 동일한 빈발 항목 집합에 대해 생성된 규칙이면 분자는 동일하다는 것은 자명하다.
즉, 분모만 변화하게 되는데, 원소의 개수가 줄어들 수록 분모의 값은 필연적으로 같거나 커질 수 밖에 없다.
그렇기에, confidence는 반드시 같거나 작아질 수 밖에 없는 것이다. (하물며 threshold와 비교하면? 분명 더 작을거다.)

| Baskets | m(ilk), c(oke), p(epsi), b(read), j(am) |
| --- | --- |
| $B_1$ = **\{m, c, b\}** | $B_2$ = **\{m, p, j\}** |
| $B_3$ = **\{m, c, b, n\}** | $B_4$ = **\{c, j\}** |
| $B_5$ = **\{m, p, b\}** | $B_6$ = **\{m, c, b, j\}** |
| $B_7$ = **\{c, b, j\}** | $B_8$ = **\{b, c\}** |

마지막으로 실제로 연관 규칙을 찾아보며 마무리해보자.
threshold = 3, confidence = 0.75 로 제한한다고 가정하자.

> Frequent itemsets: 
> **\{b, m\} \{b, c\} \{c, m\} \{c, j\} \{m, c, b\}**

| Generate rules | | | |
| --- | --- | --- | --- |
| ~~b &rarr; m [c=0.67]~~ | b &rarr; c [c=0.83] | ... | ~~b,c &rarr; m [c=0.6]~~ |
| m &rarr; b [c=0.8] | c &rarr; b [c=0.83] | | ~~b &rarr; c,m (검사 필요 없음)~~ |
| | | | ~~c &rarr; b,m (검사 필요 없음)~~ |
| | | | c,m &rarr; b [c=1] |
| | | | b,m &rarr; c [c=0.75] |
| | | | ~~m &rarr; b,c [c=0.6]~~ |
이후에 interest도 진행

### Compacting the output

생성되는 연관 규칙이 너무 많기에 이를 압축하는 방식도 있다.

1. Maximal frequent itemsets
  threshold 기준으로 압축한다.
2. Closed itemsets
  support 기준으로 압축한다.

다음 표를 보면서 이해해보자.
(Yes인 경우에만 연관 규칙을 출력한다는 뜻이다)

| Itemset | Support | Maximal | Closed |
| --- | --- | --- | --- |
| A | 4 | No | No |
| B | 5 | No | Yes |
| C | 3 | No | No |
| AB | 4 | Yes | Yes |
| AC | 2 | No | No |
| BC | 3 | Yes | Yes |
| ABC | 2 | No | Yes |
**Threshold = 3**

`Maximal 기준`
- C를 보면 support가 threshold보다 크지만 출력하지 않는다.
그 이유는 C의 superset BC가 `frequent 해서` 이미 출력하기 때문에 중복해서 출력하지 않는 것이다.
- 반대로 AB를 보면 support가 threshold보다 커서 출력한다.
그 이유는 AB의 superset ABC가 `frequent 하지 않기 때문`에 출력해야하기 때문이다.


`Closed 기준`
- C를 보면 support가 threshold보다 크지만 출력하지 않는다.
그 이유는 C의 superset BC의 `support와 같기 때문`에 출력하지 않는 것이다.
- 반대로 AB를 보면 support가 threshold보다 커서 출력한다.
그 이유는 AB의 superset ABC의 `support가 보다 작기 때문`에 출력하는 것이다.

빅데이터에서 연관 규칙을 찾아내는 방법에 대해 알아봅니다.

Association Rules

## Naive Algorithm

우선 나이브한 방법으로 빈발 항목 집합을 찾는 방법부터 알아보자.
처음에는 frequent pair를 찾는 것을 목표로 하고, 이후에 원소의 개수가 더 많은 집합을 찾는 방식으로 확장하자.

간단하게 요약하면 아래의 두 단계에 걸쳐 모든 pair를 생성한다.

1. 가능한 모든 조합의 쌍 생성
 n개의 아이템이 들어있는 Basket에서는 `n(n-1)/2` 개의 조합 쌍이 생성된다.
2. 해당 조합 쌍이 동시에 등장하는 경우 1씩 카운트하며 개수를 센다.

이 방식은 구현이 제일 간단하지만 치명적인 문제가 있다.
개수를 `4bytes`의 int형으로 저장한다고 가정하면 n개의 아이템이 존재하는 Basket에 대해 `2n(n-1)bytes`의 메모리 공간이 할당되어야 하는데, 이런 크기의 메모리 공간을 할당할 수 없을 뿐더러, 존재하지도 않은 페어의 메모리 공간을 할당해야만 하는 문제점이 있다.

### Triples

이런 한계를 극복하기 위해 원소를 triples로 관리하는 기법도 있다.
`[i, j, c]` 로 관리하는 기법인데, **\"\{i, j\} 페어가 c번 등장함\"** 이라는 의미로 관리하는 것이다.
이렇게 하면 하나의 페어당 12bytes가 들어가긴 하지만, 존재하지도 않은 페어에 대한 메모리 공간 할당은 방지할 수 있다.

하지만 메모리 주소 관리를 위해 별도의 `해시 테이블`을 할당해야 하기에 그다지 메리트가 크지는 않다.
Triples 방식이 더 효율적으로 작동하기 위해서는 가능한 모든 페어 조합 수의 1/3 수준으로 실제로 등장하는 페어수가 존재해야 한다.

---

## A-Priori Algorithm

페어가 메인 메모리에 올라갈 정도로 적다면 나이브한 방식을 사용하는것이 좋다.
Basket을 한 번만 읽어도 되는, 1pass만에 빈발 항목 집합을 찾을 수 있으니 속도가 빠르기 때문이다.

<tip>
 `pass`
 Basket(파일)을 처음부터 끝까지 읽는 횟수로, Disk I/O의 cost가 큰 만큼 pass 횟수에 따라 알고리즘의 성능을 평가하는 요소로 작동한다.
</tip>

하지만, 그렇지 않은 대다수의 경우에는 다른 방식을 고안해야 한다.
A-Priori 알고리즘의 경우에는 2pass로 pair를 찾을 수 있지만, 그 대신 메모리 효율성이 극대화되어 매우 큰 파일도 메모리에 적재할 수 있다.
하지만 이게 어떻게 가능한 것일까?

기본적인 아이디어는 이렇다.
이 파일에는 아이템이 **a, b, c** 이렇게 존재한다고 해보자.
만약 **\{a, b\}** 가 10번 등장했다면, 진 부분집합 **\{a\}, \{b\}** 역시 10변 이상 등장했을 것이다.
반대로 말하면 **\{a\}, \{b\}** 가 10번도 안나왔다면, **\{a, b\}** 역시 10번도 안나올 것이다.

따라서 빈발 항목 집합을 세기 전에 우선 threshold보다 큰 경우에만 빈번하다고 기준을 정의하고 시작한다.

### Pass 1

pass 1에서는 우선 파일을 읽어보며 개별적인 아이템 개수부터 세어본다.
이 때, 아이템 개수가 threshold보다 큰 경우에만 다음 pass에서 고려하게 된다.

![231019-205437](/posts/mid_03/231019-205437.png)

참고로 pass 2에서 빈번하게 등장한 아이템에 접근하기 위해 빈번하게 등장한 아이템들의 주소를 저장하기 위해 메모리 공간을 약간 할당한다.

### Pass 2

pass 2에서는 pass 1에서 통과한 아이템들을 이용해서 페어를 생성한다.
그리고 나이브한 방법과 마찬가지로 파일을 읽으면서 등장 횟수를 카운트한다.

이 방식이 훨씬 효율적인게, 만약 pass 1에서 읽어야 할 아이템의 개수가 1/10 으로 줄었다면,
pass 2에서 생성되는 pair의 개수는 1/100 수준으로 줄어든다.
따라서 메모리 효율성이 거의 100배 증가하는 것이다.

### Frequent Triples

pair에서 확장되어 원소의 개수가 3개, 4개인 경우의 처리 방식도 알아보자.
근데 사실 별 거 없다. 그냥 앞에서 봤던 방법의 반복이다.

빈번하게 등장한 페어를 이루는 아이템들로 triple을 만든다.
이후 각 triple의 진 부분집합이 빈번하게 등장한 pair인 경우에만 파일을 읽어보며 세어보면 된다.

예시들 들어 이해해보자.

> $C_1$ = \{\{b\} \{c\} \{j\} \{m\} \{n\} \{p\}\}
> threshold보다 많이 등장한 원소는 아래 4개라고 해보자.
> $L_1$ = \{b, c, j, m\}
> $L_1$을 이용해서 다름 pass 진행
> 
> $C_2$ = \{\{b, c\} \{b, j\} \{b, m\} \{c, j\} \{c, m\} \{j, m\}\}
> threshold보다 많이 등장한 원소는 아래 4개라고 해보자.
> $L_2$ = \{\{b, c\} \{b, m\} \{c, j\} \{c, m\}\}
> $L_2$을 이용해서 다름 pass 진행
>
> $C_3$ = \{\{b, c, m\} \{b, c, j\} \{b, m, j\} \{c, m, j\}\}
> 이 때 \{b, c, j\} \{b, m, j\} \{c, m, j\}의 부분 집합은 $L_2$에 포함되지 않으니 세어볼 필요 없음 (반드시 threshold보다 적게 등장할 것)

즉, A-Priori 알고리즘은 k-pass 단계에서 k-tuple의 집합을 생성하게 되는데,
일반적으로 k=2일 때, 메모리 사용량이 가장 많다.

---

## PCY Algorithm

Park-Chen-Yu 알고리즘으로 A-Priori 알고리즘의 pass 1에서 메모리의 빈 공간을 활용하여 탐색 효율을 높인 알고리즘이다.
그 이후의 과정은 A-Priori와 같으니, pass 1에서의 메모리 관리 방법에 대해서만 알아보자.

![231019-211632](/posts/mid_03/231019-211632.png)

### Bucket's Hash Table
pass 1에서 개별적인 아이템 등장 횟수를 카운트 할 때, 동시에 아이템으로 만들 수 있는 pair의 개수도 동시에 카운트 하는 것이다.
이 때 페어를 해싱하여 버킷으로 만들고, 그 버킷을 Hash table for pairs에 최대한 가득 채운다.

예로 들어 a, b, c의 개수를 세어보면서 \{a, b\} \{b, c\} \{a, c\}를 해싱한 주소에 등장할 때 마다 1씩 카운트 하는 것이다.
만약 \{a, b\} \{a, c\} 의 해시 결과가 같은데, 해당 pair을 해시한 곳의 값이 threshold보다 작다면 pass 2에서 \{a, b\} \{a, c\} 를 셀 필요가 없다는 뜻이된다.

그럼에도 불구하고 pass 2에서는 파일을 한 번 더 탐색을 해야만 하는데, 버킷만으로 pair가 threshold보다 크다고 단정지을 수 없는 이유는 해시의 특성 때문이다.
다른 입력에 대해 같은 출력이 나올 수 있는 해시는 여러 pair가 하나의 버킷에 카운트 될 수 있음을 시사한다.
즉, 버킷이 threshold보다 작다면 해싱후 그 버킷을 가리키는 pair는 세어볼 필요가 없지만,
threshold보다 큰 경우에는 threshold보다 작은 값이 여러개 모여 threshold보다 커졌을 가능성이 있기 때문에 다시 파일을 읽어보며 확인을 해봐야 하는 것이다.

### Bit-vector (bitmap)

아무튼, pass 1에서 pair의 해싱을 통한 버킷이 저장된 해시 테이블을 만들어 추후 파일 탐색시 검사해야 할 pair의 수를 줄이게 되는데,
해시 테이블을 암축하지 않으면 pass 2로 넘어갈 수 없다. (메모리에 꽉 차게 할당했기 때문)
어떻게 압축해야 필요한 정보를 유지할 수 있을까?

우리가 필요한 정보는 n번째 버킷이 threshold보다 많이 등장했는지(1) 아닌지(0) 이다.
따라서 해시 테이블에 n번째 버킷이 threshold보다 크다면 1, 아니면 0으로 압축할 수 있다.
4bytes(32bits)에서 1bit로 압축되는 셈이다.

그리고 이제 pass 2에서 \{b, c\}를 파일에서 몇 번 등장하는지 세어보기 전에 우선 해싱을 하여 bitmap에 해당 해시의 위치가 1이면 실제로 세어보고 0이면 셀 필요 없이 threshold보다 작다는 뜻이 된다.

---

## Random Sampling

지금까지 알아본 빈번 항목 집합을 찾는 방식은 k-tuple의 개수를 세어보기 위해서는 k-pass를 거쳐야만 했다.
이번부터 알아볼 알고리즘은 단 2-pass만에 세어볼 수 있는 방식을 알아볼 것이다.

랜덤 샘플링 기법은 파일을 메모리에 올릴 수 있을 만큼만 적당히 샘플링 해와서 모든 카운트 과정을 메모리 내부에서 해결하는 것이다.
하지만, 샘플링 비율만큼 실제 데이터 양도 줄어들기 때문에 threshold도 샘플링 비율만큼 줄여서 측정한다.

하지만 이 경우에는 False Positive, False Negative 문제가 발생할 수 있다.

<tip>
 `False Positive`
 실제로는 빈번하지 않은데 샘플링된 데이터에서는 빈번하다고 나온 경우
 
 `False Negative`
 실제로는 빈번한데 샘플링된 데이터에서는 빈번하지 않다고 나온 경우
</tip>

False Positive의 경우에는 pass 2에서 빈번 집합의 경우 실제로 빈번하게 등장하는지 검사해 봄으로써 해결할 수 있다.
하지만 False Negative의 경우에는 찾아낼 방법이 없다.

threshold를 더 작게 설정하는 방식으로 False Negative가 나올 확률을 줄일수는 있겠지만, 해결책은 아니다.

---

## SON Algorithm

기본적인 방식은 랜덤 샘플링과 동일하다.
차이점은 SON Algorithm음 모든 파일을 다 읽는다는 것이다.
즉, 한 번 읽을 때 샘플링한 작은 청크를 읽지만, 이 과정을 여러번 반복해서 전체 파일을 읽어온다는 차이점이다.

이 방식은 False Negative도 없다고 확신할 수 있다.
왜냐하면 실제로 빈번한 집합이라면 읽어오는 모든 청크에 대해 최소 1개의 청크에서는 빈번하게 등장할 것이기 때문이다.

하지만 모든 청크를 결국 메모리에 1번은 올려야 하기 때문에 시간이 오래 걸린다는 단점이 있다.

---

## Toivonen's Algorithm

시작은 랜덤 샘플링과 같다.
하지만 랜덤 샘플링에서 샘플을 파일의 1/100 수준으로 샘플링 한다면 threshold도 1/100 수준으로 설정할텐데 이 경우에는 좀 넉넉하게 1/125 정도로 설정한다는 차이가 있다.

추가로 pass 1에서 Negative Border 라는 개념을 도입하여 False Negative를 방지한다.
이 외에는 랜덤 샘플링 방식과 동일하다.

### Negative Border

Negative Border에 포함되는 집합은 본인은 빈번하지 않지만, 본인의 진 부분집합은 빈번하게 등장한 경우 포함된다.
예시를 들어 알아보자.

> 모든 집합이 **\{\} \{a\} \{b\} \{c\} \{a b\} \{b c\} \{a c\} \{a b c\}** 만 존재한다고 가정해보자.
>
> `Case 1` **\{a\} \{b\}** 만 빈번하게 등장함 &rarr; **\{a b\} \{c\}** 를 Negative Border로 추가.
> **\{a b\}** 의 경우에는 본인의 진 부분집합이 빈번하게 등장했으니 본인도 빈번하게 등장했을 가능성이 있다.
> 따라서 추가 검사를 진행해봐야 하는 것이다.
> **\{c\}** 의 경우에는 진 부분집합이랄게 없기 때문에 추가 검사를 진행해 봐야 하는 것이다.
>
> `Case 2` **\{a\} \{b\} \{c\}** 만 빈번하게 등장함 &rarr; **\{a b\} \{b c\} \{a c\}** 를 Negative Border로 추가.
> 빈번하게 등장한 집합의 다음 스탭만 의심해야지, 나아가서 **\{a b c\}** 까지는 검사하지 않는다.
>
> `Case 3` **\{\}** (아무것도 빈번하지 않음) &rarr; **\{a\} \{b\} \{c\}** 를 Negative Border로 추가.
> 샘플링을 너무 못했을 가능성이 높기에 일단 원소 1개짜리는 추가 검사를 해봐야 한다.

이후 pass 2에서 빈번 항목 집합과 Negative Border에 대해 검사를 진행한다.
False Positive의 경우에는 랜덤 샘플링과 마찬가지로 여기서 걸린다.

False Negative의 경우에는 Negative Border에 포함된 집합을 검사하면서 나오게 될텐데,
만약 Negative Border에 있는 집합이 실제로는 빈번하게 등장했다면 False Negative가 존재한다는 뜻이 된다.
이런 경우에는 다른 샘플로 pass 1부터 다시 시도하게 된다.
따라서 정확히는 2 pass안에 끝나지 않을 수는 있다.

빈발 항목 집합을 구하는 방법을 알아봅니다.

Frequent Itemset

## MapReduce 문제점

기존 MapReduce 모델의 문제점은 데이터 복제, Disk I/O 등의 오버헤드가 크다는 점이었다.

하지만, ranks를 2개(map, reduce)로 나누어 관리하여 한 반향으로 데이터를 흐르게 만들어 
시스템이 다운될 경우 재시작의 효율성이 올라가는 점도 고려하여 구현되었다.
(단방향으로 흐르기에 처리 실패가 발생한 지점부터 다시 처리하면 됌)

그러나, rank가 2개라 모든 문제를 map-reduce 패턴으로 묘사하기가 쉽지 않다는 점도 있었다.

## Spark

스파크는 오늘날 가장 많이 쓰이는 Data-Flow system으로 MapReduce에 비해 여러 부분에서 개선이 이루어졌다.

1. rank를 2개로 제한하지 않음.
 map, reduce 외의 tasks, ranks와 같은 여러 단계를 허용함.
2. Map, Reduce 외의 별도의 유용한 함수 제공.
3. 바로 디스크에 중간 결과를 저장하지 않고, 메모리에 캐싱하기도 함.
 적당한 크기의 중간 결과는 메모리에 캐싱하기에 속도로 보다 빠르다
4. MapReduce와 마찬가지로 단방향으로 데이터가 흐르는 DAGs 형식을 따른다.
 (Directed Acycle Graphs)
5. 여러 언어와 api를 제공하고, 오픈소스이며 호환성도 좋다.

<tip>
 `vs. Hadoop MapReduce`
 Spark이 더 빠른대신 메모리 사용량도 더 많다.
 Spark에서 제공하는 api가 더 많아 사용하기에 더 편하다.
 둘 다 map-reduce 부분에서는 성능차이는 없다.
</tip>

### RDD

Resilient Distributed Dataset의 약어로 Spark에서는 큰 데이터를 RDD 라는 청크로 쪼개어 key-value 페어로 저장한다.
즉, RDD가 여러개의 클러스터에 분산 저장되는데, 가장 큰 특징은 RDD는 **읽기 전용**이라는 점이다.
그렇기에 **파일로부터** RDD를 얻어오기도 하며, **RDD로부터** 새로운 RDD를 만드는 식으로 작업된다.
또한, RDD는 일반적으로 **메모리에 캐싱**되며, 필요에 따라 디스크에 저장하기도 한다.

<tip>
 `DataFrame`
 RDD와는 다르게 데이터들이 테이블 형태로 저장되먀 column별로 이름도 있다.
 
 `DataSet`
 DF의 상위호환으로 타입 세이프, 객체지향 프로그래밍 인터페이스를 지원하며, 컴파일 타임에 에러도 잡아낼 수 있다.
</tip>

### Transformations

RDD에서 새로운 RDD로의 변환을 Transformations라고 하는데, `map`, filter, join, union, intersection, distinct와 같은 변환이 있다.

중요한 점은 이러한 변환은 `Lazy evaluation` 하게 동작한다는 점인데, 이게 무슨 말이냐면
뭔가를 지시를 해도 실제로 수행을 하지 않는다는 뜻이다.
지시를 하면 지시 사항을 기록하다가 사용자가 실제로 값을 요청시 기록된 요청을 최적화 알고리즘을 적용하여 한 번에 실행하기 때문에 효율적으로 동작하게 된다.

### Actions

Lazy evaluation 중 실제로 동작을 수행하게 하는 명령이다.
count, collect, `reduce`, save 와 같은 명령이 있다.

### Task Scheduler (General DAGs)

![231019-153939](/posts/mid_02/231019-153939.png)

Spark 스케쥴러는 스마트하게 동작하는데 그 특징은 다음과 같다.

1. 파이프라인 함수를 제공한다.
 Stage 1, Stage 2와 같이 여러 단계를 추상화하여 하나의 단계로 취급해 성능을 최적화 한다.
2. 감당 가능한 크기의 데이터는 캐싱한다.
 데이터를 캐싱하여 재사용성을 높이고, 속도도 빠르게 한다.
3. key값 분포상태를 파악하여 불필요한 shuffle을 피한다.
 일례로 A &rarr; B로 넘어가며 키 값이 정렬되었으니, B &rarr; F로 넘어갈때는 불필요한 셔플을 하지 않음.

---

## methods (real-code)

<notice>
 Finding Similar Item까지 본 뒤에 코드를 보는 것이 더 좋습니다.
</notice>

### (Spark) DataFrame

- `printSchema()`
 해당 데이터프레임의 스키마를 보여줍니다.

- `take(N)`
 N개의 행을 보여줍니다.

- `show(n=N, truncate=boolean)`
 N개의 행을 표 형태로 정리하여 보여줍니다.
 truncate=False시 ...으로 요약되지 않은 전체 문자열을 출력합니다.

- `select(columnName[])`
 columnName에 해당하는 column들만 남긴 spark dataframe 객체를 반환합니다.

- `selectExpr(sqlSelect[])`
 sql select문에서 사용할 수 있는 문법을 이용하여 해당 column을 가져온 뒤 dataframe 객체로 반환합니다.

- `sort(columnName, ascending=boolean)`
 columnName을 기준으로 오름차순 정렬합니다.
 ascending=False시 내림차순으로 정렬합니다.

- `join(dataframe, this.column == dataframe.column)`
 본인(this) dataframe과 인자로 넣은(dataframe) dataframe의 공통 column을 기준으로 natural join을 수행 후 dataframe 객체를 반환합니다.
 단, 일반 sql과 다르게 공통 column이 하나만 표시되는게 아닌 중복되서 표시됩니다.

- `toPandas()`
 데이터가 pandas로 옮길 수 있을 만큼 작다면, spark dataframe에서 pandas dataframe으로 변환합니다.

- `groupBy(columnName[])`
 배열에 들어있는 모든 columnName을 기준으로 그루핑한 후 GroupedData 객체를 반환합니다.

- `rdd`
 spark dataframe에서 RDD 인스턴스를 생성합니다.

### (spark) GroupedData

- `count()`
 각 그룹의 행의 개수를 카운트하여 count column을 만들고 dataframe 객체를 반환합니다.

- `agg(column)`
 column에 대해 집계함수를 수행합니다.
 아래와 같이 응용하여 사용하면 item을 직렬화할 수 있습니다.
 alias를 이용해 column의 이름을 변경할 수 있습니다.

 ```python:.py
 df = orders_joined.groupBy('order_id').agg(collect_set('product_name').alias('items'))
 df.show()
 ```

 | order_id | items |
 |---|---|
 | 1 | [Bag of Organic B... ] |
 | 96 | [Roasted Turkey, ... ] |
 | 112 | [Umcka Elderberry... ] |

### RDD (PipelinedRDD)

- `collect()`
 RDD를 출력합니다.

- `map(function(row))`
 RDD에 대해 function를 적용합니다.
 파라미터로 RDD의 row가 전달됩니다.

 ```python:.py
 all_locations = jun_29_operations.rdd.map(lambda row: (row.TakeoffLocation, 1))
 all_locations.take(3) 
 ```

 적용 후 PipelinedRDD 객체를 반환합니다.

 > [('TAKHLI', 1), ('DANANG', 1), ('CONSTELLATION', 1)]

- `flatMap(function)`
 map과 동일한 기능을 수행합니다.
 단, 결과가 1차원 배열만을 반환합니다.

 ```python:.py
 RDDs1 = RDDs1.flatMap(lambda line: line.split(' '))
 ```

- `reduceByKey(function(number, number))`
 PipelinedRDD에 대해 function을 적용합니다.
 파라미터로 2개의 key-value pair에 대해 value가 전달됩니다.

 ```python:.py
 locations_counts_rdd = all_locations.reduceByKey(lambda a, b: a+b).sortBy(lambda r: -r[1])
 locations_counts_rdd.take(3)
 ```

 적용 후 PipelinedRDD 객체를 반환합니다.

 > [('CONSTELLATION', 87), ('TAKHLI', 56), ('KORAT', 55)]

- `sortByKey(ascending=boolean)`
 RDD key-value pair에 대해 key값을 기준으로 정렬합니다.

- `filter(function)`
 function이 true를 반환하는 값만 통과시켜 RDD객체를 반환합니다.

### spark instance

- `sql(queryString)`
 sql문법을 queryString를 실행한 후 spark dataframe 객체를 반환합니다.

- `createDataFrame(RDD)`
 RDD를 spark dataframe 인스턴스로 변환합니다.
 단, 인스턴스의 Row에 따라 Column의 이름이 결정됩니다.

 예로 들어 reduceByKey 이후 바로 createDataFrame 생성시 Row의 이름이 작성되지 않아 Column명이 _1, _2와 같은 식으로 초기화됩니다.

 따라서 아래의 코드로 이름을 지정하는 것이 시각화에 도움이 됩니다.

 ```python:.py
 locations_counts_with_schema = locations_counts_rdd.map(lambda r: Row(TakeoffLocation=r[0], MissionsCount=r[1]))
 locations_counts = spark.createDataFrame(locations_counts_with_schema)
 locations_counts.show()
 ```

- `sparkContext.textFile(path)`
 path에 해당하는 파일을 읽은 뒤 RDD 인스턴스를 반환합니다.

### FPGrowth

- `FPGrowth(itemsCol=columnName, minSupport=number, minConfidence=number)`
 dataframe의 columnName에 대해 연관규칙을 생성하는 FPGrowth 인스턴스를 생성합니다.
 이 때 minSupport, minConfidence를 설정해야 합니다.

- `fit(dataframe)`
 생성된 FPGrowth 인스턴스에 대해 dataframe을 적용하여 FPGrowthModel을 만듭니다.

- `freqItemsets, associationRules`
 생성된 FPGrowthModel에 대해 `빈발 항목 집합`과 `연관 규칙`을 생성합니다.

 ```python:.py
 # grouping with order_id
 df = orders_joined.groupBy('order_id').agg(collect_set('product_name').alias('items'))

 # change to spark dataframe
 df = spark.createDataFrame(df.toPandas(), ['id', 'items'])

 # analysis using FP-Growth
 from pyspark.ml.fpm import FPGrowth
 fpGrowth = FPGrowth(itemsCol='items', minSupport=0.01, minConfidence=0.5)
 model = fpGrowth.fit(df)

 num_freqItemsets1 = model.freqItemsets.count()
 num_associationRules1 = model.associationRules.count()
 ```

MapReduce 모델의 확장판, Spark에 대해 알아봅니다.

Spark 개념

## 분산 파일관리 시스템

방대한 데이터 보관, 또는 백업을 위해 데이터를 분산 저장하는 경우 여러대의 컴퓨터를 연결하여 하나처럼 동작하도록 구성해야 한다.

하지만, 실시간으로 데이터를 처리해야 하는 부분에 대해서는 데이터를 복사하여 네트워크 전송을 통해 처리하는 방식은 네트워크 속도가 상대적으로 매우 느리기 때문에 문제가 있다.

이런 경우에는 데이터를 옮기는 것이 아닌, 필요한 데이터를 보관하는 컴퓨터에게 `연산 작업을 맡기고`, `동기화는 주기적`으로 하는 방식을 사용하는 것이 좋다.

이렇게 데이터를 분산하여 저장하는 시스템을 분산 파일관리 시스템이라 불리고, `Spark`, `MapReduce`와 같은 시스템이 이런 방식을 사용한다.
하지만, 이런 파일관리 시스템은 1개의 머신만을 사용하는 시스템에 비해 속도가 느리기 때문에 아래의 조건을 만족하는 경우에만 사용하는 것이 바람직하다.

1. 데이터 양이 매우 많은 경우
2. 데이터의 수정은 왠만하면 일어나지 않는 경우
3. 읽고 이어쓰기가 빈번하게 일어나는 경우

### Chunk servers

16~64MB 정도의 파일을 하나의 Chunk로 묶어 관리하는데, 이런 청크를 2, 3배 중복으로 다른 물리적 공간에 저장하는 식으로 분산 관리를 하게 되는데,
이런 다른 물리적 공간을 Chunk server 라고 부른다.

![231019-143146](/posts/mid_01/231019-143146.png)

따라서 여러 청크서버에 동일한 청크가 분산 저장되어 있기 때문에 하나의 청크서버가 다운되더라도 데이터는 온전히 남는다.

또한, 위에서 언급했 듯, 데이터를 움직이는 것이 아닌 연산을 일임한다고 했는데,
서버의 과부화 방지를 위해 각 청크서버가 특정 청크에 필요한 연산을 전담하여 수행하고 결과를 반환한다.

### Master node

파일이 저장된 위치인 메타데이터를 저장한 서버이다.
따라서 파일 엑세스 요청이 들어오면, 일단 모든 요청은 마스터 노드로 향하여 요청한 파일이 어느 청크서버에 있는지 알아낸다.
이후 그 요청에 대한 응답은 청크서버로 직접 엑세스되어 청크서버에서 요청이 처리되게 된다.

여기서 드는 의문점은 **왜 마스터 노드가 직접 데이터를 전달하지 않는가**이다.
그 이유는 마스터 노드에 엑세스가 제일 많은데 데이터까지 전달하게 되면 과부화가 걸리기 때문에 그렇다.

---

## MapReduce

초창기 분산 컴퓨팅 프로그래밍 모델이다.
이 기술의 구현체로 Hadoop, Spark, Flink 등이 있는데, 이 모델의 동작 과정을 살펴보자.

### overview

![231019-144045](/posts/mid_01/231019-144045.png)

Map, Group by Key(보통 자동으로 일어남), Reduce의 3단계로 이루어지는데, 각 단계에서 어떻게 일이 처리되는지 알아보자.

참고로 Map, Reduce의 과정은 하나의 머신에서 일어나는 것이 아닌, 다중 머신에서 병렬적으로 일어난다는 점을 기억하자.

### Map

우선 개발자가 Map 함수를 작성한다.
Map 함수는 읽은 데이터를 처리하기 위해 `key-value pair`로 변환하는 작업을 수행하게 된다.

하지만 MapReduce에서 사용 가능한 규격으로 데이터를 처리해야 하는데 이 과정이 좀 까다로울 수 있다.

추가로 이 이후에 생성된 key값을 이용해서 해싱같은 방식을 이용해 생성된 페어를 Reduce를 수행할 컴퓨터로 보내게 된다.

### Group by Key

Map으로 얻어진 pair을 key값을 중심으로 정렬하고, 중복된 key들에 대해 value 들을 배열로 묶어주는 일을 처리한다.
대부분의 시스템에서 이 과정은 자동으로 일어나기 때문에 개발자가 개입할 부분이 상대적으로 적다.

하지만 성능적으로 이 단계에서 `병목현상`이 발생할 수 있다.
Map, Reduce는 파일이나 청크를 한 번만 탐색하면 끝나지만($O(n)$),
Group by Key는 정렬 및 그루핑을 해야하기 때문에 상대적으로 느리기 때문이다($O(n log(n))$).

### Reduce

개발자가 개발한 Reduce 함수를 이용해 배열로 되어있는 values들을 하나로 합쳐준다.
이 과정이 종료되면 유니크한 key-value pairs가 생성될 것이다.

### Dealing with Failures

`Map worker`가 다운된 경우에는 일이 진행 중이든 완료되었든 간에 무조건 다른 worker에게 일을 처음부터 재시작하게 한다.
왜냐하면 일이 완료된 경우 그 결과를 시간 비용의 문제 때문에 `로컬 디스크`에 데이터를 저장하기 때문이다.

반면에 `Reduce worker`가 다운된 경우에는 일이 진행 중인 경우에만 다른 worker에게 일을 처음부터 재시작하도록 한다.
Reduce일이 완료된 경우, 그 결과는 중요한 데이터이니 `분산 저장`하기 때문에 완료된 경우에 다운되어도 재시작할 필요가 없는 것이다.

### Cost Measure

MapReduce 내부적으로 사용되는 알고리즘의 비용을 측정해보자.

1. Communication cost
 모든 프로세스의 **I/O bytes**
> (아래 항목을 모두 더하면 됌)
> - 입력 파일 사이즈
> - 2 $\times$ Map process &rarr; Reduce process 로 이동한 파일 사이즈 (2를 곱한 이유는 Map, Reduce 2개이기 때문)
> - Reduce process에서 나온 출력 사이즈의 합
2. Elapsed communication cost
 Communication cost 중 가장 큰(peak) 비용 (정확히는 파일 사이즈가 가장 큰 입력 파일 기준)
 &rarr; 이 비용이 작을수록 병렬(분산)화가 잘 되었다는 뜻이다.
3. (Elapsed) Computation cost
 1, 2와 동일, 단, 기준이 byte 단위가 아닌 **I/O 시간** 단위 기준임.

<tip>
 대부분의 클라우드 서비스는 Communication cost 기준으로 비용이 청구됌.
 (Elapsed는 기준은 아님)
</tip>

---

## Problems Suited for MapReduce

Spark과 같은 라이브러리 말고 MapReduce만 사용하기에도 충분한 문제들을 알아보자.
보통 데이터 `순차탐색` 문제나, `비 실시간`으로 처리되어도 상관없는 여유로운 작업에 적합하다.

### Host size

url로 부터 host를 추출하고, 해당 호스트에서 제공하는 많고 거대한 데이터의 총 크기(용량)을 알고싶을 때 사용할 수 있다.

> (host1, size1)
> (host2, size2)
> ...

### Language Model

언어 모델 개발시에도 이용할 수 있다.

> 5개의 단어 뭉치가 문서에서 얼마나 등장하는지
> (5-word seq, count)

이런 경우도 map, reduce로 간단하게 만들 수 있다.

### join

join 연산도 MapReduce로 할 수 있다.

![231019-155529](/posts/mid_01/231019-155529.png)

$R(A,B) \Join S(B,C)$를 `natural join`한다로 해보자.

> `Map`
> 1. join에 사용될 column을 key로 사용하는 key-value 페어로 만든다.
>
> ($b_1$, ($a_1$, R))
> ($b_1$, ($a_2$, R))
> ($b_2$, ($a_3$, R))
> ($b_3$, ($a_4$, R))
> ($b_2$, ($c_1$, S))
> ($b_2$, ($c_2$, S))
> ($b_3$, ($c_3$, S))
>
> 2. 키값을 해싱한 후 Reduce 프로세스로 보낸다.

> `Reduce`
> 1. Reduce를 진행한다.
>
> ($h(b_1)$, [($a_1$, R), ($a_2$, R)])
> ($h(b_2)$, [($a_3$, R), ($c_1$, S), ($c_2$, S)])
> ($h(b_3)$, [($a_4$, R), ($c_3$, S)])
>
> 2. values에 R-S로 되어있는 value들만 묶어서 (a,b,c)로 출력한다.
> (R-R, S-S를 제외하기 위해서 value pair에 R, S를 포함시킨 것이다)
>
> ($a_3$, $b_2$, $c_1$)
> ($a_3$, $b_2$, $c_2$)
> ($a_4$, $b_3$, $c_3$)

### Not Suited

적합하지 않은 문제상황은 뭐가 있을까?
graph 탐색이나, ML에서의 `비 순차탐색` 하는 경우에는 적합치 않다.

분산 파일관리 시스템에 관련한 기초 지식을 배웁니다.

분산 파일관리 시스템

3학년 2학기 빅데이터 처리 및 응용 수업 아카이브

// 대학 - 빅데이터 처리 및 응용