데이터 마이닝

• 데이터 마이닝
• 유사 항목 찾기
  • 문서의 슁글링
  • 민해싱과 자카드 유사도
• 빈발 항목집합
  • 시장바구니 모델
  • 연관 규칙^{association rule}
  • A-priori^선험적 알고리즘
  • scikit-learn
• 클러스터링
  • K-평균 알고리즘^{K-means algorithm}
• 추천 시스템
  • RMSE
  • Netflix Challenge에 대한 흥미로운 사실
• 차원 축소
  • 차원의 저주^{curse of dimensionality}

『빅데이터 마이닝』 은 스탠포드 CS246 Mining Massive Data Sets; MMDS의 교재다. 한글판은 2nd edition, 2014를 기준으로 하며 아래는 이 책의 내용을 중심으로 정리한다. 원문은 홈페이지에서 제공한다.

데이터 마이닝

• 멱 법칙^{Power Law}: 많은 현상이 y=cx^a으로 표현될 수 있는 멱 법칙을 따른다. 여기서 지수 a는 대부분 -2에 가까운 값이다. x번째로 많이 판매된 책의 판매부수, 혹은 x번째로 가장 많이 링크되는 페이지의 링크 개수 등이 그런 현상들이다.

유사 항목 찾기

문서의 슁글링

• k슁글: 문서 D는 문자열 abcdabd이며, k=2라고 가정할때 D에 대한 2슁글 집합은 {ab, bc, cd, da, bd}이다. 부분문자열 ab는 문서 D에 두 번 등장하지만, 슁글로서는 한 번만 등장한다.
• MinHash: (or the min-wise independent permutations locality sensitive hashing scheme) is a technique for quickly estimating how similar two sets are. The scheme was invented by Andrei Broder (1997), and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results.
  • The goal of MinHash is to estimate J(A,B) quickly, without explicitly computing the intersection and union.
  • 집합을 무작위로 치환^permuation했을때, 변경된 순서에서 첫 번째로 나타나는 해당 집합의 원소가 그 집합의 민해시 값이다. e.g. h(S_1) = a

민해싱과 자카드 유사도

• 행을 무작위로 치환하는 민해시 함수가 두 집합에 대해 같은 값을 생성할 확률은 그 두 집합의 자카드 유사도와 같다.
• 파이썬 코드 풀이 MMDS 책 내용을 바탕으로 한다. Java의 두 Set 교집합 최적화를 작성할때 자카드 유사도를 사용했는데 집합을 모두 계산하지 않고 MinHash를 사용한다면 훨씬 더 빠른 속도로 계산이 가능했을 것이다.

구글에서는 SimHash를 만들어 크롤링에 유사 문서 검출에 활용한다고 한다.

지역성 기반 해싱^{LSH, locality-sensitive hashing} 모든 쌍을 조사할 필요 없이 유사해 보이는 쌍을 검토하는 방식이다.

LSH 응용 분야로 개체 식별, 지문 판독, 신문 기사 구별이 나온다. 개체 식별은 여러 피처를 대조해 동일 개체인지를 식별하는 것이고, 유사한 신문 기사는 단순히 슁글들의 자카드 유사도를 넘어 문서의 중요 단어 집합 검사, 동일한 주제인데 각기 다른 기사를 함께 클러스터링하는 방법을 포함한다. 추후 구현이 필요할때 원문을 참고하여 보다 구체적으로 파악하도록 한다.

빈발 항목집합

빈발 항목집합^{frequent itemset}을 찾는 문제는 연관 규칙^{association rule}을 발견하는 문제와 종종 동일시 된다.

시장바구니 모델

support threshold인 s가 있을때 I가 항목들의 집합이라면, I에 대한 support^지지도는 I를 부분집합으로 갖는 바구니들의 개수다. I의 support가 s 이상일때 I는 frequent로 정의한다. 실제 시장바구니 분석에 응용됐고, 해당 연구 내용은 통계학 페이지에 정리한다. 빈발 항목집합을 찾음으로써, 판매자는 공통으로 함께 팔리는 물품들을 파악할 수 있다.

더 많은 분야에 응용되는 사례:

