최단 경로 알고리즘

• 가장 짧은 경로를 찾는 것
  • 한 지점 → 한 지점
  • 한 지점 → 모든 지점
  • 모든 지점 → 모든 지점
• 지점 = 노드 (예. 마을, 국가 등..)
• 이동 가능함 = 간선으로 표시

다익스트라 최단 경로 알고리즘

• 특정 한 노드 → 다른 모든 노드 계산
• 그리디 알고리즘으로 가장 비용이 적은 노드 선택
• 동작 과정
  • 출발 노드 설정
  • 최단 거리 테이블 초기화 (자신의 노드 = 0, 그 외 노드 거리 = $\infty$)
  • 방문하지 않은 노드에서 최단 거리가 가장 짧은 노드 선택하고 다른 노드로 가는 비용 계산하는 과정 반복
    • 동일 비용을 갖는 경우 더 작은 수를 갖는 노드부터 우선 계산
    • 마지막 노드 정보를 처리하지 않아도 상관없음 (이전의 정보를 활용하여 이미 가장 짧은 노드의 거리를 갱신했기 때문)
• 처리 과정 중 더 짧은 노드가 존재하면 해당 노드를 최단 거리 노드로 갱신
• 한 번 처리된 노드의 최단 거리는 고정 → 변화 없음
• 노드 탐색 시 BFS 이용하는 알고리즘

우선순위 큐

• 우선순위가 높은 데이터를 먼저 삭제
• 힙 (최소 힙, 최대 힙)
• 다익스트라 알고리즘에서 사용됨. (시간을 개선시키기 위함)
• 파이썬: heapq 라이브러리 사용 가능 (min heap 사용) ⇒ 다익스트라 알고리즘에서 사용됨.

— 참고: 파이썬 알고리즘 인터뷰 책 & 이코테 2021 강의

TIL Algorithm study

• DFS & BFS

스택 & 큐

1. Stack

   선입후출 형식
   삽입-삭제 방식 사용

2. Queue

   선입선출 형식
   삽입-삭제 방식 사용
   예. 은행의 창구 대기열
   python from collections import deque 라이브러리 사용

재귀함수 (Recursion)

최대 재귀 깊이 설정 미리 필요함(종료조건) => 무한 호출 가능성
스택 방식 사용하여 스택 대신 사용
예. 팩토리얼 계산
예. 유클리드 호제법- 최대공약수 계산

R = A % B; GCD(A, B) = GCD(B, R)
복잡한 알고리즘 혹은 반복문 사용을 간결하게 하여 시간의 효율성 보장

DFS & BFS

1. DFS(Depth-First Search)

   깊이 우선 탐색
   스택/재귀함수 구조 사용
   시작노드부터 스택 삽입 후 방문 처리

2. BFS(Breadth-First Search)

   너비 우선 탐색
   큐 자료 구조 사용
   방무 노드를 미리 방문 처리 후 방문하지 않은 노드를 삽입, 방문 처리

TIL

• 알고리즘 문제 풀이 (백준/프로그래머스)
  —> 코테 대비 프로그래머스 문제 1~2개씩 풀기 (매일!!)

TIL

오랜만에 돌아온 TIL 시리즈
공부 뭘 했는지 기록하기 위한 나의 개인 기록 포스트

• LG Aimers part.1에 해당하는 ch.1~2 강의 다시 듣고 복습하기
• 패캠 코테 준비 강의 (탐색 알고리즘까지 마무리)
  • 백준 연습문제 풀이
• 랭디 중국어 수업

Start studying new computer language, JAVA.
— watched online lecture (FAST CAMPUS): 한 번에 끝내는 코딩테스트 369 초격차 패키지 Online

• How to install JAVA on Jupyter notebook
• JAVA data structures: Array

Array data type

• use index number
• declare using []: empty array
• fixed length of one array
• print() in python = System.out.printin();
• print total array: Array.toString()
• 1,2,3-D arrays available

Thinking note (생각노트)

이 블로그 포스트로 내 의식의 흐름(??)대로 생각을 적어보려고 한다.

거의 두 달만에 올리게 되는 것 같다. 그 동안 많은 일들이 있었고 나의 심경 또한 변화하기도 했다..
슬픔, 기회는 어느 한 순간에 찾아오는 것 같다. 내가 살고 있는 지금 이 순간들을 한번씩 돌아보면서 생각해보게 되는 것 같다.

