최적화 알고리즘을 통해 최적 할인율 쿠폰 구하기

00. 최적 할인율 쿠폰 구하기

지난 시간에도 최적 할인율 쿠폰을 구하기 위한 업무를 계속 진행했습니다. 이전 시간에는 회귀 분석을 통해서 예상 구매고객이 제일 많은 쿠폰을 찾는 과정을 진행했습니다. 다만 실제로 업무를 진행하다보니 아래와 같은 한계점을 마주쳐 새로운 방식을 고안하게 되었습니다.

• 쿠폰 속성에는 할인율만 존재하는 것이 아님 -- 최소구매조건, 최대구매조건 등 다양한 조건 또한 쿠폰을 세팅할 때 고민해야함
• 다양한 속성을 고민해서 모델을 만들 때, 다양한 조합으로 결과치를 확인하고 싶은데 회귀모델은 이 때 많은 제한점이 있음
• 회귀분석으로 모든 과정을 보기에 너무 많은 시간이 소요됨 -- 더 효율적인 모델을 사용할 필요성이 있음

위와 같은 문제점을 마주치고 업무 과정을 나눠서 진행하기로 했습니다. 먼저 이전 회귀분석에서 사용했던 내용으로 과거 데이터를 바탕으로 고객들의 예상 사용률을 예측하고자 합니다. 이렇게 예측한 예상 사용률을 바탕으로 최적화 알고리즘을 이용해서 (할인율, 최소구매조건, 최대할인금액) 값을 한 번에 구하기로 정했습니다. 그럼 다음 아래에서는 최적화 알고리즘에 대해서 간략히 먼저 공부해보도록 하겠습니다.

어차피 회사에서 잘 사용하지 않을 것 같지만 하라면 해야 하는게 직장인입니다.

01. 최적화란 무엇인가

최적화는 많은 현실 세계 문제에서 핵심적인 역할을 담당하고 있습니다. 예를 들어, 기계 학습 모델의 성능을 최대화하거나 비용을 최소화하는 제조 공정을 설계하는 등의 문제에서 최적화는 필수적인 도구입니다. 최적화 알고리즘은 주어진 조건과 제약 사항 하에서 주어진 목적 함수를 최대화하거나 최소화하기 위해 사용되는 수학적인 접근 방식입니다. 결국 손실함수의 값을 최소화하는 하이퍼 파라미터를 찾는 방법인데 이러한 방법에는 아래와 같은 대표적인 모델이 존재합니다.

출처: 하용호, 자습해도 모르겠던 딥러닝, 머리속에 인스톨 시켜드립니다

1. 경사 하강법 (Gradient Descent, GD)

   경사 하강법은 기본적인 최적화 알고리즘으로, 목적 함수의 기울기(그래디언트)를 사용하여 최적해를 찾는 방법입니다. GD는 현재 위치에서 그래디언트를 계산하고, 그래디언트의 반대 방향으로 일정 거리(학습률, learning rate)만큼 이동합니다. 이 과정을 최적해에 도달할 때까지 반복합니다. GD는 단순하고 직관적인 방법이지만, 큰 데이터셋이나 복잡한 문제에서는 계산 비용이 높아질 수 있습니다.

2. 확률적 경사 하강법 (Stochastic Gradient Descent, SGD)

   확률적 경사 하강법은 GD의 변형으로, 매 단계마다 랜덤하게 선택한 하나의 데이터 샘플에 대한 그래디언트를 계산하여 업데이트하는 방식입니다. 이는 GD보다 계산 비용이 낮아지며, 특히 대규모 데이터셋에서 더 효율적으로 동작합니다. 그러나 SGD는 그래디언트의 노이즈로 인해 수렴하는 데 더 많은 반복이 필요할 수 있습니다.

3. 모멘텀 (Momentum)

   모멘텀은 GD나 SGD보다 빠르게 수렴하고 지역 최소값에서 빠져나오는 데 도움이 되는 알고리즘입니다. 모멘텀은 현재의 그래디언트 업데이트에 이전 업데이트에 대한 모멘텀을 추가하여, 이동 방향을 고려하는 방식으로 작동합니다.

4. AdaGrad (Adaptive Gradient)

   AdaGrad는 학습률을 조정하여 각 매개변수의 업데이트 속도를 개별적으로 조절하는 알고리즘입니다. AdaGrad는 경사 제곱의 누적 합을 사용하여 각 매개변수의 학습률을 조절하는 방식으로 작동합니다. 매개변수의 그래디언트가 많이 업데이트된 경우에는 학습률이 감소하여 안정성을 향상시킵니다.

