머신러닝에서 고유값의 활용
PCA, Spectrum Clustering ...
머신러닝에서 고유값이 어떻게 활용되고 있는 지 정리한 블로그 포스트의 글을 번역했습니다. 원문의 제목은 "The essence of eigenvalues and eigenvectors in Machine Learning" 입니다.
수학 분야에서 단어 Eigen은 아마도 독일어 단어 중에서 가장 유용하게 쓰이는 단어가 아닐까 합니다. 한 행렬의 고유값과 고유 벡터를 찾는 다는 것은, 해당 행렬의 특성을 찾는다고 표현할 수 있겠습니다.
고유 벡터에 깊숙이 들어가기 전에 직사각형 배열의 숫자를 제외한 행렬이 무엇인지 이해해야합니다.
행렬은 단순히 벡터에 적용된 선형 변환입니다. 벡터에 다른 유형의 변형이 적용될 수 있습니다.
아래 매트릭스 변환을 확인해 봅시다.
img = cv2.imread(path_to_image,flags=cv2.IMREAD_UNCHANGED)
img = cv2.cvtColor(img,cv2.COLOR_BGR2RGB)
rows,cols,_ = img.shape
M = np.float32([[1, -np.sin(.1), 0],[0, np.cos(.1), 0]])
out = cv2.warpAffine(img,M,(cols,rows))
이 행렬 M은 이미지와 어떤 관계가 있습니까? 이미지의 모든 벡터에 수평 전단(horizontal shear)을 적용했습니다.
#Let's try this one
M = cv2.getRotationMatrix2D((cols/2,rows/2),45,1)
out = cv2.warpAffine(img,M,(cols,rows))
print(M)
=> [[ 0.70710678 0.70710678 -124.36235483]
[ -0.70710678 0.70710678 501.76271632]]
매트릭스 M이 이미지에 대해 무엇을 했습니까?
이 선형 변환 M은 이미지의 모든 벡터를 45도 회전시킵니다.
M = [[ 1. 0. 100.]
[ 0. 1. 100.]]
out = cv2.warpAffine(img,M,(cols,rows))
이미지를 가로 및 세로 방향으로 변환합니다.
회전에는 고유 벡터가 없습니다 (180도 회전의 경우 제외). 순수한 전단의 경우 수평 벡터는 고유 벡터입니다. 벡터 길이가 변하는 요인을 고유 값이라고합니다.
Application
고유 값 과 고유 벡터 의 개념은 많은 실제 응용에 사용됩니다. 저는 이것들 중 몇 가지만 논의 할 것입니다.
주성분 분석 (PCA)
PCA는이 개념을 사용하여 차원을 저축하여 데이터를 압축하는 데 사용되는 매우 일반적인 고전적 차원 축소 기술입니다. 차원의 저주가 이미지를 다루기 위해 고전적인 컴퓨터 비전에서 매우 중요한 문제였으며 기계 학습에서도 차원이 높은 모델의 특징 그 결과 학습에 많은 양의 데이터가 필요합니다.
간단한 행렬 연산과 통계를 사용하여 원본 데이터의 투영을 같은 수 또는 더 적은 차원으로 계산하는 방법입니다.
데이터 행렬 X 를 n × p 크기로 합시다. 여기서 n은 샘플 수이고 p는 각 샘플의 차원입니다. PCA에서는 공분산 행렬이 대칭이기 때문에 본질적으로 고유 값 분해에 의해 X의 공분산 행렬을 대각 화합니다.
C = VLVᵀ
In Python-
from numpy import cov
from numpy.linalg import eig
X = array([[-2, -2], [0, 0], [2, 2]])
C = cov(X)
#To do eigendecomposition of C
values, vectors = eig(C)
#Project data into pricipal directions
P = vectors.T.dot(X.T)
print(P.T)
Output-
[[-2.82842712 0. ]
[ 0. 0. ]
[ 2.82842712 0. ]]
여기서 V는 고유 벡터 행렬 (각 열은 고유 벡터)이고 L 는 대각선에서 고유 값이 λ_i 인 대각선 행렬입니다 .
여기에서 공분산 행렬 인 대칭 행렬의 고유 벡터는 실수와 직교입니다.
고유 벡터 라고 주축 또는 주 방향 데이터를. 주축에 데이터를 투영하는 것을 주성분이라고 합니다.
데이터를 원래의 차원보다 적은 주요 방향으로 투영하여 데이터의 차원을 줄입니다.
스펙트럼 클러스터링
K-Means는 클러스터링에 가장 널리 사용되는 알고리즘이지만 클러스터 초기화 및 기능의 차원에 대한 의존성과 같은 몇 가지 문제가 있습니다. 또한 클러스터가 아래와 같이 구형이 아닌 경우 문제에 직면합니다.
from sklearn.datasets
import make_moons
X_mn, y_mn = make_moons(150, noise=.07, random_state=21)
fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('Data with ground truth labels ', fontsize=18, fontweight='demi')
ax.scatter(X_mn[:, 0], X_mn[:, 1],c=y_mn,s=50, cmap='viridis')
스펙트럼 군집화는 행렬 의 고유 벡터 를 사용하여 K 군집을 찾는 방법 입니다. 이러한 문제를 처리하고 클러스터링을위한 다른 알고리즘을 쉽게 능가합니다.
여기서 데이터는 그래프 형식으로 표시됩니다. 이제 클러스터링은 두 클러스터 A와 B 사이의 Cut (A, B)가 두 클러스터 사이의 가중치 연결의 합으로 정의되는 그래프 컷을 만드는 것으로 생각할 수 있습니다. 예를 들어
최적의 클러스터를 찾으려면 MinCut이 필요하며 MinCut 방법의 목표는 최소 가중치 합계 연결을 갖는 두 개의 클러스터 A와 B를 찾는 것입니다.스펙트럼 클러스터링에서이 최소 절단 목표는 그래프의 인접도 및도 행렬에서 계산 된 그래프 라플라시안 행렬을 사용하여 근사화됩니다. 증명은 여기에서 보십시오
알고리즘
주어진 : n 꼭지점과 모서리 가중치 Wij, 원하는 군집 수 k
구성 (정규화 된) 그래프 라플라시안 L, G, V, D = D - W
k의 가장 작은 고유 값에 해당하는 고유 벡터를 구합니다.
U를 고유 벡터의 n × k 행렬로 설정
k-means를 사용하여 C ′를 U의 행으로 지정하는 U의 클러스터 xi ′를 찾습니다.
xi ′가 클러스터 j에 할당 된 경우 point 번째 클러스터에 데이터 포인트 xi를 할당합니다.
from sklearn.neighbors
import radius_neighbors_graph
from scipy.sparse import csgraph
from sklearn.cluster
import KMeans
#Create adjacency matrix from the dataset
A = radius_neighbors_graph(X_mn,0.4,mode='distance', metric='minkowski', p=2, metric_params=None, include_self=False)
A = A.toarray()
'''Next find out graph Laplacian matrix, which is defined as the L=D-A where A is our adjecency matrix we just saw and D is a diagonal degree matrix, every cell in the diagonal is the sum of the weights for that point'''
L = csgraph.laplacian(A, normed=False)
eigval, eigvec = np.linalg.eig(L)
이제 k-means를 사용하여 k 클러스터를 찾고 xi를 eigvec의 행으로 만듭니다. 마지막으로 데이터 포인트를 클러스터에 할당하려면 xi'가 클러스터 j에 할당 된 경우 xi를 j 번째 클러스터에 할당하십시오.
Fiedler 벡터라고도하는 두 번째로 작은 고유 벡터는 최적의 분할 점을 찾아서 그래프를 재귀 적으로이 분할하는 데 사용됩니다.
전체 예제 코드는 여기를 참조 하십시오
https://github.com/ranjeetthakur/ml_codebase/blob/master/Spectral_clustering.ipynb
스펙트럼 군집의 변형 은 컴퓨터 비전의 지역 제안 기반 객체 탐지 및 시맨틱 세그먼테이션에 사용됩니다.
컴퓨터 비전의 관심 지점 감지
마지막으로 AI에서 가장 좋아하는 분야 인 Computer Vision에 대해 이야기하겠습니다. 컴퓨터 비전에서 이미지의 관심 지점은 해당 지역에서 고유 한 지점입니다. 이러한 점은 기능으로 사용되는 클래식 Computer Vision에서 중요한 역할을합니다.
코너는 SIFT, SURF 및 HOG와 같은 다른보다 복잡한 이미지 기능과 함께 유용한 관심 사항입니다. 코너 감지 방법 중 하나에 대해 설명하겠습니다.
http://www.cs.cmu.edu/~16385/s17/Slides/6.2_Harris_Corner_Detector.pdf
작은 창을 통해 모서리를 쉽게 인식 할 수 있습니다.
창 안에 모서리가있는 경우 창을 이동하면 강도 E가 크게 변경됩니다.
해리스 코너 검출기
알고리즘
작은 영역에서 이미지 그라디언트 계산
imggray = cv2.imread('checkerboard.png',0)
i_x = cv2.Sobel(imggray,cv2.CV_64F,1,0,ksize=5)
i_y = cv2.Sobel(imggray,cv2.CV_64F,0,1,ksize=5)
공분산 행렬 계산
# Calculate the product of derivates in each direction
i_xx, i_xy, i_yy = multiply(i_x, i_x), multiply(i_x, i_y), multiply(i_y, i_y)# Calculate the sum of product of derivates
s_xx, s_xy, s_yy = cv2.GaussianBlur(i_xx, (5,5), 0), cv2.GaussianBlur(i_xy, (5,5), 0), cv2.GaussianBlur(i_yy, (5,5), 0)
고유 벡터 와 고유 값을 계산합니다 .
해리스 는 더 빠른 근사를위한 방법 을 설명했습니다 . 고유 값을 계산하지 말고 Trace and Determinant 만 계산하십시오. 이 두 가지 속성을 조합 하여 모서리 측정 -R을 계산합니다.
행렬의 Determinant = 고유 값의 곱
행렬의 Trace = 고유 값의 합
# Compute the response of the detector at each point
k = .04 # Recommended value between .04 and .06
det_h = multiply(s_xx, s_yy) - multiply(s_xy, s_xy)
trace_h = s_xx + s_yy
R = det_h - k*multiply(trace_h, trace_h)
고유 값에 임계 값 을 사용하여 코너를 감지
ratio = .2 #
thresh 를 조정하는 수 = abs (R)> ratio * abs (R) .max ()
고유 값 이 0에 가까우 면 모서리가 아니므로 둘 다 큰 위치를 찾으십시오.
E는 모든 방향에서 거의 일정합니다.
λ2 > λ1 또는 λ1 > λ2는 모서리를 나타냅니다
λ1과 λ2가 크고 λ1 ~ λ2 E가 모든 방향으로 증가
전체 예제 코드는 여기를 참조하십시오
References
Normalized Cuts and Image Segmentation. J. Shi and J. Malik, 2000
A Combined Combined and Edge Detector, Chris Harris & Mike Stephens, 1988
Algebraic Connectivity of Graph M. Fiedler, 1973
