2015. 9. 22. 01:00
Machine Learning & Data Mining

윤영식_ 'Growth Hacker/Machine Learning'



저작자표시 비영리

'Machine Learning & Data Mining' 카테고리의 다른 글

Deep Learning Tutorial  (0) 2015.09.22
Deep learning 기반 T map POI 추천 기술개발 사례  (0) 2015.09.22
실기간 추천엔진 머신 한대에 구겨넣기 (펌)  (0) 2015.09.22
Machine Learning 스터디 (1) Machine Learning이란? (펌)  (0) 2015.08.24
쉽게 풀어쓴 딥 러닝의 거의 모든 것(펌)  (0) 2015.08.23
Posted by Name_null
2015. 9. 22. 00:53
Data Analtytics

kyumin choi - 추천시스템




저작자표시 비영리

'Data Analtytics ' 카테고리의 다른 글

Data Mining 개론_Kwang Woo NAM  (0) 2015.09.22
[142] 이커머스 회사가 반드시 측정해야 할 9가지 데이터 (9 DATA SETS EVERY ECOMMERCE COMPANY SHOULD MEASURE)  (0) 2015.03.10
How to Become a Data Scientist from ryanorban  (0) 2015.03.01
실리콘밸리 Data Scientist의 하루 (펌)  (0) 2015.03.01
어떻게 하면 데이터 사이언티스트가 될 수 있나요? from Yongho Ha  (0) 2015.02.15
Posted by Name_null
2015. 9. 22. 00:48
Machine Learning & Data Mining

