[ML] 게임 이상 탐지 논문 리뷰 - An Empirical Study of Anomaly Detection in Online Games

AI 프로젝트를 위해 과장님께서 도움이 될만한 논문을 추천해주셨다. 그냥 읽으면 안읽을거 같아서 정리하며 읽어보자!  

사람이 정리한 글!

 

Abstract 

• 온라인 게임에 대한 경험적 연구에 대해 기술함
• 네가지 비지도 학습의 anomaly detection techniques을 사용
• 가상 데이터셋과 VNG company의 두가지 실제 온라인 게임의 데이터셋 사용 

 

I.Introduction

 

[단락1] 

• 온라인 게임 산업은 오늘날 굉장히 큰 비즈니스 시장임 
• but 인기가 많아질 수록 cheating도 빠르게 증가
• cheating은 심지어 유저의 돈을 잃게 조차 만드는 등 안좋은 영향을 끼침 
• 따라서 cheating 예방은 매우 중요함 

[단락2] 

• 기존의 cheat prevention 기술은 사용 여부를 감지한 후 해당 기술을 방지하려는 것이 대부분
• 이러한 점은 빠르게 변하는 cheat methods에 맞춰 대응할 수 없음 
• 최근에서야 이상 탐지 기법이 온라인 게임 사용자 중 치팅 유저를 탐지하는 데 사용되기 시작 

[단락3]

• ML에서 이상탐지는 일반 적인 행동에서 벗어난 샘플(=이상치)을 찾는 접근 방식
• VNG의 유명한 게임 중 하나에서 이상 탐지 기법이 치팅 유저 식별에 효과적임을 보여주었음 -> 후술될 기존 방식
• 그러나 기존 방법에는 몇몇 문제점 존재
  1. 탐지 정확도를 평가할 때 로지스틱회귀를 사용했기 때문에, 데이터가 선형 분리가 안될 때는 신뢰 불가
  2. non-parametric models로 성능이 느림
  3. 기존의 방법은 하나의 작은 온라인 게임 데이터셋에만 수행되었음 

[단락4] 

따라서 이 논문에서는 기존 연구를 보완, 확장을 목표로 하며 주요 contributions은 아래와 같다

1. non-linear classifers를 사용하여 비지도 이상 탐지 기법의 성능 평가하였음 
2. parametric model 을 적용하여 치팅 유저 탐지 , 훨씬 빠르고 경쟁력 있는 정확도
3. 두 개의 실제 온라인 게임 데이터셋과 하나의 가상 데이터셋에 대해 모든 기법 테스트 

[논문 목차]

섹션 II : 기존 연구 검토

섹션 III : 비지도 이상 탐지 기법의 성능 평가 방법에 대한 분석

섹션 IV : 실험 환경 설명

섹션 V :실험 결과 제시 

섹션 VI : 논문 결론 및 향후 연구 방향 제시 

 

II.Related Work

온라인 게임에서의 cheating = 이점을 얻기 위해 게임 경험을 조작하는 활동들 

ㄴ 수익 감소 및 게임 경험 훼손 야기 

ㄴ 따라서 탐지가 중요함 

 

현재 까지 cheating 탐지 기술 

[1] 게임 규칙 기반 탐지 

• 합법적 rule을 정의하고, 이 rule을 위반하면 cheating으로 간주 
• 블랙리스트 활용 
• 이미 알려진 치팅 행위는 효과적으로 탐지할 수 있지만, 빠르게 변화하는 새 치팅 기술에 대한 대응은 느림 

[2] 게임 플레이어의 통계 특성 기반 탐지 

• [ex] chapel - 각 플레이어에게 점수를 부여하고, 게임 결과와 기대값 간 차이를 분석하여 치팅 식별 
• [ex] Laurens - 서버 측 행동을 통계적 분석 
• 이 방법은 플레이어의 프라이버시를 침해하지 않으며, 모든 사용자에게 적용 가능
• but 플레이어의 데이터 분포에 대한 가정이 전제라, 가정이 맞지 않으면 성능 저하 가능 

[3] 이상 탐지 기반 

