Kaggle

Kaggle : Santa’s Stolen Sleigh

두 번째로 참여하게 된 Kaggle 대회는 Santa’s Stolen Sleigh 라는 대회이다. 이 대회는 다소 이벤트성 대회의 성격을 띠고 있는 것이, 크리스마스 기간에 맞추어 크리스마스 컨셉으로 나온 문제이기 때문이다. 제목만 봐도 그래보이지 않는가? 그러나 이 대회는 이벤트성 대회임에도 불구하고 실제 상금이 걸려있는 대회이다. 최종 1위 팀 / 리더보드 1위를 가장 길게 유지하고 있던 팀 / 제공된 Optimization Tool 을 이용한 팀 중 가장 점수가 높은 팀 에게 각각 1만불, 5천불, 5천불의 상금이 지급된다. 물론 나는 저 상금과는 상당히 거리가 멀었지만..

여하튼 이 대회는 다른 Kaggle 대회와는 다소 성격이 다른 대회이다. 다른 대회들이 정말 Data Science 스러운 문제들을 내놓고 있다면, 이 대회는 그보다는 조금더 PS적인 느낌이나 Optimization 느낌이 나는 문제를 제공했다고 할 수 있다. 과연 어떤 문제인지, 그리고 내가 어떤 방식으로 접근했는지 정리해보겠다.

Problem Description

크리스마스를 맞이하여 산타할아버지가 전 세계에 선물을 나누어주려고 한다. 세계 방방곡곡에 10만개의 선물을 배달해야하는데, 각각의 선물이 배달되어야 하는 위도-경도 좌표와 그 선물의 무게가 주어져있다. 산타할아버지는 루돌프가 끄는 썰매를 타고 North Pole에서부터 선물을 배달해야 한다. 그런데 한 번의 Trip에서 싣는 선물들의 무게의 합이 1000을 넘으면 안되고, Trip 한번이 끝나면 다시 North Pole로 돌아와서 남은 선물들을 담은 뒤 다음 Trip을 떠나야 한다. 썰매 자체의 무게는 10이다.

이 문제의 최종적인 목적은, 루돌프들이 너무 힘들지 않도록 배달하는 과정을 최대한 최적화시키는 것이다. 루돌프들이 힘든 정도는 ‘Weighted Raindeer Weariness – WRW’ 라고 해서, 다음과 같은 방식으로 계산한다.

WRW
w_kj = j번째 trip에서 k번째로 배달하는 gift의 무게, Loc_i = i번째로 배달하는 gift의 위치

즉, 어떤 지점에서 다른 지점으로 이동할 때의 그 거리와 그 거리를 이동할 때의 썰매+선물의 총 무게가 있을텐데, 이 값을 곱한 것을 모든 이동에 대해 다 더한 값을 WRW라고 하는 것이다. 이 때 거리는 haversine 이라는 방식을 이용하여, 위도와 경도를 이용하여 실제 지구상에서의 거리를 계산한 거리를 사용한다.

더 자세한 설명은 대회 페이지의 Description, Evaluation 항목에서 확인할 수 있다.

Approach

기본적으로 이 문제는 TSP 느낌이 나는 문제이다. 결국 주어진 지점들을 어떤 순서로 이동하느냐에 따라 점수가 달라지는 형태의 문제이기 때문이다. 물론 한 Trip에 대한  Weight limit이 있고, 점수 계산법도 크게 다르기 때문에 TSP와는 매우 다르면서도 훨씬 어려운 문제이기는 하지만 기본적으로 완전 그래프 위에서 경로를 최적화시켜나간다는 컨셉은 같기 때문에 전체적인 접근의 틀은 유사하게 가져갈 수 있을 것이다.

