유클리디안 유사도 – Euclidean Similarity

유클리디안 유사도는 원래 유클리디안 거리(Euclidean distance)라고 말하는 것이 맞는 것 같습니다. 유클리디안 유사도는 다소 이상한 단어의 조합이라는 생각이 듭니다. 하지만 유클리디안 유사도라는 말도 많이 통용되므로 이 포스트에서도 그냥 그렇게 하기로 하겠습니다.

유클리디안 유사도(Euclidean similarity)는 유클리디안 거리를 구해서 두 벡터의 유사도로 사용한다는 뜻입니다.

유클리디안 거리는 기하학적으로 볼 때 두 점의 직선거리를 구하는 것입니다.  또는 선형대수에서 주로 다루는 벡터 스페이스(Vector space)라고 불리는 선형 공간에서도 동일하게 최단 거리를 구하는 것을 말합니다.

코사인 유사도를 설명할 때 언급한 적이 있습니다만 유사도는 2개의 데이터만 가지고 계산해서 결과값을 뽑아내도 그것만으로는 아무짝에도 쓸모가 없습니다.

세상에 사람이 둘 만 남았다면 두 사람은 서로 닮은 걸까요? 안 닮은 걸까요? 모릅니다.

유사도는 다음과 같은 방식으로 주로 사용합니다.

  1. 여러 개의 데이터에서 주어진 것과 가장 가까운 것이 어떤것인가?
  2. 여러 개의  데이터에서 가장 가까운 것들끼리 묶어보자

유클리디안 거리는 데이터마이닝이나 기계학습에 익숙하시다면 K-means (K민즈, K중심값, K평균 이라고 번역합니다) 같은 것에서 사용하는 것을 본 적이 있을 것입니다. 유사도라는 것이 사실은 거리를 측정하는 방법(distance measurement)일 수 밖에 없습니다. 거리를 측정하는 방법을 어떤 것을 쓰느냐에 따라 이름을 무슨 무슨 유사도 이렇게 “유사도”라는 단어를 붙여서 부릅니다.

유클리디안 거리를 구하는 방법은 간단하고 매우 쉽습니다.
피타고라스 정리를 쓰면 됩니다.

위키피디아를 보면 그림을 이렇게 설명해 놨습니다.

간단 한 수식이 있지만 그림으로 보니 눈이 아프군요.

그림에서 p와  q의 유클리디안 거리는 p와 q의 직선거리를 구하면 되는 것이고 가운데 만들어진 삼각형이 직각삼각형이니까 피타고라스 정리를 쓰면 빗변의 길이, 즉 대각선의 길이를 구할 수 있습니다. 이 대각선의 길이가 유클리디안 거리입니다.

결론은 삼각형의 빗변의 길이를 계산하면 됩니다.

참고로 피타고라스 정리가 3차원 이사의 고차원에서도 되는 건지 헷갈릴 수 있겠습니다.  당연히 3차원 이상에서도 적용이 됩니다.  3차원, 4차원, 5차원, …, R차원 다 됩니다.

수학자들이 증명해 놓은 것이 있습니다. 그냥 믿고 쓰시면 됩니다.

5차원인 경우를 예를 들어서 설명하면
아래와 같이 2개의 5차원 벡터가 있다고 하고

a = (1, 2, 3, 4, 5)
b = (2, 3, 4, 5, 6)

벡터의 멤버수가 5개씩이므로 둘 다 5차원 벡터입니다.  차원이 다르면 안됩니다. 맞춰 줘야지요.

각각 차원(축)을 맞춰서 순서때로 빼준 다음에 제곱해서 더한 다음에 루트를 씌우면 됩니다.

1번째 차원: 1 – 2를 계산해서 제곱 = 1
2번째 차원: 2 – 3을 계산해서 제곱 = 1
3번째 차원: 3 – 4를 계산해서 제곱 = 1
4번째 차원: 4 – 5를 계산해서 제곱 = 1
5번째 차원: 5 – 6를 계산해서 제곱 = 1

다 더한 다음에 루트

sqrt(1 + 1 + 1 + 1 + 1)

답은 2.236068 입니다.

R코드로는 이렇게 하면 됩니다.

추가로 유클리디안 거리는 양적인 것을 기반으로 하는 것이라서 축의 스케일이 맞지 않으면 이상한 측정이 됩니다.  축의 스케일을 맞춰야 할지 말아야 할지는 그때 그때 다릅니다.

이런 말이 나오면 항상 골치만 아픕니다만 어쨌든 뭐든 쉽게 쓸 수 있는 것은 없는 것 같습니다.

예를 들면 이런 경우입니다.

a = (1, 2, 3000000, 4, 5)
b = (2, 3, 4000000, 5, 6)
c = (3, 4, 5000000, 6, 7)

3번째 차원, 3번째 축의 값에 의해 가장 큰 영향을 받습니다. 다른 차원의 값들은 구실을 못하게 됩니다.

기회가 되면 스케일을 맞추는 여러가지 방법도 적어 보겠습니다.

무선통신서비스 가입회선 통계

과학기술정보통신부 홈페이지에 방문하면 무선통신서비스 가입회선 통계 데이터를 제공하고 있어서 아무나 받아서 사용할 수 있습니다.   수작업으로 하는 것이라서 이전 달의 자료를 다음 달 말일 정도에 업데이트 해줍니다.

그러니까 2월달 자료는 3월말경에 업데이트가 됩니다.

자료가 올라오는 시기가 1개월 가까이 차이가 있어서  이전 달의 내용을 달이 바뀌고 나서 바로 볼 수 없는 것이 흠입니다만
없는 것 보다는 훨씬 낫습니다.  PDF로 제공하는 것도 좀 불편합니다. 포맷을 바꾸기가 조금 번거롭습니다.
엑셀 파일로 해주셨으면 더 좋았을텐데요.

이 자료 얘기를하는 것은 최근에 업무와 관련해서 통신서비스 관련 분석 작업을 조금하게 되었는데 작업을 하고난 김에 저 데이터를 예제로 간단한 시각화 예제를 만들어 보기로 했습니다.

