Cross-Group Aligned Problem Difficulty Clustering Using Attention-Weighted Feature Learning

기술 요약: 어텐션 가중치 기반 특징 학습을 이용한 그룹 간 정렬된 문제 난이도 클러스터링

문제 정의
온라인 저지(Online Judge, OJ) 플랫폼은 프로그래밍 교육을 위한 방대한 문제 저장소와 제출 로그를 제공하는 핵심 인프라입니다. 그러나 이 데이터를 활용하는 데 있어 중요한 과제는 학습자의 이질성입니다. 동일한 문제라도 사용자의 숙련도에 따라 쉽게 느껴질 수도, 어렵게 느껴질 수도 있습니다. 기존의 난이도 분류 방식은 대개 전역적으로 집계된 행동적 특징에 의존하는데, 이는 숙련도에 따른 상호작용 패턴을 가리는 경점가 있습니다. 또한, 서로 다른 사용자 그룹에 독립적으로 적용되는 표준 클러스터링 방식은 일관되지 않은 난이도 레이블을 생성할 수 있습니다(예: 상급자에게는 '쉬움'으로 분류된 문제가 초보자에게는 '어려움'으로 분류될 수 있음). 이는 일관된 학습 진도를 방해합니다. 추가로, OJ의 특징들(예: 제출 횟수, 시도 횟수)은 편향되어 있거나 롱테일 분포를 보이는 경우가 많아, 거리 기반 클러스터링 알고리즘에 편향을 일으킬 수 있습니다.

방법론
저자들은 통계적 모델링, 어텐션 기반 특징 학습, 그리고 그룹 간 정렬을 통합하는 숙련도 그룹 인식 프레임워크를 제안합니다. 워크플로우는 다섯 가지 주요 단계로 구성됩니다:

1. 데이터 전처리 및 특징 추출:

   • 데이터셋: 본 연구는 약 960만 건의 제출, 3,047개의 문제, 83,495명의 사용자로 구성된 Aizu Online Judge(AOJ)의 대규모 제출 로그를 활용합니다.
   • Rasch 모델링: 이진 제출 결과(정답 vs 오답)에 Rasch (1PL) 모델을 적용하여 잠재적 사용자 능력($\theta$)과 문제 난이도($\beta$)를 추정합니다.
   • 사용자 클러스터링: 사용자의 잠재적 능력과 정확도를 기반으로 K-means를 사용하여 사용자를 세 가지 숙련도 그룹(초급, 중급, 상급)으로 클러스터링합니다.
   • 특징 구축: 각 사용자 그룹에 대해 다음을 포함한 문제 수준의 특징을 집계합니다:
     • 행동적 특징: 제출 횟수, 평균 시도 횟수, 정답률, 결과 도출까지의 평균 시간.
     • 잠재적 특징: Rasch에서 도출된 난이도 점수.
   • 전처리: 왜도와 이상치를 처리하기 위해 제출 횟수, 평균 시도 횟수, 결과 도출 시간에 로그 변환을 적용합니다. 그 후 Z-score 정규화를 사용하여 특징들을 공통 척도로 매핑합니다.

2. 어텐션 기반 난이도 클러스터링 (FA–K-means):

   • 특징의 중요도가 균등하다고 가정하는 대신, 본 프레임워크는 특징 어텐션 가이드 K-means (FA–K-means) 알고리즘을 채택합니다.
   • 특징별 어텐션 모듈은 각 사용자 그룹에 대한 그룹별 가중치($A^{(g)}$)를 학습합니다. 이 모듈은 선형 변환과 tanh 활성화 함수, 그리고 softmax 함수를 사용하여 어텐션 점수를 생성하며, 이 점수는 가중치가 적용된 특징 표현($Z^{(g)}$)을 만드는 데 사용됩니다.
   • 이 모듈은 K-means 클러스터링을 적용하여 난이도 수준(쉬움, 중간, 어려움)을 식별하기 전에 재구성 손실(입력값과 재구성된 특징 간의 차이를 최소화)을 통해 학습됩니다.

3. 그룹 간 난이도 정렬:

   • 그룹 간 레이블 불일치 문제를 해결하기 위해 전역 난이도 정렬(Global Difficulty Alignment) 단계를 도입합니다.
   • 방법론은 **비단조적 순서(Non-Monotonic Ordering, NMO)**를 불일치의 지표로 정의합니다. 여기서 문제는 $Difficulty_{Beginner} < Difficulty_{Intermediate} < Difficulty_{Advanced}$가 유지되지 않을 경우(높은 레이블이 높은 난이도를 나타낸다고 가정할 때) 순서를 위반하는 것으로 간주합니다.
   • 정렬 과정은 모든 그룹에서 동일한 난이도 수준의 중심점(centroids)을 집계하여 "전역 난이도 중심"을 계산합니다. 이 전역 중심은 각 그룹의 특정 전처리 및 어텐션 모듈을 통해 다시 매핑되어 그룹별 앵커(anchor)를 생성합니다. 그 후 문제는 가장 가까운 앵커에 재할당되어, 숙련도 수준 전반에 걸쳐 통일되고 단조로운 난이도 척도를 보장합니다.

