나를 잃지 말자

가장 기본적인 clustering algorithm, unsupervised.

k는 cluster의 개수를 나타낸다.(hyperparameter)

최적의 k개의 centroids를 찾는 것이 알고리즘의 목표

알고리즘:

Assignment-step과 Update-step으로 나뉘어져있다.

각 data마다 가장 가까운 centroid을 갖는 cluster로 assign

위의 loop를 다 돌면 centroid를 해당 cluster내의 point average를 통해 update

위 2과정을 반복 후 converge하면 알고리즘 종료

특징:

Optimum으로 convergence가 보장되어 있지 않다.

L2 distance가 아닌 distance는 더 converge가 보장 안된다.

->data의 scatter가 Sphere모양이 아닌 경우에는 clustering이 잘 되지 않는다. 

->이 때는 DBSCAN을 사용하자.(DBSCAN은 다음에 알아보자.)

NP-hard for any k >= 2

복잡도가 O(n^(dk+1)), where n:데이터 개수, d:데이터 차원, k:cluster개수

->따라서 변형인 Lloyd's algorithm을 대개 사용한다. (이는 다음에 알아보자.)

metric:

clustering이 얼마나 잘됐나 평가하는 데에 있어 

각 클러스터 내의 data가 해당 centroid까지의 distance,

그리고 이를 전체 data에 대해 평균내린 값을 metric으로 잡아 사용(낮을 수록 좋은)

이러한 metric을 average diameter라 한다.

최적의 k찾기:

average diameter가 k가 클수록 낮아지는 경향이 있다. 이 때 낮아지는 "폭이" 줄어들 때의 k를 최적의 k로 택한다.

참고자료:

en.wikipedia.org/wiki/K-means_clustering

www.secmem.org/blog/2019/05/17/clustering/

RMSE(Root Mean Squared Error)로 Rating prediction 성능을 평가하는 것은

실제로 추천 시스템의 역량을 평가하는 것인지 다시 한번 생각해볼 필요가 있다.

우리는 Top-N recommendation을 통해 좀 더 user-focused metric을 가질 필요가 있다.

내가 사용자로서 추천 시스템이 내가 어떤 영화를 rating을 얼마나 줄 지 알아맞춰주기 보다는

내가 필요로 하는 상품이 상단에 나와주면 되는 것이다.

따라서 다양한 평가 지표 중에 RMSE에 너무 집중하지 말자.

특히, paper에서는 RMSE가지고 성능이 좋아졌니 마니 하는데, 이것에 너무 집중하지 말자는 것이다.

실제로 DB에 추천 결과를 적재할 때, 모든 유저에 모든 상품의 predicted rating을 적재하려고 하지 말자.

굉장히 비효율적일 뿐더러, 유저는 그러한 rating맞추기엔 관심없을 테니 말이다.

Candidate Generation -> Scoring(Hybrid) -> Ranking -> Filtering

Candidate Generation,

여기에서는 개별 모델들을 학습한다.

Scoring,

여기에서는 개별 모델을 취합하는 Hybrid Recommendation을 설계한다.

Ranking,

단순히 item을 score에 따라 sorting하기 보다는, ranking을 다시 매기는 작업을 한다.

예를 들면, 자주 등장, 인기 상품, 평점 높은 상품 등을 상단에 배치하는 로직을 적용한다.

Filtering,

기 구매한 상품을 제거, 유해한 상품을 제거, score가 낮은 상품은 제거 등의 Filtering을 거친다.

Filtering을 거치고 나서야 Top-"N" recommendation을 얻는다.

상황:

a:numpy.ndarray, 2-dimensional, 

a의 각 row마다 k개의 top values뽑기

ex)

a=np.random.randint(0,10,(4,5))  # 0에서 9까지 values중 random integers뽑아서 shape이 (4,5)인 것

k=3

res = a[np.arange(len(a))[:, None], np.argsort(a)[:, -k:]][:, ::-1]

설명:

(1)

np.argsort는 ascending order로 indices를 뽑아냄

(2)

the smallest top k를 구하려면 np.argsort(a)[:, :k], 그리고 뒤에 [:, ::-1] 없어야함

(3) 

만약 the top k largest/smallest values 를 ordering없이 뽑으려면

