空놀이

드디어 마지막 장

1. 베이지안 분류기

(1) 감독형 기법이므로 학습되어야 함

(2) 분류기는 보아온 모든 특성과 특성이 특정 분류에 연계될 숫자 확률을 추적하여 학습된다.

(3) 특정 분류에 관한 문서가 주어진 단어를 가질 확률을 생성한다.

(4) 장단점

A. 장점 

- 큰 데이터 세트를 학습하고 질의하는 속도가 매우 빠르다. 증분 학습이 필요한 경우에 특히 장점이 있다. 

- 실제로 학습한 것에 대한 해석이 다소 단순하다. 각 특성의 확률이 저장되었기 때문에 언제나 데이터베이스를 살펴볼 수 있다.

B. 단점

- 특성의 조합에 기반을 두어 변화하는 출력을 다룰 수 없다.

2. 의사결정 분류기

(1) 학습하기 : 가능한 되적의 방법으로 각 단계에서 데이터를 분리할 속성들을 선택하면서 트리를 만든다.

(2) 장단점

A. 장점

- 학습 모델을 해석하기 쉽다.

- 중요한 요인들을 트리의 상단에 올려놓는다.

- 변수의 상호 작용을 쉽게 다룰 수 있다.

B. 단점

- 회귀트리는 최저 변위를 가지는 평균값으로 데이터를 분할하지만 만일 데이터가 복잡하다면 트리는 정확한 의사결정을 하기 위해 아주 거대해져야 한다.

- 증분 학습을 지원하지 않는다.

3. 신경망

(1) 신경망은 분류와 숫자 예측 문제에 모두 적용할 수 있다.

(2) 분류기

- 가장 높은 숫자를 가진 링크를 사용자가 클릭할 만한 것으로 예측해 모든 링크마다 숫자를 제공

(3) 다층 퍼셉트론망

(4) 장단점

A. 장점

- 복잡한 비선형 함수도 처리할 수 있고 입력들 간의 의존관계도 밝힐 수 있다.

- 증분학습도 가능하며 필요한 공간도 적다.

B. 단점

- 수백 노드와 수천 시냅스를 가질 수 있어 네트워크가 제공한 해답을 어떻게 만들었는지 판단하기 불가능하다.

- 특정 문제에 대한 학습 속도와 네트워크 크기를 선택할 결정적인 규칙이 없다.

4. 지지벡터머신

(1) 대부분의 데이터를 깨끗이 분리하는 선을 찾는다.

(2) 커널 트릭

- 데이터를 다른 축으로 변환하여 선형으로 구분이 되지 않는 걸 선형으로 구분할 수 있게 도와 준다.

(3) LIBSIM 사용하기

(4) 장단점

- 가용할 데이터가 많은 문제에 좀 더 잘 적용된다. 블랙박스 기법이다. 고차원 공간으로 변환하기 때문에 분류하는 방법을 이해하기 어렵다.

A. 장점

- 아주 강력한 분류기. 더 정확하고 더 잘 동작함

B. 단점

- 최적 커널 함수와 이 함수의 인자들이 모든 데이터 세트마다 약간씩 달라 매번 이들을 찾아야 한다.

워낙에 요약된 내용들이라 블로그에 정리할 필요가 없는 것 같아 이만 줄인다.

- django : lastframework 

- tasty pi

1. Genetic Programming

가장 좋은 걸 찾은 후 진화할 때는 단순히 복사와 변경이 있다.

두가지 방법의 진화가 있다.

간단한 방법은 mutation(돌연변이) - 랜덤하게 조금만 변경

crossover - 일부를 가장 좋은 프로그램과 교체함

2. 유전자 프로그래밍과 유전자 알고리즘의 차이

(1) 유전자 알고리즘은 정해진 알고리즘의 파라미터만 찾음

(2) 유전자 프로그래밍은 알고리즘과 파라미터 둘 다를 찾음

예)

1. 테스트할 함수를 만들고 그에 대한 입력과 아웃풋 값을 테스트셋으로 200개 정도 저장한다.

2. 유전자 알고리즘을 이용하여 입력과 아웃풋이 정확히 일치하는 함수를 찾아내야 한다.