나는 기본적으로 이 문제에 대한 해결책을 크게 두 개의 단계로 나눠야 한다고 생각했다. 일단, 문제에서 각각의 Trip들에 대해 어떤 Gift들이 들어가야 하는지를 정해준다면, 각각의 Trip이 몇 번째로 진행되는가와는 상관 없이 Trip 하나하나에 대해 독립적으로 최적화를 시켜줄 수 있을 것이다. 즉, 문제를 크게 (1) Trip에 들어갈 Gift를 나누는 과정, (2) 각 Trip에서 선물을 배정하는 순서를 결정하는 과정 으로 나누어 진행할 수 있는 것이다.

이 문제를 진행하는 과정에서 가장 크게 유의해야할 점은 ‘계산량’ 이다. 먼저 선물의 갯수가 10만개나 되어, 안일하게 알고리즘을 세웠다가는 생각보다 계산량이 너무 많아져서 진행 속도가 너무 느려질 수 있다. 또한, 각 지점들 사이의 거리를 ‘haversine’ 으로 계산하는데, 이 계산에 sin, cos 뿐만 아니라 atan 등의 함수도 들어가기 때문에 거리 연산에 생각보다 많은 시간이 든다 (실험환경 기준으로 100000개의 haversine 연산을 하는 데에 0.31초 정도가 소요된다). 따라서, 최대한 계산량을 최적화하는 방향으로 문제를 해결해야 한다.

Stage #1 : Grouping Gifts (1)

문제를 Stage 1과 2로 나누어서 Grouping 과정과 Trip 순서 Optimization 과정으로 나누었지만, 실질적으로 대부분의 시간은 이 Stage 1 과정에서 소모하였다. 정말 엄청난 삽질과 멘붕, 그리고 시간소모를 하면서 결국 처음 예상했던 것과 너무 다른 방향으로 문제에 접근하게 되었고, 결국 정말 불만족스러운 결과를 얻게되었다. 여기에서는 처음부터 끝까지 내가 어떤 방식으로 문제에 매달렸는지에 대한 기록을 의식의 흐름대로 적어보려고 한다.

첫 번째 단계에서는 먼저 선물들을 묶어서 Trip에 들어갈 선물들을 선별해야한다. 이 때 대략적으로 초기해를 잡고 시작하려 했는데, 나는 처음 문제에 접근할 때 가장 좋은 방법이 ‘가까이 있는 선물들을 묶어서 한 Trip에서 같이 배달하는 것’ 이라고 생각하였다. 따라서 k-means를 구현하여 대충 가까이 있는 선물들을 묶어놓은 초기해를 만들었다. 이렇게 한 문장으로 적어놓으니 굉장히 간단하게 한 것 같지만, 이 k-means를 하는 데에도 나름 시행착오가 많이 들어갔다. haversine 연산의 시간이 오래 걸리기는 하지만 이를 기준으로도 충분히 계산할 수 있을 것이라고 생각하여, k-means를 할 때 위/경도 기반으로 계산을 진행했다. 그런데 이렇게 할 경우 클러스터의 중심점을 옮기는 과정에서 단순히 평균을 낼 수가 없어서, 단위구 위의 실제 좌표로 변환하여 평균을 낸 뒤 다시 위, 경도 기반 좌표로 바꾸는 식으로 계산을 진행했다. 또한, weight limit 조건을 만족하기 위해 가장 가까운 클러스터의 무게가 초과될 경우 다음으로 가까운 클러스터를 보는 방식으로 assign을 진행하였다.

대회 Forum을 보니 대부분의 사람들의 Trip의 수가 1200~1500 정도인 것 같아서, k를 1800으로 잡고 클러스터링을 진행하였다. 이 k-means의 경우 haversine 연산을 사용하기 때문에 numpy를 이용한 최적화를 하기가 힘들어서 실행 시간이 굉장히 오래 걸렸지만, 실행시켜놓고 일어나보니 얼추 클러스터링 된 결과를 얻을수가 있었다.

