<jupyter_start><jupyter_text>Let's look at a random set of 10 2-dimensional points, and plot them on a 2-dimensional plane.<jupyter_code>X = np.random.rand(10, 2)
X.shape
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn; seaborn.set() # Plot styling
plt.scatter(X[:, 0], X[:, 1], s=100);
col_vec = X[:, np.newaxis, :]
col_vec.shape
row_vec = X[np.newaxis, :, :]
row_vec.shape
diff = col_vec - row_vec # Using brodcasting: subtracting a row of points from a column of points: we get a matrix
# diff[i, j, 0] contains del_x_ij = x_i - x_j; diff[i, j, 1] contains del_y_ij = y_i - j_j
diff.shape
sq_diff = diff ** 2
# sq_diff[i, j, 0] containes del_x = (x_i - x_j) ** 2; sq_diff[i, j, 1] contains del_y = (y_i - y_j) ** 2
sq_diff.shape
dist_sq = sq_diff.sum(-1)
# summing along the last axis, we get sq_del_x + sq_del_y, or the squared distance
dist_sq.shape
# verify: the diagonal of the matrix is the squared distance from a point to itself, which should be zero
dist_sq.diagonal()
# Use `argsort` to sort each row.  The elements in row `i` are sorted by distance from point `i`.
nearest_sorted_idx = np.argsort(dist_sq, axis=1)
nearest_sorted_idx<jupyter_output><empty_output><jupyter_text>The first column of row `i` contains the index of point `i`, which makes sense, as a point is closest to itself.We actually have a full sort, when all we needed was *k*-nearest points.  We could, instead of a sort, partition each row so that the smallest `k + 1` sqaured distances come first, with larger distances filling the remaining positions of the array.  We can do this like so:<jupyter_code>K = 2
nearest_partition_idx = np.argpartition(dist_sq, K + 1, axis=1)
nearest_partition_idx<jupyter_output><empty_output><jupyter_text>Let us visualize the points, and also the lines representing the connections from each point to its *K* nearest neighbors.<jupyter_code>plt.scatter(X[:, 0], X[:, 1], s=100)
K = 2
for i in range(X.shape[0]):
    for j in nearest_partition_idx[i, :K+1]:
        # plot a line from X[i] to X[j], using some zip magic to make it happen
        plt.plot(*zip(X[j], X[i]), color='black')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10966542750929369, 'fraction_numerical': 0.01533457249070632, 'mean_word_length': 4.710875331564987, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '458494', 'license': 'Apache-2.0', 'n_tokens_mistral': 791, 'n_tokens_neox': 758, 'n_words': 282, 'path': 'machine_learning/jupyter_101/K-Nearest Neighbors.ipynb', 'repo_name': 'parijatmishra/learn', 'size': '2152'}