3. 임의로 함수를 몇개 만든 후 같은 입력을 주고 아웃풋을 테스트셋의 아웃풋과 비교하여 성능을 측정한다.

4. 유전자 알고리즘을 통해 돌연변이, 교배등을 통해 함수들을 만들고 아웃풋과의 비교값이 가장 작은 것을 찾는다.

5. 차이가 0이 되면 제대로 된 함수를 찾은 것이다.

6. 함수안에 쓸데 없는 공식도 들어갈 수 있으니 제거하는게 필요하다. 예) 0 + 0

- 지지벡터머신( SMV: Support Vector Machines)

01. 중매 데이터 세트

02. 데이터를 다루는 어려움

r.data[0] : 남

r.data[1] : 여

특성 : 비선형(nonlinearity), 변수 간 상호작용(interplay)

*matplotlib를 사용해서 그래프를 그렸음. 나중에 그래프 그릴 때 참조

데이터를 그래프로 확인해 보니 남녀는 각자의 나이 법위 내에서 만나는 특성이 보임

- 의사 결정 분류기 사용: 다소 복잡한 관계를 보이는 다중 숫자 입력들을 가진 문제에서 분류를 결정할 때 종종 잘 동작하지 않는다.

03. 기본 선형 분류

범주의 평균점을 계산

(1) 평균점 계산으로 두 점을 찾음 

- 불일치의 평균과 일치의 평균을 찾고 가운데 선을 그어서 일치와 불일치 쌍을 나누도록 한다.

(2) 데이터를 나누는 선을 찾음

(3) 유클리디안 거리를 사용해도 되지만 추후 확장을 고려하여 벡터와 백터 내적을 사용함

벡터 내적 : 가까울 수록 1에 근접, 0이면 수직이기 때문에 가장 다름 -1이면 멀다.

책에서는 각 평균점을 연결한 선과 평균점의 중간점과 분류할 데이터를 연결한 선을 벡터 계산하여 분류할 데이터가 어디에 가까운지 평가한다.

하지만 기본 선형 분류는 완벽히 제대로 된 분류를 하지 못하기 때문에 나중에 커널 트릭을 사용한다.

04. 분류 데이터의 특성

데이터를 분류기에 유용한 숫자로 바꿀 방법이 있어야 한다.

(1) 예 아니오 질문

(2) 관심 목록

(3) 야후 지도를 사용한 거리 계산

- 지오 코딩 API사용

(4) 새로운 데이터 세트 생성

05.  데이터 축척 조정

- 최저값을 0으로 최고값을 1로 그 다른 값을 0과 1사이의 값으로 비율을 조정함

06. 커널 기법 이해

값을 제곱하여 선형으로 분류할 수 있게 만듬

(1) 커널 트릭

- 방사 함수(radial-basis function) : 백터내적과 비슷해서 두 벡터를 받아 값을 리턴한다.

이것은 벡터내적가 달리 선형적이지 않아 더 복잡한 공간으로 매핑될 수 있다.

gamma를 바꿔가면서 적당한 값을 찾아야 한다.

07. 지지벡터머신

두 범주를 가르는 직선을 찾는 다른 경우를 보자.

각 범주의 평균점들과 평균점들을 포함하는 직선

각 범주 내 항목들에 걸친 평행선 중에 가장 멀리 떨어진 선을 구분선으로 선택

*지지벡터 : 선 근처의 점들

*지지벡터 머신 : 지지벡터를 찾아 이들을 이용해서 구분선을 찾는 알고리즘

ex) 얼굴 표현 분류, 침입 탐지, 단백질 구조 예측, 필기체 인식, 지진 발생 시 피해 규모 판단 등

08. LIBSVM 사용

SVM모델을 학습시키고 추정하며 데이터 세트 내 예측을 검증하는 오픈소스 라이브러리

svm_parameter : c - sort margin

중고나라 물품의 가격을 산정할 때

가격을 쉽게 가져올 수 있는가?

제품의 상태는 어떻게 판단하나?

A/S 

가격을 예측하는 모델을 만든다.

