행렬로 배우는 데이터 마이닝과 머신러닝

제2판 서문
이 책의 초판이 출간된 이후, 정보과학 또는 데이터과학 분야의 응용은 비약적으로 성장하였다. 오늘날 존재하는 가장 큰 상업 기업들 중 다수는 빅데이터 분야에서 활발히 활동하고 있으며, 우리의 일상생활 전반에 깊숙이 관여하여 정보와 인적 연결을 제공하고 있다. 한편으로는 사회에서의 활동과 인터넷 상의 행위가 정부 기관과 상업 기업에 의해 지속적으로 감시되고 있다. 인터넷에 공개된 개인 데이터의 프라이버시와 소유권을 둘러싼 논쟁도 계속되고 있다.
최근의 빅데이터 관련 홍보의 상당 부분은 딥러닝에 집중되어 있는데, 이는 수십 년전부터 존재해 온 신경망의 발전된 형태이다. 신경망은 여러 층의 뉴런과 그 뒤에 이어지는 비선형성으로 구성된 학습 메커니즘이다. 이러한 시스템은 주어진 입력 집합을 원하는 출력에 맞도록 학습시킬 수 있으며, 예를 들어 회귀나 분류 문제에 사용될 수 있다. 딥러닝에서는 훨씬 더 많은 층이 사용되며, 종종 방대한 양의 데이터가 학습에 활용된다.
딥러닝은 여러 응용 분야에서 엄청난 성공을 거두었지만, 그 사용은 어느 정도 실험적인 측면이 있으며 이론적 토대가 충분히 강하다고 보기는 어렵다(예를 들어 M. Elad, "Deep, Deep Trouble," SIAM News, 2017년 5월호 참조). 그러나 딥러닝과 데이터과학
의 다른 새로운 방법들의 과학적 기반을 강화하기 위한 노력이 수학, 수치해석, 통계학 공동체 전반에서 활발히 이루어지고 있다. 그 한 예로, SIAM Journal on Mathematics of Data Science 가 최근 창간되었다.
이 책 Matrix Methods 의 제2판에서 나는 보수적인 입장을 취하여 신경망을 포함시키지 않기로 결정하였다. 반면 그래프와 그래프 알고리즘은 데이터과학 전반에 걸쳐 널리 사용되고 있으며, 그 이론적 기반도 잘 정립되어 있다. 따라서 그래프 이론과 행렬 기법 간의 연관성, 그리고 몇 가지 응용을 간단히 소개하는 것은 자연스러운 추가라고 할 수 있다.

행렬로 배우는 데이터 마이닝과 머신러닝
네트워크 개념은 그래프 분할의 아이디어와 함께 서론에서 소개된다. 제2판에는 두개의 새로운 장이 추가되었다. 하나는 제 I부에 포함된 "Graphs and Matrices"이고, 다른 하나는 제 II부에 포함된 "Spectral Graph Partitioning"이다.
제10장에서는 기본적인 그래프 개념과 이에 대응하는 행렬 개념을 소개한다. 이를 통해 그래프에서의 경로와 인접 행렬의 거듭제곱 사이의 관계를 설명한다. 또한 그래프의 연결성과 행렬의 가약성(reducibility) 사이의 관계를 논의한다. 그래프 라플라시안이 도입되며, 스펙트럴 분할에 필요한 고유벡터의 성질도 함께 다룬다. 스펙트럴 그래프 분할 알고리즘 역시 설명된다.
제16장에서는 스펙트럴 분할을 사회 네트워크와 텍스트 분류에 적용한다.
책의 다른 부분들도 필요에 따라 검토하고 업데이트하였다. 여러 그림이 갱신되었고, 컬러가 사용되었다. 특히 응용 부분의 일부 참고문헌은 추가되거나 현대화되었다.
현대 데이터과학의 응용에서는 매우 거대한 문제들이 다루어진다. 다시 한 번 강조하지만, 이 책의 목적은 매우 큰 문제를 직접 해결하는 데 있지 않다. 오히려 빅데이터를 다루는 많은 알고리즘의 기초가 되는 몇 가지 행렬 기반 방법들을 학생들에게 소개하는 데 그 목적이 있다.
연습문제와 컴퓨터 과제 모음은 다음의 책 웹페이지에서 제공된다: www.siam.org/books/fa15 및 users.mai.liu.se/larel04/matrix-methods.
나는 다시 한 번 시리즈 편집자인 Nick Higham에게 감사의 뜻을 전하고 싶다. 그의 유익한 논평과 제안은 제2판을 개선하는 데 큰 도움이 되었다.
또한 제2판 작업 기간 동안 도움을 준 Paula Callaghan에게 깊은 감사를 드리며, 매우 전문적인 편집 지원을 제공해 준 Claudine Dugan과 Cheryl Hufnagle에게도 감사한다.