실제 업무에서는 저 데이터와 다른 데이터를 결합해서 확인하거나 하는 것이지만 이 포스트에서는 저 데이터만 이용해서 아주 간단한 EDA작업을 해보겠습니다.

2018년 3월까지의 데이터를 사용했습니다.

이 글을 쓰는 시점은 2018년 5월입니다

소스 코드

플롯(plot)을 그리는데 ggplot2를 사용했고 데이터 랭글링(data wrangling)은 dplyr와 tidyr를 사용했습니다. tidyverse 패키지에 몽땅 같이 들어 있으므로 한 번에 묶음 패키지를 통째로설치하고 싶으면  tidyverse만 설치하면 됩니다.

tidyverse는 ggplot2를 포함한 몇개의 유용한 패키지 를 묶어 놓은 것입니다.

아래 코드에 주석을 적어 두었습니다. 그래서 코드 설명은 따로 하지 않겠습니다.  dplyr와 tidyr에 익숙하지 않은 분들은 패키지 사용법을 잠깐 살펴봐야 할 수있습니다.  이것도 여기서는 설명하지 않겠습니다.  너무 길어집니다.

전체 코드는 다음과 같습니다.

한글 변수도 몇개 사용했고 줄이 길어서 조금 복잡해 보일텐데요. 복사해서 sublime text 같은 편집기나 Rstudio에서 보세요. 원래 한글 변수명은 잘 안쓰지만 한 번 해보고 싶었습니다.  가끔은 일탈이 필요해요.

에어리어 플롯 – area plot

가입유형별 시계열 에어리어 플롯(time-series area plot)입니다. 케이크 차트(cake chart)라고도 부릅니다.

월별 집계이기 때문에 월별로 가입유형의 변화추세를 볼 수 있습니다.
신규가입자와 기기변경이 많네요.
이전 달에 비해서 큰 폭으로 늘었다는 것을 볼 수 있습니다.

시계열 플롯 – time-series plot

통신사별 시계열 라인플롯입니다.  통신사별, 월별로 가입자를 모두 취합했습니다.

SKT의 가입자가 월등히 많은 것을 볼 수 있습니다.  증가폭도 큽니다. 다른 통신사와  MVNO도 큰폭으로 상승하긴 했습니다.

2월에 가입자가 조금 적은데 어떤 이슈가 있었거나 3월에 있을 이벤트를 사람들이 기다렸을 가능성이 큽니다.
봄 철에는 여러 이벤트가 많은 편인데 새모델이 출시된다거나 요금할인이 된다거나 또는 대학신입생들의 입학 기념품이거나 신학기 행사이거나요. 그래서 2월에는 가입을 하지 않고 3월까지 기다렸을 가능성이 큽니다.
반대로 해석하면 기업들은 통상 3월부터 이벤트를 많이합니다. 주변정보 탐색을 해보지 않았고 부가정보가 없어서 모르지만 상식만으로 그렇게 추측해 봅니다.

위의 가설은 실제로 데이터를 확인하거나 서베이를 해서 확인해 보지 않았기 때문에 논리에 기반한  소설일 뿐입니다

바 플롯 – bar plot

색깔은 기본값으로 막 칠했습니다. 알록달록하게. 나이 먹으면 알록달록한게 좋아집니다.

그냥 2018년 3월의 가입자수를 통신사별로 수치 비교 하기 위해 바 플롯을 그린 것입니다.  바 플롯(bar plot)이라고도 하지만 그냥 막대 차트(bar chart)라고 더 많이 부릅니다. 어쨌는 플롯을 보면 SKT의 가입자가 월등히 많네요.

모자이크 플롯 – mosaic plot

통신사별 구분별로 모자이크 플롯을 그렸습니다.
2차원으로 된 것으로 빈도의 비중을 비교할 때 유용한 플롯입니다.

크기가 큰 것이 많은 것입니다. 사각형의 크기를 보고 비중을 보면 됩니다.

아 쉽다. 전 이런게 좋아요. 쉬운거

그림을 보면 SKT의 기기변경 사용자가 가장 많습니다. 그 다음은 비교하기 애매하지만 KT의 기기변경과 SKT의 신규가입자가 많은 것 같습니다.
MVNO는 신규가입자의 비율이 매우 높습니다. (왜 그럴까요??)
SKT의 기기변경 비율이 다른 통신사에 비해서 높습니다.
KT는 신규가입자의 비율이 다른 통신사에 비해서 높습니다.

2018년 3월은 SKT에 기기변경으로 가입한 사람이 많고 KT는 처음 진입한 사람이 많다고 볼 수 있습니다.  모든 통신사에 걸쳐 처음 가입했다고 하면 이제 막 성인이 되었거나 외국에서 왔거나 일 것 같습니다.

어쨌든 뭐로 보든 SKT 가입자가 많군요. SKT는 통신사 중에서 무선 점유율이 가장 높은 회사로 알려져 있습니다.
여전히 장사 잘되나 봅니다.

마지막으로 소스코드에서 카이제곱 검정(chi-square test)을 했습니다만 별 의미 없는 것입니다.  결과는 귀무가설 기각으로 통신사 구분과 가입종류의 구분은 서로 독립이 아니다. 즉 “영향이 있다” 정도입니다. 이건 가설검정을 하지 않아도 모자이크 플롯으로 봐도 쉽게 알 수 있긴합니다.  하지만 검정법을 사용해서 뭐든 확실하게 한 번 보는게 좋습니다.

여기까지입니다.
사실 너무 대충 하다만 EDA입니다만 데이터를 보고 요약을 정리해 나가다 보면 뜻하지 않는 인사이트를 발견하기도 합니다. 물론 이 데이터는 집계가 너무 많이 되어 있어서 주변정보가 없는 상태에서 특별한 인사이트를 얻기는 어렵습니다.

데이터는 아래 링크를 클릭해서 받으세요.

파일 다운로드: 2018-3-mobile-user-data

Windows 10에서 Rcpp 설치 오류 해결 방법

저는 여러 OS를 사용해서 작업을 여기저기에서 난잡하게 하는 편입니다.  버전도 다 다르고 설치된 패키지들도 달라서 작업을 하기전에 패키지를 종종 재설치하곤 합니다.

