전체 글128 크루스칼 알고리즘(Kruskal Algorithm) [Python / 파이썬] 1. 크루스칼 알고리즘 신장 트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 우리는 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 2개의 도시 A, B를 선택했을 때, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 '연결'할 때, 최소한의 비용으로 연결 하려면 어떤 알고리즘을 이용해야 할까? 예를들어 위와같은 그래프가 있다고 가정해보자. 3개의 도시가 있고, 각 도시 간 도로를 건설하는 비용은 23, 13, 25이다. 여기서.. 2022. 1. 15. 서로소 집합(Disjoint Sets) [Python / 파이썬] 1. 서로소 집합이란? 수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1, 2}와 {3, 4}는 서로소 관계이다. 반면 집합 {1, 2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. .. 2022. 1. 14. Light GBM 이전에 소개했던 XGBoost에 이어서 Light GBM에 대해 정리해보려고 한다. 출처 : 이 글은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다. 1. Light GBM 1.1 Motivation 전동적일 GBM은 모든 데이터의 모든 피처를 탐색후 정보 획득률을 조사한다. 모든 데이터에대한 탐색을 효율적으로 수행하기 위해 XGBoost와 같은 경우 데이터를 버켓(bucket)으로 나누어 탐색을 수행하는 Approximate 알고리즘을 사용하였다. Light GBM은 모든 데이터에 대한 탐색과 모든 피처에 대한 완전 탐색을 완화하기 위해 고안되었다. 1.2 idea Gradient-based One-Side Sampling(GOSS) 개별적인 데이터는 일반적으로 서로 다른 그레디언트를 가지.. 2022. 1. 9. XGBoost 이전에 소개했던 부스팅(Boosting)에 이어서 XGBoost에 대해 정리해보려고 한다. 출처 : 이 글은고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다. 1. XGBoost GBM 알고리즘의 종류 중 하나로서 보다 빠르게 해를 찾아가는 과정에서 병렬 처리를 가능하게 하고자 하는 목적으로 설계된 알고리즘이다. 또한 GBM의 단점인 느린 수행 시간과 과적합 규제(R)부재 등의 문제 개선하고자 고안된 모델이다. X는 extrem을 의미하는데 GBM의 성능을 극한까지 끌어올렸다 라는 의미로 XGBoost라고 불린다고 생각하면 될 것 같다. 이제 XGBoost의 핵심적인 아이디어에 대해 개념적으로 정리해보려고 한다. Split finding algorithm 의사결정 나무에서의 Basic exact.. 2022. 1. 9. Boosting 이전에 소개했던 랜덤 포레스트(Random forest)에 이어서 Boosting과 Boosting알고리즘의 종류에 대해 정리해보려고 한다. 1. Boosting 여러 개의 learning 모델을 순차적으로 구축하여 최종적으로 합친다.(앙상블 학습) 여기서 사용하는 learning 모델은 의사결정 나무(Decision tree)를 사용하며 매우 단순한 모델이다. 단순한 모델 : 이진 분류 모델이라면 정확도가 0.5보다 조금더 좋은 모델 각 단계에서 새로운 base learner를 학습하여 이전 단계의 base learner의 단점을 보완한다. 각 단계를 거치면서 모델이 점차 강해진다 -> Boosting 2. Boosting의 종류 boosting의 종류는 아래와 같다. Adaptive boosting(.. 2022. 1. 8. [ML] 랜덤 포레스트(Random Forest) 이전에 소개했던 의사결정 나무(Decision Tree)에 이어서 랜덤 포레스트에 대해 정리해보려고 한다. 의사결정 나무는 오버 피팅될 가능성이 높다는 약점을 가진다. 가지치기(Pruning)를 통해 트리의 최대 높이를 조절할 수 있지만 이로써는 오버 피팅을 충분히 해결할 수 없다. 이러한 의사결정 나무의 오버피팅 문제를 해결하기 위한 전략으로 랜덤 포레스트(Random forest)가 있다. 파이썬 기반의 오픈 ML 라이브러리인 사이킷런(scikit-learn) 에서는 랜덤 포레스트를 활용한 분류를 위한 API를 제공한다. RandomForestClassifier가 그것이다. 아래 코드는 RandomForestClassifier를 사용하여 UCI 머신러닝 레파지토리 에서 제공하는 사용자 행동 인식(Hu.. 2022. 1. 8. 이전 1 ··· 15 16 17 18 19 20 21 22 다음