라르스 엘덴
링셰핑, 2019년 3월

● 초판 서문 ●

이 책의 초판은 스웨덴 국립 과학 계산 대학원(NGSSC)이 주관한 과학 및 기술 응용데이터 마이닝 대학원 강좌를 위해 작성된 강의 노트에서 출발하였다. 이후 이 자료는 링셰핑 대학교에서 컴퓨터과학 전공 학부생을 대상으로 한 데이터 마이닝과 IT를 위한
수치 알고리즘 과목에서 사용되며 더욱 발전되었다. 이 과목은 과학 계산 분야의 두 번째 강좌에 해당한다.
이 책은 주로 기초적인 과학 계산 또는 수치해석 과목을 이미 이수한 학부생을 대상으로 한다. 또한 선형대수 기법에 대한 입문이 필요한 데이터 마이닝 및 패턴 인식 분야의 초기 대학원생들에게도 유용할 수 있다.
이 책의 목적은 데이터 마이닝과 패턴 인식의 다양한 문제를 해결하는 데 매우 강력한 수치 선형대수 기법들이 존재함을 보여주는 데 있다. 이를 위해 스웨덴 대학의 일반적인 과학 계산(수치해석) 첫 강좌에서 다루는 범위를 넘어서는 내용을 제시할 필요가
있다. 반면, 이 책은 응용 지향적이므로 사용되는 선형대수 알고리즘의 수학적?수치적 측면을 포괄적으로 다루는 것은 불가능하다.
이 책은 세 부분으로 구성되어 있다. 데이터 마이닝과 패턴 인식의 몇 가지 영역에 대한 간단한 서론 이후, 선형대수 개념과 행렬 분해를 소개한다. 이는 학생들이 MATLAB과 같은 문제 해결 환경에서 행렬 분해를 활용하기에 충분하다고 기대한다. 일부 수학적 증명도 제시되지만, 계산 방법보다는 행렬 분해의 존재성과 성질에 중점을 둔다. 제 II부에서는 이러한 선형대수 기법을 데이터 마이닝 문제에 적용한다. 데이터 마이닝과 패턴 인식의 전체 레퍼토리를 다루지는 않으며, 선형대수 기법에 잘 맞는 문제 영역만을 선택하였다. MATLAB 등에서 제공되는 강력한 행렬 분해 소프트웨어를 효과적으로 사용하기 위해서는 기저 알고리즘에 대한 어느 정도의 이해가 필요하다. 이를 위해 제 III부에서 고유값 및 특이값 알고리즘에 대해 매우 간단히 소개한다.
행렬로 배우는 데이터 마이닝과 머신러닝
나는 "어떤 문제에는 어떤 알고리즘"과 같은 요리책을 쓰고자 한 것은 아니다. 이 분야는 너무나 다양하여 명확하고 단순한 해법을 제시하기가 어렵기 때문이다. 대신 학생들에게 그대로 적용해 볼 수도 있고, 더 가능성 있게는 특정 응용에 맞게 수정해야 할
도구 모음을 제공하고자 하였다. 책에 소개된 일부 방법은 MATLAB 스크립트로 설명되어 있는데, 이는 실제 알고리즘이라기보다는 설명을 위한 의사코드로 이해해야 한다.
연습문제와 컴퓨터 과제 모음은 다음 웹페이지에서 제공된다: www.siam.org/books/fa04.
초기 강의 노트 제작을 지원해 준 NGSSC에 감사를 표한다. 이 강의 노트는 여러 동료들에 의해 사용되었다. 유익한 논평을 제공해 준 Gene Golub과 Saara Hyv?nen에게도 감사한다. 여러 학생들이 발표의 일관성 부족을 지적하고 질문을 던져 줌으로써 내
용을 개선하는 데 도움을 주었다. 제11장에서 Berkant Savas의 석사 논문 결과를 사용할 수 있게 해 준 데에도 깊이 감사한다. 익명의 세 명의 심사자는 초기 원고를 읽고 개선을 위한 제안을 해 주었다. 마지막으로, SIAM의 시리즈 편집자인 Nick Higham에게
특별한 감사를 전한다. 그의 세심한 검토와 사려 깊은 조언은 책의 내용과 표현을 크게 향상시켰다.

