[Java] 자바로 프로그래밍 입문하기: 3.3. 자료형 설계하기 (4)

응용프로그램: 데이터 마이닝(data mining)

  이번 절에서 논의된 몇몇 개념들을 응용프로그램의 문맥에서 좀 더 설명하기 위해, 우리는 데이터 마이닝의 어려운 과제를 해결하기에 중요한 소프트웨어 기술에 대해 알아볼 것입니다. 데이터 마이닝은 웹에서 모든 사용자가 접근할 수 있는 아주 많은 정보들을 검색하는 절차를 기술할 때 널리 쓰이는 용어입니다. 

  이 기술은 웹 검색 결과의 질적 향상을 극적으로 꾀할 수 있게 만듭니다. 멀티미디어 정보 검색, 바이오메디컬 데이터베이스, 표절 검사, 게놈 연구, 상업 응용프로그램에서의 혁신, 범죄자의 프로파일링 등 다양한 목적으로 사용될 수 있죠. 따라서 아주 주목 받는 분야 중 하나이며, 데이터 마이닝에 대한 연구도 활발히 이루어지고 있습니다.

  여러분은 여러분의 컴퓨터에 있는 수천 개의 파일에 직접 접근할 수 있습니다. 또한 웹에 있는 수십억 개의 파일에 우회적으로 접근할 수 있죠. 이 파일들은 아주 다양합니다: 상업 웹 페이지도 있고, 음악과 영상, 이메일, 프로그램 코드 등 다양한 정보를 담고 있죠. 간단하게 생각해보기 위해, 우리는 텍스트 문서에만 집중하도록 합시다.(물론 우리가 고려할 방법은 사진, 음악 등의 파일에도 잘 적용해볼 수 있습니다) 

  텍스트 문서에만 집중함에도, 여전히 수많은 종류의 문서들이 존재할 것입니다. 우리의 관심은 문서를 특성화하기 위해 콘텐츠를 사용하여 파일을 검색하는 효율적인 방법을 찾는 것입니다. 이 문제에 대한 생산적인 접근법 중 하나는, 콘텐츠의 기능인 프로필(profile)이라고 하는 벡터와 각 문서를 연관시키는 것입니다. 이는 곧, 프로필은 문서를 특성화해야 하며, 따라서 문서는 서로 다른 프로필을 가지고, 비슷한 문서는 비슷한 프로필을 가져야 한다는 것입니다. 

텍스트 문서들

  여러분은 아마 이 접근법이 소설과 자바 프로그램, 게놈 사이를 구별할 수 있게 만들어준다는 사실이 별로 놀랍진 않겠지만, 콘텐츠 검색이 소설들의 작가가 서로 다르다는 사실을 알려줄 수 있다는 사실과, 다른 검색 기준들의 효과적인 기초가 될 수 있다는 사실을 알고 놀라게 될 것입니다.

  시작하기 위해, 문서의 추상화가 필요합니다. 문서란 무엇일까요? 우리가 원하는 일을 하기 위해 문서는 어떤 연산이 필요할까요? 이러한 질문에 대한 답은 우리의 설계를 나타내며, 따라서 궁극적으로 우리가 작성할 코드가 될 것입니다. 데이터 마이닝의 목적에 따라, 첫째 질문에 대한 답은 문서가 입력 스트림에 의해 정의된다는 것이며, 이는 명확하죠. 둘째 질문에 대한 답은 우리가 숫자를 이용하여 다른 문서와의 유사성을 계산할 수 있어야 한다는 것입니다. 곧 다음 API처럼 기술할 수 있습니다.

Sketch의 API

  생성자의 인자는 파일 혹은 웹사이트의 이름입니다. 두 정수는 검색의 품질을 결정하죠. 클라이언트는 simTo() 메소드를 통해 두 Sketch 사이의 유사도를 결정할 수 있습니다. 0(유사하지 않음)부터 1(유사함) 사이의 값이죠. 이 간단한 자료형은 유사도 측정 구현과 문서 검색에서 해당 측정을 사용하는 클라이언트를 구현하는 것 사이의 좋은 구분을 제공합니다.