다음은 이 초기해를 바탕으로 Optimization을 진행하여, 더 좋은 Trip들을 얻는 과정이 필요하다. 이 과정이 문제 해결에 주가 되는 과정이므로 이 과정을 해결하는 알고리즘을 설정하는 것이 굉장히 중요하다. 결국 이러한 문제를 푸는 과정은 ‘방대한 해 공간을 탐색해가면서 가장 좋은 해를 찾는 것’ 이라고 요약할 수 있을 것이다. Machine Learning 분야에서는 이러한 ‘해공간의 탐색’ 이 Gradient Descent라는 이름으로, 기울기를 따라 조금씩 이동해가면서 해공간을 탐색하는 방식으로 사용되고 있다. 그러나 이번 대회와 같은 문제에서는 목적 함수가 Discrete하기 때문에, 함수에 기울기라는 것이 존재하지 않아서 다른 방법을 적용할 필요가 있다.

해공간을 탐색하는 기법들은 정말 다양하다. GA, SA 등 이미 수많은 메타휴리스틱 기법들이 발견되어 사용되고 있고, ACO 등의 집단지성 최적화 기법도 있다. 이러한 수많은 방법들 중, 나는 이 문제에 가장 적합해보이고 내가 일전의 프로젝트에 사용해보아 가장 익숙한 Tabu Search라는 방법을 이용하여 문제에 접근하기로 하였다(사실, 대부분의 상위권 팀들은 Simulated Annealing 을 사용한 듯 하다. 그래도 기본적으로는 비슷한 흐름을 가진 기법이니..).

Tabu Search는 기본적으로 특정 해에 대해 이웃한 ‘이웃해’를 정의하여 그 이웃해들 중 가장 좋은 해로 이동하는 Local Search 기법에다가 Local Minima에 빠지지 않도록 이동 금지 목록인 Tabu List를 관리하면서 탐색하는 기법이다. 즉, 기본적으로 특정 해 상황이 있을 때 그 해와 유사한 해인 이웃해를 정의해주어야 한다. 이 문제에서는 이웃을 (1) 특정 선물을 현재 Trip에서 다른 Trip으로 옮긴 해, (2) 가까이 위치한 특정 선물 2개의 Trip을 서로 맞바꾼 해 로 정하고, 구현하였다.

여기서 문제는, Tabu Search를 행하기 위해서는 현재 해가 얼마나 좋은 해인지 그 점수를 평가하는 기준이 있어야 한다는 것이다. 문제의 첫 번째 단계에서는 단순히 선물을 여러개의 Trip으로 나누는 일만을 하기 때문에 직접적으로 이 해가 좋은 해라는 기준을 세우기가 굉장히 어렵다. 그래서 간접적으로, ‘각 나눠진 Trip들에 대해 Greedy하게 (Weight이 큰 Gift를 먼저 배달하고, Weight이 같을 경우 위도 내림차순으로 배달) 배달했을 때의 총 WRW’ 를 평가 기준으로 삼아 Tabu Search를 진행하였다.

이웃해와 평가 함수가 정해졌으니 이를 바탕으로 Tabu Search를 진행하면 되지만, 정말 Naive하게 구현할 경우 계산량이 폭발해버리고 말 것이다. 기본적으로 이웃해를 본다는 것은 정의한 이웃해에 대해 가능한 해를 다 보아야 하는데, 이웃 (1)만 봤을 때도 모든 이웃해를 다 보기 위해서는

  •  Cluster 두개를 정하는 갯수 1800P2
  •  x 이동할 선물을 정하는 갯수 평균 50개
  •  x (이동한 후의 선물 위치 찾기 O(50) + 이동한 후의 WRW 변화량 계산 O(50 * haversine 연산) )

 으로,  한 단계에서 대충 O(81억 * haversine 연산) 이 필요한데, 최소 몇천에서 몇만 단계를 이동해야 하는 탐색에서 한 단계에서 저렇게 많은 연산이 필요하면 제대로 탐색을 진행할 수조차 없다. 따라서 여기에서 계산량을 줄이기 위해서 여러 가지 방법을 사용했는데,

(1) 이동한 후의 WRW 변화량을 직접 이동시켜서 계산하는 것이 아니라, 이웃이 된 후의 변화량을 예측하여 WRW 변화량 계산을 O(1)로 줄였다. 사실 이 과정에서 삽질을 많이 해서, 디버깅 하는데 애를 좀 먹었다.

