googleAdsense_widever


Scheme 에서 행렬 다루기 _ 01 LISP

" matrix determinant 구하는 scheme code 입니다. " : http://cafe.naver.com/lisper/20
파일 : matrix.ss

matrix determinant를 먼저 하고 
나중에 inverse matrix를 통한 multiple regression 을 해보구요
그 후에 R^2 그리고 각종 test statistic 등을 해봅시다. (코드 아직 안 썼어요^^;;)

matrix는 key 가 (row-index colum-index) 인 리스트형태이고
value 가 matrix element 값인 해쉬테이블 형태로 시작합니다.
나중에 mat->list , list->mat 등의 프로시저도 쓰면 좋겠죠.

finance에서 쓰는 regression model의 설명변수는 많아야 10개 내외이므로
efficiency에 대해 고민할 필요가 없습니다. 아주 커야 20*20 matrix입니다.
따라서 복잡한 알고리즘을 생각하지 말고 일단은 determinant의 정의를 통해 구해봅시다.

lisp implementation은 plt-scheme (module mode) 이며
우리가 해야 할 일이 너무도 명확한 상황이므로 top-down approach로 갑니다. 시작합시다

우리가 쓸 모듈명을 적어줍니다.
#lang scheme

(define (det mat)
  (define (det-2x2 mat)
    (let ((a11 (hash-ref mat '(1 1)))
          (a12 (hash-ref mat '(1 2)))
          (a21 (hash-ref mat '(2 1)))
          (a22 (hash-ref mat '(2 2))))
      (- (* a11 a22)
         (* a12 a21))))
  (let ((frow (hash-filter mat (lambda (key value) (= (first key) 1)))))
    (if (= (hash-count frow) 2)
        (det-2x2 mat)
        (foldl + 0 
               (hash-map
                frow
                (lambda (key value) 
                  (if (odd? (second key))
                      (* value (det (cofactor mat (first key) (second key))))
                      (* (- value) (det (cofactor mat (first key) (second key)))))))))))

initial condition을 1*1 matrix의 determinant를 구하는 걸로 할 수도 있지만 저정도면 뭐 적당하죠.
예를 들면 3*3 matrix의 경우
a11*mat11 - a12*mat12 + a13*mat13
(mat11은 cofactor, 즉 1행 1열을 제외한 행렬입니다.)
물론 0 이 포함된 행을 찾아서 하면 더 빠르겠지만 얻어지는 이득이 거의 없습니다.

hash-filter 는 제가 쓴 프로시저입니다. 이렇게 생겼구요
(define (hash-filter ht pred)
  (let ((out-ht (make-hash)))
    (hash-for-each
     ht
     (lambda (key value) (when (pred key value)
                           (hash-set! out-ht key value))))
    out-ht))
argument 중 pred 은 predicate 입니다. 저 조건을 만족하는 애들만 골라서 다시 해쉬테이블을 만들어 리턴합니다.

이제 cofactor를 구해봅시다
(define (cofactor mat row col)
  (let ((ht (make-hash)))
    (hash-for-each 
     mat
     (lambda (key value) (unless (or (= row (first key)) (= col (second key)))
                           (hash-set! ht key value))))
    (reorder-index ht)))
아주 쉬운데요 문제는 행렬에서 그냥 특정 행과 열을 지워버리면
행렬의 인덱스가 안 맞는 다는 거죠 3x3 행렬의 두번째 row 와 3번째 colum을 없애면
인덱스가 1 2 , 1 2 여야 하는데  1 3 , 1 ,2 이런 식으로 되죠
그래서 reorder-index 라는 프로시저가 필요합니다.

(define (reorder-index mat)
  (let* ((ht (make-hash))
         (rows (get-row-index mat))
         (cols (get-col-index mat)))
    (hash-for-each mat (lambda (key value)
                         (hash-set! ht (list (second (assoc (first key) (bind-index rows)))
                                             (second (assoc (second key) (bind-index cols))))
                                    value)))
    ht))

여기서 get-row-index 와 get-col-index 는 다음과 같습니다.
(define (get-row-index mat)
  (sort (make-set (hash-map mat (lambda (key value) (first key)))) <))
(define (get-col-index mat)
  (sort (make-set (hash-map mat (lambda (key value) (second key)))) <))
거의 똑같은 프로시저이므로 abstraction이 가능하지만 하지 않았습니다.
그러려면 argument를 하나 더 늘리거나 keyword를 사용해야하는데 이렇게 간단한 프로시저에
그렇게 까지 할 필요를 못느껴서 입니다. 이름자체가 argument인거죠

여기서 make-set 이라는 프로시저가 보이는데요 이건 똑같은(equal? 로 똑같은 eq? 가 아니라)
element를 없애는 것이므로 remove-duplicate 와 같은 이름이 되어야하나
수학에서 쓰는 집합과 같은 것을 만든다는 의미로 make-set 이라고 썼습니다.
(define (make-set items)
  (let ((ht (make-hash)))
    (for-each (lambda (i) (hash-set! ht i '())) items)
    (hash-map ht (lambda (key value) key))))
해쉬 테이블을 이용했습니다. 보시면 어떻게 하는 건지 쉽게 아실 거에요

이제 bind-index라는 프로시저입니다.
(define (bind-index items)
  (map (lambda (item index) (list item index))
       items (enumerate-interval 1 (length items))))

마지막으로 enumerate-interval 입니다.
(define (enumerate-interval from to)
  (if (> from to)
      '()
      (cons from (enumerate-interval (+ from 1) to))))

이제 위의 코드들을 갖다 붙이고
(define sample-mat #hash(((1 1) . 2) ((1 2) . 0) ((1 3) . -4) ((1 4) . 6)
                         ((2 1) . 4) ((2 2) . 5) ((2 3) . 1) ((2 4) . 0)
                         ((3 1) . 0) ((3 2) . 2) ((3 3) . 6) ((3 4) . -1)
                         ((4 1) . -3) ((4 2) . 8) ((4 3) . 9) ((4 4) . 1)))
이런 매트릭스를 하나 만든후

(det sample-mat) 이라고 drscheme repl에다가 치면 1134 라고 나올겁니다

덧글

댓글 입력 영역


공지

어서오십시오.
트위터 : @FCliver
기저심리학 : 네이버카페
카카오톡 : FCliver
페이스북 : Fredric Cliver

통계 위젯 (화이트)

012
111
285966

접속자 위치