4. 평가:

   • 지표: 클러스터링 품질은 실루엣 계수(SS), 데이비스-볼딘 지수(DBI), 칼린스키-하라바츠 지수(CHI)를 사용하여 평가합니다. 그룹 간 일관성은 NMO를 통해 측정됩니다.
   • 베이스라인: 제안된 방법은 표준 K-means, 퍼지 C-means (FCM), Ward의 계층적 클러스터링 및 BIRCH와 비교됩니다.
   • 검증: 특징 분리를 검증하기 위해 크러스컬-월리스(Kruskal-Wallis, KW) 테스트와 효과 크기($\epsilon^2$)를 사용하여 통계적 유의성을 평가합니다.

주요 기여

• 숙련도 인식 프레임워크: 본 연구는 인구 집단 수준의 접근 방식이 놓칠 수 있는 상호작용 패턴을 포착하여, 세 가지 숙련도 그룹에 대해 별도로 난이도를 분류하는 프레임워크를 도입합니다.
• NMO의 공식화: 저자들은 그룹 간 레이블 불일치를 정량화하고 최소화하기 위한 해석 가능한 지표로서 비단조적 순서(NMO)를 공식화했습니다.
• FA–K-means 알고리즘: 특징 어텐션 가이드 K-means의 통합을 통해 그룹별 적응형 특징 가중치를 학습할 수 있으며, 이는 표준 균등 가중치 방식보다 향상된 그룹 내 클러스터링 품질을 제공합니다.
• 전역 정렬 전략: NMO를 크게 감소시키기 위해 체계적인 정렬 단계를 제안합니다.
• 해석 가능성: 어텐션 가중치 분석과 KW 테스트를 통해 난이도 구분을 주도하는 핵심 특징(특히 정답률과 평균 시도 횟수)을 식별했습니다.

실험 결과

• 클러스터링 품질: AOJ 데이터셋에서 FA–K-means는 모든 숙련도 그룹에서 베이스라인(K-means, FCM, Ward, BIRCH)보다 일관되게 우수한 성능을 보였습니다. 가장 높은 실루엣 계수(예: 초급의 경우 K-means의 0.34 대비 0.42), 가장 높은 칼린스키-하라바츠 지수, 가장 낮은 데이비스-볼딘 지수를 달려 성과를 입증했습니다.
• 그룹 간 일관성: 전역 정렬 단계는 NMO를 급격히 감소시켰습니다. FA–K-means의 경우, NMO는 정렬 전 **30.41%**에서 정렬 후 **9.69%**로 감소했습니다. 이는 정렬 후에도 21.50%~26.63% 범위를 유지한 베이스라인 모델들보다 뛰어난 감소 폭입니다.
• 특징 중요도: 어텐션 가중치 분석과 KW 테스트 결과, 정답률과 평균 시도 횟수가 난이도 수준을 구분하는 가장 유의미한 지표인 것으로 확인되었습니다.
• 일반화 가능성: 랭크 기반 가우시안 코풀라(rank-based Gaussian copula)를 통해 생성된 합성 데이터셋에 대한 실험에서도 AOJ의 결과를 재현하였으며, 이를 통해 어텐션 기반 재가중치 및 정렬 전략의 안정성과 견고함을 확인했습니다.
• 시각화: 사용자 수준에서 도출된 난이도 수준을 검사할 수 있도록 경량 웹 기반 대시보드를 개발했습니다.

의의 및 주장
본 논문은 제안된 프레임워크가 숙련도 그룹을 고려한 난이도 분류를 위한 효과적이고 해석 가능한 기반을 제공한다고 주장합니다. 난이도는 사용자의 숙련도에 상대적이라는 점을 인정함으로써, 이 방법은 전역적 집계보다 더 일관된 난이도 척도를 제공합니다. 저자들은 이 접근 방식이 클러스터링 타당성 지표를 개선할 뿐만 아니라, 학습자 그룹 간에 일관성을 유지하는 난이도 레이블을 생성하여 학생들의 더 나은 학습 진도를 지원하고 강사들에게 더 정보가 풍부한 문제 조직을 제공한다고 단언합니다. 본 연구는 프레임워크가 AOJ를 통해 검증되었으나, 설계 자체가 확장 가능하며 데이터 희소성이나 특징 특성이 다른 플랫폼의 유사한 도메인에도 적용 가능함을 강조합니다. 저자들은 프레임워크가 제출 기반 특징에 의존하며, 데이터 특성에 따라 성능이 달라질 수 있다는 점을 언급하며 한계점에 대해 신중한 태도를 유지합니다.