베이지안 분류기나 의사결정트리 SVM은 가격과 같은 많은 이질적인 속성들에 기반을 둔 숫자 데이터를 예측하기 어렵다.

가격 예측에는 여러 변수들의 최적 가중치를 찾아야 하는데 그것을 자동으로 결정하기 위해 5장에서 개발한 최적화 기법들을 사용

01. 예제 데이터 세트 만들기

와인을 이용한 가격 예측

02. kNN

- k-nearest neighbors : 가장 비슷한 것 몇 개를 찾아 가격들이 대강 같다고 가정하는 것. 

(1) 이웃 개수

- k : 마지막 결과를 얻기 위해 평균을 낼 물품의 개수

- 노이즈를 추가함 : 몇 사람은 싸게 구입할 것이고 어떤 사람은 비싸게 구입할 수도 있기 때문이다.

- 기술 변수를 적당하게 추가해야 한다. 최적화 기법으로 물품 개수를 선정해야 한다.

(2) 유사도 결정하기

- 유클리디안 거리를 사용한다.

* 다른 곳에서는 피어슨 상관계수, 코사인(자카드, 맨해튼 거리)(?) 사용 가능

* 어떤 걸 사용할 지에 대해서는 좀 알아봐야한다.

kNN은 계산량은 많지만 새로운 데이터가 추가될 때마다 새로 학습하지 않아도 되는 장점이 있다.

03. 물품 가중치

- 이유 : 적정한 거리의 군집을 만들기 위해서 가까운 건 더 가깝게 만들어 주고 먼 것은 더 멀게 만들어 주기 위해서

거리에 가중치를 주는 방법 3가지

- 역 함수 : 거리 값을 1에서 나눈다. 노이즈에 너무 민감할 수 있다.

- 빼기 함수 : 뺀 값이 0보다 작으면 0으로 한다. 하지만 0이 되는 경우 추천을 하지 못하는 경우 발생

- 가우스 함수 : 빨리 계산하기가 어렵지만 적당한 가중치를 만들어 줌

- 가중 kNN

결과들의 평균을 계산하는 대신에 가중 평균(weighted average)을 계산한다.

가중 평균은 각 물품의 가중치(여기서는 가우시안을 사용)에 값을 곱한 후 서로 더하고, 그것을 전체 가중치의 합으로 나눠서 계산

04. 교차 검증(cross-validation)

데이터를 학습 세트와 테스트 세트로 나누는 기법들을 총칭하는 이름

전체 데이터의 5% 정도를 테스트 세트로 만든다. 그러면 나머지 95% 학습 세트가 된다.

실제 결과와 예측의 차이를 구한다.

05. 이질 변수

(1) 축척 조정

거리를 실제 값에 근거하는 방법이 아니라 값을 정규화해서 그 값들이 모두 같은 공간에 있는 것처럼 만드는 방법

06. 축척 최적화

어닐링 최적화를 시도하여 교차 검증이 최적값을 될 수 있는 변수들의 가중치를 찾는다.

07. 불균등 분포

- 어디서 구매했는지에 따라 가격이 달라질 수 있으므로 해당 위치의 데이터를 더 면민히 관찰해야 한다.

- 확률 밀도 추정하기

단일 가격을 예측하기 보다는 물품이 특정 가격 범위 내에 떨어질 확률을 계산

뒷부분엔 이베이를 활용하여 가격을 예측하였다.

* 소감

* 의사 결정 트리 * 

의사결정트리의 목적 : 사용자가 유료 고객이 될 가망성을 예측. 사용자가 고객이 될 것임을 시사하는 요소를 알았다면 이 정보를 이용해서 광고 전략을 짜거나 사이트의 특정 측면에 쉽게 접근할 수 있게 만들거나 유료 고객의 숫자를 늘리는 데 도움이 되는 다른 전략들을 사용할 수 있다.

 - 해석이 쉬움

01. 가입 유형 추정

a. 서버 로그에서 방문 전 사이트, 지정학적 위치, 로그인 전에 본 페이지 수 등과 같은 정보를 모은다.

02. 의사 결정 트리 소개 

