1. 연관분석 알고리즘과 그 개선

지지도: 전체 사례 대비 해당 항목이 등장하는 사례의 비율
보통 분모는 고정되기 때문에 분자만 비교하는 경우가 많다.

{A}의 support, {A, B}의 support로 표기한다.

Apriori 알고리즘

개념

1. 사전에 지정한 최소 지지도보다 높은 지지도를 갖는 모든 조합을 알아내기 위한 방법
2. 확장과 가지치기를 반복하면서 완전 탐색(Brute Force)보다 효율적으로 조합을 탐색한다.

(확장) 크기 1의 후보군들을 모아 크기 2의 후보군들로, 크기 2의 후보군들을 모아 크기 3의 후보군들로 ...
(가지치기) 최소 지지도를 넘지 못할 것이 분명한 조합들을 후보군에서 제외

장단점

장점: 조합의 크기가 커질수록 후보군이 급격히 줄어드므로 Brute Force보다 효율적일 수 있다.
단점: 조합의 크기가 하나씩 커질 때마다, 데이터베이스를 매번 참조해야 한다는 한계를 지닌다.

2. FP-Growth 알고리즘

1. 빈도에 따른 정렬
2. FP-Tree의 구성

2. 의사결정나무의 생성 원리

불순도를 나타내는 두 지표

1. Gini Index
   1) 1 - (각 항목이 차지하는 비율의 제곱 합)
   2) 항복이 두 가지일 경우, 값의 범위는 0 ~ 0.5

2. Entropy
   1)
   2) 항목이 두 가지일 경우, 값의 범위는 0 ~ 1

3. K-NN에 대한 기하학적 접근

k-Nearest Neighbor

자신과 가장 가까운 k개의 이웃으로부터 분류를 수행하는 것

Voronoi Diagram

1) 최근접 이웃이 동일하게 결정되는 점들을 하나의 영역으로 묶어 구획화한 것
2) K = 1일 때의 k-최근접 이웃 알고리즘을 기하학적 형태로 표현한 것

Delaunay triangulation

1) 브로노이 다이어그램에서 인접한 영역에 해당하는 데이터끼리 이으면 점들에 대한 삼각 분할이 완성되는 것

성질

1. 모든 삼각형의 외접원은 내부에 다른 데이터를 포함하지 않음
2. 가능한 모든 삼각 분할의 형태 가운데, 전체 내각의 최솟값이 최대
   = 둔각 삼각형이 없다. 정삼각형에 가깝도록 모양이 만들어진다.