Tabular Data(정형 데이터)에서 Noise를 줄 수 있는 방법 중 하나인 Swap Noise에 대해 알아보도록 하겠습니다.

Challenges

데이터를 다루다 보면, Denoising AutoEncoder와 같이 Noise(노이즈)를 필요로 하는 경우가 종종 있습니다. 비정형 데이터(Ex. 이미지, 텍스트, 음성)에서는 범용적으로 사용되고 잘 짜여진 라이브러리 툴로 노이즈를 줄 수 있는 방법이 많습니다. 반면, 정형 데이터에 노이즈를 만들려고 하면 선뜻 와닿는 방법이 생각나지 않습니다. 가장 큰 이유는 "변수별로 갖는 범위 및 분포가 다르기 때문"이라고 생각합니다. 예를 들면, Gaussian Noise(정규분포의 랜덤값을 각 변수별로 주는 방법)을 주기 위해 각 변수별 적당한 분산값을 정하기도 힘들며, 데이터 중 횟수와 같이 정수값만 갖는 변수가 있을 때 Gaussian Noise로 생성된 소숫점의 노이즈를 추가하는 것은 원래 데이터를 정수가 아닌 값으로 변형하기 때문에 데이터가 왜곡될 수 있습니다.

Denoising AutoEncoder(DAE) 원본 데이터에 임의의 노이즈를 추가한 입력 데이터(Input)를 노이즈가 없는 깨끗한 원본 데이터(Output)로 복원하도록 학습하는 AutoEncoder. 깨끗한 원본 데이터만을 학습하면 Inference에서 노이즈가 있는 데이터를 잘 복구하지 못하는 과적합(Overfitting)을 방지하는 일반화(Regularization)효과를 줄 수 있음.

비정형 데이터에서의 Noise - Gaussian Noise : 정규분포의 랜덤 노이즈 - Salt&Pepper Noise : 마치 사진에 소금과 후추가 떨어진 듯한 랜덤의 하얀색과 검은색 노이즈

Swap Noise

Swap Noise는 Kaggle 1등 솔루션을 통해 더욱이 알려졌습니다. 방법은 매우 간단합니다. 각 변수별로 임의의 관측치를 다른 관측치의 값으로 대체하는 것입니다. (1등 솔루션은 15%의 확률로 Swap이 이루어 지도록 하였습니다.) 이렇게 생긴 노이즈는 이미 갖고 있는 변수 공간에서의 다른 값으로 대체하는 것이기 때문에 이상한 값이 생성되지 않을것이며, 각 변수별로 따로 지정해야할 하이퍼파라메터(Ex. Gaussian Noise - 평균, 분산)도 없기 때문에 손쉽게 사용할 수 있습니다. 또한, 어떠한 분포의 변수에도 적용이 가능합니다.

정형 데이터에서 노이즈가 필요하다면, Swap Noise를 고려해보시기를 추천드립니다.

Reference

• Kaggle 1등 솔루션

1. Introduction

E-commerce 시장이 커짐에 따라, 많은 상품 중 고객이 관심있어 할 제품을 소개하는 추천 시스템의 중요성이 커지고 있습니다.

추천 시스템은 아래와 같이 크게 다음의 두 가지 전략으로 근간이 되어있습니다.

1. Content based approach : 각 유저(또는 아이템)의 특징을 통해 프로파일을 생성하여, 매칭하는 시스템

    - 예시 : 영화 프로파일 - 장르, 배우, 인기도 등...
    - 단점 : 프로파일 생성을 위한 데이터 수집 및 구성하는 과정이 필요

2. Collaborative Filtering : 유저-아이템 사이의 상호 관계를 이용하여, 유사성을 기반한 매칭 시스템

      - 예시 : 유저의 아이템 구매 내역, 프로그램 시청 선호도
    - 단점 : cold start(유저-아이템의 초기 데이터 부족)

추천 시스템은 입력 데이터을 Explicit/Implicit로 구분할 수 있습니다. (참고 : Matrix Factorization (1) - Explicit/Implicit Feedback)

1. Explicit Feedback : 유저가 직접 표현한 선호도
   • 예시 : 영화 평점, 좋아요/싫어요
     • 단점 : 데이터 확보가 매우 어려움
2. Implicit Feedback : 유저 행동 기반의 관측치
   • 예시 : 구매 내역, 검색 히스토리, 마우스 움직임

Explicit Feedback는 데이터 수집 과정이 어렵기 때문에, Implicit Feedback을 활용한 연구에 집중할 필요가 있습니다. Explicit Feedback에 사용되는 알고리즘을 Implicit Feedback에 착안하기 위해서는 아래의 Implicit Feedback의 특성에 대해 주의해야 합니다.

1. No Negative Feedback : 유저 행동 기반의 관측치는 아이템에 대한 선호를 암시할 수 있지만, 비선호에 대해서는 나타내기가 어려움.
2. Implicit feedback is inherently noisy : 유저 행동을 추적하는 것은 정확한 동기와 선호도를 추측하기는 어려움.
3. The numerical value of implicit feedback indicates confidence. : 반복된 행동은 유저의 선호를 반영할 수 있지만, 한 번의 이벤트 행동은 다양한 이유로 인해 발생되기 때문에 implicit feedback의 수치는 preference가 아닌 confidence를 나타냄.
4. Evaluation of implicit-feedback recommender requires appropriate measures. : 평가 척도에 대한 고민이 필요함 (아이템 availabilty와 반복적인 행동에 대한 고려).
   

2. Preliminaries

$$ \Large\begin{aligned} r_{ui} \end{aligned} $$

1. Implicit Feedback : 유저 u의 아이템 i 선호도 → 결측치의 경우, 선호도에 대해 모르기 때문에 대부분 무시하고 알고리즘이 구현됨.
2. Explicit Feedback : 유저 u의 아이템 i에 대한 행동 → 결측치의 경우, 유저가 행동을 하지 않은 것에도 의미가 있기 때문에 주로 "0"으로 대체함.

3. Previous work

$r_{ui}$를 추정에 주로 사용되는 두 개의 방법론은 아래와 같습니다.

1. Neighborhood models

유저(또는 아이템)간의 유사도를 이용하여, 비슷한 취향의 데이터의 가중평균으로 $r_{ui}$를 추정합니다. (논문에서는 user-oriented보다는 item-oriented neighborhood model이 정확도가 높고, 예측 모델에 대한 설명이 용이하기 때문에 item-oriented 방법론이 더욱 인기가 많다고 설명합니다.) item-oriented 관점으로 $r_{ui}$는 아래와 같이 계산됩니다. $$ \Large\begin{aligned} \hat{r_{ui}} = \frac{\sum_{j \in S^{k}(i;u)}S_{ij}r_{uj}}{\sum_{j \in S^{k}(i;u)}S_{ij}} \end{aligned} $$

• $s_{ij}$ : 아이템 i,j의 유사도
• $S^{k}(i;u)$ : 아이템 i와 유사한 아이템 k개의 유저 u의 선호도

Explicit Feedback의 경우, 유저와 아이템의 bias를 보정하여 알고리즘을 향상시킬 수 있지만, Implicit Feedback에는 적용하기가 어렵습니다. 그 이유는, Explicit Feedback과 같은 평점은 모두 같은 스케일(범위)를 구성되어 있지마, Implicit Feedback과 같은 빈도는 스케일이 모두 다르며, 유사도를 계산하는 것도 명백하지 않습니다.

2. Latent factor models

Latent factor model은 관측된 선호도에 대한 latent feature를 찾는 목적에서 Collaborative Filtering 대안으로 사용됩니다. $$ \large\begin{aligned} \min_{x^, y^}\sum_{r_{(u, i)} \text{is known}}(r_{ui} - x_{u}^{\intercal}y_{i})^2 + \lambda(|x_{i}|^2 + |y_{u}|^2) \end{aligned} $$

• $x_{u} \in \mathbb{R}^f$ : user-factor vector
• $y_{i} \in \mathbb{R}^f$ : item-factor vector
• $\hat{r_{ui}} = x_{u}^{\intercal}y_{i}$ : 유저, 아이템 latent feature vector의 내적으로 선호도를 예측
• $\lambda(|x_{i}|^2 + |y_{u}|^2)$ : 과적합을 위한 regularized term

4. Our Model

본 논문은 Implicit Feedback에 적용할 수 있는 Latent factor model을 제안합니다. 가장 먼저, 유저 u가 아이템 i에 대한 선호도(preference)를 나타내는 binary variable $p_{ui}$를 정의합니다.

$$ \Large \begin{aligned} p_{ui} = \begin{cases} 1, & r_{ui} > 0 \ 0, & r_{ui} = 0 \end{cases} \end{aligned} $$

즉, 유저 u가 아이템 i에 대해 행동을 했으면 1, 아니면 0이 됩니다. 그러나, preference $p_{ui}$만으로 행동을 한 관측치에 대해 설명이 부족하기 때문에 confidence $c_{ui}$가 필요합니다. 예를 들어, 아이템에 대한 존재를 모르거나 구입할 수 있는 여력이 부족하여 어떠한 행동을 못했을 수도 있으며, 선호하지는 않지만 다른 이유로 제품을 구입하는 행동을 했었을 수도 있습니다. 하지만, 반복적인 행동은 확실히 선호한다는 증거가 될 수 있습니다. 그렇기 때문에, $r_{ui}$가 커질수록 강한 선호의 지표로 증가함수인 confidence $c_{ui}$에 대해 아래와 같이 정의할 수 있습니다.

$$ \Large\begin{aligned} c_{ui} = 1 + \alpha r_{ui} \end{aligned} $$

$\alpha$에 따라, $r_{ui}$에 대한 변동을 통제합니다. 논문에서는 $\alpha = 40$으로 정하였으며, confidence $c_{ui}$는 고정된 수치로 계산되는 값이기 때문에, 최적화할 parameter가 아닙니다.

preference $p_{ui}$와 confidence $c_{ui}$를 반영하여 최적의 user/item latent factor를 찾기 위해, loss function을 아래와 같이 정의합니다. $$ \large\begin{aligned} \min_{x^, y^}\sum_{u, i}c_{ui}(p_{ui} - x_{u}^{\intercal}y_{i})^2 + \lambda(|x_{i}|^2 + |y_{u}|^2) \end{aligned} $$ 위의 loss function는 SGD(Stochastic Gradient Descent) 또는 ALS(Alternating Least Squares)를 통해 최적화할 수 있습니다.

