두잉낫띵 두잉낫띵

Association Rules 많은 추천시스템에서 사용하는 Rule이다. 만약 어떤 이가 A라는 상품을 구매하면 후에 B 도 구매한다고 가정하자. 이때 어떤 이가 A라는 상품을 구매하면 을 "선행사건" , B도 구매한다를 "후행결과" 라고 부른다. 예제를 살펴보자 ! 해당 예제는 사람들이 어떤 색의 핸드폰 케이스를 샀는지 나타낸다. 우리는 여기서 다양한 Rules 를 발견할 수 있다. 1. 1,4,8,9 번 사람을 보니 red 를 사면 white 도 사는거 같네 2. 혹은 white 를 사면 red 를 사는거 같네 3. white 를 사면 blue 도 사는거 같네 처럼 언뜻보기에 수 많은 rules 를 찾을 수 있다. 사실 모든 아이템의 조합을 찾아내는게 가장 이상적이지만, 현실적으로 핸드폰 케이스가 ..

Level 3으로 올라오니 확 어려워진 느낌이 든다. 상식으로 풀기보다 문제를 읽고 아 ! 이건 어떤 알고리즘으로 접근하면 되겠다. 라는 생각이 들도록 노력해야겠다. 무튼 이번 문제는 수업때 듣고 이제는 기억이 가물가물한.. 최소신장트리를 이용한 문제다. 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다...

앞에서 최소신장트리를 구하는 두가지 알고리즘을 살펴봤다. 두개 중 먼저 크루스칼 알고리즘을 구현해보려 한다. 크루스칼 알고리즘 크루스칼 알고리즘은 간선의 cost 를 오름차순으로 정렬하고 제일 cost가 싼 간선 순서대로 연결시키는 알고리즘이다. 이때 사이클이 만들어지면 안되므로, 간선 추가 시 사이클이 발생하는지를 판단하는 알고리즘이 따로 필요한데, 이는 Union Find 를 이용하면 된다 Union Find 총 1 부터 10까지 10개의 노드가 존재한다. 노드는 서로 연결되어 있는데, 1-2-3-4 5-6-7-8 9-10 총 3 그룹으로 나눌 수 있다. 여기서 우리는 Parent[] 라는 배열을 사용하는데, 윗칸은 노드의 번호 , 아래칸은 해당 노드의 부모 노드를 의미한다. 연결정보를 갱신하는데, ..

신장트리 Spanning Tree 라고 불린다. original 그래프의 모든 노드가 연결되어 있으면서, 트리의 속성을 만족하는 그래프 신장트리의 조건 본래의 그래프의 모든 노드를 포함해야 한다. 모든 노드가 연결되어있어야 하지만 사이클이 존재하지 않아야 한다 ( 트리 이므로 ) 최소 신장트리 MST 라고 불린다. 가능한 신장트리 중에서 간선의 가중치 합이 최소인 신장트리 최소 신장트리를 찾는 알고리즘 2개 크루스칼 알고리즘 프림 알고리즘 크루스칼 알고리즘 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다. ( 이때 사이클이 만들어지면 안된다 !) 이 과정을 반복 프림 알고리..

Naïve Bayes Classifier 베이즈 정리에 기반한 통계적인 분류 기법이다. K-NN 과 비슷하지만, K-NN 의 경우엔 데이터가 실수의 범위일때만 사용이 가능한것에 비해 ( 유클리드 거리를 쓰니까 ) 나이브베이즈는 카테고리 데이터에 사용할 수 있다. 실수 범위의 데이터인 경우엔 bin 형태로 바꿔서 카테고리형 데이터로 바꿔 사용할 수 있다. 해당 예제는 범행 이력(?) 에 관한 표다. '과거 범행이력을 기반으로 이번에 범행을 저질렀는가 혹은 저지르지않았는가' 를 나타낸다. 맨 위 과거 범행이력은 X=1, X=0 으로 카테고리형 데이터인걸 볼 수 있다. 왼쪽 위 : 과거 범행 이력 있음. 이번에 범행 저지름. 오른쪽 위 : 과거 범행 이력 없음. 이번에 범행 저지름. 왼쪽 아래 : 과거 범행 ..

K-Nearest Neighbors ( KNN ) 말 그대로 최근접 이웃을 찾는 알고리즘이다. 지도학습의 한 종류로 거리기반 분류분석 모델이다. model-driven 한 모델이 아닌 data-driven 한 모델이다. 즉 데이터를 가지고 알아서 모델이 만들어지므로 식이 존재하지않는다. K-NN 알고리즘은 유유상종 알고리즘인데, 예를들어 A라는 사람과 가장 가까운 속성을 가진 사람이 영웅이라면, A도 영웅이겠지~ 하고 예측하는 방법이다. 즉 내가 구분하고 있는 데이터와 가장 가까운 곳에 있는 이웃이 누구냐 ? 를 보고 판단하는 방법이다. 그럼 가장 가까운 이웃은 수학적으로 어떻게 구할 수 있을까 ? 바로 Euclidean Distance 를 사용한다. Euclidean Distance 두 점 사이간의 거..

Logistic Regression 선형회귀분석과 달리 Y ( target ) 이 숫자가 아니고 카테고리일 때 사용하는 회귀분석. 즉, 특정 숫자를 예측한다기보다 데이터가 어떤 카테고리에 속해있는가 예측하기 위해 사용한다. 앞에선 다중선형회귀분석 식과 비슷하지만 여기서 target 값은 Y 가 아닌 P를 쓰는데, 이는 로지스틱 회귀분석에서는 예측하려는게 클래스이다보니 Y값을 확률로 나타내기 떄문이다. ( 0 ~ 1 사이의 값 ) 예를들어 Y값이 0.5 이하면 클래스 1로 , 0.5 초과면 클래스 2로 분류하는 식이다. 그러나 위의 식에는 문제점이 있는데, p 값이 음의 무한대부터 양의 무한대와 같은 큰 수도 가질 수 있다는 점이다. 그러나 우리는 p 값을 0~1 사이의 값으로만 표현해야한다. 이렇게 p의..

Linear Regression ( 선형 회귀분석 ) X로 Y 를 예측하며 이때 이때 Y 를 분류하는것이 아닌 '예측' 하는 것이기 때문에 Y 값은 항상 numerical 한 outcome 이어야 한다. Simple Linear Regression ( 단순 선형 회귀분석 ) 가장 간단한 지도학습 중 하나. 하나의 X 로 Y 를 예측하는 회귀선을 그리며, 이때 선은 실제 Y값과 예측된 값 사이의 편차의 제곱을 최소화 하도록 그려진다. Multiple Linear Regression ( 다중 선형 회귀분석 ) 여러개의 X 로 Y 를 예측하는 회귀선을 그린다. 우리는 P 개의 dimensions 들을 가지고 있으며, 해당 dimensions 들로 Y값을 예측한다. 빨간 박스 부분이 내가 가지고있는 선형식 ( ..