a.  단지 각 질문에 올바른 대답을 하면서 트리 내 경로를 따라 내려가면 결국 해답에 이르게 된다.

03. 트리 학습

a. 이 장에서는 CART(Classification and RegressionTrees)란 알고리즘 사용

- 루트 노드를 만든다.

- 테이블 안의 모든 관찰들을 고려해서 데이터를 분리하는 최적의 변수 선정

- 변수 선정을 위해 분리할 만한 조건을 가진 모든 변수들을 살펴본다.

- 사용자가 추정하기 편한 방법으로 결과물(사용자가 어떤 서비스에 가입할지)을 분할할 조건을 찾는다.

04. 최적 단편 선정

a. 소프트웨어 솔루션에서 사용할 변수를 선정하기 위해서는 집합의 혼합정도를 판단할 방법이 필요

b. 가능한 잘 섞이지 않은 두 집합을 선정하는 변수를 찾는 것

c. 지니 불순도(Gini impurity) : 집합 내의 결과 중 하나가 그 집합 내의 항목 중 하나에 무작위로 적용될 기대 오류율

d. 엔트로피 : 집합 내의 순서 불일치 정도

- 모든 다른 결과에 대한 p(x)log(p(x))의 총합

05. 재귀적으로 트리 만들기

a. 속성이 얼마나 좋은지 보기 위해 알고리즘은 먼저 전체 그룹의 엔트로피를 계산

b. 각 속성의 가능한 값으로 그룹을 나누고 새로운 두 그룹의 엔트로피를 계산

c. 어떤 속성이 가장 잘 나누는지를 결정하기 위해 정보이득(information gain)을 계산

d. 정보 이득 : 현재의 엔트로피와 새로운 두 그룹의 가중평균 엔트로피 간의 차

e. 알고리즘은 모든 속성마다 정보 이득을 계산하여 가장 높은 정보이득을 가진 것을 선택

06. 트리 출력하기

a. 재귀 함수 이용

b. 그래프 출력

07. 새로운 관찰 분류

08. 트리 가지치기(pruning)

a. 완전한 노트를 만든 후 불필요한 노드를 제거(overfitting 방지)

b. 노드 쌍을 병합해서 특정 경계값 이하로 엔트로피를 늘릴 수 있는지 보기 위해 공통 부모를 가지고 있는 노드 쌍을 검사.

c. 두 쌍을 가능한 모든 출력을 가진 한 개 노드로 병합(?)

2부 

김민경 - Financial Security & Machine Learning

1. 신제윤 금융위원장은 금융 보안을 위해 모든 금융권이 이상거래탐지시스템 구축을 환료해야 한다고 촉구했다. 전자 금융업종 규율을 재설계토록 하겠다. 

2. 보안은 클라이언트가 아니라 제공자가 마련해야한다.

3. Fraud(사기꾼) Detection Basics

(1) Outlier Detection - rule base detection, anomaly detection 

(2) Two approaches for treating input

(3) Three kinds of algorithms - 배치 방식에 대해 모델링 방식으로 디텍팅, 모델링을 사용하지 않고 데이터를 사용해서 디텍팅(조금 느림), immune system(면역 시스템에 기반한 것)

(4) Real time fraud detection - 

(5) Not worth spending $200 to stop $20 fraud

(6) The Pareto principile

(7) Resources available for fraud detection are always limited - 3%만 사용 가능

(8) If we cannot outspend??

(3) T-cell : 

5. Artificial Immune  Recognition System

(1) 여러 항원들이 모여서 전체 적으로 across해서 detect함

6. MAchine laerning

(1) Supervised learning

(2) Unsupervised learning

(3) Sei-supervised learning : 지도 + 비지도학습

(4) Reinforcement learning : 강화학습 - 잘못된 것을 다시 피드백

(5) Evolutionary learning : 진화 학습

(6) Meta Learning : landmark of data for classifier 

(7) Genetic algrithm : 행위가 시작적으로 왔을 때 이상한 패턴이 나오면 디텍트함

7. Types of Anomaly

(1) Point Anomalies

(2) Contextual Anmalies

(3) Collective Anomalies

