빅데이터 마이닝 3/e

1장. 데이터 마이닝

1.1 데이터 마이닝이란?
1.1.1 모델링
1.1.2 통계 모델링
1.1.3 머신러닝
1.1.4 모델링에 대한 연산적 접근
1.1.5 요약
1.1.6 특징 추출
1.2 데이터 마이닝의 통계적 한계점
1.2.1 통합 정보 인지
1.2.2 본페로니의 이론
1.2.3 본페로니의 이론 사례
1.2.4 1.2절 연습문제
1.3 알아 두면 유용한 사실들
1.3.1 문서에서의 단어 중요도
1.3.2 해시 함수
1.3.3 인덱스
1.3.4 보조기억장치
1.3.5 자연 로그의 밑
1.3.6 멱 법칙
1.3.7 1.3절 연습문제
1.4 이 책의 개요
1.5 요약
1.6 참고문헌

2장. 맵리듀스와 새로운 소프트웨어 스택

2.1 분산 파일 시스템
2.1.1 노드들의 물리적 구조
2.1.2 대용량 파일 시스템 구조
2.2 맵리듀스
2.2.1 맵 태스크
2.2.2 키에 의한 그루핑
2.2.3 리듀스 태스크
2.2.4 컴바이너
2.2.5 맵리듀스 실행에 대한 더 자세한 설명
2.2.6 노드 장애 처리
2.2.7 2.2절 연습문제
2.3 맵리듀스를 사용하는 알고리즘
2.3.1 맵리듀스를 사용한 행렬 벡터 곱셈
2.3.2 벡터 v가 메인 메모리에 올라가지 않는 경우
2.3.3 관계 대수 연산
2.3.4 맵리듀스를 사용한 선택 연산
2.3.5 맵리듀스를 사용한 추출 연산
2.3.6 맵리듀스를 사용한 합집합, 교집합, 차집합 연산
2.3.7 맵리듀스를 사용한 자연 조인 연산
2.3.8 맵리듀스를 사용한 그루핑과 집계 연산
2.3.9 행렬 곱셈
2.3.10 한 단계 맵리듀스를 사용한 행렬 곱셈
2.3.11 2.3절 연습문제
2.4 맵리듀스의 확장
2.4.1 워크플로 시스템
2.4.2 스파크
2.4.3 스파크 구현
2.4.4 텐서플로
2.4.5 맵리듀스의 재귀적 확장
2.4.6 벌크 동기 시스템
2.4.7 2.4절 연습문제
2.5 통신 비용 모델
2.5.1 태스크 네트워크에서의 통신 비용
2.5.2 월-클록 시간
2.5.3 다중 조인
2.5.4 2.5절 연습문제
2.6 맵리듀스에 대한 복잡도 이론
2.6.1 리듀서 크기와 복제율
2.6.2 예제: 유사도 조인
2.6.3 맵리듀스 문제를 위한 그래프 모델
2.6.4 매핑 스키마
2.6.5 모든 입력이 주어지지 않은 경우
2.6.6 복제율의 하한값
2.6.7 사례 분석: 행렬 곱셈
2.6.8 2.6절 연습문제
2.7 요약
2.8 참고문헌

3장. 유사 항목 찾기