이번 포스팅에서는 Anomaly Detection의 두번째 방법론 소개로 Density-based Methods의 LOF(Local Outlier Factor)에 대해 살펴보도록 하겠습니다. Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000, May). LOF: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data (pp. 93-104). 논문과 고려대학교 강필성 교수님의 자료를 참고했습니다.

Motivation

대부분의 이상치 탐지 알고리즘은 전체 데이터와 비교하여 각각의 관측치가 이상치인지 아닌지 판단하곤 합니다. 이러한 알고리즘은 위의 그림에서 $O_{2}$에 대해 이상치라고 판단하지 않습니다.

• $C_1$ - 밀도가 낮은 그룹, $C_2$ - 밀도가 높은 그룹
• $O_1, O_2$ - 이상치

$C_2$와 $O_2$사이의 거리는 $C_1$그룹내 관측치간의 거리와 유사하기 때문에, 전체적인 데이터 관점에서 보면 $O_2$는 이상치로 보기 어렵습니다.

이러한 단점을 극복하기 위해, LOF는 국소적인(local) 정보를 이용하여 이상치 정도를 나타내는 것을 목적으로 합니다.

LOF(Local Outlier Factor)란?

1. 개념

LOF는 각각의 관측치가 데이터 안에서 얼마나 벗어나 있는가에 대한 정도(이상치 정도)를 나타냅니다. LOF의 가장 중요한 특징은 모든 데이터를 전체적으로 고려하는 것이 아니라, 해당 관측치의 주변 데이터(neighbor)를 이용하여 국소적(local) 관점으로 이상치 정도를 파악하는 것입니다. 또한, 주변 데이터를 몇개까지 고려할 것인가를 나타내는 $k$라는 하이퍼-파라미터(hyper-parameter)만 결정하면 되는 장점이 있습니다.

2. Notion

알고리즘에서 사용되는 Notion 및 수식에 대해 알아보겠습니다.

2_1. the distance between objects p and q

$d(p, q)$ : 관측치 p와 q의 거리

2_2. $k$-distance of an object p

$k$-$distance(p)$ : 관측치 p와 가장 가까운 데이터 k개에 대한 거리의 평균

2_3. $k$-distance neighborhood of an object p

$N_{k}(p)$ : 관측치 p의 $k$-$distance(p)$보다 가까운 이웃의 집합 (= $k$-$distance(p)$를 계산할 때 포함된 이웃의 집합)

$k$개를 선택하니깐, $N_{k}(p)$의 개수는 $k$ 아닌가요?
정답부터 말씀드리면, No 입니다. 위의 [예시2]와 같이 동일한 distance를 갖는 이웃이 있는 경우, $N_{k}(p)$의 개수는 $k$보다 클 수 있습니다.

2_4. reachability distance of an object p w.r.t. object o

$$ \large\begin{aligned} reach{\text -}dist_{k}(p, o) = max{k{\text -}distance(o), d(o, p)} \end{aligned} $$

위의 그림으로 보면 직관적일 수 있습니다.

• 관측치 p가 o에서 멀다면 : 관측치 p와 o의 실제 거리
• 관측치 p가 o에서 가깝다면 : 관측치 o의 $k$-distance

2_5. local reachability density(lrd) of an object p

$$ \large\begin{aligned} lrd_{k}(p) = \frac{|N_{k}(p)|}{\displaystyle \sum_{o \in N_{k}(p)}reach{\text -}dist_{k}(p, o)} \end{aligned} $$ 수식을 해석하자면, 관측치 p에 대한 k-이웃의 $reach{\text -}dist_{k}(p, o)$ 평균의 역수입니다. 즉, 관측치 p주변에 이웃이 얼마나 밀도있게 있는가를 대변할 수 있습니다. k=3 일때의 예시를 통해 쉽게 접근해보도록 하겠습니다.

• [예시1] : 관측치 p의 3-이웃이 가깝게 있고, 이웃 $O_{i} (i = 1,2,3)$의 $reach{\text -}dist_{3}(p, o_i)$도 작기 때문에 $lrd_{3}(p)$는 큰 값이 산출

• [예시2] : 관측치 p의 3-이웃이 멀게 있고, 이웃 $O_{i} (i = 1,2,3)$의 $reach{\text -}dist_{3}(p, o_i)$이 크기 때문에 $lrd_{3}(p)$는 작은 값이 산출

2_6. local outlier factor(LOF) of an object p

$$ \large\begin{aligned} LOF_{k}(p) = \frac{\displaystyle\sum_{o \in N_{k}(p)}\frac{lrd_k(o)}{lrd_{k}(P)}}{|N_{k}(P)|} = \frac{\frac{1}{lrd_{k}(P)}\displaystyle\sum_{o \in N_{k}(p)}lrd_k(o)}{|N_{k}(P)|} \end{aligned} $$ 최종적으로, 관측치 p의 이상치 정도를 나타내는 LOF는 위와 같이 정의되며, 관측치 p의 밀도($lrd_{k}(p)$)와 이웃 o의 밀도($lrd_{k}(o)$)의 비율을 평균한 것 입니다. 조금 더 쉽게 보면, $lrd_{k}(p)$가 작을수록, $lrd_{k}(o)$가 클수록 LOF는 커지며, 이상치라는 것입니다.

• LOF < 1 : 밀도가 높은 분포
• LOF ≒ 1 : 이웃 관측치와 비슷한 분포
• LOF > 1 : 밀도가 낮은 분포, 크면 클수록 이상치 정도가 큼.

Summing Up

• LOF(Local Outlier Factor)는 국소적(local) 정보를 활용하여, 이상치 정도를 나타내는 척도임.
• 주변 데이터를 몇 개까지 볼 것인지($k$)에 대한 hyper-parameter 선정 필요
• LOF 값이 크면 클수록, 이상치 정도가 큼

Refernece

• Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000, May). LOF: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data (pp. 93-104).
• Cornellius Yudha Wijaya 블로그
• 강필성 교수님(고려대학교, DSBA 연구실) github
• Arun Mohan 블로그

아나콘다를 통해 파이썬 및 Pycharm을 사용 중, 다중 환경(32, 64bit) 설정 방법에 대해 알아보도록 하겠습니다. 대부분 유저분들은 64bit를 사용하고 계실테니, 32bit가 필요한 경우로 소개하도록 하겠습니다.

1. 아나콘다 32bit 가상환경 설정
2. Pycharm 가상환경 연결

1. 아나콘다 32bit 가상환경 설정

다중 환경을 설정할 때, 충돌되지 않도록 아나콘다 가상환경을 통해 진행합니다.

Anacomda Prompt를 통해, 아래의 명령어를 입력합니다.

set CONDA_FORCE_32BIT=1
conda create -n py37_32 python=3.7 anaconda

완료가 되었다면, 아래처럼 가상환경이 생성되었음을 확인할 수 있습니다.

2. Pycharm 가상환경 연결

1. Pycharm 프로젝트 생성

File > New Project를 통해 아래와 같은 화면에서 프로젝트 생성 및 이름(커서 부분) 설정을 합니다.

2. 32bit 가상환경 연결

1. Project Interpreter를 클릭
2. Existing interpreter 선택
3. 오른쪽에 ... 클릭
4. 아래와 같이 팝업창이 생기면, System Interpreter의 ... 클릭
5. 32bit 가상환경 설정하기 (※ 경로를 모르겠다면, 1. 아나콘다 32bit 가상환경 설정 단계에서, 가상환경 생성 확인(conda env list)을 통해 알 수 있습니다.)
6. OK 선택 후, 팝업창이 닫히면 Create를 통해 완료

이전 포스팅을 통해, Matrix Factorization의 기본 개념에 대해 알아보았다면, 이번에는 응용 및 확장성에 대해 소개하도록 하겠습니다. 이번 글 역시 Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8), 30-37 논문을 참조했습니다.

1. Adding Bias
2. Additional Input Sources
3. Temporal Dynamics
4. Inputs with Varying Confidence Levels
   

Advanced Matrix Factorization

1. Adding Bias

Matrix Factorization의 장점 중 하나는 데이터의 다양한 관점을 고려할 수 있다는 점입니다.

$$ \Large\begin{aligned} \hat{r_{ui}} = q_{i}^{\intercal}p_{u} \end{aligned} $$

• $$p_{u}, q_{i} \in \mathbb{R}^f$$ : User, Item Latent Matrix의 벡터
• $$\hat{r_{ui}}$$ : 유저 u의 아이템 i 선호도 추정값

가장 기본적으로 User-Item Matrix의 유저 u의 아이템 i에 대한 선호도를 유저와 아이템의 상호관계로 위와 같이 표현할 수 있지만, 아래와 같이 유저와 아이템 자체의 특성(bias 또는 intercept로 명칭)과 함께 표현할 수 있습니다.

$$ \Large\begin{aligned} \hat{r_{ui}} = \mu + b_{i} + b_{u} + q_{i}^{\intercal}p_{u} \end{aligned} $$

$$ \large\begin{aligned} \min_{q^, p^, b^*}\sum_{(u,i)\in K}(r_{ui} - \mu - b_{i} - b_{u} - q_{i}^{\intercal}p_{u})^2 + \lambda(|q_{i}|^2 + |p_{u}|^2 + b_{i}^2 + b_{u}^2) \end{aligned} $$

• $$\mu$$ : 모든 평점의 평균
• $$b_{i}$$ : 전체 영화의 평균에 대한 아이템 i의 편차
• $$b_{u}$$ : 전체 유저의 평균에 대한 유저 u의 편차

예를 들면, Joe의 Titanic에 대한 점수(3.9)를 다음과 같이 표현할 수 있습니다.

3.9 = 3.7(모든 평점 평균) + 0.5(영화 관점에서, Titanic의 0.5정도의 우위) - 0.3(유저 관점에서, Joe가 0.3정도 평균적으로 점수를 낮게 줌)

2. Additional Input Sources