(2) 한 단계에서 모든 클러스터 선택 가능성을 보는 것이 아니라, 첫 번째 클러스터를 정할 때에는 일정 갯수의 클러스터만 랜덤하게 선택해서 보았다. 또한, 두 번째 클러스터를 정할 때 현재 선택한 선물과 두 번째 클러스터의 첫번째 선물이 너무 멀리 떨어져있을 경우 탐색하지 않았다.

(3) 앞에서 소개한 Greedy한 방법의 중요한 점은, 선물들을 모두 Comparable 하게 만들 수 있다는 점이다. 따라서 각 Trip의 선물을 정렬해놓고 List의 형태로 가지고 있었고, 새로운 선물이 들어갈 위치를 찾을 때 이분 탐색을 이용하여 들어갈 위치를 찾았다. 이를 이용하면 새로운 선물이 들어갈 위치를 찾는데에 걸리는 시간이 O(50)에서 O(ln 50) 으로 줄어든다.

(4) 이웃 (2) 에서 ‘서로 가까운 선물 두 쌍을 골라서 바꾼다’ 는 식으로 되어있는데, 여기서 선물을 선택할 때마다 가까운 선물이 뭐가 있는지를 계산한다면 어마어마하게 시간이 많이 투자될 것이다. 따라서 이는 미리 전처리를 해놓아서 특정 선물에서 가장 가까운 선물들의 목록이 담긴 배열을 만들어놓고, 필요할 때 이를 불러서 사용하였다.

Stage #1 : Grouping Gifts (2)

이렇게 Tabu Search를 구현하였으니 이제 돌리면서 점수가 줄어들기만을 기다리면 될 것이다. 그런데 문제가, 너무 수렴하는 속도가 느렸다. 처음 k-means만을 돌린 초기해의 WRW가 15.55B였는데, 반나절 넘게 돌리니 13.XXB 정도가 되었지만 수렴 속도가 너무 느려져서 더 낮아지길 기대하기 힘들었다. 당시 대회 1등의 점수가 12.38B였고, 100등 안에 들기 위해서는 12.45~6B 정도까진 점수를 내려야 했기 때문에 변화의 필요성을 느꼈다. 이 때 대회 Forum을 찾아봤는데, 이 링크에서 발견한 코드에서 단순히 k=4000으로 잡고, haversine도 아니고 위/경도를 가지고 단순히 k-means를 돌린 결과임에도 불구하고 돌린 결과가 13.7B 정도였다 (아무래도 내가 k를 작게 잡고, weight limit을 주어서 돌렸다는 점에서 점수가 많이 높여진듯 하다). 따라서, 초기해를 이 링크에서 주어진 submission으로 바꾸어준 후 새롭게 Tabu Search를 돌렸다. 확실히, 초기해가 낮아지니 더 많이 내려가는 양상을 확인할 수 있었다.

그런데 여기에서도 문제가 있었다. 일단 여기서 k=4000 이었기 때문에 Tabu Search를 진행하면서 점점 Trip들이 합쳐지고 Trip의 숫자가 줄어야 했는데, Trip이 서로 합쳐지는 일은 일어나지 않았다. 확실히 Tabu Search는 각 단계에서 이웃해들 중 가장 좋은 해로 이동하기 때문에, Trip이 줄어들기 위해서는 임시적으로 점수가 오르는 방향으로 진행되어야 할 것이므로 그 방향으로 진행하지 않을 수 있다는 생각이 들었다. 그래서 기존 점수에 더해서 Trip의 선물 갯수가 줄어드는 방향으로 이동할 경우 Bonus 점수를 주는 식으로 점수를 더해보았지만, 크게 상황이 나아지지는 않았다. 지금 와서 생각해보면, 강제로 하나의 Trip을 없애고 다른 Trip들로 분배하는 operation을 추가했으면 어땠을까 싶다.

