Naive Bayes classifier Naive Bayes classifier 나이브 베이즈 분류기의 경우 간단하지만 널리 쓰이는 probabilistic 방식으로 attribute가 주어졌을 때 어떠한 클래스에 속할 확률을 제공합니다. 즉 클래스 예측 뿐 아니라 클래스에 속할 확률까지 알려주는 알고리즘입니다. 나이브 베이지 분류기는 P(Class label = Purchase | Salary = 5000, Age = 25, Gender = "Male") =? 와 같은 질문에 답을 제공합니다. 월급은 5000, 나이는 25, 성별은 남성일 때 Purchase 클래스에 속할 확률은 얼마인가? 결합 확률 P(x, y)란 x와 y가 동시에 발생할 확률을 의미하며, 조건부 확률 P(y | x)는 x가 발생했을 때 y가 발생할 확률을 의미합니다. 우.. K-Nearest Neighbor Algorithm (KNN 알고리즘) K-Nearest Neighbor K-NN 알고리즘은 데이터를 가장 가까운 속성에 따라 분류하는 알고리즘으로, K개의 가까운 이웃의 속성에 따라 분류합니다. K-NN 알고리즘의 경우 모델을 만들지 않고 새로운 데이터가 주어지면 기존의 학습 데이터를 기반으로 클래스를 예측하는 방식입니다. Basic Approach K-NN 알고리즘의 경우 d차원 공간에서 (x, y)를 한 점으로 간주합니다. 이때 x는 d개의 데이터셋이며, y는 각 데이터들의 클래스 레이블을 의미합니다. 만약 새로운 x'가 주어지게 되면 각각의 (x, y)와 거리를 계산하고, x'와 비슷한 k개의 거리를 찾습니다. k개의 거리 중 다수의 이웃이 있는 클래스에 따라 새로운 데이터 x'의 클래스를 예측할 수 있습니다. 만약 k를 너무 작게 설.. Hadoop Installation on Ubuntu (나의 하둡 설치 삽질기) 하둡? Hadoop은 여러 클러스터에서 대규모 데이터 셋을 분산 처리할 수 있게 하는 프레임워크입니다. 아마 빅데이터 수업이나 데이터마이닝 수업을 하실 때 하둡을 설치할 일이 생기실텐데, 저 또한 이러한 이유로 설치를 하게 되었습니다. 이 포스팅을 보는 분들은 적어도 저처럼 힘들게 깔지 않기를 바라면서 포스팅을 합니다! (VMware설치를 선행하시고 진행하시기 바랍니다) 1. JAVA 8 설치 1) apt 업데이트 sudo apt-get update 2) JAVA 8 설치 sudo apt-get install openjdk-8-jdk openjdk-8-jre 3) 설치 확인 java -version 2. SSH 설정 1) Openssh Server 설치 sudo apt-get install openssh.. Cloud Computing Computing at scale Big data는 많은 processing을 요구하므로 특별한 알고리즘이나 하드웨어, 도구들을 동반한다.Cluster는 우리가 필요한 resource를 제공하는데, 문제는 scale이다. 규모가 커지게 되면 당연히 power가 많이 필요하게 되고 (power는 여기서는 전력, 전기 정도로 생각하면 된다), 그에 따라 열이 많이 방출되므로 cooling system도 해결해야 하는 주요 이슈가 될 것이다. Scale-up 성능이나 용량 증강을 목적으로 하나의 서버에 디스크를 추가하거나 CPU나 메모리를 업그레이드시키는 것으로 기존의 하드웨어를 보다 높은 사양으로 업그레이드하는 것 추가적인 네트워크 연결 없이 용량을 증강할 수 있고, 추가되는 용량이나 업그레이드 비용만 부가.. CURE Algorithm (Clustering Using REpresentatives) CURE (Clustering Using REpresentatives) CURE 알고리즘은 k-means와 BFR이 cluster가 정규분포를 따르며, outlier에 취약하다는 단점을 보완하기 위해 만들어진 하이브리드 클러스팅 기법이다. centroid-based aprroach와 all-point approach를 접목하였으며, 타원형이 아닌 모양의 클러스터를 허용한다. CURE 알고리즘의 과정은 다음과 같다 1) 메인메모리의 용량만큼 샘플 instance를 랜덤하게 뽑는다 2) 초기 클러스터를 형성하기 위해 hierarchical clustering을 이용하여 가까운 점들끼리 그룹핑한다 3) 각 클러스터에서 최대한 멀리 떨어져 있는 representative instances(대표점)를 정해진 수만.. BFR Algorithm BFR Algorithm (Bradley-Fayyad-Reina) K-means의 경우 데이터 집합이 메모리에 올라갈 수 있는 사이즈일 때만 사용 가능하기 때문에, BFR알고리즘은 K-means를 변형하여 매우 큰 데이터 집합을 다룰 수 있게 한다. BFR 알고리즘은 유클리드 공간에서 정규분포(가우시안 분포)를 따른다고 가정하는데, 클러스터들이 centroid 주변에 분산되었다고 생각하면 된다. 다른 차원에서의 표준 편차는 다양할 수 있다. → x축, y축으로 볼 때 각 그래프를 보는 관점이 다름 2차원 그래프에서는 표준편차가 높을수록 넓은 산 모양이고, 낮을수록 좁은 산 모양이다. BFR 알고리즘의 과정은 다음과 같다. 1) 디스크에서 메인 메모리가 가득찰만큼 데이터를 읽는다 2) 이전 메모리의 대부분.. DBSCAN (밀도 기반 클러스터링) DBSCAN DBSCAN은 밀도 기반의 클러스터링 알고리즘입니다. 같은 클래스에 속하는 데이터는 서로 근접하게 분포할 것이다'라는 가정으로 시작하며, 밀도 기반으로 클러스터링하기 때문에 데이터셋이 불특정한 분포를 가질 때 유용합니다. Density 밀도(Density)는 한 데이터포인트의 Eps(거리반경)내에 있는 포인트의 수를 의미합니다. 간단히 말하면 Eps 내에 데이터가 몇 개 있는가?라고 생각하면 되는데, 이때 Eps는 자기 자신의 점을 포함한 반경을 의미합니다. 결국, 각 포인트의 밀도는 Eps를 어떻게 설정하느냐에 따라 달라지게 됩니다. 만약 eps가 너무 크면 모든 점들이 반경 안에 포함되기 때문에 비슷한 밀도를 가지게 되고, eps가 너무 작으면 모든 포인트들이 자신 뺴고 그 반경에 속하지.. K-means Clustering (K-평균 군집화) K-means Clustering K-means에서 K는 클러스터의 개수를 의미하고 means는 평균을 의미한다. 말 그대로 주어진 데이터를 k개의 클러스터로 묶는 알고리즘이다. Basic Algorithm 1: Select K points as initial centroids 2: Repeat 3: Form K clusters by assigning each point to its closest centroid 4: Recompute the centroid of each cluster 5: Until Centroids do not change k-means의 과정은 다음과 같다 1) k개의 initial centroid를 랜덤하게 선정한다. 2) 각 point들을 가장 가까운 centroid에 할당하여.. Hierarchical Clustering (계층적 군집) Hierarchical Clustering hierarchical clustering은 각 data point를 하나의 클러스터로 간주하고 반복적으로 가장 가까운 두개의 클러스터를 합쳐나가는 방식이다. hierarchical clustering은 single cluster에서 시작하여 가까운 cluster를 반복적으로 합쳐나가는 상향식 방법인 Agglomerative approach와 all inclusive한 cluster에서 쪼개나가는 하향식 방식인 Divisive approach로 나누어진다. Divisive approach의 경우 어떠한 기준으로 split하는지의 경우를 고려하는 비용이 크므로 잘 사용하지 않고, 이번 포스팅에서는 Agglomerative에 대해서만 설명하고자 한다. Agglome.. Clustering (군집화) Clustering 클러스터링이란 데이터를 meaningful & useful group으로 나누는 것을 의미한다. 여기서 'meaningful'은 training data가 비슷한 데이터끼리 그룹핑되는 structure를 이해할 수 있어야 함을 의미하고, 'useful'은 전체 training data 모두를 가질 필요 없이 그 크기를 줄여 대표적인 데이터만 가지고 분석할 수 있어야함을 의미한다. 결국 클러스터링은 class(=group/cluster)을 찾는 것을 목표로 하는데, 클러스터링의 정의는 아래와 같이 정의할 수 있다. "Maximize the similarity within a group and Maximize the difference between groups" 같은 cluster 내의.. Flajolet-Martin Algorithm Counting Distinct Elements Flajolet-Martin 알고리즘은 distinct data를 세는 알고리즘입니다. 이 알고리즘은 서로 다른 데이터들을 특정한 해시 함수를 이용하여 해싱한 후 그 결과를 저장하기 위해 해쉬테이블을 메모리 상에 유지하면 됩니다. 하지만 해시테이블이 너무 커서 메모리 상에 유지할 수 없다면 메모리를 절약하기 위해 서로 다른 원소들의 개수를 그저 추정해야하는데, 이 때 Flajolet-Martin 알고리즘을 사용합니다. Application Flajolet-Martin 알고리즘은 다음과 같은 상황에 적용할 수 있습니다. - How many different words are found among the Web pages being crawled at a si.. Bloom filters Filtering Data Stream Filtering은 key list인 S가 주어지면, S에 어떤 stream의 튜플이 존재하는지 살피는 것으로 일종의 membership test에 해당한다. 가장 간단한 방법은 hash table에 S의 모든 key를 저장하면 되는데, 우리는 모든 key를 저장할 충분한 메모리를 가지고 있지 않다! Bloom Filter n의 길이를 가진 비트 배열과 k개의 해시 함수가 존재하며, 해시 함수들은 [0, n) 범위의 해시 값을 출력한다. 원소 추가 시, 추가하려는 원소에 대해서 k개의 해시 값을 계산한 후 각 해시 값을 비트 배열의 인덱스에 대응하는 비트를 1로 세팅한다 원소 검사 시, 검사하려는 원소에 대해서 k개의 해시 값을 계산한 다음, 각 해시 값을 비트 배.. 이전 1 2 다음
