2015년 3월 31일 화요일

massive mining data ch1


1 Data Mining

  1. 1.1 What is data Mining?
    데이터의 모델을 찾는것이다 모델은 여러가지가 될수 있다 그렇다면 모델은 무엇인가?
    • 1.1.1 Statistical Modeling
      통계적인 모델은 데이터의 가장 가까운 분포 특성을 찾는것이다.
      ex1)숫자로 이루어진 데이터를 보고 정규 분포 를 따른다는걸 찾은 후 여러가지 추측을 하기 위해
여러 방법들이(분산, 평균등)정규 분포의 특징을 따른다고 생각하고 사용하는것
    • 1.1.2 Machine Learning
      머신 러닝은 데이터 마이닝과 동의어가 아니며 머신러닝은 데이터를 사용해 특정 모델을 훈련 시켜 원하는 결과를 도출하는 방식이다. 머신러닝의 경우 데이터에서 우리가 어떤것을 찾아야 될지 잘 모를때 좋은 성능을 발휘하며 우리가 어떤것을 찾아야할지 정확히 알때는 그렇게 짜여진 알고리즘과 비교해 머신 러닝이 더 좋은 성능을 발휘 하기는 어렵다. 머신 러닝을 데이터 마이닝에 속에 있는 부분 집합으로 간주하는 느낌이다.
    • 1.1.3 Computational Approaches to Modeling
      데이터 마이닝을 알고리즘 문제로 생각하고 가장 그럴사한 결론을 유추해내는것 위의 예제1 을 보면 데이터는 정규분포와 유사할뿐이 100 프로 정규 분포를 따르는것은 아니다.
      1.데이터가 거의 맞다고 가정하고 요약하는것
2.데이터의 가장 주된 특징만 사용하고 나머지는 무시하는것
    • 1.1.4 Summarization
      1. 구글의 Page rank 알고리즘 처럼 관심있는 부분을 요약하는것 페이지 랭킹은 하나의 숫자로 해당 페이지에 유저가 존재할 확률을 나타낸다. 해당 숫자들을 사용해서 유저의 쿼리에 적당한 순서로 결과물을 오더링 할수 있다.
      2. 클러스터링을 사용하여 데이터 자체를 centroid 등으로 요약하는 방법도 있다.
        ex1.2)클러스터링의 가장 오래된 예제는 런던의 콜레라 전염 지역을 맵에 요약 표시한것이다.