프로필 계산

  프로필을 계산하는 것은 첫번째 과제가 될 것입니다. 우리의 첫 선택은 Sketch의 프로필을 재현하는 Vector를 사용하는 것입니다. 하지만 어떤 정보가 프로필을 계산하는 데 사용되어야 할까요? Sketch의 Vector 프로필 값을 어떻게 계산할 수 있을까요? 다양한 접근법을 연구해왔으며, 연구자들은 여전히 이 작업에서 효과적이고 효율적인 알고리즘을 찾고 있습니다.

프로그램 3.3.4: Sketch

public class Sketch { private final Vector profile; // unit vector public Sketch(String text, int k, int d) { int n = text.length(); double[] freq = new double[d]; for (int i = 0; i < n-k+1; i++) { String kgram = text.substring(i, i+k); int hash = kgram.hashCode(); freq[Math.abs(hash % d)] += 1; } Vector vector = new Vector(freq); profile = vector.direction(); } public double similarTo(Sketch other) { return profile.dot(other.profile); } public String toString() { return "" + profile; } public static void main(String[] args) { int k = Integer.parseInt(args[0]); int d = Integer.parseInt(args[1]); String text = StdIn.readAll(); Sketch sketch = new Sketch(text, k, d); StdOut.println(sketch); } }

% more genomeA.txt
ATAGATGCATAGCGCATAGC
% java Sketch 2 16
% genomeA.txt
[ 0 0 0.51 0.39 0.39 0 0 0.13 0.39 0 0 0.13 0.13 0.51 0 0 ]

  우리의 Sketch 구현은 빈도 계산(frequency count) 접근법을 사용합니다. 생성자는 정수 k와 벡터 차원 d 두 개의 인자를 갖습니다. 이는 문서를 스캔하고 문서의 모든 k-gram을 시험하죠: 각 지점에서 시작하는 k 길이의 부분문자열을 검사하는 것입니다. 가장 간단한 형식으로, 프로필은 벡터이며 문자열의 k-gram 발생 빈도를 상대적으로 나타냅니다. 가능한 각 k-gram에 대한 항목은 해당 값을 가진 콘텐츠의 k-gram 수를 제공합니다. 

  예를 들어, 유전 데이터에서 k=2이고 d=16(A, T, G, C 4개의 문자로 길이가 2인 문자열의 개수)을 사용한다고 생각해봅시다. 2-gram AT는 ATAGATGCATAGCGCATAGC에서 4번 나타납니다. 따라서 AT에 해당하는 벡터는 4가 될 것입니다. 

유전 데이터 프로파일링

  빈도 벡터를 만들기 위해, 우리는 각 k-gram들을 0부터 15 사이의 정수로 변환할 수 있어야 합니다. 유전 데이터의 경우, 우리는 단 한 번의 텍스트 검사면 빈도 벡터를 만들기 위한 배열을 계산할 수 있죠. 해당하는 각 k-gram을 만날 때마다 배열의 값을 추가하는 것입니다. 이는 k-gram의 순서를 무시함으로써 일부 정보를 잃는 것처럼 보이지만, 중요한 사실은 순서의 정보 콘텐츠는 그들이 나타나는 빈도 정보보다는 덜 중요하다는 것입니다. 

  마르코프(Markov) 모델 패러다임은 우리가 이전에 1.6절에서 배웠던 랜덤 웹서핑 프로그램과는 다릅니다. 구현에 좀 더 힘써야 하죠. Sketch에서 계산을 캡슐화하는 것은 우리에게 Sketch 클라이언트를 다시 쓰지 않고도 다양한 설계를 경험할 수 있는 유연성을 줍니다.

해싱(Hashing)

  ASCII 텍스트 문자열은 각 문자가 128가지의 다른 char 값을 갖습니다. 따라서 k-gram에서 128^k 개의 경우가 가능하죠. 차원 d는 단순히 기술한다면 128^k가 될 것입니다. 이는 적당히 많은 수준을 넘어 아득하게 많은 수입니다. 유니코드의 경우, 65,536 개의 문자가 존재합니다. 2-gram만 고려하더라도, 굉장히 큰 벡터 프로필이 필요하죠. 이러한 문제를 개선하기 위해, 우리는 해싱을 사용할 것입니다. 

