Non negative Matrix Factorization ( NMF ) 하나의 배열을 비음수( 양수 + 0 )으로 구성된 두개의 배열로 인수분해 하는 방법 A( M by N ) = W(M by K) X H( K by N ) W,H 행렬에 임의의 값을 넣는다.( ?(T) = Transpose ) W = ||W*H-A|| H = ||H(T)W(T)-A(T)|| W*H 가 A에 가장 가까워질때까지 위 연산을 반복한다. NMF는 다변향 분석 알고리즘의 하나이고,선형대수학에서 행렬 X.. 알고리즘 2009.05.20
LSH( Locality sensitive hashing ) 첨언 : 글을 쓰다 보니 LSH를 어디에 사용하는지 쓰지 않은것 같다. LSH는 문서를 몇개의 signature( 고유값 )으로 표현하는 방법이다. 일반적으로 문서 하나가 100여개의 단어로 구성되어 있다면 이를 벡터로 표현했을때 100차원이라고 볼수 있다. 이것은 제한된 크기 n차원으로 줄이는 기술이다. n이 크면 클수록 원본 데이터에 유사해지지만 속도가 느려지고 작아지면 속도가 빨리진다. 물론 차원을 줄여 속도가 빨라진다고 퀄리티까지 형편 없어지면 알고리즘이고 불리지도 않았을 것이다. 차원이 줄어들면 문서의 중복 제거나 클러스터링이 가능할것 같다. 구글에서는 이기술을 map & reduce와 접목시켜 개인화된 뉴스 클러스터링을 한다고 한다. Locality sensitive hashing : 고차원 .. 알고리즘 2008.10.07
Expectation Maximization EM 알고리즘은 확률 모델에서 MLE parameters를 찾기위해 사용한다. EM 알고리즘은 두단계를 거치는데 첫번째 단계는 E단계( Expectation step ) 두번째 단계는 M단계( Maximization step )이다. running 과정에서는 이 두 단계가 계속 반복된다. 간단한 예를 살펴보면 1. 초기값 설정 2. 반복 과정 2.1 E-STEP : 주.. 알고리즘 2008.09.15
index-compression( relative-10 ) carryover12.pdf NUMBER OF LENGTH OF NUMBER OF SELECTOR CODES EACH CODE (BITS) UNUSED BITS a 30 1 0 b 15 2 0 c 10 3 0 d 7 4 2 e 6 5 0 f 5 6 0 g 4 7 2 h 3 10 0 i 2 15 0 j 1 30 0 TABLE-1 possible next selector values Current selector a b c d e f g h i j a 0 1 2 3 b 0 1 2 3 c 0 1 2 3 d 0 1 2 3 e 0 1 2 3 f 0 1 2 3 g 0 1 2 3 h 0 1 2 3 i 0 1 2 3 j 0 1 2 3 TABLE-2 relative-10은 TABLE-1에서처럼 총.. 알고리즘 2007.12.14
gamma code number unary code length offset r code -------------------------------------------------------------------------------------- 0000 0 0001 10 0 0 0002 110 10 0 10,0 0003 1110 10 1 10,1 0004 11110 110 00 110,00 0009 1111111110 1110 001 1110,001 0013 1110 101 1110,101 0024 11110 1000 11110,1000 0511 111111110 11111111 111111110,11111111 1025 11111111110 0000000001 11111111110,0000000001 0009 11111.. 알고리즘 2007.11.23
ternary search tree http://www.ddj.com/windows/184410528 당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가 존과 로버트는 binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한 ternary search trees로 시작할 것을 제안했다. -- 당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가 .. 알고리즘 2007.10.31
Bayes' theorem http://en.wikipedia.org/wiki/Bayes'_theorem 첫번째 바구니 : 초콜렛 쿠키(10), 일반쿠키(30) 두번째 바구니 : 초콜렛 쿠키(20), 일반쿠키(20) 쿠키를 하나 뽑았는데 일반 쿠키가 나왔다. 첫번째 바구니에서 뽑았을 확률 조건부 확률로 표현하면 일반쿠키를 선택했는데 첫번째 바구니일 확률 P(첫번째바구니 | 일반쿠키.. 알고리즘 2007.06.03
비터비(viterbi) 알고리즘 참고 : http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html http://en.wikipedia.org/wiki/Viterbi_algorithm 대학원때 POS(Part of speech tagging) 태거를 구현할때 처음 접했던 알고리즘인데 태거이외에도 많은 곳에서 사용되는듯하다. HMM이 등장하는 곳에서는 처리 속도때문에 어김없이 따라 나오는 알고.. 알고리즘 2007.05.24
내가 이해한 색인 압축(index compression) 요즘 관심있게 보는 색인 압축 알고리즘은 다음 세가지이다. simple-9 relative-10 carryover-12 뒤에 붙는 숫자는 32bit 안에 몇가지 방법으로 데이터가 들어가는지에 대한 것이고 각각의 이름은 상대적인 의미에서의 naming 같다. simple-9의 경우 이전에 살펴본 적이 있기 때문에 굳이 여기서 다시 설명은 하지 않.. 알고리즘 2007.03.31
색인 압축 기법 - (simple-9) -------------------------------------------------------------------------- | 압축키 | encoding할수 있는 데이터 수 | 각 코드의 길이 | 쓰지 않는 코드 길이 | |------------------------------------------------------------------------- | a | 28 | 1 | 0 | | b | 14 | 2 | 0 | | c | 09 | 3 | 1 | | d | 07 | 4 | 0 | | e | 05 | 5 | 3 | | f | 04 | 6 | 0 | | g | 03 | 7 | 1 | | h | 02 .. 알고리즘 2007.01.24