2025-11-24T15:01:18.137860

Kernel Representation and Similarity Measure for Incomplete Data

Cao, Yang, He et al.
Measuring similarity between incomplete data is a fundamental challenge in web mining, recommendation systems, and user behavior analysis. Traditional approaches either discard incomplete data or perform imputation as a preprocessing step, leading to information loss and biased similarity estimates. This paper presents the proximity kernel, a new similarity measure that directly computes similarity between incomplete data in kernel feature space without explicit imputation in the original space. The proposed method introduces data-dependent binning combined with proximity assignment to project data into a high-dimensional sparse representation that adapts to local density variations. For missing value handling, we propose a cascading fallback strategy to estimate missing feature distributions. We conduct clustering tasks on the proposed kernel representation across 12 real world incomplete datasets, demonstrating superior performance compared to existing methods while maintaining linear time complexity. All the code are available at https://anonymous.4open.science/r/proximity-kernel-2289.
academic

불완전 데이터에 대한 커널 표현 및 유사성 측정

기본 정보

  • 논문 ID: 2510.13352
  • 제목: Kernel Representation and Similarity Measure for Incomplete Data
  • 저자: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
  • 분류: cs.LG (기계학습)
  • 발표 시간: 2024년 10월 15일 (arXiv 제출)
  • 논문 링크: https://arxiv.org/abs/2510.13352v1

초록

본 논문은 불완전 데이터의 유사성 측정이라는 기초적 과제를 다루기 위해 근접 커널(proximity kernel) 방법을 제안합니다. 기존 방법들은 불완전 데이터를 버리거나 사전에 대체(imputation) 전처리를 수행하여 정보 손실과 유사성 추정 편향을 초래합니다. 근접 커널은 원본 공간에서의 명시적 대체 없이 커널 특성 공간에서 직접 불완전 데이터 간의 유사성을 계산합니다. 본 방법은 데이터 의존적 분할(binning) 메커니즘과 근접 할당(proximity assignment)을 도입하여 데이터를 국소 밀도 변화에 적응하는 고차원 희소 표현으로 투영합니다. 결측값 처리를 위해 계단식 폴백(cascading fallback) 전략을 제안하여 결측 특성 분포를 추정합니다. 12개의 실제 불완전 데이터셋에 대한 군집화 실험은 선형 시간 복잡도를 유지하면서 기존 방법을 능가하는 성능을 보여줍니다.

연구 배경 및 동기

핵심 문제

불완전 데이터의 유사성 측정은 네트워크 마이닝, 추천 시스템 및 사용자 행동 분석에서의 기초적 과제입니다. 실제 데이터는 사용자 개인정보 보호 선호도, 조사 무응답, 정보 자발적 미공개 등의 요인으로 인해 본질적으로 불완전합니다.

문제의 중요성

  1. 광범위한 존재: 추천 시스템에서 사용자는 일반적으로 소수의 항목에만 평점을 매겨 매우 희소한 사용자-항목 행렬을 생성합니다
  2. 데이터 이질성: 결측성은 수치형, 범주형 또는 혼합형 특성에 동시에 영향을 미칠 수 있습니다
  3. 하위 작업 영향: 유사성 측정은 군집화, 분류 및 이상 탐지 등의 작업의 기초이며, 부정확한 유사성 추정은 작업 성능을 크게 저하시킵니다

기존 방법의 한계

  1. 삭제 방법: 결측값을 무시하거나 불완전한 샘플을 완전히 제거하여 심각한 정보 손실과 편향을 초래합니다
  2. 대체 방법: 통계량 또는 복잡한 기법을 사용하여 결측값을 채우지만, 종종 잠재 데이터 분포를 포착하지 못하며 실제 유사성 구조를 반영하지 않는 인공적 패턴을 도입할 수 있습니다
  3. 심층학습 방법: 유망하지만 일반적으로 대규모 데이터셋과 상당한 계산 자원이 필요하며, 이론적 보장이 부족하고 초매개변수에 민감합니다

연구 동기

기존 방법은 "2단계" 전략(먼저 대체 후 유사성 계산)을 채택하지만, 본 논문은 커널 표현 공간에서 대체와 유사성 측정을 함께 처리하는 새로운 접근법을 제안합니다.

