08. Clustering

클러스터링은 주어진 항목들을 성격이 비슷한 것들끼리 모으는 작업을 말한다.
클러스터링과 분류가 다른 점은 분류에서는 나눌 카테고리가 미리 정해진 반면 클러스터링에서는 나눌 카테고리가 미리 정해져 있지 않다는 것이다.
기계학습은 크게 지도학습과 비지도 학습으로 나눌 수 있다.
지도학습은 정답을 알고 학습하는 것을 말하고(분류)
비지도 학습은 정답이 없이 분석하는 경우를 말한다.(클러스터링)

8.1 클러스터링 개념
나누어야 할 집단의 개수나 그 경계치가 미리 정해져 있지 않지만 전체 그룹을 적절한 수의 그룹으로 나누는 작업을 클러스터링이라고 한다.
전체 고객을 성향이 비슷한 그룹으로 나눌 때(이를 세그멘테이션 이라고 한다.) 클러스터링을 먼저 수행한다.

클러스터 수

• 클러스터링에는 나눌 집단의 수(이를 k라고 하자.)를 미리 정해주는 경우와 미리 정해주지 않고 적절한 집단의 수를 찾아내는 방법이 있다.
• 클러스터링에서는 적잘한 k값을 먼저 찾아내는 단계가 필요하다.
  이하 적절한 k값 찾는 방법 책 참조.
• 항목 간의 거리를 2차원 공간상에 표현한 그림을 dendrogram이라고 한다.

클러스터링 활용

• 클러스터링에서는 주어진 항목 샘픔들을 가장 자연스럽게 나누어야 한다.
  여기서 자연스러운 그루핑의 조건이란, 같은 그룹 내의 항목들은 서로 속성이 비슷해야 하고 다른 그룹에 속한 항목들 간에는 가능한 속성이 서로 많이 달라야 한다.
• 클러스터링을 활용하는 예는 구매 패턴이 비슷한 사람들을 구분하여 마케팅 대상을 나누는 것, 즉 고객 세분화를 할 때 사용한다.
  고객을 구매 유형 기준으로 나눈다고 할 때 어떤 유형이 많을지 미리 알지 못하므로 클러스터링이 필요한 것이다.

8.2 유사도
클러스터링을 하려면 항목들이 서로 얼마나 유사한지를 측정해야 한다.
유사도는 클러스터링에서만 필요한 것이 아니라 분류나 예측에서도 필요하다.
이렇게 항목 간의 유사한 정도를 수치로 나타낸 것을 유사도(similarity)라고 한다.

유사도 예

• 통계적인 관점으로는 키, 몸무게, 나이 각각의 표준 편차를 구해서 표준 편차를 기준으로 볼 때 상대적으로 이 값들이 얼마나 차이가 나는지를 비교하는 방법을 널리 사용한다.(z 변환)
• 데이터 분석 결과가 가장 많이 달라질 수 있는 부분이 바로 유사도를 정의하는 단계이고 여기에는 많은 분석 경험과 문제 도메인에 대한 이해가 필요하다.
• 또한 분석을 반복 수행하면서 유사도를 다르게 정의하는 것도 필요하다.
• 유사도(s)는 보통 0 =< s =< 1 사이의 값을 갖도록 정의한다.
• 유사도가 1에 가까울수록 서로 가까운 것이고 0에 가까울수록 유사성이 없다고 정의한다.
• 유사도의 상대 개념으로 거리(distance)를 사용한다.
• d = 1 - s

자카드 유사도

• 데이터 분석에서 널리 사용되는 유사도로 Jaccard 유사도가 있다.
• 자카드 유사도는 어떤 두 항목이 겹치는 부분의 절대량만을 보지 않고, 두 항목의 공통 부분이 얼마나 많은지를 고려하여 이에 대한 상대적인 값을 유사도로 사용하는 것이다.

해밍 거리
두 개의 벡터에 동일한 패턴이 얼마나 겹치는지를 비교할 때 해밍 거리(Hamming distance)를 자주 사용한다.
ex) DNA 시퀀스에서 일정 구간 내에 동일한 패턴이 얼마나 있는지를 비교할 때 사용된다.

• in 책의 예시) 각 코드는 총 7개의 변수가 있는데 코드 A와 코드 B는 같은 변수가 겹치는 곳이 3개이므로(a,c,d) 해밍 유사도는 3/7이고 거리는 4/7이다.
• 코드 B와 코드 C는 겹치는 변수가 2개이므로(f,r) 해밍 유사도는 2/7이고 거리는 5/7이다.

공간 거리
전통적으로 기하학에서 널리 사용하는 거리 개념으로 공간(space) 상의 거리가 있다.
공간상의 거리는 기하학자 유클리드의 이름을 따서 유클리디언(Euclidian) 거리 라고도 한다.

