Ch6. Similarity, Neighbors, and Clusters
- 숙명여자대학교 소프트웨어학부 데이터사이언스개론 - 박동철 교수님
# Similarity
- data science 방법과 해결에 기반이 됨
> 유사한 것들은 공통된 특징(common characteristics)을 가짐
- 예시
> 유사한 항목을 검사(retrieving): 회사 입장에서 최근에 좋다고 생각하는 고객과 유사한 고객을 찾음
> 유사한 item끼리 묶음 = clustering : 그룹의 특징을 보기 위해 비슷한 고객끼리 묶음
> 상품 추천: 추천을 제공하기 위해 비슷한 상품이나 고객을 찾음
> 비슷한 case로부터 추론: 비슷한 case를 제공함으로써 의사나 법률인을 도움
# Similarity and Distance
- objects 사이의 유사성을 측정하는 방법 → objects 사이의 거리(distance) 사용
- 기본 방법
> 각 object의 feature vector를 나타냄
> 두 vector사이의 Euclidean distance를 계산함
# Euclidean Distance
- Euclidean Distance: 일반적인 두 점 사이의 직선 거리
- 일반적인 Euclidean distance
> A = (a1, a2,..., an), B = (b1, b2,..., bn)가 n개의 feature vector를 가진다고 함
> Euclidean distance는 아래와 같음
# Other Distance Functions
① Euclidean distance
- 가장 폭넓게 사용되는 거리 개념. 직관적이고 계산하기 쉽다는 장점을 가짐
- L2 norm이라고도 불림
② Manhattan distance
- grid에서의 거리, 대각선으로 거리를 측정하지 못함
- grid에서 탐색할 수 있는 거리의 총합을 나타냄
> green: Euclidean distance
> red, blue, yellow: Manhattan distance
- L1 norm이라고도 불림
③ Jaccard distance
- 1에서 Jaccard similarity를 뺀 것
- 두 집합 사이의 유사도를 측정
- 교집합이 클수록 distance가 감소 → 유사도가 크다
- 0 <= Jaccard distance <= 1
④ Cosine distance
- 두 벡터가 이루는 각의 cosine을 측정
- 벡터의 크기를 무시하고자 할 때 특히 유용하게 사용됨
- 두 문서의 유사도를 측정하기 위해 text classification에서 사용됨
- 0 <= cosine distance <= 2
- cosine distance는 cos의 값 자체를 찾을 수도 있지만 그 cos이 나오는 각(두 벡터가 이루는 각)을 찾을 수도 있음
# Euclidean vs. Manhattan vs. Cosine distance
# Nearest-Neighbor Reasoning
- Nearest neighbors: 가장 유사한 instance. 즉, 가장 가까운 data point
- 우리는 많은 적용에 유용한 가장 가까운 instance를 활용할 수 있음
> 가장 좋은 기업 고객과 가장 유사한 회사를 찾음
> 가장 좋은 소매(오프라인) 고객과 가장 유사한 온라인 고객을 찾음
# Example: Whiskey Analytics
- 며칠 전 저녁에 싱글 몰트 스카치를 발견했다고 가정해 보자. 나에게 있어 위스키 "Bunnaabhaain"은 특이하고 매우 좋았던 위스키이다.
Q. 많은 single malt들 중에서, 우리는 어떻게 비슷한 다른 것들을 찾을 수 있을까?
- 데이터 과학 접근 방식을 취해보자
> 질문에 답하기에 적절한 데이터는 무엇인가?
> 각각의 몰트 위스키를 어떻게 설명할까? → feature vector로 사용
> Bunnahabhain의 가장 가까운 neighbor를 찾음
- 어떻게 단일 amlt scotch whiskey들을 feature vector들로 나타낼 수 있을까?
> Scotch 위스키의 맛에 대한 분석 책자를 활용하여 아래와 같은 숫자적인 특징들을 만들어 냄
> 다음과 같이 숫자적인 feature들을 가지고 모든 위스키의 feature vector들을 나타낼 수 있음
> feature vector들을 이용하여 Bunnahabin과 가장 가까운 다섯 개의 Scotches를 찾을 수 있었음
# Nearest Neighbors for Predictive Modeling
- 가장 가까운 neighbor에 대한 idea를 predictive modeling에 사용할 수 있음
- 일반적인 절차
> 우리가 예측하고자 하는 새로운 target 변수의 새로운 data가 주어짐
> 우리는 training data set으로부터 가장 유사한 data 몇 개를 고름
> 그 target value에 기반하여 새로운 data의 target value를 예측함
→ 다수결의 원칙을 따를지 평균적으로 정할지도 고민해야 함
# Issues with Nearest-Neighbor Methods
- Intelligibility (명료성)
> 어떻게 단일 instance를 결정했는지 묘사하는 것은 쉬움
→ 그들의 기여(contribution)에 따라 neighbor들의 집합이 의사 결정하는 것을 보여줌으로써 묘사 가능
= 단순히 가까운 이웃 몇 개를 골라 다수결의 원칙을 쓰던 평균을 내는 과정 자체를 보이는 것은 쉬움
> 어떤 지식이 data로부터 mine 되었는지를 설명하는 것은 어려움.
즉, 쉽게 말해 "왜 이 방법을 써?"라고 질문하면 할 말이 없는 것
→ 우리의 system이 그 data로부터 배우는 것은 무엇인지? 무엇에 기반해서 그런 결정을 만들 것인지?
→ 따라서 만약 모델의 명료성(intelligibility)과 정당성(justification)이 중요하면 k-NN방식은 사용 X
- 계산 효율
> training이 매우 빠름
→ 일반적으로 instance를 저장하는 것만을 포함하기 때문
→ model을 확장하는 데 있어 노력을 더 필요로 하지 않음 / 딱히 하는 게 없음
> prediction/classification이 매우 비쌈
→ database로부터 새로운 instance의 가장 가까운 neighbor들을 찾아야만 하기 때문
> 따라서, k-NN 방식은 아마 실제 적용에 있어서 비실용적일 수 있음
# Classification Using NN
- 우리는 어떻게 새로운 data의 class(label)을 예측할 수 있을까?
> neighbor들은 어떻게 새로운 instance가 분류되는 데에 사용될까?
- 일반적인 절차
> k개의 가까운 neighbor들을 계산 아래 그림에서는 k=3 임
> neighbor들의 target value를 구함 아래 그림에서는 +가 2개, • 가 1개임
→ 다수결의 원칙에 의해서 새로운 instance를 +라고 분류
빨간 동그라미는 새로운 instance가 분류되는 곳임
# Ex) Credit Card Marketing Problem
- Problem: David가 신용카드 제안에 응답할지 안 할지를 아래 data에 기반하여 예측해보자
- Solution
> 3명의 가장 가까운 neighbor들을 찾음 → Rachael, John, Norah
> 다수결의 원칙에 따라 Yes라고 예측 / 위의 3명의 응답이 각각 No, Yes, Yes 임
# Probability Estimation Using NN
- 새로운 data의 분류 가능성은 어떻게 예측할 수 있을까?
- 일반적인 절차
> K개의 가까운 neighbor들을 계산 아래 그림에서는 k=3 임
> 각 class의 빈도율(frequency ratio)을 계산
+ :2, • : 1 → + : 2/3 (66.7%), • : 1/3 (33.3%)
# Regression Using NN
- 새로운 data의 값을 어떻게 측정할 수 있을까?
- 일반적인 절차
> k개의 가장 가까운 neighbor들을 계산 아래 예시에서 k=3 임
> neighbor들의 target 값의 평균을 계산
(35+50+40)/3 = 약 42 (평균)
40(중간값)
# Two Issues Of Using NN
① 얼마나 많은 neighbor들을 사용해야 하는가?
- Nearest neighbor 알고리즘은 k-NN을 참조함
> k는 neighbor의 수를 나타냄 ex. 3-NN
> 안타깝게도 k를 결정할 수 있는 간단한 답이 없음
- 일반 관측치
> 홀수는 다수결에서 동률을 깨는 데 유용 ex. k가 6일 때 3:3이 되면 어느 하나를 선택하기 힘듦
> k가 클수록 neighbor들 간에 추정치가 더 smooth 해짐
> k = n인 경우 모든 예측에 전체 dataset이 사용됨
• classification (분류): 예측은 항상 전체 dataset에서 가장 중요한 class임
• regression (회귀 분석): 예측은 항상 모든 목푯 값의 평균임
• class probability estimation (클래스 확률 추정): 예측은 항상 base rate 확률임
② 거리가 다른 neighbor들을 동등하게 대해야 하는가?
- 다수결의 원칙과 평균에서의 문제
> 각 neighbor들이 instacne와 얼마나 가까운지(거리 자체)는 무시함 → 뭐가 더 가까운지 (순위)만 중요
> 만약 아래와 같이 k=4라고 했을 때, 다음과 같은 결과가 나옴 (Yes, No, Yes, No)
- 2번째 이슈에 대한 해결 방법
> weighted voting or weighted average
> 유사성에 따라 각 neighbor의 기여도를 확장하는 것
- weighted voting
> weight는 각각의 유사도에 따라 비율적으로 할당됨
> 많은 경우에서, weight를 모두 더하면 1이 됨 w0 + w1 + w2 + w3... + wn = 1
- weighted average
> weight는 각각의 유사도에 따라 비율적으로 할당됨
> w0 + w1 + w2 + w 3 ... + wn = 1
③ Example (weighted voting, k=4)
> wieght를 할당할 때 1/distance² 를 사용 → Similarity weight / 거리가 클수록 weight가 작음
> weight의 합이 1과 같아지게 함 → contribution (기여도)
> Prediction
Yes: 0.336(John) + 0.312(Norah) = 0.648 (약 65%) → Yes라고 예측
No: 0.344(Rachel) + 0.005(Jefferson) = 0.349 (약 35%)
→ Jefferson의 거리가 크기 때문에 wegiht가 매우 작은 것을 확인 가능
# Geometric Interpretation of NN
- 명시적인 경계가 만들어지지 않지만, 각 point의 분류를 결정함으로써 암시적인 영역을 계산할 수 있음
- ex) boundaries created by a 1-NN classifier
> 1-NN은 자기 자신을 의미하므로 규칙이 없음
> 위의 예시는 overfitting이 일어남
> 경계가 불규칙하고 알아볼 수 있는 기하학적 모양이 아님 ex. 포물선, 직선...
> training instance 주변 경계가 매우 구체적 → 극단적이게 boundary 형성
> 경계가 특이점에 매우 예민함 → "negative island"(그림에서의 노란 원)
# Overfitting & Complexity Control of NN
① 1-NN
- training point가 주어지면, training point 자기 자신이 가장 가까운 neighbor로 검색되고, 자신을 예측하는 데 사용됨
- 1-NN은 매우 강함 (training data 그 자체를 기억하는 것)
> 1-NN의 distance는 0이므로 overfit이 일어날 가능성 ↑
> complexity 증가
> k=1인 경우
② k-NN
- K는 complexity parameter
> 극단적인 complex mode을 얻음
- 다른 극단적인 예시는 k=n 일 때임 / 이 경우에는 complexity ↓
> 우리는 모델의 복잡성을 허용하지 않음
- k를 선택하는 일반적인 방법
> 다양한 다른 k 값에 대해 nested cross-validation 시행
→ k가 높거나 낮다고 해서 나쁜 것은 없음. 모델에 따라 가장 알맞은 k값이 달라짐
> test set에 대해 최고의 성능을 주는 k를 선택
> 전체 training data로부터 k-NN 모델을 만듦
# Ex) 1-NN Classifier vs. 30-NN Classifier
- 1-NN classifier
> training examples에 대한 boundaries가 매우 구체적임
- 30-NN classifier
> boundaries가 훨씬 덜 들쭉날쭉 함 → smooth out, less jagged
- K-NN에서 k에 따라 규칙적으로 classification boundary가 형성되는 것은 아님
- linear model이나 tree-structed model에서 두 경우 모두 경계가 부드러운 곡선과 규칙적으로
기하학적인 영역이지 않음
# Some Technical Details : Heterogeneous Attributes
- Issue 1: categorical attribute를 어떻게 다루는가?
> categorical attribute를 숫자로 인코딩함
ex) Sex: Male/Female → Sex: 0/1 (이진 값은 인코딩하기 쉬움)
> categorical 속성에 대한 값이 여러 개인 경우 어떻게 해야 하는가?
- Issue 2: 값이 큰 변수는 거리에 큰 영향을 미침
> 변수 범위를 측정하고 그에 따라 값을 척도화함
ex) 나이에서의 10만큼의 차이와 돈의 금액에서의 10만큼의 차이를 동일시하기 어렵기 때문
Age: [0, 100], Income: [0, 100,000] → Age: [0, 1], Income: [0, 1]
즉 100과 100,000을 똑같이 1로 취급하는 것은 문제가 있음
# Clustering
- 유사한 objects의 자연스러운 group 찾기
> 어느 target attribute도 지정하지 않음
> unsupervised segmentation이라고도 함
- 적용 사례 → 같은 그룹이면 유사도가 높을 것이라고 기대함
> 더 나은 서비스를 위해 다양한 고객 group을 찾음
> 더 나은 재고조사를 위해 유사한 제품 group을 찾음
- Basic idea: 다음과 같은 objects group을 찾음
> group 내에 object는 유사함
> 다른 group 안에 있는 objects는 유사하지 않음
- Supervised modeling vs. unsupervised modeling
> supervised: target 변수의 값을 알고 있는 데이터를 기반으로 지정된 target 변수의 값을
예측하는 패턴을 검색
> unsupervised: 데이터 집합에서 다른 종류의 규칙성을 찾음. target 변수에 초점을 맞추지 X
# Example : Whiskey Analytics Revisited
- 유사한 위스키의 cluster를 찾기 원함
> 취향에 따라 자연스러운 group을 이해
> 각 taste group에서 적어도 한 명 또는 두 명씩 구성원을 선택
- 두 가지 주요 clustering
> Hierarchical clustering
> k-mean clustering
# Hierarchical Clustering
- bottom-up 방식
- 일반적인 절차
> 각 instance를 자체 cluster로 시작
> 가장 유사한 cluster(distance ↓/nearest) 반복적으로 합쳐나감
> 이론적으로는 단일 cluster가 남을 때 멈춰야 하지만 실제 business에서는 cluster가 하나만 남는 건 X
# Distance Function Between Clusters
- 가장 유사한 clusters를 찾기 위해 clusters(data point를 포함) 사이에 distance function이 필요
> linkage function 이라고도 불림
- 전형적인 distance functions
> Min distance: 각 점에서 가장 가까운 점 사이의 Euclidean distance.
즉, 각각의 data point끼리의 가장 가까운 거리
> Centroid distance: clusters의 centroids 사이의 Euclidean distance
→ Centroid: data point끼리의 평균
# Dendrogram
- clusters의 계층을 명시적으로 표시해줌
- dendrogram을 수평선으로 clip 하면 원하는 수의 cluster를 얻을 수 있고, 라인 위의 cluster는 무시함
> 선이 아래로 이동하면 군집 수가 증가
# Advantage of Hierarchical Clustering
- 데이터 분석을 통해 추출할 cluster 수를 결정하기 전 grouping 된 결과를 확인할 수 있음
> 데이터 유사성의 landscape임
- dendrogram은 원하는 수의 cluster를 제공하기 위해 임의의 지점에서 자를 수 있음
# Hierarchical Clustering of Scotch Whiskeys
- Dendrogram은 50개 위스키의 계층적 clustering을 보여줌
> Bunnahabhain과 그것의 neighbor들을 보여주는 작은 발췌문( small excerpt)
> 이 cluster는 지역과 깔끔하게 일치하지 않음
> 가장 인지도 높은 scotch를 선택하는 것 대신, 다른 cluster로부터 단일 malts를 stock으로 선택할 수 있음
> "가장 유사한" 다른 위스키를 추천하는 가이드를 만들 수 있음
# k-Means Clustering
- 가장 널리 사용되는 centroid 기반 clustering 알고리즘
- "k-means"
> k: 데이터에서 찾을 cluster의 수 (사용자에 의해 정해짐)
> means: 중심점 (cluster안에 point들의 평균)
# k-Means Algorithm
- outline
① 초기 cluster centers가 될 k를 선택 (일반적으로 랜덤)
② 각 point에 대하여 가장 가까운 center이 있는 cluster에 할당
③ 모든 point를 할당한 후, k cluster의 centroid를 업데이트함
④ 모든 점을 가장 가까운 cluster에 다시 할당함
⑤ convergence 상태가 될 때까지 ③,④를 반복함
→ convergence: centroid도 더 이상 움직이지 않고 data point도 더 이상 움직이지 않는 상태
- ouput
> 결과 cluster의 중심
> 각 cluster에 속한 point
# (EX) k-Means Algorithm
> convergence가 될 때까지 update와 assign 반복
# (EX) A Little More Realistic Example
- k를 3개로 하는 90개의 data point에 대한 k-means
> 오른쪽 그래프의 3개 선은 16번의 반복 동안 centroid가 움직인 경로를 나타냄
# Picking Initial k Centroid
- k-mean의 한 번의 실행은 clustering에서 최고의 결과를 내지 못할 수 있음
> clustering의 결과는 초기 centroid 위치에 따라 달라지기 때문
- solution
> 다른 초기 랜덤 centroid를 가지고 k-means를 여러 번 실행함
→ 여러 번 시행할수록 복잡도가 커지고 계산량이 많아짐
> 결과 사이에서 최적의 clustering을 선택
→ best clustering: clusters의 평균 지름을 최소화함
# Picking the Right Value of k
- 실제로 우리는 k의 최적의 값을 모름
- simple strategy
> k-means를 여러 번 실행하고 best clustering을 발생시키는 k를 선택
> ex) clustering의 평균 직경이 작고 clustering수가 많지 않은 cluster
> k값이 증가할수록 overfitting의 가능성 ↑
> 보통 k는 표에서 팍 줄다가 완만해지는 시점으로 선택됨
# EX) Clustering Business News Stories
- 각 문서를 단어의 집합으로 나타냄 ex) {"girls", "apple",,,}
- Jaccard distance를 이용하여 두 문서 사이의 거리를 측정
> 문장이 유사하다고 해서 그 의미도 유사한 것은 아님
# EX) Clustering whiskey
- 각각의 위스키를 (1, 0, 1, 1, 0)과 같이 feature vector로 나타냄
- Euclidean distance를 이용해 두 위스키간의 거리를 측정
# Summary
- The fundamental concept of similarity between data items occurs throughout data science
> Finding dimilar entities, predictive modeling, clustering entities
- Distance function
> Used to measure the similarity between two entities
> Euclidean, Manhattan, Jaccard, Cosine distance
- k-NN methods
> Retrieve a set of k nearest neighbors and use them to make a prediction
- Clustering
> Group similar objects into the same group (hierarchical, k-means)
'Study > Data Science' 카테고리의 다른 글
| [DataScience] Ch8. Visualizing Model Performance (0) | 2021.08.24 |
|---|---|
| [DataScience] Ch7. Decision Analytic Thinking 1: What is a Good Model? (0) | 2021.08.24 |
| [DataScience] Ch5. Overfitting and Its Avoidance (0) | 2021.08.24 |
| [DataScience] Ch4. Fitting a Model to Data (0) | 2021.08.23 |
| [DataScience] Ch.3 Introduction to Predictive Modeling: From Correlation to Supervised Segmentation (0) | 2021.08.23 |