내가 잘할 수 있는 일이 무엇인지, 좋아하는 게 무엇인지 계속해서 고민해보고 있고 내가 순간순간을 잘 보내고 있는지도 문득 돌아보게 된다. 슬픔 그리고 행복 이 두 가지들이 나의 감정을 왔다갔다하게 만든다.

아직까지 안정되지 못한 현재 나의 모습에 때로는 불안감을 느끼기도 한다. 이 불안감이 나를 더욱 불안하게 만든다. 이 이틀 동안 꾼 꿈들은 해몽은 너무 좋은데 해몽한 대로 좋은 소식이 나를 기다리고 있을 지 의문이 든다. 불안감 때문에 더 그런 것 같다. 계속해서 이메일, 홈페이지, 그리고 휴대폰을 매일 매 시간마다 들여다보며 혹시 연락이 없는 지 계속해서 보게 된다.. 내가 기회를 놓치지 않으려고 잡았는데 그 기회가 나를 놓는 것은 아닌지..

괜찮을 거야라고 나 자신을 다독여보기는 하지만 마음 한 편에서는 왜 자꾸만 불편한 느낌이 드는 걸까. 내 노력들이 부족한 건지도 어쩌면 내가 너무 안일하게 생각했던 것은 아닐까. 나 나름대로 잘 해오고 있다라고 느끼면서도 다시 돌아보면 또 그렇지도 않은 것 같아 보인다.

나는 과연 나 자신을 신뢰하고 있는 걸까? 내 삶은 지금 얼마나 가치가 있는가?

“ 사람이 온다는 것은
사실은 어마어마한 일이다.
그는
그의 과거와
현재와
그리고
그의 미래와 함께 오기 때문이다.
한 사람의 일생이 오기 때문이다.”
[[방문객 by. 정현종]]

프로젝트가 거의 마무리 되어가고 있다. 마무리 되어가고 있는 현 시점에서 한 번 짚고 넘어갈만한 부분을 정리해볼까 싶다.

• SMOTE로 불균형 처리된 데이터로 학습을 시키면 확실히 성능이 올라가는 것을 볼 수 있다.
• 현재 이용하고 있는 데이터 자체가 불균형이 상당히 심해서 불균형 처리를 하지 않으면 성능이 상당히 낮게 나온다.
• 검증데이터에 한해서 불균형 처리를 하면 성능은 괜찮은데 테스트 데이터는 음…
• FM model 성능이 autoencoder model 보다 좀 괜찮게 나온다. (논문에서는 오토인코더가 괜찮다고 했던 것 같은데 데이터 문제로 성능이 차이가 있는 것처럼 보여진다.)

Today’s feedback:

• 오토인코더 성능을 좋게 할 수 있는 방법은? 오토인코더 중에서 좋은 성능을 가진 모델은 무엇인가?
  • 하이퍼 파라미터 튜닝 = latent feature 수, epoch 수를 늘리는 것.
  • 코드가 잘못 ⇒ accuracy 0 (다 맞는데 라벨을 잘못.)
  • 0.5보다 낮으면 코드가 틀렸을 경우 혹은 major class를 못 맞추는 경우
  • classification report에서 잘못된 게 있는지, overfitting의 가능성이 높음
  • 드롭아웃으로 학습이 안되었을 때에도 존재하지만 성능이 완전 나쁠 수는 없음.
  • 심한 드롭아웃을 하더라도 output은 랜덤샘플링에 가까운 것으로 나와야 함. (0.5에 근사하게.)
  • 성능이 0 = 결과 계산부분에서 이슈가 있을 수 있으므로 확인 필요함.
  • data 분포에 상황에 따라 다름. convolutional & denoising autoencoder가 부수적으로..
• 불균형 데이터를 처리하고 나서 딥러닝 모델의 성능이 나빠질 수 있는 경우 존재??
  • 가능함.
  • 확인 사항: 오토인코더의 성능(latent feature이 좋은지 - 오토인코더 l2 loss 먼저 확인)과 upsampling의 영향이 충분했는가 (분류성능에서는 좋지 않음. upsampling 먼저 → test 성능 확인 먼저, stratify 비율을 가지고 확인, 학습에서는 upsampling ⇒ 최종에서는 원본 데이터 셋으로)
• 오토 인코더에서 dense unit값이 늘어나면 성능이 나빠질 수도 있는지 여부
  • 오토인코더의 학습 먼저 확인 → l2 loss가 낮아지도록 하는 방향 → decode → 학습을 다시 (따로 학습)
  • 일반적으로 latent layer를 늘리거나 하지 않음.