Windows 10에서 R로 작업을 하던 중에 tidyverse를 업데이트했는데 그 뒤로 ggplot2를 로딩하니 Rcpp가 없다고 에러가 뱉어내더군요. ggplot2는 그 전까지 이상없이 쓰던 것이었습니다.

메세지를 보면 Rcpp가 없다는 것인데 Rcpp를 분명 예전에 설치했었는데 이상하다 싶었습니다. 어쨌든 Rccp 재설치를 시도했더니 이상한 에러가 나더군요.

디렉토리를 이동시키지 못했다는 메세지인데
위의 디렉토리는 관리자 권한이 필요한 디렉토리가 아니기 때문에 권한 문제는 아니었습니다.

그래서  검색을 해서 찾아보니 anti-virus의 실시간 탐지가 방해를 한다는 군요.
anti-virus 소프트웨어를 일시 중지하고 Rcpp를 설치하니 그 뒤로는 잘 됩니다.

tidyverse나 ggplot2 업그레이드 후에 ggplot2가 로딩이 되지 않거나 하면 참조하세요.

검색어 자동완성 서비스

구글, 빙, 네이버, 다음과 같은 검색포털에 접속해 보면 상단에 검색창이 있습니다.

이 검색창에 정보를 찾기 위해서 검색어를 입력하는데 이때 키보드를 타이핑할 때마다 검색창 바로 아래에 지금까지 타이핑한 글자들로 구성된 검색어 목록을 보여주고 선택을하면 검색어를 다 입력해주는  검색어 자동완성 기능이 있습니다.

검색어를 타이핑하다 말고 마우스나 키보드로 완성된 검색어를 입력할 수 있게 해주기 때문에 “검색어 자동완성”이라고 합니다.

데이터사이언스와 크게 관련이 없긴 하지만 검색어 자동완성에 대한 내용을 적어보겠습니다.

사실  추천되는 검색어 목록을 만드는 것이 데이터사이언스와 관련이 많이 있습니다만 내용이 너무 길어지니 이것은 나중에 설명하겠습니다.

앞서 설명했지만 “검색어 자동완성”은사용자가 검색어를 힘들게 다 입력하지 않아도 입력 도중의 단어로 시작하거나 또는 포함하는 단어들을 목록으로 보여주고 선택해서 검색어를 바로 완성하게 해주는 사용자 친화적 (user friendly) 기능(서비스)입니다.

아래의 그림처럼 구글에서 검색어를 입력하면서 볼 수 있는  이런 것입니다.

네이버, 다음, 빙, 야후, 덕덕고(duckduckgo)와 같은 검색포털과 각종 온라인 쇼핑몰, 오픈 마켓, 온라인 서점에서도 모두 볼 수 있습니다.

검색어 자동완성은 서비스와 사용자의 행동 유도 관점에서 각각 장단점이 있습니다.   (행동과학의 관점입니다)

장점

  • 사용자 편의성
    • 검색서비스를 이용하는 사람들이 타이핑이 불편하거나 느린 경우 편하게 원하는 검색어를 입력할 수 있게 해줍니다.
    • 사용자가 오타를 입력해서 검색결과를 찾지 못하는 것을 방지해줍니다
    • 검색어가 잘 생각나지 않을때 단어의 파편을 입력해서 목록을 보고 기억나지 않은 또는 부분적으로만 기억나는 단어를 입력해서 검색어를 입력할 수 있습니다.
    • 다른 사용자가 많이 입력하는 검색어가 제안되기 때문에 사람들이 많이 입력하는 최신 트렌드의 검색어를 자신도 입력해서 최신 자료를 입수 할 수 있습니다.
  • 포털의 이득
    • 사용자가 찾을 것이 없어도 뭐라도 제안을 해서 검색을 하게 만듭니다. 즉 사용자 입력할 검색어를 마땅히 기억하지 못해 검색 포털을 떠나는 것을 방지할 수 있습니다.
    • 상업적으로 유리한 검색어를 자동완성에 넣어서 상업적 이득을 볼 수 있습니다.

단점

  • 사용자의 새로운 경험 박탈
    • 사용자의 입장에서는 검색어를 잘못 입력해서 뜻하지 않게 좋은 자료나 괜찮은 자료를 찾을 수 있는 예외적인 경험을 할 수 있는 기회가 줄어듭니다.  사용자가 실수할 것을 방지해주니 장점이라고 볼 수도 있긴합니다.
    • 검색어는 인기 검색어나 사람들이 자주 입력하는 단어를 기반으로 추천되기 때문에 다른 사람들도 많이 검색하는 단어를 사용하기 때문에 정보 입수의 다양성에 반하게 됩니다. 일종의 개성없는 정보의 편식을 만듭니다. 반면 장점이기도 하겠습니다.

사용자의 입장에서는 어쨌든 단점보다는 장점이 더 많은 것 같습니다. 편하니까요. 하지만 가끔 검색어 자동완성이나 인기검색어로 정보의 섭취를 유도당하고 있는 것은 아닌지 생각해 봐야 합니다.

자동완성에 나오는 목록에 광고 목적으로 목록에서 위에 위치하도록 되어 있는 것도 있다는 것을 아셔야 합니다.

이제 구현 또는 구축에 대한 것을 적어보겠습니다. 기술적으로 보면 자동완성 시스템을 만들어서 운영하는 것은 생각보다 녹녹하지 않습니다.  자동완성은 포털 뿐만 아니라 소셜네트워크 서비스에서도 볼 수 있고 쇼핑몰, 인터넷서점, 그리고 사내 인트라넷 같은 곳에서도 볼 수 있습니다. 하지만 구현되어 있는 것도 다르고 각각의 상황에 따라 운영 방식이나 상태도 다를 것입니다.

구현이나 운연에 관련된 부분을 Frontend, Backend,  Data processing 3단계로 나눠서 설명해 보겠습니다.

Frontend 부분

