Contrast set learning & treatment learning (STUCCO, TAR3)
1. Contrast set learning
Before starting: contrast set은 대조군이라는 말과 같으며, 대조할 수 있도록 데이터 내에서 여러가지 다른 속성을 가지는 경우를 말한다. contrast set은 속성-값 쌍 형태로 이루어져 있다.
Contrast set learning은 연관 규칙 학습의 형태로, 각 그룹을 잘 구분할 수 있는 주요 predictors를 찾는 학습 방법이다. 연관 규칙 모델은 일반적으로 training set에서 일반적으로 함께 발생하는 속성을 연결하는 규칙을 제공한다. 예를 들어, 4년 짜리 프로그램에 등록하고 전체 과정을 수료한 사람들은 캠퍼스 근처에 사는 경향이 있다. 대조군 학습자는 현재 상황을 설명하는 규칙을 찾는 대신 그룹 간 분포에서 의미가 다른 규칙을 찾는다. 따라서, 이러한 그룹의 예측 변수로 사용할 수 있다. 예를 들어 contrast set learner는 "학사 학위 소지자나 박사 학위 소지자의 주요 식별자는 무엇이며, 박사 학위 소지자는 어떻게 다른가?"라고 질문할 수 있다.
데이터 마이닝은 일반적으로 개체의 특성을 분류하고 관찰된 항목이 어떤 범주에 속하는지 예측하는 것이다. 이 과정에서 학습 데이터를 이용하고, 새로운 데이터가 입력된다면 추가적으로 학습함으로써 기존의 가설(모델)을 개선한다. 반면, Contrast set learning의 학습방식은 이와는 반대이다. 학습된 분류 모델은 새로운 데이터를 각 클래스로 나누누는 반면, contrast set learning은 항목이 속한 범주를 이용하여 데이터가 특정 클래스로 판정되는 통계적 증거를 거꾸로 찾아낸다. 즉, contrast set 모델은 속성 값을 클래스 분포의 변경과 연관되는 규칙을 찾는다. 즉, 한 분류와 다른 분류를 대조하여 주요 예측 변수를 식별하려고 한다.
예를 들어, 항공 우주 공학자는 새로운 로켓의 시험 발사에 대한 데이터를 기록할 것이다. 로켓의 궤적, 작동 온도, 외부 압력 등과 같은 요인은 발사 내내 주기적으로 측정될 것이다. 로켓 발사가 여러 번의 성공적인 시험 후에 실패한다면, 엔지니어는 대조군 집합 학습을 사용하여 성공과 실패의 시험을 구별할 수 있다. 이러한 데이터를 학습시켜 contrast set learning을 적용하면, 각 시험의 주요 예측 변수 대 성공한 시험의 핵심 예측 변수(온도가 너무 높았고 풍압이 너무 높았던 경우 등)를 나타내는 일련의 연관 규칙을 생성한다. 이처럼 어떤 constrast set이 예측 변수를 다르게 만들었는지 찾는 것이 문제이다.
C4.5와 같은 표준 분류 알고리즘은 클래스의 중요성에 대한 개념이 없다(즉, 클래스가 "좋은" 것인지 "나쁜" 것인지 알지 못한다). 이러한 모델들은 원하는 클래스로 예측되도록 bias를 주거나 필터링할 수 없다. Contrast set learning의 목표는 그룹 간의 의미 있는 차이를 발견하는 것이므로, 특정한 클래스로 분류되도록 목적을 가지고 모델을 학습시키는 것이 좋다. MINWAL 또는 TAR 알고리즘과 같은 contrast set learner는 각 클래스에 가중치를 부여하는 방식을 사용한다.
Example: Supermarket Purchases
분류, 연관 규칙 학습, contrast set learning의 차이점은 간단한 슈퍼마켓 예시로 설명할 수 있다. 다음의 작은 데이터 집합에서 각 행은 슈퍼마켓 거래로, 각 "1"은 해당 품목이 구매되었음을 나타내며, 0"은 해당 품목이 구매되지 않았음을 나타낸다.
| Hamburger | Potatoes | Foie Gras | Onions | Champagne | 구입 목적 |
| 1 | 1 | 0 | 1 | 0 | 요리 |
| 1 | 1 | 0 | 1 | 0 | 요리 |
| 0 | 0 | 1 | 0 | 1 | 기념일 |
| 1 | 1 | 0 | 1 | 0 | 요리 |
| 1 | 1 | 0 | 0 | 1 | 파티 |
- 연관 규칙 학습은 양파와 감자를 함께 사는 고객들도 햄버거 고기를 살 가능성이 높다는 것을 발견할 수 있다.
- 분류에 따르면 양파, 감자, 햄버거 고기를 산 고객들은 요리할 물건을 구입하고 있었다는 것을 발견할 수 있다.
- Contrast set learning은 요리를 하려는 고객과 기념일 저녁 식사를 위한 쇼핑 간의 주요한 차이점을 발견한다. 요리를 하려는 고객들은 양파와 감자, 햄버거 고기를 구입하고 그리고 푸아그라나 샴페인은 사지 않는다.
변수가 많아지면 탐색 공간이 속성-값 쌍의 수에 지수적으로 증가하여 매우 커지므로 쉽게 탐색할 수 없다.
※ 연관 규칙과 Support
연관 규칙에서 규칙의 효용성을 나타내는 지표는 지지도(support)와 신뢰도(confidence), 향상도(lift)가 있다. 그 중 지지도는 조건부 확률에서 조건이 일어날 확률로 정의된다.
$${\displaystyle \mathrm {supp} (X)={\frac {|\{t\in T;X\subseteq t\}|}{|T|}}} $$
아래의 표를 이용하여 지지도 X ={beer, diapers} 의 지지도를 구해보면 1/5=0.2 이다.
$${\mathrm {lift}}(X\Rightarrow Y)={\frac {{\mathrm {supp}}(X\cup Y)}{{\mathrm {supp}}(X)\times {\mathrm {supp}}(Y)}}$$
이를 이용하여 \( \textrm{{milk, bread}} \Rightarrow \textrm{{butter}} \) 를 계산하면 $$ \frac{0.2}{0.4\times 0.4}=1.25 $$
2. Treatment learning
Treatment learning은 하나의 '원하는' 그룹을 취하여 나머지 '원하지 않는' 그룹과 대조되도록 하는 weighted contrast-set learning의 한 형태이다(desirability 수준은 weighted class로 표현된다). Treatment learning의 결과는, 적용되었을 때 원하는 출력을 이끌어내는 일련의 규칙을 제시한다.
Treatment learning은 contrast-set learning과 달리 다음과 같은 제약조건을 가진다.
- Treatment learning은 모든 그룹 간의 차이를 추구하기 보다는 초점을 맞출 특정 그룹을 지정하고, 이 원하는 그룹에 가중치를 적용하며, 나머지 그룹을 하나의 "원하지 않는" 범주로 묶는다.
- Treatment learning은 최소 이론에 명시적으로 초점을 맞추고 있다. 실제로 treatment는 최대 4가지 제약조건으로 제한된다. 즉, 로켓이 스케이트보드와 다른 이유를 모두 진술하는 것이 아니라, treatment learner는 로켓으로 예측할 때 높은 통계적 유의도를 가지는 1~4가지 주요 차이점을 제시한다.
단순함은 treatment learner가 추구하는 중요한 목표이다. Treatment learning은 클래스 분포에 가장 큰 영향을 미치는 가장 작은 변화에 주목한다.
treatment learning은 모든 속성이 가지는 값 범위의 모든 가능한 부분 집합을 탐색한다. 그러한 탐색은 실제로 실행될 수 없는 경우가 많기 때문에 treatment learning은 속성 범위를 빠르게 가지치기 하고 무시한다. 하지만, 이러한 방식 적용하면 원하는 클래스가 소수인 계층이 있는 계층 분포를 초래한다.
Example: Boston housing data
다음은 보스턴시의 주택 데이터에 대한 treatment learner TAR3의 출력의 예제이다. 이 데이터 셋에서는 각 주택에 대해 여러 가지 요인을 수집하고, 각 주택은 low, medium-low, medium-high, high로 분류한다. '원하는' 클래스는 "높음"으로 설정되며, 다른 클래스는 '원하지 않는' 클래스로 일괄 처리된다.
TAR3의 출력은 다음과 같다.
Baseline class distribution:
low: 29%
medlow: 29%
medhigh: 21%
high: 21%
Suggested Treatment: [PTRATIO=[12.6..16), RM=[6.7..9.78)]
New class distribution:
low: 0%
medlow: 0%
medhigh: 3%
high: 97%적용된 treatment(규칙)가 없는 경우 원하는 클래스는 전체 클래스 분포의 21%에 불과하다. 그러나 6.7~9.78개의 방과 이웃이 학부모-교사의 관계를 가지는 비율이 12.6~16인 비율을 가진 주택으로 데이터 셋을 필터링하면 97%가 원하는 등급(높은 등급의 주택)으로 분류된다.
3. 알고리즘
여러 Contrast set learning 알고리즘 중에 STUCCO와 TAR3에 대해 알아보자.
STUCCO
STUCCO는 contrast set을 학습하는데 트리 탐색 문제로 접근한다. 루트 노드는 빈 대조군이며, Children은 (동일한 노드를 두 번 방문하는 것을 피하기 위해) 표준적인 속성 순서를 통해 선택된 추가 아이템으로 세트를 전문화하여 추가된다. 아이들은 주어진 순서에 따라 기존의 모든 용어를 추가함으로써 형성된다. 형성된 나무는 너비 우선으로 탐색된다. 각 레벨의 노드를 고려하여 데이터 세트를 스캔하고 각 그룹에 대해 support을 계산한다. 그런 다음 각 노드를 검사하여 중요하고 큰지 여부, 잘라내야 하는지 여부 및 새 아이를 생성해야 하는지 여부를 판단한다. 모든 유의한 대조군을 배치한 후, 포스트 프로세서는 사용자에게 보여줄 서브셋을 선택한다. 즉, 낮은 순서, 단순한 결과가 먼저 표시되고, 그 다음에 "의미가 있는" 상위 순서 결과가 나타난다.[3]"
지원 계산은 대조군 집합 지원이 모든 그룹에서 동일하다는 귀무 가설(즉, 대조군 집합 지원은 그룹 구성원 자격과 무관함)을 시험하는 데서 나온다. 각 그룹에 대한 지원 카운트는 각 행이 대조군의 진가를 나타내고 각 열 변수가 그룹 멤버쉽 주파수를 나타내는 우발상황표에서 분석할 수 있는 주파수 값이다. 대조 세트 주파수와 귀무 가설의 비율 차이가 있는 경우, 알고리즘은 비율의 차이가 변수 사이의 관계를 나타내는지 또는 무작위 원인에 기인할 수 있는지를 결정해야 한다. 이는 관측된 주파수 카운트를 예상 카운트와 비교하는 카이-제곱 검정을 통해 결정할 수 있다.
노드의 모든 분기가 유의미하고 조건 절이 더 이상 많아질 수 없을 때 노드는 트리에서 제거된다. Pruning 방법은 다음과 같다.
최소 편차 크기: 두 그룹의 support 간의 최대 차이는 사용자가 지정한 임계값보다 커야 한다. 즉, 대비하고자 하는 그룹의 support 간 차이가 적으면 조건에 따라 구분이 안될 가능성이 높다.
기대 샘플의 비율: 결과를 잘 구분하는 조건(contrast set)이 구체화됨에 따라 결과 테이블에서 기대하는 샘플(조건에 맞는 샘플)의 빈도(confidence)가 감소할 수 있다. 이러한 빈도가 너무 작을 경우 카이-제곱 검정의 유효성을 위반한다.
\( {\displaystyle \chi ^2} \) 경계: 귀무 가설이 참일 때 계산된 통계의 분포에 상한선이 유지된다. 노드는 더 이상 이 컷오프를 충족시킬 수 없을 때 제거된다.
TAR3
TAR3 weighted contrast set learner는 규칙 집합의 lift(향상도)와 support(지지도) 두 가지 기본 개념을 기반으로 한다.
규칙 집합에서 lift란 조건과 결과가 서로 독립일 때와 비교해 두 사건이 동시에 얼마나 발생하는지를 나타내는 지표이다. 쉽게 말해 엑셀에서 어떤 컬럼에 조건 필터를 적용했을때, 우리가 보고자 하는 결과가 전체에서 차지하는 비율이 같으면 lift가 1이다.
lift가 1이면 \( P(A\cap B)=P(A)\cdot P(B) \)가 되어 A와 B가 독립임을 뜻한다. 따라서 규칙 사이에 유의미한 연관성이 없다는 뜻이다. 만약 lift가 2이면 필터를 적용했을 때 우리가 찾는 결과(예를 들어 y가 20~25 인 row)가 필터를 적용하기 전보다 2배 많아졌다는 뜻이다. 즉, 필터 조건(조건절)이 매우 유효하다고 할 수 있다. 어떤 결정(조건 적용)이 그 결정을 내린 후 샘플의 변화(즉, 규칙의 부과에 대응하여 클래스의 분포가 어떻게 변화하는지)에 따라 lift가 달라진다.
$$ lift(A\rightarrow B)\frac{P(A,B)}{P(A)\cdot P(B)} $$
TAR3은 각 클래스의 빈도에 따라 가중치를 부과한다. 그리고 규칙 셋은 최소화하고 클래스의 변화가 가장 크도록하는 규칙을 찾는다. 향상도(lift)를 계산할 때, 규칙이 적용되지 않은 베이스라인 스코어를 기준으로 하여 규칙이 적용됐을 때의 값을 베이스라인 스코어로 나눈다. Lift score의 역함수를 적용함으로써, TAR3 학습자는 기존 클래스는 선택하고 타겟 클래스는 reject 한다.
규칙 집합의 lift만 보고 유효성을 판단하는 것은 문제가 있다. 잘못된 데이터나 노이즈가 있을 경우 지지도(lift) 값은 높지만 규칙의 오버피팅을 유발할 수 있다. 오버핏된 규칙은 lift 값이 클 수 있지만 데이터 셋 내의 현재 상태를 정확하게 반영하지 못한다. 오버핏을 피하기 위해 TAR3는 support의 임계값을 활용한다. 즉, 조건절을 적용했을 때, 조건에 맞는 샘플이 너무 적으면 통계적 유의미성을 잃는다고 판단하는 것이다. 타겟 클래스가 주어졌을 때의 support 임계값은 사용자 지정 값(일반적으로 0.2)으로, 전체 데이터 셍에서 target 클래스의 비율과 규칙 집합이 적용되었을 때의 대상 클래스의 비율을 비교한다. TAR3은 이 임계값보다 낮은 support를 가진 모든 규칙 집합을 reject한다.
높은 lift와 높은 support 값을 모두 요구함으로써 TAR3는 이상적인 규칙 집합을 반환할 뿐만 아니라 낮은 복잡도의 규칙 집합을 만들도록 한다.
TAR3 알고리즘은 높은 heuristic 값을 가진 속성 값 범위에서만 규칙 집합을 만든다. 이 알고리즘은 lift score를 결정할 때, 각 속성 값의 범위를 고려한다. 그리고 각 속성 별 스코어를 정렬한 후 누적 누적 확률 분포로 변환된다. TAR3는 이 분포에서 무작위로 값을 선택하는데, 이는 낮은 점수 범위를 선택할 가능성이 낮다는 것을 의미한다. 또한, 높은 점수 범위를 선택할 가능성도 낮아지는데 이는 규칙의 과적합을 방지할 수도 있다. 후보 규칙 집합을 생성하기 위해 몇 몇 범위를 선택하고 결합한다. 그런 다음 이 후보 규칙 집합을 채점하고 분류한다. 사용자가 정의한 라운드 횟수 후에도 개선이 보이지 않으면 알고리즘이 종료되어 최상위 점수 규칙 집합을 반환한다.
Reference