  실제로도, 문자열을 정수 인덱스로 바꾸는 것은 자바 내부적으로도 굉장히 중요한 부분입니다. 당장 상속에 대해서 이야기할 때, 모든 객체는 Object를 상속하며 정수 값을 반환하는 hashCode()를 지닌다고 했습니다. 어떤 문자열 s가 주어졌을 때, 우리는 Math.abs(s.hashCode() % d)를 계산합니다. 이 값은 0과 d-1 사이의 정수가 될 것이며, 빈도를 계산하기 위한 배열의 인덱스로 활용할 수 있습니다. 우리가 사용할 프로필은, 문서의 모든 k-gram에서 이러한 값의 빈도에 의해 정의된 벡터의 방향입니다.

프로필 비교

  두 번째 과제는 두 프로필의 유사도를 계산하는 것입니다. 두 벡터를 비교하는 방법은 수도 없이 많습니다. 아마 가장 간단한 방법은 둘 사이의 유클리드 거리를 계산하는 것입니다. 주어진 벡터 x와 y의 거리는 다음과 같이 정의됩니다:

  여러분들은 d=2 혹은 d=3의 경우에서 이 공식이 친숙할 것입니다. 벡터의 거리는 계산하기 쉽습니다. 만약 x와 y가 벡터 값이라면, x.minus(y).magintude()는 둘 사이의 유클리드 거리입니다. 만약 문서가 비슷하다면, 그들의 프로필 역시 비슷할 것이며 두 벡터 사이의 거리가 작을 것입니다. 또 다른 유사도 측정 방법 중 하나는, 코사인(cosine) 유사도이며 이 역시 간단합니다: 프로필이 단위 벡터이고 음수가 아닌 좌표계일 때, 그들의 내적은 다음과 같습니다.

  이는 0과 1 사이의 값을 지닙니다.(단위벡터이므로) 기하학적으로, 이 양은 두 벡터가 이루는 각의 코사인 값과 같습니다. 문서가 비슷할수록, 해당 값이 1에 가까울 것임을 알 수 있죠.

모든 쌍을 비교하기

  CompareDocumnts은 다음 문제를 해결하기 위해 필요한 정보를 제공하는 간단하면서도 유용한 Sketch 클라이언트입니다: 문서들의 집합이 주어졌을 때, 가장 유사한 두 문서를 찾아내기. 이는 약간 주관적일 수 있으므로, CompareAll은 입력 리스트의 모든 문서 쌍의 코사인 유사도를 출력합니다. 적절한 크기의 k와 d에 대해, 프로필은 아주 훌륭하게 우리의 샘플 문서 집합을 특성화합니다. 이 결과는 유전 데이터, 상업 데이터, 자바 코드, 웹 소스 코드가 서로 완전히 다르다고 말할 뿐만 아니라, 톰 소여와 허클베리 핀이 오만과 편견과 아주 유사하다고 말해줍니다.

프로그램 3.3.5: SImilarity detection

public class CompareDocuments { public static void main(String[] args) { int k = Integer.parseInt(args[0]); int d = Integer.parseInt(args[1]); String[] filenames = StdIn.readAllStrings(); int n = filenames.length; // create document sketches Sketch[] sketches = new Sketch[n]; for (int i = 0; i < n; i++) { In in = new In(filenames[i]); String text = in.readAll(); sketches[i] = new Sketch(text, k, d); } // print header StdOut.print(" "); for (int i = 0; i < n; i++) { StdOut.printf("%8.4s", filenames[i]); } StdOut.println(); // print n-by-n table for (int i = 0; i < n; i++) { StdOut.printf("%.4s", filenames[i]); for (int j = 0; j < n; j++) { StdOut.printf("%8.2f", sketches[i].similarTo(sketches[j])); } StdOut.println(); } } }

% java CompareDocuments 5 10000 < docs.txt
     Cons TomS Huck Prej Pict DJIA Amaz ACTG 
Cons 1.00 0.66 0.60 0.64 0.17 0.18 0.21 0.11
TomS 0.66 1.00 0.93 0.88 0.10 0.24 0.18 0.14 
Huck 0.60 0.93 1.00 0.82 0.07 0.23 0.16 0.12 
Prej 0.64 0.88 0.82 1.00 0.10 0.25 0.19 0.15 
Pict 0.17 0.10 0.07 0.10 1.00 0.05 0.37 0.03
D3IA 0.18 0.24 0.23 0.25 0.05 1.00 0.16 0.11
Amaz 0.21 0.18 0.16 0.19 0.37 0.16 1.00 0.07
ACTG 0.11 0.14 0.12 0.15 0.03 0.11 0.07 1.00

