빈번한 부분 구조 발견의 기본 원리
빈번한 부분 구조(frequent substructure)의 발견은 일반적으로 두 단계로 이루어집니다. 첫 번째 단계에서는 빈번한 부분 구조 후보를 생성하고, 두 번째 단계에서는 각 후보의 빈도를 검사합니다.
대부분의 연구가 첫 번째 단계의 최적화에 집중되는 이유는, 두 번째 단계가 부분 그래프 동형성(subgraph isomorphism) 검사를 포함하며 이 검사의 계산 복잡도가 지나치게 높기 때문입니다(NP-완전 문제).
빈번한 부분 구조 마이닝의 주요 방법
빈번한 부분 구조를 마이닝하는 방법은 크게 두 가지로 나눌 수 있습니다.
1. Apriori 기반 접근법(Apriori-based Approach)
Apriori 기반 빈번한 부분 구조 마이닝 알고리즘은 Apriori 기반 빈번 항목집합(itemset) 마이닝 알고리즘과 동일한 특징을 공유합니다. 빈번한 그래프 탐색은 작은 '크기'의 그래프에서 시작하여, 후보에 정점(vertex), 간선(edge), 또는 경로(path)를 하나씩 추가하는 상향식(bottom-up) 방식으로 진행됩니다. 그래프 크기의 표현 방식은 사용된 알고리즘에 따라 달라집니다.
이 접근법의 가장 큰 설계 난제는 후보 생성 단계입니다. 빈번 항목집합 마이닝에서 후보 생성은 비교적 명확합니다. 예를 들어, 크기 3인 두 개의 빈번 항목집합 (abc)와 (bcd)가 있다면, 조인(join)을 통해 크기 4의 후보 (abcd)가 쉽게 도출됩니다.
그러나 빈번한 부분 구조 마이닝에서의 후보 생성은 훨씬 어렵습니다. 두 개의 부분 구조를 결합할 수 있는 방법이 매우 다양하기 때문입니다.
2. 패턴 성장 접근법(Pattern-Growth Approach)
Apriori 기반 접근법은 수준별(level-wise) 후보 생성 특성상 너비 우선 탐색(BFS) 전략을 사용해야 합니다. 크기 (k+1) 그래프가 빈번한지 확인하려면 해당 그래프에 대응하는 모든 크기 k 부분 그래프를 검사하여 빈도의 상한을 구해야 합니다. 따라서 Apriori류 접근법은 크기 (k+1) 부분 그래프를 마이닝하기 전에 일반적으로 크기 k 부분 그래프의 마이닝을 먼저 완료해야 합니다.
반면 패턴 성장 방법은 탐색 방식이 훨씬 유연합니다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)을 모두 활용할 수 있으며, 특히 DFS는 메모리 소모가 적다는 장점이 있습니다.
패턴 성장 방법의 한계: 중복 그래프 문제
패턴 성장 그래프 방법은 단순하지만 효율적이지 않습니다. 병목 현상은 그래프 확장의 비효율성에서 비롯됩니다. 동일한 그래프가 여러 번 발견될 수 있는데, 예를 들어 서로 다른 n개의 (n−1) 간선 그래프가 모두 같은 n-간선 그래프로 확장될 수 있습니다. 같은 그래프를 반복해서 발견하는 것은 계산상 매우 비효율적이며, 두 번째로 발견된 그래프를 중복 그래프(duplicate graph)라고 부릅니다.
중복 그래프 감소를 위한 해결책
중복 그래프의 생성을 줄이려면 각 빈번한 그래프를 최대한 보수적으로 확장해야 합니다. 이 원칙은 여러 새로운 알고리즘의 설계로 이어졌습니다.
스패닝(Spanning) 알고리즘은 바로 이 목적을 위해 설계되었습니다. 이 알고리즘은 중복 검출을 위해 이전에 발견된 빈번한 그래프를 다시 검색할 필요가 없으며, 어떤 중복 그래프도 확장하지 않으면서도 빈번한 그래프의 완전한 집합을 발견하는 것을 보장합니다.