Frontend 부분은 당연히 Javascript로 합니다. Ajax입니다. 사용자가 키보드를 타이핑할 때마다 backend로 사용자가 입력 중인 단어를 보내서 제안할 검색어 목록을 받아서 화면에 뿌려줍니다.
주의할 점은 사용자의 타이핑이 매우 빨라서 제안된 검색어가 화면에 보여지기 전에 사용자가 빠르게 타이핑을 하면 기존에 타이핑했던 요청(backend call)이나 지금 막 하고 있었던 자동화면창 표현(rendering)을 중단하고 다시 backend 호출을 하는 트릭이 필요합니다. 그렇게 하지 않으면 사용자에게 불편한 경험을 주게 됩니다. (눈으로 볼 때 거리적 거려서 불안감을 줍니다)

예를들어 “자동완성”이라는 검색어를 사용자가 포털의 검색창에 입력한다면 사용자는 다음과 같은 순서로 빠르게 키보드를 쳐나가게 됩니다.

  1. 자도
  2. 자동

타이핑이 빠른 사람이라면 1 ~ 2초이내에 12번의 타이핑을 하게 됩니다.  12번의 backend 호출이 일어나게 되는데 사용자가 타이핑을 멈추거나 잠시 쉴때까지는 불필요한 호출이기 때문에 생략하는 기술이 필요합니다.

물론 요즘은 javascript 라이브러리들이 잘 구현된것이 많아서 잘 된 것을 찾아서 갖다 쓰면 됩니다.
jquery autocomplete: https://jqueryui.com/autocomplete/
하지만 좀더 빠르고 잘 작동하는 것을 만드려면 직접 만드는 것이 좋습니다.

Backend 부분

backend 부분은 다양한 방법으로 구현이 가능하고 사이트의 규모나 동시 접속하는 사용자의 수같은 상황에 따라 쓸 수 있는 방법이 달라집니다.  여러 방법을 선택할 수 있습니다.

Javascript 색인 방식

몇개의 library가 잘 공개된 것이 있습니다. 이 방식은 Javascript로 자동완성에 사용할 검색어를 모두 N-gram 색인 구조로 만들어서 웹브라우저에 로딩한 후 사용하는 방식입니다.
데이터의 사이즈가 커지면 성능저하가 심하고 검색어 데이터가 대량(수천만 또는 수억)이 되면 아예 불가능 합니다.
웹페이지를 로딩할 때 데이터를 한꺼번에 로딩해야 하기 때문에 웹페이지 렌더링을 방해하거나 또는 렌더링이 된 후에도 초기에 잠깐 작동하지 않는 불편함이 생깁니다.
데이터가 적을 때 씁니다. python 문서화 패키지인 sphinx 같은 것이 static html에서 문서검색을 할 수 있게 하기 위해서 이런 것을 사용하는 것을 볼 수 있습니다. 일부 위키시스템도 이 방식을 사용합니다.
이 경우는 사실 backend가 하는 일이 별로 없긴합니다.

데이터베이스의 like query를 이용하는 방법

데이터베이스에 대놓고 like 구문을 보내서 검색하는 무식한 방식입니다. 무식하지만 쉽고 구현하기 쉽습니다. 데이터가 적고 접속 사용자도 적을 때 막 사용할 수 있는 방법입니다.

물론 DB의 full-text 검색 기능을 이용하거나 memory table 기능을 이용하거나 아니면 in-memory 데이터베이스등을 이용해서 성능을 개선할 수 있겠지만 대용량 트래픽을 받아야 하는 상황이면 DB가 이런 과부하를 견디기 어렵습니다.

유사한 방법으로 Sphinxsearch 같은 것을 쓰고 cache 를 덧대주는 방법도 있겠습니다.  그런데 Sphinxsearch는 검색엔진입니다.

Static file을 이용하는 방법

모든 예상되는 입력에 대해서 json file같은 것을 static 모두 생성(generation) 한 후에 static content server에 올려놓고 frontend에서 요청이 오면 이 파일을 그대로 당겨서 전달하는 방식입니다. 과거 어떤 포털이 이 방식을 사용했다고 합니다. 너무 무식하긴 하지만 성능은 괜찮은 방법입니다.

이것도 backend에서 하는 것은 요청한 입력에 대한 맞는 파일을 찾아서 읽은 후에 입력한 키워드에 맞는 목록 데이터를 던져주면 됩니다.

NoSQL을 이용하는 방법

memcache를 쓰거나 NoSQL 중에 반응속도가 빠른 것을 마련하고 static file 생성하는 방식처럼 모든 입력에 해당하는 키워드와 그 키워드들의 조합파편을 key로 하고 value에 검색어 제안목록을 넣어두고 요청이 올 때마다 빼서 던져주는 방식입니다.
저는 안해봐서 잘 모르겠습니다만 성능은 괜찮다고 하는 것 같습니다. 솔직히 이렇게는 안하고 싶습니다.  메모리 효율이 좀 안좋을 것 같습니다.

트리 구조(tree structure)를 이용한 대몬(Daemon)을 사용하는 방법

가장 많이 쓰이는 방법입니다. 성능도 좋고 추가 기능을 넣을 수가 있기 때문입니다. 과거에는 이런 대몬(daemon)을 직접 개발해야 하는 것이 상당히 어렵고 고통이었지만 지금은 좋은 오픈소스가 있습니다.

이 방식은 트리 자료구조(알고리즘) 중에 적합한 것을 선택해서 빠르게 HTTP 리턴을 할 수 있는 경량 웹서버를 만드는 것입니다.  Frontend에서 요청이 오면 트리탐색을 해서 트리의 하위 노드들을 모두 취합(또는 적당히 정해진 갯수만 취합해서)해서 자동완성 제안 목록을 만들고 트리 노드에 붙어 있는 value(score같은 것입니다)를 보고 역순 정렬을 하거나 해서 검색어 추천 목록 정해진 갯수만큼 뽑아서 리턴합니다. 보통 리턴해줘야 하는 자동완성 검색어 목록은  20 ~ 30개이면 됩니다.

트리 자료 구조는 보통 Trie나 FSA(Finite State Automata)를 사용하거나 유사한 것을 사용합니다.  요즘은 더 괜찮은 것들이 있을지도 모르겠습니다.

