[알고리즘] 기본 개념 정리 (10) - 기계학습에서의 알고리즘과 그 토대

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

지지도

• Support : 전체 사례 대비, 해당 항목이 등장하는 사례의 비율
• Apriori Algorithm에서 수행하는 기능은?
  • 빈번히 발생하는 세트 확인
  • 가지치기
  • 연관된 규칙 생성에 용이

신뢰도

• confidence : A를 포함하는 사례 중, B까지 포함하는 사례의 비율
• 높은 신뢰도를 보이는 연관규칙은 반드시 유의미할까?

향상도

• lift : 연관규칙 A⇒B에 대한 신뢰도를 B의 지지도로 나눈 값
• 정방향, 역방향 모두 같은 향상도를 가짐

Apriori Algorithm

• 사전에 지정한 최소 지지도보다 높은 지지도를 갖는 모든 조합을 알아내기 위한 방법 중 하나
• 확장과 가지 치기를 반복함으로써 완전 탐색보다 효율적으로 조합들을 탐색
  • 확장 - 크기 1의 후보군들을 모아 크기 2의 후보군들로, - - -
  • 가지치기 - 최소 지지도를 넘기지 못할 것이 분명한 조합들을 후보군에서 배제
• 실제 적용
  • 최소 지지도가 정해진 상황에서, 크기 1의 후보군의 지지도 확인
  • 크기 1 조합끼리 합치는 방식으로 크기 2 후보군 열 가지를 도출
  • 이 후 지지도가 최소 지지도 보다 낮은 조합 제거
  • 이후 크기 3 조합 생성 → 반복
• 장 단점
  • 조합의 크기가 커질수록 후보군이 급격히 줄어들어, 무차별 대입보다 효율적일 수 있음
  • 조합의 크기가 커질수록, 데이터베이스를 매번 참조해야함 → 데이터베이스의 데이터 저장 방식을 트리구조과 같은 수직적 구조 등으로 바꿔 탐색이 용이하도록 수정함
    • FP-Growth 알고리즘
      • 빈도에 따른 정렬
      • FP-Tree의 구성 - 정렬된 시청 내역을 이용해 구성

의사결정나무의 생성 원리

분기의 질문이 제일 중요함

→ ‘불순도’를 표현하는 두 가지의 방식

• Gini Index : ‘1 - (각 항목이 차지하는 비율의 제곱 합)’ → 항목이 두 가지일 경우, 값의 범위는 0~0.5
  • 가중 평균은, 전체에서 차지하는 비율을 곱해주는 것

이와 같이 각각의 경우를 나눠, 불순도가 0.5에 가장 가까운 것이 의미있는 구분 기준이라는 의미

• Entropy :

→ 항목이 두 가지일 경우, 값의 범위는 0~1

k-NN에 대한 기하학적 접근

k-Nearest Neighbor (최근접 이웃 알고리즘)

• 자신과 가장 가까운 k개의 이웃으로부터 분류를 수행
• Voronoi Diagram (보로노이 다이어그램)
  • 최근접 이웃이 동일하게 결정되는 점들을 하나의 영역으로 구획화
  • k = 1일 때의 k-최근접 이웃 알고리즘을 기하학적 형태로 표현한 것과도 같음
• Delaunay Triangulation (들로네 삼각 분할)
  • 인접한 영역에 해당하는 데이터끼리 이으면, 이를 들로네 삼각 분활이라고 함
    • 성질 1 → 모든 삼각형의 외접원은 내부에 다른 데이터를 포함하지 않음
    • 성질 2 → 가능한 모든 삼각 분할의 형태 가운데, 전체 내각의 최솟값이 최대가 되도록