또한, 어느정도 수렴이 된 결과를 가지고 Stage 2를 구현하여 돌려보았는데, 돌아가는 양상을 보니 Stage 2를 다 돌려도 결과가 잘해야 12.6~7B밖에 나오지 않을 것 같았다. 이렇게 되면, 좋은 점수를 얻지 못할 것 같다는 생각이 들었다.

이렇게 되어, 초기해를 clustering으로 정하는 방식을 폐기하고 이 링크에 있는 Submission으로 바꾸었다. 이 Submission의 경우 초기 점수가 12.52B 정도 되었는데, 이 방식은 선물들을 Longitude 기준으로 묶어서 North Pole 에서 시작하여 수직으로 내려오는 방식으로 진행하였다. 사실 모든 상위권 팀들은 이러한 방식으로 접근을 한 듯 하다. 이 방법을 가져와서 Gift 비교 기준 등을 수정하여 며칠 간 돌려본 결과, 12.52B에서 12.459B 정도까지 점수를 내릴 수 있었다.

Stage #2 : Trip Optimization

두 번째 단계에서는 분류한 선물들을 가지고 각각의 Trip 자체를 Optimize 하였다. Trip이 2천개 정도 있을 경우 각각의 선물은 평균적으로 50개 정도밖에 없기 때문에, 이 단계에서 빠르고 쉽게 점수를 내릴 수 있을 것이라고 기대했다.

두 번째 단계에서도 마찬가지로 Tabu Search를 이용하여 최적화를 진행했다. 이웃해는 (1) 두 선물의 배달 순서를 바꾼다 (2) 한 선물을 빼고, 다른 순서로 배달한다 로 정의하였다. 먼저 구현해놓은 Tabu Search가 있었기에, 이 단계에서는 상대적으로 쉽게 구현을 끝낼 수가 있었다.

문제는,  Stage #2가 생각보다 의미가 없는 단계였다는 것이다. 비슷한 위치 기준으로 클러스터링하여 생각한 해의 경우 확실히 처음 생각한 Greedy한 방법이 정말 ‘Greedy 할 뿐인’ 방법이었기 때문에 이 단계에서 최적화될만한 요소가 많았고, 다 돌려보지는 않았지만 대충 점수를 13.15B에서 0.4B정도는 내릴 수 있을거라는 생각이 들었다. 반면, Longitude 기준으로 진행했을 경우 위에서 생각한 Greedy한 방법이 최적해와 상당히 유사한 방법이었기 때문에 Stage #2에서 내려가는 점수가 정말 적어서 의미가 없는 수준이었다. 따라서 여기서 의욕을 잃은데다가 설상가상으로 계절학기 시험까지 겹쳐서 포기하고, 최종적으로 Stage #1에서 만든 12.459B 정도의 Submission을 제출하였다.

Result & Discussion

확실히 이 대회는 정말 재미있는 대회이기는 했지만, 개인적으로 너무 멘붕과 삽질을 한 대회여서 정신적으로 피해가 컸다. 나름 생각을 많이 하고 여러가지 시도를 해보았지만, 아직 다른 사람들과 비교해보았을 때 많이 모자란게 아닌가 싶다. 나의 최종적인 점수는 12.459B였고, 1위 팀의 점수는 12.384B였다. 나는 1127개의 팀중 최종적으로 175위를 하였다.

대회 최종적으로 1위2위를 한 팀의 결과를 링크에서 확인할 수 있다. 두 팀은 모두 SA를 기반으로 탐색을 진행한 듯 하며, 1위 팀은 SA 기반으로 가장 좋은 parameter를 찾는 데에 많은 시간을 소모한듯 하다.

아.. Kaggle 정말 너무 어려운거 같다. ㅋㅋㅋㅋ 앞으로 공부해야할 것도 너무 많고… 더 잘 하고 싶다. 공부에 대한 의욕만 불타오르게 만들어준 대회였다.

모든 실험은 python으로 구현하여 진행하였고, 구현 결과는 내 Github Repo에서 확인할 수 있다.

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중