[Mining Frequent Patterns, Associations, and Correlations]

1.What is Frequent Pattern Analysis?

• 자주 발생 패턴 분석(Frequent Pattern Analysis)은 데이터 세트에서 자주 발생하는 패턴(아이템 집합, 부분 순서, 부분 구조 등)을 찾는 과정입니다. 이는 Agrawal, Imielinski, Swami에 의해 자주 발생하는 아이템셋과 연관 규칙 마이닝(context of frequent itemsets and association rule mining)의 맥락에서 제안되었습니다. 이 분석 방법은 데이터 마이닝의 중요한 부분으로, 대용량 데이터에서 의미 있는 정보를 추출하는 데 사용됩니다. 예를 들어, 소매업에서는 고객이 자주 함께 구매하는 상품 집합을 파악하여 판매 전략을 개선하거나, 의학 분야에서는 특정 질병의 발병과 관련된 유전자 패턴을 찾는 데 사용될 수 있습니다. 자주 발생 패턴 분석은 다양한 데이터 타입에 적용될 수 있으며, 이를 통해 얻은 지식은 추천 시스템, 이상 탐지, 분류 등 다양한 분야에서 활용될 수 있습니다.빈번 패턴 분석(Frequent Pattern Analysis)은 데이터 내에 존재하는 내재적인 규칙성을 찾아내는 과정입니다. 이 분석의 동기는 다음과 같은 질문에서 비롯됩니다: 어떤 제품들이 자주 함께 구매되었는가? 예를 들어, 맥주와 기저귀가 함께 구매되는 경우, PC 구매 후 어떤 제품들이 이어서 구매되는가? 새로운 약에 대해 민감한 DNA의 종류는 무엇인가? 이러한 분석은 다양한 응용 분야에서 활용될 수 있습니다. 예를 들어, 장바구니 데이터 분석, 교차 마케팅, 카탈로그 디자인, 판매 캠페인 분석, 웹 로그(클릭 스트림) 분석, DNA 시퀀스 분석 등에서 유용하게 사용됩니다. 이런 분석을 통해, 기업들은 고객의 구매 패턴을 이해하고 마케팅 전략을 개선하거나, 과학자들은 특정 약물에 대한 유전적 반응 패턴을 발견할 수 있습니다. 빈번 패턴 분석은 대규모 데이터셋에서 유의미한 정보를 추출해내는 데 있어 중요한 도구로 작용합니다.

2.The Market-Basket Model

• 시장 바구니 모델(Market-Basket Model)은 대량의 아이템(예: 슈퍼마켓에서 판매되는 물품들)과 이러한 아이템들의 작은 부분집합으로 구성된 대량의 바구니(고객이 하루에 구매하는 물품들)로 이루어져 있습니다. 이 모델의 목적은 연관 규칙(If-Then 규칙)을 발견하는 것입니다. 예를 들어, "Amazon에서 {x, y, z}를 구매한 사람들은 {v, w}를 구매하는 경향이 있다!"와 같은 규칙을 찾아내는 것이죠. 이러한 연관 규칙은 고객의 구매 패턴을 이해하고, 특정 제품의 교차 판매 가능성을 높이며, 마케팅 전략을 개선하는데 유용하게 사용됩니다. 예를 들어, 특정 제품들이 함께 자주 구매된다는 사실을 알게 되면, 그 제품들을 서로 가까운 곳에 배치하여 판매를 촉진시키거나, 함께 구매를 유도하는 프로모션을 기획할 수 있습니다. 이 모델은 또한 웹 로그 분석, 카탈로그 디자인, 판매 캠페인 분석 등 다양한 분야에 활용될 수 있습니다.

3.Example of Applications

• Frequent Pattern Analysis의 응용 예시는 다음과 같습니다: 제품을 아이템으로, 구매 제품 세트를 바스켓으로 하는 경우: 대형 체인점들은 고객들이 함께 구매하는 제품에 대한 TB 단위의 데이터를 보유하고 있습니다. 이를 통해 고객들이 매장을 어떻게 탐색하는지 파악하고, 유혹적인 아이템을 적절한 위치에 배치할 수 있습니다. 아마존의 "이 제품을 구매한 사람들은 다음 제품도 구매했습니다" 같은 추천 시스템. 문장을 아이템으로, 문장 세트를 바스켓으로 하는 경우: 자주 함께 나타나는 문장들은 표절을 나타낼 수 있습니다. 이때, 아이템이 반드시 바스켓 안에 있어야 하는 것은 아닙니다. 약물을 아이템으로, 환자들을 바스켓으로 하는 경우: 특정 부작용을 일으키는 약물 조합을 탐지하는 데 사용됩니다. 이 경우, 아이템의 부재도 관측되어야 하므로 분석 방법이 확장되어야 합니다. 그래프 내의 커뮤니티 찾기 (예: 트위터): 아이템을 나가는 노드로, 바스켓을 노드 세트로 봅니다. 큰 그래프의 완전 이분 부그래프를 찾는 것과 같습니다. 각 노드 i를 노드 i가 가리키는 노드들의 바스켓 Bi로 봅니다. 이러한 예시들을 통해, Frequent Pattern Analysis가 다양한 분야에서 어떻게 응용될 수 있는지 알 수 있습니다. 이는 데이터 내에서 중요한 패턴이나 규칙을 찾아내어 유용한 인사이트를 제공하는 데 큰 역할을 합니다.

