강은 두 가지를 미리 정해야 했습니다. 군집이 몇 개인지와 덩어리가 공 모양이라는 것입니다. 그 대가로 초승달 두 개에서 순도 에 그쳤습니다.
이 강의는 두 가지 방법을 봅니다. 하나는 개수를 안 정하고 모든 개수를 한꺼번에 만들고, 다른 하나는 모양 대신 밀도로 덩어리를 정의합니다.
공짜가 없습니다. 개수를 안 정하는 대신 연결 방식을 정해야 하고, 모양을 안 정하는 대신 반경과 최소 이웃 수를 정해야 합니다.
문제. 계층적 군집의 골격을 세웁니다.
() 평균과 무엇이 다른지 정리하세요.
() 작은 자료에서 합치는 과정을 보세요.
() 연결 방식이 무엇을 바꾸는지 정리하세요.
생각의 실마리. 군집이 몇 개인지 모르겠으면 모든 개수를 다 만들어 두면 됩니다. 가장 가까운 둘을 계속 합치면 개에서 개까지의 모든 단계가 한 번에 나옵니다.
풀이. () 정리합니다.
| 무엇 | 평균 | 계층적 군집 |
|---|---|---|
| 개수를 언제 정하나 | 먼저 | 나중에 잘라서 |
| 결과가 무엇인가 | 배정 하나 | 나무 하나 |
| 시작점에 딸리나 | 예 | 아니오 |
| 계산량 | 에 비례 | 제곱에서 세제곱 |
| 덩어리 모양 | 공 모양만 | 연결 방식이 정함 |
셋째 줄이 큰 이점입니다. 강 문제 에서 무작위 시작이 최악 까지 갔는데, 여기서는 답이 하나로 정해집니다.
() 작은 자료에서 합치는 과정을 봅니다. 점 개를 세 덩어리로 놓았습니다.
| 합치는 순서 | 합친 높이 | 합친 뒤 크기 | 남은 덩어리 수 |
|---|---|---|---|
다섯째까지는 높이가 이하인데 여섯째에서 로 열두 배 뜁니다.
와 사이 어느 높이에서 잘라도 세 덩어리가 나옵니다. 높이의 큰 도약이 자연스러운 군집 개수를 알려 줍니다.
() 연결 방식이 무엇을 바꾸는지 정리합니다.
| 연결 방식 | 두 덩어리 거리 | 어떤 모양을 찾나 |
|---|---|---|
| 최단 | 가장 가까운 두 점 | 길게 이어진 것 |
| 최장 | 가장 먼 두 점 | 빽빽한 공 모양 |
| 평균 | 모든 쌍의 평균 | 가운데쯤 |
| 워드 | 합쳤을 때 제곱합 증가 | 평균과 비슷 |
최단 연결은 한 점만 가까우면 붙습니다. 사슬처럼 이어집니다.
최장 연결은 모든 점이 가까워야 붙습니다. 뭉친 것만 찾습니다.
워드 연결은 강의 목적함수를 그대로 씁니다. 합쳤을 때 군집 안 제곱합이 가장 적게 느는 둘을 고릅니다.
이 문제에서 배우는 것. 개수를 안 정해도 되는 대신 연결 방식을 정해야 합니다. 그리고 연결 방식이 곧 어떤 모양을 찾을지를 정하므로, 강에서 공 모양을 가정했던 자리가 여기서는 연결 방식의 선택으로 옮겨간 것입니다.
확인 1-1. 계층적 군집이 평균과 다른 점 하나를 쓰세요.
답. 개수를 미리 안 정하고 나무를 만든 뒤 잘라서 정합니다.
확인 1-2. 검산에서 다섯째와 여섯째 합침의 높이를 쓰세요.
답. 과 입니다.
확인 1-3. 워드 연결이 무엇을 최소로 하는지 쓰세요.
답. 합쳤을 때 군집 안 제곱합의 증가입니다.
문제. 네 방식을 견줍니다.
() 공 모양 자료에서 재세요.
() 길게 이어진 자료에서 재세요.
() 최단 연결의 약점을 보세요.
생각의 실마리. 연결 방식이 가정이라면, 가정이 맞는 자료와 틀린 자료에서 각각 재 봐야 합니다.
풀이. () 공 모양 덩어리 둘에서 잽니다.
| 연결 방식 | 순도 | 가장 큰 군집 크기 |
|---|---|---|
| 최단 | ||
| 최장 | ||
| 평균 | ||
| 워드 |
최장 평균 워드는 을 넘습니다. 가정이 자료에 맞습니다.
최단 연결만 으로 실패합니다. 두 덩어리가 가까워 한 점 다리로 이어졌고, 가장 큰 군집이 개라 사실상 하나로 묶어 버렸습니다.
() 초승달 두 개가 맞물린 자료에서 잽니다.
| 방법 | 순도 | 가장 큰 군집 크기 |
|---|---|---|
| 최단 연결 | ||
| 최장 연결 | ||
| 평균 연결 | ||
| 워드 연결 | ||
| 평균 |
최단 연결만 으로 완벽히 찾습니다. 이어진 것을 따라가기 때문입니다.
나머지는 강 문제 와 같은 이유로 못 찾습니다. 초승달이 볼록하지 않기 때문입니다.
문제 의 첫 표와 정확히 뒤집혔습니다. 공 모양에서 꼴찌였던 최단 연결이 여기서는 유일한 승자입니다. 연결 방식이 곧 어떤 모양을 가정하는지입니다.
() 최단 연결의 약점을 봅니다. 두 덩어리 사이에 점 개짜리 다리를 놓습니다.
| 무엇 | 다리 없을 때 순도 | 다리 있을 때 순도 |
|---|---|---|
| 최단 연결 | ||
| 워드 연결 |
다리 하나로 최단 연결이 에서 으로 무너집니다. 이것을 사슬 효과라 합니다.
워드 연결은 다리가 있어도 흔들리지 않습니다. 다리의 점 개로는 제곱합 증가를 못 이깁니다.
튼튼함과 유연함이 맞바뀝니다. 공짜가 없습니다.
이 문제에서 배우는 것. 유연한 방법일수록 작은 잡음에 약합니다. 최단 연결은 아무 모양이나 찾을 수 있는 대신, 점 몇 개가 우연히 놓인 자리에 답이 딸립니다. 강에서 나무가 불안정했던 것과 같은 종류의 맞바꿈입니다.
확인 2-1. 검산에서 공 모양 자료의 최단 연결 순도를 쓰세요.
답. 입니다.
확인 2-2. 검산에서 초승달 자료의 최단 연결과 평균 순도를 쓰세요.
답. 과 입니다.
확인 2-3. 사슬 효과가 무엇인지 쓰세요.
답. 점 몇 개가 다리를 놓으면 최단 연결이 두 덩어리를 하나로 묶는 현상입니다.
문제. 밀도 기반 군집을 세웁니다.
() 정의를 정리하세요.
() 반경을 바꿔 가며 재세요.
() 반경을 고르는 방법을 보세요.
생각의 실마리. "덩어리"를 모양으로 정의하는 대신 빽빽한 곳으로 정의할 수 있습니다. 그러면 모양을 아예 안 가정하고, 덤으로 어디에도 안 속하는 점을 남길 수 있습니다.
풀이. () 정리합니다.
| 무엇 | 정의 | 무엇이 좋은가 |
|---|---|---|
| 반경 | 안을 이웃이라 함 | 국소적으로 봄 |
| 핵심점 | 이웃이 minPts 이상 | 빽빽한 곳 |
| 경계점 | 핵심점의 이웃이지만 자기는 아님 | 가장자리 |
| 잡음점 | 둘 다 아님 | 군집에 안 넣음 |
핵심점끼리 이어지면 한 군집입니다. 개수를 안 정하고, 어디에도 안 속하는 점을 잡음으로 남깁니다.
() 초승달 자료에서 반경을 바꿔 가며 잽니다.
| 군집 수 | 잡음점 수 | 핵심점 수 | 순도 | |
|---|---|---|---|---|
이 작으면 군집이 개로 잘게 쪼개지고 잡음이 개가 됩니다. 크면 모두 한 덩어리가 됩니다.
이 나 에서 초승달 둘을 정확히 찾습니다. 평균이 이었던 문제입니다.
맨 윗줄의 순도 은 군집을 개로 쪼갠 덕이라 좋은 값이 아닙니다. 순도는 군집 수와 함께 봐야 합니다.
minPts도 바꿔 봅니다.
| minPts | 군집 수 | 잡음점 수 | 핵심점 비율 |
|---|---|---|---|
minPts를 까지 키우면 핵심점이 하나도 없어 전부 잡음이 됩니다. 대체로 차원의 두 배쯤에서 시작해 조정합니다.
() 반경을 고르는 방법을 봅니다. 각 점에서 번째 가까운 이웃까지의 거리를 정렬합니다.
| 몇 번째 점 | 번째 이웃 거리 | 앞과의 차 |
|---|---|---|
끝에서 값이 급격히 커집니다. 번째까지는 차가 인데 마지막 구간에서 입니다.
그 무릎 자리가 후보입니다. 무릎 앞은 덩어리 안의 점이고 뒤는 떨어진 점입니다.
강의 팔꿈치와 같은 종류의 눈짐작입니다. 자동으로 정해지지 않고 사람이 봐야 합니다.
이 문제에서 배우는 것. 밀도 기반 방법은 모양을 안 가정하는 대신 밀도의 눈금을 정해야 합니다. 과 minPts가 그 눈금이고, 강의 와 마찬가지로 자동으로 안 정해집니다.
확인 3-1. 핵심점의 정의를 쓰세요.
답. 반경 안의 이웃이 minPts 이상인 점입니다.
확인 3-2. 검산에서 이 와 일 때의 군집 수를 쓰세요.
답. 개와 개입니다.
확인 3-3. 검산에서 minPts가 일 때 군집 수와 잡음점 수를 쓰세요.
답. 개와 개입니다.
문제. 못 하는 것을 봅니다.
() 밀도가 다를 때를 재세요.
() 대안을 정리하세요.
() 차원이 오르면 왜 어려운지 보세요.
생각의 실마리. 이 하나입니다. 그런데 자료 안에 밀도가 다른 덩어리가 여럿 있으면, 어느 하나에 맞춘 이 다른 것에는 안 맞습니다.
풀이. () 빽빽한 덩어리와 성긴 덩어리를 나란히 두고 잽니다.
| 군집 수 | 잡음점 수 | 성긴 쪽 잡음 비율 | 순도 | |
|---|---|---|---|---|
이 이면 성긴 덩어리의 퍼센트가 잡음이 되고 순도는 입니다. 남은 점만 보면 잘 나뉜 것처럼 보입니다.
을 키우면 잡음은 줄지만 어느 자리에서 둘이 한 덩어리로 합쳐집니다. 에서 순도가 로 떨어지고 에서 이 됩니다.
잡음을 줄이는 것과 둘을 갈라 놓는 것이 서로 어긋납니다. 하나의 으로는 둘을 함께 못 합니다.
() 대안을 정리합니다.
| 방법 | 무엇을 하나 | 무엇이 남나 |
|---|---|---|
| HDBSCAN | 을 다 훑어 나무로 | 최소 크기만 정함 |
| OPTICS | 도달 거리로 순서 매김 | 그림을 봐야 함 |
| 자료를 나눠 따로 | 영역마다 다른 | 나누는 기준이 필요 |
| 강의 혼합모형 | 밀도를 모형으로 | 모양을 가정함 |
첫 줄이 요즘 표준입니다. 모든 에 대한 결과를 나무로 만들고 안정적인 가지만 남깁니다. 문제 의 계층적 군집과 문제 의 밀도 기반을 합친 셈입니다.
() 차원이 오르면 왜 어려운지 봅니다.
| 차원 | 가장 가까운 이웃 거리 | 번째 이웃 거리 | 둘의 비 |
|---|---|---|---|
차원 에서 첫 이웃과 다섯째 이웃의 거리가 배 차이인데 차원 에서는 배입니다.
그러면 밀도가 높은 곳과 낮은 곳의 구분이 사라집니다. 어느 점에서 봐도 이웃까지의 거리가 비슷하므로 핵심점과 잡음점이 안 갈립니다.
강 문제 의 거리 집중이 밀도 기반 방법을 무력하게 만듭니다.
이 문제에서 배우는 것. 밀도 기반 방법은 밀도가 고른 저차원 자료에서 강합니다. 밀도가 다르면 하나로 못 잡고, 차원이 높으면 밀도 자체가 정의되기 어렵습니다.
확인 4-1. 밀도가 다를 때 하나로 못 하는 이유를 쓰세요.
답. 잡음을 줄이려면 크게 해야 하고 둘을 가르려면 작게 해야 하기 때문입니다.
확인 4-2. 검산에서 이 과 일 때의 순도를 쓰세요.
답. 와 입니다.
확인 4-3. 검산에서 차원 와 일 때 첫 이웃과 다섯째 이웃 거리의 비를 쓰세요.
답. 과 입니다.
문제. 세 방법을 정리합니다.
() 나란히 놓고 견주세요.
() 같은 자료를 세 방법으로 나눠 보세요.
() 실무 절차를 정리하세요.
생각의 실마리. 세 방법이 각각 다른 것을 정해야 합니다. 무엇을 정할 수 있고 무엇을 못 정하는지가 선택의 기준입니다.
풀이. () 나란히 놓습니다.
| 무엇 | 평균 | 계층적 | 밀도 기반 |
|---|---|---|---|
| 개수 | 미리 정함 | 잘라서 정함 | 안 정함 |
| 모양 | 공 모양 | 연결 방식이 정함 | 아무 모양 |
| 잡음 | 다 넣음 | 다 넣음 | 따로 뺌 |
| 계산 | 가장 쌈 | 제곱 이상 | 제곱 |
| 손잡이 | 연결과 자르는 높이 | 과 minPts |
셋째 줄이 밀도 기반의 큰 장점입니다. 강과 계층적 군집은 모든 점을 어딘가에 넣어야 하는데, 이상한 점 하나가 중심을 끌어당깁니다. 강의 이상탐지로 이어집니다.
() 같은 자료를 세 방법으로 나눠 봅니다.
| 자료 | 평균 순도 | 워드 연결 순도 | 밀도 기반 순도 |
|---|---|---|---|
| 공 모양 둘 | |||
| 초승달 둘 | |||
| 밀도 다름 |
자료 모양마다 이기는 방법이 다릅니다. 공 모양에서는 밀도 기반이 로 꼴찌이고 초승달에서는 으로 유일한 승자입니다.
밀도 기반의 순도는 잡음으로 뺀 점을 빼고 잰 값입니다. 그래서 순도만으로 견주면 유리해 보입니다. 잡음을 오답으로 세면 이렇게 됩니다.
| 자료 | 잡음 뺀 순도 | 잡음을 오답으로 | 잡음 비율 |
|---|---|---|---|
| 공 모양 둘 | |||
| 초승달 둘 | |||
| 밀도 다름 |
잡음 비율이 퍼센트면 순도가 에서 로 내려갑니다.
강에서 볼 문턱 조절과 같습니다. 무엇을 안 맞히기로 하느냐의 문제이고, 안 맞힌 것을 안 세면 성적이 좋아 보입니다.
() 실무 절차를 정리합니다.
| 순서 | 무엇을 하나 |
|---|---|
| 먼저 표준화 | 거리를 쓰는 방법은 다 필요 |
| 평균 여러 로 | 가장 싸고 빠른 탐색 |
| 결과가 이상하면 | 모양을 의심하고 계층적으로 |
| 잡음이 많아 보이면 | 밀도 기반으로 |
| 차원이 높으면 | 강으로 먼저 줄임 |
마지막 줄이 중요합니다. 차원이 높으면 어느 방법도 잘 안 됩니다. 거리가 뜻을 잃기 때문이고, 그러면 군집 이전에 차원을 줄여야 합니다.
이 문제에서 배우는 것. 세 방법은 가정을 어디에 두느냐가 다를 뿐 어느 것도 공짜가 아닙니다. 그리고 평가 지표가 방법에 유리하게 기울 수 있으므로, 잡음으로 뺀 점을 어떻게 셀지까지 정해야 공정한 비교가 됩니다.
확인 5-1. 밀도 기반 군집의 가장 큰 장점을 쓰세요.
답. 어디에도 안 속하는 점을 잡음으로 뺄 수 있습니다.
확인 5-2. 검산에서 공 모양 둘의 세 방법 순도를 쓰세요.
답. 과 과 입니다.
확인 5-3. 검산에서 밀도 다름 자료의 잡음 뺀 순도와 오답으로 센 순도를 쓰세요.
답. 과 입니다.
| 유형 | 무엇을 묻나 | 어디를 보나 |
|---|---|---|
| 높이의 도약 | 자연스러운 개수 | 문제 |
| 연결 방식 | 어떤 모양을 찾나 | 문제 , |
| 사슬 효과 | 다리 하나로 무너짐 | 문제 |
| 핵심점과 잡음점 | 밀도로 정의 | 문제 |
| 반경 고르기 | 번째 이웃 거리의 무릎 | 문제 |
| 밀도가 다름 | 하나로 못 함 | 문제 |
| 차원의 저주 | 밀도가 안 갈림 | 문제 |
| 세 방법의 대비 | 무엇을 정해야 하나 | 문제 |
| 잡음을 세는 법 | 안 세면 유리해 보임 | 문제 |
| 절차 | 싼 것부터 | 문제 |
연결 방식의 정의를 한자리에 모읍니다.
| 방법 | 무엇을 안 정해도 되나 | 무엇을 정해야 하나 |
|---|---|---|
| 평균 | 없음 | |
| 계층적 | 개수 | 연결 방식 |
| 밀도 기반 | 개수와 모양 | 과 minPts |
| HDBSCAN | 개수와 모양과 | 최소 군집 크기 |
문제 6. 계층적 군집이 평균과 다른 점 하나를 쓰세요.
답. 개수를 미리 안 정하고 나무를 만든 뒤 잘라서 정합니다.
문제 7. 검산에서 다섯째와 여섯째 합침의 높이를 쓰세요.
답. 과 입니다.
문제 8. 워드 연결이 무엇을 최소로 하는지 쓰세요.
답. 합쳤을 때 군집 안 제곱합의 증가입니다.
문제 9. 검산에서 공 모양 자료의 최단 연결 순도를 쓰세요.
답. 입니다.
문제 10. 검산에서 초승달 자료의 최단 연결과 평균 순도를 쓰세요.
답. 과 입니다.
문제 11. 검산에서 다리를 놓았을 때 최단 연결과 워드 연결의 순도를 쓰세요.
답. 과 입니다.
문제 12. 핵심점의 정의를 쓰세요.
답. 반경 안의 이웃이 minPts 이상인 점입니다.
문제 13. 검산에서 이 와 일 때의 군집 수를 쓰세요.
답. 개와 개입니다.
문제 14. 검산에서 minPts가 일 때 군집 수와 잡음점 수를 쓰세요.
답. 개와 개입니다.
문제 15. 검산에서 밀도가 다른 자료의 과 의 순도를 쓰세요.
답. 와 입니다.
문제 16. 검산에서 차원 와 일 때 첫 이웃과 다섯째 이웃 거리의 비를 쓰세요.
답. 과 입니다.
문제 17. 검산에서 공 모양 둘의 세 방법 순도를 쓰세요.
답. 과 과 입니다.
문제 18. 검산에서 밀도 다름 자료의 잡음 뺀 순도와 오답으로 센 순도를 쓰세요.
답. 과 입니다.
심화 1. 랜스 윌리엄스 갱신식을 정리하세요.
네 연결 방식이 하나의 식으로 적힙니다.
| 연결 | \alpha_ | ||
|---|---|---|---|
| 최단 | |||
| 최장 | |||
| 평균 | |||
| 워드 |
이 식 덕에 원래 점들을 다시 안 봐도 됩니다. 거리행렬만 갱신하면 되고, 검산의 구현이 정확히 이 꼴입니다. 의 부호 하나가 최단과 최장을 가릅니다.
심화 2. 단조성이 깨지는 연결 방식을 정리하세요.
| 연결 | 합치는 높이가 단조인가 |
|---|---|
| 최단 | 예 |
| 최장 | 예 |
| 평균 | 예 |
| 무게중심 | 아니오 |
무게중심 연결은 나중에 합칠 때 높이가 오히려 내려갈 수 있습니다. 나무 그림이 뒤집히므로 읽기가 어렵습니다. 워드는 단조인데 무게중심은 아닌 것이 둘의 중요한 차이입니다.
심화 3. DBSCAN의 도달 가능성을 정확히 정리하세요.
| 관계 | 정의 |
|---|---|
| 직접 도달 | 가 핵심점이고 가 의 이웃 |
| 도달 | 직접 도달의 사슬로 이어짐 |
| 연결 | 어떤 핵심점에서 둘 다 도달 가능 |
| 군집 | 연결된 점들의 최대 집합 |
도달은 대칭이 아닙니다. 경계점에서 핵심점으로는 도달이 안 됩니다. 그래서 경계점이 두 군집에 걸치면 먼저 만난 쪽에 들어갑니다. 점의 순서가 답을 조금 바꾸는 유일한 자리입니다.
심화 4. HDBSCAN이 무엇을 하는지 정리하세요.
| 단계 | 무엇 |
|---|---|
| 첫째 | 상호 도달 거리로 최소 신장 트리 |
| 둘째 | 그 트리로 계층적 군집 |
| 셋째 | 안정성이 큰 가지만 남김 |
| 결과 | 없이 밀도 군집 |
첫째 줄이 핵심입니다. 성긴 곳의 점은 core 거리가 크므로 거리가 부풀어 쉽게 안 이어집니다. 그래서 밀도가 다른 덩어리를 함께 잡을 수 있고, 문제 의 문제가 풀립니다.
심화 5. 계층적 군집의 계산량을 줄이는 방법을 정리하세요.
| 방법 | 계산량 | 조건 |
|---|---|---|
| 나이브 | n^ | 없음 |
| 우선순위 큐 | 없음 | |
| SLINK | n^ | 최단 연결만 |
| 표본을 줄임 | 표본 수의 제곱 | 대표점만 |
이 하한입니다. 거리행렬을 한 번은 봐야 하기 때문이고, 그래서 표본이 수만 개를 넘으면 계층적 군집을 못 씁니다. 강의 평균이 에 비례하는 것과 대비됩니다.
심화 6. 군집 결과를 어떻게 보고할지 정리하세요.
| 무엇을 함께 적나 | 왜 |
|---|---|
| 손잡이 값 | 나 이 답을 정함 |
| 군집 크기 분포 | 하나가 다 먹었는지 |
| 잡음 비율 | 안 센 점이 얼마인지 |
| 표준화 여부 | 거리의 뜻이 바뀜 |
| 여러 번 돌린 결과 | 안정적인지 |
셋째 줄이 문제 에서 본 함정입니다. 잡음 비율을 안 적으면 순도가 부풀어 보입니다. 군집은 정답이 없으므로 무엇을 어떻게 했는지가 결과의 일부입니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 계층적 군집 | hierarchical clustering | 가까운 둘을 계속 합쳐 나무를 만듭니다 |
| 덴드로그램 | dendrogram | 합치는 과정을 그린 나무입니다 |
| 최단 연결 | single linkage | 가장 가까운 두 점의 거리입니다 |
| 최장 연결 | complete linkage | 가장 먼 두 점의 거리입니다 |
| 워드 연결 | Ward linkage | 제곱합 증가가 가장 적은 둘을 합칩니다 |
| 사슬 효과 | chaining | 다리 몇 개로 두 덩어리가 이어집니다 |
| 핵심점 | core point | 이웃이 minPts 이상인 점입니다 |
| 잡음점 | noise point | 어느 군집에도 안 넣는 점입니다 |
| 도달 가능 | density-reachable | 핵심점의 사슬로 이어집니다 |
| HDBSCAN | hierarchical DBSCAN | 모든 을 훑어 안정적인 가지를 남깁니다 |
다음은 223강 가우시안 혼합과 EM 알고리즘입니다. 강은 모양을 가정했고 이 강의는 안 가정했습니다. 다음 강의는 셋째 길로 갑니다. 모양을 확률분포로 적고, 각 점이 어느 덩어리에 얼마나 속하는지를 확률로 냅니다.
import numpy as np
rng = np.random.default_rng(20270103)
def pw(s, n):
k = n - sum(2 if ord(c) > 0x2FFF else 1 for c in str(s))
return str(s) + " " * max(k, 0)
def rw(s, n):
k = n - sum(2 if ord(c) > 0x2FFF else 1 for c in str(s))
return " " * max(k, 0) + str(s)
def dist(A, B):
return np.sqrt(((A[:, None, :] - B[None, :, :]) ** 2).sum(axis=2))
def hac(X, link):
n = len(X)
D = dist(X, X).copy()
np.fill_diagonal(D, np.inf)
mem = [[i] for i in range(n)]
alive = list(range(n))
merges = []
while len(alive) > 1:
sub = D[np.ix_(alive, alive)]
p = int(np.argmin(sub))
a, b = p // len(alive), p % len(alive)
i, j = alive[a], alive[b]
merges.append((i, j, float(sub[a, b]), len(mem[i]) + len(mem[j])))
for t in alive:
if t == i or t == j:
continue
if link == "single":
v = min(D[i, t], D[j, t])
elif link == "complete":
v = max(D[i, t], D[j, t])
elif link == "average":
v = (len(mem[i]) * D[i, t] + len(mem[j]) * D[j, t]) \
/ (len(mem[i]) + len(mem[j]))
else:
ni, nj, nt = len(mem[i]), len(mem[j]), len(mem[t])
v = np.sqrt(((ni + nt) * D[i, t] ** 2
+ (nj + nt) * D[j, t] ** 2
- nt * D[i, j] ** 2) / (ni + nj + nt))
D[i, t] = D[t, i] = v
mem[i] = mem[i] + mem[j]
alive.remove(j)
return merges, mem
def cut_tree(X, link, k):
n = len(X)
D = dist(X, X).copy()
np.fill_diagonal(D, np.inf)
mem = [[i] for i in range(n)]
alive = list(range(n))
while len(alive) > k:
sub = D[np.ix_(alive, alive)]
p = int(np.argmin(sub))
a, b = p // len(alive), p % len(alive)
i, j = alive[a], alive[b]
for t in alive:
if t == i or t == j:
continue
if link == "single":
v = min(D[i, t], D[j, t])
elif link == "complete":
v = max(D[i, t], D[j, t])
elif link == "average":
v = (len(mem[i]) * D[i, t] + len(mem[j]) * D[j, t]) \
/ (len(mem[i]) + len(mem[j]))
else:
ni, nj, nt = len(mem[i]), len(mem[j]), len(mem[t])
v = np.sqrt(((ni + nt) * D[i, t] ** 2
+ (nj + nt) * D[j, t] ** 2
- nt * D[i, j] ** 2) / (ni + nj + nt))
D[i, t] = D[t, i] = v
mem[i] = mem[i] + mem[j]
alive.remove(j)
lab = np.zeros(n, dtype=np.int64)
for c, i in enumerate(alive):
lab[mem[i]] = c
return lab
def dbscan(X, eps, minpts):
n = len(X)
D = dist(X, X)
nb = [np.where(D[i] <= eps)[0] for i in range(n)]
core = np.array([len(nb[i]) >= minpts for i in range(n)])
lab = np.full(n, -1, dtype=np.int64)
c = 0
for i in range(n):
if lab[i] != -1 or not core[i]:
continue
stack = [i]
lab[i] = c
while stack:
u = stack.pop()
for v in nb[u]:
if lab[v] == -1:
lab[v] = c
if core[v]:
stack.append(v)
c += 1
return lab, core, c
def purity(lab, z, k):
tot = 0
for j in range(k):
m = lab == j
if m.any():
tot += np.bincount(z[m]).max()
return float(tot / len(z))
def kmeans(X, k, r, tries=15):
best = None
for _ in range(tries):
C = X[r.permutation(len(X))[:k]].copy()
lab = np.zeros(len(X), dtype=np.int64)
for _ in range(200):
new = np.argmin(dist(X, C) ** 2, axis=1)
if np.array_equal(new, lab):
break
lab = new
for j in range(k):
m = lab == j
if m.any():
C[j] = X[m].mean(axis=0)
w = float(np.sum(np.min(dist(X, C) ** 2, axis=1)))
if best is None or w < best[1]:
best = (lab, w)
return best[0]
# --- 문제 1: 개수를 안 정하고 나무를 만듭니다 ---------------------------
print(" 221강은 군집 개수를 미리 정해야 했습니다")
print(" 이번에는 정하지 않고 모든 개수를 한꺼번에 만듭니다")
print(" %s %s %s"
% (pw("무엇", 22), rw("k 평균", 22), rw("계층적 군집", 24)))
for a, b, c in [("개수를 언제 정하나", "먼저", "나중에 잘라서"),
("결과가 무엇인가", "배정 하나", "나무 하나"),
("시작점에 딸리나", "예", "아니오"),
("계산량", "n 에 비례", "n 제곱에서 세제곱"),
("덩어리 모양", "공 모양만", "연결 방식이 정함")]:
print(" %s %s %s" % (pw(a, 22), rw(b, 22), rw(c, 24)))
print(" 가까운 둘을 계속 합치면 나무 하나가 나옵니다")
print(" 그 나무를 어느 높이에서 자르면 그 높이의 군집이 나옵니다")
print(" 작은 자료에서 합치는 과정을 봅니다")
P = np.array([[0.0, 0.0], [0.3, 0.1], [0.2, 0.5],
[4.0, 4.0], [4.3, 3.9], [4.1, 4.4],
[8.0, 0.0], [8.2, 0.3]])
mg, _ = hac(P, "single")
print(" 점 8 개를 세 덩어리로 놓았습니다")
print(" %s %s %s %s"
% (pw("합치는 순서", 14), rw("합친 높이", 16), rw("합친 뒤 크기", 16),
rw("남은 덩어리 수", 18)))
for t, (i, j, h, sz) in enumerate(mg):
print(" %s %16.6f %16d %18d"
% (pw(str(t + 1), 14), h, sz, 8 - t - 1))
print(" 높이가 대체로 커지다가 마지막 둘에서 크게 뜁니다")
print(" 0.42 와 5.16 사이 어느 높이에서 잘라도 세 덩어리가 나옵니다")
print(" 높이의 큰 도약이 자연스러운 군집 개수를 알려 줍니다")
print(" 연결 방식이 무엇을 바꾸는지 정리합니다")
print(" %s %s %s"
% (pw("연결 방식", 18), rw("두 덩어리 거리", 24), rw("어떤 모양을 찾나", 24)))
for a, b, c in [("최단", "가장 가까운 두 점", "길게 이어진 것"),
("최장", "가장 먼 두 점", "빽빽한 공 모양"),
("평균", "모든 쌍의 평균", "가운데쯤"),
("워드", "합쳤을 때 제곱합 증가", "k 평균과 비슷")]:
print(" %s %s %s" % (pw(a, 18), rw(b, 24), rw(c, 24)))
print(" 최단 연결은 한 점만 가까우면 붙습니다. 사슬처럼 이어집니다")
print(" 최장 연결은 모든 점이 가까워야 붙습니다. 뭉친 것만 찾습니다")
# --- 문제 2: 연결 방식이 답을 바꿉니다 ----------------------------------
print(" 네 가지 연결 방식을 같은 자료에 걸어 봅니다")
n2 = 200
z2 = rng.integers(0, 2, n2)
mu2 = np.array([[0.0, 0.0], [3.5, 0.0]])
X2 = mu2[z2] + rng.normal(0, 0.8, (n2, 2))
print(" 공 모양 덩어리 둘입니다")
print(" %s %s %s"
% (pw("연결 방식", 18), rw("순도", 16), rw("가장 큰 군집 크기", 22)))
for nm, lk in [("최단", "single"), ("최장", "complete"),
("평균", "average"), ("워드", "ward")]:
lab = cut_tree(X2, lk, 2)
print(" %s %16.6f %22d"
% (pw(nm, 18), purity(lab, z2, 2),
max(int((lab == j).sum()) for j in range(2))))
print(" 최장 평균 워드는 0.98 을 넘습니다. 가정이 자료에 맞습니다")
print(" 최단 연결만 0.540000 으로 실패합니다. 두 덩어리가 가까워 한 점 다리로 이어졌습니다")
print(" 가장 큰 군집이 199 개라 사실상 하나로 묶어 버렸습니다")
print(" 이번에는 길게 이어진 자료를 봅니다")
t3 = rng.uniform(0, np.pi, 150)
Xa = np.stack([2 * np.cos(t3), 2 * np.sin(t3)], axis=1) \
+ rng.normal(0, 0.12, (150, 2))
Xb = np.stack([2 * np.cos(t3) + 2.0, -2 * np.sin(t3) + 0.6], axis=1) \
+ rng.normal(0, 0.12, (150, 2))
X3 = np.vstack([Xa, Xb])
z3 = np.array([0] * 150 + [1] * 150)
print(" 초승달 두 개가 맞물린 자료입니다")
print(" %s %s %s"
% (pw("방법", 22), rw("순도", 16), rw("가장 큰 군집 크기", 22)))
for nm, lk in [("최단 연결", "single"), ("최장 연결", "complete"),
("평균 연결", "average"), ("워드 연결", "ward")]:
lab = cut_tree(X3, lk, 2)
print(" %s %16.6f %22d"
% (pw(nm, 22), purity(lab, z3, 2),
max(int((lab == j).sum()) for j in range(2))))
lk = kmeans(X3, 2, rng)
print(" %s %16.6f %22d"
% (pw("k 평균", 22), purity(lk, z3, 2),
max(int((lk == j).sum()) for j in range(2))))
print(" 최단 연결만 초승달을 찾습니다. 이어진 것을 따라가기 때문입니다")
print(" 나머지는 221강 문제 4 와 같은 이유로 못 찾습니다")
print(" 연결 방식이 곧 어떤 모양을 가정하는지입니다")
print(" 최단 연결의 약점도 봅니다")
X4 = np.vstack([rng.normal(0, 0.5, (100, 2)),
rng.normal(0, 0.5, (100, 2)) + np.array([4.0, 0.0])])
z4 = np.array([0] * 100 + [1] * 100)
br = np.stack([np.linspace(0.8, 3.2, 12),
np.zeros(12)], axis=1) + rng.normal(0, 0.05, (12, 2))
X4b = np.vstack([X4, br])
z4b = np.concatenate([z4, np.zeros(12, dtype=np.int64)])
print(" 두 덩어리 사이에 점 12 개짜리 다리를 놓습니다")
print(" %s %s %s"
% (pw("무엇", 24), rw("다리 없을 때 순도", 22), rw("다리 있을 때 순도", 22)))
for nm, lk_ in [("최단 연결", "single"), ("워드 연결", "ward")]:
a1 = purity(cut_tree(X4, lk_, 2), z4, 2)
a2 = purity(cut_tree(X4b, lk_, 2)[:200], z4, 2)
print(" %s %22.6f %22.6f" % (pw(nm, 24), a1, a2))
print(" 다리 하나로 최단 연결이 무너집니다. 사슬 효과라 합니다")
print(" 워드 연결은 다리가 있어도 흔들리지 않습니다")
print(" 튼튼함과 유연함이 맞바뀝니다. 공짜가 없습니다")
# --- 문제 3: 밀도로 정의합니다 ------------------------------------------
print(" 덩어리를 모양이 아니라 밀도로 정의해 봅니다")
print(" %s %s %s"
% (pw("무엇", 20), rw("정의", 28), rw("무엇이 좋은가", 22)))
for a, b, c in [("반경", "eps 안을 이웃이라 함", "국소적으로 봄"),
("핵심점", "이웃이 minPts 이상", "빽빽한 곳"),
("경계점", "핵심점의 이웃이지만 자기는 아님", "가장자리"),
("잡음점", "둘 다 아님", "군집에 안 넣음")]:
print(" %s %s %s" % (pw(a, 20), rw(b, 28), rw(c, 22)))
print(" 핵심점끼리 이어지면 한 군집입니다. 개수를 안 정합니다")
print(" 그리고 어디에도 안 속하는 점을 잡음으로 남길 수 있습니다")
print(" 초승달 자료에 걸어 봅니다")
print(" %s %s %s %s %s"
% (pw("eps", 10), rw("군집 수", 12), rw("잡음점 수", 14),
rw("핵심점 수", 14), rw("순도", 14)))
for eps in [0.15, 0.25, 0.35, 0.6, 1.2]:
lab, core, c = dbscan(X3, eps, 5)
ok = lab >= 0
pu = purity(lab[ok], z3[ok], max(c, 1)) if ok.any() and c > 0 else 0.0
print(" %s %12d %14d %14d %14.6f"
% (pw("%.2f" % eps, 10), c, int((lab < 0).sum()),
int(core.sum()), pu))
print(" eps 가 작으면 군집이 잘게 쪼개지고 잡음이 많아집니다")
print(" eps 가 크면 모두 한 덩어리가 됩니다")
print(" 가운데 어디쯤에서 초승달 둘을 정확히 찾습니다")
print(" 맨 윗줄의 순도 1 은 군집을 17 개로 쪼갠 덕이라 좋은 값이 아닙니다")
print(" 순도는 군집 수와 함께 봐야 합니다")
print(" minPts 를 바꿔 봅니다")
print(" %s %s %s %s"
% (pw("minPts", 12), rw("군집 수", 12), rw("잡음점 수", 14),
rw("핵심점 비율", 18)))
for mp in [2, 5, 10, 30]:
lab, core, c = dbscan(X3, 0.35, mp)
print(" %s %12d %14d %18.6f"
% (pw(str(mp), 12), c, int((lab < 0).sum()),
float(core.mean())))
print(" minPts 를 키우면 핵심점이 줄고 잡음이 늡니다")
print(" 대체로 차원의 두 배쯤에서 시작해 조정합니다")
print(" eps 를 고르는 방법을 봅니다")
D3 = dist(X3, X3)
kd = np.sort(D3, axis=1)[:, 5]
kd = np.sort(kd)
print(" 각 점에서 5 번째 가까운 이웃까지의 거리를 정렬합니다")
print(" %s %s %s"
% (pw("몇 번째 점", 16), rw("5 번째 이웃 거리", 22), rw("앞과의 차", 16)))
idx = [0, 75, 150, 225, 285, 299]
for a, i in enumerate(idx):
dd = 0.0 if a == 0 else kd[i] - kd[idx[a - 1]]
print(" %s %22.6f %16.6f" % (pw(str(i + 1), 16), kd[i], dd))
print(" 끝에서 값이 급격히 커집니다. 그 무릎 자리가 eps 후보입니다")
print(" 무릎 앞은 덩어리 안의 점이고 뒤는 떨어진 점입니다")
print(" 221강의 팔꿈치와 같은 종류의 눈짐작입니다")
# --- 문제 4: 밀도 기반의 한계 -------------------------------------------
print(" 밀도가 다른 덩어리가 함께 있으면 어떻게 되는지 봅니다")
Xd = np.vstack([rng.normal(0, 0.25, (150, 2)),
rng.normal(0, 1.2, (150, 2)) + np.array([3.0, 0.0])])
zd = np.array([0] * 150 + [1] * 150)
print(" 빽빽한 덩어리와 성긴 덩어리를 나란히 둡니다")
print(" %s %s %s %s %s"
% (pw("eps", 10), rw("군집 수", 12), rw("잡음점 수", 14),
rw("성긴 쪽 잡음 비율", 22), rw("순도", 14)))
for eps in [0.2, 0.35, 0.6, 1.0, 1.6]:
lab, core, c = dbscan(Xd, eps, 5)
nz = float(((lab < 0) & (zd == 1)).sum() / 150)
ok = lab >= 0
pu = purity(lab[ok], zd[ok], max(c, 1)) if ok.any() and c > 0 else 0.0
print(" %s %12d %14d %22.6f %14.6f"
% (pw("%.2f" % eps, 10), c, int((lab < 0).sum()), nz, pu))
print(" eps 가 0.20 이면 성긴 덩어리의 84 퍼센트가 잡음이 되고 순도는 0.987952 입니다")
print(" eps 를 키우면 잡음은 줄지만 어느 자리에서 둘이 한 덩어리로 합쳐집니다")
print(" 순도가 그때 0.5 로 떨어집니다. 아무것도 못 나눈 것입니다")
print(" 잡음을 줄이는 것과 둘을 갈라 놓는 것이 서로 어긋납니다")
print(" 이 문제를 푸는 방법을 정리합니다")
print(" %s %s %s"
% (pw("방법", 22), rw("무엇을 하나", 26), rw("무엇이 남나", 22)))
for a, b, c in [("HDBSCAN", "eps 를 다 훑어 나무로", "최소 크기만 정함"),
("OPTICS", "도달 거리로 순서 매김", "그림을 봐야 함"),
("자료를 나눠 따로", "영역마다 다른 eps", "나누는 기준이 필요"),
("223강의 혼합모형", "밀도를 모형으로", "모양을 가정함")]:
print(" %s %s %s" % (pw(a, 22), rw(b, 26), rw(c, 22)))
print(" 첫 줄이 요즘 표준입니다. eps 를 안 정해도 됩니다")
print(" 차원이 오르면 밀도 기반이 왜 어려운지 봅니다")
print(" %s %s %s %s"
% (pw("차원", 10), rw("가장 가까운 이웃 거리", 26),
rw("5 번째 이웃 거리", 22), rw("둘의 비", 14)))
for d in [2, 5, 20, 100]:
Q = rng.normal(0, 1, (300, d))
DQ = np.sort(dist(Q, Q), axis=1)
print(" %s %26.6f %22.6f %14.6f"
% (pw(str(d), 10), float(DQ[:, 1].mean()), float(DQ[:, 5].mean()),
float(DQ[:, 5].mean() / DQ[:, 1].mean())))
print(" 차원이 오르면 첫 이웃과 다섯째 이웃의 거리가 비슷해집니다")
print(" 그러면 밀도가 높은 곳과 낮은 곳의 구분이 사라집니다")
print(" 213강 문제 2 의 거리 집중이 밀도 기반 방법을 무력하게 만듭니다")
# --- 문제 5: 실무에서 쓰기 ---------------------------------------------
print(" 세 방법을 나란히 놓고 정리합니다")
print(" %s %s %s %s"
% (pw("무엇", 18), rw("k 평균", 18), rw("계층적", 20), rw("밀도 기반", 20)))
for a, b, c, d in [("개수", "미리 정함", "잘라서 정함", "안 정함"),
("모양", "공 모양", "연결 방식이 정함", "아무 모양"),
("잡음", "다 넣음", "다 넣음", "따로 뺌"),
("계산", "가장 쌈", "n 제곱 이상", "n 제곱"),
("손잡이", "k", "연결과 자르는 높이", "eps 와 minPts")]:
print(" %s %s %s %s"
% (pw(a, 18), rw(b, 18), rw(c, 20), rw(d, 20)))
print(" 셋째 줄이 밀도 기반의 큰 장점입니다. 225강의 이상탐지로 이어집니다")
print(" 같은 자료를 세 방법으로 나눠 견줍니다")
print(" %s %s %s %s"
% (pw("자료", 20), rw("k 평균 순도", 18), rw("워드 연결 순도", 20),
rw("밀도 기반 순도", 20)))
sets = [("공 모양 둘", X2, z2, 2, 0.6),
("초승달 둘", X3, z3, 2, 0.35),
("밀도 다름", Xd, zd, 2, 0.5)]
for nm, XX, zz, kk, ee in sets:
a1 = purity(kmeans(XX, kk, rng), zz, kk)
a2 = purity(cut_tree(XX, "ward", kk), zz, kk)
lb, _, c = dbscan(XX, ee, 5)
ok = lb >= 0
a3 = purity(lb[ok], zz[ok], max(c, 1)) if ok.any() and c > 0 else 0.0
print(" %s %18.6f %20.6f %20.6f"
% (pw(nm, 20), a1, a2, a3))
print(" 자료 모양마다 이기는 방법이 다릅니다")
print(" 밀도 기반의 순도는 잡음으로 뺀 점을 빼고 잰 값입니다")
print(" 그래서 순도만으로 견주면 밀도 기반이 유리해 보입니다")
print(" 잡음을 뺀 것이 얼마나 유리한지 봅니다")
print(" %s %s %s %s"
% (pw("자료", 20), rw("잡음 뺀 순도", 18), rw("잡음을 오답으로", 22),
rw("잡음 비율", 16)))
for nm, XX, zz, kk, ee in sets:
lb, _, c = dbscan(XX, ee, 5)
ok = lb >= 0
a3 = purity(lb[ok], zz[ok], max(c, 1)) if ok.any() and c > 0 else 0.0
a4 = a3 * float(ok.mean())
print(" %s %18.6f %22.6f %16.6f"
% (pw(nm, 20), a3, a4, float((~ok).mean())))
print(" 잡음을 오답으로 세면 값이 크게 내려갑니다")
print(" 226강에서 볼 문턱 조절과 같습니다. 무엇을 안 맞히기로 하느냐의 문제입니다")
print(" 실무 절차를 정리합니다")
print(" %s %s"
% (pw("순서", 26), rw("무엇을 하나", 34)))
for a, b in [("먼저 표준화", "거리를 쓰는 방법은 다 필요"),
("k 평균 여러 k 로", "가장 싸고 빠른 탐색"),
("결과가 이상하면", "모양을 의심하고 계층적으로"),
("잡음이 많아 보이면", "밀도 기반으로"),
("차원이 높으면", "224강으로 먼저 줄임")]:
print(" %s %s" % (pw(a, 26), rw(b, 34)))
print(" 마지막 줄이 중요합니다. 차원이 높으면 어느 방법도 잘 안 됩니다")
print(" 222강은 모양을 안 가정했습니다. 223강은 모양을 확률로 적습니다")
# 221강은 군집 개수를 미리 정해야 했습니다
# 이번에는 정하지 않고 모든 개수를 한꺼번에 만듭니다
# 무엇 k 평균 계층적 군집
# 개수를 언제 정하나 먼저 나중에 잘라서
# 결과가 무엇인가 배정 하나 나무 하나
# 시작점에 딸리나 예 아니오
# 계산량 n 에 비례 n 제곱에서 세제곱
# 덩어리 모양 공 모양만 연결 방식이 정함
# 가까운 둘을 계속 합치면 나무 하나가 나옵니다
# 그 나무를 어느 높이에서 자르면 그 높이의 군집이 나옵니다
# 작은 자료에서 합치는 과정을 봅니다
# 점 8 개를 세 덩어리로 놓았습니다
# 합치는 순서 합친 높이 합친 뒤 크기 남은 덩어리 수
# 1 0.316228 2 7
# 2 0.316228 2 6
# 3 0.360555 2 5
# 4 0.412311 3 4
# 5 0.412311 3 3
# 6 5.166237 6 2
# 7 5.307542 8 1
# 높이가 대체로 커지다가 마지막 둘에서 크게 뜁니다
# 0.42 와 5.16 사이 어느 높이에서 잘라도 세 덩어리가 나옵니다
# 높이의 큰 도약이 자연스러운 군집 개수를 알려 줍니다
# 연결 방식이 무엇을 바꾸는지 정리합니다
# 연결 방식 두 덩어리 거리 어떤 모양을 찾나
# 최단 가장 가까운 두 점 길게 이어진 것
# 최장 가장 먼 두 점 빽빽한 공 모양
# 평균 모든 쌍의 평균 가운데쯤
# 워드 합쳤을 때 제곱합 증가 k 평균과 비슷
# 최단 연결은 한 점만 가까우면 붙습니다. 사슬처럼 이어집니다
# 최장 연결은 모든 점이 가까워야 붙습니다. 뭉친 것만 찾습니다
# 네 가지 연결 방식을 같은 자료에 걸어 봅니다
# 공 모양 덩어리 둘입니다
# 연결 방식 순도 가장 큰 군집 크기
# 최단 0.540000 199
# 최장 0.985000 107
# 평균 0.985000 107
# 워드 0.980000 106
# 최장 평균 워드는 0.98 을 넘습니다. 가정이 자료에 맞습니다
# 최단 연결만 0.540000 으로 실패합니다. 두 덩어리가 가까워 한 점 다리로 이어졌습니다
# 가장 큰 군집이 199 개라 사실상 하나로 묶어 버렸습니다
# 이번에는 길게 이어진 자료를 봅니다
# 초승달 두 개가 맞물린 자료입니다
# 방법 순도 가장 큰 군집 크기
# 최단 연결 1.000000 150
# 최장 연결 0.873333 188
# 평균 연결 0.850000 195
# 워드 연결 0.850000 195
# k 평균 0.726667 158
# 최단 연결만 초승달을 찾습니다. 이어진 것을 따라가기 때문입니다
# 나머지는 221강 문제 4 와 같은 이유로 못 찾습니다
# 연결 방식이 곧 어떤 모양을 가정하는지입니다
# 최단 연결의 약점도 봅니다
# 두 덩어리 사이에 점 12 개짜리 다리를 놓습니다
# 무엇 다리 없을 때 순도 다리 있을 때 순도
# 최단 연결 1.000000 0.505000
# 워드 연결 1.000000 1.000000
# 다리 하나로 최단 연결이 무너집니다. 사슬 효과라 합니다
# 워드 연결은 다리가 있어도 흔들리지 않습니다
# 튼튼함과 유연함이 맞바뀝니다. 공짜가 없습니다
# 덩어리를 모양이 아니라 밀도로 정의해 봅니다
# 무엇 정의 무엇이 좋은가
# 반경 eps 안을 이웃이라 함 국소적으로 봄
# 핵심점 이웃이 minPts 이상 빽빽한 곳
# 경계점 핵심점의 이웃이지만 자기는 아님 가장자리
# 잡음점 둘 다 아님 군집에 안 넣음
# 핵심점끼리 이어지면 한 군집입니다. 개수를 안 정합니다
# 그리고 어디에도 안 속하는 점을 잡음으로 남길 수 있습니다
# 초승달 자료에 걸어 봅니다
# eps 군집 수 잡음점 수 핵심점 수 순도
# 0.15 17 97 137 1.000000
# 0.25 4 7 275 1.000000
# 0.35 2 1 297 1.000000
# 0.60 2 0 300 1.000000
# 1.20 1 0 300 0.500000
# eps 가 작으면 군집이 잘게 쪼개지고 잡음이 많아집니다
# eps 가 크면 모두 한 덩어리가 됩니다
# 가운데 어디쯤에서 초승달 둘을 정확히 찾습니다
# 맨 윗줄의 순도 1 은 군집을 17 개로 쪼갠 덕이라 좋은 값이 아닙니다
# 순도는 군집 수와 함께 봐야 합니다
# minPts 를 바꿔 봅니다
# minPts 군집 수 잡음점 수 핵심점 비율
# 2 2 1 0.996667
# 5 2 1 0.990000
# 10 4 7 0.863333
# 30 0 300 0.000000
# minPts 를 키우면 핵심점이 줄고 잡음이 늡니다
# 대체로 차원의 두 배쯤에서 시작해 조정합니다
# eps 를 고르는 방법을 봅니다
# 각 점에서 5 번째 가까운 이웃까지의 거리를 정렬합니다
# 몇 번째 점 5 번째 이웃 거리 앞과의 차
# 1 0.075296 0.000000
# 76 0.138315 0.063020
# 151 0.180964 0.042648
# 226 0.221422 0.040458
# 286 0.313822 0.092400
# 300 0.467157 0.153335
# 끝에서 값이 급격히 커집니다. 그 무릎 자리가 eps 후보입니다
# 무릎 앞은 덩어리 안의 점이고 뒤는 떨어진 점입니다
# 221강의 팔꿈치와 같은 종류의 눈짐작입니다
# 밀도가 다른 덩어리가 함께 있으면 어떻게 되는지 봅니다
# 빽빽한 덩어리와 성긴 덩어리를 나란히 둡니다
# eps 군집 수 잡음점 수 성긴 쪽 잡음 비율 순도
# 0.20 2 134 0.840000 0.987952
# 0.35 6 66 0.433333 0.974359
# 0.60 2 15 0.100000 0.547368
# 1.00 1 2 0.013333 0.503356
# 1.60 1 0 0.000000 0.500000
# eps 가 0.20 이면 성긴 덩어리의 84 퍼센트가 잡음이 되고 순도는 0.987952 입니다
# eps 를 키우면 잡음은 줄지만 어느 자리에서 둘이 한 덩어리로 합쳐집니다
# 순도가 그때 0.5 로 떨어집니다. 아무것도 못 나눈 것입니다
# 잡음을 줄이는 것과 둘을 갈라 놓는 것이 서로 어긋납니다
# 이 문제를 푸는 방법을 정리합니다
# 방법 무엇을 하나 무엇이 남나
# HDBSCAN eps 를 다 훑어 나무로 최소 크기만 정함
# OPTICS 도달 거리로 순서 매김 그림을 봐야 함
# 자료를 나눠 따로 영역마다 다른 eps 나누는 기준이 필요
# 223강의 혼합모형 밀도를 모형으로 모양을 가정함
# 첫 줄이 요즘 표준입니다. eps 를 안 정해도 됩니다
# 차원이 오르면 밀도 기반이 왜 어려운지 봅니다
# 차원 가장 가까운 이웃 거리 5 번째 이웃 거리 둘의 비
# 2 0.141561 0.326540 2.306711
# 5 0.854007 1.284034 1.503539
# 20 3.871634 4.433939 1.145237
# 100 11.715161 12.302850 1.050165
# 차원이 오르면 첫 이웃과 다섯째 이웃의 거리가 비슷해집니다
# 그러면 밀도가 높은 곳과 낮은 곳의 구분이 사라집니다
# 213강 문제 2 의 거리 집중이 밀도 기반 방법을 무력하게 만듭니다
# 세 방법을 나란히 놓고 정리합니다
# 무엇 k 평균 계층적 밀도 기반
# 개수 미리 정함 잘라서 정함 안 정함
# 모양 공 모양 연결 방식이 정함 아무 모양
# 잡음 다 넣음 다 넣음 따로 뺌
# 계산 가장 쌈 n 제곱 이상 n 제곱
# 손잡이 k 연결과 자르는 높이 eps 와 minPts
# 셋째 줄이 밀도 기반의 큰 장점입니다. 225강의 이상탐지로 이어집니다
# 같은 자료를 세 방법으로 나눠 견줍니다
# 자료 k 평균 순도 워드 연결 순도 밀도 기반 순도
# 공 모양 둘 0.985000 0.980000 0.534031
# 초승달 둘 0.726667 0.850000 1.000000
# 밀도 다름 0.940000 0.956667 0.963768
# 자료 모양마다 이기는 방법이 다릅니다
# 밀도 기반의 순도는 잡음으로 뺀 점을 빼고 잰 값입니다
# 그래서 순도만으로 견주면 밀도 기반이 유리해 보입니다
# 잡음을 뺀 것이 얼마나 유리한지 봅니다
# 자료 잡음 뺀 순도 잡음을 오답으로 잡음 비율
# 공 모양 둘 0.534031 0.510000 0.045000
# 초승달 둘 1.000000 0.996667 0.003333
# 밀도 다름 0.963768 0.886667 0.080000
# 잡음을 오답으로 세면 값이 크게 내려갑니다
# 226강에서 볼 문턱 조절과 같습니다. 무엇을 안 맞히기로 하느냐의 문제입니다
# 실무 절차를 정리합니다
# 순서 무엇을 하나
# 먼저 표준화 거리를 쓰는 방법은 다 필요
# k 평균 여러 k 로 가장 싸고 빠른 탐색
# 결과가 이상하면 모양을 의심하고 계층적으로
# 잡음이 많아 보이면 밀도 기반으로
# 차원이 높으면 224강으로 먼저 줄임
# 마지막 줄이 중요합니다. 차원이 높으면 어느 방법도 잘 안 됩니다
# 222강은 모양을 안 가정했습니다. 223강은 모양을 확률로 적습니다