유버와 유사한 플랫폼에서 시간대별 지역별 주문 밀집도를 파악해 차량 배차 최적화를 수행해야 함

각 주문 데이터(Order)에는 출발지 위도(open_lat), 경도(open_lng) 정보가 포함됨

특정 시간대에 어떤 지역이 주문 요청이 높은지 파악해 시각화된 히트맵을 생성해야 함

초기 구현 시 위도 경도 기반 클러스터링을 고려함. 대표적인 클러스터링 알고리즘인 K-평균 알고리즘을 사용하려 하였으나, 이는 미래 예측이 불가능한 한계가 있음. K값을 미리 정의해야 하는데, 이는 예측 가능한 클러스터 수를 요구하기 때문임

따라서 밀도 기반 클러스터링 알고리즘인 DBSCAN을 선택함. 클러스터 수를 사전에 정의하지 않아도 자동으로 노이즈 포인트를 식별할 수 있는 장점이 있음

DBSCAN 알고리즘 구조:

입력: 데이터 세트 D=(x1,x2,...,xm), 인접 영역 파라미터(ϵ,MinPts), 거리 측정 방식

출력: 클러스터 분할 C

1) 핵심 객체 집합 Ω=∅, 클러스터 수 k=0, 미방문 데이터 Γ=D, 클러스터 분할 C=∅ 초기화
2) 모든 샘플 xj에 대해 다음 단계 수행:
   a) 거리 측정 방식으로 xj의 ϵ-邻域 샘플 집합 Nϵ(xj) 계산
   b) |Nϵ(xj)|≥MinPts 조건 충족 시 xj를 핵심 객체 집합 Ω에 추가
3) Ω가 공집합일 경우 종료, 아니면 4단계로 전환
4) Ω에서 임의의 핵심 객체 o 선택, 현재 클러스터 큐 Ωcur={o}, 클러스터 번호 k=k+1, 클러스터 데이터 Ck={o} 생성
5) Ωcur이 공집합일 경우 Ck 완성, Γ 업데이트 후 3단계로 전환
6) Ωcur에서 객체 o′ 추출, Nϵ(o′) 계산 후 Δ=Nϵ(o′)∩Γ 처리, Ck 및 Γ 업데이트 후 5단계로 재귀

Java 언어로 DBSCAN 구현:

package com.df.dbscan;
import java.util.ArrayList;

public class DensityBasedClusterer {
    private double thresholdDistance;
    private int minimumPoints;
    
    public DensityBasedClusterer(double radius, int minPts) {
        this.thresholdDistance = radius;
        this.minimumPoints = minPts;
    }

    public void analyze(ArrayList<Location> locations) {
        int total = locations.size();
        int index = 0;
        int clusterId = 1;
        
        while (index < total) {
            Location center = locations.get(index++);
            if (!center.isVisited()) {
                center.setVisited(true);
                ArrayList<Location> neighbors = findNeighbors(center, locations);
                
                if (neighbors != null && neighbors.size() < minimumPoints) {
                    center.setNoised(true);
                } else {
                    center.setCluster(clusterId);
                    
                    for (Location neighbor : neighbors) {
                        if (!neighbor.isVisited()) {
                            neighbor.setVisited(true);
                            ArrayList<Location> extendedNeighbors = findNeighbors(neighbor, locations);
                            
                            if (extendedNeighbors.size() >= minimumPoints) {
                                for (Location extNeighbor : extendedNeighbors) {
                                    if (!neighbors.contains(extNeighbor)) {
                                        neighbors.add(extNeighbor);
                                    }
                                }
                            }
                        }
                        
                        if (neighbor.getCluster() == 0) {
                            neighbor.setCluster(clusterId);
                            if (neighbor.isNoised()) {
                                neighbor.setNoised(false);
                            }
                        }
                    }
                    clusterId++;
                }
            }
            
            if (index % 1000 == 0) {
                System.out.println(index);
            }
        }
    }

    private ArrayList<Location> findNeighbors(Location center, ArrayList<Location> locations) {
        ArrayList<Location> result = new ArrayList<>();
        for (Location loc : locations) {
            if (center.distanceTo(loc) <= thresholdDistance) {
                result.add(loc);
            }
        }
        return result;
    }
}

View Code처리 로직:

데이터를 HBase에서 조회해 구조화한 후 알고리즘에 전달하면 클러스터 결과를 얻을 수 있음

// HBase 데이터 조회
val queryResult = Controll.rowEndFilter2(tableName, startDate, endDate)
// 데이터 변환
import scala.collection.JavaConverters._
for (record <- queryResult) {
    val longitude = record.get("open_lng").toString.toDouble
    val latitude = record.get("open_lat").toString.toDouble
    val areaCode = record.get("begin_address_code").toString
    locationData.add(new Location(latitude, longitude, areaCode))
}

// 알고리즘 실행
val clusterer = new DensityBasedClusterer(thresholdDistance, densityThreshold)
clusterer.analyze(locationData)

// 결과 변환
val clusterMap: Map[Int, List[Location]] = locationData.asScala.groupBy(_.getCluster)
// 결과 전송 처리