Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories

기술 요약: 노드 임베딩 및 Wi-Fi 궤적 클러스터링을 이용한 그래프 기반 층 분리

문제 정의
수직 위치 결정, 특히 다층 실내 환경에서의 층 분리는 실내 측위 시스템(IPS)에서 여전히 중요한 과제로 남아 있다. GPS 기반의 실외 시스템과 달리, 실내 환경은 신호 차단, 다중 경로 간섭, 층간 신호 누설(특히 아트리움 및 개방형 공간)로 인해 신호 패턴이 중첩되는 문제를 겪는다. 전통적인 Wi-Fi 핑거프린팅 방식은 대규모의 레이블된 데이터와 사전 건물 지식(예: 평면도 또는 층수)을 요구하는 지도 학습에 의존하는 경우가 많다. 또한, 하드웨어 의존적 솔루션(기압계, IMU)은 보정 드리프트(calibration drift) 및 확장성 문제에 직면한다. 본 논문은 사전 건물 정보, 층수에 대한 지식 없이 오직 Wi-Fi 수신 신호 강도(RSSI) 궤적에만 의존하는 완전 데이터 기반의 비지도 학습 방식인 '블라인드 층 분리(blind floor separation)'의 필요성을 다룬다.

방법론
제안된 프레임워크는 층 분리를 비지도 그래프 클러스터링 문제로 정식화한다. 방법론은 다음 단계로 진행된다:

1. 그래프 구축:

   • 노드: 각 Wi-Fi 핑거프린트(가시적인 액세스 포인트로부터의 RSSI 값 벡터)는 하나의 노드로 표현된다.
   • 엣지: 엣지는 신호 유사성과 순차적 이동 맥락을 모두 포착한다.
     • 수평 엣지(Horizontal Edges): 동일한 사용자 궤적 내의 순차적인 핑거프린트들을 연결하여 시간적 연속성을 보존한다.
     • 수직/합성 엣지(Vertical/Synthetic Edges): 명시적인 수직 이동 레이블이 부족한 데이터셋(예: UJIIndoorLoc)의 경우, 층의 정체성이나 수직 감독 없이 그래프가 단일 연결 성분(connected component)을 유지할 수 있도록 합성 엣지를 도입한다.
   • 엣지 가중치: 가중치는 핑거프린트 간의 근접성을 나타낸다. 본 연구는 세 가지 전략을 평가한다:
     • 기본값(Default): 경진대회 데이터셋에서 제공되는 노이즈가 포함된 거리 추정치.
     • WBDE (Wi-Fi 기반 거리 추정): 외부 수평 위치 결정 데이터셋으로 학습된 지도 학습 ML 모델을 사용하여 재계산된 거리(층 분류 작업으로부터의 데이터 누출을 방려함).
     • 기하학적 골드 스탠다드(Geometric Gold Standard): 지면 진실 좌표(ground-truth coordinates)로부터 유도된 유클리드 거리(이론적 상한선을 확인하기 위해 UJIIndoorLoc에 대해서만 사용).

2. 노드 임베딩:

   • 프레임워크는 노드의 저차원 벡터 임베딩(차원 $d=32$)을 학습하기 위해 Node2Vec을 채택한다. Node2Vec은 편향된 무작위 보행(biased random walks)을 사용하여 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 균형을 맞춤으로써, 국소적 동종성(local homophily)과 전역적 구조적 동등성(global structural equivalence)을 모두 포착한다.
   • 본 연구는 그래프 신경망(GCN 및 GAT)과 벤치마킹을 수행하지만, GNN은 명시적인 특징 집계에 의존하므로 노이즈가 많은 Wi-Fi 그래프에서 오버 스무딩(over-smoothing) 현상이 발생할 수 있다.

3. 클러스터링 및 추정:

   • 학습된 임베딩은 K-Means를 사용하여 클러스터링된다.
   • 자동 클러스터 추정: 사전 지식 없이 층수($k$)를 결정하기 위해, 시스템은 Calinski-Harabasz (CH) 지수를 사용한다. 알고리즘은 [3, 20] 범위(Huawei 챌린지 제약 조건 기반) 내에서 $k$를 반복적으로 평가하며, 클러스터 간 분산과 클러스터 내 분산의 비율을 최대화하는 $k$를 선택한다.

4. 평가:

   • 본 방법은 비지도 방식이므로, 메트릭 계산을 위해 사후 다수결 투표(majority voting) 방식을 사용하여 익명의 클러스터를 물리적 층 레이블에 매핑한다.
   • 성능은 매핑 정확도(Mapped Accuracy), 가중 F1-Score, 조정 랜드 지수(ARI), 정규화된 상호 정보량(NMI), 클러스터 순도(Cluster Purity)를 사용하여 측정된다.
   • 통계적 견고성은 1,000회의 부트스트랩 반복을 통해 보장된다.

