[Mining Frequent Patterns, Associations, and Correlations] 2.

1.Constructing a FP-tree

• FP-tree(빈발 패턴 트리) 구축 절차는 다음과 같습니다:
• 데이터베이스(DB) 스캔: 첫 번째로 데이터베이스를 스캔하여 빈발 1-아이템셋을 찾습니다.
• 이 과정에서 각 아이템의 빈도수를 계산합니다.
• 빈발 아이템 정렬: 찾아낸 빈발 아이템들을 그들의 빈도수에 따라 내림차순으로 정렬합니다.
• 이렇게 하면 가장 빈번하게 발생하는 아이템이 리스트의 맨 앞에 오게 됩니다.
• FP-tree 구축: 데이터베이스를 다시 한 번 스캔하면서, 정렬된 빈발 아이템 순서에 따라 FP-tree를 구축합니다.
• 각 트랜잭션은 정렬된 순서대로 트리에 추가되며, 이미 트리에 존재하는 경로는 공유하고, 새로운 아이템이 나타나면 새로운 노드를 추가하여 트리를 확장합니다.
• 예를 들어, 최소 지지도(min_sup)가 3인 경우, 먼저 DB를 스캔하여 최소 지지도 이상의 빈도수를 가진 아이템들만을 선별하여 빈발 1-아이템셋을 구성합니다.
• 이 아이템들을 빈도수가 높은 순서대로 정렬한 후, DB를 다시 스캔하면서 이 순서대로 트랜잭션을 트리에 추가해 나가면서 FP-tree를 완성합니다.
• 이 방법을 통해, 효율적으로 빈발 패턴을 찾아낼 수 있으며, Apriori 방법에서 발생하는 불필요한 후보 생성 작업을 크게 줄일 수 있습니다.

2.Finding Patterns using the FP-tree

• FP-tree를 사용하여 빈번한 패턴을 찾는 과정은 다음과 같습니다.
• 1. 조건부 패턴 베이스 찾기 FP-tree에서 각 빈번한 항목 p에 대한 헤더 테이블의 링크를 따라 FP-tree를 탐색하여 조건부 패턴 베이스를 찾습니다.
• 조건부 패턴 베이스는 특정 항목 p를 포함하는 모든 패턴(경로)의 집합입니다.
• 2. 조건부 FP-tree 구축 각 패턴 베이스에 대해, 패턴 베이스 내의 각 항목의 수를 누적합니다.
• 패턴 베이스의 빈번한 항목들만을 포함하는 FP-tree를 구축합니다.
• 이때, 최소 지지도(min_sup = 3) 이상의 항목들만을 포함시킵니다.
• 3. 빈번한 패턴 생성 구축된 조건부 FP-tree를 사용하여, 최소 지지도 이상의 빈번한 패턴들을 생성합니다.
• 이 과정에서, FP-tree의 구조를 활용하여 효율적으로 패턴을 확장하며 빈번한 패턴을 찾아냅니다.
• 이러한 과정을 통해, FP-tree는 빈번한 패턴들을 효율적으로 찾아내는 데 사용됩니다.
• Apriori 알고리즘과 비교하여, FP-tree는 후보 생성 과정을 거치지 않고도 빈번한 패턴들을 효율적으로 찾을 수 있으며, 대용량 데이터셋에서도 뛰어난 성능을 보입니다.

3.Benefits of FP-tree Structure

• FP-tree 구조의 장점은 다음과 같습니다:
• 완전성 (Completeness): FP-tree는 빈번한 패턴 마이닝을 위한 완전한 정보를 보존합니다.
• 이는 모든 트랜잭션에서 긴 패턴을 결코 분해하지 않는다는 것을 의미합니다.
• 따라서, FP-tree를 사용하면 데이터베이스의 모든 빈번한 패턴을 찾아낼 수 있는 완전한 정보를 유지할 수 있습니다.
• 간결성 (Compactness): FP-tree는 빈번하지 않은 항목들을 제거함으로써 관련 없는 정보를 줄입니다.
• 이는 트리 구조가 더 간결해지고, 데이터 처리가 더 효율적이 됩니다.
• 항목들은 그 빈도의 내림차순으로 정렬되며, 더 자주 발생하는 항목일수록 더 많이 공유될 가능성이 높습니다. 이는 트리의 공유 구조를 통해 더욱 효율적으로 데이터를 압축하고, 더 빠른 패턴 탐색을 가능하게 합니다. FP-tree는 원본 데이터베이스보다 절대로 크지 않습니다(노드 링크와 카운트 필드를 제외하고). 이는 FP-tree가 데이터베이스의 효율적인 요약을 제공하며, 데이터베이스의 크기에 비해 상대적으로 작은 공간만을 차지한다는 것을 의미합니다. FP-tree 구조는 이와 같은 장점으로 인해 빈번한 패턴 마이닝에서 널리 사용되며, 특히 대규모 데이터셋을 다룰 때 높은 효율성과 효과성을 보입니다.

