Comparison of Outlier Detection Algorithms on String Data

이 논문은 문자열 데이터의 이상치 탐지를 위해 편집 거리를 기반으로 한 변형 국소 이상치 인자 알고리즘과 계층적 정규식 학습 기반 알고리즘을 제안하고, 데이터의 구조적 특성과 편집 거리 분포에 따라 각 알고리즘의 성능이 달라짐을 실험적으로 입증했습니다.

핵심

이 논문은 **"이상한 문자열 (데이터) 을 찾아내는 두 가지 방법"**에 대한 연구입니다.

보통 컴퓨터는 숫자 데이터 (예: 주가, 온도) 에서 이상한 값을 찾는 데는 능숙합니다. 하지만 사람 이름, 주소, 날짜 같은 '문자열' 데이터에서 이상한 것을 찾는 것은 훨씬 어렵습니다. 이 논문은 이 문제를 해결하기 위해 두 가지 서로 다른 전략을 비교했습니다.

이 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

🕵️‍♂️ 상황 설정: "이상한 손님 찾기"

상상해 보세요. 거대한 파티가 열려 있습니다. 대부분의 손님들은 정해진 규칙에 맞춰 옷을 입고 왔습니다 (예: 모두 검은 정장). 그런데 그중에는 엉뚱한 옷을 입은 손님들이 섞여 있습니다. 우리는 이 **'이상한 손님 (이상치, Outlier)'**을 찾아내야 합니다.

이 논문은 이 일을 어떻게 할지 두 가지 방법을 제안합니다.

---

방법 1: "이웃 관계로 판단하기" (LOF 알고리즘)

이 방법은 **"너는 주변 사람들과 너무 달라!"**라고 외치는 방식입니다.

• 원리: 파티장에 들어온 사람 A 가 주변에 있는 5~10 명의 사람들과 옷차림이 비슷하면 '정상'으로 봅니다. 하지만 사람 B 는 주변 사람들과 옷차림이 너무 다르면 '이상한 사람'으로 의심합니다.
• 문자열에 적용: 컴퓨터는 두 단어 사이의 **'글자 차이 (편집 거리)'**를 계산합니다.
  • 예: "2023-01-01"과 "2023-01-02"는 글자가 하나만 달라서 비슷합니다.
  • 하지만 "2023-01-01"과 "안녕하세요"는 글자 자체가 완전히 달라서 거리가 멉니다.
• 고급 버전 (계층적 가중치): 저자는 여기에 더 재미있는 규칙을 추가했습니다.
  • 숫자 '1'을 숫자 '2'로 바꾸는 건 가벼운 실수 (비슷한 옷) 로 봅니다.
  • 하지만 숫자 '1'을 알파벳 'A'로 바꾸는 건 완전히 다른 옷을 입은 격이라서 더 큰 차이로 봅니다.
  • 비유: "검은 정장"을 "회색 정장"으로 바꾼 건 괜찮지만, "비키니"로 바꾼 건 아주 큰 차이로 간주하는 것입니다.

장점: 데이터의 '밀집도'를 잘 파악해서, 모양이 조금씩 다른 이상한 것들도 찾아냅니다.
단점: 데이터가 너무 복잡하면 헷갈릴 수 있습니다.

---

방법 2: "규칙을 만들어서 따르기" (HiLRE 알고리즘)

이 방법은 **"우리 파티의 규칙은 이런 거야!"**라는 명쾌한 법전을 만드는 방식입니다.

• 원리: 대부분의 손님이 지켜온 규칙을 분석해서, **"정장만 입고 와야 한다"**는 규칙 (정규식) 을 만들어냅니다. 그 규칙에 맞지 않는 사람은 바로 이상한 사람으로 분류합니다.
• 문자열에 적용: 날짜 데이터가 주라면, 컴퓨터는 "숫자 4 개 - 숫자 2 개 - 숫자 2 개"라는 규칙을 찾아냅니다.
  • "2023-01-01" → 규칙 준수 ✅
  • "2023/01/01" (슬래시 사용) → 규칙 위반 ❌
• 고급 버전 (최소 일치율): 때로는 규칙이 너무 까다로울 수도 있습니다. 그래서 "최소한 90% 의 손님이 이 규칙을 따를 때만 규칙을 채택하자"는 안전 장치를 두었습니다.

장점: 규칙이 명확하면 이상한 사람을 100% 정확히 찾아냅니다. (예: 날짜 형식이 틀린 것)
단점: 만약 파티 손님들의 옷이 제각각이라면 (예: "Bonn", "Frankfurt (Oder)"처럼 길고 복잡한 이름들), 규칙을 만들기 어렵습니다. 규칙을 만들지 못하면 아무도 이상한 사람으로 못 찾습니다.

---

🥊 두 방법의 대결: 어떤 게 더 잘할까?

저자는 실제 데이터 (독일 병원 주소, 날짜, 전화번호 등) 로 실험을 해보았습니다.

