파이썬 데이터사이언스 핸드북 2 장 - 정렬과 파티셔닝

NumPy 배열의 값을 정렬하는 알고리즘: 삽입 정렬 (insertion sorts), 선택 정렬 (selection sorts), 병합 정렬 (merge sorts), 퀵 정렬 (quick sorts), 버블 정렬 (bubble sorts) 등이 있지만... 실제로 응용기술만 알면 되는 우리는 이 원리를 다 알 피요는 없다. 

Numpy 의 정렬 메서드가 효율적인 배열을 알아서 수행해주기 때문이다 +___+b

 

파이썬 배열 알고리즘 맛보기 - Selection Sort

간단한 선택 정렬은 리스트의 최솟값을 반복적으로 찾아서 리스트가 정렬될 때까지 값을 교환한다.
즉 왼쪽부터 원소를 한 개 씩 검사한다. N 개의 값을 가진 리스트의 경우 N 번 반복해야 한다. Big-O 표기법 기준 O(N)*

selection sort python

아직 익숙하지 않아서 for loop 돌 때 일어나는 일을 분해해보았다. (나를 괴롭게 했던 알고리즘...ㅎ)

이전	검사 인덱스	검사 안한 대상	검사안한대상 최소값 인덱스	swap 대상 인덱스	현재위치 값	바꿀대상 값	결과
x	i	x[i:]	np.argmin(x[i:])	swap	x[i]	x[swap]	x'
[2,1,4,3,5]	0	[2,1,3,4,5]	1	1	2	1	[1,2,4,3,5]
[1,2,4,3,5]	1	[2,4,3,5]	0	1	2	2	[1,2,4,3,5]
[1,2,4,3,5]	2	[4,3,5]	1	3	4	3	[1,2,3,4,5]
[1,2,3,4,5]	3	[4,5]	0	3	4	4	[1,2,3,4,5]
[1,2,3,4,5]	4	[5]	0	4	5	5	[1,2,3,4,5]

 

파이썬에는 위 알고리즘보다 훨씬 더 효율적인 정렬 알고리즘이 내장되어 있다. 먼저 파이썬 내장 알고리즘도 있지만, 여기서는 바로 NumPy 에 포함된 NumPy 배열에 최적화된 루틴을 살펴보자.

---

NumPy 의 빠른 정렬: np.sort 와 np.argsort

 

np.sort 는 기본적으로 퀵 정렬 알고리즘을 사용하지만, 병합 정렬, 힙 정렬도 사용할 수 있다고 한다.

입력값을 수정하지 않고 배열의 정렬 버전을 반환하려면 np.sort 를 사용하면 된다.

np.sort(x)

 

배열을 그 자리에서 바로 정렬하는 게 좋으면 배열의 sort 메서드를 사용하면 된다. 

x.sort()

 

이와 관련된 함수로는 정렬된 요소의 인덱스를 반환하는 argsort 가 있다. 

np.argsort(x)

NumPy 정렬 알고리즘은 axis 인수를 사용해 다차원 배열의 특정 행이나 특정 열에 따라 정렬할 수 있다는 것이다. 단, 각 행이나 열을 독립적인 배열로 취급하므로 행 또는 열 사이의 관계는 잃어버린다는 점을 명심하자. 

np.sort(X, axis=0)

 

 

부분 정렬: 파티션 나누기

 

때때로 전체 배열을 정렬할 필요는 없고, 단순히 배열에서 K 개의 가장 작은 값을 찾고 싶을때가 있다. NumPy 에서는 np.partition 함수에서 기능을 제공한다. 

np.partition

 

sort, argsort 와 동일한 방식으로 partition 된 인덱스를 찾기 위해서 argpartition 을 활용할 수 있다. 

np.argpartition

 

 

예제: k 최근접 이웃 알고리즘

평면도에 뿌려진 10개의 점이 있다. 각 점의 가장 까가운 이웃들을 찾기 위해 축을 따라 argsort 함수를 어떻게 사용하는지 간단히 살펴보자.

 

1. 점 10개

X (10,2) 는 10개의 점에 대한 X축, Y축 값을 나타낸다. 

산포도를 그리면 다음과 같다. 

 

2. 두 점간의 거리 계산 - 벡터화 연산

기준이 되는 점과 비교대상 점 간의 거리를 계산한다.  이를 위해 벡터화된 연산을 시도한다!아래 수식에서는 거리의 제곱을 계산하고 있다. (제곱의 값 순서나 제곱근 값의 순서가 동일하기 때문에 불필요한 제곱근을 생략하였다.)

 

문제는 나에게 이 공식이 너무 어려웠다.

X[:, np.newaxis, :]  (10, 1, 2)       X 의 2차원에서 []로 감싸고,  X 의 2차원에서 [] 로 감싼 부분을 10번 반복하도록 확장하게 된다.

X[np.newaxis, :, :] (1, 10, 2)        X 의 1차원에서 []로 감싸고, X 의 1차원에서 [] 로 감싼 부분을 10번 반복하도록 확장하게 된다. 

두개는 (10, 10, 2) 로 브로드캐스팅 된 후 계산된다.

 

 

첫번째 차원의 원소 (10,2) 에 대해서 계산값은 다음을 의미한다.

X[:, np.newaxis, :]  (10, 1, 2)  의 첫번째 원소 [0.11089082, 0.4393365] 는 기준점

X[np.newaxis, :, :]  (1, 10, 2) 이 첫번째 원소 [0.11089082, 0.4393365] 는 자기자신으로 생략하고
두번째 원소 [0.2017192, 0.8957636] 는 비교대상 점이다. 

distance_sq 는 각 비교대상 원소 (2, -)의 첫번째 값 X 값 과 두번째 값 Y 값으로, X값 간 오차 제곱과 Y값 간 오차 제곱의 합을 구하였다.

 

그래서 이런 공식이 나온다. 

dist_sq = np.sum((X[:, np.newaxis, :]) - X[np.newaxis, :, :] ** 2, axis =2)

 

dish_sq 의 형태는 (10, 10) 이다. 

1 개의 점에 대해서 10 번 비교 하고, 10 개의 점에 대해서 10 * 10 번 비교하기 때문.

파랑으로 표시된 부분은 첫 기준점  [0.11089082, 0.4393365] 에 대해 각 비교 대상 점에 대한 거리의 제곱을 의미한다. 

 

3. 가장 근접한 점 2개 고르기

파랑으로 표시된 부분은 첫 기준점  [0.11089082, 0.4393365] 의 거리 제곱 배열 중

자기 자신과 비교한 0 을 제외하고, 가장 작은 값 2개는 다음과 같다. (빨강 표시) 

 

위 배열에서 배열 전에 있던 인덱스를 확인만 하고 싶을 때 다음과 같이 사용한다.  np.argsort

 

사실 우리는 근접값 2개 (기준점 자기자신 포함하면 3개)에 대해서만 정렬하면 되므로, 파티셔닝을 사용한다. np.partition_sort

 

4. 이제 기준점과 최 근접점 2개를 이어서 그린다.

선을 포함해서 그리는 방법은 아직 배우지 않았으므로 코드 복사했다.

- 10 개의 점에 대해서  

- nearst_partition 에서 각 기준점의 최근접점 파티셔닝 배열 nearst_partition 에서 앞 3개의 원소를 가져와서

그린다. (허허)

 

 

5. 요약

벡터화된 방식의 장점은 입력 데이터의 크기에 구애받지 않는 방식으로 작성되었다는 점이다. 임의의 차원에서 100개든 100만 개든 그 사이의 이웃을 쉽게 계산할 수 있고 코드도 동일하다.