3.1 집합 유사도의 응용
3.1.1 집합의 자카드 유사도
3.1.2 문서의 유사성
3.1.3 유사 집합 문제에서의 협업 필터링
3.1.4 3.1절 연습문제
3.2 문서의 슁글링
3.2.1 k-슁글
3.2.2 슁글의 크기 선택
3.2.3 슁글의 해싱
3.2.4 단어를 기반으로 만드는 슁글
3.2.5 3.2절 연습문제
3.3 집합의 유사도 보존 요약
3.3.1 집합의 행렬 표현
3.3.2 민해싱
3.3.3 민해싱과 자카드 유사도
3.3.4 민해시 시그니처
3.3.5 민해시 시그니처 연산의 실제
3.3.6 민해싱 속도 향상
3.3.7 해시 함수를 사용한 속도 향상
3.3.8 3.3절 연습문제
3.4 문서의 지역성 기반 해싱
3.4.1 민해시 시그니처의 LSH
3.4.2 밴드 분할 기법의 분석
3.4.3 기법들의 결합
3.4.4 3.4절 연습문제
3.5 거리 측정
3.5.1 거리 측정법의 정의
3.5.2 유클리드 거리
3.5.3 자카드 거리
3.5.4 코사인 거리
3.5.5 편집 거리
3.5.6 해밍 거리
3.5.7 3.5절 연습문제
3.6 지역성 기반 함수의 이론
3.6.1 지역성 기반 함수
3.6.2 자카드 거리에 대한 지역성 기반 함수군
3.6.3 지역성 기반 함수의 확장
3.6.4 3.6절 연습문제
3.7 다른 거리 측정법들을 위한 LSH 함수군
3.7.1 해밍 거리에 대한 LSH 함수군
3.7.2 무작위 초평면과 코사인 거리
3.7.3 스케치
3.7.4 유클리드 거리의 LSH 함수군
3.7.5 유클리드 공간에서의 LSH 함수군에 대한 더 자세한 설명
3.7.6 3.7절 연습문제
3.8 지역성 기반 해시 응용 분야
3.8.1 개체 식별
3.8.2 개체 식별 예제
3.8.3 레코드의 일치 판정
3.8.4 지문 판독
3.8.5 지문 판독을 위한 LSH 함수군
3.8.6 유사한 신문 기사
3.8.7 3.8절 연습문제
3.9 높은 유사도 처리 방법
3.9.1 동일한 항목 찾기
3.9.2 집합의 문자열 표현
3.9.3 길이 기반 필터링
3.9.4 접두사 인덱싱
3.9.5 위치 정보 이용
3.9.6 인덱스 위치 및 길이 활용
3.9.7 3.9절 연습문제
3.10 요약
3.11 참고문헌

4장. 스트림 데이터 마이닝

4.1 스트림 데이터 모델
4.1.1 데이터 스트림 관리 시스템
4.1.2 스트림 소스의 예
4.1.3 스트림 질의
4.1.4 스트림 처리 시 이슈
4.2 스트림 데이터의 표본 추출
4.2.1 동기 부여를 위한 예제
4.2.2 대표 표본 추출
4.2.3 일반적인 표본 추출 문제
4.2.4 표본 크기 검증
4.2.5 4.2절 연습문제
4.3 스트림 필터링
4.3.1 동기부여를 위한 예제
4.3.2 블룸 필터
4.3.3 블룸 필터링 분석
4.3.4 4.3절 연습문제
4.4 스트림에서 중복을 제거한 원소 개수 세기
4.4.1 중복을 제거한 원소 개수
4.4.2 플라졸레-마틴 알고리즘
4.4.3 근사치의 조합
4.4.4 필요 공간
4.4.5 4.4절 연습문제
4.5 모멘트 근사치
4.5.1 모멘트의 정의
4.5.2 두 번째 모멘트를 위한 알론-마티아스-세게디 알고리즘
4.5.3 알론-마티아스-세게디 알고리즘 작동 원리
4.5.4 높은 모멘트
4.5.5 무한한 스트림의 처리
4.5.6 4.5절 연습문제
4.6 윈도우 내에서의 카운트
4.6.1 정확하게 개수를 세는 데 드는 비용
4.6.2 다타르-지오니스-인디크-모트와니 알고리즘
4.6.3 DGIM 알고리즘을 위한 공간 요구 조건
4.6.4 DGIM 알고리즘으로 질의 응답하기
4.6.5 DGIM 조건 유지하기
4.6.6 오차 줄이기
4.6.7 일반적인 개수 세기로 확장
4.6.8 4.6절 연습문제
4.7 감쇠 윈도우
4.7.1 자주 등장하는 원소를 찾는 문제
4.7.2 감쇠 윈도우의 정의
4.7.3 가장 인기 있는 원소들 찾기
4.8 요약
4.9 참고문헌