8. Association Rule Mining

(1) FP-Tree - frecate(?) pattern gross

9. Finite State Automata(FSA)

알아서 공부

10. Clustering : 데이터를 모를 때 알아서 segmentation해줌

clustering 후 가우시안 모델링을 하고 각각 커널을 넣어줌

11. Hidden Markov

- Sequence Based Algorithm : small amount of money, instance based algorithms

12. Decision Tree

Profiling?

13. SVM

최대 distance

속도가 느림, 대만대 교수 림 교수, 코세라에 강의가 있음

14. logistic regression

feture

15. Neural Network

- Feed Forward Model

16. anti-k nearest neighbor

17. Classical rule-based

18. Neural Stream

(1) Storage - hadoop : Distributed file system, mapreduce : parallel processing

(2) Algorithms - online learning, batch model, direct data, batch model, direct data

(3) Stream - Neural stream : decetralize decision process, cell base

19. A system based on profiles

기존은 rule base임

각각 사용자의 행위별로 파라미터를 만들고 그 사용자에게 서비스를 제공함 개별적으로 트레이닝 함 - hadoop이 최적이다.

Q&A

1. Hadoop이 스파크보다 좋은 이유

- 스파크(버클리에서 만듬)는 latency를 줄일 수 있다. in memory base라서 불안정하다.

- Hadoop은 안정적이다. 느리더라도 괜찮다.

책 요약

(1) 스팸 필터링
A. 규칙 기반 분류기 : 메시지가 스팸이었는지 아니었는지를 가리키는 규칙들을 사람이 설계
- 문제 : 스패머가 규칙들을 모두 배워 필터 규칙을 피해가도록 명백한 행동을 그만 둠

처음이나 메시지를 받았을 때 사용자가 알려준 정보를 학습하는 프로그램

(2) 문서와 단어
- 문서 분류를 생각할 때 항목은 문서가 되고 특성은 문서 내 단어

(3) 분류기 훈련시키기
- 바르게 분류된 문서 예가 많을수록 분류기가 바르게 판단할 가능성이 높아진다.

(4) 확률 계산
- 각 분류별로 메일 메시지 출현 횟수를 알았으니 다음 단계에는 이 숫자들을 확률로 변환
- 어떤 단어가 특정 분류에 있을 확률은 해당 분류에 있는 문서에 그 단어가 나타난 횟수를 그 분류에 있는 전체 문서 개수로 나눈 값으로 계산

A. 조건부 확률 : Pr(A | B) 주어진 B에 대한 A의 확률
B. 가장 확률 : 0.5로 시작하여 학습 데이터에서 적게 학습 되는 데이터들의 오분류를 막음
C. 다른 사람이 이미 학습시킨 스팸 필터에서 얻은 확률을 가장 확률로 사용할 수 있다.

(5) 기본 분류기
- 특정 단어를 포함하고 있는 분류로부터 문서 확률을 얻었으므로 전체 문서가 주어진 분류에 속할 확률을 계산하기 위해 개별 단어 확률을 결합할 방법 필요

A. 나이브 베이지안 분류기
- 나이브 : 결합하는 확률이 서로 독립적이라는 가정
- 주어진 분류에 전체 문서가 속할 확률을 계산
- 베이스 정리에 대한 간략한 소개
Pr(A | B) = Pr(B | A) * Pr(A) | P(B)
- 분류 선택 : 새로운 항목이 어떤 분류에 속할지를 결정
스팸 필터의 경우 좋은 메일 메시지가 스팸으로 분류되지 않는 것이 모든 스팸 메시지를 잡아내는 것보다 더 중요
스팸 필터의 경우 Bad로 필터링 되는 경계값을 보통 3으로 설정해서 Good으로 분류될 확률에 비해 3배 더 높도록 정한다.

(6) 피셔 방식
- 주어진 문서 내의 각 특성이 특정 분류에 있을 확률을 계산
- 확률들을 결합하고 그 확률 집합이 무작위 집합에 비해 더 가망성이 높은지 검사
- 서로 비교할 수 있는 각 분류별 확률을 리턴
A. 특성별 분류 확률
한 문서에 특정 특성이 주어졌을 때 그 문서가 특정 분류에 속할 가능성을 먼저 계산
Pr(Category | Feature) - 이 분류 내 해당 특성을 가진 문서 수 / 이 특성을 가진 전체 문서 수

