최근 온라인을 통한 소비 활동이 기존의 가전, 생활용품 등을 넘어 음·식료품 및 음식서비스까지 확대되고 있고, 시장 규모도 빠르게 증가하는 추세이다. 2021년 온라인 쇼핑 거래액은 약 193조 원으로 전년대비 약 21% 증가하였으며, 특히 음식서비스의 경우 거래액이 약 26조 원으로 총 거래액의 약 13%를 차지하고, 전년대비 약 48% 증가하였다(http://kostat.go.kr). 또한, 음·식료품(약 26% 증가) 및 가전·전자·통신기기(약 26% 증가)의 경우도 시장 규모가 빠르게 증가하고 있고, 코로나 팬데믹의 장기화는 온라인 소비 활동의 증가를 가속시켰다. 이와 같은 온라인 시장 규모의 확대에 발맞춰 광고 시장에서도 디지털 광고의 중요성이 강조되고 있다. 2021년 국내 광고 시장의 규모는 약 14조 원으로, 이 중에서 디지털 광고 시장이 약 54%의 점유율을 차지하고 있다. 특히, 디지털 광고 시장은 전년대비 약 32% 성장하였고, 2022년에도 성장세를 유지할 것으로 예상하고 있다(https://www.cheil.com/). 디지털 광고는 크게 소비자 인지도 향상을 주 목적으로 하는 브랜드 마케팅과 전환 향상을 주 목적으로 하는 퍼포먼스 마케팅으로 구분할 수 있다. 최근 데이터 과학에 대한 중요성이 강조되는 흐름에 따라 광고 시장도 데이터를 분석하여 목표를 수립하고 운영 및 최적화를 진행하는 퍼포먼스 마케팅 중심으로 전환되는 추세이다.

검색광고는 키워드 검색 시 파워링크, 쇼핑 검색 등 광고 영역에 홈페이지와 홍보 문구가 노출되는 상품으로 퍼포먼스 마케팅에서 가장 큰 비중을 차지하고 있다. 검색광고의 경우 광고주의 홈페이지를 눈에 띄는 영역에 보여주고, 소비자의 관심이 검색 키워드에 반영되어 있어 광고 효과가 높게 나타난다(Jerath et al., 2011). 광고주는 대상 키워드들과 키워드별 입찰가를 등록하고, 소비자가 특정 키워드를 검색하면 해당 키워드를 등록한 광고주들의 경매 과정을 거쳐 광고 영역에 홈페이지가 노출된다. 홈페이지의 노출 순서는 광고주들의 입찰가 순서를 따르고, 입찰은 비밀입찰을 기본으로 한다(Kamijo, 2013). 소비자는 광고를 통해 특정 광고주의 홈페이지에 방문하게 되고, 소비자의 방문 횟수에 따라 해당 광고주에게 비용이 청구된다. 따라서, 소비자의 검색 의도를 반영한 키워드 발굴과 비용 효율적인 입찰가 설정은 검색광고 운영의 핵심 요소이다. <Figure 1>은 검색광고 운영에 대한 개념도를 나타낸다. 검색광고에 대한 자세한 설명은(Jansen and Mullen, 2008)에 기술되어 있다.

Figure 1. 
Process Diagram of the Search Engine Marketing

현재 국내 검색광고 시장은 주요 대행사들을 중심으로 전문인력에 의한 운영 구조가 지속되고 있다. 광고주들은 대행사들에 검색광고 운영을 위임하고, 매체 종류에 따라 대행사들은 다양한 수익구조를 갖는다. 예를 들어 국내 최대 검색광고 매체의 경우 광고비에 대한 수수료를 공식대행사들에게 지급하고, 대행사들은 한정된 수수료 내에서 운영 업무를 수행한다. 검색광고는 일반적으로 10,000~100,000개까지의 키워드를 운영하고, 다수의 운영 지표들이 존재한다. 주요 운영 지표로는 클릭수, 클릭당 비용, 클릭률, 유입수, 전환수, 전환당 비용, 전환율 등이 있고, 광고주의 요청에 따라 선별적으로 관리한다. 다수의 키워드 및 운영 지표와 더불어 시간 단위의 관리 주기를 갖는 산업 특성으로 인해 한정된 전문인력 기반의 운영 방식은 한계가 존재하고, 따라서 핵심 키워드 위주의 제한적 관리 방식이 일반적으로 활용되고 있다. 또한, 전문인력 기반의 운영 방식은 결과의 질적 일관성 측면에서도 한계점이 존재한다. 본 논문에서는 전문인력 기반 운영 방식의 한계점을 극복하고, 운영 효율성의 극대화를 목표로 하는 검색광고 최적화 시스템을 소개한다. 소개하는 시스템은 검색광고 운영의 두 가지 핵심 요소인 키워드 관리와 입찰가 설정에 대한 가이드를 제공한다.

본 논문의 나머지 구성은 다음과 같다. 제2장에서는 기존 연구에 대해 소개한다. 제3장에서는 키워드 효율성 분석 모델을 제시한다. 제4장에서는 키워드 입찰가 최적화를 위한 데이터 추정 과정, 최적화 모델, 그리고 모델을 해결하기 위한 반복적 접근방식을 제시한다. 제안된 시스템에 대한 적용 결과는 제5장에서 보고하고, 마지막으로 제6장은 결론을 제시한다.

키워드 검색 시 광고 영역에 홈페이지와 홍보 문구가 보여지는 것을 노출(Impression)이라고 한다. 노출은 키워드가 등록되면 노출 순위(Rank)에 무관하게 집계되기에 소비자들이 결정하는 키워드 자체의 특성이라고 해석할 수 있다. 검색 키워드에 대한 노출이 발생하고, 클릭(Click)을 통해 광고주의 홈페이지에 소비자가 방문한 후, 다음 단계로 전환(Conversion)이 발생한다. 전환은 회원가입, 장바구니 등록, 실제 구매 등과 같이 다양한 기준을 활용한다. 마지막으로, 광고 목표에 따라 매출(Sales)까지 관리할 수 있다. 검색광고에 대한 영향 관계도(Influence diagram)는 Küçükaydin et al.(2020)에 기술되어 있다. 일반적으로 노출을 제외한 모든 운영 지표는 입찰가를 시작으로 연쇄적으로 영향을 받고, 따라서 입찰가는 검색광고의 의사결정 변수로 광고 효율성에 가장 큰 영향을 미친다. Yang et al.(2019)의 경우 노출 순위를 의사결정 변수로, 순위에 따른 입찰가를 역으로 추정하는 새로운 검색광고 모델을 재정의하여 제시하였다. 본 논문에서는 Küçükaydin et al.(2020)의 영향 관계도를 기반으로 국내 검색광고 시장을 반영하여 매출을 전환과 매출 두 단계로 세분화하여 고려한다. 영향 관계도에 대한 개념도는 <Figure 2>와 같다.

Figure 2. 
Influence Diagram of the Keyword Bidding Model

본 논문에서 다루는 키워드 관리에서는 관리 편의성 향상을 목표로 하는 키워드 효율성 분석 모델을 제안한다. 효율성 분석 모델은 다목적(Multi-objective) 운영 지표를 반영하기 위해 자료 포락 분석법(Data envelopment analysis)에 기반하고, 특히 클릭률, 전환율과 같은 비율 지표를 고려한다. 자료 포락 분석법은 투입과 산출이 있는 의사 결정 단위(Decision making unit)의 상대적 효율성을 측정하는 비모수적 방법론(Non-parametric method)으로, Charnes et al.(1978)이 제시한 이후로 많은 연구가 진행되고 다양한 분야에서 활용되고 있다. 대표적인 모델로는 Charnes et al.(1978)이 제안한 CCR 모델과 Banker et al.(1984)이 제안한 BCC 모델이 있다. 자료 포락 분석법은 금융, 보건, 농업, 교통, 그리고 교육 분야 등에서 활발하게 활용되고 있다(Liu et al., 2013). 자료 포락 분석법에 대한 조사는 Liu et al.(2013)과 Emrouznejad and Yang(2018)에서 찾을 수 있다. 자료 포락 분석법은 보통 절대적 수치 데이터를 기반으로 적용되는데, 분야에 따라 비율 데이터를 활용하는 경우도 나타난다(Emrouznejad and Amin, 2009). Hollingsworth and Smith(2003)는 비율 지표가 존재할 경우 CCR 모델보다 BCC 모델이 적합하다고 발표하였고, Emrouznejad and Amin(2009)은 비율 지표를 다루기 위한 자료 포락 분석 모델들을 제시하였다.

키워드 입찰가 설정은 검색광고 운영의 핵심 의사결정 요소임에 따라 입찰가 최적화에 대한 연구가 다양한 측면에서 진행되었다. 다수의 연구가 주어진 예산에 대하여 목표를 최대화하는 예산 최적화(Budget optimization) 문제 형태로 진행되었다. Özlük and Cholette(2007)는 검색광고에 대한 최적화 기반의 초기 연구 중 하나로 기대수익을 최대화하기 위한 확정적 비선형 모델을 제안하였다. Feldman et al.(2007)은 주어진 예산에 대하여 소비자 클릭을 최대화하는 문제에 대해 연구하였다. 연구를 통해 입찰가 결정을 위한 단일 전략(Uniform strategies)을 제시하였고, 실험을 통해 이에 대한 실용성을 확인하였다. Cholette et al.(2012)은 주어진 예산에 대하여 광고주의 기대수익을 최대화하는 확률적 모델을 제시하였다. Abhishek and Hosanagar(2013)도 예산제약 하에 기대수익을 최대화하는 모델을 제시하였다. 또한, 키워드 간의 상호작용을 고려하여 모델을 확장하였고, 실제 실험을 통해 제안한 모델들의 효과를 확인하였다. Selçuk and Özlük(2013)의 경우는 광고에 대한 목표 노출을 제약으로, 광고비를 최소화하는 확정적 최적화 모형을 제시하였다. 검색광고 최적화가 적용된 시스템에 대한 성공 사례는 Skiera and Abou Nabout(2013)에서 찾을 수 있다.

제안하는 시스템의 키워드 효율성 분석은 키워드의 광고비를 단일 투입 지표로, 그리고 나머지 운영 지표들을 다중 산출 지표로 정의하여 자료 포락 분석법을 적용한다. 특히, 비율 지표를 다루기 위해 Emrouznejad and Amin(2009)가 제안한 모델을 활용한다. 모델을 통해 관리 의사결정이 필요한 키워드를 자동으로 선별하여 전문인력의 관리 편의성을 극대화한다. 입찰가 설정에서는 다수의 연구가 키워드 입찰가 최적화를 다루고 있지만, 대부분의 경우 클릭, 전환, 기대수익과 같은 단일 목표 관점에서 방법론을 제안하고 있다. 하지만 국내 검색광고 시장의 광고주들은 많은 경우 다수의 운영 목표를 제시하고 있고, 대행사들의 경우 다중 목적 관리에 많은 인력이 투입되고, 또한 효율성 확보에 어려움을 겪고 있다. 따라서, 제안하는 시스템은 다수의 운영 목표를 다루기 위한 다목적 이진 계획 모델(Multi-objective binary programming model)을 제안한다. 또한, 제안하는 모델이 갖는 다목적과 비선형 제약(Non-linear constraint)을 다루기 위한 반복적 알고리즘(Iterative algorithm)을 제시한다. 마지막으로, 제안하는 시스템에 대한 검증을 위해 실제 운영에 시스템 결과를 적용하여 효용성을 확인한다. 본 논문은 국내 검색광고 시장의 특성을 반영한 데이터 기반 운영 방법론을 제시하고, 실제 운영 실험까지 거쳐 시스템의 효용성을 확인한 측면에서 기여도를 갖는다.

본 장에서는 키워드 효율성 분석 모델에 대해 기술한다. <Figure 2>와 같은 영향 관계도 아래 광고주는 다양한 운영 지표를 기반으로 광고를 관리하고, 이에 대한 효율성을 평가한다. 운영 지표는 크게 절대 지표(Absolute performance indicator)와 비율 지표(Ratio performance indicator)로 구분할 수 있다. 절대 지표는 값, 수량으로 나타나는 지표로, <Figure 2>에서 나타나는 노출수, 클릭수, 전환수, 매출 등을 포함한다. 비율 지표는 절대 지표들의 비율 값으로 계산되는 지표로, 확률값 관련 지표로는 클릭률, 전환율 등이 있고, 비용 및 매출 관련 지표로는 클릭당 비용, 전환당 비용, 광고비 대비 매출액 등이 있다. 이 밖에도 다양한 지표들이 존재하고, 광고주들은 광고의 목적에 따라 선별적으로 운영 지표들을 사용한다. 예를 들어, 홈페이지 오픈, 브랜드 런칭 시에는 초기 소비자 유입 확보를 위해 클릭 관련 지표를 중점적으로 사용한다. 또한, 기업 홈페이지와 같이 브랜드가 중요한 광고주들도 유입 확보를 위해 클릭 관련 지표로 광고를 운영한다. 반대로, 쇼핑, 금융, 교육과 같이 광고의 궁극적인 목적이 매출로의 연결인 경우는 전환과 매출 관련 운영 지표들을 주로 활용한다. 본 논문에서 제안하는 시스템은 보편적으로 활용되는 운영 지표를 대상으로 하지만 모델 및 알고리즘은 쉽게 확장 가능하다. 제안하는 시스템에서 고려하는 운영 지표는 <Table 1>과 같다.

<Table 1>과 같이 다수의 운영 지표가 관리됨에 따라 광고주들의 목표도 다수의 지표가 혼재되어 있고, 상쇄관계(Trade-off)에 있는 목표 설정으로 인해 운영 관리의 어려움이 더해진다. 예를 들어, 광고주가 클릭당 비용을 최소화하면서 클릭수를 최대화하는 목표를 가질 경우, 클릭당 비용을 줄이기 위해 입찰가를 내리면 노출 순위가 낮아져 클릭수도 줄어드는 현상이 나타난다. 수리적 분석 및 모델 개발 측면에서도 상쇄관계에 대한 가중치 등의 명확한 관계가 존재하지 않아 목표 운영 지표들을 단일 목적(Single-objective)으로 변환하는데 어려움이 있다. 따라서, 이와 같은 다목적 환경을 다루기 위해 자료 포락 분석법에 기반한 효율성 평가 모델을 제안한다. 특히, Emrouznejad and Amin(2009)가 제안한 모델을 활용하여 비율 지표를 반영한다. 제안하는 모델은 다음과 같다.

• 파라미터
• K: 키워드의 집합
• x_k: 키워드 k의 광고비
• y_rk: 키워드 k의 운영 지표 r에 대한 결과값

• 결정변수
• λ_k: 키워드 k에 대한 조합 변수
• θ: 분석 대상 키워드의 효율성

• 키워드 효율성 분석 모델
• 효율성 분석 대상 키워드 k^*에 대하여:

키워드 효율성 분석 모델은 선형 계획 모델(Linear programming model)로, 키워드들의 볼록 조합(Convex combination)으로 분석 대상 키워드의 운영 지표를 만족하는 최소 광고비를 산출하고, 이를 바탕으로 분석 대상 키워드의 효율성을 평가한다. 목적식 (1)은 운영 지표를 만족하는데 필요한 분석 대상 키워드의 광고비 비율을 나타내고, 이를 최소화하여 최소 비용을 산출한다. 예를 들어 θ = 0.7일 경우 대상 키워드가 사용한 광고비의 70%만 사용하여도 동일한 효과를 가져올 수 있는 키워드들의 조합이 존재함을 의미하고, 해당 수치를 대상 키워드의 효율성으로 평가한다. 제약식 (2)는 키워드들의 조합에 의한 광고비와 대상 키워드의 광고비 간의 관계를 나타낸다. 대상 키워드의 광고비에 효율성 변수를 곱해 목적식에서 최소화함으로써 최소 광고비를 산출한다. 제약식 (3)은 절대 지표들에 대한 관계를 나타낸다. 절대 지표는 노출수, 클릭수, 전환수, 매출로 구성되는 최대화 지표로 모두 대상 키워드의 성과 이상을 달성해야 한다. 비율 지표는 키워드들의 조합으로 산출되는 절대 지표의 비율 값으로 표현되고, 최대화 지표와 최소화 지표로 구분할 수 있다. 최대화 지표는 제약식 (4), (5), (6)에 각각 클릭률, 전환율, 광고비 대비 매출액이 표현되어 있다. 예를 들어 클릭률은 클릭수/노출수로 표현되고, 해당 값이 대상 키워드의 클릭률 이상이어야 한다. 최소화 지표는 제약식 (7), (8)에 각각 클릭당 비용, 전환당 비용이 표현되어 있다. 예를 들어 클릭당 비용은 광고비/클릭수로 표현되고, 해당 값이 대상 키워드의 클릭당 비용 이하여야 한다. 제약식 (9), (10)은 볼록 조합 조건을, 제약식 (10)은 변수의 범위(Domain)를 나타낸다.

효율성 분석 기반 키워드 분류

검색광고에서 대상 키워드 집합 조정에 고려하는 요소는 크게 두 가지가 있다. 첫 번째는 키워드에 대한 효율성이고, 두 번째는 키워드의 광고비 규모이다. 키워드 효율성의 경우 광고비 대비 효율성을 측정하기에 광고비의 절대적 규모는 반영되지 않는다. 따라서, 효율성만 고려하여 키워드를 운영할 경우 극단적으로 규모가 아주 작고 효율이 높은 키워드들만 선정될 수 있고, 이럴 경우 광고비 소진과 더불어 절대적인 광고 효과의 규모가 작아질 수 있다. 이와 같은 이유로 실제 운영에서는 두 가지 요소를 모두 고려하여 대상 키워드 집합을 조정한다. <Figure 3>은 두 가지 요소에 따른 키워드 분류를 나타낸다.

Figure 3. 
Keyword Classification by Efficiency and Volume

실제 검색광고 운영 상황에서는 키워드 자유 입찰 경쟁 환경으로 인해 고효율 대규모 키워드는 희소하게 나타난다. 저효율 대규모 키워드는 냉장고, 자동차, 휴대폰 등과 같이 사용자가 일반적으로 검색하는 보통명사 형태의 대표 키워드를 포함하고, 고효율 소규모 키워드는 검색광고를 진행하는 광고주의 브랜드명 등이 포함된 브랜드 특화 키워드를 포함한다. 이와 같은 유형의 키워드는 전체 키워드에서 소수(약 10% 미만)를 차지하고, 주요 시간대의 실시간 검색 순위를 높여 광고주의 브랜드 노출을 목적으로 하기 때문에 광고 운영 전문인력이 전략적으로 입찰가를 변경 관리하는 경우가 많다. 저효율 소규모 키워드는 운영되고 있는 전체 검색 광고 키워드의 대다수(약 90% 이상)를 차지하고 있으며, 최대 수만 개에 달하는 키워드를 운영 관리하는데 어려움이 있다. 관리의 어려움으로 인해 현실에서는 주로 간헐적인 관리 주기를 가지는데, 이로 인해 관리의 효율성 확보가 어렵고 전체 광고 실적에 악영향을 주게 된다. 제안하는 시스템은 전문인력에 의한 관리가 어려운 저효율 소규모 키워드 그룹을 주 대상으로 하여 입찰가 최적화 알고리즘을 적용하고, 최적화를 통해 전체 광고 실적 목표를 달성하고 운영 효율성을 향상시킨다.

본 장에서는 키워드 입찰가 최적화 모델 및 알고리즘에 대해 기술한다. 키워드 효율성 분석과 같이 입찰가 최적화도 다목적 최적화(Multi-objective optimization)에 대한 고려가 필수적이다. 특히, 본 논문에서 제안하는 시스템은 국내 검색광고 시장에서 발생하는 요구를 반영하여 두 가지 종류의 목표 설정 기능을 제공한다. 첫 번째는 목표 만족 설정으로 광고주가 설정한 운영 지표들의 목표 값들을 동시에 만족하는 기능이고, 두 번째는 우선 순위 설정으로 우선 순위에 따라 운영 지표를 극대화하는 기능이다. 두 가지 목표 설정 기능을 조합하여 복합적인 광고 운영이 가능하다. 예를 들어 광고주가 클릭수, 전환수, 그리고 노출수에 대해 목표 값을 설정하고, 마찬가지로 해당 순서로 우선 순위를 설정할 수 있다. 최적화 과정은 목표 만족 최적화, 우선 순위 최적화 순서로 진행되며, 이전 단계의 최적성을 보장하는 계층적 접근방식(hierarchical approach)을 따른다. 목표 만족 최적화의 경우 운영 지표들의 목표 값들을 동시에 만족하는 해가 존재하지 않을 수 있고, 이와 같은 경우 목표 값들을 최대한 균등하게 달성하는 해를 도출한다. 균등한 달성은 목표 값들에 대한 달성치들의 최소값을 최대화하여 특정 운영 지표에 편향된 결과를 방지하는 것을 의미한다. 우선 순위 최적화에서는 우선 순위에 따라 운영 지표의 최대 달성치를 도출한 후, 해당 달성치를 유지하는 조건하에 차순위 목표에 대한 최적화를 수행한다. <Figure 4>는 최적화 과정에 대한 예시를 나타낸다.

Figure 4. 
An Optimization Process Example

입찰가 최적화 모델의 의사결정 변수는 두 가지 방향으로 고려할 수 있다. 첫 번째는 입찰가를 연속 변수(Continuous variable)로 정의하여 입찰가에 따른 운영 지표 함수를 추정하는 방법이고, 두 번째는 입찰가를 이산화(Discretize)하여 입찰가 후보군에 대한 이진 변수(Binary variable)를 정의하고, 이에 대한 운영 지표 값을 추정하는 방법이다. 이산화의 경우 입찰가에 대한 해 탐색 공간이 축소되는 단점이 있지만, 입찰가를 연속 변수로 정의할 경우 현실 데이터를 반영하여 운영 지표 함수를 추정하는데 어려움이 따른다. 예를 들어 Park et al.(2020)의 경우 다매체 광고 예산 배정 최적화 모형에 대하여 수확체감의 법칙(Law of diminish returns)에 기반한 로그함수를 활용하였다. 이론적인 합리성에도 불구하고 키워드 단위의 추정 과정에서는 키워드에 따라 데이터가 희소한 문제와 과거 데이터의 입찰가 설정에 따라 편중된 데이터 형태가 나타나는 문제가 있다. <Figure 5>는 낙찰가의 분포에 대한 예시이다.

Figure 5. 
A Bidding Price Distribution Example

이와 같은 현실 데이터의 특성을 고려하여 제안하는 최적화 모델은 각 키워드 별로 입찰가 후보군을 생성하고, 후보군 중 최종 입찰가를 선택하는 접근방식을 따른다. 입찰가 후보군 생성은 군집화(Clustering) 방법론을 활용하고, 군집별로 대표 입찰가와 운영 지표 추정치를 산출한다. 또한, 군집화 된 입찰가 외의 영역에 대한 탐색을 위해 보간법(Interpolation)을 기반으로 군집 간의 입찰가 후보군을 추가 생성한다. 운영 지표에 대한 추정은 데이터의 크기 및 특성에 따라 회귀분석(Regression)에 기반한 추정과 변동점(Change point)에 기반한 추정을 선별적으로 사용한다. 노출수는 과거 동일 요일 및 시간대의 노출수와 유사한 패턴이 반복적으로 나타나는 특성이 있다. 이러한 특성을 반영하여 요일 및 시간대 별 노출수 데이터로 키워드 별 노출수를 회귀분석을 활용하여 추정한다. 또한 클릭률의 경우 입찰가에 따라 발생하는 노출 순위의 변동으로 인해 확률값의 변화가 나타나므로, 키워드, 입찰가 별 클릭률을 회귀분석을 활용하여 추정한다. 전환율과 전환당 매출의 경우 일반적으로 데이터가 매우 희소하게 나타남에 따라 키워드, 입찰가 별 추정에 어려움이 따른다. 제안하는 시스템에서는 키워드 데이터를 통합하여 추정하고, 특히 변동점을 추출하여 최근 데이터 그룹의 대표값을 사용하는 접근방식을 활용한다. 개략적인 데이터 추정 과정은 <Figure 6>에서 확인할 수 있다.

Figure 6. 
The Data Estimation Process

제안하는 입찰가 최적화 모형은 다음과 같다.

• 파라미터
• K : 키워드의 집합
• R : 운영 지표의 집합
• C : 입찰가 후보군의 집합
• C_k : 키워드 k의 입찰가 후보군의 집합
• b : 총 예산
• τ_r : 운영 지표 r의 목표 값
• x_i : 입찰가 후보군 i의 광고비
• y_r,i : 입찰가 후보군 i의 운영 지표 r에 대한 결과값
• 　
• 결정변수
• λ_i : 입찰가 후보군 i에 대한 선택 변수
• ρ_r : 운영 지표 r의 만족도 변수
• 　
• 키워드 입찰가 최적화 모델

키워드 입찰가 최적화 모델은 비선형 이진 계획 모델(Non-linear binary programming model)로, 최적해(Optimal solution)를 도출하기 어려운 문제(NP-hard)로 알려져 있다. 제안하는 모델은 운영 지표들의 목표 값들을 동시에 만족하는 해가 존재하지 않는 경우를 고려하여 운영 지표 만족도 변수 ρ_r, r∈R을 도입하고, 목표 값 대비 만족도를 최대화하는 접근방식을 따른다. 예를 들어 τ_CLICKS = 1000이고, 최적화 결과 ρ_CLICKS = 0.7=이라면, 목표 클릭수 1000에 대하여 70%, 즉 700의 클릭을 달성한 결과로 해석한다. 목적식 (11)은 다목적 최적화에 대한 목적 함수(Objective function)로, 각 목적 함수는 운영 지표의 만족도 변수 ρ_r, r∈R의 함수로 표현된다. 목표 만족 최적화의 경우 목표 값들에 대한 만족도들의 최소값의 최대화를 의미하고, 우선 순위 최적화의 경우 해당 운영 지표의 만족도를 목적 함수로 한다. 제약식 (12)는 광고비 예산 제약을 나타내고, 제약식 (13)은 절대 지표에 대한 만족도 관계를 나타낸다. 비율 지표 중 최대화 지표는 제약식 (14), (15), (16)에 각각 클릭률, 전환율, 광고비 대비 매출액이 표현되어 있고, 최소화 지표는 제약식 (17), (18)에 각각 클릭당 비용, 전환당 비용이 표현되어 있다. 최소화 지표의 경우 만족도 변수의 역수를 곱해 만족도가 증가할수록 목표 값이 감소하게 한다. 제약식 (19)는 키워드 별 입찰가 후보군 선택 조건을, 특히 예산 부족으로 인해 선택되지 못하는 경우를 반영한다. 제약식 (20), (21)은 변수의 범위를 나타낸다.

키워드 입찰가 최적화 모델의 비선형 제약식 (14)~(18)은 비율 지표와 지표 만족도 변수에 기인한다. 제안하는 시스템에서는 비선형 제약식으로 인한 해 도출의 어려움을 해결하기 위해 지표 만족도 변수를 모델에서 분리한다. 구체적으로, 지표 만족도를 매개변수(Parameter)로 하는 키워드 입찰가 가능해 모델을 정의하고, 지표 만족도를 반복적으로 개선하면서 해당 수치에 대한 실행가능성(Feasibility)을 입찰가 가능해 모델을 통해 확인한다. 키워드 입찰가 가능해 모델은 다음과 같다.

• 키워드 입찰가 가능해 모델
• 주어진 운영 지표 만족도 ρr*,r∈R에 대하여:

입찰가 최적화 과정에서 운영 목표의 설정에 따라 예산 소진 문제가 발생할 수 있다. 극단적인 예로 클릭률을 최대화하는 단일 운영 목표를 설정할 경우, 이 목표에 대한 최적해는 클릭률이 가장 높은 하나의 키워드로 나타난다. 따라서, 예산 소진의 하한 값에 대한 고려는 필수적이다. 최적화 모델에서 예산을 모두 사용하도록 제약을 설정할 수 있지만, 이는 데이터에 따라 해가 존재하지 않을 수 있다. 따라서, 최적화 과정의 전단계로 사용할 수 있는 예산의 최대값을 산출하고, 예산 사용량 제약을 제약식 (31)과 같이 추가한다. 또한, 예산 미사용에 대한 허용치를 설정하여 운영 지표 최적화의 탐색 영역을 확보한다.

• b^max : 최대 가능 예산 사용량
• δ : 예산 미사용 허용치(Tolerance)

반복적 탐색 알고리즘(Iterative search algorithm)은 <Figure 4>와 같이 운영 지표 만족도를 증가시키면서 실행가능성을 확인하고, 가능해가 없을 경우 해당 지표를 이전 단계의 만족도로 고정한다. 목표 만족 단계에서는 운영 지표들의 만족도를 균일하게 증가시키기 위해 현재 해의 만족도 지표들을 계산하여 최소값을 기준 만족도로 설정하고, 우선 순위에 따라 증분 단위만큼 만족도 증가가 가능한지 확인한다. 현재 해가 증가된 만족도를 충족하지 않을 경우만 키워드 입찰가 가능해 모델을 통해 확인한다. 가능할 경우 만족도를 증가시키고, 불가능할 경우 기준 만족도로 고정하고 향후 개선 과정에서 제외한다. 우선 순위 단계에서는 운영 지표들의 만족도를 우선 순위에 따라 최대한 증가시키고 고정한다. 우선 순위 최적화의 경우 절대 지표는 선형 함수로 표현되기에 지표를 목적식으로 한 최적화가 가능하지만, 비율 지표의 경우 비선형 목적식이 생성됨으로 단계적으로 만족도를 증가시키며 실행가능성을 확인하는 탐색 방법을 동일하게 적용한다.

탐색 측면에서 운영 지표 만족도의 증분 단위가 미세할수록 정교한 탐색이 가능하지만 입찰가 가능해 모델의 실행 회수가 증가한다. 예를 들어 5개의 운영 지표를 1% 단위로 0% ~ 100%까지 탐색할 경우, 최악의 경우 500번의 가능해 모델이 실행될 수 있다. 제안하는 시스템은 상용 최적화 솔버를 활용하여 구현되었고, 실제 운영 데이터에 대한 실험 결과 1초 내외의 시간으로 가능해 문제가 해결됨을 실험적으로 확인하였다. 이와 같은 실험을 기반으로 실제 구현은 1%의 증분 단위로 최적화 과정을 수행하여 현실적인 탐색의 정교함을 확보한다. 제안하는 반복적 탐색 알고리즘은 다음과 같다.

• 반복적 탐색 알고리즘
• [Setup]
• FPρr*:r∈R⟵the feasibility problem 22∼31
•              for ρr*,r∈R
•        where bmax=max∑i∈Cxiλi22,29,30
• ρr*⟵0,r∈R
• [Target search]
• T ⟵R
• while T ≠ ∅ do
• ρt*⟵the minimum of current indicator values in
• T, t∈T
• for all t∈T  do
•   ρt*⟵ρt*+0.01
•   if FPρr*:r∈R=∅then
•          ρt*⟵ρt*-0.01
•          T⟵T-{t}
•   else if ρt*≥1 then
•             ρt*⟵1
•             T⟵T-{t}
•     end if
•   end for
• end while
• [Priority search]
• for all t∈R do
•   while FPρr*:r∈R≠∅ do
•          ρt*⟵ρt*+0.01
•   end while
•   ρt*⟵ρt*-0.01
• end for
• return current solution

본 논문에서 소개한 시스템은 국내 최대 IT 기업에 구현되어 운영되고 있고, 실제 광고주의 광고 운영에 적용하여 시스템의 효용성을 확인하였다. 본 장에서는 실제 운영 결과에 대한 사례들을 소개한다. 인테리어 업종의 A사와 여행 업종의 B사를 대상으로 하고, 광고주에 대한 대외비 정보를 제외한 간략한 효과를 소개한다.

사례 1: 인테리어 업종 A사

인테리어 업계는 각 지역마다 100여개 이상의 업체들과 경쟁해야 하고, 이 때문에 인테리어 관련 대표 키워드들의 단가가 매우 비싸서 비용 효율적 관리가 매우 중요하다. 특히, 롱테일 영역의 저효율 소규모 키워드를 효율적으로 관리하여 비용대비 광고 효율성을 높이는 것이 중요하다. 우선, A사에서 관리하는 검색광고 키워드 별 광고 실적을 수집하여 키워드 효율성 분석을 진행하였다. <Figure 7>과 같은 분석 결과를 바탕으로 광고 운영 전문인력이 실시간으로 관리할 업종 대표 키워드(고비용 저효율), 핵심 브랜드 키워드(저비용 고효율) 및 입찰가 최적화 알고리즘을 적용할 다수의 저비용 저효율 키워드 그룹을 도출하였다.

Figure 7. 
Keyword Efficiency Analysis Result of Company A

<Figure 7>과 같이 대다수의 키워드는 50% 이하의 효율성, 3% 이하의 광고비 규모를 갖는다. 이와 같은 키워드들은 한정된 전문인력으로 운영될 경우 핵심 키워드 위주의 제한적 관리 방식으로 인해 간헐적인 관리주기를 갖는다. 본 논문에서는 간헐적인 관리로 운영 효율성이 떨어지는 저비용 저효율 키워드 그룹에 대하여 입찰가 최적화를 적용하였다. 인테리어 업계는 일반적으로 전환 관련 지표를 최대 목표로 하고, 전환이 크게 발생하지 않지만 전환에 따른 수익이 높아 입찰가가 높은 업종 중 하나이다. 따라서, 입찰가 최적화의 목표를 전환수와 전환당 비용 순서로 우선 순위 최적화로 설정하고 운영에 적용하였다.

<Figure 8>은 2020년 12월에 입찰가 최적화를 적용한 결과로, 전환수와 전환당 비용을 스케일하여 10월, 11월 결과와 비교하였다. 적용 결과 전환수는 2배 이상 증가하였고, 전환당 비용은 약 50% 감소하였다. 전환당 비용이 급격이 감소하면서 전환수가 증가하는 현상은 이전에는 전환을 발생시키지 못했던 저비용 저효율 키워드 그룹에서 전환이 발생한 것으로 해석할 수 있다. 이와 같은 결과는 연말에 대한 효과를 고려하더라도 유의미한 개선으로 판단할 수 있다.

Figure 8. 
Performance Results of the Bidding Optimization for Company A

사례 2: 여행 업종 B사

여행 업종 B사는 자체적으로 호텔 예약 사이트를 운영하고, 자사몰 활성화를 위한 홍보 활동을 일정 규모 이상 진행한다. 2020년 말 코로나 팬데믹으로 여행 업계 전반의 매출이 급감하였지만 브랜드 홍보를 위한 광고비 지출은 꾸준히 진행되어야 하기 때문에 광고 비용대비 효율성을 확보하는 것이 매우 중요하였다. 여행 업종 B사의 검색광고 운영에 입찰가 최적화 알고리즘을 시범 적용하기 위하여 전체 운영에 영향이 적은 광고비 대비 매출액이 낮은 키워드 그룹을 선정하였고, 2020년 4분기(9~12월)동안 비용 효율성 향상을 목적으로 최적화 알고리즘을 시범 적용하였다. 여행 업계도 인테리어 업계와 유사하게 전환이 크게 발생하지 않지만 전환에 따른 수익이 높은 업종 중 하나이고, 대상 광고주의 경우 광고비 대비 매출액을 주 목표로 한다. 따라서, 시범 적용 단계에서는 입찰가 최적화의 목표를 광고비 대비 매출액 최대화로 설정하고 운영에 적용하였다. <Figure 9>는 9월 대비 10~12월의 광고비 대비 매출액 변화를 나타낸 결과로, 입찰가 최적화 엔진을 적용하지 않은 키워드 그룹의 경우 광고비 대비 매출액이 코로나 이슈로 12월동안 급격하게 나빠지는 경향을 보인 반면, 최적화 엔진을 적용한 키워드 그룹은 12월의 코로나 이슈와 상관없이 꾸준히 광고비 대비 매출액이 증가하였다

Figure 9. 
ROAS Comparison Results for Company B

2020년 하반기의 유의미한 비용 대비 광고 효용성 개선 효과로 2021년에는 검색광고 입찰가 최적화 엔진을 확대 적용하였다. <Figure 10>은 시스템 적용 전후의 결과를 비교한 그래프로 스케일 된 광고비 대비 매출액과 전환당 비용을 나타낸다. 시스템 적용 전의 광고비 대비 매출액이 100%, 전환당 비용이 10000원이라고 할 때, 시스템 적용 결과 광고비 대비 매출액은 285%, 전환당 비용은 3886원까지 개선하는 결과를 도출하였다. 특히, 크리스마스 시즌에는 시즈널리티 및 프로모션 효과로 실적이 높고 시즌이 끝나면 실적이 감소하는 것이 일반적이지만, 시스템 적용 결과 높은 실적을 지속적으로 유지하는 것을 확인하였다. 또한, 월초와 월말 실적 비교를 통해서도 향상 효과가 나타남을 확인하였다.

Figure 10. 
Performance Results of the Bidding Optimization for Company B

두 가지 사례를 통해 제안하는 시스템, 특히 키워드 입찰가 최적화의 개선 효과를 확인하였다. 전문인력에 의한 관리 대비 입찰가 최적화의 가장 큰 장점은 대량의 키워드 관리에 있다. 전문인력의 경우 핵심 키워드 위주의 제한적 관리 방식으로 인해 운영에 대한 조정도 핵심 키워드 위주로 진행하게 된다. 이는, 대량의 관리 키워드에 기인하기도 하지만, 핵심 키워드가 가지는 광고비의 규모로 인해 조정의 효과가 크게 나타남에 있다. 제안하는 시스템의 경우 대량의 키워드를 관리할 수 있음에 따라 저비용 저효율 키워드 그룹까지 조정하여 효율성을 증대한다. 이는, 전문인력에 의한 관리보다 더 많은 해 영역을 탐색함을 의미한다. 실제 사례들을 통해 저비용 저효율 키워드 그룹이 키워드 입찰가 최적화를 통해 개선됨을 확인하였다. 검색광고 운영은 프로모션과 같은 외부요인에 의한 영향이 큰 분야이고, 업종에 따라 핵심 키워드는 기존의 전문인력에 의한 관리가 더 효과적일 수 있다. 다만, 시스템을 통해 관리가 힘든 저비용 저효율 키워드 그룹까지 동시에 개선한다면 전체 검색광고 운영의 효율이 극대화 될 것으로 기대된다.

본 논문에서는 국내 최대 IT 기업에서 개발한 검색광고 최적화 시스템을 소개하였다. 최적화 시스템은 검색광고 운영에 가장 중요한 의사결정 요소들인 키워드 선정과 입찰가 설정을 위한 키워드 효율성 분석과 입찰가 최적화 엔진을 포함하고 있다. 특히, 다수의 운영 목표를 가지는 국내 검색광고 시장 환경을 반영하기 위해 효율성 분석 엔진은 자료 포락 분석법에 기반한 모델을 활용하였고, 입찰가 최적화 엔진은 다목적 최적화 모델을 제시하고, 이를 해결하기 위한 반복적 탐색 알고리즘을 제안하였다. 개발한 시스템을 실제 광고 운영에 적용하여 효용성을 확인하였고, 적용 사례들에 대해 기술하였다. 본 연구는 국내 검색광고 시장의 특성을 반영한 데이터 기반 운영 방법론을 제시하고, 이를 시스템화 하여 실제 운영에 활용하고 있는 점에서 기여를 갖는다. 현재까지도 전문인력 중심으로 운영되는 국내 검색광고 시장에 최적화 분야가 상용화 된 좋은 사례가 될 것으로 기대한다.