Cold start 상황에서 Matrix Factorization은 구매, 검색 기록과 같은 행동 정보(behavioral information) 또는 인구 통계와 같은 추가적인 데이터 소스를 함께 사용할 수 있습니다.

간단하게 Boolean Implicit Feedback을 예를 들어보면, $$N(u)$$는 유저 u의 Implicit Feedback의 아이템 집합일 때, Matrix Factorization은 이 정보를 활용하여 유저를 프로파일링 할 수 있습니다.

• $$\displaystyle \sum_{i \in N(u)}x_{i}$$ : 유저 u가 아이템 i에 대한 Implicit Feedback
• $$\displaystyle|N(u)|^{-0.5}\sum_{i \in N(u)}x_{i}$$ : Nomaliazed Implicit Feedback

또는, 유저 u의 인구 통계학 정보도 표현할 수 있습니다.

• $$\displaystyle \sum_{a \in A(u)}y_{a}$$ : 유저 u의 정보(성별, 연령, ...)

이러한 추가적인 데이터 소스를 통해 유저 u에 대한 아이템 i의 선호도를 다음과 같이 종합적으로 나타냅니다.

$$ \large\begin{aligned} \hat{r_{ui}} = \mu + b_{i} + b_{u} + q_{i}^{\intercal}[p_{u} + |N(u)|^{-0.5}\sum_{i \in N(u)}x_{i} + \sum_{a \in A(u)}y_{a}] \end{aligned} $$

3. Temporal Dynamics

지금까지 본 내용은 사실 정적(static)인 모델이였지만, 실생활에서는 상품인식과 인기는 시간에 따라 변화하는 요소입니다. Matrix Factorization은 아래의 식으로 유저-아이템 상호작용에 대해 동적(dynamic)이고 시간 변화를 나타낼 수 있습니다. $$ \Large\begin{aligned} \hat{r_{ui}}(t) = \mu + b_{i}(t) + b_{u}(t) + q_{i}^{\intercal}p_{u}(t) \end{aligned} $$

각 시간적 변화는 다음과 같은 예시를 볼 수 있습니다.

• $$b_{i}(t)$$ : 영화의 인지도는 해당 작품의 배우가 다른 영화에 출현하는 시기에 갑자기 영향을 받는 경우
• $$b_{u}(t)$$ : 유저의 평가 기본 점수가 과거에는 3점이였다가 어느 순간 4점으로 바뀌는 경우
• $$q_{i}^{\intercal}p_{u}(t)$$ : 유저의 선호 영화 장르의 변화

4. Inputs with Varying Confidence Levels

종종, 모든 관측된 선호도(또는 평가, rating)가 동일한 가중치(weight) 또는 신뢰도(confidence)를 갖지 않을 수도 있습니다. 예를 들면, 대규모 광고로 인한 특정 상품에 쏠리는 선호도라던지 의도적으로 특정 상품에 대해 선호도를 낮추려는 적대적인 유저가 존재하는 경우도 있습니다. 또 다른 예시로, 상품 구매 여부(1/0)으로 나타낸 Implicit Feedback의 경우 상품 구매 이력이 있다고 해서 선호한다고 할 수 없습니다. 이런 경우, 상품을 몇 번 구매 횟수를 통해 신뢰도를 부여할 수 있습니다. 즉, 유저 u의 아이템 i에 대한 $$r_{ui}$$선호도에 신뢰도 $$c_{ui}$$를 통해, 아래와 같이 loss function을 나타냅니다.

$$ \large\begin{aligned} \min_{q^, p^, b^*}\sum_{(u,i)\in K}c_{ui}(r_{ui} - \mu - b_{i} - b_{u} - q_{i}^{\intercal}p_{u})^2 + \lambda(|q_{i}|^2 + |p_{u}|^2 + b_{i}^2 + b_{u}^2) \end{aligned} $$

Summing up

Matrix Factorization은 다음과 같이 확장시켜 응용할 수 있습니다.

• User-Item Matrix + 유저/아이템 각각의 특성을 반영
• User-Item Matrix + 추가적인 데이터 소스(과거 구매이력, 인구 통계학적 정보, 등...)
• User-Item Matrix + 시간적 정보
• User-Item Matrix + 유저/아이템의 신뢰도 정보

랜덤 포레스트(Random Forest)를 학습한 후, 많은 변수 중 가장 예측력이 강한 변수가 무엇인지 파악하기 위해 변수 중요도(Variable Importance)를 확인한 경험이 있으실 겁니다. 이번 포스팅에서는 랜덤 포레스트에서 변수 중요도를 계산하는 방법 3가지에 대해 소개하도록 하겠습니다.

1. MDI(Mean Decrease in Impurity) Importance
2. Permutation Importance
3. Drop column Importnace

랜덤 포레스트(Random Forest)

랜덤 포레스트란, 의사결정나무의 과적합(Over Fitting)을 해결하기 위해 여러개의 의사결정트리를 취합하여 학습성능을 높이는 앙상블 모형(Ensemble Model)입니다.

랜덤 포레스트는 아래와 같이 구현됩니다.

1. Bootstrap Sampling : 전체 데이터 N개에서 N개의 sample을 복원추출
2. Feature Random Selection : 의사결정나무를 분개할 때마다 변수 중 p개를 선택하여, 최적의 변수와 split-point를 선정
3. 1~2번 단계를 B번 반복하여, 결과를 취합

랜덤 포레스트는 각 나무에서 데이터와 변수 모두 랜덤으로 선택하기 때문에, 각 나무가 uncorrelated model(≒ 독립적)로 다양하고 풍부한 표현력을 갖는 강점이 있습니다.

변수 중요도(Variable Importnace)

랜덤 포레스트가 많은 강점이 있음에도 불구하고, 블랙박스모형이기 때문에 설명변수와 반응변수의 설명력을 확보하기 어렵다는 단점도 있습니다. 이를 어느 정도 해결하기 위해, 변수 중요도(Variable Importance)라는 척도를 통해 어느 변수가 예측 성능에 중요한 역할을 하는지를 추정하곤 합니다.

블랙박스모형에서 설명변수와 반응변수의 관계 살펴보기 - Partial Dependence Plot (PDP) 맛보기 변수 중요도는 "해당 변수가 상대적으로 얼마만큼 종속변수에 영향을 주는가?"에 대한 척도이기 때문에, "어떻게 영향을 주는가?"에 대한 답변으로는 적절하지 않습니다. Partial Dependece Plot은 블랙박스모형에서 설명변수가 종속변수에게 주는 marginal effect를 추정하는 방법입니다.

1. MDI(Mean Decrease in Impurity) Importance

MDI Importance는 가장 대표적인 변수 중요도로서, scikit-learn의 default로 내장되어 있는 방법론입니다. 각 변수가 split될 때 impurity 감소분의 평균을 중요도로 정의하는 것으로 식은 아래와 같습니다. $$ \large\begin{aligned} \Delta i(t) = i(t) - \frac{N_{tl}}{N_{t}}i(t_{l})-\frac{N_{tr}}{N_{t}}i(t_{r}) \end{aligned} $$

• $$i(t)$$ : t노드의 impurity (entropy, gini index, variance, ...)
• $$N_{t}$$ : t노드의 관측치 개수

각 노드의 관측치 개수를 고려하여 impurity 감소분이 계산되며, 값이 클수록 중요도가 높습니다.

• 장점 : 빠르고, 직관적임
• 단점 : 연속형 변수와 high-cardinality 범주형 변수에 대해서는 편향됨.

“the variable importance measures of Breiman's original Random Forest method ... are not reliable in situations where potential predictor variables vary in their scale of measurement or their number of categories.” [(Bias in random forest variable importance measures: Illustrations, sources and a solution)] (https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-8-25)

2. Permutation Importance

Permutation Importance는 "해당 변수가 랜덤으로 분포된다면, 어느 정도 성능이 떨어지는가?"라는 가정을 갖고 있습니다. Permutation Importance는 랜덤포레스트의 각 나무에서 OOB(Out of Bag) sample에서 다음과 같이 구현됩니다.

1. (①~③) b번째 tree를 생성할 때, bootstrap sample로 나무를 학습
2. (④) OOB Samples : 학습할 때 사용되지 않은 데이터 셋으로 Validation 데이터를 생성
3. (⑤) Reference Measure : OOB Sample로 나무의 예측력(accuracy, R-square, MSE 등)을 계산 및 저장
4. (⑥) Permutation Measure : OOB Sample에서 j번째 변수의 데이터를 무작위로 섞은 뒤, 학습된 나무의 예측력을 계산 및 저장
5. ⑤, ⑥단계에서 저장된 예측력 척도의 차이(Reference Measure - j번째 변수의 Permutation Measure)를 계산

위의 과정을 나무의 개수 B만큼 시행하여, 각 변수에서 계산된 중요도의 평균으로 Permutation Importance로 정의합니다.

위의 과정 중 특정 변수를 무작위로 섞었을 때 기존 Reference 척도보다 낮아지게되면, 해당 변수는 중요하다고 판단되며 척도가 유사하거나 오히려 좋아지면 불필요하다고 판단내릴 수 있습니다.

• 장점 : 모델을 다시 학습하지 않아도 되기 때문에, 계산이 빠름. 직관적임.
• 단점 : Permutation importance overestimates the importance of correlated predictors — Strobl et al (2008)

OOB(Out of Bag) Sample
N개의 데이터에서 Boostrap Sampling으로 N개의 데이터를 선택하고, 선택되지 못한 데이터를 OOB Sample이라고 합니다. OOB Sample은 학습에 사용되지 않았기 때문에, validation 용도로 사용할 수 있다는 장점이 있습니다.
- 관측치 A가 OOB Sample에 포함될 확률 : 복원추출을 한 번 시행할 때, 데이터 N개 중 관측치 A가 뽑히지 않을 확률은 $\frac{N-1}{N}$ 입니다. 이 과정을 충분히 큰 N번 반복하면 다음과 같은 확률이 계산됩니다. $$ \lim_{N\rightarrow\infty}(\frac{N-1}{N})^{N} = \lim_{N\rightarrow\infty}(1-\frac{1}{N})^N = e^{-1} = 0.368 $$

3. Drop Column Importance

