Sắp xếp nhanh trong NumPy: np.sort và np.argsort¶
Mặc dù Python có các hàm sort và sorted tích hợp sẵn để làm việc với danh sách, chúng ta sẽ không thảo luận về chúng ở đây vì hàm np.sort của NumPy lại rất hiệu quả và hữu ích cho mục đích của chúng ta.Theo mặc định, np.sort sử dụng thuật toán quicksort với độ phức tạp $\mathcal{O}[N\log N]$, tuy nhiên, mergesort và heapsort cũng có sẵn. Đối với đa số ứng dụng, quicksort mặc định là đủ để thực hiện công việc.
Để trả về một phiên bản đã được sắp xếp của mảng mà không thay đổi đầu vào, bạn có thể sử dụng np.sort:
x = np.array([2, 1, 4, 3, 5])np.sort(x)
array([1, 2, 3, 4, 5])
Nếu bạn thích sắp xếp mảng trực tiếp, bạn có thể sử dụng phương thức sort của mảng:
x.sort()print(x)
[1 2 3 4 5]
Một chức năng liên quan là argsort, thay vào đó trả về các chỉ số của các phần tử đã được sắp xếp:
x = np.array([2, 1, 4, 3, 5])i = np.argsort(x)print(i)
[1 0 3 2 4]
Phần tử đầu tiên của kết quả này cho chỉ số của phần tử nhỏ nhất, giá trị thứ hai cho chỉ số của phần tử nhỏ thứ hai, và cứ tiếp tục như vậy.Các chỉ số này sau đó có thể được sử dụng (qua chỉ số phức tạp) để xây dựng mảng đã được sắp xếp nếu muốn:
x[i]
array([1, 2, 3, 4, 5])
Sắp xếp theo dòng hay cột¶
Một tính năng hữu ích của thuật toán sắp xếp của NumPy là khả năng sắp xếp theo hàng hoặc cột cụ thể của một mảng đa chiều bằng cách sử dụng đối số axis. Ví dụ:
rand = np.random.RandomState(42)X = rand.randint(0, 10, (4, 6))print(X)
[[6 3 7 4 6 9] [2 6 7 4 3 7] [7 2 5 4 1 7] [5 1 4 0 9 5]]
# sort each column of Xnp.sort(X, axis=0)
array([[2, 1, 4, 0, 1, 5], [5, 2, 5, 4, 3, 7], [6, 3, 7, 4, 6, 7], [7, 6, 7, 4, 9, 9]])
# sort each row of Xnp.sort(X, axis=1)
array([[3, 4, 6, 6, 7, 9], [2, 3, 4, 6, 7, 7], [1, 2, 4, 5, 7, 7], [0, 1, 4, 5, 5, 9]])
Hãy nhớ rằng điều này xử lý mỗi hàng hoặc cột như một mảng độc lập, và mọi mối quan hệ giữa giá trị hàng hoặc cột sẽ bị mất!
Sắp xếp phần: Phân đoạn¶
Đôi khi chúng ta không quan tâm đến việc sắp xếp toàn bộ mảng, mà chỉ muốn tìm k giá trị nhỏ nhất trong mảng. NumPy cung cấp điều này trong chức năng np.partition . np.partition nhận một mảng và một số K ; kết quả là một mảng mới với các giá trị nhỏ nhất K ở bên trái của phân vùng, và các giá trị còn lại ở bên phải, theo thứ tự tùy ý:
x = np.array([7, 2, 3, 1, 6, 5, 4])np.partition(x, 3)
array([2, 1, 3, 4, 6, 5, 7])
Lưu ý rằng ba giá trị đầu tiên trong mảng kết quả là ba giá trị nhỏ nhất trong mảng và các vị trí mảng còn lại chứa các giá trị còn lại.Trong hai phần, các phần tử có thứ tự tùy ý.
Tương tự như việc sắp xếp, chúng ta có thể phân vùng theo một trục tùy ý của một mảng đa chiều:
np.partition(X, 2, axis=1)
array([[3, 4, 6, 7, 6, 9], [2, 3, 4, 7, 6, 7], [1, 2, 4, 5, 7, 7], [0, 1, 4, 5, 9, 5]])
Kết quả là một mảng trong đó hai ô đầu tiên trong mỗi hàng chứa các giá trị nhỏ nhất từ hàng đó, với các giá trị còn lại điền vào các ô còn lại.
Kết thúc cùng như việc có một np.argsort được tính toán chỉ số của sắp xếp, cũng có một np.argpartition được tính toán chỉ số của phân vùng.Chúng ta sẽ thấy điều này trong hành động ở phần tiếp theo.
Ví dụ: k-Nearest Neighbors¶
Hãy nhanh chóng xem cách chúng ta có thể sử dụng hàm argsort này trên nhiều trục để tìm các hàng xóm gần nhất của mỗi điểm trong một tập hợp.Chúng ta sẽ bắt đầu bằng cách tạo một tập hợp ngẫu nhiên gồm 10 điểm trên một mặt phẳng hai chiều.Sử dụng quy ước tiêu chuẩn, chúng ta sẽ sắp xếp chúng trong một mảng $10\times 2$:
X = rand.rand(10, 2)
Để hiểu điểm đó trông như thế nào, hãy nhanh chóng phân tán chúng việc biểu đồ:
%matplotlib inlineimport matplotlib.pyplot as pltimport seaborn; seaborn.set() # Plot stylingplt.scatter(X[:, 0], X[:, 1], s=100);
Bây giờ chúng ta sẽ tính khoảng cách giữa mỗi cặp điểm.Nhớ rằng khoảng cách bình phương giữa hai điểm là tổng của bình phương sự khác biệt trong mỗi chiều;sử dụng các rutin broadcasting hiệu quả (Computation on Arrays: Broadcasting) và aggregate (Aggregations: Min, Max, and Everything In Between) được cung cấp bởi NumPy, chúng ta có thể tính ma trận các khoảng cách bình phương trong một dòng code duy nhất:
dist_sq = np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis=-1)
Hoạt động này có rất nhiều đóng gói vào đó và có thể hơi khó hiểu nếu bạn không quen với quy tắc phát sóng trong NumPy. Khi bạn gặp phải mã như thế này, nó có thể hữu ích để phân tách nó thành các bước thành phần:
# for each pair of points, compute differences in their coordinatesdifferences = X[:, np.newaxis, :] - X[np.newaxis, :, :]differences.shape
(10, 10, 2)
# square the coordinate differencessq_differences = differences ** 2sq_differences.shape
(10, 10, 2)
# sum the coordinate differences to get the squared distancedist_sq = sq_differences.sum(-1)dist_sq.shape
(10, 10)
Chỉ để kiểm tra lại những gì chúng ta đang làm, chúng ta nên thấy rằng đường chéo của ma trận này (tức là tập hợp các khoảng cách giữa mỗi điểm và chính nó) đều bằng không:
dist_sq.diagonal()
array([ 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
Điều này đã kiểm tra!
nearest = np.argsort(dist_sq, axis=1)print(nearest)
[[0 3 9 7 1 4 2 5 6 8] [1 4 7 9 3 6 8 5 0 2] [2 1 4 6 3 0 8 9 7 5] [3 9 7 0 1 4 5 8 6 2] [4 1 8 5 6 7 9 3 0 2] [5 8 6 4 1 7 9 3 2 0] [6 8 5 4 1 7 9 3 2 0] [7 9 3 1 4 0 5 8 6 2] [8 5 6 4 1 7 9 3 2 0] [9 7 3 0 1 4 5 8 6 2]]
Lưu ý rằng cột đầu tiên đưa ra các số từ 0 đến 9 theo thứ tự: điều này là do việc hàng xóm gần nhất của mỗi điểm là chính nó, như chúng ta mong đợi.
Bằng cách sử dụng sắp xếp đầy đủ ở đây, chúng ta thực sự đã làm nhiều công việc hơn là cần thiết trong trường hợp này. Nếu chúng ta đơn giản chỉ quan tâm đến $k$ hàng xóm gần nhất, tất cả những gì chúng ta cần là phân vùng mỗi hàng để khoảng cách bình phương $k + 1$ nhỏ nhất đến đầu mảng, với những khoảng cách lớn hơn điền vào các vị trí còn lại của mảng. Chúng ta có thể thực hiện điều này bằng cách sử dụng hàm np.argpartition:
K = 2nearest_partition = np.argpartition(dist_sq, K + 1, axis=1)
Để hiển thị mạng lưới các hàng xóm này, hãy nhanh chóng vẽ các điểm cùng với các đường thể hiện kết nối từ mỗi điểm tới hai hàng xóm gần nhất của nó:
plt.scatter(X[:, 0], X[:, 1], s=100)# draw lines from each point to its two nearest neighborsK = 2for i in range(X.shape[0]): for j in nearest_partition[i, :K+1]: # plot a line from X[i] to X[j] # use some zip magic to make it happen: plt.plot(*zip(X[j], X[i]), color='black')
Mỗi điểm trên đồ thị có các đường được vẽ đến hai điểm láng giềng gần nhất.Khi xem quá nhanh, có thể dường như lạ khi một số điểm có nhiều hơn hai đường vẽ đi từ chúng: điều này do thực tế rằng nếu điểm A là một trong hai điểm láng giềng gần nhất của điểm B, điều này không nhất thiết ám chỉ rằng điểm B là một trong hai điểm láng giềng gần nhất của điểm A.
Mặc dù việc phát sóng và sắp xếp theo hàng của phương pháp này có vẻ phức tạp hơn viết một vòng lặp, nhưng nó lại là một cách rất hiệu quả để thao tác trên dữ liệu này trong Python.Bạn có thể cảm thấy cám dỗ để thực hiện cùng loại hoạt động bằng cách lặp qua dữ liệu một cách thủ công và sắp xếp từng set hàng xóm một cách riêng biệt, nhưng điều này chắc chắn sẽ dẫn đến một thuật toán chậm hơn so với phiên bản vectorized mà chúng ta đã sử dụng. Điều tuyệt vời của phương pháp này là nó được viết một cách đồng nhất với kích thước của dữ liệu đầu vào: chúng ta có thể dễ dàng tính toán hàng xóm trong 100 hoặc 1,000,000 điểm trong bất kỳ số chiều nào, và mã sẽ trông giống nhau.
Cuối cùng, tôi muốn nhắc rằng khi thực hiện tìm kiếm hàng xóm gần nhất với số lượng lớn, có các thuật toán dựa trên cây và/hoặc xấp xỉ có thể tỉ lệ theo $\mathcal{O}[N\log N]$ hoặc tốt hơn thay vì $\mathcal{O}[N^2]$ của thuật toán vét cạn. Một ví dụ về điều này là giao diện KD-Tree, được thực hiện trong Scikit-learn.
Nhận định: Đánh giá độ phức tạp Big-O¶
Khái niệm Big-O được sử dụng để mô tả cách số lượng thao tác được yêu cầu cho một thuật toán tăng theo kích thước đầu vào.Để sử dụng nó đúng là để đào sâu vào lĩnh vực lý thuyết khoa học máy tính, và để phân biệt cẩn thận nó với các khái niệm liên quan như small-o, big-$\theta$, big-$\Omega$ và có lẽ nhiều khái niệm lai khác.Trong khi những phân biệt này mang lại sự chính xác cho các tuyên bố về tỷ lệ thuật toán, bên ngoài các kỳ thi lý thuyết máy tính và các bình luận đạo đức của các bài viết trên blog, bạn hiếm khi thấy những phân biệt như vậy được thực hiện trong thực tế.Trong thế giới khoa học dữ liệu, thường gặp một cách sử dụng ít cứng nhắc hơn của khái niệm Big-O: như một mô tả chung (nếu chưa chính xác) về quá trình mở rộng của một thuật toán.Xin lỗi với các nhà lý thuyết và những người khoa học tỉ mỉ, đây là cách hiểu chúng tôi sẽ sử dụng trong suốt cuốn sách này.
Big-O notation, trong ngữ cảnh rộng rãi này, cho bạn biết thời gian mà thuật toán của bạn sẽ mất khi bạn tăng số lượng dữ liệu.Nếu bạn có một thuật toán $\mathcal{O}[N]$ (đọc là “order $N$”) mà mất 1 giây để thực hiện trên một danh sách có độ dài N=1,000, thì bạn nên mong đợi nó sẽ mất khoảng 5 giây cho một danh sách có độ dài N=5,000.Nếu bạn có một thuật toán $\mathcal{O}[N^2]$ (đọc là “order N square”) mà mất 1 giây cho N=1,000, thì bạn nên mong đợi nó sẽ mất khoảng 25 giây cho N=5,000.
Cho mục đích của chúng tôi, N thường sẽ chỉ ra một khía cạnh nào đó của kích thước của bộ dữ liệu (số điểm, số chiều, v.v.). Khi cố gắng phân tích hàng tỷ hoặc hàng nghìn tỷ mẫu, sự khác biệt giữa $\mathcal{O}[N]$ và $\mathcal{O}[N^2]$ có thể không đơn giản!
Lưu ý rằng định dạng big-O notation trong bản thân nó không nói về thời gian thực tế của một tính toán, mà chỉ nói về sự thay đổi tỉ lệ khi bạn thay đổi N.Nhìn chung, ví dụ như, một thuật toán $\mathcal{O}[N]$ được coi là có sự thay đổi tỉ lệ tốt hơn so với một thuật toán $\mathcal{O}[N^2]$, và có lý do chính đáng. Nhưng đối với các bộ dữ liệu nhỏ, thuật toán có sự thay đổi tỉ lệ tốt hơn có thể không nhanh hơn.Ví dụ, trong một vấn đề cụ thể, một thuật toán $\mathcal{O}[N^2]$ có thể mất 0.01 giây, trong khi một thuật toán “tốt hơn” $\mathcal{O}[N]$ có thể mất 1 giây.Tuy nhiên, nếu tăng N lên 1.000 lần, thuật toán $\mathcal{O}[N]$ sẽ giành chiến thắng.
Ngay cả phiên bản lỏng này của ký hiệu Big-O có thể rất hữu ích khi so sánh hiệu suất của các thuật toán, và chúng tôi sẽ sử dụng ký hiệu này trong suốt cuốn sách khi nói về cách thức các thuật toán tỷ lệ.
