> For the complete documentation index, see [llms.txt](https://wonjoon.gitbook.io/joons-til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wonjoon.gitbook.io/joons-til/techtalk-review/woowacon/2024/region-clustering-using-delvery-data.md).

# Region Clustering using delvery data

<https://www.youtube.com/watch?v=Ub1kL0OB5n8\\&ab\\_channel=%EC%9A%B0%EC%95%84%ED%95%9C%ED%85%8C%ED%81%AC>

## 🧭 배달 시스템에서 ‘지역’을 다시 생각하다

배달의민족은 하루 100만 건에 달하는 주문을 처리하며, 이 모든 배달을 적절한 라이더에게 할당하는 복잡한 문제를 다룹니다. 특히 `어디서 어디까지를 하나의 지역으로 볼 것인가`는 단순한 지리적 개념을 넘어서 **성능, 정확도, 효율**을 좌우하는 핵심 요소입니다. 이 발표에서는 기존의 정적 지역 분할 방식이 갖는 한계를 극복하기 위해, **Word2Vec 기반 공간 임베딩과 클러스터링 기법**을 활용해 지역을 재정의한 과정을 자세히 다룹니다.

***

## 배차 문제와 분할 정복

10분간 5만건의 주문이 발생하고 5만명의 라이더가 있을 경우

브루트 포스를 한다면 25억건의 배차 연산이 발생한다. 이는 너무나 비효율적이기에 지역을 나누어 배차시스템을 운영해야했다.

![Image](https://github.com/user-attachments/assets/b55a72ba-831d-404f-ba36-8887782df904)

## 🚨 기존 지역 분할의 한계: 균등 분할이 항상 공정하지 않다

초기에는 지도를 일정 크기의 육각형으로 나누는 **균등 분할 방식**이 사용되었습니다. 이 방식은 모든 지역을 일관성 있게 처리할 수 있어 단순하지만, 다음과 같은 실무적 문제를 유발했습니다.

1. **수요 불균형 문제**

   서울 강남과 강원 태백은 배달량 자체가 다릅니다. 하지만 동일한 크기로 분할하면, 라이더 수와 배달 건수에 비례한 최적화가 어렵습니다. → 과도한 배차 연산, 지연
2. **지리적 특성 무시**

   한강, 고속도로, 공원 등 **이동을 방해하는 지형지물**이 반영되지 않아, 실제론 이어지지 않은 지역을 하나로 묶어 비효율적인 배차를 유발했습니다.
3. **동시성 문제**

   인접 지역이 동시에 배차를 시작하면, 동일 라이더에게 중복 배차가 발생할 수 있습니다. 이 경우에는 \*\*락(Lock)\*\*으로 제어할 수 있지만, 락은 최적 배차 기회를 줄이므로 시스템 성능 저하의 원인이 됩니다.

***

## H3 라이브러리

Uber가 개발한 지리 정보 격자 시스템으로, 전 세계를 육각형 단위로 나눔.

각 셀은 고유 ID를 가지며 계층 구조(레벨 0\~15)로 표현 가능.

![Image](https://github.com/user-attachments/assets/69e4072c-2499-475a-b666-f83edc1dc7db)

## 문제 정의

![Image](https://github.com/user-attachments/assets/7044e7e3-da73-4d2d-99c4-6685c52095d1)

1. 지형/상권 고려 불가 → 예: 방이동 먹자골목이 쪼개짐
2. 타이밍/동시성: 인접 지역에 라이더 위치시, 지연/동시 배차 이슈
   * 락은 배차시스템을 비효율적으로 만들 수 있으므로, 이러한 락을 최소화 시키기 위해 보다 근본적인 문제해결이 필요.
3. 무리한 배차: 도시/경계 따라 비효율적 이동 (와일드구스 체이스)

## 🧪 문제 정의: 왜 ‘데이터 기반’ 재구성이 필요했는가?

기존 방식은 명확한 기준 없이 '지도 위 타일을 깔 듯' 나눴습니다. 하지만 서비스가 커지면서, 지역의 재구성에는 다음과 같은 정량적·정성적 기준이 필요해졌습니다:

* **라이더 이동 가능성**

  송파구처럼 라이더들이 일정 지역 안에서만 배달하는 패턴이 많았기에, 실제 **라이더의 행동 기반**으로 지역을 나눌 필요성이 대두되었습니다.
* **상권, 도로, 강 등 물리적 경계 반영**

  사람의 이동과 차량의 이동은 다르며, 배달 특성상 도보 불가능한 영역은 피해야 합니다.
* **성능을 위한 균등한 ‘문제 크기’ 구성**

  배차 최적화는 NP-Hard 문제로, 전체 조합을 계산하는 대신 지역 단위로 나누고 줄여야 합니다. 단순한 크기보다, **배달 건수와 라이더 수의 균형**이 핵심입니다.
* **행정동/수작업 분할의 한계**: 데이터를 풍부하게 활용하기 어려움
* **핵심 데이터**:
  * 라이더 GPS보다는 "액션(픽업/전달 등) 간 H3 이동 순서"
* **목표**:
  * 자연스러운 이동/빈도 중심, 상권/지리/이동경로 반영

![Image](https://github.com/user-attachments/assets/1a429c66-fefb-48d9-968d-cb084d660610)

```
- 라이더 이동이 편한 클러스터
    
    
```

![Image](https://github.com/user-attachments/assets/0a5b01c7-ec6b-4a40-af0e-c81d05bd3779)

```
    위 그래프를 보면 양끝의 값이 높은 걸 알 수 있다.
    
    이는 송파구에서 배달서빙을 100퍼센트하는 라이더가 있거나, 아예 배달을 하지 않는 라이더가 대부분임을 알 수 있고, 이는 지역을 잘 나누기만 한다면 라이더의 판단대로 주문을 이행할 수 있다고 판단하였다. 
    
```

* **지점 간 "오가기가 쉬운지"를 Metric으로 정의**
* **하이라키컬 클러스터링(Hierarchical Clustering)**: 맥락/관계로 덩어리 묶기
* **워드투벡(Word2Vec) 임베딩**:
  * 단어 대신 H3 셀/action 순서 적용(CBOW/Skip-gram 비교; skip-gram 최적)
  * 임베딩 공간의 거리 → 이동 용이성/실제로 붙어 있는지 표현
  * 데이터 희소성 문제는 skip-gram으로 완화
* **예시**: 잠실-송파구청은 가깝게, 잠실-삼성은 강 건너 멀게

***

## 🧠 Word2Vec으로 공간을 벡터화한다는 개념

![Image](https://github.com/user-attachments/assets/7cf57eb0-4d7f-4d5d-87ac-7f0c5f863f51)

Word2Vec은 원래 언어모델에서 사용되며, 단어 간 의미적 유사성을 벡터 공간에 투영하는 기술입니다. 여기서는 단어 대신 H3 셀(공간 단위)을 벡터로 표현했습니다.

* 라이더의 **픽업 → 이동 → 배달** 로그 데이터를 ‘문장’처럼 보고
* 각 H3 셀을 ‘단어’처럼 보고
* 이 순서를 바탕으로 **의미적 연결성**(이동이 쉬운 지역 vs 어려운 지역)을 학습했습니다

이 방식은 지리적 거리를 벗어나, 실제 이동 빈도와 편의성까지 반영된 **실제 행동 기반 임베딩**이라는 점에서 매우 혁신적입니다.

![Image](https://github.com/user-attachments/assets/8428f4de-372a-4ba3-8ec0-9e3d929641ef)

> 🧾 Skip-Gram vs CBOW
>
> Skip-Gram은 “이 단어 주변엔 어떤 단어가 나올까?”를 예측합니다. 이 문맥 기반 추론은 라이더가 "현재 위치에서 다음 액션은 어디서?"를 예측하는 방식과 매우 유사합니다.
>
> * Skip-Gram: 주변 단어 예측
> * CBOW: 주변 단어로 중심 단어 예측
>
> \[다중 위치 → 단일 목적지]가 아닌 \[단일 위치 → 다중 목적지] 연산을 할 수 있는 Skip-Gram을 선택함

#### Skip-Gram VS CBOW

#### 🧠라이더의 배차결정 과정

“내가 신천동에 있으니 어느 지역에 가는 것이 가장 효율적일까?”

![Image](https://github.com/user-attachments/assets/8b1ff255-2dd6-4b48-b323-507740ee8234)

#### 📉 Infrequent Cell 문제: 드러나지 않는 위험

![Image](https://github.com/user-attachments/assets/2dc1c7ca-3f7b-4238-b4e9-16995389b945)

데이터가 적은 H3 셀은 학습된 벡터가 정확하지 않습니다. 이로 인해 다음과 같은 문제가 발생합니다:

* Infrequent Cell: 라이더의 이동/배달 데이터가 거의 기록되지 않은 H3 셀
* 멀리 떨어진 두 셀이 같은 클러스터로 묶이거나
* 주요 배달지임에도 누락되거나
* 특정 셀의 벡터가 주변 맥락과 전혀 무관하게 위치하게 됩니다

이러한 문제는 곧바로 **부정확한 배차**로 이어질 수 있으므로, 후처리 단계에서 반드시 보완되어야 합니다.

#### 또한, 이 문제는 Skip-gram에서 훨씬 덜 발생했기에 자연스럽게 Skip-gram 모델을 선택

***

### 🛠 클러스터링 후처리 및 하이퍼파라미터 조정

#### 🧪 하이퍼파라미터 튜닝

* 평가 기준: 도로 경계, 상권 연속성, 인구 분포 균일성, shape regularity (예: 너무 뾰족한 모양 피하기, convex)
* 단일 피트니스 함수로 불가능 → 정성적 평가 병행

#### 🔧 후처리 작업

* **연속성 보장**: 단절 클러스터 병합 또는 제거
* **스무딩 처리**: 뾰족/얇은 지형 최적화
* **클러스터 중앙 빈 공간 자동 확장**: 광진구 사례처럼
* **비매핑된 외곽 영역 채움**: 군포·의왕시 사례, 인접 도시 클러스터에 연결

***

## 🛠️ 운영을 위한 보완: 자동화와 수동 개입의 균형

클러스터링만으로는 운영 환경에 적용할 수 없습니다. 대표적인 문제는 다음과 같습니다:

1. **클러스터 내부의 빈 영역**

   예: 광진구 어린이 대공원처럼 공원·시설물은 데이터가 부족해 누락
2. **경계 지역 왜곡**

   한강을 사이에 둔 H3 셀은 잘못된 라이더 배차를 유발
3. **신규 지역, 변경 이벤트 대응**

   클러스터는 주기적으로 재구성되지만, 실무에서는 **한 주 만에 상권이 변할 수 있습니다**

이러한 문제를 해결하기 위해, **Kafka 기반 이벤트 시스템**과 **Task Queue 기반 순차 처리**, 그리고 운영자용 지역 수정 도구(Admin Tool)를 함께 구성하였습니다.

***

## 📡 Kafka 이벤트 흐름과 레이스 컨디션 해결

#### 🧨 어떤 상황이 문제인가요?

* 운영자가 **여러 지역을 동시에 수정**하는 경우, 예를 들어 “송파구와 강남구 지역 설정을 동시에 바꿈”.
* 이 이벤트들이 **Kafka로 메시지로 전송됨**.
* Kafka는 기본적으로 이벤트를 **Key 기반으로 파티션에 분배**해요.

#### ❗ 그런데 문제가 생김!

* **송파구 이벤트는 A 파티션**, 강남구 이벤트는 B 파티션으로 감.
* 이 파티션들을 각각 다른 서버 인스턴스가 처리할 수 있어요.
* 그런데 **송파구와 강남구는 인접한 지역**이잖아요?

  → 서로 겹치는 H3 셀을 다룰 수도 있음.

  → 이걸 각기 다른 서버에서 동시에 처리하면 **경합(Race Condition)** 발생!

#### 예시)

* 인스턴스 A는 송파구 확장하면서 `H3-123` 셀을 포함
* 인스턴스 B는 강남구 확장하면서도 `H3-123` 셀을 포함
* 둘 다 모르고 `H3-123`을 자기 지역에 포함시킴 → 충돌 발생

![Image](https://github.com/user-attachments/assets/3adb33f1-fbaa-4a23-941b-f1cf2b166794)

Kakfa를 통해 이벤트 기반으로 지역의 변경 사항을 동기화 했습니다. 여러 지역이 동시에 변경될 경우, Kafka의 분산 특성상 **동시에 여러 인스턴스가 같은 데이터를 수정**하는 문제가 발생합니다.

이를 방지하기 위해:

![Image](https://github.com/user-attachments/assets/1697a62b-54a2-4d67-b859-27c14668f0f0)

* 이벤트를 중간 큐(Task Queue)에 모아 순차 처리
* 동일 TaskId로 파티셔닝하여 **단일 인스턴스에서만 처리**되도록 구성
* 병렬 처리도 가능하도록 **비인접 지역끼리 그룹화**

***

## 🧰 수작업 영역: B마트와 지형 특수성 대응

B마트는 ‘물류센터’ 성격의 픽업지로, 주변에 많은 배달이 몰립니다. 하지만 마트가 지역 경계에 위치하면, **한쪽 방향만 배차 우선권**을 얻어 배차 편중 문제가 발생합니다. 이 경우엔 **운영자가 직접 위치 조정**을 통해 해결해야 합니다.

또한 한강, 산, 도로 등은 **임베딩 벡터상 연결성이 있지만 실제론 이동 불가능**한 지형이므로, 이런 문제는 모델이 아닌 사람이 조정해야 했습니다.

**해결방안**

지역을 관리하는 Admin을 만들어 미세한 조정이 가능하도록 하여 대응할 수 있었습니다.

![Image](https://github.com/user-attachments/assets/7575a3e9-3ff1-4872-893b-02a769cfe30c)

***

## 🎉 실제 효과: 수치로 입증된 개선

1. **상권 단위 지역 분할**

   기존 서울 32개 지역 → 클러스터 기반 41개 지역으로 세분화

   방이동 상권처럼 분리되던 지역이 하나로 묶여 **배차 일관성 증가**
2. **부하 분산 효과**

   배달 밀집 지역은 작게, 외곽은 크게 → 시스템 전체 성능 균형 확보
3. **이동 거리 감소**

   와일드 구스 체이스 감소 → 특정 광역시에서 평균 픽업 거리 3.7% 개선

   수도권 지역 평균 배달 시간 2.6% 감소