이상엽/ 자료의 처리
우선순위 평가
인접행렬
개념
요소간의 연결 관계를 나타내는 정사각 행렬
- 참조한 (화살표가 나가는) 쪽은 행에, 참조된 (화살표를 받는) 쪽은 열에 쓴다.
- 1은 2와 3으로 화살표를 쏘고 있으므로, 1행은 2열과 3열에 값이 있음.
권위벡터와 허브벡터
인접행렬
에 대하여
와
을 각각
의 권위벡터와 허브벡터라 하며, 각 벡터의 성분을 권위 가중치와 허브가중치라 한다.
- 가중치로부터 중요도를 판단한다는게 아이디어
- 권위 벡터(
)는 연관받은 (열) 데이터에 대한 벡터가 된다. 그 각각의 값은 권위 가중치가 된다.
- 허브 벡터(
)는 연관한 (행) 데이터에 대한 벡터가 된다. 그 각각의 값은 허브 가중치가 된다.
- 권위 벡터(
- 권위 벡터와 허브 벡터는 상호작용을 기반으로 계속 값이 업데이트 된다.
- 업데이트 되는 와중에 어떤 기준선에 도달하여 값이 안정되면 최종적으로 그 벡터를 중요도 평가에 사용한다.
순위평가 원리
인접행렬 와 초기권위벡터
와 초기허브벡터
에 대하여
- 현재 권위 벡터는 이전 허브 벡터의 값을 원본 행렬(의 전치 행렬)에 곱하여 구하고, 마찬가지로 현재 허브 벡터는 이전 권위 벡터의 값을 원본 행렬에 곱하여 구한다.
- 이 곱을 반복하여 값을 업데이트 한다.
- 다만 이것을 점화식을 이용해서 구성하면 자기 자신만 보면 되는 (권위 벡터는 권위 벡터만으로, 허브 벡터는 허브 벡터만으로) 해석적인 결과가 구성되고, 이를 컴퓨터에 넣어서 계속 돌리면 값이 나온다.
와 같이 새로운 정규화된 권위벡터 와 허브벡터
를 정의한다. (
는 정수)
이때 를 연립하면 다음과 같이 정규화된
와
의 점화식을 얻을 수 있다.
마찬가지로
이 벡터들이 안정화가 되었다고 판단되는 상태로부터 각각 최종 중요도를 판별한다.
사례
10개의 인터넷 페이지(ㄱ~ㅊ)들 간의 인접행렬 $latex A &s=2가 다음과 같다고 하자.
앞에서 소개된 절차에 따라 $latex A &s=2의 정규화된 권위벡터가 안정화 될 때까지 반복계산한 결과는 다음과 같다.
- 위 수식은 소숫점 4자리까지만 연산하는데,
에 도달하면 값의 차이가 없기 때문에 더는 연산을 하지 않고 멈춘다.
- 만일 소숫점 자리를 5자리 이상으로 보면 더 돌 수 있다.
따라서 $latex A &s=2 권위가중치로부터 페이지 ㄱ, ㅂ, ㅅ, ㅈ는 관련이 적고, 그 외의 페이지는 중요도가 높은 것부터 ㅁ > ㅇ > ㄴ > ㅊ > ㄷ = ㄹ 순서대로 검색엔진에서 노출되어야 함을 알 수 있다.
- 요게 바로 구글 페이지 랭크 연산 방식
- 주요 키워드) 거듭제곱법(power method), 우세 고유벡터/값(dominant eigen vector/value)
자료압축
특잇값 분해
분해
한 행렬을 여러 행렬들의 곱으로 표현하는 것
ex) QR 분해, LU 분해, LDU 분해, 고윳값 분해, 헤센버그 분해, 슈르 분해, 특잇값 분해 등
특잇값
행렬
에 대하여
이
의 고윳값일 때
을 의 특잇값이라 한다.
- 고윳값을 만들려면 정사각 행렬이어야 한다. 반면 특잇값은 임의의 행렬에서도 만들어낼 수 있음.
- 일반적인 행렬을 정사각 행렬로 만들기 위해
행렬
에 대하여
를 한 후 거기서 특이값을 추출한다.
- 일반적인 행렬을 정사각 행렬로 만들기 위해
ex) 행렬 에 대하여
이므로
의 고유방정식은
이다
따라서 의 두 특잇값은 각각
이다.
특잇값 분해
영행렬이 아닌 임의의 행렬
는 다음과 같이 나타낼 수 있다.
이때 는 직교행렬이며,
는 주대각성분이
의 특잇값이고 나머지 성분들은
인
행렬이다.
- 여기서
는 합을 의미하는 것이 아니라
의 대문자 형태이다. (벡터를 의미하는
의 행렬 형태)
ex) 행렬 는 다음과 같이 특잇값 분해된다.
축소된 특잇값 분해
특잇값 분해에서 인 성분들로만 이루어진, 대수적으로 무의미한 행 또는 열을 제거한 형태를 축소된 특잇값 분해라고 한다.
즉,
또한 축소된 특잇값 분해를 이용하여 행렬 를 다음과 같이 전개한 것을
의 축소된 특잇값 전개라 한다.
ex)
자료압축 원리
압축되지 않은 행렬
를 위한 필요 저장 공간은
이다.
를 축소된 특잇값 분해한 결과가
라면
이제 필요한 저장 공간은 이다.
는 특잇값 개수 =
의 행개수 or 열개수
은
의 행 개수 =
의 성분개수
은
의 열 개수 =
의 성분개수
충분히 작다고 판단되는 에 대응하는 항들을 추가로 제거하면, 이때 필요한 저장 공간은
뿐이다.