5장. 링크 분석

5.1 페이지랭크
5.1.1 초기 검색 엔진과 용어 스팸
5.1.2 페이지랭크의 정의
5.1.3 웹의 구조
5.1.4 데드 엔드 피하기
5.1.5 스파이더 트랩과 세금 매김
5.1.6 검색 엔진의 페이지랭크 사용
5.1.7 5.1절 연습문제
5.2 페이지랭크의 효율적인 연산
5.2.1 전이 행렬의 표현
5.2.2 맵리듀스를 이용한 페이지랭크 반복
5.2.3 결과 벡터를 합산해 내기 위한 컴바이너의 사용
5.2.4 전이 행렬의 블록 표현
5.2.5 페이지랭크 반복 연산을 위한 그 외 효율적인 접근법
5.2.6 5.2절 연습문제
5.3 주제 기반 페이지랭크
5.3.1 주제 기반 페이지랭크의 필요성
5.3.2 편향된 랜덤 워크
5.3.3 주제 기반 페이지랭크의 사용
5.3.4 단어로부터 주제 추론
5.3.5 5.3절 연습문제
5.4 링크 스팸
5.4.1 스팸 팜의 구조
5.4.2 스팸 팜 분석
5.4.3 링크 스팸과의 전쟁
5.4.4 트러스트랭크
5.4.5 스팸 매스
5.4.6 5.4절 연습문제
5.5 허브와 권위자
5.5.1 HITS의 직관적 이해
5.5.2 허브 지수와 권위 지수의 공식화
5.5.3 5.5절 연습문제
5.6 요약
5.7 참고문헌

6장. 빈발 항목집합

6.1 시장바구니 모델
6.1.1 빈발 항목집합의 정의
6.1.2 빈발 항목집합의 응용
6.1.3 연관 규칙
6.1.4 신뢰도가 높은 연관 규칙 찾기
6.1.5 6.1절 연습문제
6.2 시장바구니와 선험적 알고리즘
6.2.1 시장바구니 데이터의 표현
6.2.2 항목집합을 세기 위한 메인 메모리의 사용
6.2.3 항목집합의 단조성
6.2.4 쌍 개수로의 귀결
6.2.5 선험적 알고리즘
6.2.6 모든 빈발 항목집합을 위한 선험적 알고리즘
6.2.7 6.2절 연습문제
6.3 메인 메모리에서 더 큰 데이터셋 처리하기
6.3.1 PCY 알고리즘
6.3.2 다단계 알고리즘
6.3.3 다중 해시 알고리즘
6.3.4 6.3절 연습문제
6.4 단계 한정 알고리즘
6.4.1 단순 무작위 알고리즘
6.4.2 표본 추출 알고리즘에서의 오류 방지
6.4.3 SON 알고리즘
6.4.4 SON 알고리즘과 맵리듀스
6.4.5 토이보넨의 알고리즘
6.4.6 토이보넨의 알고리즘이 동작하는 이유
6.4.7 6.4절 연습문제
6.5 스트림에서 빈발 항목 개수 세기
6.5.1 스트림에서의 표본 추출 방법
6.5.2 감쇠 윈도우에서의 빈발 항목집합
6.5.3 기법들의 결합
6.5.4 6.5절 연습문제
6.6 요약
6.7 참고문헌

7장. 클러스터링