구현할 때 몇가지를 고려해야 합니다.

  • 자체 캐시(Cache)
    • 자체 캐시를 지원해야 합니다. 자동완성을 위해서 backend의 앞쪽에 캐시를 붙여서 성능강화를 할 수도 있습니다만 자료구조내에서 데이터를 탐색하는 것도 로드가 발생하기 때문에 LRU같은 간단한 캐시 기능을 넣어야 합니다.
  • 랭킹(ranking)
    • 제안할 목록의 랭킹도 고려해야 합니다.  보통 검색어 제안 목록을 가나다 순이 아니라 스코어를 주고 그 순서로 보여주는 것이 사용자 경험상 더 낫기때문입니다.
    • 그래서 빠른 소팅(sorting) 라이브러리를 사용하거나 만들어야 합니다.
  • 메모리 페이징 문제
    • 추천하는 검색어 목록을 모두 메모리에 가지고 있을 수 있다면 그렇게 해야 합니다. 목록을 저장하기 위해서 디스크를 사용하면 페이징(paging)을 할 때 성능저하가 크기 때문에 가능한 메모리를 최대한 활용해야하고 디스크를 쓰더라도 SSD를 써야합니다.
  • 클러스터링
    • 디스크를 사용하지 않고 메모리에서만 처리하겠다고 하면 데이터가 많아질때 여러 서버에 분산하는 것이 필요합니다.  그런데 트리구조는 분산하기 굉장히 어렵습니다.
  • 온라인 업데이트
    • 데이터를 주기적으로 갱신해 주어야 하는데 가동중인 대몬을 멈추고 업데이트하기 보다는 대몬을 가동시킨 상태에서 데이터를 업데이트를 해야합니다.
    • 물론 로드밸런서(load balnacer) 같은 것을 두고 로드밸런서 뒤에 붙어 있는 서버의 대몬을 순차적으로 재시작해가면서 데이터를 갱신하는 방식을 사용할 수도 있습니다.  피곤하지요.

위의 것들은 구현할 때 고려할 내용이긴 하지만 오픈소스를 선택할 때 어떤 기능을 지원하는지 확인하는데 필요할 것 같습니다. 오픈소스 검색어 자동완성 대몬은 몇개 없습니다. 가장 잘 알려진 것은 아래 2개입니다.

  • Linked-in Cleo
  • Duck-duck-go libface

Cleo(클레오)는 라이브러리인데 Cleo를 바로 쓰기 보다는 Cleo-Primer라는 Cleo를 이용한 응용구현체의 소스를 받아서 빌드하고 설명서대로 데이터를 XML로 http 로 부어넣으면 온라인 업데이트가 가능한 방식입니다. Java로 되어 있습니다.  용도에 맞게 쓰려면 표현에 필요한 데이터 항목을 수정해야 하는데 그것 때문에 소스를 조금 수정해 주어야 합니다.

Libface 는 C++로 된 고속 대몬입니다. 써보진 않아서 아는 것이 별로 없습니다만 괜찮다고 합니다.  보기에도 괜찮아 보입니다.

이 외에도 몇개 더 있지만 소스가 오랫동안 개선 되지 않거나 사이트 자체가 사라져서 지금은 기억이 나지 않습니다.

검색엔진을 이용하는 방법

뭐 앞서의 방법이나 사실 다를바가 없지만 검색엔진 중에 자동완성 기능을 지원해주는 것들이 있습니다.
Elastic search도 기능을 지원합니다. 개발을 하지 않아도 되고 색인하는 방법만 익히면 쉽게 사용할 수 있습니다.

type-ahead 방식의 인메모리 자동완성 기능을 지원합니다. type-ahead방식은 뒤에 설명하겠습니다.

이 방법은 성능은 괜찮지만 다른 것에 비해서 무거운 검색엔진을 구동시켜야 한다는 부담이 있습니다. 하지만 대몬을 구동시키는 것이나 검색엔진을 구동시키는 것이나 데이터가 많아지면 부담스럽기는 매한가지입니다.

데이터 프로세싱

검색어 자동완성은 보통 두가지 데이터소스에서 데이터를 끌어와서 자동완성 대몬이나 서비스 구현체에 부어넣습니다.

  • 로그
    • 사용자가 입력한 검색어를 로그에 쌓아두고 빠르게 읽어서 자동완성 구동체에게 빠르게 공급합니다.
  • 데이터베이스
    • 상품의 이름을 쉽게 검색하게 하려는 쇼핑몰 같은데서는 굳이 로그를 뒤질 필요가 없습니다. 상품목록이나 주소, 사람이름 같은 것을 DB에서 내려받아 자동완성 구동체에 부어넣습니다.

로그를 읽어서 로그에서 많이 출현한 키워드에 가중치를 주거나 단순 횟수를 카운트해서 score값으로 쓸 수 있습니다. 로그를 추출할 때는 오타, 특수문자, 성인어 등을 어떻게 처리할지 함께 고민해야 합니다.

데이터베이스에서 꺼내 오는 경우는 상품명 같은것이 될텐데요. 검색어 자동완성도 일종의 추천시스템이라고 봐야하기 때문에 자동완성 목록을 추천할 때 단순히 가나다 순이 아닌 최신 상품이라든가 판매지수가 높은 상품이라든가를 상위에 노출되도록 하는 것을 고민해야합니다.

언어 처리

자동완성의 제안 목록이 되는 데이터를 프로세싱하고 대몬에 탑재할 때 고려할 것이 두가지 정도 더 있습니다.

형태소 분석기를 이용한 자동 띄어쓰기 및 자연어 처리

DB에 있는 상품명이든 사람들이 입력하는 키워드이던 띄어쓰기가 잘못되어 있는 경우가 있습니다. 이렇게 띄어쓰기가 잘 되어 있지 않은 것은 검색엔진에서 잘 다둬주지 않으면 제대로 된 검색결과를 리턴하지 않을 수 있습니다. 형태소 분석기에서 자동 띄어쓰기를 해서 잘 다듬어서 넣어주는 트릭이 필요할 수 있습니다.

자모분리

