다중 관계형 클러스터링의 정의
다중 관계형 클러스터링(multi-relational clustering)은 여러 관계(relation)에 분산되어 있는 정보를 활용하여, 데이터 객체들을 유사도(similarity)를 기준으로 여러 클러스터로 나누는 기법입니다. 단일 테이블만을 대상으로 하는 전통적인 클러스터링과 달리, 관계형 데이터베이스 전체에 걸쳐 있는 정보를 종합적으로 활용할 수 있다는 점이 큰 특징입니다.
대표적인 알고리즘으로는 CrossClus(Cross-relational Clustering with user guidance)가 있습니다. CrossClus는 클러스터링 과정에서 사용자 가이던스(user guidance)를 적극적으로 활용하고, 물리적인 조인(physical join)을 수행하지 않고도 관계 간 정보를 탐색할 수 있는 튜플 ID 전파(tuple ID propagation) 기법을 사용하여 효율성을 높입니다.
핵심 과제: 방대한 속성 공간의 문제
다중 관계형 클러스터링의 가장 큰 어려움은 서로 다른 관계들에 너무나 많은 속성(attribute)이 존재한다는 점입니다. 실제 클러스터링 작업과 관련 있는 속성은 극히 일부에 불과한 경우가 많습니다.
컴퓨터공학과 데이터베이스를 예로 들어 보겠습니다. 학생들을 클러스터링하려면 학생이 수강한 강좌, 발표한 논문, 지도교수, 소속 연구 그룹 등 매우 다양한 측면의 정보를 다루어야 합니다. 이처럼 후보 속성의 수가 방대하기 때문에 모든 속성을 일일이 고려하는 것은 비현실적입니다.
사용자 가이던스의 중요성
사용자는 보통 특정 측면의 정보를 기준으로 클러스터링을 원합니다. 예를 들어 학생들을 연구 분야별로 묶고 싶어 하는 경우가 그렇습니다. 사용자는 자신이 다루는 응용 분야의 요구 사항과 데이터의 의미(data semantics)를 잘 이해하고 있기 때문에, 간단한 질의(query) 형태로 사용자의 의도를 반영하면 고차원 다중 관계형 클러스터링의 효율성과 품질을 동시에 향상시킬 수 있습니다.
CrossClus와 다중 관계형 속성의 정의
CrossClus는 목표 관계(target relation)와 하나 이상의 관련 속성을 포함하는 사용자 질의를 입력으로 받아, 사용자가 원하는 클러스터링 목표를 명확히 지정합니다. 이를 위해 CrossClus는 다중 관계형 속성(multi-relational attribute)이라는 개념을 정의합니다.
다중 관계형 속성 A′는 다음 세 가지 요소로 구성됩니다.
- 조인 경로(join path): Rt ⋈ R1 … ⋈ Rk
- 속성: Rk.A (관계 Rk의 속성 A)
- 집계 연산자(aggregation operator): 평균(average), 개수(count), 최댓값(max) 등 — 선택 사항
이를 형식적으로 표현하면 [A′.join path, A′.attr, A′.aggr]이 되며, 여기서 A′.aggr은 생략 가능합니다. 다중 관계형 속성 A′는 원본 속성 Rk.A가 범주형인지 수치형인지에 따라 범주형(categorical) 또는 수치형(numerical) 특징으로 분류됩니다.
A′가 범주형 특징인 경우, 목표 튜플 t에 대해 t.A′는 t와 조인 가능한 Rk 내 튜플들 사이의 값 분포(distribution of values)를 나타냅니다.
속성 탐색 과정의 두 가지 난제
다중 관계형 클러스터링 과정에서 CrossClus는 여러 관계에 걸쳐 관련성 높은 속성을 탐색해야 하며, 이 과정에서 두 가지 주요 문제에 직면합니다.
- 폭발적인 탐색 공간: 목표 관계 Rt는 일반적으로 각 비목표(non-target) 관계 R과 수많은 서로 다른 조인 경로로 연결될 수 있으며, 관계 R의 모든 속성이 다중 관계형 속성의 후보가 될 수 있습니다. 따라서 이렇게 거대한 탐색 공간에서 어떤 형태의 완전 탐색(exhaustive search)도 수행하는 것은 불가능합니다.
- 관련성의 판별: 방대한 수의 속성 중 일부는 사용자 질의와 밀접하게 관련되어 있습니다(예: 학생의 지도교수는 그 학생의 연구 분야와 관련됨). 반면 상당수 속성은 무관합니다(예: 학생의 동료 학생들의 개인 정보). 관련 속성과 무관한 속성을 구분하는 것이 필수적입니다.
결론적으로 다중 관계형 클러스터링은 관계형 데이터베이스의 풍부한 정보를 활용할 수 있는 강력한 기법이지만, 방대한 속성 공간과 관련성 판별이라는 난제를 해결하기 위해 CrossClus와 같은 사용자 가이던스 기반의 지능적인 탐색 전략이 필요합니다.