연관 규칙 학습법

연관 규칙 학습법은 큰 데이터베이스에서 변수들 간의 흥미로운 관계를 발견하기 위한 규칙 기반 기계 학습 방법이다. 관심의 정도를 사용하여 데이터베이스에서 발견된 강력한 규칙을 구별하기 위한 것이다. 다양한 항목들과 주어진 모든 거래에서 연관 규칙은 특정한 항목이 연결되는 방법과 이유를 결정하는 규칙을 발견하기 위한 것이다.

강력한 규칙의 개념을 기초로 하여 라케시 아그라왈, 토마즈 이미엘린스키, 애런 스와미는 슈퍼마켓의 POS(point-of-sale) 시스템으로 기록된 대규모 거래 데이터에서 제품 간 규칙성을 발견하기 위한 연관 규칙을 도입했다. 예를 들어 슈퍼마켓의 판매 데이터에서 찾아진 {감자, 양파} ⇒ {햄버거} 규칙은 만약 손님들이 감자와 양파를 함께 구매한다면 햄버거 고기 또한 구매할 것이라는 것이다. 이러한 정보는 홍보 가격 매기기 또는 제품 배치와 같은 마켓팅 활동에 대한 결정을 위해 기초로서 사용될 수 있다.

장바구니 분석으로부터의 위의 예시 외에도 연관 규칙은 오늘날 웹 사용 마이닝, 침입 탐지, 지속적인 생산, 생물 정보학을 포함하는 많은 응용 분야에서 사용된다. 시퀀스 마이닝(sequence mining)과 대조적으로 연관 규칙 학습법은 일반적으로 거래 내에서나 거래 사이에서의 항목의 순서를 고려하지 않는다.

연관 규칙 알고리즘 자체는 데이터 마이닝에 대한 전문 지식이 없는 사람들이 실행하기 어렵게 만들 수 있는 다양한 매개 변수로 구성되었고 이해하기 어려운 규칙이 많다.

그럼에도 불구하고 연관 규칙 학습법은 데이터 상호 연결에서 행동을 예측하기 위한 훌륭한 시스템이다. 이점은 연관 규칙 학습법을 기계 학습 방법을 구현할 때 데이터의 패턴 분류나 발견을 위한 주목할 만한 기술로 만든다.

정의

아그라왈, 이미엘린스키, 스와미의 원래 정의를 따라 연관 규칙 마이닝 문제는 다음과 같이 정의된다.

$I=\{i_{1},i_{2},\cdots ,i_{n}\}$가 n개의 이진 원소들로 되어 있다고 하자.

$D=\{d_{1},d_{2},\cdots ,d_{n}\}$가 데이터베이스라는 일련의 거래라고 하자.

$D$의 각각의 거래는 독특한 거래 ID를 가지며 $I$의 부분집합을 포함한다.

규칙은 포함의 형식으로서 정의된다.

$X,Y\subseteq I$일 때 $X\Rightarrow Y$

아그라왈, 이미엘린스키, 스와미에서 규칙은 오직 하나의 집합과 하나의 원소 사이에서만 정의된다. $X\Rightarrow i_{j}$ $i_{j}\subseteq I$

모든 규칙은 두 개의 다른 집합의 원소들로 구성된다, 또한 그 집합들은 $X$가 선행 사건 또는 왼쪽 부분이라고 불리고 $Y$는 결과 또는 오른쪽 부분이라고 불리는 $X$와 $Y$ 원소 집합으로도 알려져 있다. 결과가 선행 사건과 결합했을 때 찾아지는 원소인 반면, 선행 사건은 데이터에서 찾아질 수 있는 원소이다.