空놀이

(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) : 주어진 데이터의 집합을 이용해서 데이터의 속성에 관한 정보를 추론하는 알고리즘