7.1 클러스터링 기법의 개요
7.1.1 점, 공간, 거리
7.1.2 클러스터링 전략
7.1.3 차원의 저주
7.1.4 7.1절 연습문제
7.2 계층적 클러스터링
7.2.1 유클리드 공간에서 계층적 클러스터링
7.2.2 계층적 클러스터링의 효율성
7.2.3 그 외의 계층적 클러스터링 처리 규칙들
7.2.4 비유클리드 공간에서 계층적 클러스터링
7.2.5 7.2절 연습문제
7.3 K평균 알고리즘
7.3.1 k평균의 기초
7.3.2 k평균의 클러스터 초기화
7.3.3 적합한 k값의 선택
7.3.4 BFR 알고리즘
7.3.5 BFR 알고리즘의 데이터 처리
7.3.6 7.3절 연습문제
7.4 CURE 알고리즘
7.4.1 CURE에서의 초기화
7.4.2 CURE 알고리즘의 종료
7.4.3 7.4절 연습문제
7.5 비유클리드 공간에서 클러스터링
7.5.1 GRGPF 알고리즘의 클러스터 표현 방식
7.5.2 클러스터 트리 초기화
7.5.3 GRGPF 알고리즘에서 점들을 추가하기
7.5.4 클러스터의 분할과 병합
7.5.5 7.5절 연습문제
7.6 스트림을 위한 클러스터링과 병렬 처리
7.6.1 스트림 연산 모델
7.6.2 스트림-클러스터링 알고리즘
7.6.3 버킷 초기화
7.6.4 버킷 병합
7.6.5 질의에 대한 응답
7.6.6 분산 환경에서의 클러스터링
7.6.7 7.6절 연습문제
7.7 요약
7.8 참고문헌

8장. 웹을 통한 광고

8.1 온라인 광고와 관련된 주제들
8.1.1 광고의 기회
8.1.2 광고 직접 배치
8.1.3 디스플레이 광고의 문제
8.2 온라인 알고리즘
8.2.1 온라인과 오프라인 알고리즘
8.2.2 탐욕적 알고리즘
8.2.3 경쟁률
8.2.4 8.2절 연습문제
8.3 조합 문제
8.3.1 조합과 완벽한 조합
8.3.2 최선 조합을 찾는 탐욕적 알고리즘
8.3.3 탐욕적 조합의 경쟁률
8.3.4 8.3절 연습문제
8.4 애드워즈 문제
8.4.1 검색 광고의 역사
8.4.2 애드워즈 문제의 정의
8.4.3 애드워즈 문제에 대한 탐욕적 접근법
8.4.4 밸런스 알고리즘
8.4.5 밸런스 알고리즘 경쟁률의 하한선
8.4.6 입찰자가 많은 경우의 밸런스 알고리즘
8.4.7 밸런스 알고리즘의 일반화
8.4.8 애드워즈 문제와 관련된 마지막 사실
8.4.9 8.4절 연습문제
8.5 애드워즈 구현
8.5.1 입찰과 검색 질의 조합
8.5.2 좀 더 복잡한 조합 문제
8.5.3 문서와 입찰 광고를 조합하는 알고리즘
8.6 요약
8.7 참고문헌

9장. 추천 시스템

9.1 추천 시스템 모델
9.1.1 다목적 행렬
9.1.2 롱테일
9.1.3 추천 시스템의 응용 분야
9.1.4 다목적 행렬 생성
9.2 내용 기반 추천
9.2.1 항목 프로파일
9.2.2 문서의 특징 추출
9.2.3 태그에서 얻는 항목 특징
9.2.4 항목 프로파일 표현
9.2.5 사용자 프로파일
9.2.6 내용 기반 항목 추천
9.2.7 분류 알고리즘
9.2.8 9.2절 연습문제
9.3 협업 필터링
9.3.1 유사성 측정
9.3.2 유사도의 이중성
9.3.3 사용자와 항목 클러스터링
9.3.4 9.3절 연습문제
9.4 차원 축소
9.4.1 UV 분해
9.4.2 평균 제곱근 오차
9.4.3 UV 분해의 단계적 연산
9.4.4 임의의 원소 최적화
9.4.5 완성된 UV 분해 알고리즘 구현
9.4.6 9.4절 연습문제
9.5 넷플릭스 챌린지
9.6 요약
9.7 참고문헌

10장. 소셜 네트워크 그래프 마이닝