4.Practice: FPGrowth Algorithm

• FPGrowth 알고리즘을 사용하여 빈번한 패턴을 찾는 연습을 해보겠습니다. 최소 지지도(min_sup)는 2로 설정합니다. 헤더 테이블 구축하기 데이터베이스(DB)를 스캔하여 각 아이템의 빈도수를 계산합니다.
• 최소 지지도(min_sup = 2) 이상의 빈도를 가진 아이템만을 선택하여 헤더 테이블을 구축합니다.
• 헤더 테이블에 있는 아이템들을 빈도수가 높은 순으로 정렬합니다.
• FP-tree 구축하기 데이터베이스를 다시 스캔하여 각 트랜잭션을 처리합니다.
• 트랜잭션 내의 아이템을 헤더 테이블에 따라 정렬합니다.
• 정렬된 아이템들로 FP-tree를 구축합니다.
• 이미 존재하는 경로는 공유하고, 새로운 아이템이 나타나면 새로운 노드를 추가하여 트리를 확장합니다.
• 조건부 패턴 베이스 찾기 각 빈번한 아이템에 대해, 헤더 테이블에서 해당 아이템의 링크를 따라가며 FP-tree를 탐색합니다.
• 이 과정에서 아이템의 조건부 패턴 베이스를 찾습니다. 조건부 패턴 베이스란 해당 아이템을 포함하는 모든 패턴(경로)의 집합입니다.
• 각 아이템의 조건부 패턴 베이스를 사용하여, 해당 아이템을 포함하는 조건부 FP-tree를 구축합니다.
• 이때, 최소 지지도 이상의 아이템만을 포함시킵니다.
• 이러한 단계를 거쳐 FP-tree 구조를 활용하여 데이터베이스에서 빈번한 패턴을 효율적으로 찾을 수 있습니다.
• FPGrowth 알고리즘은 후보 생성 과정 없이 빈번한 패턴을 찾을 수 있어 대규모 데이터셋을 다룰 때 매우 유용합니다.

5.Measuring Interestingness

• 관심도 측정(Interestingness Measure)은 연관 규칙의 흥미로움이나 유용성을 평가하는 데 사용됩니다.
• 여기서는 두 가지 직관적인 예를 들어 설명하겠습니다.
• 규칙: 게임 구매 -> 비디오 구매 이 규칙은 강한 연관 규칙으로 보입니다.
• 비디오 구매 확률이 75%인 것과 비교할 때, 이 규칙의 신뢰도는 66%로 높지 않습니다.
• 규칙: 게임 구매 -> 비디오 구매하지 않음 이 규칙은 약한 연관 규칙으로 보입니다.
• 비디오를 구매하지 않을 확률이 25%인 것과 비교할 때, 이 규칙의 신뢰도는 33%로 높습니다.
• 두 사건은 긍정적으로 상관관계를 가집니다.
• 부정적으로 상관관계를 가진다고 설명하기: 부정적 상관관계는 한 사건의 발생이 다른 사건의 발생 가능성을 낮추는 경우를 의미합니다.
• 예를 들어, "게임 구매 -> 비디오 구매하지 않음" 규칙에서, 게임을 구매하는 사람들 중 비디오를 구매하지 않는 경우의 신뢰도가 전체 비디오를 구매하지 않는 사람들의 비율보다 높다는 점에서, 게임 구매와 비디오 구매는 부정적으로 상관관계가 있다고 볼 수 있습니다.
• 즉, 게임을 구매하는 행위가 비디오 구매를 감소시키는 경향이 있음을 나타냅니다. 

6.Example of Interestingness Measure