• 공간은 2차원이므로 비교할 특성이 2개만 있는 항목간의 거리를 구하면 된다.
• 동시에 특성이 3개 이상인 경우돋 다차원 공간상의 가상점으로 보고 유클리디안 거리 공식을 확장해서 사용할 수 있다.
  ex) in 책
• 그런데 유클리디안 거리를 사용할 때에는 차원(dimension)이 다른 것, 그리고 단위가 다른 것을 고려하지 않으면 의미 없는 결과를 얻게 된다.
• 따라서 이를 고려해서 절대값을 사용하는 대신 모든 변수를 각각의 표준 편차로 나누어(정규화하여) 비교하는 방법을 쓴다.
• 유사도를 구하려면 먼저 문제가 요구한느 의미 있는 정확한 유사도에 대한 정의가 필요하다.
• 항목 간의 유사도는 어디에 관심을 두는가에 따라 다르게 정의할 수 있다.
• 유사도를 정의하는 것은 데이터 사이언스에서 가장 어려운 부분이다.
  유사도를 다르게 정의하면 분석 결과는 전혀 다르게 나올 것이다.
  만약 비만도를 따져야 한다면 키와 몸무게를 각각 고려해서는 안 되고 키에 비해 몸무게가 얼마인지를 나타내는 새로운 변수를 정의해서 유사도를 구해야 할 것이다.

코사인 유사도
앞에서 설명한 공간상(유클리디안) 거리는 가상공간 상에 두 점의 절대적인 거리를 이용했다.
이러한 '거리' 대신 공간상의 두 점이 만드는 각도가 적을수록 서로 가깝다고 볼 수도 있을 것이다.
즉, 공간상의 두 점의 물리적인 거리가 멀더라도 두 점이 가리키는 방향이 같으면 서로 비슷하다고 보는 것이다.
즉, 두 점 사이의 각도가 작으면 다른 두 점사이의 각도가 큰 경우보다 더 가깝다고 정의하는 게 코사인(cosine) 유사도다.

• 유사도로 두 점 사이의 각도의 cos()을 택한 이유는 다음과 같다.
  두 점이 정확히 같은 방향을 가리키면 둘 사이의 각도가 0이 되고 cos(0) = 1 이므로 유사도가 1이 되어 우리가 원하는 유사도로 사용하기가 적합하다.
  또한 두 점이 서로 직각 방향이면 둘 사이의 각도는 90도이고 cos(90) = 0 이 된다.
• 한편 두 점이 공간상에 서로 반대 방향을 이루고 있으면 두 점 사이으이 각도는 180도이고, 이 때 cos(180) = -1 이다.
  코사인 유사도는 0~1 사이의 값을 갖는 것이 아니라 -1 ~ 1 사이의 값을 가지게 된다는 특징이 있다.
  코사인 유사도는 1이면 같은 방향, -1이면 정반대의 방향을 가리킨다.
  0이면 두 item의 방향이 직각이므로 서로 아무런 동질성이 없는, 독립적인 성격을 갖는다고 본다.
  ex) 코사인 유사도는 텍스트 분석을 할 때 하나의 글에서 같은 단어가 얼마나 같이 자주 등장하는지 또는 반대 성향의 단어가 얼마나 자주 등장하는지를 가지고 유사도를 측정할 때 사용한다.

8.3 k-means 알고리즘
클러스터링을 수행하는데 k-means 알고리즘이 널리 사용된다.
동작 원리는 매우 간단하다.
전체 항목을 k개의 그룹으로 나누되 각 그룹 내에 들어 있는 항목들 간의 거리는 가능한 작고, 서로 다른 그룹에 들어 있는 항목들 간의 거리는 가능한 멀게 나눈다는 것이 기본 개념이다.

동작 원리
k-means 알고리즘의 동작 순서는 다음과 같다.

• 먼저 나눌 클러스터의 개수인 k값을 정해주어야 한다.
  다음에 특성 변수 공간상에 임의의 k개의 초기 지점을 정한다.
  이를 클러스터 중점(cluster center)라고 하는데, 클러스터 중점은 공간상 임의의 위치 좌표로 설정할 수도 있고, 주어진 데이터 항목 중에 임의의 k개의 샘플을 클러스터 중점으로 선택해도 된다.
• 초기 클러스터 중점을 선택한 다음에는 전체 항목들이 각각 어느 중점에 더 가까운지를 보고 클러스터를 새로 구성한다.
  즉, 각 중점을 중심으로 가까이 있는 항목들로 구성된 새로운 클러스터를 만드는 것이다.
• 다음에는 현재 각 클러스터에 포함된 항목의 위치들의 평균을 구해서 이를 새로운 클러스터 중점으로 변경한다.
  즉 클러스터의 무게 중심을 현재 구성항목들로부터 새로 구하는 것이다.
  이때 새로 정해진 클러스터 중심을 센트로이드(centroid)라고 한다.
  -이렇게 클러스터의 무게 중심을 바꾸는 작업을 계속 진행하여 더 이상 클러스터의 모양이 바뀌지 않을 때까지 수행하면 clustering이 완료된다.

