본문 바로가기

전체 글

 (8)
LOESS from scratch with python3 본문은 LOESS(Locally estimated scatterplot smoothing)에 대한 내용을 설명, 구현하였음. (구현 : python3) 1. LOESS? LOcally Estimated Scatterplot Smoothing의 약자로, LOcally WEighted Scatterplot Smoothing, LOWESS라고도 한다. 본문에서는 LOESS로 통일하여 작성한다. LOESS는 주어진 데이터로부터 기저 모델(deterministic model)을 추정하는 전통적인 회귀(Regression) 방법 중 하나인 최소제곱회귀(Least square regression)를 활용하는 방법이다. 최소제곱회귀는 크게 선형과 비선형으로 구분할 수 있는데, LOESS는 선형회귀의 단순성과 비선형회귀..
Isolation Forest from scratch with python3 Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou, Isolation Forest해당 글은 Isolation Forest 논문 내용 요약 및 구현, 관련 의견을 정리하였음. (구현 : python3) 논문 요약1. Introduction 기존 모델 기반(model-based) 이상 탐지 방법들은 정상치(normal instances)에 대한 프로필을 생성하고, 이와 일맥하지 않는 대상을 이상치로 분류하는 방식이다. 필자에 따르면, 이러한 접근 방식은 이상치가 아닌 정상치 프로필(profile)에 적합화(optimized)되기 때문에 오히려 이상치 탐지 자체는 부정확하고, 더 나아가 높은 연산 복잡도로 인해 고차원 데이터에 적용하기 어렵게 만든다. 따라서 필자는 기존 방법과 달리,..
Generalized Hough Transform from scratch with python3 허프 변환(Hough Transformation)은 인라이어와 아웃라이어가 섞여있는 상황에서 인라이어 군집을 찾아내는 군집화 알고리즘이다. 허프변환의 이러한 특성을 활용하여 직선, 원 등과 같은 특정 도형을 찾아내는데 활용할 수 있는데, Generalized Hough Transformation(GHT)은 임의의 도형에 일반적으로 사용할 수 있도록 설계된 버전의 허프 변환이다. 허프 변환은 찾고자 하는 도형을 (도형의 특성을 반영한) 허프 공간으로 변환한 후, 누적 테이블(accumulator)을 만들어 투표(voting)하는 방식을 취한다. 이에 대한 자세한 설명을 위해, GHT를 사용하여 아래의 그림 (B)에서 (A)를 찾아내는 예시를 살펴보자. 먼저 (A)는 찾고자 하는 도형(우산)을 정의한 영상..
우선순위 큐 : 힙(heap) 큐(Queue)는 선입선출(FIFO)로 이뤄진 자료구조다. 우선순위 큐(Priority Queue)는 큐의 출력 조건을 선입에서 특정 우선순위로 바꾼 큐를 의미한다. 다시 말해, 먼저 들어온 순서대로 내보내는 것이 아니라, 값들 간 우선순위를 설정하고, 이 우선순위가 높은 순서대로 출력하는 자료구조(큐)다. 우선순위 큐를 구현하는 포인트는 아래 2가지다.1. 데이터 간 우선순위의 기준은 무엇인가? (예 - 값의 크기 등)2. 우선순위가 높은 데이터 순으로 어떻게 정렬할 것인가? 1번 사항은 사용자의 목적에 따라 정하면 되며, 2번의 경우, 해당 큐에서 데이터를 출력하거나 입력할 때마다 고려해야 한다. 따라서, 우선순위 큐의 ADT에서는 (1) Insert, (2) delete 메서드 구현이 핵심니다.(1..
트리 : [4] 이진탐색트리 이진탐색트리(Binary Search Tree)는 탐색작업을 효율적으로 수행하기 위해 만들어진 이진트리다. ㄴ 임의의 노드 기준으로 노드의 값(Key, value)보다 (1) 작으면 왼쪽, (2) 크면 오른쪽에 저장한다.ㄴ 결과적으로 가장 왼쪽 끝의 자식노드에는 가장 작은 값을, 가장 오른쪽 끝의 자식노드에는 가장 큰 값을 갖는다.ㄴ 이진탐색트리를 중위순회하게되면, 오름차순으로 정렬된 배열을 출력한다. 이진탐색트리 연산위에서 말한 바와 같이 이진탐색트리를 구현하기 위해선 (1) 삽입, (2) 삭제연산을 구현해야 한다. (1) 삽입연산이진탐색트리가 존재할 때, 새로운 값을 삽입하고자 할 때 사용하는 방법이다. 핵심은 새롭게 삽입하고자 하는 변수(key)와 트리 내 존재하는 노드의 값을 순차적으로 비교하여 ..
트리 : [3] 이진트리 순회 순회(traversal)란, 트리의 노드들을 빠뜨리거나 중복하지 않고 모두 방문하는 탐색 방법이다. L, V, R을 각각 왼쪽으로 이동, 방문(또는 출력), 오른쪽으로 이동을 나타낸다고 할 때, 총 6가지 방법으로 L, V, R을 나열할 수 있다. 그러나 트리 : [2] 이진트리에서 언급한 바와 같이, 이진트리에는 왼쪽 $\rightarrow$ 오른쪽으로 이동이 정해져있다고 가정하기 때문에 (1) VLR, (2) LVR, (3) LRV 총 3가지 조합만 가능하다. 이 각각을 (1) 전위순회(preorder traversal), (2) 중위순회(inorder traversal), (3) 후위순회(postorder traversal)이라고 한다. 그 외 레벨순서대로 이진트리를 방문하는 (4) 레벨순회(lev..
트리 : [2] 이진트리 이진트리(Binary Tree)의 경우, 상대적으로 많이 사용하는 자료구조로 다음과 같은 특징을 갖는다. 이진트리 개념1. 모든 노드가 2개의 서브트리를 갖는 트리다. (서브트리는 공백($\emptyset$)을 포함한다.)    = 모든 노드는 최대 2개의 자식노드를 갖을 수 있다. (자식노드는 $\emptyset$을 포함한다.)    = 모든 노드의 차수(degree)는 2 이하다.2. 이진트리의 서브트리 간에는 왼쪽 $\rightarrow$ 오른쪽 순서가 존재한다. 이진트리의 성질1. 노드가 $N$개이면, 링크는 $N-1$개다. (=루트를 제외한 모든 노드는 부모노드가 존재) 2. 레벨(level)이 $i$일 때, 해당 레벨이 갖을 수 있는 최대 노드 수 : $2^{i-1}$    ㄴ 높이(heigh..
트리 : [1] 일반트리 트리(Tree)는 다음과 같은 특성을 갖는 자료구조다. (1) 위계구조를 나타내는 자료 구조다.(2) 트리의 원소(노드) 간 $1:N$의 비선형 구조를 갖는다.  트리 관련 용어 정리$\quad$ (1) 노드(Node) : 트리의 구성요소$\quad$ (2) 루트(Root) : 노드 중 부모를 갖지 않는 노드$\quad$ (3) 단말노드(Leaf) : 자식 노드를 갖지 않는 노드$\quad$ (4) 레벨(Level) : 트리의 각 층이 갖는 순서로, 루트는 0 또는 1이 된다.$\quad$ (5) 높이(Height) : 트리의 최대 레벨$\quad$ (6) 차수(Degree) : 자식 노드 수$\quad$ (7) 서브트리(Subtree) : 노드와 그 자식 노드로 이뤄진 집합$\quad$ (8) 포레스트..

티스토리툴바