http://en.wikipedia.org/wiki/1854 Broad Street cholera outbreak
    • 1.1.5 Feature Exraction
      데이터에서 특정한 패턴을 가진 데이터를 찾아내는것
      1. Frequent Itemsets : 여러 아이템을 넣을수 있는 여러 바구니, 그리고 아이템과의 다대다 관계에서 자주 같은 바구니에 들어가 있는 아이템 찾기 예를 들자면 마켓에서 햄버거와 케찹은 동시에 구매된다.
      2. Similar Items : 전체 셋의 엘리먼트를 부분집합으로 가지고 있는 여러 셋에서 서로 비슷한 (유사한) 셋을 찾아내는 문제 예를 들면 아마존에서 비슷한 취향을 가진 유저를 찾아서 유저들끼리 서로 추천을 해줄수 있다 (collaborative filtering)
  1. 1.2 Statistical Limits on Data Mining
    방대한량의 데이터를 사용하기 때문에 데이터에 생각지 못한 패턴이 존재할수도 있다. 데이터 마이닝을 할때 통계적으로 조심해야할 상황들
    • 1.2.1 Total Information Awarenss
      2002년 미국에서 부시 정부가 테러리스트의 활동을 찾기위해 모든 신용카드 이력, 호텔 예약 정보 등 많은 정보를 섞어서 TIA를 만들려고 했으나 실패했다. 문제는 위와 같은 시스템이 만들어진다면 어떻게 될것인가? 해당 정보들을 탐색하면 테러리스트 정보만 나올까 다른 정보가 나온다면 어떻게 해야될까?(테러리스트는 아니지만 불법적인 행동을 한 사람) 테러리스트라고 추측한 활동들은 얼마나 정확할까?
    • 1.2.2 Bonferronis principle
      일정한 데이터안에서 일정한 이벤트 패턴을 찾는 다고 생각해보자 만약 데이터가 랜덤하게 들어가 있다면
      실제로 해당 데이터 패턴이 존재 하지 않는다고 해도 랜덤하게 데이터가 들어감으로 특정 패턴이 생성될수 있다. 위와 같은 패턴을 bogus(가짜)라고 부른다. 만약 데이터가 많아진다면 위와 같은 가짜 패턴은 많아진다.
      통계에서는 위와 같은 상을 Bonferrion correction 을 사용해서 위와 같은 에러를 피한다.
      Bonferroni’s principle을 통계를 피해 설명해보자 당신이 생각하는 이벤트가 랜덤데이터 상황에서 몇번이나 발생할까를 계산하고 이넘버와 실제로 예측하는 패턴이 존재한 횟수를 비교해서 랜덤데이터 상황에서 랜덤하게 생기는 패턴이 더 클경우 우리가 찾은 대부분의 패턴들이 가짜 임을 알수 있다.
      1.2.1 에서 처럼 테터 리스트를 찾을때 해당 패턴이 거의 존재하지 않기 때문에 랜덤하게 생길 데이터가 훨씬 클것임을 유추할수있다.
    • 1.2.3 An Example of Bonferroni’s Principle
      우리가 악마 추종자를 찾는 다고 생각해보자 악마 추종자들은 호텔에 모여서 악마를 호출하는 의식을 하는 패턴을 가지고 있다 라고 약속하자
      (1000일안에 동일한 2명이 호텔에서 2틀을 만날 경우 악마 추종자라고 가정 (.날짜가 연속될 필요 없음, 2틀이 모두 같은 호텔일 필요 없음)) 
      0.총인구 10^9
0.모든 사람은 100일에 한번씩 호텔에 간다.
0.호텔은 하루에 100명을 수용할수 있고 호텔은 10^5 개가 존재 (10^9 의 사람들이 100일에 한번씩 갈경우 해당 사람들을 수용할 호텔의 수)
0.1000일 동안 호탤의 숙박기록을 조사
0.랜덤한게 위의 악마추종자와 같을 패턴이 나타날 수를 구해보자 
0.서로다른 두명의 사람이 같은 날에 호텔에 갈 확률은 0.01 * 0.01 = 0.001
0.두사람이 같은날 같은 호텔에 있을 확률 10^-4 * (10^-5)^2 = 10^-18
0.서로 다른 두사람이 짝의 총수 10^9C2 = 5 * 10^17(대략) nC2 = n^2/2로 가정
0.서로 다른 날의 짝의 총수 10^3C2 = 5 * 10^15
0.서로 다른 사람짝이 서로 다른 짝날에 같은 호텔에서 만날 수 (악마추종자 패턴이 주어진 데이터에서 랜덤하게 생성될 경우의 수 )
0.(5 * 10^17) * (5 * 10^15) * 10^-18 = 250,000
0.만약 악마 추종자가 10쌍이라고 가정할 경우... 우리가 찾은 패턴의 대부분이 가짜 패턴이라는걸 알수 있다.
  1. 1.3 Things Useful to Know
    • 1.3.1 Importance of words in Documents
      문서를 주제 별로 구분한다고 생각해보자 이때 각각의 주제마다 특정 단어에 대한 빈도수가 높을 것이다. 야구 문서라면 볼 배트 등을 말한다. 만약 우리가 위의 주제별 단어 셋을 가지고 해당 문서가 야구에 관한것인가를 확인하는건 어렵지 않다. 하지만 우리는 해당 문서를 먼저 분류해야지만 주제별 단어 셋을 알 수 있다. 그래서 보통 분류 작업은 문서에서 중요한 단어를 선택하는대서 시작한다. 우리는 문서에 빈도수가 높은 단어의 경우 더 중요하다고 가정할수 있다 하지만 (the a)등 stop words는 별 필요가 없기 때문에 분류하기전에 먼저 제거한다.
      좀전에 야구의 예제를 보는 것처럼 문서의 주제를 알려주는 희귀한 단어들이있다. 하지만 모든 희가한 단어들이 좋은 단어는 아니다. 예를 들어 뭥미 같은 단어는 희귀한 단어지만 문서를 식별하는대 도움을 주지 못한다. 하지만 경마를 나타낼때 기수 라는 단어는 많은 정보를 주며 1번 기수 , 2번 기수 등 처럼 연속되서 나올 경우가 많다. 즉 전체 문서에서 희귀하면서 문서에 많이 나오는 단어는 특성을 나타내는 단어라고 가정하자
      문서에서 단어의 중요성을 표현하는 지표로 TF-IDF(Term Frequenct-Inverse document frequenct) 문서안에서 단어 빈도수 - 문서 전체 숫자 /단어를 가지고 있는 문서 숫자
    • TF
      TF_{ij} = \frac{f_{ij}}{max_{k}f_{kj}}
      f_{ij} 는 다큐먼트j 에 있는 i 단어의 빈도수
      max_{k}f_{kj} 는 다큐먼트j 에 있는 모든 단어의 빈도수 중 가장 많은 나타난 단어의 빈도수
      ex)