4.Apriori Algorithm

• Apriori 알고리즘과 빈번한 패턴의 기초에 대해 설명하겠습니다. 아이템셋(Itemset): 하나 이상의 아이템으로 구성된 집합입니다. 예를 들어, k개의 아이템으로 구성된 아이템셋 X는 {X1, ..., Xk}와 같이 표현할 수 있습니다. 지지도(Support) 또는 지지도 수(Support Count): 아이템셋 X가 발생하는 빈도를 의미합니다. 절대 지지도는 아이템셋 X의 발생 횟수를, 상대 지지도는 트랜잭션 중 X를 포함하는 비율을 의미합니다. 즉, 트랜잭션이 X를 포함할 확률입니다. 빈번한 아이템셋(Frequent Itemset): 아이템셋 X의 지지도가 최소 지지도(min_sup) 임계값 이상일 경우, X를 빈번한 아이템셋이라고 합니다. 최소 지지도(min_sup): 아이템셋이 빈번하다고 간주되기 위한 최소 지지도 임계값입니다. Apriori 알고리즘은 이러한 개념을 바탕으로 데이터 내에서 빈번하게 발생하는 아이템셋을 찾는 과정입니다. 이를 위해 알고리즘은 먼저 모든 단일 아이템에 대한 지지도를 계산하고, 최소 지지도 이상의 아이템만을 선택합니다. 그 다음, 선택된 아이템들을 조합하여 더 큰 아이템셋을 생성하고, 이 아이템셋의 지지도를 계산하여 빈번한 아이템셋을 찾아냅니다. 이 과정은 더 이상 새로운 빈번한 아이템셋을 찾을 수 없을 때까지 반복됩니다. Apriori 알고리즘은 데이터 마이닝에서 빈번한 아이템셋을 찾고, 이를 바탕으로 연관 규칙을 생성하는 데 널리 사용됩니다.

5.Basics of Frequent Patterns

• 빈번한 패턴의 기본 원리는 최소 지지도(minimum support)와 신뢰도(minimum confidence)를 만족하는 모든 규칙 A -> B를 찾는 것입니다. 여기서, 지지도(support, s)는 A와 B를 모두 포함하는 거래의 확률입니다. 즉, A ∪ B가 발생하는 거래의 집합입니다. A -> B의 지지도는 P(A ∪ B)로 계산됩니다. 신뢰도(confidence, c)는 A를 포함하는 거래가 B도 포함할 조건부 확률입니다. A -> B의 신뢰도는 P(B|A) = support_count(A ∪ B) / support_count(A)로 계산됩니다. 가능한 연관 규칙의 예로는 다음과 같습니다. 맥주 -> 기저귀 (60%, 100%) 기저귀 -> 맥주 (60%, 75%) 데이터베이스에 100개의 아이템이 있다고 가정할 때, 가능한 아이템셋의 수는 다음과 같습니다. 1-아이템셋 2-아이템셋 ... n-아이템셋 {a1, …, a100}은 (1에서 100까지 선택) + (2에서 100까지 선택) + (3에서 100까지 선택) + ... + (100에서 100까지 선택) = 2^100 – 1 = 1.27 * 10^30개의 아이템셋을 포함합니다. 이는 계산하기에는 너무나도 막대한 아이템셋의 수를 의미합니다.

6.Frequent Itemset