핵심 기여

  1. 근접 커널 방법 제안: 등빈도 분할과 보로노이 기반 근접 할당을 통해 데이터를 고차원 희소 표현으로 투영하며, 명시적 밀도 추정 없이 국소 밀도에 적응합니다
  2. 계단식 폴백 전략: 결측값 처리를 위해 교집합에서 합집합을 거쳐 전역 사전까지의 점진적 제약 완화 매칭 전략을 제안합니다
  3. 선형 시간 복잡도: 선형 시간 복잡도를 구현하여 대규모 데이터셋으로의 확장성을 실현합니다
  4. 실험 검증: 12개 데이터셋의 군집화 작업에서 기존 방법을 능가하는 성능을 입증합니다

방법 상세 설명

작업 정의

n개의 샘플을 포함하는 데이터셋 D = {x₁, x₂, ..., xₙ}이 주어지면, 각 샘플 xᵢ ∈ ℝᵈ는 d차원 특성 벡터이며 결측값(NaN으로 표시)을 포함할 수 있습니다. 목표는 유사성 함수 s : D × D → 0,1을 계산하여 임의의 두 샘플 간의 유사성을 정량화하고 이를 하위 군집화 등의 작업에 사용하는 것입니다.

모델 아키텍처

1. 데이터 의존적 분할 및 근접 할당

분할 중심 선택: 각 특성 j에 대해 등빈도 분할을 사용하여 n_bins개의 분할 중심을 선택합니다:

c_{j,k} = percentile(X_{obs,j}, (k-1)×100/(n_{bins}-1))

여기서 k ∈ {1,2,...,n_bins}이고, X_obs,j는 특성 j의 모든 관측값입니다.

근접 할당 메커니즘: 기존 구간 멤버십이 아닌 근접 할당을 채택합니다:

b_{i,j} = argmin_{k∈{1,...,n_{bins}}} |x_{i,j} - c_{j,k}|

이는 특성 공간의 보로노이 다이어그램을 생성하며, 각 중심 c_j,k는 보로노이 셀을 정의합니다.

밀도 자적응 특성:

  • 밀집 영역: 연속 중심 간 거리가 작아 작은 보로노이 셀을 생성하며, 동일 거리의 두 점이 서로 다른 셀에 속할 가능성이 높습니다
  • 희소 영역: 연속 중심 간 거리가 커 큰 보로노이 셀을 생성하며, 동일 거리의 두 점이 동일 셀에 속할 가능성이 높습니다

2. 원-핫 인코딩 구성

각 특성 j와 샘플 i에 대해 이진 벡터 h_i,j ∈ {0,1}^{n_bins}을 구성합니다:

h_{i,j,k} = {1 if b_{i,j} = k; 0 otherwise}

완전한 인코딩은 모든 특성의 연결입니다: z_i = h_i,1, h_i,2, ..., h_i,d

3. 결측값 처리를 위한 계단식 폴백 전략

레벨 1 - 교집합 매칭: 모든 관측 특성에서 일치하는 샘플을 찾습니다:

S₁(i) = ∩_{j∈O_i} C_{i,j}

여기서 C_i,j = {m : m≠i, b_m,j = b_i,j}

레벨 2 - 합집합 매칭: S₁(i) = ∅인 경우, 임의의 관측 특성 매칭으로 완화합니다:

S₂(i) = ∪_{j∈O_i} C_{i,j}

레벨 3 - 전역 사전: S₂(i) = ∅인 경우, 전역 분포를 사용합니다:

p_{j,k} = count of samples in bin k for feature j / count of samples with observed feature j

각 레벨에 대해 커널 평균 임베딩(KME)을 사용하여 결측 인코딩을 추정합니다:

h_{i,j,k} = 1/|S(i)| ∑_{m∈S(i)} h_{m,j,k}

기술 혁신점

  1. 명시적 추정 없는 밀도 자적응: 등빈도 분할과 근접 할당의 조합을 통해 자연스럽게 밀도 자적응 분할을 실현합니다
  2. 커널 공간 통합 처리: 원본 공간이 아닌 표현 공간에서 결측값을 처리하여 인공적 패턴 도입을 회피합니다
  3. 점진적 매칭 전략: 엄격한 기준에서 느슨한 기준으로의 점진적 완화로 가용 정보 활용을 최대화합니다