10.1 소셜 네트워크 그래프
10.1.1 소셜 네트워크란 무엇인가?
10.1.2 그래프로서의 소셜 네트워크
10.1.3 다양한 소셜 네트워크들
10.1.4 다양한 종류의 노드를 갖는 네트워크
10.1.5 10.1절 연습문제
10.2 소셜 네트워크 그래프 클러스터링
10.2.1 소셜 네트워크 그래프의 거리 측정법
10.2.2 표준 클러스터링 방법의 적용
10.2.3 중계성
10.2.4 거번-뉴먼 알고리즘
10.2.5 중계성을 사용해 커뮤니티 찾기
10.2.6 10.2절 연습문제
10.3 커뮤니티의 직접적 발견
10.3.1 무리 찾기
10.3.2 완전 이분 그래프
10.3.3 완전 이분 부분 그래프 찾기
10.3.4 완전 이분 그래프가 존재해야 하는 이유
10.3.5 10.3절 연습문제
10.4 그래프 분할
10.4.1 분할을 잘하는 방법은 무엇인가?
10.4.2 구분선 정규화
10.4.3 그래프를 설명하는 행렬들
10.4.4 라플라스 행렬의 고유값
10.4.5 또 다른 분할 방식
10.4.6 10.4절 연습문제
10.5 겹치는 커뮤니티 찾기
10.5.1 커뮤니티의 본질
10.5.2 최대 가능도 추정법
10.5.3 소속-그래프 모델
10.5.4 커뮤니티 할당의 이산형 최적화
10.5.5 이산적인 멤버십 변경을 피하는 방법
10.5.6 10.5절 연습문제
10.6 유사순위
10.6.1 소셜 그래프의 랜덤 워커
10.6.2 재출발이 가능한 랜덤 워커
10.6.3 근사 유사순위
10.6.4 근사 유사순위가 동작하는 이유
10.6.5 커뮤니티 찾기를 위한 유사순위의 응용
10.6.6 10.6절 연습문제
10.7 삼각형의 개수 세기
10.7.1 삼각형 개수를 세는 이유
10.7.2 삼각형을 찾는 알고리즘
10.7.3 삼각형을 찾는 알고리즘의 효율
10.7.4 맵리듀스를 사용해 삼각형 찾기
10.7.5 더 적은 리듀스 태스크 사용하기
10.7.6 10.7절 연습문제
10.8 그래프의 이웃 특징
10.8.1 방향 그래프와 이웃들
10.8.2 그래프의 지름
10.8.3 이행적 폐쇄와 도달 가능성
10.8.4 맵리듀스를 통한 도달 가능성
10.8.5 세미-나이브 평가
10.8.6 선형 이행적 폐쇄
10.8.7 재귀적 배가에 의한 이행적 폐쇄
10.8.8 지능형 이행적 폐쇄
10.8.9 방법 비교
10.8.10 그래프 축소에 의한 이행적 폐쇄
10.8.11 이웃들의 크기 추정
10.8.12 10.8절 연습문제
10.9 요약
10.10 참고문헌

11장. 차원 축소

11.1 대칭 행렬의 고유값과 고유 벡터
11.1.1 정의
11.1.2 고유값과 고유 벡터 계산
11.1.3 반복 제곱법으로 고유쌍 찾기
11.1.4 고유 벡터의 행렬
11.1.5 11.1절 연습문제
11.2 주성분 분석
11.2.1 설명에 도움이 되는 예제
11.2.2 차원 축소를 위한 고유 벡터의 사용
11.2.3 거리의 행렬
11.2.4 11.2절 연습문제
11.3 특이값 분해
11.3.1 SVD의 정의
11.3.2 SVD의 해석
11.3.3 SVD를 사용한 차원 축소
11.3.4 작은 특이값을 제거하는 방식이 동작하는 이유
11.3.5 콘셉트를 사용한 질의
11.3.6 행렬의 SVD 계산
11.3.7 11.3절 연습문제
11.4 CUR 분해
11.4.1 CUR의 정의
11.4.2 행과 열의 적절한 선택
11.4.3 중간 행렬 구성
11.4.4 CUR 분해 완성
11.4.5 중복된 행과 열 제거
11.4.6 11.4절 연습문제
11.5 요약
11.6 참고문헌