적절한 k값 선택
클러스터링에서 가장 어려운 부분이 적절한 클러스터 수인 k값을 정하는 것이다.
이를 위해 데이터의 특성을 미리 알고 있어야 한다.
k값은 최소치인 1부터 최대치인 N을 가질 수 있다.
적절한 클러스트의 수를 구할 때 각 클러스터에 속한 샘플들의 동질성(homogeniety)를 봐야한다.
k=1이면 동질성 최악, k=N이면 동질성 최고.
여기서 클러스터 수 k가 너무 작으면 여러 가지 성격을 가진 항목들이 너무 섞여 있는 현상이 발생하고, k를 너무 크게 하면 항목들을 세밀하게 구분할 수 있으나 그룹 수가 너무 많아져서 클러스터링을 하는 의미가 없어진다.
따라서 적절한 클러스터 수를 택해야 하는데, 선택의 한 방법으로 동질성이 충분히 만족되는 적절히 큰 k값을 택해야 한다.
이 때 그림 8.9의(책에서) 변곡점 위치(elbow point)를 택하는 방법이 있다.

8.4 연관분석
연관분석이란 둘 또는 둘 이상의 사건이 얼마나 연관성 있게 발생하는지를 분석하는 것을 말한다.
연관분석의 예는 슈퍼마켓에서 동시에 어떤 물건들이 같이 자주 팔리는지를 파악하는 것이다.
연관분석은 어떤 두 사건의 발생하는 패턴을 분석하는 것이므로 패턴분석이라고도 한다.

연관분석은 대량의 데이터 속에 묻혀있던 사실 중에 의미 있는 패턴을 찾아내는 것이다.
ex) 맥주를 사는 사람이 혹시 치즈도 많이 사는지 궁금하다면 이 둘의 연관성을 분석해 보아야 한다.

{맥주} -> {치즈}

연관분석은 예측과는 성격이 다르다.
즉, 인과관계를 나타내주지는 않는다.

{맥주, 치즈}
위의 {맥주, 치즈}와 같은 항목들의 집합을 itemset이라 한다.
연관분석은 비지도 학습에 해당하므로, 미리 정답이 주어진 것이 아니므로 모델을 만들거나 훈련하는 과정이 필요 없다.
데이터들을 보고 어떤 연관성이 들어 있는지를 알아내면 된다.

기본 개념
연관관계를 나타내는 것을 rule이라고 한다.
연관분석을 통해서 관심을 끌만한, 의미 있는 rule을 찾아내야 한다.
그러나 항목들의 모든 가능한 조합에 관심을 가지고 분석하는 것은 어렵고 어느 정도 발생 빈도가 높은 rule을 대상으로 분석해야 한다.
이렇게 의미를 갖는 룰을 정의하기 위해 지지도(support)와 신뢰도(confidence) 두 가지 수치를 사용한다.

지지도
지지도는 전체 트랜잭션 수에서 특정 아이템셋이 발생한 확률을 나타낸다.
관심의 대상인 전체 트랜잭션 수가 N이라고 하자.
이 중에 특정 itemset X의 발생 횟수를 count(X)라고 표현하면 이 itemset X의 지지도는 다음과 같이 정의한다.

support(X) = count(X) / N

이렇게 rule로 나타낼 때 주의할 것은 이 rule이 인과관계를 나타내는 것은 아니라는 것이다.
단지 두 항목이 같은 장바구니에 담겨있을 뿐이지 어느 항목을 먼저 구매했는지는 알 수 없다.
즉, 연관관계가 인과관계를 나타내는 것은 아니다.
참고로 상관관계도 인과관계를 나타내는 것은 아니다.

신뢰도
신뢰도란 한 item의 발생이 다른 item의 발생을 어마나 믿을만하게 설명해 주는지를 나타낸다.

confidence(X -> Y) = support(X, Y) / support(X)

마치 조건부 확률을 구하는 것과 개념이 유사하다.

• 지지도와 신뢰도 값이 큰 경우를 strong rule이라고 한다.

알고리즘
천문학적인 연관관계 경우의 수를 다 확인해보는 것은 현실적으로 불가능하므로 관련이 있을 것으로 추정되는 itemset을 미리 찾아서 계산량을 줄여야 한다.
frequent itemset을 찾는 알고리즘으로 apriori 알고리즘이 널리 사용된다.
이 알고리즘의 기본 원리는 frequent itemset은 그 부분집합도 당연히 자주 발생한다는 것이다.

{A, B} itemset이 자주 발생하려면 {A}와 {B}가 각각 자주 발생해야 한다.

이 알고리즘의 장점은 대량의 데이터에 대해서도 연관분석이 가능하며, 기존의 경험에 의존할 땐 예상하지 못했던 연관성을 찾아내는데도 탁원하다는 것이다.