규칙 제약 조건의 분류
데이터 마이닝에서 규칙 제약 조건(rule constraint)은 검색 공간을 효과적으로 줄이는 강력한 도구입니다. 이러한 제약 조건은 속성에 따라 다음과 같은 다섯 가지 유형으로 분류할 수 있습니다.
1. 반단조 제약 조건(Antimonotonic Constraint)
첫 번째 유형은 반단조(antimonotonic) 제약 조건입니다. 예를 들어 "sum(I.price) ≤ 100"이라는 제약 조건을 생각해 봅시다. Apriori 프레임워크를 사용하는 경우, 매 k번째 반복에서 크기가 k인 항목 집합(itemset)을 검사하게 됩니다. 만약 어떤 항목 집합에 포함된 항목들의 가격 합계가 이미 100을 초과한다면, 이 항목 집합은 검색 공간에서 제거할 수 있습니다. 여기에 항목을 더 추가하면 비용은 오히려 증가하기 때문에 해당 제약 조건을 결코 만족할 수 없기 때문입니다.
반단조 제약 조건에 의한 가지치기(pruning)는 Apriori 방식 알고리즘의 모든 반복 단계에서 적용할 수 있으며, 데이터 마이닝 결과의 완전성(completeness)을 보장하면서 전체 마이닝 과정의 효율성을 크게 높여줍니다.
흥미로운 점은 Apriori 속성 자체도 대표적인 반단조 속성이라는 것입니다. 빈발 항목 집합(frequent itemset)의 모든 공집합이 아닌 부분 집합 역시 빈발해야 한다는 것이 이 속성의 핵심입니다. 특정 항목 집합이 최소 지지도(minimum support)를 만족하지 못하면, 그 상위 집합(superset)들 역시 만족할 수 없습니다. 이 속성은 Apriori 알고리즘의 각 반복 단계에서 검사해야 할 후보 항목 집합의 수를 줄여, 연관 규칙 탐색을 위한 검색 공간을 지속적으로 축소하는 데 활용됩니다.
2. 단조 제약 조건(Monotonic Constraint)
두 번째 유형은 단조(monotonic) 제약 조건입니다. 만약 제약 조건이 "sum(I.price) ≥ 100"이라면, 처리 방식은 완전히 달라집니다.
어떤 항목 집합 I가 이 제약 조건을 만족한다면, 즉 집합 내 항목 가격의 합계가 100 이상이라면, 여기에 항목을 더 추가해도 비용은 계속 증가하므로 제약 조건을 계속 만족하게 됩니다.
따라서 항목 집합 I에 대해 이 제약 조건을 반복해서 검사하는 것은 불필요한 중복 작업이 됩니다. 다시 말해, 어떤 항목 집합이 이 제약 조건을 만족하면 그 모든 상위 집합도 자동으로 만족합니다. 이러한 성질을 갖는 제약 조건을 단조 제약 조건이라고 합니다.
3. 간결 제약 조건(Succinct Constraint)
세 번째 유형은 간결(succinct) 제약 조건입니다. 이 유형의 경우, 제약 조건을 만족하는 집합들을 직접 열거할 수 있습니다. 규칙 제약 조건이 간결하다면, 지지도 계산(support counting)이 시작되기 전에도 제약 조건을 만족하는 집합들을 정확하게 생성해 낼 수 있습니다. 이를 통해 생성-검사(generate-and-test) 패러다임이 유발하는 막대한 오버헤드를 사전에 피할 수 있다는 것이 가장 큰 장점입니다.
4. 변환 가능 제약 조건(Convertible Constraint)
네 번째 유형은 변환 가능(convertible) 제약 조건입니다. 항목 집합 내의 항목들을 특정 순서로 배열하면, 해당 제약 조건이 빈발 항목 집합 마이닝 과정에서 단조 또는 반단조 속성을 갖도록 변환할 수 있습니다.
예를 들어, "avg(I.price) ≤ 100"이라는 제약 조건은 반단조도 아니고 단조도 아닙니다. 그러나 트랜잭션 내 항목들을 가격 오름차순으로 항목 집합에 추가하면, 이 제약 조건은 반단조 속성을 갖게 됩니다. 항목 집합 I가 제약 조건을 위반했다면(즉, 평균 가격이 100달러보다 높다면), 이후에 더 비싼 항목들을 추가해도 제약 조건을 만족하지 못하기 때문입니다.
5. 변환 불가능 제약 조건(Inconvertible Constraint)
마지막 유형은 위의 어느 범주에도 속하지 않는 변환 불가능(inconvertible) 제약 조건입니다. 이러한 제약 조건은 항목 순서를 어떻게 정렬하더라도 단조나 반단조 속성으로 변환할 수 없습니다. 따라서 일반적으로 탐욕적(greedy) 기법이나 기타 휴리스틱 방법을 통해 별도로 처리해야 하며, 검색 공간 축소 효과는 앞선 네 가지 유형에 비해 제한적입니다.