空놀이

확률을 어떻게 추정할 지
3.2 최대 우도

2.1 확률과 통계
2.1.1 확률 기초
(1) 조건부 확률
(2) 결합확률
- 두 랜덤 변수가 서로 영향을 미치지 못하면 둘은 독립(independent)
- 독립인 두 랜덤 변수는 P(X,Y) = P(X)P(Y)
(3) 우도 함수 (likelyhood) :
(4) 사후 확률 : 사건 Y가 일어난 후 Y가 어디서 나왔을 지를 확률로 계산
(5) 베이스 정리
P(X,Y) = P(Y,X)
P(X)P(Y|X) = P(Y)P(X|Y)

2.1.2. 평균과 분산
표준편차 : 분산의 제곱근(루트)
공분산 : 랜덤 벡터를 구성하는 랜덤 변수간의 관계

2.1.3 확률 분포의 표현과 추정
정규분포, 세개의 모드를 가진 분포

2.2. 베이시언 분류기
우도는 부류가 주어진 조건하의 조건부 확률이므로 부류조건부 확률(class-conditional probability)이라고도 부른다.

최소 위험 베이시언 분류기(Minimum risk Bayesian classifier)
우도비(likelihood ratio) : p(x|w1)/o(x|w2)
M부류 최소 위험 베이시언 분류기

2.3 분별함수
최소 오류 베이시언 분류기, 최소 위험 베이시언 분류기

2.4 정규 분포에서 베이시언 분류기
(1) 사전 확률은 표현과 계산이 비교적 쉽다. 하지만 우도의 추정은 경우에 따라 쉬울 수도 있고 어려울 수도 있다.

*가우시언 분포(Gaussian distribution) : 정규분포

(2) 이 절의 목표

a. 2.30의 베이시언 분류기를 그대로 이용함

b. 우도 p(x | wi)가 정규 분포를 따르는 특수한 경우에 대해 분류기가 가지는 성질을 분석하는 것이 목적

c. 특히 두 부류의 영역을 나누는 결정 경계가 어떤 모양을 갖는지에 대한 분석

2.4.1 정규 분포와 분별 함수

2.5 베이시언 분류의 특성
실제 확률 분포를 안다고 가정하면 베이시언 분류기는 오류율 측면에서 최적
베이시언 분류기를 만들기 위해서는 사전 확률과 우도를 추정해야 한다.
- 나이브 베이시언 분류기 : 특징들이 모두 독립이라는 가정을 하고 차원의 저주를 피하는 방법
특징들이 독립이라는 가정은 매우 강한 가정이다. 실제 세계는 그렇지 않다.

2.6 기각 처리
판단하기 애매한 것은 기각 처리함

책 요약

(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차원 표현을 찾는 데 사용
모든 항목 쌍의 차이 값을 구하고 이 값과 항목 간 거리가 일치하도록 도표를 만듬

(1) 협업 필터링 : 큰 무리의 사람들을 검색해서 유사한 취향을 가진 작은 집합을 발견하는 방식으로 동작함
(2) 중첩 딕셔너리 : 사람들이 선호하는 정보를 수집
(3) 유사 사용자 찾기
각각의 사람을 다른 모든 사람들과 비교해서 유사도를 계산
* 유클리디안 거리 점수(euclidean distance score)
* 피어슨 상관점수(Pearson correlation score) : 두 개의 데이터 집합이 한 직선으로 얼마나 잘 표현되는가를 나타내는 측정값

(1) 기계학습(machine learning) : 주어진 데이터의 집합을 이용해서 데이터의 속성에 관한 정보를 추론하는 알고리즘