• 관련된 개념: {Brad, Angelina}가 같이 등장한다.
• 표절: 공통된 문장이 등장한다는 사실로 해당 문서가 표절임을 증명할 수 있다.
• 생체지표: 어떤 질병과 하나 이상의 생체지표로 구성된 빈발 항목집합을 이용하면, 해당 생체 지표를 가진 환자에게 해당 질병에 대한 검사를 제안해볼 수 있다.

연관 규칙^{association rule}

I가 항목들의 집합이고 j는 단일 항목이라면 연관 규칙의 형식은 I→j이다.

• I→j confidence^신뢰도: I+j를 포함하는 집합의 수 / I를 포함하는 전체 집합의 수
• I→j interest^관심도: confidence - (j를 포함하는 전체 바구니 비율)

관심도가 높거나 매우 낮은 음수이면 높은 관심도를 보인다. 맥주와 기저귀 사례는 {diapers}→beer가 관심도가 높다. {coke}→pepsi는 음수의 관심도를 보이지만 점수는 매우 낮다. 코카콜라를 구매한 사람이 펩시를 구매할 가능성은 낮다.

confidence의 단점은 연관성의 중요도를 오해할 수 있다는 점이다. 맥주가 원래 자주 판매되는 품목이라면, 사과를 포함하는 거래가 맥주도 포함할 가능성이 커지므로 confidence를 부풀리게 된다. 하지만 lift를 이용하면 두 품목 모두의 기반 빈도^{base frequency}를 고려할 수 있다. (수학 없이 배우는 데이터 과학과 알고리즘, 2017)

lift가 1보다 크면 X가 판매될때 Y도 함께 판매될 가능성이 있다는 것이고, 1보다 작으면 X가 판매될때 Y가 판매될 가능성이 낮다.

A-priori^선험적 알고리즘

가능한 품목 집합의 가짓수를 줄이는 방법. 어떤 품목 집합의 빈도가 낮으면, 해당 품목 집합을 포함하는 더 큰 품목 집합의 빈도도 낮다. 즉, {맥주}의 빈도가 낮으면 {맥주, 피자}의 빈도도 낮아야 한다. 판매 빈도가 높은 품목 집합을 알고 싶은 것이 목표라면, {맥주, 피자}는 물론 맥주를 포함하는 모든 품목 집합을 고려할 필요가 없다. (수학 없이 배우는 데이터 과학과 알고리즘, 2017)

Support가 낮은 품목을 포함한 집합을 순차적으로 정리한다.

scikit-learn

scikit-learn에 Apriori 알고리즘을 추가해달라는 청원에 Andreas Muller의 답변: I’m not sure item set mining is in the scope of sklearn. 이후에 이어지는 쓰레드에서도 Association rule mining is outside of the scope of machine learning, and certainly out of the scope of scikit-learn. 이라고 한다. 머신러닝의 범주가 아니라는 것.

책에서 이후에 이어지는 내용들은 책 제목 massive datasets 답게 분산처리를 위한 병렬 알고리즘이 주를 이룬다.

클러스터링

거리를 계산하는 방법은 유클리드 공간에서는 유클리드 거리, 맨하탄 거리, 비유클리드 공간에서는 자카드 거리, 코사인 거리, 해밍 거리, 편집 거리등이 있다. 거리는 머신러닝 페이지에 정리한다.

유클리드 공간^{Euclidean space} 고대 그리스 수학자 유클리드가 연구했던 평면과 공간을 일반화한 것으로 2차원 유클리드 평면, 유클리드 기하학의 3차원 공간 및 기타 특정 공간을 포함한다.

K-평균 알고리즘^{K-means algorithm}

비계층적 군집분석의 대표라 할 수 있으며, 1967년 UCLA의 맥킨이 고안했다. 그때까지 주류였던 계층적 군집분석에 비해 계산량이 엄청나게 줄어들었고 속도도 빠르다. (통계의 힘 2, 2014)

주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 센트로이드^centroid를 이동하며 동작한다. BFR 알고리즘은 k-평균의 일종으로, 크기가 너무 커서 메인 메모리에 올라갈 수 없는 데이터를 처리하기 위해 고안됐다. 클러스터들은 축을 기준으로 정규 분포를 따른다고 가정한다. CURE 알고리즘은 점 할당 방식이다. 유클리드 공간만을 위해 고안됐으나 클러스터의 모형에 제한은 없다. 너무 커서 메인 메모리에 올라갈 수 없는 데이터를 다룬다. 비유클리드 공간에서는 마찬가지로 점 할당 방식인 GRGPF 알고리즘을 사용한다.

