링크 마이닝(link mining)은 소셜 네트워크, 웹 그래프, 인용 네트워크처럼 객체들이 서로 연결된 데이터를 분석하는 기법입니다. 하지만 강력한 만큼 해결해야 할 여러 가지 도전 과제가 존재합니다. 지금부터 링크 마이닝의 대표적인 6가지 문제점을 하나씩 살펴보겠습니다.
1. 논리적 종속성 vs 통계적 종속성
그래프 구조 안에는 두 가지 유형의 종속성이 공존합니다. 하나는 객체 간의 논리적 관계를 나타내는 링크 구조이고, 다른 하나는 객체 속성 간의 상관관계 같은 확률적(통계적) 종속성입니다.
문제는 이 두 종속성을 일관되게 처리하기가 매우 까다롭다는 점입니다. 특히 마이닝 대상 데이터가 여러 테이블에 걸쳐 있는 다중 관계 데이터 마이닝(multi-relational data mining)에서는 객체 간의 수많은 논리적 관계를 탐색하는 동시에, 속성 간의 확률적 종속성에 대한 표준 검색도 함께 수행해야 합니다.
이렇게 되면 탐색 공간이 기하급수적으로 커져 합리적인 수학적 모델을 찾기가 어려워집니다. 이를 완화하기 위해 논리적 관계 탐색에 특화된 귀납 논리 프로그래밍(inductive logic programming) 기법을 활용하는 방법이 제안되고 있습니다.
2. 특징 생성(Feature Construction)
링크 기반 분류에서는 객체 자신의 속성뿐만 아니라, 해당 객체와 연결된 객체들의 속성까지 함께 고려할 수 있습니다. 심지어 링크 자체도 속성을 가질 수 있습니다.
특징 생성의 목표는 이렇게 흩어진 다양한 속성 정보를 하나의 의미 있는 특징(feature)으로 통합하는 것입니다. 여기에는 두 가지 접근이 포함됩니다.
- 특징 선택(Feature Selection): 분류 성능에 가장 큰 판별력을 지닌 특징만 선별하여 사용합니다.
- 특징 집계(Feature Aggregation): 연결된 객체들의 속성 값을 요약·결합하여 새로운 특징을 만듭니다.
3. 인스턴스 vs 클래스
모델을 설계할 때 개별 객체(instance)를 직접 참조할 것인지, 아니면 객체들이 속한 일반 범주(class)를 참조할 것인지 결정해야 합니다.
- 개별 인스턴스 기반 모델: 특정 개체를 높은 확률로 연결하는 예측에 유리합니다.
- 클래스 기반 모델: 새로운 상황이나 처음 보는 개체들에 대해서도 일반화하여 적용할 수 있다는 장점이 있습니다.
4. 레이블 데이터와 비레이블 데이터의 효과적 활용
최근 머신러닝에서는 레이블이 있는 데이터와 없는 데이터를 혼합해 학습하는 반지도 학습(semi-supervised learning) 전략이 주목받고 있습니다.
비레이블 데이터는 객체 속성의 전반적인 분포를 추론하는 데 도움을 줍니다. 또한 비레이블(테스트) 데이터 사이의 링크를 활용하면 연결된 객체의 속성 정보를 끌어다 쓸 수 있고, 레이블(훈련) 데이터와 비레이블 데이터 사이의 링크는 더 정확한 추론을 가능하게 하는 종속성을 만들어 냅니다.
5. 링크 예측(Link Prediction)
링크 예측의 가장 큰 어려움은 특정 객체 쌍 사이에 실제 링크가 존재할 사전 확률(prior probability)이 일반적으로 극히 낮다는 점입니다.
이를 극복하기 위해 네트워크 내 노드 간 근접성(proximity)을 측정하는 다양한 지표 기반의 예측 방법과 확률적 모델이 제안되어 왔습니다. 아울러 데이터셋이 방대한 경우에는 개별 링크 단위가 아니라 더 상위 수준에서 링크를 모델링하는 편이 계산 효율 면에서 유리합니다.
6. 폐쇄 세계 가정 vs 개방 세계 가정
대부분의 전통적인 접근 방식은 도메인에 존재하는 모든 잠재적 엔티티(entity)를 이미 알고 있다고 가정합니다. 이른바 '폐쇄 세계(closed world)' 가정입니다.
그러나 현실 세계의 응용 환경에서는 미지의 객체가 언제든 등장할 수 있으므로 이 가정은 비현실적입니다. 이를 해결하기 위한 연구로는, 불특정 다수의 객체 집합을 포함하는 관계형 구조 위에서 확률 분포를 정의할 수 있는 전용 언어를 도입하는 방향이 활발히 진행되고 있습니다.
마무리
링크 마이닝은 관계형 데이터에서 숨겨진 패턴을 발견하는 강력한 도구이지만, 복잡한 종속성 처리, 특징 설계, 링크 예측의 희소성 등 해결해야 할 숙제가 많습니다. 각 과제에 대한 이해는 소셜 네트워크 분석, 추천 시스템, 지식 그래프 구축 등 실제 응용 분야에서 더 나은 모델을 설계하는 밑거름이 될 것입니다.