데이터 클러스터링에서는 특정 제약 조건을 처리하기 위해 다양한 기법이 필요합니다. 제약 조건은 크게 하드 제약 조건(hard constraint)과 소프트 제약 조건(soft constraint)으로 나뉘며, 각각의 일반적인 처리 원칙은 다음과 같습니다.
하드 제약 조건(Hard Constraint) 처리
엄격한 제약 조건을 다루는 일반적인 방법은 클러스터 할당 과정에서 해당 제약 조건을 철저히 준수하도록 하는 것입니다. 데이터 세트와 개체에 대한 제약 조건 집합(즉, 머스트-링크(must-link) 또는 캔낫-링크(cannot-link) 제약 조건)이 주어졌을 때, 이러한 제약을 만족하도록 k-평균(k-means) 알고리즘을 확장하려면 어떻게 해야 할까요? 이를 위해 고안된 것이 COP-k-means 알고리즘이며, 다음 단계로 동작합니다.
머스트-링크 제약 조건을 위한 슈퍼 인스턴스 생성
머스트-링크 제약 조건들의 전이 폐쇄(transitive closure)를 계산하여, 모든 머스트-링크 제약 조건을 동치 관계(equivalence relation)로 취급합니다. 이렇게 얻어진 폐쇄는 하나 이상의 객체 부분 집합을 만들어내며, 같은 부분 집합에 속한 객체들은 반드시 하나의 클러스터에 함께 배정되어야 합니다.
부분 집합이 정의되면, 집합 내 객체들을 그 평균값으로 대체할 수 있습니다. 이렇게 대체된 객체를 슈퍼 인스턴스(super instance)라고 하며, 슈퍼 인스턴스는 자신이 대표하는 객체 수를 가중치(weight)로 함께 가집니다. 이 과정을 거치면 모든 머스트-링크 제약 조건이 자동으로 충족됩니다.
수정된 k-평균 클러스터링 수행
기본 k-평균에서는 객체가 가장 가까운 중심에 배정됩니다. 캔낫-링크 제약 조건을 준수하기 위해, COP-k-means는 중심 할당 과정을 '가장 가까운 중심'이 아닌 '가장 가까운 실행 가능한(feasible) 중심'으로의 할당으로 변경합니다.
객체들이 순서대로 중심에 배정될 때, 매 단계마다 지금까지의 배정이 어떤 캔낫-링크 제약 조건도 위반하지 않는지 확인합니다. 즉, 객체는 캔낫-링크 제약을 위반하지 않으면서 가장 가까운 중심에 배정됩니다.
COP-k-means는 매 단계에서 제약 조건 위반이 없음을 보장하므로 되추적(backtracking)이 필요하지 않습니다. 제약 조건들 사이에 충돌이 없다는 전제 하에, 모든 제약을 만족하는 클러스터링을 생성하는 탐욕적(greedy) 알고리즘입니다.
소프트 제약 조건(Soft Constraint) 처리
소프트 제약 조건이 있는 클러스터링은 최적화 문제로 접근합니다. 클러스터링 결과가 소프트 제약 조건을 위반하면 해당 클러스터링에 페널티(penalty)가 부과됩니다. 따라서 최적화 목표는 두 부분으로 구성됩니다. 하나는 클러스터링 품질을 최적화하는 것이고, 다른 하나는 제약 조건 위반 페널티를 최소화하는 것입니다. 목적 함수는 클러스터링 품질 점수와 페널티 점수의 합으로 정의됩니다.
데이터 세트와 개체에 대한 소프트 제약 조건 집합이 주어지면, CVQE(Constrained Vector Quantization Error) 알고리즘은 제약 위반 페널티를 적용하면서 k-평균 클러스터링을 수행합니다. CVQE에서 사용하는 목적 함수는 k-평균에서 사용하는 거리의 총합에 제약 위반 페널티를 더해 수정한 값이며, 페널티는 다음과 같이 계산됩니다.
머스트-링크 위반에 대한 페널티
객체 x와 y 사이에 머스트-링크 제약 조건이 있는데, 두 객체가 서로 다른 두 중심 c1과 c2에 배정되면 제약 조건이 위반됩니다. 이 경우 c1과 c2 사이의 거리인 dist(c1, c2)가 페널티로 목적 함수에 더해집니다.
캔낫-링크 위반에 대한 페널티
객체 x와 y 사이에 캔낫-링크 제약 조건이 있는데, 두 객체가 동일한 중심 c에 배정되면 제약 조건이 위반됩니다. 이 경우 c와 c’(c를 제외한 가장 가까운 다른 중심) 사이의 거리인 dist(c, c’)가 페널티로 목적 함수에 더해집니다.