Drop Column Importance 방법은 모든 변수를 사용했을 때의 Reference척도에서 특정 변수를 빼고 랜덤포레스트를 다시 학습했을 때의 척도의 차이로 변수 중요도를 정의합니다. Permutation Importance와 동일하게, 변수를 뺏을 때의 성능이 많이 떨어진다면 해당 변수는 중요한 변수라고 할 수 있습니다.

• 장점 : 개념이 매우 직관적임
• 단점 : 변수의 개수만큼 모델 재학습이 필요하기 때문에, Computation 관점으로 매우 비효율적

Reference

• Eryk Lewinson 블로그
• [explained.ai] (https://explained.ai/rf-importance/)
• 사쿠의 데이터 블로그

Challenge

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.
  • 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다. 7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

Solution

On my own

def solution(operations):
    """
    - param operations : 이중 우선순위 큐가 할 연산 (List)
    - return : 큐가 비어있으면 [0,0], 비어있지 않으면 [최댓값, 최솟값]
    """

    import heapq

    q = []

    for oper in operations : 
        if oper in ["D 1", "D -1"] : 

            if len(q) == 0 : 
                continue

            if oper == "D 1" : 
                q.remove(max(q))
            else : 
                heapq.heappop(q)

        else : 
            num = int(oper.split(' ')[1])
            heapq.heappush(q, num)                

    if len(q) == 0 :
        answer = [0, 0]
    else : 
        answer = [max(q), min(q)]

    return answer

풀이 방법

1) 원소를 삭제하는 경우("D 1", "D -1")와 원소를 추가하는 경우("I 숫자")로 나누어 진행 2) python의 heapq는 최소큐로 진행되기 때문에, "D -1"의 최소값을 삭제할 때는 heapq.heappop을 활용 3) "D 1"의 최대값을 삭제할 때는 list.remove를 활용 4) 모든 연산 후 큐가 비어있으면 [0,0], 비어있지 않으면 [최댓값, 최솟값]을 return

Lessons learned

이번 알고리즘 문제는 크게 어렵지 않았지만, 아직 갈길은 먼 것 같습니다.. 화이팅!!

Collaborative Filtering 방법론 중 가장 대표적인 방법론인 Matrix Factorization에 대해 살펴보도록 하겠습니다. Netflix 추천 성능을 크게 상향시킨 Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer, 42(8), 30-37. 논문을 참조했습니다.

Matrix Factorization

Matrix Factorization은 User-Item Matrix를 F차원의 User와 Item의 latent factor 행렬곱으로 분해하는 방법을 말합니다. User-Item Matrix의 유저 u의 아이템 i에 대한 선호도는 다음과 같이 User/Item Latent Matrix의 벡터의 곱으로 표현될 수 있습니다. $$ \Large\begin{aligned} \hat{r_{ui}} = q_{i}^{\intercal}p_{u} \end{aligned} $$

• $$p_{u}, q_{i} \in \mathbb{R}^f$$ : User, Item Latent Matrix의 벡터
• $$\hat{r_{ui}}$$ : 유저 u의 아이템 i 선호도 추정값

User-Item Matrix를 User/Item Latent Matrix로 맵핑(mapping)이 되면, 유저가 평가하지 않은 선호도에 대해서도 위의 수식을 통해 쉽게 추정할 수 있습니다.

비슷한 방법으로 특이값분해(Singular Value Decomposition, SVD) 방법도 있지만, User-Item Matrix와 같이 결측값이 많은 Sparse Matrix(희소행렬)에서는 적용하기가 어렵습니다.

특이값분해(Singular Value Decomposition, SVD) 특이값 분해는 (m×n)차원의 A행렬을 다음과 같이 분해하는 방법론입니다. $$ \Large\begin{aligned} A = U\Sigma V^\intercal \end{aligned} $$

• $$U$$ : (m×m)차원의 직교행렬
• $$V$$ : (n×n)차원의 직교행렬
• $$\Sigma$$ : (m×n) 직사각 대각행렬 (대각성분 이외의 모든 값은 0)

기존의 많은 연구들이 결측치에 대한 Imputation에 집중했지만, 연산량이 많으며 부정확 Impuatation은 데이터를 왜곡시키는 단점이 있습니다.

하지만, Matrix Factorization은 Latent vector를 학습할 때, 관측된 선호도만 모델링에 활용하며, 과적합을 피하기위해 Regularized Squared Error를 사용합니다. $$ \Large\begin{aligned} \min_{q^, p^}\sum_{(u,i)\in K}(r_{ui} - q_{i}^{\intercal}p_{u})^2 + \lambda(|q_{i}|^2 + |p_{u}|^2) \end{aligned} $$

• $$K$$ : 관측된 선호도 $$r_{ui}$$의 $$(u, i)$$

과거에 관측된 선호도에 대해서만 모델링을 하지만, 향후에 관측되지 못한 선호도를 예측하는 일반화 모델을 만드는 것이 목표이기 때문에, Regularizaion을 통해 관측 데이터에 대한 과적합을 줄이는 것입니다.

알고리즘 학습 방법

1. Stochastic Gradient Descent (SGD)

1. 실제 선호도와 예측된 선호도의 차이를 에러로 정의 $$e_{ui} = r_{ui} - q_{i}^{\intercal}p_{u}$$
2. 현재 위치의 gradient 반대방향으로 $$q_{i}, p_{i}$$를 갱신 $$q_{i} ← q_{i} + \gamma \cdot (e_{ui}p_{u} - \lambda \cdot q_{i})$$ $$p_{u} ← p_{u} + \gamma \cdot (e_{ui}q_{i} - \lambda \cdot p_{u})$$

비교적 학습시간이 짧고, 쉽게 구현할 수 있습니다.

2. Alternating Least Squares (ALS)

$$q_{i}$$와 $$p_{u}$$를 둘다 모르기 때문에 Reqularized Squared Error는 Convex 하지 않지만, 만약 둘 중 하나를 고정시키면 2차식의 최적화 문제로 해결할 수 있습니다. ALS는 $$q_{i}$$와 $$p_{u}$$를 번갈아서 고정시키며, 최소제곱문제로 해를 구합니다. ALS는 다음과 같은 상황에서 SGD보다 유리합니다.

1. 병렬 시스템 : $$q_{i}$$를 학습할 때, 다른 item factor와 독립적으로 계산되기 때문에 병렬 적용이 용이함. ($$p_{u}$$도 마찬가지)
2. Implicit data : Explicit data에 비해 결측치가 비교적 적기 때문에, SGD를 사용하게 되면 연산량이 증가함.

Summing up

• Matrix Factorizaion : User-Item Matrix를 User/Item Latent Matrix로 행렬분해하는 방법론입니다.
• 유저가 평가하지 않은 결측치가 많기 때문에, SVD는 적용이 불가합니다.
• SGD, ALS 알고리즘을 통해, 관측된 데이터에 대해서만 패널티를 추가하여 학습을 합니다.

Reference

• SVD : ratsgo님 블로그(네이버)
• soobarkbar님 블로그
• JaeDuck Seo님 블로그

머신러닝을 시작하면, 가장 먼저 볼 수 있는 것이 아마 선형회귀분석(Linear Regerssion Analysis)일 것입니다.

Q. 선형회귀분석의 '선형'의 의미는 무엇일까요?

'선형(Linear)'의 의미를 '독립변수와 종속변수의 관계 그래프가 직선인 경우'라고 생각하신다면, 잘못된 생각입니다.

이번 포스팅에서는 일반선형회귀와 일반화선형회귀를 비교하면서 "선형"과 "일반화"의 의미에 대해 소개하려고 합니다.

회귀분석(Regression Analysis)이란?

회귀분석은 여러 개의 독립변수와 하나의 종속변수 간의 상관관계를 모델링하는 기법을 통칭합니다. 즉, X인자를 통해 Y를 설명하고자 하는 넓은 영역을 말합니다.

일반화선형회귀 - 일반화, 선형의 의미

1. 선형회귀(Linear Regression)이란?

선형회귀의 정확한 정의는 종속변수의 평균이 독립변수와 회귀계수(Regressin Coefficient)들의 선형결합(Linear Combination)으로 된 회귀모형을 말하며, 회귀계수를 선형 결합으로 표현할 수 있는 모형을 뜻합니다.

다음의 두 예제가 대표적인 선형회귀입니다.

1. $$y = \beta_{0} + \beta_{1}x_{1} + \beta_{2}x_{2}$$
2. $$y = \beta_{0} + \beta_{1}x_{1} + \beta_{2}x_{2}^2$$ → ($$x_{2}^2$$을 $$x_{3}$$로 치환) $$y = \beta_{0} + \beta_{1}x_{1} + \beta_{2}x_{3}$$

특히, 2번의 경우 $$x_{2}$$에 대한 제곱항이 있지만, $$x_{3}$$으로 치환하면 1번과 같은 식으로 나타낼 수 있습니다. 여기서 꼭 주의하셔야 할 점은 "선형의 의미가 독립변수와 종속변수가 꼭 직선의 그래프 형태(1차식)를 나타내는 것이 아니다."라는 점 입니다.

2. 일반화선형회귀(Generalized Linear Regression, GLM)이란?