(11) 다른 기법들

4장의 신경망 사용 가능

9장의 SVM사용 가능

정리

* 베이지안 분류법

1. Bad문서들 중에 Casino라는 단어가 나타날 확률과 Bad문서들 중 Python이 나올 확률을 계산

2. Casino라는 단어가 나왔을 때 문서가 Bad일 확률을 계산하여 판단

장점 :

단점 :

* Fisher Method

1. Casino라는 단어가 나온 문서를 먼저 추출

2. 이 문서들 중 Bad분류로 된 확률을 계산

3. Casino라는 단어가 나왔을 때 2번의 확률로 판단

장점 :

단점 :

ETC.

메일을 문서로 생각하고 문서 중 스팸을 걸러냄
단어를 이용해 스팸을 걸러냄
Supervised Learning 임
서버에서 별도로 filtering할 수도 있고 처음부터 금지어가 있을 수 있다.
scikit library 찾아보기

(1) 통계적 최적화(Stochastic optimization)
여러 변수들이 있고 다양한 해법이 있는 문제나 이 변수들의 조합에 따라 크게 변하는 산출물을 가진 문제에 사용됨
(2) 해답 표현하기
가능한 해답 표현 방식을 먼저 결정해야함
(3) 비용 함수
최적화를 사용해서 문제를 푸는 핵심 열쇠이며 동시에 선택하기 가장 어려운 존재
한 해답이 얼마나 나쁜지를 표현하는 값을 리턴해야 한다.
예) 몇가지 지표
가격, 여행 시간, 대기 시간, 출발 시간, 자동차 렌탈 기간
(4) 무작위 검색
좋은 최적화 기법은 아니지만 모든 알고리즘이 하려는 점을 정확히 이해하는 데 좋으며, 다른 알고리즘이 잘 동작하는지 볼 수 있는 기분선으로 공헌한다.
(5) 언덕 등반
무작위 해답으로 시작해서 더 좋은 해답을 찾아 이웃 해답들을 살펴보는 기법
전역최소점 : 어느 곳에서나 최고인 해답
무작위 재시작 언덕 등반 (random-restart hill climbing) : 무작위로 시작점을 몇 개 선택한 후 무작위로 선택한 시작점 중 하나가 전역 최소점에 근접할 것이란 희망을 가지고 언덕등반 알고리즘을 수차례 수행시킨다.
(6) 시뮬레이티드 어닐링(Simulated Annealing)
어닐링 : 합금을 가열한 후 천천히 냉각하는 과정. 원자는 주변을 뛰어다니다 점차 낮은 에너지 준위로 정착하기 때문에, 원자들은 가장 낮은 에너지 배치를 찾을 수 있다.
(7) 유전자 알고리즘(genetic algorithm)
개체군 : population이란 무작위 해답들을 생성하면서 시작된다.
최적화 단계마다 전체 개체군별 비용 함수가 계산되어 해답의 순위 목록을 만든다.
현재의 개체군에 대한 최상위 해답을 새로운 개체군에 추가한다(엘리트 선발(elitism)). 이 새로운 개체군의 나머지는 최고 해법을 수정하여 만든 완전히 새로운 해법을 구성한다.
해답을 변경하는 두가지 방법
A. 돌연변이(mutation) : 소량의 간단하고 무작위적인 변화를 기존 해답에 적용시키는 방법
B. 교배(crossover), 번식(breeding) : 최적 해답 두 개를 골라 어떤 방식으로 그 둘을 결합하는 것
(8) 비행편 검색 실제
KAYAK 카약 사이트의 API 이용
minidom 패키지
(9) 선호도 최적화 - 첫번째로 선택한 기숙사가 겹쳤을 때 누구를 선택하는가?
제한된 자원을 그에 대해 선호를 표현한 사람들에게 분배하여 가능한 모두 행복하게 하는 방법
- 학생 기숙사 최적화 : 학생들을 그들의 첫 번째와 두 번째 선택을 반영해서 기숙사에 배치하는 문제
모든 학생들이 적합하도록 해답을 표현하는 방법을 찾는 것
(10) 네트워크 시각화 ( 페이스북 앱에서 한번 해보고 싶음)
SNS사이트 내 각 멤버들은 연결된 친구들을 가지며 이를 모으면 사람 네트워크가 만들어진다. 이런 네트워크를 시작화하여 구조를 결정해서 이 네트워크에서 연결자 역할을 하는 사람을 찾는다.
(11) 다른 가능성들
사람의 기술 조합을 고려하여 그룹 프로젝트 안에 작업을 할당하는 방법
키워드로 태깅된 웹 사이트 목록에서 사용자가 제공한 키워드들을 가진 최적의 웹 사이트 그룹을 찾는 것