• 빈번한 아이템셋(Frequent Itemset)은 그 지지도(support)가 최소 지지도 임계값 이상인 아이템의 집합을 말합니다. 크기가 1인 모든 빈번한 아이템셋을 식별하고 표현하는 방법: 최소 지지도 임계값이 2라고 가정할 때, 지지도가 최소 지지도 임계값 이상인 아이템셋은 다음과 같습니다: {B} = 3, {C} = 2, {D} = 4, {N} = 3, {E} = 3, {M} = 2 이들은 모두 최소 지지도 임계값인 2 이상의 지지도를 가지므로 빈번한 아이템셋입니다. 크기가 2인 모든 빈번한 아이템셋을 식별하고 표현하는 방법: 최소 지지도 임계값이 2라고 가정할 때, 지지도가 2 이상인 2-아이템셋은 다음과 같습니다: {B, D} = 3, {C, D} = 2, {D, E} = 2, {N, D} = 2, {N, E} = 2, {N, M} = 2, {E, M} = 2 이들은 모두 최소 지지도 임계값인 2 이상의 지지도를 가지므로 빈번한 아이템셋입니다. 크기가 3인 모든 빈번한 아이템셋을 식별하고 표현하는 방법: 최소 지지도 임계값이 2라고 가정할 때, 지지도가 2인 3-아이템셋은 다음과 같습니다: {N, E, M} = 2 이는 최소 지지도 임계값인 2 이상의 지지도를 가지므로 빈번한 아이템셋입니다. 요약하자면, 최소 지지도 임계값을 기준으로 지지도가 이 임계값 이상인 아이템셋을 빈번한 아이템셋으로 식별하고 표현합니다. 이를 통해 데이터 내에서 중요하고 관련성 높은 아이템의 조합을 찾아낼 수 있습니다.

7.Closed Itemset

• 닫힌 아이템셋(Closed Itemset)과 닫힌 빈발 아이템셋(Closed Frequent Itemset)에 대해 설명하겠습니다. 닫힌 아이템셋이란, 아이템셋 X에 대해 동일한 지지도를 가지는 상위 패턴 Y가 존재하지 않을 때, 그 아이템셋 X를 닫힌 아이템셋이라고 합니다. 즉, X보다 더 큰 아이템셋이 있어도 지지도가 X와 같지 않다면, X는 닫힌 아이템셋입니다. 예를 들어, 최소 지지도가 2일 때, {B}는 닫힌 아이템셋인가요? 아니요, {B}의 상위 집합인 {B, D}가 동일한 지지도를 가집니다. {D}는 닫힌 아이템셋인가요? 네, 닫힌 아이템셋 조건을 만족하는 상위 집합이 존재하지 않습니다. 닫힌 빈발 아이템셋은 아이템셋 X가 빈발하면서(최소 지지도 이상) 동일한 지지도를 가지는 상위 패턴 Y가 존재하지 않을 때, 그 아이템셋 X를 닫힌 빈발 아이템셋이라고 합니다. 닫힌 패턴은 빈발 패턴의 손실 없는 압축을 제공합니다. 예를 들어, 최소 지지도가 2일 때, {B, D}는 닫힌 빈발 아이템셋인가요? 네, {B, D}는 빈발하며 닫힌 아이템셋 조건을 만족하는 상위 집합이 존재하지 않습니다. {D}는 닫힌 빈발 아이템셋인가요? 네, {D}는 빈발하며 닫힌 아이템셋 조건을 만족하는 상위 집합이 없습니다. 따라서 닫힌 빈발 아이템셋은 데이터 내에서 중요하고 의미 있는 패턴을 효율적으로 찾는 데 유용합니다.

8.Max-Itemset

• Max-Itemset은 X가 자주 발생(frequent)하며, X를 포함하는 어떤 빈번한(super-patterns) Y가 존재하지 않을 때, X를 맥스-아이템셋이라고 합니다. 예를 들어, 최소 지지도(min_sup)가 2일 때, {B, D}는 빈번한 슈퍼셋이 없으므로 맥스-아이템셋입니다. 반면, {N, E}는 빈번한 슈퍼셋 {N, E, M}이 존재하기 때문에 맥스-아이템셋이 아닙니다. Closed Itemsets(닫힌 아이템셋)와 Max-Itemsets(맥스-아이템셋)은 데이터 세트에서 중요한 패턴을 찾는데 유용합니다. 예시를 통해 설명해보겠습니다: 데이터베이스(DB)가 {<a1,a2>, <a1,a2,a3,a4,a5>}가 있고, 최소 지지도(Min_sup)가 1일 때, 닫힌 아이템셋의 집합은 C = {{a1,a2}: 2, {a1,a2,a3,a4,a5}: 1}입니다. 여기서 {a1,a2}는 두 번 등장하고, {a1,a2,a3,a4,a5}는 한 번 등장합니다. {a1,a3}의 빈도를 물어보시면, {a1,a3}는 두 번째 트랜잭션에만 등장하기 때문에 빈도는 1입니다. 따라서 최소 지지도가 1이기 때문에 {a1,a3}도 빈번한 아이템셋입니다. 맥스-아이템셋의 집합은 M = {{a1,a2,a3,a4,a5}: 1}입니다. 이는 가장 큰 아이템셋이며, 더 큰 빈번한 슈퍼셋이 존재하지 않습니다. {a1,a3}가 빈번한지에 대한 답변도 동일하게, {a1,a3}의 빈도는 1이고, 최소 지지도가 1이므로 빈번한 아이템셋입니다. 이처럼 맥스-아이템셋과 닫힌 아이템셋을 통해 데이터에서 더 의미있는 정보를 추출할 수 있습니다.