근접 커널 정의

K(x_m, x_n) = 1/d · z_m^T z_n = <z_m, z_n>

이 커널은 Mercer 조건(대칭성 및 양반정치성)을 만족하며 확률론적 해석을 가집니다: 두 샘플이 모든 특성에서 동일 분할에 속할 기대 확률을 계산합니다.

실험 설정

데이터셋

UCI의 12개 실제 데이터셋을 사용하며, 다양한 분야를 포함합니다:

  • 의료 진단: Kidney, Hepatitis, Heart, Tumor, Cancer
  • 생물 분류: Soybean, Mushroom
  • 금융 분석: Credit
  • 인구 예측: Adult
  • 정치 분석: Voting
  • 기타: Mammography, Horse

데이터셋은 155개에서 48,842개의 샘플, 5개에서 35개의 차원, 0.15%에서 19.39%의 결측률을 가집니다.

평가 지표

표준화 상호정보(NMI)를 사용하여 군집화 품질을 평가하며, K-평균 군집화를 채택하고 군집 수를 실제 클래스 수로 설정합니다.

비교 방법

9가지 대표적 방법:

  1. 단순 대체: 평균 대체
  2. 통계 방법: MissForest, MICE, KNN, EM
  3. 심층학습: GAIN, MIRACLE, MIWAE
  4. 커널 방법: HI-PMK

구현 세부사항

  • 각 실험을 10회 반복하여 평균값 계산
  • 모든 기준선 방법에 대해 초매개변수 최적화 수행
  • 근접 커널의 분할 수를 {2,3,4,6,8}에서 검색

실험 결과

주요 결과

  1. 전체 성능: 12개 데이터셋 중 10개에서 최고 또는 차고 성능 달성, 평균 NMI 최고(0.4245)
  2. 통계적 유의성: Friedman-Nemenyi 검정은 근접 커널이 HI-PMK를 제외한 모든 다른 방법을 유의하게 능가함을 보여줍니다
  3. 안정성: 상자 그림은 근접 커널이 평균 성능이 최고일 뿐만 아니라 다양한 데이터셋에서의 성능도 더욱 일관성 있음을 보여줍니다

결측률 견고성 실험

3L 및 Messidor 데이터셋에서 10%-50%의 결측률 테스트:

  • 낮음에서 중간 결측률(10%-40%)에서 안정적인 우월 성능 유지
  • 극단적 결측률(50%)에서도 합리적 성능 유지
  • 이에 비해 KNN과 MissForest는 30% 결측률에서 성능이 거의 0으로 저하됩니다

확장성 분석

  • 시간 복잡도: O(nd + d·n log n), 고정 차원에서 샘플 수에 선형
  • 공간 복잡도: O(nd), 샘플 수와 특성 수에 선형
  • 실제 실행 시간: HI-PMK 및 MIWAE보다 현저히 빠름

민감도 분석

분할 수가 2에서 10으로 변할 때, 세 개 데이터셋의 NMI 변화는 매우 작습니다(예: Mammo 데이터셋에서 0.30-0.33 사이 변동), 방법이 초매개변수에 대해 불민감함을 보여줍니다.

관련 연구

전통적 대체 방법

  • 단순 대체: 평균/최빈값 대체, 계산 효율적이지만 데이터 자연 변동성을 보존하지 못합니다
  • KNN 대체: k개의 가장 유사한 샘플을 기반으로 하지만, 고차원 희소 데이터에서 성능이 떨어집니다
  • EM 알고리즘: 최대우도 밀도 추정 기반, 강한 분포 가정 필요
  • MICE: 다중 대체 데이터셋 생성, 계산 비용이 크고 신중한 모델 지정 필요
  • MissForest: 무작위 포레스트를 사용한 반복적 대체, 과적합 가능성 및 수렴 보장 부족

심층학습 방법

  • GAIN: 생성 대적 네트워크를 사용하여 결측 데이터 분포 학습
  • MIWAE: 심층 잠재 변수 모델을 사용하여 관측 데이터 우도 하한 최대화
  • MIRACLE: 인과 추론과 심층학습을 결합하여 대체 품질 개선