• 통계적 방법의 확장판, 머신러닝 기법 활용 
• 게임 데이터의 분포에 대한 가정 없이도 사용 가능 , 치팅 + 기타 이상 행동도 식별가능 

III.Methods 

A. Anomlay Detection Techniques 

네가지 방법론에 대해 기술, 이후에 정확도 평가할 것 

온라인 게임은 unlabeled data, 4가지 비지도 학습 기반 이상 탐지 기법 사용 

 

[1] Local Outlier Factor (LOF) 

• global이 아닌 local density로 분석하는 것이 핵심 
• local density 는 객체의 abonrmal 정도를 나타내는 척도로 사용 
• p가 자신의 최근접 클러스터에서 멀리 떨어져 있다 = p의 LOF값이 높아진다 = p의 k-neigbors의 lk 값 간 비율 낮아짐
• 따라서 LOF 값이 객체의 이상치 정도를 나타내는 값으로 사용될 수 있음 
• LOF 값 계산 과정 

 

[2] Kernel Density Estimation (KDE) 

• 데이터 샘플들의 밀도를 추정하는 비모수적 방법 
• 계산 과정 (본 논문에서는 가우시안 커널 사용) 

• h=커널의 bandwidth, d는 데이터의 차원. KDE는 낮은 밀도를 가진 샘플이 드물고 이상치일 가능성이 크다는 점 이용

[3] K-means 

• 데이터를 k개 클러스터로 나눔 
• 각 데이터 포인트는 가장 가까운 클러스터 중심에 할당
• 이후 각 클러스터의 중심을 클러스터에  속한 데이터 포인트들의 평균으로 재계산 후, 더 이상 변화가 없을 때 까지 진행
• = 제곱 오차 함수  J 최소화가 목표 

• 정상 데이터는 큰 클러스터에 속하고, 이상치는 작은 클러스터에 속한다고 가정하여 이상치 판단 

 

[4] Gaussian Mixture Model (GMM) 

• 모든 데이터 포인트가 알려지지 않은 파라미터를 가진 유한개의 가우시안 분포 혼합으로 생성된다고 가정하는 확률적 모델이다. 

• GMM 모델은 종종 MLE (Maximum Likelihood Estimates)를 사용하여 훈련됨 
• 데이터 인스턴스와 추정된 평균 간의 거리는 이후 해당 인스턴스의 이상치 score로 간주 

B. Evaluation of Anomaly Detection 

• 기존 비지도 학습의 이상 탐지를 평가할 때는라벨을 사용 (훈련에서는 X) -> external evaluation approach 
  • ❌ 단점 : 라벨이 없는 데이터가 존재하는 실제 문제에 적용 가능 
• 앞서 로지스틱회귀를 통해 분류 알고리즘을 적용한 기법들은 샘플 집합 S가 주어지면, A의 성능은 S의 각 객체를 데이터셋의 다른 객체들과 구분하는 것이 얼마나 쉬운지 또는 어려운지를 측정하여 정량화 가능 
  • ❌ 단점 : 선형 분류 알고리즘 (로지스틱 회귀)를 사용했다는 점 
    
    • 만약, 데이터셋이 비선형적으로 구분될 수 있다면 이 방법을 사용해서 이상 탐지 기법을 비교하는 것이 신이 신뢰도가 떨어질 수 있음 (즉, 데이터가 복잡할 때 성능 평가를 제대로 못할 가능성이 있다) 
• 이 문제를 해결하기 위해, 본 논문에서는 비선형 분류 알고리즘을 사용하였음 

IV.Experimental Setting 

A에서 제안한 알고리즘의 실험을 위해 두 가지 세트로 나누어 진행 

 

[1] 첫번째 실험 세트 - 분류 알고리즘 

• 로지스틱 회귀 (Logistic Regression, LR) - 선형
• 서포트 벡터 머신 (Support Vector Maachine, SVM) - 비선형
• K-최근접 이웃 (K-Nearest Neigbor,KNN) - 비선형
• 랜덤 포레스트 (Random Forest, RF)  - 비선형 

[2] 두번째 실험 세트 - A에서 제안한 기법 사용 