일반선형회귀의 경우 선형성, 독립성, 등분산성, 정규성의 가정을 갖고 있습니다. 하지만, 종속변수가 연속형이 아니라면 대표적으로 오차항의 정규성 가정이 깨지게 됩니다. 대표적으로 로지스틱 회귀(Logistic Regression)과 Cox의 비례위험회귀(Cox's Proportional Hazard Regression)는 대표적인 일반화선형회귀이며, 일반화선형회귀는 종속변수를 적절한 함수로 변화시킨 $$f(y)$$를 독립변수와 회귀계수의 선형결합으로 모형화한 것입니다.

로지스틱 회귀(Ligistic Regression) 로지스틱 회귀는 종속변수가 이분형(ex. 실패/성공, 0/1, 생존/사망…)일 때의 일반화선형회귀 중 하나로서, log odds($$log(\frac{y}{1-y}$$)에 대해 독립변수와 회귀계수의 선형결합으로 모형화합니다.

Cox의 비례위험회귀(Cox's Proportional Hazard Regression) Cox의 비례위험회귀는 시간에 따라 hazard ratio($$log(\frac{h(t)}{h_0(t)})$$)가 일정하다는 가정을 갖은 생존분석 중 가장 많이 쓰이는 방법론으로서, 어떤 사건(event)이 일어날 때까지의 시간을 대상으로 분석하는 통계방법입니다.

Summing Up

• 선형(Linear) 모형 : 회귀계수를 독립변수의 선형결합으로 나타낸 모형
• 일반화선형회귀 : 종속변수를 변환하여, 회귀계수를 독립변수의 선형결합으로 나타낸 모형

Reference

• [Statistics by Jim] (https://statisticsbyjim.com/regression/difference-between-linear-nonlinear-regression-models/)
• [gimmesilver님 블로그] (https://brunch.co.kr/@gimmesilver/18)
• [높이 비상하는 즐거운 상상] (https://dermabae.tistory.com/187)

Collaborative Filtering 방법론 중 하나인 Matrix Factorization에 대해 소개를 하려다보니, Explicit/Implicit Feedback에 대한 설명이 먼저 필요한 것 같습니다. Explicit/Implicit Feedback은 Collaborative Filtering에서 사용되는 데이터인 User-Item Matrix의 데이터 종류입니다.

Explicit Feedback

Explicit Feedback이란, 유저가 직접 아이템에 대한 선호도를 표현한 데이터입니다.

예를 들면, Watch나 네이버 영화에서는 유저가 선택하는 010(또는 05)척도의 영화 평점 시스템이 있고, Netflix의 경우 "좋아요/싫어요"로 영화를 평가할 수 있습니다.

• 장점 : 유저 선호도의 직접적인 정보를 획득
• 단점 : 데이터를 구하기 어려움. 유저가 직접 평가를 하지 않는 이상, 구할 수 없음

Implicit Feedback

Implicit Feedback이란, 유저의 선호도를 간접적으로 유추하는 데이터입니다. Explicit Feedback이 데이터 품질 관점에서 매우 좋은 건 사실이지만, 데이터 수집이 어렵기 때문에 Implicit Feedback를 활용한 연구가 활발히 진행되고 있습니다.

온라인 쇼핑몰에서의 제품 구매 경험, 검색 경험, 검색 패턴 또는 마우스 행동들이 Implicit Feedback에 포함됩니다. 이러한 대체 데이터들은 유저 선호도와 연관이 있을 것이라는 가정을 내포하고 있습니다. 예를 들면, "원하는 상품의 페이지에서는 마우스 움직임이 많을 것이고 관심 없는 상품의 페이지에서는 별다른 행동 없이 페이지를 넘길 것이다."라는 가정을 하는 것입니다.

• 장점 : 유저의 평점 행동 없이, 데이터 획득 가능

• 단점 1 : 부정적인 피드백의 부재(No negative feedback) - 해당 아이템에 대한 부정적인 행동을 추론하기란 어렵습니다. 예를 들면, 유저 A가 Item 1을 구매하지 않았는데, 선호하지 않아서 사지 않은 것인지, 상품을 알지 못했기 때문에 구매를 하지 않은 것인지, 모호함이 있습니다. 반면, Explicit Feedback은 비선호를 나타내는 수치가 내포되어 있기 때문에, missing data보다는 주어진 데이터에 집중할 수 있습니다. 하지만, Implicit Feedback 데이터를 다룰 때에는, 관찰되지 않는 데이터에 비선호 정보를 포함할 가능성이 있기 때문에, missing data도 모델링에 포함해야 합니다.

• 단점 2 : 노이즈(Implicit feedback is inherently noisy) - 유저 행동에 대한 정확한 동기를 알 수 없습니다. 유저 A가 Item 1을 구매한 내역이 선호해서 구매했을 수도 있지만, 선물 용도로 샀을 수도 있고, 구매 후 실망을 했을지도 모릅니다.

• 단점 3 : Explicit Feedback의 숫자 값은 선호도를 나타내지만, Implicit Feedback에서는 신뢰도를 나타냅니다.(The numerical value of explicit feedback indicates preference, whereas the numerical value of implicit feedback indicates confidence) 다시 말해, Explicit Feedback에서는 수치가 클수록 높은 선호도를 나타내지만, Implicit Feedback에서는 항상 그렇지만은 않습니다. 유저 A가 온라인 쇼핑몰에 오래 머물러있었지만, 정말 온라인 쇼핑몰이 좋아서 그런 것인지, 잠시 자리를 비운 상태인지, 선호도를 나타내지는 않습니다. 하지만, 온라인 쇼핑몰에 반복적으로 접속을 한 이벤트가 있다면 유저의 의견이 반영된 것일지도 모릅니다.

• 단점 4 : Implicit Feedback 기반 추천시스템의 적절한 평가 척도 필요(Evaluation of implicit-feedback recommender requires appropriate measures) Implicit Feedback은 ground truth가 없기 때문에 평가 척도에 대한 고민이 필요합니다. 또한, Item 이용 가능성, 다른 Item과의 경쟁, 반복되는 feedback을 고려해야 합니다. 예를 들면, 영화 2개가 동시간에 상영이 된다고 하면, 유저 A가 두 영화를 모두 선호할지라도 한쪽만 선택할 수 있기 때문에 Implicit Feedback 데이터에 나머지 다른 영화에 대한 정보는 남을 수 없습니다.

Reference

Hu, Y., Koren, Y., & Volinsky, C. (2008, December). Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE International Conference on Data Mining (pp. 263-272). Ieee.

오늘도 알수없는 유튜브 알고리즘이 날 여기로 이끌었다...

넋놓고 유튜브를 몇시간째 보신 분들은 위의 댓글을 보신적이 있으실 겁니다. 처음 내가 원하는 영상을 보다보면, 어느 순간 평소에 관심도 없던 유튜브를 보고 있는 제 자신을 발견할 때가 종종있습니다. 저같은 경우엔 "패트병으로 재활용 아이디어"라든지, "10년 전 가수 무대 영상"이라든지.. 분명 게임 영상을 보고 있었는데 알수없는 유튜브 알고리즘에 빠져 관련없는 영상을 본 경우가 매우 많습니다.

위에서 말한 유튜브 알고리즘의 핵심은 추천 시스템입니다. 이번 포스팅에서는 Isinkaye, F. O., Folajimi, Y. O., & Ojokoh, B. A. (2015). Recommendation systems: Principles, methods and evaluation. Egyptian Informatics Journal, 16(3), 261-273. 논문의 리뷰로서 추천 시스템 분야의 전체적인 개요에 대해 알아보도록 하겠습니다.

추천 시스템(Recommendation System)이란?

추천 시스템이란, 유저의 선호도 및 과거 행동을 바탕으로 개인에 맞는 관심사를 제공하는 분야를 말합니다. 이러한 추천 시스템은 위에서 말했듯이 유튜브와 같은 비디오추천에도 쓰이지만, 온라인 쇼핑몰이나 뉴스 추천, 금융 상품 추천, 검색 시스템 등 다양한 분야에서 사용되고 있습니다.

추천 시스템은 서비스 제공자와 유저에게 모두 이득이 될 수 있습니다.

• 서비스 제공자 : quailty가 높은 상품 제공으로 인한 수익 창출
• 유저 : 원하는 상품을 찾기 위한 시간 절감, 새로운 상품에 대한 접근 용이

랭킹 시스템(Ranking System)과 추천 시스템의 차이
사용자에게 Top N개의 상품을 추천해주는 것은 추천 시스템에 추천 시스템 분야에는 잘 포함하지는 않습니다. 그 이유는 개인의 성향이나 과거의 행동에 대한 정보가 반영되지 않았다는 점입니다.

추천 시스템 방법론

1. Content-based Filtering

콘텐츠 기반 필터링(Content-based Filtering)은 해당 아이템의 도메인을 활용한 것으로 유저가 관심있는 아이템의 속성을 분석하여 새로운 아이템을 추천해주는 것입니다. 뒤에서 설명드릴 Collaborative Filtering(Item-based)와 다른 점은 다른 유저의 정보가 사용되지 않는다는 점입니다.

예를 들면, 내가 산 옷과 비슷하게 생긴 옷을 추천해주거나 뉴스 기사가 비슷하거나 관련된 다른 뉴스를 추천해주는 경우에 자주 사용됩니다.

이러한 콘텐츠 기반 필터링은 아이템들의 feature를 잘 추출하기 위한 TF-IDF(Term Frequency - Inverse Document Frequency)나 Word2Vec과 같은 Feature Extraction 방법론이 사용됩니다. 또한, 추출된 feature를 통해 아이템을 비교할 유사도(Similarity)에 대한 선택도 중요합니다.

• 장점 : 유저의 선호도에 대한 정보 없이, 아이템 정보만으로 추천 가능
• 단점 : 아이템을 설명할 수 있는 데이터(item's metadata) 구축이 필요.

2. Collaborative Filtering

협업 필터링(Collaborative Filtering, CF)은 유저-아이템의 관계(User-Item interaction)로부터 도출되는 추천 시스템입니다.

• 장점 : 아이템에 대한 콘텐츠의 정보 없이 사용 가능
• 단점1 Cold Start : ‘새로 시작할 때 곤란함’을 의미하며, 새로운 유저나 아이템의 초기 정보 부족의 문제점
• 단점2 Data Sparsity : 수 많은 유저와 아이템 사이에 경험하지 못한, 구매해보지 못한 경우가 데이터의 대부분을 차지함 (Ex. 온라인 쇼핑몰에서 내가 구매한 목록보다 구매하지 않은 목록이 압도적으로 많음)
• 단점3 Scalability : 유저와 아이템의 수가 많아질수록 데이터의 크기가 기하급수로 커짐

2_1. Memory-based Filtering

User-Item Matrix로부터 도출되는 유사도 기반으로 아이템을 추천을 합니다.

2_1_1. User-based

유저 간의 선호도(아이팀에 대한 점수)나 구매 이력을 비교하여 추천하는 방법을 User-based CF라고 합니다. 예를 들면, 유저 A가 [라면, 삼각김밥, 김치, 콜라]를 샀다고 하면, 유저 A와 가장 유사한 쇼핑 목록을 갖고 있는 유저 B [라면, 삼각김밥, 김치]에게 [콜라]를 추천해주는 것입니다.

2_1_2. Item-based

User-based와는 반대로 아이템 간의 유저 목록을 비교하여 추천하는 방법입니다.

예를 들면, 라면을 [유저 A, 유저 B, 유저 C, 유저 D]가 구매를 했다면, 라면을 산 유저의 목록과 가장 비슷한 삼각김밥 [유저 A, 유저 B, 유저 C, 유저 E]을 유저 D에게 추천하는 것입니다. 또는, 유저 E에게 라면을 추천해줄 수도 있습니다.

2_2. Model-based Filtering

Model-based CF는 User-Item interaction을 머신러닝이나 딥러닝과 같은 모델을 학습하는 것을 말합니다. 장바구니 분석(Association rule)과 같이 아이템 간의 관계를 학습할 수도 있고, Clustering을 통해 유사한 아이템이나 유저 간의 그룹을 형성할 수도 있습니다. 이 외에도 Matrix Factorization, Bayesian Network, Decision Tree 등 많은 방법론이 사용됩니다.

3. Hybrid Filtering

콘텐츠 기반 필터링과 협업 필터링은 장단점이 있기 때문에 두 방법을 같이 활용하는 방법을 Hybrid Filtering이라고 합니다.

정말 많은 파생 방법론이 있지만, 대표적으로 데이터가 적은 초기단계에는 콘텐츠 기반 필터링으로 하다가 어느정도 데이터가 누적이 되면 협업 필터링으로 변경하는 것도 포함이 됩니다.

Doodles

개인적으로 추천 시스템을 공부하게 된 이유는 크게 세 가지 가지가 있습니다.

첫 번째, 추천 시스템 분야는 다양한 방법론으로 구성되어 있다는 점이다. 단 하나의 방법론으로는 추천 문제를 풀 수는 없습니다. 데이터 Sparsity, Scalability를 해결하기 위한 Matrix Factorization, Feature Extraction으로 시작해서 아이템(혹은 유저)사이의 유사성, 또는 제3의 모델링 등 여러 단계가 필요하기 때문에 알고 싶은 것도 많고, 해보고 싶은 것도 많습니다.

두 번째, 논리적 구성을 필요로합니다. 가령, 예측력만 요구하는 task에선 모델링 가정 없이 여러 모델을 사용하여 가장 좋은 것을 선택하는 경우가 있습니다. 하지만, 추천 시스템의 논문들을 보면 "어떠한 가정을 갖고, 이렇게 방법론을 구성하였습니다."라는 고민의 흔적이 있습니다.

세 번째, "개인화"라는 단어의 인식 변화입니다. 과거의 개인화는 개인 인적 정보나 세상과 고립된 무언가에 자주 쓰이던 단어였는데, 최근에는 실시간으로 개인의 성향과 니즈에 맞춰 알맞는 경험을 할 때 자주 쓰입니다. 심지어, 초개인화라는 단어가 나올 정도로 앞으로의 미래는 점점 개인에 맞춘 특별한 경험을 중요시하게 될 것 같습니다.

앞으로의 포스팅에는 추천 시스템 관련 논문을 주로 리뷰하도록 하겠습니다.

Challenge

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

   • 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   • 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

   • 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   • 가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

Solution

1. On my own

def solution(scoville, K):
    """
    - param scoville : 음식의 스코빌 지수를 담은 배열 (List)
    - param K : 스코빌 지수 임계치 (Int)
    - return : 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 (Int)
    """

    import heapq

    heapq.heapify(scoville)
    cnt = 0
    while True : 
        min1 = heapq.heappop(scoville)
        min2 = heapq.heappop(scoville)
        if min1 >=  K :
            break
        cnt += 1
        heapq.heappush(scoville, min1 + min2*2)

        if len(scoville) <= 1 : 
            return -1
    return cnt

풀이 방법

1) heapq.heapify로 scoville을 heap구조로 만들며, 정렬된 상태로 저장 2) heapq.heappop으로 scoville에서 가장 작은 2개의 음식을 삭제하며 별개로 저장 3) heapq.heappush로 새로 만든 음식을 soville에 추가하며, 동시에 정렬 4) scoville의 최소값이 K이상이면 반복문을 멈추며, 음식을 계속 만들어서 1개로 합쳐지더라도 K이상이 되지 않으면 -1로 반환

2. Best Code

import heapq

def mix(first,second):
    return first+ second*2

def bfs(scoville,K):
    successFlag = False
    count = 0

    while len(scoville)>=1:
        first = heapq.heappop(scoville)
        if first > K:
            successFlag = True
            break
        if len(scoville)>=1:
            second = heapq.heappop(scoville)
            mixResult = mix(first,second)
            heapq.heappush(scoville, mixResult)
            count+=1

    if successFlag:
        return count
    else:
        return -1

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    answer = bfs(scoville,K)
    return answer

출처 : https://minnnne.tistory.com/4

Lessons learned

힙(heap)이 가장 유용한 경우는 전체를 정렬하는 것이 아니라 가장 큰 값(or 가장 작은 값) 몇개만 필요할 때인 것 같다. Heap에 대해 잘 설명된 블로그를 공유합니다~

• ratsgo님 블로그
• Dale Seo님 블로그
• 권희정님 블로그

이번 포스팅에서는 Anomaly Detection의 첫 방법론 소개로 Model-based Methods의 Isolation Forest에 대해 살펴보도록 하겠습니다.

Isolation Forest란?

1. 개념 및 가정

Isolation Forest는 Unsupervised Anomaly Detection 중 하나로 현재 갖고 있는 데이터 중 이상치를 탐지할 때 주로 사용됩니다. 이름에서 볼 수 있듯이 tree 기반으로 구현되는데, 랜덤으로 데이터를 split하여 모든 관측치를 고립시키며 구현됩니다.

특히, 변수가 많은 데이터에서도 효율적으로 작동할 수 있는 장점이 있습니다.

The term isolation means ‘separating an instance from the rest of the instances’.

Isolation Forest의 컨셉은 "각 관측치를 고립(=분리)시키기는 것은 이상치가 정상 데이터보다 쉽다."입니다.

위의 예제는 다음과 같이 해석됩니다. (1) 정상 데이터를 분리하는 경우, 약 7번의 split 필요 (2) 이상치를 분리하는 경우, 약 3번의 split 필요

2. 학습 방법

• 정상 데이터는 tree의 terminal node와 근접하며, 경로길이가 큼
• 이상치는 tree의 root node와 근접하며, 경로길이가 작음

랜덤포레스트가 의사결정나무를 여러번 반복하여 앙상블 하듯이, Isolation Forest는 _iTree_를 여러번 반복하여 앙상블 합니다.

iTree

1. Sub-sampling : 비복원 추출로 데이터 중 일부를 샘플링
2. 변수 선택 : 데이터 $$X$$의 변수 중 $$q$$를 랜덤 선택
3. split point 설정 : 변수 $$q$$의 범위(max~min) 중 uniform하게 split point를 선택
4. 1~3번 과정을 모든 관측치가 split 되거나, 임의의 split 횟수까지 반복(=재귀 나무)하며, 경로길이를 모두 저장

Isolation Forest 5. 1~4번 과정(iTree)을 여러번 반복

3. Scoring

$$ \Large\begin{aligned} s(x, n) = 2^{-\frac{E(h(x))}{c(n)}} \end{aligned} $$

• $$h(x)$$ : 해당 관측치의 경로길이
• $$E(h(x))$$ : 모든 iTree에서 해당 관측치에 대한 평균 경로길이
• $$c(n)$$ : $$h(x)$$를 nomalise하기 위한 값으로, $$iTree$$의 평균 경로 길이. (_iTree_는 _Binary Search Tree_와 동일한 구조이기 때문에, $$c(n)$$값을 쉽게 구한다고 함.)

$$E(h(x))$$에 따른 Score 값을 보면, 아래와 같습니다.

1. 관측치 x가 전체 경로길이의 평균과 유사(= 정상 데이터) : $$E(h(x)) → c(n)$$ , $$s → 0.5$$
2. 관측치 x가 이상치 : $$E(h(x)) → 0$$, $$s → 1$$
3. 관측치 x의 최대 경로길이 : $$E(h(x)) → n-1$$, $$s → 0$$

즉, Score는 0 ~ 1 사이에 분포되며, 1에 가까울 수록 이상치일 가능성이 크고 0.5 이하이면 정상데이터로 판단할 수 있습니다.

Summing up

• Unsupervised Anomaly Detection : Isolation Forest는 데이터에서 이상치를 탐지하기 위한 방법론입니다.
• Random Forest와 비슷하게 작동하며, 여러개의 _iTree_로 구성됩니다.
• 고차원 데이터에서도 작동할 수 있는 강점이 있습니다.

Reference

• Liu, F. T., Ting, K. M., & Zhou, Z. H. (2008, December). Isolation forest. In 2008 Eighth IEEE International Conference on Data Mining (pp. 413-422). IEEE.
• 김동화님 블로그(DSBA 연구실)
• 도도댕님 블로그
• Eryk Lewinson 블로그

Challenge

문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

입출력 예 설명 예제 #2

6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

Solution

1. On my own

def solution(priorities, location):
    """
    - param priorities : 문서의 중요도가 순서대로 담긴 배열 (List)
    - param location : 내가 인쇄를 요청한 문서의 위치 (Int)
    - return : 내가 인쇄를 요청한 문서의 인쇄 순위 (Int)
    """

    import collections

    prior_deque = collections.deque((i, p) for i, p in zip(range(len(priorities)), priorities))
    order = [0] * len(prior_deque)

    for i in range(len(prior_deque)) : 
        while True : 
            pr = prior_deque.popleft()
            max_pr = max(prior_deque, key = lambda x:x[1])
            if pr[1] < max_pr[1] : 
                prior_deque.append(pr)
            else : 
                break
        order[pr[0]] = i+1
        prior_deque.append((pr[0], 0))
    return order[location]

풀이 방법

1) 인쇄의 중요도와 위치가 동시에 저장될 수 있도록, 튜플형식의 deque 생성 2) 인쇄 목록의 첫번째 문서가 나머지 문서의 중요도보다 작으면, deque의 마지막으로 이동 3) 아니라면, order의 인쇄 위치에 맞게 순위 저장 4) 인쇄된 문서는 중요도를 0으로 변환

