실습 · 연습문제 1개

길이가 모두 같은 서열 목록 seqs(치환만 있어 정렬이 필요 없다고 가정)를 받아, 단일 연결(single linkage) 군집 번호를 반환하는 함수 identity_clusters(seqs, threshold)를 완성한다.

• 두 서열의 동일성은 같은 위치에 같은 글자가 있는 비율이다: $\mathrm{id}(a, b) = \frac{1}{L} \sum_{k} [a_k = b_k]$.
• 동일성이 threshold 이상인 두 서열을 간선으로 잇는다. 간선으로 (직접 또는 다른 서열을 거쳐) 이어진 서열은 모두 같은 군집이다(그래프의 연결 성분).
• 반환값은 길이 len(seqs)의 정수 배열이다. 군집 번호는 0부터 시작하고, 처음 등장하는 순서대로 0, 1, 2, …를 붙인다(첫 서열의 군집이 0, 그 군집에 속하지 않는 첫 서열의 군집이 1, …).

이렇게 만든 군집을 통째로 train 또는 test에 배정하면, 서로 다른 군집의 어떤 두 서열도 동일성이 threshold 미만이므로 모든 test 서열이 모든 train 서열과 기준 미만이 된다.

테스트는 손으로 만든 예(사슬처럼 이어지는 경우 포함), 군집 사이의 최대 동일성이 기준 미만인지, 군집 안의 서열이 실제로 이어져 있는지 확인한다.

힌트: 서열을 정수 배열 (N, L)로 바꾸면 (S[:, None, :] == S[None, :, :]).mean(-1)로 동일성 행렬을 한 번에 구할 수 있다. 연결 성분은 너비 우선 탐색이나 union–find로 찾는다(scipy.sparse.csgraph.connected_components를 써도 되지만, 번호 붙이는 규칙을 맞춰야 한다).