크롤러, 인덱서, 쿼리엔진, 페이지랭킹, 신경망(Neural Network)
(1) 검색 엔진이란?
- 문서 수집 개발(크롤링 포함 여부, 고정된 문서 컬렉션으로 시작하는 경우도 있음)
- 문서를 모은 후에는 색인을 함(여러 다른 단어들의 위치와 문서들을 담는 테이블을 만듬)
- 색인에는 파일 시스템 경로나 URL과 같이 문서 위치에 대한 참조만 저장
- 질의에 대해 랭킹된 문서 목록을 찾아서 돌려줌

(2) 단순 크롤러
urllib2 - 페이지들을 쉽게 다운로드 받을 수 있게 해주는 파이썬 번들 라이브러리
크롤러 코드 - Beautiful Soup API(웹페이지의 구조적 표현을 만드는 멋진 라이브러리)

(3) 색인하기
색인이란 단어 목록으로, 그 단어가 나타난 문서와 그 문서 안에서 나타난 위치를 가짐
SQLite를 사용하여 색인을 저장함

- 스키마 설정하기
1) urllist - 색인된 URL목록을 가짐
2) wordlist - 단어 목록을 가짐
3) wordlocation - 문서들 내의 단어 위치 목록을 가짐
4) link table - 한테이블에서 다른 테이블로의 연결을 가리키는 두 개의 URL ID를 저장
5) linkwords - wordid와 linkid칼럼을 사용해서 링크에서 실제 사용된 단어들을 저장

- 페이지 내 단어 찾기
soup를 사용해서 텍스트 노드를 찾고 그들의 내용을 모음
문자열을 단어 목록으로 분리하여 색인에 넣을 수 있도록 한다.

- 색인에 넣기
이전 절에서 만든 두개의 함수를 호출하여 페이지 내 단어 목록을 얻는다.
그런 후 페이지와 단어들을 색인에 추가하고 문서 내 단어 위치와 연결을 생성

(4) 검색하기
검색엔진의 검색부 만들기
검색어 문자열을 받아 개별 단어로 분리한 후 모든 다른 단어들을 담고 있는 URL들만 선별하도록 SQL쿼리를 생성하는 검색 함수

(5) 내용 기반 랭킹
주어진 검색어에 대해 페이지에 점수를 매기고 가장 높은 점수를 가진 결과들을 먼저 리턴함

- 검색어와 페이지 내용을 기반으로 점수를 계산하는 여러 방법
각각에 Weight를 주고 계산함
1) 단어 빈도 - 해당 페이지에 검색어 내 단어들이 출현한 횟수를 기반으로 페이지의 점수를 매김
2) 문서 내 위치 - 페이지 상단 가까이나 제목 줄에 나타남
3) 단어 거리 - 페이지에서 서로 가까이 붙어 있는 결과들을 찾는 것들이 유용할 때가 많음

- 정규화 함수
모든 결과를 동일한 범위와 방향으로 맞춤
ID와 점수로 된 딕셔너리를 받아 같은 ID로 0과 1사이의 점수만을 가진 새로운 딕셔너리를 리턴함

(6) 유입 링크 사용

