파고파고

Object의 type에는 크게 네 가지가 있다. 첫 번째는 흔히 데이터라고 불리는 Normal Object, 두 번째는 Normal Object와 상당히 dissimilar한 Outlier, 세 번째는 micro-cluster 형태의 Outlier, 네 번째는 Normal Object이지만, Fringe Object로서 outlier와 구별이 힘든 데이터다. 이미 이전에 클러스터링에 대해 포스팅하면서, outlier를 다루는 것에 대해 언급한 적이 있었다. 여기서는 outlier를 잘 detection하는 여러 기법에 초점을 맞춰 포스팅할 예정이다. Outlier Detection의 여러 종류 Outlier Detection은 여러 기반의 종류가 있고, 각 종류별로 장단점이 각기 다르다. 하나씩 살펴보..

Graph Mining이란, graph로부터 흥미로운 특징을 mining하는 것이다. 아래 Graph mining의 특징을 읽으며 개념을 익혀보자. "Graph의 정보가 (1) Heterogeneous 하고 (2) Multi-Relational하다." Node(object)의 입장에서도 여러 종류의 label, class, attribute 등이 있을 수 있고, Edge(links)의 입장에서도 여러 종류의 link (directed 여부)가 있을 수 있다. Graph Mining를 노드를 중요도(Priority) 순으로 Ranking하는 것으로 이해하자. HITS (Hyperlink Induced Topic Search) HITS는 대표적인 Graph Mining 기법 중 하나다. node의 중요도를 ..

Density Based Clustering은, 말 그대로 밀도를 기반으로 데이터를 클러스터링하는 기법이다. noise에 강하다는 점 등을 이유로 클러스터링에 자주 사용된다. Hyper-Parameter들 density method의 대표적인 파라미터는 아래 두 개 이다. # ε density를 판단할 구간이다. neighborhood로 판단하는 원의 radius라고 생각하면 쉽다. # Minpts density threshold이다. 해당 점이 high density를 가지고 있다고 판단하기 위해 필요한 구간 내 최소 점의 수 이다. Data Point의 종류 밀도기반 클러스터는, 데이터 상의 점들을 그 밀도와 이웃을 기준으로 세 가지 유형으로 나눈다. # core point ε 구간 안에 Minpts..

이전에 Hierarchical Clustering의 대표적인 기법들을 포스팅했다. Hierarchical Clustering 기법의 공통적인 단점 중 하나가 시간복잡도가 크다는 것이다.(최소 O(n^2)이다.) 여기서는 이러한 단점을 Hierarchical Clustering에 Distance의 개념을 더해 극복한 기법을 포스팅할 것이다. BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) Birch는 CF tree를 이용한 클러스터링 방식이며, 작동방식이 (1) CF-Tree 만들기, (2) CF-Tree의 leaf node를 클러스터링 하는 것으로 단순하다. # CF (Clustering Feature) 구체적인 작동방식 이전에,..

이전 포스팅에서 Partitioning Clustering Method 들 몇가지에 대해 다뤘다. Hierarchical Clustering도 Distance를 기준으로 클러스터링을 수행한다는 점은 partitioning method와 일관적이다. 아래의 Hierarchical Clustering Method의 특징을 살펴보며 그 개념을 이해해보자. 특징 1. k (클러스터의 수)를 미리 정하지 않아도 된다. 단, 종료조건 (termination condition) 2. Top Down 방식과 Bottom Up 방식이 있다. Top Down 방식은 DIANA, Bottom Up 방식은 AGNES가 대표적이다. 아래 그림을 통해 두 방식의 차이를 대략적으로 이해할 수 있다. 3. Dendrogram을 이용..