1.hello world world
      hello = tf_{ij} = 1
      world = tf_{ij} = 2
      max_{k}f_{kj} = 2
      hello의 TF 는 1/2
      world의 TF 는 1
      위를 보면 하나의 문서에 자주 나오는 단어들은 높은 점수를 준다.
    • IDF
      IDF_{i} = log_{2}(\frac{N}{n_{i}})
      N은 전체 문서수
      n_{i}은 해당 단어가 나온 문서수
      ex) 
1.hello world world
2.hello ha ha world
3.ho ho hehe world
      world = IDF_{i} = log_{2}(\frac{3}{3}) = 0
      hello = IDF_{i} = log_{2}(\frac{3}{2}) = 0.58
      ho = IDF_{i} = log_{2}(\frac{3}{1}) = 1.5
      전체 문서에서 자주 나오지 않을 수록 높은 점수를 준다.
    • TF * IDF
      1번 다큐먼트의 단어 중요도
      hello = 1 * 0.58 = 0.58
      world = 2 * 0 = 0
      world 의 모든 문서에서 다 나옴으로 중요하지 않은 단어이다.
      즉 전체 문서에서는 적게 나오고 해당 문서에서는 자주 나오는 단어가 해당 문서에서의 중요 단어가 된다.
    • 1.3.2 Hash Functions
      hast function 이란? 해쉬 키를 받아 들여 bucket 숫자를 리턴하는것
      bucket B개 라면 인덱스는 0 부터 B - 1 까지 존재한다.
      또한 해쉬펑션의 특징은 들어온 해쉬키를 각각의 bucket 에 골로루 잘 분산 시킬수 있다는것이다.
      하지만 위와 같이 되기 위해서는 bucket 수 에 비례한 hash-key 수 자체가 커야지만 가능하다.
      bucket이 100 개인대 해쉬키가 2개라면 적절이 분산되지 않는다.
      h(x) = x mod B
      위처럼 해쉬 펑션을 정의한 후 B = 10 이고 모든 해쉬키가 2의 배수라면 (2,4,6,..) 모든키가 골고루 분산되지 않고 0,2,4,6,8 bucket 에만 들어간다 위와 같은상황을 최소화 하기 위해 B 는 소수로 정하자 B = 11 로 정할 경우 같은 상황에서도 골고루 분포된다.
      해쉬키가 위와 같이 integer 가 아니라면 어떻게 해야 될까? 여러가지 방법이 있다.
      1.모든 데이터는 비트로 나타내어 짐으로 그냥 비트 시퀀스를 숫자로 번역하는 방법
      2.스트링키일 경우 각각의 문자를 ASCII 또는 UNICODE 의 코드 값으로 변환 후 sum 하는 방법
      3.B가 클경우 10^9 또는 2^30 일 경우 스트링키을 4개 그룹으로 분리하고 2번방법으로 각각의 그룹을 sum한후 4개의 그룹을 이어 붙이면 32bit integer 가 된다. (ex concat(123,456) = 123456)
      4.키가 스트링이 아니더라도 type을 integer 로 변경 하는 아이디어를 사용하면 위와 같은 방식으로 해쉬 펑션을 사용할수 있다.
    • 1.3.3 Indexs
      검색에 초점을 맞춰 데이터의 자료구조를 변경 시킨 것
      비트리 등 여러 구현 방법이 있지만 해쉬 테이블로 구현할 경우 해당 버킷안에 검색해야 될 데이터가 링크드 리스트 형태로 들어가있다.
      ex)  칼럼이 이름,주소,집번호 로 구성된 스키마가 있을때 집번호에 해쉬 인덱스를 생성하면 