np.argsort보다 np.partition이 낫다. 왜냐하면 np.argsort는 sorting(O(n*log(n))을 하지만 후자는 sorting하지 않음(O(n))

즉, 

res = np.partition(a, -k)[:, -k:] 하면은 top k values(not ordered)를 얻을 수 있다.

(4)

the top k largest/smallest values의 indices를 ordering없이 뽑으려면

np.partition말고 np.argpartition을 활용하면 된다.

즉,

res = np.argparition(a, -k)[:, -k:]

(5)

a에 negation붙여서 하진 말 것, 그러면 new object를 만들어서 하기 때문에 memory 더 쓰게 됨

참고자료:

kanoki.org/2020/01/14/find-k-smallest-and-largest-values-and-its-indices-in-a-numpy-array/

상황:

a = np.arange(20).reshape(4,5)

b = np.array([[0,1],[1,2],[2,3],[3,4]])

a의 first row에서는 [0,1]에 해당하는 entries를

a의 second row에서는 [1,2]에 해당하는 entries를

a의 third row에서는 [2,3]에 해당하는 entries를

a의 fourth row에서는 [3,4]에 해당하는 entries를 

가져오고 싶다.

res = a[np.arange(4)[:, None], b]

설명 

(1)

numpy.ndarray에 [:, None]을 하면 길이가 1인 axis를 하나 더 생성한다.

예를 들면

q = np.arange(10)  # shape은 (10,)

w = q[:, None]  # shape은 (10,1)

e = q[:, None]  # shape은 (10, 1, 1)

reshape(-1,1)과 비슷해보이지만

w = q.reshape(-1,1)  # (10,1)

e = w.reshape(-1,1)  # (10,1), 즉 w와 shape이 같음

(2)

a의 third row 빼고 가져오고 싶다면

ind = np.array([0,1,3])

res = a[ind[:,None], b[ind]]

(3)

a의 first, third빼고 모두 가져오고 싶다면

ind = np.array([x for x in range(len(a)) if x not in [0,2]])

res = a[ind[:,None], b[ind]]

상황:

arr는 2d numpy.ndarray

dict_는 dictionary, arr의 각 원소를 변환시킬 mapping

1.

res = np.vectorize(dict_.__getitem__)(arr)

np.vectorize는 내부적으로는 결국 python loop방식으로 돌기 때문에 numpy의 C base speedup 이점을 얻기 힘들다.

2.

u, inv = np.unique(arr, return_inverse=True)

res = np.array([dict_[x] for x in u])[inv].reshape(a.shape)

이는 [inv]와 reshape에서 numpy의 speedup이점을 얻을 수가 있다.

3. 만약 dict_의 key에 arr에 특정 원소만 존재한다면?

(1) arr의 일부 원소는 변환하고, 일부는 default값으로 바꿔 넣고 싶다면

u, inv = np.unique(arr, return_inverse=True)

res = np.array([dict_.get(x, "DEFAULT") for x in u])[inv].reshape(a.shape)

이렇게 dict_의 get method로 변환하고, missing key에 대해선 default 입력 가능

(2) arr의 일부 원소는 변환하고, 일부는 원래 그대로 두고 싶다면

u, inv = np.unique(arr, return_inverse=True)

res = np.array([dict_.get(x, x) for x in u])[inv].reshape(a.shape)

이렇게 dict_의 get method로 변환하고, missing key에 대해선 원본 그대로 입력 가능

dataframe에서 특정 column에 duplicates가 존재하면 지우는 것은 drop_duplicates를 활용한다.

중복인 것만 살리고 싶다면?

즉, 특정 column에서 한번만 등장한 것을 지우고, 다중 등장인 row만 살리고 싶다면

df = df[df."COLUMN".duplicated(keep=False)]

or

df = df[df.duplicated(['COLUMN'], keep=False)

를 사용하자. (후자는 multiple columns에도 활용 가능)

중복 여부 확인은 duplicated()

중복값 처리는 drop_duplicated()

keep에 'first', 'last', False가 가능

'first'는 중복이 있으면 첫 등장하는 것은 True, 이후는 False

'last'는 중복이 있으면 마지막 등장하는 것은 True, 이전은 False

False는 중복이 있으면 처음이든 끝이든 모두 True

itertuples가 iterrows보다 빠르다

itertuples에 들어갈 수 있는 argument로는

-index, default는 True이고 True이면 first element에 index가 포함된다. False면 index가 포함되지 않는다.

-name, default는 Pandas이며 반출하는 namedtuple의 이름을 가리킨다. 만약 name=None을 사용하면 namedtuple이 아니라 tuple을 반출한다.

-column의 개수가 255 이상이면 무조건 tuple을 반출한다. 따라서 itertuples를 활용한 함수를 정의시, 입력받은 dataframe의 column개수가 255이상인지 아닌지에 따라 구분해서 작성이 필요하다.

Python built-in인 islice을 활용한다.

from itertools import islice

for ind, row in islice(df.itertuples(index=False), 1, None):  # 2번째 row부터 iteration 시작

장점:

-domain knowledge가 필요 없음, embedding 알아서 학습하므로

-serendipity, 즉 해당 유저의 기존 interest 밖의 상품도 추천이 가능

-No need any contextual features, just the feedback matrix, 따라서 여러 추천 엔진 중 바로 적용하기 좋다.

-folding 문제를 해결(objective function에서 unobserved data에 대한 weight를 조절하여) 가능

-user/item embedding을 미리 계산해두고 저장하여 사용함으로써 Serving이 편리

-아주 많은 items가 존재하여도, user/item matrix가 대개 sparse하므로 scalability가 있음

단점:

-cold-start problem, 즉 training data에 한번도 없었던 new item은 추천되지 않는다.

  -해결방안 1, 만약 new item이 training data엔 없었지만 신규 거래내역/평점내역 등이 많이 존재한다면 전체를 재학습시켜도 되지만, 해당 new item만 embedding vector를 쉽게 학습시킬 수 있다.(projection in WALS) 즉, User embedding 그대로 유지시키고 new item vector만 학습

  -해결방안 2, new item과 유사한 items(유튜브라면 같은 업로더가 올린 타 동영상들, commerce라면 같은 분류나 같은 브랜드 내의 상품들 등)의 embedding vectors를 평균을 취하는 방식으로 new item embedding vector를 approximate

-User/Item의 feature를 함께 고려하기가 어렵다.

  -해결방안, 기존 user-item matrix에 row로는 item feature을, column으로는 user feature를 나타내는 multi-hot encoding block matrix를 추가하여 학습하면, user/item/each feature embedding을 모두 얻을 수가 있다.