2. Best Code

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

풀이 방법 아이디어는 나와 비슷하나, any를 max대신으로 사용함. 모든 문서의 순위를 구하지 않고, location에 맞는 문서가 나오면 loop를 멈춤으로써 시간을 단축

Lessons learned

"스택/큐"의 마지막 문제였는데, 순서가 있는 배열에서는 collections.deque가 정말 편리한 것을 배웠다.

Challenge

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명 첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다. 두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다. 세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

Solution

1. On my own

def solution(progresses, speeds):
    """
    - param progresses : 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 (List)
    - param speeds : 각 작업의 개발 속도가 적힌 정수 배열 (List)
    - return : 각 배포마다 몇 개의 기능이 배포되는지 개수가 적힌 정수 배열 (List)
    """

    from math import ceil
    from collections import deque

    speeds = deque(s for s in speeds)
    answer = []

    while progresses : 
        cnt = ceil((100 - progresses[0])/speeds[0])
        progresses = deque(p + s*cnt for p, s in zip(progresses, speeds))

        tmp = 0

        while progresses[0] >= 100 : 
            tmp += 1
            progresses.popleft()
            speeds.popleft()

            if not progresses : 
                break;

        answer.append(tmp)

    return answer

풀이 방법

1) progresses의 첫 번째 작업이 끝나는 일자를 구한 뒤(→ cnt에 저장), 나머지 작업도 업데이트 한다. 2) while 조건문과 popleft를 통해 나머지 작업 중 같이 배포될 작업의 개수를 구한다. 3) 작업이 완료되지 않은 지점(100% 이하)에서 멈춘 뒤, 1~2번을 진행