성능 문제 (낮은 accuracy 문제) 해결!!

작년부터 계획했던 것들이 약간씩 뒤틀리게 되면서 뭔가 혼란스럽기도 하고 계획했던 것들을 꼭 이뤄야만 한다고 생각해서인지 이렇게 포기해도 되는 건가 싶다. 뭔지 모르는 두려움? 같은 감정이 밀려온다..

올해는 좋은 일만 가득하길.. 좋은 일들만 가득하길 바란다.

지금 하고 있는 모든 것들이 나에게는 좋은 결과를 가져올 것이라 생각한다. 결과가 의미있는 것이 훨씬 더 중요하니까.

올해는 내 소망했던 많은 것들을 이룰 수 있기를!!

• 기존의 코드를 확인해서 그대로 사용가능하고 문제가 있는 경우 코드 수정이 필요. stack of flow
• 빠르게 오픈소스 코드를 가지고 와서 구현할 수 있는지
• 새로 나오는 딥러닝에 관한 논문들을 보고 바로바로 이해할 수 있고 코드로 구현할 수 있는가 (수준이 높음)
• 딥러닝/머신러닝의 차이 = feature extraction (딥러닝이 알아서 줄여줌 = embedding)
  • fully connected layer: 고차원 → 저차원으로…
  • input vector ⇒ linear classifier로 변경
  • 학습이 잘 되는 vector = 0,1로 잘 구분된 것.
  • model capacity가 크다 = 딥러닝
  • 딥러닝은 feature vector가 많음 (고차원)
  • class imbalanced ⇒ 모델 자체로는 학습하기 어려운 상태이므로 minority class를 어느 정도 보완해줘야 함. (일반적으로 배너광고를 잘 클릭하지 않음. = 극심한 class imbalanced의 상태)

Split columns in data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

cols = {'obj': [],
        'cat': [],
       'cont': []
        }

def data_split():
    file_name = 'final_data_v2.csv'
    file_path = os.getcwd()+'/drive/MyDrive/Colab Notebooks/' #[:-16]는 본인 경로에 맞게 있어도 되고 없어도 됨.
    df = pd.read_csv(file_path+file_name, encoding='utf-8')

    # 데이터 유형별 분류하기
    for dt_idx, dt_val in zip(df.dtypes.index, df.dtypes.values):
        if 'category' in dt_idx:
            df[['category1']] = LabelEncoder().fit_transform(df[['category_id_1']])
            cols['cat'].append('category1')

        if dt_val == 'object':
            if ('id' in dt_idx) | ('time' in dt_idx) | ('name' in dt_idx) | ('keyword' in dt_idx) |('url' in dt_idx):
                df.drop(columns = dt_idx, axis=1, inplace=True)
            else:
                cols['obj'].append(dt_idx)

        else:
            if ('id' in dt_idx) | ('time' in dt_idx):
                df.drop(columns = dt_idx, axis=1, inplace=True)
            else:
                if len(df[dt_idx].value_counts()) <= 30: #연속형 데이터 중 30개 내의 범주로 나눌 수 있는 데이터 = category로 구분.
                    cols['cat'].append(dt_idx)
                else:
                    if ('hour' in dt_idx) | ('group' in dt_idx):
                        pass
                    else:
                        cols['cont'].append(dt_idx) 

    return cols

# using splited columns, make new data frame
def reorganization(df):
  data = pd.DataFrame()
  cols = data_split()
  for k, v in cols.items():
    for v in cols[k]:
      if v in df.columns:
        data[v] = df[c]
      else:
        pass

  return data

# preprocessing data
def preprocessing(data, cols):
    # 데이터 유형별 분류하기
    data = reorganization(df)
    modified_df = pd.DataFrame()
    vec_dict = {idx: [] for idx in range(len(data.columns))}
    feature_index = []

    for i, c in enumerate(data.columns):
        if c in cols['obj']:
            obj_data = pd.get_dummies(data[c], prefix=c, prefix_sep = "/")
            modified_df = pd.concat([modified_df, obj_data], axis=1)
            vec_dict[i] = list(obj_data.columns)
            feature_index.extend(repeat(i, obj_data.shape[1]))

        elif c in cols['cat']:  # click_label 컬럼 = y 변수로 사용
            if 'click' in c:
                pass
            else:
                cat_data = pd.get_dummies(data[c], prefix=c, prefix_sep = "/")
                vec_dict[i] = list(cat_data.columns)
                feature_index.extend(repeat(i, cat_data.shape[1]))
                modified_df = pd.concat([modified_df, cat_data], axis=1)
        else:
            scaled_num_data = MinMaxScaler().fit_transform(df[v])
            scaled_num_data = pd.DataFrame(scaled_num_data, columns = v)
            modified_df[v] = scaled_num_data
            vec_dict[i] = list(scaled_num_data.columns)
            feature_index.extend(repeat(i, scaled_num_data.shape[1]))

    print('---- Data info ----')
    print(cols)
    print('Data Frame shape: {}'.format(data.shape))
    print('# of Feature: {}'.format(len(feature_index)))
    print(f'# of Field: {len(vec_dict)}')
    print(f'Modified DF columns: {data.columns}')
    return vec_dict, feature_index, modified_df

