제약 기반(constraint-based) 알고리즘은 빈번한 아이템셋(frequent itemset) 생성 단계에서 탐색 영역을 줄이기 위해 제약 조건을 필요로 합니다. 이때 연관 규칙 생성 단계는 완전 탐색(exhaustive) 알고리즘과 동일하게 작동합니다.
제약 조건의 중요성은 매우 명확합니다. 제약 조건을 활용하면 사용자에게 실제로 의미 있는 연관 규칙만을 생성할 수 있으며, 그 과정도 비교적 단순합니다. 제약 조건을 적용하면 후보 규칙의 영역이 크게 줄어들고, 남은 규칙들은 해당 제약 조건을 만족하게 됩니다.
제약 조건의 세 가지 유형
클러스터링에서 활용되는 제약 조건은 크게 세 가지로 분류할 수 있습니다.
1. 인스턴스에 대한 제약 조건
인스턴스에 대한 제약 조건은 클러스터 분석에서 특정 객체 쌍 또는 객체 집합이 어떻게 그룹화되어야 하는지를 정의합니다. 이 범주에는 두 가지 유형이 있습니다.
- Must-link 제약 조건 — 두 객체 x와 y에 must-link 제약이 정의되면, 클러스터 분석 결과에서 x와 y는 반드시 동일한 클러스터에 속해야 합니다. Must-link 제약은 추이성(transitivity)을 가집니다. 즉, must-link(x, y)와 must-link(y, z)가 성립하면 must-link(x, z)도 성립합니다.
- Cannot-link 제약 조건 — Cannot-link 제약은 must-link 제약의 반대 개념입니다. 두 객체 x와 y에 cannot-link 제약이 정의되면, 클러스터 분석 결과에서 x와 y는 서로 다른 클러스터에 속해야 합니다. Cannot-link 제약은 도출(entailment)이 가능합니다. 예를 들어, cannot-link(x, y), must-link(x, x'), must-link(y, y')가 주어지면 cannot-link(x', y')가 성립합니다.
2. 클러스터에 대한 제약 조건
클러스터에 대한 제약 조건은 클러스터 자체에 대한 요구 사항을 정의하며, 클러스터의 속성을 활용할 수 있습니다. 예를 들어, 클러스터 내 최소 객체 수, 클러스터의 최대 지름, 또는 클러스터의 형태(예: 볼록 형태) 등을 제약으로 지정할 수 있습니다. 또한 분할 기반(partitioning) 클러스터링 방법에서 정의되는 클러스터의 개수 역시 클러스터에 대한 제약 조건으로 간주할 수 있습니다.
3. 유사도 측정에 대한 제약 조건
유클리드 거리(Euclidean distance)와 같은 유사도 측정 방식은 클러스터 분석에서 객체 간 유사도를 계산하는 데 사용됩니다. 그러나 실제 응용 환경에서는 예외적인 상황이 발생하기 때문에, 유사도 측정에 대한 제약 조건은 유사도 계산 과정이 반드시 준수해야 할 요구 사항을 정의합니다.
예를 들어, 광장에서 이동하는 사람들을 클러스터링한다고 가정해 보겠습니다. 유클리드 거리는 두 지점 사이의 직선상 최단 거리를 계산하지만, 유사도 측정에 대한 제약 조건은 '최단 거리를 구하는 경로가 벽을 통과해서는 안 된다'는 요구 사항을 부과할 수 있습니다.
엄격함에 따른 분류: 하드 제약과 소프트 제약
클러스터링 제약 조건을 분류하는 또 다른 관점은 제약 조건이 얼마나 엄격하게 준수되어야 하는지에 따른 구분입니다.
- 하드 제약(Hard constraint) — 제약 조건을 위반하는 클러스터링 결과가 허용되지 않는 경우를 말합니다. 하드 제약은 반드시 지켜져야 합니다.
- 소프트 제약(Soft constraint) — 제약 조건을 위반하는 클러스터링 결과가 바람직하지는 않지만, 더 나은 해를 찾을 수 없는 상황이라면 허용될 수 있는 경우를 말합니다. 소프트 제약은 '선호도(preferences)'라고도 불립니다.