1. 규칙이 뚜렷한 경우 (예: 우편번호):

   • 규칙 만들기 (HiLRE) 가 압승!
   • 우편번호는 무조건 5 자리 숫자입니다. 규칙을 만들면 이상한 것 (이름이나 긴 주소) 을 바로 걸러냅니다.
   • 이웃 관계 방식은 "5 자리 이름"과 "5 자리 숫자"를 구분하기가 조금 더 어렵습니다.

2. 규칙이 복잡하거나 섞여 있는 경우 (예: 지명, 전화번호):

   • 이웃 관계 (LOF) 가 더 나았습니다.
   • 지명들은 길이가 다르고 글자도 제각각이라 규칙을 만들기 힘듭니다. 하지만 "이웃" 방식은 "너는 다른 사람들과 너무 달라"라고 판단해서 이상한 것을 찾아냅니다.
   • 특히 길이가 다른 전화번호나 주소처럼, 문자 자체는 비슷하지만 길이가 다른 경우에 이웃 방식이 잘 작동했습니다.

---

💡 결론: "상황에 맞는 도구를 선택하라"

이 논문의 핵심 메시지는 **"하나의 만능 해결책은 없다"**는 것입니다.

• 데이터가 규칙적이고 깔끔하다면 (날짜, 우편번호 등) → **규칙을 만드는 방법 (HiLRE)**이 최고입니다.
• 데이터가 다양하고 복잡하다면 (이름, 주소 등) → **이웃 관계를 보는 방법 (LOF)**이 더 잘 작동합니다.

이 연구는 컴퓨터가 방대한 텍스트 데이터 (로그 파일, 사용자 입력 등) 에서 이상한 것을 찾아내어, 시스템 오류를 미리 발견하거나 사기를 막는 데 도움을 줄 수 있음을 보여줍니다. 마치 파티에서 이상한 옷을 입은 손님을 찾아내는 두 가지 다른 눈썰미처럼, 상황에 맞는 눈을 선택하는 것이 중요합니다.

기술 요약

1. 문제 정의 (Problem)

• 배경: 이상치 탐지는 머신러닝의 핵심 문제이나, 대부분의 연구가 수치형 데이터에 국한되어 있습니다.
• 목표: 시스템 로그 파일의 비정상 활동 감지나 사용자 입력 데이터 정제 등을 위해 문자열 데이터에서 이상치를 효과적으로 탐지할 수 있는 알고리즘을 개발하고 비교하는 것입니다.
• 범위:
  • 문자열 유형: 단일 단어 (Single-word) 형태의 문자열.
  • 탐지 유형: 의미론적 (Semantic) 맥락 없이 구문론적 (Syntactical) 속성만을 기반으로 한 이상치 탐지.
  • 출력: 이상치 여부를 이진 분류 (Categorical) 하거나 이상 점수 (Anomaly Score) 를 부여하는 방식.

2. 방법론 (Methodology)

저자는 두 가지 주요 알고리즘을 제안하고 비교했습니다.

A. K-최근접 이웃 기반 접근법 (Local Outlier Factor - LOF 변형)

기존의 수치형 데이터용 LOF(Local Outlier Factor) 알고리즘을 문자열 데이터에 적용하기 위해 수정했습니다.

1. 거리 측정 (Distance Measure): 문자열 간의 거리를 계산하기 위해 레벤슈타인 거리 (Levenshtein Distance) 를 사용했습니다.
   • 계층적 가중치 (Hierarchical Weighting): 기본 레벤슈타인 거리는 모든 문자 교체 비용을 동일하게 처리하지만, 저자는 계층적 파티션 (Hierarchical Partition) 을 도입하여 문자 클래스 (숫자, 대소문자, 특수문자 등) 간의 위계 관계를 반영한 가중치를 부여했습니다. 예를 들어, 'a'를 'b'로 바꾸는 것보다 'a'를 '1'로 바꾸는 것이 더 큰 비용 (거리) 을 갖도록 설정하여 문법적 구조를 더 잘 반영하도록 했습니다.
2. k 값 결정: 이웃 수 $k$를 자동으로 결정하기 위해 KFCS(k-finder based on neighborhood consistency) 추정기를 사용했습니다.
3. 임계값 설정: 고정된 임계값 대신, 이상 점수의 평균에 계수를 곱한 동적 임계값 (Dynamic Thresholding) 방식을 사용하여 다양한 밀도의 이상치 군집을 탐지하도록 했습니다.

B. 정규식 기반 접근법 (Hierarchical Left Regular Expression - HiLRE)

데이터의 기대되는 패턴을 정규식으로 학습하여, 그 패턴에 맞지 않는 데이터를 이상치로 간주하는 방식입니다.