라르스 엘덴
링셰핑, 2006년 10월

Part Ⅰ. 선형대수학의 기본 개념과 행렬 분해
Linear Algebra Concepts and Matrix Decompositions
1장 데이터 마이닝과 패턴 인식에서의 벡터와 행렬 ··········· 2
1.1 데이터 마이닝과 패턴 인식 ···································································· 2
1.2 벡터와 행렬 ··························································································· 3
1.3 이 책의 목적 ························································································· 8
1.4 프로그래밍 환경 ···················································································· 9
1.5 부동소수점 계산 ···················································································· 9
1.6 표기법 및 관례 ···················································································· 13
2장 벡터와 행렬 ································································ 14
2.1 행렬-벡터 곱셈 ··················································································· 14
2.2 행렬-행렬 곱셈 ··················································································· 16
2.3 내적과 벡터 노름 ················································································ 18
2.4 행렬 노름 ···························································································· 20
2.5 선형 독립성과 기저 ············································································· 22
2.6 행렬의 계수 ························································································· 24
3장 선형연립방정식과 최소제곱 ······································ 25
3.1 LU 분해 ······························································································· 26
3.2 대칭 양수한정행렬 ·············································································· 28
3.3 섭동 이론과 조건수 ············································································· 29
3.4 가우스 소거법에서의 반올림 오차 ······················································· 31
3.5 밴드 행렬 ···························································································· 33
3.6 최소제곱 문제 ····················································································· 35
viii 행렬로 배우는 데이터 마이닝과 머신러닝
4장 직교성 ········································································ 43
4.1 직교 벡터와 행렬 ················································································ 44
4.2 기본 직교 행렬 ···················································································· 47
4.3 부동소수점 연산의 수 ········································································· 54
4.4 부동소수점 연산에서의 직교 변환 ······················································· 55
5장 ?? 분해 ···································································· 56
5.1 삼각형 형태로의 직교 변환 ································································· 56
5.2 최소제곱 문제 풀이 ············································································· 60
5.3 ? 를 계산할 것인가 말 것인가 ··························································· 62
5.4 ?? 분해의 플롭 카운트 ···································································· 63
5.5 최소제곱 문제 해의 오차 ····································································· 64
5.6 최소제곱 문제 해의 수정 ····································································· 65
6장 특이값 분해 ································································ 68
6.1 분해 ···································································································· 68
6.2 근본적인 부분공간 ·············································································· 73
6.3 행렬 근사 ···························································································· 76
6.4 주성분 분석 ························································································· 79
6.5 최소제곱 문제 풀이 ············································································· 80
6.6 최소제곱 문제에 대한 조건수와 섭동 이론 ·········································· 83
6.7 계수-부족 및 부정(과소결정) 시스템 ·················································· 84
6.8 SVD 계산 ···························································································· 87
6.9 대칭 행렬의 고유값 분해 ····································································· 87
6.10 완전 직교 분해 ···················································································· 90
목차 ix
7장 축소 계수 최소제곱모델 ············································ 94
7.1 절단 SVD: 주성분 회귀 ······································································ 96
7.2 크릴로프 부분공간 방법 ···································································· 100
8장 텐서 분해 ································································· 114
8.1 서론 ·································································································· 114
8.2 기본 텐서 개념 ·················································································· 115
8.3 텐서 SVD ·························································································· 118
8.4 HOSVD 를 통한 텐서 근사 ······························································· 121
9장 클러스터링 및 비음수 행렬 분해 ····························· 127
9.1 ?-평균 알고리즘 ·············································································· 128
9.2 비음수 행렬 분해 ·············································································· 132
10장 그래프와 행렬 ·························································· 139
10.1 그래프와 인접 행렬 ··········································································· 140
10.2 연결성과 기약성 ················································································ 143
10.3 그래프 라플라시안과 스펙트럴 분할 ················································· 144
10.4 이분 그래프 ······················································································· 152
11장 손글씨 숫자의 분류 ·················································· 155
11.1 손글씨 숫자와 간단한 알고리즘 ························································ 155
11.2 SVD 기저를 이용한 분류 ·································································· 157
11.3 탄젠트 거리 ······················································································· 165
x 행렬로 배우는 데이터 마이닝과 머신러닝
12장 텍스트 마이닝 ·························································· 172
12.1 문서와 쿼리의 전처리 ······································································· 173
12.2 벡터 공간 모델 ·················································································· 175
12.3 잠재 의미 색인화 ·············································································· 179
12.4 군집화 ······························································································· 185
12.5 비음수 행렬 분해 ·············································································· 187
12.6 LGK 이중대각화 ················································································ 188
12.7 평균 성능 ·························································································· 193
13장 웹써치엔진을 위한 페이지 순위 메기기 ·················· 195
13.1 페이지랭크 ························································································ 196
13.2 랜덤 워크와 마르코프 연쇄 ······························································· 199
13.3 페이지랭크 계산을 위한 멱법 ···························································· 206
13.4 HITS ·································································································· 212
14장 자동 키워드 및 핵심 문장 추출 ································ 214
14.1 중요도 점수 ······················································································· 214
14.2 계수-? 근사에서의 핵심 문장 추출 ·················································· 219
15장 텐서 SVD를 이용한 얼굴 인식 ································ 224
15.1 텐서 표현 ·························································································· 224
15.2 얼굴 인식 ·························································································· 228
15.3 HOSVD 압축을 이용한 얼굴 인식 ·················································· 232
목차 xi
16장 스펙트럴 그래프 분할 ·············································· 234
16.1 대규모 희소 라플라시안 ···································································· 235
16.2 정치 블로그 네트워크 ······································································· 235
16.3 텍스트 분류 ······················································································· 239
16.4 다중 분할 ·························································································· 246
17장 고유값과 특이값의 계산 ·········································· 247
17.1 섭동이론 ···························································································· 248
17.2 멱 방법과 역반복법 ··········································································· 254
17.3 삼대각 형태로의 유사 변환 축소 ······················································ 258
17.4 대칭 삼대각 행렬에 대한 QR 알고리즘 ············································· 260
17.5 특이값 분해 계산 ·············································································· 268
17.6 비대칭 행렬의 고유값 문제 ······························································· 269
17.7 희소 행렬 ·························································································· 271
17.8 아놀디 및 랑초스 방법 ······································································ 273
17.9 Software ··························································································· 282
찾아보기 ··············································································· 284

Lars Elden