Dart로 Dbscan, k-means 를 구현해서 사용해보고 나서 둘에 대한 비교 소감.
나의 경우는 여러 사진 데이터를 가지고 자동 포토북(자동 그룹핑, 자동 페이지 레이아웃 배치)을 만드는 미션이 있었다.
그래서 유의미한 그룹핑을 얻기 위해서 클러스터링 알고리즘을 사용하기로 했었다.
Flutter앱에서 백엔드 없이 프론트엔드에서 할 수 있는 자동 배치 알고리즘에 대한 니즈가 있었다.
그래서 Flutter dart언어로 직접 클러스터링을 구현할 수 있는 방법을 찾아봤다. 패키지로는 구현이 안 되어 있었다. 그래서 직접 chatgpt와 함께 구현하기로 했다.
dbscan을 먼저 구현했고, dateTime과 gpsLocation에 대한 두 data type 모두를 하나의 dbscan 함수에서 비교할 수 있도록 distance 함수를 인풋 데이터의 type에 맞추는 로 구현하였었다. 그 외에도 꽤나 견고하게 신경써서 구현했다고 자부한다.
- dateTime에 대해서만 dbscan,
- gpsLocation에 대해서만 dbscan,
- (1), (2) 각각의 독립적인 클러스터링 결과를 가지고 simple graph clustering을 거쳐 차원 축소하는 방법,
- 처음부터 (dateTime)과 (gpsLocation) 각각의 distance calculator를 결합하여 복합적인 distance를 사용한 dbscan
이렇게 4가지를 구현해서 비교해보았다. 그 결과는, 2
사진의 그루핑이 유의미한 것처럼 느껴지도록 하는 요인은 상대적으로 dateTime이 gpsLocation보다 큰 요인이었다.
gps만 가지고 그루핑한 사진은 크게 의미를 찾기 어려웠다. 보통 자기의 사진을 모아보는 목적은 보면서 기억을 되살리는 목적이 있기 때문에, 공간만 같고 시간이 뒤죽박죽인 사진들은 자연스럽지 못했다.
그렇지만 gps가 dateTime과 함께 분류기준으로 쓰이는 경우에는 미세하게 dateTime 단독으로 사용했을 경우보다 그루핑의 느낌이 좋았다.
아무튼, 이렇게 그루핑을 하고 나면, 밀도기반 클러스터링의 특성 상 출력되는 그룹의 개수를 특정할 수 없다. 자동 포토북의 경우는 출력되는 제일 작은 단위의 그룹이 곧 한 페이지에 들어가는 사진의 묶음이기 때문에, 그룹의 개수를 특정해주는 것이 반드시 필요하다.
이를 위해 k-means 거리기반 클러스터링을 다시 사용해보기로 했다. 즉, step2로써 다시 세분화된 그룹핑을 위해 k-means를 사용해보기로 한 것이다. 이를 위해 dart언어로 k-means를 구현했고, 전체 데이터로 작동 테스트를 한 후에, dbscan의 결과로 얻은 그룹에서 세분화된 그룹핑을 위해 각 그룹에 대해 모두 k-means를 실시하였다. 큰 그룹의 경우 더 큰 k개를 할당해서 그룹핑을 진행했다. 예를 들어 그룹사이즈가 8인 그룹과 4인 그룹이 있으면, 전자는 k=3을, 후자는 k=2로 하는 것과 비슷했다.
하지만 테스트를 진행하다 보니, 고려하지 못했던 수많은 경우의수가 존재했다는 것을 알았고, 이는 단순히 k-means나 k-means++ 과 같은 기성 클러스터링 알고리즘을 사용해서 해결할 수 있는 문제가 아니라, 휴리스틱적으로 여러 제약조건을 부합하는 알고리즘을 만들고 최적화를 해야 풀 수 있는 문제라는 것을 깨닫게 되었다.
제약조건이 여러개이고, 또한 그 각 제약 조건들이 min값, max이 존재하는 범위값이기 때문에 푸는 방법을 구상하는 데에 어려움이 있었다. 많은 시도가 있고 시간을 들였고, 지금에 와서 구상해본 바는 다음과 같다. 고생한 걸 드러내고 싶어서 여기에 가져와봤다..
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
# Dbscan을 거친 결과, 유의미하게 묶인 사진의 그룹들이 생성되었다.
# 이를 원하는 형태로 다시 재그룹핑하는 과정을 거쳐야 한다.
# 이는 최적화와 휴리스틱을 통해 해결할 수 있다.
# input
# targetPageLength : 출력할 GroupListSize의 요소 개수 목표값 : 16
# TotalPhotoNum : 전체 사진의 수 : 34
# usablePageTemplateSizeMin: 사용가능한 페이지 템플릿의 최소 크기 : 1
# usablePageTemplateSizeMax: 사용가능한 페이지 템플릿의 최대 크기 : 6
# GroupListSizes : [5, 3, 2, 19, 1, 2, 2]
# CurrentPageLength: 현재 페이지의 길이: GroupListSize.length : 7
# pageSize(= GroupListSizes[i]) 중 usablePageTemplateSizeMax보다 큰 경우는,
# 해당 pageSize 요소를 usablePageTemplateSizeMax로 나누어 올림한 값을 개수로 하는 splitList를 만든다.
# 그리고 splitList의 요소를 pageSize만큼 하나씩 순회하면서, pageSize를 다 소진할 때까지 각 자리에 +1을 한다.
# 예를 들어, pageSize가 19이고, usablePageTemplateSizeMax가 6이라면, 19를 6으로 나누면 3.16이 나오므로, 4개로 나누어진다.
# 이렇게 몇 개로 나누어지는지는, 19를 6으로 나누어서 나오는 몫을 올림한 값으로 나누어주면 된다.
# 이 과정은 getSplitNumBySize라고 하자. 예를 들어, splitIntoLength = getSplitNumBySize(19, 6)이면, splitIntoLength = 4가 된다.
# 4개의 요소를 가진 splitList를 만들고, 각 요소를 돌면서 19를 골고루 나누어주면, [5, 5, 5, 4]가 된다.
# 다시 말해, 19를 6으로 나누어서 4개의 요소로 나누고, 각 요소에 1씩 더해주면, 19가 된다.
# 또 다른 예를 들어, pageSize가 34이고, usablePageTemplateSizeMax가 6이라면, 34를 6으로 나누면 5.66이 나오므로, 6개로 나누어진다.
# 함수 getSplitNumBySize를 사용하면, splitIntoLength = getSplitNumBySize(34, 6)이면, splitIntoLength = 6이 된다.
# 6개의 요소를 가진 splitList를 만들고, 각 요소를 while문으로 반복해 돌면서 34를 골고루 나누어주면, [6, 6, 6, 6, 5, 5]가 된다.
# [1, 0, 0, 0, 0, 0] -> [1, 1, 0, 0, 0, 0] -> [1, 1, 1, 0, 0, 0] -> [1, 1, 1, 1, 0, 0] -> [1, 1, 1, 1, 1, 0] -> [1, 1, 1, 1, 1, 1] ->
# -> [2, 1, 1, 1, 1, 1] -> [2, 2, 1, 1, 1, 1] -> [2, 2, 2, 1, 1, 1] -> [2, 2, 2, 2, 1, 1] -> [2, 2, 2, 2, 2, 1] -> [2, 2, 2, 2, 2, 2] ->
# -> [3, 2, 2, 2, 2, 2] -> [3, 3, 2, 2, 2, 2] -> [3, 3, 3, 2, 2, 2] -> [3, 3, 3, 3, 2, 2] -> [3, 3, 3, 3, 3, 2] -> [3, 3, 3, 3, 3, 3] ->
# -> [4, 3, 3, 3, 3, 3] -> [4, 4, 3, 3, 3, 3] -> [4, 4, 4, 3, 3, 3] -> [4, 4, 4, 4, 3, 3] -> [4, 4, 4, 4, 4, 3] -> [4, 4, 4, 4, 4, 4] ->
# -> [5, 4, 4, 4, 4, 4] -> [5, 5, 4, 4, 4, 4] -> [5, 5, 5, 4, 4, 4] -> [5, 5, 5, 5, 4, 4] -> [5, 5, 5, 5, 5, 4] -> [5, 5, 5, 5, 5, 5] ->
# -> [6, 5, 5, 5, 5, 5] -> [6, 6, 5, 5, 5, 5] -> [6, 6, 6, 5, 5, 5] -> [6, 6, 6, 6, 5, 5]. 이 때 총 합이 34가 되므로, 멈춘다.
# 이렇게 만들어진 리스트를 splitList라고 하자.
# 이 리스트를 해당하는 pageSize가 있던 자리(GroupListSizes[i])에 대신 넣고 그 다음 요소들은 뒤로 밀어주면 된다. 이렇게 하는 과정을 splitReplaceInsert라고 하자.
# 예를 들어, GroupListSizes가 [5, 3, 2, 19, 1, 2, 2]이고, splitList가 [5, 5, 5, 4]라면, 19가 5, 5, 5, 4로 나누어진다.
# 따라서, GroupListSizes의 4번째 자리에 5, 5, 5, 4를 넣어주면 된다.
# 그 결과는, [5, 3, 2, 5, 5, 5, 4, 1, 2, 2]가 된다. 이 때 주의할 점은, insert를 하면서 기존의 요소들이 삭제되는 것이 아니라, 뒤로 밀려난다는 것이다.
# 즉, GroupListSizes = splitReplaceInsert(GroupListSizes, i, splitIntoLength)는 GroupListSizes의 i번째 자리에 splitIntoLength길이의 리스트를 넣어주고 리턴하는 함수이다.
# 예를 들어, GroupListSizes = splitReplaceInsert([5, 3, 2, 19, 1, 2, 2], 3, 6)이면, 19를 6개 자리에 나눠 담아서 [4, 3, 3, 3, 3, 3]인 splitList를 만들고, GroupListSizes의 3번째 자리에 넣어주면 [5, 3, 2, 4, 3, 3, 3, 3, 3, 1, 2, 2]가 된다.
# 다시 예를 들어, GroupListSizes = splitReplaceInsert([5, 3, 2, 19, 1, 2, 2], 3, 5)이면, 19를 5개 자리에 나눠 담아서 [4, 4, 4, 4, 3]인 splitList를 만들고, GroupListSizes의 3번째 자리에 넣어주면 [5, 3, 2, 4, 4, 4, 4, 3, 1, 2, 2]가 된다.
# 이 splitReplaceInsert과정은 함수로 만들어서, GroupListSizes의 각 요소를 검사하여 usablePageTemplateSizeMax보다 큰 경우에 대해 처리해주면 된다.
# 예를 들어, GroupListSizes의 요소 개수가 7개라면, 7번 반복하면 된다. 하지만 실제 교체가 일어나는 경우는, pageSize가 usablePageTemplateSizeMax보다 큰 경우에만 일어난다.
# 여기까지가 1차 페이징 스텝이다.
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
# 1차 페이징 스텝을 거친 후에는, GroupListSizes에는 usablePageTemplateSizeMax보다 큰 요소가 없다.
# 따라서, 2차 페이징 스텝에서는 GroupListSizes의 요소 개수가 targetPageLength보다 크거나 작을 경우에 대한 처리를 해주어야 한다.
# GroupListSizes의 요소 개수가 targetPageLength보다 크거나 작을 경우에 대한 처리를 해주어야 한다.
# 만약, GroupListSizes의 요소 개수가 targetPageLength보다 크다면, GroupListSizes의 요소 개수를 targetPageLength로 줄이면 된다.
# 만약, GroupListSizes의 요소 개수가 targetPageLength보다 작다면, GroupListSizes의 요소 개수를 targetPageLength로 늘리면 된다.
# 이렇게 하는 과정을 targetPageLength에 맞추는 과정, 즉 targetPageLengthMatch라고 하자.
# 이 과정을 함수로 만들어서, GroupListSizes의 요소 개수가 targetPageLength보다 크거나 작을 경우에 대한 처리를 해주면 된다.
# 예를 들어, GroupListSizes = targetPageLengthMatch(GroupListSizes, targetPageLength)이면, 출력된 GroupListSizes의 요소 개수는 targetPageLength개가 된다.
# GroupListSizes < targetPageLength 인 경우를 먼저 고려하자.
# 예를 들어, GroupListSizes의 요소 개수가 7개이고, targetPageLength가 16이라면, 7개를 16개로 늘리면 된다.
# (targetPageLength - GroupListSizes.length)을 needToAdd라고 하자.
# GroupListSizes를 돌면서, 가장 큰 요소를 찾고, 해당 요소에 1회만큼 2개로 splitReplaceInsert해주기로 하자. 매회 splitReplaceInsert를 해줄 때마다 needToAdd를 1회씩 줄여주면 된다.
# 또한 매회 GroupListSizes를 돌 때는 다시 첫 순서의 요소부터 돌면서 가장 큰 요소를 찾아야 한다.
# 예를 들어, GroupListSizes_before = [5, 3, 2, 4, 4, 4, 4], targetPageLength = 16이라면,
# GroupListSizes_after = tagetPageLengthMatch(GroupListSizes_before, targetPageLength)이면, 입력한 GroupListSizes_before의 요소 개수는 7개이고, targetPageLength는 16이다.
# 따라서 tagetPageLengthMatch함수 내에서,
# 16 - 7 = 9이므로, 9회만큼 가장 큰 요소에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_before, i, 2)를 반복해주면 된다.
# 1회차에 가장 앞에 있는 가장 큰 요소는 5이므로, 5의 위치인 0번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_before, 0, 2)를 해주면,
# splitReplaceInsert함수 내에서 5를 2개로 나누어주면, [3, 2]가 되고, GroupListSizes_onGoing = [3, 2, 3, 2, 4, 4, 4, 4]가 된다. 길이는 8이다.
# 2회차에 가장 앞에 있는 가장 큰 요소는 4이므로, 4의 위치인 4번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 4, 2)를 해주면,
# splitReplaceInsert함수 내에서 4를 2개로 나누어주면, [2, 2]가 되고, GroupListSizes_onGoing = [3, 2, 3, 2, 2, 2, 4, 4, 4]가 된다. 길이는 9이다.
# 3회차에 가장 앞에 있는 가장 큰 요소는 4이므로, 4의 위치인 6번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 6, 2)를 해주면,
# splitReplaceInsert함수 내에서 4를 2개로 나누어주면, [2, 2]가 되고, GroupListSizes_onGoing = [3, 2, 3, 2, 2, 2, 2, 2, 4, 4]가 된다. 길이는 10이다.
# 4회차에 가장 앞에 있는 가장 큰 요소는 4이므로, 4의 위치인 8번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 8, 2)를 해주면,
# splitReplaceInsert함수 내에서 4를 2개로 나누어주면, [2, 2]가 되고, GroupListSizes_onGoing = [3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 4]가 된다. 길이는 11이다.
# 5회차에 가장 앞에 있는 가장 큰 요소는 4이므로, 4의 위치인 10번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 10, 2)를 해주면,
# splitReplaceInsert함수 내에서 4를 2개로 나누어주면, [2, 2]가 되고, GroupListSizes_onGoing = [3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2]가 된다. 길이는 12이다.
# 6회차에 가장 앞에 있는 가장 큰 요소는 3이므로, 3의 위치인 0번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 0, 2)를 해주면,
# splitReplaceInsert함수 내에서 3를 2개로 나누어주면, [2, 1]가 되고, GroupListSizes_onGoing = [2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]가 된다. 길이는 13이다.
# 7회차에 가장 앞에 있는 가장 큰 요소는 2이므로, 2의 위치인 0번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 0, 2)를 해주면,
# splitReplaceInsert함수 내에서 2를 2개로 나누어주면, [1, 1]가 되고, GroupListSizes_onGoing = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]가 된다. 길이는 14이다.
# 8회차에 가장 앞에 있는 가장 큰 요소는 2이므로, 2의 위치인 6번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 6, 2)를 해주면,
# splitReplaceInsert함수 내에서 2를 2개로 나누어주면, [1, 1]가 되고, GroupListSizes_onGoing = [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]가 된다. 길이는 15이다.
# 9회차에 가장 앞에 있는 가장 큰 요소는 2이므로, 2의 위치인 8번째 자리에 1회만큼 GroupListSizes_onGoing = splitReplaceInsert(GroupListSizes_onGoing, 8, 2)를 해주면,
# splitReplaceInsert함수 내에서 2를 2개로 나누어주면, [1, 1]가 되고, GroupListSizes_onGoing = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]가 된다. 길이는 16이다.
# 따라서, GroupListSizes_onGoing = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2]가 된다. 길이는 16이다.
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
# GroupListSizes > targetPageLength 인 경우를 고려하자.
# 예를 들어, GroupListSizes의 요소 개수가 7개이고, targetPageLength가 4이라면, 7개를 4개로 줄이면 된다.
# (GroupListSizes.length - targetPageLength)을 needToRemove라고 하자.
# 예를 들어, GroupListSizes_before = [4, 3, 2, 4, 3, 2, 3], targetPageLength = 4이라면,
# GroupListSizes_after = targetPageLengthMatch(GroupListSizes_before, targetPageLength)이면, 입력한 GroupListSizes_before의 요소 개수는 7개이고, targetPageLength는 4이다.
# 따라서 targetPageLengthMatch함수 내에서, needToRemove = 7 - 4 = 3이므로, 3회만큼 가장 작은 요소를 찾아서 그 다음 요소와 합쳐주면 된다.
# 특정 방법에 따라 두 개의 요소를 합쳐서 하나의 요소로 만들어주는 mergeReplaceInsert함수를 needToRemove == 0 이 될 때까지 반복해주면 된다.
# 매 회마다 mergeReplaceInsert함수는 GroupListSizes의 요소 중 가장 작은 요소 한 개를 찾고, 해당 요소와 바로 이전 요소를 합쳐서 usablePageTemplateSizeMax보다 작거나 같다면, 해당 요소를 합쳐주면 된다.
# 단, 맨 앞에 있는 요소는 그냥 두고, 두 번째 요소부터 차례대로 검사하면 된다. 즉, i>0일 때만 검사하면 된다.
# mergeReplaceInsert함수는 GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_before, i-1, i)이면, GroupListSizes_before의 i-1번째 요소와 i번째 요소를 합쳐주고 리턴하는 함수이다.
# 이 때 mergeReplaceInsert함수 내에서는 인풋 리스트인 GroupListSizes_before와 크기가 동일한 isMergable 리스트를 만들어서 관리한다.
# isMergable 리스트는 GroupListSizes_before의 요소 개수만큼 true or false로 초기화된 리스트이다. 첫 요소만 false이고 나머지는 true이다. 즉, isMergable = [False, True, True, True, True, True, True]이다.
# 매 회차를 돌 때마다, isMergable[i] == False이면, 해당 i번째 요소의 검사는 무시하고 넘어가면 된다.
# isMergable = [False, True, True, True, True, True, True]이고, GroupListSizes_before = [4, 3, 2, 4, 3, 2, 3]이라면,
# 1회차에 isMergable = [False, True, True, True, True, True, True]이고, 이 true인 인덱스를 가지는 GroupListSizes_before의 요소 중 가장 작은 요소는 2이고, 2의 위치는 2번째 자리이다. 따라서, 1번째와 2번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_before, 1, 2)이면,
# mergeReplaceInsert함수 내에서는 3와 2을 합쳐주면, sum = 5가 되고, 5가 usablePageTemplateSizeMax보다 작거나 같으므로, GroupListSizes_onGoing = [5, 5, 4, 3, 2, 3]가 된다. 길이는 6이다. needToRemove = 2이다.
# 2회차에 isMergable = [False, True, True, True, True, True]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소 중 가장 작은 요소는 2이고, 2의 위치는 4번째 자리이다. 따라서, 3번째와 4번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_onGoing, 3, 4)이면,
# mergeReplaceInsert함수 내에서는 3와 2을 합쳐주면, sum = 5가 되고, 5가 usablePageTemplateSizeMax보다 작거나 같으므로, GroupListSizes_onGoing = [5, 5, 4, 5, 3]가 된다. 길이는 5이다. needToRemove = 1이다.
# 3회차에 isMergable = [False, True, True, True, True]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소 중 가장 작은 요소는 3이고, 3의 위치는 4번째 자리이다. 따라서, 3번째와 4번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_onGoing, 3, 4)이면,
# mergeReplaceInsert함수 내에서는 5와 3을 합쳐주면, sum = 8가 되고, 8이 usablePageTemplateSizeMax보다 크므로, 합칠 수 없다. 대신, isMergable[4] = False로 만들어주면 된다. needToRemove = 1이다.
# 4회차에 isMergable = [False, True, True, True, False]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소 중 가장 작은 요소는 4이고, 4의 위치는 2번째 자리이다. 따라서, 1번째와 2번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_onGoing, 1, 2)이면,
# mergeReplaceInsert함수 내에서는 5와 4을 합쳐주면, sum = 9가 되고, 9이 usablePageTemplateSizeMax보다 크므로, 합칠 수 없다. 대신, isMergable[2] = False로 만들어주면 된다. needToRemove = 1이다.
# 5회차에 isMergable = [False, True, False, True, False]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소 중 가장 작은 요소는 5이고, 5의 위치는 1번째 자리이다. 따라서, 0번째와 1번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_onGoing, 0, 1)이면,
# mergeReplaceInsert함수 내에서는 5와 5을 합쳐주면, sum = 10가 되고, 10이 usablePageTemplateSizeMax보다 크므로, 합칠 수 없다. 대신, isMergable[1] = False로 만들어주면 된다. needToRemove = 1이다.
# 6회차에 isMergable = [False, False, False, True, False]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소 중 가장 작은 요소는 5이고, 5의 위치는 3번째 자리이다. 따라서, 2번째와 3번째 숫자를 합쳐줄 수 있는지 검사한다. GroupListSizes_onGoing = mergeReplaceInsert(GroupListSizes_onGoing, 2, 3)이면,
# mergeReplaceInsert함수 내에서는 5와 4을 합쳐주면, sum = 9가 되고, 9이 usablePageTemplateSizeMax보다 크므로, 합칠 수 없다. 대신, isMergable[3] = False로 만들어주면 된다. needToRemove = 1이다.
# 7회차에 isMergable = [False, False, False, False, False]이고, 이 true인 인덱스를 가지는 GroupListSizes_onGoing 요소가 없다. 따라서, 더 이상 합칠 수 있는 요소가 없으므로, 해당 루프를 종료하면 된다.
# 루프를 종료한 후에, needToRemove를 계산하면, needToRemove = GroupListSizes_onGoing.length - targetPageLength = 5 - 4 = 1이다.
# 따라서, 이제는 다른 방식으로 처리해야 한다. 그 방법을 수행하는 함수를 dissolveFromBack이라고 하자.
# dissolveFromBack함수는 GroupListSizes_onGoing = dissolveFromBack(GroupListSizes_onGoing, needToRemove)이면, GroupListSizes_onGoing의 뒤에서부터 needToRemove만큼의 요소를 삭제하고,
# 해당 위치에 있던 요소들의 값의 합 만큼을 앞에 남아있는 요소에 뒤에서부터 더하여 해당 요소가 usablePageTemplateSizeMax와 같을 때까지 반복해주면 된다.
# 채우던 중에 usablePageTemplateSizeMax보다 크다면, 해당 요소를 그대로 두고, 그 다음 요소부터 다시 더해주면 된다.
# 이를 위해 GroupListSizes_onGoing.length-1과 동일한 isIndexAddable이라는 int를 만들어서, 점점 크기를 줄여나가게 된다. 즉, 초기의 isIndexAddable = 5이다.
# 예를 들어, GroupListSizes_onGoing = [5, 5, 4, 5, 3]이고, needToRemove = 1이라면, needToRemove만큼의 요소를 뒤에서부터 삭제하고, 해당 위치에 있던 요소들의 값의 합 만큼을 앞에 남아있는 요소에 뒤에서부터 더하여 해당 요소가 usablePageTemplateSizeMax와 같을 때까지 반복해주면 된다.
# 1회차에 GroupListSizes_onGoing = [5, 5, 4, 5], remains = 3이고, isIndexAddable = 3이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 1회차에 GroupListSizes_onGoing = [5, 5, 4, 5], remains = 3이고, isIndexAddable = 3이다.
# GroupListSizes_onGoing[isIndexAddable] < usablePageTemplateSizeMax이므로 GroupListSizes_onGoing[isIndexAddable] += 1을 하고,
# 따라서 GroupListSizes_onGoing = [5, 5, 4, 6], remains = 3-1 = 2이다.
# 다시 GroupListSizes_onGoing[isIndexAddable] = 6이므로, usablePageTemplateSizeMax와 같으므로 , remains = 2이고 isIndexAddable은 3-1 = 2이다.
# 2회차에 GroupListSizes_onGoing = [5, 5, 4, 6], remains = 1이고, isIndexAddable = 2이다.
# GroupListSizes_onGoing[isIndexAddable < usablePageTemplateSizeMax이므로 GroupListSizes_onGoing[isIndexAddable] += 1을 하고,
# 따라서 GroupListSizes_onGoing = [5, 5, 5, 6], remains = 2-1 = 1이다.
# 다시 GroupListSizes_onGoing[isIndexAddable] = 5이므로, usablePageTemplateSizeMax보다 작으므로, remains = 1이고 isIndexAddable은 2이다.
# 3회차에 GroupListSizes_onGoing = [5, 5, 5, 6], remains = 1이고, isIndexAddable = 2이다.
# GroupListSizes_onGoing[isIndexAddable] < usablePageTemplateSizeMax이므로 GroupListSizes_onGoing[isIndexAddable] += 1을 하고,
# 따라서 GroupListSizes_onGoing = [5, 5, 6, 6], remains = 1-1 = 0이다. remains가 0이므로, 더 이상 채울 요소가 없으므로, 해당 루프를 종료하면 된다.
# 따라서, GroupListSizes_onGoing = [5, 5, 6, 6]가 된다. 길이는 4이다.
1
2
3
4
5
6
7
8
9
10
# 소감: 타겟 페이지 길이에 맞추는 과정에서, 타겟 페이지 길이보다 작은 경우와 큰 경우를 모두 고려해야 한다.
# 클러스터링으로 유사한 사진끼리 묶었더라도, 타겟페이지에 맞추는 과정에서는 극단적인 경우 묶었던 것이 풀리게 되는 경우가 생길 수 있다.
# 따라서, 그럴 듯하게 자동화된 포토북을 만들기 위해서는, 타겟페이지를 사용자가 직접 설정할 수 있도록 하기보다는,
# 업로드한 사진의 개수와, 밀도 기반 클러스터링 결과에 따라 1차적으로 묶이고 최대최소 페이지레이아웃 사이즈로 나뉜 페이지들이 이루는 총 제작가능한 추천 페이지 수의 범위를 계산하여 사용자에게 보여주고,
# 이를 스크롤하여 비교하고 추천 페이지 범위 내에서 적절한 타겟페이지를 선택할 수 있도록 하는 것이 좋을 것 같다.
# 정리하자면, 자동 포토북 배치 연관성의 하락을 감수하고서라도 고정 타겟 페이지를 고수하고자 하는 사용자라면, 그에 맞는 서비스를 제공하고,
# 고정 타겟 페이지는 상대적으로 덜 고집하여 추천 페이지 범위 내에서 적절한 타겟페이지를 선택하고자 하는 사용자라면, 포토북 배치 연관성을 높이는 서비스를 제공하는 것이 좋을 것 같다.
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
# 클러스터링에 대해 정리하자면, 클러스터링은 데이터를 비슷한 것끼리 묶어주는 알고리즘이다.
# 구현 가능한 수준의 클러스터링에는 밀도기반 dbscan, k-means가 있으며, dbscan이 다양한 경우에 대해 더 유연하게 작동한다.
# 이 둘의 차이점을 알아보고, 둘의 관계가 상호보완적이라면 그 둘을 같이 사용할 것을 고려해보고, 아니라면 어느 한쪽이 다른 한쪽의 성능상 완벽한 상위호환이어서 한 쪽을 버리고 다른 한 쪽만 사용해야 하는지 알아보자.
# 둘의 차이점은 k-means는 클러스터의 개수를 미리 정해야 하지만, dbscan은 클러스터의 개수를 미리 정하지 않아도 된다는 점이다. 대신 dbscan은 한 클러스터에 속하는 데이터들의 최소 개수를 정해야 한다.
# k-means가 클러스터의 개수를 미리 정할 수 있는 점이 마치 경우에 따라 장점으로 보일 수도 있지만, 클러스터의 개수를 맞춘다는 것이 모든 클러스터가 의미있는 클러스터라는 보장이 없다.
# 예를 들어 20개를 밀도 기반 클러스터링을 하면 3개로 나뉘는데, k-means로 클러스터링을 k=10으로 하면, 3개를 10개로 굳이 찢는 과정에서 의미가 없게 찢어질 수 있다.
# 의미가 없다는 것은 추가적으로 찢어진 7개가 각각 따로 outlier처럼 4, 4, 5, 1, 1, 1, 1, 1, 1, 1개로 찢어진다면, 1개들은 의미가 없는 찢어짐이다.
# (반면 dbscan은 개수를 지정하지 않기 때문에 데이터를 표현하기 좋은 가장 적절한 개수로 찢어진다.)
# 의미가 있게 찢어지려면 고르게 찢어져야 한다. k-means에서 고르게 그룹핑을 하도록 추가하는 알고리즘은 balancing이라고 하며, 이는 각 그룹의 크기가 비슷해지도록 하는 알고리즘이다.
# k-means에 balancing을 적용하면, k-means++이라고 하는 알고리즘이 나온다. k-means++는 초기 중심점을 랜덤으로 정하는 것이 아니라, 초기 중심점을 고르게 정하는 알고리즘이다.
# 하지만 k-means++가 수행하는 balancing도 원하는 결과를 얻지 못했다. 왜냐하면 포토북의 경우 추가적인 조건이 더 들어가야 하기 때문이다.
# 먼저, 포토북의 타겟 페이지 길이가 미리 지정되어 있다. 그리고, 포토북의 최소 최대 페이지 레이아웃 사이즈가 미리 지정되어 있다.
# 포토북의 최소 최대 페이지 레이아웃 사이즈를 고려하려 하니 훨씬 복잡한 k-means++가 나오고, 제약조건이 많아졌기 때문에 클러스터링 본연의 기능을 제대로 수행하지 못하게 되었고 휴리스틱 최적화 문제로 바뀌게 된다.
# k-means와 dbscan을 둘 다 해본 결과, k-means는 dbscan을 보완하는 역할을 하지 못했다. 오히려 명백히 dbscan이 k-means의 상위호환인 것으로 보였다.
# k-means가 목표 그룹 개수인 k를 사용자가 원하는 대로 정해서 클러스터링을 하라고 있는 알고리즘이 아니라, 명백히 최적의 k값은 정해져 있는데, 그것을 찾아내기 위해 여러 시행착오를 거쳐야 하는 알고리즘이라는 것이다.
# 따라서 최적의 k를 자동으로 결정해주는 장치가 기본적으로 되어있는 dbscan 알고리즘, 혹은 k-means에 k를 자동으로 결정해주는 추가적인 장치를 더한 어떠한 알고리즘을 사용하는 편이 의미 있는 클러스터링을
# 수행하는 데에도 더 빠르고 효과적이다.
# 따라서, 이러한 복잡한 문제를 해결하기 위해서는, k-means로 원하는 형태의 원하는 개수의 그룹으로 임의로 지정하여 유의미하게 나누는 것은 가능하지 않으며,
# 사진의 가까운 정도를 기반으로 한 밀도기반dbscan 클러스터링을 수행하고, 이를 기반으로 포토북의 타겟 페이지 길이 또는 최대 최소 페이지레이아웃사이즈,
# 혹은 둘다에 맞추는 휴리스틱 최적화 재배치 과정을 거치는 것이 자동 포토북을 만드는 가능한 전략이다.
# 추가적으로, 현 시점에서 시도하지 않은 대안으로 효과가 있을 수도 있을 것으로 예상되는 유일한 방법은 두 사진 간의 유사도(affinity)를 2d배열로 저장하는 graph기반 클러스터링으로,
# 해당 방법을 사용할 시에 어떠한 과정을 거쳐 어떠한 결과를 얻을 수 있고, 지금의 방법과 비교했을 때 같은 문제가 있을지, 혹은 다른 문제가 있을지에 대해서는 시도해보지 않았기 때문에 알 수 없다.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.