어소시에이션

Association rule learning

연관 규칙 학습은 대규모 데이터베이스에서 변수 간의 흥미로운 관계를 발견하기 위한 규칙 기반 기계 학습 방법입니다.이는 데이터베이스에서 발견된 강력한 규칙을 특정하기 위한 것으로,[1] 몇 가지 관심 척도를 사용합니다.다양한 항목이 있는 트랜잭션에서 연결 규칙은 특정 항목이 연결되는 방법 또는 이유를 결정하는 규칙을 발견하기 위한 것입니다.

Rakesh Agrawal, Tomasz Imieliskiski, Arun[2] Swami는 강력한 룰의 개념을 바탕으로 슈퍼마켓의 POS(Point-of-Sale) 시스템에 의해 기록된 대규모 거래 데이터에서 상품 간의 규칙성을 발견하는 관련 규칙을 도입했다.예를 들어 슈퍼마켓의 판매 데이터에서 된 { n ns , { r { \ { \ {, } \ } \ \ { \ { \ }{ { { { { { { { { { { { { potatoes , { potatoes , { potatoes , { and 、 고객이 양파와 감자를 함께 구입하는 경우에도 햄버거를 나타냅니다.이러한 정보는 프로모션 가격이나 제품 판매 등의 마케팅 활동에 대한 결정의 기준으로 사용할 수 있습니다.

시장 바스켓 분석 협회 규칙은 위의 예와 더불어 오늘날 웹 사용 마이닝, 침입 탐지, 연속 생산 및 생물 정보학포함한 많은 응용 분야에서 채택되고 있습니다.시퀀스 마이닝과 대조적으로, 연관 규칙 학습은 일반적으로 거래 내 또는 거래 간 항목의 순서를 고려하지 않는다.

어소시에이션 룰 알고리즘 자체는 데이터 마이닝에 관한 전문지식이 없는 사용자가 실행하기 어려운 다양한 파라미터로 구성되어 있습니다.[3]

정의.

데이터 세트의 항목 집합 X와 Y 사이의 연관성을 보여주는 벤 다이어그램입니다.항목 X를 포함하는 모든 트랜잭션은 원의 왼쪽 흰색 부분에 위치하며 Y를 포함하는 트랜잭션은 빨간색과 오른쪽에 표시됩니다.X와 Y를 모두 포함하는 모든 트랜잭션은 중간에 위치하며 분홍색입니다.이 그래프에서 정보를 묘사하기 위해 여러 개념을 사용할 수 있습니다.예를 들어 분홍색 섹션의 모든 트랜잭션을 총 거래량(X(흰색)+Y(빨간색) 트랜잭션)으로 나누면 출력은 지원이라고 합니다.신뢰라고 하는 방법의 결과를 얻는 예에서는, 중간(분홍)의 모든 트랜잭션을 Y를 포함한 모든 트랜잭션(분홍)으로 나눌 수 있습니다.이 경우 Y가 선행이고 X가 결과입니다.

Agrawal, Imieli swski[2], Swami의 최초 정의에 따라 관련 규칙 마이닝의 문제는 다음과 같이 정의된다.

{ , 2 , , i { I = \ { _ { , i { , \, i {} 、 n items items items 。

Let be a set of transactions called the database.

D D트랜잭션은 고유한 트랜잭션 ID를 가지며I(\ I 의 서브셋을 포함합니다.

규칙은 다음 형식의 함축으로 정의됩니다.

[ Y ( \ X \ Y서 Xdisplay I \ X \ I) 。

아그라왈, 이미엘린스키, 스와미에서는[2] 규칙이란 집합과 단일 항목( I { display X \ i _ }) 사이에만 정의됩니다. jI { i _ { } \ I

모든 규칙은 항목 집합이라고도 하는 X(디스플레이 X Y 의 두 가지 다른 항목 집합으로 구성됩니다. 서 X X 선행 또는 왼쪽(LHS) 및 Y 결과 또는 오른쪽(RHS)이라고 합니다.선행조건은 데이터에서 찾을 수 있는 항목이며, 결과는 선행조건과 결합했을 때 찾을 수 있는 항목이다. XY ( \ style X \ Y )는 보통X ( \ X Y ( \ Y )로 해석됩니다.여기서 선행어 \ X )는 if, (\ Y)는 다음과 같습니다.이는 이론적으로 데이터셋에서 XX})가 발생할 마다 Y Y 발생한다는 것을 의미합니다.

과정

연관 규칙은 빈번한 if-then 패턴을 검색하고 Support and Confidence 아래의 특정 기준을 사용하여 가장 중요한 관계를 정의함으로써 만들어집니다.신뢰도는 if-then 문장이 참인 횟수에 의해 정의되므로, 지원은 주어진 데이터에 항목이 얼마나 자주 표시되는지를 나타내는 증거입니다.그러나 사용할 수 있는 세 번째 기준이 있는데, 이를 리프트라고 하며 기대 신뢰도와 실제 신뢰도를 비교하는 데 사용할 수 있습니다.리프트는 if-then 스테이트먼트가 참이라고 예상되는 횟수를 나타냅니다.

연결 규칙은 두 개 이상의 항목으로 작성된 항목 집합에서 계산하도록 만들어집니다.모든 가능한 항목 집합을 데이터에서 분석하여 규칙을 만들었다면 규칙이 너무 많아 아무런 의미가 없을 것입니다.이것이 바로 Association 규칙이 일반적으로 데이터로 잘 표현되는 규칙에서 만들어지는 이유입니다.

특정 분석 및 결과를 찾는 데 사용할 수 있는 다양한 데이터 마이닝 기술이 있습니다. 예를 들어 분류 분석, 클러스터링 분석 및 회귀 [4]분석 등이 있습니다.데이터에 대해 무엇을 찾고 있는지에 따라 어떤 기술을 사용해야 하는지에 따라 달라집니다.연결 규칙은 주로 분석 및 고객 행동의 예측을 찾는 데 사용됩니다.분류 분석의 경우, 대부분의 경우 질문, 결정 및 [5]동작 예측에 사용됩니다.군집화 분석은 [5]주로 데이터 내에서 가능한 관계에 대한 가정이 없는 경우에 사용됩니다.회귀 분석 여러 독립 [5]변수에서 연속 종속 변수의 값을 예측하려는 경우 사용합니다.

혜택들

데이터 세트 간의 상관 관계와 공존 관계를 이해하는 데 도움이 되는 패턴을 찾는 등 관련 규칙을 사용하면 많은 이점이 있습니다.협회의 규칙을 사용하는 매우 좋은 현실 세계의 예는 의학일 것이다.의학에서는 환자 진단을 돕기 위해 협회 규칙을 사용합니다.환자를 진단할 때 많은 질병이 비슷한 증상을 공유하기 때문에 고려해야 할 변수가 많다.의사회 규칙을 사용하여 의사는 과거의 [6]증례와 증상 관계를 비교하여 질병의 조건부 확률을 결정할 수 있다.

다운폴

그러나 어소시에이션규칙은 마이닝알고리즘에 적절한 파라미터와 임계값 설정을 찾는 등 다양한 다운을 초래하기도 합니다.하지만 발견된 규칙들이 많아지는 몰락도 있다.그 이유는 이것이 규칙이 관련된 것으로 판명되는 것을 보증하는 것은 아니지만 알고리즘의 퍼포먼스가 저하될 수도 있기 때문입니다.구현된 알고리즘에 너무 많은 변수와 파라미터가 포함될 수 있습니다.데이터 마이닝에 대한 개념이 좋지 않은 사용자는 데이터 [7]마이닝을 이해하는 데 어려움을 겪을 수 있습니다.

임계값

자주 사용되는 항목 집합 격자 - 상자의 색상은 항목 조합을 포함하는 트랜잭션 수를 나타냅니다.격자의 하위 레벨에는 부모 항목의 최소 수를 포함할 수 있습니다. 예를 들어 {ac}에는 최대 ( c \ 항목만 포함할 수 있습니다.이를 하향 폐쇄 [2]속성이라고 합니다.

연결 규칙을 사용할 때는 대부분 지원 및 신뢰만 사용합니다.단, 사용자 지정 최소 지원과 사용자 지정 최소 신뢰도를 동시에 충족해야 합니다.통상, 어소시에이션규칙의 생성은, 적용할 필요가 있는 다음의 2개의 다른 순서로 분할됩니다.

  1. 데이터베이스에 있는 모든 자주 사용되는 항목 집합을 찾기 위한 최소 지원 임계값입니다.
  2. 규칙을 만들기 위해 발견된 자주 사용되는 항목 집합에 대한 최소 신뢰 임계값입니다.
표 1.
항목들 지지하다 자신감. 항목들 지지하다 자신감.
아이템 A 30% 50% 아이템 C 45% 55%
아이템 B 15% 25% 아이템 A 30% 50%
아이템 C 45% 55% 아이템 D 35% 40%
아이템 D 35% 40% 아이템 B 15% 25%

지원 임계값은 30%, 신뢰 임계값은 50%입니다.

왼쪽 테이블은 원래 미정리 데이터이고 오른쪽 테이블은 임계값별로 구성됩니다.이 경우 항목 C가 지지와 신뢰에 대한 임계값보다 낫기 때문에 첫 번째가 됩니다.항목 A는 임계값은 스폿 온이므로 두 번째입니다.항목 D는 지원 문턱값을 충족했지만 신뢰도는 충족되지 않았습니다.항목 B는 지지 또는 신뢰의 문턱을 충족하지 못했기 때문에 마지막이다.

데이터베이스에서 자주 사용되는 항목 집합을 모두 찾는 것은 모든 데이터를 검토하여 가능한 모든 항목 집합에서 가능한 모든 항목 조합을 찾는 것이므로 쉬운 작업이 아닙니다.가능한 항목 집합은 I 전원 집합이며 -(\ 2입니다. 이는 물론 유효한 항목 집합으로 간주되지 않는 빈 집합을 제외하는 것을 의미합니다.그러나 전력 집합의 크기는 전력 집합 I 내의 항목 n의 수에서 기하급수적으로 증가합니다.서포트의 하향 폐쇄 특성[9](단일성 방지라고도[2][8] 함)을 사용하면 효율적인 검색이 가능합니다.이는 빈도가 높은 항목 집합과 그 하위 집합도 빈도가 높으므로 빈도가 높은 항목 집합의 하위 집합으로서 빈도가 낮은 항목 집합을 갖지 않을 것이다.이 속성을 이용하면 효율적인 알고리즘(예: Apriori[10] 및 Eclat[11])이 자주 사용되는 모든 항목 집합을 찾을 수 있습니다.

유용한 개념

표 2
트랜잭션 ID 우유 버터 맥주 기저귀 달걀 과일
1 1 1 0 0 0 0 1
2 0 0 1 0 0 1 1
3 0 0 0 1 1 0 0
4 1 1 1 0 0 1 1
5 0 1 0 0 0 0 0

개념을 설명하기 위해 슈퍼마켓 도메인의 작은 예를 사용합니다.표 2는 각 엔트리에서 값 1은 해당 트랜잭션에서 항목의 존재를 의미하고 값 0은 해당 트랜잭션에서 항목의 부재를 나타내는 항목을 포함하는 작은 데이터베이스를 보여준다.항목 세트는 { , r , e , d s , s, t { I= \ { displaystyle I= \ , br e 입니다

슈퍼마켓의 규칙 예로는 { e, e d { i k { \ { \ {bread } \ \ { \ { \ { }}이 있습니다.이는 버터와 빵을 구입하면 우유도 구매한다는 의미입니다.

가능한 모든 규칙 집합에서 흥미로운 규칙을 선택하기 위해 중요성과 관심의 다양한 척도에 대한 제약이 사용된다.가장 잘 알려진 제약사항은 지원 및 신뢰도에 대한 최소 임계값입니다.

X X)를 항목 세트, X\ Y 연관 규칙, T(style X\right 화살표 Y)를 특정 데이터베이스의 트랜잭션 세트라고 .

주의: 이 예는 매우 작습니다.실제 응용 프로그램에서는 규칙이 통계적으로 [citation needed]유의하다고 간주되기 전에 수백 개의 트랜잭션을 지원해야 하며, 데이터 세트에는 수천 또는 수백만 개의 트랜잭션이 포함되어 있는 경우가 많습니다.

지지하다

지원은 데이터 세트에 항목 집합이 나타나는 빈도를 나타냅니다.

이 예에서는 t ( B) ( = P B) = 및 {TEXT이라고 쓰면 을 쉽게 설명할 수 있습니다. 여기서[12] A와 B는 기록된 트랜잭션의 총 집합 내에서 이루어진 개별 트랜잭션입니다.

표 2를 예로 들면, 항목 X= {b , p e r s { X \ { \ { \}는 전체 트랜잭션(5건 중 )의 20%에서 발생하므로 / 5 0.을 갖습니다.X에 대한 지원 주장은 전제 조건의 집합이며, 따라서 X가 증가할수록(포괄적인 [13]것이 아니라) 더 제한적으로 됩니다.

또한 항목 Y { k , r d , e r { \ { { \ { 1/.\ of transactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactions further further further further further further furtherfurther further further further further further further further further further further furtheractionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactionsactions further further further further further further further further further further further further further further further y y y y y y y y y

선행 요소 및 결과를 사용할 때 데이터 마이너는 전체 데이터 집합과 비교하여 함께 구입하는 여러 항목의 지원을 결정할 수 있습니다.예를 들어, 표 2는 우유를 산다면 빵은 0.4 또는 40%의 지지를 받는다는 것을 보여준다.왜냐하면 거래의 5분의 2는 빵뿐만 아니라 우유도 구입하기 때문입니다.이 예시와 같이 작은 데이터 집합에서는 표본이 적으면 강한 상관 관계를 확인하기 어렵지만, 데이터 집합이 커지면 지원을 사용하여 슈퍼마켓 예제에서 두 개 이상의 제품 간의 상관 관계를 찾을 수 있습니다.

최소 지원 임계값은 선호 항목 집합 또는 대상 항목 집합을 결정하는 데 유용합니다.

표 3에서 지원 임계값을 0.4로 설정하면 { l { s { \ { \ { \ } \ \ { \ {} \ 최소 임계값 0.4 를 충족하지 못했기 때문에 삭제됩니다.최소 임계값은 데이터 집합에서 샘플이 중요하거나 관심 있는 것으로 간주할 만큼 충분한 지원이나 신뢰성이 없는 샘플을 제거하는 데 사용됩니다.

흥미로운 샘플을 찾는 또 다른 방법은 (support)X(신뢰도)의 값을 찾는 것입니다. 이렇게 하면 데이터 마이너는 데이터셋에서 지원 및 신뢰도가 강조 표시될 정도로 높은 샘플을 확인하고 샘플에서 항목 간의 연결에 대한 자세한 정보를 찾을 수 있습니다.

지원은 전체 데이터셋에 비해 제품 간의 연결을 찾는 데 도움이 될 수 있으며, 자신감은 하나 이상의 항목과 다른 항목 간의 연결을 살펴봅니다.아래 표는 표 4의 정보를 사용하여 신뢰도 값을 도출하여 지지와 지지 x 신뢰도 간의 비교와 대조를 보여준다.

표 3
선행 조건일 경우 결과 지지하다 X자신임을 지지하다
우유를 산다면 빵을 사세요. 2/5= 0.4 0.4X1.0 = 0.4
우유를 산다면, 달걀을 사세요. 1/5= 0.2 0.2X0.5= 0.1
빵을 산다면 과일을 사세요. 2/5= 0.4 0.4X0.66= 0.264
과일을 산다면, 달걀을 사세요. 2/5= 0.4 0.4X0.66= 0.264
만약 우유와 빵을 산다면, 과일을 사세요. 2/5= 0.4 0.4X1.0 = 0.4

T에 대한 X의 지원은 항목 집합 X를 포함하는 데이터 집합에서 트랜잭션의 비율로 정의됩니다. { 트랜잭션을 나타내며, 여기서 i는 트랜잭션의 고유 식별자이고 t는 해당 항목 세트입니다. 지원은 다음과 같이 기술할 수 있습니다.

이 표기법은 위의 슈퍼마켓 예시와 같이 항목 및 항목 집합이 쉽지 않을 수 있는 보다 복잡한 데이터 집합을 정의할 때 사용할 수 있습니다.지원을 이용할 수 있는 다른 예로는 질병을 일으키기 위해 집단적으로 작용하는 유전자 돌연변이 그룹을 찾고, 업그레이드 제안에 응답하는 가입자의 수를 조사하며, 약국에서 [12]함께 구매하지 않는 제품을 발견하는 것이다.

자신감.

신뢰도는 X를 만족하는 모든 트랜잭션에서 [14]Y를 만족시키는 비율입니다.

T에 관해서, 관련 규칙의 신뢰치(종종 X Y \ X \ Y )는 X 와 Y양쪽 모두를 포함한 트랜잭션의 비율입니다.여기서 X 는 선행치, Y 는 결과치입니다.

신뢰는 조건부 P E 의 추정치(\ P로도 해석할 수 있다.이것은, 이러한 거래에도 [13][15]LHS가 포함되어 있는 것을 전제로 한 거래에서 룰의 RHS를 찾아낼 확률이다.

일반적으로 다음과 같이 표현됩니다.

이 방정식은 데이터 집합 내의 트랜잭션 X와 Y의 공존을 X만을 포함하는 트랜잭션과 비교하여 계산함으로써 신뢰도를 계산할 수 있음을 나타냅니다.즉, X와 Y의 양쪽 트랜잭션 수가 X의 트랜잭션 수로 나누어집니다.

예를 들어 표 2는 가 11/5 1/ 1/ 0.2 0.2 .2 = 1.0{\ \}인 규칙{ , { k { m i k }\ { bread} \}}를 우스토머는 버터와 빵을 사고 그들은 우유도 산다.이 예에서는 버터와 빵이 모두 포함된 트랜잭션에 대해 규칙이 100% 정확함을 보여 줍니다.그러나 규칙 { i t { { \ { \ { } \\ { \ { } \} .6 . { \ / 5 { } fru { } fr} { 04 } g s } = fruit } fruit 이 특정 데이터 세트 내에서 과일은 총 3회 구매되며, 그 중 2회는 계란 구매로 구성됩니다.

더 큰 데이터 집합의 경우 신뢰도를 위한 최소 임계값 또는 백분율 컷오프가 항목 관계를 결정하는 데 유용할 수 있습니다.표 2의 일부 데이터에 이 방법을 적용하면 요건을 충족하지 못하는 정보는 제거됩니다.표 4는 신뢰도의 최소 임계값이 0.5(50%)인 관련 규칙의 예를 나타내고 있습니다.신뢰도가 0.5 이상인 데이터는 모두 생략됩니다.임계값을 생성하면 가장 많이 발생하는 항목들을 강조하여 데이터를 추가로 조사할수록 항목들 간의 연관성이 강화됩니다.이 표는 표 3의 신뢰도 정보를 사용하여 지지 x 신뢰도 열을 구현한다. 여기서 하나의 개념이 아닌 신뢰도와 지지를 통한 항목 간의 관계가 강조된다.Support x Confidence에 의한 규칙 순위는 특정 규칙의 신뢰도를 지원으로 배가시키며, 종종 항목 간의 관계를 보다 심층적으로 이해하기 위해 구현된다.

표 4
선행 조건일 경우 결과 자신감. 지원 x 신뢰성
우유를 산다면 빵을 사세요. 2/2= 1.0 0.4X1.0 = 0.4
우유를 산다면, 달걀을 사세요. 1/2= 0.5 0.2X0.5= 0.1
빵을 산다면 과일을 사세요. 2/3= 0.66 0.4X0.66= 0.264
과일을 산다면, 달걀을 사세요. 2/3= 0.66 0.4X0.66= 0.264
만약 우유와 빵을 산다면, 과일을 사세요. 2/2= 1.0 0.4X1.0 = 0.4

전반적으로, 연결 규칙 마이닝에 대한 신뢰를 활용하는 것은 데이터 관계를 인식하는 데 매우 좋은 방법입니다.가장 큰 장점은 특정 규칙에서 항목의 공존을 전체 발생과 비교하기 때문에 집합 내에서 서로에 대한 특정 항목 간의 관계를 강조하는 것이다.그러나 신뢰성이 관련 규칙 마이닝의 모든 개념에 최적인 방법은 아닙니다.이 기능을 사용하는 단점은 어소시에이션에 대해 여러 가지 다른 아웃룩을 제공하지 않는다는 것입니다.예를 들어, 지원과는 달리, 자신감은 전체 데이터 세트와 비교하여 특정 항목 간의 관계에 대한 관점을 제공하지 않으므로, 예를 들어 우유와 빵은 자신감을 위해 100% 발생할 수 있지만, 지원 범위는 0.4(40%)에 불과하다.그렇기 때문에 항상 관계를 정의하는 하나의 개념에만 의존하지 말고 Support x Confidence와 같은 다른 관점을 고려하는 것이 중요합니다.

들어 올리다

규칙의 리프트는 다음과 같이 정의됩니다.

또는 X와 Y가 독립적일 경우 예상되는 지지대 대비 관측된 지지대의 비율.

를 들어 규칙{ k e d { b e r { { \ } \ }\ \ { \ \ bread \ }의 리프트는 0.2 × 0{ {

만약 규칙의 리프트가 1이라면, 선행요소와 결과요소의 발생 확률은 서로 독립적이라는 것을 의미한다.두 이벤트가 서로 독립적일 경우 이러한 두 이벤트를 포함하는 규칙을 그릴 수 없습니다.

리프트가 > 1이면 두 발생이 서로 의존하는 정도를 알 수 있으며 향후 데이터 집합의 결과를 예측하는 데 이러한 규칙이 잠재적으로 유용합니다.

리프트가 < 1이면 아이템이 서로 대체됨을 알 수 있습니다.즉, 한 항목의 존재가 다른 항목의 존재에 부정적인 영향을 미치며 그 반대의 경우도 마찬가지이다.

리프트의 가치는 규칙의 지지와 전체 데이터 [13]세트를 모두 고려한다는 것입니다.

유죄판결

규칙의 v ( y ) - p ( ) - n ( X )\\ { conv } ( \ Y ){ - \ } { 1 - right right { conf } ( Y로 정의됩니다.

예를 들어 규칙{ l } { r {\}은 1- - 0.1.{- 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . } { 0 . 1 } { 0 } { 0 } { 0 } { 0 } { 0 } { 0 } { display } { } { 0 } { 0예를 들어 규칙이 잘못된 예측을 하는 빈도) X와 Y가 독립적인 경우 잘못된 예측의 관측 빈도로 나눈 값입니다.이 예에서 확신값 1.2는 규칙{ l r { t r { \ { \ { , } \ } \ \ { \ { \ {} \ } would would would would%%%%%%%% in%%%%%%%% 、 X의 20% 더 자주 부정확함을 나타냅니다.

관심의 대안적 척도

자신감과 더불어 규칙에 대한 다른 흥미로운 척도가 제안되었다.일반적인 방법은 다음과 같습니다.

탄 외 [20]연구진 및 [21]하슬러에 의해 몇 가지 추가 측정이 제시되고 비교된다.사용자가 알고 있는 것을 모델링할 수 있는 기술을 찾는 것(그리고 이러한 모델을 흥미도 척도로 사용하는 것)은 현재 "주관적 흥미도"라는 이름으로 활발한 연구 트렌드이다.

역사

결사규칙의 개념은 특히 Google Scholar에 따르면 2021년 4월 현재 23,790개 이상의 인용을 획득한 1993년 아그라왈 등의 기사로 인해 대중화되었으며, 따라서 데이터 마이닝 분야에서 가장 많이 인용된 논문 중 하나이다.[2]그러나[22] 현재 "관련 규칙"이라고 불리는 것은 1966년 페트르 [23]하젝 외 연구진이 개발한 일반적인 데이터 마이닝 방법인 GUHA에 관한 논문에서 이미 소개되었다.

모든 어소시에이션 규칙을 검색하기 위해 최소한의 지원 및 신뢰도를 사용한 초기(1989년경)는 기능 기반 모델링 프레임워크입니다.이 에서는 사용자 [24]정의 제약조건보다 p( \{supply})} n (Y)\ \ ( Y 모든 규칙이 더 큰 것으로 나타났습니다

통계적으로 건전한 관련성

연관성을 발견하는 표준 접근법의 한 가지 제한은 연관성이 있는 것으로 보이는 항목의 컬렉션을 찾기 위해 가능한 많은 연관성을 검색함으로써 많은 가짜 연관성을 발견할 위험이 크다는 것이다.이러한 항목은 데이터에서 예기치 않은 빈도로 동시에 발생하지만 우연히 발생하게 되는 항목의 집합입니다.예를 들어, 10,000개 항목의 컬렉션을 검토하고 왼쪽에 2개 항목과 오른쪽에 1개 항목이 포함된 규칙을 찾고 있다고 가정합니다.그러한 규칙은 약 100억 개가 있다.유의 수준 0.05의 독립성 통계 검정을 적용하면 연관성이 없는 경우 규칙을 받아들일 확률이 5%에 불과하다는 것을 의미합니다.연관성이 없다고 가정해도 5000,000,000개의 규칙을 찾을 수 있을 것으로 예상됩니다.통계적으로 건전한 어소시에이션[25][26] 검출에 의해 이 리스크가 제어되므로 대부분의 경우 사용자가 지정한 중요도 수준으로 스플리어스 어소시에이션을 검출할 위험이 줄어듭니다.

알고리즘

관련 규칙을 생성하기 위한 많은 알고리즘이 제안되어 왔다.

Apriori, Eclat, FP-Growth 등 잘 알려진 알고리즘이 있지만 자주 사용하는 아이템셋을 채굴하는 알고리즘이기 때문에 이 알고리즘은 작업의 절반에 불과합니다.데이터베이스 내의 빈번한 항목 집합에서 규칙을 생성하려면 다음 단계를 수행해야 합니다.

아프리오리 알고리즘

Apriori는 R에 의해 주어집니다.아그라왈과 R.1994년 Srikant는 아이템 세트 마이닝 및 어소시에이션 규칙 학습을 빈번히 실시하고 있습니다.이 작업은 데이터베이스에서 자주 사용되는 개별 항목을 식별하고 항목 집합이 충분히 자주 나타나는 한 점점 더 큰 항목 집합으로 확장합니다.알고리즘의 이름은 Apriori입니다.이는 빈번한 항목 집합 속성에 대한 사전 지식을 사용하기 때문입니다.

Apriori 알고리즘의 제어 흐름도

개요:Apriori는 "상향식" 접근방식을 사용합니다.이 접근방식은 빈번한 서브셋을 한 번에 한 항목씩 확장하고(후보 생성으로 알려진 단계), 후보 그룹을 데이터에 대해 테스트합니다.이 알고리즘은 정상적인 확장이 더 이상 발견되지 않으면 종료됩니다.Apriori는 너비 우선 검색과 해시 트리 구조를 사용하여 후보 항목 세트를 효율적으로 계산합니다.length 항목 집합에서 길이의 후보 항목 집합을 생성합니다.그런 다음 하위 패턴이 거의 없는 후보를 삭제합니다.하향 폐쇄 보조법에 따르면 후보 집합에는 모든 빈도가 높은 항목 집합이 포함됩니다.그런 다음 트랜잭션 데이터베이스를 검색하여 후보 간의 빈번한 항목 집합을 결정합니다.

예:각 행이 알파벳 문자로 표시된 특정 돌연변이 조합을 가진 암 샘플이라고 가정합니다.예를 들어 행에 {a, c}이(가) 있을 수 있습니다. 즉, 변환 'a' 및 변환 'c'의 영향을 받습니다.

입력 세트
{a, b} {c, d} {a, d} {a, e} {b, d} {a, b, d} {a, c, d} {a, b, c, d}

이제 각 문자의 발생 횟수를 세어 빈도 항목 집합을 생성합니다.이를 지원 값 검색이라고도 합니다.그런 다음 최소 지원 임계값을 선택하여 항목 세트를 제거합니다.이 알고리즘의 패스에서는, 3개를 선택합니다.

지원값
a b c d
6 4 3 6

모든 지원 값이 3 이상이기 때문에 플루닝은 없습니다.자주 사용되는 항목 집합은 {a}, {b}, {c} 및 {d}입니다.그 후 입력 세트의 돌연변이 쌍을 세어 프로세스를 반복합니다.

지원값
{a, b} {a, c} {a, d} {b, c} {b, d} {c, d}
3 2 4 1 3 4

이제 최소 지원 값 4를 설정하여 제거 후 {a, d} 및 {c, d}만 남습니다.이번에는 자주 사용하는 아이템 세트를 사용하여 세쌍둥이를 조합합니다.그런 다음 입력 세트에서 세쌍의 돌연변이의 발생을 세어 이 과정을 반복합니다.

지원값
{a, c, d}
2

아이템이1개밖에 없기 때문에 다음 네쌍둥이 조합은 비어 있기 때문에 알고리즘이 정지됩니다.

장점과 제한:

Apriori는 몇 가지 제한이 있습니다.후보 생성으로 인해 후보 집합이 커질 수 있습니다.예를 들어, 10^4 빈도의 1-항목 집합은 10^7 후보 2-항목 집합을 생성합니다.또한 알고리즘은 데이터베이스를 자주 스캔해야 하며, 특정 n+1 스캔을 수행해야 합니다. 여기서 n은 가장 긴 패턴의 길이입니다.Apriori는 Eclat 알고리즘보다 느립니다.그러나 Apriori는 데이터 집합이 클 때 Eclat에 비해 성능이 우수합니다.이는 Eclat 알고리즘에서 데이터 집합이 너무 크면 tid 목록이 메모리에 비해 너무 크기 때문입니다.FP 성장은 Apriori와 Eclat를 능가합니다.이는 FP 성장 알고리즘이 후보 생성이나 테스트를 하지 않고 콤팩트한 데이터 구조를 사용하며 데이터베이스 [27]스캔을 1개만 하기 때문입니다.

에클라트 알고리즘

Eclat[11](alt. ECLAT, Equivalence Class Transformation의 약자)는 자주 사용되는 항목 집합 격자 그래프를 깊이 우선 검색(DFS) 방식으로 통과하는 역추적 알고리즘입니다.Apriori 알고리즘에서 사용되는 Width-First Search(BFS; 폭 우선 검색) 트래버설은 체크하기 전에 아이템셋의 모든 서브셋을 체크하지만 DFS 트래버설은 더 큰 아이템셋을 체크하고 하위 서브셋의 지원을 체크하는 데 드는 비용을 절감할 수 있습니다.게다가 DFS는 BFS보다 공간의 복잡성이 낮기 때문에, 메모리 사용량은 거의 확실히 적어집니다.

이를 설명하기 위해 자주 사용되는 항목 집합 {a, b, c}이(가) 있다고 가정합니다. DFS는 자주 사용되는 항목 집합 격자의 노드를 다음 순서로 확인할 수 있습니다. {a} → {a, b} → {a, b, c}이(가) 모두 아래쪽 폐쇄 속성에 의한 지원 제약 조건을 충족하는 것으로 알려져 있습니다.BFS는 최종적으로 확인하기 전에 {a, b, c}의 각 서브셋을 조사합니다.항목 집합의 크기가 증가함에 따라 하위 집합의 수는 조합적 폭발을 겪습니다.

이 기능은 순차 실행과 지역성 강화 [28][29]속성으로 병렬 실행 모두에 적합합니다.

FP 성장 알고리즘

FP는 빈번한 [30]패턴을 나타냅니다.

첫 번째 패스에서 알고리즘은 트랜잭션 데이터 집합에서 항목(속성-값 쌍)의 발생을 카운트하고 이러한 카운트를 '헤더 테이블'에 저장합니다.두 번째 경로에서는 트랜잭션을 트리에 삽입하여 FP 트리 구조를 구축합니다.

트리를 빠르게 처리할 수 있도록 각 트랜잭션의 항목을 데이터 집합에서 빈도의 내림차순으로 정렬해야 합니다.각 거래에서 최소 지원 요건을 충족하지 못하는 항목은 폐기됩니다.많은 트랜잭션이 가장 빈번한 항목을 공유하는 경우 FP 트리는 트리 루트에 가까운 높은 압축을 제공합니다.

이 압축 버전의 메인 데이터 세트를 재귀적으로 처리하면 후보 항목을 생성하고 전체 데이터베이스에 대해 테스트하는 대신(apriori 알고리즘과 같이) 자주 항목 세트가 증가합니다.

헤더 테이블의 맨 아래, 즉 지원이 가장 적은 항목에서 해당 항목으로 끝나는 정렬된 모든 트랜잭션을 검색하여 증가하기 시작합니다.을 I)이라고 부릅니다.

I\displaystyle I에 투영된 FP 트리인 새로운 조건부 트리가 생성됩니다.투영된 트리의 모든 노드의 지원은 각 노드가 자식 수를 합산하여 다시 계산됩니다.최소 지원을 충족하지 않는 노드(및 서브트리)는 플루닝됩니다.I 항목이 최소 지원 임계값을 충족하지 못할 경우 재귀 성장은 종료됩니다.루트에서 I I 경로는 빈번한 항목 집합이 됩니다.이 스텝이 완료되면 원래 FP 트리에서 다음으로 지원이 적은 헤더 항목부터 처리가 계속됩니다.

재귀 프로세스가 완료되면 빈도가 높은 항목 세트가 모두 발견되고 연결 규칙 [31]생성이 시작됩니다.

다른이들

ASOC

ASOC 절차는[32] 고속 비트스트링 연산을 사용하여 일반화된 어소시에이션 규칙을 마이닝하는 GUHA 방식입니다.이 메서드에 의해 채굴된 관련 규칙은 apriori에 의해 출력된 규칙보다 더 일반적입니다. 예를 들어, "항목"은 접속과 분리 둘 다와 연결될 수 있으며 규칙의 선행과 결과 사이의 관계는 apriori에서와 같이 최소 지원과 신뢰의 설정에 제한되지 않습니다: 지원되는 정보의 임의 조합.t 측정치를 사용할 수 있습니다.

OPUS 검색

OPUS는 규칙 검출을 위한 효율적인 알고리즘으로 대부분의 대체 수단과 달리 최소한의 지원 [33]등의 모노톤 또는 안티 모노톤 제약이 필요하지 않습니다.처음에는 고정된 결과에[33][34] 대한 규칙을 찾는 데 사용되었지만,[35] 그 결과 어떤 항목이든 규칙을 찾도록 확장되었습니다.OPUS 검색은 인기 있는 Magnum Opus 어소시에이션 디스커버리 시스템의 핵심 기술입니다.

로레

협회 규칙 채굴에 관한 유명한 이야기는 "맥주와 기저귀" 이야기다.슈퍼마켓 쇼핑객들의 행동에 대한 설문 조사에 따르면 기저귀를 사는 고객들(아마도 젊은 남성들)도 맥주를 사는 경향이 있는 것으로 나타났다.이 일화는 일상 데이터에서 예상치 못한 연상규칙이 발견될 수 있음을 보여주는 사례로 인기를 끌었다.그 이야기가 얼마나 [36]사실인지에 대해서는 의견이 분분하다Daniel Powers는 다음과 같이 말합니다.[36]

1992년, Teradata의 소매 컨설팅 그룹의 매니저인 Thomas Blischok과 그의 스탭은 약 25개의 Osco Drug 스토어에서 120만 개의 시장 바구니를 분석했습니다.데이터베이스 쿼리는 친화성을 식별하기 위해 개발되었습니다.분석 결과 오후 5시에서 7시 사이에 소비자들이 맥주와 기저귀를 구입한 것으로 나타났다.Osco 매니저들은 진열대에서 제품을 더 가까이 옮김으로써 맥주와 기저귀의 관계를 이용하지 않았다.

기타 연결 규칙 마이닝 유형

MRIR(Multi-Relation Association Rules): Multi-Relation Association Rules(Multi-Relation Association Rules)는 각 항목이 여러 관계를 가질 수 있는 연결 규칙입니다.이러한 관계는 실체 간의 간접적인 관계를 나타냅니다.첫 번째 항목이 인근 습도 습도 세 가지 관계로 구성된 경우 다음 MRAR을 고려합니다.도시와 가깝고 습한 기후 타입에 20세 미만사람은 건강 상태가 좋다.이러한 관련 규칙은 RDBMS 데이터 또는 시멘틱 웹 [37]데이터에서 추출할 수 있습니다.

콘트라스트 세트 학습은 연상 학습의 한 형태입니다.대조도 집합 학습자는 하위 [38][39]집합 간에 분포가 유의하게 다른 규칙을 사용합니다.

가중 클래스 학습은 데이터 마이닝 결과 소비자의 특정 관심사에 초점을 맞추기 위해 클래스에 가중치를 할당할 수 있는 또 다른 형태의 연합 학습이다.

고차 패턴 검출은 복잡한 실제 데이터에 고유한 상위(다합성) 패턴 또는 이벤트 관련성을 쉽게 캡처할 수 있습니다.[40]

K-최적 패턴 검출은 각 패턴이 데이터에 자주 나타나야 하는 연관 규칙 학습에 대한 표준 접근법에 대한 대안을 제공합니다.

Ascalate Frequent Itemset 마이닝은 일부 행의 일부 항목을 [41]0으로 만들 수 있는 Frequent Itemset 마이닝의 완화된 버전입니다.

Generalized Association Rules 계층 분류법(개념 계층)

정량적 연관성 규칙 범주형 및 정량적 데이터

인터벌 데이터 연결 규칙(: 연령을 5년 증가 범위로 분할)

시퀀셜 패턴마이닝은 시퀀스 데이터베이스 내의 minsup[clarification needed] 시퀀스 중 공통되는 서브시퀀스를 검출합니다.여기서 minsup은 사용자에 의해 설정됩니다.시퀀스는 트랜잭션의 [42]순서 목록입니다.

하위 공간 클러스터링(Subspace Clustering)은 클러스터링 고차원 데이터의 특정 유형으로, 특정 [43]클러스터링 모델의 하향 폐쇄 특성에 기반하기도 합니다.

Warmr은 ACE 데이터 마이닝 스위트의 일부로 출고됩니다.첫 번째 순서 관계 규칙에 [44]대한 관련 규칙 학습을 허용합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Piatetsky-Shapiro, Gregory(1991), Piatetsky-Shapiro, Gregory, Frawley, William J., Ed., AAAI/MIT Press, Cambridge, MA.
  2. ^ a b c d e f Agrawal, R.; Imieliński, T.; Swami, A. (1993). "Mining association rules between sets of items in large databases". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. p. 207. CiteSeerX 10.1.1.40.6984. doi:10.1145/170035.170072. ISBN 978-0897915922. S2CID 490415.
  3. ^ Garcia, Enrique (2007). "Drawbacks and solutions of applying association rule mining in learning management systems" (PDF). Sci2s. Archived (PDF) from the original on 2009-12-23.
  4. ^ "Data Mining Techniques: Top 5 to Consider". Precisely. 2021-11-08. Retrieved 2021-12-10.
  5. ^ a b c "16 Data Mining Techniques: The Complete List - Talend". Talend - A Leader in Data Integration & Data Integrity. Retrieved 2021-12-10.
  6. ^ "What are Association Rules in Data Mining (Association Rule Mining)?". SearchBusinessAnalytics. Retrieved 2021-12-10.
  7. ^ "Drawbacks and solutions of applying association rule mining in learning management systems". ResearchGate. Retrieved 2021-12-10.
  8. ^ Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). "Chapter 6. Association Analysis: Basic Concepts and Algorithms" (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 978-0-321-32136-7.
  9. ^ Jian Pei; Jiawei Han; Lakshmanan, L.V.S. (2001). "Mining frequent itemsets with convertible constraints". Proceedings 17th International Conference on Data Engineering. pp. 433–442. CiteSeerX 10.1.1.205.2150. doi:10.1109/ICDE.2001.914856. ISBN 978-0-7695-1001-9. S2CID 1080975.
  10. ^ Agrawal, Rakesh, 및 Srikant, Ramakrishnan, 대규모 데이터베이스광산 관련 규칙을 위한 고속 알고리즘 2015-02-25 아카이브 2015-02-25, Jarke, Matthias, Zaniolo, Carlo, 편집자, 제20회 대규모 데이터 컨퍼런스 진행
  11. ^ a b Zaki, M. J. (2000). "Scalable algorithms for association mining". IEEE Transactions on Knowledge and Data Engineering. 12 (3): 372–390. CiteSeerX 10.1.1.79.9448. doi:10.1109/69.846291.
  12. ^ a b Larose, Daniel T.; Larose, Chantal D. (2014-06-23). Discovering Knowledge in Data. doi:10.1002/9781118874059. ISBN 9781118874059.
  13. ^ a b c Hahsler, Michael (2005). "Introduction to arules – A computational environment for mining association rules and frequent item sets" (PDF). Journal of Statistical Software. doi:10.18637/jss.v014.i15.
  14. ^ Wong, Pak (1999). "Visualizing Association Rules for Text Mining" (PDF). BSTU Laboratory of Artificial Neural Networks. Archived (PDF) from the original on 2021-11-29.
  15. ^ Hipp, J.; Güntzer, U.; Nakhaeizadeh, G. (2000). "Algorithms for association rule mining --- a general survey and comparison". ACM SIGKDD Explorations Newsletter. 2: 58–64. CiteSeerX 10.1.1.38.5305. doi:10.1145/360402.360421. S2CID 9248096.
  16. ^ Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; Tsur, Shalom (1997). "Dynamic itemset counting and implication rules for market basket data". Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97. pp. 255–264. CiteSeerX 10.1.1.41.6476. doi:10.1145/253260.253325. ISBN 978-0897919111. S2CID 15385590.
  17. ^ Omiecinski, E.R. (2003). "Alternative interest measures for mining associations in databases". IEEE Transactions on Knowledge and Data Engineering. 15: 57–69. CiteSeerX 10.1.1.329.5344. doi:10.1109/TKDE.2003.1161582.
  18. ^ Aggarwal, Charu C.; Yu, Philip S. (1998). "A new framework for itemset generation". Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '98. pp. 18–24. CiteSeerX 10.1.1.24.714. doi:10.1145/275487.275490. ISBN 978-0897919968. S2CID 11934586.
  19. ^ Piatetsky-Shapiro, Gregory; 강력한 규칙의 발견, 분석 및 제시, 데이터베이스에서의 지식 발견, 1991년, 페이지 229-248
  20. ^ Tan, Pang-Ning; Kumar, Vipin; Srivastava, Jaideep (2004). "Selecting the right objective measure for association analysis". Information Systems. 29 (4): 293–313. CiteSeerX 10.1.1.331.4740. doi:10.1016/S0306-4379(03)00072-3.
  21. ^ 마이클 하슬러(2015).협회 규칙에 대해 일반적으로 사용되는 이자 척도의 확률론적 비교.https://mhahsler.github.io/arules/docs/measures
  22. ^ Hájek, P.; Havel, I.; Chytil, M. (1966). "The GUHA method of automatic hypotheses determination". Computing. 1 (4): 293–308. doi:10.1007/BF02345483. S2CID 10511114.
  23. ^ Hájek, Petr; Rauch, Jan; Coufal, David; Feglar, Tomáš (2004). "The GUHA Method, Data Preprocessing and Mining". Database Support for Data Mining Applications. Lecture Notes in Computer Science. Vol. 2682. pp. 135–153. doi:10.1007/978-3-540-44497-8_7. ISBN 978-3-540-22479-2.
  24. ^ Webb, Geoffrey (1989). "A Machine Learning Approach to Student Modelling". Proceedings of the Third Australian Joint Conference on Artificial Intelligence (AI 89): 195–205.
  25. ^ Webb, Geoffrey I. (2007). "Discovering Significant Patterns". Machine Learning. 68: 1–33. doi:10.1007/s10994-007-5006-x.
  26. ^ Gionis, Aristides; Mannila, Heikki; Mielikäinen, Taneli; Tsaparas, Panayiotis (2007). "Assessing data mining results via swap randomization". ACM Transactions on Knowledge Discovery from Data. 1 (3): 14–es. CiteSeerX 10.1.1.141.2607. doi:10.1145/1297332.1297338. S2CID 52305658.
  27. ^ Heaton, Jeff (2017-01-30). "Comparing Dataset Characteristics that Favor the Apriori, Eclat or FP-Growth Frequent Itemset Mining Algorithms". arXiv:1701.09042 [cs.DB].
  28. ^ Zaki, Mohammed Javeed; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). "New Algorithms for Fast Discovery of Association Rules": 283–286. CiteSeerX 10.1.1.42.3283. hdl:1802/501. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  29. ^ Zaki, Mohammed J.; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). "Parallel Algorithms for Discovery of Association Rules". Data Mining and Knowledge Discovery. 1 (4): 343–373. doi:10.1023/A:1009773317876. S2CID 10038675.
  30. ^ Han (2000). "Mining Frequent Patterns Without Candidate Generation". Proceedings of the 2000 ACM SIGMOD international conference on Management of data - SIGMOD '00. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Vol. SIGMOD '00. pp. 1–12. CiteSeerX 10.1.1.40.4436. doi:10.1145/342009.335372. ISBN 978-1581132175. S2CID 6059661.
  31. ^ Witten, Frank, Hall: 데이터 마이닝 실용적인 기계학습 도구 및 기술, 제3판[page needed]
  32. ^ Hájek, Petr; Havránek, Tomáš (1978). Mechanizing Hypothesis Formation: Mathematical Foundations for a General Theory. Springer-Verlag. ISBN 978-3-540-08738-0.
  33. ^ a b Webb, Geoffrey I.(1995년); OPUS: 무질서 검색을 위한 효율적인 허용 알고리즘, 인공지능 연구 저널 3, Menlo Park, CA: AAAI Press, 페이지 431-465 온라인 액세스
  34. ^ Bayardo, Roberto J., Jr.; Agrawal, Rakesh; Gunopulos, Dimitrios (2000). "Constraint-based rule mining in large, dense databases". Data Mining and Knowledge Discovery. 4 (2): 217–240. doi:10.1023/A:1009895914772. S2CID 5120441.
  35. ^ Webb, Geoffrey I. (2000). "Efficient search for association rules". Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '00. pp. 99–107. CiteSeerX 10.1.1.33.1309. doi:10.1145/347090.347112. ISBN 978-1581132335. S2CID 5444097.
  36. ^ a b "DSS News: Vol. 3, No. 23".
  37. ^ Ramezani, Reza, Mohamad Sunni ee 및 Mohamad Ali Nematbakhsh; MAR: Mining Multi-Relation Association Rules, Journal of Computing and Security, 2014년 2호)
  38. ^ GI Webb and S. Butler and D. Newlands (2003). On Detecting Differences Between Groups. KDD'03 Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  39. ^ Menzies, T.; Ying Hu (2003). "Computing practices - Data mining for very busy people". Computer. 36 (11): 22–29. doi:10.1109/MC.2003.1244531.
  40. ^ Wong, A.K.C.; Yang Wang (1997). "High-order pattern discovery from discrete-valued data". IEEE Transactions on Knowledge and Data Engineering. 9 (6): 877–893. CiteSeerX 10.1.1.189.1704. doi:10.1109/69.649314.
  41. ^ Liu, Jinze; Paulsen, Susan; Sun, Xing; Wang, Wei; Nobel, Andrew; Prins, Jan (2006). "Mining Approximate Frequent Itemsets in the Presence of Noise: Algorithm and Analysis". Proceedings of the 2006 SIAM International Conference on Data Mining. pp. 407–418. CiteSeerX 10.1.1.215.3599. doi:10.1137/1.9781611972764.36. ISBN 978-0-89871-611-5.
  42. ^ Zaki, Mohammed J. (2001); SPADE: 빈번한 시퀀스를 채굴하는 효율적인 알고리즘, 머신 러닝 저널, 42, 페이지 31-60
  43. ^ Zimek, Arthur; Assent, Ira; Vreeken, Jilles (2014). Frequent Pattern Mining. pp. 403–423. doi:10.1007/978-3-319-07821-2_16. ISBN 978-3-319-07820-5.
  44. ^ King, R. D.; Srinivasan, A.; Dehaspe, L. (Feb 2001). "Warmr: a data mining tool for chemical data". J Comput Aided Mol Des. 15 (2): 173–81. Bibcode:2001JCAMD..15..173K. doi:10.1023/A:1008171016861. PMID 11272703. S2CID 3055046.

참고 문헌