2. Best Code

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

ceil(올림)을 쓰지 않기 위해, -((p-100)//s)로 구현한 부분과 Q[-1][0]<-((p-100)//s)을 통해, 이전에 진행된 날짜와 현재 작업이 더욱 진행해야할 날짜를 비교한 부분이 인상적임.

Lessons learned

deque의 편리함을 점점 깨닫고 있는 것 같다. 문제 풀 때 쉽게 풀려서 기분이 좋았는데, 고수의 코드를 보고 또 한 번 반성하고 나아갈 길이 더욱 많은거 같다!

Challenge

문제 설명 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한사항

• heights는 길이 2 이상 100 이하인 정수 배열입니다.
• 모든 탑의 높이는 1 이상 100 이하입니다.
• 신호를 수신하는 탑이 없으면 0으로 표시합니다.

입출력 예

입출력 예 설명 입출력 예 #2 [1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

입출력 예 #3 [1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다. [6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

Solution

1. On my own

def solution(heights):
    """
    - param heights : 맨 왼쪽부터 순서대로 탑의 높이 배열 (List)
    - return : 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열 (List)
    """
    from collections import deque

    answer = deque()
    heights = deque(h for h in heights)

    while heights : 
        top = heights.pop()
        left_len = len(heights)
        while left_len : 
            if heights[left_len -1] > top : 
                break
            else :
                left_len -= 1
        answer.appendleft(left_len)

    return list(answer)

풀이 방법 collections.deque를 생성후, pop을 통해 가장 오른쪽 탑과 나머지 탑을 역순으로 비교함.

2. Best Code

def solution(heights):
    answer = [0]*len(heights)
    stack = [] 

    for i in reversed(range(len(heights))):
        while stack and stack[-1][1] < heights[i]:
            idx, height = stack.pop()
            answer[idx] = i+1
        stack.append((i, heights[i]))
        print(stack)

    return answer

풀이 방법 대부분의 풀이를 보면 나처럼 heights의 가장 오른쪽 탑을 뽑아서 왼쪽으로 이동하며 비교하는데, 이 코드는 역발상으로 진행한다. 처음엔 잘 이해가 되지 않았는데, 직접 반복문을 하나씩 실행해보니 while문 안에서 오른쪽으로 이동한다.

Lessons learned

역으로 푸는 Best Code에 감탄하지만, 또 하나 알게된 점이 있다. while (stack and stack[-1][1] < heights[i]) 의 코드에서 stack = []인 상태에선 stack[-1][1]에서 오류가 날 줄 알았는데.. 안난다는 점이다. 알아보니, and 앞에 이미 False로 논리값이 들어갔기 때문에 and 뒤에는 실행이 안된다는 것이다!!! (나만 몰랐나..?? ㅎㅎ.. 갈길이 멀구만! )

Machine Learning(머신러닝)이란? Machine Learning의 역할은?

통계, 머신러닝(Machine Learning), 딥러닝(Deep Learning), 데이터 마이닝(Data Mining), Computer Science, 그로스해킹(Growth Hacking) 등등... 이 쪽 분야에서 흔히, 자주 등장하는 단어입니다. 저는 통계학을 전공지만, 위 분야들의 영역을 짓고 포함관계니, 어쩌니 저쩌니(Ex. 머신러닝 = 통계 + 데이터 마이닝 + Computer Science 이런식) 장황하게, 멋지게, 왈가왈부하는 것을 좋아하지 않습니다.

복잡한게 어려운 저에겐, 위의 많은 단어들은 결국 한 단어로 다음과 같이 표현할 수 있습니다.

"Data Driven Approaches"

예를 들어보자면, ** "A의 사람은 고양이를 좋아하고, B의 사람은 강아지를 좋아한다." ** 라는 문장을 아래의 그림을 보고 A/B에 어떤 말을 쓸 수 있을까요??

대부분의 사람들은 다음과 같이 대답합니다.

• "어른(A)은 고양이를 좋아하고, 아이(B)는 강아지를 좋아합니다."
• "여자(A)는 고양이를 좋아하고, 남자(B)는 강아지를 좋아합니다."
• "자연이 아닌 곳의 사람(A)은 고양이를 좋아하고, 자연이나 들판에 있는 사람(B)은 강아지를 좋아합니다."

하지만, Data Driven Approaches는 다음과 같이도 말할 수 있습니다. (물론, 눈치채신 분들도 계시겠지만..!!)

• "하얀옷을 입은 사람(A)은 고양이를 좋아하고, 색깔의 옷을 입은 사람(B)은 강아지를 좋아합니다"

머신러닝과 같이 데이터로부터 인사이트를 얻고자 하는 분야는, 우리가 생각하고 있는 관점 외에도 순수하게 데이터로만 볼 수 있는 새로운 관점을 제공할 때 가장 빛을 발하는 순간이라고 생각합니다.

Machine Learning 종류

본론으로 들어와, 머신러닝은 크게 3가지로 분류할 수 있습니다. 간혹, Semi-suprevised Learning을 포함할 때도 있지만 이번 포스팅에서는 소개하지 않겠습니다. 이번 포스팅에서는 간략한 설명만하고, 이 후 포스팅에서는 각각 자세한 내용과 논문을 통해 소개할 예정입니다.

1. Supervised Learning (지도학습)
2. Unsupervised Learning (비지도학습)
3. Reinforcement Learning (강화학습)

1. Supervised Learning (지도학습)

데이터에 Labeling이 되어 있는 상태로, 다시 말해 정답을 알려주며 학습시키는 것을 말합니다. 크게 종속변수가 연속형인 회귀(Regression)과 범주형인 분류(Classification)으로 나눌 수 있습니다.

2. Unsupervised Learing (비지도학습)

지도학습과는 달리 정답을 알려주지 않고 학습을 시키는 것으로, 데이터의 패턴이나 형태를 찾는 것을 말합니다. 비지도학습 중 가장 대표적인 분야는 유사한 데이터끼리 그룹핑을 하는 군집화(Clustering)과 고차원의 데이터를 저차원으로 줄이는 차원 축소(Dimension Reduction)이 있습니다.

3. Reinforcement Learning (강화학습)

강화학습은 시행착오를 통해 반복적으로 환경(environment)과 상호작용함으로써, 스스로 과제를 수행하는 방법을 배우는 것을 말합니다. 보상(Reward)이라는 개념을 최대화하는 방향으로 정책을 수정하고 행동하면서, 최적의 정책을 찾을 때 까지 반복 학습을 하는 것입니다.

머신러닝을 위의 3가지로 분류했지만, 각각의 방법론은 독립적이지만은 않습니다. 비지도학습이 지도학습의 중간 과정으로 활용될 수도 있고, 지도학습 문제를 군집화로도 풀 수 있습니다.

Anomaly Detection(이상치 탐지)란?

Anomaly Detection(이상치 탐지)란, 데이터 안에서 anomaly, outlier, abnormal과 같이 예상하지 못한 패턴을 찾는 일련의 활동을 말합니다.

이번 포스트는 Anomaly Detection에 대한 첫 시작이기 때문에, 자세한 내용보다는 다음의 구성에 대한 개요 정도만 소개하려합니다.

1. Anomaly Detection 적용 분야
2. Anomaly Detection 종류
3. Anomaly Detection 방법론

Anomaly Detection 적용 분야

• Fraud Detection System (이상 거래 탐지) : 신용, 카드, 보험과 같은 금융계에서 불법 및 악용 사례를 탐지
• Intrusion Detection System (침입 탐지 시스템) : 컴퓨터 또는 네트워크 시스템에 대한 원치 않는 조작을 탐지
• Predictive Maintenance (설비 예지 보전) : 설비가 고장나기 전, 이상 신호를 탐지
• Customer Churn (고객 이탈) : 제품 또는 서비스에서 구매와 사용을 중지하는 고객을 분석하는 분야

위의 사례들을 보면, 이벤트 사건이 정상 데이터에 비해 적은 것을 보실 수 있습니다. (Ex. 카드 거래 내역 중 대부분의 고객은 정상 거래를 하기 때문에, 이상 거래 내역이 매우 적음) 여기서, Anomaly Detection의 목적을 엿볼 수 있는데, 매우 많은 정상 데이터에서 극소수의 비정상 데이터를 구별하는 것이라 할 수 있습니다.

Anomaly Detection 종류

Anomaly Detection은 학습데이터에 따라 다음과 같이 3개로 볼 수 있습니다.

1. Supervised Anomaly Detection
2. Semi-supervised Anomaly Detection
3. Unsupervised Anomaly Detection

1. Supervised Anomaly Detection

학습 데이터에 비정상 데이터와 정상 데이터의 Label이 모두 존재했을 때의 경우를 말합니다. Classification의 관점으로도 볼 수 있는데, 이 경우 비정상 데이터가 매우 적기 때문에 Class Imbalanced Problem(데이터 불균형 문제)의 가능성이 있습니다. Supervised Learning의 장점인 모델 성능 평가가 가능하다는 점에서 직관적일 수 있지만, 척도 선정에 주의해야합니다. 예를 들어 데이터의 99%가 정상일 때, 모든 데이터를 정상이라고 예측하게 되면 정확도가 99%이기 때문에 마치 성능이 좋은 것 같아 보이지만, 비정상 데이터를 모두 정상이라고 예측했기 때문에 Recall과 Sensitivity관점에서는 좋은 성능이 아닙니다.

2. Semi-supervised Anomaly Detection

Semi-supervised Anomaly Detection은 정상 데이터만을 가지고 학습한 경우를 말합니다. 현재 갖고 있는 데이터가 모두 정상 데이터이지만, 미래의 이상 징후를 탐지하고 싶은 경우에 적절합니다. 정상 데이터의 특징만을 학습해서 비정상 데이터가 테스트로 입력되었을 때, 정상 특징과 부합하지 않아 이상 징후를 탐지하는 컨셉입니다.

3. Unsupervised Anomaly Detection

학습 데이터에 정상, 비정상 데이터의 Labeling이 안 된 경우를 말합니다. 즉, 데이터에 대한 가정이 없을 경우로서 모든 데이터를 활용하여 학습을 하긴 하지만, 모델링 후 정상/비정상에 대한 구분이 필요할 수 있습니다. 적합이 잘 된다면 정상/비정상 데이터의 모델링 후 분포가 이질적으로 나타날 수 있습니다.

Anomaly Detection 방법론

정확한 기준으로는 나눌 순 없지만, 제 나름대로 아래와 같이 분류해보았습니다. 이번 포스팅에서는 간략한 설명만 하고, 이후 포스팅에서는 각각 자세한 내용과 논문을 통해 소개하도록 하겠습니다.

1. Model-based Methods
2. Density/Distance-based Methods
3. Reconstruction-based Methods

1. Model-based Methods

• Isolation Forest : Tree based method로서 데이터를 분할 및 고립시켜 이상치를 탐지
• 1-class SVM : 데이터가 존재하는 영역을 정의하여, 영역 밖의 데이터들은 이상치로 간주

2. Density/Distance-based Methods

• Gaussian Mixture Model
• k-Nearest Neighbours (kNN) method
• LOF(Local Outlier Factors) : 데이터의 밀도 또는 거리 척도를 통해, majority 군집과 minority 군집을 생성하여 이상치를 탐지

3. Reconstruction-based Methods

• PCA(Principal Component Analysis) Method
• Auto-Encoder based Method : 고차원 데이터에서 주로 사용하는 방법론으로서 데이터를 압축/복원하여 복원된 정도로 이상치를 판단

위의 방법론 외에도 Deep Learning을 기반으로 한 Anomaly Detection 연구가 활발히 진행되고 있으며, 적은 비정상 데이터를 증강시킬 수 있는 방향으로도 학계에서는 많은 관심을 기울이고 있습니다.

Refernece

• 이호성님 블로그(수아랩)
• 김기현님 블로그(마키나락스)
• 김동화님 블로그(DSBA 연구실)
• Chandola, V., Banerjee, A., & Kumar, V. (2009). Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3), 1-58.
• Chalapathy, R., & Chawla, S. (2019). Deep learning for anomaly detection: A survey. arXiv preprint arXiv:1901.03407.
• Xu, X., Liu, H., & Yao, M. (2019). Recent progress of anomaly detection. Complexity, 2019.

