Midterm Preparation : Data Mining

목차

1. WSS, BSS
2. Minkowski
3. Jaccard coefficient
4. Bisecting K means
5. DBSCAN

BSS, WSS, SSE란?

SSE : WSS
WSS : Within sum of squares 군집 내에서의 응집력(Cohesion)을 의미한다.
BSS : Between-group sum of squares 군집이 다른 군집과 얼마나 다른지, 잘 분리되어 있는지를 의미한다.
SSE : Total sum of squared Errors
K 는 cluester들의 수를 의미한다. 
WSS와 BSS를 합하면 클러스터 수와 상관없이 일정하다.

 

Minkowski Distance란?

유클리드 거리와 맨해튼 거리를 일반화 한것이다. 
p = 1 : 맨허튼 거리와 동일, L1 Norm
p = 2 : 유클리드 거리와 동일, L2 Norm
p = 무한 : 체비쇼프 거리와 동일, L max Norm

https://goofcode.github.io/similarity-measure#:~:text=Minkowski%20Distance,%EC%8A%A4%ED%82%A4%20%EA%B1%B0%EB%A6%AC%EB%8A%94%20%EB%8B%A4%EC%9D%8C%EA%B3%BC%20%EA%B0%99%EC%8A%B5%EB%8B%88%EB%8B%A4.&text=p%20%3D%202%EC%9D%BC%20%EA%B2%BD%EC%9A%B0%20%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C,%ED%95%98%EA%B3%A0%2C%20L2%20norm%EC%9D%B4%EB%9D%BC%EA%B3%A0%EB%8F%84%20%ED%95%A9%EB%8B%88%EB%8B%A4.

#2. Minkowski Distance
from scipy.spatial import distance
from scipy.spatial import minkowski_distance

point_1 = (6, 5, 4)
point_2 = (3, 2, 1)
point_1, point_2

minkowski_distance = distance.minkowski(point_1, point_2, p=3)
print("Minkowski Distance between", point_1, "and", point_2, "is: ", minkowski_distance)

 

Jaccard coefficient란?

두 집합의 교집합을 합집합으로 나눈 값을 이용하여 데이터 클러스터링시에, 유사도를 측정한다.
F01은 앞의 집합의 값이 0, 뒷 자리의 값이 1일때를 의미한다. 마찬가지로 F10은 앞이 1 뒤가 0, F00은 모두 0일때, F11은 모두 1일때를 나타낸다.

계산 식 : 모두 1인 값을, 01, 10, 11 세 값을 더한 것으로 나눠준다. 00 인경우를 제거하여 유사도를 계산하게 된다.

 

Jaccard Coefficient Example

p	1	0	0	0	0	0	0	0	0	0
q	0	0	0	0	0	0	1	0	0	1

Jaccard Coefficient = 0 / (2 + 1 + 0) = 0

Bisecting K means

K-means Clustering : 랜덤하게 k개의 좌표들을 뽑아 Centroid(중심점)으로 둔다. 
각 데이터들을 Centroid와 가까운 클러스터에 모은다.
소수의 데이터만 상대적으로 남았을때까지 반복하고 종료, 수렴보장이 된다.

Bisecting K means 클러스터링 알고리즘은, K-means 알고리즘을 진행하는 것은 똑같다.
다른점은 Bisection 부분에서 가장 작은 SSE를 가지는 2개의 클러스터를 list에 추가하고,
클러스터 리스트가 K개가 넘을때까지 반복하고 종료한다.