추천 시스템

‘유사 항목 찾기’에서 유사성의 개념은 어휘적^lexical이다. 즉, 많은 문자가 동일한 순서로 배열된 문서들을 유사하다고 판단했다. 추천 시스템에서 유사성의 개념은 이와 다르다. 두 문서 사이에 어휘적 유사성이 거의 없다 하더라도 중요한 단어들이 많이 등장하는지만 집중한다. 하지만 유사한 문서들을 찾는 방법론은 거의 같다. 자카드 거리든지 코사인 거리든지 일단 거리 측정치가 있으면, 민해싱을 사용하거나(자카드 거리) 혹은 다수의 공통 키워드를 갖는(코사인 거리), 즉 유사한 문서들 쌍을 찾는 LSH 알고리즘에 무작위 초평면을 적용할 수 있다.

추천 시스템에는 두 가지 기본적인 구조가 있다.

1. 내용 기반^{Content-based filtering} 은 항목의 특성에 중점을 둔다. 항목이 갖는 특성의 유사성을 측정해 항목 간의 유사성이 결정된다.
2. 협업 필터링^{Collaborative filtering, CF} 은 사용자들과 항목들 사이의 관계에 중점을 둔다. 사용자들이 두 항목에 순위를 매기고, 매겨진 순위의 유사성에 따라 항목 간의 유사성이 결정된다.

Netflix Prize 데이타셋을 이용한 Kaggle 추천 커널, 매우 상세하게 설명하고 있어 도움이 된다. 협업 필터링을 사용한다.

RMSE

컴퓨터 과학에서는 RMSE(root-mean-square error)를 많이 사용하며, 표준 편차와는 분산의 제곱근이 아닌 에러의 제곱근이라는 차이가 있다. for an unbiased estimator, RMSE is the square root of the variance, known as the standard deviation. 분산은 거리의 제곱이며, 표준 점수는 표준 편차의 배수로 z-scores로 부르기도 한다.

Netflix Challenge에 대한 흥미로운 사실

• 우승 후보작들은 대부분 여러 알고리즘의 앙상블이었다.
• 영화 정보를 IMDB와 매칭을 시도했으나 장르와 그 외 정보는 유용하지 않았다. 머신 러닝이 어떻게든 관련 정보를 찾아낼 수 있었고, 넷플릭스와 IMDB 데이터의 영화 제목을 매칭할 때 발생하는 개체 식별 문제를 정확하게 해결하는 일이 쉽지 않았기 때문이다.
• 순위를 매기는 시간 정보가 유용하다고 알려져 있다. 영화 관람 후 즉시 순위를 매기는 사람들이 호의적일 가능성이 높은 영화들이 있다. “패치 아담스”가 그런 사례다. 반면, 즉시 순위를 매기면 좋은 평가를 하지 않으나 시간이 지난 후 더 나은 순위를 매기게 되는 영화도 있다. “메멘토”가 그런 사례다.

차원 축소

M을 정사각 행렬^{square matrix}, \(\lambda\)는 상수, e는 M과 행이 같은 0이 아닌 열 벡터일때, \(Me={\lambda}e\)인 경우 \(\lambda\)는 M의 eigenvalue^고윳값, e는 M의 eigenvector^고유벡터다. 길이와 관련된 모호성을 제거하기 위해, e의 벡터 성분들에 대한 제곱의 합이 1인 경우 eigenvector는 unit vector^{단위 벡터}가 된다. eigenvalue와 eigenvector를 eigenpair^고유쌍이라 한다.

차원의 저주^{curse of dimensionality}

데이터에서 모델을 학습할 때 독립적 샘플이 많을수록 학습이 잘 되는 반면 차원이 커질 수록 학습이 어려워지고 더 많은 데이터를 필요로 한다. (source) 차원이 커질수록 데이터는 기하급수적으로 필요하다.

Last Modified: 2022/04/25 02:50:20