커널 방법

  • 전통적 거리: 유클리드 거리는 불완전 데이터에 직접 적용되지 않습니다
  • HI-PMK: 데이터 의존적 커널 방법이지만 계산 복잡도가 높고 초매개변수에 민감합니다

결론 및 논의

주요 결론

  1. 근접 커널은 원본 공간의 명시적 대체를 회피하면서 커널 특성 공간에서 불완전 데이터의 유사성을 직접 계산하는 데 성공했습니다
  2. 데이터 의존적 분할과 근접 할당의 조합은 명시적 밀도 추정 없이 국소 밀도에 적응하는 표현을 생성합니다
  3. 계단식 폴백 전략은 가용 정보를 효과적으로 활용하며, 엄격한 매칭에서 전역 사전으로 점진적으로 완화합니다
  4. 방법은 선형 시간 복잡도를 유지하면서 우월한 성능을 달성합니다

한계

  1. 결측 메커니즘 가정: 현재 평가는 주로 MCAR(완전 무작위 결측) 메커니즘을 기반으로 하지만, 실제 데이터는 종종 더 복잡한 MAR 및 MNAR 패턴을 나타냅니다
  2. 분할 전략: 등빈도 분할이 모든 데이터 분포에 최적일 수는 없습니다
  3. 이론적 보장: 계단식 폴백 메커니즘의 이론적 수렴 보장이 부족합니다

향후 방향

  1. MAR 및 MNAR 결측 메커니즘 하에서의 방법 행동 연구
  2. 자적응 분할 선택 전략 탐색
  3. 계단식 폴백 메커니즘의 이론적 수렴 보장 수립
  4. 더 복잡한 데이터 유형 및 구조로의 확장

심층 평가

장점

  1. 방법 혁신성: 대체와 유사성 계산을 커널 표현 공간에 통합하여 전통적 2단계 방법의 문제를 회피합니다
  2. 이론적 기초: 커널 유효성에 대한 엄격한 증명을 제공하며 Mercer 조건을 만족합니다
  3. 실용성: 선형 시간 복잡도로 대규모 응용에 적합합니다
  4. 충분한 실험: 통계적 유의성 검정을 포함한 다양한 데이터셋에서의 포괄적 평가
  5. 견고성: 초매개변수에 불민감하며 다양한 결측률에서 안정적 성능

부족한 점

  1. 결측 메커니즘 제한: 주로 MCAR 가정 하에서 평가되며, 더 복잡한 결측 패턴에 대한 적응성이 충분히 검증되지 않았습니다
  2. 밀도 추정: 명시적 밀도 추정이 필요 없다고 주장하지만, 등빈도 분할은 본질적으로 암묵적 밀도 추정입니다
  3. 특성 독립성: 계단식 전략에서 특성 간 의존성 모델링이 충분하지 않을 수 있습니다
  4. 비교 공정성: 심층학습 방법과의 비교에서 계산 자원 및 조정 정도의 차이가 존재할 수 있습니다

영향력

  1. 학술 기여: 불완전 데이터 유사성 측정을 위한 새로운 이론적 틀 제공
  2. 실용적 가치: 추천 시스템, 네트워크 마이닝 등의 응용에서 직접적 가치 보유
  3. 재현성: 코드 링크 제공으로 방법 검증 및 보급 용이

적용 시나리오

  1. 추천 시스템: 사용자-항목 평점 행렬의 희소성 처리
  2. 네트워크 마이닝: 사용자 행동 데이터의 불완전성 처리
  3. 의료 데이터 분석: 임상 데이터의 결측값 처리
  4. 대규모 데이터 처리: 선형 복잡도로 대규모 응용에 적합

참고문헌

논문은 결측 데이터 처리, 커널 방법, 심층학습 등 다양한 분야의 중요 연구를 포함한 21개의 관련 문헌을 인용하며, 본 연구에 견고한 이론적 기초와 비교 기준을 제공합니다.

요약: 본 논문이 제안한 근접 커널 방법은 불완전 데이터 유사성 측정 분야에서 중요한 기여를 하며, 정교한 커널 표현 설계와 계단식 폴백 전략을 통해 성능과 효율의 양호한 균형을 실현합니다. 일부 한계가 있음에도 불구하고, 그 혁신성과 실용성은 관련 응용 분야에서 중요한 가치를 가집니다.