이전포스팅에서 K-means의 작동원리 등에 대해 다뤘다. 여기서 작성할 것은 K-means와 동일한 partitioning method이면서도 데이터 타입과 상황 등에 따라 다른 클러스터링 알고리즘들이다. K-modes k-modes는 k-means의 categorical data 버전이라고 생각하면 쉽다. (* 카테고리 데이터만 있어야 가능하다.) k-means와 작동원리는 동일하나, 아래 두 가지가 다르다. # Distance의 정의 $$d(X, Y) = \sum_{j=1}^{m}d(x_{j}, y_{j}) where \ d(x_{j}, y_{j}) = 0 \ \ if \ \ matched \ \ else \ \ 1$$ distance 함수가, centroid와의 직접적인 거리가 아니라, misma..

K-means는 partitioning method 클러스터링의 대표적인 예다. 클러스터의 centroid와 클러스터 내 점들 간의 거리(정확히는 거리 제곱 합)가 최소가 되도록 k개의 클러스터를 만드는 기법이다. 즉, 아래가 최소가 되도록 하는 클러스터 k를 만드는 것이 k-means라고 정리할 수 있겠다. $$\sum_{m=1}^{K}\sum_{i=1}^{Nm}(C_{m}-t_{i}^{m})^{2}$$ * C_m은 m 번째 cluter의 centroid, t는 m번째 cluter에 속한, i번째 datapoint를 가리킨다. 사실 위 식이 최소가 되도록 하는 partition을 찾기 위해서는, 모든 가능한 partition을 시도해보아야 한다. 현실적으로 불가능한 방식이다. 따라서, 클러스터를 cen..

여러 클러스터링 기법들에 대해서 포스팅할 예정인데, 그 전에 클러스터링이 무엇인지부터 시작해서... 관련 기본 개념을 먼저 여기 써보려 한다. 클러스터와 클러스터 분석 먼저 클러스터(cluster)가 무엇인지부터 알아야 한다. 클러스터란, 데이터 object들의 집합(collection)이다. 데이터가 뭉쳐있는 군집이라고 생각하면 쉽다. 그런 의미에서, 클러스터 분석은, 데이터에서 찾은 특성을 바탕으로 데이터 간 유사함을 찾아 묶는 것을 의미한다고 볼 수 있다. 클러스터 분석의 대표적인 특징들에 대해서도 몇 가지 살펴보자. 1. Unsupervised Learning 사전에 class가 정의되어 있지 않은, 즉 정답이 없는 비지도 학습이다. 데이터 자체의 특성이 궁금한 것에서 출발한 분석이며, 예측이 목..

Bayesian Classification은, "어떤 일이 일어날 확률이 얼마나 있음직한가?"를 기반, 즉 조건부 확률을 이용하는 분류기법이다. $$argmax_{k}p(C_{k|X})$$ 즉 어떤 조건이 주어졌을 때, 데이터가 속할 확률이 가장 높은 클래스가 그 데이터의 클래스로 분류되는 것이라고 이해하면 되겠다. 스팸메일 분류 문제를 예로 들자면, 메일에 'money'라는 단어가 들어있다는 조건 하에, (X) 메일이 스팸이 아닐 확률보다 스팸일 확률이 높기 때문에 스팸으로 분류(C)되는 상황으로 이해하자. 베이즈 정리 베이지안 분류가 바탕으로 하고 있는 베이즈 정리를 간단하게 짚고 넘어가도록 하자. $$p(C|X) = {p(X|C)\over p(X)}* p(C)$$ # posterior $$p(C|X..

Decision Tree는 말 그대로, 트리 형태의 구조를 세워 Classification을 수행하는 기법이다. 특성 Decision Tree는 아래와 같은 세 가지 특징을 지니고 있다. Greedy, Recursive, and Divide & Conquer 1. Greedy 다음단계를 고려하지 않고, 현재 상태만 고려한다. 2. Recursive 같은 방식을 재귀적으로 반복한다. (아래 동작순서를 통해 이해할 수 있다.) 3. Divide & Conquer 큰 문제를 같은 작은 문제들로 쪼개서 해결한다. (마찬가지로 아래 동작순서를 통해 이해할 수 있다.) 구조 Decision Tree는 leaf node와 그렇지 않은 node로 구성되어 있다. Classification의 측면에서 각 노드의 의미를 ..