다중 관계형 클러스터링(Multirelational Clustering)의 개념
다중 관계형 클러스터링은 여러 개의 관계(relation)에 분산되어 있는 데이터를 활용하여, 데이터 객체들을 유사도에 기반해 여러 클러스터로 나누는 기법입니다. 단일 테이블만으로 분석하는 기존의 클러스터링과 달리, 관계형 데이터베이스 전반에 흩어져 있는 정보를 종합적으로 활용한다는 점이 특징입니다.
CrossClus: 사용자 가이던스 기반의 다중 관계형 클러스터링 알고리즘
CrossClus는 'Cross-relational Clustering with user guidance'를 의미하는 알고리즘으로, 다중 관계형 클러스터링을 위해 설계되었습니다. 이 알고리즘은 클러스터링 과정에서 사용자 가이던스(user guidance)를 어떻게 활용할지 분석하고, 튜플 ID 전파(tuple ID propagation) 기법을 통해 물리적인 조인(physical join) 없이도 관계 간 정보를 효과적으로 결합할 수 있도록 합니다.
다중 관계형 클러스터링의 핵심 과제
다중 관계형 클러스터링의 가장 큰 어려움은 여러 관계에 걸쳐 수많은 속성(attribute)이 존재하지만, 특정 클러스터링 작업과 실제로 관련 있는 속성은 극히 일부에 불과하다는 점입니다.
예를 들어 학생 데이터를 클러스터링하는 경우를 생각해 볼 수 있습니다. 학생과 관련된 속성은 수강한 강좌, 발표한 논문, 지도교수, 소속 연구팀 등 다양한 정보 요소를 포괄합니다.
사용자 가이던스가 중요한 이유
사용자는 일반적으로 특정 데이터 요소를 기준으로 학생을 그룹화하는 데 관심을 갖습니다(예: 연구 분야별로 학생 클러스터링). 사용자는 자신에게 필요한 응용 목적과 데이터의 의미를 가장 잘 이해하고 있으므로, 간단한 질의(query) 형태의 사용자 가이던스를 활용하면 고차원 다중 관계형 클러스터링의 효율성과 결과 품질을 크게 향상시킬 수 있습니다.
CrossClus의 작동 방식
CrossClus는 대상 관계(target relation)와 하나 이상의 관련 속성을 포함하는 사용자 질의를 입력받아, 사용자가 원하는 클러스터링 목표를 정의합니다. 이후 다중 관계형 클러스터링 과정에서 여러 관계에 걸쳐 관련 속성을 검색하게 됩니다.
검색 단계의 두 가지 주요 난제
CrossClus가 속성 검색 단계에서 해결해야 할 두 가지 핵심 문제는 다음과 같습니다.
첫째, 대상 관계 Rt는 일반적으로 여러 조인 경로(join path)를 통해 각 비대상 관계 R과 연결될 수 있으며, 해당 관계의 모든 속성이 잠재적으로 다중 관계형 속성으로 활용될 수 있습니다. 이처럼 방대한 검색 공간에서는 어떠한 형태의 완전 탐색(exhaustive search)도 사실상 불가능합니다.
둘째, 수많은 속성 중 일부는 사용자 질의와 관련이 있지만, 나머지는 무관합니다(예: 학생의 동료 학생들에 대한 개인 정보).
휴리스틱 검색 전략
이러한 문제를 해결하기 위해 CrossClus는 검색 범위를 제한하는 전략을 사용합니다. 관계형 스키마를 그래프로 취급하여, 관계는 노드(node)로, 조인은 엣지(edge)로 표현합니다. 그런 다음 사용자가 정의한 속성에서 검색을 시작하고, 현재 속성의 인접 영역에서 유용한 속성을 반복적으로 탐색하는 휴리스틱 방법을 채택합니다. 이 방식을 통해 검색 범위를 연결된 관계로 점진적으로 확장하되, 무작위 방향으로 멀리 나아가지 않도록 통제합니다.
속성 유사성 평가 기준
CrossClus는 각 속성이 대상 튜플(target tuple)을 어떻게 군집화하는지에 주목하여 속성의 관련성을 판단합니다. 관련 속성은 사용자가 정의한 속성과의 관계를 기준으로 선택됩니다.
- 두 속성이 튜플을 매우 다르게 군집화한다면, 유사도가 낮으므로 서로 관련이 없을 가능성이 높습니다.
- 두 속성이 튜플을 같은 방식으로 군집화한다면, 서로 밀접하게 관련되어 있다고 간주할 수 있습니다.
이러한 평가 메커니즘을 통해 CrossClus는 방대한 다중 관계 공간에서도 사용자 의도에 부합하는 의미 있는 클러스터링 결과를 효율적으로 도출할 수 있습니다.