5. RMSProp (Root Mean Square Propagation

   RMSProp은 AdaGrad의 단점을 개선하기 위해 제안된 알고리즘입니다. RMSProp은 최근 그래디언트의 제곱값을 지수 이동 평균을 사용하여 누적하지 않고, 과거 그래디언트의 영향을 감소시킴으로써 학습률을 적절하게 조절합니다. 이를 통해 더 안정적인 학습이 가능하며, AdaGrad보다는 더 넓은 범위의 학습률을 유지할 수 있습니다.

6. Adam (Adaptive Moment Estimation)

   Adam은 RMSProp과 모멘텀 방식을 결합한 알고리즘으로, 현재 그래디언트와 이동 평균을 사용하여 학습률을 조절합니다. Adam은 그래디언트의 일반적인 모멘텀을 추정하고 그래디언트의 크기와 방향을 조정하여 매개변수 업데이트를 수행합니다. 이를 통해 빠른 수렴과 안정적인 학습을 동시에 달성할 수 있습니다. Adam은 다양한 유형의 최적화 문제에서 효과적이며, 기본적으로 많이 사용되는 알고리즘 중 하나입니다.

7. 유전 알고리즘 (Genetic Algorithm)

   유전 알고리즘은 위에 신경망 알고리즘과 다른 형태의 모델입니다. 다소 전통적인 모델이며 생물의 진화 원리를 모방한 메타휴리스틱 알고리즘입니다. 개체의 유전자 조합을 사용하여 후보 해집단을 생성하고, 이를 평가하고 선택 및 변형하여 최적해를 찾아냅니다. 해의 다양성을 유지하면서 전역 최적해를 찾는 데 효과적입니다. 다만 함수 복잡도에 따라 수렴이 느려질 수 있습니다.

이번 할인쿠폰 최적화의 경우 조건 최적화 문제입니다. 이는 연속 함수를 학습하는 문제가 아니라 시스템의 입력 변수와 제약 조건에 대해 최적해를 찾는 문제입니다. 따라서 신경망 알고리즘을 굳이 사용할 필요는 없어 보입니다. 그러나 유전 알고리즘은 제약 조건을 고려한 적합도 함수를 최대화하는 해를 찾는 데 특화되어 있습니다. 즉, 문제의 복잡성, 해의 다양성, 문제의 목적에 따라 유전 알고리즘이 기타 신경망 알고리즘보다 더욱 적합해보입니다. 따라서 이번 할인쿠폰 최적화 문제의 경우는 유전 알고리즘을 사용해서 분석해보도록 하겠습니다.

02. 데이터 수집 및 예상 사용률 구하기

회사에서 데이터 수집을 하려고 보니 생각보다 쿠폰의 형태가 매우 다양하다는 것을 깨달았습니다. 먼저 쿠폰에서 다양한 카테고리가 설정되어 있는 것이 있고 제외 상품조건이 있는 것이 있습니다. 그보다 더 큰 문제는 쿠폰이 모든 사용자(고객)에게 제공되지는 않는다는 점입니다.

일부 쿠폰은 모두가 다운로드 받을 수 있게 되어있거나 자동으로 제공되는 반면, 고객이 직접 다운로드 받아야 하거나 혹은 일부 고객을 한정으로 제공되는 쿠폰이 있습니다. 사실 전자보다는 후자가 대부분을 차지합니다. 이 때, 이러한 쿠폰을 바탕을 그냥 사용률을 사용하려고 하니 이러한 점들이 어렵다는 것을 깨달았습니다. 쿠폰 사용률을 바탕으로 최적화 모델을 생성할 시, 해당 사용률이 편향돼서 들어갈 수 있는 문제가 있는데 이를 해결하기 위해서는 기존 쿠폰들의 과거 데이터, 즉 실제 사용률이 아니라 가상의 고객군에게 모두 동일하게 제공 시 예측되는 사용률(이하 예측 사용률)을 가지고 최적화를 진행해야 원하는 결과값을 얻을 수 있을 것이라 생각하였습니다. 따라서 최적화에 앞서 쿠폰 데이터 및 예측 사용률을 구하는 것이 우선시되어야 했습니다.

다만 너무 구체적인 대상에게만 제공되었던 쿠폰 데이터는 가상의 고객풀에 대해서 예측 사용률을 도출하기에 적합하진 않았습니다. 워낙 데이터가 편향되어 있었기 때문에 예측 사용률 또한 평가 상 좋게 나오지는 않았습니다. 따라서 저는 이번에는 일단 최대한 고객 조건이 없이 다운로드 받을 수 있던 쿠폰들 위주로 데이터를 수집해 먼저 해당 형식의 쿠폰에 대해서만 최적화 모델을 생성하기로 했습니다. 이에 대해서는 랜덤 포레스트 모델을 사용하여 예측 사용률을 계산하였고 이를 바탕으로 최적화 알고리즘을 진행하기로 했습니다.

03. 최적화 모델 생성하기

실제로 사용한 유전 알고리즘을 최대한 간략하게 작성해보자면 아래와 같습니다.

import random
import numpy as np
from deap import creator, base, tools, algorithms

먼저 사용해야 할 라이브러리를 불러오겠습니다. 이 중에서 생소한 것은 아마 deap일텐데 이는 유전 알고리즘을 사용하기 위해 불러와야 하는 라이브러리입니다. 이 때 deap는 DEAP(Distributed Evolutionary Algorithms in Python)를 의미합니다.

# 2. 적합도 함수 정의
def fitness_function(coupon):

    discount_rate, min_purchase_amt, max_discount_amt = coupon
    
    # 적합도 계산: 가상 데이터에서 특정 쿠폰 조건과 유사한 데이터의 사용 건수 합계
    similarity = np.abs(coupons_data[:, :-1] - coupon).sum(axis=1)
    sum_of_uses = (coupons_data[:, -1] * (1 / (similarity + 1))).sum()
    
    return sum_of_uses,

그리고 유전 알고리즘에서 중요한 적합도 함수를 정의하게 됩니다. 적합도 함수는 유전 알고리즘에서 각 개체가 얼마나 적합한지를 평가하는 함수입니다. 적합도 함수는 개체의 품질을 측정하고, 이를 기반으로 개체를 선택, 교차, 변이 등의 유전 연산을 수행합니다. 이러한 유전 연산은 개체의 품질을 개선하고, 다음 세대에 더 좋은 개체를 생성하는 데 기여합니다. 이 때 좋은 적합도 함수를 생성하는 것이 매우 중요한데 좋은 적합도 함수를 선택하면 유전 알고리즘이 빠르게 최적의 해에 수렴할 수 있습니다.

위 적합도 함수는 쿠폰의 할인율(discount_rate), 최소 구매 금액(min_purchase_amt) 및 최대 할인 금액(max_discount_amt)을 입력으로 받습니다. coupons_data에서 쿠폰 조건과의 유사도를 계산하고, 그 값을 더합니다. 여기서 유사도는 입력 쿠폰과 coupons_data의 각 행 사이의 차이의 절댓값의 합입니다. 따라서 유사도가 작을수록 입력 쿠폰과 해당 데이터의 조건이 유사하다는 의미입니다.

유사도 값은 1을 더한 후 역수를 취하여 사용됩니다. 이렇게 함으로써 유사도 값이 작을수록 큰 값을 갖게 되고, 유사도 값이 크면 작은 값을 갖게 됩니다. 이는 유사한 조건을 갖는 데이터의 사용 건수에 대한 가중치를 높여주는 역할을 합니다. 마지막으로, coupons_data의 각 행의 사용 건수와 가중치를 곱한 값들을 합산하여 최종적인 쿠폰의 적합도를 계산합니다. 결과는 튜플 형태로 반환됩니다.

# 3. DEAP 라이브러리 과정 설정

# 최대화 문제로 설정 (적합도를 최대로 하는 해 찾기)
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

toolbox = base.Toolbox()
toolbox.register("attr_discount_rate", random.uniform, 0.01, 0.99)
toolbox.register("attr_min_purchase_amt", random.uniform, 1, 100000)
toolbox.register("attr_max_discount_amt", random.uniform, 1, 100000)

# 개체 초기화: 할인율, 최소 구매 금액, 최대 할인 금액 값을 튜플로 초기화
toolbox.register(
    "individual",
    tools.initCycle,
    creator.Individual,
    (toolbox.attr_discount_rate, toolbox.attr_min_purchase_amt, toolbox.attr_max_discount_amt),
    n=1,
)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=[0.0, 0.0, 0.0], sigma=[0.1, 1000, 1000], indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", fitness_function)

위 코드는 간단하게 적은 유전 알고리즘 코드입니다. 실제로 사용 시에는 위처럼 사용하지 마시고 실제 파라미터 값과 데이터를 조정하시면 됩니다.

먼저, creator 객체를 사용하여 FitnessMax 클래스와 Individual 클래스를 생성합니다. FitnessMax 클래스는 최대화 문제를 위한 적합도 클래스로 설정되며, Individual 클래스는 개체를 나타내는 리스트입니다. Individual 클래스는 FitnessMax 클래스로 적합도를 가집니다. individual 함수는 개체를 초기화하는 역할을 수행합니다. tools.initCycle을 사용하여 creator.Individual 클래스에 attr_discount_rate, attr_min_purchase_amt, attr_max_discount_amt 값을 튜플로 초기화합니다. n=1은 개체를 한 번에 하나씩 생성한다는 의미입니다. population 함수는 초기 개체 집합(개체의 모음)을 생성합니다. toolbox.individual 함수를 사용하여 creator.Individual 클래스의 개체를 생성하고, tools.initRepeat를 사용하여 해당 개체를 반복하여 리스트로 만듭니다.

유전 알고리즘에서 사용되는 다른 함수들도 등록됩니다. mate 함수는 두 개체 간의 교차(crossover)를 수행합니다. mutate 함수는 개체의 돌연변이(mutate)를 적용합니다. select 함수는 토너먼트 선택(tournament selection)을 사용하여 개체를 선택합니다. evaluate 함수는 앞서 정의한 적합도 함수인 fitness_function을 호출하여 개체의 적합도를 계산합니다.

# 4. 유전 알고리즘 적용 및 결과 출력

population = toolbox.population(n=100)
ngen = 100
cxpb, mutpb = 0.7, 0.3

result, log = algorithms.eaSimple(population, toolbox, cxpb=cxpb, mutpb=mutpb, ngen=ngen, verbose=False)
best_coupon = tools.selBest(result, k=1)[0]

먼저 초기 개체 집합인 population을 생성합니다. toolbox.population(n=100)은 toolbox에 등록된 individual 함수를 사용하여 개체를 생성하고, n 인자를 통해 개체의 수를 지정합니다. 이 경우에는 100개의 초기 개체가 생성됩니다.

ngen 변수는 진행할 세대(generation)의 수를 나타냅니다. cxpb는 교차 확률(crossover probability)로, 두 개체가 교차 연산을 수행할 확률을 나타냅니다. mutpb는 돌연변이 확률(mutation probability)로, 개체의 돌연변이가 발생할 확률을 나타냅니다.

algorithms.eaSimple 함수는 DEAP 라이브러리에서 제공하는 간단한 유전 알고리즘을 실행합니다. population은 초기 개체 집합을 나타내며, toolbox는 등록된 함수들을 포함한 도구 모음을 제공합니다. cxpb, mutpb, ngen은 앞서 설정한 교차 확률, 돌연변이 확률, 그리고 진행할 세대의 수입니다. verbose=False는 상세한 출력을 비활성화하는 매개변수입니다.

tools.selBest(result, k=1)는 result에서 적합도가 가장 높은 개체를 선택하는 함수입니다. k=1은 가장 높은 적합도를 가진 개체를 1개 선택한다는 의미입니다. 선택된 개체는 best_coupon 변수에 할당됩니다.

위와 같은 코드를 바탕으로 최적의 쿠폰할인율, 최소주문금액, 최대할인금액을 구할 수 있습니다.

04. 후기 및 피드백

사실 위 유전 알고리즘은 매우 기초적인 단계입니다. 먼저 이 작업을 진행하면서 깨닫게 된 문제점이 많습니다.

1. 쿠폰에는 더 다양한 속성들이 있다.
   대표적으로 쿠폰의 사용기한, 다운로드 기간이 존재합니다. 같은 속성의 쿠폰이라도 사용기한이 길다면 사용률이 더 높아질 수 있습니다. 따라서 이러한 조건 또한 유전알고리즘에 포함시켜야 합니다.
2. 쿠폰의 카테고리의 다양성
   보통 일반적으로 이커머스에서 쿠폰을 생성할 때 적용 카테고리가 존재합니다. 예를 들어 화장품 전용, 혹은 패션 전용, 혹은 신선식품 전용 등으로 말입니다. 그러나 이러한 조건은 매우 복잡합니다. 이번에는 이러한 속성을 무시하고 진행했지만 이 특성이 사용률에 미칠 영향은 매우 클 것으로 예상됩니다. 해당 특성과 사용률 등 다양한 쿠폰의 속성과 사용률 간 상관관계 분석을 추가로 진행해야 할 듯 합니다.
3. 데이터양의 부족
   이번에는 전체적인 틀을 생성하기 위해서 데이터 전체 양이 절대적으로 부족했습니다. 그러나 쿠폰 데이터를 전처리하는데 너무 오랜 시간이 걸리고 레거시가 복잡해서 이번에는 적은 데이터로만 진행했으나 모델을 고도화하기 위해서는 더 많은 데이터가 필요할 듯 합니다.

위 문제를 해결해가면서 유전 알고리즘을 고도화 시켜야하는 필요성이 존재합니다. 또한 유전 알고리즘 자체가 자주 사용되는 알고리즘이 아니다보니 이 알고리즘을 설명하는데 더 많은 시간이 소요되었습니다. 다음 블로그 게시글로는 이 유전 알고리즘이 어떻게 작동하는 것인지에 대해서 더 자세히 다뤄보는 것이 좋을 듯 합니다.

---

Reference.

하용호, 자습해도 모르겠던 딥러닝, 머리속에 인스톨 시켜드립니다
컬리 테크 블로그, 컬리는 물류 최적화 문제를 어떻게 풀고 있을까? - 1부