12장. 대규모 머신러닝

12.1 머신러닝 모델
12.1.1 학습 집합
12.1.2 설명에 도움이 되는 예제
12.1.3 머신러닝 기법들
12.1.4 머신러닝의 구조
12.1.5 12.1절 연습문제
12.2 퍼셉트론
12.2.1 임계값 0으로 퍼셉트론 학습시키기
12.2.2 퍼셉트론의 수렴
12.2.3 위노우 알고리즘
12.2.4 임계점의 변경을 허용하기
12.2.5 다중 클래스 퍼셉트론
12.2.6 학습 집합 변형
12.2.7 퍼셉트론의 문제점
12.2.8 퍼셉트론의 병렬 구현
12.2.9 12.2절 연습문제
12.3 서포트 벡터 머신
12.3.1 SVM의 동작 원리
12.3.2 초평면 정규화
12.3.3 최적 근사치 구분자 찾기
12.3.4 경사 하강법에 의한 SVM 해
12.3.5 확률적 경사 하강법
12.3.6 SVM의 병렬 구현
12.3.7 12.3절 연습문제
12.4 최근접 이웃 학습
12.4.1 최근접 이웃을 계산하기 위한 프레임워크
12.4.2 하나의 최근접 이웃 학습
12.4.3 일차원 함수 학습
12.4.4 커널 회귀 분석
12.4.5 고차원 유클리드 데이터 처리
12.4.6 비유클리드 거리 처리
12.4.7 12.4절 연습 문제
12.5 의사결정 트리
12.5.1 의사결정 트리 사용
12.5.2 불순도 측정
12.5.3 의사결정 트리 노드의 설계
12.5.4 수치형 특징을 사용한 테스트 선택
12.5.5 범주형 특징을 사용한 테스트 선택
12.5.6 의사결정 트리의 병렬 설계
12.5.7 노드 가지치기(Node Pruning)
12.5.8 의사결정 포레스트
12.5.9 12.5절 연습문제
12.6 학습 방식의 비교
12.7 요약
12.8 참고문헌

13장. 신경망과 딥러닝

13.1 신경망 소개
13.1.1 신경망
13.1.2 노드 간 상호 연결
13.1.3 컨볼루션 신경망
13.1.4 신경망 설계 문제
13.1.5 13.1절 연습문제
13.2 고밀도 피드 포워드 네트워크
13.2.1 선형 대수 표기법
13.2.2 활성 함수
13.2.3 시그모이드
13.2.4 쌍곡선 탄젠트
13.2.5 소프트맥스
13.2.6 정류 선형 유닛
13.2.7 손실 함수
13.2.8 회귀 손실
13.2.9 분류 손실
13.2.10 13.2절 연습문제
13.3 역전파와 경사 하강법
13.3.1 계산 그래프
13.3.2 경사, 야코비안, 연쇄 규칙
13.3.3 역전파 알고리즘
13.3.4 경사 하강 반복하기
13.3.5 텐서
13.3.6 13.3절 연습문제
13.4 컨볼루션 신경망
13.4.1 컨볼루션 레이어
13.4.2 컨볼루션과 교차 상관
13.4.3 풀링 레이어
13.4.4 CNN 아키텍처
13.4.5 구현과 학습
13.4.6 13.4절 연습문제
13.5 순환 신경망
13.5.1 RNN 학습시키기
13.5.2 경사 소실과 폭발
13.5.3 장단기 기억
13.5.4 13.5절 연습문제
13.6 정칙화
13.6.1 norm 패널티
13.6.2 드롭아웃
13.6.3 조기 종료
13.6.4 데이터셋 증강
13.7 요약