실기간 추천엔진 머신 한대에 구겨넣기 (펌)




  • 1. 코끼리 냉장고에 집어넣기: 실시간 추천엔진을 노트북에서 돌게 만들어보자 하용호 NUMBERWORKS 대표
  • 2. 하용호 용 호 지금은 ‘넘버웍스’라는 data science firm을 만들었어요
  • 3. 어떤 순서로 말하나요? 1. 추천엔진의 틀에 대해 알아보자 2. 구글 논문대로 잘만드는 방법 3. 그거보다 더 멋지게 만들어보자. 4. 정리
  • 4. 추천엔진들의 
 틀에 대해 배우자.
  • 5. Recommendation systems come in two types
  • 6. Content-based vs. Collaborative 
 Filtering 
  • 7. Content-based는어렵습니다.
            - 사전에 현업지식도 꽤 있어야하고
            - 개별 컨텐츠의 메타데이터도 거의없고
            - 상품에서 그것을 뽑아내기도 어렵습니다.
  • 8. Collaborative Filtering 그래서 모던한 추천엔진들은 을 씁니다.
  • 9. 10 Collaborative Filtering 역시 2가지로 나뉘게 됩니다.
            - Memory-based vs.Model-based 보통은 둘다 조합(hybrid)해서 씁니다.
  • 10. 11 Memory-based을 오늘은 어떻게 콩알만하게 만들 수 있는지 알아봅시다.
  • 11. memory-based 를 잘만드는 방법
  • 12. YOU
  • 13. YOU Someone
 LIKE YOU! recommend: 당신과 다른 선호가 비슷한 사람이 좋아하는 것을 당신도 좋아할 것 
  • 14. 누가 가장 닮았냐 Jaccard similarity 전체중에 겹치는 비율을 닮음으로 측정 A가 좋아한 상품 B가 좋아한 상품
  • 15. but 
 size matters
  • 16. TOO MANY COMBINATIONS : 비교할 대상(사람, 상품)이 너무 많아 누구와 비교하기 어렵다 
  • 17. 물론 이런데 쓰라고 Hadoop이 있기는 합니다만
  • 18. img from : http://thepage.time.com/2009/04/18/why-is-this-elephant-crying/ 이건 Hadoop에게도 너무 큰 계산 입니다
  • 19. 비교 대상을 줄이기 위해 pre-clustering이 필요합니다
  • 20. 그런데 naive 한 clustering 방법들은 O(N^2) 계산량이 많아 클러스터링 하려는데 클러스터링 계산량이 많다? 더 가벼운 클러스터링 방법이 필요!
  • 21. pre-clustering에 관련된 마스터 피이쓰 논문이 있습니다
  • 22. Use MinHASH as LSH(min-wise independent permutations locality sensitive hashing) 이 논문의 핵심 아이디어는
  • 23. 이건 또 뭔소리야? 알아보자. Locality Sensitive Hashing
  • 24. 기존 자료구조에서 hash는 
 충돌나지 않게 넓게 뿌리는 것이었지만
  • 25. 만약 적은 버킷에 일부러 
 비슷한 것들끼리 충돌나게 뿌리면? clustering처럼 동작하게 된다.
  • 26. Make hash functions Hash function #1 Hash function #2 HOW DOES LSH WORK? (localitysensitivehashing)
  • 27. Hash Func #1 Hash Func #2
  • 28. 클러스터링은 원래 O(n2) 이지만 hash snapshot으로 O(n) 짜리 클러스터링
  • 29. TIME SIZE
              2) 상세한 비교는 O(n2) 하지만 부담되지 않는 n에서 동작한다.
              1) 계산할 녀석과 비슷한 애들이 있는 클러스터를 찾는다
  • 30. 원래 hash function은 원본이 조금만 달라도 훅훅 달라지는게 좋은 hash였다.
                 그런데 이제는 기존과 반대로 원본이 닮았으면, 결과값들도 닮아야 하는 특수한 hash function이 필요하다.
  • 31. - cosine similarity - hamming distance - euclidean distance - jaccard similarity 닮음의 종류가 많다.
  • 32. MinHash는 Jaccard similarity를 유지하는 타입의 LSH 이런 놈이 필요했다!
  • 33. A B C r1 1 0 1 r2 0 1 1 r3 0 0 1 r4 1 1 0 r5 1 0 0 r6 0 1 1 A B C h1 2 4 1 h2 2 1 1 h3 1 2 3 r3 r5 r1 r2 r4 r6 r6 r1 r3 r2 r4 r5 hash1 hash2 random permutation r5 r4 r6 r2 r1 r3 hash3 random하게 permutation한 순서로 읽어가며 첫 1의 index를 구한다. jaccard(B,C) = 2/5 = 0.4 jaccard(A,C) = 1/6 = 0.16 sim(B,C) = 1/3 = 0.3 sim(A,C) = 0/3 = 0 jaccard = intersect/union sim = intersect/length
  • 34. 실제로는 random permutation을 만드는 것도 계산량이 많이 필요하게 되므로 universal hash를 잔뜩 random generation
             이를 random permutation의 대리자(proxy)로 사용하곤 한다.
             뭔가 말이 어려워 보이지만 하여간 저렴한 계산으로 minhash를 얻을 수 있습니다.
  • 35. 이건 일종의 dimension reduction A B C r1 1 0 1 r2 0 1 1 r3 0 0 1 r4 1 1 0 r5 1 0 0 r6 0 1 1 A B C h1 2 2 1 h2 2 1 1 h3 1 2 3 6차원 3차원
  • 36. Q P R S s1 1 2 2 1 s2 3 1 3 1 s3 1 2 1 2 s4 4 1 1 4 hash되어 나온 값을 signature라 하고 이것들을 적당히 concate시켜서 cluster id 삼는다. ‘s1-s2’, ‘s2-s3’, ‘s3-s4’, ‘s4-s1’ Q 13 Q, R 31 Q 14 Q,S 41 P 21 P, R 12 P,S 12 R 23 R,S 11 S 24
  • 37. 그래서 typical한 Batch Implementation은 다음과 같습니다. (item to item 케이스로 설명)
  • 38. minhash로 클러스터 만들기
            for 후보 in 모든 후보들:
                그 후보의 모든 click stream 로딩하기
                로딩한 것으로 minhash signature 생성하기
                signature들을 concate해서 다량의 cluster id
                이 후보를 해당 cluster id들에 집어넣기

           for cluster in 만들어진 클러스터들:
                if length(클러스터) > threshold:
                    클러스터의 멤버십 정보 저장
  • 39. 클러스터 정보로 추천하기 타겟 item이 존재함 --> 그 타겟 item의 minhash값을 가져옴 -->
              minhash값을 concate해서 해당되는 cluster 들 다 찾음 
                 for cluster in 타겟이 포함된 클러스터들:
                클러스터에 포함된 다른 뽑은 item들 로딩
                그 item들의 click stream을 로딩
                 click stream정보를 기초로 모든 pair 유사도 계산
                각 클러스터로 부터 모여온 것중 유사도 top N들을 선출
  • 40. It is typical implementation. but not attractive :(
  • 41. 더 멋지게 만들어 보자!
  • 42. 아까 구현은 2개의 문제가 있다. 느려 구려
  • 43. Heavy I/O 가 잦다 : 빨간색이 I/O 유저의 액션 우리의 반응 느려! minhash로 클러스터링 for 후보 in 모든 후보들: 그 후보의 모든 click stream 로딩하기 로딩한 것으로 minhash signature 생성하기 signature들을 concate해서 다량의 cluster id 이 후보를 해당 cluster id들에 집어넣기 for cluster in 만들어진 클러스터들: if length(클러스터) > threshold: 클러스터의 멤버십 정보 저장 클러스터 정보로 추천하기 타겟 item이 존재함 그 타겟 item의 minhash값을 가져옴 minhash값을 concate해서 cluster id 리스트작성 위를 통해 타겟이 포함된 cluster들을 다 찾음 for cluster in 타겟이 포함된 클러스터들: 클러스터에 포함된 다른 item들 로딩 그 item들의 click stream을 로딩 click stream정보를 기초로 모든 pair 유사도 계산 각 클러스터로 부터 모여온 것중 유사도 top N들을 선출 그중 적절히 소팅하여 추천
  • 44. - speed gain 후보를 한정한다. 후보를 한정한다. - quality loss 장점 : 단점 : 클러스터를 쓴다
  • 45. 어떻게 하면 엄청나게 빠른 속도로 퀄리티 손상없이 추천을 만들어낼 수 있을까?
  • 46. 왜 I/O 문제가 되는 것일까? 상품과 유저의 부익부 빈익빈 현상때문이다.
  • 47. 대부분의 서비스는 이런 양상 : user당 view수 라이트 유저 헤비 유저
  • 48. 대부분의 서비스는 이런 양상 : item당 view수 다수의 인기없는 item 보통 item 소수의 초 인기 item
  • 49. 보통은 이정도 아이유님 저스틴비버
  • 50. 매우 인기있는 유저나 아이템 존재 = 비교대상으로 자주 등장 (인기있다니까) = 엄청나게 긴 click stream = 로딩하는데 시간 걸린다 = 공간모자라 캐시 로딩한 것도 날라간다. = 각종 page out도 발생한다. =퍼포먼스가 떨어진다.
  • 51. 인기 아이템 보통 아이템 클릭 스트림의 길이 보통 아이템 보통 아이템
             이 클릭 스트림의 길이를 어떻게든 해야 등장할 때마다 퍼포먼스 깽판 치는 것을 막을 수 있다.
  • 52. 해결 방법 = 클릭 스트림 원본 말고, 짧은 대체본
                            = use good dimension reducer = 대체본끼리 비교해 바로 유사도를 알아야. = 어 그런거 이미 알고 있잖아? = minhash
  • 53. 인기 아이템 S1 S2 … Sn S1 S2 … Sn 보통 아이템 hash function수 n만큼 signature생성 이제는 모두 
 같은 길이
  • 54. S1 S2 S3 S4 signature둘 사이 겹치는 sig의 비율이 곧 jaccard S5 S1 S2 S3 S4 S5 추정된 jaccard coefficient 2/5 = 0.4 그런데 아까도 봤지만, 이 추정값과 실제 jaccard랑은 오차가 있던데?
  • 55. 더 많은 hash func을 써서 signature의 길이를 길게 할수록 오차는 줄어든다!
  • 56. 서비스 특성마다 다르다만 실험데이터에서 100개의 signature면 root mean square error 원본과 차이 RMSE 0.03 유지 충분히 근사한다! 이정도면 쓰바라시
  • 57. 구글 논문과 반대의 어프로치 구글 논문 새로운 방법 signature를 소량 생성 적절히 충돌시켜 미리 clustering 하자
             실제 계산은 
 click stream을 사용함 signature를 대량 생성 충돌을 피하고 실제 계산은 click stream대신 signature overlap을 사용함
  • 58. 이 방법의 장점 다량의 건수를 in-memory에 fit가능 자료구조상 실시간 반영 추천이 가능
  • 59. + 다량의 건수를 in-memory에 fit가능 
                    앵간하면 전부 disk io없이 계산
             + 메모리 얼마가 필요한지 예측 가능
                         예전에는 인기아이템의 클릭스트림이 얼마나 용량을 차지 할지 몰랐다. 
  • 60. item한개가 4byte짜리 시그니처 100개 , 개당 부가 공간 200 byte 더 있다 치자 
        100 x 4 + 200 = 600 byte 
         메모리 1G가 있으면 1024^3 / 800 = 1,789,569
        1기가당 180만 종류 item의 click stream을 메모리에 들고 있을 수 있다! (그런 규모 많이 없다)
  • 61. +우리를 느리게 만드는 건 대량 배치 Job “이거 다 돌아야 반영되어요” +빚은 쌓지 말고 짬짬히 분할상환하는게 좋다. “새로운 클릭이 쌓이면 그거 포함해서 다시 전부 돌려야 하지 않나요?”, “방법이 있습니다”
  • 62. 새로운 click이 일어나면 기존에 계산해 놓은 signature버리고 다 새로 계산 해야 하나? No! minhash는 ‘min 함수’의 ‘chain’이다. 때문에 좋은 성질을 가지고 있다.
  • 63. min(A,B,C) = min(min(A,B),C)
  • 64. Associative property 결합법칙 새 데이터가 들어오면 누적 적용하면 된다 Idempotence 멱등법칙 에러나도 안전하니 다시 적용하면 된다.
  • 65. 처음부터 지금까지 배치로 돌린것 = 맘 편하게 계속 누적시켜 적용한 것 전체 배치는 부담되지만, 조각들은 가볍고 빠르다! click이 들어올때마다 지금 적용하자!
  • 66. 이 성질을 이용하면 high TPS도 대응 save minhash(110)[1 DB write] = load minhash(100)[1 DB read] x compute minhash(101~110)[input buffer] old minhash new new new local minhash memorystorage updated minhash 급격히 들어오면 모아서 그것만으로 선처리한다. micro batch 뒤에 합쳐도 순차적으로 처리한 것과 같다. (결합법칙)
  • 67. 자~ 자료는 
 아주 작고 단단하게 잘 만들었다. 하지만 이것의 계산 어떻게 최적화 안될까?
  • 68. S1 S2 … Sn 자료는 잘 줄였다. S1 S2 … Sn S1 S2 … Sn S1 S2 … Sn S1 S2 … Sn 하지만 n^2의 비교? item A item B item C item D item E
  • 69. 이를 해결 하기 위해 Secondary Index를 만든다.
  • 70. item A item B item C 923 1032 58 74 87 1032 123 80 923 872 58 80 Sig1 Sig2 Sig3 Sig4 이렇게 signature로 표현 될 때 Secondary-Index KV Storage Sig위치와 값 pair를 Key로 하고 그걸 가지는 item리스트를 Value Key Value Sig1-923 A-C Sig2-872 C sig3-58 A-C sig4-80 B-C A : 2회/4sigs B : 1회/4sigs A : 0.5 B : 0.25 Value에 등장한 item이름 횟수만큼이 내 sig와 겹치는 갯수이고 = jaccard에 비레 =
  • 71. Secondary Index lookup만으로 Jaccard를 계산할 수 있다. 오오오~!
  • 72. requirement: minhash재계산 업데이트마다 2nd idx도 매우 매우 잦은 업데이트 = 반드시 메모리에서 처리되야 겠구나!
  • 73. Large Secondary-Index는 어떤 저장장치가 적절할까? Redis
  • 74. Key Value Sig1-923 A-C Sig2-872 C sig3-58 A-C sig4-80 B-C 이러한 membership 정보를 저장해야 한다. REDIS의 많은 자료구조중에 뭘 써야 할까?
  • 75. Redis Data structure candidates Strings Sets - support add, remove, union, intersection - plain K/V 좋아보인다! VS
  • 76. 사실 멤버십 정보를 string으로 만들어 저장하는 건 귀찮다. sig45 Tom Jerry Robert Jack string으로 만들어 저장 “[Tom, Jerry, Robert, Jack]” 가져온 것 다시 복호화 json.dumps(data) json.loads(data_str) [write] [read] “[Tom, Jerry, Robert, Jack]”
  • 77. 하지만 승자는 String이다. 왜?!
          Order! O(1) vs O(N) In [24]: %time gs.load_benchmark('user','key') CPU times: user 0.32 s, sys: 0.03 s, total: 0.34 s Wall time: 0.42 s In [25]: %time gs.load_benchmark('user','set') CPU times: user 32.34 s, sys: 0.13 s, total: 32.47 s Wall time: 33.88 s 1) 이 경우에서는 String이 Set보다 훨씬 좋다. string set
  • 78. ‘redis string’ 은 mget 명령이 있습니다. (multiple get at once) N call round trip -> 1 call In [9]: %timeit [redis.get(s) for s in sigs] 100 loops, best of 3: 9.99 ms per loop In [10]: %timeit redis.mget(sigs) 1000 loops, best of 3: 759 us per loop 2)
  • 79. 3) string 은 압축을 적용하기에도 편합니다. = 메모리에 더 많이 들고 있을 수 있단 듯이죠 compress speed(μs) 0.0 35.0 70.0 105.0 140.0 snappy zlib 134.0 17.3 size(%) 0% 25% 50% 75% 100% snappy zlib 40% 70% snappy쓰면 압축했는지 표도 안날정도로 빠름
  • 80. redis 는 pipe기능을 이용해 transaction 이 됩니다. 요걸로 set의 기능들을 흉내 내는게 가능하죠 4) item A 923 1032 58 74 item B 87 1032 123 80 item C 923 973 58 80 sig2-1032 sig2-973 A-B C Secondary-Index 973 sig2-1032 sig2-973 B A-C sig1 sig2 sig3 sig4 key: pos-value value: member case) sig2-1032의 A가 빠지면서 sig2-973에 추가 - atomic하게 minhash signature 업데이트
  • 81. 가질 수 있는 궁금증 2nd index key space가 걱정입니다? 이론적으로는 hash max val * sig cnt의 key가 필요 hash max를 433,494,437인 Fibonacci primes을 쓰고 100개의 signature를 만드는 경우 이론적으론 433,494,437,00 개의 key영역 필요. 하지만.
  • 82. minhash 는 min의 chain이기 때문에, 
 시간이 지나면 작은 영역에 수렴 100 15,082,312 4334944370 sigcnt 43,349,443,700 0개의 member를 가진 key는 수시로 삭제 example case)
 3,727,344 products, 
 100 sig => 15082312 keys 압축적용 후, KV모두 메모리 2G 미만 차지
  • 83. REDIS를 이용하면 transaction이 지원되면서 빠른 update가 되는 Secondary Index가 가능해집니다.
  • 84. 정리
  • 85. minhash를 min하게 유지시킨다.
          item Z에 user click이 발생했을 때 반영법 Z 183 1032 942 80그것의 signature 로딩 click 의 minhash계산 87 2043 123 300click 새롭게 얻은 가장 낮은 값으로 signature 및 2nd index변경 new 87 1032 123 80 click 발생시 조금씩 바로 처리
  • 86. 어떤 item Z와 닮은 것을 찾아야 한다면? Secondary Index 가 있을 때 추천 flow item Z 87 1032 123 80 그것의 signature 로딩 Sig1 - 87 Sig2 - 1032 Sig3 - 123 Sig4 - 80 A-B-D-F-Z C-G-Z A-B-D-Z B-D-F-Zredis.mget으로 한방에 가져옴 갯수만 카운트하면, 찾기끝 A:2/4 =0.5 B:3/4 =0.75 C:1/4 =0.25 D:3/4 =0.75
  • 87. 코끼리는 냉장고에 들어갔는가?
          필요한 Mem Size - minhash용1G / 2ndi ndex용 2G  / 기타1G 필요한
          CPU Power : REDIS 1core / minhash 유지 1core / 추천계산 1core
  • 88. 요정도면 되겠습니다.
  • 89. 사실 진정한 추천엔진은 이런 단순한 Memory based 말고도 굉장히 많은 요소들과 
 (ALS, NMF, Markov Chain등등) 적절한 프로파일링들이 잘 섞여야 합니다.
  • 90. 그럼 이것은 낚시냐? No!
  • 91. 99.9% 정확도로 다른 큰 이득을 취하는 것 1169KB 51KB logo.bmp logo.jpg 1/


    • 저작자표시 비영리

    'Machine Learning & Data Mining' 카테고리의 다른 글

    Deep learning 기반 T map POI 추천 기술개발 사례  (0) 2015.09.22
    윤영식_ 'Growth Hacker/Machine Learning'  (0) 2015.09.22
    Machine Learning 스터디 (1) Machine Learning이란? (펌)  (0) 2015.08.24
    쉽게 풀어쓴 딥 러닝의 거의 모든 것(펌)  (0) 2015.08.23
    수학을 포기한 직업 프로그래머가 머신러닝 학습을 시작하기위한 학습법 소개 (펌)  (0) 2015.08.23
    Posted by Name_null
    2015. 9. 22. 00:34
    Data Analtytics

    Data Mining 개론_Kwang Woo NAM

    http://www.slideshare.net/kwnam4u/presentations?order=latest






    Data Mining 01 - 개요

    • (p11) Data Mining 기법의 분류 
      • 발견할 지식의 종류에 따라 
        • Association(연관성 발견) 
        • Characterization(특성발견)
        • Classification(분류)
        • Summarization(요약)
        • Clustering(군집화)
        • Sequential Pattern Discovery(연속패턴발견)
        • Trend(경향 발견)
        • Deviation Detection(추세변화발견)  
      • (p22) 집단지성이란? Collective Intelligence(集團知性)
        • 다양한 사고활동을 하는 개인들이 서로 협업하거나 경쟁을 통하여 얻게 되는 집단적 지적 능력
          • 미국의 곤충학자 윌리엄 모턴 휠러(William Morton Wheeler)가 1910년 출간한 《개미：그들의 구조·발달·행동 Ants：Their Structure, Development, and Behavior》에서 처음 제시
          • 개체로는 미미한 개미가 공동체로서 협업(協業)하여 거대한 개미집을 만들어내는 것을 관찰하였고, 이를 근거로 개미는 개체로서는 미미하지만 군집(群集)하여서는 높은 지능체계를 형성한다고 설명 22
          • google, Netflix, Amazon 추천 시스템 등. 개체가 그것을 인식하는 지는 중요하지 않음 


    Data Mining 02 - 추천 시스템 만들기

    • (p3) 추천 시스템의 개요
      • 협업 필터링(Collaborative Filtering)
      • 많은 사용자들로부터 얻은 기호정보(taste information)에 따라 사용자들의 관심사들을 자동적으로 예측하게 해주는 방법(wiki)
        • 정보 과잉 문제를 해결하기 위한 정보 필터링의 주요 기법
        • 큰 무리의 사람들을 검색해서 유사한 취향을 가진 작은 집합을 발견하는 알고리즘 
          •                                                    Active User의 정보
          •                                                                |
          • User Activity Repository  --> Collaborative Filtering -->  후 보  -->  선택 --> Active User
                            |-------------------------  영향 또는 반영-----------------------------------|             
      • (p4) 추천 시스템의 개요
        • Collaborative filtering의 방법
          • 아이템 기반의 필터링(amazon)
            • Step 1 : Rating Process • 아이템 간의 상관관계를 결정하는 아이템 매트릭스(item-item matrix)를 만든다.
            • Step 2 : Predicion Process • 매트릭스를 사용하여 최신 사용자의 데이터를 기반으로 그 사용자의 기호를 유추한다.  
      • (p6) 선호 정보(preferences)의 수집
        • Preference 정보의 범위와 Rating 방법의 예
          • Recommendations.py
          • 영화 평론가 평점 Preferences를 0과 1사이의 실수로 표현 – Python을 이용한 Preference 정보의 접근 구현  
    • (p7) 유사 사용자 찾기(Finding Similar User)
        • Similar User
          • 각각의 사람을 다른 모든 사람들과 비교하여 유사한 취향을 갖는 사용자를 계산
          • Euclidean distance score와 Peason correlation score
          • 유클리디안 거리 점수(Euclidean Distance Score) 
            • Euclidean 공간 
            • 우리 머리속에서 상상하는 이상적인 평면 • 평행선 사이의 거리는 항상 일정하며 한직선에 대해서 어떤 한점을 지나는 평행선은 하나밖에 없는 평면
            • 즉, 공간상에 전혀 구부러짐이 없고 반듯하다고 생각되는 평면, 하지만 실제 공간상에서는 이러한 평면은 존재하지 않는다고 알려져있음
            • 공간은 중력에 의해 구부러진채로 존재 <영화 Snakes와 Dupree 점수로 본 평론가들간의 유사성 계산 
      • (p10) 유사 사용자 찾기(Finding Similar User) 
        • 피어슨 상관 점수(Pearson Correlation Score)
          • 두 개의 데이터 집합이 한 직선으로 얼마나 잘 표현되는가를 나타내는 측정값
          • 잘 정규화되지 않은 데이터의 경우에 좋은 결과를 제공, 두 변수간의 연관 강도 측정용 지표로서 1과 -1사이의 값
          • 1은 완전히 연관되어 있음, 0은 전혀 연관 없음, -1은 완전 반대로 연관되어 있음 
          • Best-fit -차트내의 모든 항목들과 가장 가까운 직선
          •  - 두 평론가가 모든 영화에 동일하게 평가했다면 대각선이 되며, 모든 영화 는 직선상에 존재 Seymour와 Lasalle간의 피 어슨 상관 점수는 0.4정도 <낮은 상관 점수를 갖는 평론가의 예> 
      • (p19) 항목 추천(Recommending Items)
        • 유사성 판단을 통한 추천 방법
        • 나와 가장 유사한 패턴을 갖는 평점을 기준으로 다른 영화를 추천할 수 있음
        • TopMatches 함수를 이용하여 Similarity 판단 
      • (p23) delicious.com 링크 추천 만들기



    Data Mining 03 - 군집 발견 

    • (p2) 데이터 클러스터링(군집화,Data Clustering) 개요
      • 군집 분석(Clustering Analysis)
        • 모집단 또는 범주에 대한 사전 정보가 없는 경우, 주어진 관측값들 사이의 거리 또는 유사성 을 이용하여, 전체를 몇 개의 집단으로 그룹화 하는 분석법
        • 각 집단의 성격을 파악함으로써 데이터 전체의 구조에 대한 이해를 돕고자 하는 분석법
          • 분류 분석(Classification Analysis,9장)과는 달리 목표 변수를 설정하지 않음.
          • 따라서, 분류는 supervised learning[감독학습]이라고 하고, 군집분석은 unsupervised learning[무감독학습]이라고도 함
          • 활용 예: 문서 분류, 고객세분화를 통한 타겟 마케팅 등
    • (p3) 데이터 클러스터링(군집화,Data Clustering) 개요
      • 데이터 군집화를 위한 변수의 예 
        • 인구통계적 변수 (성별, 나이, 거주지, 직업, 소득, 교육, 종교 등)
        • 구매패턴 변수 (상품, 주기, 거래액 등)
        • 생활패턴 변수 (라이프스타일, 성격, 취미, 가치관 등)
      • 변수간의 거리 또는 유사성으로 군집화 
      • 주요 군집 분석 알고리즘
        • K-Means - 꽃받침과 꽃잎 너비 변수를 이용한 군집화 K-Mean을 이용
        • EM(Expectation Maximization)  - EM 군집 (백화점 고객 데이터)
      • 군집분석의 특징
        • 군집분석은 자료의 사전정보 없이 자료를 파악하는 방법으로, 분석자의 주관에 결과가 달라질 수 있음
        • 특이값을 갖는 개체의 발견, 결측값의 보정 등에 사용될 수 있음
        • 변수의 선택이 중요
    • (p7) 블로거 군집화 : 단어 벡터
      • 블로거 데이터 상위 120명의 블로거
        • 각 블로그안에 출현하는 특정단어들의 횟수
        • 생성해야 할 데이터의 예 : 블로거와 블로그 단어의 빈도수 데이터
    • (P8) 블로거 군집화 : 단어 벡터
      • 블로그 군집화의 단계 URL의 데이터를 가져와서 Word Count blogdata.txt 
      • 데이터마이닝 : Collective Intelligence 8 Feedlist.txt Rss url 목록 파일 
      • 고빈도/저빈도 단어 필터링 Web RSS 블로그-단어 행렬을 저장 블로그
      • 단어벡터 데이터 generatefeedvector.py 계층적 군집화 알고리즘 clusters.py 적용
    • (p13) 블로거 군집화 : 피드 내 단어 수 세기
      • 고빈도/저빈도 단어 필터링 - 단어 필터링의 이유
        • 고빈도 단어 : the, a 등 • 모든 블로그에 거의 공통적으로 나타나는 단어는 군집화 변수가 되기 어려움 
        • 저빈도 단어 : slang 또는 특수어
        • 거의 한두번의 출현 빈도를 갖는 단어들은 다른 블로그와 유사성을 판단하기 어려움
        • 필터링 factor – 다음 예제에서는 10%이상 50%이하로 주고 있으나, 환경에 따라 변경 가능 
    • (p15) 블로거 군집화 : 계층적 군집화 
      •  계층적 군집화란 - 가장 유사한 그룹을 계속 병합하여 그룹 계층을 만드는 방법
        • 가까운 관측값들 끼리 묶는 병합(agglomeration)방법과 먼 관측값들을 나누어가는 분할(division) 방법이 존재
        • 계층적 군집에서는 주로 병합 방법이 사용됨
    • (p18) 블로거 군집화 : 계층적 군집화
      • 유사성 거리 계산
        • Pearson 계수를 이용한 상관 점수 계산 – 1.0이면 완전 유사, 0이면 전혀 관계없음, -1.0이면 완전 반대
    • (p26) 블로거 군집화 : 세로줄 군집화(Column Clustering)
      • 세로줄 군집화
        • 예 : 함께 구매하는 물건 전시 선반 찾기
        • 예 : 블로그간 군집화가 아니라, 블로그-단어간 군집화
    • (p29) -평균 군집화(k-means clustering) 
      • 계층적 군집화의 문제점
        • 트리 형태로 계층을 구성하긴 하나, 뚜렷한 그룹으로 분할하진 못함
        • 매우 느리게 동작. 모든 항목마다 계산이 필요하고 항목들이 병합될 때에 재계산 필요
      • K-평균 군집화의 특징  (wiki)주어진 데이터를 특정 성질에 기초해서 k개의 묶음(cluster)로 나누는 방법중 하나
        • K개의 사전에 지정된 군집의 개수를 지정하고 군집화하므로 계층적 군집화 보다 빠름
        • 단점 – 전역 최적값을 보장하지 않음 
          • 맨 처음 나눈 방법에 상당히 의존한 결과를 생성하므로 최적값에 비해 매우 나쁜 값을 얻을 수 있음 
        • 알고리즘이 빠르기 때문에 서로 다른 초기값으로 여러 번 시도하여 좋은 클러스터를 선택
          • 알고리즘을 시작할때 사전 지식없이 k값을 정해주어야 하므로, 데이터가 자연스럽지 않게 분포되는 결과를 얻을 수 있음
    • (p30) 평균 군집화(k-means clustering) 
      • 알고리즘 
        • 무작위로 선정된 k개의 중심점(centroid)을 선정
        • 이 중심점에서 각 객체들의 거리를 계산하여 결정
        • 최소 거리를 갖는 객체에 기반하여 그룹화
    • (p35) 2차원으로 데이터 보기 
      • 다차원 비례 축소법(multidimensional scaling) 
      • 데이터의 유사성이나 비유사성을 탐색하기 위하여 자료와의 적합도가 유지되는 한도내에서 2-3차원의 도표로 차원을 낮추어 보여주기위한 테크닉들의 집합(wiki) 
        • 군집화 변수 등은 여러 개의 요소에 의해 결정되므로 사람이 쉽게 인식가능한 2-3차원 도표로 표현하기 어려움
        • 정보 가시화(information visualization)에서 사용되며, 다차원 비례 축소법에 의해 그려지는 지도를 다차원 인식지도(perceptual map)이라고 함
      • 다차원 비례 축소법(multidimensional scaling)의 예
        • 상품과 상품 간의 관계 factor => 날씨, 일자, 온도, 고객 성향 등 다양 => 가시화 문제 발생
        • 주요 factor를 단순화하여 2-3차원으로 변환하여 visualization 



    Data Mining 04 - 검색과 Ranking 

    • (p3) 검색엔진
      • 검색엔진의 동작 순서
        • 웹 크롤링(Web crawling) – 웹 로봇
        • 인덱싱(Indexing)
        • 검색(Searching) 
    • (p4) 검색엔진 : 웹로봇
      • 웹 로봇의 정의
        • 지정된 URL 리스트에서 시작하여 웹 문서를 수집하고, 수집된 웹 문서에 포함된 URL들의 추출과정과 새롭게 발견된 URL에 대한 웹 문서 수집 과정을 반복하는 소프트 웨어
        • 웹 Web Robot, Spider, Crawler, Wanderer 
    • (p9) 단순 Crawler 구현
      • urllib2를 이용한 구현
      • 지정한 url을 다운로드하여 저장할 수 있도록 해주는 라이브러리 
    • (p13) 색인하기
      • 색인 데이터의 저장
      • SQLite를 이용하여 저장 – Pysqlite
      • 스키마 설정하기  
    • (p19) 검색하기 
      • 검색어를 포함한 URL 찾기 
    • (p23) 내용기반 랭킹
      • 내용기반 랭킹의 점수 지표(traditional approach) 
      • 단어빈도 – 검색어 안에 있는 단어들이 문서에 출현하는 횟수 – 문서의 적합도를 결정
      • 문서내 위치 – 다양한 단어의 위치에 대한 가정을 이용 
        • 한 문서의 핵심주제는 문서 도입부에 있을 가능섶이 높다
        • 중요한 단어일수록 글자체가 크다
        • Keyword 또는 head에 사용된 단어는 중요하다 
      • 단어거리 – 검색어 안에 여러 단어가 있을 경우 문서에서 근접해서 출현해야 한다
    • (p25) 내용기반 랭킹 : 정규화 함수
      • 숫자 점수의 정규화
      • 랭킹을 위해 다양한 점수화 factor를 도입
      • 다양한 factor들간의 통합을 위해 모든 점수를 동일한 범위와 방향으로 정규화함
        • 단어빈도, 문서내위치, 단어거리 등등의 factor 각각을 0..1의 값으로 변환
        • 정규화 방법- 최적 결과를 1로 가정하고 정규화 
    • (p34) 유입링크 사용하기 : 페이지랭크 알고리즘
      • 페이지랭크(PageRank)의 의미
        • PageRank 알고리즘을 이용하여 웹 페이지의 랭킹을 부여(래리 페이지)  
          • 웹 페이지의 중요성을 외부에서 그 웹 페이지를 가르키는 링크(역링크)를 기반으로 계산하는 알고리즘
          • 즉, 역링크를 많이 가지고 있는 웹페이지 일수록 중요하다는 전제하에 페이지의 순위를 계산
      • 페이지의 중요도
        • 그 페이지에 대한 링크를 가진 다른 페이지의 중요도와 각각의 다른 페이지들이 가지고 있는 링크 수로 계산
    • (p41) 클릭 학습 : 클릭 추적 네트워크의 설계
      • 사용자 선택의 Feedback
      • 검색엔진이 제공한 검색결과에 대한 선호도 정보(검색 결과중 어떤 것을 클릭했는가?)를 이용하여 검색엔진의 검색결과 ranking에 이용
      • Perception Network 기반의 클릭추적 네트워크
        • MLP(MultiLayer Perception) : 다층적 인식망 – 은닉층(hidden layer)과 쿼리층(query layer) Query layer hidden layer output layer 
    • (p47) 클릭 학습 : 전방전파
      • 전방 전파
        •  단어를 입력으로 취해 네트워크 내에 연결들을 활성화 시키고 URL에 대한 출력 집합을 제공하는 함수
        •  각 노드가 입력에 반응하는 정도를 표시하는 함수 선택 • 쌍곡선 탄젠트(hyperbolic tangent) 함수 사용 Tangent 함
    • (p50)  클릭 학습 : 전방전파
      • 전방전파 알고리즘 
      • 은닉층에 있는 모든 노드들마다 루프를 돌면서 입력층의 모든 출력들과 링크들의 연결강도를 곱한후 더하며 동작



    Data Mining 05 - 문서 filtering  

    • (p3) 검색엔진
      • 검색엔진의 동작 순서


    저작자표시 비영리

    'Data Analtytics ' 카테고리의 다른 글

    kyumin choi - 추천시스템  (0) 2015.09.22
    [142] 이커머스 회사가 반드시 측정해야 할 9가지 데이터 (9 DATA SETS EVERY ECOMMERCE COMPANY SHOULD MEASURE)  (0) 2015.03.10
    How to Become a Data Scientist from ryanorban  (0) 2015.03.01
    실리콘밸리 Data Scientist의 하루 (펌)  (0) 2015.03.01
    어떻게 하면 데이터 사이언티스트가 될 수 있나요? from Yongho Ha  (0) 2015.02.15
    Posted by Name_null
    2015. 8. 24. 13:19
    Machine Learning & Data Mining

    Machine Learning 스터디 (1) Machine Learning이란? (펌)

    Machine Learning 스터디 (1) Machine Learning이란?

     | Comments

    들어가며

    Machine learning이라는 것을 접한지 어느새 거의 1년 반이 넘는 시간이 지났다. 많은 Machine learning 관련 글들을 써왔지만, 제대로 정리된 글이 없어 근래에 다시 머신러닝에 대해 공부를 하는 김에 제대로 정리해보기로 했다. 이번 8월부터 연구실에서 머신러닝 스터디를 하기로 한 김에 새로 다시 읽고 있는 Bishop 책을 중심으로 글을 작성할 것 같다. 나는 Machine Learning을 차근차근 공부하기에 적절한 자료가 없는 것이 항상 아쉬웠다


    저작자표시 비영리

    'Machine Learning & Data Mining' 카테고리의 다른 글

    윤영식_ 'Growth Hacker/Machine Learning'  (0) 2015.09.22
    실기간 추천엔진 머신 한대에 구겨넣기 (펌)  (0) 2015.09.22
    쉽게 풀어쓴 딥 러닝의 거의 모든 것(펌)  (0) 2015.08.23
    수학을 포기한 직업 프로그래머가 머신러닝 학습을 시작하기위한 학습법 소개 (펌)  (0) 2015.08.23
    나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개 (펌, 조대협 블로그)  (0) 2015.08.23
    Posted by Name_null

    티스토리툴바