knn from scratch

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.9%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20return%20mo%2C%20np%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20kNN%20from%20Scratch%0A%0A%20%20%20%20**ML%20interview%20staple%20%E2%80%94%20implement%20ML%20algorithms%20from%20scratch**%0A%0A%20%20%20%20Implement%20the%20**k-Nearest%20Neighbours**%20classifier%20using%20NumPy%20only%0A%20%20%20%20(no%20%60sklearn%60).%0A%0A%20%20%20%20**Algorithm**%3A%0A%20%20%20%201.%20For%20each%20test%20point%20%60x%60%2C%20compute%20its%20Euclidean%20distance%20to%20every%0A%20%20%20%20%20%20%20training%20point.%0A%20%20%20%202.%20Find%20the%20%60k%60%20nearest%20training%20points%20(smallest%20distances).%0A%20%20%20%203.%20Return%20the%20**majority%20label**%20among%20those%20%60k%60%20neighbours.%0A%20%20%20%20%20%20%20Break%20ties%20by%20choosing%20the%20smaller%20label.%0A%0A%20%20%20%20**ML%20relevance**%3A%20kNN%20is%20used%20as%20a%20baseline%2C%20for%20anomaly%20detection%2C%20and%0A%20%20%20%20for%20embedding-space%20retrieval%20(approximate%20nearest-neighbour%20search%20is%20the%0A%20%20%20%20foundation%20of%20vector%20databases).%20%20Writing%20it%20from%20scratch%20demonstrates%20that%0A%20%20%20%20you%20can%20translate%20an%20algorithm%20description%20into%20vectorised%20NumPy%20code.%0A%0A%20%20%20%20%23%23%20Vectorised%20implementation%20(O(n%20%C2%B7%20m%20%C2%B7%20d)%20but%20all%20in%20numpy)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20%23%20---%20student%3A%20begin%20---%0A%0A%20%20%20%20def%20knn_predict(%0A%20%20%20%20%20%20%20%20X_train%3A%20np.ndarray%2C%20%20%20%23%20%5Bn%2C%20d%5D%20%20training%20features%0A%20%20%20%20%20%20%20%20y_train%3A%20np.ndarray%2C%20%20%20%23%20%5Bn%5D%20%20%20%20%20training%20labels%20(non-negative%20integers)%0A%20%20%20%20%20%20%20%20X_test%3A%20%20np.ndarray%2C%20%20%20%23%20%5Bm%2C%20d%5D%20%20test%20features%0A%20%20%20%20%20%20%20%20k%3A%20%20%20%20%20%20%20int%2C%20%20%20%20%20%20%20%20%20%20%23%20number%20of%20neighbours%0A%20%20%20%20)%20-%3E%20np.ndarray%3A%20%20%20%20%20%20%20%20%20%20%20%23%20%5Bm%5D%20%20%20%20%20predicted%20labels%0A%20%20%20%20%20%20%20%20%22%22%22kNN%20classifier%3A%20majority%20vote%20among%20the%20k%20nearest%20training%20neighbours.%0A%0A%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20X_train%3A%20training%20feature%20matrix%2C%20shape%20(n_train%2C%20n_features)%0A%20%20%20%20%20%20%20%20%20%20%20%20y_train%3A%20training%20labels%2C%20shape%20(n_train%2C)%2C%20dtype%20int%0A%20%20%20%20%20%20%20%20%20%20%20%20X_test%3A%20%20test%20feature%20matrix%2C%20shape%20(n_test%2C%20n_features)%0A%20%20%20%20%20%20%20%20%20%20%20%20k%3A%20%20%20%20%20%20%20number%20of%20nearest%20neighbours%20to%20use%0A%0A%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20Predicted%20class%20labels%20for%20each%20test%20point%2C%20shape%20(n_test%2C).%0A%20%20%20%20%20%20%20%20%20%20%20%20Ties%20broken%20by%20taking%20the%20smaller%20label%20index.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20raise%20NotImplementedError(%22Implement%20knn_predict%22)%0A%0A%20%20%20%20%23%20---%20student%3A%20end%20---%0A%20%20%20%20return%20(knn_predict%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(knn_predict%2C%20mo%2C%20np)%3A%0A%20%20%20%20def%20_oracle(X_train%2C%20y_train%2C%20X_test%2C%20k)%3A%0A%20%20%20%20%20%20%20%20diffs%20%3D%20X_test%5B%3A%2C%20np.newaxis%2C%20%3A%5D%20-%20X_train%5Bnp.newaxis%2C%20%3A%2C%20%3A%5D%0A%20%20%20%20%20%20%20%20dists%20%3D%20np.sqrt((diffs%20**%202).sum(axis%3D-1))%0A%20%20%20%20%20%20%20%20knn_idx%20%3D%20np.argsort(dists%2C%20axis%3D1)%5B%3A%2C%20%3Ak%5D%0A%20%20%20%20%20%20%20%20knn_labels%20%3D%20y_train%5Bknn_idx%5D%0A%20%20%20%20%20%20%20%20n_classes%20%3D%20int(y_train.max())%20%2B%201%0A%20%20%20%20%20%20%20%20preds%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20row%20in%20knn_labels%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20counts%20%3D%20np.bincount(row%2C%20minlength%3Dn_classes)%0A%20%20%20%20%20%20%20%20%20%20%20%20preds.append(int(counts.argmax()))%0A%20%20%20%20%20%20%20%20return%20np.array(preds)%0A%0A%20%20%20%20_solved%20%3D%20False%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20rng%20%3D%20np.random.default_rng(0)%0A%0A%20%20%20%20%20%20%20%20%23%20%E2%94%80%E2%94%80%20Test%201%3A%20simple%202-class%2C%201D%20%E2%94%80%E2%94%80%0A%20%20%20%20%20%20%20%20_Xtr%20%3D%20np.array(%5B%5B1.0%5D%2C%20%5B2.0%5D%2C%20%5B10.0%5D%2C%20%5B11.0%5D%5D)%0A%20%20%20%20%20%20%20%20_ytr%20%3D%20np.array(%5B0%2C%200%2C%201%2C%201%5D)%0A%20%20%20%20%20%20%20%20_Xte%20%3D%20np.array(%5B%5B1.5%5D%2C%20%5B10.5%5D%5D)%0A%20%20%20%20%20%20%20%20_pred%20%3D%20knn_predict(_Xtr%2C%20_ytr%2C%20_Xte%2C%20k%3D1)%0A%20%20%20%20%20%20%20%20assert%20np.array_equal(_pred%2C%20%5B0%2C%201%5D)%2C%20f%22Test%201%3A%20expected%20%5B0%2C1%5D%2C%20got%20%7B_pred.tolist()%7D%22%0A%0A%20%20%20%20%20%20%20%20%23%20%E2%94%80%E2%94%80%20Test%202%3A%20majority%20vote%20%E2%94%80%E2%94%80%0A%20%20%20%20%20%20%20%20_Xtr2%20%3D%20np.array(%5B%5B0.0%2C0.0%5D%2C%5B1.0%2C0.0%5D%2C%5B0.0%2C1.0%5D%2C%5B5.0%2C5.0%5D%5D)%0A%20%20%20%20%20%20%20%20_ytr2%20%3D%20np.array(%5B0%2C%200%2C%201%2C%201%5D)%0A%20%20%20%20%20%20%20%20_Xte2%20%3D%20np.array(%5B%5B0.1%2C%200.1%5D%5D)%20%20%23%20nearest%3A%20(0%2C0)%2C(1%2C0)%2C(0%2C1)%20%E2%86%92%202%C3%97class0%2C%201%C3%97class1%0A%20%20%20%20%20%20%20%20_pred2%20%3D%20knn_predict(_Xtr2%2C%20_ytr2%2C%20_Xte2%2C%20k%3D3)%0A%20%20%20%20%20%20%20%20assert%20_pred2%5B0%5D%20%3D%3D%200%2C%20f%22Test%202%20(majority%20vote)%3A%20expected%200%2C%20got%20%7B_pred2%5B0%5D%7D%22%0A%0A%20%20%20%20%20%20%20%20%23%20%E2%94%80%E2%94%80%20Test%203%3A%20compare%20to%20oracle%20on%20random%20data%20%E2%94%80%E2%94%80%0A%20%20%20%20%20%20%20%20_n%2C%20_d%2C%20_m%20%3D%2080%2C%204%2C%2020%0A%20%20%20%20%20%20%20%20_Xtr3%20%3D%20rng.standard_normal((_n%2C%20_d))%0A%20%20%20%20%20%20%20%20_ytr3%20%3D%20rng.integers(0%2C%203%2C%20_n)%0A%20%20%20%20%20%20%20%20_Xte3%20%3D%20rng.standard_normal((_m%2C%20_d))%0A%20%20%20%20%20%20%20%20_pred3%20%20%3D%20knn_predict(_Xtr3%2C%20_ytr3%2C%20_Xte3%2C%20k%3D5)%0A%20%20%20%20%20%20%20%20_oracle3%20%3D%20_oracle(_Xtr3%2C%20_ytr3%2C%20_Xte3%2C%20k%3D5)%0A%20%20%20%20%20%20%20%20assert%20_pred3.shape%20%3D%3D%20(_m%2C)%2C%20f%22Shape%3A%20expected%20(%7B_m%7D%2C)%2C%20got%20%7B_pred3.shape%7D%22%0A%20%20%20%20%20%20%20%20_acc%20%3D%20np.mean(_pred3%20%3D%3D%20_oracle3)%0A%20%20%20%20%20%20%20%20assert%20_acc%20%3D%3D%201.0%2C%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Test%203%3A%20predictions%20differ%20from%20oracle%20on%20%7Bint((1-_acc)*_m)%7D%2F%7B_m%7D%20points%22%0A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%E2%9C%85%20%60knn_predict%60%20is%20correct!%20%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22Oracle%20match%3A%20%7Bint(_acc*_m)%7D%2F%7B_m%7D%20test%20points.%22%0A%20%20%20%20%20%20%20%20)%2C%20kind%3D%22success%22)%0A%20%20%20%20%20%20%20%20_solved%20%3D%20True%0A%20%20%20%20except%20NotImplementedError%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9C%8F%EF%B8%8F%20%7Be%7D%22)%2C%20kind%3D%22neutral%22)%0A%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20_result%20%3D%20mo.callout(mo.md(f%22%E2%9D%8C%20%7Be%7D%22)%2C%20kind%3D%22danger%22)%0A%20%20%20%20%23%20---%20capture%20%26%20report%20---%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20import%20inspect%20as%20_inspect%2C%20json%20as%20_json%2C%20js%20as%20_js%0A%20%20%20%20%20%20%20%20from%20pyodide.ffi%20import%20to_js%20as%20_to_js%0A%20%20%20%20%20%20%20%20_srcs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_fn%20in%20(knn_predict%2C)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_srcs.append(_inspect.getsource(_fn))%0A%20%20%20%20%20%20%20%20%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20%20%20%20%20_payload%20%3D%20_json.dumps(%7B%22notebookId%22%3A%20%22ml_interview%2Fknn_from_scratch%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22code%22%3A%20%22%5Cn%5Cn%22.join(_srcs)%2C%20%22solved%22%3A%20bool(_solved)%7D)%0A%20%20%20%20%20%20%20%20if%20_solved%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch%20%3D%20_js.BroadcastChannel.new(%22mlp-notebooks%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.postMessage(_js.JSON.parse(_json.dumps(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%22type%22%3A%20%22mlp%3Anotebook-solved%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22notebookId%22%3A%20%22ml_interview%2Fknn_from_scratch%22%7D)))%0A%20%20%20%20%20%20%20%20%20%20%20%20_ch.close()%0A%20%20%20%20%20%20%20%20_js.fetch(%22%2Fapi%2Fnotebook-progress%22%2C%20_to_js(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%22method%22%3A%20%22POST%22%2C%20%22headers%22%3A%20%7B%22Content-Type%22%3A%20%22application%2Fjson%22%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%22credentials%22%3A%20%22include%22%2C%20%22body%22%3A%20_payload%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20dict_converter%3D_js.Object.fromEntries))%0A%20%20%20%20except%20Exception%3A%0A%20%20%20%20%20%20%20%20pass%0A%20%20%20%20mo.output.replace(_result)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A