데이터셋
프레임워크는 두 개의 서로 다른 데이터셋에서 평가된다:

• Huawei University Challenge 2021: 연속적인 보행 궤적과 노이즈가 포함된 거리 추정치를 가진 대규모 데이터셋.
• UJIIndoorLoc: 세 개의 건물을 다루는 벤치마크 데이터셋. 저자들은 이 데이터셋을 재구성하여 이산적인 핑거프린트로부터 궤적을 생성하였으며, 훈련(Training) 및 검증(Validation) 서브셋을 독립적인 실험으로 취급하여 일반화 가능성을 테스트하였다.

주요 결과

• 베이스라인 대비 우월성: 제안된 Node2Vec + K-Means 파이프라인은 전통적인 커뮤니티 탐지 알고리즘(Louvain, Leiden, Infomap, Label Propagation, Fast Greedy) 및 GNN 기반 모델(GCN, GAT)을 크게 능가했다.
  • Huawei 데이터셋(WBDE 거리 사용 시), 제안된 방법은 76.60%의 정확도(95% CI [0.739, 0.806])를 달성하여 최상의 베이스라인인 GAT(50.2%)를 결정적으로 앞질렀다.
  • UJIIndoorLoc 데이터셋에서, 이 방법은 훈련 서브셋에서 66.1%, 검증 서브셋에서 **59.4%**의 정확도를 달연했으며, 이는 베이스라인들이 검증 세트에서 종종 25% 미만으로 떨어지는 것과 대조적이다.
• 거리 추정의 영향: 노이즈가 있는 기본 거리를 WBDE 기반 추정치로 교체했을 때 성능이 크게 향상되어(Huawei의 경우 69.3%에서 76.6%로), 깨끗한 그래프 토폴로지가 클러스터링에 매우 중요하다는 것을 확인했다.
• 기하학과의 등가성: 주요 발견 중 하나는 UJIIndoorLoc 데이터셋에서 순수하게 신호로부터 유도된 거리(WBDE)를 사용한 클러스터링 성능이 지면 진실 기하학적 거리를 사용한 "골드 스탠다드" 결과와 통계적으로 구별할 수 없을 정도로 유사하다는 점이다. 이는 본 방법이 RSSI 데이터만으로 물리적 구조 레이아웃을 복구할 수 있음을 시사한다.
• 구조적 무결성: 전통적인 알고리즘은 높은 클러스터 순도(종종 >90%)를 달성했으나, 심각한 과잉 분할(over-segmentation, ARI가 0에 가까움)을 겪으며 일관된 층 단위 커뮤니티를 식별하는 데 실패했다. 반면 Node2Vec 접근 방식은 높은 ARI 점수(예: Huawei에서 0.669)를 유지하여, 전역적 구조적 일관성을 성공적으로 포착했음을 보여주었다.

의의 및 주장
본 논문은 자신의 주요 기여가 건물 특정 메타데이터나 레이블된 학습 데이터에 대한 의존성을 제거한, 확장 가능한 하드웨어 독립적 수직 위치 결정 솔루션이라는 점이라고 주장한다.

• 비지도 능력: 본 방법은 건물의 레이아웃에 대한 사전 지식 없이 층수를 추정하고 궤적을 분할하는 블라인드 층 분리를 성공적으로 수행한다.
• 노이즈에 대한 견고성: 직접적인 특징 집계(GNN)나 국소적 모듈성 최적화 대신 그래프 표현 학습(Node2Vec)을 활용함으로써, Wi-Fi 환경 특유의 높은 노이즈와 신호 변동에 대해 견고하다.
• 일반화 가능성: 이 접근 방식은 다양한 건축 규모와 데이터 수집 방법론(연속 궤적 vs. 재구성된 이산 핑거프린트)에 걸쳐 일관된 성능을 입증한다.
• 실용성: 본 프레임워크는 표준 Wi-Fi 핑거프린트 데이터만을 사용하므로, 추가 센서(기압계 등)나 복잡한 보정 없이 기존 무선 인프라에 적용 가능하다.

저자들은 거리 추정의 품질(WBDEA를 통해)이 성능을 향상시키기는 하지만, 핵심 가치는 임베딩 기반 프레임워크가 노이즈가 많은 신호 데이터로부터 다층 건물의 구조적 레이아웃을 자율적으로 복구할 수 있는 능력에 있다고 결론짓는다.