“빨간구두”를 키보드 한영전환을 하지 않고 두벌식으로 타이핑하면 “Qkfrksrnen”가 됩니다. 입력할 때 사용자가 영한전환을 안해서 생기는 문제인데 사용자의 실수라고 하더라도   “Qkfrks”를 치면 한글 “빨간…”으로 시작되는 검색어를 추천해서 사용자에게 편리함과 작은 감동을 주고 싶다면 데이터의 키를 만들 때 약간의 트릭을 쓰면 됩니다.

한글을 유니코드 처리를 이용해서 자모로 분리할 수 있고 자모에 대한 키보드상에 영문 매핑을 만든 후에 그것을 자료구조의 키로 만들어 주면 됩니다.

자판에서 ㄱ은 r에 매핑되고 ㄴ은 s에 매핑됩니다. 이렇게 변환된 것을 트리구조 또는 검색어 파편의 키로 만들어주면됩니다.

즉 “빨간구두”는 “Qkfrksrnen”를 키로 넣습니다.

대신 이 경우에는 Qkfrksrnen로 들어간 것이 원래 “빨간구두”였다는 것을 알아내야 하기 때문에 자료구조의 value에 함께 넣어두던가 역으로 복원하는 방법을 만들어 두어야 합니다. 번거롭긴 하지만 사용자 편의성을 높이는 방법 중 하나입니다.

위의 경우에 한글을 자모로 분리해서 영문키로 매핑하면 원래 영문으로 된 검색어는 어떻게 되는지 궁금하실지 모르겠습니다. 일부는 한글을 영타로 타이핑하면 영어에도 있는 단어와 겹치는 경우가 있지만 대부부의 경우는 겹치지 않습니다. 그래서 큰 문제는 안됩니다.

뒤로 매칭

“빨간”을 타이핑하면 “볼빨간”을 제안 즉 사용자가 입력한 키워드(입력하다만 키워드)로 끝나는 검색어를 추천해주고 싶을 수 있습니다.

사용자 자료를 찾기 위해서 키워드를 입력하는데 “빨간”은 생각이 나는데 이게 “볼빨간”인지 “눈빨간”, “목빨간” 인지 기억이 안날 수도 있습니다.  사용자를 잘 도와줘야 합니다.

이것은 간단한 방법을 쓰면 됩니다. 자료 구조에 데이터를 넣을 때 키의 문자열을 뒤집어서 넣으면 됩니다.

“볼빨간”을 자료구조에 넣을 때 “간빨볼”로도 하나 더 넣어두면 됩니다.
“볼빨간”이 영타로는 “qhfQkfrks”이기 때문에 다음처럼 해두면 됩니다.

키: value1, value2
qhfQkfrks: 볼빨간, 101
skrfkQfhq: 볼빨간, 100

위의 경우는 자료를 두벌 이상 넣어야 하기 때문에 대몬이 사용하는 메모리가 더 든다는 단점이 있습니다. 자료구조를 좀더 아름답게 고치면 메모리를 절약할 수도 있겠습니다.
런타임에 단어를 뒤집어서 조회를 해도 됩니다만 사용자의 키 타이핑이 빨라서 반응시간을 줄여야 하기 때문에 프로세싱할 때 미리 넣어두거나 대몬자체가 입력을 뒤집어서도 자료를 찾는 기능이 내장되어 있는 것이 좋습니다.

하지만 뒤집어서 넣는 것 보다는 type-ahead 방식이 여러모로 더 낫습니다.

그외  여러가지 잡다한 것들

자동완성은 영어로

  • Auto-completion
  • Auto type completion
  • Type ahead search 또는 type ahead completion
  • Completion suggest

다양 하게 부릅니다. 관련 영문 자료를 찾으시려면 저런 단어로 검색하시면 됩니다.

type-ahead 검색

type-ahead 검색은 auto-completion과 조금 구분이 되어야 합니다. type-ahead가 auto-completion의 일종이긴 하지만 단어의 어떤 부분을 매치해서 찾아주는지의 방법이 다소 다르기 때문입니다.

“검색어 자동완성” 이라는 키워드가 있고 사용자가 매치 되는 검색어의 일부를 타이핑했을 때 제안해 준다고 예를 들어 보겠습니다. 이때 n-gram 방식의 auto-completion과 type-ahead 방식의 차이로 인해서 제안 목록이 달라질 것입니다.

사용자 입력: “검색”

이때 제안할 검색어가 “검색”이라는 단어로 시작하기 때문에 두 방식다 제안이 됩니다.

사용자 입력: “자동”

이 경우에도 두 방식 모두 “검색어 자동완성”을 찾아서 제안해줍니다.

사용자 입력: “색어”

n-gram 방식은 찾아서 제안해 주지만 type-ahead 방식은 찾지 못합니다.
왜냐하면 type-ahead방식은 “검색어 자동완성” 이라는 검색어 제안을 공백을 기준으로 분리해서 앞에서부터 매치되는 것이 있는 것만 찾기 때문입니다. 최근의 검색어 자동완성이라고 하면 모두 type-ahead 방식을 말합니다. n-gram 방식이 효율도 좋지 않고 경우에 따라 제안되는 검색어가 다소 생뚱맞기 때문입니다.

type-ahead 방식을 트리 구조를 내장하고 있는 대몬에서 처리하게 하려면 key rotation이라는 간단한 트릭을 쓸 수도 있습니다.

아래와 같이 특별한 기호를 두고 공백을 기준으로 단어의 위치를 돌려서 모두 넣어준 다음에 찾을 때 찾고 보여줄 때는 원래 것을 보여주면 됩니다.

“검색어 자동 완성”
“자동|완성|검색어”
“완성|검색어|자동”

구현하려면 조금 번거롭기 때문에 오픈 소스들에는 대부분 type-ahead를 지원하기 때문에 특별히 다르게 구현해야 할 것이 아니라면 가져다가 그대로 쓰시는 것이 편할 것 같습니다.

데이터 분석

추가로 얘기하고 싶은 것은 사용자가 입력한 검색어를 데이터 분석의 목적으로 사용하는 것에 대한 것입니다.

사용자가 입력하는 키워드의 수을 세고 여러가지 정보를 붙여서 사용자들의 관심 동향(trend)를 보는 것을 하겠다고하면 검색키워드를 가지고 데이터 프로세싱을 한 후에 이것저거 살펴보고 이용하면 됩니다.

