IT&컴퓨터공학
-
[알고리즘] 최소신장트리 구하기 - 크루스칼 알고리즘 C++IT&컴퓨터공학/자료구조&알고리즘 2021. 2. 14. 22:09
앞에서 최소신장트리를 구하는 두가지 알고리즘을 살펴봤다. 두개 중 먼저 크루스칼 알고리즘을 구현해보려 한다. 크루스칼 알고리즘 크루스칼 알고리즘은 간선의 cost 를 오름차순으로 정렬하고 제일 cost가 싼 간선 순서대로 연결시키는 알고리즘이다. 이때 사이클이 만들어지면 안되므로, 간선 추가 시 사이클이 발생하는지를 판단하는 알고리즘이 따로 필요한데, 이는 Union Find 를 이용하면 된다 Union Find 총 1 부터 10까지 10개의 노드가 존재한다. 노드는 서로 연결되어 있는데, 1-2-3-4 5-6-7-8 9-10 총 3 그룹으로 나눌 수 있다. 여기서 우리는 Parent[] 라는 배열을 사용하는데, 윗칸은 노드의 번호 , 아래칸은 해당 노드의 부모 노드를 의미한다. 연결정보를 갱신하는데, ..
-
[알고리즘] 최소 신장 트리IT&컴퓨터공학/자료구조&알고리즘 2021. 2. 14. 20:43
신장트리 Spanning Tree 라고 불린다. original 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프 신장트리의 조건 본래의 그래프의 모든 노드를 포함해야 한다. 모든 노드가 연결되어있어야 하지만 사이클이 존재하지 않아야 한다 ( 트리 이므로 ) 최소 신장트리 MST 라고 불린다. 가능한 신장트리 중에서 간선의 가중치 합이 최소인 신장트리 최소 신장트리를 찾는 알고리즘 2개 크루스칼 알고리즘 프림 알고리즘 크루스칼 알고리즘 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다. ( 이때 사이클이 만들어지면 안된다 !) 이 과정을 반복 프림 알고리..
-
[데이터분석개론] Naïve Bayes Classifier. 나이브베이즈 분류IT&컴퓨터공학/데이터분석개론 2021. 2. 13. 23:28
Naïve Bayes Classifier 베이즈 정리에 기반한 통계적인 분류 기법이다. K-NN 과 비슷하지만, K-NN 의 경우엔 데이터가 실수의 범위일때만 사용이 가능한것에 비해 ( 유클리드 거리를 쓰니까 ) 나이브베이즈는 카테고리 데이터에 사용할 수 있다. 실수 범위의 데이터인 경우엔 bin 형태로 바꿔서 카테고리형 데이터로 바꿔 사용할 수 있다. 해당 예제는 범행 이력(?) 에 관한 표다. '과거 범행이력을 기반으로 이번에 범행을 저질렀는가 혹은 저지르지않았는가' 를 나타낸다. 맨 위 과거 범행이력은 X=1, X=0 으로 카테고리형 데이터인걸 볼 수 있다. 왼쪽 위 : 과거 범행 이력 있음. 이번에 범행 저지름. 오른쪽 위 : 과거 범행 이력 없음. 이번에 범행 저지름. 왼쪽 아래 : 과거 범행 ..
-
[데이터분석개론] K-Nearest NeighborsIT&컴퓨터공학/데이터분석개론 2021. 2. 13. 21:18
K-Nearest Neighbors ( KNN ) 말 그대로 최근접 이웃을 찾는 알고리즘이다. 지도학습의 한 종류로 거리기반 분류분석 모델이다. model-driven 한 모델이 아닌 data-driven 한 모델이다. 즉 데이터를 가지고 알아서 모델이 만들어지므로 식이 존재하지않는다. K-NN 알고리즘은 유유상종 알고리즘인데, 예를들어 A라는 사람과 가장 가까운 속성을 가진 사람이 영웅이라면, A도 영웅이겠지~ 하고 예측하는 방법이다. 즉 내가 구분하고 있는 데이터와 가장 가까운 곳에 있는 이웃이 누구냐 ? 를 보고 판단하는 방법이다. 그럼 가장 가까운 이웃은 수학적으로 어떻게 구할 수 있을까 ? 바로 Euclidean Distance 를 사용한다. Euclidean Distance 두 점 사이간의 거..
-
[데이터분석개론]Logistic Regression . 로지스틱 회귀분석IT&컴퓨터공학/데이터분석개론 2021. 2. 13. 20:30
Logistic Regression 선형회귀분석과 달리 Y ( target ) 이 숫자가 아니고 카테고리일 때 사용하는 회귀분석. 즉, 특정 숫자를 예측한다기보다 데이터가 어떤 카테고리에 속해있는가 예측하기 위해 사용한다. 앞에선 다중선형회귀분석 식과 비슷하지만 여기서 target 값은 Y 가 아닌 P를 쓰는데, 이는 로지스틱 회귀분석에서는 예측하려는게 클래스이다보니 Y값을 확률로 나타내기 떄문이다. ( 0 ~ 1 사이의 값 ) 예를들어 Y값이 0.5 이하면 클래스 1로 , 0.5 초과면 클래스 2로 분류하는 식이다. 그러나 위의 식에는 문제점이 있는데, p 값이 음의 무한대부터 양의 무한대와 같은 큰 수도 가질 수 있다는 점이다. 그러나 우리는 p 값을 0~1 사이의 값으로만 표현해야한다. 이렇게 p의..
-
[데이터분석개론] Linear Regression . 선형회귀분석IT&컴퓨터공학/데이터분석개론 2021. 2. 13. 14:28
Linear Regression ( 선형 회귀분석 ) X로 Y 를 예측하며 이때 이때 Y 를 분류하는것이 아닌 '예측' 하는 것이기 때문에 Y 값은 항상 numerical 한 outcome 이어야 한다. Simple Linear Regression ( 단순 선형 회귀분석 ) 가장 간단한 지도학습 중 하나. 하나의 X 로 Y 를 예측하는 회귀선을 그리며, 이때 선은 실제 Y값과 예측된 값 사이의 편차의 제곱을 최소화 하도록 그려진다. Multiple Linear Regression ( 다중 선형 회귀분석 ) 여러개의 X 로 Y 를 예측하는 회귀선을 그린다. 우리는 P 개의 dimensions 들을 가지고 있으며, 해당 dimensions 들로 Y값을 예측한다. 빨간 박스 부분이 내가 가지고있는 선형식 ( ..
-
[데이터분석개론] Predictive Performance / Classifier PerformanceIT&컴퓨터공학/데이터분석개론 2021. 2. 12. 14:57
앞에서 머신러닝으로 만들어진 모델을 가지고 우리는 예측 혹은 분류를 한다고 배웠다. 그 중 모델이 얼마나 예측을 잘하는지는 Predictive performance 로 나타내고, 분류를 잘하는지는 Classifier performance 로 나타낸다. Predictive Performance 숫자를 예측했을때 모델이 얼마나 잘 예측하고있는지 측정하는 방법. Predictive Accuracy 를 측정하는 방법 1. MAE ( Mean Absolute Error ) : absolute error 의 평균을 나타낸다. 2. Mean Error : error 의 평균을 나타낸다. Mean Error 와 MAE 는 절댓값이 있고 없고의 차이만 가지고 있다. 이런 모델을 그렸을때 , MAE 의 경우 절댓값이 있으..
-
[데이터분석개론] 머신러닝과 Performance EvaluationIT&컴퓨터공학/데이터분석개론 2021. 2. 12. 12:47
머신러닝 개요 머신러닝은 크게 Supervised Learning ( 지도학습 ) : 내가 타겟하고 있는 값이 있다. 그 타겟하고있는 값을 잘 분류하거나 예측해줘 ! Unsupervised Learning ( 비지도학습 ) : 뭘 설명하고있는지는 모르지만 그냥 이 데이터간에 어떻게 다른지 알고싶어 ! 잘 분류해봐 Reinforcement Learning ( 강화학습 ) 로 이루어져 있다. 머신러닝 과정 Raw Data 를 가지고 전처리 과정을 거친다. ( 앞에서 배운 PCA 와 같은 ) 이 전처리된 데이터를 가지고 머신러닝 과정을 진행한다. Simple Linear Regression ( 단순 선형 회귀분석 ) 위의 그림에서 볼 수 있듯이 , 약의 복용량과 지속기간에 대한 데이터는 빨간 점의 형태로 찍혀..