매일 매일 프로젝트와 관련된 내용들이 주를 이루다보니 소재가 고갈되고 있는 기분이다. (나는 누구? 여긴 어디?… (?????))

오늘 DeepFM 모델링하다가 전처리에서 코드가 자꾸 오류가 나고 진도도 나가지 못한채 막혀서 짜증이 났다. 논문 내용을 참고해서 다른 블로그 등에서 다른 사람들이 만들어 놓은 코드들을 가지고 활용해서 하다보니 시간도 오래 걸리고 이렇게 막혀버리니 답답하기도 하고…

제대로 하고 있는 것 같은데 왜 안되는지… 주말을 활용해서라도 마무리 해야지..

나를 위한 것이라고 생각하면 지금 하는 것들이 고통스럽더라도 유의미한 일이 아닐까…

올해는 모든 것이 잘되기를… 내가 이루고자 하는 모든 것들을 이룰 수 있기를…

I uploaded the most of posts regarding the project so far, so today’s post is about what I did today.

• 早上： did yoga
• 安排今天的计划
• 晚上： 运动（55分钟）
• 学习中文 （跟着说短的新闻报道和书写练习）
• did the project with a company: DeepFM modeling python codes

明天再见！！

• citation of a journal (originate from): Guo, H., TANG, R., Ye, Y., Li, Z., & He, X. (2017). DeepFM: A factorization-machine based neural network for CTR prediction. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. https://doi.org/10.24963/ijcai.2017/239

DeepFM modeling

DeepFM의 구성: FM component + deep component

$\langle FM component \rangle $

피쳐 = i일 때,