Challenge

문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한사항

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

Solution

1. On my own

def solution(bridge_length, weight, truck_weights):
    """ 
    - param bridge_lengths : 다리 길이 (int)
    - param weight : 다리가 견딜 수 있는 무게 (int)
    - param truck_weights : 트럭별 무게 (list)
    - return : 모든 트럭이 다리를 건너는 시간 (int)
    """
    import collections

    time = 0
    on_weight = 0
    on_bridge = collections.deque([0] * bridge_length)
    truck_weights = collections.deque(t for t in truck_weights)


    while truck_weights : 
        time += 1

        on_weight -= on_bridge.popleft()
        if (on_weight + truck_weights[0]) <= weight : 
            truck = truck_weights.popleft()
            on_weight += truck
            on_bridge.append(truck)            
        else : 
            on_bridge.append(0)

    return time + bridge_length

풀이 방법 collections.deque를 이용하여, 매 시간마다 다리와 대기트럭의 시뮬레이션을 재현함. 마지막 트럭이 다리에 올라가면(= 대기트럭이 없으면), 시뮬레이션을 멈추고, time + bridge_length를 통해 마지막 트럭 건너는 시간까지 구할 수 있음.

2. Best Code

import collections

DUMMY_TRUCK = 0

class Bridge(object):

    def __init__(self, length, weight):
        self._max_length = length
        self._max_weight = weight
        self._queue = collections.deque()
        self._current_weight = 0

    def push(self, truck):
        next_weight = self._current_weight + truck
        if next_weight <= self._max_weight and len(self._queue) < self._max_length:
            self._queue.append(truck)
            self._current_weight = next_weight
            return True
        else:
            return False

    def pop(self):
        item = self._queue.popleft()
        self._current_weight -= item
        return item

    def __len__(self):
        return len(self._queue)

    def __repr__(self):
        return 'Bridge({}/{} : [{}])'.format(self._current_weight, self._max_weight, list(self._queue))


def solution(bridge_length, weight, truck_weights):
    bridge = Bridge(bridge_length, weight)
    trucks = collections.deque(w for w in truck_weights)

    for _ in range(bridge_length):
        bridge.push(DUMMY_TRUCK)

    count = 0
    while trucks:
        bridge.pop()

        if bridge.push(trucks[0]):
            trucks.popleft()
        else:
            bridge.push(DUMMY_TRUCK)

        count += 1

    while bridge:
        bridge.pop()
        count += 1

    return count


def main():
    print(solution(2, 10, [7, 4, 5, 6]), 8)
    print(solution(100, 100, [10]), 101)
    print(solution(100, 100, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]), 110)


if __name__ == '__main__':
    main()

풀이 방법 class를 통해, 문제에 맞게 정교한 pop과 push를 만들어 사용함.

Lessons learned

문제를 풀다보니, collections.deque.popleft()를 활용하는 것이 queue.pop(0)보다 시간 복잡도가 적은 것을 알게 되었고, 이전 포스트에서도 보았지만, class를 잘 활용한 2. Best Code 코드는 정말 멋진 것 같다. 더 연습해서 나도 코딩 고수가 되야지 :)

Challenge

문제 설명 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

입출력 예 설명 classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

Solution

1. On my own

def solution(genres, plays):
    """
    - param genres : 노래의 장르를 나타내는 문자열 배열 (list)
    - param plays : 노래별 재생 횟수를 나타내는 정수 배열 (list)
    - return : 노래의 고유 번호를 순서 (list)
    """
    genre_dict = {}
    for g, p in zip(genres, plays) : 
        if g not in genre_dict.keys() : 
            genre_dict[g] = p
        else : 
            genre_dict[g] += p
    genre_list = sorted(genre_dict.items(), key = (lambda x: x[1]), reverse = True)

    answer = []
    for g, p in genre_list : 
        genre_idx = [i for i in range(len(genres)) if g == genres[i]]
        genre_play = [plays[p] for p in genre_idx]
        play_list = dict(zip(genre_idx, genre_play))
        play_list = sorted(play_list.items(), key = (lambda x: x[1]), reverse = True)
        answer.append(play_list[0][0])
        if len(play_list) >= 2 : 
            answer.append(play_list[1][0])

    return answer

풀이 방법

1) genre별 재생된 횟수를 구한 뒤,genre를 내림차순으로 정열 2) genre의 index를 저장한 뒤, dictionary로 만든 후, play를 통해 내림차순으로 정열 3) genre내의 1, 2순위를 가져오는데, 한 장르에 노래가 한 곡만 있을 수 있으니, 예외처리를 위한 if문 작성

2. Best Code(1)

def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
    genreSort =sorted(list(d.keys()), key= lambda x: sum(map(lambda y: y[0], d[x])), reverse = True)
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
    return answer

풀이 방법 lambda 함수를 잘 사용한 예시 lambda 함수 내부의 x, y에 대한 이해와 x: (x[0], -x[1])를 이용한 정열 아이디어가 돋보임.

2. Best Code(2)

def solution(genres, plays):
    answer = []
    dic = {}
    album_list = []
    for i in range(len(genres)):
        dic[genres[i]] = dic.get(genres[i], 0) + plays[i]
        album_list.append(album(genres[i], plays[i], i))

    dic = sorted(dic.items(), key=lambda dic:dic[1], reverse=True)
    album_list = sorted(album_list, reverse=True)



    while len(dic) > 0:
        play_genre = dic.pop(0)
        print(play_genre)
        cnt = 0;
        for ab in album_list:
            if play_genre[0] == ab.genre:
                answer.append(ab.track)
                cnt += 1
            if cnt == 2:
                break

    return answer

class album:
    def __init__(self, genre, play, track):
        self.genre = genre
        self.play = play
        self.track = track

    def __lt__(self, other):
        return self.play < other.play
    def __le__(self, other):
        return self.play <= other.play
    def __gt__(self, other):
        return self.play > other.play
    def __ge__(self, other):
        return self.play >= other.play
    def __eq__(self, other):
        return self.play == other.play
    def __ne__(self, other):
        return self.play != other.play

풀이 방법 dict.get메서드와 class사용이 인상적 dict.get : 키(key)가 없으면, default값을 지정하는 메서드 dictionary는 "키(key)-값(value)"의 쌍으로 이루어져 있지만, class를 이용해 "genre-play-track"의 세개의 쌍으로 이용함.

Lessons learned

dictionary의 장점을 점점 잘 받아들이고 있는거 같다. class를 이용한 3. Best Code(2)도 잘 기억해놨다가, 사용하면 좋을 것 같다.