[데이터사이언스개론] Similarity, Neighbors, Clusters

수업 출처) 숙명여자대학교 소프트웨어학부 박동철 교수님 '데이터사이언스개론' 수업

 

[Similarity]

1. Similarity (유사도)  -> "거리" 개념

: 많은 데이터 사이언스 방법과 솔루션들의 근본이 된다.

 

- ex) 비슷한 것들 검색, 비슷한 것들 그룹화 (클러스터링), 상품 추천, 비슷한 케이스로부터의 추론

 

- objects 간의 "거리"를 이용해서 유사도 측정

 

- 각각의 object를 feature vector로 표현 -> 두 벡터간의 유클리드 거리 계산

 

* Euclidean Distance 유클리드 거리

- 두 점 사이의 직선 거리를 계산하는 보편적인 방법

- d(A, B) = √ {(a₁-b₁)² + (a₂-b₂)² + ... + (aₙ-bₙ)²}

 

[Neighbors]

2. Nearest-Neighbor Reasoning (NN)

- Nearest-Neighbor : 가장 유사한 개체들

 

- 우수한 기업고객과 가장 유사한 기업 탐색, 온라인에서 기업의 소매 고객과 가장 유사한 고객 탐색 등  

    -> 영업인력 직접적으로 도움, 타겟 마케팅

 

- ex) 위스키 분석 

    - 며칠 전 저녁에 맛 본 "Bunnahabhain" 위스키가 마음에 들었다고 하자. 다른 single malt 위스키들 중 유사한 것을 어떻게 찾을 수 있을까?

    - 각각의 single malt 위스키들을 feature vector로 나타낸다. 그리고 저 위스키와 가장 가까운 이웃을 찾는다.

    - 이처럼 각각의 특징들을 숫자 형태로 나타낸다.

    - 그러면 이처럼 특징들을 바탕으로 다른 위스키들과의 거리를 구할 수 있다. "Glenglassaugh"가 가장 유사하다고 볼 수 있다.

 

- Nearest Neighbors for Predictive Modeling

    - 타겟 변수를 예측하고자 하는 새로운 데이터가 주어진다.

    - 훈련 데이터셋으로부터 가장 유사한 데이터들을 선택한다.

    - 그들의 타겟 값들에 기반하여 새로운 데이터의 타겟 값을 예측한다.

 

 

3. Classification Using NN

- 새로운 데이터의 클래스(label)을 어떻게 예측할 수 있을까? (이웃을 이용하여 새로운 개체 분류)

 

- k개의 가장 가까운 이웃들을 찾는다.

- 그들의 타겟 변수를 참조한다.

    예를 들어, k=3이고, 두 개의 타겟 값은 (+), 한 개의 타겟 값은 (-)이면 다수결에 의해 (+)으로 예측할 수 있다.

 

- ex) 신용카드 마켓팅 문제

    - 아래 자료에 근거하여 David가 신용카드 제안에 응답할 지 예측한다.

    - 거리가 가까운 3명의 이웃을 찾을 수 있다. (Rachael, John, Norah)

    - 그들의 타겟 값을 이용하여 다수결로 예측하면 Yes로 예측할 수 있다.

 

4. Probability Estimation Using NN

- 새로운 데이터가 클래스에 속할 확률을 어떻게 구할 수 있을까?

 

- k개의 가장 가까운 이웃을 찾는다.

- 각 클래스의 빈도 비율을 계산한다.

    예를 들어, k=3일 때 Yes가 두 명, No가 한 명이면 Yes에 속할 확률은 2/3(66.7%), No에 속할 확률은 1/3(33.3%)로 계산할 수 있다.

 

5. Regression Using NN

- 새로운 데이터의 값을 어떻게 측정할 수 있을까? 

 

- k개의 가장 가까운 이웃들을 찾는다.

- 그들의 타겟 값들의 평균(or 중간값)을 계산한다.

    예를 들어, 위의 자료에서 David의 수입을 예측하고자 한다. Rachael, John, Norah의 수입이 각각 50, 35, 40이기 때문에 평균은 42, 중간값은 40으로 예측해 볼 수 있다.

 

6. NN의 두가지 이슈

1) 몇 개의 이웃을 선택해야 하는가?

    - nearest neighbor 알고리즘은 종종 k-nn 으로 불린다.

    - k를 결정하는 데에 관한 간단한 답은 없다. *_* 

 

    - 다수결을 활용하기 위해서 홀수로 정하는 것이 좋다.

    - k가 클수록 추정치가 더욱 평준화된다. outlier의 영향을 덜 받기 때문에 나쁘지 않다.

    - k = n이면 전체 데이터셋이 예측에 활용되기 때문에

        - classification 에서는 항상 가장 많은 값의 클래스에 속할 것이고,

        - regression 에서는 타겟 값이 항상 모든 값들의 평균으로 예측될 것이며,

        - class probability estimation 에서는 항상 base rate 확률로 예측될 것이다.

 

2) 모든 이웃들을 동일하게(평등하게) 간주해야 할까?

- 몇몇의 가까운 이웃들은 다른 가까운 이웃들보다 더욱 가까울 수 있다.

 

- 다수결 예측이나 평균을 구할 때 문제가 된다.

    - 이들은 이웃이 새로운 데이터와 얼마나 가까운지는 고려하지 않는다.

    - 위의 David 예제에서 k=3 일 때에는 세개의 데이터들의 거리가 모두 15 근처로 비슷하다. 하지만 k=4 로 정하면 4번째 가까운 이웃과의 거리는 122가 되기 때문에 다른 3개의 이웃들과는 많이 차이가 난다. 이를 동일하게 취급하는 것은 문제가 있다.

 

- 이를 해결하기 위해서는 유사도에 따른 가중치를 부여하면 된다. 

    - 다수결을 이용할 때 모든 표를 1로 정하지 않고, w₁ x 1 + w₂ x 1 + w₃ x 1 + ... 의 형태로 구한다.

    - wᵢ 는 유사도에 비례하여 할당되며, 보통 Σwᵢ = 1이 되도록 설정한다.

 

    - 평균을 구할 때에도 값을 더할 때 가중치를 곱하여 더한다.

    - (w₁ v₁ + w₂ v₂ + ... wₙ vₙ) / n

    - 마찬가지로 wᵢ 는 유사도에 비례하여 할당되며, 보통 Σwᵢ = 1이 되도록 설정한다.

 

- ex) weighted voting, k = 4

    - 각 가중치를 1/distance² 으로 구한다. 제곱을 하는 이유는 이상치의 가중치를 낮추기 위해서이다.

    - 그리고 비율을 따져서 가중치들의 합이 1이 되도록 한다. 

 

    - 위와 같이 가중치를 이용하여 비율을 구할 수 있고, Yes의 값이 더욱 크기 때문에 Yes라고 예측할 수 있다.

 

7. Geometric Interpretation of NN (NN의 기하학적 해석)

- 명시적으로 경계가 형성되진 않지만, 각 점의 분류를 결정함으로써 암시적은 영역을 계산할 수 있다. 

 

- k=1 로 분류한 그래프이다. k=1인 경우 자기 자신만을 그룹으로 가지며 정확도는 100%이다. 따라서 overfitting이 된다.

 

- 그래프 관찰

    - 경계들은 불규칙적이며, 특정한 기하학적 모양을 찾아볼 수 없다.

    - 훈련 데이터셋의 개체를 둘러싼 경계는 매우 구체적이다.

    - 경계는 이상치에 매우 민감하다. 위의 그래프에서 '+' 사이에 있는 '·' 의 경우가 그렇다.

 

7. Overfitting & Complexity Control of NN 

- 1-NN 

    - 훈련 포인트 자체는 자기 자신으로 예측되며, 자기 자신이 가장 가까운 이웃으로 검색된다.

    - 그러므로 1-NN 은 overfitting이 매우 강하게 발생한다.

 

- k-NN 

    - k는 복잡도 파라미터이다. (complexity parameter)

    - 극도로 복잡하게 만드려면 k = 1로 지정할 수 있다. 

    - 다른 경우에는 k = n이 된다. 그러면 모든 모델에서 그다지 복잡하진 않을 것이다.

 

- k를 선택하는 방법은 모델에 따라 다르다.

 

- 일반적인 방법

    - 다양한 k값에 따른 중첩 교차 검증을 실시한다.

    - 테스트셋에서 가장 좋은 성능을 보여준 k를 선택한다.

    - 전체 훈련 데이터셋에 대한 k-NN 모델을 형성한다.

 

    - 선형 모델이나 트리 구조 모델에서 경계는 부드러운 곡선이나 일정한 조각의 기하학적 영역이 아니다.

 

9. NN 모델의 이슈

1) Intelligibility 명확성 (얼마나 이해하기 쉬운가)

- 단일 인스턴스가 어떻게 결정되는지 설명하는 것은 쉽다.

- 하지만, 데이터로부터 어떤 '지식'이 도출되었는지 설명하는 것은 어렵다.

    - 데이터로부터 어떤 시스템을 배웠는지, 어떤 근거로 결정을 내렸는지

- 따라서, 모델에 정당성을 부여하는 것이 중요할 땐 k-NN은 바람직하지 않다.

 

2) Computational efficiency 계산 효율

- 훈련시키는 것은 매우 빠르게 진행된다.

    - 보통 저장된 개체들만 활용하기 때문에 모델을 만드는데 큰 노력을 들일 필요가 없다.

- 하지만, 예측/분류는 많은 노력과 시간이 필요하다.

    - 데이터베이스에서 새로운 개체와 가장 가까운 이웃들을 찾아야 하기 때문이다.

- 따라서, k-NN 방법은 실시간 적용에 활용하기엔 실용적이지 않을 수 있다.

 

10. 이질적인 속성들을 다루는 기술

1) 범주형 속성을 어떻게 다룰 것인가?

- 범주형 속성을 숫자형으로 바꾼다. 

- ex) Sex: Male / Female -> 0 / 1

- 이진 변수는 바꾸기 쉽지만, 여러개의 값은 어떻게 바꿔야할까?

 

2) 값이 큰 변수들은 거리에 매우 큰 영향을 미친다.

- 따라서 변수들의 범위와 규모(축척)을 측정해야 한다.

- ex) Age : [0, 100] , Income : [0, 100,000] -> Age : [0, 1], Income : [0, 1]

 

11. 거리를 구하는 다른 함수들

11-1. Euclidean distance (L2 norm)

- 가장 많이 사용되는 거리 함수

- 직관적이고 계산하기 쉽다.

 

11-2. Manhattan distance (L1 norm)

- 격자에서 이동한 거리의 총합

- ex) d((3,4), (5,2)) = |3-5| + |4-2| = 4

 

11-3. Jaccard distance 

- 두 집합의 유사도를 측정하는 방법이다.

- 두 집합이 공통적인 요소를 많이 가질수록 거리가 감소한다.

 

11-4. Cosine distance

- 두 벡터 사이 각의 cos값을 측정하는 방법이다.

- 특히 벡터의 크기를 무시하고자 하는 경우 유용하다.

- 텍스트 분류를 통해 두 문서 사이의 유사도를 측정하고자 할 때 종종 사용된다.

 

[Clustering]

12. Clustering (군집화)

- 비슷한 개체들끼리 자연스럽게 맺어지는 그룹을 찾는 방법이다.

- 특정한 타겟 속성이 없다.

- unsupervised segmentation (비지도 분할) 이라고도 부른다.

 

- ex) 더 나은 서비스를 위해 고객 그룹화, 더 보기 좋게 진열/정리 하기 위해 상품 그룹화

 

- 그룹 내의 개체들은 비슷하며, 서로 다른 그룹의 개체들은 그다지 비슷하지 않다.

 

- 지도 모델은 알고있는 데이터의 타겟 변수 값을 기반으로 특정한 타겟 변수 값을 예측하기 위한 패턴을 발견하는 것이다.

- 비지도 모델은 데이터셋에서 타겟 변수에 초점을 맞추지 않고, 다른 종류의 정규성을 찾는 모델이다.

 

- ex) 위스키 분석 (위의 예제)

    - 이번엔 '맛'이 비슷한 위스키끼리 클러스터링을 해보려 한다.

    - 계층적 클러스터링, k-means 클러스터링을 고려해볼 수 있다.

 

 13. Hierarchical Clustering 계층적 클러스터링

- 각 개체의 고유한 클러스터에서 시작한다.

- 반복적으로 가장 가까운 클러스터끼리 합친다. 

    - 유사도나 거리함수를 이용한다.

- 이론적으로는 하나의 클러스터가 될 때까지 반복한다. 하지만 통상적으로 이정도로 많이 반복하지는 않는다.

hierarchical clustering

 

14. 클러스터 사이의 거리 (distance function = linkage function)

1) Min distance

- 각 클러스터에서 가장 가까운 점 사이의 유클리드 거리

 

2) Centroid distance  

- 클러스터의 중간(모든 데이터들의 '평균값') 사이의 유클리드 거리 

 

15. Dendrogram 계통도

- 클러스터의 계층을 명시적으로 보여주는 그림

- 계통도를 수평으로 잘라서 원하는 수의 클러스터를 구할 수 있다. 

- 이를 통해 언제 클러스터링을 멈출 지 알 수 있다.

- 아래로 갈수록 클러스터의 수가 늘어난다.

 

16. 계측적 클러스터링의 장점

- 클러스터의 수를 결정하기 전에 이미 계통도를 통해 그룹화가 된 것을 볼 수 있다.

- 원하는 수의 클러스터에서 계통도를 자를 수 있다. (클러스터링을 멈출 수 있다.)

 

17. ex) Hierarchical Clustering of Scotch Whiskeys

 

- 클러스터는 스코틀랜드의 지역과 완전히 일치하지는 않다.

- 단순히 잘 알려진 것을 구입하는 대신, 각자의 클러스터에서 선택할 수 있다.

- 혹은 다른 '가장 비슷한' 위스키를 추천하는 가이드를 만들 수도 있다.

 

18. k-Means Clustering 

- k개의 그룹을 만드는 클러스터링 알고리즘이다.

- 가장 유명한 centroid-based clustering algorithm 이다.

 

- k는 데이터에서 찾은 클러스터의 개수이다. (사용자에 의해 특정된다.)

- means는 중심을 뜻한다. 클러스터에 속한 점들의 '평균값'을 의미한다.

 

19. k-Means Algorithm

- 초기 k개의 클러스터 중심을 고른다. (보통 랜덤으로 정한다.)

- 각 점을 그로부터 가장 가까운 중심이 해당하는 클러스터에 할당한다.

- 모든 점들이 할당된 이후, k개의 클러스터의 중심을 갱신한다.

- 그리고 다시 모든 점들을 그들의 가장 가까운 클러스터에 재할당한다.

- 더 이상 점들이 클러스터를 이동하지 않고 안정될 때까지 3-4번 반복한다.

 

- 각 중심들이 클러스터의 결과이다.

- 각 점들은 각각의 클러스터에 소속되어 있다.

 

20. ex

- 90개의 점을 k=3으로 하여 클러스터링 하는 과정이다.

- 분홍색, 초록색, 파란색 선은 각각 클러스터의 중심이 이동한 경로이다.

- 경로의 끝에 까만 점이 최종 클러스터의 중심이다.

 

21. Initial k Centroids 고르기

- k-means 알고리즘을 한 번 돌리는 것은 최상의 클러스터링이 아닐 것이다.

    - 초기 중심의 위치가 클러스터링의 결과를 만들게 되기 때문이다.

 

- 해결책은 초기의 랜덤 중심부를 다르게 하여 여러번 k-means 알고리즘을 돌리는 것이다.

- 그렇게 나온 결과들 중 가장 클러스터링이 잘 된 결과를 선택한다.

- 가장 좋은 클러스터링은 클러스터의 평균 직경을 최소화하는 것이다. (각 점에서부터 중심까지의 거리의 평균)

 

22. 올바른 k 값 고르기

- 실생활에서 최적의 k 값을 고르는 방법은 알 수 없다.

- 하나의 간단한 전략은, k-means 를 여러번 돌려서 가장 클러스터링이 잘 된 k를 고르는 방법이다.

- 그것은 클러스터의 평균 직경이 작고, 클러스터의 수가 그리 많지 않은 것이다.

- 다음 그래프에서는 기울기가 완만해지는 지점인 k = 3이 가장 좋은 k이다.

 

23. ex) Clustering business news stories

- 문서들을 단어들의 집합으로 나타낸다.

- Jaccard distance 를 이용하여 두개의 문서 사이의 거리를 구한다. (1-교집합/합집합)

 

 

24. ex) Clustering wiskey

- 각 위스키의 feature vector를 나타낸다 (1, 0, 1, 1, 0, ...)

- 두 위스키 사이의 거리를 유클리드 거리로 구한다.