• 스칼라 값 $w_i$ = order-1 중요도 가중치
• 잠재 벡터(latent vector) $V_i$ = 다른 피쳐와 상호작용 정도를 측정
• $V_i$ (잠재 벡터): order-2 상호작용을 모델링을 위한 FM component & 높은 차원의 피쳐 상호작용을 모델링을 위해 Deep Component에 포함.
• $w_i$ 와 $V_i$ & 이 외의 포함한 모든 변수 -> 결합된 예측 모델에서 학습.
• order-2 (FM 모델 쌍별 피쳐의 상호작용은 각각의 피쳐의 잠재 벡터들 간의 내적곱으로 되어 있음. & 데이터 셋이 매우 sparse(드문 드문하게 퍼져있는 형태)일 때 훨씬 더 효과적으로 나타낼 수 있음.
• FM model: 피쳐 i가 데이터에 있을 때마다 잠재 벡터 $V_i$를 훈련시킬 수 있음.

$\langle formula \rangle $

1. $\hat{y}(x) := w_0 + \sum^n_{i=1}w_i x_i + \sum^n_{i=1}\sum^n_{j=i+1} \langle{v_i,v_j}\rangle x_ix_j = \langle{v_i,v_j}\rangle + \sum^n_{i=1}\sum^n_{j=i+1} \langle{v_i,v_j}\rangle x_ix_j $
2. $\langle{v_i,v_j}\rangle := \sum^k_{f=1}v_{i,f} \cdot v_{j,f}$
3. $\hat{y} = sigmoid(y_{FM} + y_{DNN})\label{1}$

• $\langle{v_i,v_j}\rangle$: order-1 피쳐들의 중요성을 반영.
• $\sum^n_{i=1}\sum^n_{j=i+1} \langle{v_i,v_j}\rangle x_ix_j $: order-2 피쳐 상호작용의 영향력을 나타냄.

• The following code is based on python:

  • This code is for preprocessing code of DeepFM modeling to predict CTR.
  • X feature of Deep FM model = various fields (nominal, continuous variables) with n-dimensional vector
  • Y feature of Deep FM model = 0, 1 labels (whether the user clicked or not)
  • nominal field => one-hot encoding vector
  • continuous field => the value as it is, or discretization (change into categorical data) then one-hot vectorization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# preprocessing code
cols = {'obj': [],
        'cat': [],
       'cont': []
        }
file_name = 'final_data.csv'
file_path = os.getcwd()[:-16]+'data\\' #[:-16]는 본인 경로에 맞게 있어도 되고 없어도 됨.
df = pd.read_csv(file_path+file_name, encoding='utf-8')

def preprocessing(df):
    # 데이터 유형별 분류하기
    for dt_idx, dt_val in zip(df.dtypes.index, df.dtypes.values):
        if 'category' in dt_idx:
            df[['goods_cat']] = LabelEncoder().fit_transform(df[['category_id_1']])
        
        if dt_val == 'object':
            if ('id' in dt_idx) | ('time' in dt_idx) | ('name' in dt_idx) | ('keyword' in dt_idx) |('url' in dt_idx):
                df.drop(columns = dt_idx, axis=1, inplace=True)
            else:
                cols['obj'].append(dt_idx)

        else:
            if ('id' in dt_idx) | ('time' in dt_idx):
                df.drop(columns = dt_idx, axis=1, inplace=True)
            else:
                if len(df[dt_idx].value_counts()) <= 5: #연속형 데이터 중 5개 내의 범주로 나눌 수 있는 데이터 = category로 구분.
                    cols['cat'].append(dt_idx)
                else:
                    if ('hour' in dt_idx) | ('group' in dt_idx):
                        pass
                    else:
                        cols['cont'].append(dt_idx) 
                 
    for k, v in cols.items(): # 컬럼 전처리 (스케일링, 원핫인코딩)
        if k == 'obj':
            obj_data = pd.get_dummies(df[v], drop_first = True)
            df = pd.concat([df, obj_data], axis=1).drop(columns = v, axis=1)

        
        elif k == 'cont':
            num_data = RobustScaler().fit_transform(df[v])
            num_data = pd.DataFrame(num_data, columns = v)
            df[v] = num_data
        
            print('---- Data info ----')
            print('X shape: {}'.format(df.shape))
            print('# of Feature: {}'.format(len(df.columns)))
            return df
    
df = preprocessing(df)
df.head(3)

Finding the outliers — isolation forest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# GridSearchCV(모델, param_grid, cv, scoring, n_jobs, verbose)
from sklearn.ensemble import IsolationForest
param_grid = {
    'n_estimators':[50, 100, 150],
    'max_samples':[50, 100, 150, 200],
    'contamination':[float(0.004), float(0.1), float(0.5), 'auto']
}

# 전처리를 거친 x_train으로 grid search cross validation 수행
grid_search = GridSearchCV(IsolationForest(max_features=1.0, bootstrap=False, random_state=42,), 
			   param_grid=param_grid, cv=10, n_jobs=-1, verbose=0, scoring = 'accuracy')
grid_search.fit(dataset)

# 가장 좋은 성능을 보인 파라미터 조합의 estimator을 model에 저장
model = grid_search.best_estimator_

# dataset 데이터를 예측 및 성능 평가
data_pred = model.predict(dataset)

#이상치 값 개수
-data_pred[data_pred == -1].sum()  #1038개

## 그리드 서치 결과
# IsolationForest(contamination=0.004, max_samples=50, n_estimators=50, random_state=42)

Filling with the values using KNN imputer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from sklearn.impute import KNNImputer
param_grid = [
    {'n_neighbors': range(3, 11, 2)}
]

imputer = KNNImputer(missing_values=np.nan, add_indicator=True)
gs = GridSearchCV(imputer, param_grid = param_grid, 
		  cv=10, n_jobs = -1, scoring = 'f1')
gs.fit(df)

# 가장 좋은 성능을 보인 파라미터 조합의 estimator을 model에 저장
model = gs.best_estimator_

#f1 scoring일 때 최적 모델 값
KNNImputer(add_indicator=True, n_neighbors=3)

## imputer 결과(f1 score)
# KNNImputer(add_indicator=True, n_neighbors=3)

# f1 score일 때 결측값 채운 부분 확인하기
df[(df.category_id_1 == 0)]

• 모델링을 할 때 데이터 양이 많으면 시간이 오래 걸림 (2~3시간 기본)
• 구글 코랩에서 GPU로 돌려도 마찬가지 (딥러닝이 아니면 GPU로 잘 안돌아감.)