데이터가 (lee,seoul,010)이라고 할때 h(010) = 1 이라고 하면 1 의 버킷에 해당 레코드의 포인터를 집어 넣고
이후 집번호로 검색할때 h(010) = 1 이라고 하면 1번 버킷만 찾으면 됨으로 빠르게 찾을 수 있다.
    • 1.3.4 Secondary Storage
      하드드라이브는 메인메모리보다 많이 느리다 하드드라이브의 최대 리드 속도는 초당 10^8Byte(100M) 라고 가정해도 좋다 메가 단위의 데이터를 다룰때는 상관없지만 기가 또는 테라 단위를 조작해야 할때는 도움이 될수 있다.
    • 1.3.5 The base of Natural Logarithms
      자연 상수 e = 2.7182….
      e = \lim_{n \to \infty}\left ( 1 + \frac{1}{n} \right )^n
      e = \sum _{n \to 0}^{\infty}\frac{1}{n!}
      x가 1,2,3,4 로 가면 대략 2,2.25,2.37,2.44 가 되고 무한대로 가면 약 2.72 로 수렴 한다는걸 쉽게 알수 있다.
      (1 + a)^b
      에서 a가 작다고 가정하자 그러면 위식을
      (1 + a)^{(1/a)(ab)}로 나타낼수 있다.
      여기서 a = 1/x 라고 대치하면 1/a = x이다 즉
      \left ( (1 + \frac{1}{x})^{x} \right )^{(ab)} \approx e^{ab}
      을 유추 할 수 있다. a가 작음으로 x 는 크다 라고 가정할수 있다 (a = 1/x) 그렇다면 우리는 위식을 e^{ab}라고 대략 적으로 생각할수 있다.
      위의 아이디어에서 a가 작고 b가 크다면 (1 - a)^b 는 대략 e^{-ab} 라고 생각할수 있다.
    • e^x
      e^x = \sum _{i=0}^\infty \frac{x^i}{i!} = 1 + x +\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+...
      x가 크다면 수렴하는대 엄청 오랜 시간이 걸리지만 x가 작의면 빨리 수렴한다.
      e^{1/2} = 1 +\frac{1}{2} +\frac{1}{8} +\frac{1}{48} +\frac{1}{384} +... = 1.64844
      e^{-1} = 1 - 1 +\frac{1}{2} -\frac{1}{6} +\frac{1}{24} + ... = 0.36786
    • 1.3.6 Power laws
      log_{10}y = 6 - 2log_{10}x
      라는 식을 생각해보자 위와 같은 식을 Power Laws 라고 한다.
      예를 들어 아마존에서 1등은 10^8 만큼 판매하고 10등은 10^6 만큼 판대한다는 식을 그리고 싶으면 위의 식을 사용하면 된다.
      logy = b+alogx
      y = e^be^{alogx} = e^bx^a = cx^a
      로그를 자연로그라고 가정하면 두번째 식이 나오고
      그후 e^b 를 상수 취급하면 마지막 식을 얻을수 있다.
      관계식을 구하는 방법
1.x = 1, y = 10^6 이고 x = 1000, y = 1 이라면
2.10^6 = c 로 두자
3.y = cx^a 임으로 
4.대입하면 1 = c(1000)^a
5.1 = 10^6 * (10^3)^a = 10^6 + 3a 
6.a = -2
7.y = 10^6x^-2 임을 알수 있다.

원본책  http://www.mmds.org/
​
작성자:
라벨: