비지도 학습
알고리즘이 레이블이 없는 데이터를 바로 사용하여 훈련하는 것을 비지도 학습이라고 한다.
앞에서 비지도 학습방법인 차원축소를 다뤘다.
군집clustering
비슷한 샘플을 클러스터cluster 로 모은다. 군집(클러스터링)은 데이터 분석, 고객 분류, 추천 시스템, 검색 엔진, 이미지 분할, 준지도 학습, 차원 축소 등에 사용할 수 있는 도구다.
이상치 탐지outlier detection
'정상'데이터가 어떻게 보이는지 학습하고, 비정상 샘플을 감지하는데 사용한다. 제조라인의 결함 감지, 시계열 데이터에서 새로운 트랜드를 찾을때 등에 사용된다.
밀도 추정density estimation
데이터셋 생성 확률 과정random process의 확률 밀도 함수probability density function 을 추정한다. 밀도추정은 이상치 탐지에도 널리 사용된다. 밀도가 매우 낮은 영역에 놓은 샘플이 이상치일 가능성이 크기 때문이다. 또한 데이터 분석과 시각화에도 유용하다.
9.1 군집
비슷한 곳에 동일하지는 않지만 충분히 비슷해서 같은 종류에 속한다고 판단할 수 있는 것들을 나누는 작업을 군집clustering이라고 부른다. 비슷한 샘플을 구별해 하나의 클러스터cluster 또는 비슷한 샘플의 그룹으로 할당하는 작업니다. 분류와 동일하게 각 샘플은 하나의 그룹에 할당되지만, 분류와달리 군집은 비지도 학습으로 따로 레이블이 지정되어 있지않다.
특성을 다양하게 사용할수록 군집 알고리즘이 클러스터를 더 잘 구분할 수 있다.
고객 분류
고객의 구매이력이나 웹사이트 내 행동을 기반으로 클러스터로 모을 수 있다. 이를 통해 고객에 대해서 더 잘 이해할 수 있다. 그래서 동일한 클러스터의 고객이 선호하는 컨텐츠를 추천할 수 있다.
데이터 분석
새로운 데이터셋을 분석할 때 군집 알고리즘을 실행하고 각 클러스터별로 분석하면 도움이 된다.
차원 축소 기법
한 데이터셋에 군집 알고리즘을 적용하면 샘플의 친화성affinity 을 측정가능하다. 각 샘플의 특성 벡터 x 는 클러스터 친화성 벡터로 바꿀 수 있다. k개의 클러스터가 있다면 이 벡터는 k 차원이 된다. k는 일반적으로 특성 벡터의 차원보다 훨신 낮다.
이상치 탐지
모든 클러스터에 친화성이 낮은 샘플은 이상치일 가능성이 높다. 웹사이트 내 행동을 기반한 클러스터는 웹사이트에 비정상 요청을 보내는 사용자를 감지할 수 있다. 특히 제조분야에서 결함을 감지할 때 유용하고 부정 거래 감지fraud detection 에도 활용 된다.
준지도 학습
많은 샘플에 일부분의 적은 샘플만 레이블이 되었다면, 군집을 수행하고 동일한 클러스터에 있는 모든 샘플에 레이블을 전파할 수 있다. 지도 학습 알고리즘에 필요한 데이터 레이블링에 큰 역할을 한다.
검색 엔진
검색 엔진에서 비슷한 이미지를 찾기 위해서, 데이터 베이스의 모든 이미지에 군집알고리즘을 통해 클러스터가 정해져 있어야한다. 사용자가 제공한 이미지를 훈련된 군집 모델을 이용해 이미지의 클러스터를 찾고 클러스터의 모든 이미지를 반환한다.
이미지 분할
색을 기반으로 픽셀을 클러스터로 모으고, 각 픽셀의 색을 클러스터의 평균색으로 바꿔 이미지의 색상 종류를 크게 줄인다. 그러면 물체의 윤곽을 감지하기 쉬워져 물체 탐지 및 추적 시스템에서 이미지 분할을 많이 사용한다.
클러스터의 정의는 비지도학습이므로 상황에 따라 다르고, 알고리즘에 따라 다르다.
어떤 알고리즘은 센트로이드centroid 라 부르는 특정 포인트를 중심으로 모인 샘플을 찾고,
어떤 알고리즘은 샘플이 밀집되어 연속된 영역을 찾고,
어떤 알고리즘은 계층적으로 클러스터의 클러스터를 찾는다.
9.1.1 k-평균 k-mean
k-mean 알고리즘은 k개의 클러스터 개수를 지정하고, k개의 센트로이드를 찾아 각 샘플과 가장 가까운 센트로이드가 포함된 클러스터로 포함시키는 방식이다. 그렇기 때문에 클러스터의 크기가 많이 다르면 잘 작동하지 않는다. 특정 클러스터의 분산이 크면 분산이 작은 클러스터에 포함될 수 있다.
하드 군집hard clustering 과같이 샘플을 하나의 클러스터에 할당하는 것보다, 샘플에 각 클러스터의 점수를 부여하는 것이 유용할 수 있다. 이를 소프트 군집soft clustering 이라고 한다. 이 점수는 샘플과 센트로이드 사이 점수가 될수도, 가우시안 방사 기저함수와 같은 유사도 점수가 될 수 있다.
샘플과 센트로이드 사이의 거리를 이용해서 비선형 차원 축소를 수행할 수 있다.
k-평균 알고리즘
센트로이드가 주어진다면, 센트로이드와의 거리측정으로,
레이블이 주어진다면, 각 클러스터의 평균으로 센트로이드를 쉽게 구할 수 있다.
센트로이드가 주어지지않는다면,
랜덤하게 k개의 샘플을 선택하여 센트로이드로 지정한다.
샘플에 레이블을 할당하고, 클러스터의 평균을 센트로이드로 지정하는 업데이트 과정을 반복한다.
이런식으로 센트로이드에 변화가 없을 때까지 반복한다. 이 알고리즘은 결국 수렴하는 것을 보장하고, 수렴한 값을 센트로이드로 지정한다.
k-mean 알고리즘은 데이터가 군집할 수 있는 구조일때 선형적이고, 그렇지 않다면 지수적으로 급격히 증가할 수 있다.
단 랜덤하게 센트로이드를 지정할 경우 적절한 솔루션에 도달하지 않을 수 있다.
센트로이드 초기화 방법
적절한 센트로이드 위치를 근사하게 알 수 있다면, 직접 초기 센트로이드 위치를 주입한다.
최적의 솔루션에 대한 기준은 각 샘플과 가장 가까운 센트로이드의 평균 제곱거리로 모델의 이니셔inertia 라고 부르는 값을 통해 판단한다.
k-평균++ 알고리즘
다른 센트로이드와의 거리가 먼 센트로이드를 선택하는 초기화 단계를 추가한다.
1. 데이터 셋에서 무작위로 균등하게 하나의 센트로이드 c_1을 선택한다.
2. 센트로이드들 과의 거리를 통해 D(x_i)^2 / sum(D(x_j)^2 의 확률로 센트로이드 c_i 로 선택한다.
3. k 개의 센트로이드가 선택될 때까지 이전단계를 반복한다.
k-평균 속도 개선과 미니배치 k-평균
k평균 알고리즘에 대해 불필요한 거리 계산을 삼각 부등식을 통해서 많이 줄일 수 있다. 또한 샘플과 센트로이드 사이의 거리에 하한선과 상한선을 유지하도록 한다.
또한 데이터셋이 매우 클경우 미니배치를 이용해서 각 반복마다 센트로이드를 조금씩 이동한다. 이는 알고리즘의 속도를 3~4배정도 빠르게 한다.
최적의 클러스터 개수 찾기
일반적으로 클러스터의 개수를 설정할지 알 수 없다. 그런데 올바르게 지정하지 않으면 결과는 매우 나빠질 수 있다.
이니셔는 클러스터 개수를 찾는데 적합한 기준이 아니다. 클러스터의 개수가 늘어날수록 이니셔는 작아지는 경향이 있기 때문이다.
그럼에도 이니셔를 사용하는 방법은 k에 대한 이니셔 그래프가 꺽이는 즉 기울기가 크다가 급격히 작아지는 구간(엘보)를 선택하는 법이다.
이보다 더 정확한 방법은 실루엣 점수silhouette soure 을 사용하는 것이다. 이 값은 모든 샘플에 대한 실루엣 계수silhouette coefficient의 평균이다. 샘플의 실루엣 계수는 (b - a) / max(a, b) 으로 구하고, 이때 a는 샘플이 속한 클러스터의 다른 샘플들과의 거리 평균이고, b는 가장 가까운 클러스터 샘플까지의 거리이다.
실루엣 계수는 -1 ~ +1 까지 변화하고, +1에 가까울수록 자신이 속한 클러스터에 적합하고, 0이면 클러스터 경계에, -1 이면 샘플이 잘못된 클러스터에 할당되어 있다는 의미이다.
이 실루엣 점수을 통해 정보를 얻을 수 있고, 추가적으로 모든 샘플의 실루엣 계수를 샘플이 속하는 클러스터와 계숫값으로 정렬해서 더많은 정보가 있는 실루엣 다이어그램silhouette diagram 을 얻을 수 있다.
실루엣 계수는 높을수록, 클러스터에 포함된 샘플의 개수가 일정할수록 이상적이다.
9.1.2 k-mean k-평균의 한계
k-mean알고리즘은 빠르고 확장이 용이하지만, 최적이 아닌 솔루션을 피하려면 여러번 실행해야 하고, 클러스터의 개수도 지정해 주어야 한다. 또한 각 클러스터의 크기와 밀도가 다양할 경우와, 원형이 아닐경우 잘 작동하지 않는다.
타원형의 데이터에서는 k-mean 대신 가우시안 혼합 모델이 더 잘 작동한다. k-mean 알고리즘을 사용하기전에 각 입력 특성의 스케일을 조정하는것이 중요하다.
9.1.3 군집을 사용한 이미지 분할
이미지 분할image segmentation 은 이미지를 세그먼트segment 여러개로 분할하는 작업이다.
시맨틱 분할semantic segmentation 에서는 동일한 종류의 물체를 같은 세그먼트에 할당한다.
군집을 색상 분할color segmentation 에 사용할 수 있다. 클러스터의 수가 표현가능한 색의 수로 지정되고, 각 픽셀은 클러스터에 포함되고, 픽셀의 색상은 포함된 클러스터의 평균색으로 표현된다. 이런식으로 color segmentation을 수행가능하다.
9.1.4 군집을 사용한 전처리
전처리 단계인 차원 축소에 군집을 사용가능하다. 특성의 수를 클러스터의 수로 줄임으로 써 데이터 전처리를 수행한다.
9.1.5 군집을 사용한 준지도 학습
준지도 학습은 레이블이 없는 데이터가 많고 레이블이 있는 데이터가 적을 때 사용하는 학습법이다.
준지도학습은 훈련 세트를 특정 개수의 클러스터로 모으고, 각 클러스터에서 센트로이드에 가장 가까운 샘플을 대표 샘플로 지정한다.
모든 대표 샘플들의 레이블을 수동으로 지정한다. 이런 이유로 무작위 샘플대신 대표 샘플을 사용한다.
각 클러스터에 속한 샘플들의 레이블을 대표 샘플의 레이블로 전파하는 것을 레이블 전파label propagation이라고 한다. 하지만 모든 클러스터의 샘플에 레이블을 지정하면 정확도가 줄어들기 때문에, 센트로이드와 가까운 특정 비율의 샘플에만 레이블을 전파한다.
능동학습
모델과 훈련세트를 지속적으로 향상시키기위해, 전문가가 학습 알고리즘과 상호작용하여 레이블을 제공한다.
불확실성 샘플링uncertainty sampling 이 능동학습에 널리 사용되는 전략이다.
1. 수집한 레이블된 샘플에서 모델을 추출하고, 레이블되지 않은 모든 샘플에 대한 예측을 만든다.
2. 모델이 가장 불확실하게 예측한 샘플을 전문가에게 레이블링을 요청한다.
3. 레이블을 부여하는 노력만큼 성능이 향상되지 않을 때까지 반복한다.
9.1.6 DBSCAN
이 알고리즘은 연속적으로 밀집된 지역을 클러스터로 정의한다.
1. 알고리즘이 각 샘플에 미리 정한 작은 거리인 입실론 내에 샘플이 몇개 놓여있는지 찾는다. 이 지역을 샘플의 입실론-이웃epsilon-neighborhood 라고 한다.
2. 입실론-이웃 내에 적어도 min_samples개 샘플이 있다면, 이를 핵심 샘플core instance 로 간주한다. 즉 핵심 샘플은 밀집된 지역에 있는 샘플이다.
3. 핵심 샘플의 이웃에 있는 모든 샘플은 같은 클러스터에 속한다. 이웃에는 다른 핵심 샘플이 포함될 수 있고, 핵심 샘플의 이웃이 핵심 샘플이면 클러스터의 범위를 늘려나간다.
4. 핵심 샘플이 아니고 이웃도 아닌 샘플은 이상치로 판단한다.
이 알고리즘은 샘플이 충분히 밀집되어 있고, 밀집 되지 않은 지역과 잘 구분될 때 잘 작동한다.
그런데 sklearn의 DBSCAN은 predict 메서드를 제공하지 않고 fit_predict를 제공한다. 즉 새로운 샘플에 대해 클러스터 예측이 불가능하다.
이렇게 분류한 핵심 샘플, 클러스터, 이상치 샘플을 통해서 자유롭게 예측기를 설계할 수 있다.
DBSCAN은 간단하지만 강력한 알고리즘이다. 이상치에 안정적이고 하이퍼 파라미터가 2개뿐이다. 하지만, 클러스터간 밀집도가 크게 다르면 모든 클러스터를 올바르게 잡아내기 어렵다.
계산복잡도는 O(m log(m))이고 eps가 커질수록 O(m^2)에 가까워진다.
9.1.7 다른 군집 알고리즘
병합 군집
클러스터 계층을 밑바닥부터 위로 쌓아 구성한다. 처음엔 샘플하나가 각클러스터이고, 반복이 진행될때마다 가까운 두 클러스터가 합쳐진다. 클러스터가 성장하면서 점점 멀리있는 데이터를 포함시키고, 지정해둔 클러스터 개수가 되면 성장을 멈춘다.
이렇게 병합되는 과정의 클러스터 쌍을 모두 트리로 그리면 이진트리를 얻을 수 있다. 또는 이웃한 샘플간 거리를 담은 m, m 크기의 휘소 행렬을 연결 행렬로 대규모 샘플에도 잘 적용할 수 있다.
BIRCH
BIRCH(balanced iterative reducing and clustering using hierarchies) 알고리즘은 특별히 대규모 데이터셋을 위해 고안되었다. 특성 개수가 너무많지 않으면 k-mean 보다 빠르고 비슷한 결과를 만든다. 샘플을 클러스터에 빠르게 할당할 수 있는 정보를 담은 트리구조를 만들어 모든 샘플을 저장하지 않는다.
평균-이동
이 알고리즘은 각 샘플을 중심으로 하는 원을 그리고, 원마다 안에 포함된 모든 샘플의 평균을 구한다.
그리고 원의 중심을 평균점으로 이동시키고, 모든 원이 움직이지 않을 때까지 평균-이동mean-shift를 계속한다.
이 평균-이동은 지역의 최대 밀도를 찾을 때까지 원을 이동시킨다. 동일한 지역에 안착된 원에 포함된 샘플을 모두 같은 클러스터이다. 모양이나 개수에 상관없이 클러스터를 찾고, 하이퍼파라미터도 Bandwidth하나 뿐이지만, 내부 밀집도가 불균형할때 여러개로 나뉘고, 계산복잡도도 O(m^2)이다.
유사도 전파
이 알고리즘은 투표 방식을 사용한다. 각 샘플은 자신을 대표할 수 있는 비슷한 샘플에 투표하고, 수렴할때 각 대표와 투표한 샘플이 클러스터를 이룬다. 유사도 전파affinity propagation은 크기가 다른 여러개의 클러스터를 감지할 수 있다.
계산복잡도는 O(m^2)이다.
스펙트럼 군집
이 알고리즘은 샘플사이의 유사도 행렬을 받아 저차원 임베딩을 만들어, 저차원 공간에서 또 다른 군집 알고리즘을 사용한다. 스펙트럼 군집spectral clustering은 복잡한 클러스터 구조를 감지하고 그래프 컷graph cut 을 찾는데 사용할 수 있다.
9.2 가우시안 혼합
가우시안 혼합 모델Gaussian mixture model(GMM) 은 샘플이 파라미터 알려지지 않은 여러개의 혼합 가우시안 분포에 의해서 생성되었다고 가정하는 모델이다. 하나의 가우시안 분포에서 생성된 모든 샘플은 하나의 클러스터를 형성한다.
샘플마다 k개의 클러스터에서 j 번째 클러스터를 선택할 확률은 가중치 phi_j 으로 정의되고, i번째 샘플이 선택한 클러스터 인덱스는 z_i 로 표기한다.
z_i = j 이면, i번째 샘플이 j 번째 클러스터에 할당되었으면, 이 샘플의 위치 x_i 는 평균이 mu_j 이고 공분산행렬이 Sigma_j 인 가우시안 분포에서 랜덤하게 샘플링된다.
- 원은 확률 변수 ( z, x )
- 사각형은 고정값 (모델의 파라미터)
- 큰 사각형을 플레이트plate, 안의 내용이 반복됨
- 플레이트의 오른쪽아래 숫자는 반복수
- 실선 화살표는 조건부 의존성
- 구불구불한 화살표는 스위치switch z_i값에 따라 샘플x_i가 다른 가우시안 분포에서 샘플링됨.
- 색이 채워진 원은 관측 변수observed variable
- 알려지지 않은 변수는 잠재 변수latent variable
데이터셋 X가 주어지면 가중치 벡터 Phi와 전체 분포의 파라미터 mu_1 ~ mu_k, sigma_1 ~ sigma_k 까지를 추정한다.
기댓값-최적화expectation-maximization (EM) 알고리즘
클러스터 파라미터를 랜덤하게 초기화한다.
샘플을 클러스터에 할당한다(기대값 단계expectation step)
클러스터를 업데이트 한다(최대화 단계maximization step)
수렴할 때까지 두 단계를 반복한다.
EM은 k-mean과 비슷하지만, 클러스터 중심뿐만 아니라, 크기, 모양, 방향과 클러스터의 상대적 가중치를 포함한다.
기댓값 단계에서 알고리즘은 클러스터 파라미터에 기반하여 각 클러스터에 속할 확률을 예측하고,
최대화 단계에서 각 클러스터가 데이터셋의 모든 샘플을 사용해 업데이트 된다.
클러스터에 속할 추정 확률로 샘플에 가중치가 적용된다. 이 확률을 샘플에 대한 클러스터의 책임responsibility 라고 부른다.
가우시안 혼합모델은 생성 모델generative model 로 새로운 샘플을 생성가능하다.
또한 샘플의 위치에 확률 밀도 함수probability density function 을 찾을 수 있다.
이 알고리즘은 클러스터가 많거나, 샘플이 적을 때 EM이 최적의 솔루션으로 수렴하기 어렵다. 이런 어려움을 줄이려면 학습할 파라미터 개수를 제한한다. 그중 한 방법이 클러스터의 모양과 방향을 제한한다. 즉 공분산 행렬에 제약을 추가한다.
- 'spherical' : 모든 클러스터가 원형 O(kmn)
- 'diag' : 타원형, 하지만 타원의 축과 좌표축과 나란함 O(kmn)
- 'tied' : 동일한 타원모양, 크기, 방향 O(kmn^2 + kn^3)
- 'full' : 제약없음 O(kmn^2 + kn^3)
9.2.1 가우시안 혼합을 사용한 이상치, 특이치 탐지
가우시안 혼합에서 밀도가 낮은 지역에 있는 샘플을 이상치로 보아 이상치 탐지outlier detection을 수행할 수 있다.
특이치 탐지novelty detection 은 이상치로 오염되지 않은 깨끗한 데이터셋에서 훈련하는 것이 이상치 탐지와는 다르다
9.2.2 클러스터 개수 선택하기
k-mean에서의 실루엣 점수를 이용하지 못하기 때문에,
BIC Bayesian information criterion 혹은,
AIC Akaike information criterion 와 같은은
이론적 정보 기준theoretical information criterion 을 최소화 하는 모델을 찾는다.
m : 샘플의 개수
p : 파라미터 개수
L_hat : 가능도 함수 likelihood function의 최대값
BIC AIC 모두 학습할 파라미터가 많을수록 벌칙을 가하고, 데이터에 잘 학습하는 모델에 보상을 더한다.
[[가능도 함수]]
확률probability 과 가능도likelihood 는 종종 구별 없이 사용되지만 통계학에서는 다른 의미를 가진다.
확률은 파라미터 theta 인 확률모델이 주어질 때, 미래 출력 x 가 얼마나 그럴듯한지 설명하고,
가능도는 출력 x 가 주어질때, 파라미터 theta 값이 얼마나 그럴듯한지 설명한다.
가능한 모든 x에 대해 확률 분포를 적분하면 항상 1이지만, 가능한 모든 theta에 대해서 가능도 함수를 적분하면 어떤 양수값도 될 수 있다.
데이터셋 X 가 주어졌을때, 일반적으로 모델 파라미터에 대해 가장 그럴 듯한 값을 예측하기 때문에
X에 대한 가능도 함수를 최대화 하는 값을 찾는다.
관측된 x에 대한 theta의 최대 가능도 추정maximun likelihoodestimate(MLE), L(theta | x) 를 최대화 한다.
만일 theta에 대한 확률분포 g가 존재하면, L(theta | x)를 최대화하는 것보다,
최대 사후 확률maximum a-posteriori(MAP)인 L(theta | x ) g( theta ) 를 최대화 하는것이 가능하다.
g( theta )가 MLE를 규제하므로 MAP을 MLE의 규제 버전으로 생각 가능하다.
로그는 항상 증가하는 함수이므로, 가능도 함수를 최대화하는 것과, 가능도함수에 로그를 취한것을 최대화하는 것과 같다. 일반적으로 곱의 최대화를 찾기 때문에 합의 최대화로 변환되는 로그를 최대화 하는것이 쉽다.
가능도함수를 최대화하는 값 theta_hat을 추정하면, AIC, BIC를 계산하기위한 L_hat 값을 계산할 수 있다.
9.2.3 베이즈 가우시안 혼합 모델
최적의 클러스터 수를 수동으로 찾지않고, 불필요한 클러스터의 가중치를 0 으로 만드는 베이즈 가우시안 혼합 모델Bayesian Gaussian Mixture Model 을 사용 할 수 있다.
클러스터 개수 n_components 를 최적의 클러스터수보다 크다고 믿는 값으로 지정하면, 이 알고리즘은 불필요한 클러스터를 자동으로 제거한다.
이 모델에서의 클러스터 파라미터(가중치, 평균, 공분산 행렬 등)는 고정된 모델 파라미터가 아니라, 클러스터 할당 처럼 잠재 확률 변수로 취급된다.
'이해부족'
9.2.4 이상치 탐지와 특이치 탐지를 위한 다른 알고리즘
PCA (inverse_transform() 메서드를 가진 다른 차원 축소 기법)
이상치의 재구성오차를 구한다.
Fast-MCD minimum covariance determinant
EllipticEnvelope 클래스는 정상 샘플이 하나의 가우시안 분포에서 생성되었다고 가정하고, 이미 데이터셋은 이상치로 오염되었다고 가정한다.
따라서 가우시안 분포의 파라미터를 추정할때 이상치를 무시한다. 즉 모든 샘플을 정상으로 취급하지 않는다.
아이솔레이션 포레스트
고차원 데이터셋의 이상치를 탐지하는데 효율적이다. 무작위로 성장한 결정 트리로 구성된 랜덤 포레스트를 만든다.
모든 샘플을 다른 샘플들과 격리 될때까지 트리 성장을 지속한다. 이상치는 다른 샘플과 멀리 떨어져 있기때문에, 평균적으로 결정트리에서 적은 단계로 다른 샘플과 격리된다.
LOF local outlier factor
이상치 탐지에 유용하다. 주어진 샘플의 주위 밀도와, 이웃 주위 밀도를 비교한다. k-neighborhood 보다 더 격리된다.
one-class SVM
특이치 탐지에 잘 맞는 알고리즘이다. 커널 SVM 분류기와 비슷하게 모든 샘플을 고차원에 맵핑하고, 선형 SVM분류기를 사용해 이상치와 정상 샘플을 분리한다.