제약 조건 기반 클러스터링이란?
제약 조건 기반 클러스터링(Constraint-based Clustering)은 사용자가 명시한 선호 사항이나 제약 조건을 만족하는 클러스터를 찾는 기법입니다. 제약 조건의 성격에 따라 다양한 접근 방식을 취할 수 있으며, 제약 조건은 크게 다음과 같은 범주로 나눌 수 있습니다.
1. 개별 객체에 대한 제약 조건
클러스터링 대상이 되는 객체 자체에 제약 조건을 정의할 수 있습니다. 예를 들어 부동산 애플리케이션에서는 가치가 100만 달러 이상인 고급 저택만을 대상으로 공간적 클러스터링을 수행하고 싶을 수 있습니다.
이러한 제약은 클러스터링할 객체의 집합을 한정하는 역할을 하며, 전처리 단계(예: SQL 쿼리를 활용한 선택 연산)를 통해 손쉽게 처리할 수 있습니다. 전처리 이후에는 일반적인 비제약 클러스터링 문제로 환원됩니다.
2. 클러스터링 매개변수 선택에 대한 제약 조건
사용자는 각 클러스터링 매개변수에 대해 원하는 값을 설정할 수 있습니다. 클러스터링 매개변수는 특정 알고리즘에 종속적인 경우가 많습니다. 예를 들어 k-means 알고리즘에서 원하는 클러스터 개수 k, DBSCAN 알고리즘에서 반경 ε과 최소 포인트 수 MinPts 등이 있습니다.
다만 이러한 사용자 지정 매개변수는 클러스터링 결과에 큰 영향을 미치지만, 알고리즘 자체에 국한된 것이기 때문에 일반적으로 제약 조건 기반 클러스터링의 한 형태로 간주되지 않습니다.
3. 거리 또는 유사도 함수에 대한 제약 조건
클러스터링 대상 객체의 특정 속성에 대해 서로 다른 거리 함수나 유사도 함수를 정의하거나, 특정 객체 쌍에 한해 별도의 거리 측정 방식을 적용할 수 있습니다. 예를 들어 운동선수를 클러스터링할 때 키, 체중, 나이, 기술 수준에 각각 다른 가중치 방식을 적용하는 경우가 이에 해당합니다.
4. 개별 클러스터의 속성에 대한 사용자 지정 제약 조건
사용자는 결과로 생성될 클러스터가 가져야 할 특성을 직접 지정할 수 있으며, 이는 클러스터링 과정 전반에 강력한 영향을 미칩니다.
예를 들어 어떤 택배 회사가 도시 내 k개 서비스 거점의 위치를 결정하려 한다고 가정해 보겠습니다. 이 회사는 고객의 이름, 위치, 서비스 이용 기간, 월평균 요금을 기록한 고객 데이터베이스를 보유하고 있습니다. 고객 위치를 기반으로 계산된 거리 함수를 사용하면 이 위치 선정 문제를 비제약 클러스터링의 한 사례로 공식화할 수 있습니다.
그러나 더 스마트한 방법은 고객을 두 그룹으로 나누는 것입니다. 즉, 자주 정기적인 서비스가 필요한 고가치 고객과 가끔 서비스가 필요한 일반 고객으로 구분하는 것입니다. 비용을 절감하면서 양질의 서비스를 제공하기 위해 관리자는 다음과 같은 제약 조건을 추가합니다.
- 각 거점은 최소 100명의 고가치 고객을 서비스해야 합니다.
- 각 거점은 최소 5,000명의 일반 고객을 서비스해야 합니다.
제약 조건 기반 클러스터링은 클러스터링 과정에서 이러한 제약 조건들을 함께 고려하게 됩니다.
5. 부분 감독(partial supervision)에 기반한 준지도 학습 클러스터링
비지도 클러스터링의 품질은 약한 형태의 감독(supervision)을 활용하면 상당히 향상시킬 수 있습니다. 여기서 감독은 주로 쌍별 제약(pairwise constraints)의 형태로 제공되며, 이는 두 객체가 동일한 클러스터에 속하는지 아니면 서로 다른 클러스터에 속하는지 레이블로 표시한 것을 의미합니다. 이처럼 제약 조건을 활용하는 클러스터링 과정을 준지도 학습 클러스터링(semi-supervised clustering)이라고 합니다.