  비교 문학(comparative literature)의 연구자는 이 프로그램을 사용해 책 사이의 관계를 발견해낼 수 있습니다. 교사는 이 프로그램을 사용해 학생들의 과제 표절을 검사할 수 있습니다.(실제로 많은 교사들은 이러한 프로그램을 사용하죠) 또한 생명과학자는 게놈의 관계를 발견하는데 사용할 수도 있죠.

유사한 문서를 검색하기

  다른 Sktech 클라이언트로는 프로필을 수많은 문서들 중 주어진 문서와 비슷한 문서가 있는지 식별하는 데에 사용하는 것입니다. 예를 들어, 웹 검색 엔진은 이 종류의 클라이언트를 사용해 여러분들에게 이전에 방문한 페이지와 비슷한 페이지를 보여주죠. 온라인 서점은 여러분이 구매했던 책과 비슷한 책을 추천해주며, SNS에서는 여러분이 좋아하는 유형의 사람들을 추천해주기도 합니다. 

  이 해결책은 단순 스케치에 불과합니다. 프로필을 효율적으로 계산하고 그들을 비교하는 알고리즘들은 여전히 컴퓨터 과학자들에게 연구되며 발명되고 있습니다. 우리의 목적은 여러분들에게 이러한 문제를 소개하고, 비슷한 문제에 직면했을 때 추상화의 힘을 어떻게 발휘할 수 있는지 보여주기 위함이었습니다. 

  벡터는 수학의 필수적인 추상화이고, 우리는 검색 방법을 추상화 계층(layers of abstraction)으로 개발할 수 있었습니다: Vector는 자바 배열로 구성되며, Sketch(Document)는 Vector로 구성되고, 클라이언트 코드는 Sketch로 구성되죠. 평소처럼 우리는 이러한 API를 개발하기 위한 많은 시도에 대해 긴 설명을 생략했지만 데이터 유형이 구현 요구 사항을 염두에 두고 문제의 요구에 응답하여 설계되었음을 알 수 있습니다.

  적절한 추상화를 구현하고 정의하는 것은 효과적인 객체지향 프로그래밍의 핵심입니다. 수학, 물리 모델, 컴퓨터 프로그램 등에서 나타나는 추상화의 힘은 이러한 예제들에 잘 스며들어 있죠. 여러분이 여러분만의 전산적 과제를 해결하기 위해 자료형을 개발하는 것이 능숙해졌을 때, 이러한 능력에 대한 감사가 더더욱 커질 것입니다.

계약에 의한 설계(Design-by-contacct)

  결론적으로, 우리는 우리의 프로그램이 동작할 때 프로그램에 대한 가정을 확인할 수 있게 해주는 자바 언어의 메커니즘을 살펴보았습니다. 예를 들어, 여러분들이 입자를 표현하는 자료형을 구현한다면, 그것의 양(mass)은 양수이고 속도는 광속보다 낮음을 주장할 수 있습니다. 혹은 여러분이 같은 크기의 두 벡터를 더하는 메소드를 구현한다면, 여러분은 결과 벡터의 길이 또한 두 길이의 합과 같은 길이를 가진다고 주장할 수 있습니다.

예외(Exceptions)

  예외란 여러분의 프로그램이 작동하는 중간에 발생하는 중지 이벤트이며, 때때로 오류가 발생함을 알려주는 신호이기도 합니다. 이를 보통 예외를 던진다(throwing an exception)이라고 표현합니다. 우리는 이미 자바 시스템 메소드가 던지는 예외들을 접해봤었습니다: StackOverflowException, DivideByZeroException, NullPointerException, ArrayOutOfBoundsException과 같은 것들이죠. 여러분 역시 자신만의 예외를 만들 수 있습니다. 가장 간단한 것은 RuntimeException이며 프로그램의 실행을 중지하고 오류 메시지를 출력합니다.

throw new RuntimeException("Error message here.");