• 관심도 측정의 예시로, X를 구매한 사람들 중 Y도 구매했을 확률의 순위를 매기는 상황을 들 수 있습니다. 예를 들어, John이 "맥주"를 구매했다고 가정해봅시다.
• 규칙: {맥주} -> {Y} 이 경우, "우유"와 "기저귀" 중 어느 것이 더 높은 신뢰도를 가지는지 비교해야 합니다.
• 답은 "우유"입니다.
• 그러나 이 결과는 "우유"의 인기도를 보상하지 않습니다.
• 이는 "우유"가 "기저귀"보다 더 높은 신뢰도를 가질 수 있지만, 이는 단순히 "우유"가 더 인기 있는 상품이기 때문일 수 있습니다.
• 관심도 측정은 이러한 인기도 차이를 고려하여, 상품 간의 실제 연관성이나 구매 경향을 더 정확하게 파악할 수 있게 해줍니다.

7.Discussion on Interestingness Measure

• 관심도 측정에 대한 토론: 단순히 지지도(support)와 신뢰도(confidence) 프레임워크만을 사용하여 연관 규칙을 평가하는 것은 충분하지 않습니다.
• 지지도-신뢰도 프레임워크는 상관 관계를 효과적으로 포착하지 못합니다.
• 상관 관계를 밝히기 위해서는 다른 측정 방법이 필요합니다.
• '향상도(lift)'와 '카이제곱(X^2)' 같은 측정 방법이 의미 있는 상관 관계를 찾는 데 유용할 수 있습니다.
• 이러한 지적은 연관 규칙 분석에서 단순한 빈도수에 기반한 지지도와 신뢰도만을 고려하는 것이 아니라, 실제 상품 간의 상관 관계와 이러한 상관 관계가 얼마나 의미 있는지를 평가하기 위해 보다 복잡한 통계적 방법을 사용할 필요성을 강조.
• 향상도는 특정 조건 하에서 결과가 얼마나 더 자주 발생하는지를 나타내며, 카이제곱 검정은 두 변수 간의 독립성을 검정하여 상관 관계의 유의성을 평가.
• 이러한 측정 방법들은 연관 규칙이 우연에 의한 것인지, 아니면 실제로 의미 있는 상관 관계를 반영하는 것인지를 판단하는 데 도움.

8.New Interestingness Measure

• 새로운 흥미도 측정 방식을 소개합니다: 상호 의존성 또는 상관관계의 측정에 '리프트(lift)'를 사용합니다.
  • 리프트 값이 1.0보다 작으면, 해당 이벤트들은 부정적으로 상관관계가 있다고 볼 수 있다.
  • 리프트 값이 1.0보다 크면, 해당 이벤트들은 긍정적으로 상관관계가 있다고 볼 수 있다.
• 예를 들어, X 구매자들 중에 Y도 구매했을 확률을 랭킹하는 상황에서, John이 "맥주"를 구매했다고 가정합시다.
• 규칙: {맥주} -> {Y} 이 경우, "우유"와 "기저귀" 중에서 어느 것이 더 높은 상관관계를 가질까요?
• "기저귀"는 "맥주"에 대해 긍정적으로 상관관계가 있다고 할 수 있습니다.
• 이는 "맥주"를 구매하는 사람들이 "기저귀"를 구매할 확률이 높다는 것을 의미하며, 리프트 값이 1.0보다 크다는 것을 통해 이러한 긍정적인 상관관계를 확인할 수 있습니다.
• 반면, "우유"와의 상관관계는 이 정보만으로는 명확하지 않습니다.
• 상관관계를 정확히 판단하기 위해서는 "우유"에 대한 리프트 값을 확인할 필요가 있다.

9.Null-Invariance

• 널-불변성에 대해 설명드리겠습니다.
• 널-트랜잭션: 검토 중인 아이템셋을 포함하지 않는 트랜잭션을 의미합니다.
• 널-트랜잭션의 수와 독립적인 측정 방법이 필요한 이유: 널-트랜잭션의 수가 많을 경우, 이는 분석 결과에 영향을 미칠 수 있기 때문에, 널-트랜잭션의 수에 영향을 받지 않는 측정 방법이 필요합니다.
• 널-불변 측정 방법 네 가지: 이 측정 방법들은 의존성이나 상관 관계를 평가하는 데 사용됩니다.
• 0.5 미만일 경우, 이벤트들은 음의 상관 관계를 가지고 있다고 볼 수 있습니다.
• 0.5 초과일 경우, 이벤트들은 양의 상관 관계를 가지고 있다고 볼 수 있습니다.
• 널-불변 측정 방법 네 가지를 계산하는 것은, 널-트랜잭션이 결과에 미치는 영향을 배제하고, 아이템셋 간의 실제 상관 관계를 보다 정확하게 이해하는 데 도움이 됩니다.
• 하지만, 구체적인 네 가지 측정 방법의 이름이나 계산 방법은 제공되지 않았습니다.
• 일반적으로, 이러한 측정 방법들은 분석의 정확성을 높이기 위해 데이터 마이닝과 같은 분야에서 사용됩니다.