- 단순 계산
각 페이지의 유입 링크 개수를 세고 링크 전체 개수를 페이지에 대한 지표로 사용하는 것
누군가 점수를 높이고 싶은 페이지를 참조하는 여러 사이트들을 마들어 그들이 원하는 페이지의 점수를 쉽게 높일 수 있음

- 페이지랭크 알고리즘
구글의 창업자에 의해 발명됨
페이지마다 점수를 할당함 - 그 페이지에 대한 링크를 가진 다른 페이지들의 중요도와 각각의 다른 페이지들이 가지고 있는 링크 수로 계산됨
모든 페이지랭크 값을 초기에 임의의 값으로 놓고 여러 번 반복 계산함(20번 정도)


- 링크 텍스트 활용
링크를 걸 때 페이지에 남긴 간락한 설명을 이용

(7) 클릭 학습
인공 신경망 구축 - 검색어 안에 있는 단어들과 사용자에게 제공된 검색 결과, 사용자가 클릭한 것으로 학습됨

- 클릭 추적 네트워크 설계
MLP네트워크(다중충 인식망) :

3. 군집 발견 : 정제되지 않은 데이터를 정제 시켜준다.
데이터 군집 : 밀접히 관련된 사물, 사람, 아이디어들의 그룹을 찾고 시각화하는 기법
(1) 감독 대 무감독 학습
- supervised learning(감독 학습 기법) : 예제 입출력을 사용해서 예측하는 방법을 학습하는 기법
EX) 신경망, 결정트리, SVM, 베이지안 필터링
- unsupervised learning(무감독 학습) : 어떤 올바른 답을 찾는 것이 아니고 데이터 집합 내에서 구조를 발견. 데이터를 취해 그 안에 있는 개별 그룹들을 발견하는 것이 목표
EX) 군집

(2) 단어 벡터
- 피드 내 단어 수 세기 : Universal Feed Parser 모듈 이용
Ex) 블로그에서 상위10%와 하위 50%의 단어들을 나열

(3) hierarchical clustering algorithm(계층적 군집화 알고리즘) : 가장 유사한 두 그룹을 계속 병합하는 방식으로 그룹 계층을 만든다.
1) 원래의 항목들만으로 구성된 군집 그룹에서 시작
2) 모든 쌍마다 그들 간의 상관 계수를 계산한 후 가장 유사한 두 개를 찾음
3) 군집들에서 가장 유사한 쌍을 합쳐 한 개의 단일 군집을 만든다.
4) 이 새로운 군집용 데이터는 앞의 두 군집들에 대한 데이터의 평균값
5) 이 과정을 단 한 개의 군집만 남을 때까지 반복 수행

Ex) 블로그 데이터 세트를 군집화해서 블로그 계층도를 만들어 본다.

(4) 계통도 출력

(5) 세로줄 군집화

(6) K평균 군집화 : 가장 많이 사용 됨. 계층적 군집화 기법은 모든 항목마다 계산이 필요하고 항목들이 병합될 때에도 재계산이 필요하기 때문에 큰 데이터 세트에서는 매우 느리게 동작한다.
사전에 생성할 군집의 개수가 지정된다.
무작위로 선정된 k개의 중심점(centroid: 군집의 중심)을 선정하고 이 점에서 가장 근접한 항목들을 할당하면서 시작

(7) 선호도 군집
소셜 네트워크 사이트 : 자발적으로 공헌한 대량의 데이터가 발생함
*타니모토 계수(Tanimoto coefficient) : 각 집합의 모든 항목을 가진 합집합에 비해 양쪽 집합에 모두 있는 교집합의 비율
def tanamoto(v1, v2):
c1, c2, shr = 0, 0, 0
for i in range(len(v1)):
if v1[i] != 0: c1 += 1
if v2[i] != 0: c2 += 1
if v1[i] != 0 and v2[i] != 0: shr += 1
return 1.0 - (float(shr) / (c1+c2-shr))

(8) 2차원으로 데이터 보기
다차원 비례 축소법 : 데이터 세트에 대한 2차원 표현을 찾는 데 사용
모든 항목 쌍의 차이 값을 구하고 이 값과 항목 간 거리가 일치하도록 도표를 만듬