9.Downward Closure Property

• 하향폐쇄성(Downward Closure Property)은 빈번한 아이템셋의 중요한 특성 중 하나입니다. 이 성질에 따르면, 어떤 아이템셋이 빈번하다면, 그 아이템셋의 모든 부분집합도 빈번합니다. 예를 들어, {맥주, 기저귀, 땅콩}이 빈번한 아이템셋이라면, {맥주, 기저귀} 역시 빈번한 아이템셋입니다. 이는 모든 {맥주, 기저귀, 땅콩}을 포함하는 거래가 반드시 {맥주, 기저귀}를 포함하기 때문입니다. 크기가 3인 모든 빈번한 아이템셋을 식별하고 표현하는 방법을 예로 들어보겠습니다. 크기가 2인 빈번한 아이템셋들이 다음과 같이 주어졌다고 가정해 보겠습니다. {B, D} = 3, {C, D} = 2, {D, E} = 2, {N, D} = 2, {N, E} = 2, {N, M} = 2, {E, M} = 2. 이러한 정보를 바탕으로, 가능한 빈번한 3-아이템셋 후보는 {N, D, E}와 {N, E, M}입니다. 이는 주어진 2-아이템셋들의 조합으로 만들 수 있는 유일한 3-아이템셋들이며, 이들이 빈번할 가능성이 있습니다. 하향폐쇄성을 이용하면, 데이터베이스 내에서 빈번한 아이템셋을 효율적으로 찾아낼 수 있습니다. 크기가 작은 아이템셋부터 시작하여 빈번한 아이템셋을 찾아내고, 그 정보를 바탕으로 더 큰 크기의 아이템셋의 빈번 여부를 판단할 수 있기 때문입니다.

10.Apriori: Candidate Generation

• Apriori 알고리즘의 후보 생성과정은 다음과 같은 원칙에 기반합니다: 만약 어떤 아이템셋이 비빈번하다면, 그 아이템셋의 상위셋은 생성되어서는 안 됩니다. 이 원칙을 Apriori 가지치기 원칙이라고 합니다. 전체 절차는 대략 다음과 같습니다: 데이터베이스를 한 번 스캔하여 빈번한 1-아이템셋을 얻습니다. 빈번한 k-아이템셋으로부터 길이가 (k + 1)인 후보 아이템셋을 생성합니다. 생성된 후보들을 데이터베이스에 대해 테스트합니다. 더 이상 빈번한 아이템셋이나 후보셋을 생성할 수 없을 때까지 이 과정을 반복합니다. 이러한 과정을 통해, Apriori 알고리즘은 큰 데이터베이스 내에서 빈번한 아이템셋을 효과적으로 찾아낼 수 있습니다. 가지치기 원칙을 사용함으로써, 검사해야 할 후보의 수를 상당히 줄일 수 있으며, 이는 전체적인 알고리즘의 실행 시간을 줄이는 데 크게 기여합니다.

11.Example of Apriori Algorithm

• Apriori 알고리즘의 예시와 주어진 최소 지지도(supmin)가 2라고 가정해 보겠습니다. Apriori 알고리즘의 의사코드는 다음과 같습니다: Ck: 크기가 k인 후보 아이템셋 Lk: 크기가 k인 빈번한 아이템셋 L1 = {빈번한 아이템}; for (k = 1; Lk != ∅; k++) do begin a. Ck+1 = Lk에서 생성된 후보들; b. 데이터베이스의 각 트랜잭션 t에 대해 i. t에 포함된 Ck+1의 모든 후보의 카운트를 증가시킴 c. Lk+1 = 최소 지지도를 만족하는 Ck+1의 후보들 end return 합집합k Lk; 이 의사코드는 Apriori 알고리즘의 실행 과정을 요약한 것입니다. 초기에 데이터베이스를 스캔하여 빈번한 1-아이템셋 L1을 구합니다. 그 다음으로, 이미 발견된 빈번한 아이템셋을 기반으로 새로운 후보 아이템셋들 Ck+1을 생성합니다. 이 후보들은 데이터베이스의 각 트랜잭션에서 발견될 때마다 카운트가 증가되고, 이 카운트를 바탕으로 최소 지지도 이상의 빈도를 가진 아이템셋만이 다음 라운드의 빈번한 아이템셋 Lk+1로 선정됩니다. 이 과정은 더 이상 새로운 빈번한 아이템셋을 찾을 수 없을 때까지 반복됩니다. 마지막으로, 모든 k에 대한 빈번한 아이템셋의 합집합을 반환합니다. 이 알고리즘을 통해, 데이터베이스 내에서 빈번하게 등장하는 아이템셋들을 효율적으로 찾아낼 수 있습니다.