  이는 사용자에게 도움이 되고 싶을 때 사용하는 예외의 좋은 예시입니다. 예를 들어 Vector의 경우, 우리는 plus()에서 만약 두 벡터가 서로 다른 차원을 지녔다면 예외를 던져야 합니다. 이를 위해, 다음 문구를 plus()의 시작 부분에 추가해볼 수 있죠.

if (coords.length != b.coords.length) throw new RuntimeException("Vector dimensions disagree.");

  Vector가 내부적으로 배열을 사용하기 때문에 서로 다른 차원의 Vector가 더해지면서 ArrayOutOfBoundsException이 발생하는 것보다는, 직접 이렇게 유익한 정보를 주는 예외를 발생시키는 것이 클라이언트들에게도 훨씬 더 좋을 것입니다.

Assertions

  assertion은 여러분이 프로그램의 중간에서 참이라 단언할 수 있는 불리언 식입니다. 만약 해당 식이 거짓이라면, 프로그램은 종료되며 오류 메시지를 보고할 것입니다. Assertion은 버그를 찾아내고 프로그램의 정확성을 보장하기 위해 널리 사용되고 있습니다. 또한 그 자체로 프로그래머의 의도를 표현하는 일종의 문서가 되죠. 예를 들어, Counter (프로그램 3.3.2)는 count 변수가 음수이면 안 된다는 검증을 increment() 메소드의 마지막 문구에 추가해볼 수 있습니다.

assert count >= 0;

  이는 음수 카운트를 식별하는 장치죠. 좀 더 세부적인 메시지를 다음과 같이 넣어볼 수도 있습니다.

assert count >= 0 : "Negative count detected in increment()";

  이는 여러분들이 버그를 찾기 쉽게 만듭니다. 기본적으로 assertion은 비활성화되어 있지만, 명령행 옵션인 -enaebleassertions(-ea)를 통해 활성화시킬 수 있습니다. Assertion은 오로지 디버그를 위함입니다: 여러분의 프로그램은 assertion에 의존하는 무언가를 하면 안 되며, 평소에는 비활성화되어 있을 것입니다.

  여러분이 시스템 프로그래밍을 배운다면, 여러분의 코드가 시스템 오류나 무한 루프에 빠지더라도 절대 종료되지 않음을 보장하는 assertion을 배우게 될 것입니다. design-by-contact라는 한 프로그래밍 모델은 이 개념을 표현하죠. 자료형의 설계자는 선조건(precondition)과 후조건(postcondition), 불변식(invariant), 부작용(side effects)를 기술합니다.

  선조건은 해당 메소드를 호출할 때 클라이언트가 만족해야 하는 조건입니다. 후조건은 메소드로부터 무언가를 반환받을 때 구현 측에서 달성해내는 조건들입니다. 불변식은 메소드 호출 시 언제나 참임을 보장하는 조건들입니다. 마지막으로 부작용은 메소드가 유발할 수 있는 변경들에 대한 것들입니다. 개발 동안, 이러한 조건들은 assertion으로 검증될 수 있으며, 많은 프로그래머들이 assertion을 디버깅에 사용합니다.

  이번 절에서는 우리를 프로그래밍 언어 설계의 깊은 호수로 이끄는, 효과적인 자료형 설계에 대해 알아보았습니다. 전문가들은 설계 개념들을 지원하는 최고의 방법이 무엇인지에 대해 여전히 고군분투하고 있습니다. 왜 자바는 함수를 인자로 받지 않을까요? 왜 MATLAB은 가변 자료형을 지원하지 않을까요? 

  1장부터 이야기했듯이, 이러한 질문을 던지는 것은 프로그래밍 언어 설계자가 되는 지름길입니다. 그럴 계획은 없으시다면, 여러분의 최선은 가능한 언어들을 다양하게 사용해보는 것입니다. 

  대부분의 시스템은 여러분이 적절하게 사용할 수 있는 확장적인 라이브러리를 지녔습니다. 하지만 여러분은 종종 여러분의 클라이언트 코드를 간단화할 수 있으며, 추상화를 구현함으로써 다른 언어로의 이전을 손쉽게 해낼 수도 있습니다. 여러분의 진짜 목표는 손에 쥐어진 문제를 적절한 방법으로 추상화 하여 여러분의 작업을 끝마치는 것입니다. 그것은 곧, 자료형의 개발입니다.

끝.