사실 이런 데이터를 들여다 보는 것은 매우 재미있습니다.  시간대와 사회적 이슈에 따라 입력하는 단어들의 경향이 달라지는 것을 볼 수 있으니까요.

하지만 자동완성이 붙어 있게 되면 몇가지 특별한 내용을 가리게 됩니다. 사용자가 어떤 키워드를 잘못 입력하지는 오타를 많이 입력하는지를 자동완성기능이 사용자의 입력을 유도해서 보이지 않게 만들 수 있습니다. 이런 경우에는 자동완성 대몬 자체가 로그를 남겨서 어떤 것들이 조회되는지 봐야 할 수 있고 자동완성의 frontend에서도 사용자가 검색어를 스스로 다 입력했는지 만약 자동완성제안 목록을 선택했다면 몇번째것을 선택했는지 등을 함께 로그에 남겨서 살펴봐야 합니다.

데이터 사이언티스트 60초 설명

데이터 사이언티스트(Data scientist)를 쉽게 설명하는 60초 짜리 짧은 동영상을 트위터에서 발견했습니다.

동영상이 괜찮은 것 같아서 공유합니다.

https://twitter.com/Fisher85M/status/935950475542847491/video/1

data.frame melt 시키기

테이블의 컬럼들을 한 컬럼으로 내리고 값을 따로 빼는 것을 melt(melting)라고 합니다.그 반대로 값을 컬럼으로 올리는  작업을 cast (casting)라고 합니다.
이런 것을 엑셀이나 DB에서는 pivot(pivoting 추축) 이라고도 하고 또 transform이라고도 말합니다.

R과 python에서 melt하는 간단한 코드 스니펫을 올립니다.  Google에 검색을 하면 다 나오는 것이지만 순전히 제 편의를 위해서 올려둡니다.

R은 특히 ggplot2를 사용할 때 facet을 쓰려면 melt된 상태여야 하는 것이 있어서 연습이 필요합니다만 늘 까먹습니다. (전 바보인가봐요)

R코드입니다.
다른 방법도 많지만 R은 reshape2 패키지를 쓰는 것이 편합니다.

python코드입니다.
python은 당연히 Pandas에 melt 함수가 있습니다.

 

RStudio 1.1 릴리즈

지난 10월 9일 RStudio 1.1이 릴리즈되었습니다.

설치를 하고 나면 다크테마로 설정된 달라진 분위기의 애플리케이션 모습을 볼 수 있습니다.

RStudio v1.1

공식 내용은 RStudio blog에서 확인할 수 있습니다.

https://blog.rstudio.com/2017/10/09/rstudio-v1.1-released/

업데이트 내용은

  • 다크테마 지원
  • 데이터베이스 컨넥터 지원 및 탐색 기능
  • 오브젝트 탐색 기능 강화
  • 터미널 탭 지원
  • 기타 소소한 업데이트

입니다.

당연한 것이겠지만 Rstudio server 1.1도 몇가지 기능 개선과 더불어 릴리즈 되었습니다.

 

포항공대 POSTECHX AI 및 데이트사이언스 관련 온라인 무료 강의

포항공대에서 개설한 MOOC(온라인 오픈 강의) 가 있습니다.

http://www.postechx.kr/ko/school/gsit

2017-10-13 기준으로 총 6개의 온라인 강의가 개설되서 진행중입니다. 밑에 강의 정보가 간단히 있습니다. 관심이 있으시면 직접 사이트에 접근해서 수강신청하시면 됩니다. 무료입니다.

Big Data
컴퓨터공학
2017-09-04 ~ 2017-12-03
Big Data
컴퓨터공학
빅데이터의 개념, 기술적인 챌리지와 다양한 접근 방법에 대한 이해를 토대로 빅데이터 문제를 직접 실습하고…

