구간 패턴을 위한 빈도 기반 제약 샘플링 (Frequency-based Constrained Sampling for Interval

출력 공간 패턴 샘플링 (Output space pattern sampling)은 대규모 패턴 공간을 탐색하기 위해 전수 패턴 마이닝 (exhaustive pattern mining)을 대체할 수 있는 강력한 대안입니다. 이는 사용자가 선택한 유용성 측정치 (interestingness measure)에 따라 추출된 대표적인 패턴에 집중할 수 있게 해주기 때문입니다. 본 논문에서 우리는 사용자가 정의한 구문 제약 (syntactic constraints) 하에서 구간 패턴 (interval patterns)을 샘플링하는 문제를 다룹니다. 우리는 샘플링 절차에 제약 조건을 직접 통합하는 샘플링 접근 방식인 CFips를 소개합니다. 이 접근 방식은 다단계 샘플링 프레임워크 (multi-step sampling framework)에 의존하며, 정확한 샘플링 보장 (sampling guarantees)을 유지하면서 구문 제약 조건을 구간 경계 (interval bounds)에 대한 기본 술어 (elementary predicates)로 분해함으로써 여러 제약 조건을 지원합니다. 우리는 CFips가 제약된 패턴 공간 내에서 해당 패턴의 빈도 (frequency)에 비례하여 구간 패턴을 샘플링함을 공식적으로 증명합니다. 실험 결과는 제약 조건을 샘플링 절차에 통합함으로써, 그렇지 않을 경우 주어진 제한 시간 내에 실패했을 마이닝 작업을 완료할 수 있음을 보여줍니다.