12. Practice: Apriori Algorithm

• Apriori 알고리즘을 연습해 보겠습니다. 여기서는 최소 지지도(min_sup)가 2라고 가정합니다. 이를 통해 C1, L1, C2, L2, C3, L3을 차례대로 생성해 보겠습니다. C1 생성 및 L1 찾기: C1은 모든 가능한 1-itemsets의 집합입니다. 데이터베이스를 스캔하여 각 항목의 지지도를 계산합니다. 최소 지지도(min_sup) 이상인 항목만을 포함하는 L1을 생성합니다. C2 생성 및 L2 찾기: L1에 있는 항목들로부터 가능한 모든 2-itemsets의 집합 C2를 생성합니다. 이때, Apriori의 속성을 이용하여 L1에 없는 항목을 포함하는 2-itemsets는 생성하지 않습니다. 데이터베이스를 다시 스캔하여 C2의 각 항목셋에 대한 지지도를 계산합니다. 최소 지지도(min_sup) 이상인 항목셋만을 포함하는 L2를 생성합니다. C3 생성 및 L3 찾기: L2에 있는 항목셋들로부터 가능한 모든 3-itemsets의 집합 C3를 생성합니다. 이때도 Apriori의 속성을 이용하여 L2의 모든 부분집합이 L2에 포함되지 않는 3-itemsets는 생성하지 않습니다. 데이터베이스를 다시 스캔하여 C3의 각 항목셋에 대한 지지도를 계산합니다. 최소 지지도(min_sup) 이상인 항목셋만을 포함하는 L3를 생성합니다. 이 과정을 통해 최소 지지도 이상의 항목셋을 찾아내는 것이 Apriori 알고리즘의 목표입니다. 이 연습에서는 L3까지의 생성을 목표로 하고 있지만, 실제 데이터 마이닝 상황에서는 더 큰 크기의 항목셋을 찾기 위해 이 과정을 반복할 수 있습니다.

13.Pattern-Growth Approach

• 패턴 성장 접근 방식은 Apriori 접근 방식의 병목 현상을 해결하기 위해 고안되었습니다. Apriori 접근 방식은 다음과 같은 몇 가지 제한 사항을 가지고 있습니다: 너비 우선 탐색(Breath-first search): 이 방법은 한 단계에서 모든 가능한 후보군을 생성하고 테스트합니다. 이는 종종 방대한 수의 후보군을 생성하게 되는 원인이 됩니다. 후보 생성 및 테스트: Apriori는 빈번한 항목 집합을 찾기 위해 모든 가능한 항목 집합의 후보를 생성하고 이를 데이터베이스와 비교해야 합니다. 이 과정은 계산적으로 비효율적일 수 있습니다. 반면에, FPGrowth(Frequent Pattern Growth) 접근 방식은 다음과 같은 특징을 가지고 있어 Apriori의 단점을 극복합니다: 깊이 우선 탐색(Depth-first search): FPGrowth는 깊이 우선 탐색을 사용하여 항목 집합의 패턴을 확장합니다. 이 접근 방식은 효율적인 패턴 확장을 가능하게 합니다. 명시적인 후보 생성을 피함: FPGrowth 방식은 후보 항목 집합을 명시적으로 생성하지 않고, 대신 FP-Tree라는 구조를 사용하여 빈번한 항목 집합을 효율적으로 저장하고 탐색합니다. 지역 빈번 항목만을 사용하여 짧은 패턴에서 긴 패턴으로 성장: FPGrowth는 지역 빈번 항목을 사용하여 짧은 패턴에서 시작하여 점차 긴 패턴을 성장시키는 방식으로 작동합니다. 이는 불필요한 후보군의 생성을 줄이고, 계산 효율성을 높입니다. 이러한 특징으로 인해 FPGrowth 방식은 대규모 데이터셋에서 빈번한 패턴을 찾는데 있어 Apriori 방식보다 훨씬 더 효율적입니다.