10.Comparison of Interestingness Measures

• 관심도 측정 방법들의 비교에 대한 예시: 이 예시에서는 다양한 측정 방법들이 어떻게 다른지 설명합니다.
• D1과 D2: mc (market basket analysis에서의 m과 c의 관계)에 따라, lift와 카이제곱(X^2)은 크게 다릅니다.
• D3과 D4: lift와 카이제곱(X^2)은 양의 상관관계를 보이는 반면, 다른 측정 방법들은 D3에서는 음의 상관관계를, D4에서는 중립을 보입니다.
• D4, D5, D6: 데이터셋이 편향됩니다.
• 각 데이터셋에 대해, IR(m, c) = 0, IR(m, c) = 0.89, IR(m, c) = 0.99로 나타납니다.
• 이 예시에서는 다양한 데이터셋(D1, D2, D3, D4, D5, D6)을 사용하여 관심도 측정 방법들(예: lift, 카이제곱(X^2), 기타)이 어떻게 다른지를 보여줍니다.
• 특히, mc에 따라 lift와 카이제곱 값이 크게 달라질 수 있으며, 데이터셋에 따라 측정 방법들 간의 상관관계가 양의 상관관계, 음의 상관관계, 또는 중립적일 수 있음을 지적합니다.
• 또한, 데이터셋이 편향될 경우 측정 결과에 영향을 미칠 수 있음을 시사합니다.
• IR(m, c) 값은 특정 관심도 측정 방법의 결과를 나타내며, 이 값이 0에서 0.99로 변화하는 것은 측정 방법이 데이터셋의 특성을 얼마나 잘 반영하는지를 보여줍니다

11.Example of Imbalanced Measures

• 불균형 데이터셋에 대한 네 가지 측정 방법을 계산하는 예시입니다. 불균형 데이터셋이란, 데이터 내의 한 클래스가 다른 클래스보다 훨씬 많이 존재하는 경우를 말합니다.
• 이런 데이터셋에서는 일반적인 측정 방법을 사용할 때 오류가 발생하기 쉽습니다.
• 따라서, 불균형 데이터셋을 평가할 때는 특별히 설계된 측정 방법을 사용해야 합니다.
• 여기 네 가지 측정 방법의 예시를 들어보겠습니다:
• 정확도(Accuracy): 이는 가장 단순하고 직관적인 측정 방법입니다. 전체 데이터 중에서 올바르게 분류된 데이터의 비율을 나타냅니다.
• 하지만, 불균형 데이터셋에서는 소수 클래스의 오류를 잘 반영하지 못할 수 있습니다.
• 정밀도(Precision)와 재현율(Recall): 정밀도는 예측된 양성 중 실제 양성의 비율을, 재현율은 실제 양성 중 양성으로 예측된 비율을 나타냅니다. 불균형 데이터셋에서는 이 두 측정 방법을 함께 사용하여 모델의 성능을 평가하는 것이 좋습니다.
• F1 점수(F1 Score): 정밀도와 재현율의 조화 평균을 나타냅니다.
• 이는 불균형 데이터셋에서 정밀도와 재현율 사이의 균형을 평가하는 데 유용한 측정 방법입니다.
• ROC 곡선 아래 면적(AUC-ROC): 이는 모델이 양성 클래스와 음성 클래스를 구분하는 능력을 평가하는 데 사용됩니다. AUC 값이 1에 가까울수록 모델의 성능이 좋다고 할 수 있습니다. 불균형 데이터셋에서 AUC-ROC는 모델이 얼마나 잘 예측하는지에 대한 전반적인 아이디어를 제공합니다. 불균형 데이터셋을 평가할 때는 이러한 측정 방법들을 적절히 조합하여 사용함으로써, 모델의 성능을 더 정확하게 평가할 수 있습니다.