1. HiLRE 학습: [Dos+16] 의 계층적 왼쪽 정규식 (Hierarchical Left Regular Expression, HiLRE) 학습 알고리즘을 기반으로 합니다. 이는 모호성이 없고, 특정 계층 구조를 따르는 제한된 형태의 정규식입니다.
2. 이상치 탐지 전략:
   • 데이터의 모든 부분집합에 대해 가능한 HiLRE 를 생성합니다.
   • 각 HiLRE 가 데이터의 얼마나 많은 부분을 매칭하는지 계산합니다.
   • 최적의 정규식 ($H^*$) 선택: 하위 집합 정규식들과 비교했을 때, 매칭되는 데이터 포인트의 수를 가장 크게 늘리는 (최소 차이 최대화) 정규식을 선택합니다.
   • 최소 매칭 비율 ($p_{min}$) 파라미터: 선택된 정규식이 전체 데이터의 최소 비율 (예: 85%) 이상을 매칭해야 한다는 조건을 추가하여, 너무 엄격하거나 너무 느슨한 정규식 선택을 방지하고 알고리즘을 조정할 수 있게 했습니다.

3. 주요 기여 (Key Contributions)

1. 문자열용 LOF 알고리즘 제안: 레벤슈타인 거리에 계층적 문자 클래스 가중치를 도입하여, 단순한 편집 거리보다 구조적 유사성을 더 잘 반영하는 이상치 탐지 방법을 제시했습니다.
2. 새로운 정규식 기반 이상치 탐지 알고리즘: HiLRE 학습 알고리즘을 변형하여, 데이터의 구조적 패턴을 자동으로 학습하고 이상치를 식별하는 새로운 접근법을 개발했습니다.
3. 실제 데이터셋을 통한 비교 분석: 독일 병원 품질 보고서의 주소 (우편번호, 군 이름, 전화번호 등), 날짜, 시간 데이터 등 실제 세계 데이터를 사용하여 두 알고리즘의 성능을 정량적으로 비교했습니다.

4. 실험 결과 (Results)

실험은 합성 데이터와 실제 데이터 (우편번호, 군 이름, 전화번호, 날짜 등) 를 사용하여 수행되었으며, ROC 곡선 (True Positive Rate vs False Positive Rate) 으로 평가되었습니다.

• 구조가 명확한 데이터 (예: 우편번호 vs 군 이름):
  • HiLRE 알고리즘이 압도적으로 우수한 성능을 보였습니다. 우편번호 (5 자리 숫자) 와 같은 명확한 구조를 가진 데이터는 정규식으로 완벽하게 표현할 수 있어, 이상치 (군 이름) 를 0 의 오검출 (False Positive) 로 완벽하게 탐지했습니다.
  • LOF 알고리즘은 길이가 같은 군 이름과 우편번호를 구분하는 데 어려움을 겪었으며, 특히 계층적 가중치를 적용한 버전이 더 안정적이었지만 여전히 HiLRE 에 비해 성능이 떨어졌습니다.
• 구조가 불규칙하거나 잡음이 많은 데이터 (예: 군 이름 vs 우편번호):
  • HiLRE 알고리즘은 군 이름처럼 다양하고 복잡한 구조를 가진 데이터에서는 정규식을 학습하는 데 실패하여 이상치 탐지 성능이 급격히 떨어졌습니다.
  • LOF 알고리즘은 밀도 기반 접근법으로 인해 상대적으로 더 견고하게 작동했으나, 여전히 많은 오검출이 발생했습니다.
• 길이 차이가 있는 데이터 (예: 우편번호 vs 집 번호/전화번호):
  • LOF 알고리즘이 더 잘 작동했습니다. 문자열의 길이나 편집 거리가 명확히 다른 경우, 밀도 기반 탐지가 효과적이었습니다.
  • HiLRE는 다양한 길이의 숫자 문자열을 처리하는 데 어려움을 겪어 과적합 (Overfitting) 또는 과소적합 (Underfitting) 문제가 발생했습니다.

종합 결론:

• HiLRE는 데이터가 명확한 구조적 패턴 (규칙성) 을 가지고 있을 때 이상치 탐지에 가장 효과적입니다.
• LOF는 데이터가 구조적 규칙성보다는 편집 거리 (Length, Edit Distance) 에 기반하여 이상치가 구분될 때 더 효과적입니다.

5. 의의 및 의의 (Significance)

• 문자열 데이터 처리의 새로운 방향 제시: 수치형 데이터 중심이었던 이상치 탐지 연구의 한계를 극복하고, 텍스트 기반 데이터 (로그, 주소, 시계열 문자 등) 에 적용 가능한 구체적인 알고리즘을 제시했습니다.
• 알고리즘 선택 가이드라인 제공: 데이터의 특성 (구조적 규칙성이 강한가, 편집 거리 차이가 큰가) 에 따라 어떤 알고리즘을 선택해야 하는지에 대한 실용적인 통찰을 제공했습니다.
• 실무 적용 가능성: 시스템 로그 분석, 데이터베이스 정제, 입력 유효성 검사 등 다양한 분야에서 자동화된 이상치 탐지 솔루션의 기초를 마련했습니다.

이 논문은 문자열 데이터의 이상치 탐지가 단일 알고리즘으로 해결될 수 없으며, 데이터의 특성에 맞는 알고리즘 (구조 기반 vs 거리 기반) 을 선택하거나 하이브리드 접근이 필요함을 시사합니다.