• LOF (Local Outlier Factor)  - 파라미터 k = 10 
• KDE (Kernel Density Estimation) - 파라미터 bandwidth는 1 
• K-means - 파라미터 JX2에서는 k=2 / Chan에서는 6 
• GMM (Gaussian Mixture Model) - 파라미터 가우시안 구성요소 수를 2에서 6까지 변화시키며 최적 모델을 Bayesian Information Criterion을 통해 선택 

*모든 알고리즘의 파라미터는 초기 실험을 통해 성능이 가장 좋게 나오는 값으로 조정됨 

 

[3] 대상 게임 

• JX2  / Chan (VNG 회사의 게임, 등록 사용자 수가 100만명을 넘는다) 
  
  • JX2 게임에서는  기존 방식에서 사용된 동일한 feature와 데이터셋 사용 
  • Chan 게임에서는 플레이한 게임 수 / 승리 게임 수 / 얻은 금액 / 잃은 금액 사용 
  • Chan 게임은 7일 연속 데이터 수집 
  • JX2는 하루 약 2만명, Chan은 약 2천명의 AU데이터 수집 

[4] 이상 사용자 판별 기준  

• LOF / KDE / GMM - "랭킹 기반" , 데이터셋 크기의 1%만큼 이상 사용자로 판정 
• K-means - 사용자가 속한 클러스터의 크기가 너무 작으면 이상 사용자로 간주
  • JX2에서는 t= 80 (클러스터 유저가 80명보다 적으면 이상유저)
  • Chan에서는 t= 30 

V.Result AND DISCUSSION 

[결론 요약] 

 

[1] 첫번째 실험 세트에서  

 

• 로지스틱 회귀는 만족스럽지 못한 성능, 많은 정상 데이터가 이상치로 분류됨 
• KNN과 RF가 SVM보다는 나음 
• SVM은 정상 클러스터 사이에 위치한 이상 샘플들 제대로 탐지 못함
• KNN과 RF는 한개 샘플을 제외하고 모두 탐지 

-> 따라서 신중하게..! 

 

[2] 두번째 실험 세트에서 

 

* 정확도 (F-score) / 탐지된 이상 사용자 수 / 연산 시간으로 성능 평가 

 

1. 정확도 (F-score) 
   • LOF가 가장 낮아 성능 좋지 않음 (지역 밀도 기반 이상치 탐지 방식이 데이터에 잘 맞지 않기 때문일수도) 
   • K-means, GMM이 KDE 보다 낫다. 다만 세 기법 간 성능 차이는 매우 작음 
2. 이상 탐지 사용자 수 (앙상블 기법 포함)  
   • K-means는 LOF,KDE,GMM과 유사한 수의 이상 유저 탐지 
   • 앙상블 모델 1 (KDE / K-menas / GMM 모두 이상치로 판단)은 탐지 수가 높으며 단일 기법과 비교해도 차이 없음 
     
     • 서로 비슷한 이상 유저를 찾았다는 증거
   • 앙상블 모델 2 (LOF/ K-menas / GMM 모두 이상치로 판단) 는 탐지 수가 매우 적음 
     • LOF 가 탐지한 이상치는 다른 기법과 매우 다름 
3. 연산 시간 
   • LOF, KDE 실행 속도가 느림 
   • 특히 JX2처럼 데이터셋이 클 경우 LOG는 K-means 및 GMM보다 약 10배 느림 / KDE는 100배 느림
   • LOF 및 KDE는 실시간 탐지나 대규모 데이터셋에 부적합 
   • 데이터 셋이 작아도 느림 , 차이는 줄지만 K-means, GMM이 더 빠름 
4. 결론 
   • K-means와 GMM은 정확도와 실행시간 측면에서 실시간 이상 탐지나 대용량 데이터셋에 적합 

VI.Conclusions and future work 

• 실험 결과, K-means와 GMM(모수적 방법)이 정확도와 실행 속도 면에서 LOF,KDE(비모수적 방법) 보다 우수한 성능
• K-means의 K수 지정과 같은 한계를 극복하기 위해 계층적 클러스터링 같은 다른걸 적용해볼 예정