컴퓨터 공학 입문 (SPOC)
컴퓨터공학
2017-09-22 ~ 2017-11-30
컴퓨터 공학 입문 (SPOC)
컴퓨터공학
본 강좌는 포스텍 및 포항제철고 재학생 대상 SPOC (Small Private Online Course…

SDN – NFV
컴퓨터공학
2017-09-04 ~ 2017-12-10
SDN – NFV
컴퓨터공학
SDN 및 NFV 기술을 소개하고 오픈 네트워킹 에코시스템을 구성하는 다양한 오픈소스 프로젝트의 사용방법에…

Software Development Process
컴퓨터공학
2017-09-04 ~ 2017-11-26
Software Development Process
컴퓨터공학
소프트웨어가 개발되는 방법을 공학적인 관점에서 살펴보고 개발 방법론이 시대의 요구에 따라서 어떻게 변해왔고…

Advanced Computer Architecture
컴퓨터공학
2017-09-04 ~ 2017-12-10
Advanced Computer Architecture
컴퓨터공학
컴퓨터 구조 개념들을 깊이 있게 이해하는 것을 목표로 하는 강좌입니다.

Internet of Things
컴퓨터공학
2017-09-04 ~ 2017-12-10
Internet of Things
컴퓨터공학
This course aims at introducing the general concepts and…

Google Cloud Engine IP 대역 알아내기

Google Cloud Engine (줄여서 이하 GCE)로부터 회사의 서비스에 발생시키는 기계적인 트래픽을 알아내기 위해서 GCE의 전체 IP대역을 알아내서 확인해 보려고 했는데 여기저기 검색해 본 결과 DNS lookup을 하면 되는 것을 알아냈습니다.

이렇게 하시면 됩니다.

명령의 결과는 밑에 있습니다.

많지 않은 것 처럼 보이지만 CIDR를 모두 풀어서 IP주소로 바꿔 놓으면 무지하게 많습니다. (구글 스케일. ‘ㅡ’;)

CIDR 형식으로 리턴되기 때문에 start, end 형식으로 바꾸시려면 Python을 사용하던지 해서 CIDR에서 Start IP와 End ip를 추출하면 됩니다. 시간이 되면 간단한 예제를 업데이트 해보겠습니다.

 

오픈소스 Yahoo Vespa

2017년 9월 26일에 Yahoo가 Vespa를 오픈해서 오픈소스로 공개했습니다.

먼저 밑에 프로젝트의 URL을 올려드립니다.
http://vespa.ai/

개인적으로 상당히 큰 사건이라고 생각합니다.

우선 Yahoo가 가진 핵심 기술 중에 절대로 공개하지 않을 것만 같은 것 중에 항상 언급이 되는 것 중에 다섯손가락 안에 꼽히는 것이 Vespa입니다.

하지만 Vespa가 뭔지 대부분의 분들은 모를 것입니다.  간단히 설명하면 Vespa는 원래는 검색엔진이었습니다. 하지만 최초에 만들어지고 Yahoo 내에서 계속 사용하면서 발전시켜서  기능이 많이 확장되었고 성숙하게 발전해서 통합 콘텐츠 처리 플랫폼이 되었습니다.

저도 Vespa를 이용해서 일을 했던 적이 있습니다만 매우 오래전이기 때문에 제가 봤던 것보다는 지금의 버전이 훨씬 더 많이 확장되었고 발전했을 것이라고 생각합니다.

조금 구체적으로 설명하면

앞서 말씀드린 것 처럼 Vespa는 검색엔진을 중심으로 둔 통합 콘텐츠 처리 플랫폼의 콤포넌트 셋입니다.  간단히 생각하면 검색엔진이라고 보면 되지만 일반적인 Solr이나 Elastic과 같은 검색엔진 보다는 주변에 가진 부속 컴포넌트들이 훨씬 더 많습니다.

Vespa의 역사를 보면 Vespa는 노르웨이의 엔지니어들이 주축으로 만든 한때 유럽의 Top1 검색엔진이었던 Fast검색엔진의 갈래입니다. Fast검색엔진은 후에 시장 주도권을 뺏긴후 차츰 회사 자체가 분할 매각되어서 지금은 거의 자취가 사라졌습니다.

분할된 Fast사는 Yahoo가 일부를 인수했고 시간의 간격을 두고 Microsoft가 일부를 인수했고 나머지 분할된 파트는 지금은 어찌되었는지 지금은 잘 모르겠습니다.

이 중에 Yahoo가 Fast에서 인수한 분할 부분은 Web search를 담당하는 쪽이었는데 인수한 Web search engine 중에  crawler같은 것을 버리고 vertical 검색 및 content platform으로 발전시킨 것이 Vespa입니다.  Vespa가 crawler같은 것을 버리고 web search 엔진을 추구하지 않은 이유는 Yahoo는 그당시에 이미 Inktomi web search를 가지고 있었기 때문에 Web search가 또 필요하지 않은 상태여서 Vertical search engine으로 방향을 전환하게 됩니다.

Vespa는 오토바이 브랜드명이기도 하지만 Vertical Search Plafrom의 약어입니다. 이름에 추구하는 바를 넣었듯이 한창때에는 세계 최고의 Vertical  Search Platform이라고 부를만 했습니다만 지금은 모르겠습니다. 검색 엔진쪽 만의 기능은 Elastic Search와 비교를 해봐야 하겠습니다.

Hadoop의 창시자인 더그커팅도 Yahoo에 근무하던 시절이 있었기 때문에 루씬도 Vespa에도 상당한 영향을 주었다고 알려져 있습니다. 때문에 Elastic이니 Solr이니 하는 Lucene기반의 것들과 비슷한 면도 많습니다.

검색엔진의 측면에서는 현재 주류라고 할 수 있는 Elastic Search와 비교를 해봐야 하겠습니다만 전체 기능의 광범위함과 성능을 볼 때는 Elastic Search가 Vespa를 따라가지 못할 것 같습니다.  하지만 편리함의 측면이라면 Elastic search가 더 나을 것입니다.

Vespa를 보면 코어 모듈의 튼튼함과 오랜 역사, 깔끔한 구조, 다양한 주변기능은 유럽 엔지니어들의 탁월한 능력을 엿볼 수 있게 해줍니다. 소스코드도 매우 깔끔하고 구조화가 잘 되어 있는 편이고 작동도 일관성있게 작동하는 것이 특징입니다.  소스코드를 들여다 보는 것 만으로도 많은 공부가 됩니다.

부속 콤포넌트 및 주변 콤포넌트로는 ML ranking(MLR이라고 부릅니다)을 비롯한 자체 개발한 문서저장용 NoSQL, 분산 데이터 파이프라인, 페더레이션(Federation)을 위한 컨테이너 등도 모두 가지고 있습니다.

그리고 여기에 Yahoo의 또 하나의 오픈 소스 선물인  Hadoop과 결합해서 사용하면 최고의 Content Agility Platform을 구성할 수 있게 됩니다.

MLR은 기계학습 기반의 검색결과 랭킹 기능입니다. GBDT기반으로 되어 있었습니다만 오픈 소스 버전에 탑재가 되었는지는 모르겠습니다.  (아마 되어 있을 것입니다. 분리하기 어렵기 때문에) 그리고 다국어 형태소 분석기와 Yahoo의 강력한 언어처리 모듈이 결합되어 비교적 매끈한 언어처리 기능까지도 지원했었습니다. 형태소 분석기와 언어처리 모듈은 오픈소스 버전에는 아마도 포함되지 않을 것입니다.

페더레이션 컨테이너 여러 검색엔진의 결과를 하나로 병합해주는 플랫폼을 말합니다.

분산 데이터 파이프라인은 소스로부터 검색엔진까지의 데이터 파이프라인으로 검색엔진으로 가기전까지 콘텐츠를 가공, 병합, 변형하는 플랫폼입니다.

이외에도 Phrase match와 Proximity 계산을 위한 고속 FSA 라이브러리와 그 외에 부속품들이 잔뜩 들어 있는 종합선물세트입니다.

대략 여기까지만 보셔도 알겠지만 대형 인터넷 포털사이트에서 사용하던 수십억건의 콘텐트를 관리, 가공, 활용, 서비스하는데 사용했던 솔루션을 이제는 누구나 사용할 수 있다는 것입니다.

기쁜일이지만 개인적으로는 서글픈 감상에도 젖어봅니다. Yahoo가 저렇게 하나씩 보따리를 풀고 사라져 가네요.