알고리즘 8

클러스터링 #1 - KMeans

클러스터링과 KMeans를 이용한 데이타의 군집화조대협 (http://bcho.tistory.com)클러스터링 문제클러스터링은 특성이 비슷한 데이타 끼리 묶어주는 머신러닝 기법이다. 비슷한 뉴스나 사용 패턴이 유사한 사용자를 묶어 주는것과 같은 패턴 인지나, 데이타 압축등에 널리 사용되는 학습 방법이다.클러스터링은 라벨링 되어 있지 않은 데이타를 묶는 경우가 일반적이기 때문에 비지도학습 (Unsupervised learning) 학습 방법이 사용된다. 클러스터링 알고리즘은 KMeans, DBSCAN, Hierarchical clustering, Spectral Clustering 등 여러가지 기법이 있으며, 알고르즘의 특성에 따라 속도나 클러스터링 성능에 차이가 있기 때문에, 데이타의 모양에 따라서 적절..

오토인코더를 이용한 비정상 거래 검출 모델의 구현 #3 - 데이타 전처리

오토 인코더를 이용한 신용카드 비정상 거래 검출 #3 학습 데이타 전처리 조대협 (http://bcho.tistory.com) 앞의 글들 (http://bcho.tistory.com/1198 http://bcho.tistory.com/1197 ) 에서 신용카드 이상 검출을 하기 위한 데이타에 대한 분석과, 오토 인코더에 대한 기본 원리 그리고 오토 인코더에 대한 샘플 코드를 살펴보았다. 이제 실제 모델을 만들기에 앞서 신용카드 거래 데이타를 학습에 적절하도록 전처리를 하도록한다.데이타양이 그리 크지 않기 때문에, 데이타 전처리는 파이썬 데이타 라이브러리인 pandas dataframe을 사용하였다. 여기서 사용된 전처리 코드는 https://github.com/bwcho75/tensorflowML/blo..

Wide and deep network 모델 활용하기

Wide & deep model 알아보기 조대협 (http://bcho.tistory.com)Wide & deep model 이글에 설명된 예제는 https://www.tensorflow.org/tutorials/wide_and_deep 문서에 있는 코드를 활용하였습니다. 음식 검색 키워드와 검색 결과를 학습 시킨 후에 이 결과를 기반으로 사용자에게 음식을 추천해주는 서비스가 있다고 하자.Monetization and Wide model (기억과 와이드 모델)로지스틱 회귀 모델을 이용하여 추천 알고리즘을 작성하여 학습을 시킨 경우, 학습 데이타를 기반으로 상세화된 예측 결과를 리턴해준다. 예를 들어 검색 키워드 (프라이드 치킨)으로 검색한 사용자가 (치킨과 와플)을 주문한 기록이 많았다면, 이 모델은 (..

Hashtable의 이해와 구현 #1

해쉬 테이블의 이해와 구현 (Hashtable) 조대협 (http://bcho.tistory.com) 기본적인 해쉬 테이블에 대한 이해 해쉬 테이블은 Key에 Value를 저장하는 데이타 구조로, value := get(key)에 대한 기능이 매우매우 빠르게 작동한다. 개발자라면 자주 쓰는 데이타 구조지만, 실제로 어떻게 작동하는지에 대해서 정확하게 알고 있지는 모르는 경우가 많다. 이 글에서는 해쉬 테이블에 대한 기본적인 구조와, 구현 방식에 대해서 설명 하도록 한다. 해쉬 테이블의 기본적인 개념은 다음과 같다.이름을 키로, 전화 번호를 저장하는 해쉬 테이블 구조를 만든다고 하자. 전체 데이타 양을 16명이라고 가정하면 John Smith의 데이타를 저장할때, index = hash_function(“..

dynamic array resizing에 대해서.

알고리즘쪽을 파다보니 재미있는게, 예전에 알았던 자료 구조도 구현 방식등에 대해서 다시 되짚어 볼 수 있는게 좋은데. (그간 생각하던 구현 방식과 다른 방식도 종종 나와서.) 보통 메모리 문제 때문에 불확실한 데이타 크기를 가지는 데이타 구조는 LinkedList를 사용하는게 유리하다고 생각했는데, 내용중에, 배열을 사용하고, 배열이 다 차면 그크기를 늘리는 (새롭게 더 큰 배열을 만들어서 기존 배열 내용을 복사해서 대처 하는것) 방식 (Array Resize)를 봤다. 일반적인 방식이기는 하지만 메모리 소모량이나 배열 복사 속도 때문에 그다지 바람직하다고 생각 안하고 있었는데, JDK내의 Map 클래스의 구현 부분을 보니, 실제로 Map 클래스에서도 array resize를 사용하고 있다. (출처 : ..

알고리즘 관련 유용한 사이트 모음

튜토리얼 포인트자료 구조에 대한 설명과 코드들을 간략하게 잘 정리해 놓음http://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm 코세라 프린스턴 알고리즘 강의https://class.coursera.org/algs4partI-010 코세라 데이타 구조에 대한 강의 (그래프 구조에 대한 문제가 잘 정리되어 있음)https://class.coursera.org/algs4partI-010 알고리즘에 대한 일반적인 설명 (Algorithm 4th edition)http://algs4.cs.princeton.edu/ Octree와 QuadTree에 대한 설명 (게임에서의 응용)http://www.gamedev.net/page/r..

그래프 노드간 연결 파악을 위한 Dynamic Connectivity 알고리즘

동적 연결 알고리즘 (Dynamic Connectivity) 조대협 (http://bcho.tistory.com) 요즘 알고리즘이 대세라 기초를 다지는 차원에서 다시 알고리즘을 보고 있는데, 오늘은 동적 연결 알고리즘에 대해서 공부한 내용을 간략하게 정리해본다. 동적 연결 알고리즘은 노드끼리 연결이 되어 있는지를 찾는 알고리즘이다.각 도시간에 연결이 되어 있는지, SNS에서 친구끼리 서로 연결이 되어 있는지와 같은 연결성만을 판단한다. 예전에 이러한 문제를 그래프 형태의 자료구조를 이용해서 풀려고 했는데, 여기서 문제의 핵심은 노드 A와 B가 연결되었는지만 판단하면 된다. 즉 자료 구조상에서, 어떤 노드가 어떤 노드와 인접해 있는지등은 표시할 필요가 없다. 아래 그림을 보자, 아래 그림에서 1과 5는 연..

나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개

나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개조대협 (http://bcho.tistory.com) 지금 부터 소개할 알고리즘은, 머신러닝 알고리즘 중에서 분류 알고리즘으로 많이 사용되는 나이브 베이스 알고리즘이다. 배경 지식나이브 베이스 알고리즘을 이해하려면 몇가지 배경 지식이 필요하다. 베이스 정리먼저 베이스 정리를 보면, 매개 변수, x,y가 있을때, 분류 1에 속할 확률이 p1(x,y)이고, 분류 2에 속할 확률이 p2(x,y)일때, p1(x,y) > p2(x,y) 이면, 이 값은 분류 1에 속한다.p1(x,y) < p2(x,y) 이면, 이 값은 분류 2에 속한다.나이브 베이스 알고리즘은 이